Energy-Delay Tradeoff for Virtual Machine Placement in Virtualized Multi-Access Edge Computing: A Two-Sided Matching Approach

By decoupling network functions from the underlying physical machines (PMs) at the edge of the networks, the virtualized multi-access edge computing (MEC) enables deployment of new network services and elastic network scaling to reduce maintenance costs in a more flexible, scalable and cost-effective manner. Although there are appealing performance gains to be achieved, the placement of virtual machines (VMs) on top of the sharing PMs to support computation-intensive applications for the smart mobile devices becomes a major challenge, especially for an increasing network scale. In this paper, we attempt to deal with the VM placement problem in virtualized MEC system, which is targeted for finding a performance balance between energy consumption and computing/offloading delay. To capture such a tradeoff for VM placement, we formulate a weighted sum based cost minimization problem as a pure 0-1 integer linear programming problem, which is NP-complete and very complex to solve with lower complexity. Based on the one-to-one mapping relation constraint, the VM placement problem is converted into a many-to-many two-sided matching problem between the VM instances and the PMs. Motivated by the student project allocation problem, we develop an extended two-sided matching algorithm with lower computational complexity for solving the many-to-many matching problem. Simulation results are presented to demonstrate the effectiveness of our proposed matching algorithm, and the normalization factor is of great significance to obtain lower total cost.