Network stochastic cross-layer optimization for meeting traffic flow availability target at minimum cost

Patent metadata

Field	Value
Publication number	US-9722912-B2
Application number	US-201514922905-A
Country	US
Kind code	B2
Filing date	Oct 26, 2015
Priority date	Jul 9, 2015
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

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.

First claim

What is claimed:

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 an initial random set of failures;
determining an impact metric for each randomly generated failure in the initial random set of failures;
forming the set of failures F R from the initial random set of failures by selecting failures in the initial random set of failures having an impact metric above a predetermined threshold;
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,
wherein, the minimum monetary cost network model is generated and updated using a linear program.

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

3. 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.

4. 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 .

5. 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.

6. 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 an initial random set of failures;
determine an impact metric for each randomly generated failure in the initial random set of failures;
form the set of failures F R from the initial random set of failures by selecting failures in the initial random set of failures having an impact metric above a predetermined threshold;
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,
wherein, the minimum monetary cost network model is generated and updated using a linear program.

7. The system of claim 6 , 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.

8. The system of claim 6 , wherein F R is generated with a Monte Carlo simulation.

9. The system of claim 6 , 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 .

10. The system of claim 9 , 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.

11. 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 an initial random set of failures;
determine an impact metric for each randomly generated failure in the initial random set of failures;
form the set of failures F R from the initial random set of failures by selecting failures in the initial random set of failures having an impact metric above a predetermined threshold;
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,
wherein, the minimum monetary cost network model is generated and updated using a linear program.

12. The computer readable medium of claim 11 , 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.

13. The computer readable medium of claim 11 , wherein F R is generate

Assignees

• Google Inc

Inventors

• Zhao Xiaoxue
• Danna Emilie Jeanne Anne
• Albrecht Christoph
• Koley Bikash
• Ahuja Satyajeet Singh
• Dangui Vinayak

Classifications

• G06F2117/06

  Spare resources, e.g. for permanent fault suppression · CPC title

• H04W16/18

  Network planning tools · CPC title

• G06F2111/08

  Probabilistic or stochastic CAD · CPC title

• G06F30/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 title

• H04L41/14

  Network analysis or design · CPC title