The fifth generation of cellular networks (5G) will rely on edge cloud deployments to satisfy the ultra-low latency demand of future applications. In this paper, we argue that such deployments can also be used to enable advanced data-driven and Machine Learning (ML) applications in mobile networks. We propose an edge-controller-based architecture for cellular networks and evaluate its performance with real data from hundreds of base stations of a major U.S. operator. In this regard, we will provide insights on how to dynamically cluster and associate base stations and controllers, according to the global mobility patterns of the users. Then, we will describe how the controllers can be used to run ML algorithms to predict the number of users in each base station, and a use case in which these predictions are exploited by a higher-layer application to route vehicular traffic according to network Key Performance Indicators (KPIs). We show that the prediction accuracy improves when based on machine learning algorithms that rely on the controllers’ view and, consequently, on the spatial correlation introduced by the user mobility, with respect to when the prediction is based only on the local data of each single base station.

We consider the problem of separating error messages generated in large distributed data center networks into error events. In such networks, each error event leads to a stream of messages generated by hardware and software components affected by the event. These messages are stored in a giant message log. We consider the unsupervised learning problem of identifying the signatures of events that generated these messages; here, the signature of an error event refers to the mixture of messages generated by the event. One of the main contributions of the paper is a novel mapping of our problem which transforms it into a problem of topic discovery in documents. Events in our problem correspond to topics and messages in our problem correspond to words in the topic discovery problem. However, there is no direct analog of documents. Therefore, we use a non-parametric change-point detection algorithm, which has linear computational complexity in the number of messages, to divide the message log into smaller subsets called episodes, which serve as the equivalents of documents. After this mapping has been done, we use a well-known algorithm for topic discovery, called LDA, to solve our problem. We theoretically analyze the change-point detection algorithm, and show that it is consistent and has low sample complexity. We also demonstrate the scalability of our algorithm on a real data set consisting of 97 million messages collected over a period of 15 days, from a distributed data center network which supports the operations of a large wireless service provider.

User location is of critical importance to cellular network operators. It is often used for network capacity planning and to aid in the analysis of service and network diagnostics. However, existing localization techniques rely on user-provided information (e.g., Angle-of-Arrival), which are not available to the operator, and often require a significant effort to collect training data. Our main contribution is the design and evaluation of the Network-Based Localization (NBL) System for localizing a user in a 4G LTE network. The NBL System consists of 2 stages. In an offline stage, we develop RF coverage maps based on a large-scale crowd-sourced channel measurement campaign. Then, in an online stage, we present a localization algorithm to quickly match RF measurements (which are already collected as part of normal network operation) to coverage map locations. The system is more practical than related works, as it does not make any assumptions about user mobility, nor does it require expensive manual training measurements. Despite the realistic assumptions, our extensive evaluations in a national 4G LTE network show that the NBL System achieves a localization accuracy which is comparable to related works (i.e., a median accuracy of 5% of the cell's coverage region).

Efficient management and control of modern and next-gen networks is of paramount importance as networks have to maintain highly reliable service quality whilst supporting rapid growth in traffic demand and new application services. Rapid mitigation of network service degradations is a key factor in delivering high service quality. Automation is vital to achieving rapid mitigation of issues, particularly at the network edge where the scale and diversity is the greatest. This automation involves the rapid detection, localization and (where possible) repair of service-impacting faults and performance impairments. However, the most significant challenge here is knowing what events to detect, how to correlate events to localize an issue and what mitigation actions should be performed in response to the identified issues. These are defined as policies to systems such as ECOMP.

As cellular networks like 4G LTE networks get more and more sophisticated, mobiles also measure and send enormous amount of mobile measurement data (in TBs/week/metropolitan) during every call and session. The mobile measurement records are saved in data center for further analysis and mining, however, these measurement records are not geo-tagged because the measurement procedures are implemented in mobile LTE stack. Geo-tagging (or localizing) the stored measurement record is a fundamental building block towards network analytics and troubleshooting since the measurement records contain rich information on call quality, latency, throughput, signal quality, error codes etc. In this work, our goal is to localize these mobile measurement records. Precisely, we answer the following question: what was the location of the mobile when it sent a given measurement record? We design and implement novel machine learning based algorithms to infer whether a mobile was outdoor and if so, it infers the latitude-longitude associated with the measurement record. The key technical challenge comes from the fact that measurement records do not contain sufficient information required for triangulation or RF fingerprinting based techniques to work by themselves. Experiments performed with real data sets from an operational 4G network in a major metropolitan show that, the median accuracy of our proposed solution is around 20 m for outdoor mobiles and outdoor classification accuracy is more than 98%.

The FCC mandate of allowing TV Whitespaces for unlicensed access has the potential for dramatic improvements in wireless access data rates. We argue that an ideal MAC should account for diverse user-location and spectrum dependent channel rates to provide fair data rates and efficient utilization. Furthermore, due to limited tunable bandwidth of a radio and fragmented spectrum, the AP should support multiple radios. We make the following contributions by designing a MAC for wireless LAN access over TV Whitespace. (i) We propose an architecture and beaconing mechanism to enable such a MAC. Our MAC is an evolution of 802.11 MAC. (ii) We propose an algorithm that chooses the Whitespaces for the different radios of the AP and assigns clients to the radios. Our algorithm has provable guarantee and is near-optimal in many scenarios. (iii) Extensive simulation over OMNET platform demonstrates the benefit of our design over a frequency and client-location agnostic Wi-Fi-like MAC. The typical throughput gain is 30-76 percent, whereas, the reduction in collisions is up to 80 percent. (iv) We implemented a proof-of-concept prototype (by modifying madWiFi drivers) that demonstrates feasibility of our design, robustness to temporal variation of available spectrum, and system throughput.

LTE's uplink (UL) efficiency critically depends on how the interference across different cells is controlled. The unique characteristics of LTE's modulation and UL resource assignment poses considerable challenges in achieving this goal because most LTE deployments have 1:1 frequency reuse, and the uplink interference can vary considerably across successive time-slots. In this paper, we propose LeAP, a measurement data-driven machine learning paradigm for power control to manage uplink interference in LTE. The data-driven approach has the inherent advantage that the solution adapts based on network traffic, propagation, and network topology, which is increasingly heterogeneous with multiple cell-overlays. LeAP system design consists of the following components: 1) design of user equipment (UE) measurement statistics that are succinct, yet expressive enough to capture the network dynamics, and 2) design of two learning-based algorithms that use the reported measurements to set the power control parameters and optimize the network performance. LeAP is standards-compliant and can be implemented in a centralized self-organized networking (SON) server resource (cloud). We perform extensive evaluations using radio network plans from a real LTE network operational in a major metro area in the US. Our results show that, compared to existing approaches, LeAP provides$4.9\times$gain in the 20th percentile of user data rate,$3.25\times$gain in median data rate.

The success of LTE heterogeneous networks (HetNets) with macrocells and picocells critically depends on efficient spectrum sharing between high-power macros and low-power picos. Two important challenges in this context are: 1) determining the amount of radio resources that macrocells should offer to picocells, and 2) determining the association rules that decide which user equipments (UEs) should associate with picos. In this paper, we develop a novel algorithm to solve these two coupled problems in a joint manner. Our algorithm has provable guarantee, and furthermore, it accounts for network topology, traffic load, and macro-pico interference map. Our solution is standard compliant and can be implemented using the notion of Almost Blank Subframes (ABS) and Cell Selection Bias (CSB) proposed by LTE standards. We also show extensive evaluations using RF plan from a real network and discuss self-optimized networking (SON)-based enhanced inter-cell interference coordination (eICIC) implementation.

Recent trends suggest that cognitive radio based wireless networks will be frequency agile and the nodes will be equipped with multiple radios capable of tuning across large swaths of spectrum. The MAC scheduling problem in such networks refers to making intelligent decisions on which communication links to activate at which time instant and over which frequency band. The challenge in designing a low-complexity distributed MAC, that achieves low delay, is posed by two additional dimensions of cognitive radio networks: interference graphs and data rates that are frequency-band dependent, and explosion in number of feasible schedules due to large number of available frequency-bands. In this paper, we propose MAXIMAL-GAIN MAC, a distributed MAC scheduler for frequency agile multi-band networks that simultaneously achieves the following: (i) optimal network-delay scaling with respect to the number of communicating pairs, (ii) low computational complexity of O(log2(maximum degree of the interference graphs)) which is independent of the number of frequency bands, number of radios per node, and overall size of the network, and (iii) robustness, i.e., it can be adapted to a scenario where nodes are not synchronized and control packets could be lost. Our proposed MAC also achieves a throughput provably within a constant fraction (under isotropic propagation) of the maximum throughput. Due to a recent impossibility result, optimal delay-scaling could only be achieved with some amount of throughput loss . Extensive simulations using OMNeT++ network simulator shows that, compared to a multi-band extension of a state-of-art CSMA algorithm (namely, Q-CSMA), our asynchronous algorithm achieves a 2.5x reduction in delay while achieving at least 85% of the maximum achievable throughput. Our MAC algorithms are derived from a novel local search based technique.

There are two emerging trends in the mobile data world. First, mobile data is exploding at a rapid rate with analysts predicting 25-50X growth by the year 2015. The second trend is that users are demanding greater degree of flexibility in selecting their operators at fine timescales. Across Asia, dual-SIM phones have become popular, while Apple is rumored to be designing a Universal SIM that will allow iPhone users to toggle between different operators. This latter trend points towards an impending disruption in wireless service models which could also be the need of the hour from the spectrum shortage perspective.

In November 2008, the FCC ruled that the digital TV whitespaces be used for unlicensed access. This is an exciting development because DTV whitespaces are in the low frequency range (50-698 MHz) compared to typical cellular and ISM bands, thus resulting in much better propagation characteristics and much higher spectral efficiencies. The FCC has also mandated certain guidelines for short range unlicensed access, so as to avoid any interference to DTV receivers. We consider the problem of WiFi like access (popularly referred to as WiFi 2.0) for enterprizes. We assume that the access points and client devices are equipped with cognitive radios, i.e., they can adaptively choose the center frequency, bandwidth and ower of operation. The access points can be equipped with one or more radios. Our goal is to design a complete system, which (i) does not violate the FCC mandate, (ii) dynamically assigns center frequency and bandwidth to each access point based on their demands and (iii) squeezes the maximum efficiency from the available spectrum. This problem is far more general than prior work that investigated dynamic spectrum allocation in cellular and ISM bands, due to the non-homogenous nature of the whitespaces, i.e., different whitespace widths in different parts of the spectrum and the large range of frequency bands with different propagation characteristics. This calls for a more holistic approach to system design that also accounts for frequency dependent propagation characteristics and radio frontend characteristics. In this paper, we first propose design rules for holistic system design. We then describe an architecture derived from our design rules. Finally we propose demand based dynamic spectrum allocation algorithms with provable worst case guarantees. We provide extensive simulation results showing that (i) the performance of our algorithm is within 94% of the optimal in typical settings and (ii) and the DTV whitespaces can provide significantly higher data rates compared to the 2.4GHz ISM band. Our approach is general enough for designing any system with access to a wide range of spectrum.

Many structured peer-to-peer (P2P) systems have been proposed as distributed hash tables (DHTs) for fast and efficient lookup of queries. In this paper, we propose a novel technique for improving average lookup times in P2P systems by caching additional neighbor pointers based on peer access frequencies. In particular, we address the problem of each peer choosing the k best pointers to store (in addition to its index pointers) to minimize the average query lookup times. We focus on two popular P2P systems, namely Pastry and Chord: we exploit the inherent structure of these systems to develop efficient, scalable algorithms for optimally choosing the k additional pointers. Simulations with Chord and Pastry demonstrate that our algorithms are very effective in reducing the lookup times significantly. Our approach can be used in tandem with other techniques such as item caching and replication, and is particularly useful for applications such as name services in mobile environments or location services, where we can expect a low churn rate for peers and a relatively higher churn rate for items.

IEEE 802.16e WiMAX is a promising new technology for broadband access networks. Amongst the class of applications that can be supported is real time video services (such as IPTV, broadcast of live events etc.). These applications are bandwidth hungry and have stringent delay constraints. Thus, scalable support for such applications is a challenging problem. To address this challenge, we consider a combination of approaches using multicast, layer encoded video and adaptive modulation of transmissions. Using these, we develop algorithms to ensure efficient, fair and timely delivery of video in WiMAX networks. The corresponding resource allocation problem is challenging because scheduling decisions (within a WiMAX base station) are performed in real-time across two dimensions, time and frequency. Moreover, combining layered video with appropriate modulation calls for novel MAC algorithms. We model the multicast resource allocation problem in WiMAX and demonstrate this problem to be NP-hard. We present a fast greedy algorithm that is (i) provably within a constant approximation of the optimal solution (based on a metric that reflects video quality as perceived by the user), and (ii) performs within 87-95% of the optimal as demonstrated by realistic simulations. We also demonstrate that our algorithm offers a 25% improvement over a naive algorithm. Moreover, in terms of the average rate received by each user, our algorithm out-performs the naive algorithm by more than 50%.

In a wireless network withnodeexclusivespectrumsharing, two popular schedules are maximum weight matching (MWM) schedule and maximum size matching (MSM) schedule. The former has been proved to be throughput optimal and has superior delay properties, and the latter schedules as many links, with packets to transmit, as possible. However, it is challenging to design algorithms for computing these schedules that (i) are distributed, (i.e., only local message exchanges between neighboring nodes are permitted) (ii) have low running times (iii) exchanges a small number of messages. In this paper, we develop algorithms that satisfy these properties and also provide good approximations to MWM and MSM schedules. We also note that constant approximation to MWM leads to improved delay properties. We refer to a round as a length of time over which every node in the network can make at most one message-transmission attempt. We propose distributed algorithms for computing (i) 1/2 - epsi e approximation to MWM schedule in O(log(1/epsi) log2n) rounds, and (ii) 2/3 - epsi approximation to MSM schedule in O((1/epsi) log2n) rounds, where n is the network size. Simulation results with a popular model for wireless ad-hoc networks demonstrate that (i) our algorithms perform within 85% - 95% of the optimal in many scenarios, and (ii) the time-complexity of the algorithms can be reduced considerably in practice. The number of message transmissions for both our algorithms scale as O(n log2n). In summary, ours is the first work to (i) provide half (two-third) approximate distribute algorithms for computing MWM (MSM) schedule with logarithmic time- complexity and quasi-linear message exchanges (ii) demonstrate that the algorithms are close to optimal for realistic topologies.

We study the problem of scheduling in OFDMA-based relay networks with emphasis on IEEE 802.16j based WiMAX relay networks. In such networks, in addition to a base station, multiple relay stations are used for enhancing the throughput, and/or improving the range of the base station. We solve the problem of MAC scheduling in such networks so as to serve the mobiles in a fair manner while exploiting the multiuser diversity, as well as the frequency selectivity of the wireless channel. The scheduling resources consist of tiles in a two-dimensional scheduling frame with time slots along one axis, and frequency bands or sub-channels along the other axis. The resource allocation problem has to be solved once every scheduling frame which is about 5 - 10 ms long. While the original scheduling problem is computationally complex, we provide an easy-to-compute upper bound on the optimum. We also propose three fast heuristic algorithms that perform close to the optimum (within 99.5%), and outperform other algorithms such as OFDM2A proposed in the past. Through extensive simulation results, we demonstrate the benefits of relaying in throughput enhancement (an improvement in the median throughput of about 25%), and feasibility of range extension (for e.g., 7 relays can be used to extend the cell-radius by 60% but mean throughput reduces by 36%). Our algorithms are easy to implement, and have an average running time of less than 0.05 ms making them appropriate for WiMAX relay networks.

In many distributed environments, the primary function of monitoring software is to detect anomalies, i.e., instances when system behavior deviates substantially from the norm. In this paper, we propose communication-efficient schemes for the anomaly detection problem, which we model as one of detecting the violation of global constraints defined over distributed system variables. Our approach eliminates the need to continuously track the global system state by decomposing global constraints into local constraints that can be checked efficiently at each site. Only in the occasional event that a local constraint is violated, do we resort to more expensive global constraint checking. We show that the problem of selecting the local constraints, based on frequency distribution of individual system variables, so as to minimize the communication cost is NP-hard. We propose approximation algorithms for computing provably near-optimal (in terms of the number of messages) local constraints. Experimental results with real-life network traffic data sets demonstrate that our technique can reduce message communication overhead by as much as 70% compared to existing data distribution-agnostic approaches.

The Birkhoff-von Neumann (BVN) strategy for single-stage input-queued crossbar switches does not support multicast, as it considers only permutation-based switch configurations. This paper extends the BVN strategy to multicast switching, where an input can simultaneously transmit to multiple outputs. Knowledge of the average rates of flows is used to compute an offline schedule. We begin by considering a system in which the fanout of each flow is split in a predecided manner. We call this static splitting (as opposed to dynamic splitting where no such constraint is imposed), and we study the rate region of the switch under this restriction. We provide a graph-theoretic formulation of the rate region.

Recently, there has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper, we present a novel gossip-based scheme using which all the nodes in an n-node overlay network can compute the common aggregates of MIN, MAX, SUM, AVERAGE, and RANK of their values using O(n log log n) messages within O(log n log log n) rounds of communication. To the best of our knowledge, ours is the first result that shows how to compute these aggregates with high probability using only O(n log log n) messages. In contrast, the best known gossip-based algorithm for computing these aggregates requires O(nlog n) messages and O(log n) rounds. Thus, our algorithm allows system designers to trade off a small increase in round complexity with a significant reduction in message complexity. This can lead to dramatically lower network congestion and longer node lifetimes in wireless and sensor networks, where channel bandwidth and battery life are severely constrained.

The problem of simultaneously disseminating k messages in a large network of n nodes, in a decentralized and distributed manner, where nodes only have knowledge about their own contents, is studied. In every discrete time-step, each node selects a communication partner randomly, uniformly among all nodes and only one message can be transmitted. The goal is to disseminate rapidly, with high probability, all messages to all nodes. It is shown that a random linear coding (RLC) based protocol disseminates all messages to all nodes in time ck+/spl Oscr/(/spl radic/kln(k)ln(n)), where c<3.46 using pull-based dissemination and c<5.96 using push-based dissemination. Simulations suggest that c<2 might be a tighter bound. Thus, if k/spl Gt/(ln(n))/sup 3/, the time for simultaneous dissemination RLC is asymptotically at most ck, versus the /spl Omega/(klog/sub 2/(n)) time of sequential dissemination. Furthermore, when k/spl Gt/(ln(n))/sup 3/, the dissemination time is order optimal. When k/spl Lt/(ln(n))/sup 2/, RLC reduces dissemination time by a factor of /spl Omega/(/spl radic/k/lnk) over sequential dissemination. The overhead of the RLC protocol is negligible for messages of reasonable size. A store-and-forward mechanism without coding is also considered. It is shown that this approach performs no better than a sequential approach when k=/spl prop/n. Owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying Bernoulli process.

We study the gains to be had by using random linear coding (RLC) for simultaneously disseminating k distinct messages in a network of n nodes in a decentralized and distributed manner for arbitrary k and n. The goal is to rapidly disseminate all the messages among all the nodes. Any node can communicate with any of the other nodes but only one at a time, nodes only have knowledge about their own contents, and the bandwidth for every transmission between two nodes is limited (does not scale with k or n). An efficient and well-studied protocol for message dissemination in such a framework is randomized gossip based message dissemination. The problem has been studied extensively without using any coding for message dissemination. We show using analysis and simulation that, in the regime k ges (ln(n))3, RLC based dissemination reduces the dissemination time (the time-steps to disseminate all the messages among all the nodes) by a factor of otimes(ln(n)) as compared to disseminating the messages sequentially (i.e., one after the other) as implicit in most non-coding based technique. In the regime k les (ln(n))2, the dissemination time with RLC goes down by a factor of Omega(radick / ln k). More precisely, our results indicate that a RLC based protocol disseminates all the messages among all the nodes in time ck + O(radick ln(k)(ln(n)) for a suitable constant c > 0. Analytical results show that, c < 3.46 using pull based dissemination, and c < 5.96 using push based dissemination, but reported simulations suggest c < 2 might be a tighter bound

The flow control algorithms currently used in the Internet have been tailored to share available capacity between users on the basis of the physical characteristics of the network links they use rather than the characteristics of their applications. However, real-time applications typically have very different requirements from file transfer or Web browsing, and treating them identically can result in a perception of poor quality of service even when adequate bandwidth is available. This is the motivation for differentiated services. In this paper, we explore service differentiation between persistent (fixed duration) and transient (fixed volume) flows, and also between transient flows of markedly different sizes; the latter is stimulated by current discussion on Web mice and elephants. We propose decentralized bandwidth allocation algorithms that can be implemented by end-systems without requiring the support of a complex network architecture, and show that they achieve performance very close to what is achievable by the optimal centralized scheme.

Mathematical models of congestion control capture the congestion indication mechanism at the router in two different ways: rate-based models, where the queue-length at the router does not explicitly appear in the model, and queue-based models, where the queue length at the router is explicitly a part of the model. Even though most congestion indication mechanisms use the queue length to compute the packet marking or dropping probability to indicate congestion, we argue that, depending upon the choice of the parameters of the AQM scheme, one would obtain a rate-based model or a rate-and-queue-based model as the deterministic limit of a stochastic system with a large number of users. We also consider the impact of implementing AQM schemes in the real queue or a virtual queue. If an AQM scheme is implemented in a real queue, we show that, to ensure that the queuing delays are negligible compared to RTTs, one is forced to choose the parameters of a AQM scheme in a manner which yields a rate-based deterministic model. On the other hand, if the AQM scheme is implemented in a virtual queue, small-queue operation is achieved independent of the choice of the parameters, thus showing a robustness property of virtual queue-based schemes.

We consider the problem of congestion control in networks which support both multirate multicast sessions and unicast sessions. We present a decentralized algorithm which enables the different rate-adaptive receivers in different multicast sessions to adjust their rates to satisfy some fairness criterion. A one-bit ECN marking strategy to be used at the nodes is also proposed. The congestion-control mechanism does not require any per-flow state information for unicast flows at the nodes. At junctions nodes of each multicast tree, some state information about the rates along the branches at the node may be required. The congestion-control mechanism takes into account the diverse user requirements when different receivers within a multicast session have different utility functions, but does not require the network to have any knowledge about the receiver utility functions.

With the rapid growth of Internet, parameter design and analysis for large-scale networks has become a topic of active interest. Since simulation of such large scale systems is not easy, deterministic fluid models have been widely used for both qualitative understanding of the behavior, as well as parameter design for such networks. In this paper, we first study a deterministic fluid model for Internet congestion control when there are multiple TCP-like flows present. We provide conditions under which such a system is globally asymptotically stable in the presence of feedback delay. We then study the corresponding system with the addition of web mice and other nonresponsive flows modeled as stochastic disturbances. We show that, when there are a large number of flows, choosing parameters based on the global stability criterion for the deterministic system (with the noise replaced by its mean value) ensures global stability for the stochastic system as well. Numerical examples and simulation results with some popular active queue management mechanisms validate the parameter choices from analysis. The results indicate that a system with multiple TCP-like flows is globally stable as long as the bandwidth-delay product per flow is not very small.

We address the problem of time varying connectivity, as would arise in a wireless communication system with channels occasionally becoming more error prone. Such channels have the property that they can only be used during intervals of variable duration as the devices' connectivities with a centralized controller change unpredictably with time. We propose a link state history based scheme in which the centralized controller, (a master for a master slave kind of system) tries to identify at each scheduling instant, the devices seeing bad connectivity. We demonstrate the advantage of the scheme on top of a master driven frequency hopping system derived from the Bluetooth specification. We also analyze the scheme using Markov chains. Numerical results from analysis show the performance of the scheme. We show that, with the right tuning of parameters, we can achieve high accuracy in identifying the good and the bad periods of the channels. Simulation results are also shown indicating improvement in throughput and goodput.