Internet Engineering Task Force Seoung-Bum Lee
INTERNET-DRAFT Jiyoung Cho
draft-lee-hmp-00.txt Andrew T. Campbell
Expires: March 2004 Columbia University
October 2003
Hotspot Mitigation Protocol (HMP)
Status of this Memo
This document is an Internet-Draft and is subject to all provisions
of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt The list of
Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Distribution of this memo is unlimited.
Abstract
This draft specifies a Hotspot Mitigation Protocol (HMP) for
mobile ad hoc networks that use on-demand routing protocols and
the IEEE 802.11 MAC. Hotspots represent transient but highly
congested regions in wireless ad hoc networks that result in
increased packet loss, end-to-end delay, and out-of-order
packets delivery. Using HMP, mobile nodes independently monitor
local conditions (e.g., buffer occupancy, packet loss, and MAC
contention and delay) in a fully distributed manner, and take
local actions in response to the emergence of hotspots, such as,
suppressing new route requests and rate controlling TCP flows.
As a result, HMP improves end-to-end throughput, delay, and
packet loss, balances the resource consumption among neighboring
nodes, and finally, improves the network connectivity by
preventing premature network partitions.
Lee, Cho, Campbell Expires March 2004 [page 1]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
Table of Contents
1. Introduction .............................................. 2
2. Hotspots .................................................. 3
2.1 Existence of Hotspots ..................................... 4
2.2 Hotspot Detection ......................................... 4
2.2.1 MAC-delay violation .................................... 5
2.2.3 Packet Loss ............................................ 6
2.2.3 Buffer Occupancy ....................................... 6
2.3 Hotspot Region ............................................ 6
3. Hotspot Mitigation Protocol ............................... 6
3.1 HMP Operation ............................................. 8
3.2 Congestion Levels ......................................... 9
3.3 Energy-awareness .......................................... 9
3.4 Protocol Sensitivity ..................................... 10
4. Acknowledgement .......................................... 10
5. Reference ................................................ 11
6. Author's Addresses ....................................... 11
1. Introduction
Hotspots are often created in regions of mobile ad hoc networks
(MANETs) where flows converge and intersect with each other.
Hotspots are defined as nodes that experience flash congestion
conditions or excessive contention over longer time-scales (e.g.,
order of seconds). Under such conditions nodes typically consume
more resources (e.g., energy) and attempt to receive, process, and
forward packets but the performance of the packet forwarding and
signaling functions is considerably diminished and limited during
hotspot periods. This is the result of excessive contention of the
shared media wireless access, and due to flash loading at hotspot
nodes, and importantly, at neighboring nodes that are in the region
of hotspots. Hotspots are often transient in nature because the
mobility of nodes in the network continuously creates, removes, and
to some degree, migrates hotspots because node mobility changes the
network topology and causes flows to be rerouted. Hotspots are
characterized by excessive contention, congestion, and resource
exhaustion in these networks. In other words, hotspots appear when
excessive contention exists, prompting congestion when insufficient
resources are available to handle the increased traffic load.
Hotspots are intrinsic to many on-demand MANET routing protocols
because most on-demand routing protocols [1][2][3] utilize shortest
path (or hop count) as their primary route creation metric. Most
Lee, Cho, Campbell Expires March 2004 [page 2]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
on-demand routing protocols allow an intermediate node to reply to a
route query using cached route information, causing traffic to
concentrate at certain nodes. Although many on-demand routing
protocols prove to be effective in routing packets in these
networks they also have a propensity to create hotspots, where these
hotspots consume a disproportionate amount of resources (e.g., energy)
[7]. Other researchers have made similar observations [4][5][6].
Ideally, establishing routes through non-congested
areas of the network and rerouting active flows away
from congested areas to non- congested areas would be the best
approach to hotspot mitigation. However, this requires extensive
collaboration between nodes to establish load-aware routes and
sophisticated algorithms to update time-varying loading conditions.
Such an approach is unscalable and not practical in mobile ad hoc
networks.
This draft specifies a Hotspot Mitigation Protocol (HMP) for
mobile ad hoc networks that use on-demand routing protocols and
the IEEE 802.11 MAC. Hotspots represent transient but highly
congested regions in wireless ad hoc networks that result in
increased packet loss, end-to-end delay, and out-of-order
packets delivery. Using HMP, mobile nodes independently monitor
local conditions, and take local actions in response to the
emergence of hotspots. As a result, HMP improves end-to-end
throughput, delay, and packet loss, balances the resource
consumption among neighboring nodes, and finally, improves the
network connectivity by preventing premature network partitions.
HMP represents a fully distributed and scalable protocol where nodes
independently monitor local conditions and take local actions:
o to declare a node to be a hotspot if a combination of MAC
contention/delays, packet loss, buffer occupancy, and remaining
energy reserves exceed certain predefined system thresholds;
o to suppress new route requests at hotspots to ensure that routed
traffic does not compound congestion problems; and
o to throttle traffic locally at hotspots to force TCP flows to
slow down.
2. Hotspots
2.1 Existence of Hotspots
Hotspots are generally created when traffic converges to a node or
small cluster of nodes. Flows traversing multiple wireless hops from
various locations intersect with each other and create transient
Lee, Cho, Campbell Expires March 2004 [page 3]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
hotspot conditions. Hotspot nodes and nodes in the vicinity of
hotspots (i.e., in hotspot regions) are prone to consume more
resources than others. Left unchecked such unbalanced resource
consumption is detrimental to mobile ad hoc networks because
overtaxed nodes would prematurely exhaust their energy reserves
before other nodes. As a consequence the network connectivity can be
unnecessarily impacted.
In addition, it is observed that hotspot nodes are often responsible
for generating a large amount of routing overhead. In general, as
the traffic load increases more hotspots appear and conditions in
hotspots (or hotspot regions) become aggravated. For detail
on the evaluation of hotspots in MANETs see [7].
2.2 Hotspot Detection
A number of system parameters are used by HMP to identify hotspots.
These per-node parameters, which are associated with MAC-delays,
packet loss, and buffer occupancy, can be configured to make HMP's
hotspot detection mechanism more or less aggressive in its
declaration of hotspots. In current version of HMP implementation,
hotspots are detected using 3 criteria:
1. MAC-delay Violations
2. Packet Loss
3. Buffer Occupancy
2.2.1 MAC-delay Violation
The MAC_DELAY_THRESH parameter is used by the protocol to detect
MAC-delay violations. If the measured MAC-delay exceeds the
MAC_DELAY_THRESH then HMP considers this a MAC-delay violation. If
the number of these violations exceeds a predefined value called
N_THRESH then the protocol takes a number of actions discussed
below. We define the MAC-delay as the measured time for the
successful transmission of a data packet at the MAC layer. This
includes the time taken for the RTS-CTS-DATA-ACK message exchange
over the air. As shown in Figure 1, the MAC-delay measurement represents
the time between T_(j) and T_(i). Because IEEE 802.11 defines up to
7 possible retransmissions of a data packet the measured MAC-delay
could represent up to a maximum of 7 RTS-CTS-DATA-ACK cycles in the
case were packet loss occurs.
Lee, Cho, Campbell Expires March 2004 [page 4]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
Node(A) Node(B)
| |
send RTS at T_(i) | ------- RTS -------> |
| <------ CTS -------- |
| ------- DATA-------> |
receive ACK at T_(j) | <------ ACK -------- |
MAC-delay = T_(j) - T_(i)
Figure 1: MAC Delay Measurement
Each node continuously monitors the on-going MAC-delay and compares
it to the MAC_DELAY_THRESH value. The N_THRESH parameter is used to
control the sensitivity of the protocol to the measured MAC-delays.
N_THRESH defines how many consecutive MAC-delay violations can be
tolerated before a node is declared a hotspot. This parameter
essentially determines how aggressive HMP is in declaring hotspots.
In other words, a node is identified as a hotspot when the
MAC_DELAY_THRESH parameter is consecutively violated more than
N_THRESH times.
2.2.2 Packet Loss
Hotspot detection also needs to consider the case of packet loss. In
the case where there is an intermittent packet loss between two
consecutive MAC-delay violations, HMP takes account of this
condition during hotspot detection; that is, a node is also
considered a hotspot when the MAC_DELAY_THRESH parameter is violated
(N_THRESH - (k)) times, where k is defined as the number of
intermittent packet losses during a hotspot detection interval. Note
that HMP monitors packet losses at MAC layer during RTS-CTS-DATA-ACK
exchange.
A hotspot detection interval starts when the first MAC-delay
violation is observed and lasts until the node either declares
itself a hotspot based on the criteria described above or a data
packet is successfully delivered without a MAC-delay violation. The
MAC-delay violation count maintained by HMP during the hotspot
detection interval is reset at the beginning of a new interval. Note
that many MANET routing protocols consider that three consecutive
packet losses represents link or route failure. Any link failure or
route error also resets all associated counters/parameters used by
HMP's hotspot detection.
Lee, Cho, Campbell Expires March 2004 [page 5]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
2.2.3 Buffer Occupancy
HMP also monitors buffer occupancy to identify hotspots. If a node
detects that the buffer occupancy exceeds a predefined threshold
called BUFFER_THRESH then it will check for MAC-delay violations.
The BUFFER_THRESH parameter is set to a buffer level that is less
than the buffer overflow mark. If BUFFER_THRESH is exceeded and
there is at least one MAC-delay violation within current hotspot
detection interval then the node declares itself a hotspot. HMP
adopt this hybrid approach to hotspot detection because buffer
occupancy information alone is insufficient to declare a hotspot
unless the buffer overflow mark is exceeded. As a result HMP
combines buffer occupancy with MAC-delay violations to make the
approach more accurate.
2.3 Hotspot Regions
A node belongs to a hotspot region if it is a hotspot or it is an
immediate neighbor of a hotspot node.
3. Hotspot Mitigation Protocol
3.1 Protocol Operations
HMP utilizes MAC-delay measurements, packet loss, buffer occupancy
information, neighbor status information and other resource
monitoring mechanisms (i.e., energy) to detect hotspots. HMP does
not limit the scope of monitoring and detection mechanisms, however.
Operators are free to introduce additional mechanisms and algorithms
according to their needs. In fact, it is envisioned that a HMP
network would embody diverse mechanisms operating concurrently. HMP
utilizes measured information to respond to conditions by executing
the most appropriate algorithms to alleviate the condition at hand.
The measured conditions are expressed by a multi-metric parameter
called STATUS, which consists of two components: symptom and
severity.
Lee, Cho, Campbell Expires March 2004 [page 6]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
Symptom describes the dominant condition a node is experiencing
while severity expresses the degree of the symptom. For example, a
node may declare its status as MODERATE_CONGESTION while another
node may declare its status as CRITICAL_ENERGY.
HMP piggybacks this status information in the IP option field and
neighboring nodes operating in promiscuous mode learn the status of
transmitters by eavesdropping their packets. The eavesdropped
information is used to create and update a Neighborhood Status Table
(NST). This status information is cached and locally maintained and
updated at each node.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL |Type of Service| Total Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
` | Identification |Flags| Fragment Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time to Live | Protocol | Header Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options (Used for HMP Options) | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2. IP Header
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| STATUS (Symtom, Severity) |PI |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ * PI = PATH_INDICATOR
Figure 3. HMP IP Option
A NST caches a list of immediate neighbors and their status. It is
primarily used to manipulate new-route-creation decisions at nodes.
A node refers to its NST to ensure that it is not aggravating the
conditions of neighboring nodes by creating new routes through them.
Lee, Cho, Campbell Expires March 2004 [page 7]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
It is assumed that there exist only a finite number of neighboring
nodes surrounding any node, which in effect defines the size of the
NST at a node. Naive suppression of new route creation may prevent
the use of the only possible path between two hosts and may yield
poor connectivity in the network, or even cause network partitions.
To avoid this, the 'new-route-suppression-mechanism' is used, if and
only if, there exists a sufficient number of non-hotspot neighbors
within its transmission range. HMP also makes sure that preceding
nodes en-route also have enough non-hotspot neighbors.
The notion of enough neighbors is defined by the NUM_ENOUGH_NEIGHBOR
parameter. This parameter has a direct impact on the network
connectivity. If NUM_ENOUGH_NEIGHBOR is too small, HMP manifests low
connectivity and may fail to provide useful routes.
HMP also ensures that it is not inadvertently denying the only
possible path between two end hosts by utilizing an indicator called
the 'PATH_INDICATOR', which is carried in the IP option field of
Route Request messages. A node that has only a few non-hotspot
neighbors (i.e., number of neighbors less than NUM_ENOUGH_NEIGHBOR)
sets this indicator (PATH_INDICATOR = 1) and upstream nodes that
receive the Route Request messages check this indicator and avoid
suppressing new routes if it is set. Nodes receiving packets with
this indicator set know that at least one preceding node explicitly
requested no new-route-suppression. This is a valuable HMP feature
because it provides a safeguard against potential over-suppression
of new route creation that may result in limited connectivity.
3.2 Congestion Levels
Main objective of congestion avoidance algorithms is preventing
further build up of traffic at hotspots. HMP distinguishes two
levels of congestion (i.e., levels 1 and 2) and adopts two
corresponding algorithms to support this view.
The first algorithm is activated when HMP determines the current
status of a node is in a moderately congested condition (i.e., level
1). This algorithm simply suppresses creation of additional routes
at hotspots by discarding new route request packets. As mentioned
previously, HMP ensures not to deny the only route between two
hosts.
The second algorithm is more aggressive and executes when nodes
encounter substantial congestion (i.e., level 2). This algorithm is
executed when a node experiences severe hotspot conditions without
any non-hotspot neighbors. This algorithm not only suppresses new
Lee, Cho, Campbell Expires March 2004 [page 8]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
route creation but also throttles best effort TCP flows traversing
the node in an attempt to reduce the load using rate control
mechanisms. TCP flows are bandwidth hungry and unless controlled can
easily occupy all remaining wireless medium bandwidth. Throttling
TCP rates locally in this manner does not necessarily hurt TCP
sessions but can effectively relieve congestion bottlenecks. Users
and operators are free to introduce other schemes to relieve
congestion conditions, e.g., one simple policy is dropping TCP
packets at bottleneck nodes.
HMP attacks the congestion at the point of congestion as opposed to
a traditional end-to-end approach. Although congestion is an
end-to-end issue where it is detected and controlled (e.g., as in
the case of TCP), traditional remedies for end-to-end congestion
control are not effective in mobile ad hoc networks. In fact, such
traditional control mechanisms may limit the utilization of the
wireless medium that is constrained by hotspots. We argue that we
can avoid such shortcomings if we tackle the problem at the point of
congestion rather than responding on end-to-end basis.
3.3 Energy-awareness
Mobile ad hoc networks are essentially energy-limited networks and
are likely to be comprised of heterogeneous nodes with diverse
energy constraints. Some mobile devices will have large energy
reserves in comparison to others. There exist various energy-aware
power-conserving protocols for mobile ad hoc networks. The common
objective of these protocols lie in conserving energy as much as
possible to prolong the lifetime of the network or extend the
lifetime of individual nodes. Although energy conservation is not a
primary concern of HMP, the protocol provides a simple mechanism to
conserve energy through its status declaration mechanism. A node
with limited energy reserves can declare itself a hotspot when its
energy reserves are marginally or critically low.
A node with energy concerns is acknowledged by neighboring nodes and
new route creation through such a node is avoided if possible. On
the other hand, a node with critical energy immediately relinquishes
its role as a router and functions strictly as an end host in order
to conserve energy (maximize its lifetime) unless it is identified
as the only intermediate node between two communicating end hosts.
Lee, Cho, Campbell Expires March 2004 [page 9]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
3.4 Protocol Sensitivity
Three key parameters govern the HMP system control mechanisms. These
are, MAC_DELAY_THRESH, N_THRESH and NUM_ENOUGH_NEIGHBOR. A
sensitivity analysis is provided in [7].
For example, if the MAC_DELAY_THRESH value is too small HMP becomes
aggressive and may declare too many hotspots. A small increase in
the MAC-delay measurement (or jitter) may falsely be recognized as
congestion with many nodes being claimed as hotspots. In contrast,
if the MAC_DELAY_THRESH value is too large HMP may not identify any
hotspots in the network and relegate itself to the baseline system.
The second parameter N_THRESH is used to prevent HMP from reacting
to transient behavior. A momentary increase in the MAC-delay
measurement and buffer occupancy are not necessarily a product of
congestion or excessive contention. Delay may be observed for a very
short period due to the rerouting of flows or a small burst of route
query packets. Reacting to such transitory phenomenon is not
beneficial because real hotspots cannot be distinguished from
transient events.
The third parameter is the NUM_ENOUGH_NEIGHBOR. Naive suppression of
new route creation at a hotspot node may prevent the use of the
'only possible path' between two hosts and may yield poor
connectivity in the network, or even cause network partitions. To
avoid this, a new-route-suppression mechanism is executed, if and
only if, there exists a sufficient number of non-hotspot neighbors
within its transmission range. The notion of 'sufficient number of
neighbors' is defined by the NUM_ENOUGH_NEIGHBOR parameter. This
information is piggybacked through PATH_INDICATOR to ensure that
preceding nodes en-route meet this 'sufficient number of neighbors'
condition when 'new-route-suppression' is executed.
4. Acknowledgement
This work is supported in part by the Army Research Office (ARO)
under Award DAAD19-99-1-0287 and with support from COMET Group
industrial sponsors.
Lee, Cho, Campbell Expires March 2004 [page 10]
INTERNET-DRAFT Hotspot Mitigation Protocol October 2003
5. Reference
[1] C. Perkins and E. Royer. "Ad hoc On-Demand Distance Vector Routing.
Proc. of the 2nd IEEE Workshop on Mobile Computing Systems and
Applications, New Orleans, LA, February 1999, pp. 90-100
[2] David B. Johnson, David A. Maltz, and Josh Broch. "DSR: The Dynamic
Source Routing Protocol for Multi-Hop WirelessAd Hoc Networks", in
Ad Hoc Networking, edited by Charles E. Perkins, Chapter 5, pp.
139-172, Addison-Wesley, 2001
[3] V. Park and S. Corson "A Highly Adaptive Distributed Routing
Algorithm for Mobile Wireless Networks, Proc. IEEE Infocom 1997,
Kobe, Japan
[4] Samir R. Das, Charles E. Perkins, and Elizabeth M. Royer.
"Performance Comparison of Two On-demand Routing Protocols for Ad
Hoc Networks." Proceedings of the IEEE Conference on Computer
Communications (INFOCOM), Tel Aviv, Israel, March 2000
[5] S.B Lee, G.S. Ahn, and A.T. Campbell, "Improving UDP and TCP
Performance in Mobile Ad Hoc Networks with INSIGNIA", June 2001,
IEEE Communication Magazine.
[6] S.J. Lee and M. Gerla "Dynamic Load-Aware Routing in Ad hoc
Networks" Proceedings of IEEE ICC 2001, Helsinki, Finland, June 2001
[7] Seoung-Bum Lee and Andrew T. Campbell, "HMP: Hotspot Mitigation
Protocol for Mobile Ad hoc networks", Ad Hoc Networks Journal,
Vol.1 No.1, March 2003
6. Author's Addresses
Seoung-Bum Lee, Jiyoung Cho, Andrew T. Campbell
Department of Electrical Engineering,
Columbia University,
500 W. 120th Street, Room 1312, New York, NY 10027
Phone : 1-212-854-0608
Fax : 1-212-316-9068
Email : sbl@comet.columbia.edu
Lee, Cho, Campbell Expires March 2004 [page 11]