INTERNET-DRAFT Zygmunt J. Haas, Cornell University Marc R. Pearlman, Cornell University Expires in six months on September 2000 March 2000 The Zone Routing Protocol (ZRP) for Ad Hoc Networks Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Distribution of this memo is unlimited. Abstract This document describes the Zone Routing Protocol (ZRP), a hybrid routing protocol suitable for a wide variety of mobile ad-hoc networks, especially those with large network spans and diverse mobility patterns. Each node proactively maintains routes within a local region (referred to as the routing zone). Knowledge of the routing zone topology is leveraged by the ZRP to improve the efficiency of a reactive route query/reply mechanism. The proactive maintenance of routing zones also helps improve the quality of discovered routes, by making them more robust to changes in network topology. The ZRP can be configured for a particular network by proper selection of a single parameter, the routing zone radius. Haas, Pearlman Expires September 2000 [Page i] INTERNET DRAFT The Zone Routing Protocol March 2000 Contents Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i Applicability Statement . . . . . . . . . . . . . . . . . . . iii A. Networking Context . . . . . . . . . . . . . . . . . iii B. Protocol Characteristics and Mechanisms . . . . . . . iii 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 2. Overview of the Zone Routing Protocol . . . . . . . . . . . 2 2.1 Routing Zones, Extended Routing Zones, and the Intrazone Routing Protocol (IARP) . . . . . . 2 2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 3 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 . . . . . . . . . . . . . . . 6 3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 7 4. Implementation Details . . . . . . . . . . . . . . . . . . 8 4.1 Intrazone Routing Protocol (IARP) -- Link State . . . 8 A. Packet Format . . . . . . . . . . . . . . . . . . 9 B. Data Structures . . . . . . . . . . . . . . . . . 10 C. Interfaces . . . . . . . . . . . . . . . . . . . . 12 D. State Machine . . . . . . . . . . . . . . . . . . 13 E. Pseudocode Implementation . . . . . . . . . . . . 14 4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 18 A. Packet Format . . . . . . . . . . . . . . . . . . 19 B. Data Structures . . . . . . . . . . . . . . . . . 22 C. Interfaces . . . . . . . . . . . . . . . . . . . . 23 D. State Machine . . . . . . . . . . . . . . . . . . 23 E. Pseudocode Implementation . . . . . . . . . . . . 25 4.3 Bordercast Resolution Protocol (BRP) . . . . . . . . . 30 A. Packet Format . . . . . . . . . . . . . . . . . . 30 B. Data Structures . . . . . . . . . . . . . . . . . 31 C. Interfaces . . . . . . . . . . . . . . . . . . . . 32 D. State Machine . . . . . . . . . . . . . . . . . . 32 E. Pseudocode Implementations . . . . . . . . . . . . 34 5. Other Considerations . . . . . . . . . . . . . . . . . . . 37 5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 37 5.2 Hierarchical Routing and the ZRP . . . . . . . . . . . 37 6. References . . . . . . . . . . . . . . . . . . . . . . . . 39 7. Draft Modifications . . . . . . . . . . . . . . . . . . . . 40 Authors' Information . . . . . . . . . . . . . . . . . . . . . 41 MANET Contact Information . . . . . . . . . . . . . . . . . . . 41 Haas, Pearlman Expires September 2000 [Page ii] INTERNET DRAFT The Zone Routing Protocol March 2000 Applicability Statement A. Networking Context The hybrid Zone Routing Protocol (ZRP) can adapt to a wide variety of network scenarios by adjusting the range of the nodes' proactively maintained routing zones. Large routing zones are preferred when demand for routes is high and/or the network consists of many slowly moving nodes. In the extreme case of a network with fixed topology, the ideal routing zone radius would be infinitely large. (Consider the purely proactive routing protocols used on the fixed Internet). On the other hand, smaller routing zones are appropriate in situations where route demand is low and/or the network consists of a small number of nodes that move fast relative to one another. In the "worst case", a routing zone radius of one hop is best, and the ZRP defaults to a traditional reactive flooding protocol. When the ZRP is properly configured for a particular network scenario, it can perform at least as well as (and often better than) its purely proactive and reactive constituent protocols. In situations where the network behavior varies across different regions, the ZRP performance can be fine-tuned by individual adjustment of each node's routing zone. The global reactive component of the ZRP uses the multicast based "bordercast" mechanism to propagate route queries throughout the network, rather than relying on neighbor-broadcast flooding found in tradtional reactive protocols. Consequently, the ZRP provides the most benefit in networks where reliable neighbor broadcasting is either inefficient or altogether impossible. In particular, the ZRP is well suited for multi-channel, multi-technology routing fabrics and networks operating under high load. B. Protocol Characteristics and Mechanisms * Does the protocol provide support for unidirectional links? (if so, how?) Yes. The ZRP provides "local" support for unidirectional links. A unidirectional link can be used as long as the link source and link destination lie within each other's routing zone. * Does the protocol require the use of tunneling? (if so, how?) No. * Does the protocol require using some form of source routing? (if so, how?) No. The ZRP's framework supports global route discovery based on source routing, distributed distance vectors, or various combinations of both. Haas, Pearlman Expires September 2000 [Page iii] INTERNET DRAFT The Zone Routing Protocol March 2000 * Does the protocol require the use of periodic messaging? (if so, how?) Yes. The ZRP proactively maintains local routing information (routing zones) based on periodic exchanges of neighbor discovery messages. * Does the protocol require the use of reliable or sequenced packet delivery? (if so, how?) The ZRP only assumes that link-layer (neighbor) unicasts are delivered reliably and in-sequence. Reliable and sequenced delivery of neighbor broadcasts and IP unicasts is not required. * Does the protocol provide support for routing through a multi- technology routing fabric? (if so, how?) Yes. It is assumed that each node's network interface is assigned a unique IP address. * Does the protocol provide support for multiple hosts per router? (if so, how?) Yes. Multiple hosts may be associated with a router. These hosts can be identified by the neighbor discovery/maintenance process. By default, it is assumed that a host's association with a router is not permanent. As a result, the ZRP exchanges routing information for individual hosts in the same manner as routing information for routers. In cases where a router is permanently associated with a network (subnetwork), the ZRP supports the exchange of network (subnetwork) prefixes in place of all aggregated host IP addresses. * Does the protocol support the IP addressing architecture? (if so, how?) Yes. Each node is assumed to have a unique IP address (or set of unique IP addresses in the case of multiple interfaces). The ZRP references all nodes/interfaces by their IP address. This version of the ZRP also supports IP network addressing (network prefixes) for routers that provide access to a network of non-router hosts. Haas, Pearlman Expires September 2000 [Page iv] INTERNET DRAFT The Zone Routing Protocol March 2000 * Does the protocol require link or neighbor status sensing (if so, how?) Yes. The ZRP proactively maintains local routing information (routing zones) based on detected changes in neighbor status. * Does the protocol have dependence on a central entity? (if so, how?) No. The ZRP is a fully distributed protocol. * Does the protocol function reactively? (if so, how?) Yes. The ZRP's GLOBAL route discovery mechanism is reactive. A route query is initiated, on demand, when a node requires routing information that is not immediately available in its routing table. The route query propagates through the network, using a special packet delivery service called "bordercasting". Bordercasting leverages knowledge of local network topology to direct route queries away from the source, thereby reducing redundancy. * Does the protocol function proactively? (if so, how?) Yes. The ZRP proactively maintains LOCAL routing information (routing zones) for each node. The routing zone information is leveraged, through the bordercasting mechanism, to support efficient global propagation of route queries. * Does the protocol provide loop-free routing? (if so, how?) Yes. In this draft, loop-freedom in the reactive route discovery process is ensured by inspection of accumulated source routes. For distributed distance vector approaches, loop-freedom can be ensured by labeling queries (replies) with the source (destination) address and locally unique sequence number. Nodes that relay these messages can temporarily cache these identifiers in order to identify and terminate loops. The ZRP's Link State proactive protocol is inherently loop-free, although temporary loops may form while new link state updates propagate through the routing zone. * Does the protocol provide for sleep period operation? (if so, how?) No. * Does the protocol provide some form of security? (if so, how?) No. It is assumed that security issues are adequately addressed by the underlying protocols (IPsec, for example). Haas, Pearlman Expires September 2000 [Page v] INTERNET DRAFT The Zone Routing Protocol March 2000 * Does the protocol provide support for utilizing multi-channel, link-layer technologies? (if so, how?) Yes. It is assumed that each node's network interface is assigned a unique IP address. Haas, Pearlman Expires September 2000 [Page vi] INTERNET DRAFT The Zone Routing Protocol March 2000 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. Examples of proactive routing protocols include the Wireless Routing Protocol (WRP) [7] and Destination-Sequenced Distance-Vector (DSDV) routing [11]. 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 other examples of reactive (also called on-demand) ad hoc network routing protocols are Dynamic Source Routing (DSR)[5], Ad-hoc On demand Distance Vector Routing (AODV) [12] and the Temporally Ordered Routing Algorithm (TORA) [8]. 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)" ([1], [2],[9]), is an example of a such a hybrid proactive/ reactive scheme. Haas, Pearlman Expires September 2000 [Page 1] INTERNET DRAFT The Zone Routing Protocol March 2000 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. Globally 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 Routing Zones, Extended Routing Zones, 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 no greater than some parameter 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 | | Routing Zone of +---+ | +---+ | +---+ +---+ | node A | +---+ ---| B |-------| | (radius = 2 hops) | | 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 hops. 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. Haas, Pearlman Expires September 2000 [Page 2] INTERNET DRAFT The Zone Routing Protocol March 2000 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 IP multicast (Distance Vector Multicast Routing Protocol (DVMRP) [14]) to the peripheral nodes. However, as will be explained later, efficient ZRP operation requires that the bordercast service be handled, on a hop-by-hop basis, by the ZRP. In its basic form, the ZRP's Intrazone Routing Protocol (IARP) is responsible for providing each node with current view of its routing zone topology. With this information, a node can identify ITS peripheral nodes AND construct a bordercast (multicast) tree to them. However, in order for the bordercast to be carried out, member of the bordercast tree needs to know the tree's downstream structure. This can be achieved if each node tracks the routing zone topology of each of ITS interior routing zone members. This "extended" routing zone consists of all nodes that are at a minimum distance (in hops) LESS THAN twice the "basic" routing zone radius. The IARP may be derived from a variety of existing globally proactive protocols that provide a complete view of network connectivity (for example, the Shortest Path First OSPF [6]). The base protocol needs to be modified to ensure that the scope of the route updates is restricted to the radius of a node's extended 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. * The IERP relies on a special sub-protocol, called the Bordercast Resolution Protocol (BRP) to provide the bordercast message delivery service for route queries. Sections 3.0 and 4.0 describe in detail the relationship between the BRP and the IERP. Haas, Pearlman Expires September 2000 [Page 3] INTERNET DRAFT The Zone Routing Protocol March 2000 2.2.1 Routing Zone Based Route Discovery We illustrate the basic operation of routing zone based route discovery through a simple (and as we will see, inefficient) IERP implementation. The source node, in need of a route to a destination node, first checks whether the destination lies within its routing zone. (This is possible since every node knows the content of its routing zone). If a path to the destination is known, no further route discovery processing is required. On the other hand, if the destination is not within the source's routing zone, the source bordercasts a route query to all of its peripheral nodes. Upon receipt of the route query, each peripheral nodes executes the same algorithm. If the destination lies within its routing zone, a route reply is sent back to the source, indicating the route to the destination. If not, this node forwards the query to ITS peripheral nodes. This process continues until the query has spread throughout the network. +---+ +---+ | F | +---+---| C |----+---+-----+---+ +---+ | D | +---+ | E |----| H | +---+ | +---+-----+---+ +---+ +---+----| B | | | A | +---+-----+---+ +---+ +---+ | G | | I | +---+ +---+ | +---+ +---+ | J | | C |----+---+----+---+ +---+ +---+ | K |----| L | +---+ +---+ In the example illustrated above, node A has a datagram to send to node L. Assuming each node's zone radius is 2 hops, node L does not lie within A's routing zone (which does include B,C,D,E,F,G). Therefore, 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. Haas, Pearlman Expires September 2000 [Page 4] INTERNET DRAFT The Zone Routing Protocol March 2000 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, the route reply can be returned via strict source routing. In order to reduce the length of query packets and query response time, the query packet's accumulated route can be cached among the path's nodes (in the form of the previous hop toward the query source), rather than explicitly recorded in the packet itself. During the reply phase, the cached previous hops can direct the reply back to the source. Along the way, information can be accumulated in the reply packet, forming a source route. Alternatively, the discovered route may be distributed among its nodes' routing tables, providing a next hop routing solution. Sending replies along the (reversed) paths explicitly traveled by the successful query packets can result in a set of discovered routes that exhibit limited diversity among. This anomalous behavior can be explained as follows. Variations in packet forwarding delay often result in one query packet reaching the destination region ahead of others. The descendents of this query packet trigger the majority of route replies. The route diversity problem is aggravated when all possible paths between the source and destination pass through a common node, called a topological bottleneck. Since only one query packet passes through the bottleneck, all discovered routes will be identical prior to the topological bottleneck. This problem could be addressed by allowing a node to relay a route query more than once. Alternatively, we can apply "diversity injection" [10] to increase diversity without generating additional route replies. During the route query stage, nodes temporarily cache the previous hop information for ALL received query packets (including the packets that are discarded). Later, during the reply phase, replies are relayed through the shortest of the least selected cached paths that does not produce a routing loop. Haas, Pearlman Expires September 2000 [Page 5] INTERNET DRAFT The Zone Routing Protocol March 2000 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 terminate a bordercasted packet before it arrives at a recipient peripheral node lying in a previously queried region of the network. The ZRP's ability to provide this level of query control capability is significantly limited when bordercast messages are forwarded to peripheral nodes by IP. To prevent redundant querying, nodes should be able to detect when routing zones that they belong to have been queried. Clearly, a node that bordercasts a route query is aware that its own zone has been queried. If bordercast messages are relayed by IP, then the query will not be detected again until it reappears at the target peripheral nodes. On the other hand, if bordercast forwarding is performed within the routing protocol, then all nodes in the bordercast tree will detect the query. Additional query detection is possible in shared channel networks if the underlying IP delivery is neighbor broadcast or if promiscuous mode operation is enabled. In this case, nodes may "overhear" a query even if they do not belong to the bordercast tree. Standard flood search protocols terminate query packets that are targeted for (or arrive at) previously queried nodes. We can extend this idea to the ZRP by discarding route queries before they arrive at bordercast recipients that belong to a previously queried routing zone. More precisely, a node will not relay a packet down a branch of the bordercast tree if each of the branch's downstream "leaves" (bordercast recipients) either lies inside the routing zone of a previous bordercasted nodes, or if this node has already relayed the query to that leaf. This scheme, which we refer to as Early Termination (ET), relies on the aforementioned Query Detection to identify which routing zone nodes have already bordercast a query. The "extended" routing zone maintained by the IARP is then used to determine the members of these previously bordercasted nodes' routing zones. 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 Routing Table). Haas, Pearlman Expires September 2000 [Page 6] INTERNET DRAFT The Zone Routing Protocol March 2000 Upon local detection of a route failure, a node may choose to attempt a route repair by discovering a path to bypass the failed link. The repair discovery process is nearly identical to an initial route discovery. Route repairs should not be substantially longer than the original failed connection. Therefore, the depth of a repair query can be limited, through the use of a "time to live" field. 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. 3.0 The ZRP Architecture ......................................... : Z R P : : : +---------+ : +---------+ +---------+ : +---------+ | 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 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 September 2000 [Page 7] INTERNET DRAFT The Zone Routing Protocol March 2000 4. Implementation Details 4.1 The IntrAzone Routing Protocol (IARP) -- Link State Implementation The Intrazone Routing Protocol (IARP) is responsible for proactively maintaining routes within each node's routing zone. Many traditional proactive protocols can be modified to serve as an IARP by limiting the range of route updates to the boundary of (extended) routing zones. In this draft, we detail implementations for a Link-State IARP. Nodes compute intrazone routes based on the link state (neighbor connectivity) of each extended routing zone node. A node may receive link state updates either from an IARP link state packet or from an interrupt generated by its Neighbor Discovery / Maintenance (NDM) process*. Link states are maintained in a Link State Table. When all pending link state updates have been received (full link state updates may contain multiple links and span multiple packets), the routing table is recomputed, using a minimum spanning tree algorithm. The Link State Table is then updated to remove links that lie outside of the extended routing zone. All new link state updates for non- peripheral routing zone nodes are forwarded to all neighbors. In addition, if a new neighbor is discovered, the new neighbor is sent the FULL link states of all non-peripheral routing zone nodes. In addition to computing routes to all nodes in the extended routing zone, the IARP also uses the extended zone topology to construct the bordercast tree of each routing zone member. A node's bordercast tree can be constructed by first determining the minimum spanning tree for its routing zone, and then pruning interior node leaves. For each bordercast tree, the node should record if it's a member, and if so, its downstream neighbors and peripheral nodes. * the IARP relies on the services of a separate protocol (referred to here as the Neighbor Discovery/Maintenance Protocol) to provide current information about a node's neighbors. At the least, this information must include the IP addresses of all the neighbors. The IARP can be readily configured to support supplemental link quality metrics. Haas, Pearlman Expires September 2000 [Page 8] INTERNET DRAFT The Zone Routing Protocol March 2000 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Source Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Packet Source Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link State ID | Zone Radius | Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Destination Subnet Mask (Optional) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- | RESERVED | Metric Type | Metric Value | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | RESERVED | Metric Type | Metric Value | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Link \| |/ Metrics \ / | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | RESERVED | Metric Type | Metric Value | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- Field Description: * Link Source Address (node_id) (32 bits) IP address of the reported link's source node. * Link Destination Address (node_id) (32 bits) IP address of the reported link's destination node. * Packet Source Address (node_id) (32 bits) IP address of the node that sent this packet. (Used to account for any outstanding link state information) * Link State ID (unsigned int) (16 bits) Sequence number used to track the link state history of the Link Source node. * Zone Radius (unsigned int) (8 bits) Routing zone radius of the link's source node. Determines the extent that link state information propagates. * Flags (boolean) (8 bits) Flags(0) Full Link Information Indicates whether this link state information was sent as: (0) a PARTIAL link state update OR (1) part of a FULL update of all the link source's current links Haas, Pearlman Expires September 2000 [Page 9] INTERNET DRAFT The Zone Routing Protocol March 2000 Flags(1) Current Link State Update Indicates whether more link state information is pending for THIS link state update {link_source,state_id} (0) INCOMPLETE (1) COMPLETE Flags(2) All Link State Updates Indicates whether more link state updates are pending (0) INCOMPLETE (1) COMPLETE Flags(3) Link Destination Subnet Mask (0) INCLUDED (1) NOT INCLUDED Flags(4) Link Status (0) DOWN (1) UP Flags(5..7) RESERVED for future use. * Node/Link Metrics (metric) (X * 32 bits) This section of the packet is used to report the quality of this link (or link source node). * Metric Type (char) (8 bits) Type of metric being reported (based on pre-defined metric types) * Metric Value (unsigned int) (16 bits) Value of node / link metric specified by Metric Type B. Data Structures B.1 Routing Table +-----------------------|--------------------------------+-----------+ | Dest | Subnet | Routes | Route | Intrazone | | Addr | Mask | | Metrics | | | (node_id) | (node_id) | (node_id list) | (metric list) | (boolean) | |-----------+-----------|----------------+---------------+-----------+ | | | | | | |-----------+-----------|----------------+---------------+-----------+ | | | | | | |-----------+-----------|----------------+---------------+-----------+ | | | | | | +-----------------------|--------------------------------------------+ Haas, Pearlman Expires September 2000 [Page 10] INTERNET DRAFT The Zone Routing Protocol March 2000 B.2 Link State Table +-----------|--------+-------+------------------+ | Link | Zone | Link | Link State | | Source | Radius | State | Information # | | Addr | | ID | | | (node_id) | (int) | (int) | (ls_info list)## | +-----------|--------+-------+------------------| | | | | | | | |-------+------------------| | | | | | | | |-------+------------------| | | | | | |-----------|--------+-------+------------------| | | | | | |-----------|--------+-------+------------------| | | | | | | | |-------+------------------| | | | | | +-----------|-----------------------------------+ # The first link state entry for each link source contains the complete link state information corresponding to the Link State ID. Subsequent entries contain only changes of a single link state. A FULL link state entry of link state #k and a PARTIAL entry of link state #(k+1) can be merged into a FULL link state entry of link state #(k+1) ## detail of (ls_info) data type +---+---|---|---+ | | ||||| | +---+---|---|---+ (a) (b) (c) (d) (a) Link Destination Address (b) Link Destination Subnet Mask (c) Link Metrics (d) Forward Flag ( indicates if link state information has been forwarded) Haas, Pearlman Expires September 2000 [Page 11] INTERNET DRAFT The Zone Routing Protocol March 2000 B.3 Bordercast Tree Table +-----------|-----------+----------------+----------------+ | | | Downstream | Downstream | | Node | Member | Neighbors | Peripheral | | | | | Nodes | | (node_id) | (boolean) | (node_id list) | (node_id list) | +-----------|-----------+----------------+----------------| | | | | | +-----------|-----------+----------------+----------------| | | | | | +-----------|-----------+----------------+----------------| | | | | | +-----------|---------------------------------------------+ B.4 Pending Link State List (list of neighbors in the process of sending link state updates) +----------+ +----------+ +----------+ | | ---> | | . . . | | (node_id list) +----------+ +----------+ +----------+ B.5 New Neighbors List (list of new neighbors to receive a copy Link State Table, upon completion of updates) +----------+ +----------+ +----------+ | | ---> | | . . . | | (node_id list) +----------+ +----------+ +----------+ B.6 Former Routing Zone Nodes (list of routing zone nodes, prior to routing table updates) +----------+ +----------+ +----------+ | | ---> | | . . . | | (node_id list) +----------+ +----------+ +----------+ 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) Haas, Pearlman Expires September 2000 [Page 12] INTERNET DRAFT The Zone Routing Protocol March 2000 C.3 NDM C.3.1 Neighbor_Lost(node,mask,metric) Used by the NDM to notify the IARP that direct contact has been lost with "node" (with subnet mask "mask"). Any node/link quality measurements are reported in the "metric" list. C.3.2 Neighbor_Found(node,mask,metric) Used by the NDM to notify the IARP that direct contact has been confirmed with "node" (with subnet mask "mask"). Any node/link quality measurements are reported in the "metric" list. C.4 IERP C.4.1 Zone_Node_Lost(node) Used by IARP to notify the IERP that a node no longer exists within the routing zone. D. State Machine The IARP protocol consists of only one state (IDLE). Therefore, no state transitions need to be specified. The IARP immediately acts upon an event and then returns back to the IDLE state. Notes: 1) X is used as a label for the node running this state machine. D.1 Event: An IARP link state packet is received. Action: The link state update is recorded in the Link State Table. If more link state updates are pending, then the IARP returns to an idle state. Otherwise, X rebuilds its routing table and the bordercast trees of its routing zone nodes. Links that lie outside of the routing zone are removed from the Link State Table. X sends its neighbors all previously unforwarded link state updates from its NON- peripheral nodes. Finally, all neighbors in the New Neighbor List are sent the link states of X's NON- peripheral nodes, and the New Neighbor List is cleared. Haas, Pearlman Expires September 2000 [Page 13] INTERNET DRAFT The Zone Routing Protocol March 2000 D.2 Event: A "Neighbor Found" interrupt is received, indicating the discovery of a neighbor N. Action: X's new link to N is recorded in the Link State Table and N is added to the New Neighbors List. If more link state updates are pending, then the IARP returns to an idle state. Otherwise, X rebuilds its routing table and the bordercast trees of its routing zone nodes. Links that lie outside of the routing zone are removed from the Link State Table. X sends its neighbors all previously unforwarded link state updates from its NON-peripheral nodes. Finally, all neighbors in the New Neighbor List are sent the link states of X's NON-peripheral nodes, and the New Neighbor List is cleared. D.3 Event: A "Neighbor Lost" interrupt is received, indicating that node N is no longer a neighbor of X. Action: The lost link to neighbor N is removed from the Link State Table and N is removed from the New Neighbor List. If more link state updates are pending, then the IARP returns to an idle state. Otherwise, X rebuilds its routing table and the bordercast trees of its routing zone nodes. Links that lie outside of the routing zone are removed from the Link State Table. X sends its neighbors all previously unforwarded link state updates from its NON- peripheral nodes. Finally, all neighbors in the New Neighbor List are sent the link states of X's NON- peripheral nodes, and the New Neighbor List is cleared. E. Pseudocode Implementation We define two complimentary operations on packets: extract(packet) and load(packet) extract (packet) extracts the fields of the IARP packet to the following variables: {link_source, link_dest, pk_source, state_id, radius, flags, mask, link_metric} * full_link_state -> flag(0) * current_update -> flag(1) * all_updates -> flag(2) * mask -> flag(3) * link_status -> flag(4) load (packet) loads the values of the aforementioned variables into the fields of the IARP packet. Haas, Pearlman Expires September 2000 [Page 14] INTERNET DRAFT The Zone Routing Protocol March 2000 E.1 Update Intrazone Routing Table args: (packet, link_dest, mask, link_metric) // IARP may be triggered by either a link state packet update // or an interrupt from the NDP if (packet) { extract(packet); my_link_changed = FALSE; } else { link_source = MY_ID; pk_source = MY_ID; state_id = MY_LINK_STATE_ID; radius = MY_ROUTING_ZONE_RADIUS; full_link_state = 0; current_update = COMPLETE; all_updates = COMPLETE; if (type(intrpt) == "Neighbor Found") link_status = UP; else link_status = DOWN; my_link_changed = TRUE; } // Record link state information in Link State Table add(Pending_Link_State_List, pk_source_id); status = add(Link_State_Table, link_source, link_dest, mask, radius, link_metric, state_id, flags); // Determine if received link state information is new if (status == NEW_LINK_INFO) { cum_status = UPDATE_IN_PROGRESS; if(my_link_changed) { if (link_status == UP) add(New_Neighbor_List, link_dest); else remove(New_Neighbor_List, link_dest); MY_LINK_STATE_ID++; } } // Release hold on pk_source when all link state information // from pk_source is received if(all_updates == COMPLETE) remove(Pending_Link_State_List, pk_source); Haas, Pearlman Expires September 2000 [Page 15] INTERNET DRAFT The Zone Routing Protocol March 2000 // Once all pending link state information has been received, // recompute Routing Table if(empty(Pending_Link_State_List) (AND) cum_status == UPDATE_IN_PROGRESS) { // Record former routing zone nodes in order to determine // (later) which nodes have left the routing zone for((EACH) node (BELONGING TO) Routing_Table) { if(Routing_Table[node].Intrazone) add(Former_Routing_Zone_Nodes, node); } // The Link State Table should not contain links that lie // beyond the (extended) routing zone. // The Routing Table is recomputed until all outlying links // have been removed from the Routing Table rebuild = TRUE; while (rebuild) { for((EACH) node (BELONGING TO) Routing_Table) { if(Routing_Table[node].Intrazone) delete(Routing_Table[node]); } for((EACH) node (BELONGING TO) Link_State_Table) { Routing_Table[node].route = compute_route_from_links(Link_State_Table,node); Routing_Table[node].Intrazone = TRUE; } rebuild = update(Link_State_Table); } // After recomputing the Routing Table, the bordercast trees // of the interior routing zone nodes are recomputed for ((EACH) node (BELONGING TO) Routing_Table) { if(Routing_Table[node].Intrazone) { Bordercast_Tree[node] = construct_bordercast_tree(Link_State_Table,node); } } // Broadcast all new link state information that lies // inside the extended routing zone broadcast_link_state_updates(Link_State_Table); // Send all link state information that lies inside the // extended routing zone to each new neighbor for ((EACH) node (BELONGING TO) New_Neighbor_List)) send_link_state_table(Link_State_Table, node); Haas, Pearlman Expires September 2000 [Page 16] INTERNET DRAFT The Zone Routing Protocol March 2000 clear(New_Neighbor_List); cum_status = UPDATE_COMPLETE; // Alert IERP about any lost routing zone nodes for ((EACH) node (BELONGING TO) Former_Routing_Zone_Nodes) { if(node !(BELONGS TO) Routing_Table) Routing_Zone_Node_Lost(IERP, node); } clear(Former_Routing_Zone_Nodes); } Haas, Pearlman Expires September 2000 [Page 17] INTERNET DRAFT The Zone Routing Protocol March 2000 4.2 IntErzone Routing Protocol (IERP) The Interzone Routing Protocol (IERP) is responsible for discovering and maintaining routes to nodes which are beyond a node's routing zone. These routes are acquired, on demand, by efficiently probing the network with bordercasted route queries.* This version of the IERP extends the basic query / reply mechanism described in Section 3. A node issues a ROUTE_QUERY when a route is needed for a destination outside of its routing zone. A ROUTE_QUERY for a new route may probe the entire network. In contrast, a route repair will only trigger a limited depths search. A ROUTE_QUERY is guided from a node outward to its peripheral nodes, using the BRP's bordercast service (described in greater detail in Section 4.3). Because future IERP implementations may not be "routing zone aware", the BRP delivers the query up to the IERP at every hop. When the ROUTE_QUERY is received at the IERP, the previous hop node address is recorded in the Routing Table and Temporary Query Cache. The previous hop node address is then overwritten in the packet by the current node's address. If the ROUTE_QUERY destination lies within this node's routing zone, then a ROUTE_REPLY is sent to the query source and a QUERY_EXTENSION is forwarded to the query destination. Otherwise, the ROUTE_QUERY is sent back down to the BRP. The QUERY_EXTENSION performs route accumulation in distributed manner, similar to the ROUTE_QUERY. When the QUERY_EXTENSION arrives at the destination, a next hop route is formed back to the query source. As the ROUTE_REPLY proceeds back the query source, each node selects a previous hop from its Temporary Query Cache (i.e. based on diversity injection criteria) and appends the address to the packet. When the ROUTE_REPLY arrives at the query source, it contains a source route to the destination. This IERP version offers some additional features. Multiple destination route discoveries (for any OR all destinations) can be aggregated into a single ROUTE_QUERY. In addition, QOS routing is supported through the collection of various route quality metrics. * The bordercast service is provided by the Bordercast Resolution Protocol (BRP) +-----+ +-----+ +-----+ | S | . . . . | Y | . . . | D | +-----+ +-----+ +-----+ (1) search for ROUTE_QUERY route |--------------------------> (2) establish ROUTE_REPLY EXTENSION connectivity <--------------------------| |=============> Sequence of the IERP Route Discovery Stages Haas, Pearlman Expires September 2000 [Page 18] INTERNET DRAFT The Zone Routing Protocol March 2000 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 | TTL | Hop Count | Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Current Hop Ptr | Num Dests = D | Num Nodes = N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Query ID | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Query/Route Source Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- | Query/Route Destination (1) Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Query/Route Destination (2) Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | Dests \| |/ | \ / | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Query/Route Destination (D) Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- | Intermediate Node (1) Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Intermediate Node (2) Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | route(1:N) \| |/ | \ / | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | | Intermediate Node (N) Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- | Node | Metric Type |D| Metric Value | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Node | Metric Type |D| Metric Value | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Node/ | | Segment \| |/ Metrics \ / | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Node | Metric Type |D| Metric Value | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- Haas, Pearlman Expires September 2000 [Page 19] INTERNET DRAFT The Zone Routing Protocol March 2000 Field Description: * Type (char) (8 bits) Identifies the type of IERP packet. The current version of IERP contains three packet types: ROUTE_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. ROUTE_REPLY: response to a ROUTE_QUERY packet, sent from the node that discovers the Destination back to the Source. At a minimum, the ROUTE_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.) * TTL (Time to Live) (unsigned int) (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, in order to control the amount of IERP traffic generated. * Hop Count (unsigned int) (8 bits) Hop count from source to current node (ROUTE_QUERY, QUERY_EXTENSION) or hop count from source to route destination (ROUTE_REPLY, ROUTE_ACCUMULATION, ROUTE_OPTIMIZATION). * Flags (boolean) (8 bits) Flags(0) ANY destination (0) / ALL destination (1) In the case of multiple destinations, specifies whether the ROUTE_QUERY should return routes for ANY specified destination, or ALL specified destinations. In the case of a single MULTICAST IP address, specifies whether the ROUTE_QUERY should return routes to ANY member of the multicast group, or ALL members of the multicast group. Flags(1..7) RESERVED for future use Haas, Pearlman Expires September 2000 [Page 20] INTERNET DRAFT The Zone Routing Protocol March 2000 * Current Hop Pointer (unsigned int) (16 bits) INDEX of the route (see below) corresponding to the route node that has most recently received this packet. (the first node in the route has an index of 1). * Number of Destinations = D (unsigned int) (8 bits) Number of destinations included in the route query/reply packet. This allows multiple route discoveries to be consolidated into a common route query process. The multiple query destinations feature is particularly useful for routing to a multicast group with known members, or for locating downstream nodes during the route repair phase. * Number of Nodes = N (unsigned int) (8 bits) Number of nodes IP addresses appearing in the route specification. * Query ID (unsigned int) (16 bits) Sequence number which, along with the Query Source Address (see below) uniquely identifies any ROUTE_QUERY in the network. * Query/Route Source Address (node_id) (32 bits) IP address of the node that initiates the ROUTE_QUERY. In subsequent stages, this corresponds to the IP address of the discovered route's source node. * Query/Route Destination Addresses (node_id) (D * 32 bits) List of IP addresses to be located during the ROUTE_QUERY phase. (Either ANY or ALL addresses, depending on the setting of Flags(0)) In subsequent stages, this field contains the IP address of the discovered route's (single) destination node. * Route (node_id) (N * 32 bits) Variable length field that contains the recorded IP addresses of nodes along the path traveled by this ROUTE_QUERY packet from the Query Source. In subsequent stages (after a route to a Query Destination has been discovered), this set of IP addresses provides a partial specification of the route between the Route Source and Route Destination. Haas, Pearlman Expires September 2000 [Page 21] INTERNET DRAFT The Zone Routing Protocol March 2000 * Node/Segment Metrics (metric) (X * 32 bits) This optional section of the packet can be used to record a variety of node and segment quality measurements. (In this context, a segment refers to the communication path between consecutive nodes in the packet's accumulated route. In the case of neighboring nodes, a segment is equivalent to a (one-hop) link). * Node (char) (8 bits) Index of the route corresponding to a particular node. * Metric Type (char) (7 bits) Type of metric being recorded (based on pre-defined metric types) * Direction Flag (boolean) (1 bit) For segment metrics, specifies either the: upstream segment (toward Query Source) (0) downstream segment (toward Query Dest) (1) * Metric Value (unsigned int) (16 bits) Value of node / segment metric specified by Metric Type B. Data Structures B.1 Routing Table (See IARP Description) B.2 Temporary Query Cache +------------------------------------------------------+ ... | Query | Query_ID | Prev_hop | Hop Count | | Source | | | | |(node_id)|(unsigned int)|(node_id list)|(unsigned int)| |---------+--------------|--------------+--------------+ ... | | | | | |---------+--------------|--------------+--------------+ ... | | | | | |---------+--------------|--------------|--------------+ ... | | | | | +------------------------------------------------------+ ... ... +--------------+ | Injection | | Counter | |(unsigned int)| ... +--------------| | | ... +--------------| | | ... +--------------| | | ... +--------------+ Haas, Pearlman Expires September 2000 [Page 22] INTERNET DRAFT The Zone Routing Protocol March 2000 C. Interfaces C.1 Higher Layer (N/A) C.2 Lower Layer (BRP) C.2.1 Send(packet,source,query_ID,BRP_cache_ID) Used by the IERP to request packet transmission through the BRP. C.2.2 Deliver(packet,BRP_cache_ID) Used by the BRP to deliver data packet to the IERP. C.3 Lower Layer (IP) C.3.1 Send() (specified in IP standard) C.3.2 Deliver() (specified in IP standard) C.4 IARP C.4.1 Zone_Node_Lost(node) Used by the IARP to notify the IERP that a node has left the routing zone C.5 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 node running this state machine. D.1 Event: A routing zone node is reported lost by the IARP, indicating that a 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 AND Proactive Route Repair is enabled, then a route "Repair" (limited depth route discovery) to H is initiated. D.2 Event: ICMP issues a "Host_Unreachable" message, triggering a route discovery for unreachable host H. Action: A FULL depth route discovery to H is initiated. X's query_id is incremented and assigned to a new ROUTE_QUERY packet. The route is initialized with the IP addresses of the route's source and destination IP addresses (X and H). Finally, the ROUTE_QUERY packet is sent to the BRP to be bordercasted. Haas, Pearlman Expires September 2000 [Page 23] INTERNET DRAFT The Zone Routing Protocol March 2000 D.3 Event: The IERP or ICMP (via source_route_failed()) triggers a "Repair" message, indicating that the next hop H specified in a source route cannot be found locally. Action: A limited depth route discovery to H is initiated. X's query_id is incremented and assigned to a new ROUTE_QUERY packet. The route is initialized with the IP addresses of the route's source and destination IP addresses (X and H). Finally, the ROUTE_QUERY packet is sent to the BRP to be bordercasted. D.4 Event: A ROUTE_QUERY packet is received with a destination that appears within X's routing zone. Action: The packet's accumulated route information (for the source)is recorded in X's Routing Table and Temporary Query Cache. The accumulated route is replaced by X's address and any accumulated route metrics are updated and compressed. X copies the ROUTE_QUERY packet's contents to a ROUTE_REPLY. A loop-free return path is selected from the Temporary Query Cache (i.e. based on "Diversity Injection"). X also forwards a QUERY_EXTENSION to discovered query destination. If the ROUTE_QUERY packet has not traveled too deep into the network (i.e. TTL > 0) AND there are still more destinations to be discovered, then the ROUTE_QUERY is sent down to the BRP to be relayed outward. D.5 Event: A ROUTE_QUERY packet is received with a destination that DOES NOT appear within X's routing zone. Action: The packet's accumulated route information (for the source) is recorded in X's Routing Table and Temporary Query Cache. The accumulated route is replaced by X's address and any accumulated route metrics are updated and compressed. The ROUTE_QUERY packet is sent down to the BRP to be relayed outward. D.6 Event: A QUERY_EXTENSION packet is received. Action: The packet's accumulated route information (for the source) is recorded in X's Routing Table. The accumulated route is replaced by X's address and any accumulated route metrics are updated and compressed. If X is not the query destination, then X forwards the message toward the destination (directly through IP) Haas, Pearlman Expires September 2000 [Page 24] INTERNET DRAFT The Zone Routing Protocol March 2000 D.7 Event: A ROUTE_REPLY packet is received. Action: The packet's accumulated route information (for the destination) is recorded in X's Routing Table. X adds its address to the accumulated route and adds metrics for the downstream (toward the destination) link to the accumulated metrics. If X is not the query source, then X forwards the message toward the source (directly through IP), along a path selected from the Temporary Query Cache (i.e. based on Diversity Injection). E. Pseudocode Implementation We define two complimentary operations on packets: extract(packet) and load(packet) extract(packet) extracts the fields of the IERP packet to the following variables: {type, TTL, hop_count, flags, current_hop_ptr, query_id, reply_id, source, reply_node, dests, route, metric} load(packet) loads the values of the aforementioned variables into the fields of the IERP packet. load(packet) automatically computes the values of: num_dests = |dests| num_nodes = |routes| Haas, Pearlman Expires September 2000 [Page 25] INTERNET DRAFT The Zone Routing Protocol March 2000 E.1 Routing Zone Node Lost args: (lost_node) // Determine if lost_node belongs to any stored routes. // If so, the route should be removed from the // Routing Table and a route repair triggered // (if proactive route repairs are enabled) repair_link = FALSE; for((EACH) node (BELONGING TO) Routing Table) { for ((EACH) route (BELONGING TO) Routing_Table[node]) { if (lost_node (BELONGS TO) route) { if (PROACTIVE_REPAIRS_ENABLED) { removal_timer = ROUTE_QUERY_TIMEOUT; repair_link = TRUE; } else { removal_timer = 0; } schedule(remove(Routing_Table[node,route],removal_timer) } } } if(repair_link) { dests = lost_node; Initiate_Route_Discovery(IERP, {dests, ALL, REPAIR}); } E.2 Initiate Route Discovery args: (dests, flags, type) // Route query is initialized and sent down to the BRP // to be bordercasted if (type == REPAIR) TTL = MAX_REPAIR_HOPS; else TTL = MAX_FULL_QUERY_HOPS; source = MY_ID query_id = MY_QUERY_ID++; type = ROUTE_QUERY; hop_count = 0; route = NULL; current_hop_ptr = 0; load (packet); send ((packet, source, query_id, NULL), BRP); Haas, Pearlman Expires September 2000 [Page 26] INTERNET DRAFT The Zone Routing Protocol March 2000 E.3 Receive IERP Packet args: (packet, BRP_cache_ID) extract(packet); switch(type) { case: ROUTE_QUERY // Update Time-to-Live and hop count TTL--; hop_count++; // Extract route (and metrics) from packet and record // them in the Routing Table and Temporary Query Cache prev_hops = route(1 : current_hop_ptr); metrics = compress(metrics, get_metrics(prev_hops|prev_hop|,MY_ID)); add(Routing_Table[source],(reverse(prev_hops), reverse(metrics),FALSE); add(Temp_Query_Cache[source,query_id], (reverse(prev_hops),hop_count)); // Determine if routes are known for each destination find_all = flags(0); find_any = !flags(0); found_any = FALSE; found_all = TRUE; // Save current values for dests and metrics, since // we may need them later DESTS = dests; METRICS = metrics; for((EACH) dest (BELONGING TO) DESTS) { if (Routing_Table[dest].Intrazone) { // A route to this destination is known found_any = TRUE; dests = dest; remove(dest, DESTS); // Forward query directly to destination, so // that the destination will have some routing // information back to the source type = QUERY_EXTENSION; prev_hops = NULL; next_hops = Routing_Table[dest].route; route = {prev_hops,MY_ID,next_hops}; current_hop_ptr = |prev_hops|+1; load(packet); send((packet,next_hops(1)),IP); Haas, Pearlman Expires September 2000 [Page 27] INTERNET DRAFT The Zone Routing Protocol March 2000 // Send reply back to the source type = ROUTE_REPLY; reply_node = MY_ID; reply_id = MY_REPLY_ID++; next_hops = Routing_Table[dest].route; prev_hops = inject_loopfree_path(next_hops, Temp_Query_Cache[source,query_id]); metrics = NULL; route = {prev_hops,MY_ID,next_hops}; current_hop_ptr = |prev_hops|+1; load(packet); send((packet,prev_hops(|prev_hops|)),IP); } found_all = found_all && found_any; } // If more destinations need to be discovered then // forward QUERY via BRP bordercasting if(((find_all && !found_all)||(find_any && !found_any)) && TTL>0) { dests = DESTS; metrics = METRICS; prev_hops = NULL; next_hops = NULL; route = {prev_hops, MY_ID, next_hops}; current_hop_ptr = |prev_hops|+1; load(packet); send((packet,BRP_cache_ID), BRP); } break; case: QUERY_EXTENSION // Extract route (and metrics) from packet and record // them in the Routing Table prev_hops = route(1 : current_hop_ptr); next_hops = route(current_hop_ptr+1 : |route|); metrics = compress(metrics, get_metrics(prev_hops|prev_hop|,MY_ID)); add(Routing_Table[source],(reverse(prev_hops), reverse(metrics),FALSE); Haas, Pearlman Expires September 2000 [Page 28] INTERNET DRAFT The Zone Routing Protocol March 2000 // Forward query extension until it reaches destination if(MY_ID !(BELONGS TO) dests) { prev_hops = NULL; if(|next_hops|==1) { next_hops = Routing_Table[dest].route; route = {prev_hops, MY_ID, next_hops}; current_hop_ptr = |prev_hops|+1; } else { current_hop_ptr++; } load(packet); send((packet,next_hops(1)),IP); } break; case: ROUTE_REPLY // Extract route (and metrics) from packet and record // them in the Routing Table prev_hops = route(1 : current_hop_ptr-1); next_hops = route(current_hop_ptr : |route|); metrics = {metrics,get_metrics(MY_ID,next_hops(1))}; add(Routing_Table[dest],(next_hops,compress(metrics),FALSE); // Forward reply until it reaches source if(MY_ID != source) { // Choose a loopfree return path from the Temporary // Query Cache (eg. shortest path, shortest least // "injected" path, etc.) prev_hops = inject_loopfree_path(next_hops, Temp_Query_Cache[source,query_id]); route = {prev_hops, MY_ID, next_hops}; current_hop_ptr = |prev_hops|+1; load(packet); send((packet,next_hop),IP); } break; } Haas, Pearlman Expires September 2000 [Page 29] INTERNET DRAFT The Zone Routing Protocol March 2000 4.3 Bordercast Resolution Protocol (BRP) The BRP provides the "bordercasting" message delivery service, here used to forward IERP route queries. Messages are relayed from a bordercasting node outward to its peripheral nodes, along a bordercast (multicast) tree. Although the intended recipients of the bordercast are the peripheral nodes, the BRP may deliver the bordercast message up to the higher layer application (in this case, the IERP) at EVERY hop. This may be necessary for applications that use bordercasting, but are generally not "routing zone aware". When a node receives a bordercasted message, it first needs to determine whether the message should be forwarded. Clearly, the node should only forward the message if it belongs to the bordercast tree. Furthermore, if the node is the (peripheral node) bordercast recipient, it would re-bordercast the message, but only if it has not been a bordercast recipient before AND it does not lie inside the routing zone of a detected "previously bordercasted" node. If the node decides not to discard the message, it next determines which of the current bordercast tree's downstream branches will be dropped. A downstream branch will be dropped if each of the branch's downstream peripheral nodes either has had a bordercast message relayed to it by this node OR lies inside the routing zone of a detected previously bordercasted node. The BRP delivers the message up to the higher layer application (IERP). After some processing, the application may return an updated message back to the BRP. The BRP will then relay the message on the selected outgoing links. A. Packet Format +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Source Addresss | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Prev Bordercast Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | E N C A P S U L A T E D P A C K E T | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Haas, Pearlman Expires September 2000 [Page 30] INTERNET DRAFT The Zone Routing Protocol March 2000 * Message Source Address (node_id) (32 bits) IP address of the node that initiates the message. * Message ID (unsigned int) (16 bits) Sequence number which, along with the Message Source Address uniquely identifies any BRP message in the network. * Prev Bordercast Address (node_id) (32 bits) IP address of the most recent bordercasting node * Encapsulated Packet (packet) *** note: Within the context of the ZRP, the Message Source Address and Message ID can assume the same values as the corresponding "Query" fields in the encapsulated IERP packet. As such, they can be eliminated AS LONG AS: (a) The BRP has read access to the contents of the encapsulated IERP packet. (b) The BRP knows the format of the IERP packet. For this version of the ZRP, both (a) and (b) are true. However, we provide the BRP with its own Message ID and Message Source fields for future support of generic higher layer applications. B. Data Structures B.1 Routing Table (see IARP description) B.2 Bordercast Tree Table (see IARP description) Haas, Pearlman Expires September 2000 [Page 31] INTERNET DRAFT The Zone Routing Protocol March 2000 B.3 Detected Messages Cache +------------------------|--------------------------+ ... | Message | Message ID | BRP_cache_ID | Prev | | Source | | |Bordercast | |(node_id)|(unsigned int)|(unsigned int)| (node_id) | |---------+--------------|--------------+-----------+ ... | | | | | | | |--------------+-----------+ ... | | | | | |---------+--------------|--------------+-----------+ ... | | | | | | | |--------------+-----------+ ... | | | | | +------------------------|--------------+-----------+ ... ... +---------------+ | Out_neighbor | | | |(node_id list) | ... +---------------| | | ... +---------------| | | ... +---------------| | | ... +---------------| | | ... +---------------+ C. Interfaces C.1 Higher Layer (IERP) C.2.1 Send(packet, BRP_cache_ID) Used by the IERP to request packet transmission. C.2.2 Deliver(packet, BRP_cache_ID) Used by the BRP to deliver a data packet up to IERP. 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 node running this state machine. Haas, Pearlman Expires September 2000 [Page 32] INTERNET DRAFT The Zone Routing Protocol March 2000 D.1 Event: A message is received from the higher layer (IERP). BRP_cache_ID == NULL. Action: The bordercast was initiated by X. X marks itself as the previous bordercast node and relays the message to all the downstream neighbors in its bordercast tree. D.2 Event: A message is received from the higher layer (IERP). BRP_cache_ID != NULL. Action: The bordercast was not initiated by X. X looks up this message's forwarding information recorded in it's Detected Messages Cache (and referenced by BRP_cache_ID). X then relays the message to the designated downstream neighbors. D.3 Event: A message is received from the IP. Action: The message is terminated under the following conditions: (1) X does not belong to the bordercast tree of prev_bcast. (2) If X is the bordercast recipient and (a) X has already been a bordercast recipient. OR (b) X is an interior (i.e. non-peripheral) member of a detected previously bordercasted node's routing zone. If X is a bordercast recipient and does not terminate the message then it re-bordercasts the message. Next, X decides which of the current bordercast tree's downstream branches (neighbor) will be dropped. A downstream branch will be dropped if, for each of the branch's downstream peripheral node D: (a) X has already relayed a message to D. OR (b) D is an interior (i.e. non-peripheral) member of a detected previously bordercasted node's routing zone Finally, X delivers the message to the higher layer (IERP). Haas, Pearlman Expires September 2000 [Page 33] INTERNET DRAFT The Zone Routing Protocol March 2000 E. Pseudocode Implementation We define two complimentary operations on packets: extract(packet) and load(packet) extract (packet) extracts the fields of the BRP packet to the following variables: {source,message_id,prev_bordercst, message_packet) load (packet) loads the values of the aforementioned variables into the fields of the BRP packet. E.1 Receive Packet from higher layer (IERP) args: (message_packet, BRP_cache_ID) // If BRP_cache_ID == NULL then this is a new bordercast // issued by this node. This new bordercast can be relayed // to ALL downstream neighbors in the bordercast tree. // Otherwise, this is an existing bordercast that should be // forwarded to the pre-assigned downstream neighbors. if(BRP_cache_ID) { prev_bcast = Detected_Messages[source,message_id ,BRP_cache_ID].prev_bcast; out_neighbors = Detected_Message [source,message_id,BRP_cache_ID].out_neighbors; } else { prev_bcast = MY_ID; out_neighbors = Bordercast_Tree[MY_ID].downstream_neighbors; } source = MY_ID; message_id = MY_BORDERCAST_ID++; load(packet); send(packet,out_neighbors),IP); E.2 Receive Packet from IP args: (packet) extract(packet); // Discard bordercast message if this node is not a member of // prev_bcast's bordercast tree discard = !Bordercast_Tree[prev_bcast].member; Haas, Pearlman Expires September 2000 [Page 34] INTERNET DRAFT The Zone Routing Protocol March 2000 // If this node is the downstream peripheral node of // prev_bcast then terminate if this node: // (a) has already been a bordercast recipient // OR // (b) is inside the routing zone of a node that has // already bordercasted the message if(is_peripheral_node(prev_bcast,MY_ID)) { for((EACH) queried_node (BELONGING TO) Detected_Messages[source,message_id] .prev_bcast) { a = MY_ID (BELONGS TO) Bordercast_Tree[queried_node] .downstream_peripheral_nodes; b = is_interior_node(queried_node,MY_ID); discard = discard || (a || b); } // Since this node is the downstream peripheral recipient, // it will re-bordercast the message (if it isn't // terminated) prev_bcast = MY_ID; } Haas, Pearlman Expires September 2000 [Page 35] INTERNET DRAFT The Zone Routing Protocol March 2000 out_neighbors = {}; if(!discard) { // Don't relay message to a given downstream neighbor if // each covered downstream peripheral node (of prev_bcast): // (a) has already been a bordercast recipient // OR // (b) is inside the routing zone of a node that has // already bordercast the message for((EACH) neighbor (BELONGING TO) Bordercast_Tree[prev_bcast] .downstream_neighbors) { drop_neighbor = TRUE; leaves = Bordercast_Tree[prev_bcast,neighbor ].downstream_peripheral_nodes; for((EACH) leaf_node (BELONGING TO) leaves) { failed_leaf = TRUE; for((EACH) queried_node (BELONGING TO) Detected_Messages[source,message_id] .prev_bcast) { a = leaf_node (BELONGS TO) Bordercast_Tree[queried_node] .downstream_peripheral_nodes; b = is_interior_node(queried_node,leaf_node); failed_leaf = failed_leaf || (a || b); } drop_neighbor = drop_neighbor && failed_leaf; } if(!drop_neighbor) out_neighbors = {out_neighbors, neighbor}; } } // Record BRP "state" in Detected Messages Cache, so that // the message can be properly forwarded when returned by // the higher layer app (IERP) BRP_cache_ID++; add(Detected_Messages[source,message_id],(BRP_cache_ID, prev_bcast,out_neighbors)); schedule(remove(Detected_Messages[BRP_cache_ID], MAX_QUERY_LIFETIME); deliver(message_packet,BRP_cache_ID); Haas, Pearlman Expires September 2000 [Page 36] INTERNET DRAFT The Zone Routing Protocol March 2000 5. Other Considerations 5.1 Sizing the Zone Radius The performance of the Zone Routing Protocol is determined by the routing zone radius. In general, dense networks consisting of a few fast moving nodes favor smaller routing zones. On the other hand, a sparse network of many slowly moving nodes operates more efficiently with a larger zone radius. The simplest approach to configuring the routing zone radius is to make the assignment once, prior to deploying the network. This can be performed by the network administration, if one exists, or by the manufacturer, as a default value. This may provide acceptable performance, especially in situations where network characteristics do not vary greatly over space and time. Alternatively, the ZRP can adapt to changes in network behavior, through dynamic configuration of the zone radius [3]. In [9], it was shown that a node can accurately estimate its optimal zone radius, on-line, based on local measurements of ZRP traffic. The re-sizing of the routing zone can be carried out by a protocol that conveys the change in zone radius to the members of the routing zone. The details of such an update protocol will be provided in a future version of this draft. 5.2 Hierarchical Routing and the ZRP In a hierarchical network architecture, network nodes are organized into a smaller number of (often disjoint) clusters. This routing hierarchy is maintained by two component routing protocols. An intra- cluster protocol provides routes between nodes of the same cluster, while an inter-cluster protocol operates globally to provide routes between clusters. The ZRP, with its routing zones and intrazone / interzone routing protocol (IARP/IERP) architecture may give the appearance of being a hierarchical routing protocol. In actuality, the ZRP is a flat routing protocol. Each node maintains its own routing zone, which heavily overlaps with the routing zones of neighboring nodes. Because there is a one-to-one correspondence between nodes and routing zones, the routing zones, unlike hierarchical clusters, do not serve to hide the details of local network topology. As a result, the network-wide interzone routing protocol (IERP) actually determines routes between individual nodes, rather than just between higher level network entities. Haas, Pearlman Expires September 2000 [Page 37] INTERNET DRAFT The Zone Routing Protocol March 2000 For small to moderately sized networks, flat routing protocols, like the ZRP, are preferable to hierarchical routing protocols. In order for a node to be located, its address needs to reflect the node's location within the network hierarchy (i.e. {cluster id,node id}). Because of node mobility, a node's cluster membership (and thus address) is subject to change. This complicates mobility management, for the benefit of more efficient routing. In many hierarchical routing protocols, each cluster designates a single clusterhead node to relay inter-cluster traffic. These clusterhead nodes become traffic "hot-spots", potentially resulting in network congestion and single point of failure. Furthermore, restricting cluster access through clusterhead nodes can lead to sub-optimal routes, as potential neighbors in different clusters are prohibited from communicating directly. Some hierarchical routing protocols, such as the Zone-Based Hierarchical Link-State (ZHLS) [4], avoid these problems by distributing routing information to all cluster nodes, rather than maintaining a single clusterhead. In spite of these disadvantages, hierarchical routing protocols are often better suited for very large networks than flat routing protocols. Because hierarchical routing protocols provide global routes to network clusters, rather than individual nodes, routing table storage is more scalable. Similarly, the amount of route update messages is also more scalable. To some extent, the reduction in routing traffic is offset by extra mobility management overhead (i.e. identifying which cluster a node belongs to). However, it is quite common that the environment or existing organizational structure causes nodes to naturally cluster together. In these cases, there may be a high degree of intra-cluster mobility, with inter-cluster mobility is less common. A hierarchical routing protocol can be viewed as a set of flat routing protocols, each operating at different levels of granularity. In a two- tier routing protocol, the inter-cluster components is essentially a flat routing protocol that computes routes between clusters. Likewise, the intra-cluster component is a flat routing protocol, that computes routes between nodes in each cluster. For example, the Near Term Digital Radio (NTDR) System [13] and ZHLS both employ proactive link state protocols to determine inter and intracluster connectivity. In place of traditional proactive or reactive protocols, we recommend that the intra-cluster and inter-cluster routing protocol components be implemented based on the hybrid proactive/reactive ZRP. As described throughout this draft, the ZRP is designed to provide an optimal balance between purely proactive and reactive routing. This applies equally well to routing between nodes at the intra-cluster level and between clusters at the inter-cluster level. Additionally, the hybrid ZRP methodology can be applied to the related mobility management protocols, which determine complete node addresses based on a node's location in the network hierarchy. Haas, Pearlman Expires September 2000 [Page 38] INTERNET DRAFT The Zone Routing Protocol March 2000 6.0 References [1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable Wireless Networks," ICUPC'97, San Diego, CA, Oct. 12,1997. [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. [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. [4] Joa-Ng, M. and Lu, I.T., "A Peer-to-Peer Zone-based Two-Level Link State Routing for Mobile Ad-Hoc Networks," to appear in IEEE JSAC issue on Ad-Hoc Networks, June, 1999. [5] 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. [6] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, RFC 2178, July 1997. [7] 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. [8] Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," IEEE INFOCOM'97, Kobe, Japan, 1997. [9] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal Configuration for the Zone Routing Protocol," IEEE JSAC, August, 1999. [10] Pearlman, M.R. and Haas, Z.J., "Improving the Performance of of Query-Based Routing Protocols Through 'Diversity Injection'", IEEE WCNC'99, New Orleans, LA, Sept. 1999. [11] 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. [12] Perkins, C.E. and Royer, E.M., "Ad-Hoc On-Demand Distance Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 [13] Ruppe, R., Griswald, S., Walsh, P. and Martin, R., "Near Term Digital Radio (NTDR) System," IEEE MILCOM'97, Monterey, CA, Nov. 1997. [14] Waitzman, D., Partridge, C., Deering, S.E., "Distance Vector Multicast Routing Protocol," RFC 1075, Nov. 1, 1988. Haas, Pearlman Expires September 2000 [Page 39] INTERNET DRAFT The Zone Routing Protocol March 2000 7.0 Draft Updates - The sole function of the Bordercast Resolution Protocol (BRP) is to perform application independent bordercasting (all excess routing protocol functionality has been moved up to the IERP). This means that the BRP can be used outside of the ZRP, for any application that requires an efficient network-wide query/probing mechanism. Likewise, a wide variety of globally reactive routing protocols may be adopted as alternate IERPs, by substituting the query "broadcast()" with "bordercast()". In further support of application independent bordercasting, the BRP can deliver messages up to the higher layer application at every hop (as opposed to only delivering for peripheral nodes). This is important for applications that wish to use the bordercast service, but are otherwise "routing zone unaware". - The bordercast message delivery service is now implemented via multicasting, rather than a series of separate unicasts to individual peripheral nodes. The bordercast control mechanisms have been revised to support this transition. - The IARP is now required to proactively track the COMPLETE topology of an EXTENDED routing zone, consisting of all nodes that are at a minimum distance (in hops) LESS THAN twice the "basic" routing zone radius. Nodes use this extended information to construct the downstream portion of each routing zone node's bordercast (multicast) tree. Consequently, the Distance Vector IARP implementation has been dropped. - For convenience, the IARP and IERP now share a single routing table. IARP entries are indicated by a special flag. - The IERP's optional Route Accumulation and Route Optimization stages have been dropped. - The route maintenance policy has been simplified. Local route repairs are only reported to the source of the broken link, not to the route's source. - Support for "diversity injection" [10] has been added to the IERP. The diversity injection mechanism allows the global route discovery to extract more information about current network connectivity, without any additional traffic. Haas, Pearlman Expires September 2000 [Page 40] INTERNET DRAFT The Zone Routing Protocol March 2000 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@ee.cornell.edu Marc R. Pearlman 389 Frank Rhodes Hall School of Electrical Engineering Cornell University Ithaca, NY 14853 United States of America tel: (607) 255-0236, fax: (607) 255-9072 Email: pearlman@ee.cornell.edu The MANET Working Group contacted through its chairs: M. Scott Corson Institute for Systems Research University of Maryland College Park, MD 20742 (301) 405-6630 corson@isr.umd.edu Joseph Macker Information Technology Division Naval Research Laboratory Washington, DC 20375 (202) 767-2001 macker@itd.nrl.navy.mil Haas, Pearlman Expires September 2000 [Page 41]