draft-ietf-manet-lanmar-02.txt		draft-ietf-manet-lanmar-03.txt
	IETF MANET Working Group Mario Gerla		IETF MANET Working Group Mario Gerla
	INTERNET-DRAFT Xiaoyan Hong		INTERNET-DRAFT Xiaoyan Hong
	Expiration: November 17, 2001 Li Ma		Expiration: June 17, 2002 Li Ma
	University of California, Los Angeles		University of California, Los Angeles
	Guangyu Pei		Guangyu Pei
	Rockwell Science Center		Rockwell Scientific Company
	May 17, 2001		December 17, 2001
	Landmark Routing Protocol (LANMAR) for Large Scale Ad Hoc Networks		Landmark Routing Protocol (LANMAR) for Large Scale Ad Hoc Networks
	<draft-ietf-manet-lanmar-02.txt>		<draft-ietf-manet-lanmar-03.txt>
	Status of This Memo		Status of This Memo
	This document is an Internet-Draft and is in full conformance with		This document is an Internet-Draft and is subject to all provisions
	all provisions of Section 10 of RFC 2026 except that the right to		of Section 10 of RFC2026.
	produce derivative works is not granted.
	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".
	skipping to change at page 2, line 15		skipping to change at page 2, line 15
	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
	is within the scope of the landmark, it will typically be routed		approaches the landmark, it will typically be routed directly to
	directly to the destination. Remote groups of nodes are		the destination. A solution to nodes outside of the scope of their
	"summarized" by the corresponding landmarks. The solution to		landmark (i.e., drifters) is also addressed in the draft. Thus,
	drifters (i.e., nodes outside of the scope of their landmark) is		by "summarizing" in the corresponding landmarks the routing
	also handled by LANMAR. Landmark dynamic election enables LANMAR		information of remote groups of nodes and by using the truncated
	to cope with mobile environments. Thus, by using the truncated		local routing table, LANMAR dramatically reduces routing table size
	local routing table and the "summarized" landmark distance vector,		and routing update overhead in large networks. The dynamic
	LANMAR dramatically reduces routing table size and update overhead		election of landmarks enables LANMAR to cope with mobile
	in large nets. 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
	Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . 1		Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . 1
	Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1		Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
	2. Changes ....................................................... 5		2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
	3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5		3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5
	3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5		3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5
	3.2. Specification Language . . . . . . . . . . . . . . . . . 5		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 . . . . . . . . 6
	5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8		5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8
	5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8		5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8
	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 . . . . . . . . . . . . . . . . . . . 10
	6.1. Data Structures . . . . . . . . . . . . . . . . . . . 11		6.1. Data Structures . . . . . . . . . . . . . . . . . . . 10
	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 . . . . . . . . . . . . . . . . . . 12		6.1.4 Neighbor List . . . . . . . . . . . . . . . . . . 11
	6.2. LANMAR Update Message Format . . . . . . . . . . . . 12		6.2. LANMAR Update Message Format . . . . . . . . . . . . 11
	6.2.1 Description of the fields . . . . . . . . . . . . 12		6.2.1 Description of the fields . . . . . . . . . . . . 12
	6.3. Processing Landmark Updates . . . . . . . . . . . . . . 13		6.3. Processing Landmark Updates . . . . . . . . . . . . . . 13
	6.3.1 Originating a Landmark in a Subnet . . . . . . . 13		6.3.1 Originating a Landmark in a Subnet . . . . . . . 13
	6.3.2 Receiving Landmark Updates . . . . . . . . . . . 14		6.3.2 Receiving Landmark Updates . . . . . . . . . . . 13
	6.3.3 Winner Competition . . . . . . . . . . . . . . . 14		6.3.3 Winner Competition . . . . . . . . . . . . . . . 14
	6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14		6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14
	6.4.1 Originating a Drifter Entry . . . . . . . . . . . 15		6.4.1 Originating a Drifter Entry . . . . . . . . . . . 14
	6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 15		6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 14
	6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 15		6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 15
	6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 15		6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 15
			6.6. Processing Lost Neighbor . . . . . . . . . . . . . . . . 15
	7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15		7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15
	8. Discussion about Storage and Processing Overhead for Drifters 16		8. Discussion about Storage and Processing Overhead for Drifters 15
	Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 16		9. Scoped Routing Operations . . . . . . . . . . . . . . . . . . 16
			9.1. Fisheye State Routing Protocol . . . . . . . . . . . . . 16
			9.2. Destination-Sequenced Distance Vector Routing Protocol . 16
			9.3. Optimized Link State Routing Protocol . . . . . . . . . 16
	References . . . . . . . . . . . . . . . . . . . . . . . . . . . 16		Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 17
	Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17		References . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
			Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 18
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18
	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 13		skipping to change at page 4, line 10
	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,
	underlying "scoped" routing algorithm will provide a one-level		the underlying "scoped" routing algorithm will provide accurate
	scope. The routing update packets are restricted only within the		routing information for nodes within scope. The routing
	scope. Accurate routing information for nodes within scope is		update packets are restricted only within the scope. The
	maintained. The routing information to remote nodes (nodes outside		routing information to remote nodes (nodes outside the node's
	the node's scope) is "summarized" by the corresponding landmarks.		scope) is "summarized" by the corresponding landmarks. Thus,
	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 drifters (Nodes that are outside the fisheye scopes of the		for nodes that are outside the scopes of the landmarks of
	landmarks of their logical groups). 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.
	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. Fisheye State Routing Protocol (FSR) [7,8] is
	such a protocol that supports LANMAR. In FSR, the link state		such a protocol that supports LANMAR. In FSR, the link state
	protocol is used within the scope. The fisheye scope		protocol is used within the scope. The scope technique
	technique can also be applied to a distance vector type protocol,		can also be applied to a distance vector type protocol,
	such as DSDV [3], in which the hop distance can be used to		such as DSDV [3], in which the hop distance can be used to
	bind the scope for routing message updating. The main advantage of		limit the scope of routing message updating. The main advantage of
	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 02 to version 03:
			- A drifter sequence number is used in drifter list to indicate
			each new occurrence of a drifter.
			- Processing of lost neighbors is added.
			- A separate section describing the modifications made to various
			proactive protocols. Operations of these protocols will then
			only perform within a certain hop distances.
			- Editorial changes.
			Major changes from version 01 to version 02:
			- 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 33		skipping to change at page 5, line 43
	node		node
	A MANET router that implements Landmark Routing Protocol.		A MANET router that implements Landmark Routing Protocol.
	neighbor		neighbor
	Nodes that are within the radio transmission range.		Nodes that are within the radio transmission range.
	scope		scope
	A zone that is bounded by hop distances.		A network area that is centered at each node and bounded
			by a certain maximum hop distances.
	host protocol		host protocol
	A proactive protocol underlies the Landmark Routing Protocol.		Also known as local routing protocl, i.e., a proactive
			protocol that works together with the Landmark Routing
			Protocol, but only operates within the scope of each node.
			underlying protocol
			This term is used interchangeably with host protocol.
			scoped routing protocol
			A routing protocol that only exchanges routing information
			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.
	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 "scoped" routing algorithm		networks. The landmark scheme on top of a "scoped" routing
	has large advantages in reducing routing update packet size and		algorithm has large advantages in reducing routing update packet
	keeping progressive accurate routes to remote nodes. It achieves		size and keeping reasonably accurate routes to remote nodes.
	high data packet delivery ratio. Moreover, the fact that the route		It achieves high data packet delivery ratio. Moreover, the fact
	error is blurred by distance obviously reduces the sensitivity to		that the route error is blurred by distance obviously reduces the
	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 mobility 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 and that 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,
	how?)		how?)
	No.		No.
	* Does the protocol require the use of tunneling? (if so, how?)		* Does the protocol require the use of tunneling? (if so, how?)
	skipping to change at page 8, line 32		skipping to change at page 8, line 46
	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 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
	update is loop-free. The landmarks are propagated in a		update loop-free. The landmarks are propagated in a
	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 "scoped" routing. In the scoped routing, each
	node broadcasts routing information periodically to its immediate		node broadcasts routing information periodically to its immediate
	neighbors. In each update packet, the node sends routing table		neighbors. In each update packet, the node includes all the
	entries within its scope. The host routing protocol uses sequence		routing table entries within the scope centered at it.
	numbers for routing entries. Each node advances its sequence
	number before sending an update packet. Through the exchange
	process, the table entries with larger sequence numbers replace
	the ones with smaller sequence numbers.
	Let's take, for example, the FSR as our 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; Only the update frequency of the landmark nodes remains
	unaltered. As a result, each node maintains accurate routing
	information for in-scope nodes and keep routing directions to the
	landmark nodes for out-scope nodes, or say, for remote groups.
	A 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 in-scope nodes 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 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 update packets.		the neighbors jointly with the landmark distance vector update
			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 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
	skipping to change at page 10, line 42		skipping to change at page 10, line 32
	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
	the landmark to each of its members, including drifters. The		the landmark to each of its members, including drifters. The
	procedure starts from l, at the time when a node finds it becomes		procedure starts from l, at the time when a node finds it becomes
	a drifter. It informs the landmark hop by hop about its presence.		a drifter. It informs the landmark hop by hop about its presence.
	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.		when a node hears a drifter is recorded. A node monitors whether
			it becomes a drifter periodically and refreshes its occurrence
			along the path towards the landmark.
	6. Protocol Specifications		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
	skipping to change at page 11, line 52		skipping to change at page 11, line 39
	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		of 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
	- 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		- Neighbor landmark flag
	- Last heard time		- Last heard time
	skipping to change at page 12, line 40		skipping to change at page 12, line 25
	| 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 |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Next Hop Address 1 |		| Next Hop Address 1 |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Distance 1 | ... :		| Distance 1 | Drifter Sequence Number 1 | ... :
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	: . . . |		: . . . |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	6.2.1. Description of the fields		6.2.1. Description of the fields
	Landmark Flag		Landmark Flag
	The landmark flag of the sending node.		The landmark flag of the original sender.
	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 13, line 29		skipping to change at page 13, line 9
	The first entry in the landmark distance vector.		The first entry in the landmark distance vector.
	Landmark Address 1, N_members 1 and Sequence Number 1 are the		Landmark Address 1, N_members 1 and Sequence Number 1 are the
	status tuple of the destination landmark.		status tuple of the destination landmark.
	Next Hop Address 1 and Distance 1 is the next hop and distance		Next Hop Address 1 and Distance 1 is the next hop and distance
	to the landmark.		to the landmark.
	These fields are repeated N_landmarks times for each entry in		These fields are repeated N_landmarks times for each entry in
	landmark distance vector.		landmark distance vector.
	Drifter Address 1, Next Hop Address 1 and Distance 1		Drifter Address 1, Next Hop Address 1, Distance 1 and
			Drifter Sequence Number 1
	The first entry in the drifter list.		The first entry in the drifter list.
	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
	skipping to change at page 14, line 9		skipping to change at page 13, line 39
	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 neighbor change, it recalculates the
	number of group members in its scope. The new number of group		number of group members in its scope. The new number of group
	members is recorded in its election weight field. If this		members is recorded in its election weight field. If this
	number is greater than a threshold T, the node qualifies as a		number is greater than a threshold T, the node qualifies as a
	landmark only when it is the only landmark for the group so far,		landmark only when it is the only landmark for the group so far,
	or it wins the election when competing with the existing landmark.		or it wins the election when competing with the existing landmark.
	When it becomes a landmark, it increases its sequence number by 2.		When it becomes a landmark, it increases its sequence number by 2.
	The old landmark entry is replaced with the new winner. The		Its current landmark status tuple will be inserted into the LMDV
			or the existing landmark is replaced with the new winner. The
	landmark entry will be broadcast to neighbors with the next update		landmark entry will be broadcast to neighbors with the next update
	packet. Every time before a landmark sends updates, it increases		packet.
	its sequence number and copies it to LMDV.
	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 incoming LMDV updates for each subnet.
	A landmark update corresponding to a new subnet will be copied.		A landmark update corresponding to a new subnet will be copied.
	An update having the same landmark as already given (in node's LMDV)		An update having the same landmark as already given (in node's LMDV)
	will be accepted only if it contains a larger sequence number.		will be accepted only if it contains a larger sequence number.
	If an update contains a different landmark for the same subnet as		If an update contains a different landmark for the same subnet as
	recorded in LMDV, only one landmark will be elected through a		recorded in LMDV, only one landmark will be elected through a
	skipping to change at page 15, line 17		skipping to change at page 14, line 44
	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 next hop to landmark is attached with
	its entry. The DFDV will be propagated with the next update packet.		its entry. Each drifter maintains a drifter 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
			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 as the
	next hop to the drifter. The reverse path to the drifter is thus		next hop to the drifter. The reverse path to the drifter is thus
	skipping to change at page 15, line 49		skipping to change at page 15, line 26
	6.5. Processing Neighbor List		6.5. Processing 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
			A lost neighbor will be discovered by checking staled entries in
			the neighbor list or by feedback from the MAC layer protocol.
			A neighbor loss leads to searches in LMDV and DFDV. If the lost
			neighbor happens to be the next hop to a landmark or a drifter,
			the corresponding table entry is removed.
	7. Data Packet Forwarding		7. Data Packet Forwarding
	Data packets are relayed hop by hop. The host protocol routing		Data packets are relayed hop by hop. The host protocol routing
	table, drifter list and landmark distance vector are looked up		table, drifter list and landmark distance vector are looked up
	sequentially for the destination entry. If the destination is		sequentially for the destination entry. If the destination is
	within a node's scope, the entry can be found directly in the		within a node's scope, the entry can be found directly in the
	routing table and the packet is forwarded to the next hop node.		routing table and the packet is forwarded to the next hop node.
	Otherwise, the drifter list DFDV is searched for the destination.		Otherwise, the drifter list DFDV is searched for the destination.
	If the entry is found, the packet is forwarded using the next hop		If the entry is found, the packet is forwarded using the next hop
	address from DFDV. If not, the logical subnet field of the		address from DFDV. If not, the logical subnet field of the
	skipping to change at page 16, line 39		skipping to change at page 16, line 22
	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.
	Thus, the extra storage per node is F*sqrt(N). Now, let us assume		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		that the number of nodes in the scope = # of landmarks = logical
	group size = sqrt(N). Then, the basic routing table overhead per		group size = sqrt(N). Then, the basic routing table overhead per
	node (excluding drifters) is 3*sqrt(N). Thus, the extra overhead		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		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.1. 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
			for 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; Only the update
			frequency of the landmark nodes remains unaltered. As a result,
			each node maintains accurate routing information for in-scope
			nodes and keep routing directions to the landmark nodes for
			out-scope nodes, or say, for remote groups. A 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 in-scope nodes of the destination.
			9.2. Destination-sequenced Distance Vector Routing protocol
			Distance Vector type routing protocols use smaller routing
			tables (comparing to Link State type) and generate lower routing
			overhead. Destination-sequenced Distance Vector Routing (DSDV) [3]
			uses destination sequenced sequence numbers to prevent the
			forming of loops. The protocol can also work together with
			LANMAR. The modifications include containing only the
			destinations within the local scope in the periodic routing
			update messages and turning off the triggered updates.
			9.3. Optimized Link State Routing protocol
			Optimized Link State Routing (OLSR) [9] provides the facility
			for scope-limited flooding of messages. The generic message
			format contains a "Time To Live" field, which gives the maximum
			number of hops that a message will travel. Each time a message
			is retransmitted, the "Time To Live" field is decreased by 1.
			When the value of this field is reduced to zero, the massage
			will not be forwarded any more.
			OLSR can be one of the underlying protocol of LANMAR. The
			"Time To Live" field is set to the scope defined in LANMAR
			when a message is originated. The advantage of the combination
			is the scalability to both dense and sparse network with
			large number of nodes and large terrain size.
	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",
	skipping to change at page 17, line 32		skipping to change at page 18, line 5
	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
			and T. Clausen, "Optimized Link State Routing Protocol", Internet
			Draft, IETF MANET Working Group, draft-ietf-manet-olsr-04.txt,
			Mar. 2001.
	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
	Institute for Systems Research		Flarion Technologies, Inc.
	University of Maryland		Bedminster One
	College Park, MD 20742		135 Route 202/206 South
			Bedminster, NJ 07921
	USA		USA
	Phone: +1 301 405-6630		Phone: +1 908 947-7033
	Email: corson@isr.umd.edu		Email: corson@flarion.com
	Joseph Macker		Joseph Macker
	Information Technology Division		Information Technology Division
	Naval Research Laboratory		Naval Research Laboratory
	Washington, DC 20375		Washington, DC 20375
	USA		USA
	Phone: +1 202 767-2001		Phone: +1 202 767-2001
	Email: macker@itd.nrl.navy.mil		Email: macker@itd.nrl.navy.mil
	Authors' Addresses		Authors' Addresses
	Questions about this document can also be directed to the authors:		Questions about this document can also be directed to the authors:
	Mario Gerla		Mario Gerla
	3732F Boelter Hall		3732F Boelter Hall
	Computer Science Department		Computer Science Department
	skipping to change at page 18, line 45		skipping to change at page 19, line 20
	Computer Science Department		Computer Science Department
	University of California		University of California
	Los Angeles, CA 90095-1596		Los Angeles, CA 90095-1596
	USA		USA
	Phone: +1 310 825-1888		Phone: +1 310 825-1888
	Fax: +1 310 825-7578		Fax: +1 310 825-7578
	Email: mary@cs.ucla.edu		Email: mary@cs.ucla.edu
	Guangyu Pei		Guangyu Pei
	Rockwell Science Center		Rockwell Scientific Company
	1049 Camino Dos Rios		1049 Camino Dos Rios
	P.O. Box 1085		P.O. Box 1085
	Thousand Oaks, CA 91358-0085		Thousand Oaks, CA 91358-0085
	USA		USA
	Phone: +1 805 373-4639		Phone: +1 805 373-4639
	Fax: +1 805 373-4383		Fax: +1 805 373-4383
	Email: gpei@rsc.rockwell.com		Email: gpei@rwsc.com
End of changes.
This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/