Automatic reconfiguration of multipoint communication channels
First Claim
1. In a communication network having a plurality of connected nodes, and a multi- point communication channel, logically represented by a tree comprising a root node from which messages are transmitted along path toward leaf nodes of the tree, interconnecting at least selected ones of said nodes, one of said selected nodes being a leader, where said leader is the root node of said tree logically representing said multipoint communication channel, a method of reconfiguring said multipoint communication channel when one or more of said selected nodes becomes disconnected from said multipoint communication channel, resulting in said multipoint communication channel being partitioned into a parent subtree and one or more disconnected subtrees, where said parent subtree comprises said leader and where each disconnected sub-tree contains a subtree root node, said method comprising:
- a) selecting and establishing a path between a node of said parent subtree and the subtree root node of each disconnected subtree not containing said leader, and;
b) when no path exists between said parent subtree and a subtree root node of any said disconnected subtree, removing said subtree root node to partition said disconnected subtree into additional disconnected subtrees, and repeating steps (a) through (b),whereby all paths selected in step (a), all disconnected subtrees to which a path was successfully selected and established in step (a) and the parent subtree containing the leader, form a reconfigured tree of said multipoint communication channel.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of reconfiguring a multipoint communications channel to reconnect selected nodes after failures occur in the network disclosed. The method for this invention requires that a selected node (leader) participating in the multipoint communication channel act as the coordinator of the re-establishment protocol. The coordinator (leader) monitors the state of network topology to determine failures, recomputes an alternative feasible communication channel path in the case of failure, and generates messages to join new network elements in the multipoint communication channel. By using a novel tree recomputation method that rejoins the disconnected subtrees created by the network failure to the tree containing the coordinator, along with network topology information, the coordinator is able to minimize messaging and preserve the original channel to the maximum possible extent. The invention can be practiced in a network which provides quality-of-service characteristics to multipoint connections, by ensuring that the recomputation of the multipoint communication channel preserves the quality-of-service of the original connection.
182 Citations
12 Claims
-
1. In a communication network having a plurality of connected nodes, and a multi- point communication channel, logically represented by a tree comprising a root node from which messages are transmitted along path toward leaf nodes of the tree, interconnecting at least selected ones of said nodes, one of said selected nodes being a leader, where said leader is the root node of said tree logically representing said multipoint communication channel, a method of reconfiguring said multipoint communication channel when one or more of said selected nodes becomes disconnected from said multipoint communication channel, resulting in said multipoint communication channel being partitioned into a parent subtree and one or more disconnected subtrees, where said parent subtree comprises said leader and where each disconnected sub-tree contains a subtree root node, said method comprising:
-
a) selecting and establishing a path between a node of said parent subtree and the subtree root node of each disconnected subtree not containing said leader, and; b) when no path exists between said parent subtree and a subtree root node of any said disconnected subtree, removing said subtree root node to partition said disconnected subtree into additional disconnected subtrees, and repeating steps (a) through (b), whereby all paths selected in step (a), all disconnected subtrees to which a path was successfully selected and established in step (a) and the parent subtree containing the leader, form a reconfigured tree of said multipoint communication channel. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. In a communication network having a plurality of connected nodes, and a multi- point communication channel, logically represented by a tree comprising a root node from which messages are transmitted along path toward leaf nodes of the tree, interconnecting at least selected ones of said nodes, one of said selected nodes being a leader, where said leader is the root node of said tree logically representing said multipoint communication channel, a method of reconfiguring said multipoint communication channel when one or more of said selected nodes becomes disconnected from said multipoint communication channel, resulting in said multipoint communication channel being partitioned into a parent subtree and one or more disconnected subtrees, where said parent subtree comprises said leader and where each disconnected sub-tree contains a subtree root node, said method comprising:
-
a) in the parent subtree, removing any leaf nodes that are not one of said selected nodes; b) selecting and establishing a path between a node of said parent subtree and the the root node of each disconnected subtree that does not contain said leader, and; c) when no path exists between said parent subtree and a subtree root node of any said disconnected subtree, removing said subtree root node to partition said disconnected subtree into additional disconnected subtrees, and then repeating steps (a) through (c), whereby all paths selected in step (b), all disconnected subtrees to which a path was successfully selected and established in step (b) and the parent subtree containing the leader after any leaf nodes are removed in step (a), form a reconfigured tree of said multipoint communication channel. - View Dependent Claims (8, 9, 10, 11, 12)
-
Specification