BINARY SEARCH-BASED APPROACH IN ROUTING-METRIC AGNOSTIC TOPOLOGIES FOR NODE SELECTION TO ENABLE EFFECTIVE LEARNING MACHINE MECHANISMS

• US 20140219078A1
• Filed: 07/19/2013
• Published: 08/07/2014
• Est. Priority Date: 02/05/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Dasgupta, Sukrit, Vasseur, Jean-Philippe, Hui, Jonathan W., Mermoud, Grgory
• Granted Patent: US 9,544,220 B2
• Time in Patent Office: Days
• US Class Current: 370/219
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

In one embodiment, nodes are polled in a network for Quality of Service (QoS) measurements, and a QoS anomaly that affects a plurality of potentially faulty nodes is detected based on the QoS measurements. A path, which traverses the plurality of potentially faulty nodes, is then computed from a first endpoint to a second endpoint. Also, a median node that is located at a point along the path between the first endpoint and the second endpoint is computed. Time-stamped packets are received from the median node, and the first endpoint and the second endpoint of the path are updated based on the received time-stamped packets, such that an amount of potentially faulty nodes is reduced. Then, the faulty node is identified from a reduced amount of potentially faulty nodes.

Claims

1. A method, comprising:

polling nodes in a network for Quality of Service (QoS) measurements;

detecting a QoS anomaly that affects a plurality of potentially faulty nodes based on the QoS measurements, wherein the plurality of potentially faulty nodes includes a faulty node causing the QoS anomaly;

computing a path, which traverses the plurality of potentially faulty nodes, from a first endpoint to a second endpoint, wherein a root node of the network is the first endpoint, and a node of the plurality of potentially faulty nodes is the second endpoint;

computing a median node of the plurality of potentially faulty nodes that is located at a point along the path between the first endpoint and the second endpoint;

receiving time-stamped packets from the median node;

updating the first endpoint and the second endpoint of the path based on the received time-stamped packets, such that an amount of potentially faulty nodes is reduced; and

identifying the faulty node from the reduced amount of potentially faulty nodes.

2. The method according to claim 1, further comprising:

determining whether a new median node that is located at a point along the path between the updated first endpoint and the updated second endpoint exists.

3. The method according to claim 2, further comprising:

when a new median node exists, determining whether the median node is affected by the QoS anomaly based on the received time-stamped packets.

4. The method according to claim 3, wherein:

when the median node is affected by the QoS anomaly, the new median node is located at a point along the path between the root node and the median node, and

when the median node is not affected by the QoS anomaly, the new median node is located at a point along the path between the median node and the deep node.

5. The method according to claim 4, further comprising:

repeating the steps of receiving time-stamped packets from the median node and updating the first endpoint and the second endpoint of the path based on the received time-stamped packets until no new median node exists.

6. The method according to claim 2, wherein when no new median node exists, the faulty node is identified as an endpoint.

7. The method according to claim 1, wherein the point along the path between the first endpoint and the second endpoint is an approximate midway point along the path between the first endpoint and the second endpoint.

8. The method according to claim 1, further comprising:

sending a message to the median node requesting that the median node apply time-stamps to one or more packets.

9. The method according to claim 1, wherein the second endpoint is a deepest node of the plurality of potentially faulty nodes that has one or more child nodes.

10. The method according to claim 1, further comprising:

computing a plurality of paths from the first endpoint to the second endpoint, wherein

when the median node is not affected by the QoS anomaly, the new median node is located at a point along one of the plurality of paths, such that a maximum amount of potentially faulty nodes is reduced.

11. The method according to claim 1, further comprising:

calculating a probabilistic model of QoS measurements corresponding to the plurality of potentially faulty nodes.

12. An apparatus, comprising:

one or more network interfaces that communicate with a network;

a processor coupled to the one or more network interfaces and configured to execute a process; and

a memory configured to store program instructions which contain the process executable by the processor, the process comprising;

polling nodes in the network for Quality of Service (QoS) measurements;

detecting a QoS anomaly that affects a plurality of potentially faulty nodes based on the QoS measurements, wherein the plurality of potentially faulty nodes includes a faulty node causing the QoS anomaly;

computing a path, which traverses the plurality of potentially faulty nodes, from a first endpoint to a second endpoint, wherein a root node of the network is the first endpoint, and a node of the plurality of potentially faulty nodes is the second endpoint;

computing a median node of the plurality of potentially faulty nodes that is located at a point along the path between the first endpoint and the second endpoint;

receiving time-stamped packets from the median node;

updating the first endpoint and the second endpoint of the path based on the received time-stamped packets, such that an amount of potentially faulty nodes is reduced; and

identifying the faulty node from the reduced amount of potentially faulty nodes.

13. The apparatus according to claim 12, wherein the process further comprises:

determining whether a new median node that is located at a point along the path between the updated first endpoint and the updated second endpoint exists.

14. The apparatus according to claim 13, wherein the process further comprises:

when a new median node exists, determining whether the median node is affected by the QoS anomaly based on the received time-stamped packets.

15. The apparatus according to claim 14, wherein:

when the median node is affected by the QoS anomaly, the new median node is located at a point along the path between the root node and the median node, and

when the median node is not affected by the QoS anomaly, the new median node is located at a point along the path between the median node and the deep node.

16. The apparatus according to claim 15, wherein the process further comprises:

repeating the steps of receiving time-stamped packets from the median node and updating the first endpoint and the second endpoint of the path based on the received time-stamped packets until no new median node exists.

17. The apparatus according to claim 13, wherein when no new median node exists, the faulty node is identified as an endpoint.

18. The apparatus according to claim 12, wherein the point along the path between the first endpoint and the second endpoint is an approximate midway point along the path between the first endpoint and the second endpoint.

19. The apparatus according to claim 12, wherein the process further comprises:

sending a message to the median node requesting that the median node apply time-stamps to one or more packets.

20. The apparatus according to claim 12, wherein the second endpoint is a deepest node of the plurality of potentially faulty nodes that has one or more child nodes.

21. The apparatus according to claim 12, wherein the process further comprises:

computing a plurality of paths from the first endpoint to the second endpoint, wherein

when the median node is not affected by the QoS anomaly, the new median node is located at a point along one of the plurality of paths, such that a maximum amount of potentially faulty nodes is reduced.

22. The apparatus according to claim 12, wherein the process further comprises:

calculating a probabilistic model of QoS measurements corresponding to the plurality of potentially faulty nodes.

23. A tangible non-transitory computer readable medium storing program instructions that cause a computer to execute a process, the process comprising:

polling nodes in a network for Quality of Service (QoS) measurements;

detecting a QoS anomaly that affects a plurality of potentially faulty nodes based on the QoS measurements, wherein the plurality of potentially faulty nodes includes a faulty node causing the QoS anomaly;

computing a path, which traverses the plurality of potentially faulty nodes, from a first endpoint to a second endpoint, wherein a root node of the network is the first endpoint, and a node of the plurality of potentially faulty nodes is the second endpoint;

computing a median node of the plurality of potentially faulty nodes that is located at a point along the path between the first endpoint and the second endpoint;

receiving time-stamped packets from the median node;

updating the first endpoint and the second endpoint of the path based on the received time-stamped packets, such that an amount of potentially faulty nodes is reduced; and

identifying the faulty node from the reduced amount of potentially faulty nodes.