Subject: RE: on documenting ECMP (was on the mpls oam framework)

From: "Busschbach, Peter B (Peter)" <[email-masked]>
Date: Tue, 18 Nov 2003 13:21:46 -0500

Dave, et.al.

In one of the side-branches of this discussion, the name Dijkstra came up a couple of times. Apart from inventing the famous algorithm, Dijkstra did important 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 program 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 let's give it a try.

I think that ECMP is an issue only for a subset of traffic. ECMP is not an issue for PW-traffic, since VCCV provides a solution. ECMP is not an issue for services with QoS guarantees, where RSVP-TE is used to set up the connection, because an explicit path is nailed down. 

The question in my mind is: for the traffic that is subject to ECMP, is it really crucial to know exactly how traffic is routed? Shouldn't we just embrace non-determinism for the advantages that it provides and find ways to work around it?

For example, when I surf the web, I don't need an ISP to be able to send OAM packets along the exact same path that I used five minutes ago. For such applications, end-to-end OAM would not be relevant, but local loopback tests might be much more useful.

Peter 

> -----Original Message-----
> From: David Allan [mailto:[email-masked]]
> Sent: Tuesday, November 18, 2003 12:00 PM
> To: [email-masked]'
> Cc: [email-masked]'; [email-masked]
> Subject: RE: on documenting ECMP (was on the mpls oam framework) 
> 
> 
> Curtis:
> 
> You misuderstand me, I lump all tools (including LSP-PING, 
> BFD, VCCV, ITU
> efforts) together under the blanket of OAM.
> 
> enough for now
> Dave
> 
> > -----Original Message-----
> > From: Curtis Villamizar [mailto:[email-masked]] 
> > Sent: Tuesday, November 18, 2003 11:56 AM
> > To: Allan, David [CAR:NS00:EXCH]
> > Cc: [email-masked]'; [email-masked]'; [email-masked]
> > Subject: Re: on documenting ECMP (was on the mpls oam framework) 
> > 
> > 
> > 
> > In message 
> > <[email-masked]
> > om>, " David Allan" writes:
> > > Curtis:
> > > 
> > > >From my perspective there is simply OAM.
> > 
> > Then withdraw as an author of the framework document.  That 
> > would be like Ohta writing the IP over ATM framework 
> > (Conventional IP or ATM advocate).
> > 
> > > To date a fundamental obstacle to progressing OAM has been 
> > the issue 
> > > of how OAM flows are distinguished, esp in the presence of 
> > ECMP. When 
> > > a packet needs to be IP, when it needs to not alias as IP, 
> > > restrictions on the use of reserved labels to distinguish 
> flows and 
> > > where such labels can appear in the stack, yadda yadda 
> > yadda. This has 
> > > been an obstacle to discussing the actual functionality 
> required or 
> > > any other relative merits as all solutions have been held 
> > up to this 
> > > problem first without the actual problem to be solved being 
> > documented 
> > > anywhere.
> > > 
> > > Taking ECMP off the table as an issue by documenting at a 
> > minimum the 
> > > protocol aspects so we can get on with the actual functionality 
> > > required would IMO be progress. The lack of information has 
> > been THE 
> > > obstruction all along.....
> > > 
> > > cheers
> > > Dave
> > 
> > See my prior email.  If OAM doesn't work with ECMP as it 
> > exists in the real world then it is just an applicability 
> > issue that needs to be documented.
> > 
> > Curtis
> > 
>

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 18 Nov 2003 14:02:42 -0500

In message <[email-masked]
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.  I understand that
you don't like ECMP and no one is asking you to like it, simply to
accept that it is part of the architecture and it will be covered by
whatever OAM emerges from the IETF.

> I think that ECMP is an issue only for a subset of traffic. ECMP is not an is
> sue for PW-traffic, since VCCV provides a solution. ECMP is not an issue for 
> services with QoS guarantees, where RSVP-TE is used to set up the connection,
>  because an explicit path is nailed down. 

QoS and explicit path are orthogonal.  Some provider may feel that
they must combine the two in their service but it is not generally the
case.  QoS and ECMP are also orthogonal.  Lets not try to sneak in
assertions that may be true in your case but are not generally true.

> The question in my mind is: for the traffic that is subject to ECMP, is it re
> ally crucial to know exactly how traffic is routed? Shouldn't we just embrace
>  non-determinism for the advantages that it provides and find ways to work ar
> ound it?

We did that in MPLS Ping.  The ingress can determine from the midpoint
(essentially by the midpoint telling it) where ECMP branches exists
and how to exercise each branch.  This method is deterministic and
will exercise all paths.  The alternate is to randomly spray across
the 127/8 space, which is non-deterministic but arguably will also
exercise all paths.  The latter method can detect loss but not measure
the loss experienced on any given path (loss may be concentrated in a
subset of the traffic).

If other techniques want to do something similar to determine how to
exercise ECMP paths, then they become applicable where ECMP is used.
If they don't they are simply not applicable when ECMP is used.  One
provider may choose to disable ECMP and use a technique that works
only with ECMP disabled.  Another provider may choose to keep ECMP
enabled and use a different OAM technique that works with ECMP.

> For example, when I surf the web, I don't need an ISP to be able to send OAM 
> packets along the exact same path that I used five minutes ago. For such appl
> ications, end-to-end OAM would not be relevant, but local loopback tests migh
> t be much more useful.

I'm quite confident that the PC in my home has not sent any OAM
packets to the IETF mail servers to verify the path to the mail
server.  But quite honestly this has nothing to do with the discussion
of the OAM framework.  If I want to test to see if my ISP is live or
the path to the IETF mail server is OK, I just use IP ping and
traceroute.  Loopback tests are accomplished for your example.

> Peter 

We had some compromise and I fear that we are now slipping back to
arguing about whether ECMP is part of the architecture.  I hope that
is not the case.

Curtis

---

From: Kireeti Kompella <[email-masked]>
Date: Tue, 18 Nov 2003 12:50:39 -0800 (PST)

Hi Curtis,

On Tue, 18 Nov 2003, Curtis Villamizar wrote:

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

---

From: "Thomas D. Nadeau" <[email-masked]>
Date: Tue, 18 Nov 2003 16:44:51 -0500

>From: [email-masked] [mailto:[email-masked]] On Behalf 
>Of Kireeti Kompella
>Sent: Tuesday, November 18, 2003 3:51 PM
>Cc: [email-masked]
>Subject: Non-determinism considered harmless
>
>
>Hi Curtis,
>
><[email-masked]
	
	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? *)

>well as the random bits, makes the task of predicting flow paths next

	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

---

From: Naiming Shen <[email-masked]>
Date: Tue, 18 Nov 2003 15:14:28 -0800

some of the routers even "secretly" perform UnEqual Cost Multi-Path,
please also document those.

- Naiming

---

From: mark seery <[email-masked]>
Date: Tue, 18 Nov 2003 19:15:30 -0500 (EST)

Some philosopher's say there is no such thing as truth, just optimization for a result (very amoral of course, but a worthwhile observation none the less).

It is clear shortest-path routing is an optimization that has proven very nice indeed, it is clear the explicit routing is an optimization that has proven useful as well. It is also worth noting that the packet networks envisioned by Paul Baran had even less determinision than what we think of as IP today - and that was an opimization for a specific result. So everyone has there determinism life preserver of choice (for some its as simple as in the light of a constant topology packets will always flow along the same path).

What we all are is obvious, we are just arguing over the size of the preserver at this point.

---

From: mark seery <[email-masked]>
Date: Wed, 19 Nov 2003 13:30:25 -0800

Busschbach, Peter B (Peter) wrote:

>(large snipping license follows - apologies in advance)......non-determinism is a powerful concept and that a program should be written in such a way that its correctness can be proven, even in the face of non-determinism..........is it really crucial to know exactly how traffic is routed? Shouldn't we just embrace non-determinism for the advantages that it provides and find ways to work around it?
>
Way OT in to the theoretical, but.................

Peter, I think your instinct that there is a philisophical/paradigm 
disconect is true, of which many would agree. I understand why you took 
the determinism route (as determinism was previously raised), but I 
don't think determinism fully explains the issue.

You may have heard of the famous computer simulation by Craig Reynolds 
(http://www.red3d.com/cwr/boids) that involved "boids" - artificial life 
birds. In one model, boids were given three simple rules: maintain a 
minimum distance from other objects, try to match velocity with other 
boids in the neighborhood, try to move towards the perceived center of 
mass of boids in the neighborhood. In one of the runs, a boid hit a 
pole, it bounced off, the other boids flew around the pole, and then all 
the boids self-organized back in to the flock formation they were 
previously in. There was not one line of code in the simulation 
directing the boids what to do if they hit a pole. From this observation 
people have inferred that in protocols, and by extension networks, you 
can not anticipate all the potential problems, and that by trying to do 
so makes the system inherently less robust; and that a better approach 
is to program rules that will lead to self-organization, and perhaps 
even one day emergent behavior. So in dynamic routing, we see yet 
another human endeavor searching for the essence of intelligence. This, 
combined with the social and technological trends of the 70's and 80's 
that highlighted the limitations of hierarchy, have combined to create a 
powerful force within our industry.

So I would observe the behavior of the boids were determinstic (not 
randomly selected choice as in some genetic algorithms of trial and 
error). But the real "life preserver" issue to which Kireeti referred is 
not whether to trust in non-determinism, but whether to trust the 
inherent intelligence of the network, and the simple rules (some of 
which Kireeti has enumerated) which we use to make sure our 
(packets)boids react when they hit their respective poles. It is the 
difference between whether you believe you can enumerate all the 
potential fault conditions or not, and whether you are willing to pay 
the price for accounting for them. It is the difference between whether 
you think intelligence lives purely in the control plane, of whether you 
think it lives in the data and management planes as well.

No doubt our respective operational experiences inform us on this and 
other issues, which of course is one of the dividing lines, and why the 
compromise of applicability seems so important.

As it is said that science often works more by metaphor than deduction 
than people believe, the search for a metaphor is good - finding the 
right one is extremely hard. It is also fair to observe that most major 
standards bodies (IEEE, IETF, ITU, ATM Forum, ANSI) are most comfortable 
with one metaphor, everything else has the potential to be an irritation 
in the oyster which produces a pearl, but often that is not the case. 
The inherent problem with MPLS is that it has the potential to confuse 
people about which metaphor is being pursued, but this thread does not 
lead much doubt (IMO) - though even within the IETF/IP community that is 
sometimes debated (adding to the confusion).

This is not anywhere near the entire story, but thought your comment 
deserved a considered response.

Best,
mark

p.s. it was constructive and worthwhile of Tom to add that even with 
MPLS there are options.