IETF MANET Working Group C.-K. Toh INTERNET DRAFT School of Electrical & Computer Engg Georgia Institute of Technology March 1999 "Long-lived Ad Hoc Routing based on the Concept of Associativity" Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and will only exist as an Internet-Draft. Please see "patent information" provided in Section 11 of this draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This document describes the associativity-based long-lived routing (ABR) protocol for ad hoc mobile networks. It is a simple and bandwidth-efficient distributed routing protocols which does not attempt to consistently maintain routing information in every node. In an ad hoc wireless network where mobile hosts are acting as routers and where routes are made inconsistent by mobile hosts' movement, we propose an Associativity-based routing scheme where a route is selected based on nodes having associativity states that imply periods of spatial, temporal, connection and signal stability. In this manner, the routes selected are likely to be long-lived and hence there is no need to restart frequently, resulting in higher attainable throughput. Our proposed protocol is based on source-initiated on-demand routing. Route requests are broadcast on a per-need basis. To discover shorten the route discovery time when the association property is violated, the localized- query and quick-abort mechanisms are respectively incorporated into the protocol. The association property also allows the integration of ad hoc routing into a base station oriented wireless LAN environment, providing the fault tolerance in times of base station failures. This draft will describe the protocol functions and information about packet headers and routing tables. ----------------------------------------------------------------- Table of Contents ----------------------------------------------------------------- Abstract 1. Introduction 2. Property of Associativity 3. ABR Terminology 4. ABR Protocol Overview 5. Packet Formats 5.1 BQ Control Packet 5.2 REPLY Control Packet 5.3 RN Control Packet 5.4 LQ Control Packet 5.5 RD Control Packet 5.6 Data Packet Format 6. ABR Routing Metrics & Tables 6.1 New Routing Metrics 6.2 ABR Routing Table 6.3 ABR Neighboring Table 6.4 Control Packet Seen Table 7. ABR Protocol Description 7.1 Route Discovery Phase 7.2 Route Reconstruction Phase 7.3 Route Deletion Phase 8. Acknowledgements & Retransmission 8.1 Data Flow Acknowledgement 8.2 Packet Retransmission 9. Other Issues 9.1 Battery Life 9.2 Asymmetric Wireless Link 9.3 Route Caching 9.4 Multicasting 10. References ----------------------------------------------------------------- 1. Introduction The Associativity-Based Long-lived Routing (ABR) protocol is designed for ad hoc wireless networks where mobile computers act as routers and packet forwarders in a wireless environment with no base stations. ABR protocol allows networks to be formed and deformed quickly, without users' intervention and without the need for fixed network infrastructures. Unlike some existing link-state and distance vector-based approaches, ABR does not attempt to consistently maintain routing information in every node. ABR is a source-initiated on-demand routing protocol and it is based on the concept of longevity of a route. A route is said to be long lived if it remains valid over time and that the nodes in the route does not constantly migrate outside the connectivity range of its immediate upstream and downstream neighbors in the route. Longevity of a route is indicated by associativity and it defines the spatial, temporal, connection and signal stability of mobile hosts. ABR is a compromise between broadcast and point-to-point routing and it uses the connection-oriented packet forwarding approach. ABR only maintains routes for sources that actually desire routes. Routing decisions are performed at the destination mobile host (MH) and only the best route will be selected (based on QoS requirements) and used while all other possible routes remain passive, therefore avoiding packet duplicates. The following sections shall explain the concept of associativity and the principles behind ABR protocol. 2. Property of Associativity. The rule of Associativity states that a MH's association with its neighbor changes as it is migrating and its transiting period can be identified by the associativity 'ticks'. The migration is such that after this unstable period, there exists a period of stability, where the MH will spend some dormant time (this does not imply that the MH is not moving) within a wireless cell before it starts to move outside the connectivity range of its neighbors. Associativity ticks are updated by the MH's data-link layer protocol. A MH periodically broadcasts beacons identifying itself and constantly updates its associativity ticks in accordance with other MHs sighted in its neighborhood. A MH is said to exhibit a high state of mobility when it has low associativity ticks with its neighbours. However, if high associativity ticks are observed, the MH is in the stable state and this is the ideal point to select the MH to perform ad-hoc routing. Consequently, if all the MHs in a route have high associativity ticks, an inter-dependent phenomenon arises where 'my' degree of associativity ticks will be high if 'you' do not move out of reachability and are in stable state. The associativity threshold used to distinguish association stability and instability is a function of the beaconing interval, mobile host's migration speed and the size of the wireless cell. Associativity ticks are reset when the neighbors or the MH itself moves out of proximity, not when the communication session is completed and the route made invalid. ABR associativity ticks are not reset immediately if a node fails to receive a beacon from a neighboring node. If the beacon is not received after 'N' times the beaconing interval, then a decision is made that the property of association stability is violated. The choice of this 'N' value is therefore critical. A smaller N may improve sensitivity but may result in a false alarm while a bigger N may lengthen the response time to link failures/changes. 3. ABR Terminology We will use some words which has some specific meaning in context of ABR. ABR Associativity Based long-lived Routing using the principle of associativity. MH Mobile host. SRC Mobile host which desires a route. DEST Mobile host to which information sent by SRC will be received. IN Intermediate nodes between SRC and DEST. BQ Broadcast query packet used by SRC when it requires a new route. REPLY This message is sent by the DEST node in response to a BQ. SEQ No. It is used to uniquely to identify each BQ packet, so that no BQ packet will be broadcast more than once. LQ Localized Query control packet which is used during route reconstruction. RRC Route Reconstruction Phase. RN Route Notification control packet. RD Route Deletion control packet. 4. ABR Protocol Overview The ABR protocol consists of three phases, which include ways how new routes should be created whenever old routes are changed. These phases are: (a) Route Discovery Phase, (b) Route Reconstruction (RRC) Phase, and (c) Route Deletion Phase. Initially, when a SRC node desires a route, the route discovery phase is invoked. When a link of an established route changes due to movement of any node, the RRC phase is invoked. When the source no longer desires the route, the route deletion phase is initiated. The route discovery phase consists of a `broadcast query (BQ)' and an `await reply' (REPLY) cycle. When a SRC node requires a route, it will send a BQ control packet and will wait for a REPLY from the DEST node. The DEST node selects the best route among all possible routes discovered and replys back to the SRC node. The RRC phase uses a localized query (LQ) approach to discover partial routes and route notification (RN) control packets to erase unwanted routes. The Route Deletion phase will be used when a SRC node no longer requires a route, and it consists of a route delete (RD) broadcast from the SRC node so that all the intermediate nodes will then remove the specific path entry from their routing tables. 5. Packets Formats 5.1 BQ Control Packet This packet is used during the route discovery phase and is sent by the SRC node. It is not a fixed length packet and its length varies as it transits from one mobile node to another towards the DEST. The various fields contained in this packet are: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |TYPE | SRC ID | DEST ID | LIVE | INa ID| Route qualities |... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ INb ID| Route qualities | INn ID | route qualities | SEQ NO|.. -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / \ +-+-+-+ / \ ...| CRC | / \ +-+-+-+ / \ / \ / \ / \ / \ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor's address: Corresponding associativity Ticks, Route| | Relaying Load, Forwarding Delay. | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The following explains the purpose of the individual fields: TYPE --- This indicates which control packet is sent. SRC-ID --- This indicates the source node IP address. DEST-ID --- This indicates the destination where the packet should be received. LIVE --- Each IN will keep on increasing this hop-count value, so it reveals how many hops are between the SRC and DEST nodes. INx --- Intermediate nodes IP addresses. SEQ NO --- Sequence number. A numerical number used to prevent duplication of BQ packets. CRC --- Cyclic Redundancy Check. 5.2 REPLY Control Packet This packet is used during the route discovery phase and is sent by the DEST node in response to the BQ control packet. It is not a fixed length packet and its size depends on the number of nodes in the route selected. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |TYPE| SRC ID | DEST ID | INa ID | INb ID | ......| INn ID |.... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ .... | summary of route qualities | CRC | +-+-+-+-+-+-+-+-+-+-++--+-+-+-+-+-+-+ / \ / \ / \ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Aggregate degree of| route length | Aggregate Route |....... | Stability | | Relaying Load | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+ .....| Cumulative Forwarding | | Delay | +-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.3 RN Control Packet This route notification (RN) packet is invoked during the route reconstruction phase and is sent by an immediate neighboring node that has detected a link failure due to a node moving away. Its packet length is fixed and it has the following format: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TYPE | ORG ID | SRC ID | DEST ID | SEQ NO | STEP | DIR | CRC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The meaning of each field is explained below: ORG ID --- This refers to the pivoting node ID, and will be explained later. STEP --- This 1-bit flag could take two values: STEP=0 implies that `backtracking' process is performed one hop at a time, towards the SRC. STEP=1 implies that the RN packet will be propagated straight back to the SRC node. DIR --- This one-bit flag is used to indicate in which direction the RN control packet is propagating (i.e., towards the SRC or DEST). 5.4 LQ Control Packet This Localized Query (LQ) packet is initiated by the upstream neighbor of the node which has moved away and has invalidated the discovered and selected route. This packet is therefore used during the route reconstruction phase. The main purpose of the LQ process is to quickly locate alternate partial routes without resorting to a full route reconstruction by the SRC node. Hence, the LQ process localizes mobility to regions close to the origin of mobility. Note that the new partial route is also selected based on associativity, so that this route is likely to be long- lived. The LQ control packet has a format shown below: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TYPE | SRC ID | DEST ID | LIVE | INa ID |route qualities |... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+ INb ID |route qualities|........ +-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ .....| INn ID| route qualities | SEQ NO | CRC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / \ / \ / \ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor's address: Corresponding associativity Ticks, Route| | Relaying Load, Forwarding Delay | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.5 RD Control Packet ABR employs both soft and hard state for deleting unwanted routes. The hard state approach involves sending an explicit Route Delete (RD) control packet via broadcast. Localized broadcast cannot be used here since the route length can change over time and the SRC node may not necessarily be aware about the new route length after one or more RRCs. The soft state approach, however, monitors traffic activity and if no traffic related to an active route is obseverd over a threshold level, the route is automatically expired and is deleted from the route entry. The format for RD control packet is illustrated below: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TYPE | SRC ID | DEST ID | LIVE | SEQ NO | CRC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Note that meaning of each field is similar to those explained earlier. 5.6 Data Packet Format Since a long packet header results in low channel utilization efficiency, in ABR, each data packet will only contain the neighboring node routing information, not all nodes in the route. Each IN will renew the next-hop information contained in the header before propagating the packet upstream or downstream. The purpose of the individual fields of the packet header is summarised below: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SRC ID | DEST ID | SEQ NO | Service Type| LAST IN |.... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ..... | CURRENT IN | CRC | Data | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ SRC ID --- Used to support packet forwarding. DEST ID --- Used for route identification. SEQ No. --- Packet duplicates prevention and uniqueness. Service Type --- Allow specification of packet priority. LAST IN --- Passive packet acknowledgement. NEXT IN --- Packet duplicates prevention and routing. CURRENT IN --- Acknowledgement and routing. 6. ABR Routing Metrics & Tables 6.1 New Routing Metrics Conventional routing qualities are characterized by: (a) fast adaptability to link changes, (b) minimum-hop path to destination (c) end-to-end delay (d) loop avoidance (e) link capacity. However, fast adaptability to changes in network topology is not necessarily a plus. It often results in an excessive radio bandwidth consumption due to excessive broadcast. ABR uses the following new routing metrics: a. Longevity of a route, b. Relaying load of INs supporting existing routes, c. Knowledge of link capacities of the selected route. The longevity of a route is important as the merits of a shorter-hop but short-lived route will be denigrated due to frequent data flow interruptions and the need for RRCs. In addition, fair relaying load distribution is important in an ad hoc mobile network since no one particular MH should be unfairly burdened to support many ad hoc routes and to perform many packet relaying functions. This also alleviates the possibility of network congestion. Finally, since the associativity of a MH with its neighbors also reflects the number of contenders within a wireless cell, the approximate aggregated throughput for the selected route can be made known to the mobile user prior to transmission. This therefore allows the user to either proceed with or abort the transmission. 6.2 ABR Routing Table +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Dest Node | SRC node | Incoming node | Outgoing node | Hop| |Address | Address | Address | Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Na | Nx | Nz | Nj | 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | Nk | Ny | Ni | No | 3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Total no. of active routes supported (Relay Load) | 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The routing table of a node supporting existing routes is shown in the table above. The table reveals that every node supporting on-going routes will map incoming packets from a particular upstream node to the corresponding out-going downstream node. Every node will also keep track of its distance (hop count) to the DEST and a record of the total routes that it is currently supporting. 6.3 ABR Neighboring Table The neighboring table is usually updated by the data link layer protocol, which will generate, receive and interpret beacons from the neighboring MHs or BSs and pass this information up to the higher protocol layers. Nomadic collaborative applications can then utilize the neighboring table information to update their participants' present and absent lists. The structure of a neighboring table is shown below. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Neighbors | Associativity Ticks |Forwarding Delay (ms)| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Na | 5 | 40 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Nb | 15 | 25 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6.4. Control Packet 'Seen' Table While the BQ query process is activated via a radio broadcast, the LQ query process is invoked via a local broadcast. To avoid MHs from processing and relaying the same BQ, RD or LQ packet twice, BQ, RD and LQ 'seen' tables are needed. If the received control packet type, route identifier and sequence number match an entry in the seen table list, then the packet is discarded. The contents of these seen tables will be erased after a certain time-out period. This time-out period must be long enough to allow a MH's neighbors to forward the control packet (BQ, RD or LQ) to their corresponding neighbors. On the other hand, because the REPLY and RN control packets utilize 'directed' broadcast, `seen' tables for these packets are not necessary. 7. ABR Protocol Description The ABR protocol consists of three phases, a. Route Discovery Phase, b. Route Reconstruction (RRC) Phase, c. Route Deletion Phase. Initially, when a source node desires a route, the route discovery phase is invoked. When a link of established route changes due to SRC, DEST, INs or subnet-bridging MH's migration, the RRC phase is invoked. When the source no longer desires the route, the route deletion phase is initiated. 7.1 Route Discovery Phase The route discovery phase allows an approximation of the data throughput associated with the selected route to be computed. This is achieved through the knowledge of associativity ticks of neighbors in the route and the relaying load of nodes of supporting the route. The route discovery phase consists of a this is elaborated below. Initially, all nodes except those of the DEST's neighbor have no routes to the DEST. A node desiring a route to the DEST broadcast a BQ message, which is propagated throughout the ad- hoc mobile network in search of MHs which have a route to the DEST. Once the BQ query has been broadcast by the SRC, all INs that receive the query will check if it has previously processed the packet. If affirmative, the query packet will be discarded, otherwise the node will check if it is the DEST. If it is not the DEST, the IN appends its MH address/identifier at the IN Ids field of the query packet and broadcasts it to its neighbors (if it has any). The associativity ticks with its neighbor will also be appended, along with the route relaying load and forwarding delay. The next succeeding IN will then erase its upstream node's neighbors' associativity ticks entries and retain only those concerned with itself and its upstream node. In this manner, the query packet reaching the DEST will only contain the intermediate MH's address and their associativity ticks. So after some time DEST will know all the possible routes and their qualities. It can then select the best route and send a REPLY packet back to the SRC, via the selected route. This causes the INs in the route to mark their routes to DEST as valid and this means all other possible routes will be inactive and will not relay packets destined for the DEST.When the REPLY packet reaches the SRC, the route is established. 7.1.1 ABR Route Selection Rules & QoS ABR route selection is performed at the DEST node. After a SRC node generates the BQ, the DEST node will at a later point in time receives information about all possible routes. It then selects the best route and informs the nodes in the route and the SRC about this selected route. Nodes in the route will therefore have their route entry 'set to be active' by the REPLY packet. Given a set of possible routes from the SRC to the DEST node, if a route consists of MHs having high associativity ticks (therefore indicating high connection stability), then that route will be chosen by the DEST, despite other shorter-hop routes. However, if the overall degrees of association stability of two or more routes are the same, then the route with the minimum hops will be chosen. If multiple routes have the same minimum-hop count, then the route with the least cumulative forwarding delay is selected. In ABR, there exists flexibility in terms of route selection based on which QoS parameter is viewed to be more important than others. High association stability is chosen to be the most important factor to be considered first since it determines how long the other QoS paramters can be maintained before the route is invalidated by MHs' movements. 7.2 Route Reconstruction Phase In the ABR protocol, the selected route is more likely to be long-lived due to the property of associativity. However,if unexpected moves by MHs do occur, the RRC procedure will attempt to quickly locate an alternate valid route without resorting to broadcast query unless necessary. The RRC phase requires the use of localized query (LQ) and route notification (RN) control packets. The route maintenance phase of the ABR protocol performs the following operations: a. Partial Route Discovery, b. Invalid Route Erasure, c. Valid Route Update, d. New Route Discovery (Worst case). The route reconstruction phase will take into account movements by SRC, DEST, INs and concurrent nodes. It is important to realize that concurrent node movements do occur and ultimately, there should only be one RRC that will eventually succeed unless the network is partitioned. 7.2.1. SRC Node Movements This will invoke a BQ_REPLY process, in order to derive a new route. ABR is a source-initiated on-demand routing protocol. So long as SRC node's movement does not result in loosing connectivity with its downstream neighbor, this BQ_REPLY process can be avoided. If the SRC node moves after the route is no longer in use or active, then no BQ_REPLY is generated. 7.2.2. DEST Node Movements When the DEST moves, the DEST's immediate upstream neighbor (called a pivoting node) will erase the route, and then will perform a LQ[H] process to ascertain if the DEST is still reachable. 'H' here refers to the hop count from the upstream node to the DEST. If the DEST receives the LQs, it will select the best partial route and send a REPLY back to the pivoting node, otherwise the LQ_TIMEOUT period will be reached and the pivoting node will backtrack to the next upstream node. During the backtrack, the new pivoting node will erase the route through that link and perform a LQ[H] process until the new pivoting node is greater than the half route length away from the DEST or when a new partial route is found. If no partial route is found, the pivoting node will send a RN[1] packet back to the SRC to initiate a BQ process. 7.2.3. Intermediate Node (IN) Movements 7.2.3.1 Upper-arm Nodes' Migration Upper arm refers to the case when the INs and DEST node contribute to half of the route length from SRC to DEST. When any such IN moves, its immediate upstream node (i.e. pivoting node) removes its outgoing node entry and its immediate downstream neighbor propagates a RN[1] packets toward the DEST, thereby deleting all the subsequent downstream nodes' invalid routing entries. A new partial route to the DEST needs to be found. The pivoting node to locate alternate partial routes invokes a LQ[H] process. The DEST will then select the best route and it will send a REPLY to the pivoting node, and all INs between DEST and pivoting node will update their routing tables. 7.2.3.2 Lower-arm Nodes' Migration Lower arm refers to the case when the SRC and INs contribute to half the route length from SRC to DEST. If any of INs move, then a RN[1] packet will be propagated downstream towards the DEST, and the pivoting node will perform a LQ[H] and waits the DEST's REPLY. If no REPLY is received a RN[0] packet is sent to the upstream node and the new pivoting node then invokes the LQ[H] process again, but with a different value of H.The cycle proceeds until the new pivoting node is the SRC (where the BQ process will be iniated to discover a new route) or a partial route to the DEST is found. 'H' here refers to the on under localized query. 7.2.3.3 Concurrent Nodes' Movements Race conditions exist due to multiple invocations of RRC processes as a result of concurrent movements by SRC, DEST and INs. The following explains why the ABR routing protocol is immune to 'multiple-RRC' conflicts and how only one RRC is valid ultimately. a. DEST-Moves RRC interrupted by Upstream INs' Moves When the DEST moves and the while the RRC is in progress, any upstream INs moves will cause their respective downstream neighbors' route to be deleted. The new pivoting node nearest to the SRC will perform the RRC and all other RRCs will be passive when they hear the newer LQ broadcast for the same route. Hence only one RRC is valid. b. Upper-Arm IN RRC interrupted by Lower ARM INs Moves This is the same as the above-mentioned case. The same argument can be applied to the case when a LQ process has to be aborted and a RN [1] packet has to be sent to the SRC to invoke a BQ but is hindered due to some upstream Ins movements. The new pivoting node nearest to the SRC will swamp the earlier RRC process by invoking a new LQ. c. Lower-Arm IN RRC interrupted by Upper Arm INs Moves While a lower arm IN RRC is taking place, any movements by any upper arm INs will not result in a LQ [H] or RN [1] process being initiated since the lower arm IN has earlier sent RN [1] packet downstream to erase invalid routes. If the RN [1] packet does not succeed in propagating towards the DEST, the LQ [H] process initiated by the Lower arm IN will also serve to delete these invalid routes. d. Lower/Upper-Arm IN RRC interrupted by DEST's Moves This has no effect on the RRC, as the LQ [H] process uses a localized query approach to locate the DEST. Once the DEST is associatively stable and is reachable from the pivoting node, the RRC process will be successful. e. Lower/Upper-Arm IN RRC interrupted by SRC's Moves While the lower or upper arm IN RRC is in progress, any moves by the SRC will result in a BQ, which will swamp out all on going LQ_REPLY_RN processes related to that route. Hence, unfruitful and stale RRCs will not continue and a new route has to be discovered via the BQ process. f. SRC and DEST nodes moving away from INs When this occurs, RRCs as a result of DEST and SRC moves will be initiated. However, the BQ process initiated by the SRC will again swamp out all unnecessary on-going RRCs. g. DEST migrating into SRC's radio coverage range When the DEST migrates, RRC is achieved via the LQ [H] process. However, when the DEST is within the SRC's radio coverage, packet duplicates result at the DEST since the DEST now receives packets from the SRC directly and also from the original SRC to DEST route. Hence to avoid packet duplicates and non-optimal routes, the SRC, on discovering that the DEST is within range and is in stable state, will send a RN [1] packet downstream to erase existing route and will re-establish a new single hop route with the DEST. 7.2.4 Subnet-Bridging MH Movements The migration of a subnet-bridging MH beyond the radio coverage of its neighboring MHs will cause the mobile subnet to be partitioned. If an existing route doesn't span across the fragmented subnets, the route is not affected and only the subnet bridging MH's upstream and downstream neighbors need to update their route and associativity entries. All other MHs remain ignorant and don't perform any route updates. However, if a existing routes span across subnets, then the route is invalidated as the DEST is no longer reachable, despite any LQ or BQ attempts. Under such circumstances, the LQ_RN cycle will eventually inform the SRC about partitioning and the SRC can then invoke BQ query. 7.2.5 Route Erasure and Updates In ABR, no attempt is made to retain alternate routes, as maintaining them causes overhead. Only one route will be selected and only one route is valid for a particular route request. The avoidance of using alternate route information means that problems associated with looping due to INs having stale routes are absent and there is no need for periodic network-wide broadcast and route updates. To erase the invalid routes RN[1] and RN[0] packets are used, as explained in previous sections. 7.3 Route Deletion Phase When a discovered route is no longer desired, a route delete (RD) broadcast would be initiated by the SRC so that all INs will update their routing table entries. A full broadcast is used compared to directed broadcast. This is so because the nodes supporting a route will change during route reconstructions, hence using directed broadcast would be unsuitable unless the SRC is always informed about changes to a route path. 8. Acknowledgements and Retransmission 8.1 Date Flow Acknowledgement In ABR, a passive acknowledgement scheme is employed for packets in transition. When a node receives a packet and performs relaying via a radio transmission to its neighbors, its previous neighbor that has sent it the packet will have heard the transmission and hence this is indirectly used as an acknowledgement to the packet sent. On the other hand, active acknowledgements will only be sent by the DEST as it no longer has a neighbor to relay the packet to. Hence this provides a data flow acknowledgement mechanism for packet forwarding in an ad-hoc mobile network. 8.2 Packet Retransmission While the data flow acknowledgement scheme allows forwarded packets to be acknowledged, there are situations where the acknowledgements never reach the intended receiver. This can be a result of radio interference which causes a sudden loss of radio connectivity. Hence, if a MH has forwarded a packet and doesn't receive an acknowledgement within a certain time interval, it retransmits the packet for x times, after which the neighboring MH will be considered as 'out-of-reach' and RRC procedures will be invoked. If, however, the radio link returns before the retransmission counter expires, the packet forwarding process continues. 9. Other Issues 9.1 Battery Life There are many other issues that are not covered by this draft. Issues related to the effects of beaconing on battery life is worth investigating and reporting. The author however recognizes the existence of power management schemes in most notebook computers today. It would be desirable to see what proportion of a notebook power is consumed by transmit, receive, and sleep mode plus that by beaconing and the display and I/O devices. 9.2 Asymmetric Wireless Link In the wireless world, it is common that two mobile transceivers may not be able to communicate with one another in full duplex mode due to the presence of asymmetric wireless links. ABR has yet to be improved to overcome this limitation. 9.3 Caching In the original ABR publication [1996], caching was not employed in order to avoid maintaining the validity of the cache entry. However, if the degree of mobility is such that routes would not be invalidated that frequently, caching may appear attractive. 9.4 Multicasting ABR has so far addressed only unicast ad hoc routing with a strong emphasis on long-lived routing. However, multicasting support is important since most collaborative applications today involves multiple parties. 10. References [1] C.-K. Toh. A Novel Distributed Routing Protocol to Support Ad-Hoc Mobile Computing. Proceedings of IEEE International Phoenix Conference on Computers and Communications, March'96. (This is the first ABR publication.) [2] C.-K. Toh. Wireless ATM and Ad Hoc Networks. Kluwer Academic Press. December 1996. [3] C.-K. Toh. Associativity-Based Routing for For Ad Hoc Mobile Networks. Wireless Personal Communications Journal, Special Issue on Mobile Networking & Computing Systems, Vol. 4, No.2, March 1997. [4] Elizabeth Royer & C.-K. Toh. A Review of Current Routing Protocols for Ad Hoc Mobile Networks, IEEE Personal Communications Magazine, April 1999. 11. Patent Information The invention cited in this draft is protected by a US patent and permissions are required before any implementation of this invention is allowed. Such persons must also provide contact information to the author of this draft. Inclusively, any derivative or extensions to this work will require permissions from the author. Circulation of this draft is, however, unlimited. Author's Address Questions about this document can be directed to the author at: C.-K. Toh Mobile Multimedia & HiSpeed Networking Laboratory School of Electrical and Computer Engineering Georgia Institute of Technology Atlanta, Georgia GA 30332, USA Tel: 404-894-7468 Fax: 404-894-7883 cktoh@ece.gatech.edu