International Journal of Control, Vol.61, No.2, 357-393, 1995
Stability Analysis of Load Balancing Systems
A load processor is a system that has a buffer which can receive load and store it while it is waiting to be processed and has a local decision-making policy for determining if portions of its load should be sent to other load processors. A load balancing system is a set of such load processors that are connected in a network so that (i) they can sense the amount of load in the buffers of neighbouring processors and pass load to them, and (ii) so that, via local information and decisions by the individual load processors, the overall load in the entire network can be balanced. Such balancing is important to ensure that certain processors are not overloaded while others are left idle (i.e. load balancing helps avoid underutilization of processing resources). The topology of the network, delays in transporting and sensing load, types of load, and types of local load passing policies all affect the performance of the load balancing system. In this paper, we show how a variety of load balancing systems can be modelled in a discrete event system (DES) theoretic framework, and how balancing properties and performance can be characterized and analysed in a general Lyapunov stability theoretic framework.