Dijkstra Algorithm as Used in the OSPF Routing Protocol

noreply@blogger.com (Unknown) — Sun, 01 Aug 2010 02:54:00 +0000

This article about Dijkstra Algorithm as used in the OSFP routing protocol. This describes steps by steps how ospf calculate shortest path to the destination using Dijkstra Algorithm and also this describes more details about OSPF routing protocols and its main operation.

Abstract – This document explains about how Dijkstra algorithm operates and main procedures of the algorithm. And this document also explains OSPF routing protocol how it implement Dijkstra algorithm to find the shorted path to the destination.

1. Introduction

Communication is most important for the 21^st century’s development. It allows people around the world to communicate each other at real time and improves their activities in day to day their lives. Communication is getting developing in every day as the result of emerging technologies. Internet and computer networking take the major part of this greatest communication development. There are various interconnected autonomous systems in a complete network which can communicate different nodes to forward the information. In order to transfer data from a source to the destination, the network must find out the best route between source and destination. This can be done by using routers. The routers are responsible for receiving and forwarding data packets through the interconnected set of networks. Routing is most important process of the network system that determines best end to end paths from source to destinations. At the router there is an algorithm which takes the dynamic decisions to determine the best path from source to the destination. This algorithm is known as Routing Algorithm. There are different routing algorithms available in these days Dijkstra Algorithm is one of them.

2.Dijkstra Algorithm

Dijkstra's algorithm is introduced by Dutch computer scientist Edsger Dijkstra in 1959. This algorithm solves the single-source shortest-path problem for a graph when all edges have non-negative path costs by producing shortest path tree [1]. Dijkstra Algorithm is also known as SPF (Shortest Path First) algorithm. [2]

2.1 Basic Steps of the Dijkstra Algorithm

The following example will explain the steps of Dijkstra's Algorithm to find the shortest route from the origin S to the destination T.

1. Initially mark the source as solved. Distance will be 0

2. Identify all unsolved nodes directly connected to solved nodes

3. Calculate the candidate distance
Candidate distance = Distance to the solved node + length of arc

4. Choose smallest candidate distance

Smallest candidate distance = XA = 2

5. Set the A as solved node and candidate distance is 2 to the A node. Repeat the steps until destination is reached.

6. Identify all unsolved directly connected node to the A and S and then calculate the candidate distance

We have two equal lowest candidate distance (XB1 & XC). In this case choose one of them arbitrarily. Set the B as solved node. (Candidate distance is 3)

7. Identify all unsolved directly connected node to the A, B and S and calculate the candidate distance

Smallest candidate distance is XC2 (XC2 = 3). Set C as solved node. Still we haven’t reached the target.

8. Identify all unsolved directly connected node to the A, B and C and calculate the candidate distance.

Smallest candidate distance is XD1 (XD1 = 5). Set D as solved node. Still we haven’t reached the target.

9. Identify all unsolved directly connected node to the A, B and D and calculate the candidate distance.

We have two equal lowest candidate distance (XB1 & XT2). In this case choose one of them for shortest path and other one for alternative route for destination. Smallest candidate distance is 8.

Therefore shortest routes for form S to T by using Dijkstra algorithm are:
S – A – T and S – A – B – T and shortest distance is 8. [3]

Cisco Computer Networking - Dijkstra Algorithm as Used in OSPF Routing Protocols

Dijkstra Algorithm as Used in the OSPF Routing Protocol

1. Introduction

2.Dijkstra Algorithm