LEDBAT

From HandWiki
Short description: Delay-based congestion control algorithm

Low Extra Delay Background Transport (LEDBAT) is a way to transfer data on the Internet quickly without clogging the network.[1] LEDBAT was invented by Stanislav Shalunov[2][3] and is used by Apple for software updates, by BitTorrent for most of its transfers[4] and by Microsoft SCCM software distribution points.[5] At one point in time, LEDBAT was estimated to carry 13–20% of Internet traffic.[4][6][3]

LEDBAT is a delay-based congestion control algorithm that uses all the available bandwidth while limiting the increase in delay;[2][7] it does so by measuring one-way delay and using changes in the measurements to limit congestion that the LEDBAT flow itself induces in the network. LEDBAT is described in RFC 6817.

Design goals

LEDBAT congestion control has the following goals:[2]

  1. Use all available bandwidth, and to maintain a low queueing delay when no other traffic is present,
  2. Limit the queuing delay it adds to that induced by other traffic, and
  3. To yield quickly to standard TCP that share the same bottleneck link.

Implementations and deployment

The two main implementations are uTP by BitTorrent and as part of TCP by Apple. BitTorrent uses uTP for most traffic and makes the code available under an open-source license.[8] Apple uses LEDBAT for Software Updates so that large software downloads to macOS computers and iOS devices do not interfere with normal user activities; Apple also makes the source code available.[9]

Both of the above implementations aim to limit the network queuing delay to 100ms. This is the maximum allowed for by the standardized protocol. If one used a lower value, then it would be starved when the other was in use.[2][9]

Windows 10 Anniversary Update introduced support for LEDBAT via undocumented socket option as an experimental Windows TCP Congestion Control Module and Windows Server 2019.[10][11][12]

Example

Assumptions:

  1. The clocks of the sender and the receiver are not synchronized.
  2. The sender sends at a fixed rate.

The sender sends 5 packets of data every 10 clock counts: 10, 20, 30, 40, 50. The units are unimportant. The receiver is receiving data not only from this particular sender but also from other sources. For the 5 packets that were sent, the receiver receives them at the following clock counts: 112, 135, 176, 250, 326. The first differences (one way delay) between the received and sent clock counts are: 102, 115, 146, 210, 276. The second differences (change in one way delay) are: 13 (115 - 102), 31, 64 and 66. The receiver will infer from the positive increase in one way delays that congestion is increasing and adjust the transfer rate accordingly.

See also

References

  1. McMillan, Robert. "How the Large Hadron Collider Will Bring the Internet to Everything" (in en-US). WIRED. https://www.wired.com/2013/06/open-garden/. 
  2. 2.0 2.1 2.2 2.3 Mirja, Kuehlewind; Greg, Hazel; Stanislav, Shalunov; Janardhan, Iyengar (December 2012). Low Extra Delay Background Transport (LEDBAT). doi:10.17487/RFC6817. http://tools.ietf.org/html/rfc6817. 
  3. 3.0 3.1 Tammy Parker (December 10, 2012). "Open Garden to enable channel bonding over Wi-Fi, 3G and 4G - FierceWirelessTech". http://www.fiercewireless.com/tech/story/open-garden-enable-channel-bonding-over-wi-fi-3g-and-4g/2012-12-10. 
  4. 4.0 4.1 This Is How Your BitTorrent Downloads Move So Fast, July 29, 2013, Retrieved November 24, 2013
  5. aczechowski. "Content management fundamentals - Configuration Manager" (in en-us). https://docs.microsoft.com/en-us/sccm/core/plan-design/hierarchy/fundamental-concepts-for-content-management#windows-ledbat. 
  6. By Gabe Stein, Former BitTorrent Engineer Thinks He Can Fix Your Wi-Fi--For Good, July 24, 2013, Retrieved November 24, 2013
  7. BY ROBERT MCMILLAN, THE INTERNET OF THINGS, July 21, 2013, Retrieved November 24, 2013
  8. Libutp - The uTorrent Transport Protocol library, Retrieved November 24, 2013
  9. 9.0 9.1 "Tcp_ledbat.c". https://opensource.apple.com/source/xnu/xnu-4570.71.2/bsd/netinet/tcp_ledbat.c.auto.html. 
  10. "Announcing: New Transport Advancements in the Anniversary Update for Windows 10 and Windows Server 2016". https://blogs.technet.microsoft.com/networking/2016/07/18/announcing-new-transport-advancements-in-the-anniversary-update-for-windows-10-and-windows-server-2016/. 
  11. Microsoft (2017). "LEDBAT++: Low priority TCP Congestion Control in Windows" (PDF). https://datatracker.ietf.org/meeting/100/materials/slides-100-iccrg-ledbat-low-priority-tcp-congestion-control-in-windows. 
  12. "Top 10 Networking Features in Windows Server 2019: #9 LEDBAT – Latency Optimized Background Transport" (in en-US). https://blogs.technet.microsoft.com/networking/2018/07/25/ledbat/.