Queues Served by a Rotating Ring

E. G. Coffman, E. N. Gilbert, A. G. Greenberg, F. T. Leighton, Philippe Robert, A. L. Stolyar

Research output: Contribution to journalArticlepeer-review

Abstract

A ring of N cells rotates in discrete steps past N queues, moving customers from their queues of arrival to randomly chosen destinations. The model has applications in communication systems, processor interconnection networks, and flexible manufacturing. The arrivals to the queues are independent and stochastically identical. The total numbers of arrivals to the system during successive steps are independent, identically distributed random variables with mean A and finite second and third moments. A greedy policy governs the insertion of customers on the ring: A customer waiting at the head of a queue enters the next unoccupied cell to appear at that queue. The customer then remains on the ring a random travel time d, leaves, and frees its cell for another customer. A necessary condition for the system to be stable is λE[d] < N. If no customer travels further than once around the ring (d≥N),λ< 1 is sufficient for stability. Other results assume d to be stochastically bounded by an exponentially distributed travel time with mean N/μ. Then λ < μ is sufficient for stability. In the limit of large N, stable systems with fixed λ and μ have expected numbers 0(l) of waiting customers per queue; then a customer’s wait in a queue is usually negligible compared with his travel time. Simulations suggest that the mean number waiting in a queue may even be 0(1/N).

Original languageEnglish (US)
Pages (from-to)371-394
Number of pages24
JournalCommunications in Statistics. Stochastic Models
Volume11
Issue number3
DOIs
StatePublished - Jan 1 1995
Externally publishedYes

Keywords

  • Asymptotics
  • Cyclic Service
  • Loop Communication Systems
  • Processor Rings
  • Stability

ASJC Scopus subject areas

  • Modeling and Simulation

Fingerprint Dive into the research topics of 'Queues Served by a Rotating Ring'. Together they form a unique fingerprint.

Cite this