[Babel-users] About split horizon in Babel, and scaling the number of neighbours

[Baptiste Jonglez]

On Fri, Jun 20, 2014 at 04:28:05PM +0200, Juliusz Chroboczek wrote:
> > As far as I know, split horizon is usually done by routing protocols in
> > order to prevent the most common cases of routing loops.
> >
> > Babel also implements split horizon, but the goal doesn't seem to be loop
> > prevention — probably because it has more sophisticated ways of preventing
> > routing loops.  Instead, split horizon is an optimisation performed when
> > an interface is known to be transitive.
> 
> Exactly.  Consider the following topology:
> 
>      Big network  .....  GW  ----  Small network
> 
> where the link between the big network and the gateway is very slow.
> Without split horizon, the whole routing table of the big network is
> echoed back over the slow link.  With split horizon, only the routing
> table of the small network is sent over the slow link.

I'm not sure to fully understand this example.  The routing table of the
big network must at some point "reach" the gateway, doesn't it?  If so,
then split horizon only helps in the GW → "Big network" direction, but
cannot do anything in the "Big network" → GW direction.


It's actually interesting.  I was assuming that the most costly operation
(in terms of control traffic) was announcing new routes and retracting old
routes.  But indeed, the periodic dump of the routing table is probably
more costly when its size is reasonably large.

Still, split horizon seems to save significant control traffic for new and
retracted routes.  Consider the following topology, where A, B, C and D
are on a common shared medium:

  A   B   C   D ---- E
  |   |   |   |
  -------------

When D announces a new route on the shared medium, then:

- without split horizon, every other router on the shared medium (A, B and
  C) will echo back the same route on the shared medium;

- with split horizon, nothing is echoed back by A, B or C.

If there are n neighbours, for each new or retracted route, there will be
n broadcast messages, instead of just one with split horizon.  This may be
significant if the shared medium is slow (emulated by a VPN) and the
network is very dynamic.

> > - control traffic as a function of the number of neighbouring nodes on the
> > same interface (with and without split horizon).  I would expect it to
> > be linear with split horizon and quadratic without split horizon, does
> > that sound right?
> 
> No, it's linear in both cases: number of neighbours * size of the FIB.
> Recall that only installed routes are announced.

Indeed, I mixed things up in the supposedly quadratic case.

> Split horizon saves up to 1/2 the traffic in extreme cases such as the one
> described above.  Typical savings are much less.

What about the following extreme situation: all Babel routers communicate
*only* through a common shared medium.  With split horizon, a router would
only include its own redistributed routes in the periodic dump.  Without
split horizon, each node would dump the entire routing table.

> > - hard limit on the number of neighbours, with and without split horizon
> > (what would be the bottleneck?  CPU usage?  network throughput?
> > possible implementation limitations?)
> 
> With wifi in ad-hoc mode, the link layer is going to collapse around 100
> neighbours.
> 
> Over ethernet, we apply enough jitter to Babel messages to avoid most
> collisions, so I'd expect the link layer to survive well into the
> thousands.  Babel is able to fit roughly 60 routes in one Ethernet frame
> (assuming a 50-50 split between IPv4 and IPv6), so with 1000 routes and
> 100 neighbours you'll see around 1500 packets every 20 seconds.
> 
> You'll see issues with packet bursts when a route disappears and nodes
> start sending requests.  You'll probably also have issues with the
> neighbour table being a flat list.  Both of which should be fixable.

Thank you for the numbers, this gives an idea.

> > On the other hand, what could go wrong if split horizon is enabled?
> > Will some routes fail to propagate?
> 
> As mentioned above -- split horizon will not gain you much in a rich
> meshed topology.  Split horizon on a non-transitive network will cause
> some routes to be missing; however, except for the resulting blackholes,
> nothing bad should happen.
> 
> Consider the following topology:
> 
>       B
>       |
>   A --+-- C
> 
> A and B can communicate, B and C can communicate, but C doesn't hear A.
> With split horizon, the routes announced by A are not reannounced by B, so
> C never learns the routes to A.
> 
> If your topology is rich enough, then C probably has an alternate route to
> A, so the missing route is not an issue.  However, I would recommend
> disabling split horizon.  If you run into excessive routing traffic,
> either manually splitting your links or manual filtering rules are likely
> to yield better results.

Thank you for the piece of advice.

> -- Juliusz
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://lists.alioth.debian.org/pipermail/babel-users/attachments/20140626/09514848/attachment.sig>