Subject: [babel] Thoughts on rfc6126bis

From: "Russ White" <[email-masked]>
Date: Mon, 27 Nov 2017 11:30:44 -0500

Y'all --

I read through the draft again, and ran into a couple of small things -- the operation of EIGRP as described in this doc has always bothered me, I finally went through and thought about what's wrong with it, and provided some wording around this. Some other minor nits, as well.

😊

Russ

==
As many routing algorithms, Babel computes costs of links between any two neighbouring nodes, abstract values attached to the edges between two nodes.  We write C(A, B) for the cost of the edge from node A to node B.
   
I think this is probably missing a word? Perhaps "Babel uses an abstract value to represent the cost of the link between any two nodes," or some such?
   
==
Given a route between any two nodes, the metric of the route is the sum of the costs of all the edges along the route.  The goal of the routing algorithm is to compute, for every source S, the tree of routes of lowest metric to S.

Because the shortest path is always loop free -- I don't know if this is worth mentioning here, but it might be useful for some readers.

==
At this point, the whole network must be rebooted in order to solve the starvation; this is essentially what EIGRP does when it performs a global synchronisation of all the routers in the network with the source (the "active" phase of EIGRP).

The active process is not a "network reboot," but rather it's very similar to what BABEL does. To describe the EIGRP process --

1. A route is lost, resulting in starvation
2. The router losing the route marks the destination as active
3. The router then sends a query to each neighbor for the now active route
4. The neighbor examines its local table for an alternative route which meets the local feasibility condition
5. If such a route to the destination is found, the router responds to the query with this information
6. If no such route is found, the router will send queries to its neighbors to continue the search

This is very similar to what BABEL does, but with two differences. First, there are no sequence numbers. Instead of sequence numbers, EIGRP assumes a route received as part of an answer to a query is always newer than the original route (and hence the feasibility condition may be reset). Second, rather than sending just the originator of the original route a request for a new route, EIGRP spreads the request out to all neighbors, so any alternative path will work.

I think what the paragraph is trying to refer to is the (old) Stuck in Active (SIA) process, not the active process. What happens here is if an EIGRP router is active on a particular destination, and does not receive an answer from a neighbor it has sent a query to for a long time, it will reset that specific neighbor state (assuming the neighbor is no longer responding). This still is not a "network reboot," of course, but it is more drastic than other possible solutions. In more recent code, EIGRP does not reset the neighbor adjacency, but rather queries again (the SIA query process), and again treats any route received in response to this query as newer than the no longer useable route (because of the topology change). 

I would change this to -- "EIGRP marks a route active, transmitting a diffusing query through the network to find an alternative route in the case of starvation." At some later point, it might be worthwhile to describe the differences between the EIGRP process and the BABEL process.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 28 Nov 2017 17:06:06 +0100

>     At this point, the whole network must be rebooted in order to solve
>     the starvation; this is essentially what EIGRP does when it performs
>     a global synchronisation of all the routers in the network with the
>     source (the "active" phase of EIGRP).

I am open to a different formulation, but I don't really see a good way of
keeping the intent while remaining reasonably concise.  I guess I could
replace "the whole network" with "the whole starving subtree", which would
be closer to what EIGRP does.

> The active process is not a "network reboot," but rather it's very
> similar to what BABEL does.

That's an interesting debate.

[...]

> This is very similar to what BABEL does, but with two
> differences. First, there are no sequence numbers. Instead of sequence
> numbers, EIGRP assumes a route received as part of an answer to a query
> is always newer than the original route (and hence the feasibility
> condition may be reset). Second, rather than sending just the originator
> of the original route a request for a new route, EIGRP spreads the
> request out to all neighbors, so any alternative path will work.

I think that is very different from what Babel does.  In order to be able
to clear the old feasibility information, EIGRP must perform a synchronisation
of the whole sub-tree that is suffering from starvation.  It is my
understanding that all the starving routers freeze until they receive
confirmation that the whole subtree has cleared their routes.

So there's synchronisation over an unbounded number of nodes --
essentially a reboot of the starving subtree.  Whence the formulation
quoted above.

This is very different from what Babel does, since Babel is designed to
avoid synchronisation.  In Babel, a request is sent out, and a new route
becomes usable as soon as a new sequence number is received -- no need to
wait for the other neighbours to acknowledge, so a slow or crashed router
will not delay reconvergence as long as faster routers are available to
forward the sequence number.

> I think what the paragraph is trying to refer to is the (old) Stuck in
> Active (SIA) process, not the active process.

I'm not entirely clear on what SIA is, since EIGRP folks are not very keen
on discussing it.  My understanding is that the synchronisation required
by the active phase does not necessarily terminate (a router could crash
between receiving a request and sending the acknowledgment), and in this
case, the network will deadlock until the SIA timeout triggers.  But
I could be wrong.

> In more recent code, EIGRP does not reset the neighbor adjacency, but
> rather queries again (the SIA query process), and again treats any route
> received in response to this query as newer than the no longer useable
> route (because of the topology change).

So basically restarting the active phase instead of dropping the
neighbour?  There's still a timeout dependent on the slowest router in the
starving component, right?

> I would change this to -- "EIGRP marks a route active, transmitting
> a diffusing query through the network to find an alternative route in
> the case of starvation."

I think that is less informative than what I've written.  Does changing
"the whole network" to "the starving subtree", as suggested above, fix it
for you?

-- Juliusz