INTERNET-DRAFT                                           Mingliang Jiang
draft-ietf-manet-cbrp-spec-00.txt          National University of S'pore
draft-ietf-manet-cbrp-spec-01.txt                             Jinyang Li
                                           National University of S'pore
                                                         Yong Chiang
                                                                Y.C. Tay
                                        National University of S'pore Singapore
                                                          14 August 1998 1999

                  Cluster Based Routing Protocol(CBRP) Functional Specification

Status of this Memo

   This document is a submission by the Mobile Ad Hoc Networking Working
   Group of the Internet Engineering Task Force (IETF).  Comments should
   be submitted to the manet@itd.nrl.navy.mil mailing list.

   Distribution of this memo is unlimited.

   This document is an Internet-Draft. Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.  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 Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   To view the entire

   The list of current Internet-Drafts, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts can be accessed at:
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern
   Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific
   Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). can be accessed at:
   http://www.ietf.org/shadow.html.

Abstract

   Cluster Based Routing Protocol (CBRP) is a routing protocol designed
   for use in mobile ad hoc networks.  The protocol divides the nodes of
   the ad hoc network into a number of overlapping or disjoint 2-hop-
   diameter clusters in a distributed manner.  A cluster head is elected
   for each cluster to maintain cluster membership information. Inter-cluster Inter-
   cluster routes are discovered dynamically using the cluster
   membership information kept at each cluster head.  By clustering
   nodes into groups, the protocol efficiently minimizes the flooding
   traffic during route discovery and speeds up this process as well.
   Furthermore, the protocol takes into consideration of the existence of
   uni-directional links and uses these links for both intra-cluster and
   inter-cluster routing.

1

   This updated draft has a more detailed description of the cluster
   formation and routing process. In addition, it describes 2 major new
   features that have been added to the protocol: route shortening and
   local repair.  Both features make use of the 2-hop-topology
   information maintained by each node through the broadcasting of HELLO
   messages.  The route shortening mechanism dynamically shortens the
   source route of the data packet being forwarded and informs the
   source about the better route.  Local route repair patches a broken
   source route automatically and avoids route rediscovery by the
   source.

1. Introduction

   There are several major difficulties for designing a routing protocol
   for MANET.  Firstly and most importantly, MANET has a dynamically
   changing topology due to the movement of mobile nodes which favors
   routing protocols that dynamically discover routes over conventional
   distant vector routing protocols [6], e.g. (e.g. Dynamic
   Source Routing[4], TORA[3], ABR[5] etc. etc.)  over conventional distance
   vector routing protocols [6].  Secondly, the fact that MANET lacks
   any structure makes IP subnetting impossible. inefficient.  However, routing
   protocols that are flat, i.e. only one level of have no hierarchy, might suffer from
   excessive overhead when scaled up.  Thirdly, links in mobile networks
   could be asymmetric at times. Routing protocols could make use If a routing protocol relies only on
   bi-directional links, the size and connectivity of the
   uni-directional network may be
   severely limited; in other words, a protocol that makes use of uni-
   directional links to can significantly reduce network partitions and
   improve its overall routing performance.

   CBRP has the following features:

   * fully distributed operation.

   * less flooding traffic during the dynamic route discovery process.

   * explicit exploitation of uni-directional links that would otherwise
     be unused.

   * broken routes could be repaired locally without rediscovery.

   * sub-optimal routes could be shortened as they are used.

   The idea of using clusters for routing in Ad hoc networks has
   appeared in [7],[8].   In these protocols clusters are introduced to
   minimize updating overhead during topology change. However, the
   overhead for letting each and every node maintain maintaining up-to-date information about the whole
   network's cluster membership and inter-
   cluster inter-cluster routing information at
   each and every node in order to route a packet is considerable.  As
   network topology changes from time to time due to node movement, the
   effort to maintain such up-to- date information is expensive and
   rarely justified as such global cluster membership information is
   obsolete long before they are used.  In comparison, simpler and
   smaller clusters are found in [9] and [10], [10]; however, the use of these
   clusters is mainly for the task of channel assignment; assignment --- how they
   can help in the routing process is not discussed.

   CBRP adopts the cluster formation algorithm as proposed in [9], but
   unlike [9], CBRP mainly concentrates on the use of clusters in the
   routing process.  CBRP is different from previously proposed cluster-
   based routing algorithms and it uses a dynamic route discovery
   strategy.

2. CBRP terminology

   This section defines terms used in CBRP that do not appear in [2]:

   * Node ID

   Node ID is a string that uniquely identifies a particular mobile
   node.  Node IDs must be totally ordered. In CBRP, we use a node's IP
   address as its ID for purposes of routing and interoperability with
   fixed networks.

   * Cluster

   A cluster consists of a group of nodes with one of them elected as a
   cluster head. The election cluster formation procedure is described in section 5.1 and
   5.2.
   6.1.

   A cluster is identified by its Cluster Head ID. Clusters are either
   overlapping or disjoint.  Each node in the network knows its
   corresponding Cluster Head(s) and therefore knows which cluster(s) it
   belongs to.

   * Host Cluster

   A node regards itself as in cluster X if it has a bi-directional link
   to the head of cluster X.   In such a case, cluster X is a host
   cluster for this node. A node could have several host clusters.

   * Cluster Head

   A cluster head is elected in the cluster formation process for each
   cluster.  Each cluster should have one and only one cluster head.  A

   The cluster head has complete knowledge about group a bi-directional link to every node in the
   cluster.

   A cluster head will have complete knowledge about group membership
   and link state information in the cluster within a bounded time once
   the topology within a cluster stabalizes.  In CBRP, each node in the stabilizes.

   Conceptually, two cluster has heads are not allowed to have a bi-directional direct bi-
   directional link to each other.  If such a link exists, one of the
   cluster head. head will relinquish its role as cluster head to the other.
   However in CBRP, we do allow two cluster heads to be able to hear
   each other directly for CONTENTION_PERIOD seconds before one cluster
   head has to give up its cluster head status; this delays postpones
   any cluster re-organization, in case the two clusters are next to
   each other only in passing.

   * Cluster Member

   All nodes within a cluster EXCEPT the cluster head are called members
   of this cluster.

   * Gateway Node

   A node is called a gateway

   Any node of a cluster if it KNOWS that it has
   a bi-directional or uni-directional link head may use to a node from another
   cluster. As shown in Figure 1, node 3 and 4 are gateway nodes of communicate with an adjacent
   cluster 1, node 6 is called a gateway node.

   * HELLO message

   All nodes broadcast HELLO messages periodically every HELLO_INTERVAL
   seconds; a node's HELLO message contains its Neighbor Table and
   Cluster Adjacency Table.  A node of cluster 8.

           2       5
         //         \\
        //           \\
       (1)===3==6====(8)
        \\           //
         \\         //
           4<------7

             Fig. 1 may sometimes broadcast a triggered
   HELLO message in response to some event that needs quick action.

3. Conceptual Data Structures

   * Neighbor Table

   The neighbor table is a conceptual data structure that we employ for
   link status sensing and cluster formation. Each entry contains
    - the ID of a the neighbor that it has connectivity with and the status of that
   link and
    - the role of the neighbor (a leader cluster head or a member).

3. Physical and Link Layer Assumptions

   This section lists
    - the assumptions we made status of that link (bi-directional or uni-directional)

   * Cluster Adjacency Table

   The Cluster Adjacency Table keeps information about the underlying
   physical adjacent clusters
   and link layers when designing CBRP.  Each node in MANET is
   equipped with a transceiver.  In general, CBRP works best with
   omnidirectional antennas. maintained by CBRP's Adjacent Cluster Discovery procedure.
   Each packet that a node sends is entry contains:

      - the ID of the neighboring cluster head
      - the gateway node (a member) to reach the neighboring
        cluster head
      - the status of the link from the gateway to the neighboring
        cluster head (bi-directional or uni-directional)

   * Two-hop Topology Database

   In CBRP, each node broadcasts its neighbor table information periodi-
   cally in HELLO packets.  Therefore, by examining the neighbor table
   from its neighbors, a node is able to gather `complete' information
   about the network topology that is at most two-hops away from itself.
   This two-hop topology information is kept in a data structure in each
   node.

4. Physical and Link Layer Assumptions

   This section lists the assumptions we made about the underlying phys-
   ical and link layers when designing CBRP.

   Each MANET node that runs CBRP is equipped with one wireless
   transceiver.  CBRP is capable of handling multiple transceivers per
   host and multiple hosts per router if the concept of a router ID is
   introduced.  For example, a host with multiple transceivers may
   select the smallest IP interface address as its router ID.

   CBRP assumes omnidirectional antennas. Each packet that a node sends
   is broadcast into the region of its radio coverage.

4.  CBRP is designed
   to operate on top of a single-channel broadcast medium, however, it
   also accommodates the presence of multiple channels by forming dif-
   ferent sets of clusters for each channel for the same group of mobile
   nodes in a manner similar to that described in [11].

5. Link/Connection Status Sensing Mechanism

   In CBRP, each node knows its bi-directional links to its neighbors as
   well as unidirectional uni-directional links from its neighbors to itself.  For this
   purpose, each node maintains a Neighbor Table as follows:

     +------------+-------------------------------+---------------------+
     | NEIGHBOR_ID| LINK_STATUS                   | ROLE                |
     +------------+-------------------------------+---------------------+
     | neighbor 1 | bi/unidirectional link to me? | is 1 a cluster head?|
     +------------+-------------------------------+---------------------+
     | neighbor 2 | bi/unidirectional link to me? | is 2 a cluster head?|
     +------------+-------------------------------+---------------------+
     |  ...
     +------------+-------------------------------+---------------------+
     | neighbor N | bi/unidirectional link to me? | is N a cluster head?|
     +------------+-------------------------------+---------------------+

   Each node periodically broadcasts its Neighbor Table periodically in a HELLO
   message mes-
   sage, as shown below below, every HELLO_INTERVAL.

   +-----------+------------------------------------------------------+
   | MY_OWN_ID

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
                                                     +-+-+-+-+-+-+-+-+
                                                     | MY_MEMBERSHIP_STATUS Length    | S |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | (CLUSTER_HEAD/CLUSTER_MEMBER/UNDECIDED)                     Neighbor1 IP address                      |
   +-----------+------------------------------------------------------+
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Neighbor Table                     Neighbor2 IP address                      |
   +------------------------------------------------------------------+
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                    ...

        Length       The first field specifies number of neighbours listed.

        S(Status)   The current status of the ID sender.
               0 --- Undecided (C_UNDECIDED)
               1 --- Cluster Head (C_HEAD)
               2 --- Cluster Member (C_MEMBER)

        L      Link Status of the corresponding neighbor of the sender.  The second field
   tells whether
               0 --- LINK_BIDIRECTIONAL
               1 --- LINK_FROM

        R      Role of the sender is a cluster head, cluster member corresponding neighbor of the sender.
               0 --- Non-Cluster-Head(C_MEMBER or
   undecided.  ("undecided" means a node C_UNDECIDED)
               1 --- Cluster Head (C_HEAD)
   The IP addresses of the neighbors and the L and R bits are taken from
   the neighbor table.  The ID of the sender is still specified in search the source
   field of its host
   cluster) the IP header.  The status field tells whether the sender is
   a cluster head, member or undecided.  (The state of Undecided is
   defined in Section 6.1) An 4 byte long L/R bit block appears after
   every 16 neighbor addresses.  In the case that there are no more than
   16 neighbors listed, there will be only one such L/R bit block.

   Upon receiving a HELLO message from its neighbor B, node A modifies
   its own Neighbor Table as follows:

     1.   It checks if B is already in the Neighbor Table, Table; if not, it
          adds one entry for B.
       2. B if it has heard from B in the previous
          HELLO_INTERVAL before (i.e. A enters B in its Neighbor Table
          only when A has heard from B's HELLO messages twice in
          HELLO_INTERVAL interval).

          If B's Neighbor Table contains A,
               A marks the link to B as bi-directional in the relevant entry.
       3.
               entry

          else A marks the link to B as uni-directional (uni-directional
               from B to A).

     2.   If B is cluster head, marks already in A's Neighbor Table,

          2.1. If the link_status field of B's entry says bi-directional
               but A is not listed in B's hello message, then change it
               to uni-directional;

          2.2. If the link_status field of B's entry says uni-direc-
               tional but A is listed B's hello message, then change it
               to bi-directional.

     3.      Update the role of B as a cluster head in the Role field of B's entry.

   Each entry in the Neighbor Table is associated with a timer. A table
   entry will be removed if a HELLO message from the entry's node is not
   received for a period of (HELLO_LOSS+1)*HELLO_INTERVAL, allowing
   HELLO_LOSS consecutive HELLO messages to be lost from that node.

   When a nodes' node's neighborhood topology stabilizes, each the Neighbor Table of
   a node will have complete knowledge information of all the nodes that it has a bi-directional link
   to and all the nodes that have a
   bi-directional or uni-directional link to it within a bounded time.
   However, a node would not know to whom it has a uni-
   directional uni-directional link.
   For example in Figure 1, the Neighbor Table of node 7 will show that
   4 has a uni-directional link to it, however node 4 would not know of
   the existence of such a link.

             8       5
           //         \\      ====    bi-directional link
          //           \\
         (1)===3==6====(2)      (1), (2) cluster heads
          \\           //
           \\         //      --->    uni-directional link
             4------>7

               Fig. 1

   Note that the 2nd and 3rd column of the neighbor table and the status
   field of the hello message need not be
   sent out used for the purposes purpose of link sensing, however,
   sensing; they are there mainly for cluster formation and other functionality of adjacent
   cluster discovery, which will be discussed in Section 6.

   In addition to maintaining the protocol.

5. Neighbor Table at each node, the peri-
   odic broadcasting of HELLO messages also enables each node to gain
   complete information about all bi-directional links within two-hops.
   Such information is kept in a data structure we call the two-hop-
   topology database.  By checking its 2-hop-topology database, a node
   can tell who are its 2-hop bi-directionally linked neighbors and
   through which intermediate nodes can they be reached.  The format of
   this 2-hop-topology database is implementation dependent.

6. Protocol Operation

   The operations of CBRP are entirely distributed.  According to the
   functionality, CBRP could be viewed as a combination of the three
   following sub-functions which will be discussed below.

5.1  The major compo-
   nents are: Cluster Formation, Adjacent Cluster Discovery and Routing.

6.1 Cluster Formation

   The goal of Cluster Formation is to impose some kind of structure or
   hierarchy in the otherwise completely disorganized ad hoc network.
   The algorithm is a variation of the simple "lowest ID" clustering
   algorithm in which the node with a lowest ID among its neighbors is
   elected as the Cluster Head [9]. [11].

   Apart from the states of C_MEMBER and C_HEAD, we define a transi-
   tional state called C_UNDECIDED for smoother operation of cluster
   formation. "Undecided" means that a node is still in search of its
   host cluster. All nodes wake up in the Undecided state. We will refer
   to a node in the undecided state as an undecided node hereafter.

   A node uses the information obtained from the HELLO message messages for
   Cluster Formation.  A An Undecided node that has schedules a u_timer to go off in
   UNDECIDED_PD seconds and broadcast a HELLO message whenever it enters
   the lowest ID among all its bi-
   directionally linked neighbors (a C_UNDECIDED state.  When a cluster head receives a HELLO message
   from an Undecided Node, it will send out a triggered HELLO message
   immediately.  If an undecided node that has given up the role as receives a HELLO message from a
   Cluster Head is not counted, i.e. indicating a cluster member node ). bi-directional link in between, it aborts
   its u_timer and sets its own status to C_MEMBER. When the u_timer
   times out, if the node's Neighbor Table contains no bi-directional
   neighbors, then it re-enters the Undecided state; otherwise it elects
   itself as a Cluster Head. The new Cluster Head will change the first
   field in its subsequently broadcast HELLO messages from "undecided" C_UNDECIDED
   to "cluster head" C_HEAD thereafter.

   A cluster head regards all the nodes neighbors that it has bi-directional
   links to as its member nodes. A node regards itself as a member node
   for a particular cluster if it has a bi-directional link to the
   corresponding cor-
   responding cluster head.  Note that a member node may hear from
   several sev-
   eral cluster heads and therefore have several host clusters.

5.2 Cluster Maintenance

   As clusters are identified by their respective clusters; its host
   cluster heads are implicitly listed in the HELLO messages it broad-
   casts.

   As clusters are identified by their respective cluster heads, we
   would like to have the cluster heads change as infrequently as
   possible. possi-
   ble.  We use the following rules for changing cluster head, as
   described in [10].

     1. A non-cluster head never challenges the status of an existing
        cluster head, i.e. if X is a non-cluster head node with a
        bi-directional link to cluster head Y, X does not become
        a cluster head even if it has an ID lower than Y's.
     2. Only when When two cluster heads move next to each other (i.e. there
        is a bi-directional link between them), them) over an extended period
        of time (for CONTENTION_PERIOD seconds), then only will one of
        them loses the lose its role of cluster head.

   Therefore, our exact algorithm is not

   As a strict "lowest ID" clustering
   algorithm.  The cluster maintenance procedure are discussed under
   three subsections:

   * Node Removal

   A node X is removed from result, whenever a host cluster either because it loses the
   bi-directional links to the cluster head, or because of node
   failures.  In either case, the cluster head and node X will time out
   the corresponding entries in their Neighbor Table so that the hears HELLO messages from
   another cluster
   information will be updated.

   * Node Addition

   A member node is added to head indicating a new cluster when bi-directional link, it discovers a bi-
   directional link sets
   c_timer to the respective cluster head even expire in CONTENTION_PERIOD seconds.  When c_timer
   expires, it will check if the cluster
   head has a higher ID, which it is consistent still in contention with rule 1.  The node will
   know its new host the other
   cluster and head, by checking if the new host other cluster head will know its
   new member through the updated Neighbor Table.

   When a node is switched on, its MY_MEMBERSHIP_STATUS field still in the
   HELLO message is initially UNDECIDED for a period of UNDECIDED_PD. its
   neighbor table.  If so, it discovers compares its own ID with that it has of the other
   cluster head's.  The one with a bi-directional link smaller ID will continue to a cluster head, it
   modifies this field act as CLUSTER_MEMBER. If there is no such bi-
   directional links to any
   cluster head, it takes the head.  The one with a bigger ID gives up its role as a cluster
   head and indicates this changes from C_HEAD to C_MEMBER in the its subsequent HELLO messages it sends.

   * Cluster Head Contention

   When two Cluster Heads move next to each
   messages. This might trigger reorganization of other (till they have a bi-
   directional link in-between), one of them must give up its role as
   cluster Head.  As a result, whenever clusters.

   Whenever a member node's last cluster head hears the HELLO
   message from another cluster head indicating a bi-directional link in
   between, it will compare entry times out, this node
   checks among its own ID with that of bi-directionally linked neighbors if it has the other cluster
   head's. The one with a smaller ID will continue to act as cluster
   head.  The one with a bigger ID gives up its role as cluster head and low-
   est ID, if so it changes from "cluster head" to "member" in its subsequent HELLO
   messages. This might trigger the formation of other new clusters.

5.3  Routing Considerations

   Routing in the CBRP is based on source routing, which is similar state to
   [4]. Therefore, it can be viewed as consisting of 3 phases: route
   discovery, packets routing C_HEAD and stale route removal, of which packet
   routing is trivial.

   Cluster structure is exploited sends out a trig-
   gered HELLO, otherwise it goes to minimize the flooding traffic
   during route discovery phase. Furthermore, some uni-directional C_UNDECIDED state.

   A simplified state transition diagram without considering unidirec-
   tional links
   are discovered and used which increases network connectivity. This for Cluster Formation is
   discussed shown in the Gateway Discovery section.

5.3.1 Gateway Appendix A.

6.2 Adjacent Cluster Discovery

   Cluster X and cluster Y are said to be bi-directionally linked, if
   any node in cluster X is bi-directionally linked to another node in
   cluster Y, or if there is a pair of opposite uni-directional links
   between any 2 nodes in cluster X and cluster Y respectively.  For
   example in Figure 2, cluster 1 and cluster 2 are bi-directionally
   linked by the pair of links 3->4 and 5->6.

   Cluster X is said to be uni-directionally linked to cluster Y if any they
   are not bi-directionally linked and if there exists some node in
   cluster X that is uni-directionally linked to any other some node in cluster Y. Y
   X is called X's Y's upstream uni-directionally linked
   neighboring cluster.

   By Gateway Disvoery, a cluster head for adjacent cluster,
   and vice versa.  For example, in Figure 1, cluster X will obtain the
   information about 1 is cluster X's bi-directionally and 2's
   upstream uni-
   directionally uni-directionally linked neighboring clusters.

   For this purpose, a adjacent cluster.

   The goal of Adjacent Cluster Adjacency table Discovery is kept at for a cluster to discover
   all its bi-directionally linked adjacent clusters. For this purpose,
   each node
   which is formatted as follows:

   +------------------+-----------------------------------------------+
   |Adjacent Cluster1 | adjacent node|to/from/bi                      |
   +------------------+-----------------------------------------------+
   |Adjacent Cluster2 | adjacent node|to/from/bi                      |
   +------------------+-----------------------------------------------+
   |...                                                               |
   +------------------------------------------------------------------+

   This table is updated by the periodic HELLO message keeps a node hears. Cluster Adjacency Table (CAT) that records informa-
   tion about all its neighboring cluster heads.

   Note that for member nodes, neighboring cluster heads are always two
   hops away and can be discovered by checking received HELLO messages.
   For a node may have several links to nodes in cluster head, its neighboring cluster heads could be 2 or 3
   hops away (see Figure 2).  Using the HELLO messages alone, a particular cluster and only one of them
   head is recorded in able to discover the cluster heads 2 hops away.  However, it
   has to rely on its member nodes' Cluster Adjacency
   Table. Table to discover
   those neighboring cluster heads that are 3 hops away.

   The selection rule format of CAT at each node is as follows:

      1. A bi-directional link takes precedence over all uni-directional
         links.
      2. Of the links that have the same precedence, the one with

     +--------------+  +--------+-----------+  +--------+-----------+
     |Adj. Cluster1 |->|gateway1|link status|->|gateway2|link status|
     +--------------+  +--------+-----------+  +--------+-----------+
     |Adj. Cluster2 |->|gateway1|link status|->|gateway2|link status|
     +--------------+  +--------+-----------+  +--------+-----------+
     |...
     +------------------------------------------------------------+

   Gateway field contains the
         lowest ID wins.

   This table is periodically sent to of the member node's host gateway node through which the
   neighboring cluster
   heads.  (It head could be piggybacked to reached.  Gateway node is the HELLO message if possible.) A mem-
   ber node of the adjacent cluster head uses its members' Cluster Adjacency table and hence always has a bi-direc-
   tional link to construct
   its own the neighboring cluster adjacency table. head.  The construction rule is the same
   as that of link status refers
   to the member's.

   Cluster head will flood its neighboring clusters with a message status of
   TTL 3 in search for the "to" link that corresponds to between a "from" node's gateway node and itself.
   The possible values are LINK_BIDIRECTIONAL, LINK_FROM, LINK_TO where
   LINK_FROM means there is a uni-directional link
   in its Cluster Adjacency Table. As a result, cluster heads will have
   complete knowledge of all its bi-directionally linked neighboring
   clusters even if from gateway node to
   itself and LINK_TO means there is no actual bi-directional links in between.
   For example, in Fig 1, Cluster 1 knows that 2 can reach cluster 1
   through 5, but 1 does not know a uni-directional link from itself
   to the gateway.  Note that cluster 2 can there may be reached several gateway nodes leading
   towards a particular adjacent cluster.

   This table is updated by node
   3. In CBRP, cluster head 1 and 2 will discover this scenario and
   disseminate the information to periodic HELLO messages a node 3 and 5 respectively.

            3-->4
          //     \\              1 and 2 are hears.  A
   member node finds out cluster heads of their respective
         //       \\             clusters, 3,4,5,6 that are members.
        (1)       (2)
         \\       //
          \\     //
            6<--5

            Fig. exactly 2

5.3.2 Route Discovery

   Route Discovery is the mechanism whereby hops away and
   records them in its CAT.  In particular, whenever a node S wishing to send a
   packet to a destination D obtains A receives a source route to D. Similar to
   other MANET protocols [4] [1],
   HELLO message from B, it scans through the way S finds a route(or multiple
   routes) to D is also done by flooding, however, because message's list of entries.
   If there is a cluster head C and the
   clustering approach link status of the number entry is
   LINK_BIDIRECTIONAL (i.e.  B is a member node of nodes that are disturbed are much
   less in general.

   Essentially in Route Discovery, cluster heads are flooded C) and, fur-
   thermore, C is not already A's host cluster, A adds an entry in search CAT
   for a source route. To perform Route Discovery, the source node S
   sends out a Route Request Packet (RREQ), adjacent cluster C with a recorded source route
   listing only itself initially. Any gateway node B and link status specifying
   status of link between A and B.

   In order for cluster heads to gain information on their adjacent
   clusters that forwards this packet
   will append its own ID in this RREQ.  Each are 3 hops away, each member node forwards broadcasts its summa-
   rized CAT as a RREQ
   packet only once and it never forwards it Cluster Adjacency Extension to a node that has already
   appeared in the recorded route. In CBRP, the RREQ HELLO message.
   (Only member node will always follow
   a route with the following pattern to reach destination D:
           S,CH1,G1,CH2,G2,G3,CH3 ..... D

   A detailed description of how send out this information, this is achieved is presented below.
   Source always unicasts RREQ to its cluster head, say CH1.  Each
   cluster head will unicast RREQ to each of its bi-directionally linked
   neighbors which have not yet appeared in the recorded route through the corresponding gateway. This process continues until the target
   case with cluster heads.) The rules for summarizing is
   found or until another node that can supply a route to the target as follows:

     - If there is
   found.

   When the target of at least one gateway with whom the Request, node D, receives the RREQ, D may
   choose to memorize the reversed source route to S.  Node D then
   copies the recorded source route into has a Route Reply packet(RREP)
   which
       bi-directional link, it then sends back to advertise the initiator of neighboring cluster as
       bi-directionally reachable.

     - If there are only uni-directional links (LINK_FROM), the Route Request (e.g.,
   node S)
       neighboring cluster will be advertised as LINK_FROM.
       (Note that, by reversing the recorded route and putting it in the IP
   header of HELLO messages alone, a node is not able to
       detect any LINK_TO link to the Route Reply packet. gateway.)

   The recorded route gives the
   complete information about format of the SEQUENCE OF CLUSTERS source should
   traverse in order Cluster Adjacency Extension to reach destination D.  While forwarding the Route
   Reply, intermediate cluster heads modifies the HELLO message is
   shown below:

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
                                                     +-+-+-+-+-+-+-+-+
                                                     |    Length     |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Adj. Cluster Head1  IP address                    |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Adj. Cluster Head2  IP header address                    |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                ....
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        Length       The number of clusterheads listed in the
   packets, substitute Extension.

        L            Link Status of the inter-cluster incoming links corresponding Adjacent Cluster
                     head. If there is at least one gateway node having
                     bi-directional link to inter-cluster
   outgoing links. Each intermediate cluster head also modifies the
   recorded route in the Route Reply packet to optimize Adjacent Cluster head,
                     the recorded
   route as much Link status is specified as possible LINK_BIDIRECTIONAL.
                     Otherwise, it is LINK_FROM.

                     0 --- LINK_BIDIRECTIONAL
                     1 --- LINK_FROM

   In addition to using HELLO messages to construct its knowledge CAT consisting
   of the 2-hop away neighboring cluster topology
   and inter-cluster gateway information. An example of such
   optimization is heads, a cluster head could check
   its members' Cluster Adjacency Extension to connect two gateway nodes by an intra-cluster link
   that does not go through find out its 3-hop away
   neighboring cluster heads in its CAT.  In particular, suppose cluster
   head A receives B's HELLO message.  After updating its CAT with the
   Neighbor Table entries in HELLO, A proceeds to check B's Cluster
   Adjacency Extension in HELLO, if it finds adjacent cluster head.

   All source routes learned by head C
   that is not already reachable within 2 hops, it creates a new entry
   in CAT for it with the gateway node are kept as B and link status as specified
   in a Route Cache, which
   is used to further reduce the cost of Route Discovery.  When extension.

   If a node
   wishes to send cluster head finds that some adjacent clusters are reachable
   only through a packet, LINK_FROM uni-directional link, it examines will flood its own Route Cache and performs
   Route Discovery only if no suitable source route is found
   neighborhood with a message of TTL 3 in its
   cache.

5.3.3 Route Removal

   A source route is removed from S if the network topology has changed
   such search for a "to" link that S can no longer use the route
   corresponds to D because this "from" link.  This message will contain the cor-
   responding entry for the adjacent cluster.  When a hop along cluster head
   receives such a message searching for it, it will check if it con-
   tains a corresponding LINK_FROM entry to the
   route no longer works. source cluster head.  If S still wants to communicate with D,
   so, it can
   invoke Route Discovery again to find will send out a new route.

6. Discussions and Implementation Considerations

   This section discusses some of reply with the problems that we have encountered
   during corresponding CAT entry and
   update its CAT with the design of CBRP. In particular, they are related to new LINK_TO entry as specified in the use
   message.  As a result, cluster heads will have complete knowledge of uni-directional
   all its bi-directionally linked adjacent clusters even if there is no
   actual bi-directional links in routing.

6.1 ARP and Uni-directional links

   In a MANET context, links between 2 nodes can be bi-directional and
   uni-directional.   However, when the link layer does MAC-layer
   address based packet filtering, (which most current technologies do),
   special care has to be taken for ARP for uni-directional links. between. For example, when there is a uni-directional link from node A to node B
   as shown in Figure 2, node A should
   Cluster 1 knows that 2 can reach cluster 1 through 5, but 1 does not rely on the conventional ARP
   protocol to resolve node B's MAC layer address, because
   know that cluster 2 can be reached through node B's ARP
   reply 3. In CBRP, cluster
   head 1 and 2 will never reach discover this scenario and disseminate the informa-
   tion to node A directly.

          A---->B

          Fig. 3 and 5 respectively.

              3-->4
            //     \\              1 and 2 are heads of their respective
           //       \\             clusters, 3,4,5,6 are members.
          (1)       (2)
           \\       //
            \\     //
              6<--5

              Fig. 2

6.3  Routing Considerations

   Routing in CBRP is able to use uni-directional links. For an intra-cluster uni-
   directional link, the upstream node based on source routing. It can be informed by its cluster
   head of the MAC-layer address of the downstream node. For a inter-
   cluster uni-directional link, viewed as shown in Figure 1, node 3(5) will
   know node 4(6)'s MAC-layer address by the process of gateway
   discovery.

6.2 Rate con-
   sisting of Stale Route Discovery 2 phases: route discovery and Uni-directional Links

   In general (not pertaining the actual packets routing.

   Cluster structure is exploited to CBRP),  when minimize the flooding traffic dur-
   ing route discovery phase. Furthermore, certain uni-directional links
   are discovered and used, discovery of stale routes can be slow. As shown in Figure 3,
   when thus increasing the link between 1 and 2 breaks, network connectivity.

6.3.1 Route Discovery

   Route Discovery is the mechanism whereby a node 1 will not be aware until S wishing to send a message comes from 2 by
   packet to a destination D obtains a source route to D. Similar to
   other MANET protocols [4] [1], the way S finds a route(or multiple
   routes) to D is also done by flooding, however, because of 3,4,5,6. This observation justifies
   CBRP's use the clus-
   tering approach the number of inter-cluster uni-directional links times nodes are disturbed are much less
   in general.

   Essentially, in Route Discovery, only between 2
   clusters.

              1--->2--->3--->4--->5
              ^                   | cluster heads are flooded with
   Route Request Packets (RREQ) in search for a source route.  The for-
   mat of such a packet is shown below:

         0                 1                   2                   3
         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |1 0| Num1      |  Num2         |         Identification        |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                         Target Address                        |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |
              +-------- 6 <-------+

                     Fig. 4

7. Future Directions               Gateway Node Address[1]                         |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |               Neighboring Cluster based routing protocols (CBRP) is Head[1]                     |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |.....                                                          |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |               Gateway Node Address[Num1]                      |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |               Neighboring Cluster Head[Num1]                  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Cluster Address[1]                         |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                               ...                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Cluster Address[Num2]                      |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        10                     type of CBRP packet (Route Request)
        Num1                   the first step towards number of Gateway Node Address
                               & Adjacent Cluster Address pairs
        Num2                   the number of Cluster Addresses
        Identification         a
   more scalable solution using clustering approach. number the RREQ originator generates
                               to uniquely identify this RREQ sent by it.
        Gateway Node Address   the gateway node who will forward this RREQ
        N'ghboring ClusterHead the corresponding cluster head the gateway
                               node will forward this RREQ to.

   To perform Route Discovery to D, the source node S sends out an RREQ,
   with the target node address field set to D. It also suggests
   how uni-directional links in Ad hoc networks can be used in routing fills the Neighboring
   Cluster Head entries with its host cluster head(s) and adjacent clus-
   ter head entries(from CAT), the reveals problems resulting from such use.

   Several questions remain corresponding Gateway Node Address is
   either the host cluster head itself or the adjacent cluster's gateway
   node.  This initial RREQ is broadcast.

     1. Whenever a member node M receives an RREQ,
        if D is its neighbor, RREQ is just uni-cast to be answered D.
        else
           if M is specified as the Gateway Node[x],
               uni-cast(relay) the RREQ to Cluster Head[x].
           else
               discard the RREQ.

     2. Whenever a cluster head C receives an RREQ,
        2.1 if it has seen this RREQ before (by looking at the identification
            field) discard it; otherwise, continue.
        2.2 records its own address in CBRP,

     1. How collisions can Cluster Address list.
        2.3
           if D is its neighbor or is 2-hop away
              uni-cast RREQ to D.
           else
              for each bi-directionally linked cluster head CH in C's CAT
                 if CH is already in previous RREQ's
                 Neighboring Cluster Head list,
                    skip
                 else if CH is in Cluster Address list
                    skip
                 else
                    record CH entry in Neighboring Clusterhead/Gateway Node pair
              broadcast RREQ

   Each cluster head node forwards an RREQ packet only once and it never
   forwards it to a node that has already appeared in the recorded
   route. In CBRP, the RREQ will always follow a route with the follow-
   ing pattern to reach destination D:
           S,CH1,G1,CH2,G2,G3,CH3 ..... D

   The recorded route in Cluster Address list will be CH1, CH2, CH3 ...

   When the target of the Request, node D, receives the RREQ, D sends
   out an RREP packet to S as a reply, with the following format:

         0                 1                   2                   3
         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |0 1| Num1      |G|  Num2       |         Identification        |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Cluster Address[1]                         |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                               ...                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Cluster Address[Num1]                      |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Calculated Route[1]                        |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                               ...                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Calculated Route[Num2]                     |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      01                     type of CBRP packet (Route Reply)
      G                      the flag indicating if this RREP is a
                             gratuitous reply packet(refer to 5.3.3)
      Identification         the identification number copied from the
                             corresponding RREQ.
      Num1                   the number of Cluster Addresses
      Num2                   the number of addresses in Calculated Route
      Cluster Address        copied from the corresponding RREQ. This is
                             the sequence of cluster heads the RREP will
                             traverse in order to reach RREQ originator.
                             (This sequence will be shortened by for-
                             warding cluster heads along the way and the
                             last address will always be the next stop
                             cluster head to forward this RREP).
      Calculated Route       A sequence of addresses of the hop by hop
                             source route calculated by the clusterhead.

   D copies the list of Cluster Addresses into the RREP packet.  (D may
   choose to memorize the reversed list of Cluster Addresses to S so
   that if D wants to find out a route to S, it may directly probe this
   route of cluster heads).  D also copies the identification field in
   RREQ to RREP and puts its own address in Calculated Route[1].

   The recorded Cluster Addresses gives the complete information about
   the SEQUENCE OF CLUSTERS RREP should traverse in order to reach S.
   Since each cluster head has knowledge of how to reach its neighboring
   CHs, the RREP packet will be routed to S eventually using IP loose
   source routing.

   While forwarding the Route Reply, intermediate cluster heads will
   calculate an optimized hop-by-hop route according to the information
   contained in the list Cluster Addresses and put it in the Calculated
   Route field.

   For example, 1. suppose cluster head C receives a RREP
     1.1 It decrements Num1 by 1.
         Cluster Address[Num1] is the neighboring cluster head
         that C should forward RREP to in order to reach S.
     1.2 C tries to find out a gateway node X to Cluster Address[Num1]
         such that the Calculated Route[Num2] could reach X directly.
         If it succeeds,
           send RREP to X
         else,
           C increment Num2 by 1 and C records itself in Calculated
           Route[Num2].  2. suppose member node M receives a RREP
     2.1 It increments Num2 by 1 and records itself in
         Calculated Route[Num2].
     2.2 if Cluster Address[Num1] is its Neighbor,
           send RREP to it directly
         else if Cluster Address[Num1] could be reached by X,
           send RREP to X.

   If a source does not receive any RREP after sending out RREQ for cer-
   tain period of time, it goes into exponential backoff before re-send-
   ing RREQ.

   As usual, all source routes learned by a node are kept in a Route
   Cache.  When a node wishes to send a packet, it always examines its
   own Route Cache first before performing Route Discovery.

6.3.2 Routing

   The actual routing is done using Source Routing and the format of the
   packet is shown below:

         0                 1                   2                   3
         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
                                        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                        |0 0| Num       |R|S|Current Num|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Address[1]                                 |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                               ...                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Address[Num]                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      00           CBRP packet type (Normal data packet containing a
                   source routing header.)

      Num          the number of addresses in the source route
                   Address[1..Num]
      Current Num  specifies the currently visited address.
      R flag       indicates if this route has been salvaged using local
                   repair
      S flag       indicates if this route has been shortened

   * Route Shortening

   Due to node movement or other reasons, a source route may become less
   optimal over time and should be shortened whenever possible.  The
   route shortening mechanism shortens sub-optimal routes locally using
   the 2-hop-topology database information.

   It works as follows:

   Whenever a node receives a source-routed data packet, it tries to
   find out the furthest node in the unvisited route that is actually
   its neighbor.  If it succeeds, it shortens the source route accord-
   ingly and sets the S flag before forwarding the packet.

   When a destination node receives a data packet with S flag set, it
   sends back a gratuitous RREP (setting the G flag in RREP) containing
   the shortened route to the packet source to inform it of the better
   route.

   * Route Error

   When a forwarding node finds out that the next hop along the source
   route for an unsalvaged packet is no longer reachable, it will create
   a Route Error (ERR) packet and send it back to the packet source to
   notify it of the link failure.  The format is shown below:

         0                 1                   2                   3
         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
                                        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                        |1 1| Num       | Current Num   |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                            Address[1]                         |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                               ...                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                            Address[Num]                       |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Broken Link From_Address                   |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Broken Link To_Address                     |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      11            CBRP Packet type (Route Error packet).
      Num           the number of addresses in the source route.
      Address       the source route this ERR packet has to traverse
                    in order to reach its destination. It is taken from
                    the source route of the data packet.
      From_Address  the ERR originator's own address.
      To_Address    unreachable next hop as specified in the original
                    source route of the data packet.

   * Local Repair

   After the forwarding node detects a broken route and sends out an ERR
   packet, it will try to salvage the data packet the best way it can
   using its own local information:

   1. It checks if the hop after next in the source route is reachable
      through an intermediate node other than the one specified as the
      next hop by searching through its 2-hop-topology database.

   2. It checks if the unreachable next hop could be reached through
      an intermediate node by checking its 2-hop-topology database.

   3. If the packet could be saved, it
      modifies the source route, sets the R flag and sends out the
      packet to the new next hop.

   Because of spatial locality, even though the next hop node moves out
   of reach from the current node, it is possible that it can still be
   reached within 2 hops.  Our simulation shows that this Local Repair
   mechanism works very well, saving a majority of data packets.

   When a destination node receives a data packet with R flag set, it
   sends back a gratuitous RREP (setting the G flag in RREP) containing
   the repaired route to the packet source to inform it of the repaired
   route, avoiding unnecessary route re-discovery.

7. Discussions and Implementation Considerations

7.1 ARP Optimization

   ARP is necessary as a node needs to know the MAC address of the next
   hop in order to send a packet.  In CBRP, however, the next hop a node
   sends the packet to is always its neighbor node.  If a node records
   the source MAC to IP mapping in ARP cache whenever it receives a
   HELLO message, it could completely avoid ARP message exchange during
   routing.

7.2 Problems with Uni-directional links

   This section discusses some of the problems that we have encountered
   during the design of CBRP. In particular, they are related to the use
   of uni-directional links in routing.

7.2.1 ARP problem

   In a MANET context, links between 2 nodes can be bi-directional and
   uni-directional.   However, when the link layer does MAC-layer
   address-based packet filtering (which most current technologies do),
   special care has to be taken with ARP for uni-directional links.  For
   example, when there is a uni-directional link from node A to node B
   as shown in Figure 3, node A should not rely on the conventional ARP
   protocol to resolve node B's MAC layer address, because node B's ARP
   reply will never reach node A directly.

          A---->B

          Fig. 3

   CBRP is able to use uni-directional links. For an intra-cluster uni-
   directional link, the upstream node can be informed by its cluster
   head of the MAC-layer address of the downstream node. For an inter-
   cluster uni-directional link, as shown in Figure 2, node 3(or 5) will
   know node 4(or 6)'s MAC-layer address by the process of adjacent
   cluster discovery.

7.2.2 802.11 Link Layer Technology

   It seems hard to make good use of uni-directional links without vio-
   lating the standard 7-layer OSI model.  The current 802.11 MAC layer
   does not consider the existence of uni-directional links, nor does it
   support them.  The sequence of RTS/CTS/Data/ACK exchange will auto-
   matically exclude the use of any uni-directional links even if one
   knows their existence.

   One possible extension to this technology is to allow ACKs to be for-
   warded by neighboring cluster heads back to the sender if a uni-
   directional link between two clusters are being used.  Such a return
   path is bounded by maximum 5 hops.  The forwarding of ACK could be
   viewed as collapsing layer 2 and layer 3 routing functionality, a
   violation of the layering model which states that lower layer should
   hide details away from upper layers.  Although this seems rather
   inefficient at first sight, if we consider the fact the bi-direc-
   tional links are preferred over uni-directional links in CBRP, we
   would realize that such a uni-directional link will not be used
   unless one cannot reach a specific node using bi-directional links
   only.

7.3 Rate of Stale Route Discovery and Uni-directional Links

   In general (not pertaining to CBRP),  when uni-directional links are
   used, discovery of stale routes can be slow. As shown in Figure 4,
   when the link between 1 and 2 breaks, node 1 will not be aware until
   a message comes from 2 by way of 3,4,5,6. This observation justifies
   CBRP's use of inter-cluster uni-directional links only between 2
   clusters.

              1--->2--->3--->4--->5
              ^                   |
              |                   |
              |                   |
              |                   |
              +-------- 6 <-------+

                     Fig. 4

8. Constants and Suggested Values
   These are the CBRP constant values that we have experiemented with in
   the simulation.

      HELLO_INTEVAL                1.5s or 2s
      HELLO_LOSS                   1
      CONTENTION_PERIOD            1.5s

9. Applicability Statement

      This section summarizes the characteristics of CBRP, as
      specified in the Applicability Statement draft.

9.1 Network Context

   The protocol is designed for medium to large networks with relatively
   large average nodal degree (> 5).  Nodal mobility should not be too
   high, i.e. node cannot move quicker than the speed of cluster forma-
   tion which is defined as 1/HELLO_INTERVAL.

   This protocol is suited for networks where most of the traffic is
   among a small set of sender-receiver pairs compared to the possibil-
   ity of N*(N-1)/2 number of pairs.  Also, the applications supported
   should be able to tolerate the delay of route discovery time.

9.2 Protocol Characteristics and Mechanisms

     *    Does the protocol provide support for unidirectional links?
          (if so, how?)

          Yes.  It selectively makes use of those uni-directional links
          that could give two-way-route to nodes that are otherwise
          inaccessible using only bi-directional links.

     *    Does the protocol require the use of tunneling? (if so, how?)

          No.

     *    Does the protocol require using some form of source routing?
          (if so, how?)

          Yes.  routes are discovered in route discovery stage and will
          be carried in the packet headers in actual routing.  (Refer to
          Section 6.2)  However, source routing is actually not
          essential to the correct working of CBRP.  As source routing
          poses a non-negligible overhead when the network sizes grow,
          we are currently designing alternatives to replace it with
          more efficient mechanisms.

     *    Does the protocol require the use of periodic messaging? (if
          so, how?)

          Yes. Periodically, each node in the network sends a HELLO mes-
          sage containing its current neighbor table.  The size of the
          message is proportional to the degree of the node (i.e. the
          number of neighbors), which is around 6 to 15 for networks of
          average density.

     *    Does the protocol require the use of reliable or sequenced
          packet delivery? (if so, how?)

          No.

     *    Does the protocol provide support for routing through a multi-
          technology routing fabric? (if so, how?)

          Yes.  Each network interface is assigned a unique IP address
          used for routing purpose.

     *    Does the protocol provide support for multiple hosts per
          router?  (if so, how?)

          Yes.  A number of hosts, each having a unique IP address,
          could associate itself with a router that forwards packets and
          participates in the routing protocol on the hosts' behalf.

     *    Does the protocol require link or neighbor status sensing (if
          so, how?)

          Yes. Neighbor status sensing is required.

     *    Does the protocol have dependence on a central entity? (if so,
          how?)

          No.  All the functions are achieved in a distributed manner.
          The cluster formation process differentiates the roles of
          nodes as cluster heads and member nodes.  Cluster heads are
          flooded during the route discovery phase to find a route to
          the destination.  However the actual routing will try to
          bypass cluster heads as intermediate nodes.

     *    Does the protocol function reactively? (if so, how?)

          Yes.  It defers getting the route information until such a
          route is explicitly asked for by the application.  Routing is
          done on demand with 3 phases: route discovery, packet routing,
          route removal.

     *    Does the protocol function proactively? (if so, how?)

          No.  But it proactively acquires its 2-hop topology informa-
          tion through the exchange of HELLO messages.

     *    Does the protocol provide loop-free routing? (if so, how?)

          Yes.  Source routing records all nodes along the route that
          could be avoided or handled effectively. Shall we
        have spatial reuse easily checked for loop-freedom.

     *    Does the protocol provide for sleep period operation? (if so,
          how?)

          No.

     *    Does the protocol provide some form of security? (if so, how?)

          Not by itself. It has to rely on other protocols (e.g. IMEP,
          IPsec) to give security support.

     *    Does the channels among different clusters?
     2. Should clusters have native protocol provide support for QoS as in [10]?
     3. Should clusters be made bigger than two hops diameter? If utilizing multi-channel,
          link-layer technologies? (if so,
        what criteria should how?)

          Yes.  Cluster-formation algorithms could be used run on different
          channels to form a bigger cluster? Or,
        should we use a hierarchy yield different sets of clusters for each channel.
          Routing could be done independently on each of clusters?  Will the resulted more
        complex cluster formation and maintenance procedure offset the
        advantage set of having a bigger size?

   To give satisfactory answers to these interesting questions will be
   our future directions in refining CBRP.
          clusters.

References
   [1] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing",
       MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3,
       1997.

   [2] Perkins, C.E., "Mobile Ad Hoc Networking Terminology",
       draft-ietf-manet-term-00.txt, work in progress.

   [3] Corson, M.S., and Ephremides, A., Park V., Corson M.S, "A Highly Adaptive Distributed Routing
       Algorithm for Mobile Wireless Networks", ACM/Baltzer Journal
       on Wireless Networks, January 1995. Networks," Proc. IEEE INFOCOM '97,
       Kobe, Japan, Apr 1997.

   [4] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing in
       Ad-Hoc Wireless Networks", Mobile Computing, T.Imielinski and
       H.Korth, editors, Kluwer, 1996.

   [5] Toh,C.K., "A Novel Distributed Routing Protocol To Support
       Ad-Hoc Mobile Computing", International Phoenix Conference on
       Computers and Communications (IPCCC'96), pg 480-486, March 1996.

   [6] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1998.

   [7] Das, B., Raghupathy, S, Vaduvur, B, "Routing in Ad Hoc Networks
       Using a Spine", Proceedings of 6th International Conference on
       Computer Communications and Networks, Las Vegas, USA, September,
       1997.

   [8] Krishna, P., Vaidya, N.H., Chatterjee, M., Pradhan, D.K., " A
       Cluster-based Approach for Routing in Dynamic Networks",
       Proceedings of the Second USENIX Symposium on Mobile and
       Location-Independent Computing, 1995.

   [9] Gerla, M., Tsai, T.C., "Multiculster, mobile, multimedia radio
       network", ACM/Balzer Journal of Wireless Networks, 1995.

   [10] Chiang, C.C., Wu, H.K., Liu, W., Gerla, M., "Routing in
        Clustered Multihop, Mobile Wireless Networks with Fading
        Channel", The Next Millennium, the IEEE SICON, 1997.

   [11] Ephremides A., Wieselthier J.E., Baker D.J., "A Design Concept
        for Reliable Mobile Radio Networks with Frequency Hopping
        Signaling", Proceedings of the IEEE, Vol.75, No.1, Jan 1987

Appendix A

     +---------------------------> C_UNDECIDED
     |             +-------------------+------------------------+
     |             |                   |                        |
     |       +-----+----------+   +----+----------+      +------+--------+
     |      /  receive HELLO /   / u_timer times /      / receive HELLO /
     |     /  from non-head /   /  out          /      /  from head    /
     |    +---------+------+   +--------+------+      +----------+----+
     |             |                   |                        |
     |  +----------+----------+  (Neighbor Table       +--------+--------+
     |  |update Neighbor Table|      Empty?)           |kill u_timer     |
     |  +----------+----------+ YES/    \NO            |update Neighbor  |
     |             | +------------+ +----+----------+  |Table as C_MEMBER|
     +-------------+-+schedule new| |send triggered |  +--------+--------+
     |               |u_timer     | |HELLO as C_HEAD|           |
     |               +------------+ +---------+-----+           |
     |                                        |                 |
     | +--------------------> C_HEAD <--------+                 |
     | |        +----------------+----------------+             +------+
     | |        |                |                |                    |
     | |   +-------------+  +--------------+  +--------+               |
     | |  /receive HELLO/  / receive HELLO/  /c_timer /                |
     | | /from non-head/  / from C_HEAD  /  / expires/                 |
     | |+-----+-------+  +--------+-----+  +-----+--+                  |
     | |      |                   |              |                     |
     | |      |           +-----------------+(Still in contention      |
     | |+---------------+ |receive HELLO    | with the other head?)    |
     | ||update Neighbor| |from C_HEAD,set  | NO/\ YES                 |
     | ||Table          | |c_timer          |  / (my ID smaller?)      |
     | |+-----+---------+ +-------+---------+ /   /    \ NO            |
     | |      |                   |          /YES/ +----+------------+ |
     | +------+-------------------+---------+----+ |send triggered   +-+
     | |                                           |HELLO as C_MEMBER| |
     | |                                           +-----------------+ |
     | |                          C_MEMBER <---------------------------+
     | |                     +-------+----------------------+          |
     | |                     |                              |          |
     | |                   +--------+-----+          +------+-------+  |
     | |                  /last head lost/          / receive HELLO/   |
     | |                 +----------+---+          +--------+-----+    |
     | +---------------+            |                       |          |
     | |send triggered +-YES-+(my ID smallest?)    +--------+-------+  |
     | |HELLO as C_HEAD|            |              | update Neighbor+--+
     | +---------------+          NO|              | Table          |
     |                      +-------+--------+     +--------+-------+
     +----------------------|schedule u_timer|
                            +----------------+
   This work was supported in part by National University of Singapore
   ARF grant RP960683.

Authors' Information

   CBRP's URL:
   Contains information on CBRP's latest development and simulation code
   http://cram.comp.nus.edu.sg/cbrp/

   Jiang Mingliang
   Mobile Computing Lab
   School of Computing
   National University of Singapore
   Singapore 119260
   Email: jiangmin@comp.nus.edu.sg jiang@eudoramail.com

   Li Jinyang
   Mobile Computing Lab
   School of Computing
   National University of Singapore
   Singapore 119260
   Email: lijinyan@comp.nus.edu.sg lijy@acm.org

   Y.C. Tay Yong Chiang
   Department of Mathematics
   National University of Singapore
   Singapore 11920 119260
   Email: mattyc@leonis.nus.edu.sg tay@acm.org