Subject: [trill] TRILL OAM Requirements: available paths

From: Erik Nordmark <[email-masked]>
Date: Fri, 27 Apr 2012 09:53:25 -0700

Two requirements use the wording "all available paths." and "all 
available ECMP paths.", respectively and I'm not sure I know what that 
means.

Take the following example picture:

                R1
               /  \
              /    \
             /      \
            /        \
           /          \
        RB11          RB12
        /  \          /  \
       /    \        /    \
    RB111  RB112  RB121  RB122
       \      \    /      /
        \      \  /      /
         \      \/      /
          ------R2------

We can see that there are 4 paths with 3 hops to get from R1 to R2, with 
two layers of ECMP decisions. But how many available paths are there?

Given that the RBridges make independent ECMP decisions, and how they do 
that is a local matter, it could be the case that for any packet, if R1 
picks the left link, then R11 would also pick the left link; if R1 picks 
the right link, then R12 also picks the right link.
Thus there would be no packet (data or OAM) that would cause packets 
between R1 and R2 to pass via RB112 or RB121.

Even if we ignore that as unlikely, there is still the fact that R1 
can't easily tell how many (shortest) paths there might be between it 
and R2. With single-level TRILL the LSDB could be used to tell, but if 
we ever go to multi-level that wouldn't be the case any more.
And even if R1 knows that there are 4 potential paths, it can't format a 
data packet (or format the flow entropy in an OAM packet) in such a way 
that particular paths get chosen by downstream ECMP decisions.

Thus for any notion of "all available paths" that make sense to me, we'd 
need an OAM approach that can explore the topology one hop at a time and 
at each hop explore all the possible ECMP choices. Using the entropy 
doesn't help with this (but the entropy is critical for following the 
path taken by a particular flow of data packets).

Hence it would be good to clarify what the assumptions are behind this 
notion of all available paths.

Thanks,
     Erik

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Fri, 27 Apr 2012 14:13:31 -0700

We can make the wording uniform. It was intended to be all available
ECMP paths. Because with IS-IS in place you have only visibility to the
Equal cost paths. When using multi-level TRILL, still the packets get
forwarded along the Equal Cost Multipaths when it is available. How the
entropy is derived to cover different equal cost paths is in the scope
of a framework/solution.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf
Of Erik Nordmark
Sent: Friday, April 27, 2012 9:53 AM
To: [email-masked]
Subject: [trill] TRILL OAM Requirements: available paths

                R1
               /  \
              /    \
             /      \
            /        \
           /          \
        RB11          RB12
        /  \          /  \
       /    \        /    \
    RB111  RB112  RB121  RB122
       \      \    /      /
        \      \  /      /
         \      \/      /
          ------R2------

Thanks,
     Erik

_______________________________________________
trill mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/trill

---

From: Santosh Rajagopalan <[email-masked]>
Date: Fri, 27 Apr 2012 14:15:25 -0700

I agree, the wording needs to be tightened to say "all possible ecmp 
paths" rather than "all available paths". An operator working out R1-R2 
communication is interested in all possible paths data traffic could take 
rather than all theoretically available paths.

From:   Erik Nordmark <[email-masked]>
To:     [email-masked]
Date:   04/27/2012 09:53 AM
Subject:        [trill] TRILL OAM Requirements: available paths
Sent by:        [email-masked]

                R1
               /  \
              /    \
             /      \
            /        \
           /          \
        RB11          RB12
        /  \          /  \
       /    \        /    \
    RB111  RB112  RB121  RB122
       \      \    /      /
        \      \  /      /
         \      \/      /
          ------R2------

Thanks,
     Erik

---

From: Erik Nordmark <[email-masked]>
Date: Fri, 27 Apr 2012 16:07:03 -0700

On 4/27/12 2:15 PM, Santosh Rajagopalan wrote:
> communication is interested in all possible paths data traffic could
> take rather than all theoretically available paths.

The issue is that there is nothing in the TRILL dataplane nor IS-IS 
control plane which helps the operator determine that some paths 
(through RB121 and RB112 in the example) are not possible; the ECMP 
input and hashing is a completely local matter on each RBridge.

It isn't useful to state a requirement around something that can't be 
determined.

    Erik

> ------------------------------------------------------------------------
>
>
>
>

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Fri, 27 Apr 2012 17:12:57 -0700

Of course it is possible. The IS-IS topology table provide the
information on all available ECMP paths to a specific destination when
the egress RBRidge nickname is known. That is what TRILL unicast
forwarding table all about. Not sure why you are saying it is not
possible to know all ECMP paths.

What path among available paths to be selected for a specified is a
local matter. That is what all about flow entropy discovery. Like I
stated earlier how it is discovered is a framework and solution issue.
If you need some reference how it is done in the MPLS world RFC 4379 is
a good reference.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf
Of Erik Nordmark
Sent: Friday, April 27, 2012 4:07 PM
To: Santosh Rajagopalan
Cc: [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

On 4/27/12 2:15 PM, Santosh Rajagopalan wrote:
> paths" rather than "all available paths". An operator working out 
> R1-R2 communication is interested in all possible paths data traffic 
> could take rather than all theoretically available paths.

    Erik

> Subject: [trill] TRILL OAM Requirements: available paths Sent by: 
> [email-masked]

> We can see that there are 4 paths with 3 hops to get from R1 to R2, 
> with two layers of ECMP decisions. But how many available paths are
there?
>
> Given that the RBridges make independent ECMP decisions, and how they 
> do that is a local matter, it could be the case that for any packet, 
> if R1 picks the left link, then R11 would also pick the left link; if 
> R1 picks the right link, then R12 also picks the right link.

> And even if R1 knows that there are 4 potential paths, it can't format

> a data packet (or format the flow entropy in an OAM packet) in such a 
> way that particular paths get chosen by downstream ECMP decisions.
>
> Thus for any notion of "all available paths" that make sense to me, 
> we'd need an OAM approach that can explore the topology one hop at a 
> time and at each hop explore all the possible ECMP choices. Using the 
> entropy doesn't help with this (but the entropy is critical for 
> following the path taken by a particular flow of data packets).
>

---

From: Sam Aldrin <[email-masked]>
Date: Fri, 27 Apr 2012 20:01:35 -0700

Erik,

The forwarding table is setup based on the control plane information, is-is, for all the ecmp paths. I am not clear when you say that requirement is not relevant for this. Even if the forwarding is local matter, one should be able test each of those ecmp paths using entropy field for crafting oam packets. This is how ecmp in other network types work as well, including trill.

If your understanding of the ecmp in trill is different to what I eluded to, I would like to hear it. 

Cheers
Sam
Sent from my iPhone

On Apr 27, 2012, at 4:07 PM, Erik Nordmark <[email-masked]> wrote:

> The issue is that there is nothing in the TRILL dataplane nor IS-IS control plane which helps the operator determine that some paths (through RB121 and RB112 in the example) are not possible; the ECMP input and hashing is a completely local matter on each RBridge.
> 
> It isn't useful to state a requirement around something that can't be determined.
> 
>   Erik
> 
>> 
>>

---

From: Erik Nordmark <[email-masked]>
Date: Sat, 28 Apr 2012 20:45:34 -0700

> possible to know all ECMP paths.

You are talking about what Santosh called "all theoretically available 
paths". Those can be determined from IS-IS.

But the document talks about "all available paths" and I don't know what 
that is supposed to mean. Do you have a succinct definition?

What is clear to me is that there can be a subset of the paths that are 
determined from IS-IS that would never be used, because no entropy in a 
packet would every pick that path.

Is the requirement in the document that the OAM solution should be able 
to test those paths?

> stated earlier how it is discovered is a framework and solution issue.

Agreed.

> If you need some reference how it is done in the MPLS world RFC 4379 is

AFAIK MPLS doesn't have a locally defined ECMP hash function in every 
hop. TRILL does, which makes these aspects different.

Regards,
    Erik

>> From: Erik Nordmark<[email-masked]>
>> To: [email-masked]

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Sat, 28 Apr 2012 21:43:00 -0700

No, I am talking about all equal cost paths. As IS-IS run through path
calculations it only maintain best cost paths. You cannot by default
obtain all theoretical paths.

Whether entrophy covers a subset or all equal cost paths is a
implementation/solution issue. That is the reason requirements are in
place to include real payloads. I am not sure whether I am getting the
explanation correctly. May be I should call you or you can dial in to
the design team meeting and I can explain.

-----Original Message-----
From: Erik Nordmark [mailto:[email-masked]] 
Sent: Saturday, April 28, 2012 8:46 PM
To: Tissa Senevirathne (tsenevir)
Cc: Santosh Rajagopalan; [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

Agreed.

> If you need some reference how it is done in the MPLS world RFC 4379 
> is a good reference.

Regards,
    Erik

>> ---------------------------------------------------------------------
>> -
>> --
>>
>>
>>
>>

---

From: Sam Aldrin <[email-masked]>
Date: Sat, 28 Apr 2012 21:54:18 -0700

Erik,

Every hop in mpls does hashing based on label stack and other header details. I do not see any difference between TRILL and mpls in this case. 

 The requirement is to specify the ability to test each of those ecmp paths available. Doesn't matter if the active traffic is taking that path or not. This is part of pro-active monitoring.

Cheers
Sam

Sent from my iPad

On Apr 28, 2012, at 8:45 PM, Erik Nordmark <[email-masked]> wrote:

> You are talking about what Santosh called "all theoretically available paths". Those can be determined from IS-IS.
> 
> But the document talks about "all available paths" and I don't know what that is supposed to mean. Do you have a succinct definition?
> 
> What is clear to me is that there can be a subset of the paths that are determined from IS-IS that would never be used, because no entropy in a packet would every pick that path.
> 
> Is the requirement in the document that the OAM solution should be able to test those paths?
> 
> AFAIK MPLS doesn't have a locally defined ECMP hash function in every hop. TRILL does, which makes these aspects different.
> 
> Regards,
>   Erik
>

---

From: Erik Nordmark <[email-masked]>
Date: Sun, 29 Apr 2012 17:36:32 -0700

> Every hop in mpls does hashing based on label stack and other header details. I do not see any difference between TRILL and mpls in this case.

That's not consistent with what I heard from others when I discussed 
MPLS OAM. But that isn't the main point.

>   The requirement is to specify the ability to test each of those ecmp paths available. Doesn't matter if the active traffic is taking that path or not. This is part of pro-active monitoring.

OK. Then please make that clear in the requirements document. For 
instance, that can be done by including a careful definition of 
"available ecmp paths" in the document.

FWIW I don't think any of the solutions that have been discussed so far 
are capable of testing all the available paths; that just means there is 
some more work needed on solutions.

    Erik

> Cheers
> Sam
>
>
> Sent from my iPad
>
> On Apr 28, 2012, at 8:45 PM, Erik Nordmark<[email-masked]>  wrote:
>

---

From: Sam Aldrin <[email-masked]>
Date: Sun, 29 Apr 2012 17:44:01 -0700

Sent from my iPhone

On Apr 29, 2012, at 5:36 PM, Erik Nordmark <[email-masked]> wrote:

> That's not consistent with what I heard from others when I discussed MPLS OAM. But that isn't the main point.
> 
> OK. Then please make that clear in the requirements document. For instance, that can be done by including a careful definition of "available ecmp paths" in the document.
> 
> FWIW I don't think any of the solutions that have been discussed so far are capable of testing all the available paths; that just means there is some more work needed on solutions.
> 
>   Erik
> 
>> Cheers
>> Sam
>> 
>> 
>> Sent from my iPad
>>

---

From: Sam Aldrin <[email-masked]>
Date: Sun, 29 Apr 2012 17:48:11 -0700

Sent from my iPhone

> That's not consistent with what I heard from others when I discussed MPLS OAM. But that isn't the main point.
All the implementations I have implemented and came across does hashing at every hop.
> OK. Then please make that clear in the requirements document. For instance, that can be done by including a careful definition of "available ecmp paths" in the document.
Definitely. This review effort is to remove any ambiguity.

Sam

---

From: Donald Eastlake <[email-masked]>
Date: Sun, 29 Apr 2012 21:26:50 -0400

I don't think the wording "all paths" should ever be used. If you the
it literally, it would even include paths that go through some
RBridges more than once.

I don't particularly like "all ECMP paths" either. I think the
clearest wording is "all least cost paths" if you are talking about
known unicast. (And "all distribution tree paths" if you were talking
about multi-destination frames.)

Thanks,
Donald
=============================
 Donald E. Eastlake 3rd   +1-508-333-2270 (cell)
 155 Beaver Street, Milford, MA 01757 USA
 [email-masked]

On Sat, Apr 28, 2012 at 11:45 PM, Erik Nordmark <[email-masked]> wrote:
> AFAIK MPLS doesn't have a locally defined ECMP hash function in every hop.
> TRILL does, which makes these aspects different.
>
> Regards,
>   Erik
>
>

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Sun, 29 Apr 2012 20:42:33 -0700

I like that Donald.. We can use "all least cost paths", that is technically more precise and represent exactly what IS-IS does.

Thanks
Tissa

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Donald Eastlake
Sent: Sunday, April 29, 2012 6:27 PM
To: [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

I don't think the wording "all paths" should ever be used. If you the it literally, it would even include paths that go through some RBridges more than once.

I don't particularly like "all ECMP paths" either. I think the clearest wording is "all least cost paths" if you are talking about known unicast. (And "all distribution tree paths" if you were talking about multi-destination frames.)

Thanks,
Donald

On Sat, Apr 28, 2012 at 11:45 PM, Erik Nordmark <[email-masked]> wrote:
>> information on all available ECMP paths to a specific destination 
>> when the egress RBRidge nickname is known. That is what TRILL unicast 
> But the document talks about "all available paths" and I don't know 
> what that is supposed to mean. Do you have a succinct definition?
>
> What is clear to me is that there can be a subset of the paths that 
> are determined from IS-IS that would never be used, because no entropy 
> in a packet would every pick that path.
>
>> From: [email-masked] [mailto:[email-masked]] On 
>> Behalf Of Erik Nordmark
>>> --------------------------------------------------------------------
>>> --
>>> --
>>>
>>>
>>>
>>>
>>> Given that the RBridges make independent ECMP decisions, and how 
>>> they do that is a local matter, it could be the case that for any 
>>> packet, if R1 picks the left link, then R11 would also pick the left 
>>> link; if
>>> can't easily tell how many (shortest) paths there might be between 
>>> it and R2. With single-level TRILL the LSDB could be used to tell, 
>>> but if
>>
>>
>>> a data packet (or format the flow entropy in an OAM packet) in such 
>>> a way that particular paths get chosen by downstream ECMP decisions.
>>>
>>> time and at each hop explore all the possible ECMP choices. Using 
>>> the entropy doesn't help with this (but the entropy is critical for

---

From: David M Bond <[email-masked]>
Date: Mon, 30 Apr 2012 11:39:04 -0400

Just a question coming from this conversation that I want to clarify:

So we have 'all possible paths' (1) which could include non-least cost
paths and so of course we don't want to use this definition.

Then we have 'all ecmp paths' or 'all least cost paths' (2) which MAY
include paths never chosen by a transit Rbridge because of the local
hashing choices.

Then we have 'all the least cost paths which may be chosen given the
hashing implementation on the local Rbridges' (3).

I wonder if choice (2) is useful or do we only really care about choice
(3). For instance, if you have 16 equal cost paths from A to B and your
hashing only will ever use 2 of those paths do we care about reporting back
ecmp paths that will never in practice be used? Perhaps the definition
should be tightened to only require determination of all least cost paths
that could be used given the local hashing implementation. Or am I
misunderstanding the conversation and is this already the point being made
between theoretical paths and least cost paths.

Thanks,
David

From:	"Tissa Senevirathne (tsenevir)" <[email-masked]>
To:	"Donald Eastlake" <[email-masked]>, <[email-masked]>
Date:	04/29/2012 11:43 PM
Subject:	Re: [trill] TRILL OAM Requirements: available paths
Sent by:	[email-masked]

I like that Donald.. We can use "all least cost paths", that is technically
more precise and represent exactly what IS-IS does.

Thanks
Tissa

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Donald Eastlake
Sent: Sunday, April 29, 2012 6:27 PM
To: [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

I don't think the wording "all paths" should ever be used. If you the it
literally, it would even include paths that go through some RBridges more
than once.

I don't particularly like "all ECMP paths" either. I think the clearest
wording is "all least cost paths" if you are talking about known unicast.
(And "all distribution tree paths" if you were talking about
multi-destination frames.)

Thanks,
Donald

> AFAIK MPLS doesn't have a locally defined ECMP hash function in every
hop.

---

From: James Carlson <[email-masked]>
Date: Mon, 30 Apr 2012 11:59:14 -0400

> paths and so of course we don't want to use this definition.

Indeed.  There are (at least) an infinite number of those if you include
loops.  :-/

> hashing implementation on the local Rbridges' (3).

I don't think (3) can actually be computed in any meaningful way.  You'd
have to know the exact hashing algorithm at each node and then perform
some sort of analysis to figure out which input values cause which
forwarding choices to be made.

But the algorithms aren't known (outside of the source code for each
node) and the analysis itself (in the general case) requires running
trials on each possible input value.  Unfortunately, the Universe will
eventually hit the big crunch or heat death, and poor TRILL management
software will still be trying to figure out whether some ECMP choices in
Podunk can or can't be made.

I think only (2) is really meaningful.  Besides, if the problems that
are described for (3) occur, that's an implementation bug, not a
feature.  The problem of cascading ECMP nodes leading to holes in the
hash values is a well-known and well-understood problem, and can be
mitigated by having each node mix in locally-chosen stable data into a
decent hash computation.

-- 
James Carlson         42.703N 71.076W         <[email-masked]>

---

From: "Puneet Agarwal" <[email-masked]>
Date: Mon, 30 Apr 2012 17:40:55 +0000

Protocol should be based on option 2 ie all ECMP paths.

Thanks.

-Puneet
From: [email-masked] [mailto:[email-masked]] On Behalf Of David M Bond
Sent: Monday, April 30, 2012 8:39 AM
To: Tissa Senevirathne (tsenevir)
Cc: Donald Eastlake; [email-masked]; [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

So we have 'all possible paths' (1) which could include non-least cost paths and so of course we don't want to use this definition.

Then we have 'all ecmp paths' or 'all least cost paths' (2) which MAY include paths never chosen by a transit Rbridge because of the local hashing choices.

Then we have 'all the least cost paths which may be chosen given the hashing implementation on the local Rbridges' (3).

I wonder if choice (2) is useful or do we only really care about choice (3). For instance, if you have 16 equal cost paths from A to B and your hashing only will ever use 2 of those paths do we care about reporting back ecmp paths that will never in practice be used? Perhaps the definition should be tightened to only require determination of all least cost paths that could be used given the local hashing implementation. Or am I misunderstanding the conversation and is this already the point being made between theoretical paths and least cost paths.

Thanks,
David

[Inactive hide details for "Tissa Senevirathne (tsenevir)" ---04/29/2012 11:43:07 PM---I like that Donald.. We can use "all leas]"Tissa Senevirathne (tsenevir)" ---04/29/2012 11:43:07 PM---I like that Donald.. We can use "all least cost paths", that is technically more precise and represe

From: "Tissa Senevirathne (tsenevir)" <[email-masked]<mailto:[email-masked]>>
To: "Donald Eastlake" <[email-masked]<mailto:[email-masked]>>, <[email-masked]<mailto:[email-masked]>>
Date: 04/29/2012 11:43 PM
Subject: Re: [trill] TRILL OAM Requirements: available paths
Sent by: [email-masked]<mailto:[email-masked]>

________________________________

Thanks
Tissa

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Donald Eastlake
Sent: Sunday, April 29, 2012 6:27 PM
To: [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

Thanks,
Donald
=============================
 Donald E. Eastlake 3rd   +1-508-333-2270 (cell)
 155 Beaver Street, Milford, MA 01757 USA
 [email-masked]<mailto:[email-masked]>

On Sat, Apr 28, 2012 at 11:45 PM, Erik Nordmark <[email-masked]<mailto:[email-masked]>> wrote:
>> From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]] On
>> Behalf Of Erik Nordmark
>> Cc: [email-masked]<mailto:[email-masked]>
>>> From: Erik Nordmark<[email-masked]<mailto:[email-masked]>>
>>> To: [email-masked]<mailto:[email-masked]>
>>> [email-masked]<mailto:[email-masked]>
>>> [email-masked]<mailto:[email-masked]>
>> [email-masked]<mailto:[email-masked]>
> [email-masked]<mailto:[email-masked]>
_______________________________________________
trill mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/trill
_______________________________________________
trill mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/trill

---

From: Santosh Rajagopalan <[email-masked]>
Date: Mon, 30 Apr 2012 10:51:20 -0700

I think OAM should only be concerned about option 3. Option 2 can easily 
be discovered by doing a route query using the cli or snmp etc. Given that 
the operator already knows that "route to RB X has 4 ecmps", she's 
probably interested in finding out how many of those will actually ever be 
used, which is (3).
--
Sunny Rajagopalan

From:   "Puneet Agarwal" <[email-masked]>
To:     David M Bond/Bedford/IBM@IBMUS, "Tissa Senevirathne (tsenevir)" 
<[email-masked]>
Cc:     Donald Eastlake <[email-masked]>, "[email-masked]" 
<[email-masked]>, "[email-masked]" <[email-masked]>
Date:   04/30/2012 10:45 AM
Subject:        Re: [trill] TRILL OAM Requirements: available paths
Sent by:        [email-masked]

Thanks.
 
-Puneet
David M Bond

I wonder if choice (2) is useful or do we only really care about choice 
(3). For instance, if you have 16 equal cost paths from A to B and your 
hashing only will ever use 2 of those paths do we care about reporting 
back ecmp paths that will never in practice be used? Perhaps the 
definition should be tightened to only require determination of all least 
cost paths that could be used given the local hashing implementation. Or 
am I misunderstanding the conversation and is this already the point being 
made between theoretical paths and least cost paths.

Thanks,
David

"Tissa Senevirathne (tsenevir)" ---04/29/2012 11:43:07 PM---I like that 
Donald.. We can use "all least cost paths", that is technically more 
precise and represe

I like that Donald.. We can use "all least cost paths", that is 
technically more precise and represent exactly what IS-IS does.

Thanks
Tissa

-----Original Message-----

Thanks,
Donald

hop.

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Mon, 30 Apr 2012 12:28:39 -0700

Let me start from the basics.

1.       TRILL is all about multiple active paths.

2.       Multiple active paths are derived from least cost paths to a
specific destinations.

3.       Well defined and implemented Hashing algorithms provide an
almost even distribution across all of the available least cost paths to
a destination

4.       If a given flow "x" does not map to  a specific least cost
path, does not map to a specific least cost path does not mean another
flow "y" to the sam destination will not map to the that path. 

5.       Well implemented hashing algorithms provide even distribution
of flows.

6.       Hence it is important to have ability to test all available
least cost paths to a destination.

7.       It is an implementation defect, If there is an implementation
out there which does not hash flows (over a longer sampling period)  in
to a specific "least cost path" of set of least cost paths to a
destination, among all available "least cost paths" to that destination.

From: David M Bond [mailto:[email-masked]] 
Sent: Monday, April 30, 2012 8:39 AM
To: Tissa Senevirathne (tsenevir)
Cc: Donald Eastlake; [email-masked]; [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

I wonder if choice (2) is useful or do we only really care about choice
(3). For instance, if you have 16 equal cost paths from A to B and your
hashing only will ever use 2 of those paths do we care about reporting
back ecmp paths that will never in practice be used? Perhaps the
definition should be tightened to only require determination of all
least cost paths that could be used given the local hashing
implementation. Or am I misunderstanding the conversation and is this
already the point being made between theoretical paths and least cost
paths.

Thanks,
David

Thanks
Tissa

-----Original Message-----
Of Donald Eastlake

I don't think the wording "all paths" should ever be used. If you the it
literally, it would even include paths that go through some RBridges
more than once.

I don't particularly like "all ECMP paths" either. I think the clearest
wording is "all least cost paths" if you are talking about known
unicast. (And "all distribution tree paths" if you were talking about
multi-destination frames.)

Thanks,
Donald

hop.

---

From: Santosh Rajagopalan <[email-masked]>
Date: Mon, 30 Apr 2012 13:04:34 -0700

Tissa,
Hash polarization can result in some of the ecmp paths being unutilized. 
In Eric's example:

                R1
               /  \
              /    \
             /      \
            /        \
           /          \
        RB11          RB12
        /  \          /  \
       /    \        /    \
    RB111  RB112  RB121  RB122
       \      \    /      /
        \      \  /      /
         \      \/      /
          ------R2------

If R1 and RB12 use the same hash polynomial & seed, then *all* flows which 
arrive at RB12 will go along the link to RB122 - the link to RB121 from 
RB12 will never be used. The OAM tool should allow us to figure out this 
is happening, instead of giving us redundant information already available 
in ISIS lsdb.
I would hesitate to call this a defect. While it is true that a lot of 
asics have countermeasures for this (usually by including a random seed as 
input to the hash polynomial), you cannot rule this out 100%. Please look 
at this documentation from a well known networking company ;-)
http://www.cisco.com/en/US/docs/ios/12_4t/ip_mcast/configuration/guide/mctlsplt.html#wp1064501 

--
Sunny

From:   "Tissa Senevirathne (tsenevir)" <[email-masked]>
To:     David M Bond/Bedford/IBM@IBMUS
Cc:     Donald Eastlake <[email-masked]>, [email-masked], 
[email-masked]
Date:   04/30/2012 12:29 PM
Subject:        Re: [trill] TRILL OAM Requirements: available paths
Sent by:        [email-masked]

1.       TRILL is all about multiple active paths.
2.       Multiple active paths are derived from least cost paths to a 
specific destinations.
3.       Well defined and implemented Hashing algorithms provide an almost 
even distribution across all of the available least cost paths to a 
destination
4.       If a given flow “x” does not map to  a specific least cost path, 
does not map to a specific least cost path does not mean another flow “y” 
to the sam destination will not map to the that path. 
5.       Well implemented hashing algorithms provide even distribution of 
flows.
6.       Hence it is important to have ability to test all available least 
cost paths to a destination.
7.       It is an implementation defect, If there is an implementation out 
there which does not hash flows (over a longer sampling period)  in to a 
specific “least cost path” of set of least cost paths to a destination, 
among all available “least cost paths” to that destination.

Thanks,
David

Thanks
Tissa

-----Original Message-----

Thanks,
Donald

hop.

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Mon, 30 Apr 2012 13:13:45 -0700

Sunny

Are we talking about a single flow here or multiple flows ?

From: [email-masked] [mailto:[email-masked]] On Behalf Of Santosh Rajagopalan
Sent: Monday, April 30, 2012 1:05 PM
To: Tissa Senevirathne (tsenevir)
Cc: Donald Eastlake; [email-masked]; David M Bond; [email-masked]
Subject: Re: [trill] TRILL OAM Requirements: available paths

Tissa, 
Hash polarization can result in some of the ecmp paths being unutilized. In Eric's example: 

               R1
              /  \
             /    \
            /      \
           /        \
          /          \
       RB11          RB12
       /  \          /  \
      /    \        /    \
   RB111  RB112  RB121  RB122
      \      \    /      /
       \      \  /      /
        \      \/      /
         ------R2------

If R1 and RB12 use the same hash polynomial & seed, then *all* flows which arrive at RB12 will go along the link to RB122 - the link to RB121 from RB12 will never be used. The OAM tool should allow us to figure out this is happening, instead of giving us redundant information already available in ISIS lsdb. 
I would hesitate to call this a defect. While it is true that a lot of asics have countermeasures for this (usually by including a random seed as input to the hash polynomial), you cannot rule this out 100%. Please look at this documentation from a well known networking company ;-) 
http://www.cisco.com/en/US/docs/ios/12_4t/ip_mcast/configuration/guide/mctlsplt.html#wp1064501 

-- 
Sunny 

Cc:        Donald Eastlake <[email-masked]>, [email-masked], [email-masked] 

  
1.       TRILL is all about multiple active paths. 
2.       Multiple active paths are derived from least cost paths to a specific destinations. 
3.       Well defined and implemented Hashing algorithms provide an almost even distribution across all of the available least cost paths to a destination 
4.       If a given flow “x” does not map to  a specific least cost path, does not map to a specific least cost path does not mean another flow “y” to the sam destination will not map to the that path. 
5.       Well implemented hashing algorithms provide even distribution of flows. 
6.       Hence it is important to have ability to test all available least cost paths to a destination. 
7.       It is an implementation defect, If there is an implementation out there which does not hash flows (over a longer sampling period)  in to a specific “least cost path” of set of least cost paths to a destination, among all available “least cost paths” to that destination. 
  
From: David M Bond [mailto:[email-masked] <mailto:[email-masked]> ] 

Thanks,
David

 "Tissa Senevirathne (tsenevir)" ---04/29/2012 11:43:07 PM---I like that Donald.. We can use "all least cost paths", that is technically more precise and represe

From: "Tissa Senevirathne (tsenevir)" <[email-masked] <mailto:[email-masked]> >
To: "Donald Eastlake" <[email-masked] <mailto:[email-masked]> >, <[email-masked] <mailto:[email-masked]> >
Date: 04/29/2012 11:43 PM
Subject: Re: [trill] TRILL OAM Requirements: available paths
Sent by: [email-masked] <mailto:[email-masked]>  

Thanks
Tissa

-----Original Message-----
From: [email-masked] <mailto:[email-masked]>  [mailto:[email-masked] <mailto:[email-masked]> ] On Behalf Of Donald Eastlake
Sent: Sunday, April 29, 2012 6:27 PM
To: [email-masked] <mailto:[email-masked]> 
Subject: Re: [trill] TRILL OAM Requirements: available paths

Thanks,
Donald
=============================
Donald E. Eastlake 3rd   +1-508-333-2270 (cell)
155 Beaver Street, Milford, MA 01757 USA
[email-masked] <mailto:[email-masked]> 

On Sat, Apr 28, 2012 at 11:45 PM, Erik Nordmark <[email-masked] <mailto:[email-masked]> > wrote:
>> From: [email-masked] <mailto:[email-masked]>  [mailto:[email-masked] <mailto:[email-masked]> ] On 
>> Behalf Of Erik Nordmark
>> Cc: [email-masked] <mailto:[email-masked]> 
>>> From: Erik Nordmark<[email-masked] <mailto:[email-masked]> >
>>> To: [email-masked] <mailto:[email-masked]> 
>>> [email-masked] <mailto:[email-masked]> 
>>> [email-masked] <mailto:[email-masked]> 
>>> https://www.ietf.org/mailman/listinfo/trill <https://www.ietf.org/mailman/listinfo/trill> 
>>>
>>>
>>
>> [email-masked] <mailto:[email-masked]> 
>> https://www.ietf.org/mailman/listinfo/trill <https://www.ietf.org/mailman/listinfo/trill> 
>>
>
> [email-masked] <mailto:[email-masked]> 
> https://www.ietf.org/mailman/listinfo/trill <https://www.ietf.org/mailman/listinfo/trill> 
_______________________________________________
trill mailing list
[email-masked] <mailto:[email-masked]> 
https://www.ietf.org/mailman/listinfo/trill <https://www.ietf.org/mailman/listinfo/trill> 
_______________________________________________
trill mailing list
[email-masked] <mailto:[email-masked]> 
https://www.ietf.org/mailman/listinfo/trill <https://www.ietf.org/mailman/listinfo/trill> 
_______________________________________________
trill mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/trill <https://www.ietf.org/mailman/listinfo/trill>

---

From: Santosh Rajagopalan <[email-masked]>
Date: Mon, 30 Apr 2012 13:25:22 -0700

When polarization strikes, in the example below, all flows starting from 
R1 would use RB12-RB122 (because the hash result was "2" at R1 as well as 
at RB12). No flows starting from R1 would ever go along the  RB12-RB121 
path. It is common to export an interface for the user to change the seed 
to the hash when she detects polarization has occurred:

http://www.cisco.com/en/US/prod/collateral/switches/ps9441/ps9402/white_paper_c11-687554.html#wp9000286 

From:   "Tissa Senevirathne (tsenevir)" <[email-masked]>
To:     Santosh Rajagopalan/Santa Clara/IBM@IBMUS
Cc:     "Donald Eastlake" <[email-masked]>, <[email-masked]>, 
David M Bond/Bedford/IBM@IBMUS, <[email-masked]>
Date:   04/30/2012 01:14 PM
Subject:        RE: [trill] TRILL OAM Requirements: available paths

Sunny

Santosh Rajagopalan
 
Tissa, 

               R1
              /  \
             /    \
            /      \
           /        \
          /          \
       RB11          RB12
       /  \          /  \
      /    \        /    \
   RB111  RB112  RB121  RB122
      \      \    /      /
       \      \  /      /
        \      \/      /
         ------R2------

-- 
Sunny 

  

Thanks,
David

Thanks
Tissa

-----Original Message-----

Thanks,
Donald

hop.

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Mon, 30 Apr 2012 14:14:02 -0700

We are now discussion about sub standard implementations that get to such polarizations.  We should not water down the requirements to cater in sub standard implementations.

What we should do is to add a requirements such the RBridges have ability to provide statistical counts on  flow distribution over ECMP.

From: Santosh Rajagopalan [mailto:[email-masked]] 
Sent: Monday, April 30, 2012 1:25 PM
To: Tissa Senevirathne (tsenevir)
Cc: Donald Eastlake; David M Bond; [email-masked]; [email-masked]
Subject: RE: [trill] TRILL OAM Requirements: available paths

When polarization strikes, in the example below, all flows starting from R1 would use RB12-RB122 (because the hash result was "2" at R1 as well as at RB12). No flows starting from R1 would ever go along the  RB12-RB121 path. It is common to export an interface for the user to change the seed to the hash when she detects polarization has occurred: 

Cc:        "Donald Eastlake" <[email-masked]>, <[email-masked]>, David M Bond/Bedford/IBM@IBMUS, <[email-masked]> 

Sunny 

From: [email-masked] [mailto:[email-masked] <mailto:[email-masked]> ] On Behalf Of Santosh Rajagopalan
  
Tissa, 

              R1
             /  \
            /    \
           /      \
          /        \
         /          \
      RB11          RB12
      /  \          /  \
     /    \        /    \
  RB111  RB112  RB121  RB122
     \      \    /      /
      \      \  /      /
       \      \/      /
        ------R2------

-- 
Sunny 

Cc:        Donald Eastlake <[email-masked] <mailto:[email-masked]> >, [email-masked] <mailto:[email-masked]> , [email-masked] <mailto:[email-masked]>  

 
 
Cc: Donald Eastlake; [email-masked] <mailto:[email-masked]> ; [email-masked] <mailto:[email-masked]> 

Thanks,
David

Thanks
Tissa

-----Original Message-----
From: [email-masked] <mailto:[email-masked]>  [mailto:[email-masked] <mailto:[email-masked]> ] On Behalf Of Donald Eastlake
Sent: Sunday, April 29, 2012 6:27 PM
To: [email-masked] <mailto:[email-masked]> 
Subject: Re: [trill] TRILL OAM Requirements: available paths

Thanks,
Donald

---

From: Donald Eastlake <[email-masked]>
Date: Mon, 30 Apr 2012 17:49:59 -0400

Sunny:

You may hesitate to call an ECMP implementation subject to polarization
defective but I wouldn't hesitate. Polarization is a well known
problem. It's easy to avoid with TRILL: An RBridge can just hash in its
nickname (or one of its nicknames picked consistently if it has more than
one). This seems better than some interface to set a seed or the like.
TRILL tries to be minimum configuration and the nickname is known to be
unique.

Thanks,
Donald

On Mon, Apr 30, 2012 at 5:14 PM, Tissa Senevirathne (tsenevir) <
[email-masked]> wrote:

> We are now discussion about sub standard implementations that get to such
> polarizations.  We should not water down the requirements to cater in sub
> standard implementations.****
>
> ** **
>
> What we should do is to add a requirements such the RBridges have ability
> to provide statistical counts on  flow distribution over ECMP.****
>
> ** **
>
> *From:* Santosh Rajagopalan [mailto:[email-masked]]
> *Sent:* Monday, April 30, 2012 1:25 PM
> *To:* Tissa Senevirathne (tsenevir)
> *Cc:* Donald Eastlake; David M Bond; [email-masked];
> [email-masked]
>
> *Subject:* RE: [trill] TRILL OAM Requirements: available paths****
>
> ** **
>
> Subject:        RE: [trill] TRILL OAM Requirements: available paths ****
> ------------------------------
>
>
>
>
> Sunny
>
> *From:* [email-masked] [mailto:[email-masked]<[email-masked]>]
> *On Behalf Of *Santosh Rajagopalan*
> Sent:* Monday, April 30, 2012 1:05 PM*
> To:* Tissa Senevirathne (tsenevir)*
> Cc:* Donald Eastlake; [email-masked]; David M Bond; [email-masked]
> *
> Subject:* Re: [trill] TRILL OAM Requirements: available paths
>
> Tissa,
> RB12 will never be used. The OAM tool should allow us to figure out this is
> happening, instead of giving us redundant information already available in
> ISIS lsdb.
> at this documentation from a well known networking company ;-) *
> *
> Sent by:        [email-masked] ****
>
> ** **
> ------------------------------
>
>
>
>
>
>  *
> From:* David M Bond [mailto:[email-masked] <[email-masked]>] *
> Sent:* Monday, April 30, 2012 8:39 AM*
> To:* Tissa Senevirathne (tsenevir)*
> Cc:* Donald Eastlake; [email-masked]; [email-masked]*
> Subject:* Re: [trill] TRILL OAM Requirements: available paths
>   ****
>
> [image: Inactive hide details for "Tissa Senevirathne (tsenevir)"
> ---04/29/2012 11:43:07 PM---I like that Donald.. We can use "all leas]"Tissa
> Senevirathne (tsenevir)" ---04/29/2012 11:43:07 PM---I like that Donald..
> We can use "all least cost paths", that is technically more precise and
> represe
>
> Sent by: [email-masked] ****
>
> ** **
> ------------------------------
>
>
>
>
>
>
> From: [email-masked] [mailto:[email-masked]<[email-masked]>]
> On Behalf Of Donald Eastlake
> 155 Beaver Street, Milford, MA 01757 USA*
> [email-masked]
>
>
> >> From: [email-masked] [mailto:[email-masked]<[email-masked]>]
> On
> >> Behalf Of Erik Nordmark
> trill mailing list*
> [email-masked]*
> *https://www.ietf.org/mailman/listinfo/trill
> trill mailing list*
> [email-masked]*
> *https://www.ietf.org/mailman/listinfo/trill
> trill mailing list*
> [email-masked]*
> *https://www.ietf.org/mailman/listinfo/trill ****
>