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

Natalia Osipova; Urtzi Ayesta; Konstantin Avrachenkov

inria-00371944, version 1

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

Natalia Osipova () ¹, Urtzi Ayesta ()^a^, 2, Konstantin Avrachenkov ()^b^, 1

(2009)

a – CNRS LAAS
b – INRIA
1: MAESTRO (INRIA Sophia Antipolis)
INRIA – Université Montpellier II - Sciences et techniques France
2: Laboratoire d'analyse et d'architecture des systèmes (LAAS)
http://www.laas.fr
CNRS : UPR8001 – Université Paul Sabatier [UPS] - Toulouse III – Institut National Polytechnique de Toulouse - INPT – Institut National des Sciences Appliquées (INSA) - Toulouse 7 Av du colonel Roche 31077 TOULOUSE CEDEX 4 France

Bibliographic reference

Attached file list to this document:

TEX

Logo-INRIA-Sophia-couleur.ps

(28.5 KB)

RR_Gittins.tex

(75.3 KB)

RR_Gittins.out

(1.2 KB)

rra4.sty

(17.3 KB)

Logo-INRIA-Rhone-Alpes-couleur.ps

(27.1 KB)

clrscode.sty

(11.1 KB)

Logo-INRIA-Futurs-couleur.ps

(25.7 KB)

RR_Gittins.aux

(10.1 KB)

Logo-INRIA-couleur.ps

(35.1 KB)

rr.dtx

(61.7 KB)

Logo-INRIA-Rennes-couleur.ps

(25.5 KB)

(24.4 KB)

(17.3 KB)

(1.1 KB)

(1.4 KB)

(43 KB)

(27.5 KB)

Logo-INRIA-Rocq-couleur.ps

(28.5 KB)

rap-tech1.ps

(19.5 KB)

Logo-INRIA-Lorraine-couleur.ps

(25.8 KB)

rap-rech1.ps

(19.5 KB)

bibliography.bib

(43.1 KB)

Logo-INRIA-vertical.ps

(29.5 KB)

RR_Gittins.bbl

(3.8 KB)

plots_chapter5_gitt

hazard_rates_NPareto.eps

(28.8 KB)

(35.7 KB)

(9.4 KB)

(30.4 KB)

(25.4 KB)

(9.5 KB)

(27.1 KB)

hazard_rates_2Pareto.eps

(24.7 KB)

NS2_2Pareto_scheme.eps

(27.2 KB)

hazard_rates_2Pareto_extens.eps

(30.6 KB)

policy_HE.eps

(32.8 KB)

T_mean_2Pareto.eps

(9.7 KB)

RR_Gittins.ps

(703 KB)

PDF

RR_Gittins.pdf

(294 KB)

inria-00371944, version 1
http://hal.inria.fr/inria-00371944
oai:hal.inria.fr:inria-00371944
From: Natalia Osipova <>
Submitted on: Monday, 30 March 2009 18:00:11
Updated on: Wednesday, 3 October 2012 14:17:36

See short view

Associated documents

PS :

PDF :

Export

Bibtex EndNote TEI RefWorks

%% inria-00371944, version 1
%% http://hal.inria.fr/inria-00371944
@techreport{osipova:inria-00371944,
    hal_id = {inria-00371944},
    url = {http://hal.inria.fr/inria-00371944},
    title = {{Optimal policy for multi-class scheduling in a single server queue}},
    author = {Osipova, Natalia and Ayesta, Urtzi and Avrachenkov, Konstantin},
    abstract = {{Nous obtenons la politique optimale pour l'ordonnancement dans une file d'attente multi-classe avec un serveur unique. Nous appliquons les r{{\'e}}sultats de Gittins \cite{Git89}, o{{\`u}} il avait trouv{{\'e}} la politique optimale qui minimise le temps moyen de sejour dans le syst{{\`e}}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{{\'e}}sultats de Gittins permet de caract{{\'e}}riser la politique d'ordonnancement optimale dans la file d'attente $M/G/1$ multi-classe. Nous appliquons le r{{\'e}}sultat g{{\'e}}n{{\'e}}ral dans plusieurs cas, lorsque la distribution de temps de service a un taux de hasard d{{\'e}}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{{\^a}}ches de classes diff{{\'e}}rentes sont classifi{{\'e}}s sur plusieurs niveaux de priorit{{\'e}} en fonction de leur service obtenu. Nous obtenons pour chaque classe l'expression du temps moyen conditionnel de s{{\'e}}jour en utilisant une approche de t{{\^a}}che marqu{{\'e}}es. Avec {\c c}a, nous comparons num{{\'e}}riquement le temps moyen de s{{\'e}}jour dans le syst{{\`e}}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{{\`e}}de la propri{{\'e}}t{{\'e}} de DHR, la politique optimale de Gittins peut {{\^e}}tre appliqu{{\'e}}e dans les routeurs d'Internet, o{{\`u}} les paquets g{{\'e}}n{{\'e}}r{{\'e}}s par des applications diff{{\'e}}rentes doivent {{\^e}}tre servis. Typiquement, le routeur n'a pas d'acc{{\`e}}s au temps exact de s{{\'e}}jour requis (en paquets) de la connexion TCP, mais il peut avoir l'acc{{\`e}}s au service atteint de chaque connexion. Ainsi, nous impl{{\'e}}mentons l'algorithme optimal de Gittins en NS-2 et nous faisons des simulations num{{\'e}}riques pour {{\'e}}valuer le gain de performance possible.}},
    keywords = {M/G/1, file d'attente multi-classe, la politique de Gittins, NS-2},
    language = {English},
    affiliation = {MAESTRO - INRIA Sophia Antipolis , Laboratoire d'analyse et d'architecture des syst{\`e}mes - LAAS},
    pages = {30},
    type = {Research Report},
    year = {2009},
    pdf = {http://hal.inria.fr/inria-00371944/PDF/RR\_Gittins.pdf},
}

%F inria-00371944, version 1
%0 Report
%U http://hal.inria.fr/inria-00371944
%2 INFO:INFO_NI
%T Optimal policy for multi-class scheduling in a single server queue
%A Osipova, Natalia
%A Ayesta, Urtzi
%A Avrachenkov, Konstantin
%+ MAESTRO - INRIA Sophia Antipolis , Laboratoire d'analyse et d'architecture des systèmes - LAAS
%X 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.
%G English
%2 Research Report
%P 30
%8 2009-00-00
%K M/G/1, file d'attente multi-classe, la politique de Gittins, NS-2
%2 2009

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00371944"><monogr>
<author><persName><forename>Natalia</forename><surname>Osipova</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">MAESTRO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<author><persName><forename>Urtzi</forename><surname>Ayesta</surname></persName>
<affiliation>
<orgName type="laboratory">LAAS</orgName>
<orgName type="team">Laboratoire d'analyse et d'architecture des systèmes</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UPR8001</orgName>
<orgName type="institution">Université Paul Sabatier [UPS] - Toulouse III</orgName>
<orgName type="institution">Institut National Polytechnique de Toulouse - INPT</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Toulouse</orgName>
</affiliation>
</author>
<author><persName><forename>Konstantin</forename><surname>Avrachenkov</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">MAESTRO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<title type="main" level="m">Optimal policy for multi-class scheduling in a single server queue</title><title type="main" level="m">Optimal policy for multi-class scheduling in a single server queue</title><imprint><biblScope type="publicationDate">2009-00-00</biblScope><biblScope type="pp">30</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00371944</idno><idno type="HALFile">http://hal.inria.fr/inria-00371944/PDF/RR_Gittins.pdf</idno></biblStruct>
</listBibl>
</listBibl>