  Accommodating services at the network edge is favorable for time-sensitive
applications. However, maintaining service usability is resource-consuming in
terms of pulling service images to the edge, synchronizing databases of service
containers, and hot updates of service modules. Accordingly, it is critical to
determine which service to place based on the received user requests and
service refreshing (maintaining) cost, which is usually neglected in existing
studies. In this work, we study how to cooperatively place timely refreshing
services and offload user requests among edge servers to minimize the backhaul
transmission costs. We formulate an integer non-linear programming problem and
prove its NP-hardness. This problem is highly non-tractable due to the complex
spatial-and-temporal coupling effect among service placement, offloading, and
refreshing costs. We first decouple the problem in the temporal domain by
transforming it into a Markov shortest-path problem. We then propose a
light-weighted Discounted Value Approximation (DVA) method, which further
decouples the problem in the spatial domain by estimating the offloading costs
among edge servers. The worst performance of DVA is proved to be bounded. 5G
service placement testbed experiments and real-trace simulations show that DVA
reduces the total transmission cost by up to 59.1% compared with the
state-of-the-art baselines.
