Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Dynamic Regret of Randomized Online Service Caching in Edge Computing



Siqi Fan, I-Hong Hou, Van Sy Mai


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.
Proceedings Title
2023 IEEE International Conference on Computer Communications (IEEE INFOCOM)
Conference Dates
May 17-20, 2023
Conference Location
New York, NY, US


Fan, S. , Hou, I. and Mai, V. (2023), Dynamic Regret of Randomized Online Service Caching in Edge Computing, 2023 IEEE International Conference on Computer Communications (IEEE INFOCOM), New York, NY, US, [online],, (Accessed July 14, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created August 29, 2023, Updated October 6, 2023