×

A case study of an adaptive load balancing algorithm. (English) Zbl 0707.90034

Summary: We present an effective load balancing algorithm for a multi-processor architecture designed for the real time switching of telephone calls. By modifying an algorithm developed for an abstract queueing model, which is of independent interest by itself, we propose a hybrid load balancing algorithm and study its performance in a simulation test-bed. This case study demonstrates how simple abstractions and theoretically intractable but intuitively appealing ideas can be combined to effectively solve a real problem.

MSC:

90B18 Communication networks in operations research
60K25 Queueing theory (aspects of probability theory)
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. K. Agrawala and S. K. Tripathi, On the optimality of semidynamic routing schemes, Info. Process. Lett. 13 (October 1981). · Zbl 0476.68033
[2] M. Bazaraa and C.M. Shetty,Nonlinear Programming, Theory and Algorithms (Wiley, New York, 1979).
[3] P. Billingsley,Convergence of Probability Measures (Wiley, New York, 1968). · Zbl 0172.21201
[4] F. Bonomi and A. Kumar, Adaptive optimal load balancing in a heterogeneous multiserver system with a central job scheduler, to appear in IEEE Trans. Comput. (1990).
[5] F. Bonomi and A. Kumar, Adaptive optimal load balancing in a heterogeneous multiserver system with a central job scheduler,Proc. 8th ICDCS, San José, CA (1988) pp. 500-509.
[6] D. Eager, E. Lazowska and J. Zahorjan, Adaptive load sharing in homogeneous distributed systems, IEEE Trans. Software Eng. SE-12, no. 5 (1986) 662-675.
[7] H.J. Kushner and D.S. Clark,Stochastic Approximation Methods for Constrained and Unconstrained Systems (Springer, New York, 1978). · Zbl 0381.60004
[8] H.J. Kushner and A. Shwartz, An invariant measure approach to the convergence of stochastic approximations with state dependent noise, SIAM J. Control Optimization 22, no. 1 (1984) 13-27. · Zbl 0535.62069 · doi:10.1137/0322002
[9] N. Rau,Matrices and Mathematical Programming (St. Martin’s Press, New York, 1981). · Zbl 0459.90043
[10] Y.T. Wang and R.T.J. Morris, Load sharing in distributed systems, IEEE Trans. Comput. C-34 (1985) 204-217. · doi:10.1109/TC.1985.1676564
[11] J. W. West, III and T. D. Lynch,UNIX SIMSCRIPT II.5®User’s Manual, CACI (January 1986).
[12] T.P. Yum, The design and analysis of semidynamic deterministic routing rule, IEEE Trans. Commun. COM-29, no. 4 (1981) 498-504.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.