OSPF NON-STOP ROUTING WITH RELIABLE FLOODING

• US 20130070637A1
• Filed: 12/02/2011
• Published: 03/21/2013
• Est. Priority Date: 09/16/2011
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Alfred C. Lindem, III, Ing-Wher Chen
• Inventors: Lindem, Alfred C. III, Lu, Wenhu, Chen, Ing-Wher
• Granted Patent: US 8,717,935 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458

Abstract

A network element is configured for open shortest path first (OSPF) non-stop routing (NSR) with reliable flooding. An active OSPF instance determines to flood a link-state advertisement (LSA). The LSA is synchronized with a backup OSPF instance including storing the LSA with a status that indicates that flooding is pending. The active OSPF instance attempts to reliably flood the LSA to a set of adjacent network elements of the flooding scope of the LSA. If flooding of the LSA completes, the active OSPF instance causes the backup OSPF instance to alter the status of the LSA to indicate that flooding is complete. If the backup OSPF instance becomes the currently active OSPF instance prior to the flooding of the LSA completing, then the new active OSPF instance attempts to reliably flood the LSA.

Claims

1. A method in a network element for open shortest path first (OSPF) non-stop routing with reliable flooding, the method comprising the steps of:

responsive to a first OSPF instance of the network element that is currently acting as an active OSPF instance determining to flood a link-state advertisement (LSA), performing the following steps;

synchronizing the LSA with a second OSPF instance of the network element currently acting as a backup OSPF instance, wherein the step of synchronizing includes storing by the second OSPF instance the LSA with a status that indicates that flooding is pending;

attempting to reliably flood by the first OSPF instance the LSA to a set of one or more adjacent network elements of a flooding scope of the LSA, the step of attempting includes;

transmitting the LSA to each of the set of adjacent network elements in the flooding scope of the LSA with an exception of one adjacent network element if the LSA was received from that adjacent network element,

including the LSA on a plurality of retransmission lists for the plurality of adjacent network elements that the LSA was transmitted to, and

maintaining the plurality of retransmission lists on the first OSPF instance, wherein the plurality of retransmission lists are not synchronized with the second OSPF instance, wherein the step of maintaining includes removing the LSA from a retransmission list for a network element responsive to receiving an acknowledgement of receipt of that LSA from that network element,

if flooding of the LSA is complete, then the first OSPF instance causing the second OSPF instance to alter the status of the LSA to indicate that flooding is complete, wherein the flooding of the LSA is complete when the LSA is not indicated on any of the plurality of retransmission lists; and

if the second OSPF instance has become the currently active OSPF instance prior to the flooding of the LSA completing, then the second OSPF instance attempting to reliably flood the LSA to all of the set of adjacent network elements of the flooding scope of the LSA.

2. The method of claim 1, wherein the second OSPF instance assumes that flooding is pending for each LSA it receives from the first OSPF instance unless the first OSPF instance indicates that flooding is complete for that LSA.

3. The method of claim 1, wherein the step of synchronizing the LSA includes transmitting a message to the second OSPF instance that indicates that flooding is pending for that LSA.

4. The method of claim 3, wherein the step of attempting to reliably flood the LSA is performed substantially concurrently with the step of synchronizing the LSA.

5. The method of claim 1, further comprising the steps of:

maintaining a counter for the LSA that indicates a current number of retransmission lists that the LSA is included on, wherein maintaining the counter includes decrementing the counter responsive to the LSA being acknowledged from one of the plurality of adjacent network elements, and

wherein flooding of the LSA is complete is indicated as being complete when the counter for the LSA is decremented to a predefined value.

6. The method of claim 1, wherein the step of the first OSPF instance causing the second OSPF instance to alter the status of an LSA to indicate that flooding is complete includes sending a message to the second OSPF instance that flooding of that LSA is complete.

7. A network element for open shortest path first (OSPF) non-stop routing with reliable flooding, comprising:

a first OSPF instance, configured to initially act as an active OSPF instance, and having a first reliable flooding module;

a second OSPF instance, configured to initially act as a standby OSPF instance, having a link state database (LSDB), a second reliable flooding module, and a flood pending list;

wherein the first reliable flooding module is configured to;

cause link-state announcements (LSAs) that it has determined to flood to be stored in the link state database and include each of those LSAs to be flooded on the flood pending list until flooding of that LSA is complete;

reliably flood the LSAs stored on the flood pending list to one or more adjacent network elements, wherein reliable flooding of an LSA is complete when an acknowledgement is received from each of the set of adjacent network elements;

upon reliable flooding of an LSA being complete, cause that LSA to be removed from the flood pending list of the second OSPF instance; and

wherein the second reliable flooding module is configured to;

after the second OSPF instance becomes the active OSPF instance, flood all LSAs included on the flood pending list to one or more adjacent network elements.

8. The network element of claim 7, wherein the first reliable flooding module is further configured to flood self-originated LSAs to all adjacent network elements.

9. The network element of claim 7, wherein the first reliable flooding module is configured to flood LSAs received from adjacent network elements that it has determined to flood to all adjacent network elements except the one from which the LSA was received.

10. The network element of claim 7, wherein the first reliable flooding module is further configured to include each LSA it has determined to flood to the one or more adjacent network elements on one or more retransmission lists associated with the one or more adjacent network elements, and wherein the first reliable flooding module is further configured to remove an LSA from a retransmission list associated with a network element responsive to an acknowledgement of receipt of that LSA from that network element.

11. The network element of claim 10, wherein the first OSPF instance further includes flood pending counters, wherein each one of the flood pending counters indicates a number of retransmission lists on which one of the LSAs is awaiting acknowledgement, and wherein flooding of an LSA is complete when its corresponding flood pending counter indicates that the LSA is not on any of the plurality of retransmission lists.

12. The network element of claim 7, wherein the first reliable flooding module is configured to, for each LSA it has determined to flood, send a message to the second reliable flooding module that indicates that flooding of that LSA is pending to cause that LSA to be included on the flood pending list.

13. The network element of claim 7, wherein the first reliable flooding module is configured to, upon reliable flooding of an LSA being complete, send a message to the second reliable flooding module that indicates that flooding of that LSA is complete to cause that LSA to be removed from the flood pending list.

14. A method in a network element for open shortest path first (OSPF) non-stop routing with reliable flooding, the network element including a first OSPF instance that initially is acting as an active OSPF instance and a second OSPF instance that initially is acting as a backup OSPF instance, the method comprising the steps of:

the first OSPF instance reliably flooding LSAs, wherein for each LSA to be flooded, the first OSPF instance synchronizes that LSA with the second OSPF instance with a status of flood pending;

responsive to reliable flooding of an LSA being complete, the first OSPF instance causing the second OSPF instance to alter the status of that LSA to indicate that flooding is complete; and

responsive to the second OSPF instance becoming the currently active OSPF instance, the second OSPF instance reliably flooding those LSAs that have a status of flood pending.

15. The method of claim 14 wherein the step of reliably flooding LSAs includes the following for each LSA to be flooded:

determining a flooding scope for the LSA that includes a set of one or more adjacent network elements;

transmitting the LSA to each of the set of adjacent network elements in the flooding scope of the LSA with an exception of one adjacent network element if the LSA was received from that adjacent network element;

including the LSA on a set of one or more retransmission lists for the set of adjacent network elements that the LSA was transmitted to respectively, and

maintaining the set of retransmission lists including removing the LSA from a retransmission list for a network element responsive to receiving an acknowledgement of receipt of that LSA from that network element.

16. The method of claim 14, wherein the step of causing the second OSPF instance to alter the status of an LSA to indicate that flooding is complete includes the first OSPF instance sending a message notifying the second OSPF instance that flooding is complete.

17. The method of claim 14, wherein the step of synchronizing the LSA with a status of flood pending includes the first OSPF instance sending the second OSPF instance a message to cause the second OSPF instance to store the LSA on a flood pending list.

18. The method of claim 14, wherein reliable flooding of an LSA is complete when the first OSPF instance has received acknowledgements of the LSA from all network elements to which the LSA was sent.

19. The method of claim 18, further comprising the steps of:

maintaining a counter for each LSA reliably flooded that indicates a current number of retransmission lists that the LSA is included on, wherein maintaining the counter includes decrementing the counter responsive to receipt of the LSA being acknowledged, and

wherein flooding of the LSA is indicated as being complete when the counter for the LSA is decremented to a predefined value.