The MPLS WG Archive

[Kireeti Kompella <kireeti@juniper.net>]

Hi Curtis,

On Tue, 18 Nov 2003, Curtis Villamizar wrote:

> In message <B99995113B318D44BBE87DC50092EDA90C0D5500@nj7460exch006u.ho.lucent.c
> om>, "Busschbach, Peter B (Peter)" writes:
> > Dave, et.al.
> >
> > In one of the side-branches of this discussion, the name Dijkstra came up a c
> > ouple of times. Apart from inventing the famous algorithm, Dijkstra did impor
> > tant work in the area of correctness proofs and concurrent processes. One of
> > his insights was that non-determinism is a powerful concept and that a progra
> > m should be written in such a way that its correctness can be proven, even in
> >  the face of non-determinism.
> >
> > We have to be careful translating this to OAM (after all, you don't want your
> >  service provider to blame non-determinism when your connections fail), but l
> > et's give it a try.
>
> Nice thought followed by a cheap shot, but fine.

Actually, I think Peter was trying to be helpful :-)

Stepping waaaay back, I think the real reason (at least, one of them)
for not liking ECMP (or for wanting to know the innards thereof) is
exactly that: non-determinism.  With connection-oriented, p2p circuits
everywhere, one can definitely (deterministically) point to the exact
boxes which a given 'flow' traverses.

Losing that determinism in the face of ECMP can be (for some) rather
like letting go of one's life-preserver -- infinitely scary, until you
realize that the human body does float.

To repeat Peter: "correctness can be proven, even in the face of
non-determinism" -- you just need the right invariant, and to prove
that each router preserves that invariant.  The invariant is of course
not reordering flows, and the post-condition is that the metric is
smaller.

The funny part about this is, some think that knowing all ECMP
algorithms would alleviate the non-determinism.  It would,
theoretically, but practically, the complexity of the algorithms, as
well as the random bits, makes the task of predicting flow paths next
to impossible.

Kireeti.
-------