Destination Sequenced Distance Vector Computer Science Essay

Published:

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

ABSTRACT

Destination Sequenced Distance Vector (DSDV) Protocol and Ad-hoc On-Demand Distance Vector (AODV) Protocol are two routing protocols which were designed for Mobile Ad-hoc Network (MANET). Ad-hoc network is a collection of wireless nodes which are mobile in nature, dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. Each node in MANET participates in routing by forwarding data for other nodes. The topology of the network in a Mobile Ad-hoc Network usually changes with time due to the mobility of nodes, interference, multipath propagation and path loss. Therefore, there are new challenges for routing protocols in Mobile Ad-hoc Networks. So, routing protocols such as Destination Sequenced Distance Vector (DSDV) and Ad-hoc On-Demand Distance Vector (AODV) have been implemented. The purpose of this master thesis is to study, understand, analyze and discuss DSDV and AODV with comparison of their respective performances such as packet delivery ratio, throughput and routing overhead using a simulation tool called NS2. DSDV is a proactive protocol depending on routing tables which are maintained at each node. AODV is a reactive protocol, which find route to a destination on demand, whenever communication is needed.

CHAPTER - 1

INTRODUCTION

A computer network is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information. Initially, computer networks were started as a necessity for sharing files and printers but later this has moved to application sharing and business logic sharing. These networks may be fixed (cabled, permanent) or temporary and wired or wireless. Wireless can be distinguished from wired as there is no physical connection between nodes in the network.

WIRED NETWORKS

In wired networks, hardware components and computers are generally connected with the help of wires and cables. Generally the cables being used in these networks are CAT5 and CAT6 cables. The connection is usually established with the help of physical devices such as Switches and Hubs in between to increase the strength of the connection.

WIRELESS NETWORKS

Wireless networks used some sort of radio frequencies in air to transmit and receive data instead of using wires and cables. The most important thing in these networks is that it eliminates the need for expensive cables. Wireless networking is an emerging technology that allows users to access information and services electronically, regardless of their geographic position. It can be classified in two types. The first one is the infrastructure network; it consists of a network with fixed and wired gateways. Another is the infrastructure less (ad-hoc) networks; in ad-hoc networks all nodes are mobile and can be connected dynamically.

ROUTING AND ROUTING PROTOCOLS

Routing and routing protocols are the most important tasks in MANET. Routing is the act of moving information from source to a destination in an internetwork. During this process, at least one intermediate node within the internetwork is encountered. Routing involves two activities; firstly, determining optimal routing path and secondly, transferring the information group (called packets) through an internetwork. The later concept is known as packet switching which is easy and straight forward but the path determination could be very complex.

A lot of the routing protocols mainly use the flooding technique for route discovery which is explain briefly as follows: A sender S broadcasts data packet P to all its neighbors and each node receiving P forwards P to their neighbors - In this way, packet P reaches the destination D provided a path from S to D exists. Node D does not forward the packet. One routing protocol that makes use of this technique is Ad-hoc On-demand Distance Vector (AODV) Routing, a routing protocol for Mobile Ad-hoc Network.

Ad-hoc On-Demand Distance Vector protocol is an on-demand protocol or reactive protocol which was designed for ad-hoc networks. AODV is a very efficient, simple and effective routing protocol for Mobile Ad-Hoc Networks which do not have fixed topology. This algorithm was motivated by the limited bandwidth that is available in the media that are used for wireless communication. It borrows most of the advantageous concept of DSR and DSDV algorithms. The on demand route discovery and route maintenance for DSR and hop-by-hop routing, usage of node sequence numbers from DSDV make the algorithm cope up with topology and routing information. The AODV protocol is loop-free and avoids the count-to-infinity problem by the use of sequence numbers. Obtaining the routes purely on-demand makes AODV a very useful and desired algorithm for MANETs.

Another widely used protocol of Mobile Ad-hoc Network is DSDV. DSDV is a proactive or in other word table driven protocol which is a modification of the conventional Bellman-Ford algorithm. The important feature of DSDV is the used of sequence number for the routing table entries. These sequence number are generated by the destination stations and routing tables at each node are synchronized by each node advertising its routing table information to its neighbors frequently. Forwarding decisions are made based on the sequence numbers. The main advantages of DSDV are that it guarantees loop-free paths and always maintains the best path to destination rather than multiple paths. However, routing table updates are costly, and there is no support for multi-path routing

The performance comparison of DSDV and AODV routing protocols can be done by using several existing performance measuring metrics for ad-hoc routing protocols.

Performance measuring metrics for ad-hoc routing protocols are -

(i) Throughput: It is defined as total number of packets received by the destination. It is a measure of effectiveness of a routing protocol.

(ii) Packet delivery ratio: It is the ratio between the numbers of packets received by the destination to the numbers of packets originated from the source. It is a measure of efficiency of the protocol.

(iii) Routing overhead: The total number of routing packets transmitted during the simulation. For packets sent over multiple hops, each transmission of the packet (each hop) counts as one transmission.

(iv) Path optimality: The difference between the number of hops a packet took to reach its destination and the length of the shortest path that physically existed through the network when the packet was originated.

(v) Packets lost: It is a measure of the number of packets dropped by the routers due to various reasons such as Collisions, Time outs, Looping, Errors.

(vi) Packets Delay (Jitter): It is a metric which is very significant with multimedia and real time traffic. It is very important for any application where data is process online.

(vii) Power consumption: The total consumed energy divided by the number of delivered packet.

PURPOSE

The objective of this Work is to concentrate mainly on Destination Sequenced Distance Vector (DSDV) and Ad-hoc On-Demand Distance Vector (AODV) routing protocols and their functionality in Ad-hoc networks with a discussion being made on their comparison through some analysis and simulation studies using NS2 on these two types of routing protocols and also to become familiar with handling the NS2 environment.

CHAPTER - 2

LITERATURE SURVEY

Laura Marie Feeney, in her paper "A taxonomy of routing protocols in mobile ad-hoc networks", provided a detail overview of a number of MANET routing protocols and also defined a taxonomy that is suitable for examining a wide variety of protocols in a structured way and exploring tradeoffs associated with various design choices. [1]

Elizabeth M. Royer and C.K. Toh, in their paper "A review of current routing protocols for Ad-Hoc Mobile Wireless Networks", has provided descriptions of several routing schemes proposed for Mobile Ad-hoc Networks. They have also provided a classification of these routing schemes according to the routing strategy (i.e., table-driven and on-demand) and have presented a comparison of these two categories of routing protocols. [2]

Mehran Abolhasan, Tadeusz A. Wysocki, Eryk Dutkiewicz, in their paper "A review of routing protocols for mobile ad-hoc networks", three categories of routing protocols where introduced. They also state that the global routing protocols, which derived mainly from the traditional link state or distance vector algorithm, maintain network connectivity proactively, and the on-demand routing protocols determined routes when they are needed. And also they state that the hybrid routing protocols employ both reactive and proactive properties by maintaining intra-zone information proactively and inter-zone information reactively. [3]

Improvement of certain other routing protocols has also been proposed, as in "An Improved Routing Protocol in Mobile Ad Hoc Networks" of Ting Liu and Kai Liu where they also proposed a novel routing protocol to improve the performance of Destination Sequenced Distance Vector (DSDV) routing protocol in mobile ad-hoc networks with high mobility. [4]

Charles E. Perkins and Pravin Bhagwat, in their paper "Highly dynamic Destination Sequenced Distance Vector routing DSDV for mobile computers", presented an algorithm, DSDV where the mobile nodes operates as routers which periodically advertises their view of the interconnection topology with other mobile nodes within the network. [5]

Perkins C.E and Royer E.M, in their paper "Ad-hoc on-demand distance vector routing", presented a distance vector algorithm, AODV that is suitable for use in Ad-hoc networks. And they concluded that AODV as compared to other Ad-hoc networks algorithms has longer latency for route establishment. [6]

In the paper "Optimizing Routing Protocols for Ad Hoc Network" of Saurabh Rastogi, evaluated some of the existing routing protocols such as dynamic source routing (DSR), ad hoc on-demand distance vector routing (AODV), destination-sequenced distance-vector (DSDV) and proposed a new protocol. In the paper he also compares the performance of existing two prominent on-demand reactive routing protocols for mobile ad hoc networks: DSR and AODV, along with the traditional proactive DSDV protocol. The performance differentials for the existing ones were analyzed using varying network load, mobility, throughput in data delivery and network size. These simulations were carried out based on the Rice Monarch Project that has made substantial extensions to the NS-2 network simulator to run ad-hoc simulations. [8]

Anurag Malik, Shivanshu Rastogi and Sajendra Kumar, in their paper "Performance Analysis of Routing Protocol in Mobile Ad Hoc Network using NS-2", examined the simulation studies and compared the on-demand (DSR and AODV) and table driven (DSDV) routing protocols by varying the pause time. And the results were obtained for the metrics: end to end delay, dropped packets, routing overhead and power efficiency and they observed that the performance of on-demand protocols were superior to the table driven protocol. [9]

Samyak Shah, Amit Khandre, Mahesh Shirole and Girish Bhole, in their paper "Performance Evaluation of Ad Hoc Routing Protocols Using NS2 Simulation", have compared the performance of two prominent on-demand reactive routing protocols for mobile ad-hoc network: DSR and AODV, along with the traditional proactive DSDV protocol. [10]

I.Vijaya and Pinak Bhusan Mishra, in their paper "Influence of Routing Protocols in Performance of Wireless Mobile Ad-hoc Network", has compared the performance of two prominent on-demand reactive routing protocols for mobile ad-hoc network: DSR and AODV, along with the traditional proactive DSDV protocol using NS-2 simulator. They observed that the on-demand protocols, DSR and AODV perform better than the table driven protocol, DSDV. The results were obtained for the metrics: throughput, delivery ratio and end to end delay. [11]

V.Ramesh, Dr.P.Subbaiah, N. Koteswar Rao and M.Janardhana Raju, in their paper "Performance Comparison and Analysis of DSDV and AODV for MANET", examined two routing protocols for mobile ad-hoc networks - the Destination Sequenced Distance Vector (DSDV), the table- driven protocol and the Ad hoc On-Demand Distance Vector routing (AODV), an On-Demand protocol and evaluated both protocols based on packet delivery fraction and average delay while varying number of sources and pause time. And they concluded that the AODV protocol is the ideal choice for communication when the communication has to happen under the UDP protocol as the base. [12]

Samir M. Said, Ibrahiem M. M. El Emary and Shatha Kadim, in their paper "Comparative study between the performance of proactive and reactive mobile ad-hoc networks (MANET) routing protocols with varying mobility", performance evaluation of both proactive wireless routing protocol, Destination Sequenced Distance Vector (DSDV) and reactive protocols, Ad-hoc On Demand Distance Vector (AODV) with continuous bit rate (CBR) traffic was executed using NS-2 simulator. The performance differentials were analyzed with varying network load and mobility. And they concluded that the routing protocols AODV gives less fluctuation results and better performance as compare with DSDV, with respect to some identified parameters of routing protocol such as, routing over head, throughput and average end to end delay. [13]

A.F.A. Abidin, N.S.M. Usop and M.K. Yusof, in their paper "Performance Comparison of Wireless Ad Hoc Routing Protocols", compared the performance of two prominent on-demand reactive routing protocols for mobile ad hoc networks: Dynamic Source Routing (DSR) and Ad Hoc On-Demand Distance Vector Routing (AODV), along with the traditional Proactive Destination-Sequenced Distance-Vector (DSDV) protocol. They concluded that the on-demand protocols, AODV and DSR perform better than the table-driven DSDV protocol. The performance differentials were analyzed using varying network load, mobility and network size. [14]

Abdul Hadi Abd Rahman and Zuriati Ahmad Zukarnain, in their paper "Performance Comparison of AODV, DSDV and I-DSDV Routing Protocols in Mobile Ad Hoc Networks", three protocols AODV, DSDV and I-DSDV were simulated using NS-2 package and were compared in terms of packet delivery ratio, end to end delay and routing overhead in different environment; varying number of nodes, speed and pause time. They found that I-DSDV were better than DSDV but not from AODV. [15]

Sapna S. Kaushik and P.R.Deshmukh, in their paper "Comparison of effectiveness of AODV, DSDV and DSR routing protocols in Mobile Ad-hoc Networks", did the realistic comparison of three routing protocols DSDV, AODV and DSR. They concluded that reactive routing protocol AODV performance is the best considering its ability to maintain connection by periodic exchange of information, which is required for TCP, based traffic. [16]

A.E. Mahmoud, R. Khalaf & A, Kayssi, in their paper "Performance Comparison of the AODV and DSDV Routing Protocols in Mobile Ad-Hoc Networks", the performance of routing protocols, DSDV, I-DSDV and AODV were measured with respect to metrics like Packet Delivery Fraction, End to End Delay and Routing Overhead in three different scenarios: pause time, no of node and node speed. It was concluded that I-DSDV improved the PDF and E2E delay when the node is high (link breakage occurred) but still perform lower performance compared to AODV. [17]

J. Broch, D. A. Maltz, D. B. Johnson, Y-C. Hu, and J Jetcheva, in their paper "A performance comparison of multi-hop wireless ad hoc network routing protocols", have compared the DSDV, TORA, DSR and AODV protocols using ns-2 simulator. The simulation was done with 50 nods with varying pause times. The results were obtained for the metrics: Packet delivery ratio, routing overhead, number of hops taken by the packets to reach the destination. [18]

Samir R. Das, R. Castaneda, J. Yan, and R. Sengupta, in their paper "Comparative performance evaluation of routing protocols for mobile ad hoc networks", evaluated the performance of routing protocols with respect to fraction of packets delivered, end-to-end delay, and routing load by varying the number of conversation per node. The evaluation was done with 30 and 60 nodes using Maryland Routing Simulator. The protocols used in the simulation are SPF, DSDV, TORA, DSR, and AODV. [19]

Samir R. Das, Charles E. Perkins and E.E. Royer, in their paper "Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks", evaluated the DSR and AODV on-demand routing protocols with three performance metrics: Packet delivery fraction, average end-to-end delay and normalized routing load with varying pause times. They have used ns-2 simulator. Based on the observations, recommendations were made as to how the performance of either protocol can be improved. [20]

Jyoti Raju and Garcia-Luna-Aceves, in their paper "A comparison of on-demand and table driven routing for ad-hoc wireless networks", have compared WRP-Lite a revised version of wireless routing protocol with DSR. The performance parameters used are end-to-end delay, control overhead, percentage of packets delivered and hop distribution. The evaluation of the performance metrics was done with respect to varying pause time. It was observed that WRP-lite has much better delay and hop performance while having comparable overhead to DSR. [21]

Azzedine Boukerche, in his paper "Performance comparison and analysis of ad hoc routing algorithms", has done the performance comparison of AODV, CBRP and DSR ad-hoc routing protocols using ns-2 simulator. The key performance metrics evaluated in his experiments are throughput, average end-to-end delay of data packets and normalized routing overhead for different data sources and varying pause times of mobile nodes. As per his observation DSR and CBRP has high throughput than in comparison with AODV. CBRP has high routing overhead than DSR. [22]

CHAPTER - 3

MOBILE AD-HOC NETWORKS (MANETs)

3.1. INTRODUCTION TO MANET

An ad-hoc network is a collection of wireless mobile nodes forming a temporary network without depending on any infrastructure or centralized administration. Mobile ad-hoc networks as shown in Fig. 3.1 are self-organizing and self-configuring multihop wireless networks where, the structure and topology of the network changes dynamically. This is mainly due to the mobility of the nodes. The nodes in the network, not only acts as hosts but also as routers that route data to/from other nodes in the network. Mobility and the absence of any fixed existing infrastructure make MANET very attractive for many applications.

MN - Mobile Node

MN4

MN2

MN1

MN3

MN5

MN7[5] NS-2, The ns Manual (formally known as NS Documentation) available at http://www. isi.edu/nsnam/ns/doc.

MN6

Fig. 3.1. Mobile Ad-hoc Network

3.2. CHARACTERISTICS OF MANETS

(i) Dynamic topology: Topology of Mobile Ad-hoc Network changes rapidly and randomly consisting of both bidirectional and unidirectional links.

(ii) Constrained in bandwidth used: The capacity of wireless networks is lesser than the hardwired systems. Considering the problems like multiple access, fading, noise and interference conditions, etc., the throughput of wireless networks is always much less than a radio's maximum transmission rate.

(iii) Constrained of energy: As all MANET nodes are mobile, they depend on exhaustible means for their energy like battery, so energy-conservation should be taken into care.

(iv) Limited security: Wireless systems are less secure than the hardwired ones. The possibility of attacks such as eavesdropping, spoofing and denial-of-service should be considered.

(v) Mobility: Nodes are mobile so they rapidly move in ad-hoc networks. And nodes mobility has major effect on the selection of a routing protocol and can thus affect the performance.

(vi) Multihopping: A multihop network is a network where the path from source to destination traverses several other nodes. Ad-hoc networks are multihop networks.

(vii) Self-organization: Ad-hoc networks automatically determine its own configuration parameters such as: addressing, routing, clustering, position identification, power control, etc. In some cases, nodes can coordinate their motion and dynamically distribute in the geographic area to provide coverage of disconnected islands.

(viii) Connection to internet: There is merit in extending the infrastructure wireless networks with infrastructure less ad-hoc networks. For example, the wireless LAN that is used for domestic networks can be extended to reach as needed (to the garage, the car park in the street, the neighbor's home, etc) with portable routers.

3.3. ADVANTAGES OF MANETS

They provide access to information and services regardless of geographic position.

These networks can be set up at any place and time.

They can be more economical in some cases, as they eliminate fixed infrastructure costs and reduce power consumption at mobile nodes.

They can be more flexible than conventional wireless networks because of their non-hierarchical distributed control and management mechanisms.

As Ad-hoc networks support multihopping, communication beyond the Line of Sight (LOS) is possible at high frequencies.

Multi-hop ad-hoc networks can reduce the power consumption of wireless devices this is because more transmission power is required for sending a signal over any distance in one long hop than in multiple shorter hops.

Because of short communication links, radio emission levels can be kept low. This reduces interference levels, increases spectrum reuse efficiency and makes it possible to use unlicensed unregulated frequency bands.

3.4. DISADVANTAGES OF MANETS

Limited resources and physical security.

Dynamic network topology makes it hard to detect malicious nodes.

Security protocols used for wired networks cannot work for ad-hoc networks.

3.5. APPLICATIONS OF MANETS

(i) In Military: Nowadays military equipment contains some sort of computer equipment. Ad-hoc networking would allow the military to take advantage of common place network technology which can be built up anywhere to maintain an information network between the soldiers, vehicles and military information head quarters. The basic techniques of ad-hoc network came from this field.

(ii) In Commercial sector: Ad-hoc network can be used in emergency/rescue operations for disaster relief efforts, e.g. in fire, flood or earthquake. Emergency rescue operations must take place where non-existing or damaged communications infrastructure and rapid deployment of a communication network is needed. Information is transfer from one rescue team member to another over a small effort. Other commercial scenarios include e.g. ship-to-ship ad-hoc mobile communication, law enforcement, etc.

(iii) In Local level: Ad-hoc networks can independently link an instant and temporary multi-media network using notebook computers or palmtop computers to spread and share information among participants at a conference or classroom. Another local level application might be in home networks where devices can communicate directly to exchange information. Similarly, in other local level environments like taxicab, sports stadium, boat and small aircraft, mobile ad-hoc communications will have many applications.

(iv) In Personal Area Network (PAN): MANET having short range can simplify the inter-communication between various mobile devices. Physical wired cables are replaced with wireless connections. Such an ad-hoc network can also extend the access to the internet or other networks. The PAN is an important and promising application field of MANET in the future.

CHAPTER - 4

ROUTING IN MANETS

4.1. INTRODUCTION TO ROUTING IN MANETS

In mobile ad-hoc networks where the nodes are mobile and it does not depend on any existing infrastructure as in the case with wireless networks and since a destination node might be out of range of a source node transmitting packets; a routing protocol is always needed to find a path between the source and the destination which can be use for the transmission purpose. So, in ad-hoc networks, each node must be able to forward data for other nodes. Again, the highly dynamic nature of a mobile ad-hoc network results, changes of network topology, adding complexity to routing. The challenges and complexities, together with the importance of routing protocol in establishing communications among nodes, make routing area the most important and active research area within the MANET domain.

4.2. CLASSIFICATION OF ROUTING PROTOCOLS IN MANETS

Ad-hoc routing protocols

Flat routing Hierarchical routing Geographic position

assisted routing

Proactive Reactive

(table-driven) (on-demand)

FSR FSLS OLSR TBRPF AODV DSR HSR GCSR ZRP LANMAR GeoCAST LAR DREAM GPSR

Classification of routing protocols in MANETs can be done in many ways, but most of these are done depending on network strategy and network structure. According to the routing strategy routing protocols can be classified as table-driven and source initiated, while depending on the network structure these are classified as flat routing hierarchical routing and geographic position assisted routing. Both the table-driven and source initiated protocols come under flat routing.

Fig.4. 1. Classification of Routing Protocols in Mobile Ad-hoc Networks

4.2.1. TABLE-DRIVEN ROUTING PROTOCOLS (PROACTIVE)

These protocols are also called as proactive protocols since they maintained routing information even before it is needed. Each and every node in the network maintains routing information to every other node in the network. Routes information is generally kept in the routing tables and is periodically updated as the network topology changes. Many of these routing protocols come from the link state routing. There exist some differences between the protocols that come under this category depending on the routing information being updated in each routing table. Furthermore, these routing protocols maintain different number of routing tables. The proactive protocols are not suitable for larger networks, as they need to maintain node entries for each and every node in the routing table of every node. This causes more overhead in the routing table result in consumption of more bandwidth. Representative proactive protocols are - Destination-Sequenced Distance-Vector (DSDV), Optimized Link State Routing (OLSR) and Topology Dissemination Based on Reverse-path Forwarding (TBRPF).

4.2.2. ON DEMAND ROUTING PROTOCOLS (REACTIVE)

These protocols are also called reactive protocols since they don't maintain routing information or routing activity at the network nodes if there is no communication. If a node wants to send a packet to another node then this protocol searches for the route in an on-demand manner and establishes the connection in order to transmit and receive the packet. The route discovery usually occurs by flooding the route request packets throughout the network. The obvious advantage with discovering routes on-demand is to avoid incurring the cost of maintaining routes that are not used. This approach is attractive when the network traffic is sporadic, burst and directed mostly toward a small subset of nodes. However, since routes are created when the need arises, data packets experience queuing delays at the source while the route is being found at session initiation and when route is being repaired later on after a failure. Representative reactive routing protocols include: Dynamic Source Routing (DSR), Ad-hoc On-Demand Distance Vector (AODV), Temporally Ordered Routine Algorithm (TORA), Associativity Based Routing (ABR), Signal Stability Routing (SSR).

4.3. PROBLEMS WITH ROUTING IN MANETS

(i) Asymmetric links: In ad-hoc networks, as the nodes are mobile and constantly change their position in the network, they do not have symmetric links so there is always a problem while routing. For example consider a MANET where node B sends a signal to node A but this does not tell anything about the quality of the connection in the reverse direction.

(ii) Routing overhead: In wireless ad-hoc network nodes often change their location within network. So, some stall routes are generated in the routing table which leads to unnecessary routing overhead.

(iii) Interference: In MANETs as links come and go depending on the transmission characteristics, one transmission might interfere with another one and node might overhear transmission of other nodes and can corrupt the total transmission.

(iv)Dynamic topology: This is another major problem with ad-hoc routing since the topology is not constant. The mobile nodes might move or medium characteristics might change. In ad-hoc networks, routing tables must somehow reflect these changes in topology and routing algorithms have to be adapted.

4.4. FACTORS TO BE CONSIDERED WHILE CHOOSING A PROTOCOL FOR MANETs

(i) Multicasting: This is the ability to send packets to multiple nodes at once. This is similar to broadcasting except the fact that broadcasting is done to all the nodes in the network. This is important as it takes less time to transfer data to multiple nodes.

(ii) Loop free: A path taken by a packet never transits the same intermediate node twice before it arrives at the destination. In order to improve the overall performance, the routing protocol should guarantee that the routes provided are loop free. This avoids any waste of bandwidth or CPU consumption.

(iii) Multiple routes: If one route gets broken due to some disaster, then the data could be sent through some other route. Thus, the protocol should allow creating multiple routes.

(iv) Distributed operation: The protocol should be distributed. It should not be dependent on a centralized node.

(v) Reactive: It means that the routes are discovered between a source and a destination only when needed to send a message. Some protocols are reactive while others are proactive which means that the route is discovered to various nodes without waiting for the need.

(vi) Unidirectional link support: The radio environment can cause the formation of unidirectional links. Utilization of these links and not only the bi-directional links improves the routing protocol performance.

(vii) Power conservation: The nodes in an ad-hoc network can be laptops and other mobile devices, such as PDAs that depends on battery power which is limited and therefore use some sort of stand-by mode to save power. It is therefore important that the routing protocol has support for these sleep modes.

(viii) Security: Wireless networking environments have strong possibilities of attacks. In order to ensure the behavior of the routing protocols, security measures like authentication and encryption through the distribution of keys among the nodes in ad-hoc network is challenging.

(ix) Quality of Service support: It is a set of service requirements that needs to be met by the network while transporting a packet stream from a source to its destination. Its needs are governed by the service requirements of end user applications and expected to guarantee a set of measurable pre-specified service attributes to the user in terms of end-to-end performance, such as delay, bandwidth, probability of packet loss, delay variance (jitter), etc. Power consumption is another QoS attribute which is more specific to MANETs.

CHAPTER - 5

DESTINATION SEQUENCED DISTANCE VECTOR

(DSDV) PROTOCOL

5.1. INTRODUCTION TO DSDV PROTOCOL

The Destination Sequenced Distance Vector routing protocol is a routing protocol used mainly for Mobile Ad-hoc Networks and is a proactive routing protocol which is a modification of conventional Bellman Ford routing algorithm. It is adapted from the conventional Routing Information Protocol (RIP) and has the only difference of having a new attribute that is the sequence number entry in the routing table at each node of the conventional RIP. Routing table is maintained at each node that lists all available destinations, the number of hops to reach the destination and the sequence number assigned by the destination node and with the help of this table, communication between nodes in the network take place. The sequence number is used to distinguish stale routes from new ones and thus avoids the formation of loops.

5.2. OVERVIEW OF DSDV PROTOCOL

Each node in the network maintains routing table for the transmission of the packets and also for the connectivity to different stations in the network. These stations list for all the available destinations and the number of hops required to reach each destination in the routing table. The routing entry is tagged with a sequence number which is generated by the destination station. In order to maintain the consistency, each station transmits and updates its routing table periodically. The packet being broadcasted between stations show which stations are accessible and how many hops are required to reach that particular station. The packets that are transmitted may contain the layer 2 or layer 3 addresses.

The advertisement of routing information can be taking place by broadcasting or multicasting the packets which are transmitted periodically as when the nodes move within the network. Data is also kept about the length of time between arrival of the first and the arrival of the best route for each particular destination. Based on this data, a decision may be made to delay advertising routes which are about to change soon, thus fluctuations of the route tables. The advertisement of routes which may not have stabilized yet is delayed in order to reduce the number of rebroadcasts of possible route entries that normally arrive with the same sequence number.

The DSDV protocol requires that each mobile node in the network must periodically advertise its own routing table to each neighboring nodes. The data broadcast by each node will contain its new sequence number and the following information for each new route; the destination address, the number of hops required to reach the destination and the new sequence number, originally assigned by the destination. The transmitted routing tables will also contain the hardware address, network address of the mobile node transmitting them. The routing table will contain the sequence number created by the transmitter and hence the most new destination sequence number is preferred as the basis for making forwarding decisions. This new sequence number is also updated to all the hosts in the network which may decide on how to maintain the routing entry for that originating mobile host.

The receiving node increments the metric after receiving the routing information and transmits information by broadcasting. Incrementing metric is done before transmission because, incoming packets will have to travel one more hop to reach its destination.

Time between broadcasting the routing information packets is the other important factor to be considered. When the mobile node received new routing information it will be retransmitted soon effecting the most rapid possible dissemination of routing information among all the cooperating mobile nodes. Mobile node cause broken links as they move from place to place within the network and this broken link may be detected by the layer2 protocol, which may be described as 'infinity'. When the route is broken in a network, then immediately that metric is assigned an infinity metric there by determining that there is no hop and the sequence number is updated. Sequence numbers originating from the mobile nodes are defined to be even number and the sequence numbers generated to indicate infinity metrics are odd numbers.

In the DSDV protocol there is two ways of broadcasting routing information namely: full dump and incremental dump. Full dump broadcasting will carry all the routing information that is the entire routing table while the incremental dump will carry only the changed information since last full dump. Irrespective of the two types, broadcasting is done in Network Protocol Date Unit (NPDU). Incremental dump requires only one NPDU to fit in all the information while full dump requires multiple NPDU. When no movement of mobile hosts is occurring full dump can be transmitted relatively infrequently. When movement becomes frequent and the size of an incremental dump approaches the size of a NPDU, then full dump can be scheduled.

When a node received an information packet from another node, it compares the sequence number with the available sequence number for that entry. If the sequence number in the incoming packet is larger, then it will update the routing information with the new sequence number else if the information arrives with the same sequence number it checks for the metric entry and if the number of hop in the incoming packet is less than the previous entry the new information is updated and lastly if information is same or metric is more then it will discard the information. When the node information is being updated the metric is increased by 1 and the sequence number is also increased by 2. Similarly, if a new node enters the network, it will announce itself in the network and the nodes in the network update their routing information with a new entry for the new node.

5.3. AN EXAMPLE OPERATION OF DSDV

MH5

MH4

MH3

MH8

MH6

MH2

MH1

MH7

MH1

Fig. 5.1. Movement of Mobile host in Ad-hoc Networks [4]

Consider Fig. 5.1 where there are 8 nodes in the network. This example shows what happen to the routing table of node MH4 when node MH1 move from node MH2 to node MH4. Here, let the address of each mobile node be denoted by MHi. Further supposed that all sequence numbers are denoted by SNNN_MHi, where MHi specifies the node that created the sequence number and SNNN is a sequence number value. And TNNN_MHi specifies the install time for mobile host MHi with TNNN the install time value.

Initially, all the nodes advertise their routing information to all the nodes in the network and hence, the routing table at MH4 initially looks like:

TABLE 5.1

ROUTING TABLE OF MH4

Destination

Next Hop

Metric

Sequence

Number

Install

Stable_Data

MH1

MH2

MH3

MH4

MH5

MH6

MH7

MH8

MH2

MH2

MH2

MH4

MH6

MH6

MH6

MH6

2

1

2

0

2

1

2

3

S406_MH1

S128_MH2

S564_MH3

S710_MH4

S392_MH5

S076_MH6

S128_MH7

S050_MH8

T001_MH4

T001_MH4

T001_MH4

T001_MH4

T002_MH4

T001_MH4

T002_MH4

T002_MH4

Ptr1_MH1

Ptr1_MH2

Ptr1_MH3

Ptr1_MH4

Ptr1_MH5

Ptr1_MH6

Ptr1_MH7

Ptr1_MH8

From table 5.1, one could say that all the computers became available to MH4 at about the same time, since its install-time for most of them is about the same. And one could also notice that none of the links between computers were broken, because all of the sequence number fields have times with even digits in the units place.

And the forwarding table at the MH4 would look like:

TABLE 5.2

FORWARDING TABLE AT MH4

Destination

Metric

Sequence

Number

MH1

MH2

MH3

MH4

MH5

MH6

MH7

MH8

2

1

2

0

2

1

2

3

S406_MH1

S128_MH2

S564_MH3

S710_MH4

S392_MH5

S076_MH6

S128_MH7

S050_MH8

But, when the node MH1 moves as shown in Fig. 5.1 nearer to node MH7 and node MH8 then, the link between node MH2 and node MH1 will be broken resulting in the assignment of infinity metric at node MH2 for node MH1 and the sequence number will be change to odd number in the routing table at node MH2. Node MH2 will update this routing information and will broadcast it to its neighbor nodes. And on the other side, as there is a new neighbor node for node MH7 and node MH8; they update their information in the routing tables and they broadcast. Now, node MH4 will receive its updated information from node MH6 where node MH6 will receive two information packets from different neighbors to reach node MH1 with same sequence number, but different metric. The selection of the route will depend on less hop count as the sequence number is the same.

This will result in some changes to the routing table of node MH4 and these changes are done according to the updated information that node MH4 got from node MH6.

Now the routing table will look like:

TABLE 5.3

ROUTING TABLE AFTER MH1 MOVEMENT

Destination

Next Hop

Metric

Sequence

Number

Install

Stable_Data

MH1

MH2

MH3

MH4

MH5

MH6

MH7

MH8

MH6

MH2

MH2

MH4

MH6

MH6

MH6

MH6

3

1

2

0

2

1

2

3

S516_MH1

S238_MH2

S674_MH3

S820_MH4

S502_MH5

S186_MH6

S238_MH7

S160_MH8

T001_MH4

T001_MH4

T001_MH4

T001_MH4

T002_MH4

T001_MH4

T002_MH4

T002_MH4

Ptr1_MH1

Ptr1_MH2

Ptr1_MH3

Ptr1_MH4

Ptr1_MH5

Ptr1_MH6

Ptr1_MH7

Ptr1_MH8

And the forwarding table will look like:

TABLE 5.4

FORWARDING TABLE AT MH4 AFTER MOVEMENT OF MH1

Destination

Metric

Sequence

Number

MH1

MH2

MH3

MH4

MH5

MH6

MH7

MH8

3

1

2

0

2

1

2

3

S516_MH1

S238_MH2

S674_MH3

S820_MH4

S502_MH5

S186_MH6

S238_MH7

S160_MH8

In this example, one node has changed its routing information, since it is in a new location. All nodes have transmitted new sequence numbers recently. If there were too many updated sequence numbers to fit in a single packet, only the one which fit will be transmitted. These would be selected with a view to fairly transmitting them in their turn over several incremental update intervals. There is no such required format for the transmission of full routing information packets. As many packets are used as are needed and all available information is transmitted. The frequency of transmitting full updates would be reduced if the volume of data began to consume a significant fraction of the available capacity of the medium.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.