The distributed nature of edge computing infrastructures requires a significant effort to avoid overload conditions due to uneven distribution of incoming load from sensors placed over a wide area. While optimisation algorithms operating offline can address this issue in the medium to long term, sudden and unexpected traffic surges require an online approach where load balancing actions are taken at a smaller time scale. However, when the service time of a single request becomes comparable with the latency needed to take and actuate load balancing decisions, the design of online approaches becomes particularly challenging. This paper focuses on the class of online algorithms for load balancing based on resource sharing among random nodes. While this randomisation principle is a straightforward and effective way to share resources and achieve load balance, it fails to work properly when the interval between decision making and decision actuating times (called schedule lag) becomes comparable with the time required to execute a job, a condition not rare in edge computing systems, and provokes stale (out-of-date) information to be involved in scheduling decisions. Our analysis combines (1) a theoretical model that evaluates how stale information reduces the effectiveness of the balancing mechanism and describes the correlation between the system state at decision making and decision actuating times; (2) a simulation approach to study a wide range of algorithm parameters and possible usage scenarios. The results of our analysis provides the designers of distributed edge systems with useful hints to decide, based on the scenario, which load balancing protocol is the most suitable.

On the impact of stale information on distributed online load balancing protocols for edge computing / Beraldi, R.; Canali, C.; Lancellotti, R.; Mattia, G. P.. - In: COMPUTER NETWORKS. - ISSN 1389-1286. - 210:(2022). [10.1016/j.comnet.2022.108935]

On the impact of stale information on distributed online load balancing protocols for edge computing

Beraldi R.
Primo
;
Mattia G. P.
2022

Abstract

The distributed nature of edge computing infrastructures requires a significant effort to avoid overload conditions due to uneven distribution of incoming load from sensors placed over a wide area. While optimisation algorithms operating offline can address this issue in the medium to long term, sudden and unexpected traffic surges require an online approach where load balancing actions are taken at a smaller time scale. However, when the service time of a single request becomes comparable with the latency needed to take and actuate load balancing decisions, the design of online approaches becomes particularly challenging. This paper focuses on the class of online algorithms for load balancing based on resource sharing among random nodes. While this randomisation principle is a straightforward and effective way to share resources and achieve load balance, it fails to work properly when the interval between decision making and decision actuating times (called schedule lag) becomes comparable with the time required to execute a job, a condition not rare in edge computing systems, and provokes stale (out-of-date) information to be involved in scheduling decisions. Our analysis combines (1) a theoretical model that evaluates how stale information reduces the effectiveness of the balancing mechanism and describes the correlation between the system state at decision making and decision actuating times; (2) a simulation approach to study a wide range of algorithm parameters and possible usage scenarios. The results of our analysis provides the designers of distributed edge systems with useful hints to decide, based on the scenario, which load balancing protocol is the most suitable.
File allegati a questo prodotto
File Dimensione Formato  
Beraldi_OnTheImpact_2022.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.71 MB
Formato Adobe PDF
2.71 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Beraldi_Postprint_OnTheImpact_2022.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Creative commons
Dimensione 956.19 kB
Formato Adobe PDF
956.19 kB Adobe PDF Visualizza/Apri PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/1629854
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact