Subject: [rbridge] Query on selection of Ingress DTree

From: somnath chatterjee <[email-masked]>
Date: Wed, 14 Dec 2011 10:04:43 +0530

Hi Authors,

As per rfc6325
"How an ingress RBridge chooses the distribution tree or trees that it
uses for multi-destination frames is beyond the scope of this
document.  However, for the reasons stated above, in the absence of
other factors, a good choice is the tree whose root is least cost from
the ingress RBridge and that is the default for an ingress RBridge
that uses a single tree to distribute multi-destination frames.
"
Say for a topology diagram below

RB1 is connected to RB2
RB2 is connected to RB1,RB4 and RB3
RB3 is connected to RB2 and RB5
RB4 is connected to RB2,RB5 and ES1(End Station)

RB1--------RB2--------RB3
                |              |
              RB4--------RB5
                |
             ES1

where End-Station1(ES1) is interested in Multicast Group MG1
two Distribution Trees(DTree) are calculated

DTree1 Rooted at RB1
RB1--------RB2--------RB3--------RB5-------RB4

and

DTree2 Rooted at RB2
RB1--------RB2--------RB3
                |
              RB4--------RB5

If RB1 receives a multicast traffic from a directly connected end-host
for Group MG1 for which the only subscriber is ES1, Ingress RBridge
RB1's best choice is to forward the traffic in DTree2 rather than
DTree1(which is closer to RB1) assuming the Distribution Trees are
multicast pruned.If multiple Dtrees are calculated in a campus and
Ingress Rbridge has to choose a distribution tree, it is not always
best option for the ingress RBridge to choose the closest rooted
Distribution Tree.

If we keep track of the following we can populate a table which when
supplied with Vlan and Group would give us the best DTree to ingress
on.

1>Cost to reach each DTree Root
2>Cost to reach from DTree Root to farthest interested host for each
multicast group

Moreover we can set the Hop-Count for these TRILL encapsulated
multicast packets to sum of cost of 1> and 2>

Is this a feasible way to select the Ingress DTree? Please let me know
your valuable comments.

Thank you,
Regards,
Somnath
_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: Radia Perlman <[email-masked]>
Date: Tue, 13 Dec 2011 22:36:11 -0800

Yeah.  The spec allows an RBridge to choose any strategy for choosing which
tree.  If one looks at a particular criterion, such as number of packet
hops to deliver the packet to all the interested participants (which seems
like a reasonable criteria for what would be a good tree), then some trees
could be significantly better than others, regardless of how close the Root
is to the ingress RBridge.  Your suggestion seems like a good suggestion.

I think it would make a nice research project and paper for someone to
study things like
a) given an engineered topology, where is the best place to put Roots
b) given a "random" topology, having some algorithm whereby the highest
priority RBridge can calculate, based on the LSP database, for instance,
where the best place to locate Roots
c) how an edge RBridge should decide which tree to ingress on.

Luckily it doesn't affect the TRILL protocol...it just would allow
implementations to make choices.

Radia

---

From: Yizhou Li <[email-masked]>
Date: Wed, 14 Dec 2011 17:31:26 +0800

I also think it is a good idea. In fat tree structure, it is very likely
that we put the tree roots at aggregation nodes. In this case, it is always
equal cost to every tree root for every access node. We need a better way to
decide the tree root to be chosen.

In addition, it would be good if we could achieve more balanced load sharing
for multi-destination frame. Currently it is highly based on tree root
selection which is highly unpredictable. 

Yizhou   

From: [email-masked] [mailto:[email-masked]] On
Behalf Of Radia Perlman
Sent: Wednesday, December 14, 2011 2:36 PM
To: somnath chatterjee
Cc: [email-masked]
Subject: Re: [rbridge] Query on selection of Ingress DTree

Yeah.  The spec allows an RBridge to choose any strategy for choosing which
tree.  If one looks at a particular criterion, such as number of packet hops
to deliver the packet to all the interested participants (which seems like a
reasonable criteria for what would be a good tree), then some trees could be
significantly better than others, regardless of how close the Root is to the
ingress RBridge.  Your suggestion seems like a good suggestion.

I think it would make a nice research project and paper for someone to study
things like

Radia

On Tue, Dec 13, 2011 at 8:34 PM, somnath chatterjee
<[email-masked]> wrote:

Hi Authors,

As per rfc6325

RB1 is connected to RB2

DTree1 Rooted at RB1

and

DTree2 Rooted at RB2

Thank you,
Regards,
Somnath

---

From: Donald Eastlake <[email-masked]>
Date: Wed, 14 Dec 2011 15:23:33 -0500

Hi Yizhou,

> decide the tree root to be chosen.

If you have multiple trees that seem equally good, I assume you could
spread multi-destination traffic across them with the same sort of
hash function used to spread different flows over ECMP paths.

> selection which is highly unpredictable.

I think that how to select which distribution tree to use for a frame,
like how to choose which RBridge on a link to make the Appointed
Forwarder for a VLAN, was intended to be an area where different
implementations could do it in different ways.

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

> Yeah.  The spec allows an RBridge to choose any strategy for ch! oosing wh
> oks at a particular criterion, such as number of packet hops to deliver the
> packet to all the interested participants (which seems like a reasonable
> criteria for what would be a good tree), then some trees could be
> c) how an edge RBridge should decide which tree to! ingress div>
>
>
>
> that uses a single tree to distribute multi-destination f! rames.
>
>
> RB1 is connected to RB2
> for Group MG1 for whic! h the onl ess RBridge
>
> __________________________________________! _____
> a href="mailto:[email-masked]">[email-masked]

---

From: "Tissa Senevirathne (tsenevir)" <[email-masked]>
Date: Wed, 14 Dec 2011 13:15:05 -0800

Comments in-line

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Donald Eastlake
Sent: Wednesday, December 14, 2011 12:24 PM
To: Yizhou Li
Cc: [email-masked]; somnath chatterjee; Radia Perlman
Subject: Re: [rbridge] Query on selection of Ingress DTree

Hi Yizhou,

[Tissa] Tree selection has to be simple and only an ingress function. I agree with Donald using the same method as unicast ECMP to select multicast trees at the ingress provide most effective. Not sure of added benefit of having any other complicated tree selection algorithms. Only restriction should be, mapping of multicast traffic of a given flow to the same tree at any given ingress RBRidge. 

Thanks,
Donald