Availability SLO-aware network optimization

Patent metadata

Field	Value
Publication number	US-12218808-B2
Application number	US-202318195974-A
Country	US
Kind code	B2
Filing date	May 11, 2023
Priority date	Oct 12, 2021
Publication date	Feb 4, 2025
Grant date	Feb 4, 2025

Abstract

The subject matter described herein provides systems and techniques for a network planning and optimization tool that may allow for network capacity planning using key network failures for an arbitrary pair of network topology and demands. Performing network capacity planning with key network failures, instead of using other techniques, may avoid over-building the topology of a network. In particular, key network failures may be generated from the probabilistic failures, and the impact of these failures on a network may be computed. Expected flow availability SLO or a function thereof may be computed, using this information, and used by the tool to design a robust network. With an embedded flow availability calculation and updated risk framework, the capacitated cross-layer network topologies output by the tool may meet network demands/flows with their respective SLO type at the lowest cost.

First claim

The invention claimed is:

1. A method for determining network topologies, the method comprising:
generating, with one or more processors, a set of probabilistic failures for a network topology based on one or more failure generation rules and one or more failure rates;
determining, with the one or more processors, key network failures of the set of probabilistic failures based on a failure-flow impact for respective probabilistic failures in the set of probabilistic failures, the key network failures being a subset of the set of probabilistic failures, wherein the key network failures are associated with respective failure-flow impacts that cause an unrouted fraction of network traffic of the network topology to be greater than a threshold; and
generating, with the one or more processors, the network topology based on the key network failures.

2. The method of claim 1 , wherein determining the key network failures further comprises:
determining the failure-flow impact for each probabilistic failure by performing a risk analysis; and
stack-ranking each probabilistic failure in the set of probabilistic failures based on its respective failure-flow impact, wherein the determined key network failures are a subset of the stack-ranked set of probabilistic failures.

3. The method of claim 1 , further comprising determining, with the one or more processors, routing for the network topology.

4. The method of claim 1 , further comprising:
generating, with the one or more processors, a per-flow unrouted fraction of traffic demanded across network states; and
computing, with the one or more processors, a flow availability service level objective (SLO) for the network topology based on the per-flow unrouted fraction of traffic demanded.

5. The method of claim 4 , further comprising:
determining, with the one or more processors, the flow availability SLO is above a threshold; and
outputting, with the one or more processors, the network topology.

6. The method of claim 4 , further comprising:
determining, with the one or more processors, the flow availability SLO is below a threshold; and
generating, with the one or more processors, a subsequent set of probabilistic failures accounting for a target network capacity.

7. The method of claim 6 , further comprising:
determining, with the one or more processors, subsequent key network failures of the subsequent set of probabilistic failures based on a failure-flow impact for each probabilistic failure in the subsequent set of probabilistic failures; and
generating, with the one or more processors, a subsequent network topology based on the subsequent key network failures.

8. A system comprising:
one or more processors; and
one or more storage devices in communication with the one or more processors and storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations for determining network topologies, the operations comprising:
generating a set of probabilistic failures for a network topology based on one or more failure generation rules and one or more failure rates;
determining key network failures of the set of probabilistic failures based on a failure-flow impact for respective probabilistic failures in the set of probabilistic failures, the key network failures being a subset of the set of probabilistic failures, wherein the key network failures are associated with respective failure-flow impacts that cause an unrouted fraction of network traffic of the network topology to be greater than a threshold; and
generating the network topology based on the key network failures.

9. The system of claim 8 , wherein determining the key network failures further comprises:
determining the failure-flow impact for each probabilistic failure by performing a risk analysis; and
stack-ranking each probabilistic failure in the set of probabilistic failures based on its respective failure-flow impact, wherein the determined key network failures are a subset of the stack-ranked set of probabilistic failures.

10. The system of claim 8 , wherein the operations further comprise determining routing for the network topology.

11. The system of claim 8 , wherein the operations further comprise:
generating a per-flow unrouted fraction of traffic demanded across network states; and
computing a flow availability service level objective (SLO) for the network topology based on the per-flow unrouted fraction of traffic demanded.

12. The system of claim 11 , wherein the operations further comprise:
determining the flow availability SLO is above a threshold; and
outputting the network topology.

13. The system of claim 11 , wherein the operations further comprise:
determining the flow availability SLO is below a threshold; and
generating a subsequent set of probabilistic failures accounting for a target network capacity.

14. The system of claim 13 , wherein the operations further comprise:
determining subsequent key network failures of the subsequent set of probabilistic failures based on a failure-flow impact for each probabilistic failure in the subsequent set of probabilistic failures; and
generating a subsequent network topology based on the subsequent key network failures.

15. A non-transitory computer-readable medium storing instructions, that when executed by one or more processors, cause the one or more processors to perform operations for determining network topologies, the operations comprising:
generating a set of probabilistic failures for a network topology based on one or more failure generation rules and one or more failure rates;
determining key network failures of the set of probabilistic failures based on a failure-flow impact for respective probabilistic failures in the set of probabilistic failures, the key network failures being a subset of the set of probabilistic failures, wherein the key network failures are associated with respective failure-flow impacts that cause an unrouted fraction of network traffic of the network topology to be greater than a threshold; and
generating the network topology based on the key network failures.

16. The non-transitory computer-readable medium of claim 15 , wherein determining the key network failures further comprises:
determining the failure-flow impact for each probabilistic failure by performing a risk analysis; and
stack-ranking each probabilistic failure in the set of probabilistic failures based on its respective failure-flow impact, wherein the determined key network failures are a subset of the stack-ranked set of probabilistic failures.

17. The non-transitory computer-readable medium of claim 15 , wherein the operations further comprise determining routing for the network topology.

18. The non-transitory computer-readable medium of claim 15 , wherein the operations further comprise:
generating a per-flow unrouted fraction of traffic demanded across network states; and
computing a flow availability service level objective (SLO) for the network topology based on the per-flow unrouted fraction of traffic demanded.

19. The non-transitory computer-readable medium of claim 18 , wherein the operations further comprise:
determining the flow availability SLO is above a threshold; and
outputting the network topology.

20. The non-transitory computer-readable medium of claim 18 , wherein the operations further comprise:
determining the flow availability SLO is below a threshold;
generating a subsequent set of probabilistic failures account

Assignees

• Google Llc

Inventors

• He Jinjie
• Johnston Matthew
• Sharma Anurag

Classifications

• H04L41/065

  involving logical or physical relationship, e.g. grouping and hierarchies · CPC title

• H04W16/18

  Network planning tools · CPC title

• H04L41/0823

  characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability (for optimising operational conditions of wireless networks H04W24/02) · CPC title

• H04L41/0896

  Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities (flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76) · CPC title

• H04L41/5019

  Ensuring fulfilment of SLA · CPC title