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

在ns2中实现了cbrp协议

        Num1                   the number of Gateway Node Address
                               & Adjacent Cluster Address pairs
        Num2                   the number of Cluster Addresses
        Identification         a 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 fills the Neighboring
   Cluster Head entries with its host cluster head(s) and adjacent clus-
   ter head entries(from CAT), the corresponding Gateway Node Address is
   either the host cluster head itself or the adjacent cluster's gateway
   node.  This initial RREQ is broadcast.









Jiang, Li, Tay                                                 [Page 14]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


     1. Whenever a member node M receives an RREQ,
        if D is its neighbor, RREQ is just uni-cast to 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 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:












Jiang, Li, Tay                                                 [Page 15]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


         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.



Jiang, Li, Tay                                                 [Page 16]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   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:














Jiang, Li, Tay                                                 [Page 17]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


         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



Jiang, Li, Tay                                                 [Page 18]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   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



Jiang, Li, Tay                                                 [Page 19]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   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



Jiang, Li, Tay                                                 [Page 20]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   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.