INTERNET-DRAFT                                           Mingliang Jiangdraft-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 manet@itd.nrl.navy.mil 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 ofJiang, 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 hasJiang, 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 eachJiang, 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 TableJiang, 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.