From kwalsh@CS.Cornell.EDU Wed Sep 25 12:16:50 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 g8PGGoh00010 for ; Wed, 25 Sep 2002 12:16:50 -0400 (EDT) Message-Id: <5.1.1.6.0.20020925113913.00a8be68@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 12:16:50 -0400 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The Performance of Query Control Schemes for the Zone Routing Protocol This paper proposes and evaluates three mechanisms for query control in the Zone Routing Protocol. The ZRP is a hybrid ad hoc routing protocol, where nodes pro-actively maintain routes within a p-hop zone, and re-actively discover routes between zones. The basic protocol works as follows: Using beacons or other detection mechanisms, each node maintains a link-state topology in a p-hop zone (using the minimum distance between nodes). Zones therefore overlap, especially so when using large radius p. Within a zone, the node is free to construct routes pro-actively according to any Intra-Zone routing protocol (IARP), such as a modified local link-state protocol. In order to reach nodes outside its zone, a node uses the Inter-Zone routing protocol (IERP) as follows: the node "bordercasts" a query message to the periphery of its zone; these nodes then repeat either the IARP or IERP as needed. Radius p controls the degree to which the algorithm is reactive vs. proactive (i.e., increasing p introduces more proactive overhead, but reduces query time). An interesting feature of ZRP is the bordercast mechanism. A node must bordercast a message to its zone's periphery by relaying through zero or more zone members (non-periphery nodes). The node might append to a broadcast an explicit bordercast tree for the zone so that neighbors can relay the message appropriately. Neighbors might then cache this for future use. An alternative approach is to have each neighbor maintain an extended zone of radius 2p-1. So, each non-periphery node in a zone will know how to relay packets to the end of the zone in a proactive manner. This paper tackles the problem of redundant flooding of interzone query messages. Zones overlap heavily, especially with larger radius. Since a node bordercasts to its periphery, and each periphery node does the same, there is the potential for worse-than-flooding behavior. Three mechanisms (QD1/QD2, ET, and RQPD) are introduced to combat this problem, effectively directing query messages outwards from the covered zones. Query detection: QD1 detects and suppresses redundant queries passing through a node (essentially, just caching the query id). QD2 detects queries overheard from neighboring zone members (eavesdropping) and can then suppress later redundant queries. Early Termination: ET prunes a subsequent bordercast tree using previously obtained knowledge of nodes covered. Nodes belong to multiple zones, but only need hear a message once. Random Query Processing Delay: RQPD adds jitter before forwarding queries, giving more opportunity for QD1/QD2 detection and thus more potential for ET pruning. This can be integrated with standard jitter mechanisms for avoiding broadcast collision problems. The evaluation seems thorough, as the authors evaluate numerous combinations of the tree mechanisms each under varying mobility and query-rate scenarios. The paper introduces CMR (call to mobility ratio), measured in calls per kilometer to capture the spectrum between networks benefiting from proactive vs reactive schemes. Unfortunately the data provided do not show ZRP to be very efficient (0-100% gain over pure flooding), even with the optimizations. I enjoyed this paper, as it presented several simple and easy to understand optimizations of a clever algorithm. But perhaps the optimizations are too simple, and something more clever or radical is needed to improve efficiency. From liuhz@CS.Cornell.EDU Wed Sep 25 21:45:25 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 g8Q1jPh00043 for ; Wed, 25 Sep 2002 21:45:25 -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 21 Date: Wed, 25 Sep 2002 21:45:24 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE626@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 21 Thread-Index: AcJk/mHIEzeYKzebS46kz+wt7mc9Xg== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8Q1jPh00043 The main objective of this paper is to provide some mechanisms that can reduce the control traffic and discovery delay of ZRP. ZRP is a hybrid routing protocol that proactively maintains routing information inside a routing zone, while reactively acquiring routes to destinations beyond the routing zone. ZRP is more efficient than purely proactive or reactive routing protocols. However, ZRP can not reduce the control traffic too much due to the overlap of routing zones. To solve this problem, this paper proposes several query control schemes, namely QD1/QD2, ET, and RQPD, for ZRP. QD1 requires bordercast packet to be directed hop-by-hop, thus all relaying nodes along the path are able to detect the query, while QD2 requires a node that's not in the border tree to be able to eavesdrop some other node's query transmission. Information abtained from QD1/QD2, combined with knowledge of the local topology can prevent query messages from entering regions that are already coverred. A realaying node can prune a peripheral node if it has already relayed the query downstream to that peripheral node. That's the job of Early Termination(ET). RQPD is to add some random interval before a node bordercast the query message, thus it can avoid potential overlap of query messages bordercast simultaneously by nearby nodes. A big problem of this paper is the assumption that's fundenmental to all these query control shemes. The paper assumes that after a node bordercasts a query, all the nodes in its routing zone will get the query sooner or later. That's the paper assume the network is a extremely relailabe network without packet loss, corruption etc. Now suppose the bordercast fails to send the query message to a peripheral node(say N). However, the QD1 of other nodes in the same zone indicates that this zone has already been coverred, thus these nodes will reject to relay bordercast on behalf of other zones to N. Thus for those networks in which this assumption doesn't hold, the algorithm will occasionally lead to route discovery failure even the route exists. Another small problem is the paper didn't explain clearly how QD1/QD2 can work independently to reduce the number of query messages. The paper did explain how the information provided by QD1/QD2 can be used by ET to eliminate duplicate queries, but it's not clear to me how they themselves work independently to control the queuy messages H. Liu From shafat@CS.Cornell.EDU Thu Sep 26 00:33:15 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 g8Q4XFh01192 for ; Thu, 26 Sep 2002 00:33:15 -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 21 Date: Thu, 26 Sep 2002 00:33:14 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D1507BE@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 21 Thread-Index: AcJlFdQHpTV/xiT0Qiqrj+6+pI2B/w== 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 g8Q4XFh01192 This paper builds upon a previous work (ref [6]), by the same authors, that presents the Zone Routing Protocol (ZRP), and investigates the performance of query control schemes for ZRP. ZRP is a hybrid routing protocol that uses localized proactive and network-wide reactive routing schemes in order to reduce protocol related control traffic and convergence time. In ZRP, each node proactively maintains a routing zone and stores link-states of neighbors of a fixed constant number of hops away. Route requests are placed on-demand when a node in a particular routing zone wants to communicate with another node in a different routing zone. This constitutes the reactive routing part of ZRP. The paper also does a critical analysis of different optimization techniques in query control mechanisms that could improve the performance of ZRP. Perhaps one of the biggest weaknesses of this paper is the lack of proofreading! Besides that, the paper does a reasonably good job of explaining the three main optimization techniques being tried out for ZRP - QD1/QD2, ET and RQPD. However, to use the first two in practice a distributed bordercast is required instead of a straightforward root directed bordercast. This, as pointed out by the paper, implies that each node should maintain an extended routing zone - thus contributing more towards control traffic. This result also shows up rather expectedly in the simulations. More work can be done in this regard to check if QD1/QD2 and ET can still be implemented using different underlying techniques. Another confusion rises from the way random delays are used in RQPD. It is still not made clear how these random delays are calculated, and what guarantees that the back-off time for two concerned nodes will not be the same. Quite a large amount of simulation data is presented that tests the efficiency of the query mechanism schemes presented in the paper. There remains one standard complaint about the simulations - the use of all mobile nodes. This essentially just tests a scenario where all nodes are constantly in motion, and this fact may justify for more network traffic in the simulation results. However, this may not be desired in a much less dynamic setting. The sudden inclusion of the discussion of multiple channels in the evaluation section was also somewhat difficult to follow, as throughout the entire paper, the mechanisms were all explained in the context of a single channel. From bd39@cornell.edu Thu Sep 26 00:44:57 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8Q4iuh03511 for ; Thu, 26 Sep 2002 00:44:56 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA12101 for ; Thu, 26 Sep 2002 00:44:57 -0400 (EDT) Message-Id: <5.1.0.14.2.20020925214207.00bd8830@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 00:43:52 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The major contribution of this paper is ZRP, zone routing protocol. Zone routing protocol differs from routing protocols we have studied in that the protocol is neither proactive, nor reactive, but a hybrid of the two. On the local, node neighborhood level, ZRP is proactive in obtaining information, but routing between node neighborhoods is done in a reactive manner. p-hop neighborhood information, or Zones, are used to more efficiently broadcast information in the network. The size of the zones, p, is used to adjust the degree to which the protocol is proactive/reactive. Every node in ZRP maintains a p-hop neighborhood link state information through a proactive protocol limited to that region. Interzone routing is performed reactively through bordercasting of the route query message and obtaining a source route. Bordercasting is the process of a node multi-casting a route query to nodes on the periphery of its zone. The paper describes several algorithms which limit the redundant broadcasts in interzone routing. - QD1/QD2: nodes within a zone which participate or overhear a bordercast transmission will know that their zone has been covered already. - ET: nodes can use recent bordercasts from nearby nodes to eliminate the necessity of bordercasting in some zones. A node A that received a border cast from B will not need to bordercast back to B. - RQPD: a random delay is added to the broadcasts, which allows time for the overhearing of other nodes. One aspect of the protocol that may be problematic is the use of overheard receptions to determine whether or not to forward a broadcast. In the case when a periphery node fails to properly receive a broadcast packet, the multicast may not reach parts of the network. This however, can be solved by listening for an ACK in unicast MAC protocols. Also, the growth of the intra-node traffic may cancel out the efficiency gains of bordercasting. ZRP performance seems highly dependent on Zone size depending on traffic patterns. In some cases the difference is a large multiple increase in traffic. It would interesting to have a mechanism to adjust p w/ respect to CMR. From mr228@cornell.edu Thu Sep 26 01:46:24 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 g8Q5kNh12654 for ; Thu, 26 Sep 2002 01:46:24 -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 BAA00246 for ; Thu, 26 Sep 2002 01:46:23 -0400 (EDT) Message-ID: <3D929F42.B660EE71@cornell.edu> Date: Thu, 26 Sep 2002 01:46:42 -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 21 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper presents a nice way to integrate proactive and reactive routing and try to get many of the benefits of each simultaneously. The main contribution, the Zone Routing Protocol (ZRP), is quite simple and effective at doing just that. Each node implements a proactive routing protocol but only within some neighborhood of size K (nodes within k hops). Outside of that neighborhood nodes use a reactive protocol to do the routing. The value of K can be adjusted to nicely "blend" proactive and reactive "amount" depending on the target application. K=0 would be a completely reactive protocol, and k=net diameter would be a completely proactive protocol. This approach has a problem, however. The network traffic used to setup and maintain routes is not decreased as they hope. Since multiple paths into and out of the proactive clusters (neighborhoods) exist, packets end up getting out of these neighborhoods and then later getting sent back in to them. This can create more traffic than just a naive flood approach. The paper proposes many ways in which to deal with this problem: QD1/QD2, ET, and RQPD. QD1 requires that border nodes (nodes in two or more neighborhoods) send messages in a directed fashion to avoid needless duplication. QD2 requires that non-border nodes eavesdrop and not forward packets that have already been seen in this neighborhood. ET works by nodes remembering recent broadcasts from nearby nodes and figuring out neighborhoods where it is clearly not necessary to transmit to. In RQPD a random delay is introduced into the broadcasts in hopes of overhearing someone else transmit a packet before you do, so you can avoid duplication. Their analysis seems to look at many interesting metrics, it seems thorough, and it justifies their approach. I liked the paper a lot -- this is a very nice approach to minimizing the tradeoffs between proactive and reactive routing. -- Mark Robson From jsy6@postoffice2.mail.cornell.edu Thu Sep 26 01:49:32 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 g8Q5nVh13448 for ; Thu, 26 Sep 2002 01:49:31 -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 BAA22176 for ; Thu, 26 Sep 2002 01:49:30 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926014815.00b48c58@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:48:52 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 paper 21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The major contribution of this paper is route query control mechanisms for the Zone Routing Protocol (ZRP) to lessen traffic and delay via overlapping query prevention. ZRP is a hybrid routing protocol because it proactively maintains routing information within its routing zone using IARP and reactively acquires routes to destination outside the routing zone using IERP. IARP maintains local topology by having each node periodically broadcast its link state for a depth of p hops, where p is the zone radius. IERP uses bordercasting, as opposed to broadcasting, for relaying messages outside the source's routing zone. Bordercasting is more efficient than broadcasting because it routes queries to peripheral nodes instead of blindly flooding the message to all neighbors. Due to the overlap in routing zones, uncontrolled bordercasting can lead to more traffic than flooding. To counter excess traffic from redundant querying, the detection (QD1/QD2), early termination (ET), and random query processing delay (RQPD) are introduced. QD1 detects local query relaying activity since the query is directed along the bordercast tree. QD2 works only in a single-channel network. Nodes listen for queries being relayed within their transmission range. In the QD1/QD2 scheme, a Query Detection Table is used to record all queries detected within the routing zone along with the ID of the node that last bordercasted the query. ET makes use of QD1/QD2 and extended routing zone to detect and prevent a query from reappearing in the routing zone that of a node that has already bordercasted the message. Since it takes time for a message to travel along the bordercast tree, there are delays in query detection. This delay offers the possibility of query overlap, despite the implementation of ET. RQPD alleviates this problem by assigning a random delay before a node can bordercast. The choice of the routing radius p is dependent on the call to mobility ratio. A network that is highly mobile but not very active will perform better with a small routing radius. A large routing radius is better suited for a slow moving but highly active network. Since the call to mobility ratio of a network is not static, it might be beneficial to have a routing radius that is dynamic. From hs247@cornell.edu Thu Sep 26 01:51:46 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-0.nyroc.rr.com [24.92.226.125]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8Q5pkh13560 for ; Thu, 26 Sep 2002 01:51:46 -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 g8Q5pjI14262 for ; Thu, 26 Sep 2002 01:51:45 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926015127.00bb00b0@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:51:45 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The main contribution of this paper is the introduction of ZRP (Zone Routing Protocol). This is the first hybrid ad-hoc routing protocol that we have looked at. Essentially each node x has a predefined radius (zone radius). Every node within x's zone radius is in x's zone. Routing within a zone is done with proactive routing, and inter zone routing is done reactively. ZRP claims to take advantage of the benefits of both proactive and reactive properties. There are two parts to ZRP, IARP (intrazone routing) and IERP (interzone routing). The paper states, IARP can basically use any proactive routing protocol. They chose a timer-based link state protocol. Like most proactive protocols, each node periodically tells broadcasts it's local information, but to only the the members in its zone. (Boundary achieved by time on the packets). The meat of the paper is in IERP. When a node wants to send a packet to a node outside of its zone, it must use IERP. IERP is a reactive protocol. It does this by sending the route request packet to its boundary nodes. If the request node is in that boundaries node's zone, we are finished, if not, that node passes on the request to it's boundary node. When the destination zone is found, a reply packet is routed back to its sender. Now, since the zone radius is variable, the larger the radius, the more overlapping in zones there is. One can imagine that a route request broadcast can be costly. The paper introduces the a new concept called bordercast. With bordercast, a node can essentially multicast its packets to the zones. They also introduce 3 concepts to prevent flooding: Query detection (cache and detect duplicate messages), Early Termination(essentially a node will not bordercast to nodes which are in it's zone and also in the src's zone) and Random Query Processing (randomly delaying bordercasts to avoid simultaneous bordercasts). Overall, the paper is pretty simple and easy to understand. One thing I think was glossed over was the implementation of bordercast. Essentially, in order to do distributed bordercast, each node in x's zone not on the border has to keep track of x's information also. This is to avoid x needing to send its bordercast tree along with every bordercast packet. They mention that this adds overhead to IERP, but really glazed over this issue. One can imagine that the large the radius is, the more information a node has to keep about it's neighbour including it's bordercast tree. How does this effect the scalability of the protocol. In the end, the paper does a good job in evaluating the protocol. Some interesting ideas to look at would be to see what could happen if each node had a different zone radius? This might be good because each node in an ad-hoc network may have different properties. Perhaps a node with less battery may want a smaller zone. From mp98@cornell.edu Thu Sep 26 02:17:14 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 g8Q6HDh17590 for ; Thu, 26 Sep 2002 02:17:13 -0400 (EDT) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id CAA05984 for ; Thu, 26 Sep 2002 02:17:13 -0400 (EDT) From: mp98@cornell.edu Date: Thu, 26 Sep 2002 02:17:11 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 21 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <97E7C49C-D117-11D6-A2CA-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.546) ZRP is an attempt to mix a proactive and reactive protocol. The proactive portion is achieved by each node communicating to its neighbors within a number of hops called the zone radius. Within the zone radius, a node maintains global knowledge (the paper suggests using link state routing) of all its neighbors. This portion of the routing protocol is referred to as IARP as opposed to IERP. IERP is the part of ZRP used to send packets beyond the neighborhood. Here route request packets are "bordercast" to nodes on the edge of the neighborhood, who "bordercast" them in turn to build a route similar to the method of DSR. When a node finds that a node in its neighborhood matches the destination of a route request packet, it sends a reply back. To alleviate the flooding nature of IERP, the authors suggest some query control mechanisms like delaying retransmission to wait for new information and pruning certain border nodes (nodes which are p hops away where p is the zone radius) and maintaining extended zone knowledge (2p -1) to help with the decisions. The paper has an extensive simulation and shows that it helps more in a multiple channel environmental than single. The protocol itself is noteworthy for the way it uses proactive routing in an intelligent manner, rather than just to do hello beacons all the time. The use of bordercasting over broadcasting is an intuitive improvement: Hopefully, neighborhood knowledge means this can be implemented through unicasts. Ultimately, I feel their weakness-and room for improvement--lies in their RDB (root directed bordercasting) and DB (distributed bordercasting) approaches to bordercasting. The amount of traffic generated by DB is absurd: It scales per node as twice the size of the zone radius while the number of nodes covered scales proportionally to the square of this radius. In a network of small diameter (entirely possible depending on the circumstances), this could mean every node is keep track almost of global information for the whole network. The authors feel, however, that RDB increases the size of a packet unfairly. But this is using their naive approach of attaching the tree to each packet. If A and B are both border nodes, reachable through C and D, then the root R does not need to include the D-B path in the packet sent to A-B. One could imagine with intelligent processing, reducing the size of the RDB information dramatically. From xz56@cornell.edu Thu Sep 26 02:55:58 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 g8Q6twh24188 for ; Thu, 26 Sep 2002 02:55:58 -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 CAA04839 for ; Thu, 26 Sep 2002 02:55:58 -0400 (EDT) Message-ID: <00c801c26529$c1591320$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 21 Date: Thu, 26 Sep 2002 02:55:52 -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 ZRP is a hybrid routing protocol and has the advantages of both proactive and reactive protocols and avoids the shortcomings by applying them in different scales. Within a local neighborhood, as they called, a "routing zone", whose radius is p-hop (p=1, flooding; p=inf, LS routing), IARP is used. IARP is a timer-based, LS protocol. LS info is obtained by using 'hello' beacons broadcasted periodically between neighbors. This makes each node has the complete info about the local region and optimal paths to each node in this region. At the same time, these control messages are limited only within the routing zone, so there is not the problem of excessive overhead as there is in proactive routing. Outside the zone, IERP is used. The main idea is that, the route is found using DSR in a jumping fashion with each jump equals to p hops. Since the nodes know the path to all other nodes in routing zone, only the border nodes are involved in this reactive path finding. Based on this, different from the standard flooding, it uses "bordercast", which greatly reduced the amount of rebroadcast by intermediate nodes. It further optimize it by using ET to prevent the interior nodes from rebroadcast packets, and by using RQPD to inhibit border nodes rebroadcast when it's coverage overlaps with someone else. Both IARP and IERP should deal well with mobility. The performance analysis is quite thorough. Since the IERP uses DSR strategy, it has the problem similar to DSR, i.e. the scalability. Since it doesn't take the advantage of the recent route info, it has not the problem caused by stale route info. Also, in the illustration used in paper, the routing zone is not only based on hops, but also physically like a circle with border nodes on it. In reality, it maybe not that ideal. The path found can not be optimal in terms of number of hops. Don't quite understand why ET is useful if border nodes can be recognized with full link state info. From ag75@cornell.edu Thu Sep 26 04:21:28 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 g8Q8LSh07863 for ; Thu, 26 Sep 2002 04:21:28 -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 EAA01154 for ; Thu, 26 Sep 2002 04:21:27 -0400 (EDT) Message-ID: <001d01c26535$be733ad0$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 21 Date: Thu, 26 Sep 2002 04:21:41 -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 presented us with improvements to the ZRP routing protocol. ZRP is a hybrid reactive/proactive protocol that's based on the idea that querying can be performed more efficiently than flooding by directing route requests to target peripheral nodes. While the authors give us a general overview of how ZRP works, the details are in the papers they reference. Thus, it's hard to say much about the protocol. The main focus of the paper is on improvements to the ZRP protocol. The authors present us with 3 improvements: querry detection (QD), early termination (ET) and random querry processing delay (RQPD). The goal of these query control mechanisms is to reduce route query traffic by directing query messages outward from the query source and away from covered routing zones. QD allows the intermediate relaying nodes to detect a query. ET eliminates many redundant messages. RQPD spreads out bordercasts to eliminate more redundant messages. The simulation of these improvements is impressive in some areas, but disappointing in others. The simulated network consists of 200 mobile nodes, which is very impressive, distributed over an area of 1000 x 1000 meters , which is big, and the nodes are allowed to move at a high speed of 25 m/s. They also ran this simulation on 50 different configurations, which is also a lot. On the other hand, their assumptions are unsatisfactory. They assume that links are bidirectional, that the channel access is contention free, and that neighbor discovery beacons are not destroyed by collisions. Since the nodes were randomly distributed they did not test for worst case behavior. Each simulation only lasted for 125 seconds and the authors did not record the data for the first 5 seconds. Finally, the simulation was ran under the assumption of low load, where the amount of application traffic is negligible compared to ZRP control traffic. It would be very interesting to see how the algorithm and the improvements behave under high load. From nbs24@cornell.edu Thu Sep 26 08:53:43 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8QCrhh27813 for ; Thu, 26 Sep 2002 08:53:43 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id IAA24322; Thu, 26 Sep 2002 08:53:38 -0400 (EDT) Date: Thu, 26 Sep 2002 08:53:38 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209261253.IAA24322@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 21 Zone Routing Protocol The paper proposes the zone routing protocol, ZRP, a hybrid ad hoc protocol that maintains routing information within overlapping routing zones (with zone radii of งค hops) proactively and discovers routes across zones reactively. They introduce the bordercasting resolution protocol, BRP which multicasts messages to peripheral nodes which border the zones. The setback with having overlapping zones is the heavy traffic caused by nodes forwarding route requests multiple times. The paper discusses three techniques (query detection, early termination and random query processing delay) to prevent query messages from returning to covered nodes. Query detection is achieved on two levels, one by bordercast relay and the other by eavesdropping. Early termination takes advantage of query detection combined with knowledge of local topology to prune any downstream branches of a bordercast tree which lead to peripheral nodes in covered regions. Random query processing delay prevents simultaneous bordercasts by inserting a delay before bordercast tree construction and early termination. The authors provide elaborate simulation results for a wide range of performance configurations and observe that reactive configurations (smaller zones) are more suitable for networks with a low route query rate to node speed ratio. It is possible that a zone will have only one peripheral node. What if this node fails? The paper does not discuss node failure and collisions, even with all the high traffic being generated. A build to the research would be to perform simulations on a larger network to determine how scalable their protocol is. It would also be nice to see the effect of non-overlapping routing zones with different zone radii. Nana B. Sam From tmroeder@CS.Cornell.EDU Thu Sep 26 10:02:25 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 g8QE2Ph10840 for ; Thu, 26 Sep 2002 10:02:25 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g8QE2OW23962; Thu, 26 Sep 2002 10:02:24 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15763.4976.596081.666185@dhcp99-233.cs.cornell.edu> Date: Thu, 26 Sep 2002 10:02:24 -0400 To: Emin Gun Sirer Subject: 615 PAPER #21 X-Mailer: VM 7.07 under Emacs 21.2.1 The Zone Routing Protocol is the first hybrid protocol that we have examined. It creates a zone around each node (the number of hops comprising a zone being a parameter of the protocol) for which the center node of the zone maintains local state proactively, and routes between zones reactively, by using what they call "bordercasting". The idea is to send the packet to the edge of your zone and let the peripheral packets of your zone do the same (ie. send to the border of their zone), and so on until the route is discovered (checking each time, of course to see if the node does not happen to be within each zone). They suggest a collection of techniques to avoid duplicate messages in the network, and evaluate them in simulation for a variety of parameter settings. The general structure of protocol seems to provide exactly what they are seeking: local changes being stored locally and far-away routes being discovered relatively quickly. Two assumptions on which this paper strongly leans are bidirectionality and that the nodes are moving slowly enough that the route discoveries can happen before significant changes to the topology occur. Since both of these assumptions are common in the literature, we can for the moment leave them unexamined. It will quickly become obvious in a real situation whether they hold up well or not. The general conclusion of the graphs seems to be that the more queries you have per second, the wider the routing zones have to be to make a difference. I would like to see results from a real network, since their results came from a custom-built simulator, and so it is hard to say how the performance would be in practice. There is little discussion of scalability, although they claim that the problem with scaling in ZRP is down to smaller amounts of data, and don't mention scaling up to more nodes. It seems that this is an argument which ought to be made, since the very nature of a zone protocol is to shrink the effective size of the network, and so the natural question to ask is: "how effectively does it perform this shrinkage?" From vrg3@cornell.edu Thu Sep 26 11:09:32 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 g8QF9Wh25415 for ; Thu, 26 Sep 2002 11:09:32 -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 LAA08002 for ; Thu, 26 Sep 2002 11:09:30 -0400 (EDT) Date: Thu, 26 Sep 2002 11:09:30 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@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 presents the Zone Routing Protocol, a hybrid between proactive and reactive routing. Each node has a local neighborhood of fixed radius inside which a proactive routing scheme is used. To communicate outside the local neighborhood, a node uses a "bordercast" to discover a route. Bordercasting is like broadcasting except that the desired behavior is for as few nodes in the local zone to retransmit the packet as possible. Bordercasting is an interesting concept. The paper mentioned two ways to achieve this. One involves the source specifying the entire route to the border (since the source knows complete routes to all other nodes in its zone); the result can be unacceptably large packet overhead. The other involves every node actually maintaining knowledge of an extended routing zone of nearly double the radius of its normal zone. This results in three levels of zoning: the immediate zone, the extended zone, and the area outside. Another issue in bordercasting with ZRP is that, since nodes' local zones overlap, without some control mechanism route requests can end up redundantly re-forwarded many times over. The proposed solutions in this paper are query detection algorithms QD1 and QD2, which rely on either active or passive eavesdropping of routing requests, an early termination (ET) algorithm whereby a node can prune part of its bordercast tree, and RQPD, Random Query Processing Delay, which helps avoid the problem of simultaneous requests. ZRP seems a little inspired by CEDAR; in a sense its route discovery protocol is like a more distributed version of CEDAR. The idea makes a lot of sense, and I was impressed by their simulation and analysis. It is important to note that they found that several of their metrics had local minima with respect to zone radius, and that radius was usually 3 hops. I was pleased to note that they had included a mobility model, and think it would be interesting to see a simulation with a model that includes some periods of stationary rest, where a proactive approach is stronger. From ashieh@CS.Cornell.EDU Thu Sep 26 11:12:44 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 g8QFChh25672 for ; Thu, 26 Sep 2002 11:12:43 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8QFChs26156 for ; Thu, 26 Sep 2002 11:12:43 -0400 (EDT) Date: Thu, 26 Sep 2002 11:12:43 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 21 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ZRP is a hybrid protocol that is locally proactive and globally reactive. Each node proactively sends link information outward for some tunable radius delta. Thus, each node collects information about all neighbors within delta hops (a "zone"), and so knows some set of routes to all these neighbors. A reactive protocol is used to route between zones. Route discovery is sent using a "bordercast" technique; that is, multicast from a receiving node to its border nodes, which then retransmit the information. The goal of bordercasting is to send route queries to all nodes in some (hopefully small) delta-dominating vertex set of the graph; this set of nodes would be aware of the complete network topology. Since bordercast may skip nodes, the zones do not overlap, and the multicast trees of neighboring/overlapping zones may be quite disjoint, it is possible for a bordercast to be transmitted back towards the originating node. Nodes that have previously heard some bordercast do not relay a subsequent bordercast of the same advertisement (caching bordercasts works if the zones are small, or the multicast trees have good overlap; otherwise, sniffing is necessary). This hybrid design exploits the spatial locality of communications (close nodes are likely to communicate with each other, and may expect some sort of real-time routing guarantee), and the property that a moving node would remain within the neighborhood of some set of nodes for some period of time. Thus, as long as a message is routed through some subset of these nodes that proactively maintain contact with the moving node, the message is likely to successfully reach that node. According to the data analysis in the paper, ZRP successfully captures this property: so long as a node moves sufficiently slow relative to the zone size (so that the node stays within a zone for some period of time), and enough route requests are sent to that node during that period of time, then the cost of proactively maintaining routing information within a zone is amortized over sufficient requests for better performance over a purely reactive scheme. This paper also points out a tradeoff between using centralized and distributed multicast tree computation. Centralization requires source-directed routing, while distribution requires that each node have some knowledge of the other nodes in the multicast tree. Since zones overlap, in a distributed case each node must have knowledge of 2x the radius of a zone to compute the multicast tree for each zone for which it is a member. ** Shortcomings The authors did not completely explain the cause of the different results for multi-channel vs single-channel. ** Future work - Can we use a TORA-like algorithm to construct distributed global knowledge of the zones during standard bordercast/neighbor discovery? Such information may then be used to directly solve the bordercast propagation problem. - If a node can approximate its movement speed (possible at low speeds with cheap accelerometers), one could perhaps cause fast-moving nodes to proactively propagate its routing information over a larger distance than a slow-moving node; this allows us to Moreover, we might not want to route through a fast-moving node since such a route is likely to be unstable. From linga@CS.Cornell.EDU Thu Sep 26 11:25:01 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 g8QFP0h28761 for ; Thu, 26 Sep 2002 11:25:01 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8QFP0h23693 for ; Thu, 26 Sep 2002 11:25:00 -0400 (EDT) Date: Thu, 26 Sep 2002 11:25:00 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 21 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ZRP (Zone-routing protocol) ZRP is a hybrid algorithm which uses proactive routing to maintain routing information for a routing zone and reactively (on-demand) figures out routes to destinations. Routing zone of a node consists of nodes which are atmost hops away from the node. Cons of proactive protocols: 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. With this in mind, the main idea of ZRP is to limit the proactive part to the nodes routing zone and use peripheral nodes (nodes which are exactly hops away from the node) for discovering routes on-demand. A Neighbor Discovery Protocol (NDP) is used to discover neighbors using "hello" beacons. IntrAzone Routing Protocol (IARP) is to monitor the routing zones proactively. This involves each node periodically broadcasting its link state to a depth of hops (say, using TTL). Then comes IntErzone Routing Protocol (IERP). This is used to establish routes to destinations (which are not in the routing zone of the source). Source node generates a route request packet which is uniquely identified by source node's id and the request number. This packet is broadcast to all the peripheral nodes of the source node (this is efficiently done using Border Resolution Protocol(BRP)). When a node receives this packet if the destination is in its routing zone it directly forwards the pkt to the destination. Otherwise it appends it's id to the packet and forwards the pkt to its peripheral nodes. The destination will send a route reply packet to source by reversing the accumulated route. Note that a single route request pkt will result in multiple route replies. Quality of these routes can be determined by some metric accumulated during the propagation of the query. A bordercast tree (to reach the peripheral nodes) is constructed using a distributed algorithm where each node in the routing zone constructs its own tree by broadcasting to 2*-1 hops. A route request could reappear in the zone which has already seen the request. To avoid redundant work query detection and query control mechanisms have been proposed in the paper. Performance results show the efficacy of the approach. Pros: One of the first of its kind which has the advantages of both proactive and reactive routing protocols. By restricting the proactive part to a routing zone disadvantages of proactive protocols are minimized. Using the peripheral nodes routes could be discovered much quicker than a normal reactive protocol, decreasing the delay considerably. Thus ZRP considerably reduces the control traffic required. Cons: A single route query packet results in multiple routes. But there is no easy way of constraining the number of routes returned (we could retrict the number of routes using some metrics but not restrict the number of routes we are interested in!) So potentially we could have a lot of routes where potentially only one is used, thus resulting in a lot of unproductive messages. Performance results assume a random distribution of nodes and do not investigate realistic topoligies and realistic workloads (nor does any paper we have seen to date). Protocol is now more complex using some advanced query control mechanisms unlike a pure proactive or reactive protocol which are conceptual simple. From smw17@cornell.edu Thu Sep 26 11:29:01 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 g8QFT0h29728 for ; Thu, 26 Sep 2002 11:29:00 -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 LAA01847 for ; Thu, 26 Sep 2002 11:29:01 -0400 (EDT) Message-ID: <3D9326FF.8080403@cornell.edu> Date: Thu, 26 Sep 2002 11:25:51 -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 21 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit ZRP The Zone Routing Protocol (ZRP) is a hybrid routing protocol, with both proactive and reactive portions. The basic operation of ZRP is fairly simple. Each node has a zone surrounding it for which it maintains a complete routing table. Thus, any route within this zone is a fast, proactive routing process. In order to route to nodes outside a node's local zone, the originator performs a bordercast, in which it transmits the packet to be forwarded to all nodes at the edge of its zone. Each of these nodes then checks their own local zone for the destination. If found, the node adds itself to the query request and forwards it to the destination. If the destination is not in the forwarding node's zone, it adds itself to the query and repeats the bordercasting procedure. In this way, the message path is defined as a series of peripheral nodes that comprise the desired route. This system may also be adapted to a distributed bordercast protocol, which reduces the per packet overhead for inter-zone communication at the price of increased effective zone size (2*p-1) being stored. From this basic system, the paper also presents a mechanism for limiting the propagation of redundant information. This is done with a few different schemes. The first scheme is Early Termination (ET), which seeks to detect when bordercasting to a peripheral node would cover ground already covered, and either restrict the bordercast or if sent, to refuse to propagate redundant information. The ET scheme makes use of two other schemes, QD1/QD2. QD1 simply states that nodes forwarding a bordercast query (i.e. - interior nodes) can recognize the packet as a query request. QD2 is an extended detection scheme, relying on nodes eavesdropping on transmissions to detect queries, thus extending the knowledge beyond the set of forwarding nodes. Based on this knowledge of the routing history, nodes can prune nodes in an intelligent fashion, reducing the routing bandwidth overhead. The second mechanism presented is a random delay mechanism. The main idea in the RQPD (Random Query Processing Delay) is that by adding the delay, it is possible to perform a more thorough pruning of the bordercast tree and save network bandwidth, as a nearby node may also be transmitting into one of your coverage zones. I like the general idea presented here, of a hybrid system trying to achieve a balance between the speed and (route creation) simplicity of a proactive algorithm with the bandwidth, storage, and complexity savings of reactive algorithms. The presentation of the various schemes possible (Table 3) gives an idea of the possible implementations in vastly different networks, and the consideration of multiple-channel hardware where promiscous mode is not reasonable was welcome. I was a bit uncomfortable with the complete omission of data for the first five seconds 'to let the network settle'. Granted, this data may not be directly related to steady state performance of the protocol, but some idea of the transient behavior would be nice, to observe the actual convergence of the system. I do find it interesting that in the presentation of results, the ZRP seems to only significantly affect the traffic patterns for multiple- channel cases. Basically, their implementation of ZRP not only does not require a broadcast medium for query floods (still necessary for 'hello' messages), but results in higher savings in non-broadcast conditions. Given the power overhead of running in promiscious mode, and the simulations presented that show that ZRP can bring multiple channel packet overhead much closer to single channel overhead, there may be some interesting applications of ZRP to power-aware systems, or to inherently multi-channel devices where a single-channel broadcast is not practical. From mtp22@cornell.edu Thu Sep 26 11:41: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 g8QFfPh02455 for ; Thu, 26 Sep 2002 11:41:25 -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 LAA13259 for ; Thu, 26 Sep 2002 11:41:22 -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 21 Date: Thu, 26 Sep 2002 11:41:30 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02092611413003.00155@narnia> Content-Transfer-Encoding: 8bit A major contribution of this paper is mechanisms to reduce flooding in ZRP and similarly structured protocols. ZRP is a hybrid protocol relying on a proactive protocol to establish routing within zones and a reactive protocol combined with the bordercast protocol to establish routing between zones. The mechanisms to reduce flooding include query detection, which involves nodes listening for overlapping bordercasts, random query processing delay, which involves waiting a random interval before propogating the request so as to increase the chance of overhearing, and early termination, which involves intermediate nodes terminating a bordercast. A weakness of the paper is that the analyses assume that the network does not change during a route request. Leaving this out could affect the discussions on zone size, making the optimal zone size smaller than the paper would indicate. A possible extension of the paper is dynamic determination of the zone size. Determining the zone size before the network is deployed requires an accurate model of how the nodes in the network will move and what the applications will require; this is often difficult to determine a priori. From mvp9@cornell.edu Thu Sep 26 11:52:25 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 g8QFqOh04743 for ; Thu, 26 Sep 2002 11:52:25 -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 LAA26679 for ; Thu, 26 Sep 2002 11:52:21 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926115129.01a7a960@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:52:21 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 21 Mime-Version: 1.0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable This paper discusses a hybrid protocol, ZRP and improvements to its inter-zone query distribution mechanism.  The ZRP isn=92t exactly new, and it resembles the CEDAR in that the network is partitioned into regions; ZRP=92s zones are maintained for each node, so there is no backbone.  It is proactive within the zone, accelerating local communication and reactive outside it, lowering the overhead for network-wide queries.  The latter are sent by =93bordercasting=94  the source sends a query directly to its periphery nodes, they to their periphery, etc, with considerable savings over flooding.  The other contribution is a set of query control mechanisms, that enforce those savings.  When nodes bordercast, the authors=92 set of 3 QCM=92s Query Detection, Early Termination, RQPD try to ensure that packets stream away from the source, so that no node gets a given bordercast more than once.  Evaluation is performed to test how various combinations of parameters and these mechanisms affect channel load.
The strongest points presented are the simplicity of the overall protocol and the apparent effectiveness of ZRP with the proposed additions.  There is an extensive comparison of combinations of different options, but unfortunately no comparison with other protocols, or measurements of delays improvements.  They claim at the end of the paper that it is =93twice as fast=94 as other =93traditional flood-search=94 queries in multi= ple channel networks, although it is not substantiated; and the prevalence of multiple channel setups is also not commented on.  They also claim in passing that the routes found are optimal(p5), providing no evidence for it.  Another concern is the requirement for error-free delivery in the simulation  is it required by the protocol and what happens if there is no such guarantee?
        The protocol appears attractive, but more calculation and/or simulation should be done to evaluate the claims presented.  A small modification that may turn out to be useful for RQPD is instead of using random times for waiting, try to base it on a small number that=92s still more likely to be unique than random (such as hop count in an earlier paper), but perhaps use some node id if its handy. From pj39@CS.Cornell.EDU Thu Sep 26 11:53:30 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 g8QFrUh04927 for ; Thu, 26 Sep 2002 11:53:30 -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 LAA01884 for ; Thu, 26 Sep 2002 11:53:27 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926115204.00b8ac70@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 11:53:23 -0400 To: egs@CS.Cornell.EDU From: Piyoosh Jalan Subject: 615 PAPER 21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The Performance of Query Control Schemes for the Zone Routing Protocol This paper on ZRP presents a hybrid protocol for routing in mobile ad-hoc networks. ZRP uses uses a proactive protocol for routing within a zone and it reactively acquired routes for inter zone routing. The hybrid routing thus is more efficient than pure proactive or pure reactive protocols. In ZRP each node in a zone maintains link state of neighbors by the use of HELLO messages. Whenever there is a packet to be sent from a source to a destination, if the destination is in the same zone as source than using the intrAzone routing protocol (IARP) the packet is routed, if the destination is in a different zone than a reactive intErzone protocol is used which employs global route discovery. IERP is different from other reactive protocols as instead of broadcasting it uses bordercasting, where a node sends a message to it's peripheral nodes these nodes than repeats the process depending on the destination being in or out of their zone. There are some potential weaknesses in the basic ZRP protocol. As there are considerable overlap between zones there may be at times that packets generated through bordercast exceed that of broadcast or flooding. The author introduces three mechanism to combat this QD1/QD2, ET and RQDP which steers queries away from the areas that have already been covered. One of the other major strong points of this paper is its simulation. Simulations are performed over a range of routing zone radii, from purely reactive routing to purely proactive routing. This gives a clear distinction of the advantages of a hybrid protocol over pure reactive and pure proactive protocols. One major drawback in the simulation again was that all the nodes were considerd to be constantly mobile. Simulation should be performed where some nodes are not always mobile. Future work could be directed towards finding appropriate radii for zones for different network conditions where some nodes are highly mobile some are static. I think this paper would go a long way in shaping the future routing protocol for manets. From ks238@cornell.edu Thu Sep 26 12:34:26 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 g8QGYPh13882 for ; Thu, 26 Sep 2002 12:34:25 -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 MAA14432 for ; Thu, 26 Sep 2002 12:34:25 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926123310.01cf1d00@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:33:40 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper 21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In this paper, the protocol ZRP, a hybrid of a proactive and reactive approach to transferring data in ad hoc networks is presented. There are two integral facets of the ZRp protocol. The first idea pertains to the defining of local routing zones, which may have a diameter of 1 or 2 hops from a source node. These routing zones are discovered using intrazone routing protocol (IARP), which uses a proactive method that entails broadcasts within the routing zone for the process of route discovery and route maintenance. The second facet of this protocol pertains to route discovery between zones. This process known as interzone routing adopts a reactive methodology which employs bordercasting, opposed to broadcasting, to create routes that cross routing zones. Once the route has been discovered using either intrazone routing or a combination of intrazone and interzone routing, a route reply packet is sent back along the discovered route. The topology of the network is updated through the use of route update packets at the MAC-level and link failures are handled. One of the problems that is addressed is the redundancy that may occur in the network due to overlapping of routing zones. Query Control mechanisms such as Query Detection, Early Termination and Random Query Processing Delay are implemented in order to mitigate the problems associated with overlapping routing zones which may congest the network unnecessarily with redundant transmissions. A simulation follows the discussion in which these Query Control mechanisms are shown to demonstrate substantial improvements in preventing network congestion. Also, the simulation concludes that the radius of routing zones increases as the mobility in the network increases as well. The clear contribution of this paper was the idea of combining both a reactive and proactive protocol. Some interesting points of discussion would be evaluating the performance of the protocol in extremely clustered networks. It seems that given this topology, a reactive approach in which routes are found on-demand would be better than ZRP. The reason for this would be that in clustered topologies the routing zones are substantially smaller in size, which means that there are a tremendous number of broadcasts associated with each route discovery request. Many of these broadcasts may seem irrelevant (not necessarily redundant). Obviously, one can increase the radius size, but then you simply return to a reactive approach anyways. The author's limit their comparison of topologies varying in mobility. On the reverse side, other topologies may suggest that proactive approaches are more efficient. I feel that ZRP is suitable for a specific type of network (i.e. evenly distributed and not too mobile), which may be a limiting factor. From sc329@cornell.edu Thu Sep 26 12:55:30 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 g8QGtUh17972 for ; Thu, 26 Sep 2002 12:55:30 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA04656 for ; Thu, 26 Sep 2002 12:55:29 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926125217.00b101d0@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 12:55:34 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed submitted by - Sangeeth Chndrakumar The performance of query control schemes for the zone routing protocol. This paper describes some effective query control schemes to reduce the control traffic overhead in a Zone Routing Protocol. ZRP is a hybrid protocol; pro-actively maintaining information about the local neighborhood and reactively acquiring routes to destination beyond the routing zone. The construction of a routing zone is requires the node to be aware of its neighbors.IntrAzone Routing Protocol(IARP) is used for neighbor discovery in this scheme. The routing zone can be varied by changing the hop counts. For route discovery to destinations, which are further, IERP is applied. Source generates route requests, which are broadcast by the peripheral nodes to the peripheral nodes of its routing zone till the packet finally reaches the destination or to some other intermediate nodes which is aware of a path to the destination. In the route reply, the entire path is reversed and send back to the node that generated the request. In case of multiple responses, the one with the best hop count is chosen. Route discovery time can further be reduced by distributed bordercasting, in which an extended routing zone is maintained by the root node. Bordercasting can reduce the number of control packets send. But because of routing zone overlaps, the control messages can infact turn out to be a bigger problem. This paper proposes a few mechanisms to avoid this: - Query Detection : by collecting information while relaying a packet to the peripheral nodes(QD1) and also by eavesdroping on other transmissions(QD2), redundant query transmission can be prevented. - Early Termination : A bordercasting can be terminated by not only peripheral nodes but also intermediate nodes, if it is already part of the routing zone. - Random Query Processing Delay : By incurring a certain delay, simultaneous broadcasting be avoided by two overlapping border nodes. The authors have given an extensive simulation of the protocol comparing the tradeoffs between IARP and IERP, under various mobility, nodes and other various protocol-specific parameters. As 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. Apparently, the simulation finds near optimal zone configurations that yields lowest traffic overhead. The only factor that actually indicates an additional tradeoff is the query jitter. 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. From yao@CS.Cornell.EDU Thu Sep 26 13:14:10 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 g8QHE9h22265 for ; Thu, 26 Sep 2002 13:14:09 -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 21 Date: Thu, 26 Sep 2002 13:14:09 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D43024797F5@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 21 Thread-Index: AcJlgCD+6eqfD1/oSZuGaLRA1nsLxQ== 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 g8QHE9h22265 The Authors present an hybrid routing protocol, ZRP, and how to reduce the control overhead through query control schemes. ZRP combines both proactive and reactive routing protocols. It uses proactive routing for neighbor nodes, while switches to reactive routing for faraway nodes. It makes a trade off between cost and delay by integrating two different routing schemes together. ZRP has two main components, intrazone routing and interzone routing. The intrazone routing is responsible to maintain topology information around a node. Each node exchanges its neighbor information to other nodes within its zone. It is very similar to a limited link state algorithm. Interzone routing may generate route requests to unknown nodes which are outside the node's zone. Unlike flooding in traditional reactive routing protocols, route requests are only sent to a subset of nodes, which is the main benefit of ZRP. A node will only forward a route request to its peripheral nodes through bordercast, and peripheral nodes will relay the request to their own perpheral nodes, unless the destination is in their zones. In this case, a route response with the exact route information is sent back to the source. The paper also addresses an imporant problem related to such routing protocols. Since zones between a node and its periherals overlaps, a well designed query control schemes is necessary to prevent redundant transmission of route requests. The paper discusses how to detect such redundant queries, and how to termiante them early. A detailed evaluation section is included at the end of the paper. It analyzes the perforamce of ZRP under various circumstances. The effects of differnet parameters are also well studied. However, there is no experiment to compare ZRP against other popular routing protocols, like DSDV or AODV. The main problem I concern about ZRP is its overhead. First, although the size of a beacon message is much smaller than that of the link state algorithm, their frequencies are close. Since a large portion of energy is consumed to transmit a packet, no matter how small it is, the cost to maintain the zone structure at all nodes is not neglecible. Second, bordercast is based on unicast, which is two or three times more expensive than the broadcast in the flooding. It is not clear to me how much benefit can be achieved by bordercast in ZRP. Yong Yao From vivi@CS.Cornell.EDU Thu Sep 26 13:44:25 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 g8QHiPh29200 for ; Thu, 26 Sep 2002 13:44:25 -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: 615paper21 Date: Thu, 26 Sep 2002 13:44:25 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF76@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper21 Thread-Index: AcJlhFrDxhVceDYaQR6NI0Ib++HpOg== 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 g8QHiPh29200 ZRP The paper describes mechanisms to limit the number of control packets sent in ZRP. It proposes Query detection, Early Termination of queries to downstream nodes, and Random Query Propagating Delay to achieve this goal. ZRP is the first hybrid routing protocol we have come across in this course. Each node proactively maintains routing information about all nodes in its routing zone. When it needs a route to a node outside its routing zone, it gets it reactively. Though the above methods lead to substantial pruning of the transmitted messages, the associated overhead of storing the {source,id} pair for each query has not been discussed. ZRP uses an innovative strategy to avoid the problems associated with source routing - namely, the size of the packet getting untenably large. Each node maintains the multicast tree topology of all the nodes in its routing zone, by keeping track of the topology of an extended rting zone. The simulations are better in a sense than the ones we have seen so far, as they are not run with seemingly randomly picked parameters; rather they try and find the best parameters. (Eg: The velocity of the nodes is varied over a wide range; the optimum routing zone radius is found to be a function of the CMR, etc.) Weaknesses: - Very strong assumption that Hello messages are not destroyed due to collisions. - Though the authors seem to have conducted reasonably extensive simulations, they have not taken spelled out the inferences that could be drawn from each graph. From aed13@cornell.edu Thu Sep 26 14:47:45 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 g8QIljh13463 for ; Thu, 26 Sep 2002 14:47:45 -0400 (EDT) Received: from andyd-laptop.cornell.edu (syr-24-58-57-97.twcny.rr.com [24.58.57.97]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id OAA29420 for ; Thu, 26 Sep 2002 14:47:44 -0400 (EDT) Message-Id: <5.1.0.14.2.20020926143730.0253d438@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 26 Sep 2002 14:47:44 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 Paper21 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper " The Peformance of Query Control Schemes of the Zone Routing Protocol" introduces methods for reducing query traffic in a hrybrid routing protocol. ZRP is a hyrbrid routing protocol utilizing proactive linkstate based protocol for Intrazone routing and a reactive protocol for route discovery(Interzone). The zone based concept establishes zones of a hop count radius, with the edge nodes known as peripheral nodes. Within the zone a standard link state protocol is used to maintain routing information, and all messages reach is curtailed by a TTL(hop count). When a node requests a destination outside it's zone it reactively transmits a Query request to it's peripheral nodes, who then bordercast the query request out to their known peripheral nodes. At each hope current node id is added to form a return path. They make the assumption of multi casting capability to reduce traffic, and implement a serious of Query Detection schemas to reduce flooding. The performance analysys lacks comparison to other protocols and makes poor assumptions on the behaviors of the 200 nodes in the network, specifically random location and constant speed in random directions.