idnits 2.17.1 draft-ietf-manet-lanmar-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-25) 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 (November 17, 2000) is 8560 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: May 17, 2001 Li Ma 5 University of California, Los Angeles 6 Guangyu Pei 7 Rockwell Science Center 8 November 17, 2000 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 network address of a node is . A landmark is dynamically elected in each group. The 48 route to a landmark is propagated throughout the network using a 49 Distance Vector mechanism. Separately, each node in the network 50 uses a "scoped" routing algorithm (e.g., FSR) to learn about routes 51 within a given (max number of hops) scope. To route a packet to a 52 destination outside its scope, a node will direct the packet to the 53 landmark corresponding to the group ID of such destination. Once 54 the packet is within the scope of the landmark, it will typically 55 be routed directly to the destination. Remote groups of nodes are 56 "summarized" by the corresponding landmarks. The solution to 57 drifters (i.e., nodes outside of the scope of their landmark) is 58 also handled by LANMAR. Landmark dynamic election enables LANMAR 59 to cope with mobile environments. By using a "scoped" routing 60 scheme, we dramatically reduce routing table size and update 61 overhead in large nets. LANMAR is well suited to provide an 62 efficient and scalable routing solution in large, mobile, ad hoc 63 environments in which group behavior applies and high mobility 64 renders traditional routing schemes inefficient. 66 Contents 68 Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . 1 70 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 72 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 74 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4 75 2.1. General Terms . . . . . . . . . . . . . . . . . . . . . 4 76 2.2. Specification Language . . . . . . . . . . . . . . . . . 5 78 3. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 5 79 3.1. Networking Context . . . . . . . . . . . . . . . . . . . 5 80 3.2. Protocol Characteristics and Mechanisms . . . . . . . . 6 82 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8 83 4.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8 84 4.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9 85 4.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10 87 5. Protocol Specifications . . . . . . . . . . . . . . . . . . . 10 88 5.1. Data Structures . . . . . . . . . . . . . . . . . . . 10 89 5.1.1 Landmark Status . . . . . . . . . . . . . . . . . 11 90 5.1.2 Landmark Distance Vector . . . . . . . . . . . . 11 91 5.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11 93 5.2. LANMAR Update Message Format . . . . . . . . . . . . 11 94 5.2.1 Description of the fields . . . . . . . . . . . . 12 95 5.3. Processing Landmark Updates . . . . . . . . . . . . . . 13 96 5.3.1 Originating a Landmark in a Subnet . . . . . . . 13 97 5.3.2 Receiving Landmark Updates . . . . . . . . . . . 14 98 5.3.3 Winner Competition . . . . . . . . . . . . . . . 14 99 5.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14 100 5.4.1 Originating a Drifter Entry . . . . . . . . . . . 14 101 5.4.2 Receiving Drifter Updates . . . . . . . . . . . . 15 103 6. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15 105 7. Discussion about Storage and Processing Overhead for Drifters 15 107 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 16 109 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 111 Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 115 1. Introduction 117 This document describes the Landmark Routing Protocol (LANMAR) [1,2] 118 developed by the Wireless Adaptive Mobility (WAM) Laboratory [4] at 119 University of California, Los Angeles. 121 The concept of landmark routing was first introduced in wired area 122 networks [6]. The original scheme required predefined multi-level 123 hierarchical addressing. The hierarchical address of each node 124 reflects its position within the hierarchy and helps to find a route 125 to it. Each node knows the routes to all the nodes within its 126 hierarchical partition. Moreover, each node knows the routes to 127 various "landmarks" at different hierarchical levels. Packet 128 forwarding is consistent with the landmark hierarchy and the path 129 is gradually refined from the top level hierarchy to lower levels 130 as a packet approaches its destination. 132 LANMAR borrows the concept of landmark and extends it to the 133 wireless ad hoc environment. LANMAR scheme does not require 134 predefined hierarchical address, but it uses the notion of landmarks 135 to keep track of logical subnets in which the members have a 136 commonality of interests and are likely to move as a "group" 137 (e.g., brigade in the battlefield, colleagues in the same 138 organization, a group of students from same class, or a team of 139 co-workers at a convention and a tank battalion in the battlefield). 141 Each such logical group has an elected landmark. For each group, 142 underlining "scoped" routing algorithm will provide a one-level 143 scope. The routing update packets are restricted only within the 144 scope. Accurate routing information for nodes within scope is 145 maintained. The routing information to remote nodes (nodes outside 146 the node's scope) is "summarized" by the corresponding landmarks. 147 Thus, the LANMAR scheme largely reduces the routing table size and 148 the routing update traffic overhead. It greatly improves 149 scalability. 151 In addition, in order to recover from landmark failures, 152 a "landmark" node is elected in each subnet. Landmark election 153 provides a flexible way for the LANMAR protocol to cope with a 154 dynamic and mobile network. The protocol also provides a solution 155 for drifters (Nodes that are outside the fisheye scopes of the 156 landmarks of their logical groups). Extra storage, processing and 157 line overhead will be incurred for landmark election and drifter 158 bookkeeping. However, the design of the algorithms provides 159 solutions without compromising scalability. For example, the 160 routing overhead for handling drifters is typically small if the 161 fraction of drifting nodes is small. More analysis is given in 162 Section 7. 164 The LANMAR runs on top of a proactive routing protocol. It also 165 requires that the underlining routing protocol support the scoped 166 subnetworking. Fisheye State Routing Protocol (FSR) [7,8] is 167 such a protocol that supports LANMAR. In FSR, the link state 168 protocol is used within the scope. However, the fisheye scope 169 technique can also be applied to a distance vector type protocol, 170 such as DSDV [3], in which the hop distance can be used to 171 bind the scope for routing message updating. The main advantage of 172 LANMAR is that the routing table includes only the nodes within the 173 scope and the landmark nodes. This feature greatly improves 174 scalability by reducing routing table size and update traffic O/H. 176 Thus the Landmark Routing Protocol provides an efficient and 177 scalable routing solution for a mobile, ad hoc environment while 178 keeping line and storage overhead (O/H) low. Moreover, the 179 election provides a much needed recovery from landmark failures. 181 2. Terminology 183 2.1. General Terms 185 This section defines terminology used in LANMAR. 187 node 188 A MANET router that implements Landmark Routing Protocol. 190 neighbor 192 Nodes that are within the radio transmission range. 194 scope 196 A zone that is bounded by hop distances. 198 host protocol 200 A proactive protocol underlines the Landmark Routing Protocol. 202 subnet 204 Logical groups of nodes that present similar motion behavior. 206 group 208 This is used interchangeably with subnet. 210 2.2. Specification Language 212 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 213 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 214 document are to be interpreted as described in RFC 2119 [5]. 216 3. Protocol Applicability 218 3.1. Networking Context 220 LANMAR is best suited for large scale mobile ad hoc wireless 221 networks. The landmark scheme on top of "scoped" routing algorithm 222 has large advantages in reducing routing update packet size and 223 keeping progressive accurate routes to remote nodes. It achieves 224 high data packet to routing packet ratio. Moreover, the fact that 225 the route error is weighted by distance obviously reduces the 226 sensitivity to network size. 228 LANMAR is also suited for high mobility ad hoc wireless networks. 229 This is because in a mobility environment, a change on a link far 230 away from the source does not necessarily cause a change in the 231 routing table at the source and that all the information about 232 remote nodes is summarized by landmarks. 234 3.2. Protocol Characteristics and Mechanisms 236 * Does the protocol provide support for unidirectional links?(if so, 237 how?) 239 Yes. Since LANMAR is on top of a host protocol, if the host 240 protocol supports unidirectional links, e.g., the FSR protocol, 241 LANMAR can use the unidirectional link states as well. 243 * Does the protocol require the use of tunneling? (if so, how?) 244 No. 246 * Does the protocol require using some form of source routing? (if 247 so, how?) 249 No. 251 * Does the protocol require the use of periodic messaging? (if so, 252 how?) 254 Yes. The LANMAR periodically broadcasts landmark information 255 to its neighbors. But the updates are piggybacked in the host 256 routing update messages. 258 * Does the protocol require the use of reliable or sequenced packet 259 delivery? (if so, how?) 261 No. As the packets are sent periodically, they need not be 262 sent reliably. 264 * Does the protocol provide support for routing through a multi- 265 technology routing fabric? (if so, how?) 267 Yes. It is assumed that each node's network interface is 268 assigned a unique IP address. 270 * Does the protocol provide support for multiple hosts per router? 271 (if so, how?) 273 Yes. The router that has multiple hosts can use network ID of 274 these hosts as the address to participate LANMAR. 276 * Does the protocol support the IP addressing architecture? (if so, 277 how?) 279 Yes. Each node is assumed to have a unique IP address (or 280 set of unique IP addresses in the case of multiple interfaces). 281 The LANMAR references all nodes/interfaces by their IP address. 283 This version of the LANMAR also supports IP network addressing 284 (network prefixes) for routers that provide access to a 285 network of non-router hosts. 287 * Does the protocol require link or neighbor status sensing (if so, 288 how?) 290 No. 292 * Does the protocol have dependence on a central entity? (if so, 293 how?) 295 No. 297 * Does the protocol function reactively? (if so, how?) 299 No. 301 * Does the protocol function proactively? (if so, how?) 303 Yes. The LANMAR proactively maintains landmark information 304 at each node. 306 * Does the protocol provide loop-free routing? (if so, how?) 308 Yes. As the protocol uses routing paths learned from the host 309 protocol for in-scope destinations, if the host protocol 310 provides loop-free routing, so does LANMAR. For out-scope 311 destinations, only routes to landmarks are used. Because these 312 routes are DSDV, it is loop free. When a packet is 313 approaching the destination, in-scope routes are used again. 315 * Does the protocol provide for sleep period operation?(if so, how?) 317 Yes. However, this requires TDMA MAC layer support. The 318 router can be scheduled to sleep during idle periods. 320 * Does the protocol provide some form of security? (if so, how?) 322 Yes. When a node broadcasts routing update message, only 323 entries of in-scope nodes and landmarks are included. This 324 will prevent other remote nodes from being heard. 326 * Does the protocol provide support for utilizing multi-channel, 327 link-layer technologies? (if so, how?) 329 Yes. In fact, the multi-channel can be used to separate 330 routing messages from user data packets. 332 4. Protocol Overview 334 4.1. Protocol Descriptions 336 As mentioned in Section 1, the landmark concept we adopt here uses 337 the notion of logical subnets in which the members have a 338 commonality of interests and are likely to move as a "group". 339 Each logical subnet has one node serving as a "landmark" of that 340 subnet. The protocol requires that the landmark of each subnet have 341 the knowledge of all the members in its group. The LANMAR protocol 342 also uses a scope at each node. The size of the scope is a 343 parameter measured in hop distance. It is chosen in such a way that 344 if a node is at the center of a subnet, the scope will cover the 345 majority of the subnet members. If the shape of a subnet is likely 346 to be a cycle, the center node's scope will cover all the members of 347 the subnet. If this center node is elected as a landmark, it 348 fulfills the requirement of the protocol. If a landmark does not 349 locate at the center, there will be some members drifting off 350 its scope. The landmark will keep records for these drifters. 352 The LANMAR relies on an underlining proactive protocol with the 353 ability of providing "scoped" routing. The LANMAR itself is a 354 distance vector type protocol. Each node maintains a distance 355 vector for landmarks of all the subnets and a distance vector for 356 drifters in its subnet. The distance vectors for landmarks and 357 drifters are exchanged through piggybacking in the periodical 358 routing update packets (link state or distance vector) of the 359 underling routing protocol. The size of the landmark distance 360 vector equals to the number of logical subnets and thus landmark 361 nodes. Both sizes of the two distance vectors are small. 363 The routing update scheme uses the "scoped" routing algorithm. 364 The main idea is summarized below. Each node broadcasts routing 365 information periodically to its immediate neighbors. In each 366 update packet, the node sends routing table entries within its 367 scope and also piggybacks the landmark and drifter distance 368 vectors. Sequence numbers are used in LANMAR update packets. 369 Each node advances its sequence number before sending an update 370 packet. Through the exchange process, the table entries with 371 larger sequence numbers replace the ones with smaller sequence 372 numbers. 374 Let's take, for example, the FSR as our host protocol. For nodes 375 within the scope, the updating is in a certain frequency. But 376 for nodes beyond the scope, the update frequency is reduced to 377 zero; Only the update frequency of the landmark nodes remains 378 unaltered. As a result, each node maintains accurate routing 379 information for in-scope nodes and keep routing directions to the 380 landmark nodes for out-scope nodes, or say, for remote groups. 381 A packet directed to a remote destination initially aims at the 382 landmark of that remote group; as it gets closer to the landmark, 383 it may eventually switch to the accurate route to the destination 384 provided by in-scope nodes of the destination. 386 4.2. Landmark Election 388 Dynamic election/re-election of landmark node is essential for 389 LANMAR to work in a wireless mobile environment. Basically, each 390 node tracks other nodes of its group in its scope and computes 391 "weight", e.g. the number of the nodes it has found. At the 392 beginning of the LANMAR, no landmark exists. Protocol LANMAR 393 only uses the host protocol functionality. As host routing 394 computation progresses, one of the nodes will learn (from 395 the host protocol's routing table) that more than a certain number 396 of group members (say, T) are in its scope. It then proclaims 397 itself as a landmark for this group and adds itself to the landmark 398 distance vector. The node broadcasts the landmark information to 399 the neighbors jointly with the host update packets. 401 When more than one node declares itself as a landmark in the same 402 group, as the landmark information floods out, each node will 403 perform a winner competition procedure. Only one landmark for each 404 group will survive and it will be elected. To avoid flapping 405 between landmarks (very possible in a mobile situation), we use 406 hysteresis in the replacement of an existing landmark. I.e., the 407 old Landmark is replaced by the new one only if its weight is, say 408 less than 1/2 of the weight of the current election winner. Once 409 ousted, the old leader needs the full weight superiority to be 410 reinstated. 412 This procedure is carried out periodically in the background (low 413 overhead, anyway). At steady state, a landmark propagates its 414 presence to all other nodes like a sink in DSDV. It is extremely 415 simple and it converges (by definition). In a mobile environment, 416 an elected landmark may eventually lose its role. The role shifting 417 is a frequent event. In a transient period, there exist several 418 landmarks in a single group. The transient period may be actually 419 the norm at high mobility. This transient behavior can be 420 drastically reduced by using hysteresis. 422 When a landmark dies, its neighbors will detect the silence after 423 a given timeout. The neighbors of the same group will then take 424 the responsibilities as landmarks and broadcast new landmark 425 information. A new round of landmark election then floods over 426 the entire network. 428 4.3. Drifters 430 Typically, all members in a logical subnet are within the scope of 431 the landmark, thus the landmark has a route to all members. It may 432 happen, however, that some of the members "drift off" the scope, 433 for example, a tank in a battalion may become stranded or lost. 434 To keep track of such "drifters", i.e., to make the route to them 435 known to the landmark, the following modification to the routing 436 table exchange is necessary. Each node, say i, on the shortest 437 path between a landmark L and a drifter l associated with that 438 landmark keeps a distance vector entry to l. Note that if l is 439 within the scope of i, this entry is already included in the 440 routing table of node i. When i transmits its distance vector to 441 neighbor, say j, then j will retain the entry to member l only if 442 d(j,l) is smaller than the scope or d(j,L) is smaller than d(i,L). 443 The latter condition occurs if j is on the shortest path from i 444 (and therefore from l) to L. This way, a path is maintained from 445 the landmark to each of its members, including drifters. 447 The occurrences of drifters are dynamic in a mobile network. In 448 order to timely remove the staled drifter information, the time 449 when a node detects itself a drifter is propagated with the 450 distance vector. 452 5. Protocol Specifications 454 This section discusses the operation of LANMAR routing protocol. 455 The sending and receiving of landmark updates are in the proactive 456 nature. The routing packets are processed separately from 457 ordinary data packets. 459 5.1. Data Structures 461 Each node has a unique "logical" identifier defined by a subnet 462 field and a host field. The host field is unique in the subnet and 463 might in fact coincide with the physical address. The "logical" 464 identifier can also be an IP address when the subnet address can 465 logically group the nodes. Moreover, each node keeps a landmark 466 status as part of identifier. As LANMAR runs on top of a host 467 routing protocol, it shares the underlining data structures. 468 Particularly, LANMAR requires the underlining data structures to 469 associate a landmark status with each node's identifier. In 470 addition, LANMAR keeps a drifter list and a landmark distance 471 vector. 473 5.1.1. Landmark Status 475 Each node has not only a "logical" identifier, which basically is 476 its address, but also a landmark status. The status includes 477 a flag which indicates whether the node is a landmark or not and a 478 weight (the number of group members the node detects within its 479 scope). Anywhere in the tables of the host protocol, when a 480 node's address is kept, a landmark status is recorded. The status 481 is piggybacked in the periodical routing update packets of the 482 host protocols together with the node address. There are two 483 fields for a status: 484 - Landmark flag 485 - Number of group members in its scope 487 5.1.2. Landmark Distance Vector 489 Landmark distance vector (LMDV) gives the next hop information to 490 all landmarks in the network. Every subnet has an entry in LMDV. 491 Initially, the entries in the underlining routing table, which 492 point to landmarks, are copied to LMDV. The LMDV entries are 493 updated when landmark update message is received or underlining 494 topology table is changed. LMDV functions as a part of the 495 routing table. It has the following fields: 496 - Landmark status 497 - Next hop address 498 - Distance 500 5.1.3. Drifter List 502 The drifter list of LANMAR provides the next hop information to 503 forward the packets to the drifters known to the current node. 504 The entries are updated explicitly using landmark update message. 505 It works as a part of routing table. The drifter list (DFDV) has 506 following fields: 507 - Destination drifter address 508 - Next hop address 509 - Last declaration time 511 5.2. LANMAR Update Message Format 513 The messages necessary for LANMAR protocol are piggybacked in the 514 host periodic update packets. The format given below is not 515 exactly how the bits appear in the host update packets. Where to 516 put these fields in the host update packets is an implementation 517 issue. The necessary fields include current node's landmark 518 status (assuming that the node's address can be obtained from IP 519 header), its landmark distance vector LMDV and the drifter list 520 DFDV. The next two subsections will describe how these 521 information is processed. 523 0 1 2 3 524 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 525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 526 | Landmark Flag | N_members | Reserved | N_landmarks | 527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 528 | Landmark Address 1 | 529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 530 | Next Hop Address 1 | 531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 532 | N_members 1 | Distance 1 | ... : 533 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 534 : . . . : 535 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 536 : . . . | N_drifters | 537 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 538 | Drifter Address 1 | 539 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 540 | Next Hop Address 1 | 541 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 542 | Distance 1 | Timestamp 1 | ... : 543 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 544 : . . . | 545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 547 5.2.1. Description of the fields 549 Landmark Flag and N_members 551 These two fields are the landmark status. N_members is the 552 number of group members in the node's scope. 554 Reserved 556 The bits are set to '0' and are ignored on reception. 558 N_landmarks 560 The number of entries of the landmark distance vector. 562 Landmark Address 1, Next Hop Address 1, N_members 1 and Distance 1 564 The first entry in the landmark distance vector. 565 Landmark Address 1 and N_members 1 are the destination landmark 566 status. 567 Next Hop Address 1 and Distance 1 is the next hop and distance 568 to the landmark. 570 These fields are repeated N_landmarks times for each entry in 571 landmark distance vector. 573 N_drifters 575 The number of entries of the drifter list. 577 Drifter Address 1, Next Hop Address 1, Distance 1, Timestamp 1 579 The first entry in the drifter list. 580 Next Hop Address 1 and Distance 1 are the next hop and distance 581 to the Drifter Address 1. 582 Timestamp 1 is the time when the node becomes a drifter. 584 These fields are repeated N_drifters times for each entry in 585 the drifter list. 587 The length of the message (including the host update fields) is 588 limited to the maximum IP packet size. In that case, multiple 589 packets may be required to broadcast all the topology entries for 590 host protocol. The landmark distance vector and drifter list will 591 be piggybacked in each packet with the same sequence number. 593 5.3. Processing Landmark Updates 595 Landmark update information is a part of the LANMAR periodic 596 routing update message, which is carried in host updating packets. 597 The update information includes sender's landmark status and LMDV. 598 Landmark update message is used for landmark election and helps 599 nodes build their LMDV. 601 5.3.1. Originating a Landmark in a Subnet 603 Every time a node detects a topology change, it recalculates the 604 number of group members in its scope. The new number of group 605 members is recorded in its landmark status and replaces the old 606 values in all the tables containing the landmark status. If this 607 number is greater than a threshold T, the node qualifies as a 608 landmark only when there is no landmark for the group according to 609 its LMDV, or it wins the election when competing with the existing 610 landmark. The landmark distance vector is updated accordingly. 611 If the host protocol has new shortest paths to landmarks, the new 612 paths are copied from the host routing table to the LMDV. 613 The landmark status and the LMDV will be broadcast to neighbors 614 with the next host update packet. 616 5.3.2. Receiving Landmark Updates 618 When a node receives a landmark update message, it compares its 619 LMDV entries with the incoming LMDV entries for each subnet. New 620 landmark enrties will be copied. Competing landmarks will 621 be solved through a winner competition algorithm. The winner will 622 be elected as the landmark for the subnet. The node's landmark 623 status and LMDV will be updated according to the outcomes of the 624 competition. The distance information can be obtained either from 625 the incoming LMDV entry or from host routing table. The updated 626 LMDV and the node's landmark status will be propagated jointly with 627 the host routing update packets. 629 5.3.3. Winner Competition 631 When more than one node declares itself as a landmark in the same 632 group, a simple solution is to let the node with the largest 633 number of group members win the election and in case of tie, 634 lowest ID breaks the tie. The other competing nodes defer. 635 However, this method is likely to cause the oscillation of 636 landmark roles between nodes. 638 To use hysteresis in replacing an existing landmark, let us assume 639 the competing node's number of members is M, the existing 640 landmark's number of members is N and a factor value S. When M is 641 greater than N*S, then the competing node replaces the existing 642 landmark. Or, when N reduces to a value smaller than a threshold T, 643 then it gives up the landmark role. A tie occurs when M falls 644 within an interval [N*1/S, N*S], then the node with larger member 645 number wins the election. If a tie occurs again with equal member 646 number, i.e., M equals to N, it is broken using lowest ID. A tie 647 can always be broken using lowest ID as the address is used as ID 648 and it is unique. 650 5.4. Processing Drifter Updates 652 Drifter update information is a part of the LANMAR periodical 653 routing update message, which is carried in host updating packets. 654 The update information is the drifter list (DFDV) of the sender. 655 The computation of the DFDV at each node includes checking the node 656 itself to see whether it is a drifter and recording paths to other 657 drifters. 659 5.4.1. Originating a Drifter Entry 661 By checking the distance to the landmark of its group, each node 662 easily knows whether it has become a drifter. If the distance is 663 larger than the scope, the node will put itself into its drifter 664 list and record the time instance. This drifter information 665 will be sent back to the landmark hop by hop along the shortest 666 path to it which can be learned from the LMDV. For each drifter, 667 only the node on its shortest path to the landmark needs to receive 668 its information, so before the entry is broadcast, the next hop to 669 landmark is attached with its entry. The DFDV will be propagated 670 with the next host routing update packet. 672 5.4.2. Receiving Drifter Updates 674 Upon receiving an update packet, the DFDV part is retrieved and 675 processed. If an entry of incoming DFDV indicates that the current 676 node is its next hop to the landmark, i.e., the current node is on 677 the drifter's shortest path to the landmark, the current node will 678 insert or update its drifter list. The node sending the update 679 packet is recorded as the next hop to the drifter. The reverse path 680 to the drifter is thus built up. The procedure ends when the 681 landmark receives the drifter entry. The updated DFDV will be 682 propagated with the next host routing update packet. 684 6. Data Packet Forwarding 686 Data packets are relayed hop by hop. The host protocol routing 687 table, drifter list and landmark distance vector are looked up 688 sequentially for the destination entry. If the destination is 689 within a node's scope, the entry can be found directly in the 690 routing table and the packet is forwarded to the next hop node. 691 Otherwise, the drifter list DFDV is searched for the destination. 692 If the entry is found, the packet is forwarded using the next hop 693 address from DFDV. If not, the logical subnet field of the 694 destination is retrieved and the LMDV entry of the landmark 695 corresponding to the destination's logical subnet is searched. 696 The data packet is then routed towards the landmark using the next 697 hop address from LMDV. The packet, however, is not necessary to 698 pass through the landmark. Rather, once the packet gets within the 699 scope of the destination on its way towards the landmark, it is 700 routed to the destination directly. 702 7. Discussion about Storage and Processing Overhead for Drifters 704 The routing storage and processing overhead introduced by the 705 distance vector extension to handle drifters is typically small 706 if the fraction of drifting nodes is small. Consider a network 707 with N nodes and L landmarks, and assume that a fraction F of the 708 members of each logical subnet have drifted. In the worst case, 709 the path length from landmark to drifter is the square root of N 710 (assuming a grid topology). Thus, sqrt(N) is the bound on the 711 number of extra routing entries required at the nodes along the 712 path to the drifter. The total number of extra routing entries is 713 sqrt(N)*L*(F*N/L) where N/L is the average logical group size. 714 Thus, the extra storage per node is F*sqrt(N). Now, let us assume 715 that the number of nodes in the scope = # of landmarks = logical 716 group size = sqrt(N). Then, the basic routing table overhead per 717 node (excluding drifters) is 3*sqrt(N). Thus, the extra overhead 718 caused by drifters is F/3. If 20% of the nodes in a group are 719 outside of the landmark scope, i.e., have drifted, the extra 720 routing O/H required to keep track of them is only 7%. 722 Acknowledgments 724 This work was supported in part by NSF under contract ANI-9814675 725 and in part by DARPA under contract DAAB07-97-C-D321. 727 References 729 [1] G. Pei, M. Gerla and X. Hong, "LANMAR: Landmark Routing for 730 Large Scale Wireless Ad Hoc Networks with Group Mobility", 731 Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000. 733 [2] M. Gerla, X. Hong, G. Pei, "Landmark Routing for Large Ad Hoc 734 Wireless Networks", Proceedings of IEEE GLOBECOM 2000, 735 San Francisco, CA, Nov. 2000. 737 [3] C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination- 738 Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," 739 In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994, 740 pp. 234-244. 742 [4] UCLA Wireless Adaptive Mobility (WAM) Laboratory. 743 http://www.cs.ucla.edu/NRL/wireless 745 [5] S. Bradner. Key words for use in RFCs to Indicate 746 Requirement Levels. RFC 2119, March 1997. 748 [6] P. F. Tsuchiya, "The Landmark Hierarchy: a new hierarchy for 749 routing in very large networks", Computer Communication Review, 750 vol.18, no.4, Aug. 1988, pp. 35-42. 752 [7] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing: 753 A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of 754 ICC 2000, New Orleans, LA, Jun. 2000. 756 [8] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in 757 Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless 758 Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000. 760 Chair's Address 762 The MANET Working Group can be contacted via its current chairs: 764 M. Scott Corson 765 Institute for Systems Research 766 University of Maryland 767 College Park, MD 20742 768 USA 770 Phone: +1 301 405-6630 771 Email: corson@isr.umd.edu 773 Joseph Macker 774 Information Technology Division 775 Naval Research Laboratory 776 Washington, DC 20375 777 USA 779 Phone: +1 202 767-2001 780 Email: macker@itd.nrl.navy.mil 782 Authors' Addresses 784 Questions about this document can also be directed to the authors: 786 Mario Gerla 787 3732F Boelter Hall 788 Computer Science Department 789 University of California 790 Los Angeles, CA 90095-1596 791 USA 793 Phone: +1 310 825-4367 794 Fax: +1 310 825-7578 795 Email: gerla@cs.ucla.edu 797 Xiaoyan Hong 798 3820 Boelter Hall 799 Computer Science Department 800 University of California 801 Los Angeles, CA 90095-1596 802 USA 804 Phone: +1 310 825-4623 805 Fax: +1 310 825-7578 806 Email: hxy@cs.ucla.edu 808 Li Ma 809 3803 Boelter Hall 810 Computer Science Department 811 University of California 812 Los Angeles, CA 90095-1596 813 USA 815 Phone: +1 310 825-1888 816 Fax: +1 310 825-7578 817 Email: mary@cs.ucla.edu 819 Guangyu Pei 820 Rockwell Science Center 821 1049 Camino Dos Rios 822 P.O. Box 1085 823 Thousand Oaks, CA 91358-0085 824 USA 826 Phone: +1 805 373-4639 827 Fax: +1 805 373-4383 828 Email: gpei@rsc.rockwell.com