From mr228@cornell.edu Wed Sep 4 21:17:42 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 g851Hgh12535 for ; Wed, 4 Sep 2002 21:17:42 -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 VAA07410 for ; Wed, 4 Sep 2002 21:17:37 -0400 (EDT) Message-ID: <3D76B0B1.1DA5A952@cornell.edu> Date: Wed, 04 Sep 2002 21:17:37 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en]C-CCK-MCD MS4.76 V20001206.2 (Windows NT 5.0; U) X-Accept-Language: en,ja MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper introduces a new routing protocol for use in Ad-hoc networks. The paper discusses current work in this area and the problems with the existing algorithms. Looping and counting-to-infinity appear to be the most significant problems with current approaches. Their algorithm attempts to resolve these and other problems by introducing the notion of time into route update packets. With a timestamp they argue it is possible to avoid propagating stale or potentially incorrect information throughout the network. Routing information is disseminated from node to node at regular, pre-determined intervals. Additionally, to improve performance, if a node receives information that makes a significant change to its routing table, this information is distributed immediately. Depending on specifics of implementation, this could be a huge win -- especially for very dynamic networks. The protocol also has provisions for doing incremental (instead of "full dump") updates. This should also be very beneficial to rapidly changing networks. Although they mention that empirical analysis has begun and looks promising, no results were available for this paper. Although theoretically their algorithm requires less storage space and should be less prone to "flooding" versus other schemes, no empirical evidence is provided to validate their theories. Future work should probably be aimed at figuring out at what protocol layer the various pieces of the routing logic should be placed. -- Mark From xz56@cornell.edu Wed Sep 4 23:32:20 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 g853WJh11996 for ; Wed, 4 Sep 2002 23:32:19 -0400 (EDT) Received: from XIN (dhcp-128-84-87-159.ece.cornell.edu [128.84.87.159]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id XAA29495 for ; Wed, 4 Sep 2002 23:32:18 -0400 (EDT) Message-ID: <00bc01c2548c$d599db60$9f575480@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 3 Date: Wed, 4 Sep 2002 23:32:16 -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 The key contribution of this paper is the introduction of the "sequence number for routing information packets" to the traditional distributed Bellman-Ford algorithm. This (should) eliminates the stale routes problem and loop formation. The problems in this paper can be: 1. Handling of the broken links. It's not quite clear described there how the sequence number is assigned to the entry regarding to the destination whose link is lost (odd or even, but based on whom?). Also, when the node is back to life, how its sequence number is synchronized to the ones stored in the other nodes routing table? I am wondering why not use a flag and leave the sequence number as it was. 2. Updating the routing table in the case of the equal sequence number. I don't think the number of hops is a good metric to use because in this case the delay is not take into consideration. Why not just discard these packets? Is it too complex the method used to damping fluctuation? From hs247@cornell.edu Wed Sep 4 23:34:32 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-1.nyroc.rr.com [24.92.226.177]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g853YWh12200 for ; Wed, 4 Sep 2002 23:34:32 -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 g853YV314648 for ; Wed, 4 Sep 2002 23:34:31 -0400 (EDT) Message-Id: <5.1.0.14.2.20020904233300.00b243e8@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Wed, 04 Sep 2002 23:34:30 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper's contribution is the introduction of the Destination-Sequence Distance-Vector Protocol (DSDV). This protocol differs from the regular distance-vector protocol, in that a sequence number is added to each entry in the vector. The claim is that this eliminates looping because a node can now differentiate between old and new updates. Small features such as incremental update make the protocol more light weight which is suppose to be better for low bandwidth devices often used in ad-hoc networks. The paper did a very good job in comparing the algorithm to related works. Also I was very impressed that they included a mathematical proof in why the DSDV will not have loops. Another area which was well done was how the authors thought about DSDV and how it can interact with other layers. Also, the mentioning of the criteria used to compare DSDV to other algorithms was good. A unique idea that was introduced was to use even and odd sequence numbers to indicate different things. The DSDV admittedly doesn't have as fast of convergence as other DV algorithms, but this is a trade off to make gains in loop prevention. A weakness of the paper is that it does not describe the algorithm in detail and there are evident holes that need to be filled. The reader would be very hard pressed if he/she tried to implement the protocol just from the description in the paper. Some areas which need filling would be generation of sequence numbers, the splitting of update packets, calculation/table for the delay of advertisement and how/when the "full dump" happens. But the authors do mention that testing and experiments still have to be done. At the time this paper was written, this algorithm was still its prelimary stages. The next step from this paper would be to implement this protocol and gather performance numbers to see how it works and compares to other protocols. And since it works at different layers, research on which layer it best works at and how it interacts with higher protocols. How does DSDV affect TCP/IP? And if this protocol is good for mobile computers, what other applications or networks can it also benefit? From shafat@CS.Cornell.EDU Thu Sep 5 00:47: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 g854lYh27782 for ; Thu, 5 Sep 2002 00:47:34 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 3 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 5 Sep 2002 00:47:33 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D15077F@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcJUl1o7NRw8pycFRmaZmr9NsEWmSQ== 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 g854lYh27782 This paper draws its main ideas from the original Distributed Bellman-Ford (DBF) routing algorithm, and incorporates two other features to present a more reliable, robust, and most importantly, loop-free algorithm for ad-hoc networks. A sequence number is tagged along in every routing table entry at each node to inject a sense of time synchronization in the network. This allows nodes to distinguish earlier packets from more recent ones broadcasted from the same originating host, and maintain a more up-to-date routing table. The other major component introduced is the damping fluctuations feature. It slows down the rate at which new routing information is disseminated in the network, and does not unnecessarily flood the channel by choosing not to frequently update new routing information of one or more highly mobile nodes. This new DSDV protocol has been proposed in a manner that seems feasible and is well illustrated with examples in the paper. However, the authors fail to present any quantitative analysis of their work, especially in regards to scalability and reliability. A quantitative comparison between the effects, with and without the dumping fluctuations factor, would also have highlighted its expected benefits. It was interesting to note the use of the MAC layer in the algorithm and how it could be used effectively. Although, the authors did not do a great job in justifying the advantages of such an implementation. Further room for improvement lies in a more critical performance evaluation, introducing security features etc. A more efficient algorithm could also be developed to reflect a more accurate "average settling time". The proposed method may not always work adequately under various circumstances. From ag75@cornell.edu Thu Sep 5 01:36:53 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 g855arh06156 for ; Thu, 5 Sep 2002 01:36:53 -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 BAA04208 for ; Thu, 5 Sep 2002 01:36:51 -0400 (EDT) Date: Thu, 5 Sep 2002 01:36:51 -0400 (EDT) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII In this paper the authors try to make modifications to the Bellman-Ford routing mechanisms. The modifications address the poor looping properties in the presence of broken links and time dependent nature of the interconnection topology describing the links. One of the positive things about the resulting algorithm is that the mobile hosts don't need to do any time synchronization. Another good thing is that the advertisement of routes that didn't stabilize yet is delayed, so the number of rebroadcasts with the same frequency number is reduced. The algorithm also guarantees loop-free paths to each destination, it is space efficient, and it will work with other higher layer protocols if the notification of which other nodes are accessible is done at layer 2. The algorithm also has some problems. It broadcasts routing info every few seconds, which results in a lot of traffic. The authors HOPE that the technique used to predict how long to wait before advertising new routes works - doesn't sound very scientific. They also say that using DSDV at layer 2 requires passing data about layer 3, which sounds like a hack. Convergence of the algorithm is bad in the worst case and untested on average. Finally, there was no study done on how the algorithm scales, which is obviously important and should be addressed. From bd39@cornell.edu Thu Sep 5 03:19:42 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 g857Jgh24071 for ; Thu, 5 Sep 2002 03:19:42 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id DAA13131 for ; Thu, 5 Sep 2002 03:19:40 -0400 (EDT) Message-Id: <5.1.0.14.2.20020905031810.00b3e878@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 05 Sep 2002 03:19:14 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The major contribution of this paper is the introduction of a new routing protocol, DSDV. DSDV seeks to provide a distributed distance vector routing algorithm that is free of loops and count to infinity problems through the use of sequence numbers. The idea of withholding advertisement of new routing information for a given amount of time is also interesting, although could result in worse, rather than better route information. A major weakness of the paper is the lack of experimental evidence. The paper mentions many properties of the protocol, i.e. fast convergence, amount of bandwidth needed to be devoted to routing informational broadcasts, which are mentioned in their future work section. This basically leaves all of the variables wide open. They give mention that these properties of the protocol are highly dependent on a laundry list of different conditions. It would be nice to know what the actual behavior is. Also, the strategy for conservation of bandwidth (O(n) on the number of nodes) in broadcasting only incremental changes in the network is dependent on the network being stable, which seems slightly contrary to the original assumption that the network would be a dynamic one. Scalability while mentioned, is not fully addressed. As with the previous paper, security is topic which is missing from the discussion. One area that could be investigated is the integration of layers 2 and 3 of the network. An ad-hoc routing algorithm requires knowledge of MAC layer properties, such as neighbors, link quality and radio strength. It would be interesting to have some consistent/efficient method of assigning network names to MAC names, rather than incorporating it with the routing protocol itself. Another area that could be investigated is the route efficiency versus mobility and settling time. All other properties of the protocol need to be empirically investigated as well. The claims of this paper are interesting, however it is peppered with too many (all) mentions of future simulation studies and forthcoming experimental data. From jsy6@postoffice2.mail.cornell.edu Thu Sep 5 03:47:20 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 g857lKh29911 for ; Thu, 5 Sep 2002 03:47:20 -0400 (EDT) Received: from JSY23.cornell.edu (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id DAA12674 for ; Thu, 5 Sep 2002 03:47:18 -0400 (EDT) Message-Id: <5.1.0.14.2.20020905033545.00a08d90@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 05 Sep 2002 03:47:17 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Currently there is no good routing protocol for a wireless mobile ad-hoc network. Wireless mediums are of limited and variable range, and may only have a single network interface adapter, unlike the existing wired media the protocols were designed for. Thus any routing protocol would need some modifications. Also, most of the protocols exhibit their worst case scenario in a highly dynamic interconnection topology. Some problems that arise are the heavy computational burden placed on each mobile host, poor convergence characteristic, and loop formations. This paper offers a solution to the above issues by introducing a modified version of the distance-vector routing algorithm (DSDV). In the distance-vector algorithm, each node maintains and broadcasts its estimate of the shortest distance to every other node in the network. The shortest distance is calculated by a succession of next hops. A node i treats its neighbor j as a next hop for destination k if the shortest path from i to k includes edge (i,j). A major modification made to this algorithm is the addition of a sequence number tag for each route table entry. The sequence number, originated by the destination station unless a link is broken, is used to quickly distinguish stale routes from the new ones. Routing tables are stored at each station of the network. These tables list all available destinations and the number of hops to each. Updates are transmitted not only periodically, but also as soon as significant new information arrives. These updates are usually sent in incremental packets, instead of sending all available information (full dump), only the changed information is sent. Full dumps are sent only when the network is fairly immobile. One weakness is the failure to approach the counting-to-infinity problem. It was acknowledged that this problem exists for the RIP algorithm, but it was not addressed how this problem is fixed for the DSDV model. Also, it would be interesting to note how this algorithm scales. For a very large network that is highly mobile, how effective will this algorithm be in transmitting the appropriate information in lieu of the high collision rate that will arise. The more mobile the network, the more updates there will be to broadcast, thus increasing the collision rate. It was noted in the beginning of the paper that poor convergence time was an issue that needed to be addressed, but there was not much information provided about the convergence time of the DSDV routing algorithm. Convergence time will depend on many parameters, including the size and mobility of the network, update periods, and average processing loads of the mobile entities among other factors. The next step would be an implementation of this protocol in order to gather performance evaluation in areas like convergence and damping fluctuations (I do not think their settling time calculation will work for some cases... i.e settling time fluctuates between two numbers). From walsh@cs.duke.edu Thu Sep 5 07:57:45 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 g85Bvjh23218 for ; Thu, 5 Sep 2002 07:57:45 -0400 (EDT) Received: from localhost (curly.cs.duke.edu [152.3.140.76]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id HAA20170 for ; Thu, 5 Sep 2002 07:57:39 -0400 (EDT) Received: from 208.51.228.79 ( [208.51.228.79]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Thu, 5 Sep 2002 07:57:39 -0400 Message-ID: <1031227059.3d7746b395d7e@login.cs.duke.edu> Date: Thu, 5 Sep 2002 07:57:39 -0400 From: walsh@cs.duke.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 3 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: 208.51.228.79 Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers Two problems with traditional Bellman-Ford Distance-Vector protocols motivate this paper: transient and long term loops; and time sensitivity (e.g. route flaps, poor convergence, etc.). The authors propose BF + sequence numbers + route invalidation + damping. Sequence numbers are used in a straightforward way to prevent routing loops, and to help invalidate stale routes. Damping is meant to prevent route flaps. Convergence is not addressed. Contributions: Straightforward use of sequence numbers to prevent routing loops. In addition, clever distinction between odd and even sequence numbers allows hosts to distinguish between routes cancelled by neighbors and those advertised by a host. Problems: Readability – the authors seem to have taken a randomized approach to constructing paragraphs and sections. Motivation – “[BF] can cause loops” is not enough detail to motivate a complete overhaul, especially in light of the authors own admission that RIP also has loops but is very successful. Evaluation – almost none, aside from an explanation of how loops are avoided. Jumbled explanation of damping, advertisement delays, ARP/MAC resolution, etc. These should have never made it into the paper. Further, the damping solution is pure speculation (e.g. unmotivated and unevaluated), and contains too many arbitrary tunable parameters. Scalability is ignored. From smw17@cornell.edu Thu Sep 5 09:46:36 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 g85Dkah18430 for ; Thu, 5 Sep 2002 09:46:36 -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 JAA19100 for ; Thu, 5 Sep 2002 09:46:35 -0400 (EDT) Message-ID: <3D775FA1.2090002@cornell.edu> Date: Thu, 05 Sep 2002 09:44:01 -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 3 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit DVDS The system/protocol described in this paper is a version of a distance vector protocol, termed Destination Sequenced Distance Vector. This is a proactive routing protocol based on an implementation of a distributed Bellman Ford algorithm. The key feature of this algorithm is the implementation of a sequence number maintained at the destination machine. By introducing this sequence number and enforcing constraints on sequence numbers for routes to this destination, the authors are able to prove that the implementation is loop-free. The algorithm presented has many positive features. It eliminates the usual looping problems present in Bellman Ford algorithms through careful use of a sequence number. It also provides a mechanism to reduce network bandwidth by permitting individual nodes to refrain from immediately advertising new routes when the node judges that there is a good chance of another update soon (based on ongoing statistical analysis at the node). A mechanism to bypass this wait was also implemented in the case of an otherwise unreachable node. The authors have also instituted an incremental update strategy, triggering route updates primarily in response to a topological shift in the network rather than always sending a full table in each update cycle.. The combination of these mechanisms should ideally reduce the average network traffic while still maintaining a reasonable response time to significant topological changes. In addition to the good properties, there are also some less desireable characteristics. While the algorithm does permit nodes to hold back on a route announcement, the node must update their routing table when a higher sequence number is available. This may have the effect of introducing repeated routing variations into the system, and may route packets through less desireable routes due to the sequence number interactions. This routing scheme also requires a per-node storage capacity that is linear in the network size and communications bandwidth proportional to the rate of topological change. Finally, there is little or no capability to deal with the case of a damaged or compromised node that is broadcasting incorrect data, and no concept is presented of how the inherent level of trust could compromise user security. To cite one example, the automatic route update based on sequence numbers could be easily subverted by a hostile node to achieve a concentration of traffic routed through the hostile node. Such behavior exposes the user to attacks such as man-in-the-middle style attacks. The security implications of an automatically configured network that is completely transparent to the user are not discussed. /Sean From mp98@cornell.edu Thu Sep 5 09:48:33 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 g85DmXh18691 for ; Thu, 5 Sep 2002 09:48:33 -0400 (EDT) Received: from r105572.resnet.cornell.edu (r105572.resnet.cornell.edu [128.253.240.214]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id JAA29951 for ; Thu, 5 Sep 2002 09:48:30 -0400 (EDT) Date: Thu, 5 Sep 2002 10:08:03 -0400 Mime-Version: 1.0 (Apple Message framework v482) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 PAPER 3 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: X-Mailer: Apple Mail (2.482) Perkins and Bhagwat describe a new distance vector routing protocol designed for ad-hoc networks. Their protocol is notable in that it was designed specifically with ad-hoc networks in mind: Incremental updates will hopefully cut down on the bandwidth needed for routing information, and there are rules that trigger an update as soon as a link is broken--a common event in ad-hoc networks. Most notable of all is the presence of sequence numbers designed to avoid loops and count-to-infinity. However, the paper does suffer from the fact that they present no benchmarks, nor even a proof of concept. The protocol itself contains no solution for the presence of a malicious host advertising 'newer' sequence numbers to break the network or start loops. Even non-maliciously, such an event could occur due to transmission errors. The protocol needs to be implemented and tested before further work can be done. The sequence number system needs to be updated to resist transmission errors and possibly for security purposes (one could imagine the destination actually signing the number with PKC). The notion of incremental routing information, and propagation of only new information may have applications in other routing algorithms. From adam@graphics.cornell.edu Thu Sep 5 10:55:17 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g85EtHh05173 for ; Thu, 5 Sep 2002 10:55:17 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g85EtB0k048940 for ; Thu, 5 Sep 2002 10:55:11 -0400 (EDT) Date: Thu, 5 Sep 2002 10:47:29 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615PAPER3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII DSDV is a step at improving ad-hoc network routing over the previously proposed Bellman-Ford alg. It aims to have loop free routing working on both network layer 2 and layer 3. It differs over the traditional distance vector alg by appending a sequence number to each route announcement (this allows the "newest" routes to be used) but also allows the receiver of such a message to wait a period of time before announcing the route. Advertised routes, would hopefully be the most stable based on this withholding idea, there would be some chance to predict and test how well the newly announced route works. Another interesting point to this article is the standard that DSDV can work in purely ad-hoc mode, or also w/ a base station and ad-hoc simultaneously. B-F however could also work w/ a base station, so it seems that this is a "selling point" of the alg and not an advantage over previous algs. The strengths of this paper include the comparision to other routing algs and the identification of the strengths/weaknesses of DSDV wrt to them. Another strength is the mathematical (and seemingly sound) proof about the loop-free nature of this alg. A third strength, I believe, is dampening fluctations, which try to keep uneeded route changes to a minimum by minimizing changes in the routing table. The fourth strength is the use of incremental and full updates in an attempt to conserve bandwidth, although w/ a highly dynamic ad-hoc network it's unclear that incremental updates will be able to conserve bandwidth. The weaknesses of this paper are certainly its lack of real world testing and evidence of performance over other routing algs. This paper does say that tests are planned to determine some things, but nothing was presented as having been done. Scalability, evaluation (as mentioned above), Security and Energy Eff are all left to the readers imagination as none are really addressed in this paper. There is certainly a scale concern for large ad-hoc networks where a table of routes could certainly get unruly and large since it is linear in size to the number of computers in the network. Implementation details are sparse too, leaving the reader once again to pondering exactly how to implement a protocol of this nature. This paper is a good improvement over traditional B-F and could be certainly improved further to make an even better alg. The gaurantee of loop free routing is great, but something needs to be done about security, and scalability. First w/ a large network (10,000 nodes?) maybe at a conference or something like that it would be extremely important to reduce the size of tables being kept, updates could certainly cause broadcast storms since incermental updates would be either very frequent or full updates often required (due to size restrictions on increment size). Is is it possible to work on some sort of distributed path system, closer to a wired network? Just a thought, one not well pondered by me. Also security is a problem that needs to be addressed, in an ad-hoc wireless network there is absolutely no gaurantee that data is secure, and not getting intercepted completely, man in the middle style attacks could easily be accomplished in this type of environment. Overall a good first step, but not necessarily developed enough for more than primitive use, in places w/ small networks that security can be enforced by distance (from other listening devices) and trust in the people using the network. From tmroeder@CS.Cornell.EDU Thu Sep 5 11:18:32 2002 Received: from dhcp99-165.cs.cornell.edu (dhcp99-165.cs.cornell.edu [128.84.99.165]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g85FIWh11816 for ; Thu, 5 Sep 2002 11:18:32 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-165.cs.cornell.edu (8.11.6/8.11.6) id g85FIfV05228; Thu, 5 Sep 2002 11:18:41 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15735.30161.684425.806146@dhcp99-165.cs.cornell.edu> Date: Thu, 5 Sep 2002 11:18:41 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER #3 X-Mailer: VM 7.05 under Emacs 21.2.1 DSDV proposes significant changes to the Bellman-Ford-like algorithms for distributed ad-hoc networks which changes are specifically designed to save on bandwidth and avoid routing loops. A clear contribution to the field is the idea of different types of 'dumps' of information, incremental and full. This differentiation allows small packets to be sent most of the time, and large packets only when needed. They also try to avoid broadcast storms in their updating of the distance information; they use an algorithm to determine how long they ought to wait, upon receiving new path lengths, before broadcasting this information to their neighbors. They also show that such loops cannot be generated by their algorithm for updates. Finally, the complexity of the storage space required is only O(n), which was matched only be RIP at the time. A major criticism of this paper is that the system has not even been completely implemented, and so almost all the ideas are purely theoretical. There is no evidence that these methods actually work well with real machines and latencies in the networks, nor with common network topologies. It would be much more valuable to read this work even a few months later, when they would have at least some idea of the acceptable parameters for the system (if indeed there are any that work well). Even within their theoretical framework, there are some problems. For instance, the issue of security and trustworthiness has not been addressed at all. The algorithms assume that all of the nodes actually want the system to end up in the best case. If a node decides that it want to degrade the network, it is easy to accomplish. Furthermore, there is a significant issue of load balancing. Under DSDV, certain nodes will wear out more quickly, for they will always be chosen as the best case for a given route, and if the route happens to have the highest volume in the neighborhood, the node will be a bottleneck for the data as well as more likely to break down more quickly. An interesting point of expansion might be to examine exactly what was given in the last paragraph, and to modify the algorithm to notice high-stress areas of the graph and to re-route or provide alternate routes to alleviate the load. Similarly, some idea of authority might be added to the system, so that nodes without authority cannot arbitrarily disrupt the communications. From kfir.shay@cornell.edu Thu Sep 5 11:20:40 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 g85FKeh12114 for ; Thu, 5 Sep 2002 11:20:40 -0400 (EDT) Received: from jigglypuff (syr-24-58-63-160.twcny.rr.com [24.58.63.160]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA16631; Thu, 5 Sep 2002 11:20:39 -0400 (EDT) From: "Kfir Shay" To: Cc: Subject: 615 PAPER 3 Date: Thu, 5 Sep 2002 11:20:39 -0400 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="windows-1255" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 The main contribution of the paper is the innovative approach (protocol) it takes to tackle the challenges of ad hoc networking. The DSDV protocol is based on modeling mobile computers as routers; the authors show how this innovative approach is very attractive with features like: loop free, no internodal coordination and low memory requirement of O(n)*. These features are highly desirable for ad hoc networking and are lacking in all other routing protocols that were covered in the article. The inner workings of the protocol are described, raising some important concepts such as: stability of routes, sequential numbering, settlings times and the representation of broken links as infinite routes. Another interesting feature is the ability of the DSDV protocol to work not only at network layer 3, but also below it yet above the MAC layer software in layer 2. The weaknesses of the paper are the lack of experimental data to prove the paper's claims and answer some questions regarding the behavior of the protocol in real life environments; this is mostly addressed as future work. Although issues like scalability and robustness are addressed, there is no numerical analysis of these issues. One can only assume that this will be elaborated in the papers to come on the DSDV protocol. *where n is number of nodes of the network kfir S. kfir.shay@cornell.edu From yao@CS.Cornell.EDU Thu Sep 5 11:25:56 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 g85FPuh13468 for ; Thu, 5 Sep 2002 11:25:56 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 3 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 5 Sep 2002 11:25:55 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C1B@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcJU8IcD2hKXei+rQUeONKxidBkUHw== From: "Yong Yao" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g85FPuh13468 The Perkins paper presents the intuition and some implementation details of a typical proactive routing algorithm, DSDV. It also analyzes the properties of the DSDV and compares it against some other routing protocols, including link state and RIP. The paper shares the same weakness as that of the PRNET paper we discussed last time, no evaluation or experiment result. Validation should be a very important part of an ad-hoc routing paper, especially when a new routing protocol is first proposed. Scalability analysis is another missing part. Proactive routing protocols suffer from the scalability problem, so it is worthwhile to analyze DSDV in a large-scale network. Some details are not well explained. One example could be when to forward an update to neighbors. If a node delays its update as described in the paper, then it could have a chain effect, which increases the potential latency of all further nodes to update their routing tables. It could be a possible expansion to add some experiments to test and compare different methods. Yong From ks238@cornell.edu Thu Sep 5 11:57:06 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 g85Fv6h22985 for ; Thu, 5 Sep 2002 11:57:06 -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 LAA29698 for ; Thu, 5 Sep 2002 11:57:05 -0400 (EDT) Message-Id: <5.1.0.14.2.20020905115545.01ccdec0@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 05 Sep 2002 11:56:51 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper was a wonderful explanation of the proactive routing protocol, DSDV Highly Dynamic Destination-Sequenced Distance-Vector Routing protocol and was also a good way to follow up the previous paper. Many issues that we had raised in regards to the earlier paper seemed to be directly addressed in this paper, which really strengthened its validity. For instance, the author starts off with a description of the memory intensive Link-State algorithm which employs a flooding protocol. Furthermore, this protocol is widely vulnerable to temporary loops. The author introduces this algorithm and its many flaws to provide a foundation upon which the rest of the paper seems to be based. In other words, the DSDV protocol seems to address many, if not all the flaws, in former protocols. Some important issues that I found DSDV address were memory or space conservation, time efficiency, prevention of the counting to infinity problem and most importantly prevention of the formation of routing loops. One of the key facets of DSDV is the inclusion of sequence numbers, which is used to prevent the existence of old data in routing tables, upon which the dynamically changing topology is based. The author goes into great depth in analyzing the issue of loop prevention with the use of sequence numbers. Additionally, the issue of damping fluctuations and the use of settling times to prevent them is also an important issue. Furthermore, a discussion regarding the use of Layer 2, MAC addressing and including base stations in the network seems to be unique features of the DSDV protocol. For the most part, I found this to be a strong paper. I felt that there were many fewer problems than with the earlier paper. A couple of obvious issues that were left out, were again, security measures in the protocol. No discussion of any security measures being implemented is discussed. Another, interesting problem that the author mentions but doesn't really draw upon which peeked my interest was the issue of "limited range by the physical characteristics of the medium," when using a wireless medium. To me, I feel that this is an inherent barrier precluding scalability that the author touches but definitely needs to elaborate more upon. I felt that the description and the justification behind making the choices for the algorithms that were made was strong for the most part. The only issues that I would pick at would be setting thresholds or maximum values arbitrarily. For instance, when describing the settling time table, we see that a maximum value for the time it takes for a route to be stable is assigned. I would expect or would like to see experimental data showing what type of maximum value is set for such thresholds and how successful they are in practice. These weaknesses are not major, but are issues worthy of discussion. I feel that the paper for the most part addressed some pivotal problems with routing algorithms quite well. From mtp22@cornell.edu Thu Sep 5 11:57:40 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 g85Fveh23041 for ; Thu, 5 Sep 2002 11:57:40 -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 LAA01641 for ; Thu, 5 Sep 2002 11:57:39 -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 3 Date: Thu, 5 Sep 2002 11:58:40 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02090511584009.00149@narnia> Content-Transfer-Encoding: 8bit The major contribution of this paper is the first loop-free distributed Bellman Ford algorithm that does not involve internodal communication. So basically what the work in this paper does is take the popular Bellman Ford algorithm used in many routing protocols and addresses its two biggest problems, routing loops and counting-to-infinity. This has been done before, but it does not appear to have been done before without internodal communication (the primary motivation behind avoiding internodal communcation being to reduce the complexity of the protocol) A weakness of this paper is the lack of statistical results. Efficiency is very important in routing and a new protocol will find it hard to gain acceptance if it has not shown to be effective. The work in this paper could be expanded upon by adding security features. The broadcast nature of many wireless networks makes it easy for people to snoop and intervene. For example, it would be easy for an attacker to figure out the sequence numbers being used by a node and forge new ones for malicious purposes. From ashieh@CS.Cornell.EDU Thu Sep 5 11:58:21 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 g85FwKh23121 for ; Thu, 5 Sep 2002 11:58:20 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g85FwKj21334 for ; Thu, 5 Sep 2002 11:58:20 -0400 (EDT) Date: Thu, 5 Sep 2002 11:58:20 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers This paper presents a loop-free distance vector algorithm. Destination-generated sequence numbers are used both as an indication of the freshness of a route, and to prevent loops from forming. New routes are chosen to replace old routes if: 1) new route has a higher sequence number 2) new route has same sequence number and lower cost. Updates caused by 2) does not cause routes to be formed, by a cited theorem. Links introduced by 1) do not cause loops because of an ordering property of the routes; each node has sequence number <= than that of the next "closer" node to the destination (*). In a loop, some node n is already on the routing path, and is induced to form a new link to an upstream node k. By 1), k > n (comparing sequence numbers). By (*), k <= n, since they're in a loop and so n is upstream to k. Condition 1) introduces transient routes of arbitrary length, and so damping was proposed to introduce hysteresis into routing update to prevent temporary bad routes from being propagated (waste bandwidth on updates that will quickly be superceded), and from being used (waste bandwidth on longer paths). Weaknesses - Damping appears to be an inelegant solution to transient routes, as it addresses topology change through some kind of weighted average (and so topology change is indirectly measured through routing changes). A more direct measurement of topology change is likely possible in this wireless setting (velocity, link state) - Did not state the loss model that they were planning to simulate - No discussion of security Future directions This routing algorithm operates at layer 2, and therefore layer 2 retransmission common in packet radio systems can operate using knowledge of the content of routing packets, eg their relative importance. Alan Shieh From sc329@cornell.edu Thu Sep 5 12:05:33 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 g85G5Xh24812 for ; Thu, 5 Sep 2002 12:05:33 -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 MAA00095 for ; Thu, 5 Sep 2002 12:05:32 -0400 (EDT) Message-Id: <5.1.0.14.2.20020905120441.02cf1ac8@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 05 Sep 2002 12:05:37 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chandrakumar Highly Dynamic Destination-Sequenced Distance-VectorRouting for Mobile Computers This paper discusses the Destination-sequenced Distance-Vector(DSDV) protocol as a proactive routing protocol for mobile ad hoc networks. The paper presents modifications to the BellMan Ford algorithm to circumvent the poor looping properties. DSDV make use of sequence numbers to obviate the need for any internodal co-oridnation to prevent the possible formation of routing loops. Each node in the network maintains a routing table, which lists all the available destination and the number of hops to reach it. A sequence number is also tagged with each entry. Sequence numbers are generated by the originating host other than the case to indicate a broken link, when an odd sequence number with an infinte metric is generated by any mobile host which detects the presence of the broken link. The novelty of DSDV lies in the clever policy of broadcasting of the updates. Newly recorded routes are scheduled for immediate advertisement to the current Mobile hosts' neighbors, whereas routes which show an improved metric is scheduled for advertisement at a time which depends on the average settling time for routes to the particular destination. When a node receives an update with a new sequence number, it updates its table. In case of receiving an update with the same sequence number, updation is done only if it has a better metric. By storing a field, install time, with each entry, a node can detect stale routes and delete those after specific time intervals. The updates sent form a node can be a full dump or an incremental. DSDV uses techniques to prevent damping fluctuations. Each node calculates a settling time by maintaining a running, weighted average over the most recent updates of routes, for each destination. The advertisement of new routes are delayed as specified by the settling time. This helps to prevent broadcast of premature metrics, which would unnecessarily ripple through the entire network. Routes with infinte metrocs are advertised immediately. The paper also explains how the algorithm guarantees loop-free paths to each destination. The comparison of DSDV with some of the other protocols reflects some of the most desirable features it possess, which is useful in a dynamic ad-hoc style environment. But DSDV still has all the inherent problems of any pro-active procol. As the network size increase, the packet size would grow bigger. This results in poor scalability. And fast convergence of updates could also be an issue with the protocol. From pj39@cornell.edu Thu Sep 5 12:22:57 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 g85GMuh29532 for ; Thu, 5 Sep 2002 12:22:57 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id MAA19195; Thu, 5 Sep 2002 12:22:54 -0400 (EDT) Date: Thu, 5 Sep 2002 12:22:54 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200209051622.MAA19195@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: pj39@cornell.edu Reply-To: pj39@cornell.edu Cc: pj39@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: pj39@cornell.edu X-Originating-IP: 132.236.227.190 Subject: 615 PAPER 3 This paper discusses a routing approach for ad-hoc networks. The main problems with a routing algorithm for ad-hoc networks are solving the routing loop problem, solving the count to infinity problem, space complexity requirements and complexity of internodal coordination. This paper (DSDV) presents an effective modification to the bellman ford algorithm to avoid routing loops in the face of broken links and the resulting time dependent nature of the interconnection topology. DSDV employs the use of sequence number tags for each route table entry to solve the routing loop problem. It uses even sequence numbers generated by originating mobile hosts and odd sequence numbers to denote broken links (metric infinity). DSDV with the help of settling time table prevents fluctuation of routing table entry advertisements (damping fluctuations). It also suggest the possible use of MAC addresses for packet forwarding thus eliminating unnecessary ARP reqeusts by mobile hosts. This paper properly explains the working of the DSDV with an example which is very useful in understanding. It also tries to prove that DSDV guarantees loop free routing. In the paper results of actual simulation is not given. Hence, in the absense of empirical information it is difficult to compare it with other routing methods. There is no empirical data to support that DSDV in the average case is expected to converge quite rapidly. With the absence of empirical data it also difficult to establish the following metrics i.e average convergence time, incremental update period, settling tiem etc. Moreover there is not much mention on the protocols at higher level esp at network layer. There is no mention on the scalabiltiy issue, security issue and energy efficieny issue. Future work should focus more on providing the results of simulation so that it can be effectively compared with other methods. From liuhz@CS.Cornell.EDU Tue Sep 10 00:43:54 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 g8A4hsh29920 for ; Tue, 10 Sep 2002 00:43:54 -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.5762.3 Subject: cs615 PAPER 3 Date: Tue, 10 Sep 2002 00:43:54 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5D4@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 3 Thread-Index: AcJYhKqcmVIHZer1QYKzeDiqcqlFwA== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8A4hsh29920 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 liuhz@CS.Cornell.EDU Tue Sep 10 00:45:14 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 g8A4jEh00007 for ; Tue, 10 Sep 2002 00:45:14 -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.5762.3 Subject: 615 PAPER 3 Date: Tue, 10 Sep 2002 00:45:14 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5D5@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcJYhNptn4xwYMWbRUek+JdbYTWMoA== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8A4jEh00007 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 vivi@CS.Cornell.EDU Tue Sep 10 11:58:50 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 g8AFwoh15460 for ; Tue, 10 Sep 2002 11:58:50 -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: 615paper3 Date: Tue, 10 Sep 2002 11:58:50 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF60@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper3 Thread-Index: AcJY4vQVVePzOJ3nSkOK56kJ83DO4g== 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 g8AFwoh15460 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. AODV The contribution of this work (as the paper says) is the realization of a smoothly functioning system that provides almost optimal routes without resorting to frequent route advertisements. It guarantees loop-free operation, and seems to be better than DSR in incorporating better routes in the middle of a transaction. AODV shares a problem with DSR - if a node that is part of the shortest path from the source to the destination does not hear an RREQ packet broadcast, the route formed will not be a shortest route. But AODV has provisions for switching to a better route, in case a node learns of a better route. (although how a node comes to know of a better route is not discussed) Although routes are not broadcast across the network, nodes still transmit "Hello" messages, which could consume bandwidth and energy, and defeat the purpose of having an On-Demand routing protocol. The paper has not specified what value is used in the "dest_sequence_#" field when a node initiates a route-discovery. This value is of immense significance, as it decides which routes are admissible, and which are not. The simulations performed here are better than the ones we have seen earlier, in the sense that simulation parameters have been determined based on the performance of the protocol in various conditions. But the mechanism used to determine optimal values of parameters "rreq_tries" and "allowed_hello_loss" seems to be faulty, as both are independent parameters, and the simulations are performed by varying one of them while keeping the other constant. There is the possibility that using different values might lead to better performance. Also the simulation of the protocol for 500 and 1000 nodes uses smaller room sizes than is desirable. The work can be extended by making this protocol support Real Time applications. (Right now, this is not possible because of the large delays.) From linga@CS.Cornell.EDU Tue Sep 10 12:13:56 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8AGDuh19765 for ; Tue, 10 Sep 2002 12:13:56 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8AGDuP21047 for ; Tue, 10 Sep 2002 12:13:56 -0400 (EDT) Date: Tue, 10 Sep 2002 12:13:56 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 3&4 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by sundial.cs.cornell.edu id g8AGDuh19765 Last class we have taken a look at proactive routing strategies. This time we are studying two reactive routing strategies. Proactive approaches require periodic advertisements and hence substantial bandwidth requirements and unnecessary load on the nodes (even when the network topology has not changed). To avoid this, routes are obtained when necessary (on-demand) in the reactive approach. The main disadvantage of reactive approaches is the delay in setting up the route from source to destination on-the-fly when the source node wants to send some information across. Ad-hoc On-Demand Distance Vector Routing (AODV) ----------------------------------------------- This a reactive routing algorithm. Routes are established only on-demand (i.e when necessary). Main problems with proactive approaches like DSDV are: scalability (control message overhead grows as O(n^2)); excessive bandwidth consumption because of periodic advertisements. The routing alogrithm proposed here scales better than proactive approaches like DSDV and also gives similar guarantees (esp. in not so frequently changing topology). A pure on-demand routing acquision scheme (nodes that are not in the active paths neither maintain any routing information nor participate in periodic routing information exchange) has been proposed. Neighbor information is important and can be maintained in many ways (eg: local broadcasts). Path discovery packets are broadcasted only when a certain source node wants to figure out a route to some destination. Source node initiates path discovery using RREQ (. A RREQ is uniquely identified by the first two fields. When a node receives a RREQ it either sends a route reply (RREP) back to the source or forwards the RREQ to its neighbors after increasing the hop count. Assuming bi-directional links reverse path is setup automatically when the RREQ travels from source to various destinations. RREP is forwarded to the source via the reverse-path. When this happens each node along the path sets up a forward pointer to the node from which the RREP came and updates timeout info and records latest destseq# for this destination. Route table management is done using timeouts: route request expiration timer-for purging reverse path entries that do not lie on the path from source to destination; active_timeout period-to maintain active neighbors corresponding to a given destination. When a link fails, the node upstream propoages a RREP with a new seq# and hopcount of infinity to all active upstream neighbors. This will eventually reach all active source nodes. Presented simulation results showing that: AODV finds routes fairly quickly and accurately; find routes without much delay; AODV scales to 1000 nodes. Pros: A new approach to routing in adhoc networks has been presented. This has the advantages of: avoiding unnecessary bandwidth consumption; decreasing load/power requirements on the nodes; better scalability. This works great especially in a not so dynamic environment (topology does not change too rapidly). Cons: The delay in setting up the path from source to destination when the source decides to send some information may be substantial (esp if the diameter of the network is high and the topology changes occur very frequently). Poor notion of scalability(just 1000 nodes, even though this appears to be the best during that period). Dynamic Source Routing in Adhoc Wireless Networks ------------------------------------------------- This is another reactive routing mechanism which is claimed to work well even in the case of high rates of host movements. Their scheme works with a simplistic assumption that the diameter of the network is a very small number. Under these simplistic assumptions the results in the paper show that the protocol works great. When a node wants to send information to a destination, it constructs a source route in the packet's header which is list of addresses of the hosts in the network through which the packet should be forwarded in order to reach the destination host. When a host which is not the destination receives this packet it simply forwards the packet to the next hop. If the source does not already know the route to the destination it dynamically discovers the route to the destination. To do this, the source node broadcasts a route-request packet to its neighbors (nodes in range). Route-request has the source id and a requestid which uniquely identifies the request. If the host-address is already present in the route-request we discard the packet. Otherwise, if it is the destination, it replies with the route-reply packet and if it is any other node, it just adds it's address to the route-request packet and broadcasts it to its neighbors. Now if the destination knows a route to the source it just sends the route-reply. Otherwise it could send it through the reverse path if the links are bi-directional. Another solution proposed is for the destination host to initiate a route discovery for the source and piggyback the route-reply information along with this route discovery. Route maintenance procedure monitors the operation of a route between any given source and destination and informs the sender of the routing errors. Acknowledgments could be hop-by-hop or passsive acks. A host of optimizations are suggested, prominent of which is using a tree to store the routes in the route-cache for efficiency reasons. Simulation resuls show the efficacy of their approach. Pros: Looks like the first of the reactive protocols to take care of high rates of host movement. Simulation results show that their scheme works great (route lengths are on average within a factor of 1.01 of optimal etc). Cons: The authors make many simplistic assumptions the most important of which is: the diameter of the network is very small. There are no simulation results showing the scalability of the system. From liuhz@CS.Cornell.EDU Wed Sep 11 20:23:43 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 g8C0Nhh29969 for ; Wed, 11 Sep 2002 20:23:43 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 3 Date: Wed, 11 Sep 2002 20:23:42 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5DE@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 3 Thread-Index: AcJZ8qZ3LiHeTjlNRfOLfapXZShEcg== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8C0Nhh29969 This paper presents a proactive routing protocol which is loop-free and suitable for a dynamic and self-starting ad-hoc network while requires no internodal coordination, thus makes the protocol quite simple. DSDV is similar to the Bellman-Ford algorithm, but includes a sequence number in the routing table. The sequence number is crucial to this algorithm, because a mobile host can quickly distinguish stale routes, which ares the main causes of routing loops, from the new ones and thus avoid formation of routing loops. Sequence number is origianated from the destination and assigned an even value in most cases except when a link is break in the network, then the node adjacent to the link will update the sequence number with an odd value. This odd sequence number is propagated to the whole network rapidly, thus all the nodes in the subnet know this change quickly. However, the use of sequence number will increase the number of advertisement packets tremendously, because each mobile host will advertise the update packet apon the receipt a route with a newer sequence number even if the network topology doesn't change at all.In this paper, a method is also given to deal with this situation. That's to delay the advertisement till the route stabilizes. Another trick present in this paper to decrease the amount of information carried in the routing packets is using two kinds of packets: "full dump" and "incremental". "incremental" packet is sent more frequently then full dump. Some weaknesses. As mentioned above, the introdution of sequence number will cause many unnecessary routes information transmittals. Although a damping fluctuation algorithm is given, its effect is not evaluated and it cannot eliminated this problem completely. Besides, the delay of advertisement updated routes will cause some incorrect routes temporarily in some case. The fast convergence property is just the author's assumption without proof. The tremendous traffic need to exchange information between adjacent nodes also prevents this protocol scaling to large networks or to high mobility scenarios From vivi@CS.Cornell.EDU Fri Sep 13 15:33:56 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 g8DJXuh02761 for ; Fri, 13 Sep 2002 15:33:56 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper3 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Fri, 13 Sep 2002 15:33:55 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF65@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper3 Thread-Index: AcJbXH/DBbtOrk8BTtGE2y4H2GdsfQ== 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 g8DJXuh02761 The paper gives an overview of the DSDV Routing Protocol for Ad hoc networks. The main contribution of this protocol is its guarantee of loop free routing. This is achieved through the innovative use of sequence numbers to time-stamp each update. The protocol makes sure that information about broken links and newly discovered neighbors is propagated through the network rapidly. Thus every node has a very current picture of the state of the network. DSDV's feature of generating immediate updates whenever there is an occurrence of a link break or the discovery of a new neighbor could mean that most of the bandwidth is consumed by these update packets when the mobile hosts are moving around rapidly. It might be a better idea to club a finite number of updates in a single (if slightly bigger) update packet. Each node's tables require O(n) space, and so do the full dumps of each node. This would be a problem in a network consisting of a large number of nodes. An alternate method of storing the routing information would be (as discussed in class) dividing the network into zones and maintaining entries corresponding to whole zones as single units. A rigorous analysis of the protocol performance would definitely be welcome. Specifically, estimates of parameters such as the bandwidth used by the update packets and the settling time of routes will verify the claims made in the paper.