--- 1/draft-ietf-manet-lanmar-04.txt 2006-02-05 00:17:19.000000000 +0100 +++ 2/draft-ietf-manet-lanmar-05.txt 2006-02-05 00:17:19.000000000 +0100 @@ -1,22 +1,22 @@ IETF MANET Working Group Mario Gerla INTERNET-DRAFT Xiaoyan Hong -Expiration: December 17, 2002 Li Ma +Expiration: May 17, 2003 Li Ma University of California, Los Angeles Guangyu Pei Rockwell Scientific Company - June 17, 2002 + November 17, 2002 Landmark Routing Protocol (LANMAR) for Large Scale Ad Hoc Networks - + Status of This Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. @@ -70,70 +70,72 @@ Contents Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . 1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 - 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5 - 3.2. Specification Language . . . . . . . . . . . . . . . . . 6 + 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 6 + 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 6 + 3.2. Specification Language . . . . . . . . . . . . . . . . . 7 - 4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 6 - 4.1. Networking Context . . . . . . . . . . . . . . . . . . . 6 + 4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 7 + 4.1. Networking Context . . . . . . . . . . . . . . . . . . . 7 4.2. Protocol Characteristics and Mechanisms . . . . . . . . 7 5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 9 - 5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9 + 5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 10 5.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10 6. Protocol Specifications . . . . . . . . . . . . . . . . . . . 11 6.1. Data Structures . . . . . . . . . . . . . . . . . . . 11 6.1.1 Landmark Status tuple . . . . . . . . . . . . . . 11 - 6.1.2 Landmark Distance Vector . . . . . . . . . . . . 11 - 6.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11 - 6.1.4 Neighbor List . . . . . . . . . . . . . . . . . . 12 + 6.1.2 Landmark Distance Vector . . . . . . . . . . . . 12 + 6.1.3 Drifter List . . . . . . . . . . . . . . . . . . 12 6.2. LANMAR Update Message Format . . . . . . . . . . . . 12 6.2.1 Description of the fields . . . . . . . . . . . . 13 - 6.2.2 Propagation of LANMAR Update Messages . . . . . . 13 + 6.2.2 Propagation of LANMAR Update Messages . . . . . . 14 6.3. Processing Landmark Updates . . . . . . . . . . . . . . 14 6.3.1 Originating a Landmark in a Subnet . . . . . . . 14 - 6.3.2 Receiving Landmark Updates . . . . . . . . . . . 14 + 6.3.2 Receiving Landmark Updates . . . . . . . . . . . 15 6.3.3 Winner Competition . . . . . . . . . . . . . . . 15 - 6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 15 - 6.4.1 Originating a Drifter Entry . . . . . . . . . . . 15 + 6.3.4 Dealing with Stale LMDV Entries . . . . . . . . . 16 + 6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 16 + 6.4.1 Originating a Drifter Entry . . . . . . . . . . . 16 6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 16 - 6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 16 - 6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 16 - 6.5.1 Update Neighbor List . . . . . . . . . . . . . . 16 - 6.5.2 Operations Regarding to Lost Neighbors . . . . . 16 - - 7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 16 + 6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 17 + 6.5. Operations Regarding to Lost Neighbors . . . . . . . . . 17 - 8. Discussion about Storage and Processing Overhead for Drifters 17 + 7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 17 - 9. Scoped Routing Operations . . . . . . . . . . . . . . . . . . 17 - 9.1. Fisheye State Routing Protocol . . . . . . . . . . . . . 17 - 9.2. Destination-Sequenced Distance Vector Routing Protocol . 18 - 9.3. Optimized Link State Routing Protocol . . . . . . . . . 18 + 8. Combining LANMAR with a Host Protocol . . . . . . . . . . . . 17 + 8.1. Share Neighbor Information . . . . . . . . . . . . . . . 18 + 8.1.1 Inform the Host Protocol about a Neighbor . . . . 18 + 8.1.2 Being Informed about a Lost Neighbor . . . . . . 18 + 8.2. Scoped Routing Operations . . . . . . . . . . . . . . . 18 + 8.2.1 Destination-Sequenced Distance Vector . . . . . . 18 + 8.2.2 Fisheye State Routing Protocol . . . . . . . . . 18 + 8.2.3 Optimized Link State Routing Protocol . . . . . . 18 + 8.2.4 Topology Broadcast Based on Reverse-Path Forwarding + . . . . . . 19 - 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 18 + 9. Implementation Status . . . . . . . . . . . . . . . . . . . . 19 - Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 18 + Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 19 - References . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 + References . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 - Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 19 + Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 1. Introduction This document describes the Landmark Routing Protocol (LANMAR) [1,2] developed by the Wireless Adaptive Mobility (WAM) Laboratory [4] at Computer Science Department, University of California, Los Angeles. The concept of landmark routing was first introduced in wired area @@ -162,46 +164,61 @@ scope) is summarized by the corresponding landmarks. Thus, the LANMAR scheme largely reduces the routing table size and the routing update traffic overhead. It greatly improves scalability. In addition, in order to recover from landmark failures, a landmark node is elected in each subnet. Landmark election provides a flexible way for the LANMAR protocol to cope with a dynamic and mobile network. The protocol also provides a solution for nodes that are outside the scopes of the landmarks of - their logical groups (drifters). Extra storage, processing and - line overhead will be incurred for landmark election and drifter - bookkeeping. However, the design of the algorithms provides - solutions without compromising scalability. For example, the - routing overhead for handling drifters is typically small if the - fraction of drifting nodes is small. More analysis is given in - Section 8. + their logical groups (drifters). The LANMAR runs on top of a proactive routing protocol. It requires that the underlying routing protocol support the scoped - subnetworking. Fisheye State Routing Protocol (FSR) [7,8] is - such a protocol that supports LANMAR. In FSR, the link state - protocol is used within the scope. The scope technique - can also be applied to a distance vector type protocol, - such as DSDV [3], in which the hop distance can be used to - limit the scope of routing message updating. The main advantage of - LANMAR is that the routing table includes only the nodes within the - scope and the landmark nodes. This feature greatly improves - scalability by reducing routing table size and update traffic O/H. + subnetworking. Many MANET proactive routing protocols (e.g., DSDV, + FSR, OLSR and TBRPF) can be the host protocol with only minor + modifications (Section 8). The main advantage of LANMAR is that + the routing table includes only the nodes within the scope and the + landmark nodes. This feature greatly improves scalability by + reducing routing table size and update traffic O/H. Thus the Landmark Routing Protocol provides an efficient and scalable routing solution for a mobile, ad hoc environment while keeping line and storage overhead (O/H) low. Moreover, the election provides a much needed recovery from landmark failures. 2. Changes + + Major changes from version 04 to version 05: + + - Clarified the relation between LANMAR and a host protocol, which + includes: Removed "Neighbor List" from LANMAR protocol and + description about related operations; Added operation + descriptions about sharing neighbor information with the host + protocol; Retained earlier descriptions about modifications on + making various MANET proactive routing protocols to route within + scope, and TBRPF is added. All these combination efforts are + organized in Section 8. + + - Removed "Landmark Flag" field from LANMAR Update message format. + Instead, "Packet type" field is added. + + - Added "last heard time" field in LMDV. Also added operations + regarding to updating this field and timing out stale entries. + + - Removed the description implying the dependency of LANMAR on the + local topology information, (as that is not the case any more,) + from descriptions of propagating and receiving a LMU. + + - Editorial changes. + Major changes from version 03 to version 04: - Removed "neighbor landmark flag" field from neighbor list. Clarified the operations when a neighbor is lost. - Clarified the processing of landmark update messages, especially, the operations when an infinite distance metric occurs. Operation regarding to an infinite distance metric is also added in data forwarding. @@ -287,23 +304,22 @@ document are to be interpreted as described in RFC 2119 [5]. 4. Protocol Applicability 4.1. Networking Context LANMAR is best suited for large scale mobile ad hoc wireless networks. The landmark scheme on top of a scoped routing algorithm has large advantages in reducing routing update packet size and keeping reasonably accurate routes to remote nodes. - It achieves high data packet delivery ratio. Moreover, the fact - that the route error is blurred by distance obviously reduces the - sensitivity to network size. + Moreover, the fact that the route error is blurred by distance + obviously reduces the sensitivity to network size. LANMAR is also suited for high mobility ad hoc wireless networks. This is because in a mobile environment, a change on a link far away from the source does not necessarily cause a change in the routing table at the source since all the information about remote nodes is summarized by landmarks. 4.2. Protocol Characteristics and Mechanisms * Does the protocol provide support for unidirectional links?(if so, @@ -398,88 +415,93 @@ routing messages from user data packets. 5. Protocol Overview 5.1. Protocol Descriptions As mentioned in Section 1, the landmark concept we adopt here uses the notion of logical subnets in which the members have a commonality of interests and are likely to move as a group. Each logical subnet has one node serving as a landmark of that - subnet. The protocol requires that the landmark of each subnet have - the knowledge of all the members in its group. The LANMAR protocol - also uses a routing scope at each node. The size of the scope is a + subnet. The protocol requires that the landmark of each subnet + have the knowledge of all the members in its group. The protocol + deploys a routing scope at each node. The size of the scope is a parameter measured in hop distance. It is chosen in such a way that if a node is at the center of a subnet, the scope will cover the majority of the subnet members. If the shape of a subnet is likely to be a cycle, the center node's scope will cover all the members of the subnet. If this center node is elected as a landmark, it - fulfills the requirement of the protocol. The elected landmark - uses a destination sequence number to ensure its routing entry - update loop-free. The landmarks are propagated in a - distance vector mechanism. Each node maintains a distance vector - for landmarks of all the subnets. The size of the landmark distance - vector equals to the number of logical subnets and thus landmark - nodes. If a landmark does not locate at the center, there will be - some members drifting off its scope. The landmark will keep a - distance vector for drifters of its group. The distance vectors - for landmarks and drifters are exchanged among neighbors in - periodical routing update packets. + fulfills the requirement of the protocol. - The LANMAR relies on an underlying proactive protocol with the - ability of providing routing within the scope. In this local scoped - routing, each node broadcasts routing information periodically to - its immediate neighbors. In each update packet, the node includes - all the routing table entries within the scope centered at it. + LANMAR is supported by two complementary, cooperating routing + schemes: (a) a local, "myopic" routing scheme (operating within the + limited scope) that maintains routes to nearby destinations and; + (b) a "long haul" distance vector routing scheme that propagates + landmark information. An elected landmark uses a destination + sequence number to ensure its routing entry update loop-free. Thus, + Each node maintains a distance vector for landmarks of all the + subnets. The size of the landmark distance vector equals to the + number of logical subnets and thus landmark nodes. + + When there are members drifting off their landmark's scope, the + landmark will create separate distance vector entries for them. + The distance vectors for landmarks and drifters are exchanged among + neighbors in periodical routing update messages. + + As a result, in-scope destinations can be routed through accurate + routes obtained from local routing table. A data packet directed + to a remote destination initially aims at the landmark of that + remote group; as it gets closer to the landmark, it may + eventually switch to the accurate route to the destination + provided by local host protocol at some nodes within the scope + of the destination. 5.2. Landmark Election Dynamic election/re-election of landmark node is essential for LANMAR to work in a wireless mobile environment. Basically, each node tracks other nodes of its group in its scope and computes weight, e.g. the number of the nodes it has found. At the beginning of the LANMAR, no landmark exists. Protocol LANMAR only uses the host protocol functionality. As host routing computation progresses, one of the nodes will learn (from - the host protocol's routing table) that more than a certain number + the system routing table) that more than a certain number of group members (say, T) are in its scope. It then proclaims itself as a landmark for this group and adds itself to the landmark distance vector. Landmarks broadcast the election weights to the neighbors jointly with the landmark distance vector update packets. When more than one node declares itself as a landmark in the same group, as the landmark information floods out, each node will perform a winner competition procedure. Only one landmark for each group will survive and it will be elected. To avoid flapping - between landmarks (very possible in a mobile situation), we use + between landmarks (very possible in a mobile situation), we may use hysteresis in the replacement of an existing landmark. I.e., the old Landmark is replaced by the new one only if its weight is, say less than 1/2 of the weight of the current election winner. Once ousted, the old leader needs the full weight superiority to be reinstated. - This procedure is carried out periodically in the background (low - overhead, anyway). At steady state, a landmark propagates its - presence to all other nodes like a sink in DSDV. It is extremely - simple and it converges (by definition). In a mobile environment, - an elected landmark may eventually lose its role. The role shifting - is a frequent event. In a transient period, there exist several + This procedure is carried out periodically in the background. + At steady state, a landmark propagates its presence to all other + nodes like a sink in DSDV. It is extremely simple and it + converges (by definition). In a mobile environment, an elected + landmark may eventually lose its role. The role shifting is a + frequent event. In a transient period, there exist several landmarks in a single group. The transient period may be actually the norm at high mobility. This transient behavior can be drastically reduced by using hysteresis. When a landmark dies, its neighbors will detect the silence after - a given timeout. The neighbors of the same group will then take - the responsibilities as landmarks and broadcast new landmark - information. A new round of landmark election then floods over - the entire network. + a given timeout period. A new round of landmark election will + then start from new qualified members and flood over the group. 5.3. Drifters Typically, all members in a logical subnet are within the scope of the landmark, thus the landmark has a route to all members. It may happen, however, that some of the members drift off the scope, for example, a tank in a battalion may become stranded or lost. To keep track of such drifters, i.e., to make the route to them known to the landmark, the following modification to the routing table exchange is necessary. Each node, say i, on the shortest @@ -497,104 +519,96 @@ The occurrences of drifters are dynamic in a mobile network. In order to timely remove the staled drifter information, the time when a node hears a drifter is recorded. A node monitors whether it becomes a drifter periodically and refreshes its occurrence along the path towards the landmark. 6. Protocol Specifications This section discusses the operation of LANMAR routing protocol. - The sending and receiving of landmark updates are in the proactive + The sending and receiving of landmark updates are in a proactive nature. The routing packets are processed separately from ordinary data packets. 6.1. Data Structures Each node has a unique logical identifier defined by a subnet field and a host field. The host field is unique in the subnet and might in fact coincide with the physical address. The logical identifier can also be an IP address when the subnet address logically reflects the grouping of nodes. As LANMAR runs on top of a host routing protocol, it shares the - routing table with the host protocol. Also, LANMAR may maintain - a separate neighbor list, or share it with the host protocol. - In addition, LANMAR keeps a landmark distance vector and a drifter - list. And each node also has a landmark status tuple. In this - draft, we only describe data structures that pertain to LANMAR. + routing table with the host protocol, i.e., both host protocol and + LANMAR contribute their portion to the system routing table. + LANMAR's routing table portion includes a landmark distance vector + (LMDV) and a drifter distance vector (DFDV). -6.1.1. Landmark Status Tuple + In addition to the routing tables, each node has a landmark status + tuple. LANMAR does not maintain a separate neighbor list. Instead, + it interacts with the host protocol for possible table updates + caused by neighbor changes. In this draft, we only describe data + structures that pertain to LANMAR. +6.1.1. Landmark Status Tuple Each node has not only a logical identifier, which basically is its address, but also a landmark status tuple. The tuple includes a flag which indicates whether the node is a landmark or not, a election weight (the number of group members the node detects within its scope) and a sequence number. When a node is elected, the status tuple will be copied to its landmark distance vector. The - sequence number is advanced. There are three fields for a tuple: + sequence number is advanced. These are the three fields for a tuple: - Landmark flag - - Number of group members in its scope + - Weight: Number of group members in its scope - Sequence number 6.1.2. Landmark Distance Vector Landmark distance vector (LMDV) gives the next hop information to all landmarks in the network. Every subnet has an entry in LMDV. The latest route information to the landmark of each subnet is learned when a landmark update message is received. LMDV functions as a part of the routing table. It has the following fields: - Landmark status tuple - Next hop address - Distance + - Last heard time 6.1.3. Drifter List The drifter list (DFDV) of LANMAR provides the next hop information - of the drifters known to the current node. The entries are updated + to the drifters known to the current node. The entries are updated with landmark update message. The latest time a drifter is heard is recorded in DFDV. The DFDV works as a part of routing table. It has the following fields: - Destination drifter address - Next hop address - Distance - Drifter sequence number - Last heard time -6.1.4. Neighbor List - - The neighbor list of LANMAR keeps current neighbor information for - a node. The latest time a neighbor is heard is recorded. The - neighbor list has the following fields: - - Neighbor address - - Last heard time - - If the host routing protocol maintains at least the above neighbor - information, LANMAR does not need to keep this separate neighbor - list. It can share the neighbor information with the host routing - protocol. - 6.2. LANMAR Update Message Format There is only one message type of LANMAR protocol: LANMAR Update (LMU). The messages are periodically exchanged with neighbors. They update the landmark distance vector LMDV and the drifter list DFDV. It is possible that LMDV or DFDV is empty, so no entries of the empty table will be included. The processing of the LMDV and DFDV will be describe separately. The following format does not include the node's identifier because it can be obtained from IP Header. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - | Landmark Flag | N_landmarks | N_drifters | Reserved | + | Type | N_landmarks | N_drifters | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Landmark Address 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Hop Address 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Distance 1 | N_members 1 | Sequence Number 1 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Drifter Address 1 | @@ -595,30 +609,32 @@ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Distance 1 | N_members 1 | Sequence Number 1 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Drifter Address 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Hop Address 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Distance 1 | Drifter Sequence Number 1 | ... : - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6.2.1. Description of the fields - Landmark Flag + Type - The landmark flag of the original sender. + This field indicates the packet type. Currently LANMAR only has + one packet type, i.e., LMU. The field is also needed to + distinguish LANMAR routing control packets from the host + protocol routing packets. N_landmarks The number of entries of the landmark distance vector. N_drifters The number of entries of the drifter list. Reserved @@ -649,100 +665,121 @@ The length of the message is limited to the maximum IP packet size. In that case, multiple packets may be required to broadcast all the entries. 6.2.2. Propagation of LANMAR Update Messages LANMAR update messages (LMUs) are propagated periodically. The frequency could be set according to mobility. Propagation jitters must be used for each message transmission to reduce collisions. - Before sending a LMU, each node checks whether it is a drifter - and does corresponding calculations (see 6.4.1). An existing - drifter node increases its drifter sequence number by 2. If the - node is a landmark, it increases its sequence number by 2 both - to its status tuple and to its entry in LMDV. Then the node - assembles in the LMU the LMDV and DFDV. This message will be - sent after a small random time interval. + Before sending each LMU, a node first performs drifter + operations (described in Section 6.4.1) to check whether + it is a drifter. An existing drifter node increases its drifter + sequence number by 2. Then a node recalculates the current number + of group members within its scope from the system routing table. + The new number is recorded at the election weight field of its + landmark status tuple. And if it is a landmark, the corresponding + entry in the LMDV must be updated with this new weight. For a + landmark node, its sequence number must increase by 2 both in its + status tuple and in its LMDV entry. Then, LMDV will be searched + for stale entries. Operations are given in 6.3.4. DFDV will be + searched for stale entries too. Operations are given in 6.4.3. + Finally, the node assembles in the LMU its LMDV and DFDV. 6.3. Processing Landmark Updates Landmark update information is a part of the LANMAR periodic routing update message. The update information includes sender's LMDV. Landmark update message is used for landmark election and building paths to landmarks. 6.3.1. Originating a Landmark in a Subnet - Every time a node detects a topology change within the scope - (either a neighbor change or a topology change leaned from the - host protocol), it recalculates the number of group members - in its scope. The new number of group members is recorded in - its election weight field. If this number is greater than a - threshold T, the node qualifies as a landmark when one of the - following conditions is met. + Before propagating of each LMU, when a node obtains a new weight, + It will check if this number is greater than a threshold T. The + node qualifies as a landmark when one of the following conditions + is met. (1) it is the only landmark for the group so far; (2) the existing landmark has an infinite distance metric; (3) it wins the election (see 6.3.3) when competing with the existing landmark. When the node becomes a landmark, it increases its sequence number by 2. Its current landmark status tuple will be inserted into the LMDV or the existing landmark is replaced with the new winner. This landmark entry will be broadcast to neighbors with the next update packet. 6.3.2. Receiving Landmark Updates - When a node receives a landmark update message, it compares its - LMDV entries with the entries in the incoming LMDV message for - each subnet. There are three situations to consider: + When a node receives a landmark update message, it recalculates + the current number of group members within its scope from the + system routing table first. The new number is recorded at the + election weight field of its landmark status tuple. And if it is + a landmark, the corresponding entry in the LMDV must be updated + with this new weight. The node compares its LMDV entries with + the entries in the incoming LMDV message for each subnet. + There are three situations to consider: (1) An incoming landmark entry corresponding to a new subnet and its distance metric is less than infinity, the entry will be copied. (2) An incoming entry having the same landmark as an existing one (in node's LMDV), it will be accepted only if one of the following conditions is met. (a) it contains a larger sequence number and the distance metric is less than infinity; (b) it contains a larger sequence number and the distance metric equals to infinity and it happens to be the next hop in the already existing entry; (c) it has the same sequence number with the existing entry, but a smaller distance metric. (3) If an incoming entry contains a different landmark for the same subnet as recorded in LMDV, only the landmark that does not have an infinite distance and is elected through a winner competition algorithm (see 6.3.3) is accepted. The LMDV entry will be kept/updated according to the outcomes of the competition. + During the processing of the current LMU, each inserted or updated + LMDV entry is stamped with receiving time in its "last heard time" + field. After a LMU is processed, the LMDV will be search for stale + entries. Operations are given in 6.3.4. + 6.3.3. Winner Competition When more than one node declares itself as a landmark in the same group, a simple solution is to let the node with the largest number of group members win the election and in case of tie, lowest ID breaks the tie. The other competing nodes defer. - However, this method is likely to cause the oscillation of - landmark roles between nodes. To use hysteresis in replacing an existing landmark, let us assume the competing node's number of members is M, the existing landmark's number of members is N and a factor value S. When M is greater than N*S, then the competing node replaces the existing landmark. Or, when N reduces to a value smaller than a threshold T, then it gives up the landmark role. A tie occurs when M falls within an interval [N*1/S, N*S], then the node with a larger member number wins the election. If a tie occurs again with equal member number, i.e., M equals to N, it is broken using lowest ID. A tie can always be broken using lowest ID as the address is used as ID and it is unique. +6.3.4. Dealing with Stale LMDV Entries + + Each entry in LMDV is time stamped of its last receiving time. + Every time before a LMU message is propagated or after a LMU is + processed, the LMDV table is checked for staled entries. If such + an entry is found, it must be marked an infinite distance metric + and the sequence number be increased by 1. Thus, the lost landmark + entry will overwrite the entries at downstream nodes. A new + elected landmark will replace the lost one. + 6.4. Processing Drifter Updates Drifter update information is a part of the LANMAR periodical routing update message. The update information is the drifter list (DFDV) of the sender. The computation of the DFDV at each node includes checking the node itself to see whether it is a drifter and recording paths to other drifters. 6.4.1. Originating a Drifter Entry @@ -774,131 +811,132 @@ receives the drifter entry. The updated DFDV will be propagated with the next update packet. 6.4.3. Removing a Drifter Entry Each entry in DFDV is time stamped of its last receiving time. Every time before the DFDV is sent or routing by DFDV is needed, the table is checked for staled entries. If such an entry is found, it is removed. -6.5. Processing Neighbor List - -6.5.1. Update Neighbor List - - When a node receives either a landmark update or a host protocol - routing update, the neighbor list is inserted if the update comes - from a new neighbor, or the corresponding neighbor entry is - updated. Current time is recorded with the entry. The - neighbor list is also search at this time for possible lost - neighbors according to the time stamps. If such a neighbor is - found, it is removed from the list. - -6.5.2. Operations Regarding to Lost Neighbors +6.5. Operations Regarding to Lost Neighbors - A lost neighbor will be discovered by checking staled entries in - the neighbor list or by feedback from the MAC layer protocol. - A neighbor loss leads to searches in LMDV and DFDV. If the lost - neighbor happens to be the next hop to a landmark or a drifter, - the corresponding table entry in LMDV is marked an infinite - distance metric, while the corresponding table entry in DFDV is - removed. The infinite distance entries in LMDV will be - propagated with a sequence number increased by 1. Thus, the new - link break information will overwrite the entries at downstream - nodes. As long as the landmark propagates next new update - message with a sequence number increased by 2, new routes are - built up. + When a lost neighbor is reported by the host protocol (the host + protocol may discover by checking staled entries in a neighbor + list or by receiving a feedback from the MAC layer protocol), + LMDV and DFDV will be searched. If the lost neighbor happens + to be the next hop to a landmark, the corresponding table entry + in LMDV must be marked an infinite distance metric and the + sequence number be increased by 1. Thus, the new link break + information will overwrite the entries at downstream nodes. + Till the landmark propagates the next new update message with + a sequence number increased by 2, new routes will build up. + If the lost neighbor happens to be the next hop to a drifter, + the corresponding table entry in DFDV is removed. 7. Data Packet Forwarding - Data packets are relayed hop by hop. The host protocol's - routing table, drifter list and landmark distance vector are - looked up sequentially for the destination entry. If the - destination is within a node's scope, the entry can be found - directly in the routing table and the packet is forwarded to + + Data packets are relayed hop by hop. Each node's system routing + table contains routing entries from the host protocol's + routing table (called local routing table), drifter distance + vector and landmark distance vector. The tables are looked up + sequentially for the destination entry. If the destination is + within a node's scope, the entry can be found directly in the + local routing table and the packet is forwarded to the next hop node. Otherwise, the drifter list DFDV is searched for the destination. If the entry is found, the packet is forwarded using the next hop address from DFDV. If not, the logical subnet field of the destination is retrieved and the LMDV entry of the landmark corresponding to the destination's logical subnet is searched. If the distance metric is not an infinity, the data packet is then routed towards the landmark using the next hop address from LMDV. If all these attempts are failed, the data packet is dropped. When the data packet is routed towards a landmark, it is not necessary for the packet to pass through the landmark. Rather, once the packet gets within the scope of the destination on its way towards the landmark, it is routed to the destination directly. -8. Discussion about Storage and Processing Overhead for Drifters +8. Combining LANMAR with a Host Protocol + Current LANMAR and a host protocol have separate data structures, + separate timers and separate routing messages, resulting in + LANMAR interfering little with the local routing information. + However, they may still have correlation when they work together. + Operations needed for combination are listed and explained in + this section. - The routing storage and processing overhead introduced by the - distance vector extension to handle drifters is typically small - if the fraction of drifting nodes is small. Consider a network - with N nodes and L landmarks, and assume that a fraction F of the - members of each logical subnet have drifted. In the worst case, - the path length from landmark to drifter is the square root of N - (assuming a grid topology). Thus, sqrt(N) is the bound on the - number of extra routing entries required at the nodes along the - path to the drifter. The total number of extra routing entries is - sqrt(N)*L*(F*N/L) where N/L is the average logical group size. - Thus, the extra storage per node is F*sqrt(N). Now, let us assume - that the number of nodes in the scope = # of landmarks = logical - group size = sqrt(N). Then, the basic routing table overhead per - node (excluding drifters) is 3*sqrt(N). Thus, the extra overhead - caused by drifters is F/3. If 20% of the nodes in a group are - outside of the landmark scope, i.e., have drifted, the extra - routing O/H required to keep track of them is only 7%. +8.1. Share Neighbor Information -9. Scoped Routing Operations + As LANMAR does not maintain a neighbor table, it may share + information about neighbors with the host protocol. -9.1. Fisheye State Routing protocol +8.1.1. Inform the Host Protocol about a Neighbor - Fisheye State Routing (FSR) [7][8] is easy to adapt to a host - protocol. A two level Fisheye scope is used when FSR is used - as a host protocol. For nodes within the scope, the updating - is in a certain frequency. But for nodes beyond the scope, - the update frequency is reduced to zero. As a result, - each node maintains accurate routing information for in-scope - nodes. A data packet directed to a remote destination initially - aims at the landmark of that remote group; as it gets closer - to the landmark, it may eventually switch to the accurate - route to the destination provided by FSR at some nodes within - the scope of the destination. + When a node receives a landmark update, LANMAR may inform the host + protocol about the sender in case the sender is a new comer. The + host protocol, if a neighbor table is maintained, may update its + neighbor table accordingly. + +8.1.2. Being Informed about a Lost Neighbor + + LANMAR may accept the notification from a host protocol regarding + to the loss of a neighbor, which leads to a search and possible + updating in LMDV and DFDV (see section 6.5). + +8.2. Scoped Routing Operations + +8.2.1. Destination-sequenced Distance Vector routing protocol -9.2. Destination-sequenced Distance Vector Routing protocol Distance Vector type routing protocols use smaller routing tables (comparing to Link State type) and generate lower routing overhead. Destination-sequenced Distance Vector Routing (DSDV) [3] uses destination sequenced sequence numbers - to prevent the forming of loops. The protocol can also work + to prevent the forming of loops. The protocol can work together with LANMAR. The modifications include containing only the destinations within the local scope in the periodic routing update messages and turning off the triggered updates. -9.3. Optimized Link State Routing protocol +8.2.2. Fisheye State Routing protocol + + Fisheye State Routing (FSR) [7][8] is easy to adapt to a host + protocol. A two level Fisheye scope is used when FSR is used + as a host protocol. For nodes within the scope, the updating + is in a certain frequency. But for nodes beyond the scope, + the update frequency is reduced to zero. As a result, + each node maintains accurate routing information for in-scope + nodes. + +8.2.3. Optimized Link State Routing protocol Optimized Link State Routing (OLSR) [9] provides the facility for scope-limited flooding of messages. The generic message format contains a Time To Live field, which gives the maximum number of hops that a message will travel. Each time a message is retransmitted, the Time To Live field is decreased by 1. When the value of this field is reduced to zero, the massage will not be forwarded any more. OLSR can be one of the underlying protocol of LANMAR. The Time To Live field is set to the scope defined in LANMAR - when a message is originated. The advantage of the combination - is the scalability to both dense and sparse network with - large number of nodes and large terrain size. + when a message is originated. -10. Implementation Status +8.2.4. Topology Broadcast Based on Reverse-Path Forwarding + + Topology Broadcast Based on Reverse-Path Forwarding (TBRPF) [10] + can be adapted to scoped routing operations as easy as that + when constructing the "reportable node set" RN, only the nodes + that are within scope are included. The source tree so built up + at a node will reach only up to a limited hop distance. To achieve + this, the hop distance should be one of the link metrics. + +9. Implementation Status LANMAR version 1 (according to version 3 of the draft, but excluding the drifter operations) has been implemented in Linux and is in use for laboratory experiments. Acknowledgments This work was supported in part by NSF under contract ANI-9814675, by DARPA under contract DAAB07-97-C-D321, and by ONR under contract N00014-01-C-0016. @@ -934,20 +971,24 @@ [8] G. Pei, M. Gerla, and T.-W. Chen, Fisheye State Routing in Mobile Ad Hoc Networks, Proceedings of Workshop on Wireless Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000. [9] P. Jacquet, P. Muhlethaler, A. Qayyum, A. Laouiti, L. Viennot and T. Clausen, Optimized Link State Routing Protocol, Internet Draft, IETF MANET Working Group, draft-ietf-manet-olsr-04.txt, Mar. 2002. + [10] R. G. Ogier, F. L. Templin, B. Bellur, M. G. Lewis, Topology + Broadcast Based on Reverse-Path Forwarding (TBRPF), Internet Draft, + IETF MANET Working Group, draft-ietf-manet-tbrpf-05.txt, Mar. 2002. + Chair's Address The MANET Working Group can be contacted via its current chairs: M. Scott Corson Flarion Technologies, Inc. Bedminster One 135 Route 202/206 South Bedminster, NJ 07921 USA