×

System for managing topology of a network in spanning tree data structure by maintaining link table and parent table in each network node

  • US 5,606,669 A
  • Filed: 05/23/1995
  • Issued: 02/25/1997
  • Est. Priority Date: 05/25/1994
  • Status: Expired due to Term
First Claim
Patent Images

1. In a data communication network having a plurality of nodes and a plurality of bi-directional links, each of said nodes being connected to at least one other node through one of said bi-directional links to enable data to be exchanged between the nodes, said network being defined by at least one spanning tree comprising a root node and one or more children nodes, each of said children nodes except the root node having a single parent node, a topology manager located in at least one of said nodes comprising:

  • a) a link table memory containing a link table for each node in the current spanning tree, each link table identifying the node with which the link table is associated and each of the links from the identified node to other nodes in the network, each link entry in a link table including a spanning tree entry which indicates whether the link is currently included in the current spanning tree,b) a parent table memory containing a node entry for each node in the current spanning tree, each node entry other than the entry for the root node further containing the address of the node'"'"'s parent node, the address of the link table for the node and the identification of dual links which are common to the link table for the node and link tables for other nodes; and

    c) spanning tree update logic for updating the link tables and the parent table upon a change in network topology affecting the current spanning tree, said spanning tree update logic further includingi) means for scanning the parent table memory to detect an entry identifying a first node for which no parent node is identified, said means assigning the root position in a new spanning tree to the first node,ii) means for reading the parent table and link table for the first node to identify at least one adjacent node which satisfies predetermined criteria for a parent node to the first node, marking the adjacent node as a parent to the first node and amending the parent tables and link tables accordingly, andiii) means for repeating the operations performed by said reading means with each identified adjacent node being assigned the role as a first node until all nodes have a parent and amending the parent tables and link tables accordingly.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×