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

From: Radia Perlman <[email-masked]>
Date: Fri, 28 Mar 2008 19:55:24 -0700

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 s also configured with a parameter indicating "total 
number of trees in the campus", which R1 announces in its LSP

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.

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.

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.

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.

Other than that, I can't think of any possible problems.

Radia

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

---

From: "Eastlake III Donald-LDE008" <[email-masked]>
Date: Sun, 30 Mar 2008 13:24:55 -0400

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: [email-masked] [mailto:[email-masked]] 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

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.)

@@@ 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...).

@@@ Of course the ranking has to be the same so if "order" were added as
above, it would have to be added here also.

@@@ 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.)

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.

@@@ Overall, I like the proposal.

Radia

@@@ Thanks,
@@@ Donald

---

From: Radia Perlman <[email-masked]>
Date: Sun, 30 Mar 2008 11:00:03 -0700

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

---

From: "Eastlake III Donald-LDE008" <[email-masked]>
Date: Sun, 30 Mar 2008 14:31:18 -0400

Hi Radia, 

See below at ###

-----Original Message-----
From: Radia Perlman [mailto:[email-masked]] 
Sent: Sunday, March 30, 2008 2:00 PM
To: Eastlake III Donald-LDE008
Cc: Developing a hybrid router/bridge.
Subject: Re: [rbridge] (slight) modification of how to choose mulitcast
trees

### It's obviously simpler to use a fixed default but I don't see what's
so hard about a computed default. To be really specific, you do
something like pick a distinguished value, say zero, and if the highest
priority Rbridge is advertising that zero trees should be computed then
each Rbridge just counts the number of Rbridges in sees its link state
database and takes the specified function of that number (square root in
my suggestion) and computes that many trees. Or, alternatively, only the
highest priority Rbridge does this calculation and promulgates the
results.

### No problem... That's why I said Rbridge adjacencies. As long as
there is anything that can change, you have all the problems of
volatility so you have to be able to handle transitions. Currently
pseudonodes can't be tree roots so there are a number of adjustments to
make if we change that.

### Well, the LID option assumes you can't have more than about 64K
ports :-) so you could just use two bytes for order and could invert all
the bits in those bytes to get the right ordering of the multiprecision
priority quantity.

priority is configured, you'd leave it at whatever it is configured to
be.

### Yes, you could do something like that. I would think you'd like
RBridges to do a good job of selecting tree roots in relatively small
unconfigured campuses which is mostly what this "order" think is about.
In large heavily configured campuses, I would think that normally none
of these tie breakers would make any difference. You would configure all
your Rbridges to say you wanted N1 roots and would configure exactly N1
Rbridges with highest priority and some number N2 of your Rbridges as
back-ups probably with priorities from (highest - 1) through (highest -
N2). Or maybe you would have configured N1+N2 Rbridges with priority
from 0 through N1+N2-1 or whatever... In these cases, only under rare
circumstances where a couple of Rbridges tied due to unintended
configuration would the tie breakers have any effect.

Radia

### Thanks,
### Donald