From eyh5@cornell.edu Mon Sep 3 16:35:10 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 f83KZAq02233 for ; Mon, 3 Sep 2001 16:35:10 -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 QAA12254 for ; Mon, 3 Sep 2001 16:35:08 -0400 (EDT) From: eyh5@cornell.edu Date: Mon, 3 Sep 2001 16:35:08 -0400 (EDT) X-Sender: eyh5@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 2 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper introduces a type of routing algorithm, Dynamic Source Routing (DSR), that is specifically applied to an ad hoc wireless network. In contrast to the routing method proposed in the paper on the DARPA PRNET, DSR employs a mechanism that performs a reactive route query to transmit packets from one mobile host of the network to another. This approach eliminates the periodic update of each node's broadcast advertisement prior to data transmissions, thus greatly reducing overhead that would take up scarce bandwidth. One approach to optimize the performance of the DSR is to take full advantage of the route cache that's associated to every mobile node in the ad hoc network. It is evident from the paper that the route cache plays a very important role in establishing a packet-delivery route. One concern is out of the proper format of the route cache. It seems that the cache is frequently updated to reflect the changing status of the network. Therefore, being able to expediently access the route entries in the cache is key to minimizing the delay due to CPU processing the information from the cache to compute, say, the next hop in the route. One way to do this is when an entry needs to be updated, it is preferable not to overwrite the whole entry, but instead update only a certain field of it. This selective update of a cache entry may reduce the CPU processing overhead in the mobile node. In taking advantage of the route cache, an incident may occur where multiple replies to a route request packet arrive to the inquiring node, each presenting a different route to reach the destination. In a situation like this, the authors of the paper propose the introduction of a delay period, computed based on the numbers of hops in the respective potential routes. In this proposal, the authors are very particular about choosing a route that requires the minimum number of hops leading to the destination. However, I think in some circumstances, such as when there is a large number of data packets in the buffer waiting to be transmitted, and when the number of hops in the first received route reply is below a preset threshold number of hops, then the node should initiate the data packet transmission immediately without waiting for subsequent route replies and making all the computations to select the best among them. The chosen route may not be the "optimal," but by doing so, the data packets may be delivered with minimal delay in the buffer, and the additional bandwidth incurred may be a tolerable trade-off and is not significant enough to outweigh the benefit of the time saved. This procedure may be more applicable when the topology of the ad hoc network is varying at a rather high rate and there is a high frequency of route request packets traversing in the network. Another concern with this routing protocol is the knowledge of the complete route in every header of the data packet to be transmitted. If the route requires a fairly large number of intermediate hops, and if there is a high volume of packets to be transmitted, this added overhead information per packet may exhaust the available bandwidth and cause congestion along the route. It may outstrip the BW saving gains acquired in reactive route discovery, and a worse consequence is the loss of transmitted data. Some new approach may be required to address this issue. The authors of the paper have produced simulation results to validate the proposed dynamic source routing algorithm in the ad hoc wireless environment. However, the model chosen (a collection of mobile hosts moving around in a medium-sized room) may be too conservative to have merits in human-initiated interactions (e.g., voice communications). Such a model is fit for, say, a mobile version of bluetooth technology, where some devices with embedded bluetooth chips (I haven't figured out what they might be) move about in a household. To emulate a more realistic ad hoc wireless scenario such as a disaster area, the simulation parameters should be defined to reflect the nature of a fairly large coverage area. From wbell@CS.Cornell.EDU Mon Sep 3 23:04:04 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 f84343q07339; Mon, 3 Sep 2001 23:04:03 -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 XAA26417; Mon, 3 Sep 2001 23:04:02 -0400 (EDT) Subject: 615 PAPER #2 From: Walter Bell To: egs@CS.Cornell.EDU Cc: wbell@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.12.99+cvs.2001.08.21.23.41 (Preview Release) Date: 03 Sep 2001 23:03:40 -0400 Message-Id: <999572645.2221.3.camel@brute> Mime-Version: 1.0 2) Dynamic Source Routing in Ad Hoc Wireless Networks This paper takes a different view of routing from the distance vector routing approaches, and instead presents a dynamic source routing mechanism, where no network resources are used in maintaining routing information unless a node is actively participating in communication with another node [either via forwarding, or source communication.] It builds on the existing wired network routing schemes such as ARP which put a large connection cost on creating a connection between two sources, but zero network resources determining routes for proactively determining connections. This allows the protocol to use slightly over optimal amounts of network resources for communication, as no routes are determined unless they are part of a communication channel. They spend a large amount of the paper describing many of the optimizations and tweaks that can be done in order to build more complete routing tables without adding additional network resources, as well as additions to allow neighbor hosts to reflect known routes without using a full route discovery. Other optimizations include evesdropping on discovered routes as well as piggybacking data on top of discovery packets for replies. They complete the discussion with the results of a built simulator that has simple models of movement and communication, in which their protocol achieved an almost optimal use of network resources. This paper borrows and expands on the idea of source routing from the wired internet, which has proven itself to be an incredibly scalable routing technique. This presents good promise as to the scalability and resource economy of this routing protocol if put into real use. They go into good detail to describe the optimizations that make this protocol efficient, which likely would lead to a good and well thought out implementation. The simulator results are somewhat incomplete and rushed, and the results are a bit too ideal to be believed as an accurate model. A more thorough understanding and discussion on the scenarios in which this protocol is inefficient would have been useful, such as more detail into resources used for contacting unreachable hosts. From viran@csl.cornell.edu Tue Sep 4 00:43:31 2001 Return-Path: Received: from cray.csl.cornell.edu (cray.csl.cornell.edu [132.236.71.70]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f844hVq16847 for ; Tue, 4 Sep 2001 00:43:31 -0400 (EDT) Received: from localhost (viran@localhost) by cray.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id AAA73338 for ; Tue, 4 Sep 2001 00:43:27 -0400 (EDT) (envelope-from viran@cray.csl.cornell.edu) X-Authentication-Warning: cray.csl.cornell.edu: viran owned process doing -bs Date: Tue, 4 Sep 2001 00:43:27 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 2 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dynamic Source Routing in Ad Hoc Wireless Networks This paper describes a source-driven routing protocol for ad-hoc networks, where a node does not pro-actively determine a route, but only looks for routes when a packet needs to be transmitted. This method relies on caching routes across the network; if a destination is requested that does not exist in the current node's cache, a route discovery packet is dispatched to determine the correct route. The reply packet with the discovered route is then piggybacked onto a new route request going back to the originator, thus allowing different forward and backward routes. Such a network discovery protocol appears to be very efficient in terms of energy and bandwidth utilization compared to a table-driven routing protocol such as that used in the PRNet. Several optimizations were presented in this paper to further reduce network maintenance overhead, including early discovery of a route at an intermediate node, hop-limits on packets, data piggybacking on the discovery packet, and exponential backoff of route discovery request retries. Most of these optimizations however rely on the nodes operating in promiscuous mode. This paper is a very clear and high-level look at an alternative to table-driven routing, and does an admirable job of presenting the theory. Most of my criticisms of this paper are leveled at the simulation results discussed at the end. The model is rather simplistic, and only looks at a relatively small number of hosts, which is unfortunate because nothing concrete about the scalability of the protocol can be stated. It's also hard to say if the network will perform efficiently if a large number of nodes are all within range of another (a dense network with width close to 1). Another difficulty is gleaning just how robust the protocol will be in the presence of unreliable links, since the model used a very low probability of link failure (5%). From teifel@csl.cornell.edu Tue Sep 4 08:37:38 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 f84Cbcq29974 for ; Tue, 4 Sep 2001 08:37:38 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f84CbYw44032 for ; Tue, 4 Sep 2001 08:37:34 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 4 Sep 2001 08:37:34 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 2 Message-ID: <20010904082655.M81767-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII DSRiAHWN: This paper applies a dynamic source routing protocol for use in ad hoc networks. Source routing is when the sender explicitly specifies the complete path for which a packet is to travel along a network. Dynamic source routing is when the packet route can be dynamically determined based on cached information or when the sender can change a given path to a destination based on a change in the network composition. Johnson & Maltz's protocol is different from prior wireless ad hoc protocols because they use no periodic routing advertisement messages to update node directory information(saving bandwidth). Their protocol is optimized for average-case performance as their protocol only incurs overhead when rapid host movement occurs. The main mechanisms required for dynamic source routing are a route cache, route discovery actions, and route maintenance actions. This paper presented several interesting optimizations, like piggy-backing data on route discovery packets and reflecting shorter routes on commonly communicating nodes. The authors identified several places where promiscuous receive mode may be beneficial in implementing services for ad hoc networks. The paper's simulator and simulation results were acceptable. I found the 1% overhead of the protocol and the 1.02% route lengths to be impressive, but they did not give anything to compare against. Again as in the first paper, it is difficult to determine how well this routing & protocol scheme works, without a comparison with the prior state routing algorithms. From gupta@CS.Cornell.EDU Tue Sep 4 10:23:29 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 f84ENTq11734 for ; Tue, 4 Sep 2001 10:23:29 -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 2 Date: Tue, 4 Sep 2001 10:23:30 -0400 Message-ID: <404A3A4758DDCC4C8A5C9A537384F9D6043A7C@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 2 Thread-Index: AcE1TSfYmEhHlJ2MEdW1ugCgydyP2Q== 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 f84ENTq11734 ----START---- Reviewer: Indranil Gupta Dynamic Source Routing in ad-hoc wireless networks, D.B. Johnson and D.A. Maltz. Summary: This paper describes an ad-hoc routing protocol that 1) is reactive (on-demand) in route discovery, 2) has packets carry the entire route, and 3) handles asymmetric wireless links. The authors assume that node movement speeds lesser than packet transmission latency through the network. Routes maintained at the sender expire after some time-out. The authors also present several optimizations based on the nodes using promiscuous overhearing of broadcasts from neighbors, as well as caches of routes from packets. For (re-) discovering a route to a destination, the sender floods out a route request packet through the network. Intermediate nodes add themselves onto the route in the packet before forwarding. Intermediate nodes also eliminate duplicate route requests. The destination sends a route reply packet to the sender with the route in it. The destination might have to do a route discovery to the sender, whence it piggybacks the route reply on the new route request packet. Several optimizations, such as an expanding ring search from the sender, and the use of route caches at intermediary nodes to return a quicker route reply are presented. For maintaining routes, all nodes actively or passively probe the health of its neighbors (or links to them), sending a route error packet to the route origin (sender of a route that passes through this node) if the next link breaks down - the sender initiates another route discovery to the destination. Probing the health of links to neighbors can be done via link level acks if the link is symmetric. For asymmetric links, the neighbor may need to do a route discovery to this node. The authors also talk of eliminating all acks along all intermediate link and using only end to end acks (origin -> destination -> origin). To prevent flood of route request packets when network is partitioned, repeated route request packets are sent at exponentially backed-off intervals. The authors use a custom simulator to measure the protocol performance. They use a variable pause time to model moving hosts. The mobility is modeled via the random way-point model. All nodes have same transmission range. For high mobility scenarios, the total load on the network is 2.6 times the messages injection rate and routes are 8 % longer than optimal routes. At moderate to low mobilities, these numbers fall to 1.1 and 1 %. Comments: - The authors say that one of the motivations for reactive protocols is that they use less bandwidth battery time than proactive protocols when there is a low message injection rate into the network or no routes are passing through a part of the network. However, variants of proactive protocols that adjust the rate of the periodic messages to current traffic, mobility etc., might do as well as the reactive protocols. Has this adaptivity been explored in the work on proactive protocols ? - The authors seem to place emphasis on being able to handle asymmetric links. Using asymmetric links for useful message transmission seems to complicate protocols (acks on links need route discovery, having only end to end acks can cause higher load per packet, etc.), while possibly shortening paths and decreasing load on nodes. However, the exact nature of this tradeoff is not investigated in the paper - using only symmetric links for useful message transmission and treating asymmetric links as interfering noise might be an easier solution. Have these two alternatives been compared in any work ? (The authors of this paper do not model asymmetric links in their simulations.) - Why is it better to have the path in the packet than along the intermediary nodes, while keeping the protocol reactive ? The authors don't explain or evaluate this. - As an alternative to having the sender (route origin) rediscover a new route every time a single link on the old route breaks down, the last 'good' (intermediary) node on the old path could itself initiate a route request to the destination and concatenate it with the original part of the old route. If this operation is carried out only some constant number of times (after which the route origin initiates a discovery), the resulting path cannot be too much longer than the shortest path most of the time. - In the simulation, the authors don't say what percentage of packets were delivered. The simulation is also weak as they don't vary several parameters, such as the message injection rate. Many other tradeoffs such as the overhead of large networks (and larger routes in the packets) are not explored. ----END---- From avneesh@csl.cornell.edu Tue Sep 4 10:50:58 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 f84Eowq14385 for ; Tue, 4 Sep 2001 10:50:58 -0400 (EDT) Subject: 615 PAPER #2 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Tue, 4 Sep 2001 10:54:58 -0400 Message-ID: <97C142C1212ED545B0023A177F5349C4053A4B@capricorn.ds.csl.cornell.edu> Content-Class: urn:content-classes:message X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER #2 Thread-Index: AcE1UZDrSTvf+mHrQeipqQSZZKri5w== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f84Eowq14385 Dynamic source routing in Ad Hoc Wireless Networks Paper Summary: The paper defines the basic properties and the need for adhoc networks and highlights the disadvantage of using conventional routing protocols in this domain. The excess traffic due to periodic routing advertisments in distance vector and link state protocols is a deterrant to the already sensitive efficiency of the adhoc network protocol. The Dynamic source routing protocol thus defined, attempts to reduce this kind of traffic and provides an optimized route discovery protocol(summarized later).This protocol also alleviates some typical problems such as lack of bidirectional performance similarity, non usable routes and delays in convergence towards stable routes as experienced by the conventional protocols. The paper also defines the diameter of the network and the promiscous receive mode of operation. The basic operation of the protocol consists of the following: a. Route Discovery: This is said to be done when a route request packet is sent to a destination, which in turn generates a route reply packet (consisting of the sequence of hops) for the sender. Each node in the hop appends its address to generate this record.Several optimization techniques (to reduce this traffic) such as looking up a routing record for similar/destination entries, detecting circular routing and piggy backing of the reply packet on the route request packet by the destination to the source are done. b. Route maintenance: Instead of periodic updates to mantain route integrity,hop by hop acknowledgements in the data link layer and proposed to provide early detection of errors. Route error packets are sent to the originator, if there is an error. Operation in promiscous mode enables passive acknowledgement i.e the sender can capture a neighbors packet transmission acknowledgement to a further node, thus confirming its passage to that further node. Several other optimizations have been discussed within this domain. One most emphasized is the use of the route cache to reduce propagation of route request packets if an intermediate node already has the rest of the route in its cache. With the help of suitable delay periods, non optimal replies in the above situation are reduced. By setting hop limits redundant route request copies are avoided. When using the route cache, special care needs to be taken to prevent the piggybacked data from becoming invalid. This is done by contrsucting a new packet and appending correct originator information. Promiscous receive mode also enables shorter routes, created due to node movement, to be easily detected. c. Partitioned networks: Finally, partitioned networks require new route requests to be sent. In order to reduce excess packets/overhead, exponential backoff coupled with promiscous recieve mode is used. Simulation results show performance of this protocol. The results are summarized by showing the number of tranmits/optimal number of transmits which increases when the pause time( non movement time) of the nodes becomes really small (< about 150 seconds). This is quite expected. The second evaluation is that of the optimal path versus the computed path which also shows simailar behaviour to the previous graph. Thus it can be concluded that both issues are viably affected by rapidly moving nodes and hence increased route discovery traffic. Critique: The paper is very well presented and the concepts have been well elucidated. Dependance on previous work and reason for current work has been shown. Related work is adequately referenced, though I have not been able to read up all references. Some points however bear concern. The first is that the compute path/optimal path ratio has non uniform behaviour for high pause time for different nodes, some values e.g those for 6 nodes are higher than those for 12 which is less than that for 18. It has not been explained why. Secondly some concepts were not simulated. The reason for one of them was explained but the rest have not.This might be due to fairly reasonable constraints, but those have not been presented. Finally though it is intuitive, it would have been nice to see a comparison of this protocol with any one conventional protocol. From daehyun@csl.cornell.edu Tue Sep 4 10:58:59 2001 Return-Path: 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.7) with ESMTP id f84Ewxq15318 for ; Tue, 4 Sep 2001 10:58:59 -0400 (EDT) Received: from atlas (syr-66-24-28-91.twcny.rr.com [66.24.28.91]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id KAA03408 for ; Tue, 4 Sep 2001 10:58:59 -0400 (EDT) Message-ID: <001501c13551$d632ef90$5b1c1842@atlas> From: "Daehyun Kim" To: Subject: 615 PAPER (2) Date: Tue, 4 Sep 2001 10:56:52 -0400 MIME-Version: 1.0 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-Type: multipart/alternative; boundary="----=_NextPart_000_0012_01C13530.4E01FCE0" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 This is a multi-part message in MIME format. ------=_NextPart_000_0012_01C13530.4E01FCE0 Content-Type: text/plain; charset="ks_c_5601-1987" Content-Transfer-Encoding: base64 VGhpcyBwYXBlciBpbnRyb2R1Y2VzIGEgcm91dGluZyBhbGdvcml0aG0gaW4gYWQtaG9jIHdpcmVs ZXNzIG5ldHdvcmtzLg0KU2VjdGlvbiAxIGFuZCAyIGV4cGxhaW4gdGhlIGdlbmVyYWwgYmFja2dy b3VuZCBhbmQgdGhlIG5ldyBhcHByb2FjaCBpbiB0aGlzDQpwYXBlciBicmllZmx5LiBDb21wYXJp c29uIGJldHdlZW4gdGhlbSBpcyBhbHNvIGdpdmVuLiBTZWN0aW9uIDMgYW5kIDQNCmRlc2NyaWJl IHRoZSByb3V0aW5nIGFsZ29yaXRobS4gU2VjdGlvbiA1IHNob3dzIHRoZSBzaW11bGF0aW9uIHJl c3VsdHMuDQpTZWN0aW9uIDYgZ2l2ZXMgdGhlIHJlbGF0ZWQgd29yay4gU2VjdGlvbiA3IGNvbmNs dWRlcy4NCg0KVGhlIHByb3Bvc2VkIGFsZ29yaXRobSBpcyBjYWxsZWQgJ0R5bmFtaWMgU291cmNl IFJvdXRpbmcnLiBJdCBpcyBiYXNlZCBvbg0Kc291cmNlIHJvdXRpbmcsIGluIHdoaWNoIHRoZSBz ZW5kZXIgY29uc3RydWN0cyB0aGUgZW50aXJlIHJvdXRlIHRvIGJlDQpmb3J3YXJkZWQgaW50byB0 aGUgcGFja2V0J3MgaGVhZGVyLiBFYWNoIGhvc3QgbWFpbnRhaW5zIGEgcm91dGluZyB0YWJsZQ0K LSBjYWxsZWQgJ1JvdXRlIENhY2hlJyB3aGljaCBpcyB1cGRhdGVkIGR5bmFtaWNhbGx5IG9uLWRl bWFuZC4NCg0KVGhlcmUgYXJlIHR3byBpbXBvcnRhbnQgcHJvdG9jb2xzLg0KDQoxLiBSb3V0ZSBE aXNjb3ZlcnkgOiBUaGlzIHByb3RvY29sIGlzIHVzZWQgdG8gZmluZCBvdXQgYSByb3V0ZSwgd2hl biBpdCBpcw0KICAgICAgICAgICAgICAgICAgICAgbm90IGluIHRoZSBSb3V0ZSBDYWNoZSBhbHJl YWR5Lg0KMi4gUm91dGUgTWFpbnRlbmFuY2UgOiB0aGlzIHByb3RvY29sIGlzIHVzZWQgdG8gbWFu YWdlIHRoZSByb3V0ZXMgaW4gdGhlDQogICAgICAgICAgICAgICAgICAgICAgIFJvdXRlIENhY2hl LiBJZiBhIHJvdXRlIGlzIG5vdCB2YWxpZCBhbnkgbW9yZSwgaXQgaXMNCiAgICAgICAgIGRlbGV0 ZWQgZnJvbSB0aGUgUm91dGUgQ2FjaGUuDQoNClNldmVyYWwgb3B0aW1pemF0aW9uIHRlY2huaXF1 ZXMgLSBGdWxsIFVzZSBvZiB0aGUgUm91dGUgQ2FjaGUsIFBpZ2d5LWJhY2tpbmcNCm9uIFJvdXRl IERpc2NvdmVyaWVzLCBSZWZsZWN0aW5nIFNob3J0ZXIgcm91dGVzIGFuZCBJbXByb3ZlZCBIYW5k bGluZyBFcnJvcnMNCi0gYXJlIGdpdmVuLiBCYXNpY2FsbHkgdGhleSBhcmUgaW50ZW5kZWQgZm9y IHJlZHVjaW5nIHRoZSBwcm90b2NvbCBvdmVyaGVhZA0KYW5kIG1hbmFnaW5nIHRoZSBSb3V0ZSBj YWNoZSBlZmZpY2llbnRseS4NCg0KVGhlIGFsZ29yaXRobSBpbiB0aGlzIHBhcGVyIGlzIGZvY3Vz ZWQgb24gcmVkdWNpbmcgdGhlIG92ZXJoZWFkIG9mIHBlcmlvZGljDQp0YWJsZSB1cGRhdGUuIEFu ZCB0aGUgc2ltdWxhdGlvbiByZXN1bHRzIHNob3dzIHRoYXQgdGhpcyBhcHByb2FjaCBpcyBzdWNj ZXNzZnVsLg0KR2VuZXJhbGx5IEkgYWdyZWUgd2l0aCB0aGlzIGFwcHJvYWNoLiBCdXQgSSdkIGxp a2UgdG8gcG9pbnQgb3V0IHR3byB0aGluZ3MuDQoNCjEuIFRoaXMgcGFwZXIgY29tcGFyZXMgdGhl aXIgbmV3IGFsZ29yaXRobSB3aXRoIHRoZSBjb252ZW50aW9uYWwgYWxnb3JpdGhtcw0KICAgLSBE aXN0YW5jZSBWZWN0b3IgYW5kIExpbmsgU3RhdGUgUm91dGluZy4gQnV0LCBpdCBkaWQgbm90IHNo b3cgdGhlIHNpbXVsYXRpb24NCiAgIHJlc3VsdHMgZm9yIHRoZW0uIFRob3VnaCB0aGUgY29tcGFy aXNvbiB3aXRoIHRoZSBvcHRpbWFsIGNhc2UgaXMgZ2l2ZW4sIGl0IHdpbGwNCiAgIGJlIGhlbHBm dWwgZm9yIHRoZSByZWFkZXJzIGlmIGl0IHNob3dzIGhvdyB0aGUgY29udmVudGlvbmFsIGFsZ29y aXRobXMgd29yay4gSW4NCiAgIGFkZGl0aW9uLCBJdCB3aWxsIGJlIGdvb2QgdG8gc2hvdyB0aGUg c2ltdWxhdGlvbiByZXN1bHRzIGZvciBtb3JlIGhvc3RzLCB0byBrbm93DQogICB0aGUgc2NhbGFi aWxpdHkgb2YgdGhpcyBwcm90b2NvbC4gDQoNCjIuIEluIHRoaXMgYWxnb3JpdGhtLCB0aGUgc2Vu ZGVyIG5lZWRzIHRvIGtub3cgdGhlIGVudGlyZSByb3V0ZXMgYmVmb3JlIGl0IHNlbmRzDQogICBw YWNrZXRzLiBJIHRoaW5rIHRoaXMgbGltaXRzIHRoZSBzY2FsYWJpbGl0eSBvZiB0aGUgcHJvdG9j b2wuIHRoZSBwcm90b2NvbCByZXF1aXJlcw0KICAgdGhhdCB0aGUgdG9wb2xvZ3kgb2YgdGhlIG5l dHdvcmsgZG9lcyBub3QgY2hhbmdlIGR1cmluZyB0aGUgUm91dGUgRGlzY292ZXJ5LiBCdXQgYXMN CiAgIHRoZSBudW1iZXIgb2YgaG9zdHMgaW5jcmVhc2VzLCB0aGlzIHJlcXVpcmVtZW50IGlzIGhh cmQgdG8gc2F0aXNmeS4gU28gdGhpcyBhbGdvcml0aG0NCiAgIG1pZ2h0IGJlIGxpbWl0ZWQgdG8g YSBzbWFsbCBudW1iZXIgb2YgaG9zdHMgb3IgYSByZWxhdGl2ZWx5IHNsb3dseSBtb3ZpbmcgaG9z dHMuIEluIG15DQogICBvcGluaW9uLCBhIG5ldyBhcHByb2FjaCB3aGljaCB1c2VzIG9ubHkgbG9j YWwgcm91dGluZyBpbmZvcm1hdGlvbiwgbm90IGVudGlyZSByb3V0ZXMNCiAgIG1pZ2h0IGJlIGEg c29sdXRpb24uDQoNClJldmlld2VyIDogRGFlaHl1biBLaW0NCg== ------=_NextPart_000_0012_01C13530.4E01FCE0 Content-Type: text/html; charset="ks_c_5601-1987" Content-Transfer-Encoding: base64 PCFET0NUWVBFIEhUTUwgUFVCTElDICItLy9XM0MvL0RURCBIVE1MIDQuMCBUcmFuc2l0aW9uYWwv L0VOIj4NCjxIVE1MPjxIRUFEPg0KPE1FVEEgaHR0cC1lcXVpdj1Db250ZW50LVR5cGUgY29udGVu dD0idGV4dC9odG1sOyBjaGFyc2V0PWtzX2NfNTYwMS0xOTg3Ij4NCjxNRVRBIGNvbnRlbnQ9Ik1T SFRNTCA1LjUwLjQ2MTYuMjAwIiBuYW1lPUdFTkVSQVRPUj4NCjxTVFlMRT48L1NUWUxFPg0KPC9I RUFEPg0KPEJPRFkgYmdDb2xvcj0jZmZmZmZmPg0KPERJVj48Rk9OVCBzaXplPTI+VGhpcyBwYXBl ciBpbnRyb2R1Y2VzIGEgcm91dGluZyBhbGdvcml0aG0gaW4gYWQtaG9jIHdpcmVsZXNzIA0KbmV0 d29ya3MuPEJSPlNlY3Rpb24gMSBhbmQgMiBleHBsYWluIHRoZSBnZW5lcmFsIGJhY2tncm91bmQg YW5kIHRoZSBuZXcgYXBwcm9hY2ggDQppbiB0aGlzPEJSPnBhcGVyIGJyaWVmbHkuIENvbXBhcmlz b24gYmV0d2VlbiB0aGVtIGlzIGFsc28gZ2l2ZW4uIFNlY3Rpb24gMyBhbmQgDQo0PEJSPmRlc2Ny aWJlIHRoZSByb3V0aW5nIGFsZ29yaXRobS4gU2VjdGlvbiA1IHNob3dzIHRoZSBzaW11bGF0aW9u IA0KcmVzdWx0cy48QlI+U2VjdGlvbiA2IGdpdmVzIHRoZSByZWxhdGVkIHdvcmsuIFNlY3Rpb24g NyBjb25jbHVkZXMuPC9GT05UPjwvRElWPg0KPERJVj4mbmJzcDs8L0RJVj4NCjxESVY+PEZPTlQg c2l6ZT0yPlRoZSBwcm9wb3NlZCBhbGdvcml0aG0gaXMgY2FsbGVkICdEeW5hbWljIFNvdXJjZSBS b3V0aW5nJy4gSXQgDQppcyBiYXNlZCBvbjxCUj5zb3VyY2Ugcm91dGluZywgaW4gd2hpY2ggdGhl IHNlbmRlciBjb25zdHJ1Y3RzIHRoZSBlbnRpcmUgcm91dGUgDQp0byBiZTxCUj5mb3J3YXJkZWQg aW50byB0aGUgcGFja2V0J3MgaGVhZGVyLiBFYWNoIGhvc3QgbWFpbnRhaW5zIGEgcm91dGluZyAN CnRhYmxlPEJSPi0gY2FsbGVkICdSb3V0ZSBDYWNoZScgd2hpY2ggaXMgdXBkYXRlZCBkeW5hbWlj YWxseSANCm9uLWRlbWFuZC48L0ZPTlQ+PC9ESVY+DQo8RElWPiZuYnNwOzwvRElWPg0KPERJVj48 Rk9OVCBzaXplPTI+VGhlcmUgYXJlIHR3byBpbXBvcnRhbnQgcHJvdG9jb2xzLjwvRk9OVD48L0RJ Vj4NCjxESVY+Jm5ic3A7PC9ESVY+DQo8RElWPjxGT05UIHNpemU9Mj4xLiBSb3V0ZSBEaXNjb3Zl cnkgOiBUaGlzIHByb3RvY29sIGlzIHVzZWQgdG8gZmluZCBvdXQgYSANCnJvdXRlLCB3aGVuIGl0 IA0KaXM8QlI+Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7 Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5i c3A7Jm5ic3A7Jm5ic3A7IA0Kbm90IGluIHRoZSBSb3V0ZSBDYWNoZSBhbHJlYWR5LjxCUj4yLiBS b3V0ZSBNYWludGVuYW5jZSA6IHRoaXMgcHJvdG9jb2wgaXMgdXNlZCANCnRvIG1hbmFnZSB0aGUg cm91dGVzIGluIA0KdGhlPEJSPiZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZu YnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNw OyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyANClJvdXRlIENhY2hlLiBJZiBh IHJvdXRlIGlzIG5vdCB2YWxpZCBhbnkgbW9yZSwgaXQgDQppczxCUj4mbmJzcDsmbmJzcDsmbmJz cDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgZGVsZXRlZCBmcm9tIHRoZSBSb3V0ZSAN CkNhY2hlLjwvRk9OVD48L0RJVj4NCjxESVY+Jm5ic3A7PC9ESVY+DQo8RElWPjxGT05UIHNpemU9 Mj5TZXZlcmFsIG9wdGltaXphdGlvbiB0ZWNobmlxdWVzIC0gRnVsbCBVc2Ugb2YgdGhlIFJvdXRl IENhY2hlLCANClBpZ2d5LWJhY2tpbmc8QlI+b24gUm91dGUgRGlzY292ZXJpZXMsIFJlZmxlY3Rp bmcgU2hvcnRlciByb3V0ZXMgYW5kIEltcHJvdmVkIA0KSGFuZGxpbmcgRXJyb3JzPEJSPi0gYXJl IGdpdmVuLiBCYXNpY2FsbHkgdGhleSBhcmUgaW50ZW5kZWQgZm9yIHJlZHVjaW5nIHRoZSANCnBy b3RvY29sIG92ZXJoZWFkPEJSPmFuZCBtYW5hZ2luZyB0aGUgUm91dGUgY2FjaGUgZWZmaWNpZW50 bHkuPC9GT05UPjwvRElWPg0KPERJVj4mbmJzcDs8L0RJVj4NCjxESVY+PEZPTlQgc2l6ZT0yPlRo ZSBhbGdvcml0aG0gaW4gdGhpcyBwYXBlciBpcyBmb2N1c2VkIG9uIHJlZHVjaW5nIHRoZSANCm92 ZXJoZWFkIG9mIHBlcmlvZGljPEJSPnRhYmxlIHVwZGF0ZS4gQW5kIHRoZSBzaW11bGF0aW9uIHJl c3VsdHMgc2hvd3MgdGhhdCB0aGlzIA0KYXBwcm9hY2ggaXMgc3VjY2Vzc2Z1bC48QlI+R2VuZXJh bGx5IEkgYWdyZWUgd2l0aCB0aGlzIGFwcHJvYWNoLiBCdXQgSSdkIGxpa2UgdG8gDQpwb2ludCBv dXQgdHdvIHRoaW5ncy48L0ZPTlQ+PC9ESVY+DQo8RElWPiZuYnNwOzwvRElWPg0KPERJVj48Rk9O VCBzaXplPTI+MS4gVGhpcyBwYXBlciBjb21wYXJlcyB0aGVpciBuZXcgYWxnb3JpdGhtIHdpdGgg dGhlIA0KY29udmVudGlvbmFsIGFsZ29yaXRobXM8QlI+Jm5ic3A7Jm5ic3A7IC0gRGlzdGFuY2Ug VmVjdG9yIGFuZCBMaW5rIFN0YXRlIA0KUm91dGluZy4gQnV0LCBpdCBkaWQgbm90IHNob3cgdGhl IHNpbXVsYXRpb248QlI+Jm5ic3A7Jm5ic3A7IHJlc3VsdHMgZm9yIHRoZW0uIA0KVGhvdWdoIHRo ZSBjb21wYXJpc29uIHdpdGggdGhlIG9wdGltYWwgY2FzZSBpcyBnaXZlbiwgaXQgd2lsbDxCUj4m bmJzcDsmbmJzcDsgYmUgDQpoZWxwZnVsIGZvciB0aGUgcmVhZGVycyBpZiBpdCBzaG93cyBob3cg dGhlIGNvbnZlbnRpb25hbCBhbGdvcml0aG1zIHdvcmsuIA0KSW48QlI+Jm5ic3A7Jm5ic3A7IGFk ZGl0aW9uLCBJdCB3aWxsIGJlIGdvb2QgdG8gc2hvdyB0aGUgc2ltdWxhdGlvbiByZXN1bHRzIGZv ciANCm1vcmUgaG9zdHMsIHRvIGtub3c8QlI+Jm5ic3A7Jm5ic3A7IHRoZSBzY2FsYWJpbGl0eSBv ZiB0aGlzIHByb3RvY29sLiANCjwvRk9OVD48L0RJVj4NCjxESVY+Jm5ic3A7PC9ESVY+DQo8RElW PjxGT05UIHNpemU9Mj4yLiBJbiB0aGlzIGFsZ29yaXRobSwgdGhlIHNlbmRlciBuZWVkcyB0byBr bm93IHRoZSBlbnRpcmUgDQpyb3V0ZXMgYmVmb3JlIGl0IHNlbmRzPEJSPiZuYnNwOyZuYnNwOyBw YWNrZXRzLiBJIHRoaW5rIHRoaXMgbGltaXRzIHRoZSANCnNjYWxhYmlsaXR5IG9mIHRoZSBwcm90 b2NvbC4gdGhlIHByb3RvY29sIHJlcXVpcmVzPEJSPiZuYnNwOyZuYnNwOyB0aGF0IHRoZSANCnRv cG9sb2d5IG9mIHRoZSBuZXR3b3JrIGRvZXMgbm90IGNoYW5nZSBkdXJpbmcgdGhlIFJvdXRlIERp c2NvdmVyeS4gQnV0IA0KYXM8QlI+Jm5ic3A7Jm5ic3A7IHRoZSBudW1iZXIgb2YgaG9zdHMgaW5j cmVhc2VzLCB0aGlzIHJlcXVpcmVtZW50IGlzIGhhcmQgdG8gDQpzYXRpc2Z5LiBTbyB0aGlzIGFs Z29yaXRobTxCUj4mbmJzcDsmbmJzcDsgbWlnaHQgYmUgbGltaXRlZCB0byBhIHNtYWxsIG51bWJl ciBvZiANCmhvc3RzIG9yIGEgcmVsYXRpdmVseSBzbG93bHkgbW92aW5nIGhvc3RzLiBJbiBteTxC Uj4mbmJzcDsmbmJzcDsgb3BpbmlvbiwgYSBuZXcgDQphcHByb2FjaCB3aGljaCB1c2VzIG9ubHkg bG9jYWwgcm91dGluZyBpbmZvcm1hdGlvbiwgbm90IGVudGlyZSANCnJvdXRlczxCUj4mbmJzcDsm bmJzcDsgbWlnaHQgYmUgYSBzb2x1dGlvbi48L0ZPTlQ+PC9ESVY+DQo8RElWPjxGT05UIHNpemU9 Mj48L0ZPTlQ+Jm5ic3A7PC9ESVY+DQo8RElWPjxGT05UIHNpemU9Mj5SZXZpZXdlciA6IERhZWh5 dW4gS2ltPC9GT05UPjwvRElWPjwvQk9EWT48L0hUTUw+DQo= ------=_NextPart_000_0012_01C13530.4E01FCE0-- From egs@CS.Cornell.EDU Tue Sep 4 11:15:18 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 f84FFHq17117 for ; Tue, 4 Sep 2001 11:15:17 -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 f84FFGY25025 for egs; Tue, 4 Sep 2001 11:15:16 -0400 (EDT) Date: Tue, 4 Sep 2001 11:15:16 -0400 (EDT) Message-Id: <200109041515.f84FFGY25025@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 2 >From kewang@CS.Cornell.EDU Tue Sep 4 11:10:08 2001 >content-class: urn:content-classes:message >X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 >Subject: review for DSR >Date: Tue, 4 Sep 2001 11:10:09 -0400 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: review for DSR >Thread-Index: AcE1U69Bb/zIug8cSw2qJv1KHJ4ikg== >From: "Ke Wang" >To: "Emin Gun Sirer" >X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f84FA7q16530 > >Review for "Dynamic Source Routing in Ad Hoc Wireless Networks", by >David B. Johnson, David A. Maltz > >This paper introduces the Dynamic Source Routing protocol (DSR) for ad >hoc networks. It's an on-demand dynamic routing protocol that is based >on the concept of source routing. That is, the sender knows the complete >hop-by-hop route to the destination. Mobile nodes maintain route caches >and update them as new routes are learned. Data packets carry the whole >route in the packet header. > >DSR mainly composed of two processes: route discovery and route >maintenance. When a node wants to send a packet, it first looks for its >route cache to find a route. If there is one, it will use this route to >send the packet. Otherwise it begins a route discovery by broadcasting a >route request packet. A route reply is generated when either the route >request packet reaches the destination, or it arrives an intermediate >node that has a route to the destination. Route maintenance is >accomplished by the use of route error packets. If any link is broken, a >route error packet is generated. When source node receives the packet, >it removes routes using this link from its cache. > >There are some advantages of DSR. It's an on-demand protocol and doesn't >need periodic routing, so it can save bandwidth and battery power, which >are rare resources in mobile network. When the topology of the network >remains the same, there is no overhead for routing. Another advantage is >that DSR doesn't require symmetric link. It can work well under >asymmetric links by piggyback. Additionally, the nodes can keep multiple >routes to a destination in the cache. Thus, route discovery does not >need to be invoked when some route is broken. > >At the same time, there are some disadvantages brought by the source >routing and aggressive use of route cache. The overhead of DSR may be >large since the DSR packet has to carry the whole routing information in >its header. Also, the memory overhead may be large because the DSR need >to remember full route and perhaps multiple routes. DSR also lacks some >way to determine the freshness of routes when there are multiple ones in >a node's route cache to choose from. DSR assumes the mobile nodes can >work under promiscuous receive mode, which is not necessarily true. >Because DSR also assumes the diameter of the network is small, and >because of the source routing requirement, DSR does not have good >scalability. > >Final thought: can we combine the traditional table-driven routing and >on-demand routing together, and let the protocol choose it under >different situation? > From daehyun@csl.cornell.edu Tue Sep 4 11:17:02 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 f84FH1q17498 for ; Tue, 4 Sep 2001 11:17:01 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id LAA02943 for egs@cs.cornell.edu; Tue, 4 Sep 2001 11:16:58 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109041516.LAA02943@wilkes.csl.cornell.edu> Subject: 615 PAPER (2) To: egs@CS.Cornell.EDU Date: Tue, 4 Sep 2001 11:16:58 -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 introduces a routing algorithm in ad-hoc wireless networks. Section 1 and 2 explain the general background and the new approach in this paper briefly. Comparison between them is also given. Section 3 and 4 describe the routing algorithm. Section 5 shows the simulation results. Section 6 gives the related work. Section 7 concludes. The proposed algorithm is called 'Dynamic Source Routing'. It is based on source routing, in which the sender constructs the entire route to be forwarded into the packet's header. Each host maintains a routing table - called 'Route Cache' which is updated dynamically on-demand. There are two important protocols. 1. Route Discovery : This protocol is used to find out a route, when it is not in the Route Cache already. 2. Route Maintenance : this protocol is used to manage the routes in the Route Cache. If a route is not valid any more, it is deleted from the Route Cache. Several optimization techniques - Full Use of the Route Cache, Piggy-backing on Route Discoveries, Reflecting Shorter routes and Improved Handling Errors - are given. Basically they are intended for reducing the protocol overhead and managing the Route cache efficiently. The algorithm in this paper is focused on reducing the overhead of periodic table update. And the simulation results shows that this approach is successful. Generally I agree with this approach. But I'd like to point out two things. 1. This paper compares their new algorithm with the conventional algorithms - Distance Vector and Link State Routing. But, it did not show the simulation results for them. Though the comparison with the optimal case is given, it will be helpful for the readers if it shows how the conventional algorithms work. In addition, It will be good to show the simulation results for more hosts, to know the scalability of this protocol. 2. In this algorithm, the sender needs to know the entire routes before it sends packets. I think this limits the scalability of the protocol. the protocol requires that the topology of the network does not change during the Route Discovery. But as the number of hosts increases, this requirement is hard to satisfy. So this algorithm might be limited to a small number of hosts or a relatively slowly moving hosts. In my opinion, a new approach which uses only local routing information, not entire routes might be a solution. From c.tavoularis@utoronto.ca Tue Sep 4 11:22:38 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 f84FMbq18103 for ; Tue, 4 Sep 2001 11:22:37 -0400 (EDT) Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 47381]) by bureau6.utcc.utoronto.ca with ESMTP id <241562-13391>; Tue, 4 Sep 2001 11:20:44 -0400 Received: by webmail3.ns.utoronto.ca id <414676-5766>; Tue, 4 Sep 2001 11:12:48 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER 2 Message-ID: <999616357.3b94ef6592861@webmail.utoronto.ca> Date: Tue, 04 Sep 2001 11:12:37 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 SUMMARY OF ARTICLE #2 - Christina Tavoularis This article presents the routing protocol Dynamic Source Routing (DSR) to be used in wireless adhoc networks. It first introduces various routing protocols for both wired and wireless networks including Distance Vector Routing and Link State Routing. DSR is contrasted to these protocols because the sender host determines a path only when data is to be transmitted, and does not require periodic broadcasting of routing information. Advantages of DSR are mainly the reduction in (1) transmission overhead, (2) overall power used by hosts and (3) memory used to store link state information, which is significant due to redundancy in wireless networks. It also speeds up the acquisition of stable routes in constantly changing dynamic networks. Results of simulation show these desirable properties to be successful using the DSR protocol. Each host maintains a route cache storing known routes, and consults its cache for a path to a desired destination. If no suitable route is found, the route discovery protocol is used concurrently with other communication with hosts. In route discovery, a host broadcasts a route request packet to all hosts within transmission range. Hosts that receive the route request packet will query their route cache, or initiate another route discovery, and eventually reply with route information. Hosts keep track of route request packets from the pair. Hosts must operate in promiscuous receive mode to optimize the efficiency of this protocol. Problems that are dealt with include collisions with simultaneous replies from multiple hosts, loop formation in routes, redundant packet propagation, and network partitioning. This article convincingly conveyed the appropriateness of DSR for adhoc networks. The simulations were thorough in demonstrating the functionality of the protocol, and poor performance traits found during simulation were properly accounted for. For example, the efficiency for constant motion of hosts in the adhoc network is poor (2.6), but is attributed to the fact that routes must continuously be discovered, and there is a higher chance of network partitioning such that attempted transmission won’t time out if the destination cannot physically be reached. I think they should have mentioned what type of addressing would be used (although it is probably assumed to be IP addressing). From jcb35@cornell.edu Tue Sep 4 11:24: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 f84FONq18170 for ; Tue, 4 Sep 2001 11:24:23 -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 LAA28549 for ; Tue, 4 Sep 2001 11:24:24 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f84FRBQ10443 for ; Tue, 4 Sep 2001 11:27:11 -0400 Date: Tue, 4 Sep 2001 11:27:11 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU Subject: 615 Paper 2 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper focused on Dynamic Source Routing (dsr), a reactive routing protocol designed specifically for ad hoc networks in which wireless mobile hosts form networks without any central administration. The protocol described uses methods to discover routes when needed instead of using routing advertisement messages as previous protocols have used. This reduces network overhead so that bandwidth and power is conserved. The paper also describes how to route maintenance and routing errors are dealt with, along with optimizations that can be performed in the protocol. The paper also details the simulation of a typical ad-hoc environment and evaluate the protocol's performance with respect to network overhead and routing effectiveness. When a host needs to find a route to another host, it broadcasts a route discovery packet to all nodes within listening distance. Those hosts then look at the packet to make sure they haven't seen it before; If they haven't, they either re-broadcast the packet with their address on it (after checking to ensure that they weren't already on their, thereby preventing circular loops) or if the address is their own, rend a route reply packet to the initiate which traces back the route. Then, to send data packets, the sender puts the route that it just discovered in the header of the data packet. To deal with route maintenance, if a route becomes broken, then when a packet gets to a node that cannot propagate it any further, it sends a route error packet back to the originating host, which is observed by the other hosts along the way and noted. That node can then start the route request again. The paper then lists a few optimizations, dealing with route caching, piggybacking data on route discoveries, and detecting shorter routes where you can "leapfrog" nodes and more error handling. Finally the paper analyses a simulation of the dsr protocol with a number of mobile hosts moving around in a medium sized room. They summarized their results by showing how the routes found compared to the optimal routes and how many excess packets were broadcast. The amount of overhead increased with the mobility of the hosts as expected, but remained low throughout. Comments: This paper is very well detailed and presented in a clear and logical manner. They detail previous work, where the need for this protocol arose and how the needs differ from existing routing protocols and how this protocol tackles those problems. The paper details how in the testing situation they incurred a low overhead in which the total number of packets transmitted by the protocol is very close to optimal (like a 1% overhead). I would be curious to also see how much total bandwidth the protocol used, since in each data packet the header contains the route to follow. Another issue dealing with routing is that the protocol does not seem to have a way to deal with broadcast packets, or multicast routing of that kind. Also, they mention once about implementing a wireless network on a college campus, and I wonder how this routing protocol would deal with interacting with a wired gateway, since it deals with routing hosts and not subnets. Finally, I would be curious to see other work, as they mentioned, in areas of security regarding routing protocols, due to the problems that one malicious node could cause. From clint@csl.cornell.edu Tue Sep 4 11:44:59 2001 Return-Path: Received: from eckert.csl.cornell.edu (eckert.csl.cornell.edu [132.236.71.67]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f84Fixq20310 for ; Tue, 4 Sep 2001 11:44:59 -0400 (EDT) Received: from localhost (clint@localhost) by eckert.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id LAA21688 for ; Tue, 4 Sep 2001 11:44:55 -0400 (EDT) (envelope-from clint@eckert.csl.cornell.edu) X-Authentication-Warning: eckert.csl.cornell.edu: clint owned process doing -bs Date: Tue, 4 Sep 2001 11:44:55 -0400 (EDT) From: Clint Kelly To: egs@CS.Cornell.EDU Subject: 615 PAPER #2 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This protocol attempts to improve on basic DV-based ad hoc routing protocols by only "discovering" routes when they are needed. This prevents the large amount of possibly needless communication in a network using DV-based protocols. As with similar protocols, the main trade-off here is that route discovery can take a long time, whereas in a DV-based network it should be relatively fast. A big contribution of this paper is that the protocol does not require symmetric links. I am not sure how realistic this is for an ad hoc network, but it is certainly a neat idea! Also, nodes in DSR can have multiple routes to one destination stored in their cache, so if one route breaks down, there still might be another that works. One of the weaknesses of this paper is that the protocol stores the entire route for a packet in the packet header. This could be expensive for long routes! Remembering entire routes instead of just destinations (like in a DV system) requires more memory. From mh97@cornell.edu Tue Sep 4 11:49:07 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 f84Fn7q20793 for ; Tue, 4 Sep 2001 11:49:07 -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 LAA13401 for ; Tue, 4 Sep 2001 11:49:07 -0400 (EDT) From: "ming hao" To: "'Emin Gun Sirer'" Subject: 615 PAPER 2 Date: Tue, 4 Sep 2001 11:48:45 -0400 Message-ID: <000501c13559$14749270$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 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700 Importance: Normal In-Reply-To: <200109022045.f82Kj9409239@hoho.cs.cornell.edu> Dynamic Source Routing in Ad Hoc Wireless Networks This paper proposes a more efficient routing algorithm, Dynamic Source Routing, which can adapts quickly to the Changing connectivity of nodes and incurs little overhead When hosts move less frequently. Simulation results is given To support the conclusion. no real implementation. Advantages of it compared to distance vector and link status is 1. no periodically broadcasting 2. no bi-directionally good link assumption. 3. less redundant paths. The main point of this algorithm is that performing route discovery only When no route info available. Every node stores route info in the cache. Routing decision is determined by checking this cache. Only when it is Not available, route discovery is performed. During route discovery, Explicit reply is needed. The route validness is maintained by the transmission acknowledgement, either at link level or high level. Some optimization is mentioned. Storing routing info in a tree; Reply from cache for route discovery; hop number limited request. Piggybacking data on request packet and so on. The result is great. But I strongly believe it totally depends on how Frequently connectivity changed and how much packets are transferred. I am not quite sure that simulation environment is an adequate simplification Of real environment. And CPU overhead is not simulated. Btw. One advantage of Source routing is that it requires less overhead In the intermediate nodes. Table look up is not necessary in them. -ming From samar@ece.cornell.edu Tue Sep 4 11:57:51 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 f84Fvpq21796 for ; Tue, 4 Sep 2001 11:57:51 -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 f84FvqV19927 for ; Tue, 4 Sep 2001 11:57:52 -0400 Date: Tue, 4 Sep 2001 11:57:52 -0400 (EDT) From: Prince Samar X-Sender: samar@ockham.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 2 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 2. Dynamic Source Routing in Ad hoc Wireless Networks Dynamic Source Routing (DSR) - one of the more popular routing protocols for mobile Ad hoc networks - is a flat reactive (or on-demand) routing protocol based on source routing. DSR, along with AODV, is under consideration for the experimental RFC status by the MANET Working Group of the IETF. DSR is intuitive and simple and at the same time easily adaptable and efficient protocol. The protocol is free of many of the disadvantages associated with distance-vector or link-state routing protocols. The protocol claims to perform well in a variety of network conditions with very little overhead and near-optimal routes. If the source does not already have a route to the destination in its route cache, it initiates route discovery. It first sends a non-propagating route request to its neighbors. If it does receive a route reply in some timeout interval, the protocol floods the whole network with the route request packet, and the destination (or any intermediate node with a valid route to the destination) replies to the source with the accumulated source-route when it receives the query. The route maintenance procedure sends a route error packet to the source in case a link in the route to the destination breaks. DSR makes use of several additional optimizations to improve the efficiency of the protocol, which include: salvaging of bad routes from route caches, gratuitous route repair and promiscuous listening. DSR makes use of route caching aggressively to extract the maximum advantage out of source routing. It also does not require any special mechanism to detect routing loops and is not timer-based, unlike some other protocols. More than one route can be found to the destination, which can be useful in case the "best" route fails. As route discoveries are initiated only on demand, the protocol control traffic is effectively utilized. But, at the same time, there is a finite delay before the route can be found. Hence it cannot, in general, be used for real-time, high QoS traffic. Also, the paper does not talk of any mechanism to expire stale routes or use fresher routes if available (other than the route error packet). This has the disadvantage of consumption of additional network bandwidth even when the packet is eventually dropped. Also, it can lead to pollution of the route caches of other nodes which (over)hear the stale route, which may or may not be corrected soon enough. The simulation results seem to be too less than what may be required to fully understand the working of the protocol. The simulation results are for low network loads with low mobility and very small number of hosts - the protocol does not seem to be tested for more "stressful" conditions. The particularly low percentage of overhead traffic may be due to the long length of conversation time between two hosts, along with the predominantly large-sized data packets. The simulation does not model channel contention which may affect the protocol performance due to the delay associated with it. Also, only bi-directional links are assumed to be present in the network, which may not be a very realistic assumption due to multipath or shadow fading. Also, the authors do not say anything about the percentage of data packets that are actually delivered to the destination. From ms103@cornell.edu Tue Sep 4 11:59:30 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 f84FxUq21867 for ; Tue, 4 Sep 2001 11:59:30 -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 LAA11657; Tue, 4 Sep 2001 11:59:29 -0400 (EDT) From: ms103@cornell.edu Date: Tue, 4 Sep 2001 11:59:29 -0400 (EDT) X-Sender: ms103@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 2 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Johnson and Maltz describe and asses a routing algorithm specifically designed for routing packets in an ad-hoc network. They take many relevant issues into consideration, and the problems of route discovery and route maintanence are addressed well. The route discovery/route cache optimization seems reasonable because it is likely that a destination will be addressed repeatedly after the first reference. One weak assumption that the authors make is that the "diameter" of the network (as defined in the paper) will be small. This will be valid only for the simplest of networks. Another shortcoming in their simulation is that they don't consider half-duplex channels and link interference effects. Admittedly they're not concerned with the link-level, but I think that real-life effects such as the ones above will negatively affect the results they've published. From ranveer@CS.Cornell.EDU Tue Sep 4 12:01:07 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 f84G17q21969 for ; Tue, 4 Sep 2001 12:01:07 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: 615 PAPER 2 Date: Tue, 4 Sep 2001 12:01:08 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 2 Thread-Index: AcE1Ws+ctEnAT6jERfO4x//DXHxEVw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f84G17q21969 Dynamic Source Routing in Ad Hoc Wireless Networks This paper proposes among the first reactive routing protocols for ad hoc networks. A node wishing to send a packet establishes a source route to the destination, and uses this information to route messages. Various optimizations are proposed to reduce traffic in the network. The main contribution of this paper is the idea of source routing in ad hoc networks. It makes sense to use source routing since lesser information is to be stored and updated at individual nodes. The on-demand nature of the protocol gives all the benefits of any reactive protocol : it is highly robust to the dynamicity of the network. DSR is also able to handle unidirectional links which is among the added benefits of this protocol. Another new scheme proposed by DSR that needs mention is the use of promiscuous mode for routing. This is a good idea for learning information of/from neighbors without any added overhead. Experience with DSR has shown the disadvantages of this protocol. DSR is no better than flooding in the presence of unidirectional links. Most of the optimizations also do not hold in the presence of unidirectional links. So although DSR works in such an environment it has a very poor performance. From ramasv@CS.Cornell.EDU Tue Sep 4 12:08:54 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 f84G8sq23002 for ; Tue, 4 Sep 2001 12:08:54 -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 2 Date: Tue, 4 Sep 2001 12:08:56 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F265@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 2 Thread-Index: AcE1W4IXIWti4JUTEdWTbQCQJ5m7oA== 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 f84G8sq23002 Dynamic Source Routing in Ad Hoc Wireless Networks This paper describes DSR, one of the most popular routing protocols for ad hoc network. DSR is a successful adaptation of the idea of source routing used in wireline networks to ad hoc networks. This protocol is on-demand (reactive) in both route discovery and route maintanence, i.e., routes are discovered only when a packet needs to be transmitted to a destination for which no route is currently available and route errors are discovered and rectified only when a packet is currently using that broken route. DSR is also defined to work in the presence of asymmetric or uni-directional links and even with MAC protocols that does not guarantee delivery and does not perform neighbor discovery. The absence of periodic message overhead and the reactive nature of both route discovery and route maintanence makes this protocol very efficient. Since DSR is a source routing protocol, each packet (data and some control) carries a header identifying the entire route the packet needs to traverse in order to reach the destination. Route discovery is performed whenever an active source route is unknown to the destination. It involves braodcasting thoughout the network a route request packet requesting for routes. The destination node or an intermediate node with an active route to the destination could send a route reply back to the source identifying the source route. Link level notifications or hop-level acknowledgements (passive or active) are used to detect link breakages. Route maintanence is performed only when a link breakage is identified attempting to send a packet. The intermediate node could then route the packet through an alternate active route it is aware of or return the packet back to the source for reinitiating route discovery. Several optimizations to the above protocol have also been presented in this paper. The most important of this is the employment of route cache. The route cache stores several source routes discovered in the recent past by itself or by other nodes. This not only provides several alternate routes when encountering link breakages but also optimize route discoveries. Later papers by the same authors have confirmed the advantages of using route cache. Other enhancements such as working in promiscous mode and using gratuitous route replies have made DSR one of the most efficient and important routing protocol. However, DSR does suffer from several limitations. The use of source routes adds extra control overhead to each data packet transmitted making DSR efficient only in small networks with routes of length about 10 hops. Although DSR is designed to work in the presence of unidirectional links its performance has not been studied in such networks (even follow up papers do not describe simulations in uni-directional enviroments). An important aspect of unidirectional routing involves identification of asymmetric links which has been ignored in this definition of DSR. Initial attempts by me to simulate DSR in unidirectional environments showed that DSR does not scale to even moderate network of 80 nodes and 20 concurrent routes. Purely on-demand route maintanance appears to be counter productive for route replies and route errors; route replies generated by intermediate nodes lead to a kind of RREP-explosion problem; hop-level active acknowledgements adds further scalability constraints to this protocol. Adequate simulations of the protocol are not presented in this paper. A maximum of 24 nodes in a small room moving at very low speeds does not reflect most real-life applications of ad hoc networks. Further standard metrics such as packet delivery, goodput, average latency used to judge routing protocols are not reported in this paper. Substituting an actual MAC and data link protocol with a simple statistical model renders the presented numbers unreliable. However, in depth simulation of this protocol performed later on reveals that DSR is an efficient routing protocol for bidirectional ad hoc networks. From egs@CS.Cornell.EDU Tue Sep 4 14:47:33 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 f84IlXq11166 for ; Tue, 4 Sep 2001 14:47:33 -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 f84IlWJ22038 for egs; Tue, 4 Sep 2001 14:47:32 -0400 (EDT) Date: Tue, 4 Sep 2001 14:47:32 -0400 (EDT) Message-Id: <200109041847.f84IlWJ22038@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 2 >From andre@CS.Cornell.EDU Tue Sep 4 11:47:53 2001 Date: Tue, 4 Sep 2001 11:45:50 -0500 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: Emin Gun Sirer Subject: CS615 Summaries Content-Disposition: inline User-Agent: Mutt/1.3.20i Dynamic Source Routing in Ad Hoc Networks This paper describes a protocol for dynamic sorce routing. The routes are computed by the sender node. Each node keeps a cache of the recently seen routes. If the destionation host is not in the cache, a discovery packet is broadcasted, and resent until the target is found. Optimization: 1) the hosts which know the route respond instead of forwarding 2) sniffing the packets to learn new routes. There is a siultation showing the protocol is quite efficient, except when the nodes move a lot, but I do not trust it, because the range of transmission was 3 when the simultation space was a square of 9, which means the number of hops between aany 2 nodes will always be small (with only 4 nodes at (3,3) (3,6) (6,3) (6,6) you cover nearly all the surface!) It is too small to be valid? Even with caching, some route discovery migh be forwarded to almost all the nodes. What about a malicious node wich claim it can reach hosts it cannot? It seems difficult to overcome. The Simulation was done with short messages, how to deal with sufficienbt long messages for theroute to change? Only tunning in the buffers and the timeouts I guess.