[Babel-users] Aggregating and visualising data from multiple Babel routers

[Baptiste Jonglez]

On Thu, Jul 03, 2014 at 08:35:40PM +0100, Gabriel Kerneis wrote:
> Le 2014-07-03 16:11, Baptiste Jonglez a écrit :
> >I just wrote a proof-of-concept in Python, to get a feeling on how this
> >can be done.  A first version of the code is available here:
> >
> >  http://ze.polyno.me/babel/babelcli.py
> 
> Nice.
> 
> Caveat: I didnt read the code, and may have not fully understood your
> explanations. But it looks like you are taking the opposite view to what I
> had in mind.
> 
> For me, only routes are "reliable", because they are the only thing which
> give you accurate information about paths between nodes (thanks to
> router-ids).

I disagree.  Routes don't provide paths, they provide, well, a distance
vector :)

If the goal is to visualise neighbourhood between routers, then neighbours
seem to be the adequate source of data (provided you know how to map
neighbours to their router-id, of course).  Routes, on the other hand,
only give an indirect information: direction.

> Neighbours, on the other hand, are identified by their interfaces, and
> there is no explicit relationship between a neighbour and a router-id
> (but you can try to guess it using routes with a null reference
> metric). You could even imagine a neighbour relaying packets but
> announcing no route at all (hence "hidden", without any way to infer its
> router-id).

I am using the following heuristic, which (I believe) is the same as Babelweb:

Input: neighbour link-local address and interface
Output: router-id of the neighbour

- consider all routes whose next-hop is (link_local, interface)
- look at the route(s) whose refmetric is minimal
- return the router-id of one of these minimal routes

Note that the minimal refmetric is used, and not only a refmetric equal to
0.  It is a perfectly respectable behaviour to redistribute routes with a
non-zero metric.  But obviously, if all redistributed routes of our
neighbour have a higher refmetric than routes it learned somewhere else,
we will pick the wrong router-id.

In any case, you're perfectly right, it is not possible to map neighbours
to their router-id in the general case.  Maybe we should have a new TLV or
sub-TLV for advertising router-id between neighbours ;)

In practice, this works most of the time, since most routers redistribute
a route to themselves.  One case where this does not happen: IPv6-only
routers with no global unicast address (you only need link-local to
forward IPv6 packets, though it might introduce some other issues).

> So my approach would be to collect all router-ids, and build edges between
> every couple of router-ids, based on routes, keeping only the lowest metric
> for each couple (distinguishing between routes with a refmetric of 0 and
> others).

I'm not sure to understand: wouldn't that build a complete graph?  My goal
is to build a graph whose edges represent neighbouring relations between
routers; is that what you have in mind?  But maybe I misunderstood your
explanation.

> Then, you can enrich information based on neighbours if you manage to
> link them to a router-id. Yes indeed, some of the "edges" that you get
> in fact contain more hops that you don't know about, and showing them
> with a different style as you do is probably a good idea.

You definitely need the neighbour -> router-id mapping, even to simply use
the information contained in routes.  Consider the following topology,
where we look from the perspective of A:

  A  ----  B  ----  C

Router A sees a route to C going through B, so it can assume that a path
"B ->* C" exists (possibly multi-hop, but for simplicity, A may simply
assume that there is an edge "B -> C").

For this, A needs to be able to tell the router-id of B, which is not
contained in the route.

> This is still a bit confused in my head, I hope it makes sense (it certainly
> helped to write it down). Please, prove me wrong or ask more questions. It
> would also helped if you described (your understanding of) "the same method
> as babelweb".

This is exactly the goal of this proof-of-concept: experiment and think
about the results :)

The method for building edges, using the view of a router A, is the
following:

1/ for each neighbour B, build an edge A -> B (guessing the router-id of B
   as discussed above)

2/ for each route R = (next-hop, interface, router-id), compute the
   neighbour N associated to (next-hop, interface), and build a tentative
   edge "N -> router-id" (again, N is a guessed router-id)

> >- we currently rebuild the whole graph at each update: it's possible to be
> >  way more efficient
> 
> And way more buggy. I tried, trust me, you don't want to go down that route
> except if you monitor thousands of nodes and need sub-second latency for
> your graph updates. (Or maybe I'm just not a good enough programmer. But
> remember Knuth.)

Indeed, partial graph update looks difficult.  I was thinking of something
much simpler: ignore updates that do not change the graph.  This is
actually the case for most updates, for instance "The RTT to this
neighbour has changed" or "The metric of this route has changed".

Thanks,
Baptiste
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.alioth.debian.org/pipermail/babel-users/attachments/20140704/70619582/attachment.sig>