An approximation to the response time for shortest queue routing

In this paper we derive an approximation for the mean response time of a multiple queue system in which shortest queue routing is used. We assume there are identical queues with infinite capacity and service times that are exponentially distributed. Arrivals of jobs to this system are Poisson and ar...

Full description

Saved in:
Bibliographic Details
Main Authors: Nelson, R. D., Philips, T. K.
Format: Conference Proceeding
Language:English
Subjects:
Computer systems organization > Architectures > Parallel architectures
Computing methodologies > Modeling and simulation > Model development and analysis > Modeling methodologies
Mathematics of computing > Mathematical analysis > Numerical analysis
Mathematics of computing > Probability and statistics > Statistical paradigms > Queueing theory
Theory of computation > Design and analysis of algorithms
Theory of computation > Design and analysis of algorithms > Approximation algorithms analysis > Routing and network design problems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we derive an approximation for the mean response time of a multiple queue system in which shortest queue routing is used. We assume there are identical queues with infinite capacity and service times that are exponentially distributed. Arrivals of jobs to this system are Poisson and are routed to a queue of minimal length. We develop an approximation which is based on both theoretical and experimental considerations and, for ≤ 8, has an relative error of less than one half of one percent when compared to simulation. For = 16, the relative error is still acceptable, being less than 2 percent. An application to a model of parallel processing and a comparison of static and dynamic load balancing schemes are presented.
ISSN:0163-5999
DOI:10.1145/75108.75392