Packetization and Aggregate Scheduling

Anne Bouillard; Nadir Farhi; Bruno Gaujal

inria-00608852, version 1

Packetization and Aggregate Scheduling

Anne Bouillard ( Author to contact preferably )^a^, 1, 2, Nadir Farhi () ³, Bruno Gaujal ()^b^, 4

N° RR-7685 (2011)

Abstract: We present a new formalism for data packetization in Network Calculus. Packet curves are introduced to model constraints on the packet lengths of data flows. Indeed, a more precise knowledge of the packet characteristics can be efficiently exploited to get tighter performance bounds, specially when dealing with scheduling policies based on packet count, such as round-robin. A second use of packet curves is the packetization of a superposition of periodic flows. Finally, we show that packet curves can be used to compute a global service curve for the aggregate of several flows, with different service curves, sharing a unique queue.

a – Ecole Normale Supérieure de Paris - ENS Paris
b – INRIA
1: Laboratoire d'informatique de l'école normale supérieure (LIENS)
CNRS : UMR8548 – Ecole normale supérieure de Paris - ENS Paris
2: TREC (INRIA Rocquencourt)
INRIA – Ecole normale supérieure de Paris - ENS Paris
3: Génie des Réseaux de Transport Terrestres et Informatique Avancée (IFSTTAR/GRETTIA)
IFSTTAR – Université Paris-Est Créteil Val-de-Marne (UPEC)
4: MESCAL (INRIA Grenoble Rhône-Alpes / LIG laboratoire d'Informatique de Grenoble)
CNRS : UMR5217 – INRIA – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Institut polytechnique de Grenoble (Grenoble INP)

inria-00608852, version 1
http://hal.inria.fr/inria-00608852
oai:hal.inria.fr:inria-00608852
From: Anne Bouillard <>
Submitted on: Friday, 15 July 2011 12:16:03
Updated on: Thursday, 5 January 2012 10:31:23

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%F inria-00608852, version 1
%0 Report
%U http://hal.inria.fr/inria-00608852
%2 INFO:INFO_DM;INFO:INFO_PF
%T Packetization and Aggregate Scheduling
%A Bouillard, Anne
%A Farhi, Nadir
%A Gaujal, Bruno
%+ Laboratoire d'informatique de l'école normale supérieure - LIENS , TREC - INRIA Rocquencourt , Génie des Réseaux de Transport Terrestres et Informatique Avancée - IFSTTAR/GRETTIA , MESCAL - INRIA Grenoble Rhône-Alpes / LIG laboratoire d'Informatique de Grenoble
%X We present a new formalism for data packetization in Network Calculus. Packet curves are introduced to model constraints on the packet lengths of data flows. Indeed, a more precise knowledge of the packet characteristics can be efficiently exploited to get tighter performance bounds, specially when dealing with scheduling policies based on packet count, such as round-robin. A second use of packet curves is the packetization of a superposition of periodic flows. Finally, we show that packet curves can be used to compute a global service curve for the aggregate of several flows, with different service curves, sharing a unique queue.
%2 Nous présentons dans ce rapport un nouveu formalisme de paquétisation de donnée en Network Calculus. La notion de courbe de paquets est introduite pour modéliser les contraintes sur les longueurs des paquets de flux de données. En effet, une connaissance plus précise des caractéristiques de paquets peuvent être exploitées efficacement pour obtenir de meilleurs bornes de performances, spécialement dans le cas de politiques de service basées sur le comptage de paquets, comme la politique round-robin. Deuxièmement, les courbes de paquets permettent de calculer des caractéristiques (courbes d'arrivées) plus précises de flux périodiques superposés. Enfin, nous montrons comment ces courbes peuvent être utilisées pour calculer une courbe de service globale pour des flux partageant différemment une même ressource.
%G English
%2 Research Report
%P 24
%8 2011-07-15
%K Network Calculus ; packetization ; scheduling ; quality of service guarantees
%Z RR-7685

<?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-00608852"><monogr>
<author><persName><forename>Anne</forename><surname>Bouillard</surname></persName>
<affiliation>
<orgName type="laboratory">LIENS</orgName>
<orgName type="team">Laboratoire d'informatique de l'école normale supérieure</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8548</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">TREC</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
</affiliation>
</author>
<author><persName><forename>Nadir</forename><surname>Farhi</surname></persName>
<affiliation>
<orgName type="laboratory">IFSTTAR/GRETTIA</orgName>
<orgName type="team">Génie des Réseaux de Transport Terrestres et Informatique Avancée</orgName>
<country>FR</country>
<orgName type="institution">IFSTTAR</orgName>
<orgName type="institution">Université Paris-Est Créteil Val-de-Marne (UPEC)</orgName>
</affiliation>
</author>
<author><persName><forename>Bruno</forename><surname>Gaujal</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LIG laboratoire d'Informatique de Grenoble</orgName>
<orgName type="team">MESCAL</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5217</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">Institut polytechnique de Grenoble (Grenoble INP)</orgName>
</affiliation>
</author>
<title type="main" level="m">Packetization and Aggregate Scheduling</title><title type="main" level="m">Packetization and Aggregate Scheduling</title><imprint><biblScope type="publicationDate">2011-07-15</biblScope><biblScope type="pp">24</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00608852</idno><idno type="HALFile">http://hal.inria.fr/inria-00608852/PDF/RR-7685.pdf</idno></biblStruct>
</listBibl>
</listBibl>