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

    Reply to:
     
    Sizwe Dumisani, Nov 6, 2003
    #1
    1. Advertising

  2. In article <>,
    Sizwe Dumisani <> wrote:
    :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
    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
    of the adjacency matrix...
    --
    Would you buy a used bit from this man??
     
    Walter Roberson, Nov 6, 2003
    #2
    1. Advertising

  3. Sizwe Dumisani

    Andre Beck Guest

    (Sizwe Dumisani) writes:
    >
    > 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?


    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.

    > 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?


    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) ;)

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


    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.

    --
    The _S_anta _C_laus _O_peration
    or "how to turn a complete illusion into a neverending money source"

    -> Andre "ABPSoft" Beck +++ ABP-RIPE +++ Dresden, Germany, Spacetime <-
     
    Andre Beck, Nov 10, 2003
    #3
  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.

    Sizwe Dumisani wrote:

    > 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
    >
    > Reply to:
    >
     
    username, Nov 16, 2003
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Amy L.
    Replies:
    0
    Views:
    2,465
    Amy L.
    Jul 24, 2003
  2. teton67

    Spanning Tree issue

    teton67, Nov 19, 2003, in forum: Cisco
    Replies:
    10
    Views:
    4,491
    Andre Beck
    Dec 27, 2003
  3. Amy L.
    Replies:
    1
    Views:
    1,506
  4. wade
    Replies:
    0
    Views:
    1,163
  5. Raimond Alpers

    Spanning-Tree

    Raimond Alpers, Dec 25, 2003, in forum: Cisco
    Replies:
    4
    Views:
    704
    Ron Bandes
    Dec 25, 2003
Loading...

Share This Page