Concept d’extensivité pour un réseau de Clos et probabilité de blocage pour un système à trois étages

  • Published on
    23-Aug-2016

  • View
    215

  • Download
    2

Embed Size (px)

Transcript

  • pp. 239-256 239

    Ernesto BONOMI *

    Jean-Luc LUTTON **

    Marc Roy FE IX *

    Concept d'extensivit6 pour un r6seau de Clos et probabilit6 de blocage

    pour un syst6me trois 6tages

    Analyse

    Les auteurs introduisent le concept d" extensivitd utile pour l'$tude de modbles r~duits d'autocommutateurs. Le calcul de la probabilit$ de blocage pour un r$seau de clos ~ 3 dtages est effectud pour diverses strategies d'acheminement. Les rdsultats sont compards d ceux obtenus par la formule de Lee clans le cas de la strat~gie al~atoire. On en d~duit une dvaluation des diff~rentes stratdgies d" acheminement.

    Mots el6s : R6seau connexion, Commutation t616communi- cation, T616trafic, Mod61e thermodynamique, Limite thermo- dynamique, Blocage, Simulation num6rique, Mod61e probabi- liste, Acheminement.

    4. Mod$lisation du r~seau de Clos d 3 dtages. 5. Probabilitd de blocage. 6. Description de la simulation. Conclusion. Annexes. Bibliographie (21 r~f.).

    INTRODUCTION

    THE CONCEPT OF EXTENSIVITY FOR CLOS NETWORKS

    AND BLOCKING PROBABIL ITY FOR THREE STAGE NETWORKS

    Abstract

    The authors introduce the concept of extensivity which is useful in the study of switching networks models of reduced size. They calculate blocking proba- bility for different routing rules and deduce an evaluation of this different routing rules. The results are compared to the Lee formula in the case of random hunting rule.

    Key words : Switching network, Telecommunication switch- ing, Teletraffic, Thermodynamic model, Thermodynamic limit, Blocking, Numerical simulation, Probabilistic model, Routing.

    Sommaire

    Introduction. 1. R~seau de Clos ~ 3 dtages. 2. R~seaux de Clos d dtages multiples. 3. Limite thermodynamique.

    La commutat ion est l 'op6ration qui consiste /t relier temporairement et de diverses faqons les 616- ments d 'un ensemble de d6part D et d 'un ensemble d'arriv6e A, lesquels peuvent 8tre identiques ou diff6rents.

    On consid6rera le deuxiSme cas et l 'on supposera que le nombre N d'616ments de D est 6gal au nombre d'616ments de A. Le syst6me r6alisant cette fonction, appel6 autocommutateur quand les op6rations se font de faqon automatique, comprend d 'une part une structure maill6e ou rdseau de connexion, qui sert de support physique aux appels et une logique de commande, c'est-/t-dire un certain nombre d'ins- tructions n6cessaires pour piloter ces derniers/t l 'aide d'un 6quipement appropri6. Un r6seau de connexion est un assemblage de sous syst6mes non bloquants (ou commutateurs 616mentaires) que nous appellerons matrices dans la suite de cet expos6. Ces commu- tateurs 616mentaires ont une dimension bien inf6rieure ~N.

    Pour mieux d6finir le probl6me, il est n6cessaire de bien pr6ciser la nature des ensembles de d6part et d'arriv6e. Chaque entr6e est une ligne connect6e /t une seule source. Ces sources sont ind6pendantes

    * CRPE, av. de la Recherche Scientifique, 45045, Orl6ans. ** Actuellement au CNET-PAA, ATR. 92131 Issydes-Moulineaux.

    1/18 ANN. TI~LI~COMMUN., 37, n ~ 5-6, 1982

  • 240 E. BONOMI. - EXTENSIVITE POUR UN RF.SEAU DE CLOS ET PROBABILITE DE BLOCAGE

    les unes des autres et de m6me intensit6. Chaque sortie est une adresse diff6rente. I1 s'agit done de liaisons point h point. Autrement dit, on ne consid6re pas, ici, le cas de faiseeaux de circuits entrants ou sortants, raceord6s /t diverses entr6es ou sorties.

    Dans la r6alit6 les appels se pr6sentent ~ l'entr6e D suivant un processus qui n'est pas pr6d6termin6 dans le temps et les demandes de connexion et les fins de communication se succ6dent /t une cadence presque al6atoire. I1 est done raisonnable de eonsi- d6rer un syst6me de connexion soumis /t des 6v6- nements purement al6atoires pour l'6tude du trafic. L'6valuation d'un tel syst6me se fair, par exemple, par la mesure de la fraction des demandes qui ne peuvent pas &re satisfaites et que l 'on appellera la probabilit~ de blocage, le module de service consid6r6 &ant /t appels perdus.

    Les blocages d6pendent des microconfigurations qui se suce6dent/t l'int6rieur du r6seau de connexion et de l'organe de eommande. Cette riehesse d'6v6ne- ments au niveau de la structure fine donne l ieu/t un processus al6atoire dont la connaissance est d'une grande utilit6 pour l'6tude de la qualit6 de l'6cou- lement de trafie du syst6me.

    Notre probl6me peut alors &re formul6 de la faqon suivante : eomprendre comment des param6tres observables int6ressants peuvent 6tre filtr6s d'une telle masse de d6tails. Bien entendu, il nous faudra passer par une phase de mod61isation qui comporte les trois hypoth6ses simplifieatriees suivantes :

    1) Les proeessus 616mentaires sont d'une part l 'appel point h point entre un 616ment libre de l'ensemble de d6part et un 616ment libre de l'ensemble d'arriv6e et d'autre part le raeerochage entre deux 616ments engag6s dans une conversation. II y a 6qui- probabilit6 dans le ehoix du couple appelant-appel6 aussi bien pour la crdation que pour la destruction de l'appel.

    2) A un moment donn6, nous supposerons que les processus de cr6ation et de destruction des appels ob6issent /l des lois de Poisson. Cela sera n6cessaire pour nous permettre d'6tablir au paragraphe 3.1. la relation entre le trafie demand6 et le trafic effeetivement 6cou16. Une telle hypoth6se qui corres- pond h des probabilit6s de cr6ation et de des- truction d'appels ind6pendantes du pass6 (ph6no- m6nes sans m6moire) est extrSmement utile sur le plan de la simulation, puisque la situation est compl6- tement d6crite par le nombre Z d'appels en cours et que nous n'avons pas besoin de consid6rer le d6roulement r6el du temps (nous mod61iserons simple- ment la succession des cr6ations et destructions d'appels sans avoir /t nous pr6occuper de la dur6e exacte entre deux 6v6nements).

    3) Outre le fait qu'un nouvel appel est suppos6 6tre dirig6 vers une sortie libre, on consid6re en plus le mod61e dit /t appel perdu. Dans ce mod61e un appelant qui se voit refuser son appel parce qu'il n'y

    a pas de circuit disponible oublie qu'il n'a pas obtenu satisfaction. On volt que cette hypoth6se est n6ces- saire pour conserver le caract~re poissonnien du processus.

    I1 en r6sulte que toutes les grandeurs moyennes sont des constantes dans le temps et que de plus la seule partie bloquante du syst~me est le r6seau de connexion. Nous excluons ainsi tous les probl6mes d'engorgement dus aux files d'attente et les compor- tements d'effondrement qui peuvent s'ensuivre lorsque le syst~me n'est plus capable de s'auto-adapter, par exemple l'impossibilit6 pour le ealeulateur de eom- mande de travailler en temps r6el.

    L'id6e maltresse de ee travail sera l'application du concept de limite thermodynamique bien eonnu par les physiciens [2, 3], dont la possibilit6 d'utilisation dans la th6orie du trafic t616phonique a 6t6 sugg6r6e par V .E . Benes [4]. Ce principe consiste /~ traiter tousles 6tats microscopiques du syst~me et/t augmen- ter sa taille jusqu'/t une dimension critique au-del/t de laquelle toutes les configurations singuli~res ont une probabilit6 d'apparition qui tend rapidement vers z6ro lorsque la taille du syst~me tend vers l'infini. Nous pr6ciserons par la suite de quelle fa~on il faudra effectuer cette limite.

    1. RI~SEAU DE CLOS A 3 I~TAGES (*)

    On utilise b matrices d'entr6e de dimension n x r pour le premier &age ; r matrices de dimension b x b pour l'6tage central ; le troisi~me &age &ant sym6- trique au premier (Fig. 1). Une connexion est carac-

    n=r b=b r ,n

    n" ~ I n

    n- ; in

    FIG. 1. - - R6seau de Clos h 3 6tages : N = rib. Three stage Clos network : N = nb.

    t6ris6e par une ligne d'entr6e appelante, une ligne de sortie appel6e et les 3 nombres suivants :

    m le nombre i E {1, 2 . . . . . b} num6ro de la matrice d'entr6e,

    - - le nombre k ~ {1, 2 . . . . . r} num6ro de la matrice centrale emprunt6e par l'appel,

    (*) Nous donnons ici une d6finition du r6seau de Clos h 3 6tages tir6e des r6f6rences [4], [20l, [21]. Signalons toutefois que les r6seaux de Clos sont parfois consid6r6s comme non-bloquants, ceci n'est bien entendu pas le cas dans notre 6tude.

    ANN. TI~Li~COMMUN., 37, n ~ 5-6, 1982 2/18

  • E. BONOMI. -- EXTENSIVITE POUR UN RESEAU DE CLOS ET PROBABILITE DE BLOCAGE 241

    le nombre j ~ {l, 2 . . . . . b} num6ro de la matrice de sortie.

    II faut remarquer que deux appels issus d'une m~me matrice d'entr6e ou dirig6s vers une mSme matrice de sortie, ne peuvent pas emprunter la mSme matrice centrale. De ce fait la donn6e de (i, k, j ) suffit pour caract6riser un chemin h l'int6rieur du syst6me et h aucun moment nous n'aurons besoin de connaitre, au sujet de l'entr6e appelante et de la sortie appel6e, plus que le couple (i, j). Nous voyons que la demande de connexion (i, j ) sera satisfaite s'il existe au moins une matrice centrale k libre pour cette connexion. Dans le cas contraire, nous parlerons d'6tat de blocage et la demande sera refus6e.

    On suppose que l 'on exploite ce type de r6seau l'aide d'une s61ection conjugu6e globale point d point, ici h deux &ages de liaisons, entre une entr6e et une sortie donn6es (une liaison servant h relier deux commutateurs de deux 6tages suceessifs).

    2. RI~SEAUX DE CLOS A I~TAGES MULT IPLES

    Consid6rons un r6seau de Clos h 3 6tages off n ----- r. Rempla~ons chacune des n matrices centrales par un autre r6seau ~t 3 6rages dont la structure est semblable au pr6c6dent (voir Fig. 2). Si nous partons de n p+I lignes d'entr6e, nous avons maintenant un r6seau h 5 6rages dont les deux premiers et les deux derniers 6tages sont identiques, form6s de matrices n n au hombre de b = n p par 6tage et dont l'6tage

    N N central est form6 de n 2 matrices ~-~ n~.

    Si on r6it6re cette d6composition avec cet 6tage central on passera d 'un syst6me de 5 h 7 6rages. En continuant nous obtiendrons un r6seau de 2 p ~ 1 6tages (p = 1, 2 . . . . ) form6s de matrices identiques de dimension n n (Fig. 2), sauf pour l'6tage central,

    N N lequel sera constitu6 de n p matrices n-~ 7" Dans le

    cas off N ----- n p+~, les matrices centrales seront de mSme taille que celle des autres 6tages.

    On supposera encore que ce r6seau h (2p q-1) 6tages de matrices est exploit6 en s61ection conjugu6e globale point h point, ~t 2p &ages de liaison entre une entr6e et une sortie donn6es.

    3. L IM ITE THERMODYNAMIQUE

    3.1. Syst6me dynamique.

    Nous appellerons ~volution la suite des 6tats du syst6me au cours du temps pendant la succession

    NxN

    nx n . N x ~- nxn n n

    9

    N N nxn ~-~x n ~ nxn

    ;. ., j 9 \ , \ 9

    fQi

    "J

    FIG. 2. - - Construction par r6currence d'un r6seau de Clos plusieurs 6tages.

    Recurrent construction of a multi-stage Clos network.

    al6atoire d'appels et de raccrochages. Ceci se traduira par le passage d'une configuration ~t une autre, ~ une fr6quence d6pendant du trafic demand6 T, le processus al6atoire r6gissant l '6volution &ant suppos6 stationnaire.

    Nous appellerons trafic demand~ le nombre moyen d'appels en eours que l 'on mesurerait si le syst6me 6tait non bloquant. On d6finit la probabilitd de blocage comme 6tant la fr6quence PB(t, T) des blocages observ6s pendant un intervalle de temps % = [0 ; t[ arbitrairement long. Cette probabilit6 d6pend de l ' interaction entre le processus d'arriv6e et la structure du r6seau.

    Soit N le nombre de lignes d'entr6e (et de sortie) que l 'on supposera &re des sources poissonniennes identiques. Consid6rons une des sources pendant l' intervalle de temps I = [~: ; 1: + dt[, alors la pro- babilit6 qu 'un appel soit cr66 en t ~ I vaut X dt si la source est libre et la probabil it6 qu'un appel en cours ~t l ' instant ,r disparaisse en t ~ I vaut ~t dt.

    Comme nous l 'avons d6j~t indiqu6 dans [1], cha- pitre 4.1., l '6volution du syst6me est done d6termin6e

    3/18 ANN. TI~LECOMMUN.) 37, n ~ 5- 6, 198

  • 242 E. BONOMI. -- EXTENSIVI'I~ POUR UN RESEAU DE CLOS ET PROBABILITE DE BLOCAGE

    par un processus de marche al6atoire off la suite d'6v6nements observ6s sont de 2 types (Fig. 3) :

    a) destruction d 'un appel par raccrochage avec la probabilit6 P~,

    b) tentative de cr6ation d 'un appel avec la pro- babilit6 P2 . Cette tentative d6bouche soit sur un 6chec, soit sur un succ6s.

    SOURCE 1 SOURCE 2 SOU RCE 3 SOURCE 4

    i i T ; 1 i L

    I ~ I l l ' ' , , I Ii I , l i t I I , I I I I ' I I I I I [ t , t t , , l [ i i , ] , i , t I

    COC OD ODCBC C DC DC 00BCO B t

    FIG. 3. - - Occupation de 4 sources au cours du temps. Blocage.

    Busy period for four traffic sources.

    Soit Z = Z(t) le nombre al6atoire d'appels en cours ~ l ' instant t, alors les probabilit6s que le pro- chain 6v6nement soit respectivement la destruction ou la cr6ation d 'un appel sont :

    [~Z Zct (1) Px = FZ+ (N- -Z)~- - N - -Z+ Z~'

    (N- - Z) ;~ (N - - Z ) (2) P2 = =

    ~Z+ (N- -Z)~ N- -Z+ Z0~'

    II faut noter que dans (1) et (2) nous nous d6bar- rassons de l 'aspect continu du temps et introduisons une discr6tisation de ce dernier caract6ris6e par un changement d'6tat ~ chaque &ape d6crit par la variable aMatoire Z(t). Ceci est possible uniquement parce que le processus est poissonnien ce qui, soit dit en passant, simplifie beaucoup la simulation en per- mettant de se d6barrasser du contr61e du temps. Toutefois, lorsque le nombre de sources est grand, la r6partition dans le temps discr6tis6 de la somme de tous les flux reproduit celle en temps r6el.

    Le processus Z(t) tend vers une 6volution limite stationnaire et done le nombre< Z(t) > tend vers une constante Z,q solution stationnaire. Cette solu- tion s'obtient en remarquant que vu le grand nombre de lignes (et on retrouve ici l 'hypoth6se thermo- dynamique), on peut admettre que les fluctuations autour d 'une valeur moyenne ~. un instant t, sont extrSmement petites par rapport au nombre d'appels en cours et l 'on peut alors supposer que PB 6volue uniquement en fonction du trafic moyen 6cou16.

    C'est finalement la m~me attitude que celle adopt6e par les physiciens qui travaillent sur des flux continus et non fluctuants quitte parfois A traiter A part des ph6nom6nes mettant en jeu des fluctuations anormales.

    Dans ces conditions, nous consid6rons que le processus Z(t) est une marche aMatoire et la moyenne d'ensemble < Z(t) > 6volue suivant le bilan :

    (i) cr6ations effectu6es pendant dt :

    Z (N- - < Z >) (1 - - Pa(< Z >)) dt,

    (ii) destructions pendant dt : F < Z > dr,

    d'o~ l'6quation d'6volution :

    d (3) dt = Z(N- - < Z>)

    (1 - -PB(< Z>)) - -F ,

    d l'6quilibre Z = Z=q et dt - - 0, ce qui

    entraine : N(1 - - PB)

    (4) Z=q = , + (1 - -Pa)

    Z,q est le trafic 6cou16 en r6gime stationnaire avec dans (4) : PB = PB (Z=q). En posant la condition Pa = 0, nous obtenons le trafic demand6 :

    N (5) T - 1 +~"

    Les 6quations (3), (4) et (5) caract6risent le processus discret simul6 qui reproduit fid6lement l'6volution al6atoire du syst6me. En initialisant le syst6me z6ro, Z(0) = 0 et en fixant T, nous obtenons le para- m6tre ct qui nous permettra de construire pas ~ pas la valeur de la variable Z. Dans la simulation num6- rique, nous tirerons au hasard un nombre y ~ [0, 1] :...

Recommended

View more >