idnits 2.17.1 draft-jonglez-babel-rtt-extension-01.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 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 132: '...ation of RTTs, a node A SHOULD include...' RFC 2119 keyword, line 138: '... an IHU to A, it SHOULD attach to the ...' RFC 2119 keyword, line 140: '...Additionally, it SHOULD ensure that th...' RFC 2119 keyword, line 311: '... MUST be processed normally and any ...' RFC 2119 keyword, line 312: '... TLV MUST be silently ignored....' (2 more instances...) -- 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 229 has weird spacing: '...rtt-min rtt...' -- The document date (May 27, 2015) is 3254 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 6126 (ref. 'BABEL') (Obsoleted by RFC 8966) ** Obsolete normative reference: RFC 7557 (ref. 'BABEL-EXT') (Obsoleted by RFC 8966) Summary: 3 errors (**), 0 flaws (~~), 2 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: November 28, 2015 May 27, 2015 8 Delay-based Metric Extension for the Babel Routing Protocol 9 draft-jonglez-babel-rtt-extension-01 11 Abstract 13 This document defines an extension to the Babel routing protocol that 14 uses symmetric delay in metric computation and therefore makes it 15 possible to prefer lower latency links to higher latency ones. 17 Status of This Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at http://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on November 28, 2015. 34 Copyright Notice 36 Copyright (c) 2015 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 52 2. Protocol operation . . . . . . . . . . . . . . . . . . . . . 3 53 2.1. Delay estimation . . . . . . . . . . . . . . . . . . . . 3 54 2.2. Metric computation . . . . . . . . . . . . . . . . . . . 5 55 2.3. Stability issues . . . . . . . . . . . . . . . . . . . . 6 56 2.4. Backwards and forwards compatibility . . . . . . . . . . 6 57 3. Packet format . . . . . . . . . . . . . . . . . . . . . . . . 6 58 3.1. Timestamp sub-TLV in Hello TLVs . . . . . . . . . . . . . 7 59 3.2. Timestamp sub-TLV in IHU TLVs . . . . . . . . . . . . . . 7 60 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 61 5. Security Considerations . . . . . . . . . . . . . . . . . . . 8 62 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 63 6.1. Normative References . . . . . . . . . . . . . . . . . . 8 64 6.2. Informative References . . . . . . . . . . . . . . . . . 8 65 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 67 1. Introduction 69 The Babel routing protocol [BABEL] does not mandate a specific 70 algorithm for computing metrics; existing implementations use a 71 packet-loss based metric on wireless links and a simple hop-count 72 metric on all other types of links. While this strategy works 73 reasonably well in many networks, it fails to select reasonable 74 routes in some topologies involving tunnels or VPNs. 76 Consider for example the following topology, with three routers A, B 77 and D located in Paris and a fourth router located in Tokyo, 78 connected through tunnels in a diamond topology. 80 +------------+ 81 | A (Paris) +---------------+ 82 +------------+ \ 83 / \ 84 / \ 85 / \ 86 +------------+ +------------+ 87 | B (Paris) | | C (Tokyo) | 88 +------------+ +------------+ 89 \ / 90 \ / 91 \ / 92 +------------+ / 93 | D (Paris) +---------------+ 94 +------------+ 96 When routing traffic from A to D, it is obviously preferable to use 97 the local route through B, as this is likely to provide better 98 service quality and lower monetary cost than the distant route 99 through C. However, the existing implementations of Babel consider 100 both routes as having the same metric, and will therefore route the 101 traffic through C in roughly half the cases. 103 In this document, we specify an extension to the Babel routing 104 protocol that enables precise measurement of the round-trip time 105 (RTT) of a link, and allows its usage in metric computation. Since 106 this causes a negative feedback loop, special care is needed to 107 ensure that the resulting network is reasonably stable (Section 2.3). 109 We believe that this protocol may be useful in other situations than 110 the one described above, such as when running Babel in a congested 111 wireless mesh network or over a complex link layer that performs its 112 own routing; the high granularity of the timestamps used (1ms) should 113 make it easier to experiment with RTT-based metrics on this kind of 114 link layers. 116 2. Protocol operation 118 The protocol estimates the RTT to each neighbour (Section 2.1) which 119 it then uses for metric computation (Section 2.2). 121 2.1. Delay estimation 123 The RTT to a neighbour is estimated using an algorithm due to Mills 124 [MILLS], originally developed for the HELLO routing protocol and 125 later used in NTP [NTP]. 127 A Babel speaker periodically sends a multicast Hello message over all 128 of its interfaces (Section 3.4.1 of [BABEL]). This Hello is usually 129 accompanied with a set of IHU messages, one per neighbour 130 (Section 3.4.2 of [BABEL]). 132 In order to enable the computation of RTTs, a node A SHOULD include 133 in every Hello that it sends a timestamp t1 (according to A's clock). 134 When a node B receives A's Hello, it records in its neighbour table 135 the timestamp t1 as well as the time t1' according to its own (B's) 136 clock at which it received the packet. 138 When B later sends an IHU to A, it SHOULD attach to the IHU the 139 timestamps t1 and t1' which it has stored in its neighbour table. 140 Additionally, it SHOULD ensure that the packet within which the IHU 141 is sent contains a Hello TLV with an associated timestamp t2' 142 (according to B's clock). Symmetrically, A will record in its 143 neighbour table the timestamp t2' as well as the time t2 (according 144 to A's clock) at which it has received the Hello. This is 145 illustrated in the following sequence diagram: 147 A B 148 | | 149 t1 + | 150 |\ | 151 | \ | 152 | \ | Hello(t1) 153 | \ | 154 | \ | 155 | \| 156 | + t1' 157 | | 158 | | 159 | | 160 | + t2' 161 | /| 162 | / | 163 | / | 164 | / | Hello(t2') 165 | / | IHU(t1, t1') 166 |/ | 167 t2 + | 168 | | 169 v v 171 A then estimates the RTT between A and B as (t2 - t1) - (t2' - t1'). 173 This algorithm has a number of desirable properties. First, since 174 there is no requirement that t1' and t2' be equal, the protocol 175 remains asynchronous -- the only change to Babel's message scheduling 176 is the requirement that a packet containing an IHU also contains a 177 Hello. Second, since only differences of timestamps according to a 178 single clock are computed, it does not require synchronised clocks. 179 Third, it requires very little additional state -- a node only needs 180 to store the two timestamps associated with the last hello received 181 from each neighbour. Finally, since it only requires piggybacking 182 one or two timestamps on each Hello and IHU packet, it makes 183 efficient use of network resources. 185 In principle, this algorithm is inaccurate in the presence of clock 186 drift (i.e. when A's and B's clocks are running at different 187 frequencies). However, t2' - t1' is usually on the order of seconds, 188 and significant clock drift is unlikely to happen at that time scale. 190 2.2. Metric computation 192 The algorithm described in the previous section allows computing an 193 RTT to every neighbour. How to map this value to a link cost is a 194 local implementation matter. 196 Obviously, the mapping should be monotonic (larger RTTs imply larger 197 costs). In addition, in order to enhance stability (Section 2.3), 198 the mapping should be bounded -- above a certain RTT, all links are 199 equally bad. 201 2.2.1. Example metric computation 203 The current implementation of Babel uses the following function for 204 mapping RTTs to link costs, parameterised by three parameters rtt- 205 min, rtt-max and max-rtt-penalty: 207 cost 208 ^ 209 | 210 | 211 | C + max-rtt-penalty 212 | +--------------------------- 213 | /. 214 | / . 215 | / . 216 | / . 217 | / . 218 | / . 219 | / . 220 | / . 221 | / . 222 | / . 223 C +------------+ . 224 | . . 225 | . . 226 | . . 227 | . . 228 0 +----------------------------------------------------> 229 0 rtt-min rtt-max RTT 231 For RTTs below rtt-min, the link cost is just the nominal cost of a 232 single hop, C. Between rtt-min and rtt-max, the cost increases 233 linearly; abover rtt-max, the constant value max-rtt-penalty is added 234 to the nominal cost. 236 2.3. Stability issues 238 Using delay as an input to the routing metric in congested networks 239 gives rise to a negative feedback loop: low RTT encourages traffic, 240 which in turn causes the RTT to increase. In a congested network, 241 such a feedback loop can cause persistent oscillations. 243 The current implementation of Babel uses three techniques that 244 collaborate to limit the frequency of oscillations: 246 o the measured RTT is smoothed, which limits Babel's response to 247 short-term RTT variations; 249 o the mapping function is bounded, which avoids switching between 250 congested routes; 252 o a hysteresis algorithm is applied to the metric before route 253 selection, which limits the worst-case frequency of route 254 oscillations. 256 These techniques are discussed in more detail in [DELAY-BASED]. 258 2.4. Backwards and forwards compatibility 260 This protocol extension stores the data that it requires within sub- 261 TLVs of Babel's Hello and IHU TLVs. As discussed in Section 4 of 262 [BABEL-EXT], implementations that do not understand this extension 263 will silently ignore the sub-TLVs while parsing the rest of the TLVs 264 that they contain. In effect, this extension supports building 265 hybrid networks consisting of extended and unextended routers, and 266 while such networks might suffer from sub-optimal routing, they will 267 not suffer from blackholes or routing loops. 269 If a sub-TLV defined in this extension is longer than expected, the 270 additional data is silently ignored. This provision is made in order 271 to allow a future version of this document to extend the packet 272 format with additional data. 274 3. Packet format 276 This extension defines the Timestamp sub-TLV [BABEL-EXT], whose Type 277 field has value 3. This sub-TLV can be contained within a Hello sub- 278 TLV, in which case it carries a single timestamp, or within an IHU 279 sub-TLV, in which case it carries two timestamps. 281 Timestamps are encoded as 32-bit unsigned integers, expressed in 282 units of one microsecond, counting from an arbitrary origin. 284 Timestamps wrap around every 4295 seconds, or slightly more than one 285 hour. 287 3.1. Timestamp sub-TLV in Hello TLVs 289 When contained within a Hello TLV, the Timestamp sub-TLV has the 290 following format: 292 0 1 2 3 293 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 294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 295 | Type = 3 | Length | Transmit timestamp | 296 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 297 | | 298 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 300 Fields : 302 Type Set to 3 to indicate a Timestamp sub-TLV. 304 Length The length of the body, exclusive of the Type and Length 305 fields. 307 Transmit timestamp The time at which the packet containing this sub- 308 TLV was sent, according to the sender's clock. 310 If the Length field is larger than the expected 4 octets, the sub-TLV 311 MUST be processed normally and any extra data contained in this sub- 312 TLV MUST be silently ignored. 314 3.2. Timestamp sub-TLV in IHU TLVs 316 When contained in an IHU TLV destined for node A, the Timestamp sub- 317 TLV has the following format: 319 0 1 2 3 320 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 321 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 322 | Type = 3 | Length | Origin timestamp | 323 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 324 | | Receive timestamp | 325 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 326 | | 327 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 329 Fields : 331 Type Set to 3 to indicate a Timestamp sub-TLV. 333 Length The length of the body, exclusive of the Type and Length 334 fields. 336 Origin timestamp A copy of the transmit timestamp of the last 337 Timestamp sub-TLV contained in a Hello TLV received from 338 node A. 340 Receive timestamp The time at which the last Hello with a Timestamp 341 sub-TLV was received from node A according to the sender's 342 clock. 344 If the Length field is larger than the expected 8 octets, the sub-TLV 345 MUST be processed normally and any extra data contained in this sub- 346 TLV MUST be silently ignored. 348 4. IANA Considerations 350 IANA is instructed to add the following entry to the "Babel Sub-TLV 351 Types" registry: 353 +------+-----------+-----------------+ 354 | Type | Name | Reference | 355 +------+-----------+-----------------+ 356 | 3 | Timestamp | (this document) | 357 +------+-----------+-----------------+ 359 5. Security Considerations 361 This extension merely adds additional timestamping data to two of the 362 TLVs sent by a Babel router, and does not significantly change the 363 security properties of the Babel protocol. 365 6. References 367 6.1. Normative References 369 [BABEL] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, 370 February 2011. 372 [BABEL-EXT] 373 Chroboczek, J., "Extension Mechanism for the Babel Routing 374 Protocol", RFC 7557, May 2015. 376 6.2. Informative References 378 [DELAY-BASED] 379 Jonglez, B. and J. Chroboczek, "A delay-based routing 380 metric", March 2014. 382 Available online from http://arxiv.org/abs/1403.3488 384 [MILLS] Mills, D., "DCN Local-Network Protocols", RFC 891, 385 December 1983. 387 [NTP] Mills, D., Martin, J., Burbank, J., and W. Kasch, "Network 388 Time Protocol Version 4: Protocol and Algorithms 389 Specification", RFC 5905, June 2010. 391 Authors' Addresses 393 Baptiste Jonglez 394 ENS Lyon 395 France 397 Email: baptiste.jonglez@ens-lyon.org 399 Juliusz Chroboczek 400 PPS, University of Paris-Diderot 401 Case 7014 402 75205 Paris Cedex 13 403 France 405 Email: jch@pps.univ-paris-diderot.fr