Congestion Control In High Speed Networks (in French)

Université Abderrahmane Mira de Béjaïa LAboratoire de Modélisation et d’Optimisation de Systèmes LAMOS

École Doctorale d’Informatique Réseaux et Systèmes Distribués ReSyD

Soutenance Publique de

Magistère

THEME

Présenté par:

Nadir BOUCHAMA

Directeur de Thèse:

Co-Directeur de Thèse:

Pr D. AISSANI

M.C Natalia DJELLAB

© Nadir BOUCHAMA, Décembre 2005

1

Plan de l’exposé  Introduction  Panorama des réseaux à haut débit Rappels, Commutation de circuits vs commutation de paquets, RNIS-LB, QoS, Frame Relay, ATM, MPLS

 Technologie ATM (Asynchronous Transfer Mode)  Qualité de Service dans ATM  Contrôle de Congestion dans les réseaux haut débit Définition, Principe du contrôle de congestion, Propriétés fondamentales, taxonomie,

 Evaluation de Performances des Réseaux ATM Méthodes analytiques, mesures, simulation, simulation à évènements discrets

 Etude de deux Algorithmes de Contrôle d’admission Modèle M/D/1 , Modèle N.D/D/1

 Simulation : Résultats & Discussions  Conclusion Générale & perspectives

© Nadir BOUCHAMA, Décembre 2005

2

Introduction • De l’importance des réseaux • Taxonomie des réseaux  Selon la distance : LAN, MAN, WAN Selon la topologie : Etoile, Bus, Anneau, etc

(a) Topologie en bus

(b) Topologie en étoile

(c) Topologie en anneau

Selon le type de commutation: Commutation de circuits

commutation de paquets

(RTC)

(Internet, X.25) © Nadir BOUCHAMA, Décembre 2005

3

Commutation de Circuits vs Commutation de paquets Commutation de circuits

Commutation de paquets Exemple : X.25 et Internet

Exemple : Réseau Téléphonique Commuté inventé en 1878

© Nadir BOUCHAMA, Décembre 2005

4

Multiplexage Statistique versus multiplexage déterministe Les réseaux téléphoniques sont utilisés pour le transfert de la voix

Débit

7

B=5

Multiplexage déterministe (allouer à chaque connexion son débit maximum)  Sous utilisation du réseau

Somme (S) 3

Les réseaux de communication de données sont utilisés pour le transfert de données (trafic sporadique) Multiplexage statistique  Bonne utilisation des ressources du réseau  Possibilité de congestion

© Nadir BOUCHAMA, Décembre 2005

Connexion 3 2.5 Connexion 2 3

Connexion 1

Temps

5

Principe de Commutation Paquet arrivant

Commutateur

Paquets sortants

File d’attente Processeur Paquet sortant

Paquet arrivant Lien d’entrée

Lien de sortie

© Nadir BOUCHAMA, Décembre 2005

6

Réseaux à Haut Débit (motivation)  Besoins de plus en plus accru en Applications Multimédias telles que la VoD (Video on Demand) et l’AoD (Audio on Demand), la vidéoconférence, etc  Ces applications sont très gourmandes en bande passante;  Minimiser les coûts de câblage (avoir sur une même interface un seul accès à plusieurs services);  Convergence des opérateurs de télécommunications et des constructeurs du matériel informatique  Naissance du RNIS-BE (Réseau Numérique à Intégration de Services Bande Etroite)

RNIS de première génération

© Nadir BOUCHAMA, Décembre 2005

7

RNIS-LB 

Le RNIS-BE offre une interface d’accès unique à des réseaux à commutation de circuits et de paquets mais ces deux réseaux restent disjoints



Pourquoi ne pas remplacer ces deux techniques de commutation par un eseule et obtenir réseau qui aura les avantages suivants:



Une souplesse d’adaptation aux changements et aux nouveaux besoins



Une efficacité dans l’utilisation des ressources disponibles



Un coût plus faible d’investissement, de fabrication, d’opération et de maintenance

 Naissance du Réseau Numérique à Intégration de Services Large Bande © Nadir BOUCHAMA, Décembre 2005

8

Standardisation  Mode asynchrone (ATM) Mode de transfert asynchrone  Unité de données : cellules (compromis entre commutation de circuits et commutation de paquets)  Taille fixe de la cellule : 53 octets

© Nadir BOUCHAMA, Décembre 2005

9

Qualité de Service (QoS) dans ATM Une définition officielle de la qualité de service (QoS) est définie également dans la recommandation E.800 de l’UIT [25] : La qualité de service correspond à l’effet général de la performance d’un service quidétermine le dégré de satisfaction d’un utilisateur de service. Paramètres Délais de bout en bout Gigue: variation des délais Disponibilité Taux de perte Bande passante

Pour ATM, LA QoS est définie en terme de paramètres de Qos qui sont les suivants: © Nadir BOUCHAMA, Décembre 2005

10

Paramètres de QoS dans ATM

© Nadir BOUCHAMA, Décembre 2005

11

Classes de service dans ATM

© Nadir BOUCHAMA, Décembre 2005

12

Congestion dans ATM  La commutation de cellules  Si ATM a hérité de la commutation de paquets sa souplesse, elle a aussi hérité de celle-ci sa vulnérabilité au phénomène de congestion

© Nadir BOUCHAMA, Décembre 2005

13

Congestion: le phénomène Définition : • Etymologiquement, Congestion (en latin congestio) = accumulation • On peut définir la congestion comme un état de certains éléments du réseau dans lequel le réseau n’est plus capable de répondre aux objectifs de performance fixés.

80 Kb/s 100 Kb/s

50Kb/s

50 Kb/s

100 Kb/s

50 Kb/s

© Nadir BOUCHAMA, Décembre 2005

14

Conséquence de la congestion La congestion est indésirable dans un réseau car elle cause: Des délais de bout en bout très longs; Des pertes de paquets et par conséquence des retransmissions inutiles; Un Affaiblissement du débit et des performances en général

Nécessité d’un contrôle de congestion

© Nadir BOUCHAMA, Décembre 2005

15

Contrôle de Congestion vs Contrôle de flux Transport Réseau Liaison Physique

Transport Réseau Liaison Physique

x u l f comme étant : Le contrôle de trafic est défini e "l’ensemble des actionsle quidpeuvent être prises par ô toute r t le réseau pour empêcher n congestion Co

Transport Réseau Liaison Physique

Transport e Réseau d e correspond aux actions qui Liaison l Le contrôle de congestion ô nle réseau pour tr par o peuvent êtrenprises i Physique t o s e l’étendue, et C l’intensité, minimiser g la durée conde la congestion On voit le réseau comme étant une boîte blanche

© Nadir BOUCHAMA, Décembre 2005

16

Effondrement de Congestion On a commencé à s’intéresser au problème de congestion dans Internet dès les années 1980. Effondrement de congestion des performance de TCP sous la version BSD UNIX de l’université de Berkley Raison: aucun mécanisme de contrôle de congestion n’a été inclus dans le protocole TCP Deux solutions ont été proposées alors: Congestion Control and Avoidance dans TCP (Van Jacobson et Karels) (Notification implicite) DECBIT : Jain et Ramakrishnan (Notification explicite)

© Nadir BOUCHAMA, Décembre 2005

17

Taxonomie des méthodes de contrôle d’admission  Selon le stade d’intervention Méthodes préventives: Méthodes réactives: Méthodes hybrides  Selon la boucle utilisée Boucle fermée : boucle ouverte  Selon la couche OSI Liaison, transport, réseau  Selon la notification de congestion Implicite explicite  Selon l’intervention De bout en bout, saut par saut

© Nadir BOUCHAMA, Décembre 2005

18

Mythes à propos de la congestion Dans: R. Jain. Congestion Control in Computer Networks : Issues and Trends. IEEE Network Magazine, pages 24–30, Mai 1990. L’auteur montre quelques fausses idées à propos des solutions que l’on peut apporter au problème de congestion: La congestion est due au manque de mémoire dans les commutateurs  Le problème sera réglé quand on aura assez de mémoire La congestion est due à la lenteur des processeurs  Le problème sera réglé quand des processeurs à haute vitesse seront inventés La congestion est due aux liaisons à faible débit  Le problème sera réglé avec l’avènement de la fibre optique et des liaisons à haut débit © Nadir BOUCHAMA, Décembre 2005

19

Malheureusement John Nagle nous montre dans le RFC970 :

1 Go 2 Go

On packet Switches with Infinite Storage (1985) 1.2 Go

Que: Buffers de taille infinie Congestion plus grave

Augmenter la taille des buffers ne règlera pas le problème de congestion

Augmenter la bande passante de ne règlera pas le problème de congestion

© Nadir BOUCHAMA, Décembre 2005

Augmenter la vitesse des processeurs ne règlera pas le problème de congestion 20

La solution ? • Les technologies à haut débit n’ont fait qu’aggraver le problème de congestion • Le renforcement d’un seul élément d’un système ne permet pas d’améliorer fortement ses performances simple déplacement du problème • Le vrai problème est la différence de performances •De ce fait, la congestion persistera aussi longtemps que cette différence demeure

La solution alors…. Il faut pas trop compter sur les technologies matérielles mais il faut investir dans la conception de nouveaux protocoles. Il faut revoir la philosophie des protocoles classiques et les adapter aux caractéristiques des réseaux haut débit

© Nadir BOUCHAMA, Décembre 2005

21

Pire encore … La congestion est plus ardue à résoudre dans les réseaux à haut débit: Produit Bande passante- délai très grand; Qualité de Service des applications Application temps réel Hétérogénéité des services

© Nadir BOUCHAMA, Décembre 2005

22

Contrôle de Congestion dans ATM Contrairement à Internet qui utilise un contrôle de congestion réactif, ATM préconise un contrôle de congestion préventif

Contrôle d’admission (Accepter ou rejeter une connexion)  Contrôle des paramètres d’utilisateur (Vérifier la conformité du trafic)  Canalisation de trafic (Trafic shaping) (Régulariser le trafic et supprimer les pics éventuels)  Rejet de paquets (Minimiser l’effet de la congestion)

© Nadir BOUCHAMA, Décembre 2005

23

Evaluation de performances On distingue trois classes principales:  Mesures - Utilisation de moniteurs logiciels et moniteurs matériels - Nécessitent que le système à étudier soit disponible pour être étudié  Méthodes analytiques Relations fonctionnelles entre les paramètres d’entrée du système et le indices de performances Exemples: Files d’attente  Simulation Utilisation de l’outil informatique - Paradigme le plus connu : Simulation à événements discrets

© Nadir BOUCHAMA, Décembre 2005

24

Files d’Attente Départ

Clients

File d’attente

Serveur

Une file d’attente peut être décrite à l’aide de la notation de Kendall:

A/B/n/K/N A : Loi des arrivées (Poisson, Déterministe, etc) B : Durée de service (exponentielle, Déterministe, etc) n: Nombre de serveurs K: Taille de la file N : Politique de service (FIFO, RANDOM,LIFO,etc) © Nadir BOUCHAMA, Décembre 2005

25

Exemple : File d’attente M/D/1 M : loi des arrivées est la loi de Poisson

Où : lambda : intensité du trafic D: Temps de service déterministe

1 : nombre de serveurs égal à 1 Taille de la file infinie Politique de service : FIFO

© Nadir BOUCHAMA, Décembre 2005

26

Simulation à événements discrets Arrivée du client #1 + entrée en service Arrivée du client #2 + mise en file Départ du client #1

Axe du temps 1

2

1 Durée entre 2 arrivées

© Nadir BOUCHAMA, Décembre 2005

Évènements

27

Simulation d’une file M/D/1 Fixer la paramètre d’entrée : Temps de simulation, taux d’arrivée lambda et taux de service mu Générer un v.a selon une loi normale (plusieurs générateurs aléatoires existent dans la litérature rand())  Générer les événements: (méthode d’inversion)

© Nadir BOUCHAMA, Décembre 2005

28

Exemple de simulation (Évolution de la taille de la file d’attente) Temps de service = 2.83 milli seconde Lambda = 0.33

Mu = 0.35 Temps Simulation = 1000

© Nadir BOUCHAMA, Décembre 2005

29

Contrôle d’admission

© Nadir BOUCHAMA, Décembre 2005

30

Algorithme basé sur un modèle M/D/1 (Call Level) Fonction CAC

Adéquat pour un trafic VBR (vidéo compressée) Chaque connexion i est caractérisée par

O NO K

CAC

* son débit crête Hi * son taux de perte CLP i Capacité (bande passante) du lien de sortie égale à C (généralement 155.52 Mo/s)

x

hi CLPi

Une connexion est admise si on a: CHARGE ADIMISSIBLE

© Nadir BOUCHAMA, Décembre 2005

? 31

Algorithme basé sur un modèle M/D/1 (Cell Level) Problème : Comment estimer la charge admissible ?

Méthode analytique exacte Méthode analytique Approximative Simulation

© Nadir BOUCHAMA, Décembre 2005

32

Algorithme basé sur un modèle N.D/D/1 Algorithme basé sur un modèle N.D/D/1  Adéquat pour un trafic CBR (exemple Voix et vidéo non compressée) Temps de service déterministe Un seul serveur N sources Paramètres d’une connexion:

© Nadir BOUCHAMA, Décembre 2005

33

Algorithme basé sur un modèle N.D/D/1

© Nadir BOUCHAMA, Décembre 2005

34

Résultats Obtenus

© Nadir BOUCHAMA, Décembre 2005

35

Conclusion Générale & Perspectives  Dans un réseau à intégration de services, un mécanisme de contrôle de congestion préventif doit être inclus  Le contrôle réactif n’est pas exclu mais est utilisé pour minimiser l’intensité, la durée, et l’étendue de la congestion;  Cependant, TCP doit être modifié pour s’adapter aux réseaux haut débit;  Le contrôle d’admission est l’exemple le plus simple du contrôle préventif;  Dans notre travail, nous avons fait une étude comparative entre deux algorithmes de contrôle d’admission  Nous avons utilisé la simulation par évènements discrets pour établir des tables de recherche qui seront utilisées par la fonction CAC  Comme perspectives, il serait intéressant d’étendre notre étude pour inclure les mécanismes d’équilibrage de charge.  Il serait aussi intéressant d’étudier de façon plus détaillée les améliorations apportées au protocole TCP dans les réseaux à liaisons satellitaires.

© Nadir BOUCHAMA, Décembre 2005

36