Subject: Re: [rbridge] Queries on RFC 6325

From: Donald Eastlake <[email-masked]>
Date: Thu, 1 Dec 2011 10:14:15 -0500

Hi Rakesh,

On Thu, Nov 17, 2011 at 2:45 AM, rakesh kumar <[email-masked]> wrote:
> Hi Donald,
>
>             I am still not clear why "with the remainder (upto the
> maximum of {j,k})" is considered. As for all the values of j,j<k,
> maximum{j,k} will default to k implies ingress set of tress will
> default k trees specified by root.

The contingencies are complex enough that it is hard to cover them all
in a natural language like English. Assume there are TN total number
of nicknames with priority greater than zero to be a tree root. And
that the minimum of the number of distribution trees supported by any
RBridge in the campus is DT. Then the number of tree computed, denoted
k, will be maximum( minimum( TN, DT), 1).

A total ordering to be a tree root is imposed on all nicknames which
defaults to the nicknames ordered by their priority to be a tree root
with ties broken by SystemID and ties in both priority and SystemID
broken by the nickname value, all treated as unsigned and with
arithmetically larger values being higher priority. The RBridge
holding the nickname that is highest priority to be tree root can list
nicknames to be put first in this total ordering. To the extent that
it lists existing nicknames those nicknames are treated as if they
were highest priority in the order listed by the RBridge that is
highest priority tree root. This might leave the total ordering of
nicknames to be tree root unchanged or just move a few nicknames up
front or it might totally re-order the list.

OK, so at this point we have the final total ordering of nicknames and
we know k, the number of trees every RBridge has to compute so it can
handle multi-destinaiton frames with the nicknames for those trees in
the egress nickname TRILL Header field. (So we now also know the tree
number of each of the k trees since they are numbered from 1 to k in
the list order.) But, to save RPFC space, an RBridge can announce how
many trees it wants to use, called j, and may specify those trees. j
is just a value in an LSP field so it can be anything. For example, if
k is 3, an RBridge could announce its j as 100. The actual number of
trees an RBridge will use, which we will call j-actual, is maximum(
minimum( j, k), 1). If an RBridge does not list any specific nicknames
that it wants to use, then the first j-actual trees from the totally
ordered list are the trees that it can use. To the extent that the
RBridge lists specific trees that it wants to use and those trees are
in the first k trees in the totally ordered list, it uses those, and
the remainder, up to j-actual, if any, are taken from the first
appearing in the totally ordered list that the RBridge has not already
specified.

> To make it more clear suppose  RB2,not the highest priority rbridge,
> has specified j=2 and D3,D4 are explicitly "specified ingress tree
> nicknames" .RB1, highest priority RBridge,has specified K=5 and
> D1,D2,D3,D4,D5 as campus wide trees to be calculated by all the
> rbridges in the campus.
>
> RB3 has to identify potential ingress trees of RB2,ingress trees are
> trees which are explicitly specified by RB2 i.e. is D3,D4 and
> remainder are implicit ingress trees upto 5 (as 5 is maximum
> {j=2,k=5}) are taken from k-campus wide trees which are
> D1,D2,D5.Thus,potential ingress trees of RB2 are D3,D4,D1,D2,D5 which
> are not different from set of trees specified by root
> D1,D2,D3,D4,D5,which wont honor j list specified by RB2.

So, based on my text above, I now think you are right and the
specification is wrong. To the first approximation, the maximum (j, k)
should be a minimum (j, k) although, when you take into account all
the contingencies, it is more complex than that.

> And i feel "with the remainder (upto the minimum of {j,k})" will honor
> j list specifed by RB2 and fetch ingress tress as subset of K trees
> for the j value less than k.

I think that, in fact, very few people are using these somewhat
complex tree selection mechanisms although they were added to the
specification due to significant demand at the time.

Unless someone can point out where I am confused above, I'll add some
material to draft-eastlake-trill-rbridge-clear-correct to fix this.

Thanks,
Donald
=============================
 Donald E. Eastlake 3rd   +1-508-333-2270 (cell)
 155 Beaver Street, Milford, MA 01757 USA
 [email-masked]

> Regards,
> Rakesh

_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: [email-masked]
Date: Sat, 3 Dec 2011 15:02:47 +0800

Hi Donald,

> If an RBridge does not list any specific nicknames that it wants to use, 

> then the first j-actual trees from the totally ordered list are the 
trees 
> that it can use. To the extent that the RBridge lists specific trees 
that 
> it wants to use and those trees are in the first k trees in the totally 
> ordered list, it uses those, and the remainder, up to j-actual, if any, 
> are taken from the first appearing in the totally ordered list that the 
> RBridge has not already specified.

I think your meaning is that RBx will use the first j-actual trees in the 
totally ordered list to forward multi-destination frames, if it does not 
specify any trees it wants to use or all the specified trees are not in 
the k trees list. 

If RBx doesn't specify any trees, it is OK to assume that RBx will use the 

first j-actual trees. However, it is not suitable to assume that RBx will 
use the first j-actual trees, if RBx specifies some wanted trees (even if 
all the trees specified by RBx are not in the k trees list).

Before finishing the link database synchronization, none RBridge knows 
exactly which trees will be actually calculated in TRILL campus, but it 
has to announce the number and the nicknames of the trees it wants to 
use, which is the base for TRILL campus to elect the k actually-calculated 

trees. So, for such an RBridge, the simple way is to specify itself as the 

roots of trees it wants to use before it knows exactly which trees can be 
actually calculated. Unfortunately, during the link database 
synchronization, 
it is a prevalent way for RBridges to specify their wanted trees.

So it is RECOMMENDED that one RBridge should re-choose its wanted trees 
from 
the k trees list and update its LSP, if it finds some of its specified 
trees 
are not actually calcualted. I think it is the best way to fix this issue, 

because it gives the RBridge an opportunity to choose the optimal trees 
for it. 
Furthermore, it is RECOMMENDED that one RBrdige should specify at least 
one 
nickname for the trees it wants to use, which can avoid most RBridges to 
focus their multi-detonation traffic on the first appearing trees in the 
totally ordered list.

Then if an RBridge doesn't specify enough nicknames for j-actual trees 
(including 
specify none nicknames), the remainder trees will be taken by the way as 
you 
suggested.

Thanks,
Zhai Hongjun
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
 Protocol Development Dept.VI, Central R&D Institute, ZTE Corporation
 No. 68, Zijinghua Road, Yuhuatai District, Nanjing, P.R.China, 210012
 
 Zhai Hongjun
 
 Tel: +86-25-52877345
 Email: [email-masked]
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""

Donald Eastlake <[email-masked]> 
发件人:  [email-masked]
2011-12-01 23:14

收件人
rakesh kumar <[email-masked]>
抄送
[email-masked]
主题
Re: [rbridge] Queries on RFC 6325

Hi Rakesh,

Thanks,
Donald

--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail is solely property of the sender's organization. This mail communication is confidential. Recipients named above are obligated to maintain secrecy and are not permitted to disclose the contents of this communication to others.
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the originator of the message. Any views expressed in this message are those of the individual sender.
This message has been scanned for viruses and Spam by ZTE Anti-Spam system.
_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: Donald Eastlake <[email-masked]>
Date: Wed, 7 Dec 2011 16:49:14 -0500

Hi Hongjun,

2011/12/3 <[email-masked]>
> > then the first j-actual trees from the totally ordered list are the trees
> > that it can use. To the extent that the RBridge lists specific trees that

Yes, that is what I meant.

> all the trees specified by RBx are not in the k trees list).

I don't see why not. RBx is limited to, at most, the first j-actual
tree that all RBridges in the campus are calculating... (see below)

> Before finishing the link database synchronization, no RBridge knows

(Actually, the highest priority RBridge to be a tree root is in charge
of what trees a calculated. What other RBridges announce as the number
of trees that want to use and what those desired trees are has no
effect on what trees every RBridge has to calculate.)

> actually calculated. Unfortunately, during the link database synchronization,

In link state routing, it is generally meaningless to speak of
"finishing the link database synchronization". You can never tell
whether some RBridge has just been added to or deleted or reconfigured
in some remote part of the campus (or some link has changed state). As
far as an particular RBridge knows, the link state database could
always be in the process of changing.

I don't really see the point of an RBridge just specifying its own
nickname (or one of them if it has more) as a tree it wants to use if
that isn't the intended stable state. While there are all kinds of
complicated things you can do with the various tree choosing
mechanisms, I would imagine that, in many cases, people would choose
one of two simple strategies:

(1) If you are only going to have a small number of trees, say 2 or 3,
you might just configure several particularly well connected RBridges
to be higher priority to be tree root and not bother to configure
anything else (other than configuring every RBridge to to say it wants
to use N trees and can compute N trees, where N is the number of trees
you want for the campus).

(2) If you are trying to optimize with lots of trees and want to
configure, you would have configured all the nicknames of all the
RBridges. You would have used the priority and specification of roots
mechanism so that the highest priority tree root RBridge would have
caused the trees you want to be computed in the campus (with adequate
provision so that what you want happens for limited failures). Under
such circumstances, I think you would know what trees you want each
RBridge to use and you might as well configure them to just list those
tree. True, if the whole network is just starting up, it may go
through some odd tree states, but it should get through them pretty
quickly and I don't see how it helps anything for an RBridge to just
list itself at the start.

> So it is RECOMMENDED that one RBridge should re-choose its wanted trees from
> the k trees list and update its LSP, if it finds some of its specified trees
> because it gives the RBridge an opportunity to choose the optimal trees for it.

An RBridge can re-choose its wanted trees whenever it wants but
dynamically determining which trees you want seems at least a little
fancy. Other than recommending that an ingress RBridge use tree whose
roots are fairly close to that ingress RBridge, I don't think we need
to say anything else. This seems like an excellent area for
implementors to exercise their ingenuity.

> Furthermore, it is RECOMMENDED that one RBrdige should specify at least one

Listing the trees you say you want to use is just to optimize the
reverse path forwarding check. While it limits the trees you can
choose, it has no other effect on what tree you actually choose for a
particular frame.
     Say there are 5 trees being calculated. If you are going to use
all 5, there is no reason to specify any of them. The ingress RBridge
is always free to use any tree that the other RBridges in the campus
can figure out it might use, so the RPFC will work. So, as I say, if
there are 5 tree, every ingress RBridge could use the tree whose root
is closest to it, which might or might not divide traffic evenly
depending on the location of the roots. Or each RBridge could
calculate a hash of the native frame destination MAC, source MAC, and
VLAN (and perhaps more fields) and use the remainder of that hash for
a frame divided by 5 to choose the tree to use for each such
multi-destination frame. Or it could pick one of the 5 trees for each
flow in some other way. It is certainly not required to use the tree
appearing first in the totally ordered list.

> Then if an RBridge doesn't specify enough nicknames for j-actual trees (including
> specify none nicknames), the remainder trees will be taken by the way as you
> suggested.

OK.

Thanks,
Donald