Troubleshooting routing topology based on a reference topology

• US 9,106,555 B2
• Filed: 01/25/2012
• Issued: 08/11/2015
• Est. Priority Date: 01/25/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, Kumar, Ajay
• Primary Examiner(s): Mills, Donald
• Assistant Examiner(s): Baron, Henry
• Application Number:
  US13/358,217
• Publication Number:
  US 20130191688A1
• Time in Patent Office: 1,294 Days
• Field of Search: 370/254, 370/252, 370/256, 709/242
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0873 Checking configuration conflicts between network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

In one embodiment, a computing device (e.g., border router or network management server) transmits a discovery message into a computer network, such as in response to a given trigger. In response to the discovery message, the device receives a unicast reply from each node of a plurality of nodes in the computer network, each reply having a neighbor list of a corresponding node and a selected parent node for the corresponding node. Based on the neighbor lists from the replies and a routing protocol shared by each of the plurality of nodes in the computer network, the device may create a reference topology for the computer network, and based on the selected parent nodes from the replies, may also determine a current topology of the computer network. Accordingly, the device may then compare the current topology to the reference topology to detect anomalies in the current topology.

Claims

1. A method, comprising:

transmitting, from a computing device in a computer network, a discovery message into the computer network;

receiving, in response to the discovery message, a unicast reply from each node of a plurality of nodes in the computer network, each reply having a neighbor list of a corresponding node and a parent node for the corresponding node;

creating a reference topology for the computer network based on the neighbor lists from the replies and a routing protocol shared by each of the plurality of nodes in the computer network, wherein the reference topology represents an ideal topology that should have been computed by the computer network when the plurality of nodes in the computer network are functioning properly;

determining a current topology of the computer network based on the selected parent nodes from the replies, wherein the current topology is an actual topology that is currently computed for the computer network; and

comparing the current topology to the reference topology to detect anomalies in the current topology.

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

detecting an anomaly in the current topology as a malformed topology having one or more incorrectly selected parent nodes.

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

detecting an anomaly in the current topology as a loop within the current topology.

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

detecting an anomaly in the current topology as an incomplete topology having one or more non-participating nodes of the plurality of nodes of the computer network.

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

attempting to correct a detected anomaly; and

reporting an anomaly status to a central management device.

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

determining an inability to correct a detected anomaly; and

reporting an anomaly status to a central management device.

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

receiving one or more updated replies from one or more nodes of the computer network, the one or more updated replies having at least one of either an updated neighbor list of a corresponding node or an updated selected parent node for the corresponding node; and

recreating the reference topology, redetermining the current topology, and recomparing the reference topology and current topology.

8. The method as in claim 1, wherein each reply further has at least one metric selected from:

link costs, link constraints, and link statistics.

9. The method as in claim 1, wherein each reply is piggybacked in a routing protocol control plane message.

10. The method as in claim 1, wherein the discovery message is piggybacked in a routing protocol control plane discovery message.

11. The method as in claim 1, wherein one or more replies further have a selected alternate parent node for the corresponding node.

12. The method as in claim 1, wherein the computing device is one of either a border router of the computer network or a network management server (NMS) for the computer network.

13. An apparatus, comprising:

one or more network interfaces to communicate with 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;

transmit a discovery message into the computer network;

receive, in response to the discovery message, a unicast reply from each node of a plurality of nodes in the computer network, each reply having a neighbor list of a corresponding node and a parent node for the corresponding node;

create a reference topology for the computer network based on the neighbor lists from the replies and a routing protocol shared by each of the plurality of nodes in the computer network, wherein the reference topology represents an ideal topology that should have been computed by the computer network when the plurality of nodes in the computer network are functioning properly;

determine a current topology of the computer network based on the selected parent nodes from the replies, wherein the current topology is an actual topology that is currently computed for the computer network; and

compare the current topology to the reference topology to detect anomalies in the current topology.

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

detect an anomaly in the current topology as a malformed topology having one or more incorrectly selected parent nodes.

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

detect an anomaly in the current topology as a loop within the current topology.

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

detect an anomaly in the current topology as an incomplete topology having one or more non-participating nodes of the plurality of nodes of the computer network.

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

attempt to correct a detected anomaly; and

report an anomaly status to a central management device.

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

determine an inability to correct a detected anomaly; and

report an anomaly status to a central management device.

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

receive one or more updated replies from one or more nodes of the computer network, the one or more updated replies having at least one of either an updated neighbor list of a corresponding node or an updated selected parent node for the corresponding node; and

recreate the reference topology, redetermine the current topology, and recompare the reference topology and current topology.

20. The apparatus as in claim 13, wherein each reply further has at least one metric selected from:

link costs, link constraints, and link statistics.

21. A system, comprising:

a plurality of nodes of a computer network configured to participate in generating a current routing topology; and

a border router configured to transmit a discovery message into the computer network;

the plurality of nodes further configured to transmit, in response to receiving the discovery message, a unicast reply to the border router, the reply having a neighbor list of a corresponding node and a parent node for the corresponding node;

the border router further configured to receive the replies, create a reference topology for the computer network based on the neighbor lists from the replies and a routing protocol shared by each of the plurality of nodes in the computer network, determine a current topology of the computer network based on the selected parent nodes from the replies, and compare the current topology to the reference topology to detect anomalies in the current topology,

wherein the reference topology represents an ideal topology that should have been computed and the current topology is an actual topology that has been computed by the computer network when the plurality of nodes in the computer network are functioning properly, and

wherein the current topology is an actual topology that is currently computed for the computer network.