Distributed predictive routing using delay predictability measurements

Patent metadata

Field	Value
Publication number	US-9525617-B2
Application number	US-201414268627-A
Country	US
Kind code	B2
Filing date	May 2, 2014
Priority date	May 2, 2014
Publication date	Dec 20, 2016
Grant date	Dec 20, 2016

Abstract

In one embodiment, a method is disclosed in which a device receives delay information for a communication segment in a network. The device determines a predictability measurement for delays along the segment using the received delay information. The predictability measurement is advertised to one or more devices in the network and used as a routing constraint to select a routing path in the network.

First claim

What is claimed is:

1. A method, comprising:
receiving, at a network interface of a device in a computer network, delay information for a communication segment in the network;
determining, by a machine learning process on the device, a predictability measurement for delays along the segment using the received delay information;
advertising, via the network interface of the device, the predictability measurement to one or more other machine learning processes on one or more other devices in the network; and
using, by the device, the predictability measurement as a routing constraint to select a routing path in the network.

2. The method as in claim 1 , further comprising:
generating a probability distribution function using the delay information, wherein the predictability measurement is based on the probability distribution function.

3. The method as in claim 2 , further comprising:
calculating the predictability measurement as an entropy measurement of the probability distribution function.

4. The method as in claim 2 , further comprising:
calculating the predictability measurement as a vector that includes two or more of: a mean, variance, skewness, kurtosis, or Sarle's coefficient of the probability distribution function.

5. The method as in claim 2 , wherein the probability distribution function is a cumulative distribution function or a probability density function.

6. The method as in claim 2 , further comprising:
providing the probability distribution function to another device that calculates a delay predictability measurement using the distribution function.

7. The method as in claim 1 , further comprising:
identifying a set of communication paths to neighboring devices, wherein the neighboring devices are configured to determine delay predictability measurements; and
determining delay predictability measurements for the communication paths.

8. The method as in claim 7 , further comprising:
determining a delay predictability measurement for a particular communication link by analyzing delay information for two or more overlapping paths in the set.

9. The method as in claim 7 , further comprising:
pruning a path from the set of communication paths based on a determination that the set includes a shorter communication path to a destination of the pruned path.

10. The method as in claim 1 , further comprising:
generating a routing topology that optimizes delay predictability measurements.

11. The method as in claim 10 , further comprising:
selecting the routing topology from among a plurality of routing topologies based on the delay predictability measurements associated with the selected topology; and
using the selected topology to route data.

12. An apparatus, comprising:
one or more network interfaces to communicate with a 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:
receive delay information for a communication segment in the network;
determine, by a machine learning process operating on the processor, a predictability measurement for delays along the segment using the received delay information;
advertise the predictability measurement to one or more other machine learning processes on one or more other devices in the network; and
use the predictability measurement as a routing constraint to select a routing path in the network.

13. The apparatus as in claim 12 , wherein the process when executed is further operable to:
generate a probability distribution function using the delay information, wherein the predictability measurement is based on the probability distribution function.

14. The apparatus as in claim 13 , wherein the process when executed is further operable to:
calculate the predictability measurement as an entropy measurement of the probability distribution function.

15. The apparatus as in claim 14 , wherein the probability distribution function is a cumulative distribution function or a probability density function.

16. The apparatus as in claim 13 , wherein the process when executed is further operable to:
calculate the predictability measurement as a vector that includes two or more of: a mean, variance, skewness, kurtosis, or Sarle's coefficient of the probability distribution function.

17. The apparatus as in claim 12 , wherein the process when executed is further operable to:
provide the probability distribution function to another device that calculates a delay predictability measurement using the distribution function.

18. The apparatus as in claim 12 , wherein the process when executed is further operable to:
identify a set of communication paths to neighboring devices, wherein the neighboring devices are configured to determine delay predictability measurements; and
determine delay predictability measurements for the communication paths.

19. The apparatus as in claim 12 , wherein the process when executed is further operable to:
prune a path from the set of communication paths based on a determination that the set includes a shorter communication path to a destination of the pruned path.

20. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:
receive delay information for a communication segment in a network;
determine, by a machine learning process, a predictability measurement for delays along the segment using the received delay information;
advertise the predictability measurement to one or more other machine learning processes on one or more other devices in the network; and
use the predictability measurement as a routing constraint to select a routing path in the network.

Assignees

• Cisco Tech Inc

Inventors

• Vasseur Jean-Philippe
• Mermoud Grégory
• Bouchacourt Diane

Classifications

• H04L45/124 Primary

  using a combination of metrics · CPC title

• H04L45/121 Primary

  by minimising delays · CPC title

• H04L45/44

  Distributed routing · CPC title

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04L43/0852

  Delays · CPC title