  Mobile Edge Computing (MEC) pushes computing functionalities away from the
centralized cloud to the network edge, thereby meeting the latency requirements
of many emerging mobile applications and saving backhaul network bandwidth.
Although many existing works have studied computation offloading policies,
service caching is an equally, if not more important, design topic of MEC, yet
receives much less attention. Service caching refers to caching application
services and their related databases/libraries in the edge server (e.g.
MEC-enabled BS), thereby enabling corresponding computation tasks to be
executed. Because only a small number of application services can be cached in
resource-limited edge server at the same time, which services to cache has to
be judiciously decided to maximize the edge computing performance. In this
paper, we investigate the extremely compelling but much less studied problem of
dynamic service caching in MEC-enabled dense cellular networks. We propose an
efficient online algorithm, called OREO, which jointly optimizes dynamic
service caching and task offloading to address a number of key challenges in
MEC systems, including service heterogeneity, unknown system dynamics, spatial
demand coupling and decentralized coordination. Our algorithm is developed
based on Lyapunov optimization and Gibbs sampling, works online without
requiring future information, and achieves provable close-to-optimal
performance. Simulation results show that our algorithm can effectively reduce
computation latency for end users while keeping energy consumption low.
