include choosing relatively simple parameters such as The rest of the paper is structured as follows. W SSID and channel, and more complex questions such related work in section 2. In section 3 we characterize as number and placement of APs, and power control. the density and usage of 802.11 hardware across various Other aspects of management include troubleshoot US cities. Section 4 presents a simulation study of the ef- ing, adapting to changes in the environment and traffic fect of dense unmanaged 802.11 deployments on end-user load, and making the wireless network secure. performance. We present an analysis of power control in We use the term chaotic deployments or chaotic networks two-dimensional grid-like deployment in Section 5. In Se to refer to a collection of wireless networks with the above tion 6, we outline the challenges involved in making chaotic oroperties. Such deployments provide many unique opp deployments self-managing. We describe our implementa- tunities. For example, they may enable new techniques tion of rate adaptation and power management techniques to determine location (22 or can provide near ubiquitous tion of these techniques. We discuss other possible power hallenges. As wireless networks become more common and control algorithms in Section 9 and conclude the paper in ore densely packed, more of these chaotic deployments will Section 10 suffer from serious contention, poor performance, and secu- rity problems. This will hinder the deployment and use of 2. RELATED WORK these infrastructures, negating many of the benefits offered In this section, we first discuss curn by wireless networks )2.11 deployments. Then, we present an in chaotic 802.11 deployments can significantly affect end- eral, and wireless networks in particular. Finally, we co The main goal of this paper is to show that interferenc mercial services and products for managing user performance. To this end, we first use large-scale mea- trast our proposal for wireless self management(i.e,trans- surements of 802.11 APs deployed in several US cities, to mission power control and multi-rate adaptation)with re- quantify current density of deployment, as well as configu- ted past approaches. ation characteristics. of 802.11 hardware. Our analysis of Several Internet Web sites provide street-level maps of the data shows that regions with tens of APs deployed in WiFi hot-spots in various cities. Popular examples include lose proximity of each other already exist in most major WifiMaps8, Wi-Fi-Zones com[7 and JIWire com 6. Sev cities. Also, most 802.11 users employ default, factory-set eral vendors also market products targeted at locating wire- configurations for key parameters such as the transmission less networks while on the go(see for example, Intego WiFi channel. Interestingly, we find that relatively new wireless Locator 5. Among h studies, the Intel Place Lab technology (e. g, 802. 11g) gets deployed very quickly. project 22[11 maintains a database of up to 30,00080211b We then simulate the measured deployment and config. APs from several US cities. In this paper, we use hot-spot uration patterns to study the impact that unplanned AP data from WifiMaps. com, as well as the Intel Place Lab deployments have on end-user performance. While it is true database of APs, to infer deployment and usage characteris- that the impact on end-user performance depends on the tics of 802.11 hardware. To the best of our knowledge, ours workloads imposed by users on their network, we do find is the first research study to quantify these characteristics that even when the APs in an unplanned deployment are We describe our data sets in greater detail in Section 3. carefully configured to use the optimal static channel assign The general problem of automatically managing and con- ment, users may experience significant performance degra figuring devices has been well-studied in the wired network dation, e.g. by as much of a factor of 3 in throughput. This ing domain. While many solutions exist [35, 33] and have effect is especially pronounced when AP density (and as been widely deployed [16], a number of interesting research ciated client density)is high and the traffic load is heavy problems in simplifying network management still remain To improve end-user performance in chaotic deployments (e.g,[13, 30). Our work in this paper compliments these we explore the use of algorithms that automatically man results by extending them to the wireless domain age the transmission power levels and transmissions rates In the wireless domain several commercial vendors mar- of APs and clients. In combination with careful channel ket automated network management software for APs. Ex assignment, our power control algorithms attempt to min amples include Propagate Networks'Autocell 3, Strix Sys- imize the interference between neighboring APs by reduc- tems' Access/One Network [1] and Alcatel OmniAccess'Air ing transmission power on individual APs when possible View Software [2. At a high-level, these products aim The strawman power control algorithm we develop, called detect interference and adapt to it by altering the transmit Power-controlled Estimated Rate Fallback(PERF), reduces power levels on the access points. Some of them(e. g, Ac- ransmission power as long as the link between an AP and cess/One)have additional support for load management and client can maintain the maximum possible speed(11Mbps effective coverage(or "coverage hole management")across for 802.11b). Experiments with an implementation of PERF multiple APs deployed throughout an enterprise network. show that it can significantly improve the performance ob- However, most of these products are tailor-made for specifi served by clients of APs that are close to each other. For hardware(for example, Air View comes embedded in all Al- example, we show that a highly utilized AP-client pair near catel OmniAcess hardware) and little is known about the another such pair can see its throughput increase from 0. 15 (proprietary) designs of these products. Also, these prod- Mbps to 3.5 Mbps. In general, we use the term self man ucts are targeted primarily at large deployments with several agement to refer to unilateral automatic configuration of tens of clients accessing and sharing a wireless network. key access point properties, such as transmission power an Also, in the past, several rate adaptation mechanisms that channel. We believe that incorporating mechanisms for self- leverage the multiple rates supported by 802.11 have been management into future wireless devices could go a long way proposed. For example, Sadeghi et al. 31 study new multi- toward improving end-user performance in chaotic networks. rate adaptation algorithms to improve throughput perfor-include choosing relatively simple parameters such as SSID and channel, and more complex questions such as number and placement of APs, and power control. Other aspects of management include troubleshoot￾ing, adapting to changes in the environment and traffic load, and making the wireless network secure. We use the term chaotic deployments or chaotic networks to refer to a collection of wireless networks with the above properties. Such deployments provide many unique oppor￾tunities. For example, they may enable new techniques to determine location [22] or can provide near ubiquitous wireless connectivity. However, they also create numerous challenges. As wireless networks become more common and more densely packed, more of these chaotic deployments will suffer from serious contention, poor performance, and secu￾rity problems. This will hinder the deployment and use of these infrastructures, negating many of the benefits offered by wireless networks. The main goal of this paper is to show that interference in chaotic 802.11 deployments can significantly affect end￾user performance. To this end, we first use large-scale mea￾surements of 802.11 APs deployed in several US cities, to quantify current density of deployment, as well as configu￾ration characteristics, of 802.11 hardware. Our analysis of the data shows that regions with tens of APs deployed in close proximity of each other already exist in most major cities. Also, most 802.11 users employ default, factory-set configurations for key parameters such as the transmission channel. Interestingly, we find that relatively new wireless technology (e.g., 802.11g) gets deployed very quickly. We then simulate the measured deployment and config￾uration patterns to study the impact that unplanned AP deployments have on end-user performance. While it is true that the impact on end-user performance depends on the workloads imposed by users on their network, we do find that even when the APs in an unplanned deployment are carefully configured to use the optimal static channel assign￾ment, users may experience significant performance degra￾dation, e.g. by as much of a factor of 3 in throughput. This effect is especially pronounced when AP density (and asso￾ciated client density) is high and the traffic load is heavy. To improve end-user performance in chaotic deployments, we explore the use of algorithms that automatically man￾age the transmission power levels and transmissions rates of APs and clients. In combination with careful channel assignment, our power control algorithms attempt to min￾imize the interference between neighboring APs by reduc￾ing transmission power on individual APs when possible. The strawman power control algorithm we develop, called Power-controlled Estimated Rate Fallback (PERF), reduces transmission power as long as the link between an AP and client can maintain the maximum possible speed (11Mbps for 802.11b). Experiments with an implementation of PERF show that it can significantly improve the performance ob￾served by clients of APs that are close to each other. For example, we show that a highly utilized AP-client pair near another such pair can see its throughput increase from 0.15 Mbps to 3.5 Mbps. In general, we use the term self man￾agement to refer to unilateral automatic configuration of key access point properties, such as transmission power and channel. We believe that incorporating mechanisms for self￾management into future wireless devices could go a long way toward improving end-user performance in chaotic networks. The rest of the paper is structured as follows. We present related work in Section 2. In Section 3 we characterize the density and usage of 802.11 hardware across various US cities. Section 4 presents a simulation study of the ef￾fect of dense unmanaged 802.11 deployments on end-user performance. We present an analysis of power control in two-dimensional grid-like deployment in Section 5. In Sec￾tion 6, we outline the challenges involved in making chaotic deployments self-managing. We describe our implementa￾tion of rate adaptation and power management techniques in Section 7. Section 8 presents an experimental evalua￾tion of these techniques. We discuss other possible power control algorithms in Section 9 and conclude the paper in Section 10. 2. RELATED WORK In this section, we first discuss current efforts to map 802.11 deployments. Then, we present an overview of com￾mercial services and products for managing networks in gen￾eral, and wireless networks in particular. Finally, we con￾trast our proposal for wireless self management (i.e., trans￾mission power control and multi-rate adaptation) with re￾lated past approaches. Several Internet Web sites provide street-level maps of WiFi hot-spots in various cities. Popular examples include WifiMaps [8], Wi-Fi-Zones.com [7] and JIWire.com [6]. Sev￾eral vendors also market products targeted at locating wire￾less networks while on the go (see for example, Intego WiFi Locator [5]. Among research studies, the Intel Place Lab project [22] [11] maintains a database of up to 30,000 802.11b APs from several US cities. In this paper, we use hot-spot data from WifiMaps.com, as well as the Intel Place Lab database of APs, to infer deployment and usage characteris￾tics of 802.11 hardware. To the best of our knowledge, ours is the first research study to quantify these characteristics. We describe our data sets in greater detail in Section 3. The general problem of automatically managing and con- figuring devices has been well-studied in the wired network￾ing domain. While many solutions exist [35, 33] and have been widely deployed [16], a number of interesting research problems in simplifying network management still remain (e.g., [13, 30]). Our work in this paper compliments these results by extending them to the wireless domain. In the wireless domain, several commercial vendors mar￾ket automated network management software for APs. Ex￾amples include Propagate Networks’ Autocell [3], Strix Sys￾tems’ Access/One Network [1] and Alcatel OmniAccess’ Air￾View Software [2]. At a high-level, these products aim to detect interference and adapt to it by altering the transmit power levels on the access points. Some of them (e.g., Ac￾cess/One) have additional support for load management and effective coverage (or “coverage hole management”) across multiple APs deployed throughout an enterprise network. However, most of these products are tailor-made for specific hardware (for example, AirView comes embedded in all Al￾catel OmniAcess hardware) and little is known about the (proprietary) designs of these products. Also, these prod￾ucts are targeted primarily at large deployments with several tens of clients accessing and sharing a wireless network. Also, in the past, several rate adaptation mechanisms that leverage the multiple rates supported by 802.11 have been proposed. For example, Sadeghi et al. [31] study new multi￾rate adaptation algorithms to improve throughput perfor-