Routing Information Protocol version 2 (RIP v2) is a routing algorithm that is based on the Bellman-Ford algorithm. As a routing algorithm, it is used to determine the best path between two nodes on a network using distance-vector for path estimation. It makes use of hop count, which is the number of intermediate routers and gateways between a source node and a destination node, to estimate the best path with the maximum hop count put at 15 (Kalamani et al., 2014). This ensures that there are no routing loops in the network. The Bellman-Ford algorithm is based on dynamic programming that uses information about the neighbouring routers.
In considering the graph model of the algorithm as a graph G(n,E,V) where n denotes the number of vertices in the network, E is the set of edges and V denotes the set of vertices, the graph is represented as an adjacency matrix (Hajela and Pandey, 2014). The algorithm uses relaxation principle to determine the single source shortest path on the network modeled as a directed graph that can also have negative edges (Patel and Baggar, 2014).
Figure 1: RIP v2 algorithm with red box showing changes to node states (Acar, 2013).
A router (node or vertex) on the network estimates the distance between it and other nodes on the network by first scanning all the edges to other nodes through the routing tables advertised by neighbor nodes. By initializing the distance vector to a node on the network to 0 and all other nodes to infinity, the algorithm successively calculates the new distance vector to the nodes and the initial vector is replaced by the new estimate if only it is shorter than the older one.
RIPV2 Messaging
The routers in a RIPV2 network communicate with each other in order to advertise their routing tabled for optimal path determination. This is achieved through a broadcast message sent when a router comes online, requesting for the routing tables. On receipt of the request message, the neighbouring routers send response messages of their routing tables which are then used by the newly connected router to update its own routing table.
Another mechanism of messaging comes with the use of timers used to update the routing table entries of a router. Four timers are used by RIPV2 which are the update timer, the invalid timer, flush timer and the hold-down timer. Messages are also sent when timers elapse.
Enhanced Interior Gateway Routing Protocol
EIGRP is also a distance-vector routing protocol developed by Cisco Systems. This protocol is proprietary and so runs only on Cisco routers. The determination of optimal path for routing information from a source to a destination by EIGRP is governed by the use of metrics based on the equation below.
According to the formula, the routing metric is dependent of a number of parameters which are; the minimum bandwidth (kilobits per second) on the path between the router and the destination
the reliability, between 1 to 255 with 255 being most reliable,
the delay along the path between the router and the destination in microseconds
the hop count
the load on the path, between 1 and 255, 255 being most saturated.
The optimal path will be selected based on the path that has the highest metric.
Route Summarization
For large and complex networks, there will be increase in network traffic, routing table size and consequently, the network overhead. One of the techniques used to reduce the network overhead if route summarization where the size of routing tables in a network is reduced through the advertisement of multiple routes as a single route. In figure 2, the routes to the three routers RTA, RTB and RTC are summarized as one route by router Z.
Figure 2: Route summarization example (Patel and Pandey, 2014)
Route redistribution also happens in EIGRP, which entails the interoperation of EIGRP with other routing protocols like Open Shortest Path First (OSPF). Here, the routes learned from one domain such as OSPF are placed in another domain such as EIGRP (Patel and Pandey, 2014).
REFERENCES
Acar, U. (2013). Parallel and Sequential Data Structures and Algorithms. PDF. Retrieved from https://www.cs.cmu.edu/afs/cs/academic/class/15210-s13/www/lectures/lecture13.pdf on 28 April, 2016.
Hajela, G. and Pandey, M. (2014). Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford. International Journal of Computer Applications, 95(15), Pp 1 - 6.
Kalamani, P., Kumar, V.M., Chithambarathanu, M. and Thomas, R. (2014). Comparison of RIP, EIGRP, OSPF, IGRP Routing Protocols in Wireless Local Area Network (WLAN) by using OPNET Simulator tool - A Practical Approach. IOSR Journal of Computer Engineering (IOSR-JCE), 16(4), Pp 57 - 64.
Patel, V. and Baggar, C. (2014). A Survey Paper of Bellman-Ford Algorithm and Dijkstra Algorithm for Finding Shortest Path in GIS Application. International Journal of P2P Network Trends and Technology (IJPTT), 5, Pp 1 - 4.
Patel, H.N. and Pandey, R. (2014). Extensive Reviews of OSPF and EIGRP Routing Protocols based on Route Summarization and Route Redistribution. International Journal of Engineering Research and Applications, 9(4), Pp 141 - 144.
