The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-01

Internet Engineering Task Force (IETF)                       S. Shalunov
Request for Comments: 6817                                      G. Hazel
Category: Experimental                                  BitTorrent, Inc.
ISSN: 2070-1721                                               J. Iyengar
                                           Franklin and Marshall College
                                                           M. Kuehlewind
                                                 University of Stuttgart
                                                           December 2012

             Low Extra Delay Background Transport (LEDBAT)

Abstract

   Low Extra Delay Background Transport (LEDBAT) is an experimental
   delay-based congestion control algorithm that seeks to utilize the
   available bandwidth on an end-to-end path while limiting the
   consequent increase in queueing delay on that path.  LEDBAT uses
   changes in one-way delay measurements to limit congestion that the
   flow itself induces in the network.  LEDBAT is designed for use by
   background bulk-transfer applications to be no more aggressive than
   standard TCP congestion control (as specified in RFC 5681) and to
   yield in the presence of competing flows, thus limiting interference
   with the network performance of competing flows.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for examination, experimental implementation, and
   evaluation.

   This document defines an Experimental Protocol for the Internet
   community.  This document is a product of the Internet Engineering
   Task Force (IETF).  It represents the consensus of the IETF
   community.  It has received public review and has been approved for
   publication by the Internet Engineering Steering Group (IESG).  Not
   all documents approved by the IESG are a candidate for any level of
   Internet Standard; see Section 2 of RFC 5741.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   http://www.rfc-editor.org/info/rfc6817.

Shalunov, et al.              Experimental                      [Page 1]
RFC 6817                         LEDBAT                    December 2012

Copyright Notice

   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) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to 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 are provided without warranty as
   described in the Simplified BSD License.

Shalunov, et al.              Experimental                      [Page 2]
RFC 6817                         LEDBAT                    December 2012

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

Shalunov, et al.              Experimental                      [Page 3]
RFC 6817                         LEDBAT                    December 2012

1.  Introduction

   TCP congestion control [RFC5681] seeks to share bandwidth at a
   bottleneck link equitably among flows competing at the bottleneck,
   and it is the predominant congestion control mechanism used on the
   Internet.  However, not all applications seek an equitable share of
   network throughput.  "Background" applications, such as software
   updates or file-sharing applications, seek to operate without
   interfering with the performance of more interactive and delay-
   and/or bandwidth-sensitive "foreground" applications.  Standard TCP
   congestion control, as specified in [RFC5681], may be too aggressive
   for use with such background applications.

   Low Extra Delay Background Transport (LEDBAT) is an experimental
   delay-based congestion control mechanism that reacts early to
   congestion in the network, thus enabling "background" applications to
   use the network while avoiding interference with the network
   performance of competing flows.  A LEDBAT sender uses one-way delay
   measurements to estimate the amount of queueing on the data path,
   controls the LEDBAT flow's congestion window based on this estimate,
   and minimizes interference with competing flows by adding low extra
   queueing delay on the end-to-end path.

   Delay-based congestion control protocols, such as TCP-Vegas
   [Bra94][Low02], are generally designed to achieve more, not less
   throughput than standard TCP, and often outperform TCP under
   particular network settings.  For further discussion on Lower-than-
   Best-Effort transport protocols see [RFC6297].  In contrast, LEDBAT
   is designed to be no more aggressive than TCP [RFC5681]; LEDBAT is a
   "scavenger" congestion control mechanism that seeks to utilize all
   available bandwidth and yields quickly when competing with standard
   TCP at a bottleneck link.

   In the rest of this document, we refer to congestion control
   specified in [RFC5681] as "standard TCP".

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 seeks to achieve the following goals:

   1.  to utilize end-to-end available bandwidth and to maintain low
       queueing delay when no other traffic is present,

Shalunov, et al.              Experimental                      [Page 4]
RFC 6817                         LEDBAT                    December 2012

   Babel is a fairly economic protocol.  Route updates take between 12
   and 40 octets per destination, depending on how successful
   compression is; in a double-stack mesh network, an average of less
   than 24 octets is typical.  The route table occupies about 35 octets
   per IPv6 entry.  To put these values into perspective, a single full-
   size Ethernet frame can carry some 65 route updates, and a megabyte
   of memory can contain a 20000-entry routing table and the associated
   source table.

   Babel is also a reasonably simple protocol.  The sample
   implementation consists of less than 8000 lines of C code, and it
   compiles to less than 60 kB of text on a 32-bit CISC architecture.

   Nonetheless, in some very constrained environments, such as PDAs,
   microwave ovens, or abacuses, it may be desirable to have subset
   implementations of the protocol.

   A parasitic implementation is one that uses a Babel network for
   routing its packets but does not announce any of the routes that it
   has learnt from its neighbours.  (This is slightly more than a
   passive implementation, which doesn't even announce routes to
   itself.)  It may either maintain a full routing table or simply

Chroboczek               Expires August 4, 2017                [Page 44]
Internet-Draft         The Babel Routing Protocol           January 2017

   select a gateway amongst any one of its neighbours that announces a
   default route.  Since a parasitic implementation never forwards
   packets, it cannot possibly participate in a routing loop; hence, it
   need not evaluate the feasibility condition, and need not maintain a
   source table.

   A parasitic implementation MUST answer acknowledgement requests and
   MUST participate in the Hello/IHU protocol.  Finally, it MUST be able
   to reply to seqno requests for routes that it announces and SHOULD be
   able to reply to route requests.

Appendix D.  Software Availability

   The sample implementation of Babel is available from
   <http://www.pps.univ-paris-diderot.fr/~jch/software/babel/>.

Appendix E.  Changes from previous versions

E.1.  Changes since RFC 6126

   o  Changed UDP port number to 6696.

   o  Consistently use router-id rather than id.

   o  Clarified that the source garbage collection timer is reset after
      sending an update even if the entry was not modified.

   o  In section "Seqno Requests", fixed an erroneous "route request".

   o  In the description of the Seqno Request TLV, added the description
      of the Router-Id field.

   o  Made router-ids all-0 and all-1 forbidden.

Author's Address

   Juliusz Chroboczek
   IRIF, University of Paris-Diderot
   Case 7014
   75205 Paris Cedex 13
   France

   Email: jch@irif.fr

Chroboczek               Expires August 4, 2017                [Page 45]