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

[Dinesh G Dutt]

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