idnits 2.17.1 draft-ietf-manet-lanmar-04.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 184 has weird spacing: '.... The scope...' == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- 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 (June 17, 2002) is 7984 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 (~~), 5 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: December 17, 2002 Li Ma 5 University of California, Los Angeles 6 Guangyu Pei 7 Rockwell Scientific Company 8 June 17, 2002 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 . . . . . . . . 7 88 5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 9 89 5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 9 90 5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9 91 5.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10 93 6. Protocol Specifications . . . . . . . . . . . . . . . . . . . 11 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 . . . . . . . . . . . . 13 101 6.2.2 Propagation of LANMAR Update Messages . . . . . . 13 102 6.3. Processing Landmark Updates . . . . . . . . . . . . . . 14 103 6.3.1 Originating a Landmark in a Subnet . . . . . . . 14 104 6.3.2 Receiving Landmark Updates . . . . . . . . . . . 14 105 6.3.3 Winner Competition . . . . . . . . . . . . . . . 15 106 6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 15 107 6.4.1 Originating a Drifter Entry . . . . . . . . . . . 15 108 6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 16 109 6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 16 110 6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 16 111 6.5.1 Update Neighbor List . . . . . . . . . . . . . . 16 112 6.5.2 Operations Regarding to Lost Neighbors . . . . . 16 114 7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 16 116 8. Discussion about Storage and Processing Overhead for Drifters 17 118 9. Scoped Routing Operations . . . . . . . . . . . . . . . . . . 17 119 9.1. Fisheye State Routing Protocol . . . . . . . . . . . . . 17 120 9.2. Destination-Sequenced Distance Vector Routing Protocol . 18 121 9.3. Optimized Link State Routing Protocol . . . . . . . . . 18 123 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 18 125 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 18 127 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 129 Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 19 131 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 133 1. Introduction 135 This document describes the Landmark Routing Protocol (LANMAR) [1,2] 136 developed by the Wireless Adaptive Mobility (WAM) Laboratory [4] at 137 Computer Science Department, University of California, Los Angeles. 139 The concept of landmark routing was first introduced in wired area 140 networks [6]. The original scheme required predefined multi-level 141 hierarchical addressing. The hierarchical address of each node 142 reflects its position within the hierarchy and helps to find a route 143 to it. Each node knows the routes to all the nodes within its 144 hierarchical partition. Moreover, each node knows the routes to 145 various landmarks at different hierarchical levels. Packet 146 forwarding is consistent with the landmark hierarchy and the path 147 is gradually refined from the top level hierarchy to lower levels 148 as a packet approaches its destination. 150 LANMAR borrows the concept of landmark and extends it to the 151 wireless ad hoc environment. LANMAR scheme does not require 152 predefined hierarchical address, but it uses the notion of landmarks 153 to keep track of logical subnets in which the members have a 154 commonality of interests and are likely to move as a group 155 (e.g., brigade in the battlefield, a group of students from same 156 class and a team of co-workers at a convention). Each such 157 logical group has an elected landmark. For each group, 158 the underlying scoped routing algorithm will provide accurate 159 routing information for nodes within scope. The routing 160 update packets are restricted only within the scope. The 161 routing information to remote nodes (nodes outside the node's 162 scope) is summarized by the corresponding landmarks. Thus, 163 the LANMAR scheme largely reduces the routing table size and 164 the routing update traffic overhead. It greatly improves 165 scalability. 167 In addition, in order to recover from landmark failures, 168 a landmark node is elected in each subnet. Landmark election 169 provides a flexible way for the LANMAR protocol to cope with a 170 dynamic and mobile network. The protocol also provides a solution 171 for nodes that are outside the scopes of the landmarks of 172 their logical groups (drifters). Extra storage, processing and 173 line overhead will be incurred for landmark election and drifter 174 bookkeeping. However, the design of the algorithms provides 175 solutions without compromising scalability. For example, the 176 routing overhead for handling drifters is typically small if the 177 fraction of drifting nodes is small. More analysis is given in 178 Section 8. 180 The LANMAR runs on top of a proactive routing protocol. It 181 requires that the underlying routing protocol support the scoped 182 subnetworking. Fisheye State Routing Protocol (FSR) [7,8] is 183 such a protocol that supports LANMAR. In FSR, the link state 184 protocol is used within the scope. The scope technique 185 can also be applied to a distance vector type protocol, 186 such as DSDV [3], in which the hop distance can be used to 187 limit the scope of routing message updating. The main advantage of 188 LANMAR is that the routing table includes only the nodes within the 189 scope and the landmark nodes. This feature greatly improves 190 scalability by reducing routing table size and update traffic O/H. 192 Thus the Landmark Routing Protocol provides an efficient and 193 scalable routing solution for a mobile, ad hoc environment while 194 keeping line and storage overhead (O/H) low. Moreover, the 195 election provides a much needed recovery from landmark failures. 197 2. Changes 198 Major changes from version 03 to version 04: 200 - Removed "neighbor landmark flag" field from neighbor list. 201 Clarified the operations when a neighbor is lost. 203 - Clarified the processing of landmark update messages, 204 especially, the operations when an infinite distance metric 205 occurs. Operation regarding to an infinite distance metric is 206 also added in data forwarding. 208 - A separate section describing the operation before sending a 209 landmark update message is added. 211 - Reported current implementation status. 213 - Editorial changes. 215 Major changes from version 02 to version 03: 217 - A drifter sequence number is used in drifter list to indicate 218 each new occurrence of a drifter. 220 - Processing of lost neighbors is added. 222 - A separate section describing the modifications made to various 223 proactive protocols. Operations of these protocols will then 224 only perform within a certain hop distances. 226 - Editorial changes. 228 Major changes from version 01 to version 02: 230 - Update of Status of This Memo. 232 Major changes from version 00 to version 01: 234 - A destination sequence number for each landmark is used to 235 ensure loop-free updates for a particular landmark. 237 - Landmark updates are propagated in separate messages, instead of 238 being piggybacked on local routing updates. This modification 239 decouples landmark routing from the underlying proactive routing 240 protocol. 242 3. Terminology 244 3.1. General Terms 245 This section defines terminology used in LANMAR. 247 node 249 A MANET router that implements Landmark Routing Protocol. 251 neighbor 253 Nodes that are within the radio transmission range. 255 scope 257 A network area that is centered at each node and bounded 258 by a certain maximum hop distances. 260 host protocol 262 Also known as local routing protocol, i.e., a proactive 263 protocol that works together with the Landmark Routing 264 Protocol, but only operates within the scope of each node. 266 underlying protocol 268 This term is used interchangeably with host protocol. 270 scoped routing protocol 272 A routing protocol that only exchanges routing information 273 up to a certain hop distance (scope). 275 subnet 277 Logical groups of nodes that present similar motion behavior. 279 group 281 This term is used interchangeably with subnet. 283 3.2. Specification Language 285 The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, 286 SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL in this 287 document are to be interpreted as described in RFC 2119 [5]. 289 4. Protocol Applicability 291 4.1. Networking Context 293 LANMAR is best suited for large scale mobile ad hoc wireless 294 networks. The landmark scheme on top of a scoped routing 295 algorithm has large advantages in reducing routing update packet 296 size and keeping reasonably accurate routes to remote nodes. 297 It achieves high data packet delivery ratio. Moreover, the fact 298 that the route error is blurred by distance obviously reduces the 299 sensitivity to network size. 301 LANMAR is also suited for high mobility ad hoc wireless networks. 302 This is because in a mobile environment, a change on a link far 303 away from the source does not necessarily cause a change in the 304 routing table at the source since all the information about 305 remote nodes is summarized by landmarks. 307 4.2. Protocol Characteristics and Mechanisms 309 * Does the protocol provide support for unidirectional links?(if so, 310 how?) 312 No. 314 * Does the protocol require the use of tunneling? (if so, how?) 315 No. 317 * Does the protocol require using some form of source routing? (if 318 so, how?) 320 No. 322 * Does the protocol require the use of periodic messaging? (if so, 323 how?) 325 Yes. The LANMAR periodically broadcasts landmark information 326 to its neighbors. 328 * Does the protocol require the use of reliable or sequenced packet 329 delivery? (if so, how?) 331 No. As the packets are sent periodically, they need not be 332 sent reliably. 334 * Does the protocol provide support for routing through a multi- 335 technology routing fabric? (if so, how?) 337 Yes. It is assumed that each node's network interface is 338 assigned a unique IP address. 340 * Does the protocol provide support for multiple hosts per router? 341 (if so, how?) 343 Yes. The router that has multiple hosts can use network ID of 344 these hosts as the address to participate LANMAR. 346 * Does the protocol support the IP addressing architecture? (if so, 347 how?) 348 Yes. Each node is assumed to have a unique IP address (or 349 set of unique IP addresses in the case of multiple interfaces). 350 The LANMAR references all nodes/interfaces by their IP address. 351 This version of the LANMAR also supports IP network addressing 352 (network prefixes) for routers that provide access to a 353 network of non-router hosts. 355 * Does the protocol require link or neighbor status sensing (if so, 356 how?) 358 No. 360 * Does the protocol have dependence on a central entity? (if so, 361 how?) 363 No. 365 * Does the protocol function reactively? (if so, how?) 367 No. 369 * Does the protocol function proactively? (if so, how?) 371 Yes. The LANMAR proactively maintains landmark information 372 at each node. 374 * Does the protocol provide loop-free routing? (if so, how?) 376 Yes. For in-scope destinations, the protocol uses routing 377 paths learned from the host protocol. If the host protocol 378 provides loop-free routing, e.g., FSR and DSDV, so does LANMAR. 379 For out-scope destinations, only routes to landmarks are used. 380 Because these routes are DSDV, it is loop free. When a packet 381 approaches the destination, in-scope routes are used again. 383 * Does the protocol provide for sleep period operation?(if so, how?) 385 Yes. However, this requires TDMA MAC layer support. The 386 router can be scheduled to sleep during idle periods. 388 * Does the protocol provide some form of security? (if so, how?) 390 Yes. When a node broadcasts routing update message, only 391 entries of in-scope nodes and landmarks are included. This 392 will prevent other remote nodes from being heard. 394 * Does the protocol provide support for utilizing multi-channel, 395 link-layer technologies? (if so, how?) 397 Yes. In fact, the multi-channel can be used to separate 398 routing messages from user data packets. 400 5. Protocol Overview 402 5.1. Protocol Descriptions 404 As mentioned in Section 1, the landmark concept we adopt here uses 405 the notion of logical subnets in which the members have a 406 commonality of interests and are likely to move as a group. 407 Each logical subnet has one node serving as a landmark of that 408 subnet. The protocol requires that the landmark of each subnet have 409 the knowledge of all the members in its group. The LANMAR protocol 410 also uses a routing scope at each node. The size of the scope is a 411 parameter measured in hop distance. It is chosen in such a way that 412 if a node is at the center of a subnet, the scope will cover the 413 majority of the subnet members. If the shape of a subnet is likely 414 to be a cycle, the center node's scope will cover all the members of 415 the subnet. If this center node is elected as a landmark, it 416 fulfills the requirement of the protocol. The elected landmark 417 uses a destination sequence number to ensure its routing entry 418 update loop-free. The landmarks are propagated in a 419 distance vector mechanism. Each node maintains a distance vector 420 for landmarks of all the subnets. The size of the landmark distance 421 vector equals to the number of logical subnets and thus landmark 422 nodes. If a landmark does not locate at the center, there will be 423 some members drifting off its scope. The landmark will keep a 424 distance vector for drifters of its group. The distance vectors 425 for landmarks and drifters are exchanged among neighbors in 426 periodical routing update packets. 428 The LANMAR relies on an underlying proactive protocol with the 429 ability of providing routing within the scope. In this local scoped 430 routing, each node broadcasts routing information periodically to 431 its immediate neighbors. In each update packet, the node includes 432 all the routing table entries within the scope centered at it. 434 5.2. Landmark Election 436 Dynamic election/re-election of landmark node is essential for 437 LANMAR to work in a wireless mobile environment. Basically, each 438 node tracks other nodes of its group in its scope and computes 439 weight, e.g. the number of the nodes it has found. At the 440 beginning of the LANMAR, no landmark exists. Protocol LANMAR 441 only uses the host protocol functionality. As host routing 442 computation progresses, one of the nodes will learn (from 443 the host protocol's routing table) that more than a certain number 444 of group members (say, T) are in its scope. It then proclaims 445 itself as a landmark for this group and adds itself to the landmark 446 distance vector. Landmarks broadcast the election weights to 447 the neighbors jointly with the landmark distance vector update 448 packets. 450 When more than one node declares itself as a landmark in the same 451 group, as the landmark information floods out, each node will 452 perform a winner competition procedure. Only one landmark for each 453 group will survive and it will be elected. To avoid flapping 454 between landmarks (very possible in a mobile situation), we use 455 hysteresis in the replacement of an existing landmark. I.e., the 456 old Landmark is replaced by the new one only if its weight is, say 457 less than 1/2 of the weight of the current election winner. Once 458 ousted, the old leader needs the full weight superiority to be 459 reinstated. 461 This procedure is carried out periodically in the background (low 462 overhead, anyway). At steady state, a landmark propagates its 463 presence to all other nodes like a sink in DSDV. It is extremely 464 simple and it converges (by definition). In a mobile environment, 465 an elected landmark may eventually lose its role. The role shifting 466 is a frequent event. In a transient period, there exist several 467 landmarks in a single group. The transient period may be actually 468 the norm at high mobility. This transient behavior can be 469 drastically reduced by using hysteresis. 471 When a landmark dies, its neighbors will detect the silence after 472 a given timeout. The neighbors of the same group will then take 473 the responsibilities as landmarks and broadcast new landmark 474 information. A new round of landmark election then floods over 475 the entire network. 477 5.3. Drifters 479 Typically, all members in a logical subnet are within the scope of 480 the landmark, thus the landmark has a route to all members. It may 481 happen, however, that some of the members drift off the scope, 482 for example, a tank in a battalion may become stranded or lost. 483 To keep track of such drifters, i.e., to make the route to them 484 known to the landmark, the following modification to the routing 485 table exchange is necessary. Each node, say i, on the shortest 486 path between a landmark L and a drifter l associated with that 487 landmark keeps a distance vector entry to l. Note that if l is 488 within the scope of i, this entry is already included in the 489 routing table of node i. When i transmits its distance vector to 490 neighbor, say j, then j will retain the entry to member l only if 491 d(j,l) is smaller than the scope or d(j,L) is smaller than d(i,L). 492 The latter condition occurs if j is on the shortest path from i 493 (and therefore from l) to L. This way, a path is maintained from 494 the landmark to each of its members, including drifters. The 495 procedure starts from l, at the time when a node finds it becomes 496 a drifter. It informs the landmark hop by hop about its presence. 498 The occurrences of drifters are dynamic in a mobile network. In 499 order to timely remove the staled drifter information, the time 500 when a node hears a drifter is recorded. A node monitors whether 501 it becomes a drifter periodically and refreshes its occurrence 502 along the path towards the landmark. 504 6. Protocol Specifications 506 This section discusses the operation of LANMAR routing protocol. 507 The sending and receiving of landmark updates are in the proactive 508 nature. The routing packets are processed separately from 509 ordinary data packets. 511 6.1. Data Structures 513 Each node has a unique logical identifier defined by a subnet 514 field and a host field. The host field is unique in the subnet and 515 might in fact coincide with the physical address. The logical 516 identifier can also be an IP address when the subnet address 517 logically reflects the grouping of nodes. 519 As LANMAR runs on top of a host routing protocol, it shares the 520 routing table with the host protocol. Also, LANMAR may maintain 521 a separate neighbor list, or share it with the host protocol. 522 In addition, LANMAR keeps a landmark distance vector and a drifter 523 list. And each node also has a landmark status tuple. In this 524 draft, we only describe data structures that pertain to LANMAR. 526 6.1.1. Landmark Status Tuple 528 Each node has not only a logical identifier, which basically is 529 its address, but also a landmark status tuple. The tuple includes 530 a flag which indicates whether the node is a landmark or not, a 531 election weight (the number of group members the node detects within 532 its scope) and a sequence number. When a node is elected, the 533 status tuple will be copied to its landmark distance vector. The 534 sequence number is advanced. There are three fields for a tuple: 535 - Landmark flag 536 - Number of group members in its scope 537 - Sequence number 539 6.1.2. Landmark Distance Vector 541 Landmark distance vector (LMDV) gives the next hop information to 542 all landmarks in the network. Every subnet has an entry in LMDV. 543 The latest route information to the landmark of each subnet is 544 learned when a landmark update message is received. LMDV functions 545 as a part of the routing table. It has the following fields: 546 - Landmark status tuple 547 - Next hop address 548 - Distance 550 6.1.3. Drifter List 552 The drifter list (DFDV) of LANMAR provides the next hop information 554 of the drifters known to the current node. The entries are updated 555 with landmark update message. The latest time a drifter is heard 556 is recorded in DFDV. The DFDV works as a part of routing table. 557 It has the following fields: 558 - Destination drifter address 559 - Next hop address 560 - Distance 561 - Drifter sequence number 562 - Last heard time 564 6.1.4. Neighbor List 566 The neighbor list of LANMAR keeps current neighbor information for 567 a node. The latest time a neighbor is heard is recorded. The 568 neighbor list has the following fields: 569 - Neighbor address 570 - Last heard time 572 If the host routing protocol maintains at least the above neighbor 573 information, LANMAR does not need to keep this separate neighbor 574 list. It can share the neighbor information with the host routing 575 protocol. 577 6.2. LANMAR Update Message Format 579 There is only one message type of LANMAR protocol: LANMAR Update 580 (LMU). The messages are periodically exchanged with neighbors. 581 They update the landmark distance vector LMDV and the drifter 582 list DFDV. It is possible that LMDV or DFDV is empty, so no 583 entries of the empty table will be included. The processing of 584 the LMDV and DFDV will be describe separately. The following format 585 does not include the node's identifier because it can be obtained 586 from IP Header. 588 0 1 2 3 589 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 590 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 591 | Landmark Flag | N_landmarks | N_drifters | Reserved | 592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 593 | Landmark Address 1 | 594 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 595 | Next Hop Address 1 | 596 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 597 | Distance 1 | N_members 1 | Sequence Number 1 : 598 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 599 : . . . : 600 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 601 | Drifter Address 1 | 602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 603 | Next Hop Address 1 | 604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 605 | Distance 1 | Drifter Sequence Number 1 | ... : 607 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 608 : . . . | 609 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 611 6.2.1. Description of the fields 613 Landmark Flag 615 The landmark flag of the original sender. 617 N_landmarks 619 The number of entries of the landmark distance vector. 621 N_drifters 623 The number of entries of the drifter list. 625 Reserved 627 The bits are set to '0' and are ignored on reception. 629 Landmark Address 1, Next Hop Address 1, Distance 1, N_members 1 630 and Sequence Number 1 632 The first entry in the landmark distance vector. 633 Landmark Address 1, N_members 1 and Sequence Number 1 are the 634 status tuple of the destination landmark. 635 Next Hop Address 1 and Distance 1 is the next hop and distance 636 to the landmark. 638 These fields are repeated N_landmarks times for each entry in 639 landmark distance vector. 641 Drifter Address 1, Next Hop Address 1, Distance 1 and 642 Drifter Sequence Number 1 644 The first entry in the drifter list. 645 Next Hop Address 1 and Distance 1 are the next hop and distance 646 to the Drifter Address 1. 648 These fields are repeated N_drifters times for each entry in 649 the drifter list. 651 The length of the message is limited to the maximum IP packet size. 652 In that case, multiple packets may be required to broadcast all the 653 entries. 655 6.2.2. Propagation of LANMAR Update Messages 657 LANMAR update messages (LMUs) are propagated periodically. The 658 frequency could be set according to mobility. Propagation jitters 659 must be used for each message transmission to reduce collisions. 660 Before sending a LMU, each node checks whether it is a drifter 661 and does corresponding calculations (see 6.4.1). An existing 662 drifter node increases its drifter sequence number by 2. If the 663 node is a landmark, it increases its sequence number by 2 both 664 to its status tuple and to its entry in LMDV. Then the node 665 assembles in the LMU the LMDV and DFDV. This message will be 666 sent after a small random time interval. 668 6.3. Processing Landmark Updates 670 Landmark update information is a part of the LANMAR periodic 671 routing update message. The update information includes sender's 672 LMDV. Landmark update message is used for landmark election and 673 building paths to landmarks. 675 6.3.1. Originating a Landmark in a Subnet 677 Every time a node detects a topology change within the scope 678 (either a neighbor change or a topology change leaned from the 679 host protocol), it recalculates the number of group members 680 in its scope. The new number of group members is recorded in 681 its election weight field. If this number is greater than a 682 threshold T, the node qualifies as a landmark when one of the 683 following conditions is met. 684 (1) it is the only landmark for the group so far; 685 (2) the existing landmark has an infinite distance metric; 686 (3) it wins the election (see 6.3.3) when competing with the 687 existing landmark. 688 When the node becomes a landmark, it increases its sequence 689 number by 2. Its current landmark status tuple will be inserted 690 into the LMDV or the existing landmark is replaced with the new 691 winner. This landmark entry will be broadcast to neighbors 692 with the next update packet. 694 6.3.2. Receiving Landmark Updates 696 When a node receives a landmark update message, it compares its 697 LMDV entries with the entries in the incoming LMDV message for 698 each subnet. There are three situations to consider: 699 (1) An incoming landmark entry corresponding to a new subnet 700 and its distance metric is less than infinity, the entry 701 will be copied. 702 (2) An incoming entry having the same landmark as an existing 703 one (in node's LMDV), it will be accepted only if one of 704 the following conditions is met. 705 (a) it contains a larger sequence number and the distance 706 metric is less than infinity; 707 (b) it contains a larger sequence number and the distance 708 metric equals to infinity and it happens to be the 709 next hop in the already existing entry; 711 (c) it has the same sequence number with the existing 712 entry, but a smaller distance metric. 713 (3) If an incoming entry contains a different landmark for 714 the same subnet as recorded in LMDV, only the landmark 715 that does not have an infinite distance and is elected 716 through a winner competition algorithm (see 6.3.3) is 717 accepted. The LMDV entry will be kept/updated according 718 to the outcomes of the competition. 720 6.3.3. Winner Competition 722 When more than one node declares itself as a landmark in the same 723 group, a simple solution is to let the node with the largest 724 number of group members win the election and in case of tie, 725 lowest ID breaks the tie. The other competing nodes defer. 726 However, this method is likely to cause the oscillation of 727 landmark roles between nodes. 729 To use hysteresis in replacing an existing landmark, let us assume 730 the competing node's number of members is M, the existing 731 landmark's number of members is N and a factor value S. When M is 732 greater than N*S, then the competing node replaces the existing 733 landmark. Or, when N reduces to a value smaller than a threshold T, 734 then it gives up the landmark role. A tie occurs when M falls 735 within an interval [N*1/S, N*S], then the node with a larger member 736 number wins the election. If a tie occurs again with equal member 737 number, i.e., M equals to N, it is broken using lowest ID. A tie 738 can always be broken using lowest ID as the address is used as ID 739 and it is unique. 741 6.4. Processing Drifter Updates 743 Drifter update information is a part of the LANMAR periodical 744 routing update message. The update information is the drifter list 745 (DFDV) of the sender. The computation of the DFDV at each node 746 includes checking the node itself to see whether it is a drifter 747 and recording paths to other drifters. 749 6.4.1. Originating a Drifter Entry 751 By checking the distance to the landmark of its group, each node 752 easily knows whether it has become a drifter. If the distance is 753 larger than the scope, the node will put itself into its drifter 754 list. This drifter information will be sent back to the landmark 755 hop by hop along the shortest path to it which can be learned from 756 the LMDV. For each drifter, only the node on its shortest path 757 to the landmark needs to receive its information, so before the 758 entry is broadcast, the drifter or the intermediate nodes 759 look for the next hop to drifter's landmark in their LMDVs first. 760 Then the next hop is included in LMU within the drifter entry. 761 Each drifter also maintains a drifter sequence number. 762 Each time a node finds itself a drifter, the sequence number 763 will be increased by 2. The DFDV will be propagated with the 764 next update packet. 766 6.4.2. Receiving Drifter Updates 768 Upon receiving an update packet, the DFDV part is retrieved and 769 processed. If an entry of incoming DFDV indicates that the current 770 node is its next hop to the landmark, i.e., the current node is on 771 the drifter's shortest path to the landmark, the current node will 772 insert or update its drifter list. The receiving time is stamped 773 in the DFDV. The node sending the update packet is recorded in 774 DFDV as the next hop to the drifter. The reverse path to the 775 drifter is thus built up. The procedure ends when the landmark 776 receives the drifter entry. The updated DFDV will be propagated 777 with the next update packet. 779 6.4.3. Removing a Drifter Entry 781 Each entry in DFDV is time stamped of its last receiving time. 782 Every time before the DFDV is sent or routing by DFDV is needed, 783 the table is checked for staled entries. If such an entry is found, 784 it is removed. 786 6.5. Processing Neighbor List 788 6.5.1. Update Neighbor List 790 When a node receives either a landmark update or a host protocol 791 routing update, the neighbor list is inserted if the update comes 792 from a new neighbor, or the corresponding neighbor entry is 793 updated. Current time is recorded with the entry. The 794 neighbor list is also search at this time for possible lost 795 neighbors according to the time stamps. If such a neighbor is 796 found, it is removed from the list. 798 6.5.2. Operations Regarding to Lost Neighbors 800 A lost neighbor will be discovered by checking staled entries in 801 the neighbor list or by feedback from the MAC layer protocol. 802 A neighbor loss leads to searches in LMDV and DFDV. If the lost 803 neighbor happens to be the next hop to a landmark or a drifter, 804 the corresponding table entry in LMDV is marked an infinite 805 distance metric, while the corresponding table entry in DFDV is 806 removed. The infinite distance entries in LMDV will be 807 propagated with a sequence number increased by 1. Thus, the new 808 link break information will overwrite the entries at downstream 809 nodes. As long as the landmark propagates next new update 810 message with a sequence number increased by 2, new routes are 811 built up. 813 7. Data Packet Forwarding 814 Data packets are relayed hop by hop. The host protocol's 815 routing table, drifter list and landmark distance vector are 816 looked up sequentially for the destination entry. If the 817 destination is within a node's scope, the entry can be found 818 directly in the routing table and the packet is forwarded to 819 the next hop node. Otherwise, the drifter list DFDV is 820 searched for the destination. If the entry is found, the 821 packet is forwarded using the next hop address from DFDV. 822 If not, the logical subnet field of the destination is retrieved 823 and the LMDV entry of the landmark corresponding to the 824 destination's logical subnet is searched. If the distance 825 metric is not an infinity, the data packet is then routed 826 towards the landmark using the next hop address from LMDV. 827 If all these attempts are failed, the data packet is dropped. 828 When the data packet is routed towards a landmark, it is not 829 necessary for the packet to pass through the landmark. Rather, 830 once the packet gets within the scope of the destination on 831 its way towards the landmark, it is routed to the destination 832 directly. 834 8. Discussion about Storage and Processing Overhead for Drifters 836 The routing storage and processing overhead introduced by the 837 distance vector extension to handle drifters is typically small 838 if the fraction of drifting nodes is small. Consider a network 839 with N nodes and L landmarks, and assume that a fraction F of the 840 members of each logical subnet have drifted. In the worst case, 841 the path length from landmark to drifter is the square root of N 842 (assuming a grid topology). Thus, sqrt(N) is the bound on the 843 number of extra routing entries required at the nodes along the 844 path to the drifter. The total number of extra routing entries is 845 sqrt(N)*L*(F*N/L) where N/L is the average logical group size. 846 Thus, the extra storage per node is F*sqrt(N). Now, let us assume 847 that the number of nodes in the scope = # of landmarks = logical 848 group size = sqrt(N). Then, the basic routing table overhead per 849 node (excluding drifters) is 3*sqrt(N). Thus, the extra overhead 850 caused by drifters is F/3. If 20% of the nodes in a group are 851 outside of the landmark scope, i.e., have drifted, the extra 852 routing O/H required to keep track of them is only 7%. 854 9. Scoped Routing Operations 856 9.1. Fisheye State Routing protocol 858 Fisheye State Routing (FSR) [7][8] is easy to adapt to a host 859 protocol. A two level Fisheye scope is used when FSR is used 860 as a host protocol. For nodes within the scope, the updating 861 is in a certain frequency. But for nodes beyond the scope, 862 the update frequency is reduced to zero. As a result, 863 each node maintains accurate routing information for in-scope 864 nodes. A data packet directed to a remote destination initially 865 aims at the landmark of that remote group; as it gets closer 866 to the landmark, it may eventually switch to the accurate 867 route to the destination provided by FSR at some nodes within 868 the scope of the destination. 870 9.2. Destination-sequenced Distance Vector Routing protocol 871 Distance Vector type routing protocols use smaller routing 872 tables (comparing to Link State type) and generate lower 873 routing overhead. Destination-sequenced Distance Vector 874 Routing (DSDV) [3] uses destination sequenced sequence numbers 875 to prevent the forming of loops. The protocol can also work 876 together with LANMAR. The modifications include containing 877 only the destinations within the local scope in the periodic 878 routing update messages and turning off the triggered updates. 880 9.3. Optimized Link State Routing protocol 882 Optimized Link State Routing (OLSR) [9] provides the facility 883 for scope-limited flooding of messages. The generic message 884 format contains a Time To Live field, which gives the maximum 885 number of hops that a message will travel. Each time a message 886 is retransmitted, the Time To Live field is decreased by 1. 887 When the value of this field is reduced to zero, the massage 888 will not be forwarded any more. 890 OLSR can be one of the underlying protocol of LANMAR. The 891 Time To Live field is set to the scope defined in LANMAR 892 when a message is originated. The advantage of the combination 893 is the scalability to both dense and sparse network with 894 large number of nodes and large terrain size. 896 10. Implementation Status 898 LANMAR version 1 (according to version 3 of the draft, but 899 excluding the drifter operations) has been implemented in Linux 900 and is in use for laboratory experiments. 902 Acknowledgments 904 This work was supported in part by NSF under contract ANI-9814675, 905 by DARPA under contract DAAB07-97-C-D321, and by ONR under 906 contract N00014-01-C-0016. 908 References 910 [1] G. Pei, M. Gerla and X. Hong, LANMAR: Landmark Routing for 911 Large Scale Wireless Ad Hoc Networks with Group Mobility, 912 Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000. 914 [2] M. Gerla, X. Hong, G. Pei, Landmark Routing for Large Ad Hoc 915 Wireless Networks, Proceedings of IEEE GLOBECOM 2000, 916 San Francisco, CA, Nov. 2000. 918 [3] C.E. Perkins and P. Bhagwat, Highly Dynamic Destination- 919 Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, 920 In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994, 921 pp. 234-244. 923 [4] UCLA Wireless Adaptive Mobility (WAM) Laboratory. 924 http://www.cs.ucla.edu/NRL/wireless 926 [5] S. Bradner. Key words for use in RFCs to Indicate 927 Requirement Levels. RFC 2119, March 1997. 929 [6] P. F. Tsuchiya, The Landmark Hierarchy: a new hierarchy for 930 routing in very large networks, Computer Communication Review, 931 vol.18, no.4, Aug. 1988, pp. 35-42. 933 [7] G. Pei, M. Gerla, and T.-W. Chen, Fisheye State Routing: 934 A Routing Scheme for Ad Hoc Wireless Networks, Proceedings of 935 ICC 2000, New Orleans, LA, Jun. 2000. 937 [8] G. Pei, M. Gerla, and T.-W. Chen, Fisheye State Routing in 938 Mobile Ad Hoc Networks, Proceedings of Workshop on Wireless 939 Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000. 941 [9] P. Jacquet, P. Muhlethaler, A. Qayyum, A. Laouiti, L. Viennot 942 and T. Clausen, Optimized Link State Routing Protocol, Internet 943 Draft, IETF MANET Working Group, draft-ietf-manet-olsr-04.txt, 944 Mar. 2002. 946 Chair's Address 948 The MANET Working Group can be contacted via its current chairs: 950 M. Scott Corson 951 Flarion Technologies, Inc. 952 Bedminster One 953 135 Route 202/206 South 954 Bedminster, NJ 07921 955 USA 957 Phone: +1 908 947-7033 958 Email: corson@flarion.com 960 Joseph Macker 961 Information Technology Division 962 Naval Research Laboratory 963 Washington, DC 20375 964 USA 966 Phone: +1 202 767-2001 967 Email: macker@itd.nrl.navy.mil 969 Authors' Addresses 971 Questions about this document can also be directed to the authors: 973 Mario Gerla 974 3732F Boelter Hall 975 Computer Science Department 976 University of California 977 Los Angeles, CA 90095-1596 978 USA 980 Phone: +1 310 825-4367 981 Fax: +1 310 825-7578 982 Email: gerla@cs.ucla.edu 984 Xiaoyan Hong 985 3803F Boelter Hall 986 Computer Science Department 987 University of California 988 Los Angeles, CA 90095-1596 989 USA 991 Phone: +1 310 825-4623 992 Fax: +1 310 825-7578 993 Email: hxy@cs.ucla.edu 995 Li Ma 996 3803D Boelter Hall 997 Computer Science Department 998 University of California 999 Los Angeles, CA 90095-1596 1000 USA 1002 Phone: +1 310 825-1888 1003 Fax: +1 310 825-7578 1004 Email: mary@cs.ucla.edu 1006 Guangyu Pei 1007 Rockwell Scientific Company 1008 1049 Camino Dos Rios 1009 P.O. Box 1085 1010 Thousand Oaks, CA 91358-0085 1011 USA 1013 Phone: +1 805 373-4639 1014 Fax: +1 805 373-4383 1015 Email: gpei@rwsc.com