Subject: Zone-Routing-Protocol (ZRP) reposting

From: Zygmunt Haas <[email-masked]>
Date: Mon, 24 Nov 1997 09:39:20 -0400 (AST)

Hi,

It appears that the previous posting of this Internet Draft did no go
through properly. 

Here is the reposting of the draft - sorry if you got it before.

Enjoy!

Zygmunt Haas.
==-==--=-=-=-= 
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas             tel: +1-607-255-3454
Wireless Networks Laboratory
323 Frank Rhodes Hall             fax: +1-607-255-9072
School of Electrical Engineering  
Cornell University                e-mail: [email-masked]
Ithaca, N.Y. 14853                
U.S.A                             http://www.ee.cornell.edu/~haas/wnl.html
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-

=================================cut here===============================

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

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

Status of this Memo

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

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

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

   Distribution of this memo is unlimited.

Abstract

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

1. Introduction

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

Haas, Pearlman             Expires May 1998                     [Page 1]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

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

Haas, Pearlman             Expires May 1998                     [Page 2]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

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

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

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

Haas, Pearlman             Expires May 1998                     [Page 3]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

2.2 The Interzone Routing Protocol (IERP)

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

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

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

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

Haas, Pearlman             Expires May 1998                     [Page 4]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

2.3 Route Accumulation procedure

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

2.4 Terminating the IERP flood

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

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

2.5 Route failures notifications

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

Haas, Pearlman             Expires May 1998                     [Page 5]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

   initiating a route discovery to the unreachable next hop.

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

2.6 Bordercast Resolution Protocol (BRP)

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

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

3.0 The ZRP Architecture

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

Legend:

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

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

Haas, Pearlman             Expires May 1998                     [Page 6]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

4.0 Implementation Details

4.1 The IntrAzone Routing Protocol (IARP)

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

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

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

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

Haas, Pearlman             Expires May 1998                     [Page 7]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

   B.  Structures

       B.1  Intrazone Routing Table

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

   C.  Interfaces

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

   D.  State Machine

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

Haas, Pearlman             Expires May 1998                     [Page 8]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

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

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

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

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

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

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

Haas, Pearlman             Expires May 1998                     [Page 9]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

    E.  Pseudocode Implementation

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

Haas, Pearlman             Expires May 1998                    [Page 10]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

4.2 IntErzone Routing Protocol (IERP)

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

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

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

   A.  Packet Format

Haas, Pearlman             Expires May 1998                    [Page 11]

INTERNET DRAFT          The Zone Routing Protocol          November 1997
                    1	                2	            3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1    
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type  |    Request ID     | Last Hop  | Hop Mrker | Max Hops  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Destination Address                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|                    Hop 0 Address (Source)                     |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
|                       Hop 1 Address  		                |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |
				| |				    |
			        | |				  source
			       \   /				  route
				\ /				    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|   |
|                      Hop (N-1) Address                        |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--

	Field Description:

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

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

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

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

Haas, Pearlman             Expires May 1998                    [Page 12]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

	B.1	Intrazone Routing Table (See IARP Description)

	B.2	Interzone Routing Table

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

Haas, Pearlman             Expires May 1998                    [Page 13]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

	B.3	Processed Request List

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

    C.  Interfaces

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

    D.  State Machine

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

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

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

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

Haas, Pearlman             Expires May 1998                    [Page 14]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

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

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

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

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

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

Haas, Pearlman             Expires May 1998                    [Page 15]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

	D.6
	    Event:   An IERP reply packet is received containing X as 
		     the source host.
	
	    Action:  The received source route is recorded in Interzone 
                     Routing Table.

	D.7
	    Event:   An IERP reply packet is received containing a node
                     other than X as the source host.
	
	    Action:  The route reply packet is fowarded to the preceding
		     hop in the route

	D.8
	    Event:   An IERP failure packet is received containing X as 
		     the source host.
	
	    Action:  X removes all routes from its Interzone Routing 
		     table which contain the broken link specified by 
		     the bad hop field.

	D.9
	    Event:   An IERP failure packet is received containing a 
		     node other than X as the source host.
	
	    Action:  X fowards the route reply packet to the preceding 
		     hop in the route

    E.  Pseudocode Implementation

	E.1 Intrazone Node Lost

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

Haas, Pearlman             Expires May 1998                    [Page 16]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

	E.2  Initiate Route Discovery

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

	E.3  Report Route Failure

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

	E.4  Receive IERP Packet

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

Haas, Pearlman             Expires May 1998                    [Page 17]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

4.3 Bordercast Resolution Protocol (BRP)

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

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

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

Haas, Pearlman             Expires May 1998                    [Page 18]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

   A.  Packet Format

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

	Field Description:

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

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

	* Data			(variable length)
		Encapsulated data

    B.  Structures

	B.1  Intrazone Routing Table	(see IARP description)

    C.  Interfaces

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

    D.  State Machine

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

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

Haas, Pearlman             Expires May 1998                    [Page 19]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

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

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

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

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

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

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

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

Haas, Pearlman             Expires May 1998                    [Page 20]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

	E.1  Receive Data Packet from IERP

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

	E.2  Receive Packet from IP

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

Haas, Pearlman             Expires May 1998                    [Page 21]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

	    }
	    deliver(IERP,data,{overheard})

5.0 Other Considerations

5.1 Sizing the Zone Radius

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

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

6.0 References

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

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

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

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

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

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

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

Haas, Pearlman             Expires May 1998                    [Page 22]

INTERNET DRAFT          The Zone Routing Protocol          November 1997

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

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

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

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

Authors' Information

   Zygmunt J. Haas
   Wireless Networks Laboratory
   323 Frank Rhodes Hall
   School of Electrial Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   tel: (607) 255-3454, fax: (607) 255-9072
   Email: [email-masked] or [email-masked]

   Marc R. Pearlman
   319 Frank Rhodes Hall
   School of Electrial Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   Email: [email-masked]

 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
   [email-masked]

   Joseph Macker
   Information Technology Division
   Naval Research Laboratory
   Washington, DC 20375
   (202) 767-2001
   [email-masked]

Haas, Pearlman               Expires in six months             [Page 23]

================================cut here================================