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 toJiang, 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 outJiang, 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 Considerations7.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) willJiang, 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.