From eyh5@cornell.edu Wed Sep 5 19:42:21 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 f85NgLq06843 for ; Wed, 5 Sep 2001 19:42:21 -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 TAA20574 for ; Wed, 5 Sep 2001 19:42:19 -0400 (EDT) From: eyh5@cornell.edu Date: Wed, 5 Sep 2001 19:42:18 -0400 (EDT) X-Sender: eyh5@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper proposes a routing scheme, Ad-hoc On-demand Distance Vector (AODV) Routing, derived from the existing Destination-Sequenced Distance Vector (DSDV). Like Dynamic Source Routing (DSR), AODV also reactively conducts a route search when called upon to transmit data packets from a source to a destination. Unlike SDR, however, it limits its presence advertisement only to its closest neighbors (i.e., one-hop with TTL=1). This globally-reactive, locally-proactive advertisement makes a mobile node's presence known to its most immediate neighbors rather than announcing itself to all nodes in the ad-hoc network, thus reducing the usage of bandwidth. Anther advantage of this arrangement is its flexible scalability, which gives relative ease in accepting new mobile nodes into the network. Another difference between AODV and DSR is that in AODV, the route path information is individually stored in each of the intermediate nodes between the source and destination, rather than appending the information to the header of the route request packet (RREQ) as the RREQ traverses along the potential route. Thus, the source node does not possess the complete knowledge (i.e., all intermediate nodes) of the route leading to the destination. This arrangement, according to the authors of the paper, will not only reduce the overhead information contained in the RREQ header, but will also allow a "reverse path" to be established when a route response (RREP) packet is sent back from the destination to the source. One thing that is not made clear in this paper is how the routing protocol will choose the best route to reach a destination if multiple alternatives are offered. The authors do point out that when such a situation occurs, the source node will make a decision to choose one with the greater destination sequence number and the smaller metric (fewer hops). However, in the last paragraph of Section 2.1, it also says that the "source node can begin data transmission as soon as the first RREP is received, and can later update its routing information if it learns of a better route." This statement sounds as to say that as soon as the source node receives the first RREP, it begins transmissions of its packets to the destination, and the "better route" will only be used in it has another stream of packets to send to the same destination in the near future. One improvement that can be made in this routing scheme is in the construction of forward and reverse paths when the RREQ and RREP packets traverse through the network. In fact, a forward path can be constructed at the same time the RREQ is passed from one node (Node A) to its next hop(s). This can be done by passive acknowledgement sent back from the next node (Node B), which will pass on (i.e., broadcast) the RREQ packet. With some additional control information stored in these intermediate nodes, this method might shorten the return delay of the RREP from the destination to the source. From avneesh@csl.cornell.edu Wed Sep 5 21:49:38 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f861nbq17856 for ; Wed, 5 Sep 2001 21:49:37 -0400 (EDT) Content-Class: urn:content-classes:message Subject: 615 PAPER #3 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Wed, 5 Sep 2001 21:53:40 -0400 Message-ID: <97C142C1212ED545B0023A177F5349C4053A59@capricorn.ds.csl.cornell.edu> X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER #3 Thread-Index: AcE2dsA7XLG/yOaqSX6ioJOZwV6jlg== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f861nbq17856 Ad-hoc On-Demand Distance Vector Routing Paper Summary/Critique: This paper describes the AODC protocol, which it seems, has been influenced by the DSDV protocol and extends, modifies and enhances the capabilities of the latter protocol. AODV is an on demand routing protocol, and hence nodes store routes only when reqd, thus reducing the need for broadcast, memory requirements and hence improving the overall scalability. There is no dependence on the medium of communication and it works as long as neighboring nodes can detect each other's broadcasts. In this way, nodes that are not involved in an active path, do not have to maintain routing information. Furthermore, with the help of monotonically increasing sequence numbers, loop free routing is ensured along with higher bandwidth efficiency. Protocol specifics: Path discovery takes place by sending RREQ packets, which are either satisfied by a node, or forwarded. What is important is that the route req packet header does not have all information (source routing), but instead, the intermediate nodes keep routing info. This allows easy setup of the reverse path for the RREP request. The paper states that the source node can begin transmitting as soon as the first RREP is received, and later update the routing information. It is not clear whether this routing information is updated during the same session, or subsequent sessions. There are also some other 'soft state' timers such as route request expiration timers etc, which have been described in functionality, but how they are determined is not explained. One thing interesting is that the protocol uses lower layer interaction (LLACKS), to reduce failure detection latency. There are also a specific local connection management transmissions, which give the idea, that within the neighborhood, a node needs to broadcast to acquire nearest neighbor information, but beyond this, the node, just responds to RREQs only. Unlike DSR, CSMA used here has the usual exponential backoff scheme. Simulations: The simulation scenario is clearly explained though there are some points. It seems that rres_retires=2 and allowed_hello_loss=2 gives a good performance, however for both values=1 in fig 6, the route acquisition latency goes to >500msec for 50 nodes, this was not explained either. I think that the future work ideas, resolve a lot of important issues that came into mind while reading the paper. From the relative performance, AODV seems to provide impressive results. The protocol has many optimizations to remove redundant data from nodes within the system, by maintaining a lot of timing info. Finally, 'goodput ratio' is actually defined in their next paper on multicast routing and not in this one!! From mh97@cornell.edu Wed Sep 5 22:50:24 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 f862oNq23893 for ; Wed, 5 Sep 2001 22:50:23 -0400 (EDT) Received: from mars (dhcp4.csl.cornell.edu [132.236.71.51]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id WAA23099 for ; Wed, 5 Sep 2001 22:50:22 -0400 (EDT) From: "ming hao" To: "'Emin Gun Sirer'" Subject: 615 PAPER 3 Date: Wed, 5 Sep 2001 22:49:44 -0400 Message-ID: <000501c1367e$9573d4a0$3347ec84@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 In-Reply-To: <200109050350.f853o6L00490@hoho.cs.cornell.edu> X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700 Importance: Normal Ad hoc On Demand Distance Vector Routing This paper presents a new routing algorithms for ad hoc network. The New algorithms, DSDV, does not need to broadcast connection messages Periodically and also does not need specify whole route by the source. This results in a nice scalability and less waste of network bandwidth. By hello message and link level failure detection, it can also adapt To the changes of network quickly. The assumption of algorithms is symmetric link and promiscuous working mode Of node. It works in the following way. 1.for route discovery, source node sends RREQ message containing source sequence# and destination sequence#. Only the node containing the route with an equal or larger destination sequence# can satisfy the request. It sends back the reply in the reverse order of sending request. 3. timer is used for each entry. So old entry will be pursed out. 4. when the link to some destination node is broken, active neighbors are informed. Route reconstruction is done by sending a RREQ with destination sequence# one bigger than before. 5. local management is done by hello message or link layer acknowledgement. Simulation results are reasonable. Number of nodes is impressive. But Conditions simulated lacks practical base. Further there are still no comparison with Other algorithms. And no breakdown analysis on how each part of algorithms Contribute to the final result. Further, Active-time-out value strongly depends on type of ad hoc network. The paper does not mention How to choose it dynamically. We will review more algorithms later in class. But till now, I suggest that 1. investigation of regularity of different ad hoc network. I believe that lots of sensers net definitely different from on-class notebook environment 2. for different activity and move pattern, different routing strategies are used and dynamically switched maybe. -ming From wbell@CS.Cornell.EDU Wed Sep 5 23:08:19 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 f8638Iq25584 for ; Wed, 5 Sep 2001 23:08:18 -0400 (EDT) Received: from [192.168.1.100] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id XAA27956 for ; Wed, 5 Sep 2001 23:08:16 -0400 (EDT) Subject: 615 PAPER #3 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.13.99+cvs.2001.09.05.07.08 (Preview Release) Date: 05 Sep 2001 23:07:56 -0400 Message-Id: <999745700.2221.3.camel@brute> Mime-Version: 1.0 3) Ad-Hoc On-Demand Distance Vector Routing AODV is a distance vector routing protocol aimed at providing a loop-free distance vector routing protocol that is more scalable than previous rebroadcasting methods. The goal was that by minimizing the propogation of routing information, the amount of bandwidth consumed by the protocol would be reduced, which would increase the ability to increase nodes. This paper was obviously a response to the Destination-Sequenced Distance Vector algorithm, and hoped to improve upon DSDV by minimizing broadcasts as well as routing table requirements. AODV is a hybrid between the Dynamic Source Routing and traditional Proactive methods, in that it sends periodic 'hello' messages in order to determine local connectivity, but uses route broadcast requests to determine non-neighbor connectivity on demand. They present the AODV algorithm, as well as simulations on it's performance on large (1000 node) mobile networks. This paper was very reactionary, seeming to justify decisions and gain validity because of previous efforts, such as the use of PARSEC simulator without any discussion as to the relevence of it's simulations. I was unhappy with the simulation treatment, as things which the algorithm were clearly trying to acheive were not shown well in the simulations. The route acquisition latency diagrams were difficult to find use for; they showed that by varying the number of retries, they could tune the route acquisition latency, but given that the latency was basically the same for all numbers (except the less valid 0 case), all they did was show that most routes could be acquired in 2 tries in their simulation, which says nothing about its use or tuning in the real world. Another large point was the scalability of this algorithm, yet on the 1000 node case, over 1/3 of all bits transmitted were control bits, which is clearly unacceptable. There was alot of direct comparison to the DSDV algorithm and it's flaws, which were addressed while new problems arose. One of the major issues that arose was their assumption of bidirectional connectivity, something that DSR did not assume, which seems to be a major issue in wireless networks, where higher-powered transmitters can reach a broader area than lower power nodes who can hear them. All in all, I believe that the thrust of this paper was into the world of hybrid DSR/DV algorithms which do local connectivity via neighborhoods, while long distance routing is done by discovery, which when done properly, seems to give a good balance between overhead and efficiency. From daehyun@csl.cornell.edu Thu Sep 6 01:57:23 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 f865vNq10789 for ; Thu, 6 Sep 2001 01:57:23 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id BAA04895 for egs@cs.cornell.edu; Thu, 6 Sep 2001 01:57:18 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109060557.BAA04895@wilkes.csl.cornell.edu> Subject: 615 PAPER 3 To: egs@CS.Cornell.EDU Date: Thu, 6 Sep 2001 01:57:18 -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 presents a routing algorithm called 'Ad-hoc On-Demand Distance Vector Routing' (AODV). AODV uses a broadcast route discovery mechanism as Dynamic Source Routing (DSR). But instead of the source routing, it uses the routing information at intermediate nodes. The sender does not set all routes into packet headers. Instead, intermediate nodes route the packets based on their own routing tables. It also use the concept of destination sequence number form Destination Sequenced distance Vector (DSDV) to maintain the most recent routing information. Important procedures are as follows; 1. Path Discovery : A route is establish by a flooding-like algorithm. The sender broadcasts a RREQ throughout the network. The destination node or any intermediate node that has a valid route to the destination node replies a RREP. The concept of destination sequence number form Destination Sequenced distance Vector (DSDV) is used to maintain the most recent routing information. 2. Path Maintenance : If a link is broken, the node which detects it propagates a RREP through all the active source nodes. Then, the sender can restart the path discovery process again. The major contribution of this paper is that it supports large size network. Scalability comes from two properties of AODV. First it does not require periodic updates of routing table. Second, each node does not maintain the entire routing table and routing is based on the routing tables at intermediate nodes. The simulation results show that AODV can scale up to 1000 nodes well. In my opinion, the weakness of this paper is as follows; 1. I think the simulation in this paper is not relevant. Above all, the simulation result does not show the performance of AODV clearly. It just shows the scalability - the performance for 1000 nodes is as good as that for 50 nodes. Performance comparison with other algorithms should be given to show the absolute performance of AODV. In addition, I think the simulations to determine the optimal parameters are not so important to be devoted such a big portion. 2. I think AODV still has a limitation in scalability. Though routing information is distributed over intermediate nodes, intermediate nodes do not update the routing table dynamically until the sender's request. If a route is broken, it should be notified back to the sender and the sender needs to rebuild the route. I think, as indicated in the future work section, intermediate node route rebuilding will be better for the ad-hoc network which changes the topology frequently. 3. I think AODV does not perform well for the network congestion. Basically, It tries to find the the shortest path regardless of the link status. So it might be possible that a link is used intensively even though there are alternate links not used. Consideration of the network congestion will help scalability and QoS. From kewang@CS.Cornell.EDU Thu Sep 6 09:55:09 2001 Return-Path: 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.7) with ESMTP id f86Dt9q25390 for ; Thu, 6 Sep 2001 09:55:09 -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.4712.0 Subject: 615 PAPER 3 Date: Thu, 6 Sep 2001 09:55:09 -0400 Message-ID: <24C06C2959910949931A2337CB264DCB04BA65@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcE224mBmI2Ou0QMRF+CNB12tcVnrg== From: "Ke Wang" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f86Dt9q25390 This paper gives another on-demand routing algorithm-AODV. It also discovers routes when needed by a discovery process, but the mechanism is quite different. It uses the traditional routing tables to keep the routing information, one entry per destination. In discovery process, a node broadcast a route request (RREQ) to its neighbors, which in turn forward it to their neighbors and so on, until it reaches the destination or an intermediate node with a "fresh" route. What's special of AODV is that AODV introduces time (sequence number) into the protocol to ensure the routes are loop-free and most recent. And it includes some characteristic of traditional proactive routing scheme in the local region. To decide neighbors, the node either sends general packets or broadcast hello message after hello_interval. Compared with DSR, AODV has better scalability because their route tables only keep next node and the packets don't need to include all the routing information. But AODV requires bi-directional communication channels. For the simulation, it is only an event-driven, packet-level simulator and without considering interaction with the lower layers. In the reality, will the MAC layer or some other lower layer's implementation will influence the performance of the routing algorithm? The authors claim that they found some optimal value for parameters like the allowed_hello_loss, but they just got the optimal value just from their simulation results. How can they know their parameters in the simulation are accurate and fit the real ad hoc network? They don't give out any reason why they choose those values. Also the usability of the routing algorithm depends a lot on the application model. AODV is proper for the kind of application that there is frequent communication between random nodes. If there are many nodes need to send message to a few nodes or on the converse, AODV is not so good for it because there will be a lot of unnecessary flooding occurs. From c.tavoularis@utoronto.ca Thu Sep 6 10:37:45 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 f86Ebiq00072 for ; Thu, 6 Sep 2001 10:37:44 -0400 (EDT) Received: from webmail1.ns.utoronto.ca ([128.100.132.24] EHLO webmail1.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 40385]) by bureau6.utcc.utoronto.ca with ESMTP id <238403-483>; Thu, 6 Sep 2001 10:37:38 -0400 Received: by webmail1.ns.utoronto.ca id <126213-4352>; Thu, 6 Sep 2001 10:37:30 -0400 To: COM S 615 Subject: 615 PAPER 3 Message-ID: <999787038.3b978a1e29098@webmail1.ns.utoronto.ca> Date: Thu, 06 Sep 2001 10:37:18 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper presents the Ad-hoc On Demand Distance Vector Routing (AODV) protocol, which, as its name suggests, presents a novel on demand routing solution to dynamically changing wireless networks. The goal of this protocol is to improve on existing routing protocols, focusing on scalability and bandwidth use. AODV borrows a lot of ideas from existing protocols: DVR, although it is pro- active rather than on-demand; DSDV, which inspired the use of sequence numbers to avoid loops; and DSR, by employing a similar route discovery technique. It also presents unique ideas, some more valuable than others. First of all, it makes the distinction between active nodes and non-active nodes that do not need to maintain or forward information. This could lead to further improvements to the network like power saving such that non-active nodes can be identified and turned off. Also, AODV minimizes header information by having each active neighbor in the path keep some routing information for active paths that it belongs to. Routing tables are kept small by having each active path member store just the necessary data in their routing tables, and repeatedly deleting old information after designated timeouts. Finally, routes are set up quickly between neighbors, which simultaneously set up reverse routes to the source. This implies the constraint that links are bi-directional. This protocol was simulated for many cases, including a large-scale network of 1000 nodes. As the authors quickly divulge, this protocol did not perform nearly as well as expected when faced with a large number of nodes. This result is mainly due to packet collisions. This protocol avoids source routing (putting the path in the header) and instead transmits an excessive amount of messages between active neighbors. Active neighbors frequently send RREQ, RREP, and hello messages, which easily contributes to network congestion and packet collisions. As mentioned, an improvement to this protocol would be to eliminate the hello message passing. From gupta@CS.Cornell.EDU Thu Sep 6 11:04:05 2001 Return-Path: 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.7) with ESMTP id f86F45q03093 for ; Thu, 6 Sep 2001 11:04:05 -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.4712.0 Subject: 615 PAPER 3 Date: Thu, 6 Sep 2001 11:04:05 -0400 Message-ID: <404A3A4758DDCC4C8A5C9A537384F9D61BB7FA@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcE25SXY0NL9AKI5EdW1ugCgydyP2Q== From: "Indranil Gupta" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f86F45q03093 ----START---- Ad-hoc on-demand distance vector routing, C.E. Perkins and E.M. Royer. Reviewer: Indranil Gupta Summary: This paper presents AODV, a reactive routing protocol for ad-hoc wireless networks. It adapts several design decisions from the Destination sequenced distance vector (DSDV) protocol, differing from it largely in the fact that DSDV is proactive. A node (re-) discovering a route to a destination floods out a route request message. Intermediary nodes that have a recent cached path to the destination send back a route reply back along the reverse path - this works as only symmetric links are used. Unlike the DSR protocol, routes are maintained at nodes along the actual route and not within the packet - intermediary nodes remember the "next hop" for each (active) destination. Successive route requests from an origin node are distinguished using a per-node broadcast id; this enables duplicated route request elimination. Each (destination) node also maintains a monotonically increasing sequence number, which might be incremented by any other node elsewhere within the network to distinguish broken old routes from new routes, all to this destination node. Tagging routes with this destination sequence number eliminates loops (proved by authors) and stale (broken) routes. A given node replaces the "next hop" to a particular destination only when it (over-)hears a route reply that advertises a path that has a higher destination sequence number than the cached route, or if they are the same, a smaller number of hops to the destination. Outstanding route requests and cached routes time out at each node, and respectively cause a repeat route request only at the originator, and a new route discovery at the node, but only if the destination is a active (i.e., there is an active route to it through this node). Nodes beacon only their immediate neighbors (explicitly or implicitly through acknowledgments). Broken links along an active route are repaired by having the downstream node along the broken link flood a route reply with an incremented destination sequence number and hop count of infinity - upstream nodes along the original route receiving this message could initiate a new route request if the route is still active. The authors evaluate their protocol using a packet-level simulator PARSEC. They use the random waypoint motion + pause time model. Their results seem to show that for both high and low data rates, the protocol delivers 95 % of the packets for 1000 nodes and 98 % of the packets for 50 nodes. Network bandwidth utilizations fall only to 66 % even at 1000 nodes. From these numbers, the authors claim that their protocol is scalable. Comments: - This protocol is an improvement over DSR in that maintaining nodes along the route is certainly more efficient than maintaining it within the packet itself. AODV trades off more storage and lookup time per node for low bandwidth utilization - this makes sense as bandwidth is the scarce resource. - A major criticism of proactive protocols has been that the beacon packet period used in those protocols might not be fast enough for the given mobility and traffic rate. A similar criticism can be applied to the protocols presented in this paper - parameters such as hello message frequency, allowed_hello_loss, route expiration timeout etc. might also not be "up to" the high rate of traffic and mobility. Adaptive protocols might do much better than reactive protocols - has this been investigated ? - Relating to the previous comment, a more general question relating to reactive vs proactive. Are reactive protocols really that much more adaptive than proactive protocols ? Or do the hidden parameters (timeouts, number of retries etc.) in reactive protocols subject them to the same bad behavior of proactive protocols, especially at high rates of traffic and mobility ? If yes, a hybrid protocol that switches between reactivity and proactivity (not as a function of cluster size like ZRP by Haas et al. but) as a function of mobility and traffic, might give us the best of both worlds ... - On detecting a broken link along an active route, the protocol currently has the route origin itself do a route rediscovery. Although this ensures shortest routes always (??), it creates significant overhead if links are flaky/mobility is high. An optimization where intermediary nodes rediscover the path could solve this problem, but would need to be carefully crafted to avoid message explosion. - The simulation data does not seem to mention the bandwidth rate of links !!! Latency measurements do not make much sense without this figure. Do the simulations model wireless bandwidth contention arising out of higher overhead or application traffic ? The reason behind the way most presented plots vary is not explained very well either. - Figure 3 (bars for 100 nodes) : it is counter-intuitive for the goodput to *decrease* with increasing number of route request retries ! Not explained. - Figure 5 is polluted by the fact that the authors do not reveal what fraction of route requests are satisfied with the 1st route request, what fraction with the second route request, and so on (say, with max route request set to 5 or so). - The authors arrive at 'optimal' values of 2 route request retries and 2 allowed hello loss packets for the best goodput from their simulations. It is not clear that these magic numbers will hold if the parameters are varied even slightly, as in the message injection rate or variation of transmission ranges for nodes, etc. - Have any application trace log-based simulations been done to evaluate this algorithms ? How about other ad-hoc routing protocols ? ----END------ From jcb35@cornell.edu Thu Sep 6 11:25:35 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 f86FPZq05214 for ; Thu, 6 Sep 2001 11:25:35 -0400 (EDT) Received: from localhost.localdomain (syr-66-66-30-147.twcny.rr.com [66.66.30.147]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA22586 for ; Thu, 6 Sep 2001 11:25:33 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f86FS4111803 for ; Thu, 6 Sep 2001 11:28:04 -0400 Date: Thu, 6 Sep 2001 11:28:04 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discusses Ad-hoc On Demand Distance Vector Routing (AODV), a reactive routing protocol for ad-hoc networks. The paper claims that this routing protocol leads to better scaling than DSDV and lower bandwidth and better battery use than proactive ad-hoc routing protocols while maintaining most of the advantages of distance-vector routing mechanisms. This algorithm carried a lot over from the DSR paper, including the ideas of sending route requests out (in this case RREQs), answering them with route replies (RREP) and route maintenance (ie. route errors, RERRs). One thing they diverge from DSR on is the assumption of bi-directional length - AODV has no way of handling routes that take advantage of one-way links. Another way they differ is that AODV has as basic structure that will support multicast/broadcast, which is a feature that DSR doesn't have, and in real applications I would think multicast would be a necessity. The individual nodes have timeouts for old routes to ensure that stale routing information doesn't lead to problems - they also use the method of storing sequence numbers for routes at each node to ensure old packets aren't responded to and to prevent loops. In the simulation, the paper pointed out that the protocol did not perform as well as hoped in a large scale network of 1000 nodes due to packet collisions. They note that a large problem in ad-hoc networks is the hidden-terminal problem. By having the intermediate routers keep state (ie instead of tagging the routes on every data packet), the protocol chooses to send more protocol control packets out instead of make the data packets larger. I would be curious to see further work in a couple of different areas, including: - security (these early paper's don't seem to focus much on it, if at all, and I would think it would be more difficult to add it on later than to build it in). - also, the intermediate node route rebuilding seems like a pretty intuitive way to try to improve performance, but as they point out more bandwith is used up during a unsuccessful reconstruction attempt than if a link failure notification had been sent instead. - different hardware - they mention briefly about locality of associate, and this leading to transmitting route information along a backbone. I wonder about how these protocols would perform with if you put a couple of more powerful wireless units in them - One would think that most of the packets would be attempted to be routed through them, and I wonder how these algorithms would respond to congestion along certain routes. - the authors discuss what values of parameters they found to be "optimal," but I wonder if these vary depending on attributes of the network - can they best be adjusted dynamically? From ranveer@CS.Cornell.EDU Thu Sep 6 11:40:53 2001 Return-Path: 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.7) with ESMTP id f86Feqq06860 for ; Thu, 6 Sep 2001 11:40:52 -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.4712.0 Subject: 615 PAPER 3 Date: Thu, 6 Sep 2001 11:40:52 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcE26kxnlSmrXqIyEdW5awCQJ59Etw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f86Feqq06860 Ad Hoc On Demand Distance Vector Routing Authors: Charles Perkins and Elizabeth Royer AODV, as the name suggests, is an on-demand protocol. The basic idea is to send route requests and use the reverse routes to send route replies and establish a path from the source to the destination. Route maintenance is also achieved without much overhead. This protocol uses the idea of sequence numbers to efficiently form loop-free routes. Sequence numbers are similar to logical clocks and are an important part of AODV, more so for MAODV(the multicast protocol). The main contribution of this paper is the idea of using the bidirectionality of links for efficiency and scalability. Since global updates are rare in AODV, the protocol is definitely more scalable. Besides, the protocol is simple and a multicast protocol(MAODV) was easily built on top of this protocol. However, this protocol has a number of disadvantages, just as the other suggested protocols for ad hoc networks. Firstly, it assumes bidirectionality of links which is quite unreasonable. This assumption also rules out most of power-awareness schemes, since otherwise all the nodes would have to simultaneously reduce their power. It should be mentioned that the latest draft(ietf draft 8) of AODV does handle unidirectional links by creating a black list of such links. However, this scheme is unreasonable since unidirectional links are no longer used, while they could be the only way to reach another node. Secondly, the results of this paper are ambiguous. Goodput Ratio is definitely not the best representation of efficiency of a protocol. A more apt measure would have been the ratio of routes that were discovered to the possible routes that are possible to be found. From ms103@cornell.edu Thu Sep 6 11:53:02 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 f86Fr1q08301 for ; Thu, 6 Sep 2001 11:53:01 -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 LAA19228; Thu, 6 Sep 2001 11:52:59 -0400 (EDT) From: ms103@cornell.edu Date: Thu, 6 Sep 2001 11:52:59 -0400 (EDT) X-Sender: ms103@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Perkins and Royer describe and assess an on-demand routing protocol for ad-hoc networks: AODV. The protocol is similar to DSR in that the source initiates route discovery reactively, but it yields it's major advantage over DSR from the fact that the source relies on other nodes to keep track of the route that is eventually (maybe) discovered. This results in a reduction of control traffic (and the myriad of wonderful things that go along with this reduction). By utilitizing time-outs, sequence numbers and 'hello' notices, AODV ensures route integrity. However, I thought that there were too many variable parameters (time-outs, loss counts), that have an effect on performance. Additionally, these parmeters depend heavily on the size of the network. Therefore I think that AODV would struggle to cope with ad-hoc networks that frequently change in size. With regards to their simulation results, I thought the simulation was well developed and executed. However, the symmetric, square room setup that they used could lead to misleading results. This is because nodes are closer and more accesible (on the average) in a symmetric configuration. Apart from that, the goodput and bandwidth overhead ratio figures were impressive. But, the average route acquisition latency figure was large for most cases. From teifel@csl.cornell.edu Thu Sep 6 11:58:21 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 f86FwLq09094 for ; Thu, 6 Sep 2001 11:58:21 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f86FwFr89814 for ; Thu, 6 Sep 2001 11:58:15 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 6 Sep 2001 11:58:15 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 Paper 3 Message-ID: <20010906115639.V81767-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII AhODDVR: This paper is about a new algorithm called Ad-hoc On Demand Distance Vector Routing(AODV). This protocol does not rely on global periodic routing update messages and so it is claimed to achieve higher throughput and scalability. AODV assumes symmetric links between neighboring nodes and the currently implemented protocol is independent of the physical layer of the network. In this scheme only active nodes keep up-to-date routing information about the network. As a result a particular route does not normally need to be discovered until communication is initiated across it. This new algorithm attempts to a) broadcast discovery packets only when needed, b) differentiate between local and global connectivity, and c) relay changes in local connectivity to nodes most likely to benefit from this information. These goals are attempting to increase the bandwidth of the network and reduce the protocol overhead. It is of note that their local connectivity management still uses periodic local broadcast messages to inform near neighbors of node status. The authors fairly detailed description of their simulation environment was more informative than in paper #2. However, in their comparison of their results with prior state protocols I found to be of questionable worth since they use different simulation environments (their's and past authors in the field), etc. I am not sure what the standard practice is in this field, but at least in most simluated fields such as this, it is best to compare various protocols when ran on the same simulation environment (other wise you will be comparing a combined metric of protocol and simulation environment, and all the related hacks that go into sim. software). It was good that they showed the somewhat promising scalability feature of its protocol and for large n (1000), which supposedly is notable in this field. Probably the most promising thing about this paper is the section on future work... if the things in that section can be acheived then AODV will be a promising protocol. From samar@ece.cornell.edu Thu Sep 6 12:05:43 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f86G5hq09755 for ; Thu, 6 Sep 2001 12:05:43 -0400 (EDT) Received: from ockham.ee.cornell.edu (ockham.ee.cornell.edu [128.84.236.58]) by memphis.ece.cornell.edu (8.11.2/8.11.2) with ESMTP id f86G5gN04264 for ; Thu, 6 Sep 2001 12:05:42 -0400 Date: Thu, 6 Sep 2001 12:05:42 -0400 (EDT) From: Prince Samar X-Sender: samar@ockham.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 3. Ad-hoc On-Demand Distance Vector Routing AODV is a reactive routing protocol for Mobile Ad hoc Networks based on distance vectors to form the route to the destination in a distributed way. AODV (and DSR) are under consideration for the experimental RFC status by the MANET Working Group of the IETF. AODV claims to have small amount of routing control traffic, less memory requirements, fast route maintenance, loop free routes and scalable to large networks. But being an on-demand protocol, the latency can be quite high before a route to the destination is found. An important feature of AODV is the maintenance of timer-based states in each node, regarding utilization of individual routing table entries to maintain freshness and prevent loops. These entries time-out and expire if not used in the recent past. As the RREQ propagates through the network, it sets up the "possible" reverse path for the route to the destination by setting up entry about the previous hop. When a RREP is sent back, it adds information about the forward path for the nodes forming the route, and the rest of the nodes delete the useless reverse entries. Each node uses a new broadcast_id for each RREQ that it initiates. AODV uses the memory effectively, maintaining one entry per destination as opposed to DSR which can have multiple route cache entries per destination. Being an on-demand protocol, route queries are initiated only when a node needs a route to a particular destination. Also, as AODV is based on distance vectors, the RREQ messages do not have to carry the accumulated route as it effectively floods the network. Thus the scarce network resources are used only when needed. But at the same time, a single route discovery can find a route to a single destination only, as opposed to DSR where the source and each intermediate node can learn a route to all other nodes present in the source-route. This lack of aggressive route caching makes AODV initiate route discovery more often, which may produce a significant network overhead. AODV also expires route entries if not used for a time-out interval. This has the problem of expiring good routes if not used recently. One drawback of AODV is that it uses bidirectional links only. Thus the protocol needs to check during every route discovery if the links are symmetric. The expiration time for routing table entries depends on the size of the network. This may be a difficult parameter to estimate in a dynamic network with nodes joining and leaving the network. The MAC protocol (CSMA) used by the authors suffers from the hidden terminal and exposed terminal problems. The authors talk of some interesting enhancements to the protocol. They have also recently added expanding ring search to the protocol which seems to improve the scalability of the protocol. The protocol has been simulated for 1000 nodes, which is much more than that for other routing protocols around. In a later work, the authors have shown that DSR outperforms AODV in less stressful conditions, but AODV outperforms DSR in more "stressful" conditions. DSR however usually beats AODV in the amount of routing load generated, probably due to the aggressive caching done by DSR. AODV also seems to be more scalable than DSR. From viran@csl.cornell.edu Thu Sep 6 12:08:39 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f86G8cq10215 for ; Thu, 6 Sep 2001 12:08:38 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f86G8XZ20787 for ; Thu, 6 Sep 2001 12:08:33 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Thu, 6 Sep 2001 12:08:33 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Ad-hoc on-demand distance vector routing This paper introduces a reactive routing scheme similar to DSR that does not require a routing table at each node. One difference from DSR is, instead of having the complete route contained in the packet, forward pointers are kept at each node to correctly route the packet, which reduces the size of the packet in large networks. They also try to distinguish local connectivity vs. general network topology management. However, they required using local periodic "hello" messages to organize a neighbourhood, thus increasing the bandwidth overhead. Their simulations have tried to measure scalability by studying networks of up to 1000 nodes, but the simulator setup does not seem to be very realistic. They used very homogenous packets in their simulations instead of using packets of different sizes. Another problem is lack of mention given to whether they tried to incorporate faulty/weak links in the network. Also, in their results, I don't believe they actually report any type of concrete data or symbol rate numbers. And scalability appears to be a problem they gloss over, as their numbers for the 1000 node case are not very promising. From gleason@CS.Cornell.EDU Thu Sep 6 12:13:25 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 f86GDPq10801 for ; Thu, 6 Sep 2001 12:13:25 -0400 (EDT) Received: from cypher.cs.cornell.edu (dhcp-147.rover.cornell.edu [128.84.24.147]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA21492 for ; Thu, 6 Sep 2001 12:13:23 -0400 (EDT) Message-Id: <5.0.2.1.2.20010906114737.00a7af50@postoffice.mail.cornell.edu> X-Sender: gleason@pop.cs.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.0.2 Date: Thu, 06 Sep 2001 12:11:53 -0400 To: egs@CS.Cornell.EDU From: Sunny Gleason Subject: 615 Paper #3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Ad-hoc On-Demand Distance Vector Routing This papers differs from the DSR paper in its use of routing by intermediate nodes vs. the source node.This cuts down the per-packet overhead from O(k) where k is the diameter of the network to O(1). Interestingly enough, they include "hello" messages in their protocol, which were intentionally left out of the DSR paper. I would think that the "hello" would degrade performance on small-diameter networks; their discussion of control packet overhead was not all that satisfactory. They mention that performance does not scale well with packet size. The assumption that packet sizes are small is disturbing because it means that the much of the bandwidth of the network is wasted on control overhead. It would be interesting to see whether some kind of packet fragmentation for packets routed for distant nodes would be useful. Another notable feature of their routing algorithm is the expiration of routing entries after a certain timeout. Since they are already keeping track of the number of "hello" messages missed by adjacent nodes, I wonder whether the node "volatility" could be incorporated into the route timeout. The new features outlined in the "future work" section sound promising -- although it is unclear whether their simulation methods are sufficient for the complexity of their algorithms. (they hint that 1000 nodes is at the edge of practical simulation; however, this is well within the range of what practical systems should be able to handle). From ramasv@CS.Cornell.EDU Thu Sep 6 12:16:09 2001 Return-Path: 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.7) with ESMTP id f86GG9q10883 for ; Thu, 6 Sep 2001 12:16:09 -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.4712.0 Subject: 615 PAPER 3 Date: Thu, 6 Sep 2001 12:16:08 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F267@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcE27vdTIWti9pUTEdWTbQCQJ5m7oA== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f86GG9q10883 Ad Hoc On Demand Distance Vector Routing AODV is another one of the popular on demand routing protocols designed for ad hoc networks. AODV uses a form of distance vector routing that attempts to reactively discover shortest path routes. Unlike DSR, AODV stores some route information (the next hop for each destination) at the intermediate nodes. This AODV to replace existing routes with better and fresh route more effectively. AODV also uses sequence number to indentify fresh routes, prevent route loops and repair route errors. Being an on-demand routing protocol, AODV employs methods similar to DSR for route discovery. A route request (RREQ) message is broadcast throughout the network whenever a fresh enough route to a destination is not found. Route replies are received from the destination or from intermediate nodes with fresh enough route to the destination. The hop-count metric in the route reply helps AODV discover shortest routes. Each node has a sequence number used to identify fresh routes to that destination. Link breakages are detected either by the neighbor discovery mechanism or indicated by the MAC layer. The downstream part of the route is marked broken by incrementing the sequence number and setting the hop-count infinity. Fresh route requests are initiated by the source to find new route to the destination. A proactive neighbor discovery mechanism is used to AODV to identify new neighbors and detect link breakages. The parameters for this mechanism are not adaptive but fixed irrespective of the topology and mobility pattern. While this could be considered to be a potential disadvantage, the use of this mechanism could be altogether avoided when protocols such as IEEE 802.11 are used. The authors report that using sequence numbers in the specified manner prevent the occurrence of route-loops in the network. However, many practical implementations of AODV have reported route-loops despite several corrections to the sequence number scheme. The absence of methods to detect route loop further intensifies this problem. AODV has been designed to route packets only along the bidirectional links in the network. Even though unidirectional links could be ignored, the need for accurately identifying them still persists and siggested methods such as using a black-list does not seem to be very effective. The simulation results presented in the paper also appear to be inadequate. Standard evaluation parameters such as packet delivery, end-end latency, and control overhead are not reported. The only reported parameter is goodput and that helps only to adjust the protocol parameters. The evaluations performed to find good protocol parameters is inconclusive. It appears that the goodput variation is insignificant when different values of RREQ-Retries and Hello-Loss are tried. Further, steep increase in the route acquisition latency for certain values are not adequately discussed. However, later simulations of this protocol have put it in a better prespective and AODV remains to be an efficient choice for routing in ad hoc networks. From egs@CS.Cornell.EDU Thu Sep 6 14:42:41 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f86Igeq27068 for ; Thu, 6 Sep 2001 14:42:40 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f86IgeJ21619 for egs; Thu, 6 Sep 2001 14:42:40 -0400 (EDT) Date: Thu, 6 Sep 2001 14:42:40 -0400 (EDT) Message-Id: <200109061842.f86IgeJ21619@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 >From papadp@ee.cornell.edu Thu Sep 6 11:39:22 2001 >Date: Thu, 6 Sep 2001 11:46:38 -0400 (EDT) >From: "Panagiotis (Panos) Papadimitratos" >X-Sender: papadp@photon >To: Emin Gun Sirer >cc: Panagiotis Papadimitratos >Subject: 615 - 09/06/01 - AODV review >X-Security: MIME headers sanitized on sundial.cs.cornell.edu > See http://www.impsec.org/email-tools/procmail-security.html > for details. $Revision: 1.129 $Date: 2001-04-14 20:20:43-07 >X-Security: The postmaster has not enabled quarantine of poisoned messages. >Content-ID: > > This message is in MIME format. The first part should be readable text, > while the remaining parts are likely unreadable without MIME-aware tools. > Send mail to mime@docserver.cac.washington.edu for more info. > >--=====================_5229644==_ >Content-Type: TEXT/PLAIN; CHARSET=US-ASCII; FORMAT=flowed >Content-ID: > > >Panos > >--=====================_5229644==_ >Content-Type: TEXT/PLAIN; CHARSET=us-ascii >Content-ID: >Content-Description: >Content-Disposition: ATTACHMENT; FILENAME="Review_AODV.txt" > >Review of: "Ad Hoc On-Demand Distance Vector (AODV) Routing" >C.E. Perkins, E.M. Royer > >Panagiotis Papadimitratos >09/05/01 > >As stated clearly by the paper title, AODV combines on-demand operation with maintenance of a vector of >distances to a set of destinations. The route discovery is initiated only when data have to be sent to a >destination, and any routing information is stored at nodes only when they belong to an active route. The >protocol aims at providing reduced control traffic overhead compared to proactive routing protocols, and at >the same time, prompt and accurate acquisition of topological knowledge. Moreover, quick adaptation to >dynamically changing connectivity is to be provided by the route maintenance operation. Although the >wireless links are not assumed bi-directional, the protocol ignores them and requires that all links >comprising a route be bi-directional. At the same time, no assumptions are required on the characteristics of >the Data Link layer protocol, and as a result, AODV provides the means for local connectivity, or neighbor, >discovery. > >In principle, AODV is invoked only when the source (S) node requires a route to the destination. S >broadcasts a route request packet (RREQ) to its neighbors. If any of them or, more generally, any of the >intermediate nodes, has knowledge of a reasonably fresh route, it provides a route reply (RREP). >Otherwise, it relays RREQ it to its own neighbors, while discarding previously seen or obsolete route >request (i.e., controlled flooding). Either the RREP is provided by some other intermediate node, or >eventually arrives at sought destination (T) (assuming it is reachable). T constructs the route reply and >returns it to S over the reverse of the route followed by the relayed RREQ. Upon reception of the RREP, S >is capable of start transmitting data to T. If at any point during the data transmission any of the route nodes >detects a link breakage, it notifies S, which may proceed by initiating a new route discovery. > >During the two phases of route discovery, the protocol, first, sets up at each traversed intermediate node, as >RREQ's propagates, a reverse path towards S. Then, as RREP's are collected over the reverse path, a >forward path is set towards T, so that potential data packets can be forwarded to T. As a result, each node >along the discovered route maintains two pointers to its successor and its predecessor, and the relevant >information that allows nodes to infer the 'freshness' of routes, RREQ's and RREP's. This state >information is stored only temporarily, and upon expiration is discarded. More specifically, on receipt of >RREQ the route request timer is set, in order to disallow spurious RREP's. While, once the forward path is >set along with the corresponding entries of the nodes' routing tables, the active_route timer is set and >updated by each in-transit data packet making use of the corresponding route. Upon expiration, the route >entry is purged. > >An AODV feature of central importance is the use of sequence numbers, which allow nodes to discard >obsolete route requests, replies and routes and maintain a fresh view of the topology. On one hand, the >source generates monotonically increasing source sequence numbers (sseq) and places them in the RREQ >packets. When the reverse path is created, sseq is placed in the routing table entry, and for subsequent >RREQ's a comparison is made so that a more up-to-date reverse path is set (when RREQ.sseq > >RouteTable.sseq). On the other hand, for each reply generated by the destination (or the intermediate node >generating a gratuitous reply) a destination sequence number is set accordingly (note: there is a slight >difference between the two cases) in order to determine the freshness of the route, i.e., the forward path. > >The neighbor discovery is an AODV feature that may serve the above stated goal, but also renders the >protocol more costly. The periodic transmission of hello messages allows the discovery and maintenance of >a local connectivity view, while increasing the bandwidth and energy consumption. In addition, the >protocol operation relies on a set of parameter values (such as request and route time-out values) that >depend on a multitude of factors. For example, under different assumptions on the node density, mobility >patterns and the communication model (in other words, which nodes communicate with each other) >different delays would occur, and, accordingly, different values would be appropriate. Furthermore, the >packet-level simulation used in this paper fails to capture the effect of important features such as the use of >a shared channel, that could have a significant impact on the network operation. > >In conclusion, AODV resolves in practice problems related to distance vector protocols with the use of >sequence numbers, appears to be able to maintain a low control overhead due to the timer mechanisms, >avoids the transmission overhead pertinent to source routing, requires relatively limited memory storage >and provides an efficient reactive MANET routing protocol. > >--=====================_5229644==_-- > From egs@CS.Cornell.EDU Thu Sep 6 14:44:59 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f86Iiwq27154 for ; Thu, 6 Sep 2001 14:44:58 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f86Iiws21896 for egs; Thu, 6 Sep 2001 14:44:58 -0400 (EDT) Date: Thu, 6 Sep 2001 14:44:58 -0400 (EDT) Message-Id: <200109061844.f86Iiws21896@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 >From andre@CS.Cornell.EDU Thu Sep 6 11:53:35 2001 >Date: Thu, 6 Sep 2001 11:51:22 -0500 >From: =?iso-8859-1?Q?Andr=E9?= Allavena >To: Emin Gun Sirer >Subject: Re: 615 Adaptive Systems. >Content-Disposition: inline >User-Agent: Mutt/1.3.20i > >Ad hoc on demand distance vector routing > >The protocol was design for scalability, routing is not saved in the >headers of each of the packets. Instead each node on the path remmembers >which node is the next one on the path. Route discoveries are sent only >when needed to reduce the overhead. There are also regulat "hello" >messages broacasted to the neighbours to show existence/survivance. >When nodes which disparears, if there are current routes using them, >route broken messages are sent back. > >This protocol seems nice to me. Critics regarding the simulation: the >scalability doesn't seem to be linear sadly. And they didn't do it using >the same conditions. Further more, I think using the same density of >node/m^2 would give more sounded results. > >-- >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 >