Project P709
Planning of Optical Network
Deliverable 3
Optical Network Planning
Volume 3 of 9: Annex B – Overview on modelling techniques, optimisation algorithms and planning tools
Suggested readers:
· PNOs studying potential upgrade possibilities for their transport networks
· PNOs upgrading and developing planning tools for optical networks
· PNO strategists and network planners
· PNO researchers in the field of network optimisation methods
For full publication
March 2000
EURESCOM PARTICIPANTS in Project P709 are:
· Finnet Group
· Swisscom AG
· Deutsche Telekom AG
· France Télécom
· MATÁV Hungarian Telecommunications Company Ltd.
· TELECOM ITALIA S.p.a.
· Portugal Telecom S.A.
· Telefonica S.A.
· Sonera Corporation
· British Telecommunications plc
· Telenor AS
This document contains material which is the copyright of certain EURESCOM PARTICIPANTS, and may not be reproduced or copied without permission.
All PARTICIPANTS have agreed to full publication of this document.
The commercial use of any information contained in this document may require a license from the proprietor of that information.
Neither the PARTICIPANTS nor EURESCOM warrant that the information contained in the report is capable of use, or that use of the information is free from risk, and accept no liability for loss or damage suffered by any person using this information.
This document has been approved by EURESCOM Board of Governors for distribution to all EURESCOM Shareholders.
ã 1999 EURESCOM Participants in P709
Deliverable 3 - Volume 3 Annex B: Overview
List of Authors
Bertrand Decocq France Télécom CNET (FT)
Abdel Lisser France Télécom CNET (FT)
Dávid Arató Hungarian Telecom MATAV (HT)
Tivadar Jakab Hungarian Telecom MATAV (HT)
Roberto Clemente CSELT (IT)
Teresa Almeida Portugal Telecom S.A. (PT)
Marcelino Pousa Portugal Telecom S.A. (PT)
Nuria Gómez-Rojo Telefónica I+D (TE)
Antonio Ruiz-Cantera Telefónica I+D (TE)
Table of Contents
List of Authors i
Table of Contents ii
Abbreviations iv
1 Introduction 1
2 Optimisation strategies and algorithms 2
2.1 Modelling optimisation problems 2
2.1.1 Flow formulation 2
2.1.2 Path-flow 4
2.1.3 Path formulation 4
2.2 Overview of optimisation algorithms 5
2.2.1 Enumeration 5
2.2.2 Branch and Bound 6
2.2.3 Relaxation techniques 6
2.2.4 Marginal improvement techniques 7
2.2.5 Simulated annealing 8
2.2.6 Tabu search 9
2.2.7 Successive smooth approximation 10
2.2.8 Simulated assignment 11
2.2.9 Genetic programming 12
2.2.10 Heuristic algorithms 14
3 Description of existing planning tools 15
3.1 ESTEREL-S 15
3.1.1 Network topology 15
3.1.2 Protection Architectures 15
3.1.3 Traffic demand 15
3.1.4 Input data 15
3.1.5 Main planning functions 16
3.1.6 Output results 17
3.2 REFORMA 17
3.2.1 Network topology 17
3.2.2 Traffic demand 19
3.2.3 Input data 19
3.2.4 Main planning functions 20
3.2.5 Output results 20
3.2.6 Network elements cost 20
3.2.7 Main differences with REFORMA-C 21
3.3 DIAMOND 21
3.3.1 General network model 21
3.3.2 Allowed node architectures 23
3.3.3 Demand matrices 23
3.3.4 Wavelength allocation policy 24
3.3.5 Recovery mechanisms 24
3.3.6 Capacity of the transmission systems 24
3.3.7 Expected failures 24
3.3.8 Main output 24
3.3.9 Planning methodology 25
4 Overview of publications on network planning 31
4.1 General books 31
4.2 Realistic optical networking experimenting 31
4.3 SDH planning 31
4.4 Optical network planning 32
4.5 Multi-layer planning papers 33
4.6 Planning tools 33
References 33
Abbreviations
ARP / Allocation Rearrangement Protection
CPU / Central Processing Unit
DCU / Demand Capacity Unit
DP / Dedicated Protection
DXC / Digital cross Connect
GA / Genetic Algorithm
HO / Higher Order
HOP / Higher Order Path
LO / Lower Order
LOP / Lower Order Path
LT / Line Terminal
LTP / Long Term Planning
MS / Multiplex Section
MSP / Multiplex Section Protection
MS-DPRing / Multiplex Section Dedicated Protection Ring
MS-SPRing / Multiplex Section Shared Protection Ring
MTP / Medium Term Planning
OADM / Optical Add Drop Multiplexer
OCH / Optical CHannel
OCH-DPRing / Optical Channel Dedicated Protection Ring
OMS / Optical Multiplex Section
OMS-DPRing / Optical Multiplex Section Dedicated Protection Ring
OMS-SPRing / Optical Multiplex Section Shared Protection Ring
OTN / Optical Transport Network
OXC / Optical Cross-Connect
PC / Personal Computer
PDH / Plesiochronous Digital Hierarchy
PNO / Public Network Operator
RX / Receiver
SA / Simulated Annealing
SAL / Simulated ALlocation
SDH / Synchronous Digital Hierarchy
SNCP / Sub-Network Connection Protection
SNC-DPRing / Sub-Network Connection Dedicated Protection Ring
SP / Shared Protection
STM / Synchronous Transport Module
STP / Short Term Planning
TS / Termination of Section
TX / Transmitter
VC / Virtual Container
WDM / Wavelength Division Multiplexing
ã 2000 EURESCOM Participants in Project P709 page v (v)
Deliverable 3 - Volume 3 Annex B: Overview
1 Introduction
This Annex completes the overview on existing transmission planning issues, which begins in Annex A.
Particularly chapter 2 describes several modelling techniques and optimisation algorithms normally used for solving the optimisation problems when planning the current transport networks. The presented techniques and algorithms may be used for solving the different problems and sub-problems specified in Annex A. Due to the nature of the problems, it is expected that these types of techniques might be used, as well, for the optimisation problems involved in the optical network planning.
Chapter 3 describes the functionalities of three well-known planning tools, developed by France Telecom/CNET, Telefonica I+D and Telecom Italia/CSELT. The aim is to show how PNOs are presently coping with of the transmission network planning issues and to understand better the expected results of planning activities.
Finally chapter 4 provides a categorised bibliography on planning issues.
2 Optimisation strategies and algorithms
This chapter includes a description of several modelling techniques and optimisation algorithms normally used for solving the optimisation problems when planning the current transport networks. The presented techniques and algorithms may be used for solving the different problems and sub-problems specified in Annex A. Due to the nature of the problems, it is expected that these types of techniques might be used, as well, for the optimisation problems involved in the optical network planning.
2.1 Modelling optimisation problems
The nature of the problem and the available domain knowledge often limits the way that the problems can be formulated. However, it is possible to formulate mathematically most of the optimisation problems in multi-layer networks by inequality linear and non-linear systems. Unfortunately, the optimum solution is not reachable nowadays in most of the formulated systems and it is not envisaged to happen in a near future. That is why, it is advisable:
· To simplify the problems;
· To avoid the search of an optimum solution of the exact formulation of the problem;
· Use alternative techniques or greedy algorithms that achieve less optimum solutions in which the error percentage can be estimated.
Choosing among the techniques that will be described afterwards is far from trivial and it cannot be done mechanically. Every problem is unique. Some of them only allow using one kind of algorithms. Moreover, the problem solver’s knowledge about the techniques and the application domain greatly influence the choice of the techniques.
The operations research provides a pretty large amount of techniques to formulate and solve optimisation problems. These techniques are based on mathematical theories of different complexity. It is not possible to use them as the problem complexity can override the hardware and software possibilities.
The elements that determine the possibility of dealing a problem with operations research techniques are:
· The type and number of variables (binary, integer, real, etc.);
· The type and number of restrictions (linear or non-linear);
· The type of the cost function (linear or non-linear).
In that context, there are different models that have been used traditionally in network optimisation as flow formulation for multi-commodity flow model, path-flow formulation and path formulation.
2.1.1 Flow formulation
A telecommunication network optimisation problem is often well described by a multi-commodity flow model. It can be formulated in the following way
FF:
under the constraints
, for all edges e
for all nodes n and all demand d.
For the demand d, cnd gives the flow requirement at node n, negative at a source and positive at a sink. (ane) is the node-arc incidence matrix.
Normal assumptions for the cost functions are fe(0) = ged (0) = 0, fe non-decreasing, ged non-decreasing for x ³ 0, convex and symmetric, ged(-x) = ged (x).
The formulation includes no explicit constraints on edge diversity. These are instead included in the cost functions ged that penalise routings where a large part of one demand flows on the same edge. With the cost functions fe linear and ged piece wise linear FF is easily solved to optimality by e.g. using the shortest flow augmentation path technique from Busacker and Gowen [24].
The formulation is made for undirected networks but can also cover directed networks as negative flows can be prohibited by cost penalties in ged. Thus we can also model node diversity in the standard way of splitting each node into one entry vertex and end one exit vertex with a directed arc from the former to the latter. For the flow on this node arc is also applied a convex cost function g. Also each edge is split into two opposite arcs, each going from the exit of one end node to the entry of the other. As the shortest augmentation path algorithms normally utilises a representation where each edge is split into two arcs it is sufficient to manipulate this representation. This means that the shortest augmentation path algorithm in the case of node diversity constraints will have to handle a slightly increased graph of 2|N| vertices and 2|E|+|N| arcs instead of the normal |N| and 2|E| respectively.
The formulation FF covers problems where individual flows have several sources and sinks with given demands. Thus if we want two disjoint (node or edge) path of the same size from one gateway pair in one country to one gateway pair in another country, we can find it by the flow augmentation path algorithm. However we can not prescribe which gateway in the first country that should communicate with which in the other. Thus is the gateways in the first country are A and B and those in the second C and D, we will know in advance whether the paths will be A-C and B-D or A-D and B-C.
The nice optimality properties of the flow augmentation algorithm holds only for a linear cost function F. If fe are concave we can get some marginal improvement results. Let x0 be a feasible solution and L a linear function such that L(x0) = F(x0) and L(x) ³ F(x) for all feasible x. If we then re-optimise some or all individual flows for the target function L+G we will get a solution that at least is not worse than the previous.
If the cost function fe are neither linear nor concave we have problems using the flow augmentation algorithm for marginal improvement. This algorithm works by successively increasing the size of an optimal flow and is not fitted for changes of an already existing flow. One problem is that the shortest path algorithm may encounter negative cycles. One approach could be to introduce the dual variables called node potentials wnd. These provide a simple local optimum criterion for the flow of each demand d0. With the notations than ne is the terminating node of edge e and n-e is the originating node and also
the flow of d0 is optimal with respect to a flow modification of size |d| if for all edges e
for d of both positive and negative sing.
One method for finding a local optimal solution is the out-of-kilter algorithm. Provided that the optimality condition is not satisfied this either finds a set of node potentials satisfying the previous equation or a re-routing cycle decreasing the cost. Still the result will only be locally optimal with respect to modifications to the flow of one demand at a time. Node potentials can also give useful information to other optimisation algorithms.
In the optimisation of a network flow for a target function with local convexities we might get a flow scattering effect. If e.g. we have a demand of 5 units between two nodes with the requirement that at most 3 may be on the same edge, the result may be two disjoint paths of size 2 and a third path of size 1 which is partly in common to both the other paths. This might be a bad solution due to circumstances not included in the model. One way of avoiding this when it is not allowed to divide the flow units, is to optimise the flow as if the demand was 6 units only using augmentation paths of size 3. After all optimisation of the demand one of the paths can be reduced in size.
2.1.2 Path-flow
In this model, a number of predefined possible routing paths are given for each demand. The main variables are the flows (non-negative) to be routed along each path. The model is studied for network design problems without reliability aspects.
The model is in [18] applied for a more accurate modelling for shorter term planning of a transmission network. There are included diversity constraints with respect to failures that affect several edges at the same time. To keep modular sizes, the problem is a mixed integer linear programming. The solution methods used were column generation, row generation and sequential linear programming. This approach can be extended to the formulation FF provided that both functions fe and ged are convex and piece wise linear.
The result will depend on how well chosen is the predefined set of routing paths. One can expect that it would be a more difficult problem to find a good set of routing paths in a network structure optimisation problem than in a problem regarding the utilisation of an existing network.
2.1.3 Path formulation
The path flow formulation was based on predetermined paths with variable flow sizes. By path formulation we denote the approach where it is the flow sizes that are predetermined while it is the path itself that is optimised. In line with this we will no longer use "demand" to denote the total demand between two nodes but the part that is to be routed on one path only. With this formulation we loose the nice optimal solution by the flow formulation to edge-or node-diversity at linear costs. On the other hand the extension to diversity with respect to more complex failure situations is simple. That may be useful at situations where the network cost is better modelled with edges representing transmission systems or high order paths instead of cables. It can also handle the situation where a demand A-B is to be diversified to a demand C-D. The approach is used in the Swedish computer tool "ROUTE1" based on the following formulation: