INTERNET-DRAFT                       Zygmunt J. Haas, Cornell University
				    Marc R. Pearlman, Cornell University
Expires in six months                                      November 1997                                        August 1998

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

Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-
   Drafts Internet-Drafts as reference
   material or to cite them other than as ``work in progress.''

   To view the entire list of current Internet-Drafts, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).

   Distribution of this memo is unlimited.

Abstract

   This document describes the Zone Routing Protocol (ZRP), a hybrid
   routing protocol for ad hoc networks.
   In particular, it is suitable for highly versatile networks,
   characterized by large range a wide variety of nodal mobilities and mobile ad-hoc
   networks, especially those with large network
   diameters. The protocol is a hybrid of a proactive spans and diverse
   mobility patterns.  Each node proactively maintains routes within a reactive
   schemes, allowing adjustment of its operation
   local region (referred to as the current
   network operational conditions.

1. Introduction

   One routing zone).  Knowledge of the major challenges in designing a
   routing protocol for the
   ad hoc networks stems from zone topology is leveraged by the fact that, on one hand, ZRP to determine
   a packet route, at least improve the reachability information
   efficiency of a reactive route query/reply mechanism.  The proactive
   maintenance of routing zones also helps improve the source
   neighbors needs to be known quality of
   discovered routes, by making them more robust to the source node. On the other hand, changes in an ad hoc network, the network topology
   topology. The ZRP can change quite often.
   Furthermore, as be configured for a particular network by
   proper selection of a single parameter, the number routing zone radius.

   This version of network nodes can be large, the
   potential ZRP internet draft describes a number of destinations is also large, requiring large and
   frequent exchange of data (e.g., routes, routes updates, or routing
   tables) among
   features which have been added to the network nodes. Thus, protocol.  The distance-vector
   based IARP algorithm has been enchanced to prevent the amount of update traffic
   can be quite high. This 'counting
   to infinity problem'.  Route caching is in contradiction with now supported by the fact that all
   updates IERP
   route discovery process.  By allowing discovered route information
   to be distributed in a wirelessly interconnected ad hoc network travel over
   the air and, thus, are costly caches, route accumulation in resources.

   In general, the existing routing protocols IERP query/
   reply packets can be classified either
   as proactive or as reactive. Proactive protocols attempt to
   continuously evaluate avoided, thereby reducing the routes within amount of
   route discovery traffic, and improving the network, so that when
   a packet needs query response time.
   Two additional (optional) stages have also been added to be forwarded, the route is already known
   discovery process, to support the acquisition and can
   be immediately used. The family of Distance-Vector protocols is an
   example optimization 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
   source routes.

				Contents

   Status of global search procedure is
   employed. The family this Memo . . . . . . . . . . . . . . . . . . . . . .  i

   Abstract  . . . . . . . . . . . . . . . . . . . . . . . . . . .  i

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . .  2

   2.  Overview of classical flooding algorithms belong to the
   reactive group. Some examples Zone Routing Protocol . . . . . . . . . . .  3
       2.1  The Notion of reactive (also called on-demand)
   ad hoc network routing protocols are [Johnson] a Routing Zone and [TORA].
	      the Intrazone Routing Protocol (IARP)  . . . . . . .  3

       2.2  The advantage 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
	    A.  Packet Format  . . . . . . . . . . . . . . . . . .  9
	    B.  Structures . . . . . . . . . . . . . . . . . . . . 10
	    C.  Interfaces . . . . . . . . . . . . . . . . . . . . 10
	    D.  State Machine  . . . . . . . . . . . . . . . . . . 11
	    E.  Pseudocode Implementation  . . . . . . . . . . . . 13

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

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

   5.  Other Considerations  . . . . . . . . . . . . . . . . . . . 37
       5.1  Sizing the Routing Zone  . . . . . . . . . . . . . . . 37

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

1. Introduction

   One of the proactive schemes is that, once major challenges in designing a route is
   needed, there is little delay until the route is determined. In
   reactive protocols, because route information may not be available
   at routing protocol for the time a datagram is received,
   ad hoc networks stems from the delay fact that, on one hand, to determine
   a route packet route, a node needs to known at least the reachability
   information to its neighbors.  On the other hand, in an ad hoc
   network, the network topology can be change quite significant. often.  Furthermore,
   as the global search procedure number of network nodes can be large, the reactive protocols requires significant control traffic.
   Because potential number of this long delay
   destinations is also large, requiring large and excessive control traffic, pure
   reactive frequent exchange of
   data (e.g., routes, routes updates, or routing protocols may not tables) among the
   network nodes. Thus, the amount of update traffic can be applicable to real-time
   communication. However, pure proactive schemes are likewise not
   appropriate for quite high.
   This is in contradiction with the fact that all updates in a
   wirelessly interconnected ad hoc networking environment, as they
   continuously use a large portion of the network capacity to keep travel over the
   routing information current. Since nodes air and,
   thus, are costly in an ad hoc networks move
   quite fast, and resources.

   In general, the existing routing protocols can be classified either
   as proactive or as reactive. Proactive protocols attempt to
   continuously evaluate the changes may routes within the network, so that when
   a packet needs to be more frequent than forwarded, the route
   requests, most is already known and can
   be immediately used.  The family of this routing information Distance-Vector protocols is never even used! This
   results again in an excessive waste
   example of the wireless network
   capacity. What is needed is a protocol that, proactive scheme.  Reactive protocols, on one hand, initiates the route-determination other
   hand, invoke a route determination procedure on-demand, but at limited on demand only. Thus,
   when a route is needed, some sort of global search
   cost. procedure is
   employed. The presented-here protocol, family of classical flooding algorithms belong to the
   reactive group. Some examples of reactive (also called on-demand)
   ad hoc network routing protocols are [Johnson], [AODV], [TORA]
   (see also [Park]).

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

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

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

2.0

2. Overview of the Zone Routing Protocol

2.1 The Notion of a Routing Zone, Zone Radius, and Bordercasting the Intrazone Routing Protocol
    (IARP)

   A routing zone is defined for each node X, and includes the nodes
   whose minimum distance in *hops* from the node in question 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 |------+---+-----+---+ |--/   +---+     +---+   |
   | G |-----| D | |--/  +---+                | E |   |  Zone of node A
   +---+  |  +---+       |        +---+-----+---+        +---+     +---+   |  of radius=2
          |            +---+------|            +---+   ---| B | |-------|     |
          |            | A | |--/   +---+             |
          |            +---+                        |
          +-----------------------------------------+

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

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

   Bordercasting is a process of sending an IP datagram ([RFC-0791]) by

   An important consequence of the routing zone construction is the
   ability of a node to all deliver a packet to its peripheral nodes.
   This service, which we refer to as bordercasting, allows for more
   efficient network-wide searching than simple neighbor broadcasting.
   Bordercasting can could be implemented either through regular a series of IP unicast
   unicasts or through an IP multicast (Distance Vector Multicast Routing
   Protocol [RFC-1075]). Of course, [RFC-1075])) to the peripheral nodes.  (In cases where
   multicasting is supported, the multicasting approach is preferred
   to reduce the amount of traffic over the air.

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

   The air.)  However, as will be
   explained later, efficient ZRP is based on two procedures: operation requires that these unicast
   or multicast services be provided by the IntrAzone Routing Protocol
   (IARP) and ZRP, with IP providing best-
   effort delivery to the IntErzone specified ZRP next hops.

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

   Note that as a node's routing zone.

   Because each node needs to learn the distances to proactively acquire route information
   only for the nodes within its zone only, zone, the nodes are updated about topological
   changes only within their routing zone. Consequently, in spite total amount of IARP traffic
   does not depend on the size of the fact that a network can network, which may be quite large, the updates are only
   locally propagated. large

2.2 The Interzone Routing Protocol (IERP)

   While the IARP finds maintains routes within a zone, IERP the IERP* is
   responsible for finding routes between nodes located at distances
   larger than the zone radius.  The IERP relies on bordercasting. Bordercasting is possible
   as any node knows the identity and the distance to all distinguished from standard
   flood-search query/response  protocols by exploiting the nodes in
   its routing zone by the virtue of the IARP protocol.

   The IERP operates as follows: The source
   topology.  A node first checks whether
   the destination is within able to respond positively to any queries for
   its routing zone nodes.  For large networks, relatively few
   destinations lie within any particular node's routing zone.  In this
   more likely case, the node can efficiently continue the propagation
   of the query, through the routing zone-based bordercast delivery
   mechanism.

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

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

   The node A has a datagram to send to node L. Assume a uniform
   routing zone radius of
   2. 2 hops.  Since L is not in A's routing zone
   (which includes B,C,D,E,F,G), A bordercast bordercasts a routing request query to its
   peripheral nodes: D,F,E, and G. Each one of these peripheral nodes
   check whether L exists in their routing zones. Since L is not found
   in any routing zones of these nodes, the nodes bordercast the request
   to their peripheral nodes. In particular, G bordercasts to K, which
   realizes that L is in its routing zone and returns the requested
   route (L-K-G-A) to the query  source, namely A.

2.3

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

2.2.2 Route Accumulation procedure Procedure

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

   In the basic Route Accumulation, a node that forwards appends its IP address to a
   received query writing into
   the query packet its identification. packet.  The sequence of these
   identifications represents IP addresses specifies a path
   route from the query's source node to the current node, and, by node.  By reversing the order, this
   sequence, a path from the current
   node to the source node.

2.4 Terminating the IERP flood

   It is desirable for route requests may also be obtained back to propagate away from the source
   and not source.  In this
   way, Y may send a reply back to loop-back into S, through strict source routing.

   Given sufficient storage space, a previously queried node may cache routing zone. To
   encourage this directed spread of route requests, IERP employs two
   loop-back prevention mechanisms. The first mechansim terminates
   threads which loop-back on themselves. Such threads are terminated
   when the
   information accumulated route (excluding in the previous hop) contains a
   host which lies within its routing zone. A separate mechanism, based
   on packet eavesdropping, is employed query packet, allowing the information
   to reduce be remove from the packet.  This has the overlapping benefit of
   parallel threads. When a host receives a route request, reducing the IERP
   records
   length of the request ID in its Processed Request List.* If a node
   "officially" receives a request that has been previously recorded, query packet, thereby decreasing the new copy is discarded. Without these measures, query traffic and
   query response time.  The IP addresses that remain in the bordercast
   transmission packet can actually generate more overhead than flooding.

   * ICMP provides a service similar
   be used to IERP's form a loose source route failure
     notification. However, the IERP service provides additional
     diagnostic information, allowing back to the query's source to respond to (If
   ALL nodes have cached the accumulated route failure more effectively.

2.5 Route failures notifications

   The IERP also provides a mechanism information, then this
   effectively becomes next hop routing.  If no nodes have cached
   accumulated route information, then this defaults to reactively respond the basic case
   previously discussed).  The same caching strategy can be applied to route
   failures. A route failure is detected by
   the IP when reply packet on its way back to the next hop in source.  In this case, a
   loose source route to the destination is determined formed.

2.2.3 Query Control Mechanisms

   Bordercasting has the potential to support global querying schemes
   that are more efficient than flooding.  To achieve this efficiency,
   the protocol should be unreachable (i.e., does not
   appear able to detect and terminate a query thread
   when it appears in the Intrazone Routing Table). Upon detection of a route
   failure, previously queried region of the IERP is alerted, and network (i.e.
   arrives at a route failure packet is
   generated.** The route failure packet propagates back node belonging to the route's
   source in the same manner as routing zone of a route reply. When 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 route's source
   receives notification of ZRP, the route failure, nodes that relay
   the expired route is
   removed from its Interzone Routing Table. The IERP may also be
   configured query to locally repair the damaged Interzone route by
   initiating a route discovery peripheral node are able to detect the unreachable next hop.

   ** Eavesdropping passing
   query.  If the underlying IP delivery is (neighbor) broadcast or
   if IP is operating in promiscuous mode, then nodes that overhear
   a query transmission are only permitted to listen also able to route requests
      (and record them in their Processed Request List); they are
      prohibited from processing detect the request any further.

2.6 Bordercast Resolution Protocol (BRP)

   The Bordercast Resolution Protocol (BRP) is included with query, further
   strengthening the IERP Query Detection (QD) mechanism.  Upon detecting
   a query, the identifying query parameters (i.e. query source,
   query ID)  are recorded in
   order a Detected Queries Table, to provide bordercasting services which do not exist in IP. In
   the current version a
   basis for termination of the BRP, the content future threads of that query.

   A node can consider a bordercast message
   is considered query to be accessible 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 by
   the peripheral node (bordercast destination).  This could result in
   wasted transmissions as a query penetrates into a previously queried
   region.  Implementing bordercasting in the ZRP allows the protocol to any host which receives
   provide an Early Termination (ET), as the
   message.***  Future versions of redundant query enters the BRP
   previously queried region.

2.2.4 Route Maintenance

   In addition to initially discovering routes, the IERP may allow also assume
   responsibility for semi-private
   bordercasting, where bordercast messages are only delivered to monitoring the
   higher layers integrity of these routes and
   repairing failed routes as appropriate.

   Route failures can be detected either proactively or reactively.
   Proactive route failure detection is triggered by the bordercast destinations (peripheral nodes).

   *** When the BRP delivers the message IARP, in
   response to the next higher layer, a
       flag is set to indicate whether node leaving the packet was overheard or
       received at its intended destination. Note that routing zone.  Any IERP routes

   containing this node as the first hop can be considered invalid.
   Route failures may also be detected reactively, by IP, when the next
   hop in a datagram's source route is determined to be unreachable
   (i.e. does not
       restrict access appear in the (Intrazone) Routing Table).

   Upon detection of a route failure, a node may choose to notify
   the route's source of the failure and / or attempt to repair the
   route.  A route failure notification consists of a transmission
   back to the message; query source, indicating that the source route has
   failed, and possibly the hop at which it only serves failed.  This type of
   service is provided by protocols like ICMP.  The node that detects
   the route failure may also try to provide repair the
       access control status failed connection by
   discovering a route to bypass the failed connection.  The repair
   discovery process is nearly identical to an initial route discovery.
   Route repairs should not be substantially longer than the original
   failed connection.  Thus, the depth of a repair query can be limited,
   through the use of hop counter.  This has the advantage of producing
   much less query traffic than an unrestricted initial route query.
   After a successful repair, the route's source MAY be notified so that
   routes are properly selected for use.  Alternatively, the repair
   could go unreported without compromising the message. connectivity between
   source and destination.

3.0 The ZRP Architecture

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

Legend:

	A<--->B

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

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

	ZRP Entities
	------------
		IARP		IntrAzone Routing Protocol
		IERP		IntErzone Routing Protocol
		BRP		Bordercast Resolution Protocol
                                           (component of IERP)

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

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

4.0

4. Implementation Details

4.1 The IntrAzone Routing Protocol (IARP)

   Although the

   The IARP can be implemented through various proactive
   protocols, we protocols. We
   present here an example of an implementation based on a modified version a modified version of the
   Distance Vector algorithm.  Routing information to a node is limited
   to the the routing zone of that node.  In this version, routing
   information consists of the route cost and the IP addresses of the
   route destination and next two hops to the destination. The second hop
   is included to identify routes where a node is it's own second hop.
   This particular looping condition can result in the "counting to
   infinity" problem.  By deleting these routes, this problem can be
   avoided, allowing the IARP to converge faster.

   A node may receive new route information either from a received IARP
   packet or from an interrupt generated by its Neighbor Discovery /
   Maintenance (NDM) proces*. In the special case when a host has
   discovered a neighor, the IARP is responsible for sending to the new
   neighbor 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). The node then records the new route information
   in its Intrazone Routing Table.  If the shortest path to the host has
   changed, the terminal broadcasts an IARP packet reflecting the
   change.

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

   A.  Packet Format
                    1	                2	            3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Destination Address                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Next Hop #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 the "next hop" host to the destination host
	* Next Hop # 2 Address	(32 bits)
	    IP address of the Next Hop #1 's "next hop" host to
            the destination host
	* Hop Count		(4 bits)
	    Length of the route to the destination host, measured
            in hops

   B.  Structures

       B.1  Intrazone Routing Table

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

   C.  Interfaces

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

   D.  State Machine

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

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

	D.1
	    Event:   An IARP packet is received containing route
                     information to a destination D. The hop count
                     associated with the received route is LESS THAN
                     OR EQUAL TO the routing zone radius.  The
		     second next-hop is EQUAL to X.

	    Action:  NONE

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

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

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

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

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

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

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

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

	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
                     Intrazone Routing Table.
		        1) If the Intrazone Routing Table still
                        contains a route to N and the length of the
                        shortest route has increased due to the route
                        removal, then the an IARP packet containing the
                        shortest route to N through X is broadcasted.
		        2) If the Intrazone Routing Table contains no
                        more routes to N, then an IARP packet containing
                        a route to D through X with hop count of INF is
                        broadcast. A "Host Lost" interrupt is generated
                        to alert the IERP that D has moved beyond the
                        routing zone.

    E.  Pseudocode Implementation

	E.1  Update Intrazone Routing Table

    	    if (packet arrived)
	      {host, route->next_hop, 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 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 IERP acquires routing information reactively, exploiting
   the knowledge of the routing zone topology through the bordercasting
   delivery service.

   This version of the IERP extends the basic query / reply mechanism
   described in Section 3.  In the basic protocol, queries are
   terminated before reaching the query destination.  This provides
   a faster response to the route query than if the destination, D,
   were to respond directly.  However, because D never receives the
   query, it does not acquire a route back to the source, S.  If the
   D needs to send data back to S (which is often the case, given the
   bi-directional nature of many applications), a separate route query
   from D to S would have to be initiated.  This substantial overhead
   is avoided by having the query forwarded to D, by the node Y that
   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 mechanisms (to be discussed
   later).  Distributing route information in the caches of the
   route's nodes can significantly reduce the size of the IERP packets
   and provide for a 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 information be
   accumulated in the IERP packets, rather than cached.  This IERP
   implementation satisfies the demands for rapid query response
   and source routing support by two stages of route reporting.  In the
   first two stages, route information is cached by the route's nodes
   (when possible).  Next-hop route are quickly returned to the source
   in QUERY-REPLY packets and forwarded to the destination in QUERY-
   EXTENSION packets.  At this point, bi-directional connectivity is
   established.  In 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 Distance Vector algorithm that restricts
   the ROUTE-ACCUMULATION stage can be eliminated.
   Also, if all of the algorithm's operation route's nodes elect not to the range of cache the routing zone
   radius.

   A terminal may receive new route
   information either from a received
   IARP packet or from an interrupt generated by its Neighbor Discovery
   / Maintenance (NDM) process$. In (perhaps due to storage limitations), then the special case when a host has
   discovered QUERY
   REPLY and QUERY-EXTENSION packets essentially serve the role of
   ROUTE-ACCUMULATION packets, obviating the need for a neighoor, separate
   ROUTE-ACCUMULATION stage.

   Because each node proactively maintains the IARP local topology of its
   routing zone, it is responsible not necessary for sending the new
   neighbor the shortest a source route to each host which is common to both of
   their routing zones. The terminal then records specify
   every hop along the new route
   information in its Intrazone Routing Table. If (i.e. strict source routing).  A properly
   chosen subset of the shortest path complete source route can be used to specify
   the host has changed, the terminal broadcasts an IARP packet
   reflecting route to the change.

   $ IARP relies on destination, and where desirable, the services of a separate protocol (referred reverse route
   back to
     here as the Neighbor Discovery/Maintenance Protocol) to provide
     current information about source.  The IERP supports such an optimization through
   a host's neighbors. At final ROUTE-OPTIMIZATION stage.  The details of the least, this
     information must include route
   optimization are described in the IP addresses BRP specification.  Upon
   completion of all the neighbors.
     The IARP can ROUTE-OPTIMIZATION stage, sufficient routing zone
   membership is acquired for each node in the route so that the source
   route may be readily configured to support supplemental
     neighbor information, such as link cost. reduced (by translating this route reduction into
   an appropriate set covering problem, and employing a suitable
   heuristic).

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

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

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

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

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

              Sequence of the IERP Route Discovery Stages
   A.  Packet Format
                    1	                2	            3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type  | Rsvd  |   Hops Left   |         Query ID              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                   Bad Link Source Address  (repair only)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                       Next IERP Address                       |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  BRP
|                       Next BRP Address                        | fields
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|                       Prev IERP Address                       |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                       Hop 0 Address (Source)                  |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|                       Hop 1 Address  		                |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
                                | |                                 |
                                | |                                 |
                               \| |/                              route
				\ /				    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|   |
|                      Hop (N-2) Address                        |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|                      Hop (N-1) Address (Destination)          |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                      Flags   (optional)                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	Field Description:

        * Type                        (4 bits)
		Identifies the type of IERP packet.  The current version
                 of IERP contains five packet types:

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

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

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

                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 information cached
			at the route's nodes is accumulated in this
			packet, providing a complete source route at
			the destination 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 of each node in the source
			route.

        * Query ID            	      (16 bits)
		Sequence number which, along with the Source Address                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Next Hop
		(see below) uniquely identifies any route query in the
                network.

        * Hops Left                   (8 bits)
                Number of hops that a route query may continue to
                propagate. This field allows a querying node to
                configure the depth of a route search, to
                control the amount of IERP traffic generated.

        * Bad Link Address                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Hop Cnt|
+-+-+-+-+
	Field Description:            (32 bits)
                Used during route repairs.  Contains the IP Address
                corresponding to the source of routes failed link.

        * Destination Next IERP Address           (32 bits)
                IP address of the destination host next IERP recipient

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

        * Hop Count		(4 Prev IERP Address           (32 bits)
	Length
                IP address of the route to 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 host, measured
                        - in hops 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.

    B.  Structures

	B.1	Intrazone Routing Table

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ (See IARP Description)

	B.2	Interzone Routing Table

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         |    	       Routes       		|
    +  Dest   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Host         |     0     |     1     | ==> |    M-1    |
|           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         |  Next :  Hop           |  Next :  Hop           | ==> | Next  :  Hop  |
|           |  Hop  : Count |  Hop  : Count |     | Hop   : Count |
+-+-+-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-+-+-+-:-+-+-+-+
    |---------|-----------|-----------|-----|-----------|
    |         |       :           |       :           | ==> |       :           |
|-----------|-------:-------|-------:-------|-----|-------:-------|
    |---------|-----------|-----------|-----|-----------|
    |         |       :    |       : |    |       :           |
|-----------|-------:-------|-------:-------|-----|-------:-------| ==> |           |       :
    +-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		   |       : |
		  \   /
		   \ /
		+-+-+-+-+   +-+-+-+-+          +-+-+-+-+
		|       :   0   |==>|   1   |==> ...==>|  N-1  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+	source
		+-+-+-+-+   +-+-+-+-+          +-+-+-+-+        route
		  source      first		 (N-1)
		   host        hop	          hop
    C.  Interfaces

	C.1  Higher Layer (N/A)
	C.2  Lower Layer (IP)
	    C.1.1 (BRP)
            C.2.1   Send()	(specified in IP standard)
	    C.1.2  Deliver()	(specified in      (same interface as IP standard)
	C.3  NDM
	    C.3.1  Neighbor_Lost(host) send())
                Used by the NDM IERP to notify the IARP that direct contact
                has been lost with "host".
	    C.3.2  Neighbor_Found(host) request transmission of an
                IERP packet.
	    C.2.2  Deliver()	(same interface as IP deliver())
		Used by the NDM BRP to notify alert the IARP that direct contact
                has been confirmed with "host".
	C.4 IERP
	    C.4.1  Host_Lost(host)  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 host no longer
                exists within node has left
                the routing zone. zone
	C.4  ICMP
            C.4.1  Host_Unreachable()    (specified in ICMP standard)
	    C.4.2  Source_Route_Failed() (specified in ICMP standard)

    D.  State Machine

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

	Notes:

	Note:  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   A "Zone_Node_Lost" interrupt is received containing route
                     information to a destination D. The hop count
                     associated with received,
		     indicating that the received route is LESS THAN node H has moved beyond the
		     routing zone radius. zone.

	    Action:  The received  Remove every route is recorded in from the Intrazone Interzone Routing Table. Table
                     which contains H.  If the received route is shorter
                     than the previous shortest route to D, any routes containing H are
		     found, then a new
                     IARP packet containing route information repair (limited depth route
		     discovery) to D
                     through X H is broadcasted. initiated.
	D.2
            Event:   An IARP packet   A "Host_Unreachable" interrupt is received containing route
                     information to a from the
                     ICMP, indicating an unknown destination host D.

            Action:  A full depth route discovery to D is initiated.
                     The hop count query_id is
                     EQUAL TO the routing zone radius.

	    Action: incremented and assigned to a new
                     QUERY packet.  The received route is recorded in initialized with the Intrazone
                     Routing Table.
                     IP addresses of the route's source and destination
                     IP addresses (X and D).  Finally, the QUERY packet
                     is bordercasted.

	D.3
            Event:   An IARP packet   A "Source_Route_Failed" or "Proactive_Repair"
                     interrupt is received containing received, indicating that the next
		     hop, H, specified in a source route
                     information does not
		     appear within the routing zone.

            Action:  A limited depth route discovery to a destination D. H is initiated.
                     The hop count query_id is
                     equal incremented and assigned to INF.

	    Action: a new
                     QUERY packet.  The route to D is removed from initialized with the Intrazone
                     Routing Table.
		        1) If
                     valid portion of the Intrazone Routing Table still
                        contains a route to D failed route, and the length of the
                        shortest route has increased due
		     bad link address field is set with X's IP address,
		     to indicate the location of the route
                        removal, then failure.
		     Finally, the an IARP QUERY packet containing the
                        shortest route to D through X is broadcasted.
		        2) If the Intrazone Routing Table contains no
                        more routes to D, then an IARP bordercasted.
	D.4
            Event:   A QUERY packet containing
                        a route to D through X with hop count of INF is
                        broadcast. received with a  destination that
                     appears within X's routing zone.

            Action:  A "Host Lost" interrupt QUERY-REPLY is
                        generated sent back to alert the IERP that D has moved
                        beyond query source, and
                     a QUERY-EXTENSION is sent to the routing zone.

	D.4 query destination.

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

	    Action:  For each destination in that
                     DOES NOT appear within X's Intrazone Routing
                     Table, an IARP routing zone.

            Action:  The QUERY packet is bordercasted.

	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 QUERY-REPLY packet is sent to N containing the
                     best route received.

            Action:  The packet contents are moved to that destination. An IARP a ROUTE-
		     ACCUMULATION packet.  The ROUTE-ACCUMULATION
		     packet is
                     then broadcasted containing the 1 hop route sent to N
                     through X.

	D.5 the query destination.

        D.8
            Event:   A "Neighbor Lost" interrupt ROUTE-ACCUMULATION packet is received, indicating
                     that host N received.  X is no longer a neighbor not
                     the final destination of this packet
                     (i.e. X != IERP_next).  This only occurs when the
                     accumulated route contains a repair

            Action:  The one hop route to N bad link is removed from replaced by the
                     Intrazone path repair in the
                     Interzone Routing Table.
		        1) If

        D.9
            Event:   A ROUTE-ACCUMULATION packet is received. X is
                     either the Intrazone Routing Table still
                        contains a route to N and the length of the
                        shortest source or (route destination).

            Action:  The (reversed) accumulated route has increased due is added to the
                     Interzone Routing Table or replaces a failed route
                        removal, then
		     if the an IARP packet containing the
                        shortest route to N through specifies a bad link.  In addition,
                     if X is broadcasted.
		        2) If the Intrazone Routing Table contains no
                        more routes to N, then an IARP ROUTE-ACCUMULATION destination, the
                     packet containing
                        a route contents may be moved to D through X with hop count of INF is
                        broadcast. A "Host Lost" interrupt a ROUTE-
		     OPTIMIZATION packet, which is generated then sent to alert
		     the IERP query destination (query source).

        D.10
            Event:   A ROUTE-OPTIMIZATION packet is received.

            Action:  The routing zone membership information that D has moved beyond is
                     collected in the
                        routing zone. 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, 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 of the IERP packet.

        E.1  Update Intrazone 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 (packet arrived)
	      {host, route->next_hop,route->hop_count} <-- packet (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)
            {
	      {host}
                bad_link = my_id + lost_host
                force_intrpt("IERP","Proactive_Repair", bad_link)
            }

	E.2  Initiate Route Discovery

            {route} <-- intrpt
	      route->next_hop=host

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

            route = prev_hops + my_id + dest
            if (type(intrpt) == "Neighbor Found") "Proactive_Repair" ||
                type(intrpt) == "Source_Route_Failed")
            {
	        for recorded_host
                hops_left        = each host in Intrazone_Routing_Table MAX_REPAIR_HOPS
                bad_link_source  = my_id
            }
            else
            {
		  best_route
                hops_left        = MAX_FULL_QUERY_HOPS
                bad_link_source  = NULL
            }
            query_id ++
            load (packet)
            send (packet, BORDERCAST)
        E.3  Receive IERP Packet

            extract(packet)
            source=route(0)
            dest = Intrazone_Routing_Table[recorded_host,0] route(length(route)-1)
            switch(pk_type)
            {
                case:  QUERY
                    if (best_route->hop_count <  ROUTING_ZONE_RADIUS) (dest (EXISTS IN) Intrazone_Routing_Table)
                    {
		    packet <-- {recorded_host,my_id,hop_count+1}
		    send(packet,host)
		  }
	        }
	        route->hop_count=1
	      }
                        type = QUERY-REPLY
                        if(bad_link_source)
                            IERP_next = bad_link_source
                        else
	        route->hop_count=INF
                            IERP_next = source
                        load(packet)
                        send(packet)

                        type = QUERY-EXTENSION
                        IERP_next = dest
                        load(packet)
                        send(packet)
                    }
            former_best_route
                    else
                        bordercast(packet)
              break
              case:  QUERY-EXTENSION
                    type = Intrazone_Routing_Table[host,0] 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 (route->hop_count < INF)
	      add(Intrazone_Routing_Table[host], route)
            else
	      remove(Intrazone_Routing_Table[host],route)
            best_route (bad_link_source)
                {
                  path_source_ptr = Intrazone_Routing_Table[host,0] get_index(route, bad_link_source)
                  path_dest_ptr   = get_index(route, dest)
                  if (best_route != NULL) (IERP_next == source)
                  {
                     bad_link     = bad_link_source + dest
                     path_repair  = route(path_source_ptr:path_dest_ptr)
                  }
                  if (best_route->hop_count != former_best_route->hop_count
		    && best_route->hop_count < ROUTING_ZONE_RADIUS) (IERP_next  == dest)
                  {
	        packet <-- {host, my_id, best_route->hop_count+1}
	        broadcast(packet)
                     bad_link     = dest + bad_link_source
                     path_repair  = reverse(route(path_source_ptr :
                                                    path_dest_ptr))
                  }
                  replace(Interzone_Routing_Table, bad_link,path_repair)
                }
                else
                {
	      force_intrpt("IERP","Host Lost",{host})
 	      packet <-- {host, my_id, INF}
	      broadcast(packet)
                  if (my_id == source)
                    add(Interzone_Routing_Table, route)
                  if (my_id == dest)
                    add(Interzone_Routing_Table, reverse(route))
                }

4.2 IntErzone Routing

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

4.3 Bordercast Resolution Protocol (IERP) (BRP)

   The Interzone Routing Protocol (IERP) BRP is responsible for discovering
   routes to hosts which are beyond a terminal's routing zone. The sublayer of the IERP
   collects that performs the operations of
   bordercasting, query control, route accumulation and routing information reactively, through bordercasted queries zone
   labelling, which contain the accumulated routes from form the source.

   When IP receives a data packet intended basis for an unknown destination
   (i.e., destination is not recorded in either the Intrazone or
   Interzone Routing Tables), the IERP is interrupted. The IERP responds
   by initiating a route discovery and procedure.

   In this BRP implementation, bordercasting is implemented as a route query. Each
   query in series
   of unicasted messages to the network peripheral nodes.  The BRP is uniquely identified by able to
   identify the IP address of peripheral based on the
   source and a request ID (local to information contained in the source).

   Upon receipt of a route request packet, a host searches its
   Intrazone Routing Table Table.  Rather than unicasting to determine if the requested destination is within its
   routing zone. If so, peripheral
   node directly through IP, the terminal responds with a route reply which
   is returned bordercasted packets are relayed to
   the source along the (reversed) accumulated route. If peripheral nodes by the destination BRP layer.  IP is not within used only to send
   these messages one hop toward the terminal's routing zone, peripheral nodes.  This allows the
   terminal adds its terminal ID
   BRP to detect all QUERY packets that are received by that node.

   To efficiently terminate the accumulated route and
   bordercasts the route request.

   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  |    Request ID     | Last Hop  | Hop Mrker | Max Hops  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Destination Address                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                    Hop 0 Address (Source)                     |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|                       Hop 1 Address  		                |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
				| |				    |
			        | |				  source
			       \   /				  route
				\ /				    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|   |
|                      Hop (N-1) Address                        |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--

	Field Description:

	* Type			(4 bits)
		Identifies query, the type of IERP packet.  The current version
                 of IERP contains three packet types:
			REQUEST:  request an Interzone source route BRP needs to
                                  the destination host specified in
				  Destination Address
			REPLY:	  response record
   sufficient information from each detected query.  The query's source
   and ID, which serve to uniquely identify a request packet;						  includes query, are added to the source route
   Detected Queries Table.  In addition, the IP address of the last
   node to bordercast the
				  destination host specified query is also recorded in
				  Destination Address
			FAILURE:  control message sent a host indicating
				  that the Detected
   Queries table.  Any threads of this query that are later received data packet
   from a different bordercasting node are discarded.  Each query also
   contains
				  an invalid source route.

	* Request ID		(10 bits)
		Sequence number which, along with a hop counter that is decremented at each node.  When the Source Address
		(see below) uniquely identifies any route query in
   counter expires, the
		network. (used only for REQUEST packet is discarded.

   IERP packets (excluding ROUTE-OPTIMIZATION packets)

	* Last Hop		(6 bits)
		Indicates that are not
   terminated next undergo a  route accumulation procedure.  As
   described earlier, route accumulation is used to construct routes,
   by recording the previous recipient IP addresses of a route's nodes in the IERP packet
		(referenced
   or local cache.  The Detected Queries Table, extended by two
   columns, serves as an index into the Source Route (see
                below))

	* Hop Marker		(6 bits)
		Currently used to indicate the hop where a convenient route failure
		was detected (referenced as an index into accumulation cache.

   The node begins the Source
                Route (see below)) (used only for FAILURE packets)
	* Max Hops		(6 bits)
		Maximum number of Interzone hops which a route query may
		propagate. accumulation procedure by adding its IP
   address to the IERP route.  This field allows is followed by the IP addresses of
   any cached nodes leading to adaptively
                configure the depth packet's destination (the "next
   hops").  This is sufficient processing for ROUTE-ACCUMULATION
   packets, where complete source routes are constructed.  On the other
   hand, QUERY, QUERY-EXTENSION and QUERY-REPLY packets should carry as
   little of a the route search in order to
                control as possible.  Therefore, if cache space is
   available, the route accumulation process records the amount of IERP traffic generated. (used only
                for REQUEST packets)

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

	* Source Route 		(N*32 bits)
		Variable length field which contains "previous hops" from the packet's source, and removes them
   from the IP addresses of
		an N hop source route. IERP packet.

   The first subfield final role of the Source
		Route contains BRP is contribute to the IP address ROUTE-OPTIMIZATION
   process by indicating the mutual routing zone membership of the route's source.
		In general,
   nodes in the n-th subfield contains source route.  This is done by appending a special
   flag field to the IP address ROUTE-OPTIMIZATION packet.  The status of the n-th hop
   k-th bit in the route.
		For REQUEST packets, flag field indicates whether the Source Route represents k-th hop in the
		incomplete accumulated
   source route to is a member of the destination host
		(as indicated by node's routing zone.  This
   membership information is eventually processed at the Destination Address)
		For REPLY and FAILURE packets, source to
   determine the Source Route contains smallest set of routing zones that cover the complete route from
   (and therefore the source host smallest set of nodes needed to the
		destination host. specify this
   route through loose source routing.)
    A.  Packet Format

	See IERP packet format in Section 4.2

    B.  Structures

        B.1  Intrazone Routing Table (See    (see IARP Description) description)

        B.2	Interzone Routing  Detected Queries Table

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

    |--------------------|--------|-----------------------|
    |  Query   |    	       Routes  Query  |
    +  Dest   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  Prev  |    Prev   |	    0    Next   |	1
    | ==>  Source  |    M-|   Id    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  IERP  |   Hop(s)  |   Hop(s)  |
    |----------+---------|--------+-----------+-----------|
    | ==>          |         |
    |---------|-----------|-----------|-----|-----------|        |   |   |   | ==>   |   |
    |---------|-----------|-----------|-----|-----------|   |
    |----------+---------|--------+---+---+---|---+---+---|
    |          |         |        |   | ==>   |   |
    +-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   |
		  \   /
		   \ /
		+-+-+-+-+   +-+-+-+-+          +-+-+-+-+   |   0   |==>|   1   |==> ...==>|  N-1
    |----------+---------|--------+---+---+---|---+---+---|
    |          |	source
		+-+-+-+-+   +-+-+-+-+          +-+-+-+-+        route
		  source      first		 (N-1)
		   host        hop	          hop
	B.3	Processed Request List

	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+         |   Source        |   Request ID   |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   |   |
	|-----------|---------------|   |   |
    |--------------------|--------|-----------------------|
                                      |
	|-----------|---------------|
                                     \|/
                                   +---+   +---+       +---+
                                   | A |-->| B |-->... | C |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                   +---+   +---+       +---+
                                    cached "source" route
    C.  Interfaces

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

    D.  State Machine

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

	Note:

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

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

	    Action:  Remove every route from the Interzone Routing Table
                     which contains H. A limited depth route discovery
                     to H is initiated. An IERP request packet
	       2) NULL is
                     created with the destination addresss set a reserved field value, corresponding to H and
                     the source route initialized with the an
                  invalid IP address
                     of X.  The request packet is then bordercasted.

	D.2 address.

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

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

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

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

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

            Action:  The request  If X is recorded in the Processed Request
                     List. In order to be processed further, four
                     conditions must be satisfied. First, the received
                     packet must not be flagged as overheard. Second,
                     the number of hops in the route must not exceed the
                     maximum hop count.  Third, the request must not
                     have been  previously recorded. Finally, no hops in the route (except query's source, then the last_hop) may lie within X's
                     routing zone. identifying
                     querying information is recorded in the Detected
		     Queries Table. X appends adds its IP address to the route
                     and sends an IERP reply
		     packet's route.  A copy of the packet is sent to
                     the preceding hop
                     in IERP layer of each peripheral node, by way of
		     a BRP transmission to the route.

	D.5 next hop to that
		     peripheral node.
        D.2
            Event:   An IERP request   A QUERY packet is received with a
                     destination that DOES NOT appear within X's routing
                     zone. from the IP.  The hop
                     counter has expired or the query was already
                     detected from another bordercasting node.

            Action:  The request packet is recorded in discarded.

        D.3
            Event:   A QUERY packet is received from IP.  The hop count
                     has not expired and the Processed Request
                     List. In order to be processed further, four
		     conditions must be satisfied. First, query has not been
		     previously detected (or was detected from the received
		     packet must
		     same bordercasting node).  X is not be flagged as overheard.  Second, the number of hops
		     intended BRP recipient.

            Action:  If cache space is available, identifying query
                     information SHOULD be recorded in the route must not exceed Detected
		     Queries Table.  The packet is then discarded.

        D.4
            Event:   A QUERY packet is received from the
		     maximum IP.  The hop count. Third,
		     count has not expired and the request must query has not have been
		     previously recorded. Finally, no hops in the
		     route (except detected (or was previously detected
		     from the last_hop) may lie within X's
		     routing zone. same bordercasting node).  X appends its IP address to is the route
		     and
		     intended BRP recipient, but is bordercasts an IERP request packet
		     containing not the updated route.

	D.6
	    Event:   An intended
		     IERP reply packet is received containing X as recipient and the source host. query destination does
		     not lie within X's routing zone.

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

	D.7
	    Event:   An IERP reply packet decremented.  If cache space
                     is available, identifying query information and
                     accumulated route information should be recorded
                     in the Detected Queries Table.  The recorded route
                     information is received containing a node
                     other than removed from the packet and X as adds
		     its IP address to the source host.

	    Action: route.
                     The route reply packet is fowarded then sent to the preceding BRP of the next hop in
                     to the route

	D.8
	    Event:   An intended IERP failure recipient.

        D.5
            Event:   A QUERY packet is received containing X as
		     the source host.

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

	D.9
	    Event:   An IERP failure packet is received containing a
		     node other than
		     count has not expired and the query has not been
		     previously detected (or was previously detected
		     from the same bordercasting node).  X as is the source host.

	    Action:
		     intended BRP recipient, and either X fowards is the route reply packet to
		     intended IERP recipient, OR the preceding 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
                     in the Detected Queries Table.  The recorded route

    E.  Pseudocode Implementation

	E.1 Intrazone Node Lost

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

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

	E.3  Report Route Failure

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

	E.4  Receive IERP Packet

            {pk_type, req_id, last_hop, bad_hop, max_hops, route} <--
                                                                  packet
            {overheard} <-- intrpt
            switch(pk_type)
            {
	      case:  REQUEST
	        add({Processed_Request_List, source, req_id)
	        LSP1_terminate = FALSE
	        n=0
	        while (!LSP1_terminate && n < last_hop)
	        {
		  if (Intrazone_Routing_Table[route(n)]!=NULL)
		    LSP1_terminate = TRUE
		  n++
	        }
	        LSP2_terminate = (Processed_Request_List[source,req_id]
                                                                != NULL)
	        if (!overheard && !LSP1_terminate && !LSP2_terminate &&
		    last_hop < max_hops)
	        {
		  last_hop++
		  route(last_hop)=my_id
		  if (dest (EXISTS IN) Intrazone_Routing_Table)
		  {
		    packet<--{REPLY,req_id,last_hop,bad_hop,max_hops,
                                                             dest,route}
		    send(packet, route(last_hop-1))
		  }
		  else
		  {
		    packet<--{REQUEST,req_id,last_hop,bad_hop,max_hops,
                                                             dest,route}
		    bordercast(packet)
		  }
	        }
	        break
	      case:   REPLY
	      case:   FAILURE
	      if (route(0) == my_id)
	      {
	        if (pk_type == ROUTE_REPLY)
		  add(Interzone_Routing_Table, route)
	        else
		{
		  link(0)=route(bad_hop)
		  link(1)=route(bad_hop+1)
		  remove(Interzone_Routing_Table,link)
		}
	      }
	      else
	      {
	        last_hop --
                     information is removed from the packet <-- {pk_type,req_id,last_hop,bad_hop,max_hops,
                                                             dest,route}
		send(packet, route(last_hop-1))
	      }
            }

4.3 Bordercast Resolution Protocol (BRP) and X adds
		     its IP address to the route.
                     The higher 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 interface 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:  If cache space is designed to available, identifying query
                     information SHOULD be compatible
   with any IP based application. However, it recorded in the Detected
		     Queries Table.  The packet is assumed that then discarded.

        D.8
            Event:   A QUERY-EXTENSION packet is received from the
   routing zone hierarchy IP.
                     X is visible only the intended BRP recipient, but is not the
		     intended IERP recipient.

            Action:  If cache space is available, identifying query
                     information and accumulated route information
                     should be recorded in the Detected Queries Table.
		     The recorded route information is removed from the
		     packet and X adds its IP address to the ZRP entities, making
   bordercasting services only of use route.
                     The packet is then sent to the IERP.

   Upon receipt BRP of a (IERP) packet the next hop
                     to be bordercasted, the intended IERP recipient.

        D.9
            Event:   A QUERY-EXTENSION packet is received from the IP.
                     X is the intended BRP resolves recipient and the bordercast address into intended
                     IERP recipient.

            Action:  If cache space is available, identifying query
                     information and accumulated route information
                     should be recorded in the Detected Queries Table.
                     The recorded route information is removed from the individual
                     packet and X adds its IP addresses of address to the
   peripheral nodes. route.
                     The received packet is then encapsulated into a BRP delivered up to the IERP.

        D.10
            Event:   A QUERY-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 and is sent
		     back to each peripheral node (via IP broadcast
   transmission).

   When 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 QUERY-REPLY packet is delivered received from IP, the (IERP) data IP.
		     X is
   decapsulated and passed on to the higher layer. If the BRP packet
   has not reached its destination, the intended BRP recipient.

	    Action:  The packet is responsible for
   forwarding the discarded.

	D.12
	    Event:   A QUERY-REPLY packet to is received from the next hop toward its destination.

   A.  Packet Format

                    1	                2	            3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Destination Address                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|			  Next Hop Address			|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              Data				|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	Field Description:

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

	* Next Hop Address	(32 bits)
		IP address of intended BRP recipient, but not the "next hop" host
		     intended IERP recipient.

            Action:  If cache space is available, accumulated route
		     information to the destination
                host

	* Data			(variable length)
		Encapsulated data

    B.  Structures

	B.1  Intrazone Routing Table	(see IARP description)

    C.  Interfaces

	C.1  Higher Layer (ie. IERP)
	    C.2.1  Send()	(same interface as IP Send() primitive)
		Used by higher layer protocol to request transmission of
                a data packet
	    C.2.2  Deliver()  (same interface as IP Deliver() primitive)
		Used by should be recorded
		     in the BRP to alert Detected Queries Table, and the higher layer protocol of recorded
		     route information removed from the arrival of a data packet
	C.2  Lower Layer (IP)
	    C.2.1  Send()	(specified in IP standard)
	    C.2.2  Deliver()	(specified in IP standard)

    D.  State Machine packet.  The BRP protocol consists IP
		     addresses of only one state (IDLE).  Therefore,
        no state transitions need X and the previous hops back to be specified. the
		     query source (cached in the Detected Queries Table)
		     are added to the route.
                     The BRP immediately
        acts upon an event and packet is then returns sent to the BRP layer of the
		     previous hop back to the IDLE state.

	Notes: 1) query source.

	D.13
	    Event:   A QUERY-REPLY packet is received from the IP.
		     X is used as a label for the host running this state
                  machine.
	       2) NULL intended BRP recipient and the intended
		     IERP recipient.

            Action:  If cache space is a reserved field value, corresponding available, accumulated route
		     information to an
                  invalid IP address.

	D.1 the destination should be recorded
		     in the Detected Queries Table, and the 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 the IERP, destined for
                     the BORDERCAST address.
		     IERP.

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

	D.15
	    Event:   A
                     copy of ROUTE-ACCUMULATION packet is received from the
		     IP.  X is not the intended BRP recipient.

	    Action:  The packet is made for each peripheral
                     host, P. (i.e., each host in X's Intrazone Routing
                     Table whose shortest route discarded.

	D.16
	    Event:   A ROUTE-ACCUMULATION packet is ROUTING_ZONE_RADIUS
                     hops away received from X). The packet's destination address the
		     IP.  X is set to the intended BRP recipient, but not the
		     intended IERP recipient.

	    Action:  The IP address addresses of P X and the next hop
                     address is set hops to the IP address
		     intended IERP recipient (which are cached in the
		     Detected Queries 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 next hop packet is delivered to P (from X). Each the IERP.  The
		     packet is then broadcasted.

	D.2 sent to the BRP layer of the next
		     hop toward the IERP recipient.
	D.17
	    Event:   A ROUTE-ACCUMULATION packet is received from the IERP, destined for a
                     non-BORDERCAST address.

	    Action:  The IERP packet
		     IP.  X is encapsulated in a BRP packet.
                     The the intended BRP packet`s destination address and next hop
                     address fields are cleared recipient and the BRP
		     intended IERP recipient.

	    Action:  The packet is
                     sent delivered up to the specified destination.

	D.3 IERP.

	D.18
	    Event:   A BRP ROUTE-OPTIMIZATION packet is received from the IP layer. The BRP
                     packet contains a next hop address EQUAL TO NULL.
		     IERP.

	    Action:  X indicates (in its flag field) those route nodes
		     that belong to its routing zone.  The data packet is decapuslated from
		     then sent to the IERP layer of the specified IERP
		     recipient, by way of a BRP packet and
		     delivered transmission to the IERP, with
		     next hop toward the overhead flag set
		     to FALSE.

	D.4 IERP recipient.

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

	    Action:  The data
		     IP.  X is decapuslated from not the intended BRP recipient.

	    Action:  The packet and
		     delivered to the IERP, with the overhead flag set
		     to FALSE.

	D.5 is discarded.

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

	    Action:  The data is decapuslated from the intended BRP packet and
		     delivered to the IERP, with recipient, but not
		     the overhead intended IERP recipient.

	    Action:  X indicates (in its flag set field) those route nodes
		     that belong to TRUE. its routing zone.  The received BRP packet is copied,
		     then sent to the
		     next hop address field is updated IERP layer of the specified IERP
		     recipient, by querying way of a BRP transmission to the
		     Intrazone Routing Table, and
		     next hop toward the new packet is
		     broadcasted.

	D.6 IERP recipient.

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

	    Action:  The data
		     IP.  X is decapuslated from the intended BRP packet recipient and
                     delivered to the IERP, with the overhead
		     intended IERP recipient.

	    Action:  X indicates (in its flag set field) those route nodes
		     that belong to its routing zone.  The packet
		     is then delivered up to TRUE. 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, 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 of the IERP packet.

        E.1  Receive Data Packet from IERP

            {dest} <-- intrpt

            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)

            IERP_prev = my_id
            switch(type)
            {
              case:  QUERY
                if (dest ((bad_link_source == BORDERCAST)
	    { my_id || source == my_id)
                    add(Detected_Queries,packet)
                for (host (IERP_next = each host in Intrazone_Routing_Table)
                {
                    if (Intrazone_Routing_Table[host,0]->hop_count
		      ==ROUTING_ZONE_RADIUS) (IERP next is a peripheral node)
                    {
		  next_hop=Intrazone_Routing_Table[host,0]->next_hop
		  packet<--{host,next_hop,data_packet}
		  broadcast(packet)
                      BRP_next=Intrazone_Routing_Table[host,0]->next_hop
                      load(pk_copy)
                      send(pk_copy,BRP_next)
                    }
                }
	    }
	    else
              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
                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 to length(route)-1)
                {
	      packet<--{dest,NULL,data_packet}
	      send(packet,dest)
                    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

	    {dest,next_hop,data}<--packet
	    overheard=FALSE

            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 (next_hop != NULL) (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
                        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
                    }
                    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 (next_hop (!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 == my_id)
	      {
	        if(dest != my_id) source)
                      flag = f , flag
                    else
                      flag = flag , f

                    if(my_id == IERP_next)
                        deliver(packet, IERP)
                    else
                    {
		  overheard=TRUE
		  next_hop
                      if(IERP_next == source)
                        BRP_next = Intrazone_Routing_Table[dest,0]->next_hop
		  packet<--{dest,next_hop,data}
		  broadcast(packet) prev_hops(0)
                      else
                        BRP_next = next_hops(0)
                      load(packet)
                      send (packet,BRP_next)
                    }
                }
                else
	        overheard=TRUE
	    }
	    deliver(IERP,data,{overheard})

5.0
                    discard(packet)
              break

5. Other Considerations

5.1 Sizing the Zone Radius

   The value of the zone radius determines the performance of the ZRP
   protocol. Zone Routing Protocol is determined by the
   routing zone radius.  In general, highly mobile dense networks should set the zone
   radius to consisting of a few
   fast moving nodes favor smaller values, while in more stationary networks the
   zone radius should be larger. Similarly, in very active networks
   (frequent query requests), routing zones.  On the other hand, a
   sparse network of many slowly moving nodes operates more efficiently
   with a larger zone radius should be larger, and in
   low-activity networks, radius.

   The simplest approach to configuring the routing zone radius should be smaller.

   We believe that setting is to
   make the size of assignment once, prior to deploying the zone radius should network.  This can
   be performed by the administration of the network, network administration, if one exists, or by
   the manufacturer, as a default value. Although some guidance  This may provide acceptable
   performance, especially in situations where network characteristics
   do not vary greatly over space and time.  Alternatively, the ZRP can
   be given as
   adpat to "optimal" value changes in network behavior, through dynamnic configuration
   of the zone radius [Haas-3],
   additional constrains and operational conditions may affect [Haas-3].  In [Haas-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
   choice. draft.

6.0 References

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

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

   [Haas-2]   Haas, Z.J., Z.J. and Pearlman, M.R., "Providing Ad-Hoc
              Connectivity with the Reconfigurable Wireless Networks",
              submitted "The Performance of Query
              Control Schemes for journal publication. the Zone Routing Protocol,"
	      SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998.

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

   [Haas-4]   Haas, Z.J. and Pearlman, M.R., "Determining the Optimal
              Configuration for the Zone Routing Protocol", submitted
              for journal publication.

   [Johnson]  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, editors, chapter 5,
              pp. 153-181, Kluwer, 1996 1996.

   [Murthy]   Murthy, S., and Garcia-Luna-Aceves, J.J., "A "An Efficient
              Routing Protocol for Packet Radio Wireless Networks", MOBICOM'95,
              November 14-15, 1995 MONET, vol. 1,
              no. 2, pp. 183-197, October 1996.

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

   [Perkins]  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 1994.

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

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

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

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

Authors' Information

   Zygmunt J. Haas
   Wireless Networks Laboratory
   323 Frank Rhodes Hall
   School of Electrial 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 Frank Rhodes Hall
   School of Electrial Electrical Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   Email: pearlman@ee.cornell.edu

 The MANET Working Group contacted through its chairs:

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

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