Spanning Tree

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

  1. 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
    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.


    Reply to:
    Sizwe Dumisani, Nov 6, 2003
    1. Advertisements

  2. :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
    about spanning trees, you are usually talking about devices not all
    having direct access to each other.

    For an example of the complexity of the calculations: if you
    have an m x n grid, then the number of spanning trees is

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

    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
    of the adjacency matrix...
    Walter Roberson, Nov 6, 2003
    1. Advertisements

  3. Sizwe Dumisani

    Andre Beck Guest

    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
    VLAN load balancing on trunks.
    Andre Beck, Nov 10, 2003
  4. Sizwe Dumisani

    username Guest

    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
    out your spanning-tree.
    username, Nov 16, 2003
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.