From daehyun@csl.cornell.edu Tue Sep 18 01:11:18 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 f8I5BIq12864 for ; Tue, 18 Sep 2001 01:11:18 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id BAA23572 for egs@cs.cornell.edu; Tue, 18 Sep 2001 01:11:13 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109180511.BAA23572@wilkes.csl.cornell.edu> Subject: 615 PAPER 10 To: egs@CS.Cornell.EDU Date: Tue, 18 Sep 2001 01:11:13 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper proposes a routing algorithm called Associativity-Based Routing (ABR). In ABR, routes are established on-demand and only the actually desire routes are maintained. ABR selects a route based on nodes having high associativity states that imply high stability. 1. Associativity: A Mobile Host (MH) periodically transmits beacons and updates associativity ticks. If a MH has low associativity ticks, it is supposed to be in a high state of mobility. Otherwise, it is supposed to be in a stable state, which is ideal point to perform routing. 2. Route Selection: A destination node selects a route based on the associativity ticks and hop distance. First, a route with the highest associativity ticks will be selected. If there are multiple routes with the same associativity ticks, the shortest route will be selected. Further, if even distances are the same, then one of the routes will be arbitrarily selected. ABR consists of two phases - Route Discovery Phase and Route Reconstruction Phase. 1. Route Discovery Phase: Initial phase where a route is established. 2. Route Reconstruction Phase: Maintenance phase where topological changes of the network are dealt with. In my opinion, this paper has the following strength and weakness. Strength. 1. Associativity. This paper characterizes the behavior of MHs, defines a new concept 'Associativity' and proposes a new routing algorithm based on that, which gives originality to this paper. 2. Adaptiveness and Scalability. ABR is on-demand and maintains only the information for the desire routes. And route maintenance algorithm allows locally reconstructing sub set of the route, instead of the entire route. So, I think, ABR is adaptive and scalable. Weakness. 1. Associativity ticks. ABR selects the route which has the highest associativity ticks. But, in my opinion, stability may not increase for ever as the associativity ticks increase. If the associativity ticks are too big, it means that a MH stayed at a location for a long time, so it is likely to move soon. I think, more study on the behavior of MHs can leads to a mapping from the associativity ticks to stability. From viran@csl.cornell.edu Tue Sep 18 03:10:08 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 f8I7A8q22877 for ; Tue, 18 Sep 2001 03:10:08 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8I7A2p43207 for ; Tue, 18 Sep 2001 03:10:02 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Tue, 18 Sep 2001 03:10:02 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 PAPER 10 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper introduces ABR, an on-demand routing protocol which uses the stability of neighboring nodes to determine the best route. The stability is determined using "associativity ticks" -- a count of "alive" messages from neighboring nodes greater than a set threshold (determined by the migration speed and transmission distance of the nodes) sets those nodes as active links, and not just a migratory node. Thus, as in TORA, the routes maintained may not be the shortest, but unlike TORA, multiple routes are not maintained. This paper was interesting in that a new metric was used to pick routes, and they actually did an experiment (albeit very simple) to study mobility traces of people occupied in real-world tasks. However, I'm not sure how extensible this protocol is for different varieties of mobile networks. It seems that it's designed for networks that have a few very stable nodes among more mobile nodes; thus the associativity ticks will be able to identify these almost base-station like nodes and route through them to reduce route rediscovery actions. I'm not sure if it will perform as satisfactorily in an environment where all the mobile nodes have high migratory patterns. From papadp@ece.cornell.edu Tue Sep 18 10:39:57 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8IEduq10666 for ; Tue, 18 Sep 2001 10:39:56 -0400 (EDT) Received: from mill (mill.ee.cornell.edu [128.84.236.64]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8IEdui28615; Tue, 18 Sep 2001 10:39:56 -0400 Date: Tue, 18 Sep 2001 10:33:06 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-Sender: papadp@mill.ee.cornell.edu To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 10 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "Associativity-Based Routing (ABR) For Ad Hoc Mobile Networks," by C-K. Toh. Panagiotis Papadimitratos papadp@ee.cornell.edu The distinctive feature of ABR, a uni-cast MANET routing protocol, is the use of 'associativity' as a primary metric in order to select more stable and thus long-lived routes. The reactive nature of the protocol and its neighbor discovery mechanism allow fast adaptation to topological changes, by prompt failure (link/path breakage) detection, route maintenance ('reconstruction'), and discarding of stale topology information. A feature of central importance (and, arguably, a disadvantage) of the presented here protocol is its reliance to the data-link layer protocol, and, in particular, the corresponding beaconing scheme that provides the means for the quantitative assessment of the association between two nodes. Each node beacons periodically in order to denote its existence and keeps track of beacons ('ticks') received from other nodes and updates its associativity table (spatial association). The reception of sufficiently many ticks (above some threshold value A_{thr}) allows the node to identify other immediate neighbors it is associated to. The degree of the association is proportional to the number of ticks (temporal association). Each node maintains values for its incident links and resets the table entry when a link failure is detected. During the route discovery process, each node appends ticks for all incident links to the propagating route request packet before re-broadcasting it to its own neighbors. Upon receipt of the query packet, the nodes extract any tick information but the one concerning the link to the upstream node. In that way, the request arrives to the destination carrying the stability information of all links along the traversed path. This information is used by the destination, which makes the route selection among several (possibly) received requests (i.e., accumulated routes). The one with the higher number of presumably stable links is chosen, and if more than one, the minimum-hop route. The route Reply is return to the source along the reverse of the chosen path and this sets the soft state at intermediate nodes, which mark the routes as valid and retain the corresponding route length and upstream and downstream nodes. Often mobility (among other factors) renders links unusable and topology changes are detected by the absence of beacon receptions. If a failing link is part of an active route, the detection can be performed independently of the data transmission. This makes the discarding of stale topology information possible for downstream links as well, in addition to the common propagation of a route error message to the source. Note that the topology information caching is implicit, and refers only to the active routes known to intermediate nodes; to that extent, ABR does not perform caching as DSR does for example. Accordingly, the protocol does not support multiple routes, that could be used, for example, as backup of a failing primary route. Upon a link failure, the upstream node that detects it (pivoting node) initiates a local query, with TTL (or, maximum number of hops to propagate) equal to the length of the now failed route segment to the destination. If this query fails, the protocol backtracks to the predecessor of the pivot, which repeats the same process, and this is repeated until the segment length exceeds the half of the initial route length. On the other hand, if the destination provides a reply to a local query, it returns the best partial route the pivot (which in turn can propagate the route change back to the source, although this is a rigid requirement). The same type of message used for discarding the active routes from intermediate nodes can be used by the source for a route deletion, which can be broadcasted in order to obliterate entries that the source is not aware of due to (partial) route reconstructions. The data forwarding is simplified (e.g., does not require source routing) since intermediate nodes store state information; the packet header contains only the next hop, which is updated en-route. Moreover, passive acknowledgments are used (with the exception of the last node that actively acks). ABR features such as the route reconstruction (RRC) appear to be efficient in theory, but the required evaluation is not provided in the clearest possible way. For example, not only the number of the local queries but also the aggregate imposed overhead should have been presented. Moreover, the RRC-resulting routes are sub-optimal and possibly less stable, with subsequent failures initiating new local queries. In short, the overlapping searches incur delays and could very well end up with backtracking to a broadcast query. All these aspects should have been further explored. On the other hand, the protocol (although it could be placed in a purely ad hoc context) is presented as an extension of an indoor wireless LAN. This reflects on the simulation set up, which resorts to the notion of a wireless cell in order to define the multihop connectivity, and, in general, limits the 'visibility' of the paper. In conclusion, the concept of route stability is highly relevant to the MANET context, and along with other ABR components, constitute an interesting case for an on-demand, reactive routing protocol that could achieve reduced control overhead. From gupta@CS.Cornell.EDU Tue Sep 18 10:41:14 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 f8IEfEq11092 for ; Tue, 18 Sep 2001 10:41:14 -0400 (EDT) From: Indranil Gupta Received: (from gupta@localhost) by ringding.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8IEfEr04043 for egs@cs.cornell.edu; Tue, 18 Sep 2001 10:41:14 -0400 (EDT) Message-Id: <200109181441.f8IEfEr04043@ringding.cs.cornell.edu> Subject: 615 PAPER 10 To: egs@CS.Cornell.EDU Date: Tue, 18 Sep 2001 10:41:14 -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------ Associativity-based routing for ad-hoc mobile networks, C.-K. Toh. Reviewer: Indranil Gupta The most novel contribution of this paper is the introduction of "stability" of a link as a metric for deciding good routes. The stability of a link is measured by the "associativity" between the end points. The algorithms in the paper use the neighbor beaconing from the MAC layer to define a high level of associativity between two nodes only if they have already exchanged more than a threshold number of beacons ("associativity ticks"). These algorithms also fit in well into an infrastructure with a few base stations, as a node will have better associativity with a nearby base station and will use it as a stable next hop. The routing algorithms presented in the paper are reactive, and give more preference to stability of a route than its "shortness" or delay. A node requiring a new route to a destination floods out a BQ (broadcast query) message that is propagated along by nodes after adding in associativity and other (delay) information about intermediate links - the destination decides the best route and sends back a reply to the sender. Node movements and link breakages in the upper half of the route are handled by sending a BQ to the destination from the node upstream of the failure - the destination replies back and a the route is repaired. A failure in the lower half of the route is handled by the node upstream of the failure sending a LQ (local query) to the destination with its old hop number (TTL) - the destination replies with a route only if there is an equal or shorter route than the old one. If the destination does not reply, the pivot node hands off the job to its immediate upstream node, which repeats the process (this could go all the way to the source). The algorithm also handles subnet bridging due to node movements, and concurrent node movements. Simulations performed in the paper reveal 1) increasing the degree of a node results in fewer localized queries (LQs) but also in a more sub-optimal route (in terms of length), and 2) routes remain fairly short. Comments: - The idea of using link associativity to obtain stable routes is the best contribution of this paper. The data presented in the paper (from the Active Badge System) is for associativity of users to a base station - this associativity is to be expected. The data provides no justification for using associativity ticks across *pairs* of nodes to decide the stability of a link between two nodes. - Associativity between two mobile nodes depends more on the interference in the area (percentage of beacons received), the relative speeds of the nodes, and the battery lives of the nodes. The paper, in its current form seems to be driven more by developing ad-hoc routing algorithms that will work well when there are base stations around. The performance of these algorithms can thus be improved significantly in an ad-hoc only network. - The policy decisions made in designing the route construction and repair algorithms in the paper are apparently arbitrary. For example, the authors do not seem to explain the significance of the half-way point along a route to change from a localized query to a broadcast query. Potentially, a large number of nodes might have moved and a large number of backtracks might be required to obtain a short route through a localized query - if the shortest route has indeed increased, it would be better to back off faster to the BQ or go with the (worse) route returned by the LQ - this decision could be made by feedback obtained about the localized queries. This is difficult in the current protocol as LQ messages are lost due to the TTL scheme; they could instead be made to reach the destination anyway, and the feedback used to tune the back off decision at the intermediary nodes. --------END------ From ranveer@CS.Cornell.EDU Tue Sep 18 12:09:11 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 f8IG9Bq21326 for ; Tue, 18 Sep 2001 12:09:11 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 10 Date: Tue, 18 Sep 2001 12:09:11 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 10 Thread-Index: AcFAXEC2QrQJQMrtS16biADC5aUnHw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f8IG9Bq21326 Associativity-based Routing for Ad-Hoc Mobile Networks This paper by C K Toh proposes an algorithm for another property desired of routing algorithms in ad hoc networks: route stability. The algorithm uses a measure of associativity ticks to determine the stability of a link. The network is assumed to be more or less stable, more like an office environment. Route decisions are made at the destination: the most stable route is chosen. The main contribution of this paper is the idea of associativity ticks for stability of routes. In fact in a subsequent paper, this idea is stretched further to mark nbrs in degrees of stability based on the number of associativity ticks received. This parameter of the 'degree of route stability' required is then specified by the source of the route. Based on this parameter the route discovery and maintenance takes place. Overall this is an interesting idea where the QoS features of routes are specified. ABR seems to be the only routing protocol that has included a measure of link load among the factors for choosing a route. ABR is a great protocol, but at the expense of more communication. Associativity ticks are extra beacons that waste battery power. Although a study by C K Toh reveals that beaconing does not affect battery life significantly, I still think that messages should be sent only when absolutely necessary. Besides, ABR works fine for more stable networks. It would not work as desired when there is more mobility in the network. From egs@CS.Cornell.EDU Tue Sep 18 13:06:11 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8IH6Bq27475 for ; Tue, 18 Sep 2001 13:06:11 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8IH6AH03496 for egs; Tue, 18 Sep 2001 13:06:10 -0400 (EDT) Date: Tue, 18 Sep 2001 13:06:10 -0400 (EDT) Message-Id: <200109181706.f8IH6AH03496@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: CS615 PAPER 10 >From ramasv@CS.Cornell.EDU Tue Sep 18 11:34:21 2001 >X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 >content-class: urn:content-classes:message >Subject: cs615 PAPER 10 >Date: Tue, 18 Sep 2001 11:34:21 -0400 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: cs615 PAPER 10 >Thread-Index: AcFAVxTlxaeJwKulEdWTbwCQJ5m7oA== >From: "Venu Ramasubramanian" >To: "Emin Gun Sirer" >X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8IFYLq16986 > >Associativity Based Routing For Ad Hoc Mobile Networks. > > This paper presents an on-demand routing protocol for mobile ad >hoc networks. The two main contributions of this paper include a method >(for the first time) to estimate the stability of a node and to detect >nodes moving in the present vicinity, and to use the stability and other >link metrics such as link capacity etc. to choose the routes. The >stability of the nodes is detected by periodic messages called >associativity ticks. > > The author of this paper claim based on an experiment that in >typical applications of ad hoc network, the nodes are mobile for short >periods of time but remaim stationary for long periods of time between >motion. This corresponds to the random waypoint mobility model used in >simulations. While this may not represent the mobility patterns for >all aplications, giving priority to stable nodes would work quite well >under this assumption. The route discovery phase of this protocol is >similar to AODV involving broadcast queries (BQ) and replies. Since the >protocol aims to select routes based on metrics other than distance >additional information is appended to the BQ as it propagates. > > Link breakages are detected wither by link level protocol or by >passive acknowledgements. Upon breakage of a routing link a local query >is initiated by the upstream node to find alternate routes. If a local >query fails to generate a reply the upstream node is intimated at it >starts the process all over again. Repeating partial recovery at each >upstream node looks very redundant and involves high control overhead. >Further, concurrent events could generate route loops. The paper argues >on a case by case basis that such a thing does not happen. But in real >systems, messages could get lost or delivered out of order and this may >cause route loops. I don;t believe that this protocol is loop free. > > The simulations presented in the paper appear to be >insufficicient. Standard metrics such as packet delivery, goodput, >latency etc... are not discussed. Results showing the effectiveness of >BQ and LQ are hard to understand. Further the simulator seems to >neglect path propagation and congestion effects and assumes perfect >medium. In sum, stability should be considered to be an important >metric while routing; this paper presents a way to detect stability. >However, other routing protocols enhanced to use stability information >might be more efficient that this. > From jcb35@cornell.edu Tue Sep 18 14:53:04 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 f8IIr4q10230 for ; Tue, 18 Sep 2001 14:53:04 -0400 (EDT) Received: from localhost.localdomain (syr-66-66-30-147.twcny.rr.com [66.66.30.147]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id OAA02760; Tue, 18 Sep 2001 14:52:50 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f8IIu3u02356; Tue, 18 Sep 2001 14:56:04 -0400 Date: Tue, 18 Sep 2001 14:56:03 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU cc: jcb35@cornell.edu Subject: 615 paper 10 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents associativity based routing, in which the protocol selects routes based on nodes being have states of "associativity" based on periods of non-movement. The goal is to establish routes that are stable (ie long-lived), and attain higher throughput. It is a reactive protocol, dealing with route requests on a per need basis. The paper claims that the protocol's associate property also allows fault tolerance in times of base station failures. Also, they claim the protocol is free from loops, deadlock, and packet duplicates. ABR uses a combination of point to point and broadcast routing approaches - routes are initiated by the source and set-up based on demand. ABR makes routing decisions at the destination, so that only the best route will be selective and made active to avoid packet duplicates. The "rule of associativity" that the paper discusses states that a mobile hosts' association with its neighbor changes as it is migrating and its movement period can be identified by association ticks which are transmitted on the data link protocol, where each host sends hello messages and updates its associativity ticks depending on the nodes it is surrounded by. By appending associativity tick numbers to route requests by intermediate nodes, the destination can select a route according to its knowledge of all the possible routes. Breaks in links and intermediate node movements are handled by passing new requests up to the source if the source of the break is in the lower half of the route and the destination if the break is in the upper half. Finally, the paper provided simulations which were not as detailed as some of the other papers we have read (well, at least they had simulations in this paper), and more information would have been nice, such as protocol overhead and such. The results seemed a little hard to read. comments: This protocol was interesting because it had data flow acknowledgment and re-transmission scheme incorporated in the protocol. This has its pros and cons, depending on what you're using it for and what protocols are on top of it. This protocol also seemed to be most effective for a very specific type of ad hoc network where nodes move for a short period of time but expeience a "dormant" period where they stay in the same area. The interesting thing is that this gives priority to nodes that are more stationary. From egs@CS.Cornell.EDU Wed Sep 19 14:26:12 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8JIQBq06762 for ; Wed, 19 Sep 2001 14:26:11 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8JIQBO12947 for egs; Wed, 19 Sep 2001 14:26:11 -0400 (EDT) Date: Wed, 19 Sep 2001 14:26:11 -0400 (EDT) Message-Id: <200109191826.f8JIQBO12947@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 10 >From eyh5@ee.cornell.edu Wed Sep 19 14:23:19 2001 Date: Wed, 19 Sep 2001 14:22:47 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: Summary of the ABR paper ------------------------------------------------- This paper presents a routing algorithm in which the selection of a suitable routh is based on the stability, or the associativity, of a route with respect to the nodes that comprise of the route. Unlikse many other routing algorithms for ad-hoc networks, this approach gives the destination node the authority to choose a suitable route for data transmission. In such a scenario, several routes may be available, some more stable (i.e., a higher degree of associativity) than the others The routing algorithm, executed at the destination node, will then choose the route with the best associativity. If more than one route has the same computed degree of associativity, the one that presents the minimal number of hops to the destination is chosen. It is clear that the ABR algorithm favors longevity of the route at the expense of added route acquisition overhead. The proposed associativity-based routing algorithm seems suitable for an ad hoc network that does not experience drastic topological changes. Indeed, this design philosophy is based on the author's belief that "in an ad-hoc mobile network, fast adaptability at the expense of excessive radio bandwidth consumption is undesirable." This may also justify the author's choice of a conference-room size environment for his simulations. ABR has a mechanism that is invoked when a link of the chosen route is severed. The Localized Query (LQ) is enabled to seek out an alternative partial route by the downstream pivoting node. This operation is possible because of the degree of associativity that is inherent in the chosen route. However, an issue that needs to be addressed here is a trade-off between the time-out period after which the pivoting node gives up searching for alternative partial node and the database of the upstream node of the broken link to queue the incoming packets from the source. One possible solution is to have the upstream node send a signal back to the source, temporarily halting the flow of the data packets until a certain amount of time has passed, after which the route is either re-established or a new route needs to be acquired. One disadvantage of the ABR is its excessive use of the bandwidth in a BW-limited ad-hoc mobile environment. On the other hand, ABR may be a good candidate when we bring QoS into ad-hoc networks. Because it introduces a sense of stability in choosing a route, that may be desirable for many multimedia-intensive applications. However, in that regard, the classical question remains: how to effectively trade off between time delay, bandwidth utilization, and the guaranteed QoS level. From mh97@cornell.edu Sun Sep 23 12:33:27 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 f8NGXRq11928 for ; Sun, 23 Sep 2001 12:33:27 -0400 (EDT) Received: from mars (syr-66-24-28-66.twcny.rr.com [66.24.28.66]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA23185 for ; Sun, 23 Sep 2001 12:33:21 -0400 (EDT) From: "ming hao" To: Subject: 615 PAPER 10 Date: Sun, 23 Sep 2001 12:32:56 -0400 Message-ID: <000001c1444d$68848390$6c01a8c0@mars> MIME-Version: 1.0 X-Security: MIME headers sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/procmail-security.html for details. $Revision: 1.129 $Date: 2001-04-14 20:20:43-07 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_0001_01C1442B.E1746A30" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2616 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 This is a multi-part message in MIME format. ------=_NextPart_000_0001_01C1442B.E1746A30 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Associativity-Based Routing for Ad-Hoc Mobile Networks by C-K. Toh this paper claims that in some cases, the mobile nodes shows stability to some degree. they usually stay on on place for a while before moving to another place. the new algorithm in the paper take advantage of this property and selects the route with higher stability so that reducing the chances of route re-construction. the algorithm includes 1. route discovery. it consists query-reply cycle. source initiates the query sends associtivity info in the query packet. at last, the destination node selects a best route and sends it back. the criteria for selecting route is based on in the order of priority, associtivity, length o froute and link status. 2. maintainance: in the case of src movement, RN is sends to invalidate all donw-stream nodes and new route discovery is initiated. if dest moves, its immediate up-stream node will perform LQ and connect the host. if fail, it sends RM[0] to its up-stream node to do LQ till it reaches src. if IN moves, it dwon-stream node sends RN[1] in the down direction to invalidate the route. while its immediate up-stream node tries to do LQ to re-construct the route. there are two things about route construction which may deserve to mention. a. the algorithm only minatains one route. but from the point of probability, it is more possible for a long route to break than a shorter one. so if the route is long, maybe it is more desirable to have multiple routes. b. considering this scenairo, the dest node moves far away. pivoting nodes keep trying LQ and backtrack. it may be more efficient to let source to do route discovery again. c. the loop free property stems from the fact that the route discovery packe has a unique sequence number. nodes will discard the packet with same sequence number. in the case of route maintainence and LQ, i think the upperstream nodes simply donot participate into the operation to avoid loop. but this has side effect because that eliminate the possible optimization that some upper stream nodes are closer to the destination. i am not very satisfied with the simulation because the paper lacks the result showing how considering associtivity helps better performance of the network; how associtivity affects the performance; to what degree the new algorithm increases performance in comparison to old algorithms. all these questions are not answered. only analysis is given in the term of performance comparison. summary: the main contribution of the paper is considering the associativity of the nodes so that route's longevity plays a important role. as for the other sides, i think this algorithm is similar to AODV. it exposes a reseach direction that taking advantage of specific features of ad hoc network helps to increase the erformance of network. btw, this paper is too long. do not know if it is good or bad. at least it increases the workload of cs615:) -ming ------=_NextPart_000_0001_01C1442B.E1746A30 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable -->

Associativity<= /span>-Based Routing for Ad-Hoc Mobile = Networks

by C-K. = Toh

 

this paper claims that in some cases, the mobile nodes = shows

stability to some degree. they usually stay on on place for

a while = before moving to another place. the new algorithm in = the

paper take advantage of this property and selects the route = with

higher<= font size=3D2 face=3DArial> stability so that reducing the chances of route = re-construction.

 

the algorithm includes

1. route discovery. it consists query-reply cycle. source initiates the

   = query sends associtivity info in the query packet. = at last, the = destination

   = node selects a best route and sends it back. the = criteria for selecting

   = route is  based on in the order = of priority, associtivity, length o froute

   = and link status.

 

2. maintainance: in the case of src movement, RN is sends to invalidate

   = all donw-stream nodes and new route discovery is initiated. if dest moves,

   = its immediate up-stream node will perform LQ and connect the host. if fail,

   = it sends RM[0] to its up-stream node to do LQ till it reaches src. if IN moves,

   = it dwon-stream node sends RN[1] in the down = direction to invalidate the route.

   = while its immediate up-stream node tries to do LQ to re-construct the = route.

 

there are two things about route construction which may deserve to mention. a.

the algorithm only minatains one route. but from the point of probability, it is

more possible for a long route to break than  = a shorter one. so if the route is =

long, maybe it is more desirable to have multiple  routes.

 

b. = considering this scenairo, the dest = node moves far away. pivoting

nodes keep trying LQ and backtrack. it may be more efficient = to

let source to do route discovery again.

 

c. the = loop free property stems from the fact that the route discovery packe

has a unique sequence number. nodes will discard the = packet with same

sequence number. in the case of route maintainence and LQ, i think =

the upperstream nodes simply donot participate into the operation

to avoid = loop. but this has side effect because that eliminate = the

possible optimization that some upper stream nodes are closer to the =

destination. =

 

i am not very satisfied with the simulation  = because the paper lacks the result showing

how  considering associtivity helps better performance of the network; how associtivity 

affects= the performance; to what degree the new algorithm increases performance in =

comparison to old algorithms. all these questions are not = answered. only analysis is given =

in the = term of performance comparison.

 

summary= : the main contribution of the paper is considering the associativity

of the = nodes so that route's longevity plays a important role. as = for the

other sides, i think this algorithm is similar to AODV. it exposes a reseach = direction

that taking advantage of specific features of ad hoc network helps to increase the =

erformance of network.

 

 

btw, this paper is too long. do not know if it is good or = bad. at least it

increases the workload of cs615:)

 

-ming

------=_NextPart_000_0001_01C1442B.E1746A30-- From eyh5@ee.cornell.edu Mon Sep 24 16:31:54 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8OKVrq24505 for ; Mon, 24 Sep 2001 16:31:53 -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 f8OKVq612420 for ; Mon, 24 Sep 2001 16:31:52 -0400 Date: Mon, 24 Sep 2001 16:30:49 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 10 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Associativity-Based Routing Protocol for Ad-Hoc Mobile Networks This paper presents a routing algorithm in which the selection of a suitable routh is based on the stability, or the associativity, of a route with respect to the nodes that comprise of the route. Unlikse many other routing algorithms for ad-hoc networks, this approach gives the destination node the authority to choose a suitable route for data transmission. In such a scenario, several routes may be available, some more stable (i.e., a higher degree of associativity) than the others The routing algorithm, executed at the destination node, will then choose the route with the best associativity. If more than one route has the same computed degree of associativity, the one that presents the minimal number of hops to the destination is chosen. It is clear that the ABR algorithm favors longevity of the route at the expense of added route acquisition overhead. The proposed associativity-based routing algorithm seems suitable for an ad hoc network that does not experience drastic topological changes. Indeed, this design philosophy is based on the author's belief that "in an ad-hoc mobile network, fast adaptability at the expense of excessive radio bandwidth consumption is undesirable." This may also justify the author's choice of a conference-room size environment for his simulations. ABR has a mechanism that is invoked when a link of the chosen route is severed. The Localized Query (LQ) is enabled to seek out an alternative partial route by the downstream pivoting node. This operation is possible because of the degree of associativity that is inherent in the chosen route. However, an issue that needs to be addressed here is a trade-off between the time-out period after which the pivoting node gives up searching for alternative partial node and the database of the upstream node of the broken link to queue the incoming packets from the source. One possible solution is to have the upstream node send a signal back to the source, temporarily halting the flow of the data packets until a certain amount of time has passed, after which the route is either re-established or a new route needs to be acquired. One disadvantage of the ABR is its excessive use of the bandwidth in a BW-limited ad-hoc mobile environment. On the other hand, ABR may be a good candidate when we bring QoS into ad-hoc networks. Because it introduces a sense of stability in choosing a route, that may be desirable for many multimedia-intensive applications. However, in that regard, the classical question remains: how to effectively trade off between time delay, bandwidth utilization, and the guaranteed QoS level. From wbell@CS.Cornell.EDU Tue Sep 25 02:50:55 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 f8P6otq24802 for ; Tue, 25 Sep 2001 02:50:55 -0400 (EDT) Received: from [10.1.1.101] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id CAA09746 for ; Tue, 25 Sep 2001 02:50:53 -0400 (EDT) Subject: 615 PAPER #10 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Evolution-Format: text/plain X-Mailer: Evolution/0.13.99+cvs.2001.09.21.20.26 (Preview Release) Date: 25 Sep 2001 02:50:29 -0400 Message-Id: <1001400653.11333.14.camel@brute> Mime-Version: 1.0 10) Associativity-Based Routing for Ad-Hoc Mobile Networks In this paper, they author motivates that Ad-Hoc networks do not have hosts which move about randomly, and presents the idea that hosts undergo a period of stability between movements, and that said stability tends to last for a decent period of time. From this idea, they've created ABR (Associativity-Based Routing) which finds routing paths are selected by their likelihood of being long-lived and therefore more stable. By choosing paths that are unlikely to be broken, ABR lowers the amount of communication bandwidth used to repair routes that are broken by having less broken routes. Routes are found on demand like algorithms such as DSR, but unlike DSR all routes are computed from a source to a destination, and the destination picks a single route which is most likely to be long-lived based on the associtativity count of the hosts [A measure of how long a link between nodes has been active.] From there routes are repaired at breakpoints via LQ local queries which attempt to repair the route. If a repair is not possible at the breakpoint, the LQ's bubble backwards towards the sender, trying to repair the route at each step. For local problems in the network, this scheme repairs routes cheaply, but it is easy to construct cases where this approach is very resource inefficient. They do an extensive performance evaluation using simulations to demonstrate the effectiveness of ABR, but tend to overwhelm the reader with details. It was difficult to pick out the important numbers from the large volume of data in the 7 pages of results. A more concise results section would have been more useful. I thought the insight of finding long lived routes not only made sense but matches my ideas on how Ad-Hoc networks are used. Although there are some subset of nodes that are constantly in motion, most nodes are stable for some period of time, and those are the nodes that should be chosen for routing paths, as they are likely to remain stable. From c.tavoularis@utoronto.ca Tue Sep 25 11:29:27 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 f8PFTQq18410 for ; Tue, 25 Sep 2001 11:29:27 -0400 (EDT) Received: from webmail2.ns.utoronto.ca ([128.100.132.25] EHLO webmail2.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 64123]) by bureau6.utcc.utoronto.ca with ESMTP id <238382-3997>; Tue, 25 Sep 2001 11:29:16 -0400 Received: by webmail2.ns.utoronto.ca id <24410-13842>; Tue, 25 Sep 2001 11:28:55 -0400 To: COM S 615 Subject: 615 PAPER 10 Message-ID: <1001431728.3bb0a2b0e7d68@webmail.utoronto.ca> Date: Tue, 25 Sep 2001 11:28:48 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 ABR (Associativity-Based Routing) is a simple straightforward on-demand protocol that attempts to make use of stability in ad hoc routing. ABR employs the unique concept of associativity to determine the amount of stability in routes. It is measured in terms of the number of ticks, or beacons, successfully exchanged between neighbors. The longer a pair of nodes are co- reachable, the higher the number of ticks. If a node and its neighbor move out of each other’s reach, their common node ticks are reset indicating movement or instability. ABR uses broadcast and point-to-point routing to reactively construct, and reconstruct routes. A source node initiates a broadcast query (BQ), which is propagated through all possible routes to the destination (DEST). DEST chooses a single route based on highest associativity (and shortest route if there is a tie), and forwards a REPLY along that route. Each node keeps track of its neighbors and hop counts to the source and destination. The Route Re- construction (RRC) Phase is invoked when an existing route changes. Nodes that lose a link along a path become pivoting nodes. A downstream pivoting node will send Route Notifications (RN) downstream to remove invalid routes. An upstream pivoting node will initiate a Localized Query (LQ), by broadcasting messages, to try to partially rebuild the path from itself. It will only select a new route that is shorter or equal to the previous route. If no suitable partial path to DEST is found before an LQ_TIMEOUT, the path will backtrack upstream and repeat LQ until the pivoting node is ½ the number of hops of the original path. At that point, it will send RNs upstream to erase the entire route and the source starts a new BQ. This algorithm is particularly efficient in dense node populations, where partial routes are easier to find, and therefore reduces re-construction time and avoids the maintenance of multiple routes. It may not perform as well in sparse environments. As an on-demand protocol, ABR requires nodes to maintain a moderate amount of information (single path to node without maintaining entire path in each node), and forwarding of routing packets is also moderate since periodic broadcasts are not required. Therefore, it is fair to say that ABR has the potential to perform well in large-scale networks, but this issue is not addressed in this paper. An interesting study would be to simulate ABR in high population networks. In addition, it is not clear how ABR will react when a network partition occurs. ABR applies well to BS-oriented WLANs, as it can exploit the stability of existing base stations, and provide recovery from BS failure. The associativity measure may not be as successful in mobile ad hoc networks. The rule of associativity states that after instability, or node migration, a node will be stable for some time. In ABR, the application of this rule is modified, and is used such that the longer a node has been stable within a group of neighbors, the more likely it will continue to be stable. Therefore it is not a direct application of the rule, nor is it guaranteed to select the most stable routes, since a node that was moving could suddenly become stable, and vice versa. To improve selection of stable routes, ABR can consider node speed in addition to associativity states. From teifel@csl.cornell.edu Tue Sep 25 11:31:11 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 f8PFVAq18492 for ; Tue, 25 Sep 2001 11:31:10 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8PFV5T20243 for ; Tue, 25 Sep 2001 11:31:05 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 25 Sep 2001 11:31:05 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 10 Message-ID: <20010925112930.U4769-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ABR: This paper presents a new routing protocol, Associative-Based Routing (ABR), that is in between broadcast and point-to-point routing. ABR does not attempt to maintain current route information at every node. Routing decisions are made at the DEST and only one route is used, while other routes remain open for other communication. Routing choices are based on the associativity property--a MH's association with its neighbors will change when it is migrating and be stable when the MH is dormant. The best route is composed of all (ideally) nodes with high associativity (dormant nodes), based on the assumption that this route will likely be longer lived than routes composed with low associativity (migrating nodes). This is one of the first papers that we have read that gives actual data from a sample distributed system (Active Badge System), which the authors believe that for practical mobile users, some dormant time will be spent before migration. Interestingly, ABR can be applied to BS-oriented WLANS to improve robustness when BS failures occur. In addition to conventional metrics (recovery time, minimum hop, propagation delay, loop avoidance, & link capacity) this author introduces longevity of a route, relaying load of INs supporting existing routes, and knowledge of link capacities of the selected route. Their target model is migration based, laptops or PDAs inside of buildings. The simulation appears to be on par with the other simulation environments we have seen in the other papers. Figures even have statistical confidence intervals! This paper was very extensive in its background information and discussions, and the analysis was good. The biggest complaint that this paper was perhaps too extensive--i.e. if every paper in this field was 40 pages (or 20 double column) it would be ridiculous. From samar@ece.cornell.edu Tue Sep 25 11:42:48 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8PFgmq19586 for ; Tue, 25 Sep 2001 11:42:48 -0400 (EDT) Received: from mill (mill.ee.cornell.edu [128.84.236.64]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8PFgl601646 for ; Tue, 25 Sep 2001 11:42:47 -0400 Date: Tue, 25 Sep 2001 11:35:14 -0400 (EDT) From: Prince Samar X-Sender: samar@mill.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 10 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=X-UNKNOWN Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by sundial.cs.cornell.edu id f8PFgmq19586 10) Associativity-Based Routing for Ad hoc Mobile networks. This paper presents a novel approach to routing in "conference" sized mobile ad hoc networks with a goal of maximizing the route lifetime. The protocol is on-demand and is claimed to be free from loops, deadlocks and packet duplicates and has scalable memory requirements. The protocol uses the associativity property to exploit the spatial and temporal relationships of the network in order to construct long-lived routes which would further require less maintenance and thus higher throughput. Each node maintains a Neighboring Table (NT) which contains information about the stability of the node's links with its neighbors in the form of Associativity 'ticks'. Each node transmits beacons at regular interval, updating the tick-count of its neighbors as well as the link quality. When a route is needed by the source, it initiates a route query by flooding the network with the BQ packets. These BQ packets accumulate the route, associativity ticks and route relaying load as they travel through the network. Eventually, a few of these BQ control packets reach the destination. The destination then decided on the best route depending on the information on route stability and congestion as gathered in the BQ packet. The best route is chosen and a REPLY sent back, while the rest of the found routes simply time-out and expire. The Route Re-Construction (RRC) phase tries to maintain routes in case a link in the route to the destination breaks. For this, depending on whether the node that has moved away lies in the Upper Arm or the Lower Arm of the Intermediate Nodes, a limited local query is initiated. The author also introduces a Dynamic Cell Size Adjustment Scheme (DCSAS) which changes the transmission power of a node if it in a congested environment. DCSAS tries to reduce the transmission range to exclude inactive neighbors but include all currently active neighbors. Comments: - This paper introduces the new and interesting concept of property of associativity between nodes in an ad hoc network. The protocol strives to select the route with the best known stability by measuring the associativity ticks of each of the intermediate nodes. However use of this property is totally dependent on the mobility pattern of the nodes in the network. It is implicitly assumed that there would always be enough "stationary" nodes so that a stable route to the destination can be found. In a highly mobile network with few resting nodes, the protocol may not provide any benefit at all. - In order to justify his claims about dormant nodes in the network, the author provides data about 52 badge wearers in a "computer laboratory". But the real scenarios where ad hoc networks may actually be deployed could be very much different (much more mobile and restless) than a laboratory where a person comes just to spend some time staring at a computer monitor. - If the destination has moved only one more hop away from its current upstream node, a lot of control traffic may be wasted as the protocol conservatively tries to obtain a shorter or equal-length route to the destination. As the RRQ backtracks, a lot of "area" of the network that has already been "covered" by the previous LQs is queried again, resulting in wastage of resources. Also the choice of half-way node to switch from a LQ to a BQ has not been explained. - The simulation results do give insights into the working of the protocol, but still a lot is missing. The paper contains only migration based results which are good for ¨stress-testing" the protocol, but does not consider random, real-like cases. The number of nodes are less (30) and no results about the amount of control traffic generated are presented. - The passive acknowledgment scheme would work only in a single, broadcast channel environment. - The protocol concentrates on providing a single "good" path. Hence it cannot support multi-path routing.