Weathering the Reallocation Storm

Efficient service placement and workload allocation methods are necessary enablers for the actively studied topic of edge computing. In this paper, we show that under certain circumstances, the number of superfluous workload reallocations from one edge server to another may grow to a significant proportion of all user tasks — a phenomenon we present as a reallocation storm. We showcase this phenomenon on a city-scale edge server deployment by simulating the allocation of user task workloads in a number of scenarios capturing likely edge computing deployments and usage patterns. The simulations are based on a large real-world data set of city-wide Wi-Fi network connections in 2013—2014, with more than 47M connections over ca. 800 access points. We identify the conditions for avoiding the reallocation storm for three common edge-based reallocation strategies, and study the latency-workload trade-off related to each strategy. As a result, we find that the superfluous reallocations vanish when the edge server capacity is increased above a certain threshold, unique for each reallocation strategy, peaking at ca. 35% of top ES workload. Further, while a reallocation strategy aiming to minimize reallocation distance consistently resulted in the worst reallocation storms, the two other strategies, namely, a random reallocation strategy, and a bottom-up strategy which always chooses the edge server with the lowest workload as a reallocation target, behave nearly identically in terms of latency as well as the reallocation storm in dense edge deployments. Since the random strategy requires much less coordination, we recommend it over the bottom-up one in dense ES deployments.