Subject: NACK proposal
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Date: Fri, 22 Jan 1993 11:21:44 MST

I presented my NACK proposal to the end-to-end interest group 
yesterday and the results were encouraging enough (at least 
from my point of view) for me to continue the process. I plan 
to implement several variations on the NACK scheme and 
produce a paper by the SIGCOMM paper deadline (Feb 28th). 
Since the NACK option (and for that matter the a SACK option) 
opens the door for a variety of additional TCP modifications I 
would like to get some feed back on potential changes.

1) NACKS: 
	1- Single NACK (lost NACK causes slow start)
	2- Multiple NACK's (tolerates up to N dropped NACKs)
	3- Repeated NACK's (sends NACK's with every duplicate 
ACK)

2) Congestion window:
	1- implement full dual window model[Z. Wang and J. 
Crowcroft] 
	2- move congestion window calculation to receiver 

3) Timer
	1- eliminate TIMESTAMP option 
	2- move retransmission timer to receiver (al la NETBLT)

I plan to mix and match these modifications to see what effect 
they have on overall performance. If anyone has any other 
suggestions (or good algorithms for what I have proposed) 
please let me know. My goal is to have a BSD implementation and an RFC by March. 

Sean O'Malley

Date: Thu, 21 Jan 1993 08:43:12 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: any trafic yesterday

I somehow managed to destroy my mail box and have lost 
all of yesterdays (Jan 20-ths) mail. If there was any 
on this group could someone send me duplicates?

Sean

From: [email-masked] (C. Douglas Brown)
Subject: Re: slow start and large windows
To: [email-masked]
Date: Wed, 20 Jan 93 13:41:13 MST

I have been following the discussion of Sean O'Malley's proposals with great 
interest and would like to express my concern with performance using TCP large
windows in an environment with congestion loss.  It appears likely that with 
high-bandwidth networks (45Mb/s and up), TCP large windows will increase the 
chances of congestion loss as more hosts dump data into the net at high rates.
I've already experienced some router problems when testing TCPLW code for SunOS
in a fairly clean environment.  Having worked with networks for quite a few 
years, I've observed that as the raw network bandwidth goes up, the traffic 
gets more and more bursty.  It's desirable to allow hosts to use a big percent-
age of the network bandwidth for short bursts, but you never know when several
hosts will do this at once, causing temporary congestion loss.  Hence, the need
to solve the congestion problem without dropping performance to a snail's pace.

Now some comments on Sean's conclusions:

> Conclusions:
> 
> It is congestion control rather that the cost of duplicate 
> retransmissions which will have the most effect upon the 
> achievable bandwidth in the face of dropped packets in 
> networks with large bandwidth delay products.
> 
Right.  When the networks get very fast, we shouldn't worry so much
about a few retransmissions, if we can keep overall performance up.

> Slow start has to be modified to be more aggressive in 
> increasing the congestion window when the window is large. 
> In particular the algorithm should be normalized so that the 
> time it takes to increase the congestion window back to its 
> original value is independent of its size. 

Or, after reading subsequent discussions, perhaps not closing the congestion 
window so severly in the first place.
> 
> Using slow start to avoid the unnecessary retransmissions 
> missions is overkill and some other method (SACK's, NACK's 
> or playing with timers) should be used to solve this problem. 

It appears that the real intent of most proposals is merely to speed 
retransmission of dropped segments; hence, a NACK is philosophically what 
we're looking at, no matter what we call it.  I personally like Sean's NACK
proposal, or some variant of it.  The other parameter of interest is the 
usable network bandwidth, which would allow the sender to avoid the oscillation
problem.  Perhaps the NACK could contain the necessary information to calculate 
effective bandwidth, as has been proposed.
> 
> While some congestion control is probably be required for 
> each dropped packet the existing reduction of the congestion 
> window to one segment and invoking slow start appears 
> draconian. Some other more benign algorithm would appear 
> to be called for.
> 
Sounds like the more recent Reno release solved the problem of a single
dropped packet.

Doug Brown ([email-masked])
Sandia National Labs
Albuquerque, NM

Date: Tue, 19 Jan 1993 10:20:26 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: slow start

O. Rose states:

> With respect to making TCP more aggressive: Take a look at
> what will happen to a router when opening the window according
> to the CURRENT TCP algorithm. You already get transient buffer-
> loads in the order of the pipesize(!) during the exponential
> opening phase (remember you are sending 2 packets in response
> to each ACK received, and these ACKs will arrive approximately
> at a rate that reflects the capabilities of the bottleneck).
> 
> I think this is already difficult to deal with in routers
> (imagine what will happen if you have to buffer several mega-
> bytes of data for each connection that is currently recovering
> using slow-start. Keep further in mind that connections tend
> to synchronize, i.e. many connections passing through a congested
> router will slow-start at about the same time. There suddenly
> is a need to buffer N megabytes! Even if we assume that such a
> lot of memory is available in modern routers (pretty expensive
> since memory has to be VERY fast to support let's say 100 Mbit/s),
> what about your poor retransmission-timers?
> 
> Now, what will happen if you make TCP even more aggressive?
> I think this is not the right direction we have to go in order
> to control congestion in high-speed networks.

Actually I was only concerned about the effect of large windows
on the linear second phase of the slow start algorithm where 
you are adding one segment to the window per round trip. As 
you point out large windows have the effect of making the 
expontial first part of the window opening MORE aggresive. 

It may be a good idea to make the expontial part of the slow 
start less aggressive while makeing the linear part of the 
algorithm more aggressive.

Sean 

Date: Tue, 19 Jan 1993 08:51:02 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked], [email-masked]
Subject: Re: correction
Cc: [email-masked], [email-masked]

Christian States 

> Any design should assume that NACKs can, and will, be lost or duplicated. I
> would feel more confortable if the list of nacked packets could be repeated in
> successive messages.

In general you are of course correct but in this case the NACKs exist 
merely to speed up retransmission. There are no correctness issues. 
So the argument is basically do you believe that you will lose enough 
NACKs to affect performance? In any case dealing with lost and duplicate 
NACKs is fairly trivial.

> I don't understand the purpose of sending "deltas" the way you describe. If
> what you want is do derive the effective bandwidth of the link, why not let
> the receiver build this estimate and send it? That would be a natural
> generalization of the "packet pair" algorithm.

All I am trying to do (so far with only fair success) is to minimally 
extend the reno mods to deal with more than one hole per window. The 
detla is an attempt to simulate what reno does with duplicate ACKs 
with NACKS. Moving the entire computation of the congetestion window
to the reciver requires that every TCP packet contain a congestion window 
going in the other direction. A more general solution to this problem 
requires the addition of congestion control parameter(s) to the timestamp 
option. Something which is possible but probably unlikely. 

Sean

To: "Sean O'Malley" <[email-masked]>
Cc: [email-masked], [email-masked]
Subject: Re: correction 
Date: Tue, 19 Jan 93 13:46:33 +0100
From: Christian Huitema <[email-masked]>

>Upon reflextion the sacked field of the NACK option should 
>contain the total number of new unacknoldged bytes in the 
>buffer since the last NACK. 

Sean,

Any design should assume that NACKs can, and will, be lost or duplicated. I
would feel more confortable if the list of nacked packets could be repeated in
successive messages.

I don't understand the purpose of sending "deltas" the way you describe. If
what you want is do derive the effective bandwidth of the link, why not let
the receiver build this estimate and send it? That would be a natural
generalization of the "packet pair" algorithm.

Christian Huitema

To: Sean O'Malley <[email-masked]>
Cc: [email-masked], [email-masked], [email-masked], [email-masked]
Subject: Re: slow start and large windows
Date: Tue, 19 Jan 93 11:05:05 +0000
From: Zheng Wang <[email-masked]>

 >The Effect of Large Windows on TCP Slow Start
 >
 >The existing version of BSD TCP (or at least the latest one I
 >could fine) responds to a dropped packet by reducing the
 >congestion window to one segment and using the TCP slow
 >start algorithm to attempt to increase the congestion window
 >back to its orginal value. The stated reason for using this
 >algorithm is to avoid the cost of duplicate transmissions of
 >the entire window in the face of a single dropped segment.
 >While it does effectively avoid these retransmission the
 >use of this algorithm on networks with very large bandwidth
 >delay products is problematical.

I think the TCP code you looked at is tahoe version (1988).
The reno version (1990) handles the problem much better.

 >Conclusions:

 >Slow start has to be modified to be more aggressive in
 >increasing the congestion window when the window is large.
 >In particular the algorithm should be normalized so that the
 >time it takes to increase the congestion window back to its
 >original value is independent of its size.

Making the slow start more aggressive will lead to greater
oscillation of the window size under normal conditions.

I think the right way to handle the problem is to prevent the
pipe from going empty. If the pipe is not empty after the loss,
you dont have to do slow start.

In tahoe tcp, a single window is used for end-to-end flow
control and for congestion control. The interaction has some
undirable effects.

In reno tcp, the window is used differently under normal
condition and after losses. In case of single packet loss,
reno can avoid pipe breakdown thus recover without slow-start.

In case of multiple losses, we have to seperate the flow
control and congestion control, and have more accurate
info about the lost packets. We have a paper on a dual-window
scheme, which can be ftp'ed from
bells.cs.ucl.ac.uk  128.16.5.31
darpa/window.ps
(a new version of the paper will be available
soon with simulation results). You comments are welcome.

Cheers
Zheng

To: [email-masked] (partho pratim mishra)
Cc: [email-masked], [email-masked], [email-masked]
Subject: Re: slow start and large windows 
Date: Tue, 19 Jan 93 08:56:27 +0100
From: Christian Huitema <[email-masked]>

You are absolutely correct. The current slow start parameters, and in
particular the "1 packet per RTT" of the linear phase, are obviously dependant
of the relation between throughput and delay. 

Having SACKs, however, enables more than just a scaled up version of the
low-star algorithm. If you assume that most losses are due to congestion, then
SACKs can let you estimate how many packets (or bytes) were effectively
received during the RTT. This gives you a direct estimation of the
effective bandwidth available! Tuning for smthg like "the available bandwidth
+ some margin" would look like a reasonable idea + would also avoid the "saw's
teeth" effect of the low star.

Christian Huitema

Date: Mon, 18 Jan 1993 16:55:55 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: correction

Upon reflextion the sacked field of the NACK option should 
contain the total number of new unacknoldged bytes in the 
buffer since the last NACK. 

the sender should compute 

	cnwnd = cnwnd + sacked
 	and use min(swnd, cnwnd) as effective window

Basically the reciver is telling the sender how many bytes it 
has removed from the pipe. (In this case underestimating it but
the reciver probably has enough information to compute it 
precisely)

Sean

Date: Mon, 18 Jan 1993 16:14:32 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: NACK option

My Proposed SACK Option Alternate:

Given Van's Reno mods and some minor modification to the 
slow start algorithm (al la Floyd and Van) the only known 
outstanding problem with tcplw is what to do about cases 
where more than one packet is dropped per window. The duplicate 
ACK detection in Reno is no help here because there is no 
timely way for the receiver to notify the sender of exactly 
which packets are missing and hence the sender cannot re-
transimit them, the pipe empties, and one is forced to reduce 
the congestion window to one segment and slow start. 

The original SACK option was proposed as a way to get around 
this problem. The basic problem with this option was that it 
required that the sender keep around a list of sent but unacked 
segments. As originally proposed the SACK option truncated 
the offsets of the SACK'ed segments to 16 bits. The only way that 
the sender can know what to retransmit is if it keeps information 
about the segments that it has sent. Since the BSD 
implementation and its derivatives do not keep such a list the 
SACK option as proposed would require significant changes to 
TCP. 

At the risk of re-inventing the wheel again (I have not seen an 
implementation of Van's proposed SACK option.) I will propose 
an alternate to the SACK option.

The NACK option:

A new NACK option would be defined which contained a 32 bit 
OFFSET field from the ACK field of the message it is contained 
in,  a 32 bit LENGTH field, and a 32 bit SACKED field which 
contains the total number of unacknowledged bytes in the 
receivers buffer. 

The receiver would keep track of the most recent hole in its 
receive buffer and if a threshold number of packets beyond this 
hole were received it would send out a NACK for that hole. The 
current hole pointer would then be moved to the next hole in 
the receive buffer (if any). The NACK would contain the offset 
and length of the hole and the total number of unacknowledged 
bytes in the buffer.

The sender upon receiving a NACK would:
	1. Cut the congestion window by 1/2 (al la Reno)
	2. Set  variable sacked equal to SACKED field in NACK option.
	3. Use min(snd_wnd, cwnd+sacked) as the effective window  size.
	4. Retransmit the offending segment (or segments).
	5. Set retransmission timer to at least 1 RTT.

The net effect of this change is that retransmission is now 
primarily the responsibility of the NACK option. Time-outs 
should only occur when NACKs or re-transmitted segments are 
lost. The actual algorithm is quite similar to Reno. 

The primary advantage of this approach is that it is simpler 
and a much smaller source delta of the existing TCP 
implementations. The sender keeps no additional information 
beyond the sacked variable. The receiver needs only to keep 
track of the oldest hole in its receiver buffer and the total 
number of unacknowledged bytes.

A secondary advantage is that only one NACK entry is needed. 
The original SACK option was based upon the assumption that 
at least 6 sacked ranges were required. As far as I can tell the 
need for multiple ranges is eliminated by sending the SACKED 
field. In particular if one resets the transmission timer there 
appears to be no need for the sender to keep track of exactly 
which segments are in the receivers buffer. If no re-transmitted 
segments or NACKs are lost no unnecessary re-retransmits 
will be performed. (Even if a retransmit is lost the Tahoe 
algorithm with prevent and serious duplicate retransmissions.)

If desired dropped NACK's can be handled by having the receiver 
send NACKs whenever it would previously send duplicate ACKs 
and/or by sending the n most recent holes in the NACK where n 
is some small threshold.

There is no way to really detect a dropped retransmit which 
would cause the original Tahoe TCP congestion control algorithm 
to be invoked. IE the  congestion window would be decreased to 
one segment and slow start would be invoked to fill the pipe. I 
don't think this is a problem because if you lost a segment and 
its retransmission you are probably experiencing sever 
congestion and want to take sever corrective action anyway. 
The sender resetting the retransmit timer will however result 
in an extra round trip delay in such case (which should be rare).

Note that give this option the need for an accurate RTT estimate 
is greatly reduced. As long as RTT is greater than the true 
round trip time TCP+NACK should work efficiently.  Fast re-
transmits are generated by NACKs not time-outs. Hence is the 
tcplw timestamp option really required?

Sean O'Malley

Date: Mon, 18 Jan 93 16:30:19 -0500
From: [email-masked] (partho pratim mishra)
To: [email-masked], [email-masked]
Subject: Re: slow start and large windows
Cc: [email-masked]

A typo in my last message:

> However, apparently Van did know about this change. 

should be

>>However, apparently Van did NOT know about this change.

To: "Sean O'Malley" <[email-masked]>
Cc: [email-masked], [email-masked], [email-masked], [email-masked], [email-masked]
Subject: Re: slow start and large windows 
Date: Mon, 18 Jan 93 16:24:55 -0500
From: Partho Mishra <[email-masked]>

> I still think that the linear slow start algorithm is wrong for 
> networks with large bandwidth delay products and is 
> too pessimistic. If you are really attempting to use slow start to 
> do rate control the total amount of time it takes to recover from 
> congestion should be the same regardless of the bandwidth delay product.
> Therefore slow start should be faster on higher bandwidth networks
> This would be easy to do by adjusting the constants in the existing 
> slow start. Ie How long to you keep increasing expontially vs. what 
> constant factor you use during the linear phase (currently it is 
> 1 it might be 5 or 10). 

This seems fairly obvious. Clearly it is a good idea to adjust the constants
of an algorithm depending on the operating environment (speed of links,
buffer sizes). Van Jacobson motivated the choice of the constants in the
original Sigcomm '88 paper using the then operational environment; it is not 
clear why these choices should be useful if and when the operating environment
changes.

Interesting we had a version of the Reno code, here at Maryland, which added
an exponential component (maxseg/8) to the linear increase rule. 

                 * When new data is acked, open the congestion window.
                 * If the window gives us less than ssthresh packets
                 * in flight, open exponentially (maxseg per packet).
                 * Otherwise open linearly: maxseg per window
                 * (maxseg^2 / cwnd per packet), plus a constant
                 * fraction of a packet (maxseg/8) to help larger windows
                 * open quickly enough.

This would cause a much faster increase at the cost of potentially 
more lost packets. However, apparently Van did know about this change. 
Thus at this point I am not sure what is standard for 4.3 BSD Reno versions.
-Partho Mishra

From: [email-masked] (Sally Floyd)
To: "Sean O'Malley" <[email-masked]>
Cc: [email-masked], [email-masked], [email-masked], [email-masked]
Subject: Re: slow start and large windows
Date: Mon, 18 Jan 93 13:21:15 PST

>I still think that the linear slow start algorithm is wrong for 
>networks with large bandwidth delay products and is 
>too pessimistic. If you are really attempting to use slow start to 
>do rate control the total amount of time it takes to recover from 
>congestion should be the same regardless of the bandwidth delay product.
>Therefore slow start should be faster on higher bandwidth networks
>This would be easy to do by adjusting the constants in the existing 
>slow start. Ie How long to you keep increasing expontially vs. what 
>constant factor you use during the linear phase (currently it is 
>1 it might be 5 or 10). 

Van and I have several articles that discuss changes to the slow start 
algorithm that would result in improving the time to recover from congestion 
for connections with larger bandwidth delay products.

See the section on Interactions with Window Adjustment Algorithms in 

Floyd, S., and Jacobson, V.,
Traffic Phase Effects in Packet-Switched Gateways,
Computer Communication Review, V.21 N.2, April 1991, pp. 26-42.

or in the journal version of the same article:

\bibitem[FJ92]{FJ92} Floyd, S., and Jacobson, V.,
On Traffic Phase Effects in Packet-Switched Gateways,
Internetworking: Research and Experience, V.3 N.3, September 1992, p.115-156.

For more analysis, see:

Floyd, S.,
Connections with Multiple Congested Gateways in Packet-Switched Networks
Part 1: One-way Traffic,
Computer Communication Review, V.21 N.5, October 1991, pp. 30-47.

The material in these articles was intended in the spirit of research,
not in the spirit of proposals for action.  We have another paper
in progress (but which unfortunately has been on hold for some time) 
that will discuss modified versions of this window increase algorithm.

- Sally

____

Date: Mon, 18 Jan 1993 13:02:23 -0800
From: [email-masked] (Bob Braden)
To: [email-masked], [email-masked], [email-masked]
Subject: Re: slow start and large windows
Cc: [email-masked], [email-masked]

> It should be a note in the RFC that you must implement van's modification 
> to support tcplw.
> 
> 

There's a more general problem, that this work exists only by example
in Tahoe (and is widely implemented), but it has never been documented
as far as I know.  The closest thing is a set of overheads that Van
used at an IETF meeting.  The words that go with the overheads was
partial gibberish, unfortunately.

I guess the E2E RG dropped the ball.
> 
> I still think that the linear slow start algorithm is wrong for 
> networks with large bandwidth delay products and is 
> too pessimistic. If you are really attempting to use slow start to 
> do rate control

Huh?

Bob

Date: Mon, 18 Jan 1993 13:41:12 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked], [email-masked], [email-masked]
Subject: Re: slow start and large windows
Cc: [email-masked], [email-masked]

Bob states:

> o Slow-start is essential in the current Internet, because many routers
>  are buffer-poor.
  
However if your bandwidth delay protocol is 7.5 megabytes you can probably 
safefly assume that you are not on the current internetwork.

>o Van solved precisely the problem you are worried about, some 4-5 years
> ago.  The "more benign" algorithm is embodied in the Fast-Retransmit/
> Congestion Avoidance code, which you will also find in BSD TCP.

Someone kindly got me a copy of that email and yes it does address 
the problem by getting rid of the need to go back to one segment.
It should be a note in the RFC that you must implement van's modification 
to support tcplw.

>o Making TCP more aggressive is NOT a good idea.  However, I think it
>  is possible to make a SACK scheme (I assume that is what is behind your
>  comments) that is consistent with congestion avoidance. We can talk
>  bout this later this week.

I still think that the linear slow start algorithm is wrong for 
networks with large bandwidth delay products and is 
too pessimistic. If you are really attempting to use slow start to 
do rate control the total amount of time it takes to recover from 
congestion should be the same regardless of the bandwidth delay product.
Therefore slow start should be faster on higher bandwidth networks
This would be easy to do by adjusting the constants in the existing 
slow start. Ie How long to you keep increasing expontially vs. what 
constant factor you use during the linear phase (currently it is 
1 it might be 5 or 10). 

To: [email-masked]
Reply-To: [email-masked] (Thomas Skibo)
From: [email-masked] (Thomas Skibo)
Subject: Re:  slow start and large windows
Date: Mon, 18 Jan 1993 19:49:16 GMT

> Suppose one has a 600 megabit/second coast-to-coast 
> connection. The bandwidth delay product (and hence the largest 
> possible window size) is 7.5 megabytes. If the MSS stays at 
> 512 bytes (which is not an unreasonable assumption) this 
> gives an N of about 14000 and implies that it will take 
> approximately 7000 RTT's to reach the original congestion 
> window. On a coast-to-coast connection with a 100 
> millisecond RTT this would take 700 seconds. If random 
> packet drops take place more often than this the TCP 
> congestion window will never reach the bandwidth delay 
> product.

I don't know about the 512 byte MSS.  I think if you're serious
about doing high-speed TCP, you need to use a bigger MSS (either
with MTU discovery or manually putting MTU specifications in route
entries so that the default MSS isn't chosen).

---
Thomas Skibo     Advanced Networking, Silicon Graphics     [email-masked]

Date: Mon, 18 Jan 1993 11:48:17 -0800
From: [email-masked] (Bob Braden)
To: [email-masked], [email-masked]
Subject: Re: slow start and large windows
Cc: [email-masked], [email-masked]

Sean,

I think the issue you raise would be most effectively discussed on the
end2end-interest list.  However, in brief:

o Slow-start is essential in the current Internet, because many routers
 are buffer-poor.

o Van solved precisely the problem you are worried about, some 4-5 years
 ago.  The "more benign" algorithm is embodied in the Fast-Retransmit/
 Congestion Avoidance code, which you will also find in BSD TCP.

o Making TCP more aggressive is NOT a good idea.  However, I think it
 is possible to make a SACK scheme (I assume that is what is behind your
 comments) that is consistent with congestion avoidance. We can talk
 bout this later this week.

Bob Braden

Date: Mon, 18 Jan 93 11:36:03 -0800
From: [email-masked] (Thomas Skibo)
To: "Sean O'Malley" <[email-masked]>
Subject: Re:  slow start and large windows
Cc: [email-masked]

> Suppose one has a 600 megabit/second coast-to-coast 
> connection. The bandwidth delay product (and hence the largest 
> possible window size) is 7.5 megabytes. If the MSS stays at 
> 512 bytes (which is not an unreasonable assumption) this 
> gives an N of about 14000 and implies that it will take 
> approximately 7000 RTT's to reach the original congestion 
> window. On a coast-to-coast connection with a 100 
> millisecond RTT this would take 700 seconds. If random 
> packet drops take place more often than this the TCP 
> congestion window will never reach the bandwidth delay 
> product.

I don't know about the 512 byte MSS.  I think if you're serious
about doing high-speed TCP, you need to use a bigger MSS (either
with MTU discovery or manually putting MTU specifications in route
entries so that the default MSS isn't chosen).

---
Thomas Skibo     Advanced Networking, Silicon Graphics     [email-masked]

To: [email-masked]
Cc: [email-masked], [email-masked], [email-masked], [email-masked]
Subject: Re: slow start and large windows 
Date: Mon, 18 Jan 93 14:16:03 -0500
From: Partho Mishra <[email-masked]>

Sean,
   In our Sigcomm 92 paper and in the companion technical
memorandum ("A Hop by hop rate based congestion control
scheme" - Mishra and Kanakia) we talked about the same
problem with TCP Tahoe. 

> The existing version of BSD TCP (or at least the latest one I 
> could find)

TCP Reno does things differently. Van's original mail to the
end to end mailing group provides the best description of
the changes from Tahoe to Reno.

>It is congestion control rather that the cost of duplicate 
>retransmissions which will have the most effect upon the 
>achievable bandwidth in the face of dropped packets in 
>networks with large bandwidth delay products.

   The degree of lost throughput caused by a TCP connection 
taking a long time to reach the original window  size after
a loss depends on the amount of available buffering and
whether random losses occur. If there are no random losses
and the amount of buffering is equal to about one
bandwidth x (round trip delay) product, then the amount
of throughput lost is not very high. This is because even
when the window size is W/2 (where the window size just
before the loss was W) the "pipe" may be almost full.  
However if there is lesser buffering available then there can
be a lot of loss in throughput, as you point out.

In the presence of random losses, TCP throughput can get shot
to pieces. We showed in a recent paper that even at 1-2% loss
rates the throughput of a TCP connection is affected badly.
The 1-2% loss figure is something we have discovered in
Internet experiments (we are still doing experiments to
establish how common the problem of random loss is).  
However, this problem has more  to do with the choice of 
loss as a congestion identification mechanism than the 
use of the window increase/decrease mechanisms of 
Slow Start / Cong Avoidance.

> It may be time to re-examine TCP congestion control from 
> scratch. See Zhang's virtual clock work or TP++.

If you check the congestion control literature I think you
will find several new mechanisms that have been proposed over
the last couple of years which should provide better 
performance compared to TCP albeit at the cost of
providing explicit feedback information. 

-Partho Mishra

Date: Mon, 18 Jan 1993 11:31:24 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: slow start and large windows
Cc: [email-masked], [email-masked]

The Effect of Large Windows on TCP Slow Start 

The existing version of BSD TCP (or at least the latest one I 
could fine) responds to a dropped packet by reducing the 
congestion window to one segment and using the TCP slow 
start algorithm to attempt to increase the congestion window 
back to its orginal value. The stated reason for using this 
algorithm is to avoid the cost of duplicate transmissions of 
the entire window in the face of a single dropped segment. 
While it does effectively avoid these retransmission the 
use of this algorithm on networks with very large bandwidth 
delay products is problematical. 

Note it is unclear to me if this use of slow start is required 
by the specification or a BSD'ism. 

TCP slow start works by increasing the congestion window 
exponentially with respect to round trip times until 1/2 of 
the original window is reached and at that point slow start 
increases the congestion window by one maximum segment 
size per round trip. Thus the time it takes to reach the 
original congestion window is:

	(log2(n/2) + n/2) * the round trip time(RTT) 	
	where n = window size/maximum segment size(MSS)

Where n is large this algorithm will take a great deal of 
time to achieve the original window after a dropped packet. 

Suppose one has a 600 megabit/second coast-to-coast 
connection. The bandwidth delay product (and hence the largest 
possible window size) is 7.5 megabytes. If the MSS stays at 
512 bytes (which is not an unreasonable assumption) this 
gives an N of about 14000 and implies that it will take 
approximately 7000 RTT's to reach the original congestion 
window. On a coast-to-coast connection with a 100 
millisecond RTT this would take 700 seconds. If random 
packet drops take place more often than this the TCP 
congestion window will never reach the bandwidth delay 
product.

Note even if one assumes a 45 Mbits T3 connection it would 
still take 50 seconds to reach the orginal congestion window 
after a dropped packet.

In high speed networks the invocation of the slow start 
algorithm for each dropped packet will significantly decrease 
the effective bandwidth of the connection for 1000's of 
RTT's after the packet drop. This effect swamps any potential 
benefit from avoiding the retransmission of packets already 
in the receivers buffer. 

Conclusions:

It is congestion control rather that the cost of duplicate 
retransmissions which will have the most effect upon the 
achievable bandwidth in the face of dropped packets in 
networks with large bandwidth delay products.

Slow start has to be modified to be more aggressive in 
increasing the congestion window when the window is large. 
In particular the algorithm should be normalized so that the 
time it takes to increase the congestion window back to its 
original value is independent of its size. 

Using slow start to avoid the unnecessary retransmissions 
missions is overkill and some other method (SACK's, NACK's 
or playing with timers) should be used to solve this problem. 

While some congestion control is probably be required for 
each dropped packet the existing reduction of the congestion 
window to one segment and invoking slow start appears 
draconian. Some other more benign algorithm would appear 
to be called for.

It may be time to re-examine TCP congestion control from 
scratch. See Zhang's virtual clock work or TP++.

Date: Thu, 7 Jan 1993 13:24:27 -0800
From: [email-masked] (Bob Braden)
To: [email-masked], [email-masked]
Subject: Re: TCP MSS & Timestamps

Stevo,

The MSS option is designed/intended to tell the remote TCP about the
properties of the host that sent the option, independent of the path.
It basically tells what is the largest transport-layer object that the
host can receive and reassemble.  For a BSD system, that limit is (?)
64K, so it would be correct for a BSD system to advertise an MSS of
65535.  Given this data, and its own knowledge about the network path
(and the presence of TCP and/or IP options), the host that receives the
MSS option can determine the largest datagram it can actually send.

On the other hand, A BSD host sends an MSS option that reflects its own
opinion about the route.  Thus, for a non-local destination, it sends
an MSS of 536 (or else it doesn't send it, assuming the default; I've
forgotten).  This means the remote host MAY NOT send a segment larger
than 536, even if the remote host KNOWS (e.g. from MTU Discovery, or
special knowledge) that it could send a larger segment.  Even if MTU
Discovery is installed, the approach will prevent its handling
assymmetric paths correctly.

Bob Braden

From: [email-masked] (Stevo Bevo-Devo Wise)
To: [email-masked]
Subject: Re: TCP MSS & Timestamps 
Date: Thu, 07 Jan 93 14:50:10 -0600

[email-masked] says:

| 
| Dave,
| 
| I basically agree with your analysis.  When I implemented the RFC-1323
| changes, I ran into this problem, so I went and looked at what I wrote
| in RFC-1122.  I spent a lot of effort on the discussion of MSS and
| segments sizes in RFC-1122, but rereading it, I find it is not as clear
| as I would like.  I guess the problem was that we had to water it down,
| because this was an area where BSD Unix violates the intent of the
| protocols.  I tried to suggest to people to do the right thing without

Could you elaborate on what BSD Unix is doing to violate the intent of
the protocols?  Is this in respect to how MSS is computed in BSD TCP?

Thanx,

Stevo.

Date: Thu, 7 Jan 1993 12:36:01 -0800
From: [email-masked] (Bob Braden)
To: [email-masked], [email-masked]
Subject: Re: TCP MSS & Timestamps

Dave,

I basically agree with your analysis.  When I implemented the RFC-1323
changes, I ran into this problem, so I went and looked at what I wrote
in RFC-1122.  I spent a lot of effort on the discussion of MSS and
segments sizes in RFC-1122, but rereading it, I find it is not as clear
as I would like.  I guess the problem was that we had to water it down,
because this was an area where BSD Unix violates the intent of the
protocols.  I tried to suggest to people to do the right thing without
actually fighting with any BSD person about it.

I ended up doing a significant reorganization of how MSS is computed
and used in SunOS TCP, to handle this problem properly.

Bob

Date: Thu, 7 Jan 1993 14:12:12 -0600
From: [email-masked] (David A. Borman)
To: [email-masked]
Subject: TCP MSS & Timestamps

In recent private mail conversation, it has come to my
attention that we probably don't all have a common view on
what to do with the TCP MSS value in the presence of TCP
options, since the TCP MSS value only refers to the TCP
data part of the packet, and the presence of TCP options
will affect that value.

Since 1323 is eligible for elevation to Draft status, this
is a good time to revise the document to clarify this issue.

First, there is a maximum packet size.  When you insert options,
the amount of space available for TCP data within a non-fragmented
IP packet goes down by the length of the options.  So, the option
length needs to be accounted for.

The "be conservative in what you send" rule can be applied
in two ways.  The first is in the generation of the MSS
value, you can say "well, I'll assume that the other side
won't adjust for the length of the options, so I'll adjust
for the option length when sending the MSS".  Meanwhile,
on the other side, when sending a packet, you can say "well,
I'll assume that the other side did not adjust for the options
length when it sent the MSS, and so I'll decrease the data
size by the option length".  You can do both, but then the
packets will usually be short.  So, you should pick one or the
other, but not both.

With two places to do the accounting for the options vs.
the MSS value, you get a grid like:

		| MSS is adjusted	| MSS is not adjusted
		| for options		| for options
----------------+-----------------------+--------------------
Sender adjusts	| packets are too	| packets are the
length for	| short			| correct length
options		|			|
----------------+-----------------------+--------------------
Sender doesn't	| packets are the	| packets are too
adjust length	| correct length	| long.
for options	|			|

The bottom right-hand corner is what we want to avoid, since that
is the case when IP will have to fragment the packet.  The only
way that the side that is sending the datagrams can guarantee that
it doesn't send IP packets that are too long is to always adjust
the data length by the length of the options.  It would be better
to send a packet that is a few bytes too short rather than one
that is a few bytes too long.

So, the bottom line is that I'd like to see a paragraph added
to 1323 stating that the generated MSS value only takes into
account the fixed IP and TCP header lengths, and that the side
that is generating the datagrams needs to adjust the length of
the TCP data to account for any IP or TCP options that it inserts
into the datagram.

Anyone disagree?

			-David Borman, [email-masked]

To: "Sean O'Malley" <[email-masked]>
Cc: [email-masked], [email-masked]
Subject: Re: SACK 
Date: Wed, 06 Jan 93 09:59:15 -0500
From: Christian Huitema <[email-masked]>

Sean,

Back in 81-82, we implemented a scheme which was very near from the
proposed TCP SACK in the "bulk transfer protocol" of the NADIR
project, for satellite networks. I remember that maintaining and
accessing the list of sacked segments was absolutely non trivial.

Out of your two choices, I would consider that we drop "1- Avoid
retransmission of SACKed segments." It is difficult to implement,
and there seem to be an agreement that we need "soft sacks" anyhow.
In this case, we can concentrate on "2- Speed retransmission of
unsacked segments", i.e. consider the "sacks" as "advisory nacks".

Implementing nacks only makes the memory management much simpler. At
worst, you can start from the "last acked packet" and count down the
transmitted segments. That is indeed expensive but:

	1) way less expensive than actually retransmitting all the
	counted down segments,

	2) often very short as the basic sack is of the form "ack up
	to N1, sack N2-N3", which means that you have to retransmit
	the segments located immediately after the last acked packet.

The real problem with "soft sacks" or "advisory nacks" have to do with
nack filtering, so that duplicate sacks will not cause multiple
retransmissions of a missing segment, and interaction with the
congestion control mechanisms -- what do we call now a "congestion
window"?

Christian Huitema

Date: Tue, 5 Jan 1993 11:49:51 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked], [email-masked], [email-masked]
Subject: Re: SACK

bob states:

> We did an experimental SACK implementation here.

Some more questions:

What TCP was it based upon? BSD?

What was the goal of the SACK option in your implementation. 
I have considered two different goals:
	1) Avoid retransmission of SACKed segments.
	2) Speed retransmission of unsacked segments

Was it a hard or soft SACK.

Is the source code avilable (to look at not to run)?

How extensive where the required changes?

Sean

Date: Tue, 5 Jan 1993 09:38:46 -0800
From: [email-masked] (Bob Braden)
To: [email-masked], [email-masked]
Subject: Re: SACK

> From [email-masked] Tue Jan  5 08:53:39 1993
> Date: Tue, 5 Jan 1993 09:54:32 MST
> From: "Sean O'Malley" <[email-masked]>
> To: [email-masked]
> Subject: SACK
> Content-Length: 576
> X-Lines: 13
> 
> 
> I have been attempting to implement a variation of the 
> originally proposed SACK option. Because the version of TCP I 
> am starting from (an x-kernelized version of the BSD TCP) 
> does not keep a list of transmitted segments implementing 
> SACK requires extensive code modifications. Getting rid of the 
> scaling on the SACK ranges helps somewhat but it is still not a 
> trivial modification. I was wondering if there are any TCP 
> implementations that keep a list of transmitted segments 
> around? It would also be nice to know if anyone else has 
> implemented SACK.
> 
> Sean O'Malley
> 

Sean,

We did an experimental SACK implementation here.  However, the SACK
spec we were considering used sequence numbers, so it would work with a
TCP that did not keep a list of transmitted segments.  There are not
very many TCPs around that do keep such a list, I suspect.  I once
wrote one that did, but I have decided the Berkeley guys got this one
right, and would not do it again.

Bob Braden

Date: Tue, 5 Jan 1993 09:54:32 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: SACK

I have been attempting to implement a variation of the 
originally proposed SACK option. Because the version of TCP I 
am starting from (an x-kernelized version of the BSD TCP) 
does not keep a list of transmitted segments implementing 
SACK requires extensive code modifications. Getting rid of the 
scaling on the SACK ranges helps somewhat but it is still not a 
trivial modification. I was wondering if there are any TCP 
implementations that keep a list of transmitted segments 
around? It would also be nice to know if anyone else has 
implemented SACK.

Sean O'Malley