idnits 2.17.1 draft-ietf-manet-zone-zrp-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 3358 lines 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 342 instances of too long lines in the document, the longest one being 4 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 634: '...e route's source MAY be notified so th...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 369 has weird spacing: '...ocedure of th...' == Line 416 has weird spacing: '...ius. An examp...' == Line 476 has weird spacing: '...esponse proto...' == Line 1112 has weird spacing: '... update of al...' == Line 1718 has weird spacing: '...cularly usefu...' -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' ** Obsolete normative reference: RFC 2178 (ref. '7') (Obsoleted by RFC 2328) -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' ** Downref: Normative reference to an Experimental RFC: RFC 1075 (ref. '13') Summary: 10 errors (**), 0 flaws (~~), 7 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Zygmunt J. Haas, Cornell 2 University 3 Marc R. Pearlman, Cornell 4 University 5 Expires in six months on December 1999 June 6 1999 8 The Zone Routing Protocol (ZRP) for Ad Hoc Networks 9 11 Status of this Memo 13 This document is an Internet-Draft and is NOT offered in accordance 14 with Section 10 of RFC2026, and the author does not provide the IETF 15 with any rights other than to publish as an Internet-Draft. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet-Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference material 24 or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 Distribution of this memo is unlimited. 34 Abstract 36 This document describes the Zone Routing Protocol (ZRP), a hybrid 37 routing protocol suitable for a wide variety of mobile ad-hoc 38 networks, especially those with large network spans and diverse 39 mobility patterns. Each node proactively maintains routes within a 40 local region (referred to as the routing zone). Knowledge of the 41 routing zone topology is leveraged by the ZRP to improve the 42 efficiency of a reactive route query/reply mechanism. The proactive 43 maintenance of routing zones also helps improve the quality of 44 discovered routes, by making them more robust to changes in network 45 topology. The ZRP can be configured for a particular network by 46 proper selection of a single parameter, the routing zone radius. 48 The ZRP framework is designed to provide a balance between the 49 contrasting proactive and reactive routing approaches. To underscore 50 this general philosophy, both the proactive and reactive components of 51 this ZRP implementation have been expanded. This draft provides 52 specifications for both a (split-horizon) Distance Vector AND a Link 53 State 54 version of the proactive IntrAzone Routing Protocol (IARP). The reactive 55 IntErzone Routing Protocol (IERP) provides a route caching option. When 56 route caching is globally enabled, the IERP acts as a reactive Distance 57 Vector protocol, distributing routing information among intermediate 58 nodes. 59 On the other hand, when route caching is disabled, the routes are 60 accumulated 61 in the query packets and the protocol operates through source routing. 63 Haas, Pearlman Expires December 1999 [Page 64 i] 65 1999 67 This ZRP specification also offers some additional enhancements. The 68 reactive route query procedure now supports route querying for multiple 69 destinations and multicast groups. Queries can be targeted for either 70 ANY destination or ALL destinations (depending on the nature of the 71 query). 72 By aggregating route queries, the amount of overhead traffic can be 73 greatly 74 reduced. In addition, the ZRP now supports QOS routing through the 75 collection of various route quality metrics (in both the proactive and 76 reactive routing components). 78 Haas, Pearlman Expires December 1999 [Page 79 ii] 80 1999 82 Contents 84 Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i 85 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i 87 Applicability Statement . . . . . . . . . . . . . . . . . . . . v 88 A. Networking Context . . . . . . . . . . . . . . . . . . v 89 B. Protocol Characteristics and Mechanisms . . . . . . . . v 91 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 93 2. Overview of the Zone Routing Protocol . . . . . . . . . . . 3 94 2.1 The Notion of a Routing Zone and the 95 Intrazone Routing Protocol (IARP) . . . . . . . . . . 3 97 2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 4 98 2.2.1 Routing Zone Based Route Discovery . . . . . . 4 99 2.2.2 Route Accumulation Procedure . . . . . . . . . 5 100 2.2.3 Query Control Mechanisms . . . . . . . . . . . 6 101 2.2.4 Route Maintenance . . . . . . . . . . . . . . . 7 103 3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 8 105 4. Implementation Details . . . . . . . . . . . . . . . . . . 9 106 4.1 Intrazone Routing Protocol (IARP) . . . . . . . . . . 9 107 4.1.1 Distance Vector Implementation . . . . . . . . 9 108 A. Packet Format . . . . . . . . . . . . . . . . 10 109 B. Data Structures . . . . . . . . . . . . . . . 11 110 C. Interfaces . . . . . . . . . . . . . . . . . . 11 111 D. State Machine . . . . . . . . . . . . . . . . 12 112 E. Pseudocode Implementation . . . . . . . . . . 14 113 4.1.2 Link State Implementation . . . . . . . . . . . 16 114 A. Packet Format . . . . . . . . . . . . . . . . 16 115 B. Data Structures . . . . . . . . . . . . . . . 18 116 C. Interfaces . . . . . . . . . . . . . . . . . . 20 117 D. State Machine . . . . . . . . . . . . . . . . 20 118 E. Pseudocode Implementation . . . . . . . . . . 21 120 4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 24 121 A. Packet Format . . . . . . . . . . . . . . . . . . 26 122 B. Data Structures . . . . . . . . . . . . . . . . . 31 123 C. Interfaces . . . . . . . . . . . . . . . . . . . . 31 124 D. State Machine . . . . . . . . . . . . . . . . . . 32 125 E. Pseudocode Implementation . . . . . . . . . . . . 33 127 4.3 Bordercasting Resolution Protocol (BRP) . . . . . . . 37 128 A. Packet Format . . . . . . . . . . . . . . . . . . 38 129 B. Data Structures . . . . . . . . . . . . . . . . . 38 130 C. Interfaces . . . . . . . . . . . . . . . . . . . . 38 131 D. State Machine . . . . . . . . . . . . . . . . . . 39 132 E. Pseudocode Implementations . . . . . . . . . . . . 43 134 Haas, Pearlman Expires December 1999 [Page 135 iii] 136 1999 138 5. Other Considerations . . . . . . . . . . . . . . . . . . . 53 139 5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 53 140 5.2 Hierarchical Routing and the ZRP . . . . . . . . . . . 53 142 6. References . . . . . . . . . . . . . . . . . . . . . . . . 55 144 Haas, Pearlman Expires December 1999 [Page 145 iv] 146 1999 148 Applicability Statement 150 A. Networking Context 152 The hybrid Zone Routing Protocol (ZRP) can adapt to a wide variety of 153 network scenarios by adjusting the range of the nodes' proactively 154 maintained routing zones. Large routing zones are preferred when demand 155 for routes is high and/or the network consists of many slowly moving 156 nodes. In the extreme case of a network with fixed topology, the ideal 157 routing zone radius would be infinitely large. (Consider the purely 158 proactive routing protocols used on the fixed Internet). On the other 159 hand, 160 smaller routing zones are appropriate in situations where route demand 161 is 162 low and/or the network consists of a small number of nodes that move 163 fast 164 relative to one another. In the "worst case", a routing zone radius of 165 one 166 hop is best, and the ZRP defaults to a tradtional reactive flooding 167 protocol. 169 When the ZRP is properly configured for a particular network scenario, 170 it 171 can perform at least as well as (and often better than) its purely 172 proactive 173 and reactive constituent protocols. In situations where the network 174 behavior varies across different regions, the ZRP performance can be 175 fine 176 tuned by individual adjustment of each node's routing zone. 178 The global reactive component of the ZRP uses the unicast/multicast 179 based 180 "bordercast" mechanism to propagate route queries throughout the 181 network, 182 rather than neighbor-broadcast based flooding found in tradtional 183 reactive 184 protocols. Consequently, the ZRP provides the most benefit in networks 185 where reliable neighbor broadcasting is either inefficient or 186 all-together 187 impossible. In particular, the ZRP is well suited for multi-channel, 188 multi- 189 technology routing fabrics and networks operating under high load. 191 B. Protocol Characteristics and Mechanisms 193 * Does the protocol provide support for unidirectional links? (if so, 194 how?) 195 Yes. The ZRP provides "local" support for unidirectional links. 196 A unidirectional link can be used as long as the link source and 197 link destination lie within each other's routing zone. 199 * Does the protocol require the use of tunneling? (if so, how?) 200 No. 202 * Does the protocol require using some form of source routing? (if 203 so, how?) 205 No. The ZRP's global reactive route discovery mechanism may 206 use either source routing or distributed distance vector based 207 route accumulation. 209 Haas, Pearlman Expires December 1999 [Page 210 v] 211 1999 213 * Does the protocol require the use of periodic messaging? (if so, 214 how?) 216 Yes. The ZRP proactively maintains local routing information 217 (routing zones) based on periodic exchanges of neighbor 218 discovery messages. 220 * Does the protocol require the use of reliable or sequenced packet 221 delivery? (if so, how?) 223 The ZRP only assumes that link-layer (neighbor) unicasts are 224 delivered reliably and in-sequence. Reliable and sequenced 225 delivery of neighbor broadcasts and IP unicasts is not 226 required. 228 * Does the protocol provide support for routing through a multi- 229 technology routing fabric? (if so, how?) 231 Yes. It is assumed that each node's network interface is 232 assigned a unique IP address. 234 * Does the protocol provide support for multiple hosts per router? 235 (if so, how?) 237 Yes. Multiple hosts may be associated with a router. These hosts 238 can be identified by the neighbor discovery/maintenance process. 240 By default, it is assumed that a host's association with a router 241 is not permanent. As a result, the ZRP exchanges routing 242 information 243 for individual hosts in the same manner as routing information for 244 routers. 246 In cases where a router is permanently associated with a network 247 (subnetwork), the ZRP supports the exchange of network (subnetwork) 248 prefixes in place of all aggregated host IP addresses. 250 * Does the protocol support the IP addressing architecture? (if so, 251 how?) 253 Yes. Each node is assumed to have a unique IP address (or 254 set of unique IP addresses in the case of multiple interfaces). 255 The ZRP references all nodes/interfaces by their IP address. 257 This version of the ZRP also supports IP network addressing 258 (network prefixes) for routers that provide access to a 259 network of non-router hosts. 261 Haas, Pearlman Expires December 1999 [Page 262 vi] 263 1999 265 * Does the protocol require link or neighbor status sensing (if so, 266 how?) 268 Yes. The ZRP proactively maintains local routing information 269 (routing zones) based on detected changes in neighbor status. 271 * Does the protocol have dependence on a central entity? (if so, 272 how?) 274 No. The ZRP is a fully distributed protocol. 276 * Does the protocol function reactively? (if so, how?) 278 Yes. The ZRP's GLOBAL route discovery mechanism is reactive. 279 A route query is initiated, on demand, when a node requires routing 280 information that is not immediately available in its routing table. 282 The route query propagates through the network, using a ZRP-specific 283 packet delivery service called "bordercasting". Bordercasting 284 leverages knowledge of local network topology to direct route 285 queries away from the source, thereby reducing redundancy. 287 * Does the protocol function proactively? (if so, how?) 289 Yes. The ZRP proactively maintains local routing information 290 (routing zones) for each node. The routing zone information is 291 leveraged, through the bordercasting mechanism, to support 292 efficient global propagation of route queries. 294 * Does the protocol provide loop-free routing? (if so, how?) 296 Yes. Loop-freedom in the reactive route discovery process 297 is ensured by labeling each route query and route reply 298 with the IP address of its originating node AND a unique 299 sequence number. Nodes that relay the route queries 300 /route replies temporarily cache these identifiers in order 301 to identify and terminate loops. 303 The routing protocols used for proactive routing zone maintenance 304 are based on traditional Distance Vector or Link State routing 305 protocols. The scope of these proactive route updates is limited 306 to the extent of a node's routing zone. 307 The ZRP's Link State proactive protocol is inherently loop-free. 308 The Distance Vector protocol may form temporary loops prior to 309 converging. However, convergence occurs quickly due to the limited 310 radius of the routing zones 312 Haas, Pearlman Expires December 1999 [Page 313 vii] 314 1999 316 * Does the protocol provide for sleep period operation? (if so, how?) 318 No. 320 * Does the protocol provide some form of security? (if so, how?) 322 No. It is assumed that security issues are adequately addressed 323 by the underlying protocols (IPsec, for example) 325 * Does the protocol provide support for utilizing multi-channel, 326 link-layer technologies? (if so, how?) 328 Yes. It is assumed that each node's network interface is 329 assigned a unique IP address. 331 Haas, Pearlman Expires December 1999 [Page 332 viii] 333 1999 335 1. Introduction 337 One of the major challenges in designing a routing protocol for the 338 ad hoc networks stems from the fact that, on one hand, to determine 339 a packet route, a node needs to known at least the reachability 340 information to its neighbors. On the other hand, in an ad hoc 341 network, the network topology can change quite often. Furthermore, 342 as the number of network nodes can be large, the potential number of 343 destinations is also large, requiring large and frequent exchange of 344 data (e.g., routes, routes updates, or routing tables) among the 345 network nodes. Thus, the amount of update traffic can be quite high. 346 This is in contradiction with the fact that all updates in a 347 wirelessly interconnected ad hoc network travel over the air and, 348 thus, are costly in resources. 350 In general, the existing routing protocols can be classified either 351 as proactive or as reactive. Proactive protocols attempt to 352 continuously evaluate the routes within the network, so that when 353 a packet needs to be forwarded, the route is already known and can 354 be immediately used. The family of Distance-Vector protocols is an 355 example of a proactive scheme. Reactive protocols, on the other 356 hand, invoke a route determination procedure on demand only. Thus, 357 when a route is needed, some sort of global search procedure is 358 employed. The family of classical flooding algorithms belong to the 359 reactive group. Some examples of reactive (also called on-demand) 360 ad hoc network routing protocols are Dynamic Source Routing (DSR)[6], 361 Ad-hoc On demand Distance Vector Routing (AODV) [11] and the 362 Temporally Ordered Routing Algorithm (TORA) [9]. 364 The advantage of the proactive schemes is that, once a route is 365 needed, there is little delay until the route is determined. In 366 reactive protocols, because route information may not be available 367 at the time a datagram is received, the delay to determine a route 368 can be quite significant. Furthermore, the global flood-search 369 procedure of the reactive protocols requires significant control 370 traffic. Because of this long delay and excessive control traffic, 371 pure reactive routing protocols may not be applicable to real-time 372 communication. However, pure proactive schemes are likewise not 373 appropriate for the ad hoc networking environment, as they 374 continuously use a large portion of the network capacity to keep the 375 routing information current. Since nodes in an ad hoc networks move 376 quite fast, and as the changes may be more frequent than the route 377 requests, most of this routing information is never even used! This 378 results in a further waste of the wireless network capacity. What is 379 needed is a protocol that, on one hand, initiates the route- 380 determination procedure on-demand, but at limited search cost. The 381 protocol described in this draft, termed the "Zone Routing Protocol 382 (ZRP)" ([1], [2]), is an example of a such a hybrid 383 proactive/reactive scheme. 385 The ZRP, on one hand, limits the scope of the proactive procedure 386 only to the node's local neighborhood. On the other hand, the search 387 throughout the network, although global in nature, is done by 388 efficiently querying selected nodes in the network, as opposed to 389 querying all the network nodes. 391 Haas, Pearlman Expires December 1999 [Page 392 1] 393 1999 395 A related issue is that of updates in the network topology. For a 396 routing protocol to be efficient, changes in the network topology 397 should have only a local effect. In other words, creation of a new 398 link at one end of the network is an important local event but, most 399 probably, not a significant piece of information at the other end of 400 the network. Proactive protocols tend to distribute such topological 401 changes widely in the network, incurring large costs. The ZRP limits 402 propagation of such information to the neighborhood of the change 403 only, thus limiting the cost of topological updates. 405 Haas, Pearlman Expires December 1999 [Page 406 2] 407 1999 409 2. Overview of the Zone Routing Protocol 411 2.1 The Notion of a Routing Zone and the Intrazone Routing Protocol 412 (IARP) 414 A routing zone is defined for each node X, and includes the nodes 415 whose minimum distance in *hops* from X is at most some predefined 416 number, which is referred to as the Zone Radius. An example of a 417 routing zone (for node A) of radius 2 is shown below. 419 +-----------------------------------------+ 420 | +---+ | 421 | +---+ ---| F |-------| | 422 +---+ | +---+ --| C |--/ +---+ +---+ | 423 | G |-----| D |--/ +---+ | E | | Zone of node A 424 +---+ | +---+ | +---+ +---+ | of radius=2 425 | +---+ ---| B |-------| | 426 | | A |--/ +---+ | 427 | +---+ | 428 +-----------------------------------------+ 430 Note that in this example nodes B through E are within the routing 431 zone of A. Node G is outside A's routing zone. Also note that E can 432 be reached by two paths from A, one with length 2 hops and one with 433 length 3 hops. Since the minimum is less or equal than 2, E is within 434 A's routing zone. 436 Peripheral nodes are nodes whose minimum distance to the node in 437 question is equal exactly to the zone radius. Thus, in the above 438 figure, nodes D, F, and E are A's peripheral nodes. 440 An important consequence of the routing zone construction is the 441 ability of a node to deliver a packet to its peripheral nodes. 442 This service, which we refer to as bordercasting, allows for more 443 efficient network-wide searching than simple neighbor broadcasting. 444 Bordercasting could be implemented either through a series of IP 445 unicasts or an IP multicast (Distance Vector Multicast Routing 446 Protocol [13]) to the peripheral nodes. (In cases where 447 multicasting is supported, the multicasting approach is preferred 448 to reduce the amount of traffic over the air.) However, as will be 449 explained later, efficient ZRP operation requires that these unicast 450 or multicast services be provided by the ZRP, with IP providing best- 451 effort delivery to the specified ZRP next hops. 453 The ZRP supports the proactive maintenance of routing zones 454 through its proactive Intrazone Routing Protocol (IARP). Through 455 the IARP, each node learns the identity of and the (minimal) 456 distance to all the nodes in its routing zone. The IARP may be 457 derived from a wide range of proactive protocols, such as 458 Distance Vector (e.g., [8], [10]) or Shortest Path First 459 (e.g., OSPF [7]). Whatever the choice of IARP is, the base 460 protocol needs to be modified to ensure that the scope of this 461 operation is restricted to the radius of a node's routing zone. 463 Haas, Pearlman Expires December 1999 [Page 464 3] 465 1999 467 Because each node needs to proactively acquire route information 468 only for the nodes within its zone, the total amount of IARP traffic 469 does not depend on the size of the network, which may be quite large 471 2.2 The Interzone Routing Protocol (IERP) 473 While the IARP maintains routes within a zone, the IERP* is 474 responsible for finding routes between nodes located at distances 475 larger than the zone radius. The IERP is distinguished from standard 476 flood-search query/response protocols by exploiting the routing zone 477 topology. A node is able to respond positively to any queries for 478 its routing zone nodes. For large networks, relatively few 479 destinations lie within any particular node's routing zone. In this 480 more likely case, the node can efficiently continue the propagation 481 of the query, through the routing zone-based bordercast delivery 482 mechanism. 484 2.2.1 Routing Zone Based Route Discovery 486 The IERP operates as follows: The source node first checks whether 487 the destination is within its routing zone. (Again, this is possible 488 as every node knows the content of its zone). If so, the path to the 489 destination is known and no further route discovery processing is 490 required. If, on the other hand, the destination is not within the 491 source's routing zone, the source bordercasts a route query to all of 492 its peripheral nodes. Now, in turn, all the peripheral nodes execute 493 the same algorithm: check whether the destination is within their 494 zone. If so, a route reply is sent back to the source indicating the 495 route to the destination. If not, the peripheral node forwards the 496 query to its peripheral nodes, which, in turn, executes the same 497 procedure. An example of this Route Discovery procedure is 498 demonstrated in the figure below. 500 * Some functions of the IERP, including bordercasting, route 501 accumulation, and query control (see later), are performed by a 502 special component of the IERP called the Bordercast Resolution 503 Protocol (BRP). Sections 3.0 and 4.0 describe, in detail, the 504 relationship between the BRP and the IERP proper. 506 Haas, Pearlman Expires December 1999 [Page 507 4] 508 1999 510 +---+ 511 +---+ | F | 512 +---+---| C |----+---+-----+---+ +---+ 513 | D | +---+ | E |----| H | 514 +---+ | +---+-----+---+ +---+ 515 +---+----| B | | 516 | A | +---+-----+---+ +---+ 517 +---+ | G | | I | 518 +---+ +---+ 519 | 520 +---+ 521 +---+ | J | 522 | C |----+---+----+---+ +---+ 523 +---+ | K |----| L | 524 +---+ +---+ 526 The node A has a datagram to send to node L. Assume a uniform 527 routing zone radius of 2 hops. Since L is not in A's routing zone 528 (which includes B,C,D,E,F,G), A bordercasts a routing query to its 529 peripheral nodes: D,F,E, and G. Each one of these peripheral nodes 530 check whether L exists in their routing zones. Since L is not found 531 in any routing zones of these nodes, the nodes bordercast the request 532 to their peripheral nodes. In particular, G bordercasts to K, which 533 realizes that L is in its routing zone and returns the requested 534 route (L-K-G-A) to the query source, namely A. 536 2.2.2 Route Accumulation Procedure 538 The query propagation mechanism allows a route query to indirectly 539 reach the desired destination (through some node Y, which discovers 540 the destination in its routing zone.) To complete the route 541 discovery process, Y needs to send a reply back to the query's 542 source, S, providing S with the desired route. To perform the route 543 reply, sufficient information needs to be accumulated during the 544 query phase so that Y is provided with a route back to S. Providing 545 routes from discovering node Y to query source S, and from the query 546 source S back to the query destination D (through Y), is the role of 547 the Route Accumulation procedure. 549 In the basic Route Accumulation, a node appends its IP address to a 550 received query packet. The sequence of IP addresses specifies a 551 route from the query's source to the current node. By reversing this 552 sequence, a route may also be obtained back to the source. In this 553 way, Y may send a reply back to S, through strict source routing. 555 Haas, Pearlman Expires December 1999 [Page 556 5] 557 1999 559 Given sufficient storage space, a queried node may cache routing 560 information accumulated in the query packet, allowing the information 561 to be remove from the packet. This has the benefit of reducing the 562 length of the query packet, thereby decreasing the query traffic and 563 query response time. The IP addresses that remain in the packet can 564 be used to form a loose source route back to the query's source (If 565 ALL nodes have cached the accumulated route information, then this 566 effectively becomes next hop routing. If no nodes have cached 567 accumulated route information, then this defaults to the basic case 568 previously discussed). The same caching strategy can be applied to 569 the reply packet on its way back to the source. In this case, a 570 loose source route to the destination is formed. 572 2.2.3 Query Control Mechanisms 574 Bordercasting has the potential to support global querying schemes 575 that are more efficient than flooding. To achieve this efficiency, 576 the protocol should be able to detect and terminate a query thread 577 when it appears in a previously queried region of the network (i.e. 578 arrives at a node belonging to the routing zone of a previously 579 queried node). This detection / termination capability is 580 significantly limited when bordercasting is implemented directly 581 through IP unicast or IP multicast. 583 By implementing bordercasting within the ZRP, the nodes that relay 584 the query to the peripheral node are able to detect the passing 585 query. If the underlying IP delivery is (neighbor) broadcast or 586 if IP is operating in promiscuous mode, then nodes that overhear 587 a query transmission are also able to detect the query, further 588 strengthening the Query Detection (QD) mechanism. Upon detecting 589 a query, the identifying query parameters (i.e. query source, 590 query ID) are recorded in a Detected Queries Table, to provide a 591 basis for termination of future threads of that query. 593 A node can consider a query to be redundant if it has already 594 detected that query, bordercasted by a different node. If 595 bordercasting is implemented directly through IP unicast/ multicast, 596 then a query thread could only be terminated after being received by 597 the peripheral node (bordercast destination). This could result in 598 wasted transmissions as a query penetrates into a previously queried 599 region. Implementing bordercasting in the ZRP allows the protocol to 600 provide an Early Termination (ET), as the redundant query enters the 601 previously queried region. 603 Haas, Pearlman Expires December 1999 [Page 604 6] 605 1999 607 2.2.4 Route Maintenance 609 In addition to initially discovering routes, the IERP may also assume 610 responsibility for monitoring the integrity of these routes and 611 repairing failed routes as appropriate. 613 Route failures can be detected either proactively or reactively. 614 Proactive route failure detection is triggered by the IARP, in 615 response to a node leaving the routing zone. Any IERP routes 616 containing this node as the first hop can be considered invalid. 617 Route failures may also be detected reactively, by IP, when the next 618 hop in a datagram's source route is determined to be unreachable 619 (i.e. does not appear in the (Intrazone) Routing Table). 621 Upon detection of a route failure, a node may choose to notify 622 the route's source of the failure and / or attempt to repair the 623 route. A route failure notification consists of a transmission 624 back to the query source, indicating that the source route has 625 failed, and possibly the hop at which it failed. This type of 626 service is provided by protocols like ICMP. The node that detects 627 the route failure may also try to repair the failed connection by 628 discovering a route to bypass the failed connection. The repair 629 discovery process is nearly identical to an initial route discovery. 630 Route repairs should not be substantially longer than the original 631 failed connection. Thus, the depth of a repair query can be limited, 632 through the use of hop counter. This has the advantage of producing 633 much less query traffic than an unrestricted initial route query. 634 After a successful repair, the route's source MAY be notified so that 635 routes are properly selected for use. Alternatively, the repair 636 could go unreported without compromising the connectivity between 637 source and destination. 639 Haas, Pearlman Expires December 1999 [Page 640 7] 641 1999 643 3.0 The ZRP Architecture 645 ......................................... 646 : ZRP : 647 : : 648 +---------+ : +---------+ +---------+ : +---------+ 649 | NDM |========>| IARP |========>| IERP |<========| ICMP | 650 +---------+ : +---------+ |.........| : +---------+ 651 /|\ : /|\ | BRP | : /|\ 652 | : | +---------+ : | 653 | : | /|\ : | 654 | :...........|...................|.......: | 655 | | | | 656 \|/ \|/ \|/ \|/ 657 +---------+---------+---------+---------+---------+---------+---------+ 658 | IP | 659 +---------+---------+---------+---------+---------+---------+---------+ 661 Legend: 663 A <---> B exchange of packets between protocols A & B 664 A ===> B information passed from protocol A to protocol B 666 Existing Protocols 667 ------------------ 668 IP Internet Protocol 669 ICMP Internet Control Message Protocol 671 ZRP Entities 672 ------------ 673 IARP IntrAzone Routing Protocol 674 IERP IntErzone Routing Protocol 675 BRP Bordercast Resolution Protocol 676 (component of IERP) 678 Additional Protocols 679 -------------------- 680 NDM Neighbor Discovery/Maintenance Protocol 682 Note, it is assumed that basic neighbor discovery operation is 683 implemented by the MAC/link-layer protocols. Thus the NDM protocol 684 remains unspecified here. 686 Haas, Pearlman Expires December 1999 [Page 687 8] 688 1999 690 4. Implementation Details 692 4.1 The IntrAzone Routing Protocol (IARP) 694 The Intrazone Routing Protocol (IARP) is responsible for proactively 695 maintaining routes within each node's routing zone. This can be achieved 696 through a variety of different implementations. In fact, many 697 traditional proactive protocols can be modified to serve as an IARP by 698 limiting the range of route updates to the boundary of routing zones. 700 In this draft, we detail implementations for both a Distance-Vector 701 and a Link-State IARP. The convergence problems typically associated 702 with 703 the Distance-Vector approach are less of a liability in the IARP 704 implementation because of the finite hop count imposed by the routing 705 zone 706 radius. Additionally, techniques such as "hold-downs", "split horizons" 707 and "poison reverse" can be used to prevent instabilities. A stable 708 Distance Vector IARP implementation converges a rate comparable to 709 Link-State IARP, and generally with less control traffic and reduced 710 computational overhead. However, the Link-State IARP provides a complete 711 view of the routing zone topology, making it a favorable option for some 712 applications (including "on-line" routing zone re-sizing). 714 4.1.1 Distance Vector (with split horizon) IARP 716 In this version of the IARP, exchanged routing messages consist of the 717 route cost (including hop count) and the IP addresses of the route's 718 destination and next TWO hops to the destination. The second hop 719 is included to identify routes where a node is it's own second hop. 720 This particular looping condition result in the "counting to 721 infinity" problem. By deleting these routes, this problem can be 722 avoided, allowing the IARP to converge faster. 724 A node may receive new route information either from a received IARP 725 packet or from an interrupt generated by its Neighbor Discovery / 726 Maintenance (NDM) process*. In the special case when a host has 727 discovered a neighbor, the IARP is responsible for sending to the new 728 neighbor the shortest route to each host which is common to both of 729 their routing zones (i.e. each host with a hop count less than it's 730 routing zone radius). The node then records the new route information 731 in its Intrazone Routing Table. If the shortest path to the host has 732 changed, the terminal broadcasts an IARP packet reflecting the 733 change. 735 * IARP relies on the services of a separate protocol (referred to 736 here as the Neighbor Discovery/Maintenance Protocol) to provide 737 current information about a host's neighbors. At the least, this 738 information must include the IP addresses of all the neighbors. 739 The IARP can be readily configured to support supplemental 740 link quality metrics. 742 Haas, Pearlman Expires December 1999 [Page 743 9] 744 1999 746 A. Packet Format 747 1 2 3 748 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 749 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 750 | Destination Address | 751 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 752 | Destination Subnet Mask (Optional) | 753 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 754 | Next Hop #1 Address | 755 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 756 | Next Hop #2 Address | 757 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 758 | RESERVED | Metric Type | Metric Value | | 759 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 760 | | Route 761 \| |/ Metrics 762 \ / 763 (optional) 764 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 765 | RESERVED | Metric Type | Metric Value | | 766 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 767 | Hop Count | 768 +-+-+-+-+-+-+-+-+ 770 Field Description: 772 * Destination Address (32 bits) 773 IP address of the destination host 775 * Destination Subnet Mask (32 bits) 776 IP subnet mask associated with the destination 778 * Next Hop # 1 Address (32 bits) 779 IP address of the "next hop" host to the destination host 781 * Next Hop # 2 Address (32 bits) 782 IP address of the Next Hop #1 's "next hop" host to 783 the destination host 785 * Node/Link Metrics (X * 32 bits) 786 This section of the packet is used to report the quality of 787 this link (or link source node). 789 * Metric Type (8 bits) 790 Type of metric being reported 791 (based on pre-defined metric types) 793 * Metric Value (16 bits) 794 Value of node / link metric specified by Metric Type 796 * Hop Count (8 bits) 797 Length of the route to the destination host, measured 798 in hops 800 Haas, Pearlman Expires December 1999 [Page 801 10] 802 1999 804 B. Data Structures 806 B.1 Intrazone Routing Table 808 +---------+--------|-----------------------------------------+ 809 | Dest | Subnet | Routes | 810 | Addr | Mask |-----------+-----------+-----+-----------+ 811 | | | 0 | 1 | ==> | M-1 | 812 +---------+--------|-----------+-----------+-----+-----------+ 813 | | | | | ==> | | 814 |---------+--------|-----------|-----------|-----|-----------| 815 | | | | | ==> | | 816 |---------+--------|-----------|-----------|-----|-----------| 817 | | | | | | | ==> | | 818 +---------+--------|----| |----+-----------+-----+-----------+ 819 | | 820 | +---\ +----------|--+--+ +--+ 821 +-----/ | | | |...| | 822 +----------|--+--+ +--+ 823 Next Hop route 824 node ID metrics 826 C. Interfaces 828 C.1 Higher Layer (N/A) 829 C.2 Lower Layer (IP) 830 C.1.1 Send() (specified in IP standard) 831 C.1.2 Deliver() (specified in IP standard) 832 C.3 NDM 833 C.3.1 Neighbor_Lost(host,mask,metric) 834 Used by the NDM to notify the IARP that direct contact 835 has been lost with "host" (with subnet mask "mask"). 836 Any node/link quality measurements are reported in 837 the "metric" list. 838 C.3.2 Neighbor_Found(host,mask,metric) 839 Used by the NDM to notify the IARP that direct contact 840 has been confirmed with "host" (with subnet mask "mask"). 841 Any node/link quality measurements are reported in 842 the "metric" list. 843 C.4 IERP 844 C.4.1 Zone_Node_Lost(host) 845 Used by IARP to notify the IERP that a node no longer 846 exists within the routing zone. 848 Haas, Pearlman Expires December 1999 [Page 849 11] 850 1999 852 D. State Machine 854 The IARP protocol consists of only one state (IDLE). Therefore, 855 no state transitions need to be specified. The IARP immediately 856 acts upon an event and then returns back to the IDLE state. 858 Notes: 1) X is used as a label for the host running this state 859 machine. 860 2) INF is a reserved field value corresponding to 861 "infinity". 863 D.1 864 Event: An IARP packet is received containing route 865 information to a destination D. The hop count 866 associated with the received route is LESS THAN 867 OR EQUAL TO the routing zone radius. The 868 second next-hop is EQUAL to X. 870 Action: NONE 872 D.2 873 Event: An IARP packet is received containing route 874 information to a destination D. The hop count 875 associated with the received route is LESS THAN 876 the routing zone radius. The second next-hop 877 is NOT EQUAL to X. 879 Action: The received route is recorded in the Intrazone 880 Routing Table. If the received route is shorter 881 than the previous shortest route to D, then a new 882 IARP packet containing route information to D 883 through X is broadcasted. 885 D.3 886 Event: An IARP packet is received containing route 887 information to a destination D. The hop count is 888 EQUAL TO the routing zone radius. The second 889 next-hop is NOT EQUAL to X. 891 Action: The received route is recorded in the Intrazone 892 Routing Table. 894 Haas, Pearlman Expires December 1999 [Page 895 12] 896 1999 898 D.4 899 Event: An IARP packet is received containing route 900 information to a destination D. The hop count is 901 equal to INF. 903 Action: The route to D is removed from the Intrazone 904 Routing Table. 905 1) If the Intrazone Routing Table still 906 contains a route to D and the length of the 907 shortest route has increased due to the route 908 removal, then the an IARP packet containing the 909 shortest route to D through X is broadcasted. 910 2) If the Intrazone Routing Table contains no 911 more routes to D, then an IARP packet containing 912 a route to D through X with hop count of INF is 913 broadcast. A "Host Lost" interrupt is 914 generated to alert the IERP that D has moved 915 beyond the routing zone. 917 D.5 918 Event: A "Neighbor Found" interrupt is received, 919 indicating the discovery of a neighbor host N. 921 Action: For each destination in X's Intrazone Routing 922 Table, an IARP packet is sent to N containing the 923 best route to that destination. An IARP packet is 924 then broadcasted containing the 1 hop route to N 925 through X. 927 D.6 928 Event: A "Neighbor Lost" interrupt is received, indicating 929 that host N is no longer a neighbor of X 931 Action: The one hop route to N is removed from the 932 Intrazone Routing Table. 933 1) If the Intrazone Routing Table still 934 contains a route to N and the length of the 935 shortest route has increased due to the route 936 removal, then the an IARP packet containing the 937 shortest route to N through X is broadcasted. 938 2) If the Intrazone Routing Table contains no 939 more routes to N, then an IARP packet containing 940 a route to D through X with hop count of INF is 941 broadcast. A "Host Lost" interrupt is generated 942 to alert the IERP that D has moved beyond the 943 routing zone. 945 Haas, Pearlman Expires December 1999 [Page 946 13] 947 1999 949 E. Pseudocode Implementation 951 We define two complimentary operations on packets: 952 extract(packet) and load(packet) 954 extract (packet) 955 extracts the fields of the IARP packet to the following 956 variables: {dest, mask, next_hop_1, next_hop_2, 957 route_metric, 958 hop_count} 960 load (packet) 961 loads the values of the aforementioned variables into 962 the fields of the IARP packet. 964 E.1 Update Intrazone Routing Table 966 if (packet arrived) 967 extract(packet) 968 else 969 { 970 {dest,mask,metric} <-- intrpt 971 next_hop_1=dest 972 if (type(intrpt) == "Neighbor Found") 973 { 974 for d = each node in Intrazone_Routing_Table 975 { 976 best_route = get_shortest_route(Intrazone_Routing_Table,d) 977 mask = get_mask(Intrazone_Routing_Table, d) 978 if (best_route->hop_count < ROUTING_ZONE_RADIUS) 979 { 980 packet<--{d,mask,MY_ID,best_route->next_hop, 981 best_route->metric,best_route->hop_count+1} 982 send(packet,dest) 983 } 984 } 985 hop_count=1 986 } 987 else 988 hop_count=INF 989 } 991 former_best_route = get_shortest_route(Intrazone_Routing_Table,dest) 993 Haas, Pearlman Expires December 1999 [Page 994 14] 995 1999 997 if (hop_count < INF) 998 { 999 if(next_hop_2 != MY_ID) 1000 { 1001 link_metric = get_metric(Intrazone_Routing_Table, next_hop_1) 1002 route_metric = add_metric(route_metric, link_metric) 1003 add(Intrazone_Routing_Table, {dest,mask,next_hop_1, 1004 route_metric,hop_count}) 1005 } 1006 } 1007 else 1008 remove(Intrazone_Routing_Table, {dest, next_hop_1}) 1009 best_route = get_shortest_route(Intrazone_Routing_Table,dest) 1010 if (best_route != NULL) 1011 { 1012 if (best_route->hop_count != former_best_route->hop_count 1013 (AND) best_route->hop_count < ROUTING_ZONE_RADIUS) 1014 { 1015 packet <-- {dest,mask,MY_ID,best_route->next_hop, 1016 best_route->metric,best_route->hop_count+1} 1017 send(packet,BROADCAST) 1018 } 1019 } 1020 else 1021 { 1022 force_intrpt("IERP","Zone Node Lost",{dest}) 1023 packet <-- {dest, mask, MY_ID, MY_ID, NULL, INF} 1024 send(packet,BROADCAST) 1025 } 1027 Haas, Pearlman Expires December 1999 [Page 1028 15] 1029 1999 1031 4.1.2 Link State IARP 1032 In this version of the IARP, nodes compute intrazone routes based on the 1033 link state (neighbor connectivity) of each routing zone node. A node may 1034 receive link state updates either from an IARP link state packet or from 1035 an interrupt generated by its Neighbor Discovery / Maintenance (NDM) 1036 process*. Link states are maintained in a Link State Table. When all 1037 pending link state updates have been received (full link state updates 1038 may 1039 contain multiple links and span multiple packets), the routing table is 1040 recomputed, using a minimum spanning tree algorithm. The Link State 1041 Table 1042 is then updated to remove links that lie outside of the routing zone. 1043 All 1044 new link state updates for non-peripheral routing zone nodes are 1045 forwarded 1046 to all neighbors. In addition, if a new neighbor is discovered, the new 1047 neighbor is sent the FULL link states of all non-peripheral routing zone 1048 nodes. 1050 * IARP relies on the services of a separate protocol (referred to 1051 here as the Neighbor Discovery/Maintenance Protocol) to provide 1052 current information about a host's neighbors. At the least, this 1053 information must include the IP addresses of all the neighbors. 1054 The IARP can be readily configured to support supplemental 1055 link quality metrics. 1057 A. Packet Format 1059 1 2 3 1060 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 1061 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1062 | Link Source Address | 1063 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1064 | Link Destination Address | 1065 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1066 | Packet Source Address | 1067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1068 | Link State ID | Zone Radius | Flags | 1069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1070 | Link Destination Subnet Mask (Optional) | 1071 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1072 | RESERVED | Metric Type | Metric Value | | 1073 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1074 | RESERVED | Metric Type | Metric Value | | 1075 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1076 | | Link 1077 \| |/ Metrics 1078 \ / | 1079 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1080 | RESERVED | Metric Type | Metric Value | | 1081 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1083 Haas, Pearlman Expires December 1999 [Page 1084 16] 1085 1999 1087 Field Description: 1089 * Link Source Address (32 bits) 1090 IP address of the reported link's source node. 1092 * Link Destination Address (32 bits) 1093 IP address of the reported link's destination node. 1095 * Packet Source Address (32 bits) 1096 IP address of the node that sent this packet. 1097 (Used to account for any outstanding link state information) 1099 * Link State ID (16 bits) 1100 Sequence number used to track the link state history of 1101 the Link Source node. 1103 * Zone Radius (8 bits) 1104 Routing zone radius of the link's source node. Determines the 1105 extent that link state information propagates. 1107 * Flags (8 bits) 1108 Flags(0) Full Link Information 1109 Indicates whether this link state information was sent as: 1110 (0) a PARTIAL link state update 1111 OR 1112 (1) part of a FULL update of all the 1113 link source's current links 1115 Flags(1) Current Link State Update 1116 Indicates whether more link state information is pending 1117 for THIS link state update {link_source,state_id} 1118 (0) INCOMPLETE 1119 (1) COMPLETE 1121 Flags(2) All Link State Updates 1122 Indicates whether more link state updates are pending 1123 (0) INCOMPLETE 1124 (1) COMPLETE 1126 Flags(3) Link Destination Subnet Mask 1127 (0) INCLUDED 1128 (1) NOT INCLUDED 1130 Flags(4) Link Status 1131 (0) DOWN 1132 (1) UP 1134 Flags(5..7) RESERVED for future use. 1136 Haas, Pearlman Expires December 1999 [Page 1137 17] 1138 1999 1140 * Node/Link Metrics (X * 32 bits) 1141 This section of the packet is used to report the quality of 1142 this link (or link source node). 1144 * Metric Type (8 bits) 1145 Type of metric being reported 1146 (based on pre-defined metric types) 1148 * Metric Value (16 bits) 1149 Value of node / link metric specified by Metric Type 1151 B. Data Structures 1153 B.1 Intrazone Routing Table 1155 +---------+--------|-----------------------------------------+ 1156 | Dest | Subnet | Routes | 1157 | Addr | Mask |-----------+-----------+-----+-----------+ 1158 | | | 0 | 1 | ==> | M-1 | 1159 +---------+--------|-----------+-----------+-----+-----------+ 1160 | | | | | ==> | | 1161 |---------+--------|-----------|-----------|-----|-----------| 1162 | | | | | ==> | | 1163 |---------+--------|-----------|-----------|-----|-----------| 1164 | | | | | | | ==> | | 1165 +---------+--------|----| |----+-----------+-----+-----------+ 1166 | | 1167 | +---\ +----------|--+--+ +--+ 1168 +-----/ | | | |...| | 1169 +----------|--+--+ +--+ 1170 Next Hop route 1171 node ID metrics 1173 Haas, Pearlman Expires December 1999 [Page 1174 18] 1175 1999 1177 B.2 Link State Table 1179 +--------+--------+------------+ 1180 | Link | Zone | Link State | Link State Information 1181 | Source | Radius | ID | 1182 +--------+--------+------------+ +---|---|-----|-+ 1183 +---|---|-----|-+ 1184 | | | |---> | | | | | | |...| | | | | 1185 | | ** 1186 | | +------------+ +---|---|-----|-+ 1187 +---|---|-----|-+ 1188 | | | |-+ 1189 | | +------------+ | +---|---|-----|-+ 1190 : : : || : +-> | | | | | | | 1191 : : : \||/ : +---|---|-----|-+ 1192 : : : \/ : 1193 | | +------------+ +---+---|-----|-+ 1194 | | | |---> | | | | | | | 1195 +--------+--------+------------+ +---+---|-----|-+ 1196 | || | || | || | (a) (b) (c) (d) 1197 : || : || : || : 1198 : \||/ : \||/ : \||/ : 1199 | \/ | \/ | \/ | 1200 +--------+--------+------------+ 1202 (a) Link Destination Address 1203 (b) Link Destination Subnet Mask 1204 (c) Link Metrics 1205 (d) Forward Flag (indicates if link state information has 1206 been forwarded) 1208 ** The first link state entry for each link source 1209 contains the complete link state information 1210 corresponding to the Link State ID. 1211 Subsequent entries contain only changes of a single 1212 link state. 1214 A FULL link state entry of link state #k and 1215 a PARTIAL entry of link state #(k+1) can be 1216 merged into a FULL link state entry of 1217 link state #(k+1) 1219 B.3 Pending Link State List 1220 (list of neighbors in the process of sending link state updates) 1222 +----------+ +----------+ +----------+ 1223 | | ---> | | . . . | | (node addresses) 1224 +----------+ +----------+ +----------+ 1226 B.4 New Neighbors List 1227 (list of new neighbors to receive a copy Link State Table, 1228 upon completion of updates) 1230 +----------+ +----------+ +----------+ 1231 | | ---> | | . . . | | (node addresses) 1232 +----------+ +----------+ +----------+ 1234 Haas, Pearlman Expires December 1999 [Page 1235 19] 1236 1999 1238 B.5 Former Routing Zone Nodes 1239 (list of routing zone nodes, prior to routing table updates) 1241 +----------+ +----------+ +----------+ 1242 | | ---> | | . . . | | (node addresses) 1243 +----------+ +----------+ +----------+ 1245 C. Interfaces 1247 C.1 Higher Layer (N/A) 1248 C.2 Lower Layer (IP) 1249 C.1.1 Send() (specified in IP standard) 1250 C.1.2 Deliver() (specified in IP standard) 1251 C.3 NDM 1252 C.3.1 Neighbor_Lost(host,mask,metric) 1253 Used by the NDM to notify the IARP that direct contact 1254 has been lost with "host" (with subnet mask "mask"). 1255 Any node/link quality measurements are reported in 1256 the "metric" list. 1257 C.3.2 Neighbor_Found(host,mask,metric) 1258 Used by the NDM to notify the IARP that direct contact 1259 has been confirmed with "host" (with subnet mask "mask"). 1260 Any node/link quality measurements are reported in 1261 the "metric" list. 1262 C.4 IERP 1263 C.4.1 Zone_Node_Lost(host) 1264 Used by IARP to notify the IERP that a node no longer 1265 exists within the routing zone. 1267 D. State Machine 1269 The IARP protocol consists of only one state (IDLE). Therefore, 1270 no state transitions need to be specified. The IARP immediately 1271 acts upon an event and then returns back to the IDLE state. 1273 Notes: 1) X is used as a label for the host running this state 1274 machine. 1275 2) INF is a reserved field value corresponding to 1276 "infinity". 1278 D.1 1279 Event: An IARP link state packet is received. 1281 Action: The link state update is recorded in the Link State 1282 Table. 1283 If more link state updates are pending, then the IARP 1284 returns to an idle state. Otherwise, X rebuilds its 1285 routing table. Links that lie outside of the routing 1286 zone 1287 are removed from the Link State Table. X sends its 1288 neighbors all previously unforwarded link state updates 1289 from its NON-peripheral nodes. Finally, all neighbors 1290 in the New Neighbor List are sent the link states of 1291 X's 1292 NON-peripheral nodes, and the New Neighbor List is 1293 cleared. 1295 Haas, Pearlman Expires December 1999 [Page 1296 20] 1297 1999 1299 D.2 1300 Event: A "Neighbor Found" interrupt is received, indicating 1301 the discovery of a neighbor N. 1303 Action: X's new link to N is recorded in the Link State Table 1304 and 1305 N is added to the New Neighbors List. If more link 1306 state 1307 updates are pending, then the IARP returns to an idle 1308 state. Otherwise, X rebuilds its routing table. Links 1309 that lie outside of the routing zone are removed from 1310 the 1311 Link State Table. X sends its neighbors all previously 1312 unforwarded link state updates from its NON-peripheral 1313 nodes. Finally, all neighbors in the New Neighbor List 1314 are sent the link states of X's NON-peripheral nodes, 1315 and 1316 the New Neighbor List is cleared. 1318 D.3 1319 Event: A "Neighbor Lost" interrupt is received, indicating 1320 that node N is no longer a neighbor of X. 1322 Action: The lost link to neighbor N is removed from the Link 1323 State Table and N is removed from the New Neighbor 1324 List. 1325 If more link state updates are pending, then the IARP 1326 returns to an idle state. Otherwise, X rebuilds its 1327 routing table. Links that lie outside of the routing 1328 zone are removed from the Link State Table. X sends 1329 its 1330 neighbors all previously unforwarded link state updates 1331 from its NON-peripheral nodes. Finally, all neighbors 1332 in the New Neighbor List are sent the link states of 1333 X's 1334 NON-peripheral nodes, and the New Neighbor List is 1335 cleared. 1337 E. Pseudocode Implementation 1339 We define two complimentary operations on packets: 1340 extract(packet) and load(packet) 1342 extract (packet) 1343 extracts the fields of the IARP packet to the following 1344 variables: {link_source, link_dest, pk_source, state_id, 1345 radius, flags, mask, link_metric} 1346 * full_link_state -> flag(0) 1347 * current_update -> flag(1) 1348 * all_updates -> flag(2) 1349 * mask -> flag(3) 1350 * link_status -> flag(4) 1352 load (packet) 1353 loads the values of the aforementioned variables into 1354 the fields of the IARP packet. 1356 Haas, Pearlman Expires December 1999 [Page 1357 21] 1358 1999 1360 E.1 Update Intrazone Routing Table 1362 if (packet arrived) 1363 { 1364 extract(packet) 1365 my_link_changed = FALSE 1366 } 1367 else 1368 { 1369 {link_dest,mask,link_metric} <-- intrpt 1370 link_source = MY_ID 1371 pk_source = MY_ID 1372 state_id = MY_LINK_STATE_ID 1373 radius = MY_ROUTING_ZONE_RADIUS 1375 full_link_state = 0 1376 current_update = COMPLETE 1377 all_updates = COMPLETE 1379 if (type(intrpt) == "Neighbor Found") 1380 link_status = UP 1381 else 1382 link_status = DOWN 1384 my_link_changed = TRUE 1385 } 1387 add(Pending_Link_State_List, link_from_id) 1388 status = add(Link_State_Table,link_source, link_dest, mask, radius, 1389 link_metric, state_id, flags) 1390 if (status == NEW_LINK_INFO) 1391 { 1392 cum_status = UPDATE_IN_PROGRESS 1393 if(my_link_changed) 1394 { 1395 if (link_status == UP) 1396 add(New_Neighbor_List, link_dest) 1397 else 1398 remove(New_Neighbor_List, link_dest) 1399 MY_LINK_STATE_ID++ 1400 } 1401 } 1403 if(all_updates == COMPLETE) 1404 remove(Pending_Link_State_List, link_from_id) 1406 Haas, Pearlman Expires December 1999 [Page 1407 22] 1408 1999 1410 if(empty(Pending_Link_State_List) (AND) 1411 cum_status == UPDATE_IN_PROGRESS) 1412 { 1413 for(each node (BELONGING TO) Intrazone_Routing_Table) 1414 add(Former_Routing_Zone_Nodes, node) 1416 rebuild = TRUE; 1417 while (rebuild) 1418 { 1419 Intrazone_Routing_Table 1420 = 1421 construct_spanning_tree(Link_State_Table); 1422 rebuild = update(Link_State_Table); 1423 } 1425 broadcast_link_state_updates(Link_State_Table); 1427 for (each node (BELONGING TO) New_Neighbor_List)) 1428 send_link_state_table(Link_State_Table, node); 1430 clear(New_Neighbor_List) 1432 cum_status = UPDATE_COMPLETE; 1434 for (each node (BELONGING TO) Former_Routing_Zone_Nodes) 1435 { 1436 if(node !(BELONGS TO) Intrazone_Routing_Table) 1437 force_intrpt("IERP","Zone Node Lost",{node}) 1438 } 1439 clear(Former_Routing_Zone_Nodes) 1440 } 1442 Haas, Pearlman Expires December 1999 [Page 1443 23] 1444 1999 1446 4.2 IntErzone Routing Protocol (IERP) 1448 The Interzone Routing Protocol (IERP) is responsible for discovering 1449 and maintaining routes to hosts which are beyond a node's routing 1450 zone. The IERP acquires routing information reactively, exploiting 1451 the knowledge of the routing zone topology through the bordercasting 1452 delivery service. 1454 This version of the IERP extends the basic query / reply mechanism 1455 described in Section 3. In the basic protocol, queries are 1456 terminated before reaching the query destination. This provides 1457 a faster response to the route query than if the destination, D, 1458 were to respond directly. However, because D never receives the 1459 query, it does not acquire a route back to the source, S. If the 1460 D needs to send data back to S (which is often the case, given the 1461 bi-directional nature of many applications), a separate route query 1462 from D to S would have to be initiated. This substantial overhead 1463 is avoided by having the query forwarded to D, by the node Y that 1464 discovers D in its routing zone. We refer to this as a 1465 QUERY_EXTENSION. 1467 Both the source and destination can acquire routes to each other 1468 through the BRP route accumulation mechanisms (to be discussed 1469 later). Distributing route information in the caches of the 1470 route's nodes can significantly reduce the size of the IERP packets 1471 and provide for a faster query response. On the other hand, QOS 1472 requirements for a particular application may favor a source 1473 specified route. (rather than a distributed next-hop approach). 1474 Source routing requires that the discovered route information be 1475 accumulated in the IERP packets, rather than cached. This IERP 1476 implementation satisfies the demands for rapid query response 1477 and source routing support by two stages of route reporting. In the 1478 first two stages, route information is cached by the route's nodes 1479 (when possible). Next-hop route are quickly returned to the source 1480 in ROUTE_REPLY packets and forwarded to the destination in QUERY_ 1481 EXTENSION packets. At this point, bi-directional connectivity is 1482 established. In the third stage, the source and destination can 1483 provide each other with complete source routes, by sending each 1484 other ROUTE_ACCUMULATION packets. As these packets traverse the 1485 route, the cached route information is accumulated in the packets, 1486 thereby constructing the desired source route. 1488 Variations on this IERP implementation can be realized by combining 1489 or eliminating some of these stages. For example, if source routing 1490 is not desired, the ROUTE_ACCUMULATION stage can be eliminated. 1491 Also, if all of the route's nodes elect not to cache the routing 1492 information (perhaps due to storage limitations), then the ROUTE_ 1493 REPLY and QUERY_EXTENSION packets essentially serve the role of 1494 ROUTE_ACCUMULATION packets, obviating the need for a separate 1495 ROUTE_ACCUMULATION stage. 1497 Haas, Pearlman Expires December 1999 [Page 1498 24] 1499 1999 1501 Because each node proactively maintains the local topology of its 1502 routing zone, it is not necessary for a source route to specify 1503 every hop along the route (i.e. strict source routing). A properly 1504 chosen subset of the complete source route can be used to specify 1505 the route to the destination, and where desirable, the reverse route 1506 back to the source. The IERP supports such an optimization through 1507 a final ROUTE_OPTIMIZATION stage. The details of the route 1508 optimization are described in the BRP specification. Upon 1509 completion of the ROUTE_OPTIMIZATION stage, sufficient routing zone 1510 membership is acquired for each node in the route so that the source 1511 route may be reduced (by translating this route reduction into 1512 an appropriate set covering problem, and employing a suitable 1513 heuristic). 1515 +-----+ +-----+ +-----+ 1516 | S | . . . . | Y | . . . | D | 1517 +-----+ +-----+ +-----+ 1519 (1) search for ROUTE_QUERY 1520 route |--------------------------> 1522 (2) establish ROUTE_REPLY EXTENSION 1523 connectivity <--------------------------| 1524 |=============> 1526 (3) provide ROUTE_ACCUMULATION 1527 (OPTIONAL) 1528 source route |----------------------------------------> 1529 <========================================| 1531 (4) optimize ROUTE_OPTIMIZATION 1532 (OPTIONAL) 1533 source route <----------------------------------------| 1534 |========================================> 1536 Sequence of the IERP Route Discovery Stages 1538 Haas, Pearlman Expires December 1999 [Page 1539 25] 1540 1999 1542 A. Packet Format 1543 1 2 3 1544 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 1545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1546 | Type | TTL | Hop Count | Flags | 1547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1548 | Current | ROF Ptr | Num Dests = D | Num Nodes = N | 1549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1550 | Query ID | Reply ID | 1551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1552 | Query/Route Source Address | 1553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1554 | Replying Node Address | 1555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1556 | Bad Link Source Address | 1557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1558 | Query/Route Destination (1) Address | | 1559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1560 | Query/Route Destination (2) Address | | 1561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1562 | | | 1563 | | Dests 1564 \| |/ | 1565 \ / | 1566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1567 | Query/Route Destination (D) Address | | 1568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1569 | Next IERP Address | | 1570 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1571 | Next BRP Address | BRP 1572 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fields 1573 | Prev IERP Address | | 1574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1575 | Intermediate Node (1) Address | | 1576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1577 | Intermediate Node (2) Address | | 1578 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1579 | | 1580 route(1:N) 1581 | | | 1582 \| |/ | 1583 \ / | 1584 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | 1585 | Intermediate Node (N) Address | | 1586 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1587 | Node | Metric Type |D| Metric Value | | 1588 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1589 | Node | Metric Type |D| Metric Value | | 1590 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1591 | | Node/ 1592 | | 1593 Segment 1594 \| |/ 1595 Metric(s) 1596 \ / | 1598 Haas, Pearlman Expires December 1999 [Page 1599 26] 1600 1999 1602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1603 | Node | Metric Type |D| Metric Value | | 1604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1605 | Route Optimization Flags (Node 0 == Source) | | 1606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1607 | Route Optimization Flags (Node 1) | | 1608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1609 | | | 1610 | | R 1611 \| |/ O 1612 \ / F 1613 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1614 | Route Optimization Flags (Node N) | | 1615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1616 | Route Optimization Flags (Node N+1 == Dest) | | 1617 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 1619 Field Description: 1621 * Type (8 bits) 1622 Identifies the type of IERP packet. The current version 1623 of IERP contains five packet types: 1625 ROUTE_QUERY: 1626 request for an Interzone source route to the 1627 destination specified by the Destination 1628 IP Address 1630 QUERY_EXTENSION: 1631 extension of a QUERY packet sent from the 1632 node that discovers the Destination to the 1633 Destination itself. 1635 ROUTE_REPLY: 1636 response to a ROUTE_QUERY packet, sent from the node 1637 that discovers the Destination back to the Source. 1638 At a minimum, the ROUTE_REPLY contains 1639 next-hop route information to the Destination. 1640 (In general, returns the source route up to 1641 the first node which has cached routing 1642 information. If no nodes have cached routing 1643 information, then the complete source route is 1644 returned.) 1646 ROUTE_ACCUMULATION (optional): 1647 sent by the Source to the Destination, in 1648 response to a ROUTE_REPLY, and sent by the 1649 Destination to the Source, in response to a 1650 QUERY_EXTENSION. Routing information cached 1651 at the route's nodes is accumulated in this 1652 packet, providing a complete source route at 1653 the destination of this packet. 1655 Haas, Pearlman Expires December 1999 [Page 1656 27] 1657 1999 1659 ROUTE_OPTIMIZATION (optional): 1660 sent by the Source to the Destination, and by the 1661 Destination to the Source, in response to a 1662 ROUTE_ACCUMULATION packet. Route Optimization 1663 Flags (ROF) are appended to this packet, 1664 reflecting the mutual routing zone membership 1665 of each node in the source route. 1667 * TTL (Time to Live) (8 bits) 1668 Number of hops that a route query may continue to 1669 propagate. This field allows a querying node to 1670 configure the depth of a route search, in order to 1671 control the amount of IERP traffic generated. 1673 * Hop Count (8 bits) 1674 Hop count from source to current node (ROUTE_QUERY, 1675 QUERY_EXTENSION) or hop count from source to route 1676 destination 1677 (ROUTE_REPLY, ROUTE_ACCUMULATION, ROUTE_OPTIMIZATION). 1679 * Flags (8 bits) 1680 Flags(0) ANY destination (0) / ALL destination (1) 1681 In the case of multiple destinations, specifies 1682 whether 1683 the ROUTE_QUERY should return routes for ANY 1684 specified 1685 destination, or ALL specified destinations. 1687 In the case of a single MULTICAST IP address, 1688 specifies 1689 whether the ROUTE_QUERY should return routes to ANY 1690 member of the multicast group, or ALL members of the 1691 multicast group. 1693 Flags(1) Passed Bad Link Source 1694 In the case of a "route repair", indicates whether 1695 the 1696 ROUTE_REPLY has passed the Bad Link Source node. 1698 Flags(2..7) RESERVED for future use 1700 * Current (8 bits) 1701 INDEX of the route (see below) corresponding to the route 1702 node 1703 that has most recently received this packet. (the first 1704 node 1705 in the route has an index of 1). 1707 * ROF Pointer (8 bits) 1708 Pointer to the starting location of the Route Optimization 1709 Flags (ROUTE_OPTIMIZATION phase). The ROF Pointer is 1710 measured 1711 in units of 32 bit words from the front of the packet. 1713 * Number of Destinations = D (8 bits) 1714 Number of destinations included in the route query/reply 1715 packet. 1716 This allows multiple route discoveries to be consolidated 1717 into a common route query process. The multiple query 1718 destinations feature is particularly useful for routing to 1719 a 1720 multicast group with known members, or for locating 1721 downstream 1722 nodes during the route repair phase. 1724 Haas, Pearlman Expires December 1999 [Page 1725 28] 1726 1999 1728 * Number of Nodes = N (8 bits) 1729 Number of nodes IP addresses appearing in the route 1730 specification. 1732 * Query ID (16 bits) 1733 Sequence number which, along with the Query Source Address 1734 (see below) uniquely identifies any ROUTE_QUERY in the 1735 network. 1737 * Reply ID (16 bits) 1738 Sequence number which, along with the Replying Node Address 1739 (see below) uniquely identifies any ROUTE_REPLY in the 1740 network 1742 * Query/Route Source Address (32 bits) 1743 IP address of the node that initiates the ROUTE_QUERY. 1744 In subsequent stages, this corresponds to the IP address of 1745 the 1746 discovered route's source node. 1748 * Replying Node Address (32 bits) 1749 IP address of the node that initiates the ROUTE_REPLY. Note 1750 that this is usually NOT the destination node. 1752 * Bad Link Source Address (32 bits) 1753 Used during route repairs. Contains the IP Address 1754 corresponding to the source of routes failed link. 1756 * Query/Route Destination Addresses (D * 32 bits) 1757 List of IP addresses to be located during the ROUTE_QUERY 1758 phase. 1759 (Either ANY or ALL addresses, depending on the setting of 1760 Flags(0)) 1761 In subsequent stages, this field contains the IP address of 1762 the 1763 discovered route's (single) destination node. 1765 * Next IERP Address (32 bits) 1766 IP address of the next IERP recipient 1768 * Next BRP Address (32 bits) 1769 IP address of the next BRP recipient. 1770 (i.e. next hop to the next IERP recipient) 1772 * Prev IERP Address (32 bits) 1773 IP address of the previous IERP recipient 1775 * Route (N * 32 bits) 1776 Variable length field that contains the recorded IP 1777 addresses 1778 of nodes along the path traveled by this ROUTE_QUERY packet 1779 from the Query Source. 1780 In subsequent stages (after a route to a Query Destination 1781 has 1782 been discovered), this set of IP addresses provides a 1783 partial 1784 specification of the route between the Route Source and 1785 Route 1786 Destination. 1788 Haas, Pearlman Expires December 1999 [Page 1789 29] 1790 1999 1792 * Node/Segment Metrics (X * 32 bits) 1793 This optional section of the packet can be used to 1794 record a variety of node and segment quality measurements. 1795 (In this context, a segment refers to the communication path 1796 between consecutive nodes in the packet's accumulated route. 1797 In the case of neighboring nodes, a segment is equivalent to 1798 a (one-hop) link). 1800 * Node (8 bits) 1801 Index of the route corresponding to a particular node. 1803 * Metric Type (7 bits) 1804 Type of metric being recorded 1805 (based on pre-defined metric types) 1807 * Direction Flag (1 bit) 1808 For segment metrics, specifies either the upstream 1809 segment (toward Query/Route Source) or the downstream 1810 segment (toward Query/Route Dest). 1811 upstream = 0 1812 downstream = 1 1814 * Metric Value (16 bits) 1815 Value of node / segment metric specified by Metric 1816 Type 1818 * ROF (Route Optimization Flags) ((N+2) * 32*ceil((N+2)/32) 1819 bits) 1820 The k-th bit of the n-th ROF subfield indicates whether 1821 Node k is located within Node n's routing zone. 1822 This routing zone membership information, collected 1823 during the optional ROUTE_OPTIMIZATION stage, may be 1824 used to determine the shortest possible specification 1825 for the accumulated source route. 1827 Haas, Pearlman Expires December 1999 [Page 1828 30] 1829 1999 1831 B. Data Structures 1832 B.1 Intrazone Routing Table (See IARP Description) 1834 B.2 Interzone Routing Table 1836 +---------+-----------------------------------------+ 1837 | | Routes | 1838 | Dest +-----------+-----------+-----+-----------+ 1839 | | 0 | 1 | ==> | M-1 | 1840 +---------+-----------+-----------+-----+-----------+ 1841 | | | | ==> | | 1842 |---------|-----------|-----------|-----|-----------| 1843 | | | | ==> | | 1844 |---------|-----------|-----------|-----|-----------| 1845 | | | | | | ==> | | 1846 +---------+----| |----+-----------+-----+-----------+ 1847 | | 1848 | +---\ +------|---|--+--+ +--+ 1849 +-----/ | | | | |...| | --+ (node 1) 1850 +------|---|--+--+ +--+ | 1851 +------------------------------+ 1852 | +------|---|--+--+ +--+ 1853 +->| | | | |...| | --+ (node 2) 1854 +------|---|--+--+ +--+ | 1855 | | : 1856 \| |/ : 1857 : \ / 1858 : 1859 | +------|---|--+--+ +--+ 1860 +->| | | | |...| | (node N) 1861 +------|---|--+--+ +--+ 1862 (a) (b) (c) 1864 (a) Node ID 1865 (b) Required Node Flag 1866 (for Route Optimization) 1867 (c) Node/Link Metric 1869 C. Interfaces 1871 C.1 Higher Layer (N/A) 1872 C.2 Lower Layer (BRP) 1873 C.2.1 Send() (same interface as IP send()) 1874 Used by the IERP to request transmission of an 1875 IERP packet. 1876 C.2.2 Deliver() (same interface as IP deliver()) 1877 Used by the BRP to alert the IERP of the arrival of a 1878 data packet. 1879 C.3 IARP 1880 C.3.1 Zone_Node_Lost(host) 1881 Used by the IARP to notify the IERP that a node has left 1882 the routing zone 1883 C.4 ICMP 1884 C.4.1 Host_Unreachable() (specified in ICMP standard) 1885 C.4.2 Source_Route_Failed() (specified in ICMP standard) 1887 Haas, Pearlman Expires December 1999 [Page 1888 31] 1889 1999 1891 D. State Machine 1893 The IERP protocol consists of only one state (IDLE). Therefore, 1894 no state transitions need to be specified. The IERP immediately 1895 acts upon an event and then returns back to the IDLE state. 1897 Note: 1) X is used as a label for the host running this state 1898 machine. 1900 D.1 1901 Event: A "Zone_Node_Lost" interrupt is received, 1902 indicating that the node H has moved beyond the 1903 routing zone. 1905 Action: Remove every route from the Interzone Routing Table 1906 which contains H. If any routes containing H are 1907 found, then a route repair (limited depth route 1908 discovery) to H is initiated. 1909 D.2 1910 Event: A "Host_Unreachable" interrupt is received from the 1911 ICMP, indicating an unknown destination host D. 1913 Action: A full depth route discovery to D is initiated. 1914 X's query_id is incremented and assigned to a new 1915 ROUTE_QUERY packet. The route is initialized with the 1916 IP addresses of the route's source and destination 1917 IP addresses (X and D). Finally, the ROUTE_QUERY 1918 packet 1919 is bordercasted. 1921 D.3 1922 Event: A "Source_Route_Failed" or "Proactive_Repair" 1923 interrupt is received, indicating that the next 1924 hop, H, specified in a source route does not 1925 appear within the routing zone. 1927 Action: A limited depth route discovery to H is initiated. 1928 The query_id is incremented and assigned to a new 1929 ROUTE_QUERY packet. The route is initialized with the 1930 valid portion of the failed route, and the bad link 1931 address field is set with X's IP address, to indicate 1932 the location of the route failure. 1933 Finally, the ROUTE_QUERY packet is bordercasted. 1934 D.4 1935 Event: A ROUTE_QUERY packet is received with a destination 1936 that 1937 appears within X's routing zone. 1939 Action: X copies the ROUTE_QUERY packet's contents to a 1940 ROUTE_REPLY, labelling it with its IP address and 1941 incremented reply_id. 1942 A QUERY_EXTENSION is sent to the query destination. 1944 D.5 1945 Event: A ROUTE_QUERY packet is received with a destination 1946 that 1947 DOES NOT appear within X's routing zone. 1949 Action: The ROUTE_QUERY packet is bordercasted. 1951 Haas, Pearlman Expires December 1999 [Page 1952 32] 1953 1999 1955 D.6 1956 Event: A QUERY_EXTENSION packet is received. 1958 Action: The packet contents are moved to a ROUTE_ACCUMULATION 1959 packet. The ROUTE_ACCUMULATION packet is sent to the 1960 query source. 1961 D.7 1962 Event: A ROUTE_REPLY packet is received. 1964 Action: The packet contents are moved to a ROUTE_ACCUMULATION 1965 packet. The ROUTE_ACCUMULATION packet is sent to the 1966 query destination. 1968 D.8 1969 Event: A ROUTE_ACCUMULATION packet is received. X is not 1970 the final destination of this packet 1971 (i.e. X != IERP_next). This only occurs when the 1972 accumulated route contains a repair 1974 Action: The bad link is replaced by the path repair in the 1975 Interzone Routing Table. 1977 D.9 1978 Event: A ROUTE_ACCUMULATION packet is received. X is 1979 either the route source or (route destination). 1981 Action: The (reversed) accumulated route is added to the 1982 Interzone Routing Table or replaces a failed route 1983 if the packet specifies a bad link. In addition, 1984 if X is the ROUTE_ACCUMULATION destination, the 1985 packet contents may be moved to a ROUTE_OPTIMIZATION 1986 packet, which is then sent to the query destination 1987 (query source). 1989 D.10 1990 Event: A ROUTE_OPTIMIZATION packet is received. 1992 Action: The routing zone membership information that is 1993 collected in the ROUTE_OPTIMIZATION packet is 1994 processed. The resulting optimized route(s) are 1995 added to the Interzone Routing Table. 1997 E. Pseudocode Implementation 1999 We define two complimentary operations on packets: 2000 extract(packet) and load(packet) 2002 extract (packet) 2003 extracts the fields of the IERP packet to the following 2004 variables: {type, TTL, hop_count, flags, current_hop_ptr, 2005 query_id, reply_id, source, reply_node, 2006 bad_link_source, dests, next_IERP, next_BRP, 2007 prev_IERP, route, metric, ROF} 2009 Haas, Pearlman Expires December 1999 [Page 2010 33] 2011 1999 2013 load (packet) 2014 loads the values of the aforementioned variables into 2015 the fields of the IERP packet. 2016 load(packet) automatically computes the values of: 2017 num_dests = |dests| 2018 num_nodes = |routes| 2020 E.1 Routing Zone Node Lost 2022 {lost_host} <-- intrpt 2023 repair_link = FALSE 2024 for host = each host in Interzone Routing Table 2025 { 2026 for (route = each Interzone route to host) 2027 { 2028 if (lost_host (EXISTS IN) route) 2029 { 2030 if (PROACTIVE_REPAIRS_ENABLED) 2031 { 2032 removal_timer = ROUTE_QUERY_TIMEOUT 2033 repair_link = TRUE 2034 } 2035 else 2036 removal_timer = 0 2037 schedule( 2038 remove(Interzone_Routing_Table[host]->route(m)), 2039 removal_timer) 2040 } 2041 } 2042 } 2043 if(repair_link) 2044 { 2045 dests = lost_host 2046 force_intrpt("IERP","Proactive_Repair",{MY_ID,dests,ALL}) 2047 } 2049 E.2 Initiate Route Discovery 2051 {source,dests,flag} <-- intrpt 2053 if (type(intrpt) == "Proactive_Repair" (OR) 2054 type(intrpt) == "Source_Route_Failed") 2055 { 2056 TTL = MAX_REPAIR_HOPS 2057 bad_link_source = MY_ID 2058 } 2059 else 2060 { 2061 TTL = MAX_FULL_QUERY_HOPS 2062 bad_link_source = NULL 2063 } 2064 query_id = MY_QUERY_ID++ 2065 load (packet) 2066 send (packet, BORDERCAST) 2068 Haas, Pearlman Expires December 1999 [Page 2069 34] 2070 1999 2072 E.3 Receive IERP Packet 2074 extract(packet) 2075 switch(type) 2076 { 2077 case: ROUTE_QUERY 2078 if (dest (EXISTS IN) Intrazone_Routing_Table) 2079 { 2080 type = ROUTE_REPLY 2081 reply_id = MY_REPLY_ID++ 2082 if(bad_link_source) 2083 IERP_next = bad_link_source 2084 else 2085 IERP_next = source 2086 load(packet) 2087 send(packet,IERP_next) 2089 type = QUERY_EXTENSION 2090 IERP_next = dest 2091 load(packet) 2092 send(packet,IERP_next) 2093 } 2094 else 2095 send(packet,BORDERCAST) 2096 break 2097 case: QUERY_EXTENSION 2098 type = ROUTE_ACCUMULATION 2099 IERP_next=source 2100 load(packet) 2101 send(packet, IERP_next) 2102 break 2103 case: ROUTE_REPLY 2104 type = ROUTE_ACCUMULATION 2105 IERP_next = dest 2106 load(packet) 2107 send(packet, IERP_next) 2108 break 2109 case: ROUTE_ACCUMULATION 2110 if (bad_link_source) 2111 { 2112 if(bad_link_source != source) 2113 repair_src_ptr = get_index(route, bad_link_source) 2114 else 2115 repair_src_ptr = 0 2117 bad_link = {bad_link_source,dest} 2118 path_repair = {bad_link_source, 2119 route(repair_src_ptr+1:|route|), 2120 dest} 2121 replace_link(Interzone_Routing_Table,IERP,bad_link, 2122 path_repair) 2123 } 2125 Haas, Pearlman Expires December 1999 [Page 2126 35] 2127 1999 2129 else 2130 { 2131 if (IERP_next == source) 2132 add(Interzone_Routing_Table, IERP, dest, 2133 next_hops,metric) 2134 if (IERP_next == dest) 2135 add(Interzone_Routing_Table, IERP, 2136 source, reverse(prev_hops),metric) 2137 } 2139 if (MY_ID == IERP_next) 2140 { 2141 if (MY_ID == source) 2142 IERP_next = dest 2143 if (MY_ID == dest) 2144 IERP_next = source 2146 type = ROUTE_OPTIMIZATION 2147 load (packet) 2148 send (packet, IERP_next) 2149 } 2150 break 2152 case: ROUTE_OPTIMIZATION 2153 if (MY_ID == source) 2155 add(Interzone_Routing_Table,IERP,dest,route,NO_METRIC,ROF) 2156 if (MY_ID == dest) 2157 add(Interzone_Routing_Table, IERP, source, 2158 reverse(route), NO_METRIC, ROF) 2159 break 2160 } 2162 Haas, Pearlman Expires December 1999 [Page 2163 36] 2164 1999 2166 4.3 Bordercast Resolution Protocol (BRP) 2168 The BRP is a sublayer of the IERP that performs the operations of 2169 bordercasting, query control, route accumulation and routing zone 2170 labelling, which form the basis for the route discovery procedure. 2172 In this BRP implementation, bordercasting is implemented as a series 2173 of unicasted messages to the peripheral nodes. The BRP is able to 2174 identify the peripheral nodes based on the information contained in 2175 the Intrazone Routing Table. Rather than unicasting to the peripheral 2176 node directly through IP, the bordercasted packets are relayed to 2177 the peripheral nodes by the BRP layer. IP is used only to send 2178 these messages one hop toward the peripheral nodes. This allows the 2179 BRP to detect all ROUTE_QUERY packets that are received by that node. 2181 To efficiently terminate the query, the BRP needs to record 2182 sufficient information from each detected query. The query's source 2183 and ID, which serve to uniquely identify a query, are added to the 2184 Detected Queries Table. In addition, the IP address of the last 2185 node to bordercast the query is also recorded in the Detected 2186 Queries table. Any threads of this query that are later received 2187 from a different bordercasting node are discarded. Each query also 2188 contains a hop counter that is decremented at each node. When the 2189 counter expires, the packet is discarded. 2191 IERP packets (excluding ROUTE_OPTIMIZATION packets) that are not 2192 terminated next undergo a route accumulation procedure. As 2193 described earlier, route accumulation is used to construct routes, 2194 by recording the IP addresses of a route's nodes in the IERP packet 2195 or local cache. The Detected Queries Table, extended by two 2196 columns, serves as a convenient route accumulation cache. 2198 The node begins the route accumulation procedure by adding its IP 2199 address to the IERP route. This is followed by the IP addresses of 2200 any cached nodes leading to the packet's destination (the "next 2201 hops"). This is sufficient processing for ROUTE_ACCUMULATION 2202 packets, where complete source routes are constructed. On the other 2203 hand, ROUTE_QUERY, QUERY_EXTENSION and ROUTE_REPLY packets should carry 2204 as 2205 little of the route as possible. Therefore, if cache space is 2206 available, the route accumulation process records the IP addresses 2207 of the "previous hops" from the packet's source, and removes them 2208 from the IERP packet. 2210 The final role of the BRP is to contribute to the ROUTE_OPTIMIZATION 2211 process by indicating the mutual routing zone membership of the 2212 nodes in the source route. This is done by appending a special 2213 flag field to the ROUTE_OPTIMIZATION packet. The status of the 2214 k-th bit in the flag field indicates whether the k-th hop in the 2215 source route is a member of the node's routing zone. This 2216 membership information is eventually processed at the source to 2217 determine the smallest set of routing zones that cover the route 2218 (and therefore the smallest set of nodes needed to specify this 2219 route through loose source routing). 2221 Haas, Pearlman Expires December 1999 [Page 2222 37] 2223 1999 2225 A. Packet Format 2227 See IERP packet format in Section 4.2 2229 B. Data Structures 2231 B.1 Intrazone Routing Table (see IARP description) 2233 B.2 Interzone Routing Table (see IERP description) 2235 B.3 Detected Queries Table 2237 +--------------------+--------+ 2238 | Query | Query | Prev | 2239 | Source | ID | IERP | 2240 |----------+---------|--------| 2241 | | | | 2242 |----------+---------|--------| 2243 | | | | 2244 |----------+---------|--------| 2245 | | | | 2246 +--------------------+--------+ 2248 B.4 Detected Replies Table 2250 +--------------------+ 2251 | Reply | Reply | 2252 | Node | ID | 2253 |----------+---------| 2254 | | | 2255 |----------+---------| 2256 | | | 2257 |----------+---------| 2258 | | | 2259 +--------------------+ 2261 C. Interfaces 2263 C.1 Higher Layer (i.e. IERP) 2264 C.2.1 Send() (same interface as IP Send() primitive) 2265 Used by higher layer protocol to request transmission of 2266 a data packet 2267 C.2.2 Deliver() (same interface as IP Deliver() primitive) 2268 Used by the BRP to alert the higher layer protocol of 2269 the arrival of a data packet 2270 C.2 Lower Layer (IP) 2271 C.2.1 Send() (specified in IP standard) 2272 C.2.2 Deliver() (specified in IP standard) 2274 Haas, Pearlman Expires December 1999 [Page 2275 38] 2276 1999 2278 D. State Machine 2280 The BRP protocol consists of only one state (IDLE). Therefore, 2281 no state transitions need to be specified. The BRP immediately 2282 acts upon an event and then returns back to the IDLE state. 2284 Notes: 1) X is used as a label for the host running this state 2285 machine. 2286 2) NULL is a reserved field value, corresponding to an 2287 invalid IP address. 2289 D.1 2290 Event: A ROUTE_QUERY packet is received from the IERP. 2292 Action: If X is the query's source, then the identifying 2293 querying 2294 information is recorded in the Detected Queries Table. 2295 X adds its IP address to the packet's route. A copy of 2296 the 2297 packet is sent to the IERP layer of each peripheral 2298 node, 2299 by way of a BRP transmission to the next hop to that 2300 peripheral node. 2302 D.2 2303 Event: A ROUTE_QUERY packet is received from the IP. The hop 2304 counter has expired or the query was already 2305 detected from another bordercasting node. 2307 Action: The packet is discarded. 2309 D.3 2310 Event: A ROUTE_QUERY packet is received from IP. The hop 2311 count 2312 has not expired and the query has not been previously 2313 detected (or was detected from the same bordercasting 2314 node). 2315 X is not the intended BRP recipient. 2317 Action: Identifying query information is recorded in the 2318 Detected 2319 Queries Table. The packet is then discarded. 2321 D.4 2322 Event: A ROUTE_QUERY packet is received from the IP. The hop 2323 count has not expired and the query has not been 2324 previously detected (or was previously detected 2325 from the same bordercasting node). X is the 2326 intended BRP recipient, but is not the intended 2327 IERP recipient and the query destination does 2328 not lie within X's routing zone. 2330 Action: The hop counter is decremented. Identifying query 2331 information is recorded in the Detected Queries Table 2332 and accumulated route information is recorded 2333 in the Interzone Routing Table. The recorded route 2334 information is removed from the packet and X adds 2335 its IP address to the route. 2336 The packet is then sent to the BRP of the next hop 2337 to the intended IERP recipient. 2339 Haas, Pearlman Expires December 1999 [Page 2340 39] 2341 1999 2343 D.5 2344 Event: A ROUTE_QUERY packet is received from the IP. The hop 2345 count has not expired and the query has not been 2346 previously detected (or was previously detected 2347 from the same bordercasting node). X is the 2348 intended BRP recipient, and either X is the 2349 intended IERP recipient, OR the query destination 2350 lies in X's routing zone. 2352 Action: The hop counter is decremented. Identifying query 2353 information is recorded in the Detected Queries Table 2354 and accumulated route information is recorded in the 2355 Detected Queries Table. The recorded route information 2356 is removed from the packet and X adds its IP address 2357 to the route. 2358 The packet is then delivered up to the IERP. 2360 D.6 2361 Event: A QUERY_EXTENSION is received from the IERP. 2363 Action: The packet is sent to the BRP layer of the 2364 next hop to the specified IERP recipient 2365 (in this case, the query destination). 2367 D.7 2368 Event: A QUERY_EXTENSION is received from the IP. 2369 X is not the intended BRP recipient. 2371 Action: Identifying query information is recorded in the 2372 Detected Queries Table and accumulated route 2373 information is recorded in the Interzone Routing 2374 Table. 2375 The packet is then discarded. 2377 D.8 2378 Event: A QUERY_EXTENSION packet is received from the IP. 2379 X is the intended BRP recipient, but is not the 2380 intended IERP recipient. 2382 Action: Identifying query information is recorded in the 2383 Detected Queries Table and accumulated route 2384 information is recorded in the Interzone Routing 2385 The recorded route information is removed from the 2386 packet and X adds its IP address to the route. 2387 The packet is then sent to the BRP of the next hop 2388 to the intended IERP recipient. 2390 Haas, Pearlman Expires December 1999 [Page 2391 40] 2392 1999 2394 D.9 2395 Event: A QUERY_EXTENSION packet is received from the IP. 2396 X is the intended BRP recipient and the intended 2397 IERP recipient. 2399 Action: Identifying query information is recorded in the 2400 Detected Queries Table and accumulated route 2401 information is recorded in the Interzone Routing 2402 Table. The recorded route information is removed 2403 from the packet and X adds its IP address to the 2404 route. The packet is then delivered up to the IERP. 2406 D.10 2407 Event: A ROUTE_REPLY packet is received from the IERP. 2409 Action: The IP addresses of X and the previous hops back 2410 to the query source (cached in the Detected Queries 2411 Table) are added to the route. The packet is sent 2412 back to the IERP layer of the query source, by way 2413 of a BRP layer transmission to the first hop back 2414 to the query source. 2416 D.11 2417 Event: A ROUTE_REPLY packet is received from the IP. 2418 X is not the intended BRP recipient or the 2419 ROUTE_REPLY was previously detected. 2421 Action: The packet is discarded. 2423 D.12 2424 Event: A ROUTE_REPLY packet is received from the IP. 2425 X is the intended BRP recipient, but not the 2426 intended IERP recipient. 2427 The ROUTE_REPLY was not previously detected. 2429 Action: Identifying query information is recorded in the 2430 Detected Replies Table and accumulated route 2431 information is recorded in the Interzone Routing 2432 Table. The IP addresses of X and the previous hops 2433 back to the query source (previously recorded in the 2434 Interzone Routing Table) are added to the route. 2435 The packet is then sent to the BRP layer of the 2436 previous hop back to the query source. 2438 D.13 2439 Event: A ROUTE_REPLY packet is received from the IP. 2440 X is the intended BRP recipient and the intended 2441 IERP recipient. 2442 The ROUTE_REPLY was not previously detected. 2444 Action: Identifying query information is recorded in the 2445 Detected Replies Table and accumulated route 2446 information is recorded in the Interzone Routing 2447 Table. The recorded route information is removed 2448 from the packet. The packet is then delivered up 2449 to the IERP. 2451 Haas, Pearlman Expires December 1999 [Page 2452 41] 2453 1999 2455 D.14 2456 Event: A ROUTE_ACCUMULATION packet is received from the IERP. 2458 Action: The packet is sent to the IERP layer of the specified 2459 IERP recipient by way of a BRP transmission to the next 2460 hop toward the IERP recipient. 2462 D.15 2463 Event: A ROUTE_ACCUMULATION packet is received from the IP. 2464 X is not the intended BRP recipient. 2466 Action: The packet is discarded. 2468 D.16 2469 Event: A ROUTE_ACCUMULATION packet is received from the IP. 2470 X is the intended BRP recipient, but not the intended 2471 IERP recipient. 2473 Action: The IP addresses of X and the next hops to the intended 2474 IERP recipient (previously recorded in the Detected 2475 Replies Table) are added to the route. 2476 If this packet contains a route repair and the repair has 2477 already been accumulated, then a copy of the packet is 2478 delivered to the IERP. The packet is then sent to the 2479 BRP 2480 layer of the next hop toward the IERP recipient. 2482 D.17 2483 Event: A ROUTE_ACCUMULATION packet is received from the IP. 2484 X is the intended BRP recipient and the intended 2485 IERP recipient. 2487 Action: The packet is delivered up to the IERP. 2489 D.18 2490 Event: A ROUTE_OPTIMIZATION packet is received from the IERP. 2492 Action: X indicates (in its ROF field) those route nodes that 2493 belong to its routing zone. The packet is then sent to 2494 the IERP layer of the specified IERP recipient, by way 2495 of a BRP transmission to the next hop toward the 2496 IERP recipient. 2498 D.19 2499 Event: A ROUTE_OPTIMIZATION packet is received from the IP. 2500 X is not the intended BRP recipient. 2502 Action: The packet is discarded. 2504 Haas, Pearlman Expires December 1999 [Page 2505 42] 2506 1999 2508 D.20 2509 Event: A ROUTE_OPTIMIZATION packet is received from the IP. 2510 X is the intended BRP recipient, but not the intended 2511 IERP recipient. 2513 Action: X indicates (in its ROF field) those route nodes that 2514 belong to its routing zone. 2515 The packet is then sent to the IERP layer of the 2516 specified next hop toward the IERP recipient. 2518 D.21 2519 Event: A ROUTE_OPTIMIZATION packet is received from the IP. 2520 X is the intended BRP recipient and the intended 2521 IERP recipient. 2523 Action: X indicates (in its ROF field) those route nodes that 2524 belong to its routing zone. The packet is then 2525 delivered up to the IERP. 2527 E. Pseudocode Implementation 2529 We define two complimentary operations on packets: 2530 extract(packet) and load(packet) 2532 extract (packet) 2533 extracts the fields of the IERP packet to the following 2534 variables: {type, TTL, hop_count, flags, current_hop_ptr, 2535 query_id, reply_id, source, reply_node, 2536 bad_link_source, dests, next_IERP, next_BRP, 2537 prev_IERP, route, metric, ROF} 2539 load (packet) 2540 loads the values of the aforementioned variables into 2541 the fields of the IERP packet. 2542 load(packet) automatically computes the values of: 2543 num_dests = |dests| 2544 num_nodes = |routes| 2546 Haas, Pearlman Expires December 1999 [Page 2547 43] 2548 1999 2550 E.1 Receive Packet from IERP 2552 extract(packet) 2554 switch(type) 2555 { 2556 case: ROUTE_QUERY 2557 IERP_prev = MY_ID 2558 if ((bad_link_source == MY_ID (OR) source == MY_ID) 2559 { 2560 if(source != MY_ID) 2561 { 2562 route = reverse(Interzone_Routing_Table(source)) 2563 route = {route, MY_ID} 2564 } 2565 else 2566 route = NULL 2568 current_hop_ptr = |route| 2570 if(bad_link_source) 2571 add(Detected_Queries,{bad_link_source,query_id, 2572 IERP_prev}) 2573 else 2574 add(Detected_Queries,{source,query_id,IERP_prev}) 2575 } 2577 for (IERP_next = each host in Intrazone_Routing_Table) 2578 { 2579 if (IERP_next is a peripheral node) 2580 { 2581 BRP_next=get_shortest_route(Intrazone_Routing_Table, 2582 IERP_next)->next_hop 2583 metric =get_metric(Intrazone_Routing_Table,BRP_next) 2584 load(packet) 2585 send(packet,BRP_next) 2586 } 2587 } 2588 break 2590 case: QUERY_EXTENSION 2591 BRP_next=get_shortest_route(Intrazone_Routing_Table, 2592 IERP_next)->next_hop 2593 load(packet) 2594 send(packet,BRP_next) 2595 break 2597 Haas, Pearlman Expires December 1999 [Page 2598 44] 2599 1999 2601 case: ROUTE_REPLY 2602 prev_hops = route(1: current_hop_ptr-1) 2603 next_hops = route(current_hop_ptr+1 : |route|) 2604 if (prev_hops(1) == MY_ID) 2605 { 2606 prev_hops=reverse(Interzone_Routing_Table[IERP_next]) 2608 if(prev_hops(1) == IERP_next (OR) prev_hops == NULL) 2609 { 2610 prev_hops = NULL 2611 BRP_next = IERP_next 2612 } 2613 else 2614 BRP_next = prev_hops(|prev_hops|) 2615 } 2616 else 2617 BRP_next = prev_hops(|prev_hops|) 2619 if (!is_neighbor(Intrazone_Routing_Table, BRP_next)) 2620 { 2621 prev_hops={prev_hops,get_route(Intrazone_Routing_Table, 2622 BRP_next)} 2623 BRP_next = prev_hops(|prev_hops|) 2624 } 2626 metric =get_metric(Intrazone_Routing_Table,BRP_next) 2627 current_hop_ptr = |prev_hops|+1 2628 route = {prev_hops, MY_ID, next_hops} 2629 load(packet) 2630 send(packet,BRP_next) 2631 break 2633 case: ROUTE_ACCUMULATION 2634 if(IERP_next == source) 2635 { 2636 BRP_next = route(|route|) 2637 current_hop_ptr = |route|+1 2638 } 2639 if(IERP_next == dest) 2640 { 2641 BRP_next = route(1) 2642 current_hop_ptr = 0 2643 } 2644 load(packet) 2645 send(packet,BRP_next) 2646 break 2648 Haas, Pearlman Expires December 1999 [Page 2649 45] 2650 1999 2652 case: ROUTE_OPTIMIZATION 2653 ROF = NULL 2654 for (node = {source,route,dest}) 2655 { 2656 if ((EXISTS) Intrazone_Routing_Table[node]) 2657 ROF = {ROF,1} 2658 else 2659 ROF = {ROF,0} 2660 } 2661 if(IERP_next == dest) 2662 { 2663 BRP_next = route(1) 2664 current_hop_ptr = 0 2665 } 2666 if(IERP_next == source) 2667 { 2668 BRP_next = route(|route|) 2669 current_hop_ptr = |route|+1 2670 } 2671 load(packet) 2672 send(packet,BRP_next) 2673 break 2675 E.2 Receive Packet from IP 2677 extract(packet) 2679 switch(type) 2680 { 2681 case ROUTE_QUERY: 2682 if (TTL > 0 (AND) 2683 (!EXISTS(Detected_Queries[source,query_id] (OR) 2684 Detected_Queries[source,query_id]->from == IERP_prev)) 2685 { 2686 TTL-- 2687 hop_count++ 2688 prev_hops = route(1 : current_hop_ptr) 2689 next_hops = route(current_hop_ptr+1 : |route|) 2691 if(bad_link_source) 2692 { 2694 add(Detected_Queries,{bad_link_source,query_id,IERP_prev}) 2695 status = 2696 add(Interzone_Routing_Table,BRP,bad_link_source, 2697 prev_hops,metric) 2698 } 2699 else 2700 { 2701 add(Detected_Queries,{source,query_id,IERP_prev}) 2702 status = add(Interzone_Routing_Table,BRP,source, 2703 prev_hops,metric) 2704 } 2706 Haas, Pearlman Expires December 1999 [Page 2707 46] 2708 1999 2710 if (status == RECORDED_ROUTE) 2711 { 2712 prev_hops = NULL 2713 metric = compress_metric(metric) 2714 } 2715 route = {prev_hops, MY_ID, next_hops} 2716 current_hop_ptr = |prev_hops|+1 2718 if(BRP_next == MY_ID) 2719 { 2720 if(IERP_next == MY_ID) 2721 { 2722 load(packet) 2723 deliver(packet,IERP) 2724 } 2725 else 2726 { 2727 d = dests (BELONGING TO) Intrazone_Routing_Table 2728 if(|d| > 0) 2729 { 2730 load(packet) 2731 deliver(packet,IERP) 2732 } 2734 if((|d| == 0) (OR) 2735 (|d| < |dests| (AND) flag(0) == ALL)) 2736 { 2737 BRP_next=get_shortest_route( 2738 Intrazone_Routing_Table, 2739 IERP_next)->next_hop 2741 metric = {metric,get_metric( 2742 Intrazone_Routing_Table, 2743 BRP_next)} 2744 load(packet) 2745 send(packet, BRP_next) 2746 } 2747 } 2748 } 2749 else 2750 discard(packet) 2751 } 2752 else 2753 { 2754 if(bad_link_source) 2756 add(Detected_Queries,{bad_link_source,query_id,IERP_prev}) 2757 else 2758 add(Detected_Queries,{source,query_id,IERP_prev}) 2760 discard(packet) 2761 } 2762 break 2764 Haas, Pearlman Expires December 1999 [Page 2765 47] 2766 1999 2768 case QUERY_EXTENSION: 2769 if (!EXISTS(Detected_Replies[reply_node,reply_id]) 2770 { 2771 hop_count++ 2772 prev_hops = route(1: current_hop_ptr) 2773 next_hops = route(current_hop_ptr+1 : |route|) 2775 if(bad_link_source) 2776 { 2778 add(Detected_Queries,{bad_link_source,query_id,IERP_prev}) 2779 status = 2780 add(Interzone_Routing_Table,BRP,bad_link_source, 2781 prev_hops,metric) 2782 } 2783 else 2784 { 2785 add(Detected_Queries,{source,query_id,IERP_prev}) 2786 status = add(Interzone_Routing_Table,BRP,source, 2787 prev_hops,metric) 2788 } 2790 if (status == RECORDED_ROUTE) 2791 { 2792 prev_hops = NULL 2793 metric = compress_metric(metric) 2794 } 2796 route = {prev_hops, MY_ID, next_hops} 2797 current_hop_ptr = |prev_hops|+1 2799 if(BRP_next == MY_ID) 2800 { 2801 if(IERP_next == MY_ID) 2802 { 2803 load(packet) 2804 deliver(packet,IERP) 2805 } 2806 else 2807 { 2809 BRP_next=get_shortest_route(Intrazone_Routing_Table, 2810 IERP_next)->next_hop 2811 metric = 2812 {metric,get_metric(Intrazone_Routing_Table, 2813 BRP_next)} 2814 load(packet) 2815 send(packet, BRP_next) 2816 } 2817 } 2818 else 2819 discard(packet) 2820 } 2821 else 2822 discard(packet) 2823 break 2825 Haas, Pearlman Expires December 1999 [Page 2826 48] 2827 1999 2829 case ROUTE_REPLY: 2830 if(MY_ID == BRP_next (AND) 2831 !EXISTS(Detected_Queries[source,query_id])) 2832 { 2833 prev_hops = route(1: current_hop_ptr-1) 2834 next_hops = route(current_hop_ptr : |route|) 2835 add(Detected_Replies, {reply_node,reply_id}) 2836 status=add(Interzone_Routing_Table,BRP,dest, 2837 next_hops,metric) 2838 if (status == RECORDED_ROUTE) 2839 { 2840 next_hops = NULL 2841 metric = compress_metric(metric) 2842 } 2844 if (prev_hops(1) == MY_ID) 2845 { 2846 prev_hops=reverse(Interzone_Routing_Table[IERP_next]) 2848 if(prev_hops(|prev_hops|) == IERP_next (OR) 2849 prev_hops == NULL) 2850 { 2851 prev_hops = NULL 2852 BRP_next = IERP_next 2853 } 2854 else 2855 BRP_next = prev_hops(|prev_hops|) 2856 } 2857 else 2858 BRP_next = prev_hops(|prev_hops|) 2860 if (!is_neighbor(Intrazone_Routing_Table, BRP_next)) 2861 { 2863 prev_hops={prev_hops,get_route(Intrazone_Routing_Table, 2864 BRP_next)} 2865 BRP_next = prev_hops(|prev_hops|) 2866 } 2867 if(MY_ID == IERP_next) 2868 { 2869 current_hop_ptr = 0 2870 load(packet) 2871 deliver(packet,IERP) 2872 } 2873 else 2874 { 2875 metric = {metric,get_metric(Intrazone_Routing_Table, 2876 BRP_next)} 2877 route = {prev_hops, MY_ID, next_hops} 2878 current_hop_ptr = |prev_hops|+1 2879 load(packet) 2880 send(packet,BRP_next) 2881 } 2882 } 2883 else 2884 discard(packet) 2885 break 2887 Haas, Pearlman Expires December 1999 [Page 2888 49] 2889 1999 2891 case ROUTE_ACCUMULATION: 2892 if(MY_ID == BRP_next) 2893 { 2894 if(IERP_next == source) 2895 { 2896 prev_hops = route(1: current_hop_ptr-1) 2897 next_hops = route(current_hop_ptr : |route|) 2899 if (prev_hops(1) == MY_ID) 2900 { 2902 prev_hops=reverse(Interzone_Routing_Table[IERP_next]) 2904 if(prev_hops(1) == IERP_next (OR) prev_hops == NULL) 2905 { 2906 prev_hops = NULL 2907 BRP_next = IERP_next 2908 } 2909 else 2910 BRP_next = prev_hops(|prev_hops|) 2911 } 2912 else 2913 BRP_next = prev_hops(|prev_hops|) 2915 if(MY_ID == bad_link_source) 2916 flags(1) = 1 2917 } 2919 if(IERP_next == dest) 2920 { 2921 prev_hops = route(1: current_hop_ptr) 2922 next_hops = route(current_hop_ptr+1 : |route|) 2924 if (next_hops(|next_hops|) == MY_ID) 2925 { 2926 next_hops=Interzone_Routing_Table[IERP_next]) 2928 if(next_hops(|next_hops|) == IERP_next (OR) 2929 next_hops == NULL) 2930 { 2931 next_hops = NULL 2932 BRP_next = IERP_next 2933 } 2934 else 2935 BRP_next = next_hops(1) 2936 } 2937 else 2938 BRP_next = next_hops(1) 2939 } 2941 Haas, Pearlman Expires December 1999 [Page 2942 50] 2943 1999 2945 if(MY_ID == IERP_next) 2946 { 2947 load(packet) 2948 deliver(packet, IERP) 2949 } 2950 else 2951 { 2952 if(flags(1) == 1) 2953 { 2954 load(packet) 2955 deliver(packet, IERP) 2956 } 2957 metric = {metric,get_metric(Intrazone_Routing_Table, 2958 BRP_next)} 2959 route = {prev_hops, MY_ID, next_hops} 2960 current_hop_ptr = |prev_hops|+1 2961 load(packet) 2962 send (packet,BRP_next) 2963 } 2964 } 2965 else 2966 discard(packet) 2967 break 2969 case ROUTE_OPTIMIZATION: 2970 if(MY_ID == BRP_next) 2971 { 2972 f = NULL 2973 for (node = {source,route,dest}) 2974 { 2975 if ((EXISTS) Intrazone_Routing_Table[node]) 2976 f = {f,1} 2977 else 2978 f = {f,0} 2979 } 2981 if (IERP_next == source) 2982 { 2983 current_hop_ptr-- 2984 prev_hops = route(1: current_hop_ptr-1) 2985 next_hops = route(current_hop_ptr+1 : |route|) 2986 BRP_next = prev_hops(|prev_hops|) 2987 ROF = {f,ROF} 2988 } 2989 if (IERP_next == dest) 2990 { 2991 current_hop_ptr++ 2992 prev_hops = route(1: current_hop_ptr-1) 2993 next_hops = route(current_hop_ptr+1 : |route|) 2994 BRP_next = next_hops(1) 2995 ROF = {ROF,f} 2996 } 2998 Haas, Pearlman Expires December 1999 [Page 2999 51] 3000 1999 3002 if(MY_ID == IERP_next) 3003 { 3004 load(packet) 3005 deliver(packet, IERP) 3006 } 3007 else 3008 { 3009 load(packet) 3010 send (packet,BRP_next) 3011 } 3012 } 3013 else 3014 discard(packet) 3015 break 3017 Haas, Pearlman Expires December 1999 [Page 3018 52] 3019 1999 3021 5. Other Considerations 3023 5.1 Sizing the Zone Radius 3025 The performance of the Zone Routing Protocol is determined by the 3026 routing zone radius. In general, dense networks consisting of a few 3027 fast moving nodes favor smaller routing zones. On the other hand, a 3028 sparse network of many slowly moving nodes operates more efficiently 3029 with a larger zone radius. 3031 The simplest approach to configuring the routing zone radius is to 3032 make the assignment once, prior to deploying the network. This can 3033 be performed by the network administration, if one exists, or by 3034 the manufacturer, as a default value. This may provide acceptable 3035 performance, especially in situations where network characteristics 3036 do not vary greatly over space and time. Alternatively, the ZRP can 3037 adapt to changes in network behavior, through dynamic configuration 3038 of the zone radius [3]. In [4], it was shown that a node can accurately 3039 estimate its optimal zone radius, on-line, based on local measurements of 3040 ZRP traffic. The re-sizing of the routing zone can be carried out by a 3041 protocol that conveys the change in zone radius to the members of the 3042 routing zone. The details of such an update protocol will be provided in 3043 a future version of this draft. 3045 5.2 Hierarchical Routing and the ZRP 3047 In a hierarchical network architecture, network nodes are organized into 3048 a 3049 smaller number of (often disjoint) clusters. This routing hierarchy is 3050 maintained by two component routing protocols. An intra-cluster protocol 3051 provides routes between nodes of the same cluster, while an inter-cluster 3052 protocol operates globally to provide routes between clusters. 3054 The ZRP, with its routing zones and intrazone / interzone routing 3055 protocol 3056 (IARP/IERP) architecture may give the appearance of being a hierarchical 3057 routing protocol. In actuality, the ZRP is a flat routing protocol. 3058 Each 3059 node maintains its own routing zone, which heavily overlaps with the 3060 routing 3061 zones of neighboring nodes. Because there is a one-to-one correspondence 3062 between nodes and routing zones, the routing zones, unlike hierarchical 3063 clusters, do not serve to hide the details of local network topology. 3064 As a result, the network-wide interzone routing protocol (IERP) actually 3065 determines routes between individual nodes, rather than just between 3066 higher 3067 level network entities. 3069 Haas, Pearlman Expires December 1999 [Page 3070 53] 3071 1999 3073 For small to moderately sized networks, flat routing protocols, like the 3074 ZRP, are preferable to hierarchical routing protocols. In order for 3075 a node to be located, its address needs to reflect the node's location 3076 within the network hierarchy (ie. {cluster id,node id}). Because of 3077 node mobility, a node's cluster membership (and thus address) is subject 3078 to change. This complicates mobility management, for the benefit of more 3079 efficient routing. In many hierarchical routing protocols, each cluster 3080 designates a single clusterhead node to relay inter-cluster traffic. 3081 These 3082 clusterhead nodes become traffic "hot-spots", potentially resulting in 3083 network congestion and single point of failure. Furthermore, restricting 3084 cluster access through clusterhead nodes can lead to sub-optimal routes, 3085 as potential neighbors in different clusters are prohibited from 3086 communicating directly. Some hieararchical routing protocols, such 3087 as the Zone-Based Hiearchical Link-State (ZHLS) [5], avoid these problems 3088 by distributing routing information to all cluster nodes, rather than 3089 maintaining a single clusterhead. 3091 In spite of these disadvantages, hierarchical routing protocols are often 3092 better suited for very large networks than flat routing protocols. 3093 Because hierarchical routing protocols provide global routes to network 3094 clusters, rather than individual nodes, routing table storage is more 3095 scalable. Similarly, the amount of route update messages is also more 3096 scalable. To some extent, the reduction in routing traffic is offset 3097 by extra mobility management overhead (i.e. identifying which cluster 3098 a node belongs to). However, it is quite common that the environment or 3099 existing organizational structure causes nodes to naturally cluster 3100 together. In these cases, there may be high degree of intra-cluster 3101 mobility, inter-cluster mobility is less common. 3103 A hierarchical routing protocol can be viewed as a set of flat routing 3104 protocols, each operating at different levels of granularity. In a two- 3105 tier routing protocol, the inter-cluster components is essentially a 3106 flat routing protocol that computes routes between clusters. Likewise, 3107 the intra-cluster component is a flat routing protocol, that computes 3108 routes 3109 between nodes in each cluster. For example, the Near Term Digital Radio 3110 (NTDR) System [12] and ZHLS both employ proactive link state protocols to 3111 determine inter and intracluster connectivity. 3113 In place of traditional proactive or reactive protocols, we recommend 3114 that the intra-cluster and inter-cluster routing protocol components 3115 be implemented based on the hybrid proactive/reactive ZRP. As described 3116 throughout this draft, the ZRP is designed to provide an optimal balance 3117 between purely proactive and reactive routing. This applies equally well 3118 to routing between nodes at the intra-cluster level and between clusters 3119 at 3120 the inter-cluster level. Additionally, the hybrid ZRP methodology can 3121 be applied to the related mobility management protocols, which determine 3122 complete node addresses based on a node's location in the network 3123 hierarchy. 3125 Haas, Pearlman Expires December 1999 [Page 3126 54] 3127 1999 3129 6.0 References 3131 [1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable 3132 Wireless Networks," ICUPC'97, San Diego, CA, Oct. 12,1997. 3134 [2] Haas, Z.J. and Pearlman, M.R., "The Performance of Query 3135 Control Schemes for the Zone Routing Protocol," 3136 SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998. 3138 [3] Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design 3139 Choices in Ad-Hoc Communications," MILCOM'98, Boston, MA, 3140 October 18-21, 1998. 3142 [4] Haas, Z.J. and Pearlman, M.R., "Determining the Optimal 3143 Configuration for the Zone Routing Protocol," to appear 3144 in IEEE JSAC issue on Ad-Hoc Networks, June, 1999. 3146 [5] Joa-Ng, M. and Lu, I.T., "A Peer-to-Peer Zone-based Two-Level 3147 Link State Routing for Mobile Ad-Hoc Networks," to appear 3148 in IEEE JSAC issue on Ad-Hoc Networks, June, 1999. 3150 [6] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing 3151 in Ad-Hoc Wireless Networks," in Mobile Computing, 3152 edited by T. Imielinski and H. Korth, chapter 5, 3153 pp. 153-181, Kluwer, 1996. 3155 [7] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, 3156 RFC 2178, July 1997. 3158 [8] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient 3159 Routing Protocol for Wireless Networks," MONET, vol. 1, 3160 no. 2, pp. 183-197, October 1996. 3162 [9] Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed 3163 Routing Algorithm for Mobile Wireless Networks," 3164 IEEE INFOCOM'97, Kobe, Japan, 1997. 3166 [10] Perkins, C.E., and Bhagwat, P., "Highly Dynamic 3167 Destination-Sequenced Distance-Vector Routing (DSDV) for 3168 Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994. 3170 [11] Perkins, C.E. and Royer, E.M., "Ad-Hoc On-Demand Distance 3171 Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 3173 [12] Ruppe, R., Griswald, S., Walsh, P. and Martin, R., "Near Term 3174 Digital Radio (NTDR) System," IEEE MILCOM'97, Monterey, CA, 3175 Nov. 1997. 3177 [13] Waitzman, D., Partridge, C., Deering, S.E., "Distance 3178 Vector Multicast Routing Protocol," RFC 1075, Nov. 1, 1988. 3180 Haas, Pearlman Expires December 1999 [Page 3181 55] 3182 1999 3184 Authors' Information 3186 Zygmunt J. Haas 3187 Wireless Networks Laboratory 3188 323 Frank Rhodes Hall 3189 School of Electrical Engineering 3190 Cornell University 3191 Ithaca, NY 14853 3192 United States of America 3193 tel: (607) 255-3454, fax: (607) 255-9072 3194 Email: haas@ee.cornell.edu 3196 Marc R. Pearlman 3197 389 Frank Rhodes Hall 3198 School of Electrical Engineering 3199 Cornell University 3200 Ithaca, NY 14853 3201 United States of America 3202 tel: (607) 255-0236, fax: (607) 255-9072 3203 Email: pearlman@ee.cornell.edu 3205 The MANET Working Group contacted through its chairs: 3207 M. Scott Corson 3208 Institute for Systems Research 3209 University of Maryland 3210 College Park, MD 20742 3211 (301) 405-6630 3212 corson@isr.umd.edu 3214 Joseph Macker 3215 Information Technology Division 3216 Naval Research Laboratory 3217 Washington, DC 20375 3218 (202) 767-2001 3219 macker@itd.nrl.navy.mil 3221 Haas, Pearlman Expires December 1999 [Page 3222 56]