Optimal policy for multi-class scheduling in a single server queue

Résumé : Nous obtenons la politique optimale pour l'ordonnancement dans une file d'attente multi-classe avec un serveur unique. Nous appliquons les r{é}sultats de Gittins \cite{Git89}, o{ù} il avait trouv{é} la politique optimale qui minimise le temps moyen de sejour dans le syst{è}me dans la file d'attente $M/G/1$ avec un serveur unique parmi toutes les politiques non-anticipatoires. Nous montrons que l'extension des r{é}sultats de Gittins permet de caract{é}riser la politique d'ordonnancement optimale dans la file d'attente $M/G/1$ multi-classe. Nous appliquons le r{é}sultat g{é}n{é}ral dans plusieurs cas, lorsque la distribution de temps de service a un taux de hasard d{é}croissant, comme Pareto et hyper-exponentielle. Nous montrons que dans le cas de plusieurs classes, la politique optimale est la politique prioritaire, dans laquelle les t{â}ches de classes diff{é}rentes sont classifi{é}s sur plusieurs niveaux de priorit{é} en fonction de leur service obtenu. Nous obtenons pour chaque classe l'expression du temps moyen conditionnel de s{é}jour en utilisant une approche de t{â}che marqu{é}es. Avec {\c c}a, nous comparons num{é}riquement le temps moyen de s{é}jour dans le syst{è}me entre les politiques de Gittins et les politiques populaires comme PS, FCFS et LAS. Comme dans Internet, la distribution de la taille des fichiers est ''heavy-tailed'' et poss{è}de la propri{é}t{é} de DHR, la politique optimale de Gittins peut {ê}tre appliqu{é}e dans les routeurs d'Internet, o{ù} les paquets g{é}n{é}r{é}s par des applications diff{é}rentes doivent {ê}tre servis. Typiquement, le routeur n'a pas d'acc{è}s au temps exact de s{é}jour requis (en paquets) de la connexion TCP, mais il peut avoir l'acc{è}s au service atteint de chaque connexion. Ainsi, nous impl{é}mentons l'algorithme optimal de Gittins en NS-2 et nous faisons des simulations num{é}riques pour {é}valuer le gain de performance possible.
Type de document :
Rapport
[Research Report] 2009, pp.30
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00371944
Contributeur : Natalia Osipova <>
Soumis le : lundi 30 mars 2009 - 18:00:11
Dernière modification le : jeudi 11 janvier 2018 - 16:56:42
Document(s) archivé(s) le : jeudi 10 juin 2010 - 19:16:47

Fichiers

RR_Gittins.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00371944, version 1

Citation

Natalia Osipova, Urtzi Ayesta, Konstantin Avrachenkov. Optimal policy for multi-class scheduling in a single server queue. [Research Report] 2009, pp.30. 〈inria-00371944〉

Partager

Métriques

Consultations de la notice

363

Téléchargements de fichiers

192