Adaptive Optimal Load Balancing in a Nonhomogeneous Multiserver System with a Central Job Scheduler
October 1990 (vol. 39 no. 10)
pp. 1232-1250
DOI Bookmark:
http://doi.ieeecomputersociety.org/10.1109/12.59854
A model comprising several servers, each equipped with its own queue and with possibly different service speeds, is considered. Each server receives a dedicated arrival stream of jobs; there is also a stream of generic jobs that arrive to a job scheduler and can be individually allocated to any of the servers. It is shown that if the arrival streams are all Poisson and all jobs have the same exponentially distributed service requirements, the probabilistic splitting of the generic stream that minimizes the average job response time is such that it balances the server idle times in a weighted least-squares sense, where the weighting coefficients are related to the service speeds of the servers. The corresponding result holds for nonexponentially distributed service times if the service speeds are all equal. This result is used to develop adaptive quasi-static algorithms for allocating jobs in the generic arrival stream when the load parameters are unknown. The algorithms utilize server idle-time measurements which are sent periodically to the central job scheduler. A model is developed for these measurements, and the result mentioned is used to cast the problem into one of finding a projection of the root of an affine function, when only noisy values of the function can be observed. [1] A. K. Agrawala and S. K. Tripathi, "On the optimality of semidynamic routing schemes,"Inform. Processing Lett., vol. 13, Oct. 1981.[2] M. Bazaraa and C. M. Shetty,Nonlinear Programming, Theory and Algorithms. New York: Wiley, 1979.[3] D. P. Bertsekas and R. G. Gallager, "Second derivative algorithms for minimum delay distributed routing in networks,"IEEE Trans. Commun., vol. COM-32, no. 8, pp. 911-919, Aug. 1984.[4] C. G. Cassandras, M. V. Abidi, and D. Towsley, "Distributed routing with on-line marginal delay estimation," inProc. IEEE INFOCOM '88, 1988, pp. 603-612.[5] F. Chang and L. Wu, "An optimal adaptive routing algorithm,"IEEE Trans. Automat. Contr., vol. AC-31, no. 8, pp. 690-700, Aug. 1986.[6] H.-F. Chen,Recursive Estimation and Control of Stochastic Systems. New York: Wiley, 1985.[7] Y. C. Chow and W. Kohler, "Models of dynamic load balancing in a heterogeneous multiple processor system,"IEEE Trans. Comput., vol. C-28, no. 5, pp. 354-361, May 1979.[8] E. de Souza e Silva and M. Gerla, "Load balancing in distributed systems with multiple classes and site constraints,"Performance '84, 1984, pp. 17-33.[9] D. Eager, E. Lazowska, and J. Zahorjan, "Adaptive load sharing in homogeneous distributed systems,"IEEE Trans. Software Eng., vol. SE-12, no. 5, pp. 662-675, May 1986.[10] R. G. Gallager, "A minimum delay routing algorithm using distributed computation,"IEEE Trans. Commun., vol. COM-25, no. 1, pp. 73-85, Jan. 1977.[11] D. L. Jagerman, "An inversion technique for the Laplace transform,"Bell Syst. Tech. J., vol. 61, no. 8, pp. 1995-2002, Oct. 1982.[12] L. Kleinrock,Queueing Systems, Vols. I&II. New York: Wiley, 1975, 1976.[13] A. Kumar, "Adaptive load control of the central processor in a distributed system with a star topology," inProc. IEEE Conf. Decision Contr., Athens, Greece, Dec. 1986, pp. 1697-1699.[14] A. Kumar, "Adaptive load control of the central processor in a distributed system with a star topology,"IEEE Trans. Comput., vol. 38, no. 11, pp. 1502-1512, Nov. 1989.[15] A. Kumar, to be published.[16] A. Kumar and F. Bonomi, "Adaptive load balancing in a multiprocessor system with a central job scheduler," inProc. 2nd Int. Workshop Appl. Math. Perform/Reliability Models of Comput. Commun. Syst., Univ. of Rome II, 1987, pp. 173-188.[17] P. R. Kumar and P. Varaiya,Stochastic Systems. Englewood Cliffs, NJ: Prentice-Hall, 1986.[18] H. J. Kushner and D. S. Clark,Stochastic Approximation Methods for Constrained and Unconstrained Systems. New York: Springer-Verlag, 1978.[19] L. M. Ni and K. Hwang, "Optimal load balancing strategies for a multiprocessor system, " inProc. 1981 Int. Conf. Parallel Processing, Columbus, OH, Aug. 1981, pp. 352-357.[20] L. M. Ni and K. Hwang, "Optimal load balancing in a multiple processor system with many job classes,"IEEE Trans. Software Eng., vol. SE-11, no. 5, pp. 491-496, May 1985.[21] H. S. Stone, "Multiprocessor scheduling with the aid of network flow algorithms,"IEEE Trans. Software Eng., vol. SE-3, pp. 85-93, Jan. 1977.[22] A. N. Tantawi and D. Towsley, "Optimal load balancing in distributed computer systems," Tech. Rep. RC-10346, IBM T. J. Watson Research Center, Jan. 1984.[23] R. W. Weber, "On optimal assignment of customers to parallel servers,"J. Appl. Prob., vol. 15, pp. 406-413, 1978.[24] W. Winston, "Optimality of the shortest line discipline,"J. Appl. Prob., pp. 181-189, 1977.[25] T. P. Yum, "The design and analysis of semidynamic deterministic routing rule,"IEEE Trans. Commun., vol. COM-29, no. 4, pp. 498-504, Apr. 1981.
Index Terms:
adaptive optimal load balancing; job allocation; nonhomogeneous multiserver system; central job scheduler; queue; service speeds; dedicated arrival stream; generic jobs; Poisson; exponentially distributed service requirements; probabilistic splitting; generic stream; average job response time; server idle times; weighted least-squares; weighting coefficients; nonexponentially distributed service times; adaptive quasi-static algorithms; load parameters; affine function; noisy values; multiprocessing systems; queueing theory; scheduling.
Citation:
F. Bonomi, A. Kumar, "Adaptive Optimal Load Balancing in a Nonhomogeneous Multiserver System with a Central Job Scheduler," IEEE Transactions on Computers, vol. 39, no. 10, pp. 1232-1250, Oct. 1990, doi:10.1109/12.59854
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb