Cours Ingenierie Du Trafic [PDF]

Zitiervorschau

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.