idnits 2.17.1 draft-ietf-manet-zone-brp-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 2 longer pages, the longest (page 0) being 629 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 4 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 49 instances of too long lines in the document, the longest one being 2 characters in excess of 72. ** The abstract seems to contain references ([2], [3]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 49 has weird spacing: '... [Page i]...' == Line 79 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 (July 2002) is 7949 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: 9 errors (**), 0 flaws (~~), 6 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 January 2003 July 2002 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 in full conformance with 13 all provisions of Section 10 of RFC 2026, except the right to 14 produce derivative works is not granted. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 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 January 2003 [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. Bordercasting (BRP) Terminology . . . . . . . . . . . . . . 2 63 3. Bordercasting -- Routing Zone Based Querying . . . . . . . 3 65 4. Bordercast Resolution Protocol (BRP) Implementation . . . . 6 66 A. Packet Format . . . . . . . . . . . . . . . . . . . . . 7 67 B. Data Structures . . . . . . . . . . . . . . . . . . . . 8 68 C. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 8 69 D. State Machine . . . . . . . . . . . . . . . . . . . . . 9 70 E. Pseudocode Implementations . . . . . . . . . . . . . . . 10 72 5. References . . . . . . . . . . . . . . . . . . . . . . . . 13 74 6. Draft Modifications . . . . . . . . . . . . . . . . . . . . 14 76 Authors' Information . . . . . . . . . . . . . . . . . . . . . 15 77 MANET Contact Information . . . . . . . . . . . . . . . . . . . 15 79 Haas, Pearlman, Samar Expires January 2003 [Page ii] 80 Applicability Statement 82 A. Networking Context 84 Bordercasting is an efficient multicast packet delivery service used 85 for guiding queries through the network. When each node proactively 86 tracks the topology of its surrounding extended routing zone, queries 87 can be directed to the edge of the node's routing zone rather than 88 blindly being relayed to *all* neighbors. Special routing zone based 89 query control mechanisms steer query packets away from regions of the 90 network that have already been covered by the query. 92 Within the context of ad hoc network routing, bordercasting is 93 proposed as a more efficient and tunable alternative to broadcasting 94 of route request messages for reactive (on-demand) routing protocols. 95 We refer to any reactive routing protocol that bordercasts route 96 requests as an Interzone Routing Protocol (IERP). The link state 97 information needed to support bordercasting is provided by a local 98 proactive Intrazone Routing Protocol (IARP). Thus, a routing protocol 99 based on bordercasting is actually hybrid reactive/proactive. For a 100 properly chosen routing zone radius, IARP's cost of tracking routing 101 zone topology is more than justified by the resulting savings in route 102 discovery overhead through bordercasting. 104 B. Protocol Characteristics and Mechanisms 106 The Bordercast Resolution Protocol (BRP) is a packet delivery service, 107 not a full featured routing protocol. Bordercasting is enabled by a 108 local proactive Intrazone Routing Protocol (IARP) and supports a 109 global reactive Interzone Routing Protocol (IERP). The character- 110 istics of the IARP [2] and IERP [3] are summarized in their 111 corresponding Internet drafts. 113 1. Introduction 115 The design of ad hoc network routing protocols is influenced by link 116 instability (due to node mobility) and limitations in available 117 bandwidth and transmission power. Traditional wired networks use 118 proactive routing protocols, like OSPF [7] and RIP [15], to maintain 119 up-to-date routes to all networks nodes. More efficient proactive 120 routing protocols have been developed for ad hoc networks [1][5][8] 121 [9][14]. However, continuously tracking the frequent topology changes 122 in a practical ad hoc network can still produce an overwhelming amount 123 of control traffic. Even worse, most of the acquired route 124 information expires before it is ever used, making the proactive 125 control traffic a poor investment of bandwidth. In contrast, reactive 126 routing protocols [6][10][13] only initiate a global, query-based, 127 route discovery as routes are needed. While some delay is incurred 128 for route acquisition, the amount of overhead traffic is generally 129 much less than proactive routing protocols, because routing information 130 is not wasted. For this reason, reactive protocols are generally 131 viewed as being more suitable than proactive routing protocols for the 132 power/bandwidth limited mobile ad hoc network. 134 Although a global proactive routing protocol may overwhelm an ad hoc 135 network's resources, a LIMITED SCOPE proactive routing protocol can 136 be used to benefit a global reactive routing protocol. 137 This hybrid routing approach forms the basis for the Zone Routing 138 Protocol (ZRP) framework [4]. 140 The cost for each node to proactively track the topology of its 141 surrounding R-hop neighborhood (routing zone) can be justified by 142 improved route discovery efficiency and more effective route 143 maintenance [11][12]. Routes to local destinations are immediately 144 available, avoiding route discoveries. When the global route 145 discovery is needed, the routing zones can be used to efficiently 146 guide route queries outward through bordercasting, rather than blindly 147 relaying queries from neighbor to neighbor. The proactive maintenance 148 of routing zones also helps improve the quality and survivability of 149 discovered routes, by making them more robust to changes in network 150 topology. Once routes have been discovered, routing zone offers 151 enhanced, real-time, route maintenance. Link failures can be bypassed 152 by multiple hop paths within the routing zone. Similarly, sub-optimal 153 route segments can be identified and traffic re-routed along shorter 154 paths. 156 Haas, Pearlman, Samar Expires January 2003 [Page 1] 157 The bordercasting packet delivery service is provided by the 158 Bordercast Resolution Protocol (BRP). The BRP uses a map of an 159 extended routing zone, provided by the local proactive Intrazone 160 Routing Protocol (IARP) [2], to construct bordercast (multicast) 161 trees along which query packets are directed. (Within the context of 162 the hybrid ZRP, the BRP is used to guide the route requests of the 163 global reactive Interzone Routing Protocol (IERP) [3]). The BRP uses 164 special query control mechanisms to steer route requests away from 165 areas of the network that have already been covered by the query. 166 The combination of multicasting and zone based query control makes 167 bordercasting an efficient and tunable service that is more suitable 168 than flood searching for network probing applications like route 169 discovery. 171 2. Bordercasting (BRP) Terminology 173 bordercast 174 A packet delivery service, based on routing zones, which 175 distributes a message through a network in such a way that 176 all reachable network nodes belong to the routing zone of at 177 least one node that has relayed the message. Bordercasting 178 uses the known structure of routing zones to efficiently 179 relay messages away from regions of the network where the 180 message as already appeared. 181 This type of delivery is intended for efficient network 182 querying, where nodes proactively distribute queriable 183 information throughout their routing zones. 185 bordercasting node 186 A node that is relaying / has relayed a message as part of 187 a bordercast 189 bordercast tree 190 A multicast tree, rooted at a bordercasting node X, which 191 spans the uncovered peripheral nodes of node X. 193 covered node 194 A node that belongs to the routing zone of a bordercasting 195 node. 197 interior node 198 A node which lies inside of a routing zone. A routing zone 199 member is either an interior node or a peripheral node. 201 peripheral node 202 A node which lies at the edge of a routing zone 204 routing zone 205 With respect to a given node X, the collection of nodes 206 whose connectivity can be monitored by X through a 207 localized proactive routing protocol (ie. an Intrazone 208 Routing Protocol (IARP)). 210 routing zone radius 211 The distance (in hops) from a node to the peripheral nodes 212 of its routing zone 214 uncovered node 215 A node that does not belong to the routing zone of a 216 bordercasting node. 218 zone radius 219 see routing zone radius 221 3. Bordercasting -- Routing Zone Based Querying 223 In this section, we describe the basic operation of route discovery 224 based on bordercasting. A node, in need of a route to a destination, 225 first checks whether the destination lies within its routing zone. 226 If a path to the destination is known, no further route discovery 227 processing is required. On the other hand, if the destination is not 228 within the source's routing zone, the source node constructs a 229 "bordercast tree" spanning all of its peripheral nodes (ie. the nodes 230 on the edge of its routing zone). It then forwards a route query to 231 the neighbors in this tree. 233 The first time that a node receives a copy of the route query, the 234 node determines whether it belongs to the bordercast tree of the 235 neighbor that forwarded the query, because only tree members need to 236 actively process the route query. If the query was forwared via 237 layer 2 unicast, tree membership is implied by receipt of the query. 238 If the query was forwarded via layer 2 broadcast, the node must 239 reconstruct the bordercast tree of its forwarding neighbor. If the 240 node determines that it does not belong to the bordercast tree, it 241 simply notes reception of the query and then discards the message. 243 If the node does belong to the forwarding neighbors bordercast tree, 244 it proceeds to process the route query. If the query destination 245 lies in the node's routing zone, it sends a route reply back to the 246 query source, indicating a route to the destination. Otherwise, the 247 node constructs its own bordercast tree, which spans the subset of its 248 peripheral nodes that have not been covered by the query. (After a 249 node processes a route query, the nodes in its routing zone are 250 considered covered. The objective of bordercasting is to forward the 251 route query toward peripheral nodes that have not been covered by the 252 query.) The node then forwards the query to the neighbors in its 253 bordercast tree. After forwarding the query, the node's routing 254 becomes covered, thereby making it unnecessary for the node to forward 255 subsequent copies of the route query. 257 +---+ 258 +---+ | F | 259 +---+---| C |----+---+-----+---+ +---+ 260 | D | +---+ | E |----| H | 261 +---+ | +---+-----+---+ +---+ 262 +---+----| B | | 263 | A | +---+-----+---+ +---+ 264 +---+ | G | | I | 265 | +---+ +---+ 266 +---+ | 267 | M | +---+ 268 +---+ +---+ | J | 269 | L |----+---+----+---+ 270 +---+ | K | 271 +---+ 273 In the example illustrated above, node A has data to send to node L. 274 Assuming each node's zone radius is 2 hops, node L does not lie within 275 node A's routing zone (which includes nodes B,C,D,E,F,G). Therefore, 276 node A constructs a bordercast tree spanning its peripheral nodes: 277 D,E,F and G. Node A then sends the route query to neighbors in this 278 multicast tree: B and C. Each of these neighbors check if L belongs 279 to its routing zone. Since node L is not found in any of these nodes' 280 routing zones, the nodes construct bordercast trees spanning their 281 uncovered peripheral nodes and send the query to neighbors in their 282 bordercast trees. In particular, node B constructs a bordercast tree 283 spanning its uncovered peripheral nodes F,H and J. Nodes C and M are 284 excluded because they belong to the routing zone of A (the node that 285 relayed the query to B). Node B sends the query to its bordercast 286 tree neighbors: E and G. Likewise, node C identifies its uncovered 287 peripheral nodes (node E) and forwards the route query to its neighbor, 288 node F. 290 The full trace of this bordercast route discovery example is summarized 291 in the following table. 293 +-----------------------------------------------------------+ 294 | Rcv'd | | Peripheral Nodes | Relays to | 295 | From | Node | Covered | Uncovered | (Tree Neighbors) | 296 |-------|--------|---------|-----------|--------------------| 297 | --- | A | | E,D,F,G | B,C | 298 |-------|--------|---------|-----------|--------------------| 299 | A | B | C,M | F,H,J | E,G | 300 |-------|--------|---------|-----------|--------------------| 301 | A | C | B,M | E | F | 302 |-------|--------|---------|-----------|--------------------| 303 | B | E | A,G | I,C | H,F | 304 |-------|--------|---------|-----------|--------------------| 305 | B | G | destination discovered -- reply sent | 306 |-------|--------|---------|-----------|--------------------| 307 | C | F | A,D | B,H | E | 308 |-------|--------|---------|-----------|--------------------| 309 | E | H | F,B | --- | --- | 310 |-------|--------|---------|-----------|--------------------| 311 | E | F | A,D,B,H | --- | --- | 312 |-------|--------|---------|-----------|--------------------| 313 | F | E | A,G,C,I | --- | --- | 314 +-----------------------------------------------------------+ 316 Eventually, a route query is received by node G, which has the 317 destination L in its routing zone. Node G does not forward the 318 query, but sends a route reply back to A, indicating the 319 discovered path: A--B--G--J--L. 321 This example demonstrates the efficiency of bordercasting as compared 322 with flood searching. If the network consists of point-to-point 323 links, bordercasting generates 8 query transmissions. If the network 324 consists of a single, shared channel, then bordercasting generates 5 325 query broadcasts. In contrast, flood searching would generate 13 326 point-to-point query transmissions, or 12 query broadcasts. 328 Haas, Pearlman, Samar Expires January 2003 [Page 5] 330 4. Bordercast Resolution Protocol (BRP) Implementation 332 When a node's BRP receives a bordercast query packet, it marks the 333 routing zone of the previous bordercasting node as having been 334 "covered". If the node is an intended recipient of the query, it 335 proceeds to deliver the query message up to the querying application 336 (eg. IERP). To enhance bordercasting efficiency, this delivery is 337 scheduled with some random delay. This provides more opportunity for 338 the node to acquire query coverage information prior to forwarding 339 the query (see below). If the node is not an intended recipient of 340 the query, it is implied that the node's own routing zone has been 341 covered by other bordercasting nodes. As such, the node marks its 342 entire routing zone as covered and discards the query. 344 After processing the query, the querying application may return the 345 query to BRP. If the node knows the route to the destination, it 346 forwards the query to the destination. Otherwise, the node forwards 347 the query to neighbors that span its uncovered peripheral nodes in its 348 bordercast tree. In either case, after forwarding the query packet, 349 the node marks all nodes in its routing zone as covered. 351 Haas, Pearlman, Samar Expires January 2003 [Page 6] 352 A. Packet Format 354 1 2 3 355 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 356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 357 | Query Source Address | 358 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 359 | Query Destination Address | 360 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 361 | Query ID |Query Extension| RESERVED | 362 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 363 | Prev Bordercast Address | 364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 365 | | 366 | E N C A P S U L A T E D P A C K E T | 367 | | 368 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 370 * Query Source Address (node_id) (32 bits) 371 IP address of the node that initiates the query. 373 * Query Destination Address (node_id) (32 bits) 374 IP address of the node that is the ultimate query 375 destination. 377 * Query ID (unsigned int) (16 bits) 378 Sequence number which, along with the Query Source 379 Address uniquely identifies any BRP query in the network. 381 * Query Extension (char) (8 bits) 382 Indicates whether query should be forwarded to 383 query destination. 385 * Prev Bordercast Address (node_id) (32 bits) 386 IP address of the most recent bordercasting node. 388 * Encapsulated Packet (packet) 390 *** note: Within the context of the BRP, the Query Source 391 Address, Query Destination Address and Query ID 392 can assume the same values as corresponding 393 fields in the encapsulated query packet. 394 These BRP fields can be eliminated AS LONG AS: 395 (a) The BRP has read access to the contents of 396 the encapsulated packet. 397 (b) The BRP knows the format of the query 398 packet. 400 Haas, Pearlman, Samar Expires January 2003 [Page 7] 401 B. Data Structures 402 B.1 IARP Routing Table (see IARP specification [2]) 404 B.2 IARP Link State Table (see IARP specification [2]) 406 B.3 Query Coverage 408 +------------------------|--------------|--------------+ 409 | Query | Query ID | BRP_cache_ID | graph | 410 | Source | | | | 411 |(node_id)|(unsigned int)|(unsigned int)| (net graph)* | 412 |---------+--------------|--------------|--------------| 413 | | | | | 414 |---------+--------------|--------------|--------------| 415 | | | | | 416 |---------+--------------|--------------|--------------| 418 * net_graph is a data structure that represents routing zone 419 connectivity and whether each routing zone member has been covered 420 by the query. 422 C. Interfaces 424 C.1 Higher Layer (IERP) 425 C.2.1 Send(packet, BRP_cache_ID) 426 Used by the IERP to request packet transmission. 428 C.2 Lower Layer (IP) 429 C.2.1 Deliver(packet) 430 Used by IP to deliver packet to BRP 432 Haas, Pearlman, Samar Expires January 2003 [Page 8] 433 D. State Machine 435 The BRP protocol consists of only one state (IDLE). Therefore, 436 no state transitions need to be specified. The BRP immediately 437 acts upon an event and then returns back to the IDLE state. 439 Notes: 1) X is used as a label for the node running this state 440 machine. 442 D.1 443 Event: A query is received from the higher layer (IERP). 444 An intrazone route to the query destination exists. 446 Action: If X has not already relayed the query to the 447 destination, X sends the query packet to the 448 next hop to the query destination. 450 D.2 451 Event: A query is received from the higher layer (IERP). 452 An intrazone route to the query destination 453 DOES NOT exist. 455 Action: X constructs the bordercast tree spanning its 456 "uncovered" peripheral nodes. The query packet 457 is forwarded to the node's tree neighbors. 458 Once the query is forwarded, the node marks all 459 of its routing zone nodes as covered 461 D.3 462 Event: A query is received from IP. 464 Action: Mark the routing zone nodes of the previous 465 bordercaster as covered. 467 If X is an intended recepient for the query, it 468 records its BRP state for this query and 469 schedules (with a random delay) delivery of the 470 encapsulated query to the higher layer 471 (i.e. IERP). 473 If X is not an intended recipient for the query, 474 it is implied that X's routing zone is covered by 475 the routing zones of other relaying nodes. Thus, 476 X marks its own routing zone as covered and 477 discards the packet 479 Haas, Pearlman, Samar Expires January 2003 [Page 9] 480 E. Pseudocode Implementation 482 We define two complimentary operations on packets: 483 extract(packet) and load(packet) 485 extract (packet) 486 extracts the fields of the BRP packet to the following 487 variables: {source, query_id, prev_bordercst, 488 encap_packet} 490 load (packet) 491 loads the values of the aforementioned variables into 492 the fields of the BRP packet. 494 E.1 Send(encap_packet, BRP_cache_ID) 496 // If BRP_cache_ID is not NULL, then this is an existing 497 // query that is being relayed and BRP state is extracted 498 // from the Query Coverage Table. Otherwise, this is a 499 // new query and BRP state is initialized. 500 if(BRP_cache_ID) 501 { 502 source = Query_Coverage[BRP_cache_ID].source; 503 query_id = Query_Coverage[BRP_cache_ID].query_id; 504 } 505 else 506 { 507 source = MY_ID; 508 query_id = MY_BORDERCAST_ID++; 509 Query_Coverage[source,query_id] = 510 new_net_graph(IARP_link_state_table); 511 } 512 coverage = Query_Coverage[source,query_id].graph; 514 Haas, Pearlman, Samar Expires January 2003 [Page 10] 515 if((EXIST)IARP_route_table[query_dest]) 516 { 517 // Route to destination is KNOWN 519 // If the query destination is not already covered, 520 // select next hop to query destination as the 521 // outgoing neighbor. 522 if(!covered(coverage, query_dest)) 523 out_neighbors = 524 IARP_Route_Table[query_dest].next_hop; 525 else 526 out_neighbors = {}; 527 } 528 else 529 { 530 // Route to destination is UNKNOWN 532 // Construct the node's bordercast tree, spanning 533 // all remaining "uncovered" peripheral nodes. 534 bordercast_tree = 535 construct_bordercast_tree(coverage, MY_ID); 536 out_neighbors = 537 bordercast_tree.my_dowstream_neighbors(); 538 } 540 // Relay query packet to outgoing neighbors. 541 prev_bcast = MY_ID; 542 load(packet); 543 send(packet,out_neighbors, IP); 545 // After relaying the route query, the node can mark its 546 // entire routing zone as covered. 547 my_zone_nodes = construct_routing_zone(coverage, MY_ID); 548 record_query_coverage(coverage, my_zone_nodes); 550 Haas, Pearlman, Samar Expires January 2003 [Page 11] 551 E.2 Deliver(packet) 553 extract(packet); 555 // Load the known coverage of this query 556 if(!(EXISTS) Query_Coverage[source, query_id]) 557 { 558 Query_Coverage[source,query_id].graph = 559 new_net_graph(IARP_link_state_table); 560 Query_Coverage[source,query_id].BRP_cache_ID = 561 BRP_cache_ID++; 562 } 563 coverage = Query_Coverage[source, query_id].graph; 565 // Mark the previous bordercaster's routing zone nodes as 566 // covered. 567 prev_bcast_zone_nodes = 568 construct_routing_zone(coverage, prev_bcast); 569 record_query_coverage(coverage, prev_bcast_zone_nodes); 571 // If this node is the previous bordercaster's outgoing 572 // neighbor, then this node becomes a bordercasting node 573 if(is_out_neighbor(prev_bcast, MY_ID, coverage)) 574 { 575 // Deliver query to querying application (eg. IERP) 576 // with a randomly generated delay. 577 schedule(deliver(encap_packet, BRP_cache_ID), 578 RELAY_JITTER); 580 // Schedule deletion of Query_Coverage entry for some 581 // future time after route query has died off in the 582 // network 583 schedule(remove(Query_Coverage[BRP_cache_ID]), 584 MAX_QUERY_LIFETIME); 585 } 586 else 587 { 588 // This node does not need to relay the query, because 589 // its entire routing zone is covered by prev_bcast and 590 // prev_bcast's bordercast tree neighbors. 591 my_zone_nodes = 592 construct_routing_zone(coverage, MY_ID); 593 record_query_coverage(coverage, my_zone_nodes); 595 discard(encap_packet); 596 } 598 Haas, Pearlman, Samar Expires January 2003 [Page 12] 600 5. References 602 [1] Garcia-Luna-Aceves, J.J. and Spohn, M., "Efficient Routing in 603 Packet-Radio Networks Using Link-State Information," 604 WCNC '99, September 1999. 606 [2] Haas, Z.J., Pearlman, M.R. and Samar, P., "Intrazone Routing 607 Protocol (IARP)," IETF Internet Draft, 608 draft-ietf-manet-iarp-02.txt, July 2002. 610 [3] Haas, Z.J., Pearlman, M.R. and Samar, P., "Interzone Routing 611 Protocol (IERP)," IETF Internet Draft, 612 draft-ietf-manet-ierp-02.txt, July 2002. 614 [4] Haas, Z.J., Pearlman, M.R. and Samar, P., "Zone Routing Protocol 615 (ZRP)," IETF Internet Draft, draft-ietf-manet-zrp-04.txt, 616 July 2002. 618 [5] Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L., 619 and Clausen T., "Optimized Link State Routing Protocol," 620 IETF Internet Draft, draft-ietf-manet-olsr-03.txt, 621 November 2000. 623 [6] Johnson, D.B. and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc 624 Wireless Networks," in Mobile Computing, edited by T. 625 Imielinski and H. Korth, chapter 5, pp. 153-181, 626 Kluwer, 1996. 628 [7] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, RFC 2178, 629 July 1997. 631 [8] Murthy, S. and Garcia-Luna-Aceves, J.J., "An Efficient Routing 632 Protocol for Wireless Networks," MONET, vol. 1, no. 2, 633 pp. 183-197, October 1996. 635 [9] Ogier, R. "Efficient Routing Protocols for Packet-Radio Networks 636 Based on Tree Sharing," MoMUC '99, November 1999. 638 [10] Park, V.D. and Corson, M.S., "A Highly Adaptive Distributed 639 Routing Algorithm for Mobile Wireless Networks," 640 IEEE INFOCOM'97, Kobe, Japan, 1997. 642 [11] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal 643 Configuration for the Zone Routing Protocol," IEEE JSAC, 644 August, 1999. 646 [12] Pearlman, M.R., Haas, Z.J. and S.I. Mir, "Using Routing Zones to 647 Support Route Maintenance in Ad Hoc Networks," 648 IEEE WCNC 2000, Chicago, IL, Sept. 2000. 650 Haas, Pearlman, Samar Expires January 2003 [Page 13] 652 [13] Perkins, C.E. and Royer, E.M., "Ad Hoc On-Demand Distance 653 Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 655 [14] Perkins, C.E. and Bhagwat, P., "Highly Dynamic 656 Destination-Sequenced Distance-Vector Routing (DSDV) for 657 Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994. 659 [15] Postel, J., "Internet Protocol," RFC 791, Sept. 1981. 661 6. Draft Modifications 663 The following are major changes between this version (02) of the BRP 664 draft and the previous version (01): 666 - The role of "intermediate node" has been eliminated from this 667 version of bordercasting. All nodes that relay bordercast messages 668 are now considered bordercasting nodes and therefore execute a common, 669 simplified algorithm. The BRP description, example and implementation 670 have been updated accordingly. 672 - A terminology section has been added. 674 Haas, Pearlman, Samar Expires January 2003 [Page 14] 676 Authors' Information 678 Zygmunt J. Haas 679 Wireless Networks Laboratory 680 323 Frank Rhodes Hall 681 School of Electrical & Computer Engineering 682 Cornell University 683 Ithaca, NY 14853 684 United States of America 685 tel: (607) 255-3454, fax: (607) 255-9072 686 Email: haas@ece.cornell.edu 688 Marc R. Pearlman 689 389 Frank Rhodes Hall 690 School of Electrical & Computer Engineering 691 Cornell University 692 Ithaca, NY 14853 693 United States of America 694 tel: (607) 255-0236, fax: (607) 255-9072 695 Email: pearlman@ece.cornell.edu 697 Prince Samar 698 374 Frank Rhodes Hall 699 School of Electrical & Computer Engineering 700 Cornell University 701 Ithaca, NY 14853 702 United States of America 703 tel: (607) 255-9068, fax: (607) 255-9072 704 Email: samar@ece.cornell.edu 706 The MANET Working Group contacted through its chairs: 708 M. Scott Corson 709 Flarion Technologies, Inc. 710 Bedminster One 711 135 Route 202/206 South 712 Bedminster, NJ 07921 713 (908) 947-7033 714 corson@isr.umd.edu 716 Joseph Macker 717 Information Technology Division 718 Naval Research Laboratory 719 Washington, DC 20375 720 (202) 767-2001 721 macker@itd.nrl.navy.mil 723 Haas, Pearlman, Samar Expires January 2003 [Page 15]