Transcript 投影片 1 - Mohammad Reza Faghani

In the name of God, The Beneficent, The Merciful
A Review of Routing and
Wavelength Assignment
Approaches for
Wavelength-Routed
Optical WDM Networks
Mohammad Reza Faghani
Outline






Introduction
Static Lightpath Establishment (SLE)
problem
Routing
Wavelength Assignment
Simulation Results
Wavelength assignment in distributed
fashion.
Introduction
Wavelength Routed Network

Definition
 A wavelength routed network consists of WXC
(wavelength crossconnect) interconnected by pointpoint fiber links in any arbitrary topology.


A lightpath is an all-optical communication path
between two nodes, established by allocating the
same wavelength throughout the route of the
transmitted data.
Issues in wavelength routed networks
 Route and wavelength assignment
 Centralized Versus Distributed Control
Wavelength-continuity constraint
H
I
G
J
K
F
B
A
1
3
SONET
O
1
2
E
2
1
D
IP
1
IP
C
N
L
M
SONET
OXC allows the efficient network management of wavelengths at the optical layer. The variety of functions that it provides are signal
monitoring, restoration, provisioning and grooming.
OXC
Wavelength Routed Networks


Given a set of connections, the problem of setting up
lightpaths by routing and assigning a wavelength to each
connection is called the Routing and WavelengthAssignment (RWA) problem.
Minimize the number of wavelength needed for certain set
of connection or Alternatively, maximize the number of
connection for a given fixed number of wavelengths.
Connection Requests

Static Lightpath Establishment (SLE) problem


Static : The set of connections is known in advance
Dynamic Lightpath Establishment (DLE) problem


Incremental : Connection requests arrive sequentially,a
lightpath is established for each connection, and a
lightpath remains in the network indefinitely
Dynamic : A lightpath is set up for each connection
request as it arrives, and the lightpath is released after
some finite amount of time
Static Lightpath Establishment (SLE)
problem
Static Lightpath Establishment

Characteristic



Lightpath requests are known in advance
RWA operations are performed off-line
Objective


Min (# of flow each link)
Max (# of connections that can be established)
Static Lightpath Establishment



The SLE problem can be formulated as a linear
program or ILP while DLE employs heuristic
methods.
SLE can be partitioned into two subproblems
 Routing
 Wavelength assignment
Each subproblem can be solved separately
ILP of SLE with wavelength-continuity
constraint

integer linear program (ILP) objective function is
to minimize the flow in each link, which, in turn,
corresponds to minimizing the number of
lightpaths passing through a particular link.
ILP of SLE with wavelength-continuity
constraint
Number of
minimize: F max such t hat
F max 
sdw
F
 ij  ij
connection
requests.
s ,d , w
Number of
connection
request on
any s,d,w
sdw
sdw
F

F
 ij  jk
i

k
sdw
  sd
w
Fijsdw  0 , 1
sdw
F
 ij  1
s,d
 sdw if s  j

  sdw if d  j
 0 ot herwise

Number of
connection
needed.
ILP of SLE with wavelength-continuity
constraint



This approach may be used to obtain the minimum number
of wavelengths required for a given set of connection
requests by performing a search on the minimum number
of wavelengths in the network.
We can apply the ILP to see if a solution can be found.This
procedure is iterated until the minimum number of
wavelengths is found.
the next ILP is used for maximizing the number of
established connections for a fixed number of wavelengths
ILP of SLE with wavelength-continuity
constraint (cont.)
N sd
Maximize: CO (  , q)   mi
i 1
mi  0,
cij  0,1
integer,i  1,2,..., N sd
i  1,2,...,P, j  1,2,...,W
C T B  1W L
m  1W C T A
mi  qi  ,
i  1,2,..., N sd
ILP of SLE with wavelength conversion


the wavelength-continuity constraint can be eliminated
if we use wavelength converters to convert one wavelength
on into another at an intermediate node before forwarding
it to the next link.
wavelength conversion may improve the efficiency by
resolving the wavelength conflicts.

This method can also be formulated using ILP.
ILP of SLE with wavelength conversion
minimize: F max such that
F max   F
sd
ij
 ij
s ,d
sd
sd
F

F
 ij  jk
i
k
  sd if s  j

  sd if d  j
 0 otherwise

ILP of SLE with wavelength conversion



full wavelength conversion in the network may
not be preferred and may not even be necessary
due to high costs and limited performance gains.
a subset of the nodes may allows wavelength
conversion, or a node employs converters that can
only convert to a limited range of wavelenghts.
Some Problem may arise due to limited
conversions.
Limited wavelength conversion

Sparse location of wavelength converters in
network



Sharing of converters




Place few converters in an arbitrary network
Where Optimally to place ?
Switch architectures that allow sharing of converters among
the various signals.
Performance Saturates as no. of converters increases.
Routing Dependent
Limited-range wavelength conversion


Range is limited to k
i  max(i-k,1) through min(i+k,w)
Routing
Routing

Both SLE and DLE use three basic approches
for routing.
 Fixed Routing
 Fixed Alternate Routing
 Adaptive Routing

Fixed Routing is Simplest, Adaptive yields the Best
performance. Alternate offers Tradeoff.
Fixed Routing


Always choose the same fixed route for a
given source-destination pair
Ex: fixed shortest-path routing



Dijkstra’s algorithm
Bellman-Ford algorithm
Disadvantage


Hign blocking probability in the dynamic case
Unable to handle fault situation (altPath,Dyn)
Fixed Routing

Fixed shortest path route from node 0 to 2.
Fixed-Alternate Routing




Each node is required to maintain a routing table
that contains an ordered list of a number of
fixed routes to each destination node
A primary route between s-d is defined as the
first route
An alternative route doesn’t share any links with
the first route (link disjoint)
Advantage


Provide some degree of fault tolerance
Reduce the blocking probability compared to fixed
routing
Fixed-Alternate Routing

Primary (Solid) and Alternate (Dashed) routes form node 0
to 2
Adaptive Routing


The route from a source node to a
destination node is chosen dynamically,
depending on the network state
Ex:


Shortest-cost-path routing
Least-congestion-path routing


Congestion is measured by available wavelengths
Advantage

Lower connection blocking than fixed and
fixed-alternate routing
Adaptive Routing

shortest-cost-path routing,




well-suited for use in wavelength-converted networks.
Each unused link has a cost of 1 unit, each used
link has a cost of ∞, and each wavelengthconverter link has a cost of c units.
If wavelength conversion is not available, c = ∞.
When a connection arrives, the shortest-cost
path between the source node and the
destination node is determined.
Adaptive Routing

Adaptive shortest cost path route from node 0 to 2.
Consider fault-tolerant

Protection





Set up two link/node-disjoint lightpaths
Primary lightpath transmit data
Backup lightpath must be reserved
Fast but need reserve resource
Restoration


The backup path is determined dynamically
after the failure has occurred
Slow but doesn't need reserve resource
Wavelength Assignment
Static Wavelength-Assignment

Minimizing the number of wavelengths
used in wavelength-continuity constraint,
reduced to the graph coloring problem




Construct an auxiliary graph G(V,E)
Color the nodes of the graph G
Largest First
Smallest Last
Static Wavelength-Assignment (cont.)
Auxiliary Graph.
Network With 8 routed Lightpath
Largest First
Smallest Last
Dynamic or Incremental Wavelength
Assignment Heuristics


For the case in which lightpaths arrive one at a
time (either incremental or dynamic traffic),
heuristic methods must be used to assign
wavelengths to lightpaths.
In dynamic problem, we assume that the number
of wavelengths is fixed (as in practical
situations), and we attempt to minimize
connection blocking.
Dynamic or Incremental Wavelength
Assignment Heuristics











Random Wavelength Assignment (R)
First-Fit (FF)
Least-Used (LU)/SPREAD
Most-Used (MU)/PACK
Min-Product (MP)
Least-Loaded (LL)
MAX-SUM (MΣ)
Relative Capacity Loss (RCL)
Distributed Relative Capacity Loss (DRCL)
Wavelength Reservation (Rsv)
Protecting Threshold (Thr)
Wavelength-usage pattern

Consider P1(2,4) and three potential paths that
share common link P2(1,5) P3(3,6) P4(0,3).
Random Wavelength Assignment (R)



First searches the space of wavelengths to
determine the set of all wavelengths that
are available on the required route
Among the available wavelengths, one is
chosen randomly
Advantage

NO communication overhead
First-Fit (FF)



When searching for available wavelengths,
a lower-numbered wavelength is considered
before a higher-numbered wavelength
The first available wavelength is then
selected
Advantage


Computation cost is lower
No communication overhead
FF example


λ0 will be assigned
λ0 will also be assigned MP and LL as single fiber.
Least-Used (LU)/SPREAD


LU selects the wavelength that is the least
used in the network, thereby attempting
to balance the load among all the
wavelengths
Disadvantage

Additional communication overhead
LU example



λ0 ,λ1 ,λ3 are each used two links
λ2 is used only one link
So LU will choose λ2
Most-Used (MU)/PACK



MU selects the most-used wavelength in
the network
Packing connections into fewer
wavelengths
Advantage


Overhead is similar to LU but MU outperforms
LU and FF
Outperforms LU (fewer wavelength used).
MU example



λ0 ,λ1 ,λ3 are each used two links
λ2 is used only one link
So MU will choose one of λ0 ,λ1 ,λ3 with equal
probability.
Min-Product (MP)



MP is used in multi-fiber network
In a Single Fiber , MP becomes FF.
The goal of MP is to pack wavelengths into fibers
min
D


lj
l ( p )


Dlj indicates the number of assigned fibers on link l and
wavelength j. MP does it for all j.
π(p): Set of links comprising path p.
MP example
0
1
2
3
4
5
λ1=2
λ1=3
λ1=1
λ1=3
λ1=5
λ2=3
λ2=2
λ2=4
λ2=1
λ2=2
λ3=1
λ3=2
λ3=1
λ3=2
λ3=1
λ1 : 2*3*1*3*5=90
λ2 : 3*2*4*1*2=48
λ3 : 1*2*1*2*1=4
So choose λ3 for path 0 to 5.
Least-Loaded (LL)


LL is also used in multi-fiber network
To select the wavelength that has the largest
residual capacity on the most-loaded link along
route p
max min ( M l  Dlj )
jSp l ( p )


Ml: Number of fibers on link l.
Sp: Set of available wavelengths along the selected paths p.
LL example
0
1
2
3
4
5
Assume 7 fibers per link
λ1=2(5)
λ1=3(4)
λ1=1(6)
λ1=3(4)
λ1=5(2)
λ2=3(4)
λ2=2(5)
λ2=4(3)
λ2=1(6)
λ2=2(5)
λ3=1(6)
λ3=2(5)
λ3=1(6)
λ3=2(5)
λ3=1(6)
Set up lightpath from 0 to 2
Choose λ3 Max(min(residual capacity))=5
MAX-SUM (MΣ)


MΣ considers all possible paths in the network
and attempts to maximize the remaining path
capacities after lightpath establishment.
Applied to both single and multi-fiber Networks
r ( , l , j )  M l  D( ) lj
r ( , p, j )  min r ( , l , j )
l ( p )
W
R( , p)   min r ( , l , j )
j 1
l ( p )
choosethe wavelength j thatmaximize R( ' ( j ), p )
pP
MΣexample
What about choosing λ0 ?
λ2 has the
highest
capacity loss
Choosing λ0 will
block path P4
Relative Capacity Loss (RCL)


RCL attempts to improve on MΣ by taking into
consideration the number of available alternate
wavelengths for each potential future connection.
MΣ
min  (r ( ' , p, j )  r ( ' ( j ), p))
pP

RCL
min  ( R( ' , p, j )  r ( ' ( j ), p)) / r ( , p, j )
pP
RCL example
Choosing the Wavelength with smallest
Total RCL.
Distributed Relative Capacity Loss (DRCL)



MΣ and RCL are difficult and expensive to
implement in a distributed environment.
MΣ and RCL both require fixed routing, which
makes it difficult to improve network
performance.
Two Problem of implementation.


how is information of network state exchanged?
how can we reduce the amount of calculation upon
receiving a connection request?
Distributed Relative Capacity Loss (DRCL)

Speed up the wavelength-assignment
procedure




each node stores information on the capacity
loss on each wavelength.
only table lookup. (w,d,rcl(w,d))
small amount of calculation are required upon
the arrival of a connection request.
Routing is implemented using the Bellman-Ford
(each node exchange table with its neighboring
nodes and updates its table).
Distributed Relative Capacity Loss (DRCL)
(cont.)


DRCL considers all of the paths from the
source node of the arriving connection
request to every other node ,excluding the
destination node of the arriving connection
request.
DRCL choose the wavelength that minimize
the sum of rcl(w,d) over all possible
destination d.
Distributed Relative Capacity Loss (DRCL)
(cont.)


If there is no path from node s to node d on
wavelength w, then rcl(w,d) = 0
If there is a direct link from node s to node d,
and the path from s to d on wavelength w is
routed through this link, then rcl(w,d) = 1/k,
where k is the number of available wavelengths on
this link through which s can reach.
DRCL example
We have to Calculate RCL for (2,0)
(2,1),(2,3),(2,5) and (2,6).
(2,0) can only be established on λ0.
(2,1) can establish on three
wavelengths giving the RCL value of 1/3
and so on.
These entry are calculated just using
the RCL table of Adjacent nodes.
Wavelength Reservation (Rsv)
λ1 is always reserved on link (1,2) for traffics of node 0 to node 3.
So node 1 cannot connect to node 2 using λ1.
Wavelength Reservation (Rsv)



A given wavelength on a specified link is
reserved for a traffic stream, usually a
multihop stream
To protect only the connections that
traverse multihop connections.
Must be combined with other wavelengthassignment scheme.
Simulation Results
Simulation Results
Comparison of Random, FF, LU,MU, Max-Sum, and
RCL for single-fiber network with 16 wavelengths.
Simulation Results
Comparison of Random, FF, LU,MU, LL, Max-Sum,
and RCL for two-fiber network with 8 wavelengths.
Simulation Results


In the single-fiber case, MU is found to achieve
the best performance under low load while MΣ
and RCL work well when the load is high ( ≥ 50
Erlangs), with the other approaches not that far
behind.
When the number of fibers per link is two (M =
2), MU, MP, and RCL perform well under low
load, while LL and MΣ offer better performance
under a higher load.
Simulation Results
Comparison of Random, FF, LU, MU, MP, LL,Max-Sum, and RCL for
four-fiber network with 4 wavelengths. LL performs better.
Simulation Results
Comparison of DRCL, FF with adaptive routing, RCL
(which can only be implemented with fixed routing), and FF with
fixed routing.
Simulation Results


Note that RCL cannot be implemented with
adaptive routing.
DRCL slightly outperforms FF (with
adaptive routing) in the reasonable region,
which is 45-65 Erlangs in this network, and
they both perform better than RCL and FF
with fixed routing.
Simulation Results


Overall, it appears that the routing scheme has
much more of an impact on the performance of
the system than the wavelength-assignment scheme.
It is important to first decide on a good routing
mechanism, and then to choose a wavelengthassignment scheme that can easily be implemented
in conjunction with the selected routing mechanism.
References

[1] H. Zang et al A Review of Routing and Wavelength Assignment
Approaches for Wavelength Routed Optical WDM Networks,
Optical Networking Magazine, IEEE Jan 2000
Thanks to Audiences