[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]

Versions: 00

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


Html markup produced by rfcmarkup 1.128b, available from https://tools.ietf.org/tools/rfcmarkup/