INTERNET-DRAFT                            Zygmunt J. Haas, Cornell
University
                                         Marc R. Pearlman, Cornell
University
Expires in six months                                        August 1998 on December 1999                              June
1999

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

   To view the entire progress."

   The list of current Internet-Drafts, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast). 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.

   This version of the

   The ZRP internet draft describes framework is designed to provide a number balance between the
   contrasting proactive and reactive routing approaches.  To underscore
   this general philosophy, both the proactive and reactive components of
   features which
   this ZRP implementation have been added to expanded.  This draft provides
   specifications for both a (split-horizon) Distance Vector AND a Link
State
   version of the protocol. proactive IntrAzone Routing Protocol (IARP).  The distance-vector
   based IARP algorithm has been enchanced to prevent the 'counting
   to infinity problem'.  Route reactive
   IntErzone Routing Protocol (IERP) provides a route caching option.  When
   route caching is now supported by globally enabled, the IERP
   route discovery process.  By allowing discovered route acts as a reactive Distance
   Vector protocol, distributing routing information
   to be distributed in caches, among intermediate
nodes.
   On the other hand, when route accumulation caching is disabled, the routes are
accumulated
   in the IERP query/
   reply 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 avoided, thereby reducing targeted for either
   ANY destination or ALL destinations (depending on the amount nature of the
query).
   By aggregating route discovery traffic, and improving queries, the query response time.
   Two additional (optional) stages have also been added to amount of overhead traffic can be
greatly
   reduced.  In addition, the ZRP now supports QOS routing through the
   collection of various route
   discovery process, to support quality metrics (in both the acquisition proactive and optimization of
   source routes.
   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

   1.  Introduction

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

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

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

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

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

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

       4.2  Interzone Routing Protocol (IERP)  . . . . . . . . . . 14 24
            A.  Packet Format  . . . . . . . . . . . . . . . . . . 16 26
            B.  Data Structures  . . . . . . . . . . . . . . . . . . . . 18 31
            C.  Interfaces . . . . . . . . . . . . . . . . . . . . 19 31
            D.  State Machine  . . . . . . . . . . . . . . . . . . 19 32
            E.  Pseudocode Implementation  . . . . . . . . . . . . 22 33

       4.3  Bordercasting Resolution Protocol (BRP)  . . . . . . . 25 37
            A.  Packet Format  . . . . . . . . . . . . . . . . . . 26 38
            B.  Data Structures  . . . . . . . . . . . . . . . . . . . . 26 38
            C.  Interfaces . . . . . . . . . . . . . . . . . . . . 26 38
            D.  State Machine  . . . . . . . . . . . . . . . . . . 26 39
            E.  Pseudocode Implementations . . . . . . . . . . . . 31 43

Haas, Pearlman                Expires December 1999                 [Page
iii]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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

   6.  References  . . . . . . . . . . . . . . . . . . . . . . . . 38

1. Introduction

   One 55

Haas, Pearlman                Expires December 1999                  [Page
iv]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

Applicability Statement

A.  Networking Context

    The hybrid Zone Routing Protocol (ZRP) can adapt to a wide variety of the major challenges in designing a
    network scenarios by adjusting the range of the nodes' proactively
    maintained routing protocol zones.  Large routing zones are preferred when demand
    for routes is high and/or the
   ad hoc networks stems from network consists of many slowly moving
    nodes.  In the fact that, on one hand, to determine
   a packet route, extreme case of a node needs to known at least network with fixed topology, the reachability
   information to its neighbors. 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 an ad hoc
   network, situations where route demand
is
    low and/or the network topology can change quite often.  Furthermore,
   as the consists of a small number of network nodes can be large, that move
fast
    relative to one another.  In the potential number "worst case", a routing zone radius of
   destinations
one
    hop is also large, requiring large best, and frequent exchange of
   data (e.g., routes, routes updates, or routing tables) among the
   network nodes. Thus, ZRP defaults to a tradtional reactive flooding
    protocol.

    When the amount of update traffic can be quite high.
   This ZRP is in contradiction with the fact that all updates in properly configured for a
   wirelessly interconnected ad hoc particular network travel over the air and,
   thus, are costly in resources.

   In general, the existing routing protocols scenario,
it
    can be classified either perform at least as proactive or well as reactive. Proactive protocols attempt to
   continuously evaluate the routes within (and often better than) its purely
proactive
    and reactive constituent protocols.  In situations where the network, so that when
   a packet needs to be forwarded, network
    behavior varies across different regions, the route is already known and ZRP performance can be immediately used.  The family
fine
    tuned by individual adjustment of Distance-Vector protocols is an
   example each node's routing zone.

    The global reactive component of a proactive scheme.  Reactive protocols, on the other
   hand, invoke a route determination procedure on demand only. Thus,
   when a route is needed, some sort of global search procedure is
   employed. The family of classical flooding algorithms belong ZRP uses the unicast/multicast
based
    "bordercast" mechanism to propagate route queries throughout the
network,
    rather than neighbor-broadcast based flooding found in tradtional
reactive group. Some examples of reactive (also called on-demand)
   ad hoc network routing protocols are [Johnson], [AODV], [TORA]
   (see also [Park]).

   The advantage of
    protocols.  Consequently, the proactive schemes is that, once a route is
   needed, there is little delay until ZRP provides the route most benefit in networks
    where reliable neighbor broadcasting is determined. either inefficient or
all-together
    impossible.  In
   reactive protocols, because route information may not be available
   at particular, the time a datagram ZRP is received, well suited for multi-channel,
multi-
    technology routing fabrics and networks operating under high load.

B.  Protocol Characteristics and Mechanisms

   * Does the delay to determine a route protocol provide support for unidirectional links? (if so,
     how?)
        Yes.  The ZRP provides "local" support for unidirectional links.
        A unidirectional link can be quite significant. Furthermore, used as long as the global flood-search
   procedure 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 reactive protocols requires significant control
   traffic.  Because protocol require using some form of this long delay and excessive control traffic,
   pure source routing? (if
   so, how?)

        No.  The ZRP's global reactive routing protocols route discovery mechanism 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 either source routing or distributed distance vector based
        route accumulation.

Haas, Pearlman                Expires December 1999                   [Page
v]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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

        Yes.  The ZRP proactively maintains local routing information current. Since nodes in an ad hoc networks move
   quite fast, and as
        (routing zones) based on periodic exchanges of neighbor
        discovery messages.

   * Does the changes may be more frequent than protocol require the route
   requests, most use of this routing information is never even used! This
   results in a further waste 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 wireless network capacity. What protocol provide support for routing through a multi-
   technology routing fabric? (if so, how?)

        Yes.  It is
   needed assumed that each node's network interface is
        assigned a protocol that, on one hand, initiates unique IP address.

   * Does the route-
   determination procedure on-demand, but at limited search cost. The protocol described in this draft, termed 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 "Zone Routing Protocol
   (ZRP)"   ([Haas-1], [Haas-2]), neighbor discovery/maintenance process.

        By default, it is an example of assumed that a such host's association with a hybrid
   proactive/reactive scheme.

   The ZRP, on one hand, limits router
        is not permanent.  As a result, the scope of ZRP exchanges routing
information
        for individual hosts in the proactive procedure
   only to same manner as routing information for
        routers.

        In cases where a router is permanently associated with a network
        (subnetwork), the node's local neighborhood. On ZRP supports the other hand, exchange of network (subnetwork)
        prefixes in place of all aggregated host IP addresses.

   * Does the search
   throughout protocol support the network, although global in nature, IP addressing architecture? (if so,
   how?)

        Yes.  Each node is done by
   efficiently querying selected nodes assumed to have a unique IP address (or
        set of unique IP addresses in the network, as opposed to
   querying case of multiple interfaces).
        The ZRP references all the network nodes.

   A related issue is that nodes/interfaces by their IP address.

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

Haas, Pearlman                Expires December 1999                  [Page
vi]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   * Does the protocol to be efficient, 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 network topology
   should protocol have only dependence on a local effect. In other words, creation of central entity? (if so,
   how?)

        No.  The ZRP is a new
   link at one end of fully distributed protocol.

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

        Yes.  The ZRP's GLOBAL route discovery mechanism is an important local event but, most
   probably, not reactive.
        A route query is initiated, on demand, when a significant piece of node requires routing
        information at that is not immediately available in its routing table.

        The route query propagates through the other end network, using a ZRP-specific
        packet delivery service called "bordercasting".  Bordercasting
        leverages knowledge of
   the network. Proactive protocols tend local network topology to distribute such topological
   changes widely in direct route
        queries away from the network, incurring large costs. source, thereby reducing redundancy.

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

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

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

        Yes.  Loop-freedom in the cost of topological updates.

2. Overview of reactive route discovery process
        is ensured by labeling each route query and route reply
        with the Zone Routing Protocol

2.1 The Notion IP address of its originating node AND a Routing Zone and unique
        sequence number.  Nodes that relay the Intrazone Routing Protocol
    (IARP)

   A route queries
        /route replies 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 Link State routing
        protocols.  The scope of these proactive route updates is defined for each node X, and includes the nodes
   whose minimum distance in *hops* from X is at most some predefined
   number, which is referred limited
        to as the Zone Radius. An  example extent of a node's routing zone (for node A) of radius 2 zone.
        The ZRP's Link State proactive protocol is shown below.

          +-----------------------------------------+
          |                       +---+             |
          |            +---+   ---| F |-------|     |
   +---+  |  +---+   --| C |--/   +---+     +---+   |
   | G |-----| D |--/  +---+                | E |   |  Zone of node A
   +---+  |  +---+       |        +---+     +---+   | inherently loop-free.
        The Distance Vector protocol may form temporary loops prior to
        converging.  However, convergence occurs quickly due to the limited
        radius of radius=2
          |            +---+   ---| B |-------|     |
          |            | A |--/   +---+             |
          |            +---+                        |
          +-----------------------------------------+

   Note that in this example nodes B through E are within the routing
   zone zones

Haas, Pearlman                Expires December 1999                 [Page
vii]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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

        No.

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

        No.  It is outside A's routing zone. Also note assumed that E can
   be reached security issues are adequately addressed
        by two paths from A, one with length 2 hops and one with
   length 3 hope. Since the minimum underlying protocols (IPsec, for example)

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

        Yes.  It is less or equal than 2, E assumed that each node's network interface is within
   A's routing zone.

   Peripheral nodes are nodes whose minimum distance to
        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 node major challenges in
   question is equal exactly to designing a routing protocol for the zone radius. Thus, in
   ad hoc networks stems from 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 fact that, on one hand, to deliver determine
   a packet to its peripheral nodes.
   This service, which we refer to as bordercasting, allows for more
   efficient network-wide searching than simple neighbor broadcasting.
   Bordercasting could be implemented either through route, a series of IP
   unicasts or an IP multicast (Distance Vector Multicast Routing
   Protocol [RFC-1075])) node needs to known at least the peripheral nodes.  (In cases where
   multicasting is supported, the multicasting approach is preferred reachability
   information to reduce its neighbors.  On the amount of traffic over other hand, in an ad hoc
   network, the air.)  However, network topology can change quite often.  Furthermore,
   as will be
   explained later, efficient ZRP operation requires that these unicast
   or multicast services be provided by the ZRP, with IP providing best-
   effort delivery to the specified ZRP next hops.

   The ZRP supports number of network nodes can be large, the proactive maintenance potential number of
   destinations is also large, requiring large and frequent exchange of
   data (e.g., routes, routes updates, or routing zones
   through its proactive Intrazone Routing Protocol (IARP).  Through tables) among the IARP, each node learns
   network nodes. Thus, the identity amount of and update traffic can be quite high.
   This is in contradiction with the (minimal)
   distance to fact that all updates in a
   wirelessly interconnected ad hoc network travel over the nodes air and,
   thus, are costly in its resources.

   In general, the existing routing zone.  The IARP may protocols can be
   derived from a wide range of proactive protocols, such classified either
   as
   Distance Vector (e.g., [Murthy], [DSDV]) proactive or Shortest Path First
   (e.g., OSPF [RFC-2178]).  Whatever as reactive. Proactive protocols attempt to
   continuously evaluate the choice of IARP is, routes within the base
   protocol network, so that when
   a packet needs to be modified to ensure that forwarded, the scope route is already known and can
   be immediately used.  The family of this
   operation Distance-Vector protocols is restricted to the radius an
   example of a node's routing zone.

   Because each node needs to proactively acquire route information
   only for the nodes within its zone, proactive scheme.  Reactive protocols, on the total amount of IARP traffic
   does not depend 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 size
   reactive group. Some examples of reactive (also called on-demand)
   ad hoc network routing protocols are Dynamic Source Routing (DSR)[6],
   Ad-hoc On demand Distance Vector Routing (AODV) [11] and the network, which may be quite large

2.2 The Interzone
   Temporally Ordered Routing Protocol (IERP)

   While Algorithm (TORA) [9].

   The advantage of the IARP maintains routes within proactive schemes is that, once a zone, route is
   needed, there is little delay until the IERP* route is
   responsible for finding routes between nodes located determined. In
   reactive protocols, because route information may not be available
   at distances
   larger than the zone radius.  The IERP time a datagram is distinguished from standard received, the delay to determine a route
   can be quite significant. Furthermore, the global flood-search query/response  protocols by exploiting
   procedure  of the reactive protocols requires significant control
   traffic.  Because of this long delay and excessive control traffic,
   pure reactive routing zone
   topology.  A node is able protocols may not be applicable to respond positively to any queries real-time
   communication.  However, pure proactive schemes are likewise not
   appropriate 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 ad hoc networking environment, as they
   continuously use a large portion of the query, through network capacity to keep the
   routing zone-based bordercast delivery
   mechanism.

2.2.1  Routing Zone Based Route Discovery
   The IERP operates information current. Since nodes in an ad hoc networks move
   quite fast, and as follows:  The source node first checks whether the destination is within its routing zone. (Again, changes may be more frequent than the route
   requests, most of this routing information is possible
   as every node knows the content never even used! This
   results in a further waste of its zone). If so, the path to the
   destination wireless network capacity. What is known and no further route discovery processing
   needed is
   required. If, a protocol that, on the other one hand, initiates the destination is not within the
   source's routing zone, the source bordercasts a route query to all of
   its peripheral nodes. Now, route-
   determination procedure on-demand, but at limited search cost. The
   protocol described in turn, all the peripheral nodes execute
   the same algorithm: check whether this draft, termed the destination "Zone Routing Protocol
   (ZRP)"   ([1], [2]), is within their
   zone. If so, an example of a route reply is sent back to such a hybrid
   proactive/reactive scheme.

   The ZRP, on one hand, limits the source indicating scope of the
   route proactive procedure
   only to the destination. If not, node's local neighborhood. On the peripheral node forwards other hand, the
   query to its peripheral nodes, which, search
   throughout the network, although global in nature, is done by
   efficiently querying selected nodes in turn, executes the same
   procedure. An example 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 this Route Discovery procedure 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
   demonstrated an important local event but, most
   probably, not a significant piece of information at the other end of
   the network. Proactive protocols tend to distribute such topological
   changes widely in the figure 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 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 some predefined
   number, which is referred to as the Zone Radius. An  example of a
   routing zone (for node A) of radius 2 is shown below.

	                      +---+

          +-----------------------------------------+
          |                       +---+             |
          |            +---+   ---| F |-------|     |
	     +---+---|
   +---+  |  +---+   --| C |----+---+-----+---+ |--/   +---+     +---+   | D
   | G |-----| D |--/  +---+                | E |----| H |
	     +---+   |      +---+-----+---+  Zone of node A
   +---+
	             +---+----| B |  |  +---+       | A |    +---+-----+---+        +---+     +---+   | G |    | I |
	                                +---+    +---+  of radius=2
          |            +---+
		               +---+   ---| B |-------|     | J
          |            | C |----+---+----+---+    +---+ A |--/   +---+             | K |----| L
          |            +---+    +---+

   The node A has a datagram to send to node L. Assume a uniform                        |
          +-----------------------------------------+

   Note that in this example nodes B through E are within the routing
   zone radius 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 L the minimum is not in less or equal than 2, E is within
   A's routing zone
   (which includes B,C,D,E,F,G), A bordercasts a routing query to its
   peripheral nodes: D,F,E, and G. Each one of these peripheral zone.

   Peripheral nodes
   check whether L exists are nodes whose minimum distance to the node in their routing zones. Since L
   question is not found equal exactly to the zone radius. Thus, in any routing zones of these nodes, the above
   figure, nodes bordercast D, F, and E are A's peripheral nodes.

   An important consequence of the request routing zone construction is the
   ability of a node to their deliver a packet to its peripheral nodes. In particular, G bordercasts to K,
   This service, which
   realizes that L we refer to as 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]) to the peripheral nodes.  (In cases where
   multicasting is in its routing zone and returns supported, the requested
   route (L-K-G-A) multicasting approach is preferred
   to reduce the query  source, namely A.

   * Some functions amount of traffic over the IERP, including bordercasting, route
     accumulation, and query control (see later), are performed air.)  However, as will be
   explained later, efficient ZRP operation requires that these unicast
   or multicast services be provided by a
     special component of the IERP called ZRP, with IP providing best-
   effort delivery to the Bordercast Resolution specified ZRP next hops.

   The ZRP supports the proactive maintenance of routing zones
   through its proactive Intrazone Routing Protocol (BRP).  Sections 3.0 and 4.0 describe, in detail, (IARP).  Through
   the
     relationship between IARP, each node learns the BRP identity of and the IERP proper.

2.2.2 Route Accumulation Procedure

   The query propagation mechanism allows a route query (minimal)
   distance to indirectly
   reach the desired destination (through some node Y, which discovers all the destination nodes in its routing zone.)   To complete the route
   discovery process, Y needs to send zone.  The IARP may be
   derived from a reply back to the query's
   source, S, providing S with wide range of proactive protocols, such as
   Distance Vector (e.g., [8], [10]) or Shortest Path First
   (e.g., OSPF [7]).  Whatever the desired route.  To perform choice of IARP is, the route
   reply, sufficient information base
   protocol needs to be accumulated during the
   query phase so modified to ensure that Y the scope of this
   operation is provided with a route back to S.  Providing
   routes from discovering node Y restricted to query source S, and from the query
   source S back radius of a node's 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 query destination D (through Y), is nodes within its zone, the role total amount of IARP traffic
   does not depend on the Route Accumulation procedure.

   In size of the basic Route Accumulation, a node appends its IP address to a
   received query packet. network, which may be quite large

2.2 The sequence of IP addresses specifies Interzone Routing Protocol (IERP)

   While the IARP maintains routes within a
   route 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 query's source routing zone
   topology.  A node is able to the current node.  By reversing this
   sequence, a route may also be obtained back respond positively to the source. any queries for
   its routing zone nodes.  For large networks, relatively few
   destinations lie within any particular node's routing zone.  In this
   way, Y may send a reply back to S,
   more likely case, the node can efficiently continue the propagation
   of the query, through strict the routing zone-based bordercast delivery
   mechanism.

2.2.1  Routing Zone Based Route Discovery

   The IERP operates as follows:  The source routing.

   Given sufficient storage space, a queried node may cache first checks whether
   the destination is within its routing
   information accumulated in zone. (Again, this is possible
   as every node knows the query packet, allowing content of its zone). If so, the information path to be remove from the packet.  This has
   destination is known and no further route discovery processing is
   required. If, on the benefit of reducing other hand, the
   length of destination is not within the query packet, thereby decreasing
   source's routing zone, the source bordercasts a route query traffic and
   query response time.  The IP addresses that remain in the packet can
   be used to form a loose source route back to the query's source (If
   ALL nodes have cached all of
   its peripheral nodes. Now, in turn, all the accumulated route information, then this
   effectively becomes next hop routing.  If no peripheral nodes have cached
   accumulated route information, then this defaults to execute
   the basic case
   previously discussed).  The same caching strategy can be applied to algorithm: check whether the destination is within their
   zone. If so, a route reply packet on its way is sent back to the source.  In this case, a
   loose source indicating the
   route to the destination is formed.

2.2.3 Query Control Mechanisms

   Bordercasting has destination. If not, the potential to support global querying schemes
   that are more efficient than flooding.  To achieve this efficiency, peripheral node forwards the protocol should be able to detect and terminate a
   query thread
   when it appears in a previously queried region of the network (i.e.
   arrives at a node belonging to its peripheral nodes, which, in turn, executes the routing zone same
   procedure.  An example of a previously
   queried node).  This detection / termination capability is
   significantly limited when bordercasting this Route Discovery procedure is implemented directly
   through IP unicast or IP multicast.

   By implementing bordercasting within the ZRP,
   demonstrated in the nodes that relay figure below.

   * Some functions of the IERP, including bordercasting, route
     accumulation, and query to the peripheral node control (see later), are able to detect the passing
   query.  If the underlying IP delivery is (neighbor) broadcast or
   if IP is operating in promiscuous mode, then nodes that overhear performed by a query transmission are also able to detect
     special component of the query, further
   strengthening IERP called the Query Detection (QD) mechanism.  Upon detecting
   a query, the identifying query parameters (i.e. query source,
   query ID)  are recorded Bordercast Resolution
     Protocol (BRP).  Sections 3.0 and 4.0 describe, in a Detected Queries Table, to provide a
   basis for termination of future threads of that query. detail, the
     relationship between the BRP and the IERP proper.

Haas, Pearlman                Expires December 1999                   [Page
4]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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

   The node can consider A has a query datagram to be redundant if it has already
   detected that query, bordercasted by send to node L. Assume a different node.  If
   bordercasting uniform
   routing zone radius of 2 hops.  Since L is implemented directly through IP unicast/ multicast,
   then not in A's routing zone
   (which includes B,C,D,E,F,G), A bordercasts a routing query thread could only be terminated after being received by
   the to its
   peripheral node (bordercast destination).  This could result nodes: D,F,E, and G. Each one of these peripheral nodes
   check whether L exists in
   wasted transmissions as a query penetrates into a previously queried
   region.  Implementing bordercasting their routing zones. Since L is not found
   in any routing zones of these nodes, the ZRP allows nodes bordercast the protocol request
   to
   provide an Early Termination (ET), as the redundant query enters the
   previously queried region.

2.2.4 Route Maintenance their peripheral nodes. In addition particular, G bordercasts 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 K, which
   realizes that L is triggered by the IARP, in
   response to a node leaving the its 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 zone and returns the next
   hop in a datagram's source requested
   route is determined (L-K-G-A) to be unreachable
   (i.e. does not appear in the (Intrazone) Routing Table).

   Upon detection of query source, namely A.

2.2.2 Route Accumulation Procedure

   The query propagation mechanism allows a route failure, a node may choose query to notify indirectly
   reach the route's source of desired destination (through some node Y, which discovers
   the failure and / or attempt to repair destination in its routing zone.)   To complete the
   route.  A route failure notification consists of
   discovery process, Y needs to send a transmission reply back to the query query's
   source, indicating that S, providing S with the desired route.  To perform the source route has
   failed, and possibly
   reply, sufficient information needs to be accumulated during the hop at which it failed.  This type of
   service
   query phase so that Y is provided by protocols like ICMP.  The node that detects
   the with a route failure may also try back to repair the failed connection by S.  Providing
   routes from discovering a route node Y to bypass query source S, and from the failed connection.  The repair
   discovery process is nearly identical query
   source S back to an initial route discovery.
   Route repairs should not be substantially longer than the original
   failed connection.  Thus, query destination D (through Y), is the depth role of
   the Route Accumulation procedure.

   In the basic Route Accumulation, a repair node appends its IP address to a
   received query can 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 limited, obtained back to the source.  In this
   way, Y may send a reply back to S, through 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 use of hop counter. query packet, allowing the information
   to be remove from the packet.  This has the advantage benefit of producing
   much less reducing the
   length of the query packet, thereby decreasing the query traffic than an unrestricted initial route query.
   After and
   query response time.  The IP addresses that remain in the packet can
   be used to form a successful repair, loose source route back to the route's query's source MAY (If
   ALL nodes have cached the accumulated route information, then this
   effectively becomes next hop routing.  If no nodes have cached
   accumulated route information, then this defaults to the basic case
   previously discussed).  The same caching strategy can be notified so that
   routes are properly selected for use.  Alternatively, applied to
   the repair
   could go unreported without compromising reply packet on its way back to the connectivity between source.  In this case, a
   loose source and destination.

3.0 The ZRP Architecture

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

Legend:

	A <---> B      exchange of packets between protocols A & B
	A  ===> B      information passed from protocol A route 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 the destination is
   implemented by formed.

2.2.3 Query Control Mechanisms

   Bordercasting has the MAC/link-layer protocols. Thus potential to support global querying schemes
   that are more efficient than flooding.  To achieve this efficiency,
   the NDM protocol
   remains unspecified here.

4. Implementation Details

4.1 The IntrAzone Routing Protocol (IARP)

   The IARP can should be implemented through various proactive protocols. We
   present here an implementation based on able to detect and terminate a modified version query thread
   when it appears in a previously queried region of the
   Distance Vector algorithm.  Routing information to network (i.e.
   arrives at a node is limited belonging to the the routing zone of a previously
   queried node).  This detection / termination capability is
   significantly limited when bordercasting is implemented directly
   through IP unicast or IP multicast.

   By implementing bordercasting within the ZRP, the nodes that node.  In this version, routing
   information consists of relay
   the route cost and query to the IP addresses of the
   route destination and next two hops peripheral node are able to detect the destination. The second hop passing
   query.  If the underlying IP delivery is included to identify routes where a node (neighbor) broadcast or
   if IP is it's own second hop.
   This particular looping condition can result operating in the "counting promiscuous mode, then nodes that overhear
   a query transmission are also able to
   infinity" problem.  By deleting these routes, this problem can be
   avoided, allowing detect the IARP query, further
   strengthening the Query Detection (QD) mechanism.  Upon detecting
   a query, the identifying query parameters (i.e. query source,
   query ID)  are recorded in a Detected Queries Table, to converge faster. provide a
   basis for termination of future threads of that query.

   A node may receive new route information either from can consider a query to be redundant if it has already
   detected that query, bordercasted by a different node.  If
   bordercasting is implemented directly through IP unicast/ multicast,
   then a query thread could only be terminated after being received IARP
   packet or from an interrupt generated by its Neighbor Discovery /
   Maintenance (NDM) proces*. In
   the special case when peripheral node (bordercast destination).  This could result in
   wasted transmissions as a host has
   discovered query penetrates into a neighor, previously queried
   region.  Implementing bordercasting in the IARP is responsible for sending ZRP allows the protocol to
   provide an Early Termination (ET), as the new
   neighbor redundant query enters the shortest route to each host which is common to both of
   their routing zones (i.e. each host with a hop count less than it's
   routing zone radius).
   previously queried region.

Haas, Pearlman                Expires December 1999                   [Page
6]

INTERNET DRAFT              The node then records Zone Routing Protocol                June
1999

2.2.4 Route Maintenance

   In addition to initially discovering routes, the new 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 information
   in its Intrazone Routing Table.  If failure detection is triggered by the shortest path IARP, in
   response to a node leaving the host has
   changed, routing zone.  Any IERP routes
   containing this node as the terminal broadcasts an IARP packet reflecting first hop can be considered invalid.
   Route failures may also be detected reactively, by IP, when the
   change.

   * IARP relies on next
   hop in a datagram's source route is determined to be unreachable
   (i.e. does not appear in the services (Intrazone) Routing Table).

   Upon detection of a separate protocol (referred route failure, a node may choose to
     here as notify
   the Neighbor Discovery/Maintenance Protocol) route's source of the failure and / or attempt to provide
     current information about repair the
   route.  A route failure notification consists of a host's neighbors.  At transmission
   back to the least, this
     information must include query source, indicating that the IP addresses source route has
   failed, and possibly the hop at which it failed.  This type of all
   service is provided by protocols like ICMP.  The node that detects
   the neighbors. route failure may also try to repair the failed connection by
   discovering a route to bypass the failed connection.  The IARP can be readily configured repair
   discovery process is nearly identical to support supplemental
     neighbor information, such as link cost.

   A.  Packet Format
                    1	                2	            3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Destination Address                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Next Hop #1 Address			|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Next Hop #2 Address			|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Hop Cnt|
+-+-+-+-+
	Field Description:

	* Destination Address   (32 bits)
	    IP address of the destination host
	* Next Hop # 1 Address	(32 bits)
	    IP address of an initial route discovery.
   Route repairs should not be substantially longer than the "next hop" host to original
   failed connection.  Thus, the destination host
	* Next Hop # 2 Address	(32 bits)
	    IP address depth of a repair query can be limited,
   through the Next Hop #1 's "next hop" host to
            the destination host
	* Hop Count		(4 bits)
	    Length use of hop counter.  This has the advantage of producing
   much less query traffic than an unrestricted initial route to query.
   After a successful repair, the destination host, measured
            in hops

   B.  Structures

       B.1  Intrazone 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 Table

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           |                     Routes                          |
|           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Host Protocol                June
1999

3.0 The ZRP Architecture

             .........................................
             :                  ZRP                  :
             :                                       :
+---------+  :      +---------+         +---------+  :      +---------+
|       0   NDM   |========>|  IARP   |========>|  IERP   |<========|  ICMP   |       1
+---------+  :      +---------+         |.........|  :      +---------+
    /|\      :          /|\             | ==>   BRP   |      M-1  :          /|\
     |       :           |           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+              +---------+  :           |
     |  Next       :  Hop           |  Next                  /|\      :  Hop           | ==>
     | Next  :  Hop       :...........|...................|.......:           |
     |                   |  Hop  : Count                   |  Hop  : Count                   |
    \|/                 \|/                 \|/                 \|/
+---------+---------+---------+---------+---------+---------+---------+
| Hop   : Count |
+-+-+-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-+-+-+-:-+-+-+-+
|           |       :       |       :       |     |       :       |
|-----------|-------:-------|-------:-------|-----|-------:-------|
|           |       :       |       :       |     |       :       |
|-----------|-------:-------|-------:-------|-----|-------:-------|
|           |       :       |       :       |     |       :       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   C.  Interfaces

	C.1  Higher Layer (N/A)
	C.2  Lower Layer (IP)
	    C.1.1  Send()	(specified in                                 IP standard)
	    C.1.2  Deliver()	(specified in                                  |
+---------+---------+---------+---------+---------+---------+---------+

Legend:

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

        Existing Protocols
        ------------------
                IP standard)
	C.3              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
	    C.3.1  Neighbor_Lost(host)
		Used             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)

   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
   traditional proactive protocols can be modified to notify the serve as an IARP that direct contact
                has been lost with "host".
	    C.3.2  Neighbor_Found(host)
		Used by
   limiting the NDM range of route updates to notify the IARP that direct contact
                has been confirmed boundary of routing zones.

   In this draft, we detail implementations for both a Distance-Vector
   and a Link-State IARP.  The convergence problems typically associated
with "host".
	C.4  IERP
            C.4.1  Zone_Node_Lost(host)
                Used by IARP to notify
   the IERP that Distance-Vector approach are less of a node no longer
                exists within liability in the routing zone.

   D.  State Machine

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

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

	D.1
	    Event:   An IARP packet is received containing route
                     information to a destination D. The finite hop count
                     associated with the received route is LESS THAN
                     OR EQUAL TO imposed by the routing
zone
   radius.  The
		     second next-hop is EQUAL  Additionally, techniques such as "hold-downs", "split horizons"
   and "poison reverse" can be used to X.

	    Action:  NONE

	D.2
	    Event:   An prevent instabilities.  A stable
   Distance Vector IARP packet is received containing route
                     information to implementation converges a destination D. The hop count
                     associated rate comparable to
   Link-State IARP, and generally with less control traffic and reduced
   computational overhead.  However, the received route is LESS THAN Link-State IARP provides a complete
   view of the routing zone radius. topology, making it a favorable option for some
   applications (including "on-line" 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 next-hop hop
   is NOT EQUAL included to X.

	    Action:  The received route identify routes where a node is recorded it's own second hop.
   This particular looping condition result in the  Intrazone
                     Routing Table. If the received route is shorter
                     than "counting to
   infinity" problem.  By deleting these routes, this problem can be
   avoided, allowing the previous shortest route IARP to D, then a converge faster.

   A node may receive new
                     IARP packet containing route information to D
                     through X is broadcasted.

	D.3
	    Event:   An either from a received IARP
   packet is received containing route
                     information to or from an interrupt generated by its Neighbor Discovery /
   Maintenance (NDM) process*. In the special case when a destination D. The hop count is
                     EQUAL TO host has
   discovered a neighbor, the routing zone radius.  The second
		     next-hop IARP is NOT EQUAL responsible for sending to X.

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

	D.4
	    Event:   An IARP packet is received containing new
   neighbor the shortest route
                     information to each host which is common to both of
   their routing zones (i.e. each host with a destination D. The hop count is
                     equal to INF.

	    Action: less than it's
   routing zone radius). The route to D is removed from node then records the new route information
   in its Intrazone Routing Table.
		        1)  If the Intrazone Routing Table still
                        contains a route to D and the length of the shortest route has increased due path to the route
                        removal, then host has
   changed, the terminal broadcasts an IARP packet containing the
                        shortest route to D through X is broadcasted.
		        2) If reflecting the Intrazone Routing Table contains no
                        more routes to D, then an
   change.

   * IARP packet containing
                        a route to D through X with hop count relies on the services of INF is
                        broadcast.  A "Host Lost" interrupt is
                        generated a separate protocol (referred to alert
     here as the IERP that D has moved
                        beyond Neighbor Discovery/Maintenance Protocol) to provide
     current information about a host's neighbors.  At the routing zone.

	D.5
	    Event:   A "Neighbor Found" interrupt is received,
                     indicating least, this
     information must include the discovery IP addresses of a neighbor host N.

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

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

	    Action: support supplemental
     link quality metrics.

Haas, Pearlman                Expires December 1999                   [Page
9]

INTERNET DRAFT              The one hop route to N is removed from the
                     Intrazone Zone Routing Table.
		        1) If 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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                       Destination Address                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                Destination Subnet Mask (Optional)             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                       Next Hop #1 Address                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                       Next Hop #2 Address                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |   RESERVED    |  Metric Type  |          Metric Value         |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                   | |                                Route
                                  \| |/                              Metrics
                                   \ /
(optional)
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |   RESERVED    |  Metric Type  |          Metric Value         |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |   Hop Count   |
    +-+-+-+-+-+-+-+-+

        Field Description:

        * Destination Address        (32 bits)
            IP address of the Intrazone Routing Table still
                        contains a route destination host

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

        * Next Hop # 1 Address       (32 bits)
            IP address of the "next hop" host to N and the length destination host

        * Next Hop # 2 Address       (32 bits)
            IP address of the
                        shortest route has increased due Next Hop #1 's "next hop" host to
            the route
                        removal, then destination host

        * Node/Link Metrics          (X * 32 bits)
                This section of the an IARP packet containing the
                        shortest route to N through X is broadcasted.
		        2) If used to report the quality of
                this link (or link source node).

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

                * Metric Value       (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 contains no
                        more routes

            +---------+--------|-----------------------------------------+
            |  Dest   | Subnet |               Routes                    |
            |  Addr   |  Mask  |-----------+-----------+-----+-----------+
            |         |        |     0     |     1     | ==> |    M-1    |
            +---------+--------|-----------+-----------+-----+-----------+
            |         |        |           |           | ==> |           |
            |---------+--------|-----------|-----------|-----|-----------|
            |         |        |           |           | ==> |           |
            |---------+--------|-----------|-----------|-----|-----------|
            |         |        |    | |    |           | ==> |           |
            +---------+--------|----| |----+-----------+-----+-----------+
                                    | |
                                    | +---\  +----------|--+--+   +--+
                                    +-----/  |          |  |  |...|  |
                                             +----------|--+--+   +--+
                                               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 N, then an notify the IARP packet containing
                        a route 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 D through X notify the IARP that direct contact
                has been confirmed with hop count of INF is
                        broadcast. A "Host Lost" interrupt is generated "host" (with subnet mask "mask").
                Any node/link quality measurements are reported in
                the "metric" list.
        C.4  IERP
            C.4.1  Zone_Node_Lost(host)
                Used by IARP to alert notify the IERP that D has moved beyond a node no longer
                exists within the routing zone.

    E.  Pseudocode Implementation

	E.1  Update Intrazone Routing Table

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

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

4.2 IntErzone

Haas, Pearlman                Expires December 1999                  [Page
11]

INTERNET DRAFT              The Zone Routing Protocol (IERP)                June
1999

   D.  State Machine

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

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

        D.1
            Event:   An IARP packet is received containing route
                   information to hosts which are beyond a node's routing
   zone. destination D. The IERP acquires routing information reactively, exploiting hop count
                   associated with the knowledge of received route is LESS THAN
                   OR EQUAL TO the routing zone topology through the bordercasting
   delivery service.

   This version of radius.  The
                   second next-hop is EQUAL to X.

            Action:  NONE

        D.2
            Event:   An IARP packet is received containing route
                   information to a destination D. The hop count
                   associated with the IERP extends received route is LESS THAN
                   the basic query / reply mechanism
   described routing zone radius.  The second next-hop
                   is NOT EQUAL to X.

          Action:  The received route is recorded in Section 3.  In the basic protocol, queries are
   terminated before reaching the query destination.  This provides
   a faster response to Intrazone
                   Routing Table. If the received route query is shorter
                   than if the destination, D,
   were previous shortest route to respond directly.  However, because D never receives the
   query, it does not acquire D, then a new
                   IARP packet containing route back information to D
                   through X is broadcasted.

        D.3
            Event:   An IARP packet is received containing route
                   information to a destination D. The hop count is
                   EQUAL TO the source, S.  If routing zone radius.  The second
                   next-hop is NOT EQUAL to X.

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

Haas, Pearlman                Expires December 1999                  [Page
12]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        D.4
            Event:   An IARP packet is received containing route
                   information to send data back a destination D. The hop count is
                   equal to S (which INF.

            Action:  The route to D is often removed from the case, given Intrazone
                   Routing Table.
                        1) If the
   bi-directional nature of many applications), Intrazone Routing Table still
                        contains a separate route query
   from to D and the length of the
                        shortest route has increased due to S would have the route
                        removal, then the an IARP packet containing the
                        shortest route to be initiated.  This substantial overhead D through X is avoided by having broadcasted.
                        2) If the query forwarded Intrazone Routing Table contains no
                        more routes to D, by then an IARP packet containing
                        a route to D through X with hop count of INF is
                        broadcast.  A "Host Lost" interrupt is
                        generated to alert the node Y IERP that
   discovers D in its has moved
                        beyond the routing zone.  We refer to this as a QUERY
   EXTENSION.

   Both

        D.5
            Event:   A "Neighbor Found" interrupt is received,
                   indicating the source and destination can acquire routes to discovery of a neighbor host N.

            Action:  For each other
   through the BRP route accumulation mechanisms (to be discussed
   later).  Distributing route information destination in X's Intrazone Routing
                   Table, an IARP packet is sent to N containing the caches of the
   route's nodes can significantly reduce
                   best route to that destination. An IARP packet is
                   then broadcasted containing the size 1 hop route to N
                   through X.

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

            Action:  The one hop route to N is removed from the IERP packets
   and provide for a faster query response.  On
                   Intrazone Routing Table.
                        1) If the other hand, QOS
   requirements for a particular application may favor a source
   specified route.  (rather than Intrazone Routing Table still
                        contains a distributed next-hop approach).
   Source routing requires that the discovered route information be
   accumulated in the IERP packets, rather than cached.  This IERP
   implementation satisfies the demands for rapid query response to N and source routing support by two stages the length of the
                        shortest route reporting.  In has increased due to the
   first two stages, route information is cached by
                        removal, then the route's nodes
   (when possible).  Next-hop an IARP packet containing the
                        shortest route are quickly returned to N through X is broadcasted.
                        2) If the source
   in QUERY-REPLY packets and forwarded Intrazone Routing Table contains no
                        more routes to the destination in QUERY-
   EXTENSION packets.  At this point, bi-directional connectivity N, then an IARP packet containing
                        a route to D through X with hop count of INF is
   established.  In
                        broadcast. A "Host Lost" interrupt is generated
                        to alert the third stage, the source and destination can
   provide each other with complete source routes, by sending each
   other ROUTE-ACCUMULATION packets.  As these packets traverse the
   route, the cached route information is accumulated in the packets,
   thereby constructing the desired source route.

   Variations on this IERP implementation can be realized by combining
   or eliminating some of these stages.  For example, if source routing
   is not desired, the ROUTE-ACCUMULATION stage can be eliminated.
   Also, if all of the route's nodes elect not to cache IERP that D has moved beyond the
                        routing
   information (perhaps due to storage limitations), then the QUERY
   REPLY zone.

Haas, Pearlman                Expires December 1999                  [Page
13]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    E.  Pseudocode Implementation

        We define two complimentary operations on packets:
        extract(packet) and QUERY-EXTENSION packets essentially serve the role of
   ROUTE-ACCUMULATION packets, obviating the need for a separate
   ROUTE-ACCUMULATION stage.

   Because each node proactively maintains the local topology of its
   routing zone, it is not necessary for a source route to specify
   every hop along load(packet)

            extract (packet)
                extracts the route (i.e. strict source routing).  A properly
   chosen subset fields of the complete source route can be used to specify
   the route IARP packet to the destination, and where desirable, the reverse route
   back to following
                variables: {dest, mask, next_hop_1, next_hop_2,
route_metric,
                            hop_count}

            load (packet)
                loads the source.  The IERP supports such an optimization through
   a final ROUTE-OPTIMIZATION stage.  The details values of the route
   optimization are described in aforementioned variables into
                the BRP specification.  Upon
   completion fields of the ROUTE-OPTIMIZATION stage, sufficient routing zone
   membership is acquired IARP packet.

     E.1  Update Intrazone Routing Table

        if (packet arrived)
           extract(packet)
        else
        {
           {dest,mask,metric} <-- intrpt
           next_hop_1=dest
           if (type(intrpt) == "Neighbor Found")
           {
              for d = each node in the route so that the source
   route may be reduced (by translating this route reduction into
   an appropriate set covering problem, Intrazone_Routing_Table
              {
                 best_route = get_shortest_route(Intrazone_Routing_Table,d)
                 mask       = 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
        }

        former_best_route = get_shortest_route(Intrazone_Routing_Table,dest)

Haas, Pearlman                Expires December 1999                  [Page
14]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        if (hop_count < INF)
        {
             if(next_hop_2 != MY_ID)
           {
              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 = get_shortest_route(Intrazone_Routing_Table,dest)
        if (best_route != NULL)
        {
           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)
           }
        }
        else
        {
           force_intrpt("IERP","Zone Node Lost",{dest})
           packet <-- {dest, mask, MY_ID, MY_ID, NULL, INF}
           send(packet,BROADCAST)
        }

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 on the
   link state (neighbor connectivity) of each routing zone node. A node may
   receive link state updates either from an IARP link state packet or from
   an interrupt generated by its Neighbor Discovery / Maintenance (NDM)
   process*.  Link states are maintained in a Link State Table.  When all
   pending link state updates have been received (full link state updates
may
   contain multiple links and employing span multiple packets), the routing table is
   recomputed, using a suitable
   heuristic).

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

  (1)  search minimum spanning tree algorithm.  The Link State
Table
   is then updated to remove links that lie outside of the routing zone.
All
   new link state updates for      	              QUERY
       route               |-------------------------->

                	              QUERY                QUERY
  (2)  establish          	      REPLY              EXTENSION
       connectivity        <--------------------------|
			   		              |=============>

  (3)  provide                        ROUTE-ACCUMULATION
       source route   	   |---------------------------------------->
                           <========================================|

  (4)  optimize                       ROUTE-OPTIMIZATION
       source route        <----------------------------------------|
                           |========================================>

              Sequence non-peripheral routing zone nodes are
forwarded
   to all neighbors.  In addition, if a new neighbor is discovered, the new
   neighbor is sent the FULL link states of all non-peripheral routing zone
   nodes.

   * IARP relies on the IERP Route Discovery Stages
   A.  Packet Format
                    1	                2	            3
0 services of a separate protocol (referred to
     here as the Neighbor Discovery/Maintenance Protocol) to provide
     current information about a host's neighbors.  At the least, this
     information must include the IP addresses of all the neighbors.
     The IARP can be readily configured to support supplemental
     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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type  | Rsvd  |   Hops Left   |         Query ID              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                   Bad                      Link Source Address  (repair only)                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                       Next IERP                    Link Destination Address                   |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  BRP
|                       Next BRP                     Packet Source Address                     | fields
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Link State ID         |                       Prev IERP Address  Zone Radius  |     Flags     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                       Hop 0 Address (Source)
|            Link Destination Subnet Mask  (Optional)           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|   RESERVED    |                       Hop 1 Address  Metric Type  |          Metric Value         |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|   RESERVED    |  Metric Type  |          Metric Value         |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                               | |                                 Link
                              \| |/                              route                               Metrics
                               \ /                                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|   |
|                      Hop (N-2) Address                        |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|                      Hop (N-1) Address (Destination)   RESERVED    |  Metric Type  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--          Metric Value         |                      Flags   (optional)   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--

Haas, Pearlman                Expires December 1999                  [Page
16]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        Field Description:

        * Type                        (4 Link Source Address           (32 bits)
		Identifies the type of IERP packet.  The current version
            IP address of IERP contains five packet types:

		QUERY:
			request for an Interzone source route to the
			destination specified by the reported link's source node.

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

        * Packet Source Address

                QUERY-EXTENSION:
			extension         (32 bits)
            IP address of a QUERY packet sent from the node that discovers the Destination to the
			Destination itself.

                QUERY-REPLY:
                        response to a QUERY packet, sent from the node
                        that discovers the Destination back this packet.
            (Used to the
			Source.  At a minimum, the QUERY-REPLY contains
                        next-hop route information account for any outstanding link state information)

        * Link State ID                 (16 bits)
            Sequence number used to track the Destination.
 			(In general, returns link state history of
            the Link Source node.

        * Zone Radius                   (8 bits)
            Routing zone radius of the link's source route up to node.  Determines the first node which has cached routing
                        information.  If no nodes have cached routing
                        information, then the complete source route is
                        returned.)

                ROUTE-ACCUMULATION (optional):
                        sent by the Source to the Destination, in
                        response to a QUERY-REPLY, and sent by the
                        Destination to the Source, in response to a
                        QUERY-EXTENSION.  Routing
            extent that link state information cached
			at the route's nodes is accumulated in propagates.

        * Flags                         (8 bits)
             Flags(0)   Full Link Information
                 Indicates whether this
			packet, providing link state information was sent as:
                          (0) a complete source route at
			the destination PARTIAL link state update
                                      OR
                          (1) part of this packet.

                ROUTE-OPTIMIZATION (optional):
                        sent by the Source to the Destination, and
			by the Destination to the Source, in response
			to a ROUTE-ACCUMULATION.  Flags are appended
			to this packet reflecting the mutual routing
			zone membership FULL update  of each node in all the source
			route.
                              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.

Haas, Pearlman                Expires December 1999                  [Page
17]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        * Query ID            	      (16 bits)
		Sequence number which, along with the Source Address
		(see below) uniquely identifies any route query in the
                network. Node/Link Metrics             (X * Hops Left                   (8 32 bits)
                Number of hops that a route query may continue to
                propagate.
                This field allows a querying node to
                configure the depth section of a route search, the packet is used to
                control report the amount quality of IERP traffic generated.
                this link (or link source node).

                * Bad Link Address            (32 Metric Type           (8 bits)
                Used during route repairs.  Contains the IP Address
                corresponding to the source
                      Type of routes failed link. metric being reported
                      (based on pre-defined metric types)

                * Next IERP Address           (32 Metric Value          (16 bits)
                IP address
                      Value of the next IERP recipient

        * Next BRP Address            (32 bits)
                IP address of the next BRP recipient.
                (i.e. next hop to the next IERP recipient)

        * Prev IERP Address           (32 bits)
                IP address of the previous IERP recipient
        * Source Route                (N * 32 bits)
                Variable length field that contains the IP addresses of
                the source route's nodes.
                        - route(0) contains the IP address of the
			  route's source.
                        - route(N-1) contains the IP address of the
                          route's destination
                        - in general, route(n) contains the IP address
			  of the n-th hop of the source route

        * Flags                       (N * 32*ceil(N/32) bits)
                The k-th bit of the n-th flag subfield indicates whether
                route(k) is located within route(n)'s routing zone.
                This routing zone membership information, collected
                during the optional ROUTE-OPTIMIZATION stage, may be
		used to determine the shortest possible specification
		for the accumulated source route. node / link metric specified by Metric Type

    B.  Data Structures

    B.1  Intrazone Routing Table (See IARP Description)

	B.2	Interzone Routing Table

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    +---------+--------|-----------------------------------------+
    |  Dest   | Subnet |                Routes                   |
    +  Dest   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  Addr   |  Mask  |-----------+-----------+-----+-----------+
    |         |        |     0     |     1     | ==> |    M-1    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    +---------+--------|-----------+-----------+-----+-----------+
    |         |        |           |           | ==> |           |
    |---------|-----------|-----------|-----|-----------|
    |---------+--------|-----------|-----------|-----|-----------|
    |         |        |           |           | ==> |           |
    |---------|-----------|-----------|-----|-----------|
    |---------+--------|-----------|-----------|-----|-----------|
    |         |        |    | |    |           | ==> |           |
    +-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    +---------+--------|----| |----+-----------+-----+-----------+
                            | |
		  \   /
		   \ /
		+-+-+-+-+   +-+-+-+-+          +-+-+-+-+
                            |   0   |==>|   1   |==> ...==>|  N-1 +---\  +----------|--+--+   +--+
                            +-----/  |	source
		+-+-+-+-+   +-+-+-+-+          +-+-+-+-+          |  |  |...|  |
                                     +----------|--+--+   +--+
                                       Next Hop      route
		  source      first		 (N-1)
		   host        hop	          hop
    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 an
                IERP packet.
	    C.2.2  Deliver()	(same interface as IP deliver())
		Used by the BRP to alert the IERP  of the arrival of a
		data packet.
	C.3  IARP
            C.3.1  Zone_Node_Lost(host)
                Used by the IARP to notify the IERP that a
                                       node 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)

    D. ID      metrics

Haas, Pearlman                Expires December 1999                  [Page
18]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

     B.2  Link State Machine Table

     +--------+--------+------------+
     |  Link  |  Zone  | Link State |        Link State Information
     | Source | Radius |     ID     |
     +--------+--------+------------+     +---|---|-----|-+
+---|---|-----|-+
     |        |        |            |---> |   |   | | | | |...|   |   | | |
| | **
     |        |        +------------+     +---|---|-----|-+
+---|---|-----|-+
     |        |        |            |-+
     |        |        +------------+ |   +---|---|-----|-+
     :        :        :     ||     : +-> |   |   | | | | |
     :        :        :    \||/    :     +---|---|-----|-+
     :        :        :     \/     :
     |        |        +------------+     +---+---|-----|-+
     |        |        |            |---> |   |   | | | | |
     +--------+--------+------------+     +---+---|-----|-+
     |   ||   |   ||   |     ||     |      (a) (b)  (c) (d)
     :   ||   :   ||   :     ||     :
     :  \||/  :  \||/  :    \||/    :
     |   \/   |   \/   |     \/     |
     +--------+--------+------------+

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

                  **   The IERP protocol consists of only one first link state (IDLE). Therefore,
        no entry for each link source
                       contains the complete link state transitions need to be specified. The IERP immediately
        acts upon an event and then returns back information
                       corresponding to the IDLE Link State ID.
                       Subsequent entries contain only changes of a single
                       link state.

	Note:  1) X is used as

                       A FULL link state entry of link state #k and
                       a label for the host running this PARTIAL entry of link 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 #(k+1) can be
                       merged into 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.
                     The query_id is incremented and assigned FULL link state entry of
                       link state #(k+1)

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

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

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

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

Haas, Pearlman                Expires December 1999                  [Page
19]

INTERNET DRAFT              The route is initialized with the
                     IP addresses Zone Routing Protocol                June
1999

   B.5  Former Routing Zone Nodes
        (list of the route's source and destination routing zone nodes, prior 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 addresses (X and D).  Finally, standard)
            C.1.2  Deliver()    (specified in IP standard)
        C.3  NDM
            C.3.1  Neighbor_Lost(host,mask,metric)
                Used by the QUERY packet
                     is bordercasted.

	D.3
            Event:   A "Source_Route_Failed" or "Proactive_Repair"
                     interrupt is received, indicating 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 next
		     hop, H, specified "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
                the "metric" list.
        C.4  IERP
            C.4.1  Zone_Node_Lost(host)
                Used by IARP to notify the IERP that a source route does not
		     appear node no longer
                exists within the routing zone.

            Action:  A limited depth route discovery

   D.  State Machine

        The IARP protocol consists of only one state (IDLE). Therefore,
        no state transitions need to H is initiated. be specified. The query_id is incremented IARP immediately
        acts upon an event and assigned then returns back to a new
                     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.
		     Finally, the QUERY packet is bordercasted.
	D.4
            Event:   A QUERY packet is received with a  destination that
                     appears within X's routing zone.

            Action:  A QUERY-REPLY IDLE state.

        Notes:  1) X is sent back to the query source, and used as a QUERY-EXTENSION is sent to label for the query destination.

	D.5
            Event:   A QUERY packet host running this state
                   machine.
                2) INF is received with a destination that
                     DOES NOT appear within X's routing zone.

            Action:  The QUERY packet is bordercasted.

	D.6 reserved field value corresponding to
                   "infinity".

        D.1
            Event:   A QUERY-EXTENSION   An IARP link state packet is received.

            Action:  The packet contents are moved to a ROUTE-
		     ACCUMULATION packet.  The ROUTE-ACCUMULATION
		     packet link state update is sent to recorded in the query source.
        D.7
            Event:   A QUERY-REPLY packet is received.

            Action:  The packet contents Link State
Table.
                     If more link state updates are moved pending, then the IARP
                     returns to a ROUTE-
		     ACCUMULATION packet.  The ROUTE-ACCUMULATION
		     packet is an idle state.  Otherwise, X rebuilds its
                     routing table.  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 to the query destination.

        D.8 link states of
X's
                     NON-peripheral nodes, and 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 ROUTE-ACCUMULATION packet is received.  X "Neighbor Found" interrupt is not received, indicating
                     the final destination discovery of this packet
                     (i.e. X != IERP_next).  This only occurs when the
                     accumulated route contains a repair neighbor N.

            Action:  The bad  X's new link to N is replaced by the path repair recorded 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 Link State Table
and
                     N is added to the
                     Interzone Routing Table or replaces a failed route
		     if New Neighbors List.  If more link
state
                     updates are pending, then the packet specifies a bad link.  In addition,
                     if IARP returns to an idle
                     state.  Otherwise, X is rebuilds its routing table.  Links
                     that lie outside of the ROUTE-ACCUMULATION destination, routing zone are removed from
the
                     packet contents may be moved to a ROUTE-
		     OPTIMIZATION packet, which is then
                     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 to the query destination (query source).

        D.10 link states of X's NON-peripheral nodes,
and
                     the New Neighbor List is cleared.

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

            Action:  The routing zone membership information that lost link to neighbor N is
                     collected in removed from the ROUTE-OPTIMIZATION packet Link
                     State Table and N is
                     processed.  The resulting optimized route(s) removed from the New Neighbor
List.
                     If more link state updates are
		     added pending, then the IARP
                     returns to an idle state.  Otherwise, X rebuilds its
                     routing table.  Links that lie outside of the Interzone Routing routing
                     zone are removed from the Link State Table.  X sends
its
                     neighbors all previously unforwarded link state updates
                     from its NON-peripheral nodes.  Finally, all neighbors
                     in the New Neighbor List are sent the link states of
X's
                     NON-peripheral nodes, and the New Neighbor List is
                     cleared.

    E.  Pseudocode Implementation

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

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

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

Haas, Pearlman                Expires December 1999                  [Page
21]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

    E.1 Routing Zone Node Lost

            {lost_host} <-- intrpt
            repair_link = FALSE
            for host = each host in Interzone  Update Intrazone Routing Table
            {
              for (route = each Interzone route to host)
              {
	        if (lost_host (EXISTS IN) route)
                {

        if (PROACTIVE_REPAIRS_ENABLED) (packet arrived)
        {
                        removal_timer = ROUTE_QUERY_TIMEOUT
                        repair_link
            extract(packet)
            my_link_changed = TRUE FALSE
        }
        else
                        removal_timer = 0
                    schedule(
			remove(Interzone_Routing_Table[host]->route(m)),
                        removal_timer)
                }
              }
            }
            if(repair_link)
        {
                bad_link = my_id + lost_host
                force_intrpt("IERP","Proactive_Repair", bad_link)
            }

	E.2  Initiate Route Discovery

            {route}
            {link_dest,mask,link_metric} <-- intrpt

            dest            = route(length(route)-1)
            current_hop_ptr = get_index(route, my_id)
            prev_hops
            link_source = route(0: current_hop_ptr-1)

            route MY_ID
            pk_source   = prev_hops + my_id + dest
            if (type(intrpt) == "Proactive_Repair" ||
                type(intrpt) == "Source_Route_Failed")
            {
                hops_left MY_ID
            state_id    = MAX_REPAIR_HOPS
                bad_link_source MY_LINK_STATE_ID
            radius      = my_id
            }
            else
            {
                hops_left MY_ROUTING_ZONE_RADIUS

            full_link_state = MAX_FULL_QUERY_HOPS
                bad_link_source 0
            current_update  = NULL
            }
            query_id ++
            load (packet)
            send (packet, BORDERCAST)
        E.3  Receive IERP Packet

            extract(packet)
            source=route(0)
            dest COMPLETE
            all_updates     = route(length(route)-1)
            switch(pk_type)
            {
                case:  QUERY COMPLETE

            if (dest (EXISTS IN) Intrazone_Routing_Table)
                    {
                        type = QUERY-REPLY
                        if(bad_link_source)
                            IERP_next (type(intrpt) == "Neighbor Found")
                link_status = bad_link_source UP
            else
                            IERP_next
               link_status = source
                        load(packet)
                        send(packet)

                        type = QUERY-EXTENSION
                        IERP_next DOWN

            my_link_changed = dest
                        load(packet)
                        send(packet) TRUE
        }
                    else
                        bordercast(packet)
              break
              case:  QUERY-EXTENSION
                    type = ROUTE-ACCUMULATION
                    IERP_next=source
                    send(packet)
              break
              case:   QUERY-REPLY
                    type = ROUTE-ACCUMULATION
                    IERP_next = dest
                    load (packet)
                    send (packet)
              break
              case:   ROUTE-ACCUMULATION
                if (bad_link_source)
                {
                  path_source_ptr = get_index(route, bad_link_source)
                  path_dest_ptr

        add(Pending_Link_State_List, link_from_id)
        status = get_index(route, dest) add(Link_State_Table,link_source, link_dest, mask, radius,
                     link_metric, state_id, flags)
        if (IERP_next (status == source) NEW_LINK_INFO)
        {
                     bad_link     = bad_link_source + dest
                     path_repair
           cum_status = route(path_source_ptr:path_dest_ptr)
                  } UPDATE_IN_PROGRESS
           if(my_link_changed)
           {
              if (IERP_next (link_status == dest)
                  {
                     bad_link     = dest + bad_link_source
                     path_repair  = reverse(route(path_source_ptr :
                                                    path_dest_ptr)) UP)
                 add(New_Neighbor_List, link_dest)
              else
                 remove(New_Neighbor_List, link_dest)
              MY_LINK_STATE_ID++
           }
                  replace(Interzone_Routing_Table, bad_link,path_repair)
        }
                else
                {
                  if (my_id == source)
                    add(Interzone_Routing_Table, route)
                  if (my_id

        if(all_updates == dest)
                    add(Interzone_Routing_Table, reverse(route))
                }

                if (my_id 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 == IERP_next) UPDATE_IN_PROGRESS)
        {
                  if (my_id == source)
                    IERP_next
            for(each node (BELONGING TO) Intrazone_Routing_Table)
               add(Former_Routing_Zone_Nodes, node)

            rebuild = dest
                  if (my_id == dest)
                    IERP_next TRUE;
            while (rebuild)
            {
               Intrazone_Routing_Table
                                    = source

                  type
construct_spanning_tree(Link_State_Table);
               rebuild = ROUTE-OPTIMIZATION
                  load (packet)
                  send (packet) update(Link_State_Table);
            }
              break
              case:   ROUTE-OPTIMIZATION
                if (my_id == source)
                    add(Interzone_Routing_Table, route, flags)
                if (my_id == dest)
                    add(Interzone_Routing_Table, reverse(route), flags)
              break

            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})
            }

4.3 Bordercast Resolution Protocol (BRP)
            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 to hosts which are beyond a node's routing
   zone.  The BRP is a sublayer of the IERP that performs acquires routing information reactively, exploiting
   the operations knowledge of
   bordercasting, query control, route accumulation and the routing zone
   labelling, which form the basis for topology through the route discovery procedure.

   In this BRP implementation, bordercasting is implemented as a series
   delivery service.

   This version of unicasted messages to the peripheral nodes.  The BRP is able to
   identify the peripheral based on IERP extends the information contained basic query / reply mechanism
   described in Section 3.  In the
   Intrazone Routing Table.  Rather than unicasting to the peripheral
   node directly through IP, the bordercasted packets basic protocol, queries are relayed to
   the peripheral nodes by
   terminated before reaching the BRP layer.  IP is used only query destination.  This provides
   a faster response to send
   these messages one hop toward the peripheral nodes.  This allows route query than if the
   BRP destination, D,
   were to detect all QUERY packets that are received by that node.

   To efficiently terminate respond directly.  However, because D never receives the
   query, the BRP needs to record
   sufficient information from each detected query.  The query's source
   and ID, which serve to uniquely identify it does not acquire a query, are added route back to the
   Detected Queries Table.  In addition, the IP address of source, S.  If the last
   node
   D needs to bordercast the query send data back to S (which is also recorded in often the Detected
   Queries table.  Any threads case, given the
   bi-directional nature of this many applications), a separate route query that are later received
   from a different bordercasting node are discarded.  Each query also
   contains a hop counter that D to S would have to be initiated.  This substantial overhead
   is decremented at each node.  When avoided by having the
   counter expires, query forwarded to D, by the packet is discarded.

   IERP packets (excluding ROUTE-OPTIMIZATION packets) node Y that are not
   terminated next undergo
   discovers D in its routing zone.  We refer to this as a
   QUERY_EXTENSION.

   Both the source and destination can acquire routes to each other
   through the BRP route accumulation procedure.  As
   described earlier, mechanisms (to be discussed
   later).  Distributing route accumulation is used to construct routes,
   by recording information in the IP addresses caches of a the
   route's nodes in can significantly reduce the size of the IERP packet
   or local cache.  The Detected Queries Table, extended by two
   columns, serves as packets
   and provide for a convenient route accumulation cache.

   The node begins faster query response.  On the other hand, QOS
   requirements for a particular application may favor a source
   specified route.  (rather than a distributed next-hop approach).
   Source routing requires that the discovered route accumulation procedure by adding its IP
   address to information be
   accumulated in the IERP route. packets, rather than cached.  This is followed by the IP addresses of
   any cached nodes leading to IERP
   implementation satisfies the packet's destination (the "next
   hops").  This is sufficient processing demands for ROUTE-ACCUMULATION
   packets, where complete source routes are constructed.  On the other
   hand, QUERY, QUERY-EXTENSION rapid query response
   and QUERY-REPLY packets should carry as
   little source routing support by two stages of route reporting.  In the
   first two stages, route as possible.  Therefore, if cache space information is
   available, cached by the route accumulation process records the IP addresses
   of the "previous hops" from route's nodes
   (when possible).  Next-hop route are quickly returned to the packet's source, source
   in ROUTE_REPLY packets and removes them
   from the IERP packet.

   The final role of forwarded to the BRP destination in QUERY_
   EXTENSION packets.  At this point, bi-directional connectivity is contribute to
   established.  In the ROUTE-OPTIMIZATION
   process third stage, the source and destination can
   provide each other with complete source routes, by indicating sending each
   other ROUTE_ACCUMULATION packets.  As these packets traverse the mutual routing zone membership of
   route, the
   nodes cached route information is accumulated in the packets,
   thereby constructing the desired source route.  This is done

   Variations on this IERP implementation can be realized by appending a special
   flag field to combining
   or eliminating some of these stages.  For example, if source routing
   is not desired, the ROUTE-OPTIMIZATION packet.  The status ROUTE_ACCUMULATION stage can be eliminated.
   Also, if all of the
   k-th bit in route's nodes elect not to cache the flag field indicates whether routing
   information (perhaps due to storage limitations), then the k-th hop in ROUTE_
   REPLY and QUERY_EXTENSION packets essentially serve the
   source route is a member role of
   ROUTE_ACCUMULATION packets, obviating the node's need for a separate
   ROUTE_ACCUMULATION stage.

Haas, Pearlman                Expires December 1999                  [Page
24]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

   Because each node proactively maintains the local topology of its
   routing zone.  This
   membership information zone, it is eventually processed at the not necessary for a source route to
   determine specify
   every hop along the smallest set route (i.e. strict source routing).  A properly
   chosen subset of routing zones that cover the complete source route
   (and therefore the smallest set of nodes needed can be used to specify this
   the route through loose source routing.)
    A.  Packet Format

	See IERP packet format in Section 4.2

    B.  Structures

        B.1  Intrazone to the destination, and where desirable, the reverse route
   back to the source.  The IERP supports such an optimization through
   a final ROUTE_OPTIMIZATION stage.  The details of the route
   optimization are described in the BRP specification.  Upon
   completion of the ROUTE_OPTIMIZATION stage, sufficient routing zone
   membership is acquired for each node in the 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 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 Table    (see IARP description)

        B.2  Detected Queries Table

    |--------------------|--------|-----------------------| 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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  Query     Type      |  Query      TTL      |  Prev   Hop Count   |    Prev     Flags     |    Next
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |    Current    |  Source    ROF Ptr    |   Id Num Dests = D |  IERP Num Nodes = N |   Hop(s)
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   Hop(s)            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 IERP Address                       |   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
    |--------------------|--------|-----------------------|
    |
                                     \|/
                                   +---+   +---+       +---+                       Next BRP Address                        | A |-->| B |-->...  BRP
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fields
    | C                       Prev IERP Address                       |
                                   +---+   +---+       +---+
                                    cached "source"   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
    |                 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
                                  \| |/
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
    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 the
                        destination specified by the Destination
                        IP Address

                QUERY_EXTENSION:
                        extension of a data QUERY packet
	    C.2.2  Deliver()  (same interface as IP Deliver() primitive)
		Used by sent from the BRP
                        node that discovers the Destination to alert the higher layer protocol of
                        Destination itself.

                ROUTE_REPLY:
                        response to a ROUTE_QUERY packet, sent from the arrival of node
                        that discovers the Destination back to the Source.
                        At a data packet
	C.2  Lower Layer (IP)
	    C.2.1  Send()	(specified in IP standard)
	    C.2.2  Deliver()	(specified in IP standard)

    D.  State Machine

	The BRP protocol consists of only one state (IDLE).  Therefore,
        no state transitions need minimum, the ROUTE_REPLY contains
                        next-hop route information to be specified. The BRP immediately
        acts upon an event and then the Destination.
                        (In general, returns back the source route up to
                        the IDLE state.

	Notes: 1) X is used as a label for first node which has cached routing
                        information.  If no nodes have cached routing
                        information, then the host running this state
                  machine.
	       2) NULL complete source route is a reserved field value, corresponding
                        returned.)

                ROUTE_ACCUMULATION (optional):
                        sent by the Source to an
                  invalid IP address.

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

            Action:  If X is Destination, in
                        response to a ROUTE_REPLY, and sent by the query's source, then
                        Destination to the identifying
                     querying Source, in response to a
                        QUERY_EXTENSION.  Routing information cached
                        at the route's nodes is recorded accumulated in this
                        packet, providing a complete source route at
                        the Detected
		     Queries Table. X adds its IP address 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
		     packet's route.  A copy of Destination, and by the packet is sent
                        Destination to the IERP layer Source, in response to a
                        ROUTE_ACCUMULATION packet.  Route Optimization
                        Flags (ROF) are appended to this packet,
                        reflecting the mutual routing zone membership
                        of each peripheral node, by way node in the source route.

        * TTL (Time to Live)                   (8 bits)
                Number of hops that a BRP transmission route query may continue to the next hop
                propagate. This field allows a querying node to that
		     peripheral node.
        D.2
            Event:   A QUERY packet is received from
                configure the IP.  The hop
                     counter has expired or depth of a route search, in order to
                control the query was already
                     detected from another bordercasting node.

            Action:  The packet is discarded.

        D.3
            Event:   A QUERY packet is received from IP.  The hop amount of IERP traffic generated.

        * Hop Count                            (8 bits)
                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:  If cache space is available, identifying query
                     information SHOULD be recorded in the Detected
		     Queries Table.  The packet is then discarded.

        D.4
            Event:   A QUERY packet is received from the IP.  The source to current node (ROUTE_QUERY,
                QUERY_EXTENSION) or hop count has not expired and the query has not been
		     previously detected (or was previously detected from source to route
destination
                (ROUTE_REPLY, ROUTE_ACCUMULATION, ROUTE_OPTIMIZATION).

        * Flags                                (8 bits)
                 Flags(0)        ANY destination (0) / ALL destination (1)
                        In the same bordercasting node).  X is the
		     intended BRP recipient, but is not the intended
		     IERP recipient and case of multiple destinations, specifies
whether
                        the query destination does
		     not lie within X's routing zone.

            Action:  The hop counter is decremented.  If cache space
                     is available, identifying query information and
                     accumulated route information ROUTE_QUERY should be recorded
                     in the Detected Queries Table.  The recorded route
                     information is removed from return routes for ANY
specified
                        destination, or ALL specified destinations.

                        In the packet and X adds
		     its case of a single MULTICAST IP address to address,
specifies
                        whether the route.
                     The packet is then sent ROUTE_QUERY should return routes to ANY
                        member of the BRP multicast group, or ALL members of the next hop
                     to
                        multicast group.

                 Flags(1)       Passed Bad Link Source
                        In the intended IERP recipient.

        D.5
            Event:   A QUERY packet is received from case of a "route repair", indicates whether
the IP.  The hop
		     count
                        ROUTE_REPLY has not expired and passed 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 Bad Link Source node.

                 Flags(2..7)     RESERVED for future use

        * Current                              (8 bits)
                INDEX of the
		     intended IERP recipient, OR route (see below) corresponding to the query destination
                     lies in X's routing zone.

            Action:  The hop counter is decremented.  If cache space
                     is available, identifying query information and
                     accumulated route information should be recorded
node
                that has most recently received this packet.  (the first
node
                in the Detected Queries Table.  The recorded route
                     information is removed from the packet and X adds
		     its IP address has an index of 1).

        * ROF Pointer                          (8 bits)
                Pointer to the route.
                     The packet is then delivered up to starting location of the IERP.

        D.6
            Event:   A QUERY-EXTENSION Route Optimization
                Flags (ROUTE_OPTIMIZATION phase).  The ROF Pointer is received
measured
                in units of 32 bit words from the IERP.

            Action:  The packet is sent to front of the BRP layer packet.

        * Number of Destinations = D           (8 bits)
                Number of destinations included in the
                     next hop route query/reply
packet.
                This allows multiple route discoveries to the specified IERP recipient
                     (in this case, the be consolidated
                into a common route query destination).

        D.7
            Event:   A QUERY-EXTENSION process.  The multiple query
                destinations feature is received from particularly  useful for routing to
a
                multicast group with known members, or for locating
downstream
                nodes during the IP.
                     X is not route repair phase.

Haas, Pearlman                Expires December 1999                  [Page
28]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

        * Number of Nodes = N                  (8 bits)
                Number of nodes IP addresses appearing in the intended BRP recipient.

            Action:  If cache space is available, identifying query
                     information SHOULD be recorded route
                specification.

        * Query ID                             (16 bits)
                Sequence number which, along with the Query Source Address
                (see below) uniquely identifies any ROUTE_QUERY in the Detected
		     Queries 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
network.

        * Reply ID                             (16 bits)
                 Sequence number which, along with the
		     intended IERP recipient.

            Action:  If cache space is available, identifying query
                     information and accumulated route information
                     should be recorded Replying Node Address
                 (see below) uniquely identifies any ROUTE_REPLY in the Detected Queries Table.
		     The recorded route information is removed from the
		     packet and X adds its
network

        * Query/Route Source Address           (32 bits)
                IP address to the route.
                     The packet is then sent to the BRP of the next hop node that initiates the ROUTE_QUERY.
                In subsequent stages, this corresponds to the intended IERP recipient.

        D.9
            Event:   A QUERY-EXTENSION packet is received from IP address of
the IP.
                     X is
                discovered route's source node.

        * Replying Node Address                (32 bits)
                IP address of the intended BRP recipient and node that initiates the intended
                     IERP recipient.

            Action:  If cache space ROUTE_REPLY.  Note
                that this is available, identifying query
                     information and accumulated route information
                     should be recorded in usually NOT the Detected Queries Table.
                     The recorded destination node.

        * Bad Link Source Address              (32 bits)
                Used during route information is removed from repairs.  Contains the
                     packet and X adds its IP address Address
                corresponding to the route.
                     The packet is then delivered up source of routes failed link.

        * Query/Route Destination Addresses    (D * 32 bits)
                List of IP addresses to be located during the IERP.

        D.10
            Event:   A QUERY-REPLY packet is received from ROUTE_QUERY
phase.
                (Either ANY or ALL addresses, depending on the setting of
                Flags(0))
                In subsequent stages, this field contains the IERP.

            Action:  The IP addresses address 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
                discovered route's (single) destination node.

        * Next IERP Address                    (32 bits)
                IP address of the next IERP layer recipient

        * Next BRP Address                     (32 bits)
                IP address of the query source, by way
		     of a next BRP layer transmission to the first recipient.
                (i.e. next hop back to the query source.

	D.11
	    Event:   A QUERY-REPLY packet is received from next IERP recipient)

        * Prev IERP Address                    (32 bits)
                IP address of the IP.
		     X is not previous IERP recipient

        * Route                                (N * 32 bits)
                Variable length field that contains the intended BRP recipient.

	    Action:  The packet is discarded.

	D.12
	    Event:   A QUERY-REPLY recorded IP
addresses
                of nodes along the path traveled by this ROUTE_QUERY packet is received
                from the IP.
		     X is the intended BRP recipient, but not the
		     intended IERP recipient.

            Action:  If cache space is available, accumulated Query Source.
                In subsequent stages (after a route
		     information to a Query Destination
has
                been discovered), this set of IP addresses provides a
partial
                specification of the destination should be recorded
		     in the Detected Queries Table, and the recorded route information removed from between the packet. Route Source and
Route
                Destination.

Haas, Pearlman                Expires December 1999                  [Page
29]

INTERNET DRAFT              The IP
		     addresses Zone Routing Protocol                June
1999

        * Node/Segment Metrics                    (X * 32 bits)
                This optional section of X and the previous hops back packet can be used to
                record a variety of node and segment quality measurements.
                (In this context, a segment refers to the
		     query source (cached communication path
                between consecutive nodes in the Detected Queries Table)
		     are added to the packet's accumulated route.
                     The packet
                In the case of neighboring nodes, a segment is then sent equivalent to the BRP layer
                a (one-hop) link).

                * Node                         (8 bits)
                      Index of the
		     previous hop back route corresponding to the query source.

	D.13
	    Event:   A QUERY-REPLY packet is received from the IP.
		     X is the intended BRP recipient and the intended
		     IERP recipient.

            Action:  If cache space is available, accumulated route
		     information to the destination should be recorded
		     in the Detected Queries Table, and the a particular node.

                * Metric Type                  (7 bits)
                      Type of metric being recorded
		     route information removed from the packet.
		     The packet is then delivered up to the IERP.

	D.14
	    Event:   A ROUTE-ACCUMULATION packet is received from
                      (based on pre-defined metric types)

                * Direction Flag               (1 bit)
                      For segment metrics, specifies either the
		     IERP.

	    Action:  The packet is sent to upstream
                      segment (toward Query/Route Source) or the IERP layer downstream
                      segment (toward Query/Route Dest).
                                    upstream   = 0
                                    downstream = 1

                * Metric Value                  (16 bits)
                      Value of the node / segment metric 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: Metric
Type

        * ROF (Route Optimization Flags)       ((N+2) * 32*ceil((N+2)/32)
bits)
                The packet is discarded.

	D.16
	    Event:   A ROUTE-ACCUMULATION packet is received from k-th bit of the
		     IP.  X n-th ROF subfield indicates whether
                Node k is located within Node n's routing zone.
                This routing zone membership information, collected
                during the intended BRP recipient, but not the
		     intended IERP recipient.

	    Action:  The IP addresses of X and the next hops optional ROUTE_OPTIMIZATION stage, may be
                used to determine the
		     intended IERP recipient (which are cached in the
		     Detected Queries Table) are added to shortest possible specification
                for the accumulated source 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.

Haas, Pearlman                Expires December 1999                  [Page
30]

INTERNET DRAFT              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 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)

                                         (a)  Node ID
                                         (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
		     intended IERP recipient.

	    Action:  The packet is delivered up to request transmission of an
                IERP packet.
            C.2.2  Deliver()    (same interface as IP deliver())
                Used by the IERP.

	D.18
	    Event:   A ROUTE-OPTIMIZATION packet is received from the
		     IERP.

	    Action:  X indicates (in its flag field) those route nodes
		     that belong to its routing zone.  The packet is
		     then sent BRP to alert the IERP layer  of the specified IERP
		     recipient, by way arrival of a BRP transmission to
                data packet.
        C.3  IARP
            C.3.1  Zone_Node_Lost(host)
                Used by the
		     next hop toward IARP to notify the IERP recipient.

	D.19
	    Event:   A ROUTE-OPTIMIZATION packet is received from the
		     IP.  X is not that a node has left
                the intended BRP recipient.

	    Action: 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

    D.  State Machine

        The packet is discarded.

	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 flag field) those route nodes
		     that belong protocol consists of only one state (IDLE). Therefore,
        no state transitions need to its routing zone. be specified. The packet is IERP immediately
        acts upon an event and then sent returns back to the IERP layer of the specified IERP
		     recipient, by way of IDLE state.

        Note:  1) X is used as a BRP transmission to the
		     next hop toward label for the IERP recipient.

	D.21 host running this state
                  machine.

        D.1
            Event:   A ROUTE-OPTIMIZATION packet "Zone_Node_Lost" interrupt is received received,
                     indicating that the node H has moved beyond the
                     routing zone.

            Action:  Remove every route from the
		     IP.  X 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 intended BRP recipient and the
		     intended IERP recipient.
                     ICMP, indicating an unknown destination host D.

            Action:  X indicates (in its flag field) those  A full depth route nodes
		     that belong discovery to its routing zone.  The packet D is then delivered up to the IERP

    E.  Pseudocode Implementation

        We define two complimentary operations on packets:
        extract(packet) initiated.
                     X's query_id is incremented and load(packet)

            extract (packet)
                extracts the fields of the IERP packet assigned to a new
                     ROUTE_QUERY packet.  The route is initialized with the following
                variables: {type, hops_left, query_id, bad_link_source,
                            next_IERP, next_BRP, prev_IERP, route, flag}

            load (packet)
                loads the values of the aforementioned variables into
                the fields
                     IP addresses of the IERP packet.

        E.1  Receive Packet from IERP

            extract (packet) route's source          = route(0)
            dest            = route(length(route)-1)
            current_hop_ptr = get_index(route, my_id)
            prev_hops       = reverse(route(0: current_hop_ptr-1))
            next_hops       = route(current_hop_ptr+1 : length(route)-1)

            IERP_prev = my_id
            switch(type)
            {
              case:  QUERY
                if ((bad_link_source == my_id || source == my_id)
                    add(Detected_Queries,packet)
                for (IERP_next = each host in Intrazone_Routing_Table)
                {
                    if (IERP next 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 peripheral node)
                    {
                      BRP_next=Intrazone_Routing_Table[host,0]->next_hop
                      load(pk_copy)
                      send(pk_copy,BRP_next)
                    }
                }
              break
              case:  QUERY-EXTENSION
                BRP_next=Intrazone_Routing_Table[IERP_next,0]->next_hop
                load(packet)
                send(packet,BRP_next)
              break
              case:  QUERY-REPLY
                if (prev_hops(0) == source)
                    prev_hops = Detected_Queries[source,query_id]
							     ->prev_hops source route = prev_hops + my_id + next_hops
                BRP_next = prev_hops(0)
		load(packet)
                send(packet,BRP_next)
              break
              case:  ROUTE-ACCUMULATION
                if(my_id == source)
                    BRP_next = next_hops(0)
                if(my_id == dest)
                    BRP_next = prev_hops(0)
		load(packet)
                send(packet,BRP_next)
              break
              case:  ROUTE-OPTIMIZATION
                flag = NULL
                for (i = 0 does not
                     appear within the routing zone.

            Action:  A limited depth route discovery to length(route)-1)
                {
                    if ((EXISTS) Intrazone_Routing_Table[route(i)])
                        flag = flag,1
                    else
                        flag = flag,0
                }
                if(my_id == source)
                    BRP_next = next_hops(0)
                if(my_id == dest)
                    BRP_next = prev_hops(0)
		load(packet)
                send(packet,BRP_next)
              break
	E.2  Receive Packet from IP

            extract(packet)

            source          = route(0)
            dest            = route(length(route)-1)
            current_hop_ptr = get_index(route, my_id)
            prev_hops       = reverse(route(0: current_hop_ptr-1))
            next_hops       = route(current_hop_ptr+1 : length(route)-1)

            switch(type)
            {
              case QUERY:
                if (hops_left > 0 &&
                    (!EXISTS(Detected_Queries[source,query_id] ||
                     Detected_Queries[source,query_id]->from
							== IERP_prev))
                {
                    hops_left --
                    if (!FULL (Detected_Queries))
                    {
                        add(Detected_Queries, packet)
                        prev_hops = source
                    }
                    else H is initiated.
                     The query_id is incremented and assigned to a new
                     ROUTE_QUERY packet.  The route = prev_hops + my_id + next_hops

                    if(BRP_next == my_id)
                    {
                        if(IERP_next == my_id ||
                           dest (EXISTS IN) Intrazone_Routing_Table)
                            deliver(packet,IERP)
                        else
                        {
                            BRP_next=Intrazone_Routing_Table[IERP_next]
                                                    ->route(0)->next_hop
                            load(packet)
                            send(packet, BRP_next)
                        }
                    }
                    else
                        discard(packet)
                }
                else
                    discard(packet)
              break
              case QUERY-EXTENSION:
                {
                    if (!FULL (Detected_Queries))
                    {
                        add(Detected_Queries,packet)
                        prev_hops = source
                    } 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 = prev_hops + my_id + next_hops

                    if(BRP_next == my_id)
                    {
                        if(IERP_next == my_id ||
                           dest (EXISTS IN) Intrazone_Routing_Table)
                            deliver(packet,IERP)
                        else
                        {
                            BRP_next=Intrazone_Routing_Table[IERP_next]
                                                    ->route(0)->next_hop
                            load(packet)
                            send(packet, BRP_next)
                        }
                    }
                    else
                        discard(packet)
                }
                else
                    discard(packet)
              break

              case QUERY-REPLY:
                if(my_id == BRP_next)
                {
                    if (!FULL (Detected_Queries))
                    {
                        add(Detected_Queries, packet)
                        next_hops = dest
                    }
                    if (prev_hops(0) == source)
                       prev_hops = Detected_Queries[source,query_id]
							    ->prev_hops
                    route = prev_hops + my_id + next_hops
                    if(my_id == IERP_next)
                        deliver(packet,IERP)
                    else
                    {
                        BRP_next = prev_hops(0)
			load(packet)
                        send(packet,BRP_next)
                    }
                }
                else
                    discard(packet)
              break
              case ROUTE-ACCUMULATION:
                if(my_id == BRP_next)
                {
                    if(my_id == IERP_next)
                        deliver(packet, IERP)
                    else
                    {
                        if (bad_link_source && IERP_next == source)
                        {
                          bad_link_ptr=get_index(route,bad_link_source)
                          if (current_hop_ptr <= bad_link_ptr)
                                deliver(packet, IERP)
			}
                        if (IERP_next == dest)
                        {
                          if(next_hops(0) == dest)
                             next_hops=Detected_Queries[source,query_id]
							     ->next_hops
                          BRP_next = next_hops(0)
                        }
                        if (IERP_next == source)
                        {
                          if(prev_hops(0) == source)
                             prev_hops=Detected_Queries[source,query_id]
							     ->prev_hops
                          BRP_next = prev_hops(0)
                        }
                        route = prev_hops + my_id + next_hops
                        load(packet)
                        send (packet,BRP_next)
                    }
                }
                else
                    discard(packet)
              break
              case ROUTE-OPTIMIZATION:
                if(my_id == BRP_next)
                {
                    f = NULL
                    for (i = 0: length(route)-1)
                    {
                      if ((EXISTS) Intrazone_Routing_Table[route(i)])
                        f = f,1
                      else
                        f = f,0
                    }
                    if (IERP_next == source)
                      flag = f , flag
                    else
                      flag = flag , f

                    if(my_id == IERP_next)
                        deliver(packet, IERP)
                    else
                    {
                      if(IERP_next == source)
                        BRP_next = prev_hops(0)
                      else
                        BRP_next = next_hops(0)
                      load(packet)
                      send (packet,BRP_next)
                    }
                }
                else
                    discard(packet)
              break

5. Other Considerations

5.1 Sizing failure.
                     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 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 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 Radius 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 == 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|)
                    }
                    if(MY_ID == IERP_next)
                    {
                        current_hop_ptr = 0
                        load(packet)
                        deliver(packet,IERP)
                    }
                    else
                    {
                        metric = {metric,get_metric(Intrazone_Routing_Table,
                                                    BRP_next)}
                        route = {prev_hops, MY_ID, next_hops}
                        current_hop_ptr = |prev_hops|+1
                        load(packet)
                        send(packet,BRP_next)
                    }
                }
                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 = route(1: current_hop_ptr-1)
                      next_hops = route(current_hop_ptr : |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(MY_ID == bad_link_source)
                          flags(1) = 1
                    }

                    if(IERP_next == dest)
                    {
                      prev_hops = route(1: current_hop_ptr)
                      next_hops = route(current_hop_ptr+1 : |route|)

                      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
                    {
                        if(flags(1) == 1)
                        {
                            load(packet)
                            deliver(packet, IERP)
                        }
                        metric = {metric,get_metric(Intrazone_Routing_Table,
                                                    BRP_next)}
                        route = {prev_hops, MY_ID, next_hops}
                        current_hop_ptr = |prev_hops|+1
                        load(packet)
                        send (packet,BRP_next)
                    }
                }
                else
                    discard(packet)
              break

              case ROUTE_OPTIMIZATION:
                if(MY_ID == BRP_next)
                {
                    f = NULL
                    for (node = {source,route,dest})
                    {
                      if ((EXISTS) Intrazone_Routing_Table[node])
                        f = {f,1}
                      else
                        f = {f,0}
                    }

                    if (IERP_next == source)
                    {
                      current_hop_ptr--
                      prev_hops = route(1: current_hop_ptr-1)
                      next_hops = route(current_hop_ptr+1 : |route|)
                      BRP_next = prev_hops(|prev_hops|)
                      ROF = {f,ROF}
                    }
                    if (IERP_next == dest)
                    {
                      current_hop_ptr++
                      prev_hops = route(1: current_hop_ptr-1)
                      next_hops = route(current_hop_ptr+1 : |route|)
                      BRP_next = next_hops(1)
                      ROF = {ROF,f}
                    }

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)
                    }
                    else
                    {
                      load(packet)
                      send (packet,BRP_next)
                    }
                }
                else
                    discard(packet)
              break

Haas, Pearlman                Expires December 1999                  [Page
52]

INTERNET DRAFT              The Zone Routing Protocol                June
1999

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], it was shown that a node can accurately
   estimate its optimal zone radius, on-line, based on local measurements of
   ZRP traffic.  The re-sizing of the routing zone can be carried out by a
   protocol that conveys the change in zone radius to the members of the
   routing zone.  The details of such an update protocol will be provided in
   a future version of this draft.

5.2 Hierarchical Routing and the ZRP

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

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

Haas, Pearlman                Expires December 1999                  [Page
53]

INTERNET DRAFT              The performance of the Zone Routing Protocol is determined by                June
1999

   For small to moderately sized networks, flat routing protocols, like the
   ZRP, are preferable to hierarchical routing zone radius. protocols.  In general, dense networks consisting order for
   a node to be located, its address needs to reflect the node's location
   within the network hierarchy (ie.  {cluster id,node id}).  Because of
   node mobility, a few
   fast moving 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 favor smaller 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 routing zones.  On protocols, such
   as the other hand, Zone-Based Hiearchical Link-State (ZHLS) [5], avoid these problems
   by distributing routing information to all cluster nodes, rather than
   maintaining a
   sparse 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 many slowly moving nodes operates route update messages is also more efficiently
   with
   scalable.  To some extent, the reduction in routing traffic is offset
   by extra mobility management overhead (i.e. identifying which cluster
   a larger zone radius.

   The simplest approach node belongs to).  However, it is quite common that the environment or
   existing organizational structure causes nodes to configuring naturally cluster
   together.  In these cases, there may be high degree of intra-cluster
   mobility, 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 zone radius protocol that computes routes between clusters.  Likewise,
   the intra-cluster component is to
   make a flat routing protocol, that computes
routes
   between nodes in each cluster.  For example, the assignment once, prior Near Term Digital Radio
   (NTDR) System [12] and ZHLS both employ proactive link state protocols to deploying
   determine inter and intracluster connectivity.

   In place of traditional proactive or reactive protocols, we recommend
   that the network.  This can intra-cluster and inter-cluster routing protocol components
   be performed by implemented based on the network administration, if one exists, or by hybrid proactive/reactive ZRP.  As described
   throughout this draft, the manufacturer, as a default value.  This may ZRP is designed to provide acceptable
   performance, especially in situations where network characteristics
   do not vary greatly over space an optimal balance
   between purely proactive and time.  Alternatively, 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
   adpat
   be applied to changes in network behavior, through dynamnic configuration
   of the zone radius [Haas-3].  In [Haas-4], it was shown that
   a related mobility management protocols, which determine
   complete node can accurately estimate its optimal zone radius, on-line, addresses 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 node's location in zone radius to the members of the routing zone. network
hierarchy.

Haas, Pearlman                Expires December 1999                  [Page
54]

INTERNET DRAFT              The
   details of such an update protocol will be provided in a future
   version of this draft. Zone Routing Protocol                June
1999

6.0 References

   [AODV]     Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing",
              MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA,
              November 3, 1997

   [Haas-1]

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

   [Haas-2]

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

   [Haas-3]

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

   [Haas-4]

   [4]   Haas, Z.J. and Pearlman, M.R., "Determining the Optimal
              Configuration for the Zone Routing Protocol", submitted Protocol," 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 for journal publication.

   [Johnson] Mobile Ad-Hoc Networks," to appear
              in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.

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

   [Murthy]

   [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", Networks," MONET, vol. 1,
              no. 2, pp. 183-197, October 1996.

   [Park]

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

   [Perkins]

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

   [TORA]     Macker, J., "Mobile Ad Hoc Internetworking", MILCOM'97
              panel on Ad-Hoc Networks,

   [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, November 3,
              Nov. 1997.

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

   [RFC-1075]

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

   [RFC-2178] Moy, J., "OSPF Version 2",

Haas, Pearlman                Expires December 1999                  [Page
55]

INTERNET DRAFT STANDARD,
              RFC 2178, July 1997.              The Zone Routing Protocol                June
1999

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@acm.org or haas@ee.cornell.edu

   Marc R. Pearlman
   319
   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]