System for managing topology of a network in spanning tree data structure by maintaining link table and parent table in each network node
First Claim
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.
0 Assignments
0 Petitions
Accused Products
Abstract
A topology manager within a data communication network including a number of nodes interconnected by bi-directional links, wherein each said node is provided with means for dynamically setting and storing within the node a full topology database including full parent-node-relationship references. The system is is capable of fast path determination and fast spanning tree recovery based on the topology database contents.
437 Citations
8 Claims
-
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 including i) 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, and iii) 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 Dependent Claims (2, 4)
-
-
3. 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; 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; and d) route selection means for quickly determining a path between any two nodes on the spanning tree, one of said nodes being identified as a source node and the other being identified as a target node, said route selection means being located at the source node and comprising i) means for scanning the parent table memory to create a first list comprising nodes on the spanning tree beginning with the source node and ending with the spanning tree root node and a second list comprising nodes on the spanning tree beginning with the target node and ending with the spanning tree root node, ii) means for processing the first and second lists by eliminating the spanning tree root node from both lists and each succeeding child node until all nodes common to both lists have been eliminated except the common node closest to the source node on the first list and to the target node on the second list, and iii) means for defining the route between the source node and the target node as the concatenation of the nodes remaining on the first and second lists.
-
-
5. For use 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 method of managing the topology of the network, said method being implemented in at least one node and comprising the steps of:
-
a) maintaining 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) maintaining a parent table 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; c) updating the link tables and the parent table upon a change in network topology affecting the current spanning tree; and d) quickly selecting a route between any two nodes on the spanning tree, one of said nodes being identified as a source node and the other being identified as a target node, said route selection steps comprising i) creating a first list comprising nodes on the spanning tree beginning with the source node and ending with the spanning tree root node and a second list comprising nodes on the spanning tree beginning with the target node and ending with the spanning tree root node, ii) beginning with the spanning tree node, eliminating the spanning tree root node from both lists and each succeeding child node until all nodes common to both lists have been eliminated except the common node closest to the source node on the first list and to the target node on the second list, and iii) concatenating the nodes remaining on the first and second lists to define the route between the source node and the target nodes. - View Dependent Claims (8)
-
-
6. For use 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 method of managing the topology of the network, said method being implemented in at least one node and comprising the steps of:
-
a) maintaining 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) maintaining a parent table 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) updating the link tables and the parent table upon a change in network topology affecting the current spanning tree, said updating step further including the steps of i) scanning the parent table memory to detect an entry identifying a first node for which no parent node is identified and assigning the root position in a new spanning tree to the first node, ii) 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, and iii) 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 Dependent Claims (7)
-
Specification