The volume of data in broadband cellular network is growing exponentially. However, studies have indicated the traffic load on the cellular base stations varies significantly over time. This gives an opportunity to accommodate additional traffic with the same network capacity if some of the traffic (e.g., p2p, cloud sync) can be amenable to `delayed scheduling' without hurting the user experience any significantly. In this paper, we study various algorithmic problems that can arise in this context. Using a model where all flows can have certain flexibility in scheduling (via use of a `deadline'), we develop optimal or near-optimal algorithms to determine the minimum network capacity for two different models. We also develop various semi-online and online algorithms for online scheduling of flows, and analyze their performance. In particular, even though the online scheduling problem is shown to be intractable, our proposed semi-online algorithm can schedule flows optimally if aided by historical data and slightly additional network capacity over the optimal. Finally, using flow level traffic traces collected at the core of a commercially operated cellular network, we evaluate the effectiveness of our techniques. Evaluations show that delayed scheduling, when done efficiently (using an offline optimal algorithm), can accommodate the same traffic with much lower network capacity (up to 50% less) with only modest delays. While such an optimal solution needs an offline approach, we demonstrate that online scheduling can be almost equally effective when historical traffic data can be exploited for estimation purposes.

We present a tool to estimate the interference between nodes and links in a live wireless network by passive monitoring of wireless traffic. This tool does not require any controlled experiments, injection of probe traffic in the network, or even access to the network nodes. Our approach requires deploying multiple sniffers across the network to capture wireless traffic traces. These traces are then analyzed using a machine learning approach to infer the carrier-sense relationship between network nodes. This coupled with an estimation of collision probabilities helps us to deduce the interference relationships. We also demonstrate an important application of this tool-detection of selfish carrier-sense behavior. This is based on identifying any asymmetry in carrier-sense behavior between node pairs and finding multiple witnesses to raise confidence. We evaluate the effectiveness of the tool for both the applications using extensive experiments and simulation. Experimental and simulation results demonstrate that the proposed approach of estimating interference relations is significantly more accurate than simpler heuristics and quite competitive with active measurements. We also validate the approach in a real Wireless LAN environment. Evaluations using a real testbed as well as ns2 simulation studies demonstrate excellent detection ability of the selfish behavior. On the other hand, the metric of selfishness used to estimate selfish behavior matches closely with actual degree of selfishness observed.

We conduct the first detailed measurement analysis of network resource usage and subscriber behavior using a large-scale data set collected inside a nationwide 3G cellular data network. The data set tracks close to a million subscribers over thousands of base stations. We analyze individual subscriber behaviors and observe a significant variation in network usage among subscribers. We characterize subscriber mobility and temporal activity patterns and identify their relation to traffic volume. We then investigate how efficiently radio resources are used by different subscribers as well as by different applications. We also analyze the network traffic from the point of view of the base stations and find significant temporal and spatial variations in different parts of the network, while the aggregated behavior appears predictable. Broadly, our observations deliver important insights into network-wide resource usage. We describe implications in pricing, protocol design and resource and spectrum management.

We present an experimental performance evaluation study of WiFi links in an open-space outdoor environment. We consider a large scale wireless sensor network scenario of seismic data collection from sensors that are buried in ground and a set of access points (APs) form the hierarchical aggregation layer and the backbone of the network. We conduct two different link characterization studies. First, we evaluate the links between the sensor nodes and a wireless AP using IEEE 802.11a/b/g. We construct the path loss model and investigate the reachability distance of this link for different protocols and different sensor node antenna heights. We then characterize the long distance wireless backhaul links between the APs. We use 802.11n and high gain directional antenna for high throughput and long distance. We evaluate how different PHY and MAC layer enhancements of 802.11n impacts its performance in an open outdoor environment. We observed up to 148 Mb/s throughput at 800 meter line-of-sight links without sophisticated tuning of antenna orientation. We believe our findings can be a benchmark for WiFi based outdoor network deployment, especially for high throughput long distance links.

With the advent of programmability in radios, it is becoming easier for wireless network nodes to cheat to obtain an unfair share of the bandwidth. In this work we study the widely used 802.11 protocol and present a solution to detect selfish carrier-sensing behavior where a node raises the CCA (clear channel assessment) threshold for carrier-sensing, or simply does not sense carrier (possibly randomly to avoid detection). Our approach is based on detecting any asymmetry in carrier-sense behavior between node pairs and finding multiple such witnesses to raise confidence. The approach is completely passive. It requires deploying multiple sniffers across the network to capture wireless traffic traces. These traces are then analyzed by using a machine learning approach to infer carrier-sense relationships between network nodes. Evaluations using a real testbed as well as ns2 simulation studies demonstrate excellent detection ability. The metric of selfishness used to estimate selfish behavior matches closely with actual degree of selfishness observed.

Wireless interference is the major cause of degradation of capacity in 802.11 wireless networks. We present an approach to estimate the interference between nodes and links in a live wireless network by passive monitoring of wireless traffic. This does not require any controlled experiments, injection of probe traffic in the network, or even access to the network nodes. Our approach requires deploying multiple sniffers across the network to capture wireless traffic traces. These traces are then analyzed to infer the interference relations between nodes and links. We model the 802.11 MAC as a Hidden Markov Model (HMM), and use a machine learning approach to learn the state transition probabilities in this model using the observed trace. This coupled with an estimation of collision probabilities helps us to deduce the interference relationships. We show the effectiveness of this method against simpler heuristics, and also a profiling-based method that requires active measurements. Experimental results demonstrate that the proposed approach is significantly more accurate than heuristics and quite competitive with active measurements. We also validate the approach in a real WLAN environment.