[rbridge] (slight) modification of how to choose mulitcast trees
Dinesh G Dutt
ddutt at cisco.com
Wed Apr 2 11:36:48 PDT 2008
I'm fine with that,
Dinesh
Anoop Ghanwani wrote:
> I would go even further and say that 1 tree is what
> should be mandated.
>
> Anoop
>
>
>> -----Original Message-----
>> From: rbridge-bounces at postel.org
>> [mailto:rbridge-bounces at postel.org] On Behalf Of Dinesh G Dutt
>> Sent: Tuesday, April 01, 2008 9:33 PM
>> To: Eastlake III Donald-LDE008
>> Cc: Developing a hybrid router/bridge.; Radia Perlman
>> Subject: Re: [rbridge] (slight) modification of how to choose
>> mulitcast trees
>>
>> Why 8 ? I prefer something much less. But again, this isn't
>> something I'd debate much about. Priority will be configured
>> as users want predictablity and determinism.
>>
>> Dinesh
>> Eastlake III Donald-LDE008 wrote:
>>
>>> Hi,
>>>
>>> See below at @@@
>>>
>>> -----Original Message-----
>>> From: Dinesh G Dutt [mailto:ddutt at cisco.com]
>>> Sent: Tuesday, April 01, 2008
>>> To: Radia Perlman
>>> Cc: Eastlake III Donald-LDE008; Developing a hybrid router/bridge.
>>> Subject: Re: [rbridge] (slight) modification of how to choose
>>> mulitcast trees
>>>
>>> Slight modification. I'd want the default to be smaller,
>>>
>> say 2 or 4.
>>
>>> But
>>>
>>> I won't quibble,
>>>
>>> Dinesh
>>>
>>> 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".
>>>>
>>>>
>>> @@@ OK, so let's go with a recommended default of 8.
>>>
>>>
>>>
>>>> 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.
>>>
>>> @@@ I'm fine with order feeding into priority in some
>>>
>> fashion if your
>>
>>> priority is not configured. People who are configuring
>>>
>> ought to know
>>
>>> what they are doing and avoid ties.
>>>
>>> @@@ Thanks,
>>> @@@ Donald
>>>
>>>
>>>
>>>> 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
>>
>> _______________________________________________
>> 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
More information about the rbridge
mailing list