Patent Document ID: 8483097
Application ID: 12889636
Patent Flag: 1

Claim One:
1. A method of generating spanning trees in a network, the network including a plurality of nodes interconnected by links, the method comprising the steps of: generating a first spanning tree, which connects all of the plurality of network nodes, wherein at least one link is left unconnected from a predetermined portion of the nodes; generating a second spanning tree, which connects all of the plurality of network nodes and which includes the links that were left unconnected in the first spanning tree; and determining for each link, whether one of the trees is excluded from the link; wherein the steps of generating the first and second spanning trees includes: selecting one of the nodes as a central node; selecting neighboring nodes that neighbor the central node, and connecting them to the central node; selecting further nodes and connecting them to the earlier connected neighboring nodes; and repeating the step of selecting further nodes until all of the plurality of network nodes are connected; wherein the steps of selecting neighboring nodes and further nodes includes: defining a node degree (De) as the number of physical links connected to the node; selecting a first group (G) of nodes having a degree of the highest value among the degrees of all the nodes; selecting the only member of the first group given that the first group has only one member; defining a node usage value (Us) as a ratio of the total number of links originating from the node in all the trees and the degree (De) of the node; selecting, when the first group (G) has more than one member, a second group (G2) to be the members of the first group (G) having the smallest usage value (Us); selecting the only member of the second group (G2) given that the second group has only one member; and selecting, when the second group (G2) has more than one member, the member of the second group (G2) having the smallest MAC address.