FAST FLOODING BASED FAST CONVERGENCE TO RECOVER FROM NETWORK FAILURES
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
110 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17)
-
-
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. - View Dependent Claims (19, 20, 21, 22)
-
-
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. - View Dependent Claims (24, 25, 26, 27, 28)
-
-
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. - View Dependent Claims (30, 31, 32, 33, 34)
-
-
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. - View Dependent Claims (36, 37, 38, 39, 40)
-
-
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. - View Dependent Claims (42, 43, 44)
-
-
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. - View Dependent Claims (46, 47, 48, 49, 50)
-
-
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. - View Dependent Claims (52, 53, 54, 55, 56)
-
-
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. - View Dependent Claims (58, 59)
-
-
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. - View Dependent Claims (61, 62)
-
-
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. - View Dependent Claims (64, 65, 66, 67, 68, 69, 70, 71)
-
-
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. - View Dependent Claims (73, 74, 75, 76, 77, 78, 79, 80)
-
-
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. - View Dependent Claims (82, 83, 84, 85, 86)
-
-
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. - View Dependent Claims (88, 89, 90)
-
-
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. - View Dependent Claims (92, 93, 94, 95, 96)
-
-
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. - View Dependent Claims (98, 99, 100)
-
-
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. - View Dependent Claims (102, 103, 104, 105, 106)
-
-
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. - View Dependent Claims (108, 109, 110)
-
Specification