The equivalence between processor sharing and service in random order

The equivalence between processor sharing and service in random order

0.00 Avg rating0 Votes
Article ID: iaor20033019
Country: Netherlands
Volume: 31
Issue: 4
Start Page Number: 254
End Page Number: 262
Publication Date: Jul 2003
Journal: Operations Research Letters
Authors: , , ,
Keywords: GI/M/1 queues
Abstract:

In this note we explore a useful equivalence relation for the delay distribution in the G/M/1 queue under two different service disciplines: (i) processor sharing (PS); and (ii) random order of service (ROS). We provide a direct probabilistic argument to show that the sojourn time under PS is equal (in distribution) to the waiting time under ROS of a customer arriving to a non-empty system. We thus conclude that the sojourn time distribution for PS is related to the waiting-time distribution for ROS through a simple multiplicative factor, which corresponds to the probability of a non-empty system at an arrival instant. We verify that previously derived expressions for the sojourn time distribution in the M/M/1 PS queue and the waiting-time distribution in the M/M/1 ROS queue are indeed identical, up to a multiplicative constant. The probabilistic nature of the argument enables us to extend the equivalence result to more general models, such as the M/M/1/K queue and ·/M/1 nodes in product-form networks.

Reviews

Required fields are marked *. Your email address will not be published.