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

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.