| RFC 9079 | Source-Specific Routing in Babel | August 2021 |
| Boutier & Chroboczek | Standards Track | [Page] |
Source-specific routing, also known as Source Address DependentRouting (SADR), is an extension to traditional next-hop routing wherepackets are forwarded according to both their destination address and their sourceaddress. This document describes an extension for source-specific routingto the Babel routing protocol.¶
This is an Internet Standards Track document.¶
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 7841.¶
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained athttps://www.rfc-editor.org/info/rfc9079.¶
Copyright (c) 2021 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.¶
The Babel routing protocol[RFC8966] is a distance vectorrouting protocol for next-hop routing. In next-hop routing, each nodemaintains a forwarding table that maps destination prefixes to next hops.The forwarding decision is a per-packet operation that depends on thedestination address of the packets and on the entries of the forwardingtable. When a packet is about to be routed, its destination address iscompared to the prefixes of the routing table: the entry with the mostspecific prefix containing the destination address of the packet ischosen, and the packet is forwarded to the associated next hop. Next-hoprouting is a simple, well-understood paradigm that works satisfactorily ina large number of cases.¶
The use of next-hop routing limits the flexibility of the routingsystem in two ways. First, since the routing decision is local to eachrouter, a router A can only select a route ABC...Z if its neighbouringrouter B has selected the route BC...Z. Second, the only criterion usedby a router to choose a route is the destination address: two packets withthe same destination follow the same route. Yet, there are other data inthe IP header that could conceivably be used to guide the routing decision-- the Type of Service (ToS) octet and, of course, the source address.¶
Source-specific routing[SS-ROUTING], or Source AddressDependent Routing (SADR), is a modest extension to next-hop routing wherethe forwarding decision depends not only on the destination address butalso on the source address of the packet being routed, which makes itpossible for two packets with the same destination but different sourceaddresses to be routed following different paths.¶
This document describes a source-specific routing extension for theBabel routing protocol[RFC8966]. This involves minorchanges to the data structures, which must include a source prefix inaddition to the destination prefix already present, and some changes tothe Update, Route Request, and Seqno Request TLVs, which are extended witha source prefix. The source prefix is encoded using a mandatory sub-TLV([RFC8966],Section 4.4).¶
Multihoming is the practice of connecting a single network to two ormore transit networks. The main application of source-specific routing isa form of multihoming known as "multihoming with multiple addresses".¶
Classical multihoming consists of assigning a provider-independentrange of addresses to the multihomed network and announcing it to alltransit providers. While classical multihoming works well for largenetworks, the cost of obtaining a provider-independent address range andannouncing it globally in the Internet is prohibitive for small networks.Unfortunately, it is not possible to implement classical multihoming withordinary provider-dependent addresses: in a network connected to twoproviders A and B, a packet with a source address allocated by A needs tobe routed through the edge router connected to A. If it is routed throughthe edge router connected to B, it will most likely be filtered (dropped),in accordance with[BCP84].¶
In multihoming with multiple addresses, every host in the multihomednetwork is assigned multiple addresses, one for each transit provider.Additional mechanisms are needed in order (i) to choose, for each packet,a source address that is associated with a provider that is currently up,and (ii) to route each packet towards the router connected to the providerassociated with its source address. One might argue that multihoming withmultiple addresses splits the difficult problem of multihoming into twosimpler sub-problems.¶
The issue of choosing a suitable source address is a decision local tothe sending host and is an area of active research. The simplest solutionis to use a traditional transport-layer protocol, such as TCP, and toprobe all available source addresses at connection time, analogously towhat is already done with destination addresses, either sequentially[RFC6724] or in parallel[RFC8305]. Sincethe transport-layer protocol is not aware of the multiple availableaddresses, flows are interrupted when the selected provider goes down(from the point of view of the user, all TCP connections are dropped whenthe network environment changes). A better user experience can beprovided by making all of the potential source and destinationaddresses available to higher-layer protocols, either at the transport layer[RFC8684][RFC4960] or at the application layer[RFC8445].¶
Source-specific routing solves the problem of routing a packet to theedge router indicated by its source address. Every edge router announces into the routing domain a default route specific to the prefix associatedwith the provider it is connected to. This route is propagated all theway to the routers on the access link, which are therefore able to routeevery packet to the correct router. Hosts simply send packets to theirdefault router -- no host changes are necessary at the network layer.¶
In addition to multihoming with multiple addresses, we are aware of two applications of source-specific routing. Tunnels and VPNs are packetencapsulation techniques that are commonly used in the Internet toestablish a network-layer topology that is different from the physicaltopology. In some deployments, the default route points at the tunnel;this causes the network stack to attempt to send encapsulated packetsthrough the tunnel, which causes it to break. Various solutions to thisproblem are possible, the most common of which is to point a host route atthe tunnel endpoint.¶
When source-specific routing is available, it becomes possible toannounce through the tunnel a default route that is specific to the prefixserved by the tunnel. Since the encapsulated packets have a sourceaddress that is not within that prefix, they are not routed through thetunnel.¶
The third application of source-specific routing is controlled anycast.Anycast is a technique in which a single destination address is used torepresent multiple network endpoints, collectively called an "anycastgroup". A packet destined to the anycast group is routed to an arbitrarymember of the group, typically the one that is nearest according to therouting protocol.¶
In many applications of anycast, such as DNS root servers, thenondeterminism of anycast is acceptable; some applications, however,require finer control. For example, in some Content Distribution Networks(CDNs), every endpoint is expected to handle a well-defined subset of theclient population. With source-specific routing, it is possible for eachmember of the anycast group to announce a route specific to its clientpopulation, a technique that is both simpler and more robust than manuallytweaking the routing protocol's metric ("prepending" in BGP).¶
In ordinary next-hop routing, when multiple routing table entries matchthe destination of a packet, the "longest prefix rule" mandates that themost specific entry applies. The reason why this rule makes sense is thatthe set of prefixes has the following "tree property":¶
It would be a natural proposition to order pairs of prefixes pointwise:to define that (D,S) is more specific than (D',S') when D is more specificthan D and S is more specific than S'. Unfortunately, the set of pairs ofprefixes with the pointwise ordering doesn't satisfy the tree property.Indeed, consider the following two pairs:¶
(2001:db8:0:1::/64, ::/0) and (::/0, 2001:db8:0:2::/64)¶
These two pairs are not disjoint (a packet with destination2001:db8:0:1::1 and source 2001:db8:0:2::1 is matched by both), butneither is more specific than the other. The effect is that there is nonatural, unambiguous way to interpret a routing table such as thefollowing:¶
destination source next-hop 2001:db8:0:1::/64 ::/0 A ::/0 2001:db8:0:2::/64 B¶
A finer ordering of pairs of prefixes is required in order toavoid all ambiguities. There are two natural choices: destination-first ordering, where (D,S) is more specific than (D',S')when¶
and, symmetrically, source-first ordering, in which sources arecompared first and destinations second.¶
Expedient as it would be to leave the choice to the implementation,this is not possible: all routers in a routing domain must use the sameordering lest persistent routing loops occur. Indeed, consider thefollowing topology:¶
A --- B --- C --- D¶
Suppose that A announces a route for (::/0, 2001:db8:0:2::/64), whileD announces a route for (2001:db8:0:1::/64, ::/0). Suppose further thatB uses destination-first ordering while C uses source-firstordering. Then a packet that matches both routes, say, with destination2001:db8:0:1::1 and source 2001:db8:0:2::1, would be sent by B towardsD and by C towards A and would therefore loop indefinitely between B andC.¶
This document mandates (Section 4) that all routersuse destination-first ordering, which is generally believed to be moreuseful than source-first ordering. Consider the following topology,where A is an edge router connected to the Internet and B is an internalrouter connected to an access network N:¶
(::/0, S) (D, ::/0) Internet --- A --- B --- N¶
A announces a source-specific default route with sourceS (::/0, S), while B announces a nonspecific route to prefix D.Consider what happens to a packet with a destination in D and a source inS. With destination-first ordering, the packet is routed towards thenetwork N, which is the only way it can possibly reach its destination.With source-first ordering, on the other hand, the packet is senttowards the Internet, with no hope of ever reaching its destination in N.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14[RFC2119][RFC8174] when, and only when, they appear in all capitals, as shown here.¶
A number of the conceptual data structures described inSection 3.2 of [RFC8966] contain a destination prefix. This specificationextends these data structures with a source prefix. Data from theoriginal protocol, which do not specify a source prefix, are stored witha zero-length source prefix, which matches the exact same set of packetsas the original, non-source-specific data.¶
Every Babel node maintains a source table, as described in[RFC8966],Section 3.2.5. A source-specific Babel nodeextends this table with the following field:¶
The source table is now indexed by 5-tuples of the form (prefix, plen,sprefix, splen, router-id).¶
Note that the route entry contains a source (see Sections2 and3.2.5of[RFC8966]) that itself contains both destination andsource prefixes. These are two different concepts and must not beconfused.¶
Every Babel node maintains a route table, as described in[RFC8966],Section 3.2.6. Each route table entry contains,among other data, a source, which this specification extends with a sourceprefix as described above. The route table is now indexed by 5-tuples ofthe form (prefix, plen, sprefix, splen, neighbour), where the first fourcomponents are obtained from the source.¶
Every Babel node maintains a table of pending seqno requests, asdescribed in[RFC8966],Section 3.2.7. Asource-specific Babel node extends this table with the following entry:¶
The table of pending seqno requests is now indexed by 5-tuples of theform (prefix, plen, sprefix, splen, router-id).¶
As noted inSection 1.3, source-specific tablescan, in general, be ambiguous, and all routers in a routing domain mustuse the same algorithm for choosing applicable routes. An implementationof the extension described in this documentMUST choose routing tableentries by using destination-first ordering, where routing tableentry R1 is preferred to routing table entry R2 when either R1'sdestination prefix is more specific than R2's or the destination prefixesare equal and R1's source prefix is more specific than R2's.¶
In practice, this means that a source-specific Babel implementationmust take care that any lower layer that performs packet forwarding obeythese semantics. More precisely:¶
This extension does not fundamentally change the operation of the Babelprotocol, and we therefore only describe differences between the originalprotocol and the extended protocol.¶
In the original protocol, three TLVs carry a destination prefix:Update, Route Request, and Seqno Request TLVs. This specification extendsthese messages so that they may carry a Source Prefix sub-TLV, asdescribed inSection 7. The sub-TLV ismarked as mandatory so that an unextended implementation will silentlyignore the whole enclosing TLV. A node obeying this specificationMUST NOT send a TLV with a zero-length source prefix; instead, it sends a TLVwith no Source Prefix sub-TLV. Conversely, an extended implementationMUST interpret an unextended TLV as carrying a source prefix of zerolength. Taken together, these properties ensure interoperability betweenthe original and extended protocols (seeSection 6).¶
This extension allows three TLVs of the original Babel protocol tocarry a source prefix: Update TLVs, Route Request TLVs, and Seqno RequestTLVs.¶
In order to advertise a route with a non-zero length source prefix,a node sends a source-specific update, i.e., an update with a SourcePrefix sub-TLV. When a node receives a source-specific update (prefix,source prefix, router-id, seqno, metric) from a neighbour neigh, itbehaves as described in[RFC8966],Section 3.5.3,except that the entry under consideration is indexed by (prefix, plen,sprefix, splen, neigh) rather than just (prefix, plen, neigh).¶
Similarly, when a node needs to send a request of either kind thatapplies to a route with a non-zero length source prefix, it sendsa source-specific request, i.e., a request with a Source Prefix sub-TLV.When a node receives a source-specific request, it behaves as described inSection 3.8 of [RFC8966], except that the request applies tothe route table entry carrying the source prefix indicated by theSource Prefix sub-TLV.¶
In the original protocol, the address encoding (AE) value 0 is used forwildcard messages: messages that apply to all routes of any addressfamily and with any destination prefix. Wildcard messages are allowed intwo places in the protocol: wildcard retractions are used to retract allof the routes previously advertised by a node on a given interface, andwildcard route requests are used to request a full dump of the route tablefrom a given node. Wildcard messages are intended to apply to all routes,including routes decorated with additional data and AE values to bedefined by future extensions; hence, this specification extendswildcard operations to apply to all routes, whatever the value of thesource prefix.¶
More precisely, a node receiving an update with the AE field set to0 and the Metric field set to infinity (a wildcard retraction)MUST applythe route acquisition procedure described inSection 3.5.3 of [RFC8966] to all of the routes that it has learned from the sendingnode, whatever the value of the source prefix. A nodeMUST NOT senda wildcard retraction with an attached source prefix, and a node thatreceives a wildcard retraction with a source prefixMUST ignore theretraction.¶
Similarly, a node that receives a route request with the AE field setto 0 (a wildcard route request)SHOULD send a full routing table dump,including routes with a non-zero length source prefix. A nodeMUST NOTsend a wildcard request that carries a source prefix, and a node receivinga wildcard request with a source prefixMUST ignore the request.¶
The protocol extension defined in this document is, to a great extent,interoperable with the base protocol defined in[RFC8966](and all previously standardised extensions). More precisely, ifnon-source-specific routers and source-specific routers are mixed ina single routing domain, Babel's loop-avoidance properties are preserved,and, in particular, no persistent routing loops will occur.¶
However, this extension is encoded using mandatory sub-TLVs, introducedin[RFC8966], and therefore is not compatible with theolder version of the Babel routing protocol[RFC6126], whichdoes not support mandatory sub-TLVs. Consequently, this extensionMUST NOT be used in a routing domain in which some routers implement[RFC6126];otherwise, persistent routing loops may occur.¶
In general, the discarding of source-specific routes bynon-source-specific routers will cause route starvation. Intuitively,unless there are enough non-source-specific routes in the network,non-source-specific routers will suffer starvation and discard packetsfor destinations that are only announced by source-specific routers.¶
In the common case where all source-specific routes are originated atone of a small set of edge routers, a simple yet sufficient condition foravoiding starvation is to build a connected source-specific backbone thatincludes all of the edge routers and announce a non-source-specificdefault route towards the backbone.¶
This extension defines a new sub-TLV used to carry a source prefix: theSource Prefix sub-TLV. It can be used within an Update, Route Request,or Seqno Request TLV to match a source-specific entry of the routetable in conjunction with the destination prefix natively carried bythese TLVs.¶
Since a source-specific routing entry is characterised by a singledestination prefix and a single source prefix, a source-specific message containsexactly one Source Prefix sub-TLV. A nodeMUST NOT send morethan one Source Prefix sub-TLV in a TLV, and a node receiving more thanone Source Prefix sub-TLV in a single TLVMUST ignore the TLV. ItMAYignore the whole packet.¶
0 1 2 3 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+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 128 | Length | Source Plen | Source Prefix...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-¶
Fields:¶
The length of the body TLV is normally of size 1+(Source Plen)/8rounded upwards. If the Length field indicates a length smaller thanthat, then the sub-TLV is corrupt, and the whole enclosing TLV must beignored; if the Length field indicates a length that is larger, then theextra octets contained in the sub-TLVMUST be silently ignored.¶
The contents of the Source Prefix sub-TLV are interpreted according tothe AE of the enclosing TLV. If a TLV with AE equal to 0 containsa Source Prefix sub-TLV, then the whole enclosing TLVMUST be ignored. Ifa TLV contains multiple Source Prefix sub-TLVs, then the whole TLVMUST beignored.¶
Note that this sub-TLV is a mandatory sub-TLV. Therefore, as describedinSection 4.4 of [RFC8966], the whole TLVMUST be ignored ifthat sub-TLV is not understood (or malformed).¶
The source-specific update is an Update TLV with a Source Prefixsub-TLV. It advertises or retracts source-specific routes in the samemanner as routes with non-source-specific updates (see[RFC8966]). A wildcard retraction (update with AE equal to 0)MUST NOT carry a Source Prefix sub-TLV.¶
Babel uses a stateful compression scheme to reduce the size taken bydestination prefixes in Update TLVs (seeSection 4.5 of [RFC8966]). The source prefix defined by this extension is notcompressed. On the other hand, compression is allowed for the destinationprefixes carried by source-specific updates. As described inSection 4.5 of [RFC8966], unextended implementations will correctlyupdate their parser state while otherwise ignoring the whole TLV.¶
A source-specific route request is a Route Request TLV with a SourcePrefix sub-TLV. It prompts the receiver to send an update for a givenpair of destination and source prefixes, as described inSection 3.8.1.1 of [RFC8966]. A wildcard request (route request with AEequal to 0)MUST NOT carry a Source Prefix sub-TLV; if a wildcard requestwith a Source Prefix sub-TLV is received, then the requestMUST beignored.¶
A source-specific seqno request is a Seqno Request TLV with a SourcePrefix sub-TLV. It requests that the receiving node perform the proceduredescribed inSection 3.8.1.2 of [RFC8966] but applied toa pair consisting of a destination and source prefix.¶
IANA has allocated sub-TLV number 128 for the Source Prefix sub-TLV inthe "Babel Sub-TLV Types" registry.¶
The extension defined in this document adds a new sub-TLV to threesub-TLVs already present in the original Babel protocol and does notchange the security properties of the protocol itself. However, theadditional flexibility provided by source-specific routing mightinvalidate the assumptions made by some network administrators, whichcould conceivably lead to security issues.¶
For example, a network administrator might be tempted to abuse routefiltering (Appendix C of [RFC8966]) as a security mechanism.Unless the filtering rules are designed to take source-specific routinginto account, they might be bypassed by a source-specific route, whichmight cause traffic to reach a portion of a network that was thought to beprotected. A network administrator might also assume that no routeis more specific than a host route and use a host route in order todirect traffic for a given destination through a security device (e.g.,a firewall); source-specific routing invalidates this assumption, and, insome topologies, announcing a source-specific route might conceivably beused to bypass the security device.¶
The authors are indebted toDonald Eastlake,Joel Halpern, andToke Hoiland-Jorgensen for their help with this document.¶