Granted Patent B2

US 8,509,098 · App. 11/414,126 · Granted Aug 13, 2013

Abstract

Claims (97)

1. A non-transitory computer readable medium for storing computer instructions which, when processed by a computer, adapt the operation of the computer to perform a method for determining a network connectivity in a network having a plurality of nodes, the method comprising the steps of:

generating a candidate link for each of a plurality of node pairs;

predicting a performance of each candidate link by evaluating an expected impact of at least one performance-impacting condition on each candidate link;

determining the expected impact of the at least one performance-impacting condition on the candidate link using:

(a) node position information associated with the nodes in the node pair, and

(b) respective condition position information associated with each of the at least one performance-impacting condition;

determining network topology changes using the predicted performances of the candidate links; and

performing network layer routing protocol computations for discovering new routes associated with said network topology changes over a network planning window using various node specific configurations actions performed according to a configuration schedule.

2. The method of claim 1 , wherein generating the candidate link for each node pair comprises the steps of:

selecting a link model comprising at least one link parameter; and

generating the candidate link using the link model, wherein the candidate link comprises a logical model of a potential physical link between the nodes in the associated node pair, wherein the candidate link comprises the at least one link parameter.

3. The method of claim 2 , wherein generating the candidate link for each node pair further comprises the steps of:

predicting position information for a first node in the node pair;

predicting position information for a second node in the node pair;

generating the candidate link for the node pair using the respective position information for the first and second nodes.

4. The method of claim 2 , wherein the at least one link parameter comprises at least one performance evaluation parameter for determining the predicted performance of the candidate link, wherein the at least one performance evaluation parameter comprises at least one of a back-to-back performance of a transmitter-receiver pair of the node pair and a loss incurred during directed transmission.

5. The method of claim 2 , wherein the at least one link parameter comprises at least one of a link type, a link direction, a link range, and a link capacity.

6. The method of claim 1 , wherein predicting the performance of each candidate link comprises the steps of:

identifying the at least one condition from a plurality of conditions associated with the network, each of the at least one condition identified using node position information associated with the nodes of the node pair and condition position information associated with each of the at least one condition;

determining the expected impact of the at least one condition on the candidate link using the node position information and the condition position information; and

predicting the performance of the candidate link by adjusting an expected performance of the candidate link using the expected impact of the at least one condition on the candidate link.

7. The method of claim 1 , wherein predicting the performance of each candidate link comprises the step of:

determining at least one of an outage probability of the candidate link and a mean power margin of the candidate link.

8. The method of claim 1 , wherein predicting the performance of each candidate link comprises the steps of:

identifying the at least one condition from a plurality of conditions associated with the network, each of the at least one condition identified using node position information associated with the nodes of the node pair and condition position information associated with each of the at least one condition, wherein at least a portion of the node and condition position information varies over a time period;

determining a time-varying expected impact of the at least one condition on the candidate link over the time period using the node and condition position information; and

predicting a time-varying performance of the candidate link over the time period by adjusting a time-varying expected performance of the candidate link using the time-varying expected impact of the at least one condition on the candidate link.

9. The method of claim 1 , wherein the at least one condition comprises at least one of a network condition, a node condition, a link condition, and an environmental condition, wherein the environmental condition comprises at least one of a terrain condition, an atmospheric condition, and a weather condition.

10. The method of claim 1 , wherein determining the network connectivity comprises the step of:

selecting at least a portion of the candidate links using the performances of the respective candidate links.

11. The method of claim 10 , further comprising:

determining at least one configuration action for establishing the network connectivity, wherein the at least one configuration action comprises at least one of a link establishment action, a link maintenance action, a link reconfiguration action, a link replacement action, and a link removal action; and

generating at least one configuration command using the at least one configuration action, the at least one configuration command adapted for physically establishing the selected candidate links in the network.

12. The method of claim 1 , wherein determining the network connectivity comprises:

determining an expected time delay associated with establishing the network connectivity in the network; and

determining the network connectivity using the expected time delay.

13. An apparatus for determining a network connectivity in a network having a plurality of nodes, comprising:

means for representing an overall network connectivity using a configuration schedule, wherein the configuration schedule comprises at least one configuration action for each of a plurality of time periods in a network planning window;

means for generating a candidate link for each of a plurality of node pairs;

means for predicting a performance of each candidate link by evaluating an expected impact of at least one performance-impacting condition on each candidate link;

means for determining the expected impact of the at least one performance-impacting condition on the candidate link using:

(a) node position information associated with the nodes in the node pair, and

(b) respective condition position information associated with each of the at least one performance-impacting condition; and

means for determining a network topology changes using the predicted performances of the candidate links; and

means for performing network layer routing protocol computations for discovering new routes associated with said network changes over a network planning window using various node specific configurations actions performed according to a configuration schedule.

14. A non-transitory computer readable medium for storing computer instructions which, when processed by a computer, adapt the operation of the computer to perform a method for determining an overall network connectivity in a network having a plurality of nodes, the method comprising the steps of:

performing the following steps for each of a plurality of time periods in a network planning window:

representing the overall network connectivity using a configuration schedule, wherein the configuration schedule comprises at least one configuration action for each of a plurality of time periods in the network planning window;

generating a candidate link for each of a plurality of node pairs;

predicting a performance of each candidate link by evaluating an expected impact of at least one performance-impacting condition on each candidate link;

determining the expected impact of the at least one performance-impacting condition on the candidate link using:

(a) node position information associated with the nodes in the node pair, and

(b) respective condition position information associated with each of the at least one performance-impacting condition; and

determining network topology changes using the predicted performances of the candidate links; and

processing each of the determined network topology changes associated with each of the plurality of time periods for determining the overall network connectivity associated with the network planning window; and

performing network layer routing protocol computations for discovering new routes associated with network topology changes over the network planning window using various node specific configurations actions performed according to a configuration schedule.

15. A non-transitory computer readable medium for storing computer instructions which, when processed by a computer, adapt the operation of the computer to perform a method for determining a network connectivity in a network having a plurality of nodes, the method comprising the steps of:

representing an overall network connectivity using a configuration schedule, wherein the configuration schedule comprises at least one configuration action for each of a plurality of time periods in a network planning window;

generating, for each of the plurality of time periods in a time window, a plurality of candidate links, the plurality of candidate links associated with a plurality of node pairs in a set of node pairs;

predicting, for each time period, a performance of each candidate link generated in that time period, the predicted performances being determined by evaluating an expected impact of at least one performance-impacting condition on each candidate link;

determining the expected impact of the at least one performance-impacting condition on the candidate link using:

(a) node position information associated with the nodes in the node pair, and

(b) respective condition position information associated with each of the at least one performance-impacting condition;

(c) network connectivity for the time window by selecting, for each time period, at least a portion of the candidate links of the time period, the candidate links selected for each time period for satisfying at least one performance quality measure; and

(d) network layer routing protocol computations for discovering new routes associated with network topology changes over a network planning window using various node specific configurations actions performed according to a configuration schedule.

16. The method of claim 15 , wherein generating the candidate link for each node pair comprises the steps of:

selecting a link model comprising at least one link parameter; and

generating the candidate link using the link model, wherein the candidate link comprises a logical model of a potential physical link between the nodes in the associated node pair, wherein the candidate link comprises the at least one link parameter.

17. The method of claim 16 , wherein generating the candidate link for each node pair further comprises the steps of:

predicting position information for a first node in the node pair;

predicting position information for a second node in the node pair;

generating the candidate link for the node pair using the respective position information for the first and second nodes.

18. The method of claim 15 , wherein predicting the performance of each candidate link comprises the steps of:

identifying the at least one condition from a plurality of conditions associated with the network, each of the at least one condition identified using node position information associated with the nodes of the node pair and condition position information associated with each of the at least one condition;

determining the expected impact of the at least one condition on the candidate link using the node position information and the condition position information; and

predicting the performance of the candidate link by adjusting an expected performance of the candidate link using the expected impact of the at least one condition on the candidate link.

19. A non-transitory computer readable medium for storing computer instructions which, when processed by a computer, adapt the operation of the computer to perform a method for establishing a network connectivity in a network having a plurality of nodes, comprising the steps of:

representing an overall network connectivity using a configuration schedule, wherein the configuration schedule comprises at least one configuration action for each of a plurality of time periods in a network planning window;

receiving, at a first node, a configuration message adapted for triggering at least one link configuration action associated with a link between the first node and a second node, the at least one link configuration action determined by a method comprising:

generating a candidate link for each of a plurality of node pairs;

predicting a performance of each candidate link by evaluating an expected impact of at least one performance-impacting condition on each candidate link;

determining the expected impact of the at least one performance-impacting condition on the candidate link using:

(a) node position information associated with the nodes in the node pair, and

(b) respective condition position information associated with each of the at least one performance-impacting condition;

determining the at least one link configuration action using the predicted performances of the candidate links; and

performing network layer routing protocol computations for discovering new routes associated with network topology changes over a network planning window the at least one link configuration action being node specific and performed according to a configuration schedule.

20. An apparatus for establishing a network connectivity in a network having a plurality of nodes, comprising:

means for representing an overall network connectivity using a configuration schedule, wherein the configuration schedule comprises at least one configuration action for each of a plurality of time periods in a network planning window;

a receiver for receiving, at a first node, a configuration message adapted for triggering at least one link configuration action associated with a link between the first node and a second node, the at least one link configuration action determined by:

means for generating a candidate link for each of a plurality of node pairs;

means for predicting a performance of each candidate link by evaluating an expected impact of at least one performance-impacting condition on each candidate link;

determining the expected impact of the at least one performance-impacting condition on the candidate link using:

(a) node position information associated with the nodes in the node pair, and

(b) respective condition position information associated with each of the at least one performance-impacting condition;

means for determining the at least one link configuration action using the predicted performances of the candidate links;

means for performing network layer routing protocol computations for discovering new routes associated with network topology changes over a network planning window, the at least one link configuration action being node specific and performed according to a configuration schedule; and

a processor coupled to the receiver for processing the configuration message to trigger the at least one configuration action associated with the link between the first node and the second node.

Assignments (9)