RFC 6817

Low Extra Delay Background Transport (LEDBAT)

📅 published December 2012, from ietf

RFC 6817: Low Extra Delay Background Transport (LEDBAT) 🎀

  • Series: Internet Engineering Task Force (IETF) 🌸
  • RFC number: 6817
  • Category: Experimental 🧪
  • Date: December 2012 📅
  • ISSN: 2070-1721
  • Authors: S. Shalunov, G. Hazel (BitTorrent, Inc.), J. Iyengar (Franklin and Marshall College), M. Kuehlewind (University of Stuttgart) 👩‍💻
  • Obsoletes / Updates: The title block doesn't list anything it obsoletes or updates 🙅‍♀️

Abstract 💖

Okay bestie, so LEDBAT (Low Extra Delay Background Transport) is an experimental, delay-based congestion control algorithm. Its whole thing is using the available bandwidth on an end-to-end path while keeping the extra queueing delay on that path from growing too much. ✨ It uses changes in one-way delay measurements to limit the congestion that the flow itself causes in the network.

It's built for background bulk-transfer applications. It's meant to be no more aggressive than standard TCP congestion control (as specified in RFC 5681), and it yields when other flows are competing, so it doesn't mess with their network performance. 🦋

Status of This Memo 📜

This document is not an Internet Standards Track specification. It's published for examination, experimental implementation, and evaluation. 🔬

This document defines an Experimental Protocol for the Internet community. It's a product of the Internet Engineering Task Force (IETF) and represents the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every document the IESG approves is a candidate for any level of Internet Standard. See Section 2 of RFC 5741 for that. 💅

For info on the current status of this document, any errata, and how to give feedback, check http://www.rfc-editor.org/info/rfc6817. 🔗

Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved. 🌈

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as in effect on the date of publication of this document. Please read these carefully, because they describe your rights and restrictions regarding this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they're provided without warranty as described in the Simplified BSD License. ⚖️

Table of Contents 🗂️

   1. Introduction ....................................................4
      1.1. Requirements Notation ......................................4
      1.2. Design Goals ...............................................4
      1.3. Applicability ..............................................5
   2. LEDBAT Congestion Control .......................................6
      2.1. Overview ...................................................6
      2.2. Preliminaries ..............................................6
      2.3. Receiver-Side Operation ....................................7
      2.4. Sender-Side Operation ......................................7
           2.4.1. An Overview .........................................7
           2.4.2. The Complete Sender Algorithm .......................8
      2.5. Parameter Values ..........................................11
   3. Understanding LEDBAT Mechanisms ................................13
      3.1. Delay Estimation ..........................................13
           3.1.1. Estimating Base Delay ..............................13
           3.1.2. Estimating Queueing Delay ..........................13
      3.2. Managing the Congestion Window ............................14
           3.2.1. Window Increase: Probing for More Bandwidth ........14
           3.2.2. Window Decrease: Responding to Congestion ..........14
      3.3. Choosing the Queuing Delay Target .........................15
   4. Discussion .....................................................15
      4.1. Framing and ACK Frequency Considerations ..................15
      4.2. Competing with TCP Flows ..................................15
      4.3. Competing with Non-TCP Flows ..............................16
      4.4. Fairness among LEDBAT Flows ...............................16
   5. Open Areas for Experimentation .................................17
      5.1. Network Effects and Monitoring ............................17
      5.2. Parameter Values ..........................................18
      5.3. Filters ...................................................19
      5.4. Framing ...................................................19
   6. Security Considerations ........................................19
   7. Acknowledgements ...............................................20
   8. References .....................................................20
      8.1. Normative References ......................................20
      8.2. Informative References ....................................20
   Appendix A. Measurement Errors ....................................22
     A.1. Clock Offset ...............................................22
     A.2. Clock Skew .................................................22

1. Introduction ✨

Okay so TCP congestion control [RFC5681] is the big one. It tries to share bandwidth at a bottleneck link fairly among the flows competing there, and it's the main congestion control mechanism on the Internet. 🌐 But not every app wants a fair share! 🙈 "Background" apps, like software updates or file sharing, want to run without getting in the way of "foreground" apps that are more interactive or sensitive to delay and/or bandwidth. Standard TCP congestion control, as specified in [RFC5681], may be too aggressive for those background apps. 😬

So LEDBAT is an experimental, delay-based congestion control mechanism that reacts early to congestion in the network. That lets "background" apps use the network without interfering with competing flows. 🦋 A LEDBAT sender uses one-way delay measurements to estimate how much queueing is on the data path. It controls the LEDBAT flow's congestion window based on that estimate, and it minimizes interference with competing flows by adding only a little extra queueing delay on the end-to-end path. 🫶

Delay-based congestion control protocols, like TCP-Vegas [Bra94][Low02], are generally designed to get more throughput than standard TCP, not less, and they often beat TCP in particular network settings. 🏆 For more on Lower-than-Best-Effort transport protocols, see [RFC6297]. LEDBAT is different: it's designed to be no more aggressive than TCP [RFC5681]. It's a "scavenger" congestion control mechanism, which means it tries to use all the available bandwidth but yields quickly when it's competing with standard TCP at a bottleneck link. 🧹💜

In the rest of this document, "standard TCP" refers to the congestion control specified in [RFC5681]. 📖

1.1. Requirements Notation 📝

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 🔑

1.2. Design Goals 🎯

LEDBAT congestion control is going for these goals:

  1. to use end-to-end available bandwidth and keep queueing delay low when no other traffic is present, 🌸
  2. to add limited queuing delay on top of what concurrent flows cause, and 💅
  3. to yield quickly to standard TCP flows that share the same bottleneck link. 🙌

1.3. Applicability 🧚

LEDBAT is a "scavenger" congestion control mechanism. It's mainly motivated by background bulk-transfer apps, like large file transfers (think file sharing) and software updates. 📦 It can be used with any app that wants to minimize its impact on the network and on other interactive, delay- and/or bandwidth-sensitive network apps. LEDBAT is expected to work well when the sender and/or receiver is connected through a residential access network. 🏠

LEDBAT can be used as part of a transport protocol or as part of an application, as long as the data transmission mechanisms can carry timestamps and acknowledge data frequently. 🕰️ It can be used with TCP, Stream Control Transmission Protocol (SCTP), and Datagram Congestion Control Protocol (DCCP), with appropriate extensions where needed. It can also be used with proprietary application protocols, like the ones built on top of UDP for peer-to-peer (P2P) applications. 🤝

When it's used with an ECN-capable framing protocol, LEDBAT should react to an Explicit Congestion Notification (ECN) mark the same way it would react to a loss, as specified in [RFC3168]. 🚩

LEDBAT is designed to reduce the buildup of a standing queue by long-lived LEDBAT flows at a link with a tail-drop FIFO queue. That way it avoids persistently delaying other flows that share the queue. 🛑 But if Active Queue Management (AQM) is configured to drop or ECN-mark packets before the LEDBAT flow starts reacting to persistent queue buildup, LEDBAT reverts to standard TCP behavior instead of yielding to other TCP flows. ⚠️ Even so, that kind of AQM is still desirable, since it keeps queuing delay low, which lines up with LEDBAT's goals. ✅ On top of that, a LEDBAT transport that supports ECN gets the same advantages an ECN-capable TCP has over an ECN-agnostic TCP: avoiding losses and possible retransmissions. 🎉

Weighted Fair Queuing (WFQ), which some home gateways use, tries to isolate and protect delay-sensitive flows from delays caused by standing queues built up by concurrent long-lived flows. 🛡️ So while it stops LEDBAT from yielding to other TCP flows, it again gets an outcome that matches LEDBAT's goals [Sch10]. 💖

2. LEDBAT Congestion Control 🌷

2.1. Overview 🔍

A standard TCP sender keeps increasing its congestion window until a loss occurs [RFC5681] or an ECN mark is received [RFC3168]. Without link errors in the network, that only happens when the queue at the bottleneck link on the end-to-end path overflows or when an AQM is applied. 📈 Packet loss or marking at the bottleneck link is expected to be preceded by an increase in queueing delay there. So LEDBAT uses that rise in queueing delay as an early signal of congestion. That lets it respond to congestion sooner than standard TCP and yield bandwidth to a competing TCP flow. 👑

LEDBAT uses one-way delay measurements to estimate queueing delay. When the estimated queueing delay is less than a predetermined target, LEDBAT infers that the network isn't congested yet, and it increases its sending rate to use any spare capacity in the network. 🚀 When the estimated queueing delay goes above the predetermined target, LEDBAT decreases its sending rate in response to potential congestion in the network. 🫧

2.2. Preliminaries 🎀

okay so a LEDBAT sender uses a congestion window (cwnd) to gate how much data it can push into the network in one round-trip time (RTT) 💅 A sender MAY maintain its cwnd in bytes or in packets, but this document uses cwnd in bytes. LEDBAT requires that each data segment carries a "timestamp" from the sender. The receiver uses that to compute the one-way delay from the sender, then sends the computed value back to the sender 🦋

bestie, there's also a slow start mechanism that can be used as specified in [RFC5681] ✨ Slow start makes the window grow faster than LEDBAT does, so conservative congestion control implementations that use LEDBAT may skip slow start altogether and start with an initial window of INIT_CWND * MSS 🌸 (INIT_CWND is described later in Section 2.5.)

"MSS" means the sender's Maximum Segment Size, which is the size of the largest segment the sender can transmit 🧚 The value of MSS can be based on the path MTU discovery [RFC4821] algorithm and/or on other factors.

2.3. Receiver-Side Operation 🫶

the receiver is the one doing the math here! 🧮 A LEDBAT receiver calculates the one-way delay from the sender to itself, using its own system time and the timestamps in the data packets it gets. Then it feeds that computed one-way delay back to the sender in the next acknowledgement. Here's how a LEDBAT receiver operates:

on data_packet:
    remote_timestamp = data_packet.timestamp
    acknowledgement.delay = local_timestamp() - remote_timestamp
    # fill in other fields of acknowledgement
    acknowledgement.send()

so a receiver is allowed to wait before sending an ACK, and it can combine acknowledgements for more than one data packet into a single ACK packet, the same way delayed ACKs work in standard TCP, for example 🎀 When it does this, the receiver MAY bundle all the delay samples into one ACK packet, and it MUST transmit the samples in the order generated 💖 When several delay samples are bundled into one ACK, the sender applies them all at once during its cwnd adjustment (more on that in the next section) 👑 The sender's adjustment can be sensitive to the order the samples are applied in, so the computed delay samples should be available to the sender in the order they were generated at the receiver 🌈

2.4. Sender-Side Operation 🔥

2.4.1. An Overview 🦋

this is the first-pass version of how a LEDBAT sender works, and the full algorithm comes later in Section 2.4.2 ✨ TARGET is the maximum queueing delay that LEDBAT itself may introduce into the network, and GAIN controls how fast the cwnd responds to changes in queueing delay. Both constants get specified later 🍓 off_target is a normalized value showing the difference between the measured current queueing delay and the predetermined TARGET delay. It can be positive or negative, so cwnd can increase or decrease in proportion to off_target 🙈

on initialization:
    base_delay = +INFINITY

on acknowledgement:
    current_delay = acknowledgement.delay
    base_delay = min(base_delay, current_delay)
    queuing_delay = current_delay - base_delay
    off_target = (TARGET - queuing_delay) / TARGET
    cwnd += GAIN * off_target * bytes_newly_acked * MSS / cwnd

this simplified version ignores multiple delay samples in an acknowledgement, noise filtering, base delay expiration, and sender idle times 😭 Don't worry, the complete sender algorithm below handles all of those ✨

2.4.2. The Complete Sender Algorithm 💜

update_current_delay() keeps a list of one-way delay measurements, and a filtered value from that list is used as an estimate of the current end-to-end delay 💅 update_base_delay() keeps a list of one-way delay minima over a number of one-minute intervals, which tracks changes in the base delay of the end-to-end path 🌸 Both lists are maintained per LEDBAT flow.

We note this algorithm assumes that slight random fluctuations exist in inter-packet arrival times at the bottleneck queue, so a LEDBAT sender can correctly measure the base delay 🧠 See Section 4.4 for a more complete discussion.

The full sender-side algorithm is below, bestie 👑

on initialization:
    # cwnd is the amount of data that is allowed to be
    # outstanding in an RTT and is defined in bytes.
    # CTO is the congestion timeout value.

    create current_delays list with CURRENT_FILTER elements
    create base_delays list with BASE_HISTORY number of elements
    initialize elements in base_delays to +INFINITY
    initialize elements in current_delays according to FILTER()
    last_rollover = -INFINITY # More than a minute in the past
    flightsize = 0
    cwnd = INIT_CWND * MSS
    CTO = 1 second

on acknowledgement:
    # flightsize is the amount of data outstanding before this ACK
    #    was received and is updated later;
    # bytes_newly_acked is the number of bytes that this ACK
    #    newly acknowledges, and it MAY be set to MSS.

    for each delay sample in the acknowledgement:
        delay = acknowledgement.delay
        update_base_delay(delay)
        update_current_delay(delay)

    queuing_delay = FILTER(current_delays) - MIN(base_delays)
    off_target = (TARGET - queuing_delay) / TARGET
    cwnd += GAIN * off_target * bytes_newly_acked * MSS / cwnd
    max_allowed_cwnd = flightsize + ALLOWED_INCREASE * MSS
    cwnd = min(cwnd, max_allowed_cwnd)
    cwnd = max(cwnd, MIN_CWND * MSS)
    flightsize = flightsize - bytes_newly_acked
    update_CTO()

on data loss:
    # at most once per RTT
    cwnd = min (cwnd, max (cwnd/2, MIN_CWND * MSS))
    if data lost is not to be retransmitted:
        flightsize = flightsize - bytes_not_to_be_retransmitted

if no ACKs are received within a CTO:
    # extreme congestion, or significant RTT change.
    # set cwnd to 1MSS and backoff the congestion timer.
    cwnd = 1 * MSS
    CTO = 2 * CTO

the update_CTO() piece is an RTT estimation mechanism that uses data transmission times and ACK reception times, and it's what powers the congestion timeout (CTO) ⏱️

update_CTO()
    # implements an RTT estimation mechanism using data
    # transmission times and ACK reception times,
    # which is used to implement a congestion timeout (CTO).
    # If implementing LEDBAT in TCP, sender SHOULD use
    # mechanisms described in RFC 6298 [RFC6298],
    # and the CTO would be the same as the retransmission timeout (RTO).

and here are the helper functions 🫧

update_current_delay(delay)
    # Maintain a list of CURRENT_FILTER last delays observed.
    delete first item in current_delays list
    append delay to current_delays list

update_base_delay(delay)
    # Maintain BASE_HISTORY delay-minima.
    # Each minimum is measured over a period of a minute.
    # 'now' is the current system time
    if round_to_minute(now) != round_to_minute(last_rollover)
        last_rollover = now
        delete first item in base_delays list
        append delay to base_delays list
    else
        base_delays.tail = MIN(base_delays.tail, delay)

the LEDBAT sender tries to pull the actual delay estimate out of the current_delay samples by running FILTER() to get rid of any outliers 🧹 Different types of filters MAY be used for FILTER(). A NULL filter, which doesn't filter at all, is a reasonable candidate too, since LEDBAT's linear controller for cwnd increase and decrease may let it recover quickly from errors caused by bad samples 🌟 Another option is the exponentially weighted moving average (EWMA) function, with weights that let it track changing network delay agilely 🦋 A simple MIN filter over a small window (much smaller than BASE_HISTORY) may also be robust against large delay peaks, like the ones delayed ACKs in TCP can cause 🍓 Care should be taken that the filter stays robust to noise while remaining sensitive to persistent congestion signals 💀

We note that when multiple delay samples are bundled within a single ACK, the sender's resulting cwnd may be slightly different than when the samples come in separate ACKs 🙈 The cwnd is adjusted based on the total number of bytes ACKed and the final filtered value of queueing_delay, no matter how many delay samples are in an ACK 💜

to get an approximate minimum over the past few minutes, a LEDBAT sender stores BASE_HISTORY separate minima, one each for the last BASE_HISTORY-1 minutes, plus one for the running current minute 🕰️ At the end of the current minute, the window moves: the earliest minimum is dropped and the latest one is added. If the connection is idle for a given minute, there's no data for the one-way delay, so a value of +INFINITY has to be stored in the list. If the connection has been idle for BASE_HISTORY minutes, all the minima in the list are set to +INFINITY and measurement starts over fresh ✨ So LEDBAT requires that during idle periods, an implementation must maintain the base delay list 🫶

LEDBAT also restricts cwnd growth after a period of inactivity 🎀 When the sender is application-limited, its cwnd gets clamped down using max_allowed_cwnd to a little more than flightsize. To be TCP-friendly, LEDBAT halves its cwnd on data loss 💖

LEDBAT uses a congestion timeout (CTO) to avoid transmitting data during periods of heavy congestion and to avoid congestion collapse. A CTO detects heavy congestion, indicated by loss of all outstanding data or acknowledgements, and when it fires, cwnd drops to 1 MSS and the CTO interval backs off exponentially 😭

that backoff of the CTO value stops the sender from sending more data into an overloaded queue, and it also lets the sender cope with sudden changes in the RTT of the path 🌈 A CTO works similarly to a retransmission timeout (RTO) in TCP [RFC6298], but since LEDBAT separates reliability from congestion control, a retransmission doesn't need to be triggered by a CTO. LEDBAT does not preclude a CTO from triggering retransmissions, though. That could be the case if LEDBAT congestion control were used with TCP framing and reliability 🧚

the CTO is a gating mechanism that makes sure the sending rate backs off exponentially under heavy congestion, and it may be implemented with or without a timer 🦋 An implementation that avoids timers may consider using a "next-time-to-send" variable, set based on the CTO, to control the earliest time a sender may transmit without receiving any ACKs 🍓 A maximum value MAY be placed on the CTO, and if one is placed, it MUST be at least 60 seconds 🔥

2.5. Parameter Values ✨

Okay bestie, so TARGET MUST be 100 milliseconds or less, and I explain why that number makes sense in Section 3.3 🎯. Using the same TARGET across LEDBAT flows is what keeps the sharing fair for everyone 🫶. A flow with a higher TARGET than its competing LEDBAT flows might grab a bigger slice of the bottleneck bandwidth 👑. So if you want one LEDBAT flow to outrank another, give the higher-priority one a higher TARGET value 💅.

ALLOWED_INCREASE SHOULD be 1, and it MUST be greater than 0 🌸. An ALLOWED_INCREASE of 0 means the cwnd doesn't grow at all 🙈. An ALLOWED_INCREASE of 1 lets the cwnd increase based on the flightsize from the previous RTT, and it also caps that increase ✨. An ALLOWED_INCREASE greater than 1 MAY be used, but only when the interaction between LEDBAT and the framing protocol gives a clear reason for it 🧚.

GAIN MUST be set to 1 or less 💖. A GAIN of 1 keeps the maximum cwnd ramp-up at the same rate as TCP Reno in Congestion Avoidance 🦋. This document uses the same GAIN for both the cwnd increase (when off_target is greater than zero) and the decrease (when off_target is less than zero). Implementations MAY use a higher GAIN for the decrease than for the increase, and here's why 👀. When a competing non-LEDBAT flow ramps up its sending rate, the LEDBAT sender might only notice a little extra delay, so it backs off slowly 🐢. To make sure a competing non-LEDBAT flow isn't hurt, the LEDBAT flow should decrease its sending rate at least as quickly as that competing flow increases its rate 🫶. A higher decrease-GAIN MAY be used so the LEDBAT flow can drop its rate faster than the competing flow's increase rate 🔥.

The size of the base_delays list, BASE_HISTORY, SHOULD be 10 🍓. If the actual base delay goes down (say, because of a route change), a LEDBAT sender adapts right away, no matter what BASE_HISTORY is 🚀. If the actual base delay goes up, though, a LEDBAT sender takes BASE_HISTORY minutes to catch up, and in the meantime it might wrongly think there's a bit more extra delay than intended (TARGET) 😭. So BASE_HISTORY is a trade-off: a higher value can give a more accurate measurement when the base delay isn't changing, while a lower value reacts faster to a real increase in base delay ⚖️.

A LEDBAT sender uses the current_delays list to keep only the delay measurements made within the last RTT 🕰️. That's how it filters out noise spikes in its measurement of the current one-way delay through the network 🧹. The size of this list, CURRENT_FILTER, can vary. It depends on the FILTER() function and on how many successful measurements were made within the last RTT 🎀. The sender should aim to collect enough delay samples in each RTT to feel statistically confident in its measurements 📊. How many samples count as "confident" depends on the network conditions, but the sender SHOULD use at least 4 delay samples in each RTT, unless a small congestion window means fewer samples are available 💜. The value of CURRENT_FILTER depends on the filter being used, but CURRENT_FILTER MUST be limited so that the samples in the list are never older than an RTT 🙌.

INIT_CWND and MIN_CWND SHOULD both be 2 🌈. An INIT_CWND of 2 helps seed FILTER() at the sender when there are no samples at the start of a flow 🌱. A MIN_CWND of 2 lets FILTER() use more than a single instantaneous delay estimate without getting too aggressive 🛡️. Slight deviations may be warranted, for example, when these INIT_CWND and MIN_CWND values interact poorly with the framing protocol 🤷‍♀️. However, INIT_CWND and MIN_CWND MUST be no larger than the corresponding values specified for TCP [RFC5681] 💅.

3. Understanding LEDBAT Mechanisms 🧠

This section breaks down the delay estimation and window management mechanisms that LEDBAT uses 🦋.

3.1. Delay Estimation

LEDBAT estimates congestion in the direction the data is flowing 🚚. To avoid measuring extra delay from things like queue buildup on the reverse path (the ACK path) or reordering, LEDBAT uses one-way delay estimates 🙅‍♀️. LEDBAT assumes the measurements are done with data packets. That means no separate measurement packets are needed, and there's no risk of measurement packets being treated differently from the data packets in the network 🫶.

End-to-end delay can be broken down into transmission (or serialization) delay, propagation (or speed-of-light) delay, queueing delay, and processing delay ⏱️. On any given path, barring some noise, every delay component except queueing delay stays constant 🧊. So to spot an increase in queueing delay in the network, a LEDBAT sender separates the queueing delay from the rest of the end-to-end delay, as described below 🔍.

3.1.1. Estimating Base Delay

Queuing delay is always added on top of the end-to-end delay, so LEDBAT estimates the sum of the constant delay components (which it calls "base delay") as the minimum delay observed on the end-to-end path 📉.

To respond to real changes in the base delay, like the ones a route change can cause, LEDBAT only uses recent measurements when estimating the base delay 🗺️. The length of the observation window is a trade-off between robustness and responsiveness 🎢. A bigger window makes it more likely that the true base delay gets detected (as long as the true base delay hasn't changed) 💪. A smaller window reacts faster to real changes in the base delay ⚡.

3.1.2. Estimating Queueing Delay

As long as the base delay is constant (no route changes), the queueing delay is the variable part of the measured end-to-end delay 🌊. LEDBAT measures queueing delay as just the difference between an end-to-end delay measurement and the current base delay estimate 🧮. The queueing delay should be filtered (depending on the usage scenario) to get rid of noise in the delay estimation, like spikes in processing delay at a node on the path 🧽.

3.2. Managing the Congestion Window

LEDBAT uses a simple linear controller to set the sending rate as a function of the delay estimate 📐. The sender's response is proportional to the difference between the current queueing delay estimate and the target 🎯.

3.2.1. Window Increase: Probing for More Bandwidth

When the queuing delay is smaller than the delay target, which is set by the TARGET parameter in this document, a LEDBAT sender increases its congestion window in proportion to the relative difference between the current queueing delay and the delay target 📈. As the current queuing delay gets closer to TARGET, LEDBAT's window growth slows down 🐌. To compete fairly with concurrent TCP flows, the fastest LEDBAT window growth (when the current queueing delay estimate is zero) is set to match TCP's: an increase of one packet per RTT 🤝. In other words, a LEDBAT flow never ramps up faster than a competing TCP flow over the same path 💅. The TARGET value sets the maximum extra queuing delay that LEDBAT will cause 🛑. If the current queuing delay equals the TARGET value, LEDBAT tries to keep that extra delay steady 🫶.

3.2.2. Window Decrease: Responding to Congestion

When a sender's queueing delay estimate is higher than the target, the LEDBAT flow's rate should be reduced 📉. LEDBAT's linear controller lets the sender decrease the window in proportion to the difference between the target and the current queueing delay ⚖️.

Unlike loss-based TCP congestion control, LEDBAT tries to avoid losses, so a LEDBAT sender isn't expected to normally rely on losses to set its sending rate 🙅‍♀️. But when data loss does happen, LEDBAT must respond the way standard TCP does. Even if the queueing delay estimates say otherwise, a loss is treated as a strong sign of congestion 🚨. So to deal with severe congestion when packets are dropped in the network, and to have a fallback in case the queuing delay estimates are wrong, a LEDBAT sender halves its congestion window whenever a loss event is detected 🪓. Just like TCP New-Reno, LEDBAT reduces its cwnd by half at most once per RTT 🫡.

3.3. Choosing the Queuing Delay Target

The International Telecommunication Union's (ITU's) Recommendation G.114 says a one-way delay of 150 ms is acceptable for most user voice applications [g114] ☎️. So the delay LEDBAT induces must be well below 150 ms, so it doesn't hurt delay-sensitive traffic sharing the same bottleneck queue 🎤. A target that's too low, on the other hand, makes the sender's algorithm more sensitive to noise in the one-way delays and in the delay measurement process 😵‍💫. That can lead to reduced throughput for the LEDBAT flow and under-utilization of the bottleneck link 📉.

Our recommendation of 100 ms or less as the target is a trade-off between these considerations ⚖️. The anecdotal evidence says this value works well 🍀. LEDBAT has been implemented and successfully deployed with a target value of 100 ms in two BitTorrent implementations: as the exclusive congestion control mechanism in BitTorrent Delivery Network Accelerator (DNA), and as an experimental mechanism in uTorrent [uTorrent] 🎉.

4. Discussion 💬

4.1. Framing and ACK Frequency Considerations

The actual framing and wire format of the protocols that use LEDBAT are outside the scope of this document 📦. We still briefly look at the data framing and ACK frequency needs of LEDBAT mechanisms 🔎.

To compute the one-way delay of the data path, this discussion assumes a framing that lets the sender timestamp packets, and lets the receiver send the measured one-way delay back to the sender in ACK packets ⏰. LEDBAT doesn't require this particular method, but it does require unambiguous delay estimates using data and ACK packets 🧩.

A LEDBAT receiver may send an ACK as often as one for every data packet received, or less often. But LEDBAT does require that the receiver MUST transmit at least one ACK in every RTT 💌.

4.2. Competing with TCP Flows

LEDBAT is designed to respond to congestion indications earlier than loss-based standard TCP [RFC5681] 🏃‍♀️. A LEDBAT flow gets more aggressive as its queueing delay estimate gets lower. Since the queueing delay estimate is non-negative, LEDBAT is most aggressive when the queueing delay estimate is zero 😤. In that case, LEDBAT ramps up its congestion window at the same rate as standard TCP [RFC5681] 🚀. LEDBAT may reduce its rate earlier than standard TCP, and it always halves its congestion window on loss 🪟. So in the worst case, where the delay estimates are completely and consistently off, a LEDBAT flow falls back to standard TCP behavior and is no more aggressive than standard TCP [RFC5681] 🫶✨.

4.3. Competing with Non-TCP Flows 🎀

okay so LEDBAT yields to all high-load flows, both TCP and non-TCP, but it may not yield to low-load, latency-sensitive traffic that doesn't cause a measurable delay at the bottleneck queue, like Voice over IP (VoIP) 📞. Those flows will still feel extra delay from any concurrent LEDBAT flows, but the TARGET delay puts a limit on the total extra delay that all the LEDBAT flows can cause together 💅. If TARGET is higher than what the bottleneck queue can sustain, the LEDBAT flows should experience loss and fall back to standard loss-based TCP behavior 💀. So in the worst case, LEDBAT adds no more latency than standard TCP when it's competing with non-TCP flows ✨. In the common case though, we expect LEDBAT flows to add TARGET amount of delay, which ought to be within the delay tolerance for most latency-sensitive apps, VoIP included 🫶.

4.4. Fairness among LEDBAT Flows 👑

The primary design goals of LEDBAT are all about how the flows act together when they're up against standard TCP 🌸. Since LEDBAT is built for background traffic, we think link utilization matters more than fairness between LEDBAT flows 💜. Still, let's look at the fairness stuff that can pop up between competing LEDBAT flows 👀.

LEDBAT as described so far doesn't have a mechanism made specifically to even out utilization among LEDBAT flows 🙈. Anecdotally, existing implementations seem to get a rough equalization anyway, since in most environments there's some randomness in inter-packet transmission times, as explained further below 🦋.

Delay-based congestion control systems have a problem: latecomers can wrongly measure and use a higher base delay than an active flow that started earlier 😭. Picture a bottleneck saturated by a single LEDBAT flow, so that flow keeps the bottleneck queue at TARGET delay. When a new LEDBAT flow arrives, it might accidentally include that steady queueing delay in its measurement of the base delay on the path 🍓. The new flow now has an inflated base delay estimate, so it may build on top of the existing, already maximal, queueing delay. As the latecomer builds up, the old flow sees the true queueing delay and backs off, while the latecomer keeps building and uses up the entire link's capacity, effectively shutting the old flow out 🥺. This is called the "latecomer's advantage" 💅.

In the worst case, if the first flow yields at the same rate the new flow increases its sending rate, the new flow sees constant end-to-end delay, which it assumes is the base delay, until the first flow backs off completely. As a result, by the time the second flow stops increasing its cwnd, it would have added twice the target queueing delay to the network 😱.

This advantage can be reduced if the first flow yields and empties the bottleneck queue faster than the incoming flow increases its occupancy in the queue. In that case, the latecomer might measure correctly a delay that is closer to the base delay ✨. While a multiplicative decrease of the congestion window might achieve that, it may cause strong fluctuations in flow throughput during the flow's steady state, so we're not into it 🙅. Thus, we do not recommend a multiplicative decrease scheme 🚫.

We note that in certain use-case scenarios, it is possible for a later LEDBAT flow to gain an unfair advantage over an existing one [Car10]. In practice, this concern ought to be alleviated by the burstiness of network traffic: all that's needed to measure the base delay is one small gap in transmission schedules between the LEDBAT flows 🌈. These gaps can occur for a number of reasons, such as latency introduced by application sending patterns, OS scheduling at the sender, processing delay at the sender or any network node, and link contention 🧚. When such a gap occurs in the first sender's transmission while the latecomer is starting, base delay is immediately and correctly measured 💖. With a small number of LEDBAT flows, system noise may sufficiently regulate the latecomer's advantage 🫧.

5. Open Areas for Experimentation 🧪

We now outline some areas that need experimentation in the Internet and under different network scenarios. These experiments should help the community understand LEDBAT's dynamics and should help towards further standardization of LEDBAT and LEDBAT-related documents 🔬.

5.1. Network Effects and Monitoring 📡

Further study is required to fully understand the behavior and convergence properties of LEDBAT in networks with non-tail-drop, non-FIFO queues, in networks with frequent route changes, and in networks with network-level load balancing 🌀. These studies should have two broad goals: (i) to understand the effects of different network mechanisms on LEDBAT, and (ii) to understand the impact of LEDBAT on the network 💫.

Network mechanisms and dynamics can influence LEDBAT flows in unintended ways 😬. For instance, frequent route changes that result in increasing base delays may, in the worst case, throttle a LEDBAT flow's throughput significantly. The influence of different network traffic management mechanisms on LEDBAT throughput should be studied 📉.

An increasing number of LEDBAT flows in the network will likely result in operator-visible network effects as well, and these should thus be studied 👀. For instance, as long as the bottleneck queue in a network is larger than TARGET (in terms of delay), we expect that both the average queueing delay and loss rate in the network should reduce as LEDBAT traffic increasingly dominates the traffic mix in the network 📊. Note that for bottleneck queues that are smaller than TARGET, LEDBAT will appear to behave very similarly to standard TCP, and its flow-level behavior may not be distinguishable from that of standard TCP 🤷‍♀️.

We note that a network operator may be able to verify the operation of a LEDBAT flow by monitoring per-flow behavior and queues in the network. When the queueing delay at a bottleneck queue is above TARGET as specified in this document, LEDBAT flows should be expected to back off and reduce their sending rate 🦋.

5.2. Parameter Values 🎛️

The throughput and response of LEDBAT to the proposed parameter values of TARGET, decrease-GAIN, BASE_HISTORY, INIT_CWND, and MIN_CWND should be evaluated with different types of competing traffic in different network settings, including with different AQM schemes at the bottleneck queue 🧁. TARGET controls LEDBAT's added latency, while decrease-GAIN controls LEDBAT's response to competing traffic. Since LEDBAT is intended to be minimally intrusive to competing traffic, the impact of TARGET and decrease-GAIN on delay-sensitive traffic should be studied 🫶. TARGET also impacts the growth rate of the congestion window when off_target is smaller than 1. This impact of TARGET on the rate of cwnd growth should be studied 🌱. The amount of history maintained by the base delay estimator, BASE_HISTORY, influences the responsiveness of LEDBAT to changing network conditions. LEDBAT's responsiveness and throughput should be evaluated in the wide area and under conditions where abrupt changes in base delay might occur, such as with route changes and with cellular handovers 📶. The impact and efficacy of these parameters should be carefully studied with tests over the Internet 🌍.

5.3. Filters 🧹

LEDBAT's effectiveness depends on a sender's ability to accurately estimate end-to-end queueing delay from delay samples 🎯. Consequently, the filtering algorithm used for this estimation, FILTER(), is an important candidate for experiments. This document suggests the use of NULL, EWMA, and MIN filters for estimating the current delay; the efficacy of these and other possible filters for this estimate should be investigated 🔍. FILTER() may also impact cwnd dynamics when delay samples are bundled in ACKs, since cwnd adaption is done once per ACK irrespective of the number of delay samples in the ACK 🎀. This impact should be studied when the different filters are considered 💅.

5.4. Framing 🖼️

This document defines only a congestion control algorithm and assumes that framing mechanisms for exchanging delay information exist within the protocol in which LEDBAT is being implemented 📦. If implemented in a new protocol, both the sender and receiver may be LEDBAT-aware. But if implemented in an existing protocol that is capable of providing one-way delay information, LEDBAT may be implemented as a sender-side-only modification 🛠️. In either case, the parent protocol may interact with LEDBAT's algorithms. For instance, the rate of ACK feedback to the data sender may be dictated by other protocol parameters, but will interact with the LEDBAT flow's dynamics 🔄. Careful experimentation is necessary to understand and integrate LEDBAT into both new and existing protocols 🧪✨.

6. Security Considerations 🔐

LEDBAT's aggressiveness is contingent on the delay estimates and on the TARGET delay value 🚨. If these parameter values at the sender are compromised such that delay estimates are artificially set to zero and the TARGET delay value is set to +INFINITY, the LEDBAT algorithm deteriorates to TCP-like behavior 😱. Thus, while LEDBAT is sensitive to these parameters, the algorithm is fundamentally limited in the worst case to be as aggressive as standard TCP 🛡️.

A man in the middle may be able to change queueing delay on a network path, and/or modify the timestamps transmitted by a LEDBAT sender, and/or modify the delays reported by a LEDBAT receiver, thus causing a LEDBAT flow to back off even when there's no congestion 👿. A protocol using LEDBAT ought to minimize the risk of such man-in-the-middle attacks by at least authenticating the timestamp field in the data packets and the delay field in the ACK packets 🔒.

LEDBAT is not known to introduce any new concerns with privacy, integrity, or other security issues for flows that use it 🫧. LEDBAT is compatible with use of IPsec and Transport Layer Security (TLS) / Datagram Transport Layer Security (DTLS) 🌸.

7. Acknowledgements 💌

We thank folks in the LEDBAT working group for their comments and feedback 🥰. Special thanks to Murari Sridharan and Rolf Winter for their patient and untiring shepherding 👑🫶.

8. References 📚

8.1. Normative References 📖

[RFC2119]   Bradner, S., "Key words for use in RFCs to Indicate
            Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC3168]   Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
            of Explicit Congestion Notification (ECN) to IP",
            RFC 3168, September 2001.

[RFC4821]   Mathis, M. and J. Heffner, "Packetization Layer Path MTU
            Discovery", RFC 4821, March 2007.

[RFC5681]   Allman, M., Paxson, V., and E. Blanton, "TCP Congestion
            Control", RFC 5681, September 2009.

[RFC6298]   Paxson, V., Allman, M., Chu, J., and M. Sargent,
            "Computing TCP's Retransmission Timer", RFC 6298,
            June 2011.

8.2. Informative References ✨

okay bestie, here's the informative reference list, which is basically the "further reading" stash 📚🎀 Everything is listed exactly as the RFC has it, so you can dig into any of these 🔍

[Bra94]     Brakmo, L., O'Malley, S., and L. Peterson, "TCP Vegas:
            New techniques for congestion detection and avoidance",
            Proceedings of SIGCOMM '94, pages 24-35, August 1994.

[Car10]     Carofiglio, G., Muscariello, L., Rossi, D., Testa, C.,
            and S. Valenti, "Rethinking Low Extra Delay Background
            Transport Protocols", October 2010,
            <http://arxiv.org/abs/1010.5623v1>.

[Low02]     Low, S., Peterson, L., and L. Wang, "Understanding TCP
            Vegas: A Duality Model", JACM 49 (2), March 2002.

[RFC5905]   Mills, D., Martin, J., Burbank, J., and W. Kasch,
            "Network Time Protocol Version 4: Protocol and Algorithms
            Specification", RFC 5905, June 2010.

[RFC6297]   Welzl, M. and D. Ros, "A Survey of Lower-than-Best-Effort
            Transport Protocols", RFC 6297, June 2011.

[Sch10]     Schneider, J., Wagner, J., Winter, R., and H. Kolbe, "Out
            of my Way -- Evaluating Low Extra Delay Background
            Transport in an ADSL Access Network", Proceedings of 22nd
            International Teletraffic Congress (ITC22), September
            2010.

[g114]      "SERIES G: TRANSMISSION SYSTEMS AND MEDIA, DIGITAL
            SYSTEMS AND NETWORKS; International telephone connections
            and circuits - General; Recommendations on the
            transmission quality for an entire international
            telephone connection; One-way transmission time", ITU-T
            Recommendation G.114, 05/2003.

[uTorrent]  Hazel, G., "uTorrent Transport Protocol library",
            July 2012, <http://github.com/bittorrent/libutp>.

Appendix A. Measurement Errors ✨

okay this appendix is my favourite nerdy bit 🧚💜 LEDBAT measures one-way delays, so anything wrong with a timestamp can sneak into the numbers. We're going to look at the two main timestamp gremlins. We use the same locally linear clock model and the same terminology as Network Time Protocol (NTP) [RFC5905]. NTP calls the difference between measured time and true time the "offset", and the difference of clock rate from the true rate the "skew". So a clock has two errors: a fixed offset from true time, and a skew. Let's see how each one hits LEDBAT 👀

A.1. Clock Offset

the offset of the clocks, both the sender's and the receiver's, shows up as a fixed error in LEDBAT's one-way delay measurement 🕰️ The offset in the measured one-way delay is just the difference between the receiver's and the sender's clock offsets. BUT LEDBAT doesn't use that estimate directly. It uses the difference between the measured one-way delay and a measured base delay. Since the offset error is the same in both the measured one-way delay and the base delay, the offsets cancel each other out in the queuing delay estimate, which is what LEDBAT uses for its window computations. So clock offset error has no impact on LEDBAT. iconic, honestly 💅

A.2. Clock Skew

clock skew usually shows up as a linearly changing error in a time estimate 📈 Like offset, the skew of LEDBAT's one-way delay estimate is the difference between the two clocks' skews. The twist is that skew does NOT cancel out when the queuing delay estimate is computed, because it makes the two clocks' offsets change over time 😭

offsets can be huge (some clocks are off by minutes, or even hours or more), but skew is typically small. Typical skews of untrained clocks seem to be around 100-200 parts per million (ppm) [RFC5905], and a skew of 100 ppm works out to an error accumulation of 6 milliseconds per minute. Here's the good news: this accumulation is limited in LEDBAT, because any error accumulation is capped at the amount of history kept by the base delay estimator, as set by the BASE_HISTORY parameter 🙌 Clock skew should generally be insignificant unless the skew is unusually high, or unless extreme values have been picked for TARGET (extremely low) and BASE_HISTORY (extremely large). Even so, we're going to look at what skew could do to LEDBAT behaviour, just to be thorough 🔍

Clock skew can show up in two ways. Either the sender's clock is faster than the receiver's, or the receiver's clock is faster than the sender's.

  • Sender's clock faster: the measured one-way delay will decrease as the sender's clock drifts forward. This drift can make the queueing delay look artificially low, but it should also lead to a lower base delay measurement, which soaks up that wrong reduction in the one-way delay estimates. so it's self-correcting, slay 💖
  • Receiver's clock faster: the one-way delay estimate will artificially increase with time. That can cut a LEDBAT flow's throughput for no reason 😤 In this case, a skew correction mechanism can be beneficial 🫶

here's one example skew correction mechanism 🧠 The receiver sends back raw (sending and receiving) timestamps. With that info, the sender can estimate one-way delays in both directions, and it can also compute and keep an estimate of the base delay as the receiver would observe it. If the sender notices the receiver reducing its base delay estimate, it may infer that the reduction is due to clock drift. The sender then compensates by increasing its own base delay estimate by that same amount. To make this work, timestamps need to be sent in both directions 🔁

we're also going to outline a few other skew correction ideas, bestie 🌈

  • Skew correction with faster virtual clock: because a faster clock on the sender leads to continuous updates of the base delay, a faster virtual clock can be used for sender timestamping. This virtual clock can be computed from the default machine clock through a linear transformation. For instance, with a 500 ppm speed-up, the sender's clock is very likely to be faster than a receiver's clock. So LEDBAT gets the implicit correction when it updates the base delay, which is kind of genius ngl 🧚
  • Skew correction with estimating drift: a LEDBAT sender keeps a history of base delay minima. That history can be the foundation for computing the clock skew difference between the two hosts. The slope of a linear function fitted to the set of minimum base delays gives an estimate of the clock skew, and that estimate can be used to correct the clocks. If the other endpoint is doing the same thing, the clock should be corrected by half of the estimated skew amount 🤝
  • Byzantine skew correction: when it's known that each host keeps long-lived connections to a number of different other hosts, a byzantine scheme can be used to estimate the skew with respect to true time. Specifically, a host calculates the skew difference for each of its peer hosts as described in the previous approach, then takes the median of those skew differences. This scheme isn't universally applicable, but it combines well with other schemes, since it's essentially a clock training mechanism 🎓 It also corrects fast, because state is preserved between connections 🏃‍♀️💨

Authors' Addresses ✨

and last but not least, the squad behind this doc 💜 Here are the authors' addresses, exactly as listed:

Stanislav Shalunov
BitTorrent, Inc.
303 Second St., Suite S200
San Francisco, CA  94107
USA

EMail: shalunov@shlang.com
URI:   http://shlang.com


Greg Hazel
BitTorrent, Inc.
303 Second St., Suite S200
San Francisco, CA  94107
USA

EMail: greg@bittorrent.com


Janardhan Iyengar
Franklin and Marshall College
415 Harrisburg Ave.
Lancaster, PA  17603
USA

EMail: jiyengar@fandm.edu


Mirja Kuehlewind
University of Stuttgart
Stuttgart
DE

EMail: mirja.kuehlewind@ikr.uni-stuttgart.de
📦 where this page comes from