JOURNAL
Week 1
I have developed
network simulation program using Language C to assign wavelength for
wavelength-routed optical networks (WRONs) based on distributed algorithm
using dedicated path protections.
(1) Improvement on locked channel.
Supposed there are 64 channels in one edge, and it locks 4 channels
while one connection passing this edge. If we choose 4 available channels
to lock from the same point, from channel 0 to channel 63 in order,
it often happens that different connections use the same locked channels
passing the same edge. Then failure occurs. After discussion with Dr.
Jaekel, I improved the program using a random number as the start point
to find the available channels to lock, instead of from channel 0 in
order, to improve the channel utilization. The number of successful
connection has increased by 80%.
(2) Improvement by adding waiting time.
Without waiting time, when a connection passes an edge which is passed
by another connection with the same locked channel, it will be failed.
After adding a waiting time, for this situation, that connection gets
one more chance. After 5 time slots, it will check again whether those
locked channels are released. If yes, then this connection can pass
this edge.
Do some experiments using different network topology, channel number,
and locked channel number. Compare the results with those results based
on centralized algorithm.
I also designed my
individual web site for CDMP.
Top
Week 2
I have developed
network simulation program using C to assign
wavelength for wavelength-routed optical networks (WRONs) based on distributed
algorithm using shared path protections. After discussion with Dr. Jaekel,
I did some improvement,
(1) Improvement by adding a fixed probability number.
Creating new connections at each time slot is too frequent. The number
of failure connection will increase because there is no enough available
channel for locking. So, we generate a random number between 0.0 to
1.0 first. Network creates a new connection only when this random number
is less than a fixed probability.
(2) Different connections share the same locked channels.
For Shared Path Protection, two or more backup lightpaths can share
a wavelength channel if their corresponding primary lightpaths are link-disjoint,
or Level 0 primary lightpath can share a wavelength channel with
one or more backup lightpaths.
So I modified the program to allow different connections to share the
same locked channels if they meet the above constrains.
Do some experiments using
different network topology, channel number, locked channel number, probability,
and waiting time. Compare the results with those results based on centralized
algorithm.
Problems I met:
I feel it is very difficult to trace or debug a program if there are
too much random numbers generated.
Top
Week
3
Dr. Jaekel suggested that I do some improvement
for assigning wavelength with wavelength conversion, or
a lightpath may be assigned the different channels at the intermediate
nodes, in the meeting on Monday.
In
the previous projects, I always solved routing and wavelength assignment
problems with wavelength continuity constraint, or
a lightpath should be assigned the same channel on each fiber if there
is not any wavelength converter at the intermediate nodes.
I developed two C
programs to assign wavelength
for WRONs with wavelength conversion, using both dedicated and shared
path protection. One is based on the centralized algorithm, another
is based on the distributed algorithm.
Comparing with the results which used wavelength
continuity constraint before, there is some improvement for shared path
protection, though it needs more average
solution time than before. For dedicated
path protection, there is not any improvement.
Top
Week
4
I studied the draft
of Dr. Jaekel's paper, "Distributed dynamic lightpath allocation
in survivable WDM Network", and Suqin Zhong's thesis, " Priority
Based Dynamic Lightpath Allocation in WDM Network".
I started to learn
how to use CPLEX software tool to solve the Linear Programming (LP)
problems. After Reading
"ILOG CPLEX 9.0 Getting Started", I
had a meeting with Cindy, a graduate student of U. of Windsor, on Friday.
Thanks to her help, I got some basic idea about how to transfer mathematical
formulation to LP format file which CPLEX can accept using Language
C.
Top
Week
5
I studied the examples and callable library
CPLEX by reading "ILOG CPLEX User Manual" and "ILOG CPLEX
Reference of Callable Library", and did some tests to be familial
with CPLEX.
I did some research on
how to assign wavelength for
WRONs, using dedicated
and shared path protection, with wavelength conversion and without wavelength
conversion, by the tool of CPLEX.
Top
Week
6
I studied Dr. Jaekel's paper, " Dynamic
Lightpath Allocation in Survivable Multifiber WDM Networks".
There are two sets of formulations in the paper. My job
is to to implement these two formulations using C with the help of CPLEX.
I had some meetings with Dr.Jaekel
and she gave me lots of help about how to understand fully these formulations.
First, I transferred formulations of LP problems, including the Objective
functions, constraints, and bounds, into LP file which is accepted by
CPLEX. Then I called CPLEX callable library functions, read this LP
file, optimized the mixed-integer linear problem automatically, and
updated a dynamic WDM network.
This week I focused on implementing the dedicated path protection for
these two sets of formulations. After coding, I tested them using different
channel number and fiber number, for both 14-node NSFNET and 20-node
ARPANET.
Top
Week
7
This week I focused on implementing the shared
path protection for formulation 1 and formulation 2. I met some problems
when I coded programs for formulation 2. Thanks to Dr. Jaekel's help,
I made some improvement on this program, though the result is still
not very good. I need to spend much time on doing more tracing and improvement
work on it.
Top
Week
8
I traced optimal
solution for formulation 1 and formulation
2, and checked LP files of failure paths. Dr. Jaekel had improved the
constraints of formulation 2. Then I modified my programs based on her
improvement. I tested them
using different channel number and fiber number, for 14-node NSFNET
and 20-node ARPANET, and compared the experiment results.
The next goal is
to develop and test heuristics for RWA in optical network, and compare
the performance with the optimal solutions.
I implemented dynamic lightpath allocation in survivable multifiber
WDM networks using dedicated path protection for single level service
(100% level 2) this week.
Top
Week
9
I plotted some MS
Excel charts of experiment results, using
ILP optimal method for formulation 1 and formulation 2, and the heuristic
method, for 14-node network.
When tracing the
results, we found CPLEX did not choose the shortest path for the new
primary path sometimes. So Dr. Jaekel modified objective function to
force CPLEX to choose the shortest path for the new primary path if
possible. Then I modified programs and did some experiments.
Top
Week
10
I implemented dynamic
lightpath allocation in survivable multifiber WDM networks using shared
path protection for single level service (100% level 2) this week.
I also read "Computer
networks and internets" written by Douglas E. Comer. It helps me
understand a few new technologies and new concepts about computer networks.
Top
Week
11
In the third week, I
had developed two C programs to
assign wavelength for WRONs with wavelength conversion, using both dedicated
and shared path protection. One was based on centralized algorithm,
and another was based on distributed algorithm.
I modified the program by finding the suitable channel using the channel
which is the closest to the channel of the previous edge, instead of
checking from channel 0 to K-1 (K=number of channel in one edge) sequentially
before. For example, if the using channel of the previous edge is n,
then we find the available channel for the current edge by checking
channel n-1, n+1, n-2, n+2.... is suitable or not. The modification
makes it easy for switching channel in technology.
Dr. Jaekel modified
the objective function for shared path protection. It forces CPLEX use
backup multiplexing as much as possible. I improved my program using
CPLEX optimal method based on Dr. Jaekel's modification for formulation
1 and 2.
Compared with previous results, the performance is improved, but the
solution time increases a bit.
Top
Week
12
I modified the program
done in week 11 by using the channel which is the closest to the channel
of the previous edge within a specified range.
In first experiment, using the centralized algorithm, for each connection,
I chose one channel on the first edge and continued from there along
the path. If it fails to find a suitable channel in the middle node,
it will go back to the first edge and choose another channel. I found
the result using different range is almost the same as the result with
full conversion since the total searching range is almost the same as
the full range.
In second experiment, If
it fails to find a suitable channel in the middle node, it will not
go back to check the first edge again, but fail this path. First, I
used channel 0 as the start point when I check the available channel
for
the first edge. When
the range is small, the number of the successful connection is few.
Second, I used a different way, using a random number as the start point
for the first edge. The performance is improved a lot for the small
range.
Top
Week
13
We have done some research
in Dynamic Lightpath Allocation in Survivable Multifiber WDM Networks
before. For the next goal, we focus on the
Static Lightpath Allocation in Survivable Multifiber WDM Networks.
I have studied the
paper, "WDM Network Optimization by ILP Based on Source Formulation"
written by Massimo Tornatiore, Guido Maier, Achille Pattavina. It introduces
a new ILP formulation, Source formulation, to solve routing fiber and
wavelength assignment(RFWA) problem for multifiber WDM network with
and without wavelength conversion. Compared with flow formulation, source
formulation is less computational and memory occupation since it uses
less variables and constraints.
Top
Week
14
I have studied the paper,
"Performance Evaluation of Survivable
Multifiber WDM Networks" written by Yuanqiu Luo, and Nirwan Ansari,
and "On the Routing and Wavelength Assignment in Multifiber WDM
Networks" written by Mohamed Saad, and Zhi-Quan Luo.
Top
Week
15
I have done some research
on the Static Lightpath
Allocation in Survivable Multifiber WDM Networks. Static
optimization of a WDM network can be so summarized: given a static traffic
matrix, find the optimum values of a set of network variables that minimizes
a given cost function, under a set of constrains[7].
Dr.
Jaekel will continue to lead me on this research field
using both ILP optimal method and heuristic method in fall term 2005.
Top
Week
16
This is the last week on my summer research
project. I have worked on my summary report.
Through this work term, I have learned
the fundamental concepts of optical networks, related development and
research directions under Dr. Jaekel's guide and studying some papers
recommended by Dr. Jaekel[5]-[10].
I have learned how to use the optimization
mathematical software tool CPLEX to solve linear programming problems.
I implemented and tested the optimal integer linear programming (ILP)
formulation using CPLEX.
I implemented a distributed algorithm for
solving the dynamic routing and wavelength assignment (RWA) problem
using both dedicated and shared path protection techniques for survivable
wavelength division multiplexing (WDM) networks, and compared the performance
to optimal solutions.
I improved programming skills in language C, and web design skills by
designing a personal web site based on the Canadian Distributed Mentor
Project (CDMP) requirement.
I
would like to thank Dr. Arunita Jaekel, who teaching me not only the
fundamental knowledge of the optical networks, but also the research
method and scientific attitude.
And
thanks to CDMP and NSERC, I have a very good summer time on computer
network research. I have learned a lot from this
research project. It make me more confident in advanced study and research
on computer science.
Top