Subject: [babel] Forwarding of seqno requests is not specified well enough

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 06 Dec 2016 02:01:46 +0100

RFC 6126 Section 3.8.1.2 says:

   If the requested router-id is not its own, the received request's hop
   count is 2 or more, and the node has a route (not necessarily a
   feasible one) for the requested prefix that does not use the
   requestor as a next hop, the node SHOULD forward the request.  It
   does so by decreasing the hop count and sending the request in a
   unicast packet destined to a neighbour that advertises the given
   prefix (not necessarily the selected neighbour) and that is distinct
   from the neighbour from which the request was received.

This is not well specified.  I don't have a minimal algorithm, but the
following algorithm is provably complete:

  If the node has at least one feasible route towards for the requested
  prefix that does not use the requestor as a next hop, it MUST forward
  the request in a unicast packet to the next hop associated with one of
  these feasible routes (typically the selected route).

  Otherwise, if the node has an unfeasible route towards the requested
  prefix, it MAY forward the request in a unicast packet to the next hop
  associated with one of these routes.

The second paragraph is not technically required, but it may speed up
convergence, and is consistent with existing implementations.

Paragraph 3.8.2.1 also needs to be more precise.  It currently says

  A node that has lost all feasible routes to a given destination MUST
  send a seqno request.
  [...]
  Such a request SHOULD be multicast over all of the node's attached
  interfaces.

This is neither minimal nor complete.  For completeness, a node that has
at least one neighbour that has recently announced a route to the lost
prefix MUST send the request to at least such neighbour, either by
unicasting it or by multicasting it.  For minimality, a node that has no
such neighbour SHOULD NOT send the request.

This does not match current implementations.

-- Juliusz