idnits 2.17.00 (12 Aug 2021) /tmp/idnits22416/draft-jonglez-babel-rtt-extension-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([BABEL]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 283: '... MUST be processed normally and any ...' RFC 2119 keyword, line 284: '... TLV MUST be silently ignored....' RFC 2119 keyword, line 317: '... MUST be processed normally and any ...' RFC 2119 keyword, line 318: '... TLV MUST be silently ignored....' -- The draft header indicates that this document updates RFC6126, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 218 has weird spacing: '...rtt-min rtt...' -- The document date (July 2, 2014) is 2879 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 6126 (ref. 'BABEL') (Obsoleted by RFC 8966) == Outdated reference: draft-chroboczek-babel-extension-mechanism has been published as RFC 7557 Summary: 6 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Jonglez 3 Internet-Draft ENS Lyon 4 Updates: 6126 (if approved) J. Chroboczek 5 Intended status: Experimental PPS, University of Paris-Diderot 6 Expires: January 3, 2015 July 2, 2014 8 Delay-based Metric Extension for the Babel Routing Protocol 9 draft-jonglez-babel-rtt-extension-00 11 Abstract 13 This document defines an extension to the Babel routing protocol 14 [BABEL] that uses the delay to a neighbour in metric computation and 15 therefore makes it possible to prefer lower latency links to higher 16 latency ones. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on January 3, 2015. 35 Copyright Notice 37 Copyright (c) 2014 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction and background . . . . . . . . . . . . . . . . . 2 53 2. Protocol operation . . . . . . . . . . . . . . . . . . . . . 3 54 2.1. Delay estimation . . . . . . . . . . . . . . . . . . . . 3 55 2.2. Metric computation . . . . . . . . . . . . . . . . . . . 4 56 2.3. Stability issues . . . . . . . . . . . . . . . . . . . . 5 57 3. Packet format . . . . . . . . . . . . . . . . . . . . . . . . 6 58 3.1. Timestamp sub-TLV in Hello TLVs . . . . . . . . . . . . . 6 59 3.2. Timestamp sub-TLV in IHU TLVs . . . . . . . . . . . . . . 7 60 4. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 61 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8 63 1. Introduction and background 65 The Babel routing protocol [BABEL] does not mandate a specific 66 algorithm for computing metrics; existing implementations use a 67 packet-loss based metric on wireless links and a simple hop-count 68 metric on all other types of links. While this strategy works 69 reasonably well in many networks, it fails to select reasonable 70 routes in some topologies involving tunnels or VPNs. 72 Consider for example the following topology, with three routers A, B 73 and D located in Paris and a fourth router located in Tokyo, 74 connected through tunnels in a diamond topology. 76 +------------+ 77 | A (Paris) +---------------+ 78 +------------+ \ 79 / \ 80 / \ 81 / \ 82 +------------+ +------------+ 83 | B (Paris) | | C (Tokyo) | 84 +------------+ +------------+ 85 \ / 86 \ / 87 \ / 88 +------------+ / 89 | D (Paris) +---------------+ 90 +------------+ 92 When routing traffic from A to D, it is obviously preferable to use 93 the local route through B, as this is likely to provide better 94 service quality and lower monetary cost than the distant route 95 through C. However, the existing implementations of Babel consider 96 both routes as having the same metric, and will therefore route the 97 traffic through C in roughly half the cases. 99 In this memo, we specify an extension to the Babel routing protocol 100 that enables precise measurement of the round-trip time (RTT) of a 101 link, and allows its usage in metric computation. Since this causes 102 a negative feedback loop, special care is needed to ensure that the 103 resulting network is reasonably stable (Section 2.3). 105 We believe that this protocol may be useful in other situations than 106 the one described above, such as when running Babel in a congested 107 wireless mesh network or over a complex link layer that performs its 108 own routing; the high granularity of the timestamps used (1ms) should 109 make it easier to experiment with RTT-based metrics on this kind of 110 link layers. 112 2. Protocol operation 114 The protocol estimates the RTT to each neighbour (Section 2.1) which 115 it then uses for metric computation (Section 2.2). 117 2.1. Delay estimation 119 The RTT to a neighbour is estimated using an algorithm due to Mills 120 [MILLS], originally developed for the HELLO routing protocol and 121 later used in NTP [NTP]. 123 A Babel speaker periodically sends a multicast Hello message over all 124 of its interfaces. This Hello is usually accompanied with a set of 125 IHU messages, one per neighbour. 127 In order to enable the computation of RTTs, a node A includes in 128 every Hello that it sends a timestamp t1 according to A's clock. 129 Additionally, a node B includes in the IHU it sends to A the 130 timestamp t1 included in the last Hello received from A, and the 131 timestamp t1' according to B's clock at which it received that Hello. 132 Upon receiving B's combined Hello and IHU, node A records the 133 timestamp t2 at which it received the combined packet, according to 134 A's clock. This is described in the following sequence diagram: 136 A B 137 | | 138 t1 + | 139 |\ | 140 | \ | 141 | \ | Hello(t1) 142 | \ | 143 | \ | 144 | \| 145 | + t1' 146 | | 147 | | 148 | | 149 | + t2' 150 | /| 151 | / | 152 | / | 153 | / | Hello(t2') 154 | / | IHU(t1, t1') 155 |/ | 156 t2 + | 157 | | 158 v v 160 Node A then computes the RTT as (t2 - t1) - (t2' - t1'). 162 This algorithm has a number of desirable properties. First, since 163 there is no requirement that t1' and t2' be equal, the protocol 164 remains asynchronous -- the only change to Babel's message scheduling 165 that is required is to ensure that IHUs are always sent together with 166 Hellos. Second, since only differences of timestamps according to a 167 single clock are computed, it does not require synchronised clocks. 168 Third, it is mostly stateless -- a node only needs to store the two 169 timestamps associated with the last hello received from each 170 neighbour. Finally, since it only requires piggybacking a couple of 171 timestamps on each Hello and IHU packet, it makes efficient use of 172 network resources. 174 In principle, this protocol is incorrect in the presence of clock 175 drift (i.e. when A's and B's clocks are running at different 176 frequencies). However, t2' - t1' is usually on the order of seconds, 177 and significant drift is unlikely to happen at this time scale. 179 2.2. Metric computation 181 The algorithm described in the previous section allows computing an 182 RTT to all neighbours. How to map this value to a link cost is left 183 to the implementation. 185 Obviously, the mapping should be monotonic (larger RTTs imply larger 186 costs). In addition, in order to enhance stability (Section 2.3), 187 the mapping should be bounded -- above a certain RTT, all links are 188 equally bad. 190 2.2.1. Sample mapping 192 The sample implementation of Babel uses the following function for 193 mapping RTTs to link costs, parameterised by three parameters rtt- 194 min, rtt-max and max-rtt-penalty: 196 cost 197 ^ 198 | 199 | 200 | C + max-rtt-penalty 201 | +--------------------------- 202 | /. 203 | / . 204 | / . 205 | / . 206 | / . 207 | / . 208 | / . 209 | / . 210 | / . 211 | / . 212 C +------------+ . 213 | . . 214 | . . 215 | . . 216 | . . 217 0 +----------------------------------------------------> 218 0 rtt-min rtt-max RTT 220 For RTTs below rtt-min, the link cost is just the nominal cost of a 221 single hop, C. Between rtt-min and rtt-max, the cost increases 222 linearly; abover rtt-max, the constant value max-rtt-penalty is added 223 to the nominal cost. 225 2.3. Stability issues 227 Using delay as an input to the routing metric in congested networks 228 gives rise to a negative feedback loop: low RTT encourages traffic, 229 which in turn causes the RTT to increase. In a congested network, 230 such a feedback loop can cause persistent oscillations. 232 The sample implementation of Babel uses three techniques that 233 collaborate to limit the frequency of oscillations: 235 o the measured RTT is smoothed, which limits Babel's response to 236 short-term RTT variations; 238 o the mapping function is bounded, which avoids switching between 239 congested routes; 241 o a hysteresis algorithm is applied to the metric before route 242 selection, which limits the worst-case frequency of route 243 oscillations. 245 These techniques are discussed in more detail in [DELAY-BASED]. 247 3. Packet format 249 This extension defines the Timestamp sub-TLV [BABEL-EXT], whose Type 250 field has value 3. This sub-TLV can be contained within a Hello sub- 251 TLV, in which case it carries a single timestamp, or within an IHU 252 sub-TLV, in which case it carries two timestamps. 254 Timestamps are encoded as 32-bit unsigned integers, expressed in 255 units of one microsecond, counting from an arbitrary origin. 256 Timestamps wrap around every 4295 seconds, or slightly more than one 257 hour. 259 3.1. Timestamp sub-TLV in Hello TLVs 261 When contained within a Hello TLV, the Timestamp sub-TLV has the 262 following format: 264 0 1 2 3 265 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 266 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 267 | Type = 3 | Length | Transmit timestamp | 268 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 269 | | 270 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 272 Fields : 274 Type Set to 3 to indicate a Timestamp sub-TLV. 276 Length The length of the body, exclusive of the Type and Length 277 fields. 279 Transmit timestamp The time at which the packet containing this sub- 280 TLV was sent, according to the sender's clock. 282 If the Length field is larger than the expected 4 octets, the sub-TLV 283 MUST be processed normally and any extra data contained in this sub- 284 TLV MUST be silently ignored. 286 3.2. Timestamp sub-TLV in IHU TLVs 288 When contained in an IHU TLV destined for node A, the Timestamp sub- 289 TLV has the following format: 291 0 1 2 3 292 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 293 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 294 | Type = 3 | Length | Origin timestamp | 295 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 296 | | Receive timestamp | 297 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 298 | | 299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 301 Fields : 303 Type Set to 3 to indicate a Timestamp sub-TLV. 305 Length The length of the body, exclusive of the Type and Length 306 fields. 308 Origin timestamp A copy of the transmit timestamp of the last 309 Timestamp sub-TLV contained in a Hello TLV received from 310 node A. 312 Receive timestamp The time at which the last Hello with a Timestamp 313 sub-TLV was received from node A according to the sender's 314 clock. 316 If the Length field is larger than the expected 8 octets, the sub-TLV 317 MUST be processed normally and any extra data contained in this sub- 318 TLV MUST be silently ignored. 320 4. References 322 [BABEL] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, 323 February 2011. 325 [BABEL-EXT] 326 Chroboczek, J., "Extension Mechanism for the Babel Routing 327 Protocol", Internet Draft draft-chroboczek-babel- 328 extension-mechanism-01, June 2014. 330 [DELAY-BASED] 331 Jonglez, B. and J. Chroboczek, "A delay-based routing 332 metric", March 2014. 334 Available online from http://arxiv.org/abs/1403.3488 336 [MILLS] Mills, D., "DCN Local-Network Protocols", RFC 891, 337 December 1983. 339 [NTP] Mills, D., Martin, J., Burbank, J., and W. Kasch, "Network 340 Time Protocol Version 4: Protocol and Algorithms 341 Specification", RFC 5905, June 2010. 343 Authors' Addresses 345 Baptiste Jonglez 346 ENS Lyon 347 France 349 Email: baptiste.jonglez@ens-lyon.org 351 Juliusz Chroboczek 352 PPS, University of Paris-Diderot 353 Case 7014 354 75205 Paris Cedex 13 355 France 357 Email: jch@pps.univ-paris-diderot.fr