US4912656A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive link assignment for a dynamic communication network
Assignee: Harris Corp
•
Filing: 1988-09-26
•
Granted: 1990-03-27
•
Expires: 2008-09-26
Abstract
Abstract An adaptive link assignment scheme for dynamically changing communication node topologies such as satellite networks, fleets of ships or aircraft, etc. Periodically each node in the network transmits topology information to all the nodes in the network. Then each node determines the degree of connectivity of the network. It is preferred that the network be at least triconnected, and if the network is less than that each node determines what connections it can make to improve the network connectivity. If more than one alternative is available, a choice is made based on line of sight endurance and then on traffic delay. The identification of the selected connection is then broadcast to all the nodes in the network. Each node thus receives the proposed changes from all the network nodes, and each node then resolves conflicts between the broadcast selections and determines what change it should make. Finally, the changes are implemented. The scheme emphasizes network connectivity to bring the network to a triconnected state and then emphasizes line of sight endurance and reduction of traffic delay.
Inventors
- 👤 Joseph B. Cain
- 👤 Stanley L. Adams
- 👤 John W. Nieto
- 👤 Michael D. Noakes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:28
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04B; H04B7/00; H04B7/14; H04B7/15; H04B7/185; H04B7/18521; H04L45/44
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
216 words
For use in a multinode communication graph including a plurality of communication nodes and having a known graph topology with each node a part of a component, each component made up of a number of nodes between one and the full number of nodes in the graph, each node having a plurality of communication ports, each port capable of establishing a communication link with a communication port of another node, a method of assigning ports to communication links to maintain the connectivity of the graph, said method comprising within any one node the steps of: (a) analyzing the current graph topology to determine the current graph connectivity state; (b) determining the available changes said one node is capable of making to improve the graph connectivity; (c) broadcasting a description of the determined changes to other nodes in the graph; (d) receiving from other nodes in the graph broadcasts of descriptions of changes determined by the other nodes to be available to such other n odes to improve the graph connectivity; (e) resolving conflicts between link assignments in the determined changes of all nodes in the graph to determine a new link assignment for said one node; and (f) initiating establishment of a new communication path with another node in accordance with the determined new link assignment.
Claim 2
Dependent Claim
216 words
For use in a multinode communication graph including a plurality of communication nodes and having a known graph topology with each node a part of a component, each component made up of a number of nodes between one and the full number of nodes in the graph, each node having a plurality of communication ports, each port capable of establishing a communication link with a communication port of another node, a method of assigning ports to communication links to maintain the connectivity of the graph, said method comprising within any one node the steps of: (a) analyzing the current graph topology to determine the current graph connectivity state; (b) determining the available changes said one node is capable of making to improve the graph connectivity; (c) broadcasting a description of the determined changes to other nodes in the graph; (d) receiving from other nodes in the graph broadcasts of descriptions of changes determined by the other nodes to be available to such other n odes to improve the graph connectivity; (e) resolving conflicts between link assignments in the determined changes of all nodes in the graph to determine a new link assignment for said one node; and (f) initiating establishment of a new communication path with another node in accordance with the determined new link assignment.
Claim 3
Dependent Claim
72 words
A method as claimed in claim 1 wherein the step of analyzing the current graph topology comprises the steps of: (i) identifying components within the graph which are at least triconnected with other components of the graph; (ii) identifying components within the graph which are less than triconnected with other components of the graph; and (iii) identifying components within the graph which are less than biconnected with other components of the graph
Claim 4
Dependent Claim
44 words
A method as claimed in claim 2 wherein the step of analysing the current graph topology comprises the further step of: (iv) identifying components within the graph which are in danger of splintering from the graph due to loss of an existing communication link.
Claim 5
Dependent Claim
42 words
A method as claimed in claim 1 wherein the step of analysing the current graph topology comprises the step of identifying components within the graph which are in danger of splintering from the graph due to loss of an existing communication link.
Claim 6
Dependent Claim
49 words
A method as claimed in claim 3 or 4 wherein the step of determining the available changes comprises the step of identifying a port within said one node that can be utilized to establish a new communication link with one of the components identified as in danger of splintering.
Claim 7
Dependent Claim
48 words
A method as claimed in claim 5 wherein the step of identifying a port comprises the step of evaluating existing communication links from said one node to identify an existing communication link that can be broken to provide a port without creating a new biconnected or less component.
Claim 8
Dependent Claim
54 words
A method as claimed in claim 2 wherein the step of determining the available changes comprises the steP of identifying a port within said one node that can be utilized to establish a new communication link with a node of another component with which the component of said one node is less than biconnected.
Claim 9
Dependent Claim
56 words
A method as claimed in claim 2 or 7 wherein the step of determining the available changes comprises the step of identifying a port within said one node that can be utilized to establish a new communication link with a node of another component with which the component o said one node is less than triconnected.
Claim 10
Dependent Claim
55 words
A method as claimed in claim 7 wherein the step of identifying a port includes the steps of determining the line of sight endurance of all port within said one node that are available to establish the new communication link; and identifying the one of said all ports having the greatest line of sight endurance.
Claim 11
Dependent Claim
45 words
A method as claimed in claim 9 wherein the step of identifying a port includes the further step of determining the effect on delay of all traffic transmitted by said one node that would result from establishing the new communication link with the identified port.
Claim 12
Dependent Claim
44 words
A method as claimed in claim 7 wherein the step of identifying a port includes the step of determining the effect on delay of all traffic transmitted by said one node that would result from establishing the new communication link with the identified port.
Claim 13
Dependent Claim
47 words
A method as claimed in claim 1 wherein the step of resolving conflicts includes comparing the descriptions of available changes received from other nodes with the available changes of said one node; identifying commonly available changes; and determining the new link assignment from the commonly available changes.
Claim 14
Dependent Claim
221 words
In a multinode communication graph including a plurality of communication nodes and having a known graph topology with each node a part of a component, each component made up of a number of nodes between one and the full number of nodes in the graph, each node having a plurality of communication ports, each port capable of establishing a communication link with a communication port of another node, an arrangement for assigning ports to communication links to maintain the connectivity of the graph, said arrangement comprising within each node; (a) means for analyzing the current graph topology to determine the current graph connectivity state; (b) means for determining the available changes said one node is capable of making to improve the graph connectivity; (c) means for broadcasting a description of the determined changes to other nodes in the graph; (d) means for receiving from other nodes in the graph broadcasts of descriptions of changes determined by the other nodes to be available to such other nodes to improve the graph connectivity; (e) means for resolving conflicts between link assignments in the determined changes of all nodes in the graph to determine a new link assignment for said one node; and (f) means for initiating establishment of a new communication path with another node in accordance with the determined new link assignment.
Claim 15
Dependent Claim
221 words
In a multinode communication graph including a plurality of communication nodes and having a known graph topology with each node a part of a component, each component made up of a number of nodes between one and the full number of nodes in the graph, each node having a plurality of communication ports, each port capable of establishing a communication link with a communication port of another node, an arrangement for assigning ports to communication links to maintain the connectivity of the graph, said arrangement comprising within each node; (a) means for analyzing the current graph topology to determine the current graph connectivity state; (b) means for determining the available changes said one node is capable of making to improve the graph connectivity; (c) means for broadcasting a description of the determined changes to other nodes in the graph; (d) means for receiving from other nodes in the graph broadcasts of descriptions of changes determined by the other nodes to be available to such other nodes to improve the graph connectivity; (e) means for resolving conflicts between link assignments in the determined changes of all nodes in the graph to determine a new link assignment for said one node; and (f) means for initiating establishment of a new communication path with another node in accordance with the determined new link assignment.
Claim 16
Dependent Claim
75 words
An arrangement as claimed in claim 13 wherein said means for analyzing the current graph topology comprises: (i) means for identifying components within the graph which are at least triconnected with other components of the graph; (ii) means for identifying components within the graph which are less than triconnected with other components of the graph; and (iii) means for identifying components within the graph which are less than biconnected with other components of the graph.
Claim 17
Dependent Claim
42 words
An arrangement as claimed in claim 14 wherein said means for analysing the current graph topology comprises: (iv) means for identifying components within the graph which are in danger of splintering from the graph due to loss of an existing communication link.
Claim 18
Dependent Claim
41 words
An arrangement as claimed in claim 13 wherein said means for analysing the current graph topology comprises means for identifying components within the graph which are in danger of splintering from the graph due to loss of an existing communication link.
Claim 19
Dependent Claim
48 words
An arrangement as claimed in claim 15 or 16 wherein said means for determining the available changes comprises means for identifying a port within said one node that can be utilized to establish a new communication link with one of the components identified as in danger of splintering.
Claim 20
Dependent Claim
47 words
An arrangement as claimed in claim 17 wherein said means for identifying a port comprises means for evaluating existing communication links from said one node to identify an existing communication link that can be broken to provide a port without creating a new biconnected or less component.
Claim 21
Dependent Claim
53 words
An arrangement as claimed in claim 14 wherein said means for determining the available changes comprises means for identifying a port within said one node that can be utilized to establish a new communication link with a node of another component with which the component of said one node is less than biconnected.
Claim 22
Dependent Claim
55 words
An arrangement as claimed in claim 14 or 19 wherein said means for determining the available changes comprises means for identifying a port within said one node that can be utilized to establish a new communication link with a node of another component with which the component of said one node is less than triconnected.
Claim 23
Dependent Claim
56 words
An arrangement as claimed in claim 19 wherein said means for identifying a port includes means for determining the line of sight endurance of all ports within said one node that are available to establish the new communication link; and means for identifying the one of said all ports having the greatest line of sight endurance.
Claim 24
Dependent Claim
44 words
An arrangement as claimed in claim 21 wherein said means for identifying a port further includes means for determining the effect on delay of all traffic transmitted by said one node that would result from establishing the new communication path with the identified port.
Claim 25
Dependent Claim
43 words
An arrangement as claimed in claim 19 wherein said means for identifying a port includes means for determining the effect on delay of all traffic transmitted by said one node that would result from establishing the new communication link with the identified port.
Claim 26
Dependent Claim
53 words
An arrangement as claimed in claim 13 wherein said means for resolving conflicts includes means for comparing the descriptions of available changes received from other nodes with the available changes of said one node; means for identifying commonly available changes; and means for determining the new link assignment from the commonly available changes.
References Cited (Backward Citations)
US4706080A
Cited
US4788721A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-03-26 | 1993-09-25 | 1994-03-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-03-26 | 1997-09-25 | 1998-03-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-03-26 | 2001-09-25 | 2002-03-27 | $7700.00 | Window Closed / Lapsed |