Network path selection

• US 10,462,042 B2
• Filed: 06/20/2017
• Issued: 10/29/2019
• Est. Priority Date: 06/20/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bajaj, Sandeep
• Primary Examiner(s): Nguyen, Phuoc H
• Application Number:
  US15/628,545
• Publication Number:
  US 20180367445A1
• Time in Patent Office: 861 Days
• Field of Search: 709224, 709227
• CPC Class Codes: H04L 41/0859 by keeping history of different configuration generations or by rolling back to previous configuration versions
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• 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 41/5051 Service on demand, e.g. definition and deployment of services in real time
• CPC Class Codes: H04L 41/5077 wherein the managed service relates to simple transport services, i.e. providing only network infrastructure
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

A method may include monitoring a network performance metric for multiple paths to a destination through a network, and storing historical performance data for the paths. The method may also include receiving a data flow directed to the destination, where the data flow may be subject to a network performance agreement. The method may additionally include determining aggregate historical performances for the paths, and comparing the aggregate historical performances for the paths. The method may also include, based on the comparison of the aggregate historical performances, routing the data flow through the network.

Claims

1. A method comprising:

monitoring one or more network performance metrics for a first path to a destination through a network and a second path to the destination through the network;

storing historical performance data of the network performance metrics of the first path and the second path;

receiving a data flow directed to the destination, the data flow subject to a network performance agreement based on at least one of the network performance metrics;

determining that a first aggregate historical performance is higher than a second aggregate historical performance, the first aggregate historical performance based on the stored historical performance data of the first path and the second aggregate historical performance based on the stored historical performance data of the second path;

based on the first aggregate historical performance being higher than the second aggregate historical performance, routing the data flow along the first path;

determining whether the first path and the second path satisfy the network performance agreement;

wherein determining that the first aggregate historical performance is higher than the second aggregate historical performance is performed in response to both the first path and the second path satisfying the network performance agreement; and

wherein determining that the first aggregate historical performance is higher than the second aggregate historical performance is performed in response to both the first path and the second path not satisfying the network performance agreement.

2. The method of claim 1, wherein the first aggregate historical performance is based on a duration of time that the at least one of the network performance metrics of the first path was below a threshold performance metric.

3. The method of claim 1, wherein the first aggregate historical performance is based on a number of times for a given duration of time that the at least one of the network performance metrics of the first path dropped below a threshold performance metric.

4. The method of claim 1, wherein the first aggregate historical performance is based on a first network provider of the first path and the second aggregate historical performance is based on a second network provider of the second path.

5. The method of claim 4, wherein the first aggregate historical performance is based on performance of other paths in the network of the first network provider and the second aggregate historical performance is based on performance of other paths in the network of the second network provider.

6. The method of claim 1, wherein the aggregate historical performance is determined using a machine learning algorithm.

7. The method of claim 1, further comprising periodically sending a message along the first path to measure the one or more network performance metrics of the first path.

8. A system, comprising:

a destination network device;

a routing network device, the destination network device reachable from the routing network device over a first path and a second path through a network, the routing network device comprising;

one or more non-transitory computer readable media storing instructions; and

one or more processors configured to execute the instructions to cause the system to perform operations, the operations comprising;

monitor one or more network performance metrics for the first path and the second path;

store historical performance data of the network performance metrics of the first path and the second path in the one or more non-transitory computer readable media;

receive a data flow directed to the destination network device, the data flow subject to a network performance agreement based on at least one of the network performance metrics;

determine that a first aggregate historical performance is higher than a second aggregate historical performance, the first aggregate historical performance based on the stored historical performance data of the first path and the second aggregate historical performance based on the stored historical performance data of the second path;

based on the first aggregate historical performance being higher than the second aggregate historical performance, route the data flow along the first path;

determining whether the first path and the second path satisfy the network performance agreement;

wherein determining that the first aggregate historical performance is higher than the second aggregate historical performance is performed in response to both the first path and the second path satisfying the network performance agreement; and

wherein determining that the first aggregate historical performance is higher than the second aggregate historical performance is performed in response to both the first path and the second path not satisfying the network performance agreement.

9. The system of claim 8, wherein the first aggregate historical performance is based on a duration of time that the at least one of the network performance metrics of the first path was below a threshold performance metric.

10. The system of claim 8, wherein the first aggregate historical performance is based on a number of times for a given duration of time that the at least one of the network performance metrics of the first path dropped below a threshold performance metric.

11. The system of claim 8, wherein the first aggregate historical performance is based on a first network provider of the first path and the second aggregate historical performance is based on a second network provider of the second path.

12. The system of claim 11, wherein the first aggregate historical performance is based on performance of other paths in the network of the first network provider and the second aggregate historical performance is based on performance of other paths in the network of the second network provider.

13. The system of claim 8, wherein the aggregate historical performance is determined using a machine learning algorithm.

14. The system of claim 8, the operations further comprising periodically send a message along the first path to measure the one or more network performance metrics of the first path.

15. A method comprising:

monitoring a network performance metric for a plurality of paths to a destination through a network;

storing historical performance data for the plurality of paths;

receiving a data flow directed to the destination, the data flow subject to a network performance agreement;

determining aggregate historical performances for the plurality of paths;

comparing the aggregate historical performances for the plurality of paths;

based on the comparison of the aggregate historical performances, routing the data flow through the network;

determining whether the first path and the second path satisfy the network performance agreement;

wherein determining that the first aggregate historical performance is higher than the second aggregate historical performance is performed in response to both the first path and the second path satisfying the network performance agreement; and

wherein determining that the first aggregate historical performance is higher than the second aggregate historical performance is performed in response to both the first path and the second path not satisfying the network performance agreement.

16. The method of claim 15, further comprising:

determining whether the plurality of paths satisfy the network performance agreement,

wherein comparing the aggregate historical performances for the plurality of paths is performed in response to one of;

at least two of the plurality of paths satisfying the network performance agreement, or

at least two of the plurality of paths not satisfying the network performance agreement.

17. The method of claim 15, wherein the aggregate historical performance of a given path of the plurality of paths is based on at least one of:

a duration of time that the network performance metric of the given path was below a threshold performance metric, and a number of times for a given duration of time that the network performance metric of the given path dropped below a threshold performance metric.

18. The method of claim 15, wherein the first aggregate historical performance is based on a plurality of network providers of the plurality of paths.