Transcript EE681_Grover_Module_last

E E 681 Fall 2001 - Lecture 23
Course Wrap-up & Challenges for
Future Optical Networking
Matthieu Clouqueur
TRLabs & University of Alberta
E E 681 Course Wrap-up
• Phase 1:
– What is a transport network?
End-users
Service layer
client
Logical layer
transport
Physical layer
system
geographical
– Concepts of reliability, availability, general methods for availability analysis
• Reliability is a mission-oriented question for non-repairable systems. In transport
networks we are interested in availability of service (in particular availability of
end-to-end service paths)
• The method used them most to evaluate a system’s availability is the cut-sets
method
E E 681 - Lecture 23
2
E E 681 Course Wrap-up
– Simple survivable transport network architecture: Automatic Protection
Switching
1
PT
L
D
Primary path
M
IL
W
Ub1
D
T
R
T
T
O
L
D
KSC
Uw
N working
C
LEV
N
N
W
R
K
PH
L
A
B
L
T
Uw
U b2
H
ST
Ut1
N
W
O
R
Ut2
s pare
Us
Backup path
– Optimization for Network Planning
• Design of capacity efficient transport network will require optimization techniques
• The general technique that will be used is “Mathematical Programming” which
formulates the problem as:
Minimize (or Maximize): {Objective Function}
Subject to: constraint 1
constraint 2
constraint 3...
E E 681 - Lecture 23
3
E E 681 Course Wrap-up
– Graph Theory:
• Vocabulary of general Graph Theory and vocabulary for transport network design
– Routing in transport networks:
• Dijkstra’s algorithm finds the shortest path between any pair of nodes in a
weighted graph.
• The k-shortest path algorithm (ksp) finds a set of simultaneously feasible paths
between two nodes. It is a good model for mesh span-restoration.
• The min-cut max-flow theorem states that “The maximum flow that is feasible
between two nodes is equal to the minimum capacity of any cut in the facility
graph between these two nodes”
• The ksp algorithm does not necessarily achieve max-flow because of a special
graph configuration called the “trap topology”
• The max-flow algorithm avoids the trap topology by allowing a change in routing
decision thanks to “reverse arcs”
• Optimal routing can also be obtained by solving mathematical programming
formulation for the max flow problem
E E 681 - Lecture 23
4
E E 681 Course Wrap-up
– Computational complexity:
• Solving large optimization problems can become very slow (if at all possible)
using Mathematical Programming
• An alternative is to accept that the solution be sub-optimal (but not too far from
optimality) if it can be found quickly: Such methods are called Heuristics
• Meta-heuristics are heuristics that apply to many optimization problems and will
be an option for solving complex network design problems:
– Simulated Annealing
– Genetic Algorithms
– Tabu Search
E E 681 - Lecture 23
5
E E 681 Course Wrap-up
• Phase 2:
– Rings: a very common survivable transport network architecture
• Unidirectional path-switch rings (UPSR)
• Rings are a simple survivable
architecture with fast restoration
• It is a protection mechanism
(restoration paths are preplanned)
• Bi-directional line-switched rings
• Rings require at least 100%
spare/working redundancy
Loop Back
Cable cut
(a) Normal Operation (before failure)
E E 681 - Lecture 23
(b) Protection Operation (after failure)
6
E E 681 Course Wrap-up
– Aspects of ring design:
• Ring sizing: For a given set of demands to be served by a ring, what is the
minimum ring size that is required?
• Ring loading: For a given ring (with known capacity), what is the maximum
number of demands (or demand volume) that can be served?
– More generally, the ring design problem is:
• For a set of end-to-end demands what is the lowest cost ring design that can
serve all demands?
• This involves: Cycle generation, ring selection, determination of glass-through
locations, demand routing
• Some measures of ring design quality are: Demand capture, Capacity
efficiency (the cost of a design is a combination of these two aspects that
depends on whether we are in the access or in the long-haul)
• Ring design is a very complex problem that can be formulated with
mathematical programming but in practice it requires the use of heuristics
(Tabu Search for example)
E E 681 - Lecture 23
7
E E 681 Course Wrap-up
– Special aspect of ring-design: Dual ring interconnect arrangements (DRI)
• The intent is to eliminate single points of failures in end-to-end service paths
served in ring-based networks
• There is two ways to transit from one ring to another (two gateways)
• Two types of arrangements are possible: “drop-and-continue” (also called
“matched nodes”), dual feeding.
– The general drawbacks of rings are:
• Very capacity inefficient
• Difficult to design
• Not flexible in terms of adding new service paths to an existing design (problem
of scalability): Establishing a new service path may require the addition of a
whole new ring with very low utilization.
E E 681 - Lecture 23
8
E E 681 Course Wrap-up
– Mesh Networks:
• They allow routing of demands on shortest path (simple and generally more
capacity efficient)
• They allow spare capacity sharing between all spans of the network (instead of
between spans of the same ring)
• Restoration of failures can be done either between the end-nodes of the failed
span (span restoration) or between the origin and destination nodes of all
affected service paths (path restoration)
– Design of mesh networks:
• Several formulations exist to do the capacity design of a mesh network:
– The Herzberg Method is the basic approach for spare capacity design of a spanrestorable network
– Variations of the Herzberg methods include: Modularity and/or joint working and
spare capacity placement for span-restoration and path-restoration.
– General issues with capacity design methods derived from Herzberg’s formulation
are: Size of the working- and restoration-route sets. A tradeoff has to be found
between optimality of the solution and optimization run time.
– Important observation: The capacity efficiency of mesh networks increases as the
nodal degree increases
E E 681 - Lecture 23
9
E E 681 Course Wrap-up
– Other aspects of mesh networks:
• Restoration paths do not need to be pre-computed, they can be found in a
distributed manner upon failure (greater adaptability to changes and no need to
maintain databases of network state)
– The Self-healing protocol allows restoration paths to be found in a distributed manner
by application of simple rules at each node based only on knowledge of the states of
adjacent links.
• The mesh architecture is more flexible in terms of adding new service paths
(adding capacity can be done on a per span basis)
– Later in the course we discovered that:
• Mesh networks have the potential (with reasonable cost increase) for serving
demands with various availability requirements (multiple service classes)
ranging between un-protected to full restorable to any dual span-failure.
• Functionally ring-based networks cannot guarantee full restorability to dual
span-failures.
E E 681 - Lecture 23
10
E E 681 Course Wrap-up
• Ring or Mesh: which architecture to choose?
– The decision factors (based on cost):
• Access: Rings seem to remain the solution of choice for access
• Metro: Ring or mesh
• Long-haul: With long distances, capacity efficiency becomes more and more
important and mesh networks become the preferable solution unless…
… the network looks like this:
Average nodal
degree d = 2.3
The nodal degree is not high
enough for mesh to be
efficient (see study by John
Doucette looking at the
effects of varying graph
connectivity)
E E 681 - Lecture 23
11
E E 681 Course Wrap-up
• Ring or Mesh: Do we need to choose?
– Not necessarily: For example, Ring-Mesh Hybrid Networks
• A ring-mesh hybrid design can contain well loaded rings (clipping off the forcers
of the mesh network) and an efficient resulting mesh
(9,9)
(9,10)
(10,9)
(10,10)
B
A
C
(16,3)
(16,0)
(16,8)
(16,14)
(7,8)
(7,14)
E
G
(17,10)
(29,16)
Due to the ring cost factor (less
than 1) the total network can be
cheaper than the original network
(9,10)
(9,10)
(2,9)
(14,20)
(2,9)
(14,20)
Z
F
(18,9)
(30,15)
E E 681 - Lecture 23
12
E E 681 Course Wrap-up
• Ring or Mesh: Do we need to choose?
– p-cycles: Let’s keep the best of both!
• A slight modification of the ring protection principle (p-cycles will protect oncycle spans as well as straddling spans) can improve greatly the capacity
efficiency of rings to bring it close to mesh efficiency and retains the restoration
speed.
E E 681 - Lecture 23
13
E E 681 Course Wrap-up
• So many ways to make a network “restorable” but how much does
that improve the availability of service?
– By “Restorable” we usually mean restorable to any single span-failure. We
therefore need to investigate multiple span or span-node failure
combinations to determine how much the availability of service has been
improved.
• Analysis of multiple failures in ring-based networks leads to closed-form models
for the service path availability.
• Analysis of multiple failures in mesh restorable networks requires a case-by case
analysis of each multiple failure.
• In both cases, guaranteeing restorability to single span-failures brings a huge
improvement to the availability of service paths (a numerical example for spanrestoration showed a reduction from 13 hours/year down to a 2.4 min/year)
• What about service paths with very high availability requirements?
– Current research on service availability is showing that mesh networks
(unlike ring-based networks) can naturally protect 20-30% of very high
availability (dual-failure restorable) demands for minimal to no cost increase.
E E 681 - Lecture 23
14
E E 681 Course Wrap-up
• Serving multiple classes of service
– The class of service that a given service path requires can be
characterized by two factors: Restoration speed required, average
availability required.
Average
availability
Banking
transactions
Span-restorable
mesh
E-mail
Ftp
Unprotected
traffic
Tele-surgery
?
Voice (telephone)
Live Video
Rings, 1+1 APS
Restoration speed
required
E E 681 - Lecture 23
15
E E 681 Course Wrap-up
• Other current research issue: Robustness of transport networks to
demand uncertainty
– A network operator does not have exact knowledge of what the demand will
be in 6 months, 1 year, 2 years, …
– Based on an estimate of what the demand will be at some point in the
future, we want to know what probability we have of being able to serve the
actual demand at that time or what percentage of the actual demand we will
be able to serve.
– The different restoration mechanisms may be more or less robust to
demand uncertainty.
– The way capacity provisioning is done could be adapted to maximize the
robustness of the network to future demands.
E E 681 - Lecture 23
16
E E 681 Transport Networking in the Future
• Future (data) optical transport networks (OTN)
– Optical:
• New optical equipment is capable of wavelength switching (Optical CrossConnects, OXC) or adding/dropping (Optical Add/Drop Multiplexers, OADM)
• From a simple point-to-point system, the optical layer will become an intelligent
optical transport network (OTN) capable of enhanced optical layer
management and distributed network intelligence
– Data:
• With increasing proportion of data traffic, capacity efficiency is not possible
anymore if bandwidth is dedicated
• Networks have to be data based.
• However these networks need to be able to provide “STM-like” service
E E 681 - Lecture 23
17
E E 681 Transport Networking in the Future
Challenges of future Optical Transport Networks*:
– Service transparency
• Optical transport networks need to be able to provide service for different types
of clients: SONET, ATM, IP,…
– Enhanced optical layer management
• Network operators will have to provide reliable service to the customers thanks
to improved signal quality monitoring in the optical network
– Real-time optical channel provisioning
• Ability to establish service paths quickly
– Optical layer restoration with performance guarantees
• Each optical channel must have restorability parameters (protected channels,
un-protected channels, restoration time required…)
Other issue:
– Multi-layer restoration will become a very important issue
• for example fast restoration can be provided at the optical layer for certain
connections and the above layers like the IP layer can do the rest)
*A. Rodriguez-Moral et al., “Optical data networking: protocol, technologies, and architectures for next generation optical transport networks and optical
internetworks,” Journal of Lightwave Technology, vol. 18, no. 12, December 2000.
E E 681 - Lecture 23
18
E E 681 Transport Networking in the Future
• How to do data transport networking?
– IP is a packet protocol but with no traffic engineering (no guarantees on
service availability, restoration time, average delay,…)
• A promising solution to data transport networking: GMPLS
– Based on MPLS, a packet switching protocol that provides traffic
engineering
– GMPLS provides management of the data plane (as MPLS) and also of
other types of traffic: TDM traffic, lambda-switched traffic and fiber-switched
traffic.
– GMPLS provides:
• Resource discovery
• Routing control
• Connection Management
E E 681 - Lecture 23
19