A Simulation Study of Epoch Load Sharing in Distributed Systems

Abstract

This paper examines load sharing in distributed systems. It proposes a special load-sharing method, referred to as epoch load sharing. With this policy, load is evenly distributed among distributed processors, with job migration only at the end of predefined intervals. The time interval between successive load sharing is called an epoch. The authors compare the performance of epoch job migration with other traditional load-sharing methods. The objective is to reduce the number of times that global system information is needed to make allocation decisions while achieving good overall performance and fairness in individual job service. The impact of the variability in migration cost and job service demand is also examined. Simulation results indicate that for specific workloads, epoch job migration can combine good performance with a moderate scheduling overhead.

Keywords

Distributed systems performance load sharing simulation

Get full access to this article

View all access options for this article.

References

Blake, B. A. 1992. Assignment of independent tasks to minimize completion time. Software Practice and Experience 22 (9): 723-734.

Eager, D. L. , E. D. Lazowska , and J. Zahorjan . 1986. A comparison of receiver-initiated and sender-initiated adaptive load sharing. Performance Evaluation 6:53-68.

Harchol-Balter, M. , and A. B. Downey . 1996. Exploiting process lifetime distribution for dynamic load balancing. Proceedings of Sigmetrics ’96, May, Philadelphia, pp. 13-24.

Karatza, H. D. 1996. Simulation study of sender-initiated load sharing with resequencing. Proceedings of Summer Computer Simulation Conference, July, Portland, OR, pp. 497-501.

Karatza, H. D. 1996. Sender-initiated versus receiver-initiated adaptive load sharing with resequencing. Proceedings of the 8th European Simulation Symposium & Exhibition, October, Genoa, Italy, pp. 546-550.

Karatza, H. D. 1998. Assignment of programs in a distributed system with resequencing. Proceedings of the 31st Annual Simulation Symposium, April, Boston, pp. 34-41.

Zhang, Y. , H. Franke , J. E. Moreira , and A. Sivasubramanian . 2000. The impact of migration on parallel job scheduling for distributed Systems. Proceedings of Europar, September, Munich, pp. 242-251.

Karatza, H. D. , and R. C. Hilzer . 2001. Epoch load sharing in a network of workstations. Proceedings of the 34th Annual Simulation Symposium, April, Seattle, WA, pp. 36-42.

McCann, C. , and J. Zahorjan . 1995. Scheduling memory constraint jobs on distributed memory parallel computers. Proceedings of the 1995 ACM Sigmetrics Conference, May, Ottawa, Canada, pp. 208-219.

10.

Rosti, E. , G. Serazzi , E. Smirni , and M. Squillante . 1998. The impact of I/O on program behaviour and parallel scheduling. Proceedings of SIGMETRICS 98, June, Madison, WI, pp. 56-65.

11.

Law, A. , and D. Kelton . 1991. Simulation modelling and analysis. New York: McGraw-Hill.