《计算机网络》课程教学资源（参考文献）Self-Management in Chaotic Wireless Deployments

Self-Management in Chaotic Wireless Deployments Aditya Akella Glenn Judd Srinivasan Seshan Peter Steenkiste Carnegie Mellon University Aditya, glenn, srini+, prs/ @cs ⊥ BSTRACT Keywords Over the past few years, wireless networking technologie access points, interference, power control, channel assign- lave made vast forays into our daily lives. Today, one can ad 802.11 hardware and other personal wireless technolog mployed at homes, shopping malls, coffee shops and air- 1. INTRODUCTION ports. Present-day wireless network deployments bear two rties: th Wireless data networking technology is ideal for many en- points(aPs) deployed by users in a spontaneous manner, vironments, including homes, airports, and shopping malls esulting in highly variable AP densities; and they are un because it is inexpensive, easy to install (no wires), and sup- managed, since manually configuring and managing a wire- ports mobile users. As a result, we have seen a sharp increase less network is very complicated. We refer to such wireless in the use of wireless over the past few years. However, us- ing wireless technology effectively is surprisingly difficult In this paper, we present a study of the impact of in- First, wireless links are susceptible to degradation(e.g,at- terference in chaotic 802.11 deployments on end-client per- tenuation and fading) and interference, both of which can formance.First, using large-scale measurement data from result in poor and unpredictable performance. Second, since several cities. we show that it is not uncommon to have tens wireless deployments must share the relatively scarce spec- of APs deployed in close proximity of each other. More- trum resources that are available for public use, they ofter interfere with each other. These factors become especially challenging in deployments where wireless devices such as tions to show that the performance of end-clients could suf- access points(APs)are placed in very close proximity. ter significantly in chaotic deployments. We argue that end In the past, most dense deployments of wireless networks client experience could be significantly improved by mak were in campus-like environments, where experts could care- ing chaotic wireless networks self-managing. We design and lly ge interference by planning cell layout, sometimes evaluate automated power control and rate adaptation al- using special tools [18]. However, the rapid deployment of gorithms to minimize interference among neighboring APs, cheap 802.11 hardware and other while ensuring robust end-client performance ogy(2.4GHz cordless phones, bluetooth devices, etc. )is quickly changing the wireless landscape. Market estimates indicate that approximately 4.5 million WiFi APs were sold Categories and Subject descriptors during the 3rd quarter of 2004 alone [21 and that the sales C 2 [Computer Systems Organization of WiFi equipment will triple by 2009[14. The resulting Computer-Communication Networks; dense deployment of wireless networking equipment in ar- C.2.1 Computer-Communication Networks eas such as neighborhoods, shopping malls, and apartment Network Architecture and Design: buildings differs from past dense campus-like deployments Wireless communication In two important ways General terms Unplanned. While campus deployments are planned to optimize coverage and minimi Measurement, Performance, Experimentation lap, many recent deployments result from ine or independent organizations each setting DAAD19-02-1-0389, and by the NSF under grant numbers ANl-0092678 small number of APs. This type of spontaneous de- CCR-0205266, and CNS-0434824, as well as by IBM and Intel. ployment results in highly variable densities of wireless nodes and APs and in some cases. these densities can digital or hard copies or part of this work become very high(e. g. urban environments, apart- om use is granted without fee provided that copies ment buildings). Moreover, 802.11 nodes have to share are not made ributed for or commercial advantage and that the spectrum with other networking technologies(e. g les bear this notice and the full citation on the first h, to post on servers or to redistribute to lists, requires Bluetooth, UWB)and devices(e. g, cordless phones 2, 2005, Cologne, Germany. Unmanaged. Configuring and managing wireless net- 93-0205/050008.$500 works is difficult for most people. Management issues

Self-Management in Chaotic Wireless Deployments Aditya Akella Glenn Judd Srinivasan Seshan Peter Steenkiste Carnegie Mellon University {aditya, glennj, srini+, prs}@cs.cmu.edu ABSTRACT Over the past few years, wireless networking technologies have made vast forays into our daily lives. Today, one can find 802.11 hardware and other personal wireless technology employed at homes, shopping malls, coffee shops and air￾ports. Present-day wireless network deployments bear two important properties: they are unplanned, with most access points (APs) deployed by users in a spontaneous manner, resulting in highly variable AP densities; and they are un￾managed, since manually configuring and managing a wire￾less network is very complicated. We refer to such wireless deployments as being chaotic. In this paper, we present a study of the impact of in￾terference in chaotic 802.11 deployments on end-client per￾formance. First, using large-scale measurement data from several cities, we show that it is not uncommon to have tens of APs deployed in close proximity of each other. More￾over, most APs are not configured to minimize interference with their neighbors. We then perform trace-driven simula￾tions to show that the performance of end-clients could suf￾fer significantly in chaotic deployments. We argue that end￾client experience could be significantly improved by mak￾ing chaotic wireless networks self-managing. We design and evaluate automated power control and rate adaptation al￾gorithms to minimize interference among neighboring APs, while ensuring robust end-client performance. Categories and Subject Descriptors C.2 [Computer Systems Organization]: Computer-Communication Networks; C.2.1 [Computer-Communication Networks]: Network Architecture and Design; Wireless communication General Terms Measurement, Performance, Experimentation This work was supported by the Army Research Office under grant number DAAD19-02-1-0389, and by the NSF under grant numbers ANI-0092678, CCR-0205266, and CNS-0434824, as well as by IBM and Intel. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. MobiCom’05, August 28–September 2, 2005, Cologne, Germany. Copyright 2005 ACM 1-59593-020-5/05/0008 ...$5.00. Keywords access points, interference, power control, channel assign￾ment 1. INTRODUCTION Wireless data networking technology is ideal for many en￾vironments, including homes, airports, and shopping malls because it is inexpensive, easy to install (no wires), and sup￾ports mobile users. As a result, we have seen a sharp increase in the use of wireless over the past few years. However, us￾ing wireless technology effectively is surprisingly difficult. First, wireless links are susceptible to degradation (e.g., at￾tenuation and fading) and interference, both of which can result in poor and unpredictable performance. Second, since wireless deployments must share the relatively scarce spec￾trum resources that are available for public use, they often interfere with each other. These factors become especially challenging in deployments where wireless devices such as access points (APs) are placed in very close proximity. In the past, most dense deployments of wireless networks were in campus-like environments, where experts could care￾fully manage interference by planning cell layout, sometimes using special tools [18]. However, the rapid deployment of cheap 802.11 hardware and other personal wireless technol￾ogy (2.4GHz cordless phones, bluetooth devices, etc.) is quickly changing the wireless landscape. Market estimates indicate that approximately 4.5 million WiFi APs were sold during the 3rd quarter of 2004 alone [21] and that the sales of WiFi equipment will triple by 2009 [14]. The resulting dense deployment of wireless networking equipment in ar￾eas such as neighborhoods, shopping malls, and apartment buildings differs from past dense campus-like deployments in two important ways: • Unplanned. While campus deployments are carefully planned to optimize coverage and minimize cell over￾lap, many recent deployments result from individuals or independent organizations each setting up one or a small number of APs. This type of spontaneous de￾ployment results in highly variable densities of wireless nodes and APs and, in some cases, these densities can become very high (e.g. urban environments, apart￾ment buildings). Moreover, 802.11 nodes have to share the spectrum with other networking technologies (e.g., Bluetooth, UWB) and devices (e.g., cordless phones). • Unmanaged. Configuring and managing wireless net￾works is difficult for most people. Management issues

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-

Data set Collected No. of aps Stats collected per AP Place lab 28475 MAC. ESSID. GPS coordinate Aug 200 MAC, ESSID, Channel Pittsburgh Wardrive 2004 AC. ESSID. Channel ported rates, GPS coordinates Table 1: Characteristics of the data sets mance in ad hoc networks. Our rate control algorithms, in uploaded by independent users onto street-level data contrast, are designed specifically to work well in conjunc from the uS Census. We obtained access to the com- tion with power control. However, it is possible to extend plete database of wardriving data maintained at this past algorithms such as [31] to support power control. website as of August 2004. For each AP, the database Similarly, traffic scheduling algorithms have been proposed provides the AP's geographic coordinates, zip code, its to optimize battery power in sensor networks, as well wireless network ID(ESSID), channel(s)employed and 02. networks(see, for example, 28, 25 ). In contrast,our the Mac address focus in this paper is not on saving energy, per se. Instead we develop power control algorithms that enable efficient use 3. Pittsburgh Wardrive: This data set was collected of the wireless spectrum in dense wireless networks. on July 29, 2004, as part of a small-scale wardriving ef- In general, ad hoc networks have recently received a great fort which covered a few densely populated residential deal of attention and the issues of power and rate control areas of Pittsburgh. For each unique AP measured, we have been also studied in the context of ad hoc routing pro again collected the GPS coordinates, the ESSID, the tocols, e.g. 24, 15, 32, 20. There are, however, significant MAC address and the channel employed differences between ad hoc networks and chaotic networks First, ad hoc networks are multi-hop while our focus is on 3.2 Measurement Observations AP-based infrastructure networks. Moreover. nodes in ad In this section, we analyze our data sets to identify real- hoc networks are often power limited and mobile. In con- world deployment properties that are relevant to the efficient trast, the nodes in chaotic networks will typically have functioning of wireless networks. The reader should note ited mobility and sufficient power. Finally, most ad hoc that data analyzed here provides a gross underestimate of networks consist of nodes that are willing to cooperate. In ly real-world efficiency problem. First, none of above data contrast, chaotic networks involve nodes from many organi- ts are complete-they may fail to identify many APs that ations, which are competing for bandwidth and spectrum re present and they certainly do not identify non-802.11 As we will see in Section 6, this has a significant impact on devices that share the same spectrum. Second, the density of the design of power and rate control algorithms wireless devices is increasing at a rapid rate, so contention in chaotic deployments will certainly increase dramatically as 3. CHARACTERIZING CURRENT 802.11 well. Because of these properties, we believe these data sets DEPLOYMENTS will lead us to underestimate deployment density. However, these data sets are not biased in any specific way and we To better understand the problems created by chaotic de- expect our other results(e.g. channel usage, AP vendor and ployment, we collect and analyze data about 802.11 AP 802. 11g deployment) to be accurate deployment in a set of metropolitan areas. In this section, we present preliminary observations of the density of APs 3.2.1 802.11 Deployment Density in these metropolitan areas, as well as typical usage char- First, we use the location information in the Place Lab acteristics, such as the channels used for transmission and data set to identify how many APs are within interference common vendor types range of each other. For this analysis, we conservatively set 3.1 Measurement Data Sets the interference range to 50m, which is considered typical of indoor deployments. We assume two nodes to be "neigh- We use three separate measurement data sets to quantify bors"if they are within each other's interference range.We the deployment density and usage of APs in various U.S. then use this neighborhood relationship to construct"inter- cities. The characteristics of the data sets are outlined in ference graphs"in various cities Table 1. a brief description of the data sets follows The results for the analysis of the interference graphs in 1. Place Lab: This data set contains a list of 80211b six uS cities are shown in Table 2. On average we note 240 APs located in various US cities, along with their GPs APs in each city from the Place Lab dataset. The third coordinates, The data was collected as part of Intel's column of Table 2 identifies the maximum degree of any AP Place Lab project [22 [11 in June 2004. The Place Lab software allows commodity hardware clients like other APs in interfering range). In Boston and San Diego notebooks, PDAs and cell phones to locate themselves for example, a particular wireless AP suffers interference by listening for radio beacons such as 802.11 APs from about 80 other APs deployed in close proximity GSM cell phone towers, and fixed Bluetooth devices. In Figure 1, we plot a distribution of the degrees of AP asured in the Place Lab data set. In most cities, we fine 2. WifMaps: The WifiMaps. com website [8 provides several hundreds of APs with a degree of at least 3. In a GIs visualization tool, to map wardriving results Portland, for example, we found that more than half of the

Data set Collected No. of APs Stats collected per AP on Place Lab Jun 2004 28475 MAC, ESSID, GPS coordinates WifiMaps Aug 2004 302934 MAC, ESSID, Channel Pittsburgh Wardrive Jul 2004 667 MAC, ESSID, Channel supported rates, GPS coordinates Table 1: Characteristics of the data sets mance in ad hoc networks. Our rate control algorithms, in contrast, are designed specifically to work well in conjunc￾tion with power control. However, it is possible to extend past algorithms such as [31] to support power control. Similarly, traffic scheduling algorithms have been proposed to optimize battery power in sensor networks, as well as 802.11 networks (see, for example, [28, 25]). In contrast, our focus in this paper is not on saving energy, per se. Instead we develop power control algorithms that enable efficient use of the wireless spectrum in dense wireless networks. In general, ad hoc networks have recently received a great deal of attention and the issues of power and rate control have been also studied in the context of ad hoc routing pro￾tocols, e.g. [24, 15, 32, 20]. There are, however, significant differences between ad hoc networks and chaotic networks. First, ad hoc networks are multi-hop while our focus is on AP-based infrastructure networks. Moreover, nodes in ad hoc networks are often power limited and mobile. In con￾trast, the nodes in chaotic networks will typically have lim￾ited mobility and sufficient power. Finally, most ad hoc networks consist of nodes that are willing to cooperate. In contrast, chaotic networks involve nodes from many organi￾zations, which are competing for bandwidth and spectrum. As we will see in Section 6, this has a significant impact on the design of power and rate control algorithms. 3. CHARACTERIZING CURRENT 802.11 DEPLOYMENTS To better understand the problems created by chaotic de￾ployments, we collect and analyze data about 802.11 AP deployment in a set of metropolitan areas. In this section, we present preliminary observations of the density of APs in these metropolitan areas, as well as typical usage char￾acteristics, such as the channels used for transmission and common vendor types. 3.1 Measurement Data Sets We use three separate measurement data sets to quantify the deployment density and usage of APs in various U.S. cities. The characteristics of the data sets are outlined in Table 1. A brief description of the data sets follows: 1. Place Lab: This data set contains a list of 802.11b APs located in various US cities, along with their GPS coordinates. The data was collected as part of Intel’s Place Lab project [22] [11] in June 2004. The Place Lab software allows commodity hardware clients like notebooks, PDAs and cell phones to locate themselves by listening for radio beacons such as 802.11 APs, GSM cell phone towers, and fixed Bluetooth devices. 2. WifiMaps: The WifiMaps.com website [8] provides a GIS visualization tool, to map wardriving results uploaded by independent users onto street-level data from the US Census. We obtained access to the com￾plete database of wardriving data maintained at this website as of August 2004. For each AP, the database provides the AP’s geographic coordinates, zip code, its wireless network ID (ESSID), channel(s) employed and the MAC address. 3. Pittsburgh Wardrive: This data set was collected on July 29, 2004, as part of a small-scale wardriving ef￾fort which covered a few densely populated residential areas of Pittsburgh. For each unique AP measured, we again collected the GPS coordinates, the ESSID, the MAC address and the channel employed. 3.2 Measurement Observations In this section, we analyze our data sets to identify real￾world deployment properties that are relevant to the efficient functioning of wireless networks. The reader should note that data analyzed here provides a gross underestimate of any real-world efficiency problem. First, none of above data sets are complete—they may fail to identify many APs that are present and they certainly do not identify non-802.11 devices that share the same spectrum. Second, the density of wireless devices is increasing at a rapid rate, so contention in chaotic deployments will certainly increase dramatically as well. Because of these properties, we believe these data sets will lead us to underestimate deployment density. However, these data sets are not biased in any specific way and we expect our other results (e.g. channel usage, AP vendor and 802.11g deployment) to be accurate. 3.2.1 802.11 Deployment Density First, we use the location information in the Place Lab data set to identify how many APs are within interference range of each other. For this analysis, we conservatively set the interference range to 50m, which is considered typical of indoor deployments. We assume two nodes to be “neigh￾bors” if they are within each other’s interference range. We then use this neighborhood relationship to construct “inter￾ference graphs” in various cities. The results for the analysis of the interference graphs in six US cities are shown in Table 2. On average we note 2400 APs in each city from the Place Lab dataset. The third column of Table 2 identifies the maximum degree of any AP in the six cities (where the degree of an AP is the number of other APs in interfering range). In Boston and San Diego, for example, a particular wireless AP suffers interference from about 80 other APs deployed in close proximity. In Figure 1, we plot a distribution of the degrees of APs measured in the Place Lab data set. In most cities, we find several hundreds of APs with a degree of at least 3. In Portland, for example, we found that more than half of the

Number of aps Max ap degree Max connected No. of connected (i. e,# neighbors) omponent size components Portland 8683 54 San Diego 34 76 93 1345 San Francisco Table 2: Statistics for APs measured in 6 US cities(Place Lab data set 1.03 1.13 1.15 1.12 1.31 3.4 Table 3: Channels employed by APs in the Wifimaps Figure 1: Distribution of AP degrees(Place Lab data set classified APs, or about 93, are 802.11g. Given the rela- tively recent standardization of 802.11g(June 2003), these 8683 nodes measured had 3 or more neighbors. Since only measurements suggest that new wireless technology gets de- three of the 802. 11b channels are non-overlapping(channel ployed relatively quickly. 1, 6 and 11), these nodes will interfere with at least one other node in their vicinity 3.2. 4 Vendors and AP Management Support The fourth column in Table 2 shows the size of the max. Vendor mum connected component in the interference graph of a Percentage of APs ty. The final column shows the number of connected com- nents in the interference graph. From these statistics, we Linksys( Cisco) find several large groups of APs deployed in close proxim Aironet(Cisco) 122 ty. Together, these statistics show that dense deployments 96 of 802. 11 hardware have already begun to appear in urban D-Link settings. As mentioned earlier, we expect the density to ole Computer continue to increase rapidly. Netgear AN Communications 3 3.2.2 802.11 Usage: Channels Delta Networks Table 3 presents the distribution of channels used by APs the WiFiMaps data set. This provides an indication of I Acer whether users of APs manage their networks at all. Notice Others hat many APs transmit on channel 6, the default on many channels in 802. 11b(i.e, channels 1 and 11). While this does Table 4: Popular AP vendors(Wifimaps data set) ntify particular conflicts, this distribution suggests that many of the APs that overlap in coverage are probably To determine popular AP brands, we look up the MAC ad- dresses available in the wifimaps data set against the ieee Company -id assignments [4] to classify each AP according to 3.2.3802.bws.802.lg the vendor. For the aps that could be classified in this man- The Pittsburgh wardrive data set contains information ner(2% of the APs in the Wifimaps data set did not have about rates supported for about 71% of the measured APs, a matching vendor name), the distribution of the vendors is or 472 out of the 667. We use this information to classify shown in Table 4. Notice that Cisco products(Linksys and these APs as 802. 11b or 802.11g. We find that 20% of the Aironet)make up nearly half of the market. This observa

City Number of APs Max AP degree Max. connected No. of connected (i.e., # neighbors) component size components Chicago 2370 42 54 369 Washington D.C. 2177 20 226 162 Boston 2551 85 168 320 Portland 8683 54 1405 971 San Diego 7934 76 93 1345 San Francisco 3037 39 409 186 Table 2: Statistics for APs measured in 6 US cities (Place Lab data set) 0 1000 2000 3000 4000 5000 6000 7000 2 4 6 8 10 12 14 16 18 20 Nodes with d >= x Degree Boston Chicago Portland San Diego San Francisco Wash D.C. Figure 1: Distribution of AP degrees (Place Lab data set) 8683 nodes measured had 3 or more neighbors. Since only three of the 802.11b channels are non-overlapping (channel 1, 6 and 11), these nodes will interfere with at least one other node in their vicinity. The fourth column in Table 2 shows the size of the max￾imum connected component in the interference graph of a city. The final column shows the number of connected com￾ponents in the interference graph. From these statistics, we find several large groups of APs deployed in close proxim￾ity. Together, these statistics show that dense deployments of 802.11 hardware have already begun to appear in urban settings. As mentioned earlier, we expect the density to continue to increase rapidly. 3.2.2 802.11 Usage: Channels Table 3 presents the distribution of channels used by APs in the WiFiMaps data set. This provides an indication of whether users of APs manage their networks at all. Notice that many APs transmit on channel 6, the default on many APs, and only 14% use the remaining two non-overlapping channels in 802.11b (i.e., channels 1 and 11). While this does not identify particular conflicts, this distribution suggests that many of the APs that overlap in coverage are probably not configured to minimize interference. 3.2.3 802.11b vs. 802.11g The Pittsburgh wardrive data set contains information about rates supported for about 71% of the measured APs, or 472 out of the 667. We use this information to classify these APs as 802.11b or 802.11g. We find that 20% of the Channel Percentage of APs 1 3.04 2 12.29 3 3.61 4 1.03 5 1.13 6 41.15 7 1.75 8 1.12 9 1.31 10 3.42 11 11.04 Table 3: Channels employed by APs in the Wifimaps data set. classified APs, or about 93, are 802.11g. Given the rela￾tively recent standardization of 802.11g (June 2003), these measurements suggest that new wireless technology gets de￾ployed relatively quickly. 3.2.4 Vendors and AP Management Support Vendor Percentage of APs Total classified 98 Linksys (Cisco) 33.5 Aironet (Cisco) 12.2 Agere Systems 9.6 D-Link 4.9 Apple Computer 4.6 Netgear 4.4 ANI Communications 4.3 Delta Networks 3.0 Lucent 2.5 Acer 2.3 Others 16.7 Table 4: Popular AP vendors (Wifimaps data set) To determine popular AP brands, we look up the MAC ad￾dresses available in the Wifimaps data set against the IEEE Company id assignments [4] to classify each AP according to the vendor. For the APs that could be classified in this man￾ner (2% of the APs in the Wifimaps data set did not have a matching vendor name), the distribution of the vendors is shown in Table 4. Notice that Cisco products (Linksys and Aironet) make up nearly half of the market. This observa-

tion suggests that if future products from this vendor incor- In order to quantify the impact of the deployment and porated built-in mechanisms for self-management of wireless usag s ce obse haracteristics of 802.11b APs on the Internet per- networks this could significantly limit the impact of inter- ved by end- ference in chaotic deployments simulations using the publicly available GloMoSim simula To understand if specific models incorporate software for tor [17]. We simulated the deployment topology shown in configuration and management of wireless networks, we sur- Figure 2(a), obtained during a portion of the Pittsburgh vey the popular APs marketed by the top three vendors in wardrive. There are 20 APs in this topology. We use the Table 4. All products(irrespective of the vendors) come following settings and assumptions in our simulations with software to allow users to configure basic parameters for their wireless networks, such as ESSID, channel and se 1. Each node in the map corresponds to an AP. curity settings. Most"low-end"APs(e.g, those targeted 2. Each AP has D clients (e. g, laptops )associated with for deployment by individual home users)do not include any it. We vary D between 1 and 3. software for automatic configuration and management of the wireless network. Some of the products targeted at enter- 3. Clients are located less than lm away from their re- rise and campus-style deployments, such as Cisco Aironet spective APs and do not move. 350 series, allow more sophisticated, centralized manage- 4. Unless otherwise specified, we assume that all APs ment of parameters such as transmit power levels, select ing non-overlapping channels, etc. across several deploy APs. Since these products are targeted at campuses, they 5. All APs employ a fixed transmit power level of 15dBm are too expensive for use in smaller-scale deployments such unless otherwise specified (This is the default setting s apartment-buildings in most commercial APs) 4. IMPACT ON END-USER PERFORMANCE 6. All APs transmit at a single rate, 2Mbps(there is no lti rate support in GloMoSim). At these setting se tresecsiven and interterence ranges are 3m an 7. RTS/CTS is turned off. This is the default setting in lost commercial APs 240 8. We use a modified two-ray path loss model for large- 230 scale path loss, and a Ricean fading model with a K 220 factor of 0 for small scale fading [29 10 Intuition suggests that the impact of interference in chaotic wireless deployments depends, to a large extent, on the 190 workloads imposed by users. If most APs are involved in 45505560657075 just occasional transmission of data to their users, then it is very likely that users will experience no degradation in (a)20-node topology performance due to interference from nearby APs. A key goal of our simulations, then, is to systematically quantify the precise impact of user workloads on eventual user per 270 formance. To achieve this, we simulate two types of user workloads over the above simulation set-up. These work- loads differ mainly in their relative proportions of Http 240 (representing Web-browsing activity) and FTP(represent- 30 g large file downloads traffic Inthefirstsetofworkloadscalledhttp,weassumethat the clients are running Http sessions across their Aps. The 210 Http fle size distribution is based on a well-known model 200 for Http traffic [26. On a client each Http transfer is 404550556065 separated from the previous one by a think time drawn from a Poisson distribution with a mean of s seconds. We vary s between the values of 5s and 20s(we also simulated Http (b)8-node sub-topology workloads with 10s, 30s and 60s sleep times. The results e qualitatively similar and are omitted for brevity ). The average load offered by the Http client is 83.3kbps for a Figure 2: Simulation topologies derived from the 5s sleep time, and 245Kbps for a 20s sleep time. There is Metropolis wardrive data set; the units on the x and otherinterferingtrafficinthehttpworkload y axis are in meters. Figure(a) shows the 20-node The second set of workloads, called comb-ftpi, is similar topologyderivedfromtheMetropolisWardrivedatatothehttpworkloadwiththeexceptionoficlientsinthe et. Figure(b) shows a sub-topology of 8 node entire set-up running long-lived FTP Alows for the duration hat were all assigned the same channel by a static of the simulation. We vary i between 1 and 3. The av optimal channel assignment algorithm when applied rage load offered by the ftp clients in our simulation is to the 20-node topology in(a) 0. 89Mbps. We simulate either set of workloads for 300s

tion suggests that if future products from this vendor incor￾porated built-in mechanisms for self-management of wireless networks this could significantly limit the impact of inter￾ference in chaotic deployments. To understand if specific models incorporate software for configuration and management of wireless networks, we sur￾vey the popular APs marketed by the top three vendors in Table 4. All products (irrespective of the vendors) come with software to allow users to configure basic parameters for their wireless networks, such as ESSID, channel and se￾curity settings. Most “low-end” APs (e.g., those targeted for deployment by individual home users) do not include any software for automatic configuration and management of the wireless network. Some of the products targeted at enter￾prise and campus-style deployments, such as Cisco Aironet 350 series, allow more sophisticated, centralized manage￾ment of parameters such as transmit power levels, select￾ing non-overlapping channels, etc. across several deployed APs. Since these products are targeted at campuses, they are too expensive for use in smaller-scale deployments such as apartment-buildings. 4. IMPACT ON END-USER PERFORMANCE 190 200 210 220 230 240 250 260 270 280 40 45 50 55 60 65 70 75 y x (a) 20-node topology 190 200 210 220 230 240 250 260 270 280 40 45 50 55 60 65 70 75 y x (b) 8-node sub-topology Figure 2: Simulation topologies derived from the Metropolis wardrive data set; the units on the x and y axis are in meters. Figure (a) shows the 20-node topology derived from the Metropolis Wardrive data set. Figure (b) shows a sub-topology of 8 nodes that were all assigned the same channel by a static optimal channel assignment algorithm when applied to the 20-node topology in (a). In order to quantify the impact of the deployment and usage characteristics of 802.11b APs on the Internet per￾formance observed by end-users, we conducted trace-driven simulations using the publicly available GloMoSim simula￾tor [17]. We simulated the deployment topology shown in Figure 2(a), obtained during a portion of the Pittsburgh wardrive. There are 20 APs in this topology. We use the following settings and assumptions in our simulations: 1. Each node in the map corresponds to an AP. 2. Each AP has D clients (e.g., laptops) associated with it. We vary D between 1 and 3. 3. Clients are located less than 1m away from their re￾spective APs and do not move. 4. Unless otherwise specified, we assume that all APs transmit on channel 6. 5. All APs employ a fixed transmit power level of 15dBm, unless otherwise specified (This is the default setting in most commercial APs). 6. All APs transmit at a single rate, 2Mbps (there is no multi rate support in GloMoSim). At these settings, the transmission and interference ranges are 31m and 65m, respectively. 7. RTS/CTS is turned off. This is the default setting in most commercial APs. 8. We use a modified two-ray path loss model for large￾scale path loss, and a Ricean fading model with a K￾factor of 0 for small scale fading [29]. Intuition suggests that the impact of interference in chaotic wireless deployments depends, to a large extent, on the workloads imposed by users. If most APs are involved in just occasional transmission of data to their users, then it is very likely that users will experience no degradation in performance due to interference from nearby APs. A key goal of our simulations, then, is to systematically quantify the precise impact of user workloads on eventual user per￾formance. To achieve this, we simulate two types of user workloads over the above simulation set-up. These work￾loads differ mainly in their relative proportions of HTTP (representing Web-browsing activity) and FTP (represent￾ing large file downloads) traffic. In the first set of workloads, called http, we assume that the clients are running HTTP sessions across their APs. The HTTP file size distribution is based on a well-known model for HTTP traffic [26]. On a client, each HTTP transfer is separated from the previous one by a think time drawn from a Poisson distribution with a mean of s seconds. We vary s between the values of 5s and 20s (We also simulated HTTP workloads with 10s, 30s and 60s sleep times. The results are qualitatively similar and are omitted for brevity). The average load offered by the HTTP client is 83.3Kbps for a 5s sleep time, and 24.5Kbps for a 20s sleep time. There is no other interfering traffic in the http workload. The second set of workloads, called comb-ftpi, is similar to the http workload with the exception of i clients in the entire set-up running long-lived FTP flows for the duration of the simulation. We vary i between 1 and 3. The av￾erage load offered by the FTP clients in our simulation is 0.89Mbps. We simulate either set of workloads for 300s

4.1 Interference at Low Client-Densities and can be viewed as the amount of work a user completed dur- Traffic Volumes ing a fixed time interval, relative to the maximum achievable work Noticethatforworkloadswithan"aggressivehttp 0.1 omponent(.e, think time of 5s), the performance of the 0806 Http flows improves until stretch= 10; beyond this point performance stays relatively flat For less aggressive Http a淀 workloads (i.e, think interval of 20s), the impact on the performance of the Http fows is less severe Th mance of the FTP flow in comb-ftpI workload is Figure 3(b). when the Http component of this 图03 慨二暑 is aggressive(s= 5s), the performance of the lone shown in 0.02 suffersbyabout17%.Withanot-so-aggressivehttpcOm- ponent, as expected, the impact on the FTP flow is minimal So far, we studied the impact of interference under rela ively light-weight" user traffic at each access points. In he next two sections, we vary two important factors deter (a)http,D=l mining the client load-the density of clients per AP and he traffic volume of the clients-to create more aggressive 0.8 4.2 Impact of Client Densities and Traffic Load 0.5 04 R03 0.2 0.1 暑齿邑图西善 (b)FTP, D=1 Figure 3: aveRage performance of Http and Ftp Stretch Hows at low client densities (D= 1) and low levels (a)httpperformance ofcompetingFtptraffic(httpandcomb-ftpiwork Firstweconductsimulationswiththehttpandcomb-ftpl 0.8 workloads, and low client densities(D= 1). The results are 0.7 hown in Figure 3. The performance measurements are the verage of 5 different simulation runs; the variance between 0.5 runs is not shown since it was low. The x-axis in these pic 04 tures is the "stretch"parameter which allows us to tune the 0.3 density of APs per square meter in a given simulation. A 0.2 simulation with a stretch of I indicates that the distance be s: 5S, WL: comb ftp S: 20S, WL: comb ftp tween a pair of APs in the simulation topology is a factor of t larger than the actual distance in the original topology. The 12345678910 distance between an ap and its clients does not change. The higher the value of stretch, the lower the likelihood of inter (b)FTP performance ference between nodes in the simulation topology. For the opology in Figure 2(a), we note that at stretch a 20, the odes are completely out of each others interference range Figure 4: Average performance of Http and Ftp Also, in our simulations, beyond stretch= 10, we see little fows at greater client densities(D= 3) impact of interference between nodes on user performance In either figure, the y-axis shows the average normalized Impact of client density. Figures 4(a)and(b)show the formance of Http(fIgurE(a))or Ftp flows(figure(b)) verage performance of the individual Http and Ftp ses inoursimulationsNormalizedHttp(Ftp)PerfOrmancesions,respectivelyinthecomb-ftpiandhttpworkloadsfor is simply the ratio of the average throughput of an Http a high number of clients associated per Ap(d=3. the Ftp)fOw to the throughput achieved by an Ftp bulk performance of both Http and Ftp flows suffers signifi- transfer when operating in isolation i. e., 0.89mbps. This cantly under high client densities From Figure 4(a), Http

4.1 Interference at Low Client-Densities and Traffic Volumes 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 1 2 3 4 5 6 7 8 9 10 Normalized HTTP Performance Stretch s: 5S, WL: http s: 5S, WL: comb ftp1 s: 20S, WL: http s: 20S, WL: comb ftp1 (a) HTTP, D = 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Normalized FTP Performance Stretch s: 5S, WL: comb ftp1 s: 20S, WL: comb ftp1 (b) FTP, D = 1 Figure 3: Average performance of HTTP and FTP flows at low client densities (D = 1) and low levels of competing FTP traffic (http and comb−f tp1 work￾loads). First, we conduct simulations with the http and comb-ftp1 workloads, and low client densities (D = 1). The results are shown in Figure 3. The performance measurements are the average of 5 different simulation runs; the variance between runs is not shown since it was low. The x-axis in these pic￾tures is the “stretch” parameter which allows us to tune the density of APs per square meter in a given simulation. A simulation with a stretch of l indicates that the distance be￾tween a pair of APs in the simulation topology is a factor of l larger than the actual distance in the original topology. The distance between an AP and its clients does not change. The higher the value of stretch, the lower the likelihood of inter￾ference between nodes in the simulation topology. For the topology in Figure 2(a), we note that at stretch ≈ 20, the nodes are completely out of each others’ interference range. Also, in our simulations, beyond stretch = 10, we see little impact of interference between nodes on user performance. In either figure, the y-axis shows the average normalized per￾formance of HTTP (Figure (a)) or FTP flows (Figure (b)) in our simulations. Normalized HTTP (FTP) performance is simply the ratio of the average throughput of an HTTP (FTP) flow to the throughput achieved by an FTP bulk transfer when operating in isolation, i.e., 0.89Mbps. This can be viewed as the amount of work a user completed dur￾ing a fixed time interval, relative to the maximum achievable work. Notice that, for workloads with an “aggressive” HTTP component (i.e., think time of 5s), the performance of the HTTP flows improves until stretch = 10; beyond this point performance stays relatively flat. For less aggressive HTTP workloads (i.e., think interval of 20s), the impact on the performance of the HTTP flows is less severe. The perfor￾mance of the FTP flow in comb-ftp1 workload is shown in Figure 3(b). When the HTTP component of this workload is aggressive (s = 5s), the performance of the lone FTP flow suffers by about 17%. With a not-so-aggressive HTTP com￾ponent, as expected, the impact on the FTP flow is minimal. So far, we studied the impact of interference under rela￾tively “light-weight” user traffic at each access points. In the next two sections, we vary two important factors deter￾mining the client load—the density of clients per AP and the traffic volume of the clients—to create more aggressive interference settings. 4.2 Impact of Client Densities and Traffic Load 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 1 2 3 4 5 6 7 8 9 10 Normalized HTTP Performance Stretch s: 5S, WL: http s: 5S, WL: comb ftp1 s: 20S, WL: http s: 20S, WL: comb ftp1 (a) HTTP performance 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Normalized FTP Performance Stretch s: 5S, WL: comb ftp1 s: 20S, WL: comb ftp1 (b) FTP performance Figure 4: Average performance of HTTP and FTP flows at greater client densities (D = 3). Impact of client density. Figures 4(a) and (b) show the average performance of the individual HTTP and FTP ses￾sions, respectively, in the comb-ftp1 and http workloads, for a high number of clients associated per AP (D = 3). The performance of both HTTP and FTP flows suffers signifi- cantly under high client densities: From Figure 4(a), HTTP

performance is lowered by about 65%(compare stretch= 1 we study if an optimal static allocation of non-overlapping ith stretch 10)due to interference between aggressive channels across APs could eliminate interference altogether Http flows(s=5s). The same is true for the performance Second we present a preliminary investigation of the effect of the Ftp flow in Figure 4(b). For a less aggressive Http of reducing the transmit power levels at Aps on the interfer component(s= 20s)the performance of the Http flows is ence experienced We also investigate how transmit power 0% inferior while the Ftp flow suffers by about 36% control improves the total capacity of a chaotic, network, as well as the fairness in the allocation of the capacity among individual APs 0.09 4.3.1 Effect of Optimal Static Channel Allocation 08 0.07 We performed simulations on the 20-node topology of Fig 06 ure 2(a), where the APs are statically assigned one of the 0.05 three non-overlapping channels(1, 6 and 11)such that no two neighboring APs share a channel, whenever possible. As 003圈哲普吾翻善—每…量: an illustration, Figure 2(b) shows the lay-out of APs that were all assigned channel 1 by this scheme. Stretch (a)httpperformance 5S, W: comb ftp ML: comb ft3“母 0.8 日善醫善…:皇…量… 0.01 5 04 0*术 Stretch VL: comb ftp2 (a)httpperformance 0. pmb ftpa 0s,WL: comb ftp3…母 567 Stretch 0.8 (b)FTP 0.7 0.6 Figure 5: Average performance of Http and ftP 04 Ing (i. s: 5S, WL: comb ftp2 the comb-ftp 2, 3 workloads) and for D=3 0.1 203WCcm出:3- Impact of traffic volume. Figures 5(a) and(b) show 12345678910 the average performance of the Http and Ftp flows re spectively, in simulations with a few more competing FTP Stretch Hows--i.e, the comb-ftp2 and comb-ftps workloads--for (b)FTP performance D=3. The performance impact on Http and Ftp flows hecaseswheretheFigure6:PerformanceofhttpandFtpflowswith ITTP component of these workloads is not very aggressive see the curves corresponding to s= 20s in Figure 5(b)) optimal static assignment of APs to the ree non- overlapping channels. The transmit power level is Using realistic channel assignments. We also performed set at 15dBm, corresponding to a reception range of simulations on the 20-node topology, where the APs were 31m tatically assigned channels based on the distribution in Ta ble 3. However. we note similar levels of interference and The performance of htTp and Ftp flows in these simu pact on performance as observed above. This is because lations are shown in Figure 6(a)and(b), respectively. The more than half the APs in this simulation were assigned average performance of both htTp and Ftp flows improves channel 6, which was the most predominant channel er ployed by most APs according to our measurements significantly. Comparing with Figures 5(a) and(b)respec- tively, we note that the performance curves flatten out earlier on account on the sparse nature of the interference 4.3 Limiting the Impact of Interference graph. Nevertheless, the impact of interference can still be Inthissectionweexploretheeffectoftwosimplemechaseentheaveragehttpperformanceisabout25%inferior nisms on mitigating interference in chaotic networks: First at stretch 1 compared to the case when no nodes inter

performance is lowered by about 65% (compare stretch = 1 with stretch = 10) due to interference between aggressive HTTP flows (s = 5s). The same is true for the performance of the FTP flow in Figure 4(b). For a less aggressive HTTP component (s = 20s) the performance of the HTTP flows is 20% inferior, while the FTP flow suffers by about 36%. 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 1 2 3 4 5 6 7 8 9 10 Normalized HTTP Performance Stretch s: 5S, WL: comb ftp2 s: 5S, WL: comb ftp3 s: 20S, WL: comb ftp2 s: 20S, WL: comb ftp3 (a) HTTP performance 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Normalized FTP Performance Stretch s: 5S, WL: comb ftp2 s: 5S, WL: comb ftp3 s: 20S, WL: comb ftp2 s: 20S, WL: comb ftp3 (b) FTP performance Figure 5: Average performance of HTTP and FTP flows at higher competing FTP traffic levels (i.e., the comb-ftp{2, 3} workloads) and for D = 3. Impact of traffic volume. Figures 5(a) and (b) show the average performance of the HTTP and FTP flows, re￾spectively, in simulations with a few more competing FTP flows—i.e., the comb-ftp2 and comb-ftp3 workloads—for D = 3. The performance impact on HTTP and FTP flows is slightly more pronounced, even for the cases where the HTTP component of these workloads is not very aggressive (see the curves corresponding to s = 20s in Figure 5(b)). Using realistic channel assignments. We also performed simulations on the 20-node topology, where the APs were statically assigned channels based on the distribution in Ta￾ble 3. However, we note similar levels of interference and impact on performance as observed above. This is because more than half the APs in this simulation were assigned channel 6, which was the most predominant channel em￾ployed by most APs according to our measurements. 4.3 Limiting the Impact of Interference In this section, we explore the effect of two simple mecha￾nisms on mitigating interference in chaotic networks: First, we study if an optimal static allocation of non-overlapping channels across APs could eliminate interference altogether. Second, we present a preliminary investigation of the effect of reducing the transmit power levels at APs on the interfer￾ence experienced. We also investigate how transmit power control improves the total capacity of a chaotic, network, as well as the fairness in the allocation of the capacity among individual APs. 4.3.1 Effect of Optimal Static Channel Allocation We performed simulations on the 20-node topology of Fig￾ure 2(a), where the APs are statically assigned one of the three non-overlapping channels (1, 6 and 11) such that no two neighboring APs share a channel, whenever possible. As an illustration, Figure 2(b) shows the lay-out of APs that were all assigned channel 1 by this scheme. 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 1 2 3 4 5 6 7 8 9 10 Normalized HTTP Performance Stretch s: 5S, WL: comb ftp2 s: 5S, WL: comb ftp3 s: 20S, WL: comb ftp2 s: 20S, WL: comb ftp3 (a) HTTP performance 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Normalized FTP Performance Stretch s: 5S, WL: comb ftp2 s: 5S, WL: comb ftp3 s: 20S, WL: comb ftp2 s: 20S, WL: comb ftp3 (b) FTP performance Figure 6: Performance of HTTP and FTP flows with optimal static assignment of APs to the three non￾overlapping channels. The transmit power level is set at 15dBm, corresponding to a reception range of 31m. The performance of HTTP and FTP flows in these simu￾lations are shown in Figure 6(a) and (b), respectively. The average performance of both HTTP and FTP flows improves significantly. Comparing with Figures 5(a) and (b) respec￾tively, we note that the performance curves “flatten out” earlier on account on the sparse nature of the interference graph. Nevertheless, the impact of interference can still be seen: the average HTTP performance is about 25% inferior at stretch = 1 compared to the case when no nodes inter-

feres with another(stretch 10). FTP performance, sim- ilarly, is far from optimal. These observations suggest that while optimal static channel allocation reduces the impact of interference, it cannot eliminate it altogether. 0.7 4.3.2 Impact of Transmit Power Control a0.6 We augment above simulations of optimal static channel 04 allocation with more conservative(lower) power settings on 0.3 the APs: we forced the 8 APs in Figure 2(b)to use a power level of 3dBm. This yields a transmission range of 15n LNEz 0.1 which is half the range from using the default power level of Bn. Next we show how this improves Http and Ftp 12345678910 performance, as well as the total network capacity. (a)FTP performance 0.8 0级Mcm 0.7 05 0.6 0.5 .02 0.3 0.01 01234567851 Transmit pow 12345678910 (a)httpperformance(range=15m) Stretch (b) Fairness Figure 8: Performance FTP Alows with and without optimal channel assignment and ap transmit power control. The workload is composed of FTP flows 65432 between each client and its AP, with D= 1. Fig- ure(a) shows the performance of FTP fows in the simulations. Figure(b) shows the fairness index for S: 5S. W: comb fio3--xk- the throughput achieved by the FTP llows. 0.1 12345678910 a workload composed fully of bulk FTP transfers (i.e, each Stretch AP has one user associated with it, and the AP runs an b)FTP performance(range 15m) FTP bulk transfer to the user). This simulation sheds light on how careful management of APs can improve the total capacity of the network. When APs are completely unman- Figure7:PerformanceofhttpandFtpflows aged, the capacity of a densely packed network rk of aps is with optimal static channel assignment of APs. The only 15% of the maximum capacity(see Figure 8(a)). Static transmit power level is set at 3dBm, corresponding channel allocation of APs improves the capacity two-fold to a reception range of 15m. Lowering the transmit power on APs improves capacity by nearly an additional factor of 2 mprovement in application performance. The perfor Fairness. In Figure8(b), we show the fairness in the through- nanceresultsforhttpandftpflowsinthesesimulationsputsachievedbyindividualFtpFlowstounderstandifthe are shown in Figures 7(a)and(b) respectively. Compared erformance of certain APs in a chaotic deployment suffers with Figures 6(a)and(b), the performance of individual significantly compared to others. Our fairness metric is de- fows improves significantly. The interference among nodes rived from[12 and is defined as gr, where a,'s are the is lowered, as can be seen by both the performance curves throughputs of individual flows flattening out at stretch= 2. These results show that trans- For the highest densities of points, we see that poor mit power control, in conjunction with a good channel allo- cation mechanism, could help reduce the impact of interfer- ence in chaotic networks substantially. e.anagement results in unfair allocation of capacity across ccess points. Channel allocation coupled with transmit power control immediately ensures a highly equitable alloca- Improvement in network capacity. In Figure 8 we show tion: except for the highest density, the fairness of allocation how transmit power control improves user performance for is above 0.9

feres with another (stretch = 10). FTP performance, sim￾ilarly, is far from optimal. These observations suggest that while optimal static channel allocation reduces the impact of interference, it cannot eliminate it altogether. 4.3.2 Impact of Transmit Power Control We augment above simulations of optimal static channel allocation with more conservative (lower) power settings on the APs: we forced the 8 APs in Figure 2(b) to use a power level of 3dBm. This yields a transmission range of 15m, which is half the range from using the default power level of 15dBm. Next, we show how this improves HTTP and FTP performance, as well as the total network capacity. 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 1 2 3 4 5 6 7 8 9 10 Normalized HTTP Performance Stretch s: 5S, WL: comb ftp2 s: 5S, WL: comb ftp3 s: 20S, WL: comb ftp2 s: 20S, WL: comb ftp3 (a) HTTP performance (range = 15m) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Normalized FTP Performance Stretch s: 5S, WL: comb ftp2 s: 5S, WL: comb ftp3 s: 20S, WL: comb ftp2 s: 20S, WL: comb ftp3 (b) FTP performance (range = 15m) Figure 7: Performance of HTTP and FTP flows with optimal static channel assignment of APs. The transmit power level is set at 3dBm, corresponding to a reception range of 15m. Improvement in application performance. The perfor￾mance results for HTTP and FTP flows in these simulations are shown in Figures 7(a) and (b) respectively. Compared with Figures 6(a) and (b), the performance of individual flows improves significantly. The interference among nodes is lowered, as can be seen by both the performance curves flattening out at stretch = 2. These results show that trans￾mit power control, in conjunction with a good channel allo￾cation mechanism, could help reduce the impact of interfer￾ence in chaotic networks substantially. Improvement in network capacity. In Figure 8 we show how transmit power control improves user performance for 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Normalized FTP Performance Stretch Original topology Static channel allocation Transmit power control (a) FTP performance 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 FTP Fairness Stretch Original topology Static channel allocation Transmit power control (b) Fairness Figure 8: Performance FTP flows with and without optimal channel assignment and AP transmit power control. The workload is composed of FTP flows between each client and its AP, with D = 1 . Fig￾ure (a) shows the performance of FTP flows in the simulations. Figure (b) shows the fairness index for the throughput achieved by the FTP flows. a workload composed fully of bulk FTP transfers (i.e., each AP has one user associated with it, and the AP runs an FTP bulk transfer to the user). This simulation sheds light on how careful management of APs can improve the total capacity of the network. When APs are completely unman￾aged, the capacity of a densely packed network of APs is only 15% of the maximum capacity (see Figure 8(a)). Static channel allocation of APs improves the capacity two-fold. Lowering the transmit power on APs improves capacity by nearly an additional factor of 2. Fairness. In Figure 8(b), we show the fairness in the through￾puts achieved by individual FTP flows to understand if the performance of certain APs in a chaotic deployment suffers significantly compared to others. Our fairness metric is de￾rived from [12] and is defined as ( P xi) 2 n P x2 i , where xi’s are the throughputs of individual flows. For the highest densities of access points, we see that poor management results in unfair allocation of capacity across access points. Channel allocation coupled with transmit power control immediately ensures a highly equitable alloca￾tion: except for the highest density, the fairness of allocation is above 0.9

In this sec ed simulations to study the impact determine the minimum physical spacing required between transmit power reduction on network performance. The APs(dmin)to support the specified load key observation from our simulations is that end-user perfor- To compute this, we first calculate the medium utilization mance can suffer significantly in chaotic deployments, espe required by each AP: utilization AP =load/ throughputmar cially when the interference is from aggressive sources(such The maximum throughput is determined by first calculating s bulk FtP transfers). We showed that careful manage th loss from the ap to the client(in dB)as: pathloss ment of APs, via transmit power control (and static channel 40+3.5*10*log(client ) this is based on the pathloss model allocation), could mitigate the negative impact on perfor- from [29 with constants that correspond to measurements e. Moreover, transmit power control can also enable collected in our local environment an equitable allocation of capacity among interfering AP Received signal strength can then be computed as RSs A key draw back of our simulations, however, is the lack of tr Power-pathloss, and the signal-to-noise ratio is SNR= upport for multi-rate adaptation. We further explore the RSS-noise Floor. We choose the noise foor to be -100 benefits of transmit power control in conjunction with multi- dBm, which is typical for our hardware. Using SNR and the rate adaptation in the next section data in Tables 5 and 6(based on measurements presented in g) we then determine the maximum transmission rate 5. BENEFITS OF TRANSMIT POWER RE that can be used for the AP-client link and the correspond g maximum throughput for that rate. DUCTION I Rate(Mbps) Minimum SNR(dB) nediumUtilization= 2(utilization of all in-range APs) Table 5: Minimum required SNR for Prism 2.5 Rate(Mbps) Throughput(Mbps) ○ ○ 1.7 ○ Table 6: Maximum 802.1lb throughput After we have computed the utilization for a single link we determine the medium utilization at each ap by sum- ming the utilization of all in-range APs. We determine that two APs are in range by computing the rss between Figure 9: Computing minimum AP spacing for a them using the same formula used above. We os iger the grid topology nter ferenceThreshold. We set inter ferenceThreshold to 100 dBm for our calculations In this section we use a simple model of wireless Figure 10 shows the results of our calculations for a client unication applied to a two-dimensional grid topology as distance of 10 meters and loads ranging from 0.1 Mbps to shown in Figure 9 to quantify the advantages of transmit 1.1 mbps. Other client distances and loss parameters would ower control. We also model the impact of rate adapta- shift or scale the graph, but the trends would remain the tion. For our analysis, we assume that each AP sends traffic same. The 2, 5.5, and 11 Mbps regions shown near the to a single client at a fixed distance(delient )from the aP. bottom of the chart specify the maximum transmission rate In practice, if this transfer used TCP, we would expect a that can be used for each power level. Consider a specific small amount of traffic from the client to ap due to the point on this graph, such as the point at -15dBm power on TCP acknowledgements the x-axis: using the 1.1 Mbps load line, this translates into As the amount of uplink traffic is small, we only consider a 20m aP distance on the y-axis. This implies that if you the downlink traffic to simplify our analysis. We also ignore want to transmit at 1.1Mbps from each AP at-15dBm, the many real-world effects such as multipath fading and chan- APs must be at least 20m apart in order to avoid overloading nel capture. We do not use these simplifying assumption the wireless link. In addition, the solid-black line parallel to subsequent sections. In particular, we stress that our al- the x-axis indicates that each AP uses a transmission rate of gorithms are designed to operate in a symmetric fashion on 5 5Mbps to communicate with its client. For the simulation both uplink and downlink traffic in the previous section we typically fixed the transmit power We examine a range of transmit power levels and traffic and then increased the stretch; this corresponds to picking loads. For each transmit power level and traffic load pair, we a point on the x-axis and moving up vertically

In this section, we used simulations to study the impact of transmit power reduction on network performance. The key observation from our simulations is that end-user perfor￾mance can suffer significantly in chaotic deployments, espe￾cially when the interference is from aggressive sources (such as bulk FTP transfers). We showed that careful manage￾ment of APs, via transmit power control (and static channel allocation), could mitigate the negative impact on perfor￾mance. Moreover, transmit power control can also enable an equitable allocation of capacity among interfering APs. A key drawback of our simulations, however, is the lack of support for multi-rate adaptation. We further explore the benefits of transmit power control in conjunction with multi￾rate adaptation in the next section. 5. BENEFITS OF TRANSMIT POWER RE￾DUCTION AP dclient mediumUtilization = ￾ (utilization of all in-range APs) Interference range of AP transmission to client at given power level. dmin Figure 9: Computing minimum AP spacing for a grid topology In this section we use a simple model of wireless com￾munication applied to a two-dimensional grid topology as shown in Figure 9 to quantify the advantages of transmit power control. We also model the impact of rate adapta￾tion. For our analysis, we assume that each AP sends traffic to a single client at a fixed distance (dclient) from the AP. In practice, if this transfer used TCP, we would expect a small amount of traffic from the client to AP due to the TCP acknowledgements. As the amount of uplink traffic is small, we only consider the downlink traffic to simplify our analysis. We also ignore many real-world effects such as multipath fading and chan￾nel capture. We do not use these simplifying assumptions in subsequent sections. In particular, we stress that our al￾gorithms are designed to operate in a symmetric fashion on both uplink and downlink traffic. We examine a range of transmit power levels and traffic loads. For each transmit power level and traffic load pair, we determine the minimum physical spacing required between APs (dmin) to support the specified load. To compute this, we first calculate the medium utilization required by each AP: utilizationAP = load/throughputmax. The maximum throughput is determined by first calculating path loss from the AP to the client (in dB) as: pathloss = 40+3.5∗10∗log(dclient); this is based on the pathloss model from [29] with constants that correspond to measurements collected in our local environment. Received signal strength can then be computed as RSS = txP ower−pathloss, and the signal-to-noise ratio is SNR = RSS − noiseF loor. We choose the noise floor to be -100 dBm, which is typical for our hardware. Using SNR and the data in Tables 5 and 6 (based on measurements presented in [9]) we then determine the maximum transmission rate that can be used for the AP-client link and the correspond￾ing maximum throughput for that rate. Rate (Mbps) Minimum SNR (dB) 1 3 2 4 5.5 8 11 12 Table 5: Minimum required SNR for Prism 2.5 Rate (Mbps) Throughput (Mbps) 1 0.85 2 1.7 5.5 3.5 11 4.9 Table 6: Maximum 802.11b throughput After we have computed the utilization for a single link, we determine the medium utilization at each AP by sum￾ming the utilization of all in-range APs. We determine that two APs are in range by computing the RSS between them using the same formula used above. We consider the candidate AP to be in range of the local AP if RSS > interferenceT hreshold. We set interferenceT hreshold to -100 dBm for our calculations. Figure 10 shows the results of our calculations for a client distance of 10 meters and loads ranging from 0.1 Mbps to 1.1 mbps. Other client distances and loss parameters would shift or scale the graph, but the trends would remain the same. The 2, 5.5, and 11 Mbps regions shown near the bottom of the chart specify the maximum transmission rate that can be used for each power level. Consider a specific point on this graph, such as the point at -15dBm power on the x-axis; using the 1.1 Mbps load line, this translates into a 20m AP distance on the y-axis. This implies that if you want to transmit at 1.1Mbps from each AP at -15dBm, the APs must be at least 20m apart in order to avoid overloading the wireless link. In addition, the solid-black line parallel to the x-axis indicates that each AP uses a transmission rate of 5.5Mbps to communicate with its client. For the simulations in the previous section we typically fixed the transmit power and then increased the stretch; this corresponds to picking a point on the x-axis and moving up vertically

throughput or fairness. An additional important consider ation is that in campus networks a user can obtain service from any of the APs in transmission range. Therefore, any design may need to carefully consider issues such as load- 85EE balancing of users across APs along with power control In chaotic networks, the infrastructure is controlled by multiple organizations, and, unfortunately, their priorities often conflict. For example, for a home network consisting of a single AP, the best strategy is to always transmit at maximum power, and there is no incentive to reduce power and, thus, interference. The results in the previous section show that such a "Max Power"strategy, when employed by multiple APs, will result in suboptimal network perfor- mance. This implies that while a single node can improve its Tx power(dBm) performance by increasing power, it can actually obtain bet- ter performance if it, and all of its neighbors, act socially and Figure 10: Minimum AP distance vs. Tx powe reduce their transmission power appropriately. This is anal (client= 10m gous to the tradeoffs between selfish and social congestion control in the Internet [10. While a node can improve per- formance by transmitting more quickly in the Internet, this the minimum distance between APs that can be support ga We draw a few key conclusions from Figure 10. Clear can result in congestion collapse and degraded performance for all. We believe that similar factors that drove the wide num supported density increases) dra- deployment of congestion control algorithms will drive the atically as the transmission power(in dBm) is decreased deployment of power control algorithms. We should note We also find that high aP density and higher loads require that an added side incentive for the deployment of auto- transmit power levels below 0 dBm. This is the lowest trans- matic power control is that it limits the propagation of an APs transmission which, in turn, limits the opportunity of mit power available from commercial hardware that we are malicious users eavesdropping on any transmission. aware of. Adding support for lower transmit power levels to wireless hardware would be a simple way of improving the Our work focuses on socially responsible power control al tensity of APs that can be supported. Secondly, the graph gorithms that would work well in chaotic environments. We an also be used to determine the upper bound on the power call such power control algorithms "socially responsible"to level that should be employed(x-axis) in order to achieve differentiate them from approaches that require global coor- dination across multiple access points(e. g for campus-wide a certain throughput, given a certain inter-AP distance(y- wireless networks). Our algorithms are targeted at individ- axis). Using a higher power level will typically not affect (i.e not decrease or increase) the performance for that node, but ual access points and clients, which behave in an altruistic will reduce performance for other, nearby nodes. This is the manner. agnostic to the actions of other aps and clients. Our algorithms could also work in campus scenarios. How- the next section. Finally we note that the highest densi- ever, we do not consider issues such a AP load-balancing ties require the use of very low transmission power, forcing which arise in such environments. We leave the extension of nodes to use a transmission rate under 11 Mbps. This sug our design to campus deployments for future work. gests that, when their traffic requirements are low, it may Note that while our algorithms are targeted at nodes be- advantageous if nodes voluntarily reduce not only their having in an altruistic manner, there are also practical con- transmission power but also their transmission rate since it siderations that make them more feasible than simply re- could increase the overall network capacity in very dense lying on the altruism of end users would. In particular networks, We will revisit this issue in Section 9 these algorithms are implemented not by end users, but by equipment vendors. From an equipment vendor's point-of view, reducing interference is beneficial. Moreover, regula- 6. DEPLOYMENT CHALLENGES tory mandates already limit transmit power, and could be Power control offers a simple but powerful technique for extended to require dynamic adjustment of transmit power reducing interference. The tradeoffs are obvious: reduc- in order to increase spatial reuse and potentially allow for ing the power on a channel can improve performance for higher transmit power limits which would clearly benefit ther channels by reducing interference, but it can reduce both end users and equipment vendors. Finally, as dis- he throughput of the channel by forcing the transmitter to cussed in Section 3.2, we find that new technology is quickly use a lower rate to deal with the reduced signal-to-noise ra adopted in chaotic networks, and that many users in chaotic tio. As a result, we must carefully consider the incentives dor implemented intelligent transmit power control could&. networks do not change factory default settings. Hence, ven that users may have for using such techniques. In practice, deployed relatively quickly and would be widely adopted the incentives for using power control are complex and we have to distinguish between the techniques that are applica- ble to campus deployments and chaotic wireless networks. In campus environments, there are a number of APs un 7. TRANSMISSION POWER AND der the control of a single organization. This organization RATE SELECTION in a position to do power control in each cell in a way that ow power adaptation affects both optimizes some global network metric, e. g. total network network-wide and individual user throughput, we ran exper-

1 10 100 1000 -20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 Tx power (dBm) minimum AP distance (meters) 0.1 0.3 0.5 0.7 0.9 1.1 Load Mbps 2 Mbps 11 Mbps 5.5 Mbps Figure 10: Minimum AP distance vs. Tx power (dclient = 10m) We draw a few key conclusions from Figure 10. Clearly the minimum distance between APs that can be supported decreases (i.e. maximum supported density increases) dra￾matically as the transmission power (in dBm) is decreased. We also find that high AP density and higher loads require transmit power levels below 0 dBm. This is the lowest trans￾mit power available from commercial hardware that we are aware of. Adding support for lower transmit power levels to wireless hardware would be a simple way of improving the density of APs that can be supported. Secondly, the graph can also be used to determine the upper bound on the power level that should be employed (x-axis) in order to achieve a certain throughput, given a certain inter-AP distance (y￾axis). Using a higher power level will typically not affect (i.e. not decrease or increase) the performance for that node, but will reduce performance for other, nearby nodes. This is the basis for one of the power control algorithms discussed in the next section. Finally we note that the highest densi￾ties require the use of very low transmission power, forcing nodes to use a transmission rate under 11 Mbps. This sug￾gests that, when their traffic requirements are low, it may be advantageous if nodes voluntarily reduce not only their transmission power but also their transmission rate since it could increase the overall network capacity in very dense networks. We will revisit this issue in Section 9. 6. DEPLOYMENT CHALLENGES Power control offers a simple but powerful technique for reducing interference. The tradeoffs are obvious: reduc￾ing the power on a channel can improve performance for other channels by reducing interference, but it can reduce the throughput of the channel by forcing the transmitter to use a lower rate to deal with the reduced signal-to-noise ra￾tio. As a result, we must carefully consider the incentives that users may have for using such techniques. In practice, the incentives for using power control are complex and we have to distinguish between the techniques that are applica￾ble to campus deployments and chaotic wireless networks. In campus environments, there are a number of APs un￾der the control of a single organization. This organization is in a position to do power control in each cell in a way that optimizes some global network metric, e.g. total network throughput or fairness. An additional important consider￾ation is that in campus networks a user can obtain service from any of the APs in transmission range. Therefore, any design may need to carefully consider issues such as load￾balancing of users across APs along with power control. In chaotic networks, the infrastructure is controlled by multiple organizations, and, unfortunately, their priorities often conflict. For example, for a home network consisting of a single AP, the best strategy is to always transmit at maximum power, and there is no incentive to reduce power and, thus, interference. The results in the previous section show that such a “Max Power” strategy, when employed by multiple APs, will result in suboptimal network perfor￾mance. This implies that while a single node can improve its performance by increasing power, it can actually obtain bet￾ter performance if it, and all of its neighbors, act socially and reduce their transmission power appropriately. This is anal￾ogous to the tradeoffs between selfish and social congestion control in the Internet [10]. While a node can improve per￾formance by transmitting more quickly in the Internet, this can result in congestion collapse and degraded performance for all. We believe that similar factors that drove the wide deployment of congestion control algorithms will drive the deployment of power control algorithms. We should note that an added side incentive for the deployment of auto￾matic power control is that it limits the propagation of an AP’s transmission which, in turn, limits the opportunity of malicious users eavesdropping on any transmission. Our work focuses on socially responsible power control al￾gorithms that would work well in chaotic environments. We call such power control algorithms “socially responsible” to differentiate them from approaches that require global coor￾dination across multiple access points (e.g., for campus-wide wireless networks). Our algorithms are targeted at individ￾ual access points and clients, which behave in an altruistic manner, agnostic to the actions of other APs and clients. Our algorithms could also work in campus scenarios. How￾ever, we do not consider issues such a AP load-balancing which arise in such environments. We leave the extension of our design to campus deployments for future work. Note that while our algorithms are targeted at nodes be￾having in an altruistic manner, there are also practical con￾siderations that make them more feasible than simply re￾lying on the altruism of end users would. In particular, these algorithms are implemented not by end users, but by equipment vendors. From an equipment vendor’s point-of￾view, reducing interference is beneficial. Moreover, regula￾tory mandates already limit transmit power, and could be extended to require dynamic adjustment of transmit power in order to increase spatial reuse and potentially allow for higher transmit power limits which would clearly benefit both end users and equipment vendors. Finally, as dis￾cussed in Section 3.2, we find that new technology is quickly adopted in chaotic networks, and that many users in chaotic networks do not change factory default settings. Hence, ven￾dor implemented intelligent transmit power control could be deployed relatively quickly and would be widely adopted. 7. TRANSMISSION POWER AND RATE SELECTION In order to characterize how power adaptation affects both network-wide and individual user throughput, we ran exper-