looping

[Martha Steenstrup <[e-mail]>]

Hi Yakov,

Before we retreat to the phone and off the idpr-wg list, let me try
once more to put forth the problem.

Suppose X and Y both seek routes to Z.  Z generates a distance vector
message at time 0 and begins propagating it to its neighbors.

   By time 1: X's route is X .. Z, and Y's route is Y .. Z.

   By time 2: X's route reaches Y, and Y's route reaches X.
              X's route becomes X .. Y .. Z, and Y's route
              becomes Y .. X .. Z.

   By time 3: X's new route reaches Y, and Y's new route
              reaches X.  X rejects the route X .. Y .. X .. Z
              because it contains a loop, and Y rejects the route
              Y .. X .. Y .. Z because it contains a loop.  However,
              X still retains the route X .. Y .. Z, and Y still
              retains the route Y .. X .. Z.

I believe that the only way to get rid of such a looped route is for a
domain A to perform the following additional test.  Whenever A
receives a distance vector for a destination B that lists A as a
domain along the route, it automatically rejects the distance vector,
because it contains A.  However, before discarding the distance
vector, A should also check that for each S preceding A in the
distance vector, S is not included on A's current route to B.  As long
as none of the Ss are on A's route to B, then there won't be any of
these loops.  However, if one of the Ss is on A's current route to B,
A must get rid of its current route, because there will be a loop.

Although these "S" checks are sufficient to detect this type of loop
(albeit a bit expensive), A may not have sufficient information to
perform them, because A will not necessarily receive the distance
vectors that point to the looping problem in the first place.

Suppose in the XYZ example, that Y's distance vector distribution
rules preclude it from distributing the vector Y .. X .. Z out the
interfaces that happen to lead back to X, and that X's distance vector
distribution rules preclude it from advertising X .. Y .. Z back in
the direction of Y.  Then neither X nor Y will have sufficient
information to detect these loops.

m