Subject: [rbridge] Compromise proposal---allowing tradeoff between computation and optimality of delivery

From: sanjays at cisco.com (Sanjay Sane (sanjays))
Date: Wed, 1 Nov 2006 11:22:49 -0800

This proposal sounds good to me, with one exception. 

If we don't expect the number of trees to be equal to the number of
rbridges, why have the tree identifier from the same number-space as of
rbridge-nickname ? 

Rbridge nickname space is 16 bits = 64K combinations. Its not practical
to scale to these many "trees". If the "tree-identifier" space is
different (say 10 bits - max 1k combinations) than the rbridge nickname
space, hardware resources can be optimized. 

To optimize the fields in the shim header, its ok to carry this
tree-identifier in the egress rbridge id field (as per your latest SHIM
header proposal). 

Yes, this would mean another "dynamic assignment" process to assign the
"tree-identifier". Whichever rbridge is configured/chosen to become the
root of a tree, first participates in the "dynamic assignment" process,
gets itself assigned a "tree-identifier", and then informs the other
RBridges with some information in its link state packet - indicating 2
things
1. flag suggesting it wants to be a root of a tree 
2. "tree-identifier" to be used for the tree computed with itself as the
root. 

-Sanjay

-----Original Message-----
From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org] On
Behalf Of Radia Perlman
Sent: Wednesday, November 01, 2006 10:43 AM
To: rbridge at postel.org
Subject: [rbridge] Compromise proposal---allowing tradeoff between
computation and optimality of delivery

There is understandable nervousness about the need to compute
per-ingress trees for every RBridge, and optimality of delivery.
I actually was dubious about whether people *really* wanted to have to
compute per-ingress trees.

Here's a proposal that will allow tradeoff between overhead of
computation and optimality of delivery. If people really want they can
have RBridges compute trees rooted at every RBridge. Or they can have
all multicast delivered on a single shared tree. Or anything in between.
I'm arbitrarily picking the zero configuration option being a single
tree.

The new shim format allows the ingress RBridge to specify the
distribution tree for multicast, by putting into the "egress RBridge"
field a tree rooted at at the specified RBridge.

In this proposal, by default, the only tree that will be computed is a
single shared tree rooted at the RBridge with smallest MAC address.
Let's say that RBridge has nickname "71". By specifying 71 as egress
RBridge in a multicast packet, the delivery path will be via the
bidirectional tree rooted at 71.

An RBridge can be configured to demand that it, too, be the root of a
tree, and it informs the other RBridges with a flag in its link state
packet.

So now we have a subset of RBridges that can be used as roots of trees,
because they have specified that in their link state packet.
Let's say that RBridges with nicknames 11, 15, 71, 222, and 259 all have
announced that they want to be roots of trees.

Then an ingress RBridge, say R2, with nickname 11, can send a
multicast/unknown destination packet with "ingress"=11 (its own) and
"egress"=11 (because it said it wanted to be a root). Or it could choose
any of the other potential ones (15, 71, 222, 259).

Likewise, an ingress RBridge, say R3, with nickname 13, who has not
requested to be the root of a tree, can specify only the trees 11, 15,
71, 222, 259. Note it cannot specify "13", since we are assuming it has
not requested that all RBridges calculate a tree rooted at itself.

If no RBridges are configured to say they want to be the root, then only
a single tree will get computed---the one rooted at 71.

So the zero configuration option is a single shared tree (still filtered
based on IP multicast announcements and VLANs) rooted at the RBridge
with smallest MAC address. But by configuration, more and more
optimality can be introduced by having RBridges compute more trees.

Radia

_______________________________________________
rbridge mailing list
rbridge at postel.org
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: Radia.Perlman at sun.com (Radia Perlman)
Date: Wed, 01 Nov 2006 12:05:23 -0800

If the header already has "ingress" and "egress" RBridge nicknames for 
unicast, then there
doesn't seem to be a reason to try to have a different nickname to 
identify the tree.
Using the already computed nickname seems simplest.

As for Ayan's questions:
a) can we assume that the list of trees is ordered and consistent:

Yes---that's the idea. The tree is specified by who is the root, and 
there needs to be deterministic
tie breakers so all RBridges calculate the same tree.

b) is it possible to have a TLV that indicates how many trees an RBridge 
is willing to compute

That seems like a good idea, though there needs to be some reasonable 
default so that RBridges
work reasonably well with zero configuration. Should the default be 1 
tree? Or 100?

So to make your proposal clear---each RBridge announces in its link 
state packet "I can support
n trees". The number of trees allowed would be the smallest n announced 
by any RBridge. If
more than n RBridges ask to be roots of trees, then the n RBridges with 
smallest MAC addresses
are roots.

There are other alternatives, similar to the "overloaded" flag. An 
RBridge that can't support
as many trees as requested could set a "overloaded with multicast trees" 
flag, and then
other RBridges could compute trees avoiding that guy. But this seems 
more complicated than
just doing what you suggest.

Radia