A Utility-Based Optimization Framework for Edge Service Entity Caching

Edge computing is one of the emerging technologies aiming to enable timely computation at the network edge. With virtualization technologies, the role of the traditional edge providers is separated into two: edge infrastructure providers (EIPs), who manage the physical edge infrastructure, and edge service providers (ESPs), who purchase slices of physical resources (e.g., CPU, bandwidth, memory space, disk storage) from EIPs and then cache service entities to offer their own value-added services to end users. When an ESP caches a service entity in an edge server, the ESP has to pay some fees (i.e, the cache cost) to the EIP that owns the edge server. One of the fundamental problems in edge virtualization is the so-called service entity caching problem, i.e., where to place service entities for an ESP to minimize the cache cost. In this paper, we study the service entity caching problem from the utility perspective. We use `utility' to denote the positive impact on a client from caching a service entity in an edge server, and the exact meaning of utility can vary depending on specific scenarios. We formulate the Utility-based Service Entity Caching (UtilitySEC) problem, which can be generalized to many existing problems by modifying the `utility'. We prove that the UtilitySEC problem is NP-complete and design an approximation algorithm for it. Extensive simulations are conducted to evaluate the performance of the proposed framework.