In this paper, we consider hybrid quantum key distribution (QKD) networks with primarily quantum repeaters and a small number of trusted nodes. While the trusted nodes need to be trusted, the use of such nodes, together with efficient routing algorithms, can significantly improve the key generation rate. We show that when trusted nodes are placed at asymmetric locations relative to Alice and Bob, however, existing routing algorithms can lead to low key rate. To address this issue, we develop dynamic routing strategies that adjust routing decisions based on the current key pool conditions in the network. In addition, we investigate new and existing classical post-processing techniques that complement the dynamic routing strategies. Using extensive simulations, we show that our dynamic routing strategies can significantly outperform static strategies, and the post-processing techniques are beneficial in high noise scenarios. In addition, combining the dynamic routing strategies and post-processing techniques can further improve the overall key rate.

Smartphones have emerged as ubiquitous platforms for people to consume content in a wide range of consumption contexts (C2) , e.g., over cellular or WiFi, playing back audio and video directly on phone or through peripheral devices such as external screens or speakers. In this article, we argue that a user’s specific C2 is an important factor to consider in Adaptive Bitrate (ABR) streaming. We examine the current practices of using C2 in five popular ABR players, and identify various limitations in existing treatments that have a detrimental impact on network resource usage and user experience. We then formulate C2-cognizant ABR streaming as an optimization problem and develop practical best-practice guidelines to realize it. Instantiating these guidelines, we develop a proof-of-concept implementation in the widely used state-of-the-art ExoPlayer platform and demonstrate that it leads to significantly better tradeoffs in terms of user experience and resource usage. Last, we show that the guidelines also benefit dash.js player that uses an ABR logic significantly different from that of ExoPlayer.

Low-latency live (LLL) adaptive bitrate (ABR) streaming relies critically on accurate bandwidth estimation to react to dynamic network conditions. While existing studies have proposed bandwidth estimation techniques for LLL streaming, these approaches are at the application level, and their accuracy is limited by the distorted timing information observed at the application level. In this paper, we propose a novel cross-layer approach that uses coarse-grained application-level semantics and fine-grained kernel-level packet capture to obtain accurate bandwidth estimation. We incorporate this technique in three popular open-source ABR players and show that it provides significantly more accurate bandwidth estimation than the state-of-the-art application-level approaches. In addition, the more accurate bandwidth estimation leads to better bandwidth prediction, which we show can lead to significantly better quality of experience (QoE) for end users.

Smartphones have emerged as ubiquitous platforms for people to consume content in a wide range of consumption contexts (C2), e.g., over cellular or WiFi, playing back audio and video directly on phone or through peripheral devices such as external screens or speakers, etc. In this paper, we argue that a user's specific C2 is an important factor to consider in Adaptive Bitrate (ABR) streaming. We examine the current practice of using C2 in four popular ABR players, and identify various limitations in existing treatments that have a detrimental impact on network resource usage and user experience. We then develop practical best-practice guidelines for C2-cognizant ABR streaming. Instantiating these guidelines, we develop a proof-of-concept implementation in the widely used state-of-the-art ExoPlayer platform and demonstrate that it leads to significantly better tradeoffs in terms of user experience and resource usage.

Neighbor discovery on duty-cycled mobile devices in group settings arises in many applications. In such scenarios, it is sufficient for an arbitrary node in a group to discover a new node. While pairwise neighbor discovery schemes can be directly applied to group settings, their performance can be severely limited as they are not designed to coordinate the efforts of group members. Explicit coordination among the group members, however, can incur large overhead in mobile networks, where the group membership changes dynamically over time. In this paper, we focus on schemes that require no explicit communication among the group members, and nodes follow deterministic schedules that can be succinctly represented. We first define the notion ofideal duty cyclefor a group, and then develop two deterministic neighbor discovery schemes for group settings, and show that both of them achieve effective duty cycle close to the ideal duty cycle. In addition, we show that the schemes are lightweight and easy to implement using experiments in a testbed. Last, we use a case study to demonstrate the usage of our proposed schemes and show that a simple enhancement leveraging the deterministic nature of the schemes leads to significant performance improvement, at the cost of only slight extra overhead.

Over-the-top video (OTT) streaming accounts for the majority of traffic on cellular networks, and also places a heavy demand on users' limited monthly cellular data budgets. In contrast to much of traditional research that focuses on improving the quality, we explore a different direction---using data budget information to better manage the data usage of mobile video streaming, while minimizing the impact on users' quality of experience (QoE). Specifically, we propose a novel framework for quality-aware Adaptive Bitrate (ABR) streaming involving a per-session data budget constraint. Under the framework, we develop two planning based strategies, one for the case where fine-grained perceptual quality information is known to the planning scheme, and another for the case where such information is not available. Evaluations for a wide range of network conditions, using different videos covering a variety of content types and encodings, demonstrate that both these strategies use much less data compared to state-of-the-art ABR schemes, while still providing comparable QoE. Our proposed approach is designed to work in conjunction with existing ABR streaming workflows, enabling ease of adoption.

While routing in wireless networks has been studied extensively, existing protocols are typically designed for a specific set of network conditions and so do not easily accommodate changes in those conditions. For instance, protocols that assume network connectivity cannot be easily applied to disconnected networks. In this paper, we develop a distributed routing strategy based on deep reinforcement learning that generalizes to diverse traffic patterns, congestion levels, network connectivity, and link dynamics. We make the following key innovations in our design: (i) the use of relational features as inputs to the deep neural network approximating the decision space, which enables our algorithm to generalize to diverse network conditions, (ii) the use of packet-centric decisions to transform the routing problem into an episodic task by viewing packets, rather than wireless devices, as reinforcement learning agents, which provides a natural way to propagate and model rewards accurately during learning, and (iii) the use of extended-time actions to model the time spent by a packet waiting in a queue, which reduces the amount of training data needed and allows the learning algorithm to converge more quickly. We evaluate our routing algorithm using a packet-level simulator and show that the policy our algorithm learns during training is able to generalize to larger and more congested networks, different topologies, and diverse link dynamics. Our algorithm outperforms shortest path and backpressure routing with respect to packets delivered and delay per packet.

Recent studies have demonstrated that geographic location features collected using smartphones can be a powerful predictor for depression. While location information can be conveniently gathered by GPS, typical datasets suffer from significant periods of missing data due to various factors (e.g., phone power dynamics, limitations of GPS). A common approach is to remove the time periods with significant missing data before data analysis. In this paper, we develop an approach that fuses location data collected from two sources: GPS and WiFi association records, on smartphones, and evaluate its performance using a dataset collected from 79 college students. Our evaluation demonstrates that our data fusion approach leads to significantly more complete data. In addition, the features extracted from the more complete data present stronger correlation with self-report depression scores, and lead to depression prediction with much higher$F_1$scores (up to 0.76 compared to 0.5 before data fusion). We further investigate the scenario when including an additional data source, i.e., the data collected from a WiFi network infrastructure. Our results show that, while this additional data source leads to even more complete data, the resultant$F_1$scores are similar to those when only using the location data (i.e., GPS and WiFi association records) from the phones.

Adaptive Bitrate (ABR) streaming is widely used in commercial video services. In this paper, we profile energy consumption of ABR streaming on mobile devices. This profiling is important, since the insights can help developing more energy-efficient ABR streaming pipelines and techniques. We first develop component power models that provide online estimation of the power draw for each component involved in ABR streaming. Using these models, we then quantify the power breakdown in ABR streaming for both regular videos and the emerging 360° panoramic videos. Our measurements validate the accuracy of the power models and provide a number of insights. We discuss use cases of the developed power models, and explore two energy reduction strategies for ABR streaming. Evaluation demonstrates that these simple strategies can provide up to 30% energy savings, with little degradation in viewing quality.

Adaptive bitrate streaming (ABR) has become the de facto technique for video streaming over the Internet. Despite a flurry of techniques, achieving high quality ABR streaming over cellular networks remains a tremendous challenge. ABR streaming can be naturally modeled as a control problem. There has been some initial work on using PID, a widely used feedback control technique, for ABR streaming. Existing studies, however, either use PID control directly without fully considering the special requirements of ABR streaming, leading to suboptimal results, or conclude that PID is not a suitable approach. In this paper, we take a fresh look at PID-based control for ABR streaming. We design a framework called PIA (PID-control based ABR streaming) that strategically leverages PID control concepts and incorporates several novel strategies to account for the various requirements of ABR streaming. We evaluate PIA using simulation based on real LTE network traces, as well as using real DASH implementation. The results demonstrate that PIA outperforms state-of-the-art schemes in providing high average bitrate with significantly lower bitrate changes (reduction up to 40 percent) and stalls (reduction up to 85 percent), while incurring very small runtime overhead. We further design PIA-E (PIA Enhanced), which improves the performance of PIA in the important initial playback phase.

Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery on duty-cycled mobile devices. Most existing studies develop integer schedules where time proceeds in discrete slots and a node is awake or asleep for an entire slot duration. We show that integer schedules can lead to significant waste of resources, and develop a generalized non-integer model, where time is continuous and a node may become awake or asleep at any point of time (subject to a few constraints) so that the resultant schedules can be significantly more efficient than integer schedules. In addition, we provide a reduction that transforms any schedule in the integer model to a corresponding schedule in the generalized non-integer model while reducing the discovery latency by up to a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. We further demonstrate the practicality of non-integer schedules in a testbed, and compare the worst-case discovery latency of several existing schemes under both integer and non-integer models. Last, we establish a family of lower bounds for the best achievable latency guarantee. These lower bounds are applicable to both integer and non-integer models, covering both symmetric and asymmetric settings, and encompassing the existing lower bounds that are only for a subset of settings as special cases.

Adaptive bitrate (ABR) streaming is the predominant approach for video streaming over the Internet. When the audio and video tracks are stored separately (i.e., in demuxed mode), the client needs to dynamically determine which audio and which video track to select for each chunk/playback position. Somewhat surprisingly, there is very little literature on how to best mesh together audio and video adaptation in ABR streaming. In this paper, we first examine the state of the art in the handling of demuxed audio and video tracks in predominant ABR protocols (DASH and HLS), as well as in real ABR client implementations in three popular players covering both browsers and mobile platforms. Combining experimental insights with code analysis, we shed light on a number of limitations in existing practices both in the protocols and the player implementations, which can cause undesirable behaviors such as stalls, selection of potentially undesirable combinations such as very low quality video with very high quality audio, etc. Based on our gained insights, we identify the underlying root causes of these issues, and propose a number of practical design best practices and principles whose collective adoption will help avoid these issues and lead to better QoE.

Streaming videos over cellular networks is highly challenging. Since cellular data is a relatively scarce resource, many video and network providers offer options for users to exercise control over the amount of data consumed by video streaming. Our study shows that existing data saving practices for Adaptive Bitrate (ABR) videos are suboptimal: they often lead to highly variable video quality and do not make the most effective use of the network bandwidth. We identify underlying causes for this and propose two novel approaches to achieve better tradeoffs between video quality and data usage. The first approach is Chunk-Based Filtering (CBF), which can be retrofitted to any existing ABR scheme. The second approach is QUality-Aware Data-efficient streaming (QUAD), a holistic rate adaptation algorithm that is designed ground up. We implement and integrate our solutions into two video player platforms (dash.js and ExoPlayer), and conduct thorough evaluations over emulated/commercial cellular networks using real videos. Our evaluations demonstrate that compared to the state of the art, the two proposed schemes achieve consistent video quality that is much closer to the user-specified target, lead to far more efficient data usage, and incur lower stalls.

Adaptive Bitrate (ABR) video streaming is widely used for over-the-top (OTT) video delivery. Recently, streaming providers have been moving towards using Variable Bitrate (VBR) encodings for the video content, spurred by the potential of improving user QoE (Quality of Experience) and reducing network bandwidth requirements compared to Constant Bitrate (CBR) encodings. However VBR introduces new challenges for ABR streaming, whose nature and implications are little understood. We explore these challenges across diverse video genres, encoding technologies, and platforms. We identify distinguishing characteristics of VBR encodings that impact user QoE and should be factored in any ABR adaptation decision. Traditional ABR adaptation strategies designed for the CBR case are not adequate for VBR. We develop novel best practice design principles to guide ABR rate adaptation for VBR encodings. As a proof of concept, we design a novel and practical control-theoretic rate adaptation scheme, CAVA (Control-theoretic Adaption for VBR-based ABR streaming), incorporating these concepts. Extensive evaluations show that CAVA substantially outperforms existing state-of-the-art adaptation techniques, validating the importance of these design principles.

Accurate cellular link bandwidth prediction can benefit upper-layer protocols significantly. In this paper, we investigate how to predict cellular link bandwidth in LTE networks. We first conduct an extensive measurement study in two major commercial LTE networks in the US, and identify five types of lower-layer information that are correlated with cellular link bandwidth. We then develop a machine learning based prediction framework, LinkForecast, that identifies the most important features (from both upper and lower layers) and uses these features to predict link bandwidth in realtime. Our evaluation shows that LinkForecast is lightweight and the prediction is highly accurate: At the time granularity of one second, the average prediction error is in the range of 3.9 to 17.0 percent for all the scenarios we explore. We further investigate the prediction performance when using lower-layer features obtained through standard APIs provided by the operating system, instead of specialized tools. Our results show that, while the features thus obtained have lower fidelity compared to those from specialized tools, they lead to similar prediction accuracy, indicating that our approach can be easily used over commercial off-the-shelf mobile devices.

Adaptive bitrate streaming (ABR) has become the de facto technique for video streaming over the Internet. Despite a flurry of techniques, achieving high quality ABR streaming over cellular networks remains a tremendous challenge. ABR streaming can be naturally modeled as a feedback control problem. There has been some initial work on using PID, a widely used feedback control technique, for ABR streaming. Existing studies, however, either use PID control directly without fully considering the special requirements of ABR streaming, leading to suboptimal results, or conclude that PID is not a suitable approach. In this paper, we take a fresh look at PID-based control for ABR streaming. We design a framework called PIA that strategically leverages PID control concepts and incorporates several novel strategies to account for the various requirements of ABR streaming. We evaluate PIA using simulation based on real LTE network traces, as well as using real DASH implementation. The results demonstrate that PIA outperforms state-of-the-art schemes in providing high average bitrate with significantly lower bitrate changes (reduction up to 40%) and stalls (reduction up to 85%), while incurring very small runtime overhead.

Smartphones, while providing users ease of access to sensitive information on the go, also present severe security risks if an attacker is able to gain access to them. To strengthen the user authentication and identification in a smartphone, we develop a biometric authentication and identification system which uses the capacitive touchscreen that is featured in all current smartphones. Our methodology focuses on using the touchscreen as a sensor to capture the image of a user's ear, thumb or four fingers. We extract the capacitive raw data from the touched body part to obtain a capacitive image, and then use it to capture geometric features (e.g., length and width of a finger) and principal components. After that, we experiment with Support Vector Machine (SVM) and Random Forest (RF) classifiers to verify and also identify each user. We achieved the maximum authentication accuracy of 98.84% by four fingers with SVM, and maxinum identification accuracy of 97.61% by four fingers with RF.

Many smartphone applications are web based and rely on cookies to maintain the status of a web session. Cookies, however, may lead to security threats since they may contain sensitive information. In addition, an attacker having access to a cookie can easily impersonate the legitimate user. In this paper, we propose and implement a system that securely outsources browser cookies to the cloud and ensures user privacy using Private Information Retrieval. Experimental evaluation using traces collected from operational cellular and WiFi networks demonstrates that our system achieves satisfactory performance for most real-life web browsing scenarios: the average latency is within 1.0 to 1.2 seconds (well within users' tolerance) even when retrieving tens of cookies over an LTE or WiFi network, and the amount of generated traffic is significantly lower than that when downloading the entire cookie database.

Wireless network traces have been widely used to understand human behaviors and provide value-added services. Sanitization based techniques have been shown to be severely lacking in protecting sensitive user information embedded in such traces. In this paper, we take an encryption based approach that provides much stronger protection of user privacy. One challenge in encrypting wireless network traces is how to encrypt time range while maintaining the utility of the traces. We propose two practical encryption techniques to support queries that involve time range. These two techniques provide much stronger security guarantee than existing order preserving encryption schemes, and present different tradeoffs in complexity, as well as storage and network bandwidth requirement. Last, we quantify the performance of the proposed approach using a smart campus prototype. The results show that our approach only leads to moderate increase in storage, network bandwidth and computation overhead, demonstrating the practicality of our approach.

Detecting node failures in mobile wireless networks is very challenging because the network topology can be highly dynamic, the network may not be always connected, and the resources are limited. In this paper, we take a probabilistic approach and propose two node failure detection schemes that systematically combine localized monitoring, location estimation and node collaboration. Extensive simulation results in both connected and disconnected networks demonstrate that our schemes achieve high failure detection rates (close to an upper bound) and low false positive rates, and incur low communication overhead. Compared to approaches that use centralized monitoring, our approach has up to 80 percent lower communication overhead, and only slightly lower detection rates and slightly higher false positive rates. In addition, our approach has the advantage that it is applicable to both connected and disconnected networks while centralized monitoring is only applicable to connected networks. Compared to other approaches that use localized monitoring, our approach has similar failure detection rates, up to 57 percent lower communication overhead and much lower false positive rates (e.g., 0.01 versus 0.27 in some settings).

Most existing studies on Delay/Disruption Tolerant Networks (DTNs) consider pair-wise node encountering that assumes nodes only meet in pairs. In many mobile wireless networks, a group of nodes, instead of only a pair of nodes, may meet each other. In this paper, we study how to effectively transmit a set of packets from a source to a destination in such group meeting scenarios. The optimization goal is to minimize the delay for the packets to reach the destination while limiting the energy consumption. We first assume that node encountering is known beforehand, and develop an algorithm to obtain the minimum delay. We then develop two practical network coding based schemes. Both schemes use a token technique to limit the total number of transmissions, and only incur signaling at the beginning of a group meeting. One scheme requires nodes in a group to exchange their encoding matrices with each other, while the other only requires exchanging rank information. Simulation results demonstrate that both schemes achieve delays close to the minimum delay for moderate number of tokens. They present different tradeoffs in the number of transmissions and the signaling overhead.

Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery between duty-cycled mobile devices. Each node is duty-cycled, i.e., its radio may only be active for a small fraction of the time. The duty cycles of the nodes can be the same or different, leading to symmetric or asymmetric cases of the neighbor discovery problem. In addition, the setting is asynchronous, i.e., clocks of different nodes may not be synchronized. Most existing studies assume an integer model (where time proceeds in discrete steps); two recent studies break away from this assumption, which allows them to develop significantly more efficient schemes. Our study improves the state-of-the-art in three main fronts. Firstly, we develop a generalized non-integer model (where time is continuous) that permits unified treatment of the assumptions in existing studies. We also provide a reduction that transforms any schedule in the basic integer model to a corresponding schedule in the generalized non-integer model while improving the performance by a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. Thirdly, we establish a new family of lower bounds for the best achievable latency guarantee in the non-integer model. They are applicable to both symmetric and asymmetric settings, and encompass the lower bounds for the integer model as special cases. Finally, we develop a novel optimal construction based on Sidon sets for the symmetric setting. Our approach differs from the approaches taken by all existing studies, and provides a new direction for constructing neighbor discovery schedules.

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow packets from multiple simultaneous transmitters to be received successfully at a receiver. Starting with a clique of n nodes, we first analyze a simple Aloha-like algorithm and show that it takes Θ((n ln n)/k) time to discover all neighbors with high probability when allowing up to k simultaneous transmissions. We then design two adaptive neighbor discovery algorithms that dynamically adjust the transmission probability for each node. We show that the adaptive algorithms yield a Θ(ln n) improvement over the Aloha-like scheme for a clique with n nodes and are thus order-optimal. Finally, we analyze our algorithms in a general multi-hop network setting. We show an upper bound of O((Δ ln n)/k) for the Aloha-like algorithm when the maximum node degree is Δ, which is at most a factor ln n worse than the optimal. In addition, when Δ is large, we show that the adaptive algorithms are orderoptimal, i.e., have a running time of O(Δ/k) which matches the lower bound for the problem.

As the world's most popular mobile operating system, Google's Android OS is the principal target of an ever increasing mobile malware threat. To counter this emerging menace, many malware detection techniques have been proposed. A key aspect of many static detection techniques is their reliance on the permissions requested in the AndroidManifest.xml file. Although these permissions are very important, the manifest also contains additional information that can be valuable in identifying malware, which, however, has not been fully utilized by existing studies. In this paper we present Manilyzer, a system that exploits the rich information in the manifest files, produces feature vectors automatically, and uses state-of-the-art machine learning algorithms to classify applications as malicious or benign. We apply Manilyzer to 617 applications (307 malicious, 310 benign) and find that it is very effective: the accuracy is up to 90%, while the false positives and false negatives are both around 10%. In addition to classifying applications, Manilyzer is used to study the trends of permission requests in malicious applications. Through this evaluation and further analysis, it is clear that malware has evolved over time, and not all malware can be detected through static analysis of manifest files. To address this issue, we briefly explore a dynamic analysis technique that monitors network traffic using a packet sniffer.

Even self-deployment is one of the best strategies to deploy mobile sensors when the region of interest is unknown and manual deployment is infeasible. A widely used distributed algorithm, Lloyd`s method, can achieve even self-deployment. It however suffers from two critical issues when being used in mobile sensor networks. First, it does not consider limited sensor communication range. Second, it does not optimize sensor movement distances, and hence can lead to excessive energy consumption, a primary concern in sensor networks. This paper first formulates a locational optimization problem that achieves even deployment while it takes account of energy consumption due to sensor movement, and then proposes two iterative algorithms. The first algorithm, named Lloyd- α, reduces the movement step sizes in Lloyd`s method. It saves traveling distance while maintaining the convergence property. However, it leads to a larger number of deployment steps. The second algorithm, named Distributed Energy-Efficient self-Deployment (DEED), reduces sensor traveling distances and requires a comparable number of deployment steps as that in Lloyd`s method. This paper further proposes an intuitive method to deal with limited sensor communication range that is applicable to all three methods. Extensive simulation using NS-2 demonstrates that DEED leads to up to 54 percent less traveling distance and 46 percent less energy consumption than Lloyd`s method.

Smart mobile handheld devices (MHDs) are being adopted at a fast speed. Compared to wireless non-handheld devices (NHDs), MHDs tend to be more mobile and can be used more opportunistically. In this paper, we study two important network usage characteristics of MHDs, namely session lengths and IP address usage, in a university campus WiFi network. Specifically, we analyze two five-week long DHCP traces collected from the network, characterize session lengths of MHDs, and develop two hyper-exponential models to capture the distribution of session lengths.We further characterize the IP address usage of MHDs, and develop two analytical models to predict the number of concurrent IP addresses that are being used by MHDs at one point of time. Goodness of fit tests indicate that our analytical models of session lengths provide good fit, and evaluation results demonstrate that the predictions from our models for IP address usage are accurate. Our results provide important insights on managing MHDs as they are being adopted rapidly in WiFi networks.

Vehicle-to-grid provides a viable approach that feeds the battery energy stored in electric vehicles (EVs) back to the power grid. Meanwhile, since EVs are mobile, the energy in EVs can be easily transported from one place to another. Based on these two observations, we introduce a novel concept called EV energy network for energy transmission and distribution using EVs. We present a concrete example to illustrate the usage of an EV energy network, and then study the optimization problem of how to deploy energy routers in an EV energy network. We prove that the problem is NP-hard and develop a greedy heuristic solution. Simulations using real-world data shows that our method is efficient.

Modern cloud-based applications (e.g., Face book, Dropbox) serve a wide range of edge clients (e.g., laptops, smart phones). The clients' characteristics vary significantly in terms of hardware (e.g., high end desktop vs. resource constrained smart phones), operating systems (e.g., Linux, Android, Mac OS, Windows), network connections (e.g., wireless vs. wired, 3G vs. 2G), and software versions (e.g., Firefox 12 vs. Firefox 13), just to name a few. Unfortunately, due to misconfiguration, outdated software, faulty hardware, or other reasons, many edge systems operate at suboptimal performance. Poor performance and root cause identification is extremely challenging for the client of the cloud system. To address this challenge, the troubleshooting service presented in this paper leverages such heterogeneity to identify and debug performance problems on edge devices. First, by looking at many runs across many different clients, the service groups clients in different clusters based on performance. Next, the service enables logging on remote clients to collect run time traces, and subsequently identifies the root cause by analyzing logs automatically. We leverage high level features such as machine/OS type along with more low level kernel level statistics such as I/O rate and system calls. To demonstrate our system we first introduce a configuration bug that was artificially injected in a recently built cluster by changing the TCP buffer size. Next, we present two real-life bugs, one I/O inefficiency bug relating to network transfers on Android, and another misconfiguration bug in VirtualBox, that were identified using our tool.

Smart mobile handheld devices (MHDs) such as smartphones have been used for a wide range of applications. Despite the recent flurry of research on various aspects of smart MHDs, little is known about their network performance in WiFi networks. In this paper, we measure the network performance of smart MHDs inside a university campus WiFi network, and identify the dominant factors that affect the network performance. Specifically, we analyze 2.9TB of data collected over three days by a monitor that is located at a gateway router of the network, and make the following findings: (1) Compared to non-handheld devices (NHDs), MHDs use well provisioned Akamai and Google servers more heavily, which boosts the overall network performance of MHDs. Furthermore, MHD flows, particularly short flows, benefit from the large initial congestion window that has been adopted by Akamai and Google servers. (2) MHDs tend to have larger local delays inside the WiFi network and are more adversely affected by the number of concurrent flows. (3) Earlier versions of Android OS (before 4.X) cannot take advantage of the large initial congestion window adopted by many servers. On the other hand, the large receive window adopted by iOS is not fully utilized by most flows, potentially leading to waste of resources. (4) Some application-level protocols cause inefficient use of network and operating system resources of MHDs in WiFi networks. Our observations provide valuable insights on content distribution, server provisioning, MHD system design, and application-level protocol design.

Faulty components in a network need to be localized and repaired to sustain the health of the network. In this paper, we propose a novel approach that carefully combines active and passive measurements to localize faults in wireless sensor networks. More specifically, we formulate a problem of optimal sequential testing guided by end-to-end data. This problem determines an optimal testing sequence of network components based on end-to-end data in sensor networks to minimize expected testing cost. We prove that this problem is NP-hard, and propose a recursive approach to solve it. This approach leads to a polynomial-time optimal algorithm for line topologies while requiring exponential running time for general topologies. We further develop two polynomial-time heuristic schemes that are applicable to general topologies. Extensive simulation shows that our heuristic schemes only require testing a very small set of network components to localize and repair all faults in the network. Our approach is superior to using active and passive measurements in isolation. It also outperforms the state-of-the-art approaches that localize and repair all faults in a network.

In this paper, we propose a classification scheme that differentiates Ethernet and WLAN TCP flows based on measurements collected passively at the edge of a network. This scheme computes two quantities, the fraction of wireless TCP flows and the degree of belief that a TCP flow traverses a WLAN inside the network, using an iterative Bayesian inference algorithm that we developed. We prove that this iterative Bayesian inference algorithm converges to the unique maximum likelihood estimate (MLE) of these two quantities. Furthermore, it has the advantage that it can handle any general K-classification problem given the marginal distributions of these classes. Numerical and experimental evaluations demonstrate that our classification scheme obtains accurate results. We apply this scheme to two sets of traces collected from two campus networks: one set collected from UMass in mid 2005 and the other collected from UConn in late 2010. Our technique infers that 4%-7% and 52%-55% of incoming TCP flows traverse an IEEE 802.11 wireless link in these two networks, respectively.

In this paper, we propose a practical scheme, Non-Binary Joint Network-Channel Coding (NB-JNCC), for reliable multi-path multi-hop communication in arbitrary large-scale wireless networks. NB-JNCC seamlessly couples channel coding and network coding to effectively combat the detrimental effect of fading of wireless channels. Specifically, NB-JNCC combines non-binary irregular low-density parity-check (LDPC) channel coding and random linear network coding through iterative joint decoding, which helps to fully exploit the spatial diversity and redundancy residing in both channel codes and network codes. In addition, since it operates over a high order Galois field, NB-JNCC can be directly combined with high order modulation without the need of any bit-to-symbol conversion nor its inverse. Through both analysis and simulation, we demonstrate the significant performance improvement of NB-JNCC over other schemes.

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow multiple packets to be received successfully at a receiver. More specifically, we design and analyze a series of randomized algorithms for neighbor discovery in MPR networks. We start with a simple Aloha-like algorithm that assumes synchronous node transmissions and the number of neighbors, n, is known. We show that the time for all the nodes to discover their respective neighbors is Θ(ln n) in an idealized MPR network that allows an arbitrary number of nodes to transmit simultaneously. In a more realistic scenario, in which no more than k nodes can transmit simultaneously, we show that the time to discover all neighbors is Θ(n ln n/k). When a node knows whether its transmission is successful or not (e.g., based on feedbacks from other nodes), we design an adaptive Aloha-like algorithm that dynamically determines the transmission probability for each node, and show that it yields a ln n improvement over the simple Aloha-like scheme. Last, we extend our schemes to take into account a number of practical considerations, such as lack of knowledge of the number of neighbors and asynchronous algorithm operation, while resulting in only a constant or log n factor slowdown in algorithm performance.

In this paper, we propose a model-based approach that uses periodic end-end probes to identify whether a “dominant congested link” exists along an end-end path. Informally, a dominant congested link refers to a link that incurs the most losses and significant queuing delays along the path. We begin by providing a formal yet intuitive definition of dominant congested link and present two simple hypothesis tests to identify whether such a link exists. We then present a novel model-based approach for dominant congested link identification that is based on interpreting probe loss as an unobserved (virtual) delay. We develop parameter inference algorithms for hidden Markov model (HMM) and Markov model with a hidden dimension (MMHD) to infer this virtual delay. Our validation using ns simulation and Internet experiments demonstrate that this approach can correctly identify a dominant congested link with only a small amount of probe data. We further provide an upper bound on the maximum queuing delay of the dominant congested link once we identify that such a link exists.

Monitoring the health of a sensor network is important for maintaining the health and normal operation of the network. For large-scale cost- effective monitoring, using inexpensive motes as sniffers is an attractive choice. In this paper, we quantify the capability and fidelity of mote-class sniffers for sensor network monitoring. In particular, we experimentally quantify the sustainable workload and the accuracy of delay and loss measurements by these types of sniffers. We find that (1) a sniffer can monitor traffic at the rate of 60 packets per second with little buffer overflow, (2) per-hop loss measurements from sniffers exhibit variations but are comparable to those at the receiver and (3) per-hop delay measurements from a sniffer are accurate (the errors are up to 300 μs). Our results indicate that measurement quality by mote-class sniffers is satisfactory for many monitoring purposes.

One challenge in delay tolerant networks (DTNs) is efficient routing, as the lack of contemporaneous end-to-end paths makes conventional routing schemes inapplicable. Many existing DTN routing protocols adopt multi-copy replication and/or are incognizant of mobility models. Hence they are not suitable for networks with extremely stringent resources and time-varying mobility models such as underwater sensor networks. In this paper, we propose a generic prediction assisted single-copy routing (PASR) scheme that can be instantiated for different mobility models in underwater sensor networks. PASR employs an effective greedy algorithm which captures the features of network mobility patterns, and provides guidance on how to use historical information. We demonstrate the superior performance of PASR through simulation.

In this paper, we propose a practical scheme, called Non-Binary Joint Network-Channel Decoding (NB-JNCD) for reliable communication in wireless networks. It seamlessly couples channel coding and network coding, and can effectively combat the detrimental effect of fading of wireless channels, especially in large networks. On a high order Galois field, NB-JNCD combines non-binary LDPC channel coding and random linear network coding through iterative joint decoding, which helps fully exploit the spatial diversity and redundancy residing in both codes. Furthermore, the scheme can unify non-binary source coding and high order modulation without the need of any bit-to-symbol conversion and its inverse. Through analysis and simulation, we demonstrate the significant performance improvement of NB-JNCD against other schemes.

Faulty components in a network need to be localized and repaired to sustain the health of the network. In this paper, we propose a novel approach that carefully combines active and passive measurements to localize faults in wireless sensor networks. More specifically, we formulate a problem of optimal sequential testing guided by end-to-end data. This problem determines an optimal testing sequence of network components based on end-to-end data in sensor networks to minimize testing cost. We prove that this problem is NP-hard and propose a greedy algorithm to solve it. Extensive simulation shows that in most settings our algorithm only requires testing a very small set of network components to localize and repair all faults in the network. Our approach is superior to using active and passive measurements in isolation. It also outperforms the state-of-the-art approaches that localize and repair all faults in a network.

In this paper, we propose two online algorithms to detect 802.11 traffic from packet-header data collected passively at a monitoring point. These algorithms have a number of applications in real-time wireless LAN management, for instance, in detecting unauthorized access points and detecting/predicting performance degradations. Both algorithms use sequential hypothesis tests and exploit fundamental properties of the 802.11 CSMA/CA MAC protocol and the half-duplex nature of wireless channels. They differ in that one requires training sets, while the other does not. We have built a system for online wireless traffic detection using these algorithms and deployed it at a university gateway router. Extensive experiments have demonstrated the effectiveness of our approach: the algorithm that requires training provides rapid detection and is extremely accurate (the detection is mostly within 10 seconds, with very low false-positive and false-negative ratios), the algorithm that does not require training detects 60 percent to 76 percent of the wireless hosts without any false positives, and both algorithms are lightweight, with computation and storage overhead well within the capability of commodity equipment.

Motivated by the wide use of TCP for multimedia streaming in practice and the increasing availability of multipath between end hosts, we study multipath live streaming via TCP in this article. We first design a simple and practical TCP-based multipath streaming scheme, named Dynamic MPath-streaming (DMP-streaming) , which dynamically distributes packets over multiple paths by implicitly inferring the available bandwidths on these paths. To allow systematic performance study, we develop an analytical model for DMP-streaming and validate the model using extensive ns simulation and Internet experiments. We explore the parameter space of this model and find that DMP-streaming generally provides satisfactory performance when the aggregate achievable TCP throughput is 1.6 times the video bitrate, when allowing a few seconds of startup delay. Last, we comment on the benefits of using multipath versus single path for TCP-based streaming.

TCP is widely used in commercial multimedia streaming systems, with recent measurement studies indicating that a significant fraction of Internet streaming media is currently delivered over HTTP/TCP. These observations motivate us to develop analytic performance models to systematically investigate the performance of TCP for both live and stored-media streaming. We validate our models via ns simulations and experiments conducted over the Internet. Our models provide guidelines indicating the circumstances under which TCP streaming leads to satisfactory performance, showing, for example, that TCP generally provides good streaming performance when the achievable TCP throughput is roughly twice the media bitrate, with only a few seconds of startup delay.

Motivated by the wide use of TCP for streaming in practice and the increasing availability of multipath between end hosts, we study multipath live streaming via TCP in this paper. We first design a simple and practical TCP-based multipath streaming scheme, named Dynamic MPath-streaming (DMP-streaming), which dynamically distributes packets over multiple paths by implicitly inferring the available bandwidths on these paths. To allow systematic performance study, we develop an analytical model for DMP-streaming and validate the model using extensive ns simulation and Internet experiments. We explore the parameter space of this model and find that DMP-streaming generally provides satisfactory performance when the aggregate achievable TCP throughput is 1.6 times the video bitrate, with a few seconds of startup delay. Last, we comment on the benefits of using multipath versus single path for TCP-based streaming.

Lossy links used in a sensor network affect network performance, and hence need to be detected and repaired [1, 2]. One approach to detect lossy links is that each node monitors the loss rates on its neighboring links and reports them to the sink. This approach, although straightforward, causes large amount of traffic. Another approach to detect lossy links is through end-to-end data that are transmitted periodically from sources to the sink(s) [3, 1, 2]. This end-to-end approach has the advantage of not generating any additional monitoring traffic. The challenge is, however, to develop accurate inference algorithms for lossy link detection based on end-to-end measurements.

Infrastructure-based overlay networks have been proposed to support the quality of service requirements of a wide range of applications. In this paper, we study using infrastructure-based overlay for delay-sensitive low-bandwidth group communications, such as teleconferencing and chat room. In particular, we study where to place overlay nodes (called proxies) to minimize end-to-end delays. We formulate the problem of optimal proxy placement using integer-linear programming and quantify the benefits from using proxies in six real-world networks. We And that, perhaps surprisingly, only two out of the six networks benefit from using proxies. We furthermore use network characteristics to explain these benefits or lack of benefits. Last, for the two networks which benefit from using proxies, we find that a small number proxies (2 to 3) are sufficient to realize most of the performance gains.

Rogue (unauthorized) wireless access points pose serious security threats to local networks. In this paper, we propose two online algorithms to detect rogue access points using sequential hypothesis tests applied to packet-header data collected passively at a monitoring point. One algorithm requires training sets, while the other does not. Both algorithms extend our earlier TCP ACK-pair technique to differentiate wired and wireless LAN TCP traffic, and exploit the fundamental properties of the 802.11 CSMA/CA MAC protocol and the half duplex nature of wireless channels. Our algorithms make prompt decisions as TCP ACK-pairs are observed, and only incur minimum computation and storage overhead. We have built a system for online rogue-access-point detection using these algorithms and deployed it at a university gateway router. Extensive experiments in various scenarios have demonstrated the excellent performance of our approach: the algorithm that requires training provides rapid detection and is extremely accurate (the detection is mostly within 10 seconds, with very low false positive and false negative ratios); the algorithm that does not require training detects 60%-76% of the wireless hosts without any false positives; both algorithms are light-weight (with computation and storage overhead well within the capability of commodity equipment).

Ethernet, wireless LAN, ADSL, cable modem and dialup are common access networks, but have dramatically different characteristics. Fast and accurate classification of access network type can improve protocol or application performance significantly. In this paper, we propose a simple and efficient end-end scheme to classify the type of an access network into three categories: Ethernet, wireless LAN and low-bandwidth connection. Our scheme is based on the intrinsic characteristics of the various access networks and utilizes the median and entropy of packet pair inter-arrival times. Extensive experiments show that our scheme obtains accurate classification results in a very short time (10 to 100 seconds).

TCP is widely used in commercial media streaming systems, with recent measurement studies indicating that a significant fraction of Internet streaming media is currently delivered over HTTP/TCP. These observations motivate us to develop analytic performance models to systematically investigate the performance of TCP for both live and stored media streaming. We validate our models via ns simulations and experiments conducted over the Internet. Our models provide guidelines indicating the circumstances under which TCP streaming leads to satisfactory performance, showing, for example, that TCP generally provides good streaming performance when the achievable TCP throughput is roughly twice the media bitrate, with only a few seconds of startup delay.

We present the design, implementation, and performance evaluation of AMPS --- a flexible, scalable proxy testbed that supports a wide and extensible set of next-generation proxy streaming services. AMPS employs a modular architecture and is built on top of a commodity Linux system. We study the performance of AMPS proxy using a server-proxy-client configuration in a switched-Gigabit LAN environment. We identify the CPU to be the system bottleneck. Through profiling study, we further identify the kernel network protocol processing and the Network Reception Module inside the proxy to be the most CPU-intensive components. We also quantify the maximum achievable throughput for two of the principal components of the proxy - the control plane and data plane, and characterize the end-to-end performance along the server-to-proxy-to-client path. We discuss lessons learned and the various optimizations made in the course of our study to improve system performance.

Low priority data transfer across the wide area is useful in several contexts, for example for the dissemination of large files such as OS updates, content distribution or prefetching. Although the design of such a service is reasonably easy when the underlying network supports service differentiation, it becomes more challenging without such network support. We describe an application level approach to designing a low priority service -- one that is 'lower than best-effort' in the context of the current Internet. We require neither network support nor changes to TCP. Instead, we use a receive window control to limit the transfer rate of the application, and the optimal rate is determined by detecting a change-point. We motivate this joint control-estimation problem by considering a fluid-based optimisation framework, and describe practical solutions, based on stochastic approximation and binary search techniques. Simulation results demonstrate the effectiveness of the approach.

TCP is widely used in commercial media streaming systems, with recent measurement studies indicating that a significant fraction of Internet streaming media is currently delivered over HTTP/TCP. These observations motivate us to develop analytic performance models to systematically investigate the performance of TCP for both live and stored media streaming. We validate our models via ns simulations and experiments conducted over the Internet. Our models provide guidelines indicating the circumstances under which TCP streaming leads to satisfactory performance, showing, for example, that TCP generally provides good streaming performance when the achievable TCP throughput is roughly twice the media bitrate, with only a few seconds of startup delay.

We address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional server-based reactive transmission schemes such as hatching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache size, and availability of unicast versus multicast capability, on the resulting transmission cost. Our evaluations show that even a relatively small prefix cache (10%-20% of the video repository) is sufficient to realize substantial savings in transmission cost. We find that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in a predominantly unicast environment such as the Internet.

In this paper, we study streaming multiple videos from a remote server to asynchronous clients through a group of proxies, using multicast on both the wide area server-proxy paths and the local area proxy-client paths. In this setting, we present an algorithm to determine the optimal cache allocation among videos at each proxy and develop an efficient streaming video distribution scheme. Our evaluations show the benefits of even a small proxy cache and quantify the gains from using multicast on the server-proxy paths.

In this paper, we propose a model-based approach that uses periodic end-end probes to identify whether a "dominant congested link" exists along an end-end path. Informally, a dominant congested link refers to a link that incurs the most losses and significant queuing delays along the path. We begin by providing a formal yet intuitive definition of dominant congested link and present two simple hypothesis tests to identify whether such a link exists. We then present and examine several novel model-based approaches for identifying a dominant congested link that are based on interpreting probe loss as an unobserved (virtual) delay. We develop parameter inference algorithms for Hidden Markov Model (HMM) and Markov model with a hidden dimension to infer this virtual delay. Our validation using ns simulation and live Internet experiments demonstrate that this approach can correctly identify a dominant congested link with only a small amount of probe data. We further estimate the maximum queuing delay of the dominant congested link, once we identify that a dominant congested link exists.

In this paper, we address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We develop a technique to analytically determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional server-based reactive transmission schemes such as batching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache size, and availability of unicast versus multicast capability, on the resultant transmission cost.. Our evaluations show that even a relatively small prefix cache (10%-20% of the video repository) is sufficient to realize substantial savings in transmission cost. We find that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in predominantly unicast environments such as the Internet.

Multimedia streaming applications can consume a significant amount of server and network resources. Periodic broadcast and patching are two approaches that use multicast transmission and client buffering in innovative ways to reduce server and network load, while at the same time allowing asynchronous access to multimedia steams by a large number of clients. Current research in this area has focussed primarily on the algorithmic aspects of these approaches, with evaluation performed via analysis or simulation. In this paper, we describe the design and implementation of a flexible streaming video server and client testbed that implements both periodic broadcast and patching, and explore the issues that arise when implementing these algorithms. We present measurements detailing the overheads associated with the various server components (signaling, transmission schedule computation, data retrieval and transmission), the interactions between the various components of the architecture, and the overall end-to-end performance. We also discuss the importance of an appropriate server video segment caching policy. We conclude with a discussion of the insights gained from our implementation and experimental evaluation.

No abstract available.