Stability of parallel server systems
From MaRDI portal
Abstract: The fundamental problem in the study of parallel-server systems is that of finding and analyzing `good' routing policies of arriving jobs to the servers. It is well known that, if full information regarding the workload process is available to a central dispatcher, then the {em join the shortest workload} (JSW) policy, which assigns jobs to the server with the least workload, is the optimal assignment policy, in that it maximizes server utilization, and thus minimizes sojourn times. The {em join the shortest queue} (JSQ) policy is an efficient dispatching policy when information is available only on the number of jobs with each of the servers, but not on their service requirements. If information on the state of the system is not available, other dispatching policies need to be employed, such as the power-of- routing policy, in which each arriving job joins the shortest among queues sampled uniformly at random. (Under this latter policy, the system is known as {em the supermarket model}.) In this paper we study the stability question of parallel server systems assuming that routing errors occur, so that arrivals may be routed to the `wrong' (not to the smallest) queue with a positive probability. We show that, even if a `non-idling' dispatching policy is employed, under which new arrivals are always routed to an idle server, if any is available, the performance of the system can be much worse than under the policy that chooses one of the servers uniformly at random. More specifically, we prove that the usual traffic intensity does not guarantee that the system is stable.
Recommendations
- On the stability of a class of non-monotonic systems of parallel queues
- Persistent-idle load-distribution
- Asymptotic optimality of balanced routing
- Stability of JSQ in queues with general server-job class compatibilities
- Delay-join the shortest queue routing for a parallel queueing system with removable servers
Cites work
- scientific article; zbMATH DE number 3885083 (Why is no real title available?)
- scientific article; zbMATH DE number 3733034 (Why is no real title available?)
- scientific article; zbMATH DE number 1947316 (Why is no real title available?)
- scientific article; zbMATH DE number 3322728 (Why is no real title available?)
- A Basic Dynamic Routing Problem and Diffusion
- A pathwise comparison of parallel queues
- Applied Probability and Queues
- Asymptotic distributions and chaos for the supermarket model
- Certain optimality properties of the first-come first-served discipline for G/G/s queues
- Chaoticity on path space for a queueing network with selection of the shortest queue among several
- Chattering and congestion collapse in an overload switching control
- Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov processes
- Deciding Which Queue to Join: Some Counterexamples
- Ergodicity of stochastic processes describing the operation of open queueing networks
- Functional central limit theorems for a large network in which customers join the shortest of several queues
- Inequalities: theory of majorization and its applications
- Instability of FIFO queueing networks
- Join the shortest queue with many servers. The heavy-traffic asymptotics
- Markov Chains
- Martingale proofs of many-server heavy-traffic limits for Markovian queues
- Modeling and analysis of stochastic systems
- Necessary and Sufficient Conditions for Delay Moments in FIFO Multiserver Queues with an Application Comparing s Slow Servers with One Fast One
- Nonlinear systems.
- On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
- On the Theory of Queues With Many Servers
- On the instability of matching queues
- On the maximum queue length in the supermarket model
- On the optimal assignment of customers to parallel servers
- On the stability of a class of non-monotonic systems of parallel queues
- On the stability of a partially accessible multi-station queue with state-dependent routing
- Optimality of the shortest line discipline
- Point processes and queues. Martingale dynamics
- Queueing system with selection of the shortest of two queues: An asymptotic approach
- Stability of join the shortest queue networks
- Stability of queueing networks
- Stationary analysis of the shortest queue problem
- Stochastic modeling and analysis of telecoms networks
- Stochastic-Process Limits
- Subdiffusive load balancing in time-varying queueing systems
- Switching in systems and control
- TWO QUEUES IN PARALLEL
- The Effect of Increasing Routing Choice on Resource Pooling
- The supermarket game
- Topics in the Constructive Theory of Countable Markov Chains
- Two Similar Queues in Parallel
- Two queues in parallel
Cited in
(14)- Stability of JSQ in queues with general server-job class compatibilities
- Stability analysis of parallel server systems under longest queue first
- Asymptotically optimal routing of a many-server parallel queueing system with long-run average criterion
- scientific article; zbMATH DE number 1863332 (Why is no real title available?)
- Parallel Server Systems with Cancel-on-Completion Redundancy
- Risk-Sensitive Control for the Parallel Server Model
- Delay-join the shortest queue routing for a parallel queueing system with removable servers
- Asymptotic optimality of balanced routing
- Persistent-idle load-distribution
- Stability aspects in using parallel algorithms
- Bias properties of infinitesimal perturbation analysis for systems with parallel servers
- Multi-layered round robin routing for parallel servers
- A pathwise comparison of parallel queues
- Uniform stability of some large-scale parallel server networks
This page was built for publication: Stability of parallel server systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5106378)
