Online Service Deployment in Edge Computing: A Comparison of Batching Techniques

We tackle an optimization problem related to the deployment of delay-sensitive services on computing facilities at the edge of the network. We consider an online setting, in which a service provider must dynamically decide where to activate services, in absence of information about upcoming users and deployment costs. We model the application as an online facility location problem under the assumption that serving each user yields a reward which is proportional to the network distance between the user and the serving facility. We propose an online algorithm to tackle such problem. It exploits mathematical programming in an online learning framework. As main feature, it updates the deployment decision after a batch of users has appeared, fitting two operational policies: to refresh decisions after batches of fixed cardinality, or to refresh at constant time intervals, thereby handling batches of variable sizes. We experiment our algorithm with simulations using a stochastic generator, built on real internet connection records. We compare the two operational policies in terms of applicability, profit and computational time. Our results indicate that using batches of variable size allow for easier policy application, with no significant decrease in profits, and only a minor increase in performance variability.