Simulation d’un système M/M/1

Simulation d’un système M/M/1

De nos jours, les réseaux véhiculent simultanément un nombre important de données hétérogènes. Ainsi, lors de la circulation de plusieurs flux, les caractéristiques du réseau engendrent des aspects négatifs sur la transmission de ces informations. Ces aspects peuvent se traduire par des délais d’acheminement importants, une incapacité d’obtenir une bande passante suffisante ou encore par la perte des paquets.

Pour remédier à ces problèmes, des mécanismes de gestion de file d’attente sont implémentés dans les routeurs, ce qui permet d’administrer les paquets plus ou moins d’une manière équitable et apporter des solutions au problème de congestion qui se produit lorsque le flux dans le réseau est supérieur aux capacités des ressources disponibles sur ce même réseau.

Dans le cadre de notre projet de modélisation de flux dans un réseau qui est la conception d’un modèle qui représente la réalité, nous allons simuler plusieurs types de files d’attente et cela afin d’étudier et évaluer les modalités de leurs fonctionnements, en utilisant le simulateur de réseau NS2 .

Le réseau est un système de communication qui relie des ordinateurs et des équipements informatiques dans un espace géographique défini. Il sert à la transmission des données (fichiers, message, etc.), au partage de données (logiciel et base de données) et au partage de matériels (imprimantes, modem, etc.).

Les types de réseaux et topologies

Les types de réseaux

Un réseau informatique est un ensemble de machines connectées entre elles qui échangent des informations, il permet la communication entre ordinateurs, le partage de fichiers, d’imprimantes et différents services. [14] On distingue différents types de réseaux selon leur taille, leur vitesse de transfert et leur étendue. Généralement il y a trois catégories de réseaux :
– LAN (local area network)
– MAN (metropolitan area network)
– WAN (wide area)
On peut distinguer deux modes de fonctionnement en réseau :
– Dans un environnement d' »égal à égal » (en anglais peer to peer), dans lequel il n’y a pas d’ordinateur central et chaque ordinateur a un rôle similaire.
– Dans un environnement « client/serveur », dans lequel un ordinateur central fournit des services réseau aux utilisateurs.

Les LAN
LAN signifie Local Area Network (en français Réseau Local). Il s’agit d’un ensemble d’ordinateurs reliés entre eux dans une petite aire géographique par un réseau, souvent à l’aide d’une même technologie (la plus répandue étant Ethernet).

Les MAN
Les MAN (Metropolitan Area Network) interconnectent plusieurs LAN géographiquement proches (au maximum quelques dizaines de km) à des débits importants. Ainsi un MAN permet à deux nœuds distants de communiquer comme si ils faisaient partie d’un même réseau local. Un MAN est formé de commutateurs ou de routeurs interconnectés par des liens hauts débits (en général en fibre optique).

Les WAN
Un WAN (Wide Area Network ou réseau étendu) interconnecte plusieurs LANs à travers de grandes distances géographiques. Les débits disponibles sur un WAN résultent d’un arbitrage avec le coût des liaisons (qui augmente avec la distance) et peuvent être faibles. Les WAN fonctionnent grâce à des routeurs qui permettent de « choisir » le trajet le plus approprié pour atteindre un nœuds du réseau. Le plus connu des WAN est Internet.

Les topologies

Les dispositifs matériels mis en œuvre ne sont pas suffisants à l’utilisation du réseau local. En effet, il est nécessaire de définir une méthode d’accès standard entre les ordinateurs, afin que ceux-ci connaissent la manière de laquelle les ordinateurs échangent les informations, notamment dans le cas où plus de deux ordinateurs se partagent le support physique. Cette méthode d’accès est appelée topologie logique. La topologie logique est réalisée par un protocole d’accès. Les protocoles d’accès les plus utilisés sont : Ethernet et Token ring.  La façon de laquelle les ordinateurs sont interconnectés physiquement est appelée topologie physique. Les topologies physiques basiques sont :

– La topologie en bus
Une topologie en bus désigne le fait que lors de l’émission de données sur le bus par une station de travail, l’ensemble des stations de travail connectées sur le bus la reçoivent. Seule la station de travail à qui le message est destiné la recopie.

– La topologie en étoile
L’ensemble des stations de travail est connecté à un Hub qui examine le contenu du message, qui le régénère, et qui le transmet qu’à son destinataire. C’est en réalité un réseau de « n » liaisons point par point, car il établit un circuit entre une paire d’utilisateurs.

– La topologie en anneau
L’information circule le long de l’anneau dans un seul sens. A chaque passage d’un message au niveau d’une station de travail, celle-ci regarde si le message lui est destiné, si c’est le cas elle le recopie.

Simulation

La simulation est l’un des outils permettant de simuler des phénomènes réels. Les objectifs principaux de la simulation sont l’évaluation des protocoles, d’architecture des réseaux et prévoir leur fonctionnement. Il existe une multitude de simulateurs tel que : OPNET, QNAP, SimuLog, OMNET++ et NS. Parmi ces simulateurs nous utilisons NS car c’est un outil libre, plus utilisé et que nous avons déjà apprit à travailler avec. Le logiciel NS-2 et son outil de visualisation NAM sont particulièrement adaptés à l’étude de réseaux complexes (filaires, sans fils) mettant en œuvre de nombreuses files d’attente, procédés de routage et types de trafics.

Intérêt de la simulation
• Quand on ne peut pas facilement observer les états du système,
• Quand on désire analyser l’enchaînement des événements dans le système, ainsi que les relations de causes à effets,
• Quand on désire valider une solution analytique,
• Quand la complexité des interactions dans le système est telle qu’elle ne peut être étudiée qu’au travers de simulations,
• Quand on désire visualiser les états d’un système,
• Quand on veut tester différentes optimisations pour améliorer un système déjà existant.

Avantages de la simulation
• Observations des états du système,
• Etudes des points de fonctionnement d’un système,
• Etudes de systèmes à échelle de temps variable,
• Etudes de l’impact des variables sur les performances du système,
• Etude d’un système sans les contraintes matérielles.

Inconvénients
• La conception de modèles peut nécessiter des compétences spéciales,
• Une autre forme d’analyse plus proche de la réalité est peut être nécessaire,
• Résultats difficilement interprétables,
• Résultats pas forcément généralisables,
• Résultats sont fonction des entrées du système.

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:
– Application : Web, ftp, Telnet, générateur de trafic (CBR, …).
– Transport : TCP, UDP, RTP, SRM.
– Routage : Statique, dynamique (vecteur distance) et routage multipoint (DVMRP, PIM).
– Gestion de file d’attente : RED, DropTail, Token bucket.
– Discipline de service : CBQ, SFQ, DRR, Fair Queuing.
– Système de transmission : CSMA/CD, CSMA/CA, lien point à point.
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 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.

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
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

Télécharger le rapport complet