idnits 2.17.00 (12 Aug 2021) /tmp/idnits28879/draft-baker-ipv6-ospf-extensible-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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 17, 2013) is 3380 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 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 F.J. Baker 3 Internet-Draft Cisco Systems 4 Intended status: Standards Track February 17, 2013 5 Expires: August 21, 2013 7 Extensible OSPF LSAs 8 draft-baker-ipv6-ospf-extensible-00 10 Abstract 12 This note describes the changes necessary for OSPFv3 to route 13 extensible classes of traffic. This implies not routing "to a 14 destination", but "traffic matching a classification tuple" which 15 includes a destination but may also include other attributes such as 16 the source address, DSCP, or Flow Label. 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 August 21, 2013. 35 Copyright Notice 37 Copyright (c) 2013 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 53 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 54 2. Theory of Routing . . . . . . . . . . . . . . . . . . . . . . 3 55 2.1. Dealing with ambiguity . . . . . . . . . . . . . . . . . 3 56 3. Extensions necessary for OSPFv3 . . . . . . . . . . . . . . . 4 57 3.1. OSPF optional data extensions . . . . . . . . . . . . . . 4 58 3.1.1. IPv6 Destination Prefix TLV . . . . . . . . . . . . . 4 59 3.1.2. IPv6 Forwarding Address TLV . . . . . . . . . . . . . 5 60 3.1.3. Referenced Advertising Router TLV . . . . . . . . . . 5 61 3.1.4. Metric TLV . . . . . . . . . . . . . . . . . . . . . 6 62 3.1.5. External Route Tag TLV . . . . . . . . . . . . . . . 6 63 3.1.6. Referenced Link State ID TLV . . . . . . . . . . . . 7 64 3.2. OSPF extensible LSAs . . . . . . . . . . . . . . . . . . 7 65 3.2.1. Extensible-Inter-area-prefix-LSA . . . . . . . . . . 8 66 3.2.2. Extensible-AS-external-LSA . . . . . . . . . . . . . 9 67 3.2.3. Extensible-Intra-Area-Prefix-LSA . . . . . . . . . . 9 68 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 69 5. Security Considerations . . . . . . . . . . . . . . . . . . . 10 70 6. Privacy Considerations . . . . . . . . . . . . . . . . . . . 11 71 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 72 8. Change Log . . . . . . . . . . . . . . . . . . . . . . . . . 11 73 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 74 9.1. Normative References . . . . . . . . . . . . . . . . . . 11 75 9.2. Informative References . . . . . . . . . . . . . . . . . 11 76 Appendix A. FIB Design . . . . . . . . . . . . . . . . . . . . . 11 77 A.1. Linux Source-Address Forwarding . . . . . . . . . . . . . 12 78 A.1.1. One FIB per source prefix . . . . . . . . . . . . . . 12 79 A.1.2. One FIB per source prefix plus a general FIB . . . . 13 80 A.2. PATRICIA . . . . . . . . . . . . . . . . . . . . . . . . 13 81 A.2.1. Virtual Bit String . . . . . . . . . . . . . . . . . 13 82 A.2.2. Tree Construction . . . . . . . . . . . . . . . . . . 14 83 A.2.3. Tree Lookup . . . . . . . . . . . . . . . . . . . . . 15 84 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 15 86 1. Introduction 88 In related documents, the author proposes extensions to OSPF and IS- 89 IS for the routing of IPv6 traffic using more than the destination 90 address as the definition of a class of traffic to be routed. These 91 include the possibility of source/destination routing, and especially 92 egress routing, routing based on the destination plus the DSCP value 93 such as is discussed in [RFC4915], and routing using the destination 94 plus the IPv6 Flow Label for a form of Role Based Access Control - if 95 the sender doesn't know the flow label value that the receiver is 96 using, which it would learn from the network administrator through 97 configuration, DHCP, or some other means, it in effect has no route 98 to the destination. 100 These capabilities, in OSPFv3, are have as a premise an extensible 101 LSA; an LSA that contains the necessary elements of any LSA as 102 discussed in section 4.4.1 of [RFC5340], a destination address, and a 103 set of options. This document describes extensible inter-area- 104 prefix-LSAs, intra-area-prefix-LSAs, and AS-external-LSAs. 105 Additional options are defined in other documents. 107 Existing OSPF LSAs that specify only a destination prefix may be 108 understood as identifying a destination prefix and "any" other 109 option, whether it be source address, flow label, or something else. 110 This is also a useful class of traffic to compactly represent, so 111 existing LSA types are not deprecated, merely added to. 113 1.1. Requirements Language 115 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 116 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 117 document are to be interpreted as described in [RFC2119]. 119 2. Theory of Routing 121 Both IS-IS and OSPF perform their calculations by building a routes 122 from the router performing the calculation to each router, and then 123 use those routes to get to destinations that those routes advertise 124 connectivity to. Following the SPF algorithm, calculation starts by 125 selecting a starting point (typically the router doing the 126 calculation), and successively adding {link, router) pairs until one 127 has calculated a route to every router in the network. As each 128 router is added, including the original router, destinations that it 129 is directly connected to are turned into routes in the route table: 130 "to get to 2001:db8::/32, route traffic to {interface, list of next 131 hop routers}". For immediate neighbors to the originating router, of 132 course, there is no next hop router; traffic is handled locally. 134 2.1. Dealing with ambiguity 136 In any routing protocol, there is the possibility of ambiguity. An 137 area border router might, for example, summarize the routes to other 138 areas into a small set of relatively short prefixes, which have more 139 specific routes within the area. Traditionally, we have dealt with 140 that using a "longest match first" rule. If the same datagram 141 matches more than one destination prefix advertised within the area, 142 we follow the route to the longest matching prefix. 144 When routing a class of traffic, we follow an analogous "most 145 specific match" rule; we follow the route for the most specific 146 matching tuple. In cases of simple overlap, such as routing to 147 2001:db8::/32 or 2001:db8:1::/48, that is exactly analogous; we 148 choose one of the two routes. 150 It is possible, however, to construct an ambiguous case in which 151 neither class subsumes the other. For example, presume that 153 o A is a prefix, 155 o B is a more-specific prefix within A, 157 o C is a different prefix, and 159 o D is a more-specific prefix of C. 161 The two classes {A, D, *, *} and {B, C, *, *} are ambiguous: a 162 datagram within {B, D, *, *} matches both classes, and it is not 163 clear in the data plane what decision to make. Solving this requires 164 the addition of a third route in the FIB corresponding to the class 165 {B, D, *, *}, which is more-specific than either of the first two, 166 and can be given routing guidance based on metrics or other policy in 167 the usual way. 169 3. Extensions necessary for OSPFv3 171 Changing OSPF to provide for this type of change requires cloning 172 many of the existing LSAs: the inter-area-prefix-LSAs, the AS- 173 external-LSAs, and the intra-area-prefix LSA. This can be done 174 specifically with the information we have thought about, or designed 175 for extensibility. We choose extensibility. 177 3.1. OSPF optional data extensions 179 This section defines a number of optional type-length-value (TLV) 180 information elements that may be included in an extensible LSA. In 181 an extensible LSA, elements not included are not considered in 182 classification and as a result are in effect wild-carded. 184 3.1.1. IPv6 Destination Prefix TLV 186 The IPv6 Destination Prefix TLV MAY be used with the IPv6 Source 187 Prefix TLV, but MUST NOT be used with the IPv4 Source Prefix TLV or 188 the IPv4 Destination Prefix TLV. 190 0 1 2 3 191 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 192 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 193 | Type | Length |Prefix Length | Prefix 194 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 196 Destination Prefix TLV 198 Destination Prefix Type: assigned by IANA 200 TLV Length: Length of the TLV in octets 202 Prefix Length: Length of the prefix in bits, in the range 0..128 204 Prefix: (Destination prefix length +7)/8 octets of prefix 206 3.1.2. IPv6 Forwarding Address TLV 208 The IPv6 Forwarding Address TLV is only used in the Extensible-AS- 209 external-LSA, and is optional. 211 0 1 2 3 212 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 213 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 214 | Type | Length | 128 bit IPv6 Address 215 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 217 IPv6 Forwarding Address TLV 219 Flow Label Type: assigned by IANA 221 TLV Length: Length of the TLV in octets 223 IPv6 Address: A fully qualified IPv6 address (128 bits). If 224 included, data traffic for the advertised destination will be 225 forwarded to this address. It MUST NOT be set to the IPv6 226 Unspecified Address (0:0:0:0:0:0:0:0) or an IPv6 Link-Local 227 Address (Prefix FE80/10). While OSPFv3 routes are normally 228 installed with link-local addresses, an OSPFv3 implementation 229 advertising a forwarding address MUST advertise a global IPv6 230 address. This global IPv6 address may be the next-hop gateway for 231 an external prefix or may be obtained through some other method 232 (e.g., configuration). 234 3.1.3. Referenced Advertising Router TLV 236 0 1 2 3 237 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 238 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 239 | Type | Length | Referenced Advertising Router 240 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 241 | | 242 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 244 Referenced Advertising Router TLV 246 Flow Label Type: assigned by IANA 248 TLV Length: Length of the TLV in octets 250 Referenced Link State ID: With the Referenced Link State ID TLV 251 (Referenced LS Type and Referenced Link State ID), Identifies the 252 router-LSA or network-LSA with which the IPv6 traffic classes 253 should be associated. If Referenced LS Type is 0x2001, the 254 prefixes are associated with a router-LSA, Referenced Link State 255 ID should be 0, and Referenced Advertising Router should be the 256 originating router's Router ID. If Referenced LS Type is 0x2002, 257 the prefixes are associated with a network-LSA, Referenced Link 258 State ID should be the Interface ID of the link's Designated 259 Router, and Referenced Advertising Router should be the Designated 260 Router's Router ID. 262 3.1.4. Metric TLV 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 | Length | Metric | 268 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 269 | PrefixOptions | Information elements for the traffic class 270 +-+-+-+-+-+-+-+-+ 272 Metric TLV 274 Flow Label Type: assigned by IANA 276 TLV Length: Length of the TLV in octets 278 Metric: The cost of this traffic class. Expressed in the same units 279 as the interface costs in router-LSAs. 281 Information Elements This information element will be followed by 282 zero or more information elements that describe the traffic class. 283 the traffic class will have been fully described when parsing 284 reaches the end of the LSA or finds a new Metric TLV. 286 3.1.5. External Route Tag TLV 287 The External Route Tag TLV is only used in the Extensible-AS- 288 external-LSA, and is optional. 290 0 1 2 3 291 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 292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 293 | Type | Length | External Route Tag 294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 296 External Route Tag TLV 298 Flow Label Type: assigned by IANA 300 TLV Length: Length of the TLV in octets 302 Route Tag: A 32-bit field that MAY be used to communicate additional 303 information between AS boundary routers. 305 3.1.6. Referenced Link State ID TLV 307 0 1 2 3 308 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 309 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 310 | Type | Length | Referenced LS Type | 311 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 312 | Referenced Link State ID | 313 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 315 Referenced Link State ID TLV 317 Flow Label Type: assigned by IANA 319 TLV Length: Length of the TLV in octets 321 Referenced LS Type: The LSType of the associate LSA. 323 Referenced Link State ID: If included, additional information 324 concerning the advertised external route can be found in the LSA 325 having LS type equal to "Referenced LS Type", Link State ID equal 326 to "Referenced Link State ID", and Advertising Router the same as 327 that specified in the Extensible-AS-external-LSA's link-state 328 header. This additional information is not used by the OSPF 329 protocol itself. It may be used to communicate information 330 between AS boundary routers. The precise nature of such 331 information is outside the scope of this specification. 333 3.2. OSPF extensible LSAs 334 This section defines the extensible Extensible-Inter-Area-Prefix-LSA, 335 Extensible-AS-external-LSA, and Extensible-Intra-Area-Prefix LSA. 337 3.2.1. Extensible-Inter-area-prefix-LSA 339 Extensible-Inter-area-prefix-LSAs have LS type equal to [IANA?]. 340 These LSAs are equivalent to OSPFv2's type 3 summary-LSAs (see 341 Section 12.4.3 of [RFC2328]). Originated by area border routers, 342 they describe IPv4 or IPv6 traffic classes that belong to other 343 areas, and are encoded using the TLVs defined in Section 3.1. A 344 separate inter-area-prefix-LSA is originated for each such traffic 345 class. For details concerning the construction of inter-area- 346 prefix-LSAs, see [RFC5340] Section 4.4.3.4. 348 For stub areas, inter-area-prefix-LSAs can also be used to describe a 349 (per-area) default route. Default summary routes are used in stub 350 areas instead of flooding a complete set of external routes. When 351 describing a default summary route, the Extensible-inter-area-prefix- 352 LSA omits the Destination Prefix information element, which has the 353 same effect as matching 0.0.0.0/0 or ::/0. 355 0 1 2 3 356 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 357 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 358 | LS Age |0|0|1| LS-Type | 359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 360 | Link State ID | 361 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 362 | Advertising Router | 363 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 364 | LS Sequence Number | 365 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 366 | LS Checksum | Length | 367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 368 | 0 | Metric | 369 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 370 | Zero or more Information Element TLVs 371 + 373 Figure 1: Extensible-Inter-area-prefix-LSA 375 LS-Type: To be assigned by IANA 377 Metric: The cost of this route. Expressed in the same units as the 378 interface costs in router-LSAs. When the Extensible-inter-area- 379 prefix-LSA is describing a route to a range of addresses (see 380 [RFC5340] Appendix C.2), the cost is set to the maximum cost to 381 any reachable component of the address range. 383 3.2.2. Extensible-AS-external-LSA 385 This is an AS-external-LSAs, but may include other information 386 elements. Unlike the AS-external-LSAs, however, the presence of 387 optional information is determined by the presence of the information 388 elements, not by flags. 390 0 1 2 3 391 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 392 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 393 | LS Age |0|1|0| Type | 394 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 395 | Link State ID | 396 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 397 | Advertising Router | 398 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 399 | LS Sequence Number | 400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 401 | LS Checksum | Length | 402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 403 | 0 |E|0 0| Metric | 404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 405 | One or more Information Element TLVs 406 + 408 Figure 2: Extensible-AS-external-LSA 410 E: The type of external metric. If bit E is set, the metric 411 specified is a Type 2 external metric. This means the metric is 412 considered larger than any intra-AS path. If bit E is zero, the 413 specified metric is a Type 1 external metric. This means that it 414 is expressed in the same units as other LSAs (i.e., the same units 415 as the interface costs in router-LSAs). 417 : The cost of this route. Interpretation depends on the external 418 type indication (bit E above). 420 3.2.3. Extensible-Intra-Area-Prefix-LSA 422 This LSA MUST include a Referenced Link State ID TLV and a Referenced 423 Advertising Router TLV immediately following the number of traffic 424 classes. It MUST also include the indicated number of Metric TLVs, 425 each of which is followed by the information elements that define 426 that class of traffic, which will usually include a Destination 427 Prefix TLV and may include a source prefix TLV, Flow Label TLV, or 428 DSCP TLV. 430 Extensible-Intra-area-prefix-LSAs have LS types assigned by IANA. A 431 router uses Extensible-intra-area-prefix-LSAs to advertise one or 432 more traffic classes that are associated with a local router address, 433 an attached stub network segment, or an attached transit network 434 segment. In IPv4, the first two were accomplished via the router's 435 router-LSA and the last via a network-LSA. In OSPF for IPv6, all 436 addressing information that was advertised in router-LSAs and 437 network-LSAs has been removed and is now advertised in intra-area- 438 prefix-LSAs. For details concerning the construction of intra-area- 439 prefix-LSA, see [RFC5340] Section 4.4.3.9. 441 A router can originate multiple extensible-intra-area-prefix-LSAs for 442 each router or transit network. Each such LSA is distinguished by 443 its unique Link State ID. 445 0 1 2 3 446 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 447 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 448 | LS Age |0|0|1| 9 | 449 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 450 | Link State ID | 451 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 452 | Advertising Router | 453 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 454 | LS Sequence Number | 455 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 456 | LS Checksum | Length | 457 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 458 | # Traffic Classes | Information Elements 459 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 461 Figure 3: Extensible-Intra-Area-Prefix-LSA 463 # Traffic Classes: The number of traffic classes that will be 464 specified. Each traffic class has, first, a metric TLV, and then 465 one or more other TLVs, normally including a Destination Prefix 466 TLV. 468 4. IANA Considerations 470 This section will request LSID values for the LSAs defined, plus 471 define a registry for optional fields. This is deferred to the -01 472 version of the draft. 474 5. Security Considerations 476 To be considered. 478 6. Privacy Considerations 480 To be considered. 482 7. Acknowledgements 484 8. Change Log 486 Initial Version: February 2013 488 9. References 490 9.1. Normative References 492 [ISO.10589.1992] 493 International Organization for Standardization, 494 "Intermediate system to intermediate system intra-domain- 495 routing routine information exchange protocol for use in 496 conjunction with the protocol for providing the 497 connectionless-mode Network Service (ISO 8473)", ISO 498 Standard 10589, 1992. 500 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 501 Requirement Levels", BCP 14, RFC 2119, March 1997. 503 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 505 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 506 for IPv6", RFC 5340, July 2008. 508 9.2. Informative References 510 [PATRICIA] 511 Morrison, D.R., "Practical Algorithm to Retrieve 512 Information Coded in Alphanumeric", Journal of the ACM 513 15(4) pp514-534, October 1968. 515 [RFC4915] Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P. 516 Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF", RFC 517 4915, June 2007. 519 Appendix A. FIB Design 520 While the design of the Forwarding Information Base is not a matter 521 for standardization, as it only has to work correctly, not 522 interoperate with something else, the design of a FIB for this type 523 of lookup may differ from approaches used in destination routing. We 524 describe one possible approach that is known to work, from the 525 perspective of a proof of concept. 527 A.1. Linux Source-Address Forwarding 529 The University of Waikato has added to the Linux Advanced Routing & 530 Traffic Control facility the ability to maintain multiple FIBS, one 531 for each of a set of prefixes. Implementing source/destination 532 routing using this mechanism is not difficult. 534 The router must know what source prefixes might be used in its 535 domain. This may be by configuration or, at least in concept, 536 learned from the routing protocols themselves. In whichever way that 537 is done, one can imagine two fundamental FIB structures to serve N 538 source prefixes; N FIBs, one per prefix, or N+1 FIBs, one per prefix 539 plus one for destinations for which the source prefix is unspecified. 541 A.1.1. One FIB per source prefix 543 In an implementation with one FIB per source prefix, the routing 544 algorithm has two possibilities. 546 o If it calculates a route to a prefix (such as a default route) 547 associated with a given source prefix, it stores the route in the 548 FIB for the relevant source prefix. 550 o If it calculates a route for which the source prefix is 551 unspecified, it stores that route in all N FIBs. 553 When forwarding a datagram, the IP forwarder looks at the source 554 address of the datagram to determine which FIB it should use. If it 555 is from an address for which there is no FIB, the forwarder discards 556 the datagram as containing a forged source address. If it is from an 557 address within one of the relevant prefixes, it looks up the 558 destination in the indicated FIB and forwards it in the usual way. 560 The argument for this approach is simplicity: there is one place to 561 look in making a forwarding decision for any given datagram. The 562 argument against it is memory space; it is likely that the FIBs will 563 be similar, but every destination route not associated with a source 564 prefix is duplicated in each FIB. In addition, since it 565 automatically removes traffic whose source address is not among the 566 configured list, it limits the possibility of user software using 567 improper addresses. 569 A.1.2. One FIB per source prefix plus a general FIB 571 In an implementation with N+1 FIBs, the algorithm is slightly more 572 complex. 574 o If it calculates a route to a prefix (such as a default route) 575 associated with a given source prefix, it stores the route in the 576 FIB for the relevant source prefix. 578 o If it calculates a route for which the source prefix is 579 unspecified, it stores that route in the FIB that is not 580 associated with a source prefix. 582 When forwarding a datagram, the IP forwarder looks at the source 583 address of the datagram to determine which FIB it should use. If it 584 is from one of the configured prefixes, it looks the destination up 585 in the indicated FIB. In any event it also looks the destination up 586 in the "unspecified source address" FIB. If the destination is found 587 in only one of the two, the indicated route is followed. If the 588 destination is found in both, the more specific route is followed. 590 The argument for this approach is memory space; if a large percentage 591 of routes are only in the general FIB, such as when egress routing is 592 used for the default route and all other routes are internal, the 593 other FIBs are likely to be very small - perhaps only a single 594 default route. The argument against this approach is complexity: 595 most lookups if not all will be done in a prefix-specific FIB and in 596 the general FIB. 598 A.2. PATRICIA 600 One approach is a [PATRICIA] Tree. This is a relative of a Trie, but 601 unlike a Trie, need not use every bit in classification, and does not 602 need the bits used to be contiguous. It depends on treating the bit 603 string as a set of slices of some size, potentially of different 604 sizes. Slice width is an implementation detail; since the algorithm 605 is most easily described using a slice of a single bit, that will be 606 presumed in this description. 608 A.2.1. Virtual Bit String 610 It is quite possible to view the fields in a datagram header 611 incorporated into the classification tuple as a virtual bit string 612 such as is shown in Figure 4. This bit string has various regions 613 within it. Some vary and are therefore useful in a radix tree 614 lookup. Some may be essentially constant - all global IPv6 addresses 615 at this writing are within 2000::/3, for example, so while it must be 616 tested to assure a match, incorporating it into the radix tree may 617 not be very helpful in classification. Others are ignored; if the 618 destination is a remote /64, we really don't care what the EID is. 619 In addition, due to variation in prefix length and other details, the 620 widths of those fields vary among themselves. The algorithm the FIB 621 implements, therefore, must efficiently deal with the fact of a 622 discontiguous lookup key. 624 +---------------------+----------------------+-----+-----------+ 625 |Destination Prefix |Source Prefix |DSCP | Flow Label| 626 +------+------+-------+------+-------+-------+-----+-----------+ 627 Common|Varying|Ignored|Common|Varying|Ignored|Varying or ignored 629 Figure 4: Treating a traffic class as a virtual bit string 631 A.2.2. Tree Construction 633 The tree is constructed by recursive slice-wise decomposition. At 634 each stage, the input is a set of classes to be classified. At each 635 stage, the result is the addition of a lookup node in the tree that 636 identifies the location of its slice in the virtual bit string (which 637 might be a bit number), the width of the slice to be inspected, and 638 an enumerated set of results. Each result is a similar set of 639 classes, and is analyzed in a similar manner. 641 The analysis is performed by enumerating which bits that have not 642 already been considered are best suited to classification. For a 643 slice of N bits, one wants to select a slide that most evenly divides 644 the set of classes into 2^N subsets. If one or more bits in the 645 slice is ignored in some of the classes, those classes must be 646 included in every subset, as the actual classification of them will 647 depend on other bits. 649 Input:{2001:db8::/32, ::/0, *, *} 650 {2001:db8:1::/48, ::/0, AF41, *} 651 {2001:db8:1::/48, ::/0, AF42, *} 652 {2001:db8:1::/48, ::/0, AF43, *} 653 Common parts: Destination prefix 2001:dba, source prefix, and label 654 Varying parts: DSCP and the third set of sixteen bits in the 655 destination prefix 656 One possible decomposition: 657 (1) slice = DSCP 658 enumerated cases: 659 (a) { {2001:db8::/32, ::/0, *, *}, {2001:db8:1::/48, ::/0, AF41, *} } 660 (b) { {2001:db8::/32, ::/0, *, *}, {2001:db8:1::/48, ::/0, AF42, *} } 661 (c) { {2001:db8::/32, ::/0, *, *}, {2001:db8:1::/48, ::/0, AF43, *} } 662 (2) slice = third sixteen bit field in destination 663 This divides each enumerated case into those containing 0001 and 664 "everything else", which would imply 2001:db8::/32 665 (1) DSCP 666 -------------------------- 667 (1a) (1b) (1c) 668 / \ / \ / \ 669 /32 /48 /32 /48 /32 /48 671 Figure 5: Example PATRICIA Tree 673 A.2.3. Tree Lookup 675 To look something up in a PATRICIA Tree, one starts at the root of 676 the tree and performs the indicated comparisons recursively walking 677 down the tree until one reaches a terminal node. When the enumerated 678 subset is empty or contains only a single class, classification 679 stops. Either classification has failed (there was no matching 680 class, or one has presumably found the indicated class. At that 681 point, every bit in the virtual bit string must be compared to the 682 classifier; classification is accepted on a perfect match. 684 In the example in Figure 5, if a packet {2001:db8:1:2:3:4:5:6, 685 2001:db8:2:3:4:5:6:7, AF41, 0} arrives, we start at the root. Since 686 it is an AF41 packet, we deduce that case (1a) applies, and since the 687 destination has 0001 in the third sixteen bit field of the 688 destination address, we are comparing to {2001:db8:1::/48, ::/0, 689 AF41, *}. Since the destination address is within 2001:db8:1::/48, 690 classification as that succeeds. 692 Author's Address 694 Fred Baker 695 Cisco Systems 696 Santa Barbara, California 93117 697 USA 699 Email: fred@cisco.com