Dynamic load distribution using anti-tasks and load state vectors

Abstract

Polling-based load distribution (LD) algorithms suffer from two weaknesses: (i) load information exchanged during a polling session is confined to the two negotiating nodes only; (ii) as the distributed system grows in size (in terms of the number of constituent nodes), a larger number of polling sessions, and thus a higher amount of network bandwidth consumption and CPU overhead, are needed. We propose a new LD algorithm which is based on anti-tasks and load state vectors. This new algorithm avoids the above weaknesses of polling-based LD algorithms. Anti-tasks are composite agents which travel around a distributed system to facilitate the pairing up of task senders and receivers, as well as the collection and dissemination of load information. Time-stamped load information of processing nodes is stored in load state vectors which, when used together with anti-tasks, encourage mutual sharing of load information among processing nodes. Anti-tasks, which make use of load state vectors to decide their traveling paths, are spontaneously directed towards processing nodes having high transient workload, thus allowing their surplus workload to be relocated quickly. Using simulations, we evaluate the performance of our new algorithm by comparing its performance with a number of well-known polling-based load distribution algorithms. We found that our algorithm provides significant reduction of mean task response time over a large range of system sizes. The cost of achieving this performance gain in terms of CPU overhead and channel bandwidth consumption is generally comparable to the other algorithms we studied. © 1998 John Wiley & Sons, Ltd.