1

Dimensionnement et Routage Optimal dans lesAnneaux Haut-Débits SDH

, O. Brun* ,

LAAS-CNRS

Octobre1999

*LAAS-CNRS, 7 avenue du Colonel Roche, 31077 Toulouse Cédex

2

PLAN1. Introduction2. Présentation de SDH

2.1 Avantage de la technologie SDH2.2 Terminologie2.3 Fonctionnement des Réseaux SDH

2.3.1 Structures des Trames SDH2.3.1.1 La Trame STM-12.3.1.2 Les Trames STM-N2.3.2 Topologie des Réseaux SDH2.3.3 Composants des Réseaux SDH

2.4 La Sécurisation dans SDH2.4.1 Drag and Drop2.4.2 Protection SNCP2.4.3 Protection MS-SPRING

3. Notations et exemple test3.1 Notations3.2 Exemple test

4. Dimensionnement optimal de l’anneau4.1 Dimensionnement à capacités héterogènes4.2 Dimensionnement à capacités homogènes

5. Routage optimal dans l’anneau5.1 Maximisation de la capacité résiduelle totale5.2 Maximisation de la capacité résiduelle minimale

6. Prise en compte des mécanismes de protection SDH6.1 Notations6.2 Dimensionnement et routage avec MS-SPRING

6.2.1 Contrainte liée au reroutage MS-SPRING6.2.3 Problème de dimensionnement6.2.4 Problème de routage

6.3 Dimensionnement et routage avec SNCP6.3.1 Dimensionnement6.3.2 Routage

7. Conclusions

8. Bibliographie

3

1. Intr oduction

Du fait de la croissance soutenue du marché des télécommunications, les opérateurs ont sans cesse dû s’adapter à untrafic téléphonique toujours plus important. Cette croissance de la demande a été la source de nombreuses avancéestechnologiques permettant de répondre aux besoins de la manière la plus économique possible.

Ainsi a-t-on vu, à partir des années 60, le remplacement progressif des réseaux analogiques à multiplexage fréquen-tiel par des réseaux à modulation PCM (Pulse Code Modulation) qui permettent l’utilisation multiple d’une mêmeligne par multiplexage numérique temporel. Le signal téléphonique est alors échantillonné à une fréquence de 8 kHz,puis numérisé et codé sur 8 bits avant d’être transmis à un débit de 64 kbit/s. Le débit de transmission résultant, ditdébit primaire, est de 2048 kbits/s lorsque 30 canaux de communications sont ainsi multiplexés

Cependant, la demande toujours plus importante de bande passante a nécessité l’introduction de niveaux de multi-plexage supplémentaires, ce qui a conduit à la définition de la hiérarchie numérique plésiochrone PDH (Plesiochro-nous Digital Hierarchy). La définition de cette hiérarchie a été réalisée indépendamment aux Etats-Unis, en Europe etau Japon, ce qui rend très difficile l’interopérabilité des équipements. De plus, l’insertion et la suppression d’uncanal de 64 kbit/s au sein d’un niveau de multiplexage supérieur sont des opérations très coûteuses car elles requie-rent le démultiplexage puis le remultiplexage complet de toute la trame.

C’est vers la fin des années 80 qu’a été introduite la hiérarchie numérique synchrone SDH (Synchronous Digital Hie-rarchy). Cette technologie conduit à l’heure actuelle à la mise en place de réseaux (backbone) à très grande capacitédans beaucoup de pays. En particulier en France, les grands opérateurs de la téléphonie construisent leurs réseauxSDH qui sont un élément clé de l’infrastructure de transmission des autoroutes de l’information.

Le coût de construction de tels réseaux est très important. Il reflète à la fois les coûts de mise en place des liaisonsoptiques (tranchées sur des milliers de Km) et les coûts des équipements. Le coût de mise en place des liaisons est unproblème important pour la création de la topologie du réseau. Il s’agit en fait de savoir comment sont interconnectésles centres entre eux et combien de sous-réseaux sont créés. Le coût des équipements dépend d’une part de la tailledes services que l’on veut satisfaire et de la manière de dimensionner et router le trafic à travers la topologie définieau préalable. C’est ce problème qui est développé dans cette étude au moyen de modèles et techniques de program-mation linéaire, programmation linéaire mixte et de programmation non-linéaire.

Dans la section 2, nous présentons un résumé des éléments essentiels de la technologie SDH. Dans la section 3, nousprésentons les notations des variables des problèmes d’optimisation. Dans la section 4, nous montrons commentmodéliser et résoudre le problème d’optimisation linéaire pour des réseaux à capacités hétérogènes et des réseaux àcapacités homogènes. Dans la section 5, nous traitons le problèmelinéaire de routage pour deux types de critères(capacité résiduelle totale, capacité résiduelle minimum). Dans la section 6, nous introduisons les mécanismes de pro-tection du trafic dans les problèmes d’optimisation. Les problèmes linéaires d’optimisation du dimensionnement et duroutage sont de nouveau résolus avec les contraintes de protection introduites par SNCP et MS-SPRING. Finalement,dans la section 7 une discussion comparative des différentes solutions est présentée en conclusion de l’étude.

2. Présentation de SDH

2.1 Avantage de la technologie SDH

Par rapport à la hiérarchie PDH, les opérateurs espèrent les avantages suivants :

• Des Débits de Transmission élevés

La technologie SDH utilise des liens de communications optiques et offre des débits allant jusqu’à 10 Gbit/ssur une seule fibre, ce qui en fait une technologie particulièrement adaptée à la construction des réseauxdorsaux (backbones). Les développements récents des technologies de multiplexage de longueurs d’ondesWDM (Wavelength Division Multiplexing) permettent d’espérer très prochainement de disposer de réseaux

4

SDH offrant des débits de 40 Gbit/s, sur une seule fibre.

• Opérations d’Insertion/Extraction simplifiées

L’utilisation d’une technique de pointeur permet de réaliser ces opérations sans avoir à démultiplexer puisre-multiplexer la trame de transmission, comme c’était le cas dans les réseaux PDH.

• Disponibilité et Adaptation Dynamique des Capacités

Les opérateurs peuvent utiliser des composants réseaux standardisés qui peuvent être contrôlés et comman-dés de manière logicielle à distance (à partir d’un point central) en utilisant un système de gestion deréseaux appelé TMN (Telecommunication Network Management ).

• Fiabilité

Les réseaux SDH incorporent plusieurs mécanismes permettant de faire face à la défaillance d’un lien oud’un composant du réseau (SNCP, MS-SPRING).

• Inter connexion

Les interfaces des réseaux SDH sont normalisées internationalement, ce qui garantit l’inter-opérabilité (avecles réseaux SONET par exemple) et diminue donc les coûts.

5

2.2 Terminologie

2.3 Fonctionnement des Réseaux SDH

2.3.1 Structures des Trames SDH

2.3.1.1 La Trame STM-1.

La trame STM-1 (Synchronous Transport Module) correspond au premier niveau dans la hiérarchie numérique syn-chrone. Elle se présente sous la forme d’une matrice de 9 rangées de 270 octets dont la transmission s’effectue degauche à droite et de haut en bas. Chaque octet correspondant à un canal de 64 kbit/s, on obtient un débit global de155 Mbits/s.

La trame est composée d’une zone de surdébit de section SOH (Section Overhead) contenant des informations pourlles reegénérateurs et les multiplexeurs sur la route empruntée par la charge utile, appelée Unité Administrative AU(Adimistrative Unit).

Table 1: Acronymes importants dans SDH

Acronymes Définition

SDH Synchronous Digital Hierarchy

Anneau (boucle,Ring)

Ensemble d’équipements formant une boucle fermée, offrant une capacité de N trames SDHSTM-1 (notée STM-N)

Sous-réseau Anneau STM-N

Site Ensemble d’équipements de réseaux colocalisés géographiquement

STM-N Synchronous Transport Module d’ordre N (1,4, 16 ou 64). Il s’agit de la puissance de laligne de transmission.

VCn Virtual Container d’ordre n (12, 3 ou 4). Unité d’information contenue dans une trame SDH

ADM Add Drop Multiplexer

APS Automatic Protection Switching

DXC Digital Cross Connect ou brasseur. Equipement de réseau SDH possédant n*n ports STM-Net permettant d’échanger des conteneurs entre ces ports.

D&C Drop and Continue

LL Ligne louée

MS Multiplexer section

PDH Plesiochronous Digital Hierarchy

PPS Path Protection System

SNCP Sub-Network ConnectionProtection

MS-SPRING Multiplex SectionSharedProtectionRING

MRN MeshRestorableNetwork. Topologie d’interconnexion avec une ou plusieurs arêtes com-munes qui permet en cas de panne de rerouter le trafic bloqué.

LRM L ink RestorationMechanism. On considère des cas de panne où la connexion défectueuseest reroutée entre les deux sommets de l’arc considéré.

6

Dans une trame STM-1, la charge utile est placée dans desconteneurs adaptés à leur débit. Ces conteneurs peuventêtre vus comme une structure hiérarchisée de groupage. A chaque conteneur est associé un surdébit dénommé POH(Path OverHead) qui sert à gérer ce niveau de groupage. Le conteneur et son surdébit forment unconteneur virtuelVC (Virtual Container). Dans l’état actuel de la normalisation, on distingue trois types de VC :

Groupage des conteneurs dans une trame STM-1Un conteneur VC4 associé à son pointeur * localisé dans le SOH constituent l’unité administrative d’une trame STM-1. Des conteneurs virtuels d’ordre inférieur (VC-12 et VC-3) peuvent être mulmtiplexés pour composer un VC-4. UnVC-i associé à son pointeur constitue une unité d’affluent TU (Tributary Unit). Un conteneur C-4 peut regrouper plu-sieurs unités d’affluent. La position d’un conteneur virtuel VC-i dans la trame STM-1 se retrouve par le pointeur duVC-4 localisé dans le SOH, puis le pointeur VC-i localisé dans le TU-i.

Le conteneur virtuel est placé dans une zone de 9 rangées de 261 octets de la trame STM-1 constituant son unitéadministrativeAinsi, une trame STM-1 peut transporter dans son unité administrative :

• un VC-4,

• ou bien VC3 et VC-12 (avec ).

2.3.1.2 Les Trames STM-N.

On obtient des débits de transmission plus élevés en multiplexant, par entrelacements d’octets, N trames STM-1 pourformer une trame STM-N. Les valeurs normalisées de N sont 1, 4, 16.

On obtient alors les débits décrits dans le tableau 3. En terme de capacité de transport de VC-12, une trame STM-16peut donc en contenir 1008 et une trame STM-64 peut en contenir 4032. Dans ce cas, la capacité de transport estquasi-continue.

Table 2: VC-n utilisable en fonction du débit du signal tributair e

VC-12 VC-3 VC-4

Débit du Signal Tributaire 2 Mbit/s 34 ou 45 Mbit/s 149 Mbit/s

Table 3: Débit global des trames STM-N (en Mbit/s)

STM-1 STM-4 STM-16 STM-64

Débit 155.52 622.08 2488.32 9953.28

123456789

SOHAU

9 octets261 octets

123456789

POH

C-4Trafic

Trib utair e

STM-1 VC-4

Figure 2-1 Structure des trames

n 3 n–( ) 21× n 3≤

7

En pratique, la décision d’utiliser tel ou tel type de ligne dépend fortement d’une économie d’échelle. Par exemple,une liaison STM-4 offre une capacité de transmission quatre fois plus élevée qu’une ligne STM-1, mais pour un coût(en terme d’équipements) à peine deux fois supérieur (cf figure 2-2).

2.3.2 Topologie des Réseaux SDH

Les réseaux SDH sont généralement construits suivant une topologique hiérarchique d’anneaux (cf figure 2.3) en uti-lisant, le plus souvent, des liens bidirectionnels. Tous les liens d’un anneau doivent offrir la même puissance detransmission STM-N. Ces liens sont en général des fibres optiques, bien que la transmission de trames SDH par desliaisons radio ou satellites soit également mise en oeuvre.

La puissance de transmission d’un anneau SDH est en principe limitée à 10 Gbits/s (liaison STM-64). Cependant,des réseaux backbone (épine dorsale des ressources à l’échelle dun pays par exemple) peuvent être amenés à proposerune puissance de transmission bien supérieure à STM-64 qui est la puissance limite de la technologie optiqueemployée.Pour proposer des puissances supérieures et surtout pour ne pas accroître les coûts déjà trés élevés de construction detels réseaux (coût des tranchées par exemple), une solution consiste à faire passer plusieurs fibres optiques dans lamême tranchée liant les noeuds d’une même boucle. On crée alors une deuxième boucle SDH complètement parallèleà la première. Il faut évidemment autant de brasseurs par noeud qu’il y a d’anneaux.

1

2

4

8

16

32

64

1 4 16 64

Capacité (VC-4)

✧

✧

✧

✧

✧ Coût

✛

✛

✛

✛

✛STM-N

Figure 2-2 Coût des liaisons

...Figure 2-3 Réseau d’anneaux

interconnectés

Triple anneau superposé

Double anneau superposé

Figure 2-4 Superposition d’anneaux

8

2.3.3 Composants des Réseaux SDH

Les réseaux SDH font intervenir quatre types de composants :

1. Régénérateurs : Ces composants permettent de régénérer le signal SDH subissant une atténuation et des distor-sions lors de la transmission.

2. Multiplexeurs Terminaux: Ces multiplexeurs sont utilisés pour multiplexer des signaux plésiochro-nes ou SDH dans des structures SDH de plus haut niveau.

3. Multiplexeurs ADM (Add/Dr op Multiplexer) : Ces organes permettent d’extraire ou d’insérer dessignaux PDH ou des signaux SDH de débit plus faible dans une trame SDH.

Dans le cas d’un double ou triple anneau (parallèle), les lignes rentrent directement dans les ADM del’anneau qui est choisi pour transmettre un flux (figure 2-6.a). L’interconnexion entre anneaux se fait parl’intermédiaire de deux ADM (figure 2-6.b).

4. Commutateurs DXC (Digital Cross-Connect): Il s’agit des organes le plus complexes du réseau. Uncommutateur DXC peut jouer le rôle d’un ADM. Il permet d’insérer des signaux PDH dans des conte-neurs virtuels ainsi que la commutation des conteneurs. En général, il est utilisé pour interconnecter

A D M

STM-NSTM-N

SDHPDH

Figure 2-5 Add/Drop Multiplexer

ADM 1

ADM 2

anneau 1

anneau 2ADM 1

anneau 1

anneau 2

ADM 2

(a) (b)Figure 2-6 Interconnexion d’ADM

9

plusieurs ADM entre eux.

2.4 La Sécurisation dans SDH

2.4.1 Drag and Drop

La liaison de deux anneaux par un seul noeud rend très critique ce point d’interconnexion en cas de panne.Pour sécuriser cette interconnexion, une solution consiste à interconnecter deux anneaux par deux noeudsadjacents créant ainsi une arête commune aux deux anneaux.

La manière dont circule l’information à la jonction des deux anneaux s’appelle le “Drag and Drop”. Cettetechnique effectue une duplication du trafic sur les deux noeuds d’interconnexion. Considérons un flux ori-ginaire d’un nopeud de l’anneau 1 destiné à un noeud de l’anneau 2 (cf figure 2.8). En fonctionnement nor-mal , le flux est dupliqué en i1 et un vote en j2 extrait une seule des composantes. Le couple (j1, i2) joue lemême rôle pour un flux circulant dans le sens des aiguilles d’une montre dans l’”anneau 1 à destinationd’un noeud de l’anneau 2. Cette technique autorise la panne d’une des liaisons (i1, j1), (i2, j2), (i1, i2),, (j1,j2) ainsi que la panne d’une seul ou des 2 ADM de i ou j.

2.4.2 Protection SNCPDans le mécanisme de protection SNCP (Sub-Network Connection Protection) qui porte aussi le nom dePPS (Path Protection System), le trafic entre un noeud source et un noeud destination est envoyépar le che-

Anneau 1

Anneau 2

Anneau 3

ADM 3

DX

CA

DM

2AD

M 1

Figure 2-7 Combinaison decommutateurs et de Multiplexeurs

Anneau 1

Anneau 2

Anneau National

AnneauAnneau

Anneau

Régional 2 Régional 1

Régional 3

Figure 2-8 Sécurisation Drag and Drop entre deux anneaux

i1

i2

j1

j2

ji

10

min direct ainsi que par le chemin rétrograde. Au noeud destination il y a un vote entre les deux signaux.Cette technique, illustrée sur la figure 2-9.a, duplique la totalité du traficv. Pour limiter la bande passantenécessaire, le trafic peut être réparti en deux composantes : une sécurisée et une non-sécurisée, la protec-tion SNC P ne s’appliquant qu’à la composante sécurisée. En conséquence, si X est la quantité de traficsécurisé à faire passer entre deux noeuds quelconques de l’anneau, il faut réserver X unités de capacité surtous les arcs de l’anneau.

2.4.3 Protection MS-SPRING

Dans la protection MS-SPRING, le trafic qui circulait sur un arc (i,j) in,utilisable est réorienté sur le che-min alternatif entre i et j. Ainsi, le trafic de i à k qui empruntait le chemin i,j,k dans le szens des aiguillesd’une montre (voir figure 2-9) emprunte le chemin alternatif i->j si la liaison directe (i,j) est en panne).

Dans ce type de protection il faut que tout le trafic véhiculé par l’arc en panne puisse être rerouté par tousles autres arcs. En fait le pire des cas est la panne du lien le plus chargé puisque c’est dans ce cas que lereste de l’anneau prendra la plus grande surcharge due à la protection. Comme dans le cas précédent, pourlimiter la bande passante nécessaire, ce mécanisme de protection peut être limité au trafic sécurisé.

3. Notations et exemple test3.1 NotationsSoit un anneau défini avec les notations suivantes :

Injection du signal dans

Vote entre les deux signaux

les deux directions

reroutage dans la

Retransmissiondu signal

direction opposée

(a) (b)

Figure 2-9 Protections SNCP et MS-SPRING

i

j k

s(k) t(k)

2

3

4

5

6

7

8

1

pk+

pk-

Figure 3-1 Notationsdu graphe

11

La valeur du trafic notée X dans ce qui suit, se caractérise par une quantité de bande passante à faire passer

entre des couples de noeuds de l’anneau. Chaque trafic Xk, indicé par est issu d’un noeud

source noté s(k) et destiné à un noeud puits t(k). Deux chemins permettent de relier s(k) à t(k) : pk+ dans le

sens des aiguilles d’une montre et pk- dans le sens inverse. Nous notons Xk+ la partie du trafic Xk qui passe

sur pk+ et Xk- la partie du trafic Xk qui passe par pk-. Notons ai, l’arête i définie comme suit :

Pour définir les arêtes empruntées par chacun des flux, nous définissons maintenant les variables suivantes:

Ainsi le trafic k passant par l’arête i est donné par :

En technologie SDH, on utilise généralement des fibres optiques pour transmettre les informations. Cha-que fibre pouvant transmettre une trame STM-N, la capacité totale d’une liaison dépend du nombre defibres et de la capacité de chacune d’elles. Dans la formulation proposée, on considère les 3 types standardde trames:

Type 1 (STM-1) : Capacité c1Type 2 (STM-4) : Capacité c2Type 3 (STM-16) : Capacité c3

La coût de construction d’une liaison est composé d’un coût fixe (coût de tranchée) et d’un coût variablefonction du nombre de fibres et du type de trame qu’elles transmettent (la différence de coût venant essen-tiellement des types de multiplexeurs à chaque xetrémioté de la fibre). A toute arête ai, on associe donc 3

coûts li1, li

2, li3 selon le type de fibre. Pour obtenir une certaine capacité Ci de l’arête ai on peut être amené

à combiner les trois types de liaisons avec ui liaisons de type STM-1, vi liaisons de type STM-4 et wiliaisons de type STM-16 :

Ci = ui . c1 + vi . c2 + wi . c3

Le coût Ji de création de l’arête ai de capacité Ci sera alors égal à :

Ji = ui . li1 + vi . li

2 + wi . li3

k 1 K,[ ]∈

i i+1arête i

ai = (i, i [mod n] +1) où n est le nombre de

noeuds de l’anneaui∀ 1 n,[ ]∈

δik + 1 si p

k +passe parai

0 sinon

=

δik – 1 si p

k –passe parai

0 sinon

=

X ik δi

k +X

k + δik –

Xk –

+=

12

Remarque: Cette formulation ne prend pas en compte les trames STM-64 (moins répandues), mais quipourraient être aisément intégrées en ajoputant un quatrième type de liaison. Notons enfin Ti le trafic totalpassant par l’arête ai ; on a :

3.2 Exemple test

4. Dimensionnement optimal de l’anneau

Dans ce paragraphe on va chercher à construire un anneau qui permette d’écouler tous les trafics Xk avecdes liaisons dont le coût total de construction est minimal. On considère successivement le cas où la capa-cité de chaque liaison de l’anneau peut être adaptée à la quantité de trafic à écouler (paragraphe 4.1) etcelui où on impose des liaisons de même type dans tout l’anneau (paragraphe 4.2).

4.1 Dimensionnement à capacités héterogènesEn adaptant les notations du paragraphe 3, le dimensionnement des liaisons sans contrainte d’homogénéitédes liaiasons s’écrit:

Ti Xik

k 1=

K

∑ δik +

Xk + δi

k –X

k –+

k 1=

K

∑= =

1

2

3

4

1

2

3

4

5

6

7

8

9

Les problèmes d’optimisation que nous résolvonspar la suite seront illustrés au travers de l’anneauSDH décrit ci-après.

Il s’agit d’un anneau composé de 4 noeuds. Lamatrice de trafic (en nombre de VC-12) décrivant lestrafics entre les noeuds est la suivante :

La numérotation des flots est représentée sur lafigure ci-contre.

A

0 60 56 30

62 0 90 0

121 0 0 70

135 157 0 0

=

min li1

ui li2

vi li3

wi+ +

i 1=

n

∑sous les contraintes :

Xk +

Xk –

+ Xk

= k∀

δik +

Xk + δi

k –X

k –+

k 1=

K

∑ c1ui c2vi c3wi+ +( )– 0≤ i∀

Xk +

Xk –

0≥, k∀ui vi wi ℵ∈, , i∀

13

Où la contrainte (1) exprime que le trafic se distribue sur les deux chemins possibles dans l’anneau et (2)exprime la contrainte de capacité dans chaque arête.

La solution optimale de ce programme mixte fournit le nombre de fibres de chaque type (ui, vi, wi) compo-sant toute arête i de l’anneau. Elle fournit également la politique de routage en calculant la quantité de tra-

fic Xk à écouler dans chaque sens . La solution est optimale au sens où il n’existe pas pourcet anneau un autre ensemble d’arêtes capable d’écouler le trafic dont le coût de construction serait infé-rieur à celui qui a été trouvé.Exemple TestPour conserver l’homogénéité avec la matrice de trafic de l’exemple test, les capacités sont exprimées ennombre de VC-12 (C1=63, C2= 252, C3=1008). Les arêtes sont supposées de longueur identiques et le

coût donné para la fonction de la figure 2-2 (li1=1, li

2=2, li3=4, ). Le coût de l’(anneau est de

11 unités. Il offre une capacité dcumulée de liens de 1197 VC-12. On peut remarquer que pour un coûtidentique, le lien (2,3) aurait pu être composé de 1 STM-4 et le lien (4,1) de 1 STM-16, offrant ainsi unecapacité cumulée de 1827 VC-12.

Le routage employé introduit relativement peu de partage des flux. Ce routage correspond majoritairementà un routage par les plus courts chemins. Cette duistribution résulte de la propriété énnoncée dans la propo-sition suivante.

Proposition 1 Dans l’anneau dimensionné à coût minimal, il existe une politique de routage qui, pour toutnoeud source de l’anneau, partage au plus un des trafics issus de ce noeud.Preuve soit k=1 le trafic de i à j1 et k=2 le trafic de i à j2

Supposons que dans l’anneau de coût minimal, les flots X1 et X2 soient partagés

k 1 K,[ ]∈∀

i∀ 1 n,[ ]∈

0

100

200

300

400

500

(1,2) (2,3) (3,4) (4,1)Liens

TRAFIC SUR LES LIENS

TraficsCapacités

0

20

40

60

80

100

120

140

160

1 2 4 6 8Flots

ROUTAGE

Xk+ Xk-

3 5 7 9

1 STM-4

2 STM-1

1 STM-4

1 STM-1

2 STM-4

j1 j2

iX1+

X2+

X1-

X2-

X1-

X2+

14

.

Faisons X1+ = X1+ +ε , X1- = X1--ε , X2+ = X1+ -ε , X2- = X2-+ε . Le trafic total Ta reste inchangé dans lesarêtes ai reliant j1 à j2 par la chaîne passant par i; il diminue de 2ε dans les arêtes a reliant j1 à j2 par la

chaîne ne passant pas par i. Par conséquent ce nouveau flot reste admissible. En choisissantε = min (X2+,

X1-), on retrouve un nouveau routage qui partage au plus l’un des deux trafics. La généralisation est immé-diate. Si plusieurs trafics sont issus du même noeud i, pour tout couple de trafics (i->ja, i->jb) la propriétéde partage pour au plus l’un des deux trafics doit être vérifiée. Ceci n’est possible que si 1 au plus de tousles trafics issus de i est partagé.❚

Ainsi pour l’exemple test, parmi les trafics 1,2 et 3 l’un d’entre eux au plus est partagé (trafic 3). Pour lecouple des trafics 4 et 5, un routage alternatif ne partagerait pas le flot 5 et partagerait légèrement le flot 4.Parmi le couple des trafics 6 et 7 aucun n’est partagé. Dans le couple des trafics 8 et 9, un seul est partagé(trafic 9).

4.2 Dimensionnement à capacités homogènes

C’est le même problème que le précédent où on cherche toujours la capacité des liaisons à coût minimalmais à la seule différence où toutes les capacités des liaisons doivent être identiques. Le problème consiste

à minimiser le coût d’une seule liaison de capacité ( ) ; cette capacité étant identique sur

toutes les liaisons. Le problème devient :

Exemple test:La solution obtenue utilise un anneau STM-1 et un anneau STM-4 en parallèle, fournissant ainsi une capa-

cité de 315 VC-12. Le trafic sur les liens et le routage obtenu sont représentés sur la figure ci-dessus. Il est

ε 0>∃ tel que X1 +

X2 +

X1 –

X2 –, , , ε>⇒

c1u c2v c3w+ +

min l1

u l2

v l3

w+ +

sous les contraintes :

Xk +

Xk –

+ Xk

= k∀

δik +

Xk + δi

k –X

k –+

k 1=

K

∑ c1u c2v c3w+ +( )– 0≤ i∀

Xk +

Xk –

0≥, k∀u v w ℵ∈, ,

0

50

100

150

200

250

300

350

(1,2) (2,3) (3,4) (4,1)Liens

TRAFIC SUR LES LIENS

TraficsCapacités

0

20

40

60

80

100

120

140

160

2 4 6 8Flots

ROUTAGE

Xk+ Xk-

1 3 5 7 9

15

intéressant de noter que la contrainte d’homogénéité des liaisons induit une augmentation du coût del’anneau (12 au lieu de 11) tout en réduisant la capacité cumulée des liaisons (1260 VC-12 au lieu de1827). La proposition 1 reste valable pour le cas d’un réseau homogène. Parmi 1,2 et 3 aucun trafic n’estpartagé. Un routage alternatif ne partagerait pas le trafic 4 et partagerait légèrement 5. Parmi 6 et 7 et parmi8 et 9, un seul trafic est partagé. On peut enfin remarquer que les trafics non partagés empruntent presquetoujours le chemin le plus court (ce qui a tendance à réduire la bande totake utilisée dans l’anneau).

5. Routage optimal dans l’anneau

Le problème de dimensionnement résolu dans le paragraphe prcédent trouve une topologie d’anneau decoût minimal: il n’existe pas de topologie de coût inférieur capable d’écouler la matrice de trafic. Le calculdu dimensionnement résout implicitement le problème du routage des flots, mais du fait que la capacité desliens est discrète, plusieurs routages sont possibles dans la topologie déterminée par la phase de dimen-sionnement. Dans ce paragraphe, on cherche des politiques de routage ayant des propriétés particulièresdans un anneau de coût minimal.Comme les anneaux SDH sont généralement à liaisons homogènes, ce paragraphe ne traite que du routageoptimal dans un anneau dont tous les liens ont la capacité c (trouvée la phase de dimensionnement).

5.1 Routage à partage minimal

Proposition 2 une politique de routage à partage minimal peut être trouvée en minimisant le trafic totaldans l’anneau.Preuve La proposition 1 du paragraphe précédent montre qu’il existe un routage qui ne partage pas plusd’un flot parmi tous ceux de source identique dans l’anneau. Nous appelons une telle politique “routage àpartage minimal”. Une des conséquences principales de la proposition 1 est qu’une politique de routage àpartage minimal réduit le trafic total sur l’anneau, par comparaison avec une politique n’ayant pas cettepropriété. Par conséquence, la minimisation du trafic total dans l’anneau doit conduire à des politiques deroutage à partage minimal.

Le problème se formule de la manière suivante :

Exemple test:

On obtient le résultat décrit dans la figure ci-dessous. Vu le critère optimisé, on vérifie que le routage per-met de dégager de la disponibilité dans certains liens Par rapport au routage de la phase de dimensionne-ment qui a tendance à utiliser toute la capacité offerte par l’anneau

min δik +

Xk + δi

k –X

k –+

k 1=

K

∑i 1=

n

∑ T*

=

sous les contraintes :

Xk +

Xk –

+ Xk

= k∀

δik +

Xk + δi

k –X

k –+

k 1=

K

∑ c– 0≤ i∀

Xk +

Xk –

0≥, k∀

16

.

5.2 Maximisation de la capacité résiduelle minimale

Une autre manière d’envisager le routage est de chercher comment écouler le trafic dans le réseau dimen-sionné de telle sorte qu’il reste une capacité résiduelle dans les liaisons de l’anneau en vue de pouvoirabsorber une augmentation passagère de trafic. Ceci revient à minimiser le trafic de la liaison la plus char-gée. Une manière d’atteindre cet objectif est de chercher la plus petite capacité de liaison (notée Z) permet-

tant d’écouler le trafic dans l’anneau homogène (on obtiendra évidemment ). Le problème deroutage s’écrit :

Exemple test:

La valeur de Z obtenue en résolvant le programme linéaire est 294.5 (295 pour le programme linéaire ennombres entiers). La solution obtenue est représentée ci-dessous. Elle équilibre la charge sur les différentsliens. Bien que cette résolution ne garantisse pas un routage à partage minimal, la minimisation du traficmaximal sur les liaisons a tendance à réduire le trafic total dans l’anneau, et donc à aller vers un routage àpartage minimal. Dans cet exemple, seuls deux trafics sont partagés (sur des chemins minimaux concur-rents) et un seul flot emprunte un chemin maximal (flot 3).

0

50

100

150

200

250

300

350

(1,2) (2,3) (3,4) (4,1)

Liens

TRAFIC SUR LES LIENS

Trafics Capacités

0

20

40

60

80

100

120

140

160

1 2 4 6 8 9Flots

ROUTAGE OPTIMAL

Xk+ Xk-

3 5 7

Z C≤

min Z

sous les contraintes :

Xk +

Xk –

+ Xk

= k∀

δik +

Xk + δi

k –X

k –+

k 1=

K

∑ Z– 0≤ i∀

Xk +

Xk –

0≥, k∀0 Z C≤ ≤

0

50

100

150

200

250

300

350

(1,2) (2,3) (3,4) (4,1)Liens

TRAFIC SUR LES LIENS

Trafics Capacites

0

20

40

60

80

100

120

140

160

1 2 4 6 8Flots

ROUTAGE OPTIMAL

Xk+ Xk-3 5 7 9

17

La résolution de ce problème garantit qu’il n’existe pas de routage permettant d’obtenir une capacité rési-duelle minimale supérieure à C-Z. Parmi les routages à maximum de capacité résiduelle minimale, dans lebut d’obtenir un routage à partage minimal on peut cherche celui qui minimise le trafic total dans l’anneau.Pour cela, il suffit de résoudre le problème 5.1 en remplaçant C par Z.

6. Prise en compte des mécanismes de protection SDH

Pour plus de généralité, nous allons considérer que la matrice de trafic est composée de parties de traficnon sécurisé et de parties de trafic sécurisé. Le cas le plus général est celui où chaque trafic est décomposéen deux parties :la partie sécurisée et la partie non sécurisée. A titre d’exemple, nous utiliserons leréseau précédemment décrit en décomposant la matrice de trafic de la façon suivante :

La partie sécurisée du trafic doit être prise en charge par un des deux mécanismes de protection, SNCP ouMS-SPRING.

6.1 NotationsNotons :

• Xks+ la partie du trafic Xk sécurisé qui passe sur pk+

• Xkn+ la partie du trafic Xk non-sécurisé qui passe sur pk+

• Xks- la partie du trafic Xk sécurisé qui passe par pk-

• Xkn- la partie du trafic Xk non-sécurisé qui passe par pk-

• le trafic k sécurisé qui passe sur la liaison i

• le trafic k non-sécurisé qui passe sur la liaison i

• le trafic sécurisé passant sur la liaison i

• le trafic non-sécurisé passant sur la liaison i

et finalement,

• le trafic nominal sur la liaison i.

6.2 Dimensionnement et routage avec MS-SPRING

On a pu voir dans la description de la protection de type MS-SPRING qu’en cas de panne d’une liaison letrafic qui la traverse était rerouté sur toutes les autres liaisons de l’anneau. En cas de rupture d’une liaison,seuls les trafics sécurisés qui l’empruntent seront reroutés sur les autres liaisons.

Le problème de dimensionnement consiste donc à trouver l’anneau de coût minimal qui permette d’écouler

A

0 60 56 30

62 0 90 0

121 0 0 70

135 157 0 0

0 6 10 5

40 0 11 0

30 0 0 8

50 70 0 0

= = +

0 54 46 25

22 0 79 0

91 0 0 62

85 87 0 0

Partie sécurisée Partie non sécurisée

Xiks δi

k +X

ks + δik –

Xks –

+=

Xikn δi

k +X

kn + δik –

Xkn –

+=

Xis

Xiks

k∑=

Xin

Xikn

k∑=

Ti Xiks

Xikn

+

k∑=

18

tout le trafic, et qui garantisse de plus que le trafic sécurisé pourra être rerouté en cas de panne d’une liaison.

6.2.1 Contrainte liée au reroutage MS-SPRING

Notons TTi,j le trafic passant dans l’arête ai si une rupture de l’arête aj survient. Dans ce cas, tout le traficprotégé sur aj est rerouté sur toutes les autres liaisons et en particulier sur ai. On obtient :

Pour assurer l’acheminement des trafics sécurisés en cas de dégradation, une liaison i doit être capable defaire passernon seulement le trafic nominal comme précédemment, mais encore le trafic sécurisé pouvantvenir d’une autre liaison. Il faut donc prévoir une réserve de capacité suffisante dans les liaisons.

• Pour le trafic nominal on a :

• En tenant compte du trafic rerouté depuis la liaison aj on a :

Le but du dimensionnement est de chercher la capacité minimale de l’anneau permettant d’écouler le trafic.Dans le cas présent, où des trafics sont protégés et reroutés en cas de panne, les capacités des liaisons doi-vent permettre d’écouler le trafic nominal et le trafic sécurisé qui est rerouté. Une liaison doit avoir unecapacité résiduelle capable d’écouler n’importe quel trafic rerouté. En particulier, elle doit être dimension-née pour le pire des cas, c’est à dire:

On doit donc chercher une capacité C telle que :

Cet ensemble de contraintes faisant intervenir l’opérateur max, peut être transformé en un ensemble équi-valent de contraintes linéaires. Pour cela l’ensemble de n contraintes précédentes faisant intervenir l’opéra-teur max est équivalent à l’ensemble des n(n-1) contraintes linéaires. On a :

6.2.2 Problème de dimensionnement

On s’intéresse uniquement au cas d’un anneau homogène. Le problème de dimensionnement devient :

T Ti j, Ti X jks

k∑+=

Ti Xiks

Xikn

+

k∑ δi

k +X

ks +X

kn ++( ) δi

k –X

ks –X

kn –+( )+

k∑= =

T Ti j, Ti δ jk +

Xks + δ j

k –X

ks –+

k∑+=

T Ti T i + max j= δ jk +

Xks + δ j

k–X

ks –+

k∑

T Ti C≤ i∀

T Ti j, C≤ i∀ j i≠∀,

19

Exemple test:

La solution optimale consiste à construire un anneau de type STM-16, ce qui laisse une grande capacitérésiduelle dans les arêtes pour rerouter le trafic sécurisé en cas de panne.Comme dans l’étude sans prise en compte des pannes, le trafic se répartit de manière équilibrée dans lesarêtes et le routage implicite calculé par un dimensionnement à coût minimal partage un tiers des flots (1n,5n, 6s, 7n, 9s et 9n).Dans l’anneau de coût minimal, on va s’intéresser maintenant à la recherche de politiques alternatives deroutage possédant des propriétés particulières.

6.2.3 Problème de routage

L’anneau étant maintenant dimensionné pour tenir compte du reroutage du trafic sécurisé (la capacité Cdes liens est fixée), il s’agit d’optimiser le routage afin de gagner de la ressource dans l’occupation desliaisons.

a) Routage à partage minimal

Proposition 3 Dans un anneau dimensioné à coût minimal pour écouler le trafic nominal et le trafic sécu-risé en cas de panne d’une liaison, il existe une politique de routage qui, pour tout noeud source del’anneau, partage au plus un trafic sécurisé et un trafic non sécurisé issus de ce noeud.

min l1

u l2

v l3

w+ +

sous les contraintes :

Xks +

Xks –

+ Xks

= k∀

Xkn +

Xkn –

+ Xkn

= k∀

δik +

Xks +

Xkn +

+( ) δik –

Xks –

Xkn –

+( )+

k∑ δ j

k +X

ks + δ jk–

Xks –

+

k∑+

c1u c2v c3w+ +( )– 0≤ i∀ j i≠∀,

Xks +

Xks –

Xkn +

Xkn –, , , 0≥ k∀

u v w ℵ∈, ,

0

200

400

600

800

1000

(1,2) (2,3) (3,4) (4,1)Liens

TRAFIC SUR LES LIENS

Capacites Trafics

0

20

40

60

80

100

120

140

160

1 2 4 6 8Flots

ROUTAGE

Xks+ Xkn+

Xks- Xkn-

3 5 7 9

20

Preuve (a) Considérons tout d’abord le trafic sécurisé. Par un raisonnement identique à celui utilisé dans lapreuve de la proposition 1, s’il existait deux flots sécurisés issus de i à destination de j1 et j2, il serait pos-sible de les rerouter de telle sorte que le trafic dans les arêtes de j1 à j2 passant par i restent identiques etque le trafic sécurisé dans l’autre chaîne (j1, j2) soient inférieur. Le flot résultant reste donc adimissible.Par le principe de protection MS-SPRING, la capacité résiduelle de chaque arête est suffisante pour écou-ler le trafic sécurisé de n’importe quelle autre arête. Comme le nouveau flot ne réduit pas la capacité rési-duelle et que le trafic sécurisé baisse sur une partie de l’anneau, la capacité de l’anneau est suffisante pourécouler ce nouveau flot en cas de panne d’une liaison. En généralisant le raisonnement à l’ensemble desflots de source i, on montre ainsi qu’il existe une politique de routage partageant au plus un trafic sécuriséissu de i.(b) Considérons maintenant le trafic non sécurisé issu de i à destination de deux noeuds j1 et j2. Par lemême raisonnement que pour le trafic sécurisé, on peut retrouver les flots de telle sorte qu’au maximum untrafic soit partagé. Le trafic non sécurisé reste identique sur la chaîne j1 à j2 passant par i et baisse surl’autre chaîne. Le nouveau flot résultant de ce re-routage reste admissible dans l’anneau de coût minimal.Par ailleurs, la capacité résiduelle des arêtes reste au moins égale à sa valeur antérieure et le trafic sécuriséest inchangé. En conséquence la capacité de l’anneau est suffisante pour écouler le nouveau flot sécurisé encas de panne d’une liaison. En généralisant à l’ensemble des flots de source i, on en déduit qu’il existe unepolitique de routage dans l’anneau de coût minimal partageant au plus un trafic non sécurisé issu de i.❚

D’après la proposition 2, une politique de routage à partage minimal est une politique qui minimise le tra-fic dans l’anneau. Comme dans le cas non-sécurisé, pour trouver une politique de routage à partage mini-mal, il faut donc minimiser le trafic dans toutes les liaisons de l’anneau. Il s’agit ici de minimiser le traficnominal (sécurisé + non-sécurisé) et de tenir compte dans les contraintes du trafic rerouté en cas de panne.Le problème devient :

Exemple test:

La politique de routage obtenue réduit significativement le trafic sur trois des qutres liens de l’anneau. Lenombre de flots partagés a été consédérablement réduit puisqu’on passe de six (en phase dimensionne-

ment) à zéro. Tous les flots utilisent un chemin minimal ce qui se vérifie également par le fait que T* = Tinf(voir paragraphe 5.1 pour la justification). Le fait que le routage à partage minimal ne partage aucun flotdécoule de la grande capacité résiduelle dans les liaisons et de la distinction entre trafic sécurisé et nonsécurisé : le grain des flots est plus faible, ce qui autorise un plus grand nombre de possibilités de routages,dont les routages par le chemin minimal qui réduit le trafic total dans l’anneau.

min δik +

Xks +

Xkn +

+( ) δik –

Xks –

Xkn –

+( )+

k∑

i∑

sous les contraintes :

Xks +

Xks –

+ Xks

= k∀

Xkn +

Xkn –

+ Xkn

= k∀

δik +

Xks +

Xkn +

+( ) δik –

Xks –

Xkn –

+( )+

k∑

δ jk +

Xks + δ j

k –X

ks –+

C≤k∑+ i∀ j i≠∀,

Xks +

Xks –

Xkn +

Xkn –, , , 0≥ k∀

21

b) Maximisation de la plus petite capacité résiduelle

Par rapport à la formulation du paragraphe 5.2, la généralisation au cas de la prise en compte de la protec-tion du trafic sécurisé par la technique MS-SPRING s’écrit :

6.3 Dimensionnement et routage avec SNCP

La protection SNCP est plus simple que MS-SPRING et consiste à doubler le trafic nominal sécurisé dansles deux sens (δ- etδ+). La contrainte précédente qui donnait le trafic sécurisé passant par l’arête ai :

devient :

Ceci revient à précharger toutes les liaisons de l’anneau avec le trafic XS. Seuls les flux non-sécurisés vontpermettre d’optimiser le “remplissage” des ressources de l’anneau.

6.3.1 Dimensionnement

0

200

400

600

800

1000

(1,2) (2,3) (3,4) (4,1)Liens

TRAFIC SUR LES LIENS

Capacites Trafics

0

20

40

60

80

100

120

140

160

1 2 4 6 8Flots

ROUTAGE OPTIMAL

Xks+ Xkn+

Xks- Xkn-

3 5 7 9

min Z

sous les contraintes :

Xks +

Xks –

+ Xks

= k∀

Xkn +

Xkn –

+ Xkn

= k∀

δik +

Xks +

Xkn +

+( ) δik –

Xks –

Xkn –

+( )+

k∑

δ jk +

Xks + δ j

k –X

ks –+

Z 0≤–k∑+ i∀ j i≠∀,

0 Z C≤ ≤

Xks +

Xks –

Xkn +

Xkn –, , , 0≥ k∀

δik +

Xks + δi

ks –X

ks –+( )

k∑

XS

Xks

k∑= i∀

22

La topologie de l’anneau homogène de coût minimal permettant d’écouler le trafic nominal et le trafic sé-curisé en cas de panne d’une liaison esty la solution du problème suivant :

Exemple test:

L’anneau de coût minimal est composé d’une ligne STM-16, comme c’était le cas avec la protection detype MS-SPRING. On constate que la protection SNCP génère beaucoup plus de trafic que MSQ-SPRING. Une borne inférieure sur le trafic cumulé dans les liaisons de l’anneau est obtenue par l’expres-sion :

Pour cet exemple test, on obtient Tinf = 1695, soit une augmentation de 52% du trafic nominal par rapportà la protection MS-SPRING. Notons également que le routage induit par le dimensionnement de coûtminimum partage trois flots (1,5 et 7).

6.3.2 Routage

a) Routage à partage minimal

La phase de dimensionnement a trouvé l’anneau de coût minimal permettant d’écouler le trafic dont une

partie est sécurisée par SNCP. C, est la capacité de cet anneau. Comme le trafic sécurisé XS passe par tout

l’anneau, le problème du routage du trafic non sécurisé Xn se ramène au problème initial de routage du tra-

fic dans un anneau de capacité C-XS. Par conséquent la proposition 1 s’adapte immédiatement à la protec-tion SNCP :

min l1

u l2

v l3

w+ +

sous les contraintes :

Xkn +

Xkn –

+ Xkn

= k∀

δik +

Xkn + δi

k –X

kn –+

k∑ c1u c2v c3w+ +( )– X

S–≤ i∀

Xkn +

Xkn –, 0≥ k∀

u v w ℵ∈, ,

Tinf nXS

Xkn

dkk∑+=

0

200

400

600

800

1000

(1,2) (2,3) (3,4) (4,1)Liens

TRAFIC SUR LES LIENS

Capacites Trafics

20

40

60

80

100

120

140

160

1 2 4 6 8Flots

ROUTAGE

Xks

Xkn+

Xkn-

3 5 97

23

Proposition 4 Dans l’anneau de coût minimal utilisant la technique SNCP pour protéger la composantesécurisée du trafic, il existe une politique de routage du trtafic non sécurisé qui, pour tout noeud source del’anneau, partage au plus un des trafics non sécurisés de ce noeud.Une telle politique est déterminée par la recherche d’un routage minimisant le trafic total dans l’anneau,soit :

Exemple test:

Le trafic total est réduit de façon significative et on peut constater que le routage ne partage aucun traficnon sécurisé. De plus, la solution du problème est P* = Tinf, ce qui implique que touis lmes flots emprun-tent un chemin minimal (comme le montre le diagramme à barres).

b) Maximisation de la plus petite capacité résiduelle

Le problème devient :

min δik +

Xkn + δi

k –X

kn –+

k∑

i∑

sous les contraintes :

Xkn +

Xkn –

+ Xkn

= k∀

δik +

Xkn + δi

k –X

kn –+

k∑ C X

S–≤ i∀

Xkn +

Xkn –, 0≥ k∀

0

200

400

600

800

1000

(1,2) (2,3) (3,4) (4,1)Liens

TRAFIC SUR LES LIENS

Capacites Trafics

0

20

40

60

80

100

120

140

160

1 2 4 6 8Flots

ROUTAGE OPTIMAL

Xks

Xkn+Xkn-

3 5 7 9

min Z

sous les contraintes :

Xkn +

Xkn –

+ Xkn

= k∀

δik +

Xkn + δi

k –X

kn –+

Z–k∑ X

S–≤ i∀

0 Z C≤ ≤

Xkn +

Xkn –, 0≥ k∀

24

7. Conclusions

Nous avons développé dans cette étude plusieurs modélisations et algorithmes de résolution du problèmede dimensionnemet et de routage dans les anneaux SDH. Les problèmes considérés pour le dimensionne-ment sont les suivants :

- Dimensionnement optimal à capacités hétérogènes- Dimensionnement optimal à capacités homogènes

Nous avons ensuite traité le problème du routage sur un réseau à capacité donnée :

- Routage optimal maximisant la capacité résiduelle totale- Routage optimal maximisant la capacité résiduelle minimale

Nous avons ensuite introduit dans ces problèmes de base les deux grands mécanismes de protection de SDHque sont SNCP et MS-SPRING. Les problèmes ont été modifiés pour prendre en compte des trafics sécuri-sés (duplication due à SNCP ou reroutage dû à MS-SPRING).

Plusieurs conclusions peuvent être tirées de cette étude :

• tout d’abord, l’approche développée permet de résoudre complètement et de manière exacte le pro-blème de l’utilisation optimale des ressources d’un anneau SDH.

• Le problème de dimensionnement tel qu’il a été formulé, est un problème mixte. Nous avons comparéles solutions obtenues avec un problème complètement combinatoire où les flux ne peuvent prendreque des valeurs discrètes. La différence est négligeable, ce qui justifie pleinement de considérer le tra-fic comme une variable continue.

• Le problème de routage permet d’améliorer la solution obtenue lors de l’étape de dimensionnement.• La solution optimale du routage (partage optimal sur le sens + ou -) n’est pas une solution triviale. Par

exemple, un routage à 50% dans les deux directions, qu’aurait pu nous dicter l’intuition, est vraimenttrès loin de l’optimum. Toutefois, dans les exemples traités [4] on peut remarquer que beaucoup deflux sont routés à 100% sur le plus court chemin (à condition qu’ils ne soient pas trop gros) et que lesautres sont partagés dans les deux directions dans une proportion dépendant des données (matrice detrafic, capacité). La proposition 1 développée dans l’article montre que la solution du routage optimalest à partage minimal, c’est à dire qu’un maximum de un flot sera partagé par noeud origine de trafic.Une bonne solution initiale (ou heuristique) pourrait consister à router la plupart des trafics sur leurplus court chemin jusqu’à saturation des capacités.

• Parmi les critères testés, il semble bien que la maximisation de la plus petite capacité résiduelle suiviede la minimisation du trafic total conduisent à la meilleure solution.

• Les mécanismes de protection (SNCP ou MS-SPRING) doivent être intégrés dans l’optimisation car lasolution change complètement en présence de flux protégés.

• Il est clair que la protection MS-SPRING consomme moins de ressources que la protection SNCP.

Les modèles et techniques de résolution développés dans cette étude traitent de manière couplée le pro-blème de dimensionnement et de routage. Pour rendre l’approche complète, il sera aussi nécessaire d’inté-grer le problème de topologie, c’est à dire comment connecter les noeuds entre eux (choix des noeudsvoisins dans un anneau) et combien d’anneaux doivent être créés pour interconneter tous les noeuds.

8. Bibliographie

25

[1] M. Sexton, A. Reid. Transmission Networking: SONET and the Synchronous Digital Hierarchy.Artech House, 1992.

[2] A. Schrijver, P. Seymour, P. Winkler. The Ring Loading Problem. SIAM Journal on DiscreteMathemathics, Vol. 11, N¡1, pp. 1-14, 1998.

[3] M. Boisseau, M. Demange, JM. Munier. Réseaux haut débit. Eyrolles, 1992.[4] JM. Garcia, O. Brun, P. Bacquet. Optimal Routing in SDH Telecommunication Networks.

LAAS Research report n¡ 99334, august 1999.[5] B. Gavish & I. Neuman. A System for Routing and Capacity Assignment in Computer Commu-

nication Networks. IEEE Trans on Com, Vol. 37, n¡4, April 1989.[6] M. Dell’Amico, M. Lab bé & F. Maffioli. Exact Solution of the SONET Ring Loading Problem.

Operation Research Letters, n¡ 25, pp. 119-129, 1999.[7] C.L. Monma &D .F. Shallcross. Methods for Designing Communications Networks with Certain

Two-Càonnected Survavility Constraints. Operations Research, Vol. 37, n¡4, July-August 1989.