Gestion des files d’attente

Gestion des files d’attente

Network Simulator NS

NS est un outil logiciel de simulation de réseaux informatiques. Il est principalement bâti avec les idées de la conception par objets, de réutilisabilité du code et de modularité. Il est devenu aujourd’hui un standard de référence en ce domaine. C’est un logiciel dans le domaine public disponible sur l’Internet. Son utilisation est gratuite. Le logiciel est exécutable tant sous Unix que sous Windows. Le simulateur NS actuel est particulièrement bien adapté aux réseaux à commutation de paquets et à la réalisation de simulations de petite taille. Il contient les fonctionnalités nécessaires à l’étude des algorithmes de routage uni point ou multipoint, des protocoles de transport, de session, de réservation, des services intégrés, des protocoles d’application comme HTTP. De plus le simulateur possède déjà une palette de systèmes de transmission (couche 1 de l’architecture TCP/IP) d’ordonnanceurs et de politiques de gestion de files d’attente pour effectuer des études de contrôle de congestion. La liste des principaux composants actuellement disponible dans NS par catégorie est: Prises ensembles, ces capacités ouvrent le champ à l’étude de nouveaux mécanismes au niveau des différentes couches de l’architecture réseau. NS est devenu l’outil de référence pour les chercheurs du domaine. Ils peuvent ainsi partager leurs efforts et échanger leurs résultats de simulations. Cette façon de faire se concrétise aujourd’hui par l’envoi dans certaines listes de diffusion électronique de scripts de simulations NS pour illustration.

Conclusion

La plupart des recherches utilisent la modélisation et la simulation. Les finalités sont diverses : le modèle peut être utilisé à des fins de contrôle et de prédiction ou à des fins de compréhension et de confrontation de points de vue. Notre objectif est de même car nous allons utiliser la simulation afin de montrer les différents phénomènes engendrés dans un réseau et cela au niveau des files d’attente qui sont responsables de la bonne circulation des données (paquets) dans ce réseau. En résumé dans ce chapitre nous avons défini les différents types de réseau tel que LAN, MAN et WAN et aussi les topologies associées à ces derniers. Ensuite nous avons présenté ce que c’est que la simulation avec ses différents avantages et inconvénients. Ensuite nous avons introduit Le simulateur NS (Network Simulator) que nous allons utiliser pour la partie simulation grâce aux résultats de ces simulations nous allons pouvoir effectuer notre étude.

Fonctionnement du XCP

XCP [5] (eXplicit Control Protocol) est un protocole qui utilise l’assistance des routeurs pour informer précisément l’émetteur des conditions de congestion du réseau. Les paquets de données XCP comportent un en-tête de congestion, rempli par l’émetteur, qui contient la taille actuelle de la fenêtre de congestion de celui-ci (le champ H_cwnd), l’estimation du temps aller-retour (le champ rtt) et une valeur appelée feedback (le champ H_feedback), qui indique à l’émetteur un incrément (si elle est positive) ou un décrément (si elle est négative) à appliquer à sa fenêtre de congestion. Le champ H_feedback est le seul qui peut être modifié par les routeurs XCP en fonction des valeurs des 2 autres champs. Quand le récepteur reçoit un paquet de données, il recopie l’en-tête du paquet dans l’en-tête d’un paquet d’accusé de réception (ACK) qui sera envoyé vers l’émetteur. A la réception de l’ACK, l’émetteur mettra à jour la taille de sa fenêtre de congestion de la manière suivante : cwnd = max (cwnd + H feedback; packetsize), où cwnd est exprimé en octets.

Le mécanisme central d’un routeur XCP est basé sur l’utilisation d’un contrôleur d’efficacité (EC) et d’un contrôleur d’équité (FC) qui réalisent la mise à jour de feedback pendant un intervalle de contrôle équivalent à la moyenne des RTT. L’EC a la responsabilité de maximiser l’utilisation de la bande passante tout en minimisant le nombre de paquets rejetés et le FC de partager les ressources de façon équitable. Il va assigner à feedback une valeur proportionnelle à la bande passante disponible (S), déduite de la différence entre le trafic entrant total et la capacité du lien de sortie. La taille résiduelle Q de la file d’attente est également prise en compte. Dans une deuxième étape, le FC traduit cette valeur feedback globale (qui peut être assimilée à une valeur agrégée de

bande passante disponible positive ou négative) en une valeur feedback par paquet (qui sera ensuite placée dans l’en-tête de chaque paquet de données) en suivant des règles d’équité par flux similaires aux règles AIMD6 de TCP. Il faut noter qu’il n’y a pas d’états par flux conservés par le routeur XCP pour exécuter toutes ces opérations.

En effet, comme les paquets de données d’un flux donné portent dans leur en-tête la valeur actuelle de la fenêtre de congestion et le RTT, il est possible de calculer pour chaque flux le nombre de paquets envoyés par fenêtre de congestion afin d’assigner la bande passante disponible de manière proportionnelle. XCP est donc capable d’atteindre très rapidement le débit optimal et de réagir aussi rapidement aux variations de bande passante. Cependant, dans le cas de cohabitation avec TCP, XCP récupérera moins de bande passante à cause du contrôle strict qu’il impose sur le taux de pertes.

Observations

Le graphe représente la taille de la fenêtre de congestion des trois sources en fonction du temps. La première source commence l’envoi des paquets dés le début de la simulation, alors la taille de la fenêtre de congestion augmente considérablement jusqu’à 115 000 octets car le contrôleur d’efficacité EC du protocole XCP cherche à utiliser le maximum de la bande passante puis cherche à l’optimiser vers 100 000 Octets pour éviter la congestion et le rejet des paquets en réduisant le flux. A sixième seconde la deuxième source débute son envoi de paquets, on remarque que la taille de la fenêtre de congestion de la deuxième source augmente ainsi que celle de la première source diminue et les deux se stabilisent au niveau de 50 000 Octets ; cela signifie que le contrôleur d’équité partage la bande passante entre les deux sources équitablement, sachant que EC maximise toujours l’utilisation de la bande passante et minimise le rejet des paquets. La troisième source envoie les paquets à la 12 sec et on remarque le même comportement qu’à la sixième seconde la taille de fenêtre de congestion des deux premières sources se réduit et la troisième augmente jusqu’à 33 000 Octets, car le partage de la ressource (bande passante) est équitable.

Conclusion

Quelle que soit la politique de qualité de service utilisée qui est définie par ces paramètres : la bande passante, le délai, la gigue et le taux de perte. C’est au niveau des files d’attente des routeurs que cette politique est mise en oeuvre, pour cela nous avons simulé les différentes files d’attente et étudié leurs résultats. Nous avons constaté qu’elles se caractérisent par deux gestions actives et passives, la gestion passive s’occupe de savoir que s’il reste de la place dans la fille d’attente avant d’accepter un paquet ou de le rejeter, elle est illustré par DROP TAIL par contre la gestion active prévient la congestion et réduise le flux avant la saturation de la file d’attente en rejetant des paquets telle que RED. Après la modélisation du système M/M/1 et la variation de ses paramètres, on conclue que le système est stable quand le taux d’arrivé λ est inférieur ou égale au taux de service μ. Finalement, la simulation du protocole de contrôle congestion XCP induit que c’est une solution à la congestion, car XCP informe en temps actuel l’émetteur du taux de remplissage de la fenêtre de congestion et adapte son flux en fonction de celle ci.

Conclusion générale

En modélisation de flux dans les réseaux, nous avons simulé avec NS (Network Simulator) différentes files d’attente. FIFO connue aussi par ‘Drop TAIL’ qui serve le premier paquet arrivée et rejette le reste des paquets une fois la file saturée, SFQ est plus équitable par rapport a Drop Tail car elle divise le flux arrivé en plusieurs partie avec la même priorité et RED gère la file activement, elle prévient contre la congestion en rejetant quelques paquets avant la saturation de la file pour que les sources réduisent leur flux, nous avons réalisé aussi une étude approfondie sur les systèmes M/M/1 et M/M/1/K est un système aux arrivées Markoviennes (M), à temps de traitement Markovien / Exponentiel (M), composé d’une file d’attente FIFO de taille illimitée ou limité K et d’un seul serveur (1) et en fin un protocole de contrôle de congestion XCP qui offre l’efficacité, la stabilité et l’équité en réseau grâce aux deux contrôleurs EC et FC. L’objectif de la simulation est d’étudier leurs performances et évaluer leurs résultats. Ce qui nous a permis de comprendre les causes principales du phénomène de congestion, de le gérer avec les files d’attente et d’utiliser une solution à la congestion tel que le protocole XCP. Puis comprendre le fonctionnement des systèmes de files d’attente et de constater leur utilité en réseau. Il existe d’autres types de files d’attente à titre d’exemple CBQ (Class Based Queuing) permet d’allouer une certaine proportion de bande passante pour une classe de trafic donnée et DRR Deficit Round Robin. Les files d’attente permettent de gérer la congestion en minimisant la perte des paquets qui évite la retransmission ce qui économise la bande passante et réduit la latence qui se définie comme la variation des délais d’acheminement ce qui enrichit la couche réseau en assurant une bonne qualité de service.

Table des matières

Introduction générale
Chapitre I Généralité
I- Introduction
II- Les types de réseaux et topologies
1- Les types de réseaux
1.1- Les LAN
1.2- Les MAN
1.3- Les WAN
2- Les topologies
2.1- La topologie en bus
2.2- La topologie en étoile
2.3- La topologie en anneau
III- Simulation
IV- Network Simulator NS
V- Conclusion
Chapitre II Gestion des files d’attente : Etat de l’art
I- Introduction
II- Les files d’attente
1- Définition
2- Théories des files d’attente [13]
2.1- Processus des Arrivées
2.2- Processus des Services
2.3- Chaînes de Markov
2.4- La Notation de Kendall
2.5- File d’attente M/M/1 [2]
3- Congestion
4- Contrôle de congestion
4.1- Explicit Congestion Notification ECN
4.2- eXplicit Congestion control Protocol XCP
III- Conclusion
Chapitre III Modélisation et évaluation des performances
I- Introduction
II- Simulations des files d’attente
1- FIFO First In First Out
2- SFQ Stochastic Fairness Queueing
3- RED Random Early Detection
III- Etude et évaluation des résultats
1- Les graphes de Drop Tail
1.1- Paquets perdus
1.2- Bande passante
2- Les graphes de SFQ
2.1- Paquets perdus
2.2- Bande passante
3- Les graphes de RED
3.1- Paquets perdus
3.2- Bande passante
IV- Simulation d’un système M/M/1
1- La démarche
2- Etude approfondie du M/M/1
V- Simulation du système M/M/1/K
1- Etude de M/M/1/K
VI- Simulation du Protocol de contrôle de congestion XCP
1- Démarche
VII- Conclusion
Conclusion générale
Références bibliographiques
Annexe A
Annexe B
Résumé

Télécharger le rapport complet