Method and system for network function placement

{
  "publication_number": "US9503391B2",
  "country": "US",
  "kind": "B2",
  "title": "Method and system for network function placement",
  "abstract": "A method implemented for network function placement is disclosed. The method optimizes network function placement for each traffic flow, to minimize the overall inter-pod traffic volume. For each traffic flow going through a data center, the method initiates a pod list. The network functions of the traffic flow is sorted in a descending order by resource demanded. Then one network function is selected one at a time according to the descending order. For each network function, the pods in the pod list is sorted in an ascending order by resource available in each pod. The method selects a first pod for the network function when possible. When no pod in the pod list has enough resource for the network function, the method adds a pod with the most available resource from a pod pool to the pod list, and selects the added pod for the network function.",
  "claims": [
    "1. A method implemented in an electronic device coupled to a network, wherein traffic of the network is routed as a set of traffic flows, wherein each traffic flow is operated on by a chain of network functions, wherein each network function is to be performed by software running on a server, wherein each server resides at a pod, wherein each pod is a hardware unit coupled to the network, the method comprising: assigning the network functions of each traffic flow to a respective pod or pods, wherein the assigning includes for each traffic flow: initiating a pod list, wherein the pod list contains no pod initially and wherein selected pods are added to the pod list to provide resources for the network functions; sorting network functions within a corresponding chain of the traffic flow in a descending order by resource demanded, wherein the resource demanded by each network function is predetermined; and selecting one network function of the traffic flow at a time according to the descending order, and for each selected network function of the traffic flow: sorting pods in the pod list in an ascending order by resources available in each pod; selecting a pod within the pod list for the network function to reside in that has enough resources available for the network function by following the ascending order of the pods in the pod list; when no pod in the pod list has enough resources available for the network function to reside, adding a pod from a pod pool to the pod list and selecting the added pod for the network function to reside, wherein the added pod is the pod outside of the pod list with the most available resources in the pod pool; and reassigning one or more network functions assigned to a pod of the selected pods with the least resources consumed into a pod of the selected pods with the most available resources to reduce a total number of selected pods, when the pod with the most available resources has sufficient resources to accommodate consumed resources of the pod with the least resources consumed; and causing the placement of the network functions in the selected pods.",
    "2. The method of claim 1, wherein the resource demanded by each network function is a bandwidth consumed by the network function.",
    "3. The method of claim 1, wherein the resource demanded by each network function is a computing power consumed by the network function.",
    "4. The method of claim 1, wherein the resource demanded by each network function is at least one of a data storage space and a memory space consumed by the network function.",
    "5. The method of claim 1, wherein the pod pool is a subset of a set of pods coupled to the network, and wherein the pod pool excludes some pods determined not suitable for hosting a network function.",
    "6. The method of claim 1, wherein at least one traffic flow arriving at a pod is from an optical switching device of an optical network.",
    "7. The method of claim 1, wherein the network follows a software-defined network (SDN) architecture and is controlled by an SDN controller, and wherein the electronic device is an application server that interacts with the SDN controller.",
    "8. An electronic devices for a network, wherein traffic of the network is routed as a set of traffic flows, wherein each traffic flow is operated on by a chain of network functions, wherein each network function is to be performed by software running on a server, wherein each server resides at a pod, wherein each pod is a hardware unit coupled to the network, the electronic device comprising: a processor and non-transitory machine-readable storage medium containing instructions, which when executed by the processor, cause the electronic device to, assign the network functions of each traffic flow to a respective pod or pods, by performing operations to: for each traffic flow: initiate a pod list, wherein the pod list contains no pod initially and wherein selected pods are added to the pod list to provide for the network functions; sort network functions within a corresponding chain of the traffic flow in a descending order by resource demanded, wherein the resource demanded by each network function is predetermined; and select one network function of the traffic flow at a time according to the descending order, and for each selected network function of the traffic flow: sort pods in the pod list in an ascending order by resources available in each pod; select a pod within the pod list for the network function to reside in that has enough resources available for the network function by following the ascending order of the pods in the pod list; when no pod in the pod list has enough resources available for the network function to reside, add a pod from a pod pool to the pod list and select the added pod for the network function to reside, wherein the added pod is the pod outside of the pod list with the most available resources in the pod pool; and reassign one or more network functions assigned to a pod of the selected pods with the least resources consumed into a pod of the selected pods with the most available resources to reduce a total number of selected pods, when the pod with the most available resources has sufficient resources to accommodate consumed resources of the pod with the least resources consumed; and cause the placement of the network functions in the selected pods.",
    "9. The electronic device of claim 8, wherein the resource demanded by each network function is a bandwidth consumed by the network function.",
    "10. The electronic device of claim 8, wherein the resource demanded by each network function is a computing power consumed by the network function.",
    "11. The electronic device of claim 8, wherein the resource demanded by each network function is at least one of a data storage space and a memory space consumed by the network function.",
    "12. The electronic device of claim 8, wherein at least one traffic flow arriving at a pod is from an optical switching device of an optical network.",
    "13. The electronic device of claim 8, wherein the network follows a software-defined network (SDN) architecture and is controlled by an SDN controller, and wherein the electronic device is an application server that interacts with the SDN controller of the SDN.",
    "14. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations at an electronic device coupled to a network, wherein traffic of the network is routed as a set of traffic flows, wherein each traffic flow is operated on by a chain of network functions, wherein each network function is to be performed by software running on a server, wherein each server resides at a pod, wherein each pod is a hardware unit coupled to the network, the operations comprising: assigning the network functions of each traffic flow to a respective pod or pods, wherein the assigning includes for each traffic flow; initiating a pod list, wherein the pod list contains no pod initially and wherein selected pods are added to the pod list to provide resources for the network functions; sorting network functions within a corresponding chain of the traffic flow in a descending order by resource demanded, wherein the resource demanded by each network function is predetermined; and selecting one network function of the traffic flow at a time according to the descending order and for each selected network function of the traffic flow: sorting pods in the pod list in an ascending order by resources available in each pod; selecting a pod within the pod list for the network function to reside in that has enough resources available for the network function by following the ascending order of the pods in the pod list; when no pod in the pod list has enough resources available for the network function to reside, adding a pod from a pod pool of the network to the pod list and selecting the added pod for the network function to reside, wherein the added pod is the pod outside of the pod list with the most available resources in the pod pool; and reassigning one or more network functions assigned to a pod of the selected pods with the least resources consumed into a pod of the selected pods with the most available resources to reduce a total number of selected pods, when the pod with the most available resources has sufficient resources to accommodate consumed resources of the pod with the least resources consumed; and causing the placement of the network functions in the selected pods.",
    "15. The non-transitory machine-readable medium of claim 14, wherein the resource demanded by each network function is a bandwidth consumed by the network function.",
    "16. The non-transitory machine-readable medium of claim 14, wherein the resource demanded by each network function is a computing power consumed by the network function.",
    "17. The non-transitory machine-readable medium of claim 14, wherein the resource demanded by each network function is at least one of a storage space and a memory space consumed by the network function.",
    "18. The non-transitory machine-readable medium of claim 14, wherein at least one traffic flow arriving at a pod is from an optical switching device of an optical network."
  ],
  "description_excerpt": "The embodiments of the invention are related to the field of networking. More specifically, the embodiments of the invention relate to a method and system for network function place of a network.\n\nThe recent advances in software engineering and high-performance commodity servers facilitate virtualization of network function (NFs). NFs traditionally delivered on proprietary and application-specific equipment now can be realized in software running on generic server hardware (e.g., commercial off-the-shelf (COTS) servers). The technology, coined as network function virtualization (NFV), is gaining increasing popularity with network operators.\n\nNFV may be implemented at various parts of a network, such as serving gateway (S-GW), packet data network gateway (P-GW), serving GPRS (general packet radio service) support node (SGSN), gateway GPRS support node (GGSN), broadband remote access server (BRAS), and provider edge (PE) routers. NFV can be also implemented to support various services or appliances such as deep packet inspection (DPI), firewall (FW), virus scanning (VS), Intrusion Detection and Prevention (IDP), and network address translation (NAT). Because NFV can be flexibly instantiated and torn down in an operator's cloud/data center (DC) when and where needed, and it provides high resource utilization and short service development cycle, network operators can achieve great capital expenditure (Capex) and operational expenditure (Opex) savings.",
  "cpc": [
    "H04L 41/0895",
    "G06F 9/50",
    "G06F 9/5077",
    "H04L 41/0806",
    "H04L 41/0896",
    "H04L 41/122",
    "H04L 41/40",
    "H04L 41/5041",
    "H04L 47/748",
    "H04L 47/782",
    "H04L 47/822"
  ],
  "ipc": [
    "H04L 12/911",
    "G06F 9/50",
    "H04L 12/24",
    "H04L 12/28"
  ],
  "assignees": [
    "Telefonaktiebolaget LM Ericsson AB"
  ],
  "inventors": [
    "Ming Xia",
    "Meral Shirazipour",
    "Ying Zhang"
  ],
  "filing_date": "2014-07-10",
  "publication_date": "2016-11-22",
  "grant_date": "2016-11-22",
  "priority_date": "2014-04-11",
  "application_number": "US-201414328471-A",
  "family_id": "54266024",
  "cited_by_count": 16,
  "citations": [
    "US20040264500A1",
    "US20100260500A1",
    "US20110131431A1",
    "US20120099863A1",
    "US20130014101A1",
    "US20150365462A1",
    "US20130272305A1",
    "US20130287397A1",
    "US20140064283A1",
    "US20140099119A1",
    "US20140119728A1",
    "US20140201375A1",
    "US20150098700A1",
    "US20150113144A1",
    "US20150181317A1",
    "US20150207586A1"
  ]
}