Subject: [ledbat] draft-shalunov-ledbat-congestion-00.txt

From: Stanislav Shalunov <[email-masked]>
Date: Wed, 4 Mar 2009 04:43:39 -0800

I'm looking forward to everyone's comments.

---------- Forwarded message ----------
From: IETF I-D Submission Tool <[email-masked]>
Date: Wed, Mar 4, 2009 at 4:32 AM
Subject: New Version Notification for draft-shalunov-ledbat-congestion-00
To: [email-masked]

A new version of I-D, draft-shalunov-ledbat-congestion-00.txt has been
successfuly submitted by Stanislav Shalunov and posted to the IETF
repository.

Filename:        draft-shalunov-ledbat-congestion
Revision:        00
Title:           Low Extra Delay Background Transport (LEDBAT)
Creation_date:   2009-03-04
WG ID:           Independent Submission
Number_of_pages: 11

Abstract:
LEDBAT is an alternative experimental congestion control algorithm.

LEDBAT enables an advanced networking application to minimize the
extra delay it induces in the bottleneck while saturating the
bottleneck.  It thus implements an end-to-end version of scavenger
service.  LEDBAT has been been implemented in BitTorrent DNA, as the
exclusive congestion control mechanism, and in uTorrent, as an
experimental mechanism, and deployed in the wild with favorable
results.

The IETF Secretariat.

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

personal: http://shlang.com

---

From: Murari Sridharan <[email-masked]>
Date: Wed, 4 Mar 2009 10:42:40 -0800

Stas, it may be a good idea to send it as an attachment to the mailing list as well. 

Thanks

---------- Forwarded message ----------
From: IETF I-D Submission Tool <[email-masked]>
Date: Wed, Mar 4, 2009 at 4:32 AM
Subject: New Version Notification for draft-shalunov-ledbat-congestion-00
To: [email-masked]

Abstract:

The IETF Secretariat.

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

personal: http://shlang.com
_______________________________________________
ledbat mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ledbat

---

From: Murari Sridharan <[email-masked]>
Date: Wed, 4 Mar 2009 10:44:55 -0800

I meant the direct link, here you go
http://tools.ietf.org/html/draft-shalunov-ledbat-congestion-00

Thanks

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Murari Sridharan
Sent: Wednesday, March 04, 2009 10:43 AM
To: Stanislav Shalunov; [email-masked]
Subject: Re: [ledbat] draft-shalunov-ledbat-congestion-00.txt

Thanks

---------- Forwarded message ----------
From: IETF I-D Submission Tool <[email-masked]>
Date: Wed, Mar 4, 2009 at 4:32 AM
Subject: New Version Notification for draft-shalunov-ledbat-congestion-00
To: [email-masked]

Abstract:

The IETF Secretariat.

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

---

From: Saverio Mascolo <[email-masked]>
Date: Sat, 14 Mar 2009 00:10:52 +0100

hi,

i read the draft.  one note regarding keeping the delay low. the  cwnd
shrinking of TCP Westwood
may help in keeping queue delay low since it basically sets
cwnd=pipe-queueing, instead of halving.

saverio

-- 
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]

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: Stanislav Shalunov <[email-masked]>
Date: Fri, 13 Mar 2009 16:44:29 -0700

Saverio,

Thank you for the comment.  Do you think you might be able to put this
in terms of draft-shalunov-ledbat-congestion-00.txt?  How exactly
would halving need to change?

Thank you,  -- Stas

Saverio Mascolo <[email-masked]> wrote:
>
> hi,
>
> i read the draft.
>
>
> one note regarding keeping the delay low. the  cwnd shrinking of TCP Westwood
> may help in keeping queue delay low since it basically sets cwnd=pipe-queueing, instead of halving.
>
>
> saverio
>
>
>
> On Wed, Mar 4, 2009 at 1:43 PM, Stanislav Shalunov <[email-masked]> wrote:
>>

--
Stanislav Shalunov
BitTorrent Inc
[email-masked]

---

From: Richard Bennett <[email-masked]>
Date: Fri, 13 Mar 2009 17:23:01 -0700

My concern about this method is the possibility of poor interoperability 
with services that use UDP. The document takes great pains to document 
the desire and describe a method of deferring to TCP, but I don't see 
anything in it that leads to deferral to VoIP or any other inelastic 
service that uses UDP. There is a plethora (or at least "some") of 
low-cost traffic shaping middleware on the 'net that boosts UDP priority 
over TCP across the board, and this equipment will tend to cause false 
positives in the detection of uncongested links.

It's difficult for any endpoint traffic shaping solution to detect 
middleboxes that favor UDP, of course, but it may not be impossible. Two 
solutions come to mind:

1. Send TCP "sounding packets" across a path that's believed to be 
uncongested and compare latency to the UDP packets. If they're similar, 
the path is uncongested, and if not, you've found a traffic shaper.

2. Be VoIP-friendly (i.e., require latency suitable for VoIP ( < 150 ms) 
on any UDP path used by this protocol.)

3. Restrict the use of this protocol to paths that support ECN, which 
essentially makes it redundant.

There are downsides to both methods, of course: method 1 adds overhead 
to path selection, and method two may arbitrarily restrict path 
selection when no actual VoIP is in use. Setting a correct threshold 
will help here, and the recommended value (150 ms) is already pretty loose.

Anyhow, it strikes me that "VoIP-friendly" operation should be a goal, 
whether we know how to achieve it or not.

RB

-- 
Richard Bennett

---

From: Saverio Mascolo <[email-masked]>
Date: Sat, 14 Mar 2009 01:34:59 +0100

> would halving need to change?

like this:

on 3 duplicate acknowledgement:
            cwnd = base_delay*BWE  (1)

where BWE is the measured used bandwidth at time t* when the 3 DUPACK
is received.

it should be noted that at time t*:

current_delay*BWE

 represents  the full pipe

whereas base_delay*BWE

represents the pipe without queueing.

In other terms   BWE*(current_delay-base_delay*BWE) is  the queueing
that we  drive  to zero through the setting (1).

thanks,
saverio

http://c3lab.poliba.it

---

From: Nicholas Weaver <[email-masked]>
Date: Fri, 13 Mar 2009 17:37:03 -0700

On Mar 13, 2009, at 5:23 PM, Richard Bennett wrote:

> My concern about this method is the possibility of poor  
> interoperability with services that use UDP. The document takes  
> great pains to document the desire and describe a method of  
> deferring to TCP, but I don't see anything in it that leads to  
> deferral to VoIP or any other inelastic service that uses UDP. There  
> is a plethora (or at least "some") of low-cost traffic shaping  
> middleware on the 'net that boosts UDP priority over TCP across the  
> board, and this equipment will tend to cause false positives in the  
> detection of uncongested links.
>
> middleboxes that favor UDP, of course, but it may not be impossible.  
> Two solutions come to mind:
>
> uncongested and compare latency to the UDP packets. If they're  
> similar, the path is uncongested, and if not, you've found a traffic  
> shaper.
>
> 2. Be VoIP-friendly (i.e., require latency suitable for VoIP ( < 150  
> ms) on any UDP path used by this protocol.)
>
> 3. Restrict the use of this protocol to paths that support ECN,  
> which essentially makes it redundant.
>
> There are downsides to both methods, of course: method 1 adds  
> overhead to path selection, and method two may arbitrarily restrict  
> path selection when no actual VoIP is in use. Setting a correct  
> threshold will help here, and the recommended value (150 ms) is  
> already pretty loose.
>
> Anyhow, it strikes me that "VoIP-friendly" operation should be a  
> goal, whether we know how to achieve it or not.

There is a 4th random thought:

Do a protocol on top of TCP.  By wrapping it around TCP, you are  
defaulting to TCP friendly and you don't get the "UDP prioritization"  
which may occur, but by framing timestamps in the TCP message, then  
adding delay based on top, you can at least solve the access link  
buffer problem.

However, its still a very open question whether you get the same delay- 
increase during congestion on transit links or on shared DOCSIS uplinks.

---

From: Stanislav Shalunov <[email-masked]>
Date: Fri, 13 Mar 2009 18:18:54 -0700

On Fri, Mar 13, 2009 at 5:23 PM, Richard Bennett <[email-masked]> wrote:
> with services that use UDP. The document takes great pains to document the
> desire and describe a method of deferring to TCP, but I don't see anything
> in it that leads to deferral to VoIP or any other inelastic service that
> uses UDP.

Section 4.9 is named "Yield to TCP" to reflect the charter
requirement, but you'll see it considers loss-based congestion control
in general and discusses TCP as a special case.

Inelastic traffic is a degenerate case of loss-based congestion
control with a constant response function: rate = f(loss), where f(x)
= desired_rate does not depend on x.

Because inelastic traffic also does not ramp up, the described
protocol introduces one target worth of extra delay experienced by
inelastic traffic.

> There is a plethora (or at least "some") of low-cost traffic
> shaping middleware on the 'net that boosts UDP priority over TCP across the

Traffic shaping detectors are not on the charter.  Traffic shapers
operate differently and change their behavior in response to
application behavior changes.  The best one could hope for are
heuristics.  Heuristics obviously should not be SHOULD or MUST
requirements.  If there are good heuristics that prove useful today,
making them optional (MAY) could be advantageous.

> uncongested and compare latency to the UDP packets. If they're similar, the
> path is uncongested, and if not, you've found a traffic shaper.

What would be the destinations?  NB: NATs make it hard to answer "same."

What would be the packet size?  NB: Serialization delay requires that
it be same as for UDP.

How many packets to use?  Need a statistically significant sample.

A statistically significant sample of non-min-size packets starts to
look like serious overhead.

> 2. Be VoIP-friendly (i.e., require latency suitable for VoIP ( < 150 ms) on
> any UDP path used by this protocol.)

Better yet, we already have a stronger requirement not to add much
delay.  If the base delay is, say, 50ms, this translates into a much
tighter requirement.

If the base delay is large already -- say, a satellite link, --
instead of just failing, the low extra delay requirement produces
useful results.

150ms is not an IETF-defined threshold and extensive discussion
already happened in IPPM whether IETF should define or use absolute
network performance thresholds.  The consensus was to leave that to
other standards bodies.

> essentially makes it redundant.

This contradicts charter requirements:

   *  operate well in networks with FIFO queuing with drop-tail discipline

   *  be deployable for popular applications that currently comprise
noticeable fractions of Internet traffic

> There are downsides to both methods, of course: method 1 adds overhead to
> path selection, and method two may arbitrarily restrict path selection when
> no actual VoIP is in use. Setting a correct threshold will help here, and
> the recommended value (150 ms) is already pretty loose.
>

Totally.  Not adding much delay to VoIP packets would serve the goal
nicely and is achieved as part of a harder goal not to add much delay
to TCP packets.

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

---

From: Stanislav Shalunov <[email-masked]>
Date: Fri, 13 Mar 2009 18:27:09 -0700

On Fri, Mar 13, 2009 at 5:37 PM, Nicholas Weaver
<[email-masked]> wrote:
> Do a protocol on top of TCP.

Note that the draft describes the congestion control and not the
framing.  The congestion control scheme could be applicable in a
variety of scenarios: over UDP, as a TCP mod, over TCP, as a CCID for
DCCP, as an SCTP mod, etc.

Over TCP has some practical disadvantages, such as inability to
control packet size to reduce serialization on slow links and very
hard to debug interactions between control loops.  It's still an
option, and you're free to use this technique even if I couldn't get
it to work.  The framing is out of scope for the WG -- it was dropped
from the charter.

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

---

From: Stanislav Shalunov <[email-masked]>
Date: Fri, 13 Mar 2009 18:43:53 -0700

Procedural note:

When discussing draft-shalunov-ledbat-congestion, unless specified
otherwise, I speak as a document author and technical contributor to
the WG, not as a co-chair.

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

---

From: Stanislav Shalunov <[email-masked]>
Date: Fri, 13 Mar 2009 19:09:14 -0700

Saverio,

Thank you.

I haven't tried this, but it looks like it might be useful.

It is, however, less than TCP's halving.  In the current incarnation,
the protocol has the property that if the delay measurements are
completely bonkers in the worst possible way, it falls back to TCP.
That property would be lost.

What does everyone think?

-- Stas

On Fri, Mar 13, 2009 at 5:34 PM, Saverio Mascolo
<[email-masked]> wrote:
> On Sat, Mar 14, 2009 at 12:44 AM, Stanislav Shalunov <[email-masked]> wrote:
>> Do you think you might be able to put this

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

---

From: Saverio Mascolo <[email-masked]>
Date: Sun, 15 Mar 2009 02:04:20 +0100

dear stas,

On Sat, Mar 14, 2009 at 3:09 AM, Stanislav Shalunov
<[email-masked]> wrote:
> It is, however, less than TCP's halving.

actually it can be less or more. It depends on how large  buffering
delays  can be on the path.

on ack reception at time t* signaling congestion  (i.e. ECN or forward
delay larger than a threshold etc),

the term:

(base_delay+queueing_delay)*BWE

represents the in flight packets, that is,
cwnd=(base_delay+queueing_delay)*BWE.

the setting cwnd/2 can be larger or smaller than the setting cwnd=
base_delay *BWE depending on queueing delay. cwnd/2 will be larger if
queueing_delay>base_delay.

Thus if you want yield to TCP, you may want set:

cwnd=min(cwnd/2,base_delay *BW)

-savio

>In the current incarnation,

http://c3lab.poliba.it

---

From: Salvatore Loreto <[email-masked]>
Date: Wed, 18 Mar 2009 13:46:37 +0200

sorry for the silly question,
but it not fully clear to me how this congestion control scheme could be 
applicable to UDP
how in this case do you detect the packet loss? are you implicitly 
considering that each data packet as well as
each ack packet contains a sequence number?

/Sal

---

From: Stanislav Shalunov <[email-masked]>
Date: Wed, 18 Mar 2009 14:52:08 -0700

To layer this on top of UDP, one needs an intermediary framing with
sequence numbers, timestamps, your_delay equivalent, ACKs, and
possibly some authentication-related fields.

FYI, BitTorrent used a protocol called uTP for framing.  Framing is
not on the WG's charter.

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]

---

From: Matthew Kaufman <[email-masked]>
Date: Fri, 27 Mar 2009 14:51:41 -0700

Even though framing is not on the WG charter, would it not be 
appropriate for the security considerations section of the draft to 
address, for instance, ACK-splitting which can cause the congestion 
algorithm to misbehave if the framing algorithm allows such an attack?

Matthew Kaufman

---

From: Stanislav Shalunov <[email-masked]>
Date: Fri, 27 Mar 2009 20:03:37 -0700

Sure, specific comments are welcome.  If they apply to *any*
congestion control, it's probably overkill and would more usefully
belong in a different document about transport protocols security.  If
there's something peculiar to this algorithm related to security, then
it should be in the document, I'd expect.

On Fri, Mar 27, 2009 at 2:51 PM, Matthew Kaufman <[email-masked]> wrote:
> Even though framing is not on the WG charter, would it not be appropriate
> for the security considerations section of the draft to address, for
> instance, ACK-splitting which can cause the congestion algorithm to
> misbehave if the framing algorithm allows such an attack?
>
> Matthew Kaufman
>

-- 
Stanislav Shalunov
BitTorrent Inc
[email-masked]