From haom@csl.cornell.edu Sun Sep 16 23:37:55 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 f8H3bsq03788 for ; Sun, 16 Sep 2001 23:37:54 -0400 (EDT) Received: from localhost (haom@localhost) by mauchly.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id XAA24380; Sun, 16 Sep 2001 23:37:48 -0400 (EDT) (envelope-from haom@mauchly.csl.cornell.edu) X-Authentication-Warning: mauchly.csl.cornell.edu: haom owned process doing -bs Date: Sun, 16 Sep 2001 23:37:48 -0400 (EDT) From: Ming Hao To: egs@CS.Cornell.EDU cc: mh97@cornell.edu Subject: 615 PAPER 8 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. this paper presents a new algorithms based on fully/partialy reversal method. the way it works is that every node maintain a quintriple as its own height and the hieghts of its neighbors. the lexicographical order of the heights determines the connection of the route. the setup of route involves the broadcasting QRY and UPD msg. every node with NULL height and some downstream links will select the a height which is (a,b,c,d+1,e), while (a,b,c,d,e) is the minum height of its downstream neighbors. the algorithms is on-demand type of algorithms. it does not need to broadcast msg even when route discovery. it can detects partition and erase the invlid route efficiently. it can also provide multiple routing, though it is not mentioned how it is used. this algorithms itself is very good. it works neatly. unfortunately, it has no results to support it. further, it needs some synchronization mechanism to order the events. follows are tow more comments. 1.the paper describes the algorithms based on one destination and mentioned there are several seperate logical aoperations for multiple destination. my question is how to take advantage of info about other destination in order to set up a route for a new destination. if all destination is created seperately, it defintely waist both bandwidth and CPU time. 2. there is an error in Figure1. node D should point to node B 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 wbell@CS.Cornell.EDU Mon Sep 17 21:14:49 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 f8I1Emq19624 for ; Mon, 17 Sep 2001 21:14:48 -0400 (EDT) Received: from [192.168.1.101] (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 VAA26763 for ; Mon, 17 Sep 2001 21:14:44 -0400 (EDT) Subject: 615 PAPER #8 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.13.99+cvs.2001.09.17.18.33 (Preview Release) Date: 17 Sep 2001 21:14:19 -0400 Message-Id: <1000775687.2860.1.camel@brute> Mime-Version: 1.0 8) A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks This paper presents a routing protocol called TORA (the Temporally-Ordered Routing Algorithm) which is a link reversal algorithm that's suited for large, dense, mobile networks. An interesting property of this algorithm is that it keeps multiple paths to each destination, which favors connectivity of the network over optimality of the communications paths. The goal of TORA was to have very reactive routing that does not propagate link failures globally, which leads to lower communication overhead and better scalability. The three primitives in TORA are the QRY (Query), UPD (Update), and CLR (clear) messages, which are used to find a route, update a route, and remove a route, respectively. Query messages establish routes via a route broadcast which is similar to a diffusing computation (The responses are via update messages.) TORA does updates via a link reversal mechanism, where at each point, messages are propagated to links which are currently considered to be downstream (outbound.) By reversing upstream and downstream links during updates, they can pass messages in ways such that they can determine network partitions and propagate link updates. Clear messages are used to propagate information about network partitions, via a local broadcast to downstream links, which informs the receiving host to remove links in it's tables for the partitioned nodes. This paper seemed to grasp a concept that some of the other algorithms have missed, which is that for a scalable network, it is in-feasible to have all nodes be alerted to a single node failure. They seem to have captured this idea well with TORA, which should do very well with respect to stability during link failures without excessive communication overhead. I felt the algorithm achieved it's goals, although I was not convinced that a simpler algorithm would have achieved the same goals. There were many singleton state bits that I couldn't quite pin a real use for, and only seemed to have well defined uses in certain situations. The notion of multiple routing paths would seem to provide much greater connectivity and much better tolerance to link failures, however, this is at the cost of route optimality, which is not adequately discussed in this paper. My intuition is that the routes generated in these dense networks would tend to be quite close to optimal ones, however a better discussion of it would have been good. From avneesh@csl.cornell.edu Tue Sep 18 00:02:39 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8I42dq05696 for ; Tue, 18 Sep 2001 00:02:39 -0400 (EDT) Content-Class: urn:content-classes:message Subject: 615 Paper #8 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Tue, 18 Sep 2001 00:07:17 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <97C142C1212ED545B0023A177F5349C4053A87@capricorn.ds.csl.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper #8 Thread-Index: AcE/92eWXWos70zaSsupiL77+5XJDQ== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8I42dq05696 A Highly adaptive Distributed Routing Algorithm for MObile Wireless Networks. Paper Summary This paper describes the design of a Temporally-ordered routing algorithm (TORA), the name of which arises from the relative ordering of time tags which match the route update events which occur within the network. The main aim of the protocol is to reduce far-reaching control message propagation across the network when a topology change event occurs. The protocol addresses the inherent problems of using the conventional protocols for a connected network, in a wireless network. The points which are interesting are that the protocol aims towards loop free routes, multiple routes and reduction of congestion as well as communication overhead instead of emphasizing on route optimality. Furthermore, the protocol can tolerate k/2-1 downstream failures for k nodes with average of k/2 downstream links, without requiring any reaction within the network. This is significant in a highly dense/connected network, where such responses could be widely propagated. The routing primitives in the protocol are the QRY, UPD and CLR messages which are used for route management. Query messages are sent by a node which requires a route and forwarded by nodes, which at that point do not have valid route themselves. The main idea is to use a destination rooted DAG, where the destination node has the lowest height of all nodes. Updates are done using link reversal where messages are sent to the upstream node to create a downstrea, link if a downstream link to the destination from the current node exists. Network partitions can also be detected, by carrying out a novel route mantainence algorithm. Another interesting action is that redundant routes which exits in a partioned network are quickly erases through this link reversal mechanism. Nodes are required to mantain some state in form of neighbor height and link state tables to manage the route information. It has also been shown that temporal ordering does not depend on the absolute values of the time tags, as long as they are in the correct order. I think that paper is extremely well written, and since I have not read many other papers for mobile network routing, I felt that the route management approach was quite novel. It would be very interesting to see how the protocol performs in the simulations and how the presence of soft state messaging etc as well as network desnity effects its performance. From daehyun@csl.cornell.edu Tue Sep 18 01:07:37 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 f8I57aq12418 for ; Tue, 18 Sep 2001 01:07:36 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id BAA23564 for egs@cs.cornell.edu; Tue, 18 Sep 2001 01:07:31 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109180507.BAA23564@wilkes.csl.cornell.edu> Subject: 615 PAPER 8 To: egs@CS.Cornell.EDU Date: Tue, 18 Sep 2001 01:07:31 -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 Temporally-Ordered Routing Algorithm (TORA), which guarantees loop-free and multiple routes for any source/destination pair. The main design point of this algorithm is to minimize reactions to topological changes. It decouples the generation of control message propagation from the rate of topological changes, thus topological changes are localized to a small subset of the network. This property gives TORA an adaptiveness to frequent topological changes and further scalability. Each node of the network maintains the following information; 1. H: The height of the node as defined by two parameters - a reference level and a delta. 2. NH: An array of the heights for all neighbors. 3. LS: An array of the link status for all links to neighbors. The protocol is composed of three basic functions; 1. Creating Routes: Multiple routes are created by this function. Basically, it creates flows from the source to the destinations through every possible paths. 2. Maintain Routes: If there happens a topological change, routing information is updated by this function. there are 5 cases - Generate, Propagate, Reflect, Detect, Generate. 3. Erase Routes: If a partition is detected by the above Maintain function, corresponding routes are deleted by this function. In my opinion, TORA has the following strength and weakness. Strength. 1. Localization. As specified in the paper, TORA localizes topological changes to subsets of the entire Network. So, a link failure or addition does not require control messages to be propagated through the entire network. as a result, TORA is more adaptive and scalable than others, which is crucial for wireless ad hoc networks. 2. Multiple Paths. Other algorithms generally find a single shortest path. So the path might be congested, or if the path fails, a new path should be found by re-initiating another path-recovery algorithm. However, TORA finds multiple paths, which provides flexibility to cope with congestion or link failure. Weakness. 1. Synchronization. TORA is based on synchronized time stamp. Actually, event synchronization is a hard problem in distributed systems, almost as hard as routing itself. Though this paper explains the effect of the synchronization problem, I think, more analysis should be given and synchronization overhead should be considered in simulations. 2. Shortest Path. TORA does not guarantee the shortest path. It find multiple paths, which may or may not include the shortest path. And it does not provide any information about which path among them should be chosen. Though this paper argues that the shortest path doesn't matter much and I generally agree, the best route selection method might be a interesting topic as a future work. 3. Simulation. Simulation results are missing. (it is said that simulations are underway.) From andre@CS.Cornell.EDU Tue Sep 18 01:26:17 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 f8I5QGq14124; Tue, 18 Sep 2001 01:26:16 -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 f8I5QGi17146; Tue, 18 Sep 2001 01:26:16 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.32 #1 (Debian)) id 15jEHr-00042Z-00; Tue, 18 Sep 2001 01:23:15 -0500 Date: Tue, 18 Sep 2001 01:23:15 -0500 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Cc: andre@CS.Cornell.EDU Subject: 615 PAPER 8 Message-ID: <20010918012315.A15518@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.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= This protocol (called TORA) is designed for dense ad hoc networks. The idea is, for each *destinationto* to define the heigh of each node, the destination being at 0. Any route from a node to another one with a smaller height is valid and will enventually reach the destination. This means having different for the same destination which avoid congestion, the necessity of setting up a new route when the current fails, and usually keeps changes local (only about the neighboors are kept) When a node has no route left to a destination (it is a local minimum), it jumps just high enough to be a local maximum, and the "hill" propagates to the adjacent nodes if this needs to be. The hill is going to grow until the flow from our current node can go finds a way out and join a river going down to the destination. If this doesn't occur, then the network is partitionned and the source node is notified because it is asked to go higher. The scheme to set up routes is devised in the paper. Basically a route for a destination is only created only when needed, but all the nodes will end up having a height, and so a routes for that destination. Drawbacks: when a node realize that it doesn't know how to route, even if it wasn't used for routing, will try to find a new route. Also the routes might be the shortest at the beginning, they might end up being like some slow running rivers (because only the next hop is known). The algo is loop free, but needs a temporal ordering which might not always be maintained. I am wondering if there isn't a way of creating loops like that. (Nothing is said about loss of packets). The worst complexity is nice (beheavies nicely when the network partitions). No studies are done on average. I think that is should be quite when the net is dense (how dense is the question). An improvement would might be not to try to repair broken routes until they are used (which quite likely not to happen since there are many - I have the feeling that local changes on the left side will infer local but unnecessary local changes when say routing from the center to the rigt. Last, nothing is said when the high reaches max_height. Peiodical refresh pakets could solve that as well as loops and improve the performances of route. How costly however? Last, nothing is said when the high reaches max_height. Peiodical refresh pakets could solve that as well as loops and improve the performances of route. How costly however? -- 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 viran@csl.cornell.edu Tue Sep 18 01:47:21 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8I5lKq15906 for ; Tue, 18 Sep 2001 01:47:20 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8I5lFx41817 for ; Tue, 18 Sep 2001 01:47:15 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Tue, 18 Sep 2001 01:47:15 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 PAPER 8 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper introduces TORA, an interesting ad-hoc on-demand routing algorithm rather different from the ones we've seen before. In particular, it doesn't attempt to maintain shortest paths in the presence of topology changes, thus avoiding a lot of network update messages to many nodes, and the need to flood the network. This also allows it to maintain multiple paths for a given source destination pair which provides automatic redundancy in the presence of link failures. TORA's information routing is analogous to how a liquid would travel down a slope from the source at the top to the destination at the bottom. It maintains a "height" for each node between a given source-destination pair thus forming a gradient that directs information in the correct direction. All the nodes are completely ordered (no two nodes may have the same height) which ensures that loops cannot occur. TORA does require additional hardware in terms of a global clock for synchronization, or at least the use of distributed clocks. TORA uses link-reversal to propagate information about topology changes and network partition detection. Thus, when a node loses all its downstream links, it reflects its upstream links (which in turn may be reflected) until a connection is made with a different path, or a partition is detected. This means that during topology changes, there is no need to send global updates about the changes; only the miniumum required number of nodes in the vicinity will detect the changes. This paper was very interesting to read, as it presented a rather novel approach to network routing. Although the simulation and evaluation section was lacking, I felt that the interesting ideas presented made up for it. One comment I have is that too little mention was made of how packets would actually be routed; most of the paper dealt with maintaining network topology information. Since there are multiple paths to a destination how does it pick which path to transmit on? Also, the paper's main goal appears to be to reduce the bandwidth requirements for maintaining routing paths for large and dense networks at the expense of of (possibly) longer latency on message transmission. It remains to be seen at what critical number of nodes this tradeoff will show benefits. Perhaps a sensor dust network of hundreds to thousands of nodes would be a good place to evaluate this algorithm, since it seems that something like AODV or DSR would have an advantage in terms of transmission times in a smaller/static topology. From papadp@ece.cornell.edu Tue Sep 18 10:40:31 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8IEeVq10727 for ; Tue, 18 Sep 2001 10:40:31 -0400 (EDT) Received: from mill (mill.ee.cornell.edu [128.84.236.64]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8IEeVi28636; Tue, 18 Sep 2001 10:40:31 -0400 Date: Tue, 18 Sep 2001 10:33:40 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-Sender: papadp@mill.ee.cornell.edu To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 8 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," by V.D. Park and M.S. Corson. Panagiotis Papadimtratos papadp@ee.cornell.edu The proposed Temporally Ordered Routing Algorithm (TORA) aims at a dynamically changing environment by providing on-demand, source initiated route discovery and fast adaptation to topological changes, without focusing on routing optimality. The main design goal of TORA is to minimize the control overhead, by constraining the localized propagation of a topological change to a limited number of nodes. It relies on a data link layer protocol for neighbor discovery and also assumes in-order, reliable message transmission. The protocol discovers, maintains and deletes routes. This last operation is essential for the operation of TORA since it bears similarities to a class of algorithms that operate only on connected networks. The route discovery establishes a sequence of links directed towards the destination and the creation of the route relies on the formation of a directed acyclic graph (DAG), routed at the destination. Given this DAG, the route formation corresponds to assigning directions to the links, or equivalently designating the upstream and downstream nodes. This is performed based on the use of a 'height' metric (which allows the lexicographic ordering of nodes) and the underlying concept is that of link reversals, performed according to positioning on the node in the DAG. Reversals occur only when the node looses all downstream links (i.e., reaches a local minimum, w.r.t. the ordering). This implies that a recalculation will occur only when all downstream links are lost, i.e., only when no route is available for the node in question. In other words, TORA is a protocol that maintains multiple routes to the same destination, as defined by the assignment of link directions, and can make use of all of them. When link failures occur, the last one that caused the loss of the last downstream link will force the node to change its height to a high, globally maximum value, which causes link reversals. The new reference level propagates only through nodes affected by the initial link reversal. As other reversals may also incur, a height adaptation will follow with the newest reference level also propagating. If such a change propagates back to the original route maintenance initiator, then, a partition has been discovered. One can infer that the smaller the number of link reversals that result in the node loosing all its downstream links, the lower the number of reference level updates and the lower the recalculation cost. This can be translated to the statement that the higher the number of downstream links, the less frequently such updates will occur. Consequently, the denser the graph the more suitable is TORA. Furthermore, the localization of the update disturbance and the incurred messaging will cause a relatively lower amortized overhead if the size of the network is large. In short, TORA appears to be more appropriate for dense and large topologies, because of the lower frequency of new route calculations. This is exactly one of the protocol disadvantages, since oscillations may occur due to successive (globally maximum) height adjustments especially when multiple route reconstructions occur. Significant delays may also be imposed due to the detection of partitions, which must be followed by route deletion and extensive recalculations. Practically, the under-construction routes can remain unstable for long periods of time, despite the eventual convergence. Another feature that limits the applicability of TORA is the requirement of clock synchronization, since the height metric depends on the (logical) time of link failure. In essence, a temporal order of the link failures is established the synchronization will require knowledge of the topology change rate, which cannot be known a priori. Thus, an incorrect ordering of failure events may cause severe inefficiencies or complete absence of routing functionality. In conclusion, TORA achieves in its limited context the stated goals, although detailed evaluation under different scenarios is required. From gupta@CS.Cornell.EDU Tue Sep 18 10:40:58 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 f8IEewq10753 for ; Tue, 18 Sep 2001 10:40:58 -0400 (EDT) From: Indranil Gupta Received: (from gupta@localhost) by ringding.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8IEevC03686 for egs@cs.cornell.edu; Tue, 18 Sep 2001 10:40:57 -0400 (EDT) Message-Id: <200109181440.f8IEevC03686@ringding.cs.cornell.edu> Subject: 615 PAPER 8 To: egs@CS.Cornell.EDU Date: Tue, 18 Sep 2001 10:40:57 -0400 (EDT) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit --------START------ A highly adaptive distributed routing algorithm for mobile wireless networks, V.D. Park and M.C. Corson. Reviewer: Indranil Gupta The authors start off by criticizing existing ad-hoc routing protocols for their behavior on partitions, and their lack of multipath routing, which the authors believe is the way to avoid congestion. The authors believe that ad-hoc routing protocols should be reactive, require localized updates, and not necessarily provide 'shortest' routes. A new routing algorithm called Temporally ordered routing (TORA) is described. For each destination, each node maintains a "height", and packets for the destination flow out from a node to a neighbor with a lower height. New route discoveries are done by having the sender broadcast a query packet, and all nodes in the network decide on a height for the destination. The assignment of heights is effectively equivalent to a destination-oriented Dijkstra's shortest path algorithm. Every node thus has multiple paths to each desintation, and typically chooses the neighbor with the smallest height to a destination as the next hop, but could just as well choose other neighboring nodes with a smaller height than itself as the next hop - this provides multiple routes. A node or link failure requires changes to heights of only local nodes, i.e., nodes whose height changes due to the failure. This protocol is initiated by a node that finds itself with a height smaller than all its neighbors - it increases its height to more than the maximum of all these neighbors, and this change is allowed to propagate to "upstream" nodes that change their heigh. Partitions are detected when a node that initiates such a protocol find itself (during the execution of the same protocol, identified by the initiator) again in a state where it has a height smaller than all its neighbors; the node then sends a CLR packet to clear routes to the partitioned-away destination. Lamport's logical clock ordering is sufficient for a consistent protocol. The use of heights to route also avoids loops. Comments: - The authors say that choosing the next hop as the neighbor with the lowest height (lower than this node's height) may not necessarily ensure that the shortest route is chosen. How much worse compared to the shortest route is this route ? After a long sequence of node and link failures (possibly pathological to the protocol), can the shortest path allowed by the heights be arbitrarily longer than the shortest route ? -The authors say that it is advantageous to maintain multiple routes from a source to a destination in large, dense and mobile networks. However, if connections are short lived (few packets) as in an email, or not too many nodes communicate with the given destination, maintaining multiple routes to a destination (essentially, the heights) is unnecessary overhead. This is especially true in a highly mobile network, and because ther routing algorithms are reactive. - It might be a better idea under the circumstances, as explained in the previous point, to have the application specify other such parameters (as expected number of packets to be sent) to avoid too much overhead on other nodes in the network. --------END------ From c.tavoularis@utoronto.ca Tue Sep 18 11:30:00 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 f8IFTxq16442 for ; Tue, 18 Sep 2001 11:29:59 -0400 (EDT) Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 35071]) by bureau6.utcc.utoronto.ca with ESMTP id <238492-4715>; Tue, 18 Sep 2001 11:29:52 -0400 Received: by webmail3.ns.utoronto.ca id <414678-5766>; Tue, 18 Sep 2001 11:29:22 -0400 To: COM S 615 Subject: 615 PAPER 8 Message-ID: <1000826961.3ba7685181706@webmail.utoronto.ca> Date: Tue, 18 Sep 2001 11:29:21 -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 presents the Temporally-Ordered-Routing Algorithm (TORA) for routing in adhoc networks. It employs physical or logical clocks to organize the temporal changes in node formation such as node displacement or link failure. It uses a link-reversal algorithm to minimize reaction to topological changes. The algorithm works as follows: each node is aware of its neighbors, whom can be reached via broadcast. Each node is also assigned a height, initially NULL, which is used to define its upstream and downstream neighbors along a path. With an on-demand approach, a node will create a route in the form of a directed acyclic graph (DAG) using a query/reply method. Link reversal is initiated when a change is detected in an existing path. If a node, other than the destination, no longer has a downstream neighbor, it maximizes its height and broadcasts this information to its neighbors. This process propagates and reverses the path to the source to determine a new path. If the message unsuccessfully returns to the originator of the link reversal, then a partition has been discovered. Consequently, the partitioned route is erased by a series of clear messages. This paper, lacking in simulation results, tries to compare TORA to existing algorithms through worst-case complexity. It is very difficult to tell the true performance of TORA, although it is clear that it could not perform much worse than existing algorithms since they are all of linear order. The main advantage of TORA is that it can prevent ‘far-reaching’ message propagation due to changes in link status. Link-reversal allows reaction to topological changes to remain localized. This favors scalability since performance is no longer a function of the total number of nodes. It is suggested that this protocol recovers well in dense nodal environments where a link failure only affects a few surrounding nodes. It is not clear how TORA would perform in sparse environments, and it would be very interesting to compare simulation results in both cases. An interesting aspect brought up in this paper is the advantage of creating multiple paths rather than a single optimal (shortest) path. Many other algorithms always elect the optimal path. This involves the risk of quickly depleting the energy in the optimal path, so that a sub-optimal path will have to be used. When congestion arises, or in the event of a link failure, it is desirable to have existing alternate paths rather than reinitiating a path discovery. It is possible to employ the optimal path in TORA using the parameter delta. An interesting project would be to compare the use of 1 optimal path versus many suboptimal paths in adhoc routing. From jcb35@cornell.edu Tue Sep 18 11:38:12 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 f8IFcCq17565 for ; Tue, 18 Sep 2001 11:38:12 -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 LAA22820 for ; Tue, 18 Sep 2001 11:38:09 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f8IFfQa02200 for ; Tue, 18 Sep 2001 11:41:27 -0400 Date: Tue, 18 Sep 2001 11:41:25 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU Subject: 615 PAPER 8 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discussed another distributed routing protocol for mobile multihop wireless networks. The authors claim it is much more suitable for large, dense, and mobile networks than previous attempts at mobile ad-hoc networking protocols. The protocol attempts to keep the reaction to failed links local by using a physical or logical clock to establish the temporal order of topology changes. They use this to structure the algorithm's reaction to changes in the connectivity graph; because of this, they call the protocol the Temporally Ordered Routing Algorithm (TORA). First the authors discuss a wide range of routing protocols from ILB to GB to DSR and discuss the shortcomings of those protocols and justify why a algorithm like TORA is needed - most of the reasons deal with scalability, protocol overhead, and problems with link failure notification propagation. Next the paper discusses assumptions they work with, namely a link level protocol in which nodes are aware of each other, that all transmitted packets are received correctly and in order of transmission, and that packets are broadcasted to neighbors. The paper then reveals the interworkings of the protocol, which deal with three types of protocol control messages: query (qry), update(upd), and clear (clr) for errors. The route discovery process creates a directed acyclic graph (dag) rooted at the destination. The route is them created through designating upstream and downstream nodes using a height metric for each node. This height metric allows a lexicographic ordering. Routes are reversed when a node looses all its downstream links (which corresponds with a local minimum in the ordering). Reversing routes corresponds to when a node needs a route. This also means that when a node looses its last downstream link from a link failure, the nodes selects a new height so it becomes a global maximum by defining a new "reference level". This action results in link reversals so that the link failure propagates outward from the point of original failure, but extends only through nodes that have lost a link to the destination. The algorithm will detect partitioning when it sees a reflected reference level. Comments: The algorithm seems to make a tradoff between maintaining multiple routes and route optimality. Tora seems to make a possibly unrealistic assumption of packet ordering and dealing with time. The simulations were not present, I thought the graphs of "worst case" scenarios were interesting, but I would really like to see graphs detailing how the algorithm stands up against others for things like route error propagation and protocol overhead. From ranveer@CS.Cornell.EDU Tue Sep 18 11:38:40 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 f8IFcdq17585 for ; Tue, 18 Sep 2001 11:38:39 -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 8 Date: Tue, 18 Sep 2001 11:38:39 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 8 Thread-Index: AcFAV/z/UBL2+HAWTrGo5tN/GXARCQ== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f8IFcdq17585 A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks This paper proposes a new routing protocol for large, dense, mobile networks. It buils on the idea of 2 previous papers, that of partial reversal (Gafni et al 1981) and LMR(Corson et al 1995). The basic idea is that a reversal algrithm is best suited for large mobile networks. A destination oriented DAG is maintained that is updated with the least overhead. TORA is extremely efficient for fast moving and large networks. It provides a solution for routing when shortest path routing is not possible, but flooding is not necessarily the only option. The advantage of TORA over the other(distance vector and link state) algorithms is in the number of control messages generated in the network. TORA is also more responsive to network and topology changes. The lesser number of control messages makes it more scalable while its responsiveness makes it more suitable for highly mobile networks. However, TORA has its own share of disadvantages. Firstly, it requires a reliable broadcast to all its neighbors. It was shown by Broch et al, 1998 that TORA performs very poorly with 802.11. Secondly, there are no simulation results that show the goodness of TORA. Finally TORA suffers from the same disadvantage as AODV: it does not support unidirectional links. There are many modifications possible on TORA. For example, it would be interesting to see how the solutions proposed in the 'Broadcast Storm' paper would help TORA and overcome the overhead shown by Broch et al in 1998. From teifel@csl.cornell.edu Tue Sep 18 11:45:36 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 f8IFjZq18312 for ; Tue, 18 Sep 2001 11:45:35 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8IFjUU45332 for ; Tue, 18 Sep 2001 11:45:30 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 18 Sep 2001 11:45:30 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 8 Message-ID: <20010918105221.D45877-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII TORA: This paper presents a novel link reversal algorithm for use in routing protocols of mobile networks. They claim that this protocol is ideally suited for adhoc networks, because their algorithm reacts only locally to small changes in topology--conserving network bandwidth. Nodes only maintain one-hop knowledge and routing is source initiated. This algorithm uses temporal information to adaptively maintain routing information based on the current network topology. The algorithm has the ability to detect network partitions and correct its own routing tables. Given the wonderful claims about the algorithm that were presented in the first few sections, I was looking forward to seeing actual simulation results--only, to come to the performance section and see that there was no simulation data at the time of publication. For a "new idea" paper, this paper clearly presented the possible advantages of this algorithm, its weaknesses and potential solutions to correct its minor flaws. From samar@ece.cornell.edu Tue Sep 18 11:53:16 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8IFrFq19352 for ; Tue, 18 Sep 2001 11:53:15 -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 f8IFrFi31042 for ; Tue, 18 Sep 2001 11:53:15 -0400 Date: Tue, 18 Sep 2001 11:53:15 -0400 (EDT) From: Prince Samar X-Sender: samar@ockham.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 8 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 8) TORA: A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks Temporally-Ordered Routing Algorithm (TORA) belongs to the family of link-reversal algorithms, based on temporally ordered sequences of diffusing computations. It is a reactive routing protocol designed specifically for mobile ad hoc networks which distributedly constructs a Directed Acyclic Graph (DAG) rooted at the destination for each query initiated in the network. The protocol is capable of finding loop-free, multi-path routes which can be dynamically maintained. The authors claim that it can limit the extent of reach of control messages caused due to local topological changes, quickly reacting and re-establishing valid routes to the destination. Also, in the event of a network partition, the protocol detects and erases all invalid routes within finite time. For each route discovery in the network, every node i maintains an ordered quintuple height H_i = (t_i, oid_i, r_i, d_i, i) such that all nodes can be ordered based on the quintuple values. Each node maintains a link-state array for all of the node's links with its neighbors and a corresponding height-array for these links. The height of the destination is always ZERO by definition. As the QRY packet propagates in the network, triggering UPD packets, the nodes choose heights such that a DAG is created with egdes directed towards the destination. To convert a destination-disoriented DAG to a destination-oriented one, rules similar to the partial reversal method are used. If a node loses its last downstream link, it could generate a new reference level, reflected back a higher sub-level or conclude a detection of partition depending upon the cause of the link failure and some other conditions. Comments: - TORA is a highly adaptive, scalable, distributed routing protocol, which is capable of computing loop-free, multi-path routes to the destination in a MANET. In my opinion, its a pretty neat algorithm though not among the most popular MANET routing protocols - probably due to its complicated algorithm as compared to protocols like AODV and DSR. - The paper does not have any simulation results to back-up its claims. They present worst-case complexity comparisons of some algorithms, but play it down themselves as the parameters may potentially be different for each protocol. The authors do state that work is underway to for a comparative study of the algorithm. - The protocol requires synchronization between the nodes using either physical or logical clocks. The authors mention that time tag errors reduce the efficiency of the protocol. How drastic would this effect be? - The protocol discovers many paths to a destination. This may lead to wastage of resources if the connection is short-lived, with few packets exchanged between the source and destination. Apart from discovering, all routes to the destination are maintained as well even if they may not be used at all. This probably could be avoided by having some parameters dependent upon the application and mobility, timing out unused routes instead of correcting them. - The algorithm does not have any good way to determine quality of routes over a period of time. - The authors describe a enhancement to the protocol by periodically propagating refresh packets in the network. But this has not been analyzed in any way. Also, how would one determine the optimal rate of these background updates. From egs@CS.Cornell.EDU Tue Sep 18 13:06:23 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8IH6Mq27495 for ; Tue, 18 Sep 2001 13:06:23 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8IH6MY03736 for egs; Tue, 18 Sep 2001 13:06:22 -0400 (EDT) Date: Tue, 18 Sep 2001 13:06:22 -0400 (EDT) Message-Id: <200109181706.f8IH6MY03736@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: CS615 PAPER 8 >From ramasv@CS.Cornell.EDU Tue Sep 18 11:08:35 2001 >X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 >content-class: urn:content-classes:message >Subject: cs615 PAPER 8 >Date: Tue, 18 Sep 2001 11:08:35 -0400 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: cs615 PAPER 8 >Thread-Index: AcFAU3t0xaeJt6ulEdWTbwCQJ5m7oA== >From: "Venu Ramasubramanian" >To: "Emin Gun Sirer" >X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8IF8Zq13942 > >A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless >Networks > > This paper presents a novel routing algorithm for mobile ad hoc >networks that creates routes on-demand, maintains the created routes by >activity local to link breakages, guarantees freedom of route loops and >maintains multiple paths for fault tolerance and to reduce congestion. >The algortihm relies on link level protocol to accurately identify link >breakages. > > This routing algorithm works by creating a directed acyclic >graph consisting of multiple loop free routes to a destination at each >node. Seperate DAGs are created and maintained for each destination for >which packets need to be sent. The DAGs are maintained by a process >described in the paper as partial/full link reversal, that consists of >reversing the direction of the links in the DAG to repair it when a link >is broken or added. The interesting feature is that the link reversals >can be performed at each node by only having certain information from >its neighbors. Thus the reactive activity upon link changes is >restricted to the locality. This is done by maintining a 5 tuple (that >has a total order) to represent the height of each node in the DAG wrt. >the destination. Timestamp is used to create new values of height that >need to be higher than any before (this facilitates the locality). >Hence this protocol is called TORA. > > The construction of the DAG is initiated only when a source node >needs to send a message. However, once constructed, the DAG is >maintained at all nodes forever. This adds a lot of control overhead to >the network as it invokes participation at all the nodes. Although the >DAG maintanance is local (and scalable), the above requirement could >prevent the protocol from scaling to large networks. Further, the DAG >may not contain the shortest route to the destination. It would be >interesting to look at the performance with a simulator or a real >network. This paper does not provide any such results. > > The advantage of the protocol is the maintainance of multiple >paths to each destination. Thus the packet delivery and latency may not >be significantly affected due to link breakages. It also helps to >reduce congestion by using alternate paths. However I think a DAG is an >overkill and may lead to very high maintanance cost. The protocol also >guarantees loop freedom and stability in the presence of partitions >which are certainly very useful. In essence, the novelty of the routing >algorithm presented makes this a very interesting paper to read. > > From egs@CS.Cornell.EDU Tue Sep 18 13:06:34 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8IH6Xq27507 for ; Tue, 18 Sep 2001 13:06:33 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8IH6Xm03859 for egs; Tue, 18 Sep 2001 13:06:33 -0400 (EDT) Date: Tue, 18 Sep 2001 13:06:33 -0400 (EDT) Message-Id: <200109181706.f8IH6Xm03859@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: CS615 PAPER 8 >From avneesh@csl.cornell.edu Mon Sep 17 23:58:48 2001 >Content-Class: urn:content-classes:message >Subject: CS615 Paper #8 >Date: Tue, 18 Sep 2001 00:03:25 -0400 >X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: CS615 Paper #8 >Thread-Index: AcE/9t1DT007TdMMTa+CuLh15p5naA== >From: "Avneesh Bhatnagar" >To: >X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8I3wlq05212 > >A Highly adaptive Distributed Routing Algorithm for MObile Wireless >Networks. > > >Paper Summary > >This paper describes the design of a Temporally-ordered routing >algorithm (TORA), the name of which arises from the relative ordering of >time tags which match the route update events which occur within the >network. The main aim of the protocol is to reduce far-reaching control >message propagation across the network when a topology change event >occurs. The protocol addresses the inherent problems of using the >conventional protocols for a connected network, in a wireless network. >The points which are interesting are that the protocol aims towards loop >free routes, multiple routes and reduction of congestion as well as >communication overhead instead of emphasizing on route optimality. >Furthermore, the protocol can tolerate k/2-1 downstream failures for k >nodes with average of k/2 downstream links, without requiring any >reaction within the network. This is significant in a highly >dense/connected network, where such responses could be widely >propagated. > >The routing primitives in the protocol are the QRY, UPD and CLR messages >which are used for route management. Query messages are sent by a node >which requires a route and forwarded by nodes, which at that point do >not have valid route themselves. The main idea is to use a destination >rooted DAG, where the destination node has the lowest height of all >nodes. Updates are done using link reversal where messages are sent to >the upstream node to create a downstrea, link if a downstream link to >the destination from the current node exists. Network partitions can >also be detected, by carrying out a novel route mantainence algorithm. >Another interesting action is that redundant routes which exits in a >partioned network are quickly erases through this link reversal >mechanism. > >Nodes are required to mantain some state in form of neighbor height and >link state tables to manage the route information. It has also been >shown that temporal ordering does not depend on the absolute values of >the time tags, as long as they are in the correct order. > >I think that paper is extremely well written, and since I have not read >many other papers for mobile network routing, I felt that the route >management approach was quite novel. It would be very interesting to see >how the protocol performs in the simulations and how the presence of >soft state messaging etc as well as network desnity effects its >performance. > From egs@CS.Cornell.EDU Wed Sep 19 10:04:29 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8JE4Sq06845 for ; Wed, 19 Sep 2001 10:04:29 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8JE4St08755 for egs; Wed, 19 Sep 2001 10:04:28 -0400 (EDT) Date: Wed, 19 Sep 2001 10:04:28 -0400 (EDT) Message-Id: <200109191404.f8JE4St08755@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 8 >From eyh5@ee.cornell.edu Wed Sep 19 08:16:29 2001 >Date: Wed, 19 Sep 2001 08:15:58 -0400 (EDT) >From: Edward Hua >To: egs@CS.Cornell.EDU >Subject: TORA summary > >Hi Gun, > > As per your request, below is the summary on TORA. > > Thanks. > >-Ed > >------------------------- > > This paper introduces a temporarally-ordered routing algorithm >(TORA) that aims at minimizing the time delay due to reaction to >topological changes in a mobile wireless network. The algorithm binds a >value, called a Height, to each of the nodes in the network. This value is >used to define the relationship of data packet flow between Node A and >Node B, that is, Node A with a greater Height value is considered the >upstream (UP) node and is capable of sending data packets to Node B, a >downstream (DN) node. When a node, say, X, which is not the destination, >has no downstream links just as the destination, the algorithm is invoked >to compute a higher Height value for X than those of its neighbors, thus >creating a reversal of "streamed" links and allowing packets to flow from >X to its neighbors. Potentially, this will be very helpful in providing >auxiliary branch paths that may come in handy if one or more of the links >of the primary path between the source and destination are severed. With >this technique of directed link reversal, the reaction to the topological >change can be minimzed as the source will be promptly able to obtain an >alternative route to the destination. > > One advantage of this algorithm is its less reliance on blindly >broadcasting a node's current state in order to maintain network >connectivity. The computation of the nodal Height value is done inside a >node, and it is only to be known by its immediate neighbors. This may save >the bandwidth normally associated with processing overhead information on >a large scale. Entailing this locally proactive announcement, the >scalability of the network is enhanced. Another strong point is the timely >restoration of the route between source and destination once a link along >the path is severed. > > An improvement could be made in the creation of a new route. It >seems that a source node broadcasts a QRY packet to all the nodes in the >network. This may be avoided by incorporating the concept of zone-routing >protocl, which defines a cluster of neighboring nodes to the source >node. Since the broadcast message (e.g., flooding) need not be known by >all the nodes anyway, these neighboring nodes will be more than adequate >to examine the QRY and rebroadcast them to their respective defined >routing zones. This technique will help reducing the excessiveness of >control information overhead propogating the network. > > Unfortunately, this paper does not provide a performance >simulation to back up its claims. Another comment to make is that this >routing protocol strives to cut down the time wasted on the reaction to >the radical change in the netowork topology, at the expense of choosing a >route that could have otherwise been "optimal." This philosophy has its >merits, as it may shift the QoS issues to the upper-layer applications >while retaining only the most basic functions within the ad hoc >network. The trade-off between optimality and reduced reaction time is an >interesting issue that deserves further study. > > >