From papadp@ece.cornell.edu Mon Oct 1 19:27:40 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 f91NReo09600 for ; Mon, 1 Oct 2001 19:27:40 -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 f91NSXo05993; Mon, 1 Oct 2001 19:28:33 -0400 Date: Mon, 1 Oct 2001 19:30:14 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-X-Sender: To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 20 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of : "An Efficient Routing Protocol for Wireless Networks," by S.Murthy and J.J.Garcia-Luna-Aceves Panagiotis Papadimtratos papadp@ee.cornell.edu The proposed Wireless Routing Protocol (WRP) addresses the issue of shortest path routing in a dynamically changing network. In particular, the Path Finding Algorithm (PFA), the core of WRP, aims at reducing the control traffic, achieving fast convergence and efficient routing information updates. Consequently, less bandwidth, which, in general is at premium, is consumed and improved responsiveness is possible. The presented here work justifies such a statement with respect to classical distance vector algorithms, as well as ones that require inter-nodal coordination. The former type of algorithms face well- known problems related to (frequent) state changes (e.g., count-to-infinity, loop formation), while the latter may experience long convergence delays due to the necessary message exchanges that could propagate far from the affected network component. In short, the PFA-based WRP tries to mitigate such inefficiencies by providing the nodes (i.e., routers) with information sufficient for inferring the state of the entire path and the rest of the paths that could be affected by a tentative routing decision. Each node advertises (update message) to its neighbors the distance to each destination along with the next- to-the-last hop, i.e., the predecessor (upstream) node of the corresponding destination. Each node maintains a distance table that contains all such distances, as reported by each neighbor, a routing table with the distance vector and the next-hop (successor) and also infers (and maintains) the contents of a link cost table and keeps track of unacknowledged update messages (in message retransmission list (MRL)). The basic idea is that upon convergence, i.e. at the point that the node indeed knows the shortest distance to each other node, the entire shortest path tree can be constructed by backtracking through the routing table with the predecessor node knowledge. Then, given the distance table contents, the weights of the constituent links can be inferred. The inferred information is used to update efficiently the routing table and, secondarily, the distance table. On the other hand, the consistency of received update messages can be checked. As a result, many temporary loop conditions can be eliminated, while the relatively 'strict' successor selection (choose the neighbor that offers the shortest path to the destination and shortest paths to all intermediate nodes of the SP) contributes in decreased interactions with the rest of the paths. In other words, 'chains' of updates are avoided and fast convergence can be achieved. The WRP add-ons that place PFA in the wireless context are related with the Medium Access Control (MAC) layer, the neighbor discovery and the link modeling. Under the assumption of a shared medium, the MAC/Data-Link layer implements reliable FIFO communication via time-outs and re-transmissions, while two nodes establish a link, i.e., are neighbors, if there is bi-directional radio connectivity. Explicit acknowledgements are required not only as a part of the reliable link-level communication but also as a means of connectivity maintenance. If a link is not used for data transmissions, void periodic routing updates serve as hello messages and failure to receive such messages for a small period of time implies that the link is broken. Both the updates and the acknowledgements are grouped in large update messages, while the node maintains a list of unacknowledged updates (to be re-transmitted, in MRL). In conclusion, WRP avoids the communication and the resultant delay imposed by the inter-nodal coordination algorithms (e.g., DUAL, which is deemed the fastest-responding one), achieves loop-freedom (eventually), but it is not clear whether the algorithm is appropriate for a mobile ad hoc network setting. For example, the overhead from hello messages and ACKs for any type of transmission and the proactive routing updates' exchange can be high. The evaluation of the protocol does not provide evidence for the opposite, since sparse wire-line topologies and single failure and 'node-up' events are used to compare PFA (and not WRP) to DUAL, DBF and ILS, algorithms that have not been designed with MANET applications in mind. From eyh5@cornell.edu Mon Oct 1 21:29:01 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 f921T1o21504 for ; Mon, 1 Oct 2001 21:29:01 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id VAA05860; Mon, 1 Oct 2001 21:28:56 -0400 (EDT) Date: Mon, 1 Oct 2001 21:28:56 -0400 (EDT) From: eyh5@cornell.edu Message-Id: <200110020128.VAA05860@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 # 20 An Efficient Routing Protocol for Wireless Networks Shree Murthy and J.J.Garcia-Luna-Aceves This paper introduces the wireless routing protocol (WRP) that is derived from the class of path-finding algorithms (PFAs). Its main objective is to significantly reduce the number of occasions in which temporary routing loops may be formed. By achieving that goal, the algorithm converges to stability faster than the other comparable routing algorithms deployed in the ad hoc network. One of the issues WRP addresses is the counting-to-infinity problem. Like other PFAs, WRP solves this problem by utilizing information rearding the length and second-to-last hop, or predecessor of the shortest path to each destination. Unlike other PFAs, WRP aims to eliminate temporary loops that often come to being before the algorithm converges (i.e., a stable, loop-free path chosen). The simulation results have shown the PFA outperforms consistenly better than DBF, DUAL, and ILS in that regard. WRP also closely relies on its retransmission mechanism to ensure that the overall connectivity of the network is maintained. The update messages are queued in the Message Retransmission List (MRL) for retransmissions for up to a certain number of times. The purpose is to account for any potential hazards that may have prevented a node?s neighbors from receiving or acknowledging the receipt of routing-table updates. The retransmission mechanism adds the premium of allowing the neighbor ample time to receive and update its own routing table; the price to pay in this strategy is the added transmissions of repetitive information. One of the byproducts of implementing WRP is the need to periodically announce a node?s presence to its neighbors of the connectivity. Usually, the presence can be learned by sending routing-table updates when there?s a link-state change in the network, or by acknowledging (ACK) the receipt of update messages from the neighboring node. However, there are occasions that the network is in a stable state, and no frequent updates have taken place for a long time. In this case, a node is required to send a null update message, which contains nothing and acts as a hello message, to its neighbors. In the authors? view, this use of null packets is justified in order to maintain network connectivity amongst its nodal members. However, it is desirable that some kind of useful control information can be transmitted during these periods in order not to waste the bandwidth in vain. From wbell@CS.Cornell.EDU Mon Oct 1 22:05:39 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 f9225do25224 for ; Mon, 1 Oct 2001 22:05:39 -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 WAA13622 for ; Mon, 1 Oct 2001 22:05:35 -0400 (EDT) Subject: 615 PAPER #20 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:19 -0400 Message-Id: <1001988345.2557.3.camel@brute> Mime-Version: 1.0 20) An Efficient Routing Protocol for Wireless Networks, Mobile Networks and Applications This paper is follow-on work to routing post-DSDV. It introduces WRP, an efficient wireless routing protocol for Ad-Hoc network which hopes to reduce the number of places where a temporary loop can occur during routing topology changes. Their goal is a quickly converging PFA (path finding algorithm) that chooses optimal paths a greater percentage of the time. WRP relies on acknowledged broadcasts for updates, where a block of updates or ACKS is sent to neighbors via a single broadcast that specifies the nodes that should be interested and should reply to this message. Each recipient listed in the packet broadcasts an ACK message back to the sender once it has completed its processing. This is a very interesting hybrid as compared to previous protocols, and the effects of it are not shown in their simulation results, as collisions are not computed. The effects of collisions of this broadcast storm on this protocol must be extreme, although more standard backoff techniques could be used to lessen this effect. Their protocol requires local connectivity information, which is either gotten via snooping on packets, or via explicit hello messages when there is no traffic from a host. Links are expired out by a simple timeout scheme. The avoid routing loops by including extra information in the update messages which explicitly lists the predecessor of the shortest path from node i to j gives each node the ability to find the shortest path by examining all the update messages from all it's neighbors concerning an update. The assume reliable update communication, and for which they use message retransmission, which assures that a node i will hear about updates from all of it's neighbors in some amount of time. This reliable update mechanism helps the convergence of WRP in response to a topology change. Their simulations were a bit naive, especially omitting the bandwidth loss due to collisions was a nice touch for a protocol that created very large broadcast storms throughout the network. I think they were more interested in the optimality of paths than anything else, and it pushed hard on them onto a solution that had good optimality guarantees, but very little practical use. From andre@CS.Cornell.EDU Tue Oct 2 01:43:00 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 f925gxo17429 for ; Tue, 2 Oct 2001 01:42:59 -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 f925gxi22844 for ; Tue, 2 Oct 2001 01:42:59 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.32 #1 (Debian)) id 15oJCo-0003hI-00 for ; Tue, 02 Oct 2001 01:39:02 -0500 Date: Tue, 2 Oct 2001 01:39:02 -0500 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Subject: 615 PAPER 20 Message-ID: <20011002013902.A14190@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.22i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= An Efficient outing Protocol for Wireless Networks. The algorithm is really neat. No, it was. I don't understand it anymore. I'm wondering if the writers don't assume knowledge of the kind of algorithms (path findings), and reading the source algorithm papers could be usefull. The idea is to store at each node the shortest distance, the next hop and the previous one to a given destination. (Note, when they say second to last, I assume it to be the one before me, not the one before the one before, me which I beleive to be the correct meaning.) That predecessor means you are going to avoid the transient loops (or only same?), the table means you can reconstruct the whole route. Concerns: what exactly is the predecessor (why cannot there be several ones, or no one when the route starts at yours?) I didn't get the proof of Property 1 (what are those concatenation of links?) and then gave for the proofs. Communication complexity: not said, I would say O(nT) where T is the height of the tree and n the number of nodes. Note that you can route from anywhere to anywhere. Seen like that, the number of messages shown in the results are not that bad, even if the experiments are done on small number of nodes. Idea for simulations: fully connected graph, progressive failures and recovery of links to modelise mouvement. Can a specific patern by used? -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From daehyun@csl.cornell.edu Tue Oct 2 11:01:13 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 f92F1Do16831 for ; Tue, 2 Oct 2001 11:01:13 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id LAA45385 for egs@cs.cornell.edu; Tue, 2 Oct 2001 11:01:08 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200110021501.LAA45385@wilkes.csl.cornell.edu> Subject: 615 PAPER 20 To: egs@CS.Cornell.EDU Date: Tue, 2 Oct 2001 11:01:08 -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 Wireless Routing Protocol (WRP), which reduces temporary routing loops, so converges quickly. WRP is based on Path Finding Algorithms (PFA). The main idea PFA is that each node maintains the shortest path spanning tree reported by its neighbors. A node constructs the shortest path spanning tree using the the spanning trees of neighbors and the link costs to neighbors. Updates messages containing the sender's spanning tree information are exchanged between neighbors. PFA has a problem of temporary loops, so it converges slowly. WRP solves this problem. When a node receives a update message or finds a link status change, it updates the routing table. Here, PFA checks the consistency of the predecessor only for the corresponding neighbor, while WRP checks for all the neighbors. This eliminates more temporary loops and make WRP converge fast. Actually, I couldn't understand this point enough. Each node maintains four tables - distance table, routing table, link-cost table and message retransmission list. 1. Distance Table: this table contains the distance and the predecessor to each destination for each neighbor of the node. 2. Routing Table; this table contains the distance, the predecessor and the successor to each destination for the node. 3. Link-cost Table: this table contains the link cost for each neighbor of the node. 4. Message Retransmission List: This table contains retransmission messages. I think the main contribution of this paper is that WRP solves the slow convergence problem of PFA. As indicated in the paper, the previous algorithms has their own weakness. Some requires global network information exchange or internodal coordination, so they demands high overhead of multi-hop communication, which is not suitable for wireless networks. Some others takes long time to converge, which can not deal with the frequent topology changes of ad hoc networks. another algorithm which gives a solution to those problems is PFA, and WRP enhances PFA. From haom@csl.cornell.edu Tue Oct 2 11:06:29 2001 Return-Path: Received: from mauchly.csl.cornell.edu (mauchly.csl.cornell.edu [132.236.71.68]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f92F6To17411 for ; Tue, 2 Oct 2001 11:06:29 -0400 (EDT) Received: from localhost (haom@localhost) by mauchly.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id LAA77944 for ; Tue, 2 Oct 2001 11:06:23 -0400 (EDT) (envelope-from haom@mauchly.csl.cornell.edu) X-Authentication-Warning: mauchly.csl.cornell.edu: haom owned process doing -bs Date: Tue, 2 Oct 2001 11:06:23 -0400 (EDT) From: Ming Hao To: egs@CS.Cornell.EDU Subject: 615 PAPER 20 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII An Effecient Routing Protocol for Wireless Networks by Shree Murthy and J.J. Garcia-Luna-Aceves the paper thinks PFA is promising because it has not counting to infinity problem and can tries to reduce the cases where temporal loop will form. i skipped most of provement. here is the general idea how 1. every node maintains distance table which includes info distance from neighbor to destination and its predecessor.(this is the unique feature of PFA). routing table storing distance, succesor and predecessor and a markerfor updating purpose. link cost table and message retransmission list. 2. when recieving a update, nodes updates its distance table. it also check if this update affects other neighbor nodes and update corresponding entries. the nodes select one of neighbor as its predecessor if that node rpovides shortest path among all its neighbors. ( i think it made a mistake by saying "node i chooses node p as its successor") 3. Link-Cost Changes can be detected by hello messages. i got a feeling that the PFA algorithms sacrifise the the sequencing in the DSDV with possible loop cases in order to achive a fast convergence. simulation: though in the beginning, the paper mentioned disadvantages of many algorithms, including better ones such as DSDV. but in th end, it compares only with DBF , DUAL and ILS. but both DBF and ILS suffer loop problems, while DSDV not. DUAL, as the paper mentioned, uses explicit synchronization though loop free. so the simulation result is not that convincing. not mention that loops still come up in some casese. -ming Ming Hao PH.D Candidate, EE mh97@cornell.edu Cornell University Office: (607) 255-0817 Ithaca, NY 14853 http://www.ee.cornell.edu/~haom/ From teifel@csl.cornell.edu Tue Oct 2 11:25:06 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 f92FP6o19670 for ; Tue, 2 Oct 2001 11:25:06 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f92FP1b09071 for ; Tue, 2 Oct 2001 11:25:01 -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 11:25:01 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 20 Message-ID: <20011002112416.D96977-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII WRP: This paper presents the wireless routing protocol (WRP). In this protocol nodes communicate the distance and second-to-last hop information for each destination. WPR reduces the transient loops, increasing its convergence time. I'll assume that the protocol specification (figure 1) is correct. WPR is based on path-finding algorithms, but is modified to avoid loops and limits routing table updates to include only those entries affected by the changing network topology. Routing information includes the identifier of the sending node, a sequence number assigned by the sending node, an update list, and a response list. As standard in most of these types of routing protocols, periodic hello messages must be sent. When a link fails or a link-cost changes, the distances and predecessors to all affected destinations are recomputed and the new information is broadcast to affected nodes. This could possibly waste bandwidth if a particular transmission route is rarely or never used. Their proof of correctness is interesting, but it relies on reliable transmissions and perfect routers--something that may not be realistic in practice. Not really sure what to make of the simulation section. They didn't actually simulate the WRP protocol, but rather a simplified protocol (PFA) from which it was based on. This, I believe, discredits the authors claim that WRP is better than previous state-of-the-art protocols. WRP may in fact be better, but the simulations that they show do nothing to convince me of that fact. [ I generally dislike commenting on the quality of the writing (as in theory it shouldn't matter), but this paper was much easier to understand than the DSDV paper we also read for this week. ] From ramasv@CS.Cornell.EDU Tue Oct 2 11:37:42 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 f92Fbgo21650 for ; Tue, 2 Oct 2001 11:37:42 -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 20 Date: Tue, 2 Oct 2001 11:37:42 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F273@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 20 Thread-Index: AcFLWCyfuygbFyUwRdOLF8PbukPiyg== 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 f92Fbgo21650 An Efficient Routing Protocol for Wireless Networks This paper presents WRP (wireless routing protocol) which is a proactive distance vector based protocol that finds shortest routes among nodes in an ad hoc networks. WRP also maintains route tables at each node containing route information to all the destinations in the network. Each node is escpected to share this information with all its neighbors by means of periodic broadcasts. A PFA (path finding algorithm) based approach that uses predecessor (one hop before the destination) to prevent couting to infinity and temporary route loops is used as an underlying scheme. The main contributions of this paper include an ACKing scheme for the neighbor-cast and a really long winded proof to justify the correctness of this PFA scheme. WRP is an implementation of the distributed belmanford algorithm with a few modifications. In addition to broadcasting the number of hops to each destination, each node also broadcasts the ID of the node one hop before the destination (predecessor). Every node then maintains in its routing table additional table that includes this predecessor information it received from each of its neighbors. This way each node can locally compute a spanning tree to each destination. Whenever a route update (broken route or shorter route) is received this spanning tree is consulted for a consistency check thus preventing the formation of temporary loops in the network. This scheme also avoids the couting to infinity problem. Periodic broadcasts sent to the neighbors need to be independantly acknowledged by all the neighbors. Thus each neighborcast message also includes a list neighbors that have not yet acknowledged the packet. The packets are re-broadcast as long as all the neighbors have not acknowledged. This scheme of guaranteeing reliability seems very inappropriate to ad hoc networks. The first neighborcast is bound to result in an ack implosion problem causing collision of all the acks. This could possibly repeat everytime. The alternative is to make each node acknowledge only by piggy backin on the periodic hello/update packets. This would delay the ack and increase the latency of spereading the information. The PFA is a very useful scheme to prevent couting to infinity and looping problems of the DBF algorithm. This protocol suffers from problems that afflict other proactive protocols such as scalability, specification of periodic interval, excessive traffic generation, large state space etc... The simulation performed shows a proof of concept for the PFA scheme. The simulation assumes an unrealistic channel model and excludes the imact of neighbor discovery and ACK schemes making the simulations inadequate. From c.tavoularis@utoronto.ca Tue Oct 2 11:48:48 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 f92Fmmo22942 for ; Tue, 2 Oct 2001 11:48:48 -0400 (EDT) Received: from webmail2.ns.utoronto.ca ([128.100.132.25] EHLO webmail2.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 53018]) by bureau6.utcc.utoronto.ca with ESMTP id <238628-21211>; Tue, 2 Oct 2001 11:48:20 -0400 Received: by webmail2.ns.utoronto.ca id <24411-13844>; Tue, 2 Oct 2001 11:48:07 -0400 To: COM S 615 Subject: 615 PAPER 20 Message-ID: <1002037687.3bb9e1b70ae88@webmail.utoronto.ca> Date: Tue, 02 Oct 2001 11:48:07 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper provides an improvement to path-finding algorithms (PFA) called Wireless Routing Protocol. It finds the shortest-path spanning tree while reducing communication overhead and the risk of temporary loops. Each node maintains routing information in four tables: distance, routing, link- cost and message-retransmission. The routing table will also tag paths if there is a loop. The link-cost table will mark broken links with infinity. The message-retransmission list keeps track of update messages to be sent to a node’s neighbors. Each update message is associated with a sequence number, and the node will keep track of received acknowledgements to determine which updates were not received and need to be retransmitted. Update messages consist of the sender’s id, a sender assigned sequence number, an update list (or ACK) and response list. The update list contains new network status information including the distance and predecessor to a destination, and the response list identifies which nodes should respond with an ACK. When there are no updates to be sent, a node will continue to broadcast messages periodically to ensure connectivity. Each node keeps track of its immediate neighbors through periodic hello messages. If a node no longer receives hello messages from a certain neighbor over some time, it can presume the link has failed (or the node has moved away). Similarly, if a hello message from a new neighbor arrives, a node can include the new link in its own tables. Therefore WRP does not rely on lower layers to determine connectivity. A node will revise its routing table upon receiving an update, or upon detecting a change in link status with a neighbor. WRP improves PFAs by having each node check routing consistency with each of its neighbors. This allows for faster convergence, and causes less temporary loops. PFA was evaluated and compared to DBF, DUAL, and ILS. These algorithms were simulated for messaging overhead in the event of link failure and recovery. PFA was shown to have low messaging overhead and quick convergence, thus preserving bandwidth and reducing delay. Assuming no collisions reduces the effectiveness of the simulations. One drawback of WRP is periodic hello messages which consume variable resources including bandwidth and energy. From ranveer@CS.Cornell.EDU Tue Oct 2 11:56:15 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 f92FuFo24352 for ; Tue, 2 Oct 2001 11:56:15 -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 20 Date: Tue, 2 Oct 2001 11:56:15 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301FEA217@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 20 Thread-Index: AcFLWsQxJPOCfeHDSuKqwZL6NPE6Aw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f92FuFo24352 An Efficient Routing Protocol for Wireless Networks This paper proposes a Path Finding Algorithm(PFA) for routing in ad hoc networks. The algorithm, called WRP, is a typical PFA with added properties of faster convergence and no temporary routing loops. It uses periodic messages( or beacons if there are no messages) to establish connectivity. Temporary loops are avoided by efficiently handling the updates and acks. This also leads to a faster convergence. A correctness proof of WRP is also presented along with the complexity analysis. A very rough simulation is also presented, which is excusable given the time when this paper was written. The first cnfusing point of this paper was the reference of WRP as a "Wireless Routing Protocol". Special properties of manets have not been considered except for each node being a router and mobility of nodes. Other parameters, such as scarcity of bandwidth, unreliable communication, limited memory have not been taken into account. Even in the simulation, the results are compared with DUAL, ILS and DBF. None of these routing algorithms have been designed for wireless networks. A comparison with DSDV would have been more appropriate. The correctness proof shows that under ideal conditions, WRP is loop-free and converges fast. In fact the more important question would be that under normal wireless conditions(and this is far from ideal), how good does WRP perform?? For example, how does WRP handle flaky links? WRP suffers from the disadvantages of proactive protocols: protocol overhead. The advantage is the faster response time. From samar@ece.cornell.edu Tue Oct 2 12:22: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 f92GMPo27766 for ; Tue, 2 Oct 2001 12:22: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 f92GNFo24330 for ; Tue, 2 Oct 2001 12:23:15 -0400 Date: Tue, 2 Oct 2001 12:22:22 -0400 (EDT) From: Prince Samar X-Sender: samar@ockham.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 20 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 20) An Efficient Routing Protocol for Wireless Networks This paper introduces the Wireless Routing Protocol (WRP) which is a proactive (or table-driven) routing protocol. In WRP, nodes broadcast updates containing the distance and the second-to-last hop for each destination. WRP is based on a path finding algorithm (PFA), which constructs a shortest path spanning tree based on the shortest path spanning tree of its neighbors as advertised by them and the cost of adjacent links. This helps in substantially reducing the number of cases in which routing loops can occur. The correctness of WRP has been proved and its complexity has been analyzed in the paper. Each node maintains a distance table, a routing table, a link-cost table and a message retransmission list. In addition to broadcasting the number of hops, a node also broadcasts predecessor (node one hop before the destination) information. Maintaining this information for each of the destination makes it possible for each node to construct the spanning tree. Later if a node receives any update, it checks its consistency against the spanning tree. This helps in avoiding the problems of looping and count-to-infinity. Acknowledgments are required from each neighbor whenever a message is sent to them. A list is maintained for the nodes which are supposed to acknowledge in the near future. A message rebroadcast is performed if no ack is received in some time. Even if a node does not have any information to share, it should send a HELLO message informing its neighbors about its presence. Comments: - WRP has been able to eliminate to a good extent some of the problems associated with other table-driven protocols: routing loop formation and count-to-infinity. They also provide a proof of correctness and complexity analyses of the algorithm. - WRP, being a proactive protocol, suffers from the problems associated with using proactive protocols for ad hoc networks: high overhead and wastage of resources, low scalability, appropriate choice of parameters etc. At the same time, it has low latency: routes are available as soon as requested. - Though requiring acks for each of the updates increases the reliability, it has the disadvantages of increased traffic, collision of acks from the neighbors(which ack at about the same time) and repeated transmission of updates by the source etc. - The simulations assume an ideal channel where a packet sent over a valid link will be received error free. Also acknowledgments and neighbor connectivity messages have been eliminated. This helps in reducing the complexity of the simulation but does not give a real picture as some of these factors could affect the performance of WRP which has not been analyzed. 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 f92GqMo01443 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 f92GqMU18322 for egs@cs.cornell.edu; Tue, 2 Oct 2001 12:52:22 -0400 (EDT) Message-Id: <200110021652.f92GqMU18322@ringding.cs.cornell.edu> Subject: 615 PAPER 20 To: egs@CS.Cornell.EDU Date: Tue, 2 Oct 2001 12:52:22 -0400 (EDT) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit An efficient routing protocol for wireless networks, Murthy and Garcia-Luna-Aceves. Reviewer: Indranil Gupta This paper proposes (yet another) routing protocol, very imaginatively named the Wireless Routing Protocol (WRP). The protocol is proactive in adapting to changes. Each node maintains, for each destination, the (best) next hop from each of n's neighbors to the destination, and the cost (length) of the route. The proactivity of the protocol means that the information can be piggybacked on the 802.11 beacon messages. The authors guarantee "eventual loop freedom" once the topology stabilizes. However, if the topology keeps changing at some rate that always beats the repair mechanism (this rate is closely related to the period of beacons), any packet sent into the network might live until its TTL expires, and never reach the destination. This will overload the network with useless packets. Notice that this rate of topology change might be well *below* the rate at which flooding might be the only option to send a message. Possible solutions to these are a) adjusting the period of beacons based on local topology change rate information, or b) implementing a loop detection scheme that will eliminate looping packets quickly. The authors present simulation results that show that WRP (which is simplified, and magically and thankfully renamed even more imaginatively to "Path finding algorithm" - PFA), when compared to DUAL, ILS and DBF, sends fewer messages and converges quickly. The authors verify this on a number of topologies such as ARPANET, nsfnet, Los-nettos. From jcb35@cornell.edu Tue Oct 2 14:26:50 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 f92IQno13429 for ; Tue, 2 Oct 2001 14:26:49 -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 OAA02968; Tue, 2 Oct 2001 14:26:46 -0400 (EDT) From: jcb35@cornell.edu Date: Tue, 2 Oct 2001 14:26:46 -0400 (EDT) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 20 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper documents wrp (the wireless routing protocol), a routing protocol for use in mobile ad-hoc networks. It aims to solve the routing loop problems in dbf (distributed bellman ford) and achieve fast convergence properties. Similar to paper 18, this paper starts of by documenting other proposed routing protocols, including dbf and dsdv, and pointing out the shortcomings of them that wrp will try to overcome. (ie. loop avoidance for dbf and latency problems in dsdv). wrp uses a path finding algorithm at each node to maintain the shortest path spanning tree from information obtained from and about its neighbors. Each node maintains this information in a distance table, a routing table, link-cost table, and a message retransmission list. Using these, a node can know which updates of an update message it has seen. The nodes use hello messages periodically broadcasted to update connectivity. The authors claim that wrp achieves quicker convergence to the correct routing information due to the fact that each node checks the consistency of information reported by all its neighbors each time it processes an event involving a neighbor. They also use sequence numbers for updates to ensure that correct updates are being processed. comments: - I'm not for sure that wrp achieves quicker convergence to the correct routing information - if it does, I wonder how many extraneous packets it sends out in the process. Would it be better to not worry, but then find out only when you need to? - I wonder if the acks are necessary with the link-level protocols that have been developed since the paper. - I wish they would have compared its performance with dsdv - this seems the obvious choice to compare results to and makes me question why they would not have. - Also, I'm not as sure that the algorithm achieves loop freedom much faster than other algorithms - especially if the network is extremely mobile.