This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Abstract- Ad hoc networks are characterized by multi-hop wireless connectivity, frequently changing network topology and the need for efficient dynamic routing protocols. We compare the performance of two prominent on-demand and Table driven routing protocols for mobile ad hoc networks Dynamic Source Routing (DSR) and Destination Sequenced Distance Vector (DSDV) . A detailed simulation model with MAC and physical layer models is used to study inter-layer interactions and their performance implications. We demonstrate that even though DSR and DSDV share similar on-demand behaviour, the differences in the protocol mechanics can lead to significant performance differentials. The performance differentials are analysed using varying network load, mobility and Data send rate. Based on the observations, we make recommendations about how the performance of either protocol can be improved.
Keywords-Ad hoc networks, wireless networks, mobile networks, routing protocols, simulation, performance evaluation.
In an ad hoc network, mobile nodes communicate with each other using multi-hop wireless links. There is no stationary infrastructure such as base stations. Each node in the network also acts as a router, forwarding data packets for other nodes.
A central challenge in the design of ad hoc networks is the development of dynamic routing protocols that can efficiently find routes between two communicating nodes [5-6]. The routing protocol must be able to keep up with the high degree of node mobility that often changes the network topology drastically and unpredictably. Such networks have been studied in the past in relation to defence research, often under the name of packet radio networks. Recently there has been a renewed interest in this field due to the common availability of low-cost laptops and palmtops with radio interfaces. Interest is also partly fuelled by growing enthusiasm in running common network protocols in dynamic wireless environments without the requirement of specific infrastructures. A mobile ad hoc networking (MANET) working group  has also been formed within the Internet Engineering Task Force (IETF) to develop a routing framework for IP-based protocols in ad hoc networks.
Our goal is to carry out a systematic performance study of two dynamic routing protocols for ad hoc networks. Dynamic Source Routing protocol (DSR) ,  and Destination Sequenced Distance Vector (DSDV). DSDV  is a hop-by-hop distance vector routing protocol requiring each node to periodically broadcast routing updates. The key advantage of DSDV over traditional distance vector protocols is that it guarantees loop-freedom.
1.1 The Destination-Sequenced Distance-Vector (DSDV) Routing Algorithm [9-10-11] [Perkins94] is based on the idea of the classical Bellman-Ford Routing Algorithm with certain improvements. Every mobile station maintains a routing table that lists all available destinations, the number of hops to reach the destination and the sequence number assigned by the destination node. The sequence number is used to distinguish stale routes from new ones and thus avoid the formation of loops. The stations periodically transmit their routing tables to their immediate neighbours. A station also transmits its routing table if a significant change has occurred in its table from the last update sent. So, the update is both time-driven and event-driven. The routing table updates can be sent in two ways:- a "full dump" or an incremental update. A full dump sends the full routing table to the neighbours and could span many packets whereas in an incremental update only those entries from the routing table are sent that has a metric change since the last update and it must fit in a packet. If there is space in the incremental update packet then those entries may be included whose sequence number has changed. When the network is relatively stable, incremental updates are sent to avoid extra traffic and full dump are relatively infrequent. In a fast-changing network, incremental packets can grow big so full dumps will be more frequent. Each route update packet, in addition to the routing table information, also contains a unique sequence number assigned by the transmitter. The route labelled with the highest (i.e. most recent) sequence number is used. If two routes have the same sequence number then the route with the best metric (i.e. shortest route) is used. Based on the past history, the stations estimate the settling time of routes. The stations delay the transmission of a routing update by settling time so as to eliminate those updates that would occur if a better route were found very soon.
DSDV  is a hop-by-hop distance vector routing protocol requiring each node to periodically broadcast routing updates. The key advantage of DSDV over traditional distance vector protocols is that it guarantees loop-freedom.
Basic Mechanisms Each DSDV node maintains a routing table listing the "next hop" for each reachable destination. DSDV tags each route with a sequence number and considers a route R more favourable than R 0 if R has a greater sequence number, or if the two routes have equal sequence numbers but R has a lower metric. Each node in the network advertises a monotonically increasing even sequence number [7-8] for itself. When a node B decides that its route to a destination D has broken, it advertises the route to D with an infinite metric and a sequence number one greater than its sequence number for the route that has broken (making an odd sequence number). This causes any node A routing packets through B to incorporate the infinite-metric route into its routing table until node A hears a route to D with a higher sequence number.
1.2 Implementation Decisions
We did not use link layer breakage detection from the 802.11 MAC protocol in obtaining the DSDV data presented in this chapter, because after implementing the protocol both with and without it, we found the performance significantly worse with the link layer breakage detection. The reason is that if a neighbour N of a node A detects that its link to A is broken; it will broadcast a triggered route update containing an infinite metric for A. The sequence number in this triggered update will be one greater than the last sequence number broadcast by A, and therefore is the highest sequence number[13-17] existing anywhere in the network for A. Each node that hears this update will record an infinite metric for destination A and will propagate the information further. This renders node A unreachable from all nodes in the network until A broadcasts a newer sequence number in a periodic update. A will send this update as soon as it learns of the infinite metric being propagated for it, but large numbers of packets can be dropped in the meantime. Our implementation uses both full and incremental updates as required by the protocol's description.
However, the published description of DSDV [18-21] is ambiguous about specifying when triggered updates should be sent. One interpretation is that the receipt of a new sequence number for a destination should cause a triggered update. We call this approach DSDV-SQ (sequence number). The advantage of this approach is that broken links will be detected and routed around as new sequence numbers propagate around the broken link and create alternate routes. The second interpretation, which we call simply DSDV, is that only the receipt of a new metric should cause a triggered update, and that the receipt of a new sequence number is not sufficiently important to incur the overhead of propagating a triggered update.
We implemented both DSDV-SQ and DSDV and found that while DSDV-SQ is much more expensive in terms of overhead, it provides a much better packet delivery ratio in most cases. The second scheme (DSDV) is much more conservative in terms of routing overhead, but because link breakages are not detected as quickly, more data packets are dropped. All of the results presented in this chapter use DSDV-SQ, with the exception of Section 5.4.2, which compares DSDV-SQ with DSDV. Table 5.1 lists the constants used in our DSDV-SQ simulation.
1.3 Dynamic Source Routing Protocol
The Dynamic Source Routing Protocol [Johnson99] is a source-routed on-demand routing protocol. A node maintains route caches containing the source routes that it is aware of. The node updates entries in the route cache as and when it learns about new routes.
The two major phases of the protocol are: route discovery and route maintenance. When the source node wants to send a packet to a destination, it looks up its route cache to determine if it already contains a route to the destination. If it finds that an unexpired route to the destination exists, then it uses this route to send the packet. But if the node does not have such a route, then it initiates the route discovery process by broadcasting a route request packet. The route request packet contains the address of the source and the destination, and a unique identification number. Each intermediate node checks whether it knows of a route to the destination. If it does not, it appends its address to the route record of the packet and forwards the packet to its neighbours. To limit the number of route requests propagated, a node processes the route request packet only if it has not already seen the packet and its address is not present in the route record of the packet.
A route reply is generated when either the destination or an intermediate node with current information about the destination receives the route request packet. A route request packet reaching such a node already contains, in its route record, the sequence of hops taken from the source to this node.
Figure 2. Creation of record route in DSRP
As the route request packet propagates through the network, the route record is formed as shown in figure 2a. If the route reply is generated by the destination then it places the route record from route request packet into the route reply packet. On the other hand, if the node generating the route reply is an intermediate node then it appends its cached route to destination to the route record of route request packet and puts that into the route reply packet. Figure 2b shows the route reply packet [22-25] being sent by the destination itself. To send the route reply packet, the responding node must have a route to the source. If it has a route to the source in its route cache, it can use that route. The reverse of route record can be used if symmetric links are supported. In case symmetric links are not supported, the node can initiate route discovery to source and piggyback the route reply on this new route request. DSRP uses two types of packets for route maintenance:- Route Error packet and Acknowledgements. When a node encounters a fatal transmission problem at its data link layer, it generates a Route Error packet. When a node receives a route error packet, it removes the hop in error from it's route cache. All routes that contain the hop in error are truncated at that point. Acknowledgment packets are used to verify the correct operation of the route links. This also includes passive acknowledgments in which a node hears the next hop forwarding the packet along the route.
2. Previous Work
In this section we summarize the most valuable previous studies concerning ad hoc on-demand routing performance comparisons and Table driven protocol. Many researchers have compared and evaluated the efficiency of the most famous on-demand routing and Table driven protocols for wireless mobile ad hoc networks, in the past. As we mentioned above, node mobility is the main network characteristic that reveals the vigilance of a routing protocol to respond to network topology [26-29] changes, and to perform fast route establishment and recovery. Thus, most of the previous studies com-pare the behaviour of the protocols as a function of the node mobility. More specifically, authors in  compare two ad hoc routing protocols using a maxi-mum number of 50 nodes but their traffic load is relatively slow, since the data packet size is 64 bytes, the maximum number of sources is 30 and every source node transmits 4 packets / sec. Furthermore, the authors do not use the latest DSR & DSDV version with the expanding ring search, which has better performance than the older version. Their mobility metric involves number of nodes, Maximum speed, send rate etc: nodes are moving towards a specific point and as soon as they reach it, they stay static for a certain amount of time, which is the pause time. Most of the previous work has taken this metric into account. Authors in  compare two routing protocols, DSR and DSDV for which they used ns2 simulators. Their results are quite valuable; however they assume a relatively small geographical region.
An interesting approach is also followed in , in which authors have introduced a new mobility metric: the relative terminal speeds rather than absolute pause times and speeds. An excellent work is presented in , in which authors have performed an extended performance evaluation between DSR and DSDV, in which the basic mobility metric is the node pause times. This work however does not include large-scale networks either. Their results show that the lack of a mechanism that could expire unused routes from caches in DSR, together with the "aggressive" use of caching, are the main reasons for the large data packet delays and the small throughput at high loads [30-33]. Moreover they observe that if both protocols use larger queues and mechanisms for clearing memory from old routes, then the performance can be increased, while the interaction with a suitable MAC protocol will also be beneficial.
Most of the previous work is limited on performing simulations for ad hoc networks with a limited number of nodes deployed in small geographical areas. The main reason is that simulations with many nodes, spread in a large area, need too much time to be completed using common simulators such as ns-2.
Nowadays, the ad hoc network technology becomes more and more popular and, as a result, large-scale ad hoc networks may be deployed in battlefields, regions of disaster and large towns. A systematic comparison of the efficiency of the current famous ad hoc routing protocols, is needed so as for the wireless community to observe their behaviour and usefulness in such networks. In fact, this was our motivation: to make observations about the behaviour of these protocols under a large-scale environment, and to decide about whether a new protocol needs to be designed, in order for new challenges to be addressed.
3. RELATED WORK
Two recent efforts are the most related to our work, as they use the same ns-2-based simulation environment. Brooch, Maltz, Johnson, Hu and Jetcheva, the original authors of the simulation model, evaluated four ad hoc routing protocols including DSDV and DSR . They used only 50 node models with similar mobility and traffic scenarios that we used. Traffic loads are kept low (4 packets/sec, 10, 30 sources, 64 byte packets). Packet delivery fraction, number of routing packets and distribution of path lengths were used as performance metrics. Santashil and Palchaudharuri, Sridhar Lavu has done similar com- parision in  they have done well but not exactly about the protocols which have been try to explain by this paper. In [10, 34-37] Martin Ganco RAJSHREE AGARWAL also has explain effective comparison.
4. Performance Analysis Using NS2 simulator
The Traffic and Mobility Models
We've used a similar model with ,  changing only the number of nodes. We did so, in order to see the impact of using large-scale topologies in the performance of the protocols as opposed to the case when a limited number of nodes, 50-100, are used. The traffic sources are continuous bit rate (CBR). The source-destination pairs are chosen randomly from the set of the networks nodes and are the same for all the duration of the simulation. The data packet is chosen to be 512 bytes and the channel bandwidth 2 Mbps.
The mobility model is random waypoint in a rectangular field 670m x 670m with 50 nodes. Each node at the beginning of the simulation remains still for "pause" time, then selects a random destination from the simulation space and moves towards that point with a randomly chosen speed (uniformly distributed between 0-50 m/s). Each simulation is run for 200s (simulation time).
Performance comparison between DSR and DSDV Namely:
With different number of Nodes & packets size.
With different Mobile speed & received/sent packets.
With different Data sent rate & rate of dropping packets.
Performance comparison with different number of Nodes
After the simulation with change nodes using both algorithms we get following results in bellow table no. 1.
As per the simulated records, We increase number of nods then packet's size also increased, as per the results of DSDV and DSR 38 routing algorithms, DSDV's packet size grater than DSR, it is the advantageous of DSDV Routing algorithms for fast communication over DSR algorithm.
Average packet size (DSDV)
Average Packet size (DSR)
Description of graph: It is clear from graph that in DSR when increasing number of nodes there have further decrement in packet size. This disadvantage of DSR can be overcome with the help of DSDV. In DSDV when number of nodes increase it doesn't decrease, its packets size increase.
Performance comparison with different Mobile speed & Received/sent packets.
As per the 2nd metric of performance comparison we get results and comparison with different mobile speed v/s received/sent packets:
recv/sent pkt dsdv
recv/sent pkt dsr
On the base of above results we have generate above graph, which are showing the rate of dropping packets are lesser of DSR [39-40] than DSDV, during fast node movement in the network area. It's showing the good performance of DSR than DSDV.
With different Data send rate & rate of dropping packets.
With different data send rate during transmission in the ad hoc network area for DSDV & DSR routing protocol, we get following records:
Pkt dropped DSDV
Description: Above table records are showing that rate of dropping packets of DSR lesser than DSDV protocol. It is the beneficial for fast data send rate if we use the DSR Protocol than DSDV.
Above graph are showing DSR graph are bellow than DSDV graph. Its means dropping packets are lesser than DSDV routing protocols. It is showing the best performance of DSR than DSDV.
We have compared performance of DSR and DSDV, Here we have compare one on demand routing protocol and another Table driven protocol for ad hoc networks respectively. DSR and DSDV both use different route discovery and different routing mechanics. In particular, DSR uses source routing and route caches and does not depend on any periodic or timer-based activities. DSR exploits caching aggressively and maintains multiple routes per destination. Every mobile station maintains a routing table that lists all available destinations, the number of hops to reach the destination and the sequence number assigned by the destination node. The sequence number is used to distinguish stale routes from new ones and thus avoid the formation of loops.
As per the above comparison between DSR and DSDV and their results we get the better performance for DSDV when we increase the number of nodes from 20 to 125 packets size also increased for transmission. For different Mobile speed Received/sent packet ratios are lesser for DSR than DSDV, and dropping packets are also lesser for DSR than DSDV.