2001 TH Medina Carvajal
2001 TH Medina Carvajal
2001 TH Medina Carvajal
THÈSE
présentée
PAR
TITRE DE LA THÈSE :
COMPOSITION DU JURY :
MM.
Pierre ROLIN Professeur, FT R&D Paris Directeur scientifique
Jean-Yves LEBOUDEC Professeur, EPFL Lausanne Rapporteur
Farouk KAMOUN Professeur, ENSI Tunis Rapporteur
Claude LABIT Directeur de Recherche, INRIA Examinateur
Laurent TOUTAIN Maître de conférences, ENST Bretagne Examinateur
Gerardo RUBINO Directeur de Recherche, INRIA Examinateur
Lionel THUAL Ingénieur des Télécommunications, Invité
FT R&D
Etude des algorithmes d’attribution de priorités
dans un Internet à Différentiation de Services
Résumé
Le modèle à Différentiation de Services (DiffServ) ajoute des nouvelles fonctionnalités aux routeurs de
l’Internet afin d’améliorer la Qualité de Service offerte aux flux. Des contraintes telles que la réduction du délai
d’acheminement ou le contrôle dans la distribution de ressources peuvent être satisfaites grâce aux mécanismes
proposés par ce modèle. A travers le Comportement Assuré, le modèle DiffServ introduit le concept d’élimination
sélective basée sur un niveau de priorité. D’un coté, cette notion peut être exploitée pour distribuer équitablement
les ressources réseau indépendamment du comportement des sources. D’autre coté, en utilisant des algorithmes de
codage audio/vidéo multi-couches, la notion de priorités peut réduire considérablement l’effet de pertes sur la
transmission de flux multimédia. Les travaux de cette thèse se concentrent sur la définition, simulation et mise en
œuvre de mécanismes d’attribution de priorités pour les services DiffServ de type Assuré. Quatre problèmes sont
abordés : distribution de ressources entre flux TCP hétérogènes, protection des flux adaptatifs face aux flux non
adaptatifs, protection des informations sémantiquement importantes de bout en bout et définition d’applications
conscientes des capacités DiffServ du réseau. Suite à l’analyse des algorithmes existants, ce document définit
deux nouvelles techniques d’attribution de priorités : 1) le Burst Sensitive Marker (BSM), destiné aux sources
TCP individuelles et 2) le Pro-Active Marker (PAM), destinée aux agrégats TCP aussi bien qu’aux flux UDP.
Basé sur le Comportement Assuré et sur le conditionneur PAM, un nouveau service réseau, destiné aux
applications de diffusion audio/vidéo, est proposé. Enfin, la mise en œuvre d’une application DiffServ multimédia
permet de démontrer l’utilité de ce service, des algorithmes proposés et, en général, de l’introduction de priorités
dans les réseaux de l’Internet.
Keywords: Differentiated Services Internet, Multi-layer Audio/Video transport, Quality of Service, Traffic
Conditioners, Packet Marking, Assured Forwarding.
a mis padres, Napoleón y Rocío,
a Roci, a Lili,
a Florence.
Ce travail a été financé par le Conseil
Mexicain de Science et Technologie
(CONACyT), dans le cadre du XIX
Programme de Coopération
SFERE-CONACyT.
Je souhaite en premier lieu remercier Pierre Rolin pour m’avoir accueilli au sein
de l’ENSTB, pour son support et pour la confiance qu’il m’a accordée en acceptant
de diriger cette thèse.
Je veux saluer tous ceux qui ont fait partie de l’équipe ENSTB Rennes pendant
mon séjour. Un grand merci à Gerardo Rubino, responsable de la recherche au
département RSM et membre de mon Jury; et à Gilbert Martineau, directeur du
Campus de Rennes. Merci à Oliver, Leila, Daniela, François, Pepe, Ana Carolina,
Joel, Marylin, Linas, Jean-Marie, Marie-Pierre et bien d’autres pour la superbe
ambiance de travail et l’amitié qui s’est établie entre nous.
Une grande amie et une grande source de conseil est pour moi Gisèle Cizault. Je
remercie tous les membres du G6 pour tout ce qu’il m’ont appris, pour leurs
conseils, pour la camaraderie et pour les richissimes discussions autour d’IPv6. A
tous merci.
Enfin, je souhaite remercier tous ce qui m’ont soutenu dans le plan moral et
affectif pendant ces années. A commencer par mes parents, Napoleón et Rocío qui,
en 29 ans, n’ont jamais cessé de me pousser vers le haut. Merci ma chère Florence
pour ton amour et ta confiance. Merci Roci et Lili pour être les meilleures sœurs du
monde. Olivier et Géraldine, je vous remercie pour m’avoir fait découvrir
l’inconditionnalité de l’amitié bretonne. Mil gracias Mario. Merci infiniment à tous
pour faire partie de ma vie.
Table de Matières
1. Introduction 1
1.1 Motivation 1
1.2 Historique 2
1.2.1 Lemodèle IntServ 2
1.2.2 Origines du groupe DiffServ à l’IETF 3
1.2.3 Ancienne approche: le champ ToS 4
1.3 Contexte de la thèse 4
1.4 Contenu de la thèse 5
Table de matières i
3.5 Les Services 33
3.6 Conclusion 34
Table de matières ii
5.5.4 Comportement des agrégats TCP 76
5.5.5 Perturbation provoquée par des flux UDP 77
5.6 Le Marqueur à Trois Couleurs (TCM) 79
5.6.1 TCM à débit simple 79
5.6.2 TCM à débit double 81
5.6.3 Comportement des flux TCP individuels 83
5.6.4 Importance du temps aller-retour dans la différentiation de flux TCP 84
5.6.5 Comportement des agrégats de flux TCP 85
5.6.6 Perturbation provoquée par des flux UDP 87
5.7 Conclusion 88
Bibliographie 140
Table de matières iv
Introduction
1
Le traitement différentié de paquets est un concept relativement ancien dans l’Internet. Il est
présent dès l’origine du protocole IPv4 avec le champ ToS, mais une définition trop vague a
limité son déploiement. Ce concept a été re-défini pour offrir un traitement adapté aux
besoins très hétérogènes des applications. Cette introduction présente les facteurs qui ont
mené l’IETF à la standardisation d’une architecture à Différentiation de Services. Ensuite,
elle précise le cadre dans lequel s’inscrit cette thèse et synthétise son contenu.
1.1 Motivation
L’Internet existant, fondé sur le principe du Best Effort, n’a pas été initialement conçu pour
prendre en compte les informations de Qualité de Service (QoS). Le modèle Best Effort maximise
l’utilisation de ressources tout en simplifiant l’opération des équipements d’interconnexion. Quand la
mémoire d’un routeur est saturée, les paquets arrivant sont rejetés. Les mécanismes de retransmission
de TCP recouvrent ces pertes, garantissant un transfert sans faute de bout en bout. Simultanément, les
algorithmes de Slow Start et de Congestion Avoidance, implantés dans TCP, assurent une distribution
de ressources relativement équitable [VJ88][rfc2581].
Si le comportement de TCP répond aux besoins d’applications traditionnellement majoritaires
dans le réseau comme telnet ou ftp [CL98], il est peu adapté pour la transmission des flux avec des
contraintes temporelles. Les applications de visio-conférence ou de Voix sur IP (VoIP) sont pour la plus
part basées sur le protocole UDP [rfc1663]. Ce protocole peut être utilisé pour obtenir un débit quasi
constant, mais il n’implante pas de mécanisme de gestion de la congestion. La présence de flux
non-adaptatifs affecte la performance de TCP, pénalisant les applications basées sur ce protocole. Des
mesures de contrôle sont nécessaires pour réduire l’effet que les flux non-adaptatifs, de plus en plus
présents sur le réseau, entraînent sur les flux adaptatifs.
Les mécanismes de contrôle de TCP empêchent de contrôler le partage de ressources. La
quantité de ressources accordées à un flux dépend de la capacité des liens et de la présence d’autres flux
dans le réseau. Des intérêts économiques poussent à la modification de ce comportement. Une
distribution contrôlée de la bande passante permettrait aux opérateurs de définir de nouveaux services
qui pourraient être facturés en conséquence. S’il devient possible dans l’Internet d’assurer le débit ou le
délai observés, les opérateurs seront en position d’implanter une politique tarifaire conforme aux
ressources accordées.
Chapitre 1: Introduction 1
L’évolution d’Internet pour prendre en compte les besoins des nouveaux flux et pour contrôler
la distribution de ressources se fera en modifiant, au niveau 3, les mécanismes de file d’attente dans les
routeurs ou en se basant sur les propriétés offertes par le niveau 2 (priorités dans IEEE 802.1p, classes
de services ATM) plutôt qu’en modifiant TCP. Les mécanismes de contrôle de flux de ce protocole
sont très mal compris à grande échelle, les modèles analytiques ne sont pas assez précis et la simulation
ne peut s’appliquer qu’à des petits réseaux. Comme le bon fonctionnement de l’Internet repose sur ces
mécanismes, les modifications de TCP se font très lentement. Au cours de ces dernières années, les
tentatives de faire un TCPng ont échouées [TCPng].
1.2 Historique
En réponse aux demandes d’amélioration de la QoS dans l’Internet, l’IETF créa en 1994
plusieurs groupes de travail destinés à définir une architecture à Intégration de Services. Dans une telle
architecture il est possible de garantir le taux de perte et le délai d’acheminement observés par un flux
individuel, tout en contrôlant la distribution de ressources entre les flux [rfc1663].
Le modèle IntServ, issu des travaux de standardisation, définit deux nouveaux services: Garanti
[rfc2212] et Contrôlé [rfc2211], mieux adaptés aux nouveaux besoins des utilisateurs et des
applications. Les fonctionnalités nécessaires à l’implantation de ces services a été étudiée. Les critères
de QoS IntServ et ceux des technologies de niveau 2 (ATM, liens à bas débit, IEEE802) ont été mis en
correspondance [rfc2382][rfc2688][rfc2815]. Au même temps, un protocole de signalisation, RSVP
[rfc2205][rfc2210], a été défini pour assurer l’échange des informations de Qualité de Service entre les
routeurs.
Le modèle est orienté récepteur, ce qui permet la réservation de ressources pour les flux multicast.
En échange, il a été nécessaire de déterminer un mécanisme pour assurer des routes symétriques
entre les émetteurs et les récepteurs.
Pour que la Qualité de Service puisse être garantie, des ressources doivent être réservées dans
chaque routeur. Ceci demande l’implantation de fonctions de contrôle d’accès, de classification et
de gestion de ressources dans chaque nœud du réseau.
La granularité spécifiée par le modèle permet de réserver des ressources jusqu’au niveau des
microflux (un transfert ftp, par exemple), augmentant le nombre de réservations qui doit être géré
par chaque routeur.
2 Chapitre 1: Introduction
Au niveau technique, la faiblesse principale de l’architecture IntServ est sa non-résistance au
facteur d’échelle. Le nombre de flux qui peuvent bénéficier d’une réservation est assez limité, en
particulier dans les routeurs du cœur du réseau. Ces équipements doivent traiter des milliers des flux
simultanément [CL98], et le coût introduit par la gestion d’états et l’ordonnancement par flux peut
entraîner une réduction considérable de leur performance.
Au niveau économique, la réservation de ressources est incompatible avec le système de
tarification forfaitaire habituellement utilisé dans l’Internet. Si aucun contrôle n’est effectué, un seul
utilisateur pourrait réserver la totalité de la bande passante au détriment des connexions établies par
d’autres utilisateurs. Un nouveau système de tarification, basé sur la quantité de ressources réservés,
devrait être implanté dans le réseau. Avec l’introduction du protocole COPS [rfc2748][rfc2749], une
telle action est imaginable à l’intérieur d’un domaine. Par contre, pour que le modèle puisse être
implanté à grande échelle, l’échange des informations concernant la tarification doit être sécurisé.
Malgré l’existence des standards qui définissent les modifications nécessaires pour faire de l’Internet
un réseau sécurisé [rfc1825][rfc2207], leur mise en œuvre n’est pas encore au niveau nécessaire pour
pourvoir transporter des informations si importantes que celles concernant la tarification.
La standardisation du modèle IntServ s’est pratiquement achevé en 1996. Pourtant, le modèle
n’a jamais été implanté à grande échelle dans le réseau. Les faiblesses énumérées précédemment
empêchent son déploiement. De nouvelles propositions cherchant à offrir des garanties strictes dans le
réseau sont actuellement à l’étude. Elles se basent sur une architecture hybride IntServ-DiffServ
[BR2K].
Chapitre 1: Introduction 3
1.2.3 Ancienne approche: le champ ToS
La Différentiation de Services se base sur une étiquette introduite dans chaque paquet qui
détermine le traitement que celui-ci obtiendra du réseau. Ce concept n’est pas nouveau dans l’Internet.
Dès la définition du protocole IPv4 [rfc791], le champ ToS dans l’en-tête était dédié aux informations
de Qualité de Service. Trois bits de ce champ dénotaient la précédence (priorité) du paquet, pendant que
quatre bits indiquaient la préférence pour l’un des quatre service identifiés à l’époque. La définition de
services trop vagues et une absence de contrôle font que ce champ n’ait été utilisé que par les protocoles
de gestion de réseau.
Le modèle à Différentiation de Services aurait pu se baser sur l’utilisation effective du champ
ToS, mais ceci ne satisferait pas aux attentes. D’ailleurs, les versions appelées "DiffServ" chez certain
constructeurs utilisent encore cette sémantique. Les 8 bits qui forment le ToS ne sont pas utilisés de
manière efficace, les services proposés sont plutôt liés à la sélection des routes et de nouveaux services
ne peuvent pas être ajoutés. Donc, le besoin d’un nouveau modèle est justifié.
Les travaux de cette thèse se concentrent sur la définition, simulation et mise en œuvre de
conditionneurs de trafic destinés aux services de type Assuré. Le Comportement Assuré AF, défini par
l’IETF, introduit dans le réseau la notion de priorité : la priorité d’un paquet détermine sa probabilité
d’élimination en cas de congestion. Les conditionneurs de trafic pour ce type de services sont en charge
d’attribuer une priorité à chaque paquet en fonction du comportement du flux, du contrat de service
et/ou de l’importance de l’information transportée.
Les applications de cette nouvelle capacité du réseau forment un domaine de recherche assez
vaste. Dans cette thèse nous nous sommes concentrés sur les aspects suivants:
4 Chapitre 1: Introduction
Basé sur le Comportement AF et sur le conditionneur PAM, un nouveau service réseau est
également proposé. Ce service est destiné aux applications de diffusion audio/vidéo. Grâce à la mise en
œuvre d’une application de streaming multimédia consciente des capacités DiffServ du réseau, l’utilité
des algorithmes et du service proposés est mise en évidence.
Le deuxième chapitre décrit les modules de base qui peuvent servir à la construction d’une
architecture à Différentiation de Services. D’un coté, il analyse les fonctions nécessaires à
l’identification et à la caractérisation d’un flux. D’autre coté, il présente les mécanismes
d’ordonnancement et de gestion de la congestion nécessaires dans les routeurs pour pouvoir offrir de
nouveaux services.
Le chapitre trois présente le modèle DiffServ, tel qu’il a été standardisé par l’IETF. Il
détermine le rôle des différents éléments composant l’architecture. Il montre la manière dont les
éléments de base peuvent être combinés dans les routeurs de frontière et du cœur du réseau afin de
mettre en place des Services Différentiés. Enfin, le chapitre identifie les paramètres qui doivent être
précisés lors de la définition d’un service DiffServ.
Dans le chapitre quatre, nous décrivons ADServ, notre mise en œuvre du modèle DiffServ. Par
la présentation des capacités de la souche, nous réaffirmons les concepts introduits dans les chapitres
précédents. Ce chapitre présente également le résultat des tests DiffServ effectués en collaboration avec
France Télécom R&D. Le chapitre termine par la description des tests similaires effectués dans le
groupe de travail européen TF-TANT.
La comparaison de performances de trois conditionneurs pour les services Assurés est réalisée
dans le chapitre cinq. Les marqueurs PTB (Parallel Token Buckets), TSW (Time Sliding Window) et
TCM (Three Color Marker) sont comparés dans différentes situations. La capacité de différentiation de
chaque conditionneur est mesurée pour les cas où 1) plusieurs sources TCP hétérogènes cherchent à
partager équitablement la capacité d’un lien, 2) les ressources doivent être distribuées de manière
pondérée entre plusieurs flux agrégés et 3) les flux adaptatifs doivent être protégés des sources UDP à
débit constant.
Le chapitre six contient deux propositions cherchant à augmenter le niveau de différentiation
dans un service Assuré. Nous présentons en premier le BSM (Burst Sensitive Marker), destiné à réduire
l’impact du RTT dans la performance des sessions TCP individuelles. En second, le PAM (Pro-Active
Marker), concentré sur la protection des paquets prioritaires, est introduit. En plus de résoudre les
problèmes identifiés dans le chapitre précédent, ces deux conditionneurs peuvent être utilisés dans la
définition de nouveaux services.
Chapitre 1: Introduction 5
Un nouveau service DiffServ est proposé dans le chapitre sept. En assurant un partage de
ressources équitable entre flux UDP et la protection des informations sémantiquement importantes, le
service multimédia constitue une bonne alternative pour la diffusion des flux audio/vidéo (streaming).
La description et les performances d’une application prototype, se servant du service DiffServ
multimédia, sont présentées à la fin du chapitre.
Pour terminer, le chapitre huit présente la conclusion et les perspectives de ce travail. Nous
faisons un positionnement de nos propositions par rapport à d’autres aspects concernant le réseau, la
Qualité de Service et les méthodes de codage et transmission des flux multimédia. Nous analysons les
possibles modifications qui peuvent rendre les algorithmes et services proposés dans ce rapport plus
performants. Pour terminer, nous identifions la relation qui existe entre la Qualité de Service et IPv6
aussi que le contexte dans lequel DiffServ peut être perfectionné dans la nouvelle version du protocole.
6 Chapitre 1: Introduction
Mécanismes élémentaires au traitement
différentié dans l’Internet 2
Ce chapitre décrit une série de mécanismes qui peuvent servir à la mise en œuvre de Services
Différentiés dans les réseaux Internet. En premier, nous décrivons la politique utilisée pour
identifier et caractériser un flux IP. Dans les modèles d’amélioration de QoS, seuls les flux
qui ont été identifiés et dont le comportement a été vérifié peuvent bénéficier d’un traitement
amélioré. Ensuite, nous présentons les méthodes d’ordonnancement et de gestion de file
d’attente qui peuvent être mis en place pour modifier le comportement des routeurs. La
combinaison de ces éléments forme le modèle DiffServ, décrit dans le chapitre suivant.
Le protocole IP, orienté datagramme, ne comporte pas dans sa définition la notion de flux. Ce
concept est néanmoins nécessaire à la mise en œuvre d’une architecture de différentiation. Les
équipements intermédiaires doivent être capables d’identifier les paquets IP appartenant au même
"flux", afin de leur accorder le traitement dont ils ont besoin. Si l’un des principes du modèle DiffServ
est l’agrégation, il existe toujours une première classification assez fine (qui peut avoir lieu directement
dans la station émettrice) qui identifie les microflux IP avant qu’ils soient injectés dans le réseau.
Un microflux peut représenter une connexion TCP ou un stream UDP individuel. Au sens IP,
un microflux est identifié par cinq champs dans l’en-tête [rfc2215]. Tous les paquets portant des valeurs
identiques sur ces champs appartiennent au même microflux IP. Les champs concernés sont:
Adresse source IP
Adresse destination IP
Protocole de transport (TCP, UDP, autres).
Port source (pour TCP ou UDP)
Port destination
Dans certaines situations, l’obtention de quintuple qui identifie un microflux peut devenir une
opération compliquée. Dans le modèle IPSec [rfc1825], l’en-tête du protocole de transport (TCP ou
UDP) est chiffrée et, par conséquence, illisible dans les routeurs intermédiaires. Dans le cas où cette
information soit indispensable pour la différentiation, une extension peut être définie; ce fût le cas dans
RSVP [rfc2207].
Un problème différent existe en IPv6 [rfc1752]: dans cette version du protocole la présence
d’extensions d’en-tête peut compliquer la recherche des numéros de port. Pour résoudre ce problème le
champ “étiquette de flux” peut être utilisé. Ce champ, actuellement inutile, peut servir à réduire le
pkt
r (octets/s)
pkt
b (octets)
Le traitement différentié de paquets dans le modèle DiffServ peut être décomposé en deux
axes: regroupement de flux en classes de service et introduction de priorités au sein de flux. Cette
section est dédié aux algorithmes d’ordonnancement, servant à contrôler la distribution de ressources
entre les classes de service.
Nombreux sont les ouvrages qui traitent le problème de l’ordonnancement dans les routeurs
[DKS90][BW99][GM92][GVC96][Gol94]. Plusieurs techniques ont été développées pour contrôler le
partage de ressources, pour isoler des classes de service ou encore pour réduire le temps d’attente des
paquets dans les files. Nous avons reconnu deux approches : celles qui utilisent une file d’attente
unique et celles qui utilisent plusieurs files. Cette sous-section présente les généralités de ces deux
approches et étudie leur utilité dans une architecture DiffServ.
Des mécanismes tel que WFQ [Ja96], SCFQ [Zh90] ou encore SCFQ+ [To97], se basent sur la
notion d’estampilles temporelles qui déterminent le point d’insertion d’un paquet dans une file unique.
Cette estampille est calculée à partir du poids attribué à la classe de service, de la longueur du paquet et
de l’interaction avec les autres classes actives sur le lien.
Flux 0; r0 = 2
Li0 10 25 10 10 25 15 15
A B C D E F G
Fi0 5 17.5 22.5 27.5 40 47.5 55
Flux 1; r1 = 1
Li1 10 25 10 10 25 15 15
L M N O P Q R
Fi1 10 35 45 55 80 95 110
Ordonnancement
A L B C D M E N F G O P
5 10 17.5 22. 27. 35 40 45. 47.5 55 55. 80
Figure 2.2: Ordonnancement par Fair Queueing
i 1 i i–1
F k = ---- L k + F k
rk
où Fik dénote l’estampille du l’ième paquet du flux k, rk le poids attribué au flux et Lik la
longueur du paquet. Le poids d’une classe, rk, détermine le pourcentage de bande passante que la classe
se voit attribuer. On dit que les poids sont normalisés si ∑ rk = 1 .
∀k
Dans l’exemple de la figure 2.2, le poids attribué au flux 0 est le double de celui du flux 1
(r0=2, r1=1). Par conséquent, malgré l’équivalence dans la taille des paquets (Li0 = Li1), les paquets du
flux 1 se voient attribuer des estampilles deux fois plus grandes (Fi1 = 2Fi0). L’état de la file,
représentée en bas de la figure 2.2, montre que les paquets du flux 0 sont effectivement servis en
premier. A long terme, le flux 0 doit observer un débit deux fois plus important que le flux 1.
La formule précédente présente deux défauts. En premier, elle ne prend pas en compte le temps
d’arrivée des paquets. Si un flux reste inactif pendant que d’autres évoluent, la valeur des
estampilles (Fik) est désynchronisée. Lors de son réveil, le flux se verra attribuer des estampilles de
faible valeur et obtiendra une quantité de ressources qui ne correspond pas à son poids (rk).
Deuxièmement, la formule ne prend pas en compte la présence d’autres flux, information indispensable
pour calculer la quantité exacte de ressources qu’un flux peut obtenir. Des techniques plus avancées
introduisent la notion de temps virtuel pour dénoter l’accélération du service quand certains flux ne sont
pas actifs à un moment donné.
La fonction de temps virtuel permet de définir le temps que les paquets restent dans une file
d’attente. Elle définit l’accélération du service quand certaines classes de service sont absentes. Le
temps virtuel, v(t), est calculée à partir de la formule ci-dessous, où τ et τ’ représentent un intervalle de
temps où l’ensemble de flux actifs reste constant.
1
v ( τ' ) – v ( τ ) = --------------------- ( τ' – τ )
∑ ri
r ∈ actifs
Avec cette correction, une politique de distribution de ressources équitable peut être mise en
place à l’aide de la formule:
i 1 i i i–1
F k = ---- L k + max(v ( a k ), Fk )
rk
où aik représente le temps d’arrivée du paquet. Cette formule est utilisée par l’algorithme de
L’insertion ordonnée des paquets dans une file unique est une opération coûteuse. Plus
précisément, le Fair Queueing demande un travail de O(log(n)) par paquet où n est le nombre de classes
actives dans le lien [SV95]. De plus, si les contraintes des classes de service telles qu’elles ont été
définies par DiffServ sont prises en compte, il est difficile d’imaginer l’application de ce type de
techniques dans l’architecture. Le grand inconvénient de l’approche à file unique est le manque
d’isolement des flux. Le comportement d’un flux ou d’une classe de service, peut facilement perturber
la performance des autres classes.
Le principe de Round Robin est très adapté à l’isolement de flux grâce au placement des
paquets en plusieurs files d’attente. Au même temps, les implémentations de ces techniques peuvent
être très efficaces, vu que le travail demandé par paquet n’est que de O(1) [McK91]. La figure 2.3
montre l’architecture de base du Round Robin. L’ordonnanceur parcourt en séquence les files et prend
le premier élément. Si une file est vide, l’ordonnanceur passe à la file suivante. L’équité offerte par ce
mécanisme dépend de la taille moyenne des paquets dans chaque file: une file contenant des paquets 2
fois plus gros que les autres obtient 2 fois plus de bande passante. Il est donc nécessaire de modifier
l’algorithme pour limiter le nombre d’octets que l’ordonnanceur peut retirer de chaque file afin
d’assurer l’équité.
classificateur
ordonnanceur
s o r tie
Shreedhar et Varghese définissent dans [SV95] le Deficit Round Robin (DRR). Cette technique
est une variation du bit-by-bit round robin: un modèle théorique d’ordonnancement prenant en compte
la taille des paquets [DKS90]. Dans cet algorithme, la variable quantum est chargée de limiter le
nombre d’octets débités dans chaque file lors du passage de l’ordonnanceur. Si la taille du paquet en
tête de la file est supérieure au quantum, le paquet n’est pas transmis et les jetons sont accumulés pour
être utilisés lors du prochain passage. Le pseudo-code 2.1 montre en détail l’algorithme du DRR.
La figure 2.4 contient un exemple d’ordonnancement avec l’algorithme de DRR. Les tableaux
à droite montrent l’évolution des crédits pour chaque file d’attente à chaque passage de l’ordonnanceur.
évolution de DCi
Flux 0; quantum = 15 jour avant après servi
Li0 10 25 10 10 25 15 1 15 5 A
2 20 20 -
A B C D E F 3 35 0 B, C
4 15 5 D
5 20 20 -
Flux 1; quantum = 15 jour avant après servi
Li1 10 15 10 15 25 10 1 15 5 L
2 20 5 M
L M N O P Q 3 20 10 N
4 25 10 O
5 25 0 P
Ordonnancement
A L M B C N D O P E
En introduisant la notion de poids sur les classes de service, les techniques de WRR peuvent
offrir une distribution différentiée de la bande passante. A différence des techniques de Fair Queueing
où le poids d’une classe (rk) est utilisé pour calculer l’estampille temporelle, dans les mécanismes de
Round Robin cette variable détermine le nombre d’octets à soustraire de chaque file d’attente à chaque
passage de l’ordonnanceur. Par exemple, en utilisant l’algorithme de DRR décrit précédemment, une
L’ordonnancement prioritaire, une variation du Round Robin assez simple à mettre en œuvre, a
la capacité de diminuer considérablement le délai observé par les paquets sensibles à ce paramètre.
Cette technique est sans doute la meilleure alternative d’ordonnancement pour des flux tels que la
téléphonie sur IP ou des jeux interactifs.
Dans une implémentation naïve, l’algorithme SPQ est le suivant: supposons qu’il n’existent
que 4 classes de service numérotées de 1 à 4 en fonction de leur sensibilité au délai (la classe 1 étant la
plus sensible). A chaque passage de l’ordonnanceur, la file 1 est servie. Tant qu’il y a des paquets sur
cette file l’ordonnanceur les retire pour les envoyer sur l’interface. Quand la file 1 devient enfin vide,
l’ordonnanceur traite les paquets de la file 2 et ainsi de suite. Quand un paquet arrive sur la file 1, il est
servi dès que l’interface termine la transmission du paquet en cours quelque soit sa priorité. La figure
2.5 montre un exemple d’ordonnancement par SPQ.
c la sse A c la sse B c lasse C
11
10
9
8
tem p s d’arriv ée
7
6
5
4
3
2
1
0
ordonnanceur
o rd re d e so rtie
0 1 2 3 4 5 6 7 8 9 1 0 11 12 13 14 15 16 17 18 19 20 21
Figure 2.5: Ordonnancement par Priority Queueing
Il ne faut pas confondre les mécanismes d’ordonnancement avec ceux de gestion de file
d’attente. L’ordonnancement est la fonction qui distribue les ressources entre les différentes classes de
service. La gestion de file d’attente est la fonction qui, au sein d’une même classe, détermine quels
paquets éliminer en cas de congestion. Cette section décrit deux mécanismes de gestion de file d’attente
qui peuvent être utilisés pour mettre en œuvre une politique d’élimination sélective, nécessaire pour
implanter le Comportement Assuré du modèle DiffServ (cf. section 3.4.1.3).
Traditionnellement, la politique FIFO (First-In, First-Out) est utilisée dans le routeurs. Dans ce
cas, si le débit d’arrivée est supérieur au débit de sortie, les paquets s’accumulent dans la file jusqu’à ce
qu’elle atteigne sa taille maximale. A partir de ce moment, tous les paquets arrivants sont éliminés. Si
cette méthode est la plus simple à mettre en œuvre, elle a aussi plusieurs défauts. D’abord, elle peut être
très inéquitable: des sources produisant des rafales importants risquent d’être plus pénalisées que des
sources quasi-constantes. Ensuite, il se peut qu’un grand nombre de paquets soient éliminés
consécutivement, provoquant l’entrée simultané de plusieurs flux TCP en mode de Slow Start. On parle
alors de synchronisation. Enfin, des files remplies en permanence se traduit par une augmentation du
délai observé par les paquets.
Pour résoudre les problèmes liés au FIFO, il existent des propositions
[Ja89][MS90][WC91][SA91] dans lesquelles le protocole de transmission dans les extrémités contrôle
la vitesse d’émission pour réduire la taille des files dans les routeurs. Ces solutions sont difficiles à
mettre en œuvre et leur efficacité est relative. Le meilleur endroit pour contrôler l’évolution des files
d’attente est dans le routeur même [FJ93].
RED s’attaque principalement à la congestion persistante dans une file d’attente. Sa fonction
d’élimination est basée sur la taille moyenne de la file, ce qui autorise des fluctuations instantanées
nécessaires pour le traitement du trafic très variable. Dans sa définition [FJ93], RED n’impose aucune
formule pour le calcul de l’occupation moyenne. Par contre, dans les exemples, un filtre passe bas est
utilisé comme le montre le pseudo-code 2.1:
Initialisation:
avg = 0
A l’arrivée de chaque paquet:
Si la file n’est pas vide,
avg = (1 - wq)avg + wqq
sinon,
m = temps pendant lequel la file était vide
avg = (1 - wq)mavg
La variable count compte les paquets acceptés dans la file depuis la dernière élimination.
Avec cette variable, la possibilité d’éliminer deux paquets consécutifs est réduite. Dans le code, pa
représente la probabilité de rejet du paquet. Elle augmente linéairement de 0 à pmax pendant que la
moyenne varie de thmin à thmax comme le montre la figure 2.6. A partir de thmax, tous les paquets sont
éliminés. Si les sources réduisent leur débit en conséquence, la moyenne revient rapidement à un niveau
acceptable.
Pa
pmax
avg
thmin thmax
Le WRED, originellement proposé par Cisco, se base sur l’utilisation des différents paramètres
RED pour différents flux. En attribuant un pmax et des seuils thmin et thmax différents, il est possible
d’offrir une distribution différentié des pertes [Cis99]. Cette utilisation n’est pas compatible avec le
modèle DiffServ. S’il est nécessaire de stocker des paramètres différents pour chaque flux traversant le
routeur, la méthode n’est pas résistante au facteur d’échelle.
Dans le Comportement Assuré (cf. section 3.4.1.3), le routeur doit éliminer les paquets en
fonction de leur précédence. WRED peut néanmoins réaliser cette fonction en utilisant un jeux de
paramètres pour chaque niveau de priorité.
Dans WRED, le calcul de l’occupation moyenne reste celui de RED. A l’arrivée de chaque
paquet, avg est actualisée quelque soit sa précédence. Par contre, c’est dans le calcul de pmax que la
différentiation s’effectue. La figure 2.7 montre un choix de paramètres qui pourrait servir pour
DiffServ. Pour les paquets de haute précédence (2 dans cet exemple) l’algorithme est très agressif: il ne
leur permet pas de traverser le routeur dès que la moyenne dépasse une limite relativement courte. Par
contre, pour les paquets de basse précédence (0 dans l’exemple), le mécanisme autorise des moyennes
plus élevées en partant du principe que dans des réseaux bien dimensionnés ces paquets ne doivent
jamais être éliminés.
Pa
pmax2
pmax1
pmax0
avg
thmin2 thmax2/thmin1 thmax1/thmin0 thmax0
RIO est l’un des premiers algorithmes a avoir été proposés pour effectuer la différentiation de
services. Dans sa définition [CF98], Clark et Fang ont décrit toute une architecture qui a servie de
référence aux travaux de l’IETF dans la matière. A l’origine, RIO était conçu pour différentier entre
deux niveaux de précédence (In et Out). Actuellement, le modèle a été étendu pour supporter plusieurs
niveaux.
Dans RIO, la différentiation se base en partie sur le calcul de l’occupation moyenne. A
différence de WRED, l’algorithme calcule une moyenne par précédence. La moyenne avgn est
2.5 Conclusion
Les mécanismes décrits dans ce chapitre réalisent des actions nécessaires au support de la QoS
dans le réseau. D’un coté, l’identification et la caractérisation d’un flux IP sont deux fonctions qui
peuvent être utilisées pour déterminer le niveau de conformité du flux par rapport à son contrat de
service. D’autre coté, la mise en place des mécanismes d’ordonnancement et de gestion de file d’attente
peuvent servir à satisfaire les besoins de QoS que le flux réclame.
Le placement et la configuration de ces mécanismes dans le réseau, ainsi que leurs interactions,
définissent un "modèle" de Qualité de Service. Par exemple, dans le modèle IntServ (cf. section 1.2.1),
la configuration des mécanismes est faite dynamiquement à partir des contraintes de QoS que les flux
signalent au moment de leur création. Ceci résulte en un modèle lourd qui n’est pas résistant au facteur
d’échelle. Une autre manière de s’attaquer au problème consiste à définir une configuration statique des
mécanismes suite à l’identification des besoins de QoS les plus généraux. Telle est la solution proposée
par le modèle DiffServ que nous décrivons dans le chapitre suivant.
Pour comprendre les décisions qui ont été prises par le groupe de travail, il faut se rappeler des
motivations qui ont mené à la création du modèle DiffServ; à savoir, l’incapacité de l’architecture
IntServ à se voir déployée à grande échelle et le besoin dans l’Internet des mécanismes d’amélioration
de la QoS. Si les problèmes que les modèles DiffServ et IntServ cherchent à résoudre sont les mêmes: le
traitement correct des flux multimédia et un meilleur contrôle dans la distribution de la bande passante,
le modèle DiffServ s’attaque à ces contraintes d'une manière moins ambitieuse mais plus résistante.
Dans ce modèle, il est impossible d’offrir des garanties strictes ou de réserver des ressources. Par
contre, la simplicité d'implantation permet à cette nouvelle architecture de se voir déployée
progressivement dans certaines régions de l'Internet.
Une des faiblesses du modèle IntServ est sa non-résistance au facteur d’échelle. Dans ce
modèle, tous les équipements du réseau doivent garder un état par flux réservé. Il suffit qu’un nœud
dans la route n’implémente pas les fonctionnalités IntServ pour que la QoS ne puisse plus être
strictement garantie. Dans l’architecture DiffServ, la priorité est donnée au regroupement des flux dont
les besoins sont similaires (agrégation) et à la définition des traitements nécessaires dans le routeurs
pour que l'agrégat de ces flux soit traité correctement.
Pour assurer la robustesse du modèle, la création d'états et la classification par flux sont deux
fonctionnalités réservées aux routeurs d’entrée au réseau. Dans ces équipements, le nombre de flux à
traiter est considérablement réduit et un bon dimensionnement doit suffire pour assurer que la capacité
ne soit pas dépassée. Dans le reste des routeurs des opérations très simples, ne demandant pas la
création d’états, assurent le traitement différentié.
Un autre reproche fait au modèle IntServ est la complexité du protocole de signalisation RSVP
[LI99]. Une grande partie de la lourdeur du protocole est due à la gestion des flux multicast et des
routes symétriques. La réservation de ressources pour des flux n vers m exige la définition de règles
3.2 Fonctionnement
Dans le modèle DiffServ, il n’existe pas de signalisation dans le cœur du réseau: seule une
étiquette dans l’en-tête, le DSCP (DiffServ Code Point), est utilisée pour assurer le traitement
différentié [rfc2474]. Cette capacité permet aux routeurs de garder un mode de fonctionnement
relativement simple qui n’affecte pas considérablement leur capacité d’acheminement. La complexité
est reportée sur les routeurs de frontière, se trouvant à l’entrée ou à la sortie d’un domaine [rfc2475].
Ces équipements sont chargés de déterminer la valeur de l’étiquette de chaque paquet en fonction d’un
contrat, du service demandé et des mécanismes de contrôle de trafic. Le DSCP occupe les six bits de
poids fort du champ DS (DiffServ) de l’en-tête IP. La figure 3.1 montre l’emplacement de ce champ. En
IPv4, il se substitue à l’ancien champ ToS; en IPv6, il se situe à la place du champ Traffic Class.
Source Address
13 bits
Destination Address
13 bits Destination Adress
Il est plus facile de comprendre l’utilité des divers outils qui forment le modèle si, avant
d’entrer dans les détails de l’architecture, un exemple de fonctionnement est présenté. La figure 3.2
montre une configuration de réseau très simple. Un site émetteur, souhaitant que ses flux bénéficient
d’un traitement différentié dans le réseau, établit un contrat de service avec son fournisseur. Ce contrat,
émetteur
ISP ISP
routeur de frontière
Le client peut effectuer un pré-marquage de ses flux avant de les transmettre au fournisseur. Signaler
une préférence en termes de classe de service ou indiquer l’importance relative des paquets sont
deux raisons qui justifient cette action. La priorité des paquets peut varier au sein d’un flux. Par
contre, les principes de DiffServ exigent que tous les paquets d’un même flux appartiennent à une
même classe de service afin d’éviter le déséquencement.
Le fournisseur connaît les spécifications techniques du contrat établi avec chacun de ses clients.
Quand le trafic produit par l’utilisateur arrive au routeur d’entrée du fournisseur, les flux sont
identifiés et leur comportement est vérifié en fonction du contrat respectif. En cas de
non-conformité, une action corrective est prise. Pour certains services, seuls les paquets conformes
au contrat peuvent entrer dans le réseau. Pour d’autres services, tous les paquets sont acceptés, mais
le routeur d’entrée modifie la priorité du paquet en fonction du niveau de conformité.
En quittant le routeur d’entrée, les paquets du site émetteur contiennent tous une étiquette, reflétant
la classe de service souhaitée et le niveau de conformité du flux par rapport au contrat.
Les routeurs du cœur du réseau ne modifient pas les étiquettes, ils se contentent de les utiliser pour
choisir la file d’attente où le paquet est inséré. Pour cet exemple, la file d’attente représente la classe
de service. Les ressources des routeur sont distribuées entre les files en fonction des services qu’ils
supportent. Dans chaque file d’attente, un algorithme de rejet sélectif est utilisé pour éliminer en
premier les paquets de basse priorité en cas de congestion.
Cet exemple entre un site et un fournisseur d’accès peut s’appliquer également à deux
opérateurs. En général, les paquets doivent traverser plusieurs domaines administratifs avant
d’atteindre leur destination; un accord est donc nécessaire entre domaines. Pour l’exemple précédent, le
fournisseur d’accès a aussi des contraintes à respecter vis-à-vis de son opérateur. Le routeur d’entrée est
La structure d’un routeur d’entrée peut être décomposé en 4 modules comme le présente la
figure 3.3. Toute la complexité de l’architecture est concentrée dans ce type d’équipements [model]. Ils
doivent effectuer une classification qui peut aller jusqu’au niveau du microflux. Une fois le flux
identifié, il est nécessaire de vérifier la conformité au contrat en utilisant un mécanisme adapté au
service demandé. Ensuite une action est prise pour pénaliser les paquets non conformes. Finalement,
avant d’injecter les paquets dans le réseau, la valeur du DSCP est actualisée en fonction du
conditionnement subi.
Pour que les différents flux produits par les utilisateurs puissent être traités d’une manière
différentiée, le routeur d’entrée doit tout d’abord effectuer une classification des paquets. Dans le
modèle DiffServ, cette opération est très similaire à celle définie pour l’architecture IntServ [rfc2205].
Elle se base toujours sur des champs de l’en-tête, mais le nombre des champs utilisé pour
l’identification peut varier en fonction du contrat. Dans le modèle DiffServ, la classification peut aller
jusqu’au niveau des microflux.
La classification au niveau des microflux s’effectue dans les points où les flux entrent dans le
réseau. Elle peut également avoir lieu dans un module de contrôle installé dans l’équipement de
l’utilisateur. Dans ce cas, l’utilisateur est en charge de faire la mise en correspondance entre les
applications et les classes de services. Le traffic est alors conditionné en tant qu’agrégat par le routeur
d’entrée du fournisseur.
La finesse de classification dépend du placement des routeurs d’entrée dans le réseau. Plus un
routeur est prêt du cœur, moins la classification est fine. Les flux dans ce cas peuvent être classifiés et
conditionnés, par exemple, en fonction de leur interface d’arrivée. Les routeurs du cœur du réseau
réalisent une classification beaucoup plus simple, basée uniquement sur la valeur du champ DSCP, ce
qui ne demande pas beaucoup de puissance de calcul ni de mémoire.
3.3.2 Vérification
Un vérificateur est chargé de déterminer le niveau de conformité pour chaque paquet du flux
arrivant dans le routeur. Cette valeur dépend du comportement instantané du flux et des caractéristiques
du contrat. Le nombre de niveaux varie en fonction du conditionnement requis par le service:
Pour des services à bas délai, il est nécessaire que seuls les paquets conformes au contrat soient
acceptés dans le réseau. Dans ce cas, une vérification à deux niveaux est suffisante: conforme ou
non-conforme, IN ou OUT.
Pour des services profitant de la capacité d’élimination sélective dans le cœur du réseau, un nombre
supérieur à deux augmente la granularité de la différentiation. Dans la définition du Comportement
Assuré, 3 niveaux de priorité ont été définis: vert, orange et rouge.
Le concept de conformité d’un flux est généralement associé au débit généré par celui-ci. Un
contrat de service doit contenir le débit maximal accepté pour chaque classe de service. Pour des
services ayant besoin d’une vérification à 2 niveaux, la méthode la plus simple consiste à mesurer son
débit moyen. Cette mesure peut être difficile à définir car la valeur obtenue dépend de la fenêtre
d’observation utilisée. Un autre mécanisme, simple et pourtant efficace, est utilisé dans
l’architecture DiffServ: le seau à jetons (cf. section 2.2).
3.3.3 Actions
L’action corrective à prendre pour les paquets non conformes d’un flux varie en fonction du
service. Trois types de pénalisation peuvent être identifiés: élimination, mise en forme et marquage.
L’élimination est sans doute l’action la plus sévère, mais nécessaire au bon fonctionnement de
certains services. Pour un flux dont les paquets non conformes sont éliminés à l’entrée, il peut être
souhaitable de contrôler le débit d’émission. Des flux interactifs contenant des contraintes
temporelles fortes pourraient tirer profit de ce type d’action. Dans un service DiffServ interactif, les
fournisseurs devront approvisionner leurs réseaux en fonction des contrats établis. L’entrée dans le
réseau des paquets au-delà du contrat peut faire croître les files d’attente dans les routeurs
intermédiaires et provoquer une augmentation dans le délai de transmission qui rendrait
l’interactivité impossible.
La mise en forme consiste à retarder, si nécessaire, l’acheminement d’un flux pour le rendre
conforme. Des services faisant appel a cette fonction peuvent être proposés aux clients qui n’ont pas
les moyens de l’effectuer dans leur site. La mise en forme est une action très coûteuse en termes des
ressources pour le routeur d’entrée, qui devra garder dans un tampon tous les paquets retardés
jusqu’à ce qu’ils deviennent conformes.
Le marquage1 est l’action qui attribue une précédence ou priorité aux paquets en fonction du résultat
de la vérification. Cette action introduit un deuxième niveau de différentiation, puisque les paquets
sont acheminés en fonction de leur classe de service et de leur priorité. Les fonctions de vérification
et de marquage sont parfois indivisibles. Elle forment le noyau des services basés sur le
Comportement Assuré où le traitement que le réseau accorde à un flux dépend à la distribution des
priorités à ses paquets.
1. Il ne faut pas confondre la fonction de marquage que l’on décrit ici avec l’ajout d’une étiquette par les
routeurs d’entrée. Dans DiffServ, tous les paquets se voient ajouter une valeur dans leur champ DS,
qu’ils subissent une pénalisation par mise en forme, par élimination ou par "marquage".
Une application alternative de la notion de priorités consiste à marquer les flux audio/vidéo, par
nature hiérarchiques, en fonction de la valeur sémantique de l’information transportée. Cette possibilité
est étudiée en détail dans le chapitre 7.
3.3.4 Etiquetage
Avant d’entrer dans le réseau, le champ DSCP de tous les paquets qui traversent le routeur
d’entrée est mis à jour. La valeur de cette étiquette est le résultat des opérations de conditionnement. Si
par définition il n’est pas possible de décomposer le DSCP en deux, il est tout de même possible
d’identifier les deux informations qui établissent la différentiation: la classe de service et la priorité du
paquet.
Le DSCP qui forme l’étiquette DiffServ ne doit pas être modifié par les routeurs du coeur du
réseau. Les routeurs de frontière peuvent quant à eux, modifier cette valeur lors des nouveaux
conditionnements ou d’un problème de sémantique entre deux domaines voisins.
A la suite des traitements effectués dans le routeur d'entrée, les paquets sont injectés dans le
réseau. Les opérations propres aux routeurs du cœur du réseau sont relativement simples, mais celles-ci
vont déterminer les performances du réseau, en termes de pertes et de délai, observés par les sites
terminaux [model]. L’un des objectifs du groupe DiffServ est de standardiser le traitement des paquets
dans ces routeurs en fonction du champ DS. Tous les paquets portant une même valeur dans ce champ
doivent être traités de la même manière.
Le traitement différentié dans le cœur d’un réseau DiffServ implique deux axes: les classes de
service et la notion de priorités. La figure 3.4 montre l’architecture logique d’un routeur capable
d’offrir ces deux niveaux de différentiation. Il est composé d’un classificateur, de plusieurs files
d’attente, d’un mécanisme d’ordonnancement et d’un algorithme de gestion de file d’attente pour
chaque file.
d’ordonnancement
paquet
mécanisme
classificateur
mécanismes de gestion
de file d’attente
Le classificateur que l’on trouve dans ce type de routeurs réalise une classification beaucoup
moins coûteuse que ceux qui se trouvent à l’entrée du domaine. Dans ce cas, les paquets sont
différentiés uniquement en fonction de l’étiquette qu’ils portent, c’est-à-dire, de la valeur du champ DS
attribuée par le routeur d’entrée. Une partie de cette étiquette sert à identifier la file d’attente sur
laquelle le paquet doit être inséré, pendant qu’une autre partie de celle-ci peut être utilisée par
l’algorithme de gestion de file d’attente pour améliorer la discrimination en cas de congestion.
Chacune des files d’attente dans les routeurs représente une classe de service. Leur propriétés,
en termes de bande passante ou de retard moyen observé, dépendent du mécanisme d’ordonnancement.
Les contraintes des comportements à bas délai comme le Comportement Expédié, exigent une
technique plutôt hybride, utilisant une combinaison de files prioritaires et des mécanismes de partage
de ressources comme le WFQ ou le WRR (cf. section 2.3).
Il a été mentionné dans la section 3.2 que le DSCP exprime le comportement par nœud (PHB:
Per-Hop Behavior) qui sera accordé au paquet. Un PHB est, d’après le [rfc2474], la description des
caractéristiques d’acheminement qui seront observés par tous les paquets comportant le même DSCP.
L’utilisation d’un PHB ou d’un groupe de PHBs ajoutée aux opérations de conditionnement réalisées à
l’entrée d’un domaine forment ce qui peut être appelé un service DiffServ.
Trois types de comportements ou PHBs ont été standardisés. Le seul PHB qui peut être
considéré comme obligatoire est celui des sélecteurs de classe; il a été conçu pour garder une certaine
compatibilité avec l’existant (le champ ToS) L’implantation d’autres comportements dans un réseau
dépend des besoins du domaine. La seule contrainte pour le support d’un nouveau PHB exige que les
PHBs supportés auparavant ne soit pas affectés par l’implantation de celui-ci.
Il faut remarquer que, pour chaque PHB standardisé, les valeurs de DSCP proposées ne sont
que des recommandations. A l’intérieur d’un domaine l’administrateur est libre de choisir les valeurs
qui facilitent la mise en œuvre du modèle. Ceci demande pourtant, l’implantation des mécanismes de
re-marquage à l’entrée du domaine pour faire la correspondance entre les DSCPs locaux et leurs
équivalences dans les domaines voisins.
La première famille de PHBs a été définie en même temps que l’architecture générale du
modèle. Les sélecteurs de classe (CS: Class Selectors) ont pour objectif d’assurer la compatibilité avec
l’ancienne sémantique du champ ToS. Avant l’apparition de DiffServ, le [rfc791] spécifiait déjà une
logique à suivre pour différentier les paquets IP à partir de la précédence contenue dans ce paramètre. Si
le champ ToS n’a pas été utilisé exactement comme il était prévu, son utilisation est assez répandue
dans l’Internet. Le [rfc2474] réserve donc les valeurs utilisées par l’ancienne sémantique et définit le
comportement que les routeurs devront accorder aux paquets marqués avec ces valeurs.
Les PHBs sont, par définition, des éléments indépendants qui peuvent être utilisés pour
construire des services. Pour le moment, il n’existe aucune proposition explicite qui utilise les
Sélecteurs de Classe ou l’Acheminement Assuré pour construire un service. Par contre,
l’Acheminement Expédié est une exception puis qu’il a été conçu, dès le départ, comme étant le
composant d’un service bien spécifique: le service Premium.
Le service Premium ou câble virtuel [pdb-vw][rfc2638] est destiné aux applications demandant
un délai et une gigue très faibles tel que le nécessite des applications comme la téléphonie sur IP. Il part
du principe que le délai introduit par le réseau est dû à l’attente des paquets dans les files des routeurs.
Il faut donc garantir que la taille de ces files soit presque nulle. Pour ceci il est nécessaire de mettre en
DSCP PHB
101 110 EF
Tableau 3.2: DSCP associé à EF
Avant la définition précise des PHBs, plusieurs hypothèses ont été examinées pour définir la
manière dont les routeurs devraient implanter la différentiation. D’un coté, nous trouvions les partisans
de la séparation du trafic en plusieurs classes de service. Les Sélecteurs de Classe sont l’exemple parfait
de ce type de différentiation. D’autre coté, plusieurs propositions [sima][rio] centraient la
différentiation sur les algorithmes de discrimination de paquets dans une même file d’attente.
L’Acheminement Assuré est sans doute le comportement le plus général qui existe. Il est le
résultat de la fusion de plusieurs propositions [sima][rio][rfc2638]. Il est composé de plusieurs classes
de service au sein desquelles un deuxième niveau de différentiation est introduit: les précédences. La
notion de précédence existait déjà dans la sémantique du champ ToS (mais la mise en correspondance
des précédences du ToS avec les Sélecteurs de Classe DiffServ, bien que valable, ne suit pas le même
principe). La précédence d’un paquet reflète sa priorité, c’est-à-dire, le dommage que peut entraîner sa
perte. Au sein d’un routeur cette information peut être utilisée pour améliorer considérablement la
Les définitions des services DiffServ qui peuvent être créés en exploitant la notion de
précédences est encore assez floue. Leur performance dépend énormément des mécanismes de
marquage utilisés à l’entrée ainsi que du paramétrage de l’algorithme de gestion de file d’attente. La
définition des services spécifiques basés sur AF est l’axe central de ce document.
Ce comportement, proposé par Bless et Wehrle dans [BW99], est au stade de draft à l’IETF.
Son objectif principal est de définir une nouvelle classe de service inférieure, en priorité, au Best Effort
classique. [BW99] identifie deux types de flux qui pourraient être utilisés avec ce PHB:
le trafic non-conforme d’un autre service. Dans certains services, les paquets non conformes d’un
flux sont acceptés dans le réseau. Pour les services basés sur AF, les paquets non conformes sont
marqués avec la plus basse priorité. [BW99] part de l’hypothèse que les classes AF seraient utilisées
simultanément par des flux conditionnés en 3 priorités et par des flux Best Effort (marqués par
défaut en basse priorité). Pour éviter que les flux Best Effort soient en compétition avec des paquets
dégradés des flux AF, il est proposé d’attribuer une précédence plus élevée à ces derniers.
La notion de différentiation entre les flux Best Effort est un concept qui a été bien reçu par le
groupe de travail DiffServ. Par contre, le PHB ne peut pas être utilisable dans toutes les situations
décrites dans [BW99]. Le LBE peut constituer une bonne alternative pour le traffic de fond, mais son
utilisation pour protéger les flux Best Effort des flux non conformes part d’une hypothèse douteuse. Il
n’est pas certain que des flux non conditionnés par des marqueurs à trois couleurs soient acceptés dans
les classes de service AF. Une telle action réduirait les assurances qui pourraient être offertes par les
services se servant de ces classes. La QoS observée deviendrait alors dépendante du traffic non
conditionné (Best Effort) injecté dans ces files d’attente.
Par contre, une possible utilisation du LBE qui n’est pas explicitement cité dans sa définition,
est l’amélioration des performances des flux TCP dans la classe Best Effort. En regroupant les flux non
adaptatifs dans une classe LBE, les flux TCP ne seraient plus perturbés par la non-adaptabilité de ces
flux UDP (c.f. Chapitre 7).
Deux solutions sont proposées pour implanter le LBE dans un routeur. La première consiste à
lui attribuer une classe de service dédiée, l’autre consiste à faire cohabiter les deux types de trafic dans
la même classe de service en attribuant aux paquets LBE un niveau de priorité inférieur. Dans le
deuxième cas, un algorithme d’élimination basé sur la priorité serait nécessaire dans la file mettant en
œuvre cette classe de service.
Il reste à trouver le code DSCP qui serait utilisé par le traffic LBE. Il est difficile de rendre
logique un code qui soit inférieur à celui réservé aux paquets Best Effort (000 000). La solution logique
consiste à attribuer le code 000 000 au traffic LBE et déterminer un nouveau code pour le traffic Best
Effort (000 010 ?). Ceci entraînerait de problèmes de compatibilité avec l’existant et constitue une des
raisons pour lesquelles cette proposition n’est pas plus avancée dans le processus de standardisation.
L’ABE, décrit par Hurley et Le Boudec dans [abe99], peut être vu comme un comportement
peu coûteux capable d’assurer un bas délai pour les applications interactives. S’il n’a pas été conçu
dans le cadre du modèle DiffServ, son intégration dans le modèle ne provoque aucune perturbation sur
la performance des autres composants. L’ABE offre un compromis entre le taux de perte et le délai
observés par un flux. Une source souhaitant réduire le délai observé par ses paquets sera pénalisée par
une augmentation dans le nombre de paquets perdus.
Dans l’Alternative Best-Effort, il existe deux types de paquets: verts et bleus. Ces couleurs
n’ont aucune relation avec la notation tricolore utilisée par la précédence dans les services utilisant AF.
Dans l’ABE, un flux marqué bleu observe un comportement du réseau similaire à celui d’un réseau
Best-Effort Classique; aucune garantie est faite pour le délai de transmission, mais le throughput est
maximisé. Par contre, des flux colorés verts observent un taux de perte plus important, mais un retard
de transmission réduit.
La mise en œuvre du comportement est basée sur l’utilisation de deux modules, représentés
dans la figure 3.5. Le PAC (Packet Admision Control) est un algorithme de gestion de file d’attente
basé sur WRED. Il limite le nombre de paquets à bas délai (verts) acceptés dans le nœud en fixant des
paramètres de configuration, en particulier le pmax (cf. section 2.4.1), différents pour chaque couleur. A
différence des autres algorithmes de ce type, le module PAC ajoute une fonction de boucle fermée
destinée à la mise à jour dynamique des paramètres de RED. Cette modification améliore
considérablement la performance offerte par ce comportement.
Packet
Admision
Control
drops
Le deuxième module utilisé par l’ABE est le EDFS (Earliest Deadline First Scheduler).
Comme le WFQ (cf. section 2.3.1), cet algorithme utilise une file unique ordonnée en fonction
d’estampilles temporelles. Pour assurer un bas délai aux paquets verts, leur temps d’émission (deadline)
est fixé à leur temps d’arrivée, tandis que pour les paquets bleus un delta est ajouté. Grâce à cette
opération les paquets à bas délai sont servis à l’avance, en évitant au même temps que les paquets
non-sensibles au délai soient retardés indéfiniment. Un deuxième contrôle d’accès est effectué par
l’EDFS: si le nombre de paquets à servir pendant une période donnée est si important que un bas délai
ne peut pas être assuré pour un paquet arrivant, le paquet est éliminé.
Suite à la définition des différents éléments qui conforment l’architecture DiffServ, le groupe
de travail a produit d’autres documents [model][dsmib][dspib] servant à clarifier les interactions entre
modules et les paramètres utilisés pour leur configuration et administration. Depuis sa création, le
groupe DiffServ avait refusé de travailler sur la définition de services. Désormais, tous les éléments
sont maintenant réunis et des travaux dans ce sens débutent à l’IETF.
[pdbdef] définit les caractéristiques d’un Service Intra Domaine ou PDB (Per Domain
Behavior). Contrairement aux PHBs (Comportement par Nœud), un PDB définit une combinaison
particulière d’éléments DiffServ qui peut être utilisée à l’intérieur d’un domaine pour offrir un service
dont la QoS est quantifiable. Les mécanismes de conditionnement et les comportements (PHBs)
doivent être considérés comme les composants d’un PDB, l’enchaînement de PDBs doit pouvoir servir
à la création de Services Différentiés de bout en bout. L’assurance de QoS entre deux équipements
terminaux, demandant la collaboration entre différents domaines administratifs, implique des actions
politiques et économiques qui ne concernent pas l’IETF. Il est donc imaginable que le travail de
standardisation s’arrête à ce stade, à la définition des services Intra Domaine.
Un Comportement Par Domaine est exactement défini comme étant "le traitement qu’un
1. frontière-en-frontière (edge to edge): dénote dans ce cas la partie de la route, parcourue par un flux,
appartenant au même domaine DiffServ.
3.6 Conclusion
Nous avons présenté dans ce chapitre que, dans le modèle DiffServ, le rôle des routeurs varie
en fonction de leur placement dans le réseau. Les routeurs d’entrée sont chargés de l’identification et du
conditionnement des flux. Le résultat de ces actions est inscrit en tant qu’étiquette dans l’en-tête de
chaque paquet. Dans le cœur du réseau, cette étiquette est le seul paramètre utilisé pour déterminer le
comportement des routeurs vis-à-vis des flux les traversant. Le chapitre suivant démontre, à l’aide de
notre mise en œuvre du modèle, l’utilité de cette combinaison d’éléments.
ADServ a été développé sur FreeBSD. FreeBSD est un système unix destiné aux ordinateurs PC ou
compatibles. Ce système d’exploitation est la référence en ce qui concerne la recherche sur les
protocoles de la famille IP. Le code source de FreeBSD est librement disponible dans [BSD]. L’atout
de ce système par rapport aux autres unix pour PC est la clarté du code et l’excellente documentation
des fonctions de réseau [WS95].
ADServ est un module de la souche Alt-Q. L’Alternative Queueing, Alt-Q, développé par Kenjiro
Cho, ajoute à FreeBSD la capacité de définir des nouvelles techniques d’ordonnancement en
modifiant le fonctions de file d’attente dans un grand nombre de pilotes d’interface réseau
[KC98][ALTQ]. Chaque nouvelle politique d’ordonnancement est un module indépendant qui ne
demande pas la modification d’autres fonctions. Un grand nombre de techniques sont déjà
disponibles: CBQ, WFQ, RED, RIO entre autres. Pour faciliter l’installation, ADServ est, du point
de vue de l’Alt-Q, un seul module d’ordonnancement.
ADServ a été spécifiquement conçu pour supporter IPv6. A l’origine, nous avons utilisé la mise en
œuvre de l’INRIA, développé par Francis Dupont [FDv6]. La dernière version ADServ, basé sur les
versions 3.5 et 4.1 de FreeBSD est aussi compatible avec l’IPv6 proposé par KAME [KAME],
intégré maintenant dans la distribution du système d’exploitation.
edged bboned
configuration
statistiques espace utilisateur
classification noyau
ordonnancement patch ADServ
fonctions edge fonctions bbone
flux de paquets flux de paquets
L’opération des modules edge (fonctions de routeur d’entrée) et bbone (fonctions de routeur du
cœur) est très différente. Les sous-sections qui suivent expliquent les capacités de chacun des modules
et donnent des exemples de fonctionnement. La section suivante explique les tests sur ADServ
effectués en interne aussi bien qu’en collaboration avec France Télécom R&D1.
Le module edge d’ADServ réalise les fonctions de routeur d’entrée décrites dans la section 3.3:
classification, vérification, pénalisation et étiquetage. Le module est activé à l’aide d’un démon externe
qui sert aussi à la configuration. Afin de réaliser la fonction de mise en forme de flux individuels, edge
met en œuvre un mécanisme d’ordonnancement non conservatif combinant le WRR (cf. section 2.3.2)
et l’utilisation d’étiquettes temporelles.
4.1.1.1 fonctionnement
La classification dans le module utilise de fonctions fournies par Alt-Q. Une procédure
générique est utilisée pour identifier l’en-tête de chaque paquet. La classification peut s’effectuer en
IPv4 aussi bien qu’en IPv6. Celle-ci peut aller jusqu’au niveau du microflux (adresses et ports source et
destination, protocole de transport). La description des flux à conditionner est communiquée par le
démon au moment de l’initialisation.
1. La mise en oeuvre "ADServ" s’inscrit dans le cadre du contrat de recherche CTI 96B5059 établi entre l’ENSTB et
FT R&D Lannion (anciennement CNET).
la mise en forme est destinée aux flux à bas délai. Un conditionnement de ce type se traduit par un
espacement régulier des paquets et l’attribution de la priorité la plus élevée à chaque paquet du flux.
L’élimination est une action qui permet de limiter le trafic qu’une source peut injecter dans le réseau.
A partir du résultat de vérification, les flux conditionnés par cette action peuvent observer des pertes
provoquées par le routeur d’entrée.
Le marquage par la source est une action hybride entre le marquage et la mise en forme. Avec cette
action, le flux est mis en forme avant de quitter le routeur, mais le niveau de priorité n’est pas
modifié. Cette action est utilisée pour contrôler le débit d’émission des sources multimédias tout en
respectant la priorité attribuée par l’application.
Suite aux actions correctives, la fonction d’étiquetage inscrit dans l’en-tête de chaque paquet la
nouvelle valeur du champ DS. L’étiquette est formée par la classe de service et le niveau de priorité. La
classe est indiquée par le démon de configuration et identique pour tous les paquets d’un même flux. Le
niveau de priorité est le résultat du conditionnement. La modification du champ DS demande en IPv4 le
re-calcul du checksum de l’en-tête.
L’ordonnancement dans edge suit le principe du Weighted Round Robin; assurant l’isolement
des flux. Une file d’attente est crée pour chaque flux devant subir une mise en forme. Les paquets
Best-Effort et les paquets AF partagent la même file. Pour garantir la fonction de mise en forme, une
étiquette temporelle est utilisée. Elle indique le temps de sortie du prochain paquet. La figure 4.2
illustre le fonctionnement de l’ordonnanceur. Il parcourt les files en Round Robin, si l’estampille est
inférieure au temps actuel et il existe un paquet dans cette file, le paquet est envoyé et l’ordonnanceur
passe à la file suivante. Aucune estampille n’est utilisée pour la classe Best-Effort/AF.
4.1.1.2 configuration
La mise en marche du module se fait à l’aide d’un fichier de configuration. Celui-ci contient les
informations nécessaires pour identifier les flux à conditionner et décrit les actions que chacun des flux
0.8
classificateur
1.7 WRR
1.4
2.1
concernés doit subir. A manière d’exemple, la figure 4.3 montre le contenu d’un tel fichier définissant
deux conditionneurs.
newtc video
video filter ipv6 hp2 acamas udp
video method sourcemark 150000 2000
video class 1
newtc charge
charge filter hp1 phedre-atm
charge method drop 250000 2000
charge class 0
Dans ce cas, le module conditionne uniquement deux flux. D’abord, le conditionneur reçoit un
nom, video pour le premier flux. Ensuite, la commande filter permet de spécifier les champs dans
l’en-tête servant à l’identification. Le conditionneur video agit sur tout paquet IPv6 UDP en
provenance de la station hp2 vers la station acamas. La méthode sourcemark est utilisée. Les
paquets sont mis en forme mais leur priorité est dictée par l’application. Le débit d’émission est fixé à
150 Ko/s avec une tolérance aux rafales de 2 Ko (seau à jetons [r,b] égal à [150Ko,2K]). Dans le cœur
du réseau, ce flux sera transmis sur la classe de service numéro 1 (AF1).
Le deuxième flux correspond au trafic de charge. Un générateur de trafic sur la machine hp1
injecte en permanence des paquets IPv4 vers l’interface ATM du routeur phedre. Seuls 2 Mbps
(250Ko/s) traversent le routeur d’entrée, le reste est éliminé. Ce flux est transporté sur la classe de
service la moins prioritaire, la classe 0 (BE).
Pour faciliter expérimentation, plusieurs fichiers de configuration peuvent être définis. Il suffit
de spécifier le nom du fichier à utiliser lors du lancement. Le démon edged, chargé de pilote le module
edge dans le noyau est exécuté à partir de la ligne de commande:
4.1.1.3 Statistiques
Les informations que edged peut fournir sont plutôt simples. Elles contiennent l’état des files
d’attente et le résultat du conditionnement par flux. La figure 4.4 en montre un exemple où le module
doit faire la mise en forme de trois flux et marquer deux autres (le numéro de flux dépend de l’ordre
d’apparition dans le fichier de configuration).
Les statistiques montrent, dans la partie supérieure, l’occupation instantanée dans chacune des
files (pkts_in_q), le nombre de paquets et d’octets transmis (Sent), ainsi que la quantité
d’information éliminée dû au débordement des files d’attente (Drop). Dans l’exemple, en plus des files
des trois flux mis en forme, une quatrième file regroupe les flux marqués et les paquets Best Effort.
En bas de la figure, trois indicateurs sont présentés pour chacun des flux: le niveau instantané
du seaux à jetons, le nombre total de paquets et le nombre de paquets non conformes (tagged). Dans
cette exemple, pris pendant les premiers instants d’une expérience, seuls 3 paquets du flux 5 ont été
marqués en base priorité.
Le module bbone d’ADServ offre les fonctionnalités d’un routeur DiffServ de cœur du réseau.
Dans la conception d’un tel élément il est nécessaire de choisir un mécanisme d’ordonnancement et un
mécanisme de gestion de file d’attente capables de satisfaire les contraintes du modèle. Plusieurs
possibilités ont été décrites dans les sections 2.3 et 2.4 Afin de garder un mode d’opération simple,
bbone utilise un ordonnanceur par priorité stricte (cf. section 2.3.2.2) où chacune des files est gérée par
un mécanisme RIOn (cf. section 2.4.3).
Le traitement accordé aux paquets IP dans les routeurs DiffServ du cœur du réseau dépend
uniquement du champ DS dans l’en-tête. Une classification très simple dans chaque nœud permet de
déterminer, en général, la file d’attente et la priorité qui correspondent au paquet. Dans la littérature, il
est indiqué que la mise en relation entre une valeur de DSCP (DiffServ Code Point) et un comportement
doit se faire à l’aide d’une table indexée [rfc2474]. Le module bbone ne respecte pas cette contrainte.
La sémantique utilisée par le module est présentée dans la figure 4.5. Le DSCP est décomposé en deux
champs de 3 bits. Le premier indique la classe de service (file d’attente), le deuxième dénote le niveau
de priorité. ADServ supporte donc jusqu’à huit classes de service composés par des paquets de huit
niveaux de priorité différents.
Cette sémantique, qui peut paraître non conforme au standard, reste cohérente avec les valeurs
recommandées pour chaque PHB existant. Ainsi, le PHB EF est mis en correspondance avec la classe
de service 5 et la priorité 3. Les PHBs du groupe AF occupent les classes 1 à 4 avec les précédences 1 à
3 dans chaque classe. Etant donné que la file 7 est la plus prioritaire dans l’implémentation, ADServ
satisfait la relation d’ordre entre les Class Selectors, EF, AF et le PHB par défaut (000 000).
L’architecture du module bbone est très similaire à celle du module edge comme le montre la
figure 4.6. Il existe plusieurs files d’attente, dans ce cas, chaque file représente une classe de service.
Les files sont servies en priorité stricte. Une estampille temporelle est utilisée pour limiter le débit
d’émission de l’interface. Cette capacité permet de forcer la congestion lors des expérimentations.
Suivant le même principe, une estampille est ajoutée à chaque file pour contrôler le partage de
ressources. Cette fonction sert à éviter la famine dans les classes moins prioritaires quand les files
supérieures sont saturées.
L’ordonnanceur fonctionne de la manière suivante: quand le pilote de l’interface est prêt à
envoyer un paquet, il demande au module bbone de lui fournir un paquet. Si le temps actuel est
inférieur au prochain temps de sortie établi dans l’étiquette, bbone retourne un pointeur nul. Dans le cas
contraire, l’ordonnanceur parcourt chacune des files en ordre décroissant. Si un paquet est présent dans
une des files et que son temps de service est inférieur au temps actuel, le paquet est envoyé au pilote
pour sa transmission. L’ordonnanceur sert la même file d’attente tant qu’il y a de paquets dans la file et
que l’estampille le permet.
0.3
1.8
Dans chaque file d’attente, RIOn est utilisé pour gérer l’élimination de paquets en cas de
congestion. En fonction des paramètres utilisés, cet algorithme peut servir à mettre en œuvre le
comportement de rejet sélectif requis par AF. Egalement, le choix de paramètres peut forcer RIOn a se
comporter comme le RED classique ou comme le FIFO. Lors des expérimentations, l’élimination
sélective a été activée sur les files simulant les classes AF, la gestion FIFO a été implantée pour la
classe EF, et RED a servi à gérer la congestion dans la classe Best Effort. La mise en œuvre de RIOn
dans bbone peut gérer jusqu’à 8 niveaux de priorité.
4.1.2.2 Configuration
Le module bbone est piloté par le démon bboned dans l’espace utilisateur. Il est chargé de lire
un fichier de configuration et de transmettre cette information au noyau. La configuration du module
demande la spécification du débit d’émission de l’interface et de chacune des classes de service. Au
sein de chaque classe de service, il faut déterminer les paramètres de RED (thmin, thmax et pmax) pour
chaque niveau de priorité.
config 4x3
rate 500K
La figure 4.7 en montre un fichier de configuration utilisé par bboned. Nous présentons
uniquement les lignes de configuration de deux classes: 1 et 3. La première commande, config 4x3,
où qn représente le numéro de classe et pn le niveau de priorité concerné. Les trois autres paramètres
correspondent aux paramètres de RED; à noter que la priorité de rejet maximale est indiquée par sa
valeur inversée. Les paramètres de la figure 4.7 ont été utilisés dans la mise en place d’une classe AF
(1) et d’une classe prioritaire bas délai EF (3).
Le démon bboned est lancé avec les mêmes options que son homologue edged. Il faut
spécifier l’interface sur laquelle les fonctionnalités DiffServ seront activées et, en option, le nom d’un
fichier de configuration et/ou le drapeau -S pour indiquer que de statistiques doivent être montrées sur
la console. La ligne de commande est donc:
4.1.2.3 Statistiques
Les statistiques que bboned présente reflètent l’état de chacune des files d’attente. Les
indicateurs en gras montrent des valeurs instantanées; les autres représentent des compteurs. La figure
4.8 présente les variables caractérisant les files 1 et 3, dont la configuration a été donnée comme
exemple dans la sous-section précédente. Le démon montre instantanément le nombre de paquets dans
Q (Queued) montre le total de paquets acceptés dans la file pour ce niveau de priorité.
E (Early Discard) indique combien de paquets ont été éliminés aléatoirement (quand la valeur de
avg varie entre thmin et thmax).
F (Forced Drop) montre la quantité d’information qui a été éliminé dû à une congestion permanente
dans la file (quand avg dépasse thmax).
L’exemple de la figure 4.8 montre l’état des indicateurs suite à la transmission d’un flux MPEG
vidéo IPv6 sur la file 1. L’algorithme RIO3 dans cette file a permis d’éliminer les paquets de basse
priorité (contenant des trames B) quand les ressources étaient insuffisantes pour transporter l’intégralité
du flux. Il est possible d’apprécier que plus de 90% de paquets de priorité 1 sont discriminés. L’utilité
de cet approche est décrite dans le chapitre 7. Les paquets dans la classe 3 correspondent au trafic de
contrôle qui a servi à piloter le serveur vidéo.
Une série d’expériences ont été menées entre l’ENST Bretagne et FT R&D afin de valider les
fonctionnalités d’ADServ. La figure 4.9 expose la topologie. Il s’agit d’une plate-forme distribuée entre
FT R&D Lannion et FT R&D Rennes. Un PVC ATM à 4 Mbps a été réservé dans le réseau Emeraude
(France Télécom) pour interconnecter les deux sites. IPv6 a servi au transport de l’information; les
interfaces ATM du cœur du réseau n’ont pas été configurées en IPv4. Par conséquence, tous les tests
dont les résultats sont présentés dans cette section ont été réalisés avec la nouvelle version du protocole.
La plate-forme est composée par cinq stations PC exécutant FreeBSD 2.2.7. La première
version d’ADServ (v 1.0) est installée dans chaque équipement. La station Lannion_h1 est la plus
importante de la plate-forme: elle réalise simultanément les fonctions de serveur (générateur de trafic
utile) et celles d’un routeur d’entrée. Lannion_atm exécute bboned en permanence pour se
comporter comme un routeur du cœur du réseau. Les performances sont mesurées par Rennes_h1, la
station réceptrice.
Trois types de tests on été réalisés. Nous présentons les résultats dans les sous-sections
suivantes. Dans chaque test, le trafic utile partage le lien avec un flux de charge, qui varie de 0 à 5
/DQQLRQBDWP 5HQQHVBDWP
FKDUJH
HGJHG
6(59(85 &/,(17
5HQQHVBK
/DQQLRQBK
Mbps. Le type de trafic produit par le serveur change en fonction du paramètre à analyser. Pour chaque
expérience, quatre situations ont été étudiées. Le tableau 4.1 met en relation les situations étudiés, le
type de trafic produit et l’algorithme concerné pour le cas en question.
1 BE BE Internet Actuel
2 AF/EF BE Priority Queueing
3 AFin AFin RED
La situation 1 sert de référence. Normalement les résultats les plus mauvais doivent apparaître
quand la différentiation n’est pas activée. Dans la situation 2, l’isolement des flux en deux classes de
service différentes (charge dans la file Best-Effort, trafic utile dans une file supérieure) permet de tester
notre mise en œuvre du SPQ (cf. section 2.3.2.2). La situation 3 sert à démontrer que la mise en place
de RED dans un routeur peut ne pas suffire pour améliorer les performances en cas de congestion.
Enfin, la dernière situation met à l’épreuve RIOn, en faisant cohabiter les deux flux dans la même file
d’attente mais avec une priorité différente pour chaque flux. Cette situation est la plus utile pour nos
travaux: en validant la cohérence de l’algorithme de discrimination sélective, nous pouvons nous
consacrer à l’étude des mécanismes de marquage dans les routeurs d’entrée.
Dans la première version d’ADServ, seuls deux niveaux de priorité étaient possibles. Pour
mettre à jour les résultats, une partie des simulations concernant les situations 3 et 4 ont été répétées en
local dans la plate-forme de l’ENST. Dans ce cas, une nouvelle version d’ADServ (v 2.0), mettant en
œuvre le marquage à trois niveaux, a assuré le traitement différentié.
Le délai est la première variable de QoS qui a été étudiée. Un délai réduit est indispensable aux
services interactifs, comme le service Premium. Dans le document définissant le Comportement
Expédié [rfc2598], il est proposé de réserver une file prioritaire au trafic EF. Dans ADServ, le seul
algorithme d’ordonnancement disponible (pour le moment) est précisément le SPQ. La souche est donc
adaptée pour le traitement des PHBs à bas délai. Les résultats dans la figure 4.10 en sont la preuve.
Pour ce premier test, une série de paquets ICMPv6 font l’aller-retour entre l’émetteur et la
destination. Grâce à la commande ping, il est possible de mesurer le délai moyen observé par le flux.
L’expérience a été répétée pour plusieurs tailles de paquets. La figure 4.10 montre le comportement
observé pour chacune des quatre situations.
118289 217800
50000
1
45000
40000
35000
30000
BE/BE
delay (us)
AF/BE
25000
AFi/AFo
3 AFi/AFi
20893
20000
18777
17155
15000
13416 4
11705
10000 9145
6585
6594
5950 5966
5000 5250
4788
4819.5 5024
4961 5337
4615
4550
2
0
0 1 2 3 4 5
Charge (Mbps)
Le délai observé par les paquets quand la charge est faible est d’autour de 5ms. Quand le trafic
de charge dépasse 50% de la capacité du lien, le délai augmente différemment pour chaque cas étudié.
La figure 4.10 montre les avantages du SPQ pour conserver cette valeur stable malgré les variations
dans la charge: le retard observé par le trafic AF/EF n’augmente pas plus de 3ms dans la situation 2. Au
delà de 2Mbps de charge, les mesures montrent des valeurs très importants pour l’Internet actuel dû à la
saturation de l’interface.
En ce qui concerne les tests sur le cas 3, le délai est multiplié par 4 quand seul RED réagit à la
congestion. Dans cette situation, des pertes sont observées aussi, mais le délai maximal d’un paquet
accepté dans la file ne dépend plus de la longueur physique de la file, mais du seuil maximal (thmax)
configuré pour RED.
Enfin, pour le cas 4, le flux prioritaire (AFin) est aussi affecté par la charge, mais les
conséquences sont moins importantes. RIO limite le nombre de paquets rouges (AFout) dans la file. En
moyenne, le nombre de paquets basse priorité est limité par thmax{rouge} (le thmax vu par les paquets de
basse priorité). Pour assurer la discrimination différentiée, cette valeur est en général assez basse. Ce
Le deuxième test concerne le pourcentage de paquets perdus par un flux DiffServ en fonction
de la congestion. Dans ce cas, le serveur de données produit de paquets à débit constant (1 Mbits/s)
pendant la durée du test. Les générateurs ttcp et gen61 ont servi à la réalisation de cette expérience.
Pour concentrer l’analyse sur les pertes, la transmission est faite en UDP. La figure 4.11 montre une
synthèse des résultats.
1
100 100 100
90
3
80 81
75
65
taux de perte (%)
60
BE/BE
AF/BE
AFi/AFo
AFi/AFi
40 40
26
4
20 20
12
9
7
2
0 1 1 1 1 1 1
0 1 2 3 4 5
Charge (Mbps)
La figure 4.11 montre que, pendant des périodes de congestion importante, le taux de pertes
subi par le flux de données dans les situations 1 et 3 est très élevé. Pour le cas du Best-Effort, une charge
supérieure à la capacité du lien résulte en une perte de 100% du trafic utile. La mise en œuvre de RED
permet de réduire ce pourcentage à 80%, mais la non adaptabilité du trafic de charge limite les
bénéfices de l’algorithme. Le meilleur résultat est observé quand les deux types de trafic sont isolés
(situation 2), la présence du trafic de fond ne perturbe pas le flux de données. Enfin, dans la situation 4,
les pertes s’élèvent à 20% en cas de congestion extrême. Dans ce cas, la saturation instantanée de la file
d’attente provoque l’élimination de paquets de haute priorité. Il faut conclure que l’efficacité de RIOn
dépend du niveau de congestion; d’où l’importance d’un bon dimensionnement pour ce type de services
différentiés.
1. gen6 est un outil développé à l’ENST qui est distribué avec la souche ADServ. Avec ce logiciel il est possible de
produire un flux UDP IPv4 ou IPv6 à débit constant. Le module client de gen6 est capable de mesurer le débit à
l’arrivée et le taux de pertes.
Le dernier cas d’étude lors de nos expérimentations concerne le débit qu’une connexion TCP
peut atteindre dans un réseau DiffServ. Le comportement de TCP est directement lié au taux des pertes,
il est aussi dépendant de la distribution de ces pertes dans le temps. Pour les services de type AF, la
configuration du marqueur à l’entrée du réseau est cruciale pour les performances de la session. En
particulier, la taille des seaux à jetons, en limitant la rafale maximale acceptable, va limiter les périodes
pendant lesquelles le débit de TCP augmente de manière exponentielle.
Pour ce test, un flux TCP a été produit avec ttcp et ftp. Un marqueur à trois couleurs, le
trTCM (cf. section 5.6.2), configuré avec rc = 125 Ko/s, rp = 180 Ko/s, est utilisé dans la situation 4. La
taille des Token Buckets est fixée à 1,5r octets. La figure 4.12 résume les résultats de l’expérience.
2500
2350
2213
2256
2199 2200
2
2186 2176
2000
1922
1860
1814
1631
1500 3
throughput (Kbps)
633
500 521
1 3
97
74
0 19
13
0 1 2 3 4 5
Charge (Mbps)
Les expériences DiffServ sont réalisées dans le réseau expérimental TEN-155; des circuits
virtuels ATM à 2 Mbps interconnectant les sites concernés. Des routeurs Cisco 7200, exécutant une
version expérimental de l’IOS (12.0 (6.5)T7), assurent le traitement différentié des paquets. L’étendue
de la topologie dépend des paramètres à mesurer. La figure 4.13 montre une abstraction de la topologie
utilisée pour la plupart des tests. En général, les fonctionnalités DiffServ sont analysées dans un seul
Sm artBits
routeur. Pour les tests sur EF, le trafic est produit et reçu par un Smartsbits 200. Cet équipement
spécialisé, étant la source et la destination du trafic, permet de calculer avec précision le délai et la
gigue observés par les paquets. Un flux de charge, produit à un debit supérieur à la capacité du lien,
partage l’interface de sortie avec le flux de données. Dans le Cisco 7200, il est nécessaire qu’une
interface soit en congestion afin d’activer les fonctions de différentiation de service [Cis99].
D’après sa définition [rfc2598], le Comportement Expédié peut servir à la mise en place d’un
service offrant un taux de pertes, un délai et une gigue très faibles. Le groupe TF-TANT a analysé le
comportement de ces paramètres dans plusieurs situations; ce qui a permis d’identifier les facteurs qui
peuvent provoquer une réduction de la QoS pour les services basés sur ce PHB. Dans les sous-sections
suivantes nous rappelons les résultats et les conclusions du groupe de travail pour chaque critère étudié.
Pour la mise en place du service EF il faut, dans un premier temps, déterminer les paramètres
de configuration offrant les meilleurs performances. Le délai observé par les paquets dans un réseau IP
dépend en grande partie du temps d’attente dans les files des routeurs. De la mise en œuvre des files
d’attente et de la politique de service de ces files dépendent les garanties qui peuvent être offertes aux
flux EF par un routeur. Pour le cas du routeur Cisco 7200, il faut considérer que, suite aux traitements
de QoS, tous les paquets sont insérés dans une file unique avant leur transmission. La bonne
configuration de cette file est un facteur clé dans la mise en place du service.
Les résultats des tests montrent que la file de transmission doit être réduite pour modifier le
moins possible les traitements DiffServ. Etant donné que la longueur de la file de transmission du Cisco
est exprimée en particules de 512 octets, la valeur optimale utilisée dans les tests EF a été fixée à 5
particules. Si, une file plus longue avait été utilisée, le délai et la gigue observés par les flux auraient
augmenté considérablement [TF1].
Un autre facteur lié à la configuration est le choix d’un algorithme d’ordonnancement adapté.
Pour le routeur concerné (Cisco 7200), deux choix sont possibles: WFQ et SPQ (cf. section 2.3). Le rfc
2598 montre, par simulation, que le deuxième choix répond mieux aux besoins du service. Le groupe
TF-TANT a cherché à valider cette conclusion.
Pour le WFQ, il a été nécessaire de trouver des paramètres de configuration adaptés. Avec cet
algorithme, le débit de service Sr dépend du poids attribué à la file wq et de la longueur du paquet L.
Il a été trouvé qu’un surdimensionnement de wEF (le poids accordé à la file EF) diminue le délai.
Pour la réalisation du test, wEF a été fixé à 5wBE, où wBE est le poids accordé à la file Best Effort.
Dans le Priority Queueing, aucune configuration n’est nécessaire, un paquet de la file prioritaire est
servi dès que l’interface termine de transmettre le paquet en cours. Par conséquence, le délai observé
par un paquet EF est limité au temps de transmission d’un paquet de la taille du MTU.
Les résultats de la comparaison sont présentés dans la figure 4.14. Elle montre le délai observé
en fonction de la taille des paquets EF. Avec le Priority Queueing, l’augmentation dans le délai
correspond uniquement à l’augmentation du temps de transmission liée à la taille des paquets. Par
contre, avec WFQ, dû à la prise en compte de la taille dans le calcul de l’étiquette temporelle, le délai
observé par un petit paquet et un gros paquet est multiplié par 8. Il existe donc un relation directe entre
le délai est la taille des paquets EF indépendamment de l’ordonnanceur utilisé. En ce qui concerne la
variation du délai (la gigue), des résultats similaires ont été observés [TF2].
PQ
4000
W RED
3500
3000
délai (usec)
2500
2000
1500
1000
500
0
64 128 256 512 1024
t a ille d e p a q u e t E F ( o c t e t s )
Quand la configuration d’un routeur reste fixe, la QoS offerte aux paquets EF dépend de la
nature du trafic. Pour les services sensibles au délai, le temps nécessaire à la transmission des paquets,
indépendamment de leur classe, affecte la QoS observée. Dans le Priority Queueing, un paquet EF est
inséré dans la file de transmission dès que possible. Si l’interface commence à transmettre un paquet
juste avant l’arrivée du paquet EF, il faut attendre L/Sr avant l’émission du paquet prioritaire. Il existe
donc une relation directe entre le retard subi par les flux prioritaires et la taille des paquets; que ce soit
des paquets prioritaires (LEF) ou des paquets appartenant à d’autres files d’attente (LBE).
Les tests ont vérifié cette évidence. Le délai de transmission est proportionnel à LBE et à LEF.
D’ailleurs, la file de transmission dans le routeur utilisé (cf. section 4.3.1.1) augmente la perturbation
que provoquent les paquets BE de grande taille. En ce qui concerne la gigue, la taille des paquets est
aussi importante: si LEF reste fixe, le délai est linéairement proportionnel à 1/2LBE. Dans la topologie
étudiée, l’augmentation dans le débit du flux EF fait grandir la file de transmission du Cisco, ce qui ne
va pas sans conséquence pour la gigue observée [TF1].
Dans une architecture DiffServ, les flux conditionnés à l’entrée convergent et divergent dans
plusieurs points du cœur du réseau. Les flux EF en provenance de différentes interfaces ne forment
qu’un seul agrégat dans l’interface de sortie d’un routeur. Dans TF-TANT, une topologie formée par 4
sites émetteurs a été mise en place pour étudier l’effet de cette agrégation. Au passage d’un flux EF de
référence dans chaque routeur, d’autre flux s’ajoutent pour partager avec lui (et la charge) les ressources
dans le lien de sortie. La figure 4.15 montre la topologie utilisée.
Les résultats des cette expérience sont très intéressants. Ils ont permis de démontrer que des
contrôles supplémentaires sont nécessaires pour assurer qu’aucun paquet EF ne soit perdu. Dans le cas
étudié, la convergence de flux vers la même interface de sortie provoque des rafales qui ne peuvent pas
toujours être absorbées par la file d’attente prioritaire. En plus, l’élargissement de la file augmente le
délai et la gigue observés par le flux EF de référence.
12 .00 18 0
1 flux
4 flux
17 0
8 flux
10 .00
12 flux
16 0
16 flux
8.0 0 20 flux
15 0
délai (msec)
délai (usec)
14 0
6.0 0
13 0
4.0 0
12 0
11 0
2.0 0
10 0
64 12 8 25 6 51 2 10 24 12 80 15 18
0.0 0
taille du packet E F (octets)
20 30 40 50 60
taille de paquet E F (octets) a gré g atio n et con g estio n a gré g atio n n i a grég a tio n , n i co n ge stio n
Le graphique gauche de la figure 4.16 montre qu’à cause de l’agrégation, le taux de pertes d’un
flux EF peut atteindre 11,5% pour un agrégat composé par 20 sources individuelles. Si l’on considère
que l’arrivée d’une rafale de paquets EF dans un routeur ne peut que s’agrandir dû aux nouveaux flux
qui sont produits par chaque nœud, ce résultat catastrophique est plutôt compréhensible. Les tests ont
montré que le taux de pertes dépend du nombre de flux composant l’agrégat et non du taux
d’occupation des flux EF.
Enfin, en ce qui concerne le délai, le graphique droit de la figure 4.16 présente le retard observé
par 4 flux EF en présence ou non de charge et/ou d’agrégation. Contrairement au taux de pertes, le délai
n’est pas affecté par l’agrégation (à noter que seuls 4 flux composent l’agrégat). Par contre, le nombre
de nœuds traversés pénalise la QoS en cas de congestion. Il a été trouvé que le délai est en grand partie
introduit par la file de transmission dans chaque routeur Cisco. Des résultats différents pourraient être
obtenus si d’autres équipements, ne mettant pas en œuvre cette file d’attente, étaient utilisés.
A présent, le groupe TF-NGN (successeur de TF-TANT) prépare une série de tests sur le
Comportement Assuré dont le but est de proposer des services basés sur ce PHB. Il est prévu de réaliser
une comparaison entre WRED et RIO (cf. section 2.4), d’analyser les effets de l’agrégation, du
re-marquage et du RTT dans TCP entre autres. Pour l’instant, un seul test sur AF a été effectué.
Le premier aspect qui doit être vérifié lors de la mise en place des services assurés est la
capacité des routeurs à éliminer les paquets en fonction de leur priorité. Deux algorithmes capables de
réaliser cette fonction ont été présentés à la fin du premier chapitre. Au niveau pratique, seul WRED est
disponible dans les équipements Cisco.
Le test qui a été réalisé consiste à mesurer le taux de pertes par couleur d’un flux UDP
traversant un routeur Cisco 7200 en congestion. Le module CAR est activé dans l’interface d’entrée
pour marquer le flux et obtenir la distribution de couleurs présentée dans la figure 4.17. Dix
distributions différentes ont été étudiées. La capacité d’acheminement du routeur est de 2000ko/s, le
flux émet à 3000ko/s. Le taux de perte global est de 33%. Dans le cas idéal, la totalité des paquets de
basse priorité (rouges) doit être éliminé en premier. Si la congestion persiste, c’est au tour de
l’information marquée en priorité intermédiaire (orange) de céder leur place. Dans le dernier cas étudié,
un résultat idéal est observé si la totalité des paquets de haute priorité (verts) arrivent au récepteur et
aucun paquet de priorité intermédiaire.
3500
débit d'émission (ko/s)
3000
2500
rouge
2000
orange
1500
vert
1000
500
0
1 2 3 4 5 6 7 8 9 10
WRED a été configuré dans l’interface de sortie à partir des paramètres du tableau 4.2. Dans le
Cisco 7200, la file WRED est plutôt courte, 64 paquets. Les paramètres de configuration ont été choisis
en fonction de cette contrainte. Dans ce premier test, la priorité maximale de rejet (pmax) est faible pour
les trois priorités, concentrant la différentiation sur le placement des seuils (thmin et thmax).
La figure 4.18 montre le résultat de l’expérience. Elle compare le débit transmis et le débit reçu
pour chaque priorité. Le comportement de WRED n’a pas satisfait les besoins du Comportement
Assuré. Tant que la somme du trafic vert et orange ne dépasse pas 75% de la capacité de la ligne,
l’élimination répond aux attentes. Par contre, si le trafic haute priorité augmente, un taux de pertes
rouge 9 18 0.1
orange 18 36 0.1
vert 36 64 0.1
Tableau 4.2: paramètres WRED dans le Cisco 7200
assez important est observé. Dans la situation 10, la probabilité de perte des paquets verts est de 50%,
très loin du cas idéal. Même situation pour l’information marquée orange: le débit d’émission et de
réception auraient dû être égaux jusqu’au cas 6; néanmoins, dès le cas 4 cette partie de l’information
subit déjà 30% de perte.
1 2000
vert orange rouge
1 0000
8000
6000
4000
2000
0
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Le comportement observé peut être provoqué par un mauvais choix de paramètres de WRED
ou par une mauvaise configuration des seaux à jetons utilisés pour marquer le flux à l’entrée. Des
nouveaux tests, basés sur d’autres configurations, sont en cours. Dans le cas où il serait impossible de
trouver le comportement requis par AF, une recommandation devra être prononcée pour inciter les
constructeurs à mettre en œuvre l’algorithme RIOn, qui a déjà fait ses épreuves lors de nos expériences
avec ADServ.
4.4. Conclusion
5.1. Motivation
Les besoins des flux traversant l’Internet sont très hétérogènes. Pour des flux temps-réel, le
délai de transmission doit être minimisé. Pour des flux de transfert de fichiers, il est préférable de se
concentrer sur la distribution de la bande passante. Dans la définition du Comportement Assuré, aucune
restriction sur le temps maximal d’acheminement n’est établie (cf. section 3.4.1.3). Les services basés
sur AF ne peuvent donc offrir aucune garantie sur le délai. Le service Premium peut servir à contrôler
aussi bien le délai que le partage de ressources, mais il faut signaler qu’il s’agit d’un PHB coûteux (cf.
section 3.4.1.2). Une bonne utilisation des mécanismes proposés par DiffServ consiste à satisfaire les
besoins des flux temps-réel en utilisant l’Acheminement Expédié et à contrôler la distribution de la
bande passante grâce aux méthodes propres au Comportement Assuré.
Le Comportement Assuré définit quatre classes de service. La notion de classes combinée aux
algorithmes de partage de bande passante (WFQ, WRR) peuvent servir à partager la capacité d’un
routeur, mais le nombre réduit de classes limite la différentiation qui peut être offerte avec cette
méthode. Dans l’Acheminement Assuré un deuxième niveau de différentiation est possible grâce à la
présence de trois niveaux de priorité dans chaque classe de service. Ses deux axes de différentiation
font de l’AF un comportement très général qui peut être utilisé pour implanter un ensemble de services.
Néanmoins, le traitement dans le cœur du réseau étant fixé, c’est dans la définition des conditionneurs
de trafic à l’entrée du réseau que des nouveaux services peuvent être proposés.
Un conditionneur de trafic pour un service AF doit assurer deux fonctions: 1) la mise en
correspondance entre les flux et les classes de service; et 2) l’attribution d’un niveau de priorité à
chaque paquet en fonction du comportement du flux. Si la distribution de ressources entre les classes de
service dépend de la politique d’ordonnancement, la bande passante accordé à chaque flux au sein
d’une même classe dépend du mécanisme d’attribution de priorités. Afin de définir des algorithmes
capables de calculer une priorité pour chaque paquet d’un flux, il faut commencer par identifier le
comportement des protocoles de transport utilisés par les connexions.
Dans ce chapitre, nous étudions différents politiques d’attribution de priorités. Nous nous
concentrons dans leur capacité de contrôler le partage différentié de la bande passante aussi bien pour
des flux individuels que pour des agrégats de flux. Nous analysons quatre situations:
Nous présentons dans la section suivante les performances du réseau pour chacune des
situations identifiées quand les mécanismes DiffServ ne sont pas utilisés. Ensuite, nous décrivons trois
algorithmes qui ont été proposés pour contrôler le partage de ressources et observons leur performance
dans chacun des cas. Un des algorithmes étudié est le Marqueur à Trois Couleurs (TCM: Three Color
Marker), seule proposition bénéficiant actuellement du statut de RFC à l’IETF.
Nous avons utilisé le simulateur NS [ns2] pour étudier la distribution de ressources dans
l’Internet existant. Une topologie plutôt simple a été retenue pour faciliter la comparaison des
performances entre les différentes propositions. Des situations plus complexes sont étudiées dans le
chapitre suivant, dédié à la définition de nouveaux conditionneurs de trafic.
La figure 5.1 montre la topologie de réseau. Elle est formée par un nombre variable de nœuds
d’entrée (En) qui sont connectés directement au lien central (qui connecte B1 et B2). La capacité du lien
entre B1 et B2 est noté par C. Dans ce chapitre, nous supposons que les pertes se concentrent sur le lien
central; le débit entre les nœuds d’entrée et le lien central étant fixée à 4C.
E1 R1
S2,1
S2,2 E2 R2
..
S2,i B1 B2
lien central
En-1 Rn-1
En Rn
Le nombre de flux individuels (Sn,i) qui entrent par chacun des nœuds d’entrée varie en
fonction du cas étudié. Pour éviter la synchronisation des flux TCP, le début d’émission de chaque flux
varie aléatoirement entre 0 et 1 secondes. Dans cette série de simulations, la taille des paquets est fixé à
1000 octets aussi bien pour des sources TCP que pour des flux UDP. Les nœuds récepteurs (Rn) situés à
la sortie du lien central mesurent le débit obtenu par chaque agrégat, c’est-à-dire, par la totalité des flux
partageant le même nœud d’entrée.
Comme point de départ, nous analysons le comportement actuel des flux TCP. Pour cette
première simulation, 32 nœuds d’entrée ont été définis dans la topologie introduite par la figure 5.1. Un
flux TCP longue durée, avec un temps d’aller-retour (RTT) de 250 ms, est injecté pendant 120 secondes
par chacune des sources. La capacité du lien central est de 10 Mbps avec une file d’attente de 100
paquets.
La figure 5.2 montre l’efficacité de TCP quant au partage des ressources. Quand les connexions
observent le même RTT, le protocole assure une distribution très équitable de la bande passante. Le
graphique a présente l’évolution de chacune des sources. Dans TCP, le contrôle de débit est basé sur la
50000 50000
40000 40000
30000 30000
20000 20000
10000 10000
0 0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux TCP
Figure 5.2: comportement et débit observé par des flux TCP, RTT identique.
Le graphique a montre que le débit moyen mesuré pour chacune des sources après la 36ème
seconde est autour de 36 Ko/s pour toutes les connexions. TCP exploite au maximum la capacité du
réseau. Si dans le long terme TCP est un protocole équitable, dans le court terme ce n’est pas le cas. Le
graphique b montre le débit moyen observé pour chaque source pendant les 30 premières secondes. Les
sources 1, 4, 18, 23 et 29 obtiennent au moins 30% plus de bande passante par rapport à la moyenne.
L’explication est la suivante: pendant que certaines sources diminuent leur débit en réponse aux pertes
observées, d’autres sources n’observant pas de perte augmentent leur débit exponentiellement. Ce
comportement est inadéquat pour des transferts http, où la durée de vie d’une connexion dépasse
rarement quelques secondes et le nombre réduit d’informations à échanger maintient TCP en phase de
croissance exponentielle presque en permanence.
Dans la pratique, il est presque impossible de trouver un comportement aussi équitable dans le
long terme que celui qui vient d’être présenté. TCP est très sensible au temps d’aller-retour (RTT), vu
que la source doit attendre les acquittements du récepteur pour détecter les pertes. Plus il y a une
différence entre le temps d’émission d’un paquet et l’arrivée de son acquittement, plus la source tarde à
détecter une perte. Le graphique a de la figure 5.3 montre l’évolution des flux TCP sous les mêmes
conditions que dans la simulation précédente, sauf que la valeur du RTT pour chaque connexion varie
de 40 à 300 ms. Dû aux différences de RTT entre les sessions, les flux ne deviennent jamais stables.
Ceci est un comportement plus fréquemment observé par les flux TCP dans l’Internet.
90000
120000
80000
100000 70000
60000
80000
50000
60000 40000
30000
40000
20000
20000 10000
0
0 40 48 56 64 72 80 88 96 104 112 120 128 136 144 152 160 168 176 184 192 200 208 216 224 232 240 248 256 264 272 280 288
Figure 5.3: comportement et débit observé par des flux TCP, RTT différent.
Dans le graphique b, le débit accordé à chaque connexion TCP est une fonction du RTT. Il
présente le débit moyen par source observé sur 5 simulations quand C (le débit du lien central) est fixé
à 10Mbps. La courbe de tendance prouve que la bande passante qu’une connexion obtient diminue
quand le RTT augmente. Lors de cette simulation et des simulations similaires utilisant des
combinaisons de RTT différents, il a été trouvé que: 1) le débit atteint par une connexion TCP dépend
du propre RTT aussi bien que du RTT observé par les sources concurrentes; 2) le RTT joue un rôle
moins important sur la performance des sources quand les valeurs en compétition son élevés (au delà de
800 ms). On peut en déduire que:
Pour assurer sa résistance au facteur d’échelle, le modèle DiffServ ne se concentre pas sur la
différentiation des flux individuels. Il est plus probable que, dans un premier temps, un service
commercial DiffServ se concentre sur les assurances qui peuvent être offertes aux agrégats de flux
(trafic sortant d’un réseau, trafic classifié par type d’application, etc.). Il est donc intéressant d’analyser
le comportement d’un flux formé par plusieurs micro-flux hétérogènes. Pour ceci, le comportement de
60 sources TCP regroupées dans 5 agrégats (nommés de A à E) a été simulé. Les 12 connexions qui
forment chaque agrégat partagent le même nœud d’entrée (c.f. figure 5.1). Le RTT pour chacune des
sources au sein d’un agrégat est choisi aléatoirement entre 40 et 300 ms. La capacité du lien central, C,
reste fixe à 10 Mbps. La figure 5.4. montre les résultats de cette simulation.
Le graphique a montre que le multiplexage des micro-flux donne aux agrégats un
comportement beaucoup moins variable que celui d’une source individuelle. La variation maximale
200000
250000
A
B
200000 C 150000
D
E
150000
100000
100000
50000
50000
0
0
A1:S(1,1) - S(1,12) A2:S(2,1) - S(2,12) A3:S(3,1) - S(3,12) A4:S(4,1) - S(4,12) A5:S(5,1) - S(5,12)
0
16
24
32
40
48
56
64
72
80
88
96
2
10
11
agregats TCP
a temps (s) b
observée est de 30% (agrégat E). Le graphique b montre que la distribution de ressources entre les
agrégats est assez équitable: chaque agrégat obtenant autour de 2 Mbps (250 Ko/s). Le même niveau
d’équité est observé sur la plupart d’échelles temporelles.
Si la différentiation de ressources est effectuée au niveau des agrégats, des mécanismes
simples d’attribution de priorités peuvent assurer une distribution contrôlée de ressources. Par contre, le
conditionnement d’un agrégat résulte en l’incapacité de contrôler la distribution des ressources à
l’intérieure de celui-ci. La figure 5.5 montre le débit observé par chacun des microflux composant les 5
agrégats.
45 000
40 000
35 000
débit observé (octets/s)
30 000
25 000
20 000
15 000
10 000
50 00
0
A B C D E
s o u rc e s T C P
Il peut exister une différence de plus de 300% entre la bande passante accordée à deux flux
individuels au sein d’un agrégat. En général, cette inéquité est une conséquence des différences de RTT
entre les connexions TCP et de la présence de flux non adaptatifs dans l’agrégat.
Si, dans l’avenir, il est nécessaire de créer des services capables d’assurer une bonne
différentiation aussi bien entre les agrégats que entre les flux les composant, des mécanismes
plus élaborés que ceux standardisés par l’IETF seront nécessaires.
Des conditionneurs qui prennent en compte ce besoin sont décrits dans le chapitre suivant.
80000 80000
70000 70000
débit observé (octets/s)
60000 60000
40000 40000
30000 30000
20000 20000
10000 10000
0 0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux UDP (1-8), flux TCP (9-32)
Figure 5.6: comportement des flux TCP en présence des flux UDP
La distribution de ressources est très inéquitable. Les sources UDP (lignes épaisses en haut du
graphique), ne réagissant pas aux pertes, obtiennent un débit très proche du débit d’émission, tandis que
les flux TCP doivent combattre entre eux pour récupérer les ressources restantes. Une caractéristique
que l’on observe dans le graphique a est que, dû à la congestion dans le lien, même si les flux TCP
présentent le même RTT, il n’existe plus la stabilité observée dans la section 5.2.1.
Un des premières avantages d’attribuer des priorités aux paquets est la possibilité de pénaliser
les sources non-adaptatives. Dans ce cas, une source ne respectant pas le débit d’émission accordé se
verra attribuer une faible priorité, permettant aux autres flux de gagner plus de bande passante dans les
routeurs. Les conditionneurs DiffServ exploitent cette possibilité.
Il a été mentionné que, grâce à l’introduction de priorités dans les paquets IP, il serait possible
de contrôler la distribution de ressources dans un service AF. Tout conditionneur destiné à ce type de
services doit assurer une distribution contrôlée de ressources avec un niveau de précision acceptable. Il
est nécessaire, pour toute proposition, d’analyser les limites de la différentiation offerte sous des
conditions extrêmes de pénurie ou de disponibilité de ressources. Bien entendu, il est aussi important de
vérifier que les faiblesses de TCP, en termes de l’impact du RTT et de l’effet des flux non-adaptatifs,
soient recouvertes grâce au conditionnement réalisé par l’algorithme. Avant de décrire en détail trois
résultat
C O N D ITIO N N E U R
Avant de rentrer dans la discussion sur la capacité de différentiation des marqueurs, il est
nécessaire de décrire les caractéristiques du réseau simulé. Plusieurs fonctionnalités1 ont été ajoutés au
simulateur afin de tester une architecture DiffServ conforme aux standards de l’IETF. Nous avons
effectué les modifications nécessaires à la topologie utilisé dans la section 5.2. (figure 5.1). En premier,
des conditionneurs ont été implantés dans les liens qui connectent les sources aux nœuds d’entrée
comme le montre la figure 5.8. Pour la simulation du comportement des agrégats, des conditionneurs
sont aussi utilisés dans les nœuds secondaires, placés entre les nœuds d’entrée et le lien central. Ensuite,
un mécanisme d’élimination sélective a été mis à l’épreuve dans le lien central. Nous avons choisi
RIO3, le RIO à trois niveaux (cf. section 2.4.3). Cette topologie est utilisée pour toutes les simulations
présentées dans le reste de ce chapitre.
En-1 Rn-1
Les paramètres de configuration d’un même conditionneur changent pour chaque cas étudié. Ils
peuvent être différents pour chaque source afin d’obtenir une répartition différentiée de bande passante.
Par contre, les paramètres de configuration de RIO3 restent constants. Puisque le comportement des
flux sera étudié pour différents niveaux de congestion, c’est-à-dire, quand la capacité C du lien central
change, la valeur des seuils est choisie en fonction de la longueur de la file d’attente du lien central (Q)
comme le montre le tableau 5.1. La représentation graphique de ces paramètres est similaire à celle de
la figure 2.7.
La validité des paramètres est vérifiée grâce à une simulation simple. Un flux CBR à 20 Mpbs
(2.50 Mo/s) est transmis sur un lien à 10 Mbps (1.25 Mo/s) utilisant une file d’attente Q de 100 paquets.
Les paramètres de RIO3 introduits par le tableau 5.1 sont utilisés. Le taux de perte est constant à 50%.
La source attribue une couleur aux paquets en fonction de pourcentages configurés. La figure 5.9
montre la couleur des paquets acceptés par le routeur pour plusieurs pourcentages de chaque couleur.
Dans la figure, %v/%o/%r dénote le pourcentage de paquets de chaque couleur qui est produit par la
source.
Notre implémentation de RIO3 répond aux attentes. La totalité des paquets rouges est éliminée
en premier par le routeur en cas de congestion. Quand le pourcentage de paquets verts et oranges
augmente, ce sont les deuxièmes qui doivent céder leur place aux premiers. Finalement, quand le
pourcentage de paquets verts est égal à la capacité du lien, un petit taux de perte (2%) est observé pour
les paquets de cette couleur. Nous considérons que ce taux de perte ne gêne pas l’opération du modèle.
12000
10000
paquets reçus
8000
ro u g e
o ra n g e
6000 ve rt
4000
2000
0
1 0 /1 0 / 8 0 1 5 /1 5 / 7 0 2 0 /2 0 / 6 0 2 5 /2 5 / 5 0 3 0 /3 0 / 4 0 3 5 /3 5 / 3 0 4 0 /4 0 / 2 0 4 5 /4 5 / 1 0 5 0 /5 0 / 0
d is trib u tio n d e p r io rité s
Nous commençons la description des conditionneurs proposés par un algorithme très simple: le
Marqueur par Seaux à Jetons Parallèles, PTB (Parallel Token Buckets). Ce marqueur, décrit dans
[SN99], a été conçu avec la seule motivation de protéger les flux adaptatifs des non-adaptatifs. Dans
cette proposition, les flux adaptatifs (TCP) sont conditionnés par un seau à jetons (cf. section 2.2)
différent de celui utilisé pour les flux non-adaptatifs (UDP). Etant donné que le seau à jetons est un
vérificateur binaire, il n’existe que deux priorités possibles pour marquer chaque type de flux. L’étude
de cette proposition permet de découvrir les limites de la différentiation avec un nombre si réduit de
niveaux. En effet, la mise en évidence des performances du modèle à deux niveaux (in/out) dans [IN98]
ont mené le groupe DiffServ a créer un troisième niveau. Si la différentiation qui peut être obtenue avec
le PTB n’atteint pas la précision d’autres propositions, [SN99] a le mérite d’avoir été un des premiers
documents proposant le conditionnement différentié des flux en fonction de leur réaction aux pertes.
5.4.1 Définition
bt
flux TC P c o n d itio n n e u r
classificateur flux
ru m arqués
bu
flux U D P
c o n d itio n n e u r
Dans un nœud d’entrée mettant en œuvre le PTB, le débit assuré r et la taille de rafale
maximale b du seau à jetons doivent être spécifiés pour chaque conditionneur. En plus, il est nécessaire
de définir la politique de marquage, c’est-à-dire, la correspondance entre le résultat de la vérification et
les trois couleurs disponibles. Dans la figure 5.11 nous avons utilisé deux seaux à jetons identiques pour
conditionner deux flux. Ils sont été configurés avec un débit assuré (r) de 60 Ko/s et une taille de seau
de 6000 octets (6 paquets). Un flux TCP (avec un RTT de 250 ms) et un flux UDP (CBR à 120 Ko/s)
ont été injectés séparément dans chacun de marqueurs.
140 140
120 120
100 100
paquets UDP
paquets TCP
80 80
rouge rouge
orange orange
60 vert 60 vert
40 40
20 20
0 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
a temps (s) b temps (s)
La figure 5.11 montre que, à cause de la variabilité du débit produit par TCP, la relation entre le
nombre de paquets conformes et non conformes n’est pas la même pour les deux types de flux. Cette
simulation prouve que l’introduction du marquage n’est pas suffisante pour protéger les flux adaptatifs.
Des mesures supplémentaires sont nécessaires:
Soit des paramètres de configuration différents sont utilisés dans chaque seau à jetons, soit des
mesures comme celle qui consiste à attribuer des couleurs différentes à chaque type de flux
doivent être mises en œuvre afin d’assurer une protection effective des flux adaptatifs.
Dans la section 5.2.1, le comportement de 32 flux TCP observant le même RTT a été étudié.
Nous avons conservé les caractéristiques de cette simulation pour les utiliser dans la topologie de la
figure 5.8. Un conditionneur basé sur un seau à jetons (TB) est placé à la sortie de chaque source. RIO3
est actif sur le lien central, configuré avec les paramètres du tableau 5.1. Pour évaluer la capacité de
différentiation du TB, les conditionneurs sont initialisés différemment. Le débit assuré, r, est fixé à
32 Ko/s pour les sources S1-S8, à 24 Ko/s pour S9-S16, 16 Ko/s pour S17-S24 et à 8 Ko/s pour S25-S32.
La taille de rafale maximale b est égal à 2r octets. Chaque source est conditionnée individuellement,
aucun traitement n’est effectuée sur les nœuds d’agrégation. La figure 5.12 en montre les résultat.
80000 60000
70000
50000
60000
débit observé (octets/s)
40000
50000
40000 30000
30000
20000
20000
10000
10000
0 0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux TCP
Quand le marquage et l’élimination sélective sont introduits, la stabilité qui avait été observée
dans la figure 5.2 disparaît. Ceci ne peut pas être considéré comme un défaut, le comportement idéal de
TCP est presque jamais observé par des vrais flux traversant l’Internet. Dans des simulations
préparatoires, il a été trouvé que la simple implantation de RED (cf. section 2.4.1) dans le lien central
suffit pour rompre avec l’équilibre. Il faut donc se concentrer sur la quantité de ressources accordées à
chaque flux.
Nous considérons qu’une bonne différentiation est observée si elle se rapproche du partage de
ressources offert par des algorithmes de Fair Queueing [Ja96][DKS90]. Dans ce cas, nous considérons
que la différentiation est 100% équitable. A partir du débit assuré pour chaque source r(Si), et de la
r (Si ) eq 5.1
D ( S i ) = C -------------------
∑ r ( Si )
i
Un deuxième cas de différentiation qui peut être considéré "équitable" est celui où les
ressources en excès sont distribués équitablement. Pour le cas de cette simulation, où le débit total
assuré est inférieur à la capacité du lien, ce type d’équité pourrait être observée. Le comportement du
modèle est conforme à ce nouveau type de différentiation, que nous allons appeler excès équitable, si,
pour n sources:
∑ i
C – r ( S ) eq 5.2
D ( S i ) = r ( S i ) + ----------------------------
i -
n
Le lignes noires dans le graphique a indiquent la moyenne des débits observés par type de
source (en fonction du conditionneur utilisé). Le graphique b le confirme qu’il existe une
différentiation, il reste à vérifier si elle satisfait une des deux équations. Le débit total assuré est de 640
Ko/s, c’est-à-dire, autour de 0.5C. Selon l’équation 5.1, le débit par source devrait être autour de 2r.
Basés sur l’équation 5.2, chaque source devrait obtenir r(Sij) + C/32. Le tableau 5.2 compare la
moyenne des débits effectivement accordés par type de source contre celui qui aurait dû être observé en
considérant les deux possibilités identifiées. Le débit total observé sur le lien central est de 1,157 Mo/s,
les 32 sources l’exploitent à 93%. Nous avons calculé les débits équitables en fonction de cette valeur
(C=1,157 Mo/s).
A partir du tableau 5.2 il peut être conclu que la différentiation à deux niveaux par seau à jetons
s’approche, en termes statistiques, l’équation 5.2 avec un taux d’erreur acceptable (~10%). Le
graphique a de la figure 5.12 montre néanmoins des différences importantes dans le débit observé par
les flux du même type. Cette caractéristique doit être prise en compte lors de la définition des services
basés sur ce conditionneur.
Le deuxième point d’étude analyse l’amélioration de l’équité quand le RTT observé par chaque
source est différent. Dans la section 5.2.2 il a été trouvé que le partage de ressources est très variable
quand les différences de RTT sont importantes. La simulation utilisée pour créer cette figure a été
reconduite sur notre architecture à Différentiation de Services. Un marqueur TB a été initialisé par
source avec un débit assuré r de 20 Ko/s et une rafale maximale b de 40 Ko (40 paquets). Les autres
caractéristiques du réseau restent constantes par rapport à la simulation précédente.
100000 100000
90000 90000
80000 80000
70000
60000
60000
50000
50000
40000
40000
30000
30000
20000
20000
10000
10000
040
48
56
64
72
80
88
96
4
2
0
8
6
4
2
0
8
6
4
2
0
8
6
4
2
0
8
6
4
2
0
8
0
10
11
12
12
13
14
15
16
16
17
18
19
20
20
21
22
23
24
24
25
26
27
28
28
1 4 7 10 13 16 19 22 25 28 RTT (ms)
a temps (s) b
La figure 5.13 montre le résultat de la simulation. Le graphique a indique une diminution dans
la variabilité des flux par rapport à la figure 5.3. La différentiation a augmenté la stabilité des flux. Dans
le graphique b il peut être observé que, mis à part les deux flux avec les RTT les plus petits, qui
obtiennent une partie importante de la bande passante, le reste des sources obtient entre 22 Ko/s et
44 Ko/s. Ceci représente une amélioration par rapport au résultat de la section 5.2.2, mais le
comportement ne peut pas encore être considéré équitable.
Dans la section 5.2.2 le comportement d’agrégats TCP, formés par des connexions à RTT
hétérogènes, a été analysé. Dans cette section nous simulons une situation qui se rapproche de celles
que l’on trouve dans les réseaux commerciaux qui offrent la Différentiation de Services. En
conditionnant un groupe de flux en tant qu’ensemble, le comportement de l’agrégat devient plus stable,
le marquage est plus précis.
Les 60 flux TCP qui ont été utilisés pour la simulation suivante gardent les mêmes
caractéristiques que ceux de la section 5.2.2. En partant de la topologie de la figure 5.8, un
conditionneur TB est placé à la sortie de chacun des 5 nœuds concentrateurs. Le débit assuré r pour
chaque agrégat varie uniformément de 300 Ko/s à 60 Ko/s comme le montre le tableau 5.3. La taille de
rafale maximale b reste fixe à 2r octets. Comme dans la section 5.2.2, le lien central est capable
351071
350000 350000
250000 250000
A
222503
B
200000 C 200000
D 166826
E
150000 150000
105697
100000 100000
50000
50000
0
0
A1:S(1,1) - S(1,12) A2:S(2,1) - S(2,12) A3:S(3,1) - S(3,12) A4:S(4,1) - S(4,12) A5:S(5,1) - S(5,12)
0
16
24
32
40
48
56
64
72
80
88
96
2
10
11
agregats TCP
a temps (s) b
Il reste à vérifier comment les ressources sont partagées au sein des agrégats. La figure 5.15
contient cette information. Si la différentiation entre les agrégats est très bonne, entre les microflux qui
le composant ce n’est pas le cas. Le débit observé de chaque agrégat peut être formé en grande partie
par le trafic de deux ou trois de connexions.
Aucune méthode utilisant le PTB n’a été développée pour améliorer les performances par
microflux observées dans la figure 5.15. Le PTB est en conséquence inadapté pour offrir des assurances
à des flux individuels. D’autres conditionneurs existent pour lesquels il est possible de pré-marquer les
sources individuelles à l’entrée du réseau afin de mieux partager la bande passante dans des situations
comme celle présentée ici. Un exemple de conditionneur de ce type est le Marqueur à Trois Couleurs
(TCM), décrit plus tard dans ce chapitre.
6 0 0 0 0
débit observé (octets/s)
5 0 0 0 0
4 0 0 0 0
3 0 0 0 0
2 0 0 0 0
1 0 0 0 0
0
3 0 0 K o /s 2 4 0 K o /s 1 8 0 K o /s 1 2 0 K o /s 6 0 K o /s
s o u rc e s T C P
Les simulations de cette section étudient le problème qui a motivé la création du PTB: la
protection des flux adaptatifs. Comme dans la section 5.2.4, des flux TCP et UDP cohabitent. Si aucune
différentiation n’est implantée, cette cohabitation est catastrophique pour les flux TCP. La
configuration utilisée dans la section 5.2.4 est prise comme base de notre modèle de simulation. 24
sources TCP et 8 sources UDP partagent le lien central de 10 Mbps. Un marqueur TB, initialisé à
r=40Ko/s et b=80Ko, est introduit à l’entrée de chaque source. La couleur accordée aux paquets est
différente pour chaque type de flux en conformité avec la définition du PTB (cf. section 5.4.1). La
figure 5.16 présente le résultat des simulations.
80000 50000
45000
70000
40000
60000
35000
débit observé (octets/s)
50000
30000
40000 25000
30000 20000
15000
20000
10000
10000
5000
0
0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux UDP (1-8), flux TCP (9-32)
Figure 5.16: différentiation par PTB, protection offerte aux flux adaptatifs
La méthode du PTB est bénéfique pour les flux TCP. Non seulement ils réussissent à obtenir un
peu plus que leur débit assuré (44,5 Ko/s) mais aussi ils se partagent la bande passante très
équitablement. Les flux UDP doivent rentrer en concurrence pour les ressources au delà des ressources
réservées, n’obtenant qu’autour 50% de r (22,1 Ko/s). En théorie, chaque seconde 1708 paquets
arrivent en moyenne au lien central. Tous les paquets ont une taille fixe de 1000 octets. Le tableau 5.4
montre la distribution de priorités résultant du conditionnement. Pour la taille de paquet utilisée, la
capacité d’acheminement est de 1250 paquets/seconde. 458 datagrammes par seconde sont éliminés.
Si RIO3 fonctionne correctement, chaque seconde la totalité des paquets rouges sont mis à
l’écart. Au contraire, 100% des paquets verts sont acceptés. Le niveau orange est le seul où les flux
TCP et UDP sont en concurrence directe. Dans ce sous-ensemble, les paquets UDP obtiennent 75% des
ressources disponibles, valeur similaire à celle observée dans la section 5.2.4 (72%). L’effet de la
non-adaptabilité des sources UDP a été déplacée par la différence de priorités.
Si l’on considère les équations 5.1 et 5.2, le PTB n’est pas un conditionneur équitable entre
TCP et UDP. Chaque source aurait dû observer un débit de 35,2 Ko/s indépendamment du protocole de
transport utilisé. Ceci ne peut pas être considéré comme un défaut. Le conditionneur résout le problème
qu’il est censé de résoudre: il protège effectivement les flux adaptatifs de non-adaptatifs et distribue
équitablement la bande passante parmi les flux du même type.
Le PTB est un des marqueurs le plus simples qui puissent exister. Néanmoins, d’après nos
simulations, son implantation dans le réseau suffirait pour différentier avec précision des agrégats TCP
et pour protéger des flux adaptatifs des non-adaptatifs. Par contre, la performance des flux TCP à RTT
différent, ainsi que la distribution de ressources au sein d’un agrégat limitent l’utilité du marqueur.
Wenjia Fang, une des précurseusses de la Différentiation de Services, définit dans [FSN2k] un
marqueur compatible avec le Comportement Assuré du modèle DiffServ. Ce marqueur, appelé
"Marqueur à Trois Couleurs par Fenêtre de Temps Glissante" (Time Sliding Window Three Color
Marker, TSWTCM), est une variation du marqueur à deux niveaux introduit dans [rio]. La distribution
proportionnelle des priorités en fonction du débit moyen est l’idée centrale derrière cette proposition.
Dans cette section, nous appellerons TSWM ce type de marqueur.
5.5.1 Définition
L’algorithme du TSWM peut être décomposé en deux parties: calcul du débit moyen (élément
vérificateur dans la figure 5.7) et attribution d’une précédence (élément marqueur dans la même
figure). Un TSWM est configuré à l’aide de trois paramètres: un intervalle de mesure de la moyenne
INT (Average Interval), un débit assuré CTR (committed traffic rate) et un débit maximal PTR (peak
A l’instant 0,
INT = constant (intervalle d’observation)
deb_moy = CTR (initialisé au débit assuré)
dern_t = 0 (temps d’arrivée du dernier paquet)
bytes_en_fen octets dans la fenêtre d’observation
temps_en_fen taille en secs de la fenêtre d’observation
dern_t temps d’arrivée du dernier paquet
Dans la section 2.2, nous remarquions que la caractérisation d’un flux par son débit moyen est
une opération risquée puisque la valeur calculée dépend en grande mesure de la fenêtre d’observation
utilisée. La figure 5.17 montre le débit moyen obtenu pour des fenêtres d’observation de 1, 2, 4 et 8
secondes. Logiquement, la moyenne devient plus stable et reflète moins les variations de la source
100
90
80
débit observé (Ko/s)
70
source
60
avg 1s
50 avg 2s
40 avg 4s
avg 8s
30
20
10
0
1 6 11 16 21 26
temps (s)
quand la taille de la fenêtre augmente. La valeur de ce paramètre doit être choisie avec précaution pour
chaque type de source. Une valeur importante augmente l’ampleur des variations de débit qui peuvent
être acceptées. Une valeur restreinte peut pénaliser trop rapidement les flux de nature variable, comme
les flux TCP. Pour les simulations de cette section nous avons retenu une fenêtre de 2 secondes.
Le pseudo-code suivant présente l’algorithme utilisé pour calculer la couleur des paquets en
fonction du débit moyen. Avec le TSWM, la probabilité de marquer un paquet orange ou rouge dépend
120 120
100 100
paquets UDP
paquets TCP
80 80
rouge rouge
orange orange
60 vert 60 vert
40 40
20 20
0 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
a temps (s) b temps (s)
La marquage obtenu grâce au TSWM est très variable comme le montre la figure 5.18. Le
pourcentage de paquets de chaque couleur varie considérablement d’un échantillon à l’autre. Pour le
flux TCP, ce comportement pourrait être compréhensible, vu la nature variable de la source. Par contre,
des variations apparaissent aussi dans le marquage du flux UDP (où ce serait préférable de compter
avec un nombre précis de paquets verts pour faciliter le pré-marquage des sources multimédia). La
raison de ce comportement est l’introduction d’une variable aléatoire (utilisation de probabilités) dans
le calcul de la couleur. A cause de cette caractéristique, en plus de la variabilité observée au sein d’une
En partant des mêmes principes que la première simulation effectuée avec le PTB (cf. section
5.4.2), nous cherchons à mesurer la capacité de différentiation du TSWM. Dans cette première
simulation, 32 flux TCP à RTT égal traversent un lien central à 10 Mbps. Plusieurs jeux de paramètres
sont utilisés dans la configuration des conditionneurs pour forcer la différentiation. Le choix des
paramètres suit les mêmes principes que dans la section 5.4.2. Le CTR du TSWM est fixé à la même
valeur que le débit assuré r utilisé par le PTB pour faciliter la comparaison. Le PTR porte une valeur
égale à 2r. L’intervalle d’observation est fixé à 2 secondes pour tous les conditionneurs.
80000 70000
70000
60000
60000
50000
débit observé (octets/s)
50000
40000
40000
30000
30000
20000
20000
10000 10000
0 0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux TCP
Le résultat de cette simulation (figure 5.19) est très satisfaisant. Dans cet approche le marqueur
justifie sa complexité par une bonne performance. Dans le temps, les flux sont assez stables (graphique
a); dans la distribution, une différence sensible et conforme aux prévisions existe entre les flux. De
plus, il existe une bonne équité entre les flux marqués à partir des mêmes paramètres (graphique b).
Pour mieux caractériser le TSWM, il est nécessaire de comparer son comportement vis à vis
des deux types d’équité (cf. section 5.4.2). Le tableau 5.5 reflète le degré de conformité du
conditionneur par rapport à l’équité absolue et à l’équité des ressources en excès. Le débit total observé
est de 1,23 Mo/s, c’est-à-dire, 98% de la capacité disponible. Les valeurs dans le tableau ont été
calculés à partir de cette valeur. Si la distribution des ressources en excès est équitable, chaque flux
obtiendrait 18,49 Ko/s au-delà de son débit assure.
A partir du tableau, on observe que le TSWM est proche du partage 100% équitable. Le
marqueur peut ne pas être très précis (jusqu’à 15% d’erreur), mais la déviation reste inférieure à celle
du PTB pour le même type d’équité (c.f. tableau 5.2). L’introduction d’un troisième niveau de priorité
est en grande partie responsable de cette bonne performance. Dans les situations, comme celle simulée
ici, où il existe assez de bande passante pour assurer l’acheminement des paquets verts de tous les flux,
les ressources en excès sont distribuées de manière différentiée à l’aide des couleurs orange et rouge.
Dans une telle architecture, si peu de flux partagent un lien de grande capacité ou des petites valeurs
sont utilisées pour configurer les marqueurs, un grand nombre de paquets rouges est produit. Quand les
liens du cœur du réseau assurent l’acheminement de la totalité des paquets verts et jaunes, les
ressources restantes sont distribuées à parts égales entre les paquets rouges. Ce cas est étudié dans le
chapitre suivant. Pour le moment, nous nous limitons à signaler que l’équité offerte par le marqueur
dans une telle situation est plutôt caractérisée par l’équation 5.2 (100% équitable).
Suivant le mode d’opération utilisé dans la section 5.4.2, la capacité du TSWM à réduire l’effet
du RTT est analysée. Un marqueur identique est implanté à l’entrée de 32 sources TCP dont le RTT
observé par chaque flux va de 40 et 300 ms. La figure 5.20 présente le résultat de cette simulation.
100000 100000
90000 90000
80000 80000
70000
debit moyen (octets/s)
70000
débit observé (octets/s)
60000
60000
50000
50000
40000
40000
30000
30000
20000
20000
10000
10000 0
40
48
56
64
72
80
88
96
4
2
0
8
6
4
2
0
8
6
4
2
0
8
6
4
2
0
8
6
4
2
0
8
0
10
11
12
12
13
14
15
16
16
17
18
19
20
20
21
22
23
24
24
25
26
27
28
28
1 4 7 10 13 16 19 22 25 28 RTT (ms)
a temps (s) b
Par rapport au PTB (c.f. figure 5.13), le comportement des flux est moins stable (graphique a);
quant à l’équité, une analyse rapide du graphique b dirait que le TSWM offre des meilleurs
Les simulations réalisées dans cette section suivent la même méthodologie que celles de la
section 5.4.4. Cinq agrégats, chacun étant composé par 12 sources TCP à RTT variable, traversent un
lien à 10 Mbps. Chaque agrégat est conditionné par un TSWM différent, cherchant à obtenir le même
degré de différentiation que celui obtenu grâce au PTB (c.f. tableau 5.3). Dans la situation étudiée ici, le
CTR ne peut pas être égalisé au débit assuré r du PTB. La somme des débits assurés atteint 72% de la
capacité du lien central. Si CTR=r et PTR=2r, la majorité des paquets produits serait verte, une
minorité serait orange et il n’y aurait aucun paquet rouge. On reviendrait à la différentiation à deux
niveaux. Pour résoudre ce problème, le CTR utilisé est égal à 2r/3 et le PTR équivaut 4r/3. L’intervalle
d’observation reste à 2 secondes. La moyenne des résultats (5 exécutions) a servi pour créer les
graphiques de la figure 5.21.
450000 400000
360652
400000 350000
350000
300000 283845
debit moyen (octets/s)
debit agregé (octets/s)
300000
250000
223488
A
250000 B
C 200000
D
200000 158062
E
150000
150000
100000 85831
100000
50000
50000
0
0
A1:S(1,1) - S(1,12) A2:S(2,1) - S(2,12) A3:S(3,1) - S(3,12) A4:S(4,1) - S(4,12) A5:S(5,1) - S(5,12)
0
16
24
32
40
48
56
64
72
80
88
96
2
10
11
agregats TCP
a temps (s) b
1. l’écart est représenté par le rapport entre le débit observé par la connexion avec le RTT le plus court et
celui observé par la source dont le RTT est le plus long. Dans ce cas, écart=D(S1)/D(S32).
Cette dernière simulation concernant le TSWM s’attaque au partage de ressources entre des
flux adaptatifs et non-adaptatifs. Les méthodes de simulation et d’évaluation restent équivalentes avec
la section 5.4.. La figure 5.23 est le résultat de la simulation de 8 flux UDP à débit constant (80 Ko/s) et
de 24 flux TCP (RTT de 200 ms). Pour les mêmes raisons que dans la section précédente, le CTR est
fixé à 2r/3, le PTR à 4r/3; où r dénote le débit assuré du PTB utilisé dans la section 5.4.5 (40 Ko/s). La
valeur exacte du CTR devrait être 26,66 Ko/s. Nous avons retenu 25 Ko/s pour faciliter l’analyse.
6 0 0 0 0
débit observé (octets/s)
5 0 0 0 0
4 0 0 0 0
3 0 0 0 0
2 0 0 0 0
1 0 0 0 0
0
3 0 0 K o /s 2 4 0 K o /s 1 8 0 K o /s 1 2 0 K o /s 6 0 K o /s
s o u rc e s T C P
80000 70000
70000 60000
60000
50000
débit observé (octets/s)
40000
30000
30000
20000
20000
10000 10000
0
0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux UDP (1-8), flux TCP (9-32)
Figure 5.23: différentiation par TSWM, protection offerte aux flux TCP
A partir du graphique b de la figure 5.23, il est observé que toutes les sources obtiennent leur
débit assuré mais, malgré l’utilisation des marqueurs identiques, les flux non-adaptatifs obtiennent 2
fois plus de ressources que les flux TCP. Il existe une amélioration par rapport à la non utilisation de
mécanismes DiffServ mais il n’existe pas d’équité. Cette simulation justifie la décision qui a été prise
dans la conception du PTB qui est omise dans la définition du TSW: une politique de marquage
identique pour des flux TCP et UDP résulte en une distribution de ressources avantageuse pour ces
derniers. Ceci ne signifie pas que le TSWM est mal adapté pour protéger les flux TCP. Il s’agit d’un
problème de paramétrage. En faisant varier les paramètres, il a été trouvé qu’une distribution équitable
de ressources (39,02 Ko/s par source) est atteinte quand CTRtcp=1,85CTRudp. Pour la situation
étudiée ici, le CTRtcp est égal à 46,25 Ko/s. On revient plus ou moins au cas du PTB, où les paquets
conformes en excès (oranges) des flux UDP sont mis au même niveaux que les paquets TCP non
conformes (rouges).
Le TSWM est un marqueur basé sur le calcul du débit moyen, une alternative à l’utilisation de
seaux à jetons. Sa complexité d’implantation a été justifiée par une bonne différentiation à la fois des
flux individuels que des flux agrégés. La protection des flux adaptatifs peut être assurée avec
l’utilisation de paramètres différents pour chaque type de flux. Pourtant, le TSWM ne peut pas corriger
Cette section est dédié au Marqueur à Trois Couleurs (Three Color Marker), seul conditionneur
destiné à la mise en priorités standardisé par l’IETF. En réalité, il existe deux versions du TCM: le
TCM à débit simple [rfc2697], et le TCM à débit double [rfc2698]. Nous présentons l’algorithme
proposé pour chacun des conditionneurs. Ensuite, nous analysons le comportement du réseau pour les
situations étudiées dans la section 5.2. quand des mécanismes DiffServ sont mis en œuvre.
Le srTCM, TCM à débit simple (single rate Three Color Marker), est configuré par trois
paramètres: le débit assuré CIR (Committed Information Rate), la taille de rafale assurée CBS
(Committed Burst Size) et la taille de rafale en excès EBS (Excess Burst Size). Ces paramètres servent
à initialiser deux seaux à jetons TC et TE comme le montre la figure 5.24. A l’instant 0, TC=CBS et
TE=EBS. Par la suite, les seaux sont remplis selon la lois:
C IR
EBS
CBS
A l’arrivée d’un paquet de taille L (en octets) dans le conditionneur, la précédence que lui est
attribuée (la couleur) dépend de l’état des seaux. A différence du TCM à deux débits, le srTCM effectue
une vérification du haut en bas, c’est-à-dire, qu’il analyse d’abord la possibilité de marquer le paquet en
vert avant de tester pour le niveau orange. Le pseudo-code ci-dessous présente l’algorithme utilisé.
sinon,
le paquet est rouge
Tc et Te ne sont pas modifiés
Pour avoir un meilleur aperçu du srTCM, la figure 5.25 montre la distribution des priorités pour
un flux TCP et un flux UDP marqués par ce conditionneur. Le flux UDP émet à débit constant
(120000o/s). Pour cette simulation le niveau de priorité n’a aucun effet sur les routeurs; on
s’intéresse uniquement à la fonction de marquage. Des valeurs de CIR=60 Ko/s, CBS=6 Ko (6
paquets) et EBS=12 Ko (12 paquets) ont été utilisés.
140 140
120 120
100 100
paquets UDP
paquets TCP
80 80
rouge rouge
orange orange
60 vert 60 vert
40 40
20 20
0 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
a temps (s) b temps (s)
La différence entre les priorités accordées aux deux flux est assez importante. D’un coté, pour
le flux TCP à débit variable, la limite théorique de 60 paquets verts par seconde n’est jamais atteinte car
la nature variable du flux vide rapidement les seaux. Par contre, cette variabilité permet aux seaux de se
remplir quand la source diminue le débit d’émission. Un bon équilibre entre le nombre de paquets de
chaque couleur existe pour ce type de source. D’autre coté, pour la source UDP à débit constant, la
totalité de jetons verts est utilisée à chaque seconde (60), mais pratiquement aucun paquet est marqué
orange. Ceci est dû à la règle de remplissage de l’algorithme où aucun jeton n’est ajouté à TE tant que
TC n’est pas complètement rempli. Ceci réduit l’intérêt du srTCM pour conditionner des streams CBR,
puisqu’un niveau de différentiation est gaspillé.
Le trTCM, TCM à débit double (two rate Three Color Marker), diffère du srTCM en plusieurs
aspects: 1) pour ce marqueur, les seaux sont remplis à débit différent; 2) l’attribution de la couleur est
faite du bas en haut; si le paquet ne peut pas être orange, le conditionneur ne vérifie pas s’il peut être
vert; et 3) quand un paquet est marqué vert, des jetons sont pris des deux seaux. Ceci résulte en un
conditionnement différent de celui offert par le srTCM.
Le trTCM est formé par deux seaux à jetons configurés par quatre paramètres: TC est défini par
le débit assuré CIR (Committed Information Rate) et la taille de rafale assurée CBS (Committed Burst
Size); TP est initialisé avec le débit maximal PIR (Peak Information Rate) et la taille de rafale maximale
PBS (Peak Burst Size). La figure 5.26 montre plus clairement la signification des paramètres.
P IR
C IR
PB S
CBS
A l’instant 0, TC et TP sont à leur niveau maximal de CBS et PBS respectivement. Par la suite,
chaque seau est rempli indépendamment à partir de la règle:
Il faut remarquer que cette indépendance dans le remplissage des seaux permet de produire des
jetons oranges en permanence, évitant le comportement observé pour les flux UDP dans la figure 5.25.
A l’arrivé d’un paquet de taille L (en octets) dans le conditionneur, l’algorithme présenté par le
pseudo-code ci-dessous sert à lui attribuer un niveau de priorité. La conformité du paquet est d’abord
vérifiée pour le seau TP. S’il n’est pas conforme, le paquet est marqué rouge et TC n’intervient pas dans
l’opération. Ce comportement peut provoquer une sous-utilisation des jetons verts si le marqueur n’est
pas bien configuré. Quand le paquet est conforme à TP, il peut être marqué orange ou vert en fonction
de sa conformité auprès de TC. Si le paquet est marqué vert, des jetons sont débités aussi bien de TC que
de TP.
Pour étudier la fonction de marquage du trTCM, il a été soumis à la même simulation que celle
effectué pour le srTCM. Un flux TCP et un flux UDP ont été marqués indépendamment en utilisant les
sinon
le paquet est vert
Te = Te - L (décrémenté jusqu’à zero)
Tc = Tc - L (décrémenté jusqu’à zero)
120 120
100 100
paquets UDP
paquets TCP
80 80
rouge rouge
orange orange
60 vert 60 vert
40 40
20 20
0 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
a temps (s) b temps (s)
La figure 5.27 montre que dans la configuration du trTCM il ne faut pas oublier que le débit de
paquets oranges n’est pas PIR, mais PIR-CIR. Le graphique a montre que même si le PIR est 1.5 fois
plus important que le CIR, moins de paquets oranges sont produits par rapport à l’exemple du srTCM.
Un PIR égal à 2xCIR aurait été nécessaire pour arriver à la même distribution de priorités.
Le graphique b montre que, pour un flux à débit constant, la distribution de priorités du trTCM
est exploitée au maximum. 60 paquets verts et 30 oranges (90-60) sont générés chaque seconde. Ceci
est un comportement souhaitable pour des flux audio/vidéo où la priorité peut non seulement refléter le
résultat d’un conditionnement, mais aussi la valeur de l’information transportée. Il est important pour
ce type de flux de compter avec le plus grand nombre possible de jetons verts pour protéger
l’information indispensable pour le décodeur.
Nous avons présenté les deux marqueurs standardisés par l’IETF. Nous avons montré
l’incapacité du srTCM à produire trois niveaux de priorité pour des flux CBR. En considérant que le
trTCM est une version plus complète du marqueur, nous le prenons comme référence pour les
simulations et les comparaisons qui apparaissent dans ce document. Toute mention du TCM dans les
chapitres à venir fait référence au trTCM, le TCM à débit double.
Cette simulation, comme les suivantes, est basée sur l’architecture à Différentiation de Service
introduite par la figure 5.8. La méthodologie utilisée est identique à celle des sections 5.4.2 et 5.5.2.
Nous commençons par l’analyse du comportement du TCM face à des sources TCP marqués
individuellement. Le paramètre de configuration de référence reste le débit assuré r, introduit dans les
simulations de la section 5.4. Cette première simulation a pour but de distribuer d’une manière
pondérée la bande passante d’un lien à 10 Mbps entre 32 flux TCP. Quatre types de TCM sont
introduits en fonction des paramètres utilisés. L’affectation d’un conditionneur à une source suit les
mêmes principes que dans la section 5.4.2.
Lors des simulations préliminaires, il a été trouvé que, comme pour le TSWM, la
différentiation offerte dépend de la proportion des paquets marqués de chaque couleur. Pour celle-ci et
le reste des simulations concernant le TCM dans ce chapitre, le CIR porte la même valeur que le
paramètre r du PTB, mais la taille de rafale maximale, CBS, est limitée à 2r/3 (et non à 2r comme pour
le PTB). En ce qui concerne le PIR et le PBS, ils sont initialisés à 2CIR et à 3CBS respectivement.
La figure 5.28 présente le résultat de la simulation. Celui-ci est très similaire, tant pour la
stabilité des flux que pour la distribution de bande passante, au comportement observé du TSWM (cf.
section 5.5.2). Les variations de débit provoquées par le TCM sont un peu moins prononcées, mais
l’attribution de ressources est un peu plus éloignée du cas idéal identifié par l’équation 5.1 (équité
absolue). Le tableau 5.7, calculé à partir du taux d’utilisation observé de 98,5%, contient la
comparaison détaillée du comportement du TCM par rapport aux deux types d’équité (cf. section
70000
60000
60000
50000
débit observé (octets/s)
40000
30000
30000
20000
20000
10000 10000
0 0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux TCP
5.4.2). En comparant le tableau 5.7 au tableau 5.5, on observe que les flux conditionnés avec un CIR
relativement restreint obtiennent moins des ressources avec le TCM qu’avec le marqueur par fenêtre
glissante. La déviation maximale reste dans les mêmes limites (15%).
D’après la première simulation, le comportement du TCM peut être considéré satisfaisant car
une distribution similaire à celle du TSWM est observée tout en utilisant un mécanisme de
caractérisation moins complexe (seau à jetons vs. débit moyen).
Il faut maintenant étudier le partage qui peut être obtenu par ce marqueur en présence de flux à
RTT différent. La figure 5.29 contient cette information. Malheureusement, le marquage résulte en une
diminution de la bande passante exploitée, qui se retrouve autour de 68%. La différence de
performances est importante: la proportion approche 4:1 entre les débits observés par les deux cas
extrêmes. Il est donc nécessaire de faire des modifications au TCM, au TSWM, ou d’introduire un
nouveau mécanisme de marquage pour résoudre ce problème (c.f. chapitre 6).
90000 90000
80000 80000
70000
60000
60000
50000
50000
40000
40000
30000
30000
20000
20000
10000
10000
0
4
2
0
8
6
4
2
0
8
6
4
2
0
8
6
4
2
0
8
6
4
2
0
8
40
48
56
64
72
80
88
96
0
10
11
12
12
13
14
15
16
16
17
18
19
20
20
21
22
23
24
24
25
26
27
28
28
1 4 7 10 13 16 19 22 25 28 RTT (ms)
a temps (s) b
Dans cette simulation, la situation étudiée dans les sections 5.4.4 et 5.5.4 est analysée quand le
TCM est utilisé comme mécanisme de conditionnement. Comme pour les autres simulations, cinq
agrégats sont formés à partir de 60 sources TCP à RTT aléatoire borné. La relation entre r et CIR reste
2r/3; les relations utilisées pour calculer les autres paramètres restent aussi inchangés. La figure 5.30
montre le résultat des simulations.
450000 400000
360697
400000 350000
350000
300000 282284
debit moyen (octets/s)
debit agregé (octets/s)
300000
250000
228766
A
250000 B
C 200000
D 169222
200000
E
150000
150000
105012
100000
100000
50000
50000
0
0
A1:S(1,1) - S(1,12) A2:S(2,1) - S(2,12) A3:S(3,1) - S(3,12) A4:S(4,1) - S(4,12) A5:S(5,1) - S(5,12)
0
16
24
32
40
48
56
64
72
80
88
96
2
10
11
agregats TCP
a temps (s) b
dans le calcul de la priorité par le TCM suivant. Cette capacité peut être utilisée pour améliorer la
distribution de ressources au sein d’un agrégat.
La figure 5.31 montre le débit observé par flux pour deux architectures différentes; les flux
étant regroupés par agrégat. Dans la première architecture seul les agrégats sont conditionnés. Dans la
deuxième, des conditionneurs sont implantés à l’entrée de chaque microflux pour informer le marqueur
d’agrégat sur le comportement des sources (c.f. figure 5.8). Tous les marqueurs des sources
individuelles ne peuvent être configurés qu’à partir des mêmes paramètres. Dans un cas réel, il est
impossible, pour un marqueur de flux individuel, de connaître les caractéristiques du conditionneur
d’agrégat ni combien de flux forment le macroflux auquel la source appartient. Pour la deuxième
simulation, le CIR est fixé à 15Ko/s, ce qui devrait être la valeur moyenne des débits assurés par flux.
5 0 0 0 0
4 5 0 0 0
4 0 0 0 0
débit observé (octets/s)
3 5 0 0 0
3 0 0 0 0
2 5 0 0 0
2 0 0 0 0
1 5 0 0 0
1 0 0 0 0
5 0 0 0
0
a 3 0 0 K o /s 2 4 0 K o /s 1 8 0 K o /s 1 2 0 K o /s 6 0 K o /s
s o u rc e s T C P
3 5 0 0 0
3 0 0 0 0
débit observé (octets/s)
2 5 0 0 0
2 0 0 0 0
1 5 0 0 0
1 0 0 0 0
5 0 0 0
0
b 3 0 0 K o /s 2 4 0 K o /s 1 8 0 K o /s 1 2 0 K o /s 6 0 K o /s
s o u rc e s T C P
250000 241058
223033
211167 215258
debit moyen (octets/s)
200000
159858
150000
100000
50000
0
200Ko/s 160 Ko/s 120 Ko/s 80 Ko/s 40 Ko/s
agregats TCP
Le graphique b de la figure 5.31 et la figure 5.32 prouvent que, si la capacité d’enchaîner les
conditionneurs peut être bénéfique, elle n’est pas utile pour résoudre le problème auquel on s’intéresse
dans cette simulation. La fonction utilisée par le TCM pour calculer une priorité en fonction du
comportement d’un flux et de la priorité initiale des paquets limite la différentiation qui peut être
obtenue quand les microflux composant les agrégats ont été pré-marqués. Dans le chapitre suivant,
cette situation est étudiée en détail et des modifications au TCM sont proposées pour améliorer la
distribution de ressources entre les microflux tout en respectant la relation d’ordre qui est imposée pour
aux agrégats.
Pour terminer cette section, la troisième situation d’étude a été mis en place dans le simulateur.
Nous cherchons à découvrir le niveau de protection que le marquage par TCM peut offrir aux flux
adaptatifs. La topologie et les caractéristiques des sources pour cette simulation sont identiques à celles
de la section 5.5.5. Deux douzaines de sources TCP et 8 flux CBR UDP partagent un lien RIO3 à 10
Mbps. Un TCM est initialisé par microflux. Comme pour le TSWM, le CIR est fixé à 2r/3 pour
améliorer les proportions des paquets de chaque niveau de priorité. A partir de l’expérience acquise
avec les conditionneurs précédents, les paramètres de configuration du TCM sont différents pour
40000
70000
35000
60000
débit observé (octets/s)
30000
30000
15000
20000
10000
10000
5000
0
0
0 12 24 36 48 60 72 84 96 108 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a temps (s) b flux UDP (1-8), flux TCP (9-32)
Figure 5.33: différentiation par TCM, protection offerte aux flux TCP
La figure 5.33, présentant le comportement et le débit moyen pour chaque source, satisfait nos
expectatives. Il était effectivement nécessaire d’accorder un débit assuré plus important aux flux TCP
pour que la non-adaptabilité des flux UDP soit pénalisée. Tel que dans la figure 5.23, des valeurs
identiques pour les deux types de marqueurs aurait été avantageuse pour les flux non adaptatifs. Nous
ne détaillons plus le résultat de cette simulation qui est, en général, très bon. Le chapitre 7 est dédié
dans sa totalité aux problèmes liés au marquage de flux UDP.
Nous avons étudié dans cette section la proposition standardisée pour le marquage à trois
couleurs. D’après nos simulations, le TCM peut offrir une différentiation de flux individuels similaire à
celle du TSWM. Par contre, le comportement observé dans le conditionnement d’agrégats est moins
satisfaisant. Avec le TCM, les flux adaptatifs peuvent être protégés d’autres types de flux en suivant le
même principe que le PTB. En ce qui concerne l’influence du RTT sur le débit atteint par des
connexions TCP, le marqueur n’offre aucune amélioration.
5.7. Conclusion
Ce chapitre nous a permis de démontrer que des services basés sur AF peuvent être construits à
partir de la notion de marquage différentié. Bien que le partage de ressources ne soit pas
mathématiquement exact, la différence entre la bande passante accordée à certain flux par rapport aux
autres est suffisamment importante pour que les trois propositions présentées dans ce chapitre servent
de base à la définition des services intra-domaine. L’étude des performances du PTB, du TSWM et du
TCM peut être résumée par le tableau 5.9.
équité entre flux TCP avec le proche du excès proche du 100% proche du 100%
même RTT équitable (eq. 5.2) équitable (eq. 5.1) équitable (eq. 5.1)
équité entre flux TCP avec des non équitable non équitable non équitable
RTT différents Réduction dans le Réduction dans le
taux d’utilisation taux d’utilisation
Les informations du tableau récapitulatif nous permettent de tirer les conclusions suivantes:
Les trois mécanismes peuvent assurer l’équité entre flux TCP quand leur RTT est identique.
Les trois marqueurs peuvent distribuer les ressources de manière pondérée entre agrégats TCP.
Les trois conditionneurs sont capables de protéger les flux adaptatifs des non adaptatifs.
Aucune des trois propositions prend en compte l’effet du RTT sur la performance de TCP, limitant
leur capacité à différentier entre des connexions TCP avec des RTT différents et à assurer l’équité au
sein des agrégats.
Il faut maintenant déterminer laquelle des trois propositions servira de référence dans la
définition de nouveaux conditionneurs. Le PTB n’exploite pas, en général, l’existence de trois priorités.
Le TSWM est un conditionneur difficile à comprendre, en partie à cause de la méthode de calcul du
débit moyen. Etant donné que le TCM utilise un algorithme basé sur une méthode de caractérisation
simple, dont les paramètres sont faciles à maîtriser, il est pris comme point de départ dans la définition
des nouveaux marqueurs. Ces nouveaux conditionneurs, introduits dans le chapitre suivant, cherchent à
résoudre les déficiences découvertes lors des analyses présentés dans ce chapitre.
Cette section introduit un nouvel élément DiffServ destiné au conditionnement des flux TCP
individuels. Il a été explicitement conçu pour réduire la disparité existant entre deux sessions TCP dont
le RTT est différent. Un tel élément diffère des propositions du chapitre 5 dans le sens qu’il n’est pas
conçu pour un usage général. Le BSM (Burst Sensitive Marker) effectue des fonctions spécifiques dont
l’usage est réservé à des cas précis. Il ne peut être utile que lors de sa mise en place pour le
conditionnement de sources TCP individuelles.
Les simulations du chapitre précédent (cf. section 5.2.2) nous ont permis de constater que TCP
est, dans la plupart des cas, un protocole inéquitable. Le débit atteint par une session individuelle
dépend considérablement du niveau d’interactivité entre l’émetteur et le récepteur. Le niveau
d’interactivité est représentée par le temps d’aller-retour de la connexion ou RTT (Round Trip Time).
Les destinataires logiquement éloignés de la source nécessitent d’un temps plus important pour
informer l’émetteur sur l’état de congestion dans le chemin. Les émetteurs dans ce cas génèrent des
rafales importantes qui seront marquées non conformes si un conditionnement est mis en place.
Pour réussir une distribution de ressources plus équitable, il faut conditionner de manière plus
stricte les flux TCP dont le RTT est court. En limitant le débit qui peut être atteint par ces connexions,
les autres sessions, à RTT long, peuvent récupérer la bande passante disponible. Aucun des
conditionneurs déjà étudiés ne prend en compte le RTT. Ce paramètre est difficile à préciser au niveau
trois (couche réseau) si aucune collaboration existe avec la couche supérieure (niveau TCP). Le modèle
DiffServ pourrait être modifié pour que le protocole de transport prenne en compte les informations de
QoS mais une telle modification romprait le principe de transparence existant. Une autre possibilité
consiste à déterminer le niveau d’interactivité d’une session TCP à partir de l’observation du flux. Le
BSM, proposé dans cette section, part de cette possibilité.
La définition du BSTB s’est inspirée d’un analyse rapproché du comportement du seau à jetons
face à une source TCP. La figure 6.1 montre le comportement de trois flux TCP NewReno dont le RTT
est de 100, 200 et 300 ms. Ces graphiques ont été obtenus à partir des simulations destinées à mesurer
la capacité de différentiation du PTB pour des flux TCP individuels (cf. section 5.4.3). La figure montre
le nombre (axe des ordonnées) et la couleur des paquets produits entre la quatrième et la douzième
seconde (axe des abcisses). Les mesures n’ont pas été prises dès la première seconde pour éviter les
fluctuations propres à l’algorithme de "slow start".
20 20 20
16 16 16
12 12 12
8 8 8
4 4 4
0 0 0
4 5 6 7 8 9 10 11 4 5 6 7 8 9 10 11 4 5 6 7 8 9 10 11
Pour notre étude, une "rafale" dénote l’envoi d’un ou plusieurs paquets après un certain temps
d’inactivité. Suite à l’observation de différents types de flux TCP, nous considérons qu’une rafale se
termine quand l’intervalle entre deux paquets dépasse 10 ms.
Deux constats peuvent être faits à partir des trois graphiques de la figure 6.1. En premier, la
fréquence des rafales augmente quand le RTT augmente. Ce comportement est logique, puisque les
connexions à RTT long doivent attendre les acquittements du récepteur avant de transmettre des
nouvelles informations. En second, les flux avec un RTT long produisent des rafales plus importantes
que ceux avec un RTT court. Par conséquence, les connexions à RTT long peuvent se voir marquer
consécutivement un nombre important des paquets comme étant non conformes (graphique à droite).
Sm = Sm ( 1 – wa ) + wa δ eq. 6.1
où wa représente le poids attribué à chaque nouvel échantillon. La figure 6.2 montre l’évolution
du Sm pour les 3 flux étudiés pendant une simulation de 120 secondes. Ces flux sont en concurrence
avec 29 autres sources comme indiqué dans la situation de la section 5.4.3. Pour cette simulation, Sm a
été initialisée à 150 ms et wa est fixé à 1/64.
0.3000
0.2500
0.2000
100 m s
Sm (s)
0.1500 200 m s
300 m s
0.1000
0.0500
0.0000
1 11 21 31 41 51 61 71 81 91 101 111
tem ps (s)
Figure 6.2: évolution du Sm pour 3 flux TCP (RTT de 100, 200 et 300 ms)
La figure 6.2 prouve qu’il existe une relation entre le Sm et le RTT de chaque session. La valeur
moyenne de la variable est de 115, 166 et 190 ms pour un RTT de 100, 200 et 300 ms respectivement.
Pour la totalité des flux participant à la simulation, le Sm moyen varie entre 100 et 200 ms, ce qui
explique pourquoi la valeur initiale est fixée à 150 ms.
Pendant 65 secondes, la relation d’ordre est respectée entre les trois séries présentées dans la
figure 6.2. Plus significatif encore, l’écart entre les valeurs est assez important pendant les premiers
secondes. Cette caractéristique est décisive, car le conditionnement pendant les premiers instants d’une
session TCP détermine en grande partie l’agressivité de la source par la suite.
En partant d’un seau à jetons classique (cf. section 2.2), l’approche qui a été suivie pour inclure
l’information sur les rafales dans le conditionneur consiste à soustraire les jetons en fonction de la
valeur de Sm. Pour conditionner plus fermement les sessions à haute interactivité, la quantité de jetons à
Il est souhaitable que la valeur de Q soit proche de L pour faciliter la comparaison du BSTB
avec d’autres techniques basées sur le seau à jetons. Dans la figure 6.2, on peut déduire que Sm varie
entre 80 et 250 ms. La substitution de valeurs dans l’équation 6.2 indique que le comportement souhaité
est atteint si un α entre 4 et 12 est choisi. Dans l’exemple qui suit, le paramètre α porte une valeur de 8.
Un tableau comparant la qualité de différentiation pour plusieurs valeurs de α est présenté dans la
section suivante, où plusieurs BSTB sont utilisés pour construire le BSM (Burst Sensitive Marker).
A titre d’exemple, le BSTB a été mis à l’épreuve dans les mêmes conditions que le PTB dans la
section 5.4.3. 32 flux TCP dont le RTT varie entre 40 et 300 ms sont transmis à travers un lien central
de 10 Mbps dans lequel RIO3 est installé (c.f. figure 5.13). Chaque source commence à transmettre
dans un instant aléatoire entre 0 et 1 secondes pour éviter la synchronisation. Un BSTB configuré par le
triplet {r,b,α} égal à {20Ko/s, 40Ko, 8} a été utilisé pour marquer chaque source. La figure 6.3 montre
le résultat de cette simulation.
100000 100000
90000 90000
80000 80000
70000 70000
débit observé (octets/s)
60000 60000
50000 50000
40000 40000
30000 30000
20000 20000
10000
10000
0
0
1 4 7 10 13 16 19 22 25 28 40 72 104 136 168 200 232 264
Figure 6.3: équité offerte par BSTB, flux TCP à RTT différent
En comparant la performance du BSTB avec celle du PTB (section 5.4.3), une légère
amélioration est déjà perceptible. Le rapport max/min entre les débits passe de 3,32 à 2,33 ; l’écart type
étant réduit de 37% (11291 contre 7152). Le taux d’occupation obtenu avec le BSTB est supérieur de
5% (87%). Ce comportement bien que meilleur ne peut pas encore être considéré comme équitable.
calcul de Sm
SI δ > 0.010 secondes
Sm = Sm*(1 - wa) + wa*δ
soustraction de jétons
Q = L / (α*Sm)
SI Q <= Tn
T n = Tn - Q
conforme = OUI
SINON
T n = Tn (le niveau n’est pas modifié)
conforme = NON
6.1.2.1 Définition
Le Burst Sensitive Marker (BSM) est un marqueur à trois couleurs similaire au TCM (cf.
section 5.6.). Il base son fonctionnement sur l’utilisation de seaux à jetons dépendants. Il existe pourtant
deux différences entre les deux. En premier, le BSM est basé sur le BSTB, un variation du Token Bucket
classique. En deuxième, le BSM peut être configuré pour limiter le débit qu’une source peut injecter à
l’aide d’un troisième sceau à jetons inexistant dans le TCM. Dans cette section, le BSM est introduit,
son algorithme est expliqué et le choix des paramètres de configuration est déduit à partir des
simulations.
La figure 6.4 présente un schéma simplifié du BSM. Le mécanisme utilise trois seaux à jetons
sensibles aux rafales, Tc, Te et Tm. Le premier seau caractérise le trafic assuré; le deuxième, le trafic en
excès et le dernier, le trafic maximal que la source peut produire. Chaque seau est configuré par un
triplet {r, b, α}, qui dénote le débit, la taille et le facteur d’agressivité du BSTB. Le flux est en premier
vérifié par Tm. S’il n’est pas considéré conforme, le paquet est éliminé. Ensuite, si la vérification par Te
est négative, le paquet est rouge. Autrement le paquet peut être marqué vert ou orange, en fonction du
contrôle effectué par Tc.
BSTB BSTB BSTB
Tm c on form e Te con fo rm e Tc co n fo rm e
VERT
{r m ,b m ,αm } {r e ,b e ,αe } {r c ,b c ,αc }
n o n co n form e n on c on fo rm e
ORANGE
n on c on fo rm e
DROP RO U G E
L’algorithme du BSM, représenté par le code 6.2, est inspiré de celui du TCM à débit double
(cf. section 5.6.2). A l’instant 0, les seaux sont remplis. Par la suite, Tm est débité à chaque fois qu’un
nouveau paquet arrive à condition que les jetons respectifs soient disponibles dans le seau. Si le paquet
est conforme à Tm, Te et Tc peuvent alors être débités suivant le même principe. Les trois seaux sont
remplis à une vitesse de rm, re et rc respectivement. Le BSM a été mis en œuvre dans le simulateur NS.
L’étude sur le partage de bande passante avec 32 sessions TCP avec des RTT différents (cf.
section 5.6.4) a été prise comme modèle pour la mise au point du BSM. Dans cette situation, une bonne
différentiation est observée si chacune des sources obtient une partie égale de ressources, c’est-à-dire, si
le rapport max/min entre les débits mesurés, est proche de 1.
Qm = L / (αm*Sm)
Qe = L / (αe*Sm)
Qc = L / (αc*Sm)
si Tm(t) - Qm < 0
le paquet est ELIMINÉ
Le niveau des sceaux n’est pas modifié
si Te(t) - Qe < 0
Tm = Tm - Qm (décrémenté jusqu’à zero)
le paquet est rouge
sinon
le paquet est vert
Tm = Tm - Qm (décrémenté jusqu’à zero)
Te = Te - Qe (décrémenté jusqu’à zero)
Tc = Tc - Qc (décrémenté jusqu’à zero)
Tc Te Tm
r rc 2rc 4rc
b 3/ 3/ 3/ r + b
2rc 2re + bc 2 m e
Tableau 6.1: relation servant à la configuration du BSM
Un facteur α égal à 8 a été utilisé dans la section précédente. Ce choix est validé par
l’expérience qui suit : à partir des paramètres du tableau de la figure 6.5, où la taille et le débit des seaux
2.50
2.39
Tc Te Tm
2.00
rapport max/min
r 20Ko/s 40Ko/s 80Ko/s 1.50
1.67
α 4 - 12 4 - 12 4 - 12 0.50
0.00
4 5 6 7 8 9 10 11 12
facteur alfa
Le facteur α joue un rôle fondamental dans l’opération du BSM : une valeur trop petite peut ne
pas protéger les flux TCP avec un RTT long. De même, une valeur trop importante peut pénaliser
excessivement les sources avec un RTT court. Pour la situation étudiée, dans laquelle toutes les sources
cherchent à obtenir la même quantité de ressources, une valeur de 8 est le meilleur choix. Le taux
d’occupation augmente quand α augmente: il va de 84% pour α=4, jusqu’à 92% pour α=12. Quand
α=8, la ligne est occupée à 91%. Dans ce domaine, il peut être dit que la valeur choisie offre aussi une
bonne performance.
Si l’utilisation du BSM améliore considérablement le niveau d’équité (rapport max/min réduit à
1,20; écart type autour de 1600 octets). Il reste à vérifier si ce comportement reste stable dans d’autres
situations. Un nouveau cas a été étudié, celui de la section 5.6.3, où 32 sources TCP continuent à
partager un lien central. Aucune agrégation intermédiaire n’est faite. Contrairement au cas précédent, la
configuration des marqueurs varie d’une source à l’autre. La distribution de ressources doit refléter la
différence entre les politiques de marquage. Par exemple, si les débits assurés sont fixés à 32, 24, 16 et
8 Ko/s, une bonne différentiation existe si un rapport de 4, 3, 2, 1 est mesuré pour les débits atteints par
les sources.
Suite à cette simulation il a été conclu que α n’est pas indépendant du rc. Le marqueur doit être
plus agressif avec les sources dont le débit assuré est plus important. Des nouvelles expériences ont été
menées pour trouver la relation qui doit exister entre les deux paramètres. La figure 6.6 compare le
niveau d’équité pondérée pour différents rapports entre α et rc. Dans cette situation, vu que rc est
variable, l’équité est mesurée par le rapport entre les débits mesuré/assuré.
Si la figure montre des performances similaires pour f=3 et f=4, la meilleure différentiation est
obtenue avec f=4. Dans la sous-section suivante, nous présentons le graphique précis du comportement
de chaque source pour cette simulation.
En partant de la formule 5.1, l’intervalle d’efficacité de α est entre 4 et 16. Basés sur ces limites
et sur le résultat précédent, la valeur du paramètre peut être calculée. Soit Rmax le plus grand débit
r (ko/s) b (ko)
2.00 1.99
rapport observé/assuré
1.60
1.50 1.51 1.53 1.52
1.37 1.35
Te 16,32,48,64 36,78,108,144
1.00
Tm 32,64,96,128 84,174,252,336
0.50
α {1,2,3,4}*f 0.00
2 2.5 3 3.5 4 4.5 5 5.5 6
facteur f
assuré dans le système et Rmin le débit assuré minimale, nous définissons l’intervalle Iα. Si, pour une
même valeur de i, le débit assuré accordé à deux sources satisfait la relation :
iI α ≤ r c – R min < ( i + 1 )I α
le facteur α à configurer dans les deux marqueurs doit être identique. De manière plus générale, les
formules suivantes montrent la méthode de calcul de α.
R max – R min
I α = ---------------------------
-
12
r c – R min
α = INT --------------------- + 4
Iα
Cette formule est utilisée dans les simulations de la sous-section suivante aussi bien que dans les
simulations combinant le BSM avec d’autres marqueurs qui sont présentées à la fin de ce chapitre.
6.1.3 Simulations
Une description détaillée des deux simulations qui ont servi à la mise au point du BSM est
présentée dans cette sous-section. A titre comparatif, un tableau montre la différentiation observée pour
chaque topologie en fonction du marqueur utilisé. En fin de section, les conséquences du contrôle de
débit à l’entrée du réseau sont analysées.
Les deux situations que nous présentons sont inspirées des sections 5.2.1 et 5.2.2 : 32 flux TCP
à RTT différent partage un lien à 10 Mbps où RIO3 est configuré à partir des paramètres du tableau 5.1.
La capacité des liens entre les sources et le backbone est telle que la congestion est concentrée sur le
lien central. Un marqueur agit indépendamment sur chaque source. La simulation varie d’un cas à
l’autre dans le sens où la configuration des conditionneurs change. Dans le premier test, des paramètres
identiques sont utilisés pour forcer l’équité entre les sources. Pour le second, des paramètres différents
servent à obtenir un partage pondéré de la bande passante.
Suite à la mise au point des paramètres, le BSM a été configuré à partir du tableau 6.2. Il est
mis en place à l’entrée du réseau pour chaque source. La figure 6.7 montre le comportement de chaque
source et le débit atteint par connexion. Cette figure peut être comparée avec la figure 5.29 pour
apercevoir la différence de performances entre le BSM et le TCM.
100000 100000
90000 90000
80000 80000
70000 70000
débit observé (octets/s)
50000 50000
40000 40000
30000 30000
20000 20000
10000
10000
0
0
1 4 7 10 13 16 19 22 25 28 40 72 104 136 168 200 232 264
r (octets/s) b (octets) α
Tc 20.000 30.000 8
Te 40.000 90.000 8
Tm 80.000 210.000 8
Tableau 6.2: paramètres de configuration du BSM
Cette sous-section présente en détail le comportement des flux dans la simulation qui a servi à
déterminer le rapport entre le facteur α et rc. La topologie est composée de 32 flux TCP. Les flux 1-8
sont conditionnés avec rc=32 Ko/s. Pour les sources 9-16, 17-24 et 25-32 le débit assuré est fixé à 24,
16 et 8 Ko/s respectivement. Le débit en excès acceptable et la taille des seaux sont déduits à partir des
relations de la sous-section 6.1.2.2. Le facteur d’agressivité α porte des valeurs de 16, 12, 8 et 4, en
fonction du débit assuré. Le résultat de la simulation est présenté dans la figure 6.8.
100000 70000
90000
60000
80000
70000 50000
débit observé (octets/s)
60000
40000
50000
30000
40000
30000
20000
20000
10000
10000
0
0
1 4 7 10 13 16 19 22 25 28 40 72 104 136 168 200 232 264
Le résultat de cette simulation a été comparé aux paramètres d’équité définis dans la section
5.4.2. Le tableau 6.4 indique que le comportement du BSM est proche du 100% équitable. D’ailleurs, le
marquage, en grande partie grâce au choix des facteurs α, accentue la différentiation entre les 4 types de
flux. Les sources avec un rc plus important obtiennent plus de ressources au delà du débit assuré.
Pour terminer, les capacités du BSM sont comparées à celles des marqueurs du chapitre 5. La
figure 6.9 montre deux paramètres caractérisant la différentiation : le rapport max/min entre les flux du
même type et le rapport entre les débits mesuré/assuré. Dans le premier cas, plus le rapport est proche de
1, mieux les ressources seront partagées. Dans le deuxième cas, une bonne différentiation est atteinte
quand le rapport reste constant pour tout type de source; mais aussi quand le marquage différentiée
agrandit l’écart entre sources marquées différemment.
2.00 3.00
1.80 2.60
rapport mesuré/assuré
rapport max/min
1.60 2.20
PTB PTB
TSW TSW
TCM TCM
1.40 BSM 1.80 BSM
1.20 1.40
1.00 1.00
32K 24K 16K 8K 32K 24K 16K 8K
débit assuré (octets/s) débit assuré (octets/s)
A partir de la figure 6.9, il peut être affirmé que le BSM offre une meilleur différentiation pour
la situation étudiée. Le rapport max/min est proche de 1 et reste presque constant pour les 4 types de
sources. En ce qui concerne le rapport débit mesuré/assuré, la pente négative ne fait que confirmer
l’information du tableau 6.4 : le BSM augmente l’écart entre sources marquées différemment. Mis à
part le BSM, le TSW est le marqueur qui offre le meilleur comportement.
Une nouvelle simulation a été réalisée pour vérifier les conséquences de la limitation de débit
sur le taux d’occupation. 32 flux TCP traversent un lien central dont la capacité C varie uniformément
de 6 a 30 Mbps. Par conséquent, la longueur de la file d’attente dans le routeur attaché à ce lien qlen est
modifiée en respectant la relation qlen=20C. Avec cette formule, pour une capacité de 10 Mbps, la file
d’attente peut accepter jusqu’à 120 paquets. RIO3 est configuré à partir des paramètres du tableau 5.1
en fonction de la qlen. En faisant varier la capacité C de 6 à 30 Mbps, le rapport entre le débit disponible
et le débit total assuré passe de 117% à 586%.
Chaque source est connectée au routeur central par un lien dédié à 10 Mbps, afin de concentrer
les pertes sur le cœur du réseau (cf. section 5.3.2). Le TCM et le SBM ont été utilisés pour conditionner
90%
6.00
80%
5.00 70%
taux d'occupation
rapport max/min
60%
4.00
SBM SBM
50%
TCM TCM
3.00
40%
2.00 30%
20%
1.00
10%
0.00 0%
6 8 10 12 14 16 18 20 22 24 26 28 30 6 8 10 12 14 16 18 20 22 24 26 28 30
a débit lien central (Mbps)
b débit lien central (Mbps)
Figure 6.5: comparaison de performances SBM vs. TCM: relation max/min et taux d’occupation
D’une part, le graphique a permet de vérifier que le BSM distribue plus équitablement la bande
passante dans des situations de sous-dimensionnement, aussi bien que sur des liens sur-dimensionnés.
Pendant que pour le SBM le rapport entre la source qui obtient le plus de ressources et celle qui obtient
le moins varie de 1,3 à 2; cette même relation atteint 6,47 quand beaucoup de ressources sont offertes
aux flux marqués avec le TCM. La différence entre deux TCPs marqués avec les mêmes paramètres est,
dans ce cas, concentrée sur le pourcentage de paquets rouges. Plus il y a des paquets rouges qui
traversent le réseau, plus la différence entre les flux à RTT court et à RTT long est importante.
6.1.4 Conclusion
Nous avons présenté dans cette section un nouveau type de conditionneur, le marqueur sensible
aux rafales. Dans les situations étudiées, cet élément DiffServ offre une bonne distribution de
ressources malgré les différences de RTT entre les connexions concurrentes. D’ailleurs, l’utilisation
d’un troisième BSTB pour limiter le débit d’une connexion n’affecte pas le taux d’occupation. Plus que
de limiter le débit, le Tm du BSM freine la croissance exponentielle de TCP dans la phase de slow-start,
permettant aux flux avec un RTT long de rattraper le retard.
La performance du BSM est acceptable pour les cas d’étude, son application est immédiate
dans des services intra-domaine où les flux ne sont marqués qu’une seule fois. Il peut être mis en œuvre
dans les hôtes produisant des flux TCP pour améliorer la distribution de ressources et augmenter le taux
d’utilisation des liens. Des propositions récentes [ref] conseillent d’améliorer la distribution de priorités
au sein d’un flux TCP en introduisant un mécanisme de mise en forme entre la source et le
conditionneur. Nous considérons que la complexité d’un tel approche n’est pas justifiée si des
marqueurs conscients des caractéristiques de TCP, comme le BSM, sont utilisés.
Cette section présente un algorithme de marquage destiné à tout type de flux: le PAM
(Pro-Active Marker). Comme le BSM, présenté dans la section précédente, ce conditionneur est basé
sur l’utilisation du seau à jetons. Le but qu’il poursuit est pourtant différent: le PAM est un mécanisme
à usage général centré sur la protection des paquets prioritaires.
Dans les services basés sur le Comportement Assuré il est indispensable d’assurer qu’un paquet
marqué prioritaire le reste pendant tout le chemin. Si le premier marquage est effectué directement par
la source, la priorité peut refléter l’importance du paquet pour l’application. Si le flux est marqué en
premier par le routeur d’entrée dans le réseau, la distribution de priorités reflète le niveau de conformité
du flux par rapport au contrat individuel de la source. Dans les deux cas, un bon fonctionnement des
algorithmes de marquage dépend du respect de cette priorité attribuée initialement tout le long de la
route.
Au niveau des routeurs, les paquets prioritaires peuvent être protégés avec un grand niveau de
précision grâce à des algorithmes tel que RIO ou WRED (cf. section 2.4). Par contre, aux points
d’agrégation, où un ensemble de flux est reconditionné en tant qu’un ensemble, cette contrainte peut ne
pas être respectée. Dans le chapitre précédent, nous avons remarqué que seul le TCM peut prendre en
compte la priorité entrante d’un paquet lors du calcul de la priorité sortante. La politique utilisée par ce
conditionneur est très simpliste: il prend le minimum entre la couleur du paquet à l’arrivée et la couleur
calculée. Ceci peut résulter en une distribution catastrophique de la bande passante, ce qui a été montré
à la fin de la section 5.6.5.
Le Conditionneur Pro-Actif, PAM, ajoute au TCM un module qui réagit aux dégradations de la
priorité provoquées par le re-marquage. Il peut modifier la priorité ou éliminer, dès l’entrée dans le
conditionneur, les paquets les moins prioritaires. Ceci réduit la concurrence dans les routeurs entre les
paquets prioritaires dégradés et les paquets initialement moins prioritaires; augmentant le nombre de
paquets de haute priorité qui atteignent au récepteur.
La sous-section suivante décrit le cas d’étude que nous avons choisi pour montrer les capacités
de la proposition. Le besoin d’améliorer la protection des paquets de haute priorité est justifié en
analysant le comportement du TCM face à ce cas d’étude. Ensuite, l’algorithme du PAM est présenté.
La situation qui a été retenue pour servir de cas d’étude est très similaire à celle utilisée dans la
section 5.6.5. Une soixantaine de sources TCP, agrégées en 5 groupes de 12, partagent un lien central à
10 Mbps. RIO3 est utilisé dans ce lien. Il existe deux points de marquage. Chaque source est
conditionnée individuellement dès son entrée dans le réseau. Ensuite, dans les nœuds d’agrégation, un
deuxième marquage est effectué sur l’ensemble des sources les traversant.
La situation étudiée dans cette section diffère de celle présentée auparavant au niveau du
conditionnement. Si, dans les nœuds intermédiaires, la configuration des marqueurs n’a pas été
modifiée, au niveau des points d’entrée la configuration est différente. La section 5.6.5 constitue un
exemple de mauvaise configuration puisque le marquage secondaire n’a pas été dimensionné en
fonction des marqueurs primaires. Dans cette nouvelle simulation les marqueurs primaires, ceux à
l’entrée du réseau, sont configurés avec un débit assuré, r, de 25, 20, 15,10 et 5 Ko/s en fonction de la
capacité du prochain marqueur. Les 5 marqueurs secondaires, ceux destinés aux agrégats, sont
configurés avec un débit assuré, r, de 300, 240, 180, 120 et 60 Ko/s. La taille de rafale maximale, b,
équivaut 1,5r octets aussi bien pour les marqueurs primaires que pour les secondaires. La figure 6.10
montre la configuration des marqueurs dans la topologie. L’ensemble de sources composant un agrégat
peut produire jusqu’à 2 fois plus de paquets verts que ceux que le conditionneur secondaire peut
accepter. Un dégradation est donc nécessaire à ce point.
S2,1 25Ko/s
S2,2 E1 R1,1
..
300Ko/s
S2,12
R1,2
S2,1 20Ko/s
S2,2 E2 240Ko/s
.. RIO3
S2,12 B1 B2
E3 lien central
10 Mbps qmax=120
E4 R5,11
S5,1 5Ko/s
S5,2 E5 60Ko/s conditionneur flux individuel
.. conditionneur agrégat R5,12
S5,12
Figure 6.10: topologie utilisée lors de la définition du PAM
Le TCM à débit double (cf. section 5.6.2) a été utilisé en tant que marqueur dans la topologie
présentée ci-dessus. En partant du débit assuré spécifié précédemment, le conditionneur est configuré
suivant les relations de la section 6.1.2.2. Les 60 sessions TCP échangent des données pendant 120
5 0
4 0
débit observé (octets/s)
3 0
2 0
1 0
0
2 0 0 K o /s 1 6 0 K o /s 1 2 0 K o /s 8 0 K o /s 4 0 K o /s
s o u rc e s T C P
Figure 6.11: différentiation à deux niveaux par TCM, débit observé par source
Deux aspects doivent être vérifiés. D’une part, la distribution de ressources entre les agrégats
doit refléter les proportions spécifiés par les paramètres de configuration des marqueurs secondaires.
D’autre part, vu que tous les flux d’un même agrégat ont été conditionnés avec des paramètres
identiques, une bonne différentiation est obtenue si les microflux composant un même agrégat
observent un débit similaire.
Le tableau 6.6 fait une synthèse des résultats obtenus. Le niveau d’équité à l’intérieur de
chaque agrégat est mesuré par le rapport max/min, entre le microflux qui obtient le plus de ressources, et
celui qui obtient le moins. En multipliant le débit moyen des flux composant chaque agrégat par 12 (le
nombre de flux), on obtient le débit observé par l’agrégat dans son ensemble. Cette valeur est comparée
au débit différentié idéal, calculée à l’aide de la formule 4.1.
30
paquets produits (x1000)
rouge
20 orange
vert
10
0
300Ko/s 240Ko/s 180Ko/s 120Ko/s 60Ko/s
m arqu eu rs
Figure 6.12: attribution de priorités par TCM dans les nœuds secondaires
A cause de la fonction de re-marquage du TCM, 28% des paquets initialement verts deviennent
oranges et 8% rentre dans le lien central avec la plus faible priorité, rouge. Ce comportement est
inacceptable pour un service basé sur l’utilisation de priorités. Il n’existe, en effet, aucune garantie pour
qu’un paquet marqué vert (prioritaire) ne soit pas éliminé dans les routeurs intermédiaires. Le PAM,
décrit dans la prochaine sous-section, est un conditionneur plus complet que le TCM. Il est capable de
résoudre le problème grâce à un mécanisme pro-actif et à la limitation de débit.
Le principe derrière l’opération du PAM est simple: quand un paquet de haut priorité dégradé
rentre dans le réseau, il doit partager les ressources avec des paquets initialement moins prioritaires. En
diminuant la priorité des paquets non prioritaires dans le conditionneur avant le marquage, les
ressources disponibles pour une certaine priorité peuvent être réservés aux paquets haute priorité
dégradés. La concurrence au même niveau entre les paquets de deux priorités différentes est évitée.
Contrairement au BSM, qui cherche à améliorer la différentiation entre flux TCP individuels, le
Pro-Active Marker, PAM, reste indifférent au comportement spécifique des protocoles de transport. Il
est conçu pour assurer que le nombre de paquets initialement prioritaires arrivant aux récepteurs soit le
plus élevé possible. Cette fonction est effectuée tout en respectant les contraintes de conditionnement
dans les points d’agrégation. La sous-section précédente n’a montré qu’une des applications possibles
d’un tel élément. Dans le chapitre suivant, nous proposons un service DiffServ destinée aux
applications multimedia qui exploite les capacités du PAM.
Le PAM peut être décomposé en trois éléments comme le montre la figure 6.13. Les paquets
conditionnés par cet élément arrivent au module pro-actif; où des mesures correctives sont prises pour
protéger les paquets de haute priorité. Dans le module vérificateur, le niveau de priorité sortante est
calculée; l’élément pro-actif étant informé des dégradations effectués. Enfin, dans l’élément marqueur
la priorité calculée par le vérificateur est inscrite dans les paquets.
feedback
élém en t
pro-actif v érificateur m arq ueu r
rejet rejet
Le principe du PAM peut être vu comme l’introduction d’une quatrième couleur dans la
différentiation. Dans la version actuelle, cette nouvelle couleur est représentée par le rejet au niveau du
conditionneur. Des versions futures pourraient accepter la transmission des paquets non conformes au
Tm, mais avec une priorité plus faible que celle accordée aux paquets rouges.
Cet élément base son opération sur l’information qui lui est transmise par le vérificateur. Seul
le vérificateur connaît quel est la priorité d’un paquet à l’arrivée et à la sortie. Quand le niveau de
priorité dans le deux cas n’est pas le même, il s’agit d’une dégradation. A chaque fois qu’un paquet se
voit diminuer sa priorité l’élément pro-actif est informé. A partir de ces informations, l’élément décide
orange->rouge rouge_out++
orange->drop rouge_out += NR
Le paquet, s’il n’a pas été éliminé, passe ensuite au vérificateur possiblement dégradé. Il faut
noter que seules les dégradations effectuées par le vérificateur sont prises en compte. Les actions
entreprises par l’élément pro-actif ne sont pas considérées dans la mise à jour des compteurs.
La fonction d’un vérificateur est de déterminer si un flux est conforme ou non à un certain
profile de trafic. Dans les chapitres précédents, nous avons étudié plusieurs mécanismes qui assurent
cette fonction. Le PAM pourrait fonctionner avec n’importe lequel parmi eux à une seule condition:
que la méthode choisie puisse informer le mécanisme pro-actif sur les dégradations effectuées. Nous
avons décidé d’utiliser un mécanisme basé sur le TCM à débit double afin de faciliter la comparaison
de performances.
En plus de fonctions propres à la vérification, le PAM a été doté d’une fonction de limitation de
débit. Un troisième seau à jetons est utilisé pour indiquer le débit maximal qui peut être produit par la
source. Si le flux n’est pas conforme à ce seau à jetons, ces paquets se verront éliminer dans le
conditionneur. Cette fonctionnalité est optionnelle, son existence n’est pas justifiée dans le
conditionnement des agrégats TCP. La valeur de cette capacité est démontrée dans le chapitre suivant,
lors de l’étude du conditionnement des flux UDP.
Le vérificateur est formé par trois seaux à jetons, Tc, Te et Tm. La version standard du Token
Bucket est utilisée; le BSTB, n’étant pas adapté au marquage des agrégats. La configuration demande
six paramètres: {rc, bc}, {re, be} et {rm, bm}, qui représentent le débit et la taille de chacun des seaux.
Initialement, les seaux sont remplis. Ils sont débités à l’arrivée de chaque paquet suivant la politique
montrée dans les code 5.4. Tc, Te et Tm se remplissent en permanence à une vitesse de rc, re et rm
respectivement jusqu’à atteindre leur taille maximale.
Le pseudo-code 6.4 décrit l’algorithme du vérificateur utilisé par le PAM. Pour faciliter la
lecture, les fonctions propres à la mise à jour des variables comptabilisant les dégradations ne sont pas
présentées. Cette fonctionnalité, nécessaire à l’opération du conditionneur, peut avoir lieu lors de la
détermination de la nouvelle priorité ou à la fin de l’algorithme. L’algorithme 5.4 a été inspiré du TCM
à débit double sensible à la priorité entrante.
si Tm(t) - L < 0
le paquet est ELIMINÉ
Le niveau des seaux n’est pas modifié
sinon
le paquet est vert
Tm = Tm - L (décrémenté jusqu’à zero)
Te = Te - L (décrémenté jusqu’à zero)
Tc = Tc - L (décrémenté jusqu’à zero)
6.2.3 Simulations
En substituant le TCM par le PAM dans les nœuds intermédiaires, la situation d’étude à été
répétée. 5 conditionneurs ont été initialisés dans les nœuds intermédiaires dont le débit assuré, rc, est
fixé à 300, 240, 180, 120 et 60 Ko/s. Le débit en excès acceptable et fixé à 2rc, ce qui est équivalent au
PIR du TCM. Le PAM utilise un troisième seau à jetons, Tm. Il a été configuré avec un débit rm = 4rc.
La taille de seaux respecte la relation 1,5R, où R dénote le débit de remplissage de chaque seau. Enfin,
un niveau de réaction NR=1 a été utilisé. A l’entrée du réseau, le TCM continue à assurer le
conditionnement individuel de chaque source utilisant la configuration de l’exemple précédent. La
figure 6.14 montre le débit moyen observé par chacune des sources pendant les 120 secondes de
simulation. Le RTT de chacune des sources est le même que dans la situation précédente. Le format de
la figure respecte le format utilisé par la figure 6.11.
A première vue, la protection des paquets initialement prioritaires a effectivement eu un effet
positif sur la différentiation. Un écart moins important entre les sources appartenant au même agrégat
4 0 0 0 0
débit observé (octets/s)
3 0 0 0 0
2 0 0 0 0
1 0 0 0 0
0
2 0 0 K o /s 1 6 0 K o /s 1 2 0 K o /s 8 0 K o /s 4 0 K o /s
s o u rc e s T C P
Figure 6.14: différentiation secondaire par PAM, débit observé par source
est observé. Pour être plus précis, le tableau 6.8 présente les informations servant à déterminer le niveau
de différentiation. Il doit être comparé au tableau 6.6.
A partir du tableau il peut être conclu que le PAM, utilisé en combinaison avec le TCM, réduit
la disparité existant au sein des agrégats. Le rapport max/min moyen est divisé par deux. Il est, dans cette
situation de 1,79. Par contre, au niveau de la différentiation entre agrégats, le mise en place du PAM
dans les nœuds secondaires ne suffit pas à assurer une distribution de ressources proche du cas idéal.
30
10
0
300Ko/s 240Ko/s 180Ko/s 120Ko/s 60Ko/s
m arqu eu rs
Figure 6.15: attribution de priorités par PAM dans les nœuds secondaires
La topologie de l’exemple précédent à servi à l’étude d’un nouveau cas. Pour assurer la
compatibilité entre les deux marqueurs proposés, le TCM à l’entrée du réseau à été remplacé par un
BSM. Le conditionneur est configuré suivant le principe de la section 6.1.2.2; le facteur α varie en
fonction du débit assuré rc. La figure 6.16 montre le résultat :
5 0 0 0 0
4 0 0 0 0
débit observé (octets/s)
3 0 0 0 0
2 0 0 0 0
1 0 0 0 0
0
2 0 0 K o /s 1 6 0 K o /s 1 2 0 K o /s 8 0 K o /s 4 0 K o /s
s o u rc e s T C P
Figure 6.16: différentiation secondaire par PAM, débit observé par source
6.2.4 Conclusion
Dans cette section, nous avons exploité la capacité du PAM pour améliorer la différentiation
d’agrégats de flux TCP. Si la couleur d’un paquet reflète le résultat d’un conditionnement précédent, un
meilleur traitement de ce type de paquets dans les points d’agrégation se traduit par une meilleure
distribution de ressources au sein de l’agrégat. Au même temps, la capacité du marqueur à respecter le
profile imposé par le vérificateur assure une bonne différentiation entre l’ensemble d’agrégats. Celle-ci
n’est qu’une utilisation possible du PAM. Dans le chapitre suivant, nous proposons un service DiffServ
destiné aux flux audio/vidéo dans lequel un marquage adapté et l’utilisation du PAM assurent la
protection de la partie sémantiquement importante des flux, améliorant la QoS lors du décodage.
Les flux audio et vidéo diffèrent des flux de données sur plusieurs points. Un flux de données,
par exemple HTTP ou FTP, requiert une transmission fiable. Aucune contrainte ne pèse sur le délai de
transit ni sur la gigue (variation de ce délai dans le temps) et l’objectif principal du protocole de
transmission est le transfert sans faute des blocs de données le plus rapidement possible. TCP offre un
contrôle de congestion qui réagit aux pertes observées en réduisant le débit d'émission et un mécanisme
de retransmission en cas de perte; deux fonctions largement utilisées par les protocoles de transfert de
fichiers.
Les capacités de TCP sont difficilement exploitables pour le transport de flux multimédia. Dans
le cas particulier des flux audio et vidéo la validité, et par conséquent l'utilité, d'un paquet dépend de la
stabilité du temps de transfert. Il ne sert en effet à rien de retransmettre un paquet perdu si celui-ci doit
arriver après que la séquence à laquelle il appartient a été jouée. Non seulement la retransmission est
inutile mais elle consomme des ressources ce qui risque de retarder des nouveaux paquets. Dans ce cas,
il est préférable d'accepter quelques pertes et de maintenir un flux continu et régulier d'information au
niveau du récepteur.
Les contraintes de transmission des flux multimédia ne peuvent être satisfaites qu’en utilisant
un protocole qui ne met pas en œuvre de mécanismes de contrôle d’émission. Les applications audio et
vidéo utilisent principalement UDP pour transporter leur flux, ce qui ne va pas sans conséquence.
D’une part, il est impossible de contrôler le partage de ressources entre flux UDP: le débit observé par
un flux est déterminé en grande partie par l’agressivité de la source. D’autre part, l’augmentation dans
la proportion de flux non adaptatifs réduit les performances des flux TCP, traditionnellement
majoritaires dans le réseau.
Une autre caractéristique importante des flux audio et vidéo est l'importance relative des
différentes parties de l'information. Dans un flux de données tous les paquets sont égaux devant la perte
puisque aucune perte n'est tolérée. Dans un flux audio ou vidéo certains paquets peuvent contenir une
information plus importante, en ce sens que la perte d'un de ces paquets plus importants se traduit par
une dégradation plus importante du son ou de l'image que la perte d'un paquet moins important. Cela
peut même aller jusqu'à rendre une partie de l’information transmise inutile.
Pour que des différences puissent être aperçues entre la valeur sémantique des blocs composant
un flux multimédia, des techniques de compression hiérarchiques ou en couches doivent être utilisées.
Deux techniques sont particulièrement adaptées à la hiérarchisation des flux: la division en fréquences
et le codage différentiel.
La division en fréquences d’un flux multimédia consiste à utiliser des filtres passe-bas ou passe-haut
pour identifier et séparer les fréquences basses et hautes [ARR95][SK95]. Or en vidéo et du fait des
caractéristiques physiologiques de la vision humaine les fréquences basses représentent les
caractéristiques les plus importantes de l'image, tandis que les hautes fréquences en représentent les
détails. A titre d’exemple, la figure 7.1 montre la décomposition en sous-bandes d’une image fixe
[Med1]. L’imagette concentrant les informations basse-fréquence aussi bien en vertical qu’en
horizontal constituerait la partie la plus importante du flux.
Image Originale filtrage horizontal filtrage vertical
PB
signal vertical
signal horizontal
PB
PH
PB
PH
PH
Le codage différentiel consiste à utiliser des références internes aux flux pour réduire la taille des
données. Ainsi l'affichage d'un segment peut dépendre d'un segment précédemment reçu, voir même
d'un segment à venir. Pour la vidéo la technique consiste à transmettre une image complète qui
servira de référence, pour les images suivantes seules les différences d'avec l'image de référence
sont codées. Les algorithmes de codage MPEG [DLG92], utilisent cette technique. La figure 7.2
I B B P B B P B B P B B
Dans la plupart des cas, la perte des informations de basses fréquences ou de l'image de
référence rend inutilisable le reste des informations transmises. La valeur sémantique des informations
contenues dans un paquet joue un rôle important pour ce type de flux. La perte d'information de
référence lors d'une congestion dans le réseau se traduit par une dégradation visuelle considérable à
l'issu du décodage. Au contraire la perte de la même quantité d'information de moindre importance
n'affectera que très peu le rendu de l'information.
La section précédente présente deux caractéristiques essentielles des flux multimédia. D'abord,
il s'agit des transmissions en UDP pour lesquelles le réseau n'a aucun moyen de contrôler le débit
d'émission. Ensuite, l'effet des pertes dans le réseau dépend fortement de la valeur sémantique de
l’information transportée dans les paquets perdus. En utilisant la capacité de l’architecture DiffServ à
différentier des paquets en fonction de leur priorité, il est possible d'améliorer le comportement des flux
audio/vidéo lorsqu'ils subissent des pertes. Le principe est d'attribuer des priorités différentes aux
paquets en fonction de leur valeur sémantique (au sens du codage). Les pertes ne sont pas réduites mais
elles sont concentrées sur les paquets les moins importants. Cela ne dispense pas de mettre en place les
mécanismes nécessaires pour différentier les flux UDP et TCP pour d'une part, protéger les flux TCP
des flux non adaptatifs et, d'autre part, mieux distribuer les ressources entre les flux UDP.
Avant de définir un service spécifique pour les flux multimédia il faut déterminer ce que l'on
attend du nouveau service. Trois aspects ont été identifiés :
1) Le service doit être capable d'attribuer les ressources en fonction d’un contrat de service. Il doit
distribuer la bande passante en fonction du SLS (Service Level Specification) qui s'applique à
chaque flux. Le partage des ressources doit refléter les différences entre les SLS aussi bien dans les
moments de congestion que dans les moments où le réseau est sous-exploité.
3) Enfin, le service doit respecter la priorité qui est attribuée à chaque paquet par la source. Au départ
du paquet cette priorité représente la valeur sémantique, mais elle peut être modifiée par les routeurs
de bordure quand les flux sont agrégés ou quand le comportement de la source dépasse les limites
établies dans le contrat.
En fonction de ces objectifs, il faut se placer dans une optique réseau. Il faut choisir, parmi
toutes les possibilités que DiffServ nous offre, celles qui répondent le mieux aux besoins du service. On
s'intéresse d'abord au choix du PHB, paramètre définissant le comportement des routeurs de cœur du
réseau (cf. section 3.4). Etant données les caractéristiques des streams multimédia, le comportement EF
n'est pas adapté. EF est un comportement coûteux, en particulier à cause des garanties de délai qu'il
peut offrir. Pour le streaming, les variations de délai sont normalement absorbées par un buffer chez le
récepteur, les assurances de délai ne sont donc plus indispensables. Plus important encore, dans EF la
notion de priorité dans les paquets n'existe pas alors que c'est un élément clé du service que l'on cherche
à proposer. AF quant à lui, répond au besoin d'attribuer des priorités aux paquets en offrant trois
niveaux de priorité. Le service multimédia est donc basé sur le Comportement Assuré.
Dans le Comportement Assuré, quatre classes de service ont été définies. Pour le cas de notre
service, cette caractéristique résout facilement le problème de partage de ressources entre les flux UDP
et TCP: en réservant une classe AF au trafic UDP et une autre au trafic TCP, les deux types de flux sont
isolés par l'algorithme d'ordonnancement (cf. section 2.3). D’ailleurs, si la classe réservée au
multimédia est considérée comme prioritaire parmi les classes AF, le service peut simultanément offrir
un service bas-délai. La différence entre ce service pour UDP et le service Premium repose sur
l’absence de contrôle d’admission; ce qui rend le premier moins coûteux, en termes de gestion de
ressources, que le deuxième.
Le dernier élément à définir concerne les actions nécessaires pour assurer le service dans les
routeurs d'entrée. Plus exactement, il faut déterminer le conditionneur qui réagit le mieux quand les
paramètres de trafic accordés (TCS: Traffic Control Specification) ne sont pas respectés. Pour le cas du
service multimédia, les conditionneurs utilisés doivent être capables de limiter le débit injecté dans le
réseau tout en assurant la non dégradation des paquets importants. Le marqueur le plus adapté pour
réaliser ces fonctions est le PAM (Pro-Active Marker), introduit dans le chapitre précédent. Afin de
valider ce choix, la capacité du PAM à fournir le service demandé est comparée à celle du TCM dans la
section suivante.
Nous avons construit un modèle de simulation pour analyser l’opération conjointe des éléments
DiffServ proposés pour mettre en œuvre le service multimédia. La topologie de réseau utilisée est
présentée dans la figure 7.3. Dans notre architecture, 25 sources UDP sont en concurrence sur un lien
central qui fait office de goulot d'étranglement. Il y a 5 blocs composés chacun par 5 sources connectées
à un lien intermédiaire. Les nœuds concentrateurs sont attachés directement au lien central. Les
capacités des nœuds ont été choisies de telle façon que les pertes se produisent uniquement sur le lien
central. Les 5 sources UDP de chaque bloc émettent à un débit de 100, 200, 400, 600 et 800 Ko/s.
Chaque source pré-marque aléatoirement 50% de ces paquets en vert, 25% en jaune et le reste étant
marqué en rouge.
udp50
udp100
udp200
udp300
udp400
lien en
congestion
udp50
udp100
udp200
udp300
udp400
n œ u ds
nœ u ds d’e ntrée inte rm é diaires ré cep te urs
Le marquage est effectué indépendamment pour chaque source en utilisant le PAM. Le débit
assuré, rc, pour chaque source est de 50, 100, 200, 300 et 400 Ko/s, ce qui correspond dans un premier
temps, à la moitié du débit d’émission de chacune des sources. Les nœuds intermédiaires effectuent un
deuxième marquage à l’aide d’un PAM configuré à partir de rc=1050 Ko/s ce qui évite, dans cette
première phase, la perte de priorité due au re-marquage dans les nœuds intermédiaires. Les autres
paramètres nécessaires à la configuration des conditionneurs sont calculés à partir du tableau 7.1. La
taille du seau mesurant le débit maximal, bm, est fixé à 2Ko pour limiter les fluctuations. Il faut signaler
que les flux UDP sont beaucoup moins sensibles aux variations de la taille des seaux. Pour ces
expériences, un niveau de réaction NR=1 a été utilisé.
Tc Te Tm
r rc 1,5rc 2rc
11
800000
10
700000
9
600000 8
x bw réservée
CBR 50K CBR 50K
Débit moyen
7
500000 CBR 100K CBR 100K
CBR 200K 6 CBR 200K
400000 CBR 300K CBR 300K
5
CBR 400K CBR 400K
300000 4
3
200000
100000
1
0 0
0.4 0.6 0.8 1 1.2 0.4 0.6 0.8 1 1.2
Occupation Occupation
Figure 7.4: Débit moyen par type de source. Rapport débit mesuré/assuré
Dans la figure 7.5, le pourcentage de pertes par couleur et par type de source est présenté en
fonction de la capacité du lien central. Nous pouvons vérifier que des pertes apparaissent en premier
lieu sur les paquets rouges. Si la source effectue le marquage correctement ce sont ceux qui transportent
l’information la moins importante. Comme un re-marquage n’est pas nécessaire, la différentiation par
couleur est entièrement assurée par RIO3. Etant donné que le pourcentage de pertes par couleur est
pratiquement le même pour tous les types de source, la figure montre que la dégradation observée par
les récepteurs est similaire.
110
100
90
CBR 50 vert
80 CBR 5 0 ja u n e
CBR 50 rouge
70 CBR 100 vert
% de pertes
CBR 1 0 0 ja u n e
60
CBR 100 rouge
50 CBR 200 vert
CBR 2 0 0 ja u n e
40 CBR 200 rouge
CBR 300 vert
30
CBR 3 0 0 ja u n e
20 CBR 300 rouge
10
0
40% 60% 80% 100 % 120 %
T a u x d e r é s e rv a tio n
Les figures 7.4 et 7.5 confirment la viabilité d'un service DiffServ pour les flux audio/vidéo. Si
toutes les sources restent conformes au contrat accordé, la distribution de la bande passante est
La différentiation entre flux dans AF est en grande partie effectuée en contrôlant le nombre de
paquets verts et jaunes que chaque source émet. Pour des liens chargés, cette différentiation suffit à
partager les ressources conformément aux SLS. Par contre, sur des liens non-chargés, un grande
nombre de paquets rouges réussit à traverser le réseau. Il faut donc contrôler la répartition des
ressources en excès. Dans le standard définissant AF, il est conseillé de limiter le nombre de paquets
rouges qu'une source peut émettre. Dans notre proposition, cette fonction est assurée par le PAM, mais
d'autres techniques pourraient servir à accomplir cette fonction.
Dans la deuxième série de tests, les marqueurs sont configurés avec les mêmes paramètres que
dans la simulation précédente. Par contre, le débit d'émission de chaque source a été fixé a 800 Ko/s.
Ceci simule le cas dans lequel toutes les sources, sauf celles ayant un débit assuré de 400 Ko/s, ne
respectent pas leur contrant. L'utilisation de débits assurés de 50, 100, 200 et 300 Ko/s permet
d'analyser la réaction du réseau pour des niveaux différents de non conformité.
900000 12
11
800000
10
700000
9
600000 8
x bw réservée
CBR 50K 7
CBR 50K
Débit moyen
3
200000
2
100000
1
0
0
40.00% 60.00% 80.00% 100.00% 120.00%
40% 60% 80% 100% 120%
Occupation Occupation
Figure 7.6: Débit moyen par type de source. Rapport débit mesuré/assuré
La figure 7.6 montre la répartition de la bande passante suivant le format de la figure 7.4. Le
contrôle de débit effectué par le PAM force une différentiation conforme aux SLS. Dans ce cas, toutes
les sources, sauf celles dont le débit maximale est de 800 Ko/s, subissent des pertes à l'entrée du réseau.
Ces pertes sont provoqués par le conditionneur. Du fait de l'utilisation de cette fonction il est possible
que la totalité de la bande passante ne soit pas utilisée. Par contre, les ressources sont toujours réparties
équitablement entre les flux. Cette caractéristique n'est pas très gênante pour des flux audio et vidéo
étant donné que les applications cible émettent en général à débit constant. Elles ne peuvent donc pas
profiter directement des ressources en excès.
Une dernière simulation a été effectuée pour observer les conséquences du re-marquage dans le
réseau. Dans certaines situations même les paquets issus de sources conformes à leur SLS peuvent être
détruits. Ces pertes peuvent être le fait d'un mauvais dimensionnement ou d'une situation
exceptionnelle (panne de routeur, modification temporaire des routes, etc.). Pour simuler ce
comportement, le débit assuré au niveau des marqueurs dans les nœuds intermédiaires a été réduit. Il ne
correspond plus qu’à 80% (840 Ko/s par bloc) de la somme de débits assurés pour les sources. L'arrivée
des paquets verts qui deviennent non conformes dans les nœuds intermédiaires va provoquer, comme
dans la simulation précédente, une dégradation du service. Par contre, dans ce cas, cette dégradation est
provoquée par le re-marquage. Il faut donc se concentrer sur l’étude de pertes par couleur. La figure 7.7
montre le résultat de la simulation dans ce sens.
110
100
90
80
70
% de pertes
60 V e rt
Jaune
50
Ro u g e
40
30
20
10
0
50 100 200 300 400
D é b it (K b )
Ce résultat est conforme à celui de la section 6.2.3 où le PAM est utilisé pour conditionner des
flux TCP. Pendant les périodes de congestion extrême, la totalité de paquets originellement rouges est
éliminée à l'entrée. La plupart des paquets jaunes sont éliminés ou dégradés et une partie des paquets
verts est re-marquée en jaune. Le paquets initialement prioritaires sont donc protégés contre les pertes
que le deuxième conditionnement pourrait entraîner.
Il faut noter un deuxième effet positif de l'algorithme du PAM: quand une source dépasse le
débit total autorisé et que des paquets doivent être éliminés, ce sont les paquets marqués en rouge par la
source qui sont éliminés en premier. Dans ce cas, même si la source ne respecte pas le SLS, ce sont les
paquets de haute priorité qui réussissent à atteindre le destinataire.
A titre comparatif, cette section termine par l’analyse de performances du TCM (cf. section
5.6.) quand il est utilisé en tant que conditionneur dans les situations concernées par le service
multimédia. En ce qui concerne la simulation de la section 7.3.1, quand les sources respectent leur
contrat, il n’existe aucune différence entre la différentiation offerte par le TCM et celle du PAM. Quand
11 100
10
90
9
80
8
70
x bw réservée
CBR 50K
% de pertes
7
CBR 100K 60 Vert
6 CBR 200K Jaune
50
CBR 300K Rouge
5
CBR 400K
40
4
30
3
20
2
1 10
0 0
0.4 0.6 0.8 1 1.2 50 100 200 300 400
a Occupation
b Débit (Kb)
Le graphique a, montre que le TCM ne peut pas assurer l’équité quand des ressources en excès
existent. Les sources avec les SLS les plus contraignants obtiennent le pourcentage le plus élevé de
ressources par rapport au contrat. Le marquage d'une source non conforme génère un grand nombre de
paquets rouges. Ce nombre varie en fonction du degré de non conformité du flux. Dans le routeur du
backbone, il n'existe plus de distinction entre les paquets marqués en rouge par la source et les paquets
qui ont été re-marqués par le TCM. Il se peut donc, qu'une source qui respecte son contrat soit affectée
tandis qu'une source non conforme profite des ressources en excès disponibles.
Quant au graphique b, la distribution de pertes par couleur correspond au résultat observé dans
la section 6.2.1. Avec le TCM, la probabilité d'avoir un paquet vert re-marqué en jaune dépend
fortement de la présence des paquets jaunes générés par les sources. Dans cette simulation, des paquets
originellement jaunes consomment tous les jetons du seau et la plupart des paquets verts à dégrader sont
colorés directement en rouge. Dans le lien central, les paquets verts et jaunes dégradés en rouge se
confondent avec les paquets initialement rouges. Nous pouvons d'ailleurs constater sur la figure 7.8,
que le pourcentage de perte pour les paquets initialement rouges n'atteint pas 60%, tandis que les
paquets verts et jaunes subissent 30% de pertes. Dans le même temps, les pourcentages de perte pour
l’informations vertes et oranges sont équivalents; ce qui met en évidence une diminution de la capacité
de différentiation du réseau.
Dans les deux situations étudiées, où une bonne performances est indispensable au bon
fonctionnement du service multimedia, le PAM propose un meilleur conditionnement que le TCM.
L’utilisation de ce marqueur dans la mise en place du service est donc justifiée.
Cette section ne décrit pas la mise en œuvre des mécanismes DiffServ nécessaires à
l’implantation du service multimédia dans un réseau. Ces fonctionnalités sont déjà couvertes par la
souche ADServ, décrite dans le chapitre 3. Cette section est centrée sur la description d’une application
tirant profit des capacités de différentiation: le SD6 (Streamer Multimédia DiffServ/IPv6), développé à
l’ENSTB. Nous décrivons l’état actuel de cet outil; des travaux sont en cours pour augmenter les
capacités de l’application.
Le schéma de la figure 7.9 montre les différents modules qui composent l’application. Le SD6
est formé par un noyau générique chargé de toutes les fonctions de réseau. A ce noyau s’ajoute un
nombre de modules destinés au traitement de flux particuliers. Un module différent est nécessaire pour
chaque type de fichier multimédia. Ces modules, présents symétriquement dans le client et dans le
serveur, réalisent la fonction d’attribution de priorités indispensable au service DiffServ.
m pegsystem m pegsystem
serveur client
audio m p3 audio m p3
... ...
noyau réseau
modules modules
Figure 7.9: schéma logique du DS6, un client/serveur DiffServ.
serveur client
module de interface
contrôle interactive
buffer
flux de données (UDP) réception
d’où la nécessité de créer un module par format. Actuellement, deux modules sont disponibles: un
module MPEG2 Vidéo [iso94b] et un module audio pour les fichiers au format .au (µ-law) [g711].
L’écriture d’un module MPEG System [iso94a] et d’un module MP3 [iso94c] est en cours.
La figure 7.11 présente de manière graphique les différents composants d’un module émetteur
multimédia. Il est composé d’un parseur qui analyse le flux selon le format. Suite à cette analyse, une
réorganisation peut s’avérer nécessaire pour améliorer la transmission (regroupement des ADU dans
MP3 [RF2k]). Ensuite, l’information est découpée de telle manière que des unités sémantiques de
priorité différente ne soient pas regroupées dans le même paquet. Pour chaque bloc d’information, une
priorité est attribuée. Enfin, les blocs et l’information sur les priorités sont envoyés au serveur. Le
serveur est en charge de recopier la priorité dans l’en-tête IP de chaque paquet avant la transmission.
serveur
attribution
parseur réorganisation découpage
priorité
Le SD6 a été conçu pour FreeBSD. Son adaptation à d’autres systèmes d’exploitation Unix doit
pouvoir se faire facilement; le code est écrit en C standard. La section suivante montre quelques
exemples d’opération du SD6. Pour terminer cette section, nous présentons dans la figure 7.12
l’interface graphique de SD6 chez le récepteur. Elle a été écrite en Tcl/Tk.
Les performances du DS6 ont été testés dans notre plate-forme d’expérimentation (figure 7.13).
Elle est composée de ubik, station effectuant simultanément les actions de serveur multimédia et de
routeur d’entrée. Coté récepteur, hp2 est une station puissante capable de décoder des fichiers MPEG
en temps réel. Le serveur et le client sont reliés à travers phedre et ibm, stations jouant le rôle de
routeurs de cœur du réseau. L’architecture est complétée par ariane et hp1, générateur et récepteur
du trafic de charge.
edged
bboned
ethernet
ubik liens lien ATM 2Mbps hp2
point-à-point
phedre ibm
ariane hp1
Figure 7.13: plate-forme d’expérimentation à l’ENSTB
Dans les deux tests qui suivent, le trafic multimédia, entre ubik et hp2, est perturbé par le
trafic de fond entre ariane et hp1. ADServ (c.f. chapitre 3) tourne sur phedre ainsi que sur ubik.
Le module edged dans ubik limite le débit d’émission suivant le principe du PAM et attribue une
classe de service au trafic multimédia. Le module bboned dans phedre est en charge de la gestion de
file d’attente grâce à la mise en place de RIO3.
Dans les fichiers audio encodés suivant le principe de la µ-law chaque octet représente un
échantillon de l’ampleur du signal [g711]. Afin de produire un flux hiérarchique à partir de ces
informations, le module implanté dans DS6 attribue une priorité plus élevée aux 4 bits poids fort de
chaque échantillon. Le flux transmis est formé par deux couches: l’une concentrant les bits de poids
fort, l’autre assemblant les bits de poids faible. Une réorganisation est nécessaire, comme le montre la
figure 7.14. Ce type de division en couches est appelé "par quantification". La couche de basse contient
le signal quantifié à 16 niveaux, la couche d’amélioration indique la différence entre les informations de
basse et une quantification à 256 niveaux.
Pour ce test, le débit d’émission du serveur et fixe à 22kbps, ce qui correspond à la vitesse de
consommation du client. En fixant la capacité de lien ATM à 64 Kb/s et le débit de charge à 84kbps on
simule un réseau dans lequel on subit 40% de pertes. Le test est exécuté deux fois. Dans la première, le
format à h0 h1 l0 l1 h2 h3 l2 l3
la transmission:
priorité: 2 0 2 0
Figure 7.14: réorganisation du flux audio (.au)
shaper du module edged attribue à tous les paquets la même priorité. Dans la deuxième, le flux est mis
en forme, mais la priorité attribuée par l’application n’est pas modifiée.
Il est difficile de donner une mesure numérique à la qualité d’une séquence audio ou vidéo. Des
paramètres tel que le SNR (rapport signal bruit) n’ont qu’une valeur très relative. Pour décrire la
différence de performances, la figure 7.15 montre une approximation du signal décodé chez le
récepteur pour les deux cas étudiés. Chaque paquet transporte 100 octets d’information. Dans le cas
présenté, le 2ème et le 3eme paquet sont perdus.
sans DiffServ avec DiffServ
300 300
250 250
200 200
150 150
100 100
50 50
0 0
1 101 201 301 401 1 101 201 301 401
séquence d'octets séquence d'octets
Quand les priorités sont ignorées (graphique à gauche), si toute l’information est reçue, la
qualité est identique à celle du fichier original. Par contre, au moment des pertes, des silences au milieu
de la séquence apparaissent; ce qui constitue une dégradation assez gênante pour l’utilisateur. Quand le
marquage DiffServ est pris en compte (graphique à droite), pendant la congestion le signal peut
toujours être reconstruit, mais avec une qualité moindre. Dans le graphique de droite, il est possible
d’apprécier, entre l’octet 100 et 300, la réduction de QoS quand seule l’information de base est utilisée
pour reconstruire le signal. Ceci n’est qu’un simple exemple. Seule l’écoute de la séquence dans les
deux cas1 peut servir à apprécier le gain que la Différentiation de Services apporte au streaming audio.
1. Des fichiers de démonstration pour les tests audio et vidéo sont disponibles dans:
http://www.rennes.enst-bretagne.fr/~medina/diffserv/
Nombreux sont les travaux qui s’attaquent à la transmission vidéo sur Internet
[BYR95][TB94][BT98]. Grâce aux méthodes de compression et à l’augmentation dans la capacité du
réseau, le streaming de ce type d’information, inimaginable auparavant, est désormais possible.
Néanmoins, la qualité des séquences, en termes de définition ou de la taille de l’image, ne peut pas
encore être comparée à celle d’autres moyens de transmission (câble, satellite, etc.). Un obstacle pour la
recherche dans ce domaine est l’absence d’indicateur fiable servant à mesurer la qualité d’un clip vidéo.
Des modifications dans le comportement des routeurs, comme celles proposées par le modèle
DiffServ, peuvent améliorer les performances du réseau vis-à-vis de flux vidéo. Dans cette section nous
décrivons le fonctionnement du module MPEG vidéo dans DS6 et analysons sa performance par
l’envoi d’une séquence de test avec et sans le traitement différentié.
Le module MPEG vidéo a été le premier à avoir été conçu pour le DS6. Son algorithme part du
principe de priorité relative existant entre les images d’un flux MPEG (cf. section 7.2). En analysant le
flux avant la transmission, le flux original est découpé en unités sémantiques. Les trames Intra sont
alors marquées en vert, les trames Prédites en orange et les trames Bidirectionnelles en rouge. Pour nos
fichiers de test, cette politique résulte en un distribution de 40-30-40 entre les 3 niveaux de priorité.
Contrairement au module audio, aucune réorganisation du flux n’est nécessaire pour la vidéo.
La transmission d’une séquence codée d’images CIF couleur (192 x 44 pixels, rapport YUV
4:2:2) demande un débit de 80 Ko/s. Le PAM, installé à l’entrée du réseau (dans ubik), est configuré
pour limiter le débit d’émission (rm) à cette valeur. La capacité du lien central est fixée à 250 Ko/s.
Etant donné que le trafic de fond part d’ariane à 450 Ko/s, le taux de perte observé par les deux flux
est autour de 55%. Le test est réalisé en deux étapes. D’abord, on analyse le cas où la priorité de paquets
est transparente pour le routeur. En suite, la même expérience est répétée quand l’information sur les
priorités est prise en compte pendant la congestion.
Plusieurs séquences vidéo ont été utilisées pour mesurer la validité de nos hypothèses. Les
résultats présentés ici concernent la séquence appelée "indy-bart", magistralement interprétée par
Homer et Bart Simpson. Le tableau 7.2 décrit les caractéristiques du flux.
Construits à l’aide du logiciel mpeg_stat [RSP95], Les tableaux 7.3 et 7.4 présentent la
composition du flux à l’arrivée dans les deux situations. La taille des fichiers enregistrés chez le
récepteur est similaire, reflétant une équivalence au niveau du taux de pertes dans les deux situations. Si
l’on considère que la perte d’une image I dégrade considérablement la reconstitution du film, les
chiffres montrent une nette amélioration quand notre méthode est mise en place.
total 421 2740 1153389 58% total 236 4987 1176839 57%
Tableau 7.3: séquence à l’arrivée (SANS DiffServ) Tableau 7.4: séquence à l’arrivée (AVEC DiffServ)
Quand le marquage par la source est désactivé (tableau 7.3), le taux de pertes est similaire entre
les trois types d’information. 42% des images arrivent au récepteur, mais beaucoup d’entre elles
présentent des défauts partiels. L’affichage est dégradé presque en permanence, ce qui rend la séquence
incompréhensible.
Quand le marquage par la source est pris en compte (tableau 7.4), la dégradation visuelle se
reflète par la diminution dans le nombre d’images par seconde. Des 960 images qui forment l’image à
l’origine, il n’y a que 236 arrivant au décodeur. Le temps rafraîchissement passe donc de 15 à 3,68
trames/seconde. Les images reçues sont peu nombreuses mais, en général, elles restent fidèles à
l’original. Vu que les pertes sont concentrées sur des informations ne servant pas de référence, le
manque d’une image ne se répercute pas sur les suivantes.
SANS marquage
Le marquage par la source peut être utilisé dans des situations différentes à celle étudiée tout au
long de cette thèse. Nous avons introduit un conditionneur qui doit superviser le comportement d’une
source TCP afin d’améliorer sa performance (le BSM). Un tel conditionneur ne serait pas nécessaire si,
au niveau transport, la source était capable de pre-marquer les paquets. Sachant que dans TCP, la perte
consécutive de paquets a des conséquences importantes sur le comportement de la session, une
implantation consciente des priorités pourrait distribuer les jetons de telle manière que le nombre de
paquets consécutifs basse priorité soit minimisé. Ceci n’est qu’un exemple qui montre les bénéfices de
la mise en place d’une fonction d’attribution de priorités au niveau TCP, où des informations précises
sur l’état de la transmission sont disponibles. Nous considérons qu’une telle fonction pourrait servir à
minimiser l’effet des pertes sur la performance de la session.
Un autre domaine qui mérite l’étude approfondie concerne le nombre des priorités qui peuvent
effectivement être différentiées dans le réseau. Nous avons montré dans ce rapport que, en ajoutant
l’information sur le priorités, l’élimination dans les routeurs devient plus précise. Nous avons présenté
les améliorations de QoS qui peuvent être obtenues si trois niveaux de priorité sont utilisés. Si on ne
reste pas sur le modèle standardisé, on peut imaginer l’utilisation d’un éventail plus vaste de niveaux de
priorité. Dans la définition du PAM, nous avons introduit un quatrième niveau de différentiation dans
lequel les paquets de plus basse priorité sont discriminés par le conditionneur. Avec une petite
modification, ces paquets pourraient être injectés dans le réseau avec une priorité inférieure à celle des
paquets rouges. Le TCM et le TSW peuvent être modifiés suivant le même principe pour donner
naissance à des conditionneurs à quatre niveaux. En ce qui concerne les routeurs du cœur du réseau, la
modification nécessaire dans RIO ou dans WRED pour les rendre conscients du quatrième niveau est
triviale. Un nombre augmenté de priorités apporterait aux routeurs une information plus précise sur la
valeur relative de chaque paquet. Il reste à déceler le nombre optimal, en termes de complexité, qui
assure un meilleur fonctionnement du modèle.
Le fonctionnement de l’Internet a souvent été mal compris par les experts en codage
multimédia et vice-versa. Avec l’augmentation du nombre de flux audio/vidéo traversant le réseau, il
devient indispensable de compter avec des algorithmes de codage conscients des contraintes du réseau
et avec un comportement de réseau adapté aux besoins de ces algorithmes. Si l’utilisation de priorités se
consolide dans l’Internet, nous considérons que les recherches dans le domaine du streaming
multimédia devraient se concentrer sur la mise au point d’algorithmes de codage en couches. Le service
multimédia, introduit dans ce rapport, ne peut être utile que si une bonne distribution de priorités est
effectuée par la source. Il existe des cas, comme pour les flux audio MPEG, où la hiérarchisation du
flux peut être difficile. Une mauvaise politique peut résulter en plus de 60% du flux marqué en haute
priorité; limitant énormément les bénéfices que la différentiation apporte. Dans la définition de
nouvelles méthodes de codage, il faudra étudier le pourcentage d’information générée pour chaque
niveau de priorité et la distribution de ces priorités dans le temps; deux paramètres déterminants au
conditionnement DiffServ et, par conséquent, à la QoS qui peut être accordée aux flux de ce type.
trame répetée
2.33
2.00
Tc Te
rapport max/min
1.55
1.50
1.00
b 40 Ko 40 - 120 Ko
α
0.50
8 8
0.00
1.0r 1.5r 2.0r 2.5r 3.0r
débit en excès (re)
est représenté par le rapport max/min, c’est-à-dire, par la relation entre le plus grand et le plus réduit des
débits observés. La meilleure différentiation (le rapport le plus proche de 1) est observée quand re=2rc.
Cette relation représente aussi le meilleur choix en ce qui concerne l’utilisation de la ligne: le taux
d’occupation atteint 91%.
b c = βr c
b e = βr e + b c
Le graphique à droite de la figure A2.2 montre le niveau d’équité observé dans le modèle en
fonction de β. Le BSM est configuré à partir du tableau à gauche de la figure. En respectant le résultat
de la simulation précédente, le rapport re=2rc est utilisé. Le facteur α n’a pas été modifié.
1.40
1.35
1.34
Tc Te 1.30
rapport max/min
1.26
1.25
r 20Ko/s 40Ko/s
1.21 1.22
1.20
1.19
1.18
b 0,5rc - 3,0rc 1,5rc - 9,0rc 1.15
α 8 8 1.10
1.05
0.5r 1.0r 1.5r 2.0r 2.5r 3.0r
facteur beta
Une source TCP avec un long RTT peut profiter d’une taille de seau importante pour
augmenter la taille des rafales conformes. Néanmoins, la simulation montre que, au delà d’un seau égal
à 3r, la différence entre les débits observés devient presque constante. La meilleur performance est
obtenue quand β = 3/2. Cette simulation a permis de découvrir que le taux d’occupation ne dépend pas
de la valeur de b. Pour tous les cas étudiés, ce facteur reste quasi-constant, autour de 90%.
Tc Te
r rc 2rc
b 3/ 3/
2rc 2re + bc
[ARR95] Packet Loss Resilience of MPEG-2 scalable coding algorithms; R. Aravind, M. Reha
Cinvalar, A. Reibman; AT&T Laboratories report; 1995.
[BR2K] A Framework For Integrated Services Operation Over Diffserv Networks; Y. Bernet, R.
Yavatkar et al.; ISSLL Internet Draft; mai 2000.
[BT98] Experience with rate control mechanisms for packet video in the Internet; J-C. Bolot, T.
Turletti; Computer Communication Review, vol. 28, no. 1; janvier 1998.
[BW99] A Lower than Best Effort Per-Hop Behavior; R. Bless, K. Wehrle; personal Internet
Draft; septembre 1999.
[BZ96] WF2Q: Worst-case Fair Weighted Fair Queueing; J.C. Bennett, H. Zhang; Proceedings
of IEEE Infocom, pp 120-128; mars 1996.
[CF98] Explicit Allocation of Best Effort Packet Delivery Service; D. Clark, W. Fang; IEEE/
ACM Transactions on Networking; Vol. 6, No. 4, pp. 363-373; août 1998.
[Cis99] Cisco IOS Quality of Service Solutions Configuration Guide; Online Manual;
http://www.cisco.com/univercd/cc/td/doc/product/software/
ios120/12cgcr/qos_c/
[CL98] The nature of the beast: recent traffic measurements from an Iternet Backbone; K.
Claffy, G. Miller, K. Thompson; INET'98; 1998.
Bibliographie 140
[DLG92] The MPEG Video Compression Algorithm; D.J. Le Gall; Signal Processing: Image
Communication, Vol. 4, No. 2; avril 1992.
[FJ93] Random Early Detection Gateways for Congestion Avoidance; S. Floyd, V. Jacobson;
IEEE/ACM Transactions on Networking, Vol. 1, No. 4, pp. 397-413; août 1993.
[FJ95] Link-Sharing and Resource Management Models for Packet Networks; S. Floyd, V.
Jacobson; IEEE/ACM Transactions on Networking; janvier 1995.
[FP99] TCP mechanisms for Diff-Serv Architecture; W. Fang, L. Peterson; Princeton University
Technical Report 605-99; 1999.
[FSN2k] A Time Sliding Window Three Colour Marker (TSWTCM); W. Fang, N. Seddigh,
B. Nandy; Personal Internet Draft; mars 2000.
[g711] Modulation par impulsions et codage (MIC) des fréquences vocales; dans Aspects
généraux des systèmes de transmission numériques : équipements terminaux;
Recommendation G.711 de l’ITU-T; 1988.
[GM92] How fair is Fair Queueing?; A.G. Greenberg, N. Madras; Journal of the ACM, Vol. 39,
No. 3; pp 568-598; juillet 1992.
[Gol94] A Self-clocked Fair queueing scheme for Broadband Applications; S.J. Golestani;
proceedings IEEE Infocom’94, pp 636-646; juin 1994.
[GVC96] Start-time Fair Queueing: A scheduling Algorithm for Integrated Services Packet
Switching Networks; P. Goyal, H.M. Vin; proceedings ACM SIGCOMM’96; août 1996.
[iso94a] Coding of Moving Pictures and Associated Audio: Systems. IOS/IEC JTC1/SC29/
WG11; Recommandation ITU-T H.222.0, ISO/IEC 13818-1, novembre 1994.
141 Bibliographie
[iso94b] Coding of Moving Pictures and Associated Audio: Video. IOS/IEC JTC1/SC29/WG11;
Recommandation ITU-T H.262, ISO/IEC 13818-2, novembre 1994.
[iso94c] Coding of Moving Pictures and Associated Audio: Audio. IOS/IEC JTC1/SC29/WG11;
Recommandation ITU-T H.262, ISO/IEC 13818-3, novembre 1994.
[KAME] Home Page du projet KAME (mise en œuvre IPv6 pour BSD)
http://www.kame.net/
[Med1] Subband Video Compression for ATM Applications; O. Medina, H. Afifi, A. Ibrahim;
IEEE ROC&C 96; Acapulco, Mexique.
[Med4] Service DiffServ pour les flux audio et vidéo; O. Medina, L. Toutain, J-M. Bonnin;
CFIP 2000; Toulouse, France.
[model] An Informal Management Model for Diffserv Routers; WG Internet Draft; Y. Bernet, S.
Blake, D. Grossman, A. Smith; juillet 2000.
[MS90] Dynamic Adaptative Windows for High Speed Data Networks: Theory and Simulations;
D. Mitra, J. Seery; proceedings SIGCOMM’90, pp 30-40; septembre 1990.
Bibliographie 142
[pdbdef] Definition of Differentiated Services Per-domain Behaviors and Rules for their
Specification; K.Nichols, B.Carpenter; WG Internet Draft; octobre 2000.
[RF2k] A More Loss-Tolerant RTP Payload Format for MP3 Audio; R. Finlayson; AVT
Internet Draft; novembre 2000.
[rfc791] Internet Protocol Specification; Information Sciences Institute, USC; septembre 1981.
[rfc1752] The Recommendation for the IP Next Generation Protocol; S. Bradner, A. Mankin;
Standards Track RFC; janvier 1995.
[rfc1825] Security Architecture for the Internet Protocol; R. Atkinson; Standards Track RFC; août
1995.
[rfc1889] RTP: A Transport Protocol for Real-Time Applications; H. Schulzrinne, GMD Focus et
al; Standards Track RFC; janvier 1996.
[rfc2207] RSVP Extensions for IPSEC Data Flows; L. Berger, T. O’Malley; Standards Track RFC;
septembre 1997.
[rfc2210] The Use of RSVP with IETF Integrated Services; J. Wroclawski; Standards Track RFC;
septembre 1997.
[rfc2382] A Framework for Integrated Services and RSVP over ATM; E. Crawley, L. Berger et al.;
Informational RFC; août 1998.
[rfc2474] Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers;
K. Nichols, S. Blake, F. Baker, D. Black; Standards Track rfc; décembre 1998.
[rfc2581] TCP Congestion Control; M. Allman, V. Paxson, W. Stevens; Standards Track RFC;
avril 1999.
143 Bibliographie
[rfc2597] Assured Forwarding PHB Group; F. Baker, J. Heinanen, W. Weiss, J. Wroclawski;
Standards Track rfc; juin 1999.
[rfc2638] A Two-bit Differentiated Services Architecture for the Internet; K. Nichols, V. Jacobson,
L. Zhang; Informational RFC; juillet 1999.
[rfc2688] Integrated Services Mappings for Low Speed Networks; S. Jackowski, D. Potzolu et al.;
Standards Track RFC; septembre 1999.
[rfc2697] A Single Rate Three Color Marker; J. Heinanen, R. Guerin; Infromational rfc, septembre
1999.
[rfc2698] A Two Rate Three Color Marker; J. Heinanen, R. Guerin; Infromational rfc, septembre
1999.
[rfc2748] The COPS (Common Open Policy Service) Protocol; D. Durham, J. Boyle et al.;
Standards Track RFC; janvier 2000.
[rfc2749] COPS usage for RSVP; S. Herzog, J. Boyle et al.; Standards Track RFC; janvier 2000.
[rfc2815] Integrated Service Mappings on IEEE 802 Networks; M. Seaman, A. Smith et al.;
Standards Track RFC; mai 2000.
[rio] Explicit Allocation of Best Effort Packet Delivery Service; D. Clark, W. Fang; ACM
Transactions on Networking; août 1998.
[RSP95] MPEG Video Software Statistics Gatherer; L. Rowe, S. Smoot, K. Patel, B. Smith;
Computer Science Division-EECS, Univ. of Calif. at Berkeley; fevrier 1995.
[rtp] RTP: A Transport Protocol for Real-Time Applications; Schulzrinne, Casner, Frederick,
Jacobson; AVT Internet Draft; juillet 2000.
[SCZ93] A Schedulling Service Model and Schedulling Architecture for an Integrated Services
Packet Network; S. Shenker, D. Clark, L. Zhang; working paper, Xerox Park; août 1993.
[sima] Simple Integrated Media Access - an Internet Service Based on Priorities; K. Kilkki, J.
Ruutu; 6th International Conference on Telecommunication Systems; mars 1998.
[SN99] Study of TCP and UDP Interaction for the AF PHB; N. Seddigh, B. Nandy et al;
Personal Internet Draft, juin 1999.
[SV95] Efficient Fair Queueing using Deficit Round Robin; M. Shreedar, G. Varghese;
Proceedings SIGCOMM’95; août 1995.
Bibliographie 144
[TB94] Issues with multicast video distribution in heterogeneous networks; T. Turletti, J-C.
Bolot; Proceedings 6th Packet Video Workshop; octobre 1994.
[To97] Gestion Préemptive et équitable de la qualité de service dans les réseaux de paquets à
intégration de services; F. Toutain; Thèse doctorale à l’Université de Rennes I; juillet
1997.
[TO99] Some extensions to enhance the scalability of the RSVP protocol; F. Tomassi, L.
Moledini; Personal Internet Draft; octobre 1999.
[VJ88] Congestion Avoidance and Control, Proceedings of the ACM SIGCOMM’88, pages
314-329, août 1988.
[WC91] A New Congestion Control Scheme: Slow Start and Search (Tri-S); Z. Wang, J.
Crowcroft; Computer Communication Review, Vol. 21, No. 1., pp. 32-43; janvier 1991.
[Zh90] Virtual Clock: A new Traffic Control Algorithm for Packet Switching Networks; L.
Zhang; ACM SIGCOMM 1990; p. 19-29, septembre 1990.
145 Bibliographie
Publications et Présentations
P
Publications:
• Service DiffServ pour les flux audio et vidéo; O. Medina, L. Toutain, J-M. Bonnin;
CFIP 2000; Toulouse, France.
Internet Drafts:
• A proposal for the use of ECN bits with UDP flows; O. Medina, F. Dupont, L. Toutain;
draft-medina-ecn-udp-00.txt
Autres Présentations:
Rennes, le
Patrick NAVATTE
Le Président du Jury,