From kwalsh@CS.Cornell.EDU Mon Sep 30 13:23:19 2002 Received: from kwalsh.cs.cornell.edu (dhcp98-75.cs.cornell.edu [128.84.98.75]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8UHNJh25784 for ; Mon, 30 Sep 2002 13:23:19 -0400 (EDT) Message-Id: <5.1.1.6.0.20020930130038.00a7d210@popsrv.cs.cornell.edu> X-Sender: kwalsh@popsrv.cs.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Mon, 30 Sep 2002 13:23:18 -0400 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 23 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols This paper makes a very strong contribution: a systematic evaluation and comparison of popular ad hoc routing protocols using a detailed simulation. The DSR (written by two of the authors of this paper), AODV, TORA, and DSDV protocols are implemented, modified (small but significant optimizations), and compared, and several interesting insights are presented based on the resulting data. The simulation is based on ns, with custom and third-party extensions for modeling a mobile multi-hop wireless ad hoc network. The physical layer is modeled with a two-ray propogation model (based on the characteristics of the WaveLAN wireless network card). The link layer implements a complete IEEE 802.11 MAC protocol. Additionally, a berkley-style ARP was implemented for all protocols, since they use IP addresses and function at the network layer. Common optimizations for all protocols included adding jitter to periodic broadcasts and control reply messages, priority for control messages in the send queue. All but DSDV also took advantage of MAC layer link breakage detection. Overall, the authors find that DSR finds close to optimal routes, has low overhead, and a high message send success rate compared to all other algorithms, and performs well over all ranges of mobility and send patterns (This was unsurprising, as the authors wrote DSR). DSDV, even in modified form, could not converge for the high-mobility cases. TORA suffered from congestion collapse problems in nearly all cases, and had extremely high overhead. AODV performed well but had overhad an order of magnitude larger than that of DSR. Some other interesting conclusions were: - Alternate routes are very important, especially in high-mobility situations. Just witness the benefit of DSR's TTL=1 query to probe neighbor caches. - Broadcasts are indeed less reliable (92%) than unicast (98%) - Piggybacking route control on data is free (or so the authors seem to claim), as in the case of DSR's source-route headers on data packets. This may indeed be the case if one considers battery power and channel reservation. - Beacon messages are really bad. - Be careful of congestion feedback mechanisms, such as found in TORA (a link failure detection due to congestion causes a storm of control messages, adding to the congestion and prompting more link failure detections). Some comments are in order: - Most simulations were done at a mobility rate of 20 m/s, or roughly 45 miles per hour. This seems awfully fast. What motivated this choice (other than making DSR look good)? - The reasons for disregarding MAC layer link breakage in DSDV is not clear to me. Why would an infinite metric broadcast from, say, node N, infect the entire network? Shouldn't it only erase those routes to A passing through N? - In all cases, one gets the feeling that very slight and subtle design changes can seriously alter the performance of the protocols (ie, the MAC/DSDV problem above), making the comparisons less meaningful. From mr228@cornell.edu Mon Sep 30 22:41:47 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g912fkh26416 for ; Mon, 30 Sep 2002 22:41:47 -0400 (EDT) Received: from cornell.edu (syr-24-58-48-238.twcny.rr.com [24.58.48.238]) by cornell.edu (8.9.3/8.9.3) with ESMTP id WAA00538 for ; Mon, 30 Sep 2002 22:41:45 -0400 (EDT) Message-ID: <3D990B6A.7DEEBE8E@cornell.edu> Date: Mon, 30 Sep 2002 22:41:46 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 23 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper presents a comparison of 4 wireless routing protocols: DSDV, TORA, DSR, and AODV. Their criticism of previous simulation results is that the authors of those papers used fundamentally flawed simulators and/or made too many over-simplifications of the underlying hardware. To generate this paper's results they have made significant modifications to NS2 in order to achieve a much more realistic model of the hardware. Their environment takes into account attributes of the routing protocols themselves, characteristics of the environment (ground reflection, etc.), and even characteristics of the wireless hardware they are simulating. Two other key points regarding their setup: (1) They use a rectangular (not square) bound for their environment. This seems more realistic as packets will need to travel longer routes given some density (2) They allow for host mobility via a random waypoint model; each node pauses for N seconds and then selects a new location and moves there with some velocity. They ran experiments with two velocities: 1m/s and 20m/s. They then run a number of simulations of each protocol and record several of the more interesting metrics. Their results and conclusions seem to indicate that TORA is the worst performer and AODV and DSR do significantly better than the other two and reasonably close to each other. Based strictly on these findings I would expect DSR to be the best performer especially given high mobility. Although it strives to produce a 'correct' hardware model, this paper uses a much less realistic traffic pattern model. Future work might look at using (and perhaps gathering) 'real-world' usage statistics and mobility patterns. Also placing the nodes initially in a uniformly dense environment is not realistic either. People (and therefore their devices) tend to congregate into dense clusters with regions of sparse population between them. One additional criticism is that their "random waypoint model" doesn't seem to be realistic at all, especially with all nodes stationary for N seconds and then all nodes moving simultaneously at time=N. While it's not reasonable to expect that any comparison can try ALL possible settings of the configurable parameters of the algorithms, it's not clear that their results are independent of their choice(s) for them. For example, their conclusion that TORA is the worst performer may be an artifact of their parameter choices. Some effort should have been made to optimize each protocol's parameters. -- Mark Robson From jsy6@postoffice2.mail.cornell.edu Mon Sep 30 23:58:43 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g913whh10372 for ; Mon, 30 Sep 2002 23:58:43 -0400 (EDT) Received: from Janet.cornell.edu (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id XAA04036 for ; Mon, 30 Sep 2002 23:58:37 -0400 (EDT) Message-Id: <5.1.0.14.2.20020930235725.00b3d298@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Mon, 30 Sep 2002 23:58:07 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 23 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The major contribution of this paper is the specifications on providing a realistic simulation of a wireless ad hoc network and the relative performance analysis of the routing protocols DSDV, TORA, DSR, and AODV. The simulation was performed using an ns-2 network with the following extensions: node mobility, an accurate model of the MAC and physical layer, and radio network interfaces. Prior to this paper, no known performance result for AODV existed and results for DSDV, TORA, and DSR were not reliable due mainly to unrealistic simulations. The results of TORA greatly differs from previous work due to the many simplifications made in past environment simulations. Some of the differences in results are also due to the implementation decisions of the protocols. For DSDV, link layer breakage detection from the MAC layer was not used, unlike the other three protocols, due to the decrease in performance. Updates were triggered by the receipt of a new sequence number for a destination instead of a new metric. This approach resulted in quicker link breakage detection and thus less data packets being dropped. TORA's simulation required the period of time for when IMEP must queue objects to be specified. This time was chosen uniformly between 150ms and 250ms since these times offered the best balance between package overhead and routing protocol convergence. In order to avoid long routing loops, TORA routing messages for aggregation were not delayed. DSR routes were only bi-directional and all nodes operated in promiscuous mode. The implementation of AODV differ the most from its specifications than the other protocols. The specifications for AODV called for periodic Hello messages in order to detect link breakages. The implementation of AODV used link layer feedback instead of periodic HELLO messages, changing link detection to be only on-demand. Also, a significantly shorter timeout for retrying route requests was used. The original timeout value was 120 seconds, the implementation used a timeout value of 6 seconds. The protocols were compared using the following 3 metrics: packet delivery ratio (in order to measure loss rate, completeness, and correctness), routing overhead where each hop counts as one transmission (to calculate scalability and battery power consumption), and path optimality (to measure the ability of the protocol to efficiently use network resources). DSR, based on these metrics, performed the best and was closely followed by AODV. TORA by far performed the worst. TORA's performance in packet delivery and overhead was very varied and surprisingly bad. This result was mainly due to congestion problems that caused failure in convergence. TORA"s link reversal process results in the creation of short-lived routing loops which was the cause for the majority of dropped packets. The loops that developed in TORA caused many MAC-layer collisions which in turn caused the loss of ACK and hello packages. These packet losses lead IMEP to believe that neighboring links were broken which led to. In one of the runs, TORA generated over 10 million objects. The simulations and comparative analysis, I felt, were well carried out and much needed, but more performance analysis can be done. Maybe tests can be done using different metrics such as energy conservation. The paper claims that the less hops (or routing overhead), the more energy is conserved, but sometimes more energy can be conserved by providing routes with more hops. Using energy conservation would thus go against the metric of the shortest route. I feel that the shortest route may not be the best metric to use since some protocols, such as TORA, specifically sacrifice route optimality for other metrics of performance. Also, instead of only using 50 mobile hosts, it would also be useful to see what the maximum density each protocol can take before it performance drops significantly. This analysis was only done with TORA since TORA begins to perform very badly for more than 30 hosts. The simulation was more realistic than the previous known simulations, but there are improvements that can make the simulation more realistic. In the simulation, the traffic sources were constant bit rate sources. It would be more realistic if the sending rate was not fixed. Also, since none of the protocols deal with load balancing, packets sizes were reduced to 64 bytes in an attempt to reduce congestive effects. Although a variety of workloads were tested, none of these workloads were workloads from real-life. From bd39@cornell.edu Tue Oct 1 00:02:23 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9142Mh11412 for ; Tue, 1 Oct 2002 00:02:22 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id AAA24776 for ; Tue, 1 Oct 2002 00:02:19 -0400 (EDT) Date: Tue, 1 Oct 2002 00:02:19 -0400 (EDT) From: bd39@cornell.edu X-Sender: bd39@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 23 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Paper 23 This paper fills in an area of complaint about many previous papers - which is the lack of a quantitative simulation of the protocols discussed. The authors use a modified version of the NS2 simulator to evaluate the performance of four routing protocols, DSDV, DSR, AODV and TORA. A realistic radio propagation model and 802.11b is used for the link and MAC layer modeling. The communication model involved up to 50 nodes moving in a random waypoint model (select a destination, move to it, pause of a constant amount of seconds) communicating in a peer-to-peer fashion with fixed rate of traffic. The metrics they chose to measure were packet delivery ratio (packets reaching intended destinations), routing overhead (number of protocol packets sent) and path optimality (difference to optimal path length). The experimental results show several interesting points: - TORA's strong assumptions about reliable communication creates severe routing loop problems. This causes TORA to perform rather badly, as the traffic is CBR, meaning that TORA will be punished for any duration of a routing loop. - DSDV fails to converge given fast topological changes, which shows a problem for proactive protocols have: failing to keep up with the mobility rate. It is interesting to see that given a high rate of mobility, reactive protocols are able to maintain routes better. (This may be a failing of DSDV itself, and not proactive protocols in general.) - What AODV saves in packet bytes over DSR, it loses in terms of number of packets sent. - Paper seems to make a strong case for DSR, beating other protocols in almost all metrics. - Traffic patterns seems to be very important in the performance of the routing protocol. Given the speed of movement of the nodes and the communication pattern (CBR with 10, 20, 30 src nodes), it seems that the evaluation is geared towards the reactive destination oriented protocols (DSR, AODV). Given fewer sinks and many sources (i.e. a sensor network), it is concievable that TORA will perform much better than shown. - Constant bit rate traffic seems to favor DSR route caching, because packets are always sent to similar destinations from the same source. As always, this paper only covered a few points in the space of possible conditions to measure and compare these protocols, but it is definitely nice to see empirical (albiet simulated) results for these protocols. From hs247@cornell.edu Tue Oct 1 00:33:59 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-1.nyroc.rr.com [24.92.226.177]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g914Xwh18031 for ; Tue, 1 Oct 2002 00:33:58 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g914XtI09707 for ; Tue, 1 Oct 2002 00:33:55 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001003348.00b84a20@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 01 Oct 2002 00:34:25 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 23 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The main contribution of this paper was the creation of a simulator to compare 4 ad-hoc routing protocols that we have studied: DSDV, TORA, DSR, and AODV. These 4 protocols were implemented and their ability to react to topology change and handled varying traffic was compared. Their main metric was to see how each protocol performs under different conditions. Their simulator was based on "ns" a simulator built by Berkeley. In order to more accurately simulate a real environment extensions were added. They had a MAC layer which used RTS/CTS and a physical/data layer that more accurately models the real world. And also packet buffer and ARP was added to implement address resolution. Each protocol was implemented at the IP layer and a bunch of implementation decision were made for each one. In particular, two version of DSDV were created: DSDV (triggers update when new metric is received), and DSDV-Seq (triggers update when new seq # is received). In particular, they found DSDV-Seq to react better because it updates faster and therefore detects link breakages faster. Most of the paper looked at DSDV-Seq instead of DSDV. In all, each protocol did well in some conditions while failed in others. For example, for TORA, when 30 sources were used, its success ratio for delivering packets dropped from when 10 or 20 sources were used. When looking at routing overhead, DSDV-Seq stays constant, while all the other ones drop as pause time increases and the number of sources decreases. The authors explain this is because no matter what, each node still sends periodic update packets. At low moving speeds, the ondemand protocols (DSR and AODV) in general have a lower overhead. Another interesting fact found was that 99.8% of unicast packets are received compared to 92.6% of broadcasts. (Though unicast requires more overhead). I thought this paper was very well done, and many insights were learned on why these protocols performed differently under different conditions. Though one thing must be looked at is the design decisions. Naturally, the results of the protocols rely heavily on their implementation and parameter choices. I also found it interesting that they did not consider using TCP/IP, since many networks use that today. (They stated that TCP/IP changes the load depending on the connection). It would have been interesting to see how this would affect the results. Also, implementations of hybrid and cluster algorithms on this simulator would be interesting. From shafat@CS.Cornell.EDU Tue Oct 1 01:31:11 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g915VBh27655 for ; Tue, 1 Oct 2002 01:31:11 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615 PAPER 23 Date: Tue, 1 Oct 2002 01:31:11 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134F98@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 23 Thread-Index: AcJnh7GyAmxOka8qTSaf9zUJ2Tc4tg== From: "Syed Shafat Zaman" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g915VBh27655 This paper does a performance analysis of four of the major routing protocols used in multi-hop wireless ad hoc networks. The main contribution of the paper is twofold. Firstly, in order to implement an unbiased and more realistic simulation environment in which to test the protocols, the authors enhance the ns simulator by adding a number of extra features. Accordingly, these modifications presented them with a more accurate simulation of mobile wireless networks. Secondly, there is the performance comparison of the routing protocols - DSDV, DSR, TORA and AODV. A large number of simulations were carried out using these protocols under varying conditions and the results are presented in the evaluation section of the paper. >From an objective point of view, the paper does a commendable job of comparing the chosen protocols on the basis of reliability, load-balancing and path optimality. Each of their performance is gauged by the same yardstick owing to the way the simulator was set up - in order to present each protocol with the exact same scenario. The paper, however, could perhaps elaborate a little more on their reasons for the choice of protocols, especially the justifications for comparing fundamentally different proactive and reactive protocols. It is also mentioned in detail what modifications were made to each protocol prior to the simulation runs, to improve their performance. This action, although useful for other purposes, does not necessarily compare the actual protocols as dictated by their original specifications. It would have been interesting to test them in the "as is" condition. The simulations could have been made even more realistic by including a higher number of nodes. Although, the scalability factor of each protocol was implicitly tested by the "routing overhead" metric, having a larger setting could have given us a better picture. Nevertheless, I believe, the paper presents enough data and sufficient justifications to provide a good performance comparison of the protocols in question. From mvp9@cornell.edu Tue Oct 1 01:44:09 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g915i8h29212 for ; Tue, 1 Oct 2002 01:44:08 -0400 (EDT) Received: from zoopark.cornell.edu (syr-24-58-46-186.twcny.rr.com [24.58.46.186]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA11315 for ; Tue, 1 Oct 2002 01:44:08 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001014331.01a64ec0@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 01 Oct 2002 01:44:07 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 23 Mime-Version: 1.0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The Broch et al. paper is a welcome change in a flow of new ideas backed up by little if any analysis.  It performs a realistic simulation systematically comparing the performance of 4 diverse protocols  AODV, TORA, DSR and DSDV with respect to packet delivery ratio, routing overhead and path optimality of each.  What may be most important, they introduce modifications to the ns-2 simulator that allows modeling of the link and physical layer behavior under each of the protocols.  They also add small but significant modifications to the protocols tested.  The strong points of this study are the novelty of comparing those protocols and the quality of that comparison.
This quality arises from several factors.  The optimizations introduced to the protocols fill the inadequacies of their descriptions and the simple pitfalls that would make comparison unfair.  The implementation and the physical model are verified by their authors and an expert respectively.   The simulation benefits from the fact that each protocol was run on a series of identical scenarios, the mostly well-chosen metrics, and the range of parameters explored.  At the same time, the last two are far from perfect -- there is no speed/delay metric and the network is small, as usual  only 50 nodes.  There are also two poor design choices that considerably affect the outcome.  The data packet size, originally to be 1024B was reduced to only 64B, potentially altering the results of the overhead/throughput comparisons.  Finally, ignoring MAC transmissions on behalf of the routing protocols in the overhead metric considerably distorts the results, as is shown in the follow-up Das et al. paper.  The mobility model is questionable as usual  20m/s seems a rather high speed, but the authors justify such claims as necessary to challenge the protocol.
        Most of all, this paper illustrates the lesson that small design changes and parameter decisions can have large performance consequences.  The results also allow informed decisions as to which protocols are best for particular situations, and where they need improvement.  These improvements offer some of logical extensions to this research.  Comparison to other MANET protocols, particularly the hybrid ones, is another.  The simulation itself can be improved by targeting larger networks and higher data rates. 
From sc329@cornell.edu Tue Oct 1 02:22:35 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g916MZh06149 for ; Tue, 1 Oct 2002 02:22:35 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id CAA07485 for ; Tue, 1 Oct 2002 02:22:34 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001022118.00b1fe30@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 01 Oct 2002 02:22:34 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 23 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed submitted by - sangeeth Chandrakumar A perfomance comparison of Multi-Hop wireless Ad hoc network routing protocols This paper is the first of its kind in providing a realistic, quantitive analyis comparing the perfomance of variety of multoi-hop wireless ad hoc network routing protocols. It compares DSDV, TORA, DSR and AODV. The simulation environment models both free space model as well ground reflection according to the signal attenuation. The pwer levels of the received packet is compared to the carrier sense threshold and receiver threshold to decide the action to be taken on it. Packet buffering is done at each node that holds up to 50 packets. The authors uses a modified ns-2 network simulator to perform the tests. The authors suggests some improvements to each of the protocols. Implementing DSDV-SQ that triggers updates with each new sequence number as opposed to new metric only; aggregating TORA and IMEP messages; using only bi-directional links in DSR to support lower layers; and implementing AODV-LL to replace periodic HELLO messages.The protocols are tested for 210 different scenario files with 50 nodes, and with two different max speeds, 1m/s and 10m/s, over which speed is uniformly distributed. The test with varying number of nodes over different fixed movemrnt patterns. The simulations presented collects the three metrics: packet delivery ratio, routing overhead and path optimality. The only proactive protocol, DSDV-SQ perfomred poorly with packet delivery unde high mobility and exhibited constant overhead due to its regular broadcasting of topology information. TORA though slightly better than DSDV was limited due to the formation of short lived loops. resulting in many packet loss. The metrics form DSR were the best among the four. DSR effectively caches routes and reuses it to have significant improvements. Packet delivery was good with AODV, but the overhead was significant with high mobility rates This paper addresses compatibility issues of routing protocols with the physical and link layer asides from providing significant results, and tests the true functionality of the protocols without making simplifying assumptions. From mp98@cornell.edu Tue Oct 1 09:24:25 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91DOPh21734 for ; Tue, 1 Oct 2002 09:24:25 -0400 (EDT) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id JAA00818 for ; Tue, 1 Oct 2002 09:24:24 -0400 (EDT) From: mp98@cornell.edu Date: Tue, 1 Oct 2002 09:24:28 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 23 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <1CE2DB2C-D541-11D6-A228-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.546) This is a kind of survey paper, but a necessary one, filling in the gaps that have come up again and again when reviewing previous papers: The lack of real simulaton and comparisons. The authors of this paper modified the ns-2 network simulator in several ways: 1) Locality/Mobility 2) A model for radio transmission (i.e. the 1/r^4 drop off) 3) Some modification to the physical layer model 4) An implementation of 802.11 MAC On top of this model they programed implementations of four of the protocols we've discussed in this course: DSDV, TORA, DSR, and AODV. Some minor modifications were made to certain protocols in cases where the specification was equivocal (for example, they split DSDV: sending out an update as soon as a new sequence number yields DSDV-SQ whereas only sending one out when the distance to a node changes yields DSDV) or where the nature of the 'physical' environment allowed them to make optimizations (for example, AODV-LL uses link layer feedback to detect broken links which avoids the overhead of numerous HELLO packets). A number of different scenario files were created so each algorithm could be tested under ther same circumstances. Their implementation of the simulation environment had something they call the "random waypoint" model for node movement: Pause, choose a random location, and move there with a random speed. Seven different pause times and two different maximum speeds were used and 10 random movement patterns were created for each combination. The communications model seemed to be choosing a set of nodes as constant transmitters and selecting destinations randomly (I could not find where destinations were specified.) The results of the simulation may basically be summarized as follows: DSR seems to do the best overall, followed by AODV, although the overhead of extra information in each packet gives DSR a higher overhead over all even though it sends less packets (this might not matter, if the RTS/CTS cost is much higher than the transmission cost: In this case, it is more important to send fewer packets than to send smaller ones). Tora does decent transmission but involves a lot of control packets (adding more network sources also seemed to crush Tora). Part of this overhead to TORA could be caused by the complicated system it is based on top of (IMEP) because Tora requires reliable transmissions to avoid loops. Obviously this is a step in the right direction. But it would be nice to see the network simulation re-implemented using a model of node movement and communication taken from real world analysis of networked user behavior: People do not wander randomly around a room, while listening to only ten people in the room talk to everyone else. From adam@graphics.cornell.edu Tue Oct 1 09:58:42 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91Dwfh28485 for ; Tue, 1 Oct 2002 09:58:42 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g91Dwa0k029323 for ; Tue, 1 Oct 2002 09:58:36 -0400 (EDT) Date: Tue, 1 Oct 2002 09:58:32 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 PAPER 23 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII A Performance Comparision of Multi-Hop Ad Hoc Network Routing Protocols. This paper gives a brief summary and comparision of the following protocols: TORA, DSDV, DSR and AODV. Each of these protocols are presented briefly in how they work and how they are implemented. For DSDV they implemented it two different ways, one w/ link layer breakage and one w/out. They noticed that the link layer breakage did much worse overall than w/out it. For TORA they implemented IMEP to provide reliable in order delivery (something that the other protoocols didn't have the advantage/disadvantage of using). FOR DSR the spent some time making optimizations (like gratitious Route Reply). Since DSR supports unidirectional links it had to be adapted to work w/ 802.11 (only supports bi-directional links) as well. For AODV there were two different implementations. The first being as-described-in-the-paper AODV and the second AODV-LL. AODV-LL differed from the original AODV by only using link layer notificaion of link state, eliminating the HELLO beacons that were being passed around. AODV-LL performed significantly better than AODV so it was used for testing. I think that the presentation of each alg (assuming you knew something about ad hoc nets and proactive/reactive protocols) was very well done. The time spent explaining how 802.11 would be simulated, the ns-2 improvements for simulation and the implementation changes were all very well presented. I think the graphs were clear and presented good information on collected data. I however raise the following questions with there simulations. First they have no truly random network model. They have a contrived CBR scheme which doesn't actually model anything close to random flow of a network (wouldn't some hosts be dormant, some overloaded, and some fluctuating?). The movement model of move, pause, move is a little far fetched too, I think that 20 m/s is a lot of speed, unless we are having an ad-hoc net in cars now, but then it would really be relative speed of the group. (imagine 15 cars moving down a highway in one direction)... I think that for all the effort that was put into thinking about setup, implementation and data collection they could have designed a better network simulation. From tmroeder@CS.Cornell.EDU Tue Oct 1 10:51:41 2002 Received: from dhcp99-233.cs.cornell.edu (dhcp99-233.cs.cornell.edu [128.84.99.233]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91Epfh10294 for ; Tue, 1 Oct 2002 10:51:41 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g91Epep06063; Tue, 1 Oct 2002 10:51:40 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15769.46716.560859.915431@dhcp99-233.cs.cornell.edu> Date: Tue, 1 Oct 2002 10:51:40 -0400 To: Emin Gun Sirer Subject: 615 PAPER #23 X-Mailer: VM 7.07 under Emacs 21.2.1 This paper appears to be the first to give detailed performance analysis comparing 4 different routing protocols in the ad hoc space. They examine DSDV, TORA, AODV, and DSR, and seek to determine the relative strengths and weaknesses of these protocols using the random-distribution, random-motion model for low to mid traffic loads. DSR comes out as a clear winner just about everywhere, with AODV in close second. The other two protocols have significant weaknesses in some areas, and hold up passably well in the rest. It is easy to be skeptical of a paper by the authors of DSR which happens to find that DSR wins easily over all the other protocols against which they compared it, but their simulations seem, in fact, to be addressing the very complaints we have leveled against other simulations: they seem to try to model the wireless medium carefully, and account for all the artifacts of this medium which can cause problems to the protocols. One of my major concerns, however, is with the speed of motion: all of the protocols perform well at 1 m/s, and the only other speed range for which they do the analysis 0-20 m/s, whose maximum is 72 km/h. At least in Vancouver, my home town, you would get a ticket for going this fast anywhere in the city, so it is hard to imagine the relevance of examining this speed, which would only be valuable for cars moving in random directions on the freeway. Even the average speed of 10 m/s is 36 km/h, which is the school zone speed in the city, and so is not fast for a car, but is still quite fast for many other things, especially given the size of the area in which the nodes move. More reasonable speeds would be the speed people walk, which is close to 1 m/s (on the slow side) anyways. The authors comment that they have factored out the MAC-layer costs of the packets, claiming that the protocols could be run over many different implementations, and so they wanted to abstract away. As the other paper for today shows, they perhaps ought to have taken them into consideration, for they would have given a clearer picture of what the differences are between DSR and AODV. From xz56@cornell.edu Tue Oct 1 11:09:48 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91F9lh13493 for ; Tue, 1 Oct 2002 11:09:48 -0400 (EDT) Received: from XIN (dhcp-ece-167.ece.cornell.edu [132.236.232.167]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA08579 for ; Tue, 1 Oct 2002 11:09:47 -0400 (EDT) Message-ID: <004501c2695c$94afc490$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 23 Date: Tue, 1 Oct 2002 11:09:45 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 This paper compares the performance of four ad hoc routing protocols: DSDV (proactive), TORA (reactive multipath), DSR (reactive, source routing) and AODV (reactive, table-driven). The main contribution is the introduction of a more accurate simulation environment, which is also used in the latter paper. RF transmission model is proper with different cases of small and large scales. The packet reception uses two threshold to distinguish between noise, signal or collision. The MAC layer uses the protocol proposed by IEEE802.11 which is very realistic. The simulation was reasonably run in different movement model characterized by pause time and speed uniformly distributed within different ranges. The metric used are packet delivery ratio, routing overhead, path optimality. Usually the two significant parameters to networks are throughput and delay. It's strange that delay is not included into the simulation. Packet delivery ratio studied in different data rate at sources can reflect the throughput of network and offer the performance of the protocol in more detail. No wonder DSDV performs poorly in both delivery ratio (because of the collision) and routing overhead (periodic routing info broadcast) except on path optimality, which is relatively a minor aspect. TORA also, takes little advantages in multiple path options and has a much worse performance than DSR and AODV, since it's kind of table-driven and proactive in updating the heights of nodes. DSR and AODV are extremely similar as far as this paper notice, although much more is talked about in the latter paper. This paper maybe was the first one introducing this simulation model, so most of the discussion are focus on the model itself. Not enough interpretation of results is offered in terms of the protocol. From pj39@cornell.edu Tue Oct 1 11:14:09 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FE8h14506 for ; Tue, 1 Oct 2002 11:14:08 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA03118; Tue, 1 Oct 2002 11:14:06 -0400 (EDT) Date: Tue, 1 Oct 2002 11:14:06 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200210011514.LAA03118@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: pj39@cornell.edu Reply-To: pj39@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: pj39@cornell.edu X-Originating-IP: 128.84.223.189 Subject: 615 PAPER 23 A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols The major contribution of this paper is a proper simulation and comparison of four popular ad hoc routing protocols DSDV, TORA, DSR and AODV. Among these routing protocols DSDV is a strictly Proactive protocol whereas AODV and DSR are Reactive protocols. For conducting the simulations the authors have slightly modified and the protocols to get a several interesting results and data to compare the above mentioned protocols. For the simulations the authors modified the basic ns-2 simulator developed at UC berkeley to include ode mobility, realistic physical layer, readio network interface and IEEE 802.11 wireless LAN MAC protocol. The goal of the simulation was to measure the ability of the routing protocols to react to network topology changes. In order to realize this different protocols were challenged with identical loads and environment conditions. Each run of the simulator accepted different pre generated scenario files. In comparing the protocols the following metrics were evaluated - Packet Delivery ratio ie the ratio of no of packets originated by the no of packets delivered - Routing overhead ie the total no of routing or control packets transmitted. - Path optimality ie the difference between the no of hops the packet took to the shortest path. The results of the simulation can be summarized as below - all the protocosl deliver greater percentage of the originated data packets when there is little node mobility (this is obvious) - DSR and AODV-LL delivers over 95% od data packets regardless of the mobility - DSDV-SQ fails to converge at pause time (node remains stationary for pause time before moving) less 300 seconds. - In terms of routing overhead DSR has the least overhead and TORA has the maximum and the overhead for DSDV-SQ is nearly constant. Packet delivery ratio - DSDV-SQ fails to converge below pause time of 300. At lower pause time (high mobility) its delivery ratio drops to 70%. - TORA with 10 or 20 source nodes delivers between 90% - 95% of packets at highest mobility (pause time 0). With 30 or more sources the performance of TORA drops drastically.. - For DSR and AODV-LL packet delivery is independent of offered traffic load. Routing overhead - AODV-LL requires about 5 times the overhead of DSR. - DSDV-SQ has appx constant of overhead regardless of the traffic load. - TORA with 30 sources at many times collapses. Path optimality - DSDV-SQ and DSR routes are close to optimal - AODV-LL and TORA takes upto 4 or more hops longer than optimal routes. Overall the author finds that DSR has the lowest overhead. DSDV performs best when node mobility rate is low. TORA delivers over 90% with 10 or 20 sources but at 30 or more sources the network is unable to handle the traffic generated by the routing protocol. Finally AODV performs almost as well as DSR at all mobility and rates and movement speeds. From smw17@cornell.edu Tue Oct 1 11:23:59 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FNwh16609 for ; Tue, 1 Oct 2002 11:23:58 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA28753 for ; Tue, 1 Oct 2002 11:23:57 -0400 (EDT) Message-ID: <3D99BD44.6070006@cornell.edu> Date: Tue, 01 Oct 2002 11:20:36 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 23 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit A Performance Comparison of Multi-Hop Wireless Ad-Hoc Routing Protocols The simulation study is conducted using the ns discrete event simulator, with modifications. The authors modified the simulator to include a realistic physical layer model, including both free space and reflection conditions. They also account for the 802.11 MAC layer, collision effects (including reception through collisions), and the 802.11 DCF for unicast packets (RTS/CTS/ACK). On this base, the authors implement the various protocols, as well as ARP to support IP-based addressing. The researchers implemented four different routing algorithms (DSDV, TORA, DSR, and AODV) based on their specifications, but made a number of enhancements to each based both on interaction with the protocol designer(s) and on improvements observed during the simulation study to alleviate major issues encountered. The data traffic patterns are modelled by selecting a random location within a 1500m x 300m arena, and travelling there at a random speed (uniform distribution from 0 to max_speed). Once the destination is reached, the node remains stationary for an interval (pause_time) before selecting a new destination. Simulations were run for 900 seconds of simulated time, with pause times of 0, 30, 60, 120, 300, 600, and 900 seconds. A sequence of 70 movement patterns was generated, ten for each pause time value. Every protocol was characterized based on the same set of movement patterns. The maximum speed was usually 20 m/s, with some simulations at 1 m/s for comparison. Data was sent from 10, 20, or 30 originating sources at a rate of 4 packets/sec, with 64-byte packets to minimize congestive effects. A number of implementation details and decisions had to be made to perform the study, in order to adjust the expectations of a particular protocol to the reality that the 802.11 standard provides. With the exception of DSDV, all protocols relied on the MAC layer to detect link breakage and invalid next-hop routes. DSDV was the exception because the broadcast storm of invalidations that occurred when a neighbor lost its link would disconnect a node from the network until its next periodic update, which had a detrimental effect on network performance. DSDV was also implemented in two different variants, with the significant difference being the question over whether or not a new sequence number should be sufficient to start a routing update, or if the node should wait for a different metric instead. DSDV-SQ updates on every sequence update, whereas DSDV only updates on a metric change. In order to implement TORA, with its more stringent network requirements, it was run over IMEP, providing reliable, in-order data transport. IEMP was set to aggregate hello and ack packets for 150ms to 250ms, but did not delay routing messages. Delaying routing messages increased the lifetime of the temporary loops formed during TORA's network repair stage, and had a significant impact on overall performance. DSR was implemented by assuming bi-directional links, permitting simple route reversal for reply packets. The hop limit function was also added, permitting a node to query the caches of its neighbors, and implements aggressive use of the route cache to both create routes and recover from broken routes. Finally, AODV was also implemented in two different ways, one making use of the hello beacons, and one relying solely on the link layer to detect breakage. These are the AODV and AODV-LL protocols, respectively. The results presented here were quite interesting. Based on their simulated configurations, AODV-LL and DSR achieved better than 95% delivery of packets across all conditions. TORA was better than 90%, as was DSDV-SQ for pause times over 300s. For shorter pause times, DSDV-SQ suffered from convergence problems. With regards to packet overhead, DSR was the best of the four. TORA was the worst of the four, with very high overhead in highly mobile networks, and a constant overhead portion. AODV-LL was better, with a high overhead in highly mobile networks, but falling to near-DSR levels as the pause time increased. DSDV-SQ had a constant overhead irrespective of the network mobility. The difference between AODV-LL and DSR is reduced if one considers the byte overhead rather than the packet overhead, and AODV is indeed superior to DSR in many situations. The catch is to remember that the overhead to transmit a few extra bytes in a data packet is not directly comparable to the overhead to send additional packets, so that a byte for byte comparison may well not corrsepond to better real-world performance. Both DSR and DSDV-SQ gave close to optimal routes, whereas TORA and AODV had significant tails to their distributions, corresponding to routes that were longer than necessary (by hop count). The possible effects of congestion on the optimal routes was not discussed, and congestion was noted as a major issue in high-load networks, especially for TORA (presumably due to its very high overhead in highly dynamic networks). From ag75@cornell.edu Tue Oct 1 11:25:30 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FPUh16763 for ; Tue, 1 Oct 2002 11:25:30 -0400 (EDT) Received: from sanya (r105361.resnet.cornell.edu [128.253.240.52]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA24730 for ; Tue, 1 Oct 2002 11:25:30 -0400 (EDT) Message-ID: <001001c2695e$d9f85c90$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 23 Date: Tue, 1 Oct 2002 11:26:02 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4910.0300 In this paper the authors compare 4 routing protocols - DSDV, TORA, DSR, and AODV. It seems that their simulation is the first one to compare all of these protocols. The authors put in a lot of thought to ensure that their simulator was realistic and fair to all protocols. Their simulator is a modified version of the ns network simulator that provides an accurate simulation of the MAC and physical-layer behavior of the 802.11 standard, including a realistic wireless transmission channel model. In previous simulations, simulators were made using many simplifying and unrealistic assumptions. Thus, the results from these previous simulations are unreliable. The authors also tried to optimize each of the four algorithms to maximize their performance. This included modifications to the basic algorithms and picking optimal constants used by algorithms. The results of their simulations are quite interesting. One wonders why DSR outperforms all other algorithms and how this would change if the size of the network was 500 instead of 50. The usual complaints about uniform distribution and random movement of nodes apply to this simulation. Still, the fact that the authors used such a realistic simulator, a rectangular testing area, various movement speeds and various pause times makes this simulation an important contribution. From liuhz@CS.Cornell.EDU Tue Oct 1 11:30:34 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FUYh17783 for ; Tue, 1 Oct 2002 11:30:34 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615 PAPER 23 Date: Tue, 1 Oct 2002 11:30:33 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE639@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 23 Thread-Index: AcJpX3ut3pT20TQ+SFS/WZmA3QRA9w== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g91FUYh17783 A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols This paper makes contributions in two areas, as stated in the conclusion of the paper. First, it provides a ns-2 based simulator which can simulate the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, thus provides a powerful tool for evaluating ad hoc networking protocols and other applications. Second, This paper evaluates the packet-level performance of four multi-hop ad hoc network routing protocols, namely DSDV, TORA, DSR, and AODV. Among them, DSDV is a proacive protocol while the others are on-demand reactive protocols. DSDV and AODV uses hop-by-hop routing, while DSR is a source routing protocols. The paper shows how the choice of different mechanism can affect the performance of the routing protocols, thus a trade-off must be made to design a good routing protocol. Three metrics are used: packet delivery rate, route length, and routing load. In terms of route length, DSR behaves best and DSDV is also close to it, while TORA and AODV take some routes much longer than the shortest one. As for packet delivery rate, DSR and AODV always behave very well, above 95%, regardless the traffic load and mobility. DSDV fails converge under high mobility conditions and TORA exhibits a poor delivery rate with heavy traffic load. DSDV has a very steady routing overhead because of periodic advertisement. DSR's overhead is less than all the others because it has many mechanisms to limit the scope of the propagation of PREQ messages like aggressive cache, gratuitous forwarding and non-propagating PREQ, etc. TORA's overheard increases with the traffic load dramatically due to congestion. The simulation reflects the performance of these four protocols in some way. However, it misses a very important metric, that is routing delay. Proacitve protocols will beat reactive protocols in this aspect since it has all the routing information before it begin to send any data packets. Taking this metric into consideration, DSR won't appear so superior as it is now. The simulation characterize the mobility very well, using the combination of pause time and the speed to describe the mobility. However, it is not so complete in case of traffic load. The simulation uses CBR sources and constant packet sizes of 64. The only variable is the number of source. Howevers, as stated in another paper(615 PAPER 25), even with 30 sources, the overall traffic is still low. AODV actually outperforms DSR in high traffic load situation in most aspects except routing overhead. Another thing that may make this paper more beautiful is it can do some simulation with different number of nodes in the network, thus we can see the scalability of differect routing protocols. From ashieh@CS.Cornell.EDU Tue Oct 1 11:31:45 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FVjh18540 for ; Tue, 1 Oct 2002 11:31:45 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g91FVjR11481 for ; Tue, 1 Oct 2002 11:31:45 -0400 (EDT) Date: Tue, 1 Oct 2002 11:31:45 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 23 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper evaluates DSDV, AODV, TORA, and DSR in a simulation framework that includes accurate MAC & physical-level modelling. Such modelling reveals a wider range of failure modes than more simplistic approaches. TORA in particular suffers from congestive collapse that is due to the feedback between link status detection and routing updates. Routing updates occur in response to link failures, which increases the congestion in the neighborhood of the updating node; this congestion in turn triggers more link failures. This congestive collapse occurs earlier for algorithms that, like TORA, require packet delivery guarantees, since the overhead (retransmission, etc) of the guarantee mechanism causes congestion at lower network "stress" levels. AODV was found to have a high routing overhead because only nodes along a selected path between source and destination will be aware of the route to the destination. By contrast, DSR's sniffing of routing information by nodes not participating in a route allow for a larger proportion of routing requests to terminate early. DSDV-SQ was found to fail to converge much sooner than the on-demand algorithms. Shortcomings A number of issues were not analyzed in the paper. The authors did not address the exact source of the DSDV congestion collapse. It seems that slow link break detection (~45 seconds) is a major culprit, but this does not directly explain why 120 second pause time did not converge (some sort of cascading effect?) Also, no explanation was provided for why DSDV-SQ performed worse than DSDV at low pause times. Future work At route discovery time, DSR's sniffing optimization provides nodes that aren't on the selected path with a route to the destination. Later, if a node moves close to the routing path of an active connection, it would learn a route to the destination. Both of these serve to reduce the average number of hops required for a DSR route request. - What would be the relative performance of AODV and DSR if AODV sniffed the RREP to fill the routing table of nodes that aren't on the chosen path? - It seems to me that the latter case discussed in the introduction especially helps DSR performance in scenarios with high pause time. What is the relative impacts (positive and negative) of the two caching effects in different regimes? From linga@CS.Cornell.EDU Tue Oct 1 11:33:59 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FXxh18772 for ; Tue, 1 Oct 2002 11:33:59 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g91FXwV29677 for ; Tue, 1 Oct 2002 11:33:58 -0400 (EDT) Date: Tue, 1 Oct 2002 11:33:58 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 23 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII A Performance Comparision of Multi-Hop Wireless AdHoc Network Routing Protocols This papers presents a comparative performance study of DSDV, TORA, DSR and AODV. To implement the above routing algorithm the authors have extended NS-2 simulator to support simulation of a MANET. NS-2 was not directly suitable to implement a MANET because: it had no notion of node position, no spatial diversity and it can model only directly connected nodes. To overcome this, NS-2 was extended to support: node mobility, a realistic physical layer, IEEE 802.11 MAC protocol using DCF and radio network interfaces (with attributes such as transmitting power). Modifications to the simulator include: modelling attenuation as proportional to 1/r^2 for small r and 1/r^4 otherwise, where r is the distance between the nodes; each mobile node has a position and velocity at any given time instant and so its state can be predicted, given the porpogation model being used; nodes have same network interfaces which support notions of transmitting power, receiver sensitivity,etc; to accurately model contention between nodes IEEE 802.11 MAC protocol using DCF has been implemented; implementation of ARP as the routing protols in the network layer and hence use IP addresses. We have looked at all four routing protocols which are studied in this paper. To provide for fair and efficient implementation authors propose minor modifications to the protocols in some cases. These include: introducing a random delay to avoid synchronization in case of say periodic broadcasts; routing packets were given priority in the transmit queues for timely propagation of routing info; except for DSDV all protocols were used with link breakage detection feedback from the MAC protocol. In DSDV, if neighbor N detects a link failure to node A, it will advertise an infinite metric route to A with the highest seq number and so eventually A is unreachable from all nodes (until it sends info with higher sequence numbers). Two variants of DSDV: DSDV-SQ where the receipt of a new sequence number for a destination causes a triggered update; DSDV - receipt of a new metric causes a triggered update. Also AODV has two variants- AODV-LL: link breakage detection using link layer feedback instead of explicit HELLO messages; AODV: using explicit HELLO messages. Metrics include: fraction of packets received at the destination (packet delivery ratio); number of routing packets transmitted during the simulation (routing overhead); difference between no. of hops achieved in the protocol and the no. of hops in the shortest path from the source to the destination (path optimality). DSR and AODV-LL have good packet delivery ration. DSR has comparatively low routing overhead whereas DSDV-SQ has constant overhead. DSDV-SQ and DSR gives routes close to optimal. DSR and AODV-LL perform well in varying rates of topology changes. Pros: Extended NS-II to enable accurate simulation of MAC and physical layer in MANET. Addressed problems encountered in previous simulations like synchronization. Simulated four popular adhoc routing protocols and evaluated their performance. Explained why previous simulations were not accurate/complete. Cons: Did not show that in some special cases they could emulate simulations results previously presented establishing the validity of their model. They did not talk about the scalability of their simulator (NS-2 is not good for large number of nodes. Only 50 nodes are used in this paper). They did not use any realistic topology and workload to perform their simulations. From aed13@cornell.edu Tue Oct 1 11:34:59 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FYxh18840 for ; Tue, 1 Oct 2002 11:34:59 -0400 (EDT) Received: from andyd-laptop.cornell.edu (syr-24-58-57-97.twcny.rr.com [24.58.57.97]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA24797 for ; Tue, 1 Oct 2002 11:34:58 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001111606.024fcdf0@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 01 Oct 2002 11:34:57 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 Paper 23 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "A Performance Comparison of Multi-Hop Ad Hoc Network Routing Protocols" provides a realistic performance comparison of DSDV, TORA, DSR and ADODV. The paper succinctly identifies or clarifies assumptions made in previous papers about the implementation details of the protocols before evaluating them. The paper begins by explaining the simulation methodology and modifications made to the ns simulator. The authors developed a MAC Layer simulation of 802.11 and precisely outline details from the radio propagation model to the RTS/CTS layer. They designed the simulator to separate scenario files, with mobility patterns, radio delays and ranges pre-calculated. This enables evaluation of each protocol under identical scenarios for each protocol. In detailing the implementation of each protocol different assumptions were made based on experimental experience and consultation with the protocol's author. Most interesting was the fact that TORA's underlying assumption of reliable, in-order packet delivery was implemented by the IMEP layer, previously unmentioned in the TORA papers we read. The paper uses the metric of Packet Delivery Ratio, Routing Overhead(total number of packets) and path optimality to compare the protocols with 10, 20 and 20 sources transmitting packets. Constant Bit Rates were used instead of TCP/IP since TCP/IP adapts to the underlying network layer and would not have permitted an even comparison of the routing layers. Simulations were run with 7 different pause rates ranging from constant motion at 0 to 900seconds(no-motion). 10 different movement patterns were generated for each pause time, providing a total of 210 scenario files. The maximum velocity of the simulations was run first a 20m/s and then again at 1/ms. Overall DSR showed the best performance in all metrics. The difference between on-demand and no-on demand protocols is vivdly illustrated by routing overhead graphs. The one evaluated hybrid protocol, ADODV performed worse the DSR which it was partially based on. DSDV showed constant behavior no matter the level of movement patter due to it's constant beaconing rate. Interestingly at the lower movement speeds most protocols were never sufficiently stressed. TORA appeared to have congestion failures with 30 sources, while DSDV-SQ failed to converge at 20m/s with low pause times. The only major drawback of this simulation was it did not repeat the results or evaluate the protocols as the number of nodes increased and provide an effective evaluation of scalability. From nbs24@cornell.edu Tue Oct 1 11:36:35 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FaYh19581 for ; Tue, 1 Oct 2002 11:36:34 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA21124; Tue, 1 Oct 2002 11:36:31 -0400 (EDT) Date: Tue, 1 Oct 2002 11:36:31 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200210011536.LAA21124@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 132.236.71.82 Subject: 615 PAPER 23 The authors present a detailed performance evaluation of four routing protocols, namely DSDV, TORA, DSR and AODV, with the goal to measure their reaction to topology change using the following metrics: packet delivery ratio, routing overload and path optimality. They modify the ns-2 network simulator to incorporate the MAC protocol, node mobility, a realistic physical layer and radio network interfaces. Their signal propagation model uses a free space propagation model and a two-ray ground reflection model. Packets with power levels below a carrier sense threshold are dropped, those above the carrier sense threshold but below a receive threshold are marked as erroneous and passed on to MAC and the remaining are handed over to the MAC. The protocols operate at the network layer using IP addresses. The routing protocols are modified to improve performance. These include inserting a random delay between broadcasts and acks to prevent synchronization, queuing routing packets at heat of transmit queue for faster propagation and using link breakage detection feedback (except for DSDV, which they find performs better without this detection) from the MAC layer. Their DSDV_SQ implementation triggers an update whenever a new sequence number for a destination is received. This has more overhead but they find it provides a better packet delivery ratio. In TORA they choose to aggregate hello and ack packets between a short period and do not delay routing messages for aggregation to ensure that the short-lived routing loops caused by the link reversals do not last long enough to drop a lot of data packets. The hello mechanism in AODV is replaced using link layer feedback from the MAC, thus saving overhead. They find that for highly mobile networks, multiple routes are key. They show that unicasts perform better than broadcasts. A weakness in the simulation model was their ‘random waypoint’ model, which does not model realistic mobility patterns. They choose a very slow node speed (1m/s) and very fast node speed (20m/s). What was the motivation for this choice? How about speed imbetween that are more realistic? They find that DSR find performs better than the other protocols but I think this is an artifact of their base architecture and their parameters they use in their simulation. A build to the research would be to perform a congestion analysis and to use a more realistic traffic pattern. Nana B. Sam From yao@CS.Cornell.EDU Tue Oct 1 11:46:00 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91Fjxh21603 for ; Tue, 1 Oct 2002 11:46:00 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615 PAPER 23 Date: Tue, 1 Oct 2002 11:45:59 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D43024797FA@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 23 Thread-Index: AcJpYaO/qfoPoR/mTJWGDvdCfYv/Tg== From: "Yong Yao" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g91Fjxh21603 This paper compares the performance of four ad-hoc routing protocols, DSDV, TORA, DSR and AODV. It is the first time these four protocols are compared on a common platform with similar setup. Many implementation details of routing protocols are discussed and several improvements are proposed by authors, including the interaction of ARP with on-demand protocols, how to avoid synchronization, tradeoff between the cost of one larger packet versus multiple smaller packets, etc. It is a valuable reference paper to anyone who are going to design ad-hoc routing protocols. The paper also presents how to extend ns2, a popular network simulator, to support wirless communication, which is not even included in the on-line reference of ns2. It explains the interactions between physical, MAC and routing layers in details. The main contribution of the paper is the methodology they used to measure the ability of the routing protocols, including both the moving model and the communcation model. It also has a detailed analysis of simulation results, from packet delivery ratio, routing overhead to path optimality. The only missing part of the paper is that there is not a failure model considered in the setup. Wireless communication links are not reliable and should break frequently. However, about 99.8% of unicast of data packets are received successfully in the simulator, which is not very possible in the real life. Yong From mtp22@cornell.edu Tue Oct 1 11:57:09 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91Fv9h23857 for ; Tue, 1 Oct 2002 11:57:09 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA26964 for ; Tue, 1 Oct 2002 11:57:08 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 23 Date: Tue, 1 Oct 2002 11:57:19 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02100111571900.00770@narnia> Content-Transfer-Encoding: 8bit One main contribution of this paper is a comparison of multiple popular ad hoc routing protocols. The paper runs extensive simulations on DSDV, AODV, DSR, and TORA, testing packet delivery percentage and routing overhead. Another main contribution of this paper is the extension of the ns-2 simulator to include properties important to ad hoc wireless networks. In particular, the authors added node mobility models, a physical layer model, and an 802.11 MAC model. A weakness of this paper is that the tests are biased towards DSR. I suspected this from the beginning when I saw that some of the authors of this paper were also involved in creating DSR. One of the things that biases the tests towards DSR are the small network sizes. One of the biggest complaints against DSR is that it doesn't scale well in large networks because of the source routing. Another such bias is the lower load on the networks in the simulation. This paper could be extended by including uni-directional links to see how protocols cope. Uni-directional links often pop up in real situations and it would be nice to see a study that included this. Also, we could extend the paper by analyzing newer hybrid protocols to see how they perform. From ks238@cornell.edu Tue Oct 1 11:59:17 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91FxHh24097 for ; Tue, 1 Oct 2002 11:59:17 -0400 (EDT) Received: from ks238.cornell.edu (syr-24-24-18-11.twcny.rr.com [24.24.18.11]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA05653 for ; Tue, 1 Oct 2002 11:59:16 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001115746.01cfaae0@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 01 Oct 2002 11:58:48 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #23 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In this paper, the authors have created simulations through which the performance of ad hoc network routing protocols could be observed. The primary contribution of the paper is that for the first time DSDV, TORA, DSR and AODV have all been simulated using the NS2 simulator. The performance of each of the routing protocols is evaluated and then compared. The group has adapted the NS2 simulator appropriately in order to test ad hoc networks. The simulator they use implements the IEEE 802.11 MAC protocol at the link layer which provides a suitable environment to test ad hoc networks. The actual implementations of each of the protocols and the corresponding adjustments that were made are discussed in the paper. There are some key features of why their simulations were more practical than previous simulations of each of the protocols. First, the size of the network (i.e. 50 nodes) is practical given the applications discussed in the introduction. Next, the simulations discussed assume varying levels of mobility within a network through their Movement Model, which allows them to test how each protocol adapts to topological changes at different rates. Another variable in the simulation, which was addressed through their Communication Model was the size and frequency with which packets were sent. The metrics studied in each of the simulations were packet delivery ratio, routing overhead and path optimality. These are key facets of the simulations, which were left out of previous simulations. The conclusions drawn at the end of the simulations seem to be consistent with many of the original hypothesis made. DSDV, a proactive protocol which employs periodic broadcasts, was unable to provide reliable data transfers in highly mobile networks. TORA, a reactive protocol which finds routes on demand, was the worst performer due to the fact that excessive routing packets in the network collided at the MAC-layer resulting in diminishing performance as the network size grew larger. The two other reactive protocols that were evaluated, DSR and AODV, showed similar performance results at varying mobility rates with issues regarding source routing overhead (i.e. RREQ and RREP packets in the network) being an issue hurting each of the protocol's results. One of the areas of concern I had is the reliability of NS-2 to provide an accurate simulation of ad hoc networks. NS-2, as the authors indicate, was originally designed for simulating "conventional networks" (i.e. not ad hoc). I am no expert on simulators, however, it may seem that a simulator developed from the ground up specifically for ad hoc networks rather than one adapted for them would be more reliable. It would be interesting to see if the results and conclusions made would differ should the authors have used a different simulator. This would be a pretty substantial flaw to the results of the paper. From vivi@CS.Cornell.EDU Tue Oct 1 13:32:36 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g91HWZh15330 for ; Tue, 1 Oct 2002 13:32:36 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615paper23 Date: Tue, 1 Oct 2002 13:32:35 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF7E@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper23 Thread-Index: AcJpcIf9r+gdAAhWSFW2k97obxjVog== From: "Vivek Vishnumurthy" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g91HWZh15330 This paper conducts a performance comparison of 4 ad-hoc routing protocols: DSDV, TORA, DSR and AODV through rigorous simulations. The protocol finds that DSR performs well in all conditions, DSDV performs well except when there is high mobility, and TORA has the highest routing overhead. Contributions: -- The authors have extended the ns-2 simulator to more accurately simulate the ad-hoc wireless environment. -- Various real issues(which were not considered earlier) have been dealt with in the paper.(For example: ambiguous specifications in the original paper that descibed the protocol). The authors tried and varied the different protocol parameters to obtain the best performance. In some cases they even modified the specifications of the protocol when they found that these modifications improved the performance. Eg: The functionality of link-breakage detection was not used in the implementation of DSDV. -- An attempt has been made to validate the results. For example, the propagation model was verified by an "expert" in radio propagation modeling. Also, all the observed results have been fairly well explained. Possible improvements -- As the paper suggests, we could get a more real picture through a model that considers the cost of acquiring the channel, and not just considers the total number of routing packets transmitted or the total number of bytes transmitted.