idnits 2.17.1 draft-ietf-manet-lanmar-03.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: ---------------------------------------------------------------------------- == Line 61 has weird spacing: '...f nodes and b...' == Line 180 has weird spacing: '.... The scope...' -- 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 (December 17, 2001) is 8165 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' == Outdated reference: A later version (-11) exists of draft-ietf-manet-olsr-04 ** Downref: Normative reference to an Experimental draft: draft-ietf-manet-olsr (ref. '9') Summary: 5 errors (**), 0 flaws (~~), 4 warnings (==), 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: June 17, 2002 Li Ma 5 University of California, Los Angeles 6 Guangyu Pei 7 Rockwell Scientific Company 8 December 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 subject to all provisions 17 of Section 10 of RFC2026. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note 21 that other groups may also distribute working documents as 22 Internet-Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at 26 any time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress". 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft is a submission to the IETF Mobile Ad Hoc 36 Networks (MANET) Working Group. Comments on this draft may be sent 37 to the Working Group at manet@itd.nrl.navy.mil, or may be sent 38 directly to the authors. 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 approaches the landmark, it will typically be routed directly to 58 the destination. A solution to nodes outside of the scope of their 59 landmark (i.e., drifters) is also addressed in the draft. Thus, 60 by "summarizing" in the corresponding landmarks the routing 61 information of remote groups of nodes and by using the truncated 62 local routing table, LANMAR dramatically reduces routing table size 63 and routing update overhead in large networks. The dynamic 64 election of landmarks enables LANMAR to cope with mobile 65 environments. 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 80 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 81 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5 82 3.2. Specification Language . . . . . . . . . . . . . . . . . 6 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 . . . . . . . . . . . . . . . . . . . 10 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 . . . . . . . . . . . . . . . . . . 11 99 6.2. LANMAR Update Message Format . . . . . . . . . . . . 11 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 . . . . . . . . . . . 13 104 6.3.3 Winner Competition . . . . . . . . . . . . . . . 14 105 6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14 106 6.4.1 Originating a Drifter Entry . . . . . . . . . . . 14 107 6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 14 108 6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 15 109 6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 15 110 6.6. Processing Lost Neighbor . . . . . . . . . . . . . . . . 15 112 7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15 114 8. Discussion about Storage and Processing Overhead for Drifters 15 116 9. Scoped Routing Operations . . . . . . . . . . . . . . . . . . 16 117 9.1. Fisheye State Routing Protocol . . . . . . . . . . . . . 16 118 9.2. Destination-Sequenced Distance Vector Routing Protocol . 16 119 9.3. Optimized Link State Routing Protocol . . . . . . . . . 16 121 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 17 123 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 125 Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 18 127 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 129 1. Introduction 131 This document describes the Landmark Routing Protocol (LANMAR) [1,2] 132 developed by the Wireless Adaptive Mobility (WAM) Laboratory [4] at 133 Computer Science Department, University of California, Los Angeles. 135 The concept of landmark routing was first introduced in wired area 136 networks [6]. The original scheme required predefined multi-level 137 hierarchical addressing. The hierarchical address of each node 138 reflects its position within the hierarchy and helps to find a route 139 to it. Each node knows the routes to all the nodes within its 140 hierarchical partition. Moreover, each node knows the routes to 141 various "landmarks" at different hierarchical levels. Packet 142 forwarding is consistent with the landmark hierarchy and the path 143 is gradually refined from the top level hierarchy to lower levels 144 as a packet approaches its destination. 146 LANMAR borrows the concept of landmark and extends it to the 147 wireless ad hoc environment. LANMAR scheme does not require 148 predefined hierarchical address, but it uses the notion of landmarks 149 to keep track of logical subnets in which the members have a 150 commonality of interests and are likely to move as a "group" 151 (e.g., brigade in the battlefield, a group of students from same 152 class and a team of co-workers at a convention). Each such 153 logical group has an elected landmark. For each group, 154 the underlying "scoped" routing algorithm will provide accurate 155 routing information for nodes within scope. The routing 156 update packets are restricted only within the scope. The 157 routing information to remote nodes (nodes outside the node's 158 scope) is "summarized" by the corresponding landmarks. Thus, 159 the LANMAR scheme largely reduces the routing table size and 160 the routing update traffic overhead. It greatly improves 161 scalability. 163 In addition, in order to recover from landmark failures, 164 a "landmark" node is elected in each subnet. Landmark election 165 provides a flexible way for the LANMAR protocol to cope with a 166 dynamic and mobile network. The protocol also provides a solution 167 for nodes that are outside the scopes of the landmarks of 168 their logical groups (drifters). Extra storage, processing and 169 line overhead will be incurred for landmark election and drifter 170 bookkeeping. However, the design of the algorithms provides 171 solutions without compromising scalability. For example, the 172 routing overhead for handling drifters is typically small if the 173 fraction of drifting nodes is small. More analysis is given in 174 Section 8. 176 The LANMAR runs on top of a proactive routing protocol. It 177 requires that the underlying routing protocol support the scoped 178 subnetworking. Fisheye State Routing Protocol (FSR) [7,8] is 179 such a protocol that supports LANMAR. In FSR, the link state 180 protocol is used within the scope. The scope technique 181 can also be applied to a distance vector type protocol, 182 such as DSDV [3], in which the hop distance can be used to 183 limit the scope of routing message updating. The main advantage of 184 LANMAR is that the routing table includes only the nodes within the 185 scope and the landmark nodes. This feature greatly improves 186 scalability by reducing routing table size and update traffic O/H. 188 Thus the Landmark Routing Protocol provides an efficient and 189 scalable routing solution for a mobile, ad hoc environment while 190 keeping line and storage overhead (O/H) low. Moreover, the 191 election provides a much needed recovery from landmark failures. 193 2. Changes 195 Major changes from version 02 to version 03: 197 - A drifter sequence number is used in drifter list to indicate 198 each new occurrence of a drifter. 200 - Processing of lost neighbors is added. 202 - A separate section describing the modifications made to various 203 proactive protocols. Operations of these protocols will then 204 only perform within a certain hop distances. 206 - Editorial changes. 208 Major changes from version 01 to version 02: 210 - Update of "Status of This Memo". 212 Major changes from version 00 to version 01: 214 - A destination sequence number for each landmark is used to 215 ensure loop-free updates for a particular landmark. 217 - Landmark updates are propagated in separate messages, instead of 218 being piggybacked on local routing updates. This modification 219 decouples landmark routing from the underlying proactive routing 220 protocol. 222 3. Terminology 224 3.1. General Terms 226 This section defines terminology used in LANMAR. 228 node 230 A MANET router that implements Landmark Routing Protocol. 232 neighbor 234 Nodes that are within the radio transmission range. 236 scope 238 A network area that is centered at each node and bounded 239 by a certain maximum hop distances. 241 host protocol 243 Also known as local routing protocl, i.e., a proactive 244 protocol that works together with the Landmark Routing 245 Protocol, but only operates within the scope of each node. 247 underlying protocol 248 This term is used interchangeably with host protocol. 250 scoped routing protocol 252 A routing protocol that only exchanges routing information 253 up to a certain hop distance (scope). 255 subnet 257 Logical groups of nodes that present similar motion behavior. 259 group 261 This term is used interchangeably with subnet. 263 3.2. Specification Language 265 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 266 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 267 document are to be interpreted as described in RFC 2119 [5]. 269 4. Protocol Applicability 271 4.1. Networking Context 273 LANMAR is best suited for large scale mobile ad hoc wireless 274 networks. The landmark scheme on top of a "scoped" routing 275 algorithm has large advantages in reducing routing update packet 276 size and keeping reasonably accurate routes to remote nodes. 277 It achieves high data packet delivery ratio. Moreover, the fact 278 that the route error is blurred by distance obviously reduces the 279 sensitivity to network size. 281 LANMAR is also suited for high mobility ad hoc wireless networks. 282 This is because in a mobile environment, a change on a link far 283 away from the source does not necessarily cause a change in the 284 routing table at the source since all the information about 285 remote nodes is summarized by landmarks. 287 4.2. Protocol Characteristics and Mechanisms 289 * Does the protocol provide support for unidirectional links?(if so, 290 how?) 292 No. 294 * Does the protocol require the use of tunneling? (if so, how?) 295 No. 297 * Does the protocol require using some form of source routing? (if 298 so, how?) 300 No. 302 * Does the protocol require the use of periodic messaging? (if so, 303 how?) 305 Yes. The LANMAR periodically broadcasts landmark information 306 to its neighbors. 308 * Does the protocol require the use of reliable or sequenced packet 309 delivery? (if so, how?) 311 No. As the packets are sent periodically, they need not be 312 sent reliably. 314 * Does the protocol provide support for routing through a multi- 315 technology routing fabric? (if so, how?) 317 Yes. It is assumed that each node's network interface is 318 assigned a unique IP address. 320 * Does the protocol provide support for multiple hosts per router? 321 (if so, how?) 323 Yes. The router that has multiple hosts can use network ID of 324 these hosts as the address to participate LANMAR. 326 * Does the protocol support the IP addressing architecture? (if so, 327 how?) 329 Yes. Each node is assumed to have a unique IP address (or 330 set of unique IP addresses in the case of multiple interfaces). 331 The LANMAR references all nodes/interfaces by their IP address. 332 This version of the LANMAR also supports IP network addressing 333 (network prefixes) for routers that provide access to a 334 network of non-router hosts. 336 * Does the protocol require link or neighbor status sensing (if so, 337 how?) 339 No. 341 * Does the protocol have dependence on a central entity? (if so, 342 how?) 344 No. 346 * Does the protocol function reactively? (if so, how?) 348 No. 350 * Does the protocol function proactively? (if so, how?) 352 Yes. The LANMAR proactively maintains landmark information 353 at each node. 355 * Does the protocol provide loop-free routing? (if so, how?) 357 Yes. For in-scope destinations, the protocol uses routing 358 paths learned from the host protocol. If the host protocol 359 provides loop-free routing, e.g., FSR and DSDV, so does LANMAR. 360 For out-scope destinations, only routes to landmarks are used. 361 Because these routes are DSDV, it is loop free. When a packet 362 approaches the destination, in-scope routes are used again. 364 * Does the protocol provide for sleep period operation?(if so, how?) 366 Yes. However, this requires TDMA MAC layer support. The 367 router can be scheduled to sleep during idle periods. 369 * Does the protocol provide some form of security? (if so, how?) 371 Yes. When a node broadcasts routing update message, only 372 entries of in-scope nodes and landmarks are included. This 373 will prevent other remote nodes from being heard. 375 * Does the protocol provide support for utilizing multi-channel, 376 link-layer technologies? (if so, how?) 378 Yes. In fact, the multi-channel can be used to separate 379 routing messages from user data packets. 381 5. Protocol Overview 383 5.1. Protocol Descriptions 385 As mentioned in Section 1, the landmark concept we adopt here uses 386 the notion of logical subnets in which the members have a 387 commonality of interests and are likely to move as a "group". 388 Each logical subnet has one node serving as a "landmark" of that 389 subnet. The protocol requires that the landmark of each subnet have 390 the knowledge of all the members in its group. The LANMAR protocol 391 also uses a routing scope at each node. The size of the scope is a 392 parameter measured in hop distance. It is chosen in such a way that 393 if a node is at the center of a subnet, the scope will cover the 394 majority of the subnet members. If the shape of a subnet is likely 395 to be a cycle, the center node's scope will cover all the members of 396 the subnet. If this center node is elected as a landmark, it 397 fulfills the requirement of the protocol. The elected landmark 398 uses a destination sequence number to ensure its routing entry 399 update loop-free. The landmarks are propagated in a 400 distance vector mechanism. Each node maintains a distance vector 401 for landmarks of all the subnets. The size of the landmark distance 402 vector equals to the number of logical subnets and thus landmark 403 nodes. If a landmark does not locate at the center, there will be 404 some members drifting off its scope. The landmark will keep a 405 distance vector for drifters of its group. The distance vectors 406 for landmarks and drifters are exchanged among neighbors in 407 periodical routing update packets. 409 The LANMAR relies on an underlying proactive protocol with the 410 ability of providing "scoped" routing. In the scoped routing, each 411 node broadcasts routing information periodically to its immediate 412 neighbors. In each update packet, the node includes all the 413 routing table entries within the scope centered at it. 415 5.2. Landmark Election 417 Dynamic election/re-election of landmark node is essential for 418 LANMAR to work in a wireless mobile environment. Basically, each 419 node tracks other nodes of its group in its scope and computes 420 "weight", e.g. the number of the nodes it has found. At the 421 beginning of the LANMAR, no landmark exists. Protocol LANMAR 422 only uses the host protocol functionality. As host routing 423 computation progresses, one of the nodes will learn (from 424 the host protocol's routing table) that more than a certain number 425 of group members (say, T) are in its scope. It then proclaims 426 itself as a landmark for this group and adds itself to the landmark 427 distance vector. Landmarks broadcast the election weights to 428 the neighbors jointly with the landmark distance vector update 429 packets. 431 When more than one node declares itself as a landmark in the same 432 group, as the landmark information floods out, each node will 433 perform a winner competition procedure. Only one landmark for each 434 group will survive and it will be elected. To avoid flapping 435 between landmarks (very possible in a mobile situation), we use 436 hysteresis in the replacement of an existing landmark. I.e., the 437 old Landmark is replaced by the new one only if its weight is, say 438 less than 1/2 of the weight of the current election winner. Once 439 ousted, the old leader needs the full weight superiority to be 440 reinstated. 442 This procedure is carried out periodically in the background (low 443 overhead, anyway). At steady state, a landmark propagates its 444 presence to all other nodes like a sink in DSDV. It is extremely 445 simple and it converges (by definition). In a mobile environment, 446 an elected landmark may eventually lose its role. The role shifting 447 is a frequent event. In a transient period, there exist several 448 landmarks in a single group. The transient period may be actually 449 the norm at high mobility. This transient behavior can be 450 drastically reduced by using hysteresis. 452 When a landmark dies, its neighbors will detect the silence after 453 a given timeout. The neighbors of the same group will then take 454 the responsibilities as landmarks and broadcast new landmark 455 information. A new round of landmark election then floods over 456 the entire network. 458 5.3. Drifters 460 Typically, all members in a logical subnet are within the scope of 461 the landmark, thus the landmark has a route to all members. It may 462 happen, however, that some of the members "drift off" the scope, 463 for example, a tank in a battalion may become stranded or lost. 464 To keep track of such "drifters", i.e., to make the route to them 465 known to the landmark, the following modification to the routing 466 table exchange is necessary. Each node, say i, on the shortest 467 path between a landmark L and a drifter l associated with that 468 landmark keeps a distance vector entry to l. Note that if l is 469 within the scope of i, this entry is already included in the 470 routing table of node i. When i transmits its distance vector to 471 neighbor, say j, then j will retain the entry to member l only if 472 d(j,l) is smaller than the scope or d(j,L) is smaller than d(i,L). 473 The latter condition occurs if j is on the shortest path from i 474 (and therefore from l) to L. This way, a path is maintained from 475 the landmark to each of its members, including drifters. The 476 procedure starts from l, at the time when a node finds it becomes 477 a drifter. It informs the landmark hop by hop about its presence. 479 The occurrences of drifters are dynamic in a mobile network. In 480 order to timely remove the staled drifter information, the time 481 when a node hears a drifter is recorded. A node monitors whether 482 it becomes a drifter periodically and refreshes its occurrence 483 along the path towards the landmark. 485 6. Protocol Specifications 487 This section discusses the operation of LANMAR routing protocol. 488 The sending and receiving of landmark updates are in the proactive 489 nature. The routing packets are processed separately from 490 ordinary data packets. 492 6.1. Data Structures 494 Each node has a unique "logical" identifier defined by a subnet 495 field and a host field. The host field is unique in the subnet and 496 might in fact coincide with the physical address. The "logical" 497 identifier can also be an IP address when the subnet address can 498 logically group the nodes. Moreover, each node keeps a landmark 499 status tuple. As LANMAR runs on top of a host routing protocol, 500 it shares the underlying routing table structures. LANMAR 501 maintains a neighbor list and shares it with the host protocol. 502 In addition, LANMAR keeps a drifter list and a landmark distance 503 vector. 505 6.1.1. Landmark Status Tuple 507 Each node has not only a "logical" identifier, which basically is 508 its address, but also a landmark status tuple. The tuple includes 509 a flag which indicates whether the node is a landmark or not, a 510 election weight (the number of group members the node detects within 511 its scope) and a sequence number. When a node is elected, the 512 status tuple will be copied to its landmark distance vector. The 513 sequence number is advanced. There are three fields for a tuple: 514 - Landmark flag 515 - Number of group members in its scope 516 - Sequence number 518 6.1.2. Landmark Distance Vector 520 Landmark distance vector (LMDV) gives the next hop information to 521 all landmarks in the network. Every subnet has an entry in LMDV. 522 The latest route information to the landmark of each subnet is 523 learned when a landmark update message is received. LMDV functions 524 as a part of the routing table. It has the following fields: 525 - Landmark status tuple 526 - Next hop address 527 - Distance 529 6.1.3. Drifter List 531 The drifter list (DFDV) of LANMAR provides the next hop information 532 of the drifters known to the current node. The entries are updated 533 with landmark update message. The latest time a drifter is heard 534 is recorded in DFDV. The DFDV works as a part of routing table. 535 It has the following fields: 536 - Destination drifter address 537 - Next hop address 538 - Distance 539 - Drifter sequence number 540 - Last heard time 542 6.1.4. Neighbor List 544 The neighbor list of LANMAR keeps current neighbor information for 545 a node. The latest time a neighbor is heard is recorded. The 546 neighbor list has the following fields: 547 - Neighbor address 548 - Neighbor landmark flag 549 - Last heard time 551 6.2. LANMAR Update Message Format 553 There is only one message type of LANMAR protocol. The messages are 554 periodically exchanged with neighbors. They update the landmark 555 distance vector LMDV and the drifter list DFDV. The processing of 556 the LMDV and DFDV will be describe separately. The following format 557 does not include the node's identifier because it can be obtained 558 from IP Header. 560 0 1 2 3 561 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 562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 563 | Landmark Flag | N_landmarks | N_drifters | Reserved | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 | Landmark Address 1 | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 567 | Next Hop Address 1 | 568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 569 | Distance 1 | N_members 1 | Sequence Number 1 : 570 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 571 : . . . : 572 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 573 | Drifter Address 1 | 574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 575 | Next Hop Address 1 | 576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 577 | Distance 1 | Drifter Sequence Number 1 | ... : 578 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 579 : . . . | 580 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 582 6.2.1. Description of the fields 584 Landmark Flag 586 The landmark flag of the original sender. 588 N_landmarks 590 The number of entries of the landmark distance vector. 592 N_drifters 594 The number of entries of the drifter list. 596 Reserved 598 The bits are set to '0' and are ignored on reception. 600 Landmark Address 1, Next Hop Address 1, Distance 1, N_members 1 601 and Sequence Number 1 603 The first entry in the landmark distance vector. 604 Landmark Address 1, N_members 1 and Sequence Number 1 are the 605 status tuple of the destination landmark. 606 Next Hop Address 1 and Distance 1 is the next hop and distance 607 to the landmark. 609 These fields are repeated N_landmarks times for each entry in 610 landmark distance vector. 612 Drifter Address 1, Next Hop Address 1, Distance 1 and 613 Drifter Sequence Number 1 615 The first entry in the drifter list. 616 Next Hop Address 1 and Distance 1 are the next hop and distance 617 to the Drifter Address 1. 619 These fields are repeated N_drifters times for each entry in 620 the drifter list. 622 The length of the message is limited to the maximum IP packet size. 623 In that case, multiple packets may be required to broadcast all the 624 entries. 626 6.3. Processing Landmark Updates 628 Landmark update information is a part of the LANMAR periodic 629 routing update message. The update information includes sender's 630 LMDV. Landmark update message is used for landmark election and 631 building paths to landmarks. 633 6.3.1. Originating a Landmark in a Subnet 635 Every time a node detects a neighbor change, it recalculates the 636 number of group members in its scope. The new number of group 637 members is recorded in its election weight field. If this 638 number is greater than a threshold T, the node qualifies as a 639 landmark only when it is the only landmark for the group so far, 640 or it wins the election when competing with the existing landmark. 641 When it becomes a landmark, it increases its sequence number by 2. 642 Its current landmark status tuple will be inserted into the LMDV 643 or the existing landmark is replaced with the new winner. The 644 landmark entry will be broadcast to neighbors with the next update 645 packet. 647 6.3.2. Receiving Landmark Updates 649 When a node receives a landmark update message, it compares its 650 LMDV entries with the incoming LMDV updates for each subnet. 651 A landmark update corresponding to a new subnet will be copied. 652 An update having the same landmark as already given (in node's LMDV) 653 will be accepted only if it contains a larger sequence number. 654 If an update contains a different landmark for the same subnet as 655 recorded in LMDV, only one landmark will be elected through a 656 winner competition algorithm. LMDV will be updated according to 657 the outcomes of the competition. 659 6.3.3. Winner Competition 661 When more than one node declares itself as a landmark in the same 662 group, a simple solution is to let the node with the largest 663 number of group members win the election and in case of tie, 664 lowest ID breaks the tie. The other competing nodes defer. 665 However, this method is likely to cause the oscillation of 666 landmark roles between nodes. 668 To use hysteresis in replacing an existing landmark, let us assume 669 the competing node's number of members is M, the existing 670 landmark's number of members is N and a factor value S. When M is 671 greater than N*S, then the competing node replaces the existing 672 landmark. Or, when N reduces to a value smaller than a threshold T, 673 then it gives up the landmark role. A tie occurs when M falls 674 within an interval [N*1/S, N*S], then the node with larger member 675 number wins the election. If a tie occurs again with equal member 676 number, i.e., M equals to N, it is broken using lowest ID. A tie 677 can always be broken using lowest ID as the address is used as ID 678 and it is unique. 680 6.4. Processing Drifter Updates 682 Drifter update information is a part of the LANMAR periodical 683 routing update message. The update information is the drifter list 684 (DFDV) of the sender. The computation of the DFDV at each node 685 includes checking the node itself to see whether it is a drifter 686 and recording paths to other drifters. 688 6.4.1. Originating a Drifter Entry 690 By checking the distance to the landmark of its group, each node 691 easily knows whether it has become a drifter. If the distance is 692 larger than the scope, the node will put itself into its drifter 693 list. This drifter information will be sent back to the landmark 694 hop by hop along the shortest path to it which can be learned from 695 the LMDV. For each drifter, only the node on its shortest path 696 to the landmark needs to receive its information, so before the 697 entry is broadcast, the next hop to landmark is attached with 698 its entry. Each drifter maintains a drifter sequence number. 699 Each time a node finds itself a drifter, the sequence number 700 will be increased by 2. The DFDV will be propagated with the 701 next update packet. 703 6.4.2. Receiving Drifter Updates 705 Upon receiving an update packet, the DFDV part is retrieved and 706 processed. If an entry of incoming DFDV indicates that the current 707 node is its next hop to the landmark, i.e., the current node is on 708 the drifter's shortest path to the landmark, the current node will 709 insert or update its drifter list. The receiving time is stamped 710 in the DFDV. The node sending the update packet is recorded as the 711 next hop to the drifter. The reverse path to the drifter is thus 712 built up. The procedure ends when the landmark receives the 713 drifter entry. The updated DFDV will be propagated with the next 714 update packet. 716 6.4.3. Removing a Drifter Entry 718 Each entry in DFDV is time stamped of its last receiving time. 719 Every time before the DFDV is sent or routing by DFDV is needed, 720 the table is checked for staled entries. If such an entry is found, 721 it is removed. 723 6.5. Processing Neighbor List 725 When a node receives either a landmark update or a host protocol 726 routing update, the neighbor list is inserted if the update comes 727 from a new neighbor, or the corresponding neighbor entry is 728 updated. Current time is recorded with the entry. The 729 neighbor list is also search at this time for possible lost 730 neighbors according to the time stamps. If such a neighbor is 731 found, it is removed from the list. 733 6.6. Processing Lost Neighbor 735 A lost neighbor will be discovered by checking staled entries in 736 the neighbor list or by feedback from the MAC layer protocol. 737 A neighbor loss leads to searches in LMDV and DFDV. If the lost 738 neighbor happens to be the next hop to a landmark or a drifter, 739 the corresponding table entry is removed. 741 7. Data Packet Forwarding 743 Data packets are relayed hop by hop. The host protocol routing 744 table, drifter list and landmark distance vector are looked up 745 sequentially for the destination entry. If the destination is 746 within a node's scope, the entry can be found directly in the 747 routing table and the packet is forwarded to the next hop node. 748 Otherwise, the drifter list DFDV is searched for the destination. 749 If the entry is found, the packet is forwarded using the next hop 750 address from DFDV. If not, the logical subnet field of the 751 destination is retrieved and the LMDV entry of the landmark 752 corresponding to the destination's logical subnet is searched. 753 The data packet is then routed towards the landmark using the next 754 hop address from LMDV. The packet, however, is not necessary to 755 pass through the landmark. Rather, once the packet gets within the 756 scope of the destination on its way towards the landmark, it is 757 routed to the destination directly. 759 8. Discussion about Storage and Processing Overhead for Drifters 760 The routing storage and processing overhead introduced by the 761 distance vector extension to handle drifters is typically small 762 if the fraction of drifting nodes is small. Consider a network 763 with N nodes and L landmarks, and assume that a fraction F of the 764 members of each logical subnet have drifted. In the worst case, 765 the path length from landmark to drifter is the square root of N 766 (assuming a grid topology). Thus, sqrt(N) is the bound on the 767 number of extra routing entries required at the nodes along the 768 path to the drifter. The total number of extra routing entries is 769 sqrt(N)*L*(F*N/L) where N/L is the average logical group size. 770 Thus, the extra storage per node is F*sqrt(N). Now, let us assume 771 that the number of nodes in the scope = # of landmarks = logical 772 group size = sqrt(N). Then, the basic routing table overhead per 773 node (excluding drifters) is 3*sqrt(N). Thus, the extra overhead 774 caused by drifters is F/3. If 20% of the nodes in a group are 775 outside of the landmark scope, i.e., have drifted, the extra 776 routing O/H required to keep track of them is only 7%. 778 9. Scoped Routing Operations 780 9.1. Fisheye State Routing protocol 782 Fisheye State Routing (FSR) [7][8] is easy to adapt to a host 783 protocol. A two level Fisheye scope is used when FSR is used 784 for host protocol. For nodes within the scope, the updating 785 is in a certain frequency. But for nodes beyond the scope, 786 the update frequency is reduced to zero; Only the update 787 frequency of the landmark nodes remains unaltered. As a result, 788 each node maintains accurate routing information for in-scope 789 nodes and keep routing directions to the landmark nodes for 790 out-scope nodes, or say, for remote groups. A packet directed 791 to a remote destination initially aims at the landmark of that 792 remote group; as it gets closer to the landmark, it may 793 eventually switch to the accurate route to the destination 794 provided by in-scope nodes of the destination. 796 9.2. Destination-sequenced Distance Vector Routing protocol 797 Distance Vector type routing protocols use smaller routing 798 tables (comparing to Link State type) and generate lower routing 799 overhead. Destination-sequenced Distance Vector Routing (DSDV) [3] 800 uses destination sequenced sequence numbers to prevent the 801 forming of loops. The protocol can also work together with 802 LANMAR. The modifications include containing only the 803 destinations within the local scope in the periodic routing 804 update messages and turning off the triggered updates. 806 9.3. Optimized Link State Routing protocol 808 Optimized Link State Routing (OLSR) [9] provides the facility 809 for scope-limited flooding of messages. The generic message 810 format contains a "Time To Live" field, which gives the maximum 811 number of hops that a message will travel. Each time a message 812 is retransmitted, the "Time To Live" field is decreased by 1. 813 When the value of this field is reduced to zero, the massage 814 will not be forwarded any more. 816 OLSR can be one of the underlying protocol of LANMAR. The 817 "Time To Live" field is set to the scope defined in LANMAR 818 when a message is originated. The advantage of the combination 819 is the scalability to both dense and sparse network with 820 large number of nodes and large terrain size. 822 Acknowledgments 824 This work was supported in part by NSF under contract ANI-9814675, 825 by DARPA under contract DAAB07-97-C-D321, and by ONR under 826 contract N00014-01-C-0016. 828 References 830 [1] G. Pei, M. Gerla and X. Hong, "LANMAR: Landmark Routing for 831 Large Scale Wireless Ad Hoc Networks with Group Mobility", 832 Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000. 834 [2] M. Gerla, X. Hong, G. Pei, "Landmark Routing for Large Ad Hoc 835 Wireless Networks", Proceedings of IEEE GLOBECOM 2000, 836 San Francisco, CA, Nov. 2000. 838 [3] C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination- 839 Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," 840 In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994, 841 pp. 234-244. 843 [4] UCLA Wireless Adaptive Mobility (WAM) Laboratory. 844 http://www.cs.ucla.edu/NRL/wireless 846 [5] S. Bradner. Key words for use in RFCs to Indicate 847 Requirement Levels. RFC 2119, March 1997. 849 [6] P. F. Tsuchiya, "The Landmark Hierarchy: a new hierarchy for 850 routing in very large networks", Computer Communication Review, 851 vol.18, no.4, Aug. 1988, pp. 35-42. 853 [7] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing: 854 A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of 855 ICC 2000, New Orleans, LA, Jun. 2000. 857 [8] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in 858 Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless 859 Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000. 861 [9] P. Jacquet, P. Muhlethaler, A. Qayyum, A. Laouiti, L. Viennot 862 and T. Clausen, "Optimized Link State Routing Protocol", Internet 863 Draft, IETF MANET Working Group, draft-ietf-manet-olsr-04.txt, 864 Mar. 2001. 866 Chair's Address 868 The MANET Working Group can be contacted via its current chairs: 870 M. Scott Corson 871 Flarion Technologies, Inc. 872 Bedminster One 873 135 Route 202/206 South 874 Bedminster, NJ 07921 875 USA 877 Phone: +1 908 947-7033 878 Email: corson@flarion.com 880 Joseph Macker 881 Information Technology Division 882 Naval Research Laboratory 883 Washington, DC 20375 884 USA 886 Phone: +1 202 767-2001 887 Email: macker@itd.nrl.navy.mil 889 Authors' Addresses 891 Questions about this document can also be directed to the authors: 893 Mario Gerla 894 3732F Boelter Hall 895 Computer Science Department 896 University of California 897 Los Angeles, CA 90095-1596 898 USA 900 Phone: +1 310 825-4367 901 Fax: +1 310 825-7578 902 Email: gerla@cs.ucla.edu 904 Xiaoyan Hong 905 3803F Boelter Hall 906 Computer Science Department 907 University of California 908 Los Angeles, CA 90095-1596 909 USA 910 Phone: +1 310 825-4623 911 Fax: +1 310 825-7578 912 Email: hxy@cs.ucla.edu 914 Li Ma 915 3803D Boelter Hall 916 Computer Science Department 917 University of California 918 Los Angeles, CA 90095-1596 919 USA 921 Phone: +1 310 825-1888 922 Fax: +1 310 825-7578 923 Email: mary@cs.ucla.edu 925 Guangyu Pei 926 Rockwell Scientific Company 927 1049 Camino Dos Rios 928 P.O. Box 1085 929 Thousand Oaks, CA 91358-0085 930 USA 932 Phone: +1 805 373-4639 933 Fax: +1 805 373-4383 934 Email: gpei@rwsc.com