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

[Toke Høiland-Jørgensen]

Juliusz Chroboczek <jch at irif.fr> writes:

>> Tying the seqno request entry to the destination had the problem that when
>> that destination neighbour entry was removed, we'd remove the entire
>> request, and thus no longer retransmit it. Tying the entry to the neighbour
>> on whose behalf we are forwarding the entry instead means that we can just
>> clear out the neighbour from the request entry when we're removing it, as
>> long as we keep a separate flag specifying that it's a unicast request.
>
> This paragraph is not entirely clear to me.  Do you mean that the
> neighbour on behalf of which we're forwarding the request has gone away?

Yes. Before we were tying a request object to the neighbour we sent the
request to, so if that neighbour went away (e.g., when the interface
goes down), the request is cleared out as well and won't be resent. This
patch moves the tracking so that the neighbour entry associated with a
request is the one on whose behalf we are forwarding it. We could just
clear it out, but because of duplicate suppression we don't know if
that's premature (i.e., if another neighbour also send the same
request). So the safe thing to do is keep the request object around so
it can be retransmitted (if we don't get an update for the prefix before
the timeout).

Another option would be to explicitly track all neighbours we received a
request for a particular prefix from. That gets a bit more complicated
because of the many-to-many relationship, though: either we need to keep
a list of all neighbours linked to a request, or we need to duplicate
the request object. The latter would mess with duplicate suppression,
and the former is annoying to do with the linked-list structures that
Bird uses.

Oh, and the reason we don't need to keep track of all neighbours is that
when we satisfy a request we just trigger a global (multicast) update
for the prefix instead of sending it individually to all neighbours we
forwarded requests on behalf of.

>> Rather than complicate the request tracking, we just change the requests
>> sent in response to an unfeasible update to be one-off unicast messages
>> without any retransmission tracking. This should be OK, as we'll send
>> another request the next time we receive the unfeasible update anyway.
>
> Note however that Babel is designed to run reasonably well with very large
> update intervals, so the next unfeasible update might not be coming soon.
> I agree that the request tracking is the most complex part of Babel,
> though, so it makes sense to take some shortcuts.

Hmm, right, well my reasoning was also that receiving an unfeasible
update is not as "urgent" because we most likely have another route for
the same prefix that is feasible already. Or is this intuition not
correct?

> (Actually, the protocol was designed so that all the intervals (Hello, IHU
> and Update) can vary dynamically, and it would make a lot of sense to
> increase the Update interval when we detect a large, stable network.)

Yeah, I've thought about playing with that on several occasions.
Lengthening the update interval would also be a good way to handle very
large routing tables without generating too much update traffic. Would
be fun if we could propagate a full internet routing table over Babel :)

-Toke