35 0 698KB
TABLE DES MATIÈRES
i
Table des matières 1
Introduction Générale
1
2
Files d'Attente et Trac
7
3
Mécanismes de partage de ressources
31
4
La Congestion: les phénomènes
45
5
Mécanismes de contrôle de congestion
55
Bibliographie
68
ii
TABLE DES MATIÈRES
Chapitre 1
Introduction Générale Sommaire 1.1
Panorama général . . . . . . . . . . . . . . . . . . .
2
1.2
La Qualité de Service . . . . . . . . . . . . . . . . .
3
1.3
1.2.1
Réseau à Commutation de Circuit
1.2.2
Réseau à Commutation par Paquets
La Modélisation
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
1
3 4
5
2
Introduction Générale
L
'organisation des réseaux vise à donner la maîtrise des phénomènes
qui s'y produisent, à l'occasion du traitement des communications, et plus
généralement des services qu'ils orent. Ces phénomènes sont gouvernés par le hasard de l'apparition des requêtes, et s'étudient indépendamment des choix de technologie mis en ÷uvre. Ils sont justiciables du formalisme du calcul des probabilités, et donnent naissance à la notion de
trac,
qui va jouer un rôle
central dans leur appréhension. Ainsi, les phénomènes de trac conditionnentils pour une large part la structure eective des réseaux modernes. Ce cours présente les éléments de la théorie du trac, en en montrant l'impact sur les architectures des réseaux et des systèmes, et en introduisant les grands problèmes que doit aronter l'Ingénieur chargé du trac. Les notions développées ici trouvent leur application dans les domaines de
conception des réseaux, dans les techniques de la planication, du dimensionnement des équipements, de la caractérisation et de la mesure de la Qualité de Service, et de la gestion en temps-réel de leur comportement. la
1.1
Panorama général
On étudie ici le réseau indépendamment des solutions techniques adoptées pour son implémentation (bres optiques, liaisons radio, IP ou ATM, etc.) . Le réseau apparaît simplement comme un graphe, reliant des noeuds (commutateurs/routeurs) et desservant des terminaux. Il a comme fonction de relier les terminaux, de leur permettre des échanges d'information, ce qu'on appelle le
On écrit
trac en trac anglais
. Première tâche, dénir en quoi consiste le trac. An d'expliciter cette
notion, il sera nécessaire d'examiner plus en détail le type de réseau et surtout le service d'interconnexion qu'on envisage.
La Qualité de Service (QoS) est une autre notion importante. Il faudra tout
l'abréviation anglaise
d'abord la dénir, se donner les moyens de la chirer (cela dépend aussi du
s'est imposée
service). Les processus se déroulant dans le réseau sont de nature aléatoire. Il
Quality of Service
en résulte que la QoS met en jeu des notions de probabilité (probabilité de rejet, etc.). Par conséquent, la dénition de la QoS et la vérication des contraintes qu'elle fait peser sur le réseau feront appel aux notions du calcul des probabilités, et plus spécialement de la
théorie des les d'attentes. Cette discipline aura
deux fonctions complémentaires: d'une part évaluer le niveau de performance d'un réseau donné; d'autre part, estimer les ressources nécessaires au respect de critères de QoS donnés (on parle de
dimensionnement).
En général, les éléments de la théorie seront insusants à traiter entièrement les problèmes de dimensionnement. On aura alors recours à la
simulation, qu'il
faut considérer comme un complément à l'approche mathématique, les deux méthodes se confortant mutuellement. L'usage conjoint de ces deux approches amènera un bon niveau de sécurité dans les prévisions. Il ne sut pas d'estimer le niveau de ressources nécessaire; cette estimation s'intègre, en fait, dans une démarche beaucoup plus générale de
planication.
Le responsable du réseau doit en eet commencer par estimer la demande (son
1.2 La Qualité de Service
3
volume, notamment) et prévoir son évolution, dimensionner les ressources en conséquence, et organiser leur mise en service. La structure du réseau, et pas seulement sa taille, sont des sujets d'étude pour la planication. Enn, quelles qu'aient pu être les précautions prises à l'occasion de la dénition et du déploiement des services, il semble inévitable que les comportements des sources, des ux de trac, provoquent des comportements inattendus, contre lesquels le réseau aura à se protéger. C'est le domaine des phénomènes de congestion, et des mécanismes de contrôle en temps-réel. L'usage de mécanismes spéciques pour garantir les qualités de service s'impose. Le cours abordera les points suivants: dénition du trac; rappels et compléments en les d'attentes; application à la modélisation; description des principaux mécanismes de gestion de la capacité (ordonnancement, priorités); présentation des phénomènes de congestion et des mécanismes de protection. présentation de la notion de Qualité de Service et des architectures de réseaux avec QoS; description des principaux algorithmes et mécanismes de gestion du trac permettant de déployer des ores à qualité de service spécique. Les notions développées dans ce cours concernent tous les types de réseaux, qu'ils soient à commutation de circuit ou de paquets, qu'ils soient xes ou mobiles. En pratique, les exemples seront pris dans chacune des catégories, sans idée préconçue. Elles sont applicables aussi bien pour de grands réseaux publics (réseaux d'opérateurs, typiquement) que dans des réseaux privés (réseaux locaux, interconnexion de réseaux locaux constituant des réseaux privés virtuels).
1.2
La Qualité de Service
La notion de Qualité de Service veut rendre compte, de façon chirée, du niveau de performances que l'utilisateur attend du réseau. La notion de QoS, son
Dans une architecture
mesure, sa vérication sont des tendances modernes c'est à dire que l'appari-
en couches, l'utilisateur
tion des mécanismes de la dérégulation leur donne une importance croissante. de la couche de niveau La signication précise de la notion de Qualité de Service dépend évidemment du
service
envisagé. Ainsi le service a-t-il des exigences de temps de réponse;
quelle est sa sensibilité aux erreurs de transmission; etc. Une dénition complète se référera souvent au mode de transport de l'information circuit ou paquet, bien que la solution adoptée par le réseau pour rendre le service doive rester transparente à l'utilisateur.
1.2.1
Réseau à Commutation de Circuit
Le réseau téléphonique est le type même de réseau à commutation de circuits. Une demande acceptée se voit orir à son usage exclusif un circuit (circuit
n est un processus couche n + 1
de
4
Introduction Générale
électrique continu, ou intervalle de temps d'une trame MIC) pour toute la durée de la connexion. La QoS est dénie en premier lieu par la possibilité de ne pas obtenir de circuit lors de la demande. On la mesure par la
probabilité d'échec.
D'autres critères, liés aux technologies, interviendront dans la QoS. Ils ne concernent pas notre propos, ce sont les critères liés à la qualité électrique de la liaison (atténuation du signal, distorsions).
1.2.2
Réseau à Commutation par Paquets
Dans un réseau orant le service de commutation de paquets, l'information des sources est fragmentée en blocs élémentaires qui voyagent dans le réseau indépendamment les uns des autres. Ces blocs ne possèdent aucune ressource en propre (comme dans le cas du circuit). Les paquets d'une connexion se retrouvent en compétition avec d'autres pour accéder aux mémoires ou aux lignes de transmission. Il en résulte un critère supplémentaire de Qualité de Service, lié au sort individuel de chaque paquet, qui subira un retard variable, et pourra même être perdu, par exemple si une des mémoires qu'il doit traverser est saturée. On mesurera la QS par la probabilité de perte de paquet et par le délai, qu'on spéciera par sa moyenne, ou de façon plus précise par un
quantile.
Pour introduire cette notion, supposons qu'on ait pu mesurer les temps d'attente des paquets qui traversent un commutateur. On trace l'
histogramme qui x et
donne les fréquences empiriques d'observation d'un temps compris entre
x + x (Figure 1.1.a). Ou, mieux encore, la distribution cumulée empirique (-
gure 1.1.b) en fait ici la distribution complémentaire, qui donne la proportion des mesures supérieures à
x.
0.02
1
0.1 Proba (attente > x)
Proba (attente = x)
0.015
0.01
0.005
0.01
0.001
une proportion p=0.01 0.0001
au-dessus de x
0
1e-05 0
2
4
6 8 10 Temps d’attente x
12
14
(a) Histogramme des temps
Fig. 1.1
0
2
4
6 8 10x Temps d’attente
12
(b) Distribution cumulee
Observation des temps d'attente
Une lecture directe du graphique donne le quantile cherché. Dans une cam-
x dép des mesures recueillies. En termes mathématiques,
pagne de mesure, ou à l'issue d'une simulation, il sut d'estimer la valeur passée par une proportion
14
1.3 La Modélisation
5
le quantile est déni à partir de la fonction de répartition, ou de la densité. Si on note
F
et
f
les fonctions correspondantes pour une variable aléatoire
X
(le
délai du paquet, ici):
F (x) f (x) le quantile pour la valeur
= =
P fX xg dF=dx
(1.1)
p (le p-quantile) est la valeur xp
Z1 xp
F (xp )
= 1 f (x)dx = p
telle que:
p
L'importance du quantile provient de la remarque suivante: les utilisateurs
Exercice: essayer de
d'un réseau plus généralement de tout serveur ne sont pas sensibles à la
trouver des
moyenne, grandeur théorique que personne ne ressent. Ils sont en réalité insen-
circonstances où la
sibles aux délais courts, dont ils n'auront pas conscience; à l'inverse ils seront
moyenne d'une
sensibles à des grandes valeurs du délai, qu'ils perçoivent. Par exemple, dans le cas où un paquet subit un retard trop important, une temporisation (qui teste le retour d'un acquittement) va expirer, provoquant sa réémission (l'émetteur interprétant le retard comme une perte). La temporisation joue le rôle d'un seuil, et seule la probabilité que le retard dépasse ce seuil est importante. Le quantile mesure la valeur du délai que le réseau assure dans
1
p des cas.
Ainsi, le temps qui s'écoule entre le décrochage du combiné téléphonique et la réception de la tonalité est de l'ordre de 0.4 secondes. Il devient intolérable au delà de 3 secondes (c'est à dire que s'il dépasse cette valeur, on voit apparaître des comportements d'impatience - qui dans ce cas peuvent mettre en cause le bon fonctionnement de l'ensemble). Les étages d'entrée des commutateurs doivent donc assurer que ce temps n'est supérieur à 3 secondes avec une probabilité
p = 0:01 (par exemple), en situation de trac de surcharge.
D'autres critères dénissent la QoS. Notamment, les notions liées à la dispo-
nibilité du service sont extrêmement importantes. En gros, il s'agira de garantir la présence permanente du service, et l'absence de ruptures intempestives de connexions. Dans un certain nombre de cas, les notions de réseau à commutation de circuit et à commutation de paquet se superposent. La technique ATM par exemple, commute des paquets (les cellules) dans un réseau de circuits virtuels. Les problématiques des deux grandes catégories se trouvent ainsi mêlées dans l'étude de ce réseau.
1.3
La Modélisation
Un réseau, un commutateur, sont des objets physiques complexes qu'il est dicile d'appréhender dans leur totalité. D'autre part, on sent bien l'inutilité
grandeur aurait un sens pour le client d'un service
6
Introduction Générale
de tenir compte de la plupart de leurs caractéristiques pour traiter un problème de trac. La
modélisation est l'approche adaptée à ces questions.
Faire un modèle, c'est, en partant d'une description complète du système réel, construire une abstraction simpliée qui conserve les particularités des phénomènes à étudier et seulement celles-ci. La modélisation est une technique délicate et empirique, un artisanat. Nous essaierons d'en montrer la puissance et l'intérêt, au travers d'exemples-types pris dans la pratique de développement et de l'exploitation des réseaux de télécommunications modernes.
Repères bibliographiques L'introduction du Calcul des Probabilités et donc du Hasard, est inévitable. Il faut donc au lecteur qui désire réellement approfondir ce domaine acquérir de bonnes notions de probabilités. L'ouvrage classique [Fel 71] peut être utile mais il en existe beaucoup d'autres. Il lui faudra aussi de bonnes notions en théorie des les d'attentes une discipline à part entière. Pour les besoins de ce cours, le Chapitre qui suit en expose les éléments nécessaires. Pour une étude plus approfondie, le lecteur pourra se reporter aux références [Kle 76, Gros 85, Bay 00] la liste n'est pas limitative. Pour changer de registre, sur un plan résolument épistémologique, la lecture de [Rue 91] est très enrichissante. L'auteur y développe des considérations stimulantes sur la façon dont le hasard s'introduit dans la physique considérations applicables au trac.
Chapitre 2
Files d'Attente et Trac Sommaire 2.1
La Station de Service élémentaire
. . . . . . . . .
8
2.2
Processus des Arrivées . . . . . . . . . . . . . . . .
9
2.3
2.4
2.5
2.6
2.2.1
Processus de Renouvellement . . . . . . . . . . . . .
9
2.2.2
Processus de Poisson . . . . . . . . . . . . . . . . .
10
2.2.3
Où rencontre-t-on les processus de Poisson ?
Processus des Services
. . . .
. . . . . . . . . . . . . . . .
10
11
2.3.1
Le temps de service résiduel . . . . . . . . . . . . . .
11
2.3.2
La loi exponentielle . . . . . . . . . . . . . . . . . . .
11
2.3.3
Lois d'Erlang . . . . . . . . . . . . . . . . . . . . .
Processus de Naissance et de Mort . . . . . . . . .
12
13
2.4.1
La notion d'état
. . . . . . . . . . . . . . . . . . . .
13
2.4.2
Chaînes de Markov . . . . . . . . . . . . . . . . . .
13
2.4.3
Les processus de naissance et de mort
. . . . . . . .
Les les d'attente classiques . . . . . . . . . . . . .
14
15
2.5.1
La Notation de Kendall
. . . . . . . . . . . . . . .
16
2.5.2
Résultats généraux . . . . . . . . . . . . . . . . . . .
16
2.5.3
File M/M/1 . . . . . . . . . . . . . . . . . . . . . . .
18
2.5.4
La le M/M/c
. . . . . . . . . . . . . . . . . . . . .
19
2.5.5
Modèles à capacité limitée . . . . . . . . . . . . . . .
20
2.5.6
Modèle M/M/R/R (modèle d'Erlang)
La notion de Trac
. . . . . . .
. . . . . . . . . . . . . . . . . .
20
21
2.6.1
Réseau fonctionnant sans attente . . . . . . . . . . .
22
2.6.2
Réseau fonctionnant avec attente . . . . . . . . . . .
24
7
8
Files d'Attente et Trac
L
es Télécommunications font usage de théories et de méthodes
issues du Calcul des Probabilités, et connues sous le nom de Théorie des Files d'Attentes (ou des réseaux de les d'attente). L'application au domaine de télécommunications, qui aboutit aux notions de trac, est le Télétrac.
2.1
La Station de Service élémentaire
La Théorie considère des
clients, qui se déplacent dans un réseau de serveurs,
qui les traitent. Lorsque plusieurs clients tentent simultanément d'obtenir un service, certains doivent patienter et attendre dans des
les d'attente, ou tampons.
Le vocabulaire est xé et conventionnel. Les clients peuvent être des humains faisant la queue à un guichet pour obtenir un ticket de train (le serveur est l'employé qui délivre les tickets). Ils peuvent représenter les paquets qui sont aiguillés vers une ligne de transmission et qui attendent la disponibilité de la ligne (deux paquets pouvant être en contention). Le serveur est alors l'automate d'émission, et le temps de service est le temps d'émission. Les demandes de prise de circuit dans un système téléphonique sont un autre type de clients. Dans ce cas, les serveurs forment un groupe: ce sont les circuits qui desservent la direction demandée. La station de service est composée d'une le d'attente, de capacité nie ou non, vidée par un ou des serveurs, et alimentée par un ux de clients: Fig. 2.1.
1
Discipline de service
Loi du service
2
Processus des arrivées
n
Attente
Séjour Fig. 2.1
La station de service de base
Pour décrire ce système de façon précise, il faut pouvoir spécier: Le mécanisme d'arrivée des clients dans le tampon (c'est à dire, en pratique, à quelle loi le processus d'arrivée va obéir). Le temps de service (c'est à dire la distribution de probabilité de sa durée). La discipline de service (quand un serveur se libère, quel client choisit-il)
2.2 Processus des Arrivées
2.2
9
Processus des Arrivées
Pour aller plus avant dans l'étude des propriétés du trac, il va être nécessaire de passer en revue les deux composantes dont il dépend. A savoir, les arrivées de clients , et leur service. On observe les arrivées de clients à l'entrée du système. Pour décrire le phénomène, la première idée venant à l'esprit sera d'utiliser l'intervalle du temps entre arrivées successives, ou bien le nombre des arrivées dans un intervalle donné. Pendant la durée
T , n(T )
arrivées se produisent. On chire le volume du
ux arrivant par le taux d'arrivée dont la dénition intuitive est:
lim n(TT )
(2.1)
T !1
On pourra aussi estimer l'intervalle moyen entre arrivées: c'est l'inverse de la quantité précédente.
2.2.1
Processus de Renouvellement
Dans le cas le plus favorable, la description statistique du temps entre les arrivées est très simple. Supposons que la situation puisse être décrite de la façon suivante:
Chaque fois qu'une arrivée se produit, je tire au sort, selon une loi donnée, l'intervalle jusqu'à la prochaine arrivée, de telle sorte que les intervalles successifs soient indépendants. On est alors dans le cas très particulier d'un processus de renouvellement. Il faut comprendre l'intérêt d'une telle notion, mais aussi ce qu'elle a de rare. Soit par exemple un processus d'arrivée qui résulterait de la superposition de deux processus de renouvellement, indépendants.
?
Processus A
Processus B
Superposition A & B
Fig. 2.2
?
?
?
?
?
?
?
? ?
?
La superposition de A et B
n'est pas
un renouvellement
Inutile de remarquer combien cette situation est commune! Le processus de superposition
n'est pas
un renouvellement. En eet, pour prévoir l'instant
?
10
Files d'Attente et Trac
d'arrivée du 3ème client, il faut se référer au 2ème, par exemple en tirant le temps interarrivées. Mais pour le 4ème, son arrivée ne peut être prévue que par référence au 1er, et non au 3ème.
2.2.2
Processus de
Poisson
Supposons que le processus des arrivées obéisse aux règles suivantes:
[t;t + t[ ne dépend pas de t. C'est la propriété dite sans mémoire. la probabilité d'apparition d'un client est proportionnelle à t, la proba-
la probabilité d'une arrivée dans un intervalle ce qui s'est passé avant l'instant
bilité de plus d'un événement étant négligeable (inniment petit d'ordre supérieur). Le coecient de proportionnalité est noté
(intensité du pro-
cessus). Voir pour une preuve les ouvrages classiques
Ce sont là les hypothèses classiques qui conduisent au processus de Poisson. La probabilité d'observer
de les d'attente
k arrivées dans un intervalle de longueur t vaut: (t)k e t Pk (t) = (2.2) k!
La loi de probabilité de l'intervalle entre deux arrivées successives est
Exercice: calculer la variance de cette quantité
A(t) = 1 e t La moyenne de cet intervalle vaut 1=: Z1 E (t) = t:dA(t)
(2.3)
0
Noter que le nombre moyen d'arrivées observé dans tout intervalle de longueur
t est t. Noter aussi que le processus de Poisson est un processus de renouvellement.
2.2.3
Où rencontre-t-on les processus de
Poisson ?
Quand on ne sait rien d'un processus d'arrivées, il est assez tentant de lui attribuer les deux propriétés énoncées ci-dessus, et qui conduisent aux formules du processus de Poisson, tant elles semblent générales et raisonnables pour de nombreux systèmes. En réalité, il n'en est rien et la vérication de ces hypothèses n'ira généralement pas de soi. Le plus souvent, la justication du recours à l'hypothèse poissonnienne repose sur le résultat suivant.
Théorème [Cin 75, Fel 71]: Soient
P
k
processus de renouvellement indé-
i ;i = 1; ;k). i le taux d'arrivée global du processus résultant de leur super-
pendants, non nécessairement poissonniens de taux d'arrivées ( On note position.
=
Si la somme précédente admet une limite
lorsque
k
augmente indéni-
ment, alors le processus superposition tend vers un processus de Poisson de taux
.
(Remarque: l'emploi de
i
et de la notion de taux d'arrivée ne préjugent
absolument pas d'une hypothèse poissonnienne pour les processus individuels).
2.3 Processus des Services
2.3
11
Processus des Services
Le processus de service pourra être d'une complexité extrême, mais on se borne le plus souvent à supposer que chaque durée de service est indépendante des autres, et qu'elles obéissent toutes à une même loi de distribution: on parle de variables indépendantes et identiquement distribuées (i.i.d.). On décrira cette loi par sa distribution de probabilité :
B (x) = P ftemps de service 2.3.1
xg
Le temps de service résiduel
Une question qui revient souvent: j'observe un service qui a déjà atteint l'âge
y. Je m'interroge sur la distribution de la durée restant à courir jusqu'à X la variable aléatoire correspondante).
la n de ce service (notons
Début de service
Y
Fin du service
=y
X Observation
Fig. 2.3
Calcul de la distribution du temps résiduel
La réponse est très simple: dire que
X >x
secondes restent à accomplir
y + x, et savoir que Y = y sachant que la durée totale est supérieure à y: c'est une probabilité conditionnelle. On a alors pour la distribution de X :
revient à dire que la durée totale sera supérieure à revient à calculer la probabilité
P (X > xjY
= y) = =
P (service > x + yjY = y) P (service > x + y) 1 B (x + y) = 1 B (y ) P (service > y)
(2.4)
De façon équivalente, la densité sera
P (X 2 [x;x + dx[jY ) = 2.3.2
b(x + y)dx 1 B (y )
(2.5)
La loi exponentielle
La loi de service la plus populaire est la loi exponentielle, qu'il est traditionnel d'écrire en utilisant comme taux de service la lettre
B (x) = P (service x) = 1 e la densité correspondante est
b(x) = e
x
:
x
(2.6)
12
Files d'Attente et Trac
La loi exponentielle doit une bonne partie de son prestige à la propriété sans mémoire, déjà rencontrée, et qui pourrait ici s'énoncer ainsi: savoir que le service a déjà duré 1 heure n'apporte aucun renseignement sur sa n prochaine. On remarquera en eet que, pour la loi exponentielle, la densité calculée à l'équation (2.5) vaut:
e
b(xjy) = indépendamment de
y.
(x+y)
e
y
= e
= b(x)
x
L'application de cette absence de mémoire montre
que la probabilité d'une n de service dans l'instant qui vient (dans l'intervalle
[t;t + dt[) est dt, quel que soit l'âge du service.
La loi exponentielle se caractérise par ses moments:
1=. 1=( )
Moyenne de la variable :
2
Variance de la variable : On introduit le
Est-il besoin de le rappeler l'écart-type est la racine carrée de la variance ?
coecient de variation, rapport de l'écart-type du temps de
service à sa moyenne. Ici, on voit que le coecient de variation vaut 1.
2.3.3
Lois d'
Erlang
Supposons que le processus de service soit composé d'une cascade de
k ser),
veurs élémentaires exponentiels, identiques (c'est à dire, de même paramètre
et indépendants les uns des autres. Le temps du service est la somme des temps passés dans chaque serveur. Supposons
= 2. Notons X le temps total, X
k
B
temps services; la distribution
B
2:
P fX xg = P fX
1
Evidemment,
B
1
et
B
et
1
X
de
X
2
est donnée par la
+ X xg = 2
Z
x u=0
les durées des deux
convolution
de
B
1
et
B (x u)dB (u) 1
2
sont identiques, et correspondent à l'exponentielle.
2
P fX xg
Z
h
x
= u = 1
=0
e
1 x
e
(x u)
xe
i
e
x du
x
Plus généralement, on montre (voir annexe à ce chapitre) que la mise en cascade de
k
serveurs exponentiels de même paramètre
bution:
B (x) = P fX
1
+ X + + Xk xg = 1 2
On appelle cette distribution la
k
conduit à une distri-
k X (x)j j =0
j!
distribution d' Erlang-k,
e
x
(2.7)
et la loi de pro-
babilité (2.7) est la loi d'Erlang- . Puisqu'il s'agit d'une somme de variables aléatoires indépendantes, moyenne et variance s'obtiennent facilement, comme la somme de la moyenne et de la variance de chaque variable exponentielle: Moyenne de la variable :
k=.
2.4 Processus de Naissance et de Mort
Variance de la variable :
k=(
)p 1= k.
2
Le coecient de variation est
2.4
13
Processus de Naissance et de Mort
2.4.1
La notion d'état
La notion d'état a une base intuitive: décrire l'état d'un système, c'est donner la liste des caractéristiques qu'il possède, et aussi donner les éléments qui permettent de prévoir son évolution. En mécanique, par exemple, on décrit l'état d'un point matériel par ses coordonnées
x;y;z
vx ;vy ;vz . via les
et par sa vitesse
Ces quantités une fois connues, on peut décrire la position du point, et équations de la mécanique, la trajectoire qu'il doit suivre.
Il en est de même pour un système stochastique, à la diérence que la prévision du futur y prend un caractère probabiliste: on ne saura prévoir l'état exact dans quelques secondes, mais seulement sa distribution de probabilité.
2.4.2
Chaînes de
Markov
X , à espace d'état discret (X ne prend ses X peut représenter le nombre des clients dans un tampon: X = 0;1;2; ). On peut noter les états E ;E ; ;Ek . Notons t ;t ; ;tn les instants successifs des changements d'état de X , et x ; ;xn la suite des états visités. Les tn pourraient être, par Considérons une variable aléatoire
valeurs que dans un espace discret. Pour se xer les idées,
1
2
1
2
1
exemple, les instants d'arrivée et de départ dans le tampon. Dans le cas général, l'étude de l'évolution de
X
est très dicile. Il existe une circonstance capitale,
qui est la base de tous les développements qui suivent: Dans le cas général, la
Andrei Andreyevich
valeur de
Markov,
X à l'instant tn dépend de tout le passé, c'est à dire de X (t );X (t ), etc. On dira que X obéit à la propriété de Markov si: P [X (tn ) = xn j X (tn ) = xn ;X (tn ) = xn ; X (t ) = x ] = P [X (tn ) = xn j X (tn) = xn] En bref, seul l'état courant (à tn ) inuence l'évolution prochaine du processus. C'est encore la propriété sans mémoire. Supposons de plus le processus homogène, c'est à dire invariable par trans+1
1
+1
+1
+1
+1
1
1
1
2
1
lation dans le temps. Ceci autorise à introduire la notation:
pj;k = P [X (tn
+1
) = Ek j X (tn) = Ej ]
(sans l'homogénéité, il aurait fallu introduire une notation du genre propriété de Markov se traduit par:
P [X (tn
+1
) = Ek ] =
X j
pj;k P [X (tn ) = Ej ]
pnj;k ).
La
(2.8)
C'est là la forme élémentaire d'un résultat fondamental, connu sous le nom d'Equation de Chapman-Kolmogorov. Le processus étudié est une Markov.
chaîne de
mathématicien russe (1856-1922)
14
Files d'Attente et Trac
2.4.3
Les processus de naissance et de mort
L'étude des processus de Markov les plus généraux est un des grands chapitres du Calcul des Probabilités. Pour les besoins très limités de ce rappel, nous nous limitons au cas très particulier et très utile où le processus ne peut faire de sauts que vers ses voisins les plus proches. Les seuls mouvements
Ek et Ek . Le taux de passage de Ek à Ek + 1 est k : c'est le taux de naissance. Le taux du passage de Ek vers Ek est le taux de mort k . Le processus de naissance et de mort a été introduit dans l'étude de l'évolution des populations: l'état Ek fait référence à autorisés sont de
Ek
vers
+1
1
traditionnellement noté 1
la taille. En accord avec cette origine, et pour simplier l'écriture, on nommera les états plus simplement
1;2;3; , sans perte de généralité.
Le problème est simple: nous cherchons à dériver la distribution de probabilité de l'état, c'est à dire la fonction
Pk (t) = P [X (t) = k] Nous allons procéder en utilisant la dynamique des équation de Chapman-
t, et examinons les possibilités. A t + t, l'état sera k si: A t, l'état était k et rien ne s'est produit. A t, l'état était k 1 et une naissance s'est produit durant l'intervalle (t;t + t). A t, l'état était k +1 et une mort s'est produit durant l'intervalle (t;t +t). L'intervalle t est petit. D'autres événements plus complexes (2 arrivées, etc.) auront lieu avec des probabilités en o(t). On écrira donc:
Kolmogorov. Plaçons-nous à un instant
l'instant
Pk (t + t)
= Pk (t)(1 k t k t) + + Pk (t)k t + + Pk (t)k t + + o(t) 1
1
+1
+1
Cette équation transcrit dèlement la description des possibilités donnée ci-dessus. A partir de cette forme, on écrit une équation diérentielle par les traitements classiques:
Pk (t + t) Pk (t) t
t) = (k + k )Pk (t) + Pk (t)k + Pk (t)k + o( t 1
1
+1
+1
Cas particulier, en 0 la transition de mort n'existera pas. Finalement, le passage à la limite conduit au système diérentiel fondamental:
dPk (t) dt dP (t) dt 0
=
(k + k )Pk (t) + Pk (t)k + Pk (t)k
=
P (t) + P (t)
1
0
0
1
1
1
+1
+1
(2.9) (2.10)
2.5 Les les d'attente classiques
15
Nous nous limiterons au cas de systèmes à l'équilibre. Pour un système dynamique à l'équilibre, un
régime permanent existe, tel que les probabilités d'état
ne dépendent pas du temps. On réécrira simplement le système ci-dessus, en y annulant toutes les dérivées. La distribution stationnaire sera notée
(k + k )Pk = P = 0
Pk k P 1
0
1
1
+ Pk
+1
k
Pk .
(2.11)
+1
(2.12)
1
P en fonction de P , puis P en P et P , et ainsi de suite. On achève le calcul par la condition de normalisation, qui dit que le système doit bien se trouver quelque part: Système que l'on résout par récurrence:
fonction de
0
1
0
2
1
X k
Pk = 1
(2.13)
Le jeu des équations (2.11,2.12) admet une interprétation très fructueuse. On
(k +k )Pk comme un ux de probabilité qui k. Un terme tel que k Pk mesure le ux de probabilité montant
peut interpréter le terme de gauche quitterait l'état de
k vers k + 1. Ce ux est le produit de la probabilité de se trouver dans l'état
par le taux de départ montant (sachant qu'on s'y trouve, si l'on veut). La même interprétation vaut pour les autres termes. L'équation dit alors que, pour que les probabilités gardent des valeurs constantes, il doit y avoir égalité entre les ux entrant et sortant des diérents états.
λ k-1 k-1
λk k
µk Fig. 2.4
k+1
µ k+1
Diagramme d'évolution d'un processus de naissance et de mort
On met à prot cette interprétation pour écrire très rapidement les équations, à partir d'un diagramme analogue à celui de la Figure 2.4.
2.5
Les les d'attente classiques
Nous rappelons très brièvement les principaux résultats: se reporter à un cours élémentaire de les d'attentes.
16
Files d'Attente et Trac
2.5.1
La Notation de
Kendall
Pour identier un système à les d'attentes, le formalisme suivant a été proposé et est unanimement adopté: A/B/n/K/N La première lettre identie la loi du processus des arrivées, la seconde le processus des services, avec dans les deux cas les conventions: M : loi sans mémoire (arrivées poissonniennes, service exponentiel); D : loi déterministe; Ek : loi Erlang-k Hk : loi hyperexponentielle d'ordre k; GI : loi générale, les variables successives étant indépendantes; G : loi générale, sans hypothèse d'indépendance. Le chire qui suit donne le nombre de serveurs, les lettres qui suivent (facultatives) identient la taille de la le d'attente et la taille de la population source (si ces valeurs sont omises, elle sont supposées innies). Par exemple, M/M/1 fait référence au modèle de base: arrivées poissonniennes, service exponentiel, un seul serveur, le d'attente non bornée. M/D/K/K indique un service de durée constante, K serveurs et K places au total (c'est à dire pas d'attente: modèle d'Erlang, voir plus loin). Dans une le d'attente, un paramètre de première importance est le taux
. C'est le produit du taux d'arrivée des = E (s). On peut montrer que 1 donne
d'utilisation, noté traditionnellement clients par le temps de service:
la probabilité de trouver le serveur inactif. Il faut (pour une le de capacité innie) que
2.5.2
< 1 (condition de stabilité).
Résultats généraux
Résoudre un système de les d'attentes consistera, en fonction des paramètres (taux d'arrivée
, taux de service ), à écrire la distribution du nombre
des clients dans le système et du temps d'attente ou à défaut de prévoir les moyennes de ces quantités. On peut citer quelques résultats de portée générale indépendants des lois des processus mis en ÷uvre: Le paramètre
= =
est le taux d'activité. La probabilité stationnaire
que le serveur soit inactif est
P
0
=1
(voir la discussion des notions de
tracs oert et écoulé à ce sujet).
Les nombres moyens et les temps d'attente sont reliés par la célèbre
for-
mule de
Little:
L'indice
x signie qu'on peut donner à ces grandeurs toute interprétation
E (Nx ) = E (Wx )
possible: le temps moyen d'attente et le nombre des clients en attente; ou bien le temps de séjour et le nombre des clients séjournant; etc.
2.5 Les les d'attente classiques
17
Cette dernière formule est très importante. Une preuve intuitive peut en être donnée, basée sur un raisonnement graphique très simple. Observons l'occupation du système (noter qu'on ne fait
aucune hypothèse
sur celui-ci). Chaque fois qu'un client entre ou sort, on met à jour le nombre des présents, et l'évolution de
N (t),
nombre de clients présents, ressemble au
diagramme suivant (Figure 2.5):
T 1
N(t)
2
3
4
5
xxxxxxx xxxxxxx xxxx xxxxxxx xxxx xxxx
xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx
t 2 31 Fig. 2.5
54
La formule de
Little
Pour estimer le nombre moyen de clients dans le système, on peut compter
P
la surface totale interceptée par par chaque client:
Dk , Dk
N (t):
c'est la somme des surfaces apportées
étant la durée que le client
système. Le nombre moyen sera alors
E (N ) =
lim T !1
k va passer dans notre
P
Dk T
(en eet, la moyenne est dénie traditionnellement comme une limite). Maintenant, la somme peut se ré-écrire, en introduisant le nombre dans la durée
T:
P
Dk T
=
P
Dk n
n de clients concernés
Tn
Sous des conditions assez générales, la limite du produit est égale au produit
n=T est simplement le taux d'arrivée du processus on . Le premier terme n'est rien d'autre que le temps moyen que chaque
des limites. Le terme le note
client passe dans le système. Si le système est le tampon d'attente, on retrouve l'expression précédente. On peut aussi donner au système d'autres sens (et par
18
Files d'Attente et Trac
exemple, la formule relie aussi bien le nombre moyen des clients verts au temps moyen qu'ils passent dans le système, etc.) .
2.5.3
File M/M/1
C'est le modèle à le d'attentes le plus célèbre à juste titre, certainement. Il permet en eet d'illustrer les concepts fondamentaux liés à l'attente devant un serveur, tels que les présentent les quelques exercices (classiques) proposés au Chapitre suivant.
, ), la le d'attente de capacité innie. Les
Le système est décrit par le processus des arrivées, poissonnien de taux la loi exponentielle de service (taux
clients pourront être supposés servis dans l'ordre de leur arrivée si cela peut ai-
n>0 1 en attente) à un instant t, la n de service du client en cours se produit dans l'intervalle (t;t + t) avec une probabilité t + o(t): propriété fondamentale de la loi de service exponentielle. De même, une arrivée se produira dans l'intervalle, avec probabilité t + o(t). On applique à ce système le formalisme et les résultats obtenus der l'intuition mais cette hypothèse n'est en fait pas nécessaire. Lorsque clients sont dans le système (un en service,
n
plus haut sur le processus de naissance et de mort. L'état est décrit par
n, qui
représente cette fois le nombre total des clients dans le système. Il évolue selon un processus de Naissance et de Mort très simple (gure 2.6).
0
-
1
....
2
Fig. 2.6
-
-
k
-
....
Evolution de l'état de la le M/M/1
Du diagramme, on déduit les résultats qui suivent. On va ici en donner une démonstration détaillée. Pour les autres systèmes plus loin, l'exercice est laissé au lecteur. L'analyse du système, selon la procédure des équations de Chapman-kolmogorov, aboutit aux équations suivantes:
P ( + )Pk
0
= =
P Pk + Pk
La sommation des équations de rang 0 à simple:
1
1
+1
n conduit à la forme particulièrement
Pn = Pn
+1
soit
Pn
+1
= Pn (avec = =) et par récurrence Pn = n +1
+1
P
0.
La normali-
2.5 Les les d'attente classiques
sation achève le traitement:
X
19
X
Pn = P
0
k
k =
1
P
0
=1
Finalement:
= n(1 ) PW = E (n) = 1 E (nW ) = 1
n0
Pn
=
(2.14)
2
PW déduit,
= . 1
E (n) donne le nombre E (nW ) le nombre moyen en attente. On en
est la probabilité qu'un client ait à attendre.
moyen de clients dans le système, et
via
la formule de Little, les temps moyens d'attente
1
=
et de séjour
1
un rôle important. Tout spécialement, doit être strictement inférieur à 1, sinon les quotients n'ont plus de sens. On montre que la condition < 1 est une condition nécessaire Les expressions ci-dessus font jouer à
elles imposent une limite:
et susante d'existence des probabilités stationnaires, ce qui est conforme à l'intuition.
2.5.4
La le M/M/c
Mêmes hypothèses et notations que ci-dessus, avec un nombre identiques en pool. Que deviennent les taux de service ? Imaginons le système dans l'état présents, qui occupent
k < c.
Cela signie que
c de serveurs
k
Le lecteur débutant
clients sont
k serveurs (les autres sont inactifs). Dans l'intervalle t
qui vient, chacun des services en cours peut se terminer, avec la probabilité
t + o(t)
(services exponentiels). La probabilité d'une et une seule n de
service est la somme des probabilités que chacun des services s'achève, diminuée de la probabilité de 2 ou plus ns de services
o(t)
2
événement de probabilité en
, donc négligeable dans l'opération de passage à la limite. Le taux de
k tant que k < c et c au-delà (parce que c est la limite au A et le trac par serveur est = A=c. La condition de stabilité reste < 1 soit A < c .
service vaut donc
nombre des serveurs actifs) . Le trac oert est noté On trouve:
k
P (k) = P (0) Ak c P (k) = P (0) Ac ()k !
!
avec
P (0) =
"c k XA 1
0
c
kc k>c
Ac 1 + k! c! 1
#
(2.15) (2.16)
1
(2.17)
devra suivre ce qui suit avec attention
20
Files d'Attente et Trac
La probabilité d'attendre est
PW
= Ac! 1 1 P (0) = C (A;c) c
(2.18)
On connaît cette formule sous le nom de Formule d'Erlang
Le temps moyen d'attente se déduit de ce qui précède, au prix de quelques calculs:
E (W ) =
avec attente ou Erlang-c
2.5.5
PW
c(1 )
E (s)
(2.19)
Modèles à capacité limitée
Le modèle M/M/1/K correspond au cas d'une capacité de tion, l'usage veut que
K
K clients. Atten-
représente le nombre total de clients dans le système,
c'est à dire en attente ou en service. Le diagramme d'évolution est obtenu par la troncature du diagramme M/M/1, et les équations donnent facilement le résultat:
P (n) =
n (1 ) 1 K
(2.20)
+1
Le critère de QS est bien sûr la probabilité de rejet:
K = 1 (1K )
(2.21)
+1
Evidemment, ici on peut lever la condition
< 1. On remarque que = 1
conduit à une diculté sur la formule. C'est qu'en réalité elle est arrangée, et il faudrait lire par exemple
K
= 1 + + + + K 2
2.5.6
Erlang)
Modèle M/M/R/R (modèle d'
C'est le modèle de système le plus simple, et le premier à avoir été étudié. Considérons un groupe de serveurs, exploités en pool, c'est à dire que chacun des serveurs peut servir indiéremment les clients qui se présentent. Les clients arrivent devant le groupe des serveurs selon un processus de Poisson, de taux
.
A leur arrivée, les clients sont servis immédiatement tant qu'un serveur au
moins est libre; si les serveurs sont tous occupés, le client qui arrive est rejeté, et est supposé disparaître dénitivement. On parle de modèle à perte. Il est aisé d'adapter le modèle de la le M/M/c, en tronquant le diagramme d'état au rang On trouve:
R. On note A = =. P (k) =
Ak PRk! Ak 0 k!
0kR
(2.22)
2.6 La notion de Trac
2
0
-
1
Pour d'obscures
....
2
Fig. 2.7
-
k
k
....
R
AR
E (R;A) = P (R) = PRR Ak !
anglo-saxons la nomment formule
(2.23)
k!
0
comme probabilité de trouver le système plein; compte tenu de la nature des arrivées, c'est aussi la probabilité de rejet. La notation
E (R;A)
est assez clas-
sique. Il est possible de prouver que le résultat précédent est valide même pour un service de type quelconque (système M/G/R/R). Le calcul eectif de la formule de la perte pose problème sous la forme cidessus: il serait vain d'évaluer une factorielle par une méthode directe! Il vaut mieux utiliser une récurrence:
X := 1 pour j de 1 a R faire X := 1 + X*j/A fin pour E(R,A) := 1/X On pourra aussi souvent utiliser une approximation (remplacer la somme au dénominateur par l'exponentielle, et utiliser la formule de Stirling pour les factorielles), qui donne une précision assez spectaculaire:
E (R;A)
A R R
p
e A=
2R
(2.24)
Anticipant sur les dénitions des tracs écoulés, le calcul du trac écoulé permet de vérier la concordance des dénitions:
Ae =
X
jP (j ) = A[1 E (A;R)]
(2.25)
L'hypothèse du service exponentiel n'est pas nécessaire, les résultats restant valables pour une loi quelconque (de moyenne permet des calculs simples.
2.6
-
Diagramme d'état du modèle d' Erlang
et.
raisons, les
d'Erlang-b
-
1=). L'hypothèse exponentielle
La notion de Trac
Les mécanismes d'occupation des ressources constituent le phénomène fondamentalement responsable de la dégradation possible de QoS; en eet, le réseau
R
21
22
Files d'Attente et Trac
ore des ressources en commun à ses utilisateurs, que ceux-ci doivent se partager. Le terme de trac rend compte de la quantité de travail présente dans un serveur, sous forme d'occupation de ce serveur. Le terme désigne à la fois la notion de travail qu'un réseau va traiter (on parle ainsi du trac routier, par exemple) et la grandeur numérique qui mesure ce travail.
2.6.1
Réseau fonctionnant sans attente
C'est le cas normal d'un réseau à commutation de circuits. Observons un groupe de circuits (faisceau reliant deux commutateurs du réseau téléphonique, par exemple). Le nombre de circuits occupés concerne directement la source (susceptible de réclamer un circuit et d'essuyer un échec). Ce nombre uctue, et
trac écoulé. En termes N (t) le nombre des circuits occupés à l'instant t, le trac écoulé Ae sera l'espérance mathématique de N (t) (supposant les bonnes l'on peut en dénir une valeur moyenne, qu'on appellera mathématiques, si on note
conditions de stationnarité).
ZT 1 Ae E (N ) = Tlim N (t)dt !1 T
(2.26)
0
Comment estimer expérimentalement cette grandeur ? Supposons qu'on observe un groupe de
R circuits (ceci est valable, bien sûr, pour tout système de
serveurs recevant des clients, selon la terminologie de la Théorie des Files
T , susamment long; des connexions d ;d ; dk . Le plus souvent, des connexions
d'attentes). L'observation dure un temps ont lieu, dont on enregistre les durées:
1
2
ont déjà commencé et sont en cours à l'instant 0, d'autres ne s'achèveront qu'après
T . On incorpore alors au comptage la fraction incluse dans l'intervalle.
On estimera le trac écoulé par:
P
di T (en toute rigueur, il faudrait augmenter T indéniment, ce qui éliminera tout eet de bord : la quantité ci dessus est un estimateur du trac écoulé). La preuve de l'identité entre les deux expressions de Ae est, là encore, dans le Ae
mode de calcul expérimental de la moyenne: on estime la surface en comptant les pavés de la gure 2.8. Le trac écoulé peut s'interpréter d'une autre façon. Soit
d la durée moyenne
de service (supposant, encore une fois, l'existence de toutes les limites nécessaires). Soit
n le nombre des clients
arrivant dans la période de mesure
La formule dénissant le trac peut s'écrire:
Ae =
P
di T
=
P
di n
Tn
Le premier terme représente la durée moyenne de service (là encore, si donc
n,
(0;T ).
T,
et
tendent vers l'inni). Le second terme représente le taux des arrivées
acceptées (nombre par unité de temps). Il faut faire la distinction entre les clients arrivés et ceux qui sont acceptés, puisque des rejets peuvent s'observer.
2.6 La notion de Trac
23
3 2 1
6
N (t)
4
-
d
1
? ?
?
3
2 4
1
t 1
2
3
?
?
?
T
Fig. 2.8
-
4
? -
Calcul de l'intégrale donnant Ae
Le produit ci-dessus admet lui-même une autre formulation. Le produit d'un taux d'entrée par une durée donne évidemment le nombre entrant pendant cette durée:
Ae
est la moyenne du nombre des clients qui entrent pendant la durée
du service. En résumé, le
trac écoulé est, à la fois (on retrouve là un avatar de la
formule de Little):
Comparer avec la démonstration de la
Le nombre des clients entrant dans le système pendant la durée moyenne
formule de Little
de service. Le produit du taux d'arrivée par la durée moyenne du service. Le nombre moyen des serveurs occupés.
Le trac écoulé est une grandeur sans dimension. On le compte en erlangs On dénit aussi le
trac oert. C'est le nombre
A
pendant la durée de service (dont certains seront rejetés). Par construction, le
Ae écoulé par Ae R. Pour
trac
0
un groupe de
R
serveurs vériera évidemment l'inégalité
le trac oert, il n'a pas de limite. Le taux de rejet
B,
ou la probabilité de perte, s'écrira comme le quotient du nombre de demandes rejetées au nombre de demandes présentées
n (ne
est le nombre accepté) dans
tout intervalle de temps, par exemple la durée moyenne de communications. Et donc,
B=
n ne n
= A AAe
Agner Krarup
des clients arrivant Erlang,
(2.27)
mathématicien danois, père de la théorie du télétrac (1878-1929)
24
Files d'Attente et Trac
2.6.2
Réseau fonctionnant avec attente
On est, ici, dans la conguration du réseau à commutation de paquets. Les mêmes notions, les mêmes dénitions s'appliquent encore. Le cas très fréquent d'un serveur unique ore la possibilité d'enrichir les notions présentées. Considérons, dans un réseau de paquets, la ligne de transmission sortante, reliant deux noeuds du réseau. Les paquets doivent attendre dans la le de sortie pour être émis l'un après l'autre. Cette fois-ci, l'état de la ligne est encore décrit par
N (t); 0 N
R, mais avec R = 1 (c'est à dire, le serveur est libre ou occupé).
Si l'on suppose une le d'attente de capacité innie, aucun rejet ne se produit, et les notions de trac oert et de trac écoulé se confondent. Puisqu'il n'y a qu'un seul serveur, le nombre moyen de serveurs occupés se réduit à la probabilité d'observer le serveur occupé (moyenne de l'indicatrice de l'événement {serveur occupé}). Les dénitions équivalentes mentionnées plus haut conduisent à la relation classique:
= E (s) = 1 P
(2.28)
0
Dans cette expression, ditionnelle),
E (s)
désigne le taux des arrivées (c'est la notation tra est le trac oert (c'est aussi
le temps moyen de service,
une notation classique).
P
0
représente la probabilité stationnaire de trouver le
serveur libre (proportion du temps d'inactivité. Les clients qui arrivent peuvent mesurer une probabilité d'inactivité diérente, on y reviendra). Les systèmes à attente sont cependant, de façon inévitable, à
capacité limitée,
et la distinction oert/écoulé reprend alors son sens.
Annexe A: utilisation des fonctions génératrices La résolution directe par substitution des équation d'état est d'une compréhension immédiate, mais se révèle fastidieuse, dès lors que le problème dépasse le cas d'école ! Il existe une méthode très astucieuse, et très puissante lorsqu'appliquée à des problèmes complexes, c'est l'utilisation des fonctions génératrices.
(Pk ;k = 0; ). On a P Pk = 1; cette relation fondamentale stipule qu'on a af-
Soit une distribution de probabilité sur les entiers (bornée ou non). Notons-la
faire à une distribution de probabilité réaliste (c'est à dire que la distribution existe, qu'on est en régime stationnaire). La
fonction génératrice de la distribution est la fonction de la variable com-
plexe:
P (z ) =
existe (
il s'agit
k
z k Pk
jz j < 1
(2.29)
z est de module strictement inférieur à 1, la fonction P (z ) < P (1) = 1), et, puisqu'elle est la somme d'un polynôme, d'une fonction analytique de la variable complexe (cette remarque est
Puisque la variable
P (z )
X
fondamentale).
2.6 La notion de Trac
25
P (z ):
Etudions alors les dérivées successives de
P 0 (z )
=
P 00 (z )
=
X k X k
Prenant alors ces quantités au point
P 0 (1)
=
P 00 (1)
=
X k
X k
kz k Pk 1
k(k
1)zk
2
Pk
z = 1, il vient:
kPk = E (k) k (k
(2.30)
1)Pk = E (k )
E (k )
2
(2.31)
Comment appliquer ces résultats ? Reprenons le cas élémentaire de la le M/M/1:
Pn = n (1 ). Le calcul de la fonction génératrice est un jeu d'enfant: P (z ) =
X n
z nn (1 ) =
1 1
z
Notons qu'on aurait pu, à partir du jeu des équations, calculer la forme de la fonction génératrice. Dans ce cas simplissime, on multiplie chacune des équations de rang
k par z k , puis un eectue la somme: le jeu des équations P ( + )Pk
0
= =
P Pk + Pk 1
1
+1
conduit à
P ( + )zk Pk
0
= =
P z k Pk 1
1
+ zk Pk
+1
soit, par sommation,
z ) = P z z
P (z )( + z soit, nalement
En
P (z ) =
0
1
P
1
0
z
z = 1, on doit avoir P (1) = 1, ce qui implique P
0
=1
.
De cette expression très synthétique, on déduit les dérivées première et seconde, et donc les deux premiers moments, et la variance du nombre de clients dans la le. Le lecteur débutant est invité à refaire ce calcul avec soin. Dans ce cas très simpliste la justication peut en paraître fallacieuse. Vois cependant les références (par exemple [Kle 76]) pour des usages plus justiés.
26
Files d'Attente et Trac
Annexe B: Et si le ux n'est pas poissonien ? Alors ... tout peut arriver ! Examinons ici le cas du modèle M(n)/M/R/R (modèle d'Engset). C'est une circonstance favorable en ce sens que les probabilités de rejet, par exemple, seront inférieures à ce qu'elles seraient dans le modèle d'arrivées poissonniennes. D'autres congurations conduiraient à des cas plus défavorables (ce qu'on appelle le
trac de débordement, où la sporadicité
des ux entrants conduit à des performances pires que le cas poissonnien. La population des sources a une taille limitée. Le processus d'arrivée est alors fonction de l'état de celles-ci (une source active ne génère pas de nouvelle demande). Une source devenant active et trouvant tous les serveurs occupés n'attend pas, et retombe immédiatement dans l'état de repos. Elle aura subi un échec, et le problème principal sera de calculer la probabilité de cet événement. C'est le système M(n)/M/R/R. On récrit les équations. Cette fois, les événements élémentaires sont:
L'arrivée d'un nouveau client, qui fait passer de taux correspondant est
n
= (N
susceptibles d'engendrer un client. La n d'un service, avec le taux
0
n en n + 1 si n < R. Le N n sources au repos
(N-2) λ
1 µ
reste
n, qui fait passer de n en n
(N-1) λ
Nλ
Fig. 2.9
n) : il
(N-R+1) λ
...
2
R-1
(R-1) µ
2µ
1.
R Rµ
Diagramme du processus du système M(n)/M/R/R
Le jeu des équations donnant la probabilité stationnaire d'observer
n serveurs
occupés s'écrit:
8 > < (N nN)Pn = (n + 1)Pn X Pn = 1 > :
n = 0; : : : ;N
+1
1 (2.32)
n=0
L'approche par
La solution s'écrit:
fonctions génératrices s'applique aussi, mais réclame du doigté
Pn = P
n
j j R
N n
N j
Rappel :
N n
= n!(NN ! n)!
(2.33)
2.6 La notion de Trac
27
La Probabilité de Rejet
Attention!
PR n'est pas la probabilité de rejet !
Méditant sur la construction du diagramme et sur sa signication, on se rend compte que cette quantité représente la proportion du temps où tous les serveurs sont occupés. C'est la probabilité d'occupation que mesurerait par échantillonnage un observateur extérieur, c'est à dire indépendant du système (de façon
Pk est la proportion du temps où le système réside dans l'état k). Mais les clients qui arrivent ne le font pas indépendamment de l'état du système, toujours à cause de la forme des n . Ils ne se font donc pas rejeter
générale,
indépendamment de l'état. Comment alors calculer la probabilité de rejet? La manière la plus simple de l'obtenir est de l'écrire comme le quotient du taux d'arrivée dans l'état de rejet
fn = cg par le taux moyen d'arrivée (c'est à dire exactement la proportion de clients perdus).
B P (Rejet) =
(N
R)PR
Au prix d'une gymnastique algébrique modérée, la formule s'exprime en fonction des quantités déja connues:
n
B=P
j R
On constate que
B
= PRN (
1)
N
j
R
1
N
j
1
(2.34)
, c'est à dire la probabilité d'occupation to-
tale pour un système comptant 1 source en moins. Signalons, en commentaire, que la formule (2.34) ci-dessus s'applique même si la loi de service n'est pas exponentielle. Cette formule est connue sous le nom de formule d'Engset.
Dimensionnement d'un Concentrateur d'Abonnés
A titre d'exemple,
considérons un étage d'abonnés, concentrant le trac de nombre restreint
R
N
usagers sur un
de lignes vers le commutateur. Compte tenu des usages
téléphoniques des abonnés, il faut calculer
R pour orir une Qualité de Service
donnée sans pour autant utiliser des circuits dont le rendement serait trop faible. La gure suivante montre ce que donne la formule, selon les valeurs de
de
, pour R = 10.
On voit que quand
N
grandit, (pour un produit
N N
perte augmente. On vérierait que la limite (quand
N
et
constant), le taux de
! 1)
est celle que
donne la formule d'Erlang (le M/M/R/R). On voit aussi sur la courbe l'eet bénéque de la population limitée. Application numérique: un trac poissonnien de 4 erlangs oert à 10 circuits subit une perte de l'ordre de
5:10
3
; si le trac est issu d'un groupe de 20
sources, le rejet sera 10 fois plus faible (
5:10
4
).
28
Files d'Attente et Trac
1
0.1
Taux de Perte
0.01
0.001 Na=4 Na=5 Na=6 Na=7 Na=10
0.0001
1e-05
1e-06 10
100 Nombre de sources
Valeur de la probabilité de rejet en fonction du nombre des sources, pour R = 10 serveurs Fig. 2.10
Annexe C : La somme de n exponentielles Soient
X ; ;Xn 1
des variables exponentielles i.i.d. (indépendantes et iden-
tiquement distribuées). Quelle est la distribution de probabilité de la somme
X
1
+ + Xn ? Cette question est avantageusement abordée via les méthodes transformée de Laplace de la densité f (x) est donnée par:
de transformées. La
F~ (s) =
Z1
e
0
sx f
(x)dx
On se reportera à son cours de maths pour les propriétés de ces fonctions. La transformée de Laplace de la distribution commune des
Xi est =(s + ).
La transformée de la somme des variables indépendantes est le produit des transformées, soit en notant
Fn (t) la distribution:
L(Fn ) = + s
n
2.6 La notion de Trac
29
On trouve, en consultant une table de transformées, la densité de probabilité correspondante:
fn (t) =
(t)n e (n 1)! 1
t
Exprimé sous forme de distribution:
Fn (t) = P fX
1
+ + Xn tg =
n X (t)k k=0
k!
e
t
La gure qui suit donne la probabilité de perte d'Erlang.
(2.35)
30
1
N=1 0.1
N=2
Probabilite de Rejet
0.01
0.001
N=3
N=4 0.0001
N=7
10
15
20
Files d'Attente et Trac
N=5
25
1e-05 30 35 1e-06
40 45 50
1e-07 0.1
1
10 Trafic Offert
100
Chapitre 3
Mécanismes de partage de ressources Sommaire 3.1
Un exemple de système temps-réel . . . . . . . . . 3.1.1
Un serveur de messagerie
3.1.2
Caractéristiques des tâches
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32 32 33
3.2
Les mécanismes d'ordonnancement . . . . . . . . .
34
3.3
Notion de Système Conservatif . . . . . . . . . . .
35
Formule de la somme pondérée . . . . . . . . . . . . Priorité entre clients identiques . . . . . . . . . . . .
3.4 3.5
3.6
35 37
La discipline HOL . . . . . . . . . . . . . . . . . . .
37
Le Serveur Cyclique ("Polling")
39
. . . . . . . . . .
3.5.1
Introduction
. . . . . . . . . . . . . . . . . . . . . .
39
3.5.2
Un exemple numérique . . . . . . . . . . . . . . . . .
41
3.5.3
D'autres politiques . . . . . . . . . . . . . . . . . . .
Annexe: calcul du temps de service restant . . . .
31
42
43
32
Mécanismes de partage de ressources
n
système informatique moderne est une organisation complexe, à la fois de
par l'architecture matérielle et de par le type de programmes qui y sont traités. Même "centralisé", il comporte de nombreuses entités distinctes (contrôleurs, disques, coprocesseurs, etc), qui coopèrent. L'agencement harmonieux et ecace de tous ces éléments impose des mécanismes d'ordonnancement des tâches. La modélisation doit impérativement prendre en compte ces particularités de fonctionnement, et doit aider à leur mise au point.
3.1
Un exemple de système temps-réel
3.1.1
Un serveur de messagerie
Considérons une machine, utilisée par les services de messagerie vocale (un
serveur vocal): répondeurs, boite aux lettres, jeux, annonces, etc. Fonctions du
serveur: stocker et gérer les messages, les restituer sur demande. Le dialogue usager-service est vocal ou utilise les touches du combiné. La gure 3.1 donne un exemple d'architecture d'une telle machine.
Stockage des messg Scripts Bus local Processeurs
Brasseur
Lignes reseau Fig. 3.1
Architecture d'un serveur vocal
Chaque communication se conforme approximativement au schéma suivant: sur détection d'un appel du réseau, aectation d'un processeur; dialogue avec l'usager (envoi d'un message, écoute de la réponse; action suivante; etc);
3.1 Un exemple de système temps-réel
33
le service" désigne un processeur particulier chargé du pilotage du dialogue; c'est lui qui contient le service eectif, on parle de
script;
dérouleur de
consultation de la BD où sont stockés les messages vocaux de l'usager, pour les délivrer; etc. Chaque communication est décrite par un script", dans lequel chaque action correspond à un travail d'une des entités du serveur. Le script contient de nombreux branchements, correspondant aux décisions de l'usager ou aux fausses man÷uvres. On pourrait expliciter encore le schéma ci-dessus, en y faisant apparaître les actions élémentaires des processeurs, les lectures et écritures en mémoire, par exemple. On voit combien le déroulement d'une communication est complexe, et ressemble en fait au traitement des programmes d'un système informatique multiprogrammé. Les questions que cette description amène concernent en premier lieu les possibilités et les performances de la machine combien de communications peut-elle accepter, quel est son temps de réponse. Elles concernent aussi les choix de conception et de dimensionnement nombre de processeurs, taille de mémoires, organisation du traitement des requêtes, etc. Pour y répondre, on bâtira un modèle du fonctionnement de la machine. Ce sera un
"réseau de les d'attentes",
chaque serveur y représente une ressource
active (processeur) devant lequel s'accumuleront les clients; chaque communication est représentée par un client qui chemine entre les ressources au gré des diérentes étapes du script. A ce stade, c'est la question de
l'ordonnancement des tâches présentes devant
les processeurs qui va nous occuper.
3.1.2
Caractéristiques des tâches
L'examen de l'exemple précédent met en valeur les caractéristiques du fonctionnement des systèmes informatiques temps-réel. Plusieurs "usagers" sont actifs simultanément - même si un seul reçoit à un instant le service du processeur. Il y a ainsi meilleure utilisation du temps processeur (celui-ci pouvant se consacrer à d'autres tâches). On parle de systèmes
multiprogrammés.
Plusieurs tâches sont généralement en attente devant chaque serveur (processeurs, disques, etc). Plutôt que de laisser le hasard seul décider de l'ordre des services, on préfère dénir des mécanismes d'ordonnancement ce chapitre y est consacré. Notamment, on utilisera des
mécanismes d'interruptions, pour accé-
lérer la réponse de périphériques lents ou saisir des événements fugaces, du
polling, pour partager équitablement la puissance, etc.
Remarque: La mémoire rapide est partagée entre les usagers actifs. On mémoire paginée. Le plus souvent, les données utilisées
introduit la notion de
34
Mécanismes de partage de ressources
occupent des positions proches les unes des autres, et la lecture d'un élément de donnée se fait en mémoire centrale. Plus rarement, il faut aller lire sur disque un bloc de données. La fréquence de ces
défauts de pages
augmente quand la
mémoire allouée diminue. Ce point limite le nombre d'usagers simultanés (degré de multiprogrammation).
3.2
Les mécanismes d'ordonnancement
Considérons la le d'attente simple (M/G/1, si on veut). A la n d'un service, comment le serveur choisit-il son prochain client? Les possibilités qu'on décrit s'appliquent à un "vrai" système à le et serveur, aussi bien qu'à un modèle conceptuel de fonctionnement complexe. Description des disciplines habituellement répertoriées: FIFO ("First-In, First-Out") c'est à dire "premier entré, premier servi" le mécanisme habituellement considéré, qu'on a toujours supposé jusqu'ici. LIFO ("Last-In, First-Out"): le dernier arrivé sera servi le premier. Intérêt: diminue l'eet pervers des impatiences pendant le service, cf. ESS4; utilisé aussi en "gestion des stocks" (même motif: eet du vieillissement); au hasard: cas où on ne peut garder trace de l'ordre d'arrivée; Round Robin: on dénit un "quantum de temps de service"; le serveur traite à tour de rôle chaque client pour une portion du temps égale au quantum; il accomplit ainsi une sorte de cycle sur les clients en attente. Dès qu'un client a reçu, en plusieurs fois, le service qu'il réclame, il quitte le serveur; Processor Sharing (PS): version asymptotique du "round robin": le quantum tend vers 0; si
n clients sont présents entre t et t + t, chacun d'eux t=n pendant ce temps (avec t ! 0).
reçoit un service élémentaire égal à
Ces mécanismes ordonnancent les choix sans discrimination; pour les suivants, on attache à chaque client une
classe, et le choix s'appuie sur cette classe. C'est
une véritable discrimination, qui permet de tirer parti des caractéristiques des clients. priorité simple HOL ("Head of the Line") les clients de classe 1 viennent se ranger en le devant ceux de classe 2 (extension immédiate à N classes); moyen usuel de favoriser un ux; Serveur Cyclique ("Polling"): dans ce mécanisme, chaque classe se voit allouer une le particulière, que le serveur explore de façon cyclique; Tout autre algorithme peut être imaginé. Par exemple, choix basé sur le temps de service demandé (les temps courts d'abord). On parle de "classe" pour diérencier les ux: selon leur priorité, selon la
préemptives. Dans ce cas, le client prioritaire interrompt le service en cours pour être distribution des temps de service, etc. On distingue aussi les priorités
servi sans attente. Le client interrompu reprendra son service après celui du
3.3 Notion de Système Conservatif
35
client interrompant. La prise en compte des événements fugaces justie cette particularité (coûteuse en temps de calcul, le plus souvent).
3.3
Notion de Système Conservatif
On conçoit que dans certains cas le choix du client soit indiérent au serveur, c'est à dire que ce choix ne change pas le travail total qu'il devra traiter. Conséquence: à chaque instant, le serveur est capable de comptabiliser la quantité de travail qui lui est oerte (on parle de son "travail restant", "unnished work" en anglais): temps de service restant à fournir au client en cours, augmenté de la somme des services des clients en attente à cet instant. On peut (presque) toujours évaluer cette quantité à un instant xé, mais elle n'a de sens que lorsque le travail restant ne dépend pas de la décision prochaine! Pour donner une autre signication à cette quantité: soit
le travail restant à l'instant
t. Stoppons à
ce moment le processus d'arrivées, et observons le comportement aléatoire du système: le serveur va travailler continûment jusqu'à décisions d'ordonnancement prises.
t + , quelles que soient les
On appelle système conservatif (work conserving) un tel système où le travail restant ne dépend pas de la discipline de choix que pratique le serveur. Contre exemples: système multi-queues avec temps de basculement; système avec impatience; système où le temps de service est fonction de l'attente (vieillissement), etc. Pour la plupart de ces systèmes, on ne peut même pas calculer ce travail à un instant donné. Le lecteur est encouragé à expliciter, dans chacun de ces cas, les raisons rendant le serveur non-conservatif.
Formule de la somme pondérée Il va de soi que, si le travail restant ne dépend pas de l'ordonnancement, le temps d'attente, lui, en dépendra. La propriété de conservation marche "vue du serveur". Pour les clients, on va voir de quoi il retourne.
Remarque préliminaire:
j l'intensité du ux de type le ux total. Il est possible de mesurer le temps d'attente sans tenir compte des classes des clients. Notons W
Une le d'attente reçoit des ux diérents, on note
j
et
Wj
l'attente moyenne qu'il subit. On note
la quantité correspondante. C'est une somme pondéré, la pondération faisant intervenir la proportion de chaque ux:
W
=
X j
Wj
L'importance de la notion de temps moyen pondéré réside dans le fait que peut ne pas savoir mesurer une autre quantité supposons par exemple un processus de mesure incapable de diérencier entre les classes.
Théorème. Imaginons un serveur devant une le d'attente traitée selon un mécanisme de priorité quelconque, conservatif et non préemptif. On a la loi de
36
Mécanismes de partage de ressources
conservation suivante:
X
i Wi =
1
W
0
= Cste
(3.1)
L'indice i court sur les classes de clients; i représente la charge de la classe P i: i = i E (s)i , Wi le temps moyen d'attente qu'elle subit; = i la charge totale; et W désigne la moyenne du temps de service restant (la preuve de cette 0
formule est donnée en annexe à ce chapitre):
=
W
0
X E (si ) X E (si ) = i
2
2
2
i
i
i
2E (si )
(3.2)
La formule signie que l'expression ne dépend pas de la discipline; bien noter que la somme des temps d'attente est pondérée par les pour
. W
Exemples: Cas particuliers
P
Rappel: loi exponentielle: constante:
W
0
=
E (s
2
i Esi =2;
i et non par les i comme
) = 2E (s) , d'où W = P i Esi; durée 2
0
Supposons une seule classe de clients (pas de priorité, un seul indice Dans ces conditions,
W
0
i).
prend la forme
= 2EE(s(s)) 2
W
0
On a alors, puisque il n'y a plus qu'un seul temps moyen d'attente, qu'on note simplement
W
=
1
W
W:
0 , soit
W
E (s) = 2(1 E (s ) ) (E (s)) 2
2
(l'introduction du dernier terme est justiée par le fait qu'il est sans dimension, il vaut 1 pour un temps constant et 2 pour une exponentielle). C'est la très célèbre formule de
Pollaczek-Khinchine
(PK).
Supposons 2 ux, de temps de service diérents, mais sans priorité. Leur temps d'attente est identique. D'où
W
1
=W = 1 1 2
X E (si ) i
2
2
on a dans ce cas une généralisation élémentaire de la formule PK. Supposons une priorité, mais des
temps moyens identiques. La formule se
réécrit, en faisant sortir le temps de service moyen, de telle façon que le temps moyen pondéré y apparaît:
W (à vérier).
=
X i
Wi =
X i E (si ) 1 2E (si ) 2
3.4 La discipline HOL
37
Preuve de la loi de conservation: on observe le système, à t on trouve n(j ) clients de classe j (=1,...P); le client en cours de service réclame encore
x0 . Le travail restant est donc:
XX n(j )
U (t) = x0 + On a noté
xi;j
i=1
j
xi;j le temps demandé par le client i de la classe j . En prenant
la moyenne,
E (U ) = W0 +
X X E[
j
xi;j ]
i
la moyenne restant est le nombre moyen de clients de classe
j
fois le
temps moyen de service. Grâce à Little, on peut relier le nombre moyen au temps d'attente, et donc:
E (U ) = W0 +
X
j Wj
j
Maintenant, le travail restant est indépendant du mécanisme d'ordonnancement (système conservatif ). On prend la valeur pour FIFO: dans ce cas, tous les
Wj
sont égaux et
E (U ) = W0 =(1
)
Priorité entre clients identiques On suppose maintenant des clients aux caractéristiques identiques: même distribution du temps d'attente (non plus seulement même moyenne). Quel que soit le mécanisme de choix, pourvu que le système soit conservatif, le choix du serveur n'a pas d'inuence sur l'occupation totale de la le; en d'autres termes,
la distribution du nombre total de clients en le ne dépend pas de la discipline.
En particulier, le nombre moyen de clients est indépendant de la discipline. Donc (Little) le temps moyen d'attente ne dépend pas de la discipline (mais la distribution de l'attente en dépend !). Remarque: vérier que ce résultat est bien en accord avec la relation de conservation (1). Exemple: FIFO, LIFO, Hasard donnent le même temps moyen d'attente.
3.4
La discipline HOL
Dans toute la suite, "priorité 1" plus forte que "priorité 2". On reprend le cas général (services diérents), serveur de type conservatif, N classes. On note
k
la somme des charges des classes 1 à
la classe 1 est prioritaire sur 2, ...,
N
k
(inclus); rappelons que
1 est prioritaire sur N . k est la charge
que "voit" la classe k (qui double k+1, k+2,.. et ne les voit pas). Remarque: la classe 1 voit quand même la classe 2, en eet un client 2 peut géner un client 1
38
Mécanismes de partage de ressources
qui arrive pendant son service. On montre que:
Wk =
W k )(1 k 0
(1
avec où
W
0
k =
k X i=1
)
1
(3.3)
i
a la même expression que plus haut. Exemple: 2 classes. Vérier que
la loi de conservation est encore valide. (Discussion: caractère sécurisant de la discipline pour la classe 1, même si
+
1
2
> 1).
Preuve: pour une discipline non préemptive,
Wj
=
W0 +
X
Esi (N ij + M ij )
i 1). Remarque: tous les systèmes sont à capacité limitée. On parle
de système à capacité limitée lorsque celle-ci fait sentir son eet pendant le
service nominal. La capacité limitée devient un problème lorsqu'elle est partagée
S1
entre ux distincts. La Figure 4.1 en donne une illustration:
1
2
N1
-
N2
Fig. 4.1
A A AA
S2
S3
-
N3
-
-
Propagation au ux 2 d'une surcharge du ux 1
A l'entrée, il y a rejet dès que les les 1 ou 2 sont pleines. Il y a blocage des serveurs S1 et S2 si la le 3 est pleine (obligatoire). On voit alors que si
1
augmente, le ux 2 va aussi être perturbé. La solution la plus simple consistera à scinder N3 en 2 parties réservées. Mais on a vu l'intérêt de partager. Une autre solution sera de partager une partie du tampon, et d'en privatiser une autre. Une règle de partage très performante a
4.2 Comportement des sources
pu être proposée:
1
47
on n'autorise pas plus de
p
N= L clients de chaque ux (ici,
N joue le rôle de N3 et L est le nombre de ux partageant la ressource). Le même mécanisme se rencontrera chaque fois que deux ux aux caractéristiques diérentes se mélangeront. Le problème de multiplexage statistique dans les réseaux haut-débit est une forme de ce phénomène.
4.1.1
L'Importance du Phénomène
C'est dans cet eet que réside la source des engorgements du trac routier - qu'on peut comparer au
deadlock
des systèmes distribués informatiques: ces
congurations s'observent aussi dans les systèmes informatiques. A noter qu'on observe de tels blocages même en l'absence de surcharge avérée, par le simple jeu des uctuations statistiques. Dans le cas du trac routier, le comportement des usagers perturbe naturellement le phénomène observé. Dans les réseaux de type téléinformatique le phénomène est le même, quoique plus simple à observer. Imaginons deux ux, le premier allant du noeud A au noeud B, le second de P au noeud Q; ces deux ux transitent par le même noeud C. Si le 1er ux sature, par congestion en B par exemple, alors C va engorger et le ux de P à Q va être perturbé, voire bloqué.
AH
HH j H * P
Fig. 4.2
4.2
C Æ
*
B
HH j
Q
HH
Interblocage par mélange des ux
Comportement des sources
Le comportement des sources se caractérise par 2 phénomènes, également importants: abandon prématuré (impatience ou temporisation) lorsque le temps de réponse s'allonge; conséquence: le serveur peut être en train de traiter le client qui abandonne, d'où un travail perdu; répétition de la demande; conséquence: le trac oert mesuré se trouve faussé, la même demande étant enregistrée plusieurs fois. On caractérise le phénomène par les paramètres suivants:
Tentative: tout client qui se présente devant le service constitue une tentative, qui est un 1er essai ou un renouvellement. On notera demandes (tentatives fraîches), et 1. M. Irland,
le ux total observé.
0
le ux de 1ères
Buer Management in a Packet Switch, IEEE Transactions on Communica-
tions, Mars 1978.
48
La Congestion: les phénomènes
= =
Coecient de répétition: c'est le rapport
0,
qui mesure l'ampli-
cation provoquée par l'encombrement; il permet de relier la demande réelle à l'observation.
Taux de persévérance: dans un modèle très simple, on tient compte du comportement de persévérance de la demande de façon probabiliste: soit
H
la
probabilité qu'une tentative qui échoue se représente une nouvelle fois (Ra-
H
nement: prendre
fonction du rang de la tentative, de la nature des échecs,
etc).
Taux de perte: on note
p la probabilité de rejet (ou abandon); en réalité,
le taux d'échec est diérent selon le rang de la tentative et l'intervalle de temps entre tentatives.
r = 1 p est le taux d'ecacité.
Il faut bien réaliser qu'on ne peut pas, la plupart du temps, percevoir les quantités originelles, telles que Essayer d'imaginer des
0.
Il est même le plus souvent dicile et très
coûteux de séparer dans une campagne de mesure
0
de
.
protocoles de mesure pour les exemples de ce chapitre
4.2.1
Un modèle de répétition
0
-+ 6
-
Système"
ec
Rejets ? HH Attente HHH
Fig. 4.3
On notera
ec
4.2.2
Clients traités Normalement
- Abandon
Modèle du phénomène des répétitions
le débit écoulé. I vient:
ec soit encore:
-
=
1
0
Hp
= (1 p) = + Hp 0
ec =
0
1
(1
p) Hp
(4.1)
Un exemple de conséquence
Supposons que le système soit une le M/M/1/N. On injecte une charge
0 , inconnue. La procédure de mesure fournit
. Voici un échantillon de résultats N = 4, et supposé
(on suppose que le ux total résultant reste Poisson); on a fait un taux de persévérance
H = 0:9:
= 0:7, on mesure = 0:78 - p = 0:115 (la M/M/1/4 aurait p = 0:086); pour = 0:9, on mesure = 1:20 - p = 0:28 (la M/M/1/4 aurait p = 0:16);
pour
0
0
4.2 Comportement des sources
pour
0 =1.2,
on mesure
49
= 3:07 - p = 0:67 (la M/M/1/4 aurait p = 0:28).
On imagine aisément les fausses interprétations qui en découlent: ou bien une mesure de trac sous-estime le rejet, ou bien une mesure du rejet réel fait surestimer
0.
Remarque Peut-on mettre le système en équations ? Voici une méthode approchée, qui consiste à supposer que le ux résultant des rebouclages conserve son caractère poissonnien ce qui est faux, en toute rigueur. On écrira une équation reliant (
et p (c'est à dire , p à : 0
p, et
et
on estimera
p par le rejet d'une
reliant
=
1
et
0
Hp
p
N (1 ) 1 N +1
donné, on prend une valeur initiale = , = g(), puis une nouvelle valeur de charge par
La résolution est itérative: pour on en déduit la perte par
p=
M/M/1/N,
0
0
= f (p), et ainsi de suite jusqu'à convergence (précision de 1/1000 en quelques itérations). L'ensemble des résultats est présenté sur le graphe suivant: (a) Trac écoule et perte
(b) Trac reellement observe
1
5 Trafic Ecoule
0.8
4
0.6
3
Trafic observe Perte 0.4
2
0.2
1
0
0 0
0.2
0.4 0.6 0.8 1 Trafic Offert Frais Fig. 4.4
0
1.2
1.4
0
0.2
0.4 0.6 0.8 1 Trafic Offert Frais
Observation des temps d'attente 6
(p)
Æ
-
e
1.2
1.4
50
La Congestion: les phénomènes
1 Trafic Ecoule 0.8
0.6 Perte 0.4 Trafic observe 0.2
0 0
0.2
0.4
0.6 0.8 Trafic Offert Frais
1
1.2
1.4
Comportement en surcharge d'une le M/M/1/N. N = 4;H = 0:9. A gauche, échelles de la perte et du trac écoulé; à droite, trac oert observé. Fig. 4.5
4.3
Variation des temps de service
Ce qui est génant c'est que ce temps va croître. Les phénomènes physiques qui provoquent cette variation sont à chaque fois spéciques du système étudié. On en donne qq exemples.
4.3.1
Nécessité d'un Contrôle de Congestion dans un réseau
On observe un réseau de transmission de données, ou plutôt une liaison de bout en bout de ce réseau (Figure 4.6). Quand un noeud est saturé (le troisième par exemple), le serveur qui le précède se trouve, par là même, bloqué. En fait, le mécanisme exact est plus complexe: S2 va traiter et émettre le paquet (le niveau 2 va en faire une trame...); arrivé devant le tampon plein, le paquet est rejeté (que faire d'autre), même si le niveau 2 est OK. S2, qui ne reçoit pas l'acquittement attendu, doit réémettre une, deux, trois... fois: tout se passe comme si le paquet attendait en S2. Si on note
B
la probabilité de rejet (on suppose la liaison homogène,
chaque étage), et qu'on suppose que chaque tentative a le même
B
scabreuse), alors il y a: une émission, soit 1 temps de service, avec probabilité
1
B
B
à
(hypothèse
4.3 Variation des temps de service
51
S1
Fig. 4.6
S2
S3
Une liaison de bout en bout, dans un réseau de données
deux émissions, soit 2 temps de service, avec probabilité trois émissions, soit 3 temps de service, avec probabilité soit en n de compte en moyenne
1=(1
un temps moyen de service équivalent
avec le rejet. Côté entrée, on note
B (1 B ) B (1 B ), etc 2
B ) émissions, ce qui revient à prendre E (s)=(1 B ): le temps de service croît
le taux d'arrivée (identique à chaque étage par sy-
métrie). La charge oerte est
(avec le modèle de serveur équivalent, le paquet
attend dans un noeud jusqu'à en sortir victorieusement, il n'y a pas de perte). On fait un modèle M/M/1/N du noeud (c'est vraiment très approché). D'où:
B=
aN (1 a) 1 aN +1
avec
a=
E (s) 1 B
Les équations sont tout-à-fait analogues à celles du modèle précédent dans lequel on ferait H=1, quoique l'interprétation en soit diérente. Pour un modèle plus réaliste, il faut rajouter l'abandon, et sûrement raner le modèle de perte. La résolution numérique, et le résultat, seraient comparables à la courbe du 6.2.
4.3.2
Un commutateur
Les demandes des usagers sont détectées par un explorateur qui place une requête dans la le du processeur principal. Celui-ci traite en permanence un certain nombre de tâches en concurrence (admission de nouvelles tâches, E/S, avancement de tâches en cours). L'ordonnancement des tâches est le plus souvent complexe (mélange d'interruptions, de scheduling cyclique, de tranches de temps périodiques, etc). Le mécanisme d'admission doit examiner les requêtes, pour distinguer les appels prioritaires, puis rejeter les appels qu'il ne peut traiter faute de ressource (de temps). Un appel rejeté n'est jamais éjecté": il vaudrait mieux le dire ignoré. On note:
Loff le nombre d'appels nouveaux arrivant par seconde, Lec le nombre d'appels traités avec succès par seconde, Lrej le nombre d'appels traités puis rejetés, Ltot le nombre total d'appels présentés (/seconde),
52
La Congestion: les phénomènes
s le temps pour servir un appel en entier, le temps pour examiner puis rejeter un appel malheureux (on supposera < s), la charge à vide (travail de fond du processeur) 0
A noter, les appels rejetés ne disparaissent pas, on les détecte à nouveau au cycle suivant; il y a répétition, et de temps en temps abandon, selon le schéma déjà exposé.
Loff
Ainsi, la commande va devoir traiter non pas Loff , mais
= Ltot demandes.
Tant que l'écoulement du trac est uide, on a:
0
+ sLec 1 Lec = Loff
Mais en surcharge,
= = 1 =
Ltot Ltot
Lrej + Lec Loff + H:Lrej + sLec + Lrej 0
La première relation exprime la conservation des appels (ils sont soit traités, soit rejetés), la seconde est, encore une fois, la caractéristique du rebouclage de répétition; la dernière relation exprime que, en surcharge, le processeur travaille 100% de son temps. De ces relation, on élimine
Lec =
(1
Lrej
et
Ltot , et:
H )(1 ) Loff s(1 H ) 0
ce qui montre que dans cette zone, le trac écoulé décroit quand le trac oert augmente... Pour la valeur-charnière
Loff
= (1
)=s, on vérie que le segment 0
montant du régime uide se raccorde au segment descendant. Remarquer aussi
que la pente du segment descendant dépend en premier lieu de la valeur de
H,
et que lorsque
H
! 1, le segment devient vertical. L'interprétation de ces
variations est laissée au lecteur.
Le phénomène, inévitable, résulte de ce qu'on doit dépenser de l'énergie sur les clients qu'on ne saura traiter. Selon le système étudié, la cause intime du phénomène pourra varier, mais elle se traduira par une mise en équation analogue. Noter que les équations aboutissent à un modèle linéaire, évidemment simplié.
4.4
Moralité
On a montré tous les méfaits possibles des phénomènes d'engorgement et de surcharge. Des remèdes sont possibles, qui ont noms procédures de contrôle de congestion, régulation de charge, etc. La conception et l'étude de telles procédures demande tout d'abord que le phénomène cause soit compris. On a
4.4 Moralité
donné les principes: pour chaque application il faudra chercher les mécanismes particuliers dans lesquels ces principes s'incarnent. Retenons de ce chapitre la conclusion suivante:
Lorsque l'intensité du trac augmente - dès que les sources sont en état de percevoir l'existence d'une attente - des phénomènes parasites apparaîssent, liés aux comportements individuels (temporisation, impatience, répétitions), qui peuvent entraîner le système dans des zones de fonctionnement instables. Il faut évidemment incorporer ces comportements au modèle pour rendre compte de façon réaliste des phénomènes observés.
Reste à étudier les mécanismes de contrôle. Mais ça, c'est une autre histoire...
Repères bibliographiques L'étude des phénomènes de surcharge dans les commutateurs téléphoniques est reprise de la référence [Hebu 85]. D'autres formes de tels phénomènes s'observent dans tous les systèmes. Par exemple, le mauvais contrôle du degré de multiprogrammation provoque un écroulement des performances des systèmes informatiques [Gel 82, Lav 83]. L'analyse de ces phénomènes de surcharge est assez tolérante: il faut trouver des modèles qualitatifs de fonctionnement, observer l'allure du phénomène, plus que des quantications précises.
53
54
La Congestion: les phénomènes
Chapitre 5
Mécanismes de contrôle de congestion Sommaire 5.1
Contrôle dans un système centralisé . . . . . . . .
56
5.2
Les Réseaux Store-and-Forward
59
5.3 5.4
. . . . . . . . .
5.2.1
Contrôle de ux, contrôle de congestion
. . . . . . .
59
5.2.2
Les mécanismes de base . . . . . . . . . . . . . . . .
59
L'allocation de crédits . . . . . . . . . . . . . . . . .
59
5.2.3
Les crédits, mécanisme implicite de régulation . . . .
60
5.2.4
Le mécanisme de fenêtre Frame Relay
. . . . . . . .
61
5.2.5
Priorités à l'accès . . . . . . . . . . . . . . . . . . . .
61
5.2.6
Mécanismes de notication
62
5.2.7
Additive Increase, Multiplicative Decrease . . . . .
. . . . . . . . . . . . . .
63
Un exemple de contrôle traditionnel . . . . . . . .
63
Le contrôle de congestion du protocole TCP . . .
63
5.4.1
Fonctionnement de la procédure
. . . . . . . . . . .
64
. . . . . . . . . . . . . . . . . .
65
La phase Congestion avoidance . . . . . . . . . . . .
65
Comment régler la temporisation ?
67
La phase Slow Start 5.4.2
55
. . . . . . . . . .
56
Mécanismes de contrôle de congestion
P
uisque la surcharge provient d'une augmentation inconsidérée du
trac oert au réseau, les mécanismes de contrôle vont avoir comme tâche
de mesurer et de limiter ce trac. Une autre contrainte qu'on leur impose est d'accomplir cette limitation de la manière la plus rentable, c'est à dire de permettre au réseau de fonctionner au plus près de sa capacité maximale. Enn, la contrainte
d'équité
est aussi invoquée. Si le réseau se trouve en
situation de pénurie, celle-ci doit être partagée équitablement entre les sources. Si une source voit son trac augmenter, il ne faut pas qu'elle puisse écraser les autres sources, même si, vu du réseau, l'écroulement typique de la congestion ne se manifeste pas. La diculté du contrôle provient en majeure partie du
caractère distribué des
sources de trac: trac émanant de sources non coordonnées, absence d'organe de contrôle central qui régulerait en fonction de l'état global du réseau.
5.1
Contrôle dans un système centralisé
Nous allons décrire très sommairement l'approche mise en ÷uvre pour la régulation de charge dans une machine de type centralisée c'est à dire dans le cas le plus favorable où l'organe de commande peut avoir une vue
instantanée de l'état des ressources.
exhaustive et
On peut se représenter le système temps-réel comme un réseau de les d'attentes, avec probablement des mécanismes d'ordonnancement complexes (voir [Kle 76], volume 2). Quoiqu'il en soit, il existera, compte tenu du prol de trac traité, une ressource plus chargée. C'est cette ressource qui va saturer en premier, quand la charge va augmenter, et c'est donc elle qu'il faut surveiller. En réalité, les prols du trac ne sont pas immuables, et par conséquent la ressource la plus chargée pourra varier, et la surveillance sera le plus souvent multiple. Imaginons pour simplier que la ressource fragile est unique, et qu'il s'agit d'un processeur central (c'est un cas assez fréquent). Le principe du contrôle est fort simple: mesure de la charge de la ressource, c'est à dire de son taux d'occupation. Par exemple, on mesurera le temps passé par le processeur au traitement des tâches de priorité les plus faibles. La mesure se fait cycliquement;
T , par exemple 10 secondes; selon la valeur du I dans le cycle, le processeur sera décrété plus ou moins chargé. La charge sera estimée par 1 I=T . En fonction du niveau détecté, les on dénit un intervalle de mesure temps total d'inactivité
actions de correction ou de prévention seront lancées.
Remarque: C'est la charge du processeur, qu'on va mesurer, et non le taux des arrivées. Pourquoi ? Simplement, parce que dans un système à le d'attente,
= =) est le principal paramètre. Rappelons aussi qu'en situation le temps de service n'est pas constant. La prudence commande donc d'observer et non . la charge (
de surcharge,
5.1 Contrôle dans un système centralisé
57
Le processus de mesure Sous cette description simpliste se cachent de redoutables pièges, qui vont conduire à complexier le schéma. En premier lieu, la mesure est entachée d'incertitude parce que les processus d'arrivée des requêtes et des services sont aléatoires. Si j'observe 2, 3 ou 4 secondes à plusieurs reprises, à l'état stationnaire, je ne retirerai pas la même information. Il faut tenir compte de l'imprécision inhérente au procédé de mesure. Pour illustrer le dilemme du processus de mesure, supposons une charge de 80 %, un processeur fonctionnant comme un système M/M/1, avec une durée moyenne de service de 30 ms. Le cycle de mesure opère en comptant le temps d'inactivité sur 1 seconde, puis sur 3 ou 10 secondes. La moyenne de ce temps est de 0.2 seconde. Voici la statistique des observations réalisées (Figure 5.1). Comme on le remarque, une valeur de cycle de 1 s conduit à surestimer la charge, dans 35 cas sur 100 elle sera estimée supérieure à 90%; mais dans 20 cas sur 100 elle sera perçue comme inférieure à 65%. On corrigera ce défaut en allongeant le cycle de mesure. Un cycle de 10 secondes donne une valeur supérieure à 0.9 pour 5% des mesures seulement. Mais, en même temps, l'allongement de la durée du cycle ne règle pas la question. Ou plutôt, il introduit un autre défaut, celui de l'allongement du temps de réaction. Dans notre exemple, il faut 10 secondes avant de détecter de façon sûre une surcharge, temps pendant lequel elle pourra se propager et s'amplier. C'est dire que le choix des paramètres d'un tel dispositif requiert un compromis obtenu après des réglages assez minutieux.
Les actions de défense Quelle action entreprendre, une fois la surcharge détectée ? Le plus souvent, la surveillance réagira progressivement, selon le franchissement de paliers dans la charge. Par exemple, un premier palier sera déni pour une charge de 80 %, un deuxième pour 85 %, etc. A chaque palier sera attachée une action d'ecacité (et de gravité) grandissante. Les systèmes temps-réel sont assez souvent dotés de mécanismes d'autoserveillance (exploration et test cyclique des éléments actifs). Ce test consomme une partie de la ressource. La première action consistera à désactiver ces tests (dont le système peut évidemment se passer, pourvu qu'ils soient rétablis en régime moins chargé). Les actions suivantes amèneront inévitablement à refuser l'accès du système à de nouvelles requêtes. Le plus souvent, on pourra établir une hiérarchie dans les rejets. Ainsi, dans un commutateur du réseau téléphonique on restreint d'abord l'accès des appels au départ (an de favoriser les appels arrivants, qui ont eux déjà consommé une partie des ressources du réseau). Une faiblesse de ce type d'action se trouvera dans les contraintes posées par l'organisation du système, par exemple la nécessité de détecter et d'analyser une demande avant de pouvoir statuer sur son sort: le traitement des requêtes conduit à un gaspillage inévitable de la ressource (cf. à ce sujet le modèle esquissé
Voir à ce sujet un exercice en n de Section
58
Mécanismes de contrôle de congestion
1
0.8
Distribution
0.6
0.4
Intervalle de mesure = 0.2 1s
3s
10s
0 0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Charge estimee
Fig. 5.1
Distribution des temps d'inactivité observés
au chapitre précédent).
1
5.2 Les Réseaux Store-and-Forward
5.2
59
Les Réseaux Store-and-Forward
Les réseaux de paquets actuels (Internet, Transpac, par exemple) utilisent un mode de travail dit Store-and-Forward. Cela signie que l'information (structurée en paquets) est transmise de proche en proche, de n÷ud en n÷ud, depuis l'origine jusqu'à la destination. A l'heure actuelle, la majorité des réseaux que l'on rencontre s'appuie sur le protocole IP. Les
routeurs traitent les paquets IP et
les aiguillent au travers des sous-réseaux (qui déroulent les couches 1 et 2). Selon la technologie mise en ÷uvre (Ethernet, Frame Relay, ATM, etc.), ces couches basses sont dotées de fonctionnalités plus ou moins élaborées, leur permettant de participer au mécanisme de gestion de congestion. Dans la suite, nous supposerons essentiellement que nous nous trouvons dans le cas traditionnel de TCP (protocole du niveau transport) tournant sur IP (niveau réseau).
5.2.1
Contrôle de ux, contrôle de congestion
Le contrôle de ux vise à asservir le débit de la source à celui du récepteur. C'est une fonction de bout-en-bout. C'est, aussi, une fonction de contrôle de congestion. C'est à dire qu'une mauvaise régulation du ux émis va provoquer une congestion sur le chemin de la connexion: si la source émet plus vite que le récepteur ne reçoit, les paquets vont s'accumuler dans le réseau, d'abord dans le n÷ud de sortie, puis dans le précédent, etc.
Remarque: La terminologie n'est pas du tout xée. C'est que, en réalité, les deux contrôles font appel à des outils assez semblables. En toute rigueur, le terme de
contrôle de ux
désigne les mécanismes par lesquels le récepteur
régule le ux de l'émetteur, alors que le
contrôle de congestion
fait référence
aux actions du réseau sur la source. La distinction contrôle de ux / contrôle de congestion est souvent omise. Voir par exemple la plupart des articles d'un numéro spécial classique IEEE Transactions on Communications, avril 1981.
5.2.2
Les mécanismes de base
Pour construire un schéma de contrôle de congestion, les réseaux vont faire appel à un certain nombre de mécanismes élémentaires toujours les mêmes, en fait.
L'allocation de crédits Un mécanisme simple est celui du se voit allouer un certain nombre
W
crédit (on parle aussi de jeton). La source de crédits. Elle peut émettre un paquet à
condition d'avoir un crédit (et le paquet consomme le crédit correspondant). Le récepteur acquitte les paquets reçus (et traités). L'accusé de réception régénère les crédits de l'émetteur, l'autorisant ainsi à poursuivre. L'émetteur numérote les paquets qu'il envoie. A l'instant
t, les paquets n
2;n 1;n ont été acquittés. Il peut envoyer le numéro n +1, mais aussi anticiper en envoyant n +2;:::;n + W . On décrit souvent ce mécanisme du nom de fenêtre,
60
Mécanismes de contrôle de congestion
mais il y a risque de confusion avec la vraie fenêtre dont nous parlons au paragraphe suivant. Le mécanisme de crédits a d'autres usages. Par exemple, la correction d'erreur par retransmission utilise un tel schéma (procédure dite
Go-back N,
par
exemple). Comme on verra dans la suite, un usage ecace conduit à varier le nombre des crédits alloués en fonction de la charge du réseau. Construire un modèle plus exact, intégrant les durées d'émission
Notons T le temps de retour d'un acquittement, qui régénère le crédit. C'est round trip time (RTT) qui est de l'ordre de 2 fois le temps de propagation (augmenté des temps d'émission et d'attente). Si la liaison se voit allouer W crédits, cela signie qu'elle émettra W paquets tous les T secondes, c'est à dire que le débit autorisé sera T=W paquets/seconde. Si on note L la longueur moyenne d'un paquet, cela donne L:T=W bits/seconde. le
5.2.3
Les crédits, mécanisme implicite de régulation
Lorsqu'une congestion se produit, quelque part dans le réseau, les paquets voient leur temps de transit s'allonger et aussi les acquittements. Il en résulte que les crédits (jetons) reviennent moins vite à l'émetteur, qui voit ainsi baisser naturellement le débit qu'il est autorisé à émettre. Comment calculer la taille de cette pseudo-fenêtre
W
(W comme win-
dow)? Un modèle classique par réseau de les peut aider. C'est un réseau fermé.
-
Paquets -
Source
-
Récepteur
W Clients
Retour des crédits Fig. 5.2
Modèle à les d'attente du contrôle par crédits
On peut le rendre plus réaliste, au prix d'une complication, en introduisant les ux incidents: dans chaque n÷ud traversé, le ux pisté doit aronter d'autres courants qui occupent les mêmes ressources. De même, chaque n÷ud peut être représenté par un modèle plus complexe. Contentons-nous ici d'un modèle
très
simpliste. Supposons une source sa-
turée (c'est à dire ayant toujours un paquet à émettre). Soit
n
le nombre de
5.2 Les Réseaux Store-and-Forward
61
crédits alloué. Imaginons que la congestion du réseau soit représentable par
. L'augmentation du RTT, résultant de l'attente E (s)=(1 ), avec E (s) = L=C le temps d'émission du
une le M/M/1 de charge supplémentaire, sera
C est le débit de la liaison). Le temps de régénération d'un crédit sera T + E (s)=(1 ). Le débit eectif sera donc:
paquet (
(1 ) Debit = LnLC + CT (1 )
Il diminue donc bien, quand
5.2.4
augmente.
Le mécanisme de fenêtre Frame Relay
Le protocole Frame Relay (FR) a popularisé la notion de
fenêtre glissante
(sliding window). Dans ce schéma, la source ne doit pas envoyer plus d'un nombre donné
n de paquets dans toute fenêtre temporelle de taille T .
Plus précisément, le FR opère sur le volume de trac et non sur le nombre de paquets (si les paquets ont une longueur constante, il n'y a pas de diérence. Travailler sur un volume permet de s'aranchir des tailles variables).
Remarque de terminologie. Après tout, le terme de fenêtre n'appartient à personne. On peut décrire la fenêtre FR comme une
fenêtre temporelle (dans
[t;t + T ], émettre au plus n paquets). Le mécanisme de crédits, quant à lui, utilise une fenêtre d'anticipation (droit d'émettre les paquets dans la fenêtre des rangs [k;k + n]).
tout intervalle
5.2.5
Priorités à l'accès
Un mécanisme, appelé
input-buer limiting
a été proposé, son application
type étant un réseau en anneau. Présentons l'argumentaire, dans un cadre simplié. On supposera un réseau homogène: tous les n÷uds sontidentiques, statistiquement. Le canal de sortie du n÷ud type se présente comme un serveur
N , alimenté par un ux de transit T et un ux de L . Chacun de ces ux subit un rejet dû à la capacité limitée, noté (respectivement) BT et BL . Le ux admis sera donc T = T (1 BT ) et
L = L (1 BL ). Une fraction p du trac est destinée au n÷ud, 1 p est en précédé d'une le de capacité provenance locale
transit. En moyenne, on renvoie autant de paquets qu'on n'en reçoit:
T
Noter que
= (1
p) T
+ L
1=p est le nombre moyen de n÷uds traversés par un paquet avant
d'atteindre sa destination. Les paquets émis par le n÷ud vont peut-être se faire bloquer au n÷ud suivant. Par homogénéité
BT
est aussi la probabilité de ce
, mais (1 BT ). On supposera enn que chaque serveur est assimilable à un système blocage. Cela revient à dire que le débit eectif du serveur est non pas M/M/1/N.
Lorsqu'aucun contrôle n'est institué, le fonctionnement est semblable à la cascade étudiée plus haut. Puisque les ux sont traités indistinctement,
BT
=
'
62
T
T
-
N
&
?
Rejets
Trac Local
L
Fig. 5.3
BL = B .On a :
$
Mécanismes de contrôle de congestion
B=
?
T
-
-
%
Modèle d'un n÷ud en isolation
aN (1 a) 1 aN +1
a=
1
B
Comme plus haut, cette équation donne lieu au phénomène de congestion. Le contrôle consiste à discriminer les paquets selon leur provenance. On instaure un seuil
NL ,
si les paquets locaux atteignent ce seuil on les rejette. Le n÷ud
obéit aux conditions:
0 0 Voir aussi S. Lam, M.
nL NL nL + nT N
(NL < N )
Au terme d'une analyse approchée, on peut montrer qu'un choix judicieux
Congestion du partage supprime le phénomène indésirable d'engorgement. Voir [Sch 87]. Control of Storeand-Forward networks by Input Buer Limit 5.2.6 Mécanismes de notication - an analysis. IEEE Le phénomène d'auto-régulation que constitue le ralentissement du retour Reiser,
Trans. Com., janvier 1979
des jetons permet un fonctionnement satisfaisant en cas de surcharge modérée. Lorsqu'une vraie surcharge s'installe, il faudra des mécanismes plus énergiques. En situation de surcharge, la seule solution est de diminuer le débit des sources. Celles-ci peuvent évidemment détecter la venue d'un engorgement, par exemple en surveillant l'allongement des RTT, ou la survenue de perte de paquets (cf. TCP). Les mécanismes de notication explicite orent au réseau un moyen direct de dialogue. Beaucoup de protocoles ont dans ce but déni un champ spécique dans l'entête du paquet:
Forward Explicit Congestion Notication (FECN) en FR, Explicit Forward Congestion Indicator (EFCI).
tandis que l'ATM parle de
FECN n'est pas, en soi, un mécanisme de régulation. C'est seulement un moyen de déclencher, à la source, un tel mécanisme. La notication explicite est un exemple direct du régime
coopératif qui peut s'instaurer dans un réseau:
le réseau prévient les sources, celles-ci réagissent en modérant leur ux, pour le bien commun.
5.3 Un exemple de contrôle traditionnel
5.2.7
63
Additive Increase, Multiplicative Decrease
Un concept commun à beaucoup de mécanismes de régulation est celui de Additive Increase, Multiplicative Decrease (AIMD). On le rencontre en ATM (mode ABR) et dans le fonctionnement de TCP, entre autres. Lorsque, en raison d'une congestion, une source doit diminuer son trac, elle le fera de façon multiplicative : à chaque opération, elle multipliera son débit d'un facteur
< 1, amenant une décroissance géométrique de celui-ci. A
l'inverse, lorsque les conditions seront uides, l'augmentation sera additive.
5.3
Un exemple de contrôle traditionnel
Le mécanisme de crédits peut fonctionner à merveille. Il sut que la somme des débits eectifs alloués à chacun des ux soit inférieure à la capacité disponible. Malheureusement, cette méthode présente l'inconvénient majeur d'être très coûteuse en bande passante. Supposons que le n÷ud examiné se partage entre 100 circuits virtuels de débits identiques. Il divise sa capacité en 100 parties, et la partage entre les circuits. La variabilité des tracs issus de chaque source va rendre cette solution très défavorisante, la mémoire sera toujours vide, etc (des crédits sont alloués, et gelés, sur des circuits inactifs momentanément). On a donc dû imaginer d'autres méthodes, plus avantageuses. La première idée consiste à gérer les crédits globalement pour tout le réseau (le réseau
N paquets, on crée N crédits, contrôle isarithmique utilise ce principe.
peut accommoder au total les n÷uds). Le
dispersés sur tous
On construit un réseau de les d'attentes représentant le mouvement des jetons. C'est un réseau fermé si le nombre des jetons est xe. Dans le n÷ud de contrôle, on peut mettre en place des mécanismes complexes: génération ou destruction de jetons; accélération ou retard de l'envoi des jetons en fonction de l'état du réseau. Par exemple, on modélisera cette fonction par un taux de service dans le n÷ud de contrôle de la forme
(n).
L'inconvénient de cette méthode réside dans la latence inhérente à l'utilisation du n÷ud de contrôle. Celui-ci opère sur une information ancienne et donc caduque. C'est aussi une solution fragile (la panne du n÷ud de contrôle paralyse le réseau entier) et non
scalable
(le terme de
scalability
est apparu ré-
cemment. Il rend compte de la diculté technologique d'étendre un réseau, ou du coût non linéaire de cette croissance). On se reportera à la référence [Sch 87] pour une description plus complète des algorithmes de ce type.
5.4
Le contrôle de congestion du protocole TCP
Avec le développement irrésistible du mode IP, TCP tend à devenir le protocole universel, au niveau transport, pour les ux de données (et plus généralement les ux à débit contrôlable).
64
Mécanismes de contrôle de congestion
Noeud de contrôle
Noeuds du réseau
Fig. 5.4
Contrôle isarithmique d'un réseau maillé
Le protocole TCP est bâti sur l'idée d'un mécanisme autonome, indépendant du réseau et des fonctions de notication explicite. La source va observer le réseau et son état,
via l'occurrence des pertes de paquets, et aussi en apprendre
l'état et le débit disponible. L'autonomie de TCP a permis d'en développer des versions diérentes, qui peuvent sans encombre coexister dans le même réseau (on les nomme TCP Tahoe, Vegas ou Reno). L'émetteur possède une réserve de crédits. Ceux-ci sont régénérés par le récepteur, selon le mécanisme décrit plus haut. Il faut consommer un crédit pour envoyer un paquet. En réalité, le mécanisme est plus complexe : les crédits sont gérés par octets. Un paquet consomme des crédits selon sa taille. A chaque émission de paquet (on parle de segment pour TCP) l'émetteur arme une temporisation. Le récepteur envoie un acquittement pour chaque bloc reçu. Si l'acquittement arrive trop tard, l'émetteur détecte ou plutôt décrète une perte de paquet.
5.4.1
Fonctionnement de la procédure
A l'ouverture de la session, TCP ne sait rien du réseau et de ses conditions de charge. La phase de démarrage va consister à tester celui-ci, pour estimer la bande passante disponible. Cela se fait au cours de la phase nommée (assez malencontreusement)
slow start.
5.4 Le contrôle de congestion du protocole TCP
La phase Slow Start Au démarrage, la fenêtre d'anticipation a une taille égale à 1. Au cours du slow start, l'émetteur augmente de 1 la taille de fenêtre à chaque acquittement reçu. Puisque l'acquittement régénère le crédit dépensé, la taille passe ainsi à 2 dès le premier acquittement. L'émission de 2 paquets acquittés donne une taille de 4, et ainsi de suite.
CWND = 1
CWND = 2
CWND = 3 CWND = 4
CWND = 5 CWND = 6 CWND = 7 etc. Fig. 5.5
Croissance de la fenêtre d'anticipation, phase slow start
La phase Congestion avoidance On notera que le terme de slow start est quelque peu mal choisi, compte tenu de la forme exponentielle de croissance de la fenêtre d'anticipation! Il est clair que, avec ce type de fonctionnement, il arrivera un moment où la source va saturer la liaison sur laquelle elle transmet (supposant que la source a susamment de trac à envoyer, pour avoir toujours un paquet prêt à transmette). Alors, un paquet nira par être perdu, parce que, quelque part sur le chemin, un tampon sera saturé.
n de deux façons possibles: n arrive à échéance avant le retour
L'émetteur est averti de la perte du paquet La temporisation armée à l'émission de d'un acquittement.
Les paquets qui suivent l'envoi perdu sont bien reçu, et donnent lieu chacun à un acquittement qui acquitte le dernier paquet bien reçu, c'est à dire
n
1.
65
66
Mécanismes de contrôle de congestion
La détection d'une perte de paquet signale à l'émetteur qu'il a atteint la limite de la capacité disponible sur son chemin. L'émetteur mémorise alors la valeur courante de la taille de fenêtre
W . Il fait Wm = W =2, et réinitialise Wm , la procédure
la procédure slow-start. Dès que la fenêtre atteint la valeur
slow-start est arrêtée et l'émetteur augmente la fenêtre d'une unité à chaque RTT (voir ci-après). Schématiquement, la taille de la fenêtre variera selon le rythme suivant (Figure 5.6, si on suppose évidemment que l'émetteur a
toujours
des paquets à
envoyer (qu'il travaille en régime de saturation):
Fenêtre Perte
W*
Perte slow start
W*
Congestion avoidance
Wm Wm
t 1
Fig. 5.6
Croissance de la fenêtre d'anticipation, phase congestion avoidance
On peut trouver des inconvénients à cette procédure, basée sur la recherche systématique de débordement des tampons. Il n'empêche qu'elle est très astucieuse: l'émetteur s'adapte aux conditions instantanées du réseau, sans dialogue spécique avec celui-ci. Au cours d'une session, si les capacités changent, TCP s'adaptera automatiquement, ce qui en fait une procédure très robuste.
Remarque 1. On a décrit le mécanisme avec des paquets et des crédits unitaires. Rappelons que TCP traite des segments, et que les crédits sont exprimés en octets.
Remarque 2. Ceci décrit la version de base. On peut songer à des mécanismes plus sophistiqués (par exemple, ne pas repartir à 1 pour la phase de congestion avoidance. De telles méthodes ont été implantées (elles diérencient entre les méthodes de détection de la perte).
Remarque 3. La description réelle de la procédure est plus complexe. En eet, elle remplit aussi le rôle de contrôle de ux de bout-en-bout. La gestion de la taille de fenêtre dépend donc aussi des conditions du récepteur.
5.4 Le contrôle de congestion du protocole TCP
5.4.2
Comment régler la temporisation ?
On peut envoyer un paquet, et mesurer le temps de retour de l'acquittement. Problème : ce temps est certainement variable. Il faut donc avoir une estimation de sa moyenne, et pouvoir tenir compte de sa variabilité. Par exemple, on
k paquets envoyés, la moyenne: RT T (1) + + RT T (k) ART T (k) = k
estimera, au bout de
Pas simple à estimer : il faut garder en mémoire toutes les valeurs précédentes ! Heureusement, on sait remplacer cette estimation par une autre, équivalente mais plus maniable :
ART T (k + 1) =
k RT T (k + 1 ART T (k) + k+1 k+1
L'inconvénient de cette approche est qu'elle garde la mémoire de tout le passé du processus, alors même que les conditions de trac changent inévitablement. Il vaudrait mieux, pour tenir compte de cette non stationnarité, opérer sur un horizon du passé limité. D'où l'estimateur (proposé dans RFC 973), qui reprend le principe classique:
SRT T (k + 1) = SRT T (k) + (1 )RT T (k + 1) Il faut choisir les bonnes valeurs pour . Les valeurs préconisées : de l'ordre de
0.8 ou 0.9. A partir de cette mesure, on peut régler la valeur de la temporisation. Par exemple, 2 fois ce temps estimé. Comment améliorer la prise en compte de la variabilité ? La temporisation doit tenir compte de la variabilité réelle des temps de retour. Prendre une valeur de 2 est trop simpliste. Il faudrait pouvoir calculer la distribution, ou tout au moins la variance du temps. Calculer une variance est encore plus coûteux que calculer une moyenne. Même problème de prise en compte de la non stationnarité. Plutôt que de travailler sur la variance, on préfère travailler sur l'écart
j RT T SRT T j, plus facile à estimer. On dénit donc l'erreur par rapport à l'estimation courante :
Err(k + 1) = RT T (k + 1) SRT T (k)
et on dénit la déviation (Sdev, déviation standard) :
SDEV (k + 1) = (1 h)SDEV (k) + h j Err(k + 1) j
Valeur à partir de laquelle on règle la temporisation :
RT O(k + 1) = SRT T (k + 1) + fDEV (k + 1) Les valeurs préconisées sont ici = 0:875;h = 0:25;f = 4.
Il faut noter que tout ceci est empirique, et résulte d'un compromis entre
la prise en compte des conditions variables de la charge dans le réseau et la complexité du calcul. Il faut toujours garder en mémoire que ces calculs se font en temps réel dans le réseau. Le processus émetteur a un certain nombre de tâches à accomplir, et ne peut multiplier à l'inni les calculs et les mises en mémoire de données.
67
68
Mécanismes de contrôle de congestion
Repères bibliographiques Sur le sujet d'actualité de ce chapitre, il faut consulter les revues pour avoir
IEEE Transactions on Communications, IEEE Journal of Selected Areas in Communications (JSAC) [par exemple, le numéro spécial: évaluation des performances des une présentation à jour des solutions et des tendances. Notamment,
réseaux large bande, Avril 1991). Les descriptions exactes des versions des protocoles TCP sont données dans les RFC (Requests for Comments) que publie l'IETF. Ils sont accessibles en ligne (http://www.rfc-editor.org/rfc.html), et souvent assez bien lisibles. (e.g. Ce texte date de 1982 ! Voir aussi RFC 2001, Janvier 1997
RFC 813, Window and Acknowledgment Strategy in TCP) Bibliographie
BIBLIOGRAPHIE
69
Bibliographie [Bay 00]
Bruno Baynat:
Théorie des les d'attente.
Hermes, collection ré-
seaux et télécommunications, 2000. [Cin 75]
Ehran Cinlar:
Introduction to Stochastic Processes. Prentice Hall,
1975. [Fel 71]
William Feller: An Introduction to Probability Theory and its Applications. John Wiley and Sons, 1971.
[Gel 82]
Erol Gelenbe, Guy Pujolle:
Introduction aux réseaux de les d'at-
[Gros 85]
Donald Gross, Carl Harris:
Fundamentals of Queueing Theory.
tentes. Eyrolles, 1982.
2nd Edition. ISBN 0-471-89067-7.John Wiley and Sons, 1985. [Hebu 85]
tateurs.
Masson, Collection Scientique des Télécommunications,
1985. [Kle 76]
Ecoulement du trac dans les autocommu-
Gérard Hébuterne.
Leonard Kleinrock:
Queueing Systems . Volume 1: Theory, 1975,
ISBN 0-471-49110-1. Volume 2: Computer Applications, 1976, ISBN 0-471-49111-X. John Wiley and Sons. [Lav 83]
Stephan .S. Lavenberg:
Computer Performance Modelling Handbook.
Academic Press, 1983. [Rob 90]
G. Robertazzi: Computer Networks and Systems: Queueing Theory and Performance Evaluation. Springer Verlag Thomas 1994.
Hasard et Chaos. Editions Odile Jacob, 1991. Telecommunication Networks: Protocols, Modeling and Analysis. Addison Wesley, 1987. R. Syski: Introduction to Congestion Theory in Telephone Systems.
[Rue 91]
David Ruelle:
[Sch 87]
Misha Schwartz:
[Sys 86]
(seconde ed.)ISBN 0-444876723. Elsevier Ltd., 1986.
[Tak 91]
Queueing Analysis. Vol. 1, vacations and priority systems. North Holland, 1991. H. Takagi:
Cette bibliographie essaie de couvrir toutes les références aux sujets abordés dans ce cours. Elle déborde largement les savoirs attendus des auditeurs.