doc: Add RFC documents

1 files changed, 1167 insertions, 0 deletions

diff --git a/doc/rfc/rfc813.txt b/doc/rfc/rfc813.txt
new file mode 100644
index 0000000..5817050
--- /dev/null
+++ b/doc/rfc/rfc813.txt
@@ -0,0 +1,1167 @@
+
+RFC:  813
+
+
+              
+                WINDOW AND ACKNOWLEDGEMENT STRATEGY IN TCP
+
+                             David D. Clark
+                  MIT Laboratory for Computer Science
+               Computer Systems and Communications Group
+                               July, 1982
+
+
+     1.  Introduction
+
+
+     This  document describes implementation strategies to deal with two
+
+mechanisms in TCP, the window and the acknowledgement.  These mechanisms
+
+are described in the specification document, but it is  possible,  while
+
+complying with the specification, to produce implementations which yield
+
+very  bad  performance.    Happily,  the pitfalls possible in window and
+
+acknowledgement strategies are very easy to avoid.
+
+
+     It is a much more difficult exercise to verify the performance of a
+
+specification than the correctness.  Certainly, we have less  experience
+
+in  this  area,  and  we  certainly  lack  any  useful formal technique.
+
+Nonetheless, it is important to attempt a specification  in  this  area,
+
+because  different  implementors  might  otherwise  choose superficially
+
+reasonable algorithms  which  interact  poorly  with  each  other.  This
+
+document  presents  a  particular  set of algorithms which have received
+
+testing in the field, and which appear to work properly with each other.
+
+With more experience, these algorithms may become  part  of  the  formal
+
+specification:  until such time their use is recommended.
+
+                                   2
+
+
+2.  The Mechanisms
+
+
+     The acknowledgement mechanism is at the heart of TCP.  Very simply,
+
+when  data  arrives at the recipient, the protocol requires that it send
+
+back an acknowledgement of this data.  The protocol specifies  that  the
+
+bytes  of  data  are  sequentially  numbered,  so that the recipient can
+
+acknowledge data by naming the highest numbered  byte  of  data  it  has
+
+received,  which  also  acknowledges  the  previous  bytes (actually, it
+
+identifies the first byte of data which it has  not  yet  received,  but
+
+this is a small detail).  The protocol contains only a general assertion
+
+that  data  should  be acknowledged promptly, but gives no more specific
+
+indication as to how quickly an acknowledgement must  be  sent,  or  how
+
+much data should be acknowledged in each separate acknowledgement.
+
+
+     The window mechanism is a flow control tool.  Whenever appropriate,
+
+the  recipient of data returns to the sender a number, which is (more or
+
+less) the size of the buffer which the receiver currently has  available
+
+for  additional  data.   This number of bytes, called the window, is the
+
+maximum which the sender is permitted to  transmit  until  the  receiver
+
+returns  some  additional  window.  Sometimes, the receiver will have no
+
+buffer space available, and will return a window value of zero.    Under
+
+these  circumstances,the  protocol  requires  the sender to send a small
+
+segment to the receiver now and then, to see if more data  is  accepted.
+
+If  the  window  remains closed at zero for some substantial period, and
+
+the sender can obtain  no  response  from  the  receiver,  the  protocol
+
+requires  the  sender  to  conclude that the receiver has failed, and to
+
+close  the  connection.    Again,  there  is  very  little   performance
+
+                                   3
+
+
+information  in  the  specification, describing under what circumstances
+
+the window should be increased, and how the  sender  should  respond  to
+
+such revised information.
+
+
+     A  bad implementation of the window algorithm can lead to extremely
+
+poor performance overall.  The degradations which  occur  in  throughput
+
+and  CPU  utilizations  can easily be several factors of ten, not just a
+
+fractional increase.  This particular phenomenon is specific enough that
+
+it has been given the name of Silly Window Syndrome, or  SWS.    Happily
+
+SWS  is  easy  to  avoid  if  a few simple rules are observed.  The most
+
+important function of this memo is to describe SWS, so that implementors
+
+will understand the general nature  of  the  problem,  and  to  describe
+
+algorithms  which  will  prevent  its  occurrence.    This document also
+
+describes   performance   enhancing   algorithms   which    relate    to
+
+acknowledgement,  and  discusses  the  way  acknowledgement  and  window
+
+algorithms interact as part of SWS.
+
+
+     3.  SILLY WINDOW SYNDROME
+
+
+     In order to understand SWS, we must first  define  two  new  terms.
+
+Superficially,  the window mechanism is very simple:  there is a number,
+
+called "the window", which is returned from the receiver to the  sender.
+
+However,  we  must have a more detailed way of talking about the meaning
+
+of this number.  The receiver of data computes a  value  which  we  will
+
+call  the  "offered  window".    In  a  simple  case, the offered window
+
+corresponds to the amount of buffer space  available  in  the  receiver.
+
+This  correspondence  is  not necessarily exact, but is a suitable model
+
+for the discussion to follow.    It  is  the  offered  window  which  is
+
+                                   4
+
+
+actually  transmitted  back from the receiver to the sender.  The sender
+
+uses the offered window  to  compute  a  different  value,  the  "usable
+
+window",  which  is  the  offered window minus the amount of outstanding
+
+unacknowledged data.  The usable window is less than  or  equal  to  the
+
+offered window, and can be much smaller.
+
+
+     Consider  the  following  simple  example.   The receiver initially
+
+provides an offered window of 1,000.  The sender uses up this window  by
+
+sending  five  segments  of 200 bytes each.  The receiver, on processing
+
+the first of these  segments,  returns  an  acknowledgement  which  also
+
+contains  an  updated  window value.  Let us assume that the receiver of
+
+the data has removed the first 200 bytes from the buffer,  so  that  the
+
+receiver once again has 1,000 bytes of available buffer.  Therefore, the
+
+receiver would return, as before, an offered window of 1,000 bytes.  The
+
+sender,  on  receipt  of  this  first  acknowledgement, now computes the
+
+additional number of bytes which may be sent.  In  fact,  of  the  1,000
+
+bytes  which  the recipient is prepared to receive at this time, 800 are
+
+already in transit, having been sent in response to the previous offered
+
+window.  In this case, the usable window is only 200 bytes.
+
+
+     Let us now consider how SWS  arises.    To  continue  the  previous
+
+example,  assume  that at some point, when the sender computes a useable
+
+window of 200 bytes, it has only 50 bytes to send  until  it  reaches  a
+
+"push"  point.   It thus sends 50 bytes in one segment, and 150 bytes in
+
+the next segment. Sometime later, this 50-byte segment  will  arrive  at
+
+the recipient, which will process and remove the 50 bytes and once again
+
+return  an  offered window of 1,000 bytes.  However, the sender will now
+
+                                   5
+
+
+compute  that there are 950 bytes in transit in the network, so that the
+
+useable window is now only 50 bytes.  Thus, the sender will  once  again
+
+send  a  50  byte  segment,  even  though  there  is no longer a natural
+
+boundary to force it.
+
+
+     In fact, whenever the acknowledgement  of  a  small  segment  comes
+
+back, the useable window associated with that acknowledgement will cause
+
+another  segment  of  the  same  small  size  to  be  sent,  until  some
+
+abnormality breaks the pattern.  It is easy to see  how  small  segments
+
+arise,  because  natural  boundaries  in the data occasionally cause the
+
+sender to take a computed useable window and divide it  up  between  two
+
+segments.   Once that division has occurred, there is no natural way for
+
+those useable window allocations to be recombined; thus the breaking  up
+
+of the useable window into small pieces will persist.
+
+
+     Thus,  SWS  is a degeneration in the throughput which develops over
+
+time, during a long data transfer.  If the sender  ever  stops,  as  for
+
+example  when  it runs out of data to send, the receiver will eventually
+
+acknowledge all  the  outstanding  data,  so  that  the  useable  window
+
+computed  by  the  sender  will  equal  the  full  offered window of the
+
+receiver.  At this point the situation will  have  healed,  and  further
+
+data  transmission  over  the  link will occur efficiently.  However, in
+
+large file transfers, which occur without interruption,  SWS  can  cause
+
+appalling  performance.  The network between the sender and the receiver
+
+becomes clogged with  many  small  segments,  and  an  equal  number  of
+
+acknowledgements,  which  in  turn  causes lost segments, which triggers
+
+massive retransmission.  Bad cases of SWS have been seen  in  which  the
+
+                                   6
+
+
+average  segment  size was one-tenth of the size the sender and receiver
+
+were prepared to deal with, and the average number of retransmission per
+
+successful segments sent was five.
+
+
+     Happily, SWS is trivial to avoid.  The following sections  describe
+
+two  algorithms,  one  executed  by the sender, and one by the receiver,
+
+which appear to eliminate SWS completely.  Actually, either algorithm by
+
+itself is sufficient to prevent SWS, and thus  protect  a  host  from  a
+
+foreign  implementation  which  has  failed  to  deal properly with this
+
+problem.  The  two  algorithms  taken  together  produce  an  additional
+
+reduction  in  CPU  consumption, observed in practice to be as high as a
+
+factor of four.
+
+
+     4.  Improved Window Algorithms
+
+
+     The receiver of data can take a very simple step to eliminate  SWS.
+
+When  it  disposes of a small amount of data, it can artificially reduce
+
+the offered window in subsequent acknowledgements, so that  the  useable
+
+window computed by the sender does not permit the sending of any further
+
+data.     At  some  later  time,  when  the  receiver  has  processed  a
+
+substantially larger amount of incoming data, the artificial  limitation
+
+on  the  offered  window  can be removed all at once, so that the sender
+
+computes a sudden large jump rather than a sequence of  small  jumps  in
+
+the useable window.
+
+
+     At  this  level,  the  algorithm  is  quite simple, but in order to
+
+determine exactly when the window should  be  opened  up  again,  it  is
+
+necessary  to  look  at some of the other details of the implementation.
+
+                                   7
+
+
+Depending  on whether the window is held artificially closed for a short
+
+or long time, two problems will  develop.    The  one  we  have  already
+
+discussed  -- never closing the window artificially -- will lead to SWS.
+
+On the other hand, if  the  window  is  only  opened  infrequently,  the
+
+pipeline  of data in the network between the sender and the receiver may
+
+have emptied out while the sender was being held off, so that a delay is
+
+introduced before additional data arrives from the sender.   This  delay
+
+does reduce throughput, but it does not consume network resources or CPU
+
+resources  in  the  process, as does SWS.  Thus, it is in this direction
+
+that one ought to overcompensate.  For a simple implementation,  a  rule
+
+of  thumb  that  seems to work in practice is to artificially reduce the
+
+offered window until the reduction constitutes one half of the available
+
+space, at which point increase the window to advertise the entire  space
+
+again.  In any event, one ought to make the chunk by which the window is
+
+opened  at  least permit one reasonably large segment.  (If the receiver
+
+is so short of buffers that it can never advertise a large enough buffer
+
+to permit at least one large segment, it is hopeless to expect any  sort
+
+of high throughput.)
+
+
+     There  is  an algorithm that the sender can use to achieve the same
+
+effect described above:  a very simple and elegant rule first  described
+
+by  Michael  Greenwald  at MIT.  The sender of the data uses the offered
+
+window to compute a useable window, and then compares the useable window
+
+to the offered window, and refrains from sending anything if  the  ratio
+
+of  useable to offered is less than a certain fraction.  Clearly, if the
+
+computed useable window is small compared to the  offered  window,  this
+
+means  that a substantial amount of previously sent information is still
+
+                                   8
+
+
+in  the  pipeline  from  the sender to the receiver, which in turn means
+
+that the sender can count on being granted a larger  useable  window  in
+
+the  future.    Until  the  useable window reaches a certain amount, the
+
+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
+
+network delivers the data to the recipient sufficiently slowly  that  it
+
+can  process  the  data fast enough to keep the buffer from overflowing.
+
+If the receiver is faster than the sender, one could, with luck,  permit
+
+an infinitely optimistic window, in which the sender is simply permitted
+
+to send full-speed.  If the sender is faster than the receiver, however,
+
+and the window is too optimistic, then some segments will cause a buffer
+
+overflow,  and  will  be  discarded.  Therefore, the correct strategy to
+
+implement an optimistic window is to  increase  the  window  size  until
+
+segments  start to be lost.  This only works if it is possible to detect
+
+that the segment has been lost.  In  some  cases,  it  is  easy  to  do,
+
+because  the  segment  is  partially processed inside the receiving host
+
+before it is thrown away.  In other cases, overflows may actually  cause
+
+the network interface to be clogged, which will cause the segments to be
+
+lost  elsewhere  in the net.  It is inadvisable to attempt an optimistic
+
+window strategy unless one is certain that the algorithm can detect  the
+
+resulting  lost  segments.  However, the increase in throughput which is
+
+possible from optimistic windows is quite substantial.  Any systems with
+
+small buffer space should seriously consider  the  merit  of  optimistic
+
+windows.
+
+
+     The  selection  of an appropriate window algorithm is actually more
+
+complicated than even the above  discussion  suggests.    The  following
+
+considerations  are  not  presented  with  the  intention  that  they be
+
+                                   16
+
+
+incorporated  in  current  implementations of TCP, but as background for
+
+the sophisticated designer who is attempting to understand how  his  TCP
+
+will  respond  to  a variety of networks, with different speed and delay
+
+characteristics.  The particular pattern of windows and acknowledgements
+
+sent from receiver to sender influences two characteristics of the  data
+
+being  sent.    First, they control the average data rate.  Clearly, the
+
+average rate of the  sender  cannot  exceed  the  average  rate  of  the
+
+receiver,  or  long-term  buffer  overflow  will  occur.    Second, they
+
+influence the burstiness of the data coming from the sender.  Burstiness
+
+has both advantages and disadvantages.  The advantage of  burstiness  is
+
+that  it  reduces  the  CPU processing necessary to send the data.  This
+
+follows from the observed fact, especially on large machines, that  most
+
+of  the  cost  of sending a segment is not the TCP or IP processing, but
+
+the scheduling overhead of getting started.
+
+
+     On the other hand, the disadvantage of burstiness is  that  it  may
+
+cause  buffers  to overflow, either in the eventual recipient, which was
+
+discussed above, or in an intermediate gateway,  a  problem  ignored  in
+
+this paper.  The algorithms described above attempts to strike a balance
+
+between  excessive  burstiness,  which  in  the  extreme cases can cause
+
+delays because a burst is  not  requested  soon  enough,  and  excessive
+
+fragmentation   of  the  data  stream  into  small  segments,  which  we
+
+identified as Silly Window Syndrome.
+
+
+     Under conditions of extreme delay  in  the  network,  none  of  the
+
+algorithms   described   above   will   achieve   adequate   throughput.
+
+Conservative window algorithms  have  a  predictable  throughput  limit,
+
+                                   17
+
+
+which  is one windowfull per roundtrip delay.  Attempts to solve this by
+
+optimistic window strategies may  cause  buffer  overflows  due  to  the
+
+bursty  nature  of the arriving data.  A very sophisticated way to solve
+
+this is for the receiver, having measured by some  means  the  roundtrip
+
+delay  and  intersegment  arrival rate of the actual connection, to open
+
+his window, not in one optimistic increment of gigantic proportion,  but
+
+in  a number of smaller optimistic increments, which have been carefully
+
+spaced using a timer so that the resulting smaller bursts  which  arrive
+
+are each sufficiently small to fit into the existing buffers.  One could
+
+visualize this as a number of requests flowing backwards through the net
+
+which trigger in return a number of bursts which flow back spaced evenly
+
+from  the  sender  to  the  receiver.    The  overall result is that the
+
+receiver uses the window mechanism to  control  the  burstiness  of  the
+
+arrivals, and the average rate.
+
+
+     To  my knowledge, no such strategy has been implemented in any TCP.
+
+First, we do not normally have delays high enough to require  this  kind
+
+of  treatment.    Second,  the  strategy described above is probably not
+
+stable unless it is very carefully balanced.  Just as buses on a  single
+
+bus  route tend to bunch up, bursts which start out equally spaced could
+
+well end up piling into each other, and forming the single  large  burst
+
+which  the  receiver was hoping to avoid.  It is important to understand
+
+this extreme case, however, in order to  understand  the  limits  beyond
+
+which  TCP,  as normally implemented, with either conservative or simple
+
+optimistic windows can be expected to  deliver  throughput  which  is  a
+
+reasonable percentage of the actual network capacity.
+
+                                   18
+
+
+     7.  Conclusions
+
+
+     This  paper  describes  three  simple  algorithms  for  performance
+
+enhancement in TCP, one at the sender end and two at the receiver.   The
+
+sender  algorithm  is  to  refrain from sending if the useable window is
+
+smaller than 25 percent of the offered window.  The receiver  algorithms
+
+are first, to artificially reduce the offered window when processing new
+
+data  if  the  resulting  reduction  does  not  represent more than some
+
+fraction, say 50 percent, of the actual space available, and second,  to
+
+refrain  from  sending an acknowledgment at all if two simple conditions
+
+hold.
+
+
+     Either of these algorithms will prevent the worst aspects of  Silly
+
+Window  Syndrome, and when these algorithms are used together, they will
+
+produce substantial improvement in CPU utilization, by  eliminating  the
+
+process of excess acknowledgements.
+
+
+     Preliminary  experiments  with  these  algorithms suggest that they
+
+work, and work very well.  Both the sender and receiver algorithms  have
+
+been  shown  to  eliminate  SWS,  even  when  talking  to  fairly  silly
+
+algorithms at the other end.  The Multics  mailer,  in  particular,  had
+
+suffered substantial attacks of SWS while sending large mail to a number
+
+of  hosts.   We believe that implementation of the sender side algorithm
+
+has  eliminated  every  known  case  of  SWS  detected  in  our  mailer.
+
+Implementation  of  the  receiver  side  algorithm  produced substantial
+
+improvements of CPU time when Multics was the sending system.    Multics
+
+is  a  typical  large  operating system, with scheduling costs which are
+
+large compared to the actual  processing  time  for  protocol  handlers.
+
+                                   19
+
+
+Tests were done sending from Multics to a host which implemented the SWS
+
+suppression  algorithm,  and  which  could  either  refrain  or not from
+
+sending acknowledgements on each segment.  As predicted, suppressing the
+
+return acknowledgements did not influence the throughput for large  data
+
+transfer  at  all,  since the throttling effect was elsewhere.  However,
+
+the CPU time required to process the data at the Multics end was cut  by
+
+a  factor  of  four  (In  this experiment, the bursts of data which were
+
+being sent were approximately eight  segments.    Thus,  the  number  of
+
+acknowledgements in the two experiments differed by a factor of eight.)
+
+
+     An  important  consideration in evaluating these algorithms is that
+
+they must not cause the protocol implementations to deadlock.    All  of
+
+the  recommendations  in this document have the characteristic that they
+
+suggest one refrain  from  doing  something  even  though  the  protocol
+
+specification  permits one to do it.  The possibility exists that if one
+
+refrains from doing something now one may never get to do it later,  and
+
+both  ends will halt, even though it would appear superficially that the
+
+transaction can continue.
+
+
+     Formally, the idea that things continue to work is referred  to  as
+
+"liveness".    One  of  the  defects  of ad hoc solutions to performance
+
+problems is the possibility that two different approaches will  interact
+
+to  prevent  liveness.   It is believed that the algorithms described in
+
+this paper are always live, and that is one of the reasons why there  is
+
+a strong advantage in uniform use of this particular proposal, except in
+
+cases where it is explicitly demonstrated not to work.
+
+
+     The  argument  for liveness in these solutions proceeds as follows.
+
+                                   20
+
+
+First,  the sender algorithm can only be stopped by one thing, a refusal
+
+of the receiver to acknowledge sent data.    As  long  as  the  receiver
+
+continues  to  acknowledge  data, the ratio of useable window to offered
+
+window will approach one, and eventually the  sender  must  continue  to
+
+send.    However,  notice  that the receiver algorithm we have advocated
+
+involves refraining from acknowledging.  Therefore, we certainly do have
+
+a situation where improper  operation  of  this  algorithm  can  prevent
+
+liveness.
+
+
+     What  we  must show is that the receiver of the data, if it chooses
+
+to refrain from acknowledging, will do so only for a short time, and not
+
+forever.  The design of the algorithm described above  was  intended  to
+
+achieve  precisely  this  goal:  whenever the receiver of data refrained
+
+from sending an acknowledgement it was required to set  a  timer.    The
+
+only  event  that  was  permitted to clear that timer was the receipt of
+
+another segment, which essentially reset the timer, and started it going
+
+again.  Thus, an acknowledgement will be sent as soon  as  no  data  has
+
+been received.  This has precisely the effect desired:  if the data flow
+
+appears to be disrupted for any reason, the receiver responds by sending
+
+an  up-to-date  acknowledgement.    In  fact,  the receiver algorithm is
+
+designed  to  be  more  robust  than  this,  for  transmission   of   an
+
+acknowledgment is triggered by two events, either a cessation of data or
+
+a  reduction in the amount of offered window to 50 percent of the actual
+
+value.    This  is  the  condition  which  will  normally  trigger   the
+
+transmission of this acknowledgement.
+
+                                   21
+
+
+
+
+
+                               APPENDIX A
+
+
+     Dynamic Calculation of Acknowledgement Delay
+
+
+     The  text  suggested  that  when  setting  a  timer to postpone the
+
+sending  of  an  acknowledgement,  a  fixed  interval  of  200  to   300
+
+milliseconds  would  work  properly  in  practice.    This  has not been
+
+verified over a wide variety of network delays, and clearly if there  is
+
+a  very  slow  net  which stretches out the intersegment arrival time, a
+
+fixed interval will fail.  In a sophisticated TCP, which is expected  to
+
+adjust   dynamically   (rather   than   manually)  to  changing  network
+
+conditions, it would be appropriate to measure this interval and respond
+
+dynamically.  The following algorithm, which has been  relegated  to  an
+
+Appendix,  because  it  has not been tested, seems sensible.  Whenever a
+
+segment arrives which does not have the push  bit  on  in  it,  start  a
+
+timer,  which  runs  until  the  next  segment  arrives.   Average these
+
+interarrival intervals, using an exponential  decay  smoothing  function
+
+tuned  to take into account perhaps the last ten or twenty segments that
+
+have come in.  Occasionally, there will be a long  interarrival  period,
+
+even  for  a  segment  which is does not terminate a piece of data being
+
+pushed, perhaps because a window has gone to zero or some glitch in  the
+
+sender  or  the  network  has held up the data.  Therefore, examine each
+
+interarrival interval, and discard it from the smoothing algorithm if it
+
+exceeds the current estimate by some amount, perhaps a ratio of  two  or
+
+four times.  By rejecting the larger intersegment arrival intervals, one
+
+should obtain a smoothed estimate of the interarrival of segments inside
+
+                                   22
+
+
+a  burst.   The number need not be exact, since the timer which triggers
+
+acknowledgement can add a fairly generous fudge factor to  this  without
+
+causing  trouble  with  the  sender's  estimate  of  the  retransmission
+
+interval, so long as the fudge factor is constant.
+
+