Predicting route utilization and non-redundant failures in network environments

• US 8,995,249 B1
• Filed: 02/13/2013
• Issued: 03/31/2015
• 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): ROBERTS, BRIAN S
• Application Number:
  US13/766,674
• Time in Patent Office: 776 Days
• Field of Search: None
• US Class Current: 370/216
• 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;

collecting traffic load data as historical traffic load data for each of a plurality of routes in a network environment comprising a plurality of distinct networks, wherein each route carries traffic between two of the networks over one or more physical connections, wherein each physical connection connects a router of one of the networks to a router of another one of the networks;

generating a topology model of the network environment, wherein the topology model includes the networks, the physical connections between the networks, and the routes between the networks over the physical connections;

analyzing the topology model to determine an extreme-case break for each route in the topology model in the network environment, wherein a break for a given route is a break in one or more of the physical connections that causes traffic to be diverted onto the given route from one or more other routes affected by the break, and wherein the extreme-case break for the given route is a particular break for which an objective function characterizing one or more route performance metrics is optimized; and

generating, for each route, a prediction of extreme-case traffic load on the respective route given the extreme-case break for the respective route according to the collected historical traffic load data for the routes and the topology model.

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

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

4. The method as recited in claim 1, wherein generating a prediction of extreme-case traffic load on a route given the extreme-case break for the respective route comprises:

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

combining the historical traffic load data for the route with the determined amount of historical traffic load that would be diverted to the route given the extreme-case break for the route; and

generating the prediction of extreme-case traffic load on the route from the combined historical traffic load for the route.

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

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

7. The method as recited in claim 1, wherein said analyzing the topology model to determine an extreme-case break in the topology model for each route in the network environment comprises, for each route:

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

for each simulated break;

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

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

8. The method as recited in claim 1, wherein the one or more route performance metrics include total traffic load on a route given a break, and wherein the extreme-case break for a given route is a break that causes a highest total traffic load on the given 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 each of a plurality of routes between a plurality of devices, wherein each route carries traffic between two of the devices over one or more physical connections between the devices;

obtaining a topology model of the devices and the routes between the devices, wherein the topology model includes, for each route, an indication of an extreme-case break according to the topology model, wherein an extreme-case break for a given route is a particular break in one or more of the physical connections for which an objective function characterizing one or more route performance metrics is optimized; and

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

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

11. The non-transitory computer-accessible storage medium as recited in claim 9, wherein the program instructions are further computer-executable to implement generating a prediction of normal traffic load on each route according to the historical traffic load data for the respective route.

12. The non-transitory computer-accessible storage medium as recited in claim 9, wherein the program instructions are further computer-executable to implement generating 99^th percentile (p99) data for each route according to the historical traffic load data for the respective route, wherein the predictions of extreme-case traffic load for the routes are generated according to the p99 data for the routes.

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

14. The non-transitory computer-accessible storage medium as recited in claim 13, wherein, in said generating a prediction of extreme-case traffic load on a route given the extreme-case break for the respective route, the program instructions are computer-executable to implement applying a smoothing function to the combined historical traffic load for the route.

15. 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 physical connections are co-located, and wherein the extreme-case break for at least one route is a break at a location at which two or more of the physical connections are co-located according to the topology model, wherein the break affects the two or more co-located physical connections.

16. The non-transitory computer-accessible storage medium as recited in claim 9, wherein the extreme-case break is one of a worst-case break determined according to a maximization of the objective function and a best-case break determined according to a minimization of the objective function.

17. A system, comprising:

one or more processors; and

a memory comprising program instructions, wherein the program instructions are executable by at least one of the one or more processors to implement a network analysis module operable to;

collect historical traffic load data for each of a plurality of routes between a plurality of networks, wherein each route carries traffic between two of the networks over one or more physical connections;

generate a topology model of the plurality of networks and the plurality of routes, wherein the topology model includes, for each route, an indication of an extreme-case break according to the topology model, wherein an extreme-case break for a given route is a break in one or more of the physical connections for which an objective function characterizing one or more route performance metrics is optimized; and

generate, for each route, a prediction of extreme-case traffic load on the respective route given the extreme-case break for the respective route according to the historical traffic load data for the routes and the topology model; and

output, for each route, a report indicating the prediction of extreme-case traffic load on the respective route given the extreme-case break for the respective route.

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

19. The system as recited in claim 17, wherein each physical connection connects a router of one of the networks to a router of another one of the networks.

20. The system as recited in claim 17, wherein the network analysis module is further operable to generate a prediction of normal traffic load on each route according to 99^th percentile (p99) data calculated from the historical traffic load data for the respective route.

21. The system as recited in claim 17, wherein the network analysis module is further operable to generate 99^th percentile (p99) data for each route according to the historical traffic load data for the respective route, wherein the predictions of extreme-case traffic load for the routes are generated according to the p99 data for the routes.

22. The system as recited in claim 21, wherein, to generate the predictions of extreme-case traffic load on the routes given the extreme-case breaks for the routes, the program instructions are executable by at least one of the one or more processors to apply a smoothing function according to an autoregressive integrated moving average (ARIMA) model to the historical p99 data for the routes.

23. The system as recited in claim 17, wherein, to generate a prediction of extreme-case traffic load on a route given the extreme-case break for the respective route, the network analysis module is operable to generate the prediction of extreme-case traffic load on the route from historical traffic load for the route combined with an amount of historical traffic load that would be diverted to the route from one or more other routes given the extreme-case break for the route.

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

25. The system as recited in claim 17, wherein the extreme-case break is one of a worst-case break determined according to a maximization of the objective function and a best-case break determined according to a minimization of the objective function.