Transcript Topological design of telecommunication networks

17th International Teletraffic Congress
Topological design of
telecommunication networks
Michał Pióroa,b, Alpar Jüttnerc, Janos Harmatosc,
Áron Szentesic, Piotr Gajowniczekb, Andrzej Mysłekb
a
b
c
Lund University, Sweden
Warsaw University of Technology, Poland
Ericsson Traffic Laboratory, Budapest, Hungary
Outline
• Background
• Network model and problem formulation
• Solution methods
–
–
–
–
Exact (Branch and Bound) and the lower bound problem
Minoux heuristic and its extensions
Other methods (SAN and SAL)
Comparison of results
• Conclusions
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
1/15
Background of Topological Design
problem:
localize links (nodes) with simultaneous routing of given
demands, minimizing the cost of links
selected literature:
Boyce et al1973 - branch-and-bound (B&B) algorithms
Dionne/Florian1979 – B&B with lower bounds for link
localization with direct demands
Minoux1989 - problems’ classification and a descent method
with flow reallocation to indirect paths for link localization
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
2/15
Transit Nodes’ and Links’ Localization
– problem formulation
Given
– a set of access nodes with geographical locations
– traffic demand between each access node pair
– potential locations of transit nodes
find
–
–
–
–
the number and locations of the transit nodes
links connecting access nodes to transit nodes
links connecting transit nodes to each other
routing (flows)
minimizing the total network cost
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
3/15
Symbols used
constants
hd volume of demand d
aedj =1 if link e belongs to path j
of demand d, 0 otherwise
ce cost of one capacity unit installed
on link e
ke fixed cost of installing link e
B budget constraint
Me upper bound for the capacity
of link e
variables
xdj flow realizing demand d allocated to path j (continuous)
ye capacity of link e (continuous)
se =1 if link e is provided, 0 otherwise (binary)
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
4/15
Network model adequate for IP/MPLS
LER
L1
LSR
L3
L2
LSP
• LER  access node
• LSR  transit node
• LSP  demand flow
LSR
LSR
L4
LSR
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
LER
L4
5/15
Optimal Network Design Problem
and Budget Constrained Problem
ONDP
minimize
C = Se ce ye + Se kese
constraints
Sj xdj = hd
SdSj aedj xdj = ye
ye  Mese
BCP
minimize
C = Se ce ye
constraints
Se kese  B
Sj xdj = hd
SdSj aedj xdj = ye
ye  Mese
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
6/15
Solution methods
• Specialized heuristics
• Simulated Allocation (SAL)
• Simulated Annealing (SAN)
• Exact algorithms: branch and bound (cutting planes)
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
7/15
Branch and Bound method
• advantages
– exact solution
– heuristics’ results verification
• disadvantages
– exponential increase of computational complexity
– solving many “unnecessary” sub-problems
1
0
1
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
8/15
Branch and Bound - lower bound
• LB proposed by Dionne/Florian1979 is not suitable for
our network model – with non-direct demands it gives
no gain
• We propose another LB – modified problem with fixed
cost transformed into variable cost:
minimize
C = Se xeye + Seke
where
xe = ce + ke /Me
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
9/15
Minoux heuristics
The original Minoux algorithm:
step 0
1
2
3
4
(greedy) allocate demands in the random order to the shortest paths:
if a link was already used for allocation of another demand use only
variable cost, otherwise use variable and installation cost of the link
calculate the cost gain of reallocating the demands from
each link to other allocated links
(the shortest alternative path is chosen)
select the link, whose elimination
results in the greatest gain
reallocate flows going through
elimination
the link being eliminated
if improvement possible
go to step 2
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
10/15
Minoux heuristics’ extensions
• individual flow shifting (H1)
• individual flow shifting with cost smoothing (H2)
Ce(y)
=cey + ke ·{1 - (1-)/[(y-1) +1]}
=0
if y > 0
otherwise.
• bulk flow shifting (H3)
– for the first positive gain (H3F)
– for the best gain (H3B)
• bulk flow shifting with cost smoothing (H4)
– two versions (H4F and H4B)
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
11/15
Other methods
• Simulated Allocation (SAL) in each step chooses, with
probability q(x), between:
– allocate(x) – adding one demand flow to the current state x
– disconnect(x) – removing one or more demand flows from
current x
• Simulated Annealing (SAN) starts from an initial
solution and selects neighboring state:
– changing the node or link status
– switching on/off a node
– switching on/off a transit or access link
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
12/15
Comparison - objective
Relative cost difference for ONDP with respect to the optimal solution [%]
network n
H1
H2
H3F
H3B
H4F
H4B
SAN
N7
0
0
0
0
0
0
0
0
N7
1
0
0
0
0
0
0
0
N7
2
0
0.90
0
0
0
0
0
N7
3
4.90
7.78
4.90
4.90
3.39
3.39
0
N7
5
114.23 110.84
20.29
20.29
13.02
0
11.66
N7
6
125.61 125.82
19.64
19.64
5.99
0
12.71
N14
0
0
0
0
0
0
0
0
N14
1
0.02
0.05
0.02
0.02
0.03
0.03
0
N14
2
0.91
1.15
0.63
0.63
0.26
0.35
0
N14
3
10.27
5.65
8.11
8.11
3.03
2.95
1.31
N14
5
128.35
17.92
43.86
37.73
10.70
10.70
25.4
SAL
0
0
0
1.55
0
0
0
0
0.44
2.26
4.39
Relative cost difference for TNLLP with respect to the optimal solution [%]
network n k
H1
H2
H3F
H3B
H4F
H4B
SAN
SAL
N14
4 4
24.13 11.59 24.13 24.13
3.43
2.28 41.24
0
N14
4 5
23.72 11.39 23.72 23.72
3.37
2.24 39.63
0
N14
4 6
22.73 11.97 22.73 22.73
4.97
3.98 25.21
3.55
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
13/15
Comparison - running time
TNLLP
ONDP
10000
10000
H1
1000
running time [s]
running time [s]
1000
100
10
1
0,1
0,01
H2
H3F
100
H3B
10
H4F
H4B
1
SAN
SAL
0,1
0
N7
2
N7
5
N7
0
N14
2
N14
5
N14
0
N28
2
N28
5
N28
(4,4) (4,5) (4,6) (5,4) (5,5) (5,6) (4,4) (4,5) (4,6) (5,4) (5,5) (5,6)
N14 N14 N14 N14 N14 N14 N28 N28 N28 N28 N28 N28
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
14/15
Conclusions
• proposed modification of Minoux algorithm can
efficiently solve TNLLP, especially H4B
• Simulated Allocation seems to be the best heuristics
• proposed lower bound can be used to construct
branch-and-bound implementations
• need for diverse methods - hybrids of the best shown
here, e.g. Greedy Randomized Adaptive Search
Procedure using SAL seems to be a good solution
© M.Pioro, A.Jüttner, J.Harmatos, Á.Szentesi, P.Gajowniczek, A.Mysłek
Topological Design of Telecommunication Networks
15/15