INTERNET-DRAFT                       Zygmunt J. Haas,  Cornell University
                                     Marc R. Pearlman, Cornell University

Expires in six months on December 1999                              June
1999 September 2000                        March 2000

           The Zone Routing Protocol (ZRP) for Ad Hoc Networks
                  <draft-ietf-manet-zone-zrp-02.txt>
                  <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.

   The ZRP framework is designed to provide a balance between the
   contrasting proactive and reactive routing approaches.  To underscore
   this general philosophy, both the proactive and reactive components of
   this ZRP implementation have been expanded.  This draft provides
   specifications for both a (split-horizon) Distance Vector AND a Link
State
   version of the proactive IntrAzone Routing Protocol (IARP).  The reactive
   IntErzone Routing Protocol (IERP) provides a route caching option.  When
   route caching is globally enabled, the IERP acts as a reactive Distance
   Vector protocol, distributing routing information among intermediate
nodes.
   On the other hand, when route caching is disabled, the routes are
accumulated
   in the query packets and the protocol operates through source routing.

Haas, Pearlman                Expires December 1999                   [Page
i]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   This ZRP specification also offers some additional enhancements.  The
   reactive route query procedure now supports route querying for multiple
   destinations and multicast groups.  Queries can be targeted for either
   ANY destination or ALL destinations (depending on the nature of the
query).
   By aggregating route queries, the amount of overhead traffic can be
greatly
   reduced.  In addition, the ZRP now supports QOS routing through the
   collection of various route quality metrics (in both the proactive and
   reactive routing components).

Haas, Pearlman                Expires December 1999                  [Page
ii]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

                                Contents

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

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

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

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

       2.2  The Interzone Routing Protocol (IERP)  . . . . . . . .  4  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 . . . . . . . . . . . . . . .  7  6

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

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

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

       4.2  Interzone Routing Protocol (IERP) . . 25

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

       4.3  Bordercasting Resolution Protocol (BRP) . . . . . . . 37
            A.  Packet Format . . . . 34

   5.  Other Considerations  . . . . . . . . . . . . . . 38
            B.  Data Structures . . . . . 37
       5.1  Sizing the Routing Zone  . . . . . . . . . . . . 38
            C.  Interfaces . . . 37
       5.2  Hierarchical Routing and the ZRP . . . . . . . . . . . 37

   6.  References  . . . . . . 38
            D.  State Machine . . . . . . . . . . . . . . . . . . 39
            E.  Pseudocode Implementations . . . . . . . . . . . . 43

Haas, Pearlman                Expires December 1999                 [Page
iii]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   5.  Other Considerations  . .

   7.  Draft Modifications . . . . . . . . . . . . . . . . . 53
       5.1  Sizing the Routing Zone  . . . . . . . . . . 40

   Authors' Information  . . . . . 53
       5.2  Hierarchical Routing and the ZRP . . . . . . . . . . . 53

   6.  References . . . . . 41
   MANET Contact Information . . . . . . . . . . . . . . . . . . . 55

Haas, Pearlman                Expires December 1999                  [Page
iv]

INTERNET DRAFT              The Zone Routing Protocol                June
1999 41

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 tradtional 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 fine-tuned by individual adjustment of each node's
    routing zone.

    The global reactive component of the ZRP uses the unicast/multicast multicast based
    "bordercast" mechanism to propagate route queries throughout the
    network, rather than relying on neighbor-broadcast based flooding found in
    tradtional reactive protocols.  Consequently, the ZRP provides the
    most benefit in networks where reliable neighbor broadcasting is
    either inefficient or
all-together altogether impossible.  In particular, the ZRP
    is well suited for multi-channel,
multi-
    technology 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 reactive route discovery mechanism may
        use either based
        on source routing or routing, distributed distance vector based
        route accumulation.

Haas, Pearlman                Expires December 1999                   [Page
v]

INTERNET DRAFT              The Zone Routing Protocol                June
1999 vectors, or various
        combinations of both.

   * 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 December 1999                  [Page
vi]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   * 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 ZRP-specific 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 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.  Loop-freedom  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 each route query and route reply queries (replies) with the IP source
        (destination) address of its originating node AND a and locally unique sequence number.  Nodes
        that relay the route queries
        /route replies these messages can temporarily cache these identifiers
        in order to identify and terminate loops.

        The routing protocols used for proactive routing zone maintenance
        are based on traditional Distance Vector or ZRP's Link State routing
        protocols.  The scope of these proactive route updates is limited
        to the extent of a node's routing zone.
        The ZRP's Link State proactive protocol protocol is inherently loop-free.
        The Distance Vector protocol may form loop-free,
        although temporary loops prior to
        converging.  However, convergence occurs quickly due to the limited
        radius of may form while new link state updates
        propagate through the routing zones

Haas, Pearlman                Expires December 1999                 [Page
vii]

INTERNET DRAFT              The Zone Routing Protocol                June
1999 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) example).

   * 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 December 1999                [Page
viii]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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)[6], (DSR)[5], Ad-hoc On demand Distance Vector
   Routing (AODV) [11] [12] and the Temporally Ordered Routing Algorithm
   (TORA) [9]. [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- route
   determination procedure on-demand, but at limited search cost. The
   protocol described in this draft, termed the "Zone Routing Protocol
   (ZRP)" ([1], [2]), [2],[9]), is an example of a such a hybrid
   proactive/reactive proactive/
   reactive scheme.

   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.

Haas, Pearlman                Expires December 1999                   [Page
1]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   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. Proactive  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.

Haas, Pearlman                Expires December 1999                   [Page
2]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

2. Overview of the Zone Routing Protocol

2.1 The Notion of a Routing Zone 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 at most no greater than some predefined
   number, which is
   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
   +---+  |  +---+       |        +---+     +---+   |  of radius=2      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.

   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, "bordercasting", allows for more
   efficient network-wide searching than simple neighbor broadcasting.
   Bordercasting could be implemented either through a series of IP
   unicasts or an IP multicast
   (Distance Vector Multicast Routing Protocol [13]) (DVMRP) [14]) to the
   peripheral nodes.  (In cases where
   multicasting is supported, the multicasting approach is preferred
   to reduce the amount of traffic over the air.)  However, as will be explained later, efficient ZRP
   operation requires that these unicast
   or multicast services the bordercast service be provided handled, on a
   hop-by-hop basis, by the ZRP, with IP providing best-
   effort delivery to the specified ZRP next hops.

   The ZRP supports the proactive maintenance of routing zones
   through ZRP.

   In its proactive basic form, the ZRP's Intrazone Routing Protocol (IARP).  Through
   the IARP, (IARP) is
   responsible for providing each node learns the identity with current view of and the (minimal)
   distance to all the nodes in its routing zone.  The IARP may be
   derived from
   zone topology.  With this information, a wide range of proactive protocols, such as
   Distance Vector (e.g., [8], [10]) or Shortest Path First
   (e.g., OSPF [7]).  Whatever node can identify ITS
   peripheral nodes AND construct a bordercast (multicast) tree to them.
   However, in order for the choice  bordercast to be carried out, member of IARP is, the base
   protocol
   bordercast tree needs to be modified 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 this
   operation the route updates is
   restricted to the radius of a node's extended routing zone.

Haas, Pearlman                Expires December 1999                   [Page
3]

INTERNET DRAFT              The Zone Routing Protocol                June
1999  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 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.

2.2.1  Routing Zone Based Route Discovery

   The IERP operates

   We illustrate the basic operation of routing zone based route
   discovery through a simple (and as follows: we will see, inefficient) IERP
   implementation.  The source node node, in need of a route to a destination
   node, first checks whether the destination is lies within its routing
   zone. (Again, this  (This is possible
   as since every node knows the content of its
   routing zone).  If so, the a path to the destination is known and known, no further
   route discovery processing is required. If, on  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. Now, in turn, all  Upon
   receipt of the route query, each peripheral nodes execute executes the same algorithm: check whether
   algorithm.  If the destination is lies within their
   zone. If so, its routing zone, a route
   reply is sent back to the source source, indicating the route to the
   destination.  If not, the peripheral this node forwards the query to its ITS peripheral nodes, which, in turn, executes the same
   procedure.  An example of this Route Discovery procedure is
   demonstrated in the figure below.

   * Some functions of
   nodes.  This process continues until the IERP, including bordercasting, route
     accumulation, and query control (see later), are performed by a
     special component of the IERP called the Bordercast Resolution
     Protocol (BRP).  Sections 3.0 and 4.0 describe, in detail, the
     relationship between the BRP and has spread throughout
   the IERP proper.

Haas, Pearlman                Expires December 1999                   [Page
4]

INTERNET DRAFT              The Zone Routing Protocol                June
1999 network.

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

   The

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

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, Y may send a the route reply back to S, through can be returned via strict source routing.

Haas, Pearlman                Expires December 1999                   [Page
5]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   Given sufficient storage space, a queried node may cache routing
   information accumulated in the query packet, allowing the information

   In order to be remove from the packet.  This has the benefit of reducing reduce the length of the query packet, thereby decreasing the query traffic packets and query response time.  The IP addresses that remain in time,
   the packet query packet's accumulated route can be used to form a loose source route back to cached among the query's source (If
   ALL path's
   nodes have cached (in the accumulated route information, then this
   effectively becomes next form of the previous hop routing.  If no nodes have cached
   accumulated route information, then this defaults to toward the basic case
   previously discussed).  The same caching strategy query source),
   rather than explicitly recorded in the packet itself.  During the
   reply phase, the cached previous hops can be applied to direct the reply packet on its way back to the
   source.  In this case, a
   loose source route to  Along the destination is formed.

2.2.3 Query Control Mechanisms

   Bordercasting has way, information can be accumulated in the potential to support global querying schemes
   that are more efficient than flooding.  To achieve this efficiency, reply
   packet, forming a source route.  Alternatively, the protocol should discovered route
   may be able to detect and terminate distributed among its nodes' routing tables, providing a next
   hop routing solution.

   Sending replies along the (reversed) paths explicitly traveled by the
   successful query thread
   when it appears packets can result in a previously queried region 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 network (i.e.
   arrives at a node belonging to the routing zone destination region ahead of a previously
   queried node).  This detection / termination capability
   others.  The descendents of this query packet trigger the majority of
   route replies.  The route diversity problem is
   significantly limited aggravated when bordercasting is implemented directly all
   possible paths between the source and destination pass through a
   common node, called a topological bottleneck.  Since only one query
   packet passes through IP unicast or IP multicast.

   By implementing bordercasting within the ZRP, bottleneck, all discovered routes will be
   identical prior to the nodes that topological bottleneck.

   This problem could be addressed by allowing a node to relay
   the a route
   query more than once. Alternatively, we can apply "diversity
   injection" [10] to increase diversity without generating additional
   route replies.  During the peripheral node are able to detect route query stage, nodes temporarily cache
   the passing
   query.  If previous hop information for ALL received query packets (including
   the underlying IP delivery is (neighbor) broadcast or
   if IP is operating in promiscuous mode, then nodes packets that overhear
   a query transmission are also able to detect discarded).  Later, during the query, further
   strengthening reply phase,
   replies are relayed through the Query Detection (QD) mechanism.  Upon detecting shortest of the least selected cached
   paths that does not produce a query, routing loop.

2.2.3 Query Control Mechanisms

   Bordercasting has the identifying query parameters (i.e. query source,
   query ID) potential to support global querying schemes
   that are recorded 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 Detected Queries Table, previously
   queried region of the network.  The ZRP's ability to provide a
   basis for termination of future threads this
   level of that query.

   A node can consider a query to be control capability is significantly limited when
   bordercast messages are forwarded to peripheral nodes by IP.

   To prevent redundant if it has already
   detected querying, nodes should be able to detect when
   routing zones that query, bordercasted by they belong to have been queried.  Clearly, a different node.  If
   bordercasting node
   that bordercasts a route query is implemented directly through IP unicast/ multicast, aware that its own zone has been
   queried.  If bordercast messages are relayed by IP, then a the query thread could only
   will not be terminated after being received by detected again until it reappears at the target peripheral node (bordercast destination).  This could result
   nodes.  On the other hand, if bordercast forwarding is performed
   within the routing protocol, then all nodes in
   wasted transmissions as a the bordercast tree
   will detect the query.  Additional query penetrates into a previously queried
   region.  Implementing bordercasting detection is possible in
   shared channel networks if the ZRP allows the protocol 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
   provide an Early Termination (ET), as the redundant
   bordercast tree.

   Standard flood search protocols terminate query enters the packets that are
   targeted for (or arrive at) previously queried region.

Haas, Pearlman                Expires December 1999                   [Page
6]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

2.2.4 Route Maintenance

   In addition nodes.  We can extend
   this idea 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 ZRP by the IARP, in
   response discarding route queries before they arrive at
   bordercast recipients that belong to a node leaving the previously queried routing
   zone.  Any IERP routes
   containing this  More precisely, a node as will not relay a packet down a branch of
   the first hop 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 (Intrazone) Routing Table).

   Upon local detection of a route failure, a node may choose to notify
   the route's source of the failure and / or attempt to repair the
   route.  A route failure notification consists of
   a transmission
   back to the query source, indicating that the source route has
   failed, and possibly the hop at which it failed.  This type of
   service is provided by protocols like ICMP.  The node that detects
   the route failure may also try to repair the failed connection by discovering a route path to bypass the failed connection. 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.  Thus,  Therefore, the depth of a repair query
   can be limited, through the use of hop counter. 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.

Haas, Pearlman                Expires December 1999                   [Page
7]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

3.0 The ZRP Architecture

             .........................................
             :                  ZRP                 Z R P                 :
             :                                       :
+---------+  :      +---------+         +---------+  :      +---------+
|   NDM   |========>|  IARP   |========>|  IERP   |<========|  ICMP   |
+---------+  :      +---------+         |.........|         |---+-----+  :      +---------+
    /|\      :          /|\             |   BRP   |             |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
                                           (component of IERP)

      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 December 1999                   [Page
8]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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.  This can be achieved
   through a variety of different implementations.  In fact, many  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 both a Distance-Vector
   and a Link-State IARP.  The convergence problems typically associated
with
   the Distance-Vector approach are less of a liability in the IARP
   implementation because of the finite hop count imposed by the routing
zone
   radius.  Additionally, techniques such as "hold-downs", "split horizons"
   and "poison reverse" can be used to prevent instabilities.  A stable
   Distance Vector IARP implementation converges a rate comparable to
   Link-State IARP, and generally with less control traffic and reduced
   computational overhead.  However,
    Nodes compute intrazone routes based on the Link-State IARP provides a complete
   view link state (neighbor
    connectivity) of the routing zone topology, making it a favorable option for some
   applications (including "on-line" each extended routing zone re-sizing).

4.1.1  Distance Vector (with split horizon) IARP

   In this version of the IARP, exchanged routing messages consist of the
   route cost (including hop count) and the IP addresses of the route's
   destination and next TWO hops to the destination. The second hop
   is included to identify routes where a node is it's own second hop.
   This particular looping condition result in the "counting to
   infinity" problem.  By deleting these routes, this problem can be
   avoided, allowing the IARP to converge faster. node.  A node may receive new route information
    link state updates either from a received an IARP link state packet or from an
    interrupt generated by its Neighbor Discovery / Maintenance (NDM)
    process*. In the special case when a host has
   discovered  Link states are maintained in a neighbor, 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 IARP
    routing table is responsible for sending to the new
   neighbor the shortest route to each host which recomputed, using a minimum spanning tree algorithm.
    The Link State Table is common then updated to both remove links that lie outside
    of
   their the extended routing zones (i.e. each host with a hop count less than it's zone.  All new link state updates for non-
    peripheral routing zone radius). The node then records nodes are forwarded to all neighbors.  In
    addition, if a new neighbor is discovered, the new route information
   in its Intrazone Routing Table.  If neighbor is sent
    the shortest path FULL link states of all non-peripheral routing zone nodes.

    In addition to computing routes to all nodes in the host has
   changed, extended routing
    zone, the terminal broadcasts an IARP packet reflecting also uses the
   change. 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 host's 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 December 1999                   [Page
9]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    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)           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
   |                       Next Hop #1 Address   RESERVED    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  Metric Type  |          Metric Value         |                       Next Hop #2 Address   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--   |
   |   RESERVED    |  Metric Type  |          Metric Value         |   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                  | |                                Route                                 Link
                                 \| |/                              Metrics
                                  \ /
(optional)                                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
   |   RESERVED    |  Metric Type  |          Metric Value         |   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |   Hop Count   |
    +-+-+-+-+-+-+-+-+

        Field Description:

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

        * Link Destination Subnet Mask    (32 bits)
            IP subnet mask associated with the destination

        * Next Hop # 1 Address     (node_id)           (32 bits)
            IP address of the "next hop" host to the reported link's destination host node.

        * Next Hop # 2 Packet Source Address        (node_id)           (32 bits)
            IP address of the Next Hop #1 's "next hop" host node that sent this packet.
            (Used to
            the destination host

        * Node/Link Metrics          (X account for any outstanding link state information)

        * 32 Link State ID                (unsigned int)      (16 bits)
                This section of the packet is
            Sequence number used to report track the quality of
                this link (or link source node).

                * Metric Type        (8 bits)
                      Type state history of metric being
            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
             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

        * Hop Count                  (8 bits)
            Length of the route to the destination host, measured
            in hops

Haas, Pearlman                Expires December 1999                  [Page
10]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    B.  Data Structures

    B.1  Intrazone  Routing Table

            +---------+--------|-----------------------------------------+

    +-----------------------|--------------------------------+-----------+
    |   Dest    |  Subnet   |     Routes     |     Route     | Intrazone |
    |   Addr    |   Mask  |-----------+-----------+-----+-----------+    |                |    Metrics    |     0           |     1
    | ==> (node_id) | (node_id) | (node_id list) | (metric list) |    M-1 (boolean) |
            +---------+--------|-----------+-----------+-----+-----------+
    |-----------+-----------|----------------+---------------+-----------+
    |           |           |                |               | ==>           |
    |-----------+-----------|----------------+---------------+-----------+
    |
            |---------+--------|-----------|-----------|-----|-----------|           |           |                |               |           | ==>
    |-----------+-----------|----------------+---------------+-----------+
    |           |
            |---------+--------|-----------|-----------|-----|-----------|           |                |               |           |
    +-----------------------|--------------------------------------------+
     B.2  Link State Table

     +-----------|--------+-------+------------------+
     |    Link   |  Zone  | ==> Link  |   Link State     |
            +---------+--------|----| |----+-----------+-----+-----------+
     |   Source  | Radius | +---\  +----------|--+--+   +--+
                                    +-----/ State |   Information #  |
     |  |...|    Addr   |        |
                                             +----------|--+--+   +--+
                                               Next Hop      route
                                               node  ID      metrics

   C.  Interfaces

        C.1  Higher Layer (N/A)
        C.2  Lower Layer (IP)
            C.1.1  Send()       (specified in IP standard)
            C.1.2  Deliver()    (specified in IP standard)
        C.3  NDM
            C.3.1  Neighbor_Lost(host,mask,metric)
                Used by the NDM to notify the IARP that direct contact
                has been lost with "host" (with subnet mask "mask").
                Any node/link quality measurements are reported in
                the "metric" list.
            C.3.2  Neighbor_Found(host,mask,metric)
                Used by the NDM to notify the IARP that direct contact
                has been confirmed with "host" (with subnet mask "mask").
                Any node/link quality measurements are reported in   |                  |
     | (node_id) | (int)  | (int) | (ls_info list)## |
     +-----------|--------+-------+------------------|
     |           |        |       |                  |
     |           |        |-------+------------------|
     |           |        |       |                  |
     |           |        |-------+------------------|
     |           |        |       |                  |
     |-----------|--------+-------+------------------|
     |           |        |       |                  |
     |-----------|--------+-------+------------------|
     |           |        |       |                  |
     |           |        |-------+------------------|
     |           |        |       |                  |
     +-----------|-----------------------------------+

      #  The first link state entry for each link source
         contains the "metric" list.
        C.4  IERP
            C.4.1  Zone_Node_Lost(host)
                Used by IARP complete link state information
         corresponding to notify the IERP that a node no longer
                exists within the routing zone.

Haas, Pearlman                Expires December 1999                  [Page
11]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   D. Link State Machine

        The IARP protocol consists of ID.
         Subsequent entries contain only one changes of a single
         link state.

         A FULL link state (IDLE). Therefore,
      no entry of link state transitions need to be specified. The IARP immediately
      acts upon an event #k and then returns back to the IDLE state.

        Notes:  1) X is used as
         a label for the host running this PARTIAL entry of link state
                   machine.
              2) INF is #(k+1) can be
         merged into a reserved field value corresponding to
                   "infinity".

        D.1
            Event:   An IARP packet is received containing route 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 to a destination D. The hop count
                   associated with the received route is LESS THAN
                   OR EQUAL TO
                               has been forwarded)
   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 routing zone radius.  The
                   second next-hop is EQUAL to X.

            Action:  NONE

        D.2
            Event:   An IARP packet is received containing route
                   information process of sending link state updates)

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

   B.5  New Neighbors List
        (list of new neighbors to receive a destination D. The hop count
                   associated with the received route is LESS THAN
                   the copy Link State Table,
         upon completion of updates)

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

   B.6  Former Routing Zone Nodes
        (list of routing zone radius.  The second next-hop
                   is NOT EQUAL nodes, prior to X.

          Action:  The received route is recorded 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)
        C.3  NDM
            C.3.1  Neighbor_Lost(node,mask,metric)
                Used by the Intrazone
                   Routing Table. If NDM to notify the received route is shorter
                   than IARP that direct contact
                has been lost with "node" (with subnet mask "mask").
                Any node/link quality measurements are reported in
                the previous shortest route "metric" list.
            C.3.2  Neighbor_Found(node,mask,metric)
                Used by the NDM to D, then a new notify the IARP packet containing route information to D
                   through X is broadcasted.

        D.3
            Event:   An 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 packet is received containing route
                   information to notify the IERP that a destination D. The hop count is
                   EQUAL TO node no longer
                exists within the routing zone radius. zone.

   D.  State Machine

        The second
                   next-hop is NOT EQUAL IARP protocol consists of only one state (IDLE). Therefore,
        no state transitions need to X.

            Action: be specified. The received route IARP immediately
        acts upon an event and then returns back to the IDLE state.

        Notes:  1) X is recorded in used as a label for the Intrazone
                   Routing Table.

Haas, Pearlman                Expires December 1999                  [Page
12]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        D.4 node running this state
                   machine.

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

            Action:  The route to D link state update is removed from recorded in the Intrazone
                   Routing Link State
                     Table.
                        1)  If more link state updates are pending,
                     then the Intrazone Routing Table still
                        contains a route IARP returns to D an idle state.  Otherwise,
                     X rebuilds its routing table and the length bordercast trees
                     of its routing zone nodes.  Links that lie outside of
                     the
                        shortest route has increased due to the route
                        removal, then the an IARP packet containing routing zone are removed from the
                        shortest route to D through Link State
                     Table.  X is broadcasted.
                        2) If sends its neighbors all previously
                     unforwarded link state updates from its NON-
                     peripheral nodes.  Finally, all neighbors in the Intrazone Routing Table contains no
                        more routes to D, then an IARP packet containing
                        a route to D through X with hop count of INF is
                        broadcast.  A "Host Lost" interrupt is
                        generated to alert New
                     Neighbor List are sent the IERP that D has moved
                        beyond link states of X's NON-
                     peripheral nodes, and the routing zone.

        D.5 New Neighbor List is
                     cleared.

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

            Action:  For each destination in  X's Intrazone Routing
                   Table, an IARP packet is sent new link to N containing is recorded in the
                   best route to that destination. An IARP packet Link State Table
                     and N is added to the New Neighbors List.  If more
                     link state updates are pending, then broadcasted containing the 1 hop route IARP returns
                     to N
                   through X.

        D.6 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 host node N is no longer a neighbor of X X.

            Action:  The one hop route lost link to neighbor N is removed from the
                   Intrazone Routing Table.
                        1) If the Intrazone Routing Link
                     State Table still
                        contains a route to N and the length of the
                        shortest route has increased due to the route
                        removal, then the an IARP packet containing the
                        shortest route to N through X is broadcasted.
                        2) If removed from the Intrazone Routing Table contains no New Neighbor
                     List.  If more routes to N, link state updates are pending, then an
                     the IARP packet containing
                        a route returns to D through an idle state.  Otherwise, X with hop count of INF is
                        broadcast. A "Host Lost" interrupt is generated
                        to alert
                     rebuilds its routing table and the IERP bordercast trees
                     of its routing zone nodes.  Links that D has moved beyond lie outside of
                     the routing zone.

Haas, Pearlman                Expires December 1999                  [Page
13]

INTERNET DRAFT              The Zone Routing Protocol                June
1999 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: {dest, {link_source, link_dest, pk_source, state_id,
                            radius, flags, mask, next_hop_1, next_hop_2,
route_metric,
                            hop_count} 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.

    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 arrived)
           extract(packet) (packet)
         {
             extract(packet);
             my_link_changed = FALSE;
         }
         else
         {
           {dest,mask,metric} <-- intrpt
           next_hop_1=dest
            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")
           {
              for d
                link_status = each node in Intrazone_Routing_Table
              {
                 best_route UP;
            else
               link_status = get_shortest_route(Intrazone_Routing_Table,d)
                 mask DOWN;

            my_link_changed = get_mask(Intrazone_Routing_Table, d)
                 if (best_route->hop_count <  ROUTING_ZONE_RADIUS)
                 {
                    packet<--{d,mask,MY_ID,best_route->next_hop,
                              best_route->metric,best_route->hop_count+1}
                    send(packet,dest)
                 }
              }
              hop_count=1
           }
           else
              hop_count=INF TRUE;
        }

        former_best_route

        // Record link state information in Link State Table
        add(Pending_Link_State_List, pk_source_id);
        status = get_shortest_route(Intrazone_Routing_Table,dest)

Haas, Pearlman                Expires December 1999                  [Page
14]

INTERNET DRAFT              The Zone Routing Protocol                June
1999 add(Link_State_Table, link_source, link_dest, mask,
                     radius, link_metric, state_id, flags);

        // Determine if (hop_count < INF)
        {
             if(next_hop_2 != MY_ID) received link state information is new
        if (status == NEW_LINK_INFO)
        {
              link_metric  = get_metric(Intrazone_Routing_Table, next_hop_1)
              route_metric = add_metric(route_metric, link_metric)
              add(Intrazone_Routing_Table, {dest,mask,next_hop_1,
                                            route_metric,hop_count})
           }
        }
        else
             remove(Intrazone_Routing_Table, {dest, next_hop_1})
        best_route
           cum_status = get_shortest_route(Intrazone_Routing_Table,dest)
        if (best_route != NULL) UPDATE_IN_PROGRESS;
           if(my_link_changed)
           {
              if (best_route->hop_count != former_best_route->hop_count
                    (AND) best_route->hop_count < ROUTING_ZONE_RADIUS)
           {
              packet <-- {dest,mask,MY_ID,best_route->next_hop,
                          best_route->metric,best_route->hop_count+1}
              send(packet,BROADCAST)
           }
        } (link_status == UP)
                 add(New_Neighbor_List, link_dest);
              else
        {
           force_intrpt("IERP","Zone Node Lost",{dest})
           packet <-- {dest, mask, MY_ID, MY_ID, NULL, INF}
           send(packet,BROADCAST)
                 remove(New_Neighbor_List, link_dest);
              MY_LINK_STATE_ID++;
           }

Haas, Pearlman                Expires December 1999                  [Page
15]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

4.1.2  Link State IARP
   In this version of the IARP, nodes compute intrazone routes based
        }

        // Release hold on the
   link state (neighbor connectivity) of each routing zone node. A node may
   receive link state updates either from an IARP pk_source when all link state packet or information
        // from
   an interrupt generated by its Neighbor Discovery / Maintenance (NDM)
   process*.  Link states are maintained in a Link State Table.  When pk_source is received
        if(all_updates == COMPLETE)
            remove(Pending_Link_State_List, pk_source);
        // Once all pending link state updates have information has been received (full link state updates
may
   contain multiple links and span multiple packets), 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 table is
   recomputed, using a minimum spanning tree algorithm. zone
            for((EACH) node (BELONGING TO) Routing_Table)
            {
               if(Routing_Table[node].Intrazone)
                   add(Former_Routing_Zone_Nodes, node);
            }

            // The Link State Table
   is then updated to remove should not contain links that lie outside of
            // beyond the (extended) routing zone.
All
   new link state updates for non-peripheral
            // 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
forwarded
   to 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 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.

   * IARP relies on the services of a separate protocol (referred to
     here as the Neighbor Discovery/Maintenance Protocol) to provide
     current information about a host's neighbors.  At the least, this state information must include that lies
            // inside the IP addresses of extended routing zone
            broadcast_link_state_updates(Link_State_Table);

            // Send all link state information that lies inside the neighbors.
     The IARP can be readily configured
            // extended routing zone to support supplemental
     link quality metrics.

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

Haas, Pearlman                Expires December 1999                  [Page
16]

INTERNET DRAFT each new neighbor
            for ((EACH) node (BELONGING TO) New_Neighbor_List))
               send_link_state_table(Link_State_Table, node);
            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);
         }

4.2 IntErzone Routing Protocol (IERP)

   The Zone Interzone Routing Protocol                June
1999

        Field Description:

        * Link Source Address           (32 bits)
            IP address of (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 reported link's source node.

        * Link Destination Address      (32 bits)
            IP address
   network with bordercasted route queries.*

   This version of the reported link's destination node.

        * Packet Source Address         (32 bits)
            IP address of IERP extends the node that sent this packet.
            (Used to account basic query / reply mechanism
   described in Section 3.  A node issues a ROUTE_QUERY when a route is
   needed for any outstanding link state information)

        * Link State ID                 (16 bits)
            Sequence number used 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 track its peripheral nodes, using the link state history of 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 Link Source node.

        * Zone Radius                   (8 bits) Routing zone radius of Table and Temporary Query Cache.  The previous
   hop node address is then overwritten in the link's source node.  Determines packet by the
            extent that link state information propagates.

        * Flags                         (8 bits)
             Flags(0)   Full Link Information
                 Indicates whether current
   node's address.  If the ROUTE_QUERY destination lies within this link state information was sent as:
                          (0) node's
   routing zone, then a PARTIAL link state update
                                      OR
                          (1) part of ROUTE_REPLY is sent to the query source and a FULL update  of all
   QUERY_EXTENSION is forwarded to the
                              link source's current links

             Flags(1)   Current Link State Update
                 Indicates whether more link state information query destination.  Otherwise, the
   ROUTE_QUERY 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.

Haas, Pearlman                Expires December 1999                  [Page
17]

INTERNET DRAFT sent back down to the BRP.

   The Zone Routing Protocol                June
1999

        * Node/Link Metrics             (X * 32 bits)
                This section of QUERY_EXTENSION performs route accumulation in distributed manner,
   similar to the packet ROUTE_QUERY.  When the QUERY_EXTENSION arrives at the
   destination, a next hop route is used formed back to report the quality of
                this link (or link 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 node).

                * Metric Type           (8 bits)
                      Type 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 metric being reported
                      (based on pre-defined metric types) various route quality metrics.

   * Metric Value          (16 bits)
                      Value of node / link metric specified The bordercast service is provided by Metric Type

    B.  Data Structures

    B.1  Intrazone Routing Table

    +---------+--------|-----------------------------------------+
    |  Dest   | Subnet |                Routes the Bordercast Resolution
     Protocol (BRP)

                       +-----+                    +-----+       +-----+
                       |  S  |  Addr      . . . .       |  Mask  |-----------+-----------+-----+-----------+  Y  | . . . |  D  |
                       +-----+                    +-----+       +-----+

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

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

              Sequence of the IERP Route Discovery Stages
   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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | ==> |    M-1    |
    +---------+--------|-----------+-----------+-----+-----------+
    |         |        |           |           | ==> |           |
    |---------+--------|-----------|-----------|-----|-----------|
    |         |        |           |           | ==> |           |
    |---------+--------|-----------|-----------|-----|-----------|
    |         |        |     Type      |      TTL      |   Hop Count   |     Flags     | ==>
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        Current Hop Ptr        |
    +---------+--------|----| |----+-----------+-----+-----------+ Num Dests = D | Num Nodes = N |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | +---\  +----------|--+--+   +--+
                            +-----/            Query ID           |           Reserved            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  |...|                 Query/Route Source Address                    |
                                     +----------|--+--+   +--+
                                       Next Hop      route
                                       node ID      metrics

Haas, Pearlman                Expires December 1999                  [Page
18]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

     B.2  Link State Table

     +--------+--------+------------+
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |  Link              Query/Route Destination (1) Address              |  Zone   | Link State
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |        Link State Information
    | Source              Query/Route Destination (2) Address              | Radius   |     ID
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
     +--------+--------+------------+     +---|---|-----|-+
+---|---|-----|-+
                                   | |                                  |            |--->
                                   | |                                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
                                   \ /                                  |     ||
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |      (a) (b)  (c) (d)
     :   ||   :   ||   :     ||     :
     :  \||/  :  \||/  :    \||/    :
    |   \/     Node      |   \/ Metric Type |D|         Metric Value          |     \/   |
     +--------+--------+------------+

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

                  **
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
        Field Description:

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

                ROUTE_QUERY:
                        request for each link an Interzone source
                       contains the complete link state information
                       corresponding route 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)

   B.3  Pending Link State List
        (list of neighbors in
                        destination specified by the process of sending link state updates)

        +----------+      +----------+        +----------+
        |          | ---> |          |  . . . |          |  (node addresses)
        +----------+      +----------+        +----------+

   B.4  New Neighbors List
        (list Destination
                        IP Address

                QUERY_EXTENSION:
                        extension of new neighbors to receive a copy Link State Table,
         upon completion of updates)

        +----------+      +----------+        +----------+
        |          | ---> |          |  . . . |          |  (node addresses)
        +----------+      +----------+        +----------+

Haas, Pearlman                Expires December 1999                  [Page
19]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   B.5  Former Routing Zone Nodes
        (list of routing zone nodes, prior QUERY packet sent from the
                        node that discovers the Destination to routing table updates)

        +----------+      +----------+        +----------+
        |          | ---> |          |  . . . |          |  (node addresses)
        +----------+      +----------+        +----------+

   C.  Interfaces

        C.1  Higher Layer (N/A)
        C.2  Lower Layer (IP)
            C.1.1  Send()       (specified in IP standard)
            C.1.2  Deliver()    (specified in IP standard)
        C.3  NDM
            C.3.1  Neighbor_Lost(host,mask,metric)
                Used by the NDM
                        Destination itself.

                ROUTE_REPLY:
                        response to notify a ROUTE_QUERY packet, sent from the IARP
                        node that direct contact
                has been lost with "host" (with subnet mask "mask").
                Any node/link quality measurements are reported in
                the "metric" list.
            C.3.2  Neighbor_Found(host,mask,metric)
                Used by discovers the NDM Destination back to notify the IARP that direct contact
                has been confirmed with "host" (with subnet mask "mask").
                Any node/link quality measurements are reported in
                        Source.  At a minimum, the "metric" list.
        C.4  IERP
            C.4.1  Zone_Node_Lost(host)
                Used by IARP ROUTE_REPLY contains
                        next-hop route information to notify the IERP that a node no longer
                exists within Destination.
                        (In general, returns the source route up to the
                        first node which has cached routing zone.

   D.  State Machine

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

        Notes:  1) X is used as a label for
                        the host running this state
                   machine.
                2) INF complete source route is returned.)

        * TTL (Time to Live)           (unsigned int)      (8 bits)
                Number of hops that a reserved route query may continue to
                propagate.  This field value corresponding allows a querying node to
                   "infinity".

        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 configure
                the IARP
                     returns to an idle state.  Otherwise, X rebuilds its
                     routing table.  Links that lie outside depth of a route search, in order to control the routing
zone
                     are removed
                amount of IERP traffic generated.

        * Hop Count                    (unsigned int)      (8 bits)
                Hop count from the Link State Table.  X sends its
                     neighbors all previously unforwarded link state updates source to current node (ROUTE_QUERY,
                QUERY_EXTENSION) or hop count from its NON-peripheral nodes.  Finally, all neighbors
                     in the New Neighbor List are sent source to route
                destination (ROUTE_REPLY, ROUTE_ACCUMULATION,
                ROUTE_OPTIMIZATION).

        * Flags                        (boolean)           (8 bits)
                 Flags(0)        ANY destination (0) / ALL destination (1)
                        In the link states case of
X's
                     NON-peripheral nodes, and multiple destinations, specifies
                        whether the New Neighbor List is
cleared.

Haas, Pearlman                Expires December 1999                  [Page
20]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        D.2
            Event:   A "Neighbor Found" interrupt is received, indicating ROUTE_QUERY should return routes for
                        ANY specified destination, or ALL specified
                        destinations.

                        In the discovery case of a neighbor N.

            Action:  X's new link to N is recorded in single MULTICAST IP address,
                        specifies whether the Link State Table
and
                     N is added ROUTE_QUERY should return
                        routes to ANY member of the New Neighbors List.  If more link
state
                     updates are pending, then multicast group, or
                        ALL members of the IARP returns to an idle
                     state.  Otherwise, X rebuilds its routing table.  Links
                     that lie outside multicast group.

                 Flags(1..7)     RESERVED for future use
        * Current Hop Pointer          (unsigned int)      (16 bits)
                INDEX of the routing zone are removed from route (see below) corresponding to the
                     Link State Table.  X sends its neighbors all previously
                     unforwarded link state updates from its NON-peripheral
                     nodes.  Finally, all neighbors route
                node that has most recently received this packet.  (the
                first node in the New Neighbor List
                     are sent the link states route has an index of X's NON-peripheral nodes,
and 1).

        * Number of Destinations = D   (unsigned int)      (8 bits)
                Number of destinations included in the New Neighbor List is cleared.

        D.3
            Event:   A "Neighbor Lost" interrupt is received, indicating
                     that node N is no longer route query/reply
                packet.  This allows multiple route discoveries to be
                consolidated into a neighbor of X.

            Action: common route query process.  The lost link to neighbor N
                multiple query destinations feature is removed from particularly useful
                for routing to a multicast group with known members, or
                for locating downstream nodes during the Link
                     State Table and route repair
                phase.

        * Number of Nodes = 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.  Links that lie outside          (unsigned int)      (8 bits)
                Number of nodes IP addresses appearing in the routing
                     zone are removed from route
                specification.

        * Query ID                     (unsigned int)      (16 bits)
                Sequence number which, along with the Link State Table.  X sends
its
                     neighbors all previously unforwarded link state updates
                     from its NON-peripheral nodes.  Finally, all neighbors Query Source Address
                (see below) uniquely identifies any ROUTE_QUERY in the New Neighbor List are sent
                network.

        * Query/Route Source Address   (node_id)           (32 bits)
                IP address of the link states node that initiates the ROUTE_QUERY.
                In subsequent stages, this corresponds to the IP address
                of
X's
                     NON-peripheral nodes, and the New Neighbor discovered route's source node.

        * Query/Route Destination Addresses  (node_id)     (D * 32 bits)
                List is
                     cleared.

    E.  Pseudocode Implementation

        We define two complimentary operations of IP addresses to be located during the ROUTE_QUERY
                phase.  (Either ANY or ALL addresses, depending on packets:
        extract(packet) and load(packet)

            extract (packet)
                extracts the fields
                setting of Flags(0))  In subsequent stages, this field
                contains the IARP packet to IP address of 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) discovered route's (single)
                destination node.

        * mask            -> flag(3) Route                        (node_id)           (N * link_status     -> flag(4)

            load (packet)
                loads 32 bits)
                Variable length field that contains the values recorded IP
                addresses of nodes along the aforementioned variables into path traveled by this
                ROUTE_QUERY packet from the fields of the IARP packet.

Haas, Pearlman                Expires December 1999                  [Page
21]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    E.1  Update Intrazone Routing Table

        if (packet arrived)
        {
            extract(packet)
            my_link_changed = FALSE
        }
        else
        {
            {link_dest,mask,link_metric} <-- intrpt
            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
        }

        add(Pending_Link_State_List, link_from_id)
        status = add(Link_State_Table,link_source, link_dest, mask, radius,
                     link_metric, state_id, flags)
        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++
           }
        }

        if(all_updates == COMPLETE)
            remove(Pending_Link_State_List, link_from_id)

Haas, Pearlman                Expires December 1999                  [Page
22]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        if(empty(Pending_Link_State_List) (AND)
                 cum_status == UPDATE_IN_PROGRESS)
        {
            for(each node (BELONGING TO) Intrazone_Routing_Table)
               add(Former_Routing_Zone_Nodes, node)

            rebuild = TRUE;
            while (rebuild)
            {
               Intrazone_Routing_Table
                                    =
construct_spanning_tree(Link_State_Table);
               rebuild = update(Link_State_Table);
            }

            broadcast_link_state_updates(Link_State_Table);

            for (each node (BELONGING TO) New_Neighbor_List))
               send_link_state_table(Link_State_Table, node);

            clear(New_Neighbor_List)

            cum_status = UPDATE_COMPLETE;

            for (each node (BELONGING TO) Former_Routing_Zone_Nodes)
            {
               if(node !(BELONGS TO) Intrazone_Routing_Table)
                  force_intrpt("IERP","Zone Node Lost",{node})
            }
            clear(Former_Routing_Zone_Nodes)
        }

Haas, Pearlman                Expires December 1999                  [Page
23]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

4.2 IntErzone Routing Protocol (IERP)

   The Interzone Routing Protocol (IERP) is responsible for discovering
   and maintaining routes Query Source.  In subsequent
                stages (after a route to hosts which are beyond a node's routing
   zone.  The IERP acquires routing information reactively, exploiting
   the knowledge Query Destination has been
                discovered), this set of IP addresses provides a partial
                specification of the routing zone topology through route between the bordercasting
   delivery service. Route Source and
                Route Destination.

        * Node/Segment Metrics         (metric)            (X * 32 bits)
                This version optional section of the IERP extends packet can be used to
                record a variety of node and segment quality measurements.
                (In this context, a segment refers to the basic query / reply mechanism
   described communication
                path between consecutive nodes in Section 3.  In the basic protocol, queries are
   terminated before reaching packet's accumulated
                route.  In the query destination.  This provides case of neighboring nodes, a faster response segment is
                equivalent to a (one-hop) link).

                * Node                 (char)              (8 bits)
                      Index of the route query than if the destination, D,
   were corresponding to respond directly.  However, because D never receives the
   query, it does not acquire a route back 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)|
          ... +--------------|
              |              |
          ... +--------------|
              |              |
          ... +--------------|
              |              |
          ... +--------------+
    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 source, S.  If BRP.
            C.2.2  Deliver(packet,BRP_cache_ID)
                Used by the
   D needs BRP to send deliver data back packet to S (which is often the case, given the
   bi-directional nature of many applications), a separate route query
   from D to S would have to be initiated.  This substantial overhead
   is avoided 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 having the query forwarded IARP to D, by notify the node Y IERP that
   discovers D in its a node has left
                the routing zone.  We refer 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 this be specified. The IERP immediately
        acts upon an event and then returns back to the IDLE state.

        Note:  1) X is used as a
   QUERY_EXTENSION.

   Both label for the source and destination can acquire 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 each other
   through the BRP H
                     is initiated.

        D.2
            Event:   ICMP issues a "Host_Unreachable" message, triggering
                     a route accumulation mechanisms (to be discussed
   later).  Distributing discovery for unreachable host H.

            Action:  A FULL depth route information in 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 caches IP addresses of the route's nodes can significantly reduce source and destination
                     IP addresses (X and H).  Finally, the size of ROUTE_QUERY
                     packet is sent to the BRP to be bordercasted.

        D.3
            Event:   The IERP packets
   and provide for or ICMP (via source_route_failed()) triggers
                     a faster query response.  On "Repair" message, indicating that the other hand, QOS
   requirements for a particular application may favor a source next hop
                     H specified route.  (rather than in a distributed next-hop approach).
   Source routing requires that the discovered source route information cannot be
   accumulated in the IERP packets, rather than cached.  This IERP
   implementation satisfies the demands for rapid query response
   and source routing support by two stages of route reporting.  In the
   first two stages, route information is cached by the route's nodes
   (when possible).  Next-hop found locally.

            Action:  A limited depth route are quickly returned discovery to the source
   in ROUTE_REPLY packets H is initiated.
                     X's query_id is incremented and forwarded assigned to the destination in QUERY_
   EXTENSION packets.  At this point, bi-directional connectivity a new
                     ROUTE_QUERY packet.  The route is
   established.  In initialized with
                     the third stage, IP addresses of the route's source and destination can
   provide each other with complete source routes, by sending each
   other ROUTE_ACCUMULATION packets.  As these packets traverse
                     IP addresses (X and H). Finally, the
   route, ROUTE_QUERY
                     packet is sent to the cached 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 in route metrics are
                     updated and compressed.

                     X copies the packets,
   thereby constructing ROUTE_QUERY packet's contents to a
                     ROUTE_REPLY.  A loop-free return path is selected
                     from the desired source route.

   Variations Temporary Query Cache (i.e. based on this IERP implementation can be realized by combining
   or eliminating some of these stages.  For example, if source routing
   is
                     "Diversity Injection").  X also forwards a
                     QUERY_EXTENSION to discovered query destination.  If
                     the ROUTE_QUERY packet has not desired, traveled too deep into
                     the ROUTE_ACCUMULATION stage can network (i.e. TTL > 0) AND there are still more
                     destinations to be eliminated.
   Also, if all of discovered, then the route's nodes elect not ROUTE_QUERY
                     is sent down to cache 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 (perhaps due to storage limitations), then (for the ROUTE_
   REPLY and QUERY_EXTENSION packets essentially serve the role of
   ROUTE_ACCUMULATION packets, obviating the need for a separate
   ROUTE_ACCUMULATION stage.

Haas, Pearlman                Expires December 1999                  [Page
24]

INTERNET DRAFT              The Zone
                     source) is recorded in X's Routing Protocol                June
1999

   Because each node proactively maintains the local topology of its
   routing zone, it Table and
                     Temporary Query Cache.  The accumulated route is not necessary for a source
                     replaced by X's address and any accumulated route
                     metrics are updated and compressed.  The ROUTE_QUERY
                     packet is sent down to specify
   every hop along the route (i.e. strict source routing). BRP to be relayed outward.

        D.6
            Event:   A properly
   chosen subset of the complete source QUERY_EXTENSION packet is received.

            Action:  The packet's accumulated route can be used to specify information (for the
                     source) is recorded in X's Routing Table.  The
                     accumulated route to is replaced by X's address and any
                     accumulated route metrics are updated and compressed.
                     If X is not the query destination, and where desirable, then X forwards the reverse route
   back to
                     message toward the source.  The IERP supports such an optimization destination (directly through
   a final ROUTE_OPTIMIZATION stage. IP)
        D.7
            Event:   A ROUTE_REPLY packet is received.

            Action:  The details of the packet's accumulated route
   optimization are described in the BRP specification.  Upon
   completion of information (for the ROUTE_OPTIMIZATION stage, sufficient routing zone
   membership
                     destination) is acquired for each node recorded in X's Routing Table.  X
                     adds its address to the accumulated route so that the source
   route may be reduced (by translating this route reduction into
   an appropriate set covering problem, and employing a suitable
   heuristic).

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

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

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

  (3)  provide                          ROUTE_ACCUMULATION
(OPTIONAL)
       source route        |---------------------------------------->
                           <========================================|

  (4)  optimize                         ROUTE_OPTIMIZATION
(OPTIONAL)
       source route        <----------------------------------------|
                           |========================================>

              Sequence of the IERP Route Discovery Stages

Haas, Pearlman                Expires December 1999                  [Page
25]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   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    |    ROF Ptr    | Num Dests = D | Num Nodes = N |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | 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 ID           |            Reply ID           |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Query/Route Source Address                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Replying Node Address                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Bad Link Source Address                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |              Query/Route Destination (1) Address              |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |              Query/Route Destination (2) Address              |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                   | |                                  |
                                   | |                                Dests
                                  \| |/                                 |
                                   \ /                                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |              Query/Route Destination (D) Address              |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |                       Next 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 Address                       |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |                       Next BRP Address                        |  BRP
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fields
    |                       Prev 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 Address                       |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |                 Intermediate packet.
                load(packet) automatically computes the values of:
                              num_dests = |dests|
                              num_nodes = |routes|
        E.1 Routing Zone 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
                                  \| |/
Metric(s)
                                   \ /                                  |

Haas, Pearlman                Expires December 1999                  [Page
26]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |     Node      | Metric Type |D|         Metric Value          |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |                 Route Optimization Flags (Node 0 == Source)   |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |                 Route Optimization Flags (Node 1)             |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                   | |                                  |
                                   | |                                  R
                                  \| |/                                 O
                                   \ /                                  F
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |                 Route Optimization Flags (Node N)             |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |                 Route Optimization Flags (Node N+1 == Dest)   |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--

        Field Description:

        * Type                                 (8 bits)
                Identifies the type of IERP packet.  The current version
                 of IERP contains five 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 Lost
            args: (lost_node)

            // Determine if lost_node belongs to any stored routes.
            // If so, the
                        Destination itself.

                ROUTE_REPLY:
                        response to a ROUTE_QUERY packet, sent route should be removed from the node
                        that discovers the Destination back to the Source.
                        At
            // Routing Table and a minimum, the ROUTE_REPLY contains
                        next-hop route information to the Destination.
                        (In general, returns the source repair triggered
            // (if proactive route up to
                        the first repairs are enabled)
            repair_link = FALSE;
            for((EACH) node which has cached routing
                        information.  If no nodes have cached routing
                        information, then the complete source (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
                        returned.)

                ROUTE_ACCUMULATION (optional):
                        sent by the Source to the Destination, in
                        response to a ROUTE_REPLY, initialized and sent by the
                        Destination down to the Source, in response BRP
             // to a
                        QUERY_EXTENSION.  Routing information cached
                        at the route's nodes is accumulated in this
                        packet, providing a complete 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 at     = NULL;
             current_hop_ptr = 0;

             load (packet);
             send ((packet, source, query_id, NULL), BRP);
        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 destination of this packet.

Haas, Pearlman                Expires December 1999                  [Page
27]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

                ROUTE_OPTIMIZATION (optional):
                        sent by the Source to the Destination, Table and by the
                        Destination to the Source, in response to a
                        ROUTE_ACCUMULATION packet.  Route Optimization
                        Flags (ROF) 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 appended 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 packet,
                        reflecting destination is known
                            found_any       = TRUE;
                            dests           = dest;
                            remove(dest, DESTS);

                            // Forward query directly to destination, so
                            // that the mutual destination will have some routing zone membership
                        of each node in
                            // information back to the source route.

        * TTL (Time to Live)                   (8 bits)
                Number of hops that a
                            type            = QUERY_EXTENSION;
                            prev_hops       = NULL;
                            next_hops       = Routing_Table[dest].route;
                            route query may continue to
                propagate. This field allows a querying node           = {prev_hops,MY_ID,next_hops};
                            current_hop_ptr = |prev_hops|+1;
                            load(packet);
                            send((packet,next_hops(1)),IP);
                            // Send reply back to
                configure the depth of a 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 search, in order           = {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
                control 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 amount of IERP traffic generated.

        * Hop Count                            (8 bits)
                Hop count 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);
                    // 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 to current node (ROUTE_QUERY,
                QUERY_EXTENSION) or hop count
                    if(MY_ID != source)
                    {
                        // Choose a loopfree return path from source 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;
            }

4.3  Bordercast Resolution Protocol (BRP)

   The BRP provides the "bordercasting" message delivery service, here
   used to forward IERP route
destination
                (ROUTE_REPLY, ROUTE_ACCUMULATION, ROUTE_OPTIMIZATION).

        * Flags                                (8 bits)
                 Flags(0)        ANY destination (0) / ALL destination (1)
                        In queries.  Messages are relayed from a
   bordercasting node outward to its peripheral nodes, along a
   bordercast (multicast) tree.  Although the case intended recipients of multiple destinations, specifies
whether
   the ROUTE_QUERY should return routes for ANY
specified
                        destination, or ALL specified destinations.

                        In bordercast are the case of a single MULTICAST IP address,
specifies
                        whether peripheral nodes, the ROUTE_QUERY should return routes to ANY
                        member of BRP may deliver the multicast group, or ALL members of
   bordercast message up to the
                        multicast group.

                 Flags(1)       Passed Bad Link Source
                        In higher layer application (in this case,
   the case of IERP) at EVERY hop.  This may be necessary for applications that
   use bordercasting, but are generally not "routing zone aware".

   When a "route repair", indicates node receives a bordercasted message, it first needs to determine
   whether the
                        ROUTE_REPLY has passed message should be forwarded.  Clearly, the Bad Link Source node.

                 Flags(2..7)     RESERVED for future use

        * Current                              (8 bits)
                INDEX of node should
   only forward the route (see below) corresponding message if it belongs to the route
node
                that has most recently received this packet.  (the first bordercast tree.
   Furthermore, if the node
                in is the route (peripheral node) bordercast recipient,
   it would re-bordercast the message, but only if it has an index of 1).

        * ROF Pointer                          (8 bits)
                Pointer to not been a bordercast
   recipient before AND it does not lie inside the starting location routing zone of a
   detected "previously bordercasted" node.

   If the Route Optimization
                Flags (ROUTE_OPTIMIZATION phase).  The ROF Pointer is
measured
                in units of 32 bit words from node decides not to discard the front message, it next determines which
   of the packet.

        * Number of Destinations = D           (8 bits)
                Number current bordercast tree's downstream branches will be dropped.
   A downstream branch will be dropped if each of destinations included in the route query/reply
packet.
                This allows multiple route discoveries branch's downstream
   peripheral nodes either has had a bordercast message relayed to be consolidated
                into it by
   this node OR lies inside the routing zone of a common route query process. detected previously
   bordercasted node.

   The multiple query
                destinations feature is particularly  useful for routing BRP delivers the message up to
a
                multicast group with known members, or for locating
downstream
                nodes during the route repair phase.

Haas, Pearlman                Expires December 1999                  [Page
28]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        * Number of Nodes = 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                  (8 C A P S U L A T E D     P A C K E T            |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        * Message Source Address       (node_id)           (32 bits)
                Number of nodes
                IP addresses appearing in address of the route
                specification. node that initiates the message.

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

        * Reply ID                             (16 bits)
                 Sequence number which, along with the Replying Node Address
                 (see below) uniquely identifies any ROUTE_REPLY in the
network

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

        * Replying Node Address                (32 bits)
                IP address of Encapsulated Packet          (packet)

        *** note:  Within the node that initiates context of the ROUTE_REPLY.  Note
                that this is usually NOT ZRP, the destination node.

        * Bad Link Message Source
                   Address              (32 bits)
                Used during route repairs.  Contains and Message ID can assume the same values
                   as the IP Address 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 source of routes failed link.

        * Query/Route Destination Addresses    (D * 32 bits)
                List contents of IP addresses to be located during
                                the ROUTE_QUERY
phase.
                (Either ANY or ALL addresses, depending on encapsulated IERP packet.
                           (b)  The BRP knows the setting format of
                Flags(0))
                In subsequent stages, this field contains the IP address IERP packet.

                   For this version of the
                discovered route's (single) destination node.

        * Next IERP Address                    (32 bits)
                IP address of ZRP, both (a) and (b) are true.
                   However, we provide the next IERP recipient

        * Next BRP Address                     (32 bits)
                IP address with its own Message ID and
                   Message Source fields for future support of the next BRP recipient.
                (i.e. next hop to the next IERP recipient)

        * generic
                   higher layer applications.

    B.  Data Structures

        B.1  Routing Table          (see IARP description)

        B.2  Bordercast Tree Table  (see IARP description)
        B.3  Detected Messages Cache

             +------------------------|--------------------------+ ...
             | Message |  Message ID  | BRP_cache_ID |   Prev IERP Address                    (32 bits)
                IP address of    |
             |  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 previous IERP recipient

        * Route                                (N * 32 bits)
                Variable length field that contains the recorded IP
addresses
                of nodes along the path traveled by this ROUTE_QUERY to request packet
                from transmission.
            C.2.2  Deliver(packet, BRP_cache_ID)
                Used by the Query Source.
                In subsequent stages (after a route BRP to deliver a Query Destination
has
                been discovered), this set of data packet up to IERP.
        C.2  Lower Layer (IP)
            C.2.1  Send()       (specified in IP addresses provides a
partial
                specification of the route between the Route Source and
Route
                Destination.

Haas, Pearlman                Expires December 1999                  [Page
29]

INTERNET DRAFT standard)
            C.2.2  Deliver()    (specified in IP standard)

    D.  State Machine

      The Zone Routing Protocol                June
1999

        * Node/Segment Metrics                    (X * 32 bits)
                This optional section BRP protocol consists of the packet can be used to
                record a variety of node only one state (IDLE).  Therefore,
      no state transitions need to be specified. The BRP immediately
      acts upon an event and segment quality measurements.
                (In this context, a segment refers then returns back to the communication path
                between consecutive nodes in the packet's accumulated route.
                In the case of neighboring nodes, a segment IDLE state.

      Notes: 1) X is equivalent to used as a (one-hop) link).

                * Node                         (8 bits)
                      Index of label for the route corresponding node running this state
                machine.

      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 a particular node.

                * Metric Type                  (7 bits)
                      Type of metric being
                     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
                      (based on pre-defined metric types)

                * Direction Flag               (1 bit)
                      For segment metrics, specifies either in
                     it's Detected Messages Cache (and referenced by
                     BRP_cache_ID).  X then relays the upstream
                      segment (toward Query/Route Source) or message to the
                     designated downstream
                      segment (toward Query/Route Dest).
                                    upstream   = 0
                                    downstream = 1

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

        * ROF (Route Optimization Flags)       ((N+2) * 32*ceil((N+2)/32)
bits)
                The k-th bit of neighbors.

      D.3
            Event:   A message is received from the n-th ROF subfield indicates whether
                Node k IP.

            Action:  The message is located within Node n's routing zone.
                This routing zone membership information, collected
                during terminated under the optional ROUTE_OPTIMIZATION stage, may be
                used following
                     conditions:
                     (1) X does not belong to determine the shortest possible specification
                for bordercast tree of
                         prev_bcast.
                     (2) If X is the accumulated source route.

Haas, Pearlman                Expires December 1999                  [Page
30]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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

        B.2     Interzone Routing Table

            +---------+-----------------------------------------+
            |         |                 Routes                  |
            |  Dest   +-----------+-----------+-----+-----------+
            |         |     0     |     1     | ==> |    M-1    |
            +---------+-----------+-----------+-----+-----------+
            |         |           |           | ==> |           |
            |---------|-----------|-----------|-----|-----------|
            |         |           |           | ==> |           |
            |---------|-----------|-----------|-----|-----------|
            |         |    | |    |           | ==> |           |
            +---------+----| |----+-----------+-----+-----------+
                           | |
                           | +---\  +------|---|--+--+   +--+
                           +-----/  |      |   |  |  |...|  | --+   (node 1)
                                    +------|---|--+--+   +--+   |
                                 +------------------------------+
                                 |  +------|---|--+--+   +--+
                                 +->|      |   |  |  |...|  | --+   (node 2)
                                    +------|---|--+--+   +--+   |
                                                 | |            :
                                                \| |/           :
                                 :               \ /
                                 :
                                 |  +------|---|--+--+   +--+
                                 +->|      |   |  |  |...|  |       (node N)
                                    +------|---|--+--+   +--+
                                      (a)   (b)      (c) bordercast recipient and
                             (a)  Node ID X has already been a bordercast recipient.
                                            OR
                             (b)  Required Node Flag
                                                  (for Route Optimization)
                                         (c)  Node/Link Metric

    C.  Interfaces

        C.1  Higher Layer (N/A)
        C.2  Lower Layer (BRP)
            C.2.1   Send()      (same interface as IP send())
                Used by the IERP to request transmission of X is an
                IERP packet.
            C.2.2  Deliver()    (same interface as IP deliver())
                Used by 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 BRP to alert message then it re-bordercasts the IERP message.

                     Next, X decides which of the arrival current bordercast
                     tree's downstream branches (neighbor) will be dropped.
                     A downstream branch will be dropped if, for each of a
                data packet.
        C.3  IARP
            C.3.1  Zone_Node_Lost(host)
                Used by the IARP to notify
                     the IERP that a branch's downstream peripheral node D:
                             (a) X has left
                the routing zone
        C.4  ICMP
            C.4.1  Host_Unreachable()    (specified in ICMP standard)
            C.4.2  Source_Route_Failed() (specified in ICMP standard)

Haas, Pearlman                Expires December 1999                  [Page
31]

INTERNET DRAFT              The Zone Routing Protocol                June
1999 already relayed a message to D.  State Machine

        The IERP protocol consists
                                            OR
                             (b) D is an interior (i.e. non-peripheral)
                                 member of only one state (IDLE). Therefore,
        no state transitions need to be specified. The IERP immediately
        acts upon an event and then returns back to the IDLE state.

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

        D.1
            Event:   A "Zone_Node_Lost" interrupt is received,
                     indicating that the 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, then a route repair (limited depth route
                     discovery) to H is initiated.
        D.2
            Event:   A "Host_Unreachable" interrupt is received from the
                     ICMP, indicating an unknown destination host D.

            Action:  A full depth route discovery to D 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 D).  Finally, the ROUTE_QUERY
packet
                     is bordercasted.

        D.3
            Event:   A "Source_Route_Failed" or "Proactive_Repair"
                     interrupt is received, indicating that the next
                     hop, H, specified in a source route does not
                     appear within the detected previously
                                 bordercasted node's routing zone.

            Action:  A limited depth route discovery to H is initiated.
                     The query_id is incremented and assigned to a new
                     ROUTE_QUERY packet.  The route is initialized with the
                     valid portion of the failed route, and the bad link
                     address field is set with X's IP address, to indicate
                     the location of the route failure. zone

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

            Action: X copies delivers the ROUTE_QUERY packet's contents to a
                     ROUTE_REPLY, labelling it with its IP address and
                     incremented reply_id.
                     A QUERY_EXTENSION is sent message to the query destination.

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

            Action:  The ROUTE_QUERY packet is bordercasted.

Haas, Pearlman                Expires December 1999                  [Page
32]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        D.6
            Event:   A QUERY_EXTENSION packet is received.

            Action:  The packet contents are moved to a ROUTE_ACCUMULATION
                     packet.  The ROUTE_ACCUMULATION packet is sent to the
                     query source.
        D.7
            Event:   A ROUTE_REPLY packet is received.

            Action:  The packet contents are moved to a ROUTE_ACCUMULATION
                     packet.  The ROUTE_ACCUMULATION packet is sent to the
                     query destination.

        D.8
            Event:   A ROUTE_ACCUMULATION packet is received.  X is not
                     the final destination of this packet
                     (i.e. X != IERP_next).  This only occurs when the
                     accumulated route contains a repair

            Action:  The bad link is replaced by the path repair in the
                     Interzone Routing Table.

        D.9
            Event:   A ROUTE_ACCUMULATION packet is received. X is
                     either the route source or (route destination).

            Action:  The (reversed) accumulated route is added to the
                     Interzone Routing Table or replaces a failed route
                     if the packet specifies a bad link.  In addition,
                     if X is the ROUTE_ACCUMULATION destination, the
                     packet contents may be moved to a ROUTE_OPTIMIZATION
                     packet, which is then sent to the query destination
                     (query source).

        D.10
            Event:   A ROUTE_OPTIMIZATION packet is received.

            Action:  The routing zone membership information that is
                     collected in the ROUTE_OPTIMIZATION packet is
                     processed.  The resulting optimized route(s) are
                     added to the Interzone Routing Table.

    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,
                            bad_link_source, dests, next_IERP, next_BRP,
                            prev_IERP, route, metric, ROF}

Haas, Pearlman                Expires December 1999                  [Page
33]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

            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|

        E.1 Routing Zone Node Lost

            {lost_host} <-- intrpt
            repair_link = FALSE
            for host = each host in Interzone Routing Table
            {
              for (route = each Interzone route to host)
              {
                if (lost_host (EXISTS IN) route)
                {
                    if (PROACTIVE_REPAIRS_ENABLED)
                    {
                        removal_timer = ROUTE_QUERY_TIMEOUT
                        repair_link = TRUE
                    }
                    else
                        removal_timer = 0
                    schedule(
                        remove(Interzone_Routing_Table[host]->route(m)),
                        removal_timer)
                }
              }
            }
            if(repair_link)
            {
                 dests = lost_host
                force_intrpt("IERP","Proactive_Repair",{MY_ID,dests,ALL})
            }

        E.2  Initiate Route Discovery

            {source,dests,flag} <-- intrpt

            if (type(intrpt) == "Proactive_Repair" (OR)
                type(intrpt) == "Source_Route_Failed")
            {
                TTL              = MAX_REPAIR_HOPS
                bad_link_source  = MY_ID
            }
            else
            {
                TTL              = MAX_FULL_QUERY_HOPS
                bad_link_source  = NULL
            }
            query_id = MY_QUERY_ID++
            load (packet)
            send (packet, BORDERCAST)

Haas, Pearlman                Expires December 1999                  [Page
34]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        E.3  Receive IERP Packet

            extract(packet)
            switch(type)
            {
                case:  ROUTE_QUERY
                    if (dest (EXISTS IN) Intrazone_Routing_Table)
                    {
                        type = ROUTE_REPLY
                        reply_id = MY_REPLY_ID++
                        if(bad_link_source)
                            IERP_next = bad_link_source
                        else
                            IERP_next = source
                        load(packet)
                        send(packet,IERP_next)

                        type = QUERY_EXTENSION
                        IERP_next = dest
                        load(packet)
                        send(packet,IERP_next)
                    }
                    else
                        send(packet,BORDERCAST)
              break
              case:  QUERY_EXTENSION
                    type = ROUTE_ACCUMULATION
                    IERP_next=source
                    load(packet)
                    send(packet, IERP_next)
              break
              case:   ROUTE_REPLY
                    type = ROUTE_ACCUMULATION
                    IERP_next = dest
                    load(packet)
                    send(packet, IERP_next)
              break
              case:   ROUTE_ACCUMULATION
                if (bad_link_source)
                {
                    if(bad_link_source != source)
                        repair_src_ptr = get_index(route, bad_link_source)
                    else
                        repair_src_ptr = 0

                    bad_link    = {bad_link_source,dest}
                    path_repair = {bad_link_source,
                                   route(repair_src_ptr+1:|route|),
                                   dest}
                    replace_link(Interzone_Routing_Table,IERP,bad_link,
                                 path_repair)
                }

Haas, Pearlman                Expires December 1999                  [Page
35]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

                else
                {
                  if (IERP_next == source)
                    add(Interzone_Routing_Table, IERP, dest,
next_hops,metric)
                  if (IERP_next == dest)
                    add(Interzone_Routing_Table, IERP,
                        source, reverse(prev_hops),metric)
                }

                if (MY_ID == IERP_next)
                {
                  if (MY_ID == source)
                    IERP_next = dest
                  if (MY_ID == dest)
                    IERP_next = source

                  type = ROUTE_OPTIMIZATION
                  load (packet)
                  send (packet, IERP_next)
                }
              break

              case:   ROUTE_OPTIMIZATION
                if (MY_ID == source)

add(Interzone_Routing_Table,IERP,dest,route,NO_METRIC,ROF)
                if (MY_ID == dest)
                    add(Interzone_Routing_Table, IERP, source,
                        reverse(route), NO_METRIC, ROF)
              break
            }

Haas, Pearlman                Expires December 1999                  [Page
36]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

4.3  Bordercast Resolution Protocol (BRP)

   The BRP is a sublayer of the IERP that performs the operations of
   bordercasting, query control, route accumulation and routing zone
   labelling, which form the basis for the route discovery procedure.

   In this BRP implementation, bordercasting is implemented as a series
   of unicasted messages to the peripheral nodes.  The BRP is able to
   identify the peripheral nodes based on the information contained in
   the Intrazone Routing Table.  Rather than unicasting to the peripheral
   node directly through IP, the bordercasted packets are relayed to
   the peripheral nodes by the BRP layer.  IP is used only to send
   these messages one hop toward the peripheral nodes.  This allows the
   BRP to detect all ROUTE_QUERY packets that are received by that node.

   To efficiently terminate the query, the BRP needs to record
   sufficient information from each detected query.  The query's source
   and ID, which serve to uniquely identify a query, are added to the
   Detected Queries Table.  In addition, the IP address of the last
   node to bordercast the query is also recorded in the Detected
   Queries table.  Any threads of this query that are later received
   from a different bordercasting node are discarded.  Each query also
   contains a hop counter that is decremented at each node.  When the
   counter expires, the packet is discarded.

   IERP packets (excluding ROUTE_OPTIMIZATION packets) that are not
   terminated next undergo a  route accumulation procedure.  As
   described earlier, route accumulation is used to construct routes,
   by recording the IP addresses of a route's nodes in the IERP packet
   or local cache.  The Detected Queries Table, extended by two
   columns, serves as a convenient route accumulation cache.

   The node begins the route accumulation procedure by adding its IP
   address to the IERP route.  This is followed by the IP addresses of
   any cached nodes leading to the packet's destination (the "next
   hops").  This is sufficient processing for ROUTE_ACCUMULATION
   packets, where complete source routes are constructed.  On the other
   hand, ROUTE_QUERY, QUERY_EXTENSION and ROUTE_REPLY packets should carry
as
   little of the route as possible.  Therefore, if cache space is
   available, the route accumulation process records the IP addresses
   of the "previous hops" from the packet's source, and removes them
   from the IERP packet.

   The final role of the BRP is to contribute to the ROUTE_OPTIMIZATION
   process by indicating the mutual routing zone membership of the
   nodes in the source route.  This is done by appending a special
   flag field to the ROUTE_OPTIMIZATION packet.  The status of the
   k-th bit in the flag field indicates whether the k-th hop in the
   source route is a member of the node's routing zone.  This
   membership information is eventually processed at the source to
   determine the smallest set of routing zones that cover the route
   (and therefore the smallest set of nodes needed to specify this
   route through loose source routing).

Haas, Pearlman                Expires December 1999                  [Page
37]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    A.  Packet Format

        See IERP packet format in Section 4.2

    B.  Data Structures

        B.1  Intrazone Routing Table    (see IARP description)

        B.2  Interzone Routing Table    (see IERP description)

        B.3  Detected Queries Table

             +--------------------+--------+
             |  Query   |  Query  |  Prev  |
             |  Source  |   ID    |  IERP  |
             |----------+---------|--------|
             |          |         |        |
             |----------+---------|--------|
             |          |         |        |
             |----------+---------|--------|
             |          |         |        |
             +--------------------+--------+

        B.4  Detected Replies Table

             +--------------------+
             |  Reply   |  Reply  |
             |  Node    |   ID    |
             |----------+---------|
             |          |         |
             |----------+---------|
             |          |         |
             |----------+---------|
             |          |         |
             +--------------------+

    C.  Interfaces

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

Haas, Pearlman                Expires December 1999                  [Page
38]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    D.  State Machine

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

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

      D.1
            Event:   A ROUTE_QUERY packet is received from the IERP.

            Action:  If X is the query's source, then the identifying
querying
                     information is recorded in the Detected Queries Table.
                     X adds its IP address to the packet's route.  A copy of
the
                     packet is sent to the IERP layer of each peripheral
node,
                     by way of a BRP transmission to the next hop to that
                     peripheral node.

      D.2
            Event:   A ROUTE_QUERY packet is received from the IP.  The hop
                     counter has expired or the query was already
                     detected from another bordercasting node.

            Action:  The packet is discarded.

      D.3
            Event:   A ROUTE_QUERY packet is received from IP.  The hop
count
                     has not expired and the query has not been previously
                     detected (or was detected from the same bordercasting
node).
                     X is not the intended BRP recipient.

            Action:  Identifying query information is recorded in the
Detected
                     Queries Table.  The packet is then discarded.

      D.4
            Event:   A ROUTE_QUERY packet is received from the IP.  The hop
                     count has not expired and the query has not been
                     previously detected (or was previously detected
                     from the same bordercasting node).  X is the
                     intended BRP recipient, but is not the intended
                     IERP recipient and the query destination does
                     not lie within X's routing zone.

            Action:  The hop counter is decremented.  Identifying query
                     information is recorded in the Detected Queries Table
                     and accumulated route information is recorded
                     in the Interzone Routing Table.  The recorded route
                     information is removed from the packet and X adds
                     its IP address to the route.
                     The packet is then sent to the BRP of the next hop
                     to the intended IERP recipient.

Haas, Pearlman                Expires December 1999                  [Page
39]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

      D.5
            Event:   A ROUTE_QUERY packet is received from the IP.  The hop
                     count has not expired and the query has not been
                     previously detected (or was previously detected
                     from the same bordercasting node).  X is the
                     intended BRP recipient, and either X is the
                     intended IERP recipient, OR the query destination
                     lies in X's routing zone.

            Action:  The hop counter is decremented.  Identifying query
                     information is recorded in the Detected Queries Table
                     and accumulated route information is recorded in the
                     Detected Queries Table.  The recorded route information
                     is removed from the packet and X adds its IP address
                     to the route.
                     The packet is then delivered up to the IERP.

      D.6
            Event:   A QUERY_EXTENSION is received from the IERP.

            Action:  The packet is sent to the BRP layer of the
                     next hop to the specified IERP recipient
                     (in this case, the query destination).

      D.7
            Event:   A QUERY_EXTENSION is received from the IP.
                     X is not the intended BRP recipient.

            Action:  Identifying query information is recorded in the
                     Detected Queries Table and accumulated route
                     information is recorded in the Interzone Routing
                     Table.
                     The packet is then discarded.

      D.8
            Event:   A QUERY_EXTENSION packet is received from the IP.
                     X is the intended BRP recipient, but is not the
                     intended IERP recipient.

            Action:  Identifying query information is recorded in the
                     Detected Queries Table and accumulated route
                     information is recorded in the Interzone Routing
                     The recorded route information is removed from the
                     packet and X adds its IP address to the route.
                     The packet is then sent to the BRP of the next hop
                     to the intended IERP recipient.

Haas, Pearlman                Expires December 1999                  [Page
40]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

      D.9
            Event:   A QUERY_EXTENSION packet is received from the IP.
                     X is the intended BRP recipient and the intended
                     IERP recipient.

            Action:  Identifying query information is recorded in the
                     Detected Queries Table and accumulated route
                     information is recorded in the Interzone Routing
                     Table.  The recorded route information is removed
                     from the packet and X adds its IP address to the
                     route.  The packet is then delivered up to the IERP.

      D.10
            Event:   A ROUTE_REPLY packet is received from the IERP.

            Action:  The IP addresses of X and the previous hops back
                     to the query source (cached in the Detected Queries
                     Table) are added to the route.  The packet is sent
                     back to the IERP layer of the query source, by way
                     of a BRP layer transmission to the first hop back
                     to the query source.

      D.11
            Event:   A ROUTE_REPLY packet is received from the IP.
                     X is not the intended BRP recipient or the
                     ROUTE_REPLY was previously detected.

            Action:  The packet is discarded.

      D.12
            Event:   A ROUTE_REPLY packet is received from the IP.
                     X is the intended BRP recipient, but not the
                     intended IERP recipient.
                     The ROUTE_REPLY was not previously detected.

            Action:  Identifying query information is recorded in the
                     Detected Replies Table and accumulated route
                     information is recorded in the Interzone Routing
                     Table.  The IP addresses of X and the previous hops
                     back to the query source (previously recorded in the
                     Interzone Routing Table) are added to the route.
                     The packet is then sent to the BRP layer of the
                     previous hop back to the query source.

      D.13
            Event:   A ROUTE_REPLY packet is received from the IP.
                     X is the intended BRP recipient and the intended
                     IERP recipient.
                     The ROUTE_REPLY was not previously detected.

            Action:  Identifying query information is recorded in the
                     Detected Replies Table and accumulated route
                     information is recorded in the Interzone Routing
                     Table.  The recorded route information is removed
                     from the packet.  The packet is then delivered up
                     to the IERP.

Haas, Pearlman                Expires December 1999                  [Page
41]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

      D.14
          Event:   A ROUTE_ACCUMULATION packet is received from the IERP.

          Action:  The packet is sent to the IERP layer of the specified
                   IERP recipient by way of a BRP transmission to the next
                   hop toward the IERP recipient.

      D.15
          Event:   A ROUTE_ACCUMULATION packet is received from the IP.
                   X is not the intended BRP recipient.

          Action:  The packet is discarded.

      D.16
          Event:   A ROUTE_ACCUMULATION packet is received from the IP.
                   X is the intended BRP recipient, but not the intended
                   IERP recipient.

          Action:  The IP addresses of X and the next hops to the intended
                   IERP recipient (previously recorded in the Detected
                   Replies Table) are added to the route.
                   If this packet contains a route repair and the repair has
                   already been accumulated, then a copy of the packet is
                   delivered to the IERP.  The packet is then sent to the
BRP
                   layer of the next hop toward the IERP recipient.

      D.17
          Event:   A ROUTE_ACCUMULATION packet is received from the IP.
                   X is the intended BRP recipient and the intended
                   IERP recipient.

          Action:  The packet is delivered up to the IERP.

      D.18
          Event:   A ROUTE_OPTIMIZATION packet is received from the IERP.

          Action:  X indicates (in its ROF field) those route nodes that
                   belong to its routing zone.  The packet is then sent to
                   the IERP layer of the specified IERP recipient, by way
                   of a BRP transmission to the next hop toward the
                   IERP recipient.

      D.19
          Event:   A ROUTE_OPTIMIZATION packet is received from the IP.
                   X is not the intended BRP recipient.

          Action:  The packet is discarded.

Haas, Pearlman                Expires December 1999                  [Page
42]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

      D.20
          Event:   A ROUTE_OPTIMIZATION packet is received from the IP.
                   X is the intended BRP recipient, but not the intended
                   IERP recipient.

          Action:  X indicates (in its ROF field) those route nodes that
                   belong to its routing zone.
                   The packet is then sent to the IERP layer of the
                   specified next hop toward the IERP recipient.

      D.21
          Event:   A ROUTE_OPTIMIZATION packet is received from the IP.
                   X is the intended BRP recipient and the intended
                   IERP recipient.

          Action:  X indicates (in its ROF field) those route nodes that
                   belong to its routing zone.  The packet is then
                   delivered up to the IERP.

    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,
                            bad_link_source, dests, next_IERP, next_BRP,
                            prev_IERP, route, metric, ROF}

            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 December 1999                  [Page
43]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        E.1  Receive Packet from IERP

            extract(packet)

            switch(type)
            {
              case:  ROUTE_QUERY
                IERP_prev = MY_ID
                if ((bad_link_source == MY_ID (OR) source == MY_ID)
                {
                    if(source != MY_ID)
                    {
                        route = reverse(Interzone_Routing_Table(source))
                        route = {route, MY_ID}
                    }
                    else
                        route = NULL

                    current_hop_ptr = |route|

                    if(bad_link_source)
                        add(Detected_Queries,{bad_link_source,query_id,
                            IERP_prev})
                    else
                        add(Detected_Queries,{source,query_id,IERP_prev})
                }

                for (IERP_next = each host in Intrazone_Routing_Table)
                {
                    if (IERP_next is a peripheral node)
                    {
                      BRP_next=get_shortest_route(Intrazone_Routing_Table,
                                                  IERP_next)->next_hop
                      metric  =get_metric(Intrazone_Routing_Table,BRP_next)
                      load(packet)
                      send(packet,BRP_next)
                    }
                }
              break

              case:  QUERY_EXTENSION
                BRP_next=get_shortest_route(Intrazone_Routing_Table,
                                            IERP_next)->next_hop
                load(packet)
                send(packet,BRP_next)
              break

Haas, Pearlman                Expires December 1999                  [Page
44]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

              case:  ROUTE_REPLY
                prev_hops = route(1: current_hop_ptr-1)
                next_hops = route(current_hop_ptr+1 : |route|)
                if (prev_hops(1) == MY_ID)
                {
                    prev_hops=reverse(Interzone_Routing_Table[IERP_next])

                    if(prev_hops(1) == IERP_next (OR) prev_hops == NULL)
                    {
                        prev_hops = NULL
                        BRP_next = IERP_next
                    }
                    else
                        BRP_next = prev_hops(|prev_hops|)
                }
                else
                    BRP_next = prev_hops(|prev_hops|)

                if (!is_neighbor(Intrazone_Routing_Table, BRP_next))
                {
                    prev_hops={prev_hops,get_route(Intrazone_Routing_Table,
                                                   BRP_next)}
                    BRP_next = prev_hops(|prev_hops|)
                }

                metric  =get_metric(Intrazone_Routing_Table,BRP_next)
                current_hop_ptr = |prev_hops|+1
                route = {prev_hops, MY_ID, next_hops}
                load(packet)
                send(packet,BRP_next)
              break

              case:  ROUTE_ACCUMULATION
                if(IERP_next == source)
                {
                    BRP_next = route(|route|)
                    current_hop_ptr = |route|+1
                }
                if(IERP_next == dest)
                {
                    BRP_next = route(1)
                    current_hop_ptr = 0
                }
                load(packet)
                send(packet,BRP_next)
              break

Haas, Pearlman                Expires December 1999                  [Page
45]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

              case:  ROUTE_OPTIMIZATION
                ROF = NULL
                for (node = {source,route,dest})
                {
                    if ((EXISTS) Intrazone_Routing_Table[node])
                        ROF = {ROF,1}
                    else
                        ROF = {ROF,0}
                }
                if(IERP_next == dest)
                {
                    BRP_next = route(1)
                    current_hop_ptr = 0
                }
                if(IERP_next == source)
                {
                    BRP_next = route(|route|)
                    current_hop_ptr = |route|+1
                }
                load(packet)
                send(packet,BRP_next)
              break

        E.2  Receive Packet from IP

            extract(packet)

            switch(type)
            {
              case ROUTE_QUERY:
                if (TTL > 0 (AND)
                    (!EXISTS(Detected_Queries[source,query_id] (OR)
                     Detected_Queries[source,query_id]->from == IERP_prev))
                {
                    TTL--
                    hop_count++
                    prev_hops = route(1 : current_hop_ptr)
                    next_hops = route(current_hop_ptr+1 : |route|)

                    if(bad_link_source)
                    {

add(Detected_Queries,{bad_link_source,query_id,IERP_prev})
                      status =
add(Interzone_Routing_Table,BRP,bad_link_source,
                                   prev_hops,metric)
                    }
                    else
                    {
                      add(Detected_Queries,{source,query_id,IERP_prev})
                      status = add(Interzone_Routing_Table,BRP,source,
                                   prev_hops,metric)
                    }

Haas, Pearlman                Expires December 1999                  [Page
46]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

                    if (status == RECORDED_ROUTE)
                    {
                        prev_hops = NULL
                        metric = compress_metric(metric)
                    }
                    route = {prev_hops, MY_ID, next_hops}
                    current_hop_ptr = |prev_hops|+1

                    if(BRP_next == MY_ID)
                    {
                        if(IERP_next == MY_ID)
                        {
                          load(packet)
                          deliver(packet,IERP)
                        }
                        else
                        {
                            d = dests (BELONGING TO) Intrazone_Routing_Table
                            if(|d| > 0)
                            {
                                 load(packet)
                                 deliver(packet,IERP)
                            }

                            if((|d| == 0) (OR)
                               (|d| < |dests| (AND) flag(0) == ALL))
                            {
                              BRP_next=get_shortest_route(
                                                   Intrazone_Routing_Table,
                                                   IERP_next)->next_hop

                              metric = {metric,get_metric(
                                                   Intrazone_Routing_Table,
                                                   BRP_next)}
                              load(packet)
                              send(packet, BRP_next)
                            }
                        }
                    }
                    else
                        discard(packet)
                }
                else
                {
                    if(bad_link_source)

add(Detected_Queries,{bad_link_source,query_id,IERP_prev})
                    else
                      add(Detected_Queries,{source,query_id,IERP_prev})

                    discard(packet)
                }
              break

Haas, Pearlman                Expires December 1999                  [Page
47]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

              case QUERY_EXTENSION:
                if (!EXISTS(Detected_Replies[reply_node,reply_id])
                {
                    hop_count++
                    prev_hops = route(1: current_hop_ptr)
                    next_hops = route(current_hop_ptr+1 : |route|)

                    if(bad_link_source)
                    {

add(Detected_Queries,{bad_link_source,query_id,IERP_prev})
                      status =
add(Interzone_Routing_Table,BRP,bad_link_source,
                                   prev_hops,metric)
                    }
                    else
                    {
                      add(Detected_Queries,{source,query_id,IERP_prev})
                      status = add(Interzone_Routing_Table,BRP,source,
                                   prev_hops,metric)
                    }

                    if (status == RECORDED_ROUTE)
                    {
                        prev_hops = NULL
                        metric = compress_metric(metric)
                    }

                    route = {prev_hops, MY_ID, next_hops}
                    current_hop_ptr = |prev_hops|+1

                    if(BRP_next == MY_ID)
                    {
                        if(IERP_next == MY_ID)
                        {
                            load(packet)
                            deliver(packet,IERP)
                        }
                        else
                        {

BRP_next=get_shortest_route(Intrazone_Routing_Table,
                                                       IERP_next)->next_hop
                           metric =
{metric,get_metric(Intrazone_Routing_Table,
                                                       BRP_next)}
                           load(packet)
                           send(packet, BRP_next)
                        }
                    }
                    else
                        discard(packet)
                }
                else
                    discard(packet)
              break

Haas, Pearlman                Expires December 1999                  [Page
48]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

              case ROUTE_REPLY:
                if(MY_ID == BRP_next (AND)
                   !EXISTS(Detected_Queries[source,query_id]))
                {
                    prev_hops = route(1: current_hop_ptr-1)
                    next_hops = route(current_hop_ptr : |route|)
                    add(Detected_Replies, {reply_node,reply_id})
                    status=add(Interzone_Routing_Table,BRP,dest,
                               next_hops,metric)
                    if (status == RECORDED_ROUTE)
                    {
                        next_hops = NULL
                        metric = compress_metric(metric)
                    }

                    if (prev_hops(1) == MY_ID)
                    {
                       prev_hops=reverse(Interzone_Routing_Table[IERP_next])

                       if(prev_hops(|prev_hops|) == IERP_next (OR)
                          prev_hops higher layer
                     (IERP).

    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)
                       {
                           prev_hops = NULL
                           BRP_next = IERP_next
                       }
                       else
                           BRP_next = prev_hops(|prev_hops|)
                    }
                    else
                       BRP_next = prev_hops(|prev_hops|)

                    if (!is_neighbor(Intrazone_Routing_Table, BRP_next)) 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_hops={prev_hops,get_route(Intrazone_Routing_Table,
                                                       BRP_next)}
                        BRP_next
                prev_bcast = prev_hops(|prev_hops|)
                    }
                    if(MY_ID == IERP_next)
                    {
                        current_hop_ptr Detected_Messages[source,message_id
                                               ,BRP_cache_ID].prev_bcast;
                out_neighbors = 0
                        load(packet)
                        deliver(packet,IERP) Detected_Message
                             [source,message_id,BRP_cache_ID].out_neighbors;
             }
             else
             {
                        metric = {metric,get_metric(Intrazone_Routing_Table,
                                                    BRP_next)}
                        route
                prev_bcast = {prev_hops, MY_ID, next_hops}
                        current_hop_ptr MY_ID;
                out_neighbors = |prev_hops|+1
                        load(packet)
                        send(packet,BRP_next) Bordercast_Tree[MY_ID].downstream_neighbors;
             }
                }
                else
                    discard(packet)
              break

Haas, Pearlman                Expires December 1999                  [Page
49]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

              case ROUTE_ACCUMULATION:
                if(MY_ID == BRP_next)
                {
                    if(IERP_next == source)
                    {
                      prev_hops
             source     = route(1: current_hop_ptr-1)
                      next_hops MY_ID;
             message_id = route(current_hop_ptr : |route|) MY_BORDERCAST_ID++;
             load(packet);
		 send(packet,out_neighbors),IP);

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

             extract(packet);

             // Discard bordercast message if (prev_hops(1) == MY_ID)
                      {

prev_hops=reverse(Interzone_Routing_Table[IERP_next])

                        if(prev_hops(1) == IERP_next (OR) prev_hops == NULL)
                        {
                           prev_hops = NULL
                           BRP_next = IERP_next
                        }
                        else
                           BRP_next = prev_hops(|prev_hops|)
                      }
                      else
                        BRP_next = prev_hops(|prev_hops|)

                      if(MY_ID == bad_link_source)
                          flags(1) = 1
                    }

                    if(IERP_next == dest)
                    {
                      prev_hops = route(1: current_hop_ptr)
                      next_hops this node is not a member of
             // prev_bcast's bordercast tree
             discard = route(current_hop_ptr+1 : |route|) !Bordercast_Tree[prev_bcast].member;
             // If this node is the downstream peripheral node of
             // prev_bcast then terminate if (next_hops(|next_hops|) == MY_ID)
                      {
                        next_hops=Interzone_Routing_Table[IERP_next])

                        if(next_hops(|next_hops|) == IERP_next (OR)
                           next_hops == NULL)
                        {
                           next_hops = NULL
                           BRP_next = IERP_next
                        }
                        else
                           BRP_next = next_hops(1)
                      }
                      else
                        BRP_next = next_hops(1)
                    }

Haas, Pearlman                Expires December 1999                  [Page
50]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

                    if(MY_ID == IERP_next)
                    {
                        load(packet)
                        deliver(packet, IERP)
                    }
                    else 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))
             {
                        if(flags(1) == 1)
                 for((EACH) queried_node (BELONGING TO)
                                  Detected_Messages[source,message_id]
                                  .prev_bcast)
                 {
                            load(packet)
                            deliver(packet, IERP)
                        }
                        metric
                    a = {metric,get_metric(Intrazone_Routing_Table,
                                                    BRP_next)}
                        route MY_ID (BELONGS TO)
                        Bordercast_Tree[queried_node]
                                            .downstream_peripheral_nodes;
                    b = {prev_hops, MY_ID, next_hops}
                        current_hop_ptr is_interior_node(queried_node,MY_ID);
                    discard = |prev_hops|+1
                        load(packet)
                        send (packet,BRP_next)
                    } discard || (a || b);
                 }
                else
                    discard(packet)
              break

              case ROUTE_OPTIMIZATION:
                if(MY_ID == BRP_next)
                {
                    f
                 // Since this node is the downstream peripheral recipient,
                 // it will re-bordercast the message (if it isn't
                 // terminated)
                 prev_bcast = NULL
                    for (node MY_ID;
             }
             out_neighbors = {source,route,dest}) {};
             if(!discard)
             {
                 // Don't relay message to a given downstream neighbor if ((EXISTS) Intrazone_Routing_Table[node])
                        f = {f,1}
                      else
                        f = {f,0}
                    }

                    if (IERP_next == source)
                 // 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)
                 {
                      current_hop_ptr--
                      prev_hops = route(1: current_hop_ptr-1)
                      next_hops
                     drop_neighbor = route(current_hop_ptr+1 : |route|)
                      BRP_next = prev_hops(|prev_hops|)
                      ROF TRUE;
                     leaves = {f,ROF}
                    }
                    if (IERP_next == dest) Bordercast_Tree[prev_bcast,neighbor
                                           ].downstream_peripheral_nodes;
                     for((EACH) leaf_node (BELONGING TO) leaves)
                     {
                      current_hop_ptr++
                      prev_hops
                         failed_leaf = route(1: current_hop_ptr-1)
                      next_hops TRUE;
                         for((EACH) queried_node (BELONGING TO)
                                Detected_Messages[source,message_id]
                                                             .prev_bcast)
                         {
                            a = route(current_hop_ptr+1 : |route|)
                      BRP_next leaf_node (BELONGS TO)
                                Bordercast_Tree[queried_node]
                                            .downstream_peripheral_nodes;
                            b = next_hops(1)
                      ROF is_interior_node(queried_node,leaf_node);
                            failed_leaf = {ROF,f} failed_leaf || (a || b);
                         }

Haas, Pearlman                Expires December 1999                  [Page
51]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

                    if(MY_ID == IERP_next)
                    {
                        load(packet)
                        deliver(packet, IERP)
                         drop_neighbor = drop_neighbor && failed_leaf;
                     }
                    else
                    {
                      load(packet)
                      send (packet,BRP_next)
                     if(!drop_neighbor)
                         out_neighbors = {out_neighbors, neighbor};
                 }
             }
                else
                    discard(packet)
              break

Haas, Pearlman                Expires December 1999                  [Page
52]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

             // 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);

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 [4], [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 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 December 1999                  [Page
53]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   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 (ie. (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 hieararchical hierarchical routing
   protocols, such as the Zone-Based Hiearchical Hierarchical Link-State (ZHLS) [5], [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 [12] [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 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.

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 the related mobility management protocols, which determine
   complete node addresses based appear
              in IEEE JSAC issue on a node's location Ad-Hoc Networks, June, 1999.

   [5]   Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing
              in the network
hierarchy.

Haas, Pearlman                Expires December 1999                  [Page
54] 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              The Zone STANDARD,
              RFC 2178, July 1997.

   [7]   Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient
              Routing Protocol                June
1999

6.0 References

   [1] 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., "A "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.

7.0  Draft Updates

   - The sole function of the Bordercast Resolution Protocol for (BRP) is
     to perform application independent bordercasting (all excess
     routing protocol functionality has been moved up to the Reconfigurable
              Wireless Networks," ICUPC'97, San Diego, CA, Oct. 12,1997.

   [2]   Haas, Z.J. and Pearlman, M.R., "The Performance IERP).
     This means that the BRP can be used outside of Query
              Control Schemes 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 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]   Haas, Z.J. and Pearlman, M.R., "Determining
     query "broadcast()" with "bordercast()".
     In further support of application independent bordercasting, the Optimal
              Configuration for BRP
     can deliver messages up to the Zone Routing Protocol," higher layer application at every hop
     (as opposed to appear
              in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.

   [5]   Joa-Ng, M. and Lu, I.T., "A Peer-to-Peer Zone-based Two-Level
              Link State Routing only delivering for Mobile Ad-Hoc Networks," peripheral nodes).  This is
     important for applications that wish to appear
              in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.

   [6]   Johnson, D.B., 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 Maltz, D.A., "Dynamic Source Routing
              in Ad-Hoc Wireless Networks," in Mobile Computing,
              edited IERP now share a single routing table.
     IARP entries are indicated by T. Imielinski and H. Korth, chapter 5,
              pp. 153-181, Kluwer, 1996.

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

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

   [9]   Park, V.D., a special flag.

   - The IERP's optional Route Accumulation and Corson, M.S., "A Highly Adaptive Distributed
              Routing Algorithm 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 Mobile Wireless Networks,"
              IEEE INFOCOM'97, Kobe, Japan, 1997. "diversity injection" [10]  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.

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

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

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

Haas, Pearlman                Expires December 1999                  [Page
55]

INTERNET DRAFT has been added to the IERP.
     The Zone Routing Protocol                June
1999 diversity injection mechanism allows the global route discovery
     to extract more information about current network connectivity,
     without any additional traffic.

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 December 1999                  [Page
56]