APPROXIMATING THE MEAN RESPONSE-TIME OF PARALLEL QUEUES WITH JSQ POLICY

This paper presents an accurate model for evaluating the mean system s ize of parallel queues with the Join the Shortest Queue (JSQ) policy. The system considered consists of N identical queues with infinite buf fers, and each of the queues has one server. The job arrival process i s assumed to be Poisson. The service times are assumed to be exponenti ally distributed. When a job arrives at the system, it is sent to the queue with the smallest number of jobs. Ties are broken by randomly se lecting one of the queues with the minimal number of jobs. Exact analy sis of the system is known to be very difficult, and our model gives v ery accurate results. A birth-death Markov process is used to model th e evolution of the number of jobs in the system. An iterative procedur e is devised to estimate the state transition rates. The mean job resp onse time can then be calculated. Extensive simulations are performed and compared with the analytical results. Our results show that this m ethod provides very accurate estimates (within 3.5%) of the mean job r esponse times for N up to 64. (C) 1996 Elsevier Science Ltd