# US 10,313,195 B2 · Dedicated protection for virtual network embedding

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

- Number: US 10,313,195 B2
- Document ID: US10313195B2
- Status: Granted
- Kind: B2
- Application number: 15/048,411
- Filed: 2016-02-19
- Published: 2017-03-16
- Granted: 2019-06-04
- Earliest claimed: 2015-09-14
- Assignees: Huawei Technologies Co., Ltd.
- Applicants: Huawei Technologies Canada Co., Ltd.
- Inventors: Reaz Ahmed; Jeebak Mitra; Shihabur Chowdhury; Nashid Shahriar; Raouf Boutaba
- Web page: https://patentgrep.com/patent/US10313195B2

## CPC

- H04L 12/4641: {Virtual LANs, VLANs, e.g. virtual private networks [VPN] (LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272)}
- H04L 41/122: of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques for virtual network embedding (VNE) with dedicated protection of multiple virtual networks against a single node or link failure are described. The virtual network embedding provides dedicated protection without using redundant substrate network resources for each of the individual virtual networks (VNs) elements.

## Claims

### Claim 1

A method for embedding a virtual network with dedicated protection onto a physical network comprising a plurality of physical nodes and a plurality of physical links connecting the physical nodes, the method comprising:
receiving a virtual network description of a virtual network topology for embedding onto the physical network, the virtual network description comprising:
a plurality of virtual nodes;
a plurality of virtual links connecting the virtual nodes; and
a plurality of location constraints, each location constraint providing an indication of a physical node onto which a virtual node is not able to be provisioned; and
embedding the virtual network with dedicated protection onto the physical network by:
embedding the virtual network onto a first partition of physical nodes of the physical network, consistent with the location constraints; and
embedding a shadow virtual network corresponding to the virtual network onto a second partition of physical nodes of the physical network, consistent with the location constraints, the physical nodes of the first and second partitions being selected such that the first and second partition have no physical nodes in common.

### Claim 2 (depends on 1)

The method of claim 1, wherein the physical network is defined according to:
G=(V,E),
the virtual network is defined according to:
G=(V,P)
the shadow virtual network is defined according to:
{tilde over (G)}=({tilde over (V)},{tilde over (E)})
where:
V is a set of individual physical nodes u;
E is a set of individual physical links;
V is a set of individual virtual nodes ū;
Ē is a set of individual virtual links;
{tilde over (V)} is a set of individual shadow virtual nodes ũ enumerated according to a transformation function τ(ū)=ũ; and
{tilde over (E)} is a set of individual shadow virtual links corresponding to the set of virtual links Ē;
the method further comprising:
generating a protected virtual network description Ĝ=({circumflex over (V)},Ê), where:
{circumflex over (V)}=V∪{tilde over (V)};
Ê=Ē∪{tilde over (E)};
wherein embedding the virtual network with dedicated protection comprises:
embedding Ĝ on the physical network such that:
any virtual node ū∈V and any shadow virtual node ũ∈{tilde over (V)} are not provisioned on a same physical node; and
any virtual link (ū,v)∈Ē and any shadow virtual link (ũ,{tilde over (v)})∈{tilde over (E)} are not provisioned on a same physical path comprising one or more of the physical links.

### Claim 3 (depends on 2)

The method of claim 2, wherein the plurality of location constraints for a virtual node are provided by a location constraint set associated with the virtual node defined as:
l
u
_
⁢
u
=
{
1
if
⁢
⁢
u
_
∈
V
_
⁢
⁢
⁢
can
⁢
⁢
be
⁢
⁢
provisioned
⁢
⁢
on
⁢
⁢
u
∈
V
,
0
otherwise
.

### Claim 4 (depends on 3)

The method of claim 3, wherein embedding the virtual network with dedicated protection is determined using an integer linear programming (ILP) formulation.

### Claim 5 (depends on 4)

The method of claim 4, wherein the ILP formulation has an objective function of:
minimize
⁢
∑
∀
(
u
^
,
v
^
)
∈
E
^
⁢
∑
∀
(
u
,
v
)
∈
E
⁢
x
uv
u
^
⁢
v
^
×
C
uv
×
b
u
^
⁢
v
^
,
⁢
where
⁢
:
x
uv
u
^
⁢
v
^
=
{
1
if
⁢
⁢
(
u
^
,
v
^
)
∈
E
^
⁢
⁢
is
⁢
⁢
mapped
⁢
⁢
to
⁢
⁢
(
u
,
v
)
∈
E
,
0
otherwise
,
,
Cuv is a cost of providing unit bandwidth for a physical link between physical nodes u, v; and
bû{circumflex over (v)} is a bandwidth requirement for a virtual link between virtual nodes û,{circumflex over (v)}.

### Claim 6 (depends on 3)

The method of claim 3, wherein the embedding is determined using a heuristic approach comprising:
a node mapping phase during which virtual nodes of the virtual network and shadow virtual nodes of the shadow virtual network are mapped to physical nodes of the physical network;
a physical network partitioning phase during which unmapped physical nodes of the physical network are partitioned to either the first partition or the second partition; and
a link mapping phase during which virtual links of the virtual network and shadow virtual links of the shadow virtual network are mapped to physical paths in respective ones of the first partition and second partition.

### Claim 7 (depends on 6)

The method of claim 6, wherein the node mapping phase comprises mapping each node of the virtual network and each node of the shadow virtual network to a separate node of the physical network.

### Claim 8 (depends on 7)

The method of claim 7, wherein the node mapping phase further comprises one or more of:
determining whether mapping a virtual node to a physical node makes it impossible to connect remaining virtual nodes;
determining whether mapping a virtual node to a physical node reduces a shortest path length of virtual nodes in the first partition or the second partition; and
determining whether mapping a virtual node to a physical node increases a connectivity of virtual nodes in the first partition or the second partition.

### Claim 9 (depends on 8)

The method of claim 8, wherein the physical network partitioning phase comprises one or more of:
determining whether adding the unmapped physical node to one of the first or second partitions makes virtual nodes of the other partition impossible to be connected;
determining whether adding the unmapped physical node to one of the first or second partitions reduces a shortest path length in the first or second partitions;
determining whether adding the unmapped physical node to one of the first or second partitions increases a connectivity of virtual nodes in the first partition or the second partition; and
determining which one of the first and second partitions is smaller.

### Claim 10 (depends on 9)

The method of claim 9, wherein the link mapping phase comprises mapping virtual links to physical paths within the disjoint partitions.

### Claim 11

A system for embedding a virtual network with dedicated protection onto a physical network comprising a plurality of physical nodes and a plurality of physical links connecting the physical nodes, the system comprising:
a processing unit for executing instructions; and
a memory unit for storing instructions, which when executed by the processor configure the system to perform steps for:
receiving a virtual network description of a virtual network topology for embedding onto the physical network, the virtual network description comprising:
a plurality of virtual nodes;
a plurality of virtual links connecting the virtual nodes; and
a plurality of location constraints, each location constraint providing an indication of a physical node a virtual node is able to be provisioned on; and
embedding the virtual network with dedicated protection onto the physical network by:
embedding the virtual network onto a first partition of physical nodes of the physical network, consistent with the location constraints; and
embedding a shadow virtual network corresponding to the virtual network onto a second partition of physical nodes of the physical network, consistent with the location constraints, the nodes of the first and second partitions being selected such that the first and second partition have no physical nodes in common, disjoint from the first partition of the physical.

### Claim 12 (depends on 11)

The system of claim 11, wherein the physical network is defined according to:
G=(V,E)
the virtual network is defined according to:
G=(V,Ē),
the shadow virtual network is defined according to:
G=(V,Ē)
where:
V is a set of individual physical nodes u;
E is set of individual physical links;
V is a set of individual virtual nodes ū;
Ē is a set of individual virtual links;
V is a set of individual shadow virtual nodes ũ enumerated according to a transformation function τ(ū)=ũ; and
{tilde over (E)} is a set of individual shadow virtual links corresponding to the set of virtual links Ē;
wherein when executed by the processor the instructions further configure the system to perform steps for:
generating a protected virtual network description Ĝ=({circumflex over (V)},Ê), where:
{circumflex over (V)}=V∪{circumflex over (V)},
Ê=Ē∪{tilde over (E)},
wherein embedding the virtual network with dedicated protection comprises:
embedding Ĝ on the physical network such that:
any virtual node ū∈V and any shadow virtual node ũ∈{tilde over (V)} are not provisioned on a same physical node; and
any virtual link (ū,v)∈Ē and any shadow virtual link (ũ,{tilde over (v)})∈{tilde over (E)} are not provisioned on a same physical path comprising one or more of the physical links.

### Claim 13 (depends on 12)

The system of claim 12, wherein the plurality of location constraints for a virtual node are provided by a location constraint set associated with the virtual node defined as:
l
u
_
⁢
u
=
{
1
if
⁢
⁢
u
_
∈
V
_
⁢
⁢
⁢
can
⁢
⁢
be
⁢
⁢
provisioned
⁢
⁢
on
⁢
⁢
u
∈
V
,
0
otherwise
.

### Claim 14 (depends on 13)

The system of claim 13, wherein embedding the virtual network with dedicated protection is determined using an integer linear programming (ILP) formulation.

### Claim 15 (depends on 14)

The system of claim 14, wherein the ILP formulation has an objective function of:
minimize
⁡
(
∑
∀
(
u
^
,
v
^
)
∈
E
^
⁢
∑
∀
(
u
,
v
)
∈
E
⁢
x
uv
u
^
⁢
v
^
×
C
uv
×
b
u
^
⁢
v
^
)
where
⁢
:
x
uv
u
^
⁢
v
^
=
{
1
if
⁢
⁢
(
u
^
,
v
^
)
∈
E
^
⁢
⁢
is
⁢
⁢
mapped
⁢
⁢
to
⁢
⁢
(
u
,
v
)
∈
E
,
0
otherwise
Cuv is a cost of providing unit bandwidth for a physical link between physical nodes u,v; and
bû{circumflex over (v)} is a bandwidth requirement for a virtual link between virtual nodes û,{circumflex over (v)}.

### Claim 16 (depends on 13)

The system of claim 13, wherein the embedding is determined using a heuristic approach comprising:
a node mapping phase during which virtual nodes of the virtual network and shadow virtual nodes of the shadow virtual network are mapped to physical nodes of the physical network;
a physical network partitioning phase during which unmapped physical nodes of the physical network are partitioned to either the first partition or the second partition; and
a link mapping phase during which virtual links of the virtual network and shadow virtual links of the shadow virtual network are mapped to physical paths in respective ones of the first partition and second partition.

### Claim 17 (depends on 16)

The system of claim 16, wherein the node mapping phase comprises mapping each virtual node of the virtual network and each shadow virtual node of the shadow virtual network to a separate physical node of the physical network.

### Claim 18 (depends on 17)

The system of claim 17, wherein the node mapping phase further comprises one or more of:
determining whether mapping a virtual node to a physical node makes it impossible to connect remaining virtual nodes;
determining whether mapping a virtual node to a physical node reduces a shortest path length of virtual nodes in the first partition or the second partition; and
determining whether mapping a virtual node to a physical node increases a connectivity of virtual nodes in the first partition or the second partition.

### Claim 19 (depends on 18)

The system of claim 18, wherein the physical network partitioning phase comprises one or more of:
determining whether adding the unmapped physical node to one of the first or second partitions makes virtual nodes of the other partition impossible to be connected;
determining whether adding the unmapped physical node to one of the first or second partitions reduces a shortest path length in the first or second partitions;
determining whether adding the unmapped physical node to one of the first or second partitions increases a connectivity of virtual nodes in the first partition of the second partition; and
determining which one of the first and second partitions is smaller.

### Claim 20 (depends on 19)

The system of claim 19, wherein the link mapping phase comprises mapping virtual links to physical paths within the disjoint partitions.