Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing
We analyze a generalization of the Discriminatory Processor Sharing (DPS) queue in a heavy-traffic setting. Customers present in the system are served simultaneously at rates controlled by a vector of weights. We assume that customers have phase-type distributed service requirements and allow that customers have different weights in various phases of their service. In our main result we establish a state-space collapse for the queue length vector in heavy traffic. The result shows that in the limit, the queue length vector is the product of an exponentially distributed random variable and a deterministic vector. This generalizes a previous result by Rege and Sengupta (1996) who considered a DPS queue with exponentially distributed service requirements. Their analysis was based on obtaining all moments of the queue length distributions by solving systems of linear equations. We undertake a more direct approach by showing that the probability generating function satisfies a partial differential equation that allows a closed-form solution after passing to the heavy-traffic limit. Making use of the state-space collapse result, we derive interesting properties in heavy traffic: (i) For the DPS queue we obtain that, conditioned on the number of customers in the system, the residual service requirements are asymptotically i.i.d. according to the forward recurrence times. (ii) We then investigate how the choice for the weights influences the asymptotic performance of the system. In particular, for the DPS queue we show that the scaled holding cost reduces as classes with a higher value for d_k/E(B_k^fwd) obtain a larger share of the capacity, where d_k is the cost associated to class k, and E(B_k^fwd) is the forward recurrence time of the class-k service requirement. The applicability of this result for a moderately loaded system is investigated by numerical experiments.
|Keywords||Discriminatory processor sharing, heavy traffic, phase-type service requirements, residual service requirements, scheduling|
|MSC||Performance evaluation; queueing; scheduling (msc 68M20)|
|THEME||Logistics (theme 3), Energy (theme 4)|
|Publisher||Cornell University Library|
|Series||arXiv.org e-Print archive|
Verloop, I.M, Ayesta, U, & Núñez Queija, R. (2009). Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing. arXiv.org e-Print archive. Cornell University Library .