RWA algorithm based on Dijkstra’s algorithm to find the
shortest routes between all source nodes and destination
nodes based on the least distance
MKET1573 Optical Communication Networks
Prepared by
Abdisalan Abdulkadir Mohamed
Mohamed Mohamud Ahmed
Mostafa Ragab Zaky Mohamad
Lecturer:
Dr. ARNIDZA RAMLI
Introduction
Data is transferred by light pathways, or wavelengths, via optical fibers in optical networks, where
routing and wavelength assignment (RWA) techniques are essential. The process of choosing the
wavelength assignment and the path routing for data transmission from a source to a destination is
referred to as RWA in optical networks
The RWA problem can be simplified by dividing it into a lightpath routing (LR) problem and a
wavelength assignment (WA) problem.
Using graph theory-based algorithms, such Dijkstra, is one efficient way to address the RWA problem.
This approach is well known for figuring out the best routes in optical networks by locating the shortest
path in a graph from a source node to every other node. The main objective is to prevent wavelength
congestion and interference in order to reduce signal deterioration and enhance network efficiency. It can
be modified as follows for RWA:
1. Graph Representation
2. Initialization
3. Shortest Path Calculation
4. Path Reconstruction:
5. Wavelength Assignment:
Advantages of Using Dijkstra’s Algorithm for RWA:
- Efficiency: Dijkstra's technique is appropriate for large-scale optical networks since it computes shortest
paths in sparse graphs with efficiency.
- Perfectionism: It ensures that data is transferred via the least-cost route in terms of distance or other
specified
metrics by guaranteeing the finding of the shortest path.
- Adaptability: Additional restrictions or network features, such transmission quality and wavelength
availability, can be incorporated into the algorithm.
PROBLEM BACKGROUND
• An overview of the algorithm's past applications in resolving the WDM network shortest path problem is provided
below:
• WDM Network Emergence: Wavelength division multiplexing (WDM) is a technology that was developed in the 1990s
to boost optical fiber capacity by simultaneous transmission of several wavelengths (or channels).
• Routing Difficulties: With the advent of WDM, networks required effective algorithms to route data between nodes while
guaranteeing effective wavelength channel utilization.
• Algorithmic Foundation: Edsger Dijkstra, a Dutch computer scientist, created Dijkstra's algorithm in 1956 to determine
the shortest path between nodes in a network. It was initially created for computer network routing, but it later served as
the basis for many other optimization issues, such as telecom routing.
Dr. Edsger Dijkstra at ETH Zurich in 1994
PROBLEM BACKGROUND (CONTINUED)
• Integration with RWA: Scientists and engineers realized that Dijkstra's method was a good fit for determining
the shortest pathways in WDM networks. The algorithm was modified to deal with the particular limitations of
optical networks, where pathways depend on wavelength channel availability in addition to distance.
• Path Calculation: Using either hop count or distance as the measure, the shortest pathways between every pair
of nodes in the network were first determined using Dijkstra's method.
• Development and Enhancement: Extensions and Modifications: As time went on, scientists created Dijkstra's
algorithm extensions and modifications that were specifically adapted to the requirements of optical networks.
These included adjustments to meet QoS needs, dynamic traffic demands, and wavelength channel
optimization.
• Impact and Adoption by Industry
Standardization: In the telecommunications sector, the use of Dijkstra's algorithm and its variations for WDM
network planning and management has become industry standard
• Operational Efficiency: RWA algorithms based on Dijkstra's ideas
considerably improved the operational efficiency and
performance of optical networks by permitting the effective
use of network resources and eliminating wavelength
channel conflicts.
.
METHODOLOGY
1. Representation of Networks
G=(V,E) is the graph that represents the optical network. The collection of nodes (network components such as switches and
routers) is denoted by the variable V. The network of fiber optic cables, or links, that connects nodes is known as E. Each link can
accommodate several wavelength channels.
2. Setup
Distance Initialization: Create a distance matrix D, in which the shortest path cost (or distance) between nodes i and j is
represented by the matrix D[i][j]. First, for all i≠j, set D[i][j]=∞ and D[i][i]=0.
3. Implementation of Dijkstra's Algorithm
Calculate the Shortest Path: From each source node (s), use Dijkstra's method to determine the shortest pathways to every other
node (t) in the network.
Priority Queue: To quickly retrieve the node that is adjacent to you with the least known distance, use a priority queue (min-
heap).
Relaxation For each node u, relax all adjacent nodes v (nodes directly connected to u) by updating their shortest path
distances if a shorter path through u is found.
Path Record: After the algorithm runs, keep track of the nodes that came before it in order to reconstruct the shortest paths.
4. Path Choice
Shortest Path Determination: Based on the calculated shortest path distances D[s][t], each source-destination pair (s,t) chooses
PROGRAM WORKABILLITY
The provided MATLAB code defines a matrix called "connections," in which each row represents an edge in a graph. Each
row specifies the start node, the end node, and the distance between them. The matrix contains multiple connections,
including an edge from node 1 to node 2 with 70 km, and so on.
Connections of the nodes
The following MATLAB code generates a weighted graph object G using the start nodes, end nodes, and distances provided
in the connection’s matrix.
Calculating the Shortest Path of all nodes
PROGRAM WORKABILLITY (CONTINUED)
This MATLAB code assigns a value of 0 to the diagonal members of the distance matrix, indicating that the distance from any node
to itself is zero.
Sets the diagonals to zero
This MATLAB code computes the shortest pathways between every pair of nodes in the graph G. It saves the distances in the
distance matrix and displays each shortest path along with its corresponding distance. The algorithm uses the shortest path function
to determine the path and distance between every pair of different nodes. It then updates the matrix and presents the outcomes.
Calculates the shortest Path
SIMULATION RESULTS AND ANALYSIS
This is generated graph from MATLAB simulation.
The graph visually represents the RWA assignment for optical communication networks, showing nodes and the weighted distances
between them. The clear labeling of distances helps in understanding the connectivity and efficiency of the network.
Dijkstra's method calculates the minimum distances between every
pair of nodes in the following figure. The table concisely
outlines the minimal distances required to travel
between nodes in the network.
Thank you
