Pass-and-swap queues
From MaRDI portal
Publication:2052797
Abstract: Order-independent (OI) queues, introduced by Berezner, Kriel, and Krzesinski in 1995, expanded the family of multi-class queues that are known to have a product-form stationary distribution by allowing for intricate class-dependent service rates. This paper further broadens this family by introducing pass-and-swap (P&S) queues, an extension of OI queues where, upon a service completion, the customer that completes service is not necessarily the one that leaves the system. More precisely, we supplement the OI queue model with an undirected graph on the customer classes, which we call a swapping graph, such that there is an edge between two classes if customers of these classes can be swapped with one another. When a customer completes service, it passes over customers in the remainder of the queue until it finds a customer it can swap positions with, that is, a customer whose class is a neighbor in the graph. In its turn, the customer that is ejected from its position takes the position of the next customer it can be swapped with, and so on. This is repeated until a customer can no longer find another customer to be swapped with; this customer is the one that leaves the queue. After proving that P&S queues have a product-form stationary distribution, we derive a necessary and sufficient stability condition for (open networks of) P&S queues that also applies to OI queues. We then study irreducibility properties of closed networks of P&S queues and derive the corresponding product-form stationary distribution. Lastly, we demonstrate that closed networks of P&S queues can be applied to describe the dynamics of new and existing load-distribution and scheduling protocols in clusters of machines in which jobs have assignment constraints.
Recommendations
Cites work
- scientific article; zbMATH DE number 4058589 (Why is no real title available?)
- scientific article; zbMATH DE number 1350310 (Why is no real title available?)
- A loss system with skill-based servers under assign to longest idle server policy
- A product form for the general stochastic matching model
- A skill based parallel service system under FCFS-ALIS -- steady state, overloads, and abandonments
- Graph spectra for complex networks
- Networks of Waiting Lines
- Networks with customers, signals, and product form solutions
- On practical product form characterizations
- Open, Closed, and Mixed Networks of Queues with Different Classes of Customers
- Order independent loss queues
- Order independent queues
- Product Form Solutions for Multiserver Centers with Hierarchical Concurrency Constraints
- Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview
- Quasi-reversible multiclass queues with order independent departure rates
- Queueing networks. A fundamental approach
- Queueing with redundant requests: exact analysis
Cited in
(3)
This page was built for publication: Pass-and-swap queues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052797)
