The MPLS WG Archive

["Thomas D. Nadeau" <tnadeau@cisco.com>]

>-----Original Message-----
>From: owner-mpls@UU.NET [mailto:owner-mpls@UU.NET] On Behalf 
>Of Kireeti Kompella
>Sent: Tuesday, November 18, 2003 3:51 PM
>To: 'curtis@fictitious.org'
>Cc: mpls@UU.NET
>Subject: Non-determinism considered harmless
>
>
>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.
	
	Wow. MPLS is openning up new doors for revenue 
opportunities all the time. The newest application would
be therapists deployed with each ECMP-enabled box for 
those folks that ECMP is triggering panic attacks? *)

>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.

	Seriously, one point to make in all of this is that if you 
WANT determinism, it is available -- completely explicit paths 
signaled with RSVP-TE. If you can't stand to let go of the life 
preserver this is an option.  Like everything though, there is no 
free lunch, which is why many folks are willing to give up some
of that determinism.

	--Tom