Delay and QoS Aware Low Complex Optimal Service Provisioning for Edge Computing
- 12 September 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Vehicular Technology
- Vol. 72 (1) , 1169-1183
Abstract
Edge computing can be used as a distributed counterpart of the cloud computing, and task offloading with much shorter delays can be achieved. In general, edge servers are resource-limited, but the services are becoming further diversified to meet the ever-increasing user demand. When an edge server cannot process the received service request of a particular service type for not locally having the corresponding service execution image, the request needs to be forwarded to another on which the particular image is installed. In this paper, an optimal scheduling method that forwards such requests is proposed by using the variant multiple-knapsack framework. Then, to find the optimal solution, we propose to reformulate it as an integer linear program. As the problem size increases, however, the problem easily becomes intractable, so we propose a distributed solution by using both Lagrangian relaxation and decomposition theory. To evaluate the effectiveness of the proposed approaches, we carry out simulations with different network layouts and with different request arrival scenarios. The evaluation results show that the centralized Lagrange dual solution can yield near-optimal solutions. In addition, the decomposed distributed solution can significantly reduce the computational and operational complexity at the expense of the total reward.Keywords
Funding Information
- National Science and Technology Council (NSTC 110-2221-E-030-002, 111-2221-E-030-011)
- National Research Foundation of Korea
- Korea government (2021R1F1A1059109)
This publication has 25 references indexed in Scilit:
- Edge Computing: Vision and ChallengesIEEE Internet of Things Journal, 2016
- Joint Optimization of Task Scheduling and Image Placement in Fog Computing Supported Software-Defined Embedded SystemIEEE Transactions on Computers, 2016
- A tutorial on decomposition methods for network utility maximizationIEEE Journal on Selected Areas in Communications, 2006
- A Polynomial Time Approximation Scheme for the Multiple Knapsack ProblemSIAM Journal on Computing, 2005
- The Lagrangian Relaxation Method for Solving Integer Programming ProblemsManagement Science, 2004
- Knapsack Problems2004
- Interior-point methodsJournal of Computational and Applied Mathematics, 2000
- An Applications Oriented Guide to Lagrangian RelaxationInterfaces, 1985
- A new polynomial-time algorithm for linear programming1984
- Validation of subgradient optimizationMathematical Programming, 1974