Method and apparatus for directional networking topology management

• US 7,830,820 B2
• Filed: 01/21/2008
• Issued: 11/09/2010
• Est. Priority Date: 01/21/2008
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Duke, Martin Huynh, Pei, Guangyu
• Primary Examiner(s): Kumar; Pankaj
• Assistant Examiner(s): Sharma; Gautam
• Application Number:
  US12/017,213
• Publication Number:
  US 20090185508A1
• Time in Patent Office: 1,023 Days
• Field of Search: 370/254
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A computer implemented method, apparatus, and computer program product to managing links in a network. A directional link management system comprises a network manager, a router, a situational awareness database, a neighbor discovery module, a topology manager, and a data link manager. The network manager provides performance parameters for a wireless network. The router routes information to neighbor nodes provides information about links between nodes in the wireless network environment. The situational awareness database stores information about the nodes. The neighbor discovery module detects a presence of a new node. The topology manager identifies a set of links for a node using the set of performance parameters, information about the links, and information about the nodes. The data link manager manages the identified links.

Claims

1. A directional link management system comprising:

a network manager, wherein the network manager is capable of providing a set of performance parameters for a wireless network in which directional links are used by a plurality of nodes in the wireless network;

a router, wherein the router is capable of routing information to neighbor nodes within the plurality of nodes and is capable of providing information about links between the plurality of nodes in the wireless network environment;

a situational awareness database, wherein the situational awareness database stores information about nodes;

a neighbor discovery module capable of detecting a presence of a new node in addition to the plurality of nodes;

a topology manager, wherein the topology manager is capable of identifying a set of links for a node with a set of nodes using the set of performance parameters, information about the links, and information about the nodes to form a set of identified links, wherein the topology manager has a plurality of states of operation comprising;

an add state in which the topology manager adds a new link to the set of identified links until the set of identified links are able to meet the set of performance parameters;

a purge state in which the topology manager removes a selected link from the set of identified links until the set of identified links are able to meet the set of performance parameters, wherein the topology manager shifts from the add state to the purge state if all of the set of performance parameters are met, and wherein the topology manager shifts from the purge state to the add state when a number of redundant paths between the nodes and a maximum hop count between the nodes are absent, while a desired throughput between the nodes in the set of performance parameters is met;

a purge cap state in which the topology manager ranks a set of existing links, removes a candidate link from the set of existing links to form a new set of links, determines whether the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters, and deletes the candidate link if the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters, wherein the topology manager shifts from the add state to the purge cap state when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters, wherein the topology manager shifts from the purge state to the purge cap state when the number of redundant paths between the nodes and the maximum hop count between the nodes are met, while a desired throughput between the nodes is absent in the set of performance parameters, and wherein the topology manager shifts from the purge cap state to the add state when the number of redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met; and

an add cap state in which the topology manager ranks a set of potential links between the nodes and selects the new link as one providing a highest improvement score from the set of potential links outside of the set of identified links, wherein the topology manager shifts from the add cap state to the purge state when all of the set of performance parameters are absent, wherein the topology manager shifts from the add cap state to the add state when the number of redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met, and wherein the topology manager shifts from the purge cap state to the add cap state when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters; and

a data link manager, wherein the data link manager is capable of managing the set of identified links.

2. The directional link management system of claim 1, wherein the data link manager manages the set of identified links by establishing the set of identified links.

3. The directional link management system of claim 2, wherein the data link manager manages the set of identified links by changing bandwidth for a selected link within the set of identified links.

4. The directional link management system of claim 3, wherein the data link manager manages the set of identified links by deleting a particular link within the set of identified links.

5. The directional link management system of claim 1, wherein the topology manager identifies the set of links by selecting links to nodes that meet the set of performance parameters that can be reached by a node.

6. The directional link management system of claim 1, wherein the set of performance parameters comprises the number of redundant paths between the nodes, the maximum hop count between the nodes, and the desired throughput between the nodes.

7. The directional link management system of claim 1, wherein the situational awareness database stores terrain information used by the topology manager to manage a set of directional links.

8. The directional link management system of claim 1, wherein the plurality of nodes comprises at least one of aircraft, ground vehicles, and ships.

9. An apparatus comprising:

a node;

a topology manager executing on the node, wherein the topology manager is capable of identifying a set of links for the node with a set of neighbor nodes using a set of performance parameters, information about links, and information about nodes to form a set of identified links, wherein the topology manager has a plurality of states of operation comprising;

an add state in which the topology manager adds a new link to the set of identified links until the set of identified links are able to meet the set of performance parameters;

a purge state in which the topology manager removes a selected link from the set of identified links until the set of identified links are able to meet the set of performance parameters, wherein the topology manager shifts from the add state to the purge state if all of the set of performance parameters are met, and wherein the topology manager shifts from the purge state to the add state when a number of redundant paths between the nodes and a maximum hop count between the nodes are absent, while a desired throughput between the nodes in the set of performance parameters is met;

a purge cap state in which the topology manager ranks a set of existing links, removes a candidate link from the set of existing links to form a new set of links, determines whether the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters, and deletes the candidate link if the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters, wherein the topology manager shifts from the add state to the purge cap state when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters, wherein the topology manager shifts from the purge state to the purge cap state when the number redundant paths between the nodes and the maximum hop count between the nodes are met, while a desired throughput between the nodes is absent in the set of performance parameters, and wherein the topology manager shifts from the purge cap state to the add state when the number redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met; and

an add cap state in which the topology manager ranks a set of potential links between the nodes and selects the new link as one providing a highest improvement score from the set of potential links outside of the set of identified links, wherein the topology manager shifts from the add cap state to the purge state when all of the set of performance parameters are absent, wherein the topology manager shifts from the add cap state to the add state when the number redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met, and wherein the topology manager shifts from the purge cap state to the add cap state when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters; and

a data link manager executing on the node, wherein the data link manager is capable of managing the set of identified links identified by the topology manager.

10. The apparatus of claim 9, wherein the set of links are directional links.

11. The apparatus of claim 9, wherein the topology manager further operates the add state to evaluate the probability that a potential link is blocked by taking a configurable estimate of the number of blockages per unit length and estimating the probability that there are no blockages using the following algorithm:

probability=exp(−

distance×

blockage density),

wherein the distance is a distance between potentially linked nodes, and wherein the blockage density is an estimate of a number of obstacles per unit distance.

12. The apparatus of claim 9, wherein the set of wherein the set of performance parameters comprises a number of redundant paths between the nodes, a maximum hop count between the nodes, and a desired throughput between the nodes.

13. The apparatus of claim 9, wherein the node is selected from one of an aircraft, a ground vehicle, and a ship.

14. A computer implemented method for managing links, the computer implemented method comprising:

responsive to receiving a set of performance parameters, adding, by a topology manager executing on a processor unit, a link to a set of links until the set of links meets the set of performance parameters, wherein the set of performance parameters comprises a number of redundant paths between nodes, a maximum hop count between the nodes, and a desired throughput between the nodes; and

responsive to all of the performance parameters in the set of performance parameters being met by the set of links, removing a selected link from the set of links until the set of links are able to meet the set of performance parameters, wherein the topology manager shifts from adding to removing if all of the set of performance parameters are met, and wherein the topology manager shifts from removing to adding when a number of redundant paths between the nodes and a maximum hop count between the nodes are absent, while a desired throughput between the nodes in the set of performance parameters is met;

ranking, by the topology manager, a set of existing links and removing a candidate link from the set of existing links to form a new set of links;

determining whether the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters and deleting the candidate link if the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters, wherein the topology manager shifts from adding to ranking when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters, wherein the topology manager shifts from the removing to ranking the set of existing links when the number of redundant paths between the nodes and the maximum hop count between the nodes are met, while a desired throughput between the nodes is absent in the set of performance parameters, and wherein the topology manager shifts from ranking the set of existing links to adding when the number of redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met; and

ranking a set of potential links between the nodes and selecting the new link as one providing a highest improvement score from the set of potential links outside of the set of identified links, wherein the topology manager shifts from ranking the set of potential links to ranking the set of existing links when all of the set of performance parameters are absent, wherein the topology manager shifts from ranking the set of potential links to adding when the number redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met, and wherein the topology manager shifts from the ranking the set of existing links to ranking the set of potential links when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters.

15. The computer implemented method of claim 14, wherein the set of performance parameters comprises the number of redundant paths between nodes, the maximum hop count between the nodes and the desired throughput between the nodes.

16. A computer program product having program code stored on a non-transitory computer readable storage medium for managing links, the program code executed by a computer to:

responsive to receiving a set of performance parameters, add a link to a set of identified links until the set of identified links meets the set of performance parameters; and

responsive to all of the performance parameters in the set of performance parameters being met by the set of identified links, remove a selected link from the set of identified links until the set of performance parameters are no longer met, wherein the program code shifts from adding to removing if all of the set of performance parameters are met, and wherein the program code shifts from removing to adding when a number of redundant paths between the nodes and a maximum hop count between the nodes are absent, while a desired throughput between the nodes in the set of performance parameters is met;

rank a set of existing links and removing a candidate link from the set of existing links to form a new set of links;

determine whether the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters and delete the candidate link if the new set of links is compliant with the number of redundant paths between the nodes and the maximum hop count between the nodes in the set of performance parameters, wherein the program code shifts from adding to ranking when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters, wherein the program code shifts from the removing to ranking the set of existing links when the number of redundant paths between the nodes and the maximum hop count between the nodes are met, while a desired throughput between the nodes is absent in the set of performance parameters, and wherein the program code shifts from ranking the set of existing links to adding when the number of redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met; and

rank a set of potential links between the nodes and select the new link as one providing a highest improvement score from the set of potential links outside of the set of identified links, wherein the program code shifts from ranking the set of potential links to ranking the set of existing links when all of the set of performance parameters are absent, wherein the program code shifts from ranking the set of potential links to adding when the number redundant paths between the nodes and the maximum hop count between the nodes are absent, while the desired throughput between the nodes in the set of performance parameters is met, and wherein the program code shifts from the ranking the set of existing links to ranking the set of potential links when the number of redundant paths between the nodes and the maximum hop count between the nodes are met while the desired throughput between the nodes is absent in the set of performance parameters.

17. The computer program product of claim 16, wherein the set of performance parameters comprises the number of redundant paths between nodes, the maximum hop count between the nodes, and the desired throughput between the nodes.