Subject: [manet] Babel (RFC 6126) questions

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 15 Dec 2011 14:47:55 -0800

Hello Julius,

I have looked at Babel, which seems to be very interesting
work.  While reading the RFC, I started to wonder about
various aspects of the protocol.  I probably have missed
some important points, but anyway I hope you would not
mind answering some questions and comments.

=========================================================

- The initial discussion doesn't properly account for
   multidimensional metrics
   = for metrics with continuous values, no total order
   = to fit the discussion, need to reformulate DSDV metric.
     For instance, [((2^96)/(seq.number)) + (# of hops)]
     would probably work for networks with diameter < 2^32
     and 32-bit sequence numbers.

     Let's call that metric M_cep.  Later in the document,
     the proper 2-dimensional DSDV metric is introduced and
     it seems to work well for Babel also.  But until that
     time, we need a single-dimensional metric in order to
     apply to the examples.

- BGP feasibility criterion does not seem at all drastic ...?

- Definition of "DSDV-feasibility":
   "a route is feasible only when its metric
    at the local node would be no larger than the metric of the currently
    selected route, i.e., an announcement carrying a metric D(B) is
    accepted by A when C(A, B) + D(B) <= D(A)"

- Using M_cep, the feasibility condition works.

- Definition of "Babel-feasibility":
   "An update sent by a neighbour B of A is feasible when
    the metric D(B) advertised by B is strictly smaller than
    A's feasibility distance, i.e., when D(B) < FD(A)."

- "Suppose that node A obeys DSDV-feasibility; then D(A)
    is nonincreasing, hence at all times D(A) <= FD(A)"
    --> This leads one to believe that at some times they
        are not the same, so that at some times A has not
        advertised its best route to the destination.
    --> Then the next paragraph does make sense.

- However, note that node A is prevented from accepting
   a feasible update from B in many circumstances -- namely
   whenever D(B) < FD(A)  but  (C(A, B) + D(B)) > D(A)

- This definition means that the language in the document
   is nonintuitive, and thus error prone.  As an example,
   the last paragraph in section 2.4 does NOT state whether
   or not node A has accepted announcement D(B), and so
   one has to imagine additional conditions which were not
   explicitly stated in order to maintain consistency.
   I guess it has to do with keeping track of multiple
   feasible routes in case one goes bad.  In this case,
   maybe in order to avoid wrong intuition, it would be
   reasonable to explicitly state that feasible route
   updates can be used if needed in the future even if
   they do not improve D(A).

- The first figures in section 2.5 do not properly
   represent DSDV-feasibility when metric M_cep is used.

- "Note that while sequence numbers are used for determining
    feasibility, they are not necessarily used in route selection: a node
    will normally ignore the sequence number when selecting a route"
    --> This doesn't properly account for metric M_cep
    --> Basically, it is a mistake to ignore the sequence number
        since the almost inevitable result is lengthier convergence

- In section 2.8, it would seem better for A to observe that
   B is its next hop to C, and for corrective action to be taken.
   Moreover, I am not yet persuaded that this consequence results
   from the prefix lengths.

- I didn't see the difference between asking for a new sequence
   number from a destination, versus sending a RREQ including
   a flag requiring an RREP from the destination.  And, I didn't
   see the advantage of prohibiting intermediate nodes to send
   "feasible" RREPs.

- In section 3.5.1, the sequence number has to be checked
   even for retractions.  An old retraction is not feasible if
   the same neighbor has advertised a more recent feasible route.
   Or else one must assume that packets from neighbors are
   always received in order.

- The suggestion to enforce hold times results from the
   argument in Section 2.8 which doesn't seem bulletproof
   to me.  I reckon the node(s) receiving the retraction
   will trigger an update to the retractor if they have
   another feasible route.

- I guess that the definition of "unfeasible route" is one
   like that specified in section 3.5.5.

- "routes with a small metric should be preferred over routes with a
       large metric;"
   --> this is the definition of metric...

- "switching router-ids should be avoided"
   --> compared to what?

- "routes through stable neighbours should be preferred over routes
       through unstable ones;"
    --> requires definition of unstable neighbor

- "stable routes should be preferred over unstable ones"
   --> requires definition of unstable route!

- "switching next hops should be avoided"
   --> compared to what?

For these points, I think it's appropriate to keep in
mind that measuring route stability is quite problematic
with anything more than very slow mobility.  DSDV had
various problems with this.

- I gather that "seqno requests" replace DSDV/AODV RREQ.

   Neither section 3.8.1.1 nor section 3.8.1.1 can be
   used by nodes that have not yet acquired routes to
   any destinations.  This means that there is a problem
   for the network to initially be formed:

   From section 3.8.1.2:
   "When a node receives a seqno request for a given router-id and
    sequence number, it checks whether its routing table contains a
    selected entry for that prefix; if no such entry exists, or the entry
    has infinite metric, it ignores the request."

================================================================

Regards,
Charlie P.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 16 Dec 2011 18:07:06 +0100

Pleased to meet you, Charles.  I've spent many a happy hour over your
papers.

> I have looked at Babel, which seems to be very interesting work.

Thanks for the kind words.  It would be great if some of my ideas could
be useful to the Manet group.

> While reading the RFC, I started to wonder about various aspects of
> the protocol.

I'll treat your individual comments in detail below.  Before I do, it is
worthwile to spell out three important design criteria that I used in Babel:

1. Babel is carefully optimised for simplicity of implementation.  In
   particular, when designing Babel I rejected any feature that
   I couldn't implement by myself over the week-end.  Should I have
   allowed myself more (notably kernel-side support), Babel would have
   ended up much more similar to AODV, and perhaps would I have used
   AODV in the first place.

   This discipline has one pleasant consequence, which is that the
   "babeld" sample implementation is portable to Linux since 2.4 and to
   some BSD variants; in particular, it takes 20 minutes to set up
   a Babel router using OpenWRT, even on hardware that's only supported
   by old kernel versions.

2. Babel is a proactive protocol, and periodic route dumps are
   compulsory.  At the core of Babel, there's a nucleus similar to RIP
   (albeit with an explicit Hello/IHU subprotocol).  While this means
   that an idle Babel router causes a moderate amount of traffic, it
   also implies that any deadlock will be resolved by the next
   broadcast.  This allows me to ignore some of the "never happen in
   practice" edge cases that you rightly mention -- if they do actually
   happen, heck, you'll just wait 20 seconds for the next periodic
   broadcast.  It also solves the problem of bootstrapping.

3. Babel is derived from DSDV, EIGRP and AODV.  The basic approach was
   to start with DSDV, and steal ideas freely from EIGRP and AODV
   whenever I felt that DSDV was being suboptimal.  (I've tried to be
   careful with giving credit, please let me know by private mail if you
   feel I haven't been diligent enough.)

>     and 32-bit sequence numbers.

Babel distinguishes between the metric m (which is just the number of
hops in your particular example, but can be ETX or a weird experimental
interference-sensitive value), and the distance d = (s,m) (a two-
dimensional space ordered lexicographically).  Metrics are used by route
selection, distances are used for determining feasibility.

This is what I feel is one of the main innovations in Babel w.r.t. DSDV
and AODV -- the fact that seqnos are not used for route selection.  More
about this below.

>        advertised its best route to the destination.

That's right.  Small fluctuations in the metric, as well as seqno
increases, don't necessarily trigger sending an update (second paragraph
of 3.4.1).

(With ETX, small fluctuations in the metric happen basically at every
hello exchange, so this is an important feature.  An alternative would
be to artificially smoothen the metric, but the current solution is both
simpler and more elegant.)

>   is nonintuitive, and thus error prone. [...] In this case,

You're absolutely right, point taken.

> - The first figures in section 2.5 do not properly represent
>   DSDV-feasibility when metric M_cep is used.

Yep.  We're only going to introduce seqnos later in that section.

>        since the almost inevitable result is lengthier convergence

As mentioned above, this is what I feel is one of the main innovations
in Babel.

With non-trivial metrics (ETX, or the weird experimental thing used in
Babel-Z), or when various nodes use different time constants, there is
not necessarily a strong correlation between higher seqnos and better
routes.  For that reason, Babel ignores seqnos in route selection.

(Earlier versions of the sample implementation did take seqnos into
account, and that was found to be a mistake.  The RFC is ambiguous in
its advice on this subject, since it reflects an earlier stage of my
understanding.)

>   Moreover, I am not yet persuaded that this consequence results

I fully agree that this is the least satisfactory part of Babel.  If you
have any good ideas for an alternative algorithm, I'm very much interested.

>   see the advantage of prohibiting intermediate nodes to send

Sorry if that's not stated clearly enough.  Intermediate nodes are
allowed to satisfy a seqno request ("send a feasible RREP" in AODV
terminology).  What they are not allowed is increasing the seqno -- any
seqno must be a copy of a seqno produced by the source.

(As a side note, the AODV terminology is somewhat misleading when
applied to Babel.  Due to the proactive nature of the protocol, route
updates are not necessarily replies to a request.)

>   always received in order.

Recall that a node can reboot and lose its state, including its seqno
number.  (The sample implementation attempts to save its seqno to stable
storage, but routers can and do crash, and we also run babeld on routers
with no useful stable storage.)  In order to clear any old state from
the network, we want a retraction to be obeyed unconditionally.

So yes, we assume that link-local packets don't routinely get reordered.
In the unlikely case they do get reordered (e.g. due to FSTP reconver-
gence or to link-layer ARQ), the next periodic broadcast will cause us
to recover (note that retractions do not update the feasibility distance).

(Please let me know if you know of other sources of link-local packet
reordering, whatever the link technology, and whether you have any
statistics on how often they happen.)

>   --> this is the definition of metric...

No, Babel is carefully designed to decouple the local route-selection
policy from what happens on the wire.  The metric is what is carried by
the updates, and a local policy can override the metric.  Compare this to
BGP, where the path length is often overridden by local policy.

> For these points, I think it's appropriate to keep in mind that
> measuring route stability is quite problematic with anything more than
> very slow mobility.

I know that now (after trying and failing to use route stability), but
I didn't at the time I wrote the RFC.  I would word this paragraph
differently now.

>   for the network to initially be formed:

Bootstrapping is done by waiting for a periodic update.  The protocol
also has provisions for sending a wildcard request at boot (last
paragraph of 3.8.1.1 and 3.8.2.4), but unless it's done carefully, it
causes broadcast storms when a whole network reboots.  (Again, I'd word
these sections differently now.)

Thanks again for your comments, and please let me know if you have any
further suggestions.

-- Juliusz

P.S. Permission to forward your mail to the babel-users list?