idnits 2.17.1 draft-ietf-manet-zone-brp-00.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-20) 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: ---------------------------------------------------------------------------- == 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 0) being 742 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 64 instances of too long lines in the document, the longest one being 4 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 49 has weird spacing: '... [Page i]...' == Line 77 has weird spacing: '... [Page ii]...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (January 2001) is 8496 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- No information found for draft-ietf-manet-iarp - is the name correct? -- Possible downref: Normative reference to a draft: ref. '2' -- No information found for draft-ietf-manet-ierp - is the name correct? -- Possible downref: Normative reference to a draft: ref. '3' -- No information found for draft-ietf-manet-zrp - is the name correct? -- Possible downref: Normative reference to a draft: ref. '4' == Outdated reference: A later version (-11) exists of draft-ietf-manet-olsr-03 ** Downref: Normative reference to an Experimental draft: draft-ietf-manet-olsr (ref. '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' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- Possible downref: Non-RFC (?) normative reference: ref. '14' Summary: 8 errors (**), 0 flaws (~~), 5 warnings (==), 17 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Zygmunt J. Haas, Cornell University 2 Marc R. Pearlman, Cornell University 3 Prince Samar, Cornell University 5 Expires in six months on July 2001 January 2001 7 The Bordercast Resolution Protocol (BRP) for Ad Hoc Networks 8 10 Status of this Memo 12 This document is an Internet-Draft and is NOT offered in accordance 13 with Section 10 of RFC2026, and the author does not provide the IETF 14 with any rights other than to publish as an Internet-Draft. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference material 23 or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Distribution of this memo is unlimited. 33 Abstract 35 The Bordercast Resolution Protocol (BRP) provides the bordercasting 36 packet delivery service used to support network querying applications. 37 The BRP uses a map of an extended routing zone, provided by the local 38 proactive Intrazone Routing Protocol (IARP), to construct bordercast 39 (multicast) trees, along which query packets are directed. Within the 40 context of the hybrid ZRP, the BRP is used to guide the route requests 41 of the global reactive Interzone Routing Protocol (IERP). The BRP 42 employs special query control mechanisms to steer route requests away 43 from areas of the network that have already been covered by the query. 44 The combination of multicasting and zone based query control makes 45 bordercasting an efficient and tunable service that is more suitable 46 than flood searching for network probing applications like route 47 discovery. 49 Haas, Pearlman, Samar Expires July 2001 [Page i] 50 Contents 52 Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i 53 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i 55 Applicability Statement . . . . . . . . . . . . . . . . . . . iii 56 A. Networking Context . . . . . . . . . . . . . . . . . iii 57 B. Protocol Characteristics and Mechanisms . . . . . . . iii 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 61 2. Routing Zone Based Querying . . . . . . . . . . . . . . . . 2 63 3. Query Control Mechanisms . . . . . . . . . . . . . . . . . 3 65 4. Bordercast Resolution Protocol (BRP) Implementation . . . . 4 66 A. Packet Format . . . . . . . . . . . . . . . . . . . . . 5 67 B. Data Structures . . . . . . . . . . . . . . . . . . . . 6 68 C. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 6 69 D. State Machine . . . . . . . . . . . . . . . . . . . . . 7 70 E. Pseudocode Implementations . . . . . . . . . . . . . . . 8 72 5. References . . . . . . . . . . . . . . . . . . . . . . . . 11 74 Authors' Information . . . . . . . . . . . . . . . . . . . . . 13 75 MANET Contact Information . . . . . . . . . . . . . . . . . . . 13 77 Haas, Pearlman, Samar Expires July 2001 [Page ii] 78 Applicability Statement 80 A. Networking Context 82 Bordercasting is an efficient multicast packet delivery service used 83 for guiding queries through the network. When each node proactively 84 tracks the topology of its surrounding extended routing zone, queries 85 can be directed to the edge of the node's routing zone rather than 86 blindly being relayed to *all* neighbors. Special routing zone based 87 query control mechanisms steer query packets away from regions of the 88 network that have already been covered by the query. 90 Within the context of ad hoc network routing, bordercasting is 91 proposed as a more efficient and tunable alternative to broadcasting 92 of route request messages for reactive (on-demand) routing protocols. 93 We refer to any reactive routing protocol that bordercasts route 94 requests as an Interzone Routing Protocol (IERP). The link state 95 information needed to support bordercasting is provided by a local 96 proactive Intrazone Routing Protocol (IARP). Thus, a routing protocol 97 based on bordercasting is actually hybrid reactive/proactive. For a 98 properly chosen routing zone radius, IARP's cost of tracking routing 99 zone topology is more than justified by the resulting savings in route 100 discovery overhead through bordercasting. 102 B. Protocol Characteristics and Mechanisms 104 The Bordercast Resolution Protocol (BRP) is a packet delivery service, 105 not a full featured routing protocol. Bordercasting is enabled by a 106 local proactive Intrazone Routing Protocol (IARP) and supports a 107 global reactive Interzone Routing Protocol (IERP). The character- 108 istics of the IARP and IERP are summarized in their corresponding 109 Internet drafts. 111 1. Introduction 113 The design of ad hoc network routing protocols is influenced by link 114 instability (due to node mobility) and limitations in available 115 bandwidth and transmission power. Traditional wired networks use 116 proactive routing protocols, like OSPF [7] and RIP [15], to maintain 117 up-to-date routes to all networks nodes. More efficient proactive 118 routing protocols have been developed for ad hoc networks [1][5][8] 119 [9][14]. However, continuously tracking the frequent topology changes 120 in a practical ad hoc network can still produce an overwhelming amount 121 of control traffic. Even worse, most of the acquired route 122 information expires before it is ever used, making the proactive 123 control traffic a poor investment of bandwidth. In contrast, reactive 124 routing protocols [6][10][13] only initiate a global, query-based, 125 route discovery as routes are needed. While some delay is incurred 126 for route acquisition, the amount of overhead traffic is generally 127 much less than proactive routing protocols, because routing information 128 is not wasted. For this reason, reactive protocols are generally 129 viewed as being more suitable than proactive routing protocols for the 130 power/bandwidth limited mobile ad hoc network. 132 Although a global proactive routing protocol may overwhelm an ad hoc 133 network's resources, a LIMITED SCOPE proactive routing protocol can 134 be used to benefit a global reactive routing protocol. 135 This hybrid routing approach forms the basis for the Zone Routing 136 Protocol (ZRP) framework [4]. 138 The cost for each node to proactively track the topology of its 139 surrounding R-hop neighborhood (routing zone) can be justified by 140 improved route discovery efficiency and more effective route 141 maintenance [11][12]. Routes to local destinations are immediately 142 available, avoiding route discoveries. When the global route 143 discovery is needed, the routing zones can be used to efficiently 144 guide route queries outward through bordercasting, rather than blindly 145 relaying queries from neighbor to neighbor. The proactive maintenance 146 of routing zones also helps improve the quality and survivability of 147 discovered routes, by making them more robust to changes in network 148 topology. Once routes have been discovered, routing zone offers 149 enhanced, real-time, route maintenance. Link failures can be bypassed 150 by multiple hop paths within the routing zone. Similarly, sub-optimal 151 route segments can be identified and traffic re-routed along shorter 152 paths. 154 Haas, Pearlman, Samar Expires July 2001 [Page 1] 155 The bordercasting packet delivery service is provided by the 156 Bordercast Resolution Protocol (BRP). The BRP uses a map of an 157 extended routing zone, provided by the local proactive Intrazone 158 Routing Protocol (IARP) [2], to construct bordercast (multicast) trees 159 along which query packets are directed. (Within the context of the 160 hybrid ZRP, the BRP is used to guide the route requests of the global 161 reactive Interzone Routing Protocol (IERP) [3]). The BRP employs 162 special query control mechanisms to steer route requests away from 163 areas of the network that have already been covered by the query. The 164 combination of multicasting and zone based query control makes 165 bordercasting an efficient and tunable service that is more suitable 166 than flood searching for network probing applications like route 167 discovery. 169 2. Routing Zone Based Querying 171 We illustrate the basic operation of routing zone based route 172 discovery through a simple (but as we will see, inefficient) IERP 173 implementation. The source node, in need of a route to a destination 174 node, first checks whether the destination lies within its routing 175 zone. (This is possible since every node knows the content of its 176 routing zone). If a path to the destination is known, no further 177 route discovery processing is required. On the other hand, if the 178 destination is not within the source's routing zone, the source 179 bordercasts a route query to all of its peripheral nodes. Upon 180 receipt of the route query, each peripheral nodes executes the same 181 algorithm. If the destination lies within its routing zone, a route 182 reply is sent back to the source, indicating the route to the 183 destination. If not, this node forwards the query to ITS peripheral 184 nodes. This process continues until the query has spread throughout 185 the network. 187 +---+ 188 +---+ | F | 189 +---+---| C |----+---+-----+---+ +---+ 190 | D | +---+ | E |----| H | 191 +---+ | +---+-----+---+ +---+ 192 +---+----| B | | 193 | A | +---+-----+---+ +---+ 194 +---+ | G | | I | 195 +---+ +---+ 196 | 197 +---+ 198 +---+ | J | 199 | C |----+---+----+---+ +---+ 200 +---+ | K |----| L | 201 +---+ +---+ 203 Haas, Pearlman, Samar Expires July 2001 [Page 2] 204 In the example illustrated above, node A has data to send to node L. 205 Assuming each node's zone radius is 2 hops, node L does not lie within 206 A's routing zone (which does include B,C,D,E,F,G). Therefore, A 207 bordercasts a routing query to its peripheral nodes: D,F,E and G. 208 Each one of these peripheral nodes checks whether L exists in its 209 routing zone. Since L is not found in any of these nodes routing 210 zones, the nodes bordercast the request to their peripheral nodes. 211 In particular, G bordercasts to K, which recognizes that L is in its 212 routing zone and returns the requested route (L-K-G-A) to the query 213 source (A). 215 The one-to-many nature of bordercasting lends itself to a multicast 216 implementation. One approach is for a node to compute its bordercast 217 (multicast) tree and append the corresponding packet forwarding 218 instructions to the bordercast packet. Alternatively, each node may 219 re-construct the bordercast tree of its interior routing zone members, 220 by proactively maintaining the topology of an "extended" zone. In 221 particular, if IARP maintains an "extended" routing zone of radius 222 2R-1 hops (while queries are still directed at peripheral nodes of an 223 "inner" routing zone of radius R hops), bordercast messages can be 224 relayed without the need for explicit directions from the bordercast 225 source. 227 3. Query Control Mechanisms 229 Bordercasting has the potential to provide global querying that is 230 more efficient than flooding. To achieve this efficiency, the 231 protocol should be able to terminate a query packet *before* it is 232 delivered to a peripheral node in a region of the network already 233 covered by the query. The capability of providing this level of 234 query control is significantly limited when bordercast messages are 235 relayed to peripheral nodes over multiple hops by the network layer. 237 To prevent redundant querying, nodes should be able to detect when the 238 routing zones that they belong to have been covered by a query. 239 Clearly, a node that bordercasts a route query is aware that its own 240 zone has been covered. If bordercast queries are relayed by IP, then 241 the query will not be detected again until it reappears at the target 242 peripheral nodes. On the other hand, if query forwarding is performed 243 within the routing protocol, then all nodes in the bordercast tree will 244 detect the query (QD1). Further query detection is possible in shared 245 channel networks if the underlying MAC layer packet delivery is through 246 neighbor broadcast or if promiscuous mode operation is enabled. In 247 this case, nodes may "overhear" a query even if they do not belong to 248 the bordercast tree (QD2). 250 Haas, Pearlman, Samar Expires July 2001 [Page 3] 251 Standard flood search protocols terminate query packets that are 252 targeted for (or arrive at) previously queried *nodes*. We can extend 253 this idea to the BRP by discarding route queries before they arrive at 254 targeted peripheral nodes belonging to a previously queried *routing 255 zone*. More precisely, a node will not relay a packet down a branch 256 of the bordercast tree if each of the branch's downstream "leaves" 257 (peripheral nodes) either lies inside the routing zone of a previous 258 bordercasted node, or if this node has already relayed the query to 259 that peripheral node. This scheme, which we refer to as Early 260 Termination (ET), relies on the aforementioned Query Detection to 261 identify which routing zone nodes have already bordercast a query. 262 The "extended" routing zone maintained by the IARP is then used to 263 determine the members of these previously bordercasted nodes' routing 264 zones. 266 4. Bordercast Resolution Protocol (BRP) Implementation 268 The BRP provides the "bordercasting" packet delivery service, here 269 used to forward IERP route queries. Queries are relayed from a 270 bordercasting node outward to its peripheral nodes, along a 271 bordercast (multicast) tree. Although the intended targets of 272 the bordercast are the peripheral nodes, the BRP delivers the 273 bordercast query up to the higher layer application (eg. the IERP) 274 at EVERY hop. This is necessary for applications that use 275 bordercasting, but are generally not "routing zone aware". 277 When the BRP receives a bordercast query packet, it marks the interior 278 nodes of the previous bordercasting node as having been "covered" by 279 the query. If this node is the peripheral node of the previous 280 bordercaster, it assumes the role of bordercaster and marks the 281 interior nodes of its own routing zone as "covered". If future query 282 messages are received, they will be steered away from the covered 283 regions. 285 After performing query detection, the node determines which downstream 286 branches of the bordercaster's bordercast tree are to be pruned. A 287 branch is pruned from the tree if all downstream peripheral nodes have 288 been covered by the query. This "early termination" helps steer the 289 query outward, away from regions of the network that have already been 290 covered by the query. The remaining downstream peripheral nodes are 291 marked as covered, and the links to downstream neighbors are recorded 292 as outgoing links. 294 The BRP delivers the query up to the higher layer application (IERP). 295 After some processing, the application may return an updated query 296 back to the BRP. The BRP will then relay the query on the selected 297 outgoing links. 299 Haas, Pearlman, Samar Expires July 2001 [Page 4] 300 A. Packet Format 302 1 2 3 303 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 304 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 305 | Query Source Address | 306 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 307 | Query Destination Address | 308 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 309 | Query ID | R E S E R V E D | 310 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 311 | Prev Bordercast Address | 312 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 313 | | 314 | E N C A P S U L A T E D P A C K E T | 315 | | 316 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 318 * Query Source Address (node_id) (32 bits) 319 IP address of the node that initiates the query. 321 * Query Destination Address (node_id) (32 bits) 322 IP address of the node that is the ultimate query 323 destination. 325 * Query ID (unsigned int) (16 bits) 326 Sequence number which, along with the Query Source 327 Address uniquely identifies any BRP query in the network. 329 * Query Extension (char) (8 bits) 330 Indicates whether query should be forwarded to 331 query destination. 333 * Prev Bordercast Address (node_id) (32 bits) 334 IP address of the most recent bordercasting node 336 * Encapsulated Packet (packet) 338 *** note: Within the context of the BRP, the Query Source 339 Address, Query Destination Address and Query ID 340 can assume the same values as corresponding 341 fields in the encapsulated query packet. 342 These BRP fields can be eliminated AS LONG AS: 343 (a) The BRP has read access to the contents of 344 the encapsulated packet. 345 (b) The BRP knows the format of the query 346 packet. 348 Haas, Pearlman, Samar Expires July 2001 [Page 5] 349 B. Data Structures 350 B.1 IARP Routing Table (see IARP specification) 352 B.2 IARP Link State Table (see IARP specification) 354 B.3 Detected Query Cache 356 +------------------------|--------------------------+ 357 | Query | Query ID | BRP_cache_ID | Prev | 358 | Source | | |Bordercast | 359 |(node_id)|(unsigned int)|(unsigned int)| (node_id) | 360 |---------+--------------|--------------+-----------+ 361 | | | | | 362 | | |--------------+-----------+ 363 | | | | | 364 |---------+--------------|--------------+-----------+ 365 | | | | | 366 | | |--------------+-----------+ 367 | | | | | 368 +------------------------|--------------+-----------+ 370 B.4 Query Coverage 372 +------------------------|---------------+ 373 | Query | Query ID | graph | 374 | Source | | | 375 |(node_id)|(unsigned int)| (net graph)* | 376 |---------+--------------|---------------| 377 | | | | 378 |---------+--------------|---------------| 379 | | | | 380 |---------+--------------|---------------| 382 * net_graph is a data structure that represents the connectivity of the 383 extended routing zone, and whether each extended routing zone member 384 has been covered by the query. 386 C. Interfaces 388 C.1 Higher Layer (IERP) 389 C.2.1 Send(packet, BRP_cache_ID) 390 Used by the IERP to request packet transmission. 392 C.2 Lower Layer (IP) 393 C.2.1 Deliver(packet) 394 Used by IP to deliver packet to BRP 396 Haas, Pearlman, Samar Expires July 2001 [Page 6] 397 D. State Machine 399 The BRP protocol consists of only one state (IDLE). Therefore, 400 no state transitions need to be specified. The BRP immediately 401 acts upon an event and then returns back to the IDLE state. 403 Notes: 1) X is used as a label for the node running this state 404 machine. 406 D.1 407 Event: A query is received from the higher layer (IERP). 408 An intrazone route to the query destination exists. 410 Action: If X has not already relayed the query to the 411 destination, X sends the query packet to the 412 next hop to the query destination. 414 D.2 415 Event: A query is received from the higher layer (IERP). 416 An intrazone route to the query destination 417 DOES NOT exist. 419 Action: X constructs the bordercast tree of the previous 420 bordercaster. X prunes branches leading to covered 421 peripheral nodes. The remaining downstream 422 peripheral nodes are marked as covered and the 423 query packet is forwarded to the remaining 424 downstream neighbors. 426 D.3 427 Event: A query is received from IP. 429 Action: Mark the interior nodes of the previous bordercaster 430 as covered. If X is a peripheral node of the 431 previous bordercaster, it becomes the new previous 432 bordercaster. 434 X records its BRP state in the Detected Query Cache 435 and schedules (with a random jitter) delivery of the 436 enapsulated query to the higher layer (i.e. IERP). 438 Haas, Pearlman, Samar Expires July 2001 [Page 7] 439 E. Pseudocode Implementation 441 We define two complimentary operations on packets: 442 extract(packet) and load(packet) 444 extract (packet) 445 extracts the fields of the BRP packet to the following 446 variables: {source, query_id, prev_bordercst, 447 encap_packet) 449 load (packet) 450 loads the values of the aforementioned variables into 451 the fields of the BRP packet. 453 E.1 Send(encap_packet, BRP_cache_ID) 455 // If BRP_cache_ID is not NULL, then this is an existing 456 // query that is being relayed and BRP state is extracted 457 // from the Detected Queries Cache and Query Coverage 458 // Table. Otherwise, this is a new query and BRP state 459 // is initialized. 460 if(BRP_cache_ID) 461 { 462 source = Detected_Queries[BRP_cache_ID].source; 463 query_id = Detected_Queries[BRP_cache_ID].query_id; 464 prev_bcast = Detected_Queries[BRP_cache_ID].prev_bcast; 465 coverage = Query_Coverage[source,query_id].init(); 466 } 467 else 468 { 469 source = MY_ID; 470 query_id = MY_BORDERCAST_ID++; 471 prev_bcast = MY_ID; 472 Query_Coverage[source,query_id] = 473 new_net_graph(IARP_link_state_table); 474 coverage = Query_Coverage[source,query_id]; 476 // Mark the previous bordercast's (here, the query 477 // source's) interior routing zone nodes as covered. 478 prev_bcast_int_nodes = 479 construct_routing_zone(coverage, prev_bcast); 480 record_query_coverage(coverage, prev_bcast_int_nodes); 481 } 483 Haas, Pearlman, Samar Expires July 2001 [Page 8] 484 if((EXIST)IARP_route_table[query_dest]) 485 { 486 // Route to destination is KNOWN 488 // If the query destination is not already covered, 489 // select next hop to query destination as the 490 // outgoing neighbor. 491 if(!covered(coverage, query_dest)) 492 out_neighbors = 493 IARP_Route_Table[query_dest].next_hop; 494 else 495 out_neighbors = {}; 497 // Mark the query destination as covered 498 record_query_coverage(coverage, query_dest); 499 } 500 else 501 { 502 // Route to destination is UNKNOWN 504 // Construct the previous bordercaster's bordercast 505 // tree. Identify the subtree that is downstream from 506 // this node. Prune branches from the subtree that 507 // lead to *covered* peripheral nodes. Mark the 508 // subtree's remaining peripheral nodes as covered. 509 // and the remaining neighbors as outgoing neighbors. 511 bordercast_tree = 512 construct_bordercast_tree(coverage, prev_bcast); 513 out_peripheral_nodes = 514 bordercast_tree.my_downstream_peripheral_nodes(); 515 out_neighbors = 516 bordercast_tree.my_dowstream_neighbors(); 518 // Mark DOWNSTREAM peripheral nodes as covered 519 record_query_coverage(coverage, out_peripheral_nodes); 520 } 522 // Relay query packet to outgoing neighbors. 523 load(packet); 524 send(packet,out_neighbors, IP); 526 Haas, Pearlman, Samar Expires July 2001 [Page 9] 527 E.2 Deliver(packet) 529 extract(packet); 531 // Load the known coverage of this query 532 if(!(EXISTS) Query_Coverage[source, query_id]) 533 { 534 Query_Coverage[source,query_id] = 535 new_net_graph(IARP_link_state_table); 536 } 537 coverage = Query_Coverage[source, query_id]; 539 // mark the previous bordercaster's interior 540 // routing zone nodes as covered. 541 bordercast_tree = 542 construct_bordercast_tree(coverage, prev_bcast); 543 record_query_coverage(coverage, prev_bcast_int_nodes); 545 // If this node is the previous bordercaster's peripheral 546 // node, then this node becomes the new previous 547 // bordercaster and this node's interior routing zone 548 // nodes are marked as covered. 549 if(is_peripheral_node(prev_bcast, MY_ID)) 550 { 551 prev_bcast = MY_ID; 552 prev_bcast_int_nodes = 553 construct_routing_zone(prev_bcast); 554 record_query_coverage(coverage, 555 prev_bcast_int_nodes); 556 } 558 // Record BRP "state" in Detected Queries Cache, so that 559 // the query can be properly forwarded when returned by 560 // the higher layer app (IERP) 561 BRP_cache_ID++; 562 add(Detected_Queries[source,query_id], 563 (BRP_cache_ID, prev_bcast); 564 schedule(remove(Detected_Queries[BRP_cache_ID]), 565 MAX_QUERY_LIFETIME); 566 schedule(deliver(encap_packet, BRP_cache_ID), RELAY_JITTER); 568 Haas, Pearlman, Samar Expires July 2001 [Page 10] 570 5. References 572 [1] Garcia-Luna-Aceves, J.J. and Spohn, M., "Efficient Routing in 573 Packet-Radio Networks Using Link-State Information," 574 WCNC '99, September 1999. 576 [2] Haas, Z.J., Pearlman, M.R. and Samar, P., "Intrazone Routing 577 Protocol (IARP)," IETF Internet Draft, 578 draft-ietf-manet-iarp-00.txt, January 2001. 580 [3] Haas, Z.J., Pearlman, M.R. and Samar, P., "Interzone Routing 581 Protocol (IERP)," IETF Internet Draft, 582 draft-ietf-manet-ierp-00.txt, January 2001. 584 [4] Haas, Z.J., Pearlman, M.R. and Samar, P., "Zone Routing Protocol 585 (ZRP)," IETF Internet Draft, draft-ietf-manet-zrp-04.txt, 586 January 2001. 588 [5] Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L., 589 and Clausen T., "Optimized Link State Routing Protocol," 590 IETF Internet Draft, draft-ietf-manet-olsr-03.txt, 591 November 2000. 593 [6] Johnson, D.B. and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc 594 Wireless Networks," in Mobile Computing, edited by T. 595 Imielinski and H. Korth, chapter 5, pp. 153-181, 596 Kluwer, 1996. 598 [7] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, RFC 2178, 599 July 1997. 601 [8] Murthy, S. and Garcia-Luna-Aceves, J.J., "An Efficient Routing 602 Protocol for Wireless Networks," MONET, vol. 1, no. 2, 603 pp. 183-197, October 1996. 605 [9] Ogier, R. "Efficient Routing Protocols for Packet-Radio Networks 606 Based on Tree Sharing," MoMUC '99, November 1999. 608 [10] Park, V.D. and Corson, M.S., "A Highly Adaptive Distributed 609 Routing Algorithm for Mobile Wireless Networks," 610 IEEE INFOCOM'97, Kobe, Japan, 1997. 612 [11] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal 613 Configuration for the Zone Routing Protocol," IEEE JSAC, 614 August, 1999. 616 [12] Pearlman, M.R., Haas, Z.J. and S.I. Mir, "Using Routing Zones to 617 Support Route Maintenance in Ad Hoc Networks," 618 IEEE WCNC 2000, Chicago, IL, Sept. 2000. 620 Haas, Pearlman, Samar Expires July 2001 [Page 11] 622 [13] Perkins, C.E. and Royer, E.M., "Ad Hoc On-Demand Distance 623 Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 625 [14] Perkins, C.E. and Bhagwat, P., "Highly Dynamic 626 Destination-Sequenced Distance-Vector Routing (DSDV) for 627 Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994. 629 [15] Postel, J., "Internet Protocol," RFC 791, Sept. 1981. 631 Haas, Pearlman, Samar Expires July 2001 [Page 12] 633 Authors' Information 635 Zygmunt J. Haas 636 Wireless Networks Laboratory 637 323 Frank Rhodes Hall 638 School of Electrical Engineering 639 Cornell University 640 Ithaca, NY 14853 641 United States of America 642 tel: (607) 255-3454, fax: (607) 255-9072 643 Email: haas@ee.cornell.edu 645 Marc R. Pearlman 646 389 Frank Rhodes Hall 647 School of Electrical Engineering 648 Cornell University 649 Ithaca, NY 14853 650 United States of America 651 tel: (607) 255-0236, fax: (607) 255-9072 652 Email: pearlman@ee.cornell.edu 654 Prince Samar 655 372 Frank Rhodes Hall 656 School of Electrical Engineering 657 Cornell University 658 Ithaca, NY 14853 659 United States of America 660 tel: (607) 255-9068, fax: (607) 255-9072 661 Email: samar@ee.cornell.edu 663 The MANET Working Group contacted through its chairs: 665 M. Scott Corson 666 Institute for Systems Research 667 University of Maryland 668 College Park, MD 20742 669 (301) 405-6630 670 corson@isr.umd.edu 672 Joseph Macker 673 Information Technology Division 674 Naval Research Laboratory 675 Washington, DC 20375 676 (202) 767-2001 677 macker@itd.nrl.navy.mil 679 Haas, Pearlman, Samar Expires July 2001 [Page 13]