Transcript ceg790

Algorithms for Allocating Wavelength
Converters in All-Optical Networks
Authors: Goaxi Xiao and Yiu-Wing Leung
Presented by: Douglas L. Potts
CEG 790 Summer 2003
From IEEE/ACM Transactions on Networking, Vol. , No. 4, Aug. 1999
Authors: Goaxi Xiao and Yiu-Wing Leung
Overview:
• Wavelength Converters: background
• Converter Placement: a study, a
algorithm proposal
• Simulations to determine worth
• Conclusions
Wavelength Converters:
background
• What are they?
• Distinction in terminology
• Why?
Wavelength Converters: background –
What are they?
• In Wavelength Division Multiplexing (WDM) divides
bandwidth across multiple wavelength channels
• On multiple hop lightpaths, it is difficult to reserve a single
wavelength for all hops (Wavelength Continuity Constraint)
• For high network load, need a way to get around the
Wavelength Continuity Constraint
• Mechanism for converting one fiber optic signal’s light
wavelength to another light wavelength
Wavelength Converters: background –
Distinction in Terminology
• Full Range Wavelength Converter (FWC)
– Converts incoming wavelength to any outgoing
wavelength
• Limited Range Wavelength Converter
– Converts incoming wavelength to a subset of outgoing
wavelengths
Wavelength Converters: background –
Distinction in Terminology
• Complete Wavelength Conversion
– When number of FWC’s in a node is equal to total number
of outgoing wavelength channels of this node
• Partial Wavelength Conversion
– As Complete Wavelength Conversion has a high cost
using fewer FWC’s per node.
Wavelength Converters: background –
Why use them?
• To resolve wavelength conflicts on a
particular hop…
• Which reduces blocking probability.
Wavelength Converters: background –
Why not?
• Costly (in terms of $ cost, but also in time
delay for conversion and signal
degradation)
• Introduces complexity in RouteWavelength Allocation (RWA)
Converter Placement – converters for all
• Previous studies looked at putting a FWC
at each node
• Results were that blocking probability is
drastically reduced, but at great cost (and
an unrealistic assumption)
Converter Placement – example node
Converter Placement – Choosy allocation
• Paper looks at a method for optimizing FWC
placement to reduce total number of
wavelength converters
• Goals for allocation
– Reduce overall blocking probability (better mean
quality of service)
– Maximum of the blocking probabilities experienced at
all the source nodes (better fairness)
Converter Placement – Choosy allocation
• Want to minimize blocking probability
• Blocking probability is available via:
– Analysis
– Simulation
Converter Placement – Choosy allocation
• Blocking probability by analysis is only
available by making some simplifying
assumptions
– specific traffic models or
– specific routing and wavelength assignment
methods
• Therefore simulation approach chosen
Converter Placement – Choosy allocation
• Main Idea – Simulate a complete wavelength conversion
network and analyze the utilization matrix of the node’s
FWC’s, optimize converter allocation based on this
utilization matrix
• Optimized allocation does alter utilization matrix for the
network, but authors claim that the estimated utilization (i.e.
that based on complete conversion) is good because for a
“well-engineered network” the traffic load handled by each
node should not approach or exceed its capacity.
Converter Placement – Choosy allocation
• It is because of the only slight change to
the utilization matrix when fewer FWC’s
are used that network performance is
maintained.
Converter Placement – RWA Algorithm
• Previous work based on two extremes of
wavelength conversion
– No Wavelength Conversion
– Complete Wavelength Conversion
• Authors needed to come up with a new
allocation algorithm
Converter Placement – RWA Algorithm
• Critical problem that algorithm needs to
solve: when a certain no. of FWC’s have
been allocated to each node, how should
the tuning nodes (i.e. nodes with
wavelength converters) be selected
Converter Placement – RWA Algorithm
• Main ideas for solving the problem:
– Once a request arrives, select the set of tuning
nodes such that required number of FWC’s is
minimized
– When more than one choice, select the one that
maximizes the min. no. of free FWC’s in each tuning
node of src. to dest. path
– When more than one choice, select one that has
max. no. of FWC’s installed on the critical node
Converter Placement – RWA Algorithm
•
Resulting algorithm:
1.
Check if there is at least one clear channel on source-to-destination
path. If one exists, assign this clear channel to the transmission
request; if there is more than one channel, select one of them on a
first-fit basis; if there is none, go to step 2.
2.
If there is at least one free wavelength channel (at any wavelength) on
every hop of the source-to-destination path, execute:
1.
Construct a directed graph in a manner similar to that in the Conflict
Resolution Algorithm. For each free wavelength channel on every
hop, the weight of the corresponding edge is M. On every
intermediate node l, the weight of the edge between the node vi(λi, l)
and node vo(λo, l) is:
c(λi, λo, l)={ M + S, if λi ≠ λo or 0, if λi = λo}
where:
S={M/(Nt(l) – Na(l)) + (1 – Na(l)/Nt(l)), if Nt(l) > Na(l) or ∞, if Nt(l) = Na(l)}
Converter Placement – RWA Algorithm
Converter Placement – RWA Algorithm
•
Resulting algorithm (cont.):
Apply in the Conflict Resolution Algorithm to find the shortest path from
the source to the destination
2.
Determine the set of tuning nodes and increment Na(l) of each tuning
node by 1.
Otherwise, the transmission request is blocked.
Numerical Results
• Simulations used to evaluate performance of the proposed
allocation method, with the steps:
– Conduct simulation for any given network with complete
wavelength conversion and any given traffic load and pattern.
During simulation, record utilization matrix.
– Based on recorded utilization matrix, execute Optimization
Algorithm to optimize allocation of FWC’s.
– Conduct another simulation for the same network with the
FWC allocation being that determined by the Optimization
Algorithm. During simulation, execute the RWA Algorithm to
perform routing and wavelength assignment and record
blocking probability.
Numerical Results
• “Extensive” Simulations conducted on regular and irregular
networks, considering both uniform and non-uniform traffic
– Regular network: 11x11 torus mesh network with 121 nodes
– Irregular network: generated randomly, starting from a 10x10
mesh network with 100 nodes and 180 bi-directional links
• Randomly delete 20 links, while ensuring that resulting network
is not disconnected
• Randomly add 30 links to the network: for the j1th node on the
i1th row and j2th node on the i2th row, define the distance as:
d(i1,j1),(i2,j2) =sqrt((i1-i2)2+(j1+j2)2)
Simulations – Results
• Fig. 7a, 7b, 8a, and
8b
Simulations – Results
• Fig. 9a, 9b, 10a, and
10b
Simulations – Results
• Fig 11a, 11b, 12a,
and 12b
Summary:
• Wavelength Converters: why and why
not
• Converter Placement: all nodes, select
nodes
• Simulations indicate Proposed allocation
matching Complete wavelength
conversion within a small margin
Conclusions
•
Utilizing Wavelength Converters in a Optical WDM Network
drastically reduces blocking probability
•
Wavelength Converters are expensive, so ideal situation is to use
small number of converters while maintaining performance
•
By using a simulation-based optimization approach, it is possible
to collect utilization statistics, upon which converter allocation is
based
•
It is possible to use the optimized converter allocation to
significantly reduce the number of converters required, and
achieve blocking probabilities which are roughly those of
Complete Wavelength Conversion