idnits 2.17.1 draft-ietf-manet-lanmar-01.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-19) 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: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. == 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 8373 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: 5 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 NOT offered in accordance 17 with Section 10 of RFC2026, and the author does not provide the IETF 18 with any rights other than to publish as an Internet-Draft. This 19 document is a submission to the Mobile Ad-hoc Networks (manet) 20 Working Group of the Internet Engineering Task Force (IETF). 21 Comments should be submitted to the Working Group mailing list at 22 "manet@itd.nrl.navy.mil". Distribution of this memo is unlimited. 24 This document is an Internet-Draft. Internet-Drafts are working 25 documents of the Internet Engineering Task Force (IETF), its areas, 26 and its working groups. Note that other groups may also distribute 27 working documents as Internet-Drafts. 29 Internet-Drafts are draft documents valid for a maximum of six 30 months and may be updated, replaced, or obsoleted by other documents 31 at any time. It is inappropriate to use Internet-Drafts as 32 reference material or to cite them other than as "work in progress." 34 The list of current Internet-Drafts can be accessed at 35 http://www.ietf.org/ietf/1id-abstracts.txt 37 The list of Internet-Draft Shadow Directories can be accessed at 38 http://www.ietf.org/shadow.html. 40 Abstract 42 The Landmark Routing Protocol (LANMAR) utilizes the concept of 43 "landmark" for scalable routing in large, mobile ad hoc networks. 44 It relies on the notion of group mobility: i.e., a logical group 45 (for example a team of coworkers at a convention) moves in a 46 coordinated fashion. The existence of such logical group can be 47 efficiently reflected in the addressing scheme. It assumes that 48 an IP like address is used consisting of a group ID (or subnet ID) 49 and a host ID, i.e. . A landmark is dynamically 50 elected in each group. The route to a landmark is propagated 51 throughout the network using a Distance Vector mechanism. 52 Separately, each node in the network uses a "scoped" routing 53 algorithm (e.g., FSR) to learn about routes within a given (max 54 number of hops) scope. To route a packet to a destination outside 55 its scope, a node will direct the packet to the landmark 56 corresponding to the group ID of such destination. Once the packet 57 is within the scope of the landmark, it will typically be routed 58 directly to the destination. Remote groups of nodes are 59 "summarized" by the corresponding landmarks. The solution to 60 drifters (i.e., nodes outside of the scope of their landmark) is 61 also handled by LANMAR. Landmark dynamic election enables LANMAR 62 to cope with mobile environments. Thus, by using the truncated 63 local routing table and the "summarized" landmark distance vector, 64 LANMAR dramatically reduces routing table size and update overhead 65 in large nets. LANMAR is well suited to provide an efficient and 66 scalable routing solution in large, mobile, ad hoc environments in 67 which group behavior applies and high mobility renders traditional 68 routing schemes inefficient. 70 Contents 72 Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . 1 74 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 76 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 78 2. Changes ....................................................... 5 80 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 81 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5 82 3.2. Specification Language . . . . . . . . . . . . . . . . . 5 84 4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 6 85 4.1. Networking Context . . . . . . . . . . . . . . . . . . . 6 86 4.2. Protocol Characteristics and Mechanisms . . . . . . . . 6 88 5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8 89 5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8 90 5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9 91 5.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10 93 6. Protocol Specifications . . . . . . . . . . . . . . . . . . . 10 94 6.1. Data Structures . . . . . . . . . . . . . . . . . . . 11 95 6.1.1 Landmark Status tuple . . . . . . . . . . . . . . 11 96 6.1.2 Landmark Distance Vector . . . . . . . . . . . . 11 97 6.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11 98 6.1.4 Neighbor List . . . . . . . . . . . . . . . . . . 12 99 6.2. LANMAR Update Message Format . . . . . . . . . . . . 12 100 6.2.1 Description of the fields . . . . . . . . . . . . 12 101 6.3. Processing Landmark Updates . . . . . . . . . . . . . . 13 102 6.3.1 Originating a Landmark in a Subnet . . . . . . . 13 103 6.3.2 Receiving Landmark Updates . . . . . . . . . . . 14 104 6.3.3 Winner Competition . . . . . . . . . . . . . . . 14 105 6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14 106 6.4.1 Originating a Drifter Entry . . . . . . . . . . . 15 107 6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 15 108 6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 15 109 6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 15 111 7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15 113 8. Discussion about Storage and Processing Overhead for Drifters 16 115 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 16 117 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 119 Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17 121 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 123 1. Introduction 125 This document describes the Landmark Routing Protocol (LANMAR) [1,2] 126 developed by the Wireless Adaptive Mobility (WAM) Laboratory [4] at 127 Computer Science Department, University of California, Los Angeles. 129 The concept of landmark routing was first introduced in wired area 130 networks [6]. The original scheme required predefined multi-level 131 hierarchical addressing. The hierarchical address of each node 132 reflects its position within the hierarchy and helps to find a route 133 to it. Each node knows the routes to all the nodes within its 134 hierarchical partition. Moreover, each node knows the routes to 135 various "landmarks" at different hierarchical levels. Packet 136 forwarding is consistent with the landmark hierarchy and the path 137 is gradually refined from the top level hierarchy to lower levels 138 as a packet approaches its destination. 140 LANMAR borrows the concept of landmark and extends it to the 141 wireless ad hoc environment. LANMAR scheme does not require 142 predefined hierarchical address, but it uses the notion of landmarks 143 to keep track of logical subnets in which the members have a 144 commonality of interests and are likely to move as a "group" 145 (e.g., brigade in the battlefield, a group of students from same 146 class and a team of co-workers at a convention). Each such 147 logical group has an elected landmark. For each group, 148 underlying "scoped" routing algorithm will provide a one-level 149 scope. The routing update packets are restricted only within the 150 scope. Accurate routing information for nodes within scope is 151 maintained. The routing information to remote nodes (nodes outside 152 the node's scope) is "summarized" by the corresponding landmarks. 153 Thus, the LANMAR scheme largely reduces the routing table size and 154 the routing update traffic overhead. It greatly improves 155 scalability. 157 In addition, in order to recover from landmark failures, 158 a "landmark" node is elected in each subnet. Landmark election 159 provides a flexible way for the LANMAR protocol to cope with a 160 dynamic and mobile network. The protocol also provides a solution 161 for drifters (Nodes that are outside the fisheye scopes of the 162 landmarks of their logical groups). Extra storage, processing and 163 line overhead will be incurred for landmark election and drifter 164 bookkeeping. However, the design of the algorithms provides 165 solutions without compromising scalability. For example, the 166 routing overhead for handling drifters is typically small if the 167 fraction of drifting nodes is small. More analysis is given in 168 Section 8. 170 The LANMAR runs on top of a proactive routing protocol. It 171 requires that the underlying routing protocol support the scoped 172 subnetworking. Fisheye State Routing Protocol (FSR) [7,8] is 173 such a protocol that supports LANMAR. In FSR, the link state 174 protocol is used within the scope. The fisheye scope 175 technique can also be applied to a distance vector type protocol, 176 such as DSDV [3], in which the hop distance can be used to 177 bind the scope for routing message updating. The main advantage of 178 LANMAR is that the routing table includes only the nodes within the 179 scope and the landmark nodes. This feature greatly improves 180 scalability by reducing routing table size and update traffic O/H. 182 Thus the Landmark Routing Protocol provides an efficient and 183 scalable routing solution for a mobile, ad hoc environment while 184 keeping line and storage overhead (O/H) low. Moreover, the 185 election provides a much needed recovery from landmark failures. 187 2. Changes 189 Major changes from version 00 to version 01: 191 - A destination sequence number for each landmark is used to 192 ensure loop-free updates for a particular landmark. 194 - Landmark updates are propagated in separate messages, instead of 195 being piggybacked on local routing updates. This modification 196 decouples landmark routing from the underlying proactive routing 197 protocol. 199 3. Terminology 201 3.1. General Terms 203 This section defines terminology used in LANMAR. 205 node 207 A MANET router that implements Landmark Routing Protocol. 209 neighbor 211 Nodes that are within the radio transmission range. 213 scope 215 A zone that is bounded by hop distances. 217 host protocol 219 A proactive protocol underlies the Landmark Routing Protocol. 221 subnet 223 Logical groups of nodes that present similar motion behavior. 225 group 227 This term is used interchangeably with subnet. 229 3.2. Specification Language 231 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 232 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 233 document are to be interpreted as described in RFC 2119 [5]. 235 4. Protocol Applicability 237 4.1. Networking Context 239 LANMAR is best suited for large scale mobile ad hoc wireless 240 networks. The landmark scheme on top of "scoped" routing algorithm 241 has large advantages in reducing routing update packet size and 242 keeping progressive accurate routes to remote nodes. It achieves 243 high data packet delivery ratio. Moreover, the fact that the route 244 error is blurred by distance obviously reduces the sensitivity to 245 network size. 247 LANMAR is also suited for high mobility ad hoc wireless networks. 248 This is because in a mobility environment, a change on a link far 249 away from the source does not necessarily cause a change in the 250 routing table at the source and that all the information about 251 remote nodes is summarized by landmarks. 253 4.2. Protocol Characteristics and Mechanisms 255 * Does the protocol provide support for unidirectional links?(if so, 256 how?) 258 No. 260 * Does the protocol require the use of tunneling? (if so, how?) 261 No. 263 * Does the protocol require using some form of source routing? (if 264 so, how?) 266 No. 268 * Does the protocol require the use of periodic messaging? (if so, 269 how?) 271 Yes. The LANMAR periodically broadcasts landmark information 272 to its neighbors. 274 * Does the protocol require the use of reliable or sequenced packet 275 delivery? (if so, how?) 277 No. As the packets are sent periodically, they need not be 278 sent reliably. 280 * Does the protocol provide support for routing through a multi- 281 technology routing fabric? (if so, how?) 283 Yes. It is assumed that each node's network interface is 284 assigned a unique IP address. 286 * Does the protocol provide support for multiple hosts per router? 287 (if so, how?) 289 Yes. The router that has multiple hosts can use network ID of 290 these hosts as the address to participate LANMAR. 292 * Does the protocol support the IP addressing architecture? (if so, 293 how?) 295 Yes. Each node is assumed to have a unique IP address (or 296 set of unique IP addresses in the case of multiple interfaces). 297 The LANMAR references all nodes/interfaces by their IP address. 298 This version of the LANMAR also supports IP network addressing 299 (network prefixes) for routers that provide access to a 300 network of non-router hosts. 302 * Does the protocol require link or neighbor status sensing (if so, 303 how?) 305 No. 307 * Does the protocol have dependence on a central entity? (if so, 308 how?) 310 No. 312 * Does the protocol function reactively? (if so, how?) 314 No. 316 * Does the protocol function proactively? (if so, how?) 318 Yes. The LANMAR proactively maintains landmark information 319 at each node. 321 * Does the protocol provide loop-free routing? (if so, how?) 323 Yes. For in-scope destinations, the protocol uses routing 324 paths learned from the host protocol. If the host protocol 325 provides loop-free routing, e.g., FSR and DSDV, so does LANMAR. 326 For out-scope destinations, only routes to landmarks are used. 327 Because these routes are DSDV, it is loop free. When a packet 328 approaches the destination, in-scope routes are used again. 330 * Does the protocol provide for sleep period operation?(if so, how?) 332 Yes. However, this requires TDMA MAC layer support. The 333 router can be scheduled to sleep during idle periods. 335 * Does the protocol provide some form of security? (if so, how?) 337 Yes. When a node broadcasts routing update message, only 338 entries of in-scope nodes and landmarks are included. This 339 will prevent other remote nodes from being heard. 341 * Does the protocol provide support for utilizing multi-channel, 342 link-layer technologies? (if so, how?) 344 Yes. In fact, the multi-channel can be used to separate 345 routing messages from user data packets. 347 5. Protocol Overview 349 5.1. Protocol Descriptions 351 As mentioned in Section 1, the landmark concept we adopt here uses 352 the notion of logical subnets in which the members have a 353 commonality of interests and are likely to move as a "group". 354 Each logical subnet has one node serving as a "landmark" of that 355 subnet. The protocol requires that the landmark of each subnet have 356 the knowledge of all the members in its group. The LANMAR protocol 357 also uses a scope at each node. The size of the scope is a 358 parameter measured in hop distance. It is chosen in such a way that 359 if a node is at the center of a subnet, the scope will cover the 360 majority of the subnet members. If the shape of a subnet is likely 361 to be a cycle, the center node's scope will cover all the members of 362 the subnet. If this center node is elected as a landmark, it 363 fulfills the requirement of the protocol. The elected landmark 364 uses a destination sequence number to ensure its routing entry 365 update is loop-free. The landmarks are propagated in a 366 distance vector mechanism. Each node maintains a distance vector 367 for landmarks of all the subnets. The size of the landmark distance 368 vector equals to the number of logical subnets and thus landmark 369 nodes. If a landmark does not locate at the center, there will be 370 some members drifting off its scope. The landmark will keep a 371 distance vector for drifters of its group. The distance vectors 372 for landmarks and drifters are exchanged among neighbors in 373 periodical routing update packets. 375 The LANMAR relies on an underlying proactive protocol with the 376 ability of providing "scoped" routing. In the scoped routing, each 377 node broadcasts routing information periodically to its immediate 378 neighbors. In each update packet, the node sends routing table 379 entries within its scope. The host routing protocol uses sequence 380 numbers for routing entries. Each node advances its sequence 381 number before sending an update packet. Through the exchange 382 process, the table entries with larger sequence numbers replace 383 the ones with smaller sequence numbers. 385 Let's take, for example, the FSR as our host protocol. For nodes 386 within the scope, the updating is in a certain frequency. But 387 for nodes beyond the scope, the update frequency is reduced to 388 zero; Only the update frequency of the landmark nodes remains 389 unaltered. As a result, each node maintains accurate routing 390 information for in-scope nodes and keep routing directions to the 391 landmark nodes for out-scope nodes, or say, for remote groups. 392 A packet directed to a remote destination initially aims at the 393 landmark of that remote group; as it gets closer to the landmark, 394 it may eventually switch to the accurate route to the destination 395 provided by in-scope nodes of the destination. 397 5.2. Landmark Election 399 Dynamic election/re-election of landmark node is essential for 400 LANMAR to work in a wireless mobile environment. Basically, each 401 node tracks other nodes of its group in its scope and computes 402 "weight", e.g. the number of the nodes it has found. At the 403 beginning of the LANMAR, no landmark exists. Protocol LANMAR 404 only uses the host protocol functionality. As host routing 405 computation progresses, one of the nodes will learn (from 406 the host protocol's routing table) that more than a certain number 407 of group members (say, T) are in its scope. It then proclaims 408 itself as a landmark for this group and adds itself to the landmark 409 distance vector. Landmarks broadcast the election weights to 410 the neighbors jointly with the landmark update packets. 412 When more than one node declares itself as a landmark in the same 413 group, as the landmark information floods out, each node will 414 perform a winner competition procedure. Only one landmark for each 415 group will survive and it will be elected. To avoid flapping 416 between landmarks (very possible in a mobile situation), we use 417 hysteresis in the replacement of an existing landmark. I.e., the 418 old Landmark is replaced by the new one only if its weight is, say 419 less than 1/2 of the weight of the current election winner. Once 420 ousted, the old leader needs the full weight superiority to be 421 reinstated. 423 This procedure is carried out periodically in the background (low 424 overhead, anyway). At steady state, a landmark propagates its 425 presence to all other nodes like a sink in DSDV. It is extremely 426 simple and it converges (by definition). In a mobile environment, 427 an elected landmark may eventually lose its role. The role shifting 428 is a frequent event. In a transient period, there exist several 429 landmarks in a single group. The transient period may be actually 430 the norm at high mobility. This transient behavior can be 431 drastically reduced by using hysteresis. 433 When a landmark dies, its neighbors will detect the silence after 434 a given timeout. The neighbors of the same group will then take 435 the responsibilities as landmarks and broadcast new landmark 436 information. A new round of landmark election then floods over 437 the entire network. 439 5.3. Drifters 441 Typically, all members in a logical subnet are within the scope of 442 the landmark, thus the landmark has a route to all members. It may 443 happen, however, that some of the members "drift off" the scope, 444 for example, a tank in a battalion may become stranded or lost. 445 To keep track of such "drifters", i.e., to make the route to them 446 known to the landmark, the following modification to the routing 447 table exchange is necessary. Each node, say i, on the shortest 448 path between a landmark L and a drifter l associated with that 449 landmark keeps a distance vector entry to l. Note that if l is 450 within the scope of i, this entry is already included in the 451 routing table of node i. When i transmits its distance vector to 452 neighbor, say j, then j will retain the entry to member l only if 453 d(j,l) is smaller than the scope or d(j,L) is smaller than d(i,L). 454 The latter condition occurs if j is on the shortest path from i 455 (and therefore from l) to L. This way, a path is maintained from 456 the landmark to each of its members, including drifters. The 457 procedure starts from l, at the time when a node finds it becomes 458 a drifter. It informs the landmark hop by hop about its presence. 460 The occurrences of drifters are dynamic in a mobile network. In 461 order to timely remove the staled drifter information, the time 462 when a node hears a drifter is recorded. 464 6. Protocol Specifications 466 This section discusses the operation of LANMAR routing protocol. 467 The sending and receiving of landmark updates are in the proactive 468 nature. The routing packets are processed separately from 469 ordinary data packets. 471 6.1. Data Structures 473 Each node has a unique "logical" identifier defined by a subnet 474 field and a host field. The host field is unique in the subnet and 475 might in fact coincide with the physical address. The "logical" 476 identifier can also be an IP address when the subnet address can 477 logically group the nodes. Moreover, each node keeps a landmark 478 status tuple. As LANMAR runs on top of a host routing protocol, 479 it shares the underlying routing table structures. LANMAR 480 maintains a neighbor list and shares it with the host protocol. 481 In addition, LANMAR keeps a drifter list and a landmark distance 482 vector. 484 6.1.1. Landmark Status Tuple 486 Each node has not only a "logical" identifier, which basically is 487 its address, but also a landmark status tuple. The tuple includes 488 a flag which indicates whether the node is a landmark or not, a 489 election weight (the number of group members the node detects within 490 its scope) and a sequence number. When a node is elected, the 491 status tuple will be copied to its landmark distance vector. The 492 sequence number is advanced. There are three fields for a tuple: 493 - Landmark flag 494 - Number of group members in its scope 495 - Sequence number 497 6.1.2. Landmark Distance Vector 499 Landmark distance vector (LMDV) gives the next hop information to 500 all landmarks in the network. Every subnet has an entry in LMDV. 501 The latest route information to the landmark of each subnet is 502 learned when a landmark update message is received. LMDV functions 503 as a part of the routing table. It has the following fields: 504 - Landmark status tuple 505 - Next hop address 506 - Distance 508 6.1.3. Drifter List 510 The drifter list (DFDV) of LANMAR provides the next hop information 511 of the drifters known to the current node. The entries are updated 512 with landmark update message. The latest time a drifter is heard 513 is recorded in DFDV. The DFDV works as a part of routing table. 514 It has the following fields: 515 - Destination drifter address 516 - Next hop address 517 - Distance 518 - Last heard time 520 6.1.4. Neighbor List 522 The neighbor list of LANMAR keeps current neighbor information for 523 a node. The latest time a neighbor is heard is recorded. The 524 neighbor list has the following fields: 525 - Neighbor address 526 - Neighbor landmark flag 527 - Last heard time 529 6.2. LANMAR Update Message Format 531 There is only one message type of LANMAR protocol. The messages are 532 periodically exchanged with neighbors. They update the landmark 533 distance vector LMDV and the drifter list DFDV. The processing of 534 the LMDV and DFDV will be describe separately. The following format 535 does not include the node's identifier because it can be obtained 536 from IP Header. 538 0 1 2 3 539 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 540 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 541 | Landmark Flag | N_landmarks | N_drifters | Reserved | 542 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 543 | Landmark Address 1 | 544 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 545 | Next Hop Address 1 | 546 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 547 | Distance 1 | N_members 1 | Sequence Number 1 : 548 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 549 : . . . : 550 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 551 | Drifter Address 1 | 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 553 | Next Hop Address 1 | 554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 555 | Distance 1 | ... : 556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 557 : . . . | 558 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 560 6.2.1. Description of the fields 562 Landmark Flag 564 The landmark flag of the sending node. 566 N_landmarks 568 The number of entries of the landmark distance vector. 570 N_drifters 572 The number of entries of the drifter list. 574 Reserved 576 The bits are set to '0' and are ignored on reception. 578 Landmark Address 1, Next Hop Address 1, Distance 1, N_members 1 579 and Sequence Number 1 581 The first entry in the landmark distance vector. 582 Landmark Address 1, N_members 1 and Sequence Number 1 are the 583 status tuple of the destination landmark. 584 Next Hop Address 1 and Distance 1 is the next hop and distance 585 to the landmark. 587 These fields are repeated N_landmarks times for each entry in 588 landmark distance vector. 590 Drifter Address 1, Next Hop Address 1 and Distance 1 592 The first entry in the drifter list. 593 Next Hop Address 1 and Distance 1 are the next hop and distance 594 to the Drifter Address 1. 596 These fields are repeated N_drifters times for each entry in 597 the drifter list. 599 The length of the message is limited to the maximum IP packet size. 600 In that case, multiple packets may be required to broadcast all the 601 entries. 603 6.3. Processing Landmark Updates 605 Landmark update information is a part of the LANMAR periodic 606 routing update message. The update information includes sender's 607 LMDV. Landmark update message is used for landmark election and 608 building paths to landmarks. 610 6.3.1. Originating a Landmark in a Subnet 612 Every time a node detects a neighbor change, it recalculates the 613 number of group members in its scope. The new number of group 614 members is recorded in its election weight field. If this 615 number is greater than a threshold T, the node qualifies as a 616 landmark only when it is the only landmark for the group so far, 617 or it wins the election when competing with the existing landmark. 618 When it becomes a landmark, it increases its sequence number by 2. 619 The old landmark entry is replaced with the new winner. The 620 landmark entry will be broadcast to neighbors with the next update 621 packet. Every time before a landmark sends updates, it increases 622 its sequence number and copies it to LMDV. 624 6.3.2. Receiving Landmark Updates 626 When a node receives a landmark update message, it compares its 627 LMDV entries with the incoming LMDV updates for each subnet. 628 A landmark update corresponding to a new subnet will be copied. 629 An update having the same landmark as already given (in node's LMDV) 630 will be accepted only if it contains a larger sequence number. 631 If an update contains a different landmark for the same subnet as 632 recorded in LMDV, only one landmark will be elected through a 633 winner competition algorithm. LMDV will be updated according to 634 the outcomes of the competition. 636 6.3.3. Winner Competition 638 When more than one node declares itself as a landmark in the same 639 group, a simple solution is to let the node with the largest 640 number of group members win the election and in case of tie, 641 lowest ID breaks the tie. The other competing nodes defer. 642 However, this method is likely to cause the oscillation of 643 landmark roles between nodes. 645 To use hysteresis in replacing an existing landmark, let us assume 646 the competing node's number of members is M, the existing 647 landmark's number of members is N and a factor value S. When M is 648 greater than N*S, then the competing node replaces the existing 649 landmark. Or, when N reduces to a value smaller than a threshold T, 650 then it gives up the landmark role. A tie occurs when M falls 651 within an interval [N*1/S, N*S], then the node with larger member 652 number wins the election. If a tie occurs again with equal member 653 number, i.e., M equals to N, it is broken using lowest ID. A tie 654 can always be broken using lowest ID as the address is used as ID 655 and it is unique. 657 6.4. Processing Drifter Updates 659 Drifter update information is a part of the LANMAR periodical 660 routing update message. The update information is the drifter list 661 (DFDV) of the sender. The computation of the DFDV at each node 662 includes checking the node itself to see whether it is a drifter 663 and recording paths to other drifters. 665 6.4.1. Originating a Drifter Entry 667 By checking the distance to the landmark of its group, each node 668 easily knows whether it has become a drifter. If the distance is 669 larger than the scope, the node will put itself into its drifter 670 list. This drifter information will be sent back to the landmark 671 hop by hop along the shortest path to it which can be learned from 672 the LMDV. For each drifter, only the node on its shortest path 673 to the landmark needs to receive its information, so before the 674 entry is broadcast, the next hop to landmark is attached with 675 its entry. The DFDV will be propagated with the next update packet. 677 6.4.2. Receiving Drifter Updates 679 Upon receiving an update packet, the DFDV part is retrieved and 680 processed. If an entry of incoming DFDV indicates that the current 681 node is its next hop to the landmark, i.e., the current node is on 682 the drifter's shortest path to the landmark, the current node will 683 insert or update its drifter list. The receiving time is stamped 684 in the DFDV. The node sending the update packet is recorded as the 685 next hop to the drifter. The reverse path to the drifter is thus 686 built up. The procedure ends when the landmark receives the 687 drifter entry. The updated DFDV will be propagated with the next 688 update packet. 690 6.4.3. Removing a Drifter Entry 692 Each entry in DFDV is time stamped of its last receiving time. 693 Every time before the DFDV is sent or routing by DFDV is needed, 694 the table is checked for staled entries. If such an entry is found, 695 it is removed. 697 6.5. Processing Neighbor List 699 When a node receives either a landmark update or a host protocol 700 routing update, the neighbor list is inserted if the update comes 701 from a new neighbor, or the corresponding neighbor entry is 702 updated. Current time is recorded with the entry. The 703 neighbor list is also search at this time for possible lost 704 neighbors according to the time stamps. If such a neighbor is 705 found, it is removed from the list. 707 7. Data Packet Forwarding 709 Data packets are relayed hop by hop. The host protocol routing 710 table, drifter list and landmark distance vector are looked up 711 sequentially for the destination entry. If the destination is 712 within a node's scope, the entry can be found directly in the 713 routing table and the packet is forwarded to the next hop node. 714 Otherwise, the drifter list DFDV is searched for the destination. 715 If the entry is found, the packet is forwarded using the next hop 716 address from DFDV. If not, the logical subnet field of the 717 destination is retrieved and the LMDV entry of the landmark 718 corresponding to the destination's logical subnet is searched. 719 The data packet is then routed towards the landmark using the next 720 hop address from LMDV. The packet, however, is not necessary to 721 pass through the landmark. Rather, once the packet gets within the 722 scope of the destination on its way towards the landmark, it is 723 routed to the destination directly. 725 8. Discussion about Storage and Processing Overhead for Drifters 727 The routing storage and processing overhead introduced by the 728 distance vector extension to handle drifters is typically small 729 if the fraction of drifting nodes is small. Consider a network 730 with N nodes and L landmarks, and assume that a fraction F of the 731 members of each logical subnet have drifted. In the worst case, 732 the path length from landmark to drifter is the square root of N 733 (assuming a grid topology). Thus, sqrt(N) is the bound on the 734 number of extra routing entries required at the nodes along the 735 path to the drifter. The total number of extra routing entries is 736 sqrt(N)*L*(F*N/L) where N/L is the average logical group size. 737 Thus, the extra storage per node is F*sqrt(N). Now, let us assume 738 that the number of nodes in the scope = # of landmarks = logical 739 group size = sqrt(N). Then, the basic routing table overhead per 740 node (excluding drifters) is 3*sqrt(N). Thus, the extra overhead 741 caused by drifters is F/3. If 20% of the nodes in a group are 742 outside of the landmark scope, i.e., have drifted, the extra 743 routing O/H required to keep track of them is only 7%. 745 Acknowledgments 747 This work was supported in part by NSF under contract ANI-9814675, 748 by DARPA under contract DAAB07-97-C-D321, and by ONR under 749 contract N00014-01-C-0016. 751 References 753 [1] G. Pei, M. Gerla and X. Hong, "LANMAR: Landmark Routing for 754 Large Scale Wireless Ad Hoc Networks with Group Mobility", 755 Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000. 757 [2] M. Gerla, X. Hong, G. Pei, "Landmark Routing for Large Ad Hoc 758 Wireless Networks", Proceedings of IEEE GLOBECOM 2000, 759 San Francisco, CA, Nov. 2000. 761 [3] C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination- 762 Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," 763 In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994, 764 pp. 234-244. 766 [4] UCLA Wireless Adaptive Mobility (WAM) Laboratory. 767 http://www.cs.ucla.edu/NRL/wireless 769 [5] S. Bradner. Key words for use in RFCs to Indicate 770 Requirement Levels. RFC 2119, March 1997. 772 [6] P. F. Tsuchiya, "The Landmark Hierarchy: a new hierarchy for 773 routing in very large networks", Computer Communication Review, 774 vol.18, no.4, Aug. 1988, pp. 35-42. 776 [7] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing: 777 A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of 778 ICC 2000, New Orleans, LA, Jun. 2000. 780 [8] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in 781 Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless 782 Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000. 784 Chair's Address 786 The MANET Working Group can be contacted via its current chairs: 788 M. Scott Corson 789 Institute for Systems Research 790 University of Maryland 791 College Park, MD 20742 792 USA 794 Phone: +1 301 405-6630 795 Email: corson@isr.umd.edu 797 Joseph Macker 798 Information Technology Division 799 Naval Research Laboratory 800 Washington, DC 20375 801 USA 802 Phone: +1 202 767-2001 803 Email: macker@itd.nrl.navy.mil 805 Authors' Addresses 807 Questions about this document can also be directed to the authors: 809 Mario Gerla 810 3732F Boelter Hall 811 Computer Science Department 812 University of California 813 Los Angeles, CA 90095-1596 814 USA 816 Phone: +1 310 825-4367 817 Fax: +1 310 825-7578 818 Email: gerla@cs.ucla.edu 820 Xiaoyan Hong 821 3803F Boelter Hall 822 Computer Science Department 823 University of California 824 Los Angeles, CA 90095-1596 825 USA 827 Phone: +1 310 825-4623 828 Fax: +1 310 825-7578 829 Email: hxy@cs.ucla.edu 831 Li Ma 832 3803D Boelter Hall 833 Computer Science Department 834 University of California 835 Los Angeles, CA 90095-1596 836 USA 838 Phone: +1 310 825-1888 839 Fax: +1 310 825-7578 840 Email: mary@cs.ucla.edu 842 Guangyu Pei 843 Rockwell Science Center 844 1049 Camino Dos Rios 845 P.O. Box 1085 846 Thousand Oaks, CA 91358-0085 847 USA 849 Phone: +1 805 373-4639 850 Fax: +1 805 373-4383 851 Email: gpei@rsc.rockwell.com