[homenet] Fwd: ANNOUNCE: source-specific routing in Babel

Juliusz Chroboczek <jch@pps.univ-paris-diderot.fr> Thu, 27 June 2013 19:54 UTC

Date: Thu, 27 Jun 2013 21:53:49 +0200
Message-ID: <7ia9mbtjn6.wl%jch@pps.univ-paris-diderot.fr>
From: Juliusz Chroboczek <jch@pps.univ-paris-diderot.fr>
To: homenet@ietf.org
References: <7ibo6rtjoo.wl%jch@pps.univ-paris-diderot.fr>
User-Agent: Wanderlust/2.15.9
MIME-Version: 1.0 (generated by SEMI 1.14.7 - "Harue")
Content-Type: text/plain; charset="US-ASCII"
Subject: [homenet] Fwd: ANNOUNCE: source-specific routing in Babel
Precedence: list

Date: Thu, 27 Jun 2013 21:52:55 +0200
Message-ID: <7ibo6rtjoo.wl%jch@pps.univ-paris-diderot.fr>
From: Matthieu Boutier <boutier@pps.univ-paris-diderot.fr>
To: babel-users@lists.alioth.debian.org
CC: Markus Stenberg <markus.stenberg@iki.fi>, fred@cisco.com
Subject: ANNOUNCE: source-specific routing in Babel

Dear all,

We are pleased to announce a first implementation of Babel-S,
a variant of Babel able to distribute source-specific routes.  The
code is available using

  git clone -b source-specific git://git.wifi.pps.univ-paris-diderot.fr/babels.git

with a web inteface on

  http://git.wifi.pps.univ-paris-diderot.fr/?p=babels.git

and a backup on

  https://github.com/boutier/babeld

Motivation
==========

Consider the case of a multihomed network (a network connected to two
ISPs).  If the network is using provider-specific addresses, a packet
needs to be routed to the right ISP depending on its *source* address.
This is in contrast to traditional routing, which only considers the
*destination* when making a routing decision.

       ISP A      ISP B
          \        /
   packets \      /  packets
   sourced  \    /   sourced
   from A    \  /    from B
           end node

Markus Stenberg has recently published a prototype of source-specific
routing for OSPF[1].  Babel-S is our attempt at a production-quality
implementation of source-specific routing within the Babel routing
protocol[2].

Implementation details
======================

In the presence of source-specific routing, a route is identified by
a pair (D, S) where D is a destination prefix and S is a sourcer
prefix.  In the general case, there is a possibile ambiguity between
two routes.

For example, in our experimental network there is a default
source-specific route

  (0.0.0.0/0, 192.168.4.0/24)
       ^            ^
       |            |
     dest         source

and a non-source-specific route

  (192.168.4.42/32, 0.0.0.0/0)

A packet that is both sourced from 192.168.4.0/24 and destined to
192.168.4.42 is ambiguous.  As was explained to us by Fred Baker, in
this case the destination should "win" -- the packet should follow the
non-source-specific route.

Unfortunately, the one Linux kernel API that works is the "rule"
system, which doesn't implement this semantics naturally.  For this
reason, we are inserting extra "disambiguation" routes for the
intersection

  (192.168.4.42/32, 192.168.4.0/24)

The exact algorithm is somewhat involved, and will be described at
some later point.  Enjoy the code in route.c in case you're interested.

Limitations
===========

- There are some limitations wrt. routes found in the kernel that were
  not installed by babeld.
- Requests for source-specific routes are broken (we're working on
  it); this could cause starvation in some very unlikely cases.
- The number of kernel tables used by the daemon cannot be configured yet.

Usage
=====

Without any special configuration, Babel-S reannounces source-specific
routes received from other Babel peers and installs them in the
kernel.  In order to introduce source-specific routes in the network,
some routers should redistribute their routes as source-specific.
This is done via the "source-prefix" configuration option.

For example, to redistribute his routes with the source
192.168.4.0/24, a router will be configured with:

  source-prefix 192.168.4.0/24

By default, Babel-S will use the routing tables 10 to 19 and the
rules' priorities 100 to 109.  You can see kernel rules and tables
using the ip command:

  ip rule show
  ip route show table 10

Babel-S defines in total 5 new configuration options, described in
details in the manual pages.  These are:

 - source-specific
 - first-table-number
 - first-rule-priority
 - announce-with-default-source-prefix
 - install-specific

This is experimental code, likely to change at any time.  Any feedback
will be very much welcome.

-- Matthieu Boutier and Juliusz Chroboczek

[1] https://github.com/fingon/hnet-core
[2] http://www.pps.univ-paris-diderot.fr/~jch/software/babel/

[homenet] Fwd: ANNOUNCE: source-specific routing … Juliusz Chroboczek
Re: [homenet] [Babel-users] ANNOUNCE: source-spec… Michael Richardson
Re: [homenet] Fwd: ANNOUNCE: source-specific rout… Lorenzo Colitti
Re: [homenet] ANNOUNCE: source-specific routing i… Juliusz Chroboczek