Distributed virtual network embedding

Patent metadata

Field	Value
Publication number	US-10230661-B2
Application number	US-201715424398-A
Country	US
Kind code	B2
Filing date	Feb 3, 2017
Priority date	Feb 3, 2017
Publication date	Mar 12, 2019
Grant date	Mar 12, 2019

Abstract

Systems and methods for performing distributed virtual network embedding are disclosed. A resource orchestrator may receive a virtual network request specifying a set of virtual nodes, a set of virtual links, each connecting two virtual nodes in a mesh topology, and resource requirements for some virtual nodes. The orchestrator may partition the virtual network request into multiple sub-requests, each specifying a linear topology for a subset of the virtual nodes and links within the mesh topology. The sub-requests may collectively include all virtual links within the mesh topology with no overlapping links. Resource orchestrators may collaborate to compute, independently for each sub-request, a respective chaining solution in which each virtual node is mapped to a physical node having resources sufficient to implementing the virtual node. A resource orchestrator may combine the respective chaining solutions for each of the sub-requests to generate a mapping solution for the virtual network request.

First claim

What is claimed is:

1. A method for distributed virtual network embedding, comprising:
receiving, at a resource orchestrator, a virtual network request specifying:
a set of virtual nodes;
a set of virtual links, each of which connects two of the virtual nodes in a mesh topology for the virtual network request; and
a resource requirement for at least one of the virtual nodes;

generating, by the resource orchestrator, a mapping solution for the virtual network request in which each virtual node in the set of virtual nodes is mapped to a respective one of a plurality of physical nodes, each physical node being represented as a vertex in a resource orchestration framework, wherein generating the mapping solution comprises:
partitioning, by the resource orchestrator, the virtual network request into a plurality of sub-requests, wherein each sub-request specifies a linear topology for a subset of the virtual nodes and virtual links within the mesh topology for the virtual network request, and the plurality of sub-requests collectively include all virtual links within the mesh topology for the virtual network request;
computing, independently for each sub-request, a respective chaining solution in which each virtual node in the subset of virtual nodes for which a linear topology is specified for the sub-request is mapped to a physical node on which resources sufficient for implementing the virtual node are available; and
combining, by the resource orchestrator, the respective chaining solutions for each of the sub-requests.

2. The method of claim 1 , wherein partitioning the virtual network request into a plurality of sub-requests comprises identifying all linear topologies within the mesh topology for the virtual network request in which the number of links is less than or equal to a predetermined maximum number of links.

3. The method of claim 1 , wherein partitioning the virtual network request into a plurality of sub-requests comprises identifying a set of linear topologies within the mesh topology for the virtual network request in which the number of virtual links in any two of the linear topologies in the set of linear topologies differs by no more than one.

4. The method of claim 1 , wherein partitioning the virtual network request into a plurality of sub-requests comprises identifying a set of linear topologies within the mesh topology for the virtual network request in which there are no overlapping virtual links between the linear topologies in the set of linear topologies.

5. The method of claim 1 , wherein:
for at least one of the sub-requests, computing the respective chaining solution comprises computing two or more chaining solutions for the sub-request; and
combining the respective chaining solutions for each of the sub-requests comprises:
selecting one of the two or more chaining solutions computed for the at least one sub-request; and
combining the selected chaining solution with respective chaining solutions for one or more sub-requests other than the at least one sub-request.

6. The method of claim 1 , wherein for two or more of the sub-requests, the respective chaining solutions are computed in parallel.

7. The method of claim 1 , further comprising:
configuring, by one or more resource orchestrators in the resource orchestration framework, resources of one or more of the plurality of physical nodes for implementation of the respective virtual nodes to which they are mapped by the mapping solution generated for the virtual network request.

8. The method of claim 1 , wherein:
at least two of the plurality of physical nodes reside in different ones of a plurality of domains in a multi-domain network; and
the resource orchestrator is one of a plurality of resource orchestrators in the resource orchestration framework, each of which coordinates resource usage in a respective one of the plurality of domains.

9. The method of claim 1 , wherein:
the virtual network request further specifies a resource requirement for at least one of the virtual links; and
for at least one of the sub-requests, computing the respective chaining solution comprises mapping a virtual node in the subset of virtual nodes for which a linear topology is specified for the sub-request to a physical node in response to determining that a physical link to the physical node meets the specified resource requirement for the at least one virtual link.

10. The method of claim 1 , wherein, for at least one of the sub-requests, computing the respective chaining solution comprises:
identifying a first physical node at which a resource requirement for a first virtual node in the linear topology for the sub-request is met;
mapping the first physical node to the first virtual node in a candidate chaining solution for the sub-request;
determining that a resource requirement for a second virtual node in the linear topology for the sub-request is met on a second physical node, the second physical node being a neighbor of the first physical node; and
mapping the second physical node to the second virtual node in the candidate chaining solution.

11. The method of claim 1 , wherein, for at least one of the sub-requests, computing the respective chaining solution comprises:
sending, by the resource orchestrator to another resource orchestrator in a network domain other than the network domain in which the resource orchestrator resides, a controller message comprising a partially mapped candidate chaining solution for the sub-request;
determining, by the other resource orchestrator, that a resource requirement for a given virtual node in the linear topology for the sub-request is met on a given physical node in the network domain other than the network domain in which the resource orchestrator resides; and
mapping the given physical node to the given virtual node in the candidate chaining solution.

12. A resource orchestration framework, comprising:
a plurality of vertices, each of which represents a respective one of a plurality of physical nodes in a network; and
a resource orchestrator;
wherein the resource orchestrator comprises:
a processor; and
a memory storing program instructions that when executed by the processor cause the processor to perform:
receiving a virtual network request specifying:
a set of virtual nodes;
a set of virtual links, each of which connects two of the virtual nodes in a mesh topology for the virtual network request; and
a resource requirement for at least one of the virtual nodes;

generating a mapping solution for the virtual network request in which each virtual node in the set of virtual nodes is mapped to a respective one of the plurality of physical nodes, wherein generating the mapping solution comprises:
partitioning the virtual network request into a plurality of sub-requests, wherein each sub-request specifies a linear topology for a subset of the virtual nodes and virtual links within the mesh topology for the virtual network request, and the plurality of sub-requests collectively include all virtual links within the mesh topology for the virtual network request;
initiating, for each sub-request, an independent computation of a respective chaining solution in which each virtual node in the subset of virtual nodes for which a linear topology is specified for the sub-request is mapped to a physical node on which resources sufficient for implementing the virtual node are available; and
combining the respective chaining solutions for each of the sub-requests.

13. The resource orchestration framework of claim 12 , wherein partitioning the virtual network request into a plurality of sub-requests comprises id

Assignees

• Fujitsu Ltd

Inventors

• Zhang Qiong
• Palacharla Paparao
• Ikeuchi Tadashi
• Wang Xi
• Kim Inwoong

Classifications

• H04L49/70

  Virtual switches · CPC title

• H04L47/827

  Aggregation of resource allocation or reservation requests · CPC title

• H04L43/0876

  Network utilisation, e.g. volume of load or congestion level · CPC title

• H04L45/586

  of virtual routers · CPC title

• H04L47/785 Primary

  among multiple network domains, e.g. multilateral agreements · CPC title