Distance Vector Routing Algorithm Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In this paper, there will be some explanations on Distance Vector Routing algorithm base on some references journal to understand its concept. We will see that there are multiple methods were presented for the past ten years in order to make DVR algorithm become sufficient enough to contribute into wireless development and enrich the application. We try to explain multiple journal in such way that we can define the answer, why DVR today is upgraded tremendously. The best way to evaluate is by looking to the specification of it bandwidth, durability, network utilization, stability, speed and latency.


"Hand-off" process will happen when a cellular mobile moves out from its own range at a base station (BS) and then switch to a new BS. The process should be fast enough and it involve only with the participating of mobile cellular nodes. We called this as an ad-hock network [4]. An ad hoc network is a dynamic connectionless network without permanent infrastructure or administration. Topologies changes frequently. Through this network, mobile nodes using multi-hop wireless link to interact with each other's [12]. In this environment, there are limited of ad-hoc network energy, bandwidth, and physical security. The ability of node to route data-packet for other node are expected in the network, above their own transmission area. It becomes the basic requirement for ad-hoc network which construct the interconnecting structure for mobile node.

Mobile ad hoc network MANETs are important and multipurpose application for nowadays communication network. Their topologies are dynamic and are difference compare with wired network. MANET require efficient routing algorithm. The present routing algorithms can be classified into two types; on-demand and table-driven. The routing base on on-demand such as Ad hoc On-demand Distance Vector AODV[1] will find an actual path only when the sources needed. However the routing base on table driven needed each single node stores the global routing information and periodically updating it such as Destination Sequence Distance Vector (DSDV). Routing Information Protocol (FIP) and BF are traditional distance-routing algorithm and not suitable for MANETs.

By using simulation show that Adaptive Distance Vector routing (ADV) contribute better performance than AODV specifically in the cases of high mobility [8]. It uses fewer routing and control overhead packets.

Innovative distance vector-routing algorithm base on token was then proposed in [2] journal paper to achieve better performance in routing as well as suit with MANETs. Also, we manage see the performance in [8] which is combination both on-demand and proactive routing method to design eligible routing protocols for MANETs. The difference between Token-based Distance-vector Routing Algorithm (TDVRA) compare to the others Distance-vector Routing (DVR) Algorithm goes when table RT which records the distance to other nodes in distance vector routine algorithm will be added with the neighbor node G, instead of maintaining other three records (d, D, P). However the NT's table remains the same. Both NT and RT are in Route table. The TDVRA is loop-free, ability to count to infinity and solving routing fluctuations problem.

Table 1: Differences between Algorithm

The routing base on AODV becomes relevant when many novel algorithms derived by researchers all over the world to improve existing algorithm. This are includes Self-repair algorithm. Base on [3] Journal, SRAODV is the algorithm proposed to takes the immediate nodes when the link break is occur, traces the link break and repairs the break route. If the intermediate node is repair but fail, the backward pre-hop node would prefer to search for an instead new route. Worst to worst condition, the new algorithm will be AODV. SRAODV decrease the latency and improve the throughput of the package deliver. It suit application involve with a dynamic network as what was discussed in MANETs. To broadcast Route Request (RREQ), the in-between nodes on the data flow are preferred rather than the source. This idea used by the algorithm of SRAODV to enhance the algorithm of AODV by adopting the in-between nodes and avoid using source to repair a route to destination. The process will involve sending Route Repairing (RR), Router Repairing Fail (RRF), Router Repairing OK (RROK) as well as Route Request (RREQ) in-between intermediate nodes without involve sending Route Error (RERR) to the source. Base on simulation result, most of the cases are valid as the above explanation. However, special cases existed when SRAODV are some less then ones using AODV and the latency value is higher. According to the writer, the future research may explain and elaborate on these special cases.

The performance of AODV may decay when the mobility of the data is high and multiple streams send to a usual location. There is a method which enhances the ratio of AODV packet delivery although in critical condition to the level of satisfactory. This is the proposed way from [4]; aim to improve performance in internet connection by applying local congestion methods in routing protocol. The ratio of the AODV packet delivery may increase up to 27% as a result of applying this method. Earlier the journal discover on innovation of AODV from DSDV as well as the process of RREQ feature to the destination until it being reply by Request Reply RREP. Here we can see that repeated RREQ will be discarding. Once the repeat request RREQ arrive at an intermediate node or at a destination, the intermediate node or destination replies back the packet of unicasting RREP to the neighbor who received the RREQ first. Critical time arrive when RREP routed back while the node along this path setup forward route. Deletion will appear if it is not use within the specific lifetime. AODV only support symmetric links. For routers, if a source node moves, it is able to reinitiate the route discovery protocol to find a new route to the destination. If a node along the route moves, its upstream neighbor notices the move and propagates a link failure notification message (an RREP with infinite metric) to each of its active upstream neighbors, to inform them of erasure of that part of the route [5]. From the observation of multiple sources, transmitting data to a common destination, the packet delivery fraction decreases up to 27% for AODV, normalized routing load and end to end delay also increases for both AODV. Analysis have been made and the propose technique are then apply to AODV. We will see that alternative routes are limited only to the active route and eliminate the stale ones. This are made to avoid congestion. However, localize congestion will occur. Therefore there are congestion control mechanism of AODV exist as result. The local route repair mechanisms also take place. At the end it will then improve performance in the packet delivery fraction, normalized routing load and end to end delay as a result.

As the conclusion of these modifications of routing algorithm for AODV in constrain condition, the AODV and DSR performs better in the normal case but decreases during multiple sources transmit data to a common destination. The method was proposed to overcome congestion that occurs. This is the earlier method before applying the algorithm.


There are numbers of implemented routing protocols to route the packets in networks. Routing protocol such as Destination-Sequenced Distance-Vector (DSDV), Ad hoc On-demand Distance Vector (AODV), Ad Hoc On-Demand Vector Stability base Route Repairing (AODVSRR) and so on which we have go through previously, need to do evaluation on its performances and throughput. One of the journal [12] was evaluated the performance of DSDV routing protocol using Constant Bit Rate (CBR) traffic pattern with different loads in the network. For information, DSDV protocol routing algorithm is the idea of the classical Bellman-Ford routing algorithm with certain improvements. Usual routing table must be developed to see the style of routing and prevent routing loops. Two sequences step are find out to decrease network traffic for updating routing table. Firstly, a full dump is maintained. Such packets contain all available routing information. Secondly, modified routing information packets since the last full dump process are transmitted. Therefore a node exchanges routing tables (fully or partially) with its neighbors, periodically or whenever a change in topology is detected. To show the protocol performance, a metrics suggested by MANET are applied. The protocols are Drop Ratio and End to end data relay. Constant Bit Rate (CBR)


To make DVR become more efficient are the one of researcher's future target. The journal [6] tries to elaborate on how to enhance two classes of distance vector routing algorithm to be a more efficient distance vector routing EDVR. EDVR operates by specifying a distance, a feasible distance, a predecessor and diffusing hops to each destination. The Routing Information protocol (RIP) based on the Distributed Bellman-Ford algorithm (DBF) is very simple implementation but very inefficient to infinity problems which cause data packets traverse loops indefinitely.

An Algorithm which replaces information's distance is called a path finding. Every router allows sending the whole tree routing's shortest-path to its own neighbors. Both part-finding algorithms will terminate the complicated routing table. This is the new technique algorithm which avoids combining loop used in diffusing update algorithm path finding algorithms and DUAL to provide the shortest- loop-free routing, better in term of efficiency compare with others algorithms.

EDFA principal of idea is base on two basic ideas. First, it uses predecessor information for each destination. This behavior terminates the counting problem to infinity. This is very clear when a loops which are temporary can be detected through router in a finite period and speed dependency but doesn't detect through distance value which offered by its neighbors. As a result, temporary loops have ability to be detected earlier compare with DBF as well as its specification. Second main idea of EDFA is blocking temporary (quasi-routing) loops using an inter-nodal synchronization method that is an extension of the synchronization mechanisms of DUAL and LPA. This result will give impact to one or multiple hops. The span of a router's query will be controlled using number of adjustable "diffusing step" include in queries.

In EDVA, a router can be in one of two or two state for a given destination which is passive or active. A passive router has a feasible successor. When router is passive, it reports its current routing information in its updates and replies. An active router however cannot send a new update regarding the destination for which it is active.

To simplified our understanding, EDVA is propose as a new routing algorithm to reduce routing converge time and the number of packets for routing information time. The research of EDVA will continue with various values and adjustable parameters to analyze its performances.

In ADV protocol, controlling the timing of update is more efficient than the periodic full update. Updating active entry of routing table is more efficient than updating full table. Analysis was done to compare performances between AVG and AODV. From figure 1, using AODV contribute 70% higher compare with AVG. AVG also denoted that it have less routing packet compare to AODV. Ferreting to figure 3, we will see that Applying ADV protocol overhead is decrease very much compared to other on demand routing. ADV can be a good protocol in burst traffic condition. It is strong in term of multi-hoop, mobile and wireless environment. It provides lower latencies for real-time traffic scenarios.[8]

Figure 1: Contribute Lower Latency than AODV

Figure 2: Packet deliveries performance compare with AODV

Figure 3: Routing overhead performance compare with AODV

Figure 4: Throughput performance compare with AODV


We can see that EDVA can contribute into the efficiency of DVR. However, not only efficiency is important, the algorithms need to be stable. This is due to the AODV which is widely deployed in Ad Hoc networks. The journal [7] propose a modification on AODV protocol to be Ad Hoc On-Demand Vector Stability base Route Repairing (AODVSRR). By calculating the route stability process to the RREQ massage and the route repair mechanism to the RREQ massage, the new protocol not only reduces the packet loss rate and the end-to-end latency, but also enhances the utilization rate of the network resources. The algorithms appear due to the routing protocols overlook the route stability of the network nodes and the shortest path will be the "hotspot" of the network. When active route fails, AODVSRR algorithm will increase the performance base on the stability estimation method. Link stability is used in Ad hoc On-demand Stability Vector AOSV. The difference come when we see that AODV will select the shortest path but fail to repair the route compare with AODVSRR. Simulation and analysis was made and the packet delivery ratio of AODVSRR achievement increase higher than AODV approximately 3%. As a conclusion, by adding the maximum stability field to the RREQ massage avoids selecting the unstable routes automatically during establishing a new route, a new algorithm of AODVSRR is proposed. It will than adding the routing repair mechanism to the RREQ message instead of initiating a new routing discovery as far as possible. This improvement reduce packet loss rate and end-to-end latency as well enhance the utilization rate of the network resources.


Due to instability of communication link and mobility of nodes, multiple route protocols are required. A brand new route protocol which is consisting of multiple route calls a protocol of Multiple Route Ad-hoc On-demand Distance Vector (MRAODV) was propose from [9]. This journal relates multiple routes with flooding of a control massage. Though Multiple Next Hops (MNH) as shown in figure 6, it detect multiple massage transmission routes, the number of detect routes is not so many. The MRAODV protocol, MNH protocol as well as Ad hoc On-demand Distance Vector Backup Routing AODV-BR protocol are than evaluated. From long evaluation process, they evaluate performance of the proposed MRAODV protocol compare with MNH and AODV-BR. The results were shown that MRAODV detect more route compare with two other protocols. It also becomes the higher in term of available route number. However MRAODV is not leading in time duration between invocations of the protocol. Direction of branch backward route is dynamically changed to detect as many routes as possible(figure 7). Therefore in future, research on MRAODV must focus on time duration because of some weakness on it.

Figure 5: Ad Hoc On-Demand Protocol (AODV) protocol

Figure 6: Less Detect Route in MNH

Figure 7: Link in backward


AODV algorithm as we discuss previously is actually consume much energy which make the nodes die too early. Improvement made to reduce the possibilities that some low energy nodes or key nodes die during information transmitting. It will then improved algorithm, enhancing the reliability of the network transmission, decreases the energy consumptions of the network and extends the lifetime of the node.

For this purpose of introducing low data rate and low cost, ZigBee network was introduced. It have significant feature such as low power consumption, great network capacity and short transmission delay. There are some other interesting feature in ZigBee network that contribute so much in developing low energy to the nodes in the network. Base on [10] propose multi-path energy balance routing algorithm (E-AOMDVjr) to reduce energy consumption, avoid network segmentation and node death as well as improve network energy efficiency. This algorithm improves the reliability of ZigBee network effectively and extends the network life. Testing and analysis were taken to analyze performance between E-AOMDVjr and AODVjr. In term of packet delivery ratio, E-AOMDVjr leads the overall percentage as shown in figure 8. In term of average end to end delay and normalized routing overhead, we can refer to figure 9 where E-AOMDVjr became the lowest in the comparison which is very good. Lastly base on figure 10 of route discovery frequency, E-AOMDVjr reduced because AODVjr algoritm uses single-path protocol. Therefore we can see that the ZigBee network is an emerging field with high practical value. The E-AOMDVjr algorithm then is an effective method to reduce the routing overhead, avoid premature death of high energy node and make use of the network resources efficiency.

Figure 8: Performance in Packet Delivery Ratio

Figure 9: Performance in average end to end delay

Figure 10: Performance in route discovery frequency


Previously we notice that IP network can die or disappear early because of its own over energy consumption. We also notice that ZigBee network contribute into the survival of IP network. In term of IP network survivability, some mechanism is introduce in [11] for its own healing purposes. This mechanism is known as "Fast Self-Healing Distance Vector Protocol" (FS-DVP). It can guarantee the forwarding continuity in the convergence period. It also a better stabilizing provider as we as reduce overhead to massage update. The DVR protocol is based on Bellman-Ford Algorithm.

Under this mechanism, if there are failure occur at the foremost next hop, nodes suppressed global advertisement and alternatively initiate packet regional rerouting, using the backward nodes subset that was to be forwarded through the fail link. The idea of FS-DVP is to pre-computer multiple feasible next hops per destination. The descriptions of the algorithm are getting backup node set, and then introduce the strategy of reroute forwarding and suppression-failure. There are methods of producing alternative set of node and its characteristic come with algorithm.

Under FS-DVP properties, it states a process of how to forward packets through FS-DVP's protocol, when a router receives the packets. We shall understand that when suppression's fail, suppression failure will be used by FD-DVP to handle future data. If FS-DVP deals with multiple failures, it can handle it simultaneously by preparing nodes in every destination's multiple nodes. However, it cannot lead to a loop during the suppression. FS-DVP also prevents "Slow Convergence" or call "Count to infinity". When the network traps into the loops, the metrics increase slowly until they reach infinity.

FS-DVP basis is distance vector protocols (DVR). Therefore FS-DVP capable to interface with each of DVR and will change the protocol only for the triggering update mechanism modification. For this moment FS-RIP will be applied by FS-DVP to RIP protocol called FS- RIP. FS-RIP use reactive failure recovery strategy to deal with multiple link or node failures simultaneously, which enhance availability of the network. Meanwhile the use of FS-DVP increases the stability. Through analysis we can see that FS-DVP able to save storage space and decrease network load effectively.

Briefly FS-DVP is proposed in order to deal with the frequent node or link failure. This mechanism able to handles the packet forwarding when the main next hop occur failure through establishing the set of backup next hops. To avoid the transient failures affecting the network stability, FS-DVP uses the routing update mechanism to enhance the network stability. This mechanism can suppress the failure message notification and adopt local rerouting strategy, to avoid reduction of availability. Theoretically, analytically and through simulation, it define that the result occurred, prove that FS-DVP ability to deal with links or nodes failures as well as increase the strength to the availability and stability's routing.


There are many algorithms which rise up recently to enhance Distance Vector Routing become well in overall performances. With many new idea of modification, in term of speed (time taken), stability of the network, durability of nodes, Increasing of bandwidth, what network is utilize, as well as latency make this Routing become more realistic. However there are still many things can do to this protocol and many relevant researches are needed. New ideas sometime give high impact to the previous research but some are less. However there are still can make more contribution of some idea for high impact research later on.


[1] T. Camp, J. Boleng, and V. Davies, A Survey of Mobility Models for Ad Hoc Network Research, Wireless Communication & Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking:

[2] L. Wang, Y.p. Lin, Z.p. Chen, "A Distributed Tokens-based Distance-Vector Routing Algorithm for Mobile Ad-hoc Networks", in Proc. Of the IEEE ICCNMC, 2003, pp. 1-4

[3] F. Jing, Z. Huaibei, "A Self-Repair Algorithm for Ad Hoc On-Demand Distance Vector Routing", in Proc. Of the IEEE, 2006, pp. 1-4

[4] G.S. Tomar, "Modified Routing Algorithm for AODV in Constrained Conditions", In Proc. Of IEEE DOI, 2008, pp. 219-224

[5] Charles E. Perkins, Elizabeth M. Royer, "Ad-Hoc on Demand Distance Vector Routing." Prac. 2nd IEEE FVksp. Mobile Conp andApps, pp. 90-100, Feb. 1999.

[6] Zhengyu Xu, Sa Dai and J . J . Garcia-Luna-Aceves, "A More Efficient Distance Vector Routing Algorithm.", in Proc. Of the IEEE , 2007, pp. 1-5

[7] S.S. Aalam and T,D.A.Victorie, "Stability base Route Repairing Algorithm for Ad Hoc On-Demand Distance Vector Routing". in Proc. Of the IEEE , 2010, pp. 98-101

[8] A.Nagaraju and C.H. Ramya Krishna, "Performance Evaluation of ADV with AODV for Mobile Ad-Hoc Network." in IEEE Network Magazine, 2009, pp.375-380

[9] H.Higaki and S.Umeshima, "Multiple-Route Ad-Hoc On-Demand Distance Vector (MRAODV0 Routing Protocol."

[10] J. Xiau and X. Lie, "The Research of E-AOMDVjr Routing Algorithm in ZigBee Network." in IEEE Network Magazine, 2011 Chinese Control and Decision Conference (CCDC), pp.2360-2365

[11] B.Wang, J.H Zhang, Y.F.Guo and J.Zhou, "A Study of Fast Network Self-Healing Mechanism for Distance Vector Routing." in IEEE Network Magazine, 2009, pp.413-416

[12] E. Mahdipour, A.M. Rahmani, E.Aminian, "Performance Evaluation of Destination-Sequenced Distance-Vector (DSDV)." in IEEE International Conference on Future Network, 2009, pp.186-190