Proportional Fair (PF) scheduling algorithms are the de facto standard in cellular networks. They exploit the users' channel state diversity (induced by fast-fading) and are optimal for stationary channel state distributions and an infinite time-horizon. However, mobile users experience a nonstationary channel, due to slow-fading (on the order of seconds), and are associated with base stations for short periods. Hence, we develop the Predictive Finite-horizon PF Scheduling ((PF)2S) Framework that exploits mobility. We present extensive channel measurement results from a 3G network and characterize mobility-induced channel state trends. We show that a user's channel state is highly reproducible and leverage that to develop a data rate prediction mechanism. We then present a few channel allocation estimation algorithms that exploit the prediction mechanism. Our trace-based simulations consider instances of the (PF)2S Framework composed of combinations of prediction and channel allocation estimation algorithms. They indicate that the framework can increase the throughput by 15%-55% compared to traditional PF schedulers, while improving fairness.

In this work, using ns-3 and different mobility models, we simulate realistic LTE network scenarios to study the effect of handover on two popular schedulers, namely the Proportional Fair (PF) and Max Weight (MW) scheduler. The performances of these schedulers are widely studied in the literature via simulation and mathematical analysis in the absence of handovers. Specifically, it has been shown that MW is throughput optimal among all scheduling policies that stabilize the system in the sense of bounding the user queues. In our experiments, however, we observe that such general conclusions may not be accurate in the presence of mobile users that hand over across multiple cells. To this end, we show that: i) MW achieves higher throughput than PF when users are confined to a single cell, but ii) when there is handover in the network across multiple cells, PF achieves a throughput similar to that of MW, and in some cases even slightly outperforms MW. Furthermore, these observations are consistent across a wide range of network scenarios in terms of round-trip delay, buffer size and channel fading.

Cellular providers are rapidly deploying multiple technologies like cell biasing, carrier aggregation, co-ordinated interference control/scheduling to improve capacity and coverage. In this paper, we explore a complementary transport layer approach based on multipath TCP that can concurrently use multiple interfaces to boost throughput of users with poor coverage and improve fairness. Multipath TCP has been recently standardized by IETF and requires no modifications to applications. It has been shown to improve fairness and throughput in wire line environments and individual user throughputs in wireless networks. However, in a wireless multi-user environment, it is not clear that it is always beneficial, as we show in this paper. Therefore, we examine if it is indeed beneficial for a service provider to judiciously decide whether to enable multiple cellular interfaces on a smart phone based on a global centralized view of its network. Alternatively, should a device decide independently based only on a local view? To quantify the network wide impact in a system where users have multiple cellular interfaces, we have developed centralized and distributed heuristic algorithms to evaluate this, particularly in the context of fairness across all the users. Our simulations and numerical models show that there are potential gains in fairness (15-30%) to be realized by judiciously enabling multipath connections at the cell edge. These gains diminish as the number of users in a cell increases or users behave greedily. We also quantify the delicate balance between throughput and fairness. Our analysis provides an intuition on which user(s) in a cellular network stand to benefit the most by enabling multiple interfaces. We also discuss LTE protocol mechanisms to enforce associations of specific interfaces to specific cells.

Proportional Fair (PF) scheduling algorithms are the de-facto standard in cellular networks. They exploit the users' channel state diversity (induced by fast-fading), and are optimal for stationary channel state distributions and an infinite time-horizon. However, mobile users experience a non-stationary channel, due to slow-fading (on the order of seconds), and are associated with basestations for short periods. Hence, we develop the Predictive Finite-horizon PF Scheduling ((PF)2S) Framework that exploits mobility. We present extensive channel measurement results from a 3G network and characterize mobility-induced channel state trends. We show that a user's channel state is highly reproducible and leverage that to develop a data rate prediction mechanism. We then present a few channel allocation estimation algorithms that rely on the prediction mechanism. Our trace-based simulations consider instances of the PF2S Framework composed of combinations of prediction and channel allocation estimation algorithms. They indicate that the framework can increase the throughput by 15%–55% compared to traditional PF schedulers, while improving fairness.

Designing scheduling algorithms that work in synergy with TCP is a challenging problem in wireless networks. Extensive research on scheduling algorithms has focused on inelastic traffic, where there is no correlation between traffic dynamics and scheduling decisions. In this work, we study the performance of several scheduling algorithms in LTE networks, where the scheduling decisions are intertwined with wireless channel fluctuations to improve the system throughput. We use ns-3 simulations to study the performance of several scheduling algorithms with a specific focus on Max Weight (MW) schedulers with both UDP and TCP traffic, while considering the detailed behavior of OFDMA-based resource allocation in LTE networks. We show that, contrary to its performance with inelastic traffic, MW schedulers may not perform well in LTE networks in the presence of TCP traffic, as they are agnostic to the TCP congestion control mechanism. We then design a new scheduler called “Queue MW” (Q-MW) which is tailored specifically to TCP dynamics by giving higher priority to TCP flows whose queue at the base station is very small in order to encourage them to send more data at a faster rate. We have implemented Q-MW in ns-3 and studied its performance in a wide range of network scenarios in terms of queue size at the base station and round-trip delay. Our simulation results show that Q-MW achieves peak and average throughput gains of 37% and 10% compared to MW schedulers if tuned properly.

The opportunities to understand human-mobility have increased significantly of late with the rapid adoption of wireless devices that report locations frequently. In this work1, we utilize one such rich data-set comprising of nationwide call data records from several million users to analyze and understand their location patterns. We define a location pattern as the set of locations visited by a user, which roughly speaking, can be considered to be the footprint of the user. Such an analysis is useful since it allows insight into aspects such as the range covered by a user, general direction and major routes of travel, characterization of geographic areas etc.,. These in turn are useful inputs for network planning, traffic planning and mobility models. We propose a systematic methodology that utilizes geometric structures like the Minimum Area Rectangle, line segmentation and clustering techniques to extract meaningful information for location patterns and apply it to our large data-set. Based on this we report on aspects such as the size and orientation of footprints, length of major routes as well as characterize and compare locales based on movement patterns. Finally, we identify some key features of location patterns that can be modeled very well with a single statistical distribution, the Double Pareto LogNormal (DPLN) distribution regardless of locale.

We consider a number of related problem formulations pertaining to adaptive subcarrier allocation in multiuser Orthogonal Frequency-Division Multiplexing (OFDM) systems, and prove that they are NP-hard. Thus there exist no known algorithms that can provide optimal solutions for all instances of these problems in polynomial time. We further prove that these problems are hard to approximate in polynomial time. Finally, we discuss qualitatively the settings under which worst case performance is likely to be observed.

Modern cellular networks commonly deploy rapid channel rate adaptation to vary the wireless capacity in response to channel conditions while maintaining a fixed target error rate (typically 1%). Although desirable in terms of throughput for inelastic applications that do not adapt to network conditions, a low fixed target error rate incurs the expense of significant power consumption, especially at high transmission rates. In this work, we show that elastic traffic, in particular TCP, benefits greatly from the perspective of power efficiency when we also incorporate target error rate adaptation. More specifically, TCP behavior, although sensitive to packet errors, is not uniformly so. When TCP has a small window, it requires extremely low packet error rates. However, for large windows, especially with a buffer, TCP can tolerate larger loss rates. The contribution of this work is in conducting a detailed and realistic investigation into how beneficial target error rate adaptation is for TCP in terms of reducing power and impact on throughput. Our work differs from past contributions in that we explicitly take into account the impact of the buffer and a variable channel. We devise simple local power-adaptation policies based on TCP behavior and study them with the help of a numerical model. Finally, we present a detailed investigation of our policies using actual modulation schemes and real channel traces collected on a commercial 1xEV-DO network. The results show that compared to the existing scheme, our policies save typically about 20% to 30% power with marginal or no reduction in throughput.

This paper explores the use of rate adaptation in cellular networks to maximize throughput of long-lived TCP sessions. We focus on the problem of maximizing the throughput of TCP connections and propose a joint optimization of MAC and physical layer parameters with respect to TCP sending rate. In particular, we propose a simple TCP-aware channel scheduler that adapts the wireless channel rate to changes in the TCP sending rate and explore its performance for both single and multiple concurrent sessions. In the case of a single TCP session, we develop a fluid model of its steady-state behavior in such a system that adapts between two channel rates. Our results indicate that a two-rate scheme improves TCP throughput by 15% to 20% over a system that does not exploit rate adaptation and that little additional benefit accrues from the addition of a third channel rate. Finally, we extend the framework to scenarios where bandwidth is shared by multiple TCP sessions. We propose two channel allocation algorithms and explore their performance through simulation. Our results indicate that TCP throughput is relatively insensitive to either channel allocation algorithm and adaptive rate variation is the dominant factor in performance.

We analyze a massive social network, gathered from the records of a large mobile phone operator, with more than a million users and tens of millions of calls. We examine the distributions of the number of phone calls per customer; the total talk minutes per customer; and the distinct number of calling partners per customer. We find that these distributions are skewed, and that they significantly deviate from what would be expected by power-law and lognormal distributions.

We present an experimental characterization of the physical and MAC layers in CDMA 1xEV-DO and their impact on transport layer performance. The 1xEV-DO network is currently the fastest mobile broadband cellular network, offering data rates of up to 3.1 Mbps for both stationary and mobile users. These rates are achieved by using novel capacity enhancement techniques at the lower layers. Specifically, 1xEV-DO incorporates rapid channel rate adaptation in response to signal conditions, and opportunistic scheduling to exploit channel fluctuations. Although shown to perform well in isolation, there is no comprehensive literature that examines the impact of these features on transport layer and application performance in real networks.

Sampling techniques are widely used for traffic measurements at high link speed to conserve router resources. Traditionally, sampled traffic data is used for network management tasks such as traffic matrix estimations, but recently it has also been used in numerous anomaly detection algorithms, as security analysis becomes increasingly critical for network providers. While the impact of sampling on traffic engineering metrics such as flow size and mean rate is well studied, its impact on anomaly detection remains an open question. This paper presents a comprehensive study on whether existing sampling techniques distort traffic features critical for effective anomaly detection. We sampled packet traces captured from a Tier-1 IP-backbone using four popular methods: random packet sampling, random flow sampling, smart sampling, and sample-and-hold. The sampled data is then used as input to detect two common classes of anomalies: volume anomalies and port scans. Since it is infeasible to enumerate all existing solutions, we study three representative algorithms: a wavelet-based volume anomaly detection and two portscan detection algorithms based on hypotheses testing. Our results show that all the four sampling methods introduce fundamental bias that degrades the performance of the three detection schemes, however the degradation curves are very different. We also identify the traffic features critical for anomaly detection and analyze how they are affected by sampling. Our work demonstrates the need for better measurement techniques, since anomaly detection operates on a drastically different information region, which is often overlooked by existing traffic accounting methods that target heavy-hitters.

TCP is the dominant transport protocol over both wired and wireless links. It is however, well known that TCP is not suitable for wireless networks and several solutions have been proposed to rectify this shortcoming. In this work, we explore cross-layer optimization of the rate adaptation feature of cellular networks to optimize throughput of a single long-lived TCP session. Modern cellular networks rate RF technology that allows them to dynamically vary the wireless channel rate in response to user demand and channel conditions. However, the set of data rates as well as the scheduler's rate adaptation policy are typically chosen to optimize throughput for inelastic applications. In order to optimize such a system for TCP, we propose a two state TCP-aware scheduler that switches between two chanrates as a function of the TCP sending rate. We develop a fluid model of the steady-state behavior of a TCP session in such a system and derive analytical expressions for TCP throughput that explicitly account for rate variability as well as the dependency between the scheduler and TCP. Using the model we choose RF layer parameters that, in conjunction with the TCP-aware scheduler, improve term throughput of a single TCP flow by 15.25%. We also compare our analytical results against those obtained from ns-2 simulations and confirm that our model indeed closely approximates TCP behavior in such an environment.

Packet sampling is commonly deployed in high-speed backbone routers to minimize resources used for network monitoring. It is known that packet sampling distorts traffic statistics and its impact has been extensively studied for traffic engineering metrics such as flow size and mean rate. However, it is unclear how packet sampling impacts anomaly detection, which has become increasingly critical to network providers. This paper is the first attempt to address this question by focusing on one common class of nonvolume-based anomalies, portscans , which are associated with worm/virus propagation. Existing portscan detection algorithms fall into two general approaches: target-specific and traffic profiling. We evaluated representative algorithms for each class, namely: 1) TRWSYN that performs stateful traffic analysis; 2) TAPS that tracks connection pattern of scanners; and 3) entropy-based traffic profiling. We applied these algorithms to detect portscans in both the original and sampled packet traces from a Tier-1 provider's backbone network. Our results demonstrate that sampling introduces fundamental bias that degrades the effectiveness of these detection algorithms and dramatically increases false positives. Through both experiments and analysis, we identify the traffic features critical for anomaly detection that are affected by sampling. Finally, using insight gained from this study, we show how portscan algorithms can be enhanced to be more robust to sampling.

Traffic engineering aims to distribute traffic so as to "optimize" some performance criterion. This optimal distribution of traffic depends on both the routing protocol and the forwarding mechanisms in use in the network. In IP networks running the OSPF or IS-IS protocols, routing is over shortest paths, and forwarding mechanisms distribute traffic "uniformly" over equal cost shortest paths. These constraints often make achieving an optimal distribution of traffic impossible. In this paper, we propose and evaluate an approach that can realize near optimal traffic distribution without changes to routing protocols and forwarding mechanisms. In addition, we explore the tradeoff that exists between performance and the configuration overhead that our solution requires. The paper's contributions are in formulating and evaluating an approach to traffic engineering in IP networks that achieves near-optimal performance while preserving the existing infrastructure.

We present an analytical technique of very low complexity, using the inclusion-exclusion principle of combinatorics, for the performance evaluation of all-optical, wavelength-division multiplexed networks with no wavelength conversion. The technique is a generalized reduced-load approximation scheme which is applicable to arbitrary topologies and traffic patterns. One of the main issues in computing blocking probabilities in all-optical networks is the significant link load correlation introduced by the wavelength continuity constraint. One of the models we propose takes this into account and gives good results even under conditions with high link load correlation. Through numerous experiments we show that our models can be used to obtain fast and accurate estimates of blocking probabilities in all-optical networks and scale well with the path length and capacity of the network. We also extend one of our models to take into account alternate routing, in the form of Fixed Alternate Routing and Least Loaded Routing.

Routing loops are caused by inconsistencies in the routing state of the network. Although undesirable from this aspect, they can provide insight into the routing dynamics that caused them. In this work we present a methodology that utilizes a priori knowledge of loops to study the correlation between routing loops and routing events that could have caused them. We apply our technique to associate route changes with packet loops detected in actual traffic traces collected from the Sprint Backbone. Our study shows that a strong correlation exists between loops and changes in the BGP routing state while the link state protocols ISIS is seldom responsible for such events. Our analysis also identifies factors that influence the distribution of loop path lengths as well as the effectiveness of our detection techniques.

Traffic engineering is aimed at distributing traffic so as to "optimize" a given performance criterion. The ability to carry out such an optimal distribution depends on both the routing protocol and the forwarding mechanisms in use in the network. In IP networks running the OSPF or IS-IS protocols, routing is over shortest paths, and forwarding mechanisms are constrained to distributing traffic uniformly over equal cost shortest paths. These constraints often make achieving an optimal distribution of traffic impossible. In this paper, we propose and evaluate an approach, based on manipulating the set of next hops for routing prefixes, that is capable of realizing near optimal traffic distribution without any change to existing routing protocols and forwarding mechanisms. In addition, we explore the tradeoff that exists between performance and the overhead associated with the additional configuration steps that our solution requires. The paper's contributions are in formulating and evaluating an approach to traffic engineering for existing IP networks that achieves performance levels comparable to that offered when deploying other forwarding technologies such as MPLS.

We present a new analytical technique, based on the inclusion-exclusion principle from combinatorial mathematics, for the analysis of all-optical networks with no wavelength conversion and random wavelength assignment. We use this technique to propose two models of low complexity for analysing networks with arbitrary topologies and traffic patterns. The first model improves the current technique by Birman (1996) in that the complexity of calculation is independent of hop-length and scales only with the capacity of the link as against that of Birman's method which grows exponentially with hop-length. We then propose a new heuristic to account for wavelength correlation and show that the second model is accurate even for sparse networks. Our technique can also be extended to analyse fixed alternate and least loaded routing.