From tmroeder@CS.Cornell.EDU Mon Sep 9 17:18:27 2002 Received: from dhcp98-44.cs.cornell.edu (dhcp98-44.cs.cornell.edu [128.84.98.44]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g89LIRh00940 for ; Mon, 9 Sep 2002 17:18:27 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp98-44.cs.cornell.edu (8.11.6/8.11.6) id g89LIRD01736; Mon, 9 Sep 2002 17:18:27 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15741.4131.460749.880736@dhcp98-44.cs.cornell.edu> Date: Mon, 9 Sep 2002 17:18:27 -0400 To: Emin Gun Sirer Subject: 615 PAPER #7 X-Mailer: VM 7.07 under Emacs 21.2.1 AODV is the first hybrid protocol that we have examined. It does require some proactive actions (the "hello" packet in particular) to maintain routing information, but other than that, it only seeks routes when it needs them, and tries to let them decay when the are no longer being used. It uses the distance vector idea, and so only knows about local neighborhoods, and finds out about global topology on demand. It has been examined on large numbers of nodes (at least within the context of a simulator), and so has a better claim to scalability than any of the protocols that we have examined thus far, which at best examined 10's of nodes. They assume bidirectionality of the wireless connections, and try to determine within the protocol if this assumption holds true. There is also an implication that nodes must offer their services to be forwarders of packets, but this is never mentioned again. If true, this could help the load-balancing problem by allowing over-used nodes on common routes to require the other hosts to route around them for a while so that they could conserve power or do a computation or whatever. One of my main concerns with the protocol is that it doesn't seem to achieve its desire. It works OK on large numbers of nodes, but not very well (70%). It is difficult to say if this result is even valid, for there were certain choices made about random motion of the nodes, and the size of the room in which they operate that could be questioned. There's no particularly compelling evidence presented that these parameters are correct, and they may artifact the results out of existence. As usual, there are no security issues addressed, and a malicious node could easily disrupt the network by claiming very short paths. An interesting question which this and other papers bring up (perhaps it has already been addressed) is how well these network simulators represent reality, and what assumptions are build into them. It would be interesting to see the results of tests run "in the wild" like the PRNET examples, and compared to simulated results of the same situations. There may be little effects which change important results. In any case, in the simulation, they still rely on random motion as a worst case, which is almost certainly not true. A point to research might well be to examine worst-case motions of nodes within a network and try to discover what they are for different protocols. From mvp9@cornell.edu Mon Sep 9 21:20:45 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 g8A1Kih20011 for ; Mon, 9 Sep 2002 21:20:44 -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 VAA19333 for ; Mon, 9 Sep 2002 21:20:41 -0400 (EDT) Date: Mon, 9 Sep 2002 21:20:41 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents AODV - another modication to the simple distance vector protocol that eliminates loops and improves efficiency for ad-hoc networks. Destination sequence numbers are adopted from DSDV to prevent loops from forming. The efficiency gain over DSDV is made by eliminating regular route broadcast messages and maintaining only active route information, making AODV a reactive protocol. By caching active routes, a host can discover a new route quickly if one of the nodes its request hits already has a recent route to the destination. "Hello" messages are apparently used mostly to discover neighbors that are still alive, which eats up bandwidth in larger networks, but their other uses are left unexplained. The protocol presented is of considerable value, especially considering that it has been successfully tested on a fairly large number of nodes. The simulation shows that the success of the protocol is fairly dependent on the choice of several parameter values, whose optimal value in turn depends on number of nodes and quality of links. Hence, simulations may be required to be run to find the best values for a given network. As their simulation validates, the protocol allows quick acquisition of routes and handling of broken links and is proven to be loop-free in a separate section - thus all the goals have been achieved. One unfortunate feature of the protocol itself is their combination of network and link layers, even though all the contributions of the protocol are limited to the network layer. Thus, when they encounter significant slowdown from packet collision in larger networks, the lack of separation prevents them from considering other MAC-level solutions such as channel partitioning, taking turns methods, etc. This transplantation seems to be a worthy alternative to pursue. The best, seemingly rare, element of the paper is the series of simulations to determine the best values for its critical parameters. However the simulation itself suffers from excessive randomness, not likely to be present in a real system. There is no explanation of 'aborted sessions' and their significance. There is also no performance comparison to any other ad-hoc protocols that would highlight the success of AODV. Finally, the presentation of the protocol (which is relatively straightforward) is incomplete and could certainly be better structured. From mr228@cornell.edu Mon Sep 9 21:47:11 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 g8A1lAh24884 for ; Mon, 9 Sep 2002 21:47:11 -0400 (EDT) Received: from cornell.edu (syr-24-58-63-179.twcny.rr.com [24.58.63.179]) by cornell.edu (8.9.3/8.9.3) with ESMTP id VAA04736 for ; Mon, 9 Sep 2002 21:47:08 -0400 (EDT) Message-ID: <3D7D4F1B.A6664A83@cornell.edu> Date: Mon, 09 Sep 2002 21:47:07 -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 7 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper presents AODV -- a routing protocol for ad-hoc networks that has nearly all the benefits of DSDV and adds the notion of "only request/store what you need" that is present in DSR. This combination has the potential to produce a substantial increase in performance. By building on DSDV, they are assured that loops and other bad behaviors present in plain DV routing will not occur. By querying for and storing only those routes necessary to satisfy requests from higher layers of the network stack, they reduce bandwidth overhead as well as minimizing storage space required to store the routes locally. The paper discusses simulations that they have run to test their system and it is evident from these tests that although the protocol is highly sensitive to a variety of parameters, when good values are found, the system performs well. A performance comparison of AODV to other protocols is absent. Future work mght seek to derive the optimum values for the various parameters as functions of # of nodes, link quality, network density, and other network characteristics. From hs247@cornell.edu Mon Sep 9 22:08:46 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-1.nyroc.rr.com [24.92.226.177]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8A28kh29493 for ; Mon, 9 Sep 2002 22:08:46 -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 g8A28h319063 for ; Mon, 9 Sep 2002 22:08:44 -0400 (EDT) Message-Id: <5.1.0.14.2.20020909220747.00b84988@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Mon, 09 Sep 2002 22:08:59 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 PAPER 7 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The main contribution of the Perkins paper is the On-Demand Distance Vector Routing. It differs from regular distance vector algorithms and DSDV in that a route from X to Y is only established if a packet needs to be sent from X to Y. In this way, bandwidth is saved as broadcasts are kept to a minimal. Also, the routing tables of a node does not need to grow to N (size of the network), it only stores routing information of nodes it needs to send to. There are several advantages to the on-demand approach. A node can start sending messages once it has established a route to its target node. It doesn't have to figure out the topology of the whole network. Also, the protocol is designed so a node has good knowledge of it neighbours and not necessarily of nodes on the other side of the network. In this way, I feel it may reflect the operation of real world applications more than the other protocols as computers communicate with its neighbours more often then with nodes far away. This locality property also makes the system more scalable than other distance vector protocols. The algorithm has ideas such as reverse and forward path setup, sequence numbers (like DSDV) and hello packets. Like the Dynamic Source routing paper, the model used to simulate the protocol has nodes that are allowed to roam randomly. I feel that this may not accurately reflect how the real world operates. In a way, on-demand was developed for this as nodes should communicate more frequently with its neighbours than nodes on the other side of the network. Also, the authors did not do a good job in talking about related works. I would have liked to see what their thoughts were comparing on-demand to dynamic source routing to on-demand. I feel that these two algorithms conceptually seem very similar, as routes to a node are determined only when needed. A comparison on how this algorithm differs from source routing will be useful. Also a model that models real world applications would better evaluate this protocol. Overall I feel this idea of on-demand is a better fit for ad-hoc networks than other distance vector protocols such as DSDV. It is better for large ad-hoc networks and the properties should be about equal to that of DSDV for small ad-hoc networks. Performance measurements looking at this comparison would be interesting. From shafat@CS.Cornell.EDU Mon Sep 9 23:52:12 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 g8A3qBh19017 for ; Mon, 9 Sep 2002 23:52:11 -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 7 Date: Mon, 9 Sep 2002 23:52:11 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D15078F@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 7 Thread-Index: AcJYfXF7Yl0Pw0SBRU6+RbVtIS4C+g== From: "Syed Shafat Zaman" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8A3qBh19017 This paper describes Ad-hoc On-Demand Distance Vector or AODV routing, a simple yet elegant reactive routing protocol used in wireless networks. It offers loop-free routes and is suitable for dynamic self-starting networks. Like the DSR algorithm, it does not require nodes to maintain a route table entry for each host on the network. On the contrary, it does not even bother to maintain a path to a particular destination if communication with that host does not become necessary. This largely reduces bandwidth consumption as global periodic routing advertisements are no longer required. Path discovery and path maintenance are done with the help of sequence numbers (much like DSDV), and source broadcast id's. These help to ensure that the most up-to-date and the quickest path is stored in the routing tables. The AODV protocol also fixes link failures quickly and reliably to reduce convergence time. Extensive simulation results are presented in the paper to justify the feasibility of the AODV protocol. The simulation environment is also varied largely to accommodate different network sizes. The performance of the protocol as far as scalability is concerned is demonstrated strongly. The paper goes on to suggest further possible improvements on the protocol. Their suggestions are all valid and would definitely improve upon the current performance of AODV. Other suggestions may include: security issues, more work on load-balancing problems and handling of packets of large size, eg. voice packets. From xz56@cornell.edu Tue Sep 10 00:03:35 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8A43Zh21675 for ; Tue, 10 Sep 2002 00:03:35 -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 AAA04026 for ; Tue, 10 Sep 2002 00:03:33 -0400 (EDT) Message-ID: <00be01c2587f$0843b0e0$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 7 Date: Tue, 10 Sep 2002 00:03:34 -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 AODV seems like a combination of DSDV and DSR. Its construction of route is much like that of DSR. Use route queries and replies and also the read of route from the intermediate node's cache. But the use of sequence number of the routing packets and the routing table maintain at each node is more like that in DSDV. While the "hello" massage is more proactive, which maintains local connectivity and lowers the latency and is a good tradeoff between the channel use and routing delay. So the on-demand routing avoids the periodic topology info advertisement and the approach of path maintenance and sequence numbering the routing packets as in DSDV avoids loops and stale routes. Since AODV takes the advantage of the DSDV which has taken care of many possible problems. The only shortcoming I find is that it's a bi-directional routing protocol can not deal with the unidirectional case. From jsy6@cornell.edu Tue Sep 10 00:33:32 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 g8A4XWh28216 for ; Tue, 10 Sep 2002 00:33:32 -0400 (EDT) Received: from Janet (syr-24-58-33-193.twcny.rr.com [24.58.33.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id AAA12457 for ; Tue, 10 Sep 2002 00:33:30 -0400 (EDT) Message-ID: <004501c25883$31727560$a400a8c0@Janet> From: "Janet Suzie Yoon" To: Subject: 615 PAPER 7 Date: Tue, 10 Sep 2002 00:33:20 -0400 MIME-Version: 1.0 X-Security: MIME headers sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.132 $Date: 2001-12-05 20:20:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_0042_01C25861.A9C99E70" 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 is a multi-part message in MIME format. ------=_NextPart_000_0042_01C25861.A9C99E70 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable In the previous paper, Dynamic Source Routing in Ad How Wireless = Networks, many advantages of the Dynamic Source Routing Protocol (DSR) = were listed over a distance vector protocol within an ad hoc wireless = mobile network. The main advantage was the reduced network and CPU = overhead since DSR protocol do not rely on periodic advertisements. The = downside to the DSR protocol was its performance in a partitioned = network. The Ad-hoc On-Demand Distance Vector Routing Protocol (AODV) = provides a modification of the distance vector routing protocol that = does not depend on periodic advertisements yet maintains the same = advantages as other distance vector protocols. Unlike the = Destination-Sequenced Distance Vector (DSDV) algorithm, AODV scales to a = large population of mobile hosts and uses loop free routes, even while = repairing broken links. =20 The DSDV uses system-wide broadcasts as well as local broadcasts known = as hello messages. Hosts use hello messages to find out what other = hosts are in its neighborhood. The AODV uses the same broadcast route = discovery as the DSR protocol but relies on dynamically establishing = route table entries maintained on all the nodes instead of source = routing. Destination sequence numbers, as in the DSDV protocol, are = used to update stale cache routes. The goals of the AODV protocol is as = follows: a host only has to discover and maintain a route to another = host when the two need to communicate (discovery packets are broadcasted = only when needed), distinguish between local connectivity and general = topology maintenance, and disperse information about changes in the = local structure only to those neighboring hosts that are likely to need = the information. =20 One disadvantage of the AODV is that it relies on symmetric links = between neighboring hosts. Much more optimal routes might be found if = asymmetric links were also used instead of ignored. One extension of = this research would be to incorporate non-symmetric links. =20 ------=_NextPart_000_0042_01C25861.A9C99E70 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

In the previous paper, Dynamic Source Routing = in Ad How=20 Wireless Networks, many advantages of the Dynamic Source Routing = Protocol (DSR)=20 were listed over a distance vector protocol within an ad hoc wireless = mobile=20 network.   The main = advantage=20 was the reduced network and CPU overhead since DSR protocol do not rely = on=20 periodic advertisements.  = The=20 downside to the DSR protocol was its performance in a partitioned = network.  The Ad-hoc On-Demand Distance = Vector=20 Routing Protocol (AODV) provides a modification of the distance vector = routing=20 protocol that does not depend on periodic advertisements yet maintains = the same=20 advantages as other distance vector protocols.  Unlike the = Destination-Sequenced=20 Distance Vector (DSDV) algorithm, AODV scales to a large population of = mobile=20 hosts and uses loop free routes, even while repairing broken links. 

The DSDV uses system-wide broadcasts as well as = local=20 broadcasts known as hello messages. =20 Hosts use hello messages to find out what other hosts are in its=20 neighborhood.  The AODV = uses the=20 same broadcast route discovery as the DSR protocol but relies on = dynamically=20 establishing route table entries maintained on all the nodes instead of = source=20 routing.  Destination = sequence=20 numbers, as in the DSDV protocol, are used to update stale cache = routes.  The goals of the AODV protocol = is as=20 follows: a host only has to discover and maintain a route to another = host when=20 the two need to communicate (discovery packets are broadcasted only when = needed), distinguish between local connectivity and general topology=20 maintenance, and disperse information about changes in the local = structure only=20 to those neighboring hosts that are likely to need the information.   

One disadvantage of the AODV is that it relies = on=20 symmetric links between neighboring hosts. =20 Much more optimal routes might be found if asymmetric links were = also=20 used instead of ignored.  = One=20 extension of this research would be to incorporate non-symmetric = links. =20

------=_NextPart_000_0042_01C25861.A9C99E70-- From bd39@cornell.edu Tue Sep 10 00:55:30 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 g8A4tUh01743 for ; Tue, 10 Sep 2002 00:55:30 -0400 (EDT) Received: from cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA27276 for ; Tue, 10 Sep 2002 00:55:28 -0400 (EDT) Message-ID: <3D7D7B24.1010303@cornell.edu> Date: Tue, 10 Sep 2002 00:55:00 -0400 From: Bowei Du User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.0) Gecko/20020605 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 7 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit The main contributions of this paper are a) a new routing reactive routing protocol b) considerations of scaling, and more accurate simulation of node networks of up 1000 nodes. The routing protocol seeks to merge ideas from DSDV and DSR. A sequenced distance vector approach to routing is used, but routes are obtained on demand by flooding. Local connectivity information is obtained by HELLO beacons. The most notable aspect of this paper is the inclusion of scalability simulations to the order of hundreds of nodes, with features such as collision, contention for the MAC layer. There is an interesting choice as the type of traffic simulated, only small data packets. This could be an area of investigate, as the type of routing versus different traffic pattern types. As with DSR, the paper does not address the broadcast storm problem that occurs when the route requests happen. However, some optimizations to avoid flooding of the network were described. As opposed to DSR, in periods of inactivity, nodes still have to broadcast HELLO messages periodically. There is an active/passive vs. power consumption tradeoff that could be investigated.Also, another topic to investigate in AODV would be ways to further reduce collisions in networks consisting of a large number of nodes. HELLO beacons still can result in packet storms, along with flooding for route discovery. From ag75@cornell.edu Tue Sep 10 01:49:42 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 g8A5ngh13718 for ; Tue, 10 Sep 2002 01:49:42 -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 BAA08645 for ; Tue, 10 Sep 2002 01:49:41 -0400 (EDT) Message-ID: <001101c2588d$dc8a4f40$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 7 Date: Tue, 10 Sep 2002 01:49:43 -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 week's papers we were presented with two algorithms: Dynamic Source Routing (DSR) and Ad-hoc On-Demand Distance Vector Routing (AODV). Both algorithms tried to avoid using periodic router advertisements to conserve available bandwidth. At the same time, the algorithms had to be capable of adapting quickly to routing changes. The above had to be done while ensuring that the algorithms are scalable. Since there is no periodic broadcasting, not only is bandwidth overhead reduced, but the mobile devices will be able to conserve more power. The DSR has the advantage of not needing links that work bidirectionally, while AODV does assume symmetric links (though this restriction might be removed in future enhancements). Another advantage that both of these algorithms have is that they do not need to discover and maintain routes to other nodes until they need to communicate. AODV maintains the routing information more efficiently, thus being more scalable than DSR. However, at least for small networks, DSR works better when the host movement is very rapid. Finally, both algorithms use caching to optimize route maintenance, thus improving their performance. There is a huge difference in the amount of testing that was done for each of the algorithms. AODV has been tested extensively with networks of 50, 100, 500 and 1000 nodes while varying a number of parameters. This allowed for good testing, including scalability testing. The rest period of 60 - 300 seconds is much greater than the 0 - 4 seconds rest period used in evaluating DSR, however, which reinforces the claim that DSR can handle very rapid changes better than AODV. Still, AODV is very scalable, which is important, and unconfirmed for DSR. The testing for DSR was not very extensive. Some of the optimizations were not implemented, channel contention was not modeled, and one-way links were also not modeled. Finally, the testing was done on small (up to 24 nodes) networks, and the size of the room was small 9x9 as compared to 50x50 through 150x150 for AODV. More testing is definitely needed to determine the conditions under which each of these algorithms performs better. From mp98@cornell.edu Tue Sep 10 09:27:57 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 g8ADRvh08959 for ; Tue, 10 Sep 2002 09:27:57 -0400 (EDT) Received: from Warren-Lapines-Computer.local. (r105572.resnet.cornell.edu [128.253.240.214]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id JAA03818 for ; Tue, 10 Sep 2002 09:27:56 -0400 (EDT) Date: Tue, 10 Sep 2002 09:27:55 -0400 Mime-Version: 1.0 (Apple Message framework v543) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 PAPER 7 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <1D87D643-C4C1-11D6-B5A3-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.543) The AODV routing protocol described by the authors is somewhat of a mixture of a route discovery protocol (like the one presented in the source routing paper) with a distance vector algorithm (like DSDV): It is not a source routing protocol because a data packet does not contain the full route to the destination, but like the source routing protocol, path discovery is used to find a route. The protocol finds the path to a host by sending out a RREQ messages. When a node receives an RREQ message, if it does not have a suitable route answer and is not the destination, it stores information remembering where the RREQ request came from, and rebroadcasts. If it is the destination or has a suitable route to the destination, it puts it in a RREP packet and sends that packet in the direction the RREQ arrived from. Upon reading an RREP packet, nodes will rebroadcast it back to the original path querier reversing the links they used to forward the RREQ packet and thus forming a path. In some sense, this protocol combines the best of both the Johnson/Maltz paper and DSDV. All the bandwidth savings of path discovery are still present, but nodes only have to store some local information rather than entire routes. The use of sequence numbers nicely avoids loops. The presence of a hop count in an packet RREP was a nice way to ensure that the most efficient route is eventually used. But the aspect of this protocol that really separates it from previous ones is the storage of active neighbors in the routing table. This helps cut down on the amount of flooding used when a break occurs. Like all papers, this one suffers from possible security risks. Future work should be done to address this and finish the benchmarking. The protocol also doesn't yet take advantage of promiscuous information. From smw17@cornell.edu Tue Sep 10 10:00:00 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 g8AE00h15994 for ; Tue, 10 Sep 2002 10:00:00 -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 JAA20254 for ; Tue, 10 Sep 2002 09:59:59 -0400 (EDT) Message-ID: <3D7DFA40.1090203@cornell.edu> Date: Tue, 10 Sep 2002 09:57:20 -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 7 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Dynamic Source Routing / AODV (NOTE - This is a single writeup covering both of the above papers) Dynamic Source Routing and AODV are similar reactive routing schemes that look to create and maintain routes on a demand basis rather than maintaining complete route connectivity at each node. Dynamic Source Routing (DSR) is the simpler of the two protocols, describing a purely reactive ad-hoc network structure. The key to this network is the route discovery mechanism. In the simplest implementation, an unknown route is determined through a broadcast process in which a route request packet is transmitted through the entire network, with basic controls to prevent re-broadcasts and loop formation. As each packet sucessfully reaches the destination, the destination replies to the route request with a route reply that includes the successful route used to reach the destination. Improvements to the basic algorithm are primarily related to more efficient use of the information present in the routing cache, including short-circuit route discovery when a node is reached with a current route and a mechanism for a quick check to determine if a destination node is a neighbor, or if a neighbor has a route to the destination already. In addition, the authors present a scheme to delay broadcast replies and rebroadcasts based on the distance to the source, with the goal of reducing the collision frequency due to temporally correlated responses. In AODV, a very similar discovery procedure is used, but rather than transmitting the entire routing path in a message, only a single next- hop is specified. Once the message reaches the next hop, a routing table local to the next-hop router determines the appropriate system to transmit to in order to reach the destination. The route discovery procedure sets up both a forward and a reverse path for the data, since the absence of the complete routing path precludes the simple reversal of the routing path for the response packet. To ensure that both the forward and reverse paths are viable and current, two sequence counters similar to those in the DSDV protocol are implemented, one for each path. AODV distributes the storage of the routing information along the chosen route, reducing the data overhead for packet routing. The AODV scheme described also makes use of 'hello' frames as a form of limited local network discovery to generate and maintain a picture of the host's neighborhood and to aid in the discovery of broken routes due to mobile hosts. There are two major advantages of these schemes relative to the distance vector schemes previously examined. First, both schemes can potentially reduce storage space and bandwidth requirements based on actual useage. In larger networks, where an all to all communication scheme rather poorly models user behavior, reactive protocols can provide more efficient use of space, power, and bandwidth. Secondly, creating routes on demand eliminates (reduces in AODV) the need for periodic beacons to build routing tables. Reducing the frequency of these potentially large exchanges reduces the power and bandwidth overhead associated with the routing stack. In order to validate their performance claims, the authors give simulated performance data to back up their claims, the first papers we've read that present any hard data. The major disadvantages to both of these schemes is closely tied to most reactive protocols. When a current route exists, the schemes are very efficient. When a route does not exist, however, both schemes are forced to fall back on broadcasting for routing determination. While a broadcast flood will almost always reach the desired destination (save for very rapidly moving hosts), it also consumes massive network band- width and resources. Broadcasting can lead to increased network contention, increased packet loss, and overall increased latencies. In high contention networks, this can further increase the already increased first-packet latency, potentially resulting in higher-level timeouts. And again, user security and robustness in the face of hostile or compromised nodes is barely mentioned. One of the major ideas I would consider to improve upon algorithms presented to date is to include some concept of heirarchy and network structure in the algorithm itself. Considering the work necessary to either maintain routes to every arbitrary 32-bit number we need to worry about, or to build a route with no more information than a destination number, it would seem to me that it may be more efficient to use the network resources to create a dynamic routing heirarchy. /Sean From walsh@cs.duke.edu Tue Sep 10 10:07:49 2002 Received: from duke.cs.duke.edu (duke.cs.duke.edu [152.3.140.1]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8AE7nh18220 for ; Tue, 10 Sep 2002 10:07:49 -0400 (EDT) Received: from localhost (moe.cs.duke.edu [152.3.140.74]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id KAA27184 for ; Tue, 10 Sep 2002 10:07:48 -0400 (EDT) Received: from 132.236.29.117 ( [132.236.29.117]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Tue, 10 Sep 2002 10:07:48 -0400 Message-ID: <1031666868.3d7dfcb4bef09@login.cs.duke.edu> Date: Tue, 10 Sep 2002 10:07:48 -0400 From: walsh@cs.duke.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.0 X-Originating-IP: 132.236.29.117 Ad-hoc On-Demand Distance Vector Routing In light of traditional distance vector (plus optimizations) and dynamic source routing protocols, the authors propose a reactive form of distance vector. In this protocol, nodes only maintain entries for routes currently in use, and populate entries on nodes along the path only when needed. The basic protocol is very similar to destination-sequenced distance vector, but does not rely heavily on periodic broadcast messages, and seems to have far fewer knobs. A weakness cited by the authors is the occasional reliance on periodic beacon messages. The evaluation of the protocol is much stronger than for previous ad- hoc work. The simulator was reused from another university, and reasonable (but still arbitrary) parameters were chosen for motion patterns, loss rates, etc. The results are promising, but not overly optimistic, as in the case of DSR. From nbs24@cornell.edu Tue Sep 10 10:50:23 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8AEoNh28421 for ; Tue, 10 Sep 2002 10:50:23 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id KAA18306; Tue, 10 Sep 2002 10:50:15 -0400 (EDT) Date: Tue, 10 Sep 2002 10:50:15 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209101450.KAA18306@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 7 Paper presents an algorithm, a pure on-demand route acquisition, that builds on the performance of DSDV by minimizing broadcasts and transmission latency. It also uses a broadcast route discovery mechanism as in DSR, but instead of source routing, it dynamically establishes route table entries at intermediate nodes. It was refreshing to see an evaluation of a 1000 nodes in their simulations. This paper failed to convey the true workings of their algorithm to me. Was it necessary to have two sequence numbers? What motivated the choice of 3000ms for their active_route_timeout? What is the difference, in principle, between this timeout and the route request expiration timeout? They could have used simple examples to make their algorithm more understandable, at least for the non- expert. From their findings, as the nodes were increased from 100 to 500, the loss to collision increased from ~6% to ~23%. To build on their research, techniques could be explored to reduce this. Nana B. Sam From ashieh@CS.Cornell.EDU Tue Sep 10 11:43:58 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 g8AFhwh11385 for ; Tue, 10 Sep 2002 11:43:58 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8AFhus10817 for ; Tue, 10 Sep 2002 11:43:56 -0400 (EDT) Date: Tue, 10 Sep 2002 11:43:56 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 7 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ** Contributions This paper presents a reactive scheme that uses a route discovery mechanism similar to that of DSR in an algorithm that inherits aspects from DSDV, namely packet & routing table structure and the loop-free property. AODV's route discovery protocol uses both source and destination sequence numbers to propagate loop-free routing information in both directions (from the source to the destination, and vice versa). Routing entries are pinned (marked as "active") during the route acknowledgement; this serves a similar purpose to the routing path that DSR encodes in the header of each data packet. This pinning overrides the default cache retirement policy. The use of sequence numbers provides explicit staleness management, which DSR does not support. This paper also provides a relatively thorough evaluation of parameters and scalability. ** Shortcomings The pinning and replacement algorithm may lead to performance degradation. Since only the active route is pinned, routing information discovered in the original route request may need to be reacquired, which wastes bandwidth. The experiments did not properly account for the density of nodes in a given area. Instead, the simulation area was tweaked to avoid degradation due to "too small" area. In fact, the node density progressively increases in the 50, 100, 500 experiments, but then decreases for 1000. ** Future work - Directly measure the increase in routing latency due to retired routing information. This information was aggregated with the acquisition latency and possibly session drops. It's possible that more topology-aware (cache longer in critical areas) retirement schemes may have better performance, and these measurements would provide some bounds for the value of such an optimization. From ks238@cornell.edu Tue Sep 10 11:54:15 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 g8AFsFh13864 for ; Tue, 10 Sep 2002 11:54:15 -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 LAA09171 for ; Tue, 10 Sep 2002 11:54:12 -0400 (EDT) Message-Id: <5.1.0.14.2.20020910115347.01b39730@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 10 Sep 2002 11:54:09 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #7 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The Ad-hoc On-Demand Distance Vector Routing protocol is presented in this paper. Once again, like many of the other papers read thus far, the authors begin by investigating some of the problems with other algorithms and then presenting their protocol and how it is able to satisfy the problems raised earlier. Since AODV is a reactive algorithm, we see that the primary issue of concern is memory efficiency (i.e. bandwidth usage and CPU usage) which is one of the biggest problems with the proactive routing algorithm, DSDV. This becomes a grave concern when scalability and transmission speed come into the picture. In the AODV algorithm we see that routes are dynamically created when they are needed. Therefore, the "control message overhead" is much better than O(n2). In AODV we see that path discovery is initiated and conducted by an RREQ packet which uses reverse path setup (storing of the address of the node from which RREQ is received). Then, if the path is current and has been based on RREQ's with the most recent sequence numbers, then a RREP packet is sent, using forward path setup, from the destination node to the source node confirming the presence of a functioning route. Then, with path maintenance, routes are adjusted if any point of failures are detected or if they exceed their active_timeout period. Path maintenance also uses sequence numbers to ensure the use of recent information and hello messages, which ensure that paths remain active. The paper has a summary of a simulation and its results. I found the simulation to be somewhat incomplete. I felt that it wasn't as comprehensive as it should have been. There are a lot more cases and combinations of mobility rates and number of nodes that should have been tested to make the simulation more complete. Another point, at the beginning of the paper they mentioned that scalability was one of problems with previous protocols. Hence, AODV aimed at reducing CPU and bandwidth usage to make the network more efficient when scaling. However, they say that the simulation for 500 to 1000 nodes didn't work well due to excessive number of collisions. I found this to be a pretty blatant weakness in their paper given that the protocol was designed to try to fix this problem. From pj39@cornell.edu Tue Sep 10 11:58: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 g8AFw4h15369 for ; Tue, 10 Sep 2002 11:58:04 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA10101; Tue, 10 Sep 2002 11:58:02 -0400 (EDT) Date: Tue, 10 Sep 2002 11:58:02 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200209101558.LAA10101@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.184 Subject: 615 PAPER 7 This paper on Ad-hoc On-Demand Distance Vector Routing introduces another reactive protocol. The main features of this protocol is that it is scalable to large networks. It aims at minimizing broadcast and transport latency. AODV is a modification of DV/DSDV algorithm. It maitains both source and destination sequence nos borrowed from DSDV. It caches active routes to dynamically establish route at intermediate nodes. It assumes the communication channel to be bidirectional and hence form the reverse path based on the first route request (RREQ) reveived at each node. It uses route caching time out to make older routes invalid. It uses periodic hello messages to detect link failures (neighbor node failure). The paper presents simulation run on networks of varying size's such as 50, 100, 500 and 1000 nodes. The major drawback of the paper is a comparison with other protocols based on different metrics like space requirements, energy and scalability etc. This type of comparison would go long way in helping to understand the merits and demerits of the protocol. Securtiy issues are again not mentioned in the paper. Interaction with higher layer protocols is not made explicit. The protocol in not highly energy efficient as compared to DSR and other Proactive protocols due to the periodic hello messges. Future work might be focussed on making the protocol more energy efficient. More work may be continued to optimize the various parameter's obtained from simulation for different kinds of network topology like higly mobile, very large networks etc. From mtp22@cornell.edu Tue Sep 10 11:58:15 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 g8AFwEh15405 for ; Tue, 10 Sep 2002 11:58:14 -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 LAA24976 for ; Tue, 10 Sep 2002 11:58:11 -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 7 Date: Tue, 10 Sep 2002 11:59:19 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02091011591901.00149@narnia> Content-Transfer-Encoding: 8bit The major contribution of this paper is the first reactive routing protocol for ad hoc networks to be based on distance vector routing, AODV. Such a protocol is important because distance vector routing has certain advantages over other forms of routing, such as source routing. For example, there are scalability issues with source routing. One of these is bandwidth consumption due to tge size of recorded routes; AODV avoids the need to record routes. A weakness of this paper is that it mixes layers in the network stack--as did DSDV. This adds unnecessary confusion to the understanding of the protocol. Another weakness of this paper, as with the DSR paper, is that it doesn't attempt to simulate worst-case scenarios; instead the simulations are done randomly, which may not reflect the worst cases. The work in this paper could be expanded upon by statiscal comparing AODV with other reactive routing protocols, such as DSR. Such data would be useful in determining which protocols are better in practice (and in what situations). From yao@CS.Cornell.EDU Tue Sep 10 12:05:22 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 g8AG5Mh17715 for ; Tue, 10 Sep 2002 12:05:22 -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 7 Date: Tue, 10 Sep 2002 12:05:21 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C20@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 7 Thread-Index: AcJY492i3L7CaMxhSNexRUlrqwp5aQ== 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 g8AG5Mh17715 The Perkins paper intorduces how to design and implement an ad-hoc routing protocol, AODV. Similar to DSR, AODV is a reactive routing protocol, to establish and maintain routes only in use. It also inherits some properties from DSDV, like the sequence number. Sequence number is a very useful technique in AODV. It can be used to avoid loop and propagation of stale routes over the network, which is a hard problem for DSR. AODV also supports local repair from internal nodes, which is very efficient for a large size nework with unstable communication links. The paper includes a good evaluation section with many details and parameter setup. It discusses some implementation details and potential improvement, like how to eliminate Hello message. However, the paper involves too many details, which makes it a little hard to read and easy to lose. If the author can compare AODV to some other well known reactive protocols, like DSR, in a high level in the beginning of the paper, and add more examples, then it would be easier for readers to follow. One problem of AODV is that it could be hard to extend AODV to a network with asymmetric links. Scalabilty is another factor to consider. AODV can support local repair, but the paper does not explain it in details. To me, it is not straightforward, and incremental sequence numbers which takes hops to the destination into account, would make route repair process more efficient. Yong From sc329@cornell.edu Tue Sep 10 13:01:58 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 g8AH1wh29232 for ; Tue, 10 Sep 2002 13:01:58 -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 NAA29658 for ; Tue, 10 Sep 2002 13:01:56 -0400 (EDT) Message-Id: <5.1.0.14.2.20020910125934.00b078f0@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 10 Sep 2002 13:02:04 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 7 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed submitted by : Sangeeth Chandrakumar On-Demand Distance Vector Routing Summary: This paper presents an on-demand distance vector routing for ad hoc networks. The on-demand approach improves over conventional distance vector as well as DSR routings. Not having to make periodic broadcasts helps in reducing the bandwidth usage. AODV also claims to have route free loops and have good scalability properties. The discovery of new routes on demand could increase the transmission latency, if this is not done smoothly. AODV introduces the concept of local broadcasting to become aware of the nodes in the neighborhood. When DSR sends the whole route information as part of the header of each packet, AODV use the route cache of intermediate nodes to route packet to the destination. AODV uses sequence numbers as in DSDV, to differentiate routes which are stale. Every node maintains a monotonically increasing sequence number which is associated with each broadcast messages it generates. If any of the intermediate nodes have a route to the destination with an appropriate seuence number for the destination, the route requeest messages are not propogated further and instead a route reply is generated to the originating host. Along with route request, a route reply path is also determined. AODV makes good use to times outs to determine the various changes that happens in the network topology.It sends unsolicited hello_messages to its active neighbors to advertise the existence of the link between them. Route tables would be updated if a node fails to recieve local bradcasts from its neighbors within a time out period. Failure of links are notified to hosts, which forces a route rediscovery form the originating host. The authors gives a simulation of performance using varying values of timeouts and pause of motion. The results seems toe show a good amount of delivery for both lower as well as higher number of nodes. They furthur claim on basis of this that the protocol is scalable. Comments: - AODV presnets a significant improvement over DSR with respect to channel bandwidth requiremennts. - One of the main drawback of the paper is the assumption of bidirectional links, which is not the usual case in a wireless environment. - Some of the parameters presented in the simulation doenst seem to have a solid rationale behind them more than being just intuitive. Moreover, setting appropriate timeouts would become increasingly difficult as the network size increases. - As described in the future work section, the possibility of route discovery by intermediate nodes instead of the originating node in case of a link failure would be something worth exploring. From liuhz@CS.Cornell.EDU Wed Sep 11 20:25:20 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 g8C0PKh00076 for ; Wed, 11 Sep 2002 20:25:20 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 7 Date: Wed, 11 Sep 2002 20:25:19 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5E0@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 7 Thread-Index: AcJZ8uA86Ai4O2y0R4SMRWdgPNc3SQ== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8C0PKh00076 This paper introduces Ad-hoc On-Demand Distance Vector Routing(AODV). This protocol borrows some ideas from DSDV and DSR, thus supercedes both algortithms in many ways. Unlike DSDV, this On -Demand protocol does not require global periodic routing advertisements(only the hello message, that's quite small, is advertised periodically and locally), thus reduce the demand on the overall bandwidth. Nevertheless, it still maintains most of the advantages of basic distance vector routing mechanisms and provides loop-free routes even while reparing broken links. The size of RREQ and RREP, different from that of DSR, is constant(and quite small) regardless of the size of the network, thus this algorithm can scale to large population, as shown in the simulation. This protocol also suppots multicasting, although the details are not given in this paper. This protocol uses the concept of destination sequence numbers, just like DSDV, to remove stale routing information. AODV relies on the route table entries at intermediate nodes, instead of the route record in the routing packet header in DSR, to build the route. Thus decreases the size of RREQ and RREQ while adds to the demands on the memory space at each host in some way. In worst case, this can be O(n*n), because each host need contain all the active neighbors for each destionation in each route table entry. AODV uses some timeout policies to reduce the size of the table. Only unexpired and active routes are kept in the table. AODV relies heavily on assumption that the network uses bidirectional links, because RREP must return in the reverse path to make this protocol work, while in DSR, a route discovery packet can be sent to find a new route to get back to the sourse if the reverse path does not work. From bd39@cornell.edu Thu Sep 12 00:39:54 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 g8C4drh23553 for ; Thu, 12 Sep 2002 00:39:54 -0400 (EDT) Received: from bomo (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA11220 for ; Thu, 12 Sep 2002 00:39:54 -0400 (EDT) Content-Type: text/plain; charset="us-ascii" From: Bowei Du To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 Date: Thu, 12 Sep 2002 00:39:16 -0400 User-Agent: KMail/1.4.1 MIME-Version: 1.0 Message-Id: <200209120039.16089.bd39@cornell.edu> Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8C4drh23553 This paper identifies a problem with the flooding algorithm in MANETs, mainly that broadcasts created by the flooding algorithm will cause a large amount of collisions and contention to occur at the MAC layer among neighboring nodes. The paper also introduces several schemes to mitigate this problem, all of which selectively decide whether or not to broadcast and propagate a message based upon different metrics, which the paper identifies as probabilistic, by count of broadcasts seen, by distance, by location and by graph clustering. The authors did a good job of analyzing some of the problems and solutions. The simulation is fairly solid; it ranges over dense to sparse node configurations with the different algorithms. One omission of the simulator is that the nodes are static and not mobile, however, it's not certain what effect this would really have on the results. Another omission is that of message loss. It would be interesting to see what effect their schemes have on the robustness of the network transmissions, whether or not enough of the network would remain reachable with bad links factored into the simulation. One area that I thought was particularly interesting was the broadcast among clusters. There are routing protocols for unicasting information in a wireless ad-hoc network, but we haven't seen any protocols for creation and management of efficient broadcast/multicast networks. It would be interesting to investigate routing protocols that formed this kind of efficient clustering networks for broadcasts (even unicast in MANETs are broadcast), taking into consideration the collisions in the MAC layer. -- From vivi@CS.Cornell.EDU Fri Sep 13 15:37:17 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 g8DJbHh03012 for ; Fri, 13 Sep 2002 15:37:17 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper7 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Fri, 13 Sep 2002 15:37:17 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF67@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper7 Thread-Index: AcJbXPfnwNFUcMvJRcmaAVVX2cgVVQ== 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 g8DJbHh03012 AODV The contribution of this work (as the paper says) is the realization of a smoothly functioning system that provides almost optimal routes without resorting to frequent route advertisements. It guarantees loop-free operation, and seems to be better than DSR in incorporating better routes in the middle of a transaction. AODV shares a problem with DSR - if a node that is part of the shortest path from the source to the destination does not hear an RREQ packet broadcast, the route formed will not be a shortest route. But AODV has provisions for switching to a better route, in case a node learns of a better route. (although how a node comes to know of a better route is not discussed) Although routes are not broadcast across the network, nodes still transmit "Hello" messages, which could consume bandwidth and energy, and defeat the purpose of having an On-Demand routing protocol. The paper has not specified what value is used in the "dest_sequence_#" field when a node initiates a route-discovery. This value is of immense significance, as it decides which routes are admissible, and which are not. The simulations performed here are better than the ones we have seen earlier, in the sense that simulation parameters have been determined based on the performance of the protocol in various conditions. But the mechanism used to determine optimal values of parameters "rreq_tries" and "allowed_hello_loss" seems to be faulty, as both are independent parameters, and the simulations are performed by varying one of them while keeping the other constant. There is the possibility that using different values might lead to better performance. Also the simulation of the protocol for 500 and 1000 nodes uses smaller room sizes than is desirable. The work can be extended by making this protocol support Real Time applications. (Right now, this is not possible because of the large delays.) From linga@CS.Cornell.EDU Tue Sep 17 11:58:40 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 g8HFweh01805 for ; Tue, 17 Sep 2002 11:58:40 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8HFweY00551 for ; Tue, 17 Sep 2002 11:58:40 -0400 (EDT) Date: Tue, 17 Sep 2002 11:58:40 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 7 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by sundial.cs.cornell.edu id g8HFweh01805 Temporally-Ordered Routing Alogrithm (TORA) A new distributed routing algorithm for mobile, multihop wireless nets which tries to overcome the problems of previous protocols has been proposed in this paper. Existing protocols have many problems(some like GB, LMR do not work well in case of partitions; others like DSDV provide only a single path for routing). A good routing algorithm should have the following properties: distributed; loop-free; provides multiple routes (to avoid congestion); route creation is fast; minimal communication overhead in reacting to topology changes. Routes are construsted as a destionation-oriented DAG (one per destination). This is done by assigning directions to the edges in an initial complete undirected graph. Route maintenance is essentially converting a direction-disoriented DAG (where there is atleast one more node with no downstream links, inaddition to the destination) back into a destionation oriented DAG. Authors have proposed a new algorithm to do this which works great even in case of network partitions. If there is a link from i to j, node j is said to downstream and node i is said to be upstream. Each node is assigned a reference level (height). When there a like failure, if a node loses its last downstream link it selects a new height so that it becomes the new global maxima. This causes link reversals which may cause other nodes to lose downstream links. Any such node does a partial reversal wrt node that already have higher heights. Authors described a clever way of using a triplet as the reference level and also a delta tuple, to do the job (details in the paper!) Erasing invalid routes is easy: when a network partition is detected, all links in the portion of the network that has become partitioned from the destination are reset to undirected links. Pros: Authors proposed a highly adaptive distributed routing algorithm which is claimed to work well even in case of highly dynamic topological changes. The protocol has competitive worst-case bounds on time-complexity(TC) and communication-complexity(CC) and inaddition overcomes the shortcomings of many of the previous protocols. The protocol has the ability to detect network partitions and also clear invalid routes in finite time. To reduce communication overhead, control messages propagation has been decoupled from the dynamics of the topology of the network (but they pay a price as the quality of DAGs deteriorates.) Cons: -No. simulation results. Worst-case complexities do not give enough insight into how the protocol performs in practise. -Scalability claims not properly justified. They claim that their algorithm is more scalable because of localized reactions to topological changes. -Bi-directional links are assumed which is not a reasonable assumption always.