Pass-and-swap queues

DOI10.1007/S11134-021-09700-3zbMATH Open1475.60178arXiv2009.12299OpenAlexW3152713936MaRDI QIDQ2052797FDOQ2052797

Authors: Céline Comte, Jan-Pieter L. Dorsman 

Publication date: 29 November 2021

Published in: Queueing Systems (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2009.12299

Recommendations

• Order independent queues
• Quasi-reversible multiclass queues with order independent departure rates
• Order independent loss queues
• Instant service queueing networks. II: Several customer-type models
• Publication:4945035

zbMATH Keywords

quasi-reversibilityfirst-come-first-servedproduct-form stationary distributionnetwork of queuesassign-to-the-longest-idle-serverorder-independent queue

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Cites Work

• Open, Closed, and Mixed Networks of Queues with Different Classes of Customers
• Networks of Waiting Lines
• Graph spectra for complex networks
• A skill based parallel service system under FCFS-ALIS -- steady state, overloads, and abandonments
• Queueing with redundant requests: exact analysis
• Title not available (Why is that?)
• A loss system with skill-based servers under assign to longest idle server policy
• Queueing networks. A fundamental approach
• Title not available (Why is that?)
• Order independent loss queues
• Quasi-reversible multiclass queues with order independent departure rates
• Order independent queues
• On practical product form characterizations
• Product Form Solutions for Multiserver Centers with Hierarchical Concurrency Constraints
• Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview
• Networks with customers, signals, and product form solutions
• A product form for the general stochastic matching model

Cited In (3)

• New directions in pass-and-swap queues
• Order independent queues
• Quasi-reversible multiclass queues with order independent departure rates

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)