  This paper studies a problem of jointly optimizing two important operations
in mobile edge computing without knowing future requests, namely service
caching, which determines which services to be hosted at the edge, and service
routing, which determines which requests to be processed locally at the edge.
We aim to address several practical challenges, including limited storage and
computation capacities of edge servers and unknown future request arrival
patterns. To this end, we formulate the problem as an online optimization
problem, in which the objective function includes costs of forwarding requests,
processing requests, and reconfiguring edge servers. By leveraging a natural
timescale separation between service routing and service caching, namely, the
former happens faster than the latter, we propose an online two-stage algorithm
and its randomized variant. Both algorithms have low complexity, and our
fractional solution achieves sublinear regret. Simulation results show that our
algorithms significantly outperform other state-of-the-art online policies.
