An Efficient Service Function Chains Orchestration Algorithm for Mobile Edge Computing

• Xiulei Wang,
• Bo Xu,
• Fenglin Jin,

Vol. 15, No. 12, December 31, 2021
10.3837/tiis.2021.12.006, Download Paper (Free):

• Mobile Edge Computing
• Internet of Things
• Service function chain
• Column Generation
• network function virtualization

Abstract

The dynamic network state and the mobility of the terminals make the service function chain (SFC) orchestration mechanisms based on static and deterministic assumptions hard to be applied in SDN/NFV mobile edge computing networks. Designing dynamic and online SFC orchestration mechanism can greatly improve the execution efficiency of compute-intensive and resource-hungry applications in mobile edge computing networks. In order to increase the overall profit of service provider and reduce the resource cost, the system running time is divided into a sequence of time slots and a dynamic orchestration scheme based on an improved column generation algorithm is proposed in each slot. Firstly, the SFC dynamic orchestration problem is formulated as an integer linear programming (ILP) model based on layered graph. Then, in order to reduce the computation costs, a column generation model is used to simplify the ILP model. Finally, a two-stage heuristic algorithm based on greedy strategy is proposed. Four metrics are defined and the performance of the proposed algorithm is evaluated based on simulation. The results show that our proposal significantly provides more than 30% reduction of run time and about 12% improvement in service deployment success ratio compared to the Viterbi algorithm based mechanism.

Statistics

Cite this article