FAST FLOODING BASED FAST CONVERGENCE TO RECOVER FROM NETWORK FAILURES

• US 20140313880A1
• Filed: 07/01/2014
• Published: 10/23/2014
• Est. Priority Date: 09/29/2010
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Lu, Wenhu, Tian, Albert Jining
• Granted Patent: US 9,614,721 B2
• Time in Patent Office: Days
• US Class Current: 370/218
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/0659 by isolating or reconfiguring faulty entities
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's

Abstract

A method in a router for initiating fast flooding based fast convergence to recover from a network failure is disclosed. The method also starts with detecting a network failure. Responsive to the detected network failure, the router floods a layer 2 fast failure notification message out a set of one or more interfaces of the router. The fast failure notification message includes information that identifies the network failure and indicates to a router that receives the fast failure notification message to flood the fast failure notification message out its interfaces that are not blocked by a spanning tree protocol (STP) independently of updating its routing table to reflect the network failure. The method continues with the router updating a routing table to reflect the network failure.

Claims

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 a set of one or more interfaces of the router, 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 an interface of the router, wherein the interface of the router is coupled with the detected network failure, and wherein the interface of the router is not part of the set of interfaces being flooded with the fast failure notification message; and

updating a routing table to reflect the network failure, wherein flooding the fast failure notification message out the set of interfaces of the router is performed prior to completion of the routing table update to reflect the network failure, and wherein the fast failure notification message has a common message format different from Interior Gateway Protocol (IGP) Protocol Data Unit (PDU) message format used for a normal IGP flooding protocol.

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 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 to couple the router 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 fast failure notification message out one or more of the plurality of interfaces, 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 the interface of the router, wherein the interface is coupled with the detected network failure, and wherein the 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 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, and wherein the fast failure notification message has a common message format different from Interior Gateway Protocol (IGP) Protocol Data Unit (PDU) message format used for a normal IGP flooding protocol.

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 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 a set of one or more interfaces of the router, wherein the fast failure notification message includes information that identifies the network failure and indicates to a router that receives the fast failure notification message to flood the fast failure notification message out its interfaces that are not blocked by a spanning tree protocol (STP) independently of updating its routing table to reflect the network failure; and

updating a routing table to reflect the network failure.

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 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 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 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 to couple the router 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 a set of one or more of the plurality of interfaces, wherein the fast failure notification message includes information that identifies the network failure and indicates to a router that receives the fast failure notification message to flood the fast failure notification message out its interfaces that are not blocked by a spanning tree protocol (STP) independently of updating its routing table to reflect the network failure; and

an application layer entity including a routing protocol module configured to update a routing table 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.

16. The 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 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 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 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 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.

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

receiving a unicast fast failure notification message that includes information that identifies a network failure, wherein the unicast fast failure notification message is sent from a second router specifically for the first router, and wherein the second router detects the network failure;

bypassing an adjacency check for the fast failure notification message; and

updating a routing table to reflect the network failure.

22. The method of claim 21, wherein the fast failure notification message has a format that is protocol independent.

23. The method of claim 21, 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.

24. A router to participate in fast flooding based fast convergence to recover from a network failure, the router comprising:

an interface configured to receive and send unicast fast failure notification messages to a routing protocol module, wherein each fast failure notification messages includes information that identifies a network failure, wherein the unicast fast failure notification message is sent from another router specifically for the router, and wherein the other router detects the network failure; and

the routing protocol module configured to perform the following for each received fast failure notification messages;

bypass an adjacency check for that fast failure notification messages, and

update a routing table to reflect the network failure indicated in that fast failure notification message.

25. The router of claim 24, wherein the fast failure notification message has a format that is protocol independent.

26. The router of claim 24, 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.