DE OPTIMALISATION DES R~,,SEAUX DE TRANSMISSION

DONNI~ES A STRUCTURE MULTIPOINT, programme REMU par

J~rome GRASSIN IngOfieur des t~l~communications *

RI~SUM]~.- AprOs avoir prdsenl~ Ies aspects physiques du rdseau it structure muIlipoint l'auteur donne une m~thode d'optimalisalion du calcul des r~seaux de transmission de donndes it structure mullipoint. It proc~de tout d'abord it un d~coupage des terminaux en ensembles raccroch~s it une seule ligne multipoint. Pour chacun de

ces ensembles, le rdseau est ensuite optimaliss

PLAn. - - Introduction. A : Carac t~r i s t iques d ' u n r~seau m u l t i p o i n t 1. Notion de r~seau multipoint ; 2. Terminal ou nnild de contr6le ; 3. Liaisons utilisges et tarification ; 4. Rdseaux it plusieurs C.T.I . B : O p t i m a l i s a t i o n des r6seaux m u l t i p o i n t s 1. But du programme ; 2. Donndes el rdsultats ; Traitement initial des donndes ; 4. Rdseau optimal; 5. Mdthodologie adopt~e ; 6. Arbre minimal et ensembles Ek; 7. Dd.termination du rdseau multipoint; 8. Procddure sp~ciale; 9. Fin de I'algorithme; 10. Rdsultats el conclusions.

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

Devan t le ddveloppement tr~s rapide des projets de r~seaux de t ransmission de donn~es fondus sur la location mensuelle de liaisons sp~cialis~es ~ l 'Adminis- t ra t ion des P.T.T., il a paru n~cessaire d 'opt imal iser

la configuration des r~seaux afin d 'ob ten i r un prix de location minimal . L 'Admin i s t r a t ion est ainsi

capable de conseiller ses clients et de leur donner rap idement le cofit d ' un projet de r~seau.

La comparaison des coflts respectifs de tr~s nom- breuses configurations devient alors possible, ce qui ne l '~tai t pas lorsque les calculs ~taient effectu~s manuel lement .

Dans le prdseut article il n 'es t quest ion que des r~seaux mul t ipoints . Les r~seaux avec concentra teurs et ceux avec mult iplexeurs feront l 'ob je t d 'une prochaine publicat ion.

Dans la premiere patt ie, nous pr~sentons les aspects physiques du r~seau /~ s t ructure m u l t i p o i n t ; la m~thode de calcul est d~crite dans la deuxi6me part ie et est suivie des r~sultats obtenus.

A. C A R A C T I ~ . . R I S T I Q U E S D ' U N RI~.SEAU M U L T I P O I N T

1. N o t i o n de r 6 s e a u m u l t i p o i n t .

Consid~rons un r~seau compor tan t un centre de t r a i t emen t de 1 ' information ou C T I et plusieurs

te rminaux . U n premier type de rdseau qui v icn t t ou t de suite i~ l 'espri t consiste h relier chaque te rminal

au C T I par une ligne directe. On obt ien t un r~seau appel~ point it point.

Cette solution peut s 'avdrer fort coflteuse si d 'une par t les t e r mi na ux sont tr~s dloign~s du C T I, et st, d ' au t re part , chacun d 'eux n 'ut i l ise sa ligne que pe nda n t une tr~s faible part ie du temps.

En pa r tagean t une m~me ligne entre plusieurs t e r mi na ux on pout am~liorcr l 'u t i l i sa t ion de la ligne et par l~ le coflt du r~seau.

La figure 1 mont re un exemple de rdseau mult i - point . Les t e r mi na ux sont localis~s en 1, 2, 3, 4.

4

3

Fla. 1. - - R~seau multipoint comportant quatre terminaux situds respectivement en 1, 2, 3, 4.

Les points tels que A, B, C sont appel~s points de diffusion. E n A, B, C sont install~s des amplif icateurs diffuseurs et des correcteurs de phase car on effectue une d~modulat ion de phase et une remodula t ion de phase lorsque la ligne se divise.

A fin que la qualit~ de la t ransmiss ion soil suffisante, on ne fern jamais plus de trois diffusions en cascade depuis le C T I jusqu 'h un te rminal quelconque. C'est ce que nous appelons la cont ra in te des trois

points de diffusion, $1. Comme il est impossible dans

une s t ructure mul t ipo in t d '~mettre s imul tan~ment h par t i r de plusieurs te rminaux , on a recours i~ une

procddure d ' in ter rogat ion (polling). Le premier ter- minal qui a r~pondu aff i rmativement t r ansme t un

* Au CNET, groupement INFORSIAT[QUE ET TRANSMISSION DES DONNEES, d6partement CALCULATEURS I~LECTRONIQUES ET SYST F.I~I ES.

- - 11 - -

2 / 8 J. ORs [ANNALES DES TI~L~C0MMUNIC~TION$

message ou re~oit un message. I1 existe de nombreuses procOdures d ' i n t e r r o g a t i o n [1].

2. T e r m i n a l ou unit6 de contr&le.

B. O P T I M A L I S A T I O N D E S P ~ S E A U X M U L T I P O I N T S

Nous avons parl~ de t e rmina l mais cet te not ion est extens ib le ~ une unit6 de contrSle gOrant plusieurs t e rminaux .

On reprOsente ici le t ra f ic issu d ' un t e rmina l e t celui destin~ h ce t e rmina l en provenance du C T I pa r un seul pa ram~t re que l 'on appel le la charge. Ce peu t 6tre pa r exemple le nombre de caract~res t rans- mis et regus p e n d a n t l 'heure charg~e.

De mOme on calcule la charge max ima le que peu t suppor te r la ligne, cet te charge est exprim~e dans la mOme uni t6 que la charge des t e rminaux . (Le rOseau est en t i~rement rOalis6 avec des lignes fonc t ionnan t tou tes h la mOme vitesse de t ransmiss ion. )

i . But du programme.

Le p rogramme (REMU) a pour bu t de d~terminer un rOseau sa t i s fa isant la con t ra in te des t rois po in ts de diffusion et don t le coot soi t quasi opt imal .

E t a n t donn6 la complexi t6 du probl~me il n ' a pas dt~ possible de t rouver le r~seau op t imal , n~anmoins la m~thode heur is t ique adoptOe donne des r~sul ta ts sa t isfa isants .

2. Donn6es et r6sultats.

3. Liaisons utilis6es et tarification.

H u i t types de lignes sont proposOs ~ l ' u t i l i sa teur e t voici les qua t re plus commun~ment employOs :

a) ligne t~lOgraphique 200 bauds ,

b) ligne tOlOphonique 2 ills,

c) l igne tOl~phonique 4 ills qual i t6 normale ,

d) ligne t~lOphonique 4 ills qual i t~ supOrieure.

L a loca t ion de la l igne est fa i te au mois et son coot est une fonct ion de la d is tance h vol d 'o iseau s~paran t les deux villes ~ relier.

La figure 2 donne l ' a l lu re de la fonct ion de coo t pour une l iaison du t y p e c . Les aut res fonct ions on t sens ib lement la mOme forme.

1685

1084 [

/ t I t ~'~ I I I ~ cl en km

35 50 100 km

FzG. 2. - - CoOt d'une liaison du type h 4 ills qualit6 normale.

Uric nouvel le t a r i f i ca t ion a ~t6 propos~e dans laquel le le coo t sera i t cons t an t au-del~ de 350 km.

4. R6seaux /L plusieurs centres de traitement de Finformation.

On p e u t t o u t aussi b ien concevoir un r6sesu p lus ieurs C T I. N6anmoins , nous ne par le rons pas dans cet a r t ic le du r~seau en t re divers C T I.

On dis t ingue t rois groupes de donnOes.

a) Le nombre de C T I e t de centres d ' ampl i f i ca t ion du rOseau des lignes ~ grande d is tance ou C A, ainsi que leur emplacement .

b) Les caractOrist iques des lignes de t ransmiss ion : le t y p e de l igne choisi e t la charge m a x i m a l e tolOrOe sur une ligne.

c) Les param~tres relat i fs aux unit~s de contrOle ou aux t e rminaux , c'est-$t-dire le centre de groupe- m e n t ou C G de r a t t a c h e m e n t , la d i s tance h ce C G et la charge de l 'uni t6 de contrSle ou du te rmina l .

D ' au t r e s donnOes telles que les l iaisons ent re C A son t eonteuues clans des fichiers utilis~s pa r le pro-

g ramme.

Les rOsultats se prOsentent sous l a - f o r m e suivante . Pour chaque C T I on dOcrit success ivement les diffOrentes lignes mul t ipo in t s qui lui sont ra t tach~es , le coo t de chacune d 'e l le e t le coo t global du rOseau.

3 . T r a i t e m e n t i n i t i a l d e s d o n n 6 e s .

Les t e r m i n a u x ou les uni tds de contrOle sont t o u t d ' a b o r d rat tachOs au C G le p lus proche , lequel centre do g roupemen t est ~ son t o u r r a t t ach6 au C A l e

plus proche.

Tou t se passe donc comme si les uni tds de contrOle 6 ta lent localisOes dans des C A, e t p a r consOquent la

cons t i tu t ion du rdseau se fa i t en p a r t a n t des C A.

P a r ail leurs, dans le cas de plusieurs C T I, on affecte chaque C A, mun i de ses unitOs de contrSle,

un C T I. Le ohoix p e u t so faire h p a r t i r de la dis- t ance ~ vol d 'o iseau ou selon un cri t~re d ' a p p a r t e n a n e e

une m~me rOgion, p a r exemple .

Alnsi le cas d ' un rOseau ~ plusieurs C T I se rame- n a n t ~ eelui de ptusieurs rdseaux ~ un seul C T I, nous ne par le rons dOsormais que de ce t te derni~re conf igurat ion.

- - 1 2 - -

t. 27, n ~ 1-2, 1972] O P T I M A L I S A T I O N D E S R I ~ S E A U X D E T R A N S M I S S I O N 318

4. R ~ s e a u opt imal .

Le r~seau optimal (*) permet de d~gager des ensembles de points dont la charge totale est inf~rieure ou ~gale h la charge maximale CHAMAX tol~r6e sur une ligne. Chacun de ces ensembles est reli~ au C T I par une seule ligne et le r~seau correspoadant satisfait la eontra inte $1.

5. M 6 t h o d o l o g i e adopt6e .

Un essai de formulat ion h l 'a ide d ' u n module lin~aire en nombres entiers s 'est r~v~16 infruetueux, car le nombre de variables ~tait prohibit if et ne per- me t t a i t pas d 'envisager un temps de t r a i t emen t acceptable sur ordirlateur.

Ne pouvan t t ra i ter d i rectement le probl~me dans sou ensemble, on a cherch6 h le f ract ionner en deux parties en u t i l i san t une m~thode heurist ique.

a) On s'efforce de d~terminer des ensembles tels

que E l , E2, E a . . . . (Fig. 3), chaeuu d 'eux a ya n t

b) Suecessivement pour ehacun des ensembles d6termin6s, figure 3, on caleule u n r6seau au meil leur eoht, sat isfaisant la eont ra in te S1.

6. Arbre minimal et ensembles E~ (Fig. 3).

a) Ddfinitions.

Soit Q le nombre de t e rminaux on d 'uni t~s de contr61e situ~s au nceud (*) i. On dit que le nceud ] est faeultat i f si tj = 0. Dans le eas eontraire, il est dit obligatoire (**).

Le graphe des liaisons entre nceuds n ' ~ t a n t pas

complet, on est parfois oblig~ de passer par un ou plusieurs noeuds intermddiaires pour relier u n couple i, ].

Soit n 1 le nombre de noeuds obligatoires. On etlerche h construire un arbre min imal rel iant ces nx nceuds en u t i l i san t ~ventue l lement certains des (N -- nl) noeuds faeultatifs.

Ce probl~me bien couuu sous le nom de probl~me de Steiner est soluble ~ l 'aide de la p rogrammat ion

/ ? \ / I "~ E~ I I .S ./ . \

I ' ,, ," I, ' ,

\ \ 1 /

\ \ 2 I / /

ez Fro. 3. - - Contiguration d'un r~seau optimal; les valeurs en regard de chaque nccud indiquent le nombre d'unit6s de contr61e en ce nmud.

une charge totale aussi voisine que possible de CHAMAX et tels que les C A qu'ils con t i ennen t soient proehes (h vol d'oiseau) les uns des autres.

Des m6thodes telles que l 'analyse factorielle sont certes tr6s appropri6es pour t ra i ter le probl~me a), mais une m6thode heuris t ique foud6e sur un calcul d 'a rbre min imal (**) s 'est av6rde plus favorable.

L 'a rbre min imal permet en effet de connecter des

points g6ographiquement voisins. E n outre, il pr6- sente l ' avan tage comme nous le verrons plus loin de fournir une tr~s bonne base de d6part pour r6soudre b).

(*) L'optimum n'est pas n~cessairement unique. (**) Au sens de la th~orie des graphes.

dynamique [2]. Malheureusement pour de gros rdseaux (N >/ 10), ee qui est le eas dans cette ~tude (N = 200), la r~solution devient imprat icable et tr~s cofiteuse, et on pr~f~re r~duire progressivement l ' a rbre min imal construi t h par t i r des N nceuds.

b) Rdductions de l'arbre.

Dans l ' a rbre min imal les nceuds faeultatifs au ron t un degr~ ~gal ~ 1 (e'est-h-dire seront pendants ) ou

(*) On parlera indistinctement de n(~ud ou de C A. Ils sont num~rot~s de 1 ~t N.

(**) Le C T I iait partie des nceuds obligatoires m~me si t I = 0.

- - 13 - -

4 / 8 J . GRASSIN [ANNALE$ DES WIlL'COMMUNICATIONS

s u p ~ r i e u r h 1. U n n c e u d f a c u l t a t i f p e n d a n t e s t d o n c

i nu t i l e e t e s t d o n c s u p p r i m 6 . I1 en es t de m ~ m e des

a u t r e s nceuds f a c u l t a t i f s qu i d e v i e n n e n t p e n d a n t s p a r

su i t e de la s u p p r e s s i o n d ' u n a u t r e nceud f a c u l t a t i f .

R e s t e le cas des nceuds f a c u l t a t i f s de degrd p ~> 2.

So i t i o u n t e l n c e u d ; sa s u p p r e s s i o n cr~e p c o m p o -

s a n t e s c o n n e x c s Z 1 , Z 2 , . . . , Z p . Af in de c o n s e r v e r

la c o n n e x i t 6 d u r6seau , il f a u t d o n c r a j o u t e r p - - 1 a rcs ,

l I , l 2 , . . . , I p _ 1 , sans c r6er de cycles , ceci p o u r p r e s e r v e r

la s t r u c t u r e d ' a r b r e e t de m a n i ~ r e que la s o m m e

s = 11 + l~ + ... + l p _ 1 so i t m i n i m a l e .

9 S

1 3

3 4;

6 2 1

Fta. 4. - - Graphe d 'un r~seau h 8 noeuds. On donne, tableau, I la matrice des arcs existants (une case vide6 qui vaut "h une

absence d'arc).

2

9 5

1 3

3 8

5 4

6 -7

S i s e s t i n f6 r i eu re h la s o m m e des l o n g u e u r s des

a rcs issus de i o d a n s l ' a r b r e p r 6 c 6 d e n t , il e s t b d n 6 f i q u e

de s u p p r i m e r i o , s i n o n i o e s t c o n s e r v 6 .

E x e m p l e . Soi t le g r a p h e de la f igure 4 ; le t a b l e a u 1

d o n n e la m a t r i c e des l i a i sons .

TABLEAU I.

Matrice des liaisons du r~seau de la figure 4.

0 9 11 3 12 23

9 0 5 16

5 0 6 4

11 6 0 8 13

3 16 0 17

12 8 0 2 5

13 2 0 10

23 4 17 5 10 0

Le r~seaU c o m p o r t e 8 nceuds N = 8, e t les n c e u d s 4

e t 5 s o n t f a c u l t a t i f s (F ig . 5a).

On c o m m e n c e p a r 61iminer le nceud 5 d u degr6 1

(Fig . 5b).

L a s u p p r e s s i o n de 4 cr6e d e u x c o m p o s a n t e s

c o u n e x e s Z 1 = { 1 , 2, 3, 8 } e t Z 2 = ( 6 , 7 } (Fig . 5c).

L a p lus c o u r t e l i a i son p e r m e t t a n t de r 6 t a b l i r la

c o n n e x i t 6 es t la l i a i son 6-8 de l o u g u e u r 5 (Fig . 5d).

L a l o n g u e u r de l ' a r b r e d i m i n u e de (6 + 8) - - 5 = 9.

2

9 5 1

4 3 8

6 7

a b

2

el s .7 8

Z2 c d

FIG. 5. - - Application de la m~thode de r6duction du graphe de la figure 4 :

a) arbre minimal de d6part, L ~ 37; b) apr~s 61imination du n(~ud 5, L -- 34 ; c i 61imination du nceud 4, S -- 5 ~ 6 ~- 8 ~ 14; d) arbre rdduit, L ~ 25.

1 4 m

t. 27, n o~ 1-2, 1972] OPTIMALISATION DES R]~SEAUX DE TRANSMISSION 5/8

La r~duc t ion de l ' a rb r e se t e r m i n e soi t pa r 6pui-

s e m e n t des nceuds facu l t a t i f s , soi t pa rce que la sup-

press ion des noeuds f acu l t a t i f s r e s t an t s n 'am61iore

pas la l ongueu r de l ' a rb re .

c) Calcul des ensembles Ek.

On c o m m e n c e pa r o r i en te r l ' a r b r e r6du i t en consi-

d6 ran t que le C T I es t la racine .

D a n s l ' e x e m p l e p r6c6den t en a d m e t t a n t que le

C T I soi t si tu6 en 8 on a u r a i t l ' o r i e n t a t i o n s u i v a n t e

(Fig. 6).

2

Fw,. 6. - - Orientation de l'arbre r6duit si le C T I est sit@ en 8.

C h a q u e nceud p o i n t e done vers son p~re sauf le

C T I qu i ne p o i n t e vers a u c u n nceud.

On calcule la charge cumul6e , CHATOT, en c h a q u e

nceud de l ' a rb r e r6dui t , en a j o u t a n t h la cha rge d ' u n

nceud la charge cumul~e de tous ses descendan t s .

On d6mar r e la p roc6dure h p a r t i r des nceuds pen-

dan t s , off CHATOT est 6gal "~ la cha rge du nceud, en

r e m o n t a n t vers le C T I. Posons :

11 = {i[CHATOT(i) ~< CHAMAX}

12 = {i[CHATOT(i) > CHA,~IAX}.

On d6 te rmine t o u t d ' a b o r d le nceud k te l que :

Cm = CHATOT (k) = m a x { CHATOT ( i) }.

i @I 1

On p e u t alors isoler un e n s e m b l e E~ eons t i t u6 du

noeud k e t de tous ses de scendan t s , et te l que la

cha rge t o t a l e Cm de ee t e n s e m b l e soi t au plus 6gale h CHAMAX.

I1 est par fo is poss ible de t r o u v e r un ensemble Ek

de cha rge t o t a l e sup6r ieure en e x p l o r a n t les nceuds i,

i ~ I~ . Soi t k un de ces nceuds, k 1 , k ~ , . . . , k p les

p d e s c e n d a n t s de k e t soi t H l ' e n s e m b l e fo rm6 p a r k

e t ses p d e s c e n d a n t s imm6dia t s . H k = {k, k 1 , . . . , kp} .

Associons ~. k sa cha rge p rop re d e t a u x k i leur cha rge

cmnu l6e d~ ; on o b t i e n t ainsi S k = (d, d 1 , d 2 , . . . , dp} .

On d 6 t e r m i n e la c o m b i n a i s o n d '616ments de Sk

te l le que la s o m m e C'k de ces 616ments soi t la p lus

g r a n d e poss ible e t inf6r ieure ~ CHA~AX. On pose

C i = m a x C'k k ~ I 2

et si la r e l a t ion CM > Cm est v~rifi6e, on a d6 t e rmin6

un ensemble Ek mei l l eu r an p o i n t de r u e de la cha rge to ta l e .

E x e m p l e . D a n s le r6seau h 8 po in t s de la f igure 7,

C T I e s t s i tu6 en 5. Les f igures 7 r e p r 6 s e n t e n t l ' a r b r e

m i n i m a l e t en c h a q u e nceud on repr6sen te , la cha rge

p ropre , f igure 7a, ou la charge cumul6e , f igure 7b,

pa r un h o m b r e 6cri t eu i t a l ique .

8 . 7 0

1 100 /

z2o J6

D

7" I - 100 /

22O '(6 b

~ \ \ ' k

l"m. 7. --- Principe du cumul des charges. a) Le C T I est situ6 en 5. A chaque nceud est assoei6e

sa propre charge (exemple : 110 pour le nceud 4). b) Repr6sentation des nceuds affect6s de leur charge

cumul6e. c) Isolation du meilleur ensemble.

$ ~ 7 0

On p r e n d CHAMAX = 500. On vdrif ie que :

I 1 = {1, 2, 3, 6, 7, 8}, 12 = {4, 5},

Cm = 250, c o r r e s p o n d a n t h k = 3.

H4 = {4, 3, 6},

S 4 = {110, 250, 220}.

L a me i l l eu re c o m b i n a i s o n est (250, 220) --~ C' 4 = 470 ; e t p o u r

H 5 = { 5 , 4 , 7 , 8 } ,

S~ = {0, 580, 150, 70},

ee t t e me i l l eu re c o m b i n a i s o n est ( 150 ,70 ) -+ C' 5 ~ 220.

On en d6du i t : CM = 470.

On p e u t done isoler l ' e n s e m b l e E 4 off le nceud 4

es t d6doubl6 en 4' e t 4", 4 ' a p p a r t e n a n t h E 4 poss~de

m a i n t e n a n t une cha rge nul le , pu i sque 4 ne fa i r pas

- - 1 5 - -

6/8 J . ORASSIN [ANNALES DES T~LI~eOMMU~ICATIONS

partie de la meilleure eombinaison, la charge propre

de 4 est douc affeetOe h 4" (Fig. 7c).

7. D6terminat ion du r6seau mult ipo int pour u n ensemble E~.

A y a n t d~termin~ u n ensemble Ek , il reste h relier eet ensemble au C T I par une liaison direete de

mani~re h satisfaire la eontra inte S1. On remarquera que l ' a rbre min imal de E~ est

eonsti tu~ des memes ares que eeux re l iant les noeuds de Eo dans l ' a rbre min imal du r~seau global.

Dans le eas de la figure 7e, le nceud 4' devient un nceud faeultat if , et par eons~quent on peut 6ventuel-

l ement rdduire l 'arbre. Apr~s avoir elass~ les nceuds de Ee par distance

eroissante au C T I (*), on teste si, en re l iant le pre- mier noeud au C T I, on ob t ien t u n r~!seau vOriflant S1. Dans l 'affirmative, on arr~te la procedure, et on ~limine les nceuds de Ek(**), sinon on reeommenee avee

le deuxi~me nceud et ainsi de suite. S'il est impossible d 'ob ten i r un r~seau sat isfaisant S1 on doit alors adopter une procedure sp~ciale

d~eritc au paragraphe 8. Reprenons l 'exemple prde~dent : sur ehaque are

on a inserit le eofit de la liaison (Fig. 8a) et le tableau I I donne la matr iee des eohts des liaisons.

\ / 6

ff

On commence par 61iminer le noeud 4' (Fig. 8b). Les cofits de liaison d~y sont les suivants :

d15 = 44, d~5 = 39, d35 = 31, d65 = 3 0 ;

e t o n d o n n e e n o u t r e : t 1 = 2, t 2 = 1, t a : 2, t 8 ~ 4. Apr~s classement on obt ien t l 'ordre su ivan t :

(6, 3, 2, 1) et en re l iant 6 h 5 on obt ien t u n r~seau v~rifiant $1 avec diffusion en 2, 3 et 6 (Fig. 9).

1

0

I 3 5

TI

6

FIa. 9. - - Rdseau m u l t i p o i n t r e l a t i f au sous-ensemble E 4.

8. Proc6dure sp6ciale.

Dans le r oh il est impossible de satisfaire la cont ra in te S1 ~ l 'aide de l ' a rbre min imal prOeOdent, il faut reprendre le probl~me concernant l 'ensemble Ek.

Nous allons essayer de construire d i rec tement un

1

0 3

IS

2

6

b Fro. 8. - - a) Sous ensemble E 4 a v a n t rOduction de l ' a rbre co r r e spondan t L = 47.

b) E 4 apr~s l'61imination du nceud 4 ~, L = 42.

TABLEA~ II.

Mat r ice des coflts des l ia isons.

0 21 10 44

21 0 15 i39 35

10 15 0 8 31 17

8 0 22 14

4 4 39 31 22 0 30 10 4

35 17 14 30 0

10 0 18

4 18 0

rOseau vOrifiant S1, les not ions de centre d ' u n graphe e t de rayon sont supposOes eonnues [3, 4]. Pour cela, apr~s avoir dOtermin6 un arbre pseudo-minimal rOalisable, c'est-~-dire vOrifiant S1, nous essaierons d'am61iorer cet arbre t o u t en gardan t une s t ructure

rOalisable.

8.1. Construction de l'arbre pseudo-minimal.

PrOcisons tou t d ' abord quelques dOfinitions.

DEfinition. On appelle ordre d ' u n nceud le hombre de points de diffusion sOparant ce nceud du C T I, ee nceud 6 tan t inclus lui-meme s'il comporte une

diffusion.

(*) E t a n t donn6 la forme de la fonct ion du cofit, le clas- s emen t selon la d i s t ance ou selon le cofit de l ia ison est le mgme.

(*,*) Voir w 9.

Exemple (Fig. 10).

On suppose que Q = 1, V i ~ 2, l 2 = 3, alors on a

OI~DRE = (1, 2, 2, 2, 3, 3, 3).

16

t. 27, n ~ 1-2, 19721 O P T I M A L I S A T I O N D E S R t ~ S E A U X D E T R A N S M I S S I O N 7/8

2 2 ~ . 36

3"?

FI(L 10. - - La valeur de l'ordre des nceuds est en italique.

8.2. Ameliorat ion de l 'arbre p seudo -min ima l .

Dans le cas o/1 l 'arbre pseudo-minimal cont ient des liaisons fictives, l 'exp6rience nous a condui t h adopter la procedure suivante.

Pour plus de clart6, prenons un exemple, celui de la figure 11.

Soit deux nceuds ~ et ~ reli~s par un arc fictif

dans APM, ~ ~tant le p~re de ~r et soit y le nceud

su ivant imm~dia tement :r sur le plus court chemin

I /

\ I 1~~, ~ P 2 P

P2

a b

FIG. 11. - - Exemple d'application de la proc6dure sp6ciale; les axes fictifs sont inscrits en pointill6s.

On rappelle tou t d 'abord br i~vement l 'a lgor i thme de Pr im [3, p. 23], pour la const ruct ion de l ' a rbre minimal .

On prend un nceud que l 'on relie ~ son plus proche voisin. Ces deux nceuds ainsi que l 'arc qui les relie

cons t i tuen t une composante connexe. On cherche alors le plus proche voisin des nceuds qu'elle contient , on ajoute ce nouveau nmud, et ainsi de suite jusqu 'h ce qu'elle renferme tous les nmuds. On poss~de alors l 'arbre minimal .

L 'a lgor i thme de Pr im va ~tre modifi~ de la fagon suivante : on relie le nceud choisi pour d~marrer l 'a lgori thme, d i rectement au CT I ; son ordre est au plus ~gal h 1 (ce nceud ne comporte pas n~cessairement une diffusion dans l 'arbre final), et on le majore en le p renan t ~gal h 1.

Pour pouvoir ra jouter un nmud h la composante connexe obtenue, il faut que son ordre r~sul tant soit au plus 6gal ~ 3. Dans certains cas, il est impossible de relier un nceud h la composante connexe par un arc du r6seau et de satisfaire la cont ra in te $1. Pour cela on est amen6 h compl6ter le graphe en ajou- t a n t des liaisons fictives entre les points non reli6s par un arc direct. Le coflt d 'une telle liaison fictive est calcul6 ~ par t i r de la distance ~ vol d'oiseau s6pa- r a n t les extr6mit6s, comme pour un arc direct.

Pour rendre le r6seau phys iquement r6alisable ces

liaisons fictives sont en fair construites au plus court chemin.

Avec ce graphe complet il est toujours possible de

construire un r~seau sat isfaisant $1 et que nous appellerons arbre pseudo-minimal (APM).

re l iant ~ ~ ~ dans le graphe ini t ial (voir d6finition de l 'arc fictif, w 8.1), y ayan t lui-m6me pour p~re le nceud i dans APM.

Soit ]o le nceud di rectement reli6 au C T I darts APM.

Si day + dvj ~ < dv~ § d ~ , alors il est int6ressant de relier d i rectement y h ]0 et ~ h y, la liaison ~y correspondant h u n arc non fictif.

On remarquera ais6ment que l 'ordre des nceuds ue peut augmenter et donc que la cont ra in te $1 reste v6rifi6e, sauf pour un cas part iculier (*).

On applique cette proc6dure jusqu 'h ce qu ' aucune am61ioration ne soit plus possible. Si certains nceuds facultatifs dev iennent pendan ts ils sont alors 61imin6s, et le r6seau est rendu phys iquement r6alisable en rempla~ant les arcs fictifs par des liaisons construi tes au plus court chemin.

Darts la prat ique, la proc6dure sp6ciale est relati- vemen t peu souvent n6cessaire, sauf pour les r6seaux off la charge moyenne d ' un te rminal est tr~s faible vis-a-vis de CHAMAX, auquel cas on risque de connecter un tr~s grand nombre de t e rminaux sur la ligne mul t i - point . L 'a rbre min imal relatif ~ u n ensemble E~ est alors souvent 61oign6 d 'une configuration mul t ipoin t .

8.3. Utilisation des centres c o m m e no~uds d 'ordre 1.

Au premier pas de la proc6dure sp6ciale on choisit

un nceud ]o qui doit etre ~ ra t tacher d i rectement au

(*) Le seul cas off la procedure n'est pas appliqu6e se pro- duit lorsque ]0 = ~ (Fig. 11). En effet, on augmenterait l'ordre de ~, et donc celui de ses descendants, et la contrainte S 1 pourrait ne plus ~tre satisfaite.

- - 1 7 - -

8 / 8 J . GRA$$IN [ANNALES DES TI~LI~COMMUN|I~ATIONS

C T I. On pourra i t bien en tendu appliquer la procOdure en p renan t successivement t o u s l e s nceuds comme noeud de dOpart et conserver la meilleure configuration.

On a donc limit6 l 'ensemble des nceuds de dOpart en un ou plusieurs centres (*) du graphe su ivan t le

cas et ceci pour deux raisons :

1) outre une rapidit6 de calcul accrue, la meilleure configurat ion est obtenue, dans la quasi- total i t6 des cas, en p a r t a n t d ' u n centre ;

2) du point de rue de la rOalisation du rOseau on prOf~re util iser des arcs directs ~ des liaisons construi tes sur des plus courts chemins. Cette derni~re condit ion est d ' a u t a n t plus faci lement rOalisOe que l 'on par t d ' un centre.

9 . F i n d e l ' a l g o r i t h m e .

Apr~s avoir cons t ru i t un rOseau pour le sous- ensemble E k h l 'a idc de l 'une des deux procOdures considOrOes, on ~limine cet ensemble du rOseau global et on cherche un nouvel ensemble Ek et ainsi de suite jusqu 'h 6puisement des nceuds.

L 'ensemble des opOrations h effectuer sont schOma- tisOes par l 'o rganigramme de la figure 12.

R ] ~ S U L T A T S E T C O N C L U S I O N

Un code ~crit en FORTnAN sur le caleulateur du CNET (**) permet de calculer un rOseau, compor tan t un peu plus de 1 000 t e rminaux , en 11 secondes (***).

I1 est donc possible de comparer tr~s rap idement de nombreuses configurat ions diff6rant par le nombre ou la posit ion des C T I e t la vitesse de t ransmiss ion

choisie. On constate une amOlioration sur le coot des

rOseaux de l 'ordre de quelques % pour les configu- rat ions compor tan t peu de t e rminaux et p o u v a n t aller jusqu'f i 50 % pour les grands rOseaux. Dans t o u s l e s exemples considOrOs jusqu 'h prOsent le r6sul- t a t obtenu h la ma in s 'est toujours av6r6 plus cher que celui ob tenu par opt imalisat ion.

Le rOseau obtenu peut ~tre ensuite simulO, ceci dans le cas od la va leur du temps de rOponse dans le rOseau est un 616ment d6terminant .

Si le temps de r6ponse est jug6 trop 61evO, on peut d iminuer la valeur de CHAMAX, par cons6quent on

obt iendra un nombre infOrieur en moyenne de ter-

m i n a u x par ligne et donc un meilleur temps de

r6ponse.

(*) Pour la d~finition du centre d'un graphe, se reporter h [4, p. 42].

(**) G E 635. (***) Le cas consid~r~ est celui d'un grand rdseau bancaire,

off par terminaux il faut entendre unitOs de contrOle, chaque agence comporte une unit6 de contrOle fi laquelle sont rat- tach~s plusieurs terminaux.

Un prochain article t ra i tera des r6seaux avec concentrateurs et des rOseaux avec mult iplexeurs.

Manuscri t recu le 5 novembre 1971.

non

Construction de I'arbre minimal g@6ral

1 l ~ l

L

J

l OUl

Calcul du meilleur ensemble Ek

Essai de construction d'un r6seau relatif ~ E. k ~ I'aide

de la procedure normale

~ o u i

Utilisation de la proc6dure sp@iale

L

EliminatiOnde E L I

FIG. 11. - - Organigramme gOnOral.

BIBLIOGRAPH IE

[1] MARTIN (J.). Teleprocessing network organisation (Organisation du rdseau de tdldtraitement). Prentice Hall, U.S.A., (1970), 290 p.

[2] DREYFUS (S. E.), WAr (R. A.). The Steiner problem in graphs (Le problOme de Steiner dans la thdorie des graphes). O.R. Center univ. o] Call]. Berkeley, O.R.C. 7032 (sept. t970), 20 p.

[3] RoY (B.). AlgObre moderne et thOorie des graphes orientals vers les sciences 6conomiques et sociales. Dunod, Paris, tome I (1969), 502 p., tome 2 (1970), 753 p.

[4] BEac~ (C.). Thdorie des graphes et ses applications. Dunod, Paris, (1967), 278 p.

N 18 m