rfc813.txt

RFC 相关的技术文档

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