[B.A.T.M.A.N.] Network models [was: Battlemesh v5 tests]

Juliusz Chroboczek
2012-03-11T15:32:37Z

Hmm, are we getting off-topic for the Battlemesh list?

>> (In a pure mesh protocol, routers with multiple interfaces should
>> probably appear as multiple nodes;

> Why? I think it is good that the routing protocol knows that something
> (some interfaces) belongs together (node).

I agree with both of you, this is precious information that should not
be dropped. The question is whether it should be embedded in the
network model, or kept outside of it.

A pure mesh model has the attraction of being extremely clean and pure;
most graph theory theorems apply to a pure mesh model straight away,
which allows you to leverage a large body of existing litterature. So
intuitively there should be some strong advantages to keeping your model
small and clean, and encoding the information about linked interfaces in
a separate data structure.

I'm not quite sure what model BATMAN uses, but it would appear that it's
almost, but not quite, a pure mesh model. Perhaps the BATMAN developers
have thought long and hard about giving up the purity of a mesh model,
and decided that it's worth it. Perhaps they haven't. It's difficult
to say, since they're not interested in communicating on technical issues.

OLSR uses a pure model and encodes extra information in additional data
structures. That's why OLSR uses MIDs and HNAs -- they're the packets
carrying the additional data. An alternative "clean" model would be to
have a router id for each interface, and an extra flag within TC entries
that shows which links are between multiple interfaces of a single node,
which is what I suggest might be a good choice at layer 2.

Babel uses a different model, the classical Internet model (very well
described by Clark in the early 80s, but I don't have the paper handy).
In that model, we're not working with a graph, but with a structure with
three kind of entities: nodes, interfaces, and links, where links
connect interfaces rather than connecting nodes. There are some
advantages to using a model that more faithfully represents reality, and
that is a good fit with what classical routing protocols do, but of
course the downside is that we're working with a somewhat messy data
structure that hasn't been studied as exhaustively as graphs have.

-- Juliusz