idnits 2.17.1 draft-boutier-homenet-source-specific-routing-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. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 3, 2013) is 3950 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'BAKER' is defined on line 365, but no explicit reference was found in the text == Unused Reference: 'TROAN' is defined on line 384, but no explicit reference was found in the text ** Obsolete normative reference: RFC 6126 (ref. 'BABEL') (Obsoleted by RFC 8966) == Outdated reference: A later version (-04) exists of draft-chroboczek-babel-extension-mechanism-00 == Outdated reference: A later version (-03) exists of draft-baker-ipv6-ospf-dst-src-routing-00 == Outdated reference: A later version (-01) exists of draft-troan-homenet-sadr-00 Summary: 4 errors (**), 0 flaws (~~), 6 warnings (==), 1 comment (--). 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 Intended status: Informational PPS, University of Paris-Diderot 5 Expires: January 4, 2014 July 3, 2013 7 Source-specific Routing 8 draft-boutier-homenet-source-specific-routing-00 10 Abstract 12 Source-specific routing is a generalisation of next-hop routing in 13 which the routing decision is made depending on a packet's source 14 address in addition to the destination. We describe the motivation 15 for source-specific routing and our experiences with an experimental 16 extension of the Babel routing protocol that implements source- 17 specific routing. 19 Status of this Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at http://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on January 4, 2014. 36 Copyright Notice 38 Copyright (c) 2013 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 2. Source-specific routing . . . . . . . . . . . . . . . . . . . . 3 55 2.1. Usage scenarios . . . . . . . . . . . . . . . . . . . . . . 3 56 2.2. Routing tables . . . . . . . . . . . . . . . . . . . . . . 4 57 3. Implementation . . . . . . . . . . . . . . . . . . . . . . . . 6 58 4. Interoperability issues . . . . . . . . . . . . . . . . . . . . 7 59 4.1. Interoperability with next-hop routing . . . . . . . . . . 7 60 4.2. Other forms of specific routing . . . . . . . . . . . . . . 7 61 5. Applicability to link-state protocols . . . . . . . . . . . . . 8 62 6. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 8 63 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 64 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 66 1. Introduction 68 The main routing paradigm deployed on the Global Internet is next-hop 69 routing. In next-hop routing, routing decisions are performed per- 70 packet, and consist in examining a packet's destination address only, 71 and mapping it to a next-hop router. 73 The use of next-hop routing restricts the flexibility of the routing 74 system in two ways. First, since a router only controls the next 75 hop, a route can only be selected by the network if it has a selected 76 route as its suffix, which makes some forms of global optimisation 77 difficult or impossible. Other routing paradigms, such as circuit 78 switching, label switching and source routing, do not have this 79 limitation. (Source-routing, in particular, has been proposed 80 multiple times as a suitable routing paradigm for the Global Internet 81 [CLARK]), but has been forbidden due to claimed security reasons 82 [RFC5095]. 84 Second, the only decision criterion used by a router is the 85 destination address. This implies that two packets with the same 86 destination are routed identically, which is not always desirable. 87 There are other data in the IP header that can be reasonably used for 88 making a routing decision -- the TOS octet, the flow-id, and, of 89 course, the source address. 91 2. Source-specific routing 93 Source-specific routing is a modest extension of next-hop routing. 94 In source-specific routing, just like in next-hop routing, a router's 95 role is limited to computing a next hop. Unlike in next-hop routing, 96 however, it can use both the destination and the source address in 97 order to perform this computation. In effect, source-specific 98 routing gives a modest amount of routing control to the sending host, 99 which can choose among potentially many source addresses, while 100 leaving routing decisions firmly in the control of the routers. 102 2.1. Usage scenarios 104 2.1.1. Simple multihoming 106 Consider a multihomed network connected to two (or more) providers, 107 for example a home network with two ADSL lines, or one ADSL line and 108 one cellular connection. We assume no cooperation between the two 109 providers, so that there are two edge routers ("CPEs"), one for each 110 provider. We further assume that one or both ISPs might be hostile 111 to multihoming, so that solutions requiring changes to the on-the- 112 wire packet format are not applicable. 114 ISP A ISP B 115 | | 116 | | 117 CPE A CPE B 118 \ / 119 \ / 120 \ / 121 end user network 123 Each provider grants the network a range of addresses that can be 124 assigned to nodes. A node can choose to configure with an address 125 from one of the two ranges, or to configure two addresses, one from 126 each range; it will then need to choose, for each packet being sent, 127 an address to use as the source address. 129 Since providers hopefully implement source address filtering [BCP38], 130 the network must choose the edge router through which to route a 131 packet depending on its source. 133 2.1.2. Tunnels and VPNs 135 Tunnels and VPNs are commonly used to establish a network-layer 136 topology that is different from the physical topology, notably for 137 security reasons. In many tunnel or VPN deployments, the end network 138 uses its native default route, and only routes some set of prefixes 139 through the tunnel or VPN. 141 In some deployments, however, the default route points at the tunnel. 142 If this is done naively, the network stack attempts to route the 143 encapsulated packets through the tunnel itself, which causes the 144 tunnel to break. Many workarounds are possible, the simplest being 145 to point a host route towards the tunnel endpoint through the native 146 interface. 148 Source-specific routing provides a clean solution to that problem. 149 The native default route is kept unchanged, while a source-specific 150 default route is installed through the tunnel. The source-specific 151 route being more specific than the native default route, packets from 152 the user network are routed through the tunnel, while the 153 encapsulated packets sourced at the edge router follow the native, 154 non-specific route. 156 2.2. Routing tables 158 In classical next-hop routing, every router maintains a routing 159 table, a set of pairs (D, NH), where D is a destination prefix and NH 160 the corresponding next-hop router. When a packet with destination 161 address d is routed, an entry (D, NH) such that d is in D is 162 selected, and the packet is sent to the corresponding NH. 164 In a source-specific router, the routing table is a set of triples of 165 the form (D, S, NH), where D is a destination prefix, S a source 166 prefix, and NH the next-hop router. When a packet with destination d 167 and source s is routed, an entry (D, S, NH) is selected such that d 168 is in D and s is in S, and the packet is sent to the corresponding 169 NH. 171 2.2.1. Ambiguity 173 The two procedures described above omit an important detail: in 174 general, there are multiple routing table entries that match a given 175 packet. A router must therefore choose one among these entries in 176 order to determine a next hop. 178 In next-hop routing, if two routing table entries overlap, then one 179 is necessarily more specific than the other; the "longest prefix 180 rule" specifies that the most specific applicable routing table entry 181 is chosen. In source-specific routing, this is no longer the case: 182 there might, in general, be multiple applicable entries with none 183 being included in the others. 185 Consider the following fragment of a routing table: 187 (2001:DB8:0:1::/64, ::/0, A) 188 (::/0, 2001:DB8:0:2::/64, B) 190 This specifies that all packets with destination in 2001:DB8:0:1::/64 191 are to be routed through A, while packets with a source in 2001:DB8: 192 0:2::/64 are to be routed through B. A packet with source 2001:DB8:0: 193 2::42 and destination 2001:DB8:0:1::57 matches both rules, although 194 neither is more specific than the other. 196 We say that a routing table such as the above is ambiguous. Most 197 practical routing tables with source-specific routes turn out to be 198 ambiguous. 200 2.2.2. Resolving ambiguity 202 In the presence of ambiguity, routing tables should be considered by 203 destination first; intuitively, "the destination wins". (We are 204 indebted to Fred Baker, who explained that to us.) 206 Consider the following network topology: 208 ::/0 --- A --- B --- C --- 2001:DB8:0:1::/64 210 Suppose that the routing table at B contains a source-specific 211 default route through A and a non-specific route towards 2001:DB8:0: 212 1::/64 through C. The correct behaviour is clearly to send a packet 213 destined to 2001:DB8:0:1::/64 through C -- this is the only choice 214 that has a chance of getting the packet to the right destination. 216 It is important to note that all routers in the same routing domain 217 must have the exact same behaviour in the presence of ambiguity, lest 218 persistent routing loops occur. Indeed, consider again the example 219 above; if router C implements a "source first" disambiguation 220 behaviour, then it will send B's packets back to B, which in turn 221 will send it back to B, etc. 223 2.2.3. Disambiguation routes 225 Ideally, we would like the lower layers of the system (the OS kernel, 226 the line cards, etc.) to implement source-specific routing tables out 227 of the box, with the right disambiguation behaviour already present. 228 In practice, however, we have found that such lower-layer support 229 either doesn't exist, doesn't work, or has a behaviour different from 230 the one desired. 232 In order to work with the limitations of the lower layers, we 233 introduce disambiguation routes. A disambiguation route is a route 234 that covers the intersection of two ambiguous routes, and therefore 235 specifies the behaviour of packets that match both. Disambiguation 236 routes do not appear on the wire, and in our implementation are not 237 even inserted into the RIB; they are computed and inserted into the 238 FIB on the fly, at route selection time. From the point of view of 239 the routing protocol, disambiguation routes are a lower level 240 implementation detail. 242 Interestingly enough, we have found that we do not need to maintain a 243 list of disambiguation routes that we have installed: when removing a 244 route from the FIB, the set of disambiguation routes that need to be 245 removed can be computed on the fly, similarly to what happens during 246 route insertion. 248 3. Implementation 250 We have implemented a source-specific variant of the Babel routing 251 protocol [BABEL] for the Linux kernel. We first attempted to use the 252 source-specific API provided by Linux; it turns out that this API is 253 specific to IPv6, and only works in a very restricted case, 254 insufficient for our needs. 256 We have therefore chosen to use the "rule" API, which allows a 257 routing daemon to use multiple routing tables that are combined using 258 a fairly flexible set of "rules". We use a dynamically allocated set 259 of routing tables, and manage routing rules on the fly. The use of 260 disambiguation routes is essential to obtaining the right behaviour. 262 4. Interoperability issues 264 4.1. Interoperability with next-hop routing 266 In many networks, only some routers will need to perform source- 267 specific routing decisions. For example, in a typical multihomed 268 network the two specific default routes will match in most of the 269 network, and only be distinguished near the edge routers. Our 270 implementation allows running a base version of Babel within most of 271 the network, and only run a source-specific daemon where the specific 272 routes are distinct. 274 Source-specific routes are encoded within the protocol as a new TLV 275 type, in accordance with the Babel extension mechanism [BABEL-EXT]. 276 This new TLV will be silently ignored by base Babel routers, which 277 will therefore route packets following non-specific routes only. 279 Hybrid networks consisting of base and source-specific routers do not 280 cause persistent routing loops. However, since non-specific routers 281 do not see source-specific routes, they might drop packets unless 282 they have enough non-specific routes; distributing a non-specific 283 default route throughout the network solves this particular issue in 284 all cases. 286 Additionally, since non-specific routers do not propagate specific 287 routes, packets may end up routed to the wrong destination unless 288 there are enough specific routers to propagate all the specific 289 routes throughout the network. A simple solution is to ensure that 290 the specific routers form a connected subgraph, which, at worst, can 291 be achieved by using tunnels. Intuitively, such a network consists 292 of a source-specific backbone together with a set of non-specific 293 leaf networks. 295 4.2. Other forms of specific routing 297 The technology described in this document is fully general, and 298 applies equally well to other forms of specific routing (say, TOS- 299 specific or flow-id-specific routing). In the presence of multiple 300 forms of specific routing, a natural question to ask is whether they 301 can interoperate in a single routing domain. 303 In general, such interoperability is possible assuming that the 304 preference rules of all the implementations are subsets of a single 305 total order on all of the routing criteria; equivalently, there must 306 exist a consistent linearisation of all of the orderings used by the 307 different implementations. Indeed, consider again a simple linear 308 topology: 310 X --- A --- B --- Y 312 Suppose that X announces a source-specific default route, while Y 313 announces a flow-id-specific default route. A packet that matches 314 both routes must be treated consistently by A and B, lest a routing 315 loop arise. 317 A simple (if brutal) way of meeting the linearisation requirement is 318 to require all routers to be specific in one dimension only: to allow 319 a router to perform source-specific routing, flow-id-specific 320 routing, but not both at the same time. 322 5. Applicability to link-state protocols 324 While our implementation is an extension of the Babel routing 325 protocol, our work applies equally well to any distance vector 326 routing protocol, such as RIPv2, RIPng or EIGRP. The question 327 remains about link-state routing protocols. 329 The currently deployed link-state protocols (OSPF and IS-IS) are 330 actually hybrid protocols: they divide the network into areas, and 331 perform link-state routing within areas and distance-vector routing 332 within areas. We are therefore confident that our techniques can be 333 used to extend link-state protocols with source-specific inter-area 334 routing (a simplified case of that has been implemented for OSPF 335 [STENBERG]); in OSPF terms, source-specific routes are analoguous to 336 Type 5 LSAs. 338 Whether it is possible to extend the current link-state protocols 339 with support for intra-area source-specific routing, or whether it is 340 desirable to do so, are currently open questions. 342 6. Conclusions 344 Source-specific routing is a modest extension to ordinary next-hop 345 routing that makes a number of useful scenarios possible. In this 346 document, we have described the difficulties associated with source- 347 specific routing, and described the solution we adopted within our 348 implementation of source-specific routing within the Babel routing 349 protocol. 351 We expect our experience to be useful to future implementers of 352 source-specific routing within other routing protocols. 354 7. References 356 [BABEL] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, 357 February 2011. 359 [BABEL-EXT] 360 Chroboczek, J., "Extension Mechanism for the Babel Routing 361 Protocol", Internet 362 Draft draft-chroboczek-babel-extension-mechanism-00, 363 June 2013. 365 [BAKER] Baker, F., "IPv6 Source/Destination Routing using OSPFv3", 366 Internet Draft draft-baker-ipv6-ospf-dst-src-routing-00, 367 February 2013. 369 [BCP38] Ferguson, P. and D. Senie, "Network Ingress Filtering: 370 Defeating Denial of Service Attacks which employ IP Source 371 Address Spoofing", BCP 38, RFC 2827, May 2000. 373 [CLARK] Reed, D. and D. Clark, "Source Routing for Campus-wide 374 Internet Transport", September 1980. 376 [RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation 377 of Type 0 Routing Headers in IPv6", RFC 5095, 378 December 2007. 380 [STENBERG] 381 Stenberg, M., "Hnet (core) package", 2012, 382 . 384 [TROAN] Troan, O. and L. Colitti, "IPv6 Multihoming with Source 385 Address Dependent Routing (SADR)", Internet 386 Draft draft-troan-homenet-sadr-00. 388 Authors' Addresses 390 Matthieu Boutier 391 PPS, University of Paris-Diderot 392 Case 7014 393 75205 Paris Cedex 13, 394 France 396 Email: boutier@pps.univ-paris-diderot.fr 398 Juliusz Chroboczek 399 PPS, University of Paris-Diderot 400 Case 7014 401 75205 Paris Cedex 13, 402 France 404 Email: jch@pps.univ-paris-diderot.fr