Optimal allocation of servers and processing time in a load balancing system. (English) Zbl 1231.90140
Summary: We consider the problem of allocating processing time in a multi-channel load balancing system by focusing on systems where processing times have distributions characterized by high variability. Our objective is to reduce congestion by routing jobs to servers based on their workload. Specifically, we arrange servers in two stations in series, and require that the load be balanced between the two stations. All arrivals join the first service center where they receive a maximum of \(T\) units of service. Arrivals with service requirements that exceed the value \(T\) join the second station where they receive their remaining service. For a variety of heavy tail service time distributions, characterized by high variability, analytical and numerical comparisons show that our scheme provides better system performance than the standard parallel multi-server model in the sense of reducing the mean delay per customer when the traffic intensity is not too low. In particular, we develop lower bounds on the traffic intensity and the service time coefficient of variation beyond which the balanced series system outperforms the parallel system.
MSC:
| 90B22 | Queues and service in operations research |
| 90B36 | Stochastic scheduling theory in operations research |
| 60K25 | Queueing theory (aspects of probability theory) |
Software:
EquiLoadReferences:
| [1] | Bachmat, E.; Sarfati, H., Analysis of size interval task assignment policies, Performance Evaluation Review, 36, 107-109 (2008) |
| [2] | Broberg, J.; Tari, Z.; Zeephongsekul, P., Task assignment with work-conserving migration, Parallel Computing, 32, 808-830 (2006) |
| [3] | Buzacott, J. A., Commonalities in reengineering business processes: models and issues, Management Science, 42, 768-782 (1996) · Zbl 0884.90090 |
| [4] | Ciardo, G.; Riska, A.; Smirni, E., Equiload: a load balancing policy for clustered web servers, Performance Evaluation, 46, 101-124 (2001) · Zbl 1013.68011 |
| [5] | Cooper, R. B., Introduction to queueing theory (1981), North-Holland: North-Holland New York · Zbl 0467.60001 |
| [6] | Crovella, M. E.; Bestavros, A., Self-similarity in world wide web traffic: evidence and possible, IEEE/ACM Transactions on Networking, 5, 835-846 (1997) |
| [7] | El-Taha, M., Optimal allocation of service time in a two-server system, Computers & Operations Research, 30, 683-693 (2003) · Zbl 1026.90021 |
| [8] | El-Taha, M.; Maddah, B., Allocation of service time in a multi-server system, Management Science, 52, 623-637 (2006) · Zbl 1232.90144 |
| [9] | El-Taha M, Maddah B. Supplement for “allocation of service time in a multi-server system”. Available online at \(\langle\) http://www.informs.org/site/ManSci/article.php?\(id=49 \rangle \); El-Taha M, Maddah B. Supplement for “allocation of service time in a multi-server system”. Available online at \(\langle\) http://www.informs.org/site/ManSci/article.php?\(id=49 \rangle \) · Zbl 1232.90144 |
| [10] | Feng, H.; Misra, V. B.; Rubenstein, D., Optimal state-free, size-aware dispatching for heterogeneous M/G-type systems, Performance Evaluation, 62, 475-492 (2005) |
| [11] | Fowler TB. A short tutorial on fractiles and internet traffic. In: The Telecommunications Review, vol. 10, Mitretek Systems, McLean, VA, 1997. p. 1-14.; Fowler TB. A short tutorial on fractiles and internet traffic. In: The Telecommunications Review, vol. 10, Mitretek Systems, McLean, VA, 1997. p. 1-14. |
| [12] | Gross, D.; Harris, C., Fundamentals of queueing theory (1998), John Wiley: John Wiley New York · Zbl 0949.60002 |
| [13] | Harchol-Balter, M., Task assignment with unknown duration, The Journal of the ACM, 49, 260-288 (2002) · Zbl 1323.68033 |
| [14] | Harchol-Balter, M.; Crovella, M. E.; Murta, C. D., On choosing a task assignment policy for a distributed server system, Journal of Parallel and Distributed Computing, 59, 204-228 (1999) |
| [15] | Harchol-Balter, M.; Downey, A. B., Exploiting process lifetime distributions for dynamic load balancing, ACM Transactions on Computer Systems, 15, 253-285 (1997) |
| [16] | Harchol-Balter M, Li C, Osogami T, Scheller-Wolf A, Squillante MS. Analysis of task assignment with cycle stealing under central queue. In: International conference on distributed computing systems, Providence, RI, 2003. p. 628-37; Harchol-Balter M, Li C, Osogami T, Scheller-Wolf A, Squillante MS. Analysis of task assignment with cycle stealing under central queue. In: International conference on distributed computing systems, Providence, RI, 2003. p. 628-37 |
| [17] | Harchol-Balter M, Scheller-Wolf A, Young A. Surprising results on task assignment in server farms with high-variability workloads. In: Proceedings of ACM SIGMETRICS 2009 conference on measurement and modeling of computer systems, Seattle, WA, 2009.; Harchol-Balter M, Scheller-Wolf A, Young A. Surprising results on task assignment in server farms with high-variability workloads. In: Proceedings of ACM SIGMETRICS 2009 conference on measurement and modeling of computer systems, Seattle, WA, 2009. |
| [18] | Karame GM. Reducing congestion in “heavy-tailed” queues. Masters thesis, American University of Beirut; 2008.; Karame GM. Reducing congestion in “heavy-tailed” queues. Masters thesis, American University of Beirut; 2008. |
| [19] | Mandelbaum, A.; Reiman, M. I., On pooling in queueing networks, Management Science, 44, 971-981 (1998) · Zbl 0989.90034 |
| [20] | Marchal, W., Some simple bounds on the mean queueing time, Operations Research, 26, 1083-1088 (1978) · Zbl 0414.60088 |
| [21] | Naldi, M., Measurement-based modeling of internet dial-up access connections, Computer Networks, 31, 2381-2390 (1999) |
| [22] | Paxson V. Why measuring the internet is painfully hard. In: The fifth informs telecommunications conference, Boca Raton, Florida, 2000.; Paxson V. Why measuring the internet is painfully hard. In: The fifth informs telecommunications conference, Boca Raton, Florida, 2000. |
| [23] | Uthaisombut P. New directions in machine scheduling. PhD thesis, Department of Computer Science and Engineering, Michigan State University; 2000.; Uthaisombut P. New directions in machine scheduling. PhD thesis, Department of Computer Science and Engineering, Michigan State University; 2000. |
| [24] | Whitt, W., Approximating a point process by a renewal process: the view through a queue, an indirect approach, Management Science, 27, 619-636 (1981) · Zbl 0457.60073 |
| [25] | Whitt, W., Approximating a point process by a renewal process, I: two basic methods, Operations Research, 30, 125-147 (1982) · Zbl 0481.90025 |
| [26] | Whitt, W., The queueing network analyzer, Bell System Technical Journal, 62, 2779-2815 (1983) |
| [27] | Whitt, W., Approximations for the GI/GI/m queue, Production and Operations Management, 2, 114-161 (1993) |
| [28] | Whitt, W., Partitioning customers into service groups, Management Science, 45, 1579-1592 (1999) · Zbl 0944.90014 |
| [29] | Wolff, R., Stochastic modeling and the theory of queues (1989), Prentice-Hall: Prentice-Hall NJ · Zbl 0701.60083 |
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.
