Subject: [homegate] Buffers in home gateways

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 9 Nov 2009 20:26:43 +0100

To expand a bit on what I said in the jabber room about buffers in  
home gateways:

I've considered two approaches. The first is to see how much buffering  
you need for a single TCP session to achieve 100% utilization. Because  
of the congestion window sawtooth behavior, without any buffering, a  
single session would only be able to use 75% of the link bandwidth.  
Caveats: in practice, we of course have more than one session, there  
are limits to the TCP window size and I might be completely mistaken.  
But anyway:

approx linkbw ^ 2 / MSS * RTT * 7 for the buffer size in bytes if the  
linkbw and MSS are in kilobits. For MSS = 12 and RTT = 0.3:

linkbw	buffer size  buffer time
64k	717          90 ms
128k	2867         179 ms
256k	11k          344 ms
1M	171k         1368 ms
10M	17M          13.6 s
100M	1669M        133 s
1G	163G         21.7 m
10G	16T          3.5 h

So basically, trying to go from 75% to 100% isn't worth the trouble as  
soon as you approach speeds of a megabit.

Then what? What's the minimum that TCP needs to be able to function?  
Basically, three packets. With delayed acknowledgments, one ACK  
releases two new segments, and another one if the congestion window  
grew by one packet. If you can't buffer these three packets the  
congestion window can't grow so TCP can't do its job.

Of course if you have three buffers and one, two or three of them are  
filled and then a three packet burst comes in you're going to lose at  
least one packet. So it seems beneficial to have more buffers. But  
that doesn't help, TCP will just fill them up and create a standing  
queue. So the chances of a lost packet remain the same.

Now perhaps buffering only three packets is a bit too radical,  
especially in the absense of simulations or real-world testing. But we  
do have experience with 10 packet buffers, and those seem to work. So  
I'd suggest "no more than 10" as our bottom line for now. And a good  
AQM scheme is highly recommended to avoid the tail drops that happen  
all over the place in everything I talked about so far.

---

From: Aki M Nyrhinen <[email-masked]>
Date: Tue, 10 Nov 2009 22:31:37 +0200

I don't understand your numbers. I haven't really followed the discussion
well enough, but now feel the urge to provide some input anyway (danger).

The following states my personal opinion which I try to loosely justify in
an unscientific manner. I don't claim this is the only truth, and I'm
sure the details could be debated forever. In any case, I hope some of
this is useful.

On Mon, Nov 09, 2009 at 08:26:43PM +0100, Iljitsch van Beijnum wrote:
> To expand a bit on what I said in the jabber room about buffers in home 
> gateways:
>
> Caveats: in practice, we of course have more than one session, there are 
> limits to the TCP window size and I might be completely mistaken. But 
> anyway:
>

If you aim at full utilization when RTT is 0.3 seconds, what exactly is
preventing TCP from achieving full utilization with 0.3 seconds worth of
buffering (that being linkbw * 0.3 in bits or bytes)? It really is this
simple if you know your RTT: TCP will halve its CWND upon a loss, which
occurs when the buffer is full, so if we set the buffer to RTT * BW, the
halved window still exactly saturates the link, leading to full utilization
and has nothing to do with how long it takes to complete a TCP sawtooth
cycle.

> Basically, three packets. With delayed acknowledgments, one ACK releases 
> two new segments, and another one if the congestion window grew by one 
> packet. If you can't buffer these three packets the congestion window 
> can't grow so TCP can't do its job.

> least one packet. So it seems beneficial to have more buffers. But that 
> doesn't help, TCP will just fill them up and create a standing queue. So 
> the chances of a lost packet remain the same.

> I'd suggest "no more than 10" as our bottom line for now. And a good AQM 
> scheme is highly recommended to avoid the tail drops that happen all over 
> the place in everything I talked about so far.

I agree that TCP would suffer incredibly with very small buffers (less
than 3-4 packets), but the "no more than 10 packets" statement is not
reasonable in a longer term either. Nor do I think TCP being able to
function is good enough for high bandwidth uplinks. Such a limit will not
destroy TCP performance but will cause premature termination of the slow
start phase.  Assuming delayed acks and that the access uplink is the
bottleneck, the slow start phase looks like bursts that hit the bottleneck
gateway at 1.5 times available bandwith, meaning its buffer will grow at 0.5
times the link bandwidth, leading to termination of slow start after the
burst length exceeds 20 packets, possibly earlier depending on whether the
buffer has time to drain completely before the last burst starts.

	    | burst |
	RTT | len   | cwnd
	----+-------+------
	  1 |  2    |  2
	  2 |  3    |  3
	  3 |  3    |  4
	  4 |  6    |  6
	  5 |  9    |  9
	  6 | 12    | 13
	  7 | 18    | 19
	  8 | 27    | 28
	  9 | 42    | 42

Looking at this table of slow start induced burst lengths with delayed
acks (i just wrote it, may contain errors), the slow start would end after
8th RTT and result in a congestion window of 15-21 packets which would
then be incremented in congestion avoidance. Assuming an end-to-end RTT
of 100ms somewhat arbitrarily, this is about 2 megabits per second, so
anything significantly faster or further than 100ms away would be forced
to congestion avoidance roughly after the speed of 2 megabits per second.

Assuming quick acks, the bursts would hit the bottleneck at twice available
bandwidth, leading to even smaller CWND and earlier switch to congestion
avoidance.

I see the real difficulty in just picking one number as follows:

	* for a long RTT, striving for full utilization will conflict
	  needs of interactive users.

	* access uplink bandwidth varies, so a fixed number of packets
	  good for one case can be bad for others (0.3s for 5 Mbps is
	  3s for 512 kbps).

	* the (end-to-end!) RTT varies wildly and can be independent of
	  the access link RTT.

I personally can use interactive sessions (that is, ssh) comfortably
upto about 0.25s RTT, beyond which it starts to feel irritatingly
sluggish, and becomes too annoying to use after exceeding 1s. For me,
this means that if I'd tune the buffers for full utilization in the
Internet (say 0.3s end-to-end RTT), I would no longer be happy with
the responsiveness of my interactive sessions. For pathological cases,
things like line-mode could help, but not all programs can be used that
way, and I have yet to see an ssh-client that comes with line-mode
capability.

Consequently, I would pick something as large as possible while keeping
response times for interactive traffic bearable, which boils down to about
0.1s (for me). The reasoning is that if the ISP-side would also choose 0.1s
buffer, this would limit the access link buffer induced RTT increase to
0.2s when bulk transfers saturate both directions, which is still within
my arbitrarily defined pain bound of 0.25s.

Achieving this does require that the gateway adjust its buffer size based
on actual access uplink bandwidth, which is easy for ADSL-type links and
hard for shared medium. But I doubt anything less would be better than
the current randomly sized buffers which people work around by TCP window
limiting and additional policing boxes in front of the gateway.

To summarize, the buffer bound should be IMO set to bound the worst case
damage to response times instead of trying to maximize bulk transfer
throughput for any statistical Internet path, which for actual Internet
RTTs will inevitably lead to unacceptable worst case behavior. But (say)
0.1 seconds worth of buffering at actual access uplink rate seems much
more sensible to me than 10 packets, in terms of both, achieving high
utilization and good response time.

Best regards,

	Aki

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 10 Nov 2009 23:21:28 +0100

> well enough, but now feel the urge to provide some input anyway  

I have included the original message in which I arrive at this  
conclusion at the end of the message.

> buffering (that being linkbw * 0.3 in bits or bytes)?

Let's suppose 10 kiloBIT packets, 10 Mbps and a 0.1 RTT to make the  
calculations nice and simple. That would mean 1 megabit worth of  
buffering as per your suggestion, or 100 packets.

Without buffering TCP would sawtooth between 5 and 10 Mbps, or a  
congestion window of 50 to 100 packets for an average of 75 = 75%  
utilization. What we really want is to cycle between 67 and 133 for an  
average of 100 = 100% utilization.

So we add 100 packets (0.1 s) worth of buffering. Then, when the cwnd  
reaches 101, 100 packets are transmitted and one is buffered. The next  
RTT the cwnd is 102 packets so 100 are transmitted and 2 buffered, so  
the total number of packets in the buffer is 3. So:

roundtrip: queue size
1: 1
2: 3
3: 6
4: 10
5: 15
6: 21
7: 28
8: 36
9: 45
10: 55
11: 66
12: 78
13: 91
14: tail drop

So you don't reach the intended 133 cwnd, but only 114 so you cycle  
between 57 and 114, average 85 = 85% utilization.

So this whole notion of one RTT worth of buffering is an urban myth,  
certainly in the case of of a single TCP session, and I stronly  
suspect also with multiple sessions (I would expect the required  
buffering to go down in a logarithmic or square relationship to the  
number of sessions but haven't been able to figure out the math to  
show that.)

The problem here is that your buffer requirements go up with the  
square of the bandwidth but your transmission rate only increases  
linerarly with bandwith so now your RTT goes up with bandwidth and  
quickly gets out of hand as I showed in my previous message.

> reasonable in a longer term either.

Why not?

> Nor do I think TCP being able to
> start phase.

You assume that if you put X buffers in a gateway (or switch, but the  
switch people seem to think all of this doesn't apply to them) then a  
fresh TCP session gets to send an X packet burst. That's only true if  
the link was previously idle. I don't think we can assume that. If  
there are ongoing bulk data transfers you're lucky to find two empty  
buffers.

However, you're right that with minimal buffering slow start suffers  
and it takes a long time to get up to speed for long delay sessions.  
The question is where sweet spot is between quick ramping up of slow  
start sessions and the delays caused by standing queues with large  
amounts of buffering. I guess someone should run some experiments or  
simulations.

> 	* the (end-to-end!) RTT varies wildly and can be independent of

Right.

> my arbitrarily defined pain bound of 0.25s.

Note that at 128 kbps 0.1 s is only 1 packet...

> hard for shared medium.

Well, originally the TTL field was supposed to count how long packets  
sat in buffers in routers. It wouldn't be inconceivable for a gateway  
to buffer packets and drop them after being buffered for 0.1 s.

> utilization and good response time.

Unfortunately, there doesn't seem to be a magic formula that provides  
an all around good buffer size. There's probably no way around active  
queue management to achieve good overall performance. Certainly if we  
want to address low delay applications such as VoIP.

Iljitsch

The original message:

On 1 aug 2009, at 14:23, Iljitsch van Beijnum wrote:

> One purpose of buffers is as follows. Consider a non-buffering router:

>  --------------
>     /| /| /| /|
>    / |/ |/ |/ |
>   /
>  /
>  --------------

> So with a single flow we cycle between 50% and 100% utilization for  
> an average of 75%. If we now add buffer space to accommodate the  
> missing 25% TCP can run 33% faster and reach full utilization. So  
> the buffering would need to be 33% of an RTT worth of data.

This is incorrect: the space between two teeth in the sawtooth isn't  
an RTT, but the time it takes to grow to the maximum window size from  
the "minimum" window size, so ~ 2/3 * link bandwidth / MSS * RTT.

So for instance, on a 1 Mbps link with a 300 ms RTT a sawtooth cycle  
takes 17 seconds. (The window for 1 Mbps = 85 packets, we cycle  
between 2/3 and 4/3 of that = 57 to 133, which takes 56 RTTs in  
congestion avoidance.)

Half that time we're building up a surplus, which needs to be large  
enough to fill in the deficit during the other half of the cycle. So  
that amount of data is half of a sawtooth wide and and varies between  
zero and a third of a link bandwidth high. So that's 2/3 * linkbw /  
MSS * RTT / 2 * linkbw / 6 = linkbw ^ 2 / MSS * RTT / 18 or approx  
linkbw ^ 2 / MSS * RTT * 7 for the buffer size in bytes if the linkbw  
and MSS are in kilobits. For MSS = 12 and RTT = 0.3:

We already knew that 1 MSS per RTT window growth doesn't do long fat  
pipes any favors, but the above shows how bad it really is. The 1500- 
byte packet size doesn't help, either.

This means that the notion of enough buffering to fill in the valleys  
in the sawtooths is untenable. Then what? A minimum of 3 packets  
allows for a normal 2-packet "burst" after a delayed ACK and then a 1- 
packet window growth. Less than that and TCP will trip over itself  
whenever cwnd grows in congestion avoidance, making it impossible to  
reach a reasonable cwnd.

With multiple sessions at the same time, we would like to give all  
sessions 3 packets worth of buffer space. Simply increasing the buffer  
won't do that because a single session will use up the additional  
buffer space (until it runs out of various windows and buffers in the  
sender or receiver). So in a tail drop scenario there doesn't seem to  
be any advantage in using more than a 3-packet buffer...

---

From: Murari Sridharan <[email-masked]>
Date: Tue, 10 Nov 2009 23:05:21 +0000

Just glanced through this but here are some very useful pointers and a few of my points. 

1. Firstly buffer sizes can be considerably lower than the standard rule of thumb whenever there is enough statmux. Statmux is really the key to lowering buffering requirements by upto a factor of sq.rt of N, where N is the number of flows. At home that may not be the case. Some interesting reading here http://portal.acm.org/citation.cfm?id=1163593.1163605
2. Too small buffering can be a serious problem at the edges. Instead of trying to explain it, here is a quick link http://portal.acm.org/citation.cfm?id=1198262

We are doing some work on improving perfornmance over low buffered links and will have something to share may be by the next IETF. 

Thanks
Murari

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Iljitsch van Beijnum
Sent: Tuesday, November 10, 2009 2:21 PM
To: Aki M Nyrhinen
Cc: [email-masked]
Subject: Re: [homegate] Buffers in home gateways

roundtrip: queue size
1: 1
2: 3
3: 6
4: 10
5: 15
6: 21
7: 28
8: 36
9: 45
10: 55
11: 66
12: 78
13: 91
14: tail drop

Why not?

Right.

Iljitsch

The original message:

With multiple sessions at the same time, we would like to give all  
sessions 3 packets worth of buffer space. Simply increasing the buffer  
won't do that because a single session will use up the additional  
buffer space (until it runs out of various windows and buffers in the  
sender or receiver). So in a tail drop scenario there doesn't seem to  
be any advantage in using more than a 3-packet buffer...
_______________________________________________
homegate mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/homegate

---

From: "Woundy, Richard" <[email-masked]>
Date: Tue, 10 Nov 2009 18:07:12 -0500

Iljitsch,

> So this whole notion of one RTT worth of buffering is an urban myth,
certainly in the case of of a single TCP session

I would consider reading the following Sigcomm 2004 paper, "Sizing
Router Buffers" by Appenzeller, Keslassy, and McKeown,
http://yuba.stanford.edu/~nickm/papers/sigcomm2004.pdf, especially
sections 1.2, 2 and 3.1.

Section 2 shows the mathematics behind why a router (with a bottleneck
link) handling a single long-lived TCP flow ought to have a buffer size
equal to the bandwidth delay product.

Section 3.1 indicates that a relatively small number of long-lived TCP
flows (such as at a home router) will tend to become synchronized, and
therefore the buffer size should still be equal to the bandwidth delay
product.

Section 3.2 and beyond indicate that long lived TCP flows tend to become
de-synchronized at routers in backbones and other places of aggregated
traffic, and suggests that such routers could use much less than the
bandwidth delay product for buffering.

It may take me a while to figure out why your calculations and
conclusions are so different. But I am pretty sure that your
calculations for achieving near 100% utilization for a single TCP flow
at 10 Mbps using 17 MB buffers seem really high.

-- Rich

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Iljitsch van Beijnum
Sent: Wednesday, November 11, 2009 7:21 AM
To: Aki M Nyrhinen
Cc: [email-masked]
Subject: Re: [homegate] Buffers in home gateways

roundtrip: queue size
1: 1
2: 3
3: 6
4: 10
5: 15
6: 21
7: 28
8: 36
9: 45
10: 55
11: 66
12: 78
13: 91
14: tail drop

Why not?

Right.

Iljitsch

The original message:

---

From: Murari Sridharan <[email-masked]>
Date: Tue, 10 Nov 2009 23:10:25 +0000

Another note of caution. In my experience the throughput is typically below the theoretical amount due to quirks in implementation and system issues so at 10G speeds we recently tried out a zero buffer itest, you don't automatically get 75% with new reno its in fact lower than that. Again too much buffering is a problem but there are ways to address that, but too shallow a buffer can seriously hamper throughput. As I said we are hoping to share our results and shed some light on this problem in general prior to the next IETF.  

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Woundy, Richard
Sent: Tuesday, November 10, 2009 3:07 PM
To: Iljitsch van Beijnum; Aki M Nyrhinen
Cc: [email-masked]
Subject: Re: [homegate] Buffers in home gateways

Iljitsch,

-- Rich

-----Original Message-----

roundtrip: queue size
1: 1
2: 3
3: 6
4: 10
5: 15
6: 21
7: 28
8: 36
9: 45
10: 55
11: 66
12: 78
13: 91
14: tail drop

Why not?

Right.

Iljitsch

The original message:

---

From: Markku Kojo <[email-masked]>
Date: Wed, 11 Nov 2009 08:58:14 +0200 (EET)

Hi Iljitsch,

On Tue, 10 Nov 2009, Iljitsch van Beijnum wrote:

> I have included the original message in which I arrive at this conclusion at
> the end of the message.
> 
> calculations nice and simple. That would mean 1 megabit worth of buffering as
> per your suggestion, or 100 packets.
> 
> Without buffering TCP would sawtooth between 5 and 10 Mbps, or a congestion
> window of 50 to 100 packets for an average of 75 = 75% utilization. What we
> really want is to cycle between 67 and 133 for an average of 100 = 100%
> utilization.

The problem with your 100% avg utilization logic here is that you 
incorrectly assume that by adding buffering you get  > 100% link 
utilization when pkts start accumulating in the buffer!?

When cwnd becomes  > 100 pkts in this example (assuming zero delay for  
the rest of the path), the pkts get buffered at the bottleneck link and 
the link is fully utilized but it still delivers pkts only at max 
link rate!
That is, at times when your cwnd is < 100 pkts your link is underutilized,
and if your link is ever underutilized during your connection (or
observation time period) you can never reach 100 % avg utilization.

After inflating cwnd beyond buf size + link BDP (bandwidth-delay product), 
a pkt drop occurs and cwnd is halved (in CA). Therefore, the cwnd size 
must be at least 2*BPD at the time (before) cwnd gets halved in order to 
allow a TCP sender to continue 100% utilization of the bottleneck link as 
Aki pointed out. But this holds only when the rest of the path delay is 
zero, which is not the case in the real world. In effect, the rest of the 
path delay varies and makes it hard to determine the proper buffer size 
as Aki also pointed out. Longer the rest of the path delay is, less 
buffering is needed to keep up 100% bottleneck link utilization all the 
time. In the example you had,  33 pkt buffer size would be good enough if 
the rest of the path delay is long enough to accomodate buffering 
capacity for 67 pkts. Then the flightsize and cwnd may reach 200 pkts 
before a drop occurs and allow to continue with cwnd of 100 pkts.

Furtehrmore, there is a bunch of other dynamics that affect determining a 
proper buffer size, including multiple flows (statistical multiplexing).
And this makes it even harder. 

Cheers,

/Markku

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 11 Nov 2009 08:19:23 +0100

On 11Nov, 2009, at 0:05 , Murari Sridharan wrote:

> 1. Firstly buffer sizes can be considerably lower than the standard rule of thumb

Looks like this rule of thumb was invented in this paper:

High performance tcp in ansnet

http://www.scs.stanford.edu/nyu/04sp/sched/ans-tcp.pdf

However, they provide no justification at all!

> http://portal.acm.org/citation.cfm?id=1163593.1163605

This only talks about the core of the network where the number of sessions is very large.

> 2. Too small buffering can be a serious problem at the edges. Instead of trying to explain it, here is a quick link http://portal.acm.org/citation.cfm?id=1198262

They tested with 2 buffers... We already established you need at least 3. They also consider the case where there is more than a single TCP flow, which is of course what we need to do ultimately, but at this point I'm not even sure we understand the needs of a single TCP flow.

> We are doing some work on improving perfornmance over low buffered links and will have something to share may be by the next IETF. 

Cool! Please send a pointer when you're ready.

Iljitsch

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 11 Nov 2009 08:24:51 +0100

> observation time period) you can never reach 100 % avg utilization.

What happens is that during the > 100% periods the excess packets beyond 100% are buffered. Then, during the < 100% periods, the buffer is drained so the 100% rate is maintaned. I calculate the required amount of buffering as follows as in my earlier messages:

and MSS are in kilobits

It's really easy to show this in a figure, where you can see that the part of the sawtooth above 100% must be buffered to fill in the empty part below 100%.

Iljitsch

---

From: Lars Eggert <[email-masked]>
Date: Wed, 11 Nov 2009 17:37:44 +0900

Hi, Iljitsch,

I note that ns2 and ns3 should be readily available to verify the math :-)

Lars

---

From: Markku Kojo <[email-masked]>
Date: Wed, 11 Nov 2009 10:39:19 +0200 (EET)

On Wed, 11 Nov 2009, Iljitsch van Beijnum wrote:

> What happens is that during the > 100% periods the excess packets 
> beyond 100% are buffered. Then, during the < 100% periods, the buffer is 
> drained so the 100% rate is maintaned. 

Right, but you need to have enough pkts in the queue to fill the gap,
i.e., the time during which a TCP sender is not sending any new data.

When the cwnd gets halved and the TCP sender fast retransmits, the TCP
sender is not sending any new data pkts until a half of the flightsize 
worth dupacks have arrived at the sender (assuming rate-halving is 
not used). In your example the flightsize (and cwnd) would be 
133 pkts, and after cwnd is halved cwnd becomes ~67 pkts. Now duirng 
the fast recovery the TCP sender needs to wait until 67 dupacks have 
arrived to inflate cwnd beyond 133 pkts and continue injecting new data. 
These dupacks arrive at the same rate as the router buffer at the 
bottleneck link drains. So, with buffer size of 33 pkts there will be a 
gap with no data in the buffer that (roughly) equals to 67-33=34 pkts 
at the link rate --> link becomes underutilized.

/Markku

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 11 Nov 2009 09:39:56 +0100

> I note that ns2 and ns3 should be readily available to verify the math :-)

Should be easy enough to do: just manipulate the amount of router buffering with standard TCP.

But I have MPTCP work that I need to get done...

Iljitsch

---

From: Murari Sridharan <[email-masked]>
Date: Wed, 11 Nov 2009 08:42:09 +0000

Iljitsch, you should look at the Stevens book there is a nice illustration that talks about the gap that markku outlines below. 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Markku Kojo
Sent: Wednesday, November 11, 2009 12:39 AM
To: Iljitsch van Beijnum
Cc: [email-masked]
Subject: Re: [homegate] Buffers in home gateways

/Markku

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 11 Nov 2009 10:37:53 +0100

> Iljitsch, you should look at the Stevens book there is a nice illustration that talks about the gap that markku outlines below. 

As I tried to explain, there is no gap, this is why my result is so much higher than the bandwith RTT product.

With the numbers used earlier (10 Mbps, 10 kilobit packets, 0.1 s RTT) in congestion avoidance it would take 66 RTTs to grow from the minimum cwnd of 67 to the maximum of 133, where half of that time we build up a surplus that needs to be buffered and the other half of the time there is a deficit that we fill in with buffered packets. During 33 RTTs that we buffer we start with 1 surplus packet and end with 33 so an average of 17. So we need to buffer 33 * 17 = 561 packets, nearly 6 times the BW RTT product.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 11 Nov 2009 21:18:07 +0100

On 11 nov 2009, at 0:07, Woundy, Richard wrote:

>> So this whole notion of one RTT worth of buffering is an urban myth, certainly in the case of of a single TCP session

Ok, this is the part where I have to eat my words and admit that I was wrong. I hate it when that happens.

What I overlooked is the ACK clocking. When the link supports a cwnd of 100 but the cwnd becomes 101, that means one packet needs to be buffered. But then when cwnd becomes 102, that means 1 extra packet, not 2, because the ACKs keep returning at a rate of 50 that ACK two packets so two new packets are released except when the window just grew, in which case it's 3, which only happens once per RTT. So the buffering requirements are linear with bandwidth.

> http://yuba.stanford.edu/~nickm/papers/sigcomm2004.pdf, especially

Thanks. This is much better than the 1994 paper I mentioned earlier. However, it looks like they modeled TCP Reno rather than TCP New Reno, i.e., they don't account for the fast recovery phase, so they arrive at a larger buffering requirement because they assume the sender will stop sending after a loss rather than do a fast retransmit and keep going with a reduced cwnd.

Putting it all together, it looks like there is some magic number of buffers somewhere between 0.5 and 1.0 times BW*RTT (some back of the envelope stuff suggests something like BW*RTT-SQRT(BW*RTT*2)) where the buffer builds up until there is a tail drop, and then the sending rate drops to below the link rate for just long enough to drain the built up queue and the cycle restarts.

Too much buffering isn't as disasterous as it would seem. For instance, with BW*RTT worth of buffering the cwnd grows to exactly twice the link rate, so a loss then kicks it down to the cwnd that matches the link rate and the buffer doesn't drain. This means that we almost immediately get a tail drop and _then_ the cwnd gets significantly below the link rate so the queue will drain for a while.

On the other hand, if there isn't enough buffering then after a single drop the cwnd becomes so low that the queue drains completely and then the link goes idle for some time before the cwnd reaches the size that matches the link rate.

All of the above suggests that any amount of buffering will make TCP perform at least a little better than the theoretical 75% without buffering and even having too much buffering isn't immediately disasterous as there won't be standing queues that cause immediate tail drops for all new sessions.

So 10 packets worth of buffering seems a reasonable starting point. It's still pretty slow at 128 or 256 kbps, but not to an unworkable degree, and assuming a 0.1 RTT 10 packets is BW*RTT at 1200 kbps so full single TCP flow performance upto somewhere in the 1 - 2 Mbps range.

(Interesting by the way that we're having a detailed discussion here while the congestion control gurus in ICCRG had little or no interest in this subject.)

Iljitsch

---

From: Lars Eggert <[email-masked]>
Date: Thu, 12 Nov 2009 09:49:56 +0900

> (Interesting by the way that we're having a detailed discussion here while the congestion control gurus in ICCRG had little or no interest in this subject.)

I dare saying that that is because the conclusion we're reaching here aren't exactly new.

Lars

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 12 Nov 2009 08:31:34 +0100

> I dare saying that that is because the conclusion we're reaching here aren't exactly new.

Then why is there no RFC providing guidance to vendors about this issue?