idnits 2.17.1 draft-ietf-manet-zone-zrp-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-23) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == Mismatching filename: the document gives the document name as 'draft-zone-routing-protocol-00', but the file name used is 'draft-ietf-manet-zone-zrp-00' ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard 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 is 1 instance of too long lines in the document, the longest one being 9 characters in excess of 72. ** There are 404 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 42 has weird spacing: '...rmation of th...' == Line 730 has weird spacing: '...ve been previ...' == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- The document date (November 1997) is 9656 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'Corson' is defined on line 1085, but no explicit reference was found in the text == Unused Reference: 'Perkins' is defined on line 1107, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'AODV' -- Possible downref: Non-RFC (?) normative reference: ref. 'Corson' -- Possible downref: Non-RFC (?) normative reference: ref. 'Haas-1' -- Possible downref: Non-RFC (?) normative reference: ref. 'Haas-2' -- Possible downref: Non-RFC (?) normative reference: ref. 'Haas-3' -- Possible downref: Non-RFC (?) normative reference: ref. 'Johnson' -- Possible downref: Non-RFC (?) normative reference: ref. 'Murthy' -- Possible downref: Non-RFC (?) normative reference: ref. 'Perkins' -- Possible downref: Non-RFC (?) normative reference: ref. 'TORA' ** Downref: Normative reference to an Experimental RFC: RFC 1075 ** Obsolete normative reference: RFC 2178 (Obsoleted by RFC 2328) Summary: 15 errors (**), 0 flaws (~~), 7 warnings (==), 10 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 Expires in six months November 1997 5 The Zone Routing Protocol (ZRP) for Ad Hoc Networks 6 8 Status of this Memo 10 This document is an Internet-Draft. Internet-Drafts are working 11 documents of the Internet Engineering Task Force (IETF), its 12 areas, and its working groups. Note that other groups may also 13 distribute working documents as Internet-Drafts. 15 Internet-Drafts are draft documents valid for a maximum of six 16 months and may be updated, replaced, or obsoleted by other 17 documents at any time. It is inappropriate to use Internet- 18 Drafts as reference material or to cite them other than as 19 ``work in progress.'' 21 To view the entire list of current Internet-Drafts, please check 22 the "1id-abstracts.txt" listing contained in the Internet-Drafts 23 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 24 (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East 25 Coast), or ftp.isi.edu (US West Coast). 27 Distribution of this memo is unlimited. 29 Abstract 31 This document describes a routing protocol for ad hoc networks. 32 In particular, it is suitable for highly versatile networks, 33 characterized by large range of nodal mobilities and large network 34 diameters. The protocol is a hybrid of a proactive and a reactive 35 schemes, allowing adjustment of its operation to the current 36 network operational conditions. 38 1. Introduction 40 One of the major challenges in designing a routing protocol for the 41 ad hoc networks stems from the fact that, on one hand, to determine 42 a packet route, at least the reachability information of the source 43 neighbors needs to be known to the source node. On the other hand, 44 in an ad hoc network, the network topology can change quite often. 45 Furthermore, as the number of network nodes can be large, the 46 potential number of destinations is also large, requiring large and 47 frequent exchange of data (e.g., routes, routes updates, or routing 48 tables) among the network nodes. Thus, the amount of update traffic 49 can be quite high. This is in contradiction with the fact that all 50 updates in a wirelessly interconnected ad hoc network travel over 51 the air and, thus, are costly in resources. 53 In general, the existing routing protocols can be classified either 54 as proactive or as reactive. Proactive protocols attempt to 55 continuously evaluate the routes within the network, so that when 56 a packet needs to be forwarded, the route is already known and can 57 be immediately used. The family of Distance-Vector protocols is an 58 example of a proactive scheme. Reactive protocols, on the other 59 hand, invoke a route determination procedure on demand only. Thus, 60 when a route is needed, some sort of global search procedure is 61 employed. The family of classical flooding algorithms belong to the 62 reactive group. Some examples of reactive (also called on-demand) 63 ad hoc network routing protocols are [Johnson] and [TORA]. 65 The advantage of the proactive schemes is that, once a route is 66 needed, there is little delay until the route is determined. In 67 reactive protocols, because route information may not be available 68 at the time a datagram is received, the delay to determine a route 69 can be quite significant. Furthermore, the global search procedure 70 of the reactive protocols requires significant control traffic. 71 Because of this long delay and excessive control traffic, pure 72 reactive routing protocols may not be applicable to real-time 73 communication. However, pure proactive schemes are likewise not 74 appropriate for the ad hoc networking environment, as they 75 continuously use a large portion of the network capacity to keep the 76 routing information current. Since nodes in an ad hoc networks move 77 quite fast, and as the changes may be more frequent than the route 78 requests, most of this routing information is never even used! This 79 results again in an excessive waste of the wireless network 80 capacity. What is needed is a protocol that, on one hand, initiates 81 the route-determination procedure on-demand, but at limited search 82 cost. The presented-here protocol, termed the "Zone Routing Protocol 83 (ZRP)," is an example of a hybrid reactive/proactive routing 84 protocol. 86 The ZRP, on one hand, limits the scope of the proactive procedure 87 only to the node's local neighborhood. On the other hand, the search 88 throughout the network, although global in nature, is done by 89 efficiently querying selected nodes in the network, as opposed to 90 querying all the network nodes. 92 A related issue is that of updates in the network topology. For a 93 routing protocol to be efficient, changes in the network topology 94 have to have local effect only. In other words, creation of a new 95 link at one end of the network is an important local event but, most 96 probably, not a significant piece of information at the other end of 97 the network. Proactive protocols tend to distribute such topological 98 changes widely in the network, incurring large costs. The ZRP limits 99 propagation of such information to the neighborhood of the change 100 only, thus limiting the cost of topological updates. 102 2.0 The Notion of Routing Zone, Zone Radius, and Bordercasting 104 A routing zone is defined for each node and includes the nodes whose 105 minimum distance in *hops* from the node in question is at most some 106 predefined number, which is referred to as the Zone Radius. An 107 example of a routing zone (for node A) of radius 2 is shown below. 109 +-----------------------------------------+ 110 | +---+ | 111 | +---+ | F | | 112 +---+ | +---+ ----| C |------+---+-----+---+ | 113 | G |-----| D | +---+ | E | | Zone of node A 114 +---+ | +---+ | +---+-----+---+ | of radius=2 115 | +---+------| B | | 116 | | A | +---+ | 117 | +---+ | 118 +-----------------------------------------+ 120 Note that in this example nodes B through E are within the routing 121 zone of A. Node G is outside A's routing zone. Also note that E can 122 be reached by two path from A, one with length 2 hops and one with 123 length 3 hope. Since the minimum is less or equal than 2, E is within 124 A's routing zone. 126 Peripheral nodes are nodes whose minimum distance to the node in 127 question is equal exactly to the zone radius. Thus, in the above 128 figure, nodes D, F, and E are A's peripheral nodes. 130 Bordercasting is a process of sending an IP datagram ([RFC-0791]) by 131 a node to all its peripheral nodes. Bordercasting can be implemented 132 either through regular IP unicast or through IP multicast (Distance 133 Vector Multicast Routing Protocol [RFC-1075]). Of course, the 134 multicasting approach is preferred to reduce the amount of traffic 135 over the air. 137 2.1 The Zone Routing Protocol (ZRP) ([Haas-1],[Haas-2]) 139 The ZRP is based on two procedures: the IntrAzone Routing Protocol 140 (IARP) and the IntErzone Routing Protocol (IERP). Through the use 141 of the IARP, each node learns the identity of and the (minimal) 142 distance to all the nodes in its routing zone. The actual IARP is 143 not specified and can include any number of protocols, such as the 144 derivatives of Distance Vector Protocol (e.g., Ad Hoc On-Demand 145 Distance Vector [AODV], Shortest Path First (e.g., OSPF 146 [RFC-2178]), [Murthy]). In fact, different portions of an ad hoc 147 network may choose to operate based on different choice of the IARP 148 protocol. Whatever the choice of IARP is, the protocol needs to be 149 modify to ensure that the scope of this operation is restricted to 150 the zone of the node in question. 152 Note that as each node needs to learn the distances to the nodes 153 within its zone only, the nodes are updated about topological 154 changes only within their routing zone. Consequently, in spite of 155 the fact that a network can be quite large, the updates are only 156 locally propagated. 158 2.2 The Interzone Routing Protocol (IERP) 160 While IARP finds routes within a zone, IERP is responsible for 161 finding routes between nodes located at distances larger than the 162 zone radius. IERP relies on bordercasting. Bordercasting is possible 163 as any node knows the identity and the distance to all the nodes in 164 its routing zone by the virtue of the IARP protocol. 166 The IERP operates as follows: The source node first checks whether 167 the destination is within its routing zone. (Again, this is possible 168 as every node knows the content of its zone). If so, the path to the 169 destination is known and no further route discovery processing is 170 required. If, on the other hand, the destination is not within the 171 source's routing zone, the source bordercasts a route request 172 (referred to here as a "request") to all its peripheral nodes. Now, 173 in turn, all the peripheral nodes execute the same algorithm: check 174 whether the destination is within their zone. If so, a route reply 175 (referred to here as a "reply") is sent back to the source 176 indicating the route to the destination. If not, the peripheral node 177 forwards the query to its peripheral nodes, which, in turn, execute 178 the same procedure. An example of this Route Discovery procedure is 179 demonstrated in the figure below. As we be shown, Thus, a route 180 within a network is specified as a sequence of nodes, separated by 181 approximately the zone radius. 183 +---+ 184 +---+ | F | 185 +---+---| C |----+---+-----+---+ +---+ 186 | D | +---+ | E |----| H | 187 +---+ | +---+-----+---+ +---+ 188 +---+----| B | | 189 | A | +---+-----+---+ +---+ 190 +---+ | G | | I | 191 +---+ +---+ 192 | 193 +---+ 194 +---+ | J | 195 | C |----+---+----+---+ +---+ 196 +---+ | K |----| L | 197 +---+ +---+ 199 The node A has a datagram to node L. Assume routing zone radius of 200 2. Since L is not in A's routing zone (which includes B,C,D,E,F,G), 201 A bordercast a routing request to its peripheral nodes: D,F,E, and 202 G. Each one of these peripheral nodes check whether L exists in their 203 routing zones. Since L is not found in any routing zones of these 204 nodes, the nodes bordercast the request to their peripheral nodes. 205 In particular, G bordercasts to K, which realizes that L is in its 206 routing zone and returns the requested route (L-K-G-A) to the query 207 source, namely A. 209 2.3 Route Accumulation procedure 211 The process by which the node receiving a query knows the path back 212 to the source of the query is the Route Accumulation procedure. In 213 particular, the Route Accumulation procedure is used to return the 214 route to the source of the query by the "last peripheral node" in 215 which routing zone the destination resides. The Route Accumulation 216 procedure is based on each node that forwards a query writing into 217 the query packet its identification. The sequence of these 218 identifications represents a path from the source node to the 219 current node, and, by reversing the order, a path from the current 220 node to the source node. 222 2.4 Terminating the IERP flood 224 It is desirable for route requests to propagate away from the source 225 and not to loop-back into a previously queried routing zone. To 226 encourage this directed spread of route requests, IERP employs two 227 loop-back prevention mechanisms. The first mechansim terminates 228 threads which loop-back on themselves. Such threads are terminated 229 when the accumulated route (excluding the previous hop) contains a 230 host which lies within its routing zone. A separate mechanism, based 231 on packet eavesdropping, is employed to reduce the overlapping of 232 parallel threads. When a host receives a route request, the IERP 233 records the request ID in its Processed Request List.* If a node 234 "officially" receives a request that has been previously recorded, 235 the new copy is discarded. Without these measures, the bordercast 236 transmission can actually generate more overhead than flooding. 238 * ICMP provides a service similar to IERP's route failure 239 notification. However, the IERP service provides additional 240 diagnostic information, allowing the source to respond to the 241 route failure more effectively. 243 2.5 Route failures notifications 245 The IERP also provides a mechanism to reactively respond to route 246 failures. A route failure is detected by the IP when the next hop in 247 a source route is determined to be unreachable (i.e., does not 248 appear in the Intrazone Routing Table). Upon detection of a route 249 failure, the IERP is alerted, and a route failure packet is 250 generated.** The route failure packet propagates back to the route's 251 source in the same manner as a route reply. When the route's source 252 receives notification of the route failure, the expired route is 253 removed from its Interzone Routing Table. The IERP may also be 254 configured to locally repair the damaged Interzone route by 255 initiating a route discovery to the unreachable next hop. 257 ** Eavesdropping nodes are only permitted to listen to route requests 258 (and record them in their Processed Request List); they are 259 prohibited from processing the request any further. 261 2.6 Bordercast Resolution Protocol (BRP) 263 The Bordercast Resolution Protocol (BRP) is included with the IERP in 264 order to provide bordercasting services which do not exist in IP. In 265 the current version of the BRP, the content of a bordercast message 266 is considered to be accessible to any host which receives the 267 message.*** Future versions of the BRP may allow for semi-private 268 bordercasting, where bordercast messages are only delivered to the 269 higher layers of the bordercast destinations (peripheral nodes). 271 *** When the BRP delivers the message to the next higher layer, a 272 flag is set to indicate whether the packet was overheard or 273 received at its intended destination. Note that this does not 274 restrict access to the message; it only serves to provide the 275 access control status of the message. 277 3.0 The ZRP Architecture 279 ......................................... 280 : ZRP : 281 : : 282 +---------+ : +---------+ +---------+ : +---------+ 283 | NDM |~~~~:~~~>| IARP |~~~~~~~~>| IERP |<~~~:~~~~| ICMP | 284 +---------+ : +---------+ +---------+ : +---------+ 285 /|\ : /|\ | BRP | : /|\ 286 | : | +---------+ : | 287 | : | /|\ : | 288 | :.......................................: | 289 | | | | 290 \|/ \|/ \|/ \|/ 291 +---------+---------+---------+---------+---------+---------+---------+ 292 | IP | 293 +---------+---------+---------+---------+---------+---------+---------+ 295 Legend: 297 A<--->B exchange of packets between protocols A & B 298 A~~~~>B information passed from protocol A to protocol B 300 Existing Protocols 301 ------------------ 302 IP Internet Protocol 303 ICMP Internet Control Message Protocol 304 ZRP Entities 305 ------------ 306 IARP IntrAzone Routing Protocol 307 IERP IntErzone Routing Protocol 308 BRP Bordercast Resolution Protocol 310 Additional Protocols 311 -------------------- 312 NDM Neighbor Discovery/Maintenance Protocol 314 Note, it is assumed that the neighbor discovery operation can be 315 implemented by the MAC/link-layer protocols. Thus the NDM protocol 316 remains unspecified here. 318 4.0 Implementation Details 320 4.1 The IntrAzone Routing Protocol (IARP) 322 Although the IARP can be implemented through various proactive 323 protocols, we present here an example of an implementation based 324 on a modified version of the Distance Vector algorithm that restricts 325 the of the algorithm's operation to the range of the routing zone 326 radius. 328 A terminal may receive new route information either from a received 329 IARP packet or from an interrupt generated by its Neighbor Discovery 330 / Maintenance (NDM) process$. In the special case when a host has 331 discovered a neighoor, the IARP is responsible for sending the new 332 neighbor the shortest route to each host which is common to both of 333 their routing zones. The terminal then records the new route 334 information in its Intrazone Routing Table. If the shortest path to 335 the host has changed, the terminal broadcasts an IARP packet 336 reflecting the change. 338 $ IARP relies on the services of a separate protocol (referred to 339 here as the Neighbor Discovery/Maintenance Protocol) to provide 340 current information about a host's neighbors. At the least, this 341 information must include the IP addresses of all the neighbors. 342 The IARP can be readily configured to support supplemental 343 neighbor information, such as link cost. 345 A. Packet Format 346 1 2 3 347 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 348 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 349 | Destination Address | 350 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 351 | Next Hop Address | 352 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 353 |Hop Cnt| 354 +-+-+-+-+ 355 Field Description: 356 * Destination Address (32 bits) 357 IP address of the destination host 358 * Next Hop Address (32 bits) 359 IP address of the "next hop" host to the destination host 360 * Hop Count (4 bits) 361 Length of the route to the destination host, measured in hops 363 B. Structures 365 B.1 Intrazone Routing Table 367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 368 | | Routes | 369 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 370 | Host | 0 | 1 | ==> | M-1 | 371 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 372 | | Next : Hop | Next : Hop | ==> | Next : Hop | 373 | | Hop : Count | Hop : Count | | Hop : Count | 374 +-+-+-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-+-+-+-:-+-+-+-+ 375 | | : | : | | : | 376 |-----------|-------:-------|-------:-------|-----|-------:-------| 377 | | : | : | | : | 378 |-----------|-------:-------|-------:-------|-----|-------:-------| 379 | | : | : | | : | 380 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 382 C. Interfaces 384 C.1 Higher Layer (N/A) 385 C.2 Lower Layer (IP) 386 C.1.1 Send() (specified in IP standard) 387 C.1.2 Deliver() (specified in IP standard) 388 C.3 NDM 389 C.3.1 Neighbor_Lost(host) 390 Used by the NDM to notify the IARP that direct contact 391 has been lost with "host". 392 C.3.2 Neighbor_Found(host) 393 Used by the NDM to notify the IARP that direct contact 394 has been confirmed with "host". 395 C.4 IERP 396 C.4.1 Host_Lost(host) 397 Used by IARP to notify the IERP that a host no longer 398 exists within the routing zone. 400 D. State Machine 402 The IARP protocol consists of only one state (IDLE). Therefore, 403 no state transitions need to be specified. The IARP immediately 404 acts upon an event and then returns back to the IDLE state. 406 Notes: 1) X is used as a label for the host running this state 407 machine. 408 2) INF is a reserved field value corresponding to 409 "infinity". 411 D.1 412 Event: An IARP packet is received containing route 413 information to a destination D. The hop count 414 associated with the received route is LESS THAN 415 the routing zone radius. 417 Action: The received route is recorded in the Intrazone 418 Routing Table. If the received route is shorter 419 than the previous shortest route to D, then a new 420 IARP packet containing route information to D 421 through X is broadcasted. 423 D.2 424 Event: An IARP packet is received containing route 425 information to a destination D. The hop count is 426 EQUAL TO the routing zone radius. 428 Action: The received route is recorded in the Intrazone 429 Routing Table. 431 D.3 432 Event: An IARP packet is received containing route 433 information to a destination D. The hop count is 434 equal to INF. 436 Action: The route to D is removed from the Intrazone 437 Routing Table. 438 1) If the Intrazone Routing Table still 439 contains a route to D and the length of the 440 shortest route has increased due to the route 441 removal, then the an IARP packet containing the 442 shortest route to D through X is broadcasted. 443 2) If the Intrazone Routing Table contains no 444 more routes to D, then an IARP packet containing 445 a route to D through X with hop count of INF is 446 broadcast. A "Host Lost" interrupt is 447 generated to alert the IERP that D has moved 448 beyond the routing zone. 450 D.4 451 Event: A "Neighbor Found" interrupt is received, 452 indicating the discovery of a neighbor host N. 454 Action: For each destination in X's Intrazone Routing 455 Table, an IARP packet is sent to N containing the 456 best route to that destination. An IARP packet is 457 then broadcasted containing the 1 hop route to N 458 through X. 460 D.5 461 Event: A "Neighbor Lost" interrupt is received, indicating 462 that host N is no longer a neighbor of X 464 Action: The one hop route to N is removed from the 465 Intrazone Routing Table. 466 1) If the Intrazone Routing Table still 467 contains a route to N and the length of the 468 shortest route has increased due to the route 469 removal, then the an IARP packet containing the 470 shortest route to N through X is broadcasted. 471 2) If the Intrazone Routing Table contains no 472 more routes to N, then an IARP packet containing 473 a route to D through X with hop count of INF is 474 broadcast. A "Host Lost" interrupt is generated 475 to alert the IERP that D has moved beyond the 476 routing zone. 478 E. Pseudocode Implementation 480 E.1 Update Intrazone Routing Table 482 if (packet arrived) 483 {host, route->next_hop,route->hop_count} <-- packet 484 else 485 { 486 {host} <-- intrpt 487 route->next_hop=host 488 if (type(intrpt) == "Neighbor Found") 489 { 490 for recorded_host = each host in Intrazone_Routing_Table 491 { 492 best_route = Intrazone_Routing_Table[recorded_host,0] 493 if (best_route->hop_count < ROUTING_ZONE_RADIUS) 494 { 495 packet <-- {recorded_host,my_id,hop_count+1} 496 send(packet,host) 497 } 498 } 499 route->hop_count=1 500 } 501 else 502 route->hop_count=INF 503 } 504 former_best_route = Intrazone_Routing_Table[host,0] 505 if (route->hop_count < INF) 506 add(Intrazone_Routing_Table[host], route) 507 else 508 remove(Intrazone_Routing_Table[host],route) 509 best_route = Intrazone_Routing_Table[host,0] 510 if (best_route != NULL) 511 { 512 if (best_route->hop_count != former_best_route->hop_count 513 && best_route->hop_count < ROUTING_ZONE_RADIUS) 514 { 515 packet <-- {host, my_id, best_route->hop_count+1} 516 broadcast(packet) 517 } 518 } 519 else 520 { 521 force_intrpt("IERP","Host Lost",{host}) 522 packet <-- {host, my_id, INF} 523 broadcast(packet) 524 } 526 4.2 IntErzone Routing Protocol (IERP) 528 The Interzone Routing Protocol (IERP) is responsible for discovering 529 routes to hosts which are beyond a terminal's routing zone. The IERP 530 collects routing information reactively, through bordercasted queries 531 which contain the accumulated routes from the source. 533 When IP receives a data packet intended for an unknown destination 534 (i.e., destination is not recorded in either the Intrazone or 535 Interzone Routing Tables), the IERP is interrupted. The IERP responds 536 by initiating a route discovery and bordercasting a route query. Each 537 query in the network is uniquely identified by the IP address of the 538 source and a request ID (local to the source). 540 Upon receipt of a route request packet, a host searches its Intrazone 541 Routing Table to determine if the requested destination is within its 542 routing zone. If so, the terminal responds with a route reply which 543 is returned to the source along the (reversed) accumulated route. If 544 the destination is not within the terminal's routing zone, the 545 terminal adds its terminal ID to the accumulated route and 546 bordercasts the route request. 548 A. Packet Format 549 1 2 3 550 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 551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 552 | Type | Request ID | Last Hop | Hop Mrker | Max Hops | 553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 554 | Destination Address | 555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 556 | Hop 0 Address (Source) | | 557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 558 | Hop 1 Address | | 559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 560 | | | 561 | | source 562 \ / route 563 \ / | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | 565 | Hop (N-1) Address | | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- 568 Field Description: 570 * Type (4 bits) 571 Identifies the type of IERP packet. The current version 572 of IERP contains three packet types: 573 REQUEST: request an Interzone source route to 574 the destination host specified in 575 Destination Address 576 REPLY: response to a request packet; includes the source route to the 577 destination host specified in 578 Destination Address 579 FAILURE: control message sent a host indicating 580 that the received data packet contains 581 an invalid source route. 583 * Request ID (10 bits) 584 Sequence number which, along with the Source Address 585 (see below) uniquely identifies any route query in the 586 network. (used only for REQUEST packets) 588 * Last Hop (6 bits) 589 Indicates the previous recipient of the IERP packet 590 (referenced as an index into the Source Route (see 591 below)) 593 * Hop Marker (6 bits) 594 Currently used to indicate the hop where a route failure 595 was detected (referenced as an index into the Source 596 Route (see below)) (used only for FAILURE packets) 598 * Max Hops (6 bits) 599 Maximum number of Interzone hops which a route query may 600 propagate. This field allows nodes to adaptively 601 configure the depth of a route search in order to 602 control the amount of IERP traffic generated. (used only 603 for REQUEST packets) 605 * Destination Address (32 bits) 606 IP address of the destination host 608 * Source Route (N*32 bits) 609 Variable length field which contains the IP addresses of 610 an N hop source route. The first subfield of the Source 611 Route contains the IP address of the route's source. 612 In general, the n-th subfield contains the IP address of 613 the n-th hop in the route. 614 For REQUEST packets, the Source Route represents the 615 incomplete accumulated route to the destination host 616 (as indicated by the Destination Address) 617 For REPLY and FAILURE packets, the Source Route contains 618 the complete route from the source host to the 619 destination host. 621 B. Structures 623 B.1 Intrazone Routing Table (See IARP Description) 625 B.2 Interzone Routing Table 627 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 628 | | Routes | 629 + Dest +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 630 | | 0 | 1 | ==> | M-| | 631 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 632 | | | | ==> | | 633 |---------|-----------|-----------|-----|-----------| 634 | | | | ==> | | 635 |---------|-----------|-----------|-----|-----------| 636 | | | | | | ==> | | 637 +-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 638 | | 639 \ / 640 \ / 641 +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ 642 | 0 |==>| 1 |==> ...==>| N-1 | source 643 +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ route 644 source first (N-1) 645 host hop hop 646 B.3 Processed Request List 648 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 649 | Source | Request ID | 650 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 651 | | | 652 |-----------|---------------| 653 | | | 654 |-----------|---------------| 655 | | | 656 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 658 C. Interfaces 660 C.1 Higher Layer (N/A) 661 C.2 Lower Layer (BRP) 662 C.2.1 Send() (same interface as IP send()) 663 Used by the IERP to request transmission of a data 664 packet. 665 C.2.2 Deliver() (same interface as IP deliver()) 666 Used by the BRP to alert the IERP of the arrival of a 667 data packet. 668 C.3 IARP 669 C.3.1 Neighbor_Lost(host) 670 Used by the NDM to notify the IARP that direct contact 671 has been lost with "host". 672 C.3.2 Neighbor_Found(host) 673 Used by the NDM to notify the IARP that direct contact 674 has been confirmed with "host". 675 C.4 ICMP 676 C.4.1 Host_Unreachable() (specified in ICMP standard) 677 C.4.2 Source_Route_Failed() (specified in ICMP standard) 679 D. State Machine 681 The IERP protocol consists of only one state (IDLE). Therefore, 682 no state transitions need to be specified. The IERP immediately 683 acts upon an event and then returns back to the IDLE state. 685 Note: 1) X is used as a label for the host running this state 686 machine. 688 D.1 689 Event: A "Host Lost" interrupt is received, indicating 690 that the host H has moved beyond the routing zone. 692 Action: Remove every route from the Interzone Routing Table 693 which contains H. A limited depth route discovery 694 to H is initiated. An IERP request packet is 695 created with the destination addresss set to H and 696 the source route initialized with the IP address 697 of X. The request packet is then bordercasted. 699 D.2 700 Event: A "Host Unreachable" interrupt is received from the 701 ICMP, indicating an unknown destination host D. 703 Action: A full depth route discovery to the lost host is 704 initiated. An IERP request packet is created with 705 the destination addresss set to H and the source 706 route initialized with the IP address of X. The 707 request packet is then bordercasted. 709 D.3 710 Event: An "Source Route Failed" interrupt is received from 711 the ICMP, indicating that the next hop specified in 712 an IP source route does not appear within the 713 routing zone. 715 Action: A route failure packet containing the invalid route 716 is sent to the route's source with the hop marker 717 indicating X as the host where a route failure was 718 detected. 720 D.4 721 Event: An IERP request packet is received with a 722 destination that appears within X's routing zone. 724 Action: The request is recorded in the Processed Request 725 List. In order to be processed further, four 726 conditions must be satisfied. First, the received 727 packet must not be flagged as overheard. Second, 728 the number of hops in the route must not exceed the 729 maximum hop count. Third, the request must not 730 have been previously recorded. Finally, no hops in 731 the route (except the last_hop) may lie within X's 732 routing zone. X appends its IP address to the route 733 and sends an IERP reply packet to the preceding hop 734 in the route. 736 D.5 737 Event: An IERP request packet is received with a 738 destination that DOES NOT appear within X's routing 739 zone. 741 Action: The request is recorded in the Processed Request 742 List. In order to be processed further, four 743 conditions must be satisfied. First, the received 744 packet must not be flagged as overheard. Second, 745 the number of hops in the route must not exceed the 746 maximum hop count. Third, the request must not have 747 been previously recorded. Finally, no hops in the 748 route (except the last_hop) may lie within X's 749 routing zone. X appends its IP address to the route 750 and is bordercasts an IERP request packet 751 containing the updated route. 753 D.6 754 Event: An IERP reply packet is received containing X as 755 the source host. 757 Action: The received source route is recorded in Interzone 758 Routing Table. 760 D.7 761 Event: An IERP reply packet is received containing a node 762 other than X as the source host. 764 Action: The route reply packet is fowarded to the preceding 765 hop in the route 767 D.8 768 Event: An IERP failure packet is received containing X as 769 the source host. 771 Action: X removes all routes from its Interzone Routing 772 table which contain the broken link specified by 773 the bad hop field. 775 D.9 776 Event: An IERP failure packet is received containing a 777 node other than X as the source host. 779 Action: X fowards the route reply packet to the preceding 780 hop in the route 782 E. Pseudocode Implementation 784 E.1 Intrazone Node Lost 786 {lost_host} <-- intrpt 787 for host = each host in Interzone Routing Table 788 { 789 m=0 790 while (Interzone_Routing_Table[host,m] != NULL) 791 { 792 route=Interzone_Routing_Table[host,m] 793 if (lost_host (EXISTS IN) route) 794 remove(Interzone_Routing_Table[host,m]) 795 else 796 m++ 797 } 798 } 799 force_intrpt("IERP","repair",{lost_host}) 801 E.2 Initiate Route Discovery 803 {dest} <-- intrpt 804 req_id++ 805 route(0)=my_id 806 last_hop=0 807 if (type(intrpt) == "repair") 808 max_hops=MAX_REPAIR_HOPS 809 else 810 max_hops=MAX_REQUEST_HOPS 811 packet <-- {REQUEST, req_id, last_hop, NULL, max_hops, dest, 812 route} 813 bordercast(packet) 814 add (Processed_Request_List, {my_id, req_id}) 816 E.3 Report Route Failure 818 {route,dest} <-- intrpt 819 last_hop=0 820 while (route(last_hop) != my_id) 821 last_hop++ 822 packet <-- {FAILURE, NULL, last_hop, last_hop, NULL, dest, 823 route} 824 send(packet, route(last_hop-1)) 826 E.4 Receive IERP Packet 828 {pk_type, req_id, last_hop, bad_hop, max_hops, route} <-- 829 packet 830 {overheard} <-- intrpt 831 switch(pk_type) 832 { 833 case: REQUEST 834 add({Processed_Request_List, source, req_id) 835 LSP1_terminate = FALSE 836 n=0 837 while (!LSP1_terminate && n < last_hop) 838 { 839 if (Intrazone_Routing_Table[route(n)]!=NULL) 840 LSP1_terminate = TRUE 841 n++ 842 } 843 LSP2_terminate = (Processed_Request_List[source,req_id] 844 != NULL) 845 if (!overheard && !LSP1_terminate && !LSP2_terminate && 846 last_hop < max_hops) 847 { 848 last_hop++ 849 route(last_hop)=my_id 850 if (dest (EXISTS IN) Intrazone_Routing_Table) 851 { 852 packet<--{REPLY,req_id,last_hop,bad_hop,max_hops, 853 dest,route} 855 send(packet, route(last_hop-1)) 856 } 857 else 858 { 859 packet<--{REQUEST,req_id,last_hop,bad_hop,max_hops, 860 dest,route} 861 bordercast(packet) 862 } 863 } 864 break 865 case: REPLY 866 case: FAILURE 867 if (route(0) == my_id) 868 { 869 if (pk_type == ROUTE_REPLY) 870 add(Interzone_Routing_Table, route) 871 else 872 { 873 link(0)=route(bad_hop) 874 link(1)=route(bad_hop+1) 875 remove(Interzone_Routing_Table,link) 876 } 877 } 878 else 879 { 880 last_hop -- 881 packet <-- {pk_type,req_id,last_hop,bad_hop,max_hops, 882 dest,route} 883 send(packet, route(last_hop-1)) 884 } 885 } 887 4.3 Bordercast Resolution Protocol (BRP) 889 The higher layer interface of the BRP is designed to be compatible 890 with any IP based application. However, it is assumed that the 891 routing zone hierarchy is visible only to the ZRP entities, making 892 bordercasting services only of use to the IERP. 894 Upon receipt of a (IERP) packet to be bordercasted, the BRP resolves 895 the bordercast address into the individual IP addresses of the 896 peripheral nodes. The received packet is then encapsulated into a BRP 897 packet and sent to each peripheral node (via IP broadcast 898 transmission). 900 When a BRP packet is delivered from IP, the (IERP) data is 901 decapsulated and passed on to the higher layer. If the BRP packet 902 has not reached its destination, the BRP is responsible for 903 forwarding the packet to the next hop toward its destination. 905 A. Packet Format 907 1 2 3 908 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 909 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 910 | Destination Address | 911 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 912 | Next Hop Address | 913 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 914 | Data | 915 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 917 Field Description: 919 * Destination Address (32 bits) 920 IP address of the destination host 922 * Next Hop Address (32 bits) 923 IP address of the "next hop" host to the destination 924 host 926 * Data (variable length) 927 Encapsulated data 929 B. Structures 931 B.1 Intrazone Routing Table (see IARP description) 933 C. Interfaces 935 C.1 Higher Layer (ie. IERP) 936 C.2.1 Send() (same interface as IP Send() primitive) 937 Used by higher layer protocol to request transmission of 938 a data packet 939 C.2.2 Deliver() (same interface as IP Deliver() primitive) 940 Used by the BRP to alert the higher layer protocol of 941 the arrival of a data packet 942 C.2 Lower Layer (IP) 943 C.2.1 Send() (specified in IP standard) 944 C.2.2 Deliver() (specified in IP standard) 946 D. State Machine 948 The BRP protocol consists of only one state (IDLE). Therefore, 949 no state transitions need to be specified. The BRP immediately 950 acts upon an event and then returns back to the IDLE state. 952 Notes: 1) X is used as a label for the host running this state 953 machine. 954 2) NULL is a reserved field value, corresponding to an 955 invalid IP address. 957 D.1 958 Event: A packet is received from the IERP, destined for 959 the BORDERCAST address. 961 Action: The IERP packet is encapsulated in a BRP packet. A 962 copy of the BRP packet is made for each peripheral 963 host, P. (i.e., each host in X's Intrazone Routing 964 Table whose shortest route is ROUTING_ZONE_RADIUS 965 hops away from X). The packet's destination address 966 is set to the IP address of P and the next hop 967 address is set to the IP address of the next hop 968 to P (from X). Each packet is then broadcasted. 970 D.2 971 Event: A packet is received from the IERP, destined for a 972 non-BORDERCAST address. 974 Action: The IERP packet is encapsulated in a BRP packet. 975 The BRP packet`s destination address and next hop 976 address fields are cleared and the BRP packet is 977 sent to the specified destination. 979 D.3 980 Event: A BRP packet is received from the IP layer. The BRP 981 packet contains a next hop address EQUAL TO NULL. 983 Action: The data is decapuslated from the BRP packet and 984 delivered to the IERP, with the overhead flag set 985 to FALSE. 987 D.4 988 Event: A BRP packet is received from the IP layer. The BRP 989 packet contains a valid next hop address and a 990 destination address EQUAL TO X. 992 Action: The data is decapuslated from the BRP packet and 993 delivered to the IERP, with the overhead flag set 994 to FALSE. 996 D.5 997 Event: A BRP packet is received from the IP layer. The BRP 998 packet contains a valid next hop address EQUAL TO 999 X and a destination address NOT EQUAL TO X. 1001 Action: The data is decapuslated from the BRP packet and 1002 delivered to the IERP, with the overhead flag set 1003 to TRUE. The received BRP packet is copied, the 1004 next hop address field is updated by querying the 1005 Intrazone Routing Table, and the new packet is 1006 broadcasted. 1008 D.6 1009 Event: A BRP packet is received from the IP layer. The BRP 1010 packet contains a valid next hop address NOT EQUAL 1011 TO X and a destination address NOT EQUAL TO X. 1013 Action: The data is decapuslated from the BRP packet and 1014 delivered to the IERP, with the overhead flag set 1015 to TRUE. 1017 E. Pseudocode Implementation 1019 E.1 Receive Data Packet from IERP 1021 {dest} <-- intrpt 1022 if (dest == BORDERCAST) 1023 { 1024 for (host = each host in Intrazone_Routing_Table) 1025 { 1026 if (Intrazone_Routing_Table[host,0]->hop_count 1027 ==ROUTING_ZONE_RADIUS) 1028 { 1029 next_hop=Intrazone_Routing_Table[host,0]->next_hop 1030 packet<--{host,next_hop,data_packet} 1031 broadcast(packet) 1032 } 1033 } 1034 } 1035 else 1036 { 1037 packet<--{dest,NULL,data_packet} 1038 send(packet,dest) 1039 } 1041 E.2 Receive Packet from IP 1043 {dest,next_hop,data}<--packet 1044 overheard=FALSE 1045 if (next_hop != NULL) 1046 { 1047 if (next_hop == my_id) 1048 { 1049 if(dest != my_id) 1050 { 1051 overheard=TRUE 1052 next_hop = Intrazone_Routing_Table[dest,0]->next_hop 1053 packet<--{dest,next_hop,data} 1054 broadcast(packet) 1055 } 1056 } 1057 else 1058 overheard=TRUE 1059 } 1060 deliver(IERP,data,{overheard}) 1062 5.0 Other Considerations 1064 5.1 Sizing the Zone Radius 1066 The value of the zone radius determines the performance of the ZRP 1067 protocol. In general, highly mobile networks should set the zone 1068 radius to a smaller values, while in more stationary networks the 1069 zone radius should be larger. Similarly, in very active networks 1070 (frequent query requests), the zone radius should be larger, and in 1071 low-activity networks, the zone radius should be smaller. 1073 We believe that setting the size of the zone radius should be 1074 performed by the administration of the network, if one exists, or 1075 by the manufacturer, as a default value. Although some guidance can 1076 be given as to "optimal" value of the zone radius [Haas-3], 1077 additional constrains and operational conditions may affect this 1078 choice. 1080 6.0 References 1082 [AODV] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing", 1083 MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, 1084 November 3, 1997 1085 [Corson] Corson, M.S., and Ephremides, A., "A Distributed Routing 1086 Algorithm for Mobile Wireless Networks", ACM/Baltzer 1087 journal on Wireless Networks, January 1995 1089 [Haas-1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable 1090 Wireless Networks", ICUPC'97, San Diego, CA, Oct. 12, 1997 1092 [Haas-2] Haas, Z.J., and Pearlman, M.R., "Providing Ad-Hoc 1093 Connectivity with the Reconfigurable Wireless Networks", 1094 submitted for journal publication. 1096 [Haas-3] Haas, Z.J., "Design Choices in Ad-Hoc Networking", 1097 in preparation. 1099 [Johnson] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing 1100 in Ad-Hoc Wireless Networks," in Mobile Computing, 1101 T. Imielinski and H. Korth, editors, Kluwer, 1996 1103 [Murthy] Murthy, S., and Garcia-Luna-Aceves, J.J., "A Routing 1104 Protocol for Packet Radio Networks", MOBICOM'95, 1105 November 14-15, 1995 1107 [Perkins] Perkins, C.E., and Bhagwat, P., "Highly Dynamic 1108 Destination-Sequenced Distance-Vector Routing (DSDV) for 1109 Mobile Computers, ACM SIGCOMM, vol.24, no.4, October 1994 1111 [TORA] Macker, J., "Mobile Ad Hoc Internetworking", MILCOM'97 1112 panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997 1114 [RFC-0791] Postel, J., Editor, "Internet Protocol", STD 5, RFC 791, 1115 September 1981 1117 [RFC-1075] Waitzman, D., Partridge, C., Deering, S.E., "Distance 1118 Vector Multicast Routing Protocol", RFC 1075, Nov. 1, 1988 1120 [RFC-2178] Moy, J., "OSPF Version 2", INTERNET DRAFT STANDARD, 1121 RFC 2178, July 1997 1123 Authors' Information 1125 Zygmunt J. Haas 1126 Wireless Networks Laboratory 1127 323 Frank Rhodes Hall 1128 School of Electrial Engineering 1129 Cornell University 1130 Ithaca, NY 14853 1131 United States of America 1132 tel: (607) 255-3454, fax: (607) 255-9072 1133 Email: haas@acm.org or haas@ee.cornell.edu 1135 Marc R. Pearlman 1136 319 Frank Rhodes Hall 1137 School of Electrial Engineering 1138 Cornell University 1139 Ithaca, NY 14853 1140 United States of America 1141 Email: pearlman@ee.cornell.edu 1143 The MANET Working Group contacted through its chairs: 1145 M. Scott Corson 1146 Institute for Systems Research 1147 University of Maryland 1148 College Park, MD 20742 1149 (301) 405-6630 1150 corson@isr.umd.edu 1152 Joseph Macker 1153 Information Technology Division 1154 Naval Research Laboratory 1155 Washington, DC 20375 1156 (202) 767-2001 1157 macker@itd.nrl.navy.mil