User Experience Oriented Edge Server Placement

Abstract Edge computing holds promising prospects and addresses certain limitations of cloud computing. In the realm of edge computing, service providers deploy edge servers in close proximity to users to minimize network latency. To optimize the utilization of limited edge servers, service providers typically adopt a decentralized approach to their placement. However, in real-world edge computing environments, runtime failures are bound to occur after the placement of edge servers, significantly degrading the user experience. Therefore, edge server placement strategies must consider scenarios involving edge server failures.In general, redundant placement techniques are employed to ensure the reliability of services deployed on edge servers. In practice, edge servers consist of one or more physical machines, which leads us to refer to the physical edge server placement as the PESP problem. From the perspective of mobile users, the PESP solution aims to provide cost-effective and stable services. We measure service stability using a robustness metric and, for the first time, introduce the average utility indicator to gauge service efficiency. Average utility pertains to the performance users obtain from edge servers, such as CPU performance. When placing edge servers, we take into account both average utility and robustness to ensure an optimal user experience.In this paper, we formally model the problem of user experience-oriented physical edge server placement (PESPU) and prove its NP-hardness. To tackle this problem, we propose an optimization method based on integer programming (PESPU-O) to find optimal solutions for small-scale problems. For large-scale problems, we present three heuristics to find solutions. Finally, we conduct experiments using real-world datasets to demonstrate the effectiveness and efficiency of our approaches.