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

[Silvano Gai]

I agree with Dinesh, we are discussing the default.
One should be the default, you can config as high as you like

-- Silvano

> -----Original Message-----
> From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org]
On
> Behalf Of Dinesh G Dutt
> Sent: Monday, April 07, 2008 8:04 AM
> To: Eastlake III Donald-LDE008
> Cc: Developing a hybrid router/bridge.
> Subject: Re: [rbridge] (slight) modification of how to choose
mulitcast
> trees
> 
> Donald,
> 
> We're talking about defaults here, not what is the maximum. I hear
your
> arguments but 8 is too much for smaller networks. I know of one large
> customer who's thinking of 16, but most prefer 2-4.
> 
> Dinesh
> Eastlake III Donald-LDE008 wrote:
> > 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
> >
> >
> 
> --
> We make our world significant by the courage of our questions and by
> the depth of our answers.                               - Carl Sagan
> 
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge