From kwalsh@CS.Cornell.EDU Wed Sep 25 13:14:59 2002 Received: from kwalsh.cs.cornell.edu (dhcp98-75.cs.cornell.edu [128.84.98.75]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8PHExh13218 for ; Wed, 25 Sep 2002 13:14:59 -0400 (EDT) Message-Id: <5.1.1.6.0.20020925125111.00a82e98@popsrv.cs.cornell.edu> X-Sender: kwalsh@popsrv.cs.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Wed, 25 Sep 2002 13:14:58 -0400 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 22 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed HARP - Hybrid Ad hoc Routing Protocol This paper introduces HARP, a hybrid reactive/proactive protocol. The protocol builds on a forest construction algorithm (DDR) presented in a previous paper, by adding HARP, a simple intra/inter-zone routing protocol. Although significant space is devoted to DDR, the algorithm is not fully describe. DDR proceeds in six phases. Essentially, it constructs a forest of trees by having each node place itself below the neighbor of highest degree. Once the tree is built, neighboring zones are discovered and advertised by the border gateway nodes. HARP is quite simple: inside a zone, routing follows the DDR tree. Outside a zone, a node floods a query along the DDR tree to neighboring zones, where the process is repeated. HARP additionally maintains a "stability" metric based on the longevity of zone-zone connections. This metric is used to select among alternate routes, and to refresh routes periodically (less stable routes are refreshed more often). The contributions of the paper are not clear. The DDR algorithm is not particularly sophisticated, at least as it is presented here, and was previously published. The HARP route discovery mechanism is the obvious method for routing in disjoint zones, and is not particularly novel. The stability metric and use is more interesting, but very little space is devoted to this aspect of the protocol. A number of problems are evident: - The DDR tree construction algorithm appears to be highly synchronous (a difficult proposition in an ad-hoc network), although perhaps this is a misunderstanding - DDR assumes, as does the evaluation/analysis, that all nodes simultaneously decide to form a network. This is not the common case in an ad-hoc network, as far as I can imagine. Rather, nodes are likely to join the network in small numbers, perhaps reaching a steady state where nodes come and go in small numbers. It is not discussed how a node can join an already existing DDR forest. - The routes discovered by HARP (both inter and intra zone routes) are likely to be very far from optimal: all traffic flows through the root of the zone (except in the case where source and dest are located in the same zone and on the same branch of the tree), and many links are never used at all. This leads to long routes, as well as heavy traffic near the center of each zone. - Finally, the stability metric assumes that past longevity is an indication of future stability. This assumption should be motivated, as it is possible that longevity and future stability are unrelated or negatively correlated (ie, in a uniform random process). From shafat@CS.Cornell.EDU Thu Sep 26 00:33:57 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 g8Q4Xuh01795 for ; Thu, 26 Sep 2002 00:33:56 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615 PAPER 22 Date: Thu, 26 Sep 2002 00:33:56 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D1507BF@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 22 Thread-Index: AcJlFe02WP+/4a0aR36bETYMoziHow== 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 g8Q4Xuh01795 This paper presents yet another hybrid ad hoc routing protocol called HARP that combines the proactive and reacting routing schemes to develop a bandwidth efficient, low delay routing protocol. It uses the general idea of intra- and inter-zone routing to connect the entire network. However, what makes it different from other hybrid routing protocols like ZRP is its modular structure, and the dependency on the Distributed Dynamic Routing (DDR) protocol to do the 'dirty work' of giving the network a logical shape by creating zones. HARP then runs on top of DDR and takes care of the two main routing tasks - path discovery and path maintenance. This allows HARP to work more independently and focus more on the routing aspect of things. What struck me most about this paper is the lack of depth in explaining the functionality of both DDR and HARP. For example, the six phases that DDR goes through in order to establish the zones and the routing tables in the nodes, were simply stated without any sort of elaboration. It would be quite impossible on the reader's part if he/she were to try to implement DDR based on the information provided in the paper. Quite a few issues regarding zone creation were also left out of the discussion. What happens when a node fails? What algorithm is used for preferred neighbor election? How does DDR accommodate for changes in the network topology? How is stability defined from DDR's perspective? HARP was also presented in a similar haphazard fashion. The lack of any quantitative analysis is another weakness of this paper. Although, it does a comparison with other hybrid routing protocols, but the question of whether HRP works in the first place was never properly shown. Its performance can be validated using simulations and testing the protocol under various conditions. More details on load balancing, duplicate suppression, link failures need to be looked into. There is no concept of fall-back mechanism in the current version of HARP and this is something that can also be worked upon in the future. From liuhz@CS.Cornell.EDU Thu Sep 26 00:52:27 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 g8Q4qQh04314 for ; Thu, 26 Sep 2002 00:52:27 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615 PAPER 22 Date: Thu, 26 Sep 2002 00:52:26 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE627@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 22 Thread-Index: AcJlGIKiQY7q/Py+SjmsAcQSz2uW5g== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8Q4qQh04314 This paper presents a hybrid routing protocol called HARP. HARP proposes a new architecture that seperates topology creation from route determination, which makes it a routing protocol with a clear and modular design. HARP incorporates DDR into itself to create hierarchical topology and to provide intra-zone routes. DDR uses only beacons between neighbors to acheive these. Therefore, it avoids global broadcast throughout the networks, thus it can reduce the control traffic. HARP uses reactive inter-zone routing protocol. Unlike flooding, route request PREQ is only tranferred between gateways. Thus bandwidth and energy are preserved. Path discovery algorithm is quite straightforward and similar to AODV in some way. Every gateway remembers its previous hop(gateway) from which it receives the PREQ and to which it will send PQEP if the it's on the way to the destination. HARP will reflesh path periodically, thus keeps the path up-to-date. However, this will introduce some overhead if the network topology changes little. Therefore, it's very important to choose an appropAriate path discovery update time to reflet the mobility of the network. HARP is a hierarchical routing protocol. It can not find the optimal routes in some cases (w.r.t hops). And nodes along the path from in-gateway to out-gateway, especially the gateway nodes will be overloaded. Thus, they are likely to become the bottlenet of the network. Some details are missing in the algorithm. E.g. what will a gateway do during route discovery state, if it already has an entry indicating next-gateway towards the destination. How to clean the original path when going to do path refreshment. Clearly, sending a CLR packet along the path and every gateway deleting next-hop when receives the CLR will do. But nothing about this is said in the paper. Some simulation about the algorithm, especially How the choose of different path refreshment rate will affect the performance of the protocol in case of networks with different mobility, will be interesting. From jsy6@postoffice2.mail.cornell.edu Thu Sep 26 01:50:11 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 g8Q5oAh13512 for ; Thu, 26 Sep 2002 01:50:10 -0400 (EDT) Received: from Janet.cornell.edu (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA23287 for ; Thu, 26 Sep 2002 01:50:10 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926014902.00b4aa28@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 01:49:34 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 22 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The main objective of HARP (hybrid ad hoc routing protocol), a zone hierarchical routing protocol, is to provide a scheme to improve delay performance by reducing the probability of path failure via establishing the most stable path from source to destination. The logical zone hierarchy of nodes is created by DDR (which does not stand for dance dance revolution, but distributed dynamic routing). Therefore, intrazone routing is reduced to forwarding messages along a path precomputed by DDR. Interzone routing in HARP can be broken down into path discovery and path maintenance. Path discovery is done by via gateways. The out-gateways update the stability value as they propagate the route request zone to zone. Path maintenance consists of path refreshment, path waiting time, path error, and new path discovery phases. Path refreshment is the periodic construction of a path before the path discovery update time. The traffic is transferred to this path right after path refreshment. This helps avoid path failures due to network topology changes. If, during path refreshment, a link failure is detected, traffic is held for certain duration of time so that it can receive some routing information (path waiting) and a path error is sent back to the source. When a source receives a path error, a new path discovery is triggered. The main measurement of this algorithm is stability. Stability is defined as "the connection stability of a zone regarding its neighbors". It does not mention how this stability is calculated and measured. Also, in order to ensure stability, proactive and reactive path recovery procedures are used. Depending on the path discovery update time, periodic path recovery can result in contention and collision, thus increasing the delay that this protocol strives to improve. From hs247@cornell.edu Thu Sep 26 01:52:42 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-1.nyroc.rr.com [24.92.226.177]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8Q5qfh13617 for ; Thu, 26 Sep 2002 01:52:42 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g8Q5qfI15039 for ; Thu, 26 Sep 2002 01:52:41 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926015219.00baff68@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 01:52:42 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 22 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Like ZRP, HARP is a hybrid ad-hoc routing protocol. How HARP differs from ZRP, is that the zones established in HARP do not overlap. It bases its zone discovery on DDR which is a dynamic routing algorithm discussed in another paper. In fact, in the protocol described, DDR takes care of intrazone routing, and HARP is only concerned with interzone routing. The authors claim that this separation of concerns is good and allows them to keep HARP very simple. DDR zone discovery is based on each node electing a node to be the preferred neighbour. The preferred neighbour is the node with most neighbours. It claims that this will converge and separate nodes into forests (distinct zones). The nodes in a zone that have links to nodes in other zones are called gateways, and it's through these gateways that interzone packets are routed. HARP is very simple. When a route to an node not in the zone is needed (discovered by its lack of presence in the intra-zone table), a prep packet is sent to all the gateways. The prep packet is then sent to the next zone. If the destination is in the zone, the prep will be routed to the destination via intrazone routing. If not, the prep packet is sent to all the gateways and so on. When the packet (can be from several routes) reaches the destination, the best route is chosen and returned to the source. The path is chosen by a metric called stability. The stability is a measurement of the strength of the connection between 2 gateways. The ideas presented in this paper are simple, maybe too simple. It doesn't seem ready to be a protocol. First of all, the multicast to all the gateways seems to be too much and from my perspective, this could mean very heavy traffic. A mechanism needs to be introduced so duplicate messages are not sent. Also, when a destination receives a prep. How long does it have to wait for to receive other preps to decide what is the most stable route? Also the path maintenance algorithm needs more detail. Maybe it's not in the scope of HARP, but more in DDV, but what happens when nodes move, intuitively, zone change, and this is not really addressed in the paper. Future work from stemming from this paper should include working out the details and seeing how this protocol can be implemented. Then an evaluation of the protocol is needed and then we can compare it to ZRP. Right now, there is only a mathematical evaluation. From bd39@cornell.edu Thu Sep 26 02:18:25 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 g8Q6IPh17628 for ; Thu, 26 Sep 2002 02:18:25 -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 CAA08849 for ; Thu, 26 Sep 2002 02:18:24 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926004356.023889a0@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 02:17:21 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 22 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed HARP contributes another zone based routing protocol. In HARP, routing and zone construction are separated into 2 different protocols. HARP seeks to modularize zone construction from zone routing, limit flooding of forwarding nodes and apply a metric for zone stability. Distributed Dynamic Routing (DDR) handles zone construction. DDR performs clustering by connecting every node with a node of highest degree in its neighborhood. After neighborhood clustering is performed, an inter-tree routing table is built and stored in the among the zone's members. Neighboring zones are located through gateways (nodes that can broadcast to more than one zone) and zone link stability is maintained with a ZID. (How this value is updated is rather confusing.) Intrazone routing is performed using the spanning tree that was formed by DDR. Interzone routing is performed by a zone broadcast for discovery, appending gateways to source routes in the broadcast, and unicasting the source route back to the source. Stability information is maintained in the node along the path. Stability is monitored by gateways on the path, and when stability falls below the requested stability, a path error is unicast back to the sender. The description of the routing protocols in this paper are very vague. It is not clear how HARP benefits significantly over ZRP in separation of zone routing and zone construction. There is a no simulation and the mathematical analysis seems lacking. Some of the assumptions in the construction of the DDR is a time order sequence of events for a distributed collection of independent nodes. Stability is not clearly defined nor is there evidence as to whether it is valid. From mr228@cornell.edu Thu Sep 26 02:25:35 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 g8Q6PYh19209 for ; Thu, 26 Sep 2002 02:25:34 -0400 (EDT) Received: from cornell.edu (syr-24-58-48-238.twcny.rr.com [24.58.48.238]) by cornell.edu (8.9.3/8.9.3) with ESMTP id CAA19079 for ; Thu, 26 Sep 2002 02:25:34 -0400 (EDT) Message-ID: <3D92A870.FB7F4115@cornell.edu> Date: Thu, 26 Sep 2002 02:25:52 -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 22 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper presents another hybrid routing scheme for ad hoc networks. They separate it into two logical layers, one to setup the logical network structure, and another to find and maintain routes. First they use something they call Distributed Dynamic Routing (DDR) to setup a tree (actually a forest) like structure in the network graph. Then, like the last paper, they have this notion of splitting the network into neighborhoods. They again use a proactive routing algorithm within a neighborhood and a reactive one outside the neighborhood. Since neighborhoods do not overlap and gateway nodes are explicitly set to be either incoming or outgoing, they do not have the same issue with excess flooding that ZRP had. While a mathematical/theoretical analysis is provided, no experimental results are given. Future work is obvious (and they mention it in their conclusion): Implement it! And compare with ZRP and ZHLS... -- Mark Robson From xz56@cornell.edu Thu Sep 26 02:55:02 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 g8Q6t2h24158 for ; Thu, 26 Sep 2002 02:55:02 -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 CAA03602 for ; Thu, 26 Sep 2002 02:55:02 -0400 (EDT) Message-ID: <00c201c26529$a04c3a90$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 22 Date: Thu, 26 Sep 2002 02:54:57 -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 HARP, also a hybrid routing protocol, uses the same concept of "routing zone" as ZRP. But they are different both in intra-zone and inter-zone routing. HARP uses DDR alg. for the intra-zone routing. DDR is a localized alg., only need to maintain the number of neighbors and choose the best neighbor thus produce a forest (this is quite similar to CEDAR in choosing the dominator), which has advantage over a LS solution w.r.t. the overhead, but it can not yield optimal paths for most source-destination pairs. Upon DDR, HARP is in charge of the inter-zone routing. It introduces the parameter "stability" as its most import criterion when choosing paths. HARP emphasize the stability rather than the optimality. Unlike ZRP, the routes are maintained in a kind of proactive way. For ad hoc network, it seems to me that it's always preferred not to have anything fixed or any node special. But HARP takes a hierarchical approach, using fixed zones with some gateways and even assigns names to zones which is difficult to imagine how it works when all the nodes in a zone are of highly mobility. ZRP contributed by introducing the concept of routing zone and just used the classical protocols of LSR and DSR (with some optimization) for intra- and interzone routing. HARP tried to make some change on the specific routing scheme. But it seems, there isn't much improvement. DDR doesn't reduce much control msg and gives paths far from optimal. HARP taking advantage from the assumed fix clusters and a very proactive-like scheme, claims high reliability. But it's not very convincing without any comparison either analytically or from simulations. From ag75@cornell.edu Thu Sep 26 04:22:01 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 g8Q8M1h07902 for ; Thu, 26 Sep 2002 04:22:01 -0400 (EDT) Received: from sanya (r105361.resnet.cornell.edu [128.253.240.52]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with SMTP id EAA01715 for ; Thu, 26 Sep 2002 04:22:00 -0400 (EDT) Message-ID: <002501c26535$d26176b0$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 22 Date: Thu, 26 Sep 2002 04:22:15 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4910.0300 In this paper the authors present HARP, which they claim is a bandwidth efficient low-delay routing protocol for mobile ad hoc networks. HARP is a hybrid protocol combining reactive and proactive approaches. HARP generates and selects paths based on zone level stability, which is an extension of node level stability that was previously used in other algorithms. This algorithm only concerns with finding and maintaining a path between source and destination, and leaves topology generation to DDR. Thus, a part of the paper is devoted to explaning DDR. Though the authors could have done a better job with the explanation, we know that DDR consists of 6 phases during which the algorithm creates zones, which are then used by HARP. There is no simulation to speak of for this algorithm. The only thing that the authors have is a mathematical analysis that involves comparison of the communication overhead. For this analysis, the authors immediately assume the nodes in the network are distributed uniformly. Thus, they completely ignore what happens in other cases. Since there is no simulation, it is not clear how this algorithm would perform when compared to others, such as ZRP. Practical results are needed to evaluate this algorithm properly. From tmroeder@CS.Cornell.EDU Thu Sep 26 10:02:48 2002 Received: from dhcp99-233.cs.cornell.edu (dhcp99-233.cs.cornell.edu [128.84.99.233]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8QE2lh10871 for ; Thu, 26 Sep 2002 10:02:47 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g8QE2lK23966; Thu, 26 Sep 2002 10:02:47 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15763.4999.478998.130083@dhcp99-233.cs.cornell.edu> Date: Thu, 26 Sep 2002 10:02:47 -0400 To: Emin Gun Sirer Subject: 615 PAPER #22 X-Mailer: VM 7.07 under Emacs 21.2.1 HARP's main contribution to the field seems to be that it is a zone protocol which makes zones disjoint, (unlike ZRP, in which every zone overlaps with many others), and then uses a several-step protocol DDR to find routes to satisfy requests from nodes within the zone. One of the main problems here that I find is that we don't really seem to be buying anything by adding all these steps (at least over ZRP), although it is difficult to tell, since there are not even simulation results with which we can compare the techniques. In their brief mathematical analysis, I could see little compelling reason to use their protocol over ZRP. On the contrary, I would greatly prefer an O(N) protocol to an O(N^2), even if the O(N) is Np^2, since p is just a parameter to be fixed, and does not necessarily vary with the size of the network. Furthermore, the steps themselves, at least for DDR, are hardly described at all, and it is difficult to determine what exactly is going in the network. The results of the steps are specified, but little is said about how to get from here to there. I have some problems with their idea of out- and in- gateways; surely any given gateway is both? It does not seem particularly useful to restrict a gateway to sending packets only one way, and the authors do not mention any reason for doing so. Something that is peripheral to the actual paper but was quite distracting to me was the authors' use of the English language. One imagines that they could have had almost any native English speaker read this paper and fix the numerous mistakes of grammar which it contains. From vrg3@cornell.edu Thu Sep 26 11:21:56 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 g8QFLth27808 for ; Thu, 26 Sep 2002 11:21:55 -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 LAA16949 for ; Thu, 26 Sep 2002 11:21:48 -0400 (EDT) Date: Thu, 26 Sep 2002 11:21:48 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 22 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents HARP, another hybrid reactive/proactive protocol. HARP separates a network into distinct zones which have no overlap. The zones are computed by elections of preferred neighbors (much like dominator selection in CEDAR). DDR, distributed dynamic routing, then forms zones from this information. From then on, complete proactive routing tables are maintained within a zone and routing between zones is done reactively through gateway nodes that have links between zones, through a routing table which is shared among the elements of a zone. At first, when seeing the brevity of this paper, I thought this protocol was likely to be extremely underdeveloped and the presentation incomplete. It is true that they gloss over many parts of the protocol, and that they did not do any kind of simulation, but HARP is also a much simpler protocol. By avoiding overlapping zones, they avoid the redundant rebroadcasting problems which the ZRP paper spent a lot of time discussing. An implementation and experimental data would be a logical step in future work. The protocol looks quite promising but needs something to back it up. From smw17@cornell.edu Thu Sep 26 11:29:57 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 g8QFTuh29828 for ; Thu, 26 Sep 2002 11:29:56 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA02561 for ; Thu, 26 Sep 2002 11:29:56 -0400 (EDT) Message-ID: <3D932738.1050205@cornell.edu> Date: Thu, 26 Sep 2002 11:26:48 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 22 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit HARP HARP (Hybrid Ad-hoc Routing Protocol) is another hybrid routing scheme for mobile ad-hoc networks. HARP is the routing algorithm itself, living above DDR (Distributed Dynamic Routing). The DDR protocol sits above the network layer, and is responsible for constructing the desired network topology. DDR seeks to create a number of non- overlapping zones within the network (covering the entire network). Inside these zones, DDR employs a cyclic algorithm dependent on a neighbor exchange of beacons to create a forest by connecting each node to the neighbor with the largest neighborhood. Once a forest is built, a clustering algorithm creates a cluster from the forest and builds the intra-zone routing table. Once complete, intra-zone routing is handled by the routing table, and inter-zone routing is sent via the gateway nodes (nodes who have a direct link to a node outside their own cluster). Gateway nodes keep track of the Zone ID (ZID) of the adjacent cluster, as well as maintaining a measure of the stability of the inter-cluster link. Working above the DDR zone formation protocol, HARP seeks only to deliver packets to their destinations. For routes within a zone, HARP simply forwards packets based on the routing table. For communications external to the zone, HARP must construct a routing path before transmitting the data. When the desired destination is an external node, a Path REQuset (PREQ) packet is sent to the set of gateway nodes for the zone. At each gateway node, a stability factor inside the PREQ packet may be adjusted, such that the net stability factor is the stability of the least stable link in the path. Gateway nodes perform some limiting of extra paths, by only forwarding an additional route if it is more stable than the previously forwarded packet. At the destination, the PREQ packets are collected, and the destination node selects the most stable recieved path, with ties randomly resolved. The path is sent back to the source to create the routing path (assumes bi-directional links). Once a link is active, HARP employs a matinence scheme. If a link is broken (and the path no longer valid), a path error is sent to the source, and data is held for a waiting time. When a source recieves a path error, it runs the path discovery protocol to re-create the path. In addition, the source periodically re-creates the path based on the stability of the current path. The new path is created in parallel with the initial path. Once the new path is ready, the data stream is switched from the original path to the new path. A number of interesting concepts are presented in this paper. The non-overlapping zone structure that also embodies some features of a node cluster is quite interesting, as is the inherent seperation of the zone discovery procedure and the actual routing algorithm. The potential of periodic quality-based route renewal is also an interesting concept, depending on the desired latency/overhead tradeoff. Unfortunately, the paper is rather vague on the actual details of both how exactly the structure is created and on what the design parameters available are. There is an assertion that only beacons are required, and a general procedure is outlined, but the limited details provided are insufficient to determine any real information about the convergence time, reaction to topology shifts, or interaction between DDR's dynamic behavior and the HARP routing scheme. Furthermore, there is no simulation presented, only a cursory mathematical analysis of the communication overhead for similar schemes. Overall, I would like to see more detail on the implementation of the clustering scheme and the convergence properties, as well as some form of simulation study of both the general performance as well as the impact of inter-layer interactions on performance. From mvp9@cornell.edu Thu Sep 26 11:53:49 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 g8QFrmh05589 for ; Thu, 26 Sep 2002 11:53:49 -0400 (EDT) Received: from zoopark.cornell.edu (syr-24-58-46-186.twcny.rr.com [24.58.46.186]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA00883 for ; Thu, 26 Sep 2002 11:53:46 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926115223.01a7a4f8@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 11:53:46 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 22 Mime-Version: 1.0 Content-Type: text/html; charset="us-ascii" This paper introduces another hybrid zone-based protocol  HARP.  Its distinctions include separation of topology formation (which uses a separate protocol DDR) from routing, “stability” as the main metric instead of shortness of routes, and pre-emptive route maintenance.   The DDR protocol is supposed to offer its own benefits  reduction of broadcast and delay (though its not clear what it is a reduction from).  Using non-overlapping zones potentially offers better performance over something like ZRP.   However, due to lack of details, it is difficult to evaluate the claims presented.
        Vagueness is a huge problem in this paper.  Definitions and whole protocols are left undescribed: how is “stability” determined?  How does DDR actually work?  When is it activated and how is re-zoning done?  How are the zones partitioned?  Can there be routing loops between zones and if not, why?  Even from the described portions, some undesired details show through: gateway nodes must keep around unbounded number of ‘routing state’ information entries; prizing stability over shortness of routes can lead to excessive traffic; etc.  There are possibly some advantages over other hybrid protocols  perhaps it does create a more robust network with fewer control messages, but the “analysis” at the end is at best unsatisfactory.  The modularity introduced by DDR is nice, but not as earth-shattering as claimed, and can actually prove undesirable in a dynamic network.
        Assuming that most of the claims made in the paper are actually true, some improvements can be made.  For one, adding metrics other than stability to route decisions.  The testing that the authors promise in the end is the first necessary extension to the project, which will probably indicate many other directions for further work.
From ashieh@CS.Cornell.EDU Thu Sep 26 11:55:52 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 g8QFtph05763 for ; Thu, 26 Sep 2002 11:55:51 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8QFtpX19986 for ; Thu, 26 Sep 2002 11:55:51 -0400 (EDT) Date: Thu, 26 Sep 2002 11:55:51 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 22 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII HARP is a hybrid algorithm that uses disjoint zones. The zones are constructed using DDR (distributed dynamic routing), which constructs a (non-spanning) forest from the network topology. The edges (from the true topology) out of each subtree of the forest induces a set of neighbors for the subtree, and a set of gateway nodes between the neighbors. An important property of this algorithm is that it is "stable" in some way such that the results of different iterations of the algorithm may be compared cheaply to extract some idea about the stability of the network. HARP uses this stability information to pick the most stable route out of a set of candidates, and to estimate how often a route will have to be refreshed. As in ZRP, a spanning tree in each zone is used to transmit reactive routing discovery to gateway nodes, which relay to adjacent nodes; discovery packets are thus broadcast to each zone (and multicast within each zone) in the network. ** Shortcomings Since the zones are non-overlapping and use a fixed set of gateways, if all nodes of a zone move away as a group, then they are quickly disconnected until another round of DDR. Moreover, since instability is detected through DDR, it is conceivable that there is some sort of instability that cannot be detected (for instance, nodes moving in such a way that the relative value of each node in the neighbor selection algorithm remains the same, but are about to lose connectivity). The paper does not describe how this algorithm responds to node failures at gateways. Such failures are critical since the zones are non-overlapping. The mathematical analysis is very sketchy and confusing. ** - Is there a way to modify DDR to partition zones such that there are multiple gateways between zones? This is important for reliability. We may also want a partitioning algorithm that allows for bigger zones in areas with many fast-moving nodes. It seems harder to do this in HARP framework than with ZRP. From mtp22@cornell.edu Thu Sep 26 11:59:11 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 g8QFxBh06744 for ; Thu, 26 Sep 2002 11:59:11 -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 LAA24900 for ; Thu, 26 Sep 2002 11:59:10 -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 22 Date: Thu, 26 Sep 2002 11:59:18 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02092611591804.00155@narnia> Content-Transfer-Encoding: 8bit A major contribution of this paper is the HARP protocol. This protocol is novel because it separates the creation of zones from the routing protocol, adding the idea of modularity to the ad hoc routing layer. Another novelty is the idea of basing the routing on a host of characteristics that can be specified by the network's application. We saw this before CEDAR, but in that case the characteristics were limited to bandwidth only. HARP relies on DDR to organize the network into zones for it. DDR is based on two earlier ideas, namely the spanning trees of DST and the zones of ZRP. One DDR takes care of the organizing the network into zones, HARP takes care of the interzone routing. A weakness of this paper is the lack of simulation results. The paper claims to outperform ZRP and ZHLS, and goes on to show this theoretically, but does not show any actual results to support this claim. A possible extension of this paper is related to its main weakness. That is, the paper could be extended by simulations. We saw in the ZRP paper a thorough analysis; a similarly thorough analysis of ZRP, ZHLS, and HARP w/DDR would be nice. From pj39@CS.Cornell.EDU Thu Sep 26 12:19:38 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 g8QGJch10848 for ; Thu, 26 Sep 2002 12:19:38 -0400 (EDT) Received: from cornell-yb3go20.cornell.edu (syr-24-59-67-50.twcny.rr.com [24.59.67.50]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA15435 for ; Thu, 26 Sep 2002 12:19:38 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926121844.01ed4780@postoffice2.mail.cornell.edu> X-Sender: pj39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 12:19:35 -0400 To: egs@CS.Cornell.EDU From: Piyoosh Jalan Subject: 615 PAPER 22 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed HARP - Hybrid Ad hoc Routing Protocol This paper describes HARP, a hybrid protocol for routing in ad hoc mobile networks. This paper which is very similar to ZRP builds upon DDR. It only maintains a path between source and destination and leaves the topology generation to DDR. In DDR nodes using periodic beacons constructs a forest. Trees in forests forms a zone and the network is partitioned into a set of non-overlapping zones. The DDR algorithm consists of six cyclic time-ordered phases which are executed based on the beacon information. Inside a zone routing takes place using the DDR tree and for inter zone routing a node sends PREQ messages from its zone to neighboring zones gateway nodes. Each gateway node keeps some routing state information found in PREQ so that it can route the PREP (response) messages to the source traversing the same path. The major weaknesses in the paper are - It uses DDR which is an existing work. - The routes generated by HARP are likely to be suboptimal for both itra and inter zone routing as all the traffic flows from the root of the zone. This also leads to overloading of the root nodes. - Implications of failure of root nodes is not discussed. - There is not a proper load balancing as the root nodes are more utilized than other nodes. - Simulations presented in the paper are not enough to gauge its advantages over other hybrid and reactive/proactive protocols. Future work could be directed towards performing more simulations and giving actual data so that the performance the protocol could be effectively gauged and further improvements on the protocol could be made. From linga@CS.Cornell.EDU Thu Sep 26 12:23:38 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8QGNch11221 for ; Thu, 26 Sep 2002 12:23:38 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8QGNbK23258 for ; Thu, 26 Sep 2002 12:23:37 -0400 (EDT) Date: Thu, 26 Sep 2002 12:23:37 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 22 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII HARP This is another hybrid routing protocol where intra-zone routing is proactive and inter-zone (for route discovery) is reactive. The new architecture proposed in this paper separates topology creation from route determination. Disadvantages of proactive protocols include: high b/w requirement for maintaining routing info, a small change in one corner of the network effects all nodes in the network, due to the highly mobile nature of mobile networks most of the routing info may not be used. Likewise reactive protocols have high control traffic and also delay in setting up the route to the destination. HARP is better than ZRP in the following ways: HARP only takes care of path establishment and maintainence and leaves topology generation to DDR (Distributed dynamic routing); limits the flooding to a subset of nodes in each zone; uses zone level stability as a metric for route determination. HARP tries to take of application requirements and find a path accordingly while DDR generates a logical structure keeping in mind the network properties. DDR algo generates a forest from a network topology in a purely distributed fashion where each node periodically talks to its neighbors. Each tree in the forest is a zone and so the zone's do not overlap (unlike in ZRP where they do). Different zones are connected by nodes which are within transmission range. Each node keeps info about other nodes with its zone (in the intra-zone table) and about nodes in neighboring zones (in the inter-zone table). HARP aims at establishing the most stable path from source to destination and also filters candidate paths using the stability criteria as soon as possible. Given source s and destination d, to establish a route from s to d: If d is in the same zone as s, s justs sends the data to d (intra-zone routing). If d is not in the same zone as s, then it forwards the path request (PREQ) to every other neighboring zone z via gateway nodes g (inter-zone routing). Now each out-gateway node forwards PREQ from it's zone to the next zone using its inter-zone table and then updates the stability value. Each forwarding node on the path appends its node id to the PREQ. The destination d chooses the path with the best stability value and sends the path reply (PREP) pkt by reversing the accumulated path. Note that inside a zone the path request follows the tree structure provided by DDR and this limits PREQ propagation to a limited subset of the nodes. Total amount of communication overhead for topology creation in the three protocols (DDR, ZRP and ZHLS) are presented. ZRP and DDR have similar overheads (but that depends on number of zones and zone-radius). Pros: Another hybrid algorithm which abstracts out the topology maintenance part from the route discovery part. It also returns the most stable path from source to destination. Intrazone flooding is limited to a small subset of node for PREQ propagation. Mathematical analysis shows that communication overhead is comparable to ZRP and lesser than ZHLS. Cons: No experimental/simulation results. Stability not defined properly. Not a significant improvement from the earlier protocols. Mathematical analysis in a very simplistic case. From ks238@cornell.edu Thu Sep 26 12:35:21 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 g8QGZLh13953 for ; Thu, 26 Sep 2002 12:35:21 -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 MAA17927 for ; Thu, 26 Sep 2002 12:35:16 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926123354.01cf19e0@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 12:34:41 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #22 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In this paper another hybrid protocol, HARP, is presented, which employs intra-zone routing and inter-zone routing. Intra-zone routing is conducted amongst nodes within a zone through proactive routing. Intra-zone routing usually entails broadcasting to all neighboring (or within the same zone) nodes. Inter-zone routing is conducted amongst nodes that are found between nodes through reactive routing. While HARP is responsible for the route discovery and route maintenance within the network, DDR is responsible for updating and maintaining network topology. DDR employs the concepts of constructing a forest (i.e. network) made of trees, which represents a zone within the network. Each zone is connected by nodes that are in neighboring zones to each other and that are in direct transmission range of each other. This is possible through the use of particular gateway nodes. HARP is responsible for the route discovery and route maintenance in order to facilitate transmissions. One of the key features of HARP, is the discovery of secure routes. When a node receives a transmission from multiple nodes, it selects its path based on which path is most stable. The path discovery and path maintenance algorithms are pretty easy and basic and the author's provide examples to illustrate their functions. Unfortunately, as seen on multiple occasions, there is no simulation so once again finding problems in the protocol is relatively difficult. The author's do provide a mathematical analysis/comparison of the protocol in regards to other protocols which proves ZRP induces less overhead than other hybrid protocols. Some areas of concern is the issue of sacrificing an optimal path for one that is secure. It would be interesting to see results that test the success rate of data transmissions versus the efficiency (in time, memory, network usage) of the protocol in networks. Even more interesting would be the idea of "looking ahead" to ensure that not just the current hop, but all hops along a particular route are secure. For instance, you may choose a route that follows a secure hop but ends up resulting in a less secure route. However, this also brings up the question of how do you measure "secure" or "stable" routes. This is not really defined. From yao@CS.Cornell.EDU Thu Sep 26 14:01:53 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 g8QI1rh03005 for ; Thu, 26 Sep 2002 14:01:53 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615 paper 22 Date: Thu, 26 Sep 2002 14:01:52 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D43024797F6@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 paper 22 Thread-Index: AcJlhsuObBFD/jOZQDa8S2ZcIi91pA== From: "Yong Yao" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8QI1rh03005 The paper presents a hybrid routing protocol, HARP. Simiar to other hybrid routing protocols, like ZRP or ZHLS, HARP combines both proactive and reactive routing protocols. It uses proactive routing to establish routes to neighbor nodes, while switches to reactive routing to discover faraway nodes. The most ditinguished properties of HARP against other ad-hoc routing protocols is that HARP has two seperate layers. DDR is responsible to maintain the network topology by constructing a forest from the network. It also combines two classical notions forest and zone. DDR consisits of six cyclic time-ordered phases, from connecting close nodes to linking neighbor trees. Seperate inter-zone and intra zone tables are distributed maintained to record the network topology. Another module on top of DDR is in charge of finding and maintaining a path to any destination. The network struct established by DDR is used to compute or generate the path. HARP has a different metic to evaluate the quality of a path, reliability. A more reliable path is prefered to a shorter path. The paper has several weaknesses. First, it lacks an evaluation section except a very brief mathematical analysis. Since both ZRP and ZHLS are hybrid routing protocols with similar intuition, it is not clear how much benefit can be achieved by HARP. Second, the concept of reliability of a path is too limited. It is only measured at the gateway nodes of clusters, which is far from complete. Since each cluster is represented as a tree, each link in the tree could be a single failure point. Finally, I can't see any main differences between HARP and other cluster-based algorithm. The only differnece is how clusters are constructed. The inter-cluster routing algorithms are very similar. There is a lot of work on how to construct clustersl How to compare the cluster created by HARP to other cluster structres is missing in the paper. Yong Yao From vivi@CS.Cornell.EDU Thu Sep 26 17:22:21 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 g8QLMLh14843 for ; Thu, 26 Sep 2002 17:22:21 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Subject: 615paper22 Date: Thu, 26 Sep 2002 17:22:20 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF77@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper22 Thread-Index: AcJlosx+93kUweSERPyjp4og+3NN2Q== 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 g8QLMLh14843 HARP is another hybrid routing protocol for ad-hoc networks. It is similar to ZRP, but with one major difference: In HARP, the zones are disjoint. This protocol works on top of another protocol DDR, and it seems like without going through the DDR paper, it is difficult to get a full feel of this paper. The paper is lacking in clarity. It does not explain in detail several aspects of the protocol, like the formation of the individual zones, the number of nodes in a zone, how the gateway nodes are identified, etc. The path maintenance suggested in this paper could be very expensive. All paths have a ttl set when they are set up, and new routes are set up after the expiry of this time. Additionally, a new path is set up whenever the estimated stability of the path goes down (whether or not the path is stable enough to support the traffic). The same path could be continued with after a check to see if it is stable enough. The analysis at the end of the paper is very short, and focuses solely on the communication overhead generated. The actual derivation/proof of the used expressions is not given. And there is no simulation whatsoever. This puts in doubt the acceptability of the protocol in an actual network. From nbs24@cornell.edu Thu Sep 26 08:54:33 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 g8QCsXh28001 for ; Thu, 26 Sep 2002 08:54:33 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id IAA24636; Thu, 26 Sep 2002 08:54:31 -0400 (EDT) Date: Thu, 26 Sep 2002 08:54:31 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209261254.IAA24636@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 23 HARP - Hybrid Ad hoc Routing Protocol This paper also introduces a hybrid protocol, HARP that maintains routing information within zones proactively and across zone reactively. Unlike ZRP, routing zones do not overlap in HARP and can have different zone radii. They use the distributed dynamic routing, DDR to build a logical zone hierarchy of nodes while HARP concerns itself with finding and maintaining a path from source to destination. Once DDR builds the tree neighboring nodes are discovered through gateway nodes, that is, nodes that have inter- zone links, at the borders. The paper introduces zone level stability as a metric of route determination. The paper failed to convey the true workings of their algorithm, especially DDR, to me. How is a stable route guaranteed? How would the algorithm behave in the presence of node failure? The paper does not present any performance evaluation. A build to the research would be a better explanation of their algorithm, addressing ad hoc network issues and providing some performance evaluation, instead of a mathematical analysis. Nana B. Sam From mp98@cornell.edu Thu Sep 26 11:55:20 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 g8QFtKh05731 for ; Thu, 26 Sep 2002 11:55:20 -0400 (EDT) Received: from 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 LAA05434 for ; Thu, 26 Sep 2002 11:55:18 -0400 (EDT) From: mp98@cornell.edu Date: Thu, 26 Sep 2002 11:55:19 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 23 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <5BA0683A-D168-11D6-A2CA-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.546) HARP is another hybrid routing protocol similar to ZRP of the previous paper. Like ZRP, it uses distinct intra- and inter-zone routing protocols. It is distinguished from ZRP in its means of zone formation and proactive routing: It uses a protocol called DDR wherein each node elects its neighbor with the highest neighborhood degree (that is, as I understand it, a node a chooses b in N(a) such that N(b) intersected with N(a) is maximized.) This is guaranteed to divide the network into a forest, although there is no mention of how big any particular tree will be. Within a tree in the forest, nodes maintain an intra-zone table which provides them with the next hop to any node in the zone. Routing within the zone thus is trivial. Nodes with neighbors who are not in the same zone as them, called gateway nodes) must also maintain an interzone table maintaining knowledge of their neighboring gateway nodes and the stability of the links. To route between zones, requires path discovery: the source sends a path request packet to all the gateway nodes in its zone (via intra-zone routing) who then forward it out to neighboring zones. When a path is found, it is sent back to the source via path reversal based upon soft state. The stability measurements of the inter-zone table are used to help pick between multiple paths that might be returned. These paths periodically expire and must be refreshed. The paper includes little analysis--Only some measurement of the cost of topology creation--and that is circumspect in its assumptions and conclusions: They assume hosts evenly distributed in the network, for example, and even though ZRP beats them in their chosen metric, they argue that HARP is superior because it constructs less zones meaning less control traffic. HARP does construct fewer zones, but this does not necessarily mean that there will be less traffic; it must be tested formally. This paper's true innovation is its zone construction technique which intuitively seems very fast and simple. However, in order to evaluate this, it requires a simulation. Since we do not know the bound on M (the size of a zone) we cannot assert the size of the N^2/M overhead to zone construction. It could be close to linear, but it's hard to say what the behavior will look like in a real host distribution.