Routage Avec Qos Dans L'internet (qos Routing In The Internet)

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Université Abderrahmane Mira de Béjaia Ecole Doctorale d’Informatique

Module : Réseaux et communication de données

Protocoles de Routage avec Qualité de Service (QoS) dans l’Internet (QoS Routing Protocols in the Internet)

BOUCHAMA Nadir & YAHIAOUI Saïd

Promotion 2003 - 2004

SOMMAIRE RESUME ............................................................................................................................................. 4 INTRODUCTION............................................................................................................................... 5 I.

LIMITES DES PROTOCOLES DE ROUTAGE « AU MIEUX » ..................................... 5 1. 2. 3.

II.

ASYMETRIE DU ROUTAGE ........................................................................................................................................6 PAS D’EQUILIBRAGE DE CHARGE .............................................................................................................................6 NON PRISE EN CHARGE DE LA QOS..........................................................................................................................6

QUALITE DE SERVICE DANS LE RESEAU INTERNET ............................................. 6

1. 2. 3. 4. 5. 6.

NOTION DE QUALITE DE SERVICE ...........................................................................................................................6 PARAMETRES DE LA QOS ........................................................................................................................................7 LE CONCEPT DE FLUX ..............................................................................................................................................8 CONCEPT D’AGREGAT (AGGREGATE) ......................................................................................................................8 ROLE D’UN PROTOCOLE DE ROUTAGE AVEC QOS ....................................................................................................8 ROUTAGE AVEC QUALITE DE SERVICE DANS L’INTERNET .......................................................................................8

III.

LES GROUPES DE TRAVAIL DE IETF.......................................................................... 11

1. 2. 3. 4.

LE MODELE D’INTEGRATION DE SERVICE INTSERV................................................................................................12 LE MODELE DE DIFFERENCIATION DE SERVICE : DIFFSERV ...................................................................................18 LE GROUPE DE TRAVAIL QOSR (QOS ROUTING)....................................................................................................23 LE GROUPE DE TRAVAIL MPLS (MULTI PROTOCOL LABEL SWITCHING) ................................................................24

IV.

ROUTAGE AVEC QOS DANS LES RESEAUX MOBILES .......................................... 27

V.

ALGORITHMES DE ROUTAGE ....................................................................................... 27 1. 2. 3.

VI.

EXEMPLES D’ALGORITHMES DE ROUTAGE AVEC QOS ...........................................................................................27 COMPLEXITE .........................................................................................................................................................28 CARACTERISTIQUES D’UN ALGORITHME DE ROUTAGE AVEC QOS.........................................................................28

PROBLEMES OUVERTS DANS LE ROUTAGE AVEC QOS...................................... 29

CONCLUSION ................................................................................................................................. 30 GLOSSAIRE ..................................................................................................................................... 31 REFERENCES BIBLIOGRAPHIQUES ....................................................................................... 32

BOUCHAMA Nadir et YAHIAOUI Saïd

2

RESYD 2004

LISTE DES FIGURES FIGURE 1 : EXEMPLE D’APPLICATIONS COMMUNES ET LEURS SENSIBILITES AUX EXIGENCES DE LA QUALITE DE SERVICE........................................................................................................................... 10 FIGURE 2 : MODELE DE REFERENCE D’UN ROUTEUR INTSERV ............................................................. 12 FIGURE 3 : MECANISME DE SEAU A JETONS........................................................................................... 14 FIGURE 4 : MESSAGES PATH ET RESV POUR LA RESERVATION DE RESSOURCES................................ 16 FIGURE 5 : EMPLACEMENT DU DS (VS. DSCP) DANS L’EN-TETE IPV4................................................. 18 FIGURE 6 : EMPLACEMENT DU DS (VS. DSCP) DANS L’EN-TETE IPV6................................................. 19 FIGURE 7 : FORMAT DU CHAMP DS. ..................................................................................................... 19 FIGURE 8 : ARCHITECTURE D’UNE REGION DIFFSERV .......................................................................... 19 FIGURE 9 : PRINCIPE DE FONCTIONNEMENT D’UN ROUTEUR FRONTIERE .............................................. 21 FIGURE 10 : ARCHITECTURE D’UN ROUTEUR INTERNE. ........................................................................ 21 FIGURE 11 : ARCHITECTURE D’UN ROUTEUR INTERNE ......................................................................... 26 FIGURE 12 : COMPLEXITES AU PIRE DES CAS DES ALGORITHMES DE ROUTAGE AVEC QOS. .................. 28

BOUCHAMA Nadir et YAHIAOUI Saïd

3

RESYD 2004

Protocoles de routage avec QoS dans l’Internet

Résumé Le réseau Internet est un réseau de commutation de paquets en mode non connecté offrant des services « au mieux » et donc non garantis. Cette absence de garantie ne permet pas la mise en fonctionnement opérationnel d’applications demandant un contrôle sévère des ressources utilisées, et présente donc un obstacle majeur pour le trafic multimédia qui devient de plus en plus sollicité. Beaucoup d’attention a été donnée ces dernières années au développement d’algorithmes de routage avec Qualité de Service. Au sein de l’IETF, plusieurs équipes de travail qui coopèrent afin d’aboutir à de tels protocoles. L’objectif de ce rapport est d’étudier les protocoles de routage avec Qualité de Service (QoS routing) dans l’Internet et les différents modèles proposés par les groupes de travail de l’IETF. Nous y expliciterons deux concepts clés : le routage et la Qualité de Service (QoS) .Par la suite, nous présenterons quelques protocoles de routage avec Qualité de Service conçus à cet effet. Mot clés : Routage, Qualité de Service, IntServ, RSVP, DiffServ, QoSR, MPLS.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 4

Protocoles de routage avec QoS dans l’Internet

INTRODUCTION Le besoin accru en matière d’utilisation d’applications multimédias sur Internet a déclenché beaucoup de recherches sur la façon de satisfaire les besoins en Qualité de Service (QoS) pour ces applications : exigences concernant la bande passante, le délai, la gigue, etc. Chaque application peut avoir des besoins spécifiques. Par conséquent, il est difficile de définir globalement des niveaux de service. Par exemple, garantir une borne sur le délai de transmission des paquets peut être profitable aux applications de téléphonie ; garantir un débit peut être nécessaire pour les applications de vidéo à la demande (VOD), etc [CHA 03]. Dans cette dynamique, la communauté des chercheurs s’est consacrée ses derniers temps à une étude sérieuse du problème de routage avec QoS, ce qui a donné naissance à plusieurs protocoles de routage supportant la QoS (QoS routing protocols).

I.

Limites des protocoles de routage « au mieux » Le réseau Internet est un réseau de commutation de paquets en mode sans connexion offrant

des services au mieux (Best Effort). Il a été développé à une époque où la bande passante était rare, la stratégie étant d'obtenir une occupation maximum des liens quitte à introduire des délais supplémentaires dans la transmission des données. Le principe du « Best Effort », qui est une politique de gestion de la pénurie, se traduit par une simplification à l'extrême des équipements d'interconnexion. Quand la mémoire d'un routeur est saturée, les paquets entrants sont rejetés [TOU 99]. L’absence de garantie caractérisant ce principe ne permet pas de répondre aux exigences en Qualité de Service des applications multimédias et temps réel qui sont plutôt gourmandes en bande passante et sensibles aux variations des délais interpaquets, ainsi qu’aux pertes de paquets. D’autre part, les protocoles de routage tels que OSPF et RIP sont basés sur le choix du plus court chemin calculé suivant une métrique unique arbitraire (poids administratif ou nombre de sauts). Par conséquent, Ils ne permettent pas d'utiliser d'autres chemins qui pourraient convenir pour transporter du trafic moins prioritaire (courrier électronique). Les manques caractérisant le routage « Best Effort» peuvent être résumés dans ce qui suit [MEL 01] :

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 5

Protocoles de routage avec QoS dans l’Internet

1. Asymétrie du routage Le trafic sur l’Internet et les réseaux est bidirectionnel : l’émetteur possède un chemin pour rejoindre le destinataire, qui en retour contient un chemin pour rejoindre l’émetteur. En raison des différentes politiques de routage, il est fréquent que le chemin de retour soit complètement différent du chemin aller. Cette asymétrie peut poser un problème dans la mesure où les chemins empruntés à l’aller et au retour ne possèdent pas les mêmes caractéristiques de QoS (notamment en ce qui concerne le temps de traversée du réseau).

2. Pas d’équilibrage de charge Autre inconvénient des protocoles de routage : l’incapacité d’équilibrage de charge sur les liens réseaux.

3. Non prise en charge de la QoS Les protocoles de routage « Best Effort » ne permettent pas de tenir compte de la qualité de service demandée pour un datagramme, car le choix des routes ne fait pas intervenir de métriques liées à la QoS. Pour pallier aux lacunes du service « Best Effort », la communauté Internet est mobilisée pour essayer d’introduire la notion de Qualité de Service. Ainsi, sont apparus des protocoles de routage supportant la QoS. Ces derniers font l’objet de recherche de plusieurs équipes de travail au sein de l’IETF (Internet Engineering Task Force).

II. Qualité de Service dans le réseau Internet 1. Notion de Qualité de Service Dans un premier temps, il convient de préciser ce que recouvre le terme «Qualité de Service » (en anglais : Quality of Service). Dans [MEL 01], la Qualité de Service est définie comme étant « la capacité de transporter efficacement le flux de données d’une application tout en satisfaisant les exigences (contraintes) dictées par l’utilisateur (ou l’application) ». 1.1. Définition de l’ISO et ITU-T [ISO/CEI 13236 - X.641 ; Décembre 1997] « C’est un ensemble d’exigences de qualité sur le comportement collectif d’un ou de plusieurs objets » [MAM 03]. 1.2. Définition de l’IETF « La Qualité de Service désigne la manière dont le service de livraison de paquets est fourni et qui est décrite par des paramètres tels que la bande passante, le délai de remise de paquet et les taux de perte de paquets » [MAM 03].

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 6

Protocoles de routage avec QoS dans l’Internet 1.3. Définition du CCITT [recommandation E.800] « La Qualité de Service correspond à l’effet général de la performance d’un service qui détermine le degré de satisfaction d’un utilisateur de service ».

2. Paramètres de la QoS Les principaux paramètres connus de la Qualité de Service sont [MEL 01]: 2.1. Disponibilité Elle est définie comme étant le rapport entre le temps de bon fonctionnement des services et le temps total d’ouverture du service. C’est la forme la plus évidente de QoS puisqu’elle établi la possibilité d’utiliser le réseau. 2.2. Bande passante C’est la capacité de transmission d’une liaison du réseau mesurée en bit par seconde. La bande passante disponible sur un chemin entre une source et une destination correspond à la plus petite capacité disponible sur ces liens. La bande passante disponible sur un lien dépend de ses caractéristiques techniques et du nombre de flots de données. 2.3. Latence (delay) La latence correspond au temps que requière un paquet pour traverser le réseau d’un point d’entrée a un point de sortie. Elle dépend des facteurs suivants : 1. Type du media de transmission ; 2. Nombre d’équipements réseau traversés ; 3. La taille des paquets (temps de sérialisation). 2.4. Gigue La gigue est définie comme étant la variation des délais d’acheminement (latence) des paquets sur le réseau. Ce paramètre est particulièrement sensible pour les applications multimédia temps réel qui requièrent un délai inter paquets relativement stable. Elle dépend principalement de : -

type et volume du trafic sur le réseau ;

-

type et nombre d’équipement réseau.

2.5. Taux de perte C’est le rapport du nombre d’octets émis et le nombre d’octets reçus. Il s’agit par conséquent de la mesure de la capacité utile de transmission.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 7

Protocoles de routage avec QoS dans l’Internet

3. Le concept de flux Un flux est un stream individuel et unidirectionnel de données entre deux applications identifiées par 5 paramètres [MEL 01] : -

le protocole de transport ;

-

l’adresse source ;

-

le numéro de port source ;

-

l’adresse destination ;

-

le numéro de port destination.

4. Concept d’agrégat (aggregate) [MEL 01] Un agrégat est la combinaison de deux ou plusieurs flux. Généralement, les flux à combiner possèdent des éléments communs : il pourra s’agir d’un des 5 paramètres cités précédemment (le protocole de transport, adresse source, adresse destination, numéro du port source, numéro du port destination), ou encore d’un niveau de priorité. L’agrégat présente l’avantage de minimiser les informations de QoS à véhiculer, ce qui est fort utile sur de grands réseaux comportant des milliers de flux. Ainsi, au lieu d’appliquer une QoS distincte pour chaque type de flux, on mettra en place une QoS par agrégat. Cette agrégation peut être appliquée en tout point du réseau pour traverser des liens multiples, ou bien dans la définition initiale des flux.

5. Rôle d’un protocole de routage avec QoS Pour répondre aux différents besoins en QoS, un protocole de routage avec QoS doit : •

Acheminer un flux le long d'un chemin satisfaisant les demandes en QoS ou bien fournir un mécanisme pour indiquer que le flux n'a pas été admis ;

•

Indiquer les perturbations dues aux changements de topologies ;

•

Satisfaire le service best-effort sans réservation de ressources ;

•

supporter le trafic multicast ;

•

Tenter de diminuer l'overhead induit par la consommation des ressources et le calcul ;

•

Fournir des mécanismes de contrôle d'admission.

6. Routage avec Qualité de Service dans l’Internet 6.1. Motivation Deux raisons essentielles justifient le besoin en Qualité de Service dans l’Internet :

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 8

Protocoles de routage avec QoS dans l’Internet La première raison est le développement rapide ces dernières années de nouvelles technologies dans le domaine des réseaux à haut débit, traitement d’images, et la compression audio/vidéo. Il est alors possible de supporter le trafic multimédia dans les réseaux de communication. La seconde raison est le besoin accru des utilisateurs des réseaux informatiques en matière d’applications multimédia avec un certain niveau de sécurité [ZHA 99]. Cette activité requiert généralement deux entités [VAN 03b] [KUI 02]: le protocole de routage et l’algorithme de routage : •

Le protocole de routage gère la dynamique du processus de routage en capturant l’état du réseau et des ressources disponibles sur celui-ci, et distribuant cette information sur le réseau.

•

L’algorithme de routage utilise cette information pour calculer les chemins et optimiser un certain critère et/ou obéir à des contraintes. En d’autres termes, il s’agit ici de choisir un chemin réalisable (feasible path).

6.2. Définition « Le routage avec Qualité de Service est l’acte de déplacer l’information à travers un réseau à partir d’une source à une destination tout en respectant les exigences en Qualité de Service de façon à apporter une satisfaction à l’utilisateur d’une part et une optimisation des ressources du réseau d’autre part.» [WAN 96]. Une autre définition de ce concept a été proposé par [CHA 03] : «Il s'agit du processus d'établissement et de maintenance de routes optimales (pour la paire communicante comme pour le réseau) satisfaisant un certain critère sur la qualité de la transmission de données ».

Le routage est un aspect important dans l'implémentation de la Qualité de Service, en particulier pour les aspects suivants : - Choix du meilleur chemin ; - Stabilité du réseau ; - Existence de politiques différentes. 6.3. Complexité du routage avec Qualité de Service Relativement, plusieurs articles sont consacrés aux algorithmes de routage avec Qualité de Service, mais très peu traitent les protocoles de routage avec Qualité de Service. Ceci signifie que

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 9

Protocoles de routage avec QoS dans l’Internet l’on trouve plus de difficulté pour définir un protocole de routage avec Qualité de Service que de définir un algorithme de routage avec Qualité de Service [VAN 03b] [ZHA 99]. A cause des diverses exigences en Qualité de Service, le routage avec Qualité de Service est considéré comme étant un problème NP-complet et, par conséquent, ne peut pas être résolu par un algorithme simple et efficace [BET 01] [ALK 03]. D’autre part, malgré sa difficulté de mise en œuvre, le routage avec Qualité de Service est d’une valeur inestimable dans une architecture réseau qui a besoin de satisfaire le trafic et les exigences du service [VAN 03b].

Application E-mail E-mail confidentiel Transfert de données

Transfert de fichiers

Trafic en temps réel

Transaction d’argent Audio sur demande (AOD) Vidéo sur demande (VOD) Téléphonie Visioconférence Visioconférence confidentielle

Perte Haut Haut

Délai Bas Bas

Sensibilité Gigue Bande passante Bas Bas Bas Bas

Haut

Bas

Bas

Bas Moyen Haut

Bas

Haut Bas Bas Bas Bas Bas

Bas Bas Bas Haut Haut Haut

Bas Haut Haut Haut Haut Haut

Bas Moyen Haut Bas Haut Haut

Haut Bas Bas Bas Bas Haut

sécurité Bas Haut

Figure 1 : Exemple d’applications communes et leurs sensibilités aux exigences de la Qualité de Service.

En général, la table ci-dessus (figure 1) montre que les trafics différents peuvent être classifiés comme suit [ALK 03] : •

Trafic sensible au délai : La plupart des applications temps-réel (vidéo, audio et voix) peuvent être classés sous cette

catégorie. Quelques trafics temps-réel sont sensibles aux délais bout en bout aussi bien qu’aux variations de délais (gigue) comme la téléphonie, et la vidéoconférence tandis que d’autres sont intolérantes à la gigue, mais peuvent tolérer les délais de bout en bout comme l’audio et la vidéo sur demande. •

Trafic sensible aux pertes Le transfert de fichiers et l’envoi du courrier électronique peuvent être classifiés sous cette

catégorie. Dans ce type d’applications, aucun bit ne doit être transmis de façon erronée. Si un

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 10

Protocoles de routage avec QoS dans l’Internet paquet est endommagé durant la transmission, il ne sera pas acquitté et, par conséquent, il sera retransmis. •

Trafic sensible à la sécurité Exemples de telles applications sont les transactions d’argent, et les applications

confidentielles. •

Trafic sensible à la bande passante On peut citer par exemple la vidéo sur demande (VOD).

•

Trafic multi-sensible Ce type de trafic est sensible à plusieurs paramètres. Par exemple, un courrier électronique

confidentiel est sensible à la sécurité et à la perte, tandis que la vidéoconférence est sensible au délai et à la sécurité.

6.4 Etapes d’approvisionnement en Qualité de Service Afin de fournir une Qualité de Service dans l’Internet, en utilisant la réservation de ressources et l’ordonnancement, les étapes suivantes doivent être respectées à tour de rôle au niveau de chaque système et composant participant dans l’application de bout en bout [ZHA 99]. 1. Exigences en Qualité de Service : chaque application doit spécifier exactement ses besoins en Qualité de Service et ceci en indiquant quel paramètre doit être maximisé ou minimisé. 2. Contrôle d’admission : quand une application émet son besoin en Qualité de Service, un contrôle d’admission doit vérifier si cette demande peut être satisfaite en prenant en compte les réservations déjà existantes. Si c’est le cas, la meilleure Qualité de Service possible sera offerte et par conséquent, l’application se verra donner une certaine garantie en Qualité de Service. 3. Réservation de ressources : selon la garantie en QoS, les ressources appropriées doivent être réservées pour l’application concernée. 4. Respect de la garantie en QoS : les garanties en QoS doivent être exécutées par un ordonnanceur approprié.

III. Les groupes de travail de IETF Des groupes de travail de l’IETF (Internet Engineering Task Force) se sont penchés sur l’étude de politiques de services visant à classer les flux de données selon les besoins. Tout d’abord, il est apparu le groupe pour le développement du modèle d’intégration de service IntServ

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 11

Protocoles de routage avec QoS dans l’Internet (Integrated Services), puis, un second groupe pour le développement du modèle de différenciation de service DiffServ (Differentiated Services).

1. Le modèle d’intégration de service IntServ Le groupe de travail IntServ a été constitué en 1994, le but était de pouvoir améliorer le réseau Internet et d’en faire un réseau à intégration de service [RFC 1633]. Il a fallu en effet pouvoir différencier l’utilisation de la bande passante disponible entre les flots multimédia et les flots de données. Les besoins requis par chacun de ces types de flots n’étant pas les mêmes, le groupe de l’IntServ a défini un ensemble de classes de services qui, implémentées au sein des routeurs, devraient allouer aux flots une certaine qualité de service, à chaque traversée des routeurs, pour les acheminer jusqu’à destination avec cette QoS [TOU 02]. Le principe du modèle IntServ repose sur deux fondements [RFC 1633] : •

Tout d’abord le réseau doit être contrôlé et soumis aux mécanismes de contrôle d’admission des flux ;

•

La nécessité de disposer de mécanismes de réservation de ressources pour obtenir différents services. IntServ utilise pour cela le protocole de signalisation appelé RSVP (Resource ReSerVation Protocol) (nous le détaillerons ultérieurement).

Le groupe de travail IntServ a définit une architecture capable de prendre en charge la QoS sans toucher au protocole IP [TOU 99]. Les réseaux à intégration de services sont constitués de routeurs qui assurent les fonctionnalités de contrôle d’admission de flux et de réservation de ressources. Leur architecture est présentée dans la figure 2 [BET 01] : Protocole de signalisation (RSVP)

Protocole de signalisation (RSVP)

Processus de réservation

Contrôle d’accès

Paquets entrants

Classificateur de paquets

Contrôle d’admission

Ordonnanceur

Processus de routage

Paquets sortants

Figure 2 : Modèle de référence d’un routeur IntServ

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 12

Protocoles de routage avec QoS dans l’Internet Le contrôle de trafic est mis en œuvre à travers les modules suivants : ¾ Le contrôle d’accès (policy control) : vérifie si la requête d’un flot est légitime par rapport aux règles fixées par l’administrateur du réseau. ¾

Le classificateur de paquets (packet classifier) : accueille les paquets entrants et classe chaque paquet dans la classe de flots convenable.

¾ L’ordonnanceur (scheduler) : reçoit les paquets du module précédent et gère leur retransmission en utilisant des files d’attente. Tous les paquets qui seront classés par le classificateur et appartenant à une même classe seront traités de la même manière par l’ordonnanceur. ¾

Le contrôleur d’admission (admission controller) vérifie s’il est capable de garantir la qualité de service requise par un flot et s’il y a suffisamment de ressources disponibles au moment de l’établissement d’une réservation.

¾ Le module de réservation de ressources : qui est en permanence en communication avec les différents composants du routeur. Il offre les mécanismes de signalisation nécessaires pour mettre en place une réservation le long d’un chemin pour un flot donné.

1.1 Caractérisation des flots : La spécification des flots permet d’expliciter la Qualité de Service requise par chacun des flots ainsi que les caractéristiques du trafic généré par ceux-ci. Les besoins de Qualité de Service spécifiés par une application sont définis selon les paramètres suivants : – la priorité : priorité qui sera attribuée au flot ; – le débit : débit requis par l’application ; – le délai : besoin en délai de bout en bout ; –

la perte : taux de perte autorisé par l’application.

Pour pouvoir utiliser les services définis pour les réseaux à intégration de services, le groupe IntServ a défini et déterminé une propriété pour caractériser les trafics d’un tel réseau. [RFC 2215] décrit les paramètres de spécification de trafic contenus dans une structure de données de spécification de trafic appelée TSpec (Traffic Specification). La caractérisation s’effectue selon le modèle représenté par la figure 3 ci-dessous : le token bucket (seau à jetons).

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 13

Protocoles de routage avec QoS dans l’Internet

Jetons, débit r

Seau de jetons Capacité b Débit crête, p

flot

Figure 3 : mécanisme de seau à jetons

¾ b : capacité du « seau » ¾ r : débit moyen délivré par le « seau » ¾ p : débit crête ¾ M : taille maximale du paquet ¾ m : taille minimale d’un paquet contrôlable

Le mécanisme du seau à jetons (token bucket) est utilisé pour lisser le trafic afin de mieux le contrôler. Il regroupe trois paramètres parmi cinq du TSpec. Tout d’abord, par sa capacité (paramètre b) et par le débit autorisé (paramètre r), il permet de contrôler le débit moyen du flot. Le paramètre p est utilisé pour limiter le débit crête. Les deux autres paramètres de TSpec qui interviennent dans la spécification des flots sont « la taille maximale » du paquet contenu dans le flot (notée M), et « la plus petite unité de traitement » (notée m). Ces deux paramètres ne caractérisent les flots que par rapport à l’implémentation des mécanismes de QoS. Ainsi, on ne pourra garantir une certaine QoS qu’aux paquets du flot n’excédant pas la taille maximale définie dans TSpec. Le paramètre « m » indique que tous le paquets dont la taille lui sera inférieure, seront tout de même traités comme un paquet ayant cette taille « m ».

1.2 Classes de service Le groupe de travail IntServ a rendu l’Internet un réseau à intégration de services en distinguant deux classes de services supplémentaires par rapport au service traditionnel du «besteffort». Les classes de service permettent de définir le traitement particulier que recevra un flux dans un routeur.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 14

Protocoles de routage avec QoS dans l’Internet Ces nouveaux services sont la classe à charge contrôlée, mieux connue sous le nom « controlled load service », où les performances reçues sont celles d’un réseau peu chargé ; et la classe de service garanti, ou encore « guaranteed service », où l’application qui demande le service possède l’assurance que les performances du réseau vont rester celles dont elle a besoin [TOU 02].

1.

La classe Best-effort : le service dit « au-mieux » (Best-Effort) ne garantit aucun critère de qualité de service : ni le délai de transmission, ni l’absence de pertes de paquets, ni l’absence de gigue ne sont considérés pour acheminer les flots de diverses natures. Ce service n’est évidemment pas approprié pour les flux multimédia qui transportent des informations à délivrer en temps réel. Il peut toutefois servir pour le transport de données. La messagerie électronique serait l’application la moins sensible à tous ces critères et supporterait donc sans trop de contraintes, le service du best-effort.

2.

La charge contrôlée (Controlled-load) [RFC 2211] : Le service de charge contrôlée effectue une différenciation entre les trafics et leur attribue des codes de priorité en fonction de la sensibilité des applications. Bien évidemment, ce service est plus adéquat que le besteffort pour les applications multimédia très sensibles à la congestion dans le réseau. Il offre un service proche de celui présenté par le best-effort lorsque celui-ci se trouve particulièrement dans des conditions de réseaux non congestionnés. La garantie est donc fournie pour le débit. Mais contrairement au best-effort, le service de charge contrôlée ne détériore pas la qualité du flot lorsque le réseau est surchargé. En effet, les applications qui demandent ce type de service doivent tenir informé le réseau du trafic qui va le traverser, de manière à obtenir une meilleure exploitation du service et du réseau lui-même. Néanmoins, le réseau ne promet pas de garanties temporelles. La variable de spécification de trafic (TSpec) est nécessaire pour identifier la conformité des paquets par rapport au service.

3. Le service garanti (Guaranteed Service) [RFC 2212] est basé sur les résultats du Network Calculus qui permet de trouver une borne maximale pour le temps de transmission d'un paquet et la taille maximale des mémoires tampons nécessaires dans les équipements pour éviter les pertes de paquets. Le destinataire en fixant le débit minimal que doit offrir le réseau à ce flux influe sur le temps maximal de transmission des paquets. Ainsi, pour réduire les temps de traversée, il est possible de réserver à un débit nettement supérieur à celui de la source.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 15

Protocoles de routage avec QoS dans l’Internet 1.3. Le protocole RSVP Les premières études ont cherché à améliorer les algorithmes d’ordonnancement du traitement des datagrammes dans les machines. Ensuite, on s’est beaucoup plus intéressé à la gestion globale des ressources du réseau, ce qui a donné naissance à un protocole de réservation de ressources connu aujourd'hui sous le nom de RSVP (Reservation Setup Protocol). Ce protocole est un protocole de signalisation au modèle de ce qui existe dans les réseaux classiques de télécommunications comme le réseau téléphonique par exemple. Le principe en est simple : chaque application déclare au réseau ses besoins ; à partir de ces besoins, le réseau, s'il le peut, garantit la disponibilité des ressources nécessaires à l'application. Le protocole de signalisation RSVP, qui a été défini par le groupe de travail RSVP [RFC2205-RFC2208], est un mécanisme dynamique conçu pour effectuer des réservations de ressources explicites dans une architecture IntServ. RSVP est utilisé uniquement pour la communication des paramètres de QoS, il ne comprend pas l'information qu'il transporte dans les requêtes de QoS. RSVP est initié par une application au début d'une session de communication. Une session est identifiée par l'adresse IP de destination, le type de protocole de la couche transport et le numéro de port de destination. Le protocole RSVP définit sept types de messages, les principaux étant les messages PATH et RESV. Ces deux messages assurent le fonctionnement de base de RSVP. Tous les messages RSVP sont envoyés sur le réseau comme des datagrammes IP avec le numéro de protocole 46.

Emetteur

Récepteur Le message PATH Le message RESV Figure 4 : Messages PATH et RESV pour la réservation de ressources.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 16

Protocoles de routage avec QoS dans l’Internet Chaque paquet RSVP contient les détails sur la session à laquelle il appartient. L'affectation des ressources demandées par l'intermédiaire de RSVP pour un flot donné est indépendante de RSVP, elle dépend d'IntServ. Une fois que les ressources demandées par RSVP sont réservées, elles sont utilisées pour ce flot de données. RSVP établit et maintient un état logiciel (soft state) entre les noeuds constituant le chemin réservé. Par opposition à la réservation d'un chemin statique, cet état logiciel est caractérisé par des messages de rafraîchissement envoyés périodiquement le long du chemin pour maintenir l'état [LEG 01]. RSVP fournit aussi une QoS dynamique tenant compte des modifications de ressources ; celles-ci peuvent être dues au destinataire, à l'émetteur ou encore à de nouveaux membres dans un groupe multicast. Dans RSVP, le destinataire est responsable de la réservation de ressources QoS. L'émetteur RSVP envoie ses exigences au destinataire. Après réception, le destinataire RSVP utilise le même chemin pour renvoyer un message spécifiant la QoS souhaitée et fixer la réservation des ressources correspondantes dans chaque nœud. L'émetteur RSVP envoie alors les données. Ainsi, si une route change au cours de la transmission, des données peuvent être temporairement transmises à travers un chemin où aucune réservation n’a été faite. De plus, RSVP a été prévu pour fonctionner dans un environnement où certains routeurs ne garantissent pas la réservation de ressources (routeurs non-RSVP). Dans ce cas, la réservation ne sera réalisée que dans les nœuds la permettant. Les participants de la session en sont informés, ce qui leur permet de prendre les décisions applicatives qu’ils souhaitent. Cette traversée de routeurs classiques n’est pas une cause d’échec du processus de réservation. Dans le cas de défaillance d’un routeur, le protocole RSVP reconstruit la route depuis l’émetteur jusqu’aux récepteurs si les mécanismes de routage permettent cette reconfiguration. Avec RSVP, les détails de cette reconstruction dépendent du protocole de transmission utilisé ; en effet, la source continue de transmettre des données à travers un chemin sans réservation jusqu’à ce qu’il y ait eu un échange de messages PATH et RESV. Un autre problème important concerne RSVP et les politiques de contrôle. RSVP ne définit pas la politique elle-même mais définit seulement le mécanisme pour transporter celle-ci. Certains constructeurs désirant alors fournir des mécanismes propriétaires, un nouveau groupe de travail "RAP" de l'IETF a été créé fin 1997 pour définir des extensions à RSVP relatives aux politiques de contrôle et spécifier un protocole d'échange d'informations de contrôle entre des nœuds RSVP et des « policy servers » capables de fournir ces informations. Le traitement supplémentaire lié à RSVP résulte principalement du rafraîchissement périodique de l’information contenue dans les routeurs. Ce qui semble impliquer que celui-ci va être directement BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 17

Protocoles de routage avec QoS dans l’Internet proportionnel au nombre de participants à une session. Mais RSVP contient un mécanisme permettant d’alléger cette surcharge : la fusion. Celui-ci assure qu’un nombre minimal de messages de réservation sera émis sur chaque liaison.

2. Le modèle de différenciation de service : DiffServ La difficulté de déployer IntServ sur Internet tient dans sa considération de la Qualité de Service au niveau du flux. La gestion de la réservation de ressources à ce niveau demande une immense capacité de traitement. Ainsi, plutôt que d’utiliser la technique de réservation par session, un second groupe de l’IETF s’est orienté vers un autre modèle d’implémentation de qualité de service, que l’on peut utiliser pour des réseaux importants en envergure, mais aussi en charge : le modèle à différenciation de services. L’intérêt d’un tel modèle est de pouvoir s’occuper du problème d’approvisionnement en qualité de service à travers une allocation de services basée sur un contrat établi entre un fournisseur de services et un client. Pour le groupe de travail DiffServ, un flux de paquet IP perd son identité propre et circule sur Internet en tant que membre d’une classe de flux. L’approche de DiffServ permet donc à des fournisseurs d’offrir différents niveaux de services à certaines classes de flots de trafic rassemblés. Ainsi, il devient question de supporter un schéma de classification en attribuant des priorités à des agrégats de trafic. De ce fait, les paquets sont classés grâce à un mécanisme de marquage dans l’en-tête des paquets IP, et les services qui sont octroyés par les routeurs à ces paquets dépendent des classes alors définies [RFC 2638]. Ce marquage est effectué au niveau de l’étiquette de l’en-tête du paquet : le DSCP (DiffServ Code Point) [RFC 2474] qui se situe dans le champ DS de l’en-tête IP réservé à DiffServ. Les figures 5 et 6 présentent l’emplacement des champs DS et DSCP dans les en-têtes IPv4 et IPv6, le format du champ DS et donné par la figure 7. Grâce à ce marquage, et à l’approche différente de DiffServ par rapport à IntServ, les routeurs DiffServ gardent une certaine souplesse d’utilisation du point de vue acheminement par rapport à ceux utilisés dans l’IntServ.

Version TTL

IHL Identification

DS Flag Protocol

Total length Fragment Offset Header Checksum

Source Address Destination Address Figure 5 : Emplacement du DS (vs. DSCP) dans l’en-tête IPv4

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 18

Protocoles de routage avec QoS dans l’Internet

Version

Flow label Hop limit

DS Playload length

Hop limit

Source Address

Destination Address

Figure 6 : Emplacement du DS (vs. DSCP) dans l’en-tête IPv6.

0

1

2

3

4

5

6

CSCP

7

unused DSCP Figure 7 : Format du champ DS.

2.1 Architecture du modèle DiffServ Dans le modèle DiffServ, le réseau est divisé en Domaines DiffServ (DS Domain) (Voir la figure 8). Chaque domaine est un groupement de routeurs qui possèdent une même définition de service et de PHB. Ces domaines sont regroupés dans des Régions DiffServ (DS Region). Chaque région doit être capable d’offrir la QoS de bout en bout pour un chemin qui traverse ses domaines [BET 01]. Les hôtes sont directement rattachés aux routeurs frontières. Entre ces derniers et les domaines DS, des contrats de service appelé SLA (Service-Level Agreement) sont mis en œuvre pour spécifier les classes de service supportées et la quantité de trafic autorisée pour chaque classe. Ces informations sont nécessaires à connaître si un client désire obtenir des services différenciés. Région DiffServ

Routeurs frontières

Routeurs internes

Domaines DiffServ Figure 8 : Architecture d’une région DiffServ

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 19

Protocoles de routage avec QoS dans l’Internet L’architecture adoptée par DiffServ est fondée sur deux principales catégories de routeurs : les routeurs frontières (edge routers) et les routeurs de coeur (ou internes) (core routers). a. Les routeurs frontières : les « edge routers » Les routeurs frontières sont responsables de la classification des paquets et du conditionnement du trafic. L’opération de classification est opérée à l’entrée du réseau, zone où la différenciation de service est mise en œuvre, le domaine DS, pour assurer le traitement ciblé: celui de pouvoir différencier les différents flots qui arrivent dans le réseau. Ces routeurs sont caractérisés par leur gestion des états par flots. Après classification, les paquets subissent une opération de vérification (module "meter") qui consiste à déterminer le niveau de conformité pour chacun des paquets d’un même flot. Ces niveaux de conformité varient en fonction du conditionnement requis par le service. L’étape qui suit la vérification du niveau de conformité est de deux types : si les paquets sont conformes, alors ils sont envoyés pour être étiquetés. Dans le cas contraire, il y a trois manières de traiter les paquets non conformes : mise en forme (shape), marquage (mark) ou élimination (drop) : • l’opération de mise en forme (shape) a pour but de rendre conforme les paquets qui ne le sont pas, et ce, par simple retardement de son acheminement. Après un certain temps de retardement, les paquets deviendront conformes et seront injectés vers le module d’étiquetage. • le processus d’élimination (drop) est nécessaire pour assurer un fonctionnement fiable du routeur : tous les paquets qui ne sont pas conformes seront forcés à être éliminés. Les flots pour lesquels il serait préférable d’utiliser cette méthode sont les flots interactifs. En effet, si on choisit d’appliquer la mise en forme pour ce type de flots, les paquets subiront un retard significatif et rendront l’interactivité de l’application impossible. C’est pourquoi il leur est préférable d’être éliminés. • enfin, le mécanisme de marquage (mark) a pour effet d’attribuer une priorité aux paquets en fonction du résultat fourni par l’opération de vérification. Par conséquent, en plus du premier niveau de différenciation, une seconde classification est effectuée par l’opération de marquage (nous verrons son utilisation au niveau des classes de service de DiffServ).

Avant d’être envoyés vers l’intérieur du réseau, les paquets subissent une dernière opération : l’étiquetage effectif du champ DSCP. La valeur attribuée au champ correspond au résultat de toutes les opérations précédentes. Celle-ci peut être modifiée au sein d’autres routeurs de bordure,

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 20

Protocoles de routage avec QoS dans l’Internet selon le nouveau conditionnement qui va être appliqué au flot après sa traversée dans les équipements. La marque qu'un paquet reçoit identifie la classe de trafic à laquelle il appartient. Les paquets ainsi marqués sont alors envoyés dans le réseau avec cette mise en forme. DSCP marking

IN

Classifier

shape meter

mark

OUT

drop

Figure 9 : Principe de fonctionnement d’un routeur frontière

b. Les routeurs internes : les « core routers » Les routeurs internes (voir figure 9) se chargent de la gestion des états par classe et traitent les paquets en fonction de la classe codée dans l’en-tête en les traitant en accord avec le comportement local correspondant : le Per-Hop-Behavior (PHB). Les PHB se basent uniquement sur le marquage de paquet, pour permettre aux routeurs d’identifier la classe de trafic à laquelle le paquet appartient ; en aucun cas ils ne traiteront différemment des paquets de

Classificateur

sources différentes.

Classification

Gestion de files d’attente

Mécanismes d’ordonnancement

Figure 10 : Architecture d’un routeur interne.

Comme le montre la figure 10 le classificateur envoie les paquets vers différentes files d’attente, selon l’identificateur placé dans le champ DS, préalablement marqué par les routeurs d’entrée du réseau (les routeurs « edge »). Seule une partie du champ permet d’indiquer la file d’attente appropriée : il s’agit du champ CSCP (Class Selector Code Points) qui, constitué de 3 bits, permet de coder la classe de service correspondant à la catégorie du paquet. Ainsi, chaque file d’attente caractérise une classe de service et ne recevra que les paquets qui sont conformes à ce service. BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 21

Protocoles de routage avec QoS dans l’Internet Au niveau des files d’attente, des mécanismes de gestion sont implémentés pour obtenir un maximum d’équité de traitement lors de congestions. Les mécanismes d’ordonnancement, permettent de traiter les paquets en fonction de leur besoin en débit, délai, etc…

2.2 Classes de services de DiffServ Trois niveaux de priorité sont définis dans DiffServ : le service "Best-Effort", le service "Assured Forwarding", et le service "Expedited Forwarding". 1. Le service « Best-Effort » Le service Best-Effort (BE), que nous avons déjà décrit précédemment, correspond à la priorité la plus faible. C’est le service actuellement utilisé dans l’Internet et qui ne distingue pas les flots prioritaires des flots moins prioritaires [TOU 02]. 2. Le service « Assured Forwarding » Le comportement Assured Forwarding (AF) est le fruit de plusieurs propositions qui centraient la différenciation des paquets sur des algorithmes de discrimination des paquets à l’intérieur d’une même file d’attente. Il englobe quatre classes de traitement et un second niveau de différenciation pour attribuer les priorités : la précédence. Cette dernière met en évidence l’importance d’un paquet et par conséquent la dégradation que peut engendrer sa perte sur la qualité de l’information. La notion de précédence peut être utilisée au sein des routeurs pour perfectionner l’opération de rejet des paquets en cas de surcharge et de congestion du réseau. Le service AF se trouve donc constitué de quatre classes de service définissant chacun trois niveaux de priorité. De ce fait, le service est composé de douze PHB interdépendants (6 bits) pour les douze PHB définis [RFC 2597]. 3. Le service « Expedited Forwarding » Le service Expedited Forwarding (EF) défini dans [RFC 2598] conçu pour servir des applications demandant de faibles pertes, un délai et une gigue très faibles et une garantie de bande-passante. Le principe de base est de pouvoir garantir une taille des files d’attente dans les routeurs la plus restreinte possible. Pour assurer qu’un routeur puisse avoir un comportement (PHB) fonctionnant en EF, il doit assurer que le débit d’émission du trafic soit toujours supérieur ou égal à un certain seuil. Ce dernier peut être connu et configurable, auquel cas les mécanismes de gestion externes peuvent faire respecter la relation entre le débit d’entrée et le débit de sortie au niveau de tous les nœuds du domaine.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 22

Protocoles de routage avec QoS dans l’Internet Le service EF est un service à forte priorité, délivrant des garanties en matière de bande passante, et permettant des taux de perte, de délai et de gigue faibles [TOU 02].

3. Le groupe de travail QoSR (QoS Routing) Le groupe de travail QoSR (Quality of Service Routing) de l'IETF a pour objectif d'intégrer les métriques de la QoS et les critères de choix d'un chemin dans les protocoles de routage existants. Pour cela, un RFC [RFC 2386] définissant les conditions auxquelles doit satisfaire ce modèle a été rédigé par le groupe de travail QoSR, avec pour objectifs: •

encourager l'évolution des architectures de routage intradomaines basées sur la QoS,

•

favoriser les interactions simples, cohérentes et stables entre les domaines administratifs (AS) implémentant les solutions de routage ainsi définies.

3.1 Intradomain QoSR Etant donné un ensemble clairement défini de paramètres QoS, un mécanisme de routage robuste et raisonnable doit calculer le chemin approprié sans dégrader la performance globale du réseau. Aussi, des concessions sur le calcul du chemin ont été faites, quitte à ne pas obtenir le chemin optimal. De plus, les mécanismes de contrôle d'admission ou utilisation des bits IP Precedence dans le rejet des paquets peuvent aider à réduire le trafic pour lequel le chemin doit être calculé. Un protocole de routage "à état de liens" dont la caractéristique est de détecter rapidement les modifications de topologies et les transmettre à ses voisins, peut convenir. Mais des modifications sont nécessaires pour intégrer les exigences QoS et minimiser les informations échangées dans les annonces de liens. Deux propositions ont été faites pour utiliser OSPF en ce sens. 3.2 Interdomain QoSR L'aspect principal dans le routage entre domaines différents (AS) est la stabilité. C'est pourquoi, un protocole de routage à état de liens, qui communique les modifications de topologies à ses voisins, semble peu adapté, là où il est préférable de minimiser les échanges d'informations entre AS voisins. Actuellement le protocole BGP (Border Gateway Protocol) largement implémenté dans l'Internet, fournit le routage inter domaines dans l'Internet. Dans BGP, le chemin est basé sur la destination et BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 23

Protocoles de routage avec QoS dans l’Internet est sélectionné suivant le plus long préfixe correspondant. Plusieurs mécanismes basés sur les attributs de BGP peuvent influencer le choix de celui-ci, sans toutefois offrir un bon niveau de fonctionnalité. Cependant, ils conservent une certaine importance, tant que des méthodes de choix du chemin basé sur les métriques QoS ne sont pas disponibles. Un autre problème affectant la QoS est le routage asymétrique du fait des politiques différentes de routage des diverses organisations. Ceci affecte surtout les nouvelles applications temps réel audio et vidéo, mais aussi le protocole RSVP qui nécessite la symétrie des chemins pour fonctionner.

4. Le groupe de travail MPLS (Multi Protocol Label Switching) Comme nous l’avons vu, l’objectif de DiffServ est de fournir une solution de Qualité de Service qui résiste au facteur d’échelle. Le protocole MPLS, défini plus récemment, a été conçu pour répondre aux mêmes besoins. De ce fait, la charte du groupe de travail MPLS a été définie dans le [RFC 3468]. La commutation multi-protocoles avec étiquetage des flux (Multi-Protocol Label Switching, MPLS) est une technique réseau en cours de normalisation à l'IETF dont le rôle principal est de combiner les concepts de commutation de label et de routage. MPLS doit permettre d’améliorer le rapport performance/prix des équipements de routage, d’améliorer l’efficacité du routage (en particulier pour les grands réseaux) et d’enrichir les services de routage (les nouveaux services étant transparents pour les mécanismes de commutation d'étiquette, ils peuvent être déployés sans modification sur le coeur du réseau). Le protocole MPLS est un protocole qui utilise un mécanisme de routage qui lui est propre, basé sur l'attribution d'une étiquette (label) à chaque paquet. Cela lui permet de router les paquets en optimisant les passages de la couche 2 à la couche 3 du modèle OSI et d'être indépendant du codage de celles-ci suivant les différentes technologies (ATM, Frame Relay, Ethernet etc...). Le but est d'associer la puissance de la commutation de la couche 2 avec la flexibilité du routage de la couche 3. Schématiquement, on peut le représenter comme étant situé entre la couche 2 (liaison) et la couche 3 (réseau). La base de MPLS, la commutation donc, introduit bien entendu une étiquette (label, tag) qui sert à chaque équipement MPLS pour acheminer (forward) chaque unité de donnée entrante : chaque unité de données (PDU, Protocol Data Unit dans le vocabulaire ISO) contient une marque, une étiquette qui en permet l’identification, comme un code barre sur un produit. Il n’y a pas de différence avec ce que fait un commutateur X25, FR, ATM ou MAC (commutateur de réseau local,

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 24

Protocoles de routage avec QoS dans l’Internet commutateur Ethernet, LAN switch) ou même un routeur IP, appelé aujourd’hui commutateur de niveau 3, surtout dans le haut de gamme. Ces commutateurs MPLS portent le nom de LSR (Label Switch Router) qui fait référence et à la commutation (switch) et aux étiquettes. 4.1 Définitions élémentaires Avant d’expliquer le fonctionnement de MPLS, nous donnerons ci-dessous quelques définitions élémentaires : 1. Label ou étiquette : entier qui est associé à un paquet lorsqu'il circule dans un réseau MPLS et sur lequel ce dernier s'appuie pour prendre des décisions de routage. 2. MPLS Ingress node : un routeur d'entrée MPLS routeur qui gère le trafic qui entre dans un réseau MPLS. 3. MPLS Egress node : Un routeur de sortie MPLS ou encore MPLS Egress Node est un routeur qui gère le trafic qui sort d'un réseau MPLS. 4. LSR : Un routeur de commutation par label ou LSR (Label Switch Router) est un routeur d'un réseau MPLS qui est capable de retransmettre les paquets au niveau de la couche 3 en s'appuyant seulement sur le mécanisme des labels. 5. LER : Un LER (Label Edge Router) est un LSR qui fait l'interface entre le réseau MPLS et le monde extérieur. C'est lui qui est chargé par exemple d’étiqueter les paquets à leurs entrées dans le réseau MPLS.

4.2. Fonctionnement du protocole MPLS Le principe de MPLS s'appuie sur une technique qui permet d'attribuer une étiquette à chaque flux de données TCP/IP. Cette étiquette courte, de longueur fixe, correspond à un bref résumé de l'en-tête du datagramme IP ; elle fournit des informations sur le chemin que le paquet doit parcourir, afin qu'il puisse être commuté ou routé plus rapidement sur des réseaux utilisant différents types de protocoles. Ainsi les commutateurs/routeurs analysent l'étiquette des flux au lieu de leur adresse de destination. Le premier routeur MPLS que le datagramme rencontre appose une étiquette sur ce datagramme qui peut alors être envoyé très rapidement dans le réseau MPLS en fonction de cette étiquette (voir Figure 11). De l'autre côté du réseau, le datagramme IP est "déballé" et acheminé de manière classique. Le protocole MPLS, comme spécifié par l'IETF, est principalement destiné à être utilisé en combinaison avec DiffServ.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 25

Protocoles de routage avec QoS dans l’Internet Label swapping

Inclusion du label selon la FEC et transmission

LSR Echange de labels selon la FEC et transmission

LSR Echange de labels selon la FEC et transmission

Ingress node

LSR

Edge LSR ou LER

Egress node

LER

Figure 11 : Architecture d’un routeur interne

4.3 Avantages de MPLS MPLS apporte plusieurs autres bénéfices pour les réseaux IP : • Gestion du trafic (Traffic Engineering) i.e. la capacité de configurer le chemin que vont

emprunter les différents flux sur le réseau et d'associer des caractéristiques de performances à une classe de trafic, • Etablissement de VPNs, i.e. la possibilité d'établir des VPNs sur un réseau MPLS sans la

nécessité d'utiliser des protocoles de cryptage ou des applications clientes particulières, • Transport de services associés au niveau 2 (tels Ethernet, Frame Relay and ATM) au dessus

d'un noyau IP/MPLS, • Suppressions des " Multiple layers " i. e. que typiquement la plus part des fournisseurs de

réseau utilisent un modèle de recouvrement où SONET/SDH est déployé à la couche 1, ATM est utilisé à la couche 2 et l'IP est utilisé à la couche 3. En utilisant MPLS, les fournisseurs de réseaux peuvent faire passer plusieurs des fonctions de contrôle de SONET/SDH et d'ATM à la couche 3, simplifiant de ce fait la gestion du réseau et sa complexité. Un chemin basé sur les mécanismes MPLS (LSP) peut être établi en traversant plusieurs couches de transports de niveau 2 tels que ATM, Frame Relay ou l'Ethernet. Une des vraies promesses de MPLS est la capacité de créer les circuits de bout en bout, avec des caractéristiques de performances spécifiques, à travers n'importe quel type de support de transport, éliminant le besoin de réseaux de recouvrement ou de mécanismes de contrôle de niveau 2 seulement.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 26

Protocoles de routage avec QoS dans l’Internet

IV. Routage avec QoS dans les réseaux mobiles L'évolution rapide des systèmes mobiles impose la prise en compte des utilisateurs mobiles utilisant la même variété d'applications que les utilisateurs fixes. L'introduction de la QoS dans les réseaux mobiles est encore plus complexe, car leur topologie et leurs ressources évoluent dynamiquement. Le besoin de mécanismes de QoS dans ces environnements est incontestable du fait de la rareté des ressources, de l'imprévisibilité de la bande passante et des taux d'erreurs importants. S’il est facile de prendre en considération la disparition ou la faible fiabilité d’un lien dans les réseaux filaires, il n’en est pas de même dans les réseaux ad hoc. En effet, le simple fait de fermer une porte suffit pour couper un lien déjà existant. Par conséquent, il est impossible de prévoir si un lien existant à une certaine date sera toujours valide à une date ultérieure. (Voir [CHA 03]) Les travaux publiés concernant le routage avec QoS dans les réseaux ad hoc reposent beaucoup sur les protocoles de routage du groupe Manet (Mobile Ad hoc NETworks) [RFC 2501]. Un protocole a été proposé par [LEG 01] appelé MIR (Mobile IP Reservation Protocol). Il est basé sur un algorithme distribué qui répartit la bande passante localement et sur un contrôle d’admission dans le réseau qui garantit une plus faible probabilité de blocage aux handoffs qu’aux nouvelles connexions. Il propose également des mécanismes pour optimiser l’utilisation de la bande passante pour cette solution.

V. Algorithmes de routage Il es aujourd’hui connu et démontré que le problème de routage avec QoS est un problème NP-complet [VAN 03a][BET 03]. En pratique, ceci signifie la non faisabilité de la solution exacte. La problématique ne réside pas dans le fait de trouver un algorithme exact pour le routage avec QoS mais réside en fait dans la complexité de l’algorithme proposé.

1. Exemples d’algorithmes de routage avec QoS Plusieurs algorithmes ont été proposés pour le routage avec Qualité de Service. On peut citer par exemple : -

Algorithme approximatif de Jaffe,

-

Algorithme de Iwata,

-

Algorithme approximatif de Chen,

-

Algorithme aléatoire,

-

Algorithme H_MCOOP,

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 27

Protocoles de routage avec QoS dans l’Internet -

SAMCRA (Self-Adaptative Multiple Constraints Routing Algorithm)

-

TAMCRA (Tunable Accuracy Multiple Constraints Routing Algorithm)

(Pour plus de détails voir [KUI 02])

2. Complexité Le tableau suivant (voir Figure 12) résume la complexité de ces algorithmes [KUI 02] : Algorithme

Complexité au pire des cas

Algorithme de Jaffe

O(N log N + mE)

Algorithme de Iwata

O(mN log N + mE)

SAMCRA TAMCRA

O(kN log (kN) +k2mE)

EDSP,EBF

O( x22 ...xm2 N 2 ), O( x2 ...xm NE )

Randomized algorithm

O(mN logN + mE)

H_MCOP

O(N logN + mE)

LPH

O(k2NE)

A* Prune

O(QN(m + N + log h))

Figure 12 : Complexités au pire des cas des algorithmes de routage avec QoS.

3. Caractéristiques d’un algorithme de routage avec QoS En fait, un algorithme de routage avec QoS doit satisfaire les points suivants : •

Généralité : En effet, les applications multimédia tendent à avoir des besoins différents en matière de

bande passante, délai, gigue, coût, et ainsi de suite. Du point de vue d’un concepteur réseau, il serait avantageux de définir un algorithme de routage générique au lieu d’en implémenter plusieurs qui sont différents, et qui répondent indépendamment à des besoins différents en QoS. •

Extensibilité : Comme l’infrastructure du réseau et sa capacité évoluent, de nouvelles applications sont

devenues possibles. Il serait alors intéressant de concevoir de algorithmes extensibles et les adapter aux nouvelles applications, car les réseaux deviennent de plus en plus complexes d’un côté, et le déploiement de nouveaux Algorithmes est très coûteux d’un autre côté. •

Simplicité La simplicité d’un algorithme de routage en terme de temps/complexité logique permet

souvent une efficacité d’implémentation, de débogage, et d’évaluation.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 28

Protocoles de routage avec QoS dans l’Internet •

Scalabilité Le critère de scalabilité ou de « mise en échelle » est un critère très évident.

VI. Problèmes ouverts dans le routage avec QoS Les problèmes suivants sont classées comme problèmes ouverts (open issues) dans le domaine du routage avec QoS, et donc représentent un défi pour la communauté des chercheurs dans ce domaine [VAN 03a]. - Déterminer dans quels graphes et structures à états de liens le problème du MC(O)P (Multiple Constraints (Optimal) Path) n’est pas NP-complet, - Comparer de façon détaillée et objective les aspects dynamiques proposés du routage avec QoS, - Concevoir un protocole optimal de routage avec QoS, - Déployer les protocoles de routage avec QoS pour DiffServ, - Combiner les approches du routage avec QoS et les protocoles de signalisation, - Routage multipoint (multicast routing) avec QoS, - Routage avec QoS dans les réseaux mobiles ad hoc.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 29

Protocoles de routage avec QoS dans l’Internet

Conclusion Comme nous l’avons vu dans ce rapport, le problème de définir un protocole de routage avec QoS répondant à toutes les exigences attendues est très délicat Les trois modèles de l’IETF connus dans ce domaine sont IntServ, DiffServ et MPLS. Ce dernier protocole est une approche très prometteuse vu ses caractéristiques. Cependant, il rencontre certains problèmes de mise en œuvre. Une autre version de MPLS appelée GMPLS (Generalized MPLS) a été conçue pour répondre à quelques problèmes techniques de mise en œuvre. La difficulté pour le routage avec QoS dans les réseaux mobiles est plus grande vu la mobilité des nœuds. La tâche se complique plus lorsqu’il s’agit d’un routage multipoint (multicast routing) avec QoS. D’autre part, un algorithme qui puisse répondre à toutes les exigences en Qualité de Service des utilisateurs n’existe pas encore. Le problème majeur des solutions proposées est le facteur d’échelle ou « scalabilité ». Plusieurs problèmes restent ouverts et présentent donc un défi pour la communauté des chercheurs dans le domaine du routage avec Qualité de Service. .

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 30

Glossaire

Glossaire AOD

Audio On Demand

ATM

Asynchronous Transfert Mode

CCITT

Comité Consultatif International Téléphonique et Télégraphique

DiffServ

Differentiated Services

DVMRP

Distance Vector Multicast Routing Protocol

IETF

Internet Task Engineering Force

IntServ

Integrated Services

IP

Internet Protocol

ISP

Internet Service Provider

ISSLL

Integrated Services over Specific Link Layers

ITU

International Telecommunication Union

LER

Label Edge Router

LSR

Label Switch Router

MPLS

Multi-Protocol Label Switching

OSI

Open Systems Interconnection

OSPF

Open Shortest Path First

QoS

Quality of Service

QoSMIC

QoS Sensitive Multicast Internet protoCol

RAP

Ressource Allocation Protocol

RFC

Request For Comments

RIP

Routing Information Protocol

RSVP

Ressource ReSerVation Protocol

RTCP

Realtime Transport Control Protocol

RTP

Realtime Transport Protocol

TCP

Transmission Control Protocol

UDP

User Datagram Protocol

YAM

Yet Another Multicast protocol

VOD

Video On Demand

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 31

Bibliographie

Références bibliographiques [ALK 03]

Abdullah M. S. Alkahtani, M. E. Woodward and K. Al-Begain, «An Overview of Quality of Service (QoS) and QoS Routing in Communication Networks».Department of Computing, University of Bradford, UK. PGNet 2003.

[BET 01]

Hatem BETTAHAR, «Les Protocoles de Routage Multipoint et la Qualité de Services dans l'Internet ». Thèse de Doctorat en Informatique soutenue le 3 décembre 2001 à l’Université de Compiègne.

[CHA 98]

Gordon Chaffee, “RSVP: The ReSerVation Protocol” Berkeley Multimedia Research Center.

[CHA 03]

Claude CHAUDET et Isabelle GUERIN LASSOUS « Routage QoS et réseaux ad-hoc : de l’état de lien à l’état de nœud ». Rapport de recherche n° 4700 à l’INRIA. Site http://www.inria.fr

[HOR 00]

Eric HORLAIT, Nicolas ROUHANAIT, «Qualité de service dans l’architecture TCP/IP». Université Pierre et Marie Curie. Laboratoire LIP6. Mars 2000.

[KUI 02]

F.A. Kuiper, T. Korkmaz, M. Krunz, P. Van Mieghem, « Overview of constraint-Based Path Selection Algorithms for QoS Routing». Septembre 2002.

[LEG 01]

M. Gwendal LE GRAND, « Qualité de service dans des environnements Internet mobile».Thèse de Doctorat en Informatique. Université Pierre et Marie Curie. Paris VI. Date de soutenance : 11 Juillet 2001.

[MAC 02]

José Antonio Garcia Macias, " Architecture de Communication Mobile avec Qualité de Service (Mobile communication Architecture with Quality of Service). Thèse de Doctorat en Informatique soutenue le 8 Janvier 2002 à l'Institut National Polytechnique de Grenoble.

[MAM 03]

Zoubir MAMMERI, «Gestion de la Qualité de Service : Concepts et mécanismes ».Université Paul Sabatier de Toulouse. Notes de cours de Septembre 2003.

[MEL 01]

Jean-Louis Mélin, « Qualité de service sur IP ». Editions EYROLLES 2001.

[TOU 99]

Laurent Toutain, « Réseaux locaux et Internet, des protocoles à l’interconnexion », 2éme édition revue et augmentée. Edition HERMES, Janvier 1999.

[TOU 00]

Laurent Toutain, Jean Marie Bonnin, Octavio Medina ,« La qualité de service dans l'Internet » ALGOTEL 2000.

[TOU 02]

Leila TOUMI, « Algorithmes et mécanismes pour la qualité de service dans des réseaux hétérogènes ». Thèse de doctorat soutenue le 20 décembre 2002.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 32

Bibliographie

[VAN 03a]

P. Van Mieghem and F.A. Kuipers, « On the Complexity of QoS Routing» Delft University of Technology.Information Technology and Systems.P.O Box 5031, 2600 GA Delft, The Netherlands.

[VAN 03b] Van Mieghem, P. (ed.), F.A. Kuipers, T. Korkmaz, M. Krunz, M. Curado, E. Monteiro, X. Masip-Bruin, J. Solé-Pareta, and S. Sánchez-López, «Quality of Service Routing », Chapter 3 in Quality of Future Internet Services, EU-COST 263 Final Report, edited by Smirnov et al. in Springer LNCS 2856, pp. 80-117. 2003. [WAN 96]

Z. Wang and J. Crowcroft, "Quality-of-Service Routing for Supporting Multimedia Applications", IEEE Journal on Selected Areas in Communications, vol. 14, n. 7, pp. 1228-1234, 1996.

[ZHA 99]

Peng ZHANG, « Perspectives of QoS routing in the Internet: Preliminary Study».technical report. Laboratory of Telecommunication technologie.Helsinki University of Technology.9 Septembre 1999.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 33

Bibliographie

Les RFCs [RFC 1633]

R. Braden, D. Clark, S. Shenker: Integrated Services in the Internet Architecture: an Overview. Juin 1994.

[RFC 2205]

R. Braden, Ed. L. Zhang S. Berson S. Herzog S. Jamin Resource ReSerVation Protocol (RSVP). Septembre 1997.

[RFC 2206]

F. Baker, J. Krawczyk, A. Sastry : RSVP Management Information Base using SMIv2. Septembre 1997.

[RFC 2207]

L. Berger, T. O'Malley : RSVP Extensions for IPSEC Data Flows. Septembre 1997

[RFC 2208]

A. Mankin, Ed., F. Baker, B. Braden, S. Bradner, M. O`Dell, A. Romanow, A. Weinrib, L. Zhang : Resource ReSerVation Protocol (RSVP) -- Version 1 Applicability Statement Some Guidelines on Deployment. Septembre 1997.

[RFC 2210]

J. Wroclawski .The Use of RSVP with IETF Integrated Services. Septembre 1997.

[RFC 2211]

J. Wroclawski. Specification of the Controlled-Load Network Element Service. Septembre 1997.

[RFC 2212]

S. Shenker, C. Partridge, R. Guerin. Specification of Guaranteed Quality of Service. Septembre 1997.

[RFC 2215]

S. Shenker, J. Wroclawski, “General Characterization Parameters for Integrated Service Network Elements”, RFC 2215, September 1997.

[RFC 2386]

E. Crawley R. Nair B. Rajagopalan H. Sandick A Framework for QoS-based Routing in the Internet. Aout 1998.

[RFC 2474]

K. Nichols, S. Blake, F. Baker, D. Black., Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers. Decembre 1998.

[RFC 2475]

S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss. An Architecture for Differentiated Service. Décembre 1998.

[RFC 2501]

S. Corson, J. Macker : Mobile Ad hoc Networking (MANET) - Routing Protocol Performance Issues and Evaluation Considerations. Janvier 1999.

[RFC 2597]

J. Heinanen, F. Baker, W. Weiss, J. Wroclawski : Assured Forwarding PHB Group. Juin 1999.

[RFC 2598]

V. Jacobson, K. Nichols, K. Poduri : An Expedited Forwarding PHB. Juin 1999.

[RFC 2638]

K. Nichols, V. Jacobson, L. Zhang : A Two-bit Differentiated Services Architecture for the Internet. Juillet 1999

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 34

Bibliographie

[RFC 3468]

L. Andersson et G. Swallow : The Multiprotocol Label Switching (MPLS) Working Group decision on MPLS signaling protocols. Février 2003.

BOUCHAMA Nadir et YAHIAOUI Saïd

RESYD 2004 35