| 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
This document describes extensions 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 November 28, 2015.
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.
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].
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.4. A source-specific Babel node extends this table with the following field:
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.
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.
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:
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.
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:
This extension does not fundamentally change the operation of the Babel protocol.
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.
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.
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.
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.
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)
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.
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].
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:
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:
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:
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 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.
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) |
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.
| [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. |
| [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. |