A novel approach to the queue stability analysis of polling models

Sum Lam, Kow Chuen Chang

Research output: Journal article publicationConference articleAcademic researchpeer-review

Abstract

In this paper we propose a novel approach to derive necessary and sufficient stability conditions of individual queues in a polling model. We illustrate the approach by applying it to a reservation scheme, which is modeled as a polling model with gated limited service policy and dependent walk times. Our approach is based on a notion of queue stability ordering and Loynes' theorem for a G/G/1 queue. The queue stability ordering specifies the sequence of queues to become unstable when the system traffic increases linearly. We have proved that the stability of any two queues in the system can be compared based on their quantities γ/M, where γ is the customer arrival rate to the queue and M is the maximum number of customers to be served during each server visit. Given a stability ordering, we obtain the queue stability conditions via Loynes' theorem and dominant systems. The queue stability conditions obtained are analytically computable except for a non-linear quantity. We use a vacation model to approximate this quantity and the stability conditions computed using the approximation are very accurate. We also show that the new queue stability results generalize the system stability results obtained previously.
Original languageEnglish
Pages (from-to)156-167
Number of pages12
JournalProceedings of SPIE - The International Society for Optical Engineering
Volume3530
DOIs
Publication statusPublished - 1 Dec 1998
EventPerformance and Control of Network Systems II - Boston, MA, United States
Duration: 2 Nov 19984 Nov 1998

Keywords

  • Dominant systems
  • Loynes' Theorem
  • Polling models
  • Queue stability analysis
  • Queue stability ordering
  • Reservation schemes

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering

Cite this