NETWORK STOCHASTIC CROSS-LAYER OPTIMIZATION FOR MEETING TRAFFIC FLOW AVAILABILITY TARGET AT MINIMUM COST

• US 20170012856A1
• Filed: 10/26/2015
• Published: 01/12/2017
• Est. Priority Date: 07/09/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Albrecht, Christoph, Koley, Bikash, Zhao, Xiaoxue, Danna, Emilie Jeanne Anne, Ahuja, Satyajeet Singh, Dangui, Vinayak
• Granted Patent: US 9,722,912 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2111/08 Probabilistic or stochastic CAD
• CPC Class Codes: G06F 2117/06 Spare resources, e.g. for permanent fault suppression
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04W 16/18 Network planning tools

Abstract

The present disclosure describes system and methods for network planning. The systems and methods can incorporate network traffic demands, availability requirements, latency, physical infrastructure and networking device capability, and detailed cost structures to calculate a network design with minimum or reduced cost compared to conventional methods. In some implementations, the method include providing an initial, deterministic set of failures, and then successively performing a network optimization and a network availability simulation to determine which failures most impact the performance of the network model. The high impact failures can then be provided back into the system, which generates an improved network design while still maintaining minimum cost.

Claims

1. A method for designing a network, the method comprising:

generating a minimum monetary cost network model capable of satisfying a traffic demand and responsive to a set of variables each defining one of a network cost, a physical layer feature, or a logical layer feature, a set of constraints defining a relationship between at least two variables from the set of variables, and an objective to reduce the monetary cost of a network defined by the minimum monetary cost network model;

generating an optimization set of network failures F_o;

iteratively, until the current minimum monetary cost network satisfies the traffic demands given a random set of failures F_R;

updating the minimum monetary cost network model capable of satisfying the traffic demand given F_o and generated responsive to the set of variables, the set of constraints, and the objective to reduce the monetary cost of the network;

generating a random set of failures F_R;

determining whether the minimum cost monetary network model satisfies the traffic demand given F_R;

in response to determining that the minimum cost network does not satisfy the traffic demands given F_R, selecting a subset of failures from F_R and adding the subset of failures from F_R to F_o; and

in response to determining that the minimum cost network satisfies the traffic demands given F_R, outputting the current minimum cost network model.

2. The method of claim 1, further comprising generating and updating the minimum monetary cost network model with a linear program.

3. The method of claim 1, further comprising generating and updating the minimum monetary cost network model with a mixed-integer-linear program.

4. The method of claim 1, wherein F_R is generated by identifying failures based on independent random variables associated with each of a plurality of potential failures.

5. The method of claim 1, further comprising determining an impact metric for each failure in F_R.

6. The method of claim 5, wherein each failure of the subset of failures has an impact metric above a predetermined threshold.

7. The method of claim 1, further comprising updating the minimum monetary cost network model to satisfy an additional set of traffic demands given F_o.

8. The method of claim 1, further comprising:

identifying a local backup path for each of traffic demands given a set of network failures F_t; and

updating the minimum monetary cost network model capable of satisfying the traffic demands when the traffic demands traverse their respective local backup path.

9. A system comprising a computer readable medium storing processor executable instructions and a least one processor, wherein execution of the processor executable instructions cause the at least one processor to:

generate a minimum monetary cost network model capable of satisfying a traffic demand and responsive to a set of variables each defining one of a network cost, a physical layer feature, or a logical layer feature, a set of constraints defining a relationship between at least two variables from the set of variables, and an objective to reduce the monetary cost of a network defined by the minimum monetary cost network model;

generate an optimization set of network failures F_o;

iteratively, until the current minimum monetary cost network satisfies the traffic demands given a random set of failures F_R;

update the minimum monetary cost network model capable of satisfying the traffic demand given F_o and generated responsive to the set of variables, the set of constraints, and the objective to reduce the monetary cost of the network;

generate a random set of failures F_R;

determine whether the minimum cost monetary network model satisfies the traffic demand given F_R;

in response to determining that the minimum cost network does not satisfy the traffic demands given F_R, select a subset of failures from F_R and add the subset of failures from F_R to F_O; and

in response to determining that the minimum cost network satisfies the traffic demands given F_R, output the current minimum cost network model.

10. The system of claim 9, wherein execution of the processor executable instructions further causes the at least one processor to generate and update the minimum monetary cost network model with a linear program.

11. The system of claim 9, wherein execution of the processor executable instructions further causes the at least one processor to generate and update the minimum monetary cost network model with a mixed-integer-linear program.

12. The system of claim 9, wherein F_R is generated with a Monte Carlo simulation.

13. The system of claim 9, wherein execution of the processor executable instructions further causes the at least one processor to determine an impact metric for each failure in F_R.

14. The system of claim 13, wherein each failure of the subset of failures has an impact metric above a predetermined threshold.

15. The system of claim 9, wherein execution of the processor executable instructions further causes the at least one processor to update the minimum monetary cost network model to satisfy an additional set of traffic demands given F_o.

16. The system of claim 15, wherein execution of the processor executable instructions further causes the at least one processor to:

identify a backup path for each of traffic demands given a set of network failures F_t; and

update the minimum monetary cost network model capable of satisfying the traffic demands when the traffic demands traverse their respective backup path.

17. A computer readable medium storing processor executable instructions thereon, wherein execution of the processor executable instructions cause a processor to:

generate a minimum monetary cost network model capable of satisfying a traffic demand and responsive to a set of variables each defining one of a network cost, a physical layer feature, or a logical layer feature, a set of constraints defining a relationship between at least two variables from the set of variables, and an objective to reduce the monetary cost of a network defined by the minimum monetary cost network model;

generate an optimization set of network failures F_o;

iteratively, until the current minimum monetary cost network satisfies the traffic demands given a random set of failures F_R;

update the minimum monetary cost network model capable of satisfying the traffic demand given F_o and generated responsive to the set of variables, the set of constraints, and the objective to reduce the monetary cost of the network;

generate a random set of failures F_R;

determine whether the minimum cost monetary network model satisfies the traffic demand given F_R;

in response to determining that the minimum cost network does not satisfy the traffic demands given F_R, select a subset of failures from F_R and add the subset of failures from F_R to F_O; and

in response to determining that the minimum cost network satisfies the traffic demands given F_R, output the current minimum cost network model.

18. The computer readable medium of claim 17, wherein execution of processor executable instructions further causes the processor to generate and update the minimum monetary cost network model with a linear program.

19. The computer readable medium of claim 17, wherein execution of processor executable instructions further causes the processor to generate and update the minimum monetary cost network model with a mixed-integer-linear program.

20. The computer readable medium of claim 17, wherein F_R is generated with a Monte Carlo simulation.

21. The computer readable medium of claim 17, wherein execution of processor executable instructions further causes the processor to determine an impact metric for each failure in F_R.

22. The computer readable medium of claim 21, wherein each failure of the subset of failures has an impact metric above a predetermined threshold.

23. The computer readable medium of claim 17, wherein execution of processor executable instructions further causes the processor to update the minimum monetary cost network model to satisfy an additional set of traffic demands given F_o.

24. A method for designing a network, the method comprising:

receiving a set of optimization network failures F_o, an occurrence probability for each of the failures in F_o, and a target availability for each of a plurality of flows;

generating a minimum monetary cost network model capable of satisfying a traffic demand responsive to a long-term capacity requirement of the minimum cost network model;

iteratively, until a probability of each of the plurality of flows being satisfied across each of the failures in F_o is greater than the respective target availability for each of the plurality of flows;

updating the minimum monetary cost network model responsive to a short-term capacity requirement of the minimum cost network model given each of the failures in F_o; and

calculating the probability of each of the plurality of flows being satisfied across each of the failures in F_o.