Application du Codage Réseau aux Architectures à Garanties de Qualité de Service (QoS), Network coding : principles and applications

Ali Mahmino

Description

Sous la direction de Christian Fraboul, Jérôme Lacan
Thèse soutenue le 12 novembre 2009: INPT
L'intérêt du codage réseau (network coding) pour améliorer le débit ou optimiser l'utilisation de la capacité du réseau a été clairement démontré dans différents contextes. Certains travaux ont notamment montré que le codage réseau permet de diminuer le délai (maximal et moyen) de transmission de bout-en-bout d'un paquet. Ceci est dû au fait que le traitement simultané de plusieurs paquets dans un noeud de codage permet de réduire le temps passé par les paquets dans les files d'attente par rapport au routage classique. Dans cette thèse, nous considérons l'application du codage réseau dans le contexte des réseaux proposant des garanties de qualité de service (QoS). Notre principale contribution est la proposition de trois stratégies de codage réseau assurant un niveau de QoS garantie exprimé en termes de délai de bout-en-bout. La première stratégie, appelée stratégie orientée réseau est une stratégie de codage aléatoire, en termes de dates d'arrivée des paquets, permettant de réduire au maximum le temps passé par les paquets dans les files d'attente des routeurs. Le point faible de cette approche, comme toute approche aléatoire, est qu'elle n'est pas totalement fiable. Les deux autres stratégies proposées implémentent une stratégie fiable en utilisant le concept de code en bloc. La première, appelée stratégie orientée flux est basée sur la définition classique du codage réseau alors que la seconde, appelée stratégie de transfert rapide, permet de réduire les temps d'attente des paquets dans les files d'attente en les transférant sans attendre tous les paquets du même bloc. Les délais maximums engendrés par les différentes stratégies ont été évalués au niveau d'un noeud de codage en utilisant le calcul réseau (network calculus). Les bornes de délais de bout-de-bout ont ensuite été calculées pour plusieurs types de réseaux. Dans la plupart des cas, ces bornes sont meilleures que celles obtenues pour le routage classique. Les stratégies de codage réseau fiables et la stratégie de routage ont été implémentées et évaluées par simulation sur les réseaux étudiés précédemment. Les résultats obtenus montrent que les pires cas de délais de bout-en-bout observés ont les mêmes comportements que les bornes maximales théoriques calculées, validant ainsi les stratégies proposées.
-Codage Réseau
-Délai
-Stratégie de Codage
-Nœud de Codage
-Routage
-Calcul Réseau
The Interest of network coding to improve the throughput or to optimize the use of the network capacity was clearly shown in various contexts. Certain work in particular showed that network coding allows to decrease the end-to-end transmission delay (maximum and average) of a package. This is due to the fact that the processing simultaneous of several packages in a coding node allows to reduce the maximum time spent by the packets in the buffers compared to a classical routing. In this thesis, we consider the application of network coding in the context of the networks providing quality-of-service (QoS) guarantees. Our contributions include the following. First, we propose three network coding strategies ensuring a level of QoS guaranteed expressed in terms of end-in-end delay. The first strategy, called Network-Oriented Strategy (NOS), is a random coding strategy. This coding strategy simply consists in combining the inputs packets present in the buffer of a node. It allows minimizing the time spent by the packets in the router's buffers. The weak point of this approach, as any random approach, is that it is not completely reliable. The two other strategies suggested implement a reliable strategy by using the concept of generation. The first, called Flow-Oriented Strategy (FOS) is based on the traditional definition of network coding whereas the second, called Fast Forwarding Strategy (FFS), allows reducing the packet's buffering delays by transferring them without awaiting all packets of the same generation. The maximum delays generated by different strategies have been evaluated at a coding node level by using network calculus. The end-to-end delay bounds have been then calculated for several types of networks. In most cases, these bounds are better than those obtained for the classical routing. The reliable network coding strategies and the routing strategy have been implemented and evaluated by simulation on networks studied previously. The results obtained show that the worst cases of end-in-end delays observed have the same behaviors as the calculated maximum theoretical bounds, thus validating the suggested strategies
Source: http://www.theses.fr/2009INPT023H/document

Sujets

• Routage

Informations

• Publié par: Thesee
• Nombre de lectures: 65
• 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 .........