idnits 2.17.1 draft-ietf-manet-lanmar-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 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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 (May 17, 2001) is 8381 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' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' Summary: 4 errors (**), 0 flaws (~~), 1 warning (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF MANET Working Group Mario Gerla 3 INTERNET-DRAFT Xiaoyan Hong 4 Expiration: November 17, 2001 Li Ma 5 University of California, Los Angeles 6 Guangyu Pei 7 Rockwell Science Center 8 May 17, 2001 10 Landmark Routing Protocol (LANMAR) for Large Scale Ad Hoc Networks 12 14 Status of This Memo 16 This document is an Internet-Draft and is in full conformance with 17 all provisions of Section 10 of RFC 2026 except that the right to 18 produce derivative works is not granted. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note 22 that other groups may also distribute working documents as 23 Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at 27 any time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress". 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 This Internet-Draft is a submission to the IETF Mobile Ad Hoc 37 Networks (MANET) Working Group. Comments on this draft may be sent 38 to the Working Group at manet@itd.nrl.navy.mil, or may be sent 39 directly to the authors. 41 Abstract 43 The Landmark Routing Protocol (LANMAR) utilizes the concept of 44 "landmark" for scalable routing in large, mobile ad hoc networks. 45 It relies on the notion of group mobility: i.e., a logical group 46 (for example a team of coworkers at a convention) moves in a 47 coordinated fashion. The existence of such logical group can be 48 efficiently reflected in the addressing scheme. It assumes that 49 an IP like address is used consisting of a group ID (or subnet ID) 50 and a host ID, i.e. . A landmark is dynamically 51 elected in each group. The route to a landmark is propagated 52 throughout the network using a Distance Vector mechanism. 53 Separately, each node in the network uses a "scoped" routing 54 algorithm (e.g., FSR) to learn about routes within a given (max 55 number of hops) scope. To route a packet to a destination outside 56 its scope, a node will direct the packet to the landmark 57 corresponding to the group ID of such destination. Once the packet 58 is within the scope of the landmark, it will typically be routed 59 directly to the destination. Remote groups of nodes are 60 "summarized" by the corresponding landmarks. The solution to 61 drifters (i.e., nodes outside of the scope of their landmark) is 62 also handled by LANMAR. Landmark dynamic election enables LANMAR 63 to cope with mobile environments. Thus, by using the truncated 64 local routing table and the "summarized" landmark distance vector, 65 LANMAR dramatically reduces routing table size and update overhead 66 in large nets. LANMAR is well suited to provide an efficient and 67 scalable routing solution in large, mobile, ad hoc environments in 68 which group behavior applies and high mobility renders traditional 69 routing schemes inefficient. 71 Contents 73 Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . 1 75 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 77 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 79 2. Changes ....................................................... 5 81 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 82 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5 83 3.2. Specification Language . . . . . . . . . . . . . . . . . 5 85 4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 6 86 4.1. Networking Context . . . . . . . . . . . . . . . . . . . 6 87 4.2. Protocol Characteristics and Mechanisms . . . . . . . . 6 89 5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8 90 5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8 91 5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9 92 5.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10 94 6. Protocol Specifications . . . . . . . . . . . . . . . . . . . 10 95 6.1. Data Structures . . . . . . . . . . . . . . . . . . . 11 96 6.1.1 Landmark Status tuple . . . . . . . . . . . . . . 11 97 6.1.2 Landmark Distance Vector . . . . . . . . . . . . 11 98 6.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11 99 6.1.4 Neighbor List . . . . . . . . . . . . . . . . . . 12 100 6.2. LANMAR Update Message Format . . . . . . . . . . . . 12 101 6.2.1 Description of the fields . . . . . . . . . . . . 12 102 6.3. Processing Landmark Updates . . . . . . . . . . . . . . 13 103 6.3.1 Originating a Landmark in a Subnet . . . . . . . 13 104 6.3.2 Receiving Landmark Updates . . . . . . . . . . . 14 105 6.3.3 Winner Competition . . . . . . . . . . . . . . . 14 106 6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14 107 6.4.1 Originating a Drifter Entry . . . . . . . . . . . 15 108 6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 15 109 6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 15 110 6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 15 112 7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15 114 8. Discussion about Storage and Processing Overhead for Drifters 16 116 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 16 118 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 120 Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17 122 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 124 1. Introduction 126 This document describes the Landmark Routing Protocol (LANMAR) [1,2] 127 developed by the Wireless Adaptive Mobility (WAM) Laboratory [4] at 128 Computer Science Department, University of California, Los Angeles. 130 The concept of landmark routing was first introduced in wired area 131 networks [6]. The original scheme required predefined multi-level 132 hierarchical addressing. The hierarchical address of each node 133 reflects its position within the hierarchy and helps to find a route 134 to it. Each node knows the routes to all the nodes within its 135 hierarchical partition. Moreover, each node knows the routes to 136 various "landmarks" at different hierarchical levels. Packet 137 forwarding is consistent with the landmark hierarchy and the path 138 is gradually refined from the top level hierarchy to lower levels 139 as a packet approaches its destination. 141 LANMAR borrows the concept of landmark and extends it to the 142 wireless ad hoc environment. LANMAR scheme does not require 143 predefined hierarchical address, but it uses the notion of landmarks 144 to keep track of logical subnets in which the members have a 145 commonality of interests and are likely to move as a "group" 146 (e.g., brigade in the battlefield, a group of students from same 147 class and a team of co-workers at a convention). Each such 148 logical group has an elected landmark. For each group, 149 underlying "scoped" routing algorithm will provide a one-level 150 scope. The routing update packets are restricted only within the 151 scope. Accurate routing information for nodes within scope is 152 maintained. The routing information to remote nodes (nodes outside 153 the node's scope) is "summarized" by the corresponding landmarks. 154 Thus, the LANMAR scheme largely reduces the routing table size and 155 the routing update traffic overhead. It greatly improves 156 scalability. 158 In addition, in order to recover from landmark failures, 159 a "landmark" node is elected in each subnet. Landmark election 160 provides a flexible way for the LANMAR protocol to cope with a 161 dynamic and mobile network. The protocol also provides a solution 162 for drifters (Nodes that are outside the fisheye scopes of the 163 landmarks of their logical groups). Extra storage, processing and 164 line overhead will be incurred for landmark election and drifter 165 bookkeeping. However, the design of the algorithms provides 166 solutions without compromising scalability. For example, the 167 routing overhead for handling drifters is typically small if the 168 fraction of drifting nodes is small. More analysis is given in 169 Section 8. 171 The LANMAR runs on top of a proactive routing protocol. It 172 requires that the underlying routing protocol support the scoped 173 subnetworking. Fisheye State Routing Protocol (FSR) [7,8] is 174 such a protocol that supports LANMAR. In FSR, the link state 175 protocol is used within the scope. The fisheye scope 176 technique can also be applied to a distance vector type protocol, 177 such as DSDV [3], in which the hop distance can be used to 178 bind the scope for routing message updating. The main advantage of 179 LANMAR is that the routing table includes only the nodes within the 180 scope and the landmark nodes. This feature greatly improves 181 scalability by reducing routing table size and update traffic O/H. 183 Thus the Landmark Routing Protocol provides an efficient and 184 scalable routing solution for a mobile, ad hoc environment while 185 keeping line and storage overhead (O/H) low. Moreover, the 186 election provides a much needed recovery from landmark failures. 188 2. Changes 190 Major changes from version 00 to version 01: 192 - A destination sequence number for each landmark is used to 193 ensure loop-free updates for a particular landmark. 195 - Landmark updates are propagated in separate messages, instead of 196 being piggybacked on local routing updates. This modification 197 decouples landmark routing from the underlying proactive routing 198 protocol. 200 3. Terminology 202 3.1. General Terms 204 This section defines terminology used in LANMAR. 206 node 208 A MANET router that implements Landmark Routing Protocol. 210 neighbor 212 Nodes that are within the radio transmission range. 214 scope 216 A zone that is bounded by hop distances. 218 host protocol 220 A proactive protocol underlies the Landmark Routing Protocol. 222 subnet 224 Logical groups of nodes that present similar motion behavior. 226 group 228 This term is used interchangeably with subnet. 230 3.2. Specification Language 232 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 233 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 234 document are to be interpreted as described in RFC 2119 [5]. 236 4. Protocol Applicability 238 4.1. Networking Context 240 LANMAR is best suited for large scale mobile ad hoc wireless 241 networks. The landmark scheme on top of "scoped" routing algorithm 242 has large advantages in reducing routing update packet size and 243 keeping progressive accurate routes to remote nodes. It achieves 244 high data packet delivery ratio. Moreover, the fact that the route 245 error is blurred by distance obviously reduces the sensitivity to 246 network size. 248 LANMAR is also suited for high mobility ad hoc wireless networks. 249 This is because in a mobility environment, a change on a link far 250 away from the source does not necessarily cause a change in the 251 routing table at the source and that all the information about 252 remote nodes is summarized by landmarks. 254 4.2. Protocol Characteristics and Mechanisms 256 * Does the protocol provide support for unidirectional links?(if so, 257 how?) 259 No. 261 * Does the protocol require the use of tunneling? (if so, how?) 262 No. 264 * Does the protocol require using some form of source routing? (if 265 so, how?) 267 No. 269 * Does the protocol require the use of periodic messaging? (if so, 270 how?) 272 Yes. The LANMAR periodically broadcasts landmark information 273 to its neighbors. 275 * Does the protocol require the use of reliable or sequenced packet 276 delivery? (if so, how?) 278 No. As the packets are sent periodically, they need not be 279 sent reliably. 281 * Does the protocol provide support for routing through a multi- 282 technology routing fabric? (if so, how?) 284 Yes. It is assumed that each node's network interface is 285 assigned a unique IP address. 287 * Does the protocol provide support for multiple hosts per router? 288 (if so, how?) 290 Yes. The router that has multiple hosts can use network ID of 291 these hosts as the address to participate LANMAR. 293 * Does the protocol support the IP addressing architecture? (if so, 294 how?) 296 Yes. Each node is assumed to have a unique IP address (or 297 set of unique IP addresses in the case of multiple interfaces). 298 The LANMAR references all nodes/interfaces by their IP address. 299 This version of the LANMAR also supports IP network addressing 300 (network prefixes) for routers that provide access to a 301 network of non-router hosts. 303 * Does the protocol require link or neighbor status sensing (if so, 304 how?) 306 No. 308 * Does the protocol have dependence on a central entity? (if so, 309 how?) 311 No. 313 * Does the protocol function reactively? (if so, how?) 315 No. 317 * Does the protocol function proactively? (if so, how?) 319 Yes. The LANMAR proactively maintains landmark information 320 at each node. 322 * Does the protocol provide loop-free routing? (if so, how?) 324 Yes. For in-scope destinations, the protocol uses routing 325 paths learned from the host protocol. If the host protocol 326 provides loop-free routing, e.g., FSR and DSDV, so does LANMAR. 327 For out-scope destinations, only routes to landmarks are used. 328 Because these routes are DSDV, it is loop free. When a packet 329 approaches the destination, in-scope routes are used again. 331 * Does the protocol provide for sleep period operation?(if so, how?) 333 Yes. However, this requires TDMA MAC layer support. The 334 router can be scheduled to sleep during idle periods. 336 * Does the protocol provide some form of security? (if so, how?) 338 Yes. When a node broadcasts routing update message, only 339 entries of in-scope nodes and landmarks are included. This 340 will prevent other remote nodes from being heard. 342 * Does the protocol provide support for utilizing multi-channel, 343 link-layer technologies? (if so, how?) 345 Yes. In fact, the multi-channel can be used to separate 346 routing messages from user data packets. 348 5. Protocol Overview 350 5.1. Protocol Descriptions 352 As mentioned in Section 1, the landmark concept we adopt here uses 353 the notion of logical subnets in which the members have a 354 commonality of interests and are likely to move as a "group". 355 Each logical subnet has one node serving as a "landmark" of that 356 subnet. The protocol requires that the landmark of each subnet have 357 the knowledge of all the members in its group. The LANMAR protocol 358 also uses a scope at each node. The size of the scope is a 359 parameter measured in hop distance. It is chosen in such a way that 360 if a node is at the center of a subnet, the scope will cover the 361 majority of the subnet members. If the shape of a subnet is likely 362 to be a cycle, the center node's scope will cover all the members of 363 the subnet. If this center node is elected as a landmark, it 364 fulfills the requirement of the protocol. The elected landmark 365 uses a destination sequence number to ensure its routing entry 366 update is loop-free. The landmarks are propagated in a 367 distance vector mechanism. Each node maintains a distance vector 368 for landmarks of all the subnets. The size of the landmark distance 369 vector equals to the number of logical subnets and thus landmark 370 nodes. If a landmark does not locate at the center, there will be 371 some members drifting off its scope. The landmark will keep a 372 distance vector for drifters of its group. The distance vectors 373 for landmarks and drifters are exchanged among neighbors in 374 periodical routing update packets. 376 The LANMAR relies on an underlying proactive protocol with the 377 ability of providing "scoped" routing. In the scoped routing, each 378 node broadcasts routing information periodically to its immediate 379 neighbors. In each update packet, the node sends routing table 380 entries within its scope. The host routing protocol uses sequence 381 numbers for routing entries. Each node advances its sequence 382 number before sending an update packet. Through the exchange 383 process, the table entries with larger sequence numbers replace 384 the ones with smaller sequence numbers. 386 Let's take, for example, the FSR as our host protocol. For nodes 387 within the scope, the updating is in a certain frequency. But 388 for nodes beyond the scope, the update frequency is reduced to 389 zero; Only the update frequency of the landmark nodes remains 390 unaltered. As a result, each node maintains accurate routing 391 information for in-scope nodes and keep routing directions to the 392 landmark nodes for out-scope nodes, or say, for remote groups. 393 A packet directed to a remote destination initially aims at the 394 landmark of that remote group; as it gets closer to the landmark, 395 it may eventually switch to the accurate route to the destination 396 provided by in-scope nodes of the destination. 398 5.2. Landmark Election 400 Dynamic election/re-election of landmark node is essential for 401 LANMAR to work in a wireless mobile environment. Basically, each 402 node tracks other nodes of its group in its scope and computes 403 "weight", e.g. the number of the nodes it has found. At the 404 beginning of the LANMAR, no landmark exists. Protocol LANMAR 405 only uses the host protocol functionality. As host routing 406 computation progresses, one of the nodes will learn (from 407 the host protocol's routing table) that more than a certain number 408 of group members (say, T) are in its scope. It then proclaims 409 itself as a landmark for this group and adds itself to the landmark 410 distance vector. Landmarks broadcast the election weights to 411 the neighbors jointly with the landmark update packets. 413 When more than one node declares itself as a landmark in the same 414 group, as the landmark information floods out, each node will 415 perform a winner competition procedure. Only one landmark for each 416 group will survive and it will be elected. To avoid flapping 417 between landmarks (very possible in a mobile situation), we use 418 hysteresis in the replacement of an existing landmark. I.e., the 419 old Landmark is replaced by the new one only if its weight is, say 420 less than 1/2 of the weight of the current election winner. Once 421 ousted, the old leader needs the full weight superiority to be 422 reinstated. 424 This procedure is carried out periodically in the background (low 425 overhead, anyway). At steady state, a landmark propagates its 426 presence to all other nodes like a sink in DSDV. It is extremely 427 simple and it converges (by definition). In a mobile environment, 428 an elected landmark may eventually lose its role. The role shifting 429 is a frequent event. In a transient period, there exist several 430 landmarks in a single group. The transient period may be actually 431 the norm at high mobility. This transient behavior can be 432 drastically reduced by using hysteresis. 434 When a landmark dies, its neighbors will detect the silence after 435 a given timeout. The neighbors of the same group will then take 436 the responsibilities as landmarks and broadcast new landmark 437 information. A new round of landmark election then floods over 438 the entire network. 440 5.3. Drifters 442 Typically, all members in a logical subnet are within the scope of 443 the landmark, thus the landmark has a route to all members. It may 444 happen, however, that some of the members "drift off" the scope, 445 for example, a tank in a battalion may become stranded or lost. 446 To keep track of such "drifters", i.e., to make the route to them 447 known to the landmark, the following modification to the routing 448 table exchange is necessary. Each node, say i, on the shortest 449 path between a landmark L and a drifter l associated with that 450 landmark keeps a distance vector entry to l. Note that if l is 451 within the scope of i, this entry is already included in the 452 routing table of node i. When i transmits its distance vector to 453 neighbor, say j, then j will retain the entry to member l only if 454 d(j,l) is smaller than the scope or d(j,L) is smaller than d(i,L). 455 The latter condition occurs if j is on the shortest path from i 456 (and therefore from l) to L. This way, a path is maintained from 457 the landmark to each of its members, including drifters. The 458 procedure starts from l, at the time when a node finds it becomes 459 a drifter. It informs the landmark hop by hop about its presence. 461 The occurrences of drifters are dynamic in a mobile network. In 462 order to timely remove the staled drifter information, the time 463 when a node hears a drifter is recorded. 465 6. Protocol Specifications 467 This section discusses the operation of LANMAR routing protocol. 468 The sending and receiving of landmark updates are in the proactive 469 nature. The routing packets are processed separately from 470 ordinary data packets. 472 6.1. Data Structures 474 Each node has a unique "logical" identifier defined by a subnet 475 field and a host field. The host field is unique in the subnet and 476 might in fact coincide with the physical address. The "logical" 477 identifier can also be an IP address when the subnet address can 478 logically group the nodes. Moreover, each node keeps a landmark 479 status tuple. As LANMAR runs on top of a host routing protocol, 480 it shares the underlying routing table structures. LANMAR 481 maintains a neighbor list and shares it with the host protocol. 482 In addition, LANMAR keeps a drifter list and a landmark distance 483 vector. 485 6.1.1. Landmark Status Tuple 487 Each node has not only a "logical" identifier, which basically is 488 its address, but also a landmark status tuple. The tuple includes 489 a flag which indicates whether the node is a landmark or not, a 490 election weight (the number of group members the node detects within 491 its scope) and a sequence number. When a node is elected, the 492 status tuple will be copied to its landmark distance vector. The 493 sequence number is advanced. There are three fields for a tuple: 494 - Landmark flag 495 - Number of group members in its scope 496 - Sequence number 498 6.1.2. Landmark Distance Vector 500 Landmark distance vector (LMDV) gives the next hop information to 501 all landmarks in the network. Every subnet has an entry in LMDV. 502 The latest route information to the landmark of each subnet is 503 learned when a landmark update message is received. LMDV functions 504 as a part of the routing table. It has the following fields: 505 - Landmark status tuple 506 - Next hop address 507 - Distance 509 6.1.3. Drifter List 511 The drifter list (DFDV) of LANMAR provides the next hop information 512 of the drifters known to the current node. The entries are updated 513 with landmark update message. The latest time a drifter is heard 514 is recorded in DFDV. The DFDV works as a part of routing table. 515 It has the following fields: 516 - Destination drifter address 517 - Next hop address 518 - Distance 519 - Last heard time 521 6.1.4. Neighbor List 523 The neighbor list of LANMAR keeps current neighbor information for 524 a node. The latest time a neighbor is heard is recorded. The 525 neighbor list has the following fields: 526 - Neighbor address 527 - Neighbor landmark flag 528 - Last heard time 530 6.2. LANMAR Update Message Format 532 There is only one message type of LANMAR protocol. The messages are 533 periodically exchanged with neighbors. They update the landmark 534 distance vector LMDV and the drifter list DFDV. The processing of 535 the LMDV and DFDV will be describe separately. The following format 536 does not include the node's identifier because it can be obtained 537 from IP Header. 539 0 1 2 3 540 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 541 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 542 | Landmark Flag | N_landmarks | N_drifters | Reserved | 543 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 544 | Landmark Address 1 | 545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 546 | Next Hop Address 1 | 547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 548 | Distance 1 | N_members 1 | Sequence Number 1 : 549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 550 : . . . : 551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 552 | Drifter Address 1 | 553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 554 | Next Hop Address 1 | 555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 556 | Distance 1 | ... : 557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 558 : . . . | 559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 561 6.2.1. Description of the fields 563 Landmark Flag 565 The landmark flag of the sending node. 567 N_landmarks 569 The number of entries of the landmark distance vector. 571 N_drifters 573 The number of entries of the drifter list. 575 Reserved 577 The bits are set to '0' and are ignored on reception. 579 Landmark Address 1, Next Hop Address 1, Distance 1, N_members 1 580 and Sequence Number 1 582 The first entry in the landmark distance vector. 583 Landmark Address 1, N_members 1 and Sequence Number 1 are the 584 status tuple of the destination landmark. 585 Next Hop Address 1 and Distance 1 is the next hop and distance 586 to the landmark. 588 These fields are repeated N_landmarks times for each entry in 589 landmark distance vector. 591 Drifter Address 1, Next Hop Address 1 and Distance 1 593 The first entry in the drifter list. 594 Next Hop Address 1 and Distance 1 are the next hop and distance 595 to the Drifter Address 1. 597 These fields are repeated N_drifters times for each entry in 598 the drifter list. 600 The length of the message is limited to the maximum IP packet size. 601 In that case, multiple packets may be required to broadcast all the 602 entries. 604 6.3. Processing Landmark Updates 606 Landmark update information is a part of the LANMAR periodic 607 routing update message. The update information includes sender's 608 LMDV. Landmark update message is used for landmark election and 609 building paths to landmarks. 611 6.3.1. Originating a Landmark in a Subnet 613 Every time a node detects a neighbor change, it recalculates the 614 number of group members in its scope. The new number of group 615 members is recorded in its election weight field. If this 616 number is greater than a threshold T, the node qualifies as a 617 landmark only when it is the only landmark for the group so far, 618 or it wins the election when competing with the existing landmark. 619 When it becomes a landmark, it increases its sequence number by 2. 620 The old landmark entry is replaced with the new winner. The 621 landmark entry will be broadcast to neighbors with the next update 622 packet. Every time before a landmark sends updates, it increases 623 its sequence number and copies it to LMDV. 625 6.3.2. Receiving Landmark Updates 627 When a node receives a landmark update message, it compares its 628 LMDV entries with the incoming LMDV updates for each subnet. 629 A landmark update corresponding to a new subnet will be copied. 630 An update having the same landmark as already given (in node's LMDV) 631 will be accepted only if it contains a larger sequence number. 632 If an update contains a different landmark for the same subnet as 633 recorded in LMDV, only one landmark will be elected through a 634 winner competition algorithm. LMDV will be updated according to 635 the outcomes of the competition. 637 6.3.3. Winner Competition 639 When more than one node declares itself as a landmark in the same 640 group, a simple solution is to let the node with the largest 641 number of group members win the election and in case of tie, 642 lowest ID breaks the tie. The other competing nodes defer. 643 However, this method is likely to cause the oscillation of 644 landmark roles between nodes. 646 To use hysteresis in replacing an existing landmark, let us assume 647 the competing node's number of members is M, the existing 648 landmark's number of members is N and a factor value S. When M is 649 greater than N*S, then the competing node replaces the existing 650 landmark. Or, when N reduces to a value smaller than a threshold T, 651 then it gives up the landmark role. A tie occurs when M falls 652 within an interval [N*1/S, N*S], then the node with larger member 653 number wins the election. If a tie occurs again with equal member 654 number, i.e., M equals to N, it is broken using lowest ID. A tie 655 can always be broken using lowest ID as the address is used as ID 656 and it is unique. 658 6.4. Processing Drifter Updates 660 Drifter update information is a part of the LANMAR periodical 661 routing update message. The update information is the drifter list 662 (DFDV) of the sender. The computation of the DFDV at each node 663 includes checking the node itself to see whether it is a drifter 664 and recording paths to other drifters. 666 6.4.1. Originating a Drifter Entry 668 By checking the distance to the landmark of its group, each node 669 easily knows whether it has become a drifter. If the distance is 670 larger than the scope, the node will put itself into its drifter 671 list. This drifter information will be sent back to the landmark 672 hop by hop along the shortest path to it which can be learned from 673 the LMDV. For each drifter, only the node on its shortest path 674 to the landmark needs to receive its information, so before the 675 entry is broadcast, the next hop to landmark is attached with 676 its entry. The DFDV will be propagated with the next update packet. 678 6.4.2. Receiving Drifter Updates 680 Upon receiving an update packet, the DFDV part is retrieved and 681 processed. If an entry of incoming DFDV indicates that the current 682 node is its next hop to the landmark, i.e., the current node is on 683 the drifter's shortest path to the landmark, the current node will 684 insert or update its drifter list. The receiving time is stamped 685 in the DFDV. The node sending the update packet is recorded as the 686 next hop to the drifter. The reverse path to the drifter is thus 687 built up. The procedure ends when the landmark receives the 688 drifter entry. The updated DFDV will be propagated with the next 689 update packet. 691 6.4.3. Removing a Drifter Entry 693 Each entry in DFDV is time stamped of its last receiving time. 694 Every time before the DFDV is sent or routing by DFDV is needed, 695 the table is checked for staled entries. If such an entry is found, 696 it is removed. 698 6.5. Processing Neighbor List 700 When a node receives either a landmark update or a host protocol 701 routing update, the neighbor list is inserted if the update comes 702 from a new neighbor, or the corresponding neighbor entry is 703 updated. Current time is recorded with the entry. The 704 neighbor list is also search at this time for possible lost 705 neighbors according to the time stamps. If such a neighbor is 706 found, it is removed from the list. 708 7. Data Packet Forwarding 710 Data packets are relayed hop by hop. The host protocol routing 711 table, drifter list and landmark distance vector are looked up 712 sequentially for the destination entry. If the destination is 713 within a node's scope, the entry can be found directly in the 714 routing table and the packet is forwarded to the next hop node. 715 Otherwise, the drifter list DFDV is searched for the destination. 716 If the entry is found, the packet is forwarded using the next hop 717 address from DFDV. If not, the logical subnet field of the 718 destination is retrieved and the LMDV entry of the landmark 719 corresponding to the destination's logical subnet is searched. 720 The data packet is then routed towards the landmark using the next 721 hop address from LMDV. The packet, however, is not necessary to 722 pass through the landmark. Rather, once the packet gets within the 723 scope of the destination on its way towards the landmark, it is 724 routed to the destination directly. 726 8. Discussion about Storage and Processing Overhead for Drifters 728 The routing storage and processing overhead introduced by the 729 distance vector extension to handle drifters is typically small 730 if the fraction of drifting nodes is small. Consider a network 731 with N nodes and L landmarks, and assume that a fraction F of the 732 members of each logical subnet have drifted. In the worst case, 733 the path length from landmark to drifter is the square root of N 734 (assuming a grid topology). Thus, sqrt(N) is the bound on the 735 number of extra routing entries required at the nodes along the 736 path to the drifter. The total number of extra routing entries is 737 sqrt(N)*L*(F*N/L) where N/L is the average logical group size. 738 Thus, the extra storage per node is F*sqrt(N). Now, let us assume 739 that the number of nodes in the scope = # of landmarks = logical 740 group size = sqrt(N). Then, the basic routing table overhead per 741 node (excluding drifters) is 3*sqrt(N). Thus, the extra overhead 742 caused by drifters is F/3. If 20% of the nodes in a group are 743 outside of the landmark scope, i.e., have drifted, the extra 744 routing O/H required to keep track of them is only 7%. 746 Acknowledgments 748 This work was supported in part by NSF under contract ANI-9814675, 749 by DARPA under contract DAAB07-97-C-D321, and by ONR under 750 contract N00014-01-C-0016. 752 References 754 [1] G. Pei, M. Gerla and X. Hong, "LANMAR: Landmark Routing for 755 Large Scale Wireless Ad Hoc Networks with Group Mobility", 756 Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000. 758 [2] M. Gerla, X. Hong, G. Pei, "Landmark Routing for Large Ad Hoc 759 Wireless Networks", Proceedings of IEEE GLOBECOM 2000, 760 San Francisco, CA, Nov. 2000. 762 [3] C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination- 763 Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," 764 In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994, 765 pp. 234-244. 767 [4] UCLA Wireless Adaptive Mobility (WAM) Laboratory. 768 http://www.cs.ucla.edu/NRL/wireless 770 [5] S. Bradner. Key words for use in RFCs to Indicate 771 Requirement Levels. RFC 2119, March 1997. 773 [6] P. F. Tsuchiya, "The Landmark Hierarchy: a new hierarchy for 774 routing in very large networks", Computer Communication Review, 775 vol.18, no.4, Aug. 1988, pp. 35-42. 777 [7] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing: 778 A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of 779 ICC 2000, New Orleans, LA, Jun. 2000. 781 [8] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in 782 Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless 783 Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000. 785 Chair's Address 787 The MANET Working Group can be contacted via its current chairs: 789 M. Scott Corson 790 Institute for Systems Research 791 University of Maryland 792 College Park, MD 20742 793 USA 795 Phone: +1 301 405-6630 796 Email: corson@isr.umd.edu 798 Joseph Macker 799 Information Technology Division 800 Naval Research Laboratory 801 Washington, DC 20375 802 USA 803 Phone: +1 202 767-2001 804 Email: macker@itd.nrl.navy.mil 806 Authors' Addresses 808 Questions about this document can also be directed to the authors: 810 Mario Gerla 811 3732F Boelter Hall 812 Computer Science Department 813 University of California 814 Los Angeles, CA 90095-1596 815 USA 817 Phone: +1 310 825-4367 818 Fax: +1 310 825-7578 819 Email: gerla@cs.ucla.edu 821 Xiaoyan Hong 822 3803F Boelter Hall 823 Computer Science Department 824 University of California 825 Los Angeles, CA 90095-1596 826 USA 828 Phone: +1 310 825-4623 829 Fax: +1 310 825-7578 830 Email: hxy@cs.ucla.edu 832 Li Ma 833 3803D Boelter Hall 834 Computer Science Department 835 University of California 836 Los Angeles, CA 90095-1596 837 USA 839 Phone: +1 310 825-1888 840 Fax: +1 310 825-7578 841 Email: mary@cs.ucla.edu 843 Guangyu Pei 844 Rockwell Science Center 845 1049 Camino Dos Rios 846 P.O. Box 1085 847 Thousand Oaks, CA 91358-0085 848 USA 850 Phone: +1 805 373-4639 851 Fax: +1 805 373-4383 852 Email: gpei@rsc.rockwell.com