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

在ns2中实现了cbrp协议

   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




Jiang, Li, Tay                                                 [Page 21]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   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



Jiang, Li, Tay                                                 [Page 22]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


          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



Jiang, Li, Tay                                                 [Page 23]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


          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 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 protocol provide support for utilizing multi-channel,
          link-layer technologies? (if so, how?)

          Yes.  Cluster-formation algorithms could be run on different
          channels to yield different sets of clusters for each channel.
          Routing could be done independently on each of the set of
          clusters.


References



Jiang, Li, Tay                                                 [Page 24]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   [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] Park V., Corson M.S, "A Highly Adaptive Distributed Routing
       Algorithm for Mobile Wireless 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










Jiang, Li, Tay                                                 [Page 25]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


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|
                            +----------------+



Jiang, Li, Tay                                                 [Page 26]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   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:8080/cram/cbrp/

   Jiang Mingliang
   Mobile Computing Lab
   School of Computing
   National University of Singapore
   Singapore 119260
   Email: [e-mail]

   Li Jinyang
   Mobile Computing Lab
   School of Computing
   National University of Singapore
   Singapore 119260
   Email: [e-mail]

   Y.C. Tay
   Department of Mathematics
   National University of Singapore
   Singapore 119260
   Email: [e-mail]




















Jiang, Li, Tay                                                 [Page 27]