Embed Size (px)
Citation preview
O.R.T.I. : OPTIMALISATION DES
J 6 r S m e G R A S S I N Ingdnieur des T616communications *
R]~SEAUX DE T]~L]~INFORMATIQUE
pa r
e t Gilles G A T O T Maitre es Sciences : Informatiquc **
R~SUM~. - - Aprds une prdsentation rapide des types de rdseaux enoisageables el de leurs caracldristiques propres, les auleurs abordent en ddtail la mdthode d'optimalisation des rdseaux multipoints. Les principales iddes de cette mdthode heuristique servent pour le calcul des rdseaux avec concentrateurs. Les rdsultats obtenus sur des cas rdels el de grande dimension semblent trds encourageants. En conclusion, Ies auteurs traitent les probldmes de sdeuritd de ces rdseaux. Les programmes d'optimalisation el de simulation constituent l'ensemble
de programmes appel~ O.R.T.I .
PLAN. - - Introduction �9 I : Structure e t earaet~rist iques des di[[drents rdseaux 1.1. Les lignes louses; 1.2. Tarification des lignes loudes; 1.3. Terminaux et extrdmilds de lignes; 1.4. R~seau point ~ point; 1.5. Rdseau mullipoint ; 1.6. R~seau comportant des concentrateurs ou des muUiplexeurs ; 1.7. Autres rdseaux ; 1.8. Rdseaux comportant plusieurs C.T.I . �9 I I : Rdseaux mui t ipo in ts II .1. Prdlraitement des donndes; I I .2 . Remarques sur la tarification des liaisons; II .3. Formulation mathdmatique du probikme ; II .4. Confi- guration optimale; II .5. Arbre minimal; II .6. Ddlermination d'un ensemble E~; II .7. Ddlerminalion du r~seau multipoinl pour uu ensemble Ek ; II .8. Elimination de l' ensemble Ek. �9 I I I : Rdseaux aoee eoncen- t ra teurs I I I .1 . Traitement gdndral de ees rdseaux; I I I .2 . CaIcul du rdseau aval; I I I .3 . Caleul du rdseau amont. �9 IV : Rd.sultats. Exemples IV.1. Rdsullals pratiques ; IV.2. Valeur des solutions obtenues ; IV.3. Exemples de rdseaux. �9 V : S i m u l a t i o n �9 V I : Probl~.me de la s~curitd. Conclusion.
Bibliographie (5 r6f.).
INTRODUCTION I. STRUCTURE ET CARACTI~.RISTIQUES
DES DIFF]~RENTS B]~SEAUX
Les r6seaux que nous a l lons 6 tudier son t cons-
t i tu6s h p a r t i r de l ignes lou6es h l ' A d m i n i s t r a t i o n
des P .T .T . D e v a n t le n o m b r e sans cesse c ro i s san t de
d e m a n d e s de la p a r t d ' a u t r e s a d m i n i s t r a t i o n s , d ' e n t r e -
prises pr iv6es ou na t ional i s6es , p o u r c o n s t i t u e r des
r6seaux de t616informat ique , il nous a p a r u n6cessaire
de d6ve loppe r un ce r t a i n n o m b r e de m o y e n s p e r m e t -
t a u t de c o m p a r e r r a p i d e m e n t d iverses so lu t ions en t r e
elles, af in de p ropose r h l ' u t i l i s a t e u r un r6seau d o n t
le cofl t de loca t ion m e n s u e l sa l t le p lus fa ib le possible . R a p p e l o n s que dans un r6seau lou6, le c l i en t a
l ' exc lu s iv i t 6 de l ' u t i l i s a t i on des l ignes ce qui n ' e s t pas le cas p o u r un r6seau c o n s t r u i t h p a r t i r
du r6seau c o m m u t 6 . D a n s une p remibre pa r t i e nous p r6sen t e rons les
s t r u c t u r e s possibles et les ca r ac t6 r i s t i ques des r6seaux,
puis nous naris in t6resserons au ca lcul des r6seaux
m u l t i p o i n t s , celui des r6seaux a v e c c o n c e n t r a t e u r s
ou m u l t i p l e x e u r s f a i san t l ' o b j e t d ' u n e t ro i s i~me
par t i e . Nous t e r m i n e r o n s ce t a r t i c le p a r que lques
c o m m e n t a i r e s sur les r6su l ta t s ob t enus e t sur la s imu-
l a t ion des r6seaux.
A v a n t d ' a b o r d e r le su je t qui nous pr6occupe , nous
t e n o n s fi s ignaler la possibi l i t6 de r6al iser le r6seau
h l ' a ide du r6seau c o m m u t 6 ou encore du r6seau
CADUC~ mis en service au d6bu t de j a n v i e r 1972. Le
coflt de tels r6seaux est o b t e n u pa r de s imples add i -
t ions e t ne fa i t donc l ' o b j e t d ' a u c u n e op t ima l i s a t i on .
1.1. Les lignes lou6es.
L ' u t i l i s a t e u r a l e cho ix en t r e h u i t t y p e s de l ignes
p a r m i lesquels nous ne m e n t i o n n e r o n s que les q u a t r e
les plus c o u r a m m e n t employ6s :
a) L igne t616graphique : 200 bauds ,
b) l igne t616phonique : 2 ills,
c) l igne t616phonique : 4 ills, qua l i t6 n o r m a l e ,
d) l igne t616phonique : 4 ills, qua l i t6 sup6r ieure .
Le r6seau s u p p o r t de ces l ignes est celui de la
D i r e c t i o n des t616communica t ions du r6seau n a t i o n a l
(D.T.R.N.) des P .T .T . Les n ~ u d s de n o t r e r6seau au
* A u C N E T - I s s y , g r o u p e m e n t INFORMA.TIQUE ET TRANSMISSION DES DONNI~ES~ d 6 p a r t e m e n t CAI, CULATEURS I~LECTRONIQUES ET SYSTI~MES.
** Ing6nieur contractuel au CNET-Issy, groupement INFORMATIQUE ET TRANSMISSION DES DONNEES, d6partement CAI.- CULATEURS ELECTRONIQUES ET SYSTI~MES.
1/16 A. TELEC., 28, n o~ 1-2, 1973
4 J. GRASSIN. -- OPTIMALISATION DES R~SEAUX DE DONN~ES
nombre de 230 environ, const i tuent une part ie de
l 'ensemble des centres d 'ampl i f ica t ion (C. A.) du
r~seau D.T.R.N.
NOUS dirons qu ' i l existe un arc entre deux noeuds
s'il existe au moins un groupe primaire (*) entre ces
nceuds dans le rdseau D.T.R.N.
Le graphe h par t i r duquel von t ~tre r~alis~s les
r~seaux de t~l~informatique comporte done environ
230 neeuds et 1 500 ares. Tous les ares sont non or ien t , s
nous appelerous G le graphe ainsi constitu~.
1.2. Tarification des lignes lou6es.
Le coflt de locat ion d 'une ligne de type donn~
rel iant deux points A e t B d~pend seulement de la
distance i~ vol d 'oiseau s~parant A et B (**).
La fonct ion de coflt est cont inue et lin~aire par
morceaux que] que soit le type envisage.
La figure 1 donne l 'a l lure de cette fonct ion pour
une liaison du type a) d~crite au paragraphe 11.
CoOt en F/mois
2 073
723
243
~" denkm 10 50 350
Fro. 1. - - Cofit d'une ligne t~l~graphique ~ 200 bauds en fonction de sa longueur d.
Pour les autres types de ligne, l 'al lure de la courbe
est sensiblement la m~me.
Nous verrons p le inement la n6cessit6 d 'une telle
dis t inct ion dans la suite.
Nous ne consid~rerons que les extr6mit~s de ligne
et ehaque EXTL sera caract6ris6e par deux paramStres ,
sa charge et le uombre de t e rminaux qui lui sont
eonneet6s.
La somme du trafic issu de cet te extr~mit~ de ligne
et du trafic qui lui est destin6 en provenance du CT~,
repr6sente la charge de eet te ~XTL. En pra t ique cet te
charge est obtenue en sommant les charges des ter-
minaux connect~s h I'EXTL consid~r~e.
Cette charge dolt 6tre exprim~e avec la m~me unit~
pour toutes les extr6mit~s de lignes EXTL et peu t
6tre, par exemple, le nombre de caraet~res ~mis et
re~us en moyenne pendan t l 'heure charg~e ou bien
un nombre de messages par minute .
Nous allons m a in t enan t 6tudier les diff6rentes
s t ructures de r6seau envisageables.
1.4. R6seau point ~ point.
La premiere id6e et Ia plus simple qui v ien t ~ t 'espr i t
pour construire un r~seau consiste h relier chaque
EXTL par une ligne directe au CTL On obt ient un r~seau
dit point ?l point (Fig. 2).
6
FIG. 2. - - R6seau point h point.
1.3. Terminaux et extr6mit6s de ligne.
Un r6seau de t ransmission de donn6es est consti tud
d 'un ou de plusieurs centres de t r a i t emen t de l ' infor-
mat ion (C.T.I.) et de t e rminaux (t~l~imprimeurs,
~crans, machines de caisse, etc.). Ces t e rminaux
doivent ~tre connect~s au(x) C.T.I. par l ' interm~diaire
de lignes louses.
Phys iquemen t une ligne about i t soit h u n te rmina l
soit h une unit~ de contr61e h laquelle sont ra t tach6s
plusieurs t e rminaux . Nous dirons que la ligne about i t
h une extr~mitd de ligne ( E X T L e n abr6g~). L'EXTL
peut comporter plusieurs t e rminaux , c 'est le cas d 'une
unit~ de contr61e, mais d 'une EXTL ne par t qu 'une
seule ligne vers le CTI. Un te rminal reli6 au CTI par
une ligne est consid6r~ comme une EXTL ne compor-
t an t qu ' un seul terminal .
(*) Un groupe primaire 6quivaut h 12 circuits t616phoniques. (**) ]l existe n6anmoins une petite diff6rence dans la tariff-
cation des diff6rents tron~ons d'un r6seau multipoint, comme nous le verrons plus loin.
Cette solution peu t s 'av6rer tr6s coflteuse si un
grand nombre de EXTL s0nt 61oign6es du CTI et si
chacune d 'en t re elles n 'ut i l ise sa ligne que pendan t
une tr6s faible par t ie du temps ou de fa~on 6quivalente
si les EXTL ont une charge tr~s pet i te . L 'u t i l i sa t ion
du r~seau eommut6 peu t alors ~tre plus int~ressante
du point de r u e du coflt dans de nombreux cas.
1.5. R6seau multipoint.
En connectant plusieurs E X T L (*) SUr une m~me ligne on a donc tendance h diminuer le coflt to ta l
du r~seau et ~ amdliorer l 'u t i l i sa t ion des lignes.
La figure 3 donne un exemple d 'un tel r~seau dit
multipoint. Le r6seau obtenu correspond ~ un arbre rel iant les
EXTL, num6rot6es de 1 it 6, au CTI. Le type de ligne
utilis6 est homog~ne sur t o u s l e s tron~ons ; n6anmoins
(*) Toutes les EXTL consid~rdes sont suppos6es situ6es dans la localit6 d'un C.A. (voir w 1.1).
A. T#,I.AC., 28, n ~ 1-2, 1973 2/16
J . GRASSIN. -- O P T I M A L I S A T I O N DES Ri~SEAUX DE DONNi~ES 5
6
4
Fro. 3. - - R 6 s e a u d i t mullipoinls r e l a t i f au m ~ m e e n s e m b l e de t e r m i n a u x que le r 6 s e a u p o i n t h p o i n t de la f igure 2.
il existe une pet i te diff6rence darts la fac tura t ion des
trongons te rminaux, tels que (2-3) ou (6-5). Pour ces
trongons et pour certains types de ligne seulement,
le coot est multipli6 par un facteur de l 'ordre de
1-2. Le coot to ta l du r6seau est la somme des coots
de tous les tron$ons.
Darts [1] une m~thode de calcul des r6seaux mult i -
points est propos6e. Le probl6me des r6seaux ayan t
6t6 reformul6 depuis la paru t ion de [1], certaines
contraintes ayan t 6t6 modifi6es ou ayan t 6t6 ajout@s,
il en r6sulte des modif icat ions sensibles dans la
m6thode de r6solution.
a) Contrainte SI ou contrainte des trois tron~ons.
Diverses contraintes techniques nous imposent
une l imi ta t ion sur la longueur du chemin rel iant une
EXTL quelconque au CTI (la longueur consid6r6e ici
est le hombre d 'arcs composant le chemin). A y a n t
un r6seau arborescent ce chemin est d 'ai l leurs unique.
Cette longueur ne doit en aucun cas d6passer 3 et cela
const i tue la contrainte que nous appelons sI, ou
contra inte des trois tron~;ons. Un point quelconque
du r6seau sera doric reli6 au CTI par une chaine
compos6e de 3 ares au plus.
b) Contrainte de charge.
Darts un r6seau mul t ipoint , il n 'es t pas possible
d '6met t re s imul tan6ment depuis plusieurs t e rminaux .
De m~me plusieurs t e rminaux ne peuven t pas rece-
voir s imul tau6ment des messages p rovenan t du CTL
On a doric recours ~ des proc6dures d ' in te r roga t ion
(polling) dont J. Martin donne une excellente des-
cr ipt ion [2].
Par ailleurs le trafic 6cou16 par la ligne mul t ipo in t
ne pent pas exc6der une valeur CM que nous appelons
la charge maximale de la ligne. Cette charge CM est
une f ract ion de la charge th6orique maximale CTM .
En prenan t un 6quivalent de 10 unit6s binaires
par caract~re, on a pour une ligne fi 1 200 bauds
C T = 120 caract6res/seconde.
On a la relat ion : C M = )~C T , 0 <<. X <<. 1 ,
En g6n~ral on prend : ;~= 0,7 .
Soit Ek l 'ensemble des t e rminaux connectes sur
la ligne k et soit c i l a charge du te rminal i. Le fai t
que les t e rminaux ne puissent pas t r ansmet t re simul-
t an6ment se t r adu i t par l ' in~galit6 encore appelde
conlrainle de charge :
Ci <~ C M , i ~ E k
c) Contrainte sur les terminaux.
Darts certain cas le nombre de t e r m i n a u x ou d'EXTL
appar t enan t h E k ne dolt pas d~passer une certaine
valeur T M. Cette contra inte l imi tan t le hombre de
t e rminaux par lignes peut provenir d 'une pr66tude
ou d ' imp6rat i fs techniques. En prenan t T M = oo,
on a la possibilit6 d ' ignorer cet te contrainte. Toute-
lois la valeur de T M est ident ique pour toutes les
lignes mul t ipoin ts cons t i tuan t le r~seau.
1.6. R6seau comportant des concentrateurs ou des multiplexeurs.
I1 est parfois possible d 'am~liorer le r endement
des lignes et de diminuer le coflt du r~seau en u t i l i sant
des concentrateurs . On profi te du fair que dans la
major i t6 des applicat ions les t e rminaux rm trans-
m e t t e n t pas et ne regoivent pas de l ' in format ion de
fagon continue pour en connecter un grand hombre
sur un concent ra teur qui se charge 6ventue l lement
de faire un pr6 t ra i tement des messages, mais sur tout
effectue une conversion de la vitesse de t ransmission
grace h une m6moire tampon. La transmission entre
les t e rminaux et le coneentra teur s 'effectue '~ une
vitesse beaucoup plus faible que celle entre le concen-
t r a teur et le CTI.
a) Rdseau aval.
Le r6seau rel iant les EXTL au coneent ra teur peu t
6tre de type point h point ou mul t ipoin t . I1 por te le
nora de r6seau avaI et est soumis aux m6mes
contraintes que les r6seaux point h point ou
mul t ipoint .
b) Rdseau amont.
I1 en est de m6me du r6seau amont ou r6seau hante
vitesse qui relie les concentra teurs au CTI.
c) Contraintes propres au concentrateur.
Outre les contraintes relat ives aux r6seaux amour
et aval il existe des l imitat ions po r t an t sur le hombre
max ima l de t e rminaux ou d'EXTL qui peuven t 6tre
connect6s h u n concentra teur . Cette contra in te peu t
avoir un aspect pu rement matdriel ou bien au contraire
6tre le r6sultat d 'une 6rude pr6alable sur l '6volut ion
du temps de r6ponse moyen en fonct ion du trafic et
du hombre des t e rminaux attach6s ~ un concentra teur .
d) Emplacement des concentrateurs.
I1 para i t raisonnable d ' implan te r les concentra-
teurs darts un centre impor tan t ceci pour des raisons
3/16 A. TkLkC., 28, n ~s 1-2, 1973
6 J . G R A S S I N . -- O P T I M A L I S A T I O N D E S R ] ~ S E A U X D E D O N N ] ~ E S
de rapidit6 d ' in te rven t ion en cas de panue. A cette fin, on a restreint les possibilit6s d ' imp lan ta t ion aux
CA.
1.7. Autres r6seaux.
Les r6seaux en boucle, les r6seaux inter ordinateurs ne seront pas trait6s dans le pr6sent article, car ils font appel ~ des techniques d 'opt imal isa t ion tr~s diff6rentes de celles qui von t 6tre expos6es. N6anmoins ils font l 'obje t d '6tudes h l 'heure actuelle.
1.8. R6seaux comportant plusieurs C.T.I.
Nous avons ment ionn6 les r6seaux h plusieurs CTI sans pr6ciser la fa~on dont chaque te rmina l 6tait affect6 h un CTL Le r6seau inter CT~ fait l 'obje t d ' un calcul s6par6 et rentre dans le cadre des r6seaux du
paragraphe 1.7. L 'affectat ion des t e r m i n a u x ou des EXTL peut
se faire de deux mani6res.
Dans le eas off la charge de l 'ensemble des EXTL
reli6es h un m~me cA d6passe la charge maximale CM d 'une ligne, ou que le hombre de t e r minaux correspondants est sup6rieur h TM, il est n6cessaire de t irer unc ou plusieurs lignes directes entre ce CA et le CTX en ins ta l lant a u t a n t de dispositifs de diffusion
au cA qu' i l y a de lignes directes. A chaque ligne direete, on associe le plus grand
nombre possible d'EXTL, tou t en respeetant la eont ra in te de charge et celle relative aux te rminaux .
Apr6s 61imination des EXTL connect6es h des lignes directes, il reste en chaque cA u n certain hombre, 6ventuel lement nul, d'EXTL telles que la charge totale correspondante est inf6rieure h CM et que l e n o m b r e
tota l de t e rminaux est inf6rieur h TM. On peut donc associer h chaque CA une cbarge
C/ et un hombre d'EXTL 0U de t e r mi na ux t t tels que :
Ci ~ CM, V,, t, < TM �9
II.2. Remarques sur la tarification des liaisons.
a) Prdaffecfion.
Pour diverses raisons d 'ordre adminis t rat i f ,
d ' appar tenance h une m~me r~gion, etc. l 'u t i l i sa teur
peut affecter a priori u n terminal h un CT~ donn6.
b) Affectation libre.
Si aucune contra iute ne r~git l 'affectation, alors le crit6re choisi est celui de la distance h vol d'oiseau. Chaque EXTL est affect6e au CTZ le plus proche h vol d'oiseau. On obt ien t ainsi une par t i t ion de l 'ensemble des t e rminaux qui peu t servir de base de d6part h d 'au t res optimalisat ions.
Dans t o u s l e s cas, on se ram~ne h l 'opt imal isa t ion d ' u n r6seau compor tan t u n s e u l CTL
Apr6s avoir vu les diff6rentes structures de r6seau possibles nous allons m a i n t e n a n t examiner les m6thodes d 'op t imal i sa t ion correspondantes. Duns le cas des r6seaux poin t ~ point , parler d 'opt imal i - sation est un b ie r grand mot , quand il suffit d 'addi- t ionner les coflts relatifs h chacune des lignes rel iant une EXTL au CTI.
C'est pourquoi Rous l imiterons notre examen au cas des r6seaux mul t ipoints , puis h celui des r6seaux avec coucentrateurs.
II. I:t~SEAUX MULTIPOINTS]
II.1. Pr6traitement des donn6es, lignes directes.
Chaque EXTL est d ' abord rat tack6e au centre de groupement (CG) le plus proche, lequel cG est ensuite rat tach6 au cA le plus proche. Cela 6quivaut donc h regrouper plusieurs ~XTL s u r u n mdme cA.
Comme nous l ' avons men t ionn6 au w 1.2 il existe une singularit6 daus la tar i f ieat ion des liaisons d ' u n
r6seau mul t ipoint . Cette diff6rence n 'es t ru lable que pour les lignes du type c et d. Su ivan t que la liaison relic une extr6mit6 terminale h un dispositif de diffusion ou qu'elle relie deux dispositifs de diffusion
entre eux, le tarif est diff6rent. Ces deux tarifs sont d 'ai l leurs diff6rents du tarif po in t h point .
A t i t re d 'exemple, nous consid6rerons une liaison de 100 km r6alis6e en 4 ills qualit6 normale :
coflt de location
mensuel 1. Extr6mit6 terminale - disposition de
diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . 1444,50 F
2. Disposition de diffusion - disposit ion de diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . 1203,00 F
3. Po in t ~ point . . . . . . . . . . . . . . . . . . . . . . 1686,00 F
Pour t o u s l e s types de lignes autres que e et d, le tarif est ident ique au tarif poin t h point .
Duns l 'opt imal isa t ion p roprement dite, il n ' a pus 6t6 possible de tenir compte de la diff6rence entre 1 et 2. L 'op t imal i sa t ion de la s t ructure est faite sur la base de 2 et une fois le r6seau d6termin6, on
r6ajuste les coflts pour les liaisons du eas 1. E n d 'autres termes, l 'opt imal isa t ion est faite eomme si toutes les
liaisons compor ta ient un dispositif de diffusion h chacune de leurs extr6mit6s, l ' a j u s t emen t du eoflt pour les liaisons terminales n ' 6 t a n t fait qu 'h la fin.
Une just i f ieat ion du ehoix de cette m6thode provien t de ce que pour la quasi- total i t6 des r6seaux r6els 6tudi6s, le hombre des liaisons du type 1 est trgs faible.
Duns le graphe G, on remplace donc la longueur des ares par les coflts de location correspondants caleul6s sur le mode 2, avan t de proc6der h l 'opt imal isat ion.
A. T~c., 28, r~ ~ 1-2~ 1973 4/16
J . G R A S S I N . - - 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 D O N N E E S 7
11.3. Formulation math6matique du pro- blame.
U n r~seau m u l t i p o i n t es t un a rb re d o n t la rac ine
est le CTI. U n e des ca rac t~ r i s t iques de ce r6seau est
c{ue c h a q u e nceud est accessible depuis la rac ine pa r
un c h e m i n de l ongueu r au plus ~gale /~ 3. A c h a q u e
l igne m u l t i p o i n t es t associ~ un sous -a rb re v~r i f i an t
les c o n t r a i n t e s de charge et de t e r m i n a u x .
f ihaque nceud de charge non nul le es t reli~ h la
rac ine p a r ur~ c h e m i n et un seul. P o u r un nceud i
donn6 il ex is te un rmmbre Ni de chemins de l o n g u e u r
au plus ~gale h 3. A c h a c u n de ces chemins on p e u t
associer une va r i ab l e b ina i re x~j ] - 1 , 2 . . . . , N~,
te l le que :
i xiJ = 1 , si le c h e m i n ] es t choisi ,
xtj = 0 , cas con t ra i re .
Ni La c o n t r a i u t e de cho ix m u l t i p l e ~ x~j = 1 t r a d u i t
j = l le fa i t que le nceud i est reli~ h la rac ine pa r un
c h e m i n e t un seul.
On r e m a r q u e r a t o u t de sui te que le n o m b r e N~
p e u t ~tre tr~s g rand , ce c [ u i e s t v ra i en p r a t i q u e .
C h a q u e c h e m i n e m p r u n t e un ce r t a i n u o m b r e d 'a rcs ,
e t il es t possible d ' o b t e n i r la m a t r i c e a r c - ehemins A
en i n sc r i van t en l igne les ares et en co lonne les ehemins .
[ 1, si Fare k a p p a r t i e n t au c h e m i n l,
[ A ] = [akzl,akz= 10, c a s cont ra i re .
La m a t r i c e A nous p e r m e t de f o r m u l e r le p rob l~me
g~n~ral c o m m e un p r o g r a m m e l in~aire en h o m b r e s
ent iers .
Soi t gk la va r i ab l e ent i~re associ@ h l ' ex i s t ence
d ' u n are,
g ~ = 0, l ' a rc k n ' e x i s t e pas dans le r~seau,
g~ ~ 0 , il ex is te une ou p lus ieurs l ignes e m p r u n -
t a u t l ' a rc ~.
Il lui co r r e spond de plus un cofl t ck.
Consid~rons d ' a u t r e p a r t la m a t r i c e A~ d~dui te
de A en m u l t i p l i a n t t o u t e s les co lonnes de A re l a t ives
au nceud i p a r c,t, la cha rge du noeud i e t ceci p o u r tous
les i. De m ~ m e on o b t i e u t A2 en e f f ec tuan t la m ~ m e o p e r a t i o n avec t,~.
chemin s re la t i fs chemins re la t i f s
au no~ud 1 au n(~ud p
I 1 1
1 l i [A] = 1 . . . . . . 1
1 1 _ 1 1 _
I C 1 Cp I
C 1 e 1 cp i
[ A 1 ] = C 1 Cp
e 1 Cp
c 1 cp
arcs,
L a c o n t r a i n t e de charge se t r a d u i t p o u r e h a q u e arc
k pa r l ' inSgal i t6 :
cllkl Xl ~ C M ~]k V k , 1
De m ~ m e la c o n t r a i n t e sur les t e r m i n a u x s ' e x p r i m e
p a r :
~.~a~l Xl < T M gk V k . 1
L ' i n d i c e l co r r e spond ici h un couple i].
La v a r i a b l e gk n ' e s t pas b iva l en t e , ma i s ent i~re
que l conque , car p lus ieurs l ignes m u l t i p o i n t s p e u v e n t
e m p r u n t e r le m ~ m e arc.
Le p r o g r a m m e p e u t doric se f o r m u l e r :
X l l . . . . . .
A1
[ A2
ZpNp Yl . . . . . . Yu
~<
11111
11111
"111 [il E n p o s a n t :
[31] = 11111 1
11111 " .
111
et en d6s ignan t p a r I la m a t r i c e uni t6 , on a l e pro- n
g r a m m e l in6aire s u i v a n t : Min Y, Ci g i , i = 1
te l que [zt l] X - - CM I Y <. O,
I [zt[2 X - - T M I Y <~ O,
[~1 x = e , !
X b i v a l e n t , Y en t ie r ,
off Y = (g . . . . , gn), n d tan t le h o m b r e d ' a r c s du r~seau.
e
est un v e e t e u r ~ m eomposan t e s , m ~ t an t le n o m b r e
de nceuds de charge non nul le
X ( Z l l , x 1 2 , . . . X l , N l ~ X21 , . . . ~ Xpl ~ ... XpNp) .
I1 est i m p e n s a b l e de r6soudre un t e l p r o g r a m m e
en h o m b r e s en t ie rs 6 ran t donn6 les mi l l ie rs de va r i ab l e s
qu ' i l e o m p o r t e m ~ m e p o u r un t o u t p e t i t r6seau.
C 'es t p o u r q u o i nous avons or ient6 n o t r e r eche rche
vers une m 6 t h o d e heu r i s t i que , p o u v a n t d o n n e r des
r6su l ta t s dans un t e m p s de calcul r6dui t .
5/16 A. T~L~C. , 28 , n ~ 1-.2, 1 9 7 3
8 J . G R A S S I N . -- 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 D O N N ~ E S
11.4. Configuration optimale.
Le r~seau optimal , nous l ' avons vu au paragraphe precedent a une s t ructure d 'arbre dont la racine est le CTI (Fig. 4).
/ \
I . - - - - -4 / / / / \
\,,, \ / /
( 2"-, \, / 1 ,\" }
\ \ . . / \ J F l a . 4. - - Configuration optimale.
A chaque ligne k about i ssan t au CIT, on peu t asso- cier l 'ensemble E~ des CA rattach~s sur la ligne k. Cette ligne est un sous-arbre de l 'arbre gdn~ral qu 'es t le rdseau.
I1 existe donc une par t i t ion de l 'ensemble des noeuds en ensembles Ek tels que pour chacun de ces ensembles les diverses contra intes soient respect~es.
Cette remarque nous a condui t fi adopter la d~marche suivante h deux phases dans la m~thode
heurist ique.
a) D~terminer des ensembles Ek tels que la charge de chaque ensemble, c'est-h-dire la somme des
charges des E X T L ~ui en font partie, soit inf~rieure h CM et que le hombre de t e rminaux soit inf6rieur
h T M .
b) Pour chaque Ek calculer le r6seau de Ineilleur coot sat isfaisant la cont ra in te des trois tron~ons.
Na ture l lement si dans a) les ensembles Ek sont form6s de points g6ographiquement voisins, il est fort probable que le coot obtenu en b) sera bon.
L 'a rbre min ima l fait en g6n6ral apparai t re des connexions entre points g6ographiquement voisins
et pr6sente en outre l ' avan tage de fournir une excel-
lente base de d6part pour r6soudre le problbme b) comme nous le verrons par la suite.
II.5. Arbre minimal .
1. D~flnition.
Un nceud i est dit facul tat i f si ci = ti = 0, et obli- gatoire dans le eas contraire.
On remarquera d'ail leurs que ci ~ 0 ~-> ti ~ O.
R e m a r q u e . Le CTI est toujours consider6 comme un nceud obligatoire m~me si sa charge est nulle.
Le graphe G n ' ~ t a n t pas complet, il est patrols n6cessaire de passer par un ou plusieurs nceuds faeultatifs pour relier deux nceuds obligatoires.
D6signons par N le hombre de nceuds de G, et soit N 1 le nombre de nceuds obligatoires pour u n probl~me donn6. Ce nombre N1 varie en effet d ' u n probl~me
l 'autre . On se propose de calcnter l ' a rbre min imal re l iant ces N 1 nceuds obligatoires en e m p r u n t a n t
6ventuel lement certains des N - N 1 nceuds facultatifs.
Dreyfus [3] propose une m6thode de r6solution
exacte de ce probl~me, par la p rogrammat ion dyna- mique, mais pour de grands r~seaux eompor tan t beau- coup de nceuds facultatifs, ce qui est malheureusement notre eas, cette m~thode est imprat icable et tr~s
coflteuse. Nous avons pr6fdrd r~duire progressivement l ' a rbre
min imal construi t ~ par t i r des N noeuds de la fa~on
suivante.
2. Rdduction de l'arbre.
a) Suppression des n~uds [acultuti[s de degrd I.
Le degr6 d ' u n no~ud facultat i f dans l 'arbre mini -
mal est soit 6gal ~t u n ce qui correspond h u n poir~t pe nda n t (*), soit sup6rieur i~ un. Nous consid6rons q u ' u n nceud facultat i f p e n d a n t est inuti le et m6rite
d '6tre supprim6. De la suppression d ' u n ou de plusieurs nceuds
facultatifs pendants , peu t r6sulter l ' appar i t ion d 'aut res n(euds pendan t s facultatifs. Cette suppression se poursui t jusqu '~ ce que tous les nceuds facultat ifs
res tants soient de degr6 p ~> 2.
b) Suppression des no~uds faeultati[s de degr~ sup~rieur ou ~gal d 2.
Eliminer u n nccud / de degr~ p ~quivaut h cr ier p composantes connexes Z 1, Z 2, ... Z p . Pour main- tenir la connexit6 du r6seau, il faut donc ra jouter p--1 arcs de longueur 11, 12, ... Ip , sans cr6er de cycles et de sorte que la somme s = l 1 + l~ § ... § lp_ 1
soit minimale. Cela ~quivaut it construire l ' a rbre min imal pour
le graphe H d~fini comme suit. A ehaque composante connexe correspond un nceud de H. Darts le cas off il existe au moins u n arc entre la composante I e t
la composante J , il existe un arc de longueur mini-
male. Dans H, on assoeie alors u n are de m~me ion- gueur que cet arc de longueur minimale entre les sommets correspondants h 1 et h J. S i i l n 'exis te aueun
arc entre I e t J alors on associe un arc de longueur
infinie darts H. L 'a rbre min imal dans H a une longneur s et si s
est inf~rieure h la somme des longueurs des arcs issus de i dans l 'arbre calcul~ sur G, alors il est intdressant
(*) Un point pendant est un point de degr6 1.
A. T~LI~C., 28, n o' 1-2, 1973 6/16
J . G R A S S I N . -- 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 D O N N E E S 9
d'61iminer i ; on r a j o u t e a lors les arcs de l ' a r b r e
m i n i m a l calcul6 sur H.
L ' e x e m p l e s u i v a n t va i l lus t re r la p r o c 6 d u r e de
r6duc t ion .
E x e m p l e 2. Soi t le g r a p h e de la f igure 5 ; le t a b l e a u I
d o n n e la m a t r i c e des l ia isons .
TABLEAU I
Malrice des liaisons du rdseau de la figure 5. Une case vide dquivaut ~ une absence d'arc
0
11
12
23
9 11
0 5
5 0 6
6 0
16
8
13
3
16
12
17 9
13
23
4
17
2 9
0 10
10 0
2
9 5
1 3
3 4
5 8
12
2 7
Fro. 5. - - Graphe d'un r6seau h 8 nceuds. On donne tableau I la matriee des arcs existants.
Le r6seau c o m p r e n d 8 nceuds , N : 8, e t les nceuds 4
e t 5 s o n t f acu l t a t i f s . L ' a r b r e m i n i m a l (Fig. 6 a) es t
2
5~
[ I ~ 2 6 7
0
2
9 S
I 3
4 8
6 )
b
4r..- s I J
Z2 c
2
9 S
I
6 J 2 , 7
e
9 / / d
Z2
Fro. 6. - - Application de la m6thode de r6duction au graphe de la figure 5. a) arbre minimal de d~part L = 37 ; b) apr~s ~limination du nceud 5, L = 34 ; c) 61imination du nc~ud 4,
composantes Z 1 Z2; d) graphe H associ6; e) arbre r~duit.
7/16 A. TEL~fi., 28, n o' 1-2, 1973
10 J . G R A S S I N , - - O P T I M A L I S A T I O N D E S R ~ S E A U X D E D O N N / ~ E S
d 'abord rdduit par 61imination du noeud 5 de degr6 1
(Fig. 6b) .
La suppression de 4 e r ie deux eomposantes connexes
Z1 = { 1, 2, 3, 8} et Z ~ = { 6, 7} (Fig. 6c). Le graphe H
se r~duit ici ~ 2 nceuds z 1 et zz reli~s par un are de
longueur 9. L ' a rb re min imal est done eet arc lui-mdme
et done la liaison 6-8 de longueur 9 permet de rdtablir
la eonnexit~ et de d iminuer la longueur de l ' a rbre
de 5 unit6s, ear la somme des longueurs des arcs issus
de 4 est ~gale h 14.
La rdduetion de l ' a rbre se te rmine soit par 6puise-
men t des nceuds facultat ifs , soit parce que la suppres-
sion des noeuds facul tat i fs res tan t n 'am~liore pas
la longueur de l 'arbre.
Cette mdthode de r~ductiou donne d 'excel lents
rdsultats en pra t ique m~me pour des pet i ts r~seaux.
II.6. D6terminat ion d'un ensemble E~.
Apr~s r6duction de l 'arbre, on oriertte celui-ci en
r emon tan t des extr6mit~s vers le CT~ qui est la racine.
Chaque nceud pointe vers sort p~re OR son pr~ddces-
seur sauf le C T I qui ne pointe nulle part .
Dans l ' exemple prdcddent en p renan t le nceud 8
pour CTI, l ' o r ien ta t ion serait la suivante : Fig. 7.
2
3 8
FIG. 7. - - Orientation de l'arbre rdduit lorsque le CTI est en 8 : 2 a pour p~re 3 et 7 a pour p~re 6.
On proc~de alors au cumul des charges et des
t e rminaux en pa r t an t des extrdmitds pendantes de
l ' a rbre et en r emon tau t vers la racine. Par ce procdd6
on obt ient err ehaque nceud une charge eumulde c~
et un nombre de t e rminaux eumulds t~.
Soit Fl = { ] [ P E ~ (]) : i }. !
Alors c~= c l + ~ c~. j ~F~
j~F,
En un nceud pendan t c~ = cl et c 'est par ces nceuds-
lit qu ' i l fau t commencer le cumul.
Nous allons m a i n t e n a n t effectuer une par t i t ion
de l ' ensemble Q des nceuds res tants en deux sous-
ensembles 11 et I S.
11= {i ~ QI c~ <~ c M e t t'l ~ T M } ,
12 = Q - - 11 .
I1 faut noter au passage que l 'ensemble Ix n 'es t
jamais vide car il cont ieut au moins les rtceuds pen-
dants de l ' a rbre (on rappelle que pour un nceud pendan t
C~ : C t < C M e t t~ ~ li < TM ; cf. w II.1). La contra inte de charge est toujours prdsente
landis que T M peut ~tre infini. Su ivau t la na ture du
probl~me trai t6 on peut deviner laquelle des deux
contra intes est prdponddrante et par consdquent
adopter une priorit6 sur l 'ordre darts lequel ces
contraintes doivent ~tre satisfaites.
I . E x p l o r a t i o n d e I~. On d~termine tou t d 'abord le nceud k G 11 selon
l 'un des deux crit~res suivants :
a) si la contra inte de charge est la plus s6v~re
alors k est tel que :
C' C' t' " ,~ = Max I , et ~ <~ T M , i ~ I 1
b) si la contra inte sur les t e r m i n a u x est la plus
s6v~re alors k est tel que :
t' ( ' k = Max , , et ck <~ C M . iG I x
L 'ensemble E~ d~fini par k et tous ses descendants
satisfait done h la lois Ia cont ra in te de charge et celle
re la t ive aux te rminaux.
Tr~s souvent et l 'exp6rience l 'a montr6, il est
possible d ' ident i f ier un ensemble Ek meil leur du
point de r u e de la charge to ta le ou des t e rminaux ,
en explorant l 'ensemble 12.
2. E x p l o r a t i o n d e I2 .
Supposons tou t d ' abord que la contra in te sur les
t e rminaux soit la plus sdv~re et soil l ~ 12 et q l ,
q2, ..-, q~ ses p descendants immddiats, l e t ses p
descendants forment un ensemble que nous appe-
lerons F.
F - ~ { l, ql , q2 . . . . . qp } .
Associons h k, ses param~tres propres cz et h e t i p
aux qi leurs param~tres cumulus Cql et tqi. On obt ient t t t ainsi deux ensembles F 1 : { cl , Cql , Cq2 . . . . Cqp } et
t ~] t 172= { Q ' t q l ' q 2 ' " ' ' t q p } "
I1 existe au moins une combinaison d'~l~ments
de F~ den t la somme S 2 est au plus ~gale h T M , et
telle que la somme S 1 des ~ldments ~quivalents dans
F 1 soit au plus dgale h CM. On leur associe bien
entendu la m~me combinaison dans F.
Exemple : le po in t I seul est tel flue tz ~< T M et
Cl ~ CM.
E n supposant que nous ayons donn~ la plus grande
priorit~ h la contra inte sur les t e rminaux nous cher-
cherons la combinaison d'~l~ments de F 2 telle que
la somme S 2 soil max imale avec S 2 <~ T M , et que
la somme S 1 correspondante v~rifie S 1 <~ C M . On fai t ensuite var ier l dans 12 et si la meil leure
! somme t rouvde S 2 vdrifie S 2 ~ I k , on a donc t rouv6
un ensemble El meil leur que l 'ensemble E k , ~ savoir
que le nombre de t e rminaux contenus darts Ez est
supdrieur h celui de E k . La charge totale de El est
admissible.
A. T~L~c., 2S, no' 1-2, 1973 8]16
J . G R A S S I N . -- 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 D O N N t ~ E S 11
3. Exemple.
Dans le r6seau h 8 po in t s de la f igure 8, le {2TI est
s i tus en 5. E n c h a q u e nceud on repr6sen te la charge
ts0 ,C. / 2 ~.7 _2 3
o
100 8] 70 /-2 / f : > . . ~ 58o ~ . ~ . ~
220 ,( 6 5
b
7
3
Fro. 8. - - Prineipe du eumul de charges : a) le CTI est en 5, h ehaque n~eud on assoeie C l et ti, exemple : C~ = 110, t~ = 2 ; b) 6tats des noeuds apr~s eumul, exemple : C' a = 250, t ' a = 5 ; c) E~ est le meilleur ensemble du point de rue du
nombre de terminaux.
p r o p r e p a r un n o m b r e en i t a l i que et les t e r m i n a u x
p a r uu n o m b r e en i t a l ique soulignS, f igure 8 a, e t les
m~mes q u a n t i t 6 s cumulSes , f igure 8 b.
Supposons que C M = 500 e t T M = 10. OI1 vSri-
f iera que 1 1 = {1, 2, 3, 6, 7, 8} et I S = {4,5}. t i !
O n a t 3 : { s = 5 = M a x ti, i ~ : I 1
' = 250 C 3
' = 220 C6
L ' e x p l o r a t i o n de 12 nous c o n d u i t h :
F = { 4 , 3 , 6 } ,
l = 4 : F 1 = { 1 1 0 , 2 5 0 , 2 2 0 } ,
F 2 = { 2 , 5 , 5 } .
L a me i l l eu re c o m b i n a i s o n est {3,6}, car
S 2 = 5 + 5 = 1 0 e t S 1 = 4 7 0 ,
F = { 5 , 4 , 7 , 8 } ,
l - - 5 : F 1 = ( 0 , 580, 150, 7 0 } ,
F 2 = { 0 , 12, 3 , 2 } .
La me i l l eu re c o m b i n a i s o n est {7,8}, car $ 2 =
3 + 2 = 5 e t S1 = 220.
U n e c o m b i n a i s o n te l le que {4,7} v io le en effet les
d e u x c o n t r a i u t e s e t do i t donc 6tre rejetSe.
L a mei l l eu re de t o u t e s les combina i sons est o b t e n u e
p o u r l = 4.
Ou v o i t que S 2 = 1 0 > t ~ = 5.
L ' e n s e m b l e E r e t e n u est l ' en semb le E 4 , qui c o n t i e n t
t o u s l e s d e s c e n d a n t s du uceud 4. Le noeud 4 n ' i n t e r -
v e n a n t pas dans la combina i son o p t i m a l e , on le
dSdouble en 4' e t 4". On affecte la charge e t les te r -
m i n a u x de 4 ~ 4", t and i s que 4' est un uceud f a c u l t a t i f
p e r m e t t a n t de conse rve r la connex i t6 du r6seau. I1
p o u r r a 6 v e u t u e l l e m e n t e t re supp r im6 p a r la sui te .
11.7. D6termination du r6seau multipoint pour un ensemble E~.
1. Procedure directe.
La p r e m i e r e pa r t i e de l ' h e u r i s t i q u e eons i s t a i t h sSlee-
t i oune r un ensemble Ek(*) sa t i s fa i san t une c o n t r a i n t e
de cha rge e t une e o n t r a i n t e sur les t e r m i n a u x . Les
EXTL de Ek p e u v e n t done 6tre eonnee t~es sur une
m ~ m e l igne qu i do l t sa t is fa i re la e o n t r a i n t e des
t ro is troa~;ons. N o u s al lons vo i r c o m m e n t rSpondre
h ee t t e ex igenee clans les p a r a g r a p h e s qu i su iven t .
Duns l ' a r b r e m i n i m a l prSeSdent , les ares qui r e l i en t
les po in t s de Ek ne c o n s t i t u e n t pus nSees sa i r emen t
l ' a r b r e m i n i m a l p o u r Ee.
N S a n m o i n s on u t i l i se ee sous -a rbre e t on le r~du i t
6 v e n t u e l l e m e n t p a r 61iminat ion de p o i n t s f aeu l t a t i f s
te ls que 4' (ef Fig. 8 e). Les nceuds de E~ son t ensu i t e
classSs p a r d i s t ance c ro i ssan te au CTI, OU de fa~ort
6 q u i v a l e n t e p a r eof l t de l ia ison croissant .
Si en r e l i an t le p r e m i e r nceud au CT~ le rSseau o b t e n u
sa t i s fa i t la e o n t r a i n t e des t ro is t ron$ons , on eonsidbre
que e ' e s t le rSseau optimal p o u r l ' e n s e m b l e Ek. Duns
le eas eon t r a i r e on r e c o m m e n c e a v e c le deux iSme
rtoeud e t ainsi de suite.
I1 es t tr~s poss ible qu ' ap r~s e x a m e n du de rn i e r
noeud aueun rSseau rSal isable , e ' e s t -h -d i re vSr i f i an t
la e o n t r a i n t e des t ro is t ron~ons , n ' a i t 6t6 t rouvS .
D e v a n t ee e o n s t a t d 'Schee, assez ra re en p r a t i q u e
fo r t h e u r e u s e m e n t , on a reeours h une p r o c e d u r e
spSeiale, fondSe elle aussi sur une n o t i o n d ' a r b r e
m i n i m a l .
A v a u t de p o u r s u i v r e ee t t e p r e s e n t a t i o n il se ra i t
b o a de se poser la q u e s t i o n s u i v a n t e : E x i s t e - t - i l
en t re t o u t p o i n t du r~seau e t le CTI, au m o i a s un
e h e m i n de l o n g u e u r t ro is ou moins (la l o n g u e u r es t
pr ise ici au sens du n o m b r e d 'a res ) ? I1 es t t r & faci le
(*) I1 s'agit du meilleur ensemble trouv6 ~ l'issue des explorations de I t et de I S .
9/16 A. T ~ L i c . , 28 , n o* I - 2 t 1 9 7 3
12 J. ORASSIN. -- OPTIMALISATION DES R]~SEAUX DE DONNI~ES
d ' imaginer des graphes G pour lesquels la rdponse h cette question est ndgative. Alors le probl~me du r6seau mul t ipo in t n ' a pas de solution.
Dans la rdalitd il n ' e n est pas ainsi bien que G ne
soit pas complet.
2. Proc6dure sp6ciale.
Au prdalable nous allons rappeler et poser quelques ddfinitions [5].
- - O n appeUe ~carl des noeuds i et j le nombre
m i n i m a l e (i, j) d'arcs d 'un chemin reliant i ~ ].
- - On appelle ~cartement d 'un nveud i la quanlil~
e i ( i ) = M a x e (i, j). J
- - S i le graphe esl connexe alors e i (i) est f ini pour
tout i. On appelle centre du graphe tout noeud dont
l'dearlemenl est m i n i m a l .
- - On appellera ordre d 'un nceud dans un rdseau
mul t ipo in l le nombre de tronr [ormanl le chemin
qui le relic au CT1.
E n imposant h l 'ordre d ' u n noeud quelconque d'dtre au plus dgal ~ 3, la cont ra in te des trois tron~ons
est satisfaite.
- - L e graphe n'~lant pas complet on rajoule des
arcs, que l'on appelle fictifs, entre les couples de points
non relids par un arc direct.
Afin de rendre le rdseau phys iquement rdalisable ces liaisons fictives sont construites au plus court
chemin (au sens des longueurs, donc des coflts). Consid~rons donc l 'ensemble Ee pour lequel nous
n ' avons pus pu t rouver de r6seau mul t ipo in ts par la proc6dure prdc~dente. Nous allons essayer de g~n~rer d i rectement un r~seau mul t ipoin ts pour E~, qui satisfasse la cont ra in te des trois tron~ons. Les autres contra intes sont ddj~t satisfaites de par
le choix m~me de E~. Soit donc G 1 le graphe constitu~ par les noeuds de
E~ et les ares de G rel iant ces noeuds. G~ lui est u n graphe ayan t les m~mes nceuds et les m~mes ares que G i , mais compldtd par les arcs fictifs.
a) Arbre pseudo-minimal .
Pour construire le rdseau qui est un arbre nous allons modifier quelque peu l 'a lgori thme de Pr im [4, p. 23]. Cet algori thme pe rme t t an t de calculer ua arbre min imal fonct ionne comme suit.
P a r t a n t d ' u n noeud on le relic ~ son plus proehe voisin. Ces deux noeuds ainsi que l 'arc qui les relic cons t i tuen t une composante connexe. On ra joute
ensuite le nceud le plus proche des nceuds de la
composante connexe et ainsi de suite jusqu'fi ce qu'elle renferme tous les nceuds. On poss~de alors l 'arbre
minimal . On est obligd de modifier l 'a lgor i thme prdcddent
pour t rouver un arbre vdrif iant la cont ra in te des trois tron~ons et de ce fait nous appelerons arbre pseudo-minimal , APM, l 'a rbre ainsi trouvd.
Le noeud choisi comme nceud de ddpart sera relid d i reetement au CTI, et a donc un ordre dgal h 1, h
moins que le CT 1 fasse part ie de Ek auquel cas le c m e s t
choisi comme nceud de d~part(*) et son ordre est dgal 0. Pour pouvoir ra jouter un noeud h la composante
connexe au cours de l 'a lgor i thme il faut que l 'ordre r~sul tant du noeud soit au plus dgal h 3.
On voit bien que pour certains graphes G1, il serait impossible de relier certains nceuds. C'est pour cette raison que le calcul de l ' a rbre est effectud sur G~.
b) Choix du neeud de d~part.
Si le CTI ne fait pas par t ie de l 'ensemble Ek , on peut envisager, successivement pour chaque nceud pris comme naeud de ddpart , de calculer I'APM, d'amdliorer cet arbre par les procddures ddcrites plus loin et de conserver le meil leur rdseau obtenu. Ces caleuls r i squent d 'etre longs, sur tout si Ek cont ient
beaucoup de noeuds et il est donc raisonnable de ne considdrer q u ' u n ensemble r6duit de nceuds de ddpart possibles. I n tu i t i vemen t on est condui t i~ choisir un nceud tel que le hombre d 'arcs n~,cessaires pour a t te indre tou t autre nceud soil aussi faible que pos-
sible afin d 'avoir les plus grandes chances de satisfaire les contraintes des trois tron~ons.
Les centres d ' u n graphe possSdent prdcis6ment cette propridtd et c 'est eux que l 'on utilise en prat ique.
Ils sont ddterminds ~ par t i r de G i.
c) Premi t re amdlioration de l'arbre pseudo-min imal .
L'APM a ya n t dtd calculd par la mdthode prdcd- dente il se peut qu ' i l cont ienne des liaisons fictives que nous allons chercher h dliminer. Cet arbre est
orientd en p renan t le CTI pour nceud puits (**).
Pour s impl i fer l 'exposd, nous allons raisonner sur
un exemple, celui de la figure 9.
Soil en E e t B relids par un arc fictif duns AP, B dtant le p~re de E et soil D l e successeur immddiat de E sur le plus court chemin de E h B. En t re E e t D il existe doric un arc direct. A est le p~re de D et I est un nceud directement relid au CTI c'est-~-dire un nceud d 'ordre 1.
das ddsignant la longueur de l 'arc ~ si
dDE+ did ~ dDA + dEB alors on am61iore ta longueur de l 'arbre en rel iant d i rectement D h I e t E h D. On v6rifiera que l 'ordre des nceuds reste toujours au plus 6gal h 3 et que le nombre d 'arcs fictifs ne peut que diminuer .
(Cette proeddure n ' e s t pas applicable darts t o u s l e s eas en part ieulier si l 'ordre des p~res de D et E est
6gal ~ 0 ou ~ 1.)
On applique eette mdthode jusqu 'h ee qu ' i l ne soit
plus possible d'a.mdliorer la longueur de l 'arbre. Les points pendants faeultatifs, s i i l y en a, sont
alors 61imin6s.
(*) Le CTI est en effet le seul nceud de ddpart possible duns ce cas lh car autrement on aurait un rdseau boucld. (**) On appelle nceud puits un n~ud destinataire du riot
du trafic. On a rajout4 la liaison entre le nceud de ddpart (nceud d'ordre 1) et le aT1 au cas off ce dernier ne fait pas partie de l'ensemble E k .
A. T~L~C., 28, n ~ 1-2, 1973 10/16
J . G R A S S I N . -- O P T I M A L I S A T I O N D E S R E S E A U X D E D O N N ~ E S 13
••, C I C
A A
\ I
D E D E
FIG. 9. - - Exemple d'application de la procedure sp6ciale ; les arcs fictifs sont inscrits en pointill6s.
d) Deuxi~me amdlioration de l'arbre pseudo-minimal.
A l'issue de la premiere amel iorat ion on ra joute
le CTI h l 'ensemble E k , s'il n ' y ~tait pas dSjh. On
essaie d 'am~liorer le r~seau precedent :
- - soit en r a t t achan t d 'aut res nceuds de E~ par
un are direct (non fietif) au CT~;
- - s0it en r a t t a chan t des points d 'ordre 2 ou 3 h des points d 'ordre inf~rieur.
Le ealcul de I'AeM et les deux ameliorat ions sont
effeetu~s successivement pour chacun des centres
et le meil leur r~seau obtenu est conserve.
La m~thode ne garant i t pas l 'absence d 'arcs fictifs
dans la solution finale, nSanmoins dans t o u s l e s
exemples trait~s jusqu 'h present le r~seau final ne
eontenai t aueun are fietif. Un examen manuel de la
solution serait n~eessaire dans le eas off le rSseau
compor te ra i t au moins un are fictif.
D ' au t re pa r t nous avons remarqu~ que le recours
h eet te procedure sp~ciale est assez rare (environ
10 % des eas).
II.8. Elimination de l'ensemble K~.
Le r~seau mul t ipo in t relat if ~ Ek ayan t 6t~ ealcul~
on ~limine l 'ensemble Ek, on me t fi jour les param~tres
eumut~s en chaque nceud de l ' a rbre de depar t et l 'on
recommence la d~terminat ion d 'un autre ensemble
E~ et ainsi de suite jusqu 'h ~puisement des no~uds.
Le eoflt des liaisons terminales est ensuite eorrig~
lots de l '~dition des r~sultats.
III. B~SEAUX AVEG CONGENTBATEUBS
III.1. Traitement g6n~ral de ces r6seaux.
Nous avons vu (of. w 1.6) que l 'on ava i t deux types
de r~seaux possibles h la fois pour la par t ie amon t
et pour la part ie aval. Dans l 'opt imal isa t ion, il est
n~eessaire de prendre en compte ~ la lois le coflt
des lignes et eelui des coneentrateurs . Bien entendu
au vu des corLtraintes propres aux eoneentra teurs ,
telles que le nombre max ima l de t e rminaux qu' i ls
peuven t g6rer, il faut un hombre minimal de coneen-
t rateurs . Un objeetif pourra i t consister h minimal iser
le nombre de eoncentra teurs mais le coflt du r6seau
de dis t r ibut ion c'est-~t-dire du rdseau aval est prepon-
derant (c 'est une propri~t~ classique de r~seaux dans
les probl~mes de r~seaux t~l~phoniques).
Une opt imal isa t ion direete et globale de t o u t le
r~seau, m~me dans le cas r e l a t ivement simple d 'un
r~seau point h poin t amont et point ~ poin t aval,
est done re la t ivement diffmile ~tant donn~e sa complexitY.
Cette diffieult~ nous a condui t ~ l ' approehe suivante
en deux phases.
1 re phase : D~terminat ion du r~seau aval en utili-
sant la capaeit~ des eoneentra teurs au mieux, ce qui
ind i rec tement rev ien t h minimaliser leur nombre.
Dans cette premi6re phase la posit ion des eoncentra-
teurs n 'es t pas impos~e a priori.
2 e phase : A par t i r des eoneentra teurs d~termin~s
h la phase I on optimalise un iquemen t le r~seau amont .
III.2. Calcul du r6seau aval.
Le pr6 t ra i t ement des donn6es est le m~me que
clans le cas mul t ipo in t ; il sutiit de remplaeer le t e rme
de ligne directe par concent ra teur ra t tach~ en ligne direete au CTI.
Ce p r6 t ra i t ement effectu6, il impor te de d6terminer
le meil leur r6seau pour les t e rminaux restants . Comme
le r6seau de dis t r ibut ion est par essence m~me assez
coflteux, il importe de ra t t acher des points voisins
autour d 'un m~me eoneentra teur . Ce regroupement
est effectu6 d 'une fa?on similaire au cas mul t ipo in t
fi savoir que l 'on eherche le meil leur ensemble Ek
de nccuds sat isfaisant les contra intes propres au
coneent ra teur (cf. w II.6).
Ayan t d6termin6 un ensemble Ek de nceuds il
reste done h loealiser au mieux le concentra teur . Pour
11/16 A. T~L~C., 28, n oa 1-2, 1973
] 4 J . GRASSIN. -- O P T I M A L I S A T I O N DES R ~ S E A U X DE DONNI~,ES
ce faire, nous allons dist inguer le cas point h point du cas mul t ipoin t .
1. Rdseaa aval point d point.
Pour un tel r6seau, le hombre de lignes aboutis- sant au concent ra teur est 6gal au nombre d 'extr~mit6s de ligne de l 'ensemble Ek. Consid6rons le barycent re g6ographique B~ des nceuds obligatoires de Ek , chaque
nceud 6tant pond6r6 par le hombre d 'extrdmit6s de lignes situ6es en ce nceud. Soit B le c~ le plus proche de B 1 . Consid6rons le cercle de rayon R centr6 en B, tels que tous le s nceuds de Ek soient situ6s h l ' in t6r ieur de ce cercle. On pourra prendre pour R la plus grande
distance de B aux points de Ek, major@ de 10 % par exemple.
Chaque c~ situ6 h l ' in t6r ieur du cercle est un emplacement potent ie l pour u n concentrateur . Cela restreint consid6rablemeut l 'ensemble des positions possibles pour le concentra teur , mais il serait stupide par exemple lorsque les t e rminaux sont situ6s duns la r6gion de Marseille-Nice et que le CTI est h Paris,
d ' implan te r un concent ra teur h Brest auquel on relierait ces te rminaux.
I1 suffit ensuite de calculer le cotit du r6seau pour clmcune des posit ions potentielles. L '6num6ra t ion est toutefois appr6ciablemeut r~duite en p a r t a n t de B, qui est gdnSralement tr6s voisin de la position optimale. Darts le calcul du r6seau, on t ient compte du cotit de la liaison h haute vitesse concentrateur-cTi. Le meilleur r6seau t rouv6 est conservC
On est done ramen6 au calcul d ' u n r6seau point h point ou d ' u n r6seau mul t ipo in t , ce que nous savons faire.
IV. R ] ~ S U L T A T S . E X E M P L E S
IV.1. R~sultats pratiques.
Un des buts de cette 6tude 6tait de pouvoir calculer un certain nombre de r6seaux tr~s rap idement afin d'effectuer des comparaisons sur le cofit des diff6- rentes structures.
Pour une appl icat ion compor tan t u n millier d ' E X T L ,
le calcul d ' u n r6seau mul t i po in t n6cessite envi ron 10 h 15 secondes de temps de processeur, celui d ' uu r6seau avec concentra teurs ~ s t ructure mul t ipo in t en amon t et en aval demande envi ron 60 h 90 secondes (*).
D 'une fa~on g6n6rale nous pouvons dire que le temps du calcul ne croit que tr~s fa ib lement au-delh de 300 ~XTL. En effet au fur et h mesure que le nombre des EXTL augmente , on est condui t ~ installer de
plus en plus de lignes directes et dans t o u s l e s cas le hombre de nceuds p o u v a n t in te rveni r dans le graphe G ne peut pas d6passer 230 (cf. w 1.11) ce qui l imite ipso /acto le temps de calcul.
IV.2. Valeur des solutions obtenues.
2. R~seau cwal multipoint.
De m6me que pour u n r6seau point h point , on
d6termine le barycent re B I des nceuds et le nceud B (*) de E~ le plus proche de B 1. La d~terminat ion de l 'ensemble des emplacements possibles du concen- t r a teur est similaire.
La suite de la proc6dure consisterait h d6terminer pour chaque posit ion du concent ra teur le meilleur r6seau mul t ipo in t , le concent ra teur j ouan t ici le rSle du CwI. Cette m6thode serait lourde en pra t ique et on pr6f6re utiliser une bonne 6valuat ion du cotit du r6seau mul t ipo in t pour chaque posit ion du concen- t rateur . Cela nous permet de d6terminer la posit ion du concentra teur et d 'opt imaliser le r6seau seulement pour cette position.
Apr6s 61imination de E~, la suite de la m6thode ressemble en tous points ~ celle du paragraphe II.
111.3. Calcul du r6seau amont.
Le r6seau amon t utilise comme donn6es les posi- t ions et les caract6ristiques des concentra teurs trouv6s lors du calcul du r6seau aval.
(*) A la diff6rence du cas point h point, B n'est pas un cA quelconque mais un nceud de Etc. Ce choix permet en effet de calculer une bonne 6valuation du cofit du r~seau multi- point associ6 ~ chaque position possible du concentrateur.
Bien que le temps de calcul soit r e la t ivement faible quel cr6dit pouvons-nous accorder aux r6sultats fournis par les m6thodes heurist iques pr6c6dentes ?
Duns le cas des r6seaux mul t ipo in t s nous avons proc6d6 ~ de nombreuses comparaisons entre u n r6sultat heurist ique et un r6sultat obtenu ~ la main par un sp6cialiste, ceci pour des r6seaux compor tan t jusqu '~ 50 terminaux. La comparaison a toujours 6t6 en faveur de la m6thode heurist ique : l 'am61ioration tr6s 16g~re pour les peti ts r6seaux peut a t te indre parfois 10 h 15 %.
Pour de tr6s grands r6seaux, tels les r6seaux bancaires compor tan t plusieurs milliers de t e rminaux une telle comparaison n ' a h vrai dire jamais pu 6tre faite, ou tou t du moins il serait peut-6tre possible de la faire une lois mais cer ta inement pus plusieurs.
Tou t en fournissant des solutions meiilcures que
celles obtenues ~ la main, le r6seau t rouv6 est-il proche de l ' op t imum ? Pour r6pondre h cette question nous avons consid6r6 u n r6seau avec concentra teurs po in t h point amon t et aval, compor tan t environ 5 0 EXTL.
Ce probl~me peut ais6ment ~tre formul~ comme un programme lin~aire en nombres entiers. Afin de rSduire la taille du probl~me, chaque EXTL ne pouva i t etre reli6e qu h u n concent ra teur ct u n seul (bien stir)
situ6 dans un cA parmi les 30 plus proches de I'EXTL.
(*) Sur un HB 635.
A. T~L~C., 28, n a* I-2, 1973 12/ i6
J . GRASSIN. -- O P T I M A L I S A T I O N D E S R~ .SEAUX D E D O N N ~ E S 1 5
Nous a v o n s aussi pr is en c o m p t e les c o n t r a i n t e s
p r o p r e s a u x c o n c e n t r a t e u r s (cf. w 1.6 c). Le p ro-
g r a m m e lin~aire o b t e n u c o m p o r t a i t 1 700 va r i ab l e s
eutiGres d o n t 1 500 boolGennes e t 500 c o n t r a i n t e s . Le
code de p r o g r a m m a t i o n linGaire U M P I R E (*) a 6t6
ut i l is6 p o u r sa rGsolution.
La so lu t ion c o n t i n u e , e x t r e m e m e n t f r a c t i o n n a i r e ,
a 6t6 o b t e n u e au b o u t de 300 s econdes s e u l e m e n t (*).
Apr~s 1 heu re de calcul , nous a v o u s o b t e n u d e u x solu-
t i ons rGalisables s e u l e m e n t , la me i l l eu re d ' e n t r e elles
6 t a u t 17 % m o i n s b o n n e que la so lu t i on h e u r i s t i q u e
trouvGe elle en 40 secondes (**). B ien stir l ' o p t i n m m
TA.BLEAU I I - Liste des E X T L et de leurs caractdristiques
Nora de I 'EXTL Terminaux Charge
ALBI 1 26 ANGOUL~ME 1 '70 BAYONNE 1 40 BOaDEAUX 1 170 CARCASSONNE 1 70 CLERMONT-FERRAND 1 40 CLER1V[ONT- SERA C 1 10 CONDOM 1 50 LIMOGES 1 35 MONTAUBAN 1 40 MONTPELLIER 1 40 Pt~u 1 50 PERPIGNAN 1 80 ST G~UDENS 1 25 TOULOUSE 1 170 Tovns 1 80 ORIA~ANS 1 50 BREST 1 60 LE MANS 1 50 NANTES 1 100 PtENNES 1 100 ANNECY 1 100 AVIGNON 1 100 BOURGES 1 70 CANNES 1 30 GRENOBLE 1 180 LYON 1 240 MARSEILLE C 1 200 MARSEILLE P 1 25 NtcE 1 85 NIMES 1 40 ST ]~TIENNE 1 70 ST RAPr~A~L 1 40 TOULON 1 50 VALENCE 1 30 AMIENS 1 110 BOULOGNE SUP, MER 1 70 CAEN 1 90 CHARLEVILLE - MEZII~RES 1 10 CHATEAU-THIERRY 1 10 LE HAVRE 1 10 LENS 1 160 LILLE 1 300 REIMS 1 10 ROUEN 1 150 ST QUENTIN 1 10 VALEN CIENN ES 1 120 AUXERRE 1 80 BAR LE DUC 1 10 BESAN~,ON 1 40 D~JON 1 10 FORBACH 1 70 METZ 1 125 MULHOUSE 1 100 NANCY 1 90 STRASBOURG l 100 TROYES 1 10
(*) Sur un UNIVAC 1108. (**) Sur un HB 635.
n ' ~ t a i t pa s encore a t t e i n t m a i s t o u t le m o n d e sui t
que les de rn i e r s % e t la vGrif icat ion de l ' o p t i m a l i t 6 s o n t
trSs co f l t eux en p r o g r a m m a t i o n en h o m b r e s en t i e r s .
AprGs une te l le expGrience nous p e n s o n s p o u v o i r
a f f i rmer que les r~su l t a t s fou rn i s p a r les mG t hodes
h e u r i s t i q u e s s o n t p r o c h e s de l ' o p t i m u m . D u n s t o u s
ces p r o b l b m e s l ' o p t i m u m es t v r a i s e m b l a b l e m e n t
trGs p l a t 6 t a n t d o n n 6 les n o m b r e u s e s v a r i a n t e s o b t c -
hues m a n u e l l e m e n t ~ p a r t i r de la so lu t ion h e u r i s t i q u e .
IV.3. Exemples de r6seaux.
Le problGme c i -dessous es t e x t r a i t d ' u n e x e m p l e
rGel. N o u s al lous s u c c e s s i v e m e n t considGrer un rGseau
m u l t i p o i n t e t u n rGseau avec c o n c e n t r a t e u r p o i n t h
p o i n t a m o n t e t p o i n t h p o i n t ava l h t i t r e d ' i l l u s t r a t i o n .
Le t a b l e a u II d o n n e la l is te des EXTL a v e c l eu rs
ca rac tGr i s t iques . Le t a b l e a u I I I d o n n e les v a l e u r s
TABLEAU III - - Valeurs des C M el T M
Multipoint . . . . . . . . . . Concentrateur . . . . . . .
CM T M
1 200 15 4 800 15
de C M e t TM p o u r le rGseau m u l t i p o i n t e t p o u r le
rGseau avec c o n c e n t r a t e u r . Les unitGs de c h a r g e s s o n t
i d e n t i q u e s darts le t a b l e a u II e t d a n s le t a b l e a u I I I .
Les EXTL s o n t reprGsentGes sur la f igure 10. D a n s le
rGseau m u l t i p o i n t de la f igure 11, on p e u t se d e m a n d e r
p o u r q u o i ANNECY es t r a t t a c h 6 h BESANOON p l u t b t
q u ' h VALENCE (la l ia ison ANNECY-VALENCE 6 ran t
p lus 6conomique) . La l igne PARIS-AVIGNON a y a n t
une cha rge de 1 140 unitGs, la cha rge s u p p l G m e n t a i r e
(100 unitGs) d'ANNECY fe ra i t d~passe r la v a l eu r de
1 200 unitGs de C M .
E n a u g m e n t a n t d ' a u m o i n s 40 unitGs la v a l eu r de
C M on p o u r r a i t e f fec tuer ce b a s c u l e r n e n t . Mais a lors
il s e ra i t poss ib le de rel ier d i r e c t e m e n t DIJON h TROYES
e t d 'Gl imiuer la l i a i son BESAN~ON-NANcY en r e l i a n t
BESANOON h DIJON, ce qui d i m i n u e r a i t encore le cofi t
du rGseau.
De m ~ m e duns le rGseau avec c o n c e n t r a t e u r s de
la f igure 12 il e s t imposs ib le de re l ier MONTPELLIER
au c o n c e n t r a t e u r d'AvIGNON car celui-ci e s t s a tu r6
du p o i n t de r u e des EXTL. P a r c o n t r e ANNECY es t
r a t t a c h 6 au c o u c e n t r a t e u r si tu~ ~t AVIGNON. Le fa i r
d ' a u g m e n t e r T M d ' u n e un i t6 p e r m e t t r a i t de re l ier
MONTPELLIER • AVIGNON et d o n c de g ag n e r sur le
c o o t des l igues.
V. SIMULATION
Les r~seaux o b t e n u s p e u v e n t ~tre en s u i t e s imul~s,
l ' e x c e p t i o n des r~seaux avec c o n c e n t r a t e u r s d o n t
13/16 A. TI~L]~C., 98, n ~ 1-2, 1973
16 J . G R A S S I N . - - O P T I M A L I S A T I O N D E S R ~ S E A U X D E D O N N I ~ E S
BOULOGNE ~.r o k 1 LLE ~300
~ 1' LENE o ^~,VALE.C,ENNEB / 160 ~. 120 I;t
/ , L . J I o !0 ~ MEZIERES
O St-QUENTIN O ~%. 1
1 - " 7 ,o [ .... ; 7 �9 I~ ~ . ~ E HAVRE ~ o "' ~ ~ FOREACH
ROUEN 1 ~ I~,~ O 1 CHATEAU O REIMS 10 ~ ~ - ~ k ~ . ~ -
- I 1 - - - 1 125 )
~ ~ { 90 PARIS ~ 10 BAR-LE.DUC " . ETRASEOURG , 1 1 1 of
50 TROVES o ( - ~ RENNES o LE MANE 1
, j o ~o I - - ~ . ]00 o MULHOUSE o !
a ORLEANS o 1 = ~ ' ~ ORLEANS AUXERRE 100 J
~ A N T E S TOURS OIJ(~N BE S2NCON " r
100 ou BOURGES 71 41/ /~
% , 1
ANGOULEME e
8ORDEAUX
CONDOM o
FI~. 10. - - R6part i t ion g~o- graphique des extr6mit6s de lignes. La charge est indi- qu6e par un nombre en ilali- que, le nombre de t e rminaux
en caract~res droits.
B A Y ~ . . ~
.75 1 1 LIMOGES 40 10
o CLERMONT FERRAND o
1 40
1 LYON 240
St-ETIENNE l o
70
VALENCE o 1
3O
ANNECY o 1 ~ ) soo t..
I
GRENOBLEo 1 f f ~ l
180 "' , t
? ()
1 MONTAUBAN ~ | 50 o 1 40 e AVIGNON 100
o ALB( 26 NIMES o ~ m ~ o~ 1 ~ 9
o MONTPELLIER o 3(] ~/CANNES
TOULOUSE 41 _ o
]70 CARCASSONN E * , i ~ " - ' - ~ ' ~ ~ _ ~ 40 PAU o 70 1 , S.-GAUOENS o / ~ - ~ '~O~L<~ <'~
% 50 1 4 ~ x.~*,, r 25 #1
~ ' ~ ' ~ ' ~ ) %'~" ~ PERPIGNAN o �9 - ~ . : 1:
la partie aval est en mul t ipo in t . Dans l 'opt imal i - sation on s '6tai t content~ de r6sumer les caract~ris- t iques de trafie d ' u n te rmina l dans un seul param~tre:
sa charge. Au niveau de la s imulat ion le degr6 de finesse
a t t e in t est sans comparaison. I1 est en effet n6ces- saire de pr6ciser les diff6rents types de messages 6mis et re~us, la d is t r ibut ion de leur longueur, les lois d'arriv6es, le mode de t ransmission, le type de proc6dure &inter rogat ion adopt6 sur chaque ]igne etc.
La s imulat ion du r6seau complet n ' es t envisageable que si ce dernier est pet i t disons jusqu '~ 100 te rminaux .
Au-delh, il est pr6f~rable de ne simuler qu 'une ou deux
lignes about issants au CTI. Les r6sultats nous renseignent sur le temps de
r6ponse, les files d ' a t t en t e au terminal , aux concen- t rateurs , sur la taille de la m6moire et la taille des buffers n6cessaires darts chaque concent ra teur etc.
Les param~tres de l 'opt imal isa t ion tels que la
charge maximale CM d 'une ligne ou le hombre maxi-
real de t e rminaux connectables T M sur une ligne peuven t 6tre modifi6s si par exemple le temps de r6ponse ne satisfait pas aux normes souhait6es.
On recommence alors l 'opt imal isa t ion avec les nouvelles valeurs des param~tres.
In i t ia lement ces param~tres peuven t 6tre estim6s h l 'aide de calculs de files d ' a t t en te ou m6me par de peti tes simulations.
V I . P R O B L ~ . M E D E L A S ~ U B I T ~ , ,
Jusqu 'h pr6sent, nous n ' avons pas 6voqu6 le pro- blbme de la s6curit6. Le ealcul direct d ' u n r6seau p renan t en eompte des consid6rations de s6curit6 est n e t t e m e n t plus diflicile. E n outre, la not ion de s6curit6 varie d 'une applicat ion fi l ' autre . Pour eer-
h. Tf~L~C., 28, n ~ i -2 , 1973 14/16
J. GRASSIN. -- OPTIMALISATION DES RESEAUX DE DONNI~ES 17
BOULOGNE V'~ | -"~.. LILLE/~ '~ ( L~N ;~ - - -- "'---'o ~ ALENCIENNES
AMIENS A ~ %
( CAiN ] / ~ REIMS J ' " % . . . . I ) ...... I / - _ MErZ .;
- - ~ ~ A S L / ~&%u BAR LEOUG _,~-.'-'-'~-*-,"~l,-' N ~ . . ~ O - ~ - - STRASBOURG /J
"~ . . . . . . . . . . . . . . . . . . . " ' ' ' ' " "" " ' ' ' ' ' " i . . . . . . . i RENNES " ' ' ' ' ' ' " / ~ , l ~ TROYES ~ ]
,-4 N..,.., ,., ~ LE ~ANS '\ ORLEANS \ / ,r ~'/(-~ �9 - ~ \ . " ] \ ~ MULHOUSE {
~ NT O O B ~ . . . . ! \ O ON EBANON
ANGOULEME CLERMONT-FERRAND LYON ANNEGY
Fro. 1 1 . - R~seau millipoint ~ , ~ \ ~ ~ s,- "~ obtenu par la m6thode heuris- (kX'~ \\ I ~ ?
\ I P ~IBORDEAUX \ , VALENCE " ' k
/ CO N OOM M 0 N~'~T A ~'B'~A\N~ / ~ ' - - ' ~ ~ ALBi NIMEB ~VIGNON . . . . ~1
J MONTPELLIE R BAYO,~.~>._~ / ~CARCASSONNE / / ~ / ~ ' l ~ \ ~.----"-- ~'
" ~ _ ~ St GAUOENS \ I~J TOL LON
~ f ~ PERPIGNAN
taines, u n arr~t d 'une heure est encore admissible pour d 'autres , aucune in te r rup t ion n 'es t tol6r6e.
a) S~curit~ par r~seau commute.
C'est un premier mode de secours envisageable. Si on se r6serve un certain hombre d 'entr6es par r6seau commut6 sur le CTI 0U sur les concentrateurs , elles peuven t alors 6tre utilis6es pour d6panner tem- pora i rement la part ic d6faillante du r6seau ~ condi- t ion bien en tendu que la rapidit6 de modula t ion uti- lis6e soit compatible avec les normes du r6seau commut6.
Le cofit d 'une telle s6curit6 est d6termin6 b. l 'aide des programmcs sp6cifiques au calcul des r6seaux
commut6s.
b) S~curit~ par boucles.
On peut envisager des r6seaux bouel6s ~, condit ion que les circuits physiques e m p r u n t e n t des supports diff6rents. Si dans la figure 13 les circuits CTI-A et
CTt-B sont pris sur le m6me efible par exemple et
si le c~ble est d6faillant la s6curit6 est nulle. Si le r6seau est r6alis6 en circuits 4 ills de qualit6 sup6- rieure la contra inte des trois tron~ons doit 6tre respect6e, ~ savoir que tou t te rminal doit pouvoir 6tre a t t e in t depuis le c m e n 3 tron~ons au plus quclle que soit la coupure darts la boucle.
Cette contra inte est relach6e pour les circuits 4 ills de qualit6 normale. E n prat ique, on l imitera n6an- moins le nombre de tron~ons h 8 au plus.
Ces r6seaux font l 'obje t d '6tudes h l 'heure actuelle.
VII . C O N C L U S I O N
Nous avons essay6 de pr6senter les mdthodes utilis~es pour le caleul des r6seaux de t~16informatique.
A c e s m6thodes d 'opt imal isat ion, il faut adjoindre les outils de ealeuls des confgura t ions Caduc6e,
r6seau eommut6, telex quc nous avons br i~vement 6voqu6 au paragraphe I e t dont nous n ' avons pas
15/16 A. T~L~C., 28, n ~ I-2, 1973
18
BREST
Cb
FIG. 12. - - R6seau avec con- centrateurs. Les D mat6ria- l/sent les concentrateurs. On remarquera les deux lignes issues de Marseille et de Cler- mont-Ferrand. En effet, on a 2 EXTL dans chacune de ces
villes.
J. GRASSIN. -- OPTIMALISATION DES RI~SEAUX DE DONNEES
BOULOGNE ~f~ E),\
/ \ LENS ~ / "~tVALENCIENNES
) ',, I/ / ~ : / "//./ L_-'
/.,,,~r...~:.S,..~[AMiE,S""o St-QUENTIN . ' . . . ...----- /" . ' MEZIERES
" ~ ~ / ROUEN ] CHATEAU REIMS \ ~ I:~RBACH
CAEN ' THIERRY ~ ' / ~ _ ~
PARIS ~ ~"
"~. ........ LE MANSes/" / RENNES . . . . . . . . . ~"~ "-7 ~'..'_- ." - . := ,* /
/ " ',,'-.. OR'EANB/
STRASBOURG
O r ~ MULHOUSE (, AUXERRE ~ ~ . ~ /
DIJON ~NCON /I
S S P
d ' S
NANTES
\ %'.. [
TOURS .
LIMOGES ANGOULEME
\\\
\\ I BORDEAUX \ "-.. \
CONDOM O.....
%o I BOURGES
MONTAUBAN
CLERMONT FERRAND LYON
i /
ANNECY ~ ( i
D ~ E . O ~ E ~
AVIGNON
) /
BAYONNE , / / / //TOULOUSE "% ~ /
~ _ . ~ St-GAUDENS
MONTPELLIER
,ER,IGN~ t TOULON
:.RAPHAEL
B
C
A
FIG, 13. - - S6curit6 par boucle.
6prouv6 le besoin de parler ici. Tous ces outils cons t i tuen t un ensemble de pro-
grammes que nous appelons O R T I (optimal/sat /on des r6seaux de t616informatique). Pour 6tre complet
il faudra i t a jouter h cela des programmes de calcul p r enan t en compte les probl~mes de la s6curit6 et aussi des outils de calculs pour les r6seaux inter ordinateurs.
ORTI a d6jh servi de nombreuses fois et pour des r~seaux de taille tr~s diff6rentes. Nous citerons par exemple la Banque Nat ionale de Paris, la Soci6t6
G6n6rale, le Groupe Drouot, la CAPA, P6troles BP, la MGEN, Air Inter , la Gendarmerie , SOFINCO,
les Gh6ques postaux.
Manuscrit rer le 22 novembre 1972
BIBLIOGRAPHIE
[1] GRASSIN (J.). Optimal/sat/on des r6seaux de trans- mission de donn6es h structure multipoint. Programme, REMU. Ann. Tdldcommunic., Fr. (janv.-f6vr. 1972), 27, n ~ 1, pp. 11-18.
[2] MARTIN (J.). T61dprocessing network organ/sat/on (Organ/sat/on du rdseau de tdldtraitement). Prentice Hall, U. S. A., (1970), 290 p.
[3] DREYFUS (S.E.), WAaN~a (R. A.). The Steiner problem in graphs (Le probl6me de Steiner dans la thdorie des graphes). 0.11. Center univ. o] Cali]. Berkeley, O.R.C. 7032 (sept. 1970), 20 p.
[~] Roy (B.). Alg6bre moderne et thdorie des graphes orient6s vers les sciences dconomiques et sociales. Dunod, Paris, tome t (1969), 502 p., tome 2 (1970), 753 p.
[5] BERG~ (C.). Th6orie des graphes et ses applications. Dunod, Paris, (1957), 278 p.
A. TI~L~C., 28, n ~ 1-2, 1973 16/16
