Adaptive link assignment for a dynamic communication network
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
24 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. 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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification