OSPF Implementation using Dijkastra Algorithm

What is routing?

Network routing is the process of selecting a path across one or more networks. The principles of routing can apply to any type of network, from telephone networks to public transportation. In packet-switching networks, such as the Internet, routing selects the paths for Internet Protocol (IP) packets to travel from their origin to their destination. These Internet routing decisions are made by specialized pieces of network hardware called routers.

Consider the image below. For a data packet to get from Computer A to Computer B, should it pass through networks 1, 3, and 5 or networks 2 and 4? The packet will take a shorter path through networks 2 and 4, but networks 1, 3, and 5 might be faster at forwarding packets than 2 and 4. These are the kinds of choices network routers constantly make.

ROUTING PROTOCOL :

When data move across multiple network, IP routing helps to determine the path of data by setting some protocols to reach the source destination. Ultimately data travels at the physical level through routers IP routing protocols enable routers to setup a forwarding table that correlates final destination with next hop addresses. Let me take you through the internal Routing Mechanism and key terms.

The IP network is classified into two categories: 

a) Interior Gateway Protocol

b)Exterior Gateway Protocol

What is OSPF

The OSPF (Open Shortest Path First) protocol is one of a family of IP Routing protocols, and is an Interior Gateway Protocol (IGP) for the Internet, used to distribute IP routing information throughout a single Autonomous System (AS) in an IP network.

The OSPF protocol is a link-state routing protocol, which means that the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the AS, so that every router within the AS has a complete picture of the topology of the AS. This picture is then used to calculate end-to-end paths through the AS, normally using a variant of the Dijkstra algorithm. Therefore, in a link-state routing protocol, the next hop address to which data is forwarded is determined by choosing the best end-to-end path to the eventual destination.

The main advantage of a link state routing protocol like OSPF is that the complete knowledge of topology allows routers to calculate routes that satisfy particular criteria. This can be useful for traffic engineering purposes, where routes can be constrained to meet particular quality of service requirements. The main disadvantage of a link state routing protocol is that it does not scale well as more routers are added to the routing domain. Increasing the number of routers increases the size and frequency of the topology updates, and also the length of time it takes to calculate end-to-end routes. This lack of scalability means that a link state routing protocol is unsuitable for routing across the Internet at large, which is the reason why IGPs only route traffic within a single AS.

Each OSPF router distributes information about its local state (usable interfaces and reachable neighbors, and the cost of using each interface) to other routers using a Link State Advertisement (LSA) message. Each router uses the received messages to build up an identical database that describes the topology of the AS.

From this database, each router calculates its own routing table using a Shortest Path First (SPF) or Dijkstra algorithm. This routing table contains all the destinations the routing protocol knows about, associated with a next hop IP address and outgoing interface.

• The protocol recalculates routes when network topology changes, using the Dijkstra algorithm, and minimize the routing protocol traffic that it generates.
• It provides support for multiple paths of equal cost.
• It provides a multi-level hierarchy (two-level for OSPF) called “area routing,” so that information about the topology within a defined area of the AS is hidden from routers outside this area. This enables an additional level of routing protection and a reduction in routing protocol traffic.
• All protocol exchanges can be authenticated so that only trusted routers can join in the routing exchanges for the AS.

Implementation of Dijkstra’s Algorthim

The algorithm can be implemented from a source ‘S’ To a destination ‘D’ in the graph by following the below-mentioned points:

Implementation of OSPF using Dijkstra’s Algorithm

• OSPF is used to find the best path between the source and the destination router using it’s own Shortest Path First. Dijkstra’s algorithm is widely used in the routing protocol required by the routers to update their forwarding table.
• It provides the shortest cost path from the source router to other routers in the network.
• Also, the protocol recalculates routes when network topology changes by using Dijkstra’s algorithm and minimizes the routing protocol traffic that it generates.

The distance of vertex connected to each other is taken as the weights and infinity if not connected. With every visit, it calculates the least possible weights following the formula :

dist[r]=min(dist[r], dist[q]+cost[q][r])

Applications of Open Shortest Path First

OSPF is the first broadly used routing protocol. It can unite with a network in very little time, and it is one of the protocols that can render loop-free paths. Aside from these features, Open Short Path First allows the imposition of policies for the propagation of routes in the network.

Open Short Path First is better at load sharing on external links compared to other IGPs. Considering these benefits, it can found widespread use.

Microsoft’s Windows NT 4.0 Server, Windows 2000 Server, and Windows Server 2003 all have OSPF v2 in the Routing and Remote Access Services.

OpenBSD Operating system has an implementation of OpenBGPD protocol which has OpenOSPFD implementation.

GNU Zebra is a GPL routing suite that supports OSPF for Unix-Like systems.