From papadp@ece.cornell.edu Mon Oct 1 19:20:34 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f91NKYo09079 for ; Mon, 1 Oct 2001 19:20:34 -0400 (EDT) Received: from plato (plato.ece.cornell.edu [128.84.239.28]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f91NLRo05760; Mon, 1 Oct 2001 19:21:27 -0400 Date: Mon, 1 Oct 2001 19:23:08 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-X-Sender: To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 18 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," by C.E. Perkins and P. Bhagwat. Panagiotis Papadimtratos papadp@ee.cornell.edu DSDV is a proactive routing protocol that extends distance vector routing in order to render the idea applicable in the MANET context, while maintaining simplicity (in contrast to schemes requiring inter- nodal coordination). The basic idea is the use of sequence numbers indicating the freshness of routing updates as a means to avoid loops and speed up convergence. Practically, sequence numbers act as the primary routing metric, complemented by the number of hops, i.e., distance. Nodes update their topology view favoring updates that carry 'fresh' sequence numbers, or, in case the update entry at least as recent as the one currently known, the update is performed only if the distance to the corresponding destination is decreased. As explained below, these criteria provide for loop-freedom in a steady-state condition. Nodes periodically advertise their views on the topology, i.e., their distance vectors, accompanied by the sequence numbers of the updates generated by the corresponding destination nodes. Each advertisement/ update is identified by a monotonically increasing, even, sequence number maintained by the transmitting node. Upon reception of the advertised routing table, nodes update their own routing tables accordingly. Upon detection of a link breakage, one or more destinations may become unreachable. Then, the detecting node issues an infinite metric update with a sequence number incremented by one (i.e., an odd sequence number), with respect to the known destination sequence number. This declares the destination unreachable and forces receiving nodes to incorporate it in their own advertisements, until they hear a new advertisement from the destination. Such an update will be the next even number and it will exceed the previously assigned odd number, thus propagating the fresh reachability information. The essence of this mechanism is that potentially stale information will not be used for routing table updates, and thus loops cannot be created (recall discussion of the loop-free criteria; path length increase). The apparent drawback is that although a destination deemed unreachable by one node may be very well reachable, through an alternate path, by other nodes receiving the infinite-metric update. Nonetheless, this condition will not be changed until the new (periodic) advertisement of the destination reaches that network area. The updates are advertised not only periodically but also in a triggered manner. An example is the above-described case of the destination declared unreachable that receives an update; it advertises its routing table with the entry to itself (metric 0) accompanied by a new sequence number. A relatively more frequent case is that of the reception of an update that carrying a new, lower metric for a specific destination. Then, the triggered update is necessary so that more nodes potentially adapt their shortest paths. Finally, one would expect that the most frequent type of triggered update would be the one due to a new sequence number accompanying a non-decreasing distance metric. Nevertheless, it is not clarified whether this is a feature of the protocol; on one hand, distribution of more up-to-date state information can contribute in route maintenance, but, on the other hand, it may impose a significant control traffic overhead without (any) significant routing decision changes. The significance of a route decision change is a concept that recurs in this work, without the provision of clear guidelines. The motivation is to avoid routing fluctuations and excessive overhead, with the latter being the target of damping mechanism. Nodes maintain a time estimate of the settling time, i.e., the time difference between the first route installment and the instance of an arguably 'optimal' route (possibly, a route metric that is not decreased for several update intervals). Then, it is indicated that, maybe, nodes could implement some method to determine which changes are significant, e.g., not likely to change fast, and choose accordingly how to structure their updates. A practical efficiency enhancement, regarding the update propagation, is the distinction between 'full dump' and 'incremental' updates. Instead of always transmitting the entire distance vector (used here interchangeably with routing table) to one's neighbors, the periodic advertisements are composed only of distances that changed due to previously received updates. In conclusion, the proactiveness of DSDV limits its applicability for highly dynamic topologies, while its control overhead is not expected to vary significantly over a range of topology rates of change (assuming a reasonably 'aggressive' triggered update policy). Furthermore, the periodic (full or incremental) advertisement interval is an operational parameter that cannot be set in an ad hoc manner. Nonetheless, its simplicity and the 'appropriate' choice of operational parameters render DSDV competitive, in a range of scenarios, to other MANET routing protocols. Of course, the authors should have provided the protocol placement, with respect to the application context and the intended underlying protocol layer, in the first place. From eyh5@cornell.edu Mon Oct 1 21:26:49 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 f921Qno21436 for ; Mon, 1 Oct 2001 21:26:49 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id VAA04794; Mon, 1 Oct 2001 21:26:44 -0400 (EDT) Date: Mon, 1 Oct 2001 21:26:44 -0400 (EDT) From: eyh5@cornell.edu Message-Id: <200110020126.VAA04794@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: eyh5@cornell.edu Reply-To: eyh5@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: eyh5@cornell.edu X-Originating-IP: 128.84.224.150 Subject: 615 Paper # 18 Highly Dynamic Destination-Sequenced Distance-Vector Routing for Mobile Computers Charles E. Perkins, Pravin Bhagwat This paper discusses the use of destination-sequenced distance vector (DSDV) routing protcol as a routing technique in an ad-hoc network. Since this paper was written in the mid-1990s, the proposal recommends the proactive route-searching approach (within the neighborhood of the querying node), one that has been increasingly questioned and replaced by the reactive route-searching approach in the more recent proposals. Nevertheless, DSDV laid the foundation for the future work in the area. One major contribution is that it introduces the use of a sequence number, generated by the destination node, to reflect the freshness of the information contained in the broadcast route-query packet. The sequence number is pivotal for the querying node to choose a suitable route among several candidates. The second criterion in choosing a route is to choose the route with the lowest metric if it shares the same sequence number with another candidate route. Another important contribution by DSDV is that it ensures loop-freedom in its routes. DSDV has paid close attention to the time interval between two consecutive routing-information broadcasts. The concerns here are that any such broadcast must to some degree ensure that the routing information it carries will be durable and not easily overwritten in a foreseeable future, and that this information be disseminated as quickly as possible throughout the network. To this end, the proposal devises the scheme of incremental dump and full dump. The incremental dump is broadcast more frequently, carrying only information changed since the last full dump. This technique has the advantage of saving bandwidth by transmitting fewer control packets, and facilitating expedient change in the routing tables of the receiving nodes. The performance evaluation of DDSV compares it with several other routing algorithms in three aspects: loop freedom, use of internodal coordination, and space comlexity. Although in this paper, DSDV is said to have a space complexity of O(n), in a later paper on AODV, also by Perkins, it is acknowledged the actual complexity is O(n^2). Given the proactive nature of algorithm, it can be deduced that the network scalability may be a valid concern, as more nodes will spend more time and overhead control information in exchanging the advertisements of their presence. Another problem inherent in DSDV is the reliance on the destination node to disseminate update information. This, tied into the large scale of network, may result in a longer delay for all the nodes to receive and maintain up-to-date routing information. From wbell@CS.Cornell.EDU Mon Oct 1 22:05:25 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9225Oo25211 for ; Mon, 1 Oct 2001 22:05:24 -0400 (EDT) Received: from [192.168.1.103] (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 WAA13140 for ; Mon, 1 Oct 2001 22:05:20 -0400 (EDT) Subject: 615 PAPER #18 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.14.99+cvs.2001.09.29.08.08 (Preview Release) Date: 01 Oct 2001 22:05:02 -0400 Message-Id: <1001988330.2431.0.camel@brute> Mime-Version: 1.0 18) Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers DSDV is the introduction of the Destination-Sequenced Distance-Vector Routing protocol whose goal is to provide loop free shortest-path routing via maintaining next-hop tables at each node for each destination. Routing information is propagated by routing tables which are exchanged by neighbors periodically either incrementally, or full dumps when desired. They place a good deal of emphasis on keeping the network stable, and to be precise, to keep the network from oscillating because of varying times of propagation of routing information. To that end, they keep a set of routing tables, which are advertised which may be different from the actual tables used to perform routing of packets. Advertised tables are synchronized with the actual routing tables after some period of time when it has been decided that these routes are stable. This also has the added benefit of reducing network traffic as better routes are found. The goal is to keep incremental updates small [within one packet] and to only push out changes that high enough importance, such as link failures, which are immediately broadcast to neighbors and produce a broadcast storm as they flood the network. One can see that these local changes have severe consequences to a large portion of the network, and therefore the scalability of such a protocol is likely small. It seems that bandwidth efficiency was very much on their minds and they present many ways that bandwidth can be further optimized. Without simulations, I can only conjecture that their fears are well founded and that DSDV uses a large amount of the total network bandwidth in control packets. They present a proof of loop freedom, which seems to have been a large accomplishment over previous algorithms of this type, and hint that in the future simulation results will be presented. This paper is definitely the stab into a new territory of routing protocols and is most likely a highly referenced paper, despite it's lack of details in many places. From mh97@cornell.edu Tue Oct 2 00:18:10 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 f924I5o09180 for ; Tue, 2 Oct 2001 00:18:05 -0400 (EDT) Received: from mars (syr-66-24-28-66.twcny.rr.com [66.24.28.66]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA07225 for ; Tue, 2 Oct 2001 00:18:02 -0400 (EDT) From: "ming hao" To: Subject: 615 PAPER 18 Date: Tue, 2 Oct 2001 00:17:25 -0400 Message-ID: <001301c14af9$25d85050$6701a8c0@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 V6.00.2600.0000 Importance: Normal High Dynamic Destination Sequenced Dsitance Vector Routing for Mobile Computers this paper makes a small modification on the DBF, i.e., tagging each updates from the destination so that the resulting algorithm gaurantees loop free. The way it works is that: 1. destination generates update information about routing and tags it with sequence number(even number in the paper) and then broadcasts it to its neighbors. other nodes update their route table only if they get a update with newer sequence number or a better metric. this ensures the loop free. 2. when the node detecting a link failure, it can also generate a sequence number which is different from normal one, to eliminates invalid routes. in addition, the paper also proposes a mechanithm to damp fluctuation. the idea is the introduction of a settling time. nodes will delay for a while before it rebroadcasts the updates. this time is selected based on previous average and recent event has a higer weighting factor. link failure message will not be delayed. no results are givent about new algorithm. fast convergence feature is only intutition. but the paper compares it with other proactive algorithms and shows the new algorithm can not only be loop free, but also save memory space. Maybe it is the best among proactive algorithms. but the message overhead is too high and on-demand routing algorithms would be better than them. -ming From viran@csl.cornell.edu Tue Oct 2 04:24:07 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 f928O7o04411 for ; Tue, 2 Oct 2001 04:24:07 -0400 (EDT) Received: from localhost (viran@localhost) by cray.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id EAA74516 for ; Tue, 2 Oct 2001 04:24:02 -0400 (EDT) (envelope-from viran@cray.csl.cornell.edu) X-Authentication-Warning: cray.csl.cornell.edu: viran owned process doing -bs Date: Tue, 2 Oct 2001 04:24:02 -0400 (EDT) From: "Virantha N. Ekanayake" To: egs@CS.Cornell.EDU Subject: 615 PAPER 18 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents a modification to DV routing using the Bellman-Ford algorithm, with the addition of sequence numbers to the routing updates. This prevents stale information from being used to update routing tables, thus eliminating loops after the routing tables have converged to the correct network topology. They also propose using a damping function to smooth out the routing table update frequency (which is a major problem with pro-active protocols). Evaluation of the ideas presented in the paper is difficult, since no simulations have been done. It seems that the scalability will be about the same as AODV (i.e. not very high). From teifel@csl.cornell.edu Tue Oct 2 10:21:29 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 f92ELTo11862 for ; Tue, 2 Oct 2001 10:21:29 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f92ELOr07974 for ; Tue, 2 Oct 2001 10:21:24 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 2 Oct 2001 10:21:23 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 18 Message-ID: <20011002102046.Y96977-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII DSDV: This paper presents the Destination-Sequenced Distance-Vector (DSDV) protocol. This protocol requires each node to periodically and incrementally broadcast routing and topological information to its neighbors. Each node also agrees to relay packets to other nodes upon request. The periodic routing update includes the following information: (the destination's address, the number of hops required to reach the destination, and the sequence number of the information received regarding that destination, as originally stamped by the destination). DSDV requires its routing protocols to converge as quickly as possible, so that a moving mobile node does not cause a close series of storm broadcasts. This, I think, this somewhat limits the maximum mobility allowed for nodes in this protocol and is not addressed in this paper--except in the future work section. Section 3 could have been written better, i.e. there should have been a sentence or two that clearly defined what the DSDV protocol was. It was difficult to clearly get a good idea about it until reading all the way through at least Section 5. The solution to the problem with DSDV--i.e. a mobile host receiving two routes to the same destination, but with different sequence numbers--is explained in a rather hand-wavy manner. But if this paper is a ``new idea'' paper then it is fine, although not really satisfying. The lack of simulation data in this paper was not impressive. The order estimates of performance versus other protocols is nice, but actual performance in these dynamic networks is more complicated and needs to be simulated. From daehyun@csl.cornell.edu Tue Oct 2 11:00:10 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 f92F0Ao16727 for ; Tue, 2 Oct 2001 11:00:10 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id LAA45377 for egs@cs.cornell.edu; Tue, 2 Oct 2001 11:00:05 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200110021500.LAA45377@wilkes.csl.cornell.edu> Subject: 615 PAPER 18 To: egs@CS.Cornell.EDU Date: Tue, 2 Oct 2001 11:00:05 -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 proposes a routing algorithm called Destination Sequenced Distance Vector Routing (DSDV), which provides loop free routing in ad hoc networks. DSDV is a extension of Distance Vector (DV) routing algorithm. The main problem of DV is that it is not loop free. Several modified algorithms are proposed to solve this problem. But they requires some forms of internodal coordination, which is not suitable in ad hoc networks. So, the main goal of DSDV is to provide a simple loop free routing algorithm The main idea of DSDV is to use a sequence number, which prevents false information from being used, so guarantees loop free. A mobile host uses even sequence numbers, when it sends out routing information to neighbors. But a broken link update packet uses odd sequence number. In this way, the real sequence number can supersede the infinite metric. When a mobile host receives new routing information, it compares the information to the previous information, then more recent sequence number will be used. If the sequence numbers are same, the better metric will be used. DSDV uses periodic advertisements to propagate the routing information through the network. Because this might be big overhead, they uses two types of packets, 'full dump' and 'incremental'. Full dump packets contain all the routing information, but incremental packets contain only the changes since the last full dump. By scheduling these two packets cleverly, the overhead can be reduced. I think the main contribution of this paper is that it provides a basis for routing algorithms in ad hoc networks. Actually, this paper is published in the mid 1990, so it does not seem as good as other algorithms we have discussed so far. But, it is still valuable in that many protocols are based on DSDV. This paper compares some routing algorithms and one of the criteria is space complexity. They say that because of the lack of memory in mobile computers, economy of space is important and emphasize on the excellence of DSDV in that points. But, I think is not valid any more. Memory or computation within a mobile host is much smaller problem than communication between hosts, with respect to both time and power. One interesting point of this paper is that it tries to apply DSDV into layer 2 as well as layer 3. Though this might not be related to this paper much, I think this is a new idea. In my opinion, in wireless communication, layer 3 and layer 2 are very closely related, so routing protocols should consider both aspects at the same time. From ramasv@CS.Cornell.EDU Tue Oct 2 11: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 f92F8so17538 for ; Tue, 2 Oct 2001 11:08:54 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: cs615 PAPER 18 Date: Tue, 2 Oct 2001 11:08:53 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7CE46@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 18 Thread-Index: AcFLVCaGbMU8XPLuRZqQeH/Y946RHQ== 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 f92F8so17538 Highly Dynamic Destination Sequenced Distance Vector Routing for Mobile Computers This paper describes a routing protocol called DSDV designed for ad hoc networks. DSDV is a proactive routing scheme that maintains at each node routing information for all the destinations. Each node is expected to send periodic packets containing this routing information to all its neighbors. A distance vector scheme based on Distributed Belmanford algorithm is used to find shortest routes. The innovation in this paper involves using sequence numbers to avoid permanent loop formation and implmenting a damping scheme and incremental update scheme to reduce the overhead due to link breakages. Routes to each node has a sequence number identifying the freshness of the routes (higher sequence number imply fresher routes.) At all points of time routes with a higher sequence number is given priority over another route with lower sequence number even if it is fewer hops. Each destination periodically increases its sequence number to the next higher even number. This information trickles throughout the network eventually making all the nodes to have a fresh enough route to this destination. Using even numbers has an advantage in that a broken route (due to link breakage) is marked with the next higher odd number. This prevents nodes from cofusing a broken route with a good route (as happens in AODV). Changes in route information (higher sequence number, change in metric) are broadcast throughout the network in a controlled manner. Only the changed information is carried by incremental updates while a full dump takes place occasionally. This decreases the length of periodic packets. Information regarding broken routes trigger immediate broadcasts. While broadcast due to other changes are damped (i.e., sent with a delay). The damping scheme is proposed to prevent unnecessary update and damping time is decided adaptively using a weighted average scheme. An advantage of DSDV is that the routes are guaranteed to be loop-free if the channel behaves reasonably well even in the presence of mobility. However, sequence number updates force creation of fresher routes even though the older routes could be stable. How frequently this needs to be done is a prameter decided in an ad-hoc manner. The damping feature introduced in the paper is very intereseting and could be studied further. Deciding frequencies of full-dumps and incremental dumps is not trivial. The protocol is essentially proactive and gathers routing information for entire network. The protocol can thus not scale to large networks or to high mobility scenarios because the traffic generated also grows. From samar@ece.cornell.edu Tue Oct 2 11:13:26 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f92FDPo18164 for ; Tue, 2 Oct 2001 11:13:25 -0400 (EDT) Received: from ockham.ee.cornell.edu (ockham.ee.cornell.edu [128.84.236.58]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f92FEFo22062 for ; Tue, 2 Oct 2001 11:14:15 -0400 Date: Tue, 2 Oct 2001 11:13:22 -0400 (EDT) From: Prince Samar X-Sender: samar@ockham.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 18 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 18) Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers This paper presents a proactive routing protocol for ad hoc networks, which has been formed by modifying the basic Bellman-Ford routing mechanism to make it suitable for a dynamic, self-starting network mechanism. The approach uses sequence numbers to tag each routing table entry in order to eliminate routing loops and count-to-infinity. The algorithm could be used at the network layer or at the MAC-layer by using network layer or MAC layer addresses. The protocol sends out periodic updates or triggered updates to make sure that pertinent route table changes can be propagated throughout the population of the mobile nodes as quickly as possible whenever any topology changes are noticed. All sequence numbers are generated by the destination host in each route table entry except for cases when a link has been broken. The sequence numbers generated by the destination are even numbers and the ones generated by any other node detecting a change are odd numbers. This helps in keeping the knowledge of network topology fresh at a node. A mechanism is used for damping the possible fluctuations arising due to the best route arriving out of order - routes are not advertised until it is likely that they are stable (by using a guess based on the past history). Comments: - This protocol, like other table-driven protocols, suffers from drawbacks like high overhead, very low scalability and congestion in high mobility. As each node maintains routing information about any possible destination in the network, the overhead of the protocol is quite high. Also a lot of this is wasted as majority of the routes are not used at all. Also at high mobility, the routing updates are very frequent, congesting the network and eating up the scare network resources like bandwidth, battery power etc. - In cases of high mobility, its possible for DSDV to fail to converge, as is shown in some later comparison works. Also DSDV is not completely free of routing loops as is claimed by the author. - The authors have suggested many ideas to patch up some deficiencies of the protocol. eg. determining which route changes are more significant, reducing the frequency of updates in congestion etc. But these are presented vaguely and no evaluation is done. - There are no simulations done. Hence there is no way to tell how the protocol will perform in practical cases. The protocol seems to depend a lot on the "appropriate" choices of parameters and it is not known if this can be done adaptively and distributedly. From ranveer@CS.Cornell.EDU Tue Oct 2 11:20:36 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 f92FKao19145 for ; Tue, 2 Oct 2001 11:20:36 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 18 Date: Tue, 2 Oct 2001 11:20:36 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301FEA216@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 18 Thread-Index: AcFLVck0a2XR5xefQbygAI5zYSgBhw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f92FKao19145 Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV) for Mobile Computers This paper proposes a new routing scheme for ad hoc networks. The routing is distance-vector based and proactive. Nodes maintain an O(N) routing information. Overall the working of the algorithm is very much similar to the other DBF-based routing algorithms, except for a new concept of Destination-based sequence numbers. This is the main contribution of this paper. These sequence number maintain a logical ordering between updates, and help DSDV in avoiding loops. Overall, this is a seminal work and seems to have been among the first papers on routing in ad hoc networks. It details the problem of routing in ad hoc networks and presents a scheme for doing so. DSDV is a simple protocol that introduced the usage of sequence numbers for loop avoidance. DSDV also looked at route instability in ad hoc networks and has a scheme for damping fluctuations. DSDV suffers from all the disadvantages of a proactive protocol: the extra protocol overhead. Besides, the huge amount of exchanged messages and the message size drastically reduces its scalability. The authors use a broadcast wireless medium for communication, which is very unreliable. Its affect on the protocol needs to be studied. Besides, there are other factors, such as the periodicity of broadcasts and ratio of 'full dumps' to 'incremental notification' which affect the protocol, and this should have been studied. Basically, a simulation of the protocol would be helpful. From jcb35@cornell.edu Tue Oct 2 11:27:42 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 f92FRgo19945 for ; Tue, 2 Oct 2001 11:27:42 -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 LAA23997 for ; Tue, 2 Oct 2001 11:27:39 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f92FUlY13915 for ; Tue, 2 Oct 2001 11:30:47 -0400 Date: Tue, 2 Oct 2001 11:30:46 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU Subject: 615 paper 18 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII DSDV is another routing protocol for ad-hoc networks that uses distributed bellman ford routing mechanisms with some enhancements that prevent loops to produce a routing algorithm for highly mobile networks. The paper starts with a description of the Distributed Bellman-Ford (dbf) and RIP algorithms and pointing out the counting-to-infinity and and short and long lived loops problems that each has. To solve these problems, each node periodically broadcasts its routing table with the following information per route: the destination address, number of hops to destination, and the sequence number of the info received regarding the destination. As indicated by the name of this algorithm, the sequence numbers play a vital role in preventing loops and updating routes. These sequence numbers, usually chosen by the destination, allow the nodes to choose the optimal path by picking the route with the highest sequence number and then the lowest number of hops. Broken links are indicated by a value of infinity, and sequence numbers generated by nodes with a broken links always take on an odd value - this way, any real sequence number will supersede an infinity metric. Conversely, sequence numbers generated by the destination node take on an even value. I assume they have methods for dealing with node resents (like remembering sequence numbers only for a certain time period). They also present methods for dealing with fluctuations by storing information about "settling time" with each route. comments: I'm not convinced that the complexity of this algorithm is O(n) with all the broadcasts going on and the way the link updates propagate. This seems to be an early paper (preceding dsr and aodv) and there isn't any simulation result, which is usual for papers presenting a new idea in the field, but it does make a good start at solving some problems that come up in mobile ad-hoc networks. From c.tavoularis@utoronto.ca Tue Oct 2 11:53:40 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 f92Freo23823 for ; Tue, 2 Oct 2001 11:53:40 -0400 (EDT) Received: from webmail2.ns.utoronto.ca ([128.100.132.25] EHLO webmail2.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 62370]) by bureau6.utcc.utoronto.ca with ESMTP id <238609-21217>; Tue, 2 Oct 2001 11:53:34 -0400 Received: by webmail2.ns.utoronto.ca id <24411-13844>; Tue, 2 Oct 2001 11:53:22 -0400 To: COM S 615 Subject: 615 PAPER 18 Message-ID: <1002037990.3bb9e2e6b3cab@webmail.utoronto.ca> Date: Tue, 02 Oct 2001 11:53:10 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT User-Agent: IMP/PHP IMAP webmail program 2.2.3 Out of existing routing algorithms, distance vector algorithms have proven to be most suitable for ad hoc routing since they require less bandwidth and storage overhead. This paper presents the distance vector algorithm called Destination-Sequenced Distance-Vector Routing (DSDV) which employs a Distributed Bellman-Ford (DBF) algorithm for shortest path routing and corrects problems such as counting to infinity and loop-formation by associating sequence numbers with routing packets. In DBF, each node stores the next hop and the distance of the shortest path to every other node in the network. Therefore, the size of route tables is equal to the number of nodes in the network. Nodes maintain and update routing information via periodic broadcasts of all known paths to each of their neighbors. DSDV adapts DBF to mobile networks by adding support for dynamically changing topologies. In addition to periodic broadcasts, which are delayed, each node will broadcast a change in link state as soon as it is detected. Broken links are indicated by infinite length and each node will update its route table accordingly. Nodes are required to store additional routing information, specifically sequence numbers indicating the freshness of each path. Sequence numbers, generally even, are uniquely assigned by the destination, except when a link failure occurs and the detecting node immediately broadcasts the news with an odd sequence number. DSDV also avoids continuing retransmittal of routes caused by receiving unstable-route information or out of order updates. This is accomplished by having nodes wait for a settling-time before updating their route tables and forwarding the advertisement. Settling time is determined by a maintained weighted average time of route fluctuation of a particular path. The proactive nature of DSDV makes it less suitable for constantly changing mobile environments. DSDV does incur quite a bit of bandwidth overhead since regular broadcasts are necessary to avoid stale routes. The study of bandwidth, energy and storage usage of this protocol is critical. Effectively, it is more efficient than link state algorithms. From gupta@CS.Cornell.EDU Tue Oct 2 12:52:26 2001 Return-Path: Received: from ringding.cs.cornell.edu (ringding.cs.cornell.edu [128.84.96.109]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f92Gq8o01433 for ; Tue, 2 Oct 2001 12:52:25 -0400 (EDT) From: Indranil Gupta Received: (from gupta@localhost) by ringding.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f92Gq8718315 for egs@cs.cornell.edu; Tue, 2 Oct 2001 12:52:08 -0400 (EDT) Message-Id: <200110021652.f92Gq8718315@ringding.cs.cornell.edu> Subject: 615 PAPER 18 To: egs@CS.Cornell.EDU Date: Tue, 2 Oct 2001 12:52:08 -0400 (EDT) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Highly dynamic destination-sequenced distance-vector routing for mobile computers (DSDV), Perkins and Bhagwat. Reviewer: Indranil Gupta This paper presents, DSDV, a proactive distance vector routing scheme. Loops are avoided using destination sequence numbers - a loop cannot exist along any route as the next hop at a node is chosen only if the destination sequence of the downstream neighbor is lower than or equal to this node's sequence number for that destination. The information can be broadcasted piggybacked on the 802.11 beacon messages. The authors show that their scheme requires no internodal coordination, and lower space complexity - better than other protocols such as Bellman-Ford, RIP etc. No experimental results are presented. The idea of destination sequences proposed in this paper has found use in many other routing protocols, such as AODV. Are there other techniques (than destination sequence numbers) that guarantee such loop freedom ? More generally, is there a general class of strategies that can be applied to *any* routing algorithm to ensure that permanent loops are eliminated ? One area of proactive protocols that has not been studied is adjusting the period of beacons that are sent out, based on nearby node movement speed and local topology change rate. This would help make the protocol robust to some threshold level of node movements by piggybacking information on 802.11 messages, and making it kind of reactive (and adaptive in time) when the frequency of topology changes goes above this threshold level. From andre@CS.Cornell.EDU Tue Oct 2 13:08:57 2001 Return-Path: Received: from sundown.cs.cornell.edu (sundown.cs.cornell.edu [128.84.96.20]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f92H8uo03374 for ; Tue, 2 Oct 2001 13:08:56 -0400 (EDT) Received: from khaffy (mail@dhcp99-178.cs.cornell.edu [128.84.99.178]) by sundown.cs.cornell.edu (8.11.3/8.11.3/R-3.6) with ESMTP id f92H8ui06122 for ; Tue, 2 Oct 2001 13:08:56 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.32 #1 (Debian)) id 15oTub-0003xl-00 for ; Tue, 02 Oct 2001 13:04:57 -0500 Date: Tue, 2 Oct 2001 13:04:57 -0500 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Subject: 615 PAPER 18 Message-ID: <20011002130457.A15217@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.3.22i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= DSDV is a variant of Bellman Ford, just adds sequence number to the route to prevent transient lopping and counting to infinity problems. It seems to be loop free (it depends on how they increment the sequence numbers, I didnd't get all the details). There is no indication of the communication complexity, which could be high since they are afraid of it and try to do some cachig to slow downs the number of updates. This might (or even without) rise a problem of latency, thus the nodes would often use old route.