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

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

Return-Path: <jch@pps.univ-paris-diderot.fr>
X-Original-To: homenet@ietfa.amsl.com
Delivered-To: homenet@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C82DA21F9F52 for <homenet@ietfa.amsl.com>; Thu, 27 Jun 2013 12:54:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.448
X-Spam-Level:
X-Spam-Status: No, score=0.448 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FRT_POSSIBLE=2.697, HELO_EQ_FR=0.35]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id CPe6LcjORlWh for <homenet@ietfa.amsl.com>; Thu, 27 Jun 2013 12:53:58 -0700 (PDT)
Received: from potemkin.univ-paris7.fr (potemkin.univ-paris7.fr [IPv6:2001:660:3301:8000::1:1]) by ietfa.amsl.com (Postfix) with ESMTP id 6393A21F9F53 for <homenet@ietf.org>; Thu, 27 Jun 2013 12:53:57 -0700 (PDT)
Received: from mailhub.math.univ-paris-diderot.fr (mailhub.math.univ-paris-diderot.fr [81.194.30.253]) by potemkin.univ-paris7.fr (8.14.4/8.14.4/relay2/38117) with ESMTP id r5RJrqZK021796 for <homenet@ietf.org>; Thu, 27 Jun 2013 21:53:55 +0200
Received: from mailhub.math.univ-paris-diderot.fr (localhost [127.0.0.1]) by mailhub.math.univ-paris-diderot.fr (Postfix) with ESMTP id 043644F1FF for <homenet@ietf.org>; Thu, 27 Jun 2013 21:53:52 +0200 (CEST)
X-Virus-Scanned: amavisd-new at math.univ-paris-diderot.fr
Received: from mailhub.math.univ-paris-diderot.fr ([127.0.0.1]) by mailhub.math.univ-paris-diderot.fr (mailhub.math.univ-paris-diderot.fr [127.0.0.1]) (amavisd-new, port 10023) with ESMTP id yfEb5Icfe9gd for <homenet@ietf.org>; Thu, 27 Jun 2013 21:53:49 +0200 (CEST)
Received: from lanthane.pps.univ-paris-diderot.fr (unknown [172.23.36.54]) (Authenticated sender: jch) by mailhub.math.univ-paris-diderot.fr (Postfix) with ESMTPSA id AFAD64F1FB for <homenet@ietf.org>; Thu, 27 Jun 2013 21:53:49 +0200 (CEST)
Received: from localhost ([::1] helo=lanthane.pps.univ-paris-diderot.fr) by lanthane.pps.univ-paris-diderot.fr with esmtp (Exim 4.80) (envelope-from <jch@pps.univ-paris-diderot.fr>) id 1UsIGL-0007XJ-CW for homenet@ietf.org; Thu, 27 Jun 2013 21:53:49 +0200
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
X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.2.7 (potemkin.univ-paris7.fr [194.254.61.141]); Thu, 27 Jun 2013 21:53:55 +0200 (CEST)
Subject: [homenet] Fwd: ANNOUNCE: source-specific routing in Babel
X-BeenThere: homenet@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: <homenet.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/homenet>, <mailto:homenet-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/homenet>
List-Post: <mailto:homenet@ietf.org>
List-Help: <mailto:homenet-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/homenet>, <mailto:homenet-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 27 Jun 2013 19:54:03 -0000

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>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/