# US 10,873,502 B2 · System and method for joint embedding and backup provisioning in virtual networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,873,502 B2
- Document ID: US10873502B2
- Status: Granted
- Kind: B2
- Application number: 15/650,354
- Filed: 2017-07-14
- Published: 2018-02-01
- Granted: 2020-12-22
- Earliest claimed: 2016-07-29
- Assignees: Huawei Technologies Canada Co., Ltd.
- Applicants: Nashid Shahriar; Aimal Khan; Reaz Ahmed; Jeebak Mitra; Shihabur Rahman Chowdhury; Raouf Boutaba
- Inventors: Nashid Shahriar; Aimal Khan; Reaz Ahmed; Jeebak Mitra; Shihabur Rahman Chowdhury; Raouf Boutaba
- Web page: https://patentgrep.com/patent/US10873502B2

## CPC

- H04L 41/122: of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
- G06F 9/45558: {Hypervisor-specific management and integration aspects}
- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- H04L 41/0663: Performing the actions predefined by failover planning, e.g. switching to standby network elements
- H04L 41/0836: {to enhance reliability, e.g. reduce downtime}
- H04L 41/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)
- H04L 41/40: using virtualisation of network functions or resources, e.g. SDN or NFV entities
- G06F 2009/4557: {Distribution of virtual machine instances; Migration and load balancing}
- G06F 2009/45595: {Network integration; Enabling network access in virtual machine instances}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Network Virtualization can be used to map a virtual network (VN) on a substrate network (SN) while accounting for possible substrate failures, known as the Survivable Virtual Network Embedding (SVNE) problem. The VN can be equipped with sufficient spare backup capacity to sustain the Quality of Service during substrate failures, and the resulting VN may be equipped accordingly. The present application discloses jointly optimizing spare backup capacity allocation and embedding a VN to provide full bandwidth in the presence of a single substrate link failure. A solution may be formulated as a Quadratic Integer Program that can be further transformed into an Integer Linear Program, or as a heuristic.

## Claims

### Claim 1

A method for use in network virtualization comprising:
jointly optimizing provisioning of backup bandwidth capacity for a virtual network and embedding of the virtual network on a substrate network to reduce consumption of substrate network resources, the backup bandwidth capacity allocated within the virtual network being used upon occurrence of a failure in the substrate network; and
embedding the virtual network and the backup bandwidth capacity within the virtual network.

### Claim 2 (depends on 1)

The method of claim 1, wherein the jointly optimizing the provisioning of the backup bandwidth capacity for the virtual network and embedding of the virtual network on the substrate network comprises formulating a joint optimization solution as a Quadratic Integer Program (QIP).

### Claim 3 (depends on 2)

The method of claim 2 wherein the formulating the joint optimization solution as the Quadratic Integer Program comprises formulating a solution to minimize:
∑
∀
(
u
^
,
v
^
)
∈
E
^
⁢
∑
∀
(
u
,
v
)
∈
E
⁢
x
uv
u
^
⁢
v
^
×
C
uv
×
(
b
u
^
⁢
v
^
+
S
u
^
⁢
v
^
)
wherein û and {circumflex over (v)} are first and second virtual nodes in the virtual network, u and v are first and second nodes in the substrate network, xuvû{circumflex over (v)} is a mapping between a virtual link VLink(û, {circumflex over (v)})∈Ê and a substrate link SLink(u, v)∈E, Ê and E are a set of all virtual links in the virtual network and a set of all substrate links in the substrate network, respectively, Cuv is a cost of allocating unit bandwidth for a VLink in SLink (u, v), bû{circumflex over (v)} is a bandwidth between the first and second virtual nodes û and {circumflex over (v)} and Sû{circumflex over (v)} is a spare bandwidth capacity between the first and second virtual nodes û and {circumflex over (v)}.

### Claim 4 (depends on 3)

The method of claim 3 further comprising pre-empting over-commitment of the bandwidth by using a constraint defined by:
∀(u,v)∈E:Σ∀(û,{circumflex over (v)})∈Êxuvû,{circumflex over (v)}×(bû{circumflex over (v)}+Sû{circumflex over (v)})≤buv.

### Claim 5 (depends on 2)

The method of claim 2, wherein the formulating the joint optimization solution as the Quadratic Integer Program further comprises transforming the Quadratic Integer Program to an Integer Linear Program (ILP).

### Claim 6 (depends on 5)

The method of claim 5 wherein the transforming the Quadratic Integer Program to the Integer Linear Program comprises formulating the solution to minimize:
∑
∀
(
u
^
,
v
^
)
∈
E
^
⁢
∑
∀
(
u
,
v
)
∈
E
⁢
x
uv
u
^
⁢
v
^
×
C
uv
×
b
u
^
⁢
v
^
+
C
uv
×
q
uv
u
^
⁢
v
^
wherein û and {circumflex over (v)} are first and second virtual nodes in the virtual network, u and v are first and second nodes in the substrate network, xuvû{circumflex over (v)} is a mapping between a virtual link VLink(û, {circumflex over (v)})∈Ê and a substrate link SLink(u, v)∈E, Ê and E are a set of all virtual links in the virtual network and a set of all substrate links in the substrate network, respectively, Cuv is a cost of allocating unit bandwidth for a VLink for SLink (u, v), bû{circumflex over (v)} is a bandwidth between the first and second virtual nodes û and {circumflex over (v)} and quvû{circumflex over (v)}) is an integer variable related to a spare bandwidth capacity between the first and second virtual nodes û and {circumflex over (v)}.

### Claim 7 (depends on 6)

The method of claim 6 further comprising pre-empting over-commitment of the bandwidth by using a constraint defined by:
∀(u,v)∈E:Σ∀(û,{circumflex over (v)})∈Êxuvû,{circumflex over (v)}×bû{circumflex over (v)}+quvû{circumflex over (v)}≤buv.

### Claim 8 (depends on 1)

The method of claim 1, wherein the jointly optimizing the provisioning of the backup bandwidth capacity for the virtual network and embedding the virtual network on the substrate network comprises optimizing by obtaining a solution to the joint optimization using a heuristic process.

### Claim 9 (depends on 1)

The method of claim 1, wherein the jointly optimizing the provisioning of the backup bandwidth capacity for the virtual network and embedding of the virtual network on the substrate network comprises:
for each virtual link between a pair of virtual nodes in the virtual network, allocating spare bandwidth capacity along a non-empty backup virtual path between the pair of virtual nodes, wherein the non-empty backup virtual path is disjoint from a primary virtual link between the pair of virtual nodes such that the allocated spare bandwidth capacity is available between the pair of virtual nodes when the primary virtual link is affected by a substrate link failure in the substrate network;
embedding each of the pair of virtual nodes to one substrate node in the substrate network, such that multiple virtual nodes from a same virtual network request are not mapped to a same substrate node;
embedding each of the virtual links onto a non-empty substrate path having sufficient bandwidth to accommodate a virtual link's primary bandwidth demand and backup spare capacity provisioned on the virtual link; and
disjointedly embedding the primary virtual link and backup virtual links on the backup virtual path to mitigate an effect of substrate link failure of a single link affecting the primary virtual link and the backup virtual links at a same time.

### Claim 10 (depends on 1)

The method of claim 1 wherein the jointly optimizing the provisioning of the backup bandwidth capacity for the virtual network and embedding of the virtual network on the substrate network comprises:
performing an initial embedding of the virtual network and finding estimated spare backup bandwidth capacity on virtual links in the virtual network for at least one primary virtual link by:
determining a backup virtual path for each primary virtual link incident to a virtual node and estimating spare backup bandwidth capacity on the virtual link belonging to the backup virtual path;
determining disjointedness requirements based on the estimated spare backup bandwidth capacity;
embedding the virtual node to a substrate node incurring least cost of embedding for the virtual links incident to the virtual node; and
embedding the virtual links incident to the virtual node on a substrate path having sufficient bandwidth to serve a primary bandwidth demand of the virtual link and the estimated spare backup capacity;
identifying paths consisting of the virtual links allocated for the backup bandwidth capacity belonging to different shared risk groups; and
re-determining the estimated spare backup bandwidth capacity on the virtual links allocated for backup bandwidth capacity to further optimize the allocation of the estimated spare backup bandwidth capacity.

### Claim 11

An apparatus comprising:
a processor; and
a processor readable storage device, having stored thereon, processor executable instructions that when executed by the processor cause the processor to:
jointly optimize provisioning of backup bandwidth capacity for a virtual network and embedding of the virtual network on a substrate network to reduce consumption of substrate network resources, the backup bandwidth capacity allocated within the virtual network being used upon occurrence of a failure in the substrate network; and
embed the virtual network and the backup bandwidth capacity within the virtual network.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the jointly optimizing the provisioning of the backup bandwidth capacity for the virtual network and embedding of the virtual network on the substrate network comprises formulating a joint optimization solution as a Quadratic Integer Program (QIP).

### Claim 13 (depends on 12)

The apparatus of claim 12 wherein the formulating the joint optimization solution as the Quadratic Integer Program comprises formulating a solution to minimize the expression:
∑
∀
(
u
^
,
v
^
)
∈
E
^
⁢
∑
∀
(
u
,
v
)
∈
E
⁢
x
uv
u
^
⁢
v
^
×
C
uv
×
(
b
u
^
⁢
v
^
+
S
u
^
⁢
v
^
)
wherein û and {circumflex over (v)} are first and second virtual nodes in the virtual network, u and v are first and second nodes in the substrate network, xuvû{circumflex over (v)} is a mapping between a virtual link VLink(û, {circumflex over (v)})∈Ê and a substrate link SLink(u, v)∈E, Ê and E are a set of all virtual links in the virtual network and a set of all substrate links in the substrate network, respectively, Cuv is a cost of allocating unit bandwidth for a VLink in SLink (u, v), bû{circumflex over (v)} is a bandwidth between the first and second virtual nodes û and {circumflex over (v)} and Sû{circumflex over (v)} is a spare bandwidth capacity between the first and second virtual nodes û and {circumflex over (v)}.

### Claim 14 (depends on 13)

The apparatus of claim 13 further comprising pre-empting over-commitment of the bandwidth by using a constraint defined by:
∀(u,v)∈E:Σ∀(û,{circumflex over (v)})∈Êxuvû,{circumflex over (v)}×(bû,{circumflex over (v)}+Sû,{circumflex over (v)})≤buv.

### Claim 15 (depends on 12)

The apparatus of claim 12, wherein the formulating the joint optimization solution as the Quadratic Integer Program further comprises transforming the Quadratic Integer Program to an Integer Linear Program (ILP).

### Claim 16 (depends on 15)

The apparatus of claim 15 wherein the transforming the Quadratic Integer Program to the Integer Linear Program comprises formulating the solution to minimize the expression:
∑
∀
(
u
^
,
v
^
)
∈
E
^
⁢
∑
∀
(
u
,
v
)
∈
E
⁢
x
uv
u
^
⁢
v
^
×
C
uv
×
b
u
^
⁢
v
^
+
C
uv
×
q
uv
u
^
⁢
v
^
wherein û and {circumflex over (v)} are first and second virtual nodes in the virtual network, u and v are first and second nodes in the substrate network, xuvû{circumflex over (v)} is a mapping between a virtual link VLink(û, {circumflex over (v)})∈Ê and a substrate link SLink(u, v)∈E, Ê and E are a set of all virtual links in the virtual network and a set of all substrate links in the substrate network, respectively, Cuv is a cost of allocating unit bandwidth for a VLink in SLink(u, v), bû{circumflex over (v)} is a bandwidth between the first and second virtual nodes û and {circumflex over (v)} and quvû{circumflex over (v)} is an integer variable related to a spare bandwidth capacity between the first and second virtual nodes û and {circumflex over (v)}.

### Claim 17 (depends on 16)

The apparatus of claim 16 further comprising pre-empting over-commitment of the bandwidth by using a constraint defined by:
∀(u,v)∈E:Σ∀(û,{circumflex over (v)})∈Êxuvû,{circumflex over (v)}×bû,{circumflex over (v)}+quvû,{circumflex over (v)}≤buv.

### Claim 18 (depends on 11)

The apparatus of claim 11, wherein the jointly optimizing the provisioning of the backup bandwidth capacity for the virtual network and embedding the virtual network on the substrate network comprises jointly optimizing by formulating a solution to the joint optimization using a heuristic process.

### Claim 19 (depends on 11)

The apparatus of claim 11, wherein the jointly optimizing the provisioning of the backup bandwidth capacity for the virtual network and embedding the virtual network on the substrate network comprises:
for each virtual link between a pair of virtual nodes in the virtual network, allocating spare bandwidth capacity along a non-empty backup virtual path between the pair of virtual nodes, wherein the non-empty backup virtual path is disjoint from a primary virtual link between the pair of virtual nodes such that the allocated spare bandwidth capacity is available between the pair of virtual nodes when the primary virtual link is affected by a substrate link failure in the substrate network;
embedding each of the pair of virtual nodes to one substrate node in the substrate network, such that multiple virtual nodes from a same virtual network request are not mapped to a same substrate node;
embedding each of the virtual links onto a non-empty substrate path having sufficient bandwidth to accommodate a virtual link's primary bandwidth demand and backup spare capacity provisioned on the virtual link; and
disjointedly embedding the primary virtual link and backup virtual links on the backup virtual path to mitigate an effect of a substrate link failure affecting the primary virtual link and the backup virtual links at the same time.

### Claim 20 (depends on 11)

The apparatus of claim 11 wherein the jointly optimizing the provisioning of backup bandwidth capacity for the virtual network and embedding of the virtual network on the substrate network comprises:
performing an initial embedding of the virtual network and finding estimated spare backup bandwidth capacity on virtual links in the virtual network for at least one primary virtual link by:
determining a backup virtual path for each primary virtual link incident to a virtual node û and estimating spare backup bandwidth capacity on the virtual link belonging to the backup virtual path;
determining disjointedness requirements based on the estimated spare backup bandwidth capacity;
embedding the virtual node to a substrate node incurring least cost of embedding for the virtual links incident to the virtual node; and
embedding the virtual links incident to the virtual node on a substrate path having sufficient bandwidth to serve a primary bandwidth demand of the virtual link and the estimated spare backup capacity;
identifying paths consisting of the virtual links allocated for the backup bandwidth capacity belonging to different shared risk groups; and
re-determining the estimated spare backup bandwidth capacity on the virtual links allocated for backup bandwidth capacity to further optimize the allocation of the estimated spare backup bandwidth capacity.

### Claim 21 (depends on 11)

The apparatus of claim 11 further configured to receive virtual node descriptions constraints, and physical network descriptions.

### Claim 22

A processor readable storage device, having stored thereon, processor executable instructions that when executed by the processor cause the processor to:
jointly optimize provisioning of backup bandwidth capacity for a virtual network and embedding of the virtual network on a substrate network to reduce substrate network resources, the backup bandwidth capacity allocated within the virtual network being used upon occurrence of a failure in the substrate network; and
embed the virtual network and the backup bandwidth capacity within the virtual network.