On the instability of matching queues

Pascal Moyal, Ohad Perry

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

A matching queue is described via a graph, an arrival process and a matching policy. Specifically, to each node in the graph there is a corresponding arrival process of items, which can either be queued or matched with queued items in neighboring nodes. The matching policy specifies how items are matched whenever more than one matching is possible. Given the matching graph and the matching policy, the stability region of the system is the set of intensities of the arrival processes rendering the underlying Markov process positive recurrent. In a recent paper, a condition on the arrival intensities, which was named NCOND, was shown to be necessary for the stability of a matching queue. That condition can be thought of as an analogue to the usual traffic condition for traditional queueing networks, and it is thus natural to study whether it is also sufficient. In this paper, we show that this is not the case in general. Specifically, we prove that, except for a particular class of graphs, there always exists a matching policy rendering the stability region strictly smaller than the set of arrival intensities satisfying NCOND. Our proof combines graph- and queueing-theoretic techniques: After showing explicitly, via fluid-limit arguments that the stability regions of two basic models is strictly included in NCOND, we generalize this result to any graph inducing either one of those two basic graphs.

Original languageEnglish (US)
Pages (from-to)3385-3434
Number of pages50
JournalAnnals of Applied Probability
Volume27
Issue number6
DOIs
StatePublished - Dec 2017

Keywords

  • Fluid limits
  • Graphs
  • Instability
  • Matching queues

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'On the instability of matching queues'. Together they form a unique fingerprint.

Cite this