Abstract

Fog computing infrastructures must support increasingly complex applications where a large number of sensors send data to intermediate fog nodes for processing. As the load in such applications (as in the case of a smart cities scenario) is subject to significant fluctuations both over time and space, it is fundamental to provide load balancing across the infrastructure. In this paper we study a fully distributed algorithm for load balancing based on random probing of the neighbors status. A qualifying point of our study is that we take into account the impact of delay during the probe phase and we show how the presence of stale information impact on the algorithm performance. We propose a theoretical model for the loss of correlation between actual load on a node and stale information arriving to the neighbors with a network-induced delay. Furthermore, we analyze through simulation the performance of the proposed algorithm considering a wide set of parameters and comparing it with an alternative approach from the literature that is based on random walks. Our analysis points out under which conditions the proposed algorithm can outperform the alternatives.

Citation

Beraldi, R., Canali, C., Lancellotti, R., & Proietti Mattia, G. (2020, November). Randomized load balancing under loosely correlated state information in fog computing. 23rd ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM’20). https://doi.org/10.1145/3416010.3423244

@inproceedings{2020BeraldiRandomized,
  author = {Beraldi, Roberto and Canali, Claudia and Lancellotti, Riccardo and {Proietti Mattia}, Gabriele},
  title = {Randomized load balancing under loosely correlated state information in fog computing},
  booktitle = {23rd ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM'20)},
  address = {Alicante, Spain},
  days = {15},
  month = nov,
  year = {2020},
  keywords = {Fog Computing; load balancing},
  doi = {10.1145/3416010.3423244}
}