Time-efficient network function virtualization architecture

Patent metadata

Field	Value
Publication number	US-2016234077-A1
Application number	US-201514616760-A
Country	US
Kind code	A1
Filing date	Feb 9, 2015
Priority date	Feb 9, 2015
Publication date	Aug 11, 2016
Grant date	—

Abstract

A method for designing a Network Function Virtualization (NFV) architecture includes accepting a definition of multiple Virtual Network Functions (VNFs), and of one or more packet types having respective occurrence probabilities, wherein each packet type is associated with a respective subset of the VNFs that are to be applied to packets of that packet type. Information on multiple available physical computers, each capable of running only a partial subset of the multiple VNFs, is further accepted. The VNFs are allocated to the physical computers by applying an optimality criterion to definition and the information.

First claim

1 . A method for designing a Network Function Virtualization (NFV) architecture, the method comprising:
accepting a definition of multiple Virtual Network Functions (VNFs), and of one or more packet types having respective occurrence probabilities, wherein each packet type is associated with a respective subset of the VNFs that are to be applied to packets of that packet type; further accepting information on multiple available physical computers, wherein each physical computer is capable of running only a partial subset of the multiple VNFs; and allocating the VNFs to the physical computers by applying an optimality criterion to the definition and the information.

2 . The method according to claim 1 , wherein allocating the VNFs comprises generating a graph in which each vertex represents a respective VNF and each edge indicates that the VNFs represented by the vertices of that edge are allocated jointly to the same physical computer, and processing the graph in accordance with the optimality criterion.

3 . The method according to claim 2 , wherein processing the graph comprises partitioning the graph into subsets, wherein each subset comprises the vertices corresponding to respective VNFs that are allocated jointly to the same respective physical computer.

4 . The method according to claim 3 , wherein partitioning the graph comprises selecting the subsets based on weights assigned to one or more edges of the graph.

5 . The method according to claim 4 , and comprising assigning the weights based on the definition.

6 . The method according to claim 4 , wherein selecting the subsets comprises maximizing a sum of weights of the edges included in the subsets.

7 . The method according to claim 6 , wherein selecting the subsets comprises maximizing the sum of weights in each subset individually.

8 . The method according to claim 3 , wherein partitioning the graph comprises defining at least two subsets that have a different number of vertices.

9 . The method according to claim 3 , wherein partitioning the graph comprises partitioning the graph into a partition that comprises pairwise non-adjacent edges, wherein no two edges in the partition share a common vertex of the graph.

10 . The method according to claim 3 , wherein partitioning the graph comprises selecting each of the subsets iteratively, by excluding the vertices of an already selected subset from the graph before selecting another subset.

11 . The method according to claim 1 , and comprising re-allocating the VNFs to the physical computers in response to a change in the definition or the information.

12 . The method according to claim 1 , wherein the optimality criterion aims to minimize a latency of applying the VNFs to the packets by the physical computers.

13 . The method according to claim 1 , wherein the optimality criterion aims to set an upper bound on a latency of applying the VNFs to the packets by the physical computers.

14 . The method according to claim 1 , wherein the optimality criterion aims to minimize a network bandwidth consumed by applying the VNFs when allocated to the physical computers.

15 . An apparatus for designing a Network Function Virtualization (NFV) architecture, the apparatus comprising:
a memory, which is configured to hold a definition of multiple Virtual Network Functions (VNFs), and of one or more packet types having respective occurrence probabilities, wherein each packet type is associated with a respective subset of the VNFs that are to be applied to packets of that packet type, and to further hold information on multiple available physical computers, wherein each physical computer is capable of running only a partial subset of the multiple VNFs; and a processor, which is configured to allocate the VNFs to the physical computers by applying an optimality criterion to the definition and the information.

16 . The apparatus according to claim 15 , wherein the processor is configured allocate the VNFs by generating a graph in which each vertex represents a respective VNF and each edge indicates that the VNFs represented by the vertices of that edge are allocated jointly to the same physical computer, and to process the graph in accordance with the optimality criterion.

17 . The apparatus according to claim 16 , wherein the processor is configured to process the graph by partitioning the graph into subsets, wherein each subset comprises the vertices corresponding to respective VNFs that are allocated jointly to the same respective physical computer.

18 . The apparatus according to claim 17 , wherein the processor is configured to select the subsets based on weights assigned to one or more edges of the graph.

19 . The apparatus according to claim 18 , wherein the processor is configured to assign the weights based on the definition.

20 . The apparatus according to claim 18 , wherein the processor is configured to select the subsets by maximizing a sum of weights of the edges included in the subsets.

21 . The apparatus according to claim 20 , wherein the processor is configured to select the subsets by maximizing the sum of weights in each subset individually.

22 . The apparatus according to claim 17 , wherein the processor is configured to partition the graph by defining at least two subsets that have a different number of vertices.

23 . The apparatus according to claim 17 , wherein the processor is configured to partition the graph into a partition that comprises pairwise non-adjacent edges, wherein no two edges in the partition share a common vertex of the graph.

24 . The apparatus according to claim 17 , wherein the processor is configured to select each of the subsets iteratively, by excluding the vertices of an already selected subset from the graph before selecting another subset.

25 . The apparatus according to claim 15 , wherein the processor is configured to re-allocate the VNFs to the physical computers in response to a change in the definition or the information.

26 . The apparatus according to claim 15 , wherein the optimality criterion aims to minimize a latency of applying the VNFs to the packets by the physical computers.

27 . The apparatus according to claim 15 , wherein the optimality criterion aims to set an upper bound on a latency of applying the VNFs to the packets by the physical computers.

28 . The apparatus according to claim 15 , wherein the optimality criterion aims to minimize a network bandwidth consumed by applying the VNFs when allocated to the physical computers.

Assignees

• Mellanox Technologies Ltd

Inventors

• Rottenstreich Ori
• Goldenberg Dror

Classifications

• H04L47/12

  Avoiding congestion; Recovering from congestion · 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/50 Primary

  Network service management, e.g. ensuring proper service fulfilment according to agreements · CPC title

• H04L41/5054

  Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components · CPC title