A Performance Comparison of Multi-Hop Wireless Ad Hoc Network routing protocols Josh Broch David A Maltz David B. Johnson Yih-Chun Hu Jorjeta Jetcheva Computer Science Departme Carnegie mellon University urgh, PA 15213 http://www.monarch.cs.cmuedu Abstract Many different protocols have been proposed to solve the An ad hoc network is a collection of wireless mobile nodes dynamically hop routing problem in ad hoc networks, each based on forming a temporary network without the use of any existing network infras. assumptions and intuitions. However, little is known about the tructure or centralized administration. Due to the limited transmission range performance of these protocols, and no attempt has previously been of wireless network interfaces, multiple network "hops"may be needed fo ade to directly compare them in a realistic ma one node to exchange data with another across the network. In recent years, This paper is the first to provide a realistic, quantitative analy a variety of new routing protocols targeted specifically at this environment comparing the performance of a variety of multi-hop wireless ad hoc have been developed, but little performance information on each protocol network routing protocols. We present results of detailed simulations and no realistic performance comparison between them is available. This showing the relative performance of four recently proposed ad hoc per presents the results of a detailed packet-level simulation comparin routing protocols: DSDV [18], TORA [14, 15], DSR [9, 10, 21, and four multi-hop wireless ad hoc network routing protocols that cover a range AODV [17]. To enable these simulations, we extended the ns-2 of design choices: DSDV, TORA, DSR, and AoDv. We have extended network simulator [6]to include the ns-2 network simulator to accurately model the MAc and physical-layer navior of the IEEE 802. 11 wireless Lan standard, including a realistic ireless transmission channel model, and present the results of simulations A realistic physical layer including a radio propagation model of networks of 50 mobile nodes supporting propagation delay, capture effects, and carrier sense[20] 1 Introduction Radio network interfaces with properties such as transmission power, antenna gain, and receiver sensitivity In areas in which there is little or no communication infrastructure The IEEE802. 1/ Medium Access Control (MAC) protocol using existing infrastructure is expensive or inconvenient to use, the Distributed Coordination Function (DCF)[8 nobile users may still be able to communicate through the formation of an ad hoc network. In such a network. each mobile node n simulations operates not only as a host but also as a router, forwarding packets an ad hoc routing protocol that allows it to discover"multi-hop" paths 2 Simulation environment is sometimes also called infrastructureless networking [13], since the ns is a discrete event simulator developed by the University of themselves to form their own network"on the fiy. Some examples of substantial support for simulating TCP and other protocols over con- the possible uses of ad hoc networking include students using laptop ventional networks, it provides no support for accurately simulating computers to participate in an interactive lecture, business associates the physical aspects of multi-hop wireless networks or the mac pro- sharing information during a meeting, soldiers relaying information tocols needed in such environments. Berkeley has recently released for situational awareness on the battlefield [12, 21], and emergency ns code that provides some support for modeling wireless LANs, but disaster relief personnel coordinating efforts after a hurricane or this code cannot be used for studying multi-hop ad hoc networks as it does not support the notion of node position; there is no spatial diversity (all nodes are in the same collision domain), and it can only odel dire onnected nod (AFMC) under In this section, we describe some of the modifications we made to contract number F19628-96-C-0061, and by the is to allow accurate simulation of mobile wireless networks IBM Cooperative Fellowship, and Yih-Chun Hu was also supported by an 2.1 Physical and Data Link Layer Model representing the official policies or To accurately model the attenuation of radio waves between anten- endorsements, either express or implied, ofNSF, AFMC, DARPA, the AT&T Foundation, nas close to the ground, radio engineers typically use a model that M, Carnegie Mellon University, or the U.S. Government. attenuates the power of a signal as 1/ at short distances(ris the distance between the antennas), and as 1/r at longer distances The crossover point is called the reference distance, and is typically around 100 meters for outdoor low-gain antennas 1. 5m above the ground plane operating in the 1-2GHz band [20]. Following this Conference on Mobile Computing and Networking(MobiCom 98) practice, our signal propagation model combines both a free space October 25-30, 1998, Dallas, Texas, USA. Copyright 1998 ACM propagation model and a two-ray ground reflection model. When a transmitter is within the reference distance of the receiver, we
A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols Josh Broch David A. Maltz David B. Johnson Yih-Chun Hu Jorjeta Jetcheva Computer Science Department Carnegie Mellon University Pittsburgh, PA 15213 http://www.monarch.cs.cmu.edu/ Abstract An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. Due to the limited transmission range of wireless network interfaces, multiple network "hops" may be needed for one node to exchange data with another across the network. In recent years, a variety of new routing protocols targeted specifically at this environment have been developed, but little performance information on each protocol and no realistic performance comparison between them is available. This paper presents the results of a detailed packet-level simulation comparing four multi-hop wireless ad hoc network routing protocols that cover a range of design choices: DSDV, TORA, DSR, and AODV. We have extended the ns-2 network simulator to accurately model the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, including a realistic wireless transmission channel model, and present the results of simulations of networks of 50 mobile nodes. 1 Introduction In areas in which there is little or no communication infrastructure or the existing infrastructure is expensive or inconvenient to use, wireless mobile users may still be able to communicate through the formation of an ad hoc network. In such a network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other. Each node participates in an ad hoc routing protocol that allows it to discover “multi-hop” paths through the network to any other node. The idea of ad hoc networking is sometimes also called infrastructureless networking [13], since the mobile nodes in the network dynamically establish routing among themselves to form their own network “on the fly.” Some examples of the possible uses of ad hoc networking include students using laptop computers to participate in an interactive lecture, business associates sharing information during a meeting, soldiers relaying information for situational awareness on the battlefield [12, 21], and emergency disaster relief personnel coordinating efforts after a hurricane or earthquake. This work was supported in part by the National Science Foundation (NSF) under CAREER Award NCR-9502725, by the Air Force Materiel Command (AFMC) under DARPA contract number F19628-96-C-0061, and by the AT&T Foundation under a Special Purpose Grant in Science and Engineering. David Maltz was also supported under an IBM Cooperative Fellowship, and Yih-Chun Hu was also supported by an NSF Graduate Fellowship. The views and conclusions contained here are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either express or implied, of NSF, AFMC, DARPA, the AT&T Foundation, IBM, Carnegie Mellon University, or the U.S. Government. To appear in Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom’98), October 25–30, 1998, Dallas, Texas, USA. Copyright © 1998 ACM. Many different protocols have been proposed to solve the multihop routing problem in ad hoc networks, each based on different assumptions and intuitions. However, little is known about the actual performance of these protocols, and no attempt has previously been made to directly compare them in a realistic manner. This paper is the first to provide a realistic, quantitative analysis comparing the performance of a variety of multi-hop wireless ad hoc network routing protocols. We present results of detailed simulations showing the relative performance of four recently proposed ad hoc routing protocols: DSDV [18], TORA [14, 15], DSR [9, 10, 2], and AODV [17]. To enable these simulations, we extended the ns-2 network simulator [6] to include: Node mobility. A realistic physical layer including a radio propagation model supporting propagation delay, capture effects, and carrier sense [20]. Radio network interfaces with properties such as transmission power, antenna gain, and receiver sensitivity. The IEEE 802.11 Medium Access Control (MAC) protocol using the Distributed Coordination Function (DCF) [8]. Our results in this paper are based on simulations of an ad hoc network of 50 wireless mobile nodes moving about and communicating with each other. We analyze the performance of each protocol and explain the design choices that account for their performance. 2 Simulation Environment ns is a discrete event simulator developed by the University of California at Berkeley and the VINT project [6]. While it provides substantial support for simulating TCP and other protocols over conventional networks, it provides no support for accurately simulating the physical aspects of multi-hop wireless networks or the MAC protocols needed in such environments. Berkeley has recently released ns code that provides some support for modeling wireless LANs, but this code cannot be used for studying multi-hop ad hoc networks as it does not support the notion of node position; there is no spatial diversity (all nodes are in the same collision domain), and it can only model directly connected nodes. In this section, we describe some of the modifications we made to ns to allow accurate simulation of mobile wireless networks. 2.1 Physical and Data Link Layer Model To accurately model the attenuation of radio waves between antennas close to the ground, radio engineers typically use a model that attenuates the power of a signal as 1r2 at short distances (r is the distance between the antennas), and as 1r4 at longer distances. The crossover point is called the reference distance, and is typically around 100 meters for outdoor low-gain antennas 1.5m above the ground plane operating in the 1–2GHz band [20]. Following this practice, our signal propagation model combines both a free space propagation model and a two-ray ground reflection model. When a transmitter is within the reference distance of the receiver, we use
the free space model where the signal attenuates as 1/r?. Outside of drop-tail fashion. Each on-demand routing protocol (i.e, TORA, this distance, we use the ground reflection model where the signal DSR, or AODV), can buffer separately an additional 50 packets that falls off as 1/r that are awaiting discovery of a route through the network Each mobile node has a position and a velocity and moves around or a flat grid. The position of using either a digital elevation map 3 Ad Hoc Network Routing Protocols Studied on a topography that is specifie In this section, we briefly describe the key features of the dsdv, a function of time, and is used by the radio propagation model to TORA, DSR, and AoDV protocols studied in our simulations. We calculate the propagation delay from one node to another and to also describe the particular parameters that we chose when imple determine the power level of a received signal at each mobile node Each mobile node has one or more wireless network interfaces enting each protocol The protocols were carefully implemented according to their spec- together by a single physical channel. When a network interface ifications published as of April 1998 and based on clarifications of channel object. This object then computes the propagation delay experimentation with them. In particular, during the process of im- plementing each protocol and analyzing the results from early simu- a"packet reception"event for each. This event notifies the receiving lation runs, we discovered some modifications for each protocol that interface that the first bit of a new packet has arrived. At this time. improved its performance. The key improvements to each protoce ne power level at which the packet was received is compared to two are highlighted in the respective protocol descriptions below.We different values: the carrier sense threshold and the receive threshold also made the following improvements to all of the protocols If the power level falls below the carrier sense threshold, the revent synchronization, periodic broadcas and is discarded as noise. If the received power level is above the ent in response to the reception of a broadcast packet were sense threshold but below the receive threshold, the packet is n jittered using a random delay uniformly distributed between 0 as a packet in error before being passed to the mAc layer. Otherwise, and 10 milliseconds he packet is simply handed up to the MAc layer To insure that routing information propagated through the net- Once the MAC layer receives a packet, it checks to insure that its ork in a timely fashion routing packet ng sent were queued receive state is presently"idle. If the receiver is not idle, one of two for transmission at the head of the network interface transmit things can happen. If the power level of the packet already being ueue, whereas all other packets(ARP and data) were inserted received is at least 10 db greater than the received power level of the at the end of the interface transmit queue new packet, we assume capture, discard the new packet, and allow Each of the protocols used link breakage detection feedback the receiving interface to continue with its current receive operation. from the 802 11 MAC layer that indicated when a packet could Otherwise, a collision occurs and both packets are dropp not be forwarded to its next hop, with the exception of DSDV If the MAC layer is idle when an incoming packet is passed up s explained in Section 3. 1.2 from the network interface, it simply computes the transmission time of the packet and schedules a"packet reception complete "event for 3.1 Destination-Sequenced Distance Vector(DSDV) itself. When this event occurs, the MAC layer verifies that the packet DSDV [18] is a hop-by-hop distance vector routing protocol requir is error-free, performs destination address filtering, and passes the ing each node to periodically broadcast routing updates. The key advantage of DSDV over traditional distance vector protocols is that 2.2 Medium Access Control it guarantees loop-freedom. The link layer of our simulator implements the complete IEEE 802.11 3.1.1 Basic Mechanisms standard [8 Medium Access Control (MAC) protocol Distributed Coordination Function(DCF) in order to accurately model the Each DSDV node maintains a routing table listing t the"next hop"for contention of nodes for the wireless medium dcf is similar each reachable destination. DsDV tags each route with a sequence MACA [II] and MACAW [1 and is designed to use both physi- number and considers a route R more favorable than l if r has a cal carrier sense and virtual carrier sense mechanisms to reduce the greater sequence number, or if the two routes have equal sequence probability of collisions due to hidden terminals. The transmission of numbers but R has a lower metric. Each node in the network ad- each unicast packet is preceded by a Request-to-Send/Clear-to-Sene vertises a monotonically increasing even sequence number for itself. (RTS/CTS) exchange that reserves the wireless channel for trans- When a node b decides that its route to a destination d has broken mission of a data packet. Each correctly received unicast packet is 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 followed by an Acknowledgment(ACK to the sender, which retrans- broken(making an odd sequence number). This causes any node mits the packet a limited number of times until this ACK is received A routing packets through B to incorporate the infinite-metric route sense indicate that the medium is clear, but they are not preceded by into its routing table until node a hears a route to D with a higher an RTS/CtS and are not acknowledged by their recipients sequence number. 2.3 Address Resolution 3.1.2 Implementation Decisions We did not use link layer breakage detection from the 802. 11 MAC Unix ims, an implementation of ARP [19], modeled after the BSD protocol in obtaining the DSDv data presented in this paper,because implementation [23], was included in the simulation and used after implementing the protocol both with and without it, we found to resolve IP addresses to link layer addresses. The broadcast nature with the link layer breakage of an ARP REQUEST packet(Section 6.)and the interaction of ArP detection. The reason is that if a neighbor N of a node a detects with on-demand protocols(Section 6. 4)make ARP an importan that its link to A is broken, it will broadcast a triggered route updat detail of the simulation 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 existing Each node has a queue for packets awaiting transmission by the anywhere in the network for A. Each node that hears this update will network interface that holds up to 50 packets and is managed in a record an infinite metric for destination A and will propagate the
the free space model where the signal attenuates as 1r2 . Outside of this distance, we use the ground reflection model where the signal falls off as 1r4 . Each mobile node has a position and a velocity and moves around on a topography that is specified using either a digital elevation map or a flat grid. The position of a mobile node can be calculated as a function of time, and is used by the radio propagation model to calculate the propagation delay from one node to another and to determine the power level of a received signal at each mobile node. Each mobile node has one or more wireless network interfaces, with all interfaces of the same type (on all mobile nodes) linked together by a single physical channel. When a network interface transmits a packet, it passes the packet to the appropriate physical channel object. This object then computes the propagation delay from the sender to every other interface on the channel and schedules a “packet reception” event for each. This event notifies the receiving interface that the first bit of a new packet has arrived. At this time, the power level at which the packet was received is compared to two different values: the carrier sense threshold and the receive threshold. If the power level falls below the carrier sense threshold, the packet is discarded as noise. If the received power level is above the carrier sense threshold but below the receive threshold, the packet is marked as a packet in error before being passed to the MAC layer. Otherwise, the packet is simply handed up to the MAC layer. Once the MAC layer receives a packet, it checks to insure that its receive state is presently “idle.” If the receiver is not idle, one of two things can happen. If the power level of the packet already being received is at least 10 dB greater than the received power level of the new packet, we assume capture, discard the new packet, and allow the receiving interface to continue with its current receive operation. Otherwise, a collision occurs and both packets are dropped. If the MAC layer is idle when an incoming packet is passed up from the network interface, it simply computes the transmission time of the packet and schedules a “packet reception complete” event for itself. When this event occurs, the MAC layer verifies that the packet is error-free, performs destination address filtering, and passes the packet up the protocol stack. 2.2 Medium Access Control The link layer of our simulator implements the complete IEEE 802.11 standard [8] Medium Access Control (MAC) protocol Distributed Coordination Function (DCF) in order to accurately model the contention of nodes for the wireless medium. DCF is similar to MACA [11] and MACAW [1] and is designed to use both physical carrier sense and virtual carrier sense mechanisms to reduce the probability of collisions due to hidden terminals. The transmission of each unicast packet is preceded by a Request-to-Send/Clear-to-Send (RTS/CTS) exchange that reserves the wireless channel for transmission of a data packet. Each correctly received unicast packet is followed by an Acknowledgment (ACK) to the sender, which retransmits the packet a limited number of times until this ACK is received. Broadcast packets are sent only when virtual and physical carrier sense indicate that the medium is clear, but they are not preceded by an RTS/CTS and are not acknowledged by their recipients. 2.3 Address Resolution Since the routing protocols all operate at the network layer using IP addresses, an implementation of ARP [19], modeled after the BSD Unix implementation [23], was included in the simulation and used to resolve IP addresses to link layer addresses. The broadcast nature of an ARP REQUEST packet (Section 6.3) and the interaction of ARP with on-demand protocols (Section 6.4) make ARP an important detail of the simulation. 2.4 Packet Buffering Each node has a queue for packets awaiting transmission by the network interface that holds up to 50 packets and is managed in a drop-tail fashion. Each on-demand routing protocol (i.e., TORA, DSR, or AODV), can buffer separately an additional 50 packets that that are awaiting discovery of a route through the network. 3 Ad Hoc Network Routing Protocols Studied In this section, we briefly describe the key features of the DSDV, TORA, DSR, and AODV protocols studied in our simulations. We also describe the particular parameters that we chose when implementing each protocol. The protocols were carefully implemented according to their specifications published as of April 1998 and based on clarifications of some issues from the designers of each protocol and on our own experimentation with them. In particular, during the process of implementing each protocol and analyzing the results from early simulation runs, we discovered some modifications for each protocol that improved its performance. The key improvements to each protocol are highlighted in the respective protocol descriptions below. We also made the following improvements to all of the protocols: To prevent synchronization, periodic broadcasts and packets sent in response to the reception of a broadcast packet were jittered using a random delay uniformly distributed between 0 and 10 milliseconds. To insure that routing information propagated through the network in a timely fashion, routing packets being sent were queued for transmission at the head of the network interface transmit queue, whereas all other packets (ARP and data) were inserted at the end of the interface transmit queue. Each of the protocols used link breakage detection feedback from the 802.11 MAC layer that indicated when a packet could not be forwarded to its next hop, with the exception of DSDV as explained in Section 3.1.2. 3.1 Destination-Sequenced Distance Vector (DSDV) DSDV [18] 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. 3.1.1 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 favorable than R 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 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. 3.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 paper, 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 neighbor 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 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 2
Table I Constants used in the dsDv-sQ simulation with respect to the destination. As this packet propagates through the network, each node that receives the upDate sets its height to a value greater than the height of the neighbor from which the UPDATE issed before link declared broken was received. This has the effect of creating a series of directed links from the original sender of the quERy to the node that initially generated the UPDATE. When a node discovers that a route to a destination is no longer Maximum packets buffered per node per destination valid, it adjusts its height so that it is a local maximum with respect to its neighbors and transmits an UPDATE packet. If the node has ne information further. This renders node a unreachable from all nodes ighbors of finite height with respect to this destination, then the in the network until a broadcasts a newer sequence number in node instead attempts to discover a new route as described above it learns of the When a node detects a network partition, it generates a CLEAR packet infinite metric being propagated for it, but large numbers of packets that resets routing state and removes invalid routes from the network can be dropped in the meantime. TORA is layered on top of IMEP, the Internet MANET ur implementation uses both full and incremental updates as Encapsulation Protocol [51 which is required to provide reliable, required by the protocol' s description. However, the published de- in-order delivery of all routing control messages from a node to each scription of DsDv [18) is ambiguous about specifying when trig. of its neighbors, plus notification to the routing protocol whenever a of a new sequence number for a destination should cause a triggered IMEP attempts to aggregate many TORA and IMEP control mes. update. We call this approach DSDV-SQ(sequence number). The sages(which IMEP refers to as objects)together into a single packet outed around as new sequence numbers propagate around the broken uence number and a response list of other nodes from which an ACK link and create alternate routes. The second interpretation, which we has not yet been received, and only those nodes AcK the block when call simply DSDV, is that only the receipt of a new metric should receiving it, IMEPretransmits each block with some period, and con- cause a triggered update, and that the receipt of a new sequence num- tinues to retransmit it if needed for some maximum total period,after which time. the link to each unacknowledged node is declared down ber is not sufficiently important to incur the overhead of propagating and TORA is notified. IMEP can also provide network layer address a triggered update le implemented both DSDV-SQ and DSDV and found that while resolution, but we did not use this service, as we used ARP[19] with DSDV-sQ is much more expensive in terms of overhead, it provides all four routing protocols. For link status ser a much better packet delivery ratio in most cases. The second scheme a list of a node's neighbors, each IMEP node periodically transmits (DSDV) is much more conservative in terms of routing overhead, but a BEACON(or"BEACON-equivalent) packet, which is answered by ecause link breakages are not detected as quickly, more data packet each node hearing it with a hello (or "HELLO-equivalent ket are dropped. All of the results in this paper use DSDv-SQ, with th exception of Section 6.2, which compares thi 3.2.2 Implementation Decisions Table I lists the constants used in our DSDv-SQ simulation. IMEP must queue objects for some period of time to allow poss ble aggregation with other objects, but the IMEP specification [ 5] 3.2 Temporally-Ordered Routing Algorithm( TORA) does not define this time period, and we discovered that the overall reversal"algorithm. It is designed to discover routes on demand, value. After significant experimentation, we chose as the best bal- provide multiple routes to a destination, establish routes quickly, ance between packet overhead and routing protocol convergence, to d minimize communication overhead by localizing algorithmic aggregate HELLo and Ack packets for a time uniformly chosen be- reaction to topological changes when possible. Route optimality tween 150 ms and 250 ms, and to not delay tORa routing messages (shortest-path routing) is considered of secondary importance, and for aggregation. The reason for not delaying these messages is that longer routes are often used to avoid the overhead of discovering the ToRa link reversal process creates short-lived routing loops that ewer routes exist from the time that the link-reversal starts until the time that all The actions taken by toRa can be described in terms of water nodes that need to be aware of the reversal receive the corresponding flowing downhill towards a destination node through a network of UPDATE (Section 5. 2). Delaying the transmission of TORa routing tubes that models the routing state of the real network. The tubes messages for aggregation, coupled with any queuing delay at the represent links between nodes in the network, the junctions of tubes network interface, allows these routing loops to last long enough that represent the nodes, and the water in the tubes represents the packets significant numbers of data packets are dropped flowing towards the destination. Each node has a height with respect The TORA and IMEP specifications [15, 5] do not define the pre- to the destination that is computed by the routing protocol. If a tube cise semantics of reliable object delivery required by TORA,but longer flow through it, the height of A is set to a height greater than vided in order to prevent the creation of long-lived routing loops that of any of its remaining neighbors, such that water will now fle ular, all toRa objects must be delivered reliably and in back out of A(and towards the other nodes that had been routing order, without any duplication. Additionally, all neighboring nodes packets to the destination via A in the ad hoc network must have a consistent picture of the network 3.2./ Basic mechanisms with regard to each destination. This implies that anytime a node a decides its link to a neighbor b has gone down, B must also decide At each node in the network, a logically separate copy of TORA is that the link to a has gone down In for each destination. When a node needs a route to a particular We have implemented IMEP to provide this functional the destination for which it requires a route. This packet propagates specified by IMEP [5]. We chose a retransmission period of t hot destination, it broadcasts a qUERY packet containing the address of the retransmission timeout and total number of attem through the network until it reaches either the destination, or an and a total timeout of 1500 ms, although based up observations intermediate node having a route to the destination. The recipient an adaptive retransmission timer should be added to the protocol. In- of the query then broadcasts an UPDATE packet listing its height order delivery is enforced by, at each receiver node b, only passin
Table I Constants used in the DSDV-SQ simulation. Periodic route update interval 15 s Periodic updates missed before link declared broken 3 Initial triggered update weighted settling time 6 s Weighted settling time weighting factor 7/8 Route advertisement aggregation time 1 s Maximum packets buffered per node per destination 5 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] 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 in this paper use DSDV-SQ, with the exception of Section 6.2, which compares this with DSDV. Table I lists the constants used in our DSDV-SQ simulation. 3.2 Temporally-Ordered Routing Algorithm (TORA) TORA [14, 15] is a distributed routing protocol based on a “link reversal” algorithm. It is designed to discover routes on demand, provide multiple routes to a destination, establish routes quickly, and minimize communication overhead by localizing algorithmic reaction to topological changes when possible. Route optimality (shortest-path routing) is considered of secondary importance, and longer routes are often used to avoid the overhead of discovering newer routes. The actions taken by TORA can be described in terms of water flowing downhill towards a destination node through a network of tubes that models the routing state of the real network. The tubes represent links between nodes in the network, the junctions of tubes represent the nodes, and the water in the tubes represents the packets flowing towards the destination. Each node has a height with respect to the destination that is computed by the routing protocol. If a tube between nodes A and B becomes blocked such that water can no longer flow through it, the height of A is set to a height greater than that of any of its remaining neighbors, such that water will now flow back out of A (and towards the other nodes that had been routing packets to the destination via A). 3.2.1 Basic Mechanisms At each node in the network, a logically separate copy of TORA is run for each destination. When a node needs a route to a particular destination, it broadcasts a QUERY packet containing the address of the destination for which it requires a route. This packet propagates through the network until it reaches either the destination, or an intermediate node having a route to the destination. The recipient of the QUERY then broadcasts an UPDATE packet listing its height with respect to the destination. As this packet propagates through the network, each node that receives the UPDATE sets its height to a value greater than the height of the neighbor from which the UPDATE was received. This has the effect of creating a series of directed links from the original sender of the QUERY to the node that initially generated the UPDATE. When a node discovers that a route to a destination is no longer valid, it adjusts its height so that it is a local maximum with respect to its neighbors and transmits an UPDATE packet. If the node has no neighbors of finite height with respect to this destination, then the node instead attempts to discover a new route as described above. When a node detects a network partition, it generates a CLEAR packet that resets routing state and removes invalid routes from the network. TORA is layered on top of IMEP, the Internet MANET Encapsulation Protocol [5], which is required to provide reliable, in-order delivery of all routing control messages from a node to each of its neighbors, plus notification to the routing protocol whenever a link to one of its neighbors is created or broken. To reduce overhead, IMEP attempts to aggregate many TORA and IMEP control messages (which IMEP refers to as objects) together into a single packet (as an object block) before transmission. Each block carries a sequence number and a response list of other nodes from which an ACK has not yet been received, and only those nodes ACK the block when receiving it; IMEP retransmits each block with some period, and continues to retransmit it if needed for some maximum total period, after which time, the link to each unacknowledged node is declared down and TORA is notified. IMEP can also provide network layer address resolution, but we did not use this service, as we used ARP [19] with all four routing protocols. For link status sensing and maintaining a list of a node’s neighbors, each IMEP node periodically transmits a BEACON (or “BEACON-equivalent”) packet, which is answered by each node hearing it with a HELLO (or “HELLO-equivalent”) packet. 3.2.2 Implementation Decisions IMEP must queue objects for some period of time to allow possible aggregation with other objects, but the IMEP specification [5] does not define this time period, and we discovered that the overall performance of the protocol was very sensitive to the choice of this value. After significant experimentation, we chose as the best balance between packet overhead and routing protocol convergence, to aggregate HELLO and ACK packets for a time uniformly chosen between 150 ms and 250 ms, and to not delay TORA routing messages for aggregation. The reason for not delaying these messages is that the TORA link reversal process creates short-lived routing loops that exist from the time that the link-reversal starts until the time that all nodes that need to be aware of the reversal receive the corresponding UPDATE (Section 5.2). Delaying the transmission of TORA routing messages for aggregation, coupled with any queuing delay at the network interface, allows these routing loops to last long enough that significant numbers of data packets are dropped. The TORA and IMEP specifications [15, 5] do not define the precise semantics of reliable object delivery required by TORA, but experimentation showed that very strong semantics must be provided in order to prevent the creation of long-lived routing loops. In particular, all TORA objects must be delivered reliably and in order, without any duplication. Additionally, all neighboring nodes in the ad hoc network must have a consistent picture of the network with regard to each destination. This implies that anytime a node A decides its link to a neighbor B has gone down, B must also decide that the link to A has gone down. We have implemented IMEP to provide this functionality, although the retransmission timeout and total number of attempts are not specified by IMEP [5]. We chose a retransmission period of 500 ms and a total timeout of 1500 ms, although based upon our observations, an adaptive retransmission timer should be added to the protocol. Inorder delivery is enforced by, at each receiver node B, only passing 3
Table II Constants used in the ToRA simulation Table llI Constants used in the dsr simulation. Time between retransmitted ROUTE REQUESTS 500ms Time after which a link is declared down if no BEACON or 3s (exponentially backed off) HELLo packets were exchanged Size of eader carrying n addresse 4n+ 4 bytes Time after which an object block is retransmitted if no 500ms Tin Time after which an object block is not retransmitted and the Max rate for sending gratuitous REPLys for a rou link to the destination is declared down Min hello and Ack aggregation delay 150ms a ROUtE ERROR packet. The sender S can then attempt to use any Max heLLo and AcK aggregation delay other route to d already in its cache or can invoke Route Discovery an object block from some node a to TORA if the block has the equence number that IMEP at B next expects from A. Blocks with SIOn.S lower sequence numbers may generate another ACk but are otherwise Using the suggestions from the published description of DSR [101 dropped. Blocks with higher sequence numbers are queued unti we have optimized our implementation in a number of way missing blocks arrive or until the maximum 1500 ms total timeout Although the dsr protocol supports unidirectional routes, IEEE pires, at which point b can be certain the object will never be 802.11 requires an RTS/CTS/Data/ACK exchange for all unicast transmitted. By this point, A will have declared its link to B down, packets, limiting the routing protocol to using only bidirectional since it will not have received an ACK for the missing packet. To links in delivering data packets. We implemented DSR to discover give the routing protocol at B a picture consistent with that seen by only routes composed of bidirectional links by requiring that a node the protocol at A, the IMEP layer at B notifies its routing protocol return all ROUTE REPLY messages to the requestor by reversing the that the link to A is down, then notifies it the link is back up, and path over which the ROUTE REQUEST packet came. If the path taken then processes the queued packets. by a roUtE REQUEST contained unidirectional links, then the cor- Finally, we improved IMEP's method of link status sensing by responding ROUTE REPLY will not reach the requestor, preventing it reducing it to a point that functions with minimum overhead yet from learning the unidirectional link route still maintains all of the required link status information. During In Route Discovery, a node first sends a RoUTE REQUEST with the our experimentation with IMEP, we found that nodes need only maximum propagation limit(hop limit)set to zero, prohibiting its send BEACON messages when they are disconnected from all other neighbors from rebroadcasting it. At the cost of a single broadcast nodes. Suppose two nodes A and B, both of which have neighbors, packet, this mechanism allows a node to query the route caches of transmit a single HELLo listing each of their neighbors once per all its neighbors for a route and also optimizes the case in which the nodes will overhear each other's HELLOs and all other transmissions, search times out, a propagating ROUTE REQUEST is sent. ing each node to create a link to the other with"incoming Nodes operate their network interfaces in promiscuous mode, dis- Is In subsequent HELLo messages, A and b will list each other, abling the interfaces address filtering and causing the network proto- confirming that a bi-directional link exists between them col to receive all packets that the interface overhears. These packets Table ll lists the constants used in our tora simulation are scanned for useful source routes or rouTE ERROR messages and 3.3 Dynamic Source Routing (DSR) then discarded. This optimization allows nodes to learn potentially useful information, while causing no additional overhead on the lim- DSR [9, 10, 2] uses source routing rather than hop-by-hop routing, ited network bandwidth with each packet to be routed carrying in its header the complete, Furthermore, when a node overhears a packet not addressed to advantage of source routing is that intermediat no ust pass. The key itself, it checks the unprocessed portion of the source route in the ordered list of nodes through which the packet maintain up-to-date routing information in order to route the packets this source route could bypass the unprocessed hops preceding it in they forward, since the packets themselves already contain all the the route. The node then sends a gratuitous ROUTE REPLY message Iting decisions. This fact, coupled with the on-demand nature of to the packet's source, giving it the shorter route without these hops the protocol, eliminates the need for the periodic route advertisement Finally, when an intermediate node forwarding a packet discovers and neighbor detection packets present in other protocols that the next hop in the source route is unreachable, it examines its route cache for another route to the destination If a route exists the 33. Basic mechanisms node replaces the broken source route on the packet with the route The DSR protocol consists of two mechanisms: Route Discovery from its cache and retransmits the packet. If a route does not exist in and Route Maintenance. Route Discovery is the mechanism by its cache, the node drops the packet and does not begin a new route hich a node S wishing to send a packet to a destination d obtains Discovery of its own a source route to D. To perform a Route Discovery, the source node Table lli lists the constants used in our dsr simulation s broadcasts a RoUtE REQUEST packet that is flooded through the network in a controlled manner and is answered by a ROUTE rEPLY 3.4 Ad Hoc On-Demand Distance Vector(AODv) acket from either the destination node or another node that knows a AodV [17 is essentially a combination of both DSR and dsdv route to the destination. To reduce the cost of Route Discovery, each It borrows the basic on-demand mechanism of Route Discovery and node maintains a cache of source routes it has learned or overheard, Route Maintenance from DSR, plus the use of hop-by-hop routing, hich it aggressively uses to limit the frequency and propagation of sequence numbers, and periodic beacons from DSDV ROUTE REQUESTS Route maintenance is the sm by which a packets sender 3.4. Basic mechanisms detects if the network top as changed such that it When a node s needs a route to some destination d. it broad- longer use its route to the on d because two nodes listed casts a ROUTE REQUEST message to its neighbors, including the last the route have moved ou f each other. When Route known sequence number for that destination. The ROUTE REQUEST maintenance indicates a source route is broken, s is notified with is flooded in a controlled manner through the network until it reaches
Table II Constants used in the TORA simulation. BEACON period 1 s Time after which a link is declared down if no BEACON or HELLO packets were exchanged 3 s Time after which an object block is retransmitted if no acknowledgment is received 500 ms Time after which an object block is not retransmitted and the link to the destination is declared down 1500 ms Min HELLO and ACK aggregation delay 150 ms Max HELLO and ACK aggregation delay 250 ms an object block from some node A to TORA if the block has the sequence number that IMEP at B next expects from A. Blocks with lower sequence numbers may generate another ACK but are otherwise dropped. Blocks with higher sequence numbers are queued until the missing blocks arrive or until the maximum 1500 ms total timeout expires, at which point B can be certain the object will never be retransmitted. By this point, A will have declared its link to B down, since it will not have received an ACK for the missing packet. To give the routing protocol at B a picture consistent with that seen by the protocol at A, the IMEP layer at B notifies its routing protocol that the link to A is down, then notifies it the link is back up, and then processes the queued packets. Finally, we improved IMEP’s method of link status sensing by reducing it to a point that functions with minimum overhead yet still maintains all of the required link status information. During our experimentation with IMEP, we found that nodes need only send BEACON messages when they are disconnected from all other nodes. Suppose two nodes A and B, both of which have neighbors, transmit a single HELLO listing each of their neighbors once per BEACON period. If a bi-directional link exists between A and B, both nodes will overhear each other’s HELLOs and all other transmissions, causing each node to create a link to the other with “incoming” status. In subsequent HELLO messages, A and B will list each other, confirming that a bi-directional link exists between them. Table II lists the constants used in our TORA simulation. 3.3 Dynamic Source Routing (DSR) DSR [9, 10, 2] uses source routing rather than hop-by-hop routing, with each packet to be routed carrying in its header the complete, ordered list of nodes through which the packet must pass. The key advantage of source routing is that intermediate nodes do not need to maintain up-to-date routing information in order to route the packets they forward, since the packets themselves already contain all the routing decisions. This fact, coupled with the on-demand nature of the protocol, eliminates the need for the periodic route advertisement and neighbor detection packets present in other protocols. 3.3.1 Basic Mechanisms The DSR protocol consists of two mechanisms: Route Discovery and Route Maintenance. Route Discovery is the mechanism by which a node S wishing to send a packet to a destination D obtains a source route to D. To perform a Route Discovery, the source node S broadcasts a ROUTE REQUEST packet that is flooded through the network in a controlled manner and is answered by a ROUTE REPLY packet from either the destination node or another node that knows a route to the destination. To reduce the cost of Route Discovery, each node maintains a cache of source routes it has learned or overheard, which it aggressively uses to limit the frequency and propagation of ROUTE REQUESTs. Route Maintenance is the mechanism by which a packet’s sender S detects if the network topology has changed such that it can no longer use its route to the destination D because two nodes listed in the route have moved out of range of each other. When Route Maintenance indicates a source route is broken, S is notified with Table III Constants used in the DSR simulation. Time between retransmitted ROUTE REQUESTs (exponentially backed off) 500 ms Size of source route header carrying n addresses 4n + 4 bytes Timeout for nonpropagating search 30 ms Time to hold packets awaiting routes 30 s Max rate for sending gratuitous REPLYs for a route 1/s a ROUTE ERROR packet. The sender S can then attempt to use any other route to D already in its cache or can invoke Route Discovery again to find a new route. 3.3.2 Implementation Decisions Using the suggestions from the published description of DSR [10], we have optimized our implementation in a number of ways. Although the DSR protocol supports unidirectional routes, IEEE 802.11 requires an RTS/CTS/Data/ACK exchange for all unicast packets, limiting the routing protocol to using only bidirectional links in delivering data packets. We implemented DSR to discover only routes composed of bidirectional links by requiring that a node return all ROUTE REPLY messages to the requestor by reversing the path over which the ROUTE REQUEST packet came. If the path taken by a ROUTE REQUEST contained unidirectional links, then the corresponding ROUTE REPLY will not reach the requestor, preventing it from learning the unidirectional link route. In Route Discovery, a node first sends a ROUTE REQUEST with the maximum propagation limit (hop limit) set to zero, prohibiting its neighbors from rebroadcasting it. At the cost of a single broadcast packet, this mechanism allows a node to query the route caches of all its neighbors for a route and also optimizes the case in which the destination node is adjacent to the source. If this nonpropagating search times out, a propagating ROUTE REQUEST is sent. Nodes operate their network interfaces in promiscuous mode, disabling the interface’s address filtering and causing the network protocol to receive all packets that the interface overhears. These packets are scanned for useful source routes or ROUTE ERROR messages and then discarded. This optimization allows nodes to learn potentially useful information, while causing no additional overhead on the limited network bandwidth. Furthermore, when a node overhears a packet not addressed to itself, it checks the unprocessed portion of the source route in the packet’s header. If the node’s own address is present, it knows that this source route could bypass the unprocessed hops preceding it in the route. The node then sends a gratuitous ROUTE REPLY message to the packet’s source, giving it the shorter route without these hops. Finally, when an intermediate node forwarding a packet discovers that the next hop in the source route is unreachable, it examines its route cache for another route to the destination. If a route exists, the node replaces the broken source route on the packet with the route from its cache and retransmits the packet. If a route does not exist in its cache, the node drops the packet and does not begin a new Route Discovery of its own. Table III lists the constants used in our DSR simulation. 3.4 Ad Hoc On-Demand Distance Vector (AODV) AODV [17] is essentially a combination of both DSR and DSDV. It borrows the basic on-demand mechanism of Route Discovery and Route Maintenance from DSR, plus the use of hop-by-hop routing, sequence numbers, and periodic beacons from DSDV. 3.4.1 Basic Mechanisms When a node S needs a route to some destination D, it broadcasts a ROUTE REQUEST message to its neighbors, including the last known sequence number for that destination. The ROUTE REQUEST is flooded in a controlled manner through the network until it reaches 4
a node that has a route to the destination Each node that forwards Table Iv Constants used in the aodv-LL simulation the route request creates a reverse route for itself back to node s the ro Time for which a route is considered active node generates a ROUTE REPLY that contains the number of hops Lifetime on a ROUTE REPLY sent by necessary to reach D and the sequence number for D most recentl seen by the node generating the REPly. Each node that participates UTE REQUEST iS retried in forwarding this reply back toward the originator of the route Time for which the broadcast id for a forwarded rouTe REQUEST (node S), creates a forward route to D. The state created REQUEST is kept in each node along the path from S to D is hop-by-hop state, that is, Time for which reverse route information for a route each node remembers only the next hop and not the entire route,as REPLY is kept ould be done in source routing In order to maintain routes, AoDV normally requires that each node periodically transmit a HELLo message, with a default rate of once per second. Failure to receive three consecutive HELLo mes- Our protocol evaluations are based on the simulation of 50 wireless ges from a neighbor is taken as an indication that the link to the nodes forming an ad hoc network, moving about over a rectangular neighbor in question is down. Alternatively, the AODV specification (1500m x 300m)flat space for 900 seconds of simulated time.We efly suggests that a node may use physical layer or link layer meth- chose a rectangular space in order to force the use of longer routes ods to detect link breakages to nodes that it considers neighbors [17].be When a link goes down, any upstream node that has recently density. The physical radio characteristics of each mobile node's net forwarded ets to a destination using that link is notified via an work interface, such as the antenna gain, transmit power, and receiver UNSOLICITED ROUTE REPLY containing an infinite metric for that sensitivity, were chosen to approximate the Lucent WaveLAN [22] destination. Upon receipt of such a ROUTE REPLY, a node must direct sequence spread spectrum radio In order to enable direct, fair comp s between the protocols, described above it was critical to challenge the protocols with identical loads and 3.4.2 Implementation Decisions environmental conditions. Each run of the simulator accepts as input We initially implemented AODV using periodic HELLO messages for exact sequence of packets originated by each node, together with the link breakage detection as described in the AODV specification [17]. exact time at which each change in motion or packet origination is For comparison, we also implemented a version of AoDV that we call to occur. We pre-generated 210 different scenario files with varying AODV-LL (link layer), instead using only link layer feedback from movement patterns and traffc loads, and then ran all four routing mechanism. Such an approach saves the overhead of the periodic was challenged in an identical fashion, we can directly compare the HELLo messages, but does somewhat change the fundamental nature of the protocol; for example, all link breakage detection in AODV-LL is only on-demand, and thus a broken link cannot be detected until 4.1 Movement Model a packet needs to be sent over the link, whereas the periodic HELLo Nodes in the simulation move according to a model that we call the messages in standard AoDV may allow broken links to be detected "random waypoint" model [10]. The movement scenario files we before a packet must be forwarded. Nevertheless, we found our alter- used for eachsimulation are characterized by pause time. Each node nate version AODV-LL to perform significantly better than standard begins the simulation by remaining stationary for pause time seconds AoDV, and so we report measurements from that version here. It then selects a random destination in the 1500m x 300m space and In addition, we also changed our AODV implementation to use a moves to that destination at a speed distributed uniformly between 0 shorter timeout of 6 seconds before retrying a ROUTE REQUEST for and some maximum speed. Upon reaching the destination, the node which no ROUTE REPLY has been received(RREP_WAIT_TIME). pauses again for pause time seconds, selects another destination, and The value given in the AODV specification was 120 seconds, based proceeds there as previously described, repeating this behavior for on the other constants specified there for AODV. However, a route the duration of the simulation. Each simulation ran for 900 seconds REPly can only be returned if each node along the discovered route of simulated time still has a reverse route along which to return it, saved from when the We ran our simulations with movement patterns generated for 7 ROUTE REQUEST was propagated. Since the specified timeout for this different pause times: 0, 30, 60, 120, 300, 600, and 900 seconds everse route information in each node is only 3 seconds, the original A pause time of 0 seconds corresponds to continuous motion, and a ROUTE REPLY timeout value of 120 seconds unnecessarily limited use time of 900( the length of the simulation) corresponds the protocol's ability to recover from a dropped rOUTE REQUEST or motion. ROUTE REPLY packet Because the performance of the protocols is very sensitive to move- Table Iv lists the constants used in our AodV-LL simulation ment pattern, we generated scenario files with 70 different movement patterns, 10 for each value of pause time. All four routing protocols ere run on the same 70 movement patterns We experimented with two different maximum speeds of node The overall goal of our experiments was to measure the ability of movement. We primarily report in this paper data from simulations ne routing protocols to react to network topology change while using a maximum node speed of 20 meters per second(average speed Continuing to successfully deliver data packets to their destinations 10 meters per second), but also compare this to simulations using measure this ability, our basic methodology was to apply to a maximum speed of I meter per second mulated network a variety of workloads, in effect testing with each data packet originated by so der whether the routing protoc 4.2 Communication Model can at that time route to the destination of that packet. We were As the goal of our simulation was to compare the performance of each not attempting to measure the protocols' performance on a particular routing protocol, we chose our traffic to be constant bit rate workload taken from real life, but rather to measure the protocols ( CBr)sources. When defining the parameters of the communication performance under a range of conditions odel, we experimented with sending rates of 1, 4, and 8 packets
a node that has a route to the destination. Each node that forwards the ROUTE REQUEST creates a reverse route for itself back to node S. When the ROUTE REQUEST reaches a node with a route to D, that node generates a ROUTE REPLY that contains the number of hops necessary to reach D and the sequence number for D most recently seen by the node generating the REPLY. Each node that participates in forwarding this REPLY back toward the originator of the ROUTE REQUEST (node S), creates a forward route to D. The state created in each node along the path from S to D is hop-by-hop state; that is, each node remembers only the next hop and not the entire route, as would be done in source routing. In order to maintain routes, AODV normally requires that each node periodically transmit a HELLO message, with a default rate of once per second. Failure to receive three consecutive HELLO messages from a neighbor is taken as an indication that the link to the neighbor in question is down. Alternatively, the AODV specification briefly suggests that a node may use physical layer or link layer methods to detect link breakages to nodes that it considers neighbors [17]. When a link goes down, any upstream node that has recently forwarded packets to a destination using that link is notified via an UNSOLICITED ROUTE REPLY containing an infinite metric for that destination. Upon receipt of such a ROUTE REPLY, a node must acquire a new route to the destination using Route Discovery as described above. 3.4.2 Implementation Decisions We initially implemented AODV using periodic HELLO messages for link breakage detection as described in the AODV specification [17]. For comparison, we also implemented a version of AODV that we call AODV-LL (link layer), instead using only link layer feedback from 802.11 as in DSR, completely eliminating the standard AODV HELLO mechanism. Such an approach saves the overhead of the periodic HELLO messages, but does somewhat change the fundamental nature of the protocol; for example, all link breakage detection in AODV-LL is only on-demand, and thus a broken link cannot be detected until a packet needs to be sent over the link, whereas the periodic HELLO messages in standard AODV may allow broken links to be detected before a packet must be forwarded. Nevertheless, we found our alternate version AODV-LL to perform significantly better than standard AODV, and so we report measurements from that version here. In addition, we also changed our AODV implementation to use a shorter timeout of 6 seconds before retrying a ROUTE REQUEST for which no ROUTE REPLY has been received (RREP WAIT TIME). The value given in the AODV specification was 120 seconds, based on the other constants specified there for AODV. However, a ROUTE REPLY can only be returned if each node along the discovered route still has a reverse route along which to return it, saved from when the ROUTEREQUEST was propagated. Since the specified timeout for this reverse route information in each node is only 3 seconds, the original ROUTE REPLY timeout value of 120 seconds unnecessarily limited the protocol’s ability to recover from a dropped ROUTE REQUEST or ROUTE REPLY packet. Table IV lists the constants used in our AODV-LL simulation. 4 Methodology The overall goal of our experiments was to measure the ability of the routing protocols to react to network topology change while continuing to successfully deliver data packets to their destinations. To measure this ability, our basic methodology was to apply to a simulated network a variety of workloads, in effect testing with each data packet originated by some sender whether the routing protocol can at that time route to the destination of that packet. We were not attempting to measure the protocols’ performance on a particular workload taken from real life, but rather to measure the protocols’ performance under a range of conditions. Table IV Constants used in the AODV-LL simulation. Time for which a route is considered active 300 s Lifetime on a ROUTE REPLY sent by destination node 600 s Number of times a ROUTE REQUEST is retried 3 Time before a ROUTE REQUEST is retried 6 s Time for which the broadcast id for a forwarded ROUTE REQUEST is kept 3 s Time for which reverse route information for a ROUTE REPLY is kept 3 s Time before broken link is deleted from routing table 3 s MAC layer link breakage detection yes Our protocol evaluations are based on the simulation of 50 wireless nodes forming an ad hoc network, moving about over a rectangular (1500m 300m) flat space for 900 seconds of simulated time. We chose a rectangular space in order to force the use of longer routes between nodes than would occur in a square space with equal node density. The physical radio characteristics of each mobile node’s network interface, such as the antenna gain, transmit power, and receiver sensitivity, were chosen to approximate the Lucent WaveLAN [22] direct sequence spread spectrum radio. In order to enable direct, fair comparisons between the protocols, it was critical to challenge the protocols with identical loads and environmental conditions. Each run of the simulator accepts as input a scenario file that describes the exact motion of each node and the exact sequence of packets originated by each node, together with the exact time at which each change in motion or packet origination is to occur. We pre-generated 210 different scenario files with varying movement patterns and traffic loads, and then ran all four routing protocols against each of these scenario files. Since each protocol was challenged in an identical fashion, we can directly compare the performance results of the four protocols. 4.1 Movement Model Nodes in the simulation move according to a model that we call the “random waypoint” model [10]. The movement scenario files we used for each simulation are characterized by a pause time. Each node begins the simulation by remaining stationary for pause time seconds. It then selects a random destination in the 1500m 300m space and moves to that destination at a speed distributed uniformly between 0 and some maximum speed. Upon reaching the destination, the node pauses again for pause time seconds, selects another destination, and proceeds there as previously described, repeating this behavior for the duration of the simulation. Each simulation ran for 900 seconds of simulated time. We ran our simulations with movement patterns generated for 7 different pause times: 0, 30, 60, 120, 300, 600, and 900 seconds. A pause time of 0 seconds corresponds to continuous motion, and a pause time of 900 (the length of the simulation) corresponds to no motion. Because the performance of the protocols is very sensitive to movement pattern, we generated scenario files with 70 different movement patterns, 10 for each value of pause time. All four routing protocols were run on the same 70 movement patterns. We experimented with two different maximum speeds of node movement. We primarily report in this paper data from simulations using a maximum node speed of 20 meters per second (average speed 10 meters per second), but also compare this to simulations using a maximum speed of 1 meter per second. 4.2 Communication Model As the goal of our simulation was to compare the performance of each routing protocol, we chose our traffic sources to be constant bit rate (CBR) sources. When defining the parameters of the communication model, we experimented with sending rates of 1, 4, and 8 packets 5
Table V Average number of link connectivity changes during each 900-second simulation as a function of pause time of Connectivity Changes Pause time 245 Figure 1 shows the distribution of shortest the destination was the given distance away when the packet was Figure 1 n of the shortest path available to each originated. The average data packet in our simulations had to cross 2.6 hops to reach its destination, and the farthest reachable node to d, networks containing 10, 20, and 30 CBR which the routing protocols had to deliver a packet was 8 hops away Table V shows the average number of link connectivity changes izes of 64 and 1024 bytes that occurred during each of the simulations runs for each value tov ving the number of CBR sources was approximately equivalent of pause time. We count one link connectivity change whenever a to varying the sending rate. Hence, for these simulations we chose to node goes into or out of direct communication range with another fix the sending rate at 4 packets per second, and used three different node. For the specific scenarios we used, the 30-s communication patterns corresponding to 10, 20, and 30 sources. scenarios at I m/s actually have a slightly higher average rate of link When using 1024-byte packets, we found that congestion, du connectivity change than the o-second pause time scenarios, due to lack of spatial diversity, became a problem for all protocols and an artifact of the random generation of the scenarios. This artifact ne or two nodes would drop most of the packets that they received is also visible as a slight bump at a pause time of 30 seconds in the protocols could consistently track changes in topology, we attempted 4.4 Validation of the Propagation Model and MAC Layer to factor out congestive effects by reducing the packet size to 64 bytes. Our propagation model uses standard equations and techniques, and This smaller packet size still provides a good test of the routing it was verified by an expert in radio prop behavior n modeling. We that the propaga- All communication patterns were peer-to-peer, and connections tion, capture, and carrier sense models were working as designed The 802. 11 MAC implementation was studied in a variety of sce- were started at times uniformly distributed between 0 and 180 sec- narios and independently verified by two of the authors. We exper- onds. The three communication patterns(10, 20, and 30 sources). taken in conjunction with the 70 movement patterns, provide a total mentally tested that when all nodes of 210 different scenario files for each maximum node movement data packets experience collisions(regardless of offered traffic load) and that each node is able to make progress sending packets. This speed(I m/s and 20 m/s)with which we compared the four routing verified that the carrier sense, RTS/CTS, and back-off mechanisms We did not use TCP sources because TCP a conforming of 802 1 1 were working correctly load to the network, meaning that it changes the times at whic it sends packets based on its perception of the network's ability to 4.5 Validation of the Routing Protocol Implementations carry packets. As a result, both the time at which each data packet is Each protocol implementation was studied and verified by at least iginated by its sender and the position of the node when sending two of the authors, and two independent implementations were made he packet would differ between the protocols, preventing a direct of both aodv and dSDv The results of each simulation were internally consistent. That is, the percentage of packets originated by theapplication layer 4.3 Scenario Characteristics sources that were not logged as either received or dropped at the end To characterize the challenge our scenarios placed on the routing of the simulation was less than 0.01 %(approximately 10 packets per protocols, we measured the lengths of the routes over which the simulation). These packets were almost certainly in the end protocols had to deliver packets, and the total number of topology of the simulation, as the simulation originates between 40 and 120 hanges in each scenario. packets per simulated second and terminates at exactly 900 seconds When each data packet is originated, an internal mechanist without a cool-down period simulator(separate from the routing protocols) calculates the shortest The results of our simulations are in fact, different from the few path between the packet's sender and its destination. The packet is previously reported studies of some of these protocols. We explain abeled with this information, which is compared with the number the reasons for these differences in Sections 5, 6, and 7 of hops actually taken by the packet when received by the intended destination. The shortest path is calculated based on a nominal 4.6 Metrics transmission range of 250m for each radio and does not account for In comparing the protocols, we chose to evaluate them according to congestion or interference that any particular packet might see the following three metrics
1 2 3 4 5 6 7 8 9 10 0 500,000 1,000,000 1,500,000 2,000,000 2,500,000 3,000,000 3,500,000 4,000,000 4,500,000 Number of packets Shortest available path length 1 m/s scenarios 20 m/s scenarios Figure 1 Distribution of the shortest path available to each application packet originated over all scenarios. per second, networks containing 10, 20, and 30 CBR sources, and packet sizes of 64 and 1024 bytes. Varying the number of CBR sources was approximately equivalent to varying the sending rate. Hence, for these simulations we chose to fix the sending rate at 4 packets per second, and used three different communication patterns corresponding to 10, 20, and 30 sources. When using 1024-byte packets, we found that congestion, due to lack of spatial diversity, became a problem for all protocols and one or two nodes would drop most of the packets that they received for forwarding. As none of the studied protocols performs load balancing, and the goal of our analysis was to determine if the routing protocols could consistently track changes in topology, we attempted to factor out congestive effects by reducing the packet size to 64 bytes. This smaller packet size still provides a good test of the routing protocols, since we are still testing their ability to determine routes to a destination with the same frequency (a total of 40, 80, or 120 times per second). All communication patterns were peer-to-peer, and connections were started at times uniformly distributed between 0 and 180 seconds. The three communication patterns (10, 20, and 30 sources), taken in conjunction with the 70 movement patterns, provide a total of 210 different scenario files for each maximum node movement speed (1 m/s and 20 m/s) with which we compared the four routing protocols. We did not use TCP sources because TCP offers a conforming load to the network, meaning that it changes the times at which it sends packets based on its perception of the network’s ability to carry packets. As a result, both the time at which each data packet is originated by its sender and the position of the node when sending the packet would differ between the protocols, preventing a direct comparison between them. 4.3 Scenario Characteristics To characterize the challenge our scenarios placed on the routing protocols, we measured the lengths of the routes over which the protocols had to deliver packets, and the total number of topology changes in each scenario. When each data packet is originated, an internal mechanism of our simulator (separate from the routing protocols) calculates the shortest path between the packet’s sender and its destination. The packet is labeled with this information, which is compared with the number of hops actually taken by the packet when received by the intended destination. The shortest path is calculated based on a nominal transmission range of 250m for each radio and does not account for congestion or interference that any particular packet might see. Table V Average number of link connectivity changes during each 900-second simulation as a function of pause time. # of Connectivity Changes Pause Time 1 m/s 20 m/s 0 898 11857 30 908 8984 60 792 7738 120 732 5390 300 512 2428 600 245 1270 900 0 0 Figure 1 shows the distribution of shortest path lengths for all packets over the 210 scenario files at 1 m/s and 20 m/s that we used. The height of each bar represents the number of packets for which the destination was the given distance away when the packet was originated. The average data packet in our simulations had to cross 2.6 hops to reach its destination, and the farthest reachable node to which the routing protocols had to deliver a packet was 8 hops away. Table V shows the average number of link connectivity changes that occurred during each of the simulations runs for each value of pause time. We count one link connectivity change whenever a node goes into or out of direct communication range with another node. For the specific scenarios we used, the 30-second pause time scenarios at 1 m/s actually have a slightly higher average rate of link connectivity change than the 0-second pause time scenarios, due to an artifact of the random generation of the scenarios. This artifact is also visible as a slight bump at a pause time of 30 seconds in the performance graphs we present for 1 m/s in Section 5. 4.4 Validation of the Propagation Model and MAC Layer Our propagation model uses standard equations and techniques, and it was verified by an expert in radio propagation modeling. We analyzed the power and simulated radio behavior as a function of distance between small groups of nodes to ensure that the propagation, capture, and carrier sense models were working as designed. The 802.11 MAC implementation was studied in a variety of scenarios and independently verified by two of the authors. We experimentally tested that when all nodes are in range of each other, no data packets experience collisions (regardless of offered traffic load), and that each node is able to make progress sending packets. This verified that the carrier sense, RTS/CTS, and back-off mechanisms of 802.11 were working correctly. 4.5 Validation of the Routing Protocol Implementations Each protocol implementation was studied and verified by at least two of the authors, and two independent implementations were made of both AODV and DSDV. The results of each simulation were internally consistent. That is, the percentage of packets originated by the “application layer” sources that were not logged as either received or dropped at the end of the simulation was less than 0.01% (approximately 10 packets per simulation). These packets were almost certainly in transit at the end of the simulation, as the simulation originates between 40 and 120 packets per simulated second and terminates at exactly 900 seconds without a cool-down period. The results of our simulations are, in fact, different from the few previously reported studies of some of these protocols. We explain the reasons for these differences in Sections 5, 6, and 7. 4.6 Metrics In comparing the protocols, we chose to evaluate them according to the following three metrics: 6
Packet delivery ratio: The ratio between the number of packets originated by the "application layer"CBR sources and the num- ber of packets received by the CBr sink at the final destination. Routing overhead: The total number of routing packets trans- ted during the simulation. For packets sent over multiple ps, each transmission of the packet(each hop)counts as one transmission Path optimality: The difference between the number of hops packet took to reach its destination and the length of the shortest path that physically existed through the network when the packet Packet delivery ratio is important as it describes the loss rate that will be seen by the transport protocols, which in turn effects the naximum throughput that the network can support. This metric characterizes both the completeness and correctness of the routing protocol Routing overhead is an important metric for comparing these pro- tocols, as it measures the scalability of a protocol, the degree to which it will function in congested or low-bandwidth environments, and its Figure 2 Comparison between the four protocols of the fraction of efficiency in terms of consuming node battery power. Protocols that application data packets successfully delivered(packet delivery ratio as a function of pause time. Pause time O represents constant mobility send large numbers of routing packets can also increase the prob- ability of packet collisions and may delay data packets in network interface transmission queues. We also evaluated the number of bytes of routing overhead caused by the source routing header re- DSR quired by dsr, and present those results in Section 6.1. We did 口AoLL not include IEEE 802. 11 MAC packets or ARP packets in routing overhead, since the routing protocols could be run over a variety of different medium access or address resolution protocols, each of which would have different overhead. Our goal was to compare the routing protocols to each other, not to find the optimal performance possible in our scenario In the absence of opuIm measures the ability of the routing protocol to eficiently use network resources by selecting the shortest path from a source to a destination. We calculate it as the difference between the shortest path found internally by the simulator when the packet was originated, and the number of hops the packet actually took to reach its destination 5 Simulation Results As noted in Section 4. 1, we conducted simulations using two different Figure 3 on between the four protocols of the number of node movement speeds: a maximum speed of 20 m/s(average speed routing packets sent(routing overhead) as a function of pause time 10 m/s)and a maximum speed of I m/s. We first compare the four Pause time 0 represents constant mob protocols based on the 20 m/s simulations, and then in Section 5.5 present data for I m/s for comparison. For all simulations, the The TORA results shown in Figures 2 and 3 at paus communication patterns were peer-to-peer, with each run having either 10, 20, or 30 sources sending 4 packets per second he average of only 9 scenarios, as the overhead for the tenth scenario was much higher than the others due to significant congestion caused by the routing protocol. The complete results are included below and <plained in Section 5.3 Figures 2 and 3 highlight the relative performance of the four routing protocols on our traffic loads of 20 sources 5.2 Packet Delivery Ratio Details All of the protocols deliver a greater percentage of the originated Figure 4 shows the fraction of the originated application data packets data packets when there is little node mobility (i.e, at large pause each protocol was able to deliver, as a function of both node mobility BR onverging to 100% delivery when there is no node motion. rate(pause time)and network load(number of sources). For DSR and AODV-LL perform particularly well, delivering over 95% d AODV-LL, packet delivery ratio is independent of offered traffic lata packets regardless of mobility rate. In thes oad, with both protocols delivering between 95% and 100% of the DSDV-sQ fails to converge at pause times less than 300 second ts in The four routing protocols impose vastly different amounts DSDv-SQ fails to ime 300. where it de- verhead, as shown in Figu livers about 92% of its es of mobility (lower separates DSR, which has the least overhead, from TORA, which pause times), DSDV-SQ to a 70% packet de- has the most. The basic character of each protocol is demonstrated livery ratio. Nearly all of the dropped packets are lost because a stale in the shape of its overhead curve. TORA, DSR, and AODV-LL are routing table entry directed them to be forwarded over a broken link all on-demand protocols, and their overhead drops as the mobility As described in Section 3. 1. 2, DsDv-sQ maintains only one route ate drops. As DSDv-sQ is a largely periodic routing protocol, its per destination and consequently, each packet that the MAc layer is overhead is nearly constant with respect to mobility rate unable to deliver is dropped since there are no alternate routes
Packet delivery ratio: The ratio between the number of packets originated by the “application layer” CBR sources and the number of packets received by the CBR sink at the final destination. 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. 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. Packet delivery ratio is important as it describes the loss rate that will be seen by the transport protocols, which in turn effects the maximum throughput that the network can support. This metric characterizes both the completeness and correctness of the routing protocol. Routing overhead is an important metric for comparing these protocols, as it measures the scalability of a protocol, the degree to which it will function in congested or low-bandwidth environments, and its efficiency in terms of consuming node battery power. Protocols that send large numbers of routing packets can also increase the probability of packet collisions and may delay data packets in network interface transmission queues. We also evaluated the number of bytes of routing overhead caused by the source routing header required by DSR, and present those results in Section 6.1. We did not include IEEE 802.11 MAC packets or ARP packets in routing overhead, since the routing protocols could be run over a variety of different medium access or address resolution protocols, each of which would have different overhead. Our goal was to compare the routing protocols to each other, not to find the optimal performance possible in our scenarios. In the absence of congestion or other “noise,” path optimality measures the ability of the routing protocol to efficiently use network resources by selecting the shortest path from a source to a destination. We calculate it as the difference between the shortest path found internally by the simulator when the packet was originated, and the number of hops the packet actually took to reach its destination. 5 Simulation Results As noted in Section 4.1, we conducted simulations using two different node movement speeds: a maximum speed of 20 m/s (average speed 10 m/s) and a maximum speed of 1 m/s. We first compare the four protocols based on the 20 m/s simulations, and then in Section 5.5 present data for 1 m/s for comparison. For all simulations, the communication patterns were peer-to-peer, with each run having either 10, 20, or 30 sources sending 4 packets per second. 5.1 Comparison Summary Figures 2 and 3 highlight the relative performance of the four routing protocols on our traffic loads of 20 sources. All of the protocols deliver a greater percentage of the originated data packets when there is little node mobility (i.e., at large pause time), converging to 100% delivery when there is no node motion. DSR and AODV-LL perform particularly well, delivering over 95% of the data packets regardless of mobility rate. In these scenarios, DSDV-SQ fails to converge at pause times less than 300 seconds. The four routing protocols impose vastly different amounts of overhead, as shown in Figure 3. Nearly an order of magnitude separates DSR, which has the least overhead, from TORA, which has the most. The basic character of each protocol is demonstrated in the shape of its overhead curve. TORA, DSR, and AODV-LL are all on-demand protocols, and their overhead drops as the mobility rate drops. As DSDV-SQ is a largely periodic routing protocol, its overhead is nearly constant with respect to mobility rate. 0 100 200 300 400 500 600 700 800 900 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Pause time (secs) # data packets received / # data packets sent DSDV−SQ TORA DSR AODV−LL Figure 2 Comparison between the four protocols of the fraction of application data packets successfully delivered (packet delivery ratio) as a function of pause time. Pause time 0 represents constant mobility. 0 100 200 300 400 500 600 700 800 900 0 20,000 40,000 60,000 80,000 100,000 120,000 140,000 160,000 Pause time (secs) Routing overhead (packets) DSDV−SQ TORA DSR AODV−LL Figure 3 Comparison between the four protocols of the number of routing packets sent (routing overhead) as a function of pause time. Pause time 0 represents constant mobility. The TORA results shown in Figures 2 and 3 at pause time 600 are the average of only 9 scenarios, as the overhead for the tenth scenario was much higher than the others due to significant congestion caused by the routing protocol. The complete results are included below and explained in Section 5.3. 5.2 Packet Delivery Ratio Details Figure 4 shows the fraction of the originated application data packets each protocol was able to deliver, as a function of both node mobility rate (pause time) and network load (number of sources). For DSR and AODV-LL, packet delivery ratio is independent of offered traffic load, with both protocols delivering between 95% and 100% of the packets in all cases. DSDV-SQ fails to converge below pause time 300, where it delivers about 92% of its packets. At higher rates of mobility (lower pause times), DSDV-SQ does poorly, dropping to a 70% packet delivery ratio. Nearly all of the dropped packets are lost because a stale routing table entry directed them to be forwarded over a broken link. As described in Section 3.1.2, DSDV-SQ maintains only one route per destination and consequently, each packet that the MAC layer is unable to deliver is dropped since there are no alternate routes. 7
t6a a (a) DSDv-SQ b)DSR 国影 -*3 (c) TORA (d) AODV-LL Figure 4 Packet delivery ratio as a function of pause time. TORa is shown on a different vertical scale for clarity(see Figure 2) TORA does well with 10 or 20 sources, delivering between 90% overhead to TORAIMEP which, as shown in Section 5.3, is already nd 95% of originated data packets even at the highest rate of node higher than the other protocols studied here to the creation of short-lived routing loops that are a natural part 5.3 Routing Overhead Details of its link-reversal process. Consider a node A routing packets to Figure 5 shows the number of routing protocol packets sent by ea C via B. If B's link to C breaks, B will reverse its link to A otocol in obtaining the delivery ratios shown in Figure 4. DSR and transmit an UPDATE to notify its neighbors it has done this, and DSDv-SQ are plotted on a the same scale as each other, but AOD begin routing packets to C via A. Until A receives the UPDATE, LL and TORa are each plotted on different scales to best show the data packets to C will loop between A and B. Our implementation effect of pause time and offered load on overhead. TORA, DSR, of ToRa detects when the next-hop of a packet is the same as the and AODV-LL are on-demand rout previous-hop and drops the data packet, since experiments showed of sources increases, we expect the number of routing packets sent that allowing these packets to loop until their TTL expires or the to increase because there are more destinations to which the networ loop resolves causes more packets to be dropped overall, as the must maintain working routes ng data packets interfere with the ability of other nearby nodes to DSR and AODV-LL, which use only on-demand packets and ver essfully exchange the broadcast UPDATE packet that will resolve similar basic mechanisms, have almost identically shaped curves thel Both protocols exhibit the desirable property that the incremental With 30 sources, TORA's average packet delivery ratio drops to cost of additional sources decreases as sources are added. since the e time 0, although upon examination of the data w protocol can use information learned from one route discovery to found that variability was extremely large, with packet delivery ra- complete a subsequent route discovery. tios ranging from 8% to 91%. In most of these scenarios, TORA However, the absolute overhead required by DsR and AODV-LL fails to converge because of increased congestion, as explained in are very different, with AODV-LL requiring about 5 times the over- Section 53. A very recently released revision to the IMEP speci- head of DSR when there is constant node motion(pause time 0). This fication [4] claims to prove the reliable control dramatic in AODV-LL's overhead occurs because each semantics provided by IMEP, which might eliminate some of the be- its route discoveries typically propagates to every node in the ad hoc saviors seen here. However, these new mechanisms add more packet etwork. For example, at pause time 0 with 30 sources, AODV-LL
0 100 200 300 400 500 600 700 800 900 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Pause time (secs) # data packets received / # data packets sent 10 sources 20 sources 30 sources (a) DSDV-SQ 0 100 200 300 400 500 600 700 800 900 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Pause time (secs) # data packets received / # data packets sent 10 sources 20 sources 30 sources (b) DSR 0 100 200 300 400 500 600 700 800 900 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Pause time (secs) # data packets received / # data packets sent 10 sources 20 sources 30 sources (c) TORA 0 100 200 300 400 500 600 700 800 900 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Pause time (secs) # data packets received / # data packets sent 10 sources 20 sources 30 sources (d) AODV-LL Figure 4 Packet delivery ratio as a function of pause time. TORA is shown on a different vertical scale for clarity (see Figure 2). TORA does well with 10 or 20 sources, delivering between 90% and 95% of originated data packets even at the highest rate of node mobility (pause time 0). The majority of the packet drops are due to the creation of short-lived routing loops that are a natural part of its link-reversal process. Consider a node A routing packets to C via B. If B’s link to C breaks, B will reverse its link to A, transmit an UPDATE to notify its neighbors it has done this, and begin routing packets to C via A. Until A receives the UPDATE, data packets to C will loop between A and B. Our implementation of TORA detects when the next-hop of a packet is the same as the previous-hop and drops the data packet, since experiments showed that allowing these packets to loop until their TTL expires or the loop resolves causes more packets to be dropped overall, as the looping data packets interfere with the ability of other nearby nodes to successfully exchange the broadcast UPDATE packet that will resolve their routing loop. With 30 sources, TORA’s average packet delivery ratio drops to 40% at pause time 0, although upon examination of the data we found that variability was extremely large, with packet delivery ratios ranging from 8% to 91%. In most of these scenarios, TORA fails to converge because of increased congestion, as explained in Section 5.3. A very recently released revision to the IMEP speci- fication [4] claims to improve the reliable control message delivery semantics provided by IMEP, which might eliminate some of the behaviors seen here. However, these new mechanisms add more packet overhead to TORA/IMEP which, as shown in Section 5.3, is already higher than the other protocols studied here. 5.3 Routing Overhead Details Figure 5 shows the number of routing protocol packets sent by each protocol in obtaining the delivery ratios shown in Figure 4. DSR and DSDV-SQ are plotted on a the same scale as each other, but AODVLL and TORA are each plotted on different scales to best show the effect of pause time and offered load on overhead. TORA, DSR, and AODV-LL are on-demand routing protocols, so as the number of sources increases, we expect the number of routing packets sent to increase because there are more destinations to which the network must maintain working routes. DSR and AODV-LL, which use only on-demand packets and very similar basic mechanisms, have almost identically shaped curves. Both protocols exhibit the desirable property that the incremental cost of additional sources decreases as sources are added, since the protocol can use information learned from one route discovery to complete a subsequent route discovery. However, the absolute overhead required by DSR and AODV-LL are very different, with AODV-LL requiring about 5 times the overhead of DSR when there is constant node motion (pause time 0). This dramatic increase in AODV-LL’s overhead occurs because each of its route discoveries typically propagates to every node in the ad hoc network. For example, at pause time 0 with 30 sources, AODV-LL 8
a) DSDv-SQ (b)DSR 180,000 a6000 (c) TORA Figure 5 Routing overhead as a function of pause time. TORA and AoDV-LL are shown on different vertical scales for clarity(see Figure 3) about 2200 route discoveries per 900-second simulation the pause time 900 scenarios when all nodes were stationary. TORA ulting in around 110,000 ROUTE REQUEST transmissions In reacted to the perceived link breakages by sending more UPDATES, DSR limits the scope and overhead of roUTE REQUEST which closed the feedback loop by directly causing more conges- by using caching from forwarded and promiscuously over- tion. More importantly, each UPDATE sent required reliable delivery, ackets and using non-propagating ROUTE REQUESTS as de- which increased the systems exposure to additional erroneous link non-pro in Section 3.3.2, which results in DSR sending only 950 failure detections, since the failure to receive an ACK from retrans- non-propagating requests and 300 propagating requests per simula- mitted UPDATEs was treated as a link failure indication. In the worst runs, TORA generated over 10 million objects, which IMEP aggre TORA's overhead is the sum of a constant mobility-independent gated into 1.6 million packets requiring reliable delivery. In the few verhead and a variable mobility-dependent overhead The constant 30-source runs where congestion did not develop, the overhead var overhead is the result of IMEP's neighbor discovery mechanism, ied from 639,000 packets at pause time 0 to 47,000 packets at pause hich requires each node to transmit at least 1 HELLo packet per time 900 BEACON period(I second). For 900-second simulations with 50 DSDV-sQ has approximately constant overhead, regardless of odes, this results in a minimum overhead of 45,000 packets. The movement rate or offered traffic load. This constant behavior arises ariable part of the overhead consists of the routing packets tora because each destination d broadcasts a periodic update with a new uses to create and maintain routes, multiplied by the number of sequence number every 15 seconds. With 50 unsynchronized nodes retransmission and acknowledgment packets IMEP uses to ensure in the simulation, at least one node broadcasts a periodic update dur- their reliable, in-order delivery ing each second. DSDV-SQ considers the receipt of a new sequence In many of our scenarios with 30 sources, TORA essentially number for a node to be important enough to distribute immediately derwent congestive collapse. A positive feedback loop developed in (Section 3. 1), so each node that TORA/MEP wherein the number of routing packets sent caused ates a triggered update. These triggered updates flood the network erous MAC-layer collisions, which in turn caused data, ACK, and as each node receiving one learns a new sequence number and so HELLo packets to be lost. The loss of these packets caused IMEP to also generates a triggered update. Each node limits the rate at which erroneously believe that links to its neighbors were breaking, eve it sends triggered updates to one per second, but since there is at least
0 100 200 300 400 500 600 700 800 900 0 5,000 10,000 15,000 20,000 25,000 30,000 35,000 40,000 45,000 50,000 Pause time (secs) Routing overhead (packets) 10 sources 20 sources 30 sources (a) DSDV-SQ 0 100 200 300 400 500 600 700 800 900 0 5,000 10,000 15,000 20,000 25,000 30,000 35,000 40,000 45,000 50,000 Pause time (secs) Routing overhead (packets) 10 sources 20 sources 30 sources (b) DSR 0 100 200 300 400 500 600 700 800 900 0 45,000 90,000 135,000 180,000 500,000 1,500,000 2,500,000 3,500,000 Pause time (secs) Routing overhead (packets) 10 sources 20 sources 30 sources (c) TORA 0 100 200 300 400 500 600 700 800 900 0 20,000 40,000 60,000 80,000 100,000 120,000 140,000 160,000 180,000 Pause time (secs) Routing overhead (packets) 10 sources 20 sources 30 sources (d) AODV-LL Figure 5 Routing overhead as a function of pause time. TORA and AODV-LL are shown on different vertical scales for clarity (see Figure 3). initiates about 2200 route discoveries per 900-second simulation run, resulting in around 110,000 ROUTE REQUEST transmissions. In contrast, DSR limits the scope and overhead of ROUTE REQUEST packets by using caching from forwarded and promiscuously overheard packets and using non-propagating ROUTE REQUESTs as described in Section 3.3.2, which results in DSR sending only 950 non-propagating requests and 300 propagating requests per simulation run. TORA’s overhead is the sum of a constant mobility-independent overhead and a variable mobility-dependent overhead. The constant overhead is the result of IMEP’s neighbor discovery mechanism, which requires each node to transmit at least 1 HELLO packet per BEACON period (1 second). For 900-second simulations with 50 nodes, this results in a minimum overhead of 45,000 packets. The variable part of the overhead consists of the routing packets TORA uses to create and maintain routes, multiplied by the number of retransmission and acknowledgment packets IMEP uses to ensure their reliable, in-order delivery. In many of our scenarios with 30 sources, TORA essentially underwent congestive collapse. A positive feedback loop developed in TORA/IMEP wherein the number of routing packets sent caused numerous MAC-layer collisions, which in turn caused data, ACK, and HELLO packets to be lost. The loss of these packets caused IMEP to erroneously believe that links to its neighbors were breaking, even in the pause time 900 scenarios when all nodes were stationary. TORA reacted to the perceived link breakages by sending more UPDATEs, which closed the feedback loop by directly causing more congestion. More importantly, each UPDATE sent required reliable delivery, which increased the system’s exposure to additional erroneous link failure detections, since the failure to receive an ACK from retransmitted UPDATEs was treated as a link failure indication. In the worst runs, TORA generated over 10 million objects, which IMEP aggregated into 1.6 million packets requiring reliable delivery. In the few 30-source runs where congestion did not develop, the overhead varied from 639,000 packets at pause time 0 to 47,000 packets at pause time 900. DSDV-SQ has approximately constant overhead, regardless of movement rate or offered traffic load. This constant behavior arises because each destination D broadcasts a periodic update with a new sequence number every 15 seconds. With 50 unsynchronized nodes in the simulation, at least one node broadcasts a periodic update during each second. DSDV-SQ considers the receipt of a new sequence number for a node to be important enough to distribute immediately (Section 3.1), so each node that receives D’s periodic update generates a triggered update. These triggered updates flood the network, as each node receiving one learns a new sequence number and so also generates a triggered update. Each node limits the rate at which it sends triggered updates to one per second, but since there is at least 9
d:古 th lenath Figure 7 Comparison of the fraction of application data packets Figure 6 Difference between the number of hops each packet cessfully delivered as a function of pause time. Speed is I m/s took to reach its destination and the optimal number of hops required. Data is for 20 sources one new sequene ber per second, every node updates at the maximum permitted rate. Therefore, periodic action of dsDv-SQ is once per 15 seco effective rate of a group of nodes is one update per node pe an overhead of 45,000 packets for a 900-second, 50-node simulation 5.4 Path Optimality Details As described in Section 4. an internal mechanism of our simulato nows the length of the shortest possible path between all nodes in the network at any time and labels all packets with this path length when they are originated. Figure 6 shows the difference between by data packets. a difference of 0 means the packet took a shortest ath, and a difference greater than 0 indicates the number of extra hops the packet took Both dsDv-sQ and dsr use routes very close to optimal. TORA and AODV-LL each have a significant tail, taking up to hops longer than optimal for some packets, although TORA was Figure 8 Comparison of the number of not designed to find shortest paths. For space reasons, Figure 6 as a function of pause time. Speed is 1 m/s aggregates the data from all pause times into one graph. When the data are broken out by pause time, DSDV-SQ and dsr do very well separation between DSR and AODV-LL, regardless of pause time, with no statistically significant change in more effective at lower speeds where the s caching i Is even AODV-LL, on the other hand respect to pause time in the length of the routes they use relative to Due to its largely periodic nature, DSDV-sQ continues to have a constant overhead of approximately 41,000 packets, while tORas the shortest possible routes. When node mobility is very low, they overhead is dominated by the link/status sensing mechanism ofIMEP se routes that are significantly closer to the shortest possible routes which amounts to one packet per node per second, or a total of 45,000 than when nodes are moving ackets per simulation(Section 5.3) 5.5 Lower Speed of Node Movement 6 Additional observations n order to explore how the protocols scale as the rate of topology hange varies, we changed the maximum node speed from 20 m/ 6.1 Overhead in Souree Routing Protocols to 1 m/s and re-evaluated all four protocols over scenario files using When comparing the number of routing overhead packets sent by this lower movement speed. Figures 7 and 8 show the results of this each of the protocols, DSR clearly has the lowest overhead ( Figure 5) experiment when using 20 sources. All of the protocols deliver more The data for 20 uced in Figure 9(a)on a semi-I than 98.5% of their packets at this movement speed. Unlike in the axis for clarity. However, if routing overhead is measured in bytes O m/s scenarios, where DSDV-SQ could not converge, it delivers and includes the bytes of the source route header that DSR places in excellent performance in the I m/s scenarios each packet, DSR becomes than AODV-LL except Even at this slower rate of movement, each of the routing protocols at the highest rates of mobility, although it still transmits fewer bytes ounts of overhead. Neither DSr of routing overhead than does dsdv-sQ or TORA. AODV-LL uses AODV-LL were seriously challenged by this set s,as a Route Discovery mechanism based on DSR's, but it creates hop- ases only mildly as pause time decreases. The by-hop routing state in each node along a path in order to eliminate
0 1 2 3 4 5 6 7 8 9 10 >10 0 50,000 100,000 150,000 200,000 250,000 300,000 350,000 400,000 Number of packets Path length difference from shortest (hops) DSDV−SQ TORA DSR AODV−LL Figure 6 Difference between the number of hops each packet took to reach its destination and the optimal number of hops required. Data is for 20 sources. one new sequence number per second, every node transmits triggered updates at the maximum permitted rate. Therefore, although the base periodic action of DSDV-SQ is once per 15 seconds, the effective rate of a group of nodes is one update per node per second, yielding an overhead of 45,000 packets for a 900-second, 50-node simulation. 5.4 Path Optimality Details As described in Section 4, an internal mechanism of our simulator knows the length of the shortest possible path between all nodes in the network at any time and labels all packets with this path length when they are originated. Figure 6 shows the difference between this shortest path length and the length of the paths actually taken by data packets. A difference of 0 means the packet took a shortest path, and a difference greater than 0 indicates the number of extra hops the packet took. Both DSDV-SQ and DSR use routes very close to optimal. TORA and AODV-LL each have a significant tail, taking up to 4 or more hops longer than optimal for some packets, although TORA was not designed to find shortest paths. For space reasons, Figure 6 aggregates the data from all pause times into one graph. When the data are broken out by pause time, DSDV-SQ and DSR do very well regardless of pause time, with no statistically significant change in optimality of routing with respect to node mobility rate. TORA and AODV-LL, on the other hand, each show a significant difference with respect to pause time in the length of the routes they use relative to the shortest possible routes. When node mobility is very low, they use routes that are significantly closer to the shortest possible routes than when nodes are moving. 5.5 Lower Speed of Node Movement In order to explore how the protocols scale as the rate of topology change varies, we changed the maximum node speed from 20 m/s to 1 m/s and re-evaluated all four protocols over scenario files using this lower movement speed. Figures 7 and 8 show the results of this experiment when using 20 sources. All of the protocols deliver more than 98.5% of their packets at this movement speed. Unlike in the 20 m/s scenarios, where DSDV-SQ could not converge, it delivers excellent performance in the 1 m/s scenarios. Even at this slower rate of movement, each of the routing protocols generated very different amounts of overhead. Neither DSR nor AODV-LL were seriously challenged by this set of scenarios, as the overhead increases only mildly as pause time decreases. The 0 100 200 300 400 500 600 700 800 900 0.95 0.955 0.96 0.965 0.97 0.975 0.98 0.985 0.99 0.995 1 Pause time (secs) # data packets received / # data packets sent DSDV−SQ TORA DSR AODV−LL Figure 7 Comparison of the fraction of application data packets successfully delivered as a function of pause time. Speed is 1 m/s. 0 100 200 300 400 500 600 700 800 900 0 10,000 20,000 30,000 40,000 50,000 60,000 70,000 Pause time (secs) Routing overhead (packets) DSDV−SQ TORA DSR AODV−LL Figure 8 Comparison of the number of routing packets sent as a function of pause time. Speed is 1 m/s. separation between DSR and AODV-LL, however, has grown from a factor of 5 to nearly a factor of 10 because DSR’s caching is even more effective at lower speeds where the cached information goes stale more slowly. Due to its largely periodic nature, DSDV-SQ continues to have a constant overhead of approximately 41,000 packets, while TORA’s overhead is dominated by the link/status sensing mechanism of IMEP, which amounts to one packet per node per second, or a total of 45,000 packets per simulation (Section 5.3). 6 Additional Observations 6.1 Overhead in Source Routing Protocols When comparing the number of routing overhead packets sent by each of the protocols, DSR clearly has the lowest overhead (Figure 5). The data for 20 sources is reproduced in Figure 9(a) on a semi-log axis for clarity. However, if routing overhead is measured in bytes and includes the bytes of the source route header that DSR places in each packet, DSR becomes more expensive than AODV-LL except at the highest rates of mobility, although it still transmits fewer bytes of routing overhead than does DSDV-SQ or TORA. AODV-LL uses a Route Discovery mechanism based on DSR’s, but it creates hopby-hop routing state in each node along a path in order to eliminate 10