From andre@CS.Cornell.EDU Wed Oct 10 17:59:23 2001 Return-Path: Received: from sundown.cs.cornell.edu (sundown.cs.cornell.edu [128.84.96.20]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9ALxMo23154 for ; Wed, 10 Oct 2001 17:59:22 -0400 (EDT) Received: from khaffy (mail@dhcp99-178.cs.cornell.edu [128.84.99.178]) by sundown.cs.cornell.edu (8.11.3/8.11.3/R-3.6) with ESMTP id f9ALxMi09783 for ; Wed, 10 Oct 2001 17:59:22 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.32 #1 (Debian)) id 15rSB5-0003H4-00 for ; Wed, 10 Oct 2001 17:50:15 -0500 Date: Wed, 10 Oct 2001 17:50:15 -0500 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Subject: 615 PAPER 21 Message-ID: <20011010175015.A12531@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.22i Zone Routing Protocol. This paper proposes a hybrid routing scheme: there is a DVR zone around each node, the rest of the routing (further aways nodes) is on demand. Any knid of DSV algorithm is fine for the local zone. When a node doesn't know the route to a node (so that node is outside the local zone), it queries the periphirical nodes of its zone, which either know the route because it is in their local zone; or propagate the query to the peripherical nodes. (Peripherical nodes = set of nodes which are r hops away from the center where r is the radius of the zone). This is the BRP Border Route Protocol. Loop back termination: in the BRP, the current route from originator is saved, to avoid loops. Query Detection (I didn't get everything). The idea is to detect and avoid propagating queries that has already been propagated by one of the other guys of the zone. Intermediate node (the inner nodes of a zone can play their role) but I think everything could be done at the level of the peripherical nodes. Improvment: Selective Bordercasting (SBC) keep a knowledge of the peripherical nodes of your own peripherical nodes, so that you only decrease the redondancy and only forward the query to some of your peripherical nodes. (avoid transmitting to useless nodes because of the circles supperposition) but you need to be careful with the query detection filtering. Simulations show that SRB is not really useful except for multiple channel networks. The results show that a good choice of the radius (depends on the mobility - frequency of communication) yields to less traffic than pure reactive or proactive. -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From wbell@CS.Cornell.EDU Wed Oct 10 22:12:21 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9B2CKo18244 for ; Wed, 10 Oct 2001 22:12:20 -0400 (EDT) Received: from dhcp-190.rover.cornell.edu (dhcp-190.rover.cornell.edu [128.84.24.190]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id WAA06470 for ; Wed, 10 Oct 2001 22:12:19 -0400 (EDT) Subject: 615 PAPER #21 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.14.99+cvs.2001.09.29.08.08 (Preview Release) Date: 10 Oct 2001 22:12:11 -0400 Message-Id: <1002766353.2435.1484.camel@brute> Mime-Version: 1.0 21) The Performance of Query Control Schemes for the Zone Routing Protocol This paper looks at the performance of the Zone Routing Protocol for ad-hoc networks and motivates how ZRP can be improved by various query control schemes, which keep queries for routes from performing a flood on the entire network. ZRP is a hybrid protocol, which does proactive route-finding in a small neighborhood called a zone, which is determined as a number of hops from a given node. Routes for nodes not in a source node's zone are found via reactive protocol similar to DSR. This balance between proactive and reactive gives ZRP it's good performance and large scalability, unlike totally proactive protocols where control overhead overwhelms the network. Because of it's proactive portion, we see that it has a lower control overhead as compared to strictly reactive protocols such as DSR. The goal of ZRP is to make local communication cheap by continually maintaining routes to nearby nodes, and to reduce route finding overhead for far away nodes by utilizing these local routes maintained at each node. Each node is responsible for keeping the connectivity of a local neighborhood, and these neighborhoods will necessarily overlap. ZRP proposes several ways to use this overlapping property in order to optimize route queries over basic flooding by not redundantly rebroadcasting. The main insight is to only broadcast route queries over what they call border nodes [bordercasting], because interior nodes in a zone cannot possibly have more useful routing information than the nodes on the periphery of a source node's zone. They also propose 4 schemes for reducing redundant broadcasts : Loopback Termination, Query Detection, Early Termination, and Selective Bordercasting. The analysis of ZRP has got to be one of the best we've seen thus far, as it's probably reproducible and is well thought out. They analyze the impact of the different broadcast reduction mechanisms as to how they impact control traffic overhead, as well as route latency. I was very impressed at the insight as to why selective bordercasting was not always a good idea, especially in conjunction with QD2. ZRP shows one of the largest simulations we've seen thus far (500 nodes), and is definitely showing it's ability to scale. It would be interesting to see if the scalability had a bound, or in what cases ZRP doesn't do well. I understood their reasons for fragmenting the simulation for computational efficiency, although I was unable to determine if their assumptions for breaking the IERP and the IARP into 2 segments was really valid. It would be nice to see a unified simulation, even with a smaller population of nodes. From samar@ece.cornell.edu Thu Oct 11 02:56:45 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9B6ujo16966 for ; Thu, 11 Oct 2001 02:56:45 -0400 (EDT) Received: from hegel (hegel.ee.cornell.edu [128.84.236.63]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9B6v0Q05666 for ; Thu, 11 Oct 2001 02:57:00 -0400 Date: Thu, 11 Oct 2001 02:56:40 -0400 (EDT) From: Prince Samar X-Sender: samar@hegel.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 21 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 21) The Performance of Query Control Schemes for the Zone Routing Protocol The Zone Routing Protocol is a hybrid protocol for Ad hoc networks which maintains proactive information about the local neighborhood of a node, called zone, to efficiently query the network reactively to order to determine a route to the destination. A zone is characterized by a zone radius R - all nodes within R hops from a node are said to belong to its zone. ZRP uses Intrazone Routing Protocol (IARP), which could be any proactive protocol, to maintain routing information about its zone. Interzone Routing Protocol (IERP), which could be any reactive protocol, is used to globally query the network for a route to the destination. Bordercast Resolution Protocol (BRP) is used to multicast the route request packet to a node's peripheral nodes. The paper proposes query control schemes to guide the querying of the network "outwards" so that newer areas are covered, moving the query away from the region which has already been "covered" by other nodes. Here a node is "covered" if it lies inside the zone of a node which has already relayed the query or if the node has already received a query from the same node. When BRP multicasts the query to its peripheral nodes, the nodes forwarding the query packet will know about the query (QD1). Also in single channel networks, neighbors of the previous nodes may also promiscuously overhear the query (QD2). Using QD1 and QD2, nodes can mark the appropriate area of their zone as covered. Using the information obtained through QD1 and QD2 and the knowledge of the local topology, nodes can detect and terminate redundant queries (ET). Also, introducing Random Query Processing Delay (RQPD) lets a node listen to the queries from its neighbors and drop any redundant queries. ZRP is a hybrid framework which uses a table-driven protocol (like OLSR, TBRPF, DSDV etc.) and an on-demand protocol (like AODV, DSR etc) to efficiently perform routing in an ad hoc network. One possible problem associated with the deployment of ZRP in practical ad hoc networks is the determination of the optimum zone radius prior to the actual network set-up. Though algorithms for determination of the optimal zone radius have been proposed, they still require that this optimal zone radius be known beforehand by each node so that each node can tune into the same zone radius. How could a node determine and change the zone radius dynamically and how to extend the scheme so that each node could have independent zone radius depending on its traffic and mobility pattern (and that of the nodes in its surroundings) are some of the associated research problems. From daehyun@csl.cornell.edu Thu Oct 11 05:27:28 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9B9RSo02757 for ; Thu, 11 Oct 2001 05:27:28 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id FAA62920 for egs@cs.cornell.edu; Thu, 11 Oct 2001 05:27:23 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200110110927.FAA62920@wilkes.csl.cornell.edu> Subject: 615 PAPER 21 To: egs@CS.Cornell.EDU Date: Thu, 11 Oct 2001 05:27:23 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper proposes a mechanism which can reduce control messages in Zone Routing Protocol (ZRP). ZRP is a routing protocol for ad hoc networks. The mian idea of ZRP is to hybrid proactive and reactive routing schemes. Each node maintains a routing zone. It uses a proactive routing algorithm called IntrAzone Routing Protocol (IARP) for sending messages within the zone. But, if the destination of a message is beyond the zone, it uses a reactive routing algorithm called IntErzone Routing Protocol (IERP). Proactive algorithms has less latency in finding routes than reactive ones. But it has higher control message overhead, especially in ad hoc networks. ZRP tries to solve these problems by hybriding two approaches. One nice feature of ZRP is Bordercasting. Usually, reactive algorithms use flooding to establish routes. But, IERP uses bordercasting instead. Because it maintains the routing zone and knows all routing information inside the zone, it does not need to flood the messages to intermediate nodes. It only has to sends the messages to border nodes. Bordercasting potentially can reduce control messages. But because the routing zones overlap and bordercasting sends messages with length of zone radius, the control messages might be even bigger than flooding. This paper proposed 4 mechanisms to solve the problem. 1. Loop-back Termination (LT) : If loop is detected in a bordercasting, it is terminated. 2. Query Detection (QD1/QD2) : If a bordercasting is overlapped with another bordercasting, it is terminated. 3. Early Termination (ET) : A bordercasting can be terminated by not only peripheral nodes but also intermediate nodes. 4. Selective Bordercasting (SBC) : Bordercasting messages are sent to only subset of peripheral nodes, if it can cover entire area. The main contribution of this paper is that it solves the major problem of ZRP. ZRP uses bordercasting to reduce the message overhead of flooding. But, in contrary, it might even increase the overhead. This paper proposes mechanisms to solve the problem and shows the results by simulations. In my opinion, ZRP is a very nice approach. Especially, bordercast might be a good alternative for flooding. In ad hoc network, flooding was used as a general mechanism for routing. But as indicated in this paper, its overhead is big. I think bordercast solves the problem with the mechanisms in this paper. From haom@csl.cornell.edu Thu Oct 11 09:55:32 2001 Return-Path: Received: from mauchly.csl.cornell.edu (mauchly.csl.cornell.edu [132.236.71.68]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BDtVo00776 for ; Thu, 11 Oct 2001 09:55:32 -0400 (EDT) Received: from localhost (haom@localhost) by mauchly.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id JAA94167 for ; Thu, 11 Oct 2001 09:55:26 -0400 (EDT) (envelope-from haom@mauchly.csl.cornell.edu) X-Authentication-Warning: mauchly.csl.cornell.edu: haom owned process doing -bs Date: Thu, 11 Oct 2001 09:55:26 -0400 (EDT) From: Ming Hao To: egs@CS.Cornell.EDU Subject: 615 PAPER 21 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The Performance of Query Control Schemes for the Zone Routing Protocol By Zygmunt J. Haas and Marc R. Pearlman the paper propose a hybrid protocol to better compromise latency of response and communication overhead. the radius of the zone is two hops the algorithm has two parts: 1 proactive method for intra zone routing. 2. reactive method for interzone routing. when a node transmit the query msg, it only sends it to its peripheral nodes, which is called bordercasting. still the old problem. if a node discards the a query which has reached it, i am pretty sure it can not find the shortest route unless it only discards the next query whose hop is bigger than previous one. the important part of the paper is 3 methods to avoiding flooding,reffered to as query control scheme. a. Loop-back Termination (LT). the border will not reply the query if it finds itself in the accumulated path. b.QD1/QD2. let intermediate nodes record the info about the replyed query message. it is the base of ET. c.Early Termination (ET). extending terminiation capability to intermediate nodes. d. Selective Bordercasting (SBC). with the infor about the nodes within the range of 2p, sender nodes can determine which intermediate border nodes should take part in the replying so that overlapping transmission is eliminated. simulation results: the paper gave the details about the performance impact of LT,ET and QD1 on the communication overhead at differnt moving speed of nodes. one conclusion can be drawn is that there is an optimal p in differnt moving pattern and routing query rate. the latter highly depends on the application pattern. one thing confues me is that i believe the trend is that on-demand routing is better suited to ad hoc network than proative. but in all the figurs about the total communication overhead vs. p shows the opposite. i think there is something wrong if it does not caused by the selection of simulation parameters. another drawback is that it did not considering the path maintainance. because reacive protocol can repair part of changed path locally, it is better than proactive counterparts. this is especially useful when mobility is not uniform across the ad hoc network. the results about latency is too simple. in the only one figure, it does not even comment how fast the nodes move and how latency depends on the moving speed. further, it did not explain why the latency decreases so much from r=1 to p=2. summary: this is a nice paper which smartly combines two routing algorithm aturaly and can be adjusted to approaching either one. it would be nicer if the paper can compare ZRP with other algorithms in the term of latency and communication overhead. Another remaining problem is how to p adapt to the chaning enviroment automatically and quickly. inspired idea: 1. reactive protocol can incur big response latency only in the case of the first query. following queries have no problem. the only problem here is hit ratio(like cache). conmmunication overhead should be considered in the following way: high overhead causes trouble only when the bandwidth used for control is needed for real communication. otherwise, it is not a problem. though less overhead is almost always better in the term of power consumption. but timing is also a factor. -ming Ming Hao PH.D Candidate, EE mh97@cornell.edu Cornell University Office: (607) 255-0817 Ithaca, NY 14853 http://www.ee.cornell.edu/~haom/ From papadp@ece.cornell.edu Thu Oct 11 10:00:47 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BE0lo01344 for ; Thu, 11 Oct 2001 10:00:47 -0400 (EDT) Received: from photon (photon.ee.cornell.edu [128.84.239.166]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9BE10Q11086; Thu, 11 Oct 2001 10:01:00 -0400 Date: Thu, 11 Oct 2001 10:03:26 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-Sender: papadp@photon.ee.cornell.edu To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 21 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of "The Performance of Query-Control Schemes for the Zone Routing Protocol," by Z.J. Haas and M.R. Perlman. Panagiotis Papadimtratos papadp@ee.cornell.edu The Zone Routing Protocol (ZRP) is a hybrid routing protocol for mobile ad hoc networks (MANET's) in that it encompasses a proactive and a reactive component. The proactive protocol is used to maintain the topology view of the routing zone, i.e., the neighborhood of the node, while the reactive one is used to discover routes to nodes that lie beyond the routing zone. The balance between these two components and the tuning of the protocol can yield less control traffic, compared to a purely reactive or proactive approach in a dynamically changing topology. Furthermore, the delay of route discovery will be lower than the delay of a scheme that relies solely on a flood searching. The performance of the protocol(s) depends on the network conditions and the interaction between the proactive and reactive components and the benefits yielded by each of them. On one hand, the proactive (IARP) maintenance is naturally restricted to a small (e.g., 3 or 4 hops) zone, since the cost increases fast with the zone size, while a large portion of the extensive view would remain unused before becoming obsolete. But, it is exactly the knowledge of all nodes and routes to all nodes within the zone that allows ZRP to: (i) take advantage of localities in communication (ii) direct efficiently the search throughout the network (iii) reduce the search delays and, (iv) perform local (reactive) route maintenance. On the other hand, the cost of the reactive (IERP) component increases as the size of zones becomes smaller, and this would happen in highly dynamic topology, where the reactive operation increase would counter-balance the savings from the exorbitant control overhead of a large-zone maintenance. The propagation of the search itself is an important issue since it could have resulted in much higher control overhead than that of conventional flooding. The mechanisms that will disallow this phenomenon and at the same time maintain the correctness and efficiency of the protocol are exactly the topic of the paper. The central node (CN) of the routing zone constructs Bordercast tree, a tree rooted at CN with leaves the border nodes of the zone, i.e., the nodes that are rho hops from CN. Rho is the size of the zone, namely, the zone radius. If the sought destination does not lie within the zone, then IERP is invoked for a search beyond the zone. The query packet is forwarded from CN to its border nodes (while accumulating the tree links) and once reaching there the whole zone is considered covered; it would not make sense to let the query reach any intermediate node of the zone since it will not be the destination for sure. The hop-by-hop relaying of the query along the bordercast tree provides for the first Query Detection mechanism (QD1); the intermediate nodes become aware of the query. Furthermore, if a shared medium is used, any other node that overhears the query propagating along tree links will also learn about the query (QD2). Nonetheless, QD1 and QD2 do not guarantee that the entire routing zone will be notified on the query. An additional enhancement is provided by the early termination (ET): a node receiving the query can proceed by inferring, based on its topology knowledge, which links of its bordercast tree should be pruned, i.e., which links it should not propagate the query over. This is possible either when the nodes maintain the extended zone view (2*rho1), or they cache the bordercast trees of other interior nodes (the latter is straightforward from the way the CN operates according to BRP). Finally, a random delay before propagating the query can be introduced so that more that one border-nodes avoid relaying the query in overlapping zones. The delay would result in allowing the query detection and early detection mechanisms to limit the overlap, and thus the inefficiency. In conclusion, the extensive, accurate simulation results indicate the above-mentioned tradeoffs between IERP and IARP, and evaluate different combinations of query control mechanisms under different mobility, load, and protocol-specific parameter values. As it would be expected, for low mobility and frequent transmissions, the more proactive operation yields better performance. Whereas, for dynamic topology with nodes generating low traffic rates, the more reactive configuration is better. In all cases, there is an apparent optimal zone configuration that yields the lowest traffic overhead, and it also appears that the same configuration will yield the lowest delays as well. Moreover, the route discovery remains near optimal. The only factor that actually indicates an additional tradeoff is the query jitter, that on one hand contributes in reducing the control traffic, and on the other hand, its ad hoc choice can severely degrade the route discovery delay. From gupta@CS.Cornell.EDU Thu Oct 11 10:27:09 2001 Return-Path: Received: from ringding.cs.cornell.edu (ringding.cs.cornell.edu [128.84.96.109]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BER8o04811 for ; Thu, 11 Oct 2001 10:27:08 -0400 (EDT) From: Indranil Gupta Received: (from gupta@localhost) by ringding.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f9BER8728714 for egs@cs.cornell.edu; Thu, 11 Oct 2001 10:27:08 -0400 (EDT) Message-Id: <200110111427.f9BER8728714@ringding.cs.cornell.edu> Subject: 615 PAPER 21 To: egs@CS.Cornell.EDU Date: Thu, 11 Oct 2001 10:27:08 -0400 (EDT) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit ----START----- The performance of query control schemes for the zone routing protocol, Haas and Pearlman. Reviewer: Indranil Gupta The authors present work on ZRP, a hybrid alternative to proactive and reactive protocols. Each node proactively maintains routing information regarding other nodes within a zone (defined as some number of hops away from the node). Routes to nodes not in the zone are discovered reactively. The protocol has the following components : 1) Bordercast protocol (BRP) used by a node to send a broadcast to nodes on the fringes of its zone, 2) IARP, the proactive intrazone routing protocol, and 3) IERP, the reactive interzone routiong protocol. The reactive interzone route discovery is done by using bordercasting - however, this results in more traffic than flooding. In this paper, the authors present several optimizations to offset the problems caused by the above super-flooding phenomenon. These optimizations essentially involve throttling the forwarding of a route discovery message at a node by 1) estimating if this node lies in overlapping zones of nodes that have bordercast the same query (LT), 2) overhearing bordercasts from another node in whose zone this node lies (QD), 3) checking if this node has seen the same query earlier (ET), and 4) bordercasting to a selective set of border nodes to avoid overlap (SBC). Simulation results show that the first three optimizations reduce the amount of control traffic while the last one increases it. Overall, given a call ratio and mobility parameter, there is an optimal value of the zone radius, in order to reduce the control traffic. Comments: - The authors' criticism of hierarchical routing protocols is unfair as it focuses on only one instance of such work (Landmark Hierarchy). Recent work on systems like Astrolabe (Cornell), Grid Location Service (GLS), could lead to the development of peer to peer routing schemes that do not necessarily need to use representatives in the hierarchical zones. In other words, the overhead of routing control traffic would be spread across all nodes in the system, while routes could be discovered that are fairly close to optimal. However, this is an yet-uninvestigated area. - Does the optimal value of zone radius depend only on the call to mobility ratio (CMR) or also the call rate. In either case, could each node *locally* adjust its zone radius according to local measurements of mobility, while still guaranteeing the same properties ? - The authors could use the idea of increase/decrease waves to quell further propagation (bordercasting/flooding) of a route query message once the destination has been found. Route query messages have to be delayed at nodes (more than the route query quell message), resulting in an increased latency for route discovery across zones, but potentially reducing the overhead of flooding to the entire network if the source and destination are close by, yet not in each others' zones. - The optimal zone size appears to be a function of a) mobility parameters, and b) reaction time to each topology change. The authors do not investigate the second parameter (as they assume that the network topology remains constant over a route discovery period, and reconfiguration per topology change). ----END----- From teifel@csl.cornell.edu Thu Oct 11 11:04:40 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BF4do10108 for ; Thu, 11 Oct 2001 11:04:39 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9BF4YI47117 for ; Thu, 11 Oct 2001 11:04:34 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 11 Oct 2001 11:04:34 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 21 Message-ID: <20011011110320.M29382-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ZRP: This paper discusses the performance of the Zone Routing Protocol (ZRP) for ad-hoc networks. ZRP is locally proactive and globally reactive in its routing. This hybrid approach has the potential to be more efficient than traditional routing protocols, but only if it has proper query control. This paper analyzes good query control mechanisms for the ZRP. Query control mechanisms. Look-back termination prevents a thread from returning to a routing zone that it previously queried. Query detection allows intermediate nodes in a zone to detect query requests. Selective Bordercasting eliminates thread overlap at the local level, which helps to reduce thread overlap farther out in the network. Although SBC requires more topology information to implement (twice a normal zone topology). Simulation section is perhaps the most extensive of any of the papers we have read in this class. I like the idea of this hybrid protocol for ad-hoc networks. Of course any hybrid protocol may be more complicated to implement, but I think hybrid protocols (combined by some heuristic) are the only thing that will work effectively (in terms of performance) on dynamic ad-hoc networks. From avneesh@csl.cornell.edu Thu Oct 11 11:06:34 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BF6Yo10296 for ; Thu, 11 Oct 2001 11:06:34 -0400 (EDT) Subject: 615 Paper 21 Date: Thu, 11 Oct 2001 11:07:08 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Message-ID: <97C142C1212ED545B0023A177F5349C4053ADD@capricorn.ds.csl.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: content-class: urn:content-classes:message X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Thread-Topic: 615 Paper 21 Thread-Index: AcFSZmU36MGckMmmQ9i55sDWWv1aUA== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f9BF6Yo10296 The Performance of Query Control Schemes for the Zone Routing Protocol Summary/Critique: This paper presents the Zone Routing Protocol (ZRP), which extends the idea of having a hybrid scheme, i.e. local proactive route maintenance, and global reactive route maintenance. The locality of a node is defined as a 'zone', which might have variable radius. The routing is proactive within a zone and nodes which are not within a zone are discovered using the reactive component of the protocol. The authors have also presented various schemes to reduce unnecessary traffic within a zone, and also reducing redundant traffic when a node is part of multiple zones. The discovery of neighbors or nodes in a zone, is done with the help of a MAC layer protocol(NDP), which involves broadcasting of hello beacons. There are thus three components of this protocol: (1). IARP: This is the proactive intrazone routing component, which is implemented as a modified DV scheme. The hop count bounds the zone radius. (2). IERP: This is the reactive component, which uses a query response mechanism, and also employs (3) a bordercasting mechanism which a node uses to send a message to fringe nodes. The bordercasting mechanism which is implemented using multicast or unicast, might actually cause more traffic than flooding, in order to alleviate this problem, the authors suggest three schemes: (1) Loop-back Termination (LT) : Reducing the occurence of a loop, which might arise if a query returns to a previously visited routing zone, through some other node. (2) Query Detection : Uses a promiscuous mode, where the nodes can overhear a query within their zone, and hence avoid a repetition. (3) Early Termination (ET) : If an intermediate node has seen this query before, then it might not forward it. (4)Selective Bordercasting : Select a set of nodes to prevent overlap, while doing the border cast. Simulations: The authors provide fairly comprehensive simulations, showing the performance of the above schemes. the SBC actually increases the total amount of traffic, while the others tend to optimize it. The performance has also been evaluated in under varying node mobility. I think that the paper was very well written and that ZRP is a good extension to the hybrid protocol idea. The simulations cover the mobility aspect very well, however rate of mobility change has not been looked at. Another aspect that might have been interesting is the route maintenance procedure and evaluation. I would also be led to assume that the discovered routes are fairly optimal although there are no results for that. From c.tavoularis@utoronto.ca Thu Oct 11 11:46:07 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BFk6o15656 for ; Thu, 11 Oct 2001 11:46:06 -0400 (EDT) Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 33347]) by bureau6.utcc.utoronto.ca with ESMTP id <238783-16096>; Thu, 11 Oct 2001 11:45:54 -0400 Received: by webmail3.ns.utoronto.ca id <414676-221>; Thu, 11 Oct 2001 11:45:31 -0400 To: COM S 615 Subject: 615 PAPER 21 Message-ID: <1002815127.3bc5be97ecda2@webmail.utoronto.ca> Date: Thu, 11 Oct 2001 11:45:27 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper proposes performance optimizing techniques for the Zone Routing Protocol (ZRP) by implementing effectiving query control mechanisms to detect, prevent and terminate overlapping queries. Successful query control will reduce network delay and control traffic overhead in the system. ZRP is a hybrid protocol that employs proactive routing within a routing zone, and reactive routing between zones. A zone is defined by a radius centered at each node in number of hops, such that the radius is a key parameter choice in the design of ZRP. Intrazone Routing Protocol (IARP) proactively maintains routing information within a zone by forwarding updates, in a modified distance vector manner. Interzone Routing Protocol (IERP) reactively forwards information to the peripheral nodes of a zone (i.e. nodes located at the radius distance), known as Bordercast Resolution Protocol (BRP), and avoids flooding. IERP is triggered only when the destination of a query is outside the current routing zone. The query packet, containing unique ID and accumulated route from source, is forwarded to the peripheral nodes which in turn check their zone for the destination node. When the destination is found, a reply is unicast back via the accumulated route, and the source will select the shortest route received. IERP, IARP and BRP are interdependent and have opposite tradeoffs as seen in the simulation. Since each node has a zone, neighboring zones coincide causing overlapping query threads. Four combinable techniques are proposed to exploit the structure of ZRP to reduce redundancy and overhead. Loop-back termination (LT) requires each node that receives the query to verify the accumulated route for the presence of any nodes within its zone. If so, it will discard the query as the zone has already been inspected. Query Detection (QD1/QD2) implements eavesdropping on queries such that intermediate nodes in the zone detect the query (QD1) as well as neigboring nodes that overhear the IP broadcast (QD2, requiring single channel). Intermediate nodes, in addition to peripheral nodes, may terminate a query thread if they detect that the zone has previously been queried. Selective bordercasting (SBC), as opposed to (full) bordercasting, allows the central node to transmit to a subset of the peripheral nodes, according to the minimal partitioning set of the extended peripheral nodes located 2 radii away. SBC limits loops and overlap, yet increases control traffic and IERP packet size. The simulation analysis of ZRP was very thorough and effective such that each of optimizing techniques were evaluated and compared in terms of control traffic (IARP separate from IERP) and delay. Simplistic assumptions were made regarding the MAC layer to ensure that performance characteristics were a result of ZRP alone (i.e. no collision, contention, or packet loss within dxmit). ET was found to work well in combination with other schemes. SBC incurred a lot of control overhead, but was found to perform better than full bordercast with multi-channel networks, and small zone radii. Since ZRP is proactive within the zone, slow moving nodal environments favor a large zone radius. Similarly, since ZRP is reactive between zones, fast moving nodal environments favor a small zone radius. The radius is a key parameter that depends on the environment, therefore ZRP works best when prior knowledge of mean nodal velocity and route query rate can be exploited. From ramasv@CS.Cornell.EDU Thu Oct 11 12:09:21 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BG9Lo18773 for ; Thu, 11 Oct 2001 12:09:21 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: cs615 PAPER 21 Date: Thu, 11 Oct 2001 12:09:21 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F278@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 21 Thread-Index: AcFSbxYAc4teJs5DR5+Uor3nMXItGw== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f9BG9Lo18773 The Performance of Query Control Schemes for the Zone Routing Protocol This paper is a detailed analysis of the bordercasting activity of a hybrod protocol Zone Routing Protocol. ZRP is a protocol that combines proactive and reactive routing strategies to achieve scalability in a large network. ZRP performs proactive routing through a protocol called IARP in a small region around each node called a zone. This proactive knowledge is then used to in the reactive routing protocol to suppress route query overheads. However routing between distant nodes still remains reactive and is constrained by route maintenance problems in the presence of mobility. ZRP's important contribution is the process of border-casting that is used to reduce the broadcast overhead of route discovery process. Route queries are multicast only to a small set of pheripheral nodes in each zone. Several optimizations are discussed in this paper to improve the efficiency of this border-casting activity. Loop-back termination identifies and terminates route queries being sent back to the query source. QD1 (query detection 1) is a mechanism by each each node detects if the query has already visited its zone. QD2 involves promiscous mode activity to further improve the chances of finding if the query has already visited the zone. By maintaining some extra state an early termination of the queries can be applied for those which has already visited the current zone. An extra delay (RQPD) is incurred on bordercasting to do this more effectively. Further optimizations (SBC) is done by collecting additional information about an extended zone at the proactive protocol layer. Query dissemination can be further pruned by doing this however it comes at an extra cost needed to collect the bordercast tree of the pheripheral nodes in the routing zone. The paper also contains a set of good simulations to evaluate the performance of the different query schemes. SBC shows good performance for multi-channel network while QD1+QD2+ET gives as good a reduction in overhead in single-channel network. The overall overhead of the protocol for query discovery + proactive component shows a nice convex curve with an optimal zone radius depending on the and query rate, mobility. This analysis adds more validity to the paper and its contents. It would be interesting to optimize the zone radius as the protocol is in progress by somehow measuring the query rate and estimating the mobility. The later could be estimated from the amount of updates generated at the proactive layer. It would also be interesting to combine route maintenance activity along with route discovery and measure things like end-end thoughput and latency of ZRP. From viran@csl.cornell.edu Thu Oct 11 12:29:56 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BGTuo21428 for ; Thu, 11 Oct 2001 12:29:56 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9BGTpB06337 for ; Thu, 11 Oct 2001 12:29:51 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Thu, 11 Oct 2001 12:29:51 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 21 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ZRP is a hybrid routing protocol that proactively maintains topology information about a node's closer neighbors (a zone is defined to be on the order of 2 to 3 hops away), and reactively determines routes to nodes that are not within the current zone. This interzoneroute query is done by broadcasting to the periphery nodes (bordercasting) of the current node. Since zones may heavily overlap, such bordercasting may result in queries being forwarded multiple times, thus flooding the network; the authors propose several query control schemes to alleviate this problem. One obvious one is to prevent rebroadcast of queries at nodes that have already seen that query (QD1/QD2). Another is to use early termination and direct queries in an outward radiating pattern. The simulations used a high number of nodes (500), but the separate simulations of IARP and IERP weren't that convincing. IERP simulations were done assuming that the network topology remains constant over the duration a route discovery. I wonder if the correctness of the protocol holds in case of changes. Also, the performance numbers mostly detail ZRP control traffic packet numbers, which isn't that useful on its own. A comparison of ZRP with the new query control schemes with other routing scheme overheads would have been much more useful. From jcb35@cornell.edu Thu Oct 11 12:32:22 2001 Return-Path: Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9BGWMo21631 for ; Thu, 11 Oct 2001 12:32: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 MAA25829 for ; Thu, 11 Oct 2001 12:32:17 -0400 (EDT) From: jcb35@cornell.edu Date: Thu, 11 Oct 2001 12:32:17 -0400 (EDT) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 21 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discussed the Zone Routing Protocol (zrp) for ad-hoc networks. This protocol is an interesting mix of reactive and proactive routing protocols used in mobile ad hoc networking by having each node keep an updated list of the local neighborhood nodes and using route requests for nodes that are beyond its local neighborhood. ZRP distinguishes two "zones" for every node. The first zone is where the nodes proactively maintain routes to all destination - it is basically all nodes within a certain radius (hop-count) of r. Within this zone, the node uses a Inrtazone Routing Protocol (IARP) which can be derived from any proactive link state protocol (ie. it sends route updates out with the ttl being the radius of the neighborhood). Outside the local neighborhood, the protocol uses a reactive method for establishing routes. The paper calls this protocol the IntErzone Routing Protocol (IERP) which uses the idea of bordercasting. This is a way to send messages to the outskirts of the node's local neighborhood. If each node keeps track of an extended routing zone, which is up to 2*radius - 1 hops away, it can use the IARP to decrease the load on the IERP. Each node on the bordercast edges can re-broadcast the route request further until a route is found. Next, the authors address the issue of unnecessary floods across the network - since the neighborhoods overlap, each node could forward a route request multiple times. They have a couple of methods for dealing with this: Query Detection - This is done by a bordercast relay being overheard by another node that is in the same neighborhood that has already seen the route request. Early Termination - using query detection and knowledge of local topology, a node can "prune" its bordercast-tree to ensure requests only go "downstream" and not back toward the source node. random query processing delay - by waiting a certain random delay, a node can see if it's broadcast will not be effective (ie if another node has covered the nodes it would have) and, using early termination, can abstain from forwarding the request. Next, the authors presented performance results. These results were much more extensive than almost any other paper we had read. comments: I thought this was a novel twist to the hierarchical protocols we had looked at before - it requires much less structure and state being kept about the neighborhoods (ie who's the leader), and doesn't seem to have some of the problems they did (like sub-optimal routes). As they said in the paper, I wonder about the tradeoffs of the random query processing delay and when it becomes useful to use it. I wonder if there is an adaptive way to adjust neighborhood size based on how much traffic the node is processing. I would be curious to see comparisons of this protocol other ad-hoc routing protocols, specifically the heirarchical based approaches. It would be interesting to see how much the route lengths improved and how long the requests took for each protocol. I would assume the would use the normal route error type messages that other protocols used, but they made no mention of it in the paper. From egs@CS.Cornell.EDU Thu Oct 18 21:51:41 2001 Return-Path: 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.7) with ESMTP id f9J1pfo21750 for ; Thu, 18 Oct 2001 21:51:41 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f9J1pfe09292 for egs; Thu, 18 Oct 2001 21:51:41 -0400 (EDT) Date: Thu, 18 Oct 2001 21:51:41 -0400 (EDT) Message-Id: <200110190151.f9J1pfe09292@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 21 >From eyh5@ee.cornell.edu Sat Oct 13 20:44:03 2001 >X-UIDL: 9I7"!/WS!!hdM!!gaj"! >Date: Sat, 13 Oct 2001 20:43:43 -0400 (EDT) >From: Edward Hua >To: egs@CS.Cornell.EDU >Subject: ZRP comments for Oct. 11 lecture) > >The Performance of Query Control Scheme for the Zone Routing Protocol > >Zygmunt Haas and Mark Pearlman > >This paper proposes a routing protocol that is a hybrid of the proactive >and reactive routing used in ad hoc networks. The Zone Routing Protocol >(ZRP) has two intergral components to function, Intrazone Routing Protocol >(IARP) and Interzone Routing Protocol (IERP). The former proactively >queries the neighboring nodes of a mobile node to establish a database of >available routes to the neighbors, whereas the latter is invoked when the >destination lies beyond the neighborhood of a mobile node (i.e., reactive >route query). The query control employed in ZRP is the bordercasting, >which, instead of blind flooding of route query, directs query messages >outward, away from the neighborhood of the query originator, thus >delivering the query to un-covered areas expediently. > > In incorporating bordercasting into the IERP, one concern >addressed by the paper is the excessive, redundant querying that may >appear more than once in the routing zone of a node that has already >bordercast the query. To tackle this problem, the authors propose an Early >Termination (ET) mechanism, combined with the query detection scheme and >knowledge of the local topology, that gets rid of the redundant queries >within a routing zone. This mechanism is therefore helpful in combating >query overlapping that results in an tremendous increase in overhead >traffic. > > One of the potential problems this paper does not address is the >redundant query messages from multiple routing zones, each originating >from one peripheral node of the originating querying node. This stems from >the fact that bordercasting does not provide adequate directionality to >direct query messages outward and away from areas that have already been >covered. The proposal in this paper only focuses on directing the query >away from the routing zone of the query originator. If the query same >query message can be eliminated in the overlapping area of the two >neighboring routing zones, further overhead may be reduced. > > A further improvement may be made when selecting different radii >for different routing zones. In this paper, the radius is the same for all >routing zones in the network. This is fine, but it may not offer the kind >of the optimality that may otherwise be achieved by routing zones of >various sizes. This may deserve some further research. > >