Subject: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00

From: Bob Briscoe <[email-masked]>
Date: Wed, 01 Apr 2009 11:46:03 +0100

Stas,

This posting repeats what I said in the ledbat 
w-g meeting in SF, but to the whole list and with 
added reasoning, given the benefit of more time for thought.

On balance it seems wrong to aim for a hard-coded 
delay target (25ms). I understand your reasoning 
for it in the draft (dividing delay between 
competing flows rather than adding), but there 
are also stronger scaling reasons against it...

For 1500B* packets, 25ms represents a standing queue of:
    1 pkt @ 512kb/s
   17 pkt @   8Mb/s
   50 pkt @  24Mb/s (some backhaul links today)
  208 pkt @ 100Mb/s (typical PON access rate today)
2080 pkt @   1Gb/s (increasingly backhaul links are GigE)

As bottleneck links get faster (magically this is 
happening!), we will want to reduce the 
hard-coded delay (to save on fast buffer memory and the power it requires).

But if the the algo in draft-00 were changed in 
the future to aim at 10ms (while the installed 
base all still aimed at 25ms), the new code would 
always be starved by the installed base. 
Therefore we would be stuck forever with the 
number we first thought of: 25ms hard-coded.

Spelling this out longhand, imagine two flows competing:
         Flow N (New)    (10ms target)
         Flow L (Legacy) (25ms target)

L drives delay to 25ms
while both flows have packets to send {
     N reduces rate because delay greater than 10ms
     L sees delay decrease so increases its rate to drive delay to 25ms
}
Result: newer algorithm always starves.

IMHO, the algo needs to aim at minimising the 
congestion delay, not aim at a fixed target (the 
draft says the former but does the latter). 
Section 3 onwards of [Key04] may help, even tho 
it's in the context of adapting the receive 
window it's still based on delay sensing. I'd be 
interested to know whether Microsoft's BITS now 
implements something like this algo.

Bob

[* = This might be fine if packet size scaled 
with link speeds, but that isn't happening.]

[Key04] Peter Key, Laurent Massoulié and Bing 
Wang, "Emulating low-priority transport at the 
application layer: a background transfer service" 
In: "ACM SIGMETRICS '04/Performance '04: Proceedings of the joint international
conference on Measurement and modeling of 
computer systems", pp. 118--129 
<http://research.microsoft.com/apps/pubs/default.aspx?id=67381> (2004)

________________________________________________________________
Bob Briscoe,               Networks Research Centre, BT Research

---

From: Stanislav Shalunov <[email-masked]>
Date: Thu, 2 Apr 2009 23:11:21 -0700

Bob,

The choice of parameters for congestion control has a degree to which
it's arbitrary.  Why does TCP ramp up at a hard-coded 1 MSS/RTT?  Why
not 3.5 or 0.6?  Why does it multiply by 0.5 instead of 7/8 or 0.2 or
0?

If a future version of TCP chooses 0.2 and 0.3 as its favorite lucky
numbers while the installed base is at 1 and 0.5, the consequences are
similar.

While the choice of the particular parametrization for TCP might be
argued to be suboptimal because it doesn't scale with link speed, I'm
not aware of any congestion control mechanism without parameters.

The mechanism we use scales the target queue linearly with link speed,
as you point out.  It's a feature.  It enables the mechanism to work
on a variety of bottleneck speeds.  If you specify the target in
bytes, you lose on fast links because your delay starts getting lower
than scheduling noise and/or PCI bus jitter and you lose on slow links
because the delay is too large for interactive apps.

As choice of parameters goes, the choice of the gain is much more
arbitrary than the choice of the target.  The gain simply matches TCP
in the worst case.  Target is essentially the lowest value than can be
reliably distinguished from 0 on a variety of machines under a variety
of circumstances.

As a practical matter, 25ms is a substantial reduction from the 1RTT
rule of thumb and so it's reasonable to expect that the deployed gear
will have this much delay.  Usually it has far more.  (Even at 10Gb/s
and up.)  If some gear at an atypical bottleneck doesn't have this
much, the behavior degenerates into TCP.

It is also a fairly unsubstantial increase relative to RTT and will
remain such unless progress is made on the speed-of-light problem (or
the planet is shrunk?).

The work you cite never seems to mention minimizing delay as a goal.
It discusses the queuing delay achieved in Theorem 3.  And there's a
parameter that controls it (alpha_b^*).

-- Stas

On Wed, Apr 1, 2009 at 3:46 AM, Bob Briscoe <[email-masked]> wrote:
> Stas,
>
> This posting repeats what I said in the ledbat w-g meeting in SF, but to the
> whole list and with added reasoning, given the benefit of more time for
> thought.
>
> On balance it seems wrong to aim for a hard-coded delay target (25ms). I
> understand your reasoning for it in the draft (dividing delay between
> competing flows rather than adding), but there are also stronger scaling
> reasons against it...
>
> As bottleneck links get faster (magically this is happening!), we will want
> to reduce the hard-coded delay (to save on fast buffer memory and the power
> it requires).
>
> But if the the algo in draft-00 were changed in the future to aim at 10ms
> (while the installed base all still aimed at 25ms), the new code would
> always be starved by the installed base. Therefore we would be stuck forever
> with the number we first thought of: 25ms hard-coded.
>
> IMHO, the algo needs to aim at minimising the congestion delay, not aim at a
> fixed target (the draft says the former but does the latter). Section 3
> onwards of [Key04] may help, even tho it's in the context of adapting the
> receive window it's still based on delay sensing. I'd be interested to know
> whether Microsoft's BITS now implements something like this algo.
>
>
> Bob
>
> [* = This might be fine if packet size scaled with link speeds, but that
> isn't happening.]
>
> [Key04] Peter Key, Laurent Massoulié and Bing Wang, "Emulating low-priority
> transport at the application layer: a background transfer service" In: "ACM
> SIGMETRICS '04/Performance '04: Proceedings of the joint international
> conference on Measurement and modeling of computer systems", pp. 118--129

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

personal: http://shlang.com

---

From: Saverio Mascolo <[email-masked]>
Date: Fri, 3 Apr 2009 13:43:29 +0200

On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov
<[email-masked]>wrote:

> it's arbitrary.  Why does TCP ramp up at a hard-coded 1 MSS/RTT?

here i have an answer that it is important to have in mind, especially
because of many TCP variants that try a more aggressive probing (some of
them replacing TCP NewReno).

The  increasing at 1 MSS/RTT is the *unique* increase with  the property
that  *only one packet is lost* when  the path capacity is hit. This because
of  a feedback lag equal to RTT, i.e. after 1 RTT TCP  knows if the capacity
has been hit. This 1 MSS/RTT increment has the very nice property that only
one lost packet needs to be retransmitted.

TCP variants trying a more aggressive probing experience several packet
losses when the capacity is hit. So what happens is that the throughput
increases but also retransmissions so that you end up with same goodput but
with higher retransmissions, which is not good.

These considerations imply that when setting:

cwnd+=gain*(T_target-T_forward)

it is feasible to choose a low gain in order  to have a TCP less than best
effort but it is difficult  to set a larger gain to have a quick probing in
case of gigabit nets without ending in the problem before mentioned (we
tried it sometime ago and we give up)!

Why
> not 3.5 or 0.6?  Why does it multiply by 0.5 instead of 7/8 or 0.2 or

again, here  a less than best effort can be:

cwnd=min(cwnd/2,BWE*base_rtt)

saverio

> _______________________________________________
> ledbat mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ledbat
>

-- 
Prof. Saverio Mascolo
Dipartimento di Elettrotecnica ed Elettronica
Politecnico di Bari
Via Orabona 4
70125 Bari
Italy
Tel. +39 080 5963621
Fax. +39 080 5963410
email:[email-masked] <[email-masked]>

http://c3lab.poliba.it

---

From: Lachlan Andrew <[email-masked]>
Date: Sat, 4 Apr 2009 20:28:51 +1000

Greetings Saverio,

2009/4/3 Saverio Mascolo <[email-masked]>:
> On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov <[email-masked]>
> wrote:
>>
> The  increasing at 1 MSS/RTT is the _unique_ increase with  the property that
> _only_one_packet_is_lost_ when  the path capacity is hit.

It is the fastest, but increasing by 1 MSS  every 2 RTT also has that
property if there is a single flow.  More importantly, if there are
multiple flows, then 1 MSS/RTT doesn't guarantee a single loss per RTT
for a given flow, and so any benefit from that is lost.

$0.02,
Lachlan

-- 
Lachlan Andrew  Centre for Advanced Internet Architectures (CAIA)
Swinburne University of Technology, Melbourne, Australia
<http://caia.swin.edu.au/cv/landrew> <http://netlab.caltech.edu/lachlan>
Ph +61 3 9214 4837

---

From: "Don Bowman" <[email-masked]>
Date: Sat, 4 Apr 2009 10:16:45 -0400

> On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov
<[email-masked]>
> _only_one_packet_is_lost_ when  the path capacity is hit.

Has anyone taken a stab @ a model in NS? [http://www.isi.edu/nsnam/ns/].
It would
help answer the what-ifs of timing and interactions with other protocols
I think.

---

From: Arnaud Legout <[email-masked]>
Date: Sun, 05 Apr 2009 21:48:53 +0200

Hi

> help answer the what-ifs of timing and interactions with other protocols
doing simulations involving TCP in ns-2 is simply a bad idea, as ns-3 
has been released.
Why? Because in ns-3 you have the real TCP BSD stack in it. Ns-3 is not 
a simple evolution
of ns-2, it is a complete rewrite with a new design based on the 
experience gathered on ns-2.
Here is the URL for ns-3
http://www.nsnam.org/

Regards,
Arnaud.

---

From: Saverio Mascolo <[email-masked]>
Date: Tue, 7 Apr 2009 18:10:40 +0200

hi,

what about keeping track of the number of uploading connections N and using
the setting:

on ack reception:
cwnd+=(1/cwnd)*1/N

in any of the tcp connections open by the p2p client? this would make the
p2p application equivalent to one TCP uploading connection.

saverio

http://c3lab.poliba.it

=================================
This message may contain confidential and/or legally privileged information.
 If you are not the intended recipient of the message, please destroy it.
Any unauthorized dissemination, distribution, or copying of the material in
this message, and any attachments to the message, is strictly forbidden.

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 08 Apr 2009 19:03:21 +0100

Stas,

Pointing to other protocols that don't scale 
isn't a good reason for deliberately designing a 
new one that we know from the start won't scale 
into the future. But I guess it's up to me / 
others to come up with a more adaptive approach if we can.

more inline...

>not aware of any congestion control mechanism without parameters.

I believe it's particularly important to avoid 
non-dimensionless parameters (ie. to avoid 
parameters with units). Wherever there is one, 
I'd rather it was either adaptive, or a parameter 
under application control. But enough of these generalities...

>because the delay is too large for interactive apps.

All understood. I certainly wasn't proposing we set a buffer target in bytes.

But to me it's short-sighted and defeatist to say 
"operating systems will never reliably be able to 
measure delays to finer granularity than Xms". 
Just because they usually can't today.

The part I don't like is increasing rate to hit a 
target delay. I'd prefer that the algo 
continually increases rate (w per window say) 
whether or not there's delay, and decreases rate 
whenever it measures delay. Then the two will 
balance at the *lowest measureable* delay delta. 
I'd like to eventually see w under app-control 
through the API (that argument requires another 
thread). But, if I don't win that argument, w could initially be hard-coded.

This has the property that the more flows compete 
for the same queue, the more the delay will be. I 
know you don't like that, but I actually think 
it's a desirable property. It automatically 
solves sharing of bottlnecks and problems like 
the late-comers disadvantage (separate thread 
with Doug Leith). It's a proven approach in 
nearly every congestion control we have.

Imagine large numbers of flows share a hard-coded 
delay target, all with fixed gain. Imagine the 
measured delay is slightly above target. Each one 
makes a small rate reduction and gets surprised 
that the delay has reduced a lot more than they 
expected (because everyone else made a similar 
reduction). So they all increase more than they 
reduced. And the delay shoots up. Result, unstable oscillation?

I know, this depends on the relative RTTs etc...

I'm not saying there *is* a problem. It just 
seems a rate *increase* towards a hard-coded 
delay target is unnecessary. We only have to 
*reduce* in the presence of *any* measurable 
delay. Doing otherwise moves into unnecessarily 
uncharted territory that should have warning signs "Here be monsters".

>reliably distinguished from 0 on a variety of machines under a variety

Understood

>and up.)

I doubt the 1RTT rule of thumb is used much these 
days. It would require ridiculously large amounts 
of buffer memory on hi-speed interfaces. Back in 
2005, when I last asked, I discovered BT folks 
were generally configuring buffer sizes in a way 
that grew with about the sq-root of link speed 
(not deliberately following Nick McKeown's advice 
that came out around then, this was just 
happenchance even tho they knew about McKeown's papers).

You might configure about 25ms of buffer on a 
155Mb/s interface these days. But on a GigE I'm 
sure a good config would be less. For 10Gb/s 
interfaces, what's the evidence for them being 
config'd with far more than 25ms? Assuming 1500B 
pkt size, this is about 21,000 packets of buffer.

However, the point is that the trend for the 
future is to reduce buffer memory on faster 
interfaces, to reduce power requirements, given 
so much buffer is now believed not to actually be 
necessary. But I should also re-run my 2005 survey.

>If some gear at an atypical bottleneck doesn't have this

That sounds good if you say it quickly. But it's 
actually a failure. It means all the flows one 
expected to scavenge quietly in the background, 
actually compete on equal terms in the foreground.

Do you think of LEDBAT as a solution with 
long-term relevance for sharing any bottleneck? 
Or do you think of it as a stop-gap for sharing 
low speed bottlenecks? I don't use the term 
stop-gap disparagingly. I just mean something 
that loses relevance in 5-10years, rather than 
something that one expects will last as long as TCP has.

>remain such unless progress is made on the speed-of-light problem (or

I keep on constant alert for breakthroughs in 
these areas. But I'm currently more worried that 
a 25ms target is an unnecessarily large choice, 
given I don't believe we have to make a choice 
anyway (see alternative approach above).

>parameter that controls it (alpha_b^*).

Queuing delay is inside the alpha variable. On 
second thoughts, it's prob not worth using that 
paper to shed light on anything tho - too much 
generality is included, which makes it too 
complex as a basis for discussion here.

Bob

> Therefore we would be stuck forever
> congestion delay, not aim at a

---

From: Lachlan Andrew <[email-masked]>
Date: Thu, 9 Apr 2009 08:20:21 +1000

Greetings Bob,

2009/4/9 Bob Briscoe <[email-masked]>:
>> If you specify the target in
> But to me it's short-sighted and defeatist to say "operating systems will
> never reliably be able to measure delays to finer granularity than Xms".

It is easy to *measure* delay, the questions is "what is the source of
the delay?"  If delay is a sign of congestion, then it is justifiable
to back off.  If it is just jitter (something falling out of a cache
along the route, perhaps) then the OS has no way to know.

If jitter is consistently going down, then you're right about being
short sighted.  If jitter isn't going down, then we shouldn't design a
protocol which assumes it will.  Does anyone on the list have data
about trends in jitter?

> The part I don't like is increasing rate to hit a target delay. I'd prefer
> that the algo continually increases rate (w per window say) whether or not
> there's delay, and decreases rate whenever it measures delay. Then the two
> will balance at the *lowest measureable* delay delta.

That sounds like Doug's "delay AIMD".  He and I have been discussing
that, and it seems quite sensitive to asymmetric jitter.  If one flow
(with jitter) backs off noticeably when it senses a particular
threshold of delay then the flow without jitter never gets to see the
threshold met, and so never backs off until the jittered flow is
starved, and then the cycle repeats.

That might be avoided if the backoff is very small when delay is
experienced (like Vegas).

Also, the Linux stack has occasional very long delays of many ms;
should it set a "lowest measureable" target which is longer than these
very long delays, because otherwise the might be spurious?

> I'm currently
> more worried that a 25ms target is an unnecessarily large choice, given I
> don't believe we have to make a choice anyway

I agree that 25ms is an unnecessarily large delay, since jitter is
typically in the 1ms range.

$0.02,
Lachlan

---

From: "Don Bowman" <[email-masked]>
Date: Wed, 8 Apr 2009 22:43:58 -0400

Andrew Lachlan wrote:
>> All understood. I certainly wasn't proposing we set a buffer target
in
>> bytes.

Watch out for mobile networks where handoffs cause change in delay,
Changes in error correction (that tunnel you are driving through) cause
delay changes, etc. The network may also be able to dynamically shift
bandwidth from upstream to downstream (e.g. wimax, lte).
The latency is also much higher on 3G networks than on fixed.

Also dynamic bandwidth networks don't always have buffering
associated. An example, the 'powerboost' used in cable is a token-credit
model which allows higher than nominal rates to be achieved until
the sender/receiver is out of credits, and then it reverts to nominal
rate. No buffer depth changes occur, the scheduler just changes rate
suddenly. This has sometimes caused oscillations with media applications
that try to 'measure' the rate of the line, and then pick a codec.

 ...

>typically in the 1ms range.

I think this (1ms) is pretty low for mobile. I also think it's pretty
low for fixed.
Measurements I have done on RTP jitter (e.g. voip) show more like 10ms
of jitter for non-facilities-based voip, and I believe should be
consistent
for TCP.

The proposed initial use of ledbat is e.g. p2p file sharing. In this
application,
the other endpoint is as likely to be on the far side of the world as
the
far side of your street, so I think we will see a pretty wide dynamic
range
in both jitter (from the high hop count) and latency.

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 09 Apr 2009 12:53:01 +0100

Stas,

OK, taking what Lachlan has said, I now accept we need *a* hard-coded 
threshold below which we assume delay variation isn't necessarily congestion.

1/ The value is TBA. Perhaps 25ms, perhaps 5ms. Whatever we choose 
will always hurt in some cases (e.g. Don's); the choice is about 
which ones are corner cases we can live with. E.g. During mobile 
handover, there will be a period during which the controller gets 
confused. It will sort itself out in time. Is that important? 
Dunno... It's for debate.

I'd say it's something we can live with traded against the benefit of 
exploiting congestion info from delay 'most' of the time.

2/ But this still leaves questions about the core part of the control 
algo. However, these are more appropriate to Doug Lieth's thread on 
competing flows, so I'll shift to there.

Bob