Subject: [ledbat] on "random reshuffling"

From: David Ros <[email-masked]>
Date: Tue, 9 Nov 2010 14:53:02 +0800

Hi,

I did not raise this in the meeting because I haven't actually read the paper, but there's some (seemingly) relevant work about to appear in Globecom 2010.

The authors seem to claim that the random_input method proposed in the ledbat draft does not work. The paper is a little light on details, and they tested this using simulation, but it's a data point nonetheless.

It's available here: http://arxiv.org/pdf/1006.3018

Regards,

David.

=================================================================
David ROS
http://www.rennes.enst-bretagne.fr/~dros/

I love deadlines. I like the whooshing sound they make as they fly by. -- Douglas Adams

---

From: Murari Sridharan <[email-masked]>
Date: Tue, 9 Nov 2010 07:47:45 +0000

David, thanks, excellent timely reference, I just briefly glanced through this and I'd leave it upto the editors to incorporate appropriate text. Not I am not saying we change anything in the algorithm but simply to add text backup or if we decide that the random perturbation isn't adding value we can remove that from the document and just state the assumptions for fairness which is already included in the discussion section. 

Thanks
Murari 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of David Ros
Sent: Monday, November 08, 2010 10:53 PM
To: [email-masked]
Subject: [ledbat] on "random reshuffling"

Hi,

Regards,

David.

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

---

From: Dario Rossi <[email-masked]>
Date: Fri, 12 Nov 2010 13:14:32 +0100

Dear all,

I have previously sent some information regarding LEDBAT open points 
(25th september 2010),
but the mail was possibly too long, and hence some information was lost 
in the process (for your convenience, I have recollected the original 
mail text and put it online at:
http://perso.telecom-paristech.fr/~drossi/index.php?n=Software.LEDBAT#ietf )

briefly, as far as the "random reshuffling" is concerned, our Globecom 
experiments show that it does not help --  rather, dropping the 
congestion window may, which is due to two reasons:
1) in the 80s it has been shown that AIAD dynamics lead to unfairness 
(with drop is no longer AIAD),
2) window drops help latecomer to correct their base delay estimate (as 
the queue may empty)

a more recent study is available at http://arxiv.org/abs/1010.5623  where:
1) we show that the problem arise even with the current BitTorrent 
implementation http://github.com/bittorrent/libutp
2) we also show that the problem is exhacerbated by backlogged transfers 
(while chunk-by-chunk transmission the latecomer unfairness reduces)
3) we  propose a more mature solution (which  is not yet available on 
our Linux implementation on the Web, but if there is interest on the 
list, we may fix this easily)

notice that I have not had the time to read the latest version of the 
draft (sorry!)

Best regards,
D.

-- 

* Available implementations

Recently, several implementations of LEDBAT appeared: to the best of our 
knowledge, only BitTorrent [BT] and the ns2+Linux [OPENLEDBAT] 
implementations are publicy available, while other implementations are 
used in performance evaluation studies such as [ITC22] and [ATQR] but 
not available online.

[BT] used to differ from LEDBAT specification in (1) the choice of a 
TARGET=100ms parameter (while in the draft is/was set to 25ms) and (2) 
in the use of variable framing (outside of draft scope).

So far, these implementation have not been experimentally compared.

* Experimental studies

The BitTorrent implementation (though based on the previous 
closed-source uTP and not on the open-source [BT] release) has been 
evaluated in [PAM], which points out that the level of low priority of 
LEDBAT depends on the TCP flavor and settings, and that cross traffic in 
the reverse path may have an important impact in practice.

Further details concerning the [BT] implementations are available in 
[IPTPS] where  BitTorrent details an algorithm to solve the problem of 
the clock drift in LEDBAT, that ameliorate the queuing delay estimation 
at the sender side.

The experimental work in [ITC22] exploits instead a own implementation 
and points that LEDBAT may not work as expected (and actually might be 
needed) in case active queue management techniques AQM are applied in 
user modems (the study also suggests AQM to become a default practice in 
set-top-box devices)

* Latecomer unfairness

In the simplest setup [ICCCN] points out the existence of a latecomer 
unfairness problem, that is also discussed in the mailing list.

[GLOBECOM] shows this to be tied to both the protocol dynamics as well 
as measurement errors, proposing simple solution.

[ICCCN,GLOBECOM] however assume FIFO queuing, and it would be 
interesting to see the impact of actually deployed AQM techniques as 
suggested in [ITC22].

[ARXIV] also shows the problem to be exacerbated by backlogged 
transmissions, in the sense that in chunk-by-chunk transmission, the 
time elapsed between consecutive chunks may flush the queue empty (and 
let latecomer correct their base delay estimate).

Interestingly, while [ITC22] observe a latecomer issue, this phenomenon 
is not observed in [ATQR].  [ARXIV] further shows that latecomer 
unfairness also arise on [BT] implementation (depending on the scenario).

* Sensitivity analisis and comparison

[ICCNT] propose a dynamic adjustation of LEDBAT parameters to address 
oscillations of congestion window in  steady state.

[LCN] performs a sensitivity analysis of LEDBAT (to the TARGET and GAIN 
settings) and also relatively compare the level of low-priority of 
LEDBAT, TCP-LP and TCP-NICE, showing LEDBAT to achieve the lowest priority.

A sensitivity to heterogeneous TARGETs settings (i.e., the fact that 
Legacy implementations with higher TARGETs may starve compliant 
implementation) has been pointed out in the mailing list and [ITC22,LCN].

Hence, chosing a single, fixed TARGET value remains an open point.

* References

[BT]
G. Hazel. uTorrent Transport Protocol library. 
http://github.com/bittorrent/libutp, May 2010.

[OPENLEDBAT] 
http://perso.infres.enst.fr/~drossi/index.php?n=Software.LEDBAT

[ITC22]
Joscha Schneider. Joerg Wagner,  Rolf Winter ,  Hans-Joerg Kolbe,
"Out of my Way -- Evaluating Low Extra Delay Background Transport in an 
ADSL Access Network" . In Proceedings of the 22nd International 
Teletraffic Congress (ITC22), Amsterdam, The Netherlands, September 7 - 
9 2010.

[AQTR]
Mugurel Ionut Andreica, Nicolae Tapus, Johan Pouwelse, "Performance 
Evaluation of a Python Implementation of the New LEDBAT Congestion 
Control Algorithm", Proceedings of the IEEE International Conference on 
Automation, Quality and Testing, Robotics (AQTR'10), Romania, 28-30 May, 
2010
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5520827

[IPTPS]
B. Cohen and A. Norberg. "Correcting for clock drift in uTP and
LEDBAT." Invited talk at 9th USENIX International Workshop on
Peer-to-Peer Systems (IPTPS 2010), San Jose, CA, Apr 2010.
http://www.usenix.org/event/iptps10/tech/slides/cohen.pdf

[ICCNT]
A.J. Abu and S. Gordon. "A Dynamic Algorithm for Stabilising
LEDBAT Congestion Window." In 2nd IEEE International Conference on
Computer and Network Technology (ICCNT 2010), Bangkok, Thailand,
Apr 2010.
http://www.computer.org/portal/web/csdl/doi/10.1109/ICCNT.2010.37

[PAM]
D. Rossi, C. Testa and S. Valenti, "Yes, we LEDBAT: Playing with the new 
BitTorrent congestion control algorithm" . In Passive and Active 
Measurement (PAM'10), Zurich, Switzerland, April 2010.
http://www.pam2010.ethz.ch/papers/full-length/4.pdf

[ICCCN]
D. Rossi, C. Testa, S. Valenti and L. Muscariello, "LEDBAT: the new 
BitTorrent congestion control protocol" . In International Conference on 
Computer Communication Networks (ICCCN'10), Zurich, Switzerland, August 
2-5 2010.
http://ieeexplore.ieee.org/iel5/5559661/5560011/05560080.pdf

[LCN]
G. Carofiglio, L. Muscariello, D. Rossi and C. Testa, "A hands-on 
Assessment of Transport Protocols with Lower than Best Effort Priority" 
. In 35th IEEE Conference on Local Computer Networks (LCN'10), Denver, 
CO, USA, October 10-14 2010.
http://arxiv.org/pdf/1006.3017

[GLOBECOM]
G. Carofiglio, L. Muscariello, D. Rossi and S. Valenti, "The quest for 
LEDBAT fairness". In IEEE Globecom'10, Miami, FL, USA, December 6-10 2010.
http://arxiv.org/pdf/1006.3018v1

[ARXIV] G. Carofiglio, L. Muscariello, D. Rossi and S. Valenti,
"Rethinking low extra delay background transport protocols"
http://arxiv.org/abs/1010.5623

-- 
  Oo    Associate Professor
   >     TELECOM ParisTech
  ~     (formerly ENST)

mail:  [email-masked]
phone: +33.1.4581.7563
fax:   +33.1.4581.7158
web:   http://www.enst.fr/~drossi