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

[Eastlake III Donald-LDE008]

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