idnits 2.17.1 draft-ietf-manet-zone-zrp-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == It seems as if not all pages are separated by form feeds - found 0 form feeds but 17 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 49 instances of too long lines in the document, the longest one being 2 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 275 has weird spacing: '...ocedure of th...' == Line 336 has weird spacing: '... An example ...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 2002) is 7956 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: '10' is defined on line 637, but no explicit reference was found in the text == Unused Reference: '20' is defined on line 675, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- No information found for draft-ietf-manet-iarp - is the name correct? -- Possible downref: Normative reference to a draft: ref. '3' -- No information found for draft-ietf-manet-ierp - is the name correct? -- Possible downref: Normative reference to a draft: ref. '4' -- No information found for draft-ietf-manet-brp - is the name correct? -- Possible downref: Normative reference to a draft: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' == Outdated reference: A later version (-11) exists of draft-ietf-manet-olsr-03 ** Downref: Normative reference to an Experimental draft: draft-ietf-manet-olsr (ref. '7') -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' ** Obsolete normative reference: RFC 2178 (ref. '10') (Obsoleted by RFC 2328) -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' -- Possible downref: Non-RFC (?) normative reference: ref. '16' -- Possible downref: Non-RFC (?) normative reference: ref. '17' -- Possible downref: Non-RFC (?) normative reference: ref. '18' -- Possible downref: Non-RFC (?) normative reference: ref. '19' ** Downref: Normative reference to an Experimental RFC: RFC 1075 (ref. '20') Summary: 9 errors (**), 0 flaws (~~), 7 warnings (==), 22 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Zygmunt J. Haas, Cornell University 2 Marc R. Pearlman, Cornell University 3 Prince Samar, Cornell University 5 Expires in six months on January 2003 July 2002 7 The Zone Routing Protocol (ZRP) for Ad Hoc Networks 8 10 Status of this Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC 2026, except the right to produce 14 derivative works is not granted. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that other 18 groups may also distribute working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference material 23 or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Distribution of this memo is unlimited. 33 Abstract 35 This document describes the Zone Routing Protocol (ZRP) framework, a 36 hybrid routing framework suitable for a wide variety of mobile ad-hoc 37 networks, especially those with large network spans and diverse 38 mobility patterns. Each node proactively maintains routes within a 39 local region (referred to as the routing zone). Knowledge of the 40 routing zone topology is leveraged by the ZRP to improve the 41 efficiency of a globally reactive route query/reply mechanism. The 42 proactive maintenance of routing zones also helps improve the quality 43 of discovered routes, by making them more robust to changes in network 44 topology. The ZRP can be configured for a particular network by proper 45 selection of a single parameter, the routing zone radius. 47 Contents 49 Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i 50 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i 52 Applicability Statement . . . . . . . . . . . . . . . . . . . iii 53 A. Networking Context . . . . . . . . . . . . . . . . . iii 54 B. Protocol Characteristics and Mechanisms . . . . . . . iii 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 58 2. Overview of the Zone Routing Framework . . . . . . . . . . . 2 59 2.1 Routing Zones and the Intrazone Routing Protocol . . . 2 61 2.2 Bordercast-Based Global Reactive (Interzone) Routing . 4 63 3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . . 5 65 4. Other Considerations . . . . . . . . . . . . . . . . . . . . 6 66 4.1 Sizing the Routing Zone . . . . . . . . . . . . . . . . 6 67 4.2 Hierarchical Routing and the ZRP . . . . . . . . . . . 6 69 5. Patent Rights Statement . . . . . . . . . . . . . . . . . . . 8 71 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 73 Authors' Information . . . . . . . . . . . . . . . . . . . . . 11 74 MANET Contact Information . . . . . . . . . . . . . . . . . . . 11 76 Applicability Statement 78 A. Networking Context 80 The hybrid Zone Routing Protocol (ZRP) framework can adapt to a wide 81 variety of network scenarios by adjusting the range of the nodes' 82 proactively maintained routing zones. Large routing zones are 83 preferred when demand for routes is high and/or the network consists 84 of many slowly moving nodes. In the extreme case of a network with 85 fixed topology, the ideal routing zone radius would be infinitely 86 large. (Consider the purely proactive routing protocols used on the 87 fixed Internet). On the other hand, smaller routing zones are 88 appropriate in situations where route demand is low and/or the 89 network consists of a small number of nodes that move fast relative 90 to one another. In the "worst case", a routing zone radius of one 91 hop is best, and the ZRP defaults to a traditional reactive flooding 92 protocol. 94 When the ZRP is properly configured for a particular network scenario, 95 it can perform at least as well as (and often better than) its purely 96 proactive and reactive constituent protocols. In situations where 97 the network behavior varies across different regions, the ZRP 98 performance can be fine-tuned by individual adjustment of each node's 99 routing zone. 101 The global reactive component of the ZRP uses the multicast based 102 "bordercast" mechanism to propagate route queries throughout the 103 network efficiently, rather than relying on neighbor-broadcast 104 flooding found in traditional reactive protocols. Consequently, the 105 ZRP provides the most benefit in networks where reliable neighbor 106 broadcasting is either inefficient or altogether impossible. In 107 particular, the ZRP is well suited for multi-channel, multi- 108 technology routing fabrics and networks operating under high load. 110 B. Protocol Characteristics and Mechanisms 112 * Does the protocol provide support for unidirectional links? 113 (if so, how?) 114 Yes. The ZRP provides "local" support for unidirectional links. 115 A unidirectional link can be used as long as the link source and 116 link destination lie within each other's routing zone. 118 * Does the protocol require the use of tunneling? (if so, how?) 119 No. 121 * Does the protocol require using some form of source routing? 122 (if so, how?) 124 No. The ZRP's framework supports global route discovery based 125 on source routing, distributed distance vectors, or various 126 combinations of both. 128 * Does the protocol require the use of periodic messaging? 129 (if so, how?) 131 Yes. The ZRP framework proactively maintains local routing 132 information (routing zones) based on periodic exchanges of 133 neighbor discovery messages. 135 * Does the protocol require the use of reliable or sequenced packet 136 delivery? (if so, how?) 138 The ZRP only assumes that link-layer (neighbor) unicasts are 139 delivered reliably and in-sequence. Reliable and sequenced 140 delivery of neighbor broadcasts and IP unicasts is not 141 required. 143 * Does the protocol provide support for routing through a multi- 144 technology routing fabric? (if so, how?) 146 Yes. It is assumed that each node's network interface is 147 assigned a unique IP address. 149 * Does the protocol provide support for multiple hosts per router? 150 (if so, how?) 152 Yes. Multiple hosts may be associated with a router. These 153 hosts can be identified by the neighbor discovery/maintenance 154 process. 156 By default, it is assumed that a host's association with a router 157 is not permanent. As a result, the ZRP exchanges routing 158 information for individual hosts in the same manner as routing 159 information for routers. 161 In cases where a router is permanently associated with a network 162 (subnetwork), the ZRP supports the exchange of network 163 (subnetwork) prefixes in place of all aggregated host IP 164 addresses. 166 * Does the protocol support the IP addressing architecture? 167 (if so, how?) 169 Yes. Each node is assumed to have a unique IP address (or 170 set of unique IP addresses in the case of multiple interfaces). 171 The ZRP references all nodes/interfaces by their IP address. 173 This version of the ZRP also supports IP network addressing 174 (network prefixes) for routers that provide access to a 175 network of non-router hosts. 177 * Does the protocol require link or neighbor status sensing 178 (if so, how?) 180 Yes. The ZRP proactively maintains local routing information 181 (routing zones) based on detected changes in neighbor status. 183 * Does the protocol have dependence on a central entity? 184 (if so, how?) 186 No. The ZRP is a fully distributed protocol. 188 * Does the protocol function reactively? (if so, how?) 190 Yes. The ZRP's GLOBAL route discovery mechanism is reactive. 191 A route query is initiated, on demand, when a node requires 192 routing information that is not immediately available in its 193 routing table. 195 The route query propagates through the network, using a special 196 packet delivery service called "bordercasting". Bordercasting 197 leverages knowledge of local network topology to direct route 198 queries away from the source, thereby reducing redundancy. 200 * Does the protocol function proactively? (if so, how?) 202 Yes. The ZRP proactively maintains LOCAL routing information 203 (routing zones) for each node. The routing zone information is 204 leveraged, through the bordercasting mechanism, to support 205 efficient global propagation of route queries. 207 * Does the protocol provide loop-free routing? (if so, how?) 209 Yes. If the reactive Interzone Routing is based on source 210 routing, loop-freedom in the route discovery process is ensured 211 by inspection of accumulated source routes. For distributed 212 distance vector approaches, loop-freedom can be ensured by 213 labeling queries (replies) with the source (destination) address 214 and locally unique sequence number. Nodes that relay these 215 messages can temporarily cache these identifiers in order to 216 identify and terminate loops. 218 The proactive Intrazone Routing based on link states is 219 inherently loop-free, although temporary loops may form while new 220 link state updates propagate through the routing zone. 222 * Does the protocol provide for sleep period operation? (if so, how?) 224 No. Sleep period operation is not addressed in this draft. 225 However, sleep period support can be included as needed. 227 * Does the protocol provide some form of security? (if so, how?) 229 No. It is assumed that security issues are adequately addressed 230 by the underlying protocols (IPsec, for example). 232 * Does the protocol provide support for utilizing multi-channel, 233 link-layer technologies? (if so, how?) 235 Yes. It is assumed that each node's network interface is 236 assigned a unique IP address. 238 1. Introduction 240 One of the major challenges in designing a routing protocol for the 241 ad hoc networks stems from the fact that, on one hand, to determine 242 a packet route, a node needs to know at least the reachability 243 information to its neighbors. On the other hand, in an ad hoc 244 network, the network topology can change quite often. Furthermore, 245 as the number of network nodes can be large, the potential number of 246 destinations is also large, requiring large and frequent exchange of 247 data (e.g., routes, routes updates, or routing tables) among the 248 network nodes. Thus, the amount of update traffic can be quite high. 249 This is in contradiction with the fact that all updates in a 250 wirelessly interconnected ad hoc network travel over the air and, 251 thus, are costly in resources. 253 In general, the existing routing protocols can be classified either 254 as proactive or as reactive. Proactive protocols attempt to 255 continuously evaluate the routes within the network, so that when 256 a packet needs to be forwarded, the route is already known and can 257 be immediately used. The family of Distance-Vector protocols is an 258 example of a proactive scheme. Examples of proactive routing 259 protocols include the Wireless Routing Protocol (WRP) [11] and 260 Destination-Sequenced Distance-Vector (DSDV) routing [16]. Reactive 261 protocols, on the other hand, invoke a route determination procedure 262 on demand only. Thus, when a route is needed, some sort of global 263 search procedure is employed. The family of classical flooding 264 algorithms belong to the reactive group. Some other examples of 265 reactive (also called on-demand) ad hoc network routing protocols are 266 Dynamic Source Routing (DSR) [9], Ad-hoc On demand Distance Vector 267 Routing (AODV) [17] and the Temporally Ordered Routing Algorithm 268 (TORA) [13]. 270 The advantage of the proactive schemes is that, once a route is 271 needed, there is little delay until the route is determined. In 272 reactive protocols, because route information may not be available 273 at the time a datagram is received, the delay to determine a route 274 can be quite significant. Furthermore, the global flood-search 275 procedure of the reactive protocols requires significant control 276 traffic. Because of this long delay and excessive control traffic, 277 pure reactive routing protocols may not be applicable to real-time 278 communication. However, pure proactive schemes are likewise not 279 appropriate for the ad hoc networking environment, as they 280 continuously use a large portion of the network capacity to keep the 281 routing information current. Since nodes in an ad hoc network move 282 quite fast, and as the changes may be more frequent than the route 283 requests, most of this routing information is never even used! This 284 results in a further waste of the wireless network capacity. What is 285 needed is a protocol that, on one hand, initiates the route 286 determination procedure on-demand, but at limited search cost. The 287 protocol described in this draft, termed the "Zone Routing Protocol 288 (ZRP)" ([1],[2],[14]), is an example of a such a hybrid proactive/ 289 reactive scheme. 291 The ZRP, on one hand, limits the scope of the proactive procedure 292 only to the node's local neighborhood. On the other hand, the search 293 throughout the network, although global in nature, is done by 294 efficiently querying selected nodes in the network, as opposed to 295 querying all the network nodes. 297 A related issue is that of updates in the network topology. For a 298 routing protocol to be efficient, changes in the network topology 299 should have only a local effect. In other words, creation of a new 300 link at one end of the network is an important local event but, most 301 probably, not a significant piece of information at the other end of 302 the network. Globally proactive protocols tend to distribute such 303 topological changes widely in the network, incurring large costs. The 304 ZRP limits propagation of such information to the neighborhood of the 305 change only, thus limiting the cost of topological updates. 307 2. Overview of the Zone Routing Framework 309 In the Zone Routing framework, a proactive routing protocol provides a 310 detailed and fresh view of each node's surrounding local topology 311 (routing zone) at the local level. The knowledge of local topology is 312 used to support services such as proactive route maintenance, 313 unidirectional link discovery and guided message distribution. One 314 particular message distribution service, called bordercasting [5], 315 directs queries throughout the network across overlapping routing 316 zones. Bordercasting is used in place of traditional broadcasting to 317 improve the efficiency of a global reactive routing protocol. 319 The benefits provided by routing zones, compared with the overhead of 320 proactively tracking routing zone topology, determine the optimal 321 framework configuration. As network conditions change, the framework 322 can be dynamically reconfigured through adjustment of each node's 323 routing zone 325 2.1 Routing Zones and the Intrazone Routing Protocol (IARP) 327 In Zone Routing, the Intrazone Routing Protocol (IARP) proactively 328 maintains routes to destinations within a local neighborhood, which we 329 refer to as a routing zone. More precisely, a node's routing zone is 330 defined as a collection of nodes whose minimum distance in hops from 331 the node in question is no greater than a parameter referred to as the 332 zone radius. Note that each node maintains its own routing zone. An 333 important consequence is that the routing zones of neighboring nodes 334 overlap. 336 An example of a routing zone (for node A) of radius 2 is shown below. 338 +-----------------------------------------+ 339 | +---+ | 340 | +---+ ---| F |-------| | 341 +---+ | +---+ --| C |--/ +---+ +---+ | 342 | G |-----| D |--/ +---+ | E | | Routing Zone of 343 +---+ | +---+ | +---+ +---+ | node A 344 | +---+ ---| B |-------| | (radius = 2 hops) 345 | | A |--/ +---+ | 346 | +---+ | 347 +-----------------------------------------+ 349 Note that in this example nodes B through F are within the routing 350 zone of A. Node G is outside A's routing zone. Also note that E can be 351 reached by two paths from A, one with length 2 hops and one with 352 length 3 hops. Since the minimum is less or equal than 2, E is within 353 A's routing zone. 355 Peripheral nodes are nodes whose minimum distance to the node in 356 question is equal exactly to the zone radius. Thus, in the above 357 figure, nodes D, F, and E are A's peripheral nodes. 359 The construction of a routing zone requires a node to first know who 360 its neighbors are. A neighbor is defined as a node with whom direct 361 (point-to-point) communication can be established and is, thus, one 362 hop away. Identification of a node's neighbors may be provided 363 directly by the media access control (MAC) protocols, as in the case 364 of polling-based protocols. In other cases, neighbor discovery may 365 be implemented through a separate Neighbor Discovery Protocol (NDP). 366 Such a protocol typically operates through the periodic broadcasting 367 of "hello" beacons. The reception (or quality of reception) of a 368 "hello" beacon can be used to indicate the status of a connection to 369 the beaconing neighbor. 371 Neighbor discovery information is used as a basis for the IARP. 372 IARP can be derived from globally proactive link state routing 373 protocols that provide a complete view of network connectivity. 374 [3] describes the Intrazone Routing Protocol (IARP) in detail and 375 lists the conversion guidelines for adapting a proactive link-state 376 based routing protocol to serve as an IARP. 378 2.2 Bordercast-Based Global Reactive (Interzone) Routing 380 Route discovery in the Zone Routing framework is distinguished from 381 standard broadcast-based route discovery through a message 382 distribution service known as the Bordercast Resolution Protocol (BRP) 383 [5]. Rather than blindly broadcasting a route query from neighbor to 384 neighbor, bordercasting allows the query to be directed outward, 385 toward regions of the network (specifically, toward peripheral nodes) 386 that have not yet been "covered" by the query. (A covered node is one 387 that belongs to the routing zone of a node that has received a route 388 query). The query control mechanisms reduce route query traffic by 389 directing query messages outward from the query source and away from 390 covered routing zones. 392 A node can determine local query coverage by noting the addresses of 393 neighboring nodes that have forwarded the query. In the case of 394 multiple channel networks, a node can only detect query packets that 395 have been directly forwarded to it. For single channel networks, a 396 node may be able to detect any query packet forwarded within the 397 node's radio range. When a node identifies a query forwarding 398 neighbor, all known members of that neighbor's routing zone (i.e., 399 those members which belong to both the node's and neighbor's routing 400 zones) are marked as covered. 402 When a node is called upon to relay a bordercast message, it again 403 uses its routing zone topology to construct a bordercast tree, that is 404 rooted at itself and spans its uncovered peripheral nodes. The 405 message is then forwarded to those neighbors in the bordercast tree. 406 By virtue of the fact that this node has forwarded the query, all of 407 its routing zone members are marked as covered. Therefore, a 408 bordercasting node will not forward a query more than once. 409 The details of the Bordercast Resolution Protocol are described in [5]. 411 Given the availability of an underlying bordercast service, the 412 operation of Zone Routing's global reactive Interzone Routing Protocol 413 (IERP) is quite similar to standard route discovery protocols. An IERP 414 route discovery is initiated when no route is locally available to the 415 destination of an outgoing data packet. The source generates a route 416 query packet, which is uniquely identified by a combination of the 417 source node's address and request number. The query is then relayed to 418 a subset of neighbors as determined by the bordercast algorithm. Upon 419 receipt of a route query packet, a node checks if the destination lies 420 in its zone or if a valid route to it is available in its route cache. 421 If the answer is affirmative, a route reply is sent back to the 422 source. If not, the node bordercasts the query again. The operation of 423 the IERP is sufficiently general, so that many existing reactive 424 protocols can be used as an IERP with minimal modification. The 425 details of IERP's operation can be found in [4]. 427 3.0 The ZRP Architecture 429 ......................................... 430 : Z R P : 431 : : 432 +---------+ : +---------+ +---------+ : +---------+ 433 | NDP |========>| IARP |========>| IERP |<========| ICMP | 434 +---------+ : +---------+ |---+-----+ : +---------+ 435 /|\ : /|\ |BRP| /|\ : /|\ 436 | : | +---+ | : | 437 | : | /|\ | : | 438 | :...........|................|.....|....: | 439 | | | | | 440 \|/ \|/ \|/ \|/ \|/ 441 +---------+---------+---------+---------+---------+---------+---------+ 442 | IP | 443 +---------+---------+---------+---------+---------+---------+---------+ 445 Legend: 447 A <---> B exchange of packets between protocols A & B 448 A ===> B information passed from protocol A to protocol B 450 Existing Protocols 451 ------------------ 452 IP Internet Protocol 453 ICMP Internet Control Message Protocol 455 ZRP Entities 456 ------------ 457 IARP IntrAzone Routing Protocol 458 IERP IntErzone Routing Protocol 459 BRP Bordercast Resolution Protocol 461 Additional Protocols 462 -------------------- 463 NDP Neighbor Discovery Protocol 465 The architecture of the hybrid Zone Routing framework is modular, so 466 that a link state routing protocol can be used as an IARP [3] and an 467 on-demand routing protocol can be used as an IERP [4]. As an example, 468 consider TBRPF [12] or OLSR [7] as an IARP and AODV [15] or DSR [8] as 469 an IERP. 471 4. Other Considerations 473 4.1 Sizing the Zone Radius 475 The performance of the Zone Routing Protocol is determined by the 476 routing zone radius. In general, dense networks consisting of a few 477 fast moving nodes favor smaller routing zones. On the other hand, a 478 sparse network of many slowly moving nodes operates more efficiently 479 with a larger zone radius. 481 The simplest approach to configuring the routing zone radius is to 482 make the assignment once, prior to deploying the network. This can 483 be performed by the network administration, if one exists, or by 484 the manufacturer, as a default value. This may provide acceptable 485 performance, especially in situations where network characteristics 486 do not vary greatly over space and time. Alternatively, the ZRP can 487 adapt to changes in network behavior, through dynamic configuration 488 of the zone radius [6]. In [14], it was shown that a node can 489 accurately estimate its optimal zone radius, on-line, based on local 490 measurements of ZRP traffic. The re-sizing of the routing zone can be 491 carried out by a protocol that conveys the change in zone radius to 492 the members of the routing zone. 494 In Zone Routing with independently sized routing zones capability, 495 each of the nodes in the network can adaptively configure its own 496 optimal zone radius in a distributed fashion. The performance of Zone 497 Routing is further improved by the ability to provide fine-tuned 498 adaptation to local and temporal variations in network characteristics 499 [19]. The details of the Independent Zone Routing (IZR) framework will 500 be included in a future version of this draft. 502 4.2 Hierarchical Routing and the ZRP 504 In a hierarchical network architecture, network nodes are organized 505 into a smaller number of (often disjoint) clusters. This routing 506 hierarchy is maintained by two component routing protocols. An intra- 507 cluster protocol provides routes between nodes of the same cluster, 508 while an inter-cluster protocol operates globally to provide routes 509 between clusters. 511 The ZRP, with its routing zones and intrazone / interzone routing 512 protocol (IARP/IERP) architecture may give the appearance of being a 513 hierarchical routing protocol. In actuality, the ZRP is a flat 514 routing protocol. Each node maintains its own routing zone, which 515 heavily overlaps with the routing zones of neighboring nodes. Because 516 there is a one-to-one correspondence between nodes and routing zones, 517 the routing zones, unlike hierarchical clusters, do not serve to hide 518 the details of local network topology. As a result, the network-wide 519 interzone routing protocol (IERP) actually determines routes between 520 individual nodes, rather than just between higher level network 521 entities. 523 For small to moderately sized networks, flat routing protocols, like 524 the ZRP, are preferable to hierarchical routing protocols. In order 525 for a node to be located, its address needs to reflect the node's 526 location within the network hierarchy (i.e. {cluster id,node id}). 527 Because of node mobility, a node's cluster membership (and thus 528 address) is subject to change. This complicates mobility management, 529 for the benefit of more efficient routing. In many hierarchical 530 routing protocols, each cluster designates a single clusterhead node 531 to relay inter-cluster traffic. These clusterhead nodes become 532 traffic "hot-spots", potentially resulting in network congestion and 533 single point of failure. Furthermore, restricting cluster access 534 through clusterhead nodes can lead to sub-optimal routes, as potential 535 neighbors in different clusters are prohibited from communicating 536 directly. Some hierarchical routing protocols, such as the 537 Zone-Based Hierarchical Link-State (ZHLS) [8], avoid these problems by 538 distributing routing information to all cluster nodes, rather than 539 maintaining a single clusterhead. 541 In spite of these disadvantages, hierarchical routing protocols are 542 often better suited for very large networks than flat routing 543 protocols. Because hierarchical routing protocols provide global 544 routes to network clusters, rather than individual nodes, routing 545 table storage is more scalable. Similarly, the amount of route update 546 messages is also more scalable. To some extent, the reduction in 547 routing traffic is offset by extra mobility management overhead (i.e. 548 identifying which cluster a node belongs to). However, it is quite 549 common that the environment or existing organizational structure 550 causes nodes to naturally cluster together. In these cases, there may 551 be a high degree of intra-cluster mobility, with inter-cluster 552 mobility is less common. 554 A hierarchical routing protocol can be viewed as a set of flat routing 555 protocols, each operating at different levels of granularity. In a 556 two-tier routing protocol, the inter-cluster components is essentially 557 a flat routing protocol that computes routes between clusters. 558 Likewise, the intra-cluster component is a flat routing protocol, that 559 computes routes between nodes in each cluster. For example, the Near 560 Term Digital Radio (NTDR) System [18] and ZHLS both employ proactive 561 link state protocols to determine inter and intracluster connectivity. 563 In place of traditional proactive or reactive protocols, we recommend 564 that the intra-cluster and inter-cluster routing protocol components 565 be implemented based on the hybrid proactive/reactive ZRP. As 566 described throughout this draft, the ZRP is designed to provide an 567 optimal balance between purely proactive and reactive routing. This 568 applies equally well to routing between nodes at the intra-cluster 569 level and between clusters at the inter-cluster level. Additionally, 570 the hybrid ZRP methodology can be applied to the related mobility 571 management protocols, which determine complete node addresses based on 572 a node's location in the network hierarchy. 574 5. Patent Rights Statement 576 Cornell University has filed one or more patents protecting the 577 inventions described in this submission (the "Patents"). If Cornell 578 University's submission, or material portions thereof, is accepted and 579 becomes part of the IETF standard (the "Standard"), then Cornell will 580 grant any entity wishing to practice the Standard a non-exclusive, 581 royalty-free license under the Patents to the extent, but only to the 582 extent, that such license is required to implement (a) mandatory 583 elements of the Standard; or (b) elements of Cornell's submission that 584 are explicitly specified (and not merely incorporated by reference) in 585 the Standard. 587 Use of any elements of Cornell's submission that are neither required 588 in order to implement the Standard nor explicitly specified in the 589 Standard will require an additional license from Cornell University 590 under terms to be negotiated between the parties. 592 While the protocol disclosed in Cornell's submission is being 593 evaluated by the IETF, whether on the standards track or otherwise, 594 Cornell University will and hereby does grant any party a license to 595 utilize, test and evaluate such protocol solely for non-commercial, 596 research purposes. 598 6. References 600 [1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable 601 Wireless Networks," ICUPC'97, San Diego, CA, Oct. 12,1997. 603 [2] Haas, Z.J. and Pearlman, M.R., "The Performance of Query 604 Control Schemes for the Zone Routing Protocol," 605 SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998. 607 [3] Haas, Z.J., Pearlman, M.R. and Samar, P., "Intrazone Routing 608 Protocol (IARP)," IETF Internet Draft, 609 draft-ietf-manet-iarp-02.txt, July 2002. 611 [4] Haas, Z.J., Pearlman, M.R. and Samar, P., "Interzone Routing 612 Protocol (IERP)," IETF Internet Draft, 613 draft-ietf-manet-ierp-02.txt, July 2002. 615 [5] Haas, Z.J., Pearlman, M.R. and Samar, P., "Bordercasting 616 Resolution Protocol (BRP)," IETF Internet Draft, 617 draft-ietf-manet-brp-02.txt, July 2002. 619 [6] Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design 620 Choices in Ad-Hoc Communications," MILCOM'98, Boston, MA, 621 October 18-21, 1998. 623 [7] Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L., 624 and Clausen T., "Optimized Link State Routing Protocol," 625 IETF Internet Draft, draft-ietf-manet-olsr-03.txt, 626 November 2000. 628 [8] Joa-Ng, M. and Lu, I.T., "A Peer-to-Peer Zone-based Two-Level 629 Link State Routing for Mobile Ad-Hoc Networks," to appear 630 in IEEE JSAC issue on Ad-Hoc Networks, June, 1999. 632 [9] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing 633 in Ad-Hoc Wireless Networks," in Mobile Computing, 634 edited by T. Imielinski and H. Korth, chapter 5, 635 pp. 153-181, Kluwer, 1996. 637 [10] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, 638 RFC 2178, July 1997. 640 [11] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient 641 Routing Protocol for Wireless Networks," MONET, vol. 1, 642 no. 2, pp. 183-197, October 1996. 644 [12] Ogier, R. "Efficient Routing Protocols for Packet-Radio 645 Networks Based on Tree Sharing," MoMUC '99, November 1999. 647 [13] Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed 648 Routing Algorithm for Mobile Wireless Networks," 649 IEEE INFOCOM'97, Kobe, Japan, 1997. 651 [14] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal 652 Configuration for the Zone Routing Protocol," IEEE JSAC, 653 August, 1999. 655 [15] Pearlman, M.R. and Haas, Z.J., "Improving the Performance of 656 of Query-Based Routing Protocols Through 'Diversity 657 Injection'", IEEE WCNC'99, New Orleans, LA, Sept. 1999. 659 [16] Perkins, C.E., and Bhagwat, P., "Highly Dynamic 660 Destination-Sequenced Distance-Vector Routing (DSDV) for 661 Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994. 663 [17] Perkins, C.E. and Royer, E.M., "Ad-Hoc On-Demand Distance 664 Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 666 [18] Ruppe, R., Griswald, S., Walsh, P. and Martin, R., "Near Term 667 Digital Radio (NTDR) System," IEEE MILCOM'97, Monterey, CA, 668 Nov. 1997. 670 [19] Samar, P., Pearlman, M.R. and Haas, Z.J., "Hybrid Routing: The 671 Pursuit of an Adaptable and Scalable Routing Framework for 672 Ad Hoc Networks," in Handbook of Ad Hoc Wireless Networks, 673 M. Ilyas, ed., CRC Press 2002. 675 [20] Waitzman, D., Partridge, C., Deering, S.E., "Distance 676 Vector Multicast Routing Protocol," RFC 1075, Nov. 1, 1988. 678 Authors' Information 680 Zygmunt J. Haas 681 Wireless Networks Laboratory 682 323 Frank Rhodes Hall 683 School of Electrical & Computer Engineering 684 Cornell University 685 Ithaca, NY 14853 686 United States of America 687 tel: (607) 255-3454, fax: (607) 255-9072 688 Email: haas@ece.cornell.edu 690 Marc R. Pearlman 691 389 Frank Rhodes Hall 692 School of Electrical & Computer Engineering 693 Cornell University 694 Ithaca, NY 14853 695 United States of America 696 tel: (607) 255-0236, fax: (607) 255-9072 697 Email: pearlman@ece.cornell.edu 699 Prince Samar 700 374 Frank Rhodes Hall 701 School of Electrical & Computer Engineering 702 Cornell University 703 Ithaca, NY 14853 704 United States of America 705 tel: (607) 255-9068, fax: (607) 255-9072 706 Email: samar@ece.cornell.edu 708 The MANET Working Group contacted through its chairs: 710 M. Scott Corson 711 Institute for Systems Research 712 University of Maryland 713 College Park, MD 20742 714 (301) 405-6630 715 corson@isr.umd.edu 717 Joseph Macker 718 Information Technology Division 719 Naval Research Laboratory 720 Washington, DC 20375 721 (202) 767-2001 722 macker@itd.nrl.navy.mil