《计算机网络》课程教学资源（参考文献）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