From tmroeder@CS.Cornell.EDU Mon Sep 9 16:30:36 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 g89KUah19380 for ; Mon, 9 Sep 2002 16:30:36 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp98-44.cs.cornell.edu (8.11.6/8.11.6) id g89KUa601712; Mon, 9 Sep 2002 16:30:36 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15741.1260.452974.885433@dhcp98-44.cs.cornell.edu> Date: Mon, 9 Sep 2002 16:30:36 -0400 To: Emin Gun Sirer Subject: 615 PAPER #5 X-Mailer: VM 7.07 under Emacs 21.2.1 The major contribution of the DSR paper was to add a reactive protocol to the literature. The advantages are numerous; one of the greatest benefits is the reduction in the use of bandwidth as overhead for the protocol. If there is no movement, then once the routes are set up, there will be little to no discussion between the hosts about how to route packets. There are also many optimizations in the protocol to help speed convergence of a quickly moving network; there are many caching strategies, and promiscuous mode is used to its fullest to capture any information which might be flying by in the ether. Furthermore, as opposed to the individual hosts along a path making routing decisions, the path is determined by the sender of the packet, and the hosts along the path only need to pass the packet on to the next host as specified in the packet header. This property of the protocol has the effect of requiring little overhead on the part of hosts along the path, and hence eliminating some of the need to route carefully to load-balance the network. They try not to assume bidirectionality in the protocol, but have not truly simulated it in their mockup to see if they deal with such problems well. Another issue is with the evaluation of this protocol. While they have run a few simulations on a very small number of nodes (only 24!), there is no way to tell how well DSR scales to thousands or even hundreds of nodes. Furthermore, in their simulation, there are many magic numbers which control how many packets are dropped, and many other such parameters in the system. They do not know to what degree these parameters affect the simulation, and worse, have given no indication where they got the values from. If they have simply pulled them out of thin air, then there is no reason to believe that their simluation reflects reality at all. The issue of load-balancing is also important: if everyone chooses to pass their packets through a certain machine, then it will wear out more quickly, or its battery will die more quickly. The protocol could take this into account. Points to pursue: - As per Christos Papadimitriou, maybe we should assume a power-law distribution of communication requests rather than an exponential distribution, since that is claimed to be the way people pattern, and people are likely to be the ones using this system. - Verify the parameters chosen, and try to statistically discover what the real parameters are. Further research might also examine the effects of barriers to the radio communication and the effects of disturbances in the air (eg. mircowaves and such :-) - Experimentation could be done with huge numbers of nodes and non-random movements to see if they cause problems with the routing algorithms From mvp9@cornell.edu Mon Sep 9 21:19:52 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 g8A1Jqh19945 for ; Mon, 9 Sep 2002 21:19:52 -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 VAA18980 for ; Mon, 9 Sep 2002 21:19:50 -0400 (EDT) Date: Mon, 9 Sep 2002 21:19:50 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The Johnson and Maltz paper presents a novel approach to ad-hoc routing, using dynamic source routing. This fits neither the link-state nor the distance vector model. The whole route is specified by the source of a packet, and most of the work is shifted over to route maintenance and discovery. Little state is maintained besides cached routes, and there are no periodic broadcasts, greatly decreasing overhead and making the protocol almost purely reactive (optimized for light usage). The danger of routing loops is eliminated by the chosen method of route discovery. The resulting routes are the currently best by the metric of shortest traversal time, which means introducing any other metric would involve considerable modification. Promiscuous mode can be used for some of the proposed optimizations but is not required, which expands their application range. Likewise, bidirectional links are not required. There is also a definite separation of network and link layers allowing freedom in choosing the underlying protocol, certainly a plus. The strengths of paper also include the analysis of several optimizations, a comparison to previous work and protocols, a discussion of likely extensions to the protocol, and of course their simulation which gives very favorable results. The protocol performs nearly optimal in bandwidth overhead and discovered route length. As always, it would be nice to compare their protocol with some other implemented or proposed ones. For example, doing route discovery only when some data is to be sent may introduce unwanted delays, when physically implemented. Also, it is likely that this approach may require more storage than DV protocols, since a whole path is stored for each destination (even with their tree optimization in mind). Their simulation however is lacking in some respects. First the size of the network is relatively small - maxing out at 24 nodes; this is unfortunate because it does not allow exploration of the scaling and graph topology issues that a net of 1000 or so may introduce. At these sizes, their lack of any congestion/ load-balancing mechanisms may become a serious handicap. The many parameters that control the protocol appear arbitrary - begging the question, how accurate is the approximation? Many directions for improvement are suggested throughout the paper, from route discovery flooding method to tricks involving promiscuous listening mode. The simplicity of the protocol promises good things if it is experimentally proves to be as good as it claims. From mr228@cornell.edu Mon Sep 9 21:46:43 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 g8A1khh24842 for ; Mon, 9 Sep 2002 21:46:43 -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 VAA04419 for ; Mon, 9 Sep 2002 21:46:40 -0400 (EDT) Message-ID: <3D7D4F02.A9C80AB8@cornell.edu> Date: Mon, 09 Sep 2002 21:46:42 -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 5 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper describes a routing protocol for use in Ad-hoc wirless networks. Dynamic Source Routing as they call it is a protocol wherein each node stores locally (in a "route cache") the route that a packet should take to get to any other node in the network. Route cache's are initially empty and are filled by issuing route requests. When a node wants to send a packet and doesn't have a route to that destination in its route cache, it floods out a route request and waits for a response from dest indicating the best route to take. They argue that this approach is better than distance vector or link state schemes for a number of reasons. The primary reason is bandwidth savings. Their tests indicate that even in environments with a significant amount of host mobility, the protocol's bandwidth usage is 1% or less of total data transmitted. The paper goes on to present many interesting and very useful optimizations of the protocol, most of which they've implemented and tested. They also present empirical results which, at face value, appear very good. Lastly, they provide a comparison to other work in the area. Future work might be aimed at solving the "constant motion" problem for which this protocol seems to do poorly (Is there really anything that can be done in these environments?) Also, the paper mentions many parameters that it arbitrarily fixes -- optimization of these parameters might also be warranted. From hs247@cornell.edu Mon Sep 9 22:01:48 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-0.nyroc.rr.com [24.92.226.125]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8A21ch27662 for ; Mon, 9 Sep 2002 22:01:38 -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 g8A21X307189 for ; Mon, 9 Sep 2002 22:01:33 -0400 (EDT) Message-Id: <5.1.0.14.2.20020909215816.00b80508@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:01:04 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 PAPER 5 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Johnson & Maltz introduce Dynamic Source Routing for Ad Hoc Wireless Networks. With dynamic source routing, the sender must determine the route of the packet before sending the information. The claim is that dynamic source routing converges faster than Distance Routing and Link State algorithm. There are also dynamic source routing algorithms for wired networks, but Johnson & Maltz introduce ideas of caching and promiscuous receive to try to make dynamic source routing more efficient for ad hoc wireless networks. The authors did a very good job in comparing their algorithm to related works. Many of the ideas in this algorithm are related to other protocols. Things implemented include exponential back-off to preventing flooding of a node, passive acknowledgment (though they call it promiscuous monitoring) and piggy backing of replies. Also, to back their algorithm up, a simulation was set up. Even though a simulation was built, one of the weaknesses was the simulation. They assumed the movement was random and that every node had equal communication capabilities. But in reality this may not be the case. Some nodes may be weaker than others or not want to participate. Also in real life, a "speaker" in the room could be doing most of the talking, (therefore data transfer is broadcasting with one person doing most of the speaking), or groups can be formed in a classroom that may not necessarily need to communicate with other groups. The authors also do not offer any specific example of how this protocol fits in with other layers. In section 3, they mention many alternatives depending on the underlying layer, but don't really say anything specific to which one would be best. Some future work could involve actually implementing this for real world applications, such as a company meeting, a class room or a lecture hall (with people entering and leaving). Also the simulation is only for up to 24 nodes. Does dynamic source routing still work if n is very large? How does this affect the efficiency of the protocol? For ad-hoc networks in general, naming is a huge issue. How does a person entering a room find out about other nodes? (this may be out of scope) From mp98@cornell.edu Mon Sep 9 22:52:15 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 g8A2qFh08002 for ; Mon, 9 Sep 2002 22:52:15 -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 WAA27774 for ; Mon, 9 Sep 2002 22:52:13 -0400 (EDT) Date: Mon, 9 Sep 2002 22:52:12 -0400 Mime-Version: 1.0 (Apple Message framework v543) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 PAPER 5 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <4E5F7E77-C468-11D6-B5A3-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.543) The authors of this paper discuss a source routing protocol designed for wireless networks. Unlike Link State and distance vector algorithms, the source routing protocol does not use a periodic system of updates, but instead uses a query based source routing technique slightly reminiscent of breadth first search to determine the path to a destination. Once obtained, this route will be attached by the host to each packet for that destination, specifying the entire route. Their approach is noteworthy because it provides a simple means to avoid loops--When the entire route is known, one can easily check for them. It takes advantage of the promiscuous nature of wireless communication in several ways: They suggest routers in the network monitoring paths as they go by, and using unsolicited route reply packets if the know of a more efficient route and update their own routing tables if they hear of a better one. The approach of piggy backing is not really innovative, but does help conserve overhead. Like many protocols, this one falls apart on a security level--It is very easy for a host to spoof a route. A more original failing of their protocol is its poor handling of permanent addition or deletions of hosts to the network. While they run lots of tests on moving hosts, and even disjoint sets of hosts, they never run on any tests on the disappearance of old hosts or the sudden appearance of new ones. Instead they brush this point aside, hoping that higher level protocols will eventually give up. Obviously there is still some work to be done to address the failings of the protocol. Also, some elements of promiscuous information discovery bear examination in other contexts, as does the notion of the endpoints specifying the entire route of a packet. From shafat@CS.Cornell.EDU Mon Sep 9 23:51:06 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 g8A3p6h18944 for ; Mon, 9 Sep 2002 23:51:06 -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 5 Date: Mon, 9 Sep 2002 23:51:05 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D15078E@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 5 Thread-Index: AcJYfUo8OhP21g0YQtyV3FRIuI5c3g== 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 g8A3p6h18944 This paper presents a reactive routing algorithm called Dynamic Source Routing (DSR) for use in ad hoc wireless networks. The protocol has a number of distinctive advantages over other (proactive) routing protocols like link-state or distance vector. It adapts quickly to highly dynamic network topologies, incurring no extra overhead cost for propagation of link information. In fact, the paper states only a 1% overhead of total data packets transmitted in a simulated test of a common scenario. This achievement is mainly due to the fact that DSR uses no periodic routing advertisement messages to establish routes in the network. Rather, the initiating node takes on the job of determining a complete path (and, most often the shortest) to the destination before transmitting the packet. Unlike other discussed protocols DSR also does not need links to work bidirectionally, which can lead to a positive impact on performance. A number of optimizations are employed to make the protocol as efficient and reliable as possible. One major issue that was barely touched upon in the paper is that of security. This is all the more important in this protocol as it allows hosts to 'sniff' on any packet while they are in a promiscuous receive mode. In one of the optimization techniques (piggybacking on route discoveries), hosts are even allowed to mask the initiator of a route reply packet - thus leaving the payload vulnerable to any malicious action. The simulations carried out to test the protocol also had some shortcomings. In its simplified version factors like obstacle to transmission etc, were not introduced. Inclusion of these elements would reflect a much clearer picture of load-balancing and congestion control capability of DSR. Also, using a maximum node size of only 24, in a 9-by-9 meter room, does not help predict how the protocol would perform in a much larger setting. The choice of the simulation parameters were also left to the reader to ponder upon. From xz56@cornell.edu Tue Sep 10 00:02:53 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 g8A42rh21601 for ; Tue, 10 Sep 2002 00:02:53 -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 AAA01772 for ; Tue, 10 Sep 2002 00:02:51 -0400 (EDT) Message-ID: <00b801c2587e$ef6a4d40$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 5 Date: Tue, 10 Sep 2002 00:02:51 -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 DSR is relatively an intuitive solution for reactive routing. The key ideas in it is using route discovery protocol to construct source route and using a route cache to store the routes. The route is obtained using a route request/reply dialog when it's needed, which greatly reduced the channel use compared with periodic advertisement of route info in DSDV and related proactive routing protocols. The optimizations of the protocol successfully solved many possible problems. Such as specifying the max # of hops of propagation of the request, use of route cache in the intermediate node to speedup the process of route finding, eavesdropping the route info the reduce the latency, the design of the formation of route error packet etc. But it seems that, the lack of the info on the nodes that are unreachable at the cache will greatly reduce the efficiency of the alg both at the setup and later use (even though the backoff deals with this). And the protocol kinds of assumes a bi-directional link between nodes. The handling of the asymmetric link is not clearly stated. Also, although the reply of the route by intermediate node, on one hand reduces the latency. But on the other hand, it causes the problem of forming of cycle (which solved by adding some complexity) and more seriously the stale route. I am thinking why not add the previous node on the route to the table too. The scalability seems a big problem in this protocol. Because the max hops for the propagation of the request is a necessity to avoid excessive of that, at the same time, it greatly limited the scale of the networks. From bd39@cornell.edu Tue Sep 10 00:22:04 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 g8A4M3h25404 for ; Tue, 10 Sep 2002 00:22:04 -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 AAA16581 for ; Tue, 10 Sep 2002 00:22:02 -0400 (EDT) Message-ID: <3D7D734E.50905@cornell.edu> Date: Tue, 10 Sep 2002 00:21:34 -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 5 References: <200209092143.g89LhSY24712@zinger.cs.cornell.edu> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit The main contribution of this paper is the introduction of a new routing protocol, Dynamic Source Routing. This protocol is reactive and operates differently from both Link State and Distance Vector protocols. Routes are discovered by flooding of the network from the sender on a need basis. Routing information is kept in the DSR packet header itself, and the entire route itself is kept by node in its routing table. The authors identify that transmission costs expended node energy, which is finite, and describe ways to minimize the overhead of the routing protocol (caching, passive acknowledgments, promiscuous listening of other node activity). One major concern that this paper did not fully address about DSR is the effect of the significant number of broadcasts it generates in route discovery. The lack of simulation of collisions in the medium leads to the false assumption that they are not significant. When a route request is flooded to the network, there will be contention for the medium among neighboring nodes all rebroadcasting the route requests. Flooding may also negate the energy benefits of a reactive protocol. Also, the inclusion of the entire route in the protocol packet (both for request and routing) may be prohibitive in terms packet size. The fact that the simulation was limited to at most 24 nodes indicates that issues related to scaling were not tested. The claims about low overhead of the protocol may not be true for larger numbers of nodes. The use of sending error packet back to the original sender seems to be a good idea, however, it seems to be used rather liberally in many cases. It would also be interesting to see how a promiscuous receive vs. full power down of the network interface affects power consumption. Another topic to investigate would be the differences in network latency between active and passive protocols, whether it impacts performance. From ag75@cornell.edu Tue Sep 10 01:48: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 g8A5mvh13685 for ; Tue, 10 Sep 2002 01:48:57 -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 BAA07654 for ; Tue, 10 Sep 2002 01:48:55 -0400 (EDT) Message-ID: <000b01c2588d$c1864370$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 5 Date: Tue, 10 Sep 2002 01:48:57 -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 jsy6@cornell.edu Tue Sep 10 01: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 g8A5sFh14507 for ; Tue, 10 Sep 2002 01:54:15 -0400 (EDT) Received: from Janet (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id BAA07608 for ; Tue, 10 Sep 2002 01:54:14 -0400 (EDT) Message-ID: <000801c2588e$755796b0$a400a8c0@Janet> From: "Janet Suzie Yoon" To: Subject: 615 PAPER 5 Date: Tue, 10 Sep 2002 01:53:59 -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_0005_01C2586C.EDF824D0" 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_0005_01C2586C.EDF824D0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable In source routing, the sender of the packet determines the entire = forwarding sequence of nodes the packet is to take. Each forwarding = "hop" in this route is stored in the packet's header. In a Dynamic = Source Routing Protocol (DSRP), the sender dynamically determines a = route to the target host by first checking its route cache. If a route = to the target is not cached, then a route discovery protocol is used to = find a route. =20 The route discovery protocol used works by the initiator broadcasting a = route request to its neighbors, which propagates down the ad hoc network = until the route request reaches the target or destinations host. In the = event of a successful route discovery, the target sends the initiating = host a route reply packet, which lists the sequence of network hops the = succeeding route request took. The route request packet contains the target or destination host, the = address of the original sender, route record to store the sequence of = hops taken by the route request packet during the route discovery, and a = unique request id set by the sender. Each host maintains a list of = pair in order to be able to detect = duplicate route requests. A host will discard a route request packet = for the following two reasons: if the = pair is listed in the host's record of recently seen requests and if the = host's address is already exists in the route record in the request. If = the host is not the target, then it will append its address to the route = record and then rebroadcast the request. If the host is the target, = then a copy of the route record is sent in a route reply packet tot he = initiator. Since it is not assumed that the links do not work equally = well in both directions, the route reply packet cannot be returned in = reverse order of the route record. Instead, the route reply packet is = piggybacked on a route request targeted at the initiator of the route = discovery. =20 Once a route is obtained, a host may send a packet to another host. The = operation of the route it maintained by the route maintenance procedure = during the use of the route. Any data link errors are reported back to = the original sender in the form or a route error packet. This packet = contains the addresses of both the hosts involved in the hop error. The = original sender truncates all route which contain the erred hop in its = route cache. End-to-end acknowledgement can also be used in lieu of = hop-to-hop acknowledgement to perform route maintenance. =20 There are a number of route discovery and maintenance optimizations that = can be used to reduce overheard packets and improve the average = efficiency of the routes. Most of the optimizations involve making = full use of the route cache. The data in the host's route cache can be = stored as a tree of routes, routed at this host. Route updates and = lookup would be more efficient in this format. A host can also = configuring its network interface into promiscuous mode and updating its = route cache based on any route information from any packet it can = overhear. The route cache can be used to avoid propagating a route = request packet received from another host. If a host A receives a route = request packet for whom the target is a host whose route is stored in = A's route cache, host A can return this route in a route reply packet to = the original sender without re-broadcasting the route request. To avoid = packet collisions and ensure a route of minimum length is most likely = selected, the host must wait for a calculated delay period (based on the = length in number of network hops for the route to be returned) before = transmitting the route reply. To perform a route discovery, a route = request with a hop limit of one is sent. This is to check if the target = is within the transmitter range or if another host within the range has = the route of the target cached. If no route reply is returned, then a = new route request with a predefined maximum hop limit is sent. =20 The main advantage of the DSRP over the distance vector protocol is its = independence from periodic routing advertisement messages. Eliminating = the need for these periodic messages greatly reduces network bandwidth = and CPU overhead. Also, distance vectors may compute some routes that = do not work since it assumes transmissions between two hosts are equal = in both directions. =20 Still, there are some improvements that can be made to the DSRP. In the = case of a partitioned network, DSRP performs worse than the distance = vector algorithm. If a host wants to communicate with an unreachable = host, it will periodically initiate a route request, thus consuming = network resources. The distance vector protocol does not make such = efforts assuming that the routes have converged. Improvement can also = be made in error handling. The current protocol sends a route error = packet to the original sender in face of a data link error, in which the = sender reissues a route request. It might be more efficient if the host = that first detects the error issues the route request and tries to send = the packet to the target itself. Also, while the error packet is being = sent to the original sender, other hosts should listen and update their = route cache as needed. =20 Further research should be done with experimentation of different = parameters such as timeouts and holdoff periods, which must be = configured within the protocol, and their effect. There should also be = more research in respect to security and measures to prevent denial of = service attacks. =20 =20 ------=_NextPart_000_0005_01C2586C.EDF824D0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

In=20 source routing, the sender of the packet determines the entire = forwarding=20 sequence of nodes the packet is to take. =20 Each forwarding =93hop=94 in this route is stored in the = packet=92s=20 header.  In a Dynamic = Source Routing=20 Protocol (DSRP), the sender dynamically determines a route to the target = host by=20 first checking its route cache.  = If=20 a route to the target is not cached, then a route discovery protocol is = used to=20 find a route.   =20

The=20 route discovery protocol used works by the initiator broadcasting a = route=20 request to its neighbors, which propagates down the ad hoc network until = the=20 route request reaches the target or destinations host.  In the event of a successful = route=20 discovery, the target sends the initiating host a route reply packet, = which=20 lists the sequence of network hops the succeeding route request = took.

The=20 route request packet contains the target or destination host, the = address of the=20 original sender, route record to store the sequence of hops taken by the = route=20 request packet during the route discovery, and a unique request id set = by the=20 sender.  Each host = maintains a list=20 of <initiator address, request id> pair in order to be able to = detect=20 duplicate route requests.  = A host=20 will discard a route request packet for the following two reasons: if = the=20 <initiator address, request id> pair is listed in the host=92s = record of=20 recently seen requests and if the host=92s address is already exists in = the route=20 record in the request.  If = the host=20 is not the target, then it will append its address to the route record = and then=20 rebroadcast the request.  = If the=20 host is the target, then a copy of the route record is sent in a route = reply=20 packet tot he initiator.  = Since it=20 is not assumed that the links do not work equally well in both = directions, the=20 route reply packet cannot be returned in reverse order of the route = record.  Instead, the route reply = packet is=20 piggybacked on a route request targeted at the initiator of the route=20 discovery. 

Once=20 a route is obtained, a host may send a packet to another host.  The operation of the route it = maintained=20 by the route maintenance procedure during the use of the route.  Any data link errors are = reported back=20 to the original sender in the form or a route error packet.  This packet contains the = addresses of=20 both the hosts involved in the hop error. =20 The original sender truncates all route which contain the erred = hop in=20 its route cache.  = End-to-end=20 acknowledgement can also be used in lieu of hop-to-hop acknowledgement = to=20 perform route maintenance.   =

There are a number of route discovery and = maintenance=20 optimizations that can be used to reduce overheard packets and improve = the=20 average efficiency of the routes.   Most of the optimizations = involve=20 making full use of the route cache. =20 The data in the host=92s route cache can be stored as a tree of = routes,=20 routed at this host.  = Route updates=20 and lookup would be more efficient in this format.  A host can also configuring = its network=20 interface into promiscuous mode and updating its route cache based on = any route=20 information from any packet it can overhear.  The route cache can be used to = avoid=20 propagating a route request packet received from another host.  If a host A receives a route = request=20 packet for whom the target is a host whose route is stored in A=92s = route cache,=20 host A can return this route in a route reply packet to the original = sender=20 without re-broadcasting the route request. =20 To avoid packet collisions and ensure a route of minimum length = is most=20 likely selected, the host must wait for a calculated delay period (based = on the=20 length in number of network hops for the route to be returned) before=20 transmitting the route reply.  = To=20 perform a route discovery, a route request with a hop limit of one is = sent.  This is to check if the target = is within=20 the transmitter range or if another host within the range has the route = of the=20 target cached.  If no = route reply is=20 returned, then a new route request with a predefined maximum hop limit = is=20 sent. 

The=20 main advantage of the DSRP over the distance vector protocol is its = independence=20 from periodic routing advertisement messages.  Eliminating the need for these = periodic=20 messages greatly reduces network bandwidth and CPU overhead.  Also, distance vectors may = compute some=20 routes that do not work since it assumes transmissions between two hosts = are=20 equal in both directions.  =   

Still, there are some improvements that can be = made to=20 the DSRP.  In the case of = a=20 partitioned network, DSRP performs worse than the distance vector=20 algorithm.  If a host = wants to=20 communicate with an unreachable host, it will periodically initiate a = route=20 request, thus consuming network resources. =20 The distance vector protocol does not make such efforts assuming = that the=20 routes have converged.  = Improvement=20 can also be made in error handling. =20 The current protocol sends a route error packet to the original = sender in=20 face of a data link error, in which the sender reissues a route = request.  It might be more efficient if = the host=20 that first detects the error issues the route request and tries to send = the=20 packet to the target itself.  = Also,=20 while the error packet is being sent to the original sender, other hosts = should=20 listen and update their route cache as needed. 

Further research should be done with = experimentation of=20 different parameters such as timeouts and holdoff periods, which must be = configured within the protocol, and their effect.  There should also be more = research in=20 respect to security and measures to prevent denial of service = attacks. 

 

------=_NextPart_000_0005_01C2586C.EDF824D0-- From sc329@cornell.edu Tue Sep 10 02:12:07 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 g8A6C7h16967 for ; Tue, 10 Sep 2002 02:12:07 -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 CAA03392 for ; Tue, 10 Sep 2002 02:12:06 -0400 (EDT) Message-Id: <5.1.0.14.2.20020910020820.02dcafa8@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 02:12:11 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 5 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed submitted by - Sangeeth Chandrakumar Dynamic Source Routing in Ad Hoc wireless Networks Summary: This paper presents a reactive protocol for routing in ad hoc networks using dynamic source routing. DSR does not send periodic updates as in Distance vector or link state protocols, thus saving bandwidth. Battery power is also conserved on the mobile hosts as need not stay alert to receive regular updates. DSR obviates the need for bi-directional links, though the performance of such links are not quite clear form the paper. when conventional routing fails in the event of dynamic topology changes, DSR seems to adapt well to the various instances of the networks. The basic operation of DSR is by the maintenance of a route cache at every mobile node. A route discovery protocol is used to broadcast packets till the route to the destination is discovered. The route replyt packet send from the destination to the originating host contains the entire route, which would be stored in the cache and used for furthur transmissions to the same destination. Duplicate packets are discarded, and also care is taken to avoid routing loops. in case of uni-directional links, piggy backing of route replys on route requests are used to inform the orifginating host of the route. The paper also presents a number of optimizations, which reduces the number of overheads. By effective use of route cache, introducing delays while broadcasting, by implementing an expanding ring, the number of transmissions can be kept to a minimum. Exponential backoff helps to keep the rate of transmissions low in case the target is not reachable. Also by updating the route cache upon receiving error packets helps to prevent using routes that do not exist. Comments: Though the paper presents a lucid approach of routing protocol, there are a few drawbacks. - The simulation using a few nodes in a small room seems to simplistic to extrapolate the performance of the protocol in a real environment. - The non uniformity of performance with varying number of nodes is not explained. - Though the paper claims a better perfoormance compared to distance Vector ands link state, no evidence is given to ratify the claim. - The assumption of a small "diameter" in the network makes the scalability an issue. - Presence of stale routes are not accounted for, when fresh routes which are shorter might be available. From pj39@cornell.edu Tue Sep 10 02:34:52 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 g8A6Yqh21192 for ; Tue, 10 Sep 2002 02:34:52 -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 CAA23919 for ; Tue, 10 Sep 2002 02:34:49 -0400 (EDT) Date: Tue, 10 Sep 2002 02:34:48 -0400 (EDT) From: pj39@cornell.edu X-Sender: pj39@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper introduces a reactive routing protocol called Dynamic Source Routing (DSR) for routing in ad-hoc networks. The major contribution of this paper is the introduction of Route Discovery which uses flooding to find the route to the destination. This route discovery protocol evidently gives the shortest possible route. The authors argues that this will save a lot of network bandwidth as compared to other Proactive protocols which use periodic beacons for route updates. During period of littly of no movement the nodes can remain in sleep mode thus saving a lot of battery power and bandwidth. This protocol adapts quickly for highly mobile hosts. This protocol also does not assume that the links are bidirectional as in other Proactive protocols thus sometime improving performance substantaially. It suggest a number of optimizations to route discovery and route maintenance which further improves efficiency. The major weaknesses in this protocol is that it fails to recognize the overhead in flooding of route discovery packets. The no of retransmissions and bandwith loss may be substantial in case of network with highly mobile nodes. These may offset the advantages gained with resepect to proactive protocols. The other weakness lack of empirical data for scalability, the authors provide simulation of a network with 24 nodes, it does not talk about very network with thousands of nodes. Some future work could be directed towards optimizing the protocol for highly dynamic networks where nodes are constantly in motion. From smw17@cornell.edu Tue Sep 10 09:59:28 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 g8ADxSh15947 for ; Tue, 10 Sep 2002 09:59:28 -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 JAA19857 for ; Tue, 10 Sep 2002 09:59:27 -0400 (EDT) Message-ID: <3D7DFA20.1070707@cornell.edu> Date: Tue, 10 Sep 2002 09:56:48 -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 5 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:23 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 g8AE7Mh17542 for ; Tue, 10 Sep 2002 10:07:22 -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 KAA27177 for ; Tue, 10 Sep 2002 10:07:22 -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:22 -0400 Message-ID: <1031666842.3d7dfc9a1d4bd@login.cs.duke.edu> Date: Tue, 10 Sep 2002 10:07:22 -0400 From: walsh@cs.duke.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 5 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 Dynamic Source Routing in Ad Hoc Wireless Networks As an alternative to more traditional distance-vector approaches, the authors propose a reactive source routing protocol for ad-hoc networks. All data packets carry the full source route, which is discovered and cached dynamically. During use, routes are maintained by tracking errors, drops, etc. Optimizations include organizing the route cache as a tree, answering route discovery requests from neighbor caches, data piggybacking, and shortening of routes (not implemented). The simplicity of the approach is a nice feature. However, finding the shortest route appears to depend entirely on the specific timing of route discovery requests, in that the route traveled by the first packet to reach the destination will be used. This seems unnatural in lossy wireless networks. The main problem, however, is that the evaluation results are not convincing or even believable. The simulation was apparently custom built (why no reuse?), did not model contention or congestion (key features of wireless networks), and used only a 5% normal-distributed loss rate. The motion pattern is absurd (1 hour pause-times in some cases), and the resulting data suspiciously close to optimum. From nbs24@cornell.edu Tue Sep 10 10:48:52 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 g8AEmqh28239 for ; Tue, 10 Sep 2002 10:48:52 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id KAA17390; Tue, 10 Sep 2002 10:48:48 -0400 (EDT) Date: Tue, 10 Sep 2002 10:48:48 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209101448.KAA17390@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 5 Paper presents a new routing protocol, dynamic source routing, for ad-hoc wireless networks. The paper describes the algorithm which improves on distance vector routing by leveraging existing Internet routing algorithms and modifying them for the wireless environment. The routes are created on-demand, and thus eliminate the need for periodic broadcasts of route advertisements, thereby reducing the network bandwidth overhead and conserving battery power at each node. This is accomplished through broadcast route discovery and maintenance schemes that take advantage of caching of learned routes at each node. To prevent collision of simultaneous transmission of route replies, each node delays it's reply from it's cache slightly while allowing all nodes to promiscuosly receive replies. A hop limit is also imposed to reduce the propagation of redundant copies of the same route requests. To address the problem of unreachable nodes, an exponential backoff limits the rate of new route discoveries. Other techniques presented are piggybacking error and reply packets on route discoveries to reduce delays and packets transmitted Their simulations only covered 24 nodes but they didn't mention that scalability could be an issue; as the network grows the control packets and message packets also grow and the storage requirements would grow. In Figure 5, their findings show that as the movement rate slowed down (beyond a pause time of 1000), the smallest network had worst relative performance. This is counter-intuitive to me and an explanation would have helped. To build on the research, they could expand their simulation environment and evaluate it's scalability. Since they do not model channel contention in their simulator, they could include that and evaluate the network's performance. Nana B. Sam From ashieh@CS.Cornell.EDU Tue Sep 10 11:26:00 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 g8AFQ0h06530 for ; Tue, 10 Sep 2002 11:26:00 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8AFPxM00419 for ; Tue, 10 Sep 2002 11:26:00 -0400 (EDT) Date: Tue, 10 Sep 2002 11:25:59 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ** Contributions This paper presents a reactive routing algorithm that encodes the routing path in each packet header. Each destination requires O(diameter) state at a communications endpoint. In steady-state, intermediate nodes need not store routing information since all necessary information is encapsulated in the header. Routing information is cached in intermediate nodes to quickly return route suffixes, thus exploiting locality to reduce routing overhead. Since the protocol is reactive, routing information is not typically exchanged between idle nodes and nodes not involved in pairwise communications, unless triggered by a route discovery broadcast. (In a proactive algorithm, O(n^2) bandwidth is periodically consumed to freshen routing updates). ** Issues A significant problem with DSR is its bandwidth usage. The initial routing request consumes w(n) bandwidth, since the routing packets get progressively bigger. One can imagine degenerate network topologies where the bandwidth consumption is O(n^2) (lollipop with n/2 nodes in the stick and n/2 nodes in the clique, with the end of the stick initiating a route discovery). Although route caching is called an "optimization" in the paper, it seems to be essential to acceptable performance in certain usage levels. Without caching in intermediate nodes (as described above), DSR could consume incredible amounts of bandwidth for route discovery. However, with routing information cached in interior nodes, DSR becomes like AODV, except with no explicit mechanism for determining route staleness other than the cache replacement/retirement policies, and the extra overhead per data packet. The evaluation was not particularly useful. The experiment provides few clues as to how well DSR scales (testing only run up to 24 nodes). Neither the latency (major penalty with reactive scheme) nor the control overhead were characterized; this would require actual workload benchmarks that they did not develop. ** Extensions - Quantifying the diameter (along with other graph & statistical properties) in a set of real networks would be useful in evaluating the extra routing overhead - The authors did not make a good point for the statelessness that DSR allows. Is this useful? (e.g. can you win in the interior nodes by having simplified processing and smaller route caches? since the radio is probably one of the most energy-consuming items, probably not) From yao@CS.Cornell.EDU Tue Sep 10 11:34:26 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 g8AFYQh08605 for ; Tue, 10 Sep 2002 11:34:26 -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 5 Date: Tue, 10 Sep 2002 11:34:25 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C1F@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 5 Thread-Index: AcJY34terFhIZ0FOQeekiF9ZPzcHcg== 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 g8AFYQh08605 The Johnson and Maltz paper present the intuition and implementation details of a reactive routing protocol, DSR. In contrast to PRNET and DSDV, DSR is a reactive routing protocol, which discovers and maintains routes only in use. For most applications over ad hoc networks, this is a big improvement in terms of bandwith and energy consumption. DSR is also a source routing protocol. The source will specify the whole route to the destination for an outgoing packet. One advantage of source routing is that links between nodes can be asymmetric, although extra modifications to the protocol are required. The paper also discusses many optimiztion and potential improvement of the DSR. However, the paper has an incomplete evaluation section. First, all experiments were tested on a packet-level simulator, which does not take MAC layer issues into accout. Second, both the network size and the network workload are small. More experiments on the scalability of the system would make the paper stronger. Finally, it is better to compare DSR against previous proposed routing protocol, like DSDV, in terms of bandwith and delay. DSR itself has some problems. One of them is the false reply. It is possible that a node with some stale routes cached could reply a route request, and propagate such stale routes further. It could be a serious problem in a large size network. The DSR does not support local repair either, which is proved to be very efficient in some applications. Yong From ks238@cornell.edu Tue Sep 10 11:50:37 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 g8AFobh12792 for ; Tue, 10 Sep 2002 11:50:37 -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 LAA24282 for ; Tue, 10 Sep 2002 11:50:36 -0400 (EDT) Message-Id: <5.1.0.14.2.20020910114951.01b34ec0@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:50:33 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #5 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In their paper on Dynamic Source Routing Protocols in ad hoc networks, Johnson and Maltz describe a new memory efficient protocol, which employs the caching of routes. They start by addressing the problems with the distance vector and link state routing algorithms. First, the issue of memory efficiency comes to play in distance vector and link state routing due to the periodic broadcasts that are part of both algorithms. On the other hand, Dynamic Source Routing eliminates the need for having periodic broadcasts, many of which go unnoticed and thereby are wasting precious bandwidth space, by dynamically discovering routes when needed, and caching them in memory for certain periods of time in case they are needed again. Conservation becomes especially apparent in the case of networks with little to no movement. In addition, Source Routing prevents the need to maintain redundant paths within the same network. A final advantage is that Source Routing allows for a network to quickly adapt itself without excessive amounts of down time, unlike the case for distant vector and link state protocols. Two key facets of the Dynamic Source Routing protocols are there Route Discovery and Route Maintenance mechanisms. Route Discovery uses a basic algorithm by which a route request packet deciphers the shortest path to the target node, and a route reply packet which confirms the discovery. With Route Maintenance hop-by-hop acknowledgments, end-to-end acknowledgements, and passive acknowledgments are used in order to detect route failures or retransmission errors in the network. The protocols unique quality comes with route caching which as described earlier has substantial benefits in decreasing the amount of CPU usage in the route discovery process. Route caching allows for shorter routes to be quickly updated from previous routes without the need for engaging in another route discovery process. The simulation at the end of the paper is definitely incomplete. The issue of scalability is never tested because they decide to limit the test to only 24 nodes. I find this to be a serious weakness because this was suppose to be one of the benefits of this protocol. Thus their simulation's evidence can't be relied on too heavily when looking for larger applications. From aed13@cornell.edu Tue Sep 10 11:56:33 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 g8AFuXh14358 for ; Tue, 10 Sep 2002 11:56:33 -0400 (EDT) Received: from andyd-laptop.cornell.edu (syr-66-67-66-109.twcny.rr.com [66.67.66.109]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA11757 for ; Tue, 10 Sep 2002 11:56:30 -0400 (EDT) Message-Id: <5.1.0.14.2.20020910111954.02112588@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 10 Sep 2002 11:56:29 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 PAPER5 and PAPER6 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "Dynamic Source Routing in Ad Hoc Wireless Networks" presents a conceptually different method of routing with improvements in network overhead and battery life compared to distance vector and link state protocols read to date. The protocol utilizes source routing by which the send specifies the complete of traversal through the network. The paper separates network maintenance into distinct concepts of route discovery and route maintenance, which are usually combined in the maintenance broadcast messages of the earlier protocols. The paper is well organized in presenting the conceptual design of the protocols. It includes concrete simulation methodology and results unlike earlier papers. It optimizations and architecture mix routing and MAC level issues, specifically the use of NIC in permiscuous mode to provide more information to the routing layer. The paper discusses significant optimizations to the route cache including, router's ability to add a learned route that traversed it, or it heard promiscuously, to limit the number of hops of a discovery, and a delay procedure for responding with in-cache answer routes that guarantees only the router with the shortest path replies. Ounce again the author mixes MAC and routing level issues in this optimization. Overall the paper was well structured and provided a scientific evaluation of their methodology, assumptions and results. The paper "Ad=hoc On-Demand Distance Vector Routing" modifies the distance vector algorithm to lower network overhead, by only maintaining and creating routing information as need(on-demand) avoiding the high overhead of global level broadcasts found in most Distance vector algorithms. This paper introduces the concept of separating network topology management between groups of nodes and the management of information within a group of local neighbors. Their methodology works to reduce information dissemination to only the nodes who need to know the local information has changed. The protocol combines techniques from DSR and DSDV to assemble the routing information at intermediary nodes and to maintain monotonically increasing sequence numbers, respectively. It uses a route discovery methodology almost identical to "Dynamic Source Routing in Ad Hoc Wireless Networks", and mainly differs in the distribution of routing information within the network. The simulations include an analysis of the cost of "Hello" setup messages and the overall performance, but does not provide comparisons to other protocols in the same environment. --Andrew Davis From mtp22@cornell.edu Tue Sep 10 11:57:50 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 g8AFvoh15327 for ; Tue, 10 Sep 2002 11:57:50 -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 LAA23233 for ; Tue, 10 Sep 2002 11:57:47 -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 5 Date: Tue, 10 Sep 2002 11:58:57 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02091011585700.00149@narnia> Content-Transfer-Encoding: 8bit The major contribution of this paper is the first reactive routing protocol for ad hoc networks, DSR. Such a protocol is important because mobile hosts, unlike traditional routers, have to seriously consider power consumption. DSR reduces power consumption by avoiding periodic route broadcasts. A weakness of this paper is that it does not describe any mechanism for authoritative route requests. That is, it does not describe a way for a node to ask that a route request not be satisfied by a cached entry. Without such a mechanism, I believe there is a way--in a network whose topology includes some unidirectional links--for a node to be permanently disconnected from another node in the network even though a route does exist. This could happen if the node initiating the communication is "stuck" behind a neighboring node that always returns a stale cache entry. This could be fixed by propogating route error messages along the original path, but this is described as an optimization and not a requirement of the protocol. Another weakness of this paper is that it doesn't attempt to simulate a worst-case scenario; all of the simulations are done using random positions and movement, which often don't reflect the worst-case scenarios. The work in this paper could be expanded upon by simulating the protocol using different MAC protocols, e.g. ones that allow unidirectional links. Further simulations could also be run where actual packet collisions are simulated. From liuhz@CS.Cornell.EDU Wed Sep 11 20:24:34 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8C0OYh00039 for ; Wed, 11 Sep 2002 20:24:34 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 5 Date: Wed, 11 Sep 2002 20:24:33 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5DF@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 5 Thread-Index: AcJZ8sRtteF4iCv+SVaWr7MRSsx4kw== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8C0OYh00039 This paper presents an on-demand routing protocol that uses dynamic source routing. The protocol adapts quickly to routing changes when host movement is frequent, yet requires little or no overhead during periods in which hosts move less frequently. Unlike conventional distance vector or link state routing algorithms, this protocol uses no periodic advertisement messages, thereby reducing network bandwidth overhead and conerving battery power on the mobile hosts, particularly during periods when network topology doesn't change significantly. Another thing that makes it outstanding is that it doesn't require bidirectinal links, although it works better when afforded. The simulation results show this protocol performs very well in a small size network(less than 24). The basic algorithm goes as follows: A route discovery packet is broadcast when a host want to send packets to some destination that it has no route in its caches. This dicovery packet is propagated until it reaches some host that has already known a route to the destination. Then the route reply packet is sent back to the original source along the reverse path if bidirectional transmission is provided, otherwise a route discovery packet is sent to find a route to the source. This paper also introduce some optimizations to this algorithm, like nonpropagating route request, piggybacking route discoveries and so on, which improve the performance of this protocol greatly. Despite of these, the size of the route discovery and reply packets is O(n), where n is the number of the hosts in the network, which makes it impossible to scale this protocol to some network with a large population. In case of partioned networks,this protocol behaves sillily, despite of the back off mechanism, continuing to make periodic efforts to find a route to the unreachable host and consuming some network resources. At last, this paper does not address the security concerns inherent in wireless networks, as stated by the authors themselves. From egs@CS.Cornell.EDU Thu Sep 12 12:14:01 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 g8CGE0h24346 for ; Thu, 12 Sep 2002 12:14:00 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id g8CGE0N10079 for egs; Thu, 12 Sep 2002 12:14:00 -0400 (EDT) Date: Thu, 12 Sep 2002 12:14:00 -0400 (EDT) Message-Id: <200209121614.g8CGE0N10079@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 5 >From linga@CS.Cornell.EDU Thu Sep 12 11:59:18 2002 >Date: Thu, 12 Sep 2002 11:59:18 -0400 (EDT) >From: Prakash Linga >To: Emin Gun Sirer >Subject: 614 PAPER 5 > > > >Broadcast Storm Problem in MANET > >The usual way of broadcasting by flooding is expensive and results in serious redundancy, contention and collision issues (Broadcast Storm Problem). This paper analyses the seriouness of broadcast storm problem and proposes simply schemes to tackle this problem. > >Flooding is a problem because of three main reasons: many broadcasts could be redundant, heavy contention could exist (as rebroadcasting hosts are normally close to each other) and collisions are more likely to occur as RTS/CTS dialogue is inapplicable, there is no collision detection and timing of rebroadcasts is highly correlated. >Analysis on redundant broadcasts shows that: the benefit of a host rebroadcasting a message after it has heard the message k times is very low for higher k (k>=4, the expected additional coverage is below 0.05%). >Analysis on Contention shows that: the probability that all n hosts experience contention quickly crosses 0.8 for n>=6. >Several mechanisms have been proposed to reduce redundancy, contention and collision (All schemes except that last operate in a fully distributed manner. Contention and collision could be reduced by inserting a small random delay before rebroadcasting the message.): >Probability scheme: On receiving a broadcast message for the first time a host will rebroadcast it with probability p. >Counter-Based scheme: A counter c is used to keep track of the number of times a given broadcast message is received. When c>=C (where C is a counter threshold) the rebroadcast is inhibited. >Distance-Based scheme: Relative distance between the hosts is used to decide whether a rebroadcast has to be done or not. >Location-Based scheme: Given the locations of the broadcasting hosts, additional coverage can be estimated more precisely and comparing this with a coverage threshold we can determine whether the rebroadcast should be performed or not. >Cluster-Based scheme: MANET is divided into cluster where each cluster has a head. If the receiving host is a non-gateway member, rebroadcast is inhibited. Otherwise (if he is a head or a gateway) use any of the previous schemes to decide if rebroadcast has to be done or not. >Performance metrics: Reachability(RE), Saved ReBroadcasts(SRB) and average latency. For different schemes: threshold vs RE, threshold vs SRB and threshold vs avg. latency was plotted to understand the performance of these schemes. Location-based scheme is the best of all. It provides high levels of reachability with a good amount of saving rebroadcasts. > >Pros: >This paper provides insights into the Broadcast storm problem. Explains why this is a problem, shows through analysis how serious this problem could get and then suggests simple schemes to overcome this problem effectively. They present simulation results showing the efficacy of their approach compared to naive flooding. > >Cons: >Only simple schemes have been investigates. We could imagine hybrid schemes like: On receiving the message for k time, inhibit rebroadcast with a probability proportional to k. >Incorporating this into other MANET protocols like reliable broadcasts etc has not been investigated. >Applicability and usefulness of these schemes in a large MANET with high mobility has not been tested. > > From vivi@CS.Cornell.EDU Fri Sep 13 15:36:35 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 g8DJaZh02929 for ; Fri, 13 Sep 2002 15:36:35 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper5 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Fri, 13 Sep 2002 15:36:34 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF66@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper5 Thread-Index: AcJbXN6spwLD9OGqSzGv3w9i/tr7Kw== 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 g8DJaZh02929 Dynamic Source Routing: The main contribution of this protocol is the accomplishment of routing without periodic route updates, thus saving bandwidth and power. As pointed out in the paper, this feature of the protocol also prevents wastage of bandwidth when there is no host movement taking place in the network. The basic problem with this protocol is that there is no guarantee that any route that is formed is the optimal route. This is due to the fact that during route discovery, the route request packet might not be heard by nodes which are part of the shortest path from the source to the intended destination, (as the route request packet is a broadcast packet). Also, even if the route initially achieved is the optimal route, progressive movement of the nodes that are part of this route could mean that routing is continued to be implemented through the same nodes, even if they no longer form the shortest path. If the route discovery mechanism fails, DSR implements the Exponential Backoff Scheme to space the following route request packets to the destination. If the first few route request packets fail to reach the destination due to some reason (they are broadcast pkts), then DSR wrongly assumes that there is no route possible, and this leads to huge delays. Also, the paper does not specify what the application does in such a scenario. (How long the application has to wait before it realizes that a route cannot be realized is not specified). The paper does not explain the logic behind choosing the various parameters used in the simulations. The largest number of nodes used in the simulation is 24, which is not at all large in the real world. Also, route caches would grow untenably large in networks made of a large number of nodes, and so do the overheads because of the source routes. So whether the protocol is scalable is a doubtable issue. The simulations have not studied the number of packets that actually reach the destination, and the number of transactions had to be dropped. The delay associated with the packets has not been recorded as well.