EFFICIENT LINK REPAIR MECHANISM TRIGGERED BY DATA TRAFFIC

• US 20130227336A1
• Filed: 02/28/2012
• Published: 08/29/2013
• Est. Priority Date: 02/28/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Agarwal, Navneet, Vasseur, Jean-Philippe
• Granted Patent: US 9,172,636 B2
• Time in Patent Office: Days
• US Class Current: 714/4.3
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

In one embodiment, an intermediate device transmits a data message away from a root device toward a receiver device in a computer network, the data message transmitted by utilizing, in reverse, a link that had been previously selected by the receiver device toward the root device. In response to detecting that the data message did not reach the receiver device, a discovery message is may be sent to one or more neighbor devices, wherein the discovery message carries an identification (ID) of the receiver device and a discovery scope indicating how many hops the discovery message is allowed to traverse to reach the receiver device, and wherein the receiver device, upon receiving the discovery message, triggers a local link repair of the link from the receiver device toward the root device.

Claims

1. A method, comprising:

transmitting, by an intermediate device, a data message away from a root device toward a receiver device in a computer network, the data message transmitted by utilizing, in reverse, a link that had been previously selected by the receiver device toward the root device;

detecting that the data message did not reach the receiver device; and

in response to detecting that the data message did not reach the receiver device, sending a discovery message to one or more neighbor devices, wherein the discovery message carries an identification (ID) of the receiver device and a discovery scope indicating how many hops the discovery message is allowed to traverse to reach the receiver device, and wherein the receiver device, upon receiving the discovery message, triggers a local link repair of the link from the receiver device toward the root device.

2. The method as in claim 1, further comprising:

maintaining a one-hop neighbor list at the intermediate device; and

sending the discovery message to the one or more neighbor devices from the one-hop neighbor list.

3. The method as in claim 1, further comprising:

sending the discovery message to only neighbor devices that are as far as or further than the intermediate device from the root device.

4. The method as in claim 1, wherein sending the discovery message comprises one of either unicasting the discovery message or multicasting the discovery message.

5. The method as in claim 1, further comprising:

sending the discovery message one discovery scope level at a time, wherein each neighbor device receiving the discovery message checks whether it can reach the receiver device, and if so, notifies the intermediate device, and if not, delays a configured time before forwarding the discovery message to a next discovery scope level; and

sending, in response to receiving a notification at the intermediate device that a particular neighbor device can reach the receiver device, an instruction to each other neighbor device to cease forwarding the discovery message.

6. The method as in claim 1, further comprising:

encapsulating the data message within the discovery message.

7. The method as in claim 1, further comprising:

receiving, from a particular neighbor device that can reach the receiver device, a reply to the discovery message, wherein the reply carries a proper path to the receiver device.

8. The method as in claim 1, wherein the discovery message is originated by one of either the intermediate device, or a source of the data message after having been notified that the data message did not reach the receiver device.

9. The method as in claim 1, further comprising:

determining that the discovery message did not result in reaching the receiver device; and

in response, increasing the discovery scope of a subsequently sent discovery message to the receiver device.

10. A method, comprising:

receiving a discovery message at a particular device in response to an intermediate device detecting that a data message transmitted away from a root device toward a receiver device in a computer network did not reach the receiver device, wherein the data message was transmitted utilizing, in reverse, a link that had been previously selected by the receiver device toward the root device, wherein the discovery message carries an identification (ID) of the receiver device and a discovery scope indicating how many hops the discovery message is allowed to traverse to reach the receiver device;

determining whether the receiver device is reachable by the particular device; and

in response to the receiver device being reachable, forwarding the discovery message to the receiver device, wherein the receiver device, upon receiving the discovery message, triggers a local link repair of the link from the receiver device toward the root device; and

is in response to the receiver device not being reachable, decrementing the discovery scope, and, if the decremented discovery scope is non-zero, forwarding the discovery message to one or more neighbor devices of the particular device.

11. The method as in claim 10, further comprising:

maintaining a one-hop neighbor list at the particular device; and

forwarding the discovery message to the one or more neighbor devices from the one-hop neighbor list.

12. The method as in claim 10, further comprising:

sending the discovery message to only neighbor devices that are as far as or further than the particular device from the root device.

13. The method as in claim 10, wherein forwarding the discovery message comprises one of either unicasting the discovery message or multicasting the discovery message.

14. The method as in claim 10, further comprising:

forwarding the discovery message one discovery scope level at a time, wherein each neighbor device receiving the discovery message checks whether it can reach the receiver device, and if so, notifies the particular device, and if not, delays a configured time before forwarding the discovery message to a next discovery scope level; and

sending, in response to receiving a notification at the particular device that a particular neighbor device can reach the receiver device, an instruction to each other neighbor device to cease forwarding the discovery message.

15. The method as in claim 10, further comprising:

in response to the receiver device being reachable over a proper path, returning a reply to the discovery message, wherein the reply carries a proper path to the receiver device.

16. A method, comprising:

determining a selected link from a particular device toward a root device in a computer network, wherein traffic destined away from the root device via the particular device utilizes the selected link in reverse from an intermediate device;

receiving a discovery message at the particular device in response to the intermediate device detecting that a data message transmitted over the selected link in reverse did not reach the particular device, wherein the discovery message is received from a neighbor device other than the intermediate device; and

in response to receiving the discovery message, triggering a local link repair of the selected link from the particular device toward the root device to determine a new selected link from the particular device toward the root device, wherein traffic destined away from the root device via the particular device utilizes the new selected link in reverse from another intermediate device.

17. The method as in claim 16, further comprising:

receiving a data message at the particular device over an improper, unselected link from a given intermediate device; and

notifying the given intermediate device of the improper use of the unselected link.

18. The method as in claim 17, further comprising:

determining that more than a configured number of improper uses of unselected links have occurred at the particular device; and

in response, notifying a management device of the improper uses, wherein the management device is configured to take corrective action regarding the improper uses.

19. The method as in claim 16, further comprising:

decapsulating the data message from within the discovery message.

20. An apparatus, comprising:

one or more network interfaces to communicate in a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

generate and transmit a discovery message in response to a data message sent away from a root device of the computer network not reaching an intended receiver device over a link that had been previously selected, in reverse, by the receiver device toward the root device;

receive a discovery message for a first intermediate device transmitting a different data message and to forward the discovery messages to the receiver device if reachable, else, in response to the receiver device not being reachable, decrement a discovery scope of the discovery messages, and forward a discovery message with a non-zero scope to one or more neighbor devices; and

receive a discovery message intended for the apparatus in response to a second intermediate device detecting that a data message did not reach the apparatus over a link previously selected, in reverse, from the apparatus to the second intermediate device, and to trigger a local link repair of the previously selected link in response.

21. The apparatus as in claim 20, wherein the process when executed is further operable to:

receive a data message over an improper, unselected link from a given intermediate device; and

notify the given intermediate device of the improper use of the unselected link.

22. A tangible, non-transitory, computer-readable media having software encoded thereon, the software, when executed by a processor on an apparatus, operable to:

generate and transmit a discovery message in response to a data message sent away from a root device of the computer network not reaching an intended receiver device over a link that had been previously selected, in reverse, by the receiver device toward the root device;

receive a discovery message for a first intermediate device transmitting a different data message and to forward the discovery messages to the receiver device if reachable, else, in response to the receiver device not being reachable, decrement a discovery scope of the discovery messages, and forward a discovery message with a non-zero scope to one or more neighbor devices; and

receive a discovery message intended for the apparatus in response to a second intermediate device detecting that a data message did not reach the apparatus over a link previously selected, in reverse, from the apparatus to the second intermediate device, and is to trigger a local link repair of the previously selected link in response.