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

[Greg Daley]

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