Chapitre 3 La qualité de service dans les
réseaux à commutation IP
3.1 Introduction du chapitre
Comme nous l'avons vu au chapitre 2, les mécanismes nécessaires à la
fourniture de la qualité de service dans les réseaux à commutation de
paquets sont maintenant assez bien connus. Cependant, le développement de
nouvelles technologies pour les réseaux haut débit rend nécessaire
l'adaptation de ces techniques pour ces nouvelles technologies. Il est en
effet nécessaire, pour obtenir une qualité de service de bout en bout, que
les mécanismes de qualité de service soient mis en place également dans les
réseaux d'interconnexion.
Une technologie de réseau haut débit apparue récemment est la
commutation IP (ou plus généralement la commutation par
labels). Nous nous proposons d'adapter le modèle défini par l'IntServ (et
en particulier le protocole RSVP) au contexte de cette solution de façon à
obtenir une technologie de réseau haut débit intégrant la gestion de la
qualité de service.
Nous commençons par décrire le principe de la commutation IP et plus
particulièrement la solution IP switching. Puis nous étudions la façon d'y
intégrer la qualité de service pour obtenir notre proposition que nous
appelons ``RSVP switching''. Pour celle-ci nous proposons des ajouts simples
au protocole RSVP et une technique d'ordonnancement permettant d'optimiser
l'allocation des ressources. Pour finir, nous évaluons notre proposition par
le biais de simulations, de la réalisation d'un prototype et enfin d'une
étude de scalabilité réalisée sur une implémentation de RSVP.
3.2 La commutation IP
3.2.1 Motivation
Depuis plusieurs années des travaux importants sont menés pour utiliser le
protocole IP sur les réseaux ATM. En effet, la flexibilité et la robustesse
d'IP associées au développement spectaculaire de l'Internet l'ont imposé
comme protocole de couche réseau quasi-universel. D'autre part les
investissements industriels massifs dans ATM ont résulté en l'apparition de
matériel très performant à (relativement) bas prix et ont ainsi fait d'ATM
la technologie par excellence pour les réseaux haut débit. De plus, ATM a
été largement adopté dans le milieu des télécommunications.
De nombreuses solutions existent, nous pouvons les classer en deux familles
selon l'approche utilisée :
-
l'approche ``classique'' où IP fonctionne au dessus de la
signalisation ATM définie par l'ATM forum,
- l'approche ``commutation IP'' où IP fonctionne directement sur le
matériel ATM, la signalisation de l'ATM forum étant éliminée.
L'approche ``classique'', chronologiquement la première, inclut aussi bien
des solutions proposées par l'IETF, telles que Classical IP over
ATM (CLIP) [Lau93, Atk94], puis [LH98] et son extension
au multicast Multicast Address Resolution Server (MARS)
[Arm96, TA97], que des solutions développées par l'ATM forum,
comme LAN Emulation (LANE) [FM96] ou
MultiProtocol Over ATM (MPOA) [MPO97].
La mise en oeuvre et l'utilisabilité de ces solutions sont rendues
difficiles pour deux raisons :
-
l'inadéquation entre le modèle utilisé par IP et celui de l'ATM forum
: IP fonctionne en mode non connecté alors que les services ATM forum sont
en mode connecté.
- le recouvrement de fonctionnalités : il y a duplication des
fonctionnalités entre la signalisation ATM forum et la signalisation
IP. La superposition des deux signalisations fait qu'IP ne peut pas
connaître la topologie effective du réseau.
Si ces problèmes ne sont pas insurmontables, leurs conséquences sont
visibles dans toutes ces solutions par :
-
une complexité protocolaire très importante,
- l'inefficacité dans l'utilisation des ressources.
L'approche ``commutation IP'', au contraire, élimine la signalisation ATM
forum, IP ayant ainsi directement accès aux fonctionnalités de niveau
liaison du matériel ATM. Nous décrivons le principe de cette approche dans
la section suivante.
3.2.2 ATM sous IP
Comme le montre la figure 3.1, dans les solutions de type
``commutation IP'' IP est utilisé directement sur le matériel ATM (avec
cependant une couche d'adaptation réduite au strict nécessaire et donc très
légère) ce qui évite l'empilement des couches et des fonctionnalités des
solutions ``classiques''.
Figure 3.1 : Piles protocolaires des deux approches
Un élément d'interconnexion est un routeur IP qui contrôle un commutateur
ATM. Il peut ainsi traiter le trafic classiquement au niveau IP
(forwarding, nous parlerons de trafic routé) ou au niveau ATM
(switching, nous parlerons de trafic commuté).
Pour être commuté, le trafic doit arriver porteur d'un label correspondant à
une association (label amont, label aval, lien aval) pour le lien amont
considéré. Dans ce cas, le lien et le label de sortie sont accessibles
directement par simple indirection dans la table de commutation, on dit que
le trafic emprunte un ``raccourci'' (cut-through). La commutation de
cellules ATM peut avoir lieu directement, alors que l'absence de cette
information nécessite le réassemblage du paquet IP et la consultation des
tables de routage IP.
La mise en place des labels peut être :
-
orientée flot (flow driven), c'est à dire basée sur les
flots de données qui traversent le noeud. Les labels sont alors associés
aux flots.
- orientée topologie (topology driven), c'est à dire basée
sur les routes suivies par les données. Les labels sont alors mis en place
en fonction des informations de routage.
Le principe de la commutation IP a été généralisé à tous types de réseaux
sous l'appellation ``commutation par labels'' (label switching) qui
est étudiée par le groupe de travail Multi Protocol Label Switching
(MPLS1)
de l'IETF [C+99]. L'utilisation des labels est bénéfique même si le
noeud ne dispose pas d'un moteur de commutation. Ils permettent
d'accélérer le traitement des paquets en évitant l'opération de ``recherche
de plus long préfixe'' (longest prefix match) du routage classique.
3.2.3 La solution IP switching
IP switching est chronologiquement la première solution à avoir été
présentée et même commercialisée. Elle est orientée flot, donc
initialement tout le trafic est routé, puis des labels sont associés aux
flots qui peuvent alors être commutés. Comme illustré sur la figure
3.2, chaque IP switch choisit des
flots2 susceptibles d'être commutés,
leur attribue un label et transmet l'information (information de
redirection : description d'un flot et label associé) à son voisin
amont au moyen du protocole IFMP (Ipsilon Flow Management Protocol
[N+96a]). Celui-ci enverra désormais les paquets de ce flot sur le
VPI/VCI correspondant à ce label. Après réception d'une information de
redirection pour ce flot depuis l'IP switch aval, deux labels amont et aval
identifient le flot et il devient possible de le commuter par simple
insertion d'une entrée dans la table de commutation. C'est le rôle du
protocole GSMP (General Switch Management Protocol [N+96b]). Celui-ci
fournit également au routeur les informations sur les caractéristiques
pertinentes du commutateur. Dans sa deuxième version [N+98], il
permet également de spécifier des paramètres de qualité de service associés
à chaque entrée de commutation. Les informations de redirection sont
stockées dans des états relachés (éphémères). Ces états doivent être
rafraîchis régulièrement sous peine d'expirer, ce qui assure simplicité et
robustesse du mécanisme. L'encapsulation des paquets IP avec label dans les
trames ATM est définie dans le RFC 1954 [N+96c].
Figure 3.2 : IP switching
La décision d'attribuer un label à un flot IP est prise localement par le
module de classification de flots. Pour obtenir des performances
élevées, il est bien évident que l'IP switch doit commuter le plus de trafic
possible. Mais l'établissement d'un raccourci demandant un certain
overhead et un certain délai, il n'est rentable de commuter que les
flots suffisament longs pour que le gain obtenu par la commutation excède
l'overhead nécessaire à la mise en place des labels.
C'est le rôle du classificateur de flots de déterminer quels sont les flots
qui doivent être commutés, en ``devinant'' quelle sera leur longueur à
partir des informations telles que le protocole utilisé ou le nombre de
paquets déjà routés pour ce flot [NLM96, NML98]. Des simulations
basées sur des traces de trafic Internet [LM97] ont montré que
l'approche était efficace pour le trafic Internet tel qu'il était il y a
deux ans. Mais du fait de l'évolution rapide de l'Internet, ces
caractéristiques changent rapidement et il est donc difficile de prévoir la
validité de cette approche à moyen terme.
3.3 Notre proposition : RSVP switching
3.3.1 Intégration de RSVP
Dans IP switching, le rôle du classificateur de flots est de repérer
les flots de longue durée afin qu'ils soient commutés. Il se base pour cela
sur diverses informations qui fournissent implicitement des
indications sur la durée du flot. Nous considérons que le fait qu'une
garantie de service soit demandée pour un flot est une indication
explicite que ce flot sera de longue durée, la mise en place de la
réservation à l'aide du protocole RSVP demandant elle même un certain délai.
Nous décidons donc de commuter tous les flots pour lesquels doivent être
fournies des garanties de service. Cela n'implique cependant absolument pas
que tous les flots ``best-effort'' doivent être routés, mais plutôt que l'on
ajoute un critère pour la décision de commuter un flot. Commuter
uniquement les flots à QoS n'est souhaitable que si ces flots
constituent la majeure partie du trafic, le but étant toujours d'obtenir le
débit le plus élevé possible en profitant au maximum des capacités du
commutateur.
Si le fait de commuter les flots à QoS est bénéfique pour la performance
globale de l'IP switch en terme de bande passante totale, il l'est aussi
pour l'efficacité dans la fourniture des garanties de services. Le moteur de
commutation engendrant des délais bien moins élevés que le routage au niveau
IP, ces flots subiront moins de délai et auront donc besoin de moins de
ressources pour recevoir le même service, indépendamment des mécanismes mis
en oeuvre pour garantir le service demandé. Nous détaillons ce point dans
la section suivante (3.3.2).
Enfin, il apparaît clairement que RSVP et IFMP utilisant tous deux des
états relachés et transmettant des informations de noeud à noeud
le long du chemin, leur intégration peut être réalisée de manière assez
directe. L'information de redirection (i.e. un label) peut très facilement
être ajoutée aux informations de réservation et transportée dans les paquets
RESV. De cette façon, le chemin commuté s'établit en même temps que
les réservations. Il est d'ailleurs à noter que dans le cas de services à
garanties de délai (comme le GS) la séparation entre l'établissement de la
réservation et la mise en place du chemin commuté compliquerait
singulièrement les choses, les caractéristiques (déviation par rapport à un
modèle fluide, voir 2.4) des chemins routés et commutés n'étant
pas les mêmes.
Architecture d'un RSVP switch
Figure 3.3 : Architecture d'un RSVP switch
La figure 3.3 montre l'architecture du RSVP switch
ainsi défini. On y retrouve tous les éléments d'un routeur à intégration de
services (classificateur de paquets, module RSVP, ordonnanceur) et d'un IP
switch classique (module GSMP ainsi que classificateur de flots et module
IFMP pour le trafic BE). Bien entendu, le commutateur ATM doit être équipé
de mécanismes de contrôle de trafic par flot (ordonnanceur de cellules).
Modifications de RSVP
Les modifications de RSVP portent sur la syntaxe des messages et l'interface
avec le contrôle de trafic. Elles sont décrites en détail dans
[Die98], nous les décrivons succinctement ici.
Ajout de l'objet LABEL
Pour que RSVP transporte les informations de redirection, nous proposons de
définir un objet RSVP ``LABEL'' représenté figure 3.4.
Une valeur non utilisée a été choisie pour l'identifieur
(Class=40). Nous définissons le label sur 32 bits, donc
C-type=1. L'objet complet occupe 8 octets et peut contenir un label
ATM basé sur le VPI/VCI ou celui d'une autre technologie. Comme nous l'avons
dit, le label sera manipulé avec les informations de réservation, donc
transporté dans les messages RESV. Il identifie un flot de données et sera
donc placé à côté de l'objet FILTER_SPEC. Afin de maintenir la
compatiblité avec la version sans label de RSVP, cet objet est défini comme
étant optionnel dans la structure du message. Ainsi un flot pourra traverser
de manière transparente des zones avec et sans gestion des labels.
| Length (= 8 octets) sur 16 bits |
Class (= 40) 8 bits |
C-type (= 1) 8 bits |
| Label sur 32 bits |
Figure 3.4 : Objet LABEL
Une difficulté se pose avec le modèle multipoint étendu de RSVP, qui demande
des fonctionnalités de filtrage et d'agrégation (voir
2.2.4) qui peuvent difficilement être réalisées au niveau de la
couche liaison. Une solution possible est de reporter ces fonctionnalités
hors de la zone commutée, en effectuant des pre-filtrage et
post-agrégation. Le multicast n'étant pas spécifiquement notre
propos, nous ne détaillerons pas ces méthodes qui ont été décrites dans
[FF99].
Modification de l'interface avec le noyau
La communication avec le contrôle de trafic implémenté dans le noyau du
système d'exploitation se fait par l'interface suivante, définie dans
[BZB+97].
rhandle TC_AddFlowspec(OIf, FLOWSPEC, SENDER_TSPEC,
ADSPEC, flags, FLOWSPEC);
FLOWSPEC TC_ModFlowspec(OIf, rhandle, FLOWSPEC, SENDER_TSPEC,
ADSPEC, flags, FLOWSPEC);
TC_DelFlowspec(OIf, rhandle);
fhandle TC_AddFilter(OIf, rhandle, Session, FILTER_SPEC);
TC_DelFilter(OIf, fhandle);
Les fonctions TC_AddFlowspec, TC_ModFlowspec et
TC_DelFlowspec agissent sur les paramètres de l'ordonnanceur de
paquets, et les fonctions TC_AddFilter et TC_DelFilter,
sur les paramètres du classificateur de paquets. Les Flowspecs et
Filterspecs existant peuvent être référencés par des handles
retournés par les fonctions.
La gestion des labels a nécessité de légers ajouts à cette interface qui
devient :
rhandle TCrsw_AddFlowspec(OIf, FLOWSPEC, SENDER_TSPEC,
ADSPEC, flags, FLOWSPEC);
FLOWSPEC TCrsw_ModFlowspec(OIf, rhandle, FLOWSPEC, SENDER_TSPEC,
ADSPEC, flags, FLOWSPEC);
TCrsw_DelFlowspec(OIf, rhandle);
fhandle TCrsw_AddFilter(OIf, rhandle, Session, FILTER_SPEC);
fhandle TCrsw_AddFilter(OIf, rhandle, Session, FILTER_SPEC, LabelSwap);
TCrsw_DelFilter(OIf, fhandle);
LABEL TCrsw_GetLabel(IIf);
TCrsw_FreeLabel(LABEL);
L'ajout du préfixe ``rsw'' aux noms de fonctions correspond à une
interface spécialisée pour la technologie réseau RSVP switching. La nouvelle
version de TCrsw_AddFilter permet de spécifier une paire de labels
pour l'établissement du raccourci. L'espace des labels est géré par le
noyau, TCrsw_GetLabel renvoie à RSVP un label libre et
TCrsw_FreeLabel permet de libérer un label qui n'est plus utilisé.
Situation de l'approche
Étant partis d'une approche de la commutation IP orientée flot nous
avons construit une approche basée sur RSVP que nous appelons orientée
session (session driven) car basée sur les sessions RSVP.
Il peut paraître naturel de l'assimiler à l'approche orientée flot puisque
les labels sont associés aux flots de données par l'intermédiaire de RSVP.
Cependant, l'approche orientée topologie, initialement basée sur les
informations de routage a été étendue pour pouvoir tenir compte de tout type
de signalisation ce qui en fait une approche orientée signalisation
(control driven). Notre approche orientée session peut donc être
rattachée aussi bien à l'approche orientée flot (car basée sur les flots de
données) qu'à l'approche orientée signalisation (car basée sur la
signalisation RSVP).
3.3.2 Implémentation des classes de service
Efficacité du Guaranteed Service
Nous détaillons ici l'intérêt de commuter les flots demandant des garanties
de délai. Nous avons vu page ?? que le délai donné dans
la formule (2.1) est composé de deux parties. La première est
le délai d'écoulement au débit de la réservation d'une rafale de taille
maximale, la deuxième les délais ajoutés dans chaque noeud à cause des
effets de paquetisation et de serialisation. Ces deux effets sont
directement liés aux tailles de paquets3 et seront donc
considérablement réduits dans le cas d'un ordonnanceur de cellules. Le gain
sera bien entendu particulièrement important pour les flots dont la majeure
partie du délai est apporté par le deuxième terme, c'est à dire les flots à
petites rafales ou traversant un grand nombre de noeuds. Nous illustrons
ceci dans le cas de deux flots ayant pour caractéristiques respectives (p=25
Mb/s, r=300 kb/s, b=20 ko) et (p=25 Mb/s, r=300 kb/s, b=0 ko), traversant
n=10 noeuds. Le débit des liens est C=155 Mb/s. Nous comparons la
réservation nécessaire dans les cas du routage de paquets IP de 1024 octets
et de la commutation de cellules ATM (53 octets) en fonction du délai
désiré. Notez que dans ces courbes, nous ne tenons pas compte de la
condition de stabilité R > r. La réservation à affecter est donc le
maximum de la valeur donnée par la courbe et du débit moyen du flot.
Figure 3.5 : Réservation en fonction du délai désiré
Sur la figure 3.5, les deux courbes supérieures concernent le
premier flot (taille maximum de rafale de 20 ko). La majeure partie du délai
est alors dû au temps d'écoulement de la rafale et la différence entre les
cas IP et ATM est relativement faible. Par contre, pour le deuxième flot,
dont la taille de rafale est nulle, le délai dépend uniquement des tailles
de paquets et le gain est très important.
Ceci implique que pour une garantie de délai donnée, la quantité de
ressources à réserver sera (éventuellement beaucoup) plus faible dans le cas
de la commutation. La quantité de qualité de service que le réseau
peut fournir pour un dimensionnement (quantité de ressources) donné est donc
plus importante.
Le service BR : Bandwidth Recovery
Motivation
Bien que nous venions de montrer que l'ordonnancement au niveau cellule
pouvait considérablement améliorer les choses, il n'en reste pas moins
qu'avec un ordonnanceur de type weighted fair queuing la garantie de
délai est directement liée à la bande passante réservée, ce qui fait que les
flots à faible débit demandant des délais courts devront réserver beaucoup
de ressources. Avec un ordonnanceur qui découple réservation de bande
passante et garantie de délai, la réservation R est également toujours
plus grande que le débit moyen du flot r, et une quantité de bande
passante R-r est alors réservée mais non utilisée. Bien sur cette bande
passante n'est pas strictement ``perdue'' dans le sens où elle reste
disponible pour le trafic best-effort (si l'ordonnanceur conserve le
travail). Cependant, dans la mesure où elle a été réservée, sa
disponibilité est garantie et elle devrait pouvoir être utilisée pour
fournir des garanties de services à d'autres flots. Évidemment, le type de
service qu'il est possible de garantir est bien plus ``faible'' que le GS
puisque cette bande passante n'est disponible qu'en
moyenne4.
Beaucoup d'applications n'ont pas besoin de garanties strictes en terme de
délai, mais ont plutôt besoin d'un certain niveau de garantie en bande
passante. Nous pensons en particulier à toutes les applications qui ont
besoin d'une ``interactivité à échelle humaine'', c'est à dire qui ont
besoin d'effectuer leurs transferts de données en un temps ``raisonnable''
(tel que perçu par l'utilisateur). Les butineurs web ou les applications de
transfert de fichier en sont un bon exemple.
Aussi nous proposons une classe de service permettant d'utiliser ces
sur-réservations pour fournir une garantie de bande passante ``à long
terme''. L'idée de ce service est similaire à ce qui est présenté
dans [G+96]. La différence principale réside dans la façon dont
il est implémenté et dont il interagit avec le trafic best-effort.
Le type de QoS fournie par cette classe de service peut être globalement
compatible avec ce qui est requis pour la classe de service Controlled
Load. On peut dont la voir comme une implémentation possible du CL,
conçue pour être implémentée conjointement avec la classe GS de façon à
optimiser l'utilisation des ressources. Elle peut très bien cohabiter avec
une autre réalisation du CL dans le cas où la bande passante ``gaspillée''
par les flots GS ne serait pas suffisante pour satisfaire l'ensemble des
flots CL.
Réalisation
Pour implémenter cette classe de service, que nous appellerons BR (pour
Bandwidth Recovery), nous utilisons un ordonnanceur de type
Weighted Fair Queuing avec des files séparées pour chaque flot GS ou
BR. À chaque flot GS est affecté un poids qui détermine la quantité de bande
passante Ri allouée à ce flot. Supposons un lien de capacité Cl et N
flots GS chacun caractérisé par le TSPEC (bi,ri,pi). Pour
garantir le service aux flots GS, l'inégalité suivante doit être respectée :
|
|
|
|
Ri £ Cl - DBR -
DSIG
(3.1) |
Cette inégalité est illustrée sur la partie gauche de la figure
3.6. Dans l'équation précédente, DBR et DSIG représentent les portions de
bande passante réservées respectivement aux flots BR et à la
signalisation. Le poids associé au ``flot signalisation'' est basé sur
une estimation de la bande passante nécessaire au trafic de
signalisation.
Le poids associé à chaque flot BR, et donc la bande passante réservée, est
choisie volontairement très petite. Son rôle est de permettre aux flots BR
d'accéder à la bande passante réservée mais non utilisée par les flots GS.
Avec une discipline de service de type GPS, une portion de bande passante
est garantie à chaque flot, mais si certains n'utilisent pas la totalité de
ce qui leur a été réservé, d'autres flots tentant d'utiliser plus que leur
propre part se partageront alors cette bande passante. Ainsi dans notre cas
les flots GS n'utiliseront pas la totalité de leur part, et les flots BR
utiliseront plus que la leur en récupérant la bande passante ``gaspillée''
par les flots GS comme illustré sur la figure 3.6. La bande
passante ``récupérée'' est répartie équitablement (au sens de l'équité
``max-min'') entre les flots BR en fonction de leurs poids respectifs.
Figure 3.6 : Bande passante réservée et utilisée par les flots GS et BR
Considérons N flots BR avec un débit moyen égal à ri,
leur garantir un débit minimum à long terme est possible si :
|
|
|
|
ri + |
|
ri £ Cl -
DSIG
(3.2) |
L'équation (3.2) assure que si les flots GS respectent leur
contrat de trafic (ou qu'un mécanisme de polissage est utilisé), les flots
BR recevront chacun un débit minimum garanti ri sur une échelle de
temps raisonnable.
Le trafic best-effort
Comme nous l'avons dit, le trafic best-effort devra être routé
ou commuté selon les critères utilisés par les IP switches
classiques. Dans tous les cas, il sera servi à un niveau de priorité réduite
afin de ne pas influer sur le service garanti aux autres flots. Dans toute
la discussion précédente sur la réalisation des classes de service, nous
avons considéré que toute la bande passante du lien pouvait être utilisée
par les flots à QoS. Nous l'avons fait uniquement dans un souci de
simplification, il est très fortement souhaitable de réserver une partie du
lien pour le trafic best-effort ce qui pourra être fait en remplaçant
dans les équations (3.2) et éventuellement (3.1) la
capacité du lien Cl par la capacité dédiée aux flots à QoS.
L'ordonnanceur utilisé
Le schéma de l'ordonnanceur est donné en figure 3.7. Dans la
partie commutation, chacun des flots GS et BR, ainsi que la signalisation
sont traités individuellement alors que le trafic best-effort est
traité dans une seule file de priorité inférieure. Au niveau routage (c'est
à dire tout le trafic qui n'est pas commuté, soit une partie du trafic BE et
la signalisation) on traite séparément la signalisation et le trafic BE (par
exemple en utilisant des priorités) de façon à garantir le passage de la
signalisation.
Figure 3.7 : L'ordonnanceur utilisé
3.4 Évaluation de RSVP switching
Nous avons procédé à une évaluation de la solution RSVP switching selon
trois axes :
- des simulations ont permis de valider l'ordonnanceur proposé et le bon
fonctionnement des classes de service GS et BR ;
- la réalisation d'un prototype nous a permis de montrer la faisabilité des
mécanismes proposés, en particulier l'inclusion des fonctionnalités d'IFMP
dans RSVP ;
- enfin, nous avons voulu évaluer dans quelle mesure le fait d'avoir
utilisé une gestion des ressources par flot est une limitation à la
scalabilité du modèle. Le plan de contrôle étant à notre avis le plus
sensible à ce type de problèmes, nous avons effectué des tests sur le
comportement d'une implémentation de RSVP avec un grand nombre de flots.
3.4.1 Simulations pour les classes de service
Afin de valider notre proposition concernant l'implémentation de la classe
de service BR, nous avons procédé à des simulations. Le réseau
simulé (figure 3.8) est constitué de cinq RSVP switches
connectés par des liens à 51 Mb/s et implémentant les services GS et BR avec
un ordonnanceur weighted fair queuing. À chaque RSVP switch est
connectée une station qui génère et reçoit des flots. Un total de neuf flots
GS sont répartis de façon que chaque lien inter-switch soit occupé par six
flots GS. Trois flots traversent cinq noeuds, deux traversent quatre noeuds, deux traversent trois noeuds et deux traversent deux noeuds.
Figure 3.8 : Topologie du réseau simulé
Les sources sont du type ON/OFF filtrées par un double seau percé
(leaky bucket) pour les contraindre aux spécifications du type (b,r
,p) (figure 3.9). La génération des jetons se fait au débit r
pour le premier seau et p pour le second. Le premier seau a une profondeur
de b, il sert à réguler le débit moyen et les rafales, le deuxième seau a
une profonfeur de L, il joue le rôle de régulateur de débit crête. Tous
les flots GS sont caractérisés par (b=100 ko, r=3 Mb/s, p=25 Mb/s) et
demandent un délai inférieur à 100 ms. Les réservations R nécessaires pour
satisfaire ce délai sont données dans le tableau 3.1 avec le poids
associé au flot dans l'ordonnanceur et la taille de tampons nécessaires. Le
tableau 3.2 montre que la réservation des liens atteint presque
100 %.
Figure 3.9 : Le double seau percé
| longueur |
|
|
|
| du chemin |
R (Mb/s) |
poids |
B (nb. cellules) |
| 5 |
8.4603 |
0.16589 |
1804 |
| 4 |
8.4562 |
0.16581 |
1804 |
| 3 |
8.4521 |
0.16573 |
1804 |
| 2 |
8.4480 |
0.16565 |
1804 |
Table 3.1 : Réservations (R), poids (W), taille des tampons (B)
| lien |
R total (Mb/s) |
réservation du lien (%) |
| S1-S2 |
50.7372 |
99.49 |
| S2-S3 |
50.7454 |
99.50 |
| S3-S4 |
50.7454 |
99.50 |
| S4-S5 |
50.7372 |
99.49 |
Table 3.2 : Réservation des liens
À ces flots GS s'ajoutent cinq flots BR qui traversent la totalité du réseau
et ont des débits moyens de 12 Mb/s, 9 Mb/s, 6 Mb/s et 1,5 Mb/s pour les
deux derniers. Ces valeurs sont choisies de façon à pousser l'utilisation du
réseau au maximum possible, tout en respectant l'équation (3.2).
Enfin, du trafic best-effort traverse tous les noeuds.
Résultats
Les résultats des simulations sont montrés figures 3.10 et
3.11. La figure 3.10(a) montre les délais des
paquets d'un des flots GS. On constate que la garantie de délai est bien
respectée, donc que les flots BR n'ont pas eu d'impact sur la garantie des
flots GS. Alors que le délai maximum visé était de 100 ms, le maximum
effectif est de moins de 50 ms et la plupart des paquets ont subi un délai
inférieur à 30 ms. Ceci est la conséquence de l'aspect très conservateur
(conservative) des méthodes de calcul (décrites au chapitre
2) utilisées pour le calcul des bornes de délais.
La figure 3.10(b) montre le délai des paquets pour un des flots
BR. Les délais sont ici bien plus importants, mais restent tout à fait
acceptables pour les types d'applications que nous avons envisagés. Enfin,
les figures 3.11(a) et (b) montrent respectivement le débit
moyen reçu par tous les flots BR à court terme et à long terme. On voit que
le débit converge assez rapidement vers les valeurs recherchées.
(a) Délai flot GS
(b) Délai flot BR
Figure 3.10 : Délai
(a) Débit moyen BR à long terme
(b) Débit moyen BR à court terme
Figure 3.11 : Débit moyen
3.4.2 Réalisation d'un prototype
Principe de l'émulation
La réalisation d'un RSVP switch nécessite un accès de bas niveau aux
capacités du commutateur ATM, de manière à manipuler la table de commutation
et les paramètres de chaque canal virtuel. C'est normalement GSMP qui
fournit cette fonctionnalité. Réaliser une implémentation de GSMP nécessite
de pouvoir manipuler facilement la configuration interne du commutateur ce
qui n'est évidemment pas notre cas. Au moment de ce travail, il n'existait
pas à notre connaissance de matériel ATM ouvert susceptible d'être utilisé
pour notre prototype.
Nous avons donc choisi de placer dans le routeur une émulation
logicielle de la commutation. Deux chemins de traitement sont possibles
dans le routeur pour les paquets IP ; ils peuvent être routés normalement ou
``commutés'' si un raccourci est en place pour le flot concerné. Les paquets
``commutés'' évitent une partie du traitement normalement appliqué, en
particulier l'opération de routage est remplacée par une simple consultation
de la table de commutation et le paquet est placé directement dans la
file d'attente du périphérique de sortie.
Même si ce chemin raccourci peut effectivement améliorer quelque peu les
performances (en particulier si la table de routage a un grand nombre
d'entrées et que la configuration du trafic est telle que le cache de
routes n'est pas efficace), il est clair que l'on perd une grande part du
gain potentiel de performance, qui provient principalement des capacités
matérielles du commutateur ATM. Ce prototype a cependant pour but de montrer
la faisabilité et la viabilité des mécanismes proposés, et non pas la
performance globale du système. L'approche logicielle nous apporte également
plus de souplesse et de facilité de développement.
Les composants du prototype
Le prototype est basé sur du matériel de type PC standard. Il utilise le
système d'exploitation GNU/Linux [Sta98] avec un noyau
modifié, associé à une version modifiée du démon RSVP développé par
l'ISI5 (Information
Sciences Institute, University of Southern California) comme indiqué dans
le tableau 3.3.
| Composant |
Ajouts/Modifications |
| RSVP ISI 4.2a3 |
gestion des labels |
| |
interface avec le noyau |
| Noyau Linux 2.1.23 |
souche IPv6 DRET/LIP6/INRIA |
| |
``commutation'' |
| |
ordonnancement des paquets |
| |
interface de configuration (appels systèmes) |
| Outil de configuration |
|
Table 3.3 : Les composants de l'implémentation
Le noyau est Linux 2.1.23 avec la souche IPv6 expérimentale de la DRET
développée conjointement par le LIP6 et l'INRIA6 et
un gestionnaire de carte ATM ``Linux-ATM'' développé à l'EPFL (École
Polytechnique Fédérale de Lausane) [Alm96]. Les cartes ATM
utilisées sont des Efficient Networks ENI155 pour port PCI, pouvant
supporter des débits de 155 Mb/s sur fibre optique multimode. Notons qu'il
était tout à fait possible techniquement d'utiliser IPv4, le choix d'IPv6
découle de contraintes contractuelles du projet dans le cadre duquel le
prototype a été expérimenté (voir le paragaphe sur l'expérimentation, pages
suivantes).
L'implémentation
Au noyau Linux ont été ajoutées les deux fonctionnalités constituant
l'émulation de la partie commutateur :
-
le moteur de commutation,
- l'ordonnanceur de paquets.
La figure 3.12 décrit sommairement l'organisation du code réseau
dans le noyau Linux. Un paquet arrivant sur la carte réseau (1) déclenche
une interruption matérielle et la fonction netif_rx() place le
paquet dans une file de paquets (la file backlog) pour traitement
ultérieur. Périodiquement, une interruption logicielle (fonction
net_bh()) vient chercher un paquet dans la file backlog
et le passe à la couche IP (fonction ip_rcv()). Là, le paquet est
routé, puis la fonction do_dev_queue_xmit() le place en queue de
la file associée au périphérique de sortie (device) d'où il sera
extrait pour être transmis à la carte (2) par la même fonction (qui joue
donc deux rôles).
Les ajouts effectués pour assurer les fonctionnalités du RSVP switch sont
montrés figure 3.13. Lorsque qu'un paquet est extrait de la file
backlog par net_bh() pour traitement, il est passé à la
fonction rsw_rcv() qui détermine si le paquet doit être routé (il
est alors passé à ip_rcv()) ou commuté. Dans ce dernier cas, le
périphérique de sortie est déterminé à l'aide de la table de
commutation et le paquet est passé directement à la fonction
do_dev_queue_xmit() pour être placé dans une des files de
paquets du périphérique de sortie. Les paquets best-effort sont placés dans
la file de priorité basse et les paquets GS ou BR dans celle de priorité
haute. Dans ce dernier cas la fonction, au lieu de placer le paquet en queue
de file, calcule l'estampille du paquet en consultant la table ``QoS''
contenant les informations d'ordonnancement pour chaque flot et insère le
paquet dans la file triée7.
Une interface à RSVP sous forme d'appels système permet la configuration des
tables de commutation et d'ordonnancement.
Figure 3.12 : Mécanismes réseau de Linux 2.1
Figure 3.13 : Architecture du RSVP switch émulé
L'implémentation du moteur de commutation est décrite de manière détaillée
dans [FRDF98]. Pour l'ordonnanceur de paquets, l'algorithme SCFQ (cité
page ??) a été choisi pour la simplicité de calcul de la
fonction de temps virtuel.
Les modifications apportées au démon RSVP concernent l'intégration de la
gestion des labels (implémentation documentée dans [Die98]), le
portage du démon pour la souche IPv6-Linux de la DRET et l'ajout de
l'interface avec le noyau (mise en place des raccourcis et réservations).
Enfin, un outil de configuration rsw_config a été développé pour
permettre la configuration manuelle du RSVP switch (mise en place de
raccourcis et de réservations) sans passer par RSVP.
L'expérimentation
Notre prototype de RSVP switch a été utilisé dans l'expérimentation du
projet DGA/MENERT appelé DIS/ATM auquel le LIP6 participait avec le LAAS,
l'INRIA Sophia Antipolis et Dassault Électronique. Le projet consistait en
la fourniture d'une architecture réseau à haut débit avec qualité de service
pour des applications de type simulation interactive distribuée (DIS
pour Distributed Interactive Simulation).
Le réseau d'expérimentation a été bâti à partir de la plate-forme
Safir en interconnectant les réseaux des trois sites (LIP6,
LAAS et INRIA) au moyen de RSVP switches (figure 3.14).
Figure 3.14 : Plateforme d'expérimentation
Les résultats de l'expérimentation ont été assez décevants au niveau de la
qualité de service. Ceci est dû en partie à des erreurs de mise en place de
l'expérimentation et en partie aux limitations de notre implémentation de
l'ordonnanceur. L'analyse des résultats de l'expérimentation [CDD+99]
a montré que des pertes avaient lieu dans des éléments dont nous n'avions
pas le contrôle (lissage réalisé par les commutateurs ATM de raccordement au
réseau SAFIR). Il aurait donc fallu mettre en oeuvre un conditionnement de
trafic au niveau du RSVP switch de façon à limiter le débit sortant et
empêcher l'entrée en action des mécanismes de contrôle de trafic des
éléments hors de notre contrôle.
En ce qui concerne les limitations de l'implémentation, nous avions choisi
de réduire au minimum les modifications à faire au noyau Linux, qui présente
plusieurs défauts dans ce contexte :
- la gestion des fonctionnalités réseau s'effectuant par interruption
logicielle (c'est à dire plus ou moins en tâche de fond), il est difficile
de prévoir le temps écoulé avant le traitement d'un paquet. De plus, la
capacité de traitement dépendra de la charge de la machine pour les autres
tâches.
- la file d'entrée backlog pose un gros problème car on peut
difficilement différencier les paquets à ce niveau. La fonction
netif_rx() correspondant à une interruption matérielle doit se
terminer le plus rapidement possible sous peine de perturber de manière
imprévisible l'ensemble du système. De plus, comme il n'y a qu'une seule
file pour toutes les interfaces, le trafic suivant des routes différentes
est mélangé.
Enfin, le comportement d'un ordonnanceur WFQ se différencie d'un traitement
FIFO par définition en situation de congestion (instantanée ou de longue
durée), c'est à dire précisément dans une situation de surcharge de la
machine où le comportement se dégrade et l'observation est rendue délicate,
sinon impossible.
Toutefois, l'expérimentation a permis de valider fonctionnellement le modèle
RSVP switching et de montrer la bonne interopération entre zones commutées
(utilisant RSVP switching) et zones non commutées (utilisant RSVP sur un
réseau classique).
3.4.3 Étude de scalabilité de RSVP
Motivation
Le troisième aspect de l'évaluation de RSVP switching concerne les limites
de scalabilité. En effet, si nous avons adapté les mécanismes du modèle
proposé par l'IntServ au contexte d'une technologie de réseau haut débit,
nous avons conservé le principe d'une gestion de la qualité de service
par flot. La viabilité de cette approche dans le cadre de réseaux
d'interconnexion traversés par un très grand nombre de flots est sujette à
discussion. Comme nous l'avons déjà évoqué au chapitre 2, le
maintien d'états par flot est susceptible de poser des problèmes aussi bien
dans le plan de données (classification et ordonnancement) que dans le plan
de contrôle (états RSVP). Cependant dans le cadre d'une solution basée sur
la commutation IP les fonctionnalités du chemin de données sont assurées par
le matériel ATM. L'opération de classification consiste en une simple
lecture du label, et des techniques d'ordonnancement cablées de type WFQ
sont d'ores et déjà capables de traiter jusqu'à 64000 flots
[Gué98].
Il nous semble donc que c'est le plan de contrôle, c'est à dire RSVP, qui
est le plus susceptible de poser un problème de scalabilité pour
RSVP switching.
Expérimentation
La plateforme de test utilisée est composée de trois PC standards sous
GNU/Linux et est représentée figure 3.15.
Figure 3.15 : La plateforme utilisée
L'implémentation de RSVP utilisée est celle de l'ISI originale, sans ajout
de la gestion des labels. Celle-ci nous a posé de très gros problèmes pour
mener cette expérimentation. Les principales difficultés ont concerné le
nombre maximal de flots que l'implémentation peut gérer. Il s'est en effet
avéré que tel que livré par l'ISI, le démon ne peut supporter plus de 64
sessions. Repousser ces limites a constitué un travail plus que conséquent,
car de nombreuses structures de données utilisaient ces limites pour
diverses ``astuces'' de programmation de manière non documentée. Nous avons
finalement pu repousser ces limites à une valeur théorique de 524288. Limite
extrêmement théorique, car le démon utilisant de manière statique (c'est à
dire avant qu'une seule réservation soit effectivement réalisée) de grandes
quantités de mémoire dépendant de ces limites, nous avons finalement dû
utiliser une limite de 4096 flots pour obtenir un démon utilisable. Les
mêmes limitations concernent l'outil de test rtap fourni avec RSVP.
Lors des expérimentations, nous avons mesuré la charge du processeur et la
mémoire utilisée par le démon RSVP à l'aide d'un outil spécialement
développé à partir des sources de top, célèbre outil de mesure de
la charge pour Linux.
Résultats
Les deux graphes 3.16 et 3.17 montrent
l'évolution de la charge en mémoire et en temps processeur (temps de calcul
utilisé depuis de début de l'expérimentation, exprimé en
jiffies, unité de temps du noyau égale à 10 ms sur architecture
Intel) en fonction du nombre de réservations effectuées.
Dans l'expérimentation de la figure 3.16, les demandes de
réservation successives étaient espacées de deux secondes. On voit que
l'occupation mémoire est parfaitement linéaire à part une anomalie autour de
la réservation numéro 1500. La charge processeur présente quant à elle des
paliers assez étonants et son allure globale est assez peu encourageante
pour la scalabilité. Nous avons tracé les fonctions en x2 et en x3
les plus proches de la courbe expérimentale (déterminées par le logiciel
gnuplot). L'allure de la courbe de la charge processeur est plus
proche du type x3 (la courbe en x2 colle moins bien aux extrémités),
ce qui indique une charge quadratique en fonction du nombre de réservations
(la charge à un instant donné étant la dérivée de la courbe tracée).
Figure 3.16 : Test 1 -- Charge mémoire et processeur
Dans le cas de la figure 3.17, le délai entre les demandes de
réservation successives était fixé à une seconde. L'occupation mémoire
présente le même type d'anomalie mais de façon beaucoup plus importante et
pas au même moment. Elle semble cependant pouvoir à nouveau être majorée
par une fonction linéaire. Le phénomène de paliers se retrouve pour la
charge du processeur qui n'est à nouveau pas très encourageante. Sa
progression semble cependant s'infléchir quelque peu au dessus de 2500
réservations. Nous n'avons pas représenté les courbes en x2 et x3,
mais nos tests ont montré que la courbe en x3 est la meilleure si l'on se
limite aux 2500 premières réservations, tandis que la courbe en x2 est
plus satisfaisante aux extrémités.
Figure 3.17 : Test 2 -- Charge mémoire et processeur
Pour le test 1, l'allure du temps nécessaire pour établir une réservation en
fonction du nombre de réservations déjà établies, figure
3.18, conforte les résultats suggérés par la figure
3.16 puisqu'elle est elle aussi quadratique.
Figure 3.18 : Test 1 -- Temps nécessaire pour une réservation
Étant données nos réserves sur la qualité de l'implémentation de RSVP
utilisée, il est difficile de tirer des conclusions sur le protocole lui
même. Il est en effet délicat de distinguer dans nos résultats ce qui est
intrinsèque à RSVP de ce qui provient des défauts de l'implémentation.
Il semble cependant raisonnable de considérer que l'occupation mémoire est
linéaire par rapport au nombre de flots (le contraire aurait été assez
surprenant). Ces expérimentations tendent à montrer que la charge processeur
est en x2, ce qui est nettement plus problématique. Aucun des mécanismes
de RSVP ne nous semble pouvoir expliquer ce résultat, aussi est-ce peut être
dû à des défauts de l'implémentation. On notera toutefois qu'il s'agit d'une
courbe quadratique très peu agressive (le coefficient du terme en x2
étant trois ordres de grandeur plus faible que celui du terme en x, voir
les coefficients de x3 et x2 -- cette courbe est l'intégrale de la
charge instantanée -- sur la figure 3.16) ce qui tempère
quelque peu l'aspect négatif. Enfin, il faut garder à l'esprit que les tests
ne portent que sur un nombre assez réduit de réservations. Pour des
conclusions plus définitives, il serait nécessaire d'une part de mener des
tests de façon plus poussée, d'autre part de comparer les résultats de
plusieurs implémentations.
3.5 Conclusion du chapitre
Dans ce chapitre, nous avons proposé une méthode d'adaptation de
l'architecture IntServ à une technologie spécifique au haut débit, la
commutation IP. Nous avons pour cela intégré les fonctionnalités de mise en
place de réservations et de raccourcis pour obtenir un système cohérent.
L'objectif était de conserver les bases de l'architecture IntServ (notamment
sa grande flexibilité) tout en mettant à profit les capacités du commutateur
en terme de débit et de qualité de service. Les caractéristiques positives
d'un ordonnancement au niveau cellule associées avec le service BR
permettent d'envisager une utilisation efficace des ressources du réseau.
Il n'est pas possible dans le cadre d'un travail de thèse d'évaluer la
performance effective d'un tel système dont la réalisation nécessite de gros
investissements. Nous avons cependant montré, au moyen d'un prototype
utilisé dans une expérimentation, la viabilité fonctionnelle de la solution.
Dans ce travail, nous avons tenté de résoudre les problèmes liés au haut
débit sans nous préoccuper de ceux liés au facteur d'échelle. Dans le plan
de données, les limitations dépendront des capacités du commutateur dont on
peut espérer qu'elles évolueront rapidement. Au niveau du plan de contrôle,
nous pensons, appuyés par les résultats de notre étude, que les problèmes ne
sont pas si graves que l'on peut le croire, même s'il est clair que c'est là
que se trouvent les limites principales. En particulier, nous n'avons pas pu
tirer de conclusion définitive sur l'évolution de la charge processeur en
fonction du nombre de réservations, même si nous soupçonnons des problèmes
liés à l'implémentation utilisée.
Cette solution est donc plutôt destinée à des environnements haut débit
ayant besoin de qualité de service mais avec un nombre (relativement) limité
de flots. Dans les chapitres suivants, nous nous intéressons au problème du
passage à l'échelle d'une architecture à intégration de service.
- 1
- http://www.ietf.org/html.charters/mpls-charter.html
- 2
- Plusieurs granularités sont possibles pour la définition des
flots : paire d'adresses IP et ports sources/destination ou paires
d'adresses IP uniquement [NMLH97].
- 3
- Cela est vrai aussi bien
dans le cas d'un WFQ que dans toutes les disciplines à contrôle de débit
(RCS, Rate Controlled Service) [G+96].
- 4
- Dans le cas d'un flot sans rafale, la
sur-réservation dûe aux délais ajoutés par les termes d'erreur C et D
des noeuds peut être utilisée pour fournir des garanties identiques à
celles fournies par le GS. La solution est d'agréger des flots, comme
nous le décrivons au chapitre 4, section 4.5.
- 5
- ftp://ftp.isi.edu/rsvp/release/
- 6
- Des informations
sur cette souche sont disponibles à http://www-rp.lip6.fr/IPv6.
- 7
- La gestion d'une seule file de paquets
triés permet d'obtenir un comportement équivalent à des files séparées.
