[rbridge] (slight) modification of how to choose mulitcast trees

Tue Apr 1 18:43:04 PDT 2008

I agree with you Radia on both points,

Dinesh
Radia Perlman wrote:
> My only 2 comments on your comments:
> a) I don't see how there can be a default of square root of number of 
> RBridges, since RBridges wouldn't know the number
> of bridges. I'd say we should pick a number like "10".
> b) Sorry -- need to "think aloud" here for a bit.
> A few questions about "order": "ports" is known in advance and doesn't 
> change. "adjacencies" is not known in advance .
> But then you really want "RBridge adjacencies" and not just ports to 
> endnodes...so I'm not sure. Maybe
> it has to be "RBridge adjacencies". But does having a fluctuating 
> "order" cause problems? In theory we might want a pseudonode
> to be a tree root, but pseudonodes don't get nicknames, and therefore 
> can't be specified as a tree root in the TRILL header.
>
> And then using numerically largest works for "order" but not for 
> "distance to me", so that has to be adjusted (shouldn't be hard, perhaps
> making "order" be 1000 minus the number of RBridge adjacencies, going no 
> lower than "0"). And "order" can be calculated from
> the LSP -- it doesn't have to be separately announced. Though if you are 
> connected to a pseudonode do you have to remember
> to count all the RBridges connected to that pseudonode?
>
> It might be simpler to just have "order" feed into priority, as in, if 
> your priority is not configured in advance, then if you have more
> than some number (say 2) RBridge adjacencies, you decrement your 
> priority by 1 for every extra RBridge adjacency. If your
> priority is configured, you'd leave it at whatever it is configured to be.
>
> Radia
>
>
>
>
> Eastlake III Donald-LDE008 wrote:
>   
>> Hi,
>>
>> I agree that the present requirement that all Rbridges default to having
>> the RequestTree be TRUE probably results in Rbridges being required to
>> calculate too many trees in a large campus. See comments below at @@@
>>
>> -----Original Message-----
>> From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org] On
>> Behalf Of Radia Perlman
>> Sent: Friday, March 28, 2008 10:55 PM
>> To: Developing a hybrid router/bridge.
>> Subject: [rbridge] (slight) modification of how to choose mulitcast
>> trees
>>
>> Dinesh suggested the following, as a way of making configuration easier 
>> for how to choose multicast trees.
>>
>> 1) Each RBridge is configured with a priority for being selected a 
>> multicast tree root (with of course a default being a medium priority)
>>
>> 2) Each RBridge R1 is also configured with a parameter indicating "total
>>
>> number of trees in the campus", which R1 announces in its LSP.
>>
>> @@@ So what's the recommended default here? It might sound a bit odd but
>> I would suggest that the default be something like the square root of
>> the number of Rbridges in the campus. (See comment below on volatility.)
>>
>> 3) RBridges are ranked by (priority, ID). The RBridge with the 
>> numerically lowest priority, and then numerically lowest ID being the
>> tie breaker, dictates the total number of trees all the other RBridges 
>> must calculate (the number that R1 announces in its LSP according
>> to rule 2 above.
>>
>> @@@ As long as you are generating a concatenated global priority number
>> like (priority, ID), why not make it a little more clever by having it
>> be (priority, order, ID) or something like that? (Where "order" is the
>> number of adjacencies the Rbridge has, so you'd have to change the
>> ranking to be highest priority is numerically largest...).
>>
>> 4) An RBridge calculates n distribution trees, where n is the number 
>> announced by the lowest (priority, ID) RBridge R1, in R1's LSP,
>> as the "total number of trees". The n trees computed are the ones using 
>> the n numerically lowest (priority, ID) RBridges as roots
>>
>> 5) if RB1 is ingress RBridge on port p, and (*note another parameter 
>> "k"*) is configured to do k-way path splitting on that port for
>> multidestination frames, the k tree roots that RB1 chooses consist of 
>> the three for which the triple "(cost of root to me, priority, ID)" are
>> the k smallest.
>>
>> @@@ Of course the ranking has to be the same so if "order" were added as
>> above, it would have to be added here also.
>>
>> Intuition: suppose there is a topology with a lot of "leaf" RBridges., 
>> and "next level" RBridges that the leaf RBridges connect to.
>> If there are m leaf RBridges connected to next level RBridge RBx, then 
>> there is no reason to compute trees with any of the leaf
>> RBridges as root -- the tree rooted at RBx will be the same tree, and 
>> will indeed be a shortest path tree for each of the attached
>> leaf RBridges. If a leaf RBridge is attached to several next-level 
>> RBridges, the most significant number in the triple -- "cost
>> of root to me" will cause the leaf RBridge to multipath the multicast 
>> among multiple shortest-path trees.
>>
>> @@@ That's all true but the special case of an Rbridge of order 1
>> connected to an Rbridge of order >1 seems so simple to check for that
>> you could just rule them out. Or, if "order" were added to the
>> comparison tuple as above, in the default case where all Rbridges have
>> the default priority, order 1 Rbridges would automatically have lowest
>> priority. (See also slides 8 and 9 of my presentation at 
>> http://www.ietf.org/proceedings/07jul/slides/trill-3/sld1.htm.)
>>
>> This seems completely safe, and easier than configuring, for each 
>> RBridge, the set of root RBridges to choose for multicast tree roots.
>> It also means that you can configure in one place a total number of 
>> roots, rather than possibly having too many RBridges volunteer for
>> being tree roots, and winding up with too much overhead on RBridges 
>> because they'll have to compute a tree for every RBridge that
>> says it will want to be a tree root.
>>
>> There might be a concern about volatility -- when an RBridge with 
>> numerically low priority goes down, it might cause:
>> a) a change to the total number of trees to be computed by everyone 
>> (since the next best might be configured with a different number)
>> b) a change to the list of "tree roots I will choose" announced by RB2 
>> when one of the roots for the k best (cost to me, priority, ID) goes
>> down.
>>
>> @@@ There are plenty of other possible causes for volatility. Like a
>> high priority-to-be-tree-root Rbridge coming up or an Rbridge's
>> priority-to-be-tree-root being reconfigured. But the solution to them
>> all is the same. An Rbridge has to keep calculating (or at least keep
>> around) trees for old roots as long as their reasonably might be frames
>> in transit specifying those roots. It has to calculate trees for any new
>> roots right away and, if appropriate, start advertising that it might
>> use them. What root (or from what set of roots) to choose for new native
>> multi-destination frames an Rbridge is encapsulating is a bit messier.
>> Seems to me that until it is reasonably sure that information has
>> propagated concerning new roots, it should only use those in the
>> intersection of the sets of old and new roots. If that intersection is
>> null, something only likely to occur when there are a very small number
>> of tree roots, you have a bit of a problem and might as well use the new
>> root(s). But this is no worse than under the previous scheme if
>> RequestTree was FALSE for all Rbridges and the Rbridge with the lowest
>> system ID, which had defaulted to being the only tree root, goes down.
>>
>> Other than that, I can't think of any possible problems.
>>
>> @@@ Overall, I like the proposal.
>>
>> Radia
>>
>> @@@ Thanks,
>> @@@ Donald
>>
>> _______________________________________________
>> rbridge mailing list
>> rbridge at postel.org
>> http://mailman.postel.org/mailman/listinfo/rbridge
>>   
>>     
>
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge
>
>   

-- 
We make our world significant by the courage of our questions and by 
the depth of our answers.                               - Carl Sagan