rfc813.txt

RFC 相关的技术文档

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.