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 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: haas@acm.org or haas@ee.cornell.edu Marc R. Pearlman 319 Frank Rhodes Hall School of Electrial 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 Haas, Pearlman Expires in six months [Page 23]