<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7652.24">
<TITLE>RE: [rbridge] (slight) modification of how to choose mulitcast trees</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<BR>
<P><FONT SIZE=2>Yes, I meant recommended default=1. To me, that<BR>
would mandate that my implementation be capable<BR>
of computing at least that many trees, hence<BR>
the choice of language.<BR>
<BR>
Anoop<BR>
<BR>
-----Original Message-----<BR>
From: rbridge-bounces@postel.org on behalf of Radia Perlman<BR>
Sent: Sat 4/5/2008 6:05 PM<BR>
To: Developing a hybrid router/bridge.<BR>
Subject: Re: [rbridge] (slight) modification of how to choose mulitcast trees<BR>
<BR>
I don't understand. What do you mean by "mandated"? Do you mean<BR>
"recommended default=1"?<BR>
That probably wouldn't be controversial. But if you mean "mandated" as<BR>
in, "only do one tree" (which was my original<BR>
assumption, by the way), I'm sure that would be controversial.<BR>
<BR>
I'm almost certain you meant "recommended default=1", rather than<BR>
"mandate one tree"<BR>
but it would be good to clarify what you meant.<BR>
<BR>
Radia<BR>
<BR>
<BR>
<BR>
Anoop Ghanwani wrote:<BR>
> I would go even further and say that 1 tree is what<BR>
> should be mandated.<BR>
><BR>
> Anoop<BR>
><BR>
> <BR>
>> -----Original Message-----<BR>
>> From: rbridge-bounces@postel.org<BR>
>> [<A HREF="mailto:rbridge-bounces@postel.org">mailto:rbridge-bounces@postel.org</A>] On Behalf Of Dinesh G Dutt<BR>
>> Sent: Tuesday, April 01, 2008 9:33 PM<BR>
>> To: Eastlake III Donald-LDE008<BR>
>> Cc: Developing a hybrid router/bridge.; Radia Perlman<BR>
>> Subject: Re: [rbridge] (slight) modification of how to choose<BR>
>> mulitcast trees<BR>
>><BR>
>> Why 8 ? I prefer something much less. But again, this isn't<BR>
>> something I'd debate much about. Priority will be configured<BR>
>> as users want predictablity and determinism.<BR>
>><BR>
>> Dinesh<BR>
>> Eastlake III Donald-LDE008 wrote:<BR>
>> <BR>
>>> Hi,<BR>
>>><BR>
>>> See below at @@@<BR>
>>><BR>
>>> -----Original Message-----<BR>
>>> From: Dinesh G Dutt [<A HREF="mailto:ddutt@cisco.com">mailto:ddutt@cisco.com</A>]<BR>
>>> Sent: Tuesday, April 01, 2008<BR>
>>> To: Radia Perlman<BR>
>>> Cc: Eastlake III Donald-LDE008; Developing a hybrid router/bridge.<BR>
>>> Subject: Re: [rbridge] (slight) modification of how to choose<BR>
>>> mulitcast trees<BR>
>>><BR>
>>> Slight modification. I'd want the default to be smaller,<BR>
>>> <BR>
>> say 2 or 4.<BR>
>> <BR>
>>> But<BR>
>>><BR>
>>> I won't quibble,<BR>
>>><BR>
>>> Dinesh<BR>
>>><BR>
>>> I agree with you Radia on both points,<BR>
>>><BR>
>>> Dinesh<BR>
>>><BR>
>>> Radia Perlman wrote:<BR>
>>> <BR>
>>> <BR>
>>>> My only 2 comments on your comments:<BR>
>>>> a) I don't see how there can be a default of square root<BR>
>>>> <BR>
>> of number of<BR>
>> <BR>
>>>> RBridges, since RBridges wouldn't know the number of<BR>
>>>> <BR>
>> bridges. I'd say<BR>
>> <BR>
>>>> we should pick a number like "10".<BR>
>>>> <BR>
>>>> <BR>
>>> @@@ OK, so let's go with a recommended default of 8.<BR>
>>><BR>
>>> <BR>
>>> <BR>
>>>> b) Sorry -- need to "think aloud" here for a bit.<BR>
>>>> A few questions about "order": "ports" is known in advance and<BR>
>>>> doesn't<BR>
>>>> <BR>
>>>> <BR>
>>> <BR>
>>> <BR>
>>>> change. "adjacencies" is not known in advance .<BR>
>>>> But then you really want "RBridge adjacencies" and not<BR>
>>>> <BR>
>> just ports to<BR>
>> <BR>
>>>> endnodes...so I'm not sure. Maybe it has to be "RBridge<BR>
>>>> <BR>
>> adjacencies".<BR>
>> <BR>
>>>> But does having a fluctuating "order" cause problems? In theory we<BR>
>>>> might want a pseudonode to be a tree root, but pseudonodes<BR>
>>>> <BR>
>> don't get<BR>
>> <BR>
>>>> nicknames, and therefore can't be specified as a tree root in the<BR>
>>>> TRILL header.<BR>
>>>><BR>
>>>> And then using numerically largest works for "order" but not for<BR>
>>>> "distance to me", so that has to be adjusted (shouldn't be hard,<BR>
>>>> <BR>
>>>> <BR>
>>> perhaps<BR>
>>> <BR>
>>> <BR>
>>>> making "order" be 1000 minus the number of RBridge<BR>
>>>> <BR>
>> adjacencies, going<BR>
>> <BR>
>>>> <BR>
>>>> <BR>
>>> no<BR>
>>> <BR>
>>> <BR>
>>>> lower than "0"). And "order" can be calculated from the LSP -- it<BR>
>>>> doesn't have to be separately announced. Though if you<BR>
>>>> <BR>
>>>> <BR>
>>> are<BR>
>>> <BR>
>>> <BR>
>>>> connected to a pseudonode do you have to remember to count all the<BR>
>>>> RBridges connected to that pseudonode?<BR>
>>>><BR>
>>>> It might be simpler to just have "order" feed into<BR>
>>>> <BR>
>> priority, as in,<BR>
>> <BR>
>>>> if<BR>
>>>> <BR>
>>>> <BR>
>>> <BR>
>>> <BR>
>>>> your priority is not configured in advance, then if you have more<BR>
>>>> than some number (say 2) RBridge adjacencies, you decrement your<BR>
>>>> priority by 1 for every extra RBridge adjacency. If your<BR>
>>>> <BR>
>> priority is<BR>
>> <BR>
>>>> configured, you'd leave it at whatever it is configured to<BR>
>>>> <BR>
>>>> <BR>
>>> be.<BR>
>>><BR>
>>> @@@ I'm fine with order feeding into priority in some<BR>
>>> <BR>
>> fashion if your<BR>
>> <BR>
>>> priority is not configured. People who are configuring<BR>
>>> <BR>
>> ought to know<BR>
>> <BR>
>>> what they are doing and avoid ties.<BR>
>>><BR>
>>> @@@ Thanks,<BR>
>>> @@@ Donald<BR>
>>><BR>
>>> <BR>
>>> <BR>
>>>> Radia<BR>
>>>><BR>
>>>><BR>
>>>><BR>
>>>><BR>
>>>> Eastlake III Donald-LDE008 wrote:<BR>
>>>> <BR>
>>>> <BR>
>>>> <BR>
>>>>> Hi,<BR>
>>>>><BR>
>>>>> I agree that the present requirement that all Rbridges default to<BR>
>>>>> <BR>
>>>>> <BR>
>>> having<BR>
>>> <BR>
>>> <BR>
>>>>> the RequestTree be TRUE probably results in Rbridges<BR>
>>>>> <BR>
>> being required<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> to<BR>
>>> <BR>
>>> <BR>
>>>>> calculate too many trees in a large campus. See comments below at<BR>
>>>>> @@@<BR>
>>>>><BR>
>>>>> -----Original Message-----<BR>
>>>>> From: rbridge-bounces@postel.org<BR>
>>>>> <BR>
>> [<A HREF="mailto:rbridge-bounces@postel.org">mailto:rbridge-bounces@postel.org</A>]<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> On<BR>
>>> <BR>
>>> <BR>
>>>>> Behalf Of Radia Perlman<BR>
>>>>> Sent: Friday, March 28, 2008 10:55 PM<BR>
>>>>> To: Developing a hybrid router/bridge.<BR>
>>>>> Subject: [rbridge] (slight) modification of how to choose<BR>
>>>>> <BR>
>> mulitcast<BR>
>> <BR>
>>>>> trees<BR>
>>>>><BR>
>>>>> Dinesh suggested the following, as a way of making configuration<BR>
>>>>> <BR>
>>>>> <BR>
>>> easier<BR>
>>> <BR>
>>> <BR>
>>>>> for how to choose multicast trees.<BR>
>>>>><BR>
>>>>> 1) Each RBridge is configured with a priority for being<BR>
>>>>> <BR>
>> selected a<BR>
>> <BR>
>>>>> multicast tree root (with of course a default being a medium<BR>
>>>>> <BR>
>>>>> <BR>
>>> priority)<BR>
>>> <BR>
>>> <BR>
>>>>> 2) Each RBridge R1 is also configured with a parameter indicating<BR>
>>>>> <BR>
>>>>> <BR>
>>> "total<BR>
>>> <BR>
>>> <BR>
>>>>> number of trees in the campus", which R1 announces in its LSP.<BR>
>>>>><BR>
>>>>> @@@ So what's the recommended default here? It might<BR>
>>>>> <BR>
>> sound a bit odd<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> but<BR>
>>> <BR>
>>> <BR>
>>>>> I would suggest that the default be something like the<BR>
>>>>> <BR>
>> square root<BR>
>> <BR>
>>>>> of the number of Rbridges in the campus. (See comment below on<BR>
>>>>> <BR>
>>>>> <BR>
>>> volatility.)<BR>
>>> <BR>
>>> <BR>
>>>>> 3) RBridges are ranked by (priority, ID). The RBridge with the<BR>
>>>>> numerically lowest priority, and then numerically lowest ID being<BR>
>>>>> the tie breaker, dictates the total number of trees all the other<BR>
>>>>> <BR>
>>>>> <BR>
>>> RBridges<BR>
>>> <BR>
>>> <BR>
>>>>> must calculate (the number that R1 announces in its LSP<BR>
>>>>> <BR>
>> according to<BR>
>> <BR>
>>>>> rule 2 above.<BR>
>>>>><BR>
>>>>> @@@ As long as you are generating a concatenated global priority<BR>
>>>>> <BR>
>>>>> <BR>
>>> number<BR>
>>> <BR>
>>> <BR>
>>>>> like (priority, ID), why not make it a little more clever<BR>
>>>>> <BR>
>> by having<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> it<BR>
>>> <BR>
>>> <BR>
>>>>> be (priority, order, ID) or something like that? (Where "order" is<BR>
>>>>> <BR>
>>>>> <BR>
>>> the<BR>
>>> <BR>
>>> <BR>
>>>>> number of adjacencies the Rbridge has, so you'd have to<BR>
>>>>> <BR>
>> change the<BR>
>> <BR>
>>>>> ranking to be highest priority is numerically largest...).<BR>
>>>>><BR>
>>>>> 4) An RBridge calculates n distribution trees, where n is<BR>
>>>>> <BR>
>> the number<BR>
>> <BR>
>>>>> announced by the lowest (priority, ID) RBridge R1, in<BR>
>>>>> <BR>
>> R1's LSP, as<BR>
>> <BR>
>>>>> the "total number of trees". The n trees computed are the ones<BR>
>>>>> <BR>
>>>>> <BR>
>>> using<BR>
>>> <BR>
>>> <BR>
>>>>> the n numerically lowest (priority, ID) RBridges as roots<BR>
>>>>><BR>
>>>>> 5) if RB1 is ingress RBridge on port p, and (*note<BR>
>>>>> <BR>
>> another parameter<BR>
>> <BR>
>>>>> "k"*) is configured to do k-way path splitting on that port for<BR>
>>>>> multidestination frames, the k tree roots that RB1<BR>
>>>>> <BR>
>> chooses consist<BR>
>> <BR>
>>>>> of<BR>
>>>>> <BR>
>>>>> <BR>
>>> <BR>
>>> <BR>
>>>>> the three for which the triple "(cost of root to me,<BR>
>>>>> <BR>
>> priority, ID)"<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> are<BR>
>>> <BR>
>>> <BR>
>>>>> the k smallest.<BR>
>>>>><BR>
>>>>> @@@ Of course the ranking has to be the same so if "order" were<BR>
>>>>> added<BR>
>>>>> <BR>
>>>>> <BR>
>>> as<BR>
>>> <BR>
>>> <BR>
>>>>> above, it would have to be added here also.<BR>
>>>>><BR>
>>>>> Intuition: suppose there is a topology with a lot of "leaf"<BR>
>>>>> <BR>
>>>>> <BR>
>>> RBridges.,<BR>
>>> <BR>
>>> <BR>
>>>>> and "next level" RBridges that the leaf RBridges connect to.<BR>
>>>>> If there are m leaf RBridges connected to next level RBridge RBx,<BR>
>>>>> <BR>
>>>>> <BR>
>>> then<BR>
>>> <BR>
>>> <BR>
>>>>> there is no reason to compute trees with any of the leaf<BR>
>>>>> <BR>
>> RBridges as<BR>
>> <BR>
>>>>> root -- the tree rooted at RBx will be the same tree, and<BR>
>>>>> <BR>
>>>>> <BR>
>>> <BR>
>>> <BR>
>>>>> will indeed be a shortest path tree for each of the attached leaf<BR>
>>>>> RBridges. If a leaf RBridge is attached to several next-level<BR>
>>>>> RBridges, the most significant number in the triple --<BR>
>>>>> <BR>
>> "cost of root<BR>
>> <BR>
>>>>> to me" will cause the leaf RBridge to multipath the multicast<BR>
>>>>> <BR>
>>>>> <BR>
>>> <BR>
>>> <BR>
>>>>> among multiple shortest-path trees.<BR>
>>>>><BR>
>>>>> @@@ That's all true but the special case of an Rbridge of order 1<BR>
>>>>> connected to an Rbridge of order >1 seems so simple to check for<BR>
>>>>> that you could just rule them out. Or, if "order" were<BR>
>>>>> <BR>
>> added to the<BR>
>> <BR>
>>>>> comparison tuple as above, in the default case where all Rbridges<BR>
>>>>> <BR>
>>>>> <BR>
>>> have<BR>
>>> <BR>
>>> <BR>
>>>>> the default priority, order 1 Rbridges would automatically have<BR>
>>>>> <BR>
>>>>> <BR>
>>> lowest<BR>
>>> <BR>
>>> <BR>
>>>>> priority. (See also slides 8 and 9 of my presentation at<BR>
>>>>> <A HREF="http://www.ietf.org/proceedings/07jul/slides/trill-3/sld1.htm">http://www.ietf.org/proceedings/07jul/slides/trill-3/sld1.htm</A>.)<BR>
>>>>><BR>
>>>>> This seems completely safe, and easier than configuring, for each<BR>
>>>>> RBridge, the set of root RBridges to choose for multicast<BR>
>>>>> <BR>
>> tree roots.<BR>
>> <BR>
>>>>> It also means that you can configure in one place a total<BR>
>>>>> <BR>
>> number of<BR>
>> <BR>
>>>>> roots, rather than possibly having too many RBridges<BR>
>>>>> <BR>
>> volunteer for<BR>
>> <BR>
>>>>> being tree roots, and winding up with too much overhead<BR>
>>>>> <BR>
>> on RBridges<BR>
>> <BR>
>>>>> because they'll have to compute a tree for every RBridge<BR>
>>>>> <BR>
>> that says<BR>
>> <BR>
>>>>> it will want to be a tree root.<BR>
>>>>><BR>
>>>>> There might be a concern about volatility -- when an RBridge with<BR>
>>>>> numerically low priority goes down, it might cause:<BR>
>>>>> a) a change to the total number of trees to be computed<BR>
>>>>> <BR>
>> by everyone<BR>
>> <BR>
>>>>> (since the next best might be configured with a different number)<BR>
>>>>> b) a change to the list of "tree roots I will choose" announced by<BR>
>>>>> <BR>
>>>>> <BR>
>>> RB2<BR>
>>> <BR>
>>> <BR>
>>>>> when one of the roots for the k best (cost to me,<BR>
>>>>> <BR>
>> priority, ID) goes<BR>
>> <BR>
>>>>> down.<BR>
>>>>><BR>
>>>>> @@@ There are plenty of other possible causes for<BR>
>>>>> <BR>
>> volatility. Like a<BR>
>> <BR>
>>>>> high priority-to-be-tree-root Rbridge coming up or an Rbridge's<BR>
>>>>> priority-to-be-tree-root being reconfigured. But the solution to<BR>
>>>>> them all is the same. An Rbridge has to keep calculating (or at<BR>
>>>>> least keep<BR>
>>>>> around) trees for old roots as long as their reasonably might be<BR>
>>>>> <BR>
>>>>> <BR>
>>> frames<BR>
>>> <BR>
>>> <BR>
>>>>> in transit specifying those roots. It has to calculate<BR>
>>>>> <BR>
>> trees for any<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> new<BR>
>>> <BR>
>>> <BR>
>>>>> roots right away and, if appropriate, start advertising that it<BR>
>>>>> might use them. What root (or from what set of roots) to<BR>
>>>>> <BR>
>> choose for<BR>
>> <BR>
>>>>> new<BR>
>>>>> <BR>
>>>>> <BR>
>>> native<BR>
>>> <BR>
>>> <BR>
>>>>> multi-destination frames an Rbridge is encapsulating is a bit<BR>
>>>>> <BR>
>>>>> <BR>
>>> messier.<BR>
>>> <BR>
>>> <BR>
>>>>> Seems to me that until it is reasonably sure that information has<BR>
>>>>> propagated concerning new roots, it should only use those in the<BR>
>>>>> intersection of the sets of old and new roots. If that<BR>
>>>>> <BR>
>> intersection<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> is<BR>
>>> <BR>
>>> <BR>
>>>>> null, something only likely to occur when there are a very small<BR>
>>>>> <BR>
>>>>> <BR>
>>> number<BR>
>>> <BR>
>>> <BR>
>>>>> of tree roots, you have a bit of a problem and might as<BR>
>>>>> <BR>
>> well use the<BR>
>> <BR>
>>>>> <BR>
>>>>> <BR>
>>> new<BR>
>>> <BR>
>>> <BR>
>>>>> root(s). But this is no worse than under the previous scheme if<BR>
>>>>> RequestTree was FALSE for all Rbridges and the Rbridge with the<BR>
>>>>> <BR>
>>>>> <BR>
>>> lowest<BR>
>>> <BR>
>>> <BR>
>>>>> system ID, which had defaulted to being the only tree root, goes<BR>
>>>>> <BR>
>>>>> <BR>
>>> down.<BR>
>>> <BR>
>>> <BR>
>>>>> Other than that, I can't think of any possible problems.<BR>
>>>>><BR>
>>>>> @@@ Overall, I like the proposal.<BR>
>>>>><BR>
>>>>> Radia<BR>
>>>>><BR>
>>>>> @@@ Thanks,<BR>
>>>>> @@@ Donald<BR>
>>>>><BR>
>>>>> _______________________________________________<BR>
>>>>> rbridge mailing list<BR>
>>>>> rbridge@postel.org<BR>
>>>>> <A HREF="http://mailman.postel.org/mailman/listinfo/rbridge">http://mailman.postel.org/mailman/listinfo/rbridge</A><BR>
>>>>> <BR>
>>>>> <BR>
>>>>> <BR>
>>>>> <BR>
>>>> _______________________________________________<BR>
>>>> rbridge mailing list<BR>
>>>> rbridge@postel.org<BR>
>>>> <A HREF="http://mailman.postel.org/mailman/listinfo/rbridge">http://mailman.postel.org/mailman/listinfo/rbridge</A><BR>
>>>><BR>
>>>> <BR>
>>>> <BR>
>>>> <BR>
>>> <BR>
>>> <BR>
>> --<BR>
>> We make our world significant by the courage of our questions and by<BR>
>> the depth of our answers. - Carl Sagan<BR>
>><BR>
>> _______________________________________________<BR>
>> rbridge mailing list<BR>
>> rbridge@postel.org<BR>
>> <A HREF="http://mailman.postel.org/mailman/listinfo/rbridge">http://mailman.postel.org/mailman/listinfo/rbridge</A><BR>
>><BR>
>> <BR>
<BR>
_______________________________________________<BR>
rbridge mailing list<BR>
rbridge@postel.org<BR>
<A HREF="http://mailman.postel.org/mailman/listinfo/rbridge">http://mailman.postel.org/mailman/listinfo/rbridge</A><BR>
<BR>
</FONT>
</P>
</BODY>
</HTML>