Predicting route utilization and non-redundant failures in network environments

• US 9,900,244 B2
• Filed: 03/30/2015
• Issued: 02/20/2018
• Est. Priority Date: 02/13/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roy, Sonali, Mortimer, Samuel Joseph
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Ganguly, Sumitra
• Application Number:
  US14/673,806
• Publication Number:
  US 20150207727A1
• Time in Patent Office: 1,058 Days
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 2011/0081 Fault tolerance; Redundancy; Recovery; Reconfigurability
• CPC Class Codes: H04Q 2011/009 Topology aspects

Abstract

A network analysis module may obtain information including but not limited to network traffic and topology information for a network environment including multiple separate networks and physical connections between the networks. The module generates a network topology model including but not limited to extreme-case failure or break information according to the network topology information, and applies the historical network traffic information to the network topology model to predict future expected normal traffic load and extreme-case traffic load for each route over the physical connections between the networks. Output may include one or more reports for each route, each report indicating the historical and predicted traffic levels for both normal and extreme-case scenarios of a respective route.

Claims

1. A method, comprising:

performing, by one or more computing devices;

obtaining historical traffic load data for individual routes of a plurality of routes between a plurality of devices in a network environment, wherein the network environment connects the plurality of devices via a plurality of physical connections, and each individual route of the plurality of routes carries traffic between two devices of the plurality of devices over one or more of the plurality of physical connections between the two devices;

obtaining a topology model of the network environment, wherein the topology model includes, for each particular route of the plurality of routes, an indication of a failure-case according to the topology model, wherein the failure-case for a particular route is a failure in one or more of the plurality of physical connections that causes traffic to be diverted onto the particular route from one or more other routes of the plurality of routes affected by the failure; and

generating, for each particular route of the plurality of routes, a prediction of failure-case traffic load on the particular route given the failure-case for the particular route according to the historical traffic load data for the plurality of routes and the topology model.

2. The method as recited in claim 1, further comprising generating a prediction of normal traffic load for each of the plurality of routes according to the historical traffic load data.

3. The method as recited in claim 1, further comprising, prior to said generating the prediction, performing a statistical analysis of the historical traffic load data to generate historical 99^th percentile (p99) data for each individual route of the plurality of routes, wherein the prediction of failure-case traffic load is generated according to the historical p99 data.

4. The method as recited in claim 1, wherein said generating a prediction of failure-case traffic load comprises:

determining, from the topology model and the historical traffic load data, an amount of historical traffic load that would be diverted from one or more other routes to the particular route given the failure-case;

combining the historical traffic load data for the particular route with the determined amount of historical traffic load that would be diverted to the particular route given the failure-case to produce a combined historical traffic load; and

generating the prediction of failure-case traffic load on the particular route from the combined historical traffic load.

5. The method as recited in claim 4, wherein said generating the prediction of failure-case traffic load on the particular route comprises applying a smoothing function according to an autoregressive integrated moving average (ARIMA) model to the combined historical traffic load.

6. The method as recited in claim 1, wherein said obtaining the topology model of the network environment comprises determining one or more locations in a topology of the network environment at which two or more of the plurality of physical connections are co-located, wherein the failure-case for at least one route is a break at a location of the one or more locations, and wherein the break affects two or more co-located physical connections co-located at the location.

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

simulating two or more breaks at different locations in the topology model that would cause traffic to be diverted onto the particular route;

for each particular break of the simulated breaks;

determining an amount of traffic that would be diverted onto the particular route from one or more other routes given the particular break; and

determining values for one or more route performance metrics according to the determined amount of traffic that would be diverted onto the particular route given the particular break; and

analyzing the values for the one or more route performance metrics for each of the simulated breaks to determine an extreme-case break for the particular route.

8. The method as recited in claim 1, further comprising:

determining that the failure-case for the particular route is an extreme-case break based on an optimization of one or more route performance metrics according to an objective function, wherein the extreme-case break is a break that causes a highest total traffic load on the particular route according to the objective function.

9. A non-transitory computer-accessible storage medium storing program instructions, wherein the program instructions are computer-executable to implement:

obtaining historical traffic load data for individual routes of a plurality of routes between a plurality of devices in a network environment, wherein the network environment connects the plurality of devices via a plurality of physical connections, and each individual route of the plurality of routes carries traffic between two devices of the plurality of devices over one or more of the plurality of physical connections between the two devices;

obtaining a topology model of the network environment, wherein the topology model includes, for each particular route of the plurality of routes, an indication of a failure-case according to the topology model, wherein the failure-case for a particular route is a failure in one or more of the plurality of physical connections that causes traffic to be diverted onto the particular route from one or more other routes of the plurality of routes affected by the failure; and

generating, for each particular route of the plurality of routes, a prediction of failure-case traffic load on the particular route given the failure-case for the particular route according to the historical traffic load data for the plurality of routes and the topology model.

10. The non-transitory computer-accessible storage medium as recited in claim 9, wherein at least one of the plurality of devices is a router of a distinct network in the network environment, the network environment comprising a plurality of networks.

11. The non-transitory computer-accessible storage medium as recited in claim 9, wherein, in said generating a prediction, the program instructions are computer-executable to implement generating the prediction of failure-case traffic load based at least in part on historical traffic load for the particular route combined with an amount of historical traffic load that would be diverted to the particular route from one or more other routes given the failure-case.

12. The non-transitory computer-accessible storage medium as recited in claim 9, wherein the topology model further indicates one or more locations at which two or more of the plurality of physical connections are co-located, wherein the failure-case for at least one route is a break at a location of the one or more locations, and wherein the break affects two or more co-located physical connections at the location.

13. The non-transitory computer-accessible storage medium as recited in claim 9, wherein the failure-case is one of a worst-case break determined according to a maximization of an objective function according to the topology model or a best-case break determined according to a minimization of the objective function according to the topology model.

14. A system, comprising:

one or more hardware computing devices configured to implement a network analysis module configured to;

obtain historical traffic load data for individual routes of a plurality of routes between a plurality of devices, wherein the plurality of devices are connected via a plurality of physical connections, and each individual route of the plurality of routes carries traffic between two devices of the plurality of devices over one or more of the plurality of physical connections between the two devices;

obtain a topology model of the plurality of devices and the plurality of routes between the plurality of devices, wherein the topology model includes, for each particular route of the plurality of routes, an indication of a failure-case according to the topology model, wherein the failure-case for a particular route is a failure in one or more of the plurality of physical connections that causes traffic to be diverted onto the particular route from one or more other routes of the plurality of routes affected by the failure; and

generate, for each particular route of the plurality of routes, a prediction of failure-case traffic load on the particular route given the failure-case for the particular route according to the historical traffic load data for the plurality of routes and the topology model.

15. The system as recited in claim 14, wherein at least one of the plurality of physical connections is a fiber optic connection.

16. The system as recited in claim 14, wherein each of the plurality of physical connections connects a router of one network to a router of another network.

17. The system as recited in claim 14, wherein, to generate the prediction of failure-case traffic load, the network analysis module is further configured to apply a smoothing function according to an autoregressive integrated moving average (ARIMA) model to historical p99 data for the particular route.

18. The system as recited in claim 14, wherein, to generate the prediction of failure-case traffic load, the network analysis module is further configured to generate the prediction of failure-case traffic load on the particular route based at least in part on the historical traffic load for the particular route combined with an amount of historical traffic load that would be diverted to the particular route from one or more other routes given the failure-case.

19. The system as recited in claim 14, wherein the topology model further indicates one or more locations at which two or more of the plurality of physical connections are co-located, and wherein the failure-case for at least one route is a break at a location of the one or more locations, and wherein the break affects two or more co-located physical connections at the location.

20. The system as recited in claim 14, wherein the failure-case break is one of a worst-case break determined according to a maximization of an objective function according to the topology model or a best-case break determined according to a minimization of the objective function according to the topology model.