idnits 2.17.1 draft-ietf-manet-zone-iarp-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 1 longer page, the longest (page 0) being 740 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 62 instances of too long lines in the document, the longest one being 4 characters in excess of 72. ** There are 2 instances of lines with control characters in the document. ** The abstract seems to contain references ([2]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** 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 320: '... SHOULD be excluded from the trans...' RFC 2119 keyword, line 328: '... - The IARP SHOULD support link stat...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 51 has weird spacing: '... [Page i]...' == Line 79 has weird spacing: '... [Page ii]...' == Line 176 has weird spacing: '... [Page iv]...' == Line 211 has weird spacing: '... [Page v]...' == Line 665 has weird spacing: '...America tel:...' -- 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 7954 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. 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-brp - 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: 11 errors (**), 0 flaws (~~), 8 warnings (==), 18 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 Intrazone Routing Protocol (IARP) 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 This document describes the Intrazone Routing Protocol (IARP), a 36 limited scope proactive routing protocol used to improve the 37 performance of existing globally reactive routing protocols. With 38 each node monitoring changes in its surrounding R-hop neighborhood 39 (routing zone), global route discoveries to local destinations can be 40 avoided. When a global route search is needed, the IARP's routing 41 zones can be used to efficiently guide route queries outwards (via 42 bordercasting) rather than blindly relaying queries from neighbor 43 to neighbor. The proactive maintenance of routing zones also helps 44 improve the quality of discovered routes, by making them more robust 45 to changes in network topology. Once routes have been discovered, 46 IARP's routing zone offers enhanced, real-time, route maintenance. 47 Link failures can be bypassed by multiple hop paths within the 48 routing zone. Similarly, suboptimal route segments can be identified 49 and traffic re-routed along shorter paths. 51 Haas, Pearlman, Samar Expires January 2003 [Page i] 52 Contents 54 Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i 55 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i 57 Applicability Statement . . . . . . . . . . . . . . . . . . . iii 58 A. Networking Context . . . . . . . . . . . . . . . . . iii 59 B. Protocol Characteristics and Mechanisms . . . . . . . iii 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 63 2. Routing Zones and Intrazone Routing . . . . . . . . . . . . 2 65 3. IARP Conversion Guidelines . . . . . . . . . . . . . . . . 3 67 4. Implementation Example - Timer Based Link State . . . . . . 3 68 A. Packet Format . . . . . . . . . . . . . . . . . . . . . 4 69 B. Data Structures . . . . . . . . . . . . . . . . . . . . 5 70 C. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 6 71 D. State Machine . . . . . . . . . . . . . . . . . . . . . 6 72 E. Pseudocode Implementation . . . . . . . . . . . . . . . 7 74 5. References . . . . . . . . . . . . . . . . . . . . . . . . 9 76 Authors' Information . . . . . . . . . . . . . . . . . . . . . 11 77 MANET Contact Information . . . . . . . . . . . . . . . . . . . 11 79 Haas, Pearlman, Samar Expires January 2003 [Page ii] 80 Applicability Statement 82 A. Networking Context 84 The Intrazone Routing Protocol (IARP) is a limited scope proactive 85 routing protocol, which is used to support a primary global routing 86 protocol. The scope of the IARP is defined by the routing zone 87 radius: the distance in hops that IARP route updates are relayed. 89 IARP's proactive tracking of local network connectivity provides 90 support for route acquisition and route maintenance. First, routes 91 to local destinations are immediately available, avoiding the traffic 92 overhead and latency of a route discovery. When a global route 93 discovery is required for more distant destinations, inefficient 94 query broadcasting can be replaced by a more bandwidth efficient 95 query bordercasting [2], which directs queries to the periphery of 96 the routing zone. 98 Once routes have been discovered, IARP's routing zone offers 99 enhanced, real-time, route maintenance. Link failures can be 100 bypassed by multiple hop paths within the routing zone. Similarly, 101 suboptimal route segments can be identified, enabling traffic to be 102 re-routed along shorter paths. 104 B. Protocol Characteristics and Mechanisms 106 * Does the protocol provide support for unidirectional links? 107 (if so, how?) 108 Yes. The IARP can provide "local" support for unidirectional 109 links. A unidirectional link can be used as long as the link 110 source and link destination lie within each other's routing zone. 112 * Does the protocol require the use of tunneling? (if so, how?) 113 No. 115 * Does the protocol require using some form of source routing? 116 (if so, how?) 118 No. 120 * Does the protocol require the use of periodic messaging? 121 (if so, how?) 123 Yes. The IARP proactively maintains local routing information 124 (routing zones) based on periodic exchanges of neighbor 125 discovery messages. 127 * Does the protocol require the use of reliable or sequenced packet 128 delivery? (if so, how?) 130 IARP only assumes that link-layer (neighbor) unicasts are 131 delivered reliably and in-sequence. Reliable and sequenced 132 delivery of neighbor broadcasts and IP unicasts is not 133 required. 135 * Does the protocol provide support for routing through a multi- 136 technology routing fabric? (if so, how?) 138 Yes. It is assumed that each node's network interface is 139 assigned a unique IP address. 141 * Does the protocol provide support for multiple hosts per router? 142 (if so, how?) 144 Yes. Multiple hosts may be associated with a router. These 145 hosts can be identified by the neighbor discovery/maintenance 146 process. 148 By default, it is assumed that a host's association with a router 149 is not permanent. As a result, IARP exchanges routing 150 information for individual hosts in the same manner as routing 151 information for routers. 153 In cases where a router is permanently associated with a network 154 (subnetwork), IARP supports the exchange of network 155 (subnetwork) prefixes in place of all aggregated host IP 156 addresses. 158 * Does the protocol support the IP addressing architecture? 159 (if so, how?) 161 Yes. Each node is assumed to have a unique IP address (or set of 162 unique IP addresses in the case of multiple interfaces). The IARP 163 references all nodes/interfaces by their IP address. 165 * Does the protocol require link or neighbor status sensing 166 (if so, how?) 168 Yes. IARP proactively maintains local routing information 169 (routing zones) based on detected changes in neighbor status. 171 * Does the protocol have dependence on a central entity? 172 (if so, how?) 174 No. IARP is a fully distributed protocol. 176 Haas, Pearlman, Samar Expires January 2003 [Page iv] 178 * Does the protocol function reactively? (if so, how?) 180 No. 182 * Does the protocol function proactively? (if so, how?) 184 Yes. IARP proactively maintains LOCAL routing information 185 (routing zones) for each node. The routing zone information is 186 leveraged, through the bordercasting mechanism, to support 187 efficient global propagation of route queries. 189 * Does the protocol provide loop-free routing? (if so, how?) 191 Yes. IARP's link state proactive protocol is inherently 192 loop-free, although temporary loops may form while new link 193 state updates propagate through the routing zone. 195 * Does the protocol provide for sleep period operation? (if so, how?) 197 No. Sleep period operation is not addressed in this draft. 198 However, sleep period support can be included as needed. 200 * Does the protocol provide some form of security? (if so, how?) 202 No. It is assumed that security issues are adequately addressed 203 by the underlying protocols (IPsec, for example). 205 * Does the protocol provide support for utilizing multi-channel, 206 link-layer technologies? (if so, how?) 208 Yes. It is assumed that each node's network interface is 209 assigned a unique IP address. 211 Haas, Pearlman, Samar Expires January 2003 [Page v] 213 1. Introduction 215 The design of ad hoc network routing protocols is influenced by link 216 instability (due to node mobility) and limitations in available 217 bandwidth and transmission power. Traditional wired networks use 218 proactive routing protocols, like OSPF [7] and RIP [15] to maintain 219 up-to-date routes to all networks nodes. More efficient proactive 220 routing protocols have been developed for ad hoc networks [1][5][8] 221 [9][14]. However, continuously tracking the frequent topology changes 222 in a practical ad hoc network can still produce an overwhelming amount 223 of control traffic. Even worse, most of the acquired route 224 information expires before it is ever used, making the proactive 225 control traffic a poor investment of bandwidth. In contrast, reactive 226 routing protocols [6][10][13] only initiate a global, query-based, 227 route discovery as routes are needed. While some delay is incurred in 228 route acquisition, the amount of overhead traffic is generally much 229 less than proactive routing protocols, because routing information is 230 not wasted. For this reason, reactive protocols are generally viewed 231 as being more suitable than proactive routing protocols for the power/ 232 bandwidth limited mobile ad hoc network. 234 Although a global proactive routing protocol may overwhelm an ad hoc 235 network's resources, a LIMITED SCOPE proactive routing protocol can be 236 used to the advantage of a global reactive routing protocol. This 237 hybrid routing approach forms the basis for the Zone Routing Protocol 238 (ZRP) framework [4]. 240 The cost for each node to proactively track the topology of its 241 surrounding R-hop neighborhood (routing zone) can be justified by 242 improved route discovery efficiency and more effective route 243 maintenance [11][12]. Routes to local destinations are immediately 244 available, avoiding route discoveries. When global route discovery is 245 needed, the routing zones can be used to efficiently guide route 246 queries outwards through bordercasting [2], rather than blindly 247 relaying queries from neighbor to neighbor. The proactive maintenance 248 of routing zones also helps improve the quality and survivability of 249 discovered routes, by making them more robust to changes in network 250 topology. Once routes have been discovered, routing zone offers 251 enhanced, real-time, route maintenance. Link failures can be bypassed 252 by multiple hop paths within the routing zone. Similarly, suboptimal 253 route segments can be identified and traffic re-routed along shorter 254 paths. 256 Within the context of the ZRP, we refer to the locally proactive 257 routing component as the Intrazone Routing Protocol (IARP). The IARP 258 is not a specific routing protocol. Rather, it is a family of 259 limited-depth, proactive, link state routing protocols. In this 260 document, we provide an implementation of a simple timer-based IARP. 261 In addition, we provide a set of basic guidelines which can be used to 262 convert an existing proactive routing protocol to an IARP. 264 Haas, Pearlman, Samar Expires January 2003 [Page 1] 266 2. Routing Zones and Intrazone Routing 268 A routing zone for a node X is defined as the set of nodes whose 269 minimum distance in *hops* from X is no greater than some parameter 270 referred to as the zone radius. An example of a radius R = 2 hop 271 routing zone (for node A) is shown below. 273 +-----------------------------------------+ 274 | +---+ | 275 | +---+ ---| F |-------| | 276 +---+ | +---+ --| C |--/ +---+ +---+ | 277 | G |-----| D |--/ +---+ | E | | Routing Zone of 278 +---+ | +---+ | +---+ +---+ | node A 279 | +---+ ---| B |-------| | (radius = 2 hops) 280 | | A |--/ +---+ | 281 | +---+ | 282 +-----------------------------------------+ 284 In this example nodes B through F are within the routing zone of A. 285 Node G is outside A's routing zone. Also note that E can be reached by 286 two paths from A, one with length 2 hops and one with length 3 hops. 287 Since the minimum is less than or equal to 2, E is within A's routing 288 zone. Peripheral nodes are routing zone nodes whose minimum distance 289 to the node in question is equal exactly to the zone radius. In the 290 above figure, nodes D, F and E are A's peripheral nodes. These 291 peripheral nodes play an important role in efficient querying based on 292 bordercasting. We note that each node maintains its own routing zone. 293 As a result, routing zones of nearby nodes may overlap heavily. 295 Each node proactively tracks the topology of its routing zone through 296 an IntrAzone Routing Protocol (IARP). IARP is derived from globally 297 proactive link state routing protocols (for example, OSPF). The base 298 protocol needs to be modified to ensure that the scope of the route 299 updates is restricted to the radius of the node's routing zone. The 300 required modifications and example IARP are described in the next 301 sections. 303 Haas, Pearlman, Samar Expires January 2003 [Page 2] 305 3. IARP Conversion Guidelines 307 Traditional proactive link state protocols can be modified to serve as 308 an IARP by limiting link state updates to the scope of the link 309 source's routing zone. The following guidelines can be used to 310 convert existing proactive link state routing protocols to an IARP: 312 - The scope of link state advertisements are limited by a TTL (time 313 to live) in the link state update packet. The TTL is initialized to 314 R-1 hops by the link source. When a node receives the update 315 packet, it decrements the TTL value. When the TTL reaches 0, the 316 packet is discarded. 318 - If the base routing protocol performs link state table transfers 319 with new neighbors, link sources that are at least R-1 hops away 320 SHOULD be excluded from the transfer. This reduces the transmission 321 of redundant link state to neighbors closer to the link source, and 322 prevents transmission of out-of-zone link state to neighbors farther 323 from the link source. 325 - Nodes periodically update their link state tables, discarding link 326 sources that are farther than R-1 hops away. 328 - The IARP SHOULD support link state metrics that are consistent with 329 the metrics used by the Interzone Routing Protocol (IERP) [3]. 330 These additional metrics allow the IERP to import IARP routes in 331 support of enhanced route maintenance (route repair, route 332 shortening, etc.). 334 4. Implementation Example - Timer Based Link State IARP 336 Nodes compute intrazone routes based on the proactively tracked link 337 state of each routing zone member. Each node periodically advertises 338 its link state (current set of neighbors and corresponding lists of 339 link metrics) throughout its routing zone. Nodes monitor their 340 own link state by means of a neighbor discovery protocol *. 342 The scope of a link state update is controlled by a TTL (time-to- 343 live) value that is carried in the link state packet. The TTL is 344 initialized by the link source to R-1 hops (where R is the zone 345 radius). Upon receipt of link state update packet, the link state is 346 recorded, the routing table is recomputed and the packet's TTL value 347 is decremented. As long as the TTL value is greater than 0, the link 348 state update packet is rebroadcasted. 350 * This IARP relies on the services of a separate protocol (referred to 351 here as the Neighbor Discovery Protocol (NDP)) to provide current 352 information about a node's neighbors. At the least, this informa- 353 tion must include the IP addresses of all the neighbors. IARP and 354 NDP can be configured to support supplemental link quality metrics. 356 Haas, Pearlman, Samar Expires January 2003 [Page 3] 358 A. Packet Format 360 1 2 3 361 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 362 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 363 | Link Source Address | 364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 365 | Link State Seq Num | Zone Radius | TTL | 366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 367 | RESERVED | RESERVED | Link Dest Cnt | 368 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 369 | Link Destination 1 Address | 370 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 371 | Link Destination 1 Subnet Mask (Optional) | 372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 373 | RESERVED | Metric Type | Metric Value | | 374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Link 375 | RESERVED | Metric Type | Metric Value | Metrics 376 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 377 | RESERVED | Metric Type | Metric Value | | 378 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 379 | | 380 | | 381 \| |/ 382 \ / 383 \/ 384 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 385 | Link Destination n Address | 386 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 387 | Link Destination n Subnet Mask (Optional) | 388 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 389 | RESERVED | Metric Type | Metric Value | | 390 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Link 391 | RESERVED | Metric Type | Metric Value | Metrics 392 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 393 | RESERVED | Metric Type | Metric Value | | 394 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 396 Field Description: 398 * Link Source Address (node_id) (32 bits) 399 IP address of the reported link's source node. 401 * Link State Seq Num (unsigned int) (16 bits) 402 Sequence number used to track the link state history of 403 the Link Source node. 405 * Zone Radius (char) (8 bits) 406 Routing zone radius of the link's source node. Determines 407 the extent that link state information propagates. 409 Haas, Pearlman, Samar Expires January 2003 [Page 4] 410 * TTL (char) (8 bits) 411 number of hops remaining until packet is to be discarded 413 * Link Dest Count (char) (8 bits) 414 number of link source's neighbors 416 * Link Destination Address (node_id) (n * 32 bits) 417 IP addresses of the link source's neighbor nodes. 419 * Node/Link Metrics (metric) (n*X * 32 bits) 420 This section of the packet is used to report the quality 421 of this link (or link source node). 423 * Metric Type (char) (8 bits) 424 Type of metric being reported 425 (based on pre-defined metric types) 427 * Metric Value (unsigned int) (16 bits) 428 Value of node / link metric specified by Metric Type 430 B. Data Structures 432 B.1 Routing Table 434 +-----------------------|--------------------------------+ 435 | Dest | Subnet | Routes | Route | 436 | Addr | Mask | | Metrics | 437 | (node_id) | (node_id) | (node_id list) | (metric list) | 438 |-----------+-----------|----------------+---------------| 439 | | | | | 440 |-----------+-----------|----------------+---------------| 441 | | | | | 442 |-----------+-----------|----------------+---------------| 443 | | | | | 444 +-----------------------|--------------------------------+ 446 B.2 Link State Table 448 +-----------|--------+-------+--------+------------------+ 449 | Link | Zone | Link | Insert | Link State | 450 | Source | Radius | State | Time | Information | 451 | Addr | | ID | | | 452 | (node_id) | (int) | (int) | (int) | (ls_info list) | 453 +-----------|--------+-------+--------+------------------| 454 | | | | | | 455 |-----------|--------+-------+--------+------------------| 456 | | | | | | 457 |-----------|--------+-------+--------+------------------| 458 | | | | | | 459 +-----------|--------------------------------------------+ 461 Haas, Pearlman, Samar Expires January 2003 [Page 5] 463 ## detail of (ls_info) data type 464 +---+---|---| 465 | | ||||| 466 +---+---|---| 467 (a) (b) (c) 469 (a) Link Destination Address 470 (b) Link Destination Subnet Mask 471 (c) Link Metrics 473 C. Interfaces 475 C.1 Higher Layer (N/A) 477 C.2 Lower Layer (IP) 478 C.1.1 Deliver(packet) 479 Used by IP to deliver packet to IARP 481 C.3 NDP 482 C.3.1 Deliver() 483 Used by NDP to indicate an update in link state. 484 IARP retrieves the actual link state from NDP via 485 Neighbor_State(&neighbor[n],&mask[n],&metrics[n][x]). 487 D. State Machine 489 The IARP protocol consists of only one state (IDLE). Therefore, 490 no state transitions need to be specified. The IARP immediately 491 acts upon an event and then returns back to the IDLE state. 493 Notes: 1) X is used as a label for the node running this state 494 machine. 496 D.1 497 Event: Link state broadcast timer interrupt. 499 Action: X consults the neighbor discovery process for its 500 own link state (list of neighbors and corresponding 501 link metrics). X updates its Link State Table and 502 Routing Table accordingly. The TTL value is 503 initialized to R-1 hops (where R is the zone radius). 504 If the TTL is greater than 0 then X loads a link 505 state packet and broadcasts it to its neighbors. 507 Haas, Pearlman, Samar Expires January 2003 [Page 6] 508 D.2 509 Event: An IARP link state packet is received. 511 Action: The link state update is recorded in the Link State 512 Table and the Routing Table is updated accordingly. 513 The TTL is decremented. If the TTL is greater 514 than 0 then X broadcasts the link state packet to 515 its neighbors. 517 D.3 518 Event: Link State Table refresh interrupt. 520 Action: Remove from the Link State Table any links that are 521 older than LINK_STATE_LIFETIME. 523 E. Pseudocode Implementation 525 We define two complimentary operations on packets: 526 extract(packet) and load(packet) 528 extract (packet) 529 extracts the fields of the IARP packet to the following 530 variables: {link_source, state_seq_num, radius, TTL, 531 link_dest[n], mask[n], link_metric[n][x]} 533 load (packet) 534 loads the values of the aforementioned variables into 535 the fields of the IARP packet. 537 E.1 Deliver(packet) 538 Deliver() 540 // This procedure handles both incoming link state packet and 541 // periodic advertisement of own link state 543 if(packet) 544 extract(packet); 545 else 546 { 547 link_source = MY_ID; 548 Neighbor_State(&neighbor[n],&mask[n],&metrics[n][x]); 549 TTL = R; 550 } 552 // Record link state information in Link State Table 553 add(Link_State_Table, link_source, link_dest, mask, radius, 554 link_metric, state_id, flags); 556 Haas, Pearlman, Samar Expires January 2003 [Page 7] 557 // Recompute Routing Table 558 Routing_Table =compute_routes_from_links(Link_State_Table,node); 560 // Report Routing Table update to IERP 561 IARP_updated(); 563 // Relay link state update only if link source lies inside of 564 // of routing zone (evaluated based on TTL value) 565 TTL--; 566 if(TTL > 0) 567 { 568 load(packet); 569 broadcast(packet); 570 } 571 else 572 discard(packet); 574 E.2 Refresh Link State Table args: () 576 // Periodically remove from the Link State Table link states 577 // that are older than LINK_STATE_LIFETIME 579 for each link_source (BELONGING TO) Link_State_Table 580 { 581 insert_time = Link_State_Table[link_source].insert_time; 583 if(current_time()-insert_time > LINK_STATE_LIFETIME) 584 remove_from_table(Link_State_Table, link_source); 585 } 587 // Recompute Routing Table 588 Routing_Table = compute_routes_from_links(Link_State_Table,node); 590 // Report Routing Table update to IERP 591 IARP_updated(); 593 Haas, Pearlman, Samar Expires January 2003 [Page 8] 595 5. References 597 [1] Garcia-Luna-Aceves, J.J. and Spohn, M., "Efficient Routing in 598 Packet-Radio Networks Using Link-State Information," 599 WCNC '99, September 1999. 601 [2] Haas, Z.J., Pearlman, M.R. and Samar, P., "Bordercast Resolution 602 Protocol (BRP)," IETF Internet Draft, 603 draft-ietf-manet-brp-02.txt, July 2002. 605 [3] Haas, Z.J., Pearlman, M.R. and Samar, P., "Interzone Routing 606 Protocol (IERP)," IETF Internet Draft, 607 draft-ietf-manet-ierp-02.txt, July 2002. 609 [4] Haas, Z.J., Pearlman, M.R. and Samar, P., "Zone Routing Protocol 610 (ZRP)," IETF Internet Draft, draft-ietf-manet-zrp-04.txt, 611 July 2002. 613 [5] Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L., 614 and Clausen T., "Optimized Link State Routing Protocol," 615 IETF Internet Draft, draft-ietf-manet-olsr-03.txt, 616 November 2000. 618 [6] Johnson, D.B. and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc 619 Wireless Networks," in Mobile Computing, edited by T. 620 Imielinski and H. Korth, chapter 5, pp. 153-181, 621 Kluwer, 1996. 623 [7] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, RFC 2178, 624 July 1997. 626 [8] Murthy, S. and Garcia-Luna-Aceves, J.J., "An Efficient Routing 627 Protocol for Wireless Networks," MONET, vol. 1, no. 2, 628 pp. 183-197, October 1996. 630 [9] Ogier, R. "Efficient Routing Protocols for Packet-Radio Networks 631 Based on Tree Sharing," MoMUC '99, November 1999. 633 [10] Park, V.D. and Corson, M.S., "A Highly Adaptive Distributed 634 Routing Algorithm for Mobile Wireless Networks," 635 IEEE INFOCOM'97, Kobe, Japan, 1997. 636 [11] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal 637 Configuration for the Zone Routing Protocol," IEEE JSAC, 638 August, 1999. 640 [12] Pearlman, M.R., Haas, Z.J. and S.I. Mir, "Using Routing Zones to 641 Support Route Maintenance in Ad Hoc Networks," 642 IEEE WCNC 2000, Chicago, IL, Sept. 2000. 644 Haas, Pearlman, Samar Expires January 2003 [Page 9] 646 [13] Perkins, C.E. and Royer, E.M., "Ad Hoc On-Demand Distance 647 Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 649 [14] Perkins, C.E. and Bhagwat, P., "Highly Dynamic 650 Destination-Sequenced Distance-Vector Routing (DSDV) for 651 Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994. 653 [15] Postel, J., "Internet Protocol," RFC 791, Sept. 1981. 655 Haas, Pearlman, Samar Expires January 2003 [Page 10] 657 Authors' Information 659 Zygmunt J. Haas 660 Wireless Networks Laboratory 661 323 Frank Rhodes Hall 662 School of Electrical & Computer Engineering 663 Cornell University 664 Ithaca, NY 14853 665 United States of America tel: (607) 255-3454, fax: (607) 255-9072 666 Email: haas@ece.cornell.edu 668 Marc R. Pearlman 669 389 Frank Rhodes Hall 670 School of Electrical & Computer Engineering 671 Cornell University 672 Ithaca, NY 14853 673 United States of America 674 tel: (607) 255-0236, fax: (607) 255-9072 675 Email: pearlman@ece.cornell.edu 677 Prince Samar 678 374 Frank Rhodes Hall 679 School of Electrical & Computer Engineering 680 Cornell University 681 Ithaca, NY 14853 682 United States of America 683 tel: (607) 255-9068, fax: (607) 255-9072 684 Email: samar@ece.cornell.edu 686 The MANET Working Group contacted through its chairs: 688 M. Scott Corson 689 Institute for Systems Research 690 University of Maryland College Park, MD 20742 691 (301) 405-6630 692 corson@isr.umd.edu 694 Joseph Macker 695 Information Technology Division 696 Naval Research Laboratory 697 Washington, DC 20375 698 (202) 767-2001 699 macker@itd.nrl.navy.mil 701 Haas, Pearlman, Samar Expires January 2003 [Page 11]