Optimization of the Locations of Virtual Network Functions

In traditional networks, the network functions are implemented as physical appliances which are called middleboxes and these middleboxes need to be deployed in predetermined locations throughout the network. Therefore one of the most important disadvantages of using middleboxes is that each network function deployment requires a great deal of human work. During their operation, middleboxes need maintenance which also demands for massive human work. Therefore using middleboxes for each network function puts a constraint on the flexibility of the network. Network Function Virtualization (NFV) is a proposed architectural framework which introduces the virtualization of network functions. In NFV, each network function is implemented as software and deployed on data center servers which offers greater network flexibility with the ability of run-time network service deployment throughout the network. With this technology, the places of network functions can be determined for satisfying different requirements such as Quality of Service (QoS) for end-users. Determining optimal locations for Virtual Network Functions (VNFs) is an open research area. In this research, the optimal placement of VNFs is studied. The objective of this work is determined to minimize the end-to-end Round Trip Time (RTT) between the end users and the deployed network functions while also minimizing the number of data centers used.First, the problem is formulated using Integer Linear Programming (ILP) and it is shown that it is NP-hard. Therefore an updated problem definition is formulated to propose a heuristic. The proposed heuristic uses the knapsack problem notion to solve the problem in a smaller amount of time with a trade-off in objective value. Lastly, for the proof of concept, the updated problem definition is also formulated using ILP and the proposed heuristic and the ILP formulation are compared under different scenarios.Electrical Engineerin