Réflexions sur l’article de P. Boyer et G. Hebuterne intitulé: « Relations de conservation pour...

424

Correspondance R 6 f l e x i o n s sur I ' a r t ic le

de P. B o y e r e t G. H e b u t e r n e in t i tu ld :

RELATIONS DE CONSERVATION POUR UNE FILE D'ATTENTE AVEC DES CLIENTS IMPATIENTS,

(Annales des Tdldcommunications, mai-juin 1983, 38, n ~ 5-6, pp. 226-230)

par P. LE G A L L (CNET, DICET, AIN)

1. LE PROBLEME

La lecture de l 'art icle de MM. Boyer et Hebuterne est int6ressante sur un plan d ' ini t iat ion th6orique ~t l '6tude d ' un seul serveur, bien que les r6f6rences soient restreintes et r6centes.

Le probl6me des queues avec impatience est en fait tr~s impor tan t en ing6nierie du trafic de t616communi- cation. I1 est consid6r6 d6j~t depuis une cinquantaine d'ann6es, et toute son importance apparu t vers les ann6es 60, lors de la g6n6ralisation de l 'exploi ta t ion interurbaine automat ique.

Afin d '6viter des prises d 'organes de commande de dur6es anormales dues ~t des d6rangements ou des surcharges en trafic, c 'est en effet une r6elle n6cessit6 que d ' in t roduire des temporisat ions contr6- lant les attentes, se t raduisant finalement par l '6mission de la tonalit6 d 'occupa t ion vers l ' abonn6 demandeur pour le forcer ~ abandonner , ou 6ventuellement d 'une annonce parl6e l ' invi tant ~t refaire son appel ult6rieu- rement.

2. LES I~TUDES

Toutefois, les probl6mes pos6s par la r6alit6 tech- nique ne concernent pas un serveur, mais plusieurs serveurs. La difficult6 de l '6tude est beaucoup plus grande, et nous pensons utile d ' indiquer les r6f6rences des principales 6tudes connues par les ing6nieurs du trafic. Elles supposent des arrivdes poissonniennes, car c 'est la loi consid6r6e habituellement comme la plus r6aliste, et des durdes de service exponentielles, hypoth6se choisie pour la commodit6 des calculs, bien que peu r6aliste.

2.3 Cas GI/G/s (*) et impatience g6n6rale.

En fair, on a g6n6ralement utilis6 une horloge unique telle que la dur6e de l ' impatience est al6atoire- ment et uniform6ment r6partie entre deux valeurs fixes. Par exemple, les ing6nieurs <~ commutants )) ont l 'habitude de dire que l 'a t tente tombe sous le contr61e de la << came 15s-30s >>, dans le cas o/a ces deux valeurs limites sont respectivement 15 et 30 s.

La difficult6 de l '6tude est alors la m~me que dans le cas d 'une fonct ion de r6parti t ion quelconque pour la dur6e al6atoire d ' impat ience . Les 6quations du processus dans le cas G I / G / s ont 6t6 6crites en 1962 par F. Pollaczek [7], mais elles ne sont pas encore r6solues, d 'o~ un centre d'int6rSt pour les jeunes chercheurs.

3. L ' E X P ~ R I E N C E

La th6orie ne donnan t finalement pas les moyens de travail n6cessaires, l ' ing6nieur s 'est tourn6 vers l 'observat ion des appels rejet6s par cette impatience. C 'es t que les << disciplines >> de queues r6ellement utilis6es sont complexes et le trafic est particuli6rement instable dans les 6quipements communs de commande : le trafic r6el est << vivant >~, suivant la terminologie anglaise.

Le param6tre global g6n6ralement observ6 est celui (compl6mentaire) donnan t la proport ion d 'appels tax6s (r6ception du signal de r6ponse), sommant tous le s cas de r6ussite. I1 est utilis6 par l 'Administra- tion frangaise sous le nora de taux d'efficacit6 et, peu ~t peu, est utilis6 pa r les autres Administrations sous des noms divers : taux de r6ponse, taux d 'about is- sement.

2.1. Impatience de dur6e exponentielle 4. LA RECHERCHE

Ce cas fut pos6 b. l 'or igine par les 6tudes d'attente de tonalitd d ' invi ta t ion ~t num6roter : cf. [1, 2] et [3].

2.2 Impatience de dur6e constante

Nous esp6rons que ces brefs commentaires peuvent ~tre utiles pour orienter les esprits de jeunes chercheurs en ing6nierie de trafic, et pour les documenter.

L' in t roduct ion de temporisat ions propres ~ certains organes de c o m m a n d e a donn6 lieu aussi ~t des 6tudes assez anciennes : cf. [4, 5 et 6].

(*) Cette notation habituelle, due ~t Kendall, d6signe le cas de s serveurs, recevant un processus d'arriv6es r6g6n6ratives g6n6ral (GI : General Input) et les dur6es de service ob6issant

une loi g6n6rale.

ANN. TI~LI~COMMUN., 38, n ~ 9-10, 1983 1/2

CORRESPONDANCE 425

BIBLIOGRAPHIE

[1] PALM (C.). Etude des d61ais d'attente. Ericsson Technics, Stockholm (1937), 5, n ~ 2, pp. 39-56.

[2] PALM (C.). Research on telephone traffic carried by full availability groups. Tele (6dition anglaise), Su6de (1957), n ~ 1, pp. 1-107.

[3] CLOS (C.), WILKINSON (R. I.). Dialing habits of telephone customers. Bell. Syst. tech. J., USA (1952), 31, pp. 32-67.

[4] ST6RMER (H.). Archiv d'elektr. Uebertragung (1956), 10, pp. 58-64.

[51 BARRER (D. Y.). Queueing with impatient customers and indifferent clerks. Opns. Research, USA (1957), 5, pp. 644- 649.

16] BARRER (D. Y.). Queueing with impatient customers and ordered service. Opns Research., USA (1957), 5, pp. 650-656.

[7] POLLACZEK (F.). SHF une th6orie unifi6e des probl6mes stochastiques soulev6s par l'encombrement d'un faisceau parfait de lignes t616phoniques. C. R. Acad. Sci., Fr. (4 juin 1962), pp. 3965-3967.

REPONSE DES AUTEURS

Les remarques de M. Le Gall nous incitent /l pr6ciser quelques points de d6tail concernant l 'article pr6cit6, qui nous semblent de nature/~ clarifier le d6bat.

1) I1 ne faut pas donner / l l 'article plus d ' importance qu' i l n 'en veut avoir. Ce n 'es t absolument pas une synthbse sur le probl~me des files avec impatience. I1 ne s 'agissait pour nous que d '6tendre la validit6 de r6sultats ant6rieurs au cas de lois d'arriv6es g6n6- rales, en mont ran t la puissance et la simplicit6 d 'une approche rdgdndrative ; il va de sol dans ces conditions que la bibliographie, qui ne concerne que le contenu de l 'article, est forc6ment tr6s incompl6te. N6anmoins, la r6f6rence [BaH 81] de l 'article donne des 616ments bibliographiques assez complets (les r6f6rences [6] et [7] de M. Le Gall y sont cit6es). Signalons 6galement pour compl6ter l 'ouvrage classique de Syski [Sys 60], qui analyse assez compl6tement les t ravaux ant6rieurs /t 1960.

2) C o m m e le dit for t jus tement M. Le Gall, le probl6me de l ' impat ience est tr6s impor tant en ing6- nierie du t616trafic. I1 n 'emp~che qu' i l n ' a jamais vraiment 6t6 abord6 (sauf peut-~tre dans l '6tude de St6rmer, r6f6rence [4] ). I1 est significatif/t cet 6gard de constater que le Congr6s de T616trafic n ' a jamais accueilli une seule communica t ion sur le sujet (h la connaissance des auteurs tout au moins). L 'ensemble des r6f6rences cit6es par M. Le Gall et nous-m~mes (soit 15 articles) repr6sente probablement un inven- taire exhaustif de la b i b l i o g r a p h i e : soit environ un article t o u s l e s trois ans !

C 'es t assez dire q u ' o n est en pr6sence d 'un domaine d '6tude difficile, mSme en voulant se limiter/~ la file /t un serveur.

3) Faut-il 6tudier un syst6me /~ un ou /t plusieurs serveurs ? Dans le cas d ' une file /t s > 1 serveurs, il faudra en prat ique venir au cas simplifi6 d'arriv6es poissonniennes et de lois de service exponentielles.

Pr~cisons qu ' i l s 'agit de lois simplifi6es, q u ' o n ne peut justifier autrement que par les r6sultats qu'elles autorisent. L '&ude du syst6me markovien h s serveurs et loi d ' impat ience gkndrale a 6t6 faite enti6rement (au plan des temps d 'a t tente et du rejet) dans la r6f6rence [BaH 81], ofz est 6galement 6voqu6e une applicat ion h u n probl6me r6el de t616trafic (fonction- nement d ' un PABX, et attente devant les op6ratrices) ; signalons que le m6me probl6me a 6t6 6galement r6solu, de fa~on ind6pendante, dans la r6f6rence [HaS 80], dont nous n ' avons pris connaissance que tr6s r6cemment. I1 nous semble qu ' i l y a 1/t le premier r6sultat impor tan t depuis ceux de St6rmer : la raise en 6quation de Pollaczek [7] est une impasse au plan de l 'ing6nierie du trafic.

Pour le cas h u n seul serveur, on peut au moins rel~cher l 'hypoth6se de lois de service exponentielles : voir [BaH 81]. Est-ce une &ude utile ? Pour notre part , notre r6ponse est affirmative bien stir. Remar- quons q u ' u n livre d 'environ 700 pages a 6t6 consacr6

la file ~ un serveur (<< The single server queue >> par J. W. Cohen). Le t616trafic ne se r6duit pas au probl6me (tr6s important) du calcul des faisceaux ou d 'o rganes communs. Les probl6mes pos6s par les architectures d ' au tocommuta teu r s modernes, par les protocoles de transmission (HDLC, CCITT n ~ 7, etc.) aboutissent naturellement /t des mod61es de files h un serveur, avec clients impatients (impatience humaine, temporisation).

I1 reste n6anmoins que le t ra i tement de la file h s serveurs, /l lois d 'arriv6e et de service g6n6rales (GI /G/s , dans la notat ion consacr6e) avec impatience g6n6rale reste /t faire, et que l ' explora t ion du cas s = 1 ne donne pas d ' a rme pour l ' aborder . D 'au t res m6thodes seraient n6cessaires, qui d 'ai l leurs r6sou- draient le probl~me <r plus simple >> de la file G I / G / s sans impatience.. .

BIBLIOGRAPHIE

[BaH 81] BACCELLI (F.), HEBUTERNE (G.). On queues with impatient customers Performance 81. North Holland Ed, Amsterdam (1981).

[HaS 80] HAUGEN (R. B.), SKOGAN (E.). Queueing system with

stochastic timeouts. IEEE Trans. COM, USA (1980), 28, n ~ 12, pp. 1984-1989.

[SYS 60] SYSK[ (R.). Introduction to congestion theory in telephone systems. Oliver and Boyd, London (1960).

2/2 ANN. T~L~COMMUN., 38, n ~ 9-10, 1983