Implémentation d’un protocole de routage à Vecteur Distance sous NS2

Architectures et modèle de référence

                À part les supports de communications (physique ou hertzien), il faut en outre une architecture logicielle chargée du contrôle des paquets dans le réseau. Cela est nécessaire, en effet, pour que les données arrivent correctement au destinataire, avec la QoS exigée. Les trois grandes architectures qui se disputent actuellement le marché mondial des réseaux sont l’architecture OSI (Open Systems Interconnection) qui provient de la normalisation de l’ISO (International Standardization Organization ), l’architecture TCP/IP qui est utilisé dans le réseau Internet et l’architecture pour l’environnement ATM (Asynchronous Transfer Mode) introduite par l’UIT (Union Internationale des Télécommunications). OSI constitue toujours le modèle de référence pour décrire les éléments nécessaires à la réalisation d’une architecture réseau [4].

Qualité de Service

               La QoS est la capacité à véhiculer dans de bonnes conditions un type de trafic donné. La QoS est un concept de gestion qui a pour but d’optimiser les ressources d’un réseau (en management du système d’information) ou d’un processus (en logistique) et de garantir de bonnes performances aux applications critiques pour l’organisation. La QoS permet d’offrir aux utilisateurs des débits et des temps de réponse différenciés par applications (ou activités) suivant les protocoles mis en œuvre au niveau de la structure. Elle permet ainsi aux fournisseurs de services (départements réseaux des entreprises, opérateurs…) de s’engager formellement auprès de leurs clients sur les caractéristiques de transport des données applicatives sur leurs infrastructures IP.
Exigences : Sur un réseau en mode connecté, tous les paquets appartenant au flux suivent la même route. Sur un réseau fonctionnant dans le mode sans connexion, les paquets peuvent emprunter différents parcours. Les besoins de chaque flux peuvent être caractérisés par quatre paramètres principaux qui sont la fiabilité, le délai de transit, la gigue, le débit binaire et le déséquencement. Ceux-ci déterminent ensemble la QoS, que le flux requiert [10] [11].La fiabilité est caractérisée par le taux moyen d’erreurs lors d’un échange de données. Le délai de transit, latence, temps de réponse ou temps d’acheminement est le temps écoulé entre l’envoi d’un paquet et sa réception. La gigue est la variation de délai de bout en bout. Le débit binaire, souvent appelé bande passante par abus de langage est le taux de transfert maximum pouvant être maintenu entre deux terminaux. Le déséquencement définit la modification de l’ordre d’arrivée des paquets.
Enjeux : Selon le type d’un service envisagé, la qualité pourra résider dans le débit (téléchargement ou diffusion vidéo), le délai (pour les applications interactives ou la téléphonie), la disponibilité (accès à un service partagé) ou encore le taux de pertes de paquets (sans influence pour de la voix ou de la vidéo, mais critiques pour le téléchargement) [12].

QoS assurée par TCP

               TCP possède différents algorithmes, dits Algorithmes TCP, pour satisfaire certains critères de la QoS. Parmi les plus connus sont : TCP tahoe, TCP Reno, TCP new Reno et TCP Vegas. Ces algorithmes travaillent principalement sur la régulation du débit en fonction de la bande passante de la liaison. Le débit optimal à utiliser pour un lien n’est jamais connu par TCP : d’ailleurs il est difficile à estimer. IP qui porte TCP, ne garantie pas que le chemin sera stable dans le temps à travers le réseau, d’où une impossibilité à prédire le débit à utiliser. De plus le débit est aussi conditionné par d’autres facteurs comme l’existence de flux concurrents sur une partie du chemin : comme le cas de plusieurs téléchargements simultanés sur des serveurs de différents niveaux de performance. C’est ainsi que TCP essaye de deviner le meilleur débit à utiliser en essayant de toujours augmenter le débit jusqu’à la survenue d’une perte de paquet. Les algorithmes TCP sont distingués par la forme du slow-start (démarrage lent) et leur façon d’utiliser la bande passante disponible [17].

Algorithme à vecteur distance

                Avec l’algorithme de routage à vecteur distance, chaque routeur maintient sa propre table de routage, c’est-à-dire qu’un vecteur lui indique la meilleure distance vers chaque destination et la ligne à utiliser dans chaque cas [19]. Ainsi chaque nœud connaît la distance (valeur du lien) vers les nœuds adjacents et distribue cette information à tous ses voisins. Un calcul et/ou une nouvelle distribution sont effectués quand il y a changement de coût ou découverte d’un lien. Cet algorithme est basé sur celui de Bellman-Ford (cf. A1).

Protocoles de routage internes

              Les principaux protocoles de routage interne sont RIP (Routing Information Protocol), OSPF (Open Shortest Path First ), IGRP (Interior Gateway Routing Protocol ), et IS-IS (Intermediate System – Intermediate System).
a. RIP : RIP rentre dans la classe des algorithmes de routage à vecteur de distance et est basé sur l’algorithme de plus court chemin de Bellman et, plus tard, amélioré par Ford et Bellman. Une version repartis utilise l’algorithme de Ford-Fulkerson. La métrique utilisée est la distance en termes de nombre de saut et sa valeur maximale est limitée à quinze. Chaque routeur envoie périodiquement (toutes les trente secondes) l’état de ses table sà ses voisins sous forme de broadcast . Si aucune information ne concernant une certaine route n’arrive durant trois échanges successifs, celle-ci sera supprimée. RIP s’appuie sur le protocole supérieure UDP, le format de la première version d’un datagramme RIP est donné dans Fig 2.7. Le champ Commande permet de distinguer les différents types de messages (requête, réponse,…), tandis que le champ Version identifie la version du protocole. Pour chaque entrée de la table de routage de l’émetteur, chaque message RIP comporte l’adresse IP du réseau (champ Adresse IP) et la distance de celui-ci au routeur émetteur (champ Métrique). Le champ Famille d’adresse est mis à 2 pour la famille IP [9]. La taille maximale des datagrammes est de l’ordre du nombre de routeurs dans le réseau. Toutefois, un datagramme RIP ne peut contenir que 25 routes.
b. OSPF : OSPF fait partie des protocoles de routage à état de liens. Il subdivise un AS en plusieurs zones. De ce fait, il découpe le routage en trois catégories et distingue trois types de routeurs : les routeurs intra-zones, inter-zones et externes. Ce qui permet la diminution des échanges d’informations de routage dans le réseau. Les zones d’un AS sont reliées entre elles par une zone appelée backbone, un routeur interzone a au moins une sortie dans celui-ci (Fig 2.8). OSPF met en œuvre trois sous-protocoles: le protocole Hello, le protocole d’échange et le protocole d’inondation. Le protocole Hello est utilisé entre deux routeurs adjacents pour synchroniser leur base de connaissance ; il s’agit d’un établissement et maintien des relations d’adjacence. Le protocole d’échange permet, lors de l’initialisation d’un routeur, l’acquisition des entrées de sa base de données. Le protocole d’inondation est utilisé par un routeur pour signaler la modification de l’état d’un lien qui lui est rattaché, ce protocole peut être de type requête, de mise à jour ou d’acquittement [9]. L’état de lien est inondé dans la zone. Chaque routeur calcule donc sa table à partir des états de liens reçus des autres routeurs de l’AS.L’état de liens d’un routeur n’est envoyé qu’en cas de modification et les mises à jour sont transmises par inondation fiabilisée, c’est-à-dire qu’un acquittement est envoyé à l’émetteur direct du message d’inondation et non pas à l’émetteur initial.
c. IGRP : IGRP est un protocole interne propriétaire à Cisco. Le coût d’une route est calculé dynamiquement et prend en compte pour chaque route: le délai, le débit minimal du lien le plus faible, la charge de ce lien et la fiabilité. Il supporte l’équilibrage de charge entre chemins du même coût, mais aussi entre chemins de coûts différents [4].

CONCLUSION

               L’évolution des réseaux de communication a grandement marqué le début du XXIème siècle dans le monde. À l’origine, destinés pour le transport de la voix, puis des données, et dernièrement pour le multimédia, les réseaux téléinformatiques ont révolutionné la vie de la société moderne. Nombreuses applications n’auraient aucune utilité sans un moyen de communication, d’autre ne seraient pas exploitables. Sur ce, diverses études et travaux de recherches ont été menés. Des architectures de référence, comme l’OSI, ont été proposées et continuent encore d’être exploités à l’heure actuelle. Le routage constitue l’essence de la communication informatique. Consistant à établir une route entre deux terminaux distants, il recouvre plusieurs notions de bases et avancés que les Ingénieurs réseaux ne peuvent pas s’en dispenser. En effet, le routage utilise des notions mathématiques et techniques très complexe, surtout quand le système à étudier est diversifié, ce qui est généralement le cas. Concernant ce travail, l’implémentation du protocole de routage à vecteur distance, baptisé « DVProtocol v1.0» sous le simulateur NS2 de VINT, a été une réussite. Les recherches effectuées lors de la réalisation a permis d’acquérir des connaissances scientifiques et informatiques très élargies. En effet, la conception s’était basée sur les théories sur le routage, tant dans son aspect technique que mathématique, et sur le fonctionnement de NS2 lui-même. L’une des difficultés rencontrées dans la réalisation était la recherche effectuée concernant l’architecture de NS2. En effet, toute implémentation de nouveau composant dans ce simulateur implique impérativement des pré-requis sur le fonctionnement interne de ce dernier. La conception a dû être précédée d’une étude de son comportement vis-à-vis des modèles de simulation. Plus précisément, une analyse minutieuse de son code source a été indispensable. En outre, l’analyse de résultats de simulation n’était pas une tâche évidente avec NS2 car il nécessite l’écriture de scripts externes au système. Par aiileurs, DVProtocol a pour limite de ne pas tenir compte du débit et des charges du réseau pour le choix d’itinéraire. En effet, il utilise l’algorithme de recherche de chemin le plus court de Bellman-Ford et ne tient compte donc que le nombre de saut comme critère de choix de route. Pour cela, la conception d’un protocole de routage utilisant les outils mathématiques sur les problèmes de transport, notamment l’algorithme de Ford-Fulkerson, ou la technique d’apprentissage par renforcement, comme le Q-Learning, pourrait être envisageable, une continuité de ce travail que nous laissons à nos cadets.

Table des matières

INTRODUCTION
Chapitre 1: GENERALITES SUR LE RESEAU INFORMATIQUE
1. 1 Eléments de base des réseaux
1. 2 Qualité de Service
1. 3 Architecture TCP/IP
Chapitre 2: CONCEPTS DE BASE SUR LE ROUTAGE
2. 1 Routage et routeur
2. 2 Algorithmes de routage
2. 3 Protocoles de routage
Chapitre 3: IMPLEMENTATION ET SIMULATION SOUS NS2
3. 1 Présentation de NS2
3. 2 Implémentation et simulation
3. 3 Conclusion
CONCLUSION

Télécharger le rapport complet