System and method for joint embedding and backup provisioning in virtual networks

Patent metadata

Field	Value
Publication number	US-10873502-B2
Application number	US-201715650354-A
Country	US
Kind code	B2
Filing date	Jul 14, 2017
Priority date	Jul 29, 2016
Publication date	Dec 22, 2020
Grant date	Dec 22, 2020

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.

First claim

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

2. 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).

3. 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, x uv û{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, C uv 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)}.

4. 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)})∈Ê x uv û,{circumflex over (v)} ×( b û{circumflex over (v)} +S û{circumflex over (v)} )≤ b uv .

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

6. 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
^

Assignees

• SHAHRIAR Nashid
• Khan Aimal
• Ahmed Reaz
• Mitra Jeebak
• Chowdhury Shihabur Rahman
• Boutaba Raouf
• Huawei Tech Canada Co Ltd

Inventors

• SHAHRIAR Nashid
• Khan Aimal
• Ahmed Reaz
• Mitra Jeebak
• Chowdhury Shihabur Rahman
• Boutaba Raouf

Classifications

• 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/0836 Primary

  to enhance reliability, e.g. reduce downtime · CPC title

• H04L41/40

  using virtualisation of network functions or resources, e.g. SDN or NFV entities · CPC title

• H04L41/122 Primary

  of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV] · CPC title

• H04L41/0663

  Performing the actions predefined by failover planning, e.g. switching to standby network elements · CPC title