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
Datatracker
Report a datatracker bug
draft-ietf-manet-longlived-adhoc-routing-00
None
| Document | Document type |
Expired Internet-Draft
(manet WG)
Expired & archived
|
|
|---|---|---|---|
| Select version | |||
| Author |
C-K Toh
Email authors |
||
| RFC stream |
|
||
| Intended RFC status | (None) | ||
| Other formats | |||
| Additional resources | Mailing list discussion |