Network Working Group                                         M. Boutier
Internet-Draft                                             J. Chroboczek
Updates: 6126bis (if approved)         IRIF, University of Paris-Diderot
Intended status: Standards Track                         August 21, 2017       IRIF, University of Paris-Diderot
Expires: February 22, July 24, 2018                                  January 20, 2018

                    Source-Specific Routing in Babel


   Source-specific routing (also known as Source-Address Dependent
   Routing, SADR) is an extension to traditional next-hop routing where
   packets are forwarded according to both their destination and their
   source address.  This document describes the
   source-specific routing an extension to the Standard Track's Babel for source-
   specific routing protocol defined in [BABEL].  It is incompatible with to the
   Experimental Track's Babel [RFC6126].

   Source-specific routing is also known as Source Address Dependent
   Routing, SAD Routing, SADR, Destination/Source Routing or Source/
   Destination Routing. protocol.

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

   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 February 22, July 24, 2018.

Copyright Notice

   Copyright (c) 2017 2018 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
   ( 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.

Table of Contents

   1.  TODOs . . . . . . . . . . .  Introduction and background . . . . . . . . . . . . . . . . .   2
   2.  Introduction and background .  Specification of Requirements . . . . . . . . . . . . . . . .   2   3
   3.  Data Structures . . . . . . . . . . . . . . . . . . . . . . .   3
     3.1.  The Source Table  . . . . . . . . . . . . . . . . . . . .   3
     3.2.  The Route Table . . . . . . . . . . . . . . . . . . . . .   4
     3.3.  The Table of Pending Seqno Requests . . . . . . . . . . .   4
   4.  Data Forwarding . . . . . . . . . . . . . . . . . . . . . . .   4
   5.  Protocol Operation  . . . . . . . . . . . . . . . . . . . . .   5
     5.1.  Source-specific messages  . . . . . . . . . . . . . . . .   6
     5.2.  Route Acquisition . . . . . . . . . . . . . .  Protocol Messages . . . . . .   6
     5.3.  Wildcard retractions (update) . . . . . . . . . . . . . .   6
     5.2.  Wildcard requests Messages . . . . . . . . . . . . . . . . . . . .   6
   6.  Compatibility with the base protocol  . . . . . . . . . . . .   7
     6.1.  Loop-avoidance  . . . . . . . . . . . . . . . . . . . . .   7
     6.2.  Starvation and Blackholes . . . . . . . . . . . . . . . .   8   7
   7.  Protocol Encoding . . . . . . . . . . . . . . . . . . . . . .   8
     7.1.  Source Prefix sub-TLV . . . . . . . . . . . . . . . . . .   8
     7.2.  Source-specific Update  . . . . . . . . . . . . . . . . .   9
     7.3.  Source-specific (Route) Request . . . . . . . . . . . . .   9
     7.4.  Source-Specific Seqno Request . . . . . . . . . . . . . .   9
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   9
   9.  Security considerations . . . . . . . . . . . . . . . . . . .   9
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .  10
     10.1.  Normative References . . . . . . . . . . . . . . . . . .  10
     10.2.  Informative References . . . . . . . . . . . . . . . . .  10
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  10

1.  TODOs

   o  Source Prefix sub-TLV type: TBD

   o  check references (Section) for BABEL in 6126bis

2.  Introduction and background

   The Babel routing protocol as defined is [BABEL] is a distance vector routing
   protocol for next-hop routing.  In next-hop routing, each node
   maintains a forwarding table which maps destination prefixes to next-hops. next
   hops.  The forwarding decision is a per-packet operation which
   depends on the destination address of the packets and on the entries
   of the forwarding table.  When a packet is about to be routed, its
   destination address is compared to the prefixes of the routing table:
   the entry with the most specific prefix containing the destination
   address of the packet is choosen, chosen, and the packet is forwarded to the
   associated next-hop.  Next-hop routing is a simple, well understood
   paradigm that works satisfactorily in a large number of cases.

   Source-specific routing [SS-ROUTING], or Source Address Dependent
   Routing (SADR) [DSR], is a modest extension of to next-hop routing where
   the forwarding decision additionnaly depends not only on the destination address
   but also on the source address of the packets. packet being routed, which
   makes it possible for two packets with the same destination but
   different source addresses to be routed following different paths.
   The forwarding tables are extended to map pairs of prefixes
   (destination, source) to a next-hop. next hops.  When multiple entries are candidate to route match a
   given packet, the one with the most specific destination prefix is choosen, and
   chosen, and, in case of equality equality, the one with the most specific source.  In source-specific routing, two
   packets with the same destination but different sources may be
   forwarded among different paths.
   source prefix.

   The main application of source-specific routing is, at the time of
   this writing, is multihoming with Provider Agregatable (PA) addresses.
   In such configuration, each Internet Service Provider (ISP) provides
   to the network
   multiple addresses, a PA prefix technique for multihoming which, unlike
   multihoming, does not require the use of provider-independent
   addresses and does not cause excessive growth of the global routing
   table.  In a default route for network using this prefix while
   performing ingress filtering ([BCP84]).  Each form of multihoming, each host has is
   given multiple addresses, one address per ISP, and sends packets with upstream provider.  When a host
   sources a packet, it picks one of these its addresses as the source
   address.  Source-specific routing ensures that packets are routed
   towards the provider address
   of their source address, such the packet, and source-specific routing is used to route the
   packet to an edge router that they are not
   filtered out. is connected to the corresponding
   provider, which is compatible with [BCP84].  More details and more use cases can be found are given

   This document describes the a source-specific routing extension for the
   Babel routing protocol [BABEL].  This involves minor changes to the
   structures and protocol messages.  The data structures receive an
   additionnal structures, which must include a source prefix which is part of the index, similarly in addition to
   (and with)
   the destination prefix.  The prefix already present, and some changes to the
   Update, Route Request and Seqno Request are the three messages TLVs, which carry a (destination)
   prefix: they are extended with
   a source prefix.  The source prefix is encoded using a mandatory sub-
   TLV ([BABEL] Section 4.4).

2.  Specification of Requirements

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in [RFC2119].

3.  Data Structures


   A number of the conceptual data structures described in Section 3.2
   of a Babel node contains a destination
   prefix or are partly indexed by [BABEL] contain a destination prefix.  This extension
   adds a source prefix to specification extends
   these data structures and indexes. with a source prefix.  Data from the original
   protocol, which do not specify a source prefix, are stored with a
   zero length source prefix, which matches exactly the same set of
   packets as the original, non-source-specific data.

3.1.  The Source Table

   Every Babel node maintains a source table, as described in [BABEL], [BABEL]
   Section 3.2.5.  A source-specific Babel node extends this table with
   the following field.  With this extension, the source table is
   indexed by triples of the form (prefix, source prefix, router-id). field:

   o  the  The source prefix specifying the source address of packets to
      which this entry applies.

   If a

   The source table entry has a zero length source prefix, then the
   entry is a non-source-specific entry, and is treated just like a
   source table entry defined now indexed by triples of the original Babel protocol.

   With this extension, form (prefix,
   source prefix, router-id).

   Note that the route entry contains a source which itself contains a
   source prefix.  These are two very different concepts, and concepts that should not
   be confused.

3.2.  The Route Table

   Every Babel node maintains a route table, as described in [BABEL], [BABEL]
   Section 3.2.6.  With  Each route table entry contains, among other data, a
   source, which this extension, the specification extends with a source prefix as
   described above.  The route table is now indexed by triples of the
   form (prefix, source prefix, neighbour) neighbour), where the prefix and source
   prefix are 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. source.

3.3.  The Table of Pending Seqno Requests

   Every Babel node maintains a table of pending seqno requests, as
   described in [BABEL], Section 3.2.7.  A source-specific Babel node
   extends this table with the following entry.  With this extension,
   the entry:

   o  The source prefix being requested.

   The table of pending seqno requests is now indexed by triples of the
   form (prefix, source prefix, router-id).

   o  the source prefix being requested.

4.  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 entry: two routing table entries might match a
   given packet without one necessarily being more specific than the
   other.  Consider for example the following routing table:

             destination                source     next-hop
       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 all packets with 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 details are available given 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.)  This is consistent with the behaviour
   described in Section 3.3 of [DSR].

   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:

   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] Section V.B for such an algorithm);

   o  If the lower layers cannot hold source-specific routes, then a
      Babel implementation MUST silently ignore (drop) any source-
      specific routes.

5.  Protocol Operation

   This extension does not fundamentally change the operation of the
   Babel protocol.  We protocol, and we therefore only describe the fundamental differences between
   the original protocol and this extension in this section.  The other
   mechanisms described in [BABEL] (Section 3) are the extended to pairs of
   (destination, source) prefixes instead of just (destination)

5.1.  Source-specific messages

   Three messages protocol.

   In the original protocol, three TLVs carry a destination prefix:
   Updates, Route Requests and Seqno Requests.  These  This specification
   extends these messages are extended to carry, in
   addition, optionally carry a source prefix if (and only if) the corresponding route sub-TLV,
   as described in Section 7 below.  The sub-TLV is
   source-specific.  More formally, marked as mandatory,
   so that an Update, a Route Request and a
   Seqno Request unextended implementation will silently ignore the whole
   enclising TLV.  A node obeying this specification MUST carry NOT send a source prefix if they concern TLV
   with a source-
   specific route (non-zero length zero-length source prefix) and MUST NOT carry prefix: instead, it sends a TLV with no
   source prefix otherwise (zero length source prefix).  A message which
   carries sub-TLV.  Conversely, an extended implementation MUST
   interpret an unextended TLV as carrying a source prefix is said of zero
   length.  Taken together, these properties ensure interoperability
   between the original and extended protocols (see Section 6 below).

5.1.  Protocol Messages

   This extension allows three TLVs of the original Babel protocol to be source-specific.

   carry a source prefix: Update TLVs, Route Acquisition

   When Request TLVs and Seqno
   Request TLVs.

   In order to advertise a non-source-specific Babel node receives route with a source-specific
   update, it silently ignores it.  When non-zero-length source prefix, a source-specific Babel
   receives a non-source-specific update, it MUST treat this update as sends a
   zero length source-specific update. Update, i.e., an Update with a source
   prefix sub-TLV.  When a source-specific Babel node receives a source-specific update Update
   (prefix, source prefix, router-id, seqno, metric) from a neighbour
   neigh, it behaves as described in [BABEL] (Section 3.5.4) though
   indexing entries Section 3.5.4, except that
   the entry under consideration is indexed by (prefix, source prefix,
   neigh) rather than just (prefix, neigh).

5.3.  Wildcard retractions (update)

   The original protocol defines

   Similarly, when a wildcard update with AE equals node needs to 0
   as being send a Request of either kind that
   applies to a route with a non-zero length source prefix, it sends a
   source-specific Request, i.e., a Request with a source prefix sub-
   TLV.  When a wildcard retraction.  A node receiving receives a source-specific Request, it behaves as
   described in Section 3.8 of [BABEL], except that the request applies
   to the Route Table entry carrying the source prefix indicated by the

5.2.  Wildcard Messages

   In the original protocol, the Address Encoding value 0 is used for
   retraction on an interface must consider messages: messages that apply to all routes, of any address
   family and with any destination prefix.  Wildcard messages are
   allowed in two places in the sending node
   retracts protocol: wildcard retractions are used
   to retract all of the routes it previously advertised by a node on this interface.

   Wildcard retractions a
   given interface, and wildcard Route Requests are used when a node is about to leave request a
   full dump of the
   network.  Thus, Route Table from a given node.  Wildcard messages
   are intended to apply to all routes, including routes decorated with
   additional data and AE values to be defined by future extensions, and
   hence this extension does not define source-specific
   wildcard retraction, but specification extends wildcard retraction operations to apply also to
   source-specific routes. all
   routes, whatever the value of the source prefix.

   More formally, precisely, a node receiving an Update with the AE field set to 0
   and the Metric field set to infinity (a wildcard update retraction) MUST
   apply the route acquisition procedure described in Section 3.5.4 of
   [BABEL] to all of the routes that is has learned from the sending
   node, whatever the value of the source prefix.  A node MUST NOT
   carry send
   a wildcard retraction with an attached source prefix, and a source-specific Babel node receiving that
   receives a
   (legacy) wildcard update retraction with a source prefix MUST retracts all routes it learns from this
   node (including source-specific ones).

5.4.  Wildcard requests

   The original Babel protocol states that when silently
   ignore it.

   Similarly, a node that receives a route request with the AE field set
   to 0 (a wildcard route request, it request) SHOULD send a full routing table dump.
   This extension does not change this statement:
   dump, including routes with a source-specific non-zero-length source prefix.  A node
   MUST NOT send a full routing table dump when receiving a wildcard

   Source-specific wildcard requests does not exist: a wildcard request
   MUST NOT carry that carries a source prefix, and a source prefix associated with a
   wildcard update SHOULD be ignored.

   One of the motivation behalf this design choice is that wildcard
   requests are defined with AE equals to 0.  They naturally apply to AE
   1, AE 2 and AE 3 defined in [BABEL], but also to any other AE which
   may be defined in the future.  New AEs, new TLVs or new sub-TLVs are
   extension mechanisms.  Thus, the semantics of and a
   node receiving a wildcard request is
   clearly to also asks for routes coming from extensions. with a with a source prefix MUST
   silently ignore it.

6.  Compatibility with the base protocol

   The protocol extension defined in this document is, to a great
   extent, interoperable with the base protocol defined in [BABEL] (and
   all of 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 encoded using mandatory sub-TLVs,
   introduced in [BABEL], and therefore is not compatible with the Experimental
   Track's older
   version of the Babel Routing Protocol [RFC6126].  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.

6.1.  Loop-avoidance

   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 (non source-specific) merely ignores the
   source prefix information when it receives the update rather than
   ignoring the whole TLV, and reannounces re-announces the route as D.  This
   reannouncement re-
   announcement 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

6.2.  Starvation and Blackholes

   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.

7.  Protocol Encoding

   This extension defines a new sub-TLV used to carry a source prefix by prefix:
   the three following existing messages: Source Prefix sub-TLV.  It can be used within an Update, a Route
   Request and or a Seqno Request. Request TLV to match a source-specific entry of
   the Route Table, in conjunction with the destination prefix natively
   carried by these TLVs.

   Since a source-specific routing entry is characterized by a single
   destination prefix and a single source prefix, a source-specific
   message contains exactly one Source Prefix sub-TLV.  A node MUST NOT
   send more that one Source Prefix sub-TLV in a TLV, and a node
   receiving more than one Source Prefix sub-TLV in a single TLV SHOULD
   ignore this TLV.  It MAY ignore the whole packet.

7.1.  Source Prefix sub-TLV

   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[128]| TBD  |    Length     |  Source Plen  | Source Prefix...


   Type      Set to TBD[128] TBD to indicate a Source Prefix sub-TLV.

   Length    The length of the body, exclusive of the Type and Length

   Source Plen  The length of the advertised source prefix.  This MUST
             NOT be 0.

   Source Prefix  The source prefix being advertised.  This field's size
             is (Source Plen)/8 rounded upwards.

   The contents of the source prefix encoding (AE) is the same as the Prefix's.  It is
   defined by sub-TLV are interpreted according
   to the AE field of the corresponding enclosing TLV.

   Note that this sub-TLV is a Mandatory mandatory sub-TLV.  The  Threfore, as
   described in Section 4.4 of [BABEL], the whole TLV MUST be ignored if
   that sub-TLV is not recognized. understood (or malformed).  Otherwise, routing
   loops may occur (see Section 6.1).

7.2.  Source-specific Update

   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]).  A
   wildcard retraction (Update with AE equals to 0) MUST NOT carry a
   Source Prefix sub-TLV.

   Contrary to the destination prefix, this extension does not compress
   the source prefix attached to Updates.  However, as defined in
   [BABEL] (Section 4.5), the compression is
   allowed for the destination prefix of source-specific routes.  Legacy implementation  As
   described in Section 4.5 of [BABEL], unextended implementations will
   correctly update their parser state while otherwise ignoring the
   whole TLV
   afterwards. TLV.

7.3.  Source-specific (Route) Request

   A source-specific Route Request is a Route Request TLV with a Source
   Prefix sub-TLV.  It prompts the receiver to send an update for a
   given pair of destination and source prefixes. prefixes, as described in
   Section of [BABEL].  A wildcard request (Route Request with
   AE equals to 0) MUST NOT carry a Source Prefix sub-TLV.

7.4.  Source-Specific Seqno Request

   A source-specific Seqno Request is a Seqno Request TLV with a Source
   Prefix sub-TLV.  It is just like a Seqno Request for a source-
   specific route.  It uses requests the same mechanisms receiving node to perform the
   procedure described in [BABEL]. Section of [BABEL], but applied to a
   pair of a destination and source prefix.

8.  IANA Considerations

   IANA is requested to allocate TBD, a Babel sub-TLV type from the
   range reserved for mandatory sub-TLVs [value 128 suggested], and to
   add the following entry to the "Babel mandatory sub-TLV Types"

              | Type     | Name          | Reference       |
              | TBD[128] | Source Prefix | (this document) |

9.  Security considerations

   The extension defined in this document adds a new sub-TLV to three
   TLVs already present in the original Babel protocol.  It protocol, and does not by in
   itself change the security properties of the protocol.  However,
   source-specific routing gives more control over routing to the
   sending hosts, which might have security implications (see Section 8
   of [DSR]).

10.  References

10.1.  Normative References

   [BABEL]    Chroboczek, J., "The Babel Routing Protocol", Internet
              Draft draft-ietf-babel-rfc6126bis-02, draft-ietf-babel-rfc6126bis-04, May 2017.

   [BCP84]    Baker, F. and P. Savola, "Ingress Filtering for Multihomed
              Networks", BCP 84, RFC 3704, March 2004.


   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997.

10.2.  Informative References

   [DSR]      Lamparter, D. and A. Smirnov, "Destination/Source
              Routing", Internet Draft draft-ietf-rtgwg-dst-src-routing, draft-ietf-rtgwg-dst-src-routing-
              06, May 2017. 2018.

   [RFC6126]  Chroboczek, J., "The Babel Routing Protocol
              (Experimental)", RFC 6126, February 2011.

10.2.  Informative References

              Boutier, M. and J. Chroboczek, "Source-Specific Routing",
              August 2014.

              In Proc.  IFIP Networking 2015.  A slightly earlier
              version is available online from

Authors' Addresses

   Matthieu Boutier
   IRIF, University of Paris-Diderot
   Case 7014
   75205 Paris Cedex 13

   Juliusz Chroboczek
   IRIF, University of Paris-Diderot
   Case 7014
   75205 Paris Cedex 13