Subject: [rbridge] Existing issues in root bridge selection for LANs.

From: greg.daley at eng.monash.edu.au (Greg Daley)
Date: Tue, 03 May 2005 12:32:56 +1000

Hi,

Here's the idea I was thinking about a while ago, which
looks applicable to rbridge.  More work needs to be done,
to ensure that the mean path cost is always lower, but
I'd guess it's a fairly good bet to never be worse if
most of the traffic exists the LAN.

Most edge LANs today have the bulk of the hosts' traffic
leaving the LAN through at most one or two ports.
The traffic in many cases is sourced or sunk from devices
in the LAN (it is essentially a stub LAN), and the data
travells to the Internet, or to off-link servers, through
IP routers.

Unmodified Spanning Tree algorithm as implemented in
ethernet switches today will produce a spanning tree,
which is not guaranteed to be one which is anchored
near to the IP routers.

This is because the bridge priority of switches is
typically provided with a default higher order (2) octets of
the Bridge Identifier with a value of 32768.

This means that all switches have the same default
priority, and MAC addresses (as provided in the
lower order bits of the switch's BridgeID),
will be used to break ties between switches.

Therefore unless a manual priority configuration is
provided, MAC switch vendors with the lowest IEEE OUI
will win.  When the same IEEE OUI is part of the
bridge Identifier of all participating switches,
the oldest switch (with the lowest sequence within
the OUI) will always be elected as root bridge.

The default settings for the path cost in spanning tree
protocol are symmetric for all systems.  This is regardless
of the importance or topological placement of a particular switch.

Other dynamic systems which automatically configure STP bridge
priorities may be useful (such as distance from routers). By
preferring to choose switches closer to egress IP routers,
lower mean path costs would be achieved for devices communicating
through the router, which is a common technique in Internet
connected systems.

As an example, there's a tight mesh of switches on a LAN:

All links are 100mbps, with switches indexed A-L, and
a router R connected through two links to H and L
and queueing delay is negligible.

A---B---C---D
   \   \   \   \
    E---F---G---H--R
     \   \   \   \/
      I---J---K---L

Since A has the lowset MAC address, and all link costs
are equal, that means that all costs are calculated
with reference to the distance from those nodes connected
to A.

If we choose the links AB, AE, nodes B and E are connected
to the tree node set [A] with cost c.

EI, EF, BC are then connected to the tree nodes [A,B,E],
with cost c.

The tree-node set is now [A,B,E,I,F,C]. The nearest adjacent
links are: IJ, FJ, FG, CG, CD.  Spanning tree protocol
will deterministically choose one of each (tie break being the
mac address).  The links FJ, CG and CD are added to the
link set, and the tree-node set is [AB, AE, EI, EF, BC, FJ, CG, CD].

Adding H and K to the set follows the same pattern.
In this case, there are equal cost links, with the links
GK, DH having the lowest origin MAC address.

Subsequently the link HL is added to the spanning tree set.
the Links HR and LR are kept open since the switches H and L
are designated bridges for that LAN segment.

The MST based on A is therefore:

AB, AE, EI, EF, BC, FJ, CG, CD, GK, DH, HL.

A---B---C---D
   \   \   \   \
    E-X-F-X-G-X-H--R
     \   \   \   \/
      I-X-J-X-K-X-L

In this case, if traffic for the router is evenly
distributed amongst the switches (My guess is that
it won't, but this will do for now), the mean
distance travelled by packets is proportional to:

Sum k=A to L ( mst_A_cost_distance(k,R) )/ 12

Since we have a uniform set of links.

==> Sum k=A to L (c * mst_A_hops(k,R)) /12

==> c * Sum ..( mst_A_hops(k,R)).
==> c * ( 5 + 4 + 3 + 2 + 6 + 5 + 4 + 1 + 7 + 6 + 5 + 1) /12
Router mean cost MST c * 49/12 == 4.083
Router worst cost (A) = 7

If instead we built the root spanning tree from either of the
switches on connected links from R, we would gain the following
MSTs, and costs:

A---B---C---D
   \   \   \   \
    E---F---G---H--R
     \   \   \   \/
      I---J---K---L

Based on H:

HD, HG, HL, GK, DC, GF, CB,  FE, FJ, EI, BA.

A---B---C---D
   X   X   X   \
    E---F---G---H--R
     \   \   \   \/
      I-X-J-X-K-X-L

Router Mean cost (H) =
c*(5 + 4 + 3 + 2 + 4 + 3 + 2 + 1 + 5 + 4 + 3 + 2)/12

Router Mean cost (H) = c * 3.16
Router Worst cost (H) = 5

A---B---C---D
   \   \   \   \
    E---F---G---H--R
     \   \   \   \/
      I---J---K---L

Based on L:

A---B---C---D
   X   X   X   \
    E---F---G---H--R
     X   X   X   \/
      I---J---K---L

LH, LK, KJ, HG, HD, DC, GF, JI, CB, FE, BA

== c*(6 + 5 + 4 + 3 + 5 + 4 + 3 + 2 + 4 + 3 + 2 + 1)/12

Router Mean cost (L)= c* 3.5
Router Worst cost (L) = c * 6

As you can see, lower mean path costs are achieved in
this example, when choosing a root anchored close
to the router.

Actual costs are dependent, in this case, on MAC
address placement. Investigation would have to be undertaken
to determine how significant the tie-breaking measures
are..

As an idea though, if a heuristic solution exists which allows
routers to modify their root-bridge preference if they are
adjacent to an IP Router, this would allow selection
of MST-Roots which provide better mean and worst router
trip costs.

Greg

---

From: erik.nordmark at sun.com (Erik Nordmark)
Date: Tue, 03 May 2005 10:00:12 -0700

> most of the traffic exists the LAN.

Given that TRILL will use a use a link-state routing protocol to find 
the pair-wise shortest paths (without any configuration of any device), 
I don't see how this applies to TRILL.

Are your proposing some improvements to the IEEE 802.1 protocols?

> will win. 

My understanding is that manual configuration is used in enterprise 
Ethernets, which among other things ensure that the root bridge is close 
to the routers.

    Erik

---

From: greg.daley at eng.monash.edu.au (Greg Daley)
Date: Wed, 04 May 2005 10:29:10 +1000

Hi Erik,

> Are your proposing some improvements to the IEEE 802.1 protocols?

Given that each trill network interfaces with a legacy 802.1 LAN,
some work to choose a good root for the 802.1D spanning-tree in each
LAN would be useful to reduce the aggregate traffic load on the network.

This doesn't require modification to the 802.1D mechanism, except
that devices which know they are closer to the ingress/egress of
the network can make their chances better.

The original idea I had was before my rbridge awareness (notice that
the router R in the network wasn't considered).  Where trill routers
are present, they have direct knowledge that they are at the edge
of a LAN, and are potential ingress/egress points.

It's possible to use trill's routing protocol on the legacy LAN
to elect which of the trill routers will be the most preferred root
(rather than for exchange of link state).

Alternatively, if no routing protocol is explicitly used on the legacy
LAN, routers within the trill cloud which know they are attached to the
same legacy LAN can determine from their trill routing knowledge which
is the best root.

> Ethernets, which among other things ensure that the root bridge is close 

Yes.  Terrible isn't it!?

:)

The point I was making was that manual configuration is needed,
which means that the traffic flows need to be known
(in that case by an administrator).  The same technique could be
applied automatically or heuristically.

I guess that if there's a requirement for trill/rbridge systems
to interconnect bunches of old gear, you don't want to pick a root
in each "area" manually.

The trill routers should be able to select/elect themselves as the
most likely root bridge (barring explicit manual configuration
perhaps??).  I think Radia's point was that this adds stability.
My point was that the aggregate traffic load may be smaller.

Greg

---

From: erik.nordmark at sun.com (Erik Nordmark)
Date: Tue, 03 May 2005 18:16:35 -0700

> LAN would be useful to reduce the aggregate traffic load on the network.

Ah - sorry for the misunderstanding.
Exactly what makes sense in this case has to do with both the details of 
how rbridges interact with bridges, and what network topology gets deployed.

> of a LAN, and are potential ingress/egress points.

Hmm - a term like "TRILL routers" might be a bit confusing.
We need to be able to discuss networks which have
  - L2 endpoints
	IP hosts
	IP routers
  - Existing bridges
  - TRILL devices (aka rbridges)

When I want to draw diagrams showing routers R1, R2, bridges (B1, B2, 
..), hosts (H1, H2, ..) I've found it useful to pick another letter for 
the hybrid TRILL devices, so I've used "T".
But a term like "trillers" for these devices is a bit odd. I guess we 
could use Rbridges and name them RB1, RB2, etc.

> (rather than for exchange of link state).

If you are assuming that the RSTP protocol terminates at the rbridges, 
then you end up with a sub-topology of the LAN with e.g.

	<rest of LAN up here>
	 |                |
	RB1              RB2
	 |                |
	 -------------------
	 |    |      |
	H1    H2     R1

Where the line is the middle is made up of bridges.
Thus the issue is where RSTP places the root bridge in this sub-topology 
of the whole LAN.

Do I understand your case correctly?

Note that RB1 and RB2 needs to elect one of them to be the forwarder 
between the sub-topology and the rest of the LAN, to make sure that the 
learning tables in the bridges don't flap from seeing packets from the 
same source MAC address sometimes come from RB1 and other times from 
RB2. The bridges will then forward packets based on the port they 
learned the MAC address on, i.e. back towards the RB that forwarded 
packets "in".

Depending on the bridge topology "below" RB1 and RB2, it might very well 
make sense to have the RSTP root bridge be close to RB1/RB2.
It might even make sense to have RB1/RB2 to act as a bridge on the lower 
interface so that itself can become the root bridge.
But a lot of this depends on the topology and traffic patterns "below" 
the RBs in the figure.

> same legacy LAN can determine from their trill routing knowledge which

I didn't understand this part.

    Erik

---

From: greg.daley at eng.monash.edu.au (Greg Daley)
Date: Wed, 04 May 2005 13:15:41 +1000

Hi Erik,

Sorry about not knowing the right terms to use.

I'll try to adopt the ones you used.

> how rbridges interact with bridges, and what network topology gets 

Yes, definitely.

I'd be interested to see if the model is applicable though,
so that I can determine if I need to go off and do more analysis
of the potential benefits.

> could use Rbridges and name them RB1, RB2, etc.

OK, I'll put T, for Trill or Terminus Bridges... or something.

> then you end up with a sub-topology of the LAN with e.g.

Yes.

> interface so that itself can become the root bridge.

This is what I was thinking was particularly applicable to Trill.

> But a lot of this depends on the topology and traffic patterns "below" 

Indeed. That's the case.

My guess (still not checked generally) is that if more traffic is
flowing into and out of one RBridge, then it will be the best place
to have a root (for scalability and traffic dimensioning purposes).

Your diagram is a useful one, since it illustrates non-Trill capable
routers in the network.

In those situations the Internet Router is likely to be the best
root bridge of all, and its adjacent bridge is likely to not be a Trill
device, and is not likely to be able to automatically configure.

Here it's likely that the root bridge will have to be selected manually,
although there may be a case for automatic root bridge selection on
one of the Trill devices, over default preference devices if it is
likely to be a big traffic generator.

> I didn't understand this part.

I was thinking that if the trill devices are connected to the same trill
cloud ("above" the RBs in the diagram), they could do the root
preference election on the "above" side, based on link-state
knowledge from the "below" LAN.

This was basically an off-the-cuff idea though.  It's probably better to
run the lot on the "below" side to handle disjoint Trill domains
connecting to the same legacy LAN.

I'm not sure if the RB as Root Bridge idea is always beneficial, but
would it be worth looking into?

Greg

---

From: touch at ISI.EDU (Joe Touch)
Date: Wed, 04 May 2005 04:18:15 -0700

Erik Nordmark wrote:
...
> could use Rbridges and name them RB1, RB2, etc.

We use the term rbridges in the current ID, and label them RB1, RB2,
etc. as you note.

Joe
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : http://www.postel.org/pipermail/rbridge/attachments/20050504/cd6cf917/signature.bin

---

From: alper.yegin at samsung.com (Alper Yegin)
Date: Wed, 04 May 2005 11:22:03 -0700

> would it be worth looking into?

I think it is more likely to be beneficial, given that it is (they are)
used as the ingress and egress to the rest of the LAN (ie, connecting
bridged segment to the rest of the LAN). But of course, if there is
heavy traffic local to the bridged segment (below RB(s)), then all the
bets are off. 

I think it can be a good default choice, that can be overridden by
manual config or any other dynamic mechanism (if there is any).

Alper

---

From: erik.nordmark at sun.com (Erik Nordmark)
Date: Fri, 06 May 2005 14:13:33 -0700

Greg Daley wrote:

>> Thus the issue is where RSTP places the root bridge in this 
>> sub-topology of the whole LAN.

> to have a root (for scalability and traffic dimensioning purposes).

That's probably the case.

> Your diagram is a useful one, since it illustrates non-Trill capable

Yes, but my figure, repeated below, might not be that representative for 
 >>     RB1              RB2

I real enterprise LAN of reasonable size is probably going to have some 
edge switches connecting to hosts, and a layer of distribution switches, 
which connect to the routers. So a more natural picture would be with 
the routers on "top", perhaps connected to the RBs without any 
intervening bridges:

       R1        R2
        |         |
       RB3       RB4
        | \     /  |
        |  \   /   |
      <rest of LAN up here, with additional "leafs" like the one below
      attached to it>
       |                |
      RB1              RB2
       |                |
       -------------------
       |    |
      H1    H2

> device, and is not likely to be able to automatically configure.

But if the toplogy is more like the picture above, then there is no 
issue with a 802.1D spanning tree between R1 and RB3 etc.
You'd still have a bridge spanning tree for the ("----") bridged 
sub-topology at the bottom, but for that one getting the root close/at 
the RB is good enough.

> likely to be a big traffic generator.

There is still the option to do manual things, but it is worth while to 
think of what LAN topologies look like today, and whether TRILL can 
automatically come up with a reasonable thing for such topologies.
The topology between the RBridges is already handled by using the 
link-state routing protocol, and your suggestion to handle the "leaf" 
bridged sub-topologies by placing their root bridge at/close to the RB 
is a good one.

> connecting to the same legacy LAN.

I'm still failing to draw the topology from your description. Sorry.
(Perhaps you can glue me in off-line.)

> would it be worth looking into?

I think so.
I think we also need to figure out how to get smooth failover when RB1 
fails and we want the designed bridge for the sub-topology to become 
RB2, and have the bridges quickly discard their learned information 
which points at the dead RB1.
Having the designated RB look like the root bridge to the rest of the 
bridges (or look like the shortest cost to the root bridge) is one way 
to make the failover smooth for the bridges.
But there might be other ways to accomplish this.

    Erik

---

From: greg.daley at eng.monash.edu.au (Greg Daley)
Date: Tue, 10 May 2005 14:22:06 +1000

Hi Erik,

Erik Nordmark wrote:
[cut]
>      <rest of LAN up here, with additional "leafs" like the one below

Even if the lower topology is more complex (distribution switches,
redundant paths), the spanning tree rooted at the active Rbridge
is optimal for a stub LAN.

In fact, the more (simple) cycles in the bridges, the better the
performance is compared to other roots.

[cut]
> (Perhaps you can glue me in off-line.)

I guess there's no rush yet.

I was just saying that negotiation can be explicit on the legacy LAN
(like OSPF Designated Router negotiation) or through voodoo which
doesn't exchange signaling on the legacy LAN (but uses rbridge
link-state knowledge).

> But there might be other ways to accomplish this.

It's fairly simple, with the way that root bridge selection works
in 802.1D, to just make the bridge ID preference higher
(making it slightly less desirable) for the backup.

The minor trick is to allow explicit configuration of other bridges
as root, where the automated root isn't going to be suitable (for
example, the 'top' network). This reduces the administrative load to
a single LAN though.

Greg

---

From: gsankara at cisco.com (Ganesh CS)
Date: Thu, 12 May 2005 20:07:49 +0530

Hi Greg,
Greg Daley wrote:
[cut]

>(making it slightly less desirable) for the backup.
Here are we talking about Rbridges running 802.1D as well on the edges 
connecting to 802.1D based bridges or Rbridges will not run 802.1D ?
In the former case, default bridge priority of Rbridges can be set to 
make them more preferred so that RB1 to RB2 bridge fail over is smooth.
In the latter case, a mechanism such as the one you have described is 
required. I have a question here. Assuming such a mechanism is in place 
then consider the following diag.

       R1        R2
       |         |
      RB3       RB4
       |         |
       |         |
     <cloud of bridges>
      |          |
     RB1        RB2
      |          |
      |          |
     R4         R3

Here RB1 and RB2 will be trying to make their neighbors as root. From 
the other end, RB3 and RB4 will also be involved in a similar effort. 
How do we detect/accomodate this case ?

Ganesh

>_______________________________________________
>rbridge mailing list
>rbridge at postel.org
>http://www.postel.org/mailman/listinfo/rbridge
>
>  
>