Learning end-to-end delays in computer networks from sporadic round-trip delay probing

• US 9,491,076 B2
• Filed: 01/27/2014
• Issued: 11/08/2016
• Est. Priority Date: 01/06/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Mermoud, Grgory, Vasseur, Jean-Philippe, Dasgupta, Sukrit
• Primary Examiner(s): KHIRODHAR, MAHARISHI V
• Application Number:
  US14/164,781
• Publication Number:
  US 20150195171A1
• Time in Patent Office: 1,016 Days
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports

Abstract

In one embodiment, periodic round-trip probes are executed in a network, whereby a packet is transmitted along a particular communication path from a source to a destination and back to the source. Statistical information relating to the round-trip probes is gathered, and a transmission delay of the round-trip probes is calculated based on the gathered statistical information. Also, an end-to-end transmission delay along an arbitrary communication path in the network is estimated based on the calculated transmission delay of the round-trip probes.

Claims

1. A method, comprising:

sending, by a device in a network, periodic round-trip probes in the network, wherein a packet is transmitted along a particular communication path from a source to a destination and back to the source;

gathering, by the device, statistical information relating to the round-trip probes;

calculating, by the device, a transmission delay of the round-trip probes based on the gathered statistical information; and

estimating, by a learning machine algorithm executing on the device, an end-to-end transmission delay along any arbitrary communication path in the network, even communication paths which have not been probed, based on the calculated transmission delay of the round-trip probes.

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

estimating a transmission delay of an arbitrary communication link in the arbitrary communication path based on the calculated transmission delay of the round-trip probes, wherein the arbitrary communication path is composed of one or more communication links.

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

obtaining time-stamps from packets in the network; and

estimating a one-way transmission delay along an arbitrary communication path in the network based on the calculated transmission delay of the round-trip probes and the obtained time-stamps.

4. The method as in claim 1, wherein the learning machine algorithm is a learning machine-based link-wise estimation algorithm.

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

measuring a real transmission delay in the network; and

refining the estimation algorithm based on the measured real transmission delay.

6. The method as in claim 4, wherein the estimation algorithm uses an expectation-maximization scheme and an underlying regression model.

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

sending a probe to one or more nodes in the network, the probe causing the one or more nodes to report a measured transmission delay local to the one or more nodes.

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

defining a schedule by which the one or more nodes report the measured transmission delay.

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

determining a node of the one or more nodes that is important in relation to the one or more nodes based on an amount of information available to the node; and

sending a first probe to the node that is important.

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

defining a trigger mechanism which, when satisfied, cause the probe to be sent to a particular node of the one or more nodes; and

in response to the trigger mechanism being satisfied, sending the probe to the particular node.

11. 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;

executing periodic round-trip probes in the network, whereby a packet is transmitted along a particular communication path from a source to a destination and back to the source;

gathering statistical information relating to the round-trip probes;

calculating a transmission delay of the round-trip probes based on the gathered statistical information; and

estimating, via a learning machine algorithm, an end-to-end transmission delay along any arbitrary communication path in the network, even communication paths which have not been probed, based on the calculated transmission delay of the round-trip probes.

12. The apparatus as in claim 11, wherein the process further comprises:

estimating a transmission delay of an arbitrary communication link in the arbitrary communication path based on the calculated transmission delay of the round-trip probes, wherein the arbitrary communication path is composed of one or more communication links.

13. The apparatus as in claim 11, wherein the process further comprises:

obtaining time-stamps from packets in the network; and

estimating a one-way transmission delay along an arbitrary communication path in the network based on the calculated transmission delay of the round-trip probes and the obtained time-stamps.

14. The apparatus as in claim 11, wherein the learning machine algorithm is a learning machine-based link-wise estimation algorithm.

15. The apparatus as in claim 14, wherein the process further comprises:

measuring a real transmission delay in the network; and

refining the estimation algorithm based on the measured real transmission delay.

16. The apparatus as in claim 14, wherein the estimation algorithm uses an expectation-maximization scheme and an underlying regression model.

17. The apparatus as in claim 11, wherein the process further comprises:

sending a probe to one or more nodes in the network, the probe causing the one or more nodes to report a measured transmission delay local to the one or more nodes.

18. The apparatus as in claim 17, wherein the process further comprises:

defining a schedule by which the one or more nodes report the measured transmission delay.

19. The apparatus as in claim 17, wherein the process further comprises:

determining a node of the one or more nodes that is important in relation to the one or more nodes based on an amount of information available to the node; and

sending a first probe to the node that is important.

20. The apparatus as in claim 17, wherein the process further comprises:

defining a trigger mechanism which, when satisfied, cause the probe to be sent to a particular node of the one or more nodes; and

in response to the trigger mechanism being satisfied, sending the probe to the particular node.

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

executing periodic round-trip probes in a network, whereby a packet is transmitted along a particular communication path from a source to a destination and back to the source;

gathering statistical information relating to the round-trip probes;

calculating a transmission delay of the round-trip probes based on the gathered statistical information; and

estimating, via a learning machine algorithm, an end-to-end transmission delay along any arbitrary communication path in the network, even communication paths which have not been probed, based on the calculated transmission delay of the round-trip probes.