Window and Acknowledgement Strategy in TCP
RFC 813

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions

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