draft-ietf-manet-cbrp-spec-01.txt

在ns2中实现了cbrp协议

INTERNET-DRAFT                                           Mingliang Jiang
draft-ietf-manet-cbrp-spec-01.txt                             Jinyang Li
                                                                Y.C. Tay
                                        National University of Singapore
                                                               July 1999


                  Cluster Based Routing Protocol(CBRP)



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 [e-mail] mailing list.

   Distribution of this memo is unlimited.

   This document is an Internet-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."

   To view the entire list of current Internet-Drafts, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts 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).


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 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 the existence of



Jiang, Li, Tay                                                  [Page 1]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   uni-directional links and uses these links for both intra-cluster and
   inter-cluster routing.

   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 (e.g. Dynamic
   Source Routing[4], TORA[3], ABR[5] etc.)  over conventional distance
   vector routing protocols [6].  Secondly, the fact that MANET lacks
   any structure makes IP subnetting inefficient.  However, routing
   protocols that are flat, i.e. have no hierarchy, might suffer from
   excessive overhead when scaled up.  Thirdly, links in mobile networks
   could be asymmetric at times. If a routing protocol relies only on
   bi-directional links, the size and connectivity of the network may be
   severely limited; in other words, a protocol that makes use of uni-
   directional links can significantly reduce network partitions and
   improve 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



Jiang, Li, Tay                                                  [Page 2]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   appeared in [7],[8].   In these protocols clusters are introduced to
   minimize updating overhead during topology change. However, the
   overhead for maintaining up-to-date information about the whole
   network's cluster membership and 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]; however, the use of these
   clusters is mainly for the task of channel 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.

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 cluster formation procedure is described in section
   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



Jiang, Li, Tay                                                  [Page 3]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   cluster.  Each cluster should have one and only one cluster head.
   The cluster head has 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 stabilizes.

   Conceptually, two cluster heads are not allowed to have a direct bi-
   directional link to each other.  If such a link exists, one of the
   cluster 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

   Any node a cluster head may use to communicate with an adjacent
   cluster 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 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 the neighbor that it has connectivity with and
    - the role of the neighbor (a cluster head or a member).
    - the status of that link (bi-directional or uni-directional)

   * Cluster Adjacency Table




Jiang, Li, Tay                                                  [Page 4]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   The Cluster Adjacency Table keeps information about adjacent clusters
   and is maintained by CBRP's Adjacent Cluster Discovery procedure.
   Each 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.  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 uni-directional links from its neighbors to itself.  For this
   purpose, each node maintains a Neighbor Table as follows:








Jiang, Li, Tay                                                  [Page 5]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


     +------------+-------------------------------+---------------------+
     | 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 in a HELLO mes-
   sage, as shown below, every HELLO_INTERVAL.


      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    | 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|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                     Neighbor1 IP address                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                     Neighbor2 IP address                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                    ...



        Length       The number of neighbours listed.

        S(Status)   The current status of the 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.
               0 --- LINK_BIDIRECTIONAL
               1 --- LINK_FROM

        R      Role of the corresponding neighbor of the sender.
               0 --- Non-Cluster-Head(C_MEMBER or C_UNDECIDED)
               1 --- Cluster Head (C_HEAD)





Jiang, Li, Tay                                                  [Page 6]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   The IP addresses of the neighbors and the L and R bits are taken from
   the neighbor table.  The ID of the sender is specified in the source
   field of 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; if not, it
          adds one entry for 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

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


     2.   If B is 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 in the Role field of B's entry.