Deficit Round-Robin (DRR) is a packet scheduling algorithm devised for providing fair queuing in the presence of variable length packets. Upper bounds on the buffer occupancy and scheduling delay of a leaky bucket regulated flow have been proved to hold under DRR. However, performance bounds are important for real-time traffic such as video or voice, whereas regarding data traffic average performance indices are meaningful in most of the cases. In this paper we propose and solve a specific worst-case model that enables us to calculate quantiles of the queue length distribution at any time (and hence average delays) as a function of the offered load, when the arrival process is Poissonian. The model proposed is a discrete time discrete state Markov chain of M/G/1-Type, and hence we used the matrix analytic methodology to solve it. The structure of the blocks belonging to the transition probability matrix is fully exploited. As a result of the above exploitation an effective algorithm for computing the matrix G is proposed. The algorithm consists in diagonalizing suitable matrix functions by means of Discrete Fourier Transform and in applying Newton’s method.

An M/G/1 Queuing System with Multiple Vacations to Assess the Performance of a Simplified Deficit Round Robin Model

LENZINI, LUCIANO;MEINI, BEATRICE;MINGOZZI, ENZO;STEA, GIOVANNI
2003-01-01

Abstract

Deficit Round-Robin (DRR) is a packet scheduling algorithm devised for providing fair queuing in the presence of variable length packets. Upper bounds on the buffer occupancy and scheduling delay of a leaky bucket regulated flow have been proved to hold under DRR. However, performance bounds are important for real-time traffic such as video or voice, whereas regarding data traffic average performance indices are meaningful in most of the cases. In this paper we propose and solve a specific worst-case model that enables us to calculate quantiles of the queue length distribution at any time (and hence average delays) as a function of the offered load, when the arrival process is Poissonian. The model proposed is a discrete time discrete state Markov chain of M/G/1-Type, and hence we used the matrix analytic methodology to solve it. The structure of the blocks belonging to the transition probability matrix is fully exploited. As a result of the above exploitation an effective algorithm for computing the matrix G is proposed. The algorithm consists in diagonalizing suitable matrix functions by means of Discrete Fourier Transform and in applying Newton’s method.
2003
3540408142
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/191337
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact