Identifying link failures in a network

• US 6,804,712 B1
• Filed: 06/30/2000
• Issued: 10/12/2004
• Est. Priority Date: 06/30/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kracht, James
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): Choudhary, Anita
• Application Number:
  US09/607,748
• Time in Patent Office: 1,565 Days
• Field of Search: 709/223-224, 370/216, 370/222, 370/242, 370/254-258, 714/4
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 41/0659 by isolating or reconfiguring faulty entities
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A mechanism for identifying link failures in a network is disclosed. To identifying link failures, a failed-link discovery mechanism receives information that represents a physical topology of the network. A management station that is associated with the network is identified and a path between one or more devices of the network and the management station is determined. For each link, a set of beyond link devices, that identifies only those devices that are beyond a particular link relative to the management station, is identified. Thereafter, a first message is sent to each active device within the network. Based on the responses that are returned in response to the first messages, a set of non-responding devices within the network is determined. The set of non-responding devices is then compared to each set of beyond link devices to identify link failures within the network.

Claims

1. A method for identifying failures of links in a network, the method comprising the computer-implemented steps of:

receiving information that represents a physical topology of the network;

determining a path between a particular network device and a management station that is associated with the network, wherein the path consists of one or more links that connect devices within the network;

determining, based on whether the particular network device is between one or more devices of the network and the management station, a set of beyond link devices, wherein the set of beyond link devices includes only devices that can communicate with the management station through the particular network device and that cannot communicate with the management station without the particular network device;

sending a first message to one or more active devices within the network, wherein each first message requests a response to be returned from the device for which the message was sent;

determining a set of non-responding devices within the network based on responses to the first messages; and

comparing the set of non-responding devices to the set of beyond link devices to identify link failures within the network.

2. The method as recited in claim 1, wherein the step of sending a first message includes the step of sending an Internet Control Message Protocol (“

ICMP”

) message to one or more devices within the network.

3. The method as recited in claim 1, wherein the step of determining a set of non-responding devices includes the steps of:

sending a second message to devices within the network that did not respond to the first message; and

identifying a particular device as a non-responding device only if the particular device fails to respond to the second message.

4. The method as recited in claim 3, further comprising the step of identifying a set of slow responding devices, wherein the set of slow responding devices includes those devices that responded to the second message from the management station.

5. The method as recited in claim 1, wherein the step of determining a set of non-responding devices within the network includes the step of maintaining an active device bit vector that identifies devices for which a response is expected in response to sending the first messages.

7. The method as recited in claim 1, wherein:

the step of sending a first message to one or more active devices within the network further includes the steps of;

polling one or more devices at a first frequency rate to determine an initial set of non-responding devices; and

polling at a second frequency rate devices within the initial set of non-responding devices to determine a set of slow-responding devices, wherein the first frequency rate and the second frequency rate represent different polling rates; and

the step of determining a set of non-responding devices within the network comprises the step of comparing the initial set of non-responding devices to the set of slow-responding devices to determine the set of non-responding devices.

6. A method for identifying failures of links in a network, the method comprising the computer-implemented steps of:

receiving information that represents a physical topology of the network;

determining a path between one or more devices of the network and a management station that is associated with the network, wherein each path consists of one or more links that connects devices within the network;

determining for each link a set of beyond link devices, wherein each set of beyond link devices includes only devices that are beyond a particular link relative to the management station;

sending a first message to one or more active devices within the network, wherein each first message requests a response to be returned from the device for which the message was sent;

determining a set of non-responding devices within the network based on responses to the first messages, wherein the step of determining a set of non-responding devices within the network includes the step of maintaining an active device bit vector that identifies devices for which a response is expected in response to sending the first messages;

comparing the set of non-responding devices to each set of beyond link devices to identify link failures within the network;

computing a response bit vector, wherein the response vector identifies devices that responded to the first messages;

computing an intermediate bit vector by performing a logical bitwise AND between the active device bit vector and the response bit vector; and

computing a non-response bit vector by performing a logical bitwise exclusive-or (XOR) between the intermediate bit vector and an all ones bit vector, wherein the non-response bit vector identifies all devices for which a response was not received.

8. A computer-readable medium carrying one or more sequences of instructions for identifying link failures in a network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving information that represents a physical topology of the network;

determining a path between a particular network devices and a management station that is associated with the network, wherein the path consists of one or more links that connect devices within the network;

determining, based on whether the particular network device is between one or more devices of the network and the management station, a set of beyond link devices, wherein the set of beyond link devices includes only devices that can communicate with the management station through the particular network device and that cannot communicate with the management station without the particular network device;

sending a first message to one or more active devices within the network, wherein each first message requests a response to be returned from the device for which the message was sent;

determining a set of non-responding devices within the network based on responses to the first messages; and

comparing the set of non-responding devices to the set of beyond link devices to identify link failures within the network.

9. The computer-readable medium as recited in claim 8, wherein the step of sending a first message includes the step of sending an Internet Control Message Protocol (“

ICMP”

) message to one or more devices within the network.

10. The computer-readable medium as recited in claim 8, wherein the step of determining a set of non-responding devices includes the steps of:

sending a second message to devices within the network that did not respond to the first message; and

identifying a particular device as a non-responding device only if the particular device fails to respond to the second message.

11. The computer-readable medium as recited in claim 10, further comprising instructions for performing the step of identifying a set of slow responding devices, wherein the set of slow responding devices includes those devices that responded to the second message from the management station.

12. The computer-readable medium as recited in claim 8, wherein the step of determining a set of non-responding devices within the network includes the step of maintaining an active device bit vector that identifies devices for which a response is expected in response to sending the first messages.

14. The computer-readable medium as recited in claim 8, wherein:

the step of sending a first message to one or more active devices within the network further includes the steps of;

polling one or more devices at a first frequency rate to determine an initial set of non-responding devices; and

polling at a second frequency rate devices within the initial set of non-responding devices to determine a set of slow-responding devices, wherein the first frequency rate and the second frequency rate represent different polling rates; and

the step of determining a set of non-responding devices within the network comprises the step of comparing the initial set of non-responding devices to the set of slow-responding devices to determine the set of non-responding devices.

13. A computer-readable medium carrying one or more sequences of instructions for identifying link failures in a network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving information that represents a physical topology of the network;

determining a path between one or more devices of the network and a management station that is associated with the network, wherein each path consists of one or more links that connects devices within the network;

determining for each link a set of beyond link devices, wherein each set of beyond link devices includes only devices that are beyond a particular link relative to the management station;

sending a first message to one or more active devices within the network, wherein each first message requests a response to be returned from the device for which the message was sent;

determining a set of non-responding devices within the network based on responses to the first messages, wherein the step of determining a set of non-responding devices within the network includes the step of maintaining an active device bit vector that identifies devices for which a response is expected in response to sending the first messages;

comparing the set of non-responding devices to each set of beyond link devices to identify link failures within the network;

computing a response bit vector, wherein the response vector identifies devices that responded to the first messages;

computing an intermediate bit vector by performing a logical bitwise AND between the active device bit vector and the response bit vector; and

computing a non-response bit vector by performing a logical bitwise exclusive-or (XOR) between the intermediate bit vector and an all ones bit vector, wherein the non-response bit vector identifies all devices for which a response was not received.

15. A network device configured for identifying link failures in a network, comprising:

a network interface;

a processor coupled to the network interface and receiving information from the network interface;

a computer-readable medium accessible by the processor and comprising one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of;

receiving information that represents a physical topology of the network;

determining a path between a particular network devices and a management station that is associated with the network, wherein the path consists of one or more links that connect devices within the network;

determining, based on whether the particular network device is between one or more devices of the network and the management station, a set of beyond link devices, wherein the set of beyond link devices includes only devices that can communicate with the management station through the particular network device and that cannot communicate with the management station without the particular network device;

sending a first message to one or more active devices within the network, wherein each first message requests a response to be returned from the device for which the message was sent;

determining a set of non-responding devices within the network based on responses to the first messages; and

comparing the set of non-responding devices to the set of beyond link devices to identify link failures within the network.

16. The network device as recited in claim 15, wherein the step of sending a first message includes the step of sending an Internet Control Message Protocol (“

ICMP”

) message to one or more devices within the network.

17. The network device as recited in claim 15, wherein the step of determining a set of non-responding devices includes the steps of:

sending a second message to devices within the network that did not respond to the first message; and

identifying a particular device as a non-responding device only if the particular device fails to respond to the second message.

18. The network device as recited in claim 17, further configured for performing the step of identifying a set of slow responding devices, wherein the set of slow responding devices includes those devices that responded to the second message from the management station.

19. The network device as recited in claim 15, wherein the step of determining a set of non-responding devices within the network includes the step of maintaining an active device bit vector that identifies devices for which a response is expected in response to sending the first messages.

21. The network device as recited in claim 15, wherein:

the step of sending a first messages one or more active devices within the network further includes the steps of;

polling one or more devices at a first frequency rate to determine an initial set of non-responding devices; and

polling at a second frequency rate devices within the initial set of non-responding devices to determine a set of slow-responding devices, wherein the first frequency rate and the second frequency rate represent different polling rates; and

the step of determining a set of non-responding devices within the network comprises the step of comparing the initial set of non-responding devices to the set of slow-responding devices to determine the set of non-responding devices.

20. A network device configured for identifying link failures in a network, comprising:

a network interface;

a processor coupled to the network interface and receiving information from the network interface;

a computer-readable medium accessible by the processor and comprising one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of;

receiving information that represents a physical topology of the network;

determining a path between one or more devices of the network and a management station that is associated with the network, wherein each path consists of one or more links that connects devices within the network;

determining for each link a set of beyond link devices, wherein each set of beyond link devices includes only devices that are beyond a particular link relative to the management station;

sending a first message to one or more active devices within the network, wherein each first message requests a response to be returned from the device for which the message was sent;

determining a set of non-responding devices within the network based on responses to the first messages, wherein the step of determining a set of non-responding devices within the network includes the step of maintaining an active device bit vector that identifies devices for which a response is expected in response to sending the first messages;

comparing the set of non-responding devices to each set of beyond link devices to identify link failures within the network;

computing a response bit vector, wherein the response vector identifies devices that responded to the first messages;

computing an intermediate bit vector by performing a logical bitwise AND between the active device bit vector and the response bit vector; and

computing a non-response bit vector by performing a logical bitwise exclusive-or (XOR) between the intermediate bit vector and an all ones bit vector, wherein the non-response bit vector identifies all devices for which a,response was not received.

22. A network device configured for identifying link failures in a network, comprising:

means for receiving information that represents a physical topology of the network;

means for determining a path between a particular network device and a management station that is associated with the network, wherein the path consists of one or more links connecting one or more devices within the network;

means for determining, based on whether the particular network device is between one or more devices of the network and the management station, a set of beyond link devices, wherein the set of beyond link devices includes only devices that can communicate with the management station through the particular network device and that cannot communicate with the management station without the particular network device;

means for sending a first message to each active device within the network, wherein each first message requests a response to be returned from the device for which the message was sent;

means for determining a set of non-responding devices within the network based on responses to the first messages; and

means for comparing the set of non-responding devices to the set of beyond link devices to identify link failures within the network.

23. A method for identifying failures of links in a network, the method comprising the computer-implemented steps of:

obtaining information that represents a physical topology of the network;

verifying that the network does not include any redundant paths;

identifying a management station that is associated with the network;

determining a path between a particular network device and the management station, wherein the path consists of one or more links connecting one or more devices within the network;

determining a set of beyond link devices, wherein the set of beyond link devices includes only devices that can communicate with the management station through the particular network device and that cannot communicate with the management station without the particular network device;

polling each active device within the network to determine a set of non-responding devices; and

comparing the set of non-responding devices to the set of beyond link devices to identify link failures within the network.