Subject: New text for Link Layer designers draft...

From: Jamshid Mahdavi <[email-masked]>
Date: 28 Jul 1999 13:09:26 -0700

Here is the text as I have updated it for the link layer designer's
draft.  I believe that I have incorporated most of the comments people
suggested.

Again, comments/complaints welcome.  I still feel that it could use
some wordsmithing, but I think we can do that once we move it into
place in the draft.

--Jamshid

4. Effects of Packet Corruption (Loss) on TCP/IP Performance

4.1  How TCP Works

One of the functions of the TCP transport protocol is to provide
end-host based congestion control for the Internet.  This is a
critical part of the overall stability of the Internet, and the
workings of TCP's congestion control algorithms are important for link
layer designers to understand.

TCP assumes that, at the most abstract level, the network consists of
links and queues.  Queues provide output-buffering on links which are
momentarily oversubscribed.  

In the event that the demand on a link exceeds its capacity for long
enough to fill the queue, arriving packets in excess of the queue
capacity will be dropped.  (Note:  this is with drop tail queues,
which are no longer the recommended queuing style for the Internet).

These drops are the primary signal which TCP uses to detect congestion
in the Internet.  (This is a very good signal to use for congestion,
because it happens automatically.  It doesn't require any special
behavior from hardware, and doesn't require any understanding of IP or
IP headers.)

TCP detects losses through the use of a cumulative acknowledgement.
The TCP receiver sends a cumulative acknowledgement which covers all
segments received so far.  If a segment is lost, the cumulative
acknowledgement will cease to advance.  The receiver sends "Duplicate
Acknowledgments" or "Dupacks" for packets which arrive out of
sequence.  TCP can use these duplicate acks to detect a loss.  The
algorithm waits until a certain number (currently 3) are seen prior to
assuming a loss has occured; this helps to prevent mistaking packet
reordering for packet loss.  In some cases, losses may also be
detected through a "Retransmission Timeout".  This occurs if zero, or
too few, ACKs arrive to signal a loss through the dupacks mechanism.
Retransmission timeouts impose a more severe performance penalty,
since the sender will be idle during the timeout interval, and must
restart from a window of 1 following the timeout.

A new technique called "Explicit Congestion Notification" (ECN) allows
routers to directly signal congestion to hosts without dropping
packets.  This is done by setting a bit in the IP header.  Since this
is currently an optional behavior (and, longer term, there will always
be the possibility of congestion in portions of the network which
don't support ECN), the lack of an ECN bit MUST NEVER be interpreted
as a lack of congestion.  Thus, for the foreseeable future, TCP MUST
interpret a lost packet as a signal of congestion.

The TCP "congestion avoidance" [RFC2481] algorithm is the end-system
congestion control algorithm used by TCP.  This algorithm maintains a
congestion window (cwnd), which controls the amount of data which TCP may
send at any given point in time.  Reducing cwnd reduces the overall
bandwidth obtained by the connection; similarly, raising cwnd
increases the performance.

TCP probes for network bandwidth by slowly increasing cwnd.  When a
packet loss is detected (or congestion is signalled by other
mechanisms), cwnd is divided by two.  This algorithm is referred to as
an "Additive Increase, Multicative Decrease" (AIMD) algorithm.  The
steep decrease in response to congestion provides for network
stability; the AIMD algorithm also provides for fairness between long
running TCP connections sharing the same path.

The AIMD algorithm, by itself, can take a long time to increase cwnd
to large values.  For network paths where a large cwnd is required,
TCP also uses another algorithm called "Slow Start" in order to
quickly reach larger values of cwnd at the start of a connection and
after idle periods or retransmission timeouts.

4.2  TCP Performance Characteristics

4.2.1  Caveat

In this section, we present the current "state-of-the-art"
understanding of TCP performance.  This analysis attempts to
characterize the performance of TCP connections over links of varying
characteristics.

Link designers may wish to use the techniques in this section to
predict what performance TCP/IP may achieve over a new link layer
design.  Such analysis is encouraged.  Because this is relatively new
analysis, and the theory is based on single stream TCP connections
under "ideal" conditions, it should be recognized that the results of
such analysis may be different than actual performance in the
Internet.  That being said, we have done the best we can to provide
information which will help designers get an accurate picture of the
capabilities and limitations of TCP under various conditions.

4.2.2  The Formulae

The performance of TCP's AIMD Congestion Avoidance algorithm has been
extensively analyzed.  The current best formula for the performance of
the specific algorithms used by Reno TCP is given by Padhye, et.al.[1]
This formula is:

                                 MSS
    BW = --------------------------------------------------------
         RTT*sqrt(1.33*p) + RTO*p*[1+32*p^2]*min[1,3*sqrt(.75*p)]

In this formula, the variables are as follows:
    MSS  is the segment size being used by the connection
    RTT  is the end-to-end round trip time of the TCP connection
    RTO  is the packet timeout (based on RTT)
    p    is the packet loss rate for the path 
         (i.e. .01 if there is 1% packet loss)

This is currently considered to be the best approximate formula for
TCP performance.  A further simplification to this formula is
generally made by assuming that RTO is approximately 5*RTT.

TCP is constantly being improved.  A simpler formula, which gives an
upper bound on the performance of any AIMD algorithm which is likely
to be implemented in TCP in the future, was derived by Ott, et.al. [2][3]

              MSS   1
    BW = 0.93 --- -------
	      RTT sqrt(p)              

4.2.3  Assumptions of these formulae

Both of these formulae allow for BW to become infinite if there is no
loss.  This is because an Internet path will drop packets at
bottleneck queues if the load is too high.  Thus, a completely
lossless TCP/IP network can never occur (unless the network is not
being used).

The RTT used is the average RTT including queuing delays.

The formulae are calculations for a single TCP connection.  If a path
carries many TCP connections, each will follow the formulae above
independently.

The formulae assume long running TCP connections.  For connections
which are extremely short (<10 packets) and don't lose any packets,
performance is driven by the TCP slow start algorithm.  For
connections of medium length, where on average only a few segments are
lost, single connection performance will actually be slightly better
than given by the formulae above.

The difference between the simple and complex formulae above is that
the complex formula includes the effects of TCP retransmission
timeouts.  For very low levels of packet loss (significantly less than
1%), timeouts are unlikely to occur, and the formulae lead to very
similar results.  At higher packet losses (1% and above), the complex
formula gives a more accurate estimate of performance (which will
always be significantly lower than the result from the simple
formula).

Note that these formulae break down as p approaches 100%.

4.3  Analysis of Link Layer Effects on TCP Performance

Link layer designers who are interested in understanding the
performance of TCP over these links can use these formulae to figure
this out.  Consider the following example:

   A designer invents a new wireless link layer which, on average,
   loses 1% of IP packets.  The link layer supports packets of up to
   1040 bytes, and has a one-way delay of 20 msec.

   If this link layer were used in the Internet, on a path which
   otherwise had a roundtrip of of 80 msec, you could compute an upper
   bound on the performance as follows:

   For MSS, use 1000 bytes (remove the 40 bytes for TCP/IP headers,
   which do not contribute to performance).

   For RTT, use 120 msec (80 msec for the Internet part, plus 20 msec
   each way for the new wireless link).

   For p, use .01.  For C, assume 1.  

   The simple formula gives:

   BW = (1000 * 8 bits) / (.120 sec * sqrt(.01)) = 666 kbit/sec

   The more complex formula gives:

   BW = 402.9 kbit/sec

   If this were a 2 Mb/s wireless LAN, the designers might be somewhat
   dissapointed.

Some observations on performance:

1.  We have assumed that the packet losses on the link layer are
    interpreted as congestion by TCP.  This is a "fact of life" which
    must be accepted.

2.  Note that the equations for TCP performance are all expressed in
    terms of packet loss.  Many link-layer designers think in terms of
    bit-error rate.  If there is a uniform random distribution of
    errors, then the probability of a packet being corrupted is:

       p = 1 - ([1 - BER]^[MSS * 8])

    (Here we assume MSS is represented in bytes).  If the inequality

       BER * MSS * 8 << 1

    holds, p can be approximated by:

       p = BER * MSS * 8

    These equations can be used to apply BER to the performance
    equations above. 

    Note that links with Forward Error Correction (FEC) generally have
    very non-uniform bit error distributions.  The distribution is a
    strong function of the types and combinations of FEC algorithms
    used.  In such cases these equations cannnot be used to apply BER
    to the performance equations above.  If the distribution of error
    distributions under the FEC scheme is known, one could apply the
    same type of analysis as above, using the correct distribution
    function for the BER.  It is more likely in these FEC cases,
    however, that empirical methods will need to be used to determine
    the actual packet loss rate.

3.  Note that the packet size plays an important role.  Larger packet
    sizes will allow for improved performance at the same *packet
    loss* rate.  Assuming constant, uniform bit-errors (insead of
    packet errors), and assuming that the BER is small enough for the
    approximation [p=BER*MSS*8] to apply, a simple derivation will
    show that larger packet sizes still result in increased TCP
    performance.  For this reason (and others) it is advisable to
    support larger packet sizes where possible.

    To derive this, simply plug in p = BER*MSS*8 into the simple
    formula for performance.  The result is p = O(sqrt(MSS)),
    providing larger performance for larger packet sizes.

    If the approximation p = BER*MSS*8 breaks down, and in particular
    if the BER is high enough that BER*MSS approaches (or exceeds) 1,
    the packet loss rate p will tend to 100%, resulting in zero
    throughput.

4.  We have chosen a specific RTT which might occur on a wide-area
    Internet path within the USA.  In the Internet, it is important to
    recognize that RTT varies considerably.  

    In a wired LAN environment, RTT are less than 10 msec.
    International connections may have RTTs of 200 msec or more.
    Modems and other slow links also have high RTTs due to packet
    transmission times.

    Links running over geostationary repeater satellites have one-way
    times of around 250ms (125ms up to the satellite, 125ms down) so
    the RTT of an end-to-end TCP connection that includes such a link
    can be expected to be greater than 250ms.

    Heavily congested links may have queues which back up, increasing
    RTTs.  Finally, VPNs and other forms of encrypted tunnels can add
    significant end-to-end delay to network connections.

    Increased delay decreases the overall performance of TCP at a
    given loss rate.  A good rule of thumb is to recognize that you
    can't do anything about the laws of physics, so you can't change
    the propagation delay.  Many link layer designers are likely to
    face the following tradeoff: using additional delay to reduce the
    probability of packet loss (through FEC, ARQ, or other methods).
    Increasing the delay somewhat in order to decrease packet loss is
    probably a worthwhile investment, either up to doubling, or in the
    case of very low delay pipes, adding 10-20 msec won't have much
    effect on a typical Internet path.

---

From: Lloyd Wood <[email-masked]>
Date: Thu, 29 Jul 1999 11:29:48 +0100 (BST)

comments inline, below.

> some wordsmithing, but I think we can do that once we move it into

once it's in place, wordsmithing is less likely to happen as there's
less focus on this part.

I'm assuming a large explanation of what RTT is up front in the
document.

> behavior from hardware, and doesn't require any understanding of IP or

Once again, the drop itself is not the signal; this contradicts the
following paragraph. You need to explain the causal relationship
between drops and losses; the paragraph above needs to relate to the
paragraph below.

> restart from a window of 1 following the timeout.

Should really explain variations on the theme such as SACK here -
these variations are more likely to see deployment than ECN is, so the
ECN focus is a little odd. ECN's experimental; I'd lose the next
paragraph.

> the specific algorithms used by Reno TCP is given by Padhye, et.al.[1]

Your references have vanished.

> This is currently considered to be the best approximate formula for

Reno

> TCP performance.  

SACK would alter the p function, yes?

> A further simplification to this formula is

You really mean being under-utilised.

Consider real life, where the TCP window maxes out (not that it ever
really does, thanks to memory churn.) The formulae aren't limited by
window size. You can have a high-capacity network carrying some
maxed-out windows TCP traffic. You won't see loss, because the
windows can't grow further to fill even the bottleneck.

A completely lossless TCP/IP internet is very unlikely to occur,
though...

> The RTT used is the average RTT including queuing delays.

sounds more like RTO...

>     In a wired LAN environment, RTT are less than 10 msec.

when communications are between hosts on the same LAN. Good rule -
give an RTT timew, specify where the endpoints are, to ensure
endpoints-RTT association.

>     International connections 

between hosts in different countries.

>     may have RTTs of 200 msec or more.

thanks to serialization.
 
>     significant end-to-end delay to network connections.

separate encryption and tunnelling. Different effects.

>     effect on a typical Internet path.

TCP RTO granularity comments here, I think; the paragraph above leads
into them nicely.

cheers,

L.

<[email-masked]>PGP<http://www.ee.surrey.ac.uk/Personal/L.Wood/>