Fast flooding based fast convergence to recover from network failures

1. A method in a router for initiating fast flooding based fast convergence to recover from a network failure, the method comprising the steps of:

detecting a network failure;

responsive to the detected network failure, flooding a fast failure notification message out of one or more interfaces of the router, wherein the fast failure notification message has a type-length-value (TLV) format different from an Interior Gateway Protocol (IGP) Protocol Data Unit (PDU) message format used for a normal IGP flooding protocol, wherein the fast failure notification message includes information that identifies the network failure, wherein the fast failure notification message includes as its source MAC (Media Access Control) address a MAC address that is assigned to one interface of the router, wherein the one interface of the router is coupled with the detected network failure, and wherein the one interface of the router is not part of the one or more interfaces being flooded with the fast failure notification message; and

updating a routing table of the router to reflect the network failure responsive to the detection, wherein flooding the fast failure notification message out of the one or more interfaces of the router is performed prior to completion of the routing table update to reflect the network failure.

2. The method of claim 1 , wherein the step of detecting the network failure is performed by one or more of: Layer-2 link-event monitoring and signaling, and Bidirectional Forwarding Detection (BFD).

3. The method of claim 1 , further comprising the step of initiating, by the router, a normal flooding of a message that indicates the network failure after the step of updating the routing table to reflect the network failure.

4. The method of claim 1 , wherein the fast failure notification message further includes as its destination MAC address a MAC address that is reserved for fast failure notification message flooding that indicates to the router that is to receive the fast failure notification message to determine in its data transport layer whether to flood that fast failure notification message out a set of one or more of its interfaces before it determines whether to update its routing table.

5. A router to initiate fast flooding based fast convergence to recover from a network failure, the router comprising:

a data transport layer entity including:

a plurality of interfaces implementing in circuits to couple the router, by links, with a plurality of other routers, and

a Fast Failure Notification (FFN) module that is configured to, in response to the detected network failure, flood a fast failure notification message out one or more of the plurality of interfaces, wherein the fast failure notification message has a type-length-value (TLV) format different from an Interior Gateway Protocol (IGP) Protocol Data Unit (PDU) message format used for a normal IGP flooding protocol, wherein the fast failure notification message includes information that identifies the network failure, wherein the fast failure notification message includes as its source MAC (Media Access Control) address a MAC address that is assigned to one interface of the router, wherein the one interface is coupled with the detected network failure, and wherein the one interface of the router is not part of the one or more of the plurality of interface being flooded with the fast failure notification message; and

an application layer entity including a routing protocol module configured to update a routing table of the router in response to the detected network failure;

wherein the FFN module is further configured to flood the fast failure notification message out the one or more of the plurality of interfaces independently of the update to the routing table to be performed by the routing protocol module.

6. The router of claim 5 , wherein the router is further configured to detect the network failure by one or more of: Layer-2 link-event monitoring and signaling, and Bidirectional Forwarding Detection (BFD).

7. The router of claim 5 , wherein the routing protocol module is further configured to initiate a normal flooding of a message that indicates the network failure after the routing protocol module updates the routing table.

8. The router of claim 5 , wherein the fast failure notification message further includes as its destination MAC address a MAC address that is reserved for fast failure notification message flooding that indicates to the router that is to receive the fast failure notification message to determine in its data transport layer whether to flood that fast failure notification message out a set of one or more of its interfaces independent of its routing protocol module to update its routing table to reflect the network failure.

9. A method in a first router for initiating fast flooding based fast convergence to recover from a network failure, the method comprising the steps of:

detecting a network failure;

responsive to the detected network failure, flooding a layer 2 fast failure notification message out of one or more interfaces of the first router, wherein the layer 2 fast failure notification message is sent prior to completion of update of a routing table of the first router, wherein the fast failure notification message includes information that identifies the network failure and indicates to a second router that receives the fast failure notification message to flood the fast failure notification message out the second router's interfaces that are not blocked by a spanning tree protocol (STP) independently of updating the second router's routing table to reflect the network failure; and

updating the routing table of the first router to reflect the network failure responsive to the detection.

10. The method of claim 9 , wherein the step of detecting the network failure is performed by one or more of: Layer-2 link-event monitoring and signaling, and Bidirectional Forwarding Detection (BFD).

11. The method of claim 9 , further comprising the step of initiating, by the first router, a normal flooding of a message that indicates the network failure after the step of updating the routing table to reflect the network failure.

12. The method of claim 9 , wherein the fast failure notification message further includes as its destination MAC address a MAC address that is reserved for fast failure notification message flooding.

13. The method of claim 9 , wherein the fast failure notification message has a format that is protocol independent and is issued by the first router's data plane.

14. The method of claim 9 , wherein the fast failure notification message has an IGP PDU (Interior Gateway Protocol Protocol Data Unit) packet format that is specific to a particular IGP routing protocol.

15. A first router to initiate fast flooding based fast convergence to recover from a network failure, the first router comprising:

a data transport layer entity including:

a plurality of interfaces implementing in circuits to couple the router, by links, with a plurality of other routers, and

a Fast Failure Notification (FFN) module that is configured to, in response to a detected network failure, flood a layer 2 fast failure notification message out of one or more of the plurality of interfaces, wherein the layer 2 fast failure notification message is sent prior to completion of update of a routing table of the first router, wherein the fast failure notification message includes information that identifies the network failure and indicates to a second router that receives the fast failure notification message to flood the fast failure notification message out the second router's interfaces that are not blocked by a spanning tree protocol (STP) independently of updating the second router's routing table to reflect the network failure; and

an application layer entity including a routing protocol module configured to update the routing table of the first router in response to the detected network failure,

wherein the FFN module is further configured to flood the fast failure notification message out of the one or more of the plurality of interfaces independently of the update to the routing table to be performed by the routing protocol module.

16. The first router of claim 15 , wherein the router is further configured to detect the network failure by one or more of: Layer-2 link-event monitoring and signaling, and Bidirectional Forwarding Detection (BFD).

17. The first router of claim 15 , wherein the routing protocol module is further configured to initiate a normal flooding of a message that indicates the network failure after the routing protocol module updates the routing table.

18. The first router of claim 15 , wherein the fast failure notification message further includes as its destination MAC address a MAC address that is reserved for fast failure notification message flooding.

19. The first router of claim 15 , wherein the fast failure notification message has a format that is protocol independent and is issued by the data transport layer.

20. The first router of claim 15 , wherein the routing protocol module is an IGP (Interior Gateway Protocol) module, and wherein the fast failure notification message has an IGP PDU (Protocol Data Unit) packet format that is specific to the IGP module.