rfc813.txt

RFC 相关的技术文档

sender should simply refuse to send anything.


     Simple experiments suggest that the exact value of the ratio is not

very important, but that a value of about 25 percent  is  sufficient  to

avoid  SWS  and  achieve reasonable throughput, even for machines with a

small offered window.    An  additional  enhancement  which  might  help

throughput  would be to attempt to hold off sending until one can send a

maximum size segment.  Another enhancement would be to send anyway, even

if the ratio is small, if the useable window is sufficient to  hold  the

data available up to the next "push point".


     This algorithm at the sender end is very simple.  Notice that it is

not  necessary  to  set  a timer to protect against protocol lockup when

postponing the  send  operation.    Further  acknowledgements,  as  they

arrive,  will  inevitably change the ratio of offered to useable window.

(To see this, note that when all the data in the  catanet  pipeline  has

arrived  at  the  receiver,  the resulting acknowledgement must yield an

offered window and  useable  window  that  equal  each  other.)  If  the

expected  acknowledgements  do  not arrive, the retransmission mechanism

will come into play to assure that something finally happens.  Thus,  to

add  this  algorithm  to an existing TCP implementation usually requires

one line of code.  As part of the send algorithm it is already necessary

to compute the useable window from the offered window.  It is  a  simple

matter  to add a line of code which, if the ratio is less than a certain

                                   9


percent,  sets  the  useable  window to zero.  The results of SWS are so

devastating that no sender  should  be  without  this  simple  piece  of

insurance.


     5.  Improved Acknowledgement Algorithms


     In the beginning of this paper, an overly simplistic implementation

of  TCP  was described, which led to SWS.  One of the characteristics of

this implementation was that the  recipient  of  data  sent  a  separate

acknowledgement  for  every  segment  that it received.  This compulsive

acknowledgement  was  one  of  the   causes   of   SWS,   because   each

acknowledgement provided some new useable window, but even if one of the

algorithms  described  above  is  used to eliminate SWS, overly frequent

acknowledgement still has  a  substantial  problem,  which  is  that  it

greatly  increases the processing time at the sender's end.  Measurement

of TCP implementations, especially on large operating systems,  indicate

that  most  of  the  overhead  of  dealing  with a segment is not in the

processing at the TCP or IP level, but simply in the scheduling  of  the

handler which is required to deal with the segment.  A steady dribble of

acknowledgements  causes a high overhead in scheduling, with very little

to show for it.  This waste is to be avoided if possible.


     There are two reasons  for  prompt  acknowledgement.    One  is  to

prevent  retransmission.  We will discuss later how to determine whether

unnecessary  retransmission  is  occurring.    The  other   reason   one

acknowledges  promptly  is  to permit further data to be sent.  However,

the previous section makes quite clear that it is not  always  desirable

to send a little bit of data, even though the receiver may have room for

                                   10


it.    Therefore,  one  can  state  a  general  rule  that  under normal

operation, the receiver of data need not,  and  for  efficiency  reasons

should  not,  acknowledge  the data unless either the acknowledgement is

intended to produce an increased useable window, is necessary  in  order

to  prevent  retransmission  or  is  being  sent  as  part  of a reverse

direction segment being sent for some other reason.  We will consider an

algorithm to achieve these goals.


     Only the recipient of  the  data  can  control  the  generation  of

acknowledgements.    Once  an  acknowledgement  has  been  sent from the

receiver back to the sender, the sender must process it.   Although  the

extra overhead is incurred at the sender's end, it is entirely under the

receiver's  control.  Therefore, we must now describe an algorithm which

occurs at the receiver's end.  Obviously, the algorithm  must  have  the

following  general form; sometimes the receiver of data, upon processing

a segment, decides not to send an acknowledgement now, but  to  postpone

the  acknowledgement until some time in the future, perhaps by setting a

timer.  The peril of this approach  is  that  on  many  large  operating

systems  it  is  extremely costly to respond to a timer event, almost as

costly as to respond to an incoming segment.  Clearly, if  the  receiver

of  the data, in order to avoid extra overhead at the sender end, spends

a great deal of time responding to timer interrupts, no overall  benefit

has been achieved, for efficiency at the sender end is achieved by great

thrashing  at  the  receiver end.  We must find an algorithm that avoids

both of these perils.


     The following scheme seems a good compromise.  The receiver of data

                                   11


will   refrain   from   sending   an   acknowledgement   under   certain

circumstances, in which case it must set a timer which  will  cause  the

acknowledgement  to be sent later.  However, the receiver should do this

only where it is a reasonable guess that some other event will intervene

and prevent the necessity of the timer  interrupt.    The  most  obvious

event  on  which  to depend is the arrival of another segment.  So, if a

segment arrives, postpone sending an  acknowledgement  if  both  of  the

following  conditions  hold.    First,  the  push  bit is not set in the

segment, since it is a reasonable assumption that  there  is  more  data

coming  in  a  subsequent  segment.   Second, there is no revised window

information to be sent back.


     This algorithm will insure that the timer, although set, is  seldom

used.    The  interval  of  the  timer is related to the expected inter-

segment delay, which is in turn a function  of  the  particular  network

through  which  the  data  is  flowing.    For the Arpanet, a reasonable

interval seems to be 200 to 300 milliseconds.  Appendix A  describes  an

adaptive algorithm for measuring this delay.


     The section on improved window algorithms described both a receiver

algorithm  and  a  sender  algorithm,  and suggested that both should be

used.  The reason for this is now clear.  While the sender algorithm  is

extremely  simple,  and  useful  as insurance, the receiver algorithm is

required in order that this improved acknowledgement strategy work.   If

the  receipt  of every segment causes a new window value to be returned,

then of necessity  an  acknowledgement  will  be  sent  for  every  data

segment.    When, according to the strategy of the previous section, the

                                   12


receiver  determines  to artificially reduce the offered window, that is

precisely the circumstance under which an acknowledgement  need  not  be

sent.      When   the   receiver   window  algorithm  and  the  receiver

acknowledgement algorithm are  used  together,  it  will  be  seen  that

sending  an  acknowledgement  will  be triggered by one of the following

events.  First, a push bit has been received.  Second, a temporary pause

in the data stream is detected.  Third,  the  offered  window  has  been

artificially reduced to one-half its actual value.


     In the beginning of this section, it was pointed out that there are

two  reasons  why  one must acknowledge data.  Our consideration at this

point has been concerned only with the first,  that  an  acknowledgement

must  be  returned as part of triggering the sending of new data.  It is

also necessary to acknowledge  whenever  the  failure  to  do  so  would

trigger retransmission by the sender.  Since the retransmission interval

is  selected  by  the  sender,  the  receiver  of the data cannot make a

precise  determination  of  when  the  acknowledgement  must  be   sent.

However,   there   is   a  rough  rule  the  sender  can  use  to  avoid

retransmission, provided that the receiver is reasonably well behaved.


     We will assume that sender of the data uses the optional  algorithm

described  in  the  TCP  specification,  in which the roundtrip delay is

measured using an exponential decay smoothing algorithm.  Retransmission

of a segment occurs if the measured delay for that segment  exceeds  the

smoothed  average  by  some  factor.  To see how retransmission might be

triggered, one must consider the pattern  of  segment  arrivals  at  the

receiver.   The goal of our strategy was that the sender should send off

                                   13


a  number of segments in close sequence, and receive one acknowledgement

for the whole burst.  The  acknowledgement  will  be  generated  by  the

receiver  at  the time that the last segment in the burst arrives at the

receiver.  (To ensure the prompt  return  of  the  acknowledgement,  the

sender  could  turn on the "push" bit in the last segment of the burst.)

The delay observed at the sender between the initial transmission  of  a

segment  and  the  receipt  of the acknowledgement will include both the

network transit time, plus the  holding  time  at  the  receiver.    The

holding  time  will be greatest for the first segments in the burst, and

smallest for the last segments  in  the  burst.    Thus,  the  smoothing

algorithm  will  measure  a  delay  which is roughly proportional to the

average roundtrip delay for all the segments in  the  burst.    Problems

will  arise  if  the  average  delay  is  substantially smaller than the

maximum delay  and  the  smoothing  algorithm  used  has  a  very  small

threshold  for  triggering retransmission.  The widest variation between

average and maximum delay  will  occur  when  network  transit  time  is

negligible, and all delay is processing time.  In this case, the maximum

will  be  twice  the  average  (by simple algebra) so the threshold that

controls retransmission should be somewhat more than a factor of two.


     In practice, retransmission of the first segments of  a  burst  has

not  been  a  problem because the delay measured consists of the network

roundtrip  delay,  as  well  as  the  delay  due  to   withholding   the

acknowledgement,  and the roundtrip tends to dominate except in very low

roundtrip time situations (such as when sending to one's self  for  test

purposes).    This low roundtrip situation can be covered very simply by

including a minimum value below which  the  roundtrip  estimate  is  not

permitted to drop.

                                   14


     In  our  experiments  with  this  algorithm,  retransmission due to

faulty calculation of the roundtrip delay occurred only once,  when  the

parameters  of  the exponential smoothing algorithm had been misadjusted

so that they were only  taking  into  account  the  last  two  or  three

segments  sent.   Clearly, this will cause trouble since the last two or

three segments of any burst are the  ones  whose  holding  time  at  the

receiver is minimal, so the resulting total estimate was much lower than

appropriate.   Once the parameters of the algorithm had been adjusted so

that the number of segments taken into account was  approximately  twice

the  number  of  segments  in  a burst of average size, with a threshold

factor of 1.5, no further retransmission has ever been identified due to

this problem, including when sending to ourself and  when  sending  over

high delay nets.


     6.  Conservative Vs. Optimistic Windows


     According  to the TCP specification, the offered window is presumed

to have some relationship to the amount of data which  the  receiver  is

actually  prepared  to receive.  However, it is not necessarily an exact

correspondence.  We will use the term "conservative window" to  describe

the case where the offered window is precisely no larger than the actual

buffering  available.  The drawback to conservative window algorithms is

that they can produce very low throughput in long delay situations.   It

is easy to see that the maximum input of a conservative window algorithm

is  one  bufferfull  every  roundtrip  delay  in the net, since the next

bufferfull cannot be launched until the  updated  window/acknowledgement

information from the previous transmission has made the roundtrip.

                                   15


     In  certain  cases,  it  may  be  possible  to increase the overall

throughput of the transmission by increasing the offered window over the

actual buffer available at the receiver.  Such a strategy we  will  call

an  "optimistic  window" strategy.  The optimistic strategy works if the