L’indiscernabilité locale dans les réseaux de files d’attente à multiliaisons ou multiserveurs

214 pp. 214-237

L'indiscernabilite de files

locale dans les reseaux d'attente & multiliaisons

ou multiserveurs Pierre LE GALL*

R~sum~

Comme auparavant pour les r~seaux de files d'attente ~t simples serveurs, on montre maintenant que, pour les rdseaux ?z multiserveurs (ou multiliaisons), les queues locales sont caract~ris~es par des arriv~es locales indiscernables (aprks la travers~e de deux ou trois dtages) correspondant (dans les m~moires de gestion) & des agglutinations de services courts derribre un service long, susceptibles de produire (dans les mdmoires de gestion d'entrde) des encombrements trbs longs (m#me pour des intensit~s de trafic faibles) quand les dur6es de service varient beaucoup. Dans ce cas, les thdories traditionnelles (ddpendant surtout de la charge) ne conviennent pas pour le dimensionnement de ces m~moires de gestion d' entr~e.

Mots cl~s : File d'attente, t~tude th6orique, R6seau file d'attente, M6moire tampon, Surcharge, Temps service.

THE LOCAL INDISTINGUISHABILITY IN MULTISERVER (MULTILINK) QUEUEING NETWORKS

Abstract

As previously for single link queueing networks, now it is proved, for multiserver (multilink) queueing networks, that the local queues are defined by indistinguishable local arrivals (after having crossed two or three stages), corresponding (in buffers) to some agglutinations of short service times behind long service times, possibly leading (in the input buffers) to very long congestion times (even for low traffic intensities) when the service times are highly varying. In that case, traditional queueing theories (mainly influenced by the loads) are not appropriate for input buffer dimensioning.

Key words : Queue, Theoretical study, Queueing network, Buffer storage, Overload, Service time.

* Ing6nieur en Chef honoraire des TEl6communications, 4, Parc de la B~reng~re, F-92210 Saint-Cloud, France.

ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004 1/24

P. LE GALL -- L~INDISCERNAB1LITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 215

Sommaire

I. Introduction II. R~seaux defiles d' attente ~ simples

serveurs III. R(seaux defiles d' attente

gt multiserveurs

IV. Consequences de l'indiscernabilit~ locale pour le cftblage, le dimensionnement, la gestion, la normalisation et la protection

V. Conclusion Bibliographie (10 r~f )

I. I N T R O D U C T I O N

Jusqu'b maintenant, l'6tude des rEseaux de files d'attente s'est fortement inspirEe de celle des rEseaux tE16phoniques ~ b appels perdus ~. L'arrivEe locale a toujours ErE consid6rEe comme discernable, donnant lieu (Eventuellement) ~t des processus locaux d'arriv6es rEgEnE- ratifs ou m~me poissonniens si les chemins d'arrivEe pouvaient &re considErEs comme nombreux et indEpendants. L'habitude a 6t6 prise de considErer ces rEseaux de files d'attente comme pouvant ~tre dEcomposEs en petits rEseaux (plus simples h Etudier), quitte h sommer les attentes successives partielles. Et m~me pour les grands rEseaux maillEs, on admet aisE- ment qu'ils peuvent &re considErEs comme la succession de queues isolEes et indEpendantes, conduisant b une influence relativement minimisEe des longues durEes de service sur les faibles durEes de service qui suivent. Au debut des grands rEseaux, on avait fait un effort de normalisation (dans le rEseau et pour 1' acc~s ~ l'usager) pour dEfinir le rEseau ATM OU tOUS les paquets avaient pourtant la m~me longueur. Depuis, on a considErE qu'il Etait inutile de normaliser, m~me dans le cas de longueurs de paquets extr~mement variables, le serveur classique isol6 M/G/1 6tant tr~s docile et semblant s'intEgrer facilement dans les rEseaux. Pourtant, l'expErience ayant donne une influence inattendue des longues durEes de service (ou des longs paquets), on a invoqu6 (dans la littErature internationale) les processus ~< frac- tals >> de Mandelbrot et les rEpartitions de durEes de service ~ longues traTnEes de type ~, Pareto >~. Tout ceci, pour conserver la discemabilitE des arrivEes locales.

En fait, que petit observer un esprit critique non expert en files d' attente ? Qu'il consid6re une autoroute ?~ plusieurs voies avec interdiction pour les poids lourds de doubler, et qu'il se demande ce qui pourrait se passer si cette interdiction Etait levee. Les poids lourds font envi- ron 60 km/h. Les voitures de tourisme vont facilement deux fois plus vite. Avec l'interdiction prEcitEe, les voitures de tourisme peuvent doubler : elles sont discernables par leur vitesse propre et rapide. Si on l~ve l'interdiction prEcitEe, notre observateur verra rapidement un poids lourd sur chaque voie gEnErant (derriere lui) une agglutination de voitures de tourisme ne pouvant rouler qu'b 60 km/h. Toutes ces voitures et camions deviennent indiscernables pour la vitesse, d 'ob une baisse sensible du debit de l'autoroute, m~me en cas de peu de poids lourds.

Avec nos calculs sophistiquEs qui vont suivre, nous allons trouver le m~me phEnomEne d'indiscernabilitd pour les arrivEes locales dans les rEseaux de files d'attente ~t multiserveurs, phEnom~ne dE ~un changement de paramktre directeur apr~s le premier Etage : au lieu de l'attente locale, c 'est le temps de sEjour (6gal au temps de service de l'arrivEe initiant la pEriode d'encombrement) qui va contr61er le processus local de queue. I1 en rEsultera l 'appa-

2/24 ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004

216 P. LE GALL - L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE

rition d'agglutinations entra~nant de longues p6riodes d'encombrement m~me ~t charge faible (dans les m6moires d'entr6e, mais pas sur les circuits), en cas de dur6es de service extrd- mement variables et de courants de trafic entrants n 'ayant pas beaucoup interf6r6 avec d'autres h l '6tage juste en amont. Ceci rend discutables les m6thodes de gestion traditionnelles (bas6es sur l'influence des charges et n6gligeant celle des m6moires de gestion) et pose des contraintes de normalisation pour la variation de ces longueurs de service ou de paquet, moins de ne disposer d 'une ~< zone de gestion ou de commande >> beaucoup plus rapide que le r6seau de liaisons lui-m~me. Mais ce n'est plus forc6ment le cas pour les m6moires d'entr6e de ce r6seau de gestion (en particulier dans les R6seaux Intelligents), et ce n'est pas le cas pour la m6moire d'entr6e de l 'usager ou du ~< site>> consid6r6, ceux-ci risquant d'etre sans protection.

Nous nous proposons de rappeler sommairement, dans la Section II, la th6orie r6cem- ment publi6e ~ l'l~tranger pour les r6seaux de files d'attente h simples serveurs (ou liaisons) : cas de la commutation de paquets [8] et cas de r6seaux g6n6raux [9]. Cela nous sera n6ces- saire pour traiter, h la Section III, le cas nouveau des r6seaux de files d'attente a multiserveurs (ou multiliaisons), avec choix dans l 'ordre des arriv6es locales, en nous r6f6rant ~ nos r6cents travaux sur le multiserveur G/G/s : cf. [6]. Enfin, ~ la Section IV, nous analyserons quelques cons6quences pour le cfiblage, le dimensionnement, la gestion, la normalisation et la protection. Toutes ces r6f6rences 6viteront de longs expos6s math6matiques, car la raison premiere de la non-d6tection ant6rieure de cette indiscernabilit6 r6side dans la pratique des raisonnements habituels probabilistes n6cessitant l 'usage d'hypoth~ses simplificatrices par- fois douteuses : par exemple l 'abus de la loi de Poisson suppose la discernabilit6 des arriv6es locales. Mais nous retrouverons cette bonne loi traditionnelle dans le cas de courants de trafic amont divergeant, cassant en aval les corr61ations de ~ l 'effet queue s6rie >>, sans avoir besoin de revenir aux notions traditionnelles de trafic offert et de source locale de trafic. En effet, il n ' y aura plus d'appels offerts vers l 'aval mais des portions offertes de p6riodes d 'encombre- merit amont, comportant des appels indiscernables. Le cablage amont (d6finissant le degr6 d'interf6rence des courants amont) aura finalement plus d'influence sur les encombrements aval des m6moires d'entr6e que les charges elles-mEmes, surtout dans le cas de charges cou- rantes faibles eutra~nant un sous-dimensionnement avec les m6thodes classiques se r6f6rant h la notion erronn6e de source locale de trafic.

Par souci de clart6 nous avons pr6f6r6 publier dans la langue de Descartes.*

II. RI~SEAUX DE FILES D'ATTENTE ~, SIMPLES SERVEURS

La queue locale est dEfinie par la convergence de divers chemins entrants. Nous verrons comment nous d6barrasser de l 'existence des courants transversaux amont. On est alors amen6 ?t dEfinir au pr6alable l 'arbre de concentration et la queue s6rie 6quivalente, avant d'6valuer l 'effet des courants de trafic divergcant juste en amont.

* Par exemple, si les termes ~attente>> et <<temps de sdjour>> (= attente + dur6e de service) sont bien clairs en franqais, il n'en est pas de m6me en anglais, o~ le mot <<waiting>> peut aussi bien d6signer les deux termes pr6ci- t6s : cf. la formule de Little. Cette confusion serait d6sastreuse pour le pr6sent article, ok le param~tre directeur (habituellement l'attente) devient le temps de s(jour ~ partir du deuxi~me 6tage.

ANN. TELECOMMUN., 59, n ° 1-2, 2004 3/24

E LE GALL - L'INDISCERNABILITE LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 217

I L l . L e R ~ s e a u e t I ' A r b r e d e C o n c e n t r a t i o n

A la figure 1 ci-dessous, on repr6sente n chemins entrants, d6finissant un arbre de concentration ~ m 6tages, chacun (dans chaque branche) correspondant ~t un serveur ou une liaison, avec une file d'attente o?a le choix des arriv6es se fait dans l'ordre. Les courants de trafic longitudinaux Ai(i = 1... n) sont offerts hun serveur final h l'6tage de concentration (m+ 1), c 'est h dire l'6tage local consid6r6. Dans les 6tages amont, ces courants (trait6s dans les m0mes queues que pour les courants Bi) interf6rent avec d'autres courants de trafic longitudinaux B i (i = 1... n), lesquels divergent ~ l'6tage m e t ne sont donc pas offerts au serveur final consid6r& Ils contiennent des visiteurs (ou paquets) qui peuvent ~tre d6nom- m6s << dgparts prgmaturds >>. A l'6tage m, ils ne peuvent &re distingu6s des visiteurs (ou paquets) des courants A i, car leur temps de s6jour est identique a celui des visiteurs (ou paquets) de ces courants A i durant la m~me p6riode d'encombrement. En cons6quence, il est impossible de dire que le courant de trafic A iest offert au serveur final (m + 1) consi- d6r6. On peut seulement dire qu'une portion de la p6riode d'encombrement est offerte au serveur final, sans pouvoir dissocier les 616ments des courants A iet B i. Mais nous verrons que le r61e essentiel, de tout glgment de B i s'interposant, sera de casser (en aval) les corrg- lations entre deux 616ments successifs de Ai, en modifiant l'intervalle d'arriv6e. L'apparition de l'indiscernabilit~ et de ces << dgparts pr(matur~s ~> va changer profond6ment le type de raisonnement ~ adopter.

En tout cas, cette propri6t6 de temps de s6jour identiques (durant une p6riode d'encombrement) permet de faire abstraction des autres courants de trafic transversaux, darts les 6tages plus en amont. D'ailleurs, le visiteur (ou paquet), initiant une p6riode d'encombrement, a un long temps de service durant lequel la queue aval (comprenant les courants transversaux) s'6vacue. En outre, si les services successifs de ce visiteur sont identiques (et ce sera aussi ~ consid6rer dans le cas de r6seaux g6n6raux), les pdriodes d'encombrement ne peuvent se morceler. Notre visiteur au long service a aussi initi6 les p6riodes d'encombrement amont (courants transversaux exclus). I1 est donc ais6 d'61iminer l'existence des courants transversaux amont.

Stage 1 Stage m BI B 1 ~ Stage (m+l)

A~ g n _ _

FIG. l - A concentration of n identical m-stage tandem queues with premature departures.

Concentration de n queues sdrie identiques ?tm gtages avec dgparts prdmaturds.

4/24 ANN. TELr~COMMUN., 59, n ° 1-2, 2004

218 P. LE GALL -- L' INDISCERNABILITt~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE

De m4me, une arriv6e <~ interm6diaire >> peut 4tre consid4r6e comme offerte au premier 6tage avec un temps de service nul durant les premiers 6tages. En outre, une arriv6e << exo- g6ne >> ~t l '6tage (m+ 1) ne sera consid6r6e que pour son influence sur les arriv6es <<endo- g6nes >>, seules consid6r6es dans la pr6sente 6tude. Cette arriv6e n'apparalt alors que comme une arriv6e interm6diaire.

D'ofi la Figure 1 simple, avec sa sym6trie et sans courants transversaux ni arriv6es inter- m6diaires. Cette m6thode de l 'arbre de concentration est d'ailleurs adopt6e depuis longtemps par I'UIT-T dans ses Recommandations sur L'ing6nierie du trafic, concemant particuli~rement les R6seaux Intelligents, oh l 'on m61ange de courts messages de signalisation et des messages intelligents, 10 ou 15 fois plus longs.

I I .2 . N o t a t i o n e t H y p o t h e s e s

On rappelle que, dans toutes les files d'attente, les arriv6es locales sont traitges dans leur ordre d'arriv~e. Du fait de l 'indiscernabilit6 des temps de s6jour nous serons amen6, ~t la Section I1.3.4, ~ introduire un effet de gigue pour en tenir compte. Nous supposons, en outre, le r~gime stationnaire.

Pour les notations, consid6rons le cas g6n6ral non restreint ?t la commutation de paquets. Dans une queue s&ie, consid6rons le h e visiteur a l '6tage k (= 1... m) :

- attente locale : w~ ; dur6e de service local • T ~ ; - fonction de r6partition de T hk: Fk(t) = Prob (T k < t) ; E(T h k) = T k ; - dur6e de s6jour local: s ~ = w ~ + T ~; fonction de r6partition • Uk(t) = Prob (s ~ < t) ; - intervalle d'arriv6e [entre les visiteurs ( h - 1) et hi • yk . • h - l , -p6 r iode d' inoccupation (6ventuelle) durant l 'intervalle

(1) Y ~ - 1 : ekh -1"

En d' autres termes, nous pouvons 6crire (dans le cas d 'une branche d6termin6e) :

= ek-1 + k-I (2) Yh k - 1 Th '

En outre, nous poserons :

(3) T J + ... + T kh = Th(j, k), s J +...+ Skh = Sh(J, k).

Pour le visiteur h, ces deux termes sont respectivement la dur6e de service globale et la dur6e de s6jour globale de l '6tage j ~t l '6tage k. Du fait de l 'hypoth~se de stationnarit6, Fin- dice h peut ~tre supprim6 quand il n 'es t pas nOcessaire. A l '6tage (m+ 1) du serveur final de concentration de la Figure 1, ces termes correspondent ~t une branche arbitraire et nous introduirons la relation :

(4) vm+ 1 --h-1 = Y J-1 + [Sh(J' m) - S h _ l(J' m)],

ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004 5/24

P. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 219

oil, en l 'absence des courants B i, le processus YJh-l concerne le processus total des arriv6es h l '6tage j sur l 'ensemble des n branches. Habituellement, au premier 6tage, Yl_l correspond au processus total des arrivEes au r6seau (et atteignant ensuite le serveur final consid6r6), processus habituellement suppos6 poissonnien, de taux d'arriv6es : ~, = [E(Ylh_l] -1. La charge (= intensit6 du trafic) du serveur final (m+ 1) est alors :

(5) /9 = )~-T m+l.

A l'6tage m de la branche i (en excluant les courants transversaux) les charges de A iet B i • tt sont respectivement a i et a i, et nous posons :

(6) a i = a(~ + a"i,

oil une arriv6e exog6ne peut correspondre hun courant A i avec m i = 0 e t a i = a]. Nous d6dui- sons donc, pour la charge du serveur final •

2' (7) p = a i. i = l

Notons que, dans la branche i (~ l '6tage m), la probabilit6 (pour deux paquets successifs) de ne pas atre s6par6s par un d6part pr6matur6 est :

a • i

(8) P i - ai,

d'apr~s la notation (6). En consid6rant maintenant toutes les branches de l 'arbre de concentration et le serveur final (m + 1), la probabilit6 de deux arriv6es locales successives de ne pas ~tre s6par6es par des d6parts pr6matur6s est, avec la notation (7) •

1 x 2 , a' (9) _ ~_~ i nl i=1 -P- " Pi"

11.3. L a queue s6rie 6quivalente ( s a n s d 6 p a r t s p r 6 m a t u r 6 s )

II.3.1. L'6quivalence

Pour l'instant, nous omettons l'existence des courants B i de la Figure 1, et donc l 'existence des d6parts pr6matur6s. Dans [8] nous avons d6fini une queue s(rie (quivalente o~a la queue locale, h l '6tage final (m+ 1), est identique ~ la queue du serveur final de l 'arbre de concentration. D'apr~s la notation (1), l 'attente de cette queue locale est d6finie par l 'expression stochastique suivante :

(10) w~n+l = (s~n+l 1 _ ym+l~+ h-1 j ,

avec la notation (X) + = Max (0, X). En introduisant la relation (4), nous d6duisons l '6quation :

(11) Sh( j, m) + w~ n+l = Max [Sh(J, m), Sh_l( j, m+ 1) - Y J-l]"

6/24 ANN. TI~LI~COMMLrN., 59, n ° 1-2, 2004

220 P. LE GALL - L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE

Ajoutons T~ n+ 1 dans les deux membres. Nous obtenons •

(12) Sh( j, m+l) = Max [Sh( j, m) + T ~ +1, Sh_l(j, m+l) + T~ n÷l - Y J-l]"

D6signons par h = n o l 'indice du visiteur (ou paquet) initiant la p6riode d'encombrement, et par W0(m + 1) l 'attente (en r6gime stationnaire) correspondant au serveur isol6 M/G/1 d6fini par le couple (YI_I, T~n+l), le processus Yt_ l (~ l 'entr6e du rEseau) 6tant suppos6 poissonnien. Faisons j = 1 dans l'6quation (11). Dans [8] nous avons obtenu la relation :

(13) Sh(1, m) + w~ n+l = Sn0(1, m) + W0(m + 1).

En commutation depaquets, o~ T~ . . . . . T~ n+~ (si les d6bits successifs sont identiques), les p6riodes d'encombrement ne peuvent se morceler. Le visiteur (ou paquet) n o a alors aussi initi6 les p6riodes d'encombrement amont (en excluant les courants transversaux). En cons6- quence, nous pouvons 6crire avec la notation (3) :

(14) Sn0(1, m) = Tn0(1, m)

Dans [8] nous avons donn6 le nombre (m+ 1) d'6tages de la queue s(rie ~quivalente par l 'expression :

Var Tn0(1, m) (15) m2 -- War T m+l '

x n 0

en supposant ces variances non nulles. Rappelons que Tn0(1, m) et T m÷ln0 correspondent a la combinaison de toutes les branches de l 'arbre de concentration de la Figure 1.

H.3.2. L'indiscernabilit~

Durant l 'encombrement, (2) donne (en commutation de paquets) :

Y~-I = T J-1 = T ~ + I = T 1.

Le second terme entre crochets, dans la relation (12), donne alors, durant un encombrement :

(16) Sh( j, m+l) = Sh_l(j, m+ 1) . . . . . Sn0(J, m+ 1).

En consid6rant toutes les valeurs de j, nous d6duisons qu'~ chaque 6tage tousles temps de s6jour sont identiques ~ celui initiant l 'encombrement, lequel est long. Ainsi, les petits paquets occupent la m6moire de gestion comme s'ils 6taient longs. I1 en r6sulte une forte surcharge darts cette m6moire, avec agglutination des petits paquets derriere les grands. Tous les visiteurs (ou paquets) deviennent indiscernables, le processus des arriv6es n'ayant plus d'effet (sauf pour le vide entre p6riodes d'encombrement et pour la longueur du service du visiteur initiant l 'encombrement). Autrement dit, le paramktre directeur n'est plus l 'attente : c 'est maintenant le temps de sgjour impos6 par le paquet leader initiant l 'encombrement. Le processus de queue locale n'est plus une queue G/G/1 et nous ne pouvons plus le repr6senter par des exemples sur une figure comme pour le premier 6tage off tous les 616ments sont discernables. Ce r6sultat ressemble ~t notre exemple du trafic routier, consid6r6 dans l'introduction, trafic domin6 par la lenteur des camions poids lourds, rendant inutile la rapidit6 propre

ANN. TI~LI~'COMMUN., 59, n ° 1-2, 2004 7/24

P. LE GALL - L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 221

de chaque petite voiture. C'est cette indiscernabilit6, avec son param6tre directeur, qui sera compl6tement oubliEe dans les th6ories traditionnelles de rEseaux de files d'attente.

Dans ce cas de commutation de paquets (h d6bits identiques), dEsignons par T N la longueur de paquet la plus grande et par T 1 la longueur la plus petite, et posons :

TN (17) A -

Tl

Dans [8] on a vu que le taux de re jet de la mEmoire est ElevE si sa capacitd K (en nombre de paquets) est inf6rieure h A, laquelle correspond h la taille maximale des agglutinations. Au contraire, ce taux de rejet s'annule si l 'on respecte la condition :

(18) ~ - A - ~ .

Notons que cette condition peut ~tre attEnuEe dans la z6ne de commande si le debit interne est plus Elev6 que le debit du rEseau.

II.3.3. La queue locale (dans la queue s~rie ~quivalente)

Dans le cas d'un support infini pour la r6partition des longueurs de paquet (ou de service), nous avons rappel6 dans [8] que seules les r6partitions compl6mentaires [1- Fk(t)] ~t d6croissance exponentielle pouvaient &re admises, une d6croissance plus lente ~ la Pareto (en fonction de puissance) ne pouvant ~tre accept6e. Ceci est dO ~ l'effet d'amalgame des p6riodes d'encombrement : quand un service plus long (que celui de la p6riode d'encombrement en cours) arrive, il impose sa nouvelle longueur ce qui allonge d'autant la p6riode d'encombrement. A l'origine, ce ph6nom~ne a 6t6 detect6 dans [4].

Le calcul de l'attente locale W(m + 1), h l'6tage (m + 1), n'est pas simple ; mais nous pouvons rnentionner un r6sultat simple [2] dans le cas de la queue s6rie M/M/1 --> M/1 (en commutation de paquets), compar6 a l'attente W 0 de la queue isolEe M/M/l, en ce qui concerne la valeur moyenne :

(19) W(m+l) _= In [(m+ 1). W 0 ] + 0,577, si m > 1.

Darts le cas de la commutation de paquets, de longueurs forcEment finies, consid6rons l'6tage (m+ 1) un courant de trafic compose de N courants partiels poissonniens, d'indice ! (1 = 1... N), Ecoulant des paquets de longueur constante T 1 ( T 1 < T 2 <...< TN). Le taux d'ar- riv6e partiel est ~q et la charge partielle est Pl = ~" Tr Pour le courant global, nous posons :

N N

1=1 1 =1

Dans [7] nous avons d6fini la fonction de r6partition Um+l(t) du temps de sdjour local l'Etage (m+ 1) :

Pour t < T 1 : U m + l ( t ) = 0 ;

PourT f S t <Tt+ 1 "Um+l(t) = Vo(1)'Vl(t,m;l), avec"

(21) Vo(h -- ~1 + " ' " + ~ l . l - - p k 1-(p l+ . . . + p p '

8/24 ANN. T~-zJA~COMMUN., 59, n ° 1-2, 2004

222 P. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE

vt(t, m ; l) =

[ [ k l + l + . . . ' + ~ N _ t) Exp - m l ~ l + - - 7 ~ . . ' + p / ) " (T/+I m + "'" + ~N . (TN_ TN_ 1)] ]

1 - (Pl +'" ''+ PN-1)

Pour t _> TN: Um+l(t) = 1.

Quand m croit, S m+l ----> T Net War(s m+l) ---> 0, conduisant ?~ la constance des temps de s6jour et au <<ph6nom~ne d'agglutination>> dans les m6moires de gestion. En fait, pour m e t T N grands (pN/p n'6tant pas faible), on peut se contenter de l 'approximation suivante, rela- tive au temps de sdjour des longs paquets :

Um+l(t) = (1__~_~) . 1 - p ' Exp [ - mPN {1 t ~ P o u r 0 < t < T N I-(P-PN) L 1- (P--PN)'~ --~N/J; k /

Pour t > TN:

(22) Um+l(t) = 1

Notons que ce cas de queue locale, sans <~ d6parts pr6matur6s >> en amont, correspond au cas off il n 'y a gu~re d'interfdrence avec d'autres courants de trafic ~ l'6tage juste en amont.

11.3.4. L'effet de gigue et la queue terminale de I 'arbre de concentrat ion

Les fonctions de r6partition (21) et (22) sont relatives au temps de s6jour Um+ 1 d'un paquet arbitraire ~t l'6tage (m+ 1) de la queue s6rie 6quivalente. Ce serait le m~me temps de s6jour ~ l'6tage final de l 'arbre de concentration de la Figure 1, si les arriv6es locales se fai- saient dans le m~me ordre qu'~ l'arriv6e 7t l'entr6e du r6seau. En fait, il n 'en est rien, surtout en cas de dissym6trie des branches de l'arbre. Dans [8], nous avons 6t6 amen6 ~ ajouter un << effet de gigue local >> J, de sorte que, suivant la notation (1), le temps de s6jour stationnaire

l '6tage final (m+l) de l 'arbre de concentration est :

(23) S m+l ---- Urn+ 1 + J.

J a la mEme valeur pour tousles paquets de la p6riode d'encombrement consid6rEe et est ind6pendant de Urn+ 1. Dans [8] on a donn6 une expression approximative pour la fonction de r6partition J(t) de J, si PN < 0 ,3p et n 2 > 5, n 2 6tant le nombre de branches identiques de l'arbre, T et p &ant d6finis par (20) :

p o u r 0 < t < T " - T : J ( t ) - 1 - p " .p,, (l _ l ) . p, T,, T 1 - p " t + T ' a v e c , n 2 1 - p" T"

(24) pour t _> T" -T : J(t) = 1.

En fait, l 'effet de gigue n'est sensible que pour les lourdes charges, mais il est compatible avec l'indiscemabilit6 des arriv6es locales.

ANN. T~LI~COMMUN., 59, n ° 1-2, 2004 9/24

P. LE GALL -- L'INDISCERNABILITt~ LOCALE DANS LES Rt~SEAUX DE FILES D'ATTENTE 223

11.4. Le r6seau h commutation de paquets

Pour un rEseau h commutation de paquets (avec mSme debit h chaque Etage), les courants de trafic B i, producteurs de << d(parts pr(matur(s >>, apparaissent maintenant dans la Figure 1. A cause de la dependance mutuelle des courants A ie t B i (h l'Etage m), gErEs dans une mSme queue, on ne peut plus dire que les paquets de A i sont offerts au serveur final (m+ 1). On doit maintenant dire qu 'une portion de la pEriode d 'encombrement h l 'Etage m est offerte h ce serveur final. Soit ~ un nombre alEatoire 6gal h 1 avec la probabilitE (l/n1) dEfinie par (9), et

Egale h 0 avec la probabilit6 (1 _ 1 ) , et ajoutons T ~ ÷1 aux deux membres de (13), cette relation pouvant s'Ecrire : nl

(25) s~ n+l = [Sno(1, m) - Sh(1, m)] + [Wo(m+ 1) + T~ n+l]

Dans [8], nous avons not6 que l ' indiscemabilit6 des arrivEes (~t l'Etage m) entra~ne que le serveur final (m+ 1) ne perqoit que le temps de sEjour global amont apparent c~. Sh(1, m). La relation stochastique (25) devient alors, h cause de cette apparence :

st~ n+l = o~. [Sno(1-, m) - Sh(1, m)] + [Wo(m + 1)+Tt~n+I],

ou encore d'aprSs (25) Egal h (23) :

(26) s~n+ 1 = ~. [Urn+ 1 + J] + (1 - 0¢) • [W0(m + 1) + T~ n+ l].

Pour R(z) > 0 et en appliquant l 'opErateur espErance E, nous dEduisons la relation de base pour le temps de s(jour local d 'une arrivEe quelconque, h l 'Etage (m+ 1) et en r(gime stationnaire :

(27)

Eexp [- z.s~ n+l] = ( 1 ) - E e x p [- Z(Um+ 1 + J)] + (1 - 1 ) .Eexp [- z.(W0(m + 1) + T~+I)] n I n 1

Le premier cas, de frEquence (1/nl), correspond h <<l'effet de queue sdrie>> quand deux arrivEes locales successives ne sont pas sEparEes par un (ou plusieurs) depart prematurE. Dans le cas contraire, le deuxi~me terme correspond h la queue isolde soumise directement au processus y l _ 1 des arrivEes offertes ~t l'entrEe (et s'Ecoulant dans le serveur final consi- dErE). De sorte que dans [8] nous avons pu presenter la propriEtE fondamentale :

Propri~t6 1. (L'indiscernabilit( et l'influence des d(parts pr(matur(s). Dans tout rEseau commute par paquets, toute correlation entre deux arrivEes locales suc-

cessives disparalt si ces arrivEes sont sEparEes (en amont) par des d(parts pr(matur(s. Le processus des arrivEes 7t l 'entrEe du rEseau est alors << d(voilg >>, sans aucun rapport avec la notion (non valable) de source de trafic locale. Cela suppose, toutefois, que la capacit6 (en nombre de paquets) des mEmoires de gestion est supErieure h la taille maximale des agglutinations (17) : cf. condition (18).

10/24 ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004

224 P. LE GALL -- L'INDISCERNABILITE LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE

Cette propri6t6 a d'ailleurs 6t6 v6rifi6e par l'exp6rience involontaire suivante. Lors du remaniement du c~blage des noeuds (= Points de Transfert de Signalisation) d'un R6seau Intelligent peu charg6 [donc condition (18) non satisfaite a cause des calculs habituels] mais 6coulant des messages de signalisation courts et aussi des messages Intelligents 10 ou 15 fois plus longs, les circuits sortants d'une bonne proportion de ces noeuds sont devenus pratiquement ind6pendants (pour leur gestion), supprimant l'apparition de d6parts pr6matur6s (vu par l'aval). L'effet queue s6rie est alors apparu dans les m6moires d'entr6e (~ d6bit interne peu 61ev6) des centres aval, alors que la condition (18) n'6tait pas satisfaite (~ cause des faibles charges). Finalement, sans changement des charges un encombrement g~n~ral s'est produit (durant 12 heures) dans les mdmoires d'entrde. I1 a ainsi 6t6 bien mis en 6vidence la non existence de sources de trafic locales, t~tant non initi6s h ce ph6nom~ne, les Ing6nieurs ont cru ~ une erreur de logiciel.

G6n6ralement, ce sont les m6moires d'entr6e des usagers ou des sites (~ d6bit interne peu 61ev6) qui sont les plus sensibles : on peut ainsi imaginer des processus d'attaques de sites informatiques, en particulier ?t l 'aide de la convergence de longs messages peu fr6- quents pour ne plus satisfaire la condition (18). En tout cas, ces m6moires sont causes des coupures, hachures ou retards survenant durant une communication t616phonique par internet.

Ces exemples montrent que, si la condition (18) n'est pas satisfaite, la protection de l'usager ou des sites ne peut ~tre assur6e. Pour y rem6dier, c'est une affaire de normalisation (ou de segmentation) des longueurs de paquets. Les charges ne sont plus seules h consid6rer et la gestion des nouveaux r6seaux doit tenir compte des probl~mes 6ventuels dus a l 'effet queue s6rie, quand il y a peu de << d6parts pr6matur6s >> en amont par suite de peu d'interf6rence entre les courants A i et Bi, si le processus de queues amont est tr~s faible.

II.5. Le r~seau g~n~ral h simples serveurs

Dans [9], nous avons r6cemment pu 6tendre les propri6t6s pr6c6dentes au cas de r6seaux g6n6raux h simples serveurs, ~t la condition de franchir deux 6tages au pr6alable pour trouver l'apparition de << faux vides >> d6clench6s par l'existence de pdriodes d'encombrement mor- celdes, quand un service aval est plus court qu'un service amont, rompant la r6gularit6 de la commutation de paquets. Dans ce cas, deux paquets successifs, corr616s en amont, peuvent paraitre non corr616s en aval, car s6par6s par ce faux vide, consid6r6 comme un vrai vide dans les th6ories traditionnelles et entralnant faussement l'hypoth6se d'ind6pendance de ces deux paquets successifs. Comme pr6c6demment, avant de consid6rer le r6seau, examinons la queue s6rie.

I I .5 .1 . L a q u e u e s~r ie

Dans le cas pr6c6dent dc la commutation de paquets, nous avions not6 que le paquet, initiant une p6riode d'encombrement, en avait fait de m~me aux 6tages pr6c6dents. Dans la relation (12), le premier terme entre crochets devient, avec la notation (3) :

Sh( j , m) = Th(J, m).

ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004 11/24

P. LE GALL - L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 225

Cette relation (12) peut donc s'6crire, dans le cas de la commutation de paquets :

(28) Sh( j, re+l) = Max [Th( j, m+ 1), Sh_~( j , m + 1) + T~ n÷l - YJ-1]"

Dans le cas g6n6ral ofa les p6riodes d'encombrement peuvent se morceler, nous avons donn6 dans [9] une extension ~ cette relation, laquelle devient :

Sh( j, m+l) = Max [Th( j, m + 1), Sh_l( j , m+l) + Oh( j, m + 1)-Y~_~], (29)

avec :

(30) Oh( j, m + 1) = Max [T j ..... T~n+l].

Compte tenu de (4), le deuxi~me terme entre crochets dans (29) conduit ~t l'expression suivante, durant une p6riode d'encombrement/~ l'&age m :

(31) Y~-I + [Sh(J' m) - Sh_l( j, m)] = Y~n+11 = Oh( j, m).

Ainsi, dans (29), 0h(J, m+l)est un intervalle d'arriv6e y~n~ offert h l'6tage aval (m+ 2). Ce n'est pas la dur6e de service local T~ n÷l comme indiqu6 dans la relation stochastique d'origine (12). Dans cette relation (12), le premier terme de la parenth~se concernait le temps d'acc~s du paquet initiant l'encombrement (h partir d'un vide vrai ou faux). II pouvait donc avoir attendu en amont, d'o~a [dans (12)] son temps de s6jour amont Sh( j, m) incluant des attentes 6ventuelles. Maintenant, dans ce cas g6n6ral de p6riodes d'encombrement morce- 16es (6ventuellement), la nouvelle relation stochastique (29), ota le premier terme de la parenth~se ne comporte qu'un temps global de service amont, ne consid~re (dans le deuxi~me terme) qu'une p6riode d'encombrement entre deux vrais vides, incluant donc les faux vides.

D'otl le terme Oh(j, m+ 1) au lieu du terme habituel T~ ÷1. C'est que, maintenant, un faux vide n'est plus consid6r6 comme sdparant deux paquets ind6pendants : ils sont interd6pen- dants par ce terme Oh( j, m+ 1) d6pendant des 6tages amont, au contraire des th6ories traditionnelles ota l'on ne distingue pas les vides vrais ou faux. Et m~me, l'expression (30) de O h montre que tous les 6tages amont peuvent avoir la m~me influence, alors que g6n6ralement on admettait une influence d6croissante en fonction de la distance de cet &age amont consi- d6r6. Finalement, ce terme 0 u va apporter une diff6rence fondamentale avec les th6ofies traditionnelles.

En outre, le visiteur (ou le paquet), retard6 en amont, n'arrivera qu'~t la fin de ce faux vide. I1 ne le percevra pas (d'ofa le nora de << faux vide >>). I1 percevra comme si les services successifs gtaient identiques ou croissants, d'oll la Propri~t~ 2 ci-dessous.

Nous avons prouv6 ces relations(29)-(30) dans [9], ~t l'aide d'une mEthode purement analytique, tr~s efficace mais recourant 5 l'int6gration de Cauchy et nous 6vitant d'avoir ~ introduire des consid6rations physiques. Toutefois, pour la bonne compr6hension du lecteur, nous proposons, ~ l'Annexe, une d6monstration moins math6matique mais plus physique. Elle n6cessite de bien assimiler la notion d'indiscernabilitd ddcoulant de l'existence d'un parambtre directeur (le temps de s6jour), lequel efface la queue habituelle G/G/loit les dldments sont discernables sans paramOtre directeur (et efface aussi la validit6 de figures locales, qui ne peuvent repr6senter que des 616merits discernables).

I1 est utile de mentionner que l'effet d'amalgame des p6riodes d'encombrement (cf. Sec- tion I1.3.3.) tend ~ supprimer l'existence des faux vides dans le cas de r6partitions de service ~t <~ longues trafndes >> ("heavy tails" en Anglais), difficilement acceptables darts l'effet queue s6rie.

12/24 ANN. TI~Lt~COMMUN., 59, n ° 1-2, 2004


Toutes ces remarques s'appliquent ~ la queue s6rie Jackson M/M/1 ~ M/1. bien connue. L'erreur habituelle provient de ce que l'on admet implicitement la notion de source de trafic locale. Une fin de service ~ un &age est consid6r6e comme une source poissonnienne pour l'6tage suivant. De m~me, une simulation de trafic, observant un 6tage donn6, ne distingue pas les faux vides des vrais vides. On conclut que chaque 6tage se comporte comme un serveur M/M/let on dEduit que la queue s6rie Jackson est une succession de serveurs M/M/1. D'oh la th6orie markovienne g6n6ralis6e des r6seaux de queues ~ dur6es de service exponentielles.

Finalement, en partant de la relation (29) et en accord avec nos remarques ant6rieures sur la perception du visiteur arrivant seulement en fin de faux vide, nous avons prouv6 dans [9] la propri6t6 suivante :

Propri~t~ 2. (L'indiscernabilitd des temps de sdjour dans les queues s(rie). Dans les queues s6rie en r6gime stationnaire, et pour n'importe quel type de corr61ation

(existante ou non) entre les dur6es de service successives du h e visiteur, la dur6e de s6jour local s~ n+l [h l'6tage (m+ 1)], est la somme de deux composantes :

- Une premiere composante U ~ +~ correspond ~ l'hypoth~se oh les dur6es hypoth6tiques de service amont successives seraient identiques ~ la dur6e de service locale T~ n+l, le hombre d'6tages (m+ 1) 6tant d6fini par l'expression (15) oh Tno(1, m) tient compte des corr61ations (existantes ou non) entre les services r6els successifs, letemps de s6jour local correspondant

(23). - Une seconde composante V~ n÷l correspond ?~ l'attente du serveur G/G/l, d6finie par la

dur6e de service :

(32) "c~ n*x = 0h(1, m + 1) - 0h(1, m) = [T~ n+l - 0h(1, m)] +,

et par l'intervalle d'arriv6e local 0h(1, m) durant les p6riodes d'encombrement, 0h(1, m) 6tant d6fini par l'expression (30).

En fait, la premi6re composante correspond h n'importe quel visiteur au sein de la p6riode d'encombrement, et est ind6pendante de l'intervalle d'arrivde local 0h(1, m). Par contre, la seconde composante est propre fi un visiteur donne, mais d6croR rapidement quand m croit, pour devenir pratiquement n6gligeable apr6s l'6tage 3. Autrement dit, la discernabi- lit6 disparait pratiquement apr~s le troisi~me Stage et, d'ailleurs, l'arriv6e locale discernable s'Echappe progressivement quand m cro~t.

Finalement, une queue s6rie apparait comme un moyen de transfert de services oh le processus d'arriv6es sert ~t dffinir les vrais vides, ainsi que les dur6es de service initiant les p6riodes d'encombrement, avec la complication de l'amalgame progressif des p6riodes d'encombrement.

II.5.2. Le r~seau g~n~ral

En d6finitive, cette Propri6t6 2 permet d'utiliser tous les r6sultats pr6sent6s ~ la Section II.4. pour la commutation de paquets. Ainsi, m6me quand les p6riodes d'encombrement sont morcel6es (cas de la zone de commande), nous pouvons 6noncer :

Propri~t~ 3. (L'effet queue sdrie dans les r(seaux de files d'attente 71 simples serveurs). En r6gime stationnaire et apr~s avoir travers6 trois 6tages d'un r6seau g6n6ral quelconque

de files d'attente ~t simples serveurs, oh les dur6es de service successives (d'un m~me visi-

ANN. TI~L/~COMMUN,, 59. n ° 1-2, 2004 13/24

P. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 227

teur) sont corrgldes (ou non), les arriv6es locales (et les chemins entrants) deviennent indiscernables et correspondent au phdnom~ne d'agglutination darts les m6moires de gestion.

Le temps de s6jour local r6el peut ~tre considErE comme g6n6r6 par des durEes de service amont hypoth6tiques et identiques ~ la dur6e de service locale, le nombre Equivalent d'6tages travers6s 6tant d6fini par l'expression (15), incluant dans Tn0(1, m) les corr61a- tions existant (ou non) entre les services reels successifs (du m6me visiteur).Ceci suppose une capacit6 (en nombre de visiteurs) des m6moires de gestion sup6rieure h la taille max# male des agglutinations (T N / Tl), suivant la notation (21), afin d'6viter l 'influence des agglutinations.

On peut finalement remarquer que les mEthodes habituelles de simulation de trafic sont gEn6ralement organis6es pour simuler des successions d'6v~nements discemables ou Evaluer des coefficients de transition entre 6tats discernables, ce qui ne peut conduire qu'~t une sous- 6valuation de l'influence des longs services. En definitive, la seule m6thode sfire consiste simuler tout le r6seau et ?~ suivre la progression complete des appels d'un courant de trafic, ce qui peut ~tre fastidieux ou impossible dans le cas de grands rEseaux, surtout quand it s' agit de simuler aussi les mEmoires de gestion. Car les phEnom6nes d'encombrement se passent dans ces m6moires et non dans les rEseaux ou les serveurs.

III. RESEAUX DE FILES D'ATTENTE A MULTISERVEURS

Maintenant, pour tenir compte de l'utilisation de hauts d6bits permettant d'6couler les paquets d'une communication sur plusieurs liaisons d'un m~me canal, nous passons au cas nouveau de r6seaux gEn6raux de files d'attente ~t multiserveurs (et queues uniques), ofa le processus des arrivEes ~ l'entrEe concerne encore des arrivEes distinctes (non simultan6es), en rdgime stationnaire. A chaque queue, les arrivfes sont choisies dans l'ordre des arrivdes, et les durEes de service successives (d'un m~me visiteur) sont corr~l~es ou non.

ConformEment ~ notre exemple de l'autoroute, cite en introduction, nous retrouverons les propfi6t6s des serveurs uniques avec l'indiscernabilit6 et les agglutinations des arrivEes locales. Mais, en l'absence de normalisation des durEes de service, le cas de multiserveurs permet de rendre discemables les services courts en affectant les services longs ~ un ou deux serveurs seulement (comme dans l'exemple de l'autoroute), h la condition que ces services ne soient pas trop nombreux.

Nous rappellerons tout d'abord nos r6cents rEsultats simples sur le serveur GI/G/L (et m~me G/G/L), publi6s dans [6], avant de passer ~ la queue s6rie, puis au r6seau gEnEral, dans le cas d'un usage symdtrique des serveurs.

III.1. Le multiserveur GI/G/L

La queue GI/G/L, avec choix dans l'ordre des arriv6es, est d6finie par un processus d'ar- riv6es r6g6n6ratif, mutuellement ind6pendant des dur6es de service et par des dur6es de ser-

14/24 ANN. TI~L~COMMUN., 59, n ° 1-2, 2 0 0 4

228 I'. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE HLES D'ATrENTE

vice mutuellement indEpendantes. La fonction caractEristique des intervalles d'arriv6e Y~-I et des durEes de service T~ n+l sont respectivement q00(z) et q0m+1(z), correspondant h :

(33) ~00(z) = f o eZt • dF0(t), ¢Pm+l(Z) = f o eZt "dFm+l(t), R(z) < 0.

La charge du multiserveur est :

E(T~ n+l) (34) L . r / - < L,

E(Y~_I)

7/(< 1) Etant la charge de chaque serveur. Dans [6] nous avons dEmontrE trois propriEtEs, caractErisant ce multiserveur et correspondant h l'indiscernabilitE des departs en cas d'encombrement, e t a la discemabilitE en cas de non encombrement.

Propri~t~ 4. (Comportement de chaque serveur) Dans une queue symEtrique stationnaire GI/G/L, dEfinie par le couple [¢p0(z), ~Pm+l(Z)],

chaque serveur se comporte indEpendamment comme un simple serveur GI/G/1, de charge 7/, et est dEfini par le couple [~P0(Lz), ¢pm+l(z)].

Nora : On en d6duit la probabilitE Q0 de non attente devant ce simple serveur, et la taille moyenne v de sa pEriode d 'encombrement ininterrompue :

1 (35) v - Q0"

Propri~t~ 5. (Le multiserveur encombre'). Si w(j) est l 'attente d 'un visiteur quelconque devant le simple serveur j , supposd en

combrg et se comportant suivant la PropriEtE 4, l'attente d 'un visiteur quelconque devant le multiserveur stationnaire, supposg encombrd, est :

(36) "~ = Min [w(1) ..... w(L)].

Les departs sont donc indiscernables en cas d'encombrement. Par contre, en cas de non encombrement, les d6parts sont discemables comme dans le modble ~t ~ appels perdus >>, off la taille de la pEriode d 'encombrement est seulement v = 1. Autrement dit, en regime stationnaire, on peut supposer l'Etat initial vide et 6voluer vers le debut d 'un encombrement suivant le module h appels perdus, ce qui ne semble avoir jamais EtE consider6, en particulier dans [10]. Nous dEduisons finalement :

Propri~t~ 6. (La probabiIit~ d'attente du multiserveur). La probabilitE d'attente de la queue stationnaire GI/G/L est :

(37) P = v'Pa l + ( v - 1)P a '

O~1 Pa est la probabilitg de perte dans le mod61e fi appels perdus, v Etant donn6 par (35).

ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004 15/24

P. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RESEAUX DE FILES D'ATTENTE 229

Nota : a) Pour la queue M/G/L, nous dEduisons que P est Egal h la formule classique 1 d'attente d'Erlang, car (35) donne : v =

l - r /" b) La PropriEtE 5 n'est pas valable pour la queue GI/D/L, ~ cause de l 'aspect dEterministe

de la rEpartition des arriv6es sur chaque serveur. Cette queue est Equivalente a la queue GI/D/1 d6finie par le couple [(~p0(z)) L, tPm+l(Z)]. Mais les singularitEs, correspondant aux (z/ racines de l'Equation [%(z)]L40m+l(Z) = 1, c'est-~-dire encore de l'6quation %(z).q~m+ 1 -~- = 1

ou encore %(Lz) . ~0m+l(z) = 1, sont ceUes du serveur de la PropriEtE 4. De plus, C. Palm a note que la formule d'attente d'Erlang &ait finalement une excellente approximation pour 6valuer la probabilit6 d'attente de la queue M/D/L.

ConsidErons maintenant la queue sErie.

III .2 . La q u e u e s~rie h m u l t i s e r v e u r s GI /G1/L --> Gm+l]L

I1 est commode d'utiliser la notation vectorielle et l '6quation de Borovkov [1] pour la queue GI/G/L, afin d'Etendre l 'expression (10) ci-dessus au cas de la queue sErie ~ multiserveurs. A l'Etage (m+ 1) de la queue sErie GI/G1/L ---> GIn+l/L, nous rappelons que l'intervalle d'arrivEe, entre les visiteurs ( h - 1) et h, est: y~__~l. Soit w~,~ 1 l'attente jusqu'h ce qu'au moins j serveurs soient libres pour l'arrivEe X~ +1. Le vecteur w~ n+l a pour coordonnEes wm+l hd (J = 1...L). Soit R(X) le vecteur ayant pour entrees (Xl... XL), O~ x I = Min j (xj), e = (1, 0.. .0) et i = (1...1). Borovkov 6tablit l '6quation vectorielle g6n6rale et locale suivante, h l'6tage (m + 1) :

(38) w~ n+l = Max [0, R(W~+l ~ + T~_+1%) - Y~+I 1. i]

Introduisons l 'expression (4) dans (38), nous dEduisons l'6quation vectorielle :

(39) Sh(1, m)- i + w~ n+l = Max [Sh(1 , m ) . i, R(Sh_l(1, m). i + w~+~ +T~_+I l • e)-Y~_ r i].

Si h = n o correspond au visiteur initiant une p6riode d'encombrement, nous d6duisons de (39), comme pour (13), pour h > n o :

(40) Sh(1, m)- i + w~ n+l = Sno(1, m) . i + (Wo)~ n+l.

Soustrayons Sno(1, m) • i dans les deux membres de (39). A cause de (40) nous obtenons :

= "I'm* 1 A (41) (W0)~+I Max [0, R((w0)~+~ + -h_x.~) -Y~-I" i]

Autrement dit, (w0)~+l correspond au multiserveur d6fini par le couple [Y[-1, T ~ +1] et non par le couple fy1 T 11 du premier 6tage [comme pour (13)]. Nous d6duisons de (40) et t h-l' h J

16/24 ANN. TELECOMMUN., 59, n ° 1-2, 2004


(41) que, 5 l'6tage (m + 1) et durant la p6riode d'encombrement (morcel6e ou non), les d6buts de service peuvent se d6duire, par une simple translation Sn0(1, m), des d6buts de service ~t l'6tage 1 [o~ l'on utilise les services T~ n+l de l'6tage (m + 1)]. En d'autres termes, ~t l'6tage (m + 1) le visiteur peut &re consid6r6 comme servi par le serveur ayant le m~me num6ro que ce serveur fictif suppos6 ~t l'6tage 1, alors qu'en r6alit6 il peut y avoir changement de num6ro en cours de progression. Finalement, pour le comportement de la queue h l'6tage (m+ 1) tout se passe comme si le visiteur 6tait trait6 par une queue s6rie h simples serveurs identiques avec dur6e de service T~ n+l. Nous pouvons 6noncer la propri6t6 importante suivante, d6coulant de la Propri6t6 4 :

Propri~t~ 7. (La queue sFrie & multiserveurs). A l'6tage (m+ 1) d'une queue s6rie ~t multiserveurs de capacit6 L, d6finie par le processus

d'arriv6es ¢p0(z) au premier 6tage, l'attente et le temps de s6jour local d'un visiteur quelconque sont semblables ?a ceux d'une queue s6rie h simples serveurs identiques avec un processus d'arriv6es (P0(Lz), le temps de service h chaque 6tage 6tant T~ a+l et le nombre d'6tages 6quivalent 6tant donn6 par l'expression (15).

Cette Propri6t6 7 correspond h l'exemple de l'autoroute consid6r6 dans l'introduction.

111.3. Le r~seau h muitiserveurs

A cause du morcellement des p6riodes d'encombrement des r6seaux g6n6raux ~ multiserveurs, il n'apparalt gu6re possible, a priori, de supposer un comportement local comme influenc6 par une sorte de commutation par paquets. En fait, h la Section II.5.1. et avant d'6noncer la Propri6t6 2, nous avions d6jh remarqu6 que, dans le cas Jackson de totale ind6- pendance entre les dur6es de service successifs, le visiteur arrivait h la fin des faux vides sans pouvoir les percevoir. Finalement, la Propri6t6 7 ci-dessus nous ramenant au cas des queues s6rie h simples serveurs (identiques), nous pouvons invoquer la Propri6t6 3 des r6seaux h simples serveurs et l'6tendre aux r6seaux ~t multiserveurs.

Propri~t~ 8. (L'effet queue sFrie dans les rFseaux ~t multiserveurs). En r6gime stationnaire et apr6s avoir travers6 trois &ages d'un r6seau g6n6ral h multiser-

veurs, o?a les dur6es de service successives (d'un m~me visiteur) sont corrgIFes (ou non), les Propri6t6s 3 et 7 m~nent 7t l'indiscernabilit6 des arriv6es locales (et des chemins entrants) et correspondent au ph6nom~ne d'agglutination dans les m6moires de gestion dont la capacit6 minimale K 1 (en nombre de visiteurs) est maintenant L fois celle de la Propri6t6 3 :

(42) K 1 > L.

en utilisant la notation (21). Les expressions [(15) pour la d6termination du nombre d'6tages ~quivalent] et (27) ~ l'6tage (m+ 1) sont encore valables, o~ [Urn+l+ J] correspond ~ la queue s6rie ~ simples serveurs identiques (Propri6t~ 7) d6fini par le couple [~Oo(L.z ), ~Om÷l(z)] et

ANN. Tt~LI~COMMUN., 59, n ° 1-2. 2004 17/24

P. LE GALL - L'INDISCERNABILITI~ LOCALE DANS LES Rt~SEAUX DE FILES D'ATTENTE 231

Wo(m+l) correspond maintenant au multiserveur GI/G/L isol6 [h l'6tage (m+ 1)], d6fini par le couple [%(z), ¢pm+l(z)].

Finalement, l'indiscernabilit6 des arrivdes locales (et des chemins entrants) simplifie l'6tude des r6seaux ~ multiserveurs, en nous ramenant au cas de simples serveurs. Notons, toutefois, que la condition (42) impose une capacit6 minimale, des m6moires de gestion, L fois sup6rieure ~t celle du cas des simples serveurs. Nous verrons qu'un mode d'exploitation, assignant les services longs ~ une ou deux liaisons seulement, all~gera consid6rablement les m6moires.

IV. CONSI~QUENCES DE L ' INDISCERNABILITI~ L O C A L E POUR LE CABLAGE, LE DIMENSIONNEMENT, LA GESTION,

LA NORMALISATION ET LA P R O T E C T I O N

IV.I. La m~thode d'investigation et le param~tre directeur

Notons bien la diff6rence fondamentale du module d'exploitation avec attente, notam- ment pour la commutation de paquets et la gestion de la z6ne de commande, avec le mod61e ~ << appels perdus ,,, pratiqu6 en commutation de circuits. Dans le cas de l'attente, la taille v d'une p6riode d'encombrement est sup6rieure ~ 1 et l'indiscemabilit6 (avec les agglutinations) appara~t durant cet encombrement. Au contraire, en commutation de circuits (donc ~t appels perdus) on a v = 1 et on conserve toujours la discemabilit6. Mais en commutation de paquets, on remplace la discernabilitg avec la protection des usagers par l'indiscernabilitd avec une protection affaiblie des usagers : voir nos commentaires apr6s la Propri6t6 1, off il apparait que l'influence de la charge locale est remplac6e par l'influence du c~blage amont, susceptible d'affaiblir les mdthodes traditionnelles de gestion de r6seau. Notons toutefois que le gros avantage de la commutation de paquets est d'avoir pu remplacer les circuits par le param6tre temps. L'essor de la haute technologie a permis de passer progressivement des kilobits aux gigabits, rendant imperceptible l'apparition d' agglutinations quand le d6bit interne de la z6ne de commande est bien sup6rieur ~t celui du r6seau.

Notons aussi que, m~me pour de grands esprits, l'&re humain perqoit difficilement cette notion d'indiscernabilit6 li6e ~ l'apparition d'un <~ parambtre directeur >> (ici le temps de s6jour local, dominant l'attente), non existant dans la queue isol6e ou au premier 6tage d'un r6seau (tel le leitmotiv en fond d'op6ras de Verdi et Wagner) : voir l'opposition historique des statistiques (discernables) de Bose-Einstein et des statistiques (indiscernables) de Fermi-Dirac pour appr6cier (en physique nucl6aire) le comportement des 61ectrons ~ un mSme niveau d'gnergie autour de l'atome. Pendant de nombreuses ann6es, on ne s'6tait int6ress6 qu'aux ph6nom6nes amusants relativistes avant de consid6rer s6rieusement le nouveau ~ param6tre directeur >> : l'dnergie de la matiSre et ses cons6quences (pourtant d6jg apparue bien auparavant dans les 6quations de H. Poincar6 et dans l'irradiation de la plaque de zinc de Joliot).

18/24 ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004

232 e. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RESEAUX DE FILES D'ATTENTE

IV.2. Le cfiblage, le dimensionnement et la gestion

Nous rappelons notre exemple apr~s l ' tnonc6 de la Propritt6 1, Section 11.4. Un changement dans la fapon de gtrer les attentes de sortie des noeuds amont change profondtment le comportement du trafic dans les attentes d'entrte des noeuds en aval, puisque la notion de source de trafic locale n'est plus valable comme en commutation de circuits. Dans le cas du modtle ~t appels perdus, les corr61ations amont mtnent ~ la notion de ~ trafic adouci >~, pour conserver cette notion de source de trafic locale. Mais ici, l'indiscernabilit6 supprime la notion de source de trafic locale et ntcessite de considtrer en bloc (dans l ' t tage amont) tous les 616merits, mSme ceux changeant ensuite de chemin (les ~ dtparts prfmaturts >>). On ne peut, dans l'expression fondamentale (27), que considtrer une portion de l 'encombrement amont comme offerte au serveur aval considtr6.

Par contre, cette expression (27) tient compte de l'influence des ~ d6parts prtmaturds ~> (des courants amont divergeant) qui cassent toutes les corrtlations apparues dans la progression amont pour ~ d&oiler ~ le processus d'arriv6es (~ l 'entrte du r6seau) dans toute sa purett. C'est gdndral dans tousles grands ensembles : il appara~t l'indiscernabilit6 li6e hun nouveau paramttre local (ici le temps de stjour) gouvernant l'6volution, difftrent du cas d'isolement (ou du premier 6tage) o~ ce param~tre n'existe pas.

Naturellement, ces considtrations peuvent ~tre embarrassantes pour la marche ?~ suivre, car il n 'est pas question de pouvoir agir sur le c~blage des n~euds amont. Toute- fois, dans [8] on a constat6 que si les calculs traditionnels conduisaient ~t une capacit6 de m6moire vtrifiant la condition (18), on pouvait ignorer l 'influence des agglutinations et donc l 'influence du c~blage sortant des noeuds amont. D 'apr t s le tableau 1 de cette r6ft- rence, correspondant ~t une distribution uniforme des charges de chaque classe de longueur de paquet, il rtsulte qu'il en est ainsi pour une charge du rtseau (donc du circuit) suptrieure ou 6gale ~t 0,6 : p > 0,6. Mais pour p < 0,5 il faut absolument respecter la condition (18), ou (42) dans le cas du multiserveur, si l 'on veut 6viter de longs encombrements dans ces mtmoires d'entrte.Cette condition devient p < 0,9 s'il n 'y a pas distribution uniforme (par exemple, une ou deux classes de petits paquets c6toyant une classe de paquets trts longs).

l~videmment, pour l'efficacit6 des m&hodes de gestion de rtseau traditionnelles bastes sur l'observation des charges, il est surprenant d'apprendre que les charges faibles peuvent gtntrer de longs encombrements, alors que les charges fortes ne gfntrent que des encombrements de durte classique. Mais c 'est la constquence d'une absence de normalisation dans la variation des longueurs de temps de service (ou de paquet), absence lite ~t la croyance de la notion de source de trafic locale.

Cette absence de normalisation est ontreuse dans le cas des multiliaisons pour hauts dtbits. La condition (42) impose une capacit6 minimale L fois plus 61evte dans les mfmoires d'entrte. En fait, le cas des multiliaisons permet de remgdier a une absence de normalisation (d'ota le prtsent article), en assignant les longs services TN2 sur deux liaisons (par exemple) et les services courts (longueurs < TN~) sur les ( L - 2 ) autres liaisons (un peu comme pour l 'exemple de l'autoroute). La condition (42) devient :

(43) > ( L - 2). ( TN' ) + 2,

ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004 19/24

E LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 233

ce qui est beaucoup moins contraignant en capacit6 de m6moires : pratiquement les services longs n 'ont alors plus gu~re d'effet sur la capacit6 minimale des m6moires d'entr6e, ce qui rejoint notre exemple de l 'autoroute, cit6 dans l 'Introduction.

IV.3. La normalisation et la protection

Dans le cas des r6seaux ?t tr~s large bande, ce besoin de normalisation des dur6es de service n 'apparak pas : les m6moires travaillant dans les gigabits rendent imperceptibles l 'effet des agglutinations. Mais ce n 'est plus forc6ment le cas des serveurs locaux.

Cette facilit6 de transmission, en commuta t ion de paquets, ne devraient pas faire oublier certaines obligations morales, concernant la protection du r6seau et surtout des usa- gets. I1 est embarrassant de trouver, en << surfant sur la toile >>, des informations donnant des m6thodes d 'at taque (discr6tes) de noeuds ou de sites par convergence de paquets tr6s longs (mais peu fr6quents) aux identit6s et origines banales. Une premi6re m6thode de protection consisterait ~ imposer la segmentation des longs paquets. Une seconde m6thode (la plus efficace) serait de normaliser tout s implement ces longueurs de paquets, au prix d 'une petite complication dans la gestion de ces paquets pour r6tablir (~ l 'arriv6e) l ' information initiale.

V. C O N C L U S I O N

En utilisant des m6thodes d'investigation peu habituelles, orient6es vers l 'utilisation de relations stochastiques plut6t que de processus al6atoires classiques, nous avons 61imin6 la notion habituelle de source discernable de trafic locale et mis en valeur l 'apparition d 'agglutinations dans les m6moires d'entr6e et nous avons d6terr6 cette notion d'indiscernabilit~ locale, qui nous a permis de passer ais6ment au cas des multiserveurs.

Elle nous a aussi permis de mettre ~jour la notion deparambtre directeur local (le temps de s6jour), inexistante dans le cas de la queue isol6e, pour expliquer l 'effet de 1' amalgame sur le processus de queue, et permettant ~t ces nouveaux << d~parts pr(matur~s >> des courants divergeant (juste en amont) de briser l 'effet de toutes les corr61ations amont pour << d~voiler >> le processus d'arriv6es h l 'entr6e du r6seau, si celui-ci est convenablement charg6 par une m6thode de gestion appropri6e, car l'indiscernabilit~ locale tend ?~ escamoter l'effet de la charge au profit d'agglutinations dans les m6moires d'entr6e, dont la protection r6side dans un dimensionnement associ6 h la grande variation des longueurs de paquets, ou dans l'utilisation de multiliaisons.

En d6finitive pour le cas de simples serveurs, et compte tenu de notre remarque h la fin de l 'Annexe, le pr6sent article a present6 une th~orie des r~seaux g~n~raux de files d'attente avec arrivges ggngrales & l'entr~e du r~seau.

Manuscrit refu le 5 septembre 2002 Accept~ le 26 novembre 2003

20/24 ANN. TI~LI~COMMUN,, 59, n ° 1-2, 2004

234 P. LE GALL -- L'INDISCERNABILITE LOCALE DANS LES RESEAUX DE FILES D'ATTENTE

R e m e r c i e m e n t s

L'auteur remercie tout particulibrement l'un de ses examinateurs anonymes pour ses nombreuses remarques et ses demandes de clarification concernant les exposes sur l'indiscernabilit(, ayant entrafng des adjonctions et l'Annexe.

B I B L I O G R A P H I E

[1] BOROVKOV (A.A.), Stochastic Processes in Queueing Theory. Springer-Verlag, New York, (1976), 280 p. [2] F~CnE (G.), VEILLARD (Y.), The tunneling technique and the tandem queue effect. Proc. wIP Workshop on tp

andaTM traffic Management, WArM 2001, Paris (Sept. 3-5, 2001), pp. 53-61. [3] FRIEDMAN (H.D.), Reduction Method for Tandem Queueing Systems, Operations Research, U.S.A. (1965),

vol. 13. [4] KLEINROCK (L.), Communication Nets, Stochastic Message Flow and Delay, Mac Graw-Hill Book Company,

New York (1964), Lincoln Laboratory Publication. [5] LE GALL (P.), Traffic modeling in packet switched networks for single links. Ann. T~ldcommunic. (1994), 49,

n ° 3-4, pp. 111-126. [6] LE GALL (P.), The stationary G/G/s queue with non-identical servers. J of AppL Math. and Stoch. Anal

0AMSA), (1998), 11, n°2, pp.163-178. [7] LE GALL (P.), The stationary local sojourn time in single server tandem queues with renewal input. J. of AppL

Math. and Stoch. Anal. (JAMSA), (1999), 12, n°4, pp.417-428. [8] LE GALL (P.), Local queue in single link packet switched networks with variable packet lengths Proc. ITC-17,

Salvador de Bahia (Brazil, Sept. 2001) ; Teletraffic Engineering in the lnternet Era, 4, Elsevier (Amsterdam), 2001, pp.l139-1150.

[9] LE GALL (P.), Single server tandem queues and queueing networks with non-correlated successive service times. Z of Appl. Math. and Stoch. Anal 0AMSA), (2001), 14, n°4, pp.381-398.

[10] POLLACZEK (E), Th6orie analytique des probl~mes stochastiques relatifs hun groupe de lignes t616phoniques avec dispositif d'attente. Mdmorial des Sciences Mathdmatiques, Gauthier-Villars, Paris (1961).

B I O G R A P H I E

Pierre L E G A L L a fait carri6re h SOCCrrEL (chef du Service T616trafic) et au CNET (chef de la d616gation franqaise ~ la Commission 2 de I'UIT-T) ; Est membre de l 'Acad6mie des Sciences de New York ;

A N N E X E

L e p a r a m ~ t r e d i r e c t e u r et les f a u x v ides : E f f a c e m e n t d u p r o c e s s u s local des arr iv~es

a) Le faux vide

Dans nos commentaires suivant 1' expression (31), nous avons soulign6 l ' importance d 'un nouveau param~tre Oh( j, m + 1), qui appara~t comme un intervalle d'arriv6e offert vers l '6tage

ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004 21/24

P, LE GALL - L'INDISCERNABILITt~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE 235

aval (m + 1) et qui ne s'identifie pas forc6ment h la dur4e de service local T ~ ÷l, comme en commutation de paquets (h ddbit unique), ofa les p6riodes d 'encombrement ne sont pas mor- cel6es. Maintenant, dans le cas plus g6n4ral off les dur4es de service successives ne sont pas identiques, les p6riodes d 'encombrement peuvent se morceler et ~tre s4par6es par des ~< faux vides >>.

Mais au cas ota le << visiteur >> prfic6dent (h - 1) se lib4rerait plus vite en aval, d6clenchant un << faux vide >>, nous avons remarqu6 que le visiteur suivant h ne pourrait arriver en aval qu'~t une 4poque correspondant au cas oia le visiteur (h - 1) aurait une dur4e de service 6gale

son service amont, comme en commutation de paquets. Autrement dit, le visiteur h ne per- ~oit pas le faux vide et se croit toujours dans le cas de la commutation de paquets, lui faisant donc subir une attente. Or, pour les th6ories traditionnelles, ne distinguant pas les faux vides des vrais vides, le visiteur h ne dolt pas attendre. I1 y a donc une divergence entre les r4sultats habituels et ceux d6coulant de la relation stochastique de base (29). A l 'origine, nous avions obtenu cette relation dans [9] par simple d6duction analytique (int6gration de Cauchy) ne n6cessitant aucun raisonnement pour comprendre le ph4nom6ne physique. On se propose maintenant d'expliquer le phdnom6ne (a posteriori).

b) Le param~tre directeur

La relation stochastique de base (10) de la queue 5 l '4tage (m + 1) est celle d 'un serveur G/G/1. Mais il y a d6pendance entre le trafic offert et le temps de s6jour pr4c4dent. On ne peut l 'utiliser directement. Les relations de base sont l 'expression (2) de l 'intervalle d'arri- v4e, incluant le vide 4ventuel, et surtout la relation (4) que nous 6crirons pour l '4tage local (m+ 1), avec m _> 1 :

( la) y~_+2 _ y~+l 1 = s~n+l _ s m + l h - l "

Notons que, si on ajoute une m~me quantit4 A aux temps de s4jour des visiteurs successifs [second membre de (la)], il n 'appara/t aucun changement pour les intervalles d'arriv4e [premier membre de (la)]. Examinons maintenant en d4tail l '6tage 2.

oO F.tage 2.

Consid4rons une p6riode d 'encombrement h l '6tage l(e~ = 0). De l 'expression (2) nous d6duisons :

(2a) Y2_ 1 TIh, Y131 T 2 + e 2 - 2 1 - s 2 1 ) + Max 2 = = _ T h +(T h _ = [Th,T1 + Th 2 -S2_l ].

(1 a) devient, pour m = 1 :

(3a) Y 3 _ , - Y2_l = s 2 - sZ_v

Suite h notre remarque ant6rieure, une certaine diminution A des temps de s6jour s]~ et s~_, ne change pas la quantit4 y 3 _ Y 2 1 = y 3 1 _ T 1, et done y 3 reste inehang4. Prenons une diminution.

(4a) A = s2_1 - T~ _> 0.

22/24 ANN. T~LI~COMMUN., 59, n ° 1-2, 2004

236 l,. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATTENTE

La nouvelle valeur de sh_ 12 est T~ qui correspond h l'apparition d'un faux vide, correspondant donc h :

(5a) S2_l = T t.

(2a) devient, si l'in6galit6 (4a) est v6rifi6e :

(6a) Y3_ 1 = M a x 2 2 (Th, T~) = T~.

Du fait de (4a), on peut alors avoir T~ < T 2 et donc d'aprSs (6a) : Y 3 1 = Max(T~, T 2) = T~.

Mais notons que T~ est ind6pendant de T~. Si T~ = T~, (3a) donne alors :

(7a) s 2 = s2_1.

Du fait du faux vide, on peut alors accro~tre T[ sans changer sh_ 12 et Sh2 _- Th .2 On conserve donc l'6galit6 (7a) et donc s2_l = T 2, ces 6galit6s se conservant aussi apr~s suppression de la d6croissance A. En outre, (2a) devient :

y3_, = Max [T~, T~)].

Nous pouvons 6noncer :

Proprifit~ la . (constance du temps de s6jour h travers un faux vide). l'6tage 2 de la queue s6rie 6quivalente et quand T~ < T~, les temps de s6jour successifs

s2_l et s 2 sont 6gaux, m~me si ces visiteurs sont s6par6s par un ~ faux vide ~>. En outre, Fin- tervalle d'arriv6e vers l'aval vaut :

(8a) Y3_1 = Max [T~, T~].

Donc la queue it l'(tage 2 n'estpas du type G/G/I, mais la Propri~t~ 2 permet de d6com- poser le temps de s6jour en une composante ofa (7a) et (8a) sont toujours v6rifi6s (meme pour T~ > T~), et en une seconde composante du type G/G/lcorrespondant ~ la dur6e de service suppl6mentaire IT 2 - T~] +.

Notons que, la notion de faux vide n'existant pas ~t l'6tage 1, on ne peut y appliquer la Propri6t6 la.

fl ) Etage (m + 1).

L'6galit6 Y~-I = T~ devient maintenant, toujours dans le cas de l 'encombrement l'6tage 1 :

(9a) Y~+~ = 0n(1, m).

En outre, pour la premiere composante de la Propri~t~ 2, (8a) devient :

(10a) ym+2h_l = 0h(l' m+ 1) = Max [0h(1, m), T~+I],

d'o?a l'expression (30) de 0h(1, m + 1). En r6sum6, la Propri6t6 la devient :

ANN. TI~LI~COMMUN., 59, n ° 1-2, 2004 23/24

P. LE GALL -- L'INDISCERNABILITI~ LOCALE DANS LES RI~SEAUX DE FILES D'ATI'ENTE 237

Propri6t6 2a. (constance du temps de sdjour gl travers un faux vide) ; ~, l'6tage (m+ 1) de la queue s6rie 6quivalente, durant un encombrement h l'6tage 1 et

quand :

(1 la) T~ n+l < 0h(1, m),

les temps de s6jour successifs m+l s~n+l Sh_ 1 et sont 6gaux, m~me si ces visiteurs sont s6par6s par un ~( faux vide ~. En outre, l'intervalle d'arriv6e est donn6 par l'expression (30) de 0h(1, m).

Cette constance du temps de s6jour fait apparMtre une troisi~me propri6t6 :

Propri6t6 3a. (le paramktre directeur). Durant une p6riode d'encombrement de la queue s6rie 6quivalente, incluant les faux

vides, et en supposant la condition (1 la), les temps de s6jour 5 l'6tage (m+ 1) restent constants et 6gaux h celui du leader initiant cette p6riode : c' est le paramktre directeur. Les attentes s'en d6duisent comme cons6quence.

Ainsi, l'indiscemabilit6 conceme aussi bien les arriv6es que les branches de l'arbre de concentration, soumises au mfime leader.

Darts le cas de r6partitions de dur6es de service h <~ longues trafndes >>, la condition (1 la) est ais6ment v6rifi6e quand m cro~t, de sorte que la queue locale ~ l'6tage (m+ 1) se comporte comme si les dur6es de serviceT k &aient identiques ~ T~ n+l. Par contre, on peut voir que le ph6nom~ne de l' amalgame des p6riodes d'encombrement, d6tect6 dans [4], en faisant croitre les temps de s6jour, tend h effacer les faux vides.

A noter que, dans le cas de dur6es de services constantes et identiques h chaque 6tage (mais diff6rentes entre &ages), l'expression (30) de 0best en accord avec [3].

Enfin cette Annexe, ne supposant rien sur la nature du processus Y~-1, est valable pour un processus g(ndral d' arrivfes ~ l'entr6e du r~seau.

24/24 ANN. Tr~LECOMMON., 59, n ° 1-2, 2004

Documents

L’indiscernabilité locale dans les réseaux de files d’attente à multiliaisons ou multiserveurs