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]