From kevin.walsh@flashmail.com Mon Sep 30 20:59:54 2002 Received: from mail.usadatanet.net (mail.usadatanet.net [208.48.41.252]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g910xrh06211 for ; Mon, 30 Sep 2002 20:59:54 -0400 (EDT) Received: from home.flashmail.com (unverified [208.51.228.137]) by mail.usadatanet.net (Vircom SMTPRS 5.1.202) with ESMTP id for ; Mon, 30 Sep 2002 20:51:20 -0400 Message-Id: <5.1.1.6.0.20020930202140.00a9a008@mail.flashmail.com> X-Sender: kevin.walsh@mail.flashmail.com X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Mon, 30 Sep 2002 20:59:30 -0400 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 25 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Performance Comparison of Two On Demand Routing Protocols for Ad Hoc Networks The authors of DSDV and (later) AODV present in this paper a performance comparison of AODV and DSR in a very similar vein to the evalation by Broch et al [paper 23]. Here, however, the AODV protocol has been apparently improved substantially, while DSR is left untouched. The authors conclude that DSR performs best in small, low-mobility networks, and that AODV performs best in large, high stress networks (high mobility, high send rate). In leading up to this conclusion, the authors make some observations about the behavior of the protocols and imply some rather interesting conclusions. First, while DSR is shown by the author's own data to have significantly lower overhead, an argument is made that the higher proportion of unicast control messages in DSR compared to AODV is a bad thing. The reasoning is that a unicast message requires a RTS/CTS/data/ACK series of messages, causing congestion problems, while a broadcast is much ligher weight. This reasonning is perhaps somewhat at odds with prevailing opinion: broadcast is bad for congestion because of the lack of RTS/CTS, and very unreliable to boot. This point is repeated several times, with the RTS/CTS being cited as a cause for congestion, collisions, and erroneous link breakage detection. It is unclear how a broadcast could possibly improve the situation, as several authors have reported higher loss/collision rates for broadcast than for unicast messages. Next, the authors imply that the comparatively shorter routes in DSR are a hinderance, because the shorter routes may not be the least congested routes. A simple trick in AODV, which the authors cite, is to use the _first_ path discovered, not the _shortest_ path. This might help choose the route with the least delay and/or least congestion. Not mentioned or evaluated, though, is the possibility of using the identical trick in DSR. Finally, the authors claim several times that AODV benefits greatly from its expiration and detection of stale routes. In a high mobility situation, the ability to choose the newer among multiple alternate routes is a definite plus. Only in the last paragraphs of the paper was it mentioned that a trivial modification to DSR, adding timestamps to route cache entries, might bring this benefit to DSR as well. From hs247@cornell.edu Tue Oct 1 00:34:34 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-0.nyroc.rr.com [24.92.226.125]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g914YYh18077 for ; Tue, 1 Oct 2002 00:34:34 -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 g914YVI10322 for ; Tue, 1 Oct 2002 00:34:31 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001003447.00b7a448@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:35:03 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 25 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper compared in detail two ad-hoc on-demand routing protocols: DSR and AODV. In particular, 4 performance metrics were looked at, Packet Delivery Fraction (ratio of packets delivered successfully to attempts), Average end-to-end delay of Packets, Normalized routing loading, and Normalized MAC load. They concluded that DSR performs better at low stress environments and AODV performs better under high stress environments. One of the main differences in performance that they identify is that DSR relies heavily on caching while AODV does not. The reliance on caching makes DSR a good performer at low loads and minimized topology changes. AODV on the other hand seems to react better to higher loads and changes. Another point that the paper seemed to concentrate on was overhead. They explained that DSR was significantly lower in routing loading. But his was due to the fact that DSR uses mainly unicasts. Unicasts have been proven to be more successful, but this doesn't tell the whole story. In fact, if you consider the overall MAC overhead, the DSR has a higher in overhead in stressful environments. This is a very significant point in that RTS/CTS and acks in the MAC layer needed to establish unicasts can be expensive. This paper identified a new trade off: higher overhead for unicasts in order to get higher rates in packet delivery. Perhaps it would be worth while to research this area more. What are the tradeoffs and in what situations is it better to use the less reliable but cheaper broadcast? How does this affect the scalability of a protocol. In this paper, the results say that AODV performs better under higher loads. Another aspect to look at might be to look at the density of an ad-hoc network. If more nodes are packed together, more nodes are in contention if they want to unicast. Perhaps this may be another metric to look at: how algorithms perform in networks of different densities. In this way, it may be more useful to model a simulator so nodes do not move randomly, but maybe in clusters. From jsy6@postoffice2.mail.cornell.edu Tue Oct 1 01:17: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 g915H4h25329 for ; Tue, 1 Oct 2002 01:17:06 -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 BAA08532 for ; Tue, 1 Oct 2002 01:17:02 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001011609.00b3d6d0@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 01 Oct 2002 01:16:32 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 25 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper is an extension of "A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocol", whose results showed that based on its metrics, DSR performed best followed closely by AODV. DSR and AODV are both on-demand routing protocols whose key motivation is the reduction of routing load. DSR is seen as the more aggressive routing protocol due to its use of source routing and caching. Due to the use of promiscuous listening and single request-reply cycle, DSR has greater access to routing information than AODV. DSR is considered more aggressive of the two because it replies to all route requests, thus it keeps track of more than one route from source to destination. DSR thus does not have to send a route request in the face of most link breakages, but suffers from stale routes in the cache. AODV using the time driven, conservative sequence number and routing table approach. The routing table for AODV keeps track of at most one route entry per destination. AODV sends much more route requests than DSR but not as many route error packets. These differences in the two routing protocols result in each protocol performing better in different networking environments. The performance metrics for this simulation are packet delivery fraction, average end-to-end delay of data packets, normalized routing load, and normalized MAC load. In an environment with a smaller number of hosts and lower load and mobility, DSR outperforms AODV in terms of delay and throughput. In a more stressful environment, AODV performs better. This result is due to the use of aggressive caching by DSR and its lack of a mechanism to clean up stale caches. DSR, as mentioned above, generated fewer routing packets in general than AODV and yet DSR incurred a greater load on the MAC level since it incurred more unicast routing packets. Unicasts packets are more expensive in the MAC layer used. This leads one to believe that the relative performance of the protocol is dependent of the implementation of the protocol layers used and their interactions. Since it was noticed that DSR's performance suffered the most due to its lack of a mechanism to clean up stale cache, the next step would be to try to produce such a mechanism. From mr228@cornell.edu Tue Oct 1 01:17:19 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 g915HHh25351 for ; Tue, 1 Oct 2002 01:17:18 -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 BAA18410 for ; Tue, 1 Oct 2002 01:17:16 -0400 (EDT) Message-ID: <3D992FDD.861A9FD9@cornell.edu> Date: Tue, 01 Oct 2002 01:17:17 -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 25 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper compares two of the routing protocols, namely DSR and AODV. The test environment is very similar to that of the last paper (even many of the parameters are set the same). The metrics being measured and analyzed are: Ratio of packet delivered to attempts, average end-to-end delay, Normalized Routing Load, and Normalized MAC load. The paper does a good job of decomposing and analyzing the various components of the overhead that exists with each protocol. They distinguish between RTS, CTS, ACK, unicast control packets, and broadcast control packets. They provide helpful data from their simulations so it's clear what percentage of the channel is spent doing each of these for each protocol. They conclude, based on empirical results, that AODV outperforms in less "stressful" situations and AODV outperforms in more stressful ones. They then suggest several reasons for this. First, they claim the AODV is much better at detection of stale routes, whereas DSR will try to make use of a stale route before noting its absence. Second, they note that DSR involves an extensive amount of state that is cached within the nodes of the network. This aggressive caching helps DSR to have significantly less overhead as compared to AODV for low mobility environments but fails to efficiently detect stale routes in higher mobility situations. The paper itself identifies 3 areas in need of further investigation: (quoting from the paper) 1.) Using congestion-related metrics (e.g., queue lengths) to evaluate routes instead of emphasizing the hop-wise shortest routes. 2.) Removing "aged" packets from the network. The aged packets are typically not important for the upper layer protocol, because they will probably be retransmitted. These stale packets do contribute unnecessarily to the load in the routing layer. 3.) Studying interactions between protocol layers when designing wireless network protocols. -- Mark Robson From shafat@CS.Cornell.EDU Tue Oct 1 01:31:25 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 g915VPh27669 for ; Tue, 1 Oct 2002 01:31:25 -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 25 Date: Tue, 1 Oct 2002 01:31:25 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134F99@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 25 Thread-Index: AcJoLndCidfWhhJKRDy7mGkR/b26xQ== 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 g915VPh27669 This paper addresses the performance issues of two routing algorithms for mobile wireless ad hoc networks, and does a head-to-head comparison of them. The two chosen algorithms, DSR and AODV, are both reactive by nature with some fundamental differences in the way they work. This gives rise to discrepancies in their performances, under varying conditions, which are thoroughly investigated in this paper. The same version of the ns-2 simulation model that was used in the previous paper is used here as well. The protocols are tested on the basis of four performance metrics - packet delivery fraction, average end-to-end delay of data packets, normalized routing load and normalized MAC load. A large amount of simulation data is collected, and is analyzed both qualitatively and quantitatively. The paper's strength lies in its detailed analysis of the graphs plotted from the experimental data. A lot of importance is placed, as it should be, on justifying the behavior of each protocol in the given conditions. Based on their analysis, the authors are able to make some valid observations on the performance of these two protocols, and accordingly, suggest some effective improvements that could be implemented in the future. As for the weaknesses, there does not seem to be any significant ones in this paper. One complaint would be that it does not elaborate too much on the simulation model used. Also, the reason behind choosing "normalized MAC load" as a performance metric, along with "normalized routing load" seemed somewhat redundant. Since this paper aims to do a strict comparison between the two routing protocols, the former metric could have perhaps been left out. From mvp9@cornell.edu Tue Oct 1 01:44:51 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 g915ioh29227 for ; Tue, 1 Oct 2002 01:44:51 -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 BAA12181 for ; Tue, 1 Oct 2002 01:44:50 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001014409.01a70250@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:48 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 25 Mime-Version: 1.0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The contributions offered by the Das et al. paper is the comparison of the two protocols AODV and DSR, insights into their behavior, strengths and weaknesses, and various conclusions about MANET protocols in general.  For example, they show that there is no correlation of hop count and actual transmission speed (delay), that performance of routing protocols is highly interrelated with the underlying link and physical layers, etc.  The demonstrated tradeoffs of AODV and DSR allow informed decisions of when the use of each is best and opens roads for improving the performance of each.
        The simulation aspects are quite strong:  The choice of metrics, measuring speed, and overhead load of the protocols.  Data rates which are more realistic, though not entirely so, but still allow good approximation of real conditions (512b/packet is a lot better than 64b!)  The incorporation of MAC-level control packets as part of the metric is an important step toward modeling a real MANET.  The conclusions are also both concrete and useful.  However, there are some points in the simulation description with which issue can be raised.  Since this is purely a simulation paper, the fact that the movement model is still random is unfortunate.  There are also fewer details about the parameters used for each protocol, and clearly, they can make a big difference.  While the Broch et al. study had the authors of protocols verify the authors=92 setup, this was not the case here.  A small counterintuitive point that I noticed  in Figure 2, more traffic corresponds to less delay.  This can be explained for DSR by its increased use of caching, but for AODV its far from clear.  Another small point  why only on-demand protocols, and these specifically; is it so clear that on-demand is best?  Finally, it is very surprising to see DSR do so poorly on delivery rates, compared to the Broch et al. paper.  The parameters for the network seem similar, what accounts for this discrepancy?
        The most obvious pursuit of this work would be to implement some of the suggestions for both tested protocols, and do more testing.  Also, testing on a larger network would be informative.  Further extensions would include incorporating these in a whole protocol stack with TCP and higher layers to more effectively model real world use.  Most importantly, how do these protocols compare to other MANET ones, especially hybrid and partitioning ones like ZRP, HARP and CEDAR.  The modified ns-2 simulator used in this paper would provide an excellent format for that.
From bd39@cornell.edu Tue Oct 1 02:07:18 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 g9167Ih03418 for ; Tue, 1 Oct 2002 02:07:18 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id CAA11779 for ; Tue, 1 Oct 2002 02:07:17 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001020558.0277e5d0@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 01 Oct 2002 02:06:11 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 25 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Paper 25 In this paper, the two reactive protocols DSR and AODV are compared. The authors characterize DSR as being aggressive in route finding (caching, unsolicited RREP's), whereas AODV is conservative in its route maintainance (timeouts, broadcast route error replies.) DSR can result in stale route entries, while AODV can prematurely drop routes. A similar format to simulation as the previous paper is followed: use of ns2, 50 or 100 nodes with a pause and move mobility model with CBR traffic. The metrics measured are packet delivery fraction, average end-to-end delay and normalized MAC load, which is a new metric. - In low load situations, both DSR and AODV are comparable, however in high load situations, AODV outperformed DSR. (Which is in conflict with the previous paper, which seemed to use the same evaluation setup.) - DSR generates less protocol packets than AODV, however an examination of the traffic on the MAC layer reveals that DSR in actuality generates more MAC level activity than AODV. This also leads to DSR having poorer performance on higher networks loads. (DSR network saturated at a lower level of delivery than AODV.) - This paper introduces the notion that unicast sends are more expensive because of RTS/CTS activity at the MAC level. It is interesting to see that despite having a greater routing load, AODV has comparable MAC layer load. This contradicts many earlier assumptions that unicast is inherently more efficient and would cause less contention. It appears that RTS broadcasts suffer from the same problems as normal broadcasts. In essence, the authors note that careful attention must be paid to interlayer interactions. - It would be interesting to see if the authors complaints about stale DSR caches could be alleviated by a simple time out scheme for cache entries. A chart illustrating the degree to which routes in the DSR cache are stale (i.e. not optimal length) would be stronger support for their claim. - Is MAC load the cause for lower saturation load of DSR? It would follow that frequent broadcasts have a similar problem of collisions and contention. Perhaps what the significance of the difference is that the information propagated by broadcasts is unreliable, whereas unicast is resent in 801.11b until the send succeeds. From tmroeder@CS.Cornell.EDU Tue Oct 1 10:52:10 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 g91EqAh10318 for ; Tue, 1 Oct 2002 10:52:10 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g91Eq9G06067; Tue, 1 Oct 2002 10:52:09 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15769.46745.604945.769778@dhcp99-233.cs.cornell.edu> Date: Tue, 1 Oct 2002 10:52:09 -0400 To: Emin Gun Sirer Subject: 615 PAPER #25 X-Mailer: VM 7.07 under Emacs 21.2.1 This paper, 3 years after the other paper for today, seeks to examine the performance of DSR and AODV under high-load situations, using the same speed and motion model as the other paper. It adds one different metric to examine the effectiveness of each protocol; the normalized MAC load, in which they count the number of MAC-layer packets transmitted for each delivered data packet. They determine that with few sources, AODV and DSR give approximately the same performance. With many sources, DSR wins in low mobility situations, and AODV wins in high mobility situations. They further load tested the protocols by ramping up the number of packets being transmitted until the network was saturated. Here again, DSR came second to AODV. Again, it is easy to be skeptical of paper in which an author of AODV tests his protocol against DSR and finds that it wins. Comparing this paper with the DSR team's paper, however, we can see that they are examining different enough situations that the results can be explained. The main difference between the two is the number of sources, and the rate at which packets are sent. The most interesting result of the paper is the determination that DSR causes significantly more MAC-layer traffic than AODV, despite the fact that it sends fewer routing messages. This result shows that more study needs to be done about how to optimize the interaction with the lower-level protocols, and suggests also that one must take them into account when designing the higher-level interactions. I would be interested to see a comparison of DSR and AODV at the MAC level using the parameters and settings that the DSR team used for their 1998 paper, and see if that affects the relative evaluation of the worth of the protocols. From xz56@cornell.edu Tue Oct 1 11:11:40 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 g91FBeh14289 for ; Tue, 1 Oct 2002 11:11:40 -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 LAA16604 for ; Tue, 1 Oct 2002 11:11:39 -0400 (EDT) Message-ID: <005401c2695c$d78105e0$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 25 Date: Tue, 1 Oct 2002 11:10:25 -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 two very similar ad hoc on-demand routing protocols: DSR and AODV. It used a similar simulation environment as in the first paper, but different metrics: packet delivery ration, average end-to-end delay, normalized routing load, normalized MAC load and gave explanations stem from the different specification in these two protocols for the different performance. By noticing the difference behavior with large number of sources at different mobility in terms of delivery ratio and delay, the paper pointed out that the reason is that DSR uses an aggressive caching, which although reduced the propagations of RREP, may give stale routing info and pollute other nodes, even affect the performance of TCP, when nodes are of high mobility. So Holland even suggested to switch off the cache replies to improve the performance of DSR, which is reasonable, but will also cut some advantages of DSR too. The compromise may be give an expire time to each entry as that in AODV. The routing load of DSR is always lower than AODV in terms of number of packets but opposite of bytes, as also was noticed in the first paper. But as reasoned there, it may be more appropriate to use the # of packets as the criterion for load measurement since that is what influences the channel use. The MAC load, on the other hand, is higher in DSR than in AODV, because more unicasts is used in DSR. But it seems to me that, more unicast although will increase the MAC load, can improve the reliance of the packet delivery and reduce the redundant rebroadcast. The discrepancy in performance in terms of path optimality (used in first paper) and delay shows that it may be more proper to define the optimality of route by energy efficiency and load balance rather than the number of hops. In summary, this paper is very helpful to understand the DSR and AODV in more depth. From ag75@cornell.edu Tue Oct 1 11:25:43 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 g91FPgh16925 for ; Tue, 1 Oct 2002 11:25:43 -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 LAA25443 for ; Tue, 1 Oct 2002 11:25:42 -0400 (EDT) Message-ID: <001101c2695e$e19313f0$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 25 Date: Tue, 1 Oct 2002 11:26:14 -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 the performance of DSR and AODV. The simulator that the authors use is the one from previous paper (23), but they change certain parameters of the simulation. The authors perform testing on networks with sizes 50 and 100, which allows for better scalability testing than just the 50 node network used in previous paper. The authors also change some of the performance metrics. While the packet delivery fraction is used in both papers, average end-to-end delay of data packets is used in this paper versus path optimality in the previous paper. Average end-to-end delay is probably a better metric because what we really care about is how fast the packet gets there, not how many hops it takes. Since the simulator is the same as the one in previous paper, the same positives (realistic) and negatives (uniform node distribution, random motion) apply. Once again one has to question why in this test AODV outperformed DSR in most cases. It is unclear how the implementation of each algorithm might have impacted the performance. The authors mention that they made certain improvements to AODV, and they also mention that certain improvements can be made to DSR, so it's not clear how the results would change if those improvements were actually made. The results of this simulation suggest that DSR performs better there is a smaller number of nodes and lower load and/or mobility, while AODV performs better under more stressful conditions when there are many nodes and higher mobility. DSR, however, consistently generates less routing load than AODV. The results for 100-node network suggest that DSR might not scale very well. This deserves further investigation with an implementation of DSR that implements the improvements that the authors mention. From liuhz@CS.Cornell.EDU Tue Oct 1 11:31:38 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 g91FVch18505 for ; Tue, 1 Oct 2002 11:31:38 -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 25 Date: Tue, 1 Oct 2002 11:31:37 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE63A@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 25 Thread-Index: AcJpX6HVk+uTM3NiQ0CP7Ih8MxHung== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g91FVch18505 Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks This Paper compares the performance of two on-demand routing protocols, namely DSR and AODV, for ad hoc networks under various traffic load and mobility conditions. The paper explains in detail the reasons that cause the different performance and gives some ideas that may optimize both protocols. DSR and AODV are both reactive routing protocols, but they still use many different mechanisms. DSR uses source routing, aggressive cache and multiple routes for one destination are maintained, while AODV takes advantage of the routing table and keeps only a single route for one per destination. Another advantage of AODV over DSR is that it uses destination sequence number to remove stale routes. This difference leads to their different performance even in the identical simulattion situation. In this paper, four metrics are used to evaluate the protocols. There are packet delivery fraction, end-to-end delay, routing load and MAC load. In general, DSR outperforms AODV in less stressful situations(less source nodes and lower mobility) in terms of throughput and delay. AODV, however, outperforms DSR in more stressful situations. DSR always generates less routing protocols, thanks to alternative routes and aggressive caches. However comparison of MAC load goes agaist DSR in most cases except under low mobility conditions. The main reasons that cause DSR's poor performance under stressful conditions are: 1.it does not broadcast link breakage messages to the whole networks, but just sends it back to the source. Thus some nodes that are not on the path from the source to the broken link will still keep this link in their caches, which will lead to routing failure and packet loss later. Although gratuitous route repaire can alleviate this problem, it can not get resolve it completely. 2. DSR has no mechanism to remove stale routes or determine the freshness of routes when multiple choices are available. Given some mechanisms that can propagate the link failure messages faster and more efficiently and expire stale cache entities, DSR can perform much better. On the other hand, AODV can benefit from source routing the request and reply packets in the route discovery process. The paper also suggests somethings that may improve the performance of both protocols, for example: using congestion-related metrics, removing "aged" packets from the network and paying attention to the interaction between protocol layers, which may give rise to some original routing protocols in the future. One thing that I don't understand is: in the DSR paper(615 paper5), it does mention the expiration time for each cache entry, however, in this paper, it claims that DSR doesn't have mechanisms to expire stale routes. And all the simulation results are based on this assumption. I beleive if the timeout mechanism is incorporated into the simulation, the results will be quite differect and make DSR more intriguing. From smw17@cornell.edu Tue Oct 1 11:31:40 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 g91FVeh18525 for ; Tue, 1 Oct 2002 11:31:40 -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 LAA06277 for ; Tue, 1 Oct 2002 11:31:39 -0400 (EDT) Message-ID: <3D99BF12.8060707@cornell.edu> Date: Tue, 01 Oct 2002 11:28:18 -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 25 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Performance Comparison of Two On-Demand Routing Protocols for Ad-Hoc Networks The simulator for this study is ns-2, in a configuration that includes the physical, data link, and MAC support necessary for simulating multi-hop ad-hoc wireless networks, including the 802.11 DCF (RTS/CTS/ACK). The physical model is designed to be similar to Lucent's WaveLAN 2Mb wireless ethernet card, with a nominal range of 250m. On top of this base, the authors compare two protocols, AODV and DSR. The authors attempted to closely match the specifications for each protocol. Node traffic patterns were modeled in two arenas, a 1500m x 300m arena (50 nodes) and a 2200m x 600m arena (100 nodes). Nodes select a random destination and travel at a uniform random speed. At the destination, nodes pause for a pause time before selecting a new destination. At least five runs are averaged for each data point, and both protocols are run on identical scenarios. The 50 node simulations were run for 900s, and the 100 node simulations for 500s. Data was transmitted in the 50-node runs from 10, 20, 30, or 40 nodes, at 4 packets/sec for all except the 40-node case, where congestion required scaling back to 3 packets/sec. In the 100 node case, only the 10, 20, and 40 node cases are used, and the traffic scales back to 2 packets/sec for the 40 node scenatio. Data packets are 512 bytes in this study. The main focus of this work was to compare the AODV and DSR protocols under interesting network conditions. In order to do so, they looked at very heavily used networks (40 of 50 nodes transmitting CBR - 1.5kbps) and larger data packets than previous works. For the lower numbers of sources (10 and 20), there was little difference with respect to either delay or delivery fraction between the two protocols. Only in high load situations do the simulated results demonstrate meaningful differences. As the network load is increased, the results show that AODV performs better for highly dynamic networks, whereas DSR performs better for longer pause times. Part of the reasoning for this difference comes down to the aggressive cache behavior of DSR and the route reply mechanism. AODV selects a single route at the destination that creates a bi-directional route back to the source. In contrast, the DSR implementation replies to all route requests, providing the source with a number of different routes to choose from. DSR also monitors network traffic to find additional routing information from neighboring transmissions. As a result, a DSR-based subsystem may have far more routes available than an AODV system, which has a single next hop route to choose from. In highly dynamic networks, these routes become a liability, because route replies based on a stale route cache entry can significantly delay route acquisition, leading to more delay and dropped packets. In less dynamic situations, however, the route cache may provide still-good routes that avoid a new route discovery, and may also achieve limited load balancing by routing around heavily congested nodes due to the increased delay and packet loss observed at the congested node. I did have a problem with the overhead analysis. The standard packet and byte based overhead analysis was present, and made sense. DSR has lower overhead, but is not as pronounced a difference when considering byte loads rather than packet loads. My concern is not with this, but with the subsequent analysis of MAC loads. The statement is made that AODV has a lower MAC load because errors are reported in a broadcast, whereas DSR errors are unicast. Given that broadcasts do not have the RTS/CTS/ACK overhead, the AODV broadcasts are claimed to be cheaper. My problem with this reasoning is that while the transmission iteslf may well be cheaper, it is not at all clear to me that the overall scheme is cheaper. The RTS/CTS/ACK overhead manifests iteslf as a simple overhead that is added to every transmission, whereas the broadcast overhead will appear as increased contention, congestion, and packet loss throughout the network. It does not seem to me that the authors have properly considered this impact in the analysis of MAC loads. From adam@graphics.cornell.edu Tue Oct 1 11:51:40 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 g91Fpeh22727 for ; Tue, 1 Oct 2002 11:51:40 -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 g91FpT0k030052 for ; Tue, 1 Oct 2002 11:51:34 -0400 (EDT) Date: Tue, 1 Oct 2002 11:51:25 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 PAPER 25 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Performance Comparision of Two On-Demand Routing Protocols for Ad Hoc Networks. This paper reviews AODV and DSR and serves as a survey of the two protocols. Like the previous paper they introduce them w/ brief summaries of the protocols. A short critique of AODV and DSR is presented noting that there are improvements avail to both algs. Specifically DSR caching comes up as an issue wrt weaknesses of DSR. The simulation model is roughly similar to that of the previous paper. The performance metrics of Packet Delivery Fraction, Average End-to-end delay of packets, normalized routing load, normalized MAC load I think are very appropriate measurement metrics to use. End-to-end metrics are surely important, and I'm glad it has its own category, but isn't the sole focus of performance in these algs. I am still however not impressed w/ the simulation setup. I think that using a real implementation or real data are much much much better than using the contrived sequences of mobility, sources, etc. I realize that for high number of sources these limited tests show that some effort can be concentrated on having more efficient large ad-hoc nets (40+ sources, since traffic was a problem w/ this and cbr was downgraded from 4 to 3 in these situations). These tests are a good start and give some indication that failures, overload, latency, convergence and mobility will all be issues in bigger networks. From pj39@cornell.edu Tue Oct 1 11:55:50 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 g91Ftnh23395 for ; Tue, 1 Oct 2002 11:55:49 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA05883; Tue, 1 Oct 2002 11:55:46 -0400 (EDT) Date: Tue, 1 Oct 2002 11:55:46 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200210011555.LAA05883@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 25 Performance Comparison of Two On Demand Routing Protocols for Ad Hoc Networks The authors in this paper compares AODV and DSR two reactive protocols for mobile ad hoc networks. Though both AODV and DSR shares on demand routing behavior, DSR uses source routing and AODV uses a table driven approach. Here to the simulation model is based on the ns-2 developed at UC Berkeley. The traffic sources are continuous bit rate (CBR) and the mobility model uses the random waypoint model in a rectangular field. The four important perfomance metrics that the authors evaluates are packet delivery fraction, average end-to- end delay of data packets, normalized routing load and normailized MAC load. In the acutal simulation results for 50 node experiment they used 10, 20, 30 and 40 traffic sources which packet rate of 4 packets/s and for 40 sources 3 packets/s. The packet delivery fraction for AODV and DSR were similar for with 10 and 20 sources. With 30 to 40 sources AODV outperforms DSR by about 15 percent. For higher pause times DSR has a better delivery fraction than AODV. In all cases DSR had significantly lower routing load than AODV. When the number of nodes is low DSR and AODV performs similarly regardless of mobility. For large number of sources DSR outperforms AODV under low mobility conditions, wheread AODV starts out performing DSR for high mobility scenarios. DSR has lower routing load than AODV, this is because of the overhead due to AODV's route requests. Due to caching of ruotes DSR is more likely to find a route in the cache. Mobility affects the performance of DSR and AODV differently. Due to high mobility link failures are often and this triggers new route discoveries in AODV since it has at most one route per destination, The reaction of DSR to link failures is mild because of the abundance of cached routes at each node. DSR performs better in less stressful situation than in more stressful situation (large no of nodes, sources and higher mobility). This due to caching which at highe loads grow too large and provide stale routes. To summmarize DSR outperforms AODV in less stressful sitaations. AODV however outperforms DSR in more stressful situations. This is attributed to the aggressive use of caching in DSR. The author reiterates that AODV benefits greatly from its expiration and detection of stale routes. One major contribution that appears from this paper is that a mechanism is required for detection and expiration of stale routes in DSR for it to perform better at more stressful situations. From nbs24@cornell.edu Tue Oct 1 11:57:05 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 g91Fv4h23840 for ; Tue, 1 Oct 2002 11:57:04 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA06860; Tue, 1 Oct 2002 11:57:02 -0400 (EDT) Date: Tue, 1 Oct 2002 11:57:02 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200210011557.LAA06860@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 25 This paper provides a performance evaluation of DSR and AODV, both reactive protocols, using the ns-2 network simulator using the following metrics: packet delivery fraction, average end-to-end delay of data packets, normalized routing load and normalized MAC load. They provide a wide range of quantitative data for their analyses. They find that for few sources, the two protocols behave similarly but as the sources increase, DSR outperforms AODV under low-mobility conditions. Also, they find that AODV performs better in large and more stressful networks. They attribute DSR’s reduction in performance in this regard to the choice of stale routes, which consume additional network bandwidth and pollute the caches of other nodes. The authors use the ‘random waypoint’ mobility model just like in the previous paper. Again, it is not that difficult to get a real-world traffic pattern for simulations. They mention that the use of more unicasts routing packets hurt DSR’s performance. Is this indirectly saying that DSR should be using broadcast or was this supposed to expose a flaw in the DSR algorithm? To build on the research a more realistic traffic pattern can be employed for a larger number of nodes (more than the 50 nodes they used). Nana B. Sam From mtp22@cornell.edu Tue Oct 1 11:57:34 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 g91FvYh23907 for ; Tue, 1 Oct 2002 11:57:34 -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 LAA28584 for ; Tue, 1 Oct 2002 11:57:33 -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 25 Date: Tue, 1 Oct 2002 11:57:43 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02100111574301.00770@narnia> Content-Transfer-Encoding: 8bit main contribution of this paper is the reevaluation of AODV in terms of DSR. In a sense, this is the authors of AODV's response to the previous paper we read. They perform simulations that include higher network load and larger networks, using similar performance criteria. Another contribution is the recommendations for improving both protocols. That is, both protocols should consider congestion more serioiusly when determining routes, and both protocols should take care to remove old packets from the network, reduing the extra load they cause. A weakness of this paper is that it uses a new version of AODV without using a new version of DSR. The new version of AODV uses new query control mechanisms not found in simulations in the previous paper. In a sense, it is unfair to allow AODV to take into account the problems presented in the previous paper and change its protocol without allowing the same thing for DSR. The paper does some nice work on showing how network load can be deceivingly calculated by routing load. It shows that unicasts tax the MAC layer much more, and so need to be taken into account. I'd like to see an analysis of this with other protocols that use unicasts, or multicasts, such as ZRP and HARP. From ashieh@CS.Cornell.EDU Tue Oct 1 11:57:35 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 g91FvZh23912 for ; Tue, 1 Oct 2002 11:57:35 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g91FvZI25861 for ; Tue, 1 Oct 2002 11:57:35 -0400 (EDT) Date: Tue, 1 Oct 2002 11:57:34 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 25 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper evaluates AODV and DSR, using the simulation framework developed in the CMU evaluation. Like the earlier CMU paper, this paper underscores the importance of looking at MAC and physical-layer interactions with the routing protocols. Again, congestion-induced link failures (e.g., when congestion, not node movement, causes a link failure) are used as an example of this. Congestion at hotspots (since neither of these algorithms attempt to load balance) causes AODV to believe that links have failed permanently, when in fact they would still be usable once traffic subsides. Thus, transient phase effects could cause removal of possibly relevant routing information from the network and trigger additional route discoveries. Caching of routing information (as in DSR) was found to have significant implications on performance. When the network is fairly static, caching hides the congestion problem mentioned earlier, since in DSR nodes off the "optimal" path cache overheard routing information, and so if informtion is purged from the "optimal" path, an alternate likely still exists, and a route discovery need not start from scratch as is likely the case in AODV. However, in a highly dynamic network detected link failures are more likely to be actual link failures, and so many nodes cache stale route information. This causes considerable extra overhead: a node may reply to a route query with stale information, causing the source to send data through the stale path (and also propagating the bad route information to nodes parallel to that path); once the route is found to be bogus, the source has to do another route request, which may again result a route reply with stale information. It may take several iterations for all bogus information that can possibly confuse the source to be purged from the network. ** Shortcomings The authors directly measure the direct MAC overhead of these algorithms, but do not present any measurements for the indirect MAC overhead of broadcasts. As presented, AODV seems to stress the network less than DSR does, even though it requires more broadcasts. The paper also does not explain the considerable differences from the CMU paper in the DSR performance curves. ** Future work - The congestive link failure effects suggest some band-aid solutions in which MAC information (e.g. derivative of link strength, or amount of traffic in the immediate area) or routing information (higher order network stability metric) is used to determine whether a loss is more likely to be caused by congestion. Furthermore, it may be useful to use flow control (perhaps broadcast a negative advertisement that is heeded by some subset of the offending sources) to force traffic away from hotspots. - Perhaps DSR should employ aggressive cache purging to reduce the amount of stale information in the network. Conceivably, the number of eagerly-returned routes that turn out to be stale, or the velocity of the destination, can be used to determine where/when such a policy is necessary. - Itemize events that trigger RREQ in AODV to determine where the algorithm needs to be tuned to reduce the routing overhead. See writeup for CMU paper for ideas. From aed13@cornell.edu Tue Oct 1 11:58:36 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 g91Fwah24043 for ; Tue, 1 Oct 2002 11:58:36 -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 LAA08014 for ; Tue, 1 Oct 2002 11:58:35 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001114358.025efca0@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:58:29 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 Paper 25 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks" extend directly off the work of the previous paper and dives into the exact causes of performance differences between ADODV and DSR. The simulation methodology is the same, with most of the same assumptions. The authors try differentiate their work by showing the effects higher load and increasing the number of nodes to 100 nodes. They are overall limited by the ns2 simulator and are working on optimizations to enable simulations of larger networks. The overall results show that DSR in most cases performs better then ADODV.Interesting points included: ADODV and DSR both suffer from congestion with 40 sources transmitting. ADODV only performs 15% better at high mobility with an disproportionally larger routing overhead. ADODV has a routing overhead higher by a factor of 2-3 in most cases. ADODV normalized network load was significantly higher for all scenarios due to its pro-active nature. The author's also add the metric of end-to-end delay to their evaluation metrics and found that ADODV had lower delays at high mobility rates. At low source levels of 10-20 sources ADODV and DSR had similar delay, but as number of sources and therefore network load increased ADODV's delay also increased due to network congestion. ADODV performance was better then DSR in overall throughput and lower delay that was attributed to DSR's cached routing information becoming stale. The need for network balancing within the protocol's is mentioned, since the performance metrics encounter congestion limits. From mp98@cornell.edu Tue Oct 1 11:59:04 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 g91Fx3h24076 for ; Tue, 1 Oct 2002 11:59:04 -0400 (EDT) Received: from cornell.edu (dhcp226.libecafe-dhcp.cornell.edu [128.253.117.226]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA09550 for ; Tue, 1 Oct 2002 11:59:04 -0400 (EDT) From: mp98@cornell.edu Date: Tue, 1 Oct 2002 11:59:05 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 25 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: X-Mailer: Apple Mail (2.546) This is another comparison paper, this time focusing specifically on AODV and DSR. It does a good job focusing on the differences between the two protocols and the resultant trade-offs: For example, DSR's specification requires promiscuous learning, whereas AODV does not take advantage of it; DSR can maintain multiple routes whereas AODV has only one; DSR has no explicit reoute expiration mechanism; and AODV's broken link flooding is more extensive. This papers tries to closely model the implementation of the previous one. Like the previous paper as well, they assume bidirectional links and modify DSR in the logical way to take advantage of it (i.e. Route replies may use the final path in the route request). Their models are much the same as well: Random waypoint movement, and random source and destination pairs to maintain a constant bit rate. Though the numbers change, they are still creating a series of network scenarios based on different pause times, number of sources, What must really separate this paper from the previous is their metrics: Packet Delivery Fraction - This was covered in the previous paper, but here DSR does not vastly outperform AODV. The authors feel that this is because they are considering larger loads. Delay - This was not considered in the previous work. AODV tends to outperform DSR here, possibly due to the higher overhead of finding an entire route (and the way the destination replies to all route request packets it sees, congesting the network). Loads - Both MAC and routing. Although the previous paper measured the total number of packets sent, this metric is a measure of the ratio of overhead packets (only routing packets for routing load, but routing and link layer packets for MAC load) to data packets. DSR always has more efficient routing loads, but AODV tends to outperform in terms of MAC loads--DSR sends fewer packets, but has a lot RTS retransmission according to the authors. This paper is an improvement over the previous one due to a superior choice of metrics. Ultimately, however, I still would like to see it re-implemented with a different movement and communications model. From ks238@cornell.edu Tue Oct 1 11:59: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 g91Fxgh24160 for ; Tue, 1 Oct 2002 11:59:42 -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 LAA07381 for ; Tue, 1 Oct 2002 11:59:42 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001115850.01cfbe30@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:59:13 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #25 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In this paper we see that two of the best performing reactive protocols that have been evaluated thus far are simulated and compared. The first protocol is DSR which is an on-demand routing protocol that uses route caches to store multiple "hop-by-hop" routes from the same source to the same destination. This was a key feature for those networks that exhibited large amounts of mobility and thus were constantly experiencing link failures between certain nodes. With route caches, alternate paths were easily found without the need to undergo an additional route request. AODV, also another on-demand routing protocol, did away with the idea of route caching and having multiple routes between two nodes, and instead adopted route tables that stored only one route which was discovered when needed. In addition, old routes were discarded after they were idle passed a certain expiration date. This significantly improved AODV's performance in highly mobile networks. The simulation that was used by the authors was based on the NS-2 simulator that was used in the last paper as well. Once again 802.11 is used as the MAC layer protocol which provides a simulation environment for ad hoc networks. The simulations implement their own Traffic and Mobility Models on 50 nodes and 100 nodes that are moving at random speeds to random locations and are pausing for designated periods of time (varying the speed with which topologies are changing). The performance metrics that are evaluated are the success of packet delivery, end-to-end delays of packets, normalized routing loads and MAC load. The results are consistent with original conjectures. In a slow moving and relatively link error free topology, DSR performs reliably and optimally. This can obviously be attributed to the fact that in slow moving topologies should few links fail, DSR's performance will not be substantially effected. On the other hand, AODV performs much better in those topologies that are undergoing dramatic topology changes. This can be attributed to the fact that route discovery in AODV is more reliable (i.e. fresher routes) than route discovery in DSR, even though DSR has less load overhead. Route discovery is the primary activity in highly mobile activities and its efficiency is vital. From yao@CS.Cornell.EDU Tue Oct 1 12:51:28 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 g91GpSh05892 for ; Tue, 1 Oct 2002 12:51:28 -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 25 Date: Tue, 1 Oct 2002 12:51:27 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D43024797FB@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 25 Thread-Index: AcJpaslrc66Mxw7ZSAyGYPcEFcBBEQ== 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 g91GpSh05892 The paper compares two on-demand ad-hoc routing protocols, DSR and AODV on ns2. It starts with a brief description and comparision of two routing protocols. The main differences of them are: First, DSR has access to greater amount of routing information than AODV, becasue of the soure routing nature, and have less route discovery. Second, DSR replies to all requests thus the source node learns many different paths while AODV just replies once. However, the overhead is also increased by replying a request multiple times. Third, DSR has no explicit mechansim to expire stale route information, but AODV use timers to remove old route entries. Fourth, AODV propagates errors to all the nodes using RERR messages. In DSR, only upstream nodes are aware of the link failure promptly. The authors perform well-designed experiments and make a detailed analysis of experiment results. Several important conclusions are listed here. 1. With high mobility, AODV outperforms DSR in terms of packet delivery rate and latency. However, DSR wins if nodes mobility becomes low. 2. DSR usually introduce less routing overhead than AODV, partially because of caching and promiscuous propagation in DSR. Another reason is that it is usually cheaper to increase the packet length, instead of sending multiple small packets. Since AODV generate more route requests than DSR, although the packet size of DSR is larger, the overall cost of AODV is still higher than DSR. 3. DSR have higher cost in all scenarios if the MAC layer overhead is considered. 4. DSR will usually find shorter paths than AODV. Although more nodes are involved in experiments than the previous paper, it stll has limited results of how these protocols scale to larger networks with hundreds or even thousands of nodes, for examle, sensor networks. Another possilbe performance metrice could be the power consumption, which is a better reflection of the overall cost of the routing protocol. Yong From sc329@cornell.edu Tue Oct 1 13:14:24 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 g91HENh11004 for ; Tue, 1 Oct 2002 13:14:23 -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 NAA07415 for ; Tue, 1 Oct 2002 13:14:21 -0400 (EDT) Message-Id: <5.1.0.14.2.20021001131119.00b1a580@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 13:14:23 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 25 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chandrakumar Performance Comparison of Two On-Demand routing protocols for Ad Hoc networks This paper presents a study of performance of two dynamic routing protocols for ad hoc networks: DSR and AODV. They both share a few common characteristics in that they are reactive, discovers new routes and failed routes through various packets and the routing information is stored in the intermediate nodes. DSR uses source routing technique. A node sends out route request packets to all its neighbors flooding the network till it reaches the destination. Upon receiveing a route reply packets, the route is cached for future use. Upon route failures, route error packets are sent to the source node, which can then use alternate routes if it has any or request a new route. AODV uses a table driven approach, where it stores a unique route for each destination. Freshness of information is maintained with the use of sequence numbers. Stale routes are regularly purged from the table. And in case of broken links all the nodes are intimated of the change. The simulation model presented here uses varying number of nodes: 10, 20, 30 & 40 using random waypoint mobility model. The mobility is uniformally distributed between 0-20 m/s. They collect the following metrics: Packet delivery fraction, average end-to-end delay, Normalized routing load, Normalized MAC load.The results show that, when the number of sources is low, the performance (delivery and delay) of DSR and AODV is similar regardless of mobility. With large number of sources, DSR delivers better performance under low-mobility conditions. However, AODV starts outperforming DSR for high mobility scenarios. DSR alwasys demonstrated a lower routing load than AODV. When the major contributor to the routing load for AODV was route requests, route reply and and route error packets formed a major part for DSR's overhead. By virtue of aggressive caching, DSR is more likely to find a route in the cache, and hence resorts to less route discovery than AODV. But DSR presents a higher MAC load in more challenging situations because of the unicast nature of route relies and route errors. Whereas route requests have much less MAC overhear(no use of RTS/CTS/DATA/ACK). So with MAC overhead, DSR was found to have higher network load than AODV. Also AODV seems to finds better routes which are less congested than in the case of DSR. Since the destination replies only to the first arriving route request, this automatically favours the least congested route instead of the shortest route. The major contributions of the paper was in examining the various overhead in both the network and MAC layer. It stresses the importance of coordinating the work of the routing algorithm with the efficiency of MAC layer in order to minimize the overall network overhead.Another contribution is that it summarizes the strengths and weaknesses of the two algorithms and presents some likely real-life scenarios where each of them may be better suited for deployment. From linga@CS.Cornell.EDU Tue Oct 1 13:46:55 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 g91Hkth18522 for ; Tue, 1 Oct 2002 13:46:55 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g91HktE05610 for ; Tue, 1 Oct 2002 13:46:55 -0400 (EDT) Date: Tue, 1 Oct 2002 13:46:54 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 25 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Performance Comparision of DSR and AODV This paper does a detailed performance study of two reactive dynamic routing protocols for adhoc networks (DSR and AODV). Main differences between DSR and AODV: DSR uses source routing (and hence knows the routes to all nodes along the path to the destination) and uses route cache aggresively whereas AODV uses a more conservative approach where each node maintains a routing table with one entry per destination and uses a sequence-number driven approach to maintain fresh routes. The authors use the simulation environment (based on NS-2) as proposed in the previous paper. Performance metrics used are: packet delivery fraction, average end-to-end delay of data packets, normalized routing load (number of routing packets sent per one packet delivered at the destination), normalized MAC load (number of routing, ARP and control packets sent per one packet delivered at the destination). First set of experiments measure the performance of the algos with different number of sources and varying mobility rate. For higher number of sources (30, 40) AODV performs better than DSR for small pause times (packet delivery fraction and packet delay as metrics) but DSR performs better than AODV for larger pause times. DSR has significantly lesser routing load especially at higher number of sources. MAC load for DSR decreases with increasing number of sources and is lesser than that of AODV. The above results are for a network of 50 nodes. Similar results for a network of 100 nodes have also been presented. Utilization of network capacity is extremely low in either of the protocols (throughput about 2-3% of network capacity). DSR works well in case of not so intensive situations (like lesser load, smaller number of nodes etc) and AODV works better in case of more intensive situations (with greater number of nodes, greater mobility etc). Authors propose that the protocols could work better by: using congestion-related metrics in place of short-path metric; removing stale packets from the network which unnecessarily contribute to the routing load. Pros: A comprehensive performance study of DSR and AODV has been presented in this paper. Authors present the performance of these two routing protocols in different scenarios wrt different performance metrics. In short, DSR works well in case of not so intensive situations (like lesser load, smaller number of nodes etc) and AODV works better in case of more intensive situations (with greater number of nodes, greater mobility etc). Authors proposed simple modifications which can improve the performance of these protocols. Cons: Restricted the study to just two protocols. The study is very much similar to the first paper (comparing AODV, DSR, DSDV, TORA) but a little more extensive. Did not consider simple extensions to the versions of the protocols originally proposed (for example DSR does not talk about mechanisms to do expiration of stale routes. Authors did not care to consider a simple scheme to take care of this!) From vivi@CS.Cornell.EDU Tue Oct 1 14:02: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 g91I2Zh21780 for ; Tue, 1 Oct 2002 14:02: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: 615paper25 Date: Tue, 1 Oct 2002 14:02:35 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D14B4B5@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper25 Thread-Index: AcJpdLkn+NP4kcFPRMaWpehX35EkMQ== 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 g91I2Zh21780 This is another performance evaluation paper: It compares DSR and AODV. It concludes that DSR performs better than AODV in less "stressful" conditions (stress = high node density, high mobility), and AODV outperforms DSR in more stressful conditions. Contributions -- The simulations collect the Delay and the Normalized MAC load figures (not commonly measured by simulations in this area). The MAC load could be a very important figure if, as conjectured, the cost of acquiring the channel is significantly larger than the subsequent cost of transmitting a packet. The MAC Load gives the total number of MAC packets transmitted for each delivered data packet. This, along with the Routing Load, are very accurate measures of the total overhead. -- The paper makes one very interesting observation: at high load, the Delay associated with a path is not correlated to the number of hops in the path; rather, the excessive delay at the most congested node in the path is the most significant factor in the end-to-end delay. This strengthens the claim that hop-count is not a very important metric. The paper suggests the following modifications to the protocols to improve performance. (though how good these modifications are can only be tested by another set of simulations) ** Use congestion-related metrics, instead of laying too much importance on shortest-hop paths. ** Remove old packets from the network. (The paper says that DSR suffers from its policy of aggressive caching in conditions of high mobility and high loads.) The paper could be improved by implementing the suggested modifications and redoing the simulations.