Transcript ppt - University of Alberta

E E 681 - Module 13
p-Cycles
W. D. Grover
TRLabs & University of Alberta
© Wayne D. Grover 2002, 2003
( Version for book website
Dec. 2003)
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Background and Motivation
“ Ring “
“Mesh”
A. 50 msec restoration times
B. Complex network planning and
growth
C. High installed capacity for
demand-served
D. Simple, low-cost ADMs
E. Hard to accommodate multiple
service classes
F. Ring-constrained routing
G. Up to 1.5 sec restoration times
H. Simple, exact capacity planning
solutions
I. well under 100% redundancy
J. Relatively expensive DCS/OXC
K. Easy / efficient to design for
multiple service classes
L. Shortest-path routing
“ Shopping list” : A, D, H, I, L (and K) please...keep the rest
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Relative Characteristics of Known
Schemes
1+1 APS,
Rings
100% redundancy: “the dividing line”
Capacity
Redundancy
p-Cycles
Mesh Span Restoration
Shared Backup Path
Protection (SBPP)
True Mesh Path
Restoration
Restoration Times
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
p-Cycles
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
p-Cycles - an “on-cycle” failure
loopback
loopback
Reaction to an “on-cycle” failure
is logically identical to a unit-capacity
BLSR loopback reaction
E E 681 - Module 13
“on-cycle” spans
have both working and spare capacity
like a BLSR
© Wayne D. Grover 2002, 2003
‹#›
p-Cycles - a “straddling span” failure
Break-in
Break-in
Reaction to a straddling span failure
is to switch failed signals onto two protection paths
formed from the related p-cycle
Straddling spans have two protected
working signal units and have
no2002,
spare
capacity
E E 681 - Module 13
© Wayne D. Grover
2003
‹#›
How much difference can this make ?
x2
A lot !
x2
Re-consider the example:
x2
x2
It consumes 13 unit-hops
of spare capacity
It protects one working signal
on 13 spans and two working
on 9 spans
x2
E E 681 - Module 13
x2
x2
x2
i.e., spare / working ratio
= 13 / (13*1 + 9*2 )
= 42%
x2
A fully-loaded Hamiltonian p-cycle
reaches the redundancy limit, 1/(d-1)
© Wayne D. Grover 2002, 2003
‹#›
Example of a whole p-cycle network design
Working span capacities arising from one unit of demand on
each node-pair:
10
Total
working capacity:
158 units
6
4
6
7
4
8
1
6
9
9
14
4
10
5
13
7
3
E E 681 - Module 13
7
11
© Wayne D. Grover 2002, 2003
7
5
2
‹#›
Design Solution: 53.8 % overall redundancy
p-Cycle Copies
A
B
C
D
E
Total:
1
1
1
2
2
7
Total protection capacity: 85 units
Redundancy:
53.8%
Optimal configuration dynamically computable or self-organized
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
ADM-like nodal device for p-cycle networking
nodal redundancy R =
 spare  2  1
 working 2  2k k  1
example : k  3  R  25%
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Summary: Important Features of p-Cycles
•
•
•
•
Working paths go via shortest routes over the graph
p-Cycles are formed only in the spare capacity
Can be either OXC-based or based on ADM-like nodal devices
a unit-capacity p-cycle protects:
– one unit of working capacity for “on cycle” failures
– two units of working capacity for “straddling” span failures
• Straddling spans:
– there may be up to N(N-1)/2 -N straddling span relationships
– straddling spans each bear two working channels and zero spare
– -> mesh capacity efficiency
• Only two nodes do any real-time switching for restoration
– protection capacity is fully pre-connected
– switching actions are known prior to failure
– -> BLSR speed
• “pre-configured protection cycles”  p - cycles
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
p-Cycle Capacity Design
A. Form the spare
capacity into a
particular set of
pre-connected
cycles !
i
j
If span i fails,
p-cycle j provides
one unit of
restoration
capacity
A span on the cycle fails - 1 Restoration Path, BLSR-like
j
i
A p-cycle
If span i fails,
p-cycle j provides
two units of
restoration
capacity
A span off the p-cycle fails - 2 Restoration Paths, Mesh-like
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
" xi , j  1 " case
" xi , j  2 " case
‹#›
Optimal Spare capacity design Typical Results
• “Excess Sparing” = Spare Capacity compared to Optimal SpanRestorable Mesh
Test
Network
Excess
spare
capacity
# of unitcapacity
p-cycles
formed
# of
distinct
cycles
used
1
2
3
4
5
9.09 %
3.07 %
0.0 %
2.38 %
0.0 %
5
88
250
2237
161
5
10
10
27
39
i.e., “mesh-like” capacity
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Understanding why p-cycles are so
efficient...
Spare
UPSR
or
BLSR
p-Cycle
…with same
spare capacity
Working
Coverage
9 Spares
cover 9
Workers
E E 681 - Module 13
“the clam-shell diagram”
© Wayne D. Grover 2002, 2003
9 Spares
cover 29
working
channels
on 19
spans
‹#›
Further comparing p-cycles to
rings
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
A Priori p-Cycle Efficiency: AE(p)
• AE (p) measures a cycle’s potential to provide
protection relationships for working channels
X p ,i

2  S S , p  SC , p
iS
AE  p  

SC,p = # on cycle
SC , p
 ci
Xp,i = 1 if on cycle
Xp,i = 2 if straddler
E E 681 - Module 13
iS X p ,i 1
SS,p = # straddlers
ci = unit cost of i
SS,p = 3
SS,p = 4
SC,p = 9
SC,p = 10
AE(p) = 1.67
AE(p) = 1.80
© Wayne D. Grover 2002, 2003
‹#›
Demand-weighted p-Cycle Efficiency: Ew(p)
(slide corrected October 2006)
• Ew(p) measures a cycle’s actual efficiency in providing
protection relationships for uncovered working channels.
Note Ew(p) can only be les than or equal to the corresponding AE(p)
Ew
Xp,i = 1 if on cycle
Xp,i = 2 if straddler
3
1
0
2
3
iS
i
2
1
4
p ,i
)
i
wi = working on i
ci = unit cost of i
iS X p ,i 1
3
2
2
4
 min( w , X
 p 
 c
AE(p) = 1.67
Ew(p) = 1.44
1
2
1
4
1
2
1
2
3
0
2
AE(p) = 1.67
Ew(p) = 1.33
1
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Self-organization of the p-cycles ...
• p-cycles certainly could be centrally computed and
configured.
– based on the preceding formulation
However, an interesting option is to consider if the
network can adaptively and continually selforganize
- a near-optimal set of p-cycles within itself,
- for whatever demand pattern and capacity
configuration it currently finds.
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Self-organization of the p-cycles
• Based on an extension / adaptation of SHN™ distributed mesh
restoration algorithm
– “DCPC” = distributed cycle pre-configuration protocol
• Operates continually in background
– Non-real time phase self-organizes p-cycles
– Real time phase is essentially BLSR switching
– p-cycles in continual self-test while in “storage”
• Centralized “oversight” but not low-level control
– Method is autonomous, adaptive
• Networks actual state on the ground is the database
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Key concepts of DCPC protocol
• Node roles:
– Cycler node state , Tandem node state
• DCPC implemented as event-driven Finite State Machine (FSM)
• Nodal interactions are (directly) only between adjacent nodes
– Indirectly between all nodes (organic self-organization)
– via “statelets” on carrier / optical signal overheads
• Three main steps / time-scales / processes
– Each nodes act individually, “exploring” network from its
standpoint as cycler node.
– All nodes indirectly compare results
– Globally best p-cycle is created
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Overview of DCPC protocol
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
How DCPC discovers “best p-cycles” (2)
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
How DCPC discovers “best p-cycles” (1)
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
DCPC Performance studies
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Illustrating the Real time phase
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Adapting p-cycles to the IP-layer …
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
IP Network Restoration
• IP Networks are already “Restorable”
• Restoration occurs when the Routing protocol updates the
Routing Tables
• This update can take a Minute or more - Packets are lost until this
happens
• Speed-up of IP Restoration is needed
• Not losing packets would be great too
• Also some control over capacity / congestion impacts needed
• p-cycles proposed as “fast” part of a fast + slow strategy that retains
normal OSPF-type routing table re-convergence
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Operation of IP-layer p-cycles
Data Encapsulation
Router
Failed Link
Data De-Encapsulation
Router
p-cycle
(a) On-Cycle Failure
(1 restoration Path)
E E 681 - Module 13
(b) Straddling Failure
(2 Restoration paths)
© Wayne D. Grover 2002, 2003
‹#›
Router Failure Restoration using
“Node-Encircling” p-Cycles
•
•
Node Encircling p-Cycles. Each Node has
a p-Cycle dedicated to its failure
For each Node, a p-Cycle is chosen which
includes all logically “Adjacent” Nodes
but not the Protected Node
NodeEncircling pcycle
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
Other
Nodes
Encircled
Node
‹#›
Router Restoration using
“Node-Encircling” p-Cycles
Node
Failure
p-Cycles are Virtual Circuits/Protection Structures which can
redirect Packets around Failures
– Plain IP is Connectionless but p-Cycles can be realized with
MPLS, IP Tunneling/Static Routes
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›
Concluding Comments
•
p-cycles offer new approaches to both WDM and IP-layer transport
– “ mesh-like efficiency with ring-like speed ”
•
Capacity-planning theory
– for 100% span restoration in WDM / Sonet with mesh sparing
– for controlled worst-case over-subscription in IP-layer
•
“Node-encircling” p-cycles
– fast integrated restoration against either router or link-failures
•
Nortel has implemented span-restoration via IP p-cycles
– ~ 10 msec restoration time, no packet loss in their experiments
•
Ongoing studies:
• Integrated planning of composite node / link restoration p-cycles
• Availability analysis of p-cycles
E E 681 - Module 13
© Wayne D. Grover 2002, 2003
‹#›