[PATCH] babel: Rework seqno request handling to track sender, not destination

[Juliusz Chroboczek]

>   * the neighbour, if any, on behalf of which we are forwarding this request;

[...]

> But it is true that since forwarded requests are not resent, i also do not
> see the need for this information.

Agreed on both counts.

> I think that the text of section 3.2.7 (The Table of Pending Seqno
> Requests) is confusing with regard to this, as it describes resent
> counter for each entry without any qualifier that it is only used for
> originated requests and not for forwarded requests).

Right.  The field is only necessary if you send an update only to the
requesting node.  Neither BIRD nor babeld currently implements that.

Some background.  The basic principle of Seqno requests is sound: the only
entity that can reliably determine that it's suffering from starvation is
the starving node itself, and hence Babel (like EIGRP, but unlike DSDV)
uses an explicit request mechanism to resolve starvation when it happens.

The mechanism is also provably complete: in the absence of persistent
packet loss, the simple mechanism in Section 3.8.2.2 (sending a request
when starving and receiving an unfeasible update) is enough to guarantee
completeness.

So from a purely theoretical point of view, all you need to do is (1) send
a request when you're starving and receive an unfeasible update, and (2)
forward each request at most once and only if you have a feasible route.
However, if this is the only mechanism you implement, then the expected
convergence time will be on the order of half the update interval
multiplied by the distance (hop count) to the closest non-starving router.
And that's in the absence of packet loss.

Back in 2008-2010, I've spent a lot of time experimenting with various
tradeoffs, and the RFC is confusing as a result of these experimentations.
The algorithm described in the RFC works fairly well in practice, except
during periods of very high instability in dense networks, in which case
it tends to generate too many requests.

We could certainly do better if somebody spent a year of their life
working on the problem.  Perhaps when I retire :-)

-- Juliusz