Transcript LDP, CR-LDP and GMPLS

Research Issues on Routing and Wavelength
Assignment for Wavelength Routed WDM Networks
Qualifying Exam
Hsu-Chen, Cheng
PhD. Student
Department of Information Management
National Taiwan University
10/27/2003
Outline

Introduction of Optical Networks




Optical Network Design and Engineering





WDM Technology
Optical Network Control Plane
IP/WDM Traffic Engineering
Routing and Wavelength Assignment (RWA)
Heuristics
Optical Multicasting
Multi-granularity Architecture of Optical Network
Future Research Direction
2
The Trend of Network Technology
Packet Switch
Circuit Switch
IP
E
ATM
M
SONET
DWDM
S
IP /MPLSE
SONET
M
S
DWDM
IP GMPLSE
M
Thin SONET
IP GMPLS
DWDM
OXC
DWDM
OXC
S
E
M
S
Time
Introduction of Optical Networks
3
Optical Networks

First Generation:



FDDI
Gigabit Ethernet
Second Generation:

WDM Local Area Network



WDM Wide Area Network




Passive Star Network
Single-Hop WDM Network
Wavelength routed Network
OBS
OPS
Wavelength-routed optical networks are the most
promising candidates for backbone high-speed WAN.
Introduction of Optical Networks
4
Optical Network Technologies

WDM Technology



Fixed Point-to-Point  Wavelength routed
300 λ x 40Gbps
Optical Components






OADM (Optical add/drop multiplexer)
OXC (Optical cross-connect)
Tunable Laser
Amplifier
Wavelength Converter
Wavelength Splitter
Introduction of Optical Networks
5
The Architecture of Wavelength Router
Introduction of Optical Networks
6
Physical Topology and Logical Topology


A physical topology is a graph representing the
physical interconnection of the wavelength routing
nodes by means of fiber-optic cables.
A logical topology is a directed graph that results
when the lightpaths are setup by suitably configuring
the wavelength routing nodes.
Optical Network Design and Engineering
7
The Architecture of Wavelength-routed Optical
Network
Introduction of Optical Networks
8
Optical Network Control Plane

Apparatus




IETF (Internet Engineering Task Force)
ODSI (Optical Domain Service Interconnection)
OIF (Optical Internetworking Forum)
Issues


Signaling Mechanism (UNI)
Signaling and control protocol for dynamic lightpath
establishment and traffic engineering
Introduction of Optical Networks
9
Optical Network Control Plane (cont’d)
Traffic
Engineering
Database
•RSVP-TE
Signaling Protocol
Topology and
Resource
Discovery
Topology and resource
information
•CR-LDP
Lightpath
Management
Updates
Route
information
Route
Computation
•Neighbor discovery
•Link Monitoring
•State distribution
•LMP [J. P. Lang 2001]
RWA algorithms/
traffic engineering
Link-state routing
protocol (OSPF)
Introduction of Optical Networks
10
IP/WDM Traffic Engineering

Overlay Model




Peer Model


Closer to classical IP and ARP over ATM scheme
The IP and optical network are independent of each other
Edge IP router interacts with its ingress OXC over a welldefined UNI
The IP and optical network are treated together as a single
network
Augmented Model

IP and optical networks use separate routing protocol, but
information from one routing protocol is passed through the
other routing protocol
G. N. Rouskas and H. G. Perros, A Tutorial on Optical Networks, Networking 2002 Tutorials, vol.
2497, 2002, pp. 155-193.
Introduction of Optical Networks
11
TE Model

WDM Traffic Engineering Model



MPLS Traffic Engineering Model



Minimum average packet delay
Maximize scale up capability
Overlay model
Virtual topology (LSPs)
IP over WDM Traffic Engineering Model


Virtual topology design
Routing and wavelength assignment
Introduction of Optical Networks
12
RWA constraints


Wavelength continuity constraint
Distinct wavelength constraint
Optical Network Design and Engineering
13
Wavelength Conversion


Wavelength converters translate wavelength fi to fk.
They may be used as components of the wavelength routing
nodes.
λ1
λ1
λ1
λ1
λ2
λ2
λ2
λ2
λ3
λ3
λ3
λ3
(a) No conversion
(b) Fixed conversion
λ1
λ1
λ1
λ1
λ2
λ2
λ2
λ2
λ3
λ3
λ3
λ3
(c) Limited conversion
(d) Full conversion
Optical Network Design and Engineering
14
RWA Problem

Static RWA





Topology Subproblem
Lightpath routing subproblem
Wavelength assignment subproblem
Traffic routing subproblem
Dynamic RWA


Route Computation
Wavelength Assignment
Optical Network Design and Engineering
15
Physical Topology Design

This step includes –





Sizing the links (no. of wavelength channel, capability of
each channel)
Sizing the OXCs
Placement of resources (Amplifiers, Converters, Splitters)
Dealing with link or OXC failures
Placement of converters [J. Iness, 1999]



Static RWA
Sparse location of wavelength converters
Sharing of converters (Nodal Design)
Limited-range wavelength conversion [R. Ramaswami and G.
H. Sasaki, 1998]
16
Virtual Topology Design


A solution to the static RWA problem consists of a set
of long-lived ligthpaths which create a logical topology
among the edges node.
It is not possible to implement fully connected virtual
topologies.


N(N-1) lightpaths
Objective



Static RWA
Minimize the maximum congestion level
Minimize the average weighted number of hops
Minimize the average packet delay
17
Wavelength Assignment
4
λ1
λ0
1
2
1
2
3
5
8
3
λ1
λ2 7
4
λ2
λ0
7
8
6
Graph-coloring problem
NP-complete
6
5
λ1
λ0
Sequential graph-coloring algorithms
Static RWA
18
Route Computation


Static algorithm and adaptive algorithm
Lightpath routing

Constraint algorithm




Adaptive unconstrained routing (AUR)
Hybrid routing


Fixed routing algorithm
Fixed alternative algorithm
Least to most congested
AUR has better improvement on call blocking
probability[A. Mokhtar and Murat Azizoğlu, 1998]
Dynamic RWA
19
Candidate Paths


The candidate paths for a request are considered in
increasing order of path length (or path cost).
Path length is defined as the sum of the weights
assigned to each physical link along the path.



K-shortest path



K-minimum hop paths
K-minimum distance paths
Pair-wise link disjoint
Dijkstra algorithm
Physical constraints (attenuation, dispersion et al.)

Constraint-based shortest path first algorithm [B. Davie, 2000]
Dynamic RWA
20
Wavelength Assignment

[H. Zanf et al., 2000]










Random Wavelength Assignment (R)
First-Fit (FF)
Single-fiber
Least-Used (LU)
Most-Used (MU)
Min-Product (MP)
Least-Loaded (LL)
Multi-fiber
MAX-SUM (MΣ)
Relative Capacity Loss (RCL)
Wavelength Reservation (Rsv)
Protecting Threshold (Thr)
Dynamic RWA
21
General Model of Virtual Topology Design

Mixed Integer Linear Programming






[B. Mukherjee et al., 1994]
[B. Mukherjee et al., 1996]
[R.Ramaswami and K. N. Sivarajan, 1996]
[R. Krishnaswamy and K. N. Sivarajan, 1998]
[R. Krishnaswamy and K. N. Sivarajan, 2001]
Objective
min( max )
General Model
22
Congestion

Congestion may be viewed as a function of the
various parameters of the network such as








the traffic matrix,
number of wavelengths the fiber can support,
resources at each node (number of transmitters and
receivers),
the hop lengths of the logical links,
the multiplicity restrictions on the logical topology,
the multiplicity restrictions on the physical topology,
symmetry/asymmetry restrictions,
the propagation delay.
General Model
23
Objective
min( max )




The motivation for choosing this objective is that the electronic
processing (switching speed) requirement is proportional to the
congestion.
If the switching speeds at the nodes are limited, then minimizing
congestion would be appropriate as it would enable the traffic
carried per wavelength to increase.
If there is heavy traffic between some source–destination pair,
then there is a logical link between them; this is a desirable
property.
This happens because of the objective function, i.e., if there is
heavy traffic between node i and node j then because of the
objective there would tend to be an edge in the logical topology.
General Model
24
Notations
s,d
source and destination of a packet, when used as
superscripts;
i,j originating and terminating node of a logical link
(lightpath);
l,m endpoints of a physical link;
k wavelength number, when used as a superscript.
General Model
25
Parameters
 Physical Topology:
GP (V , EP )
 Link Indicator: Plm
 Virtual Degree:
n
 Traffic Matrix:   [(sd ) ]
 Allowed Physical Hop:
General Model
H  [hij ]
26
Variables
 Lightpath Indicator: bij
(k )
c
 Lightpath wavelength Indicator: ij
 Link-lightpath Wavelength Indicator:
cij( k ) (l , m)
)
 Traffic intensity variables: (sd
ij
General Model
27
Constraints- Degree Constraints
b
ij
 l ,
i
 l ,
i
j
b
ji
j
bij  0,1 and

i  0,1,2,...N  1.
The above constraint ensures that the number of logical
links originating (out-degree) and terminating (in-degree)
at node is less than or equal to the number of transmitters
and receivers at that node.
General Model
28
Constraints- Traffic Constraints
Traffic routing constraints
ij  max ,
(i, j )
ij   (ijsd ) ,
(i, j )
sd
(ijsd )  bij ( sd ) ,
(i, j ), (s, d )
Flow Conservation

( sd )
ij
j

 (jisd )
j
( sd )
if s  i

  ( sd ) , if d  i,
0,
if s  i and d  i



( s, d )


The above first two equations ensure that the load on any logical link is
no greater than the maximum load, which is being minimized.
General Model
29
Constraints- Wavelength Continuity Constraints
Unique wavelength constraints:
W 1
(k )
c
 ij  bij , (i,j)
k 0

This ensures that if logical link exists, then only one
wavelength is assigned to it, among the possible choices.
cij( k ) (l , m)  cij( k ) , (i, j ), (l , m), k

This equation ensures that only those Cl(.km) (l , m) could be
(k )
nonzero for which the corresponding C (i, j ) variables
are nonzero.
General Model
30
Constraints- Wavelength Continuity Constraints
Wavelength clash constraints
(k )
c
 ij (l , m)  1, (l , m), k
ij
Conservation of wavelength constraints
bij , if m  j



(k )
(k )
C
(
l
,
m
)
P

C
(
m
,
l
)
P


b
,
if
m

i
,
 ij
  (i, j), m

ij
lm  ij
m ,l
k 0 l
k 0 l
0,
if m  i and m  j. 


W 1
F 1

Let logical link bij use wavelength k. Then by conservation
of wavelength constraints there is a path in the physical
topology from node i to node j with wavelength assigned to
it.
General Model
31
Constraints- Hop Bound Constraints
Hop bound Constraints
(k )
C
 ij (l, m)  hij , (i,j ),k
lm
General Model
32
Heuristics

Subproblems:






Topology Subproblem: bij
(k )
Lightpath routing subproblem: cij (l , m)
(k )
c
Wavelength assignment subproblem: ij
(sd )
Traffic routing subproblem: ij
Some of above subproblem are NP-hard.
Solving the subproblems in sequence and combining
the solutions may not result in the optimal solution for
the full integrated problem.
RWA Heuristics
33
Lower Bound on Congestion

Physical topology independent bound (p.43)
max  (1 / El ) ij  rH / El

ij
Minimum flow tree bound (MFT) (p.43)
max  rH min / El

Iterative LP-relaxation bound (p.43)



Aggregate formulation
Cutting Plane
Independent topologies bound (p.43)


Uniform traffic: 5% - 10% tighter than the bound obtained
from MFT
Nonuniform traffic: up to 50% higher than MFT bound
RWA Heuristics
34
Lower Bound on the Number of Wavelength

Physical topology degree bound (p.45)

Derived from the Simple consideration that he node with the
minimum physical degree.


 l 
 p

Physical topology link bound (p.46)

Assuming that each node sources lightpaths to exactly those
node it can be reach with the minimum number of hops.
  (1 / 2 E p ) li ( l )
i

Lagrangian relaxation bound

顏宏旭 (2001)
RWA Heuristics
35
Regular Topologies



Regular topologies such as hypercube have several
advantages as virtual topologies.
They are well understood, and results regarding
bounds and averages are comparatively easier to
derive.
Two subproblem


Node Mapping Subproblem
Path Mapping Subproblem
RWA Heuristics
36
Pre-specified Topologies





The topology in terms of a list of lightpaths with their
source and destination nodes is supposed to be given
for each instance of problem.
The lightpath routing and wavelength assignment
subproblems can be viewd as having goals defined
purely in terms of lightpaths.
Static Lightpath Establishment problem [I. Chlamtac,
1995]
Maximize wavelength utilization [C. Chen, 1995]
Randomized rounding and graph coloring [D.
Banerjee 1996]
RWA Heuristics
37
Arbitrary Topologies

[R. Ramaswami, 1996]






HLDA (Heuristic topology design algorithm)
MLDA (Minimum-delay logical topology design algorithm)
TILDA (Traffic Independent logical topology design algorithm)
LPLDA (LP-relaxation logical topology design algorithm)
RLDA (Random logical topology design algorithm)
[D. Banerjee, 2000]


Maximizing Single-Hop Traffic
Maximizing Multihop Traffic
RWA Heuristics
38
Optical Multicasting

Multicasting at IP layer
Optical Multicasting
39
Optical Multicasting

Multicasting by Lightpaths
Optical Multicasting
40
Optical Multicasting

Multicasting at WDM Layer (Light Tree Architecture)
Optical Multicasting
41
Light Tree Architecture

Application




Optical multicast
Enhanced virtual connectivity
Traffic grooming
Steiner Tree Problem



Shortest path-based heuristic (SPH)
Spanning tree-based heuristic (STH)
Metaheuristics
Optical Multicasting
42
WDM Multicast Mode

[Y. Yang et al., 2000]



Multicast with same wavelength
(MSW)
Multicast with same destination
wavelength model (MSDW)
Multicast with any wavelength
model (MAW)
Optical Multicasting
43
MC-RWA



MC-RWA bears many similarities to the RWA problem.
The tight coupling routing and wavelength
assignment remains and becomes stronger.
Physical topology design problem



Resources placement
[M. Ali and J. Deogun, 2000]
Virtual topology design problem



Minimize call blocking probability
Minimize the number of transceiver needed
Minimize average packet hop distance
Optical Multicasting
44
MC-RWA Researches (1/2)

[L. H. Sahasrabuddhe, 1999]



An optimum light tree-based virtual topology has a lower
value of average packet hop distance than that of an
optimum lightpath-based virtual topology
An optimum light tree-based virtual topology requires fewer
opto-electronic components
Light forest [X. Zhang et al., 2000]




Reroute-to-Source
Reroute-to-Any
Member-First
Member-Only
Optical Multicasting
45
MC-RWA Researches (2/2)

[Y. Sun et al., 2001]



Optical Multicasting
The USCH1 algorithm gives
the worst network throughput
The wavelength continuity
constraint limits the
performance of the MSCH1
algorithm
The best approach is the
MSCH2 if the wavelength
converters are not available
46
Super-Lightpath RWA

WDM + OTDM
Optical Multicasting
47
Tree Shared Multicast

[D. N. Yang and W. Liao, 2003]




A light tree can carry data of multiple multicast streams, and
data of a multicast stream may traverse multiple light-trees to
reach a receiver.
Multicast routing and wavelength assignment of light-trees
Design of light-tree based logical topology for multicast
streams
[郭至鈞，民國92]




Multicasting group aggregation and MC-RWA
Source-based tree aggregation
Maximize the total revenue
Lagrangian relaxation
Optical Multicasting
48
Tree-Sharing Strategies


Given the set Mi at edge router i, we consider a strategy to
decompose Mi into a number of MSCs (Multicast Sharing
Class)
Perfect Overlap (PO), Super Overlap (SO), and Arbitrary
Overlap (AO)
Optical Multicasting
49
Optical Waveband Switch



WBS has attracted attention for its practical
importance in reducing port count, associates control
complexity, and cost of photonic cross-connect.
In WBS networks, several wavelengths are grouped
together as a band and switch as single entity using
single port.
MG-OXC not only switch traffic at multiple
granularities such as fiber, band, and wavelength, but
also add and drop traffic at multiple granularities .
Multi-granularity Optical Networks
50
Multilayer MG-OXC
1
1
Fiber Cross-connect
(FXC)
n
BTF
Mux
Bdrop
FXC
layer
FTB
Demux
Waveband Crossconnect
(BXC)
BTW
Demux
Fadd
n
WTB
Mux
Wavelength Crossconnect
(WXC)
Wdrop
Wadd
Badd
BXC
layer
WXC
layer
Fdrop
TX/RX block
Multi-granularity Optical Networks
51
Single Layer MG-OXC
1
1
FXC
2
2
BXC
n
n
WXC
m
Fadd
Badd
Wdrop
Wadd
Bdrop
Fdrop
TX/RX block
Multi-granularity Optical Networks
52
Lightpath Grouping Strategy

End-to-end grouping:


One-end grouping:


Grouping the traffic (lightpaths) with same source-destination
only
Grouping the traffic between the same source (or destination)
nodes and different destination (or source) nodes
Subpath grouping:

Grouping traffic with common subpath (from any source to
any destination)
Multi-granularity Optical Networks
53
WRN vs. WBS

WRN



WBS


Minimum the number of wavelengths
Minimum wavelength hops
Minimum the number of ports
Waveband conversion
λ0
λ0
λ1
λ1
λ2
λ2
λ3
λ3
b0
b1
Multi-granularity Optical Networks
λ0
λ0
λ1
λ1
λ2
λ2
λ3
λ3
b0
b1
54
WBS Failure Recovery

Band Merging
λ0
λ1
λ2
λ3
λ4
λ5

b0
b1
Band Swapping
λ0
λ1
λ2
λ3
λ4
λ5
b0
b1
Multi-granularity Optical Networks
55
Hierarchical Routing Model



Network node architecture
Sequence of routing and waveband aggregation
Route Computation
Integrated routing
Separate routing
H
Online
routing
Offline
routing
Multi-granularity Optical Networks
us
o
e
e n rk
g
o wo
om net
s
ou
e
e n rk
g
o o
er etw
t
He n
56
Integrated routing
Separate routing
Researches of M. Lee et al.
Online
routing





Offline
routing
s
ou
ne k
e
r
og o
m etw
Ho n
us
eo
n
ge rk
ro o
te etw
e
n
H
Multi-Layer MG-OXC
The waveband is formed by grouping lights with the same
destination in a network
ILP formulation
Maximize the reduction gain of crossconnect size with the
minimum number of wavelengths
Results



The introduction of waveband leads to a very large reduction in
crossconnect requirements for large-scale networks.
A large reduction of crossconnect requirements can still be
expected even at nonoptimal wavelength granularity.
The reduction depends on network topology, traffic demand and
traffic pattern.
Multi-granularity Optical Networks
57
Integrated routing
Separate routing
Researches of Y.Suemura et al.
Online
routing


Propose and analyze two heuristic routing and
aggregation algorithms (online and offline) to be used for
homogeneous networks in separate routing framework.
Minimum the routing cost



Offline
routing
s
ou
ne k
e
r
og o
m etw
Ho n
us
eo
n
ge rk
ro o
te etw
e
n
H
Assume that all the ports (OEO and optical ones) have the same
cost.
The cost of routing is the total number of used ports.
The simulations demonstrate a significant cost reduction by
employing hierarchical routing (from 33% in online algorithm to
almost 60% in offline one)
Multi-granularity Optical Networks
58
Integrated routing
Separate routing
Researches of X. Cao et al.
Online
routing



This research show that WBS is different from traditional
wavelength, and thus techniques developed for wavelengthrouted networks cannot be directly applied to effectively WBSrelated problem.
The objective is to route lightpaths and assign appropriate
wavelength to them so as the minimum the total number of
prots required by the MG-OXCs.
Static offline problem (Network Planning)


Balanced Path Routing with Heavy Traffic (BPHT)
Dynamic real-time problem (Network Servicing)


Offline
routing
s
ou
ne k
e
r
og o
m etw
Ho n
us
eo
n
ge rk
ro o
te etw
e
n
H
Maximum Overlap Ratio (MOR)
Results


BPHT: 50% fewer total ports than using ordinary OXCs
MOR: 35 % saving in the number of ports
Multi-granularity Optical Networks
59
Integrated routing
Separate routing
Researches of P. Ho et al.
Online
routing

Dynamic tunnel allocation (DTA)


Use fixed alternative routing with k-shortest paths to inspect
networks along each alternative path for dynamically setting up
lightpaths.
Capacity-balanced static tunnel allocation (CB-STA)


Offline
routing
s
ou
ne k
e
r
og o
m etw
Ho n
us
eo
n
ge rk
ro o
te etw
e
n
H
Fiber and waveband tunnels are allocated into networks at the
planning stage according to weighted network link-state.
Simulation Results


DTA is outperformed by CB-STA in the same network environment
duo to a well-disciplined approach for allocating tunnels with CBSTA.
The mix of the two approaches yields the best performance given
the same network environment apparatus.
Multi-granularity Optical Networks
60
Future Research Topics


New optical component application
Optical Multicasting




WBS







QoS Multicasting
Tree Aggregation Problem
Call Admission Control
Converter and Splitter Placement
Waveband Multicasting
Heterogeneous WBS Network
Survivability
Optical Packet Switch and Optical Burst Switch
Passive Optical Network- EPON and GPON
After the Optical Bubble?
61
Q&A