[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
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]