Subject: Link Layer designers draft...

From: Jamshid Mahdavi <[email-masked]>
Date: 23 Jul 1999 07:28:20 -0700

All,

I drafted the following (large) section of text for the PILC Link
Layer designers draft which Phil is assembling.  I wanted to send it
by the list for comments, since it is long on its own and may spark
some interesting discussions/controversy.  Note that the section
numbering is random, and doesn't reflect where this fits in the master
document.

--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 can't be screwed up).  Newer techniques such as ECN expand
on the means by which TCP can detect congestion, but it will remain
true for the foreseeable future that 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.

4.2  TCP Performance Characteristics

The performance of this 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.1  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).

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. 

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), 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.  

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 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.  Satellite links have one-way
    times of about 500 msec (250 msec up and down).  Heavily congested
    links may have queues which back up, increasing RTTs.  Finally,
    VPNs and other forms of encrypted tunnels add significant 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 some delays are
    going to be required.  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.

[1]  Padhye, J., Firoiu, V., Towsley, D., and Kurose, J., Modeling TCP
     Throughput: a Simple Model and its Empirical Validation, UMASS
     CMPSCI Tech Report TR98-008, Feb. 1998.

[2]  M. Mathis, J. Semke, J. Mahdavi, T. Ott, "The Macroscopic Behavior
     of the TCP Congestion Avoidance Algorithm",Computer Communication
     Review, volume 27, number 3, July 1997.

[3]  T. Ott, J.H.B. Kemperman, M. Mathis, The Stationary Behavior of
     Ideal TCP Congestion Avoidance.  
     ftp://ftp.bellcore.com/pub/tjo/TCPwindow.ps

---

From: PAN Jianping <[email-masked]>
Date: Fri, 23 Jul 1999 12:46:54 -0400

>mechanisms), cwnd is divided by two.  This algorithm is referred to as

just few details.

actually modern tcp implementation has (at least) two variables to 
perform its congestion control algorithms, one is cwnd (congestion 
window as you mentioned) another is ssthresh (slow-start threshold). 
when cwnd less than ssthresh, cwnd almost increases exponentially
per rtt (so not _slowly_); and when cwnd larger than ssthresh, cwnd 
increase linearly per rtt. on different singals of (congestion) loss, 

  - sender timeout. ssthresh = max(flight-size, 2*mss), usually use
    current cwnd as the flight-size; cwnd = initial-window, usually
    1 mss

  - after 3 duplicated acknowledgments. ssthresh = max (flight-size,
    2*mss); cwnd = initial-window (in tcp-rahoe) or ssthresh (tcp-reno)
    or ssthresh+3mss (tcp-reno with inflat cwnd during fast-recovery 
    period, and re-assigned to ssthresh when exit fast-recovery)

  - (new proposed ecn, almost same as fast-recovery)

when running with slight packet loss rate, timeout is rare, and usually
single (or a small amount of multiple) packet loss recovered by fast
recovery. that's the reason for the simple formula.

>running TCP connections sharing the same path.

----------------------------------------------------------------------------
  PAN Jianping                                      [email-masked]
============================================================================

---

From: Lloyd Wood <[email-masked]>
Date: Fri, 23 Jul 1999 18:52:14 +0100 (BST)

On Fri, 23 Jul 1999, Lloyd Wood wrote:

> Define up and down. I'd go for something like:
> 
>  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 500ms.

greater than 250ms, dammit.

L.

keeps forgetting about asymmetry.

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

---

From: Lloyd Wood <[email-masked]>
Date: Fri, 23 Jul 1999 18:46:06 +0100 (BST)

On 23 Jul 1999, Jamshid Mahdavi wrote:

> Layer designers draft which Phil is assembling. 

great; it's always easier to come up with material when you're staring
at something other than a blank piece of paper - comments on various
chunks below.

> in the Internet. 

The drops themselves aren't the signal directly. It's the subsequent
absence of arrival and timeouts; an indirect consequence of the
link/router congestion management method. It's almost as if you're
explaining ECN here; at least, that's my impression.

> generally made by assuming that RTO is approximately 5*RTT.

Great. Throw these equations at link designers, and they're going to
say things like 'my link has this RTT, therefore...'. Entirely the
wrong approach; IMO you should be stressing how the link doesn't know
the RTT of stuff going across it, or whether it's the bottleneck or
not, and giving an idea of the vast unknowns they can't control up
front, before leading to the upper performance bound. I do think the
eqns need disclaiming heavily - reality is fuzzier - and I'd labour
the point about what TCP RTT is - communication between two end points
across multiple links/networks - and isn't.

>     sizes still result in increased TCP performance.

If the derivation's simple, it's worth presenting. 'larger packet 
sizes still result in increased TCP performance' is an
overgeneralisation; consider jumbograms on severely errored links.
Nothing would get through. Hmmm, fit that into the derivation...

>     For this reason

Okay, we're now in discussion of IP MTU, rather than TCP. Hints on
deciding sensible MTU sizes and mapping packets to MAC frames needed,
I think.

>     are less than 10 msec. 

Temporary shadowing on a wireless LAN link can really mess up this
kind of claim. (Reiner?)

>     International connections may have RTTs of
>     due to packet transmission times.

Hmmm, suddenly RTT's a strawman. If you'd begun by talking about thin
and fat pipes a la RFC1323 this bit would make more sense. This
also implies you're talking about a link RTT, rather than a large
contribution to large overall RTTs...

>     Satellite links have one-way
>     times of about 500 msec (250 msec up and down).  

>     Heavily congested

Any delay isn't added to the network connection as such; it's just
endnode processing. Might as well complain that disk seek times slow
down FTP transfers - and surely the delay's really only in
establishing encrypted connections? Tunnelling and effects is a whole
other issue.

Discussion of link-layer compression strategies and encryption
interactions would be appropriate here.

>     going to be required.  

...and they're called propagation delays. Everything else is subject
to negotiation with advancements in existing technology.

>     Increasing the delay somewhat in order to

This gets into FEC/ACK considerations, and needs to be qualified with
great care in what you can get away with in terms of TCP RTO
granularity IMO.

cheers,

L.

---

From: Jamshid Mahdavi <[email-masked]>
Date: 23 Jul 1999 14:26:41 -0700

First, thanks everyone for the comments; I believe I
have incorporated all of them in one form or another back into the
text.  I'll send out a new copy after things stop rolling in.

I did the quick calculation to compare a single 1 MB long running
connection to a series of 100 10kB short connections, as I described
in my previous reply to Ralph.  The results were (in my mind)
inconclusive, so I'm still trying to figure out what to make of the
statement "Short sessions with low BW on long-delay links are more
sensitive to packet loss rate than are long sessions."  Ralph and I
will probably discuss this some offline.

> explaining ECN here; at least, that's my impression.

Well, I admit I do think of the world in an ECN-like way :-).  In the
end, a loss and an ECN are treated in the same way.  I've added words
to the effect that what is actually detected by the end system is a
series of dupacks or a timeout.

> across multiple links/networks - and isn't.

This is a very good point.

> Nothing would get through. Hmmm, fit that into the derivation...

My mistake -- I went and used the "simple formula" which only applies
when BER is small.  The calculation breaks down when BER*MSS*8
approaches 1.

> deciding sensible MTU sizes and mapping packets to MAC frames needed,

This section should reference other parts of the document where these
issues are discussed in more detail...

...

The rest of the comments are incorporated :-)

--J