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

[Silvano Gai]

8 is too much,
I will prefer 1, I can accept 2.

-- Silvano

> -----Original Message-----
> From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org]
On
> Behalf Of Eastlake III Donald-LDE008
> Sent: Sunday, April 06, 2008 8:49 PM
> To: Developing a hybrid router/bridge.
> Subject: Re: [rbridge] (slight) modification of how to choose
mulitcast
> trees
> 
> Hi,
> 
> On "Why 8", or really why >1, as the recommended default number of
> distribution trees, my answer is as follows:
> 
> Having more than one distribution tree has a bunch of benefits.
> +   It probabilistically reduces the concentration of
multi-destination
> traffic onto particular links and increases the aggregate capacity for
> them in much the same way that using IS-IS does in comparison with
> spanning tree.
> +   By choosing a tree rooted nearby when you are encapsulating an
> unknown unicast frame, you reduce the probability of mis-ordering
frames
> when the address become known. (In the limit, if you root a tree for
> every node, the probability of mis-ordering becomes very small.)
> +   Finally, unless you do a tree for every node, there are things
that
> can happen which will change the set of tree calculated. This can
> include nodes going down, coming up, having their priority or
> RequestTree flag or whatever you are using reconfigured, etc. If you
> have only one tree, you are guaranteed that when that one tree changes
> all multi-destination frames in flight now refer to a tree that is no
> longer supposed to be computed and all newly encapsulated frames need
to
> refer to a new frame which may not yet have been calculated. Most
> methods of automatically choosing which nodes to use as tree roots are
> designed to be reasonably stable so the probability is low that the
> entire set of tree would change even if that set has only a few
members.
> In fact, if you are calculating k trees, most commonly only 1 would
lose
> its must-be-calculated status and k-1 would remain. Thus it is more
> likely that, after a change in the tree set, frames in flight still
> refer to trees that are being calculated. And it would be a reasonable
> strategy to, for a short time, use trees in the intersection of the
old
> and new sets when frames are newly encapsulated so as to make it
highly
> probably that nodes forwarding such frames will already have computed
a
> tree for the root specified.
> 
> The more tree the better, according to the above factors. So what's
the
> disadvantage of having many distribution trees? There is no effect on
> the size of the link state database or volume of routing information.
> It's really just a local computational cost. Assuming building a tree
> with n nodes and L pair wise links, the effort is proportional to L +
> n*(log n). Thus building one for every node would be n*(L + n*(log n))
> or n*L + (n**2)*(log n) effort. This is certainly a bit daunting for
> large n. So we seem to be looking for some k, the recommended default
> number of trees, such that k*(L + n*(log n)) is tolerable. Actually,
in
> order to perform unicast forwarding, each node needs to, in effect,
> compute a tree rooted on itself. So it has to do n*(log n) even if
there
> are zero multi-destination trees. So we are looking for a recommended
> default number of trees k such that (k+1)*(L + n*(log n)) is
tolerable.
> (These are all approximations.)
> 
> Numbers that have been suggested for k are 1, 2, 4, 8, and 10. I don't
> think that we have the data or the scoring criteria to calculate an
> optimal value. I think TRILL should be aiming several years out when
> Moore's law will have had further effect. People in the ISIS working
> group keep saying that Dijkstra calculations are cheap can be done
> quickly. Even with only one distribution tree, you still have to
> actually calculate two trees because you need, in effect, a self
rooted
> one for unicast. While I certainly don't want to make the argument
that
> if you can do N, you should be able to do N+1, and thus by induction
> could do an unbounded number, still, it seems to me that if you have
to
> calculate at least 2 tree, making the recommended default 2 or 4
(i.e.,
> so you end up calculating 3 or 5 distribution trees) just shouldn't be
> that hard and yields considerable benefits in multi-destination
traffic
> capacity, reduced mis-ordering, and increased stability due to trees
> that remain valid across typical changes in the set of distribution
> trees to calculate. I still think 8 is reasonable and I don't see why
> you would set k to 1 unless you wanted to restrict the default campus
> performance for multi-destination traffic to be no better than that of
> bridges with a single spanning tree.
> 
> Thanks,
> Donald
> 
> -----Original Message-----
> From: Dinesh G Dutt [mailto:ddutt at cisco.com]
> Sent: Wednesday, April 02, 2008 12:33 AM
> To: Eastlake III Donald-LDE008
> Cc: Radia Perlman; Developing a hybrid router/bridge.
> 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
> 
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge