Load Sharing in Distributed Real-Time Systems with Broadcast State Changes

TitleLoad Sharing in Distributed Real-Time Systems with Broadcast State Changes
Publication TypeTechnical Report
Year of Publication1988
AuthorsShin, K. G., & Chang Y-C.
Other Numbers1219

If task arrivals are not uniformly distributed over the nodes in a distributed real-time system, some nodes may become overloaded while others are lightly-loaded or even idle. Consequently, some tasks cannot be completed before their deadlines, even if the overall system has the capacity to meet all deadlines. Load sharing (LS) is one way to alleviate this difficulty. In this paper, we propose a decentralized, dynamic LS method for a distributed real-time system. Under this LS method, whenever the state of a node changes from lightly-loaded to overloaded and vice versa, the node broadcasts this change to a set of nodes, called a buddy set, in the system. An overloaded node can select, without probing other nodes, the first available node from its preferred list, an ordered set of nodes in its buddy set. Preferred lists are so constructed that the probability of more than one overloaded node "dumping" their loads on a single lightly-loaded node may be made very small. Performance of the proposed LS policy is evaluated with both analytic modeling and simulation. Analytic models are used to derive the distribution of queue length at each node, the probability of meeting task deadlines, and analyze the effects of buddy set size, the frequency of state change, and the average system sojourn time of each task. On the other hand, simulation is used to verify analytic results. The proposed LS method is shown to meet task deadlines with a very high probability.

Bibliographic Notes

ICSI Technical Report TR-88-006

Abbreviated Authors

K. Shin and Y.-C. Chang

ICSI Publication Type

Technical Report