From mvp9@cornell.edu Sun Sep 15 19:56:28 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8FNuSh27986 for ; Sun, 15 Sep 2002 19:56:28 -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 TAA12642; Sun, 15 Sep 2002 19:56:25 -0400 (EDT) Date: Sun, 15 Sep 2002 19:56:24 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 11 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents a new routing protocol for MANETs. It fits none of the three models we've encountered so far - dv, link-state or source-routing. Instead it works by maintaining most of the state associated with link-state in a DAG, but it is not refreshed as often. The claim is that TORA minimizes reaction to topological changes and separates generation of control messages from rate of topological changes (which are achieved through roughly the same means). The protocol as described is hideously complicated and obfuscated, precluding reasonable inspection. It is not clear that some of the related protocols mentioned in the outset could not achieve the same claims by simply maintaining multiple routes instead of only one best route. The worst drawback of TORA is the exhorbitant assumptions that it makes. Not only does it require bidirectional links and a link-level protocol that allows a node to always be aware of the state of the link to each neighbor, but, it actually depends on correct and in-order transmission of all packets!! The analysis of achievement of initial goals is absent in any concrete form and the worst-case analysis of it and similar protocols is barely informative because of the "fuzzy" complexity parameters, and is not that impressive anyway. Although it may be more scalable than its counterparts, it offers few, if any benefits. From hs247@cornell.edu Mon Sep 16 16:46:35 2002 Received: from mailout6-0 (mailout6-1.nyroc.rr.com [24.92.226.177]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8GKkYh09498 for ; Mon, 16 Sep 2002 16:46:34 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0 (8.11.6/RoadRunner 1.20) with ESMTP id g8GKijf18619 for ; Mon, 16 Sep 2002 16:44:45 -0400 (EDT) Message-Id: <5.1.0.14.2.20020916164507.00b31ba0@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Mon, 16 Sep 2002 16:45:30 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 11 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The authors Park and Corson present the Temporally-Ordered Routing Algorithm (TORA). The general idea of this paper seems to be to represent the ad-hoc network as a directed acyclic graph. The nodes in a graph are ordered globally with a sending node having the highest ordering and the destination node having the lowest. Since there may be many downstream routes, a node can potentially choose amoung multiple paths to send a packet. In this way, having multiple paths avoids congestion and gives alternate options when a route becomes disconnected. When a node become disconnected and loses all downstream routes, (it knows this if is the local minimum), a node then assigns itself the globally highest ranking and therefore routes will have to adapt to this change. This adapting to change is done by a link reversal scheme. Ideally, only its neighbours will have to react which keeps overall topology change small, as only local nodes have to react. One disadvantage to this scheme is that over time, the graph may have routes that are not optimal. Since a node only has to keep track of its neighbours, broadcasts are limited and tables are kept to a minimal, which theoretically means networks implementing this protocol are more scalable. The paper seems to refer to a lot of outside papers. And since I personally unfamiliar with these papers, I found many things in the paper hard to understand. In general, the algorithm described seemed very complicated and I had a hard time understanding what was going on. But from my point of view, it seems like the paper was based on many assumptions. I did not like how the algorithm has to depended on a global ordering system such as clock synchronization. To me, having clock synchronization means nodes must talk to a centralized server which would be undesirable in an ad-hoc network. There seems to be some good ideas in this protocol. The proposed properties if true would be ideal for an ad-hoc network. Work about choosing delta parameters and possibly how having those assumptions might affect the protocol should be investigated. At the fore front though, an implementation of this protocol is needed to see how it performs practically. Once this is done, perhaps the ideas proposed in this paper can be validated. From shafat@CS.Cornell.EDU Mon Sep 16 20:35:16 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H0ZFh19172 for ; Mon, 16 Sep 2002 20:35:16 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 11 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Mon, 16 Sep 2002 20:35:15 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D1507A0@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 11 Thread-Index: AcJd4hht2DyQs3WTSLeDbvsvx1cX1g== From: "Syed Shafat Zaman" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8H0ZFh19172 This paper introduces a "link-removal" algorithm to develop a loop-free routing protocol for wireless networks. It relies heavily upon the "temporal order of topological change events" and hence, is referred to as the Temporally-Ordered Routing Algorithm or TORA. The protocol takes a different approach to developing an effective algorithm than some of its predecessors, and does not emphasize on determining the shortest path to a destination. This inadvertently allows it to offer multiple routes between two nodes. Another important factor that it addresses is the convergence time. It is capable of establishing new routes and detecting network partitions with a small finite number of iterations. Like distance vector algorithms, TORA requires a node to only maintain information about its neighbors. This helps minimize the communication cost and storage requirement in the network. All these characteristics of the protocol is claimed to make it highly adaptive, scalable, and extremely suitable for highly dynamic and dense wireless networks. One of the major drawbacks of the paper is the obvious exclusion of quantitative data. While the algorithm itself is rather complex, it is even harder to predict it's assured high degree of efficiency until simulations or experiments are carried out. It is also not clear from the paper how multiple source-destination pairs are handled by the protocol. A separate section describing the actual working of the protocol (e.g. packet forwarding) would have been helpful. This observation is important as intermediate nodes in a route may have to change their "height" very frequently to forward packets to different destinations. Another underlying assumption - that all transmitted packets are received correctly and in order - also challenges the full functionality of TORA. This also needs extensive testing as the protocol supports multiple routes and the assumption may not always hold. From jsy6@cornell.edu Mon Sep 16 21:58:52 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H1wqh04738 for ; Mon, 16 Sep 2002 21:58:52 -0400 (EDT) Received: from Janet (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id VAA19939 for ; Mon, 16 Sep 2002 21:58:44 -0400 (EDT) Message-ID: <000a01c25ded$b148b640$a400a8c0@Janet> From: "Janet Suzie Yoon" To: Subject: 615 PAPER 11 Date: Mon, 16 Sep 2002 21:58:12 -0400 MIME-Version: 1.0 X-Security: MIME headers sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.132 $Date: 2001-12-05 20:20:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_0007_01C25DCC.26822490" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 This is a multi-part message in MIME format. ------=_NextPart_000_0007_01C25DCC.26822490 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The largest contribution of this paper is the introduction of the = Temporally-ordered Routing Algorithm (TORA), a distributed routing = protocol that localizes its reaction to topological changes in a mobile, = multihop, wireless network. Localization is achieved with the use of a = logical or physical clock to temporally order topological changes (hence = its name), allowing an ordering of the protocol's reaction to these = changes. The ability to react locally to topological changes minimizes = the amount of communication needed in the network, thus making TORA = scalable and highly adaptive. TORA is distributed because nodes only = need to maintain information about its neighbors. Another main = advantage of TORA is its ability to quickly establish loop-free routes = on a need-only basis, thus alleviating congestion. Also TORA, upon = detecting network partition, can erase invalid routes within a finite = amount of time. TORA is basically a temporally ordered sequence of directed link = reversals. The protocol can be partitioned into three functions - = creating, maintaining, and erasing routes. The function to create = routes can only be called by a node that needs a route to a destination = and has no directed links. Creating routes is essentially building a = destination oriented DAG. Maintaining routes is the reaction to = topological changes. Since TORA provides multiple routes from source to = destination, many topological changes do not require any reaction. The = amount of time it takes to re-establish routes is finite. Erasing = routes occur when a partition is detected. Invalid routes are erased by = setting the links to the undirected state. =20 Although reacting to a partition takes a small amount of time, actually = detecting a partition can potentially take a long time. To detect a = partition from a node to the destination, the following steps must = occur. Suppose a node loses its last downstream link. It then chooses = a new height and becomes a global maximum. This action causes link = reversals that can result in other nodes losing their last downstream = link. This outward propagation from the original failure extends = through all nodes which lost all routes to the destination. These links = must choose a height so that they are the local maximum. This reflected = reference level must propagate back to the originating node from all of = its neighbors in order to determine that no route to the destination = exists. It is not until the originating node detected a partition that = the route erasing function can be called. This partition detection = algorithm relies on the assumption that links are equal in both = direction and that all transmitted packets are correctly received in the = order they were transmitted, along with the other functions in TORA. = These assumptions are unrealistic. In real life, packet delays and = losses are common and links are not always bi-directional. =20 Another glaring disadvantage of TORA is the amount of information each = node must maintain. Every node i must keep track of its own height and = the height of all its neighbors. It must also maintain a link-state = array for any link (i,j), a route-required flag, the time at which the = last UDP packet was broadcasted, and the time each link (i,j) became = active. It would be good to know exactly the minimum amount of memory = and computational power each node is required. Comparative simulated = data would also be good; the paper only offers worst case protocol = complexities. Finally, the link-reversing functions in TORA results in = the routes becoming less optimal than it was at creation. The next step = in research would be to incorporate an embedded far-reaching control = message propagation into the protocol as a second mechanism (right now, = only a localized message propagation is used). This global propagation = should be infrequent, but periodical and independent of the dynamics of = the network topology. This messaging propagation would be used for = route optimization and soft-state route verification.=20 ------=_NextPart_000_0007_01C25DCC.26822490 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

The largest contribution of this paper = is the=20 introduction of the Temporally-ordered Routing Algorithm (TORA), a = distributed=20 routing protocol that localizes its reaction to topological changes in a = mobile,=20 multihop, wireless network. =20 Localization is achieved with the use of a logical or physical = clock to=20 temporally order topological changes (hence its name), allowing an = ordering of=20 the protocol=92s reaction to these changes. =20 The ability to react locally to topological changes minimizes the = amount=20 of communication needed in the network, thus making TORA scalable and = highly=20 adaptive.  TORA is = distributed=20 because nodes only need to maintain information about its = neighbors.  Another main advantage of TORA = is its=20 ability to quickly establish loop-free routes on a need-only basis, thus = alleviating congestion.  = Also TORA,=20 upon detecting network partition, can erase invalid routes within a = finite=20 amount of time.

TORA is basically a temporally = ordered=20 sequence of directed link reversals. =20 The protocol can be partitioned into three functions =96 = creating,=20 maintaining, and erasing routes.  = The function to create routes can only be called by a node that = needs a=20 route to a destination and has no directed links.  Creating routes is essentially = building=20 a destination oriented DAG. =20 Maintaining routes is the reaction to topological changes.  Since TORA provides multiple = routes from=20 source to destination, many topological changes do not require any=20 reaction.  The amount of = time it=20 takes to re-establish routes is finite. =20 Erasing routes occur when a partition is detected.  Invalid routes are erased by = setting the=20 links to the undirected state. =20

Although reacting to a partition = takes a=20 small amount of time, actually detecting a partition can potentially = take a long=20 time.  To detect a = partition from a=20 node to the destination, the following steps must occur.  Suppose a node loses its last = downstream=20 link.  It then chooses a = new height=20 and becomes a global maximum.  = This=20 action causes link reversals that can result in other nodes losing their = last=20 downstream link.  This = outward=20 propagation from the original failure extends through all nodes which = lost all=20 routes to the destination.  = These=20 links must choose a height so that they are the local maximum.  This reflected reference level = must=20 propagate back to the originating node from all of its neighbors in = order to=20 determine that no route to the destination exists.  It is not until the = originating node=20 detected a partition that the route erasing function can be called.  This partition detection = algorithm=20 relies on the assumption that links are equal in both direction and that = all=20 transmitted packets are correctly received in the order they were = transmitted,=20 along with the other functions in TORA. =20 These assumptions are unrealistic. =20 In real life, packet delays and losses are common and links are = not=20 always bi-directional. =20

Another glaring disadvantage of TORA = is the amount=20 of information each node must maintain. =20 Every node i must keep track of its own height and the height of = all its=20 neighbors.  It must also = maintain a=20 link-state array for any link (i,j), a route-required flag, the time at = which=20 the last UDP packet was broadcasted, and the time each link (i,j) became = active.  It would be good = to know=20 exactly the minimum amount of memory and computational power each node = is=20 required.  Comparative = simulated=20 data would also be good; the paper only offers worst case protocol=20 complexities.  Finally, = the=20 link-reversing functions in TORA results in the routes becoming less = optimal=20 than it was at creation.  = The next=20 step in research would be to incorporate an embedded far-reaching = control=20 message propagation into the protocol as a second mechanism (right now, = only a=20 localized message propagation is used). =20 This global propagation should be infrequent, but periodical and=20 independent of the dynamics of the network topology.  This messaging propagation = would be used=20 for route optimization and soft-state route verification.=20

------=_NextPart_000_0007_01C25DCC.26822490-- From bd39@cornell.edu Mon Sep 16 22:11:56 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H2Buh07348 for ; Mon, 16 Sep 2002 22:11:56 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id WAA22137 for ; Mon, 16 Sep 2002 22:11:54 -0400 (EDT) Message-Id: <5.1.0.14.2.20020916221040.00bc7090@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Mon, 16 Sep 2002 22:11:00 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 11 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Paper 11 - TORA The authors of this paper focus their routing protocol design on a metric different previous articles we have read. They specifically desire to address the issue of scalability of routing protocols in a (very) large network. Instead of a minimization of path length, they seek to minimize protocol overhead given topological changes. The main idea behind the operation of their protocol is the formation of a "gradient" like path for packet to flow from source to destination. One notable aspect of the TORA protocol is the formation of multiple paths which provide redundancy in the network and allow links to fail without needing to update the way routing is done. Also notable is that route repair is done locally. In this way, route discovery is truly distributed among all of the nodes. It is easy to imagine a load balancing scheme that could take advantage of the multiple routes. One assumption the paper make is that links are bidirectional. The paper also makes some arguments about the need for time synchronization and node neighborhood information - these aspects of the protocol involve inter-node communication, and should be addressed as well (but was not.) A big assumption that the paper did not address was the that internode communication is lossless. No error conditions were addressed, especially regarding lost protocol packets. Also notable is the lack of experimental data. Some areas for investigation would be the extension of this protocol to support routing to multiple destination rather than one. One unfortunate aspect of this protocols is that protocol traffic only maintains the "gradient" for a single destination node, which means that protocol traffic will not scale well when there are a number of different destinations that the nodes want to communicate with. Also, the presence of multiple routes means that there is in place a mechanism for load balancing, which would be an interesting addition to the protocol. From nbs24@cornell.edu Mon Sep 16 22:29:43 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H2Thh11609 for ; Mon, 16 Sep 2002 22:29:43 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id WAA07628; Mon, 16 Sep 2002 22:29:39 -0400 (EDT) Date: Mon, 16 Sep 2002 22:29:39 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209170229.WAA07628@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@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: nbs24@cornell.edu X-Originating-IP: 64.185.145.94 Subject: 615 PAPER 11 The paper proposes another reactive routing protocol, Temporarily-Ordered Routing Algorithm (TORA). It's major contribution is the design of an algorithm that minimizes reaction to topological changes. Using a link reversal scheme and based on relative node heights, reaction to topological changes are localized within a defined neighborhood. Partitions are also quickly identified and invalidated. The algorithm incorporates a scheme to suppress duplicate rebroadcasts. The proposed algorithm depends on the nodes maintaining some ordering (either by sychronized clocks or some other ordering means). I think this is where the algorithm breaks. In an ad-hoc network rapid topological changes will make maintaining ordering difficult and if a central clock has to be used, that will be defeat the purpose of an ad-hoc network, which has no centralization. Another assumption for the proposed algorithm is that the packets are recieved correctly and in order. How can this be guaranteed? It would have been good to see the effect of their algorithm in a real implementation. The authors should have given nice summaries of previous work they were building on, instead of asking readers to go read the references. The algorithm looks like it scales well, but definitely a real implementation will be a good build to the research. Some simulations will help in choosing optimal values for the routing parameters that are proposed. Nana B. Sam From xz56@cornell.edu Mon Sep 16 22:48:12 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H2mBh15189 for ; Mon, 16 Sep 2002 22:48:11 -0400 (EDT) Received: from XIN (dhcp-ece-167.ece.cornell.edu [132.236.232.167]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id WAA24506 for ; Mon, 16 Sep 2002 22:48:10 -0400 (EDT) Message-ID: <00cf01c25df4$a8872df0$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 11 Date: Mon, 16 Sep 2002 22:48:08 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 The paper describes the protocol of TORA, which is of reactive type. By constructing a DAG rooted at destination, it offers multiple links which increases the reliability and reduces the need to refind the route in the case of a single link failure. The destination-oriented DAG is constructed by iterations of two algorithms: full reversal method (adding a new node into the DAG), partial reversal method (handling the case when a single link fails and some other links still work and erasing the node when no link is available). Also during this reversal process, "heights" are assigned to each node which represents the direction in the DAG. The good point of the paper is that construction of DAG offering multiple routes enhances the performance of the protocol with respect to reliability and overhead; and the assignment of heights as a way of representing the routes reduces the memory needed to store the route info. The way authors used to present the protocol is not very good. It's difficult to grasp the main idea at the first sight. And the detailed description part will make much more sense if more explanation of example is given, esp. for the parameters. Some confusions: 1. How the creating routes function is ended? The QRY can travel very broadly over the network even when the sufficient routes have been found. 2. Is there a distinct DAG for each destination at each node? If yes, it seems to be a enormous routing table. If not, heights will be reassigned each time when destination changes, i.e. a new process of creating routes is needed for each transmission session. From mr228@cornell.edu Mon Sep 16 23:30:15 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H3UFh23564 for ; Mon, 16 Sep 2002 23:30:15 -0400 (EDT) Received: from cornell.edu (syr-24-58-63-179.twcny.rr.com [24.58.63.179]) by cornell.edu (8.9.3/8.9.3) with ESMTP id XAA10718 for ; Mon, 16 Sep 2002 23:30:11 -0400 (EDT) Message-ID: <3D86A1C2.B2B7C2CD@cornell.edu> Date: Mon, 16 Sep 2002 23:30:10 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 11 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper considers routing in a densely packed network. Their primary goal is not to get the shortest path, but to get reasonably short paths with an algorithm that can scale in a very large and very dense network. Unlike the previous papers they are considering the case where the hosts move very frequently, thus requiring (nearly) constant reorganization of the network. For the other protocols this meant a lot of overhead in the packets required to "fix" routes. Their goal here is to provide an algorithm that requires only local updates as hosts move. They call their proposed algorithm TORA: Temporally-Ordered Routing Algorithm. The protocol constructs a DAG in the network any time a node needs to send data to some destination. The sending node is at the root of the DAG and information flows towards the destination, which is at the lowest height of the tree. Maintenance of routes is done with "update" packets. The extent to which these packets need to be forwarded is bounded and many link failures don't require "update" transmissions since there can be multiple routes to the destination. The paper defers much of the work it builds on and requires the reader to go find and read other papers. I am not familiar with many of the algorithms and protocols they mention, so it may have been helpful for them to at least provide a very brief synopses of their citations. The paper has several problems and makes several problematic assumptions. While they do present rough algorithm complexity analysis (and compare it with other protocols), experimental results are absent. They assume bi-directional links; in practice, these are not always present. It also seems that the protocol as is would have a hard time dealing with packet loss due to the synchronization requirements. And the need for synchronization seems to be another weak point: How will all the nodes be guaranteed some sense of synchroneity in a truly distributed network? Future work might consider possible applications that would be used on top of this protocol. Many environments may not have need for such a protocol (hosts aren't this mobile and/or the network not dense), and certain applications may not work well with it. That is, given an application that required many "destinations" instead of just one (or a select few) how would the protocol behave? Would latency issues outweigh the value this protocol provides in a given environment? -- Mark Robson From yao@CS.Cornell.EDU Tue Sep 17 00:51:22 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H4pKh09361 for ; Tue, 17 Sep 2002 00:51:21 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 11 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 17 Sep 2002 00:51:20 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C30@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 11 Thread-Index: AcJd7md3LQdZHVRcRrG5+EZ2iIXDLQ== From: "Yong Yao" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8H4pKh09361 The paper presents a routing protocol, TORA, for ad-hoc networks. The main differences between TORA and other existing routing protocols are that TORA can recover efficiently when the network is partitioned, and support multipath routing. The authors also suggest that ad-hoc routing protocols should be reactive, distribute over nodes, and have low initialization delay, while not necessarily provide shortest paths. The basic idea of TORA is to maintain a height at each node for each destination. A node may send packets to one of its neighbor with a smaller height. Intially, the height is NULL. With an on-demand approach, a node will create a route in the form of a DAG using a query/reply method. After a change is detected, a link reversal will be established. Except the destination, any node without a downstream neighbor, maximizes its height and propagate this information further. This process repeats until the source determine a new path, or it gets back to the original node, which means the network is partitioned. Another process is then activated to erase the old route. The paper has some weakness too. TORA does not try to find a optimal route, so the length of a route could end up being much longer than the shortest one. That's a waste of energy, especially for routes with heavy traffic. How to synchronize among different nodes could be another problem. Since TORA is based on synchronized time stamp, it is required to solve the synchronization problem first, which is almost as hard as routing itself. It lacks a detailed simulation. Routing is a very complex problem, and it is very important to test a new routing algorithm through experiments. Although the paper has a evaluation section, I would like to see more experiment results and analysis, and comparision to other existing routing protocols. Yong Yao From ag75@cornell.edu Tue Sep 17 02:29:22 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8H6TMh25502 for ; Tue, 17 Sep 2002 02:29:22 -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 CAA17861 for ; Tue, 17 Sep 2002 02:29:19 -0400 (EDT) Date: Tue, 17 Sep 2002 02:29:19 -0400 (EDT) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 11 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The authors claim that the protocol described in this paper is highly adaptive, efficient and scalable. They say that it is best-suited for use in large, dense, mobile networks in which only several nearby nodes are typically involved in a reaction. The authors refer to other papers ou several occasions in their explanation, which makes their explanation of the algorithm difficult to understand. One of the positive things about the protocol is that it reacts quickly and efficiently to topological changes and is stable in the face of network partitions. It also decouples the generation of control messages from the rate of topological changes, thus minimizing the reaction to topological changes. The protocol guarantees loop-free routes and provides multiple routes to alleviate congestion. Finally, in the event of a network partition, the protocol detects the partition and erases all invalid routes within a finite time. Despite its benefits there are serious drawbacks to this algorithm. Some of the assumptions that are made are quite demanding. The protocol assumes that all transmitted packets are received correctly and in order of transmission. It also assumes that clocks are synchronized, without which the efficiency with which routes are reestablished is lost. And, finally, the protocol assumes the existence of two-way communication. The algorithm also does not guarantee that the route that it will provie will be the shortest one. Lastly, there were no simulations performed to confirm that the algorithm actually works and that it really does scale well. From ashieh@CS.Cornell.EDU Tue Sep 17 10:59:51 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HExoh18895 for ; Tue, 17 Sep 2002 10:59:50 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8HExoe12756 for ; Tue, 17 Sep 2002 10:59:50 -0400 (EDT) Date: Tue, 17 Sep 2002 10:59:50 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 11 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper contributes a reactive routing algorithm that, under a assumptions of no packetloss and preservation of ordering between packets, provides loop-freedom, and resilience to network partition. The requirement for using the shortest path is relaxed, allowing the algorithm to restrict propagation of topology change. Moreover, each node retains sufficient information to support multiple links between hosts (at the cost of O(d * N) space, vs O(N) for AODV). (The route discovery mechanism is very similar to that of AODV and DSR with aggressive caching, except no attempt is made to shorten paths) TORA introduces the concept of marking nodes with "heights". Packets flow from higher nodes to lower nodes (downstream). The height update rules ensure that routing updates are always propagated upstream (based on some possibly stale routing DAG); this prevents the spread of routing updates in one direction of the DAG. The update rules also prevent routing updates from propagating past nodes that still have a downstream connections; only when all downstream connections are removed by height updates in downstream nodes can updates continue upstream. This property reduces the need for hysteresis in deciding when to propagate updates (e.g. "settling time" of DSDV). When updates propagate to the source of the routing DAG, "reflections" (increases in height, which trigger a cascade of link reversals) back toward the originator of the update are generated. These reflections have identical propagation properties to the initial routing update; only when all links are reversed by reflection updates will the reflection reach the originating source. In this case, TORA detects a network partition. ** Shortcomings The correctness of TORA is highly dependent on the zero packetloss assumption. It is possible to construct traces where a network partition is not detected and incorrect routes are generated; similar traces may be constructed to induce cycles in the routing graph. Reordering of packets is perhaps less problematic, since heights are monotonically increasing and thus somewhat idempotent (propagation of outdated updates are possible). Given enough settling time, the routing DAG should stabilize. This paper completely lacks simulation information, and does not contain a space complexity comparison. Extensions - Add some measure of the quality of using a particular neighbor (e.g. hop count, loss rate). Preferably using rules for propagating information that allow metric updates to be propagated locally, with some relaxation on the accuracy of a statement. - Add some way of specifying or forcing alternate routes/load balancing, perhaps with some sort of economy (paying for routes using packets, with inflation of hop costs based on load). Alternatively, implicit stream caching (given a source, what is the next hop to use?) From smw17@cornell.edu Tue Sep 17 11:18:14 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HFIEh23251 for ; Tue, 17 Sep 2002 11:18:14 -0400 (EDT) Received: from cornell.edu ([128.84.84.84]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA19346 for ; Tue, 17 Sep 2002 11:18:14 -0400 (EDT) Message-ID: <3D8749C0.2090800@cornell.edu> Date: Tue, 17 Sep 2002 11:26:56 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 11 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit TORA The TORA routing protocol is a source-initiated reactive routing protocol. TORA considers the network as a graph, and during each route creation step TORA configures the individual network links to create a destination- rooted DAG. This is achieved by assigning each node a height function derived from five distinct values providing destination id, originator id, reference level, delta from the reference level, and a reflection bit. These five values provide the ability to form a route by assigning appropriate link directions, and also maintain said route as link topologies change over time through intelligent link (direction) reversals. Once the DAG is configured, network traffic is limited to transmitted data, or reactions to broken links. Broken links only cause a reaction when severing the link breaks the last downstream connection the node has, and the propagation of the link breakage is limited to those nodes that need to update their configuration to deal with the topological changes. TORA will also detect a partition in the network in finite time through the reflection bit, and clear invalid routing information from the network. TORA is an interesting routing protocol with a number of benefits. At route creation, it sets up a complete set of routing paths (DAG creation) in the network. As such, TORA is relatively robust in the face of link failures, demonstrating an average case of k/2 downstream links for k total links between nodes. It also localizes the reaction to link state changes, avoiding the need for global dissemination of routing changes unless necessary. This suggests that TORA should be more scaleable than other protocols we have investigated, and should be more tolerant of highly dynamic network topologies. The graceful handling of network partitioning is another attrractive feature of this protocol, as compared to other protocols we have investigated. TORA is capable of detecting a network partition (by detecting a reflected reference level) and clearing out inactive routes, in comparison to protocols relying on high-level timeouts to detect partitions. This paper also has a few weaknesses. The first, which is mentioned in the paper, is that by decoupling route creation and route matinence, the DAG will over time become less optimal as links reverse in reaction to topology changes. The authors also fail to deal much with network losses, especially during route creation. Given the high rate of loss and contention of broadcast packets, the effects of packet loss should be considered in the analytic formulation of the network behavior, especially for a protocol intended for use in ad-hoc wireless networks. The first improvement to this work would be a simulation study of actual performance in realistic networks, to determine how much the factors neglected in the analytical treatment will affect performance and behavior. The second improvement, which is hinted at in the paper, is to provide a low-bandwidth mechanism for global dissemination of routing information, ideally a mechanism for the system to detect potential improvements and re-direct the graph without requiring a complete route regeneration. From liuhz@CS.Cornell.EDU Tue Sep 17 11:28:31 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HFSUh25622 for ; Tue, 17 Sep 2002 11:28:30 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 11 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 17 Sep 2002 11:28:30 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5F4@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 11 Thread-Index: AcJeXuBbt1wEyZuRQx63hqdPyYXGtQ== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8HFSUh25622 This paper introduces a protocol know as the temporally-Ordered Routing Algorithm(TORA). This protocol is highly adaptive, effieient and scalable; being best-suited for use in large, dense, mobile networks. It's an on-demand protocol, thus no periodic advertisements are necessary. In this protocol, the routes are represented by some directed acyclic graphs(DAG) rooted at the destinations. Each node maintains its height, the heights of all its neighbors and a link-state array with an entry for each adjacent link. Apon stabilization, these link-state arrays represent the directions that the routes should follow. When a node wants to communicate with some destination and no routes to the destination are available, the node will broadcast a QRY packet. TORA uses a route_required flat to suppress duplicate QRY packet. The QRY packet is broadcast until it reaches some node that has at least one downstream link. Then some UPD packet is sent back and the height for all the nodes that broadcast the QRY packet are built one by one backwards. TORA uses FUll/Partial reversal method to maintain routes when some node loses its last downstream link. This method can also be used to detect nework partitions and accordingly, a CLR packet is broadcast to erase the invalid routes in that case. Strength 1. On-demand routing protocol, thus it has the advantages shared by this class of protocol 2. Loop free. The temporally-ordered heights guarantee the routes are loop-free. 3. multi-path routes. This protocol can find multiple src/dest paths. Multiple paths are useful to alleviate the congestion and make this protocol more flexible in face of link failure. 4. Localization of reation to topological changes. Only nodes that lost all their downstream links are affected. This saves bandwidth but may decrease the route optimalty as discussed later. 5. This protocol can detect network partitions and erase all the invalid routes within a finite time. (3 passes of the set of affected nodes). weakness 1. This protocol requires accurate temporal ordering of events distributed in the networks. This may require help from some centralized device. That's not recommended in ad-hoc network. Although the author claimed it's possible to establish the temporal order of events with some "logical clocks" which can be implemented by counters with no actual timing mechanism, I think that mechanism must be quite complex and requires much network communication for coordination. 2. The protocol doesn't always give the shortest route. Initially, there is some data that indicates the distance to the dest, but this data will be damaged due to link reversals. The authors did present some possible enhancement that MAY improv the route optimalty, but the result is unpredictable without any simulation. 3. This protocol is built on the assumption that each node has a unique ID. Is it easy to assign a unique ID to each node and maintain the mapping from the ID to IP address of each node in a large network? 4. The paper is less pervasive without simulation data. It would be very interesting to see how the protocol performs in the simulations and how the presence of periodic refress packets etc as well as network desnity effects its performance. From adam@graphics.cornell.edu Tue Sep 17 11:41:47 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HFflh28588 for ; Tue, 17 Sep 2002 11:41:47 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g8HFff0k036188 for ; Tue, 17 Sep 2002 11:41:42 -0400 (EDT) Date: Tue, 17 Sep 2002 11:33:51 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 PAPER 11 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper begins w/ a review of the previous algs and the disadvantages of them. Briefly it mentions GB and it's instability w/ partitioned networks, LMR and "false reply" propogation, DSDV and single path routing, WRP w/ it's overhead and finally DSR w/ scalability issues. In the presenting of their own alg, they try to have a routing alg that doesn't suffer from partitioning problmes and to minimize reaction to topological changes. The protocol will depend on localized message propogration, not global which will help to suppress topological sensitivity. The protocol is basically three functions (creating routes, maintaining and deleting them). There are three different control packets (one for each function) a query, update, and clear which each serve seperate function. The paper progresses into detailed explanation of the three functions and how they work. I don't like this paper (as w/ many of the papers we have read) for lack of tangible results. The implementation of this stuff is critical to knowing if the "theory" behind this provides better results. I wish that this paper had acknowledged the problem w/ all other papers in this field that no testing was done, and then did some, but it didn't. I might further find issue w/ scalability, there is a large amount of data that each node must maintain, and the scale up to huge systems, would be an issue. The thick and hard to read implementation of this alg could have been better presented as well, but that's simply a matter of having to read how it works again and again. I feel that having more information on implementation and low level details is better than leaving out too much so that no one can implement it (kudos to them for referencing a more detailed version of things when they glossed over some important details). I did like this paper as an example of a routing alg that would preform well in overcoming the shortcomings presented in the introduction and I generally think it is an improvement over what was presented before. Since this system works in an on-demand style if there is no traffic through your node to an area of the network there is no wasted effort, maintaining links there. This I believe is a much better approach than trying to expend resources unilaterally over the whole network. I think that further work could include a serious analysis of this network, especially w/ some sort of help from a GPS based input. I could imagine some sort of melding between the previous paper (Broadcast Storms) use of location and this papers routing style to make a decent (yet possibly overly complex) ad hoc network for dense, highly mobile situations. From vrg3@cornell.edu Tue Sep 17 11:46:03 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HFk3h29545 for ; Tue, 17 Sep 2002 11:46:03 -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 LAA24528; Tue, 17 Sep 2002 11:46:00 -0400 (EDT) Date: Tue, 17 Sep 2002 11:46:00 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 11 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper introduces the Temporally-Ordered Routing Protocol (TORA). TORA's big strengths are that it always produces loop-free routes, efficiently handles network partitions, can handle multiple routes between hosts, and is scalable. TORA is reactive; routes are generated as needed when prompted by a source. A DAG is generated with the destination at the root. The structure of the DAG is not stored in complete form at any node; instead, each node only has knowledge of its most immediate neighbors. Each node has a "height," and only transmits to its neighbors of lower height. When the DAG needs to be adjusted, link directions are reversed (and so height relationships as well). An important strength of TORA is that route changes only require local reconfiguration; when the topology of the network changes it is not necessary to broadcast the change to the entire network. This allows it to respond more quickly to changes in topology. At the same time, it does have the weakness that the routes are not necessarily the shortest possible routes. In fact, as the routes are maintained and modified, the routes will become less and less efficient. A goal of the authors was to reduce routing overhead, which they have mostly succeeded in, but sub-optimal routes do introduce another kind of overhead. Since the nodes are meant to have a synchronized clock of some kind anyhow, a periodic scheduled reset of the entire network may help. Another big weakness is that TORA was designed with the assumption of a reliable medium in which all packets are received intact and in order. This simply is not a realistic assumption for an ad-hoc wireless network. The obvious follow-up to this research is to perform a simulation. While the mathematical arguments make sense, it is important to see just how much the protocol is affected by more real-life issues. From pj39@cornell.edu Tue Sep 17 11:48:59 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HFmxh29728 for ; Tue, 17 Sep 2002 11:48:59 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA26958; Tue, 17 Sep 2002 11:48:55 -0400 (EDT) Date: Tue, 17 Sep 2002 11:48:55 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200209171548.LAA26958@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: pj39@cornell.edu Reply-To: pj39@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: pj39@cornell.edu X-Originating-IP: 128.84.223.189 Subject: 615 PAPER 11 In this paper the authors describe a highly adaptive distributed routing algorithm for MANET's called TORA. The algorithm is best suited for large and dense mobile networks. This paper routinely emphasizes the drawbacks of other existing protocols like GB, LMR, DSDV, WRP and DSR. The major drawback with these protocols the author points out is they maintain only a single path to route to a destination. The key concept behind TORA is to minimize the reaction to topological changes as control messages generated is localized to a small set of nodes. The authors considers the network to be a destination oriented directed acyclic graph (DAG). The nodes in the graph are lexicographically ordered. The idea is that when there is a link failure the node select a new height that is a global maximum. This results in link reversals of the neighbors. The major drawback of the paper are that it assumes all the links are bidirectional (as link reversal is the basis of this paper). The papera also assumes the communication is channel is error free and hence doesnt talk about retransmission procedure or errror detection and correction. The paper randomly refers to and compares with other papers, describing in details about other protocols which at times becomes confusing and makes it hard to understand the TORA algorithm itself which the author is trying to explain. I found the algorithm as a whole difficult to comprehend at times as lots of parameters are considered and conditions exist. Since there is no distance estimate for the links over time and there are link reversals to take care of broken links the destination oriented DAG may have less optimal routes at a later time. The paper gives a comparison with other protocols in terms of time complexity and communication complexity. It doesn't talks about space complexity and memory requirements. Evidently in TORA each node maintains a lot of information like its own height, height of its neighbors, route required field, each time link (i,j) became active etc. Future work could be directed towards periodical propogation of control packets from the destination. Also periodical but less frequent propogation of control messages which are global and not localized to neighbors could be used for determining more opimal routes. From mp98@cornell.edu Tue Sep 17 11:50:24 2002 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.10) with ESMTP id g8HFoOh00539 for ; Tue, 17 Sep 2002 11:50:24 -0400 (EDT) Received: from dhcp226.libecafe-dhcp.cornell.edu (dhcp226.libecafe-dhcp.cornell.edu [128.253.117.226]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA21892 for ; Tue, 17 Sep 2002 11:50:22 -0400 (EDT) Date: Tue, 17 Sep 2002 11:50:24 -0400 Mime-Version: 1.0 (Apple Message framework v543) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 11 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <2E171C7B-CA55-11D6-848A-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.543) This paper describes a complicated protocol and algorithm for loop free routing in a wireless network. For a given destination, nodes will propagate a route request, maintain soft state, and remember their route in reaction to the query's response. This is quite similar to previous algorithms, but TORA is set apart by its use of time tags to maintain the order of events and the use of reference levels (with partial reversal of links) to keep small network topology changes localized. The most notable contribution is the presence of reference levels on nodes. These reference levels characterize the nature of route lost and allow for fast recognizing of partitionings. In addition this algorithm avoids flooding to some extent (information only needs be forwarded to certain hosts who are interested in routes) and is the first algorithm we've discussed so far with an explicit mention of multiple routes, possibly allowing for load balancing. The paper itself puts out its fundamental weaknesses. It's assumptions are extreme (perfect transmission, bi directional links, etc) and its performance measurements are just worst case analysis. Future work should be done either through careful analysis or good simulation to determine how well TORA works in practice. From aed13@cornell.edu Tue Sep 17 11:52:41 2002 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.10) with ESMTP id g8HFqeh00720 for ; Tue, 17 Sep 2002 11:52:40 -0400 (EDT) Received: from andyd-laptop.cornell.edu (syr-66-67-66-109.twcny.rr.com [66.67.66.109]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA28897 for ; Tue, 17 Sep 2002 11:52:37 -0400 (EDT) Message-Id: <5.1.0.14.2.20020917113709.00affe98@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 17 Sep 2002 11:52:52 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 PAPER11 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks" builds on the work of the GB protocol class family to describe Temporarily Oriented Routing Algorithm (TORA). The protocol utilizes a temporal sequencing of events, such as topological events to define a strict lexicographic order. This ordering is used to construct a directed-acyclic graph to a destination, or so called "destination-oriented-DAG". This paper makes succinctly outlines design choices and its assumptions, which is some cases are fundamental different design priorities compared to earlier papers in the area. While TORA maintains existing design goals of distributive routing, low network overhead, and scalability, it adds two key requirements while discarding the common requirement of finding the shortest path or optimal route. TORA adds the requirements of multiple routing paths to destinations and to "de couples the generation of potential far-reaching control messages form the rate of topological changes". The paper outlines in great mathematical detail the protocol mechanism including the 3 phases of operation, route creation, route maintenance, and route erasing and their respective QRY, UPD, and CLR packets. The complexity of the algorithm makes it appear difficult to understand and implement, but the key concept of route reversal enables topology to adapt quickly with minimal overhead to link failures. Like other reactive algorithms route information is only created and maintained on a needed basis. The complexity of the algorithm which is more easily understood by viewing the decision trees and relatively few figures, makes it understandable that they have failed to implement the protocol as of the date of this paper. No simulation results, but a mere complexity analysis compared to other protocols is all that is available. --Andrew Davis From mtp22@cornell.edu Tue Sep 17 11:54:57 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HFsvh00885 for ; Tue, 17 Sep 2002 11:54:57 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA05723 for ; Tue, 17 Sep 2002 11:54:56 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 11 Date: Tue, 17 Sep 2002 11:56:13 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <0209171156130B.00149@narnia> Content-Transfer-Encoding: 8bit The major contribution of this paper is the TORA routing protocol, which seeks to have all of the advantages of prior routing protocols without any of the disadvantages. In particular, the protocol attempts to provide multipath to avoid congestion; to improve upon route performance in highly dynamic networks; and to conserve bandwidth in the case of network partitioning. It theoretically appears to accomplish this; however, it introduces disadvantages that don't appear in the prior routing protocols that TORA is trying to improve upon. One of these disadvantages is the need for synchronization. The paper assumes that all packets are received correctly and in order. This is like having a mini TCP at the link layer, which may be asking too much. Another disadvantage is sub-optimal routes. The paper mentions that over time the routes may become sub-optimal and claims that this is not that important, but we don't know because of another weakness in the paper: the lack of simulations. The work in this paper could be expanded upon by performing simulations of the protocol. This could shed light on a number of issues. In particular, the feasability of different synching schemes, the unimportance of sub-optimal routes, and the benefits over prior protocols. From vivi@CS.Cornell.EDU Tue Sep 17 12:00:02 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HG01h01929 for ; Tue, 17 Sep 2002 12:00:01 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper11 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 17 Sep 2002 12:00:01 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D14B4AB@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper11 Thread-Index: AcJeY0jI6/IL/9N1Q7OcMpE7VfMw5Q== From: "Vivek Vishnumurthy" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8HG01h01929 TORA: The unique features of the protocol suggested by this paper are: its very efficient handling of partitions and fast reaction to topological changes in the network, and the possibility of multiple routes to the same destination to avoid congestion. The time taken by the network to stabilize after link failures or even partitions is very small. The routing is also loop-free. The paper outlines existing protocols, and describes their weaknesses. It lists out the desired qualities of a "good" routing protocol. It describes the motivation behind the protocol suggested. This feature has not been seen in any of the papers we have seen so far. One of the main weaknesses of the paper is that it is not very readable. The paper very quickly dives right down to the implementation details, without describing what is being done. The paper does not say whether the protocol permits simultaneous multiple traffics (with different destinations) at all, and if so, how it does the same. Maintaining all the suggested data structures for all the destinations would make the protocol untenable in large dense networks with heavy traffics; the protocol would not be scalable. The paper also does not clearly explain how the logical clocks are implemented. The paper has not provided any simulation results. In the worst-case performance comparison, the space requirement also could have been considered. From ks238@cornell.edu Tue Sep 17 12:00:14 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HG0Eh02390 for ; Tue, 17 Sep 2002 12:00:14 -0400 (EDT) Received: from ks238.cornell.edu (syr-24-24-18-11.twcny.rr.com [24.24.18.11]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA25892 for ; Tue, 17 Sep 2002 12:00:10 -0400 (EDT) Message-Id: <5.1.0.14.2.20020917115742.01ce08b0@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 17 Sep 2002 11:59:31 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 PAPER #11 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In this paper, a new protocol, different from those that have been encountered thus far was presented. The protocol, called TORA, is a routing mechanism for mobile adaptive networks which has many of the advantages that previous protocols studied have had, with the addition of being designed specifically to "minimize reaction to topological changes." One way it achieves this is by sacrificing the idea of finding a shortest distance path between nodes, and by allowing multiple paths between nodes, which can all be used. This way, should a link go down, an alternate route, that has already been discovered can be used without the need of rediscovering a shortest-distance path. This is ideal for a network with a large degree of topological change as it would greatly reduce the amount of CPU and memory usage and will decrease congestion in the network. The authors go into a discussion regarding the fundamentals of the protocol and include descriptions regarding route creation, maintenance and deletion (which is used in detecting and eliminating partitions). They conclude the paper with a discussion of comparing the worst-case runtimes for each of the algorithms that have been developed thus far. First, on just a mechanics level for writing papers, I felt that it was a bad idea for the authors to assume that their audience had previously read many of the papers that are referenced by them or had previous knowledge regarding the TORA protocol. It is usually helpful to provide a summary of the referenced material rather than just referencing it. I found it difficult to follow their discussion of the algorithm for this reason. In addition, overall it seemed to be a pretty convoluted discussion that should have been presented a little better and clearer. Despite the fact that no simulation or their results were given making it more difficult to find problems with the TORA algorithm, I did want to mention some weaknesses. I found that while I was following the algorithm, one reason I kept getting lost was because of the many packets and variables that needed to be tracked while discovering or maintaining routes between two nodes. This brings to light an interesting question of how much memory/energy at each mobile node and network bandwidth is actually saved with this protocol. Moreover, the question of scalability once again comes into the picture, especially since they are claiming the protocol is best suited for large networks. Another question I had pertains to the use of multiple routes to a certain node. This seems to have some inherent problems in larger networks. The author doesn't discuss optimal route finding especially after a failure has been recovered. This would mean that routes, which are not optimal would be used, which is dangerous in larger networks especially from a memory conservation point of view (which is a key goal of the protocol). Bottom line, not having experimental data makes it difficult to criticize or defend the protocol in regards to this issue and many more. It just seems the paper is very incomplete without it. From sc329@cornell.edu Tue Sep 17 12:15:23 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8HGFNh05769 for ; Tue, 17 Sep 2002 12:15:23 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA27261 for ; Tue, 17 Sep 2002 12:15:20 -0400 (EDT) Message-Id: <5.1.0.14.2.20020917121212.00b06df0@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 17 Sep 2002 12:15:26 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 11 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chandrakumar A highly adaptive distributed routing algorithm for mobile wireless networks Summary : This paper presents a distributed routing protocol, temporally ordered routing algorithm (TORA), for MANET. The authors start the discussion by eliciting some of the shortcomings of the existing algorithms. They claim that routing optimality is not that important in a dense adhoc network. Moreover computing routes between every source/destination places a hugu stress on the network bandwidth. Most of the previous protocols computes only a single route between any source/destination pair, which would result in more congestion. The main characteristics of TORA are loop-free routes, multiple routes to destination, quick establishment of routes in a dynamic topology and localizing the network reaction in case of failures, thus prohibiting any need for 'far-reaching' messages. It decouples the generation of potentially far reaching control message propagation form the rate of topological changes. The three main functions of the of the protocol are creating routes, maintaining routes and erasing stale routes. These operation are done with the help of QRY, UPD and CLR control messages.Route discovery is accomplished by the construction of a DAG rooted at the destination. Every node is associated with a 'height' value, which can be totally ordered. The height of the neighboring nodes determine the direction - upstream or downstream, of the links. When a node does not have any more downstream links, the node selects a new local maxima as its reference level. IF this value results in the loss of downstream links to its neighbors, they in turn selects a higher reflected reference value, which gets further propagated until every node had downstream links. If this reflected value finally reaches the originating node, partition is detected and the node can erase some of the entries. Comments: - TORA assumes that the links are bi-directional, which may not be case with most of mobile networks. - Correct order of transmission is difficult to achieve and clock synchronization is a serious issue in distributed networks. - The paper does not have any simulation results, though the authors claim work is underway. Though the worst case scenarios presents a rosy picture of the performance of the protocol. - The authors does not mention who is it advantageous in maintaining multiple routes in a dense mobile environment.