Transcript ppt - University of Alberta

E E 681 - Module 14
The “Forcer” Concept
& Forcer-Clipping Ring-Mesh Hybrid Networks
W.D. Grover
TRLabs & University of Alberta
© Wayne D. Grover 2002, 2003
Introducing the “Forcer” Concept:
Why does span BC have 7 spares in this design?
(10,
A
2)
C
(10,
A
2)
C
(10, 2)
A
C
5
5
(3, 5)
5
(3, 5)
(7, 5)
(3, 5)
(7, 5)
(2, 5)
(2, 7)
(2, 7)
(7, 5)
(2, 5)
(2, 5)
(working,spare)
B
2
(2, 7)
D
B
D
B
D
•
If AC is cut, 5 restoration paths exist on ABC and 5 on ADC.
•
If AB is cut, 2 restoration paths exist on ACB and 5 on ADCB.
– > AB ‘forces’ 7 spares on BC
•
Similarly, Span AC is the forcer for spans AB, AD, and DC (5 spare links)
•
Forcer threshold is the decrease needed (in the number of working links) to change a forcing
span into a non-forcer (for AB that would be 3).
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
Forcer relationship
‹#›
The Forcer Concept (by example)
2
“Forcer Skeleton”
Span Number
Working links, Spare links, Forcer Magnitude
1
74,53,46
7
53,74,32
2
71,29,-27
3
5
55,20,24
1
6
Forcer Span
4
53,0,-37
“ All non-forcer spans
could have wi =0 and
the total spare
capacity for 100%
span restorability
would not be any
lower.”
• Forcers are red
17
47,28,1
8
16,45,-29
3
71,19,17
6
52,6,-32
7
9
68,14,-8
4
11
51,39,13
13
16,41,16
5
10
59,18,1
15
50,3,-37
16
48,23,-3
8
20
64,22,-4
9
22
65,33,-14
21
78,34,53
23
34,78,19
18
41,16,41
14
81,0,-12
19
57,3,-30
Network 1
- “Bellcore” (NJ LATA)
- with published demand data
- 11 nodes
- 23 spans
- Average degree = 4.2
Notes:
12
48,27,1
• Forcer magnitudes are the
amount of wi by which the
given span is above the
threshold of being a forcer.
• Non-forcers has a
negative forcer magnitude
indicating how many wi
additions are possible
without requiring any
increase in total network
spare capacity.
11
The forcer skeleton alone accounts for all
the spare capacity required in the optimal design.
10
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Formal Statements
• Preamble:
– In general, for any span j, there will always be some other span i,
which will require a number of spare links on j, that is equal to or
greater than that required by any other failure span.
– When this relationship is true, we say that span i is the forcer (or a
co-forcer) of span j.
• re: co-forcer: more than one span may require the same number of
spares on span j, so the forcer relationships may be many-to-one.
• Definition:
A forcer span is any span for which an increase in network
total sparing is required to maintain restorability if the
span's working capacity is increased.
– Conversely, a non-forcer is a span on which at least one working
link may be added without requiring any additional spare capacity
for the network to remain 100% restorable. “Super-restorability”
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Algorithms for forcer analysis
1. Iterate the mesh spare capacity optimal solution:
– idea is to observe change in
spare
as wi values are reduced.
• solve an initial mesh spare capacity placement (scp) problem
- for given set of wi
- record scp0 =
spare
• for every span
- j:=0; spare_tot(j) := scp0
repeat
wi := wi -1 ; j:=j+1 ;
re-solve scp ;
spare_tot(j) < spare_tot(j-1) ?

if no, span i is a (now) a non-forcer; done_loop := true
if yes, span i is a (still) a forcer
until done_loop (and exit with j-1 as the “forcer strength” of span i)
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Algorithms for forcer analysis
2. Use a routing model of the restoration process:
– idea is to discover which failures fully require the si values found on
other spans.
• solve an initial mesh spare capacity placement (scp) problem
• for every span x (taken as a failure span)
- run “ksp” as a simulation of the restoration process
- for every span i in the ksp pathset for failure x:
- record s i (x) - the number of spares on span i
used upon failure of span x.
- if (s i (x) = s i ) then span x is a forcer of span i.
- else (if s i (x) < s i then span x is not a forcer of span i.)
until {done all spans, x} (and exit with the matrix of s i (x) values )
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Information encoded in the si (x) results
when span x fails .....
how much spare
si (x) table
does it use on
span i ?
(x,i) where s i (x) = s i
A. the logical forcer structure:
• for span i, every other span x such that (s i (x) = s i )…
is a (co-) forcer of span i .
• for every span i, there must be at least one such other span x
Class: (or else what ...?)
• non-forcers are spans x such that s i (x) = s i is false for every i
B. measures of forcer magnitude: .... (next slide)
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Measures of Forcer Magnitude encoded in the si (x) ...
x = a particular span, considered in its role as a possible forcer span
i, j = other spans of the network.
si (x) = amount of spare capacity used on span i, by restoration of span x.
Forcing Strength of span x on a specific
other span i :
Logical Forcer status of a span x


Fi ( x)  max  si ( x)  max si( j ),0 
j  i, x


F *( x)  0  Forcer  true
F *( x)  0  Forcer  false
“ latent forcer ”
Measures of Global Forcer Strength of span x:
F *( x)

max  Fi ( x)
ix
E E 681 - Module 14
Or...
F*( x)


i  {S  x}
© Wayne D. Grover 2002, 2003
Fi ( x)
‹#›
Understanding the forcer magnitude and
“latent forcer” relationships
Span x
Forces 14 spares
for its restoration


Fi ( x)  max  si ( x)  max si( j ) , 0 
j  i, x


 max 14  10, 0
This D is the “forcer magnitude”
4
of x on i.
Span i
Requires 10 spares
on span i
for its restoration
All other spans
require < 10
spare on span i
Span j
i.e. span j is the
next latent forcer.
Span j
E E 681 - Module 14
max si ( j )  10
j  i, x
...
Span k
© Wayne D. Grover 2002, 2003
Aside from x itself,
no other span requires
as much spare on i
as does span j.
‹#›
An approach to ring - mesh hybrids based on the
forcer analysis of mesh networks
•
Motivation:
– Hybrid designs may be lower in cost than pure ring or pure mesh.
• Pure ring designs typically contain some very inefficient individual rings
• Efficiency of pure mesh designs may be limited by dominant forcer effects (
demand-topology interactions, to be explained).
reference paper: W.D. Grover, R.G. Martens, “Forcer-Clipping: A Principle for Economic
Design of Ring-Mesh Hybrid Transport Networks”, accepted (July 2000) for publication in
Information Technology and Management, Special Issue on Design of Communication
Networks.
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Why hybrids?: Comparing ADM-based rings and Xconnect based mesh
W3
S3
Protection
S
W
W
DCS
S1
S2
- only dropped traffic
needs terminations
W2
W1
DCS / OCX mesh
ADM / OADM rings
Termination costs 
Termination costs 
Network redundancy 
Network redundancy 
RING
$  ADM/OADM based
$  Sparing high
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
MESH
 DCS/OXC based $
 Sparing low
$
‹#›
A first view of the hybrid concept being considered ...
ADM
Glassthrough
Selected “Forcer clipping”
Ring-2
Rings
hybrid transport
network
X-connect
“ Residual
Ring-1Mesh”
Logical Demand
Physical Topology
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
An important clarification…
•
This is not a “multi-layer scheme” in the sense of involving fault
escalation.
•
Every demand is protected on each segment of its route either in a
ring- or a mesh-survivability domain.
•
Both ring and mesh components act simultaneously and
independently to protect demand segments in their domains
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
The “forcer-clipping” hypothesis
• Preamble:
– Measures such as F*(x) let us pinpoint which spans most drive the spare
capacity requirements of the surrounding restorable mesh network design.
– F*(x) reflects the total 'height' by which span x's working link quantity is
above the point at which it would no longer be a forcer (i.e., other spans
would become forcers, halting the relief of spare capacity)
•
Main idea:
– if the strongest forcers were removed or lowered, the complete mesh
network would become more efficient
– maybe rings could be used to “clip off” these worst forcers ....
– hypothesis: a ring might be placed on the mesh network to 'clip the
tops' off of one or more of the forcer spans, thereby more than
proportionally reducing its total working and spare capacity cost.
• Net cost reductions would arise if the cost of the forcer-clipping ring is
less than the net savings in the underlying mesh layer after its working
capacity is adjusted and its spare capacity plan is re-optimized.
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
The “Forcer Clipping” Hypothesis
• Rings could “clip the tops off ” strong forcers in the mesh,
resulting in net savings, exceeding the cost of the rings.
Forcer span
Self-contained BLSR
“clips” off strong forcers
spare capacity
‘hidden’
forcer
Forcer span
Reduces &
levels
underlying
mesh
“forcer” landscape of a puremesh network
Residual mesh forcer landscape
and “forcer-clipping” rings
For certain ring placements, economies may arise from:
1) enhancement of the residual mesh capacity efficiency, due to forcer clipping
2) creation of a well-loaded ring, displacing wi quantities from the mesh, lowering
relative termination costs.
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Example of some actual ring-placement trials
- just to see the nature of how ring and mesh interact in a capacity-design sense
- not yet guided by forcing clipping principle, but quantitatively exact mesh network
redesigns following each ring trial placement
Example uses a 12 unit-capacity ring
(9,9)
(9,10)
Pure mesh:
(10,9)
(10,10)
B
Redundancy =
129 / 154 = 0.84
A
C
(16,3)
(16,0)
(16,8)
(16,14)
Test ring 1:
Revised mesh:
(7,8)
(7,14)
E
G
(17,10)
(29,16)
(9,10)
(9,10)
(2,9)
(14,20)
Capacity return ratio =
(2,9)
(14,20)
Z
F
“Capacity return ratio” =
total (mesh working + re-designed sparing) reduction
total (w + s) capacity represented by ring placement
(129-84) + (154-106)
4 x 12 x 2
= 0.969
(18,9)
(30,15)
E E 681 - Module 14
Redundancy =
84 / 106 = 0.79
High CRR --> good economics
© Wayne D. Grover 2002, 2003
‹#›
Example of some actual ring-placement trials
- just to see the nature of how ring and mesh interact in a capacity-design sense
- not yet guided by forcing clipping principle, but quantitatively exact mesh network
redesigns following each ring trial placement
Example uses a 12 unit-capacity ring
(9,10)
(9,10)
Pure mesh:
(10,10)
(10,10)
B
Redundancy =
129 / 154 = 0.84
A
C
(16,0)
(16,0)
(4,3)
(16,14)
Test ring 2:
Revised mesh:
(0,13)
(7,14)
E
G
(17,17)
(29,16)
(9,10)
(9,10)
(14,20)
(14,20)
Capacity return ratio =
(14,20)
(14,20)
Z
F
“Capacity return ratio” =
total (mesh working + re-designed sparing) reduction
total (w + s) capacity represented by ring placement
(129-117) + (154-123)
4 x 12 x 2
= 0.45
(30,14)
(30,15)
E E 681 - Module 14
Redundancy =
117 / 123 = 0.95
High CRR --> good economics
© Wayne D. Grover 2002, 2003
‹#›
Heuristic Algorithms based on “Forcer Clipping”
Find all cycles of
network graph
Forcer analysis of
initial mesh
Use forcer assessments to
build ranked “short-list”
of ring placements
- Heuristic 1: sums the global forcer magnitudes F*(x) of
spans in the cycle
- Heuristic 2: looks at the fraction of logical forcers
in the cycle, i.e.  {F *( x)  0}
xcycle
|{x  cycle}|
Place a “short-list” ring
Callable
CPLEX
Residual mesh re-design
Assess total economic impact
at least one
ring proves in
Place max-payback ring and
permanently alter the residual
mesh design
no further gain
from any ring
Repeat until no further
rings prove-in
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Heuristic Algorithms: Details
1. The optimal spare capacity problem of the initial pure-mesh network is solved.
2.
All elemental cycles of the network graph are generated.
3. Forcer analysis is done, and the forcer-clipping merit and ranking of each ring candidate is determined.
4. The top-ranked candidates (by the criteria of 3.) are stored in a working set.
5. Main loop: (until the economic return factor of the best ring is < 1)
a) Secondary loop: (until all the candidate rings in the working set have been tested)
1) Place candidate ring.
2) Create IP tableau for the modified mesh design.
3) Solve the relaxed IP problem with CPLEX.
4) Obtain the new spare capacity total from the solution.
5) Calculate the economic return factor (capacity return x mesh cost/ring cost where mesh cost = 1
and ring cost = economy of scale factor x cost factor).
6) Compare the ring with the best found so far (the first ring excluded), replace if better.
b) If the economic return factor for the best ring is  1, it is placed and the mesh permanently altered.
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Example
2
Span Number
Working links, Spare links, Forcer Threshold
Step 1: Forcer Analysis Stage
1
74,53,46
7
53,74,32
2
71,29,-27
3
Pure Mesh Reference
5
55,20,24
1
Spare Capacity: 625
Working Capacity: 1252
Total Capacity: 1877
6
12
48,27,1
4
53,0,-37
8
16,45,-29
3
71,19,17
Very weak forcers
(F*(x)=1)
are ignored here
17
47,28,1
6
52,6,-32
7
9
68,14,-8
4
11
51,39,13
13
16,41,16
5
10
59,18,1
15
50,3,-37
18
41,16,41
14
81,0,-12
16
48,23,-3
8
19
57,3,-30
20
64,22,-4
9
22
65,33,-14
21
78,34,53
11
23
34,78,19
Forcer Span
10
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Example (cont’d)
After 3 ring placement iterations
OC-48 BLSR (x3)
Spare Capacity: 625  323
Working Capacity: 1252  730
Total Cost: 1877  1705
Net Cost Reduction: 172 (9%)
Ring Cost Factor = 0.8
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Example (cont’d)
2
Span Number
Working links, Spare links, Forcer Threshold
Residual Mesh Resultant
1
26,7,22
7
5,26,-2
- lower spare capacities
2
23,9,-1
3
5
7,24,-19
1
6
- increased mesh efficiency
12
48,1,-1
4
53,1,-2
17
0,25,-25
8
16,17,2
3
23,11,-22
6
52,4,1
7
9
20,33,-23
4
11
51,15,-10
13
0,0,0
5
10
59,17,1
15
50,4,-24
18
0,0,0
14
81,0,15
16
48,26,-4
8
19
57,21,1
20
64,14,19
9
22
17,25,-36
21
30,13,30
11
23
0,30,-13
Forcer Span
10
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
An Optimal Formulation
(for assessment of heuristic performance)
S
M
Minimize: cost of spare and working in mesh,
plus costs of rings placed.
 c [i ] ( s  w )    c [ r ] 
Subject To: 1) The mesh must be restorable:
Yi = set of eligible rest routes for span i
xip = restoration flow assigned to pth elig.
route for restoration of span i.
x
2) The mesh working capacity is reduced by rings:
R = set of all cycles of graph
3) Restoration sparing for the residual mesh:
Zi j = { Yi : route contains span j }
4) Ring capacity is modular (M modularities):
bq is the working capacity offered by the
qth modular ring size.
m
i
i 1
ip
pYi
q
r
i
rR q 1
 wi
i  1,
wi   Br ,i  wi0
,S
i  S
r R
x
ip
p  Zi j
Bri 
 sk

q 1.. M
i  S ; k Vi
bq r
q
r  R ; i  S [r ]
Reference: W. Grover, R. Martens, "Optimized design of ring-mesh hybrid networks,” Proc. DRCN 2000.
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
q
Other Data for Results:
 12, 24, 48-unit module ring capacities
 {2cost4capacity} economy-of-scale model for rings
 4-fibre BLSR ring capacity model
 ADM-ring cost / unit installed capacity =
mesh * cost factor @ 24 - unit modular capacity (see next slide)
 ‘gravity type’ point-to-point demand patterns
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Ring-Mesh Relative Costing Model
1.0
relative cost scale:
ring / mesh
OC-12
0.8
OC-24
“Cost factor” is defined as
relative cost per physical unit capacity
to average DCS-terminated unit capacity
in mesh for OC-24 ring
Mesh (per unit capacity)
OC-48
May apply
economy of
scale rule, e.g.,
4 times
capacity for 2
times cost
Rings (modular at
sizes 12, 24, 48)
Example:
• Cost factor = 0.8 implies that an OC-24 ring span (actually representing 48 units of capacity)
is cost -equivalent to 0.8 (48) = 38.4 units of capacity on a mesh span
• Ring relative cost then scales up or down according to the economy of scale model employed
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Some Results
( … where optimal and heuristic can be compared)
Network #1
Network #2
Network #3
11 nodes
11 nodes
15 nodes
23 spans
20 spans
28 spans
1877
1705
2211
1750 (6.8 %)
1504 (11.8%)
2092 (5.4 %)
7.3 min
1.7 min
50.8 min
1 ring
1 ring
1 ring
1705 (9.2 %)
1509 (11.5 %)
2092 (5.4 %)
20.1 min
2.1 min
38.4 min
3 rings
1 ring
1 ring
1667 (11.2 %)
1487 (12.8 %)
2088 (5.6 %) *
36.9 min
6.3 min
25.3 hrs
4 rings
3 rings
4 rings
1617
1437
1888
Initial Mesh
(reference case)
Heuristic #1
Heuristic #2
Optimal Solution
Method
LP Lower Bound
Average cost
savings %

Objective function values,
(% savings),
execution time,
number of rings
8.0
8.7
9.9

“Cost savings” are
relative to objective
function value for
“pure-mesh”
Ring cost factor = 0.8
* result obtained with MIPGAP = 200
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Some Results
( … where optimal and heuristic can be compared)
Objection function values (total cost), execution times, and number of rings placed
Initial Mesh
(reference case)
Heuristic #1
Heuristic #2
Optimal Solution
Method
LP Lower Bound
Network #1
Network #2
Network #3
Average
11 nodes
11 nodes
15 nodes
cost
23 spans
20 spans
28 spans
Savings %
1877
1705
2211

1589 (15.3 %)
1350 (20.8 %)
1913 (13.5 %)
10.5 min
2.5 min
2.1 hrs
2 rings
2 rings
3 rings
1507 (19.7 %)
1373 (19.5 %)
1740 (21.3 %)
20.9 min
2.1 min
4.4 hrs
4 rings
1 ring
4 rings
1411 (24.8 %)
1275 (25.2 %)
1873* (15.3 %)
10.9 hrs
31.2 min
23.3 hrs
5 rings
5 rings
8 rings
1311
1175
1473
Ring cost factor = 0.6
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
16.5
20.2
21.8

* result from optimal formulation after 24
hours
‹#›
Other Results (where only the heuristic can go):
Heuristic
#2
Net #4
Net #5
Net #6
19 nodes
16 nodes
27 nodes
39 spans
29 spans
48 spans
23.8%
38.6%
39.5%
8 rings
12 rings
11 rings
11.9 hrs
1.0 hr
2.3 hrs
% savings over optimal pure mesh
Number of rings placed
CPU time
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Question
But if rings are less costly, won’t the solution just slide to an all-rings design ?
No: There is a true Cross-Architectural Optimum design point
Combined Cost of Rings and Mesh
1900
1850
Cost
1800
1750
1700
1650
1600
0
1
2
3
4
Number of Rings Used
Network #1, Heuristic #2
Ring Cost Factor = 0.8
E E 681 - Module 14
Test case where heuristic was compelled
to place one more ring (4) than it wanted.
© Wayne D. Grover 2002, 2003
‹#›
Insights - understanding hybrid and why it “works”
•
A good forcer clipping ring pays for itself by:
• (1) attaining good utilization for itself, while displacing mesh capacity
• (2) enhancing the mesh efficiency through forcer-levelling.
•
But even when ring transport is up to 40% cheaper than mesh,
architectural aspects lead to a hybrid - not a pure ring outcome. why?
• Pure ring or pure mesh now seen to arise only as limiting cases:
– (1) “rings must be rings” …closing the circle limits ring efficiency.
– (2) mesh residual become more and more efficient (because it becomes
more forcer leveled) and eventually no ring addition can pay off anymore
•
Why is the prediction of “forcer levelling” in the residual meshes
not more evident in the results than actually seen?
• When rings are placed they scour out mesh capacity to their full depth,
not just the forcer peaks they were placed to ‘clip’.
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›
Summary of Main Findings
•
The “forcer-clipping” hypothesis is suggested as an effective
principle in ring-mesh hybrid network design.
•
Advent of DCS with integrated ADM shelf functionality motivates /
enables this type of true hybrid.
•
Heuristics observed to be within ~ 5% of optimal for test cases
– This is taken as confirming the basic validation of the forcer-clipping insight.
•
Heuristic #2 seems superior, and executes in reasonable time for
large problems
– Heuristic 2 thought to be “selecting in” more co-forcer and latent-forcer
combinations which the economic trial placements then discover and exploit
•
This work suggests that in general even mesh networks should be
examined for “express ring” opportunities.
E E 681 - Module 14
© Wayne D. Grover 2002, 2003
‹#›