Ledbat

Introduction

Welcome to our Low Extra Delay Background Transport (LEDBAT) page. LEDBAT is a new experimental congestion control protocol, designed for data transfers with lower than Best Effort priority that is standardized at the IETF. LEDBAT aims at providing a lower-than-best-effort service, yielding to elastic TCP traffic while at the same time efficiently exploiting the available bandwidth. Moreover it tries to introduce just a limited amount of additional delay on the forward path, in order to prevent self-induced congestion and avoid hurting interactive traffic (e.g. VoIP and gaming). We implement LEDBAT as a TCP flavor using the TCP-Linux interface: in this way, (nearly) the same code runs as both a module in the Linux kernel, as well as for the network simulator ns2 . Our code is heavily inspired by the TCP-LP Linux kernel implementation, from which our development started. In this page you will find our open implementation of the LEDBAT congestion control algorithm, as a TCP congestion control flavor (we use the TCP timestamp option to carry the values of the timestamps needed by the protocol to perform its calculations).

If you use the code, please cite it as:

  Dario Rossi, Claudio Testa, Silvio Valenti, Luca Muscariello, 
  LEDBAT: the new BitTorrent congestion control protocol, 
  International Conference on Computer Communications and Networks (ICCCN 2010), Zurich, Switzerland, August, 2010.

and don't hesitate to look at the publication section for other useful references and datasets.

How to setup the LEDBAT module for ns2

Here we provide the ns2 source code of the TCP-LEDBAT implementation of draft v0 (notice that while intermediate draft version changed much from v0, the latest v10 and the RFC are similar to v0). Alternatively, have a look at the kernel implementatio below, that has been updated to draft v9, and that should be straightforward to adapting to ns2 (in which case you may need to follow these instructions).

1. If you have not done it yet, follow these instructions to download and build ns2 .

2. download the source code of our ns2 implementation and save it as tcp_ledbat.c in the directory tcp/linux/src/ under the ns source tree.

3. edit Makefile.in in the ns source directory, adding the new file to the object list

    OBJ_CC = \
    ...
    tcp/linux/src/tcp_ledbat.o \
    ...

4. recompile the simulator

    $ configure
    $ make

5. in your tcl script, include the following lines to create a LEDBAT sender node (cfr. tcp-linux tutorial for more information)

    ...
    set tcp_sender [new Agent/TCP/Linux]
    $tcp_sender set timestamps_ true
    $tcp_sender select_ca ledbat
    ...

How to setup the LEDBAT module for the linux kernel

We have updated the source code of TCP-LEDBAT to version 9 of the draft. Notice that while we have carefully tested the simulation code, the kernel-level code should be regarded as alpha and needs much more testing: any bug reports or patches are welcome!. Please also have a look to our git repository for more updates.

1. Download the code from the git repository containing the module source and the Makefile

2. Follow the instruction in the README file

    tar xvzf ledbat-module.tgz
    cd ledbat-module
    make; make install
    sudo modprobe tcp_ledbat

3. Enable the congestion control for new connections

    sudo sysctl -w net.ipv4.tcp_congestion_control=ledbat

4. If you prefer not to switch all connections to LEDBAT, you can just add it to the allowed congestion control algorithms

   sudo sysctl net.ipv4.tcp_allowed_congestion_control="cubic reno ledbat" 

and then use the server.c and client.c simple programs to test the module (alternatively, later version of iperf let you select the congestion control flavor through the -Z option directly from the command line).

How to configure LEDBAT parameters

The tcp_ledbat module has the following parameters.

base_histo_len
length of the base_history vector, default=6
noise_filter_len
length of the noise_filter vector, default=3
target
TARGET queuing delay, default=25
alpha1
numerator of the GAIN, default=1
alpha2
denominator of the GAIN, default=1
min_impl
select the minimum implementation: default=0
0 use the standart base_histo
1 use the minimum over all ledbat connections
2 use the one-way delay moving average
do_ss
specify wheter to perform slow start: default=0
0 no
1 yes, à la TCP (i.e., setting initial threshold to \infty)
2 yes, using a custom slow-start threshold ledbat_ssthresh to switch to congestion avoidance (i.e. prior that avoiding a loss), default=65000

If, for instance, you want to change the target to 100ms, include this line in your script:

    $tcp_sender set_ca_param ledbat target 100

FAQ

  • The code seems not to follow the draft. You forgot to divide offset by target and cwnd.

Right, the code tries to avoid floating point arithmetic so we used a trick to avoid this calculation. Let's have a look at the code:

    max_cwnd = ((u32) (tp->snd_cwnd))*target;
    [...]
    cwnd = tp->snd_cwnd_cnt + offset;
    tp->snd_cwnd_cnt = cwnd;
    if (ledbat->snd_cwnd_cnt >= max_cwnd) {
        tp->snd_cwnd++;
    }

Basically we use the counter tp->snd_cwnd_cnt to avoid floating point calculation. We increment the congestion window value (tp->snd_cwnd) only when the counter reaches max_cwnd, which is equal to snd_cwnd * target. This means that to increment the congestion window we need at least cwnd packets with a delay of 0, because each of these packets is going to increment the counter of target. This is equivalent to divide offset by cwnd and target.

Contacts

  • Dario Rossi <dario (dot) rossi (at) enst (dot) fr>
  • Claudio Testa <claudio (dot) testa (at) enst (dot) fr>
  • Silvio Valenti <silvio (dot) valenti (at) gmail (dot) com>

Publications

Our work on LEDBAT is based on either experimental measurements [PAM-10],[TMA-12],[TMA-13a],[TMA-13b],[PAM-13],[P2P-12],[P2P-13a] or simulative [ICCCN-10],[LCN-10],[GLOBECOM-10],[CoNEXT-12],[COMNET-13] approaches. Earlier work focused on congestion control perspective from a single flow [PAM-10],[ICCCN-10],[LCN-10],[GLOBECOM-10],[COMNET-13], after which we focused on the impact of LEDBAT from the BitTorrent swarm perspective [P2P-11],[TMA-12],[P2P-13a] and more recently on its impact on bufferbloat [P2P-12],[TMA-13a],[PAM-13] or its interdependence with Active Queue Management techniques [CoNEXT-12],[TMA-13b],[ITC-13]

We pointed out the existence of a latecomer unfairness problem [ICCCN-10], to which we propose some solution in [GLOBECOM-10,COMNET-13]. We further addressed a sensitivity analysis of LEDBAT in [LCN-10] where we also relatively compare the level of low-priority of LEDBAT, TCP-LP and TCP-NICE. Further, [PAM-10] points out that the level of low priority depends on the TCP flavor and settings, and that cross traffic in the reverse path may have an important impact in practice. Finally, notice that LEDBAT manages to achieve a lower-than-best-effort (i.e., lower than TCP) priority only in case of FIFO buffering: our simulative [CoNEXT-12] and experimental [TMA-13b] work shows that in case LEDBAT and TCP share a bottleneck buffer governed by AQM (RED, Choke, CoDel) or scheduling (SFQ, DRR) then they will fairly compete for bottleneck resources. Beside this issue is more general than the LEDBAT case, as it also applies to other lower-than-best-effort protocols such as TCP-NICE and TCP-LP for instance -- so check the LEDBAT+AQM section of this website.

While the latecomer unfairness problem is especially bad in case of backlogged connections (e.g., two competing uploads, backups, FTP-like transfers, etc.) it is less of a problem in case of small-lived or on/off sources [COMNET-13]. As such, performance studies based on simulation [P2P-11] or experiments [TMA-12] have shown LEDBAT to have a good interplay with the BitTorrent swarming protocol. We have extended these results using an experimental methodology in [P2P-13a], considering a wider range of congestion control protocols, including low-priority alternatives to LEDBAT such as NICE and TCP-LP, or other delay-based protocols such as Vegas -- more details are available in the the Lower than Best Effort (LBE) section of this website.

At the same time, while one of the original goals of LEDBAT was to relieve the negative effects of self-induced congestion on the user experience, our work [P2P-12,TMA-13a,PAM-13] show that this problem is only partly solved -- as a single TCP connection, due to BitTorrent or to other applications, can still cause bufferbloat. More precisely, [PAM-13] proposes a methodology to infer the amount of queuing delay of remote peers exploiting the LEDBAT timestamps. We implemented the methodology in a software tool demonstrated at [P2P-12], that we used in a Internet measurement campaign -- more details and datasets in the Bufferbloat section of this website.

  1. [TOMPECS-16] De Cicco, Luca, Gong, Yixi, Rossi, Dario and Leonardi, Emilio , A control theoretic analysis of low-priority congestion controlreprioritization under AQM . ACM Transactions on Modeling and Performance Evaluation of Computer Systems, 1:17:1-17:33, September 2016.
  2. [COMNET-14b] YiXi Gong, Dario Rossi, Claudio Testa, Silvio Valenti and Dave Taht, Fighting the bufferbloat: on the coexistence of AQM and low priority congestion control (extended version) . Computer Networks, 65:255 - 267, 2014.
  3. [GLOBECOM-13] C. Chirichella, D. Rossi, C. Testa, T. Friedman and A. Pescape, Passive bufferbloat measurement exploitingtransport layer information . In IEEE GLOBECOM, December 2013.
  4. [ITC-13] Gong, YiXi, Rossi, Dario and Leonardi, Emilio, Modeling the interdependency of low-prioritycongestion control and active queue management . In The 25th International Teletraffic Congress (ITC25), Runner-up for Best Paper Award, september 2013.
  5. [P2P-13a] C. Testa, D. Rossi, A. Rao and A. Legout, Data Plane Throughput vs Control Plane Delay: Experimental Study ofBitTorrent Performance . In IEEE P2P'XIII, Trento, Italy, September 2013.
  6. [COMNET-13] G. Carofiglio, L. Muscariello, D. Rossi, C. Testa, S. Valenti, Rethinking low extra delay backtround transport protocols . Elsevier Computer Networks, 57:1838-1852, june 2013.
  7. [TMA-13a] C. Chirichella and D. Rossi, To the Moon and back: are Internet bufferbloat delays really that large . In IEEE INFOCOM Workshop on Traffic Measurement and Analysis (TMA'13), Turin, Italy, April 14-19 2013.
  8. [TMA-13b] Y. Gong, D. Rossi, C. Testa, S. Valenti and D. Taht, Fighting the bufferbloat: on the coexistence of AQM and low priority congestion control . In IEEE INFOCOM Workshop on Traffic Measurement and Analysis (TMA'13), Turin, Italy, April 14-19 2013.
  9. [PAM-13] C. Chirichella, D. Rossi, C. Testa, T. Friedman and A. Pescape, Remotely Gauging Upstream Bufferbloat Delays . In Passive and Active Measurement (PAM), Extended Abstract, Hong Kong, China, March 18-19 2013.
  10. [CONEXT-12] Y. Gong, D. Rossi, C. Testa, S. Valenti and D. Taht , Interaction or Interference: can AQM and Low PriorityCongestion Control Successfully Collaborate . In ACM CoNEXT'12 Student Workshop, pages 25-26, December 2012.
  11. [P2P-12] Chiara Chirichella, Dario Rossi, Claudio Testa, Timur Friedman, Antonio Pescapé, Inferring the buffering delay of remote BitTorrent peers under LEDBAT vs TCP . In IEEE P2P'XII, pages 77-78, september 2012.
  12. [TMA-12] C. Testa, D. Rossi, A. Rao and A. Legout, Experimental Assessment of BitTorrent Completion Time in Heterogeneous TCP/uTP swarms . In Traffic Measurement and Analysis (TMA) Workshop at Passive and Active Measurement (PAM), pages 52-56, Wien, AU, March 12-14 2012.
  13. [P2P-11] C. Testa and D. Rossi, The impact of uTP on BitTorrent completion time . In IEEE Peer to Peer (P2P'11), Kyoto, Japan, September 2011.
  14. [LEDBAT-COLUMBIA] D. Rossi, A crash course on LEDBAT, the new BitTorrent congestion control algorithm . Technical report, Talk at Columbia University, 2011.
  15. [PAM-10] 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.
  16. [ICCCN-10] 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.
  17. [LCN-10] 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.
  18. [TECHREP-10] Dario Rossi, C. Testa, S. Valenti, P. Veglia and L. Muscariello, News from the Internet congestion control world . Technical report, Telecom ParisTech, 2010.
  19. [GLOBECOM-10a] 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.
  20. [TECHREP-10b] G. Carofiglio, L. Muscariello, D. Rossi, C. Testa and S. Valenti, Rethinking low extra delay backtround transport protocols . Technical report, Telecom ParisTech, 2010.