Joint placement and chaining of virtual network functions for virtualized systems based on a scalable genetic algorithm

Patent metadata

Field	Value
Publication number	US-11934856-B2
Application number	US-201917263033-A
Country	US
Kind code	B2
Filing date	Jul 30, 2019
Priority date	Jul 30, 2018
Publication date	Mar 19, 2024
Grant date	Mar 19, 2024

Abstract

A system performs joint placement and chaining of virtual network functions (VNFs) based on a genetic algorithm in response to a request for virtual network services, including an in-line service. The request includes a description of a virtual network of VNFs and virtual links connecting the VNFs. A description of a physical network including servers and physical links is provided. Each chromosome in a population encodes a mapping between the virtual links enumerated to form a locus and a corresponding sequence of server pairs. Each chromosome is evaluated against objective functions subject to constraints to identify a chromosome as a solution. The VNFs are placed on the servers according to the mapping encoded in the identified chromosome. According to the mapping, each VNF is mapped to one of the servers and each virtual link is mapped to a path composed of one or more of the physical links.

First claim

What is claimed is:

1. A method for joint placement and chaining of a scalable number of VNFs, comprising:
receiving a request for virtual network services, the request including a first description of a virtual network including the VNFs and virtual links connecting the VNFs, wherein a subset of the VNFs form a server function chain to provide an in-line network service;
obtaining a second description of a physical network including servers and physical links;
initializing a population of chromosomes, wherein each chromosome encodes a mapping between the virtual links enumerated to form a locus and a corresponding sequence of server pairs, wherein end-point VNFs of each virtual link are mapped to a server pair connected by one or more of the physical links;
evaluating, for each of a plurality of generations of the population which evolves according to a genetic algorithm, each chromosome within the population against a set of objective functions subject to a set of constraints to identify a chromosome as a solution, wherein the objective functions include: a cost function for transporting traffic of the virtual network services through the physical links, wherein the cost function is a function of a distance between each server pair, a bandwidth required by each virtual link, and a cost for transporting one traffic unit through one physical hop distance; and
placing the VNFs on the servers according to the mapping encoded in the identified chromosome, which maps each VNF to one of the servers and each virtual link to a path composed of one or more of the physical links.

2. The method of claim 1 , wherein each chromosome in the population of chromosomes complies with affinity and anti-affinity requirements specified by the request with respect to the placement of the VNFs.

3. The method of claim 1 , further comprising: initializing the population of chromosomes in which each virtual link is randomly assigned to a path connecting a server pair.

4. The method of claim 1 , wherein evaluating each chromosome further comprises:
checking the chromosome prior to evaluation of the chromosome against the objective functions for an invalid genotype, wherein the invalid genotype includes an invalid mapping between an end-point VNF of a virtual link and a server; and
fixing the invalid genotype if the chromosome contains the invalid genotype.

5. The method of claim 1 , wherein evaluating each chromosome further comprises:
identifying a given virtual link specified by two end-point VNFs mapped to two non-adjacent servers in the chromosome; and
finding a shortest path composed of two or more physical links between the two non-adjacent servers prior to evaluation of the chromosome against the objective functions.

6. The method of claim 1 , wherein the first description indicates available resources on each server and each physical link, and the second description indicates resources including end-to-end delays required by the virtual network service.

7. The method of claim 1 , wherein the objective functions include: a best-fit function which finds the required server resources including capacities of a central processing unit (CPU), memory and storage, to be allocated to the virtual network services in view of remaining server resources.

8. The method of claim 1 , wherein evaluating each chromosome further comprises:
evaluating each chromosome against the objective functions subject to the set of constraints with one or more of the constraints relaxed with respect to Quality of Service (QoS) for the physical network to provide best-effort virtualized services.

9. The method of claim 1 , wherein evaluating each chromosome further comprises:
evaluating each chromosome against the objective functions subject to all of the constraints in the set of constraints with respect to a Service Level Agreement (SLA) for the physical network to provide dedicated virtualized services.

10. The method of claim 1 , wherein the set of constraints include a maximum value of an end-to-end delay for each virtual link of each virtual network service.

11. The method of claim 1 , wherein the set of constraints include constraints for enforcing valid placement of the VNFs and valid allocation of the physical links in view of physical network topology.

12. A network node comprising:
processing circuitry; and
memory to store instructions executable by the processing circuitry for joint placement and chaining of a scalable number of VNFs,
the network node operative to:
receive a request for virtual network services, the request including a first description of a virtual network including the VNFs and virtual links connecting the VNFs, wherein a subset of the VNFs form a server function chain to provide an in-line network service;
obtain a second description of a physical network including servers and physical links;
initialize a population of chromosomes, wherein each chromosome encodes a mapping between the virtual links enumerated to form a locus and a corresponding sequence of server pairs, wherein end-point VNFs of each virtual link are mapped to a server pair connected by one or more of the physical links;
evaluate, for each of a plurality of generations of the population which evolves according to a genetic algorithm, each chromosome within the population against a set of objective functions subject to a set of constraints to identify a chromosome as a solution, wherein the objective functions include: a cost function for transporting traffic of the virtual network services through the physical links, wherein the cost function is a function of a distance between each server pair, a bandwidth required by each virtual link, and a cost for transporting one traffic unit through one physical hop distance; and
place the VNFs on the servers according to the mapping encoded in the identified chromosome, which maps each VNF to one of the servers and each virtual link to a path composed of one or more of the physical links.

13. The network node of claim 12 , wherein each chromosome in the population of chromosomes complies with affinity and anti-affinity requirements specified by the request with respect to the placement of the VNFs.

14. The network node of claim 12 , wherein the network node is further operative to: initialize the population of chromosomes in which each virtual link is randomly assigned to a path connecting a server pair.

15. The network node of claim 12 , wherein when evaluating each chromosome, the network node is further operative to:
check the chromosome prior to evaluation of the chromosome against the objective functions for an invalid genotype, wherein the invalid genotype includes an invalid mapping between an end-point VNF of a virtual link and a server; and
fix the invalid genotype if the chromosome contains the invalid genotype.

16. The network node of claim 12 , wherein when evaluating each chromosome, the network node is further operative to:
identify a given virtual link specified by two end-point VNFs mapped to two non-adjacent servers in the chromosome; and
find a shortest path composed of two or more physical links between the two non-adjacent servers prior to evaluation of the chromosome against the objective functions.

17. The network node of claim 12 , wherein the first description indicates available resources on each server and each physical link, and the second description indicates resources including end-to-end delays required by the virtual network service.

18. The network node of claim 12 , wherein the objective functions include: a

Assignees

• Lahlou Laaziz
• Kara Nadjia
• Edstroem Claes Goeran Robert
• Ericsson Telefon Ab L M

Inventors

• Lahlou Laaziz
• Kara Nadjia
• Edström Claes Göran Robert

Classifications

• G06F9/45558 Primary

  Hypervisor-specific management and integration aspects · CPC title

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/5077

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• H04L41/5019

  Ensuring fulfilment of SLA · CPC title

• H04L43/0876

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