draft-ietf-manet-lanmar-03.txt   draft-ietf-manet-lanmar-04.txt 
IETF MANET Working Group Mario Gerla IETF MANET Working Group Mario Gerla
INTERNET-DRAFT Xiaoyan Hong INTERNET-DRAFT Xiaoyan Hong
Expiration: June 17, 2002 Li Ma Expiration: December 17, 2002 Li Ma
University of California, Los Angeles University of California, Los Angeles
Guangyu Pei Guangyu Pei
Rockwell Scientific Company Rockwell Scientific Company
December 17, 2001 June 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-03.txt> <draft-ietf-manet-lanmar-04.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.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet-Drafts as reference any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress". material or to cite them other than as work in progress.
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft is a submission to the IETF Mobile Ad Hoc This Internet-Draft is a submission to the IETF Mobile Ad Hoc
Networks (MANET) Working Group. Comments on this draft may be sent Networks (MANET) Working Group. Comments on this draft may be sent
to the Working Group at manet@itd.nrl.navy.mil, or may be sent to the Working Group at manet@itd.nrl.navy.mil, or may be sent
directly to the authors. directly to the authors.
Abstract Abstract
The Landmark Routing Protocol (LANMAR) utilizes the concept of The Landmark Routing Protocol (LANMAR) utilizes the concept of
"landmark" for scalable routing in large, mobile ad hoc networks. landmark for scalable routing in large, mobile ad hoc networks.
It relies on the notion of group mobility: i.e., a logical group It relies on the notion of group mobility: i.e., a logical group
(for example a team of coworkers at a convention) moves in a (for example a team of coworkers at a convention) moves in a
coordinated fashion. The existence of such logical group can be coordinated fashion. The existence of such logical group can be
efficiently reflected in the addressing scheme. It assumes that efficiently reflected in the addressing scheme. It assumes that
an IP like address is used consisting of a group ID (or subnet ID) an IP like address is used consisting of a group ID (or subnet ID)
and a host ID, i.e. <Group ID, Host ID>. A landmark is dynamically and a host ID, i.e. <Group ID, Host ID>. A landmark is dynamically
elected in each group. The route to a landmark is propagated elected in each group. The route to a landmark is propagated
throughout the network using a Distance Vector mechanism. throughout the network using a Distance Vector mechanism.
Separately, each node in the network uses a "scoped" routing Separately, each node in the network uses a scoped routing
algorithm (e.g., FSR) to learn about routes within a given (max algorithm (e.g., FSR) to learn about routes within a given (max
number of hops) scope. To route a packet to a destination outside number of hops) scope. To route a packet to a destination outside
its scope, a node will direct the packet to the landmark its scope, a node will direct the packet to the landmark
corresponding to the group ID of such destination. Once the packet corresponding to the group ID of such destination. Once the packet
approaches the landmark, it will typically be routed directly to approaches the landmark, it will typically be routed directly to
the destination. A solution to nodes outside of the scope of their the destination. A solution to nodes outside of the scope of their
landmark (i.e., drifters) is also addressed in the draft. Thus, landmark (i.e., drifters) is also addressed in the draft. Thus,
by "summarizing" in the corresponding landmarks the routing by summarizing in the corresponding landmarks the routing
information of remote groups of nodes and by using the truncated information of remote groups of nodes and by using the truncated
local routing table, LANMAR dramatically reduces routing table size local routing table, LANMAR dramatically reduces routing table size
and routing update overhead in large networks. The dynamic and routing update overhead in large networks. The dynamic
election of landmarks enables LANMAR to cope with mobile election of landmarks enables LANMAR to cope with mobile
environments. LANMAR is well suited to provide an efficient and environments. LANMAR is well suited to provide an efficient and
scalable routing solution in large, mobile, ad hoc environments in scalable routing solution in large, mobile, ad hoc environments in
which group behavior applies and high mobility renders traditional which group behavior applies and high mobility renders traditional
routing schemes inefficient. routing schemes inefficient.
Contents Contents
skipping to change at page 2, line 44 skipping to change at page 2, line 44
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5
3.2. Specification Language . . . . . . . . . . . . . . . . . 6 3.2. Specification Language . . . . . . . . . . . . . . . . . 6
4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 6 4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 6
4.1. Networking Context . . . . . . . . . . . . . . . . . . . 6 4.1. Networking Context . . . . . . . . . . . . . . . . . . . 6
4.2. Protocol Characteristics and Mechanisms . . . . . . . . 6 4.2. Protocol Characteristics and Mechanisms . . . . . . . . 7
5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8 5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 9
5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8 5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 9
5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9 5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9
5.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10 5.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10
6. Protocol Specifications . . . . . . . . . . . . . . . . . . . 10 6. Protocol Specifications . . . . . . . . . . . . . . . . . . . 11
6.1. Data Structures . . . . . . . . . . . . . . . . . . . 10 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 . . . . . . . . . . . . 11
6.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11 6.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11
6.1.4 Neighbor List . . . . . . . . . . . . . . . . . . 11 6.1.4 Neighbor List . . . . . . . . . . . . . . . . . . 12
6.2. LANMAR Update Message Format . . . . . . . . . . . . 11 6.2. LANMAR Update Message Format . . . . . . . . . . . . 12
6.2.1 Description of the fields . . . . . . . . . . . . 12 6.2.1 Description of the fields . . . . . . . . . . . . 13
6.3. Processing Landmark Updates . . . . . . . . . . . . . . 13 6.2.2 Propagation of LANMAR Update Messages . . . . . . 13
6.3.1 Originating a Landmark in a Subnet . . . . . . . 13 6.3. Processing Landmark Updates . . . . . . . . . . . . . . 14
6.3.2 Receiving Landmark Updates . . . . . . . . . . . 13 6.3.1 Originating a Landmark in a Subnet . . . . . . . 14
6.3.3 Winner Competition . . . . . . . . . . . . . . . 14 6.3.2 Receiving Landmark Updates . . . . . . . . . . . 14
6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14 6.3.3 Winner Competition . . . . . . . . . . . . . . . 15
6.4.1 Originating a Drifter Entry . . . . . . . . . . . 14 6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 15
6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 14 6.4.1 Originating a Drifter Entry . . . . . . . . . . . 15
6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 15 6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 16
6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 15 6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 16
6.6. Processing Lost Neighbor . . . . . . . . . . . . . . . . 15 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 . . . . . . . . . . . . . . . . . . . . 15 7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 16
8. Discussion about Storage and Processing Overhead for Drifters 15 8. Discussion about Storage and Processing Overhead for Drifters 17
9. Scoped Routing Operations . . . . . . . . . . . . . . . . . . 16 9. Scoped Routing Operations . . . . . . . . . . . . . . . . . . 17
9.1. Fisheye State Routing Protocol . . . . . . . . . . . . . 16 9.1. Fisheye State Routing Protocol . . . . . . . . . . . . . 17
9.2. Destination-Sequenced Distance Vector Routing Protocol . 16 9.2. Destination-Sequenced Distance Vector Routing Protocol . 18
9.3. Optimized Link State Routing Protocol . . . . . . . . . 16 9.3. Optimized Link State Routing Protocol . . . . . . . . . 18
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 17 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 18
References . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 18
Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 18 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 19
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
networks [6]. The original scheme required predefined multi-level networks [6]. The original scheme required predefined multi-level
hierarchical addressing. The hierarchical address of each node hierarchical addressing. The hierarchical address of each node
reflects its position within the hierarchy and helps to find a route reflects its position within the hierarchy and helps to find a route
to it. Each node knows the routes to all the nodes within its to it. Each node knows the routes to all the nodes within its
hierarchical partition. Moreover, each node knows the routes to hierarchical partition. Moreover, each node knows the routes to
various "landmarks" at different hierarchical levels. Packet various landmarks at different hierarchical levels. Packet
forwarding is consistent with the landmark hierarchy and the path forwarding is consistent with the landmark hierarchy and the path
is gradually refined from the top level hierarchy to lower levels is gradually refined from the top level hierarchy to lower levels
as a packet approaches its destination. as a packet approaches its destination.
LANMAR borrows the concept of landmark and extends it to the LANMAR borrows the concept of landmark and extends it to the
wireless ad hoc environment. LANMAR scheme does not require wireless ad hoc environment. LANMAR scheme does not require
predefined hierarchical address, but it uses the notion of landmarks predefined hierarchical address, but it uses the notion of landmarks
to keep track of logical subnets in which the members have a to keep track 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
(e.g., brigade in the battlefield, a group of students from same (e.g., brigade in the battlefield, a group of students from same
class and a team of co-workers at a convention). Each such class and a team of co-workers at a convention). Each such
logical group has an elected landmark. For each group, logical group has an elected landmark. For each group,
the underlying "scoped" routing algorithm will provide accurate the underlying scoped routing algorithm will provide accurate
routing information for nodes within scope. The routing routing information for nodes within scope. The routing
update packets are restricted only within the scope. The update packets are restricted only within the scope. The
routing information to remote nodes (nodes outside the node's routing information to remote nodes (nodes outside the node's
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). Extra storage, processing and
line overhead will be incurred for landmark election and drifter line overhead will be incurred for landmark election and drifter
bookkeeping. However, the design of the algorithms provides bookkeeping. However, the design of the algorithms provides
solutions without compromising scalability. For example, the solutions without compromising scalability. For example, the
routing overhead for handling drifters is typically small if the routing overhead for handling drifters is typically small if the
fraction of drifting nodes is small. More analysis is given in fraction of drifting nodes is small. More analysis is given in
Section 8. Section 8.
skipping to change at page 4, line 50 skipping to change at page 5, line 4
LANMAR is that the routing table includes only the nodes within the LANMAR is that the routing table includes only the nodes within the
scope and the landmark nodes. This feature greatly improves scope and the landmark nodes. This feature greatly improves
scalability by reducing routing table size and update traffic O/H. 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 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.
- A separate section describing the operation before sending a
landmark update message is added.
- Reported current implementation status.
- Editorial changes.
Major changes from version 02 to version 03: Major changes from version 02 to version 03:
- A drifter sequence number is used in drifter list to indicate - A drifter sequence number is used in drifter list to indicate
each new occurrence of a drifter. each new occurrence of a drifter.
- Processing of lost neighbors is added. - Processing of lost neighbors is added.
- A separate section describing the modifications made to various - A separate section describing the modifications made to various
proactive protocols. Operations of these protocols will then proactive protocols. Operations of these protocols will then
only perform within a certain hop distances. only perform within a certain hop distances.
- Editorial changes. - Editorial changes.
Major changes from version 01 to version 02: Major changes from version 01 to version 02:
- Update of "Status of This Memo". - Update of Status of This Memo.
Major changes from version 00 to version 01: Major changes from version 00 to version 01:
- A destination sequence number for each landmark is used to - A destination sequence number for each landmark is used to
ensure loop-free updates for a particular landmark. ensure loop-free updates for a particular landmark.
- Landmark updates are propagated in separate messages, instead of - Landmark updates are propagated in separate messages, instead of
being piggybacked on local routing updates. This modification being piggybacked on local routing updates. This modification
decouples landmark routing from the underlying proactive routing decouples landmark routing from the underlying proactive routing
protocol. protocol.
skipping to change at page 5, line 48 skipping to change at page 6, line 21
Nodes that are within the radio transmission range. Nodes that are within the radio transmission range.
scope scope
A network area that is centered at each node and bounded A network area that is centered at each node and bounded
by a certain maximum hop distances. by a certain maximum hop distances.
host protocol host protocol
Also known as local routing protocl, i.e., a proactive Also known as local routing protocol, i.e., a proactive
protocol that works together with the Landmark Routing protocol that works together with the Landmark Routing
Protocol, but only operates within the scope of each node. Protocol, but only operates within the scope of each node.
underlying protocol underlying protocol
This term is used interchangeably with host protocol. This term is used interchangeably with host protocol.
scoped routing protocol scoped routing protocol
A routing protocol that only exchanges routing information A routing protocol that only exchanges routing information
up to a certain hop distance (scope). up to a certain hop distance (scope).
subnet subnet
Logical groups of nodes that present similar motion behavior. Logical groups of nodes that present similar motion behavior.
skipping to change at page 6, line 21 skipping to change at page 6, line 44
subnet subnet
Logical groups of nodes that present similar motion behavior. Logical groups of nodes that present similar motion behavior.
group group
This term is used interchangeably with subnet. This term is used interchangeably with subnet.
3.2. Specification Language 3.2. Specification Language
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT,
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL in this
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 It achieves high data packet delivery ratio. Moreover, the fact
that the route error is blurred by distance obviously reduces the that the route error is blurred by distance 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
skipping to change at page 8, line 42 skipping to change at page 9, line 11
Yes. In fact, the multi-channel can be used to separate Yes. In fact, the multi-channel can be used to separate
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 have
the knowledge of all the members in its group. The LANMAR protocol 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 also uses 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. The elected landmark
uses a destination sequence number to ensure its routing entry uses a destination sequence number to ensure its routing entry
skipping to change at page 9, line 13 skipping to change at page 9, line 34
distance vector mechanism. Each node maintains a distance vector distance vector mechanism. Each node maintains a distance vector
for landmarks of all the subnets. The size of the landmark distance for landmarks of all the subnets. The size of the landmark distance
vector equals to the number of logical subnets and thus landmark vector equals to the number of logical subnets and thus landmark
nodes. If a landmark does not locate at the center, there will be nodes. If a landmark does not locate at the center, there will be
some members drifting off its scope. The landmark will keep a some members drifting off its scope. The landmark will keep a
distance vector for drifters of its group. The distance vectors distance vector for drifters of its group. The distance vectors
for landmarks and drifters are exchanged among neighbors in for landmarks and drifters are exchanged among neighbors in
periodical routing update packets. periodical routing update packets.
The LANMAR relies on an underlying proactive protocol with the The LANMAR relies on an underlying proactive protocol with the
ability of providing "scoped" routing. In the scoped routing, each ability of providing routing within the scope. In this local scoped
node broadcasts routing information periodically to its immediate routing, each node broadcasts routing information periodically to
neighbors. In each update packet, the node includes all the its immediate neighbors. In each update packet, the node includes
routing table entries within the scope centered at it. all the routing table entries within the scope centered at it.
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 host protocol's 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.
skipping to change at page 10, line 13 skipping to change at page 10, line 36
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. The neighbors of the same group will then take
the responsibilities as landmarks and broadcast new landmark the responsibilities as landmarks and broadcast new landmark
information. A new round of landmark election then floods over information. A new round of landmark election then floods over
the entire network. 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
path between a landmark L and a drifter l associated with that path between a landmark L and a drifter l associated with that
landmark keeps a distance vector entry to l. Note that if l is landmark keeps a distance vector entry to l. Note that if l is
within the scope of i, this entry is already included in the within the scope of i, this entry is already included in the
routing table of node i. When i transmits its distance vector to routing table of node i. When i transmits its distance vector to
neighbor, say j, then j will retain the entry to member l only if neighbor, say j, then j will retain the entry to member l only if
d(j,l) is smaller than the scope or d(j,L) is smaller than d(i,L). d(j,l) is smaller than the scope or d(j,L) is smaller than d(i,L).
The latter condition occurs if j is on the shortest path from i The latter condition occurs if j is on the shortest path from i
(and therefore from l) to L. This way, a path is maintained from (and therefore from l) to L. This way, a path is maintained from
skipping to change at page 10, line 45 skipping to change at page 11, line 15
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 the 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 can identifier can also be an IP address when the subnet address
logically group the nodes. Moreover, each node keeps a landmark logically reflects the grouping of nodes.
status tuple. As LANMAR runs on top of a host routing protocol,
it shares the underlying routing table structures. LANMAR As LANMAR runs on top of a host routing protocol, it shares the
maintains a neighbor list and shares it with the host protocol. routing table with the host protocol. Also, LANMAR may maintain
In addition, LANMAR keeps a drifter list and a landmark distance a separate neighbor list, or share it with the host protocol.
vector. 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.
6.1.1. Landmark Status Tuple 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. There are three fields for a tuple:
- Landmark flag - Landmark flag
- Number of group members in its scope - Number of group members in its scope
- Sequence number - Sequence number
skipping to change at page 11, line 48 skipping to change at page 12, line 20
- Distance - Distance
- Drifter sequence number - Drifter sequence number
- Last heard time - Last heard time
6.1.4. Neighbor List 6.1.4. Neighbor List
The neighbor list of LANMAR keeps current neighbor information for The neighbor list of LANMAR keeps current neighbor information for
a node. The latest time a neighbor is heard is recorded. The a node. The latest time a neighbor is heard is recorded. The
neighbor list has the following fields: neighbor list has the following fields:
- Neighbor address - Neighbor address
- Neighbor landmark flag
- Last heard time - 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. The messages are There is only one message type of LANMAR protocol: LANMAR Update
periodically exchanged with neighbors. They update the landmark (LMU). The messages are periodically exchanged with neighbors.
distance vector LMDV and the drifter list DFDV. The processing of 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 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 | | Landmark Flag | N_landmarks | N_drifters | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Landmark Address 1 | | Landmark Address 1 |
skipping to change at page 13, line 23 skipping to change at page 13, line 53
Next Hop Address 1 and Distance 1 are the next hop and distance Next Hop Address 1 and Distance 1 are the next hop and distance
to the Drifter Address 1. to the Drifter Address 1.
These fields are repeated N_drifters times for each entry in These fields are repeated N_drifters times for each entry in
the drifter list. the drifter list.
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
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.
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 neighbor change, it recalculates the Every time a node detects a topology change within the scope
number of group members in its scope. The new number of group (either a neighbor change or a topology change leaned from the
members is recorded in its election weight field. If this host protocol), it recalculates the number of group members
number is greater than a threshold T, the node qualifies as a in its scope. The new number of group members is recorded in
landmark only when it is the only landmark for the group so far, its election weight field. If this number is greater than a
or it wins the election when competing with the existing landmark. threshold T, the node qualifies as a landmark when one of the
When it becomes a landmark, it increases its sequence number by 2. following conditions is met.
Its current landmark status tuple will be inserted into the LMDV (1) it is the only landmark for the group so far;
or the existing landmark is replaced with the new winner. The (2) the existing landmark has an infinite distance metric;
landmark entry will be broadcast to neighbors with the next update (3) it wins the election (see 6.3.3) when competing with the
packet. 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 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 compares its
LMDV entries with the incoming LMDV updates for each subnet. LMDV entries with the entries in the incoming LMDV message for
A landmark update corresponding to a new subnet will be copied. each subnet. There are three situations to consider:
An update having the same landmark as already given (in node's LMDV) (1) An incoming landmark entry corresponding to a new subnet
will be accepted only if it contains a larger sequence number. and its distance metric is less than infinity, the entry
If an update contains a different landmark for the same subnet as will be copied.
recorded in LMDV, only one landmark will be elected through a (2) An incoming entry having the same landmark as an existing
winner competition algorithm. LMDV will be updated according to one (in node's LMDV), it will be accepted only if one of
the outcomes of the competition. 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.
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 However, this method is likely to cause the oscillation of
landmark roles between nodes. 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 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.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
skipping to change at page 14, line 43 skipping to change at page 15, line 51
6.4.1. Originating a Drifter Entry 6.4.1. Originating a Drifter Entry
By checking the distance to the landmark of its group, each node By checking the distance to the landmark of its group, each node
easily knows whether it has become a drifter. If the distance is easily knows whether it has become a drifter. If the distance is
larger than the scope, the node will put itself into its drifter larger than the scope, the node will put itself into its drifter
list. This drifter information will be sent back to the landmark list. This drifter information will be sent back to the landmark
hop by hop along the shortest path to it which can be learned from hop by hop along the shortest path to it which can be learned from
the LMDV. For each drifter, only the node on its shortest path the LMDV. For each drifter, only the node on its shortest path
to the landmark needs to receive its information, so before the to the landmark needs to receive its information, so before the
entry is broadcast, the next hop to landmark is attached with entry is broadcast, the drifter or the intermediate nodes
its entry. Each drifter maintains a drifter sequence number. look for the next hop to drifter's landmark in their LMDVs first.
Then the next hop is included in LMU within the drifter entry.
Each drifter also maintains a drifter sequence number.
Each time a node finds itself a drifter, the sequence number Each time a node finds itself a drifter, the sequence number
will be increased by 2. The DFDV will be propagated with the will be increased by 2. The DFDV will be propagated with the
next update packet. next update packet.
6.4.2. Receiving Drifter Updates 6.4.2. Receiving Drifter Updates
Upon receiving an update packet, the DFDV part is retrieved and Upon receiving an update packet, the DFDV part is retrieved and
processed. If an entry of incoming DFDV indicates that the current processed. If an entry of incoming DFDV indicates that the current
node is its next hop to the landmark, i.e., the current node is on node is its next hop to the landmark, i.e., the current node is on
the drifter's shortest path to the landmark, the current node will the drifter's shortest path to the landmark, the current node will
insert or update its drifter list. The receiving time is stamped insert or update its drifter list. The receiving time is stamped
in the DFDV. The node sending the update packet is recorded as the in the DFDV. The node sending the update packet is recorded in
next hop to the drifter. The reverse path to the drifter is thus DFDV as the next hop to the drifter. The reverse path to the
built up. The procedure ends when the landmark receives the drifter is thus built up. The procedure ends when the landmark
drifter entry. The updated DFDV will be propagated with the next receives the drifter entry. The updated DFDV will be propagated
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. Processing Neighbor List
6.5.1. Update Neighbor List
When a node receives either a landmark update or a host protocol When a node receives either a landmark update or a host protocol
routing update, the neighbor list is inserted if the update comes routing update, the neighbor list is inserted if the update comes
from a new neighbor, or the corresponding neighbor entry is from a new neighbor, or the corresponding neighbor entry is
updated. Current time is recorded with the entry. The updated. Current time is recorded with the entry. The
neighbor list is also search at this time for possible lost neighbor list is also search at this time for possible lost
neighbors according to the time stamps. If such a neighbor is neighbors according to the time stamps. If such a neighbor is
found, it is removed from the list. found, it is removed from the list.
6.6. Processing Lost Neighbor 6.5.2. Operations Regarding to Lost Neighbors
A lost neighbor will be discovered by checking staled entries in A lost neighbor will be discovered by checking staled entries in
the neighbor list or by feedback from the MAC layer protocol. the neighbor list or by feedback from the MAC layer protocol.
A neighbor loss leads to searches in LMDV and DFDV. If the lost 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, neighbor happens to be the next hop to a landmark or a drifter,
the corresponding table entry is removed. 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.
7. Data Packet Forwarding 7. Data Packet Forwarding
Data packets are relayed hop by hop. The host protocol's
Data packets are relayed hop by hop. The host protocol routing routing table, drifter list and landmark distance vector are
table, drifter list and landmark distance vector are looked up looked up sequentially for the destination entry. If the
sequentially for the destination entry. If the destination is destination is within a node's scope, the entry can be found
within a node's scope, the entry can be found directly in the directly in the routing table and the packet is forwarded to
routing table and the packet is forwarded to the next hop node. the next hop node. Otherwise, the drifter list DFDV is
Otherwise, the drifter list DFDV is searched for the destination. searched for the destination. If the entry is found, the
If the entry is found, the packet is forwarded using the next hop packet is forwarded using the next hop address from DFDV.
address from DFDV. If not, the logical subnet field of the If not, the logical subnet field of the destination is retrieved
destination is retrieved and the LMDV entry of the landmark and the LMDV entry of the landmark corresponding to the
corresponding to the destination's logical subnet is searched. destination's logical subnet is searched. If the distance
The data packet is then routed towards the landmark using the next metric is not an infinity, the data packet is then routed
hop address from LMDV. The packet, however, is not necessary to towards the landmark using the next hop address from LMDV.
pass through the landmark. Rather, once the packet gets within the If all these attempts are failed, the data packet is dropped.
scope of the destination on its way towards the landmark, it is When the data packet is routed towards a landmark, it is not
routed to the destination directly. 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. Discussion about Storage and Processing Overhead for Drifters
The routing storage and processing overhead introduced by the The routing storage and processing overhead introduced by the
distance vector extension to handle drifters is typically small distance vector extension to handle drifters is typically small
if the fraction of drifting nodes is small. Consider a network 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 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, members of each logical subnet have drifted. In the worst case,
the path length from landmark to drifter is the square root of N 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 (assuming a grid topology). Thus, sqrt(N) is the bound on the
number of extra routing entries required at the nodes along the number of extra routing entries required at the nodes along the
path to the drifter. The total number of extra routing entries is 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. sqrt(N)*L*(F*N/L) where N/L is the average logical group size.
skipping to change at page 16, line 28 skipping to change at page 17, line 50
caused by drifters is F/3. If 20% of the nodes in a group are 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 outside of the landmark scope, i.e., have drifted, the extra
routing O/H required to keep track of them is only 7%. routing O/H required to keep track of them is only 7%.
9. Scoped Routing Operations 9. Scoped Routing Operations
9.1. Fisheye State Routing protocol 9.1. Fisheye State Routing protocol
Fisheye State Routing (FSR) [7][8] is easy to adapt to a host 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 protocol. A two level Fisheye scope is used when FSR is used
for host protocol. For nodes within the scope, the updating as a host protocol. For nodes within the scope, the updating
is in a certain frequency. But for nodes beyond the scope, is in a certain frequency. But for nodes beyond the scope,
the update frequency is reduced to zero; Only the update the update frequency is reduced to zero. As a result,
frequency of the landmark nodes remains unaltered. As a result,
each node maintains accurate routing information for in-scope each node maintains accurate routing information for in-scope
nodes and keep routing directions to the landmark nodes for nodes. A data packet directed to a remote destination initially
out-scope nodes, or say, for remote groups. A packet directed aims at the landmark of that remote group; as it gets closer
to a remote destination initially aims at the landmark of that to the landmark, it may eventually switch to the accurate
remote group; as it gets closer to the landmark, it may route to the destination provided by FSR at some nodes within
eventually switch to the accurate route to the destination the scope of the destination.
provided by in-scope nodes of the destination.
9.2. 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 routing tables (comparing to Link State type) and generate lower
overhead. Destination-sequenced Distance Vector Routing (DSDV) [3] routing overhead. Destination-sequenced Distance Vector
uses destination sequenced sequence numbers to prevent the Routing (DSDV) [3] uses destination sequenced sequence numbers
forming of loops. The protocol can also work together with to prevent the forming of loops. The protocol can also work
LANMAR. The modifications include containing only the together with LANMAR. The modifications include containing
destinations within the local scope in the periodic routing only the destinations within the local scope in the periodic
update messages and turning off the triggered updates. routing update messages and turning off the triggered updates.
9.3. Optimized Link State Routing protocol 9.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. The advantage of the combination
is the scalability to both dense and sparse network with is the scalability to both dense and sparse network with
large number of nodes and large terrain size. large number of nodes and large terrain size.
10. 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 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.
References References
[1] G. Pei, M. Gerla and X. Hong, "LANMAR: Landmark Routing for [1] G. Pei, M. Gerla and X. Hong, LANMAR: Landmark Routing for
Large Scale Wireless Ad Hoc Networks with Group Mobility", Large Scale Wireless Ad Hoc Networks with Group Mobility,
Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000. Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000.
[2] M. Gerla, X. Hong, G. Pei, "Landmark Routing for Large Ad Hoc [2] M. Gerla, X. Hong, G. Pei, Landmark Routing for Large Ad Hoc
Wireless Networks", Proceedings of IEEE GLOBECOM 2000, Wireless Networks, Proceedings of IEEE GLOBECOM 2000,
San Francisco, CA, Nov. 2000. San Francisco, CA, Nov. 2000.
[3] C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination- [3] C.E. Perkins and P. Bhagwat, Highly Dynamic Destination-
Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,
In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994, In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994,
pp. 234-244. pp. 234-244.
[4] UCLA Wireless Adaptive Mobility (WAM) Laboratory. [4] UCLA Wireless Adaptive Mobility (WAM) Laboratory.
http://www.cs.ucla.edu/NRL/wireless http://www.cs.ucla.edu/NRL/wireless
[5] S. Bradner. Key words for use in RFCs to Indicate [5] S. Bradner. Key words for use in RFCs to Indicate
Requirement Levels. RFC 2119, March 1997. Requirement Levels. RFC 2119, March 1997.
[6] P. F. Tsuchiya, "The Landmark Hierarchy: a new hierarchy for [6] P. F. Tsuchiya, The Landmark Hierarchy: a new hierarchy for
routing in very large networks", Computer Communication Review, routing in very large networks, Computer Communication Review,
vol.18, no.4, Aug. 1988, pp. 35-42. vol.18, no.4, Aug. 1988, pp. 35-42.
[7] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing: [7] G. Pei, M. Gerla, and T.-W. Chen, Fisheye State Routing:
A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of A Routing Scheme for Ad Hoc Wireless Networks, Proceedings of
ICC 2000, New Orleans, LA, Jun. 2000. ICC 2000, New Orleans, LA, Jun. 2000.
[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. 2001. 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
 End of changes. 

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