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

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/