System and method for scheduling routing table calculation in link state routing protocols

1. A method of recovering from a failure in a network of routers, the method comprising:

receiving link state advertisements (“LSAs”) from a plurality of routers affected by the failure;

determining previous instances of the received LSAs;

iterating through contents of the received LSAs and the previous instances;

identifying a plurality of subevents based on the iteration;

correlating the subevents to identify the failure; and

scheduling an update in a routing table in response to identifying the failure.

2. The method of claim 1 , wherein correlating subevents comprises starting a timer and ceasing the correlating act based on the timer timing a period, and the method further comprising:

scheduling an update in the routing table if the timer traverses the period and the failure has not yet been identified.

3. A network failure recovery system for a plurality of routers, the system comprising:

a memory configured to store a previous instance of link state advertisement (“LSA”) of the routers;

a module configured to receive at least one LSA from the routers;

an iteration module configured to compare contents of the stored LSA and the received LSA;

an identifying module configured to identify a plurality of subevents based on the iteration;

a correlating module configured to correlate the identified subevents; and

a scheduler configured to schedule an update in a routing table based on the correlated subevents.

4. The system of claim 3 , wherein each of the subevents comprises a link down event, a link up event, a router down event, a router up event, a shared risk link group down event, and a point-of-presence down event.

5. The system of claim 3 , wherein the identifying module is further configured to determine an adjacency status from the received LSA.

6. The system of claim 3 , wherein the correlating module is further configured to identify a change of topology, the system further comprising:

a timing module configured to be started when a failure occurs; and

a routing table module configured to determine the routing table when the change of topology remains unidentified and after the timing module has fired.

7. The system of claim 6 , wherein the failure comprises at least one of a node failure, a shared risk link group failure, and a point-of-presence failure.

8. A method of identifying a topology change of a network, the method comprising:

a first router receiving link state advertisements from a plurality of other routers affected by the topology change;

the first router comparing the received link state advertisements with prior link state advertisement instances to identify a plurality of changes;

the first router correlating the plurality of changes to identify the topology change; and

the first router scheduling a routing table update in response to identifying the topology change and not to each received link state advertisement, thereby requiring less routing table updates.

9. The method of claim 8 , wherein the topology change is identified from a group consisting of a link down event, a link up event, a router down event, a router up event, a shared risk link group down event, and a point-of-presence down event.

10. The method of claim 8 , further comprising

starting a timer when initiating the above mentioned process of identifying the topology change; and

scheduling a routing table update when the timer fires if the topology change remains unidentified.

11. The method of claim 1 , wherein the failure is identified from the group consisting of a link failure, a router failure, a shared risk link group failure, and a point-of-presence failure.

12. The method of claim 1 , wherein at least one of the plurality of subevents is a loss of adjacency between a router originating a link state advertisement and a neighbor router.

13. The method of claim 1 , wherein the correlating the subevents includes identifying a link failure when a router at either end of a link indicates loss of adjacency with a router at the other end.

14. The method of claim 1 , wherein correlating the subevents includes identifying a router failure when all neighbor routers listed as adjacent in the last LSA from a failed router have indicated the loss of adjacency with the failed router.

15. The method of claim 1 , wherein correlating the subevents includes identifying a shared risk link group failure when all links that belong to the shared risk link group have been identified to have failed.

16. The method of claim 1 , wherein the plurality of routers includes a first plurality of routers and a second plurality of routers, wherein correlating the subevents includes identifying a point-of-presence failure when all links connecting a first plurality of routers in a point-of-presence to a second plurality of routers outside the point-of-presence have been identified to have failed.