Application du Codage Réseau aux Architectures à Garanties de Qualité de Service (QoS)

Muriel Médard

Description

Niveau: Supérieur, Doctorat, Bac+8

• mémoire

THÈSE En vue de l'obtention du DOCTORAT DE L'UNIVERSITÉ DE TOULOUSE Délivré par Institut National Polytechnique de Toulouse (INPT) Discipline ou spécialité : Informatique, Réseaux JURY Muriel Médard Professeur d'Université, MIT, Etats Unis Chadi Barakat HDR, Chargé de Recherche, INRIA, Sophia Antipolis, France Jérôme Lacan Professeur ISAE, France Christian Fraboul Professeur INPT, France Ecole doctorale : Mathématiques, Informatique et télécommunications de Toulouse (M.I.T.T.) Unité de recherche : DMIA/ISAE Directeur(s) de Thèse : Jérôme LACAN Christian FRABOUL Présentée et soutenue par Ali Mahmino Le x Titre : Application du Codage Réseau aux Architectures à Garanties de Qualité de Service (QoS) Kavé Salamatian Professeur à l'Université de Lancaster, Angleterre Francès Fabrice Enseignant, chercheur à l'ISAE, France 12.11.2009

• codage réseau linéaire


• nouvelles stratégies de codage réseau


• application du codage réseau aux architectures


• codage réseau


• profond respect


• stratégie orientée


• réseau


• département de mathématiques


• qos

Sujets

• Mémoire
• Institut national polytechnique de Toulouse
• Toulouse
• Université du Lancaster
• Frances
• Médard
• Antipolis

Informations

• Publié par: profil-feym-2012
• Nombre de lectures: 68
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

THÈSE

En vue de l'obtention du
DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE
Délivré par Institut National Polytechnique de Toulouse (INPT)
Discipline ou spécialité : Informatique, Réseaux
Présentée et soutenue par Ali Mahmino
Le 12.11.2009x
Titre :
Application du Codage Réseau aux Architectures à Garanties de Qualité de Service (QoS)
JURY
Professeur d'Université, MIT, Etats UnisMuriel Médard
Chadi Barakat HDR, Chargé de Recherche, INRIA, Sophia Antipolis, France
Kavé Salamatian Professeur à l'Université de Lancaster, Angleterre
Francès Fabrice Enseignant, chercheur à l'ISAE, France
Jérôme Lacan Prof esseur ISAE, France
Christian F r aboul Prof es seur INPT, France

Ecole doctorale : Mathématiques, Informatique et télécommunications de Toulouse (M.I.T.T.)

Unité de recherche : DMIA/ISAE

Directeur(s) de Thèse : Jérôme LACAN

Christian FRABOULRemerciements
Je tiens tout d’abord à remercier mes directeurs de thèse, M. le Professeur Jérôme Lacan,
pour m’avoir guidé, encouragé, supporté et pour la gentillesse, la patience et toute l’attention
qu’il a manifesté à mon égard durant cette thèse, et pour sa disponibilité et sa confiance et ses
précieux conseils et M. le Professeur Christian Fraboul, pour m’avoir encadré et dirigé par
ses conseils avisés et suggestions qui ont permis l’accomplissement de ce travail. Je ne sais
comment exprimer ma gratitude à ces deux personnes autrement qu’en leur adressant ici les
marques de ma reconnaissance et de mon profond respect.
Je remercie M. Patrick Sénac, chef du Département de Mathématiques, Informatique et
Automatique (DMIA) à l’Institut Supérieur de l’Aéronautique et de l’Espace (ISAE) à Toulouse,
France, pour m’avoir accueilli au sein de son département et ses groupes.
Je suis très sensible à l’honneur que m’a fait M. Kavé Salamatian, professeur à l’université
de Lancaster en Angleterre, en acceptant de présider le jury de cette thèse. Je lui exprime toute
ma reconnaissance pour l’intérêt porté à ce travail.
J’exprime toute ma gratitude à MmeMuriel Médard, professeur au département de génie
électrique et informatique et au laboratoire de recherches d’électronique à l’Institut de Techno-
logie du Massachusetts (MIT) à Cambridge, Massachusetts, États-Unis, et M. Chadi Barakat,
HDR, chargé de recherche, INRIA, Sophia-Antipolis, France, pour l’honneur qu’ils m’ont fait
en acceptant d’être les rapporteurs de cette thèse . Ils ont également contribué par leurs nom-
breuses remarques et suggestions à améliorer la qualité de ce mémoire, et je leur en suis très
reconnaissant.
J’adresse ma profonde reconnaissance à Monsieur Fabrice Francès, enseignant, chercheur
au Département de Mathématiques, Informatique et Automatique (DMIA) à l’Institut Supé-
rieur de l’Aéronautique et de l’Espace (ISAE) à Toulouse, France, pour l’honneur qu’il me fait
en acceptant de bien vouloir participer à ce jury de soutenance
Je tiens aussi à mentionner le plaisir que j’ai eu à travailler au sein du DMIA, et j’en remer-
cie ici tous les membres qui sans eux, mes conditions de travail auraient sans doute été très
différentes et beaucoup moins agréables. Je pense ici en particulier à Mlle. et MM. A. Mifdaoui,
E. Lochin, F. Francès, P. de Saqui-Sannes, T. Pérennou, Y. Caumel, B. Jarlan.
Je passe ensuite une dédicace spéciale à tous les jeunes gens avec qui j’ai eu le plaisir de tra-
vailler et de côtoyer durant ces quelques années à Toulouse, à savoir Emmanuel, Hervé, Mathieu,
Amine, Ta r e k, Alex, Guodong, Lei, Thomas, Pierre,....
Je remercie chaudement mes parents mes frères et sœurs et le reste de la famille pour leurs
encouragements et leur assistance aussi bien matérielle que morale qui m’ont permis de faire
cette thèse dans de bonnes conditions.
J’associe à mes remerciements l’Université d’Alep et le laboratoire de Télécommunications
Spatiales et Aéronautiques (TéSA- Toulouse) pour leur soutien financier.
iRemerciements
1Enfin, je voudrais remercier mes amis Rami et Manel, A. Kazem et Samar, Maya , Sam, Ha-
kima, Houda, Samir et les autres pour leur aide sympathique tant sur le plan, scientifique qu’hu-
main et pour la bonne humeur dans laquelle ce travail a été accompli.
Pour finir, Je tiens également à exprimer toute ma gratitude envers Mlle. la Dr. H. Azira et
M. A. Bouabdallah pour leur aide et leur soutien et pour leurs relectures avisées du manuscrit.
Ali MAHMINO
Novembre 2009
Département Mathématiques, Informatique, Automatique (DMIA)
Institut supérieur de l’aéronautique et de l’espace (ISAE), Toulouse, France
1. Merci du fond du cœur pour tout
iiTable des matières
Résumé 1
1 Introduction 3
1.1 Présentation de la problématique et des objectifs .............. 4
1.2 Organisation du document........................... 6
2 État de l’art et notions de base 9
2.1 Introduction ................................... 10
2.2 Codage réseau .................................. 10
2.2.1 Introduction du codage réseau .................... 10
2.2.2 Codage réseau et théorie des graphes ................ 13
2.2.3 Les principales notions théoriques du codage réseau ....... 15
2.2.3.1 Théorie de Min-cut Max-flux ................ 15
2.2.3.2 Codage réseau linéaire multicast ............. 15
2.2.3.3 réseau linéaire aléatoire .............. 17
2.2.3.4 Construction algébrique du codage réseau ........ 20
2.3 Bénéfices et intérêts de codage réseau .................... 28
2.3.1 Augmentation de la capacité multicast et du débit ......... 29
2.3.2 Diminution de l’énergie par bit .................... 29
2.3.3 Robustesse et tolérance aux fautes .................. 31
2.4 Applications de codage réseau dans différents domaines et types de
réseaux ...................................... 32
2.4.1 Internet ................................. 32
2.4.1.1 Modèle de paquet ...................... 33
2.4.1.2 de file d’attente ................... 35
2.4.2 Réseaux de recouvrement "Overlay" ................. 36
2.4.3 ad-hoc et sans fil ....................... 37
iiiTable des matières
3 Codage réseau et réseaux avec des garanties de qualité de service (QoS) 39
3.1 Introduction ................................... 40
3.2 Réseaux avec des garanties de qualité de service (QoS) .......... 40
3.2.1 Concepts et exemples de réseaux avec des garanties de QoS ... 40
3.2.1.1 Internet et Qualité de Service................ 40
3.2.1.2 ATM et Qualité de Service ................. 43
3.2.1.3 Les réseaux embarqués ................... 45
3.3 Besoins et applications du codage réseau au sein des réseaux avec QoS
garantie...................................... 49
3.3.1 Intérêts du codage réseau pour les réseaux avec QoS garantie .. 49
3.3.2 Conditions d’application du codage réseau ............. 51
3.4 Le calcul réseau ................................. 52
3.4.1 Intérêts du calcul réseau pour notre problématique ........ 53
3.4.2 Les notions de base du calcul réseau ................. 53
4 Nouvelles stratégies de codage réseau 59
4.1 Introduction et hypothèses........................... 60
4.2 Stratégie Orientée Réseau (NOS : Network-Oriented Strategy) ...... 62
4.2.1 Introduction ............................... 62
4.2.2 Définitions et hypothèses ....................... 62
4.2.3 Architecture d’un nœud de codage.................. 63
4.2.4 NOS au niveau d’un nœud de codage ................ 64
4.2.5 NOS au niveau d’un réseau ...................... 66
4.2.6 Discussion sur le décodage ...................... 71
4.3 Stratégie Orientée Flux (FOS : Flow-Oriented Strategy) .......... 71
4.3.1 Introduction ............................... 71
4.3.2 Définitions et hypothèses ....................... 71
4.3.3 FOS au niveau d’un nœud de codage ................ 72
4.3.3.1 Analyse des délais ...................... 73
4.3.3.2 Délai maximum dans un nœud intermédiaire de pre-
mier ordre .......................... 74
4.3.4 FOS au niveau d’un réseau ...................... 75
4.3.5 Discussion ...............