Network Working Group M. Boutier Internet-Draft J. Chroboczek Updates: 6126 (if approved) PPS, University of Paris-Diderot Intended status: Experimental May 27, 2015 Expires: November 28, 2015 Source-Specific Routing in Babel draft-boutier-babel-source-specific-01 Abstract This document describes extensions to the Babel routing protocol to support source-specific routing. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on November 28, 2015. Copyright Notice Copyright (c) 2015 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 (http://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. Boutier & Chroboczek Expires November 28, 2015 [Page 1] Internet-Draft Source-Specific Routing in Babel May 2015 Table of Contents 1. Introduction and background . . . . . . . . . . . . . . . . . 2 2. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 2 2.1. The Source Table . . . . . . . . . . . . . . . . . . . . 2 2.2. The Route Table . . . . . . . . . . . . . . . . . . . . . 3 2.3. The Table of Pending Requests . . . . . . . . . . . . . . 3 3. Data Forwarding . . . . . . . . . . . . . . . . . . . . . . . 3 4. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 4 4.1. Updates . . . . . . . . . . . . . . . . . . . . . . . . . 4 4.2. Requests . . . . . . . . . . . . . . . . . . . . . . . . 5 5. Backwards compatibility . . . . . . . . . . . . . . . . . . . 5 5.1. Loop-avoidance . . . . . . . . . . . . . . . . . . . . . 6 5.2. Blackholes . . . . . . . . . . . . . . . . . . . . . . . 6 6. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 6 6.1. Source-Specific Update . . . . . . . . . . . . . . . . . 6 6.2. Source-Specific Request . . . . . . . . . . . . . . . . . 8 6.3. Source-Specific Seqno Request . . . . . . . . . . . . . . 8 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 8. Security considerations . . . . . . . . . . . . . . . . . . . 10 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 9.1. Normative References . . . . . . . . . . . . . . . . . . 10 9.2. Informative References . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 1. Introduction and background Source-specific routing is an extension to traditional next-hop routing where packets are routed according to both their destination and their source address. This document describes extensions to the Babel routing protocol [BABEL] to support source-specific routing. Background information about source-specific routing is provided in [SS-ROUTING]. 2. Data Structures This extension adds some data to the data structures maintained by a Babel node. 2.1. The Source Table Every Babel node maintains a source table, as described in [BABEL], Section 3.2.4. A source-specific Babel node extends this table with the following field: o the source prefix (sprefix, splen) specifying the source of packets to which this entry applies. Boutier & Chroboczek Expires November 28, 2015 [Page 2] Internet-Draft Source-Specific Routing in Babel May 2015 If splen is 0, then this is a non-specific entry, and is treated just like a source table entry defined by the original Babel protocol. With this extension the route entry contains a source which itself contains a source prefix. Notwithstanding the accidental similarity in their names, these are two very different concepts, and should not be confused. 2.2. The Route Table Every Babel node maintains a route table, as described in [BABEL], Section 3.2.5. With this extension, this table is indexed by the 5-tuple (prefix, plen, source prefix, source plen, router-id) obtained from the associated source table entry. 2.3. The Table of Pending Requests Every Babel node maintains a table of pending requests, as described in [BABEL], Section 3.2.6. A source-specific Babel node extends this table with the following entry: o the source prefix being requested. 3. Data Forwarding In next-hop routing, if two routing table entries overlap, then one is necessarily more specific than the other; the "longest prefix rule" specifies that the most specific applicable routing table entry is chosen. With source-specific routing, there might no longer be a most specific applicable prefix: two routing table entries might match a given packet without one necessarily being more specific than the other. Consider for example the following fragment of a routing table: (2001:DB8:0:1::/64, ::/0, A) (::/0, 2001:DB8:0:2::/64, B) This specifies that all packets with destination in 2001:DB8:0:1::/64 are to be routed through A, while packets with a source in 2001:DB8:0:2::/64 are to be routed through B. A packet with source 2001:DB8:0:2::42 and destination 2001:DB8:0:1::57 matches both rules, although neither is more specific than the other. A choice is necessary, and unless the choice being made is the same on all routers in a routing domain, persistent routing loops may occur. Boutier & Chroboczek Expires November 28, 2015 [Page 3] Internet-Draft Source-Specific Routing in Babel May 2015 A Babel implementation MUST choose routing table entries by using the so-called destination-first ordering, where a routing table entry R1 is preferred to a routing table entry R2 when either R1's destination prefix is more specific than R2's, or the destination prefixes are equal and R1's source prefix is more specific than R2's. (In more formal terms, routing table entries are compared using the lexicographic product of the destination prefix ordering by the source prefix ordering.) In practice, this means that a source-specific Babel implementation must take care that any lower layers that perform packet forwarding obey this semantics. In particular: o If the lower layers implement the destination-first ordering, then the Babel implementation MAY use them directly; o If the lower layers can hold source-specific routes, but not with the right semantics, then the Babel implementation MUST disambiguate the routing table by using a suitable disambiguation algorithm (see [SS-ROUTING] for such an algorithm). o If the lower layers cannot hold source-specific routes, then a Babel implementation SHOULD silently ignore any source-specific routes and MUST NOT reannounce them to other nodes. 4. Protocol Operation This extension does not fundamentally change the operation of the Babel protocol. 4.1. Updates This extension introduces a new kind of update, the source-specific update. Whenever a source-specific Babel node needs to send an update, it checks whether the update is for a source-specific route (a route with a source prefix of non-zero length); if that is the case, it MUST send a source-specific update (Section 6.1), and otherwise it MUST send a non-specific update ([BABEL], Section 4.4.9). Every Babel node maintains a source table, which it updates whenever it sends an Update ([BABEL], Section 3.7.3). A source-specific Babel node MUST update the source table not only when it sends an update, but also when it sends a source-specific update. Boutier & Chroboczek Expires November 28, 2015 [Page 4] Internet-Draft Source-Specific Routing in Babel May 2015 4.2. Requests This extension duplicates Babel's two request types: there are now two kinds of route requests (source-specific and unspecific), and, similarly, two kinds of seqno requests. This extension does not modify Babel's strategy for sending requests. Whenever a Babel node needs to send a request, it checks whether the request is for a source-specific route; if it is, it MUST send one of the request types defined in this document; if it is not, then it MUST send one of the request types defined in the original Babel specification. 4.2.1. Wildcard requests The Babel protocol provides the ability to request a full routing table dump by sending a "wildcard request", a route request with the AE field set to 0. This extension does not modify the semantics of wildcard requests: a wildcard request prompts a dump of non-specific routes only, and a Babel node SHOULD NOT send any source-specific updates in reply to a wildcard request. A different request is used for obtaining a dump of the source- specific routes in a node's routing table. A "source-specific wildcard request" is a source-specific request (Section 6.2) whose AE field is 0; it requests a dump of the receiving nodes source-specific routes only (routes with a source prefix length of 1 or more). A node SHOULD NOT send any non-specific updates in reply to a source- specific wildcard request. In consequence, a node requiring a full routing table dump must send both a non-specific wildcard request and a source-specific wildcard request. 5. Backwards compatibility The protocol extension defined in this document is, to a great extent, interoperable with the base protocol defined in [BABEL] (and all its known extensions). More precisely, if non-specific routers and source-specific routers are mixed in a single routing domain, Babel's loop-avoidance properties are preserved, and, in particular, no persistent routing loops will occur. However, unless there is a backbone of source-specific routers that connects all source-specific edge routers, blackholes might occur. Boutier & Chroboczek Expires November 28, 2015 [Page 5] Internet-Draft Source-Specific Routing in Babel May 2015 5.1. Loop-avoidance The extension defined in this protocol uses three new TLVs that mirror the existing TLVs for non-specific routing rather than using sub-TLVs to carry source prefix information. As discussed in Section 4 of [BABEL-EXT], this encoding ensures that non-specific routers will silently ignore the whole source-specific TLV, which is necessary to avoid persistent routing loops in hybrid networks. Consider two nodes A and B, with A source-specific announcing a route to (D, S). Suppose that B ignores the source information when it receives the update, and reannounces it as D. This is reannounced to A, which treats it as (D, ::/0). Packets destined to D but not sourced in S will be forwarded by A to B, and by B to A, causing a persistent routing loop: (D,S) (D,::/0) <-- <-- ------ A ----------------- B --> (D,::/0) 5.2. Blackholes In general, discarding of source-specific routes by non-specific routers will cause routing blackholes. Intuitively, unless there are enough non-specific routes in the network, non-specific routers will suffer starvation, and discard packets for destinations that are only announced by source-specific routers. A simple yet sufficient condition for avoiding blackholes is to build a connected source- specific backbone that includes all of the edge routers, and announce a (non-specific) default route towards the backbone. 6. Protocol Encoding This extension defines three new TLV types that are used by Source- Specific Babel nodes and silently ignored by ordinary Babel nodes, in accordance with [BABEL-EXT]. 6.1. Source-Specific Update Boutier & Chroboczek Expires November 28, 2015 [Page 6] Internet-Draft Source-Specific Routing in Babel May 2015 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 = 13 | Length | AE | Source Plen | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Plen | Omitted | Interval | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Seqno | Metric | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Prefix... +-+-+-+-+-+-+-+-+-+-+-+- | Source prefix... +-+-+-+-+-+-+-+-+-+-+-+- Fields: Type Set to 13 to indicate a source-specific update TLV. Length The length of the body, exclusive of the Type and Length fields. AE The encoding of the prefix field. Source Plen The length of the advertised source prefix. This MUST NOT be 0. Plen The length of the advertised destination prefix. Omitted The number of octets that have been omitted at the beginning of the advertised prefix and that should be taken from a preceding Update TLV with the flag with value 80 hexadecimal set. Interval An upper bound, expressed in centiseconds, on the time after which the sending node will send a new update for this prefix. This MUST NOT be 0 and SHOULD NOT be less than 10. The receiving node will use this value to compute a hold time for this routing table entry. The value FFFF hexadecimal (infinity) expresses that this announcement will not be repeated unless a request is received. Seqno The originator's sequence number for this update. Metric The sender's metric for this route. The value FFFF hexadecimal (infinity) means that this is a route retraction. Boutier & Chroboczek Expires November 28, 2015 [Page 7] Internet-Draft Source-Specific Routing in Babel May 2015 Prefix The destination prefix being advertised. This field's size is (Plen/8 - Omitted) rounded upwards. Source Prefix The source prefix being advertised. This field's size is (Source Plen)/8 rounded upwards. 6.2. Source-Specific Request 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 = 14 | Length | AE | Plen | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Plen | Prefix... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- | Source prefix... +-+-+-+-+-+-+-+-+-+-+-+- Fields: Type Set to 14 to indicate a Source-Specific Route Request TLV. Length The length of the body, exclusive of the Type and Length fields. AE The encoding of the prefix field. The value 0 (wildcard) requests a full dump of all the source-specific routes of the receving node (i.e. those with non-zero source prefix length). Plen The length of the requested destination prefix. Source Plen The length of the requested source prefix. This MUST NOT be 0, except for AE 0. Prefix The destination prefix being requested. This field's size is Plen/8 rounded upwards. Source Prefix The source prefix being advertised. This field's size is (Source Plen)/8 rounded upwards. 6.3. Source-Specific Seqno Request Boutier & Chroboczek Expires November 28, 2015 [Page 8] Internet-Draft Source-Specific Routing in Babel May 2015 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 = 15 | Length | AE | Plen | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Seqno | Hop Count | Source Plen | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Router-Id + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Prefix... +-+-+-+-+-+-+-+-+-+-+-+- | Source prefix... +-+-+-+-+-+-+-+-+-+-+-+- Fields: Type Set to 15 to indicate a Source-Specific Seqno Request TLV. Length The length of the body, exclusive of the Type and Length fields. AE The encoding of the prefix field. This MUST NOT be 0. Plen The length of the requested destination prefix. Seqno The sequence number that is being requested. Hop Count The maximum number of times that this TLV may be forwarded, plus 1. This MUST NOT be 0. Source Plen The length of the requested source prefix. This MUST NOT be 0. Router-Id The Router-ID associated to this route. Prefix The destination prefix being requested. This field's size is Plen/8 rounded upwards. Source Prefix The source prefix being advertised. This field's size is "Source Plen"/8 rounded upwards. A Source-Specific Seqno Request TLV prompts the receiving node to send an Update for the route specified by the AE, Plen, Prefix, Source Plen and Source Prefix fields, with either a router-id different from what is specified by the Router-Id field, or a Seqno no less than what is specified by the Seqno field. If this request Boutier & Chroboczek Expires November 28, 2015 [Page 9] Internet-Draft Source-Specific Routing in Babel May 2015 cannot be satisfied locally, then it is forwarded according to the rules set out in Section 3.8.1.2 of [BABEL]. Just like an ordinary Seqno Request, a Source-Specific Seqno Request MAY be sent to a multicast address but MUST NOT be forwarded to a multicast address and MUST NOT be forwarded to more than one neighbour. A Source-Specific Seqno Request MUST NOT be forwarded if its Hop Count field is 1. 7. IANA Considerations IANA is instructed to add the following entries to the "Babel TLV Types" registry: +------+-------------------------------+-----------------+ | Type | Name | Reference | +------+-------------------------------+-----------------+ | 13 | Source-specific Update | (this document) | | 14 | Source-specific Request | (this document) | | 15 | Source-specific Seqno Request | (this document) | +------+-------------------------------+-----------------+ 8. Security considerations The extension defined in this document adds three new TLVs that are source-specific generalisations of the TLVs already present in the original Babel protocol. It does not by itself change the security properties of the protocol. 9. References 9.1. Normative References [BABEL] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, February 2011. [BABEL-EXT] Chroboczek, J., "Extension Mechanism for the Babel Routing Protocol", RFC 7557, May 2015. 9.2. Informative References [SS-ROUTING] Boutier, M. and J. Chroboczek, "Source-Specific Routing", August 2014. Boutier & Chroboczek Expires November 28, 2015 [Page 10] Internet-Draft Source-Specific Routing in Babel May 2015 In Proc. IFIP Networking 2015. A slightly earlier version is available online from http://arxiv.org/ pdf/1403.0445. Authors' Addresses Matthieu Boutier PPS, University of Paris-Diderot Case 7014 75205 Paris Cedex 13 France Email: boutier@pps.univ-paris-diderot.fr Juliusz Chroboczek PPS, University of Paris-Diderot Case 7014 75205 Paris Cedex 13 France Email: jch@pps.univ-paris-diderot.fr Boutier & Chroboczek Expires November 28, 2015 [Page 11]