[Search] [pdf|bibtex] [Tracker] [WG] [Email] [Nits]

Versions: 00 01 02 03 04                                                
INTERNET-DRAFT                       Zygmunt J. Haas, Cornell University
                                    Marc R. Pearlman, Cornell University
Expires in six months                                      November 1997

               The Zone Routing Protocol (ZRP) for Ad Hoc Networks
                  <draft-zone-routing-protocol-00.txt>

Status of this Memo

   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
   (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East
   Coast), or ftp.isi.edu (US West Coast).

   Distribution of this memo is unlimited.

Abstract

   This document describes a routing protocol for ad hoc networks.
   In particular, it is suitable for highly versatile networks,
   characterized by large range of nodal mobilities and large network
   diameters. The protocol is a hybrid of a proactive and a reactive
   schemes, allowing adjustment of its operation to the current
   network operational conditions.

1. Introduction

   One of the major challenges in designing a routing protocol for the
   ad hoc networks stems from the fact that, on one hand, to determine
   a packet route, at least the reachability information  of the source
   neighbors needs to be known to the source node. On the other hand,
   in an ad hoc network, the network topology can change quite often.
   Furthermore, as the number of network nodes can be large, the
   potential number of destinations is also large, requiring large and
   frequent exchange of data (e.g., routes, routes updates, or routing
   tables) among the network nodes. Thus, the amount of update traffic
   can be quite high. This is in contradiction with the fact that all
   updates in a wirelessly interconnected ad hoc network travel over
   the air and, thus, are costly in resources.


Haas, Pearlman             Expires May 1998                     [Page 1]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

   In general, the existing routing protocols can be classified either
   as proactive or as reactive. Proactive protocols attempt to
   continuously evaluate the routes within the network, so that when
   a packet needs to be forwarded, the route is already known and can
   be immediately used. The family of Distance-Vector protocols is an
   example of a proactive scheme. Reactive protocols, on the other
   hand, invoke a route determination procedure on demand only. Thus,
   when a route is needed, some sort of global search procedure is
   employed. The family of classical flooding algorithms belong to the
   reactive group. Some examples of reactive (also called on-demand)
   ad hoc network routing protocols are [Johnson] and [TORA].

   The advantage of the proactive schemes is that, once a route is
   needed, there is little delay until the route is determined. In
   reactive protocols, because route information may not be available
   at the time a datagram is received, the delay to determine a route
   can be quite significant. Furthermore, the global search procedure
   of the reactive protocols requires significant control traffic.
   Because of this long delay and excessive control traffic, pure
   reactive routing protocols may not be applicable to real-time
   communication. However, pure proactive schemes are likewise not
   appropriate for the ad hoc networking environment, as they
   continuously use a large portion of the network capacity to keep the
   routing information current. Since nodes in an ad hoc networks move
   quite fast, and as the changes may be more frequent than the route
   requests, most of this routing information is never even used! This
   results again in an excessive waste of the wireless network
   capacity. What is needed is a protocol that, on one hand, initiates
   the route-determination procedure on-demand, but at limited search
   cost. The presented-here protocol, termed the "Zone Routing Protocol
   (ZRP)," is an example of a hybrid reactive/proactive routing
   protocol.

   The ZRP, on one hand, limits the scope of the proactive procedure
   only to the node's local neighborhood. On the other hand, the search
   throughout the network, although global in nature, is done by
   efficiently querying selected nodes in the network, as opposed to
   querying all the network nodes.

   A related issue is that of updates in the network topology. For a
   routing protocol to be efficient, changes in the network topology
   have to have local effect only. In other words, creation of a new
   link at one end of the network is an important local event but, most
   probably, not a significant piece of information at the other end of
   the network. Proactive protocols tend to distribute such topological
   changes widely in the network, incurring large costs. The ZRP limits
   propagation of such information to the neighborhood of the change
   only, thus limiting the cost of topological updates.

Haas, Pearlman             Expires May 1998                     [Page 2]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

2.0 The Notion of Routing Zone, Zone Radius, and Bordercasting

   A routing zone is defined for each node and includes the nodes whose
   minimum distance in *hops* from the node in question is at most some
   predefined number, which is referred to as the Zone Radius. An
   example of a routing zone (for node A) of radius 2 is shown below.

          +-----------------------------------------+
          |                       +---+             |
          |            +---+      | F |             |
   +---+  |  +---+ ----| C |------+---+-----+---+   |
   | G |-----| D |     +---+                | E |   |  Zone of node A
   +---+  |  +---+       |        +---+-----+---+   |  of radius=2
          |            +---+------| B |             |
          |            | A |      +---+             |
          |            +---+                        |
          +-----------------------------------------+

   Note that in this example nodes B through E are within the routing
   zone of A. Node G is outside A's routing zone. Also note that E can
   be reached by two path from A, one with length 2 hops and one with
   length 3 hope. Since the minimum is less or equal than 2, E is within
   A's routing zone.

   Peripheral nodes are nodes whose minimum distance to the node in
   question is equal exactly to the zone radius. Thus, in the above
   figure, nodes D, F, and E are A's peripheral nodes.

   Bordercasting is a process of sending an IP datagram ([RFC-0791]) by
   a node to all its peripheral nodes. Bordercasting can be implemented
   either through regular IP unicast or through IP multicast (Distance
   Vector Multicast Routing Protocol [RFC-1075]). Of course, the
   multicasting approach is preferred to reduce the amount of traffic
   over the air.

2.1 The Zone Routing Protocol (ZRP) ([Haas-1],[Haas-2])

   The ZRP is based on two procedures: the IntrAzone Routing Protocol
   (IARP) and the IntErzone Routing Protocol (IERP). Through the use
   of the IARP, each node learns the identity of and the (minimal)
   distance to all the nodes in its routing zone. The actual IARP is
   not specified and can include any number of protocols, such as the
   derivatives of Distance Vector Protocol (e.g., Ad Hoc On-Demand
   Distance Vector [AODV], Shortest Path First (e.g., OSPF
   [RFC-2178]), [Murthy]). In fact, different portions of an ad hoc
   network may choose to operate based on different choice of the IARP
   protocol. Whatever the choice of IARP is, the protocol needs to be
   modify to ensure that the scope of this operation is restricted to
   the zone of the node in question.

   Note that as each node needs to learn the distances to the nodes
   within its zone only, the nodes are updated about topological

Haas, Pearlman             Expires May 1998                     [Page 3]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

   changes only within their routing zone. Consequently, in spite of
   the fact that a network can be quite large, the updates are only
   locally propagated.

2.2 The Interzone Routing Protocol (IERP)

   While IARP finds routes within a zone, IERP is responsible for
   finding routes between nodes located at distances larger than the
   zone radius. IERP relies on bordercasting. Bordercasting is possible
   as any node knows the identity and the distance to all the nodes in
   its routing zone by the virtue of the IARP protocol.

   The IERP operates as follows: The source node first checks whether
   the destination is within its routing zone. (Again, this is possible
   as every node knows the content of its zone). If so, the path to the
   destination is known and no further route discovery processing is
   required. If, on the other hand, the destination is not within the
   source's routing zone, the source bordercasts a route request
   (referred to here as a "request") to all its peripheral nodes. Now,
   in turn, all the peripheral nodes execute the same algorithm: check
   whether the destination is within their zone. If so, a route reply
   (referred to here as a "reply") is sent back to the source
   indicating the route to the destination. If not, the peripheral node
   forwards the query to its peripheral nodes, which, in turn, execute
   the same procedure. An example of this Route Discovery procedure is
   demonstrated in the figure below. As we be shown, Thus, a route
   within a network is specified as a sequence of nodes, separated by
   approximately the zone radius.


                              +---+
                     +---+    | F |
             +---+---| C |----+---+-----+---+    +---+
             | D |   +---+              | E |----| H |
             +---+     |      +---+-----+---+    +---+
                     +---+----| B |                |
                     | A |    +---+-----+---+    +---+
                     +---+              | G |    | I |
                                        +---+    +---+
                                          |
                                        +---+
                               +---+    | J |
                               | C |----+---+----+---+    +---+
                               +---+             | K |----| L |
                                                 +---+    +---+

   The node A has a datagram to node L. Assume routing zone radius of
   2. Since L is not in A's routing zone (which includes B,C,D,E,F,G),
   A bordercast a routing request to its peripheral nodes: D,F,E, and
   G. Each one of these peripheral nodes check whether L exists in their
   routing zones. Since L is not found in any routing zones of these

Haas, Pearlman             Expires May 1998                     [Page 4]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

   nodes, the nodes bordercast the request to their peripheral nodes.
   In particular, G bordercasts to K, which realizes that L is in its
   routing zone and returns the requested route (L-K-G-A) to the query
   source, namely A.

2.3 Route Accumulation procedure

   The process by which the node receiving a query knows the path back
   to the source of the query is the Route Accumulation procedure. In
   particular, the Route Accumulation procedure is used to return the
   route to the source of the query by the "last peripheral node" in
   which routing zone the destination resides. The Route Accumulation
   procedure is based on each node that forwards a query writing into
   the query packet its identification. The sequence of these
   identifications represents a path from the source node to the
   current node, and, by reversing the order, a path from the current
   node to the source node.

2.4 Terminating the IERP flood

   It is desirable for route requests to propagate away from the source
   and not to loop-back into a previously queried routing zone. To
   encourage this directed spread of route requests, IERP employs two
   loop-back prevention mechanisms. The first mechansim terminates
   threads which loop-back on themselves. Such threads are terminated
   when the accumulated route (excluding the previous hop) contains a
   host which lies within its routing zone. A separate mechanism, based
   on packet eavesdropping, is employed to reduce the overlapping of
   parallel threads. When a host receives a route request, the IERP
   records the request ID in its Processed Request List.* If a node
   "officially" receives a request that has been previously recorded,
   the new copy is discarded. Without these measures, the bordercast
   transmission can actually generate more overhead than flooding.

   * ICMP provides a service similar to IERP's route failure
     notification. However, the IERP service provides additional
     diagnostic information, allowing the source to respond to the
     route failure more effectively.

2.5 Route failures notifications

   The IERP also provides a mechanism to reactively respond to route
   failures. A route failure is detected by the IP when the next hop in
   a source route is determined to be unreachable (i.e., does not
   appear in the Intrazone Routing Table). Upon detection of a route
   failure, the IERP is alerted, and a route failure packet is
   generated.** The route failure packet propagates back to the route's
   source in the same manner as a route reply. When the route's source
   receives notification of the route failure, the expired route is
   removed from its Interzone Routing Table. The IERP may also be
   configured to locally repair the damaged Interzone route by

Haas, Pearlman             Expires May 1998                     [Page 5]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

   initiating a route discovery to the unreachable next hop.

   ** Eavesdropping nodes are only permitted to listen to route requests
      (and record them in their Processed Request List); they are
      prohibited from processing the request any further.

2.6 Bordercast Resolution Protocol (BRP)

   The Bordercast Resolution Protocol (BRP) is included with the IERP in
   order to provide bordercasting services which do not exist in IP. In
   the current version of the BRP, the content of a bordercast message
   is considered to be accessible to any host which receives the
   message.***  Future versions of the BRP may allow for semi-private
   bordercasting, where bordercast messages are only delivered to the
   higher layers of the bordercast destinations (peripheral nodes).

   *** When the BRP delivers the message to the next higher layer, a
       flag is set to indicate whether the packet was overheard or
       received at its intended destination. Note that this does not
       restrict access to the message; it only serves to provide the
       access control status of the message.

3.0 The ZRP Architecture

               .........................................
               :                 ZRP                   :
               :                                       :
+---------+    :    +---------+         +---------+    :    +---------+
|   NDM   |~~~~:~~~>|  IARP   |~~~~~~~~>|  IERP   |<~~~:~~~~|  ICMP   |
+---------+    :    +---------+         +---------+    :    +---------+
    /|\        :        /|\             |   BRP   |    :        /|\
     |         :         |              +---------+    :         |
     |         :         |                  /|\        :         |
     |         :.......................................:         |
     |                   |                   |                   |
    \|/                 \|/                 \|/                 \|/
+---------+---------+---------+---------+---------+---------+---------+
|                               IP                                    |
+---------+---------+---------+---------+---------+---------+---------+

Legend:

        A<--->B      exchange of packets between protocols A & B
        A~~~~>B      information passed from protocol A to protocol B

        Existing Protocols
        ------------------
                IP              Internet Protocol
                ICMP            Internet Control Message Protocol



Haas, Pearlman             Expires May 1998                     [Page 6]


INTERNET DRAFT          The Zone Routing Protocol          November 1997


        ZRP Entities
        ------------
                IARP            IntrAzone Routing Protocol
                IERP            IntErzone Routing Protocol
                BRP             Bordercast Resolution Protocol

        Additional Protocols
        --------------------
                NDM             Neighbor Discovery/Maintenance Protocol

   Note, it is assumed that the neighbor discovery operation can be
   implemented by the MAC/link-layer protocols. Thus the NDM protocol
   remains unspecified here.

4.0 Implementation Details

4.1 The IntrAzone Routing Protocol (IARP)

   Although the IARP can be implemented through various proactive
   protocols, we present here an example of an implementation based
   on a modified version of the Distance Vector algorithm that restricts
   the of the algorithm's operation to the range of the routing zone
   radius.

   A terminal may receive new route information either from a received
   IARP packet or from an interrupt generated by its Neighbor Discovery
   / Maintenance (NDM) process$. In the special case when a host has
   discovered a neighoor, the IARP is responsible for sending the new
   neighbor the shortest route to each host which is common to both of
   their routing zones. The terminal then records the new route
   information in its Intrazone Routing Table. If the shortest path to
   the host has changed, the terminal broadcasts an IARP packet
   reflecting the change.

   $ IARP relies on the services of a separate protocol (referred to
     here as the Neighbor Discovery/Maintenance Protocol) to provide
     current information about a host's neighbors. At the least, this
     information must include the IP addresses of all the neighbors.
     The IARP can be readily configured to support supplemental
     neighbor information, such as link cost.

   A.  Packet Format
                    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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      Destination Address                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Next Hop Address                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Hop Cnt|
+-+-+-+-+

Haas, Pearlman             Expires May 1998                     [Page 7]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        Field Description:
                * Destination Address   (32 bits)
        IP address of the destination host
                * Next Hop Address      (32 bits)
        IP address of the "next hop" host to the destination host
                * Hop Count             (4 bits)
        Length of the route to the destination host, measured in hops


   B.  Structures

       B.1  Intrazone Routing Table

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           |                     Routes                          |
|           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Host    |       0       |       1       | ==> |      M-1      |
|           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           |  Next :  Hop  |  Next :  Hop  | ==> | Next  :  Hop  |
|           |  Hop  : Count |  Hop  : Count |     | Hop   : Count |
+-+-+-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-+-+-+-:-+-+-+-+
|           |       :       |       :       |     |       :       |
|-----------|-------:-------|-------:-------|-----|-------:-------|
|           |       :       |       :       |     |       :       |
|-----------|-------:-------|-------:-------|-----|-------:-------|
|           |       :       |       :       |     |       :       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   C.  Interfaces

        C.1  Higher Layer (N/A)
        C.2  Lower Layer (IP)
            C.1.1  Send()       (specified in IP standard)
            C.1.2  Deliver()    (specified in IP standard)
        C.3  NDM
            C.3.1  Neighbor_Lost(host)
                Used by the NDM to notify the IARP that direct contact
                has been lost with "host".
            C.3.2  Neighbor_Found(host)
                Used by the NDM to notify the IARP that direct contact
                has been confirmed with "host".
        C.4  IERP
            C.4.1  Host_Lost(host)
                Used by IARP to notify the IERP that a host no longer
                exists within the routing zone.

   D.  State Machine

        The IARP protocol consists of only one state (IDLE). Therefore,
        no state transitions need to be specified. The IARP immediately
        acts upon an event and then returns back to the IDLE state.

Haas, Pearlman             Expires May 1998                     [Page 8]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        Notes:  1) X is used as a label for the host running this state
                   machine.
                2) INF is a reserved field value corresponding to
                   "infinity".

        D.1
            Event:   An IARP packet is received containing route
                     information to a destination D. The hop count
                     associated with the received route is LESS THAN
                     the routing zone radius.

            Action:  The received route is recorded in the Intrazone
                     Routing Table. If the received route is shorter
                     than the previous shortest route to D, then a new
                     IARP packet containing route information to D
                     through X is broadcasted.

        D.2
            Event:   An IARP packet is received containing route
                     information to a destination D. The hop count is
                     EQUAL TO the routing zone radius.

            Action:  The received route is recorded in the Intrazone
                     Routing Table.

        D.3
            Event:   An IARP packet is received containing route
                     information to a destination D. The hop count is
                     equal to INF.

            Action:  The route to D is removed from the Intrazone
                     Routing Table.
                        1) If the Intrazone Routing Table still
                        contains a route to D and the length of the
                        shortest route has increased due to the route
                        removal, then the an IARP packet containing the
                        shortest route to D through X is broadcasted.
                        2) If the Intrazone Routing Table contains no
                        more routes to D, then an IARP packet containing
                        a route to D through X with hop count of INF is
                        broadcast.  A "Host Lost" interrupt is
                        generated to alert the IERP that D has moved
                        beyond the routing zone.

        D.4
            Event:   A "Neighbor Found" interrupt is received,
                     indicating the discovery of a neighbor host N.

            Action:  For each destination in X's Intrazone Routing
                     Table, an IARP packet is sent to N containing the
                     best route to that destination. An IARP packet is
                     then broadcasted containing the 1 hop route to N
                     through X.

Haas, Pearlman             Expires May 1998                     [Page 9]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        D.5
            Event:   A "Neighbor Lost" interrupt is received, indicating
                     that host N is no longer a neighbor of X

            Action:  The one hop route to N is removed from the
                     Intrazone Routing Table.
                        1) If the Intrazone Routing Table still
                        contains a route to N and the length of the
                        shortest route has increased due to the route
                        removal, then the an IARP packet containing the
                        shortest route to N through X is broadcasted.
                        2) If the Intrazone Routing Table contains no
                        more routes to N, then an IARP packet containing
                        a route to D through X with hop count of INF is
                        broadcast. A "Host Lost" interrupt is generated
                        to alert the IERP that D has moved beyond the
                        routing zone.

    E.  Pseudocode Implementation

        E.1  Update Intrazone Routing Table

            if (packet arrived)
              {host, route->next_hop,route->hop_count} <-- packet
            else
            {
              {host} <-- intrpt
              route->next_hop=host
              if (type(intrpt) == "Neighbor Found")
              {
                for recorded_host = each host in Intrazone_Routing_Table
                {
                  best_route = Intrazone_Routing_Table[recorded_host,0]
                  if (best_route->hop_count <  ROUTING_ZONE_RADIUS)
                  {
                    packet <-- {recorded_host,my_id,hop_count+1}
                    send(packet,host)
                  }
                }
                route->hop_count=1
              }
              else
                route->hop_count=INF
            }


Haas, Pearlman             Expires May 1998                    [Page 10]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

            former_best_route = Intrazone_Routing_Table[host,0]
            if (route->hop_count < INF)
              add(Intrazone_Routing_Table[host], route)
            else
              remove(Intrazone_Routing_Table[host],route)
            best_route = Intrazone_Routing_Table[host,0]
            if (best_route != NULL)
            {
              if (best_route->hop_count != former_best_route->hop_count
                    && best_route->hop_count < ROUTING_ZONE_RADIUS)
              {
                packet <-- {host, my_id, best_route->hop_count+1}
                broadcast(packet)
              }
            }
            else
            {
              force_intrpt("IERP","Host Lost",{host})
              packet <-- {host, my_id, INF}
              broadcast(packet)
            }

4.2 IntErzone Routing Protocol (IERP)

   The Interzone Routing Protocol (IERP) is responsible for discovering
   routes to hosts which are beyond a terminal's routing zone. The IERP
   collects routing information reactively, through bordercasted queries
   which contain the accumulated routes from the source.

   When IP receives a data packet intended for an unknown destination
   (i.e., destination is not recorded in either the Intrazone or
   Interzone Routing Tables), the IERP is interrupted. The IERP responds
   by initiating a route discovery and bordercasting a route query. Each
   query in the network is uniquely identified by the IP address of the
   source and a request ID (local to the source).

   Upon receipt of a route request packet, a host searches its Intrazone
   Routing Table to determine if the requested destination is within its
   routing zone. If so, the terminal responds with a route reply which
   is returned to the source along the (reversed) accumulated route. If
   the destination is not within the terminal's routing zone, the
   terminal adds its terminal ID to the accumulated route and
   bordercasts the route request.

   A.  Packet Format




Haas, Pearlman             Expires May 1998                    [Page 11]


INTERNET DRAFT          The Zone Routing Protocol          November 1997
                    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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type  |    Request ID     | Last Hop  | Hop Mrker | Max Hops  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Destination Address                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                    Hop 0 Address (Source)                     |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|                       Hop 1 Address                           |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                | |                                 |
                                | |                               source
                               \   /                              route
                                \ /                                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|   |
|                      Hop (N-1) Address                        |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--

        Field Description:

        * Type                  (4 bits)
                Identifies the type of IERP packet.  The current version
                 of IERP contains three packet types:
                        REQUEST:  request an Interzone source route to
                                  the destination host specified in
                                  Destination Address
                        REPLY:    response to a request packet;                                           includes the source route to the
                                  destination host specified in
                                  Destination Address
                        FAILURE:  control message sent a host indicating
                                  that the received data packet contains
                                  an invalid source route.

        * Request ID            (10 bits)
                Sequence number which, along with the Source Address
                (see below) uniquely identifies any route query in the
                network. (used only for REQUEST packets)

        * Last Hop              (6 bits)
                Indicates the previous recipient of the IERP packet
                (referenced as an index into the Source Route (see
                below))

        * Hop Marker            (6 bits)
                Currently used to indicate the hop where a route failure
                was detected (referenced as an index into the Source
                Route (see below)) (used only for FAILURE packets)



Haas, Pearlman             Expires May 1998                    [Page 12]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        * Max Hops              (6 bits)
                Maximum number of Interzone hops which a route query may
                propagate. This field allows nodes to adaptively
                configure the depth of a route search in order to
                control the amount of IERP traffic generated. (used only
                for REQUEST packets)

        * Destination Address   (32 bits)
                IP address of the destination host

        * Source Route          (N*32 bits)
                Variable length field which contains the IP addresses of
                an N hop source route.  The first subfield of the Source
                Route contains the IP address of the route's source.
                In general, the n-th subfield contains the IP address of
                the n-th hop in the route.
                For REQUEST packets, the Source Route represents the
                incomplete accumulated route to the destination host
                (as indicated by the Destination Address)
                For REPLY and FAILURE packets, the Source Route contains
                the complete route from the source host to the
                destination host.

    B.  Structures

        B.1     Intrazone Routing Table (See IARP Description)

        B.2     Interzone Routing Table

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         |                Routes                   |
    +  Dest   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         |     0     |     1     | ==> |    M-|    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         |           |           | ==> |           |
    |---------|-----------|-----------|-----|-----------|
    |         |           |           | ==> |           |
    |---------|-----------|-----------|-----|-----------|
    |         |    | |    |           | ==> |           |
    +-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                   | |
                  \   /
                   \ /
                +-+-+-+-+   +-+-+-+-+          +-+-+-+-+
                |   0   |==>|   1   |==> ...==>|  N-1  |        source
                +-+-+-+-+   +-+-+-+-+          +-+-+-+-+        route
                  source      first              (N-1)
                   host        hop                hop


Haas, Pearlman             Expires May 1998                    [Page 13]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        B.3     Processed Request List

        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |   Source  |   Request ID  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |           |               |
        |-----------|---------------|
        |           |               |
        |-----------|---------------|
        |           |               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    C.  Interfaces

        C.1  Higher Layer (N/A)
        C.2  Lower Layer (BRP)
            C.2.1  Send()       (same interface as IP send())
                Used by the IERP to request transmission of a data
                packet.
            C.2.2  Deliver()    (same interface as IP deliver())
                Used by the BRP to alert the IERP  of the arrival of a
                data packet.
        C.3  IARP
            C.3.1  Neighbor_Lost(host)
                Used by the NDM to notify the IARP that direct contact
                has been lost with "host".
            C.3.2  Neighbor_Found(host)
                Used by the NDM to notify the IARP that direct contact
                has been confirmed with "host".
        C.4  ICMP
            C.4.1  Host_Unreachable()   (specified in ICMP standard)
            C.4.2  Source_Route_Failed() (specified in ICMP standard)

    D.  State Machine

        The IERP protocol consists of only one state (IDLE). Therefore,
        no state transitions need to be specified. The IERP immediately
        acts upon an event and then returns back to the IDLE state.

        Note:  1) X is used as a label for the host running this state
        machine.

        D.1
            Event:   A "Host Lost" interrupt is received, indicating
                     that the host H has moved beyond the routing zone.

            Action:  Remove every route from the Interzone Routing Table
                     which contains H. A limited depth route discovery
                     to H is initiated. An IERP request packet is
                     created with the destination addresss set to H and
                     the source route initialized with the IP address
                     of X.  The request packet is then bordercasted.

Haas, Pearlman             Expires May 1998                    [Page 14]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        D.2
            Event:   A "Host Unreachable" interrupt is received from the
                     ICMP, indicating an unknown destination host D.

            Action:  A full depth route discovery to the lost host is
                     initiated. An IERP request packet is created with
                     the destination addresss set to H and the source
                     route initialized with the IP address of X. The
                     request packet is then bordercasted.

        D.3
            Event:   An "Source Route Failed" interrupt is received from
                     the ICMP, indicating that the next hop specified in
                     an IP source route does not appear within the
                     routing zone.

            Action:  A route failure packet containing the invalid route
                     is sent to the route's source with the hop marker
                     indicating X as the host where a route failure was
                     detected.

        D.4
            Event:   An IERP request packet is received with a
                     destination that appears within X's routing zone.

            Action:  The request is recorded in the Processed Request
                     List. In order to be processed further, four
                     conditions must be satisfied. First, the received
                     packet must not be flagged as overheard. Second,
                     the number of hops in the route must not exceed the
                     maximum hop count.  Third, the request must not
                     have been  previously recorded. Finally, no hops in
                     the route (except the last_hop) may lie within X's
                     routing zone. X appends its IP address to the route
                     and sends an IERP reply packet to the preceding hop
                     in the route.

        D.5
            Event:   An IERP request packet is received with a
                     destination that DOES NOT appear within X's routing
                     zone.

            Action:  The request is recorded in the Processed Request
                     List. In order to be processed further, four
                     conditions must be satisfied. First, the received
                     packet must not be flagged as overheard.  Second,
                     the number of hops in the route must not exceed the
                     maximum hop count. Third, the request must not have
                     been previously recorded. Finally, no hops in the
                     route (except the last_hop) may lie within X's
                     routing zone. X appends its IP address to the route
                     and is bordercasts an IERP request packet
                     containing the updated route.

Haas, Pearlman             Expires May 1998                    [Page 15]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        D.6
            Event:   An IERP reply packet is received containing X as
                     the source host.

            Action:  The received source route is recorded in Interzone
                     Routing Table.

        D.7
            Event:   An IERP reply packet is received containing a node
                     other than X as the source host.

            Action:  The route reply packet is fowarded to the preceding
                     hop in the route

        D.8
            Event:   An IERP failure packet is received containing X as
                     the source host.

            Action:  X removes all routes from its Interzone Routing
                     table which contain the broken link specified by
                     the bad hop field.

        D.9
            Event:   An IERP failure packet is received containing a
                     node other than X as the source host.

            Action:  X fowards the route reply packet to the preceding
                     hop in the route


    E.  Pseudocode Implementation

        E.1 Intrazone Node Lost

            {lost_host} <-- intrpt
            for host = each host in Interzone Routing Table
            {
              m=0
              while (Interzone_Routing_Table[host,m] != NULL)
              {
                route=Interzone_Routing_Table[host,m]
                if (lost_host (EXISTS IN) route)
                  remove(Interzone_Routing_Table[host,m])
                else
                  m++
              }
            }
            force_intrpt("IERP","repair",{lost_host})



Haas, Pearlman             Expires May 1998                    [Page 16]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        E.2  Initiate Route Discovery

            {dest} <-- intrpt
            req_id++
            route(0)=my_id
            last_hop=0
            if (type(intrpt) == "repair")
              max_hops=MAX_REPAIR_HOPS
            else
              max_hops=MAX_REQUEST_HOPS
            packet <-- {REQUEST, req_id, last_hop, NULL, max_hops, dest,
                                                                  route}
            bordercast(packet)
            add (Processed_Request_List, {my_id, req_id})

        E.3  Report Route Failure

            {route,dest} <-- intrpt
            last_hop=0
            while (route(last_hop) != my_id)
              last_hop++
            packet <-- {FAILURE, NULL, last_hop, last_hop, NULL, dest,
                                                                  route}
            send(packet, route(last_hop-1))

        E.4  Receive IERP Packet

            {pk_type, req_id, last_hop, bad_hop, max_hops, route} <--
                                                                  packet
            {overheard} <-- intrpt
            switch(pk_type)
            {
              case:  REQUEST
                add({Processed_Request_List, source, req_id)
                LSP1_terminate = FALSE
                n=0
                while (!LSP1_terminate && n < last_hop)
                {
                  if (Intrazone_Routing_Table[route(n)]!=NULL)
                    LSP1_terminate = TRUE
                  n++
                }
                LSP2_terminate = (Processed_Request_List[source,req_id]
                                                                != NULL)
                if (!overheard && !LSP1_terminate && !LSP2_terminate &&
                    last_hop < max_hops)
                {
                  last_hop++
                  route(last_hop)=my_id
                  if (dest (EXISTS IN) Intrazone_Routing_Table)
                  {
                    packet<--{REPLY,req_id,last_hop,bad_hop,max_hops,
                                                             dest,route}

Haas, Pearlman             Expires May 1998                    [Page 17]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

                    send(packet, route(last_hop-1))
                  }
                  else
                  {
                    packet<--{REQUEST,req_id,last_hop,bad_hop,max_hops,
                                                             dest,route}
                    bordercast(packet)
                  }
                }
                break
              case:   REPLY
              case:   FAILURE
              if (route(0) == my_id)
              {
                if (pk_type == ROUTE_REPLY)
                  add(Interzone_Routing_Table, route)
                else
                {
                  link(0)=route(bad_hop)
                  link(1)=route(bad_hop+1)
                  remove(Interzone_Routing_Table,link)
                }
              }
              else
              {
                last_hop --
                packet <-- {pk_type,req_id,last_hop,bad_hop,max_hops,
                                                             dest,route}
                send(packet, route(last_hop-1))
              }
            }

4.3 Bordercast Resolution Protocol (BRP)

   The higher layer interface of the BRP is designed to be compatible
   with any IP based application. However, it is assumed that the
   routing zone hierarchy is visible only to the ZRP entities, making
   bordercasting services only of use to the IERP.

   Upon receipt of a (IERP) packet to be bordercasted, the BRP resolves
   the bordercast address into the individual IP addresses of the
   peripheral nodes. The received packet is then encapsulated into a BRP
   packet and sent to each peripheral node (via IP broadcast
   transmission).

   When a BRP packet is delivered from IP, the (IERP) data is
   decapsulated and passed on to the higher layer. If the BRP packet
   has not reached its destination, the BRP is responsible for
   forwarding the packet to the next hop toward its destination.



Haas, Pearlman             Expires May 1998                    [Page 18]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

   A.  Packet Format

                    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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Destination Address                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                         Next Hop Address                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              Data                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        Field Description:

        * Destination Address   (32 bits)
                IP address of the destination host

        * Next Hop Address      (32 bits)
                IP address of the "next hop" host to the destination
                host

        * Data                  (variable length)
                Encapsulated data


    B.  Structures

        B.1  Intrazone Routing Table    (see IARP description)


    C.  Interfaces

        C.1  Higher Layer (ie. IERP)
            C.2.1  Send()       (same interface as IP Send() primitive)
                Used by higher layer protocol to request transmission of
                a data packet
            C.2.2  Deliver()  (same interface as IP Deliver() primitive)
                Used by the BRP to alert the higher layer protocol of
                the arrival of a data packet
        C.2  Lower Layer (IP)
            C.2.1  Send()       (specified in IP standard)
            C.2.2  Deliver()    (specified in IP standard)

    D.  State Machine

        The BRP protocol consists of only one state (IDLE).  Therefore,
        no state transitions need to be specified. The BRP immediately
        acts upon an event and then returns back to the IDLE state.

        Notes: 1) X is used as a label for the host running this state
                  machine.
               2) NULL is a reserved field value, corresponding to an
                  invalid IP address.

Haas, Pearlman             Expires May 1998                    [Page 19]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        D.1
            Event:   A packet is received from the IERP, destined for
                     the BORDERCAST address.

            Action:  The IERP packet is encapsulated in a BRP packet. A
                     copy of the BRP packet is made for each peripheral
                     host, P. (i.e., each host in X's Intrazone Routing
                     Table whose shortest route is ROUTING_ZONE_RADIUS
                     hops away from X). The packet's destination address
                     is set to the IP address of P and the next hop
                     address is set to the IP address of the next hop
                     to P (from X). Each packet is then broadcasted.

        D.2
            Event:   A packet is received from the IERP, destined for a
                     non-BORDERCAST address.

            Action:  The IERP packet is encapsulated in a BRP packet.
                     The BRP packet`s destination address and next hop
                     address fields are cleared and the BRP packet is
                     sent to the specified destination.

        D.3
            Event:   A BRP packet is received from the IP layer. The BRP
                     packet contains a next hop address EQUAL TO NULL.

            Action:  The data is decapuslated from the BRP packet and
                     delivered to the IERP, with the overhead flag set
                     to FALSE.

        D.4
            Event:   A BRP packet is received from the IP layer. The BRP
                     packet contains a valid next hop address and a
                     destination address EQUAL TO X.

            Action:  The data is decapuslated from the BRP packet and
                     delivered to the IERP, with the overhead flag set
                     to FALSE.

        D.5
            Event:   A BRP packet is received from the IP layer. The BRP
                     packet contains a valid next hop address EQUAL TO
                     X and a destination address NOT EQUAL TO X.

            Action:  The data is decapuslated from the BRP packet and
                     delivered to the IERP, with the overhead flag set
                     to TRUE. The received BRP packet is copied, the
                     next hop address field is updated by querying the
                     Intrazone Routing Table, and the new packet is
                     broadcasted.


Haas, Pearlman             Expires May 1998                    [Page 20]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

        D.6
            Event:   A BRP packet is received from the IP layer. The BRP
                     packet contains a valid next hop address NOT EQUAL
                     TO X and a destination address NOT EQUAL TO X.

            Action:  The data is decapuslated from the BRP packet and
                     delivered to the IERP, with the overhead flag set
                     to TRUE.

    E.  Pseudocode Implementation

        E.1  Receive Data Packet from IERP

            {dest} <-- intrpt
            if (dest == BORDERCAST)
            {
              for (host = each host in Intrazone_Routing_Table)
              {
                if (Intrazone_Routing_Table[host,0]->hop_count
                      ==ROUTING_ZONE_RADIUS)
                {
                  next_hop=Intrazone_Routing_Table[host,0]->next_hop
                  packet<--{host,next_hop,data_packet}
                  broadcast(packet)
                }
              }
            }
            else
            {
              packet<--{dest,NULL,data_packet}
              send(packet,dest)
            }

        E.2  Receive Packet from IP

            {dest,next_hop,data}<--packet
            overheard=FALSE
            if (next_hop != NULL)
            {
              if (next_hop == my_id)
              {
                if(dest != my_id)
                {
                  overheard=TRUE
                  next_hop = Intrazone_Routing_Table[dest,0]->next_hop
                  packet<--{dest,next_hop,data}
                  broadcast(packet)
                }
              }
              else
                overheard=TRUE

Haas, Pearlman             Expires May 1998                    [Page 21]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

            }
            deliver(IERP,data,{overheard})

5.0 Other Considerations

5.1 Sizing the Zone Radius

   The value of the zone radius determines the performance of the ZRP
   protocol. In general, highly mobile networks should set the zone
   radius to a smaller values, while in more stationary networks the
   zone radius should be larger. Similarly, in very active networks
   (frequent query requests), the zone radius should be larger, and in
   low-activity networks, the zone radius should be smaller.

   We believe that setting the size of the zone radius should be
   performed by the administration of the network, if one exists, or
   by the manufacturer, as a default value. Although some guidance can
   be given as to "optimal" value of the zone radius [Haas-3],
   additional constrains and operational conditions may affect this
   choice.

6.0 References

   [AODV]     Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing",
              MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA,
              November 3, 1997
   [Corson]   Corson, M.S., and Ephremides, A., "A Distributed Routing
              Algorithm for Mobile Wireless Networks", ACM/Baltzer
              journal on Wireless Networks, January 1995

   [Haas-1]   Haas, Z.J., "A New Routing Protocol for the Reconfigurable
              Wireless Networks", ICUPC'97, San Diego, CA, Oct. 12, 1997

   [Haas-2]   Haas, Z.J., and Pearlman, M.R., "Providing Ad-Hoc
              Connectivity with the Reconfigurable Wireless Networks",
              submitted for journal publication.

   [Haas-3]   Haas, Z.J., "Design Choices in Ad-Hoc Networking",
              in preparation.

   [Johnson]  Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing
              in Ad-Hoc Wireless Networks," in Mobile Computing,
              T. Imielinski and H. Korth, editors, Kluwer, 1996

   [Murthy]   Murthy, S., and Garcia-Luna-Aceves, J.J., "A Routing
              Protocol for Packet Radio Networks", MOBICOM'95,
              November 14-15, 1995

   [Perkins]  Perkins, C.E., and Bhagwat, P., "Highly Dynamic
              Destination-Sequenced Distance-Vector Routing (DSDV) for
              Mobile Computers, ACM SIGCOMM, vol.24, no.4, October 1994


Haas, Pearlman             Expires May 1998                    [Page 22]


INTERNET DRAFT          The Zone Routing Protocol          November 1997

   [TORA]     Macker, J., "Mobile Ad Hoc Internetworking", MILCOM'97
              panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997

   [RFC-0791] Postel, J., Editor, "Internet Protocol", STD 5, RFC 791,
              September 1981

   [RFC-1075] Waitzman, D., Partridge, C., Deering, S.E., "Distance
              Vector Multicast Routing Protocol", RFC 1075, Nov. 1, 1988

   [RFC-2178] Moy, J., "OSPF Version 2", INTERNET DRAFT STANDARD,
              RFC 2178, July 1997


Authors' Information

   Zygmunt J. Haas
   Wireless Networks Laboratory
   323 Frank Rhodes Hall
   School of Electrial Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   tel: (607) 255-3454, fax: (607) 255-9072
   Email: haas@acm.org or haas@ee.cornell.edu

   Marc R. Pearlman
   319 Frank Rhodes Hall
   School of Electrial Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   Email: pearlman@ee.cornell.edu


 The MANET Working Group contacted through its chairs:

   M. Scott Corson
   Institute for Systems Research
   University of Maryland
   College Park, MD 20742
   (301) 405-6630
   corson@isr.umd.edu

   Joseph Macker
   Information Technology Division
   Naval Research Laboratory
   Washington, DC 20375
   (202) 767-2001
   macker@itd.nrl.navy.mil



Haas, Pearlman               Expires in six months             [Page 23]