[ih] WiFi, DV, and transmission delay

[Dave Taht]

Juliusz Chroboczek <jch at irif.fr> writes:

>>> Finally remembered who it was; Jose Garcia-Luna. He added a mechanism
>>> to DV that basically prevented the formation of loops. I don't recall
>>> the details of how it worked, but if you visualize a network as a pool
>>> of water, and a connectivity change is a stone dropped into the pool,
>>> then the routing updates are like the ripples that spread out from the
>>> point of impact.  Anyway, IIRC, Jose's mechanism limits changes to
>>> a single ripple, so it's even better than loop prevention, it bounds
>>> the time to respond to a connectivity change (I _think_ - it's been
>>> decades since I looked at it).
>
>> This is a really good description. I can ask juliusz where babel's loop
>> free "feasibility condition" came from...
>
> It's lifted wholesale from DUAL (Garcia-Luna's algorithm).
>
> The bit that I did not take from DUAL is the diffusing update algorithm
> (the elegant bit described above as "a single ripple"), which
> unfortunately does not terminate in general: if a router crashes at just
> the wrong time, the diffusing computation fails to terminate, and
> a timeout is required in order to recover (that's known as the "Stuck in
> Active" (SIA) state in EIGRP).  Babel avoids the issue by using route
> sequencing (lifted from DSDV) augmented with an unreliable recovery
> mechanism (seqno requests).  In effect, on a very lossy network Babel will
> spuriously discard routes where DUAL would deadlock.

nice to see you here juliusz!

... And ideas march on, rippling back and forth, results,
mis-interpreted, mis-identified, technologic change happens, tests
repeated, fixed, re-analyzed, and re-implemented, tested, and
re-iterated and progress seeps forward and sideways and backwards.

I had not tied the knot between DUAL and babel and - AHA! from rfc6126

Garcia Luna Aceves, J., "Loop-Free Routing Using
               Diffusing Computations", IEEE/ACM Transactions on
               Networking 1:1, February 1993.

http://www.cs.cornell.edu/people/egs/615/lunes93.pdf

thx for connecting the dots (noel: is the ripples in the pool analogy yours,
or sourced from somewhere?)

This is later ref to dual and garcia-luna's work I've found so far
https://apps.dtic.mil/dtic/tr/fulltext/u2/a457720.pdf

although all his work is turning out to be fascinating.

(https://apps.dtic.mil/dtic/tr/fulltext/u2/a461695.pdf)

while I'm here, babel's rtt metric extension...

(https://tools.ietf.org/html/draft-jonglez-babel-rtt-extension-01) I
seem to recall was partially derived from mill's work on ntp. Was it
also influenced by the early arpanet routing protocols? Somewhere on
these enormous threads here this month was mentioned that unsmoothed RTT
issues was another one of DV's problems led to spf and link-state.

How's the deployment going?

...

You've made the "heretical" claim that shortest path routing is not the
best routing mechanism for wireless networks in some paper/preso also.

>
> -- Juliusz