draft-ietf-manet-lanmar-00.txt		draft-ietf-manet-lanmar-01.txt
	IETF MANET Working Group Mario Gerla		IETF MANET Working Group Mario Gerla
	INTERNET-DRAFT Xiaoyan Hong		INTERNET-DRAFT Xiaoyan Hong
	Expiration: May 17, 2001 Li Ma		Expiration: November 17, 2001 Li Ma
	University of California, Los Angeles		University of California, Los Angeles
	Guangyu Pei		Guangyu Pei
	Rockwell Science Center		Rockwell Science Center
	November 17, 2000		May 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-00.txt>		<draft-ietf-manet-lanmar-01.txt>
	Status of This Memo		Status of This Memo
	This document is an Internet-Draft and is NOT offered in accordance		This document is an Internet-Draft and is NOT offered in accordance
	with Section 10 of RFC2026, and the author does not provide the IETF		with Section 10 of RFC2026, and the author does not provide the IETF
	with any rights other than to publish as an Internet-Draft. This		with any rights other than to publish as an Internet-Draft. This
	document is a submission to the Mobile Ad-hoc Networks (manet)		document is a submission to the Mobile Ad-hoc Networks (manet)
	Working Group of the Internet Engineering Task Force (IETF).		Working Group of the Internet Engineering Task Force (IETF).
	Comments should be submitted to the Working Group mailing list at		Comments should be submitted to the Working Group mailing list at
	"manet@itd.nrl.navy.mil". Distribution of this memo is unlimited.		"manet@itd.nrl.navy.mil". Distribution of this memo is unlimited.
	skipping to change at page 2, line 4		skipping to change at page 2, line 4
	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.
	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 network address of a node is <Group ID,		coordinated fashion. The existence of such logical group can be
	Host ID>. A landmark is dynamically elected in each group. The		efficiently reflected in the addressing scheme. It assumes that
	route to a landmark is propagated throughout the network using a		an IP like address is used consisting of a group ID (or subnet ID)
	Distance Vector mechanism. Separately, each node in the network		and a host ID, i.e. <Group ID, Host ID>. A landmark is dynamically
	uses a "scoped" routing algorithm (e.g., FSR) to learn about routes		elected in each group. The route to a landmark is propagated
	within a given (max number of hops) scope. To route a packet to a		throughout the network using a Distance Vector mechanism.
	destination outside its scope, a node will direct the packet to the		Separately, each node in the network uses a "scoped" routing
	landmark corresponding to the group ID of such destination. Once		algorithm (e.g., FSR) to learn about routes within a given (max
	the packet is within the scope of the landmark, it will typically		number of hops) scope. To route a packet to a destination outside
	be routed directly to the destination. Remote groups of nodes are		its scope, a node will direct the packet to the landmark
			corresponding to the group ID of such destination. Once the packet
			is within the scope of the landmark, it will typically be routed
			directly to the destination. Remote groups of nodes are
	"summarized" by the corresponding landmarks. The solution to		"summarized" by the corresponding landmarks. The solution to
	drifters (i.e., nodes outside of the scope of their landmark) is		drifters (i.e., nodes outside of the scope of their landmark) is
	also handled by LANMAR. Landmark dynamic election enables LANMAR		also handled by LANMAR. Landmark dynamic election enables LANMAR
	to cope with mobile environments. By using a "scoped" routing		to cope with mobile environments. Thus, by using the truncated
	scheme, we dramatically reduce routing table size and update		local routing table and the "summarized" landmark distance vector,
	overhead in large nets. LANMAR is well suited to provide an		LANMAR dramatically reduces routing table size and update overhead
	efficient and scalable routing solution in large, mobile, ad hoc		in large nets. LANMAR is well suited to provide an efficient and
	environments in which group behavior applies and high mobility		scalable routing solution in large, mobile, ad hoc environments in
	renders traditional routing schemes inefficient.		which group behavior applies and high mobility renders traditional
			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. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4		2. Changes ....................................................... 5
	2.1. General Terms . . . . . . . . . . . . . . . . . . . . . 4
	2.2. Specification Language . . . . . . . . . . . . . . . . . 5
	3. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 5		3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5
	3.1. Networking Context . . . . . . . . . . . . . . . . . . . 5		3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 5
	3.2. Protocol Characteristics and Mechanisms . . . . . . . . 6		3.2. Specification Language . . . . . . . . . . . . . . . . . 5
	4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8		4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 6
	4.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8		4.1. Networking Context . . . . . . . . . . . . . . . . . . . 6
	4.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9		4.2. Protocol Characteristics and Mechanisms . . . . . . . . 6
	4.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10
	5. Protocol Specifications . . . . . . . . . . . . . . . . . . . 10		5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8
	5.1. Data Structures . . . . . . . . . . . . . . . . . . . 10		5.1. Protocol Descriptions . . . . . . . . . . . . . . . . . 8
	5.1.1 Landmark Status . . . . . . . . . . . . . . . . . 11		5.2. Landmark Election . . . . . . . . . . . . . . . . . . . 9
	5.1.2 Landmark Distance Vector . . . . . . . . . . . . 11		5.3. Drifters . . . . . . . . . . . . . . . . . . . . . . . . 10
	5.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11		6. Protocol Specifications . . . . . . . . . . . . . . . . . . . 10
	5.2. LANMAR Update Message Format . . . . . . . . . . . . 11		6.1. Data Structures . . . . . . . . . . . . . . . . . . . 11
	5.2.1 Description of the fields . . . . . . . . . . . . 12		6.1.1 Landmark Status tuple . . . . . . . . . . . . . . 11
	5.3. Processing Landmark Updates . . . . . . . . . . . . . . 13		6.1.2 Landmark Distance Vector . . . . . . . . . . . . 11
	5.3.1 Originating a Landmark in a Subnet . . . . . . . 13		6.1.3 Drifter List . . . . . . . . . . . . . . . . . . 11
	5.3.2 Receiving Landmark Updates . . . . . . . . . . . 14		6.1.4 Neighbor List . . . . . . . . . . . . . . . . . . 12
	5.3.3 Winner Competition . . . . . . . . . . . . . . . 14		6.2. LANMAR Update Message Format . . . . . . . . . . . . 12
	5.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14		6.2.1 Description of the fields . . . . . . . . . . . . 12
	5.4.1 Originating a Drifter Entry . . . . . . . . . . . 14		6.3. Processing Landmark Updates . . . . . . . . . . . . . . 13
	5.4.2 Receiving Drifter Updates . . . . . . . . . . . . 15		6.3.1 Originating a Landmark in a Subnet . . . . . . . 13
			6.3.2 Receiving Landmark Updates . . . . . . . . . . . 14
			6.3.3 Winner Competition . . . . . . . . . . . . . . . 14
			6.4. Processing Drifter Updates . . . . . . . . . . . . . . . 14
			6.4.1 Originating a Drifter Entry . . . . . . . . . . . 15
			6.4.2 Receiving Drifter Updates . . . . . . . . . . . . 15
			6.4.3 Removing a Drifter Entry . . . . . . . . . . . . 15
			6.5. Processing Neighbor List . . . . . . . . . . . . . . . . 15
	6. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15		7. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 15
	7. Discussion about Storage and Processing Overhead for Drifters 15		8. Discussion about Storage and Processing Overhead for Drifters 16
	Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 16		Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 16
	References . . . . . . . . . . . . . . . . . . . . . . . . . . . 16		References . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
	Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17		Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17		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
	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, colleagues in the same		(e.g., brigade in the battlefield, a group of students from same
	organization, a group of students from same class, or a team of		class and a team of co-workers at a convention). Each such
	co-workers at a convention and a tank battalion in the battlefield).		logical group has an elected landmark. For each group,
			underlying "scoped" routing algorithm will provide a one-level
	Each such logical group has an elected landmark. For each group,
	underlining "scoped" routing algorithm will provide a one-level
	scope. The routing update packets are restricted only within the		scope. The routing update packets are restricted only within the
	scope. Accurate routing information for nodes within scope is		scope. Accurate routing information for nodes within scope is
	maintained. The routing information to remote nodes (nodes outside		maintained. The routing information to remote nodes (nodes outside
	the node's scope) is "summarized" by the corresponding landmarks.		the node's scope) is "summarized" by the corresponding landmarks.
	Thus, the LANMAR scheme largely reduces the routing table size and		Thus, 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 drifters (Nodes that are outside the fisheye scopes of the
	landmarks of their logical groups). Extra storage, processing and		landmarks of their logical groups). 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 7.		Section 8.
	The LANMAR runs on top of a proactive routing protocol. It also		The LANMAR runs on top of a proactive routing protocol. It
	requires that the underlining 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. However, the fisheye scope		protocol is used within the scope. The fisheye scope
	technique can also be applied to a distance vector type protocol,		technique 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		bind the scope for 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. Terminology		2. Changes
	2.1. General Terms		Major changes from version 00 to version 01:
			- A destination sequence number for each landmark is used to
			ensure loop-free updates for a particular landmark.
			- Landmark updates are propagated in separate messages, instead of
			being piggybacked on local routing updates. This modification
			decouples landmark routing from the underlying proactive routing
			protocol.
			3. Terminology
			3.1. General Terms
	This section defines terminology used in LANMAR.		This section defines terminology used in LANMAR.
	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 zone that is bounded by hop distances.
	skipping to change at page 5, line 16		skipping to change at page 5, line 37
	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 zone that is bounded by hop distances.
	host protocol		host protocol
	A proactive protocol underlines the Landmark Routing Protocol.		A proactive protocol underlies the Landmark Routing Protocol.
	subnet		subnet
	Logical groups of nodes that present similar motion behavior.		Logical groups of nodes that present similar motion behavior.
	group		group
	This is used interchangeably with subnet.		This term is used interchangeably with subnet.
	2.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].
	3. Protocol Applicability		4. Protocol Applicability
	3.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 "scoped" routing algorithm
	has large advantages in reducing routing update packet size and		has large advantages in reducing routing update packet size and
	keeping progressive accurate routes to remote nodes. It achieves		keeping progressive accurate routes to remote nodes. It achieves
	high data packet to routing packet ratio. Moreover, the fact that		high data packet delivery ratio. Moreover, the fact that the route
	the route error is weighted by distance obviously reduces the		error is blurred by distance obviously reduces the sensitivity to
	sensitivity to network size.		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 mobility 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 and that all the information about
	remote nodes is summarized by landmarks.		remote nodes is summarized by landmarks.
	3.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?)
	Yes. Since LANMAR is on top of a host protocol, if the host		No.
	protocol supports unidirectional links, e.g., the FSR protocol,
	LANMAR can use the unidirectional link states as well.
	* Does the protocol require the use of tunneling? (if so, how?)		* Does the protocol require the use of tunneling? (if so, how?)
	No.		No.
	* Does the protocol require using some form of source routing? (if		* Does the protocol require using some form of source routing? (if
	so, how?)		so, how?)
	No.		No.
	* Does the protocol require the use of periodic messaging? (if so,		* Does the protocol require the use of periodic messaging? (if so,
	how?)		how?)
	Yes. The LANMAR periodically broadcasts landmark information		Yes. The LANMAR periodically broadcasts landmark information
	to its neighbors. But the updates are piggybacked in the host		to its neighbors.
	routing update messages.
	* Does the protocol require the use of reliable or sequenced packet		* Does the protocol require the use of reliable or sequenced packet
	delivery? (if so, how?)		delivery? (if so, how?)
	No. As the packets are sent periodically, they need not be		No. As the packets are sent periodically, they need not be
	sent reliably.		sent reliably.
	* Does the protocol provide support for routing through a multi-		* Does the protocol provide support for routing through a multi-
	technology routing fabric? (if so, how?)		technology routing fabric? (if so, how?)
	skipping to change at page 7, line 30		skipping to change at page 7, line 46
	No.		No.
	* Does the protocol function proactively? (if so, how?)		* Does the protocol function proactively? (if so, how?)
	Yes. The LANMAR proactively maintains landmark information		Yes. The LANMAR proactively maintains landmark information
	at each node.		at each node.
	* Does the protocol provide loop-free routing? (if so, how?)		* Does the protocol provide loop-free routing? (if so, how?)
	Yes. As the protocol uses routing paths learned from the host		Yes. For in-scope destinations, the protocol uses routing
	protocol for in-scope destinations, if the host protocol		paths learned from the host protocol. If the host protocol
	provides loop-free routing, so does LANMAR. For out-scope		provides loop-free routing, e.g., FSR and DSDV, so does LANMAR.
	destinations, only routes to landmarks are used. Because these		For out-scope destinations, only routes to landmarks are used.
	routes are DSDV, it is loop free. When a packet is		Because these routes are DSDV, it is loop free. When a packet
	approaching the destination, in-scope routes are used again.		approaches the destination, in-scope routes are used again.
	* Does the protocol provide for sleep period operation?(if so, how?)		* Does the protocol provide for sleep period operation?(if so, how?)
	Yes. However, this requires TDMA MAC layer support. The		Yes. However, this requires TDMA MAC layer support. The
	router can be scheduled to sleep during idle periods.		router can be scheduled to sleep during idle periods.
	* Does the protocol provide some form of security? (if so, how?)		* Does the protocol provide some form of security? (if so, how?)
	Yes. When a node broadcasts routing update message, only		Yes. When a node broadcasts routing update message, only
	entries of in-scope nodes and landmarks are included. This		entries of in-scope nodes and landmarks are included. This
	will prevent other remote nodes from being heard.		will prevent other remote nodes from being heard.
	* Does the protocol provide support for utilizing multi-channel,		* Does the protocol provide support for utilizing multi-channel,
	link-layer technologies? (if so, how?)		link-layer technologies? (if so, how?)
	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.
	4. Protocol Overview		5. Protocol Overview
	4.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 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. If a landmark does not		fulfills the requirement of the protocol. The elected landmark
	locate at the center, there will be some members drifting off		uses a destination sequence number to ensure its routing entry
	its scope. The landmark will keep records for these drifters.		update is loop-free. The landmarks are propagated in a
			distance vector mechanism. Each node maintains a distance vector
	The LANMAR relies on an underlining proactive protocol with the		for landmarks of all the subnets. The size of the landmark distance
	ability of providing "scoped" routing. The LANMAR itself is a
	distance vector type protocol. Each node maintains a distance
	vector for landmarks of all the subnets and a distance vector for
	drifters in its subnet. The distance vectors for landmarks and
	drifters are exchanged through piggybacking in the periodical
	routing update packets (link state or distance vector) of the
	underling routing protocol. 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. Both sizes of the two distance vectors are small.		nodes. If a landmark does not locate at the center, there will be
			some members drifting off its scope. The landmark will keep a
			distance vector for drifters of its group. The distance vectors
			for landmarks and drifters are exchanged among neighbors in
			periodical routing update packets.
	The routing update scheme uses the "scoped" routing algorithm.		The LANMAR relies on an underlying proactive protocol with the
	The main idea is summarized below. Each node broadcasts routing		ability of providing "scoped" routing. In the scoped routing, each
	information periodically to its immediate neighbors. In each		node broadcasts routing information periodically to its immediate
	update packet, the node sends routing table entries within its		neighbors. In each update packet, the node sends routing table
	scope and also piggybacks the landmark and drifter distance		entries within its scope. The host routing protocol uses sequence
	vectors. Sequence numbers are used in LANMAR update packets.		numbers for routing entries. Each node advances its sequence
	Each node advances its sequence number before sending an update		number before sending an update packet. Through the exchange
	packet. Through the exchange process, the table entries with		process, the table entries with larger sequence numbers replace
	larger sequence numbers replace the ones with smaller sequence		the ones with smaller sequence numbers.
	numbers.
	Let's take, for example, the FSR as our host protocol. For nodes		Let's take, for example, the FSR as our host protocol. For nodes
	within the scope, the updating is in a certain frequency. But		within the scope, the updating is in a certain frequency. But
	for nodes beyond the scope, the update frequency is reduced to		for nodes beyond the scope, the update frequency is reduced to
	zero; Only the update frequency of the landmark nodes remains		zero; Only the update frequency of the landmark nodes remains
	unaltered. As a result, each node maintains accurate routing		unaltered. As a result, each node maintains accurate routing
	information for in-scope nodes and keep routing directions to the		information for in-scope nodes and keep routing directions to the
	landmark nodes for out-scope nodes, or say, for remote groups.		landmark nodes for out-scope nodes, or say, for remote groups.
	A packet directed to a remote destination initially aims at the		A packet directed to a remote destination initially aims at the
	landmark of that remote group; as it gets closer to the landmark,		landmark of that remote group; as it gets closer to the landmark,
	it may eventually switch to the accurate route to the destination		it may eventually switch to the accurate route to the destination
	provided by in-scope nodes of the destination.		provided by in-scope nodes of the destination.
	4.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. The node broadcasts the landmark information to		distance vector. Landmarks broadcast the election weights to
	the neighbors jointly with the host update packets.		the neighbors jointly with the landmark 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 6		skipping to change at page 10, line 19
	landmarks in a single group. The transient period may be actually		landmarks in a single group. The transient period may be actually
	the norm at high mobility. This transient behavior can be		the norm at high mobility. This transient behavior can be
	drastically reduced by using hysteresis.		drastically reduced by using hysteresis.
	When a landmark dies, its neighbors will detect the silence after		When a landmark dies, its neighbors will detect the silence after
	a given timeout. The neighbors of the same group will then take		a given timeout. 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.
	4.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
	the landmark to each of its members, including drifters.		the landmark to each of its members, including drifters. The
			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.
	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 detects itself a drifter is propagated with the		when a node hears a drifter is recorded.
	distance vector.
	5. 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.
	5.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 can
	logically group the nodes. Moreover, each node keeps a landmark		logically group the nodes. Moreover, each node keeps a landmark
	status as part of identifier. As LANMAR runs on top of a host		status tuple. As LANMAR runs on top of a host routing protocol,
	routing protocol, it shares the underlining data structures.		it shares the underlying routing table structures. LANMAR
	Particularly, LANMAR requires the underlining data structures to		maintains a neighbor list and shares it with the host protocol.
	associate a landmark status with each node's identifier. In		In addition, LANMAR keeps a drifter list and a landmark distance
	addition, LANMAR keeps a drifter list and a landmark distance
	vector.		vector.
	5.1.1. Landmark Status		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. The status includes		its address, but also a landmark status tuple. The tuple includes
	a flag which indicates whether the node is a landmark or not and a		a flag which indicates whether the node is a landmark or not, a
	weight (the number of group members the node detects within its		election weight (the number of group members the node detects within
	scope). Anywhere in the tables of the host protocol, when a		its scope) and a sequence number. When a node is elected, the
	node's address is kept, a landmark status is recorded. The status		status tuple will be copied to its landmark distance vector. The
	is piggybacked in the periodical routing update packets of the		sequence number is advanced. There are three fields for a tuple:
	host protocols together with the node address. There are two
	fields for a status:
	- Landmark flag		- Landmark flag
	- Number of group members in its scope		- Number of group members in its scope
			- Sequence number
	5.1.2. Landmark Distance Vector		6.1.2. Landmark Distance Vector
	Landmark distance vector (LMDV) gives the next hop information to		Landmark distance vector (LMDV) gives the next hop information to
	all landmarks in the network. Every subnet has an entry in LMDV.		all landmarks in the network. Every subnet has an entry in LMDV.
	Initially, the entries in the underlining routing table, which		The latest route information to the landmark of each subnet is
	point to landmarks, are copied to LMDV. The LMDV entries are		learned when a landmark update message is received. LMDV functions
	updated when landmark update message is received or underlining		as a part of the routing table. It has the following fields:
	topology table is changed. LMDV functions as a part of the		- Landmark status tuple
	routing table. It has the following fields:
	- Landmark status
	- Next hop address		- Next hop address
	- Distance		- Distance
	5.1.3. Drifter List		6.1.3. Drifter List
	The drifter list of LANMAR provides the next hop information to		The drifter list (DFDV) of LANMAR provides the next hop information
	forward the packets to the drifters known to the current node.		of the drifters known to the current node. The entries are updated
	The entries are updated explicitly using landmark update message.		with landmark update message. The latest time a drifter is heard
	It works as a part of routing table. The drifter list (DFDV) has		is recorded in DFDV. The DFDV works as a part of routing table.
	following fields:		It has the following fields:
	- Destination drifter address		- Destination drifter address
	- Next hop address		- Next hop address
	- Last declaration time		- Distance
			- Last heard time
	5.2. LANMAR Update Message Format		6.1.4. Neighbor List
	The messages necessary for LANMAR protocol are piggybacked in the		The neighbor list of LANMAR keeps current neighbor information for
	host periodic update packets. The format given below is not		a node. The latest time a neighbor is heard is recorded. The
	exactly how the bits appear in the host update packets. Where to		neighbor list has the following fields:
	put these fields in the host update packets is an implementation		- Neighbor address
	issue. The necessary fields include current node's landmark		- Neighbor landmark flag
	status (assuming that the node's address can be obtained from IP		- Last heard time
	header), its landmark distance vector LMDV and the drifter list
	DFDV. The next two subsections will describe how these		6.2. LANMAR Update Message Format
	information is processed.
			There is only one message type of LANMAR protocol. The messages are
			periodically exchanged with neighbors. They update the landmark
			distance vector LMDV and the drifter list DFDV. The processing of
			the LMDV and DFDV will be describe separately. The following format
			does not include the node's identifier because it can be obtained
			from IP Header.
	0 1 2 3		0 1 2 3
	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_members | Reserved | N_landmarks |		| Landmark Flag | N_landmarks | N_drifters | Reserved |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Landmark Address 1 |		| Landmark Address 1 |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Next Hop Address 1 |		| Next Hop Address 1 |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| N_members 1 | Distance 1 | ... :		| Distance 1 | N_members 1 | Sequence Number 1 :
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	: . . . :		: . . . :
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	: . . . | N_drifters |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Drifter Address 1 |		| Drifter Address 1 |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Next Hop Address 1 |		| Next Hop Address 1 |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Distance 1 | Timestamp 1 | ... :		| Distance 1 | ... :
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	: . . . |		: . . . |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	5.2.1. Description of the fields		6.2.1. Description of the fields
	Landmark Flag and N_members
	These two fields are the landmark status. N_members is the
	number of group members in the node's scope.
	Reserved		Landmark Flag
	The bits are set to '0' and are ignored on reception.		The landmark flag of the sending node.
	N_landmarks		N_landmarks
	The number of entries of the landmark distance vector.		The number of entries of the landmark distance vector.
	Landmark Address 1, Next Hop Address 1, N_members 1 and Distance 1		N_drifters
			The number of entries of the drifter list.
			Reserved
			The bits are set to '0' and are ignored on reception.
			Landmark Address 1, Next Hop Address 1, Distance 1, N_members 1
			and Sequence Number 1
	The first entry in the landmark distance vector.		The first entry in the landmark distance vector.
	Landmark Address 1 and N_members 1 are the destination landmark		Landmark Address 1, N_members 1 and Sequence Number 1 are the
	status.		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.
	N_drifters		Drifter Address 1, Next Hop Address 1 and Distance 1
	The number of entries of the drifter list.
	Drifter Address 1, Next Hop Address 1, Distance 1, Timestamp 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.
	Timestamp 1 is the time when the node becomes a drifter.
	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 (including the host update fields) is		The length of the message is limited to the maximum IP packet size.
	limited to the maximum IP packet size. In that case, multiple		In that case, multiple packets may be required to broadcast all the
	packets may be required to broadcast all the topology entries for		entries.
	host protocol. The landmark distance vector and drifter list will
	be piggybacked in each packet with the same sequence number.
	5.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, which is carried in host updating packets.		routing update message. The update information includes sender's
	The update information includes sender's landmark status and LMDV.		LMDV. Landmark update message is used for landmark election and
	Landmark update message is used for landmark election and helps		building paths to landmarks.
	nodes build their LMDV.
	5.3.1. Originating a Landmark in a Subnet		6.3.1. Originating a Landmark in a Subnet
	Every time a node detects a topology change, 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 landmark status and replaces the old		members is recorded in its election weight field. If this
	values in all the tables containing the landmark status. 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 there is no landmark for the group according to		landmark only when it is the only landmark for the group so far,
	its LMDV, or it wins the election when competing with the existing		or it wins the election when competing with the existing landmark.
	landmark. The landmark distance vector is updated accordingly.		When it becomes a landmark, it increases its sequence number by 2.
	If the host protocol has new shortest paths to landmarks, the new		The old landmark entry is replaced with the new winner. The
	paths are copied from the host routing table to the LMDV.		landmark entry will be broadcast to neighbors with the next update
	The landmark status and the LMDV will be broadcast to neighbors		packet. Every time before a landmark sends updates, it increases
	with the next host update packet.		its sequence number and copies it to LMDV.
	5.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 entries for each subnet. New		LMDV entries with the incoming LMDV updates for each subnet.
	landmark enrties will be copied. Competing landmarks will		A landmark update corresponding to a new subnet will be copied.
	be solved through a winner competition algorithm. The winner will		An update having the same landmark as already given (in node's LMDV)
	be elected as the landmark for the subnet. The node's landmark		will be accepted only if it contains a larger sequence number.
	status and LMDV will be updated according to the outcomes of the		If an update contains a different landmark for the same subnet as
	competition. The distance information can be obtained either from		recorded in LMDV, only one landmark will be elected through a
	the incoming LMDV entry or from host routing table. The updated		winner competition algorithm. LMDV will be updated according to
	LMDV and the node's landmark status will be propagated jointly with		the outcomes of the competition.
	the host routing update packets.
	5.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 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.
	5.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, which is carried in host updating packets.		routing update message. The update information is the drifter list
	The update information is the drifter list (DFDV) of the sender.		(DFDV) of the sender. The computation of the DFDV at each node
	The computation of the DFDV at each node includes checking the node		includes checking the node itself to see whether it is a drifter
	itself to see whether it is a drifter and recording paths to other		and recording paths to other drifters.
	drifters.
	5.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 and record the time instance. This drifter information		list. This drifter information will be sent back to the landmark
	will be sent back to the landmark hop by hop along the shortest		hop by hop along the shortest path to it which can be learned from
	path to it which can be learned from the LMDV. For each drifter,		the LMDV. For each drifter, only the node on its shortest path
	only the node on its shortest path to the landmark needs to receive		to the landmark needs to receive its information, so before the
	its information, so before the entry is broadcast, the next hop to		entry is broadcast, the next hop to landmark is attached with
	landmark is attached with its entry. The DFDV will be propagated		its entry. The DFDV will be propagated with the next update packet.
	with the next host routing update packet.
	5.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 node sending the update		insert or update its drifter list. The receiving time is stamped
	packet is recorded as the next hop to the drifter. The reverse path		in the DFDV. The node sending the update packet is recorded as the
	to the drifter is thus built up. The procedure ends when the		next hop to the drifter. The reverse path to the drifter is thus
	landmark receives the drifter entry. The updated DFDV will be		built up. The procedure ends when the landmark receives the
	propagated with the next host routing update packet.		drifter entry. The updated DFDV will be propagated with the next
			update packet.
	6. Data Packet Forwarding		6.4.3. Removing a Drifter Entry
			Each entry in DFDV is time stamped of its last receiving time.
			Every time before the DFDV is sent or routing by DFDV is needed,
			the table is checked for staled entries. If such an entry is found,
			it is removed.
			6.5. Processing Neighbor List
			When a node receives either a landmark update or a host protocol
			routing update, the neighbor list is inserted if the update comes
			from a new neighbor, or the corresponding neighbor entry is
			updated. Current time is recorded with the entry. The
			neighbor list is also search at this time for possible lost
			neighbors according to the time stamps. If such a neighbor is
			found, it is removed from the list.
			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
	destination is retrieved and the LMDV entry of the landmark		destination is retrieved and the LMDV entry of the landmark
	corresponding to the destination's logical subnet is searched.		corresponding to the destination's logical subnet is searched.
	The data packet is then routed towards the landmark using the next		The data packet is then routed towards the landmark using the next
	hop address from LMDV. The packet, however, is not necessary to		hop address from LMDV. The packet, however, is not necessary to
	pass through the landmark. Rather, once the packet gets within the		pass through the landmark. Rather, once the packet gets within the
	scope of the destination on its way towards the landmark, it is		scope of the destination on its way towards the landmark, it is
	routed to the destination directly.		routed to the destination directly.
	7. 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
	skipping to change at page 16, line 18		skipping to change at page 16, line 41
	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%.
	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,
	and in part by DARPA under contract DAAB07-97-C-D321.		by DARPA under contract DAAB07-97-C-D321, and by ONR under
			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.
	skipping to change at page 17, line 47		skipping to change at page 18, line 23
	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-4367		Phone: +1 310 825-4367
	Fax: +1 310 825-7578		Fax: +1 310 825-7578
	Email: gerla@cs.ucla.edu		Email: gerla@cs.ucla.edu
	Xiaoyan Hong		Xiaoyan Hong
	3820 Boelter Hall		3803F Boelter Hall
	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-4623		Phone: +1 310 825-4623
	Fax: +1 310 825-7578		Fax: +1 310 825-7578
	Email: hxy@cs.ucla.edu		Email: hxy@cs.ucla.edu
	Li Ma		Li Ma
	3803 Boelter Hall		3803D Boelter Hall
	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
End of changes.
This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/