Subject: Re: [rbridge] dist tree parallel links - proposed solution

From: jeff pickering <[email-masked]>
Date: Tue, 23 Jun 2009 06:15:32 -0700

Ayan,

Thanks much for all the help, but I still think there is a problem. I'll 
try to rearticulate:

Scenario: RB-B is computing dist tree spf and has neighbor RB-A towards 
root.
RB-A has multiple ptpt links to RB-B (ptpt critical to issue) and those 
links are UNEQUAL COST.
RB-B must choose RB-A's lowest cost link (RB-Bs links costs are irrelevant.)
RB-A announces in its LSP only the links to RB-B and their costs. 
(unlike a bcast subnet
where pnode ID would also be included).  It does not include any info 
that might enable
RB-B to identify which link the announced cost is associated with. 
Likewise, the 3way hello
contains nothing that allows mapping remote cost to adjacency. 
Tiebreaking rules based on
circuit ID dont apply because there is no tie.

(note that the wide metric tlv contains only system ID in its 7 octet 
link info).

RB-B could make a choice based on its own link costs, but that would be 
a problem for RPF.
So its seems additional information is needed. I see two options:

1) add some ciruict ID info to the subtlv of the wide metric ISN link.
2) add cost info to the new link capability tlv.
3) enforce some relationship between circuit ID and cost such that 
higher cost
    means less preferred circuit ID. Could then use circuit ID for a 
decision.

3) seems kink of hokey to me.
and since the issue is purely local to RB-A and RB-B, I would prefer 
option 2.

Of course if Im out to lunch, I'd love to hear why.

Regards,
Jeff

Ayan Banerjee wrote:
> Jeff,
>
> At nodes RB-A and RB-B, where this information is necessary during the SPF
> run, LSP link information, adjacency information, metric information etc all
> values are present.
>
> Agree that other nodes do not have the complete information, however, they
> only care about the cost of the link between RB-A and RB-B. The link (among
> the parallel links) to be used  between RB-A and RB-B is needed locally and
> complete information is present at those two nodes.
>
> Thanks,
> Ayan
>
> On 6/22/09 1:09 PM, "jeff pickering" <[email-masked]> wrote:
>
>   
>> Ayan,
>>
>> How? There is no cost info in the 3way hello/handshake and no 3way cid
>> related info
>> in the LSP ISN link (wide narrow or otherwise).
>>
>> Thanks,
>> Jeff
>>
>>
>>
>> Ayan Banerjee wrote:
>>     
>>> Jeff, 
>>>
>>> Agreed. However, from the adjacency state machine (since 3-way is mandatory
>>> in TRILL) one can figure this information.
>>>
>>> Thanks,
>>> Ayan
>>>
>>>
>>> On 6/22/09 12:34 PM, "jeff pickering" <[email-masked]> wrote:
>>>
>>>   
>>>       
>>>> For the local matter of RB-B making its adjacency set, it has 2
>>>> adjcacencies to RB-A and it
>>>> must choose one. The one it must choose is that represented by the
>>>> lowest cost of link of
>>>> the upstream node (RB-A). But for a ptpt link, there is nothing in the
>>>> LSP that would allow
>>>> RB-B to determine which one of its adjacencies corresponded/mapped to
>>>> that link.
>>>>
>>>> Thanks,
>>>> Jeff
>>>>
>>>>
>>>>
>>>> Ayan Banerjee wrote:
>>>>     
>>>>         
>>>>> Jeff,
>>>>>
>>>>> On re-reading your email, I see that you have unequal costs. The costs from
>>>>> the upstream node will be honored for the bi-directional tree.
>>>>>
>>>>> On a separate note, for equal cost multi-path, the link that needs to be
>>>>> used between nodes RB-A and RB-B are a local matter. Other nodes will just
>>>>> "view" the tree as being connected between RB-A and RB-B. I was trying to
>>>>> state how the "local" algorithm is made deterministic.
>>>>>
>>>>> Thanks,
>>>>> Ayan
>>>>>
>>>>>
>>>>> On 6/22/09 11:49 AM, "jeff pickering" <[email-masked]> wrote:
>>>>>
>>>>>   
>>>>>       
>>>>>           
>>>>>> Im sorry if Im being obtuse. This is a non-equal cost issue. RB-A will
>>>>>> advertise in its
>>>>>> LSP ISN entry a link to RB-B and its associated cost, but no (ext/cid
>>>>>> for ptpt) info
>>>>>> which allows RB-B on the other end to determine which one of its
>>>>>> adjacencies (and therefore
>>>>>> ports) the advertised link corresponds to. I understand for bcast, you
>>>>>> can determine this
>>>>>> from the pnode id part on the ISN link, but dont see what info you have
>>>>>> have for ptpt.
>>>>>> (unless I misread the wide metrics spec 5305).
>>>>>>
>>>>>> Jeff
>>>>>>
>>>>>>
>>>>>> Ayan Banerjee wrote:
>>>>>>     
>>>>>>         
>>>>>>             
>>>>>>> Jeff,
>>>>>>>
>>>>>>> In TRILL 3-way handshake is mandatory for P2P links. Hence, each node
>>>>>>> will
>>>>>>> get an unique extended circuit identifier after adjacency formation. On
>>>>>>> LAN
>>>>>>> links, the source mac can be used an identifier for uniqueness of each
>>>>>>> link.
>>>>>>>
>>>>>>> I believe that P2P links are preferred over LAN links. Among the set, in
>>>>>>> the
>>>>>>> event there are multiple "identifiers" then the highest (or lowest - I
>>>>>>> remember that there was some discussion on the list about highest/lowest,
>>>>>>> do
>>>>>>> not recall what we ended up with) one will be chosen for the tree.
>>>>>>>
>>>>>>> Thanks,
>>>>>>> Ayan
>>>>>>>
>>>>>>> On 6/22/09 8:55 AM, "jeff pickering" <[email-masked]> wrote:
>>>>>>>
>>>>>>>   
>>>>>>>       
>>>>>>>           
>>>>>>>               
>>>>>>>> I have a distribution tree parallel links question I was hoping someone
>>>>>>>> could clarify
>>>>>>>> for me.
>>>>>>>>
>>>>>>>> Let's say you have 2 RBs downstream from the root, with parallel links
>>>>>>>> between them.
>>>>>>>>
>>>>>>>> RB-A has cost 10 on link 1, cost 20 on link 2.
>>>>>>>> RB-B has cost 20 on link 1, cost 10 on link 2.
>>>>>>>>
>>>>>>>> Lets say RB-B is downstream from RB-A. When computing its paths, RB-A
>>>>>>>> will clearly
>>>>>>>> use link 1. Whether it shows 1 or 2 links in its LSPs is irrelevant,
>>>>>>>> RB-B still needs to know
>>>>>>>> somehow to choose its adjacency over link 1 for its path to the root.
>>>>>>>> But in the asymetric cost
>>>>>>>> case, I dont see how its can do this. Is there something new in either
>>>>>>>> the LSP or hello that
>>>>>>>> would resolve this?
>>>>>>>>
>>>>>>>> Or should RB-B use its lower cost and if so how does the RPF issue get
>>>>>>>> addressed?
>>>>>>>>
>>>>>>>> Thanks to anyone who can enlighten me.
>>>>>>>>
>>>>>>>> Jeff
>>>>>>>>
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> rbridge mailing list
>>>>>>>> [email-masked]
>>>>>>>> http://mailman.postel.org/mailman/listinfo/rbridge
>>>>>>>>     
>>>>>>>>         
>>>>>>>>            
>>>>>>>>                 
>>>>>>>   
>>>>>>>       
>>>>>>>           
>>>>>>>               
>>>>>   
>>>>>       
>>>>>           
>>>
>>>   
>>>       
>
>
>
>   

_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: Radia Perlman <[email-masked]>
Date: Tue, 23 Jun 2009 09:49:23 -0700

Let me see if I understand your question by restating it.

You are concerned, when calculating the multicast distribution tree from 
root R, that all RBridges
calculate the same tree, and think there might be a problem if someplace 
in the tree there is a link
with asymmetric costs in the two directions. Is that what you are 
concerned about?

I don't think there's a problem with having different bridges calculate 
the tree rooted at R differently,
because they all use the same tree-building algorithm, starting with R, 
searching for paths shortest path first.

But there is an interesting issue.
I believe, when building the tree, looking at the newly treed node, say 
R1, that it is R1's reported cost
to each of R1's neighbors that are used, not neighbor's cost to R1 
(other than the "two way connectivity check",
which I assume only checks that they both report the link exists, but 
not whether the costs are the same).

So...... Suppose the link costs really are very different in the two 
directions for some link. For unicast,
when R is calculating a shortest path tree from itself to each 
destination, it makes sense to use the
link cost outwards from R, and the cost in the reverse direction is 
irrelevant.

However, for multicast, it is a bidirectional tree being built. So, for 
instance, if some node R7 might get
put into the tree as a child of R3, where the link cost R3-R7 is, say 
cost 2, but the reverse cost is, say, 4.5 gazillion,
or R7 might get put into the tree as a child of R4, where the link cost 
R4-R7 and R7-R4 is a reasonable cost in both
directions of, say, 18, then placing R7 as a child of R4 would be a 
better choice than placing R7
as a child of R3.

I don't think we really want to worry about this, but it is interesting.

If we were worried about it, we could use, as the cost of a link between 
R1 and R2, the *average* of the costs
in each direction, for building the multicast tree. If there really were 
links with wildly different costs in
the two directions, it might even be the right thing to do.

Radia

---

From: jeff pickering <[email-masked]>
Date: Tue, 23 Jun 2009 10:54:03 -0700

Actually, I was primarily concerned about RPF check failures. Lets say 
R7 just got put into the multicast
tree as a child of R4 (R7 is the one running the SPF here).
There are multiple links PTPT links between R4 and R7. If the links cost 
differ, R4 will
perform its RPF check when receiving multicast packets from R7 and toss 
packets that dont arrive on
its view of the lowest cost link between the two. That implies that R7 
must know what R4's lowest cost
link is when determining its upstream adjacency for the multicast tree. 
And for a PTPT link, I just dont
see how R7 makes that decision. Clearly things are different if the link 
is broadcast because the link in
the LSP contains a pnode ID which can can be used by R7 to dtermine 
exactly which link is
implied when R4 puts a cost/ISN pair in its LSP.

Please note that this has nothing to do with bcast links, or any router 
other than R4 and R7. All routers, including
R4 and R7 compute the same tree as far as how nodes are interconnected 
in the tree. Its just that R7 may pick
the wrong link over which to forward to R4 and therefore the RPF could fail.

Jeff

Radia Perlman wrote:
> You are concerned, when calculating the multicast distribution tree 
> from root R, that all RBridges
> calculate the same tree, and think there might be a problem if 
> someplace in the tree there is a link
> I don't think there's a problem with having different bridges 
> calculate the tree rooted at R differently,
> because they all use the same tree-building algorithm, starting with 
> R, searching for paths shortest path first.
>
> I believe, when building the tree, looking at the newly treed node, 
> say R1, that it is R1's reported cost
> However, for multicast, it is a bidirectional tree being built. So, 
> for instance, if some node R7 might get
> or R7 might get put into the tree as a child of R4, where the link 
> cost R4-R7 and R7-R4 is a reasonable cost in both
> If we were worried about it, we could use, as the cost of a link 
> between R1 and R2, the *average* of the costs
> in each direction, for building the multicast tree. If there really 
> were links with wildly different costs in
>> Thanks much for all the help, but I still think there is a problem. 
>> I'll try to rearticulate:
>>
>> Scenario: RB-B is computing dist tree spf and has neighbor RB-A 
>> towards root.
>> RB-A has multiple ptpt links to RB-B (ptpt critical to issue) and 
>> those links are UNEQUAL COST.
>> RB-B could make a choice based on its own link costs, but that would 
>> be a problem for RPF.

---

From: Donald Eastlake <[email-masked]>
Date: Tue, 23 Jun 2009 16:02:37 -0400

Hi Jeff,
Draft version -13, which should be posted in a few days, removes the
qualifier "least cost". The preferred path among a set of parallel P2P links
is chosen based only on extended circuit ID.
Thanks,
Donald
=============================
Donald E. Eastlake 3rd   +1-508-634-2066 (home)
155 Beaver Street
Milford, MA 01757 USA
[email-masked]

---

From: jeff pickering <[email-masked]>
Date: Tue, 23 Jun 2009 15:04:03 -0700

Excellent. Thanks for the clarification.

Jeff

Donald Eastlake wrote:
> qualifier "least cost". The preferred path among a set of parallel P2P 
> links is chosen based only on extended circuit ID.
>
> Thanks,
> Donald
> [email-masked] <mailto:[email-masked]>
>
>
> On Tue, Jun 23, 2009 at 1:54 PM, jeff pickering <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>
>     >>> run, LSP link information, adjacency information, metric
>     information
>     >>> etc all
>     >>> values are present.
>     >>>
>     >>> only care about the cost of the link between RB-A and RB-B.
>     The link
>     >>> (among
>     >>> On 6/22/09 1:09 PM, "jeff pickering" <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     >>>
>     >>>
>     >>>> Ayan,
>     >>>>
>     >>>>> Agreed. However, from the adjacency state machine (since
>     3-way is
>     >>>>> mandatory
>     >>>>> On 6/22/09 12:34 PM, "jeff pickering" <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     >>>>>
>     >>>>>
>     >>>>>>> On re-reading your email, I see that you have unequal
>     costs. The
>     >>>>>>> costs from
>     >>>>>>> used between nodes RB-A and RB-B are a local matter. Other
>     nodes
>     >>>>>>> will just
>     >>>>>>> "view" the tree as being connected between RB-A and RB-B.
>     I was
>     >>>>>>> trying to
>     >>>>>>> On 6/22/09 11:49 AM, "jeff pickering"
>     <[email-masked] <mailto:[email-masked]>> wrote:
>     >>>>>>>
>     >>>>>>>
>     >>>>>>>> from the pnode id part on the ISN link, but dont see what
>     info
>     >>>>>>>> you have
>     >>>>>>>> have for ptpt.
>     >>>>>>>>> links, the source mac can be used an identifier for
>     uniqueness
>     >>>>>>>>> of each
>     >>>>>>>>> link.
>     >>>>>>>>>
>     >>>>>>>>> On 6/22/09 8:55 AM, "jeff pickering"
>     <[email-masked] <mailto:[email-masked]>>
>     >>>>>>>>> wrote:
>     >>>>>>>>>
>     >>>>>>>>>
>     >>>>>>>>>> case, I dont see how its can do this. Is there
>     something new
>     >>>>>>>>>> in either
>     >>>>>>>>>> the LSP or hello that
>     >>>>>>>>>> would resolve this?
>     >>>>>>>>>>
>     >>>>>>>>>> Or should RB-B use its lower cost and if so how does
>     the RPF
>     >>>>>>>>>> issue get
>     >>>>>>>>>> addressed?
>     >>>>>>>>>>
>     >>>>>>>>>> [email-masked] <mailto:[email-masked]>
>     >> [email-masked] <mailto:[email-masked]>
>     [email-masked] <mailto:[email-masked]>
> ------------------------------------------------------------------------
>