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

Natalia Osipova (1) , Urtzi Ayesta (2) , Konstantin Avrachenkov (1)

1 MAESTRO - Models for the performance analysis and the control of networks
2 LAAS - Laboratoire d'analyse et d'architecture des systèmes

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.

Mots clés: M/G/1; file d'attente multi-classe; la politique de Gittins; NS-2

Domaines: Réseaux et télécommunications [cs.NI]

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