From mh97@cornell.edu Mon Oct 22 18:43:36 2001 Return-Path: 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.7) with ESMTP id f9MMhZo18125 for ; Mon, 22 Oct 2001 18:43:35 -0400 (EDT) Received: from mars (dhcp5.csl.cornell.edu [132.236.71.52]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id SAA28615 for ; Mon, 22 Oct 2001 18:43:34 -0400 (EDT) From: "ming hao" To: "'Emin Gun Sirer'" Subject: 615 PAPER 26 Date: Mon, 22 Oct 2001 18:42:36 -0400 Message-ID: <000201c15b4a$d8de4f40$3447ec84@mars> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2616 Importance: Normal In-Reply-To: <200110162318.f9GNIpP11007@zinger.cs.cornell.edu> X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks Charles E.Perkins,Elizabeth M.Royer,Samir R.Das and Mahesh K.Marina. the main differences of these two algorithms are: 1. DSR can grab more route info for each requet-reply cycle than aodv and rhus tends to have less route discovery. 2. destination replies all the requests from differnet paths for DSR while AODV just replies once. 3.cache pollution is main problem of DSR while the TTL machanism may expire valid routes. 4.AODV propagates errors to all the nodes using the broken links while DSR just backs the packets to the upstream nodes. the authors have done a much more thouroughly study for these two algorithms than previous one. some interesting and important results are summarized here. 1. DSR has less routing overhead than AODV. this mainly come from the optimizations of DSR such as caching, promiscuous propagation and the fact that source node gets all the routes for intermediate nodes in addition to the destination nodes. all these make DSR have less routing overhead. 2. but for MAC overhead, AODV tends has less overhead than DSR because MAC layer deal with RREQ and RREP and REER int the differnt way. broadcast does not involve RTS/CTS. so i think the concept of MAC overhead is one of main contributions of this paper. this metric is more accurate than routing overhead in the term of considering power consumtion and bandwidth effeciency. 3. lack of load balancing can result in the long latency. this is reflected when the network has less mobility and more data sources. both algorithms suffered. 4. the trend is that AODV has smaller latency and much higer packet delivery ratio than DSR in the case of higher mobility and more nodes and sources. this stems from the high possibility of DSR's cache pollution and more collision at MAC layer because of the multiple replies. while onthe other hand in the lower mobility environment, the timer mechanism can cause DSDV expire valid route and link failure caused by congestion can be tolerated by DSR because of its abandunt route infomation and salvaging mechanism in the intermediate nodes. 5. as indicated in the previous paper, the DSR tends to have shorter paths. This fact has two sides effect. in the congestion, DSR tends to make thing worse. so load balancing is necessary in the hot spot scenario. in the summary, i like this paper much better than the previous one because it really covers more scenario so that giving us a more complete results.it also explained the deep reasons which is definitely useful for future algorithm development. further, some new metrics are used which can reflect more practical performance of the routing algorithms. -ming From eyh5@ee.cornell.edu Mon Oct 22 22:20:17 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9N2KGo10358 for ; Mon, 22 Oct 2001 22:20:16 -0400 (EDT) Received: from james (james.ee.cornell.edu [128.84.236.65]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9N2KoN17635 for ; Mon, 22 Oct 2001 22:20:50 -0400 Date: Mon, 22 Oct 2001 22:19:06 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 26 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks Charles Perkins, Elizabeth M. Royer, Samir R. Das This paper is intended to evaluate the effectiveness of AODV and DSR, two of the most popular routing algorithms in ad hoc networks. The performance metrics include the packet delivery fraction, average end-to-end delay of data packets, normalized routing load, and normalized MAC load. Although both routing algorithms are based on reactive routing, their designs are sufficiently different, and a simple "better" or "worse" can in no way provide a authoritative judgement of how these two algorithms compare in performance. Indeed, the authors of this paper, and the end of their evaluation, propose several scenarios in which one may be favored than the other, meritting both algorithms to a variety of ad hoc applications in which they may be more effective. A few observations emerge from the evaluations performed in this paper: 1)AODV has a better packet delivery fraction than DSR when the nodes operate in high mobility, whereas the situation is reversed when the mobility is not so great. 2)In a sparsely populated network (i.e., 50 nodes), AODV outperforms DSR in average delay when the nodes operate in high mobility; DSR does better than AODV in this regard when nodes slow down in the network. In a densely populated network (i.e., 100 nodes), AODV consistently incurs less delay than DSR in a much larger range of nodal mobility. This may be due to the fact that the benefit of DSR's route caching is up to a certain extent, beyond which the high load in the network deems this mechanism to o large to improve the performance. 3)DSR has lower routing overhead than AODV. This is due to the fact that AODV employs many route requests, packet-wise, in querying a route, who outnumber the amount of route replies in DSR, a major contributing source of overhead in the latter. 4)When the MAC layer overhead is factored into calculating the total overhead, DSR is found to have higher overall network load than AODV in all scenarios. One of the contributions in this paper is that it examines the overhead in both the network and MAC layers, thus providing a more accurate perspective of the overhead that results from employing the two algorithms. It highlights 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 wbell@CS.Cornell.EDU Mon Oct 22 22:56:39 2001 Return-Path: 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.7) with ESMTP id f9N2udo14457 for ; Mon, 22 Oct 2001 22:56:39 -0400 (EDT) Received: from dhcp-190.rover.cornell.edu (dhcp-190.rover.cornell.edu [128.84.24.190]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id WAA15174 for ; Mon, 22 Oct 2001 22:56:38 -0400 (EDT) Subject: 615 PAPER #26 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit Message-Id: <1003805795.1044.21.camel@brute> Mime-Version: 1.0 X-Mailer: Evolution/0.16.99+cvs.2001.10.18.15.19 (Preview Release) Date: 22 Oct 2001 22:56:17 -0400 26) Performance Comparison of Two On-demand Routing Protocols for Ad- hoc Networks This paper presents a detailed simulation study of DSR and AODV while varying the mobility and the number of sources over 50 node and 100 node networks. Their goal is definitely to critique and provide research as to the usability of DSR and AODV in large networks as usable implementations become commonplace. They utilize ns-2 in an 802.11 simulation environment, matching closely to the Broch et al. paper. By targeting just 2 protocols, they present a more exhaustive study of these two, comparing along 3 axes: number of nodes, number of sources, and pause time. Once again, we see that given a detailed study that neither protocol outshines the other in all respects: with high numbers of sources, AODV tends to have lower packet delays, but at higher mobility, DSR has lower packet delays. We see that both protocols have desirable base cases: at low mobility and link failure, we see high throughput, low packet delays and low routing load. As we change these parameters, the two protocols deviate highly-- we see that as the number of sources grows, AODV's routing load highly increases, while DSR's grows slowly, almost always having a lower routing load than AODV because of aggressive caching. They present observations that routing load is related to MAC overhead and can be used as a good measure for predicting application performance. Since AODV's routing load is mostly broadcast messages, it tends to be comparable to DSR's load (although still about 40% higher), which sends many unicast messages, all of which require an RTS/CTS transmission. This MAC interaction is an interesting point which we have not discussed thus far-- integration of the routing protocol with knowledge of the MAC layer can give better performance than our abstract view of the MAC we've assumed this far. This paper presents a well thought out and detailed discussion of the trade-offs between DSR and AODV and presents the idea that future work should be directed towards better use of the MAC layer by routing protocols. From teifel@csl.cornell.edu Tue Oct 23 03:30:26 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9N7UQo11947 for ; Tue, 23 Oct 2001 03:30:26 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9N7UK236474 for ; Tue, 23 Oct 2001 03:30:20 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 23 Oct 2001 03:30:20 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 26 Message-ID: <20011023032944.U35379-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII on-demand routing comparison: This paper discusses the relative performance of two on-demand ad hoc network routing protocols (DSR and AODV). While this paper is primarily a simulation study, it also makes recommendations for improving the performance of the two protocols. Their simulation model appears to be based on the simulation work developed in the previous paper (paper #25), and so uses a robust version of ns-2 to simulate the wireless ad hoc network protocols. In general, they conclude that DSR is better than AODV in less stressful networks, while it is vice versa in stressful networks. DSR, however, normally will generate less routing load than AODV. They also notice that the DSR caching policy will affect protocol performance. They suggest both protocols can be improved by using congestion-related metrics to evaluate routes, rather than shortest path, which is intuitively obvious--but know one is doing to yet. They also suggest removed aged packets from the network to help congestion. Finally they suggest the behavior between the routing and MAC layers may affect performance. From daehyun@csl.cornell.edu Tue Oct 23 10:04:45 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9NE4jo27232 for ; Tue, 23 Oct 2001 10:04:45 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id KAA09417 for egs@cs.cornell.edu; Tue, 23 Oct 2001 10:04:39 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200110231404.KAA09417@wilkes.csl.cornell.edu> Subject: 615 PAPER 26 To: egs@CS.Cornell.EDU Date: Tue, 23 Oct 2001 10:04:39 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper compares the performance of two on-demand routing protocols - DSR and AODV. It shows that two protocols have significant performance differentials, and proposes techniques to improve them. Two algorithms have the following common and different characteristics; Common Characteristics: 1. The most important common characteristic of two protocols is that they are both reactive. They initiate routing activities on an on demand basis. 2. The route recoveries are based on query and reply cycles. 3. The routing information is stored in intermediate nodes. Different Characteristics; 1. DSR uses a source routing, but AODV uses a table driven routing. As a result, DSR can access more routing information than AODV. 2. DSR replies to all route discovery requests, so the source can have alternative routes, but AODV replies to only the first one and also keeps only one entry in the routing table. 3. DSR does not use any timer, but AODV uses it. AODV have a mechanism to expire old routing information, but DSR does not have such a mechanism. 4. AODV is more conservative than DSR in route deletion. In AODV, a link failure information is sent to all nodes, but in DSR, only the upsteam nodes of a data packet are notified. They performed the simulations, for two experiment sets - Varying mobility and number of sources and Varying offered load, with four metrics - Packet delivery fraction, Average end-to-end delay of data packets, Normalized routing load and Normalized MAC load. In short, DSR shows better performance in less stressful situations, but AODV gets better as the situations go stressful. DSR always has less protocol overhead than AODV. However there are variations with respect to simulation setting. Based on the simulation results, they proposed techniques for two protocols. For DSR, they proposed a timer scheme to eliminate false routing information. For AODV, they proposed a source routing scheme to reduce the protocol overhead. This paper has done similar simulation study as the other paper I have reviewed. The simulation settings and metrics of this paper is also very well designed as that paper. One good thing of this paper is that it tries to suggest new schemes to improve the protocols based on the simulation result. From c.tavoularis@utoronto.ca Tue Oct 23 11:59:29 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9NFxSo11542 for ; Tue, 23 Oct 2001 11:59:28 -0400 (EDT) Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 34350]) by bureau6.utcc.utoronto.ca with ESMTP id <238718-7992>; Tue, 23 Oct 2001 11:59:24 -0400 Received: by webmail3.ns.utoronto.ca id <414676-224>; Tue, 23 Oct 2001 11:58:56 -0400 To: COM S 615 Subject: 615 PAPER 26 Message-ID: <1003852736.3bd593c01cf91@webmail.utoronto.ca> Date: Tue, 23 Oct 2001 11:58:56 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper presents a detailed simulation study of two on-demand routing protocols, AODV and DSR, with accurate MAC and physical layer models. These protocols were evaluated in terms of packet delivery fraction, received throughput in kilobits per second, average end-to-end delay, normalized routing load as well as normalized MAC load. Again, ns-2 was used which models 802.11 network characteristics. Many results are presented, but the general trend is that AODV performs better in high traffic and high load (‘stressful’) situations, while DSR outperforms in low traffic and low load (‘less stressful’) situations. More specifically, DSR has significantly worse packet delivery in high load or high mobility situations, although DSR and AODV have comparable packet delivery otherwise. Delay in DSR is also much higher than AODV in high mobility, although it is slightly less in slow-moving environments. This is an interesting result since DSR focuses on routes with least number of hops, while AODV tends to choose the least congested route. We can see from this result that the shortest route does not imply the least delay. DSR always incurs less routing overhead while frequently incurring higher MAC overhead except in low mobility. The reason that DSR performs poorly in high mobility is because it aggressively uses cached information to find new routes when the current route is broken. When topology is changing quickly, the cached route information becomes stale but continues to be used temporarily and even gets propagated to nodes listening in promiscuous mode. An improvement would be to determine an expiry time for cached information. The cached alternate routes improve DSR performance in low mobility situations when the cached routes remain valid for longer. The increased MAC overhead in DSR is due to frequent use of unicast, as opposed to broadcast, which is more costly at the MAC layer due to use of RTS/CTS/Data/ACK exchanges. AODV has more routing overhead because it generates many more RREQs and essentially floods the network when discovering a route. This paper provides useful MAC layer performance analysis, which is often neglected in the study of routing protocols. It is clear that routing protocol performance is highly dependent on its interaction with lower layers, which has not been optimized in on-demand protocols. One critique would be that although AODV delivers more packets than DSR in stressful environments, its packet delivery ratio is by no means considered sufficient performance for proper operation. Also, unicast is more costly than broadcast at the MAC layer, yet more reliable and I’m surprised that it was not more evident in the simulation results (i.e. affects on packet loss and collisions?). From samar@ece.cornell.edu Tue Oct 23 12:00:37 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9NG0ao11735 for ; Tue, 23 Oct 2001 12:00:36 -0400 (EDT) Received: from descartes (descartes.ee.cornell.edu [128.84.236.60]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9NG18N30473 for ; Tue, 23 Oct 2001 12:01:08 -0400 Date: Tue, 23 Oct 2001 12:00:08 -0400 (EDT) From: Prince Samar X-Sender: samar@descartes.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 26 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 26) Performance Comparison of two On-Demand Routing Portocols for Ad hoc Networks. This paper compares the performance of two popular on-demand ad hoc routing protocols: DSR and AODV. Even though the two protocols reactively find a route to the destination, they differ in many aspects which makes them perform quite differently in different scenarios. Important differences between the protocols are: 1. DSR is based on source routing and has access to a lot more routing information at each node as compared to AODV which is based on distance vectors. 2. The destination replies to many copies of the same query reaching it along different paths in DSR. In AODV, the destination replies to only the first copy of the query reaching it. Thus, a single route request cycle in DSR generates a lot of information which is cached in all the nodes receiving (or overhearing) the reply packet. 3. DSR does not expire stale routes or prefer fresher routes. Thus the aggressive caching of DSR has the drawback of polluting the caches of other nodes too and may severely affect the performance of TCP. 4. The route error messages have the effect of deleting all the routes containing the failed link in AODV. In DSR, the route error message travels back only along the failed route at hand. The simulation model used consists of 802.11 MAC, radio range of 250m, nominal bit rate of 2 Mbps, a send buffer of 64 packets and 50 (100) nodes in an area of 1500m x 300m (2200m x 600m). The velocity of the nodes is uniformly distributed between 0-20m/s and a random waypoint model is used. The metrics evaluated are: packet delivery fraction, end-to-end delay, routing load and MAC load. In terms of metrics like delay and trroughput, the simulation results show that DSR usually performs better on a lower scale and when the network conditions are not stressful. AODV tends to out-perform DSR in more stressful conditions. DSR almost always has a lower routing load than AODV. But when one looks at the total MAC load, DSR was found to generate higher overall network load than AODV in the high mobility or high traffic scenarios. The increase in the MAC load for DSR is attributed to the fact that DSR retuns many routes to the source which are unicasted back. In low mobility cases, DSR works great but its performance degrades below AODV in high mobility cases mainly due to its aggressive use of route caches where the routes are not timed-out. It would have been interesting to see how these two protocols scale to bigger networks with a few hundred nodes. Also the choice of the elongated rectangluar network area again may not necessarily show the whole picture related to these two protocols. The authors mention a few ideas which may possibly improve the performace of these two protocols. The main among them are: expiring stale routes in DSR, using congestion related metrics, removing aged packets from the netwrok and studying in greater detail the effects of interactions between protocol layers. From andre@CS.Cornell.EDU Tue Oct 23 12:46:09 2001 Return-Path: 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.7) with ESMTP id f9NGk8o17261; Tue, 23 Oct 2001 12:46:08 -0400 (EDT) Received: from khaffy (d2192.dialup.cornell.edu [132.236.155.192]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA01765; Tue, 23 Oct 2001 12:46:06 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.31 #1 (Debian)) id 15vz6H-0000SG-00; Tue, 23 Oct 2001 12:48:01 +0200 Date: Tue, 23 Oct 2001 12:48:01 +0200 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Subject: CS615 PAPER 26 Message-ID: <20011023124801.A1588@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= Performance Comparision of AODV and DSR. The settings are a more recent version of AODV compared to the previous paper comparing AODV, TOA, DSR and DSDV. Here the load and the number of nodes is larger. It turns out that DSR perfomrs better in less stresssful situations. (lower overhead, and somehow higher packet delivery). But AODV does better at high rate high number of nodes in the net. The explanation is the agressive use of caching by DSR. It reduces the routing overhead by giving routes really quickly, but those routes are more likely to be stale/outdated in high mobility scenarios. Hence there are useless. But there provide some improvement at low mobility... -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From jcb35@cornell.edu Tue Oct 23 15:03:11 2001 Return-Path: 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.7) with ESMTP id f9NJ3Bo03927 for ; Tue, 23 Oct 2001 15:03:11 -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 PAA11706 for ; Tue, 23 Oct 2001 15:03:07 -0400 (EDT) From: jcb35@cornell.edu Date: Tue, 23 Oct 2001 15:03:07 -0400 (EDT) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 paper 26 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Performance Comparison of AODV and DSR This paper presents a comparison of the aodv and dsr routing protocols. They specifically want to look at how the differences in the two protocols contribute to their performance on ad-hoc networks. DSR uses source routing, so the nodes are able to obtain more information by listening to other routes and peeking at the source routes on packets. Contrary to DSR, AODV only really sees routes in terms of it successor. Because of this, DSR uses caching quit agressivley and may see multiple replies to a route, but a node in AODV will only receive one reply from the destination for each route request. Finally, DSR doesn't expire stale routes, leading to misleading state being kept around on nodes. For the simulator, they used ns-2 like the other paper we read. They also use a random waypoint mobility model in a rectangular field with 50 and 100 nodes. The results indicate that with high mobility, the route caches used in DSR hinder its ability to find routes and so AODV performs better. But with low mobility, AODV is affected every time a link fails, but DSR is unaffected by these link failures, and so it performs better at lower mobility rates. DSR consistantly had fewer routing packets overall in the simulations, but it generated more unicast routing packets, which were expensive in the MAC layer simulator they used, and did not translate to smaller network load. They claimed that the combination of MAC layer and on-demand routing hinders the network capacity, and mention this as a point for future work.