  This paper studies an online service caching problem, where an edge server,
equipped with a prediction window of future service request arrivals, needs to
decide which services to host locally subject to limited storage capacity. The
edge server aims to minimize the sum of a request forwarding cost (i.e., the
cost of forwarding requests to remote data centers to process) and a service
instantiating cost (i.e., that of retrieving and setting up a service).
Considering request patterns are usually non-stationary in practice, the
performance of the edge server is measured by dynamic regret, which compares
the total cost with that of the dynamic optimal offline solution. To solve the
problem, we propose a randomized online algorithm with low complexity and
theoretically derive an upper bound on its expected dynamic regret. Simulation
results show that our algorithm significantly outperforms other
state-of-the-art policies in terms of the runtime and expected total cost.
