Subject: RE: Last call on LSP Ping - ECMP thread (continued)

From: "Gray, Eric" <[email-masked]>
Date: Tue, 10 Dec 2002 10:33:41 -0500

Curtis,

	It seems I'm going have to make one more attempt to clarify 
this discussion, after which I may not bother to continue. Please 
do not make the assumption that a lack of response from me in the 
future is an indication of agreement. :-)

	Just to be perfectly clear, what you are saying is that - if 
you were making a purchase decision, you would hand the vendor in
question a copy of a readily available Informational RFC entitled 
"Analysis of an Equal-Cost Multi-Path Algorithm" and tell them to
implement that?  You should note a few things about this RFC:

o	it uses "... an ..." in the title (implying acknowlgement
	that other approaches exist and are not included in the
	analysis);
o	it does not specify a particular hash function (author's 
	choice to use the word specify, not mine);  
o	it makes a comparison between the general idea of using a 
	hash key and such time honored ECMP approaches as "Round 
	Robin" and "Random Choice" (rather than comparing various
	choices of hash functions); 
o	it lists some specific ways that one might use to establish
	hash thresholds (no one of which is used to the exclusion
	of all others today);
o	it seems to lead the reader to conclude that the general 
	idea of using a hash key based on packet header fields that
	identify a flow is a good one;
o	it informs the reader of engineering trade-offs involved.

	Entirely aside from the fact this very useful information
is obvious to people who implement routers, it does not require 
anything that is not included in what I suggested.  Nor is the 
fact you hand an implementer that RFC going to change choices 
they have already made based on considerations very similar (if 
not identical) to the engineering trade-offs the RFC describes.  
Those choices may have been driven by a number of factors, but 
it is certainly late in the process for them to change their 
choices once they have completed an implementation.

	Presumably, there are customer-related considerations to be 
taken into account beyond a value judgment as to what constitutes
a "good hash" or what is easy in some implementations.

	Finally, the use of IP header fields in LSP-based ECMP is
far from an established practice.  Based on your own earlier
assertions with respect to when it would be appropriate (after
determining that an individual flow is in fact an IP flow), the
approach is not scalable.  Therefore, an IP destination based 
approach to ping-ing equal cost paths is (as I said earlier)
misleading and most likely not useful.

	The LSP Ping draft should define a specific address to be
used as the default IP destination address, rather than a range.  
As I now understand it (you still have not, AFAIK, sent the message
that contains all the parts of your suggestion), your suggestion
to provide a mechanism to allow an intermediate node to suggest
addresses that would test all equal cost paths would work.  I
would not have a problem with picking those addresses from the
127/8 range, as long as a single address (127.0.0.1) is stated
as the default in lieu of a suggested address.

Eric W. Gray
Systems Architect
Celox Networks, Inc.
[email-masked]
508 305 7214

> [...]
> >
> > > The normal HASH is over a 64 bit quantity.  ...
> >
> > 	Again, this is an assertion though how anyone might
> > determine what the "normal" hash algorithms might include
> > is beyond me.
> 
> It comes from a bit over a decade working in Internet operations and
> in IP protocol development and experience with a large number of
> routers.  Plus it is documented in RFC 2992.
> 
>   2992 Analysis of an Equal-Cost Multi-Path Algorithm. C. Hopps.
>        November 2000. (Format: TXT=17524 bytes) (Status: INFORMATIONAL)
> 
> I think that justifies the assertion.
> 
> ...
> 
> > > If there is a router that does ECMP and uses an IP hash that doesn't
> > > include the lower 24 bits, I'd be really surprised.  I don't think
> > > such a thing exists or that there is any good reason to build such a
> > > thing and therefore your objection has no merit.
> >
> > 	Then you should be prepared to be surprised.  In
> > general, it is sufficient to group flows using either a
> > source or a destination IP address based hash.  Further,
> > it is of some importance to use a range of algorithms, or
> > (non-exclusive) a variation of key sources/patterns so
> > that it is possible for the same source and destination
> > to map to a different has key at different places in the
> > network.  Finally, it is very important to keep the hash
> > algorithms simple.
> 
> That is the purpose of the random key to the hash, periodically
> updated (very long interval).
> 
> > 	Consequently, it is possible that you may discover
> > that some schemes use only a small-ish set of bits from
> > either the source or destination IP address, depending
> > on the location of the device, and the direction of packet
> > flow, relative to the network core.  Even if the entire
> > 64 bits of source and destination IP address is injected
> > into some algorithms, it is possible that steps in the
> > algorithms themselves may ignore some of those bits.
> 
> A good hash does not ignore any of the bits.
> 
> > 	If you believe that my objection still has no merit,
> > then we are unlikely to find common ground for further
> > discussion - at least with respect to this issue.
> 
> Can you please name such a router.  I know it is not Cisco, Juniper,
> or Avici.  Nor the old Bay routers, or Ironbridge, or Pluris or the
> former Argon.  Some of the newer edge boxes may have done this.  If
> so, can you please name one?
> 
> ...
> 
> Such a router would be quite broken not because MPLS-ping wouldn't
> work but the oad split wouldn't be very good.  If making a purchasing
> decision, I'd hand the maker a copy of RFC2992 and wait for them to
> fix the routers or go elsewhere.
> 
> ...
> 
> > > I thought I just did propose something (not in the attached message
> > > but in a prior message) that unlike what you state above requires no
> > > change to forwarding.  It requires only a change in MPLS TTL expired
> > > processing if the payload is MPLS-ping (which is already required).
> > > It is really spread over three messages.  Do I need to resend it in
> > > one message?
> >
> > 	Either that, or point out which three messages.
> 
> 
> I'll just resend them as one.
> 
> Curtis
> 
> 
> > Eric W. Gray
> > Systems Architect
> > Celox Networks, Inc.
> > [email-masked]
> > 508 305 7214

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 10 Dec 2002 11:20:24 -0500

In message <[email-masked]
> future is an indication of agreement. :-)

This is noted.

> choices once they have completed an implementation.

This is informational and points to some requirements.  It is not
normative, but if a router doesn't meet the requirements the
consequences (microflow reorder or poor load split) are clear and
ample indication of how to avoid this is given.

 requirements:

  1.  Any multipath implementation must avoid reordering microflows.

  2.  Some algorithms split traffic better than others.  Using the
      whole address rather than part of it still doesn't split
      microflows and balances load better.

  3.  Some algorithms produce a delay discontinuity for less
      microflows when a new member is added or deleted.

The third criteria in RFC2991 is ignored by current practice.

 key points:

  1.  Per packet (send every other packet to a different interface)
      load split reorders the packets within microflows and is bad.
      [This also impacts L2VPN if reordering at egress is unsupported.]

  2.  The granularity of per IP perfix load split is too coarse and
      the resulting load split can be terrible.  For example, all
      traffic to 18/8 (MIT) going to one interface might make for a
      very uneven load split on a Boston circuit.

Current practice dates back to the late 1980s, possible earlier, when
the PC-RT based T1-NSFNET routers did multipath by src/dst based hash.
The method of hash and modulo or a specific hash designed to produce
an even distribution over a number range has been used by numerous
routers including current Cisco, Juniper, and Avici products, and I'm
sure others.  I mentioned before Bay, Pluris, Argon, Ironbridge, all
used similar techniques.

> a "good hash" or what is easy in some implementations.

Could you please give a criteria for a "good hash" that you feel might
be applicable to real networks and might lead to a different decision
on what algorithm to use.  In other words what should the algorithm be
doing differently.  [You already indicated you may not respond.]

> misleading and most likely not useful.

This I will entirely agree on.  I still owe you the concatenated
response on multipath where I will very willingly acknowledge that
multipath support varies.

> as the default in lieu of a suggested address.

Again.  Details to follow shortly.  The range is needed.

Curtis