# Spanning Tree

Discussion in 'Cisco' started by Sizwe Dumisani, Nov 6, 2003.

1. ### Sizwe DumisaniGuest

In trying to digest CISCO PVST, IEEE RST, 802.1d, etc a natural
question occured to me: Given N nodes (switches/bridges), how many
spanning trees are there?
I could dig out my topology books, but I'd rather not resort to that
yet.
Is there a good text that could provide the answer? By the way, does
there exist
a software package that will allow the end-user to position N nodes on
a plane and then generate a graph of all possible spanning trees? This
might be useful in Campus local area network design.

Thanks

Sizwe Dumisani, Nov 6, 2003

2. ### Walter RobersonGuest

:In trying to digest CISCO PVST, IEEE RST, 802.1d, etc a natural
:question occured to me: Given N nodes (switches/bridges), how many
:spanning trees are there?

Depends. Is the tree A-B-C different than the tree C-B-A ?
They have the same topology, but they have different tree roots.

I've just looked around a bit and it appears the answer is non-trivial.
It depends on how they are connected, because when you are talking

For an example of the complexity of the calculations: if you
have an m x n grid, then the number of spanning trees is
http://www.math.wisc.edu/~propp/SSL/trees

_____
1 | | pi j pi k
--- | | (4 - 2 cos ---- - 2 cos ----)
m n | | m n
j,k

where the product is taken over all pairs (j,k) with j=0,1,2,...,m-1
and k=0,1,2,...,n-1 except (0,0).

The general formulae apparently has to do with the determinant

Walter Roberson, Nov 6, 2003

3. ### Andre BeckGuest

In traditional 802.1D and as long as we are not speaking about the
dynamic phase during a topology change, there is exactly one stable
spanning tree throughout the broadcast domain. There is one root,
the root ports, segment designated ports and blocked ports are
established and path costs as well as priorities are settled.
Ehem - seems I misinterpreted your question. You are asking how many
possible spanning trees could occur with N nodes? Well, that depends
on the actual meshing. Somehow the number is just N, as that is the
number of possible roots. If you consider two trees with the same
root but different blocked ports as different, it of course will get
more complicated - but this would also mean different topologies
(a broken link changes topology, a modified pathcost/port priority
in some sense does the same). So as long as you don't modify topology,
the number is indeed N. When it comes to the number of possible
topologies with N nodes where at least every node is connected once,
that's graph theory and math is not my playground (especially not
combinatorics)
Not that I knew of any. In reality, you tend to design a network with
financial and topological limits, resulting in a fixed number of
devices as well as a fixed meshing. If that is done, the devices that
qualify as primary and fall back root bridges usually pop out very
obviously, as they are typically recruited from the core layer switches.

Thinking a bit about really large networks (those with more than a hand-
ful of core switches and lots of sattelite distribution and access
switches, probably a three digit number of total bridges), I see your
argument. A kind of "STP simulator" would be nice, that one would feed
with the planned topology and it would compute the ideal root and
fallback roots for certain traffic patterns. If fed with more VLAN
topology and expected flow paths, the software could even compute the
optimal path costs or port priorities to get a spanning forest to do

Andre Beck, Nov 10, 2003

Generally speaking there is only one instance of spanning-tree, however if
you are using PVST then it is an instance per VLAN. This allows your
network to converge faster. Look at Cisco Works (LMS) because it will map