FAST FLOODING BASED FAST CONVERGENCE TO RECOVER FROM NETWORK FAILURES

• US 20120075988A1
• Filed: 04/20/2011
• Published: 03/29/2012
• 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 8,804,489 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 router detects a network failure and responsive to that failure, floods a fast failure notification message out a set of interfaces of the router. The fast failure notification message includes information that identifies the network failure and includes as its source MAC (Media Access Control) address a MAC address that is assigned to an interface that is coupled with the detected network failure and is not part of the set of interfaces of the router. The router updates a routing table to reflect the network failure. The flooding of the fast failure notification message is performed prior to completion of the routing table update 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, and wherein the fast failure notification message includes as its source MAC (Media Access Control) address a MAC address that is assigned to an interface that is coupled with the detected network failure and is not part of the set of interfaces of the router; 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.

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 if its interfaces before it determines whether to update its routing table.

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

6. The method of claim 1, 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.

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

a data transport layer 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, and wherein the fast failure notification message includes as its source MAC (Media Access Control) address a MAC address that is assigned to the interface that is coupled with the detected network failure; and

an application layer 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.

8. The router of claim 7, 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).

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

10. The router of claim 7, 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 if its interfaces independent of its routing protocol module to update its routing table to reflect the network failure.

11. The router of claim 7, wherein the fast failure notification message has a format that is protocol independent and is issued by the router'"'"'s data plane.

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

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

receiving, on an interface of the router, a first fast failure notification message that includes information that identifies a network failure;

responsive to determining that a source MAC (Media Access Control) address of the fast failure notification message is not associated with the interface, performing the following steps;

adding the source MAC address and interface pair to a bridge MAC table of the router,

flooding the first fast failure notification message to one or more other interfaces for transport to one or more other routers, and

updating a routing table to reflect the network failure;

wherein the step of flooding the first fast failure notification message is performed prior to completion of the step of updating the routing table to reflect the network failure.

14. The method of claim 13, further comprising the steps of:

receiving, on the interface of the router, a second fast failure notification message that includes information that identifies a network failure;

responsive to determining that a source MAC address of the second fast failure notification message is associated with the interface, dropping the packet.

15. The method of claim 14, wherein the first and second fast failure notification messages are identified through identification of a specific destination MAC address reserved for fast flooding based fast convergence.

16. The method of claim 13, wherein the first fast failure notification message has a format that is protocol independent.

17. The method of claim 13, wherein the first 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.

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

an application layer including a routing protocol module configured to manage a routing table; and

a data transport layer including;

a plurality of interfaces to couple the router with a plurality of other routers,

a bridge MAC (Media Access Control) table to store associations of MAC addresses and interfaces, and

a Fast Failure Notification (FFN) module that is configured to, in response to receipt at one of the plurality of interfaces a first fast failure notification message that includes information that identifies a network failure, perform the following;

responsive to a determination that a source MAC (Media Access Control) address of the first fast failure notification message is associated with the interface in which the first fast failure notification message was received on, associate the source MAC address and interface to the bridge MAC table, flood the first fast failure notification message to one or more other ones of the plurality of interfaces, and send the first fast failure notification message to the routing protocol module to update the routing table to reflect the network failure,

wherein the FFN module is to flood the first fast failure notification message to the one or more other ones of the plurality of interfaces prior to the routing protocol module completing its update of the routing table to reflect the network failure.

19. The router of claim 18, wherein the FFN module is further configured to, in response to receipt at one of the plurality of interfaces a second fast failure notification message that includes information that identifies a network failure, perform the following:

responsive to determining that a source MAC address of the second fast failure notification message is associated with the interface in which the second fast failure notification message was received on, drop the packet.

20. The router of claim 19, wherein the first and second fast failure notification messages are identified through identification of a specific destination MAC address reserved for fast flooding based fast convergence.

21. The router of claim 18, wherein the first fast failure notification message has a format that is protocol independent.

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

23. 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.

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

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

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

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

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

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

a data transport layer 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 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.

30. The router of claim 29, 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).

31. The router of claim 29, 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.

32. The router of claim 29, 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.

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

34. The router of claim 29, 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.

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

receiving, on an interface of the router, a fast failure notification message that includes information that identifies a network failure;

flooding the fast failure notification message out one or more interfaces of the router that are not blocked by a spanning tree protocol (STP); and

updating a routing table to reflect the network failure;

wherein the step of flooding the fast failure notification message is performed prior to completion of the step of updating the routing table to reflect the network failure.

36. The method of claim 35, wherein the fast failure notification message is identified through an identification of a specific destination MAC (Media Access Control) address reserved for fast flooding based fast convergence.

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

38. The method of claim 35, 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.

39. The method of claim 35, wherein the step of flooding the fast failure notification message is performed by a data transport layer of the router without interaction of an application layer of the router.

40. The method of claim 39, wherein the step of updating the routing table includes the step of the data transport layer of the router forwarding the fast failure notification message to an IGP (Interior Gateway Protocol) module of the application layer of the router to update the routing table.

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

an application layer including a routing protocol module configured to manage a routing table; and

a data transport layer 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 receipt at one of the plurality of interfaces of a fast failure notification message that includes information that identifies a network failure, perform the following;

flood the fast failure notification message out one or more of the plurality of interfaces that are not blocked by a spanning tree protocol (STP), and

send the fast failure notification message to the routing protocol module to update the routing table to reflect the network failure;

wherein the FFN module is to flood the fast failure notification message to the one or more interfaces prior to the routing protocol module completing its update of the routing table to reflect the network failure.

42. The router of claim 41, wherein the fast failure notification messages is identified through identification of a specific destination MAC address reserved for fast flooding based fast convergence.

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

44. The router of claim 41, 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.

45. 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, transmitting a fast failure notification message that includes information that identifies the network failure to each other router that is in a same domain as the router; and

updating a routing table to reflect the network failure;

wherein the step of transmitting the fast failure notification message is performed independently of the step of updating the routing table to reflect the network failure.

46. The method of claim 45, 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).

47. The method of claim 45, wherein the fast failure notification message includes information to indicate that an adjacency check should be bypassed by the receiving routers.

48. The method of claim 45, 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.

49. The method of claim 45, wherein the fast failure notification message is generated and transmitted by the router'"'"'s data plane.

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

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

a data transport layer including a Fast Failure Notification (FFN) module configured to, in response to a detected network failure, transmit a fast failure notification message that includes information that identifies the network failure to each other router that is in a same domain as the router; and

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

wherein the FFN module is configured to transmit the fast failure notification message to each other router that is in a same domain as the router independently of the update to the routing table to be performed by the routing protocol module.

52. The router of claim 51, 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).

53. The router of claim 51, wherein the fast failure notification message includes information to indicate that an adjacency check should be bypassed by the receiving routers.

54. The router of claim 51, wherein the FFN module is configured to generate the fast failure notification message.

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

56. The router of claim 51, 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.

57. A method in a 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;

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

updating a routing table to reflect the network failure.

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

59. The method of claim 57, 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.

60. 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; 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.

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

62. The router of claim 60, 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.

63. 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, transmitting a fast failure notification message to a multicast group address, wherein the fast failure notification message includes information that identifies the network failure and further indicates to each of a plurality of routers that have joined the multicast group and will receive the fast failure notification message to determine whether to multicast the fast failure notification message to its interfaces independently of that router updating its routing table; and

updating a routing table of the router to reflect the network failure;

wherein the step of transmitting the fast failure notification message is performed independently of the step of updating the routing table to reflect the network failure.

64. The method of claim 63, wherein the fast failure notification message indicates to each of the plurality of routers that have joined the multicast group and will receive the fast failure notification message to use a shortest path first tree in their data transport layer to determine whether to multicast the fast failure notification message.

65. The method of claim 63, wherein the fast failure notification message indicates to each of the plurality of routers that have joined the multicast group and will receive the fast failure notification message to perform a reverse path forwarding (RPF) check.

66. The method of claim 63, wherein the fast failure notification message indicates to each of the plurality of routers that have joined the multicast group and will receive the fast failure notification message to use a bidirectional multicast tree built using a PIM (Protocol Independent Multicast) protocol to determine whether to multicast the fast failure notification message.

67. The method of claim 63, 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).

68. The method of claim 63, 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.

69. The method of claim 63, wherein the multicast group address is reserved for fast failure notification message flooding.

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

71. The method of claim 63, 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.

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

a data transport layer 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, transmit a fast failure notification message to a multicast group address, wherein the fast failure notification message includes information that identifies the network failure and further indicates to each of a plurality of routers that have joined the multicast group and will receive the fast failure notification message to determine whether to multicast the fast failure notification message to its interfaces independently of that router updating its routing table; and

an application layer 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 transmit the fast failure notification message to the multicast group address independently of the update to the routing table to be performed by the routing protocol module.

73. The router of claim 72, wherein the fast failure notification message indicates to each of the plurality of routers that have joined the multicast group and will receive the fast failure notification message to use a shortest path first tree in their data transport layer to determine whether to multicast the fast failure notification message.

74. The router of claim 72, wherein the fast failure notification message indicates to each of the plurality of routers that have joined the multicast group and will receive the fast failure notification message to perform a reverse path forwarding (RPF) check.

75. The router of claim 72, wherein the fast failure notification message indicates to each of the plurality of routers that have joined the multicast group and will receive the fast failure notification message to use a bidirectional multicast tree built using a PIM (Protocol Independent Multicast) protocol to determine whether to multicast the fast failure notification message.

76. The router of claim 72, 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).

77. The router of claim 72, 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.

78. The router of claim 72, wherein the multicast group address is reserved for fast failure notification message flooding.

79. The router of claim 72, wherein the fast failure notification message has a format that is protocol independent and is generated by the FFN module.

80. The router of claim 72, 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.

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

joining a multicast group;

receiving, at an interface, a first fast failure notification message that includes information that identifies a network failure, wherein the first fast failure notification message is addressed to an address associated with the multicast group;

responsive to determining that the interface that the first fast failure notification message was received on is the same interface used by the router to reach a source router of the first fast failure notification message, multicasting the first fast failure notification message to at least one other interface; and

updating a routing table of the router to reflect the network failure;

wherein the step of multicasting the first fast failure notification message is performed prior to completion of the step of updating the routing table to reflect the network failure.

82. The method of claim 81, wherein the address associated with the multicast group is reserved for fast failure notification messages.

83. The method of claim 81, further comprising the steps of:

receiving, at the interface, a second fast failure notification message that includes information that identifies a network failure, wherein the second fast failure notification message is addressed to the address associated with the multicast group; and

responsive to determining that the interface that the second fast failure notification message was received on is not the same interface that is used by the router to reach the source router of the second fast failure notification message, dropping the second fast failure notification message.

84. The method of claim 83, wherein the first and second fast failure notification messages have a format that is protocol independent.

85. The method of claim 83, wherein the first and second fast failure notification messages have an IGP PDU (Interior Gateway Protocol Protocol Data Unit) packet format that is specific to a particular IGP routing protocol.

86. The method of claim 81, wherein the step of determining that the interface that the first fast failure notification message was received on is the same interface as used by the router to reach a source router of the first fast failure notification message is performed by a data transport layer of the router without interaction with an application layer of the router.

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

an application layer including a routing protocol module configured to manage a routing table; and

a data transport layer 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 receipt at one of the plurality of interfaces of a first fast failure notification message that includes information that identifies a network failure and is addressed to an address associated with a multicast group reserved for fast flooding based fast convergence, perform the following;

responsive to a determination that the interface in which the first fast failure notification message was received on is the same interface used by the router to reach a source router of the first fast failure notification message, multicast the first fast failure notification message to the other ones of the plurality of interfaces, and

send the first fast failure notification message to the routing protocol module to update the routing table to reflect the network failure;

wherein the FFN module is to multicast the first fast failure notification message to the other ones of the plurality of interfaces prior to the routing protocol module completing its update of the routing table to reflect the network failure.

88. The router of claim 87, wherein the FFN module is further configured to, in response to receipt at one of the plurality of interfaces a second fast failure notification message that includes information that identifies a network failure, perform the following:

responsive to a determination that the interface in which the second fast failure notification message was received on is not the same interface used by the router to reach a source router of the second fast failure notification message, drop the second fast failure notification message.

89. The router of claim 88, wherein the first and second fast failure notification messages have a format that is protocol independent.

90. The router of claim 88, wherein the routing protocol module is an IGP (Interior Gateway Protocol) module, and wherein the first and second fast failure notification messages have an IGP PDU (Protocol Data Unit) packet format that is specific to the IGP module.

91. A method in a router for participating in fast flooding based fast convergence to recover from a network failure, wherein the router is one of a plurality of routers in a network, the method comprising the steps of:

electing one of the plurality of routers in the network to be a root node;

constructing a shortest path first tree rooted at the root node based on current network topology;

joining a multicast group;

receiving, on an interface of the router, a fast failure notification message that includes information that identifies a network failure, wherein the first fast failure notification message is addressed to an address associated with the multicast group;

multicasting the fast failure notification message according to the shortest path first tree;

updating a routing table of the router to reflect the network failure;

wherein the step of multicasting the fast failure notification message according to the shortest path first tree is performed prior to completion of the step of updating the routing table to reflect the network failure.

92. The method of claim 91, further comprising the steps of:

downloading the shortest path first tree to a data transport layer of the router;

wherein the step of multicasting the first failure notification message according to the shortest path first tree is performed at the data transport layer without interaction from an application layer of the router.

93. The method of claim 92, wherein the step of updating the routing table is performed by the application layer of the router.

94. The method of claim 91, wherein the address associated with the multicast group is reserved for fast failure notification messages.

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

96. The method of claim 91, 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.

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

an application layer including a routing protocol module configured to manage a routing table; and

a data transport layer including;

a plurality of interfaces to couple the router with a plurality of other routers,

a shortest path first tree rooted at one of the plurality of routers,

a Fast Failure Notification (FFN) module that is configured to, in response to receipt at one of the plurality of interfaces a fast failure notification message that includes information that identifies a network failure, perform the following;

multicast the fast failure notification message according to the shortest path first tree, and

send the fast failure notification message to the routing protocol module to update the routing table to reflect the network failure;

wherein the FFN module is to multicast the fast failure notification message prior to the routing protocol module completing its update of the routing table to reflect the network failure.

98. The router of claim 97, wherein the address associated with the multicast group is reserved for fast failure notification messages.

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

100. The router of claim 97, 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.

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

building a bidirectional multicast tree using a PIM (Protocol Independent Multicast) protocol implementation;

joining a multicast group;

receiving, on an interface of the router, a fast failure notification message that includes information that identifies a network failure, wherein the first fast failure notification message is addressed to an address associated with the multicast group;

multicasting the fast failure notification message according to the bidirectional multicast tree; and

updating a routing table of the router to reflect the network failure;

wherein the step of multicasting the fast failure notification message according to the bidirectional multicast tree is performed prior to completion of the step of updating the routing table to reflect the network failure.

102. The method of claim 101, further comprising the steps of:

downloading the bidirectional multicast tree to a data transport layer of the router;

wherein the step of multicasting the first failure notification message according to the bidirectional multicast tree is performed at the data transport layer without interaction from an application layer of the router.

103. The method of claim 102, wherein the step of updating the routing table is performed by the application layer of the router.

104. The method of claim 101, wherein the address associated with the multicast group is reserved for fast failure notification messages.

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

106. The method of claim 101, 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.

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

an application layer including a routing protocol module configured to manage a routing table; and

a data transport layer including;

a plurality of interfaces to couple the router with a plurality of other routers,

a bidirectional multicast tree built using a PIM (Protocol Independent Multicast) protocol implementation,

a Fast Failure Notification (FFN) module that is configured to, in response to receipt at one of the plurality of interfaces a fast failure notification message that includes information that identifies a network failure, perform the following;

multicast the fast failure notification message according to the bidirectional multicast tree, and

send the fast failure notification message to the routing protocol module to update the routing table to reflect the network failure;

wherein the FFN module is to multicast the fast failure notification message prior to the routing protocol module completing its update of the routing table to reflect the network failure.

108. The router of claim 107, wherein the address associated with the multicast group is reserved for fast failure notification messages.

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

110. The router of claim 107, 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.