INTERNET-DRAFT Zygmunt J. Haas, Cornell University Marc R. Pearlman, Cornell University Expires in six months August 1998 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 the Zone Routing Protocol (ZRP), a hybrid routing protocol suitable for a wide variety of mobile ad-hoc networks, especially those with large network spans and diverse mobility patterns. Each node proactively maintains routes within a local region (referred to as the routing zone). Knowledge of the routing zone topology is leveraged by the ZRP to improve the efficiency of a reactive route query/reply mechanism. The proactive maintenance of routing zones also helps improve the quality of discovered routes, by making them more robust to changes in network topology. The ZRP can be configured for a particular network by proper selection of a single parameter, the routing zone radius. This version of the ZRP internet draft describes a number of features which have been added to the protocol. The distance-vector based IARP algorithm has been enchanced to prevent the 'counting to infinity problem'. Route caching is now supported by the IERP route discovery process. By allowing discovered route information to be distributed in caches, route accumulation in the IERP query/ reply packets can be avoided, thereby reducing the amount of route discovery traffic, and improving the query response time. Two additional (optional) stages have also been added to the route discovery process, to support the acquisition and optimization of source routes. Haas, Pearlman Expires February 1999 [Page i] INTERNET DRAFT The Zone Routing Protocol August 1998 Contents Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2 2. Overview of the Zone Routing Protocol . . . . . . . . . . . 3 2.1 The Notion of a Routing Zone and the Intrazone Routing Protocol (IARP) . . . . . . . 3 2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 4 2.2.1 Routing Zone Based Route Discovery . . . . . . 4 2.2.2 Route Accumulation Procedure . . . . . . . . . 5 2.2.3 Query Control Mechanisms . . . . . . . . . . . 6 2.2.4 Route Maintenance . . . . . . . . . . . . . . . 7 3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 8 4. Implementation Details . . . . . . . . . . . . . . . . . . 9 4.1 Intrazone Routing Protocol (IARP) . . . . . . . . . . 9 A. Packet Format . . . . . . . . . . . . . . . . . . 9 B. Structures . . . . . . . . . . . . . . . . . . . . 10 C. Interfaces . . . . . . . . . . . . . . . . . . . . 10 D. State Machine . . . . . . . . . . . . . . . . . . 11 E. Pseudocode Implementation . . . . . . . . . . . . 13 4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 14 A. Packet Format . . . . . . . . . . . . . . . . . . 16 B. Structures . . . . . . . . . . . . . . . . . . . . 18 C. Interfaces . . . . . . . . . . . . . . . . . . . . 19 D. State Machine . . . . . . . . . . . . . . . . . . 19 E. Pseudocode Implementation . . . . . . . . . . . . 22 4.3 Bordercasting Resolution Protocol (BRP) . . . . . . . 25 A. Packet Format . . . . . . . . . . . . . . . . . . 26 B. Structures . . . . . . . . . . . . . . . . . . . . 26 C. Interfaces . . . . . . . . . . . . . . . . . . . . 26 D. State Machine . . . . . . . . . . . . . . . . . . 26 E. Pseudocode Implementations . . . . . . . . . . . . 31 5. Other Considerations . . . . . . . . . . . . . . . . . . . 37 5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 37 6. References . . . . . . . . . . . . . . . . . . . . . . . . 38 Haas, Pearlman Expires February 1999 [Page 1] INTERNET DRAFT The Zone Routing Protocol August 1998 1. Introduction One of the major challenges in designing a routing protocol for the ad hoc networks stems from the fact that, on one hand, to determine a packet route, a node needs to known at least the reachability information to its neighbors. On the other hand, in an ad hoc network, the network topology can change quite often. Furthermore, as the number of network nodes can be large, the potential number of destinations is also large, requiring large and frequent exchange of data (e.g., routes, routes updates, or routing tables) among the network nodes. Thus, the amount of update traffic can be quite high. This is in contradiction with the fact that all updates in a wirelessly interconnected ad hoc network travel over the air and, thus, are costly in resources. In general, the existing routing protocols can be classified either as proactive or as reactive. Proactive protocols attempt to continuously evaluate the routes within the network, so that when a packet needs to be forwarded, the route is already known and can be immediately used. The family of Distance-Vector protocols is an example of a proactive scheme. 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], [AODV], [TORA] (see also [Park]). The advantage of the proactive schemes is that, once a route is needed, there is little delay until the route is determined. In reactive protocols, because route information may not be available at the time a datagram is received, the delay to determine a route can be quite significant. Furthermore, the global flood-search procedure of the reactive protocols requires significant control traffic. Because of this long delay and excessive control traffic, pure reactive routing protocols may not be applicable to real-time communication. However, pure proactive schemes are likewise not appropriate for the ad hoc networking environment, as they continuously use a large portion of the network capacity to keep the routing information current. Since nodes in an ad hoc networks move quite fast, and as the changes may be more frequent than the route requests, most of this routing information is never even used! This results in a further waste of the wireless network capacity. What is needed is a protocol that, on one hand, initiates the route- determination procedure on-demand, but at limited search cost. The protocol described in this draft, termed the "Zone Routing Protocol (ZRP)" ([Haas-1], [Haas-2]), is an example of a such a hybrid proactive/reactive scheme. Haas, Pearlman Expires February 1999 [Page 2] INTERNET DRAFT The Zone Routing Protocol August 1998 The ZRP, on one hand, limits the scope of the proactive procedure only to the node's local neighborhood. On the other hand, the search throughout the network, although global in nature, is done by efficiently querying selected nodes in the network, as opposed to querying all the network nodes. A related issue is that of updates in the network topology. For a routing protocol to be efficient, changes in the network topology should have only a local effect. In other words, creation of a new link at one end of the network is an important local event but, most probably, not a significant piece of information at the other end of the network. Proactive protocols tend to distribute such topological changes widely in the network, incurring large costs. The ZRP limits propagation of such information to the neighborhood of the change only, thus limiting the cost of topological updates. 2. Overview of the Zone Routing Protocol 2.1 The Notion of a Routing Zone and the Intrazone Routing Protocol (IARP) A routing zone is defined for each node X, and includes the nodes whose minimum distance in *hops* from X is at most some predefined number, which is referred to as the Zone Radius. An example of a routing zone (for node A) of radius 2 is shown below. +-----------------------------------------+ | +---+ | | +---+ ---| F |-------| | +---+ | +---+ --| C |--/ +---+ +---+ | | 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 paths from A, one with length 2 hops and one with length 3 hope. Since the minimum is less or equal than 2, E is within A's routing zone. Peripheral nodes are nodes whose minimum distance to the node in question is equal exactly to the zone radius. Thus, in the above figure, nodes D, F, and E are A's peripheral nodes. An important consequence of the routing zone construction is the ability of a node to deliver a packet to its peripheral nodes. This service, which we refer to as bordercasting, allows for more efficient network-wide searching than simple neighbor broadcasting. Bordercasting could be implemented either through a series of IP unicasts or an IP multicast (Distance Vector Multicast Routing Haas, Pearlman Expires February 1999 [Page 3] INTERNET DRAFT The Zone Routing Protocol August 1998 Protocol [RFC-1075])) to the peripheral nodes. (In cases where multicasting is supported, the multicasting approach is preferred to reduce the amount of traffic over the air.) However, as will be explained later, efficient ZRP operation requires that these unicast or multicast services be provided by the ZRP, with IP providing best- effort delivery to the specified ZRP next hops. The ZRP supports the proactive maintenance of routing zones through its proactive Intrazone Routing Protocol (IARP). Through the IARP, each node learns the identity of and the (minimal) distance to all the nodes in its routing zone. The IARP may be derived from a wide range of proactive protocols, such as Distance Vector (e.g., [Murthy], [DSDV]) or Shortest Path First (e.g., OSPF [RFC-2178]). Whatever the choice of IARP is, the base protocol needs to be modified to ensure that the scope of this operation is restricted to the radius of a node's routing zone. Because each node needs to proactively acquire route information only for the nodes within its zone, the total amount of IARP traffic does not depend on the size of the network, which may be quite large 2.2 The Interzone Routing Protocol (IERP) While the IARP maintains routes within a zone, the IERP* is responsible for finding routes between nodes located at distances larger than the zone radius. The IERP is distinguished from standard flood-search query/response protocols by exploiting the routing zone topology. A node is able to respond positively to any queries for its routing zone nodes. For large networks, relatively few destinations lie within any particular node's routing zone. In this more likely case, the node can efficiently continue the propagation of the query, through the routing zone-based bordercast delivery mechanism. 2.2.1 Routing Zone Based Route Discovery The IERP operates as follows: The source node first checks whether the destination is within its routing zone. (Again, this is possible as every node knows the content of its zone). If so, the path to the destination is known and no further route discovery processing is required. If, on the other hand, the destination is not within the source's routing zone, the source bordercasts a route query to all of its peripheral nodes. Now, in turn, all the peripheral nodes execute the same algorithm: check whether the destination is within their zone. If so, a route reply 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, executes the same procedure. An example of this Route Discovery procedure is demonstrated in the figure below. Haas, Pearlman Expires February 1999 [Page 4] INTERNET DRAFT The Zone Routing Protocol August 1998 +---+ +---+ | F | +---+---| C |----+---+-----+---+ +---+ | D | +---+ | E |----| H | +---+ | +---+-----+---+ +---+ +---+----| B | | | A | +---+-----+---+ +---+ +---+ | G | | I | +---+ +---+ | +---+ +---+ | J | | C |----+---+----+---+ +---+ +---+ | K |----| L | +---+ +---+ The node A has a datagram to send to node L. Assume a uniform routing zone radius of 2 hops. Since L is not in A's routing zone (which includes B,C,D,E,F,G), A bordercasts a routing query to its peripheral nodes: D,F,E, and G. Each one of these peripheral nodes check whether L exists in their routing zones. Since L is not found in any routing zones of these nodes, the nodes bordercast the request to their peripheral nodes. In particular, G bordercasts to K, which realizes that L is in its routing zone and returns the requested route (L-K-G-A) to the query source, namely A. * Some functions of the IERP, including bordercasting, route accumulation, and query control (see later), are performed by a special component of the IERP called the Bordercast Resolution Protocol (BRP). Sections 3.0 and 4.0 describe, in detail, the relationship between the BRP and the IERP proper. 2.2.2 Route Accumulation Procedure The query propagation mechanism allows a route query to indirectly reach the desired destination (through some node Y, which discovers the destination in its routing zone.) To complete the route discovery process, Y needs to send a reply back to the query's source, S, providing S with the desired route. To perform the route reply, sufficient information needs to be accumulated during the query phase so that Y is provided with a route back to S. Providing routes from discovering node Y to query source S, and from the query source S back to the query destination D (through Y), is the role of the Route Accumulation procedure. In the basic Route Accumulation, a node appends its IP address to a received query packet. The sequence of IP addresses specifies a route from the query's source to the current node. By reversing this sequence, a route may also be obtained back to the source. In this way, Y may send a reply back to S, through strict source routing. Haas, Pearlman Expires February 1999 [Page 5] INTERNET DRAFT The Zone Routing Protocol August 1998 Given sufficient storage space, a queried node may cache routing information accumulated in the query packet, allowing the information to be remove from the packet. This has the benefit of reducing the length of the query packet, thereby decreasing the query traffic and query response time. The IP addresses that remain in the packet can be used to form a loose source route back to the query's source (If ALL nodes have cached the accumulated route information, then this effectively becomes next hop routing. If no nodes have cached accumulated route information, then this defaults to the basic case previously discussed). The same caching strategy can be applied to the reply packet on its way back to the source. In this case, a loose source route to the destination is formed. 2.2.3 Query Control Mechanisms Bordercasting has the potential to support global querying schemes that are more efficient than flooding. To achieve this efficiency, the protocol should be able to detect and terminate a query thread when it appears in a previously queried region of the network (i.e. arrives at a node belonging to the routing zone of a previously queried node). This detection / termination capability is significantly limited when bordercasting is implemented directly through IP unicast or IP multicast. By implementing bordercasting within the ZRP, the nodes that relay the query to the peripheral node are able to detect the passing query. If the underlying IP delivery is (neighbor) broadcast or if IP is operating in promiscuous mode, then nodes that overhear a query transmission are also able to detect the query, further strengthening the Query Detection (QD) mechanism. Upon detecting a query, the identifying query parameters (i.e. query source, query ID) are recorded in a Detected Queries Table, to provide a basis for termination of future threads of that query. A node can consider a query to be redundant if it has already detected that query, bordercasted by a different node. If bordercasting is implemented directly through IP unicast/ multicast, then a query thread could only be terminated after being received by the peripheral node (bordercast destination). This could result in wasted transmissions as a query penetrates into a previously queried region. Implementing bordercasting in the ZRP allows the protocol to provide an Early Termination (ET), as the redundant query enters the previously queried region. Haas, Pearlman Expires February 1999 [Page 6] INTERNET DRAFT The Zone Routing Protocol August 1998 2.2.4 Route Maintenance In addition to initially discovering routes, the IERP may also assume responsibility for monitoring the integrity of these routes and repairing failed routes as appropriate. Route failures can be detected either proactively or reactively. Proactive route failure detection is triggered by the IARP, in response to a node leaving the routing zone. Any IERP routes containing this node as the first hop can be considered invalid. Route failures may also be detected reactively, by IP, when the next hop in a datagram's source route is determined to be unreachable (i.e. does not appear in the (Intrazone) Routing Table). Upon detection of a route failure, a node may choose to notify the route's source of the failure and / or attempt to repair the route. A route failure notification consists of a transmission back to the query source, indicating that the source route has failed, and possibly the hop at which it failed. This type of service is provided by protocols like ICMP. The node that detects the route failure may also try to repair the failed connection by discovering a route to bypass the failed connection. The repair discovery process is nearly identical to an initial route discovery. Route repairs should not be substantially longer than the original failed connection. Thus, the depth of a repair query can be limited, through the use of hop counter. This has the advantage of producing much less query traffic than an unrestricted initial route query. After a successful repair, the route's source MAY be notified so that routes are properly selected for use. Alternatively, the repair could go unreported without compromising the connectivity between source and destination. Haas, Pearlman Expires February 1999 [Page 7] INTERNET DRAFT The Zone Routing Protocol August 1998 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 ZRP Entities ------------ IARP IntrAzone Routing Protocol IERP IntErzone Routing Protocol BRP Bordercast Resolution Protocol (component of IERP) Additional Protocols -------------------- NDM Neighbor Discovery/Maintenance Protocol Note, it is assumed that basic neighbor discovery operation is implemented by the MAC/link-layer protocols. Thus the NDM protocol remains unspecified here. Haas, Pearlman Expires February 1999 [Page 8] INTERNET DRAFT The Zone Routing Protocol August 1998 4. Implementation Details 4.1 The IntrAzone Routing Protocol (IARP) The IARP can be implemented through various proactive protocols. We present here an implementation based on a modified version of the Distance Vector algorithm. Routing information to a node is limited to the the routing zone of that node. In this version, routing information consists of the route cost and the IP addresses of the route destination and next two hops to the destination. The second hop is included to identify routes where a node is it's own second hop. This particular looping condition can result in the "counting to infinity" problem. By deleting these routes, this problem can be avoided, allowing the IARP to converge faster. A node may receive new route information either from a received IARP packet or from an interrupt generated by its Neighbor Discovery / Maintenance (NDM) proces*. In the special case when a host has discovered a neighor, the IARP is responsible for sending to the new neighbor the shortest route to each host which is common to both of their routing zones (i.e. each host with a hop count less than it's routing zone radius). The node then records the new route information in its Intrazone Routing Table. If the shortest path to the host has changed, the terminal broadcasts an IARP packet reflecting the change. * IARP relies on the services of a separate protocol (referred to here as the Neighbor Discovery/Maintenance Protocol) to provide current information about a host's neighbors. At the least, this information must include the IP addresses of all the neighbors. The IARP can be readily configured to support supplemental neighbor information, such as link cost. A. Packet Format 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Hop #1 Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Hop #2 Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Hop Cnt| +-+-+-+-+ Haas, Pearlman Expires February 1999 [Page 9] INTERNET DRAFT The Zone Routing Protocol August 1998 Field Description: * Destination Address (32 bits) IP address of the destination host * Next Hop # 1 Address (32 bits) IP address of the "next hop" host to the destination host * Next Hop # 2 Address (32 bits) IP address of the Next Hop #1 's "next hop" host to the destination host * Hop Count (4 bits) Length of the route to the destination host, measured in hops B. Structures B.1 Intrazone Routing Table +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Routes | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Host | 0 | 1 | ==> | M-1 | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Next : Hop | Next : Hop | ==> | Next : Hop | | | Hop : Count | Hop : Count | | Hop : Count | +-+-+-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-+-+-+-:-+-+-+-+ | | : | : | | : | |-----------|-------:-------|-------:-------|-----|-------:-------| | | : | : | | : | |-----------|-------:-------|-------:-------|-----|-------:-------| | | : | : | | : | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ C. Interfaces C.1 Higher Layer (N/A) C.2 Lower Layer (IP) C.1.1 Send() (specified in IP standard) C.1.2 Deliver() (specified in IP standard) C.3 NDM C.3.1 Neighbor_Lost(host) Used by the NDM to notify the IARP that direct contact has been lost with "host". C.3.2 Neighbor_Found(host) Used by the NDM to notify the IARP that direct contact has been confirmed with "host". C.4 IERP C.4.1 Zone_Node_Lost(host) Used by IARP to notify the IERP that a node no longer exists within the routing zone. Haas, Pearlman Expires February 1999 [Page 10] INTERNET DRAFT The Zone Routing Protocol August 1998 D. State Machine The IARP protocol consists of only one state (IDLE). Therefore, no state transitions need to be specified. The IARP immediately acts upon an event and then returns back to the IDLE state. Notes: 1) X is used as a label for the host running this state machine. 2) INF is a reserved field value corresponding to "infinity". D.1 Event: An IARP packet is received containing route information to a destination D. The hop count associated with the received route is LESS THAN OR EQUAL TO the routing zone radius. The second next-hop is EQUAL to X. Action: NONE D.2 Event: An IARP packet is received containing route information to a destination D. The hop count associated with the received route is LESS THAN the routing zone radius. The second next-hop is NOT EQUAL to X. Action: The received route is recorded in the Intrazone Routing Table. If the received route is shorter than the previous shortest route to D, then a new IARP packet containing route information to D through X is broadcasted. D.3 Event: An IARP packet is received containing route information to a destination D. The hop count is EQUAL TO the routing zone radius. The second next-hop is NOT EQUAL to X. Action: The received route is recorded in the Intrazone Routing Table. Haas, Pearlman Expires February 1999 [Page 11] INTERNET DRAFT The Zone Routing Protocol August 1998 D.4 Event: An IARP packet is received containing route information to a destination D. The hop count is equal to INF. Action: The route to D is removed from the Intrazone Routing Table. 1) If the Intrazone Routing Table still contains a route to D and the length of the shortest route has increased due to the route removal, then the an IARP packet containing the shortest route to D through X is broadcasted. 2) If the Intrazone Routing Table contains no more routes to D, then an IARP packet containing a route to D through X with hop count of INF is broadcast. A "Host Lost" interrupt is generated to alert the IERP that D has moved beyond the routing zone. D.5 Event: A "Neighbor Found" interrupt is received, indicating the discovery of a neighbor host N. Action: For each destination in X's Intrazone Routing Table, an IARP packet is sent to N containing the best route to that destination. An IARP packet is then broadcasted containing the 1 hop route to N through X. D.6 Event: A "Neighbor Lost" interrupt is received, indicating that host N is no longer a neighbor of X Action: The one hop route to N is removed from the Intrazone Routing Table. 1) If the Intrazone Routing Table still contains a route to N and the length of the shortest route has increased due to the route removal, then the an IARP packet containing the shortest route to N through X is broadcasted. 2) If the Intrazone Routing Table contains no more routes to N, then an IARP packet containing a route to D through X with hop count of INF is broadcast. A "Host Lost" interrupt is generated to alert the IERP that D has moved beyond the routing zone. Haas, Pearlman Expires February 1999 [Page 12] INTERNET DRAFT The Zone Routing Protocol August 1998 E. Pseudocode Implementation E.1 Update Intrazone Routing Table if (packet arrived) {host, route->next_hop, next_next_hop, route->hop_count} <-- packet else { {host} <-- intrpt route->next_hop=host if (type(intrpt) == "Neighbor Found") { for dest = each host in Intrazone_Routing_Table { best_route = Intrazone_Routing_Table[dest,0] if (best_route->hop_count < ROUTING_ZONE_RADIUS) { packet <--{dest,my_id,best_route->next_hop, best_route->hop_count+1} send(packet,host) } } route->hop_count=1 } else route->hop_count=INF } former_best_route = Intrazone_Routing_Table[host,0] if (route->hop_count < INF) if(route->next_next_hop != my_id add(Intrazone_Routing_Table[host], route) else remove(Intrazone_Routing_Table[host], route) best_route = Intrazone_Routing_Table[host,0] if (best_route != NULL) { if (best_route->hop_count != former_best_route->hop_count && best_route->hop_count < ROUTING_ZONE_RADIUS) { packet <-- {host, my_id, best_route->next_hop, best_route->hop_count+1} broadcast(packet) } } else { force_intrpt("IERP","Zone Node Lost",{host}) packet <-- {host, my_id, my_id, INF} broadcast(packet) } Haas, Pearlman Expires February 1999 [Page 13] INTERNET DRAFT The Zone Routing Protocol August 1998 4.2 IntErzone Routing Protocol (IERP) The Interzone Routing Protocol (IERP) is responsible for discovering and maintaining routes to hosts which are beyond a node's routing zone. The IERP acquires routing information reactively, exploiting the knowledge of the routing zone topology through the bordercasting delivery service. This version of the IERP extends the basic query / reply mechanism described in Section 3. In the basic protocol, queries are terminated before reaching the query destination. This provides a faster response to the route query than if the destination, D, were to respond directly. However, because D never receives the query, it does not acquire a route back to the source, S. If the D needs to send data back to S (which is often the case, given the bi-directional nature of many applications), a separate route query from D to S would have to be initiated. This substantial overhead is avoided by having the query forwarded to D, by the node Y that discovers D in its routing zone. We refer to this as a QUERY EXTENSION. Both the source and destination can acquire routes to each other through the BRP route accumulation mechanisms (to be discussed later). Distributing route information in the caches of the route's nodes can significantly reduce the size of the IERP packets and provide for a faster query response. On the other hand, QOS requirements for a particular application may favor a source specified route. (rather than a distributed next-hop approach). Source routing requires that the discovered route information be accumulated in the IERP packets, rather than cached. This IERP implementation satisfies the demands for rapid query response and source routing support by two stages of route reporting. In the first two stages, route information is cached by the route's nodes (when possible). Next-hop route are quickly returned to the source in QUERY-REPLY packets and forwarded to the destination in QUERY- EXTENSION packets. At this point, bi-directional connectivity is established. In the third stage, the source and destination can provide each other with complete source routes, by sending each other ROUTE-ACCUMULATION packets. As these packets traverse the route, the cached route information is accumulated in the packets, thereby constructing the desired source route. Variations on this IERP implementation can be realized by combining or eliminating some of these stages. For example, if source routing is not desired, the ROUTE-ACCUMULATION stage can be eliminated. Also, if all of the route's nodes elect not to cache the routing information (perhaps due to storage limitations), then the QUERY REPLY and QUERY-EXTENSION packets essentially serve the role of ROUTE-ACCUMULATION packets, obviating the need for a separate ROUTE-ACCUMULATION stage. Haas, Pearlman Expires February 1999 [Page 14] INTERNET DRAFT The Zone Routing Protocol August 1998 Because each node proactively maintains the local topology of its routing zone, it is not necessary for a source route to specify every hop along the route (i.e. strict source routing). A properly chosen subset of the complete source route can be used to specify the route to the destination, and where desirable, the reverse route back to the source. The IERP supports such an optimization through a final ROUTE-OPTIMIZATION stage. The details of the route optimization are described in the BRP specification. Upon completion of the ROUTE-OPTIMIZATION stage, sufficient routing zone membership is acquired for each node in the route so that the source route may be reduced (by translating this route reduction into an appropriate set covering problem, and employing a suitable heuristic). +-----+ +-----+ +-----+ | S | . . . . | Y | . . . | D | +-----+ +-----+ +-----+ (1) search for QUERY route |--------------------------> QUERY QUERY (2) establish REPLY EXTENSION connectivity <--------------------------| |=============> (3) provide ROUTE-ACCUMULATION source route |----------------------------------------> <========================================| (4) optimize ROUTE-OPTIMIZATION source route <----------------------------------------| |========================================> Sequence of the IERP Route Discovery Stages Haas, Pearlman Expires February 1999 [Page 15] INTERNET DRAFT The Zone Routing Protocol August 1998 A. Packet Format 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Rsvd | Hops Left | Query ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bad Link Source Address (repair only) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- | Next IERP Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ BRP | Next BRP Address | fields +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Prev IERP Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- | Hop 0 Address (Source) | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Hop 1 Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | \| |/ route \ / | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | | Hop (N-2) Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Hop (N-1) Address (Destination) | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- | Flags (optional) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Field Description: * Type (4 bits) Identifies the type of IERP packet. The current version of IERP contains five packet types: QUERY: request for an Interzone source route to the destination specified by the Destination IP Address QUERY-EXTENSION: extension of a QUERY packet sent from the node that discovers the Destination to the Destination itself. Haas, Pearlman Expires February 1999 [Page 16] INTERNET DRAFT The Zone Routing Protocol August 1998 QUERY-REPLY: response to a QUERY packet, sent from the node that discovers the Destination back to the Source. At a minimum, the QUERY-REPLY contains next-hop route information to the Destination. (In general, returns the source route up to the first node which has cached routing information. If no nodes have cached routing information, then the complete source route is returned.) ROUTE-ACCUMULATION (optional): sent by the Source to the Destination, in response to a QUERY-REPLY, and sent by the Destination to the Source, in response to a QUERY-EXTENSION. Routing information cached at the route's nodes is accumulated in this packet, providing a complete source route at the destination of this packet. ROUTE-OPTIMIZATION (optional): sent by the Source to the Destination, and by the Destination to the Source, in response to a ROUTE-ACCUMULATION. Flags are appended to this packet reflecting the mutual routing zone membership of each node in the source route. * Query ID (16 bits) Sequence number which, along with the Source Address (see below) uniquely identifies any route query in the network. * Hops Left (8 bits) Number of hops that a route query may continue to propagate. This field allows a querying node to configure the depth of a route search, to control the amount of IERP traffic generated. * Bad Link Address (32 bits) Used during route repairs. Contains the IP Address corresponding to the source of routes failed link. * Next IERP Address (32 bits) IP address of the next IERP recipient * Next BRP Address (32 bits) IP address of the next BRP recipient. (i.e. next hop to the next IERP recipient) * Prev IERP Address (32 bits) IP address of the previous IERP recipient Haas, Pearlman Expires February 1999 [Page 17] INTERNET DRAFT The Zone Routing Protocol August 1998 * Source Route (N * 32 bits) Variable length field that contains the IP addresses of the source route's nodes. - route(0) contains the IP address of the route's source. - route(N-1) contains the IP address of the route's destination - in general, route(n) contains the IP address of the n-th hop of the source route * Flags (N * 32*ceil(N/32) bits) The k-th bit of the n-th flag subfield indicates whether route(k) is located within route(n)'s routing zone. This routing zone membership information, collected during the optional ROUTE-OPTIMIZATION stage, may be used to determine the shortest possible specification for the accumulated source route. B. Structures B.1 Intrazone Routing Table (See IARP Description) B.2 Interzone Routing Table +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Routes | + Dest +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | 0 | 1 | ==> | M-1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | ==> | | |---------|-----------|-----------|-----|-----------| | | | | ==> | | |---------|-----------|-----------|-----|-----------| | | | | | | ==> | | +-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | \ / \ / +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ | 0 |==>| 1 |==> ...==>| N-1 | source +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ route source first (N-1) host hop hop Haas, Pearlman Expires February 1999 [Page i8] INTERNET DRAFT The Zone Routing Protocol August 1998 C. Interfaces C.1 Higher Layer (N/A) C.2 Lower Layer (BRP) C.2.1 Send() (same interface as IP send()) Used by the IERP to request transmission of an IERP packet. C.2.2 Deliver() (same interface as IP deliver()) Used by the BRP to alert the IERP of the arrival of a data packet. C.3 IARP C.3.1 Zone_Node_Lost(host) Used by the IARP to notify the IERP that a node has left the routing zone C.4 ICMP C.4.1 Host_Unreachable() (specified in ICMP standard) C.4.2 Source_Route_Failed() (specified in ICMP standard) D. 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 "Zone_Node_Lost" interrupt is received, indicating that the node H has moved beyond the routing zone. Action: Remove every route from the Interzone Routing Table which contains H. If any routes containing H are found, then a route repair (limited depth route discovery) to H is initiated. D.2 Event: A "Host_Unreachable" interrupt is received from the ICMP, indicating an unknown destination host D. Action: A full depth route discovery to D is initiated. The query_id is incremented and assigned to a new QUERY packet. The route is initialized with the IP addresses of the route's source and destination IP addresses (X and D). Finally, the QUERY packet is bordercasted. Haas, Pearlman Expires February 1999 [Page 19] INTERNET DRAFT The Zone Routing Protocol August 1998 D.3 Event: A "Source_Route_Failed" or "Proactive_Repair" interrupt is received, indicating that the next hop, H, specified in a source route does not appear within the routing zone. Action: A limited depth route discovery to H is initiated. The query_id is incremented and assigned to a new QUERY packet. The route is initialized with the valid portion of the failed route, and the bad link address field is set with X's IP address, to indicate the location of the route failure. Finally, the QUERY packet is bordercasted. D.4 Event: A QUERY packet is received with a destination that appears within X's routing zone. Action: A QUERY-REPLY is sent back to the query source, and a QUERY-EXTENSION is sent to the query destination. D.5 Event: A QUERY packet is received with a destination that DOES NOT appear within X's routing zone. Action: The QUERY packet is bordercasted. D.6 Event: A QUERY-EXTENSION packet is received. Action: The packet contents are moved to a ROUTE- ACCUMULATION packet. The ROUTE-ACCUMULATION packet is sent to the query source. D.7 Event: A QUERY-REPLY packet is received. Action: The packet contents are moved to a ROUTE- ACCUMULATION packet. The ROUTE-ACCUMULATION packet is sent to the query destination. D.8 Event: A ROUTE-ACCUMULATION packet is received. X is not the final destination of this packet (i.e. X != IERP_next). This only occurs when the accumulated route contains a repair Action: The bad link is replaced by the path repair in the Interzone Routing Table. Haas, Pearlman Expires February 1999 [Page 20] INTERNET DRAFT The Zone Routing Protocol August 1998 D.9 Event: A ROUTE-ACCUMULATION packet is received. X is either the route source or (route destination). Action: The (reversed) accumulated route is added to the Interzone Routing Table or replaces a failed route if the packet specifies a bad link. In addition, if X is the ROUTE-ACCUMULATION destination, the packet contents may be moved to a ROUTE- OPTIMIZATION packet, which is then sent to the query destination (query source). D.10 Event: A ROUTE-OPTIMIZATION packet is received. Action: The routing zone membership information that is collected in the ROUTE-OPTIMIZATION packet is processed. The resulting optimized route(s) are added to the Interzone Routing Table. E. Pseudocode Implementation We define two complimentary operations on packets: extract(packet) and load(packet) extract (packet) extracts the fields of the IERP packet to the following variables: {type, hops_left, query_id, bad_link_source, next_IERP, next_BRP, prev_IERP, route, flag} load (packet) loads the values of the aforementioned variables into the fields of the IERP packet. Haas, Pearlman Expires February 1999 [Page 21] INTERNET DRAFT The Zone Routing Protocol August 1998 E.1 Routing Zone Node Lost {lost_host} <-- intrpt repair_link = FALSE for host = each host in Interzone Routing Table { for (route = each Interzone route to host) { if (lost_host (EXISTS IN) route) { if (PROACTIVE_REPAIRS_ENABLED) { removal_timer = ROUTE_QUERY_TIMEOUT repair_link = TRUE } else removal_timer = 0 schedule( remove(Interzone_Routing_Table[host]->route(m)), removal_timer) } } } if(repair_link) { bad_link = my_id + lost_host force_intrpt("IERP","Proactive_Repair", bad_link) } E.2 Initiate Route Discovery {route} <-- intrpt dest = route(length(route)-1) current_hop_ptr = get_index(route, my_id) prev_hops = route(0: current_hop_ptr-1) route = prev_hops + my_id + dest if (type(intrpt) == "Proactive_Repair" || type(intrpt) == "Source_Route_Failed") { hops_left = MAX_REPAIR_HOPS bad_link_source = my_id } else { hops_left = MAX_FULL_QUERY_HOPS bad_link_source = NULL } query_id ++ load (packet) send (packet, BORDERCAST) Haas, Pearlman Expires February 1999 [Page 22] INTERNET DRAFT The Zone Routing Protocol August 1998 E.3 Receive IERP Packet extract(packet) source=route(0) dest = route(length(route)-1) switch(pk_type) { case: QUERY if (dest (EXISTS IN) Intrazone_Routing_Table) { type = QUERY-REPLY if(bad_link_source) IERP_next = bad_link_source else IERP_next = source load(packet) send(packet) type = QUERY-EXTENSION IERP_next = dest load(packet) send(packet) } else bordercast(packet) break case: QUERY-EXTENSION type = ROUTE-ACCUMULATION IERP_next=source send(packet) break case: QUERY-REPLY type = ROUTE-ACCUMULATION IERP_next = dest load (packet) send (packet) break Haas, Pearlman Expires February 1999 [Page 23] INTERNET DRAFT The Zone Routing Protocol August 1998 case: ROUTE-ACCUMULATION if (bad_link_source) { path_source_ptr = get_index(route, bad_link_source) path_dest_ptr = get_index(route, dest) if (IERP_next == source) { bad_link = bad_link_source + dest path_repair = route(path_source_ptr:path_dest_ptr) } if (IERP_next == dest) { bad_link = dest + bad_link_source path_repair = reverse(route(path_source_ptr : path_dest_ptr)) } replace(Interzone_Routing_Table, bad_link,path_repair) } else { if (my_id == source) add(Interzone_Routing_Table, route) if (my_id == dest) add(Interzone_Routing_Table, reverse(route)) } if (my_id == IERP_next) { if (my_id == source) IERP_next = dest if (my_id == dest) IERP_next = source type = ROUTE-OPTIMIZATION load (packet) send (packet) } break case: ROUTE-OPTIMIZATION if (my_id == source) add(Interzone_Routing_Table, route, flags) if (my_id == dest) add(Interzone_Routing_Table, reverse(route), flags) break } Haas, Pearlman Expires February 1999 [Page 24] INTERNET DRAFT The Zone Routing Protocol August 1998 4.3 Bordercast Resolution Protocol (BRP) The BRP is a sublayer of the IERP that performs the operations of bordercasting, query control, route accumulation and routing zone labelling, which form the basis for the route discovery procedure. In this BRP implementation, bordercasting is implemented as a series of unicasted messages to the peripheral nodes. The BRP is able to identify the peripheral based on the information contained in the Intrazone Routing Table. Rather than unicasting to the peripheral node directly through IP, the bordercasted packets are relayed to the peripheral nodes by the BRP layer. IP is used only to send these messages one hop toward the peripheral nodes. This allows the BRP to detect all QUERY packets that are received by that node. To efficiently terminate the query, the BRP needs to record sufficient information from each detected query. The query's source and ID, which serve to uniquely identify a query, are added to the Detected Queries Table. In addition, the IP address of the last node to bordercast the query is also recorded in the Detected Queries table. Any threads of this query that are later received from a different bordercasting node are discarded. Each query also contains a hop counter that is decremented at each node. When the counter expires, the packet is discarded. IERP packets (excluding ROUTE-OPTIMIZATION packets) that are not terminated next undergo a route accumulation procedure. As described earlier, route accumulation is used to construct routes, by recording the IP addresses of a route's nodes in the IERP packet or local cache. The Detected Queries Table, extended by two columns, serves as a convenient route accumulation cache. The node begins the route accumulation procedure by adding its IP address to the IERP route. This is followed by the IP addresses of any cached nodes leading to the packet's destination (the "next hops"). This is sufficient processing for ROUTE-ACCUMULATION packets, where complete source routes are constructed. On the other hand, QUERY, QUERY-EXTENSION and QUERY-REPLY packets should carry as little of the route as possible. Therefore, if cache space is available, the route accumulation process records the IP addresses of the "previous hops" from the packet's source, and removes them from the IERP packet. The final role of the BRP is contribute to the ROUTE-OPTIMIZATION process by indicating the mutual routing zone membership of the nodes in the source route. This is done by appending a special flag field to the ROUTE-OPTIMIZATION packet. The status of the k-th bit in the flag field indicates whether the k-th hop in the source route is a member of the node's routing zone. This membership information is eventually processed at the source to determine the smallest set of routing zones that cover the route (and therefore the smallest set of nodes needed to specify this route through loose source routing.) Haas, Pearlman Expires February 1999 [Page 25] INTERNET DRAFT The Zone Routing Protocol August 1998 A. Packet Format See IERP packet format in Section 4.2 B. Structures B.1 Intrazone Routing Table (see IARP description) B.2 Detected Queries Table |--------------------|--------|-----------------------| | Query | Query | Prev | Prev | Next | | Source | Id | IERP | Hop(s) | Hop(s) | |----------+---------|--------+-----------+-----------| | | | | | | | | | | |----------+---------|--------+---+---+---|---+---+---| | | | | | | | | | | |----------+---------|--------+---+---+---|---+---+---| | | | | | | | | | | |--------------------|--------|-----------------------| | \|/ +---+ +---+ +---+ | A |-->| B |-->... | C | +---+ +---+ +---+ cached "source" route C. Interfaces C.1 Higher Layer (i.e. IERP) C.2.1 Send() (same interface as IP Send() primitive) Used by higher layer protocol to request transmission 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 February 1999 [Page 26] INTERNET DRAFT The Zone Routing Protocol August 1998 D.1 Event: A QUERY packet is received from the IERP Action: If X is the query's source, then the identifying querying information is recorded in the Detected Queries Table. X adds its IP address to the packet's route. A copy of the packet is sent to the IERP layer of each peripheral node, by way of a BRP transmission to the next hop to that peripheral node. D.2 Event: A QUERY packet is received from the IP. The hop counter has expired or the query was already detected from another bordercasting node. Action: The packet is discarded. D.3 Event: A QUERY packet is received from IP. The hop count has not expired and the query has not been previously detected (or was detected from the same bordercasting node). X is not the intended BRP recipient. Action: If cache space is available, identifying query information SHOULD be recorded in the Detected Queries Table. The packet is then discarded. D.4 Event: A QUERY packet is received from the IP. The hop count has not expired and the query has not been previously detected (or was previously detected from the same bordercasting node). X is the intended BRP recipient, but is not the intended IERP recipient and the query destination does not lie within X's routing zone. Action: The hop counter is decremented. If cache space is available, identifying query information and accumulated route information should be recorded in the Detected Queries Table. The recorded route information is removed from the packet and X adds its IP address to the route. The packet is then sent to the BRP of the next hop to the intended IERP recipient. Haas, Pearlman Expires February 1999 [Page 27] INTERNET DRAFT The Zone Routing Protocol August 1998 D.5 Event: A QUERY packet is received from the IP. The hop count has not expired and the query has not been previously detected (or was previously detected from the same bordercasting node). X is the intended BRP recipient, and either X is the intended IERP recipient, OR the query destination lies in X's routing zone. Action: The hop counter is decremented. If cache space is available, identifying query information and accumulated route information should be recorded in the Detected Queries Table. The recorded route information is removed from the packet and X adds its IP address to the route. The packet is then delivered up to the IERP. D.6 Event: A QUERY-EXTENSION is received from the IERP. Action: The packet is sent to the BRP layer of the next hop to the specified IERP recipient (in this case, the query destination). D.7 Event: A QUERY-EXTENSION is received from the IP. X is not the intended BRP recipient. Action: If cache space is available, identifying query information SHOULD be recorded in the Detected Queries Table. The packet is then discarded. D.8 Event: A QUERY-EXTENSION packet is received from the IP. X is the intended BRP recipient, but is not the intended IERP recipient. Action: If cache space is available, identifying query information and accumulated route information should be recorded in the Detected Queries Table. The recorded route information is removed from the packet and X adds its IP address to the route. The packet is then sent to the BRP of the next hop to the intended IERP recipient. Haas, Pearlman Expires February 1999 [Page 28] INTERNET DRAFT The Zone Routing Protocol August 1998 D.9 Event: A QUERY-EXTENSION packet is received from the IP. X is the intended BRP recipient and the intended IERP recipient. Action: If cache space is available, identifying query information and accumulated route information should be recorded in the Detected Queries Table. The recorded route information is removed from the packet and X adds its IP address to the route. The packet is then delivered up to the IERP. D.10 Event: A QUERY-REPLY packet is received from the IERP. Action: The IP addresses of X and the previous hops back to the query source (cached in the Detected Queries Table) are added to the route. The packet is sent back to the IERP layer of the query source, by way of a BRP layer transmission to the first hop back to the query source. D.11 Event: A QUERY-REPLY packet is received from the IP. X is not the intended BRP recipient. Action: The packet is discarded. D.12 Event: A QUERY-REPLY packet is received from the IP. X is the intended BRP recipient, but not the intended IERP recipient. Action: If cache space is available, accumulated route information to the destination should be recorded in the Detected Queries Table, and the recorded route information removed from the packet. The IP addresses of X and the previous hops back to the query source (cached in the Detected Queries Table) are added to the route. The packet is then sent to the BRP layer of the previous hop back to the query source. D.13 Event: A QUERY-REPLY packet is received from the IP. X is the intended BRP recipient and the intended IERP recipient. Action: If cache space is available, accumulated route information to the destination should be recorded in the Detected Queries Table, and the recorded route information removed from the packet. The packet is then delivered up to the IERP. Haas, Pearlman Expires February 1999 [Page 29] INTERNET DRAFT The Zone Routing Protocol August 1998 D.14 Event: A ROUTE-ACCUMULATION packet is received from the IERP. Action: The packet is sent to the IERP layer of the specified IERP recipient by way of a BRP transmission to the next hop toward the IERP recipient. D.15 Event: A ROUTE-ACCUMULATION packet is received from the IP. X is not the intended BRP recipient. Action: The packet is discarded. D.16 Event: A ROUTE-ACCUMULATION packet is received from the IP. X is the intended BRP recipient, but not the intended IERP recipient. Action: The IP addresses of X and the next hops to the intended IERP recipient (which are cached in the Detected Queries Table) are added to the route. If this packet contains a route repair and the repair has already been accumulated, then a copy of the packet is delivered to the IERP. The packet is then sent to the BRP layer of the next hop toward the IERP recipient. D.17 Event: A ROUTE-ACCUMULATION packet is received from the IP. X is the intended BRP recipient and the intended IERP recipient. Action: The packet is delivered up to the IERP. D.18 Event: A ROUTE-OPTIMIZATION packet is received from the IERP. Action: X indicates (in its flag field) those route nodes that belong to its routing zone. The packet is then sent to the IERP layer of the specified IERP recipient, by way of a BRP transmission to the next hop toward the IERP recipient. D.19 Event: A ROUTE-OPTIMIZATION packet is received from the IP. X is not the intended BRP recipient. Action: The packet is discarded. Haas, Pearlman Expires February 1999 [Page 30] INTERNET DRAFT The Zone Routing Protocol August 1998 D.20 Event: A ROUTE-OPTIMIZATION packet is received from the IP. X is the intended BRP recipient, but not the intended IERP recipient. Action: X indicates (in its flag field) those route nodes that belong to its routing zone. The packet is then sent to the IERP layer of the specified IERP recipient, by way of a BRP transmission to the next hop toward the IERP recipient. D.21 Event: A ROUTE-OPTIMIZATION packet is received from the IP. X is the intended BRP recipient and the intended IERP recipient. Action: X indicates (in its flag field) those route nodes that belong to its routing zone. The packet is then delivered up to the IERP E. Pseudocode Implementation We define two complimentary operations on packets: extract(packet) and load(packet) extract (packet) extracts the fields of the IERP packet to the following variables: {type, hops_left, query_id, bad_link_source, next_IERP, next_BRP, prev_IERP, route, flag} load (packet) loads the values of the aforementioned variables into the fields of the IERP packet. E.1 Receive Packet from IERP extract (packet) source = route(0) dest = route(length(route)-1) current_hop_ptr = get_index(route, my_id) prev_hops = reverse(route(0: current_hop_ptr-1)) next_hops = route(current_hop_ptr+1 : length(route)-1) IERP_prev = my_id Haas, Pearlman Expires February 1999 [Page 31] INTERNET DRAFT The Zone Routing Protocol August 1998 switch(type) { case: QUERY if ((bad_link_source == my_id || source == my_id) add(Detected_Queries,packet) for (IERP_next = each host in Intrazone_Routing_Table) { if (IERP next is a peripheral node) { BRP_next=Intrazone_Routing_Table[host,0]->next_hop load(pk_copy) send(pk_copy,BRP_next) } } break case: QUERY-EXTENSION BRP_next=Intrazone_Routing_Table[IERP_next,0]->next_hop load(packet) send(packet,BRP_next) break case: QUERY-REPLY if (prev_hops(0) == source) prev_hops = Detected_Queries[source,query_id] ->prev_hops route = prev_hops + my_id + next_hops BRP_next = prev_hops(0) load(packet) send(packet,BRP_next) break case: ROUTE-ACCUMULATION if(my_id == source) BRP_next = next_hops(0) if(my_id == dest) BRP_next = prev_hops(0) load(packet) send(packet,BRP_next) break case: ROUTE-OPTIMIZATION flag = NULL for (i = 0 to length(route)-1) { if ((EXISTS) Intrazone_Routing_Table[route(i)]) flag = flag,1 else flag = flag,0 } if(my_id == source) BRP_next = next_hops(0) if(my_id == dest) BRP_next = prev_hops(0) load(packet) send(packet,BRP_next) break Haas, Pearlman Expires February 1999 [Page 32] INTERNET DRAFT The Zone Routing Protocol August 1998 E.2 Receive Packet from IP extract(packet) source = route(0) dest = route(length(route)-1) current_hop_ptr = get_index(route, my_id) prev_hops = reverse(route(0: current_hop_ptr-1)) next_hops = route(current_hop_ptr+1 : length(route)-1) switch(type) { case QUERY: if (hops_left > 0 && (!EXISTS(Detected_Queries[source,query_id] || Detected_Queries[source,query_id]->from == IERP_prev)) { hops_left -- if (!FULL (Detected_Queries)) { add(Detected_Queries, packet) prev_hops = source } else route = prev_hops + my_id + next_hops if(BRP_next == my_id) { if(IERP_next == my_id || dest (EXISTS IN) Intrazone_Routing_Table) deliver(packet,IERP) else { BRP_next=Intrazone_Routing_Table[IERP_next] ->route(0)->next_hop load(packet) send(packet, BRP_next) } } else discard(packet) } else discard(packet) break Haas, Pearlman Expires February 1999 [Page 33] INTERNET DRAFT The Zone Routing Protocol August 1998 case QUERY-EXTENSION: { if (!FULL (Detected_Queries)) { add(Detected_Queries,packet) prev_hops = source } route = prev_hops + my_id + next_hops if(BRP_next == my_id) { if(IERP_next == my_id || dest (EXISTS IN) Intrazone_Routing_Table) deliver(packet,IERP) else { BRP_next=Intrazone_Routing_Table[IERP_next] ->route(0)->next_hop load(packet) send(packet, BRP_next) } } else discard(packet) } else discard(packet) break case QUERY-REPLY: if(my_id == BRP_next) { if (!FULL (Detected_Queries)) { add(Detected_Queries, packet) next_hops = dest } if (prev_hops(0) == source) prev_hops = Detected_Queries[source,query_id] ->prev_hops route = prev_hops + my_id + next_hops if(my_id == IERP_next) deliver(packet,IERP) else { BRP_next = prev_hops(0) load(packet) send(packet,BRP_next) } } else discard(packet) break Haas, Pearlman Expires February 1999 [Page 34] INTERNET DRAFT The Zone Routing Protocol August 1998 case ROUTE-ACCUMULATION: if(my_id == BRP_next) { if(my_id == IERP_next) deliver(packet, IERP) else { if (bad_link_source && IERP_next == source) { bad_link_ptr=get_index(route,bad_link_source) if (current_hop_ptr <= bad_link_ptr) deliver(packet, IERP) } if (IERP_next == dest) { if(next_hops(0) == dest) next_hops=Detected_Queries[source,query_id] ->next_hops BRP_next = next_hops(0) } if (IERP_next == source) { if(prev_hops(0) == source) prev_hops=Detected_Queries[source,query_id] ->prev_hops BRP_next = prev_hops(0) } route = prev_hops + my_id + next_hops load(packet) send (packet,BRP_next) } } else discard(packet) break Haas, Pearlman Expires February 1999 [Page 35] INTERNET DRAFT The Zone Routing Protocol August 1998 case ROUTE-OPTIMIZATION: if(my_id == BRP_next) { f = NULL for (i = 0: length(route)-1) { if ((EXISTS) Intrazone_Routing_Table[route(i)]) f = f,1 else f = f,0 } if (IERP_next == source) flag = f , flag else flag = flag , f if(my_id == IERP_next) deliver(packet, IERP) else { if(IERP_next == source) BRP_next = prev_hops(0) else BRP_next = next_hops(0) load(packet) send (packet,BRP_next) } } else discard(packet) break Haas, Pearlman Expires February 1999 [Page 36] INTERNET DRAFT The Zone Routing Protocol August 1998 5. Other Considerations 5.1 Sizing the Zone Radius The performance of the Zone Routing Protocol is determined by the routing zone radius. In general, dense networks consisting of a few fast moving nodes favor smaller routing zones. On the other hand, a sparse network of many slowly moving nodes operates more efficiently with a larger zone radius. The simplest approach to configuring the routing zone radius is to make the assignment once, prior to deploying the network. This can be performed by the network administration, if one exists, or by the manufacturer, as a default value. This may provide acceptable performance, especially in situations where network characteristics do not vary greatly over space and time. Alternatively, the ZRP can adpat to changes in network behavior, through dynamnic configuration of the zone radius [Haas-3]. In [Haas-4], it was shown that a node can accurately estimate its optimal zone radius, on-line, based on local measurements of ZRP traffic. The re-sizing of the routing zone can be carried out by a protocol that conveys the change in zone radius to the members of the routing zone. The details of such an update protocol will be provided in a future version of this draft. Haas, Pearlman Expires February 1999 [Page 37] INTERNET DRAFT The Zone Routing Protocol August 1998 6.0 References [AODV] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing", MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997 [Haas-1] 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., "The Performance of Query Control Schemes for the Zone Routing Protocol," SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998. [Haas-3] Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design Choices in Ad-Hoc Communications", MILCOM'98, Boston, MA, October 18-21, 1998. [Haas-4] Haas, Z.J. and Pearlman, M.R., "Determining the Optimal Configuration for the Zone Routing Protocol", submitted for journal publication. [Johnson] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc Wireless Networks," in Mobile Computing, edited by T. Imielinski and H. Korth, chapter 5, pp. 153-181, Kluwer, 1996. [Murthy] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient Routing Protocol for Wireless Networks", MONET, vol. 1, no. 2, pp. 183-197, October 1996. [Park] Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," IEEE INFOCOM'97, Kobe, Japan, 1997. [Perkins] Perkins, C.E., and Bhagwat, P., "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers",ACM SIGCOMM, vol.24, no.4, October 1994. [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. Haas, Pearlman Expires February 1999 [Page 38] INTERNET DRAFT The Zone Routing Protocol August 1998 Authors' Information Zygmunt J. Haas Wireless Networks Laboratory 323 Frank Rhodes Hall School of Electrical Engineering Cornell University Ithaca, NY 14853 United States of America tel: (607) 255-3454, fax: (607) 255-9072 Email: haas@acm.org or haas@ee.cornell.edu Marc R. Pearlman 319 Frank Rhodes Hall School of Electrical Engineering Cornell University Ithaca, NY 14853 United States of America Email: pearlman@ee.cornell.edu The MANET Working Group contacted through its chairs: M. Scott Corson Institute for Systems Research University of Maryland College Park, MD 20742 (301) 405-6630 corson@isr.umd.edu Joseph Macker Information Technology Division Naval Research Laboratory Washington, DC 20375 (202) 767-2001 macker@itd.nrl.navy.mil Haas, Pearlman Expires February 1999 [Page 39] INTERNET DRAFT The Zone Routing Protocol August 1998