Subject: RE: your mail

From: "Gray, Eric" <[email-masked]>
Date: Tue, 23 Jul 2002 11:20:44 -0400

Shahram,

	As you said (or implied) earlier, using the entire
MPLS stack identifies the inner-most LSP.  This might be
considered a 'flow', by some definitions of flow.  It is
an interesting fact that containing LSPs are 'flows' by a 
coarser definition and even the inner most LSP is likely 
to be an aggregation of 'flows' by some finer definition 
of flow.  

	One could seek to get to an even finer definition 
of flow by going beyond the bottom of stack label.  One 
question is whether or not this is necessary, or even 
helpful to at least the extent that it might be hard to 
do.  A separate questions is whether or not it can even
be done correctly.

	The key considerations in picking an approach to
doing ECMP are maximizing the extent to which traffic is
(expected to be) evenly distributed while avoiding risk
of scattering traffic in doing so.  An example of traffic
scattering would be what would happen if you attempt to
use IP DA/SA as part of your hash key (bucket selector)
with non IP packets (particularly if the bit positions 
corresponding to IP DA/SA happen to be associated with
fields that change from one packet to the next in any 
specific flow under consideration).

	While developing a hash based on identifying flows 
is a sufficient means to ensure that individual flows do 
not get scattered, it is not necessary (the usual formal 
definition of necessary and sufficient apply here).  If
it is known that flows will be bucketed in any aggregate
form, then individual flows will be bucketed that way as
well and will not be scattered.

	After some thought, it becomes clear that one way
to bucket flows in such an aggregate form is to use the
first and last label in the stack (where last means any
label that can be consistently selected based on either
the bottom of stack indication or some number N that is
the highest number of labels that can be examined by a
particular implementation).  This is what was proposed.

	This reduces the question to whether or not there
is anything to gain - in terms of distribution equity -
from using a finer aggregate.  The answer to this is 
something each implementer has to decide for themselves
based on specifics of their own implementation.  A very
important consideration is how much information their
implementation wants to - or even can - know about the
quantity of traffic that is associated with individual
flows at whatever granularity they choose to use.  I
believe the proposal describes a reasonable basis for
doing ECMP that will fit many/most implementations.

	Incidentally, there are many algorithms that will 
generate a hash from a bit stream of nearly arbitrary 
length (it cannot be infinite, for example). That's a 
completely unrelated topic, in my opinion.

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

-----Original Message-----
From: Shahram Davari [mailto:[email-masked]] 
Sent: Tuesday, July 23, 2002 10:04 AM
To: 'Gray, Eric'; [email-masked]'
Cc: [email-masked]
Subject: RE: your mail 

Thanks Eric,

Your response seems reasonable. However, I have heard that
some implementation hash the label stack, up to the Nth
label or bottom-label (if the stack has less than N labels).
Does that mean that the hashing algorithm should operate on a 
variable length input? And if so does such an algorithm exist?

Yours,
-Shahram

> -----Original Message-----
> From: Gray, Eric [mailto:[email-masked]]
> Sent: Monday, July 22, 2002 5:06 PM
> To: Shahram Davari; [email-masked]'
> Cc: [email-masked]
> Subject: RE: your mail 
> 
> 
> Shahram,
> 
> 	There is nothing to be fearful, uncertain or
> doubtful about here.
> 
> 	If an implementation can handle up to N labels,
> then it can use either the bottom-of-stack label or
> the Nth label for a hash key.  With respect to flows,
> this will be consistent.  It will also tend to give
> the greatest degree of entropy in hashing possible
> for a specific labeled packet.  It doesn't guarantee
> even distribution any worse than any other 'guess'.
> 
> 	Use of the IP header as well is a) unnecessary,
> b) unhelpful and c) not a good idea.
> 
> Eric W. Gray
> Systems Architect
> Celox Networks, Inc.
> [email-masked]
> 508 305 7214
> 
> 
> -----Original Message-----
> From: Shahram Davari [mailto:[email-masked]] 
> Sent: Monday, July 22, 2002 4:48 PM
> To: [email-masked]'
> Cc: 'Giles Heron'; [email-masked]; 
> [email-masked]; [email-masked]
> Subject: RE: your mail 
> 
> Hi Eric,
> 
> If I understand you correctly, what you are saying is that 
> assume a number
> such as "N", and hash the Nth label, regardless of whether it is the 
> real bottom-most label (i.e. with S=1) or not. If so then:
> 
> 1) How do you know that at least N labels exist in all packets?
> 2) The Nth label can not identify a flow by itself, rather 
> you need to hash
> the whole label stack from the top, up to the Nth label, in order to
> identify a flow.
> 3) I have heard that some implementations hash the IP header 
> too? How does
> that fit in to your model? How do you know that the payload 
> is IP? And don't
> you need to find the real bottom of stack (S=1) in order to 
> include the IP
> header in the hash?
> 
> Yours,
> -Shahram
> 
> > -----Original Message-----
> > From: Eric Rosen [mailto:[email-masked]]
> > Sent: Monday, July 22, 2002 3:15 PM
> > To: Shahram Davari
> > Cc: 'Giles Heron'; [email-masked]; [email-masked];
> > [email-masked]
> > Subject: Re: your mail 
> > 
> > 
> > 
> > Shahram> "Deep" or "not deep"  you need potentially unlimited 
> > packet parsing
> > Shahram> (uo to  MTU size), since as you  said the number of  
> > labels are not
> > Shahram> limited to 2. 
> > 
> > To  the MTU  size?   That would  be for  the  case where  the 
> > entire  packet
> > contains the MPLS label stack and there is no payload?
> > 
> > As has been made  clear repeatedly, you can hash on any  
> > label, you just get
> > more fine-grained load balancing the  further down you go.  
> > So generally you
> > would look  at the  bottom-most label  that you can  easily 
> > see,  given your
> > particular forwarding architecture. 
> > 
> > 
> > 
> > 
>