A framework for Usage Modeling and Anomaly Detection in Large-Scale 802.11 Networks

A Framework for Usage Modeling and Anomaly Detection in Large-Scale 802.11 Networks Dossa Mohamed Massa Tese de Doutoramento Apresentada à Faculdade de Engenharia da Universidade do Porto em Telecommunications Engineering Supervisor: Prof. Ricardo Santos Morla (PhD) April 2015 ii Abstract Wireless 802.11 networks are a popular technology that offers inexpensive ubiquitous access to the Internet in campuses, enterprises, homes, coffee shops, airports, and other public places. Their wide-scale adoption has brought great convenience to many people, giving them anytime and anywhere access to the Internet. As a result people are becoming more and more dependent on these networks and are increasingly demanding reliability and high performance when connecting to the Internet through them. Due to the inherent problems of the wireless medium, these demands from the users pose significant challenges for network administrators. Learning how each part of the network behaves and how it is used is fundamental in addressing these challenges. As a network grows in scale and usage, these demands become an even greater challenge and it may not be feasible for administrators to use the same techniques that are used for small deployments. It is increasingly difficult for network administrators to maintain knowledge of infrastructure usage properties including usage patterns of individual access points (APs), users, and locations as well as their susceptibility to different problems as a deployment scales up. Network administrators require other complementary techniques for network management. In this thesis, we propose to use the analysis of collected 802.11 network usage data to aid performance and fault management of large-scale networks. Realistic knowledge of the usage patterns of 802.11 networks is critical for performance management, in a bid to make sure that resources are provisioned according to usage and that the network delivers the desired performance with respect to the expected usage. Learning from the collected 802.11 data is also crucial for fault management, as it may help network administrators to efficiently detect and fix different connectivity and performance problems facing the users of large-scale 802.11 networks. To simplify management of large-scale 802.11 networks, in this thesis we contribute with a framework for 1) usage modeling and 2) anomaly detection, both based on the analysis of collected 802.11 usage data. Most previous works on usage modeling focus on the user perspective of 802.11 including user mobility, registration, dwelling, and encounter patterns. In our framework we propose and evaluate a number of probabilistic models for automatic characterization of access point (AP) usage. We include time-dependent and timeindependent models of AP usage characterization, as well as models that consider AP week structure usage namely weekdays, weekends, and individual days of the week (Monday-Sunday). On the other hand, most previous works on anomaly detection uses enhanced devices (clients and APs), hardware sensors, sniffers, and controllers for detecting anomalies such as interference, overload, and halted or crashed APs. In our framework, we propose a methodology for detecting patterns of AP usage anomaly based on the iii analysis of the relationship between session endings at 802.11 AP. We identify a usage pattern named “abrupt ending” of 802.11 AP connections that happens when a large number of user sessions in the same access point (AP) end within a one second window. We propose an algorithm for automatic detection and characterization of different anomaly-related patterns associated to AP abrupt ending occurrences. We confirm the existence of significant statistical relationship between abrupt ending occurrences, anomaly-related patterns occurrences, and aggregate 802.11 network usage in terms of total number of sessions. We confirm the existence of abrupt endings in other 802.11 deployments. Our findings indicate abrupt endings are primarily the effect of interference across the 802.11 infrastructure and usage pattern behavior of the APs, but also misconfiguration and bugs on the 802.11 APs. Users and their respective device’s specifics play no significant role in abrupt ending manifestation. We finally provide an online implementation of the detection and characterization of abrupt endings and their respective anomaly-related patterns using the Esper complex event driven processing engine. “The more you know about your 802.11 network, the more you can do with it and the better you can make it” John Cox: Best practices for managing WLANs (2008) iv Resumo As redes sem fio 802.11 são uma tecnologia popular que oferece acesso ubíquo e barato à Internet no campus, na empresa, em casa, no café, no aeroporto, e noutros espaços públicos. A sua ampla adoção é conveniente para muitas pessoas, dando-lhes acesso à Internet em qualquer altura e em qualquer lugar. Como resultado desta adoção, as pessoas estão a tornar-se cada vez mais dependentes destas redes e exigem cada vez mais fiabilidade e alto desempenho quando se ligam à Internet através destas redes. Devido aos problemas inerentes do meio sem fios, estas exigências dos utilizadores colocam desafios significativos para os administradores destas redes. Aprender como cada parte da rede se comporta e como é utilizada é fundamental para endereçar estes desafios. À medida que a rede cresce em escala e utilização, estas exigências dos utilizadores tornam-se um ainda maior desafio e pode não ser viável os administradores utilizarem as mesmas técnicas que utilizam para pequenas redes. É cada vez mais difícil para os administradores de rede manterem conhecimento das propriedades da utilização da infraestrutura - incluindo padrões de utilização de pontos de acesso sem fio (APs) individuais, utilizadores, e localizações bem como a sua susceptibilidade a diferentes problemas à medida que a rede se torna maior. Os administradores de rede precisam de outras técnicas complementares para a gestão da rede. Nesta tese propomos utilizar a análise de dados de utilização recolhidos da rede 802.11 para ajudar à gestão de desempenho e falhas em redes de grande escala. O conhecimento realista dos padrões de utilização das redes 802.11 é crítico para a gestão de desempenho, de modo a garantir que os recursos são aprovisionados de acordo com a utilização e que a rede oferece a capacidade desejada para a utilização esperada. Aprender a partir dos dados recolhidos da rede 802.11 é também crucial para a gestão de falhas, já que pode ajudar os gestores de rede a detetar e resolver eficientemente problemas de conectividade e desempenho que afetam os utilizadores de redes 802.11 em grande escala. De modo a simplificar a gestão destas redes, nesta tese contribuímos com uma framework para 1) modelização da utilização e 2) detecção de anomalias, ambas baseadas na análise de dados de utilização recolhidos da rede 802.11. A maioria dos trabalhos anteriores em modelização da utilização dá ênfase à perspetiva do utilizador incluindo padrões de mobilidade, registo, estadia, e encontro. Na nossa framework propomos e avaliamos vários modelos probabilísticos para a caracterização automática da utilização de APs. Incluímos modelos dependentes e independentes do tempo, bem como modelos que consideram a estrutura semanal da utilização dos APs nomeadamente dias da semana, fins de semana, e dias individuais da semana (Segundafeira a Domingo). Por outro lado, a maioria dos trabalhos anteriores em detecção de anomalias utiliza dispositivos aumentados (clientes e APs), sensores em hardware, sniffers, e controladores para detetar anomalias como interferência, sobrecarga, e APs parados ou em falha. Na nossa framework propomos uma metodologia para detetar padrões de v anomalias de utilização de APs baseada na análise de relações entre término de sessões nos APs. Identificamos um padrão de utilização chamado “término abrupto” de ligações a APs 802.11 que ocorre quando um grande número de sessões de utilizador no mesmo AP terminam na mesma janela de um segundo. Propomos um algoritmo para a detecção e caracterização automática de vários padrões anómalos associados a ocorrências de términos abruptos. Confirmamos a existência de uma relação estatística significativa entre ocorrência de términos abruptos, ocorrência de padrões relacionados com anomalias, e utilização agregada da rede 802.11 em termos de número total de sessões. Confirmamos a existência de términos abruptos em outras redes 802.11. O que descobrimos indica que os términos abruptos são principalmente o efeito de interferência através da infraestrutura 802.11 e padrões de comportamento dos APs, mas também configurações erradas e bugs nos APs. Os utilizadores e as características dos seus dispositivos não tomam um papel significativo na manifestação de términos abruptos. Por fim providenciamos uma implementação online da detecção e caracterização de términos abruptos e dos seus respetivos padrões de anomalia utilizando o motor Esper de processamento de eventos complexos. vi Acknowledgements First and foremost, I would like to express my sincere gratitude to my academic advisor Prof. Ricardo Santos Morla, whom his constant support, stimulating discussions, valuable comments and insights provided me the perfect guidance that I needed through my Ph.D. journey. Ricardo’s comments and ideas always come at the appropriate moment and place with the right amount, keeping me busy and focused always. I am very glad that all our efforts were useful and valuable. A part of the effort has turned into completion of this thesis, and the rest prepared me well for my future careers. I would also like to thank my employer the Institute of Finance Management in Tanzania (IFM) and the Foundation for Science and Technology (FCT) in Portugal for their extended financial support throughout my Ph.D. studies. Certainly, without their support results of this work would not be the same. FCT support was received through grant number SFRH/BD/69824/2010. I am also thankful that in the context of FCT, particularly project SUM through PTDC/EIA/113999/2009, I received UMinho data set which I used for validation of my results in this thesis. Also, I am very grateful to INESC-TEC direction for allowing me to conduct my research in their highly reputable research laboratory (CTM). It's an incredibly positive working environment. In addition, I am very thankful to all my colleagues including those at IFM, in the MAP-tele program, and at INESC-TEC for their constant encouragement, support, and friendship. I am also very grateful to all my friends in Porto for the good moment we spent together. They really helped me in making this beautiful city a home away from home. Moreover, I would like to thank all members of my family, especially my parents Hajj Mohamed .K. Massa and the late Nibaro Athuman Liku, for being a source of joy in my life and for making me a person I am today both personally and professionally. Also, I am enormously grateful to all my seven brothers, two sisters, and all my in-laws for their endless love, encouragement, advice, and support. They always encouraged me through the rough times and advised me not to give up on this Ph.D. work. I am thankful for all their efforts and I feel very lucky to have them in my family. Last but not least, I would like to thank my wife Halima Sharifu. She has been very considerate and supportive throughout my Ph.D. process: always turning around the boring situations into laughter and depressing ones into consolations. I am specifically grateful for her encouragement to let me pursue what I dream of rather than what would have seemed convenient for us. I am also enormously grateful to our children Nibaro, Abdillah, and Abdulrahman. Nibaro came just to visit me here with my father and decided to stay until the end of my Ph.D. Little Abdillah was born at the last stage of my Ph.D. work, while a tiny Abdulrahman was born during thesis write-up phase. Indeed, they both brought much fun, happiness, and joy into our lives which are impossible to enumerate all here. vii Table of Contents Chapter 1: Introduction.............................................................................................................. 1 1.1 Management Challenges of Deployed 802.11 Networks ............................................ 1 1.2 Trace-Based Analysis for 802.11 Network Management ........................................... 2 1.3 Limitation of Current Analyses ................................................................................... 3 1.4 Framework for Usage Modeling and Anomaly Detection .......................................... 4 1.5 Contributions ............................................................................................................... 7 1.6 Thesis Structure ........................................................................................................... 8 Chapter 2: Overview of 802.11 Networks ................................................................................. 9 2.1 Network Architecture .................................................................................................. 9 2.2 Protocol Architecture ................................................................................................ 11 2.2.1 Data Link Layer .................................................................................................. 11 2.2.2 Physical Layer ..................................................................................................... 13 2.3 Challenges of Managing 802.11 Networks ............................................................... 14 2.4 Network Management ............................................................................................... 16 2.4.1 Network Management Architecture .................................................................... 16 2.4.2 Simple Network Management Protocol (SNMP) ................................................ 17 2.4.3 Functions of Network Management Systems ...................................................... 18 2.5 Trace-Based Analysis as a complement to Network Management ........................... 21 2.5.1 SNMP-based Network Management ................................................................... 21 2.5.2 Web-based Network Management ...................................................................... 21 2.5.3 Automated Network Management ...................................................................... 21 2.5.4 Trace-based Network Management ..................................................................... 21 2.6 The need for A Framework ....................................................................................... 23 Chapter 3: Related Work ......................................................................................................... 25 3.1 Introduction ............................................................................................................... 25 3.2 Usage Modeling ........................................................................................................ 26 3.2.1 General Statistics ................................................................................................. 26 3.2.2 Mobility Modeling .............................................................................................. 27 3.2.3 User Encounter Patterns ...................................................................................... 31 3.2.4 User Registration Patterns ................................................................................... 33 3.2.5 User Access Durations ........................................................................................ 34 viii 3.2.6 Traffic Characterization ...................................................................................... 35 3.2.7 Public 802.11 Infrastructure Usage ..................................................................... 36 3.3 Anomaly Detection ................................................................................................... 38 3.3.1 Overload Detection ............................................................................................. 38 3.3.2 AP Halt/Crash Detection ..................................................................................... 40 3.3.3 Interference Detection ......................................................................................... 41 3.3.4 Rogue AP Detection ............................................................................................ 42 3.3.5 Performance Anomaly Detection ........................................................................ 43 3.3.6 Network Management Tools ............................................................................... 46 3.4 Analysis ..................................................................................................................... 47 3.5 Conclusion................................................................................................................. 51 Chapter 4: Modeling 802.11 AP Usage .................................................................................... 52 4.1 Introduction ............................................................................................................... 52 4.2 Experimental Setup ................................................................................................... 53 4.2.1 Variables.............................................................................................................. 53 4.2.2 Data Set ............................................................................................................... 53 4.2.3 Figures of Merit ................................................................................................... 55 4.3 Statistical Generative Models of 802.11 AP usage ................................................... 56 4.3.1 Overview ............................................................................................................. 56 4.3.2 Exponential.......................................................................................................... 57 4.3.3 Discrete Mixture of Exponentials using K-Means .............................................. 57 4.3.4 Mixture of Exponentials with Gamma Scale ...................................................... 58 4.3.5 Above-Below AP Daily Event Count Average ................................................... 58 4.3.6 Binary Conditional Probability Models .............................................................. 60 4.3.7 Plugging-in Above-Below Average Models ....................................................... 60 4.3.8 ARIMA Model .................................................................................................... 61 4.4 Experimental Evaluation of 802.11AP Usage Models .............................................. 61 4.4.1 Exponential.......................................................................................................... 61 4.4.2 Discrete Mixture of Exponentials using K-Means .............................................. 61 4.4.3 Mixture of Exponentials with Gamma scale ....................................................... 62 4.4.4 Above-Below AP Daily Event Count Average ................................................... 62 4.4.5 Binary Conditional Probability Models .............................................................. 63 4.4.6 Plugging-in Above-Below Average Models ....................................................... 63 4.4.7 ARIMA Model .................................................................................................... 64 4.4.8 Cross-Validation .................................................................................................. 64 ix 4.5 Time-Dependent Models Considering Different Settings of Variables .................... 66 4.5.1 Overview ............................................................................................................. 66 4.5.2 Considering All-days AP Usage Samples ........................................................... 66 4.5.3 Considering Week Structure AP Usage Samples ................................................ 67 4.5.4 Comparing All-days Model Vs. Hybrid Model ................................................... 69 4.5.5 Comparing All-days Model Vs. Individual Days Model .................................... 69 4.5.6 Summary ............................................................................................................. 70 4.6 Performance Comparison of AP Usage Models based on Different Data Sets ......... 70 4.6.1 Overview ............................................................................................................. 70 4.6.2 Binary Conditional Probability Models .............................................................. 71 4.6.3 Plugging-in Above-Below Average Models ....................................................... 71 4.6.4 Summary ............................................................................................................. 71 4.7 Conclusions ............................................................................................................... 74 Chapter 5: Anomaly Detection of 802.11 AP Usage - Abrupt Ending of 802.11 AP Connections .............................................................................................................. 75 5.1 Introduction ............................................................................................................... 75 5.2 Abrupt Ending Characterization ................................................................................ 76 5.2.1 Definition ............................................................................................................ 76 5.2.2 Trace Data Characteristics................................................................................... 77 5.2.3 Threshold for Abrupt Ending of AP Connections ............................................... 77 5.2.4 Abrupt Ending Data Overview ............................................................................ 78 5.3 Possible Causes ......................................................................................................... 79 5.3.1 Abrupt Ending and User’s Devices ..................................................................... 79 5.3.2 Abrupt Ending and AP Models ........................................................................... 79 5.3.3 Abrupt Ending and User IDs ............................................................................... 80 5.3.4 Abrupt Ending and AP Locations ....................................................................... 81 5.3.5 Abrupt Ending and Usage ................................................................................... 81 5.4 Statistical Models of Abrupt Ending Occurrences .................................................... 82 5.4.1 Methodology ....................................................................................................... 82 5.4.2 Linear Regression Model .................................................................................... 83 5.4.3 Continuous probability Distributions Models ..................................................... 85 5.5 Conclusions ............................................................................................................... 89 Chapter 6: Detecting and Modeling Patterns of Abrupt Ending of 802.11 AP Connections .............................................................................................................. 90 6.1 Introduction ............................................................................................................... 90 6.2 Algorithm for Detection and Characterization of Anomaly-related Patterns ............ 91 2 affect multiple APs and locations at the same time in the infrastructure and can be difficult to detect given the scale of the network. Having a device walk/run near every AP for detection of problems in the network proves to be not only inconvenient but also expensive. To constantly ensure that users of the network have consistent access, that problems on the network can be quickly identified and resolved, and that the network provides desired capacity and reliably, 802.11 administrators require complementary approaches such as learning from the collected 802.11 network usage data. 1.2 Trace-Based Analysis for 802.11 Network Management Network management encompasses a wide range of activities as depicted by the ISO FCAPS model [15, 16], which defines five areas of network management functions: fault, configuration, accounting, performance, and security. Analysis of the collected network usage data can play a crucial role towards fulfilling some of the goals of these management functions, given the aforementioned complexities of large-scale 802.11 networks. The following discusses how this can be achieved in each of the five management areas. 1) Fault management: different abnormal network usage behaviors of APs, users, and locations can be detected by observing different indicators of abnormality in the data e.g. increased packet error rate or packet retransmissions rate. 2) Configuration management: problems related to device misconfigurations (APs or users) in any location of the network can be detected by observing appropriate patterns in the usage data e.g. authentication failure for legitimate users or frequently disconnected clients. 3) Accounting management: tracking network usage e.g. association durations and amount of bytes/packet sent and received of individual users, group of users, departments or units is possible irrespective of their locations. 4) Performance management: Over-utilized/under-utilized APs and locations in terms of usage in the infrastructure can be observed and together with their corresponding times of the day e.g., their aggregate association durations, number of sessions established, and traffic. 5) Security management: unauthorized access to a network as well as unauthorized access points attached to a network in any location of the network can be identified from the trace data, e.g. unknown/unregistered user and AP MAC addresses. While configuration, accounting, and security remain important functions of 802.11 network management; our emphasis in this thesis is on the application of trace-based analysis on performance and fault management of a large-scale network. Performance management is focused on ensuring that network performance is maintained at acceptable thresholds. To realize this goal effectively, appropriate plan and models for network usage need to be developed from trace analysis, so that resources in the network can be provisioned with proper balance to achieve the desired network performance, in relation to usage. The goal of fault management is to detect and correct faults that occur in the network. To detect and correct faults quickly and efficiently, appropriate indicators for network usage anomalies must be devised and monitored from the trace data, so that algorithms and models can be developed for identification of their true nature and for their proper characterization. Our approach of using collected 3 802.11 usage data analysis for performance and fault management aims to fulfill the aforementioned objectives in such a manner. In this way, administrator in charge of managing 802.11 networks can stay ahead of impending capacity and connectivity problems likely to occur in large-scale networks. 1.3 Limitation of Current Analyses The focus of early 802.11 trace-based works was to understand general characteristics of 802.11 network usage. Numerous basic statistics about 802.11 network usage were then presented: like the average number of users, average session’s duration, bytes sent and received, and protocols used [51 - 55]. Although these statistics helped to understand the underlying usage properties of 802.11 networks, there were no attempts to model this usage. The major focus of recent studies on 802.11 networks is on user mobility [56 - 80], user encounter patterns at APs [81 - 88], user registration patterns at APs [89 - 95], user dwelling time at APs [96 - 100], and traffic [101 - 109]. These works provide broad classification of users based on their degree of mobility, encounter patterns, arrival and departures patterns to APs, and traffic. However, their focus is more on the users’ perspective of network usage rather than the access point, e.g. mobility, association, and traffic models of individual users or group of users. In addition, it is not possible to derive synthetic samples from these models for using e.g. in a network simulator as most of the proposed models are not probabilistic in nature. On the other hand, most works for anomaly detection proposed in the literature aim to detect overload and flash crowd at an AP [117 - 128], failed and disconnected clients at AP [129 - 132], anomalous signal strength variations at AP and interference [136 - 147], and rogue AP [145 - 153]. However, in order to detect anomalies most of these works suggest the use of enhanced devices (clients and APs), sniffers, and third party hardware device such as controllers/sensors rather than looking at AP usage patterns. While detecting patterns of anomaly by looking at AP usage data can be simple and effective, deploying and maintaining these devices in 802.11 infrastructures is difficult and expensive. Along the same line of research there are other works that aim to detect hidden terminals, stations experiencing capture, anomalous traffic, and intrusions at AP [154 - 175]. However, the performance of each proposed 802.11 deployment scenarios in these frameworks is evaluated either based on a small scale network, on a testbed, or on simulations, thus hardly quantifying the underlying characteristics of a large-scale 802.11 deployment. There exist also several open source and commercial-based products that aid 802.11 network management tasks [176 - 179]. However, their main focus is to provide aggregate statistics and graphs of 802.11 network usage rather than detecting patterns of anomaly in AP usage and establishing their respective nature. Current approaches do not support automatic detection and characterization of anomaly-related patterns in the usage of APs namely AP interference, AP crash, AP overload, user intermittent connectivity and authentication failure patterns at AP which makes them not viable option for immediate adoption as network management tools. 4 1.4 Framework for Usage Modeling and Anomaly Detection Our focus in this thesis is on probabilistic models of AP usage and detecting patterns of anomaly in the usage of AP. The emphasis on AP usage and the use of probabilistic generative models is better suited to 1) performance management of largescale 802.11 infrastructures, e.g. models for capacity planning suitable for resource provisioning of large-scale 802.11 networks, and 2) network simulation tools for evaluating applications and protocols that may run in 802.11 infrastructures. The emphasis on detecting patterns of anomaly in the usage of AP and establishment of their respective nature is better suited to 3) fault management of large-scale 802.11 networks, as it may help network administrators to quickly and efficiently detect and fix problems linked to usage of the large-scale 802.11 networks. With the aforementioned 1-3 items in mind, in this thesis we propose a framework for realistic usage modeling and anomaly detection for large-scale 802.11 networks. The high level architecture of this framework is shown in figure 1. Figure 1. Proposed framework for usage modeling and anomaly detection Our proposed framework can be used in two network management functions as far as FCAPS is concerned, namely performance and fault management. Our proposed framework can be part of a proactive network management strategy for handling network capacity and reliability problems before they affect network and network services. For example, the performance management feature of our framework aims to provide network administrators with the ability to understand and to predict usage of APs in 802.11 infrastructures. Understanding AP usage can be helpful in resource allocations of a large-scale 802.11 network. Proper allocation of network resources may enable 802.11 networks to deliver performance according to the expected usage and traffic demand of 802.11 users, thereby resolving many of performance problems such as AP overload, degraded throughput, and delay. On the other hand, the fault 5 management feature of our framework aims to help 802.11 administrators in diagnosing and detecting patterns of anomaly associated to usage of APs in the infrastructure. In this way, appropriate remedial actions/decisions can be taken depending on the nature of anomaly diagnosed, as an attempt to offer and guarantee consistent connectivity to wireless users. Being able to properly plan for usage of APs and to quickly and efficiently detect patterns of anomaly in their usages, allows administrators to proactively manage 802.11 networks against performance and connectivity degradations. This is to emphasize the usefulness of our proposed framework to 802.11 administrators in aiding performance and fault management tasks. To develop our proposed framework, we use a data set collected from the underlying 802.11 environment, namely 802.11 session data collected centrally from the server running RADIUS (Remote Authentication Dial-In User Service) protocol [36]. This is a set of 802.11 traces from the Eduroam hotspot of the Faculty of Engineering of the University of Porto (FEUP). In our 802.11 network access points are configured to monitor associations of individual users in the network, and all association events are recorded in the server running RADIUS authentication protocol. In this way usage activity of individual access points and users extended over seconds, minutes, hours, days, weeks, months, and years is maintained. The collected RADIUS data can therefore be used for different purposes such as realistic 802.11 AP usage modeling and anomaly detection as proposed in this thesis. In our framework, we investigate different methods of automatic learning from the data and methods for parameter and threshold estimation from the data. We include into our framework: 1) models for characterizing AP usage, 2) methodologies and an algorithm for detecting patterns of anomaly in AP usage, as well as models for characterizing their occurrences in relation to 802.11 network usage - both based on the collected 802.11 AP session data. For usage modeling: we attempt to derive generative probabilistic models of AP usage based on daily keep-alive event counts. A keep-alive event is a message sent by a mobile client every 15 minutes for refreshing the client’s association with an AP. Due to their periodic nature, keep-alive statistics give us estimates of the time users stay associated with an AP during which they may generate traffic with different profiles. We decided to model keep-alive event counts given the evidence that user-AP association pattern and event counts are correlated with access duration and traffic at APs [104, 108, 113]. We therefore propose a number of generative statistical models for access point (AP) usage characterization based on daily counts of keep-alive event events and compare them using log-likelihood and Akaike Information Criterion (AIC) values figures of merit. These models include time-independent and time-dependent models for characterizing AP usage i.e., models that consider independency between consecutive usage samples of APs and those that consider dependency in time. The timeindependent models investigated are a simple exponential model, a discrete mixture of exponentials, a continuous Gamma mixture of exponentials, and an above-below model that allows thinking about the usage problem in binary terms (i.e. AP usage as either 6 high or low). The time-dependent models include a table conditional probability distribution model that uses binary variables for predicting the next value of an AP usage given its previous usage samples. We further consider week structure usage samples of AP and evaluate AP usage models: for weekdays, weekends, and individual days of the week (Monday through Sunday). We understand that for any modelingbased efforts to be effective, it is important to assess the performance of the proposed models. With this in mind, we provide cross-validation comparison results of all our models based on log-likelihood and AIC values on specific training and test data sets. For anomaly detection: we propose a methodology for detecting patterns of AP usage anomaly and their respective nature from the analysis of AP usage data. We focus on a usage pattern named “abrupt ending” of 802.11 AP connections. Abrupt ending of connections refers to a situation where an 802.11 AP drops all or a significant part of its users’ connections within a one second time window, as seen from RADIUS authentication logs [36]. During abrupt endings, mobile stations typically change association to other APs, and it can take few seconds, minutes, or even hours before an AP starts accepting new connections again. Each time a handoff happens, management frames are exchanged between the station and the target AP, thus keeping the medium busy and preventing other stations from accessing the wireless medium [119, 123, 155]. The need to associate and re-associate, especially during abrupt ending can have significant impact on the users-AP connectivity and traffic performance. Recognizing potential connectivity disturbance of wireless user connections upon encountering abrupt ending of 802.11 AP connections, in our framework we propose a method for detecting the abrupt ending of AP connections from collected 802.11 AP usage data. We also propose an algorithm for detecting and characterizing abrupt endings into several patterns of AP usage anomaly. We detect AP-related as well as user-related anomalous patterns. The detected AP-related patterns include: 1) interference across AP vicinity, i.e. when neighboring APs encounter abrupt endings in succession within one minute, 2) AP persistent interference, i.e. when a particular AP has encountered abrupt endings repeatedly in one day, 3) AP overload, i.e. when continued user sessions exist after an abrupt ending, meaning the abrupt ending occurred as a result of AP over-utilization by these users, 4) AP halt/crash, i.e. when no single user session/connection existed after abrupt ending during a specified time period, indicating an AP that is not running, and 5) AP interference, i.e. when abrupt ending does not belong to any of the aforementioned patterns. The detected user-related patterns are: 1) user authentication failure, i.e. inability of users to connect to an AP, which is observed when an abrupt ending resulted from a single user; and 2) user intermittent connectivity to AP, i.e. when frequently disconnected user sessions are observed at AP, particularly before and after abrupt ending. We also include in our framework statistical models for characterizing abrupt ending of AP connections occurrence and anomaly-related patterns occurrence in relation to aggregate 802.11 network usage, in terms of total number of sessions. These models include linear regression models and continuous probability models such as Exponential, Gamma, and Gaussian distributions. The proposed models can help 802.11 administrators to estimate 7 occurrences of abrupt endings and their resulting anomaly-related patterns in the usage of APs of these large-scale 802.11 infrastructures. 1.5 Contributions The scope of this thesis encompasses two major research thrusts: 1) proposing and evaluating models of 802.11 AP usage applicable to large-scale networks, and 2) investigating patterns of AP usage anomaly and techniques needed to detect and characterize them efficiently. Both 1) and 2) are based on the collected 802.11 AP usage data. The key contributions we make are:  A set of probabilistic models for access point (AP) usage characterization. These include time-independent and time-dependent models for automatic 802.11 AP usage characterizations.  Considering week structure usage samples of APs and proposing AP usage models for weekdays, weekends, and specific individual days (Monday through Sunday).  The identification of a new usage pattern named “abrupt ending” of 802.11 AP connections from the analysis of AP usage data. We propose an algorithm for the detection and characterization of different anomaly-related patterns associated to AP abrupt ending, and we also propose statistical models for characterizing their occurrences with respect to aggregate network usage.  The confirmation of the existence of significant statistical relationship between abrupt ending occurrences and aggregate 802.11 network usage, in terms of total number of sessions. We show this relationship is also significant for most anomaly-related patterns we investigate and can be modeled by linear regressions as well as exponential distributions.  The confirmation that abrupt endings and their respective underlying anomalyrelated patterns are the general phenomena among the 802.11 deployments we analyzed, and that they are the consequence of interference across the infrastructure, usage pattern behavior of APs, and bugs/misconfigurations of APs, while users and specifics of user devices plays no significant role in their manifestation.  An online implementation of the detection and characterization of abrupt endings and their associated anomaly-related patterns using the Esper complex event driven processing engine. These contributions can also be found in the following list of our publications:  Massa, D., & Morla, R. (2013). Modeling 802.11 AP Usage through Daily Keep-Alive Event Counts. Wireless networks, 19(5), 1005-1022, [47].  Massa, D., & Morla, R. (2010). Modeling 802.11 AP Usage through Daily Keep-Alive Event Counts. In 16th International Conference on Network-Based Information Systems (pp. 195-200). IEEE, [48]. 8  Massa, D., & Morla, R. (2013). Abrupt Ending of 802.11 AP Connections. In Computers and Communications (ISCC), Symposium on (pp. 000348-000353). IEEE, [49]. In addition, we have one more paper titled “Detecting and Modeling Patterns of 802.11 AP Abrupt Ending of Connections” submitted to a journal for possible publication at a time of this thesis submission. 1.6 Thesis Structure In chapter 2 we provide background materials on 802.11 networks. We explain their physical and protocol architectures, their inherent problems and challenges for network management. In chapter 3 we provide survey of the related work pertaining to the problem of usage modeling and anomaly detection in large-scale 802.11 networks. In chapter 4 we present our modeling work of 802.11 AP usage. We evaluate and compare different probabilistic models (time-dependent and time-independent) for characterizing AP usage based on AP daily keep-alive event counts. In chapter 5 we present the first part of our anomaly detection work. We identify a usage pattern named abrupt ending of AP connection from the analysis of 802.11 AP usage data, and we investigate their occurrences and propose models for their characterization. In chapter 6 we present an algorithm for characterizing abrupt endings as one of a set of different forms of anomaly-related patterns in the usage of 802.11 APs, and propose models for characterizing their occurrences with respect to aggregate network usage. We also include an online implementation of the detection and characterization of abrupt endings and their resulting anomaly-related patterns in this chapter. In chapter 7 we provide conclusions and suggest directions for future work. 9 Chapter 2 Overview of 802.11 Networks 2.1 Network Architecture A wireless 802.11 network (WLAN or Wi-Fi) is a type of computer network that is designed to offer location-independent network access among various computing devices by means of radio waves rather than a cable infrastructure [1]. In campuses 802.11 networks are typically deployed as the final link connecting the existing backbone wired network to a group of client stations, allowing these users to roam while accessing the full resources and services of the network across buildings or campus. The most obvious motivation and benefit behind these 802.11 deployments is increased nomad behavior. This means wireless 802.11 users are no longer tied to a location. A wireless user can move about freely with their devices from one place to another and access 802.11 networks without the restrictions of connecting to the network backbone. The other benefit includes cost-effective network setup, particularly for locations which are difficult to wire, e.g. older buildings and solid-wall structures. To offer 802.11 wireless services in these areas requires only installation of base stations and antennas, rather than running cables and patching in new Ethernet jacks, while adding users is just a matter of authorization. This can also translate to reduced cost of ownership, particularly in environments which are dynamic in nature that may perhaps require frequent modifications [1]. In 802.11 networks, each device with 802.11 capabilities (whether mobile, portable, or fixed), is referred to as a wireless station. In fact, these wireless stations are of two categories: access points and clients [1]. Wireless Access Points (APs) usually act as base stations to 802.11 networks. They connect wireless clients to the existing wired network and handle any communications between them. Wireless clients are mobile devices equipped with a wireless adapter. These devices include PCs, laptops, PDAs, tablets, and smart phones. Usually, the wireless adapter in the client device communicates with the access point using RF signals. When connection is established, wireless clients can have access to the network and network services just as if they are part of the wired network. When two or more stations are in communication range and happen to communicate to each other they form a Basic Service Set (BSS) [1]. The smallest possible BSS consists of two stations. A station in the same basic service area can communicate with other members of the BSS. A BSS that is not connected to a base station is called an Independent Basic Service Set (IBSS) or an Ad-Hoc network (figure 2(a)). In an ad-hoc network, stations communicate directly with each other in a peer to peer fashion. There is no base station and thus no device to coordinate 10 communications. This also implies stations in ad-hoc network cannot connect to any other basic service set. Ad-hoc networks usually involve a few number of stations set up for certain objectives and for a short duration such as in a disaster recovery [2]. When two or more BSS's are interconnected they form an infrastructure network [2]. Infrastructure network uses base stations for all communications, including communication between stations in the same BSS. For communication to be achieved, all stations are required to be within the communication range of the access point. Stations must first associate to the access point in order to use the infrastructure network. Two or more BSS's can be interconnected using a Distribution System (DS) [1, 2]. DS increases network coverage by linking access points to form an extended, larger network. This means each BSS becomes a component of an extended network, which makes seamless mobility between BSS's easier to achieve. Admission to the DS is via the use of access points, and also data moves between the BSS and the DS with the aid of these access points. (a) Ad-hoc mode (b) Infrastructure Mode Figure 2. Wireless 802.11 network architecture[1] Creating arbitrarily large and complex networks using BSS's and DS's leads to the next level of hierarchy called the Extended Service Set (ESS) (figure 2(b)). The interesting thing of the ESS is that the entire 802.11 network looks like an independent 11 basic service set to the Logical Link Control layer (LLC) [2]. This means irrespective of basic service area, stations within the ESS can communicate with each other even when moving between BSS′s. Distribution system supports the following mobility-related transitions. For example, No-transition: if a station is stationary or is moving only within its own BSS. BSS-transition: when a station moves between BSS's in the same ESS. ESS transition: when a station moves between BSS's belonging to different ESS's [3]. However, for a station to use 802.11 networks, it must first associate itself with the BSS infrastructure, typically via an access point. Association events are very dynamic in nature, because stations are always on the move, and are frequently turned on and off. A wireless station can only be associated with one AP at a time [3]. This allows DS to know the identity and the location of access point a station is associated with. In addition to association, there are two other association-related services supported by DS. When a station moves between BSSs it will switch access point. This service is termed as reassociation [3]. Reassociation is normally initiated by the station, in particular when signal strength indicates different association can be helpful. When reassociation is complete, the DS updates its location records to reflect station reachability via a new access point. Disassociation service is when the existing association between the mobile station and the AP is terminated. This can be triggered by either party. Once disassociation is complete, a disassociated station can no longer send or receive data. 2.2 Protocol Architecture 2.2.1 Data Link Layer IEEE 802.11 specifications focus on the two lowest layers of the OSI model, incorporating both physical and data link components. Each 802.11 network contains both a MAC and a Physical (PHY) component. The architecture allows multiple physical layers to be developed to support the 802.11 MAC. The MAC layer regulates how to access the medium and send data, while transmission and reception is dealt by the physical layer (PHY). The data link layer in these 802.11 networks comprises of two sub-layers: Logical Link Control (LLC) and Media Access Control (MAC). 802.11 networks make use of the same 802.2 LLC and 48-bit addressing similar to other 802 LANs, where MAC address is unique. This allows for simple bridging between 802.11 networks and existing IEEE backbone networks. The 802.11 MAC is designed to support multiple competing nodes to share the radio medium [4]. To control access to the transmission media and for collision detection, 802.3 Ethernet LANs employ Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol [4]. In this scheme, a station must first listen to the media before attempting to transmit, and once a collision is detected, a transmitting station stops its transmission of the frame, transmits a jam signal, and then waits for a random time interval before trying to resend the frame. To detect a collision, a station must have the 18 the same request-id, a zero-values error status in case if there is no error, and the same variable buildings. If an exception occurs in some variables, certain error status will be returned. For example, if it happens the agent does not implement a particular variable, the noSuchName error status is returned, tooBig when response is too large to send, badValue when an invalid values or syntax is specified, and readOnly when a manager write a read only variable [17]. Remote Network Monitoring (RMON): RMON uses a technique named remote management to obtain monitoring data [18]. Using this approach, a network monitor also known as a probe is used to collect data from the managed device. The probe can be stand-alone or embedded within the managed device. Rather than communicating directly to the device, management systems use SNMP to communicate with an RMON agent in the probe [18]. This makes it easier the sharing of information among multiple stations. In addition, if it happens that management application loses connection to the RMON agent data can be easily retrieved. Because the RMON agent has ability to collect data even though connection to the management system is absent. Usually a probe has considerable resources, hence can easily keep historical statistical information that could be played back afterwards by the network management station. 2.4.3 Functions of Network Management Systems The functions performed by a network management system can be categorized into the following five broad areas as far as FCAPS model is concerned. Fault Management: Its main goal is to detect, isolate, notify, and correct faults encountered in the network [19]. The ability to detect problems quickly and efficiently in any network is critical because faults in the network can result into serious network service degradation. As such, fault management is one of the most implemented among the ISO network management elements. Typically, fault detection is accomplished by listening to alarms generated in real-time or through analysis of error log files. This is possible because most monitored devices are configured to send a notification when they encounter a fault, usually via Simple Network Management Protocol (SNMP). Only after a fault has been identified and analyzed can remedial actions be taken by administrators. These may involve actions such as debugging, rebooting, or replacing failed devices e.g. APs, routers, servers, and switches. This type of fault management is referred to as passive; the fault management system only gets to know of a fault after it has received, for example, an SNMP alarm [20]. One significant drawback with this approach is that the devices need not only to be intelligent enough to send alarms, but they should be in the appropriate state too: some faults can be so severe (e.g. AP crash) rendering the device unable to issue alarm, thereby allowing faults to go undetected. On the other hand, active fault management involves sending periodic requests, e.g. Ping or Traceroute, SNMP polling to monitored devices in the network, specifically for checking their accessibility and status and the value of certain variables [20]. If no response is forthcoming or a fault is diagnosed, alarm is issued. The main limitations of this method are three: first, it wastes considerable amount of network bandwidth due to 19 the overhead involved in sending and receiving message in the network. Second, there is a chance of missing the actual thresholds, as every decision depends on the polling interval. Third, human administrators are still responsible for manually analyzing and interpreting the collected data to identify the causes of anomalies. Configuration Management: Its main goal is to monitor and manage network system configuration information, including versions of different hardware and software elements on the network [19]. This area is equally important, as many network issues result from changes in configuration files, installed modules, and change of hardware models and software versions. Configuration information is usually collected and kept in an inventory database, which makes traceability of network devices configuration information easier [21]. In this manner, the updated configuration information can be easily collected by using e.g. SNMP or scripting. In addition, configuration management is useful in making large change because manually updating individual devices is a tedious, time-consuming, and error-prone task. Using an automatic configuration management system one specific change/update can automatically be applied to all devices in the network. This not only saves time, but also ensures consistency of configuration information among different network devices, which may in turn reduce possibility of errors. Owing to the heterogeneous nature of network devices, it is very important to implement a common interface that provides support for configuring all devices in the networks. Accounting Management: Collects usage statistics for different users or departments so that bills can be generated and usage quotas can be enforced [19]. For non-billed networks ‘accounting’ is replaced by administration. In this respect, network administration aims to administer users of the network by granting passwords and network access permissions, also to administer the operations of equipment e.g. software backup and synchronization [22]. Typically, usage requirements for different organization differ significantly, which defeats the need of having a single accounting protocol. Nonetheless, one protocol commonly used for accounting is RADIUS protocol [35, 36]. RADIUS is an application layer client/server protocol that provides three main functions: 1) to provide authentication services for users and their devices so that they can access the network; 2) to grant authorization to authenticated users/devices to use the network and network services; and 3) to provide accounting for their usage of network and network services. For example, when a user is authenticated and connected, the Acct-Status-Type attribute will register this as “START” indicating that the request is the beginning of user service and when the user connection ends the AcctStatus-Type attribute will register this as “STOP”. The STOP records in the RADIUS server contains all the information in the start record plus additional usage information, such as access time, number of input and output bytes as well as number of input and output packets. For a usage-based accounting, this information can be useful for billing purposes and invoice generation [22]. The accounting data can be used to extract knowledge of overall network usage and for trend analysis. Trend analysis involves forecasting future usage, which is usually achieved through the use of statistical sampling techniques and models [22]. In fact, trending is equally important even for 20 billed networks, because prediction of future usage helps administrators to prepare network and network resources to cater for any anticipated usage. Performance Management: Ensures performance of the network and network services remains at acceptable thresholds [19]. Performance management may include activities such as monitoring, planning, and fine-tuning the network to fulfil performance requirements of the organization, specifically in terms of offered capacity, reliability, and latency [19]. Most performance problems in the network are related to capacity, for example the offered throughput of the network can be drastically lowered as a result of too many users sharing the same network element such as APs or network service such as streaming server. Performance information can be collected passively or actively through management systems that implement SNMP, and configured to alert network administrators when performance indicators move above or below given thresholds [15]. By collecting and analyzing performance data over time, knowledge of usage baselines and trends for different network elements and services can be established. This may allow network administrators to plan and perform network maintenance before a given capacity problem can cause network down time [23]. The major challenge of baselining and trending approaches is on dealing and processing huge amount of information such as the one generated by a large-scale network. Therefore, it is of utmost importance to define clearly the variables to monitor from the collected usage data and the threshold values that require action. Security Management: This network management function is responsible for protecting network and network resources against unauthorized access. It is also responsible for managing user rights and access privileges so that only legitimate users have access to appropriate network resources [19]. Specialized analysis tools are often used to identify assets and their respective threats, and also to rate overall network system vulnerabilities which in turn makes mitigation of any potential security problems easier [24]. Appropriate security measures need to be configured on the network and network resources in order to ensure that sensitive data cannot be accessed or changed e.g. via SNMP or rogue AP. Additionally, key management is also critical to the security of a network and network resources. Rules must be imposed regarding the use of passwords. In this respect, all passwords used must abide by the organization standards and guidelines such as minimum string length, and mixture of characters and numbers to make a guessing of password difficult. The starting point for any good security management implementation is on the organization security policies and procedures. These are out of scope of this thesis, and are not further addressed. 21 2.5 Trace-Based Analysis as a complement to Network Management 2.5.1 SNMP-based Network Management Many network management efforts make use of protocols such as the simple network management (SNMP) protocol and data models (e.g. management information base (MIB)) for automating the task of collecting information from network devices and for communicating back to network administrators [25][26][27]. With these approaches, network administrator manually analyzes and interprets the collected data before attempting to carry out any service update, configuration, or network upgrade. Network management following these approaches is highly influenced by the skills of the network administrator. 2.5.2 Web-based Network Management Web-based approaches and common object request broker architecture (CORBA) are among other network management efforts [28][29]. These approaches use web services as a management framework in simplifying network management operations e.g. configure device, turn it off and on, and collect alarms. The main limitation with these approaches is that, even a simple task such as introducing a new network variable or defining new MIB entry requires the overhead of taking the whole managed system down [30]. Again, the operation of the managed networks is constrained by the expertise of human network administrator. 2.5.3 Automated Network Management The increased complexity of managed network systems led to development of management tools that try to alleviate the task of network management from human network administrators. Examples of these approaches include mobile agents, active networks, and policy languages [31][32][33]. A major limitation of these automated management approaches is their reactive nature. In the sense that, all management decisions depend on the current system diagnosis, leaving no room for past observation or future prediction [34]. As such, these approaches are unable to adequately evolve and adapt with changing organization objectives and usage demands. 2.5.4 Trace-based Network Management Despite the network management approaches mentioned above, trace-based management approaches appear to provide a promising solution to most of the aforementioned problems. To achieve large-scale data collection, research community uses existing 802.11 infrastructures to obtain 802.11 traces. Typically, 802.11 access points (APs) and servers (e.g. RADIUS) in the 802.11 networks are configured to monitor the association and usage of individual 802.11 users. In this manner, relatively rich data set related to usage characteristics of APs and users that spans seconds, minutes, hours, days, months, and years can be maintained. In addition, the research community has been organizing traces over the years and several websites for archiving 22 the relevant traces have been maintained. Two prominent examples of such websites are [37] and [38]. These websites grant accessibility of 802.11 traces and other relevant resources to the research community. Example of research works that use these traces can be found in the following references: user mobility modeling [53, 55, 57, 60, 61, 65], user registration pattern [89, 91, 92, 93], access duration and traffic [96, 104, 105]. Trace-based Analysis and Network Usage: Systematic analysis of the collected 802.11 usage traces can help to understand deeply usage dynamics of different components within the managed network. This can be accomplished for example, by defining a set of models based on the collected underlying data that characterize the usage patterns of the access points, users of the network, applications running on top of the underlying infrastructure, locations of the environment encompassing the network, and the overall aggregate infrastructure usage properties. For example, in the previous research large-scale trace analysis has proven helpful to unearth hidden trends in 802.11 usage such as user mobility [56 - 80], access point popularity and their periodic usage patterns behavior [51 - 64], also preferences of applications by users and popularity of their devices [100 - 116]. Other interesting findings from trace analysis include: timevarying Poisson processes for modeling users’ arrival to APs [58, 63, 89, 90], powerlaw distributions for modeling distinct user groups with commonalities [82, 83], BiPareto distribution for modeling encounter events between individual nodes [81], and Weibull regression model for approximating the arrivals of traffic flows at individual APs [107]. Trace-based Analysis and Anomaly Detection: Systematic analysis of the collected 802.1 usage data can help to detect faults or anomalies in the components of the managed network. Example of useful findings in the literature related to detection of anomalies based on the analysis of 802.11 traces include: detection of repeated handoffs in client connections at the same AP during overload [117, 118, 119, 155], arrival of flash crowds at APs [123], detection of unusual events or happenings in physical space [39], and detection of other anomalous usage patterns such as short sessions [40]. In addition to detection of anomalies, statistical models for characterizing occurrences of different faults can be established. These models enable estimation of occurrences of faults at some stage during network operations (e.g. AP failure or AP overload, intermittent connections at AP etc.), allowing network administrators to take precautionary measures, especially in reducing the impact of the network anomalies or even preventing the anomaly from occurring at all. Trace-based Analysis in other Domains: Other possibilities exploited to collect usage traces include cellphone traces [41 - 43]. Though cellphones are perhaps the most popular wireless devices used, large-scale traces are difficult to obtain from the cellular phone operators owing to privacy concerns. There are also emerging efforts in collecting vehicle movement traces preferably through GPS positioning system, for example [44]. However, this effort requires active reporting from the monitored vehicles, hence does not scale well. A study of human physical mobility has relatively received greater attention in the literature. For example, authors in [45, 46] tried to 23 understand human global mobility patterns by examining human travel behavior through bags and money circulation properties. These efforts indicate importance of trace-based analysis for different empirical studies. Summary: Management techniques developed based on the collected usage traces are likely to be proactive rather than reactive, in the sense that management decisions can be made based on analysis of information related to present usage state of the network or managed components as well as based on the knowledge of the predicted future usage state of the network. For example, through our probabilistic models for AP usage (chapter 4), future usage pattern of the AP can be depicted based on either present day usage, or based on specific number of consecutive previous days or similar past days usage patterns behavior. In this manner, baselines for usage of APs on different days can be established which can later help to identify APs and locations surpassing planned capacity. In addition, models or algorithms developed based on the collected 802.11 usage data can be fine-tuned with little effort to suit different 802.11 environments. In this case, what one needs to do is just to change parameters of the models to include parameters of the new underlying 802.11 environment. As a side note, to generalize findings beyond a specific environment, it is important to consider analyzing multiple traces from different networks using the same exact method. 2.6 The need for A Framework It was argued in chapter 1 that, as usage and scale of 802.11 networks grows, so grow the challenges of managing these networks. One argument is that maintaining baseline knowledge of infrastructure usage properties, including usage patterns of individual APs, users, and locations, and their likelihood of encountering problems by administrators becomes increasingly difficult due to scale. On the other hand, due to the unreliable nature of the wireless medium, 802.11 users are likely to suffer performance and connectivity problems while using these 802.11 large-scale infrastructures, e.g. QoS degradation of their traffic, intermittent connectivity of their connections, and in some cases authentication failure. These problems can be caused by AP interference, AP overload, crashed AP, or weak RF signals due to RF holes/dead spots. To detect problems by 802.11 administrators physically visiting the place after receiving a phone call, e.g. from troubled 802.11 user, can be impractical due to size but also it is possible that when administrators arrive to the spot the problem may have disappeared only to reappear later on. To complement existing management techniques, in this thesis we propose a framework for usage modeling and anomaly for the large-scale 802.11 networks, based on the collected 802.11 usage data. Since there is no any known network management solution that allows network administrators to perform both performance and fault management using an easy access data set, our proposed framework use 802.11 AP session data collected centrally at RADIUS authentication server. This makes easier accessibility of user-AP association records for all APs on different parts of the largescale network. With this readily available data set, extensive analysis pertaining to the 24 underlying usage properties of 802.11 APs and their associated problems can be easily accomplished. In connection to this, our proposed framework is based on this collected 802.11 AP usage data and consists of two research thrusts, namely usage modeling and anomaly detection (see figure 1), which are captured by two network management functions: performance and fault management, respectively. Combining these two network management functions allows network managers that use our proposed framework to prevent problems in the usage of the large-scale 802.11 networks before they affect network and network service. For example, through the usage modeling feature, network administrators will be able to understand and predict usage in the infrastructure, thereby allocating network resources accordingly. In this manner, in addition to establishing usage baselines for APs, capacity problems of large-scale infrastructures can be prevented before affecting network services. For example, if there is knowledge that usage is going to exceed for some APs in a given day, administrator may decide to temporarily install additional APs in the vicinity of those APs so as to redistribute the load. On the other hand, the anomaly detection feature of our framework will help to deal with network connectivity issues. This will help in detecting connectivity problems quickly and efficiently, giving network administrators the opportunity to deploy counter active measures, for example to change the configuration parameters of APs, reboot, add, relocate APs, or remove problematic APs. And this could be done before users start calling to complain about their wireless network usage experience. To develop our framework, we started by looking at the extensive 802.11 data sets collected from our campus 802.11 network and identified the important characteristics of data that we intend to work upon. Details of these data sets are provided in the subsequent chapters of this thesis. Following these observations, we engage first into a modeling effort of AP usage in chapter 4, where we train and evaluate different timeindependent and time-dependent models for characterizing AP usage, based on AP keep-alive event counts. Then in chapter 5 we focus on anomaly detection of AP usage and we investigate a method for detecting abrupt ending of AP connections from massive collected 802.11 usage data. We propose statistical models for characterizing their occurrences with respect to aggregate 802.11 network usage. In chapter 6 we present an algorithm for characterizing different anomaly-related patterns of AP usage resulting from the occurrences of abrupt endings. Therefore, patterns such as AP interference, AP overload, AP crash, user authentication failure, and intermittent connectivity were detected, characterized, and modeled. Moreover, we map all the contributions of our work to network management FCAPS model, specifically performance and fault management, in order to support the importance and usefulness of the observations. 25 Chapter 3 Related Work 3.1 Introduction In this chapter we analyze existing works on 802.11 usage modeling and anomaly detection. This is because our framework proposed in this thesis includes these two features in aiding both performance and fault management of large-scale 802.11 networks. We begin with the analysis of the early trace-based research on 802.11 usage until recent works with an emphasis on APs, users, and traffic modeling. We analyze works conducted on the traces of university campuses, corporate organizations, and public 802.11 infrastructures. In addition to early works about general statistics subsection 3.2.1, we present analysis of the recent works related to user mobility modeling at AP in subsection 3.2.2, user encounters patterns in subsection 3.2.3, user registration patterns in subsection 3.2.4, user access durations in subsection 3.2.5, and traffic characterization in subsection 3.2.6. From AP perspective, all the above mentioned items constitute to the aggregate usage of the 802.11 AP. When considering the problem of modeling 802.11 AP usage to aid performance management of a largescale 802.11 network, it is increasingly important to analyze all aspects of user activities that may amount to overall usage at the 802.11 AP. We also include the analysis of public 802.11 infrastructure usage in subsection 3.2.7. Moreover, for anomaly detection in 802.11 networks, we analyze relevant existing works not just limited to the collected 802.11 usage data, but simulations and testbed works are also included. This is due to rarity of works in the literature that tried to detect anomalies from the collected 802.11 usage data. The main emphasis is placed on the detection of connectivity anomalies in the usage of 802.11 access points. We focus on the features and techniques used for the detection of AP overload in subsection 3.3.1, AP halt/crash in subsection 3.3.2, AP interference in subsection 3.3.3, rogue AP in subsection 3.3.4, and other performance anomaly of 802.11 networks such as capture effect, repeated handoffs, and MAC misbehavior in subsection 3.3.5. The first three items mentioned above are in particular related to our anomaly detection work of chapter 5 and 6. Also, in addition to connectivity problems caused by rogue AP and various performance anomalies of 802.11 networks, these three anomalies (AP overload, AP halt/crash, and AP interference) are responsible for majority of connectivity problems in these large-scale 802.11 infrastructures. We will review these works in this chapter. 26 3.2 Usage Modeling 3.2.1 General Statistics In the initial stage of 802.11 trace-based works, most researchers focused on understanding how wireless users generally use the deployed 802.11 infrastructures. In many of these works, basic statistics about user behavior and network performance were collected and analyzed. For example, Tang and Baker [51] collected a twelve-week 802.11 trace from a university campus, aiming to characterize global properties of 802.11 infrastructure usage in the academic environment. In their analysis, they observe most users in campus are stationary and utilize the network only for web-surfing, session-oriented, and chat-oriented activities. Additionally, they find that the peak throughput is usually caused by a single application (HTTP) and that in overall incoming traffic dominates outgoing traffic. Later, Tang and Baker [52] analyzed network traces of a metropolitan-area wireless network, aiming to understand user behavior in a typical daily life situation. In their analysis, they find the network was used mostly during the day and evening hours, and on average users associate with few APs which are in close proximity geographically. Along the same direction of research, authors in [53] tried to characterize user behavior and network performance from a three day conference network trace. In their analysis, they observe that users are evenly distributed across all APs. In addition, load distribution between APs is highly uneven and web traffic is responsible for 46% of the total bandwidth among all application traffic mix. In [54], authors extended the work of Tang and Baker [51], by considering larger traces covering almost all buildings on a campus, including residential buildings in analyzing user behavior and network traffic. They find that residential traffic is the most dominant one among all other traffic, and web protocols account for (53%) of the total traffic volume. In [55] authors analyzed over seventeen weeks of trace data from a mature 802.11 network that includes about 550 access points and 7000 users. They compared the findings from this trace to the trace collected two years ago after the initial deployment of their WLAN [54]. In their analysis, they observe substantial change in applications used in 802.11 infrastructure including significant increases in peer-to-peer, streaming multimedia, and voice over IP (VoIP) traffic, with on-campus traffic exceeding off-campus traffic. This is contrary to the initial stage where web and off-campus traffics were dominant components. Although the analyses presented by these works help to gain general understanding of user behaviors and network performance, most of these works do not try to model 802.11 usage. To improve upon this shortcoming, most recent 802.11 trace-based works attempted to focus on modeling user behaviors; one particular important aspect is the mobility of 802.11 users. 27 3.2.2 Mobility Modeling User Mobility: There are numerous efforts in the literature that tried to exploit the ubiquity provided by 802.11 networks to understand and model mobility of users among available access points (APs), buildings, and across the whole 802.11 infrastructure. For example, authors in [56] modeled user mobility based on how frequently users visit various APs together with their duration of stay in those APs. They find that users spend a large fraction of their time at a single home AP, whereas the probability distributions of their movement and stay time follow power laws. Authors in [57] considered the number of unique users associated to APs during each hour, aiming to classify user mobility patterns on hourly basis. The analysis of a one-year 802.11 trace indicates both user mobility and AP popularity depend on the academic calendar and their periodic behavior depends on the proximity to other APs. Authors in [58] modeled influx and outflux of user movement at AP from a two-month period Dartmouth traces. By counting the hourly number of users at each AP and through the use of Discrete Fourier Transform (DFT), they observe repeated temporal pattern every 24 hours at each AP, by considering the number of associations of the same hour in different days they then aggregate multiple days’ association vectors to form a single 24-elemet vector for each AP and cluster APs based on their peak hour of visits. They find that average users’ arrival rate and the distribution of the daily arrivals for each cluster follow nonhomogeneous Poisson processes. Authors in [59] studied individuality of users’ mobility patterns from eight months Dartmouth traces. Without using geographical information, they proposed a mobility clustering aware algorithm based on graph theory, which uses the number of roaming events between APs as a metric for estimating proximity between APs. Using their algorithm, they were able to depict individuals’ mobility as well as to categorize the resulting clusters into places with social meaning and paths. Focusing on mobility patterns of hand-held devices rather than laptops, authors in [60] studied a method of estimating the user’s physical location from 802.11 traces and of mapping the coordinates of the campus and GPS data for each AP. By observing association events of mobile devices such VoIP devices and PDA on each workday, they find that pause time and speed distributions each follow a log-normal distribution, and the direction of movements follow the direction of popular roads and walkways on the campus. Along the same direction, authors in [61] analyzed the mobility patterns of PDA users in a campus WLAN based on their proximity when they are within communication range of each other. Authors observe their proposed evolutionary topology model results in a completely connected graph only when users’ moves within the indoor locations of campus, and once these users moves throughout (outdoor) campus they create numerous islands of disconnected graphs, which can be captured by their other proposed campus waypoint model. Other interesting research on user mobility include [62], where authors analyzed 802.11 traces collected from three university campus WLANs, aiming to compare user association behavior to access points in these environments. By looking at user association patterns within each AP and between APs, particularly at the repetitive 34 distribution fitted the behavior in the building with classrooms. In [95], the same authors examined usage pattern of the library in the main campus of the Technical University of Catalonia (UPC). They find existence of daily and weekly repetitive patterns in WLAN usage, half of the population accesses the WLAN once during each month, and many users associate to only one of the twelve possible access points, indicating many users are static. The behavior on Fridays and the weekends were different than that of the first four days of the week and the proximity of final exams resulted in slight increases in the average amount of active devices registered to available APs. These works analyzed total user associations only from a specific set of APs and buildings such as library. Therefore, little is known about applicability of these models to all APs, buildings, and locations within large-scale 802.11 networks. Furthermore, there is no consideration of Ping-Pong sessions in the construction of these models. In addition to user registration patterns at APs, there are also several attempts in the literature that aim to characterize user access durations at APs. These works are discussed in the following subsection. 3.2.5 User Access Durations Characterization of user access durations has been researched extensively in the studies about 802.11 network usage. The focus of most previous works in this area is to understand time users normally stay associated to APs. For example, authors in [96] analyzed duration spent at each AP by considering continuous user session to AP without any disconnection (i.e. without re-association between consecutive associations). Their analysis show that, mobility and building type affect the session and visit durations at APs, also they observe as the mobility increases the visit duration tends to decrease stochastically, while opposite happens for session duration; hence proposed a family of Bi-Pareto distributions to model the associations and session duration at APs. Authors in [97] characterized usage of the campus network in terms of overall infrastructure usage, user mobility, sessions, and access durations. They observe the number of APs visited per user is influenced by geographic proximity of the locations, and in overall, the number of sessions per user followed a Logarithmic distribution while durations for stationary session followed a two-parameter Weibull distribution and mobile session durations followed an Inverse Gaussian distribution. Authors in [98] developed a wireless user model from analysis of five different traces. They define several users’ states (i.e. active, idle, sleeping, and gone) and state transitions, and propose to employ a hidden Markov model to these state transition matrices. They find that the user models are similar across all five traces even though the traces were collected at different venues (library, coffee shops, and conference) and residing time to APs followed a generalized Pareto distribution. In the same direction of research, there exist several works that try to understand user access time from simulation and testbed experiments. For example, authors in [99] studied the impact of mobility models on cell residence time for WLAN. They simulate different scenarios of AP density and observe that the average cell residence time 35 decrease when a memoryless movement pattern is followed (e.g. Random Waypoint) and increase when smoother movement patterns are followed (e.g. Gauss-Markov); they further indicate the cell (AP) residence time can be better characterized by lognormal distributions. Author in [100] designed and implemented a general framework for behavior-aware dwell prediction with and without the aid of client sensor data. In their testbed experiment, mobile devices (smartphones) are programmed to periodically report their sensor readings to the AP (e.g. accelerometer and compass), a support vector machine (SVM) classifier accepts the readings and combine with measurement features from WiFi RSS, and therefore, based on training data from past data a classifier predicts users likely dwell time. Most of these models consider aggregate association duration at AP regardless of the type of connections. Hence the accuracy of the resulting models can be highly influenced by the Ping-Pong connections at AP. In addition to user access duration at AP, there several works in the literature that attempted to characterize and model traffic. We review these works in the next subsection. 3.2.6 Traffic Characterization Focusing on the infrastructure usage and network performance rather than user behavior, there exist a number of studies aiming at characterizing traffic of access points and aggregate traffic load of 802.11 infrastructure networks. For example, authors in [101] proposed a time-series forecasting method for characterizing traffic of APs. Using their proposed methodology, they observe the aggregate hourly traffic for all APs in the infrastructure exhibits diurnal and weekly periodicities, while similar trend is observed in the hourly traffic for several APs. Authors in [102] provided Singular Spectrum Analysis of the structure of traffic load measured in a large-scale campus-wide WLAN. Using their approach, they observe the time-series of traffic load at a given AP has a small intrinsic dimension, which can be modeled using a small number of leading principal components, while the residual components can be exploited to capture irregular variations (i.e. a stochastic noise). Authors in [103] proposed a traffic prediction mechanism using the Recursive Least Squares algorithm. Using their proposed method, they were able to predict future traffic load at APs in the time scale of few minutes, although prediction accuracy was constrained by the amount of history size used in the training process. Other interesting works include [104], where authors performed a system-wide characterization of the workload of wireless access points (APs) in a campus 802.11 infrastructure. They compared two different campus networks using similar analysis methods and find log normality is prevalent in the aggregate traffic load of APs in both campuses. Moreover, they observe a correlation between the number of associations and traffic load at APs. Authors in [105] presented a session-level and follow-level modeling of traffic in a campus 802.11 network. They modeled the session arrival process at AP as a time-varying Poisson process. They observe the arrival of a user session at AP triggers the arrival of a group of flows that form a cluster process, which can be described by a cluster Poison process. Also, they observe session arrival times at 36 APs are uncorrelated and exponentially distributed with a mean equal to unity; while the Bi-Pareto distribution yielded the best fit for the number of flows per session, a lognormal model provided the best fit for flow inter-arrivals within sessions. Authors in [106] modeled traffic workload in terms of wireless sessions and network flows, using buildings as basic entities for traffic demand. They find that traffic and roaming patterns varies across various times (hour, day, week) and spatially correlated in terms of building and building-type. Moreover, sessions for the traffic non-stationarity in time followed a time-varying Poisson process, and also, the in-session number of flows and the flow sizes can be well approximated by the Bi-Pareto distribution; whereas the Lognormal distribution was the best fit for in-session flow inter-arrivals out of a set of common distributions including Weibull, Gamma, and Pareto. In [107], authors characterized static and roaming traffic flows at APs from collected 802.11 usage data. They look at TCP flows at each AP and observed their inter-arrival time and duration, and find that Weibull regression model is able to accurately approximate the arrivals of flows at individual APs; on the other hand, both roaming flows with less than five handoffs and the number of handoffs followed Geometric distribution. Along the same direction of research, authors in [108] analyzed traffic characteristics of a high-speed wireless Internet access sessions. By observing session lengths and traffic volumes, they find that the longer the session the higher the upand downloaded traffic volumes, the downloaded traffic tend to increase with the increase in uploaded traffic, and in overall, these underlying relationships can be captured quantitatively by the trends determined by the power-law and linear regression. Authors in [109] assessed several network usage metrics related to AP utilization including traffic load. They observe the residential and academic sectors are responsible for most of inbound and outbound traffic load, with nearly 80% of the total. Also, sessions of long duration depends on the AP location (e.g. home or research center), and sessions of short duration occurs mostly when many users are associated to APs. Similar to the models for association durations and registration patterns at AP in the previous subsections, these proposed traffic models can be influenced by the traffic resulting from the Ping-Pong connections. Since, most of these models consider total traffic generated at AP throughout users-AP association regardless of the type of connections. 3.2.7 Public 802.11 Infrastructure Usage There exist various efforts in the literature where researchers attempted to analyze usage patterns of the publicly deployed 802.11 infrastructure. Their main goal in these works is to highlight global properties of the infrastructure usage, similar to those explained throughout subsection 3.2.1 to 3.2.6. For example, authors in [110, 111] studied the usage of the Google WiFi network deployed in Mountain View California based on client device type i.e. traditional laptop users, fixed-location access devices, and PDA-like smartphone device. They analyzed usage activities in terms of traffic demands, and mobility of only active clients, as they roam through the city (in their settings client is considered to be active if it sends at least one packet per second during 37 a 15-minute reporting interval, hence trace records have a granularity of 15 minutes). Results shows Google WiFi network has a substantial daily user population, with weekend usage lower than weekdays use; 35% of all devices associate with only one AP, whereas smartphones frequently associate with a large number of APs, and the traffic varies substantially among the different populations with the predominance of HTTP, peer-to-peer, and other TCP traffic. In another effort, authors in [112] examined five weeks traces from the Verizon Wi-Fi Hotspot in Manhattan. In their analysis, they find most clients used the network infrequently and visited few APs, and usage of the network display a strong diurnal usage pattern with weekly trend. The hotspot APs were not that busy even during peak usage periods, and on average the aggregate usage is higher on week-days than on weekends. Authors in [113] examined a 5 month long traces collected by a wireless network service provider operating hotspots in restaurants, serviced apartments, hotels, and airports all over Australia. They analyzed number of sessions established, session durations, and traffic for different user accounts on hourly, daily, and weekly basis. They observe highest user activity during the night with busy hours occurring between 8 p.m. and midnight, whereas the daily activity is roughly uniform for all days of the week. The average session length is about an hour and most of the timed out sessions were idle when implicitly disconnected, on the other hand, the average hourly traffic is high, particularly when most sessions are active, while daily traffic is asymmetric with outbound traffic less than inbound traffic. In the same line of research, authors in [114] presented a quantitative analysis of the usage of a large public wireless local area network that provide both indoor coverage at a university campus and selected public city premises, as well as outdoor coverage in a city center of Oulu in Finland. They find that university usage is more on office hours and weekdays, while the city usage is higher during the evening hours and weekends; additionally, city usage is higher than university usage in terms of the aggregate traffic volume. Analysis of user mobility indicated users are not very mobile, as less than 10% of the sessions involved spatial movement of at least 50 meters, while 60% of the stations using the network appear to have a home location (access point), where they spent about 80% of their total time. In a slightly different attempt, authors in [115] presented results of Internet traffic measurements of a commercial broadband wireless access network for home users. Analysis of data collected from 250 households reveal that P2P file sharing traffic is used almost all day long, whereas the amount of web and streaming traffic increases in the evening hours with a peak at 19:00 o’clock. A further analysis of the P2P traffic shows that BitTorrent is about 56% and eDonkey is about 41 %; furthermore streaming traffic consumed about 22% of the total traffic besides web and P2P. In [116], authors highlighted the challenges of establishing a global hotspot infrastructure both technical and deployment-related challenges. This is in order to define a viable hotspot business model that would be able to cater and provide added value for all its stakeholders: the end user, the network service provider, and the building and premise owners. They proposed several issues that need to be considered for it to be a reality, for instance issues related to authentication, security, coverage, management, location services, billing, and interoperability. 38 The usage characterizations of the above mentioned public 802.11 networks produced almost similar results. On average aggregate usage of the network displayed diurnal usage pattern with weekly trend, and higher network usage was noted on weekends than on week-days, which is contrary to a campus setting [56 - 64]. Most users have a home location (AP) with some visited few APs, and traffic is dominated mostly by HTTP and peer-to-peer applications. However, for most of these works the focus is on providing statistics about infrastructure usage, and mobility models of individual and group of users rather than probabilistic models for overall access point usage characterization e.g. probabilistic models for predicting future usage of an AP based on the current and previous usage patterns of the AP. 3.3 Anomaly Detection 3.3.1 Overload Detection The IEEE 802.11 MAC protocol originally was designed to offer asynchronous best-effort service to stations within 802.11 network systems. In the sense that each station associated to 802.11 AP is granted the same transmission opportunities similar to other stations in the long term. This means if the number of associated stations to an AP increases the throughput per station is likely to decrease drastically. Increase in the number of associated stations to an AP can results into queues buildup in both the stations and the access point, leading to loss of frames, which could be detrimental to the overall 802.11 performance. In connection to this, there exist various efforts in the literature that tried to investigate the underlying properties of overloaded 802.11 networks from collected 802.11 usage data. For example, authors in [117, 118] analyzed variations in the linklayer properties during network overload period. In [117], authors observe that the overloaded wireless network is characterized by extensive medium occupancy, high traffic, frequent bit errors, numerous retransmissions, and significant data rate variations. In [118], authors find that the use of RTS/CTS denies nodes from gaining fair access to a heavily congested channel, and the use of rate adaptation in response to network congestion generated a lot of handoffs which impact negatively 802.11 performances. Authors in [119] shows that, under overload conditions stations only maintain a short association period with an AP, and repeated association and reassociation attempts due to lost connections are common phenomena even in the absence of mobility. Their analysis of handoffs shows that stations’ throughput suffers drastically following each handoff, leading to suboptimal network performance. In [120], authors find that the increase in packet losses necessitate stations to initiate a handoff in search of a better AP in their vicinity, and the use of channel busy time allows in differentiating packet losses due to overload and those due to poor link quality. These works do not propose any mechanism or method for overload detection or prevention. They only analyzed a section of 802.11 network usage data where the highest number of users was observed in the 802.11 APs, and ignored the fact it is also possible for some few users to also cause AP overload. 39 To minimize user connectivity disruptions (repeated handoffs, bit errors, retransmission) during overload situations and for proper balance of network usage, several techniques have been proposed in the literature. For example, authors in [121, 122] presented a distributed admission control that limits the possibility of AP overload due to a high arrival rate of network flows. In their admission systems, each station perform a short probe that estimates MAC service time, the offered load, and transmission rates in an AP to determine if AP has enough capacity for a new connection. Thus, the flow is admitted only if the estimate is below a predefined threshold, otherwise the proposed admission controls block stations from initiating new sessions. In [123], authors proposed a queue-based user association management system to mitigate the impact posed by arrival of flash crowds and presence of high concentrations of users in 802.11 networks. Their propose system maintains a queue of users that request network access, and grants 802.11 network accesses only to a limited number of users at a time. One limitation of these schemes is that they require modification at APs (e.g. scheduling and bandwidth partitioning mechanisms) which cannot be easily adopted in large-scale 802.11 networks. Along the same direction of research, authors in [124] proposed a load-balancing scheme in which agents’ runs on each access point and periodically exchange load information (AP throughput) to determine whether AP is overloaded, balanced, or under-loaded. In their approach, access points which are overloaded forces handoff, and only lightly loaded access points must accept roaming stations. In [125], authors proposed a dense access points deployment architecture (DenseAP), where a central controller collects throughput information from all APs before deciding which AP should each client associate with. In addition, the central controller also decides on the assignment of channels to APs and also performs periodic load balancing to reallocate clients from APs with significant load to nearby APs with light loads. Authors in [126] proposed a system for automatic access point discovery and selection called Virgil. In their system station first scans all available APs in a given location and quickly associates to each AP, and runs a series of tests to estimate the quality in terms of throughput and delay of each AP’s connection to the Internet before choosing best AP to associate with. However, these proposed schemes improve aggregate throughput, fairness, and delay at 802.11 AP, but they require certain support and cooperation between clients’ and access points which cannot be easily applied in large-scale 802.11 networks, given the higher number of users, access points, and network locations. Furthermore, the focus in most of these works is in controlling the number of newly arrived users that requires admission to 802.11 AP, and gives less importance to the detection of AP overload situations resulting from users who are already associated to the 802.11 AP. In a slight different effort, authors in [127] presented a load balancing technique similar to cell breathing in cellular networks that controls AP’s coverage range (cell size), by dynamically changing the transmission power of the beaconing messages of AP. They develop numerous polynomial time algorithms to help find the optimal beacon power settings that could minimize the load of the most congested AP, in terms of number of users and traffic demands. In [128], authors modelled access point 40 selection as a game and assess the impact of user dynamics on arrival/departure patterns system behavior. They find that their proposed access point selection algorithm bring the game to a Nash equilibrium in a matter of single iteration, as each user makes a single selfish AP selection based on the current state of the system. One limitation of these proposed schemes is that users are likely to be shifted between APs frequently, owing to the time varying nature of the wireless medium and bursty nature of wireless users’ traffic. These two inherent wireless properties are likely to influence changes in traffic load and delay in the AP at any moment in time, and as a consequence of that users will be shifted to other APs each time any of these happens. 3.3.2 AP Halt/Crash Detection Due to time varying nature of the wireless medium and usage pattern behavior of a large-scale 802.11 infrastructure, it is possible one or more access points at any given moment in time to face problems and stop running (i.e. halt or crash). As a consequence of AP halt/crash, clients’ connections and throughput will be severely impaired, leading to significant amount of intermittent sessions as user clients will keep probing and searching for good connections in their vicinity, repeatedly. This can cause wireless medium to be busy, due to extensive medium occupancy by management frames, and therefore preventing other stations from accessing the medium. To detect such failed AP by probing the wireless interface of all APs in the infrastructure proves to be a laborintensive and inefficient task. The ability to automatic detect AP halt/crash is valuable for effective management of large-scale 802.11 infrastructures. In connection to this, there exist few efforts that tried to detect halted/crashed AP from 802.11 measurement data. For example, authors in [129] proposed an algorithm that exploits device mobility to detect presence of faulty APs in an 802.11 network. The main assumption in their algorithm is that the longer the time an AP does not register events, the greater the probability that particular AP is faulty (i.e. halted/crashed). In our work we consider the absence of registered events in a specified time after AP abrupt ending of connections and not just after last registered association event at an AP. In [130], authors proposed architecture to improve fault tolerance during access point failures, where centralized management system (MS) collects measurement from all APs on a timely basis. In their approach whenever a miss reading (RSSI) measurement from AP is detected, a centralized Management Station (MS) polls that AP to confirm such AP failure, and remotely sets the new configuration in other working APs. While this proposed scheme is able to detect out of service AP (i.e. AP which is not responding to status probes because of the problem in the wired link), but it fails to detect AP that broadcast wireless beacons and yet cannot allow devices to associate. Authors in [131] proposed and evaluated a technique called Client Conduit, which enables bootstrapping and fault diagnosis of disconnected clients around APs. Their solution focuses primarily on the use of controller with assistance of a diagnosis server to detect and self-diagnose disconnected clients around halted or crashed APs. In their approach, clients are augmented to start an ad-hoc network whenever an AP is faced with a problem. Authors in [132] proposed a distributed self-diagnosis protocol where 41 nodes test each other in the network. In their approach, each mobile node sends a task to its immediate neighbor nodes to determine if they are running or failed, then the output of this test is shared to all other nodes for attaining a global view of the network status. The focus in these works is in supporting disconnected clients to not associate with a halt/crash AP, but for that to be possible clients require cooperation among themselves and support from a third party device such as diagnostic server or management station. Instrumenting devices (APs and Clients) and introduction of third party devices in large-scale 802.11 networks can be difficult and expensive owing to higher number of users and APs. 3.3.3 Interference Detection Interference in 802.11 networks in most cases is caused by the broadcast nature of wireless links where transmission in one link of the network is able to interfere with the transmissions in other neighboring links. In addition to time varying nature of the wireless medium, interference in 802.11 networks can also be caused by other radio waves in the same frequency range. During interference data hardly make it through the air, in most cases requiring lots of retransmissions which results in overall 802.11 performance degradation. There exists a large body of work about interference in the literature, where researchers studied the effects of interference from different perspectives before suggesting ways and techniques to detect and mitigate its potential impact. For example, authors in [133] studied the impact of interference in chaotic 802.11 deployments on end-client performance. Result shows the performance of end-clients throughput suffers significantly in chaotic deployments, as most APs are not configured to minimize interference with their neighbors. In [134], author propose methods that include intelligent frequency allocation to APs, load-balancing of user associations to APs, and the use of adaptive power control to APs to mitigate the effect of interference in dense 802.11 deployments. Authors in [135] examined QoS characteristics for mobile-WLAN devices, in terms of the measured throughput, when multiple m-WLANs use different channels at different geometric distances. They find the effect of the channel distance on the throughput is non-uniform in nature, with some distances resulting into more than the expected channel interference. Authors in [136] studied the impact of RF interference on 802.11 networks, from range of devices such as Zigbee and cordless phones that crowd the 2.4GHz ISM band, and also from devices such as wireless camera jammers and non-compliant 802.11 devices that disrupt 802.11 operations. They experimentally confirm that changing 802.11 operational parameters such as clear channel assessment (CCA) threshold and rates is not effective at withstanding interference compared to moving to a different channel. Along the same direction of research, authors in [137] proposed an online interference estimation mechanism (PIE), implemented at the AP with a central controller placed at the wired network to observe ongoing traffic at different APs. They demonstrate that PIE is able to diagnose interference as well as certain performance issues such as hidden terminals and rate anomaly in real deployments. In [138, 139], 42 authors proposed tools that provides a time-domain view of how the medium is used in a given 802.11 channel. In [138], authors demonstrate that physical layer properties such as bit error patterns and medium busy times can be exploited to identify the cause of interference from non-802.11 devices. Whereas in [139] authors demonstrate that when the airspace is congested, changes in a victim node’s throughput are more closely related to its interferers than other devices. Other interesting research include [140], where authors investigated the problem of learning the graph structure based on network traffic transmission patterns, especially information about successes and failures in transmissions. They find that the networks with sparse interference patterns can be quickly identified by their approach than those with dense interference patterns. In [141], authors presented a general model for error probability and throughput of packet transmissions on a small wireless networks. In their approach, senders and receivers communicate at short distances and potential interferers are slightly far away. In the same line of research, authors in [142] proposed a model based on a Markov chain to capture the interaction between different senders and receivers in heterogeneous multihop wireless networks. The proposed model takes input traffic demand and received signal strength (RSSI) between pairs of nodes to estimate interference among an arbitrary number of senders. Authors in [143, 144] presented an approach based on Hidden Markov Model to estimate the interference between nodes and links by passive monitoring of wireless traffic. They first identify the interference relations between nodes and links, and model the 802.11 MAC as a Hidden Markov Model (HMM) to infer pairwise interference. The proposed technique in [143] was able to estimate non-binary pairwise interference, but failed to infer aggregated interference from a set of nodes. Whereas the proposed technique in [144] was able to infer the carrier-sense relationship between network nodes, but failed to detect selfish carriersense behavior of network nodes. Most of these approaches considered just one or few set of APs in their evaluation, or make use of dedicated sniffers and controllers to help capture network traffic for potential detection of interference patterns at the sender, link, and receiver. This again is not scalable due to a large number of users, APs, and network locations that exists in these 802.11 large-scale deployments. 3.3.4 Rogue AP Detection A rogue access point (Rogue AP) is an 802.11 access point that has been installed on a wired side of an 802.11 network, possibly without explicit authorization from the network administrators. This can be accomplished in either of two ways 1) it could be naively installed by a legitimate user who is not aware of its potential security implications, or 2) it could be intentionally installed as an insider attack. A rogue AP can pose significant security threat to a wired part of 802.11 networks; since it is possible through it to provide a backdoor into an 802.11 network to outsiders (i.e. illegitimate users). Moreover, rogue AP can potentially affect network connectivity by 43 interfering with nearby legitimate APs, leading to user intermittent connectivity and in some cases authentication failure at APs. The first step in the controlling of a rogue AP and its potential impact is to detect its existence. There are numerous efforts in the literature that try to automate rogue AP detection beyond the monitoring components normally used by network administrators to listen to wireless frames from all access points and to compare to the prerecorded list of legitimate APs. For example, authors in [145] proposed a centralized system that collects data transparently at data aggregation point such as a router or a gateway to detect the possibility of existence of rogue APs. Their approach first discovers all wireless stations associated in the network and verifies their authorization; thus any unauthorized wireless station found in a given AP indicates that the attached access point must be a rogue AP. In the same line of research, authors in [146, 147] used a packet analysis method to detect rogue APs. Their proposed method compares the gateways and the routes that each packet travels to determine whether an access point is legitimate or rogue. In [148], authors proposed a framework that separates frames into IP and TCP components; allowing for information such as client MAC addresses, SSID, channel assignment, encryption status, and beacon interval to be analyzed for potential events generated by a rogue AP. In another effort, authors in [149, 150] examined the round trip time (RTT) variation of network traffic resulted from the DCF, link-layer retransmissions, contention, coupled with a list of authorized APs and their respective switch ports to detect presence of rogue access points on a wired link. In [151, 152, 153], authors proposed a timing-based client-centric approach that uses the round trip time between the user and the DNS server to detect whether an AP is a rogue AP or not. In their scheme, the user will send a series of DNS requests and measure the RTT from the local DNS server; an abnormal RTT will be considered coming from rogue AP and therefore detected by the user. These works do not attempt to detect connectivity anomalies resulting from the existence of a rogue AP. Detection of rogue AP can minimize cases of user intermittent connectivity and user authentication failure in the network. In addition to time varying nature of the wireless medium and RF holes, the aforementioned user-related anomalies have potential to manifest themselves possibly due to interference effects caused by rogue APs in these large-scale 802.11 networks. We do not detect Rogue AP in this thesis, but we focus on detecting the user-related anomalous patterns of user’s intermittent connectivity and user’s authentication failure at APs that may perhaps be caused by Rogue AP. 3.3.5 Performance Anomaly Detection In addition to RF effects such as exposed and hidden terminals, the capture effect, and fading; there also other performance anomalies which contribute to overall connectivity degradation of 802.11 networks. In this section, we try to enumerate few important works that analyzed performance anomaly from 802.11 measurement data. 50 Discussion: From table 1, it’s clear that the majority of works in literature about 802.11 usage focused on modeling user mobility, user encounter patterns, user registration patterns, user access duration, and traffic at APs (item 1-10). For most of these works, especially item 2-6, the focus is to obtain particular statistics about individual users or group of users associations at AP, and to establish a model based on these quantities. This is particularly important if the goal is to understand user behavior, but if the aim is to understand access point usage behavior, then models that consider total user association events at AP regardless of movement patterns of individual users or group of users or their similarity in terms of associations and encounters patterns at AP can be increasingly beneficial to network administrators as far as capacity planning and resource provisioning of a large-scale network is concerned. For example, works about user registration patterns, user access durations, and traffic (item 7-9). Limitation of these proposed models is that they do not exclude association events and traffic resulting from the Ping-Pong sessions, as it was evident in the related work that removing Ping-Pong sessions in constructing statistical models can improve their fidelity significantly [71, 72]. This means models that get rid of the Ping-Pong sessions and at the same time capable of characterizing overall access point usage can be of great benefit to 802.11 administrators, than just those that consider total user associations, access durations, and throughput regardless of the type of connections established at APs. These observations are also applicable to the works about public 802.11 infrastructure usage (item 10). The only exception is on the works about general statistics (item 1) where no attempt was made to model 802.11 usage. On the other hand, most proposed approaches in the literature for detecting anomalies in 802.11 networks such as AP overload, AP crash, and AP interference (item 11-13) requires modification at either client or AP [121-128], or implementing cooperation between clients [130-132], and introduction of a third party device such controller, sniffers, and sensors [136-144]. However, instrumenting devices (clients and APs) and deployment of a third party device such as sniffers, controller, and sensors in 802.11 large–scale infrastructures can be increasingly difficult and expensive. Other approaches for anomaly detection, for example [148-153] and [158-175], were evaluated based on a small scale network, on a testbed, and through simulations, hence there is no guarantee on how these frameworks are able to scale-up to large networks with minimum cost and overhead. This is in addition to uncertainty about their actual performance when tested with real workload from a large-scale 802.11 deployment. There works for anomaly detection in 802.11 networks based on low cost data such as RADIUS session data and SNMP data, for example [117-120], [129], [133-135], [145147], and [154-157]. However, most of these works examine only few set of specific APs instead of all APs in the infrastructure. Hence their scalability is also not guaranteed. We conclude that there is no solution in the related work that supports all features depicted by table 1. As it was evident in table 1, most works in the literature supports only a subset of these features. Our proposed framework in this thesis is the only solution that supports all features provided by table 1. Moreover, there also features 51 peculiar to our proposed framework which are not supported by any of the previous work. These are columns in table 1 filled completely with marker “x”. Specifically, none of the work in the literature has considered probabilistic generative models for automatic access point usage characterization based on the aggregate users-AP association events from all users on all APs. In addition, none of the work has considered analysis of session endings at 802.11 AP for ease detection of anomalies in the usage of APs e.g. AP halt/crash, AP overload, AP interference, interference across the vicinity of an AP, AP persistent interference and, user authentication failure and user intermittent connectivity to APs. Furthermore, none of the work has considered statistical models for estimating occurrences of the aforementioned anomalies in AP usage with respect to aggregate network usage in terms of the total number of sessions. Unlike all related works, our proposed framework in this thesis is the only solution that performs both performance and fault management using easily accessible low cost data collected from the real large-scale 802.11 infrastructure. The ease of our proposed framework makes it a viable option for immediate adoption, complementing the existing network management approaches in large-scale 802.11 networks 3.5 Conclusion In this chapter we analyzed relevant works pertaining to the problem of usage modeling and anomaly detection in 802.11 networks. We presented more insights on the techniques and features employed by most existing works in the literature. Despite all these works in the literature, to the best of our knowledge this is the first attempt to derive generative probabilistic models of AP usage based on the readily accessible RADIUS session data (i.e. keep-alive event counts generated every 15 minutes for refreshing user-AP connections) and to compare them using the log-likelihood and AIC values figures of merit (chapter 4). This is also the first work to identify a usage pattern namely “abrupt ending” of 802.11 AP connections that happens when all or a significant number of user connections end in the same access point within a one second window (chapter 5). The emphasis on AP usage and the use of probabilistic generative models is better suited to performance management of 802.11 networks, especially capacity planning, and on network simulation experiments for evaluating protocols and applications in these large-scale 802.11 infrastructures. The emphasis on detecting abrupt ending of AP connections and their resulting patterns is better suited to fault management of 802.11 networks, as it may help network administrators to quickly and efficiently detect and fix connectivity problems in the usage of the access points (APs) of the large-scale 802.11 infrastructures (chapter 6). 52 Chapter 4 Modeling 802.11 AP Usage 4.1 Introduction In this chapter we motivate and introduce our modeling effort of 802.11 access point (AP) usage. Our goal is to propose generative probabilistic models of AP usage, which embodies the perception of the time that 802.11 users stay associated with APs when accessing network resources of a large-scale 802.11 network. We model usage based on AP daily keep-alive event counts. Keep-alive events are message sent by a mobile client every 15 minutes for refreshing the client’s association with an AP. Due to their periodic nature, keep-alive statistics can provide us with the estimates of the time users stay associated with an AP during which they may generate traffic with different profiles. We also employ an above-below AP event count average binary indicator that allows thinking about AP usage modeling in binary terms such as when AP usage is high or low. We train and evaluate our models based on a data set collected from FEUP’s 802.11 Eduroam hotspot. The models we present in this chapter are generative, in the sense they can be used to generate synthetic daily event counts for a single AP or a collection of APs. The emphasis on AP usage and the use of probabilistic generative models is better suited for: 1) performance management of large-scale 802.11 infrastructures e.g. models for capacity planning suitable for resource provisioning of the large-scale 802.11 networks, and 2) network simulation tools for evaluating applications and protocols in 802.11 infrastructures. In this chapter we proceed as follows. We first describe our experimental setup, the choice of data sets, and figure of merit used for evaluating our models in section 4.2. In section 4.3, we propose and evaluate different time-independent and time-dependent models for characterizing AP usage and present their evaluation results in section 4.4. In section 4.5, we evaluate models that consider week structure usage samples of APs. In section 4.6, we present performance evaluation of our extended time-dependent models based on data sets other than the one on which they were trained for. In section 4.7 we present concluding remarks. 53 4.2 Experimental Setup 4.2.1 Variables In this work, we use RADIUS authentication data. All 802.11 APs on campus are configured to send 1) log event ‘START’ whenever the wireless client authenticates or roams into the network, 2) interim log event ‘ALIVE’ every 15 minutes during the entire duration of connection for refreshing wireless clients association to APs, and 3) log event ‘STOP’ whenever the wireless clients disassociate or dis-authenticate from the network. All these log events are sent from 802.11 APs and are recorded in a central server running the RADIUS protocol (Remote Authentication Dial In User Service) specifically for authentication, authorization, and accounting as stipulated in RFCs 2865 and 2866 of IETF [35, 36]. The variables we want to model in this work are the AP daily keep-alive event counts, i.e. the series of interim updates generated periodically between the start of user connection at an AP until the end of user’s connection. Owing to their periodic nature, keep-alive statistics can tell us estimates of the time users stay associated with an AP, during which traffic of different profiles can be generated. We are using daily statistics because of the natural daily behavior cycle of users, especially on campuses. Previous studies on user behavior have indicated that the number of clients using a particular access point exhibits a weekly periodic behavior with a strong daily pattern, particularly during working days [56 - 64]. Rather than modeling traffic directly, we choose to model event counts based on the following two arguments. 1) There is evidence that user/AP association pattern and thus event counts are correlated with access duration and traffic at APs ([104, 108, 113] and figure 5). This means that event counts can also be used to understand baseline usage for APs, and consequently to support resource reservation in large-scale networks. 2) The possibility of plugging in different traffic models onto our event count models to generate different network traffic patterns according to the needs of simulation experiment or protocol to evaluate. 4.2.2 Data Set Our data set is a 183x53 matrix consisting of daily keep-alive event counts from 183 access points on 53 consecutive days. All our 183 APs are located on campus buildings bearing the same SIID. This allows wireless users to roam seamlessly between campus buildings and campus physical space, since most of these APs also cover outdoor environments. Buildings in our campus are mainly class rooms, theaters, offices, laboratories, canteens, libraries, etc., with the exclusion of residential buildings. The 53 consecutive days chosen for training our models include week-days and week-ends during one semester of the academic year 2009. Daily event counts in this data set are integers that range from 0 to the maximum of 2229, while the corresponding number of users responsible for these events ranges from 0 to the maximum of 186, (i.e. total number of users observed on campus during the studied trace period). Figure 5 provides more details on this usage information. We 54 observe more usage on the week-days than on weekends. Note the peaks (week-days usage) and the crests (week-ends usage) in plot “a” through “e” with a periodic (i.e. weekly) repetition. Figure 5(a) shows the number per day from all 183 APs. Figure 5(b) depicts distribution of the daily event counts of APs in the hotspot during the studied 53 days. Figure 5(c) shows the number of users per day from all 183 APs. Figure 5(d) shows the relationship between the number of events and the number of users over the 53 days. Figure 5(e) and figure 5(f) show the total number of events and the total number of traffic for all 183 APs, respectively. We split the data set and use two subsets for training/testing our models, taking into account that any value over 2/3 is appropriate for training the models [181]. Our training set includes data from the 53 days of 143 randomly selected access points. The test set includes data from the 53 days of the remaining 40 access points that were not used in the training set. We employ AP-based splitting not just because of its simplicity but rather due to the overall goal of our work, which is to understand usage of AP and try to predict daily and weekly usage of APs in the hotspot. Pearson’s Linear Correlation Coefficient: in order to gain deeper insights regarding relationships that may exist between different aspects of 802.11 AP usage in our data set, we employ Pearson’s linear correlation coefficient. We check for possible correlation between the number of users and the number of events, and also between the total number of events and the total traffic. We observe positive correlation in each case: 1) for the number of users and the number of events the correlation coefficient is 0.688, which can be visually seen in figure 5(d); while 2) for the total number of events and the total input bytes correlation coefficient result is 0.7063; and 3) for the total number of events and the total output bytes correlation coefficient result is 0.754, portrayed visually in figure 5(e) and 5(f). 55 (a) Number of events vs. days (b) Histogram of the event counts (c) Number of users vs. days (d) Number of Events, Users vs. Days (e) Total number of Events vs. Days (f) Total traffic in Bytes (Input, Output) vs. days Figure 5. Underlying features of the access points usage pattern in the hotspot 4.2.3 Figures of Merit Log-Likelihood: We use log-likelihood values to measure the goodness of fit of our models. The model with larger log-likelihood value is better than the one with smaller log-likelihood value [47, 182]. Therefore, for each probabilistic model we propose in the next sections, we compute the log-likelihood of that model based on specific training and test data sets. The log-likelihood of a model’s probabilistic density function M with parameter Θ on a data set X=(x1,x2,…,xN) is defined as: 56 LL(M;Θ;X)=∑ln⁡M(xi;Θ)⁡ N i=1 This is a standard figure of merit in probabilistic learning. For the same data set, better fitting models have higher log-likelihood. Computing the log-likelihood of different models on the same training data provides an indicator of which model better fits the data that was used to select and train the models. Computing the log-likelihood of models given the test data provides an indicator of which model performs better on the same, yet unseen data i.e. provides a measure of how well the model captures the statistical variation in the training set. Akaike Information Criterion: We also use Akaike information criterion (AIC) as an additional measure of the relative goodness of fit for our models and hence for model selection. AIC uses the concept of the information entropy and offers a relative measure of the information lost when a given model is used to describe real data [47, 183]. The general form for calculating AIC for a model with log-likelihood (LL) and the number of parameters K is defined as: AIC=−2∗LL+2∗K Given a set of candidate models for our data, the preferred model is the one with the minimum AIC value i.e. the model that minimizes the information loss and a penalty in increasing the number of estimated parameters. 4.3 Statistical Generative Models of 802.11 AP usage 4.3.1 Overview In this section, we aim to provide descriptions of our proposed generative statistical models of access point (AP) usage and their mathematical formulations. We first consider models that assume the independence between consecutive daily event counts of APs i.e. time-independent models. Although this may not be the case, it caters to simpler models. Later in the section we will compare these models with others that do consider dependency between consecutive daily event counts i.e. time-dependent models. Our time-independent models include a simple exponential distribution model, a discrete mixture of exponentials, a continuous Gamma mixture of exponentials, and an above-below model that allows presenting AP usage modeling problem in binary terms, for example if AP usage is high or low. Our time-dependent models include binary conditional probability (CPD) models and plugging-in above-below average models which provide a way to compare our time-independent models with time-dependent models. This is because our time-dependent models use binary variables for predicting next value for AP usage while the time-independent use event counts samples of APs. Moreover, we use seasoned ARIMA model (Auto-Regressive Integrated Moving Average) a standard tool for time series modeling, as an extra assessment of our time- 57 dependent models. Experimental evaluation and validation results of all our proposed models in terms of log-likelihood and AIC values from specific pair of training/test are provided in section 4.4. 4.3.2 Exponential We start our modeling endeavor by assuming that all daily event counts come from the same distribution, regardless of day or access point with an average rate λ. To explain this we pick a simple model i.e. exponential distribution because of its suitability in modeling events that occur continuously with constant average rate. We fit exponential model to our training and test data using maximum likelihood estimation function in Matlab. The following are the PDF and log-likelihood functions for this distribution on sample set X=(x1,x2,…,xN): pexp(x;⁡λ)=λexp(−λx) LL=⁡Nlnλ−λ∑xi N i=1 4.3.3 Discrete Mixture of Exponentials using K-Means We next consider a mixture of distributions and in particular a discrete mixture of two or more exponential distributions (representing group of APs with different event counts averages) which has the following standard mixture PDF and log-likelihood functions on sample set X=(x1,x2,…,xN): pdis_mix_exp(x;W,Λ)=∑wkλkexp⁡(−λkx)⁡ K k=1 LL=⁡∑ln∑wkλkexp⁡(−λkxi)⁡ K k=1 N i=1 Thus, each component of the mixture has a weight wk, where (w1,w2,…,wK)=W and ∑wk K k=1 =1, and a parameter λk of the exponential, where (λ1,λ2,…,λK)=⁡Λ. The standard approach to generate a daily event count sample x using this model is straightforward: first choose a component k by generating a sample from a multinomial distribution with probabilities 𝑊. Then generate a value x from an exponential distribution with parameter λk. We use Matlab’s K-Means algorithm to cluster the averages of daily event counts of different APs in the training and test sets into K components, with K ranging between 2 and 20. The centers of the K clusters are used as the parameters of the Λ exponential components, whereas the percentages of APs assigned to the different components of the mixture were used as weights 𝑊. 58 4.3.4 Mixture of Exponentials with Gamma Scale In a further attempt to gain better fitting in terms of log-likelihood and AIC values of the discrete mixture model of the previous subsection 4.3.3, without increasing complexity of the model (number of parameters), we employ a continuous mixture of exponentials with a parametric mixture model. We chose Gamma distribution Γ(λ;α,β)=β𝛼/Γ(𝛼).𝜆𝛼−1exp⁡(−βλ) as the mixing model (also called scale) on the different values of λ. The mixture distribution on sample set X=(x1,x2,…,xN) is then: pmix_exp(x,λ;α,β)=Γ(λ;α,β)λexp(−λx) pmix_exp(x;α,β)=∫ Γ(λ;α,β)λaexp(−λx)dλ +∞ 0=α βα (β+x)α+1 LL=⁡Nlnα+⁡α⁡N⁡lnβ−(α+1)∑ln(β+xi) N i=1 The second form of pmix_exp is the marginal distribution on x. For generating a sample with this model we first generate a λ from a Gamma distribution with parameters α and β, and then generate the sample from an exponential distribution with parameter λ. 4.3.5 Above-Below AP Daily Event Count Average In the case where we want to think about AP usage as either high or low it may be useful to consider a binary variable 𝜃 that encodes whether a sample is above or below the average daily event count of its AP. This is so in order to represent APs with different usage activity levels in the 802.11 hotspot (see figure 6). Our proposed Abovebelow average model is better suited to explain situations where some group of APs in the hotspot are highly utilized i.e. high activity APs (above average APs) and those with low activity (below average APs). We see a clear separation between these groups of APs from the results of K-Means clustering (K=2) of the average number of events of APs, as shown in figure 6. Figure 6. Clusters of APs based on above-below average event counts 59 For generating samples we use a three-level model. 1) For each daily event count sample we generate a value θ from a Gaussian distribution with support [0,1]⁡and parameters μ and σ. 2) We use θ as the parameter of a mixture of two components, each of which is a Gamma mixture of exponentials, with parameters α1,β1 for the component above the AP average and α0,β0 for the component below. 3) We finally generate a sample daily event count from an exponential distribution λ which we draw from the mixture of two components. This yields the following joint PDF, where Θ= (μ,σ,α1,β1,α0,β0) is the parameter vector and 𝒩[0,1](θ;μ,σ) is a Gaussian distribution with support [0,1]. pabv⁡blw(x,λ,θ;Θ)=𝒩[0,1](θ;μ,σ)⁡.⁡ .⁡⁡{⁡θ⁡Γ(λ;α1,β1)⁡λexp(−λx)+ +(1−θ)⁡Γ(λ;α0,β0)⁡λexp(−λx)⁡} Where 𝒩[0,1](θ;μ,σ)=𝒩(θ;μ,σ) ∫𝒩(ϑ;μ,σ)dϑ 1 0,θ∈[0,1] The marginal distribution on x can be obtained by integrating the joint distribution over λ and θ. We first integrate on θ by computing D(μ,σ)=∫θ𝒩[0,1](θ;μ,σ)dθ 1 0 – the expected value of θ on 𝒩[0,1](θ;μ,σ) – using the standard error function erf⁡(x). Then we integrate on λ using the result of the marginal distribution for the Gamma mixture of exponentials in the previous section. The marginal distribution on x is: pabv⁡blw(x;Θ)=D α1β1α1 (x+β1)α1+1+(1−D) α0β0α0 (x+β0)α0+1 With D(μ,σ)=− σ √2π(exp(−(1−μ)2 2σ2)−exp(− μ2 2σ2))+ +μ 2(erf(1−μ √2σ)+erf⁡( μ √2σ)) The log-likelihood of this model on sample set X=(x1,x2,…,xN) is: LL=∑ln N i=1 (pabv⁡blw(xi;Θ)) For parameter fitting and for computing the log-likelihood on the training and test data, we first split the training data into above-below AP average sets. For estimating 𝒩[0,1](θ;μ,σ) we calculate θa, i.e. the percentage of daily event counts above AP average for each AP, and fit a Gaussian distribution on the resulting set of θa⁡to get an estimate of μ and σ. Similarly, we calculate the daily event count rates for samples above 66 4.5 Time-Dependent Models Considering Different Settings of Variables 4.5.1 Overview In this section, we look at a different arrangement of time variables contrary from that of section 4.3 and 4.4. Rather than predicting tT based on all T-1 previous samples, here we consider different combinations of the T-1 previous samples, where one or more of the T-1 previous samples may or may not occur. The aim is to understand which combinations may result into better prediction of tT. We limit T to 4 and use R=2 through 8 to index models with the following arrangement of variables (tT-1), (tT-2), (tT-3), (tT-1, tT2), (tT-2, tT-3), (tT-1, tT-3), and (tT-1, tT-2, tT-3), as shown in figure 11. Figure 11. R=2:8 Different modeling proposals 4.5.2 Considering All-days AP Usage Samples We first consider usage samples from all APs on all days to build table CPD and plugging-in above-below average event count models for R=2:8, in a similar fashion as in section 4.3.6. and 4.3.7. We then compute the log-likelihood and AIC for all R=2:8 models. Cross validation results for table CPD models are shown in table 4. From table 4, it is apparent that the LL and AIC values on average are higher at R = 2, 5, 7, 8 and lower at R = 3, 4, 6. These results indicates using models (tT-2) and (tT-3) alone for table CPD models is of no benefit, while including model (tT-1) in any settings result into better prediction of tT. Model R=2 R=3 R=4 R=5 R=6 R=7 R=8 LLtrain -4518.07 -4812.89 -4818.67 -4486.86 -4799.51 -4488.81 -4415.89 LLtest -1267.23 -1352.00 -1354.38 -1262.45 -1348.39 -1259.08 -1241.78 AICtrain 9044.13 9633.78 9645.33 8989.73 9615.02 8993.62 8863.78 AICtest 2542.46 2711.99 2716.76 2540.89 2712.79 2534.17 2515.55 Table 4. Log-likelihood and AIC results of the R=2:8 CPD models on the training and test data sets 67 However, for the plugging-in above-below average models the log-likelihoods and AIC results change slightly across R=2:8 (see table 5) and in fact, on average are higher at R = 5, 6, 7, 8 and lower at R = 2, 3, 4. These results indicate including models (tT-1), (tT-2), and (tT-3) alone is not beneficial in modeling both the training and test data for these event count models. However, the LL and AIC results in table 5 are not significantly different. Model R=2 R=3 R=4 R=5 R=6 R=7 R=8 LLtrain -33401.7 -33401.5 -33401.5 -33392.4 -33393 -33394.9 -33367.9 LLtest -9405.87 -9405.90 -9405.99 -9398.72 -9398.7 -9398.7 -9390.72 AICtrain 66823.44 66823.03 66822.9 66812.8 66814.02 66817.71 66779.7 AICtest 18831.73 18831.80 18831.97 18825.44 18825.4 18825.39 18825.44 Table 5. Log-likelihood and AIC results of the R=2:8 Plugging-in above-below average models Moreover, when comparing results of table 5 and those of ARIMA model in table 2, it is evident that our plugging-in above-below models perform better on average in terms of log-likelihood and AIC values than ARIMA model fittings. This is true for all R=2:8 models on both training and test data sets. These results signify usefulness of the plugging-in above-below models in modeling event counts of AP over standard ARIMA model. In this section, we studied the impact of time dependency ordering of AP’s usage samples in the model. Our conclusion is two-fold: 1) for the binary CPD model the previous sample tT-1 is predominant and not including it has detrimental impact on the model ability to predict AP usage; 2) for the plugging-in above-below average model neither the order nor the number of previous samples significantly impacts model performance. 4.5.3 Considering Week Structure AP Usage Samples Next, we study AP usage based on the structure of the week: 1) week-days usage, 2) week-ends usage, and 3) specific Monday through Sunday, seven individual days of the week usages. The aim is to derive usage models for each and to predict usage at APs, for example usage in the next week-day, next week-end, and in the next specific day given its previous T-1 usage samples. We compute the log-likelihood and AIC values for all part of the week structure for both table CPD and plugging-in above-below average event count models. Table 6 shows cross validation results for all R=2:8 CPD models across all parts of weekstructure. LL and AIC values are apparently higher at R = 2, 5, 7, 8 and lower at R= 3, 4, 6; revealing the same insights as CPD models of the previous subsection 4.5.2. That is using model (tT-2) and (tT-3) alone for CPD models is of no benefit for all parts of the week structure, while including model (tT-1) result into better prediction of tT. 68 Model LL/AIC R=2 R=3 R=4 R=5 R=6 R=7 R=8 Week-Days LLtrain -3002,85 -3077,58 -3151,44 -2922,43 -3048,75 -2970,57 -2904,14 LLtest -840,281 -861,025 -883,476 -818,418 -853,039 -831,285 -814,084 AICtrain 6013,697 6163,157 6310,871 5860,862 6113,49 5957,141 5840,286 AICtest 1688,563 1730,049 1774,952 1652,836 1722,078 1678,57 1660,169 Week-Ends LLtrain -370,016 -389,146 -396,024 -363,529 -383,359 -366,189 -358,573 LLtest -106,407 -112,057 -114,167 -105,009 -111,152 -105,938 -100,033 AICtrain 748,0323 786,2912 800,0474 743,0589 782,7181 748,3776 749,1462 AICtest 220,8139 232,1136 236,3349 226,0189 238,3034 227,8765 228,0666 IndividualDays LLtrain -2320,9 -2369,55 -2386,31 -2294,31 -2360,82 -2310,87 -2282,09 LLtest -666,731 -681,526 -686,413 -664,174 -682,578 -667,475 -666,944 AICtrain 4649,806 4747,093 4780,625 4604,622 4737,63 4637,733 4596,187 AICtest 1341,463 1371,052 1380,826 1344,348 1381,156 1350,949 1365,888 Table 6. Log-likelihood and AIC results of the R=2:8 CPD models across all parts of the week-structure Nevertheless, for fitting plugging-in above-below average models on daily event counts of APs, we allow parameters μ and σ of the N[0,1] (θ, μ, σ) distribution in the model to change according to either week-days, week-ends, or individual days R=2:8 CPD table values. Consequently, we compute the log-likelihood and AIC values across all part of the week structure. Cross-validation results in table 7 indicates that loglikelihood and AIC values change very slightly across R=2:8 and are apparently higher at R = 5, 6, 7, 8 and lower at R= 2, 3, 4; this is true for all parts of the week structure. These results indicate including more previous samples (tT-1), (tT-2), and (tT-3) is of no significant benefit in modeling both training and test data for these models. Model LL/AIC R=2 R=3 R=4 R=5 R=6 R=7 R=8 Week-Days LLtrain -28428,5 -28431,5 -28427,5 -28423,1 -28422,9 -28423,1 -28415,3 LLtest -8022,01 -8022,02 -8022,02 -8021,92 -8021,99 -8021,89 -8021,81 AICtrain 56876,92 56883,0 56875,01 56874,19 56873,81 56874,23 56874,62 AICtest 16064,02 16064,03 16064,04 16071,83 16071,97 16071,78 16087,61 Week-Ends LLtrain -3838,84 -3835,07 -3832,96 -3827,36 -3822,69 -3824,84 -3820,1 LLtest -1028,55 -1035,22 -1028,93 -1023,39 -1024,19 -1024,39 -1015,8 AICtrain 7697,689 7690,143 7685,919 7682,71 7673,377 7677,677 7684,195 AICtest 2077,107 2090,441 2077,854 2074,77 2076,376 2076,784 2075,591 IndividualDays LLtrain -21178,7 -21189,9 -21186,6 -21159,5 -21157 -21154,2 -21162,9 LLtest -5941,63 -5940,76 -5941,33 -5924,46 -5922,94 -5923,38 -5918,36 AICtrain 42377,45 42399,71 42393,13 42347,03 42342,05 42336,34 42369,82 AICtest 11903,26 11901,51 11902,65 11876,92 11873,87 11874,76 11880,71 Table 7. Log-likelihood and AIC results of the R=2:8 Plugging-in models across all parts of the week-structure Moreover, the log-likelihood and AIC results after fitting ARIMA model on the week structure AP usage samples are shown on table 8. Results indicate that the plugging-in above-below models based on week-days, week-ends, and individual days AP usage samples in table 7 outperformed ARIMA model fittings in terms of both loglikelihood and AIC values. This is true for all R=2:8 on both training and test data, across all parts of the week structure. 69 ARIMA Model AR SAR Log-likelihood AIC Week-Days Train 0,0688 -0,0324 -34526,7 69061,33 Week-Days Test -0,0179 0,0664 -11072,0 22151,92 Week-Ends Train 0,1508 -0,0214 -12456,5 24921,06 Week-Ends Test 0,113 0,068 -4361,19 8730,38 Individual Days Train 0,6022 -0,2566 -46869,7 93795,43 Individual Days Test 0,073 0,4028 -15382,8 30821,61 Table 8. ARIMA model fitting results for all parts of the week-structure 4.5.4 Comparing All-days Model Vs. Hybrid Model In this section, we compare the all-days model of subsection 4.5.2 to a hybrid model of the week-days and week-ends models. Depending on the day of the week, the hybrid model will choose to apply the week-days model (if it’s a week day) or the week-ends model (if it’s Saturday or Sunday). We set the all-days model as a baseline and monitor the gain in log-likelihood incurred using the hybrid model. Cross-validation results indicate that the log-likelihood and AIC values of the hybrid CPD and plugging-in above-below models on average are higher than that of the all-days model for all R=2:8 (see table 9). This means the hybrid model is better than the all-days model in the prediction of tT for all possible values of R. However, using the hybrid model increases model complexity by order two. Model LL/AIC R=2 R=3 R=4 R=5 R=6 R=7 R=8 CPD LLtrain -1145,20 -1346,16 -1271,21 -1200,90 -1367,40 -1152,05 -1153,18 LLtest -320,54 -378,92 -356,74 -339,02 -384,20 -321,86 -327,66 AICtrain 2282,40 2684,33 2534,41 2385,81 2718,81 2288,10 2274,35 AICtest 633,08 749,83 705,47 662,04 752,41 627,72 627,31 PluggingIn LLtrain -1134,36 -1134,93 -1141,04 -1141,94 -1147,41 -1146,96 -1132,50 LLtest -355,31 -348,66 -355,04 -353,41 -352,52 -352,42 -353,11 AICtrain 2248,83 2249,89 2261,97 2255,90 2266,83 2265,80 2220,88 AICtest 690,60 677,33 690,08 678,84 677,05 676,83 662,24 Table 9. The gain in log-likelihood and AIC values across R=2:8 of the hybrid model over all-days model 4.5.5 Comparing All-days Model Vs. Individual Days Model We lastly compare the all-days model of section 4.5.2 to the individual day’s usage model. As such, depending on the day of the week, the individual day’s model will choose to apply appropriate model for a given particular day of the week e.g. if it is Monday an AP usage models for Monday will be chosen. We set the all-days model as a baseline and monitor the gain in log-likelihood incurred using the individual day’s model. The log-likelihood and AIC values of the individual days CPD and plugging-in above-below model are significantly higher than that of the all-days model (table 10). This shows that the individual day’s model is considerably better than the all-days model in the prediction of tT . This insight is confirmed by cross-validation results on training and tests data sets, see table 10. However, using the individual day’s model increases model complexity by order 7. 70 Model LL/AIC R=2 R=3 R=4 R=5 R=6 R=7 R=8 CPD LLtrain -2197,17 -2443,34 -2432,36 -2192,55 -2438,69 -2177,94 -2133,80 LLtest -600,50 -670,47 -667,97 -598,28 -665,81 -591,61 -574,84 AICtrain 4394,33 4886,69 4864,71 4385,11 4877,39 4355,88 4267,59 AICtest 1201,00 1340,94 1335,93 1196,55 1331,63 1183,22 1149,66 PluggingIn LLtrain -12223,0 -12211,6 -12214,9 -12232,9 -12236,0 -12240,7 -12205,0 LLtest -3464,24 -3465,14 -3464,66 -3474,26 -3475,76 -3475,32 -3472,36 AICtrain 24445,99 24423,32 24429,77 24465,77 24471,97 24481,37 24409,88 AICtest 6928,47 6930,29 6929,32 6948,52 6951,53 6950,63 6944,73 Table 10. The gain in log-likelihood and AIC values across R=2:8 of the individual days model over the all-days model 4.5.6 Summary In this section we consider all-days and week structure usage sample of APs. We compared different binary CPD models and plugging-in above-below average models based on all-days and on different parts of the week structure AP usage samples, with different time dependency ordering of samples. In addition to confirming our guess that considering week structure has a positive impact on the performance of all models, our conclusions are: 1) individual days model has approximately twice performance gain from all-days model when compared to hybrid model on CPD data; whereas 2) on event count data using the plugging-in above-below average model, this performance gain is an order of magnitude higher than that of CPD model; 3) binary CPD performance continues to show dependency on previous sample and plugging-in above-below average model performance on test data continues to be independent of AP’s previous sample ordering, regardless of week-day, week-end, hybrid, or individual day model and data. 4.6 Performance Comparison of AP Usage Models based on Different Data Sets 4.6.1 Overview In this section, we want to understand the applicability and feasibility of using the binary conditional probability models and plugging-in above-below models of the previous section 4.5 when applied to different usage data. Namely, we want first: 1) to employ model derived from the parameters of all-days model and apply it to week-days and week-ends AP’s usage data; next 2) to employ model derived from the parameters of week-days model and apply it to all-days and weekends AP’s usage data, and lastly; 3) to employ model derived from the parameters of the week-ends model and apply it to all-days and week-ends AP’s usage data. Intuitively, models should have better performance on the data set on which they were trained, e.g. the all-days CPD or plugging-in above-below model should have better log-likelihood on all-days data than on week-days or week-ends AP usage samples. The aim of this section is to understand the extent to which this reasoning is correct. 71 4.6.2 Binary Conditional Probability Models To realize the above set objectives, we first consider binary R=2:8 CPD models. Figure 12 shows cross-validation results for these CPD models based on the aforementioned 1-3 scenarios. On average: 1) the binary CPD models based on all-days parameters outperformed others when applied to the all-days AP’s usage data; similarly 2) the binary CPD models based on week-days parameters outperformed others when applied to the week-days AP’s usage data; and likewise 3) the binary CPD based on week-ends parameters outperformed others when applied to the week-ends AP’s usage data. This is true on both training and test data sets across all R=2:8; hence agrees with our first intuition that models should perform better on the data set to which they were trained. 4.6.3 Plugging-in Above-Below Average Models We also consider R=2:8 plugging-in above-below event count models. Figure 13 shows cross-validation results for these event count models given the same conditions stated in 4.6.1. The log-likelihood results change slightly across R. On average: 1) the log-likelihood of the plugging-in above-below average models based on the parameters of all-days given the all-days AP’s usage data outperformed others on training data set, while for the test data set plugging-in models based on week-ends usage data perform better than others; 2) the log-likelihood of the plugging-in above-below average models based on week-days parameters given the week-days usage data outperformed others on the training data set, while for the test data plugging-in week-ends models perform better; 3) the log-likelihood of the plugging-in above-below average models based on the parameters of all-days to the week-ends usage data outperformed others on both training and test data sets. However, the maximum, minimum, and standard deviation in the cross-validation results continue to indicate large dispersion throughout R=2:8. 4.6.4 Summary In this section we tried to understand how different week structure models perform when applied to parts of the week AP’s usage data for which they were not trained on. For binary CPD models we confirmed our intuition that e.g. week-days model had better performance on week-days usage data than on all-days or week-ends usage data; this is also true for all other CPD models. However, for the event count data using the plugging-in above-below average models we could not confirm this, given the large dispersion of the results. 72 Figure 12. 100 random hold-out cross-validation results of the R=2:8 CPD models when applied to different AP usage data, average (solid lines), standard deviation (bars), minimum and maximum (dotted lines) 73 Figure 13. 100 random hold-out cross-validation results of the R=2:8 Plugging-in abovebelow average models when applied to different usage data, average (solid lines), standard deviation (bars), minimum and maximum (dotted lines) 74 4.7 Conclusions In this chapter, we presented an approach to model 802.11 AP usage that focuses on daily keep-alive event counts proportional to the time users are connected to an AP, and used generative probabilistic models such as a Gamma mixture of exponentials, binary Conditional probability models, and a plugging-in above-below AP average model that makes it easier to consider dependencies between consecutive samples in time. We compared our models with the log-likelihood and AIC values standard figures of merit in statistical learning, based on specific training and test data sets. We conclude that the increase in complexity of the T = 6 plugging-in above-below models with 38 parameters (that has the best log-likelihood and AIC values on both training and test sets) leads on average to a much smaller gain, in terms of both log-likelihood and AIC values, as compared to complexity incurred by using the Gamma distribution with 2 parameters and the above-below model with 6 parameters. These conclusions are supported by a 100-fold random holdout cross-validation. Cross-validation results also confirmed the significant gain in log-likelihood and AIC values on the training and test data sets of using 1) a hybrid model for week-days/week-ends and 2) individual day’s model for a given specific day of the week, as well as 3) the meager impact of adding more time dependency through AP previous samples and of changing time variable settings for the event count plugging-in models. We believe models presented in this chapter can be useful as a complement to the existing performance management techniques of large-scale 802.11 networks. Based on the insights derived from our models, particularly conditional probability distribution (CPD) models, 802.11 administrators might be able to understand and predict AP usage on daily and weekly basis, and thus allocate network resources according to expected usage, for example, installing additional APs on days where is usage is known to be high. Moreover, anomaly detection of 802.11 AP usages can also be enhanced based on the insights derived from our models e.g. baselines or usage levels of different APs and days can be established. This means that high usage (e.g. event counts) for a particular AP that is not known usually to be very active could indicate the possibility of an anomaly such as AP overload. The absence of activity/events in an AP that is usually known for its high usage could indicate an anomaly such as an AP crash. The same idea can be applied for detecting usage anomalies on different days of the week, with exception for holidays. For example, days which are usually known for low usage (event counts), high usage in these days could mean an unusual event has happened in the infrastructure (e.g. conference), and vice versa. In this thesis, we do not further explore our AP usage models for anomaly detection. We focus instead on a pattern that we call “Abrupt Ending” of 802.11 AP connections. In the next subsequent chapters, we will explain methods, algorithm, and models for detecting and characterizing such pattern of anomalies in AP usage based on the collected 802.11 usage data. 75 Chapter 5 Anomaly Detection of 802.11 AP Usage - Abrupt Ending of 802.11 AP Connections 5.1 Introduction In this chapter, we introduce our first anomaly detection work. Our emphasis is on detecting patterns of anomaly in the usage of 802.11 APs. In our context, an anomaly is a pattern that does not conform to normal 802.11 AP usage behavioral patterns. Anomaly detection refers to the process of finding these non-conforming patterns. The importance of anomaly detection in 802.11 networks or in any other domain is that usually anomalies translates to significant, and often critical, actionable decisions in an attempt to remedy the anomalous situation. In this chapter we focus on a usage pattern named “abrupt ending” of 802.11 AP connections that happens when a large number of user sessions in the same access point (AP) end within a one second window. Our goal is three-fold: 1) to investigate a method for detecting abrupt ending of AP connections from massive 802.11 usage data, 2) to examine possible causes that influence AP abrupt ending occurrence; and 3) to propose models for proper characterization of their occurrences. The emphasis on detecting and characterizing patterns of anomaly in AP usage is critical for fault management of large-scale 802.11 networks as it may help network administrators to quickly and efficiently detect and fix different connectivity problems that users of largescale 802.11 networks often face, for example authentication failure and intermittent connectivity of user connections. We will follow this up in the chapter 6. We proceed as follows in this chapter. In section 5.2, we define abrupt ending of AP connections, and describe what happens upon their occurrences, including resulting connectivity disruptions to wireless users. We also investigate a method for detecting abrupt ending of AP connections from the collected massive 802.11 usage data in this section. In section 5.3, we examine causes of AP abrupt endings manifestation from different perspectives including users, user devices, AP models, AP locations, and aggregate usage of the 802.11 infrastructure network. In section 5.4, we propose statistical models for characterizing occurrence of abrupt endings with respect to aggregate usage of 802.11 networks, in terms of total number of sessions. In section 5.5 we present concluding remarks. 82 (a) Daily total network usage vs. (b) Hourly total network usage vs. total total number of Abrupt endings number of Abrupt endings (c) Total number of abrupt endings (d) Total number of abrupt endings for each day of the week for each hour of the day Figure 17. Underlying salient features of the aggregate 802.11 total network usage and total abrupt ending occurrences 5.4 Statistical Models of Abrupt Ending Occurrences 5.4.1 Methodology In this section, we aim first to find out if there exists any significant statistical relationship between abrupt ending occurrences and aggregate 802.11 network usage, in terms of the total number of sessions established per hour. Second, we aim to propose different statistical models that best capture the underlying relationship between abrupt endings and aggregate 802.11 network usages. In this way, models for characterizing abrupt ending of AP connections applicable for fault management of large-scale 802.11 networks can be established. To accomplish this investigation we first obtain average values of abrupt endings for different ranges of session intervals called bins. We search for abrupt ending event in every 10 session length while maintaining a count. A session interval is considered to be a bin if at least 50 non-zero elements (abrupt ending events) have been identified. This allows us to reduce the randomness of the response variable observed in figure 83 17(b), while introducing linear effects in the observations. This approach is similar to the partitioning method used in [185]. The resulting plot depicting the relationship between these session intervals (bins) and their respective average number of abrupt endings is given by figure 18. Assuming this linear behavior, traditional linear regression techniques using standard least-squares estimation can be employed. Figure 18. Total 802.11 session count vs. average number of abrupt endings 5.4.2 Linear Regression Model In this section, we intend to fit a simple linear regression model in order to depict details of the statistical relationship between average abrupt endings (y) and the aggregate 802.11 network usage in terms of total number of sessions per hour (x), illustrated by figure 19. We fist perform correlation analysis between the two variables. Pearson correlation analysis of the variables resulted into 0.94, which indicates strong positive correlation between independent variable “x” and dependent variable “y”. We then proceed in fitting linear regression model, traditionally given by the equation: y = βo + β1x + ϵ. We assume the error term to be independent of “x” and is normally distributed variable with zero mean, similar to previous work [186]. Moreover, in our linear model the y-intercept βo is insignificant, because its p-value (0.486) is much greater than all significant levels tested (0.10, 0.05, 0.01, and 0.001), hence fail to pass goodness of fit test. Interestingly, this result affirms further our first intuition that no abrupt ending can be observed once there are no sessions in the 802.11 networks. We therefore consider βo= 0, which simplifies the final linear regression equation to y = β1x. We use linear model package in R to obtain the estimates for β1= 0.0030685 and its corresponding p-value < 2e-16; which passes goodness of fit test at all significance levels tested (0.10, 0.05, 0.01, and 0.001). The final linear equation for estimating average number of abrupt endings given total number of sessions is given by the following linear equation: y = 0.0030685 x, portrayed visually by figure 19. In order to assess goodness of fit of our proposed linear model we use the coefficient of determination R2 [187]. The coefficient R2 indicates how closely values obtained after 84 fitting a model match the dependent variable the model is intended to predict. R2 values are usually between 0 and 1; a higher value of R2 implies higher prediction capability of the model. We obtain the estimate for R2 = 0.96, which further confirms the significance of the statistical relationship between these two variables. In simple terms, this means our proposed simple linear regression model is able to approximate 96% of the response in the dependent variable. Figure 19. Plot of the proposed simple linear regression model fittings We lastly examine the residuals and the fitted values of our simple linear regression model. This is a standard way in any modeling endeavor, for gaining further insights related to the goodness of fit of the proposed model. By definition the residual data of the simple linear regression model is the difference between the observed data of the dependent variable and the fitted value. Analysis of fit (figure 20(a) and 20(b)) suggests that the proposed linear equation (figure 19) is able to approximate bulk of abrupt ending averages (about 96%) as majority of the residuals (observed - fitted values) lies between -1 and 1. 85 (a) Plot of the fitted value vs. residuals after regression line fitting (b) Histogram of the residuals after regression line fitting Figure 20. Simple linear regression model fittings and resulting analysis of fit 5.4.3 Continuous Probability Distributions Models The good fitting results achieved by the regression analysis of the variables in the previous section 5.4.2 ignore the effect associated to distributions of elements within the bins and the possible impact of the error term in the relationship. In this section, we argue that better or improved fitting results can be achieved by employing other statistical models that can as well fit elements within the bins i.e., fitting individual abrupt ending occurrences at distinct intervals of the total number of sessions. A large number of elements within most session intervals lie along the x-axis close to zero (see figure 17(b)). As such, we believe the exponential family of continuous probability distributions models (Exponential, Gamma, and Gaussian) is better suited to explain 86 this underlying characteristic. To assess goodness of fit for these models with respect to each bin, we use the Log-likelihood and the Akaike Information Criterion (AIC) metrics similar to chapter 4. These are standard figure of merit in statistical learning [47, 182, 183]. The model with larger log-likelihood value and AIC value is better than the one with smaller log-likelihood value and AIC value for the same set of data. The log-likelihood of a model’s probabilistic density function M with parameter Θ on a data set X=(x1,x2,…,xN) is defined as: LL(M;Θ;X)=∑ln⁡M(xi;Θ)⁡ N i=1 Whereas the general form for calculating Akaike Information Criterion (AIC) for a model with log-likelihood (LL) and the number of parameters K is defined as: AIC=−2∗LL+2∗K Exponential distributions: To commence this modeling effort, similar to chapter 4, we first pick a simple Exponential distribution model. We fit this model on abrupt endings data at each intervals (bins) of the total number of sessions, using maximum likelihood estimation function in R. The following are the PDF and log-likelihood expressions on sample set X=(x1,x2,…,xN): pexp(x;⁡λ)=λexp(−λx) LL=⁡Nlnλ−λ∑xi N i=1 Gamma distributions: Similarly in another attempt to gain better fitting, we fit a two parameters model of continuous probability distributions i.e. Gamma distributions on abrupt ending data at each bin. The PDF and corresponding log-likelihood expressions for Gamma distributions on sample set X=(x1,x2,…,xN) are: pgam(x;α,β)=β𝛼/Γ(𝛼).𝑥𝛼−1exp⁡(−βx) LL=⁡Nα β−∑xi N i=1 Gaussian distributions: In a final attempt to gain an improved fitting, we eventually fit Gaussian distributions on abrupt ending data at each bin using maximum likelihood estimation function in R. The following are the PDF and log-likelihood expressions for the sample set X=(x1,x2,…,xN) which is normally distributed⁡𝑁(μ,σ2): pgau(x;μ,σ2)=1 √2πσ2⁡(exp(−(1−μ)2 2σ2)) LL=⁡−N 2ln(2π)−N 2ln(σ2)−1 2σ2∑(xi−μ)2 N i=1 87 Results: Figure 21 depicts fitting results of the Exponential, Gamma, and Gaussian distributions at various bins. Figure 21(a) shows the estimated rate (λ) parameter of the Exponential distributions at each bin. When we take the inverse of the estimated rates (i.e. 1/ λ), this yields very similar values to bin’s averages used in the linear regression model fitting (figure 19). Figure 21(b) shows the estimated shape parameter α and rate parameter β of the gamma distributions, as estimated by maximum likelihood function in R. Again these parameters when taken as α / β at each bin produce similar values as those used in linear regression fittings. Figure 21(c) shows the estimates for mean 𝜇 and standard deviation σ of the Gaussian distributions. Again, the estimates for means 𝜇 are very similar in values to the bin’s averages used in the linear regression model fitting of as well as 1/⁡𝜆 of the exponential model and α / β of the Gamma distributions. (a) The estimated λ parameter of the (b) The estimated α and β parameters of Exponential distribution the Gamma distribution (c) The estimated μ and σ parameters of the Gaussian distribution Figure 21. Model parameters and fitting results for Exponential, Gamma, and Gaussian distributions models on abrupt ending data set at each bin In order to determine goodness of fit of the proposed models, we subsequently compute the log-likelihood and AIC values at each (bin) using these estimated rate parameters. Results are presented in figure 22(a) and 22(b), respectively. Generally, Exponential distributions model outperforms Gamma and Gaussian distribution models in terms of AIC values in most of the bins (see dash-dot line in figure 22(b)), while achieving comparable results in terms of log-likelihoods (see figure 22(a)). This is due 88 to the simplicity of the exponential model which has only one parameter. Although Gaussian and Gamma models have similar complexity, in terms of number of parameters, the poor performance of the Gaussian model in terms of log-likelihoods is attributed to skewedness of elements within bins (i.e. elements being not symmetric); this underlying characteristic can be better explained by Exponential and/or Gamma model. (a) Log-likelihood results for all the three models (b) AIC results for all the three models Figure 22. Log-likelihood and AIC results for Exponential, Gamma, and Gaussian distributions models on abrupt ending data set at each bin 89 5.5 Conclusions In this chapter, we have identified a new usage pattern named “abrupt ending” of 802.11 AP connections that happens when a large number of user’s sessions in the same access point (AP) end within a one second window. We observed up to 40 distinct user’s sessions ending at the same second in some access points and over thousands of abrupt endings in a two and a half year 802.11 traces of the Faculty of Engineering of the University of Porto. We confirmed the existence of significant statistical relationship between abrupt ending occurrences and 802.11 aggregate usage, in terms of total number of sessions. We proved this relationship by: 1) Pearson correlation coefficient between variables (r = 0.94), 2) Coefficient of determination (R2 = 0.96) between variables in the linear regression model, and 3) P-values (< 2e-16) which passes all significant levels tested. In addition, we demonstrated that a family of continuous probability distributions (e.g. Exponential, Gamma, and Gaussian models) is suitable to capture the underlying relationship between abrupt ending occurrences and aggregate 802.11 usages. Due to its simplicity, Exponential distributions model outperformed others and proved to be sufficient for capturing the overall characteristics between these variables. We believe our methods and models presented in this chapter can enhance anomaly detection in the large-scale 802.11 networks. Detecting patterns of anomalies in AP usage is essential for effective management of large-scale networks, particularly in handling network reliability problems. Based on the insights of the models proposed in this chapter, 802.11 administrators might be able to characterize abrupt ending occurrences in large-scale 802.11 infrastructures and thereby plan, and make decision or act in an attempt to guarantee continuous and reliable coverage of 802.11 networks. In the next chapter, we will present algorithm for characterizing abrupt ending of AP connections discussed in this chapter into different forms of anomaly-related patterns. Once the appropriate nature of an anomaly is established, relevant counter measures can be easily taken to remedy such anomaly. This is important for a proactive approach to fault management of the large-scale 802.11 networks. 90 Chapter 6 Detecting and Modeling Patterns of Abrupt Ending of 802.11 AP Connections 6.1 Introduction The task of anomaly detection plays significant role in 802.11 networks. In most cases, the detection of patterns of anomaly results in actionable decision by network administrators in an attempt to mitigate the effects caused by anomalous situations. For network administrators to make informed and appropriate decisions first the true nature of anomalies needs to be established and existence of their underlying patterns identified. In this chapter, we take a step further from detecting individually abrupt ending of AP connections and focus on detecting and characterizing patterns of anomaly resulting from the occurrence of AP abrupt ending of connections. We investigate the existence of these patterns by analyzing the timing of each abrupt ending event, the regularity of AP abrupt ending within a day, and the presence and absence of continued sessions after each AP abrupt ending event. We consider these factors mainly for detecting AP-related anomalous patterns namely interference across AP vicinity, AP persistent interference, AP halt/crash, AP overload, and AP interference. For detecting the user-related patterns of user’s authentication failure and users’ intermittent connectivity to APs, we analyze the identity of users involved in each abrupt ending, and also we observe user intermittent sessions just before abrupt ending occurrences and their prevalence afterwards. The emphasis on detecting and characterizing these anomaly-related patterns is crucial for fault management of the large-scale 802.11 networks. Proper detection of the aforementioned patterns might help network administrators in making informed decisions and taking timely actions. Examples of the short term actions that can be taken include rebooting of the APs, adjusting power settings of APs, and changing of operational channels and antenna radiation patterns of the APs [129-131]. When thinking of long term planning and maintenance of 802.11 networks, actions such as adding more APs, and replacing and relocating some APs can be useful given the nature of the problem. In this chapter, we do not further explore actionable decisions by 802.11 administrators, but rather focus on characterizing abrupt endings into respective patterns of AP usage anomaly. In section 6.2, we present an algorithm for detection and characterization of abrupt endings into different forms of anomaly-related patterns. In section 6.3, we discuss experimental results using different thresholds of time intervals learned from our data set, for depicting anomaly-related patterns described in section 6.2. In section 6.4, we 91 propose statistical models for characterizing occurrence of these anomaly-related patterns. In section 6.5, we provide evaluation of our experimental results using a density based clustering algorithm (DBSCAN) and on data set from different 802.11 deployments. In section 6.6, we provide an online implementation of the detection and characterization of abrupt endings into their respective anomaly-related patterns using complex event processing techniques. In section 6.7 we provide concluding remarks. 6.2 Algorithm for Detection and Characterization of Anomaly-related Patterns 6.2.1 Anomaly-Related Pattern Characterization We consider the following anomaly-related patterns based on manual inspection of 802.11 AP usage data. From AP’s perspective these patterns are: 1) Interference across AP vicinity patterns - this is when abrupt ending occurred as well to neighboring APs within specified time interval, possibly due to interference from the neighboring APs or the increase in number of collisions taking place in the wireless medium. 2) AP persistence interference patterns – this is where repeated abrupt endings are observed for a given AP during a specified duration of time, possibly due to dead spot/RF holes. 3) AP overload patterns - if the presence of continued session(s) to an AP is evident after abrupt ending during a specified time interval; this might be the case of heavy utilization by some few users. 4) AP halt/crash patterns - when no log event (START, ALIVE, or STOP) is seen after abrupt ending for a given time period; this may indicate possibility of AP failure. 5) AP Interference patterns - where abrupt ending events do not belong to any of the aforementioned patterns, perhaps caused by the presence of source of interferences e.g. RF devices. We name these anomalous patterns as APrelated patterns. We also consider user-related anomalous patterns in our study. These patterns are: 6) User authentication failure to AP – when abrupt ending resulted from a single user, possibly due to the use of wrong or expired credentials by user or problem in the network services e.g. authentication serves, and 7) User intermittent connectivity to AP patterns – when users intermittent connectivity is evident just before and after abrupt ending occurrence, possibly due to changing wireless conditions and inconsistent coverage of 802.11 networks. 6.2.2 Anomaly-Related Pattern Definition We use the following definitions for detecting anomaly-related patterns outlined in the previous subsection. For AP-related patterns: 1) Pattern A (interference across AP vicinity) occurs when more than one AP encounter abrupt endings in a 60 seconds time interval. 2) AP Persistent interference (pattern B) happens when four or more abrupt endings occur in one specific AP in a space of one day. 3) AP overload (pattern C) happen when continued sessions are observed within 15 minutes after abrupt ending. 4) AP halt/crash (pattern D) occurs when an AP stops registering events for more than half an hour after AP abrupt ending occurrences, i.e. when no user connection is observed at 98 6.3.8 Summary In this section, we presented experimental results for all anomaly-related patterns investigated in this thesis. We demonstrated the impact of each threshold setting on the detection results for each pattern. Detection of these patterns may necessitate remedial decision and action from 802.11 administrators. Although actionable decisions are beyond the scope of this thesis, but here we highlight some of the remedial actions that can be considered for each of these patterns. For example: 1) pattern A - may include action such as adjusting power settings of APs, and changing of radiation patterns and frequency channels of the APs. 2) Pattern B - may require relocating APs that often encounters abrupt ending, or changing configuration parameters of these APs. 3) Pattern C - may need action such as increasing density of APs, especially in the location(s) which appears to be congested so often. 5) Patten D - may require rebooting, or replacing the crashed or halted APs. 5) Pattern E - in addition to removing source of interference close to APs, requires actions similar to pattern A; since both are caused by RF interference. 6) Pattern F - may necessitate blocking of unauthorized or problematic users, issuing of new credentials to legitimate users, and in some situations carefully examination of the wired part of the large-scale 802.11 networks can be desired. 7) Pattern G - decisions here depends on the nature of the abrupt ending characterizing the identified intermittent connections: for example, if the abrupt ending belongs to pattern A then relevant measures applicable to pattern A can be employed, and so on. These remedial actions are attempts that can be considered by 802.11 administrators, in order to guarantee continuous and reliable coverage of the large-scale 802.11 networks. 6.4 Anomaly-Related Pattern Modeling: Experimental Results 6.4.1 Linear Regression Models In this section, we propose simple linear models to capture overall characteristics of the abrupt endings associated to anomaly-related patterns investigated in section 6.3 and aggregate 802.11 network usage, in terms of the total number of sessions established per hour, similar to section 5.4.2. Although in section 5.4.2 we used average abrupt endings as a dependent variable irrespective of patterns, in this section we use average abrupt endings significant to a particular pattern as dependent variable “y” and aggregate network usage (i.e. total number of sessions per hour binned at various session intervals) as independent variable “x”. However, there is an exception here particularly for anomaly-related pattern B (AP persistent interference), because these patterns are detected in a period of one day (see definition in subsection 6.2.2). Rather than using hourly aggregate network usage for these patterns, we instead use daily aggregate 802.11 network usage (total number of sessions per day) as independent variable “x”. Another exception is for pattern G (user intermittent connectivity) where we analyzed un-binned observations of the total number of intermittent sessions (see definition in subsection 6.2.2) per hour before and after abrupt ending occurrences (as independent variable “x”) versus the total number of abrupt endings in the same hour (dependent variable “y”). We did not bin observations for this pattern because the majority of 99 elements in the response variable are non-zero with linear behavior (see figure 25(e) and 25(f)). We fit linear regression model between variables for each anomaly-related pattern investigated in this chapter using equation y = βo + β1x similar to chapter 5. Table 19 present parameters of the fitted simple linear regression models and their corresponding goodness of fit tests for all anomaly-related patterns of AP usage. Figure 25 illustrates simple linear regression models fitting only for those patterns exhibiting significant relationship between variables. Results: Pearson correlation (r) and regression analysis of the variables (R2 and pvalues in table 19) indicates strong significant statistical relationship between variables for all anomaly-related patterns studied except for two patterns: 1) AP halt/crash and 2) user authentication failure. In these two patterns the Pearson correlation and R2 coefficients are reasonably small, whilst their p-values fail to pass all significant levels tested, particularly at 0.01 and 0.001. These results means AP halt/crash patterns and user authentication failure patterns might be the consequence of other causes apart from 802.11 network usage. For example: AP misconfiguration and defective hardware for the former pattern, while for the later pattern might be the consequence of the use of wrong or expired credentials and of problems related to network or network services in the wired part of 802.11 networks, e.g. authentication/logging-in servers problem. As for the other patterns, results suggest statistical significance of the relationship between variables in the regression equations, since their p-values pass all significant level tested (0.10, 0.05, 0.01, and 0.001). In addition, results for R2 indicate that all our fitted linear models are able to explain the majority of the response in the observed values of the dependent variable. Note, the y-intercept is insignificant for all anomaly patterns studied, similar to the insights of chapter 5, except for pattern G (intermittent connectivity patterns before and after abrupt ending occurrences), where in both cases the y-intercept is significant with their p-values being able to pass all significant level tested (0.10, 0.05, 0.01, and 0.001). These insights indicate that intermittent sessions can be important indicator of 802.11 AP usage anomalies, and can subsequently lead to abrupt ending of AP connections. Therefore, models developed based on these patterns can be helpful in estimating occurrences of AP abrupt ending of connections with respect to usage of these large-scale 802.11 infrastructures. Pearson Correlation Linear Regression Model Parameters Anomaly-Related Pattern r β0 β1 R2 p-value Across AP Vicinity Interference 0.87 - 0.0494 0.944 6.68E-13 AP Persistence Interference 0.84 - 0.0216 0.888 5.19E-09 AP Overload 0.74 - 0.00117 0.863 4.38E-03 AP Halt/Crash 0.34 - 0.00219 0.509 0.0358 AP Interference 0.87 - 0.00725 0.898 2.2E-16 User Authentication Failure 0.21 - 0.00083 0.524 0.0264 Intermittent Connectivity (Before) 0.81 2.321 0.0447 0.761 2.2E-16 Intermittent Connectivity (After) 0.84 2.202 0.0432 0.798 2.4E-16 Table 19. Linear regression models fitting results and goodness of fit analysis for each anomaly-related pattern 100 (a) Across AP vicinity interference patterns fitting (b) AP persistence interference patterns fitting (c) AP Overload patterns fitting (d) AP interference patterns fitting (e) Intermittent connectivity patterns (f) Intermittent connectivity patterns fitting before abrupt ending fitting after abrupt ending Figure 25. Linear Regression models fitting for the significant anomaly-related patterns 101 6.4.2 Continuous Probability Distributions Models In this section, we use continuous probability distributions models (namely the Exponential, Gamma, and Gaussian distributions) for capturing overall insights of the abrupt ending occurrences of each anomaly-related pattern given aggregate 802.11 total network usage, similar to section 5.4.3. Fitting results for these models on each anomaly-related pattern are presented in table 20. Results indicate Gamma and Gaussian models achieve slightly better fittings in terms of log-likelihoods over the exponential model, although the small gain attained by these models comes at the expense of the increase in complexity, in terms of number of parameters of the models. This claim is further justified by the AIC results, where exponential model appear to have slightly better results in terms of AIC values for most patterns. Given these very close results (LL and AIC values) by the virtue of simplicity of the model, simple exponential distribution is favored for modeling all anomaly-related patterns investigated in this chapter. Exponential Model Gamma Model Gaussian Model Anomaly-Related Pattern λ LL AIC α Β LL AIC μ σ LL AIC Across AP Vicinity Interference 0.171 -66.422 134.843 6.03 1.029 -53.532 111.065 5.857 2.321 -54.271 112.542 AP Persistence Interference 0.036 -73.533 149.066 2.11 0.076 -71.292 146.584 27.812 20.217 -75.233 154.466 AP Overload 0.643 -17.284 36.569 6.268 4.035 -10.635 25.270 1.553 0.679 -12.385 28.770 AP Halt/Crash 0.714 -13.364 28.729 4.442 3.173 -9.304 22.608 1.4 0.8 -11.958 27.916 AP Interference 0.109 -264.121 530.241 2.071 0.225 -253.776 511.553 9.216 7.055 -276.561 557.123 User Authentication Failure 0.932 -18.861 39.723 20.145 18.779 -13.012 29.77 1.4 0.8 -15.747 35.493 Intermittent Connectivity (Before) 0.0182 -611.999 1225.99 0.729 0.0133 -607.453 1218.91 54.821 100.99 -608.96 1221.92 Intermittent Connectivity (After) 0.016 -605.933 1213.87 0.738 0.012 -601.91 1207.82 63.32 110.94 -603.256 1210.51 Table 20. Model Parameters, LL, and AIC values for each statistical model on each anomaly-related pattern 6.4.3 Summary In this section, we examined the existence of significant statistical relationship between anomaly-related patterns occurrences and 802.11 aggregate usage. We find the relationship to be statistically significant for all anomaly-related patterns examined, except for AP halt/crash patterns and user authentication failure patterns. In addition, we proposed a family of continuous probability distributions e.g. Exponential, Gamma, and Gaussian models to capture underlying relationship between anomaly-related patterns occurrences and aggregate total 802.11 network usage. Despite its simplicity, the Exponential distribution model proved to be sufficient for capturing the overall relationships between variables for all the anomaly-related patterns investigated in this chapter. However, Gamma and Gaussian models achieved very close results to exponential model (see LL and AIC results in table 20), but complexity in terms of number of parameters counted against them. 102 6.5 Anomaly-Related Pattern Detection: Experimental Evaluation 6.5.1 Using Data sets from different Hotspots We applied our offline algorithm of section 6.2 (figure 23) using a more recent FEUP trace data set, i.e. 395 consecutive days between 1st May 2010 and 31st May 2011. We suppose the 802.11 infrastructure was more mature in its usage considering the trend stipulated in Table 11. The network was covered by total of 244 APs. During this period we observe more usage on the 802.11 infrastructure (total number of sessions established 4,303,517 i.e. about 46% increase per year), a larger number of users (24,807 i.e. about 37% increase per year), and 14,784 of the abrupt endings i.e. 57% increase per year. Using our proposed algorithm we detected 1201 across AP vicinity interference patterns, 657 patterns of AP persistence interference, 586 patterns of AP overload, and 43 patterns of AP halt/crash. In addition, we detected 452 cases of authentication failure patterns. We also applied our algorithm to a data set from another university, i.e. University of Minho (UMinho). This data was obtained in the context of FCT project SUM. Our aim is to cross check the existence of abrupt endings and their associated anomalyrelated patterns in other 802.11 deployments. We analyzed one month data set from one academic semester (01-30 June 2011). The network had 971 APs and 8,055 users. The total number of sessions established by these users in one month is 1,240,594. We detected 217 AP abrupt ending events, 94 patterns of AP vicinity interferences, 12 patterns of AP persistence interference, 31 patterns of AP overload, 3 patterns of AP halt/crash, and 37 cases of authentication failure patterns. Furthermore, we applied our algorithm to another 802.11 hotspot at INESC TEC with 75 APs, 464 users, and a total number of sessions established in one month of 11,480. From these figures (if compared to the other two 802.11 deployments) we could understand the network is relatively small and not heavily utilized. We did not detect any AP abrupt ending of connections event during the studied one month trace period. This further confirms our intuition about the correlations that exist between abrupt endings and 802.11 network usage, as described in chapter 5: the higher 802.11 infrastructure is utilized in term of network usage, the higher the possibility of abrupt endings and their respective patterns and vice versa. 6.5.2 DBSCAN Clustering Results We evaluate pattern A (across AP vicinity interference) results of our anomaly detection algorithm of section 6.2, using density based spatial clustering algorithm (DBSCAN) [188]. We take timestamps corresponding to each AP abrupt ending event occurrence as an input to the DBSCAN algorithm. We set minimum number of points in a neighborhood of each point (MinPts) to 2, aiming to obtain clusters with the minimum of 2 elements. In this way, we can depict clusters whereby at least two APs were involved in across AP vicinity interference. Consequently, we can establish the minimum number for any vicinity segment detection. We vary the maximum radius of the neighborhood reachability distance (i.e. Eps) between elements in the same way as 103 in the detection of across AP vicinity interference patterns (cf. figure 24). The number of clusters and the number of clustered elements for each Eps, as well as the difference in number of clusters and clustered elements between consecutive Eps are depicted by figure 26. (a) Different Eps settings for DBSCAN vs. Counts: 1) total number of clusters, 2) total number of elements within clusters, 3) difference in number of clusters, and 4) difference in number of elements within clusters at consecutive intervals (b) Histogram of the clustered segment lengths Figure 26. DBSCAN clustering results of the abrupt ending data Figure 26(a) shows that as the Eps in DBSCAN algorithm increases, the number of depicted clusters increase with the significant increase noted at 60 seconds (line #1). Thereafter, the number of depicted clusters did not show any significant increase. These observations match the insights of figure 24, confirming 60 seconds as an optimal threshold for across AP vicinity interference pattern detection. Another argument supporting this threshold is the histogram of the cluster’s segment length of the DBSCAN algorithm figure 26(b), which indicates significant change in clusters segment lengths after 60 seconds. 104 In this section, we presented additional evaluation of pattern A (across AP vicinity interference) owing to its significance. Remember these patterns occur when APs in an 802.11 infrastructure encounters abrupt endings in succession during short interval of time (i.e. 60 sec). Thus if not controlled, large part of an 802.11 network can suffer from this cascading effect, causing connectivity problems to 802.11 users. Similar to what is reported in the previous work [84], where an entire 802.11 network collapsed due to heavy control, management, and data packet processing required by the arrival of high number of user to APs, each time APs started accepting connections after recovering from a halt condition. 6.6 Online Detection of Anomaly-Related Patterns 6.6.1 Methodology In section 6.3 we used an offline detection approach with relational databases and standard query language (SQL) in depicting the anomaly-related patterns of 802.11 AP usage investigated in this chapter. In this section, we propose to use the Esper engine [189] for complex event processing and analysis to implement online detection of these patterns. The Esper engine works like a relational database turned upside-down, i.e. instead of storing the data and running queries, the Esper engine allows applications to store queries and run the data through the queries. Response is quick when conditions that match queries occur [189]. Event streams (infinite set of events which are further correlated) considered over a time window period can be highly meaningful and reacting to them quickly is critical for effective management decisions [190]. We take advantage of the continuous execution model provided by the Esper engine to implement online event driven detection and characterization of abrupt endings and their respective anomaly-related patterns. The architecture of our online detection tool is shown in figure 27. We use timestamp and AP IP address associated to each user session ending (i.e. RADIUS log event STOP) to form an input data stream of session endings. From this input event stream, we automatically detect abrupt ending events using the definition provided in chapter 4 (i.e. timestamp where three or more session endings are observed in the same AP) and consequently generate another data stream of abrupt ending events. We use relationship between these two event data streams observed in specified window periods to characterize abrupt endings into appropriate pattern of AP-related anomaly. We assess the impact of using different time window settings (sliding window) for each pattern against detection capability. Our overall goal is to implement a system that can automatically detect all APrelated anomalous patterns investigated in this chapter as quick as possible, and to promptly raise alarms. Alarms may increase situational awareness to network administrators who can check 802.11 network and act when needed. In this manner, 802.11 administrators may be relieved from the burden of continuous monitoring 802.11 large-scale infrastructures. 105 Figure 27. Online system’s architecture for anomaly-related patterns detection Anomaly-Related Pattern Definition: The threshold settings we use here for some patterns detection are slightly different from those used in section 6.3. This is because with our online implementation we aim to reduce detection time yet achieving almost comparable results to the offline detection, which is our baseline for comparison. We employ simple rules for online detection of each anomaly-related pattern on the same data set used in section 6.3. For example: 1) Pattern A: interference across AP vicinity is detected when abrupt ending events occur in a 60 seconds time window between several APs. This threshold is the same for offline detection, because by reducing it there is the danger of splitting one vicinity segment into many segments, on the other hand, further reduction may possibly fade out this pattern completely; 2) Pattern B: AP Persistent interference is detected when four or more abrupt ending events occur in one AP within a 12 hours’ time window (our offline detection use 24 hours detection period); 3) Pattern C: AP overload is detected when continued sessions are observed within 1 minute window after abrupt ending event (offline detection use 15 minutes); 4) Pattern D: AP halt/crash is detected when no user session is observed within 5 minutes window after abrupt ending event (offline detection uses 30 minutes); 5) Pattern E: AP Interference is detected if an abrupt ending event is not associated to any of the above mentioned patterns. We did not investigate user-related patterns F and G, because event streams based on RADIUS log event STOP alone are not enough for characterizing these patterns. These patterns require user information (e.g. User ID) beside each log event STOP, and incorporating it (i.e. user ID event stream) may increase complexity of the online implementation, we leave out this for future work. 6.6.2 Interference Across AP Vicinity Patterns We test different thresholds of time intervals using sliding window approach while counting the number of abrupt ending events belonging to this particular pattern at various window sizes. Figure 28 shows that as the time window increases the total number of AP vicinity segments and total number of interfering APs increases, with 106 insignificant change noted after 60 seconds; similar to the insights of figure 24. We therefore keep 60 seconds window size as an optimal detection threshold for this pattern, in the same way as in the offline detection of section 6.3. Figure 28. Different time windows tested vs. counts: (1) total number of vicinity segments detected, (2) total number of interfering APs within vicinity segments, (3) difference in number of segments from previous time window, and (4) difference in number of interfering APs between consecutive segments We performed sensitivity analysis on the results obtained from online detection of these patterns (figure 28) against our results of offline detection (figure 24). Sensitivity analysis in this case has maximum 100%, since similar results were obtained. This means our online detector has ability to produce 100% matching results to offline detection using the same 60 seconds threshold. We did not attempt to reduce this threshold further, because further reduction is likely to split abrupt endings that belong to the same vicinity segment into various distinct vicinity segments; while further reduction is likely to destroy vicinity segments completely, as the majority of abrupt endings would appear individually without forming any pattern. 6.6.3 AP Persistent Intereference Patterns We count the number of abrupt ending events per AP greater or equal to four (similar to offline detection in section 6.3.2) exploiting both sliding and batched windowing approaches at distinct time window intervals. Sliding window’s approach means each latest abrupt ending event is checked against the previous occurrence of the abrupt ending event for the same AP within the duration of the chosen window size e.g. in our case 12 hours. While batched window uses fixed intervals of window size e.g. 12 hours, meaning counts of abrupt ending events for all APs is executed at the end of each window size. Batched window is very similar in concept to our offline detection. Figure 29 depicts detection results for different time windows tested using both approaches. 107 (a) Time windows tested for online detection of AP persistence interference (b) Hour of the day where 4 abrupt ending events per AP occurred Figure 29. Results for online detection of AP persistence interference patterns Figure 29(a) shows the number of instances of AP persistence interferences detected increase with the increase in window size and the detected instances becomes insignificant at around 10 hours until 18 hours. This indicates the chosen 12 hours can be suitable window size for detecting AP persistent interference using both approaches sliding or batched windows. However, batched window consumes more computational and memory resources than sliding window. In batched window events are collected in batches and processed in batches [191], while in sliding window only recent elements of a stream are more important. This fact justifies the use of sliding window over batched window for online detection of these patterns. Figure 29(b) depicts the hour of the day where APs normally reaches four abrupt ending event counts. Remember, occurrences of four abrupt endings to an AP in a given window period is what defines AP persistent of interference patterns (section 6.2). In addition, figure 29(b) shows that the number of 4 counts for AP abrupt ending events follows hotspot usage pattern behavior, with high counts noted between 10:00 and 20:00 hours. These insights may help 802.11 administrators to determine suitable window sizes for both sliding window detection 114 References [1] Gast, M. (2005). 802.11 wireless networks: the definitive guide. O'Reilly Media, Inc. [2] Stuber, G. L. (1997). Principles of Mobile Communications. Kluwer, Academic Press. [3] Bianchi, G., Fratta, L., & Oliveri, M. (1996). Performance evaluation and enhancement of the CSMA/CA MAC protocol for 802.11 wireless LANs. In Personal, Indoor and Mobile Radio Communications, PIMRC'96., Seventh IEEE International Symposium on (Vol. 2, pp. 392-396). IEEE. [4] Gummalla, A. C. V., & Limb, J. O. (2000). Wireless medium access control protocols. Communications Surveys & Tutorials, IEEE, 3(2), 2-15. [5] Xu, S., & Saadawi, T. (2002). Revealing the problems with 802.11 medium access control protocol in multi-hop wireless ad hoc networks. Computer Networks, 38(4), 531-548. [6] Bianchi, G. (2000). Performance analysis of the IEEE 802.11 distributed coordination function. Selected Areas in Communications, IEEE Journal on, 18(3), 535-547. [7] Bing, B. (1999). Measured performance of the IEEE 802.11 wireless LAN. In Local Computer Networks, LCN'99. Conference on (pp. 34-42). IEEE. [8] T. D., Niemi, M., & Saarinen, J. (2002). Trends in personal wireless data communications. Computer Communications, 25(1), 84-99. [9] Stallings, W. (2004). IEEE 8O2. 11: wireless LANs from a to n. IT professional, 6(5), 32-37. [10] Nguyen, D. N., & Krunz, M. (2013). Cooperative MIMO in wireless networks: recent developments and challenges. Network, IEEE, 27(4). [11] Pathak, P. H., & Dutta, R. (2011). A survey of network design problems and joint design approaches in wireless mesh networks. Communications Surveys & Tutorials, IEEE, 13(3), 396-428. [12] Patras, P., Qi, H., & Malone, D. (2014). Mitigating collisions through power-hopping to improve 802.11 performance. Pervasive and Mobile Computing, 11, 41-55. [13] Xu, F., Zhu, X., Tan, C., Li, Q., Yan, G., & Wu, J. (2013). Smartassoc: Decentralized access point selection algorithm to improve throughput. Parallel and Distributed Systems, IEEE Transactions on, 24 (12), 2482 – 2491. [14] Dargie, W., & Schill, A. (2011). Stability and performance analysis of randomly deployed wireless networks. Journal of Computer and System Sciences, 77(5), 852-860. [15] Leinwand, A., & Conroy, K. F. (1996). Network management: a practical perspective. Unix and Open Systems Series. Reading, MA: Addison-Wesley, 2nd ed. [16] Klerer, S. M. (1988). The OSI management architecture: an overview. Network, IEEE, 2(2), 20-29. [17] Simoneau, P. (1999). SNMP network management. McGraw-Hill, Inc.. [18] Lee, J. S., & Hsu, P. L. (2004). Design and implementation of the SNMP agents for remote monitoring and control via UML and Petri nets. Control Systems Technology, IEEE Transactions on, 12(2), 293-302. [19] Caruso, R. E. (1990). Network management: a tutorial overview. Communications Magazine, IEEE, 28(3), 20-25. 115 [20] Hassan, R., Razali, R., Mohseni, S., Mohamad, O., & Ismail, Z. (2009). Architecture of Network Management Tools for Heterogeneous System. International Journal of Computer Science and Information Security, (IJCSIS), Vol. 6, No. 3. [21] Freeman, B. D. (2010). Network Configuration Management. In Guide to Reliable Internet Services and Applications (pp. 255-275). Springer London. [22] Goyal, P., Mikkilineni, R., & Ganti, M. (2009). FCAPS in the business services fabric model. In Enabling Technologies: Infrastructures for Collaborative Enterprises, WETICE'09. 18th IEEE International Workshops on (pp. 45-51). IEEE. [23] Lu, X., Zhou, W., & Song, J. (2010). Key issues of future network management. In Computer Application and System Modeling (ICCASM), International Conference on (Vol. 11, pp. V11-649). IEEE. [24] Said, S. B. H., Guillouard, K., & Bonnin, J. M. (2013). A Comparative Study on Security Implementation in EPS/LTE and WLAN/802.11. In Wireless Networks and Security (pp. 457-489). Springer Berlin Heidelberg. [25] Pras, A., Drevers, T., van de Meent, R., & Quartel, D. (2004). Comparing the performance of SNMP and web services-based management. Network and Service Management, IEEE Transactions on, 1(2), 72-82. [26] Pan, H., Li, T., & Shi, Y. (2014). Computer Network Monitoring System Based on Information Processing Technology. In Proceedings of the 9th International Symposium on Linear Drives for Industry Applications, Volume 1 (pp. 721-728). Springer Berlin Heidelberg. [27] Surputheen, M. M., Ravi, G., & Srinivasan, R. (2012). SNMP Based Network Optimization Technique Using Genetic Algorithms. International Journal of Computer Science Issues (IJCSI), 9(2). [28] Pavlou, G., Flegkas, P., Gouveris, S., & Liotta, A. (2004). On management technologies and the potential of web services. Communications Magazine, IEEE, 42(7), 58-66. [29] Shang-Fu, G., & Xiao-Li, Y. (2012). Study and Design of Integrated Transmission Network Management System Based on CORBA and Web. In Industrial Control and Electronics Engineering (ICICEE), 2012 International Conference on (pp. 600-603). IEEE. [30] Gupta, A. (2006). Network management: Current trends and future perspectives. Journal of Network and Systems Management, 14(4), 483-491. [31] Satoh, I. (2002). A framework for building reusable mobile agents for network management. In Network Operations and Management Symposium, 2002. NOMS 2002. 2002 IEEE/IFIP (pp. 51-64). IEEE. [32] Yang, S. Y., & Chang, Y. Y. (2011). An active and intelligent network management system with ontology-based and multi-agent techniques. Expert Systems with Applications, 38(8), 10320-10342. [33] Verma, D. C. (2002). Simplifying network administration using policy-based management. Network, IEEE, 16(2), 20-26. [34] Samaan, N., & Karmouch, A. (2009). Towards autonomic network management: an analysis of current and future research directions. Communications Surveys & Tutorials, IEEE, 11(3), 22-36. [35] RFC 2865 (RADIUS) protocol, http://tools.ietf.org/html/rfc2865 last accessed November 2014. 116 [36] RFC 2866 RADIUS acccounting, http://tools.ietf.org/html/rfc2866 last accessed November 2014. [37] CRAWDAD: A Community Resource for Archiving Wireless Data At Dartmouth. http://crawdad.cs.dartmouth.edu/index.php last accessed November 2014. [38] MobiLib: Community-wide Library of Mobility and Wireless Networks Measurements. http://nile.usc.edu/MobiLib last accessed November 2014. [39] Allahdadi, A., Morla, R., Aguiar, A., & Cardoso, J. S. (2013). Predicting short 802.11 sessions from RADIUS usage data. In Local Computer Networks Workshops (LCN Workshops), IEEE 38th Conference on (pp. 1-8). IEEE. [40] Baras, K., & Moreira, A. (2010). Anomaly detection in university campus WiFi zones. In Pervasive Computing and Communications Workshops (PERCOM Workshops), 8th IEEE International Conference on (pp. 202-207). IEEE. [41] Calabrese, F., Diao, M., Di Lorenzo, G., Ferreira Jr, J., & Ratti, C. (2013). Understanding individual mobility patterns from urban sensing data: A mobile phone trace example. Transportation research part C: emerging technologies, 26, 301-313. [42] H Zang, H., & Bolot, J. C. (2007). Mining Call Data to Increase the Robustness of Cellular Networks to Signaling DoS Attacks. In Proceedings of the 13th annual ACM international conference on Mobile computing and networking (pp. 123-134). ACM. [43] Lane, N. D., Miluzzo, E., Lu, H., Peebles, D., Choudhury, T., & Campbell, A. T. (2010). A survey of mobile phone sensing. Communications Magazine, IEEE, 48(9), 140-150. [44] Zhu, Y., Liu, X., & Wang, Y. (2013). Pervasive Urban Sensing with Large-Scale Mobile Probe Vehicles, International Journal of Distributed Sensor Networks 762503, [45] González, M. C., Hidalgo, C. A., & Barabási, A. L. (2009). Understanding individual human mobility patterns. Nature, 458(7235), 238-238. [46] Brockmann, D., & Theis, F. (2008). Money circulation, trackable items, and the emergence of universal human mobility patterns. Pervasive Computing, IEEE, 7(4), 2835. [47] Massa, D., & Morla, R. (2013). Modeling 802.11 AP usage through daily keep-alive event counts. Wireless networks, 19(5), 1005-1022. [48] Massa, D., & Morla, R. (2010). Modeling 802.11 AP Usage through Daily Keep-Alive Event Counts. In 16th International Conference on Network-Based Information Systems (pp. 195-200). IEEE. [49] Massa, D., & Morla, R. (2013). Abrupt ending of 802.11 ap connections. In Computers and Communications (ISCC), IEEE Symposium on (pp. 000348-000353). IEEE. [50] Amatriain, X., Jaimes, A., Oliver, N., & Pujol, J. M. (2011). Data mining methods for recommender systems. In Recommender Systems Handbook (pp. 39-71). [51] Tang, D., & Baker, M. (2000). Analysis of a local-area wireless network. In Proceedings of the 6th annual international conference on Mobile computing and networking (pp. 1-10). ACM. [52] Tang, D., & Baker, M. (2002). Analysis of a metropolitan-area wireless network. Wireless Networks, 8(2-3), 107-120. [53] Balachandran, A., Voelker, G. M., Bahl, P., & Rangan, P. V. (2002). Characterizing user behavior and network performance in a public wireless LAN. In ACM SIGMETRICS Performance Evaluation Review (Vol. 30, No. 1, pp. 195-205). ACM. 117 [54] Kotz, D., & Essien, K. (2002). Analysis of a Campus-wide Wireless Network. In In Proceedings of ACM Mobicom. ACM. [55] Henderson, T., Kotz, D., & Abyzov, I. (2004). The changing usage of a mature campuswide wireless network. In Proceedings of the 10th annual international conference on Mobile computing and networking (pp. 187-201). ACM. [56] Balazinska, M., & Castro, P. (2003). Characterizing mobility and network usage in a corporate wireless local-area network. In Proceedings of the 1st international conference on Mobile systems, applications and services (pp. 303-316). ACM. [57] Kim, M., & Kotz, D. (2007). Periodic properties of user mobility and access-point popularity. Personal and Ubiquitous Computing, 11(6), 465-479. [58] Kim, M., & Kotz, D. (2005). Modeling users' mobility among WiFi access points. In Papers presented at the 2005 workshop on Wireless traffic measurements and modeling (pp. 19-24). USENIX Association. [59] Boc, M., Fladenmuller, A., & De Amorim, M. D. (2007). Towards self-characterization of user mobility patterns. In Mobile and Wireless Communications Summit, 2007. 16th IST (pp. 1-5). IEEE. [60] Kim, M., Kotz, D., & Kim, S. (2006). Extracting a Mobility Model from Real User Traces. In INFOCOM (Vol. 6, pp. 1-13). IEEE. [61] McNett, M., & Voelker, G. M. (2005). Access and mobility of wireless PDA users. ACM SIGMOBILE Mobile Computing and Communications Review, 9(2), 40-55. [62] Hsu, W. J., & Helmy, A. (2006). On modeling user associations in wireless LAN traces on university campuses. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 4th International Symposium on (pp. 1-9). IEEE. [63] Chen, Y. C., Kurose, J., & Towsley, D. (2012, March). A mixed queueing network model of mobility in a campus wireless network. In INFOCOM, Proceedings (pp. 26562660). IEEE. [64] Ghosh, J., Beal, M. J., Ngo, H. Q., & Qiao, C. (2006). On profiling mobility and predicting locations of wireless users. In Proceedings of the 2nd international workshop on Multi-hop ad hoc networks: from theory to reality (pp. 55-62). ACM. [65] Song, L., Kotz, D., Jain, R., & He, X. (2006). Evaluating next-cell predictors with extensive Wi-Fi mobility data. Mobile Computing, IEEE Transactions on, 5(12), 16331649. [66] Kim, J., & Helmy, A. (2011). The evolution of wlan user mobility and its effect on prediction. In Wireless Communications and Mobile Computing Conference (IWCMC), 7th International (pp. 226-231). IEEE. [67] Lee, J. K., & Hou, J. C. (2006). Modeling steady-state and transient behaviors of user mobility: formulation, analysis, and application. In Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing (pp. 85-96). ACM. [68] Chon, Y., Shin, H., Talipov, E., & Cha, H. (2012). Evaluating mobility models for temporal prediction with high-granularity mobility data. In Pervasive computing and communications (percom), IEEE international conference on (pp. 206-212). IEEE. 118 [69] Gao, W., & Cao, G. (2010). Fine-grained mobility characterization: steady and transient state behaviors. In Proceedings of the eleventh ACM international symposium on Mobile ad hoc networking and computing (pp. 61-70). ACM. [70] Abu-Ghazaleh, H., & Alfa, A. S. (2010). Application of mobility prediction in wireless networks using markov renewal theory. Vehicular Technology, IEEE Transactions on, 59(2), 788-802. [71] Hong, J., & Kim, H. (2011). An empirical framework for user mobility models: Refining and modeling user registration patterns. Journal of Computer and System Sciences, 77(5), 869-883. [72] Hong, J., & Kim, H. (2013). A Dual Mobility Model with User Profiling: Decoupling User Mobile Patterns from Association Patterns. The Computer Journal, 56(6), 771784. [73] Zhao, M., & Wang, W. (2009). A unified mobility model for analysis and simulation of mobile wireless networks. Wireless Networks, 15(3), 365-389. [74] Resta, G., & Santi, P. (2008). WiQoSM: An integrated QoS-aware mobility and user behavior model for wireless data networks. IEEE Transactions on Networking Mobile Computing, 7(2), 187–198. [75] Lee, K., Hong, S., Kim, S. J., Rhee, I., & Chong, S. (2009). Slaw: A new mobility model for human walks. In INFOCOM, (pp. 855-863). IEEE. [76] Rhee, I., Shin, M., Hong, S., Lee, K., Kim, S. J., & Chong, S. (2011). On the levy-walk nature of human mobility. IEEE/ACM Transactions on Networking (TON), 19(3), 630643. [77] Kosta, S., Mei, A., & Stefa, J. (2010). Small world in motion (SWIM): Modeling communities in ad-hoc mobile networking. In Sensor Mesh and Ad Hoc Communications and Networks (SECON), 27th Annual IEEE Communications Society Conference on (pp. 1-9). IEEE. [78] Meneses, F., & Moreira, A. (2012). Large scale movement analysis from WiFi based location data. In Indoor Positioning and Indoor Navigation (IPIN), International Conference on. IEEE. [79] Balasubramanian, A., Mahajan, R., Venkataramani, A., Levine, B. N., & Zahorjan, J. (2008). Interactive wifi connectivity for moving vehicles. ACM SIGCOMM Computer Communication Review, 38(4), 427-438. [80] Mahajan, R., Zahorjan, J., & Zill, B. (2007). Understanding WiFi-based connectivity from moving vehicles. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement (pp. 321-326). ACM. [81] Hsu, W.-j., & Helmy, A. (2010). “On nodal encounter patterns in wireless LAN traces”, IEEE Transaction on Mobile Computing, 9(11), 1563–1577. [82] Hsu, W. J., Dutta, D., & Helmy, A. (2007). Mining behavioral groups in large wireless LANs. In Proceedings of the 13th annual ACM international conference on Mobile computing and networking (pp. 338-341). ACM. [83] Hsu, W. J., Dutta, D., & Helmy, A. (2012). Structural analysis of user association patterns in university campus wireless lans. Mobile Computing, IEEE Transactions on, 11(11), 1734-1748. 119 [84] Hsu, W. J., Spyropoulos, T., Psounis, K., & Helmy, A. (2007). Modeling time-variant user mobility in wireless mobile networks. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE (pp. 758-766). IEEE. [85] Hsu, W. J., Spyropoulos, T., Psounis, K., & Helmy, A. (2009). Modeling spatial and temporal dependencies of user mobility in wireless mobile networks. IEEE/ACM Transactions on Networking (TON), 17(5), 1564-1577. [86] Chen, Y. C., Rosensweig, E., Kurose, J., & Towsley, D. (2010). Group detection in mobility traces. In Proceedings of the 6th international wireless communications and mobile computing conference (pp. 875-879). ACM. [87] Karagiannis, T., Le Boudec, J. Y., & Vojnovic, M. (2010). Power law and exponential decay of intercontact times between mobile devices. Mobile Computing, IEEE Transactions on, 9(10), 1377-1390. [88] Williams, M. J., Whitaker, R. M., & Allen, S. M. (2012). Measuring individual regularity in human visiting patterns. In International Confernece on Social Computing (SocialCom) (pp. 117-122). IEEE. [89] Papadopouli, M., Shen, H., & Spanakis, M. (2005). Modeling client arrivals at access points in wireless campus-wide networks. In 14th IEEE Workshop on Local and Metropolitan Area Networks (pp. 18-21). IEEE. [90] Ghosh, A., Jana, R., Ramaswami, V., Rowland, J., & Shankaranarayanan, N. K. (2011). Modeling and characterization of large-scale Wi-Fi traffic in public hot-spots. In INFOCOM, Proceedings (pp. 2921-2929). IEEE. [91] Jain, R., Lelescu, D., & Balakrishnan, M. (2007). Model T: a model for user registration patterns based on campus WLAN data. Wireless Networks, 13(6), 711-735. [92] Chinchilla, F., Lindsey, M., & Papadopouli, M. (2004). Analysis of wireless information locality and association patterns in a campus. In INFOCOM 2004. Twentythird AnnualJoint Conference of the IEEE Computer and Communications Societies (Vol. 2, pp. 906-917). IEEE. [93] Lelescu, D., Kozat, U. C., Jain, R., & Balakrishnan, M. (2006). Model T++: an empirical joint space-time registration model. In Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing (pp. 61-72). ACM. [94] Zola, E., & Barcelo-Arroyo, F. (2012). Distribution of the frequency of connections in academic WLAN networks. In ICNS 2012, The Eighth International Conference on Networking and Services (pp. 69-74). [95] Zola, E., & Barcelo-Arroyo, F. (2013). Characterizing User Behavior in a European Academic WiFi Network. International Journal of Handheld Computing Research (IJHCR), 4(2), 55-68. [96] Papadopouli, M., Shen, H., & Spanakis, M. (2005). Characterizing the duration and association patterns of wireless access in a campus. In Wireless Conference 2005-Next Generation Wireless and Mobile Communications and Services (European Wireless), 11th European (pp. 1-7). VDE. [97] Mahanti, A., Williamson, C., & Arlitt, M. (2007). Remote analysis of a distributed WLAN using passive wireless-side measurement. Performance Evaluation, 64(9), 909932. 120 [98] Phillips, C., & Singh, S. (2008). An empirical activity model for wlan users. In INFOCOM, 08. The 27th Conference on Computer Communications. IEEE. [99] Zola, E., & Barcelo-Arroyo, F. (2009). Impact of mobility models on the cell residence time in WLAN networks. In Sarnoff Symposium, SARNOFF'09 (pp. 1-5). IEEE. [100] Manweiler, J., Santhapuri, N., Choudhury, R. R., & Nelakuditi, S. (2013). Predicting length of stay at WiFi hotspots. In INFOCOM, 13 Proceedings (pp. 3102-3110). IEEE. [101] Papadopouli, M., Shen, H., Raftopoulos, E., Ploumidis, M., & Hernandez-Campus, F. (2005). Short-term traffic forecasting in a campus-wide wireless network. In Personal, Indoor and Mobile Radio Communications, PIMRC, 05. 16th International Symposium on (Vol. 3, pp. 1446-1452). IEEE. [102] Tzagkarakis, G., Papadopouli, M., & Tsakalides, P. (2009). Trend forecasting based on Singular Spectrum Analysis of traffic workload in a large-scale wireless LAN. Performance Evaluation, 66(3), 173-190. [103] Kulkarni, P., Lewis, T., & Fan, Z. (2011). Simple traffic prediction mechanism and its applications in wireless networks. Wireless Personal Communications, 59(2), 261-274. [104] Hernandez-Campos, F., & Papadopouli, M. (2005). A comparative measurement study the workload of wireless access points in campus networks. In Personal, Indoor and Mobile Radio Communications, PIMRC, 05. 16th International Symposium on (Vol. 3, pp. 1776-1780). IEEE. [105] Hernández-Campos, F., Karaliopoulos, M., Papadopouli, M., & Shen, H. (2006). Spatio-temporal modeling of traffic workload in a campus WLAN. In Proceedings of the 2nd annual international workshop on Wireless internet (p. 1). ACM. [106] Karaliopoulos, M., Papadopouli, M., Raftopoulos, E., & Shen, H. (2007). On scalable measurement-driven modeling of traffic demand in large WLANs. In Local & Metropolitan Area Networks, LANMAN, 07. 15th Workshop on (pp. 102-110). IEEE. [107] Meng, X. G., Wong, S. H., Yuan, Y., & Lu, S. (2004). Characterizing flows in large wireless data networks. In Proceedings of the 10th annual international conference on Mobile computing and networking (pp. 174-186). ACM. [108] Chlebus, E., & Divgi, G. (2007). The Pareto or truncated Pareto distribution? Measurement-based modeling of session traffic for Wi-Fi wireless Internet access. In Wireless Communications and Networking Conference, WCNC, 07 (pp. 3625-3630). IEEE. [109] Mulhanga, M. M., Lima, S. R., & Carvalho, P. (2011). Characterising Eduroam WLANs Usage Trends: A Case Study. In Modeling, Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS), 19th International Symposium on (pp. 447-449). IEEE. [110] Afanasyev, M., Chen, T., Voelker, G. M., & Snoeren, A. C. (2008). Analysis of a mixed-use urban wifi network: when metropolitan becomes neapolitan. In Proceedings of the 8th ACM SIGCOMM conference on Internet measurement (pp. 85-98). ACM. [111] Afanasyev, M., Chen, T., Voelker, G. M., & Snoeren, A. C. (2010). Usage patterns in an urban wifi network. Networking, IEEE/ACM Transactions on, 18(5), 1359-1372. [112] Blinn, D. P., Henderson, T., & Kotz, D. (2005). Analysis of a Wi-Fi hotspot network. In Papers presented at the workshop on Wireless traffic measurements and modeling (pp. 1-6). USENIX Association. 121 [113] Divgi, G., & Chlebus, E. (2013). Characterization of user activity and traffic in a commercial nationwide Wi-Fi hotspot network: global and individual metrics. Wireless networks, 19(7), 1783-1805. [114] Ojala, T., Hakanen, T., Makinen, T., & Rivinoja, V. (2005). Usage analysis of a large public wireless LAN. In Wireless Networks, Communications and Mobile Computing, International Conference on (Vol. 1, pp. 661-667). IEEE. [115] Wamser, F., Pries, R., Staehle, D., Heck, K., & Tran-Gia, P. (2011). Traffic characterization of a residential wireless Internet access. Telecommunication Systems, 48(1-2), 5-17. [116] Balachandran, A., Voelker, G. M., & Bahl, P. (2005). Wireless hotspots: current challenges and future directions. Mobile Networks and Applications, 10(3), 265-274. [117] Jardosh, A. P., Ramachandran, K. N., Almeroth, K. C., & Belding-Royer, E. M. (2005). Understanding link-layer behavior in highly congested IEEE 802.11 b wireless networks. In Proceedings of the ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis (pp. 11-16). ACM. [118] Jardosh, A. P., Ramachandran, K. N., Almeroth, K. C., & Belding-Royer, E. M. (2005). Understanding congestion in IEEE 802.11 b wireless networks. In Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement (pp. 25-25). USENIX Association. [119] Raghavendra, R., Belding, E. M., Papagiannaki, K., & Almeroth, K. C. (2010). Unwanted link layer traffic in large IEEE 802.11 wireless networks. IEEE Transactions on Mobile Computing, 9(9), 1212-1225. [120] Acharya, P. A. K., Sharma, A., Belding, E. M., Almeroth, K. C., & Papagiannaki, K. (2008). Congestion-aware rate adaptation in wireless networks: A measurement-driven approach. In Sensor, Mesh and Ad Hoc Communications and Networks, SECON'08. 5th Annual IEEE Communications Society Conference on (pp. 1-9). IEEE. [121] Velayos, H., Más, I., & Karlsson, G. (2006). Overload protection for ieee 802.11 cells. In Quality of Service, IWQoS 06. 14th IEEE International Workshop on (pp. 149-158). IEEE. [122] Abusubaih, M., Wiethoelter, S., Gross, J., & Wolisz, A. (2008). A new access point selection policy for multi-rate IEEE 802.11 WLANs. International Journal of Parallel, Emergent and Distributed Systems, 23(4), 291-307. [123] Jardosh, A. P., Mittal, K., Ramachandran, K. N., Belding, E. M., & Almeroth, K. C. (2006). IQU: practical queue-based user association management for WLANs. In Proceedings of the 12th annual international conference on Mobile computing and networking (pp. 158-169). ACM. [124] Velayos, H., Aleo, V., & Karlsson, G. (2004). Load balancing in overlapping wireless LAN cells. In International Conference on Communications (Vol. 7, pp. 3833-3836). IEEE. [125] Murty, R., Padhye, J., Chandra, R., Wolman, A., & Zill, B. (2008). Designing High Performance Enterprise Wi-Fi Networks. In NSDI (Vol. 8, pp. 73-88). [126] Nicholson, A. J., Chawathe, Y., Chen, M. Y., Noble, B. D., & Wetherall, D. (2006). Improved access point selection. In Proceedings of the 4th international conference on Mobile systems, applications and services (pp. 233-245). ACM. 122 [127] Bejerano, Y., & Han, S. J. (2009). Cell breathing techniques for load balancing in wireless LANs. Mobile Computing, IEEE Transactions on, 8(6), 735-749. [128] Mittal, K., Belding, E. M., & Suri, S. (2008). A game-theoretic analysis of wireless access point selection by mobile users. Computer Communications, 31(10), 2049-2062. [129] Pan, H. J., & Keshav, S. (2006). Detection and repair of faulty access points. In Wireless Communications and Networking Conference, WCNC 06. (Vol. 1, pp. 532538). IEEE. [130] de Deus, F. E., Puttini, R. S., Molinaro, L. F., Abdalla, H., Amvame-Nze, G., & Kabara, J. (2006). Fault tolerance in IEEE 802.11 WLANs. In Telecommunications Symposium, International (pp. 626-631). IEEE. [131] Adya, A., Bahl, P., Chandra, R., & Qiu, L. (2004). Architecture and techniques for diagnosing faults in IEEE 802.11 infrastructure networks. In Proceedings of the 10th annual international conference on Mobile computing and networking (pp. 30-44). ACM. [132] Elhadef, M., Boukerche, A., & Elkadiki, H. (2008). A distributed fault identification protocol for wireless and mobile ad hoc networks. Journal of Parallel and Distributed Computing, 68(3), 321-335. [133] Akella, A., Judd, G., Seshan, S., & Steenkiste, P. (2007). Self-management in chaotic wireless deployments. Wireless Networks, 13(6), 737-755. [134] Broustis, I., Papagiannaki, K., Krishnamurthy, S. V., Faloutsos, M., & Mhatre, V. P. (2010). Measurement-driven guidelines for 802.11 WLAN design. IEEE/ACM Transactions on Networking (TON), 18(3), 722-735. [135] Moriuchi, A., Murase, T., Oguchi, M., Baid, A., Sagari, S., Seskar, I., & Raychaudhuri, D. (2013). Measurement study of adjacent channel interference in mobile WLANs. In Communications Workshops (ICC), International Conference on (pp. 566-570). IEEE. [136] Gummadi, R., Wetherall, D., Greenstein, B., & Seshan, S. (2007). Understanding and mitigating the impact of RF interference on 802.11 networks. ACM SIGCOMM Computer Communication Review, 37(4), 385-396. [137] Shrivastava, V., Rayanchu, S. K., Banerjee, S., & Papagiannaki, K. (2011). PIE in the Sky: Online Passive Interference Estimation for Enterprise WLANs. In NSDI (Vol. 11, p. 20). [138] Lakshminarayanan, K., Seshan, S., & Steenkiste, P. (2011). Understanding 802.11 performance in heterogeneous environments. In Proceedings of the 2nd ACM SIGCOMM workshop on Home networks (pp. 43-48). ACM. [139] Cai, K., Blackstock, M., Feeley, M. J., & Krasic, C. (2009). Non-intrusive, dynamic interference detection for 802.11 networks. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (pp. 377-383). ACM. [140] Yang, J., Draper, S. C., & Nowak, R. (2012). Passive learning of the interference graph of a wireless network. In Information Theory Proceedings (ISIT), IEEE International Symposium on (pp. 2735-2740). IEEE. [141] Chang, H., Misra, V., & Rubenstein, D. (2006). A General Model and Analysis of Physical Layer Capture in 802.11 Networks. In INFOCOM. IEEE. [142] Qiu, L., Zhang, Y., Wang, F., Han, M. K., & Mahajan, R. (2007). A general model of wireless interference. In Proceedings of the 13th annual ACM international conference on Mobile computing and networking (pp. 171-182). ACM. 123 [143] Kashyap, A., Paul, U., & Das, S. R. (2010). Deconstructing interference relations in WiFi networks. In Sensor Mesh and Ad Hoc Communications and Networks (SECON), 7th Annual IEEE Communications Society Conference on (pp. 1-9). IEEE. [144] Paul, U., Kashyap, A., Maheshwari, R., & Das, S. R. (2013). Passive measurement of interference in WiFi networks with application in misbehavior detection. Mobile Computing, IEEE Transactions on, 12(3), 434-446. [145] Qu, G., & Nefcy, M. M. (2010). RAPiD: An indirect rogue access points detection system. In Performance Computing and Communications Conference (IPCCC), IEEE 29th International (pp. 9-16). IEEE. [146] Kao, K. F., Liao, I., & Li, Y. C. (2009). Detecting rogue access points using client-side bottleneck bandwidth analysis. Computers and Security, 28(3), 144-152. [147] Nikbakhsh, S., Manaf, A. B. A., Zamani, M., & Janbeglou, M. (2012). A novel approach for rogue access point detection on the client-side. In Advanced Information Networking and Applications Workshops (WAINA), 26th International Conference on (pp. 684-687). IEEE. [148] Ma, L., Teymorian, A. Y., & Cheng, X. (2008). A hybrid rogue access point protection framework for commodity Wi-Fi networks. In INFOCOM 2008. The 27th Conference on Computer Communications. IEEE. [149] Watkins, L., Beyah, R., & Corbett, C. (2007). A passive approach to rogue access point detection. In Global Telecommunications Conference, GLOBECOM'07. (pp. 355-360). IEEE. [150] Venkataraman, A., & Beyah, R. (2009). Rogue access point detection using innate characteristics of the 802.11 mac. In Security and Privacy in Communication Networks (pp. 394-416). Springer Berlin Heidelberg. [151] Han, H., Sheng, B., Tan, C. C., Li, Q., & Lu, S. (2011). A timing-based scheme for rogue AP detection. Parallel and Distributed Systems, IEEE Transactions on, 22(11), 1912-1925. [152] Han, H., Sheng, B., Tan, C. C., Li, Q., & Lu, S. (2009). A measurement based rogue ap detection scheme. In INFOCOM 09, IEEE (pp. 1593-1601). IEEE. [153] Shivaraj, G., Song, M., & Shetty, S. (2010). Using Hidden Markov Model to detect rogue access points. Security and Communication Networks, 3(5), 394-407 [154] Rodrig, M., Reis, C., Mahajan, R., Wetherall, D., & Zahorjan, J. (2005). Measurementbased characterization of 802.11 in a hotspot setting. In Proceedings of the ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis (pp. 5-10). ACM. [155] Raghavendra, R., Belding, E. M., Papagiannaki, K., & Almeroth, K. C. (2007). Understanding handoffs in large ieee 802.11 wireless networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement (pp. 333-338). ACM. [156] Cheng, Y. C., Afanasyev, M., Verkaik, P., Benkö, P., Chiang, J., Snoeren, A. C., & Voelker, G. M. (2007). Automating cross-layer diagnosis of enterprise wireless networks (Vol. 37, No. 4, pp. 25-36). ACM. [157] Ergin, M. A., Ramachandran, K., & Gruteser, M. (2008). An experimental study of inter-cell interference effects on system performance in unplanned wireless LAN deployments. Computer Networks, 52(14), 2728-2744