[Search] [txt|pdf|bibtex] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04                                                
INTERNET-DRAFT                       Zygmunt J. Haas,  Cornell University
                                     Marc R. Pearlman, Cornell University

Expires in six months on September 2000                        March 2000

           The Zone Routing Protocol (ZRP) for Ad Hoc Networks
                  <draft-ietf-manet-zone-zrp-03.txt>

Status of this Memo

   This document is an Internet-Draft and is NOT offered in accordance
   with Section 10 of RFC2026, and the author does not provide the IETF
   with any rights other than to publish as 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."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   Distribution of this memo is unlimited.

Abstract

   This document describes the Zone Routing Protocol (ZRP), a hybrid
   routing protocol suitable for a wide variety of mobile ad-hoc
   networks, especially those with large network spans and diverse
   mobility patterns.  Each node proactively maintains routes within a
   local region (referred to as the routing zone).  Knowledge of the
   routing zone topology is leveraged by the ZRP to improve the
   efficiency of a reactive route query/reply mechanism.  The proactive
   maintenance of routing zones also helps improve the quality of
   discovered routes, by making them more robust to changes in network
   topology. The ZRP can be configured for a particular network by
   proper selection of a single parameter, the routing zone radius.














Haas, Pearlman              Expires September 2000               [Page i]


INTERNET DRAFT              The Zone Routing Protocol          March 2000

                                Contents

   Status of this Memo . . . . . . . . . . . . . . . . . . . . . .  i
   Abstract  . . . . . . . . . . . . . . . . . . . . . . . . . . .  i

   Applicability Statement . . . . . . . . . . . . . . . . . . .  iii
       A. Networking Context   . . . . . . . . . . . . . . . . .  iii
       B. Protocol Characteristics and Mechanisms  . . . . . . .  iii

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . .  1

   2.  Overview of the Zone Routing Protocol . . . . . . . . . . .  2
       2.1  Routing Zones, Extended Routing Zones,
            and the Intrazone Routing Protocol (IARP)  . . . . . .  2

       2.2  The Interzone Routing Protocol (IERP)  . . . . . . . .  3
            2.2.1  Routing Zone Based Route Discovery  . . . . . .  4
            2.2.2  Route Accumulation Procedure  . . . . . . . . .  5
            2.2.3  Query Control Mechanisms  . . . . . . . . . . .  6
            2.2.4  Route Maintenance . . . . . . . . . . . . . . .  6

   3.  The ZRP Architecture  . . . . . . . . . . . . . . . . . . .  7

   4.  Implementation Details  . . . . . . . . . . . . . . . . . .  8
       4.1  Intrazone Routing Protocol (IARP) -- Link State  . . .  8
            A.  Packet Format  . . . . . . . . . . . . . . . . . .  9
            B.  Data Structures  . . . . . . . . . . . . . . . . . 10
            C.  Interfaces . . . . . . . . . . . . . . . . . . . . 12
            D.  State Machine  . . . . . . . . . . . . . . . . . . 13
            E.  Pseudocode Implementation  . . . . . . . . . . . . 14

       4.2  Interzone Routing Protocol (IERP)  . . . . . . . . . . 18
            A.  Packet Format  . . . . . . . . . . . . . . . . . . 19
            B.  Data Structures  . . . . . . . . . . . . . . . . . 22
            C.  Interfaces . . . . . . . . . . . . . . . . . . . . 23
            D.  State Machine  . . . . . . . . . . . . . . . . . . 23
            E.  Pseudocode Implementation  . . . . . . . . . . . . 25

       4.3  Bordercast Resolution Protocol (BRP) . . . . . . . . . 30
            A.  Packet Format  . . . . . . . . . . . . . . . . . . 30
            B.  Data Structures  . . . . . . . . . . . . . . . . . 31
            C.  Interfaces . . . . . . . . . . . . . . . . . . . . 32
            D.  State Machine  . . . . . . . . . . . . . . . . . . 32
            E.  Pseudocode Implementations . . . . . . . . . . . . 34

   5.  Other Considerations  . . . . . . . . . . . . . . . . . . . 37
       5.1  Sizing the Routing Zone  . . . . . . . . . . . . . . . 37
       5.2  Hierarchical Routing and the ZRP . . . . . . . . . . . 37

   6.  References  . . . . . . . . . . . . . . . . . . . . . . . . 39

   7.  Draft Modifications . . . . . . . . . . . . . . . . . . . . 40

   Authors' Information  . . . . . . . . . . . . . . . . . . . . . 41
   MANET Contact Information . . . . . . . . . . . . . . . . . . . 41


Haas, Pearlman              Expires September 2000              [Page ii]


INTERNET DRAFT              The Zone Routing Protocol          March 2000

Applicability Statement

A.  Networking Context

    The hybrid Zone Routing Protocol (ZRP) can adapt to a wide variety of
    network scenarios by adjusting the range of the nodes' proactively
    maintained routing zones.  Large routing zones are preferred when
    demand for routes is high and/or the network consists of many slowly
    moving nodes.  In the extreme case of a network with fixed topology,
    the ideal routing zone radius would be infinitely large.  (Consider
    the purely proactive routing protocols used on the fixed Internet).
    On the other hand, smaller routing zones are appropriate in
    situations where route demand is low and/or the network consists of a
    small number of nodes that move fast relative to one another.  In the
    "worst case", a routing zone radius of one hop is best, and the ZRP
    defaults to a traditional reactive flooding protocol.

    When the ZRP is properly configured for a particular network scenario,
    it can perform at least as well as (and often better than) its purely
    proactive and reactive constituent protocols.  In situations where
    the network behavior varies across different regions, the ZRP
    performance can be fine-tuned by individual adjustment of each node's
    routing zone.

    The global reactive component of the ZRP uses the multicast based
    "bordercast" mechanism to propagate route queries throughout the
    network, rather than relying on neighbor-broadcast flooding found in
    tradtional reactive protocols.  Consequently, the ZRP provides the
    most benefit in networks where reliable neighbor broadcasting is
    either inefficient or altogether impossible.  In particular, the ZRP
    is well suited for multi-channel, multi-technology routing fabrics
    and networks operating under high load.

B.  Protocol Characteristics and Mechanisms

   * Does the protocol provide support for unidirectional links?
     (if so, how?)
        Yes.  The ZRP provides "local" support for unidirectional links.
        A unidirectional link can be used as long as the link source and
        link destination lie within each other's routing zone.

   * 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?)

        No.  The ZRP's framework supports global route discovery based
        on source routing, distributed distance vectors, or various
        combinations of both.






Haas, Pearlman              Expires September 2000             [Page iii]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   * Does the protocol require the use of periodic messaging?
     (if so, how?)

        Yes.  The ZRP proactively maintains local routing information
        (routing zones) based on periodic exchanges of neighbor
        discovery messages.

   * Does the protocol require the use of reliable or sequenced packet
     delivery? (if so, how?)

        The ZRP only assumes that link-layer (neighbor) unicasts are
        delivered reliably and in-sequence.  Reliable and sequenced
        delivery of neighbor broadcasts and IP unicasts is not
        required.

   * Does the protocol provide support for routing through a multi-
     technology routing fabric? (if so, how?)

        Yes.  It is assumed that each node's network interface is
        assigned a unique IP address.


   * Does the protocol provide support for multiple hosts per router?
     (if so, how?)

        Yes.  Multiple hosts may be associated with a router.  These
        hosts can be identified by the neighbor discovery/maintenance
        process.

        By default, it is assumed that a host's association with a router
        is not permanent.  As a result, the ZRP exchanges routing
        information for individual hosts in the same manner as routing
        information for routers.

        In cases where a router is permanently associated with a network
        (subnetwork), the ZRP supports the exchange of network
        (subnetwork) prefixes in place of all aggregated host IP
        addresses.

   * Does the protocol support the IP addressing architecture?
     (if so, how?)

        Yes.  Each node is assumed to have a unique IP address (or
        set of unique IP addresses in the case of multiple interfaces).
        The ZRP references all nodes/interfaces by their IP address.

        This version of the ZRP also supports IP network addressing
        (network prefixes) for routers that provide access to a
        network of non-router hosts.







Haas, Pearlman              Expires September 2000              [Page iv]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   * Does the protocol require link or neighbor status sensing
     (if so, how?)

        Yes.  The ZRP proactively maintains local routing information
        (routing zones) based on detected changes in neighbor status.

   * Does the protocol have dependence on a central entity?
     (if so, how?)

        No.  The ZRP is a fully distributed protocol.

   * Does the protocol function reactively? (if so, how?)

        Yes.  The ZRP's GLOBAL route discovery mechanism is reactive.
        A route query is initiated, on demand, when a node requires
        routing information that is not immediately available in its
        routing table.

        The route query propagates through the network, using a special
        packet delivery service called "bordercasting".  Bordercasting
        leverages knowledge of local network topology to direct route
        queries away from the source, thereby reducing redundancy.


   * Does the protocol function proactively? (if so, how?)

        Yes.  The ZRP proactively maintains LOCAL routing information
        (routing zones) for each node.  The routing zone information is
        leveraged, through the bordercasting mechanism, to support
        efficient global propagation of route queries.

   * Does the protocol provide loop-free routing? (if so, how?)

        Yes.  In this draft, loop-freedom in the reactive route discovery
        process is ensured by inspection of accumulated source routes.
        For distributed distance vector approaches, loop-freedom can be
        ensured by labeling queries (replies) with the source
        (destination) address and locally unique sequence number.  Nodes
        that relay these messages can temporarily cache these identifiers
        in order to identify and terminate loops.

        The ZRP's Link State proactive protocol is inherently loop-free,
        although temporary loops may form while new link state updates
        propagate through the routing zone.

   * Does the protocol provide for sleep period operation? (if so, how?)

        No.

   * Does the protocol provide some form of security? (if so, how?)

        No.  It is assumed that security issues are adequately addressed
        by the underlying protocols (IPsec, for example).

Haas, Pearlman              Expires September 2000               [Page v]


INTERNET DRAFT              The Zone Routing Protocol          March 2000

   * Does the protocol provide support for utilizing multi-channel,
     link-layer technologies? (if so, how?)

        Yes.  It is assumed that each node's network interface is
        assigned a unique IP address.



















































Haas, Pearlman              Expires September 2000              [Page vi]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


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, a node needs to known at least the reachability
   information to its neighbors.  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.

   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.  Examples of proactive routing
   protocols include the Wireless Routing Protocol (WRP) [7] and
   Destination-Sequenced Distance-Vector (DSDV) routing [11].  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 other examples of
   reactive (also called on-demand) ad hoc network routing protocols are
   Dynamic Source Routing (DSR)[5], Ad-hoc On demand Distance Vector
   Routing (AODV) [12] and the Temporally Ordered Routing Algorithm
   (TORA) [8].

   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 flood-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 in a further 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
   protocol described in this draft, termed the "Zone Routing Protocol
   (ZRP)" ([1], [2],[9]), is an example of a such a hybrid proactive/
   reactive scheme.



Haas, Pearlman              Expires September 2000               [Page 1]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   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
   should have only a local effect. 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.  Globally 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.

2. Overview of the Zone Routing Protocol

2.1 Routing Zones, Extended Routing Zones, and the
    Intrazone Routing Protocol (IARP)

   A routing zone is defined for each node X, and includes the nodes
   whose minimum distance in *hops* from X is no greater than some
   parameter 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 |   |  Routing Zone of
   +---+  |  +---+       |        +---+     +---+   |      node A
          |            +---+   ---| B |-------|     |  (radius = 2 hops)
          |            | 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 paths from A, one with length 2 hops and one with
   length 3 hops.  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.









Haas, Pearlman              Expires September 2000               [Page 2]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   An important consequence of the routing zone construction is the
   ability of a node to deliver a packet to its peripheral nodes.  This
   service, which we refer to as "bordercasting", allows for more
   efficient network-wide searching than simple neighbor broadcasting.
   Bordercasting could be implemented either through IP multicast
   (Distance Vector Multicast Routing Protocol (DVMRP) [14]) to the
   peripheral nodes.  However, as will be explained later, efficient ZRP
   operation requires that the bordercast service be handled, on a
   hop-by-hop basis, by the ZRP.

   In its basic form, the ZRP's Intrazone Routing Protocol (IARP) is
   responsible for providing each node with current view of its routing
   zone topology.  With this information, a node can identify ITS
   peripheral nodes AND construct a bordercast (multicast) tree to them.
   However, in order for the  bordercast to be carried out, member of the
   bordercast tree needs to know the tree's downstream structure.  This
   can be achieved if each node tracks the routing zone topology of each
   of ITS interior routing zone members.  This "extended" routing zone
   consists of all nodes that are at a minimum distance (in hops) LESS
   THAN twice the "basic" routing zone radius.

   The IARP may be derived from a variety of existing globally proactive
   protocols that provide a complete view of network connectivity (for
   example, the Shortest Path First OSPF [6]).  The base protocol needs
   to be modified to ensure that the scope of the route updates is
   restricted to the radius of a node's extended routing zone.  Because
   each node needs to proactively acquire route information only for the
   nodes within its zone, the total amount of IARP traffic does not
   depend on the size of the network, which may be quite large.


2.2 The Interzone Routing Protocol (IERP)

   While the IARP maintains routes within a zone, the IERP* is
   responsible for finding routes between nodes located at distances
   larger than the zone radius.  The IERP is distinguished from standard
   flood-search query/response  protocols by exploiting the routing zone
   topology.  A node is able to respond positively to any queries for its
   routing zone nodes.  For large networks, relatively few destinations
   lie within any particular node's routing zone.  In this more likely
   case, the node can efficiently continue the propagation of the query,
   through the routing zone-based bordercast delivery mechanism.

* The IERP relies on a special sub-protocol, called the Bordercast
     Resolution Protocol (BRP) to provide the bordercast message delivery
     service for route queries.  Sections 3.0 and 4.0 describe in detail
     the relationship between the BRP and the IERP.








Haas, Pearlman              Expires September 2000               [Page 3]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


2.2.1  Routing Zone Based Route Discovery

   We illustrate the basic operation of routing zone based route
   discovery through a simple (and as we will see, inefficient) IERP
   implementation.  The source node, in need of a route to a destination
   node, first checks whether the destination lies within its routing
   zone.  (This is possible since every node knows the content of its
   routing zone).  If a path to the destination is known, no further
   route discovery processing is required.  On the other hand, if the
   destination is not within the source's routing zone, the source
   bordercasts a route query to all of its peripheral nodes.  Upon
   receipt of the route query, each peripheral nodes executes the same
   algorithm.  If the destination lies within its routing zone, a route
   reply is sent back to the source, indicating the route to the
   destination.  If not, this node forwards the query to ITS peripheral
   nodes.  This process continues until the query has spread throughout
   the network.

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


   In the example illustrated above, node A has a datagram to send to
   node L.  Assuming each node's zone radius is 2 hops, node L does not
   lie within A's routing zone (which does include B,C,D,E,F,G).
   Therefore, A bordercasts a routing query 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 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.










Haas, Pearlman              Expires September 2000               [Page 4]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


2.2.2 Route Accumulation Procedure

   The query propagation mechanism allows a route query to indirectly
   reach the desired destination (through some node Y, which discovers
   the destination in its routing zone.)   To complete the route
   discovery process, Y needs to send a reply back to the query's source,
   S, providing S with the desired route.  To perform the route reply,
   sufficient information needs to be accumulated during the query phase
   so that Y is provided with a route back to S.  Providing routes from
   discovering node Y to query source S, and from the query source S back
   to the query destination D (through Y), is the role of the Route
   Accumulation procedure.

   In the basic Route Accumulation, a node appends its IP address to a
   received query packet.  The sequence of IP addresses specifies a route
   from the query's source to the current node.  By reversing this
   sequence, a route may also be obtained back to the source.  In this
   way, the route reply can be returned via strict source routing.

   In order to reduce the length of query packets and query response time,
   the query packet's accumulated route can be cached among the path's
   nodes (in the form of the previous hop toward the query source),
   rather than explicitly recorded in the packet itself.  During the
   reply phase, the cached previous hops can direct the reply back to the
   source.  Along the way, information can be accumulated in the reply
   packet, forming a source route.  Alternatively, the discovered route
   may be distributed among its nodes' routing tables, providing a next
   hop routing solution.

   Sending replies along the (reversed) paths explicitly traveled by the
   successful query packets can result in a set of discovered routes that
   exhibit limited diversity among.  This anomalous behavior can be
   explained as follows.  Variations in packet forwarding delay often
   result in one query packet reaching the destination region ahead of
   others.  The descendents of this query packet trigger the majority of
   route replies.  The route diversity problem is aggravated when all
   possible paths between the source and destination pass through a
   common node, called a topological bottleneck.  Since only one query
   packet passes through the bottleneck, all discovered routes will be
   identical prior to the topological bottleneck.

   This problem could be addressed by allowing a node to relay a route
   query more than once. Alternatively, we can apply "diversity
   injection" [10] to increase diversity without generating additional
   route replies.  During the route query stage, nodes temporarily cache
   the previous hop information for ALL received query packets (including
   the packets that are discarded).  Later, during the reply phase,
   replies are relayed through the shortest of the least selected cached
   paths that does not produce a routing loop.






Haas, Pearlman              Expires September 2000               [Page 5]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


2.2.3 Query Control Mechanisms

   Bordercasting has the potential to support global querying schemes
   that are more efficient than flooding.  To achieve this efficiency,
   the protocol should be able to terminate a bordercasted packet before
   it arrives at a recipient peripheral node lying in a previously
   queried region of the network.  The ZRP's ability to provide this
   level of query control capability is significantly limited when
   bordercast messages are forwarded to peripheral nodes by IP.

   To prevent redundant querying, nodes should be able to detect when
   routing zones that they belong to have been queried.  Clearly, a node
   that bordercasts a route query is aware that its own zone has been
   queried.  If bordercast messages are relayed by IP, then the query
   will not be detected again until it reappears at the target peripheral
   nodes.  On the other hand, if bordercast forwarding is performed
   within the routing protocol, then all nodes in the bordercast tree
   will detect the query.  Additional query detection is possible in
   shared channel networks if the underlying IP delivery is neighbor
   broadcast or if promiscuous mode operation is enabled.  In this case,
   nodes may "overhear" a query even if they do not belong to the
   bordercast tree.

   Standard flood search protocols terminate query packets that are
   targeted for (or arrive at) previously queried nodes.  We can extend
   this idea to the ZRP by discarding route queries before they arrive at
   bordercast recipients that belong to a previously queried routing
   zone.  More precisely, a node will not relay a packet down a branch of
   the bordercast tree if each of the branch's downstream "leaves"
   (bordercast recipients) either lies inside the routing zone of a
   previous bordercasted nodes, or if this node has already relayed the
   query to that leaf.  This scheme, which we refer to as Early
   Termination (ET), relies on the aforementioned Query Detection to
   identify which routing zone nodes have already bordercast a query.
   The "extended" routing zone maintained by the IARP is then used to
   determine the members of these previously bordercasted nodes' routing
   zones.


2.2.4 Route Maintenance

   In addition to initially discovering routes, the IERP may also assume
   responsibility for monitoring the integrity of these routes and
   repairing failed routes as appropriate.

   Route failures can be detected either proactively or reactively.
   Proactive route failure detection is triggered by the IARP, in
   response to a node leaving the routing zone.  Any IERP routes
   containing this node as the first hop can be considered invalid.
   Route failures may also be detected reactively, by IP, when the next
   hop in a datagram's source route is determined to be unreachable
   (i.e. does not appear in the Routing Table).



Haas, Pearlman              Expires September 2000               [Page 6]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   Upon local detection of a route failure, a node may choose to attempt
   a route repair by discovering a path to bypass the failed link.  The
   repair discovery process is nearly identical to an initial route
   discovery.  Route repairs should not be substantially longer than the
   original failed connection.  Therefore, the depth of a repair query
   can be limited, through the use of a "time to live" field.  This has
   the advantage of producing much less query traffic than an
   unrestricted initial route query.  After a successful repair, the
   route's source MAY be notified so that routes are properly selected
   for use.  Alternatively, the repair could go unreported without
   compromising the connectivity between source and destination.


3.0 The ZRP Architecture

             .........................................
             :                 Z R P                 :
             :                                       :
+---------+  :      +---------+         +---------+  :      +---------+
|   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

        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 basic neighbor discovery operation is
   implemented by the MAC/link-layer protocols. Thus the NDM protocol
   remains unspecified here.

Haas, Pearlman              Expires September 2000               [Page 7]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


4. Implementation Details

4.1 The IntrAzone Routing Protocol (IARP)  -- Link State Implementation

    The Intrazone Routing Protocol (IARP) is responsible for proactively
    maintaining routes within each node's routing zone.  Many traditional
    proactive protocols can be modified to serve as an IARP by limiting
    the range of route updates to the boundary of (extended) routing
    zones.

    In this draft, we detail implementations for a Link-State IARP.
    Nodes compute intrazone routes based on the link state (neighbor
    connectivity) of each extended routing zone node.  A node may receive
    link state updates either from an IARP link state packet or from an
    interrupt generated by its Neighbor Discovery / Maintenance (NDM)
    process*.  Link states are maintained in a Link State Table.  When
    all pending link state updates have been received (full link state
    updates may contain multiple links and span multiple packets), the
    routing table is recomputed, using a minimum spanning tree algorithm.
    The Link State Table is then updated to remove links that lie outside
    of the extended routing zone.  All new link state updates for non-
    peripheral routing zone nodes are forwarded to all neighbors.  In
    addition, if a new neighbor is discovered, the new neighbor is sent
    the FULL link states of all non-peripheral routing zone nodes.

    In addition to computing routes to all nodes in the extended routing
    zone, the IARP also uses the extended zone topology to construct
    the bordercast tree of each routing zone member.  A node's bordercast
    tree can be constructed by first determining the minimum spanning
    tree for its routing zone, and then pruning interior node leaves.
    For each bordercast tree, the node should record if it's a member,
    and if so, its downstream neighbors and peripheral nodes.

   * the IARP relies on the services of a separate protocol (referred to
     here as the Neighbor Discovery/Maintenance Protocol) to provide
     current information about a node'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 link
     quality metrics.
















Haas, Pearlman              Expires September 2000               [Page 8]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Link Source Address                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Link Destination Address                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Packet Source Address                     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Link State ID         |  Zone Radius  |     Flags     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Link Destination Subnet Mask  (Optional)           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
   |   RESERVED    |  Metric Type  |          Metric Value         |   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
   |   RESERVED    |  Metric Type  |          Metric Value         |   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                  | |                                 Link
                                 \| |/                              Metrics
                                  \ /                                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
   |   RESERVED    |  Metric Type  |          Metric Value         |   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--

        Field Description:

        * Link Source Address          (node_id)           (32 bits)
            IP address of the reported link's source node.

        * Link Destination Address     (node_id)           (32 bits)
            IP address of the reported link's destination node.

        * Packet Source Address        (node_id)           (32 bits)
            IP address of the node that sent this packet.
            (Used to account for any outstanding link state information)

        * Link State ID                (unsigned int)      (16 bits)
            Sequence number used to track the link state history of
            the Link Source node.

        * Zone Radius                  (unsigned int)      (8 bits)
            Routing zone radius of the link's source node.  Determines
            the extent that link state information propagates.

        * Flags                        (boolean)           (8 bits)
             Flags(0)   Full Link Information
                 Indicates whether this link state information was sent
                 as:
                          (0) a PARTIAL link state update
                                      OR
                          (1) part of a FULL update  of all the
                              link source's current links

Haas, Pearlman              Expires September 2000               [Page 9]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


             Flags(1)   Current Link State Update
                 Indicates whether more link state information is pending
                 for THIS link state update {link_source,state_id}
                          (0) INCOMPLETE
                          (1) COMPLETE

             Flags(2)   All Link State Updates
                 Indicates whether more link state updates are pending
                          (0) INCOMPLETE
                          (1) COMPLETE

             Flags(3)   Link Destination Subnet Mask
                          (0) INCLUDED
                          (1) NOT INCLUDED

             Flags(4)   Link Status
                          (0) DOWN
                          (1) UP

             Flags(5..7)  RESERVED for future use.

        * Node/Link Metrics            (metric)            (X * 32 bits)
                This section of the packet is used to report the quality
                of this link (or link source node).

                * Metric Type          (char)              (8 bits)
                      Type of metric being reported
                      (based on pre-defined metric types)

                * Metric Value         (unsigned int)      (16 bits)
                      Value of node / link metric specified by Metric Type


    B.  Data Structures

    B.1  Routing Table

    +-----------------------|--------------------------------+-----------+
    |   Dest    |  Subnet   |     Routes     |     Route     | Intrazone |
    |   Addr    |   Mask    |                |    Metrics    |           |
    | (node_id) | (node_id) | (node_id list) | (metric list) | (boolean) |
    |-----------+-----------|----------------+---------------+-----------+
    |           |           |                |               |           |
    |-----------+-----------|----------------+---------------+-----------+
    |           |           |                |               |           |
    |-----------+-----------|----------------+---------------+-----------+
    |           |           |                |               |           |
    +-----------------------|--------------------------------------------+







Haas, Pearlman              Expires September 2000              [Page 10]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


     B.2  Link State Table

     +-----------|--------+-------+------------------+
     |    Link   |  Zone  | Link  |   Link State     |
     |   Source  | Radius | State |   Information #  |
     |    Addr   |        |  ID   |                  |
     | (node_id) | (int)  | (int) | (ls_info list)## |
     +-----------|--------+-------+------------------|
     |           |        |       |                  |
     |           |        |-------+------------------|
     |           |        |       |                  |
     |           |        |-------+------------------|
     |           |        |       |                  |
     |-----------|--------+-------+------------------|
     |           |        |       |                  |
     |-----------|--------+-------+------------------|
     |           |        |       |                  |
     |           |        |-------+------------------|
     |           |        |       |                  |
     +-----------|-----------------------------------+

      #  The first link state entry for each link source
         contains the complete link state information
         corresponding to the Link State ID.
         Subsequent entries contain only changes of a single
         link state.

         A FULL link state entry of link state #k and
         a PARTIAL entry of link state #(k+1) can be
         merged into a FULL link state entry of
         link state #(k+1)

      ## detail of (ls_info) data type
          +---+---|---|---+
          |   |   |||||   |
          +---+---|---|---+
           (a) (b) (c) (d)

           (a)  Link Destination Address
           (b)  Link Destination Subnet Mask
           (c)  Link Metrics
           (d)  Forward Flag ( indicates if link state information
                               has been forwarded)












Haas, Pearlman              Expires September 2000              [Page 11]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   B.3  Bordercast Tree Table

        +-----------|-----------+----------------+----------------+
        |           |           |   Downstream   |   Downstream   |
        |   Node    |   Member  |   Neighbors    |   Peripheral   |
        |           |           |                |     Nodes      |
        | (node_id) | (boolean) | (node_id list) | (node_id list) |
        +-----------|-----------+----------------+----------------|
        |           |           |                |                |
        +-----------|-----------+----------------+----------------|
        |           |           |                |                |
        +-----------|-----------+----------------+----------------|
        |           |           |                |                |
        +-----------|---------------------------------------------+


   B.4  Pending Link State List
        (list of neighbors in the process of sending link state updates)

        +----------+      +----------+        +----------+
        |          | ---> |          |  . . . |          |  (node_id list)
        +----------+      +----------+        +----------+

   B.5  New Neighbors List
        (list of new neighbors to receive a copy Link State Table,
         upon completion of updates)

        +----------+      +----------+        +----------+
        |          | ---> |          |  . . . |          |  (node_id list)
        +----------+      +----------+        +----------+

   B.6  Former Routing Zone Nodes
        (list of routing zone nodes, prior to routing table updates)

        +----------+      +----------+        +----------+
        |          | ---> |          |  . . . |          |  (node_id list)
        +----------+      +----------+        +----------+

   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)











Haas, Pearlman              Expires September 2000              [Page 12]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        C.3  NDM
            C.3.1  Neighbor_Lost(node,mask,metric)
                Used by the NDM to notify the IARP that direct contact
                has been lost with "node" (with subnet mask "mask").
                Any node/link quality measurements are reported in
                the "metric" list.
            C.3.2  Neighbor_Found(node,mask,metric)
                Used by the NDM to notify the IARP that direct contact
                has been confirmed with "node" (with subnet mask "mask").
                Any node/link quality measurements are reported in
                the "metric" list.
        C.4  IERP
            C.4.1  Zone_Node_Lost(node)
                Used by IARP to notify the IERP that a node 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.

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

        D.1
            Event:   An IARP link state packet is received.

            Action:  The link state update is recorded in the Link State
                     Table.  If more link state updates are pending,
                     then the IARP returns to an idle state.  Otherwise,
                     X rebuilds its routing table and the bordercast trees
                     of its routing zone nodes.  Links that lie outside of
                     the routing zone are removed from the Link State
                     Table.  X sends its neighbors all previously
                     unforwarded link state updates from its NON-
                     peripheral nodes.  Finally, all neighbors in the New
                     Neighbor List are sent the link states of X's NON-
                     peripheral nodes, and the New Neighbor List is
                     cleared.















Haas, Pearlman              Expires September 2000              [Page 13]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


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

            Action:  X's new link to N is recorded in the Link State Table
                     and N is added to the New Neighbors List.  If more
                     link state updates are pending, then the IARP returns
                     to an idle state.  Otherwise, X rebuilds its routing
                     table and the bordercast trees of its routing zone
                     nodes.  Links that lie outside of the routing zone
                     are removed from the Link State Table.  X sends its
                     neighbors all previously unforwarded link state
                     updates from its NON-peripheral nodes.  Finally, all
                     neighbors in the New Neighbor List are sent the link
                     states of X's NON-peripheral nodes, and the New
                     Neighbor List is cleared.

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

            Action:  The lost link to neighbor N is removed from the Link
                     State Table and N is removed from the New Neighbor
                     List.  If more link state updates are pending, then
                     the IARP returns to an idle state.  Otherwise, X
                     rebuilds its routing table and the bordercast trees
                     of its routing zone nodes.  Links that lie outside of
                     the routing zone are removed from the Link State
                     Table.  X sends its neighbors all previously
                     unforwarded link state updates from its NON-
                     peripheral nodes.  Finally, all neighbors in the New
                     Neighbor List are sent the link states of X's NON-
                     peripheral nodes, and the New Neighbor List is
                     cleared.

    E.  Pseudocode Implementation

        We define two complimentary operations on packets:
        extract(packet) and load(packet)

            extract (packet)
                extracts the fields of the IARP packet to the following
                variables: {link_source, link_dest, pk_source, state_id,
                            radius, flags, mask, link_metric}
                             * full_link_state -> flag(0)
                             * current_update  -> flag(1)
                             * all_updates     -> flag(2)
                             * mask            -> flag(3)
                             * link_status     -> flag(4)

            load (packet)
                loads the values of the aforementioned variables into
                the fields of the IARP packet.


Haas, Pearlman              Expires September 2000              [Page 14]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


    E.1  Update Intrazone Routing Table
         args:  (packet, link_dest, mask, link_metric)

         // IARP may be triggered by either a link state packet update
         // or an interrupt from the NDP

         if (packet)
         {
             extract(packet);
             my_link_changed = FALSE;
         }
         else
         {
            link_source = MY_ID;
            pk_source   = MY_ID;
            state_id    = MY_LINK_STATE_ID;
            radius      = MY_ROUTING_ZONE_RADIUS;

            full_link_state = 0;
            current_update  = COMPLETE;
            all_updates     = COMPLETE;

            if (type(intrpt) == "Neighbor Found")
                link_status = UP;
            else
               link_status = DOWN;

            my_link_changed = TRUE;
        }

        // Record link state information in Link State Table
        add(Pending_Link_State_List, pk_source_id);
        status = add(Link_State_Table, link_source, link_dest, mask,
                     radius, link_metric, state_id, flags);

        // Determine if received link state information is new
        if (status == NEW_LINK_INFO)
        {
           cum_status = UPDATE_IN_PROGRESS;
           if(my_link_changed)
           {
              if (link_status == UP)
                 add(New_Neighbor_List, link_dest);
              else
                 remove(New_Neighbor_List, link_dest);
              MY_LINK_STATE_ID++;
           }
        }

        // Release hold on pk_source when all link state information
        // from pk_source is received
        if(all_updates == COMPLETE)
            remove(Pending_Link_State_List, pk_source);


Haas, Pearlman              Expires September 2000              [Page 15]


INTERNET DRAFT              The Zone Routing Protocol          March 2000

        // Once all pending link state information has been received,
        // recompute Routing Table
        if(empty(Pending_Link_State_List) (AND)
                 cum_status == UPDATE_IN_PROGRESS)
        {
            // Record former routing zone nodes in order to determine
            // (later) which nodes have left the routing zone
            for((EACH) node (BELONGING TO) Routing_Table)
            {
               if(Routing_Table[node].Intrazone)
                   add(Former_Routing_Zone_Nodes, node);
            }

            // The Link State Table should not contain links that lie
            // beyond the (extended) routing zone.
            // The Routing Table is recomputed until all outlying links
            // have been removed from the Routing Table
            rebuild = TRUE;
            while (rebuild)
            {
                 for((EACH) node (BELONGING TO) Routing_Table)
                 {
                     if(Routing_Table[node].Intrazone)
                         delete(Routing_Table[node]);
                 }

                 for((EACH) node (BELONGING TO) Link_State_Table)
                 {
                     Routing_Table[node].route =
                           compute_route_from_links(Link_State_Table,node);
                     Routing_Table[node].Intrazone = TRUE;
                 }
                 rebuild = update(Link_State_Table);
            }

            // After recomputing the Routing Table, the bordercast trees
            // of the interior routing zone nodes are recomputed
            for ((EACH) node (BELONGING TO) Routing_Table)
            {
                if(Routing_Table[node].Intrazone)
                {
                    Bordercast_Tree[node] =
                          construct_bordercast_tree(Link_State_Table,node);
                }
            }

            // Broadcast all new link state information that lies
            // inside the extended routing zone
            broadcast_link_state_updates(Link_State_Table);

            // Send all link state information that lies inside the
            // extended routing zone to each new neighbor
            for ((EACH) node (BELONGING TO) New_Neighbor_List))
               send_link_state_table(Link_State_Table, node);


Haas, Pearlman              Expires September 2000              [Page 16]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


            clear(New_Neighbor_List);

            cum_status = UPDATE_COMPLETE;

            // Alert IERP about any lost routing zone nodes
            for ((EACH) node (BELONGING TO) Former_Routing_Zone_Nodes)
            {
               if(node !(BELONGS TO) Routing_Table)
                  Routing_Zone_Node_Lost(IERP, node);
            }
            clear(Former_Routing_Zone_Nodes);
         }











































Haas, Pearlman              Expires September 2000              [Page 17]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


4.2 IntErzone Routing Protocol (IERP)

   The Interzone Routing Protocol (IERP) is responsible for discovering
   and maintaining routes to nodes which are beyond a node's routing
   zone.  These routes are acquired, on demand, by efficiently probing the
   network with bordercasted route queries.*

   This version of the IERP extends the basic query / reply mechanism
   described in Section 3.  A node issues a ROUTE_QUERY when a route is
   needed for a destination outside of its routing zone.  A ROUTE_QUERY
   for a new route may probe the entire network.  In contrast, a route
   repair will only trigger a limited depths search.  A ROUTE_QUERY is
   guided from a node outward to its peripheral nodes, using the BRP's
   bordercast service (described in greater detail in Section 4.3).
   Because future IERP implementations may not be "routing zone aware",
   the BRP delivers the query up to the IERP at every hop.  When the
   ROUTE_QUERY is received at the IERP, the previous hop node address is
   recorded in the Routing Table and Temporary Query Cache.  The previous
   hop node address is then overwritten in the packet by the current
   node's address.  If the ROUTE_QUERY destination lies within this node's
   routing zone, then a ROUTE_REPLY is sent to the query source and a
   QUERY_EXTENSION is forwarded to the query destination.  Otherwise, the
   ROUTE_QUERY is sent back down to the BRP.

   The QUERY_EXTENSION performs route accumulation in distributed manner,
   similar to the ROUTE_QUERY.  When the QUERY_EXTENSION arrives at the
   destination, a next hop route is formed back to the query source.

   As the ROUTE_REPLY proceeds back the query source, each node selects a
   previous hop from its Temporary Query Cache (i.e. based on diversity
   injection criteria) and appends the address to the packet.  When the
   ROUTE_REPLY arrives at the query source, it contains a source route
   to the destination.

   This IERP version offers some additional features.  Multiple
   destination route discoveries (for any OR all destinations) can be
   aggregated into a single ROUTE_QUERY.  In addition, QOS routing is
   supported through the collection of various route quality metrics.

   * The bordercast service is provided by the Bordercast Resolution
     Protocol (BRP)

                       +-----+                    +-----+       +-----+
                       |  S  |      . . . .       |  Y  | . . . |  D  |
                       +-----+                    +-----+       +-----+

  (1)  search for                   ROUTE_QUERY
       route               |-------------------------->

  (2)  establish                    ROUTE_REPLY            EXTENSION
       connectivity        <--------------------------|
                                                      |=============>

              Sequence of the IERP Route Discovery Stages

Haas, Pearlman              Expires September 2000              [Page 18]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |     Type      |      TTL      |   Hop Count   |     Flags     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        Current Hop Ptr        | Num Dests = D | Num Nodes = N |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            Query ID           |           Reserved            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Query/Route Source Address                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |              Query/Route Destination (1) Address              |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |              Query/Route Destination (2) Address              |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                   | |                                  |
                                   | |                                Dests
                                  \| |/                                 |
                                   \ /                                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |              Query/Route Destination (D) Address              |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |                 Intermediate Node (1) Address                 |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |                 Intermediate Node (2) Address                 |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                   | |                                  |
                                   | |                           route(1:N)
                                  \| |/                                 |
                                   \ /                                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|   |
    |                 Intermediate Node (N) Address                 |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |     Node      | Metric Type |D|          Metric Value         |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |     Node      | Metric Type |D|          Metric Value         |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                   | |                                Node/
                                   | |                              Segment
                                  \| |/                             Metrics
                                   \ /                                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |     Node      | Metric Type |D|         Metric Value          |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--










Haas, Pearlman              Expires September 2000              [Page 19]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        Field Description:

        * Type                         (char)              (8 bits)
                Identifies the type of IERP packet.  The current version
                 of IERP contains three packet types:

                ROUTE_QUERY:
                        request for an Interzone source route to the
                        destination specified by the Destination
                        IP Address

                QUERY_EXTENSION:
                        extension of a QUERY packet sent from the
                        node that discovers the Destination to the
                        Destination itself.

                ROUTE_REPLY:
                        response to a ROUTE_QUERY packet, sent from the
                        node that discovers the Destination back to the
                        Source.  At a minimum, the ROUTE_REPLY contains
                        next-hop route information to the Destination.
                        (In general, returns the source route up to the
                        first node which has cached routing information
                        If no nodes have cached routing information, then
                        the complete source route is returned.)

        * TTL (Time to Live)           (unsigned int)      (8 bits)
                Number of hops that a route query may continue to
                propagate.  This field allows a querying node to configure
                the depth of a route search, in order to control the
                amount of IERP traffic generated.

        * Hop Count                    (unsigned int)      (8 bits)
                Hop count from source to current node (ROUTE_QUERY,
                QUERY_EXTENSION) or hop count from source to route
                destination (ROUTE_REPLY, ROUTE_ACCUMULATION,
                ROUTE_OPTIMIZATION).

        * Flags                        (boolean)           (8 bits)
                 Flags(0)        ANY destination (0) / ALL destination (1)
                        In the case of multiple destinations, specifies
                        whether the ROUTE_QUERY should return routes for
                        ANY specified destination, or ALL specified
                        destinations.

                        In the case of a single MULTICAST IP address,
                        specifies whether the ROUTE_QUERY should return
                        routes to ANY member of the multicast group, or
                        ALL members of the multicast group.

                 Flags(1..7)     RESERVED for future use




Haas, Pearlman              Expires September 2000              [Page 20]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        * Current Hop Pointer          (unsigned int)      (16 bits)
                INDEX of the route (see below) corresponding to the route
                node that has most recently received this packet.  (the
                first node in the route has an index of 1).

        * Number of Destinations = D   (unsigned int)      (8 bits)
                Number of destinations included in the route query/reply
                packet.  This allows multiple route discoveries to be
                consolidated into a common route query process.  The
                multiple query destinations feature is particularly useful
                for routing to a multicast group with known members, or
                for locating downstream nodes during the route repair
                phase.

        * Number of Nodes = N          (unsigned int)      (8 bits)
                Number of nodes IP addresses appearing in the route
                specification.

        * Query ID                     (unsigned int)      (16 bits)
                Sequence number which, along with the Query Source Address
                (see below) uniquely identifies any ROUTE_QUERY in the
                network.

        * Query/Route Source Address   (node_id)           (32 bits)
                IP address of the node that initiates the ROUTE_QUERY.
                In subsequent stages, this corresponds to the IP address
                of the discovered route's source node.

        * Query/Route Destination Addresses  (node_id)     (D * 32 bits)
                List of IP addresses to be located during the ROUTE_QUERY
                phase.  (Either ANY or ALL addresses, depending on the
                setting of Flags(0))  In subsequent stages, this field
                contains the IP address of the discovered route's (single)
                destination node.

        * Route                        (node_id)           (N * 32 bits)
                Variable length field that contains the recorded IP
                addresses of nodes along the path traveled by this
                ROUTE_QUERY packet from the Query Source.  In subsequent
                stages (after a route to a Query Destination has been
                discovered), this set of IP addresses provides a partial
                specification of the route between the Route Source and
                Route Destination.












Haas, Pearlman              Expires September 2000              [Page 21]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        * Node/Segment Metrics         (metric)            (X * 32 bits)
                This optional section of the packet can be used to
                record a variety of node and segment quality measurements.
                (In this context, a segment refers to the communication
                path between consecutive nodes in the packet's accumulated
                route.  In the case of neighboring nodes, a segment is
                equivalent to a (one-hop) link).

                * Node                 (char)              (8 bits)
                      Index of the route corresponding to a particular
                      node.

                * Metric Type          (char)              (7 bits)
                      Type of metric being recorded
                      (based on pre-defined metric types)

                * Direction Flag       (boolean)           (1 bit)
                      For segment metrics, specifies either the:
                      upstream segment   (toward Query Source)       (0)
                      downstream segment (toward Query Dest)         (1)

                * Metric Value         (unsigned int)      (16 bits)
                      Value of node / segment metric specified by
                      Metric Type

    B.  Data Structures
        B.1  Routing Table   (See IARP Description)

        B.2  Temporary Query Cache

        +------------------------------------------------------+  ...
        | Query   |   Query_ID   |   Prev_hop   |  Hop Count   |
        | Source  |              |              |              |
        |(node_id)|(unsigned int)|(node_id list)|(unsigned int)|
        |---------+--------------|--------------+--------------+  ...
        |         |              |              |              |
        |---------+--------------|--------------+--------------+  ...
        |         |              |              |              |
        |---------+--------------|--------------|--------------+  ...
        |         |              |              |              |
        +------------------------------------------------------+  ...

          ... +--------------+
              |  Injection   |
              |   Counter    |
              |(unsigned int)|
          ... +--------------|
              |              |
          ... +--------------|
              |              |
          ... +--------------|
              |              |
          ... +--------------+


Haas, Pearlman              Expires September 2000              [Page 22]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


    C.  Interfaces

        C.1  Higher Layer (N/A)
        C.2  Lower Layer (BRP)
            C.2.1   Send(packet,source,query_ID,BRP_cache_ID)
                Used by the IERP to request packet transmission
                through the BRP.
            C.2.2  Deliver(packet,BRP_cache_ID)
                Used by the BRP to deliver data packet to the IERP.
        C.3  Lower Layer (IP)
            C.3.1  Send()       (specified in IP standard)
            C.3.2  Deliver()    (specified in IP standard)
        C.4  IARP
            C.4.1  Zone_Node_Lost(node)
                Used by the IARP to notify the IERP that a node has left
                the routing zone
        C.5  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 node running this state
                  machine.

        D.1
            Event:   A routing zone node is reported lost by the IARP,
                     indicating that a node H has moved beyond the
                     routing zone.

            Action:  Remove every route from the Interzone Routing Table
                     which contains H.  If any routes containing H are
                     found AND Proactive Route Repair is enabled, then a
                     route "Repair" (limited depth route discovery) to H
                     is initiated.

        D.2
            Event:   ICMP issues a "Host_Unreachable" message, triggering
                     a route discovery for unreachable host H.

            Action:  A FULL depth route discovery to H is initiated.
                     X's query_id is incremented and assigned to a new
                     ROUTE_QUERY packet.  The route is initialized with
                     the IP addresses of the route's source and destination
                     IP addresses (X and H).  Finally, the ROUTE_QUERY
                     packet is sent to the BRP to be bordercasted.





Haas, Pearlman              Expires September 2000              [Page 23]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        D.3
            Event:   The IERP or ICMP (via source_route_failed()) triggers
                     a "Repair" message, indicating that the next hop
                     H specified in a source route cannot be found locally.

            Action:  A limited depth route discovery to H is initiated.
                     X's query_id is incremented and assigned to a new
                     ROUTE_QUERY packet.  The route is initialized with
                     the IP addresses of the route's source and destination
                     IP addresses (X and H). Finally, the ROUTE_QUERY
                     packet is sent to the BRP to be bordercasted.

        D.4
            Event:   A ROUTE_QUERY packet is received with a destination
                     that appears within X's routing zone.

            Action:  The packet's accumulated route information (for the
                     source)is recorded in X's Routing Table and Temporary
                     Query Cache.  The accumulated route is replaced by
                     X's address and any accumulated route metrics are
                     updated and compressed.

                     X copies the ROUTE_QUERY packet's contents to a
                     ROUTE_REPLY.  A loop-free return path is selected
                     from the Temporary Query Cache (i.e. based on
                     "Diversity Injection").  X also forwards a
                     QUERY_EXTENSION to discovered query destination.  If
                     the ROUTE_QUERY packet has not traveled too deep into
                     the network (i.e. TTL > 0) AND there are still more
                     destinations to be discovered, then the ROUTE_QUERY
                     is sent down to the BRP to be relayed outward.

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

            Action:  The packet's accumulated route information (for the
                     source) is recorded in X's Routing Table and
                     Temporary Query Cache.  The accumulated route is
                     replaced by X's address and any accumulated route
                     metrics are updated and compressed.  The ROUTE_QUERY
                     packet is sent down to the BRP to be relayed outward.

        D.6
            Event:   A QUERY_EXTENSION packet is received.

            Action:  The packet's accumulated route information (for the
                     source) is recorded in X's Routing Table.  The
                     accumulated route is replaced by X's address and any
                     accumulated route metrics are updated and compressed.
                     If X is not the query destination, then X forwards the
                     message toward the destination (directly through IP)



Haas, Pearlman              Expires September 2000              [Page 24]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        D.7
            Event:   A ROUTE_REPLY packet is received.

            Action:  The packet's accumulated route information (for the
                     destination) is recorded in X's Routing Table.  X
                     adds its address to the accumulated route and adds
                     metrics for the downstream (toward the destination)
                     link to the accumulated metrics.  If X is not the
                     query source, then X forwards the message toward the
                     source (directly through IP), along a path selected
                     from the Temporary Query Cache (i.e. based on
                     Diversity Injection).

    E.  Pseudocode Implementation

        We define two complimentary operations on packets:
        extract(packet) and load(packet)

            extract(packet)
                extracts the fields of the IERP packet to the following
                variables: {type, TTL, hop_count, flags, current_hop_ptr,
                            query_id, reply_id, source, reply_node,
                            dests, route, metric}

            load(packet)
                loads the values of the aforementioned variables into
                the fields of the IERP packet.
                load(packet) automatically computes the values of:
                              num_dests = |dests|
                              num_nodes = |routes|

























Haas, Pearlman              Expires September 2000              [Page 25]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        E.1 Routing Zone Node Lost
            args: (lost_node)

            // Determine if lost_node belongs to any stored routes.
            // If so, the route should be removed from the
            // Routing Table and a route repair triggered
            // (if proactive route repairs are enabled)
            repair_link = FALSE;
            for((EACH) node (BELONGING TO) Routing Table)
            {
              for ((EACH) route (BELONGING TO) Routing_Table[node])
              {
                if (lost_node (BELONGS TO) route)
                {
                  if (PROACTIVE_REPAIRS_ENABLED)
                  {
                      removal_timer = ROUTE_QUERY_TIMEOUT;
                      repair_link = TRUE;
                  }
                  else
                  {
                      removal_timer = 0;
                  }
                  schedule(remove(Routing_Table[node,route],removal_timer)
                }
              }
            }
            if(repair_link)
            {
                dests = lost_node;
                Initiate_Route_Discovery(IERP, {dests, ALL, REPAIR});
            }

        E.2  Initiate Route Discovery
             args:  (dests, flags, type)

             // Route query is initialized and sent down to the BRP
             // to be bordercasted

             if (type == REPAIR)
                TTL = MAX_REPAIR_HOPS;
             else
                TTL = MAX_FULL_QUERY_HOPS;

             source    = MY_ID
             query_id  = MY_QUERY_ID++;
             type      = ROUTE_QUERY;
             hop_count = 0;
             route     = NULL;
             current_hop_ptr = 0;

             load (packet);
             send ((packet, source, query_id, NULL), BRP);


Haas, Pearlman              Expires September 2000              [Page 26]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        E.3  Receive IERP Packet
             args:  (packet, BRP_cache_ID)

             extract(packet);
             switch(type)
             {
                case:  ROUTE_QUERY
                    // Update Time-to-Live and hop count
                    TTL--;
                    hop_count++;

                    // Extract route (and metrics) from packet and record
                    // them in the Routing Table and Temporary Query Cache
                    prev_hops = route(1 : current_hop_ptr);
                    metrics = compress(metrics,
                                  get_metrics(prev_hops|prev_hop|,MY_ID));
                    add(Routing_Table[source],(reverse(prev_hops),
                                                  reverse(metrics),FALSE);
                    add(Temp_Query_Cache[source,query_id],
                                          (reverse(prev_hops),hop_count));

                    // Determine if routes are known for each destination
                    find_all  =  flags(0);
                    find_any  = !flags(0);
                    found_any = FALSE;
                    found_all = TRUE;

                    // Save current values for dests and metrics, since
                    // we may need them later
                    DESTS     = dests;
                    METRICS   = metrics;
                    for((EACH) dest (BELONGING TO) DESTS)
                    {
                        if (Routing_Table[dest].Intrazone)
                        {
                            // A route to this destination is known
                            found_any       = TRUE;
                            dests           = dest;
                            remove(dest, DESTS);

                            // Forward query directly to destination, so
                            // that the destination will have some routing
                            // information back to the source
                            type            = QUERY_EXTENSION;
                            prev_hops       = NULL;
                            next_hops       = Routing_Table[dest].route;
                            route           = {prev_hops,MY_ID,next_hops};
                            current_hop_ptr = |prev_hops|+1;
                            load(packet);
                            send((packet,next_hops(1)),IP);





Haas, Pearlman              Expires September 2000              [Page 27]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


                            // Send reply back to the source
                            type            = ROUTE_REPLY;
                            reply_node      = MY_ID;
                            reply_id        = MY_REPLY_ID++;
                            next_hops       = Routing_Table[dest].route;
                            prev_hops   = inject_loopfree_path(next_hops,
                                        Temp_Query_Cache[source,query_id]);
                            metrics         = NULL;
                            route           = {prev_hops,MY_ID,next_hops};
                            current_hop_ptr = |prev_hops|+1;
                            load(packet);
                            send((packet,prev_hops(|prev_hops|)),IP);
                        }
                        found_all = found_all && found_any;
                    }

                    // If more destinations need to be discovered then
                    // forward QUERY via BRP bordercasting
                    if(((find_all && !found_all)||(find_any && !found_any))
                        && TTL>0)
                    {
                        dests           = DESTS;
                        metrics         = METRICS;
                        prev_hops       = NULL;
                        next_hops       = NULL;
                        route           = {prev_hops, MY_ID, next_hops};
                        current_hop_ptr = |prev_hops|+1;
                        load(packet);
                        send((packet,BRP_cache_ID), BRP);
                    }
                break;

                case:  QUERY_EXTENSION
                    // Extract route (and metrics) from packet and record
                    // them in the Routing Table
                    prev_hops = route(1 : current_hop_ptr);
                    next_hops = route(current_hop_ptr+1 : |route|);
                    metrics   = compress(metrics,
                                  get_metrics(prev_hops|prev_hop|,MY_ID));
                    add(Routing_Table[source],(reverse(prev_hops),
                                                   reverse(metrics),FALSE);














Haas, Pearlman              Expires September 2000              [Page 28]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


                    // Forward query extension until it reaches destination
                    if(MY_ID !(BELONGS TO) dests)
                    {
                        prev_hops = NULL;
                        if(|next_hops|==1)
                        {
                            next_hops = Routing_Table[dest].route;
                            route           = {prev_hops, MY_ID, next_hops};
                            current_hop_ptr = |prev_hops|+1;
                        }
                        else
                        {
                            current_hop_ptr++;
                        }
                        load(packet);
                        send((packet,next_hops(1)),IP);
                    }
                break;

                case:   ROUTE_REPLY
                    // Extract route (and metrics) from packet and record
                    // them in the Routing Table
                    prev_hops = route(1 : current_hop_ptr-1);
                    next_hops = route(current_hop_ptr : |route|);
                    metrics = {metrics,get_metrics(MY_ID,next_hops(1))};
                    add(Routing_Table[dest],(next_hops,compress(metrics),FALSE);

                    // Forward reply until it reaches source
                    if(MY_ID != source)
                    {
                        // Choose a loopfree return path from the Temporary
                        // Query Cache (eg. shortest path, shortest least
                        // "injected" path, etc.)

                        prev_hops  = inject_loopfree_path(next_hops,
                                       Temp_Query_Cache[source,query_id]);
                        route           = {prev_hops, MY_ID, next_hops};
                        current_hop_ptr = |prev_hops|+1;
                        load(packet);
                        send((packet,next_hop),IP);
                    }
                break;
            }













Haas, Pearlman              Expires September 2000               [Page 29]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


4.3  Bordercast Resolution Protocol (BRP)

   The BRP provides the "bordercasting" message delivery service, here
   used to forward IERP route queries.  Messages are relayed from a
   bordercasting node outward to its peripheral nodes, along a
   bordercast (multicast) tree.  Although the intended recipients of
   the bordercast are the peripheral nodes, the BRP may deliver the
   bordercast message up to the higher layer application (in this case,
   the IERP) at EVERY hop.  This may be necessary for applications that
   use bordercasting, but are generally not "routing zone aware".

   When a node receives a bordercasted message, it first needs to determine
   whether the message should be forwarded.  Clearly, the node should
   only forward the message if it belongs to the bordercast tree.
   Furthermore, if the node is the (peripheral node) bordercast recipient,
   it would re-bordercast the message, but only if it has not been a bordercast
   recipient before AND it does not lie inside the routing zone of a
   detected "previously bordercasted" node.

   If the node decides not to discard the message, it next determines which
   of the current bordercast tree's downstream branches will be dropped.
   A downstream branch will be dropped if each of the branch's downstream
   peripheral nodes either has had a bordercast message relayed to it by
   this node OR lies inside the routing zone of a detected previously
   bordercasted node.

   The BRP delivers the message up to the higher layer application (IERP).
   After some processing, the application may return an updated message
   back to the BRP.  The BRP will then relay the message on the selected
   outgoing links.


   A.  Packet Format

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Message Source Addresss                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                          Message ID                           |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Prev Bordercast Address                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    |            E N C A P S U L A T E D     P A C K E T            |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+









Haas, Pearlman              Expires September 2000              [Page 30]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        * Message Source Address       (node_id)           (32 bits)
                IP address of the node that initiates the message.

        * Message ID                     (unsigned int)    (16 bits)
                Sequence number which, along with the Message Source
                Address uniquely identifies any BRP message in the
                network.

        * Prev Bordercast Address      (node_id)           (32 bits)
                IP address of the most recent bordercasting node

        * Encapsulated Packet          (packet)

        *** note:  Within the context of the ZRP, the Message Source
                   Address and Message ID can assume the same values
                   as the corresponding "Query" fields in the
                   encapsulated IERP packet.
                   As such, they can be eliminated AS LONG AS:
                           (a)  The BRP has read access to the contents of
                                the encapsulated IERP packet.
                           (b)  The BRP knows the format of the IERP packet.

                   For this version of the ZRP, both (a) and (b) are true.
                   However, we provide the BRP with its own Message ID and
                   Message Source fields for future support of generic
                   higher layer applications.

    B.  Data Structures

        B.1  Routing Table          (see IARP description)

        B.2  Bordercast Tree Table  (see IARP description)























Haas, Pearlman              Expires September 2000              [Page 31]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


        B.3  Detected Messages Cache

             +------------------------|--------------------------+ ...
             | Message |  Message ID  | BRP_cache_ID |   Prev    |
             |  Source |              |              |Bordercast |
             |(node_id)|(unsigned int)|(unsigned int)| (node_id) |
             |---------+--------------|--------------+-----------+ ...
             |         |              |              |           |
             |         |              |--------------+-----------+ ...
             |         |              |              |           |
             |---------+--------------|--------------+-----------+ ...
             |         |              |              |           |
             |         |              |--------------+-----------+ ...
             |         |              |              |           |
             +------------------------|--------------+-----------+ ...

                 ... +---------------+
                     | Out_neighbor  |
                     |               |
                     |(node_id list) |
                 ... +---------------|
                     |               |
                 ... +---------------|
                     |               |
                 ... +---------------|
                     |               |
                 ... +---------------|
                     |               |
                 ... +---------------+

    C.  Interfaces

        C.1  Higher Layer (IERP)
            C.2.1  Send(packet, BRP_cache_ID)
                Used by the IERP to request packet transmission.
            C.2.2  Deliver(packet, BRP_cache_ID)
                Used by the BRP to deliver a data packet up to IERP.
        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 node running this state
                machine.






Haas, Pearlman              Expires September 2000              [Page 32]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


      D.1
            Event:   A message is received from the higher layer (IERP).
                     BRP_cache_ID == NULL.

            Action:  The bordercast was initiated by X.  X marks itself as
                     the previous bordercast node and relays the message to
                     all the downstream neighbors in its bordercast tree.

      D.2
            Event:   A message is received from the higher layer (IERP).
                     BRP_cache_ID != NULL.

            Action:  The bordercast was not initiated by X.  X looks up
                     this message's forwarding information recorded in
                     it's Detected Messages Cache (and referenced by
                     BRP_cache_ID).  X then relays the message to the
                     designated downstream neighbors.

      D.3
            Event:   A message is received from the IP.

            Action:  The message is terminated under the following
                     conditions:
                     (1) X does not belong to the bordercast tree of
                         prev_bcast.
                     (2) If X is the bordercast recipient and
                             (a) X has already been a bordercast recipient.
                                            OR
                             (b) X is an interior (i.e. non-peripheral)
                                 member of a detected previously
                                 bordercasted node's routing zone.

                     If X is a bordercast recipient and does not terminate
                     the message then it re-bordercasts the message.

                     Next, X decides which of the current bordercast
                     tree's downstream branches (neighbor) will be dropped.
                     A downstream branch will be dropped if, for each of
                     the branch's downstream peripheral node D:
                             (a) X has already relayed a message to D.
                                            OR
                             (b) D is an interior (i.e. non-peripheral)
                                 member of a detected previously
                                 bordercasted node's routing zone

                     Finally, X delivers the message to the higher layer
                     (IERP).









Haas, Pearlman              Expires September 2000              [Page 33]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


    E.  Pseudocode Implementation

        We define two complimentary operations on packets:
        extract(packet) and load(packet)

            extract (packet)
                  extracts the fields of the BRP packet to the following
                  variables: {source,message_id,prev_bordercst,
                              message_packet)

            load (packet)
                loads the values of the aforementioned variables into
                the fields of the BRP packet.


        E.1  Receive Packet from higher layer (IERP)
             args: (message_packet, BRP_cache_ID)

             // If BRP_cache_ID == NULL then this is a new bordercast
             // issued by this node.  This new bordercast can be relayed
             // to ALL downstream neighbors in the bordercast tree.
             // Otherwise, this is an existing bordercast that should be
             // forwarded to the pre-assigned downstream neighbors.

             if(BRP_cache_ID)
             {
                prev_bcast = Detected_Messages[source,message_id
                                               ,BRP_cache_ID].prev_bcast;
                out_neighbors = Detected_Message
                             [source,message_id,BRP_cache_ID].out_neighbors;
             }
             else
             {
                prev_bcast = MY_ID;
                out_neighbors = Bordercast_Tree[MY_ID].downstream_neighbors;
             }
             source     = MY_ID;
             message_id = MY_BORDERCAST_ID++;
             load(packet);
                 send(packet,out_neighbors),IP);


        E.2  Receive Packet from IP
             args:  (packet)

             extract(packet);

             // Discard bordercast message if this node is not a member of
             // prev_bcast's bordercast tree
             discard = !Bordercast_Tree[prev_bcast].member;






Haas, Pearlman              Expires September 2000              [Page 34]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


             // If this node is the downstream peripheral node of
             // prev_bcast then terminate if this node:
             //     (a) has already been a bordercast recipient
             //                       OR
             //     (b) is inside the routing zone of a node that has
             //         already bordercasted the message

             if(is_peripheral_node(prev_bcast,MY_ID))
             {
                 for((EACH) queried_node (BELONGING TO)
                                  Detected_Messages[source,message_id]
                                  .prev_bcast)
                 {
                    a = MY_ID (BELONGS TO)
                        Bordercast_Tree[queried_node]
                                            .downstream_peripheral_nodes;
                    b = is_interior_node(queried_node,MY_ID);
                    discard = discard || (a || b);
                 }
                 // Since this node is the downstream peripheral recipient,
                 // it will re-bordercast the message (if it isn't
                 // terminated)
                 prev_bcast = MY_ID;
             }
































Haas, Pearlman              Expires September 2000              [Page 35]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


             out_neighbors = {};
             if(!discard)
             {
                 // Don't relay message to a given downstream neighbor if
                 // each covered downstream peripheral node (of prev_bcast):
                 //     (a) has already been a bordercast recipient
                 //                       OR
                 //     (b) is inside the routing zone of a node that has
                 //         already bordercast the message

                 for((EACH) neighbor (BELONGING TO)
                                          Bordercast_Tree[prev_bcast]
                                                   .downstream_neighbors)
                 {
                     drop_neighbor = TRUE;
                     leaves = Bordercast_Tree[prev_bcast,neighbor
                                           ].downstream_peripheral_nodes;
                     for((EACH) leaf_node (BELONGING TO) leaves)
                     {
                         failed_leaf = TRUE;
                         for((EACH) queried_node (BELONGING TO)
                                Detected_Messages[source,message_id]
                                                             .prev_bcast)
                         {
                            a = leaf_node (BELONGS TO)
                                Bordercast_Tree[queried_node]
                                            .downstream_peripheral_nodes;
                            b = is_interior_node(queried_node,leaf_node);
                            failed_leaf = failed_leaf || (a || b);
                         }
                         drop_neighbor = drop_neighbor && failed_leaf;
                     }
                     if(!drop_neighbor)
                         out_neighbors = {out_neighbors, neighbor};
                 }
             }

             // Record BRP "state" in Detected Messages Cache, so that
             // the message can be properly forwarded when returned by
             // the higher layer app (IERP)
             BRP_cache_ID++;
             add(Detected_Messages[source,message_id],(BRP_cache_ID,
                                               prev_bcast,out_neighbors));
             schedule(remove(Detected_Messages[BRP_cache_ID],
                                                      MAX_QUERY_LIFETIME);

             deliver(message_packet,BRP_cache_ID);









Haas, Pearlman              Expires September 2000              [Page 36]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


5. Other Considerations

5.1 Sizing the Zone Radius

   The performance of the Zone Routing Protocol is determined by the
   routing zone radius.  In general, dense networks consisting of a few
   fast moving nodes favor smaller routing zones.  On the other hand, a
   sparse network of many slowly moving nodes operates more efficiently
   with a larger zone radius.

   The simplest approach to configuring the routing zone radius is to
   make the assignment once, prior to deploying the network.  This can
   be performed by the network administration, if one exists, or by
   the manufacturer, as a default value.  This may provide acceptable
   performance, especially in situations where network characteristics
   do not vary greatly over space and time.  Alternatively, the ZRP can
   adapt to changes in network behavior, through dynamic configuration
   of the zone radius [3].  In [9], it was shown that a node can
   accurately estimate its optimal zone radius, on-line, based on local
   measurements of ZRP traffic.  The re-sizing of the routing zone can be
   carried out by a protocol that conveys the change in zone radius to the
   members of the routing zone.  The details of such an update protocol
   will be provided in a future version of this draft.

5.2 Hierarchical Routing and the ZRP

   In a hierarchical network architecture, network nodes are organized
   into a smaller number of (often disjoint) clusters.  This routing
   hierarchy is maintained by two component routing protocols.  An intra-
   cluster protocol provides routes between nodes of the same cluster,
   while an inter-cluster protocol operates globally to provide routes
   between clusters.

   The ZRP, with its routing zones and intrazone / interzone routing
   protocol (IARP/IERP) architecture may give the appearance of being a
   hierarchical routing protocol.  In actuality, the ZRP is a flat routing
   protocol.  Each node maintains its own routing zone, which heavily
   overlaps with the routing zones of neighboring nodes.  Because there is
   a one-to-one correspondence between nodes and routing zones, the routing
   zones, unlike hierarchical clusters, do not serve to hide the details of
   local network topology.  As a result, the network-wide interzone routing
   protocol (IERP) actually determines routes between individual nodes,
   rather than just between higher level network entities.












Haas, Pearlman              Expires September 2000              [Page 37]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


   For small to moderately sized networks, flat routing protocols, like the
   ZRP, are preferable to hierarchical routing protocols.  In order for
   a node to be located, its address needs to reflect the node's location
   within the network hierarchy (i.e.  {cluster id,node id}).  Because of
   node mobility, a node's cluster membership (and thus address) is subject
   to change.  This complicates mobility management, for the benefit of
   more efficient routing.  In many hierarchical routing protocols, each
   cluster designates a single clusterhead node to relay inter-cluster
   traffic.  These clusterhead nodes become traffic "hot-spots",
   potentially resulting in network congestion and single point of failure.
   Furthermore, restricting cluster access through clusterhead nodes can
   lead to sub-optimal routes, as potential neighbors in different clusters
   are prohibited from communicating directly.   Some hierarchical routing
   protocols, such as the Zone-Based Hierarchical Link-State (ZHLS) [4],
   avoid these problems by distributing routing information to all cluster
   nodes, rather than maintaining a single clusterhead.

   In spite of these disadvantages, hierarchical routing protocols are
   often better suited for very large networks than flat routing protocols.
   Because hierarchical routing protocols provide global routes to network
   clusters, rather than individual nodes, routing table storage is more
   scalable.  Similarly, the amount of route update messages is also more
   scalable.  To some extent, the reduction in routing traffic is offset
   by extra mobility management overhead (i.e. identifying which cluster
   a node belongs to).  However, it is quite common that the environment or
   existing organizational structure causes nodes to naturally cluster
   together.  In these cases, there may be a high degree of intra-cluster
   mobility, with inter-cluster mobility is less common.

   A hierarchical routing protocol can be viewed as a set of flat routing
   protocols, each operating at different levels of granularity.  In a two-
   tier routing protocol, the inter-cluster components is essentially a
   flat routing protocol that computes routes between clusters.  Likewise,
   the intra-cluster component is a flat routing protocol, that computes
   routes between nodes in each cluster.  For example, the Near Term
   Digital Radio (NTDR) System [13] and ZHLS both employ proactive link
   state protocols to determine inter and intracluster connectivity.

   In place of traditional proactive or reactive protocols, we recommend
   that the intra-cluster and inter-cluster routing protocol components
   be implemented based on the hybrid proactive/reactive ZRP.  As described
   throughout this draft, the ZRP is designed to provide an optimal balance
   between purely proactive and reactive routing.  This applies equally well
   to routing between nodes at the intra-cluster level and between clusters
   at the inter-cluster level.  Additionally, the hybrid ZRP methodology can
   be applied to the related mobility management protocols, which determine
   complete node addresses based on a node's location in the network
   hierarchy.








Haas, Pearlman              Expires September 2000              [Page 38]


INTERNET DRAFT              The Zone Routing Protocol          March 2000

6.0 References

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

   [2]   Haas, Z.J. and Pearlman, M.R., "The Performance of Query
              Control Schemes for the Zone Routing Protocol,"
              SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998.

   [3]   Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design
              Choices in Ad-Hoc Communications," MILCOM'98, Boston, MA,
              October 18-21, 1998.

   [4]   Joa-Ng, M. and Lu, I.T., "A Peer-to-Peer Zone-based Two-Level
              Link State Routing for Mobile Ad-Hoc Networks," to appear
              in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.

   [5]   Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing
              in Ad-Hoc Wireless Networks," in Mobile Computing,
              edited by T. Imielinski and H. Korth, chapter 5,
              pp. 153-181, Kluwer, 1996.

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

   [7]   Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient
              Routing Protocol for Wireless Networks," MONET, vol. 1,
              no. 2, pp. 183-197, October 1996.

   [8]   Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed
              Routing Algorithm for Mobile Wireless Networks,"
              IEEE INFOCOM'97, Kobe, Japan, 1997.

   [9]   Pearlman, M.R. and Haas, Z.J., "Determining the Optimal
              Configuration for the Zone Routing Protocol," IEEE JSAC,
              August, 1999.

   [10]  Pearlman, M.R. and Haas, Z.J., "Improving the Performance of
              of Query-Based Routing Protocols Through 'Diversity
              Injection'", IEEE WCNC'99, New Orleans, LA, Sept. 1999.

   [11]  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.

   [12]  Perkins, C.E. and Royer, E.M., "Ad-Hoc On-Demand Distance
              Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999

   [13]  Ruppe, R., Griswald, S., Walsh, P. and Martin, R., "Near Term
              Digital Radio (NTDR) System," IEEE MILCOM'97, Monterey, CA,
              Nov. 1997.

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

Haas, Pearlman              Expires September 2000              [Page 39]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


7.0  Draft Updates

   - The sole function of the Bordercast Resolution Protocol (BRP) is
     to perform application independent bordercasting (all excess
     routing protocol functionality has been moved up to the IERP).
     This means that the BRP can be used outside of the ZRP, for any
     application that requires an efficient network-wide query/probing
     mechanism.  Likewise, a wide variety of globally reactive routing
     protocols may be adopted as alternate IERPs, by substituting the
     query "broadcast()" with "bordercast()".
     In further support of application independent bordercasting, the BRP
     can deliver messages up to the higher layer application at every hop
     (as opposed to only delivering for peripheral nodes).  This is
     important for applications that wish to use the bordercast service,
     but are otherwise "routing zone unaware".

   - The bordercast message delivery service is now implemented via
     multicasting, rather than a series of separate unicasts to individual
     peripheral nodes.  The bordercast control mechanisms have been revised
     to support this transition.

   - The IARP is now required to proactively track the COMPLETE topology of
     an EXTENDED routing zone, consisting of all nodes that are at a
     minimum distance (in hops) LESS THAN twice the "basic" routing zone
     radius.  Nodes use this extended information to construct the
     downstream portion of each routing zone node's bordercast (multicast)
     tree.  Consequently, the Distance Vector IARP implementation has been
     dropped.

   - For convenience, the IARP and IERP now share a single routing table.
     IARP entries are indicated by a special flag.

   - The IERP's optional Route Accumulation and Route Optimization stages
     have been dropped.

   - The route maintenance policy has been simplified.  Local route
     repairs are only reported to the source of the broken link, not to
     the route's source.

   - Support for "diversity injection" [10] has been added to the IERP.
     The diversity injection mechanism allows the global route discovery
     to extract more information about current network connectivity,
     without any additional traffic.













Haas, Pearlman              Expires September 2000               [Page 40]


INTERNET DRAFT              The Zone Routing Protocol          March 2000


Authors' Information

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

   Marc R. Pearlman
   389 Frank Rhodes Hall
   School of Electrical Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   tel: (607) 255-0236, fax: (607) 255-9072
   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 September 2000               [Page 41]