LEARNING END-TO-END DELAYS IN COMPUTER NETWORKS FROM SPORADIC ROUND-TRIP DELAY PROBING

• US 20150195171A1
• Filed: 01/27/2014
• Published: 07/09/2015
• 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
• Granted Patent: US 9,491,076 B2
• Time in Patent Office: 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:

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 an end-to-end transmission delay along an arbitrary communication path in the network 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 estimating of the end-to-end transmission delay is performed according to an 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 respective node.

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 of relative importance based on an amount of information available to the node; and

sending a first probe to the node of relative importance.

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. The method as in claim 1, wherein the estimating of the end-to-end transmission delay is performed by a learning machine (LM).

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;

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 an end-to-end transmission delay along an arbitrary communication path in the network based on the calculated transmission delay of the round-trip probes.

13. The apparatus as in claim 12, 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.

14. The apparatus as in claim 12, 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.

15. The apparatus as in claim 12, wherein the estimating of the end-to-end transmission delay is performed according to an estimation algorithm.

16. The apparatus as in claim 15, 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.

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

18. The apparatus as in claim 12, 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 respective node.

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

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

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

determining a node of the one or more nodes of relative importance based on an amount of information available to the node; and

sending a first probe to the node of relative importance.

21. The apparatus as in claim 18, 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.

22. The apparatus as in claim 12, wherein the apparatus is a learning machine (LM).

23. 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 an end-to-end transmission delay along an arbitrary communication path in the network based on the calculated transmission delay of the round-trip probes.