Lookahead computation of routing information

• US 8,516,152 B2
• Filed: 11/12/2010
• Issued: 08/20/2013
• Est. Priority Date: 11/12/2010
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Rege, Kiran M., Nandagopal, Thyaga
• Primary Examiner(s): HIGA, BRENDAN Y
• Application Number:
  US12/944,928
• Publication Number:
  US 20120124235A1
• Time in Patent Office: 1,012 Days
• Field of Search: 709220-226, 709238-244
• US Class Current: 709/242
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

Various exemplary embodiments relate to a method and related network node including one or more of the following: receiving, at the node, an indication that a current network state has changed to a new network state from an old network state; determining whether the node has access to pre-computed routing information associated with the new network state; if the node has access to pre-computed routing information associated with the new network state, using the pre-computed routing information to route future network traffic; and if the node does not have access to pre-computed routing information associated with the new network state, computing new routing information and using the new routing information to route future network traffic.

Claims

1. A method of reducing routing path convergence time in a network performed in a network node, the method comprising:

generating an ordered set of predicted future network states, wherein the ordered set of predicted future states is ordered based on a likelihood of the network transitioning to each of the respective future network states;

determining the first future network state within the ordered set of predicted future network states for which routing information has not already been computed;

computing predicted routing information based on the first future network state;

storing the predicted routing information in association with the first future network state at the node;

receiving, at the node, an indication that a current network state has changed to a new network state from an old network state;

determining whether the node has access to pre-computed routing information associated with the new network state

if the node has access to pre-computed routing information associated with the new network state, using the pre-computed routing information to route future network traffic; and

if the node does not have access to pre-computed routing information associated with the new network state, computing new routing information and using the new routing information to route future network traffic.

2. The method of claim 1, wherein the step of computing is performed at a second network node distinct from the network node.

3. The method of claim 1 wherein the pre-computed routing information and the new routing information are both shortest path trees.

4. The method of claim 1 wherein the pre-computed routing information and the new routing information are both forwarding tables.

5. The method of claim 1 wherein using routing information to route future network traffic comprises computing a forwarding table based on the routing information.

6. The method of claim 1, further comprising:

after receiving the indication that a current network state has changed, storing old routing information associated with the old network state at the node in association with the old network state.

7. The method of claim 1, further comprising storing a history of previous network states.

8. The method of claim 1, further comprising:

determining whether a memory of the network node is full; and

if the memory is not full;

computing additional predicted routing information based on an additional future network state; and

storing the additional predicted routing information in association with the additional future network state at the node.

9. The method of claim 1, wherein the network node only computes predicted routing information when a processor of the network node would otherwise be idle.

10. A network node that reduces routing path convergence time in a network, the network node comprising:

a processor;

a first interface that receives network state information; and

a network state predictor that predicts an ordered set of predicted future network states based on the network state information, wherein the ordered set of predicted future states is ordered based on a likelihood of the network transitioning to each of the respective future network states; and

a routing information generator that generates at least one set of routing information based on the ordered set of predicted future network states.

11. The network node of claim 10, wherein the network state information includes at least one of a link state advertisement, a description of a current network state, and a description of a network state history.

12. The network node of claim 10, further comprising:

a network state prediction generator that generates a prediction message that includes the at least one future network state; and

a second interface that transmits the prediction message to a second network node.

13. The network node of claim 12,

wherein the network state prediction generator is a routing information message generator and the prediction message further includes the at least one set of routing information.

14. The network node of claim 10, further comprising:

a second interface;

a forwarding table storage that stores a forwarding table;

a routing processor that;

receives network traffic via the first interface,

determines a next hop of the network traffic using the forwarding table, and

transmits the network traffic to the next hop via the second interface.

15. The network node of claim 10, further comprising:

a link state advertisement identifier that determines whether a message received via the first interface includes a link state advertisement;

a network state machine that;

determines a new network state based on the link state advertisement,

determines whether the at least one future network state includes the new network state,

if the at least one future network state includes the new network state, identifies predicted routing information associated with the new network state within the at least one set of routing information, and

if the at least one future network state does not include the new network state, indicates to the routing information generator that new routing information should be generated for the new network state.

16. The network node of claim 10, further comprising:

a prediction storage configured to store the predicted routing information,

wherein the routing information generator is configured to determine whether the prediction storage is full, and if the prediction storage is not full;

compute additional predicted routing information based on an additional future network state; and

store the additional predicted routing information in the prediction storage in association with the additional future network state.

17. A non-transitory machine-readable storage medium encoded with instructions for reducing routing path convergence time in a network performed in a network node, the machine-readable storage medium comprising:

instructions for generating an ordered set of predicted future network states, wherein the ordered set of predicted future states is ordered based on a likelihood of the network transitioning to each of the respective future network states;

instructions for determining a first future network state within the ordered set of predicted future network states for which routing information has not already been computed;

instructions for computing predicted routing information based on the first future network state;

instructions for storing the predicted routing information in association with the first future network state at the node;

instructions for receiving, at the node, an indication that a current network state has changed to a new network state from an old network state;

instructions for determining whether the node has access to pre-computed routing information associated with the new network state;

instructions for, if the node has access to pre-computed routing information associated with the new network state, using the pre-computed routing information to route future network traffic; and

instructions for, if the node does not have access to pre-computed routing information associated with the new network state, computing new routing information and using the new routing information to route future network traffic.

18. The non-transitory machine-readable storage medium of claim 17 wherein the instructions for using routing information to route future network traffic comprise instructions for computing a forwarding table based on the routing information.

19. The non-transitory machine-readable storage medium of claim 17, further comprising:

instructions for, after receiving the indication that a current network state has changed, storing old routing information associated with the old network state at the node in association with the old network state.

20. The non-transitory machine-readable storage medium of claim 17, further comprising:

determining whether a memory of the network node is full; and

if the memory is not full;

computing additional predicted routing information based on an additional future network state; and

storing the additional predicted routing information in association with the additional future network state at the node.