idnits 2.17.1 draft-boutier-babel-source-specific-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 145: '...l implementation MUST choose routing t...' RFC 2119 keyword, line 159: '...l implementation MAY use them directly...' RFC 2119 keyword, line 162: '...cs, then the Babel implementation MUST...' RFC 2119 keyword, line 167: '...l implementation SHOULD silently ignor...' RFC 2119 keyword, line 168: '... routes and MUST NOT reannounce t...' (16 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 -- The document date (May 27, 2015) is 3257 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 (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M. Boutier 3 Internet-Draft J. Chroboczek 4 Updates: 6126 (if approved) PPS, University of Paris-Diderot 5 Intended status: Experimental May 27, 2015 6 Expires: November 28, 2015 8 Source-Specific Routing in Babel 9 draft-boutier-babel-source-specific-01 11 Abstract 13 This document describes extensions to the Babel routing protocol to 14 support source-specific routing. 16 Status of This Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on November 28, 2015. 33 Copyright Notice 35 Copyright (c) 2015 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction and background . . . . . . . . . . . . . . . . . 2 51 2. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 2 52 2.1. The Source Table . . . . . . . . . . . . . . . . . . . . 2 53 2.2. The Route Table . . . . . . . . . . . . . . . . . . . . . 3 54 2.3. The Table of Pending Requests . . . . . . . . . . . . . . 3 55 3. Data Forwarding . . . . . . . . . . . . . . . . . . . . . . . 3 56 4. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 4 57 4.1. Updates . . . . . . . . . . . . . . . . . . . . . . . . . 4 58 4.2. Requests . . . . . . . . . . . . . . . . . . . . . . . . 5 59 5. Backwards compatibility . . . . . . . . . . . . . . . . . . . 5 60 5.1. Loop-avoidance . . . . . . . . . . . . . . . . . . . . . 6 61 5.2. Blackholes . . . . . . . . . . . . . . . . . . . . . . . 6 62 6. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 6 63 6.1. Source-Specific Update . . . . . . . . . . . . . . . . . 6 64 6.2. Source-Specific Request . . . . . . . . . . . . . . . . . 8 65 6.3. Source-Specific Seqno Request . . . . . . . . . . . . . . 8 66 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 67 8. Security considerations . . . . . . . . . . . . . . . . . . . 10 68 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 69 9.1. Normative References . . . . . . . . . . . . . . . . . . 10 70 9.2. Informative References . . . . . . . . . . . . . . . . . 10 71 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 73 1. Introduction and background 75 Source-specific routing is an extension to traditional next-hop 76 routing where packets are routed according to both their destination 77 and their source address. This document describes extensions to the 78 Babel routing protocol [BABEL] to support source-specific routing. 80 Background information about source-specific routing is provided in 81 [SS-ROUTING]. 83 2. Data Structures 85 This extension adds some data to the data structures maintained by a 86 Babel node. 88 2.1. The Source Table 90 Every Babel node maintains a source table, as described in [BABEL], 91 Section 3.2.4. A source-specific Babel node extends this table with 92 the following field: 94 o the source prefix (sprefix, splen) specifying the source of 95 packets to which this entry applies. 97 If splen is 0, then this is a non-specific entry, and is treated just 98 like a source table entry defined by the original Babel protocol. 100 With this extension the route entry contains a source which itself 101 contains a source prefix. Notwithstanding the accidental similarity 102 in their names, these are two very different concepts, and should not 103 be confused. 105 2.2. The Route Table 107 Every Babel node maintains a route table, as described in [BABEL], 108 Section 3.2.5. With this extension, this table is indexed by the 109 5-tuple (prefix, plen, source prefix, source plen, router-id) 110 obtained from the associated source table entry. 112 2.3. The Table of Pending Requests 114 Every Babel node maintains a table of pending requests, as described 115 in [BABEL], Section 3.2.6. A source-specific Babel node extends this 116 table with the following entry: 118 o the source prefix being requested. 120 3. Data Forwarding 122 In next-hop routing, if two routing table entries overlap, then one 123 is necessarily more specific than the other; the "longest prefix 124 rule" specifies that the most specific applicable routing table entry 125 is chosen. 127 With source-specific routing, there might no longer be a most 128 specific applicable prefix: two routing table entries might match a 129 given packet without one necessarily being more specific than the 130 other. Consider for example the following fragment of a routing 131 table: 133 (2001:DB8:0:1::/64, ::/0, A) 135 (::/0, 2001:DB8:0:2::/64, B) 137 This specifies that all packets with destination in 2001:DB8:0:1::/64 138 are to be routed through A, while packets with a source in 139 2001:DB8:0:2::/64 are to be routed through B. A packet with source 140 2001:DB8:0:2::42 and destination 2001:DB8:0:1::57 matches both rules, 141 although neither is more specific than the other. A choice is 142 necessary, and unless the choice being made is the same on all 143 routers in a routing domain, persistent routing loops may occur. 145 A Babel implementation MUST choose routing table entries by using the 146 so-called destination-first ordering, where a routing table entry R1 147 is preferred to a routing table entry R2 when either R1's destination 148 prefix is more specific than R2's, or the destination prefixes are 149 equal and R1's source prefix is more specific than R2's. (In more 150 formal terms, routing table entries are compared using the 151 lexicographic product of the destination prefix ordering by the 152 source prefix ordering.) 154 In practice, this means that a source-specific Babel implementation 155 must take care that any lower layers that perform packet forwarding 156 obey this semantics. In particular: 158 o If the lower layers implement the destination-first ordering, then 159 the Babel implementation MAY use them directly; 161 o If the lower layers can hold source-specific routes, but not with 162 the right semantics, then the Babel implementation MUST 163 disambiguate the routing table by using a suitable disambiguation 164 algorithm (see [SS-ROUTING] for such an algorithm). 166 o If the lower layers cannot hold source-specific routes, then a 167 Babel implementation SHOULD silently ignore any source-specific 168 routes and MUST NOT reannounce them to other nodes. 170 4. Protocol Operation 172 This extension does not fundamentally change the operation of the 173 Babel protocol. 175 4.1. Updates 177 This extension introduces a new kind of update, the source-specific 178 update. Whenever a source-specific Babel node needs to send an 179 update, it checks whether the update is for a source-specific route 180 (a route with a source prefix of non-zero length); if that is the 181 case, it MUST send a source-specific update (Section 6.1), and 182 otherwise it MUST send a non-specific update ([BABEL], 183 Section 4.4.9). 185 Every Babel node maintains a source table, which it updates whenever 186 it sends an Update ([BABEL], Section 3.7.3). A source-specific Babel 187 node MUST update the source table not only when it sends an update, 188 but also when it sends a source-specific update. 190 4.2. Requests 192 This extension duplicates Babel's two request types: there are now 193 two kinds of route requests (source-specific and unspecific), and, 194 similarly, two kinds of seqno requests. 196 This extension does not modify Babel's strategy for sending requests. 197 Whenever a Babel node needs to send a request, it checks whether the 198 request is for a source-specific route; if it is, it MUST send one of 199 the request types defined in this document; if it is not, then it 200 MUST send one of the request types defined in the original Babel 201 specification. 203 4.2.1. Wildcard requests 205 The Babel protocol provides the ability to request a full routing 206 table dump by sending a "wildcard request", a route request with the 207 AE field set to 0. This extension does not modify the semantics of 208 wildcard requests: a wildcard request prompts a dump of non-specific 209 routes only, and a Babel node SHOULD NOT send any source-specific 210 updates in reply to a wildcard request. 212 A different request is used for obtaining a dump of the source- 213 specific routes in a node's routing table. A "source-specific 214 wildcard request" is a source-specific request (Section 6.2) whose AE 215 field is 0; it requests a dump of the receiving nodes source-specific 216 routes only (routes with a source prefix length of 1 or more). A 217 node SHOULD NOT send any non-specific updates in reply to a source- 218 specific wildcard request. 220 In consequence, a node requiring a full routing table dump must send 221 both a non-specific wildcard request and a source-specific wildcard 222 request. 224 5. Backwards compatibility 226 The protocol extension defined in this document is, to a great 227 extent, interoperable with the base protocol defined in [BABEL] (and 228 all its known extensions). More precisely, if non-specific routers 229 and source-specific routers are mixed in a single routing domain, 230 Babel's loop-avoidance properties are preserved, and, in particular, 231 no persistent routing loops will occur. However, unless there is a 232 backbone of source-specific routers that connects all source-specific 233 edge routers, blackholes might occur. 235 5.1. Loop-avoidance 237 The extension defined in this protocol uses three new TLVs that 238 mirror the existing TLVs for non-specific routing rather than using 239 sub-TLVs to carry source prefix information. As discussed in 240 Section 4 of [BABEL-EXT], this encoding ensures that non-specific 241 routers will silently ignore the whole source-specific TLV, which is 242 necessary to avoid persistent routing loops in hybrid networks. 244 Consider two nodes A and B, with A source-specific announcing a route 245 to (D, S). Suppose that B ignores the source information when it 246 receives the update, and reannounces it as D. This is reannounced to 247 A, which treats it as (D, ::/0). Packets destined to D but not 248 sourced in S will be forwarded by A to B, and by B to A, causing a 249 persistent routing loop: 251 (D,S) (D,::/0) 252 <-- <-- 253 ------ A ----------------- B 254 --> 255 (D,::/0) 257 5.2. Blackholes 259 In general, discarding of source-specific routes by non-specific 260 routers will cause routing blackholes. Intuitively, unless there are 261 enough non-specific routes in the network, non-specific routers will 262 suffer starvation, and discard packets for destinations that are only 263 announced by source-specific routers. A simple yet sufficient 264 condition for avoiding blackholes is to build a connected source- 265 specific backbone that includes all of the edge routers, and announce 266 a (non-specific) default route towards the backbone. 268 6. Protocol Encoding 270 This extension defines three new TLV types that are used by Source- 271 Specific Babel nodes and silently ignored by ordinary Babel nodes, in 272 accordance with [BABEL-EXT]. 274 6.1. Source-Specific Update 275 0 1 2 3 276 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 277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 278 | Type = 13 | Length | AE | Source Plen | 279 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 280 | Plen | Omitted | Interval | 281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 282 | Seqno | Metric | 283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 284 | Prefix... 285 +-+-+-+-+-+-+-+-+-+-+-+- 286 | Source prefix... 287 +-+-+-+-+-+-+-+-+-+-+-+- 289 Fields: 291 Type Set to 13 to indicate a source-specific update TLV. 293 Length The length of the body, exclusive of the Type and Length 294 fields. 296 AE The encoding of the prefix field. 298 Source Plen The length of the advertised source prefix. This MUST 299 NOT be 0. 301 Plen The length of the advertised destination prefix. 303 Omitted The number of octets that have been omitted at the 304 beginning of the advertised prefix and that should be taken 305 from a preceding Update TLV with the flag with value 80 306 hexadecimal set. 308 Interval An upper bound, expressed in centiseconds, on the time 309 after which the sending node will send a new update for 310 this prefix. This MUST NOT be 0 and SHOULD NOT be less 311 than 10. The receiving node will use this value to compute 312 a hold time for this routing table entry. The value FFFF 313 hexadecimal (infinity) expresses that this announcement 314 will not be repeated unless a request is received. 316 Seqno The originator's sequence number for this update. 318 Metric The sender's metric for this route. The value FFFF 319 hexadecimal (infinity) means that this is a route 320 retraction. 322 Prefix The destination prefix being advertised. This field's size 323 is (Plen/8 - Omitted) rounded upwards. 325 Source Prefix The source prefix being advertised. This field's size 326 is (Source Plen)/8 rounded upwards. 328 6.2. Source-Specific Request 330 0 1 2 3 331 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 332 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 333 | Type = 14 | Length | AE | Plen | 334 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 335 | Source Plen | Prefix... 336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 337 | Source prefix... 338 +-+-+-+-+-+-+-+-+-+-+-+- 340 Fields: 342 Type Set to 14 to indicate a Source-Specific Route Request TLV. 344 Length The length of the body, exclusive of the Type and Length 345 fields. 347 AE The encoding of the prefix field. The value 0 (wildcard) 348 requests a full dump of all the source-specific routes of 349 the receving node (i.e. those with non-zero source prefix 350 length). 352 Plen The length of the requested destination prefix. 354 Source Plen The length of the requested source prefix. This MUST 355 NOT be 0, except for AE 0. 357 Prefix The destination prefix being requested. This field's size 358 is Plen/8 rounded upwards. 360 Source Prefix The source prefix being advertised. This field's size 361 is (Source Plen)/8 rounded upwards. 363 6.3. Source-Specific Seqno Request 364 0 1 2 3 365 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 366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 367 | Type = 15 | Length | AE | Plen | 368 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 369 | Seqno | Hop Count | Source Plen | 370 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 371 | | 372 + Router-Id + 373 | | 374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 375 | Prefix... 376 +-+-+-+-+-+-+-+-+-+-+-+- 377 | Source prefix... 378 +-+-+-+-+-+-+-+-+-+-+-+- 380 Fields: 382 Type Set to 15 to indicate a Source-Specific Seqno Request TLV. 384 Length The length of the body, exclusive of the Type and Length 385 fields. 387 AE The encoding of the prefix field. This MUST NOT be 0. 389 Plen The length of the requested destination prefix. 391 Seqno The sequence number that is being requested. 393 Hop Count The maximum number of times that this TLV may be forwarded, 394 plus 1. This MUST NOT be 0. 396 Source Plen The length of the requested source prefix. This MUST 397 NOT be 0. 399 Router-Id The Router-ID associated to this route. 401 Prefix The destination prefix being requested. This field's size 402 is Plen/8 rounded upwards. 404 Source Prefix The source prefix being advertised. This field's size 405 is "Source Plen"/8 rounded upwards. 407 A Source-Specific Seqno Request TLV prompts the receiving node to 408 send an Update for the route specified by the AE, Plen, Prefix, 409 Source Plen and Source Prefix fields, with either a router-id 410 different from what is specified by the Router-Id field, or a Seqno 411 no less than what is specified by the Seqno field. If this request 412 cannot be satisfied locally, then it is forwarded according to the 413 rules set out in Section 3.8.1.2 of [BABEL]. 415 Just like an ordinary Seqno Request, a Source-Specific Seqno Request 416 MAY be sent to a multicast address but MUST NOT be forwarded to a 417 multicast address and MUST NOT be forwarded to more than one 418 neighbour. A Source-Specific Seqno Request MUST NOT be forwarded if 419 its Hop Count field is 1. 421 7. IANA Considerations 423 IANA is instructed to add the following entries to the "Babel TLV 424 Types" registry: 426 +------+-------------------------------+-----------------+ 427 | Type | Name | Reference | 428 +------+-------------------------------+-----------------+ 429 | 13 | Source-specific Update | (this document) | 430 | 14 | Source-specific Request | (this document) | 431 | 15 | Source-specific Seqno Request | (this document) | 432 +------+-------------------------------+-----------------+ 434 8. Security considerations 436 The extension defined in this document adds three new TLVs that are 437 source-specific generalisations of the TLVs already present in the 438 original Babel protocol. It does not by itself change the security 439 properties of the protocol. 441 9. References 443 9.1. Normative References 445 [BABEL] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, 446 February 2011. 448 [BABEL-EXT] 449 Chroboczek, J., "Extension Mechanism for the Babel Routing 450 Protocol", RFC 7557, May 2015. 452 9.2. Informative References 454 [SS-ROUTING] 455 Boutier, M. and J. Chroboczek, "Source-Specific Routing", 456 August 2014. 458 In Proc. IFIP Networking 2015. A slightly earlier 459 version is available online from http://arxiv.org/ 460 pdf/1403.0445. 462 Authors' Addresses 464 Matthieu Boutier 465 PPS, University of Paris-Diderot 466 Case 7014 467 75205 Paris Cedex 13 468 France 470 Email: boutier@pps.univ-paris-diderot.fr 472 Juliusz Chroboczek 473 PPS, University of Paris-Diderot 474 Case 7014 475 75205 Paris Cedex 13 476 France 478 Email: jch@pps.univ-paris-diderot.fr