Connectivity-aware virtual network embedding

Patent metadata

Field	Value
Publication number	US-9813287-B2
Application number	US-201615048573-A
Country	US
Kind code	B2
Filing date	Feb 19, 2016
Priority date	Jul 30, 2015
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

Embedding a virtual network onto a physical network may be done in such a manner to ensure that the embedded virtual network maintains connectivity in the event of failure of k links in the physical network. The embedding determines virtual links that must be embedded onto disjoint paths in the physical network and then embeds the virtual network according to ensure the determined virtual links are embedded on disjoint paths.

First claim

What is claimed is:

1. A method for embedding a virtual network definition defining a virtual network comprising a plurality of virtual nodes and a plurality of virtual links on a physical network, the method comprising:
determining a conflicting set for each virtual link of the virtual network definition, each conflicting set comprising a plurality of virtual links of the virtual network that must be embedded on disjoint paths in the physical network to maintain connectivity of the virtual network in the presence of k physical link failures; and
embedding the virtual network onto the physical network so that each of the plurality virtual links in each conflicting set are embedded on disjoint paths of the physical network.

2. The method of claim 1 , further comprising augmenting the virtual network definition by adding parallel virtual links between virtual nodes so that each of the virtual nodes comprises at least k+1 virtual links.

3. The method of claim 2 , wherein the parallel virtual links are added when determining the conflicting set for each virtual link.

4. The method of claim 3 , wherein augmenting the virtual network definition and determining the conflicting set comprises:
selecting an initial virtual node as a protected component;
selecting a virtual node outside of the protected component having a virtual link to a virtual node inside the protected component;
attempting to determine k+1 edge-disjoint shortest paths from the protected component to the selected virtual node;
if k+1 edge-disjoint shortest paths are determined:
adding the selected virtual node to the protected component;
updating the conflicting set of the virtual link between the selected virtual node and the virtual node inside the protected component to include all virtual links in the k+1 edge-disjoint shortest paths; and
removing all of the virtual links in the k+1 edge-disjoint shortest paths from further consideration in augmenting the virtual network definition and determining the conflicting set;

if k+1 edge-disjoint shortest paths are not determined:
adding n parallel virtual links between the selected virtual node and the virtual node inside the protected component to provide k+1 edge-disjoint shortest paths, where n=k+1−(number of determined edge-disjoint shortest paths);
adding the selected virtual node to the protected component;
updating the conflicting set of the virtual link between the selected virtual node and the virtual node inside the protected component to include all virtual links in the determined edge-disjoint shortest paths and the n parallel virtual links; and
removing all of the virtual links in the determined edge-disjoint shortest paths and the n parallel virtual links from further consideration in augmenting the virtual network definition and determining the conflicting set; and

selecting a next virtual node outside of the protected component having a virtual link to a virtual node inside the protected component.

5. The method of claim 1 , wherein determining the conflicting set for each of the virtual links comprises determining the conflicting set for each of the virtual links using an optimal cut-set approach.

6. The method of claim 1 , wherein determining the embedding comprises using an integer linear programming (ILP) formulation to determine the embedding.

7. The method of claim 1 , wherein determining the embedding comprises using a heuristic approach to determine the embedding.

8. The method of claim 7 , wherein the heuristic approach comprises:
sorting in decreasing order the virtual nodes according to a sum of conflicting set size of each virtual link incident upon the respective virtual node; and
mapping virtual nodes and virtual links of the virtual network definition to the physical network beginning with the virtual nodes having the largest sum of conflicting set size.

9. The method of claim 8 , wherein each virtual link incident upon a virtual node is mapped to the physical network in a decreasing order of the conflicting set size of each one of the virtual links.

10. The method of claim 1 , further comprising receiving the virtual network definition as a virtual network request for embedding onto a physical network.

11. A system for embedding a virtual network comprising a plurality of virtual nodes and a plurality of virtual links on a physical network, 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:
determining a conflicting set for each virtual link of a virtual network definition defining the virtual network, each conflicting set comprising a plurality of virtual links of the virtual network that must be embedded on disjoint paths in the physical network to maintain connectivity of the virtual network in the presence of k physical link failures; and
embedding the virtual network onto the physical network so that each of the plurality virtual links in each conflicting set are embedded on disjoint paths of the physical network.

12. The system of claim 11 , wherein the instructions configure the system to further perform steps for augmenting the virtual network definition by adding parallel virtual links between virtual nodes so that each of the virtual nodes comprises at least k+1 virtual links.

13. The system of claim 12 , wherein the parallel virtual links are added when determining the conflicting set for each virtual link.

14. The system of claim 13 , wherein augmenting the virtual network definition and determining the conflicting set comprises:
selecting an initial virtual node as a protected component;
selecting a virtual node outside of the protected component having a virtual link to a virtual node inside the protected component;
attempting to determine k+1 edge-disjoint shortest paths from the protected component to the selected virtual node;
if k+1 edge-disjoint shortest paths are determined:
adding the selected virtual node to the protected component;
updating the conflicting set of the virtual link between the selected virtual node and the virtual node inside the protected component to include all virtual links in the k+1 edge-disjoint shortest paths; and
removing all of the virtual links in the k+1 edge-disjoint shortest paths from further consideration in augmenting the virtual network definition and determining the conflicting set;

if k+1 edge-disjoint shortest paths are not determined:
adding n parallel virtual links between the selected virtual node and the virtual node inside the protected component to provide k+1 edge-disjoint shortest paths,
where n=k+1−(number of determined edge-disjoint shortest paths);

adding the selected virtual node to the protected component;
updating the conflicting set of the virtual link between the selected virtual node and the virtual node inside the protected component to include all virtual links in the determined edge-disjoint shortest paths and the n parallel virtual links; and
removing all of the virtual links in the determined edge-disjoint shortest paths and the n parallel virtual links from further consideration in augmenting the virtual network definition and determining the conflicting set; and

selecting a next virtual node outside of the protected component having a virtual link to a virtual node inside the protected component.

15. The system of claim 11 , wherein determining the conflicting set for each of the virtual links comprises determining the conflicting set for each of the virtual links using an optimal cut-set approach.

Assignees

• Huawei Tech Canada Co Ltd
• Huawei Tech Co Ltd

Inventors

• Ahmed Reaz
• Mitra Jeebak
• Chowdhury Shihabur
• SHAHRIAR Nashid
• Boutaba Raouf

Classifications

• H04L41/0836

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

• H04L45/12

  Shortest path evaluation · CPC title

• H04L41/0672

  Electricity · mapped topic

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L41/0668 Primary

  by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure · CPC title