[rbridge] (slight) modification of how to choose mulitcast trees
Radia Perlman
Radia.Perlman at sun.com
Sat Apr 5 18:05:37 PDT 2008
I don't understand. What do you mean by "mandated"? Do you mean
"recommended default=1"?
That probably wouldn't be controversial. But if you mean "mandated" as
in, "only do one tree" (which was my original
assumption, by the way), I'm sure that would be controversial.
I'm almost certain you meant "recommended default=1", rather than
"mandate one tree"
but it would be good to clarify what you meant.
Radia
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
>>
>>
More information about the rbridge
mailing list