Abstract
We consider the power-of-two policy with d = 2, Poisson job arrivals, heterogeneous servers and a general job requirement distribution. With the help of the first two light traffic derivatives for the average job response time, we point to interesting structural features associated with server heterogeneity in light traffic.
- V. Gupta, M. Harchol Balter, K. Sigman and W. Whitt, "Analysis of join-the-shortest-queue routing for web server farms," Performance Evaluation 64 (2007), pp. 1062--1081. Google ScholarDigital Library
- M. Harchol Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action, Cambridge University Press, Cambridge (UK), 2013. Google ScholarDigital Library
- A. Izagirre, U. Ayesta and I.M. Verloop, "Sojourn time approximations in a multi-class time-sharing server," in Proceedings of IEEE Infocom 2014, Toronto (ON), April 2014.Google Scholar
- A. Izagirre and A.M. Makowski, "Light traffic behavior under the power-of-two load balancing strategy: The heterogeneous case," Performance Evaluation. To be submitted (2014).Google Scholar
- A.W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications, Academic Press, San Diego (CA), 1979.Google Scholar
- M. Mitzenmacher, "The power of two choices in randomized load balancing," IEEE Transactions on Parallel and Distributed Systems TPDS-12 (2001), pp. 1094--1104. Google ScholarDigital Library
- A. Mukhopadhyay and R.R. Mazumdar, "Analysis of randomized join-the-shortest-queue (JSQ) schemes in large heterogeneous processor sharing systems," Submitted (2013).Google Scholar
- M.I. Reiman and B. Simon, "An interpolation approximation for queueing systems with Poisson input," Operations Research 36 (1988), pp. 454--469. Google ScholarDigital Library
- M.I. Reiman and B. Simon, "Open queueing systems in light traffic," Mathematics of Operations Research 14 (1989), pp. 26--59. Google ScholarDigital Library
- N.D. Vvedenskaya, R.L. Dobrushin and F.I. Karpelevich, "Queueing system with selection of the shortest of two queues: An asymptotic approach," Problems of Information Transmission 32 (1996), pp. 20--34.Google Scholar
- W. Whitt, "Deciding which queue to join: Some counterexamples," Operations Research 34 (1986), pp. 55--62. Google ScholarDigital Library
Recommendations
Light traffic behavior under the power-of-two load balancing strategy
We consider a multi-server queueing system under the power-of-two policy with Poisson job arrivals, heterogeneous servers and a general job requirement distribution; each server operates under the first-come first-serve policy and there are no buffer ...
The Power of Two Choices in Randomized Load Balancing
We consider the following natural model: Customers arrive as a Poisson stream of rate \lambda n, \lambda < 1, at a collection of n servers. Each customer chooses some constant d servers independently and uniformly at random from the n servers and waits ...
Light-Traffic Analysis for Queues with Spatially Distributed Arrivals
We consider the following continuous polling system: Customers arrive according to a homogeneous Poisson process or a more general stationary point process and wait on a circle in order to be served by a single server. The server is “greedy,” in the ...
Comments