Edge Service Selection in a Virtual Service Marketplace

Abstract: A brokerless edge service marketplace could play a significant role in enabling an eco- system where a large number of edge providers and Communication Service Providers (CSPs) offer Mobile Edge Infrastructure Services (EISs) to providers of edge-based applications and services. The marketplace would be the bridge between EIS providers and their customers, managing the relations between actors in the mobile edge eco- system. One of the key services of the marketplace is service selection where not only a list of EISs matching the customers’ demands is provided but also enables service selection based on the customers’ requirements to fully automate the process.We firstly consider different selection scenarios and investigate essential parameters for service selection in such a marketplace, including (i) important attributes of EISs such as coverage area, latency, pricing, etc, and (ii) the requirements of edge-based applications such as latency and reliability. We formulate how these application requirements can be fulfilled by choosing the right set of EISs among available services in the marketplace as two different optimization problems considering average latency and cost as separate objectives to minimize. First, we relax the objective function in average delay minimization problem, which is a linear-fractional programming problem. We solve the relaxed version of the problem by Branch and bound (BnB) and Bound and Branch with Priority Queue (BnBPQ) algorithms. Additionally, we relax the objective function in total monetary cost minimization problem which is an integer linear programming problem. We propose Best Fit (BF) and Improved Best Fit (IBF) algorithms to solve the problem. Furthermore, the IBM CPLEX Optimizer [1] is also implemented to solve the two problems. The evaluation shows that the algorithms we implemented can solve the problems with results close to optimal as compared to the results of exhaustive search and shorter run time than exhaustive search. Meanwhile, the CPLEX can solve the problem well, but it’s not scalable for huge problem instances since the problems are NP-complete and not solvable in polynomial time.