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

[Eastlake III Donald-LDE008]

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