Subject: [Roll] fundamental (?) choice between convergence to "best" routes and (transient) loop avoidance in DV routing

From: Mukul Goyal <[email-masked]>
Date: Sat, 4 Jul 2009 02:19:12 -0500 (CDT)

Here is some food for thought:

Its my conjecture that in DV routing, there is a fundamental choice to be made: either you can have ultimate convergence to best routes or you can avoid transient loops but you can not have both.

Consider the following scenario:

         R
        / \
        A-B
        | |
        C-D

All links are bidirectional and link costs in both directions are same. All link costs are 1 except link B-R has cost 50 and A-B has cost 5.

Case 1:
---------
Suppose there is no attempt to avoid loops. Clearly, the routes to R from different nodes would be as follows:

A: A->R
C: C->A->R
D: D->C->A->R
B: B->D->C->A->R

And the costs advertised by different nodes to R would be as follows:

A: 1
C: 2
D: 3
B: 4

Suddenly, the cost of link A-R becomes 100. We have a classic "count to infinity" problem at hand. In the absence of any "poison reverse" solution, routing loops exist until B realizes that its best route to R is B->R. Other nodes also realize that they should go through B to reach R.

In this case, we were able to converge to best routes but had to bear transient routing loops.

Case 2:
----------------
Suppose we have loop avoidance in place in the form of an invariant DAG based on depths derived from initial link costs.

The DAG is: B->D->C->A->R

Since the DAG is invariant and a node can not choose a deeper node as parent, we are doomed to use the original suboptimal paths after the cost of link A-R changes from 1 to 100.

In this case, we were able to avoid loops at the cost of being stuck with bad routes.

Case 3:
------------------
Suppose we allow the DAG to change. When link A-R increases in cost from 1 to 100, A advertises a new depth and basically triggers a sequence of events similar to case 1. As in case 1, we converge to the best routes (and to a new DAG) after a transient during which the routing loops exist. It is my conjecture that the routing loops may not be avoidable no matter how the "costs" are mapped to the DAG "depths".