Optimal VNF placement: Addressing Multiple min-cost solutions

Network Function Virtualization (NFV) can lower the CAPEX and/or OPEX for service providers and allows to deploy services quickly. Randomly placing Network Functions (NF) in the network can cause excessive use of resources such as bandwidth (BW). Consequently, many researchers proposed optimal placement strategies, which place NFs with minimum cost while providing a requested Quality of Service (QoS) level. The cost is typically based on the usage of resources in the network such as BW, memory, etc. In this paper, we use an Integer Linear Programming (ILP) model designed for the Virtual Network Function Embedding Problem (VNFEP) in wired and wireless networks and solve it with different solvers. We then solve the optimization problem for a sequence of arriving requests and measure acceptance ratio and placement costs. The results gathered from different solvers show different acceptance ratios while all the elements of the models such as the network topology, its available resources, and requested resources are the same. The underlying cause is that each of the solvers uses (potentially) a different optimal solution, as the optimization problem frequently has more than a single min-cost solution. Depending on the selected min-cost solution, the placement of future requests is impacted differently. Two approaches are discussed in this paper to deal with this issue. Firstly, we identify important factors in choosing between multiple min-cost solutions and design a heuristic which smartly selects among all available min-cost placement options. The results show that our heuristic provides a higher acceptance ratio compared to randomly choosing one of the min-cost solutions. Secondly, we provide a joint optimization model which provides an optimal placement of both previous and current requests at once. In this joint optimization model, a new request and previously placed requests will be placed in the network optimally. This may potentially cause a change in the placement of previously placed NFs. The results show that each approach has its advantages and disadvantages. We show in our results that both methods increase the acceptance ratio in comparison to any optimization method that uses the first optimal placement it finds