| Network Working Group | M. Boutier |
| Internet-Draft | J. Chroboczek |
| Updates: 6126bis (if approved) | IRIF, University of Paris-Diderot |
| Intended status: Standards Track | July 03, 2017 |
| Expires: January 4, 2018 |
Source-Specific Routing in Babel
draft-boutier-babel-source-specific-03
This document describes an extension to the Babel routing protocol to support source-specific routing.
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 January 4, 2018.
Copyright (c) 2017 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.
Source-specific routing (also known as Source Address Dependant Routing, SAD Routing or SADR) is an extension to traditional next-hop routing where packets are routed according to both their destination and their source address. This document describes the source-specific routing extension to the Babel routing protocol as defined in 6126bis [BABEL].
Background information about source-specific routing is provided in [SS-ROUTING].
This extension adds some data to the data structures maintained by a Babel node.
Every Babel node maintains a source table, as described in [BABEL], Section 3.2.5. A source-specific Babel node extends this table with the following field:
If a source table entry has a zero length source prefix (splen equals to 0), then the entry is a non-source-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. These are two very different concepts, and should not be confused.
Every Babel node maintains a route table, as described in [BABEL], Section 3.2.6. 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.
If a route table entry has a zero length source prefix, then the entry is a non-source-specific entry, and is treated just like a route table entry defined by the original Babel protocol.
Every Babel node maintains a table of pending requests, as described in [BABEL], Section 3.2.7. A source-specific Babel node extends this table with the following entry:
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:
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. More informations are available in [SS-ROUTING] Section IV.C.
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 layer that performs packet forwarding obey this semantics. In particular:
This extension does not fundamentally change the operation of the Babel protocol. We only describe the fundamental differences between the original protocol and the extension in this section. The other mechanisms described in [BABEL] (Section 3) are extended to pairs of (destination, source) prefixes instead of just (destination) prefixes.
Three messages are used to communicate informations on routes: Updates, Route Requests and Seqno Requests. With this extension, these messages carry an additionnal source prefix if (and only if) the corresponding route is source-specific. More formally, an Update, a Route Request and a Seqno Request MUST carry a source prefix if they concern a source-specific route (non-zero length source prefix) and MUST NOT carry a source prefix otherwise (zero length source prefix). A message which carries a source prefix is said to be source-specific.
When a non-source-specific Babel node receives a source-specific update, it silently ignores it.
TODO{On receipt of a source-specific update (id, prefix, source prefix, seqno, metric), a source-specific Babel node behaves as described in [BABEL] Section 3.5.4 though indexing entries by (neigh, id, prefix, source prefix).} When a source-specific Babel node receives a non-source-specific update, it MUST treat this update as carrying a zero length source prefix.
The original protocol defines a wildcard update with AE equals to 0 as being a wildcard retraction. A node receiving a wildcard retraction on an interface must consider that the sending node retracts all the routes it advertised on this interface.
Wildcard retractions are used when a node is about to leave the network. Thus, this extension does not define source-specific wildcard retraction, but extends wildcard retraction to apply also to source-specific routes. More formally, a wildcard update MUST NOT carry a source prefix, and a source-specific Babel node receiving a (legacy) wildcard update MUST retracts all routes it learns from this node (including source-specific ones).
TODO: behaviour to be defined.
The original Babel protocol states that when a node receives a wildcard route request, it SHOULD send a full routing table dump. This extension does not change this statement: a source-specific node SHOULD send a full routing table dump when receiving a wildcard request.
Source-specific wildcard requests does not exist: a wildcard request SHOULD NOT carry a source prefix.
We assume that a mandatory sub-TLV has a corresponding non-mandatory sub-TLV. This proposal is like Proposal 3 but instead of having multiple wildcard request TLVs, one for each kind of route understood, we use one wildcard request with sub-TLVs corresponding to the extension. To have a full routing table dump, a node sends a wildcard requests with a non-mandatory Source sub-TLV.
A source-specific node SHOULD always attach a non-mandatory Source sub-TLV to its wildcard requests.
This proposal has been rejected because it implies to share the space of non-mandatory and mandatory sub-TLVs.
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. As the original protocol has no source-specific routes, such a request may only concern non-source-specific routes. This extension does not modify the semantics of wildcard requests in that sense: a wildcard request prompts the receiver to send its non-source-specific routes only, and a Babel node SHOULD NOT send any source-specific updates in reply to a wildcard request.
To obtain a dump of the source-specific routes, a source-specific wildcard request MUST be used. A source-specific wildcard request is a wildcard request carrying a zero length source prefix.
When a node receives a source-specific wildcard request, it SHOULD send a dump of its routes which are source-specific "only". It SHOULD NOT send any non-source-specific routes in reply to a source-specific wildcard request. It SHOULD NOT send any source-specific routes which are under the effect of a future extension. Such extension should detail how to handle the possible combinations.
In consequence, a node requiring a full routing table dump must send both a non-source-specific wildcard request and a source-specific wildcard request.
Wildcard requests are deprecated. Either deprecate it in 6126bis, or say the following.
A node receiving a wildcard request SHOULD ignore it.
This proposal has been rejected because wildcard requests speeds up the convergence of the network on boot. This is considered important.
By default, a vanilla wildcard request triggers a dump of all non-specific routes. We define a new non-mandatory sub-TLV on Route Requests called "Requested Route Types" that contains an array of all the types of routes this request is requesting.
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 = TBD | Length | RR Type 1 | RR Type 2... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
We also create a registry of Requested Route (RR) types, for example:
A node receiving a Requested Route Types sub-TLV in a wildcard request SHOULD sends back a dump of all its routes corresponding to the requested types or to a combination of these types.
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-source-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, this extension is not compatible with the Experimental Track's Babel Routing Protocol (RFC 6126). It requires the mandatory sub-TLV introduced in [BABEL]. Consequently, this extension MUST NOT be used with routers implementing RFC 6126, otherwise persistent routing loops may occur.
The extension defined in this protocol uses a new Mandatory sub-TLV to carry the source prefix information. As discussed in Section 4.4 of [BABEL], this encoding ensures that non-source-specific routers will silently ignore the whole 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 merely ignores the source prefix information when it receives the update rather than ignoring the sub-TLV, and reannounces the route as D. This reannouncement reaches 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)
<-- <--
------ A ----------------- B
-->
(D,::/0)
In general, discarding source-specific routes by non-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 packets for destinations that are only announced by source-specific routers.
A simple yet sufficient condition for avoiding starvation is to build a connected source-specific backbone that includes all of the edge routers, and announce a (non-source-specific) default route towards the backbone.
This extension defines a new sub-TLV used to carry a source prefix by the three following existing messages: Update, Route Request and Seqno 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 = TBD | Length | Source Plen | Source Prefix... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields:
The Source Prefix field's encoding (AE) is the same as the Prefix's. It is defined by the AE field of the corresponding TLV.
Note that this sub-TLV is a Mandatory sub-TLV. The whole TLV MUST be ignored if that TLV is not recognized as described in Section 4.4. Otherwise, routing loops may occur.
The source-specific Update is an Update TLV with a Source Prefix sub-TLV. It advertises or retracts source-specific routes in the same manner than routes with non-source-specific Updates (see [BABEL]). This TLV MUST NOT be attached to wildcard updates.
Contrary to the destination prefix, this extension does not compress the source prefix attached to Updates. The destination prefix uses compression as defined in [BABEL] for Updates with Mandatory extensions.
However, as defined in [BABEL] (Section 4.5), the compression is allowed for the destination prefix of source-specific routes. Legacy implementation will correctly update their parser state, while ignoring the whole TLV afterwards.
TODO: A source-specific Route Request prompts the receiver to send an update for a given pair of destination and source prefixes. It MUST NOT be used to request a full routing table dump. The Source Prefix sub-TLV of a wildcard source-specific Route Request (Request with AE equals to 0 and a Source Prefix sub-TLV) MIGHT be ignored: a receiver MIGHT reply by a full routing table dump.
A source-specific Seqno Request is just like a Seqno Request for a source-specific route. It uses the same mechanisms described in [BABEL].
IANA is instructed to add the following entry to the "Babel sub-TLV Types" registry:
| Type | Name | Reference |
|---|---|---|
| TBD | Source Prefix | (this document) |
The extension defined in this document adds a new sub-TLV to three TLVs already present in the original Babel protocol. It does not by itself change the security properties of the protocol.
| [BABEL] | Chroboczek, J., "The Babel Routing Protocol", Internet Draft draft-ietf-babel-rfc6126bis-02, May 2017. |
| [SS-ROUTING] |
Boutier, M. and J. Chroboczek, "Source-Specific Routing", August 2014. In Proc. IFIP Networking 2015. A slightly earlier version is available online from http://arxiv.org/pdf/1403.0445. |