Chapitre 4 Une approche de la scalabilité
par l'agrégation de flots
4.1 Introduction du chapitre
Comme nous l'avons abordé au chapitre 2 et en fin de chapitre
3, l'architecture IntServ/RSVP pose un problème de scalabilité qui
rend difficile son utilisation dans le cadre de réseaux de grandes
dimensions. Il est encore difficile de dire dans quelle mesure et à partir
de combien de flots le problème se pose réellement, mais il est clair qu'une
gestion des ressources par flot dans le contexte de l'Internet dont
la dimension ne cesse de croître peut impliquer un très fort
overhead.
Dans ce chapitre nous étudions une approche basée sur l'agrégation de flots
pour résoudre le problème de scalabilité de l'architecture IntServ. Nous
proposons de conserver les mêmes mécanismes et méthodes de gestion du trafic
en changeant la granularité de la gestion des ressources à l'intérieur des
réseaux d'interconnexion.
Nous commençons par définir l'architecture globale de notre proposition,
puis montrons comment on peut déduire une garantie de service à des flots
agrégés à partir des ressources allouées à l'agrégat. Nous décrivons ensuite
les mécanismes et protocoles à mettre en oeuvre pour les fonctionnalités
dont nous avons besoin. Puis nous étudions les conditions dans lesquelles
l'agrégation de flots, en plus de réduire le nombre d'états, permet une
meilleure gestion des ressources (bande passante). Enfin, nous discutons les
limites de notre proposition et la comparons avec quelques autres
propositions de la communauté de recherche avant de conclure.
4.2 Architecture
Nous considérons une interconnexion de réseaux mettant en oeuvre le modèle
IntServ/RSVP. Ces réseaux sont interconnectés par un backbone
utilisant des techniques d'agrégation pour fournir les services de l'IntServ
avec une quantité d'état fortement réduite. Ceci est représenté sur la
figure 4.1.
Figure 4.1 : Réseaux IntServ interconnectés par un backbone
Les deux objectifs que nous nous fixons sont :
-
garantie de QoS de bout en bout,
- fonctionnement totalement transparent (une application ne doit
pas se préoccuper de savoir si le flot traversera une zone backbone
ou non).
Le premier point ne peut être atteint que si le modèle mis en oeuvre au
sein du backbone assure le même type de QoS que l'IntServ. Un moyen de
fournir la transparence est de faire apparaître tout le backbone comme étant
un seul élément IntServ/RSVP.
Nous proposons d'agréger les flots (dans un macro-flot que nous appellerons
b-flot pour backbone flow) par couples de routeur d'entrée
dans le backbone (qu'on appellera ingress) et de routeur de sortie
(egress). Ces routeurs de connexion entre les réseaux IntServ et
le backbone jouent évidemment un rôle primordial.
Montrons que ce modèle résout le problème de scalabilité de l'architecture
IntServ/RSVP. Soit n le nombre de réseaux connectés au backbone. On a
alors n2 combinaisons {ingress, egress}. Sur chaque couple, on devra
gérer un nombre fini a de b-flots (un pour chaque classe de service
disponible1). Remarquons aussi qu'à chaque extrémité on
aura au maximum a · (n-1) b-flots en entrée et a · (n-1) b-flots
en sortie. Le nombre de flots RSVP n'a aucune incidence sur la scalabilité
du modèle, et le nombre de réseaux connectés restera forcément (pour des
raisons matérielles) à des valeurs raisonnables.
Ainsi, le nombre de b-flots à gérer sur chaque routeur d'extrémité est
linéaire par rapport au nombre de réseaux connectés tandis que le
nombre total de b-flots à gérer par un routeur à l'intérieur du backbone est
quadratique dans le pire des cas. Comme le nombre de réseaux
connectés n'est pas susceptible d'atteindre de grandes valeurs, ce modèle
parait satisfaisant du point de vue de la scalabilité.
4.3 Agrégation
4.3.1 Concept de b-flot
Nous nous proposons d'effectuer une agrégation homogène, c'est à dire
d'agréger parallèlement les trois états de signalisation, de classification
et d'ordonnancement associés à un flot. Ainsi des flots sont regroupés en un
seul b-flot auquel sont associés ses trois états, qui représentent
chacun l'état agrégé des états correspondants des flots agrégés.
Cette agrégation homogène nous conduit donc à un modèle par flot
semblable à celui de RSVP. À chaque flot sont associés un état de
classification qui permet de filtrer les paquets faisant partie de ce flot,
un état d'ordonnancement pour fournir la QoS allouée et un état de
signalisation pour la gestion du flot.
La différence se situe au niveau de la génération du flot. Dans le modèle
IntServ, un flot résulte de l'activité d'un utilisateur. Il est défini de
bout en bout, par un couple d'instances d'applications (une instance
d'application étant identifiée par une adresse machine et un numéro de
port).
Le b-flot n'existe qu'à l'intérieur du backbone, ses extrémités
sont les routeurs d'entrée (l'ingress) et de sortie
(l'egress) du backbone. Le b-flot est donc défini non pas au niveau
de l'application mais au niveau du réseau puisque c'est le réseau qui le
génère par agrégation de flots applicatifs. Nous pouvons l'identifier par le
couple d'adresses de ``ses'' routeurs ingress et egress et
le type de service qu'il doit recevoir (on agrégera évidemment des flots
ayant des demandes de QoS semblables).
| type |
génération |
granularité |
étendue |
| flot |
utilisateur |
application |
hôte à hôte |
| b-flot |
réseau |
route |
ingress à egress |
Table 4.1 : flots et b-flots
Ainsi, par rapport au modèle RSVP classique, on modifie la
granularité (``à qui s'applique la réservation ?'') et
l'étendue (``d'où à où ?'') des réservations, ce qui est résumé
dans le tableau 4.1. Cette approche de l'utilisation de RSVP
sur des agrégations de flots à l'intérieur du backbone est décrite notamment
dans [GBH97].
4.3.2 Spécificités
Nous venons de voir que l'on peut se ramener à un modèle similaire à celui
qu'utilise RSVP. Cependant, de par leur nature d'agrégats de flots, les
b-flots auront des comportements particuliers que nous devrons prendre en
compte. L'environnement de type réseau d'interconnexion dans lequel évoluent
ces b-flots, possède également des caractéristiques spécifiques. Ainsi les
protocoles de routage dynamique sont très rarement utilisés dans un
backbone. Les changements de route sont exceptionnels et seront plutôt
réalisés par un opérateur (``à la main''). Nous avons relevé les trois
points suivants ; les deux premiers ne sont pas à prendre en compte dans le
cas d'un routage statique.
CAC après changement de route
RSVP utilise le concept d'``état relâché'' qui permet de s'adapter
automatiquement aux changements de route. Le path state est
installé sur la nouvelle route par un message PATH qui aura été créé soit
suite à l'expiration d'un temporisateur de rafraîchissement (refresh
timeout -- avec donc un délai potentiel lié à la fréquence de
rafraîchissement), soit suite à une notification du protocole de routage
(local repair). Quand ce message PATH arrive au premier noeud
commun à l'ancienne et à la nouvelle route, le noeud, constatant que le
champ PHOP diffère de celui stocké dans son path state envoie
immédiatement un rafraîchissement RESV à ce noeud amont. La réservation se
crée donc sur la nouvelle route. Il peut bien sur arriver que le contrôle
d'admission (CAC pour call admission control) refuse alors la
réservation ce qui entraînera la fermeture de la session. Ceci est
parfaitement acceptable dans le cas classique, où un flot est indivisible,
mais pas pour un b-flot qui est divisible en de nombreux flots. Le bon
comportement serait de fermer seulement une partie des sessions RSVP de
façon à ramener la réservation nécessaire au b-flot à une valeur acceptée
par le CAC.
Annulation des réservations
Dans le cas d'un changement de route, non seulement des réservations doivent
être installées sur la nouvelle route, mais celles de l'ancienne route
doivent être annulées.
Comme nous venons de le voir, dès qu'un changement de route est détecté les
réservations sont intallées sur la nouvelle portion de route. Par contre les
réservations qui étaient établies sur l'ancien fragment de route ne
disparaîtront qu'à l'expiration de la temporisation de survie
(cleanup timeout). Ce temps est directement proportionnel à la
période des rafraîchissements dont la valeur conseillée est assez grande (30
secondes) ce qui aboutit à une valeur conseillée de 150 secondes (!) pour le
cleanup timeout.
Ceci est sans doute acceptable avec la sémantique de flot utilisée par les
concepteurs de RSVP, mais pose un réel problème pour des b-flots auxquels
seront généralement réservées de grandes quantités de ressources.
Trois façons de traiter ce problème sont possibles :
-
considérer qu'il n'y a jamais (ou presque) de changement de route dans
l'environnement considéré (et éventuellement les empêcher) ;
- garder le mécanisme de temporisation de RSVP mais avec des
rafraîchissements très rapprochés (et donc un délai d'expiration court),
ce qui a pour inconvénient d'augmenter la charge de traitement ;
- détecter les changements de route et annuler les réservations.
Ces points sont à prendre en compte lors de la conception du protocole de
gestion intra-backbone (section 4.4.3) qui dépendra fortement de
la technologie utilisée. Nous ne les discuterons donc pas plus dans notre
étude.
Dynamicité
Dans le modèle IntServ les caractéristiques d'un flot et la réservation qui
lui est affectée peuvent changer à tout moment, mais c'est en pratique
rarement le cas. Ce sont donc essentiellement les rafraîchissements qui se
chargent de la maintenance des états relâchés.
Un b-flot étant constitué d'un grand nombre de flots, il sera beaucoup plus
dynamique. Définissons la dynamicité comme étant la fréquence avec
laquelle les caractéristiques d'un flot sont modifiées. Si la dynamicité
moyenne d'un flot est égale à d, la dynamicité moyenne d'un b-flot composé
de n flots est égale à n × d.
Ainsi, si l'on groupe 100 flots de dynamicité 1/100 Hz (flots ayant une
période stable de 100 secondes), la dynamicité du b-flot est de 1 Hz (soit
une période stable de 1 seconde). Il est clair que dès que l'on agrège une
quantité significative de flots, il est nécessaire de réaliser une
``accumulation'' des demandes de modification (incluant l'ajout ou le
retrait d'un flot) avant de les appliquer au b-flot. Une possibilité est de
procéder à des modifications par paliers.
4.3.3 Caractérisation du b-flot
Comme décrit en 2.2.3, dans l'architecture IntServ chaque flot est
caractérisé par un TSPEC (traffic specification) qui comprend
essentiellement trois paramètres : b la taille maximum de rafale, r le
débit moyen et p le débit crête. Les ressources à réserver dans le réseau
pour une qualité de service donnée dépendent de cette caractérisation. On
définit le TSPEC (bb, rb, pb) d'un b-flot comme étant la ``somme'' des
TSPEC (bi, ri, pi) des flots i qui le composent. De manière assez
évidente, on a bb=åbi, rb=åri et pb=åpi. Le service
à rendre au b-flot étant connu, le calcul de son TSPEC permet de calculer la
réservation à lui affecter.
Dans le cas du controlled load, la connaissance des trois
paramètres principaux est suffisante pour caractériser un flot. Il n'y a
donc aucune difficulté pour le calcul de la réservation à affecter à un
b-flot.
Par contre, dans ce cas du service GS tous les paramètres du TSPEC doivent
être connus. De plus les fondements théoriques du GS (que nous avons décrits
en 2.4) utilisent des outils mathématiques relativement
complexes [Cru96, LB96]. Nous montrons maintenant comment
caractériser une agrégation de flots devant recevoir ce service.
Agrégation de courbes d'arrivée
Soit un flot Fi caractérisé par le TSPEC (bi, ri, pi) et ayant Li
comme taille maximum de paquet. Sa courbe d'arrivée dans un modèle fluide
est alors :
Ai(t) = min { pi.t, bi + ri.t }
Si l'on agrège n flots Fi, 1 £ i £ n, la courbe
d'arrivée du b-flot Fa constitué par l'agrégation est donnée par :
Pour chaque flot Fi, on définit la valeur ti telle que pi ti
= bi + ri ti. On a alors :
| |
-- si t £ ti |
Ai(t) = pi t
|
| |
-- si t ³ ti |
Ai(t) = bi + ri t |
Calculons la valeur de la courbe d'arrivée de Fa :
| |
-- si t £ min(ti) |
Aa(t) = å(pi t) = t åpi
|
| |
-- si t ³ max(ti) |
Aa(t) = å(bi + ri t) = åbi + t åri |
| |
-- si min(ti) £ t £ max(ti) |
Aa(t) = åmin(pi t, bi + ri t) |
Remarquons que Aa() est une somme de fonctions continues et croissantes,
elle est donc elle même continue et croissante. La figure 4.2
montre qu'entre min(ti) et max(ti) la courbe d'arrivée du flot
se trouve quelque part dans le triangle (ABC). Une première solution est de
la majorer par les côtés CA et AB ce qui nous donne :
Aa(t) = min (t åpi, åbi + t åri)
Il est possible de calculer une courbe d'arrivée plus raide (tight)
en utilisant la cascade des TSPEC comme discuté dans
[SKWS98]. On dispose alors d'une caractérisation plus précise dans
la zone (ABC) ce qui évite de surestimer les délais et réservations
nécessaires. La caractérisation obtenue est cependant plus complexe et ne
peut plus s'exprimer dans le cadre d'un simple TSPEC. Par soucis de clarté
et de simplicité, nous considérerons dans la suite la première
caractérisation même s'il est clair qu'en pratique une implémentation aura
tout intérêt à baser ses calculs sur la caractérisation la plus ``serrée''
possible.
Figure 4.2 : Courbe d'arrivée (fluide) de l'agrégation
Pour tenir compte du fait que l'on n'est pas dans un modèle fluide, il faut,
comme nous l'avons montré en section 2.4 ajouter l'effet du
premier paquet non policé. Or ici dans le pire des cas chacun des flots
agrégés fournira en même temps un paquet de taille maximum, ce qui constitue
un ``paquet virtuel'' de taille åLi octets.
Aa(t) = min ( åLi + t åpi, åbi + t åri)
Insistons bien sur le fait que ce ``paquet virtuel'' n'existe qu'au moment
de la création du b-flot, et n'a de sens que pour le calcul de la courbe
d'arrivée du b-flot. Ce ``paquet'' sera immédiatement ``lissé'' (les paquets
qui le composent seront espacés), et la taille maximum de paquet du b-flot
est max(Li).
Une autre façon de considérer les choses est de caractériser le b-flot par
sa courbe d'arrivée après que le ``paquet virtuel'' ait été lissé et
de tenir compte du délai ajouté par ce lissage que nous appellerons ``délai
d'agrégation''. La courbe d'arrivée est alors :
Aa(t) = min ( max(Li) + åpi t, åbi + åri t)
Et le délai d'agrégation peut se calculer comme D2 - D1 sur la figure
4.3 ce qui donne :
| D1 = |
|
· |
|
+
|
|
+ + |
|
|
æ
ç
ç
è |
|
+ Dj |
ö
÷
÷
ø |
| D2 = |
|
· |
|
+
|
|
+ |
|
|
æ
ç
ç
è |
|
+ Dj |
ö
÷
÷
ø |
et
Figure 4.3 : Courbes d'arrivée du b-flot
En conclusion, le b-flot peut être caractérisé par les paramètres
(bb=åbi, rb=åri, pb=åpi). La taille maximum de paquet
est L = max(Li). Un ``paquet virtuel'' de taille L = åLi est à
prendre en compte pour le calcul des délais par les courbes d'arrivée et de
service.
La formule classique du délai (2.1) s'applique donc sous la
forme suivante :
|
D = |
|
|
|
+
|
|
+ |
|
|
æ
ç
ç
è |
|
+ Dj |
ö
÷
÷
ø |
(4.1) |
La réservation à appliquer pour garantir un délai se calcule classiquement à
partir de cette équation.
4.4 Mécanismes
4.4.1 Interfaçage
Émulation d'un lien virtuel
Pour assurer un fonctionnement transparent, le backbone doit se comporter
globalement comme un élément de l'architecture IntServ/RSVP. On
peut en fait considérer que le routeur ingress est le noeud RSVP et le
chemin dans le backbone le lien (virtuel) associé à ce noeud. Le routeur
egress gère quant à lui normalement ``son'' lien, mais doit de plus coopérer
avec l'ingress pour la gestion du lien virtuel. On définit un lien virtuel
comme la route entre un couple (ingress, egress). L'état de contrôle
de trafic (TCS pour traffic control state) de l'ingress pour ce
b-flot ne sera pas associé à un lien physique mais à un lien virtuel. Sur
un même lien virtuel, plusieurs b-flots peuvent fournir des QoS différentes,
de la même façon qu'un lien est partagé entre plusieurs flots.
Figure 4.4 : Le chemin dans le backbone est vu comme un ``lien virtuel''
Les différences se situent alors dans les éléments suivants:
- lien virtuel
- Les messages RSVP doivent ``sauter'' les noeuds
internes du backbone. Il suffit pour cela que ces noeuds se contentent
de router les paquets RSVP sans leur appliquer aucun traitement
particulier (au sens où ils ne doivent pas déclencher d'action autre que
leur simple transmission ; ils peuvent très bien être traités
différemment, par exemple prioritairement sur le reste du trafic).
- routage
- Pour déterminer quel est le lien virtuel de sortie, une
solution est d'envoyer un message adressé à la destination de la session.
Ce message sera intercepté par un routeur egress, qui répondra à
l'ingress. Celui-ci connaîtra alors le lien virtuel de sortie. Cette
information sera conservée pour éviter de recommencer cette coûteuse
opération de ``routage sur lien virtuel'' à chaque message PATH. On peut
par exemple gérer un cache de routes.
- contrôle d'admission
- Le contrôle d'admission vérifie que suffisamment
de ressources sont disponibles dans le routeur et dans le lien, ce qui est
habituellement une opération locale. Dans notre cas, le test devra être
fait à chacun des noeuds du lien virtuel. Ceci est du ressort du
protocole de gestion intra-backbone (section 4.4.3).
- caractérisation du lien
- Chaque ingress doit connaître les
caractérisations (les termes d'erreur C et D) correspondant à chacun des
liens virtuels auxquels il est relié. Ces caractérisations représentent la
combinaison des caractérisations des routeurs (ingress inclu, egress
exclu) et liens physiques qui constituent réellement le lien
virtuel. La découverte de cette caractérisation peut être faite par
exemple en même temps que le routage sur lien virtuel décrit ci-dessus.
Avec ces modifications (qui ne portent que sur le backbone) RSVP peut être
utilisé de manière classique et complètement transparente.
Mises à jour du b-flot
Quand la composition du b-flot change, la réservation qui doit lui être
affectée est recalculée, et la nouvelle valeur doit être transmise à tous
les noeuds du lien virtuel emprunté par le b-flot.
La nature du protocole à utiliser pour ces mises à jour peut être très
variable, et dépend notamment des caractéristiques du backbone (topologie,
routage dynamique ou non...). Nous discutons ce point en section
4.4.3.
Nous avons vu en section 4.3.2 que la dynamicité d'un b-flot
est beaucoup plus élevée que celle d'un flot classique, ce qui interdit
d'appliquer immédiatement toutes les modifications. Elles devront plutôt
être ``accumulées'' et appliquées régulièrement (modèle synchrone) ou bien
la réservation du b-flot peut être modifiée par paliers. La façon précise de
réaliser cette accumulation dépend largement du type de protocole utilisé à
l'intérieur du backbone et de la dynamicité qu'il offre.
Génération du b-flot
À la création à l'ingress d'un resv state (par réception d'un
message RESV et succès du contrôle d'admission pour la modification
résultante du b-flot sur le lien virtuel), l'agrégation du flot dans le
b-flot doit devenir effective. Les paquets du flot concerné seront alors
aiguillés vers le b-flot correspondant (sous réserve que ce flot respecte
son contrat de trafic, voir le paragraphe ``Isolation'' ci-dessous).
L'effacement d'une réservation (par expiration ou provoquée explicitement)
entraîne la modification du TCS, donc de la bande passante allouée au
b-flot. À partir de ce moment, les paquets du flot concerné doivent cesser
d'être aiguillés vers le b-flot pour être émis en trafic best-effort.
C'est le rôle de ce que nous appellerons le module d'aiguillage de
générer le b-flot en sélectionnant les paquets des flots appropriés.
Isolation entre les flots
Dans le modèle classique, les réservations sont allouées séparément à chaque
flot et ceux-ci sont donc isolés afin qu'un flot ne respectant pas
son contrat de trafic n'affecte pas le service fourni aux autres flots.
La réservation affectée à un b-flot assure une garantie de service pour ce
b-flot. Pour que cette garantie se traduise en des garanties individuelles
pour chacun des flots composant le b-flot, il faut pouvoir contrôler l'effet
que l'un des flots peut avoir sur les autres. À défaut de pouvoir isoler les
flots les uns des autres dans chaque noeud, on peut contrôler le trafic
offert par chaque flot au moment de la génération du b-flot, ce que nous
appellerons isolation en amont. Selon la classe de service concernée,
la façon de réaliser cette isolation peut varier légèrement. Nous décrivons
ci-dessous les méthodes à utiliser pour les classes GS et CL.
Cas du GS
Dans le cas du GS, l'application se doit de respecter son contrat de trafic
car tout excès peut rendre complètement caduque la garantie de délai, et
même provoquer des pertes de paquets. De plus, pour des raisons liées à la
façon dont ce service est implémenté, le réseau peut être amené à lisser le
trafic des flots GS conformément à leur TSPEC (reshaping points
[SPG97, pages 9--12]). On lissera donc les flots GS au moment de
l'agrégation.
Cas du CL
Le cas de la classe de service controlled load est plus délicat. Un
flot peut très bien excéder son contrat de trafic, auquel cas le service
n'est garanti qu'à la portion conforme au TSPEC, le surplus étant traité
comme trafic best-effort2. On devrait donc au moment de l'agrégation
policer chacun des flots et diriger le trafic en excès vers le service
best-effort.
Cependant, dans la mesure où l'état des ressources du réseau le permet (pas
de congestion), il serait préférable de ne pas ``diviser'' les flots de
cette façon car cela peut provoquer des déséquencements inutiles. L'idéal
serait donc de ne rejeter les paquets non conformes au TSPEC vers le service
best-effort que lorsque cela est réellement nécessaire, c'est à dire quand
(et où) le réseau n'est plus capable de rendre le service demandé
également au trafic en excès. Pour cela, on peut au moment de
l'agrégation marquer pour chaque flot les paquets qui dépassent le TSPEC,
c'est à dire effectuer un profilage du flot (par analogie avec le
lissage). Si une congestion apparaît dans un des noeuds du réseau, ils
seront alors relégués prioritairement vers le service best-effort (ou jetés
si la congestion le rend nécessaire, par exemple avec un mécanisme de type
push-out) [GBH97]. Il s'agit là d'une forme d'isolation
combinée en amont/locale.
Le tableau 4.2 résume les façons possibles de fournir
l'isolation.
| Type |
Description |
| locale |
- traitement séparé des flots dans chaque noeud |
| en amont |
- lissage des flots à l'agrégation |
| |
- traitement agrégé dans chaque noeud |
| combinée |
- profilage des flots à l'agrégation |
| en amont/locale |
- traitement agrégé avec différentiation IN/OUT |
| |
éventuelle |
Table 4.2 : Les trois types d'isolations
Architecture d'un routeur ingress
La figure 4.5 montre l'architecture d'un routeur
ingress. Dans le plan de contrôle les états de RSVP path state
(PS) et resv state (RS) sont maintenus pour chaque flot. Par contre
les traffic control states (TCS) correspondent chacun à un b-flot. Un
module (CAC) est chargé de gérer le contrôle d'admission sur les liens
virtuels, et un autre de gérer le cache de routes sur liens virtuels.
Dans le plan de données, les paquets sont tout d'abord routés
normalement de façon à déterminer l'interface de sortie. Ils sont ensuite
classifiés (par flot) et lissés ou profilés
conformément aux spécifications de trafic contenues dans les états RSVP. À
partir de l'information fournie par le routage sur lien virtuel associée à
l'information sur la qualité de service désirée, on détermine dans quel
b-flot ils doivent être aiguillés. Finalement, l'ordonnanceur partage
les ressources entre les b-flots en fonction des TCS correspondants.
Figure 4.5 : Architecture d'un routeur ingress
Quel délai pour les flots GS ?
Si le service fourni par la classe CL est le même pour tous les flots quels
que soient leurs caractéristiques, ce n'est pas le cas de la classe GS. Les
flots GS demandent tous une garantie de délai qu'ils choisissent
individuellement. Il est clair cependant qu'il serait très inefficace
d'agréger des flots ayant des demandes de délai différentes, car il faudrait
fournir le délai le plus faible de tous les flots à l'ensemble du b-flot, ce
qui équivaut à fournir un sur-service à tous les flots qui demandaient un
délai moins strict et aboutit donc à une sur-réservation des ressources.
Deux approches sont possibles pour résoudre ce problème : le délai à fournir
peut être choisi par le réseau ou par l'application.
Choix par le réseau
Une première solution consiste à agréger dans un seul b-flot tous les flots
GS d'un lien virtuel, en leur fournissant donc le même délai. Pratiquement
cela peut-être réalisé en exportant la valeur du délai garanti par le
backbone au moyen du paramètre de caractérisation D du routeur ingress (on
met alors C à zéro). Ainsi l'application prendra ce délai en compte pour
le calcul de sa réservation. Ayant calculé la courbe d'arrivée du b-flot et
connaissant les caractéristiques du chemin à l'intérieur du backbone (les
vraies valeurs Cbackbone et Dbackbone caractérisant le
lien virtuel, sommes des C et D des noeuds qui le constituent) on peut
calculer la réservation à appliquer au b-flot pour garantir le délai fixé.
L'intérêt de cette approche est de ne devoir gérer qu'un seul b-flot GS pour
chaque couple (ingress, egress).
Choix par l'application
Cette solution a l'inconvénient de proposer un service standard identique
pour tous. L'autre solution est de laisser l'application choisir le délai.
Le routeur ingress (qui gère le lien virtuel) exporte les vraies
valeurs Cbackbone et Dbackbone qui caractérisent le lien virtuel.
À la réception de la réservation, connaissant les valeurs de Cbackbone
et Dbackbone et les caractéristiques du flot, on peut calculer le délai
à fournir sur le backbone (nous détaillons comment dans la section
suivante). On peut alors agréger les flots demandant des délais proches et
créer plusieurs b-flots GS. Évidemment, agréger des flots ayant des demandes
de délai hétérogènes implique un surcoût en réservation dépendant des écarts
de délais demandés.
Sachant que pour que l'agrégation soit efficace le backbone ne peut proposer
qu'un nombre limité de délais, la solution la plus efficace serait de
proposer à l'application de choisir entre quelques valeurs de délais
susceptibles de satisfaire tous les types d'applications. Cela serait
possible à réaliser avec RSVP mais nécessite des modifications de l'API
(application programming interface), et est donc contraire à notre
objectif de transparence pour l'application.
4.4.2 Calcul de délais partiels
Nous avons vu que le critère majeur pour décider quels flots agréger était
le délai demandé. Or dans le cadre de l'architecture proposée par l'IntServ,
le délai de bout en bout est décidé par l'application qui calcule
en conséquence la réservation qu'elle va demander au réseau (le réseau lui
ayant fourni une caractérisation du chemin suivi).
Pour mettre en oeuvre l'agrégation, le réseau a besoin de connaître le
délai à fournir à un flot (et non pas sa réservation), de plus c'est le
délai sur le tronçon de réseau où l'agrégation a lieu qui est bien
évidemment à prendre en compte, et non pas le délai de bout en bout. Nous
montrons donc comment le réseau peut calculer le délai à fournir à un flot
sur un tronçon de réseau à partir de la réservation demandée par
l'application, des caractéristiques du flot et de celles de ce tronçon du
réseau.
La formule qui permet de calculer le délai maximum d'un paquet qu'elle soit
sous sa forme simplifiée (2.2) ou non (2.1) est
constituée de deux parties :
-
un terme de temps d'écoulement de la rafale,
- un terme lié à l'approximation du modèle fluide.
Le premier terme est lié aux caractéristiques du flot, alors que le deuxième
est la somme des délais ajoutés à chacun des noeuds traversés (qui peut
dépendre aussi des caractéristiques du flot --- terme C).
Intuitivement on en déduit que le délai maximal sur un tronçon de réseau
donné est égal à la somme du délai dû au temps d'écoulement de la rafale
(qui peut se produire n'importe où dans le réseau) et des délais dûs aux
termes d'erreur des noeuds k à l traversés.
|
D =
|
|
· |
|
+ |
|
+
|
|
|
æ
ç
ç
è |
|
+ Dj |
ö
÷
÷
ø |
(4.2) |
Cette formule peut être démontrée à partir du calcul avec les courbes
d'arrivée et de service comme le montre la figure 4.6. Si
le délai est à calculer sur le tronçon qui va du kieme au lieme
noeud, posons Cpar = åi=kl Ci et Dpar = åi=kl
Di, la figure montre que le délai est matérialisé par le segment IK.
Figure 4.6 : Courbes d'arrivée du flot et de service
Les informations nécessaires à ce calcul sont donc les caractérisations du
flot (qui est fournie par l'application) et du tronçon du réseau.
On remarquera que la somme des délais partiels est supérieure au délai
total, car le délai dû aux rafales peut se produire n'importe où sur le
réseau (mais une seule fois).
4.4.3 Protocole de gestion des b-flots
Le protocole utilisé à l'intérieur du backbone permet la gestion des
b-flots. Ses fonctionnalités doivent être :
-
mise à jour des réservations (et CAC),
- éventuellement3 création et suppression des
b-flots.
Plusieurs types de protocoles peuvent assurer ces fonctionnalités. On peut
utiliser un protocole du type RSVP allégé (adapté conformément à nos
remarques de la section 4.3.2) et orienté émetteur. En
effet, l'orientation récepteur de RSVP se justifie par son modèle multicast
étendu hétérogène. Dans notre contexte, où l'on ne traite que des b-flots
unicast et homogènes, l'orientation émetteur paraît plus naturelle.
On peut également utiliser une architecture centralisée, où un serveur
(broker) gère l'ensemble des b-flots au moyen d'un protocole
propriétaire.
En fait, la façon dont le service est réalisé au sein du backbone importe
peu, du moment que sont disponibles les fonctionnalités nécessaires à la
gestion des b-flots. Différentes solutions sont possibles, dont les extrêmes
sont le modèle réparti et à base de soft states ``à la'' RSVP et le
protocole propriétaire centralisé utilisant des connexions dures.
4.5 Gains de bande passante dûs à l'agrégation
Nous avons vu que l'agrégation entraîne l'ajout d'un délai
d'agrégation correspondant à la contention des paquets des flots agrégés
accédant au b-flot. Le phénomène inverse, c'est à dire une diminution du
délai (et donc des ressources réservées pour garantir un délai donné) se
produit également et est même susceptible d'être largement majoritaire. Des
travaux visant à utiliser l'agrégation spécifiquement pour cet aspect (sans
recherche de la scalabilité) ont d'ailleurs été menés (par exemple
[RG97]).
4.5.1 Cas général
La première source de gain possible est constituée par le terme C
reflétant l'erreur d'approximation dépendant du débit du flot d'un serveur
émulant le GPS (voir 2.4 page ??). Le délai
correspondant à ce terme d'erreur est égal à C/R. Or, dans le cas
de serveurs WFQ par exemple, la valeur de C est la taille maximum d'un
paquet du flot.
Lors de l'agrégation de flots, les effets des rafales s'ajoutent mais sont
compensés par l'augmentation de la réservation. Les délais dûs au terme
d'erreur D ne bougent pas puisque ce délai est (potentiellement) appliqué
à tout paquet indépendament du flot auquel il appartient.
Enfin les délais dûs au terme d'erreur C diminuent car les valeurs de C
ne s'ajoutent pas quand on agrège des flots (le C du b-flot étant le
maximum des C des flots agrégés), et les effets sont inversement
proportionnels à la réservation qui elle augmente (intuitivement, elle est
de l'ordre de grandeur de la somme des réservations qu'il fallait allouer
aux flots individuels). Le gain ainsi procuré est d'autant plus grand que la
portée de l'agrégation (le nombre de noeuds sur lesquels les flots sont
agrégés) est élevé.
4.5.2 Cas des flots à débit constant
Soit un flot F à débit constant r, traversant n noeuds i émulant un
canal dédié avec les termes d'erreur Ci et Di, et ayant besoin d'une
garantie de délai D. Nous retrouvons l'équation (2.2) :
| D = |
|
+ |
|
|
æ
ç
ç
è |
|
+ Di |
ö
÷
÷
ø |
Le premier terme correspondant au fait que le flot n'étant pas fluide, et
donc pas à débit constant aux petites échelles de temps, il émet des
``rafales'' de données de taille un paquet, comme illustré figure
4.7.
Figure 4.7 : Cas d'un flot à débit constant
Ceci se traduit en réservation :
Cette équation n'étant bien sur valable que si r £ R. Toutefois, si r <
R, une partie de la bande passante réservée (R-r) n'est pas utilisée.
Dans le chapitre 3 (section 3.3.2), nous avons montré comment
utiliser la bande passante réservée en excés pour un flot GS pour fournir
des garanties en moyenne. Dans le cas présent, où le flot est à débit
constant, cette bande passante peut être utilisée pour fournir les mêmes
garanties strictes instantanées qui sont fournies au flot à débit r.
En effet, la réservation R peut fournir la garantie de délai D jusqu'à
la valeur maximale de r=R. L'utilisation optimale des ressources
correspond au cas où on a r=R. Cependant, la réservation ne dépend pas du
débit du flot (sauf dans la mesure où elle doit être supérieure à ce débit)
mais uniquement du délai demandé, et l'on peut très bien se retrouver dans
des situations où le taux d'utilisation des ressources R/r
est très faible. Ainsi en agrégeant p flots ayant la même contrainte de
délai, on crée un b-flot dont le débit rb est la somme des débits ri
des flots agrégés. En ajoutant le délai créé à l'agrégation, le délai du
b-flot s'exprime comme :
et la réservation nécessaire Rb pour garantir le délai est :
| Rb = max |
æ
ç
ç
è |
åri, |
|
|
ö
÷
÷
ø |
Si Rb = åri, la réservation moyenne ramenée par flot est égale à
Rb/p = åri/p = ri,moy . L'utilisation du réseau
est donc optimale, puisqu'on garantit le délai avec une réservation égale au
débit du flot, le taux d'utilisation des ressources est égal à un. Il est à
noter qu'on ne peut pas réduire la réservation pour obtenir un délai garanti
plus élevé. Si la réservation est inférieure au débit du flot, plus aucune
garantie n'est possible, car il n'y aura plus assez de bande passante pour
écouler le trafic du flot.
Sinon (Rb > åri) la réservation moyenne ramenée par flot est :
| = Rfl · |
æ
ç
ç
è |
|
+ |
|
|
ö
÷
÷
ø |
Voyons maintenant dans quels cas cette opération d'agrégation est bénéfique
en terme d'utilisation des ressources, c'est à dire que la réservation du
b-flot ramenée par flot est inférieure à la réservation du flot seul.
Il faut que :
ce qui est vrai pour tous p ³ 1, n ³ 1.
Ainsi, nous venons de montrer que l'agrégation de flots à débit constant
demandant des délais semblables en plus d'être intéressante pour la
scalabilité, pouvait conduire à une meilleure utilisation des ressources du
réseau. Ce résultat nous semble très intéressant et mériterait un
approfondissement des travaux dans cette direction mais cela sort du cadre
de notre sujet.
4.5.3 Utilisation
La première méthode, qui utilise le gain sur le terme Ctot, est
applicable dans n'importe quel contexte, mais le gain n'est pas
systématique. Il faudra donc avant de l'appliquer à des flots donnés
calculer le résultat de l'agrégation éventuelle. Des règles générales sur
les caractéristiques des flots susceptibles de résulter en une agrégation
bénéfique doivent pouvoir être dégagées. Par exemple, pour des flots aux
caractéristiques identiques demandant le même délai, l'agrégation est
toujours bénéfique [RG97].
L'applicabilité de la deuxième méthode peut paraître assez réduite puisque
se limitant à des flots à débit constant. En fait, le débit des flots n'a
pas réellement à être constant, du moment que leur débit crête p est
inférieur à leur réservation R. La bande passante disponible susceptible
d'être récupérée pour des garanties dures est alors égale à R-p (au lieu
de R-r). Les applications qui ont besoin de délais très courts pour des
flots à débit crête très faible (par exemple séries de transactions temps
réel, certains flots des simulations interactives distribuées) et qui
engendrent donc une grande sur-réservation de ressources, pourraient être de
bonnes candidates pour cette méthode.
4.6 Limitations et comparaisons
4.6.1 Le multicast
Le modèle que nous avons choisi d'utiliser (un b-flot par couple
{ingress, egress} et classe de QoS) s'applique difficilement au
multicast. En effet le nombre de b-flots multicast potentiels est
extrêmement élevé. Ainsi on a n-2 flots 1 vers 2 et 2 vers 1, n-3
flots 1 vers 3 et 3 vers 1 etc...
Ce très grand nombre de b-flots à gérer peut compromettre la
scalabilité du modèle en rendant l'agrégation largement inopérante. Le
modèle multicast étendu de RSVP, en impliquant des arbres hétérogènes,
accentuera encore ce problème.
Cependant, dans le cas où la topologie du backbone est à maillage complet
(ce qui est souvent le cas) le problème du multicast se résout très
simplement car un flot multicast se réduit à une série de flots unicast que
l'on traite indépendamment.
Pour un flot multicast 1 vers n, le message envoyé par l'ingress sera reçu
par plusieurs egress. Pour un flot multicast n vers 1, l'egress recevra
plusieurs messages et transmettra donc les messages RESV à chacun d'eux. Le
modèle étendu n vers m s'obtient par combinaison de ces deux mécanismes,
comme le montre la figure 4.8.
Figure 4.8 : Multicast 2 vers 2
Dans le cas où le backbone n'est pas à maillage complet, la gestion du
multicast s'avère plus délicate. Si le nombre de flots multicast est faible
(ce qui est le cas dans l'Internet actuel) et ne pose donc pas de problème
de scalabilité on peut envisager de les traiter normalement (c'est à dire
sans mettre en oeuvre de techniques d'agrégation) à l'intérieur du
backbone. On aura alors une architecture IntServ classique pour les flots
multicast en parallèle à des techniques d'agrégation pour les flots
unicast. Cela peut paraître une approche raisonnable à court terme, tant que
l'utilisation des applications multicast ne se développe pas sensiblement.
De même, si la majorité des sessions multicast a lieu entre les mêmes
réseaux l'agrégation entre ces réseaux peut se révéler efficace, on peut
alors installer un b-flot multicast. Le protocole intra backbone devra alors
évidemment être capable de gérer le multicast. L'efficacité de cette
approche dépend de la distribution (au sens statistique) des flots multicast
dans le réseau...
Enfin, on peut choisir de ne pas supporter le multicast, donc de décomposer
les flots multicast en séries de flots unicast en dupliquant les paquets au
niveau de l'ingress. On préserve ainsi la scalabilité en sacrifiant la bande
passante.
Il est clair que notre solution d'agrégation par flots n'est pas
applicable au cas du multicast. Peut être une approche basée sur
l'agrégation par classe (à la DiffServ) pourrait elle se révéler plus
applicable au multicast, mais cela induirait très probablement un
relâchement des garanties. Indépendamment des problèmes de scalabilité liés
aux garanties de service, le multicast apporte ses propres problèmes qui ne
sont pas encore tous résolus. Il nous semble donc que la fourniture de
garanties de service dures de manière scalable à des flots multicast est un
problème extrêmement difficile que nous n'avons pas la prétention de
résoudre dans le cadre de ce travail de thèse.
4.6.2 Autres approches
Interopération IntServ/DiffServ
Dans [BYF+99], il est proposé une architecture globalement
similaire à ce que nous venons de présenter mais en utilisant DiffServ à
l'intérieur du backbone. Nous avons brièvement discuté le modèle
DiffServ en section 2.3. Indépendamment des problèmes qui ne
sont pas encore résolus, il nous semble que le modèle de service proposé est
inférieur à celui de l'IntServ, soit en fermeté des garanties, soit en
flexibilité. Que l'on ait réellement besoin d'un modèle aussi complet et
flexible que celui proposé par l'IntServ est bien sur discutable. Cependant,
deux options sont possibles :
- soit le modèle DiffServ est suffisant et on a tout intérêt à
l'utiliser partout, y compris dans les réseaux de petites dimensions où
IntServ est utilisable,
- soit il ne l'est pas et alors l'utiliser dans le backbone ne
résout pas le problème.
Nous pensons donc que cette approche n'est pas très satisfaisante.
SRP
Une approche originale est Scalable resource Reservation Protocol
(SRP) proposée dans [FALB98]. L'idée est de s'inspirer du modèle de
contrôle de congestion de l'Internet, c'est à dire de mettre le moins
possible d'intelligence dans les routeurs en reportant la complexité dans
les hôtes (et donc en leur faisant confiance). Sur chaque lien, tous les
flots sont agrégés et aucune connaissance des flots individuels n'est
conservée dans le réseau. Chaque routeur conserve la réservation totale
qu'il a accordée et surveille le trafic. Le protocole utilise trois types de
paquets : best-effort, request et reserved. Brièvement,
une application désirant obtenir une garantie de débit émet des paquets
request au débit désiré. Quand un routeur reçoit des paquets de ce
type, si il a assez de ressources il augmente la réservation et transmet les
paquets, sinon il change les paquets en best-effort. Le récepteur
mesure le débit arrivant en paquets request et en déduit la
réservation acceptée sur tout le chemin. Il l'envoie par un protocole de
réaction (feedback) à l'émetteur qui peut alors émettre des paquets
reserved au débit accepté. Dans les routeurs, les paquets
request (non dégradés en best-effort) et reserved sont
traités prioritairement.
Il est possible de gérer le multicast mais le modèle se complique
sérieusement si l'on veut permettre l'hétérogénéité des récepteurs. Les
principes utilisés font que ce modèle ne peut convenir que pour des
garanties relativement lâches, du type de celles requises pour le service
Controlled Load. Il supposent de plus la coopération honnête des
hôtes.
Dynamic Packet State
Enfin, Stoica et Zhang proposent dans [SZ98, SZ99] un modèle
adapté aux garanties de délai dures. L'originalité de leur approche est
qu'elle n'est pas basée sur l'agrégation, mais consiste à supprimer le
besoin de maintenir des états par flot dans chaque noeud en transportant
les états dans les paquets, selon la technique qu'ils appellent DPS
(Dynamic Packet State). Nous reportons la description de ce modèle au
chapitre suivant où nous proposons une approche similaire.
4.7 Conclusion du chapitre
Dans ce chapitre, nous avons proposé une solution possible au problème de
scalabilité de l'architecture IntServ. Basée sur des techniques
d'agrégation, cette approche reproduit le même modèle que l'IntServ à une
échelle différente et permet donc de conserver la sémantique des garanties
IntServ, ce qui est son atout majeur par rapport aux autres approches
proposées (à l'exception de DPS).
Nous avons de plus montré comment pouvaient être mis en oeuvre des
mécanismes assurant la transparence totale de l'interopération entre les
zones avec et sans agrégation, ce qui permet de conserver une interface
unique au niveau des applications.
La contrepartie inhérente à l'agrégation est une certaine perte de
flexibilité. En particulier notre approche n'est malheureusement pas
applicable au multicast en général. Le multicast n'étant cependant pas
lui-même utilisable à grande échelle, cela ne nous paraît pas un
inconvénient majeur, au moins pour les quelques années à venir. Il nous
semble que fournir à la fois la qualité de service de manière scalable
et le multicast est un problème extrêmement difficile, et qu'il
faudra probablement que les problèmes propres au multicast aient eux-mêmes
été résolus pour pouvoir y apporter des solutions.
Notre objectif dans l'étude des techniques d'agrégation était la réduction
du nombre d'états pour fournir un modèle scalable. Il se trouve que
l'agrégation peut apporter d'autres bénéfices en terme d'efficacité
d'utilisation des ressources, ce que nous avons montré en section
4.5. Ceci, combiné au service BR proposé dans le chapitre
3, devrait contribuer à permettre d'atteindre une utilisation
optimale des ressources dans un réseau à intégration de services.
- 1
- Dans certains cas, plusieurs b-flots peuvent être
nécessaires pour une classe de service comme nous le verrons avec le service
GS page ??.
- 2
- La spécification [Wro97a] laisse en
fait le choix entre cette solution et une dégradation uniforme du service
pour tous les paquets du flot.
- 3
- Éventuellement car on peut aussi choisir
d'avoir des b-flots installés statiquement.
