US5805578A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic reconfiguration of multipoint communication channels
Assignee: International Business Machines Corp
•
Filing: 1996-03-12
•
Granted: 1998-09-08
•
Expires: 2016-03-12
Abstract
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.
Inventors
- 👤 Paul Alan Stirpe
- 👤 Dinesh Chandra Verma
- 👤 Stephen Joseph Nadas
- 👤 Manish Gupta
- 👤 Elizabeth A. Hervatic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:18
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/42; H04L45/02; H04L45/28; H04L45/48
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
235 words
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.
Claim 2
Dependent Claim
235 words
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.
Claim 3
Dependent Claim
28 words
A method as set forth in claim 1, wherein removal of subtree root nodes and establishment of paths in said multipoint communication channel are carried out in parallel.
Claim 4
Dependent Claim
118 words
A method as set forth in claim 1, wherein said paths are established in step (a) by transmitting information in messages to acquire network elements, to indicate no longer used network elements that must be reclaimed prior to adding said network elements, in the event that by adding said new network elements prior to the reclaiming said no longer used network elements could cause a cycle to be formed in said multipoint communication channel, and prior to adding a new network element of said new network elements at a given node, reclaiming those of said network elements that are no longer required at said node that could cause a cycle to be formed in said multipoint communication channel.
Claim 5
Dependent Claim
99 words
A method as set forth in claim 1, wherein cycles are avoided in multiple reconfigurations of the multipoint communication channel comprising the steps of i) maintaining an existing state of any network elements which could not be explicitly reclaimed by the leader for the duration of a liveness time-out interval, and ii) avoiding the latter elements in a subsequent modifications of the multipoint communication channel, wherein the liveness time-out interval is the interval of time for which a network element is implicitly reclaimed because a liveness message is not received from the leader within said pre-specified liveness time-out interval.
Claim 6
Dependent Claim
44 words
A method as set forth in claim 1, wherein said multipoint communication channel is constrained by parametric constraints from the leader to any participant nodes, and wherein only paths satisfying said parametric constraints are included in said reconfigured tree of said multipoint communication channel.
Claim 7
Dependent Claim
30 words
A method as set forth in claim 5, wherein the parametric constraints for said multipoint communication channel are selected to offer Quality of Service guarantees to said multipoint communication channel.
Claim 8
Dependent Claim
264 words
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.
Claim 9
Dependent Claim
264 words
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.
Claim 10
Dependent Claim
28 words
A method as set forth in claim 7, wherein removal of subtree root nodes and establishment of paths in said multipoint communication channel are carried out in parallel.
Claim 11
Dependent Claim
118 words
A method as set forth in claim 7, wherein said paths are established in step (a) by transmitting information in messages to acquire network elements, to indicate no longer used network elements that must be reclaimed prior to adding said network elements, in the event that by adding said new network elements prior to the reclaiming said no longer used network elements could cause a cycle to be formed in said multipoint communication channel, and prior to adding a new network element of said new network elements at a given node, reclaiming those of said network elements that are no longer required at said node that could cause a cycle to be formed in said multipoint communication channel.
Claim 12
Dependent Claim
99 words
A method as set forth in claim 7, wherein cycles are avoided in multiple reconfigurations of the multipoint communication channel comprising the steps of i) maintaining an existing state of any network elements which could not be explicitly reclaimed by the leader for the duration of a liveness time-out interval, and ii) avoiding the latter elements in a subsequent modifications of the multipoint communication channel, wherein the liveness time-out interval is the interval of time for which a network element is implicitly reclaimed because a liveness message is not received from the leader within said pre-specified liveness time-out interval.
Claim 13
Dependent Claim
44 words
A method as set forth in claim 7, wherein said multipoint communication channel is constrained by parametric constraints from the leader to any participant nodes, and wherein only paths satisfying said parametric constraints are included in said reconfigured tree of said multipoint communication channel.
Claim 14
Dependent Claim
30 words
A method as set forth in claim 11, wherein the parametric constraints for said multipoint communication channel are selected to offer Quality of Service guarantees to said multipoint communication channel.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-07 | 2002-03-09 | 2002-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-07 | 2006-03-09 | 2006-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-07 | 2010-03-09 | 2010-09-08 | $7700.00 | Window Closed / Lapsed |