Dynamic Routing Algorithms

Dynamic routing is a networking technique that provides optimal data routing. The network administrators and engineers configure a dynamic routing protocol on the network interfaces. The protocol running on the router learns about others routers automatically and also dynamically exchange routing information with each other. Dynamic routing protocols perform several activities, including network discovery and maintaining routing tables. Unlike static routing, dynamic routing protocol automatically selects the best route to put into the routing table as well as the network changes update automatically into the routing table accordingly. Cisco ISR routers can support a variety of dynamic IPv4 and IPv6 routing protocols including:

  • EIGRP and EIGRP for IPv6– Enhanced Interior Gateway Routing Protocol
  • OSPF– Open Shortest Path First for IPv4 and OSPFv3 for IPv6
  • IS-IS– Intermediate System-to-Intermediate System
  • RIP and RIPng(RIP for next Generation for IPv6)– Routing Information Protocol

All the dynamic routing protocols use routing algorithms. There are two types of routing algorithms:

  1. Distance Vector Routing algorithms
  2. Link state routing algorithms

Dynamic Routing Algorithms

Distance Vector Routing algorithms

distance-vector routing protocol informs its neighbors about topology changes periodically. It is a simple protocol used in packet-switched networks that use distance to decide the best packet forwarding path. It is also known as the Bellman-Ford algorithm, where all routers maintain a Distance Vector table containing the distance between the router itself and all other possible destination and the way to the destination. A hop is a trip that a packet takes from one router to another as it traverses a network on the way to its destination. In simple words, the distance vectors protocols count the hop between the source to the destination.

Each Router configured distance vector algorithm transmits its distance as well as the vector to all neighbors. Other routers using distance vector protocol receives and saves the most recent information from each of its neighbors.  The Distance Vector calculates distance using minimizing the cost to each destination. The Routing Information Protocol(RIP) uses Distance Vector Technique. Using the distance vector, each router advertises its routing table to its adjacent neighbors. Each advertisement has the following information:

Distance – The hop count for the router

Vector – The direction where the route is located

The receiving router does not generate acknowledgements, so it reduces the overhead of routing protocol traffic. The router selects the best path with the lowest cost to the possible destination for the packet. Routers add the selected route to its routing tables and propagate it to the neighbor using hop to hop until all router spread the information to the entire network.

Links State Routing Algorithms

The Link-State keeps complete record and roadmap of the router running link-state routing protocol in the network. Each router running link-state protocol share information about the router to its directly connected interfaces and the state of all interfaces configuring with the link-state protocol. Link-state routing constantly attempts to keep full networks topology by updating itself incrementally when a change happens in the network.

The router sends routing information to all the routers in the network as multicast messages. After starting up, the router sends its first link-state information to its neighbors. So, this reduces the network load by only sending updates to its link information. The Open Shortest Path First (OSPF) is the most important routing protocol type of Link-State routing protocol. The important terms of using link-state are following.

Link-state advertisements (LSAs) –It is an update on their link status, so router send LSA when a link has changed from the current state. It is a small packet of routing information flooded out to all routers in their area or zone.

Topological database – A topological database is a set of information gathered from the exchange of several LSAs between routers, they describe the network topology in great detail. All routers in the network store the received LSA packets in the link-state database (LSDB).

SPF algorithm – The shortest path first (SPF) algorithm also known as the Dijkstra’s algorithm, Performed the calculation of the database and builds the SPF tree. All routers in an area run this algorithm in parallel, storing the results in their topological databases.

Routing tables – A list of the known destination and interfaces.