| RFC : | rfc813 |
| Title: | |
| Date: | July 1982 |
| Status: | UNKNOWN |
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.