The cellular network has undergone rapid progress since its inception in 1980s. While rapid iteration of newer generations of cellular technology plays a key role in this evolution, the incremental and eventually wide deployment of every new technology generation also plays a vital role in delivering the promised performance improvement. In this work, we conduct the first metamorphosis study of a cellular network generation, 5G, by measuring the user-experienced 5G performance from 5G network's birth (initial deployment) to maturity (steady state). By analyzing a 4-year 5G performance trace of 2.65M+ Ookla® ~Speedtest Intelligence® ~measurements collected in 9 cities in the United States and Europe from January 2020 to December 2023, we unveil the detailed evolution of 5G coverage, throughput, and latency at the quarterly granularity, compare the performance diversity across the 9 representative cities, and gain insights into compounding factors that affect user-experienced 5G performance, such as adoption of 5G devices and the load on the 5G network. Our study uncovers the typical life-cycle of a new cellular technology generation as it undergoes its ''growing pain'' towards delivering its promised QoE over the previous technology generation.

In 2022, 3 years after the initial 5G rollout, through a cross-country US driving trip (from Los Angeles to Boston), the authors of [28] conducted an in-depth measurement study of user-perceived experience (network coverage, performance, and QoE of a set of major 5G ''killer'' apps) over all three major US carriers. The study revealed disappointingly low 5G coverage and suboptimal network performance -- falling short of the expectations needed to support the new generation of 5G ''killer apps. Now, five years into the 5G era, widely considered its midlife, 5G networks are expected to deliver stable and mature performance. In this work, we replicate the 2022 study along the same coast-to-coast route, evaluating the current state of cellular coverage and network and application performance across all three major US operators. While we observe a substantial increase in 5G coverage and a corresponding boost in network performance, two out of three operators still exhibit less than 50% 5G coverage along the driving route even five years after the initial 5G rollout. We expand the scope of the previous work by analyzing key lower-layer KPIs that directly influence the network performance. Finally, we introduce a head-to-head comparison with Starlink's LEO satellite network to assess whether emerging non-terrestrial networks (NTNs) can complement the terrestrial cellular infrastructure in the next generation of wireless connectivity.

Despite 5G’s promise of enhanced capacity and lower latency, recent measurement studies have shown that users experience significant cellular performance degradation under vehicular mobility. In this paper, we go beyond prior work that merely characterizes 5G performance, by uncovering the underlying mechanisms responsible for throughput degradation episodes during vehicular mobility. Through extensive measurements across 3,687 km of driving routes in the U.S., we collect granular performance and network KPI data from three major carriers across diverse radio access technologies. We introduce a novel KPI-driven clustering methodology that not only quantifies the frequency and duration of performance degradations, but also critically identifies their root causes by analyzing KPIs and their interactions. Our analysis reveals previously unidentified patterns: persistent higher degradation rates in uplink versus downlink, technology-specific vulnerability signatures in LTE and 5G deployments, and the predominance of compound degradation mechanisms where multiple factors interact to create severe throughput reductions. These findings provide essential information for developing mobility-aware resource management strategies to address the unique challenges of vehicular connectivity.

After a rapid deployment worldwide over the past few years, 5G is expected to have reached a mature deployment stage to provide measurable improvement of network performance and user experience over its predecessors. In this study, we aim to assess 5G deployment maturity via three conditions: (1) Does 5G performance remain stable over a long time span (1 year)? (2) Does 5G provide better performance than its predecessor Long-Term Evolution (LTE)? (3) Does the technology offer similar performance across diverse geographic areas and cellular operators? We answer this important question by conducting two year-long measurement campaigns of 5G uplink performance leveraging a custom Android app: one crowd-sourced, cross-sectional campaign spanning 8 major cities in 7 countries and two different continents (Europe and North America), and one controlled campaign focusing on mmWave deployment at a fixed location in the downtown area of Boston, MA. Our datasets show that 5G deployment in major cities appears to have matured, with no major performance improvements observed over a one-year period, but 5G does not provide consistent, superior measurable performance over LTE, especially in terms of latency, and further there exists clear uneven 5G performance across the 8 cities. Our study suggests that, while 5G deployment appears to have stagnated, it is short of delivering its promised performance and user experience gain over its predecessor.

In Video Analytics Pipelines (VAP), Analytics Units (AUs) such as object detection and face recognition operating on remote servers rely heavily on surveillance cameras to capture high-quality video streams to achieve high accuracy. Modern network cameras offer an array of parameters that directly influence video quality. While a few of such parameters, e.g., exposure, focus and white balance, are automatically adjusted by the camera internally, the others are not. We denote such camera parameters as non-automated (NAUTO) parameters. In this work, we first show that in a typical surveillance camera deployment, environmental condition changes can have significant adverse effect on the accuracy of insights from the AUs, but such adverse impact can potentially be mitigated by dynamically adjusting NAUTO camera parameters in response to changes in environmental conditions. Second, since most end-users lack the skill or understanding to appropriately configure these parameters and typically use a fixed parameter setting, we presentCamTuner, to our knowledge, the first framework that dynamically adapts NAUTO camera parameters to optimize the accuracy of AUs in a VAP in response to adverse changes in environmental conditions.CamTuneris based on SARSA reinforcement learning and it incorporates two novel components: a light-weight analytics quality estimator and a virtual camera that drastically speed up offline RL training. Our controlled experiments and real-world VAP deployment show that compared to a VAP using the default camera setting,CamTunerenhances VAP accuracy by detecting 15.9% additional persons and 2.6% –4.2% additional cars (without any false positives) in a large enterprise parking lot.CamTuneropens up new avenues for elevating video analytics accuracy, transcending mere incremental enhancements achieved through refining deep-learning models.

With rapid evolution of mobile core network (MCN) architectures, large-scale control-plane traffic (CPT) traces are critical to studying MCN design and performance optimization by the R&D community. The prior-art control-plane traffic generator SMM heavily relies on domain knowledge which requires re-design as the domain evolves. In this work, we study the feasibility of developing a high-fidelity MCN control plane traffic generator by leveraging generative ML models. We identify key challenges in synthesizing high-fidelity CPT including generic (to data-plane) requirements such as multimodality feature relationships and unique requirements such as stateful semantics and long-term (time-of-day) data variations. We show state-of-the-art, generative adversarial network (GAN)-based approaches shown to work well for data-plane traffic cannot meet these fidelity requirements of CPT, and develop a transformer-based model, CPT-GPT, that accurately captures complex dependencies among the samples in each traffic stream (control events by the same UE) without the need for GAN. Our evaluation of CPT-GPT on a large-scale control-plane traffic trace shows that (1) it does not rely on domain knowledge yet synthesizes control-plane traffic with comparable fidelity as SMM; (2) compared to the prior-art GAN-based approach, it reduces the fraction of streams that violate stateful semantics by two orders of magnitude, the max y-distance of sojourn time distributions of streams by 16.0%, and the transfer learning time in deriving new hourly models by 3.36×.

The rise of machine learning workload on smart-phones has propelled GPUs into one of the most power hungry components of modern smartphones. Optimizing the power consumption of mobile GPUs in turn requires accurate estimation of their power draw during app execution. We observe that the prior-art, utilization-frequency based GPU models cannot capture the diverse micro-architectural usage of modern mobile GPUs, and study whether performance monitoring counter (PMC)-based models recently proposed for desktop/server GPUs can be applied to accurately model mobile GPU power. Our study shows that the PMCs that come with dominating mobile GPUs used in modern smartphones are sufficient to model mobile GPU power, but exhibit multicollinearity if used altogether. We present APGPM, the first mobile GPU power modeling methodology that automatically selects an optimal set of PMCs that maximizes the GPU power model accuracy. Evaluation on the two representative mobile GPUs shows that APGPM-generated GPU power models reduce the MAPE modeling error of prior-art by 11.3% to 15.4% while using only 4.66% to 20.41 % of the total number of available PMCs.

With faster wireless networks and server GPUs, offloading high-accuracy but compute-intensive AR tasks implemented in Deep Neural Networks (DNNs) to edge servers offers a promising way to support high-QoE Augmented/Mixed Reality (AR/MR) applications. A cost-effective way for AR app vendors to deploy such edge-assisted AR apps to support a large user base is to use commercial Machine-Learning-as-a-Service (MLaaS) deployed at the edge cloud. To maximize cost-effectiveness, such an MLaaS provider faces a key design challenge, i.e., how to maximize the number of clients concurrently served by each GPU server in its cluster while meeting per-client AR task accuracy SLAs. The above AR offloading inference serving problem differs from generic inference serving or video analytics serving in one fundamental way: due to the use of local tracking which reuses the last server-returned inference result to derive results for the current frame, the offloading frequency and end-to-end latency of each AR client directly affect its AR task accuracy (for all the frames).

After 4 years of rapid deployment in the US, 5G is expected to have significantly improved the performance and overall user experience of mobile networks. However, recent measurement studies have focused either on static performance or a single aspect (e.g., handovers) under driving conditions of 5G, and do not provide a complete picture of cellular network performance today under driving conditions - a major use case of mobile networks. Through a cross-continental US driving trip (from LA to Boston, 5700km+), we conduct an in-depth measurement study of user-perceived experience (network coverage/performance and QoE of a set of major latency-critical 5G "killer'' apps) To understand the root cause of the observed network performance, while collecting low-level 5G statistics and signaling messages. Our study shows disappointingly low coverage of 5G networks today under driving and highly fragmented coverage by cellular technologies. More importantly, network and application performance are often poor under driving even in areas with full 5G coverage. We also examine the correlation of technology-wise coverage and performance with geo-location and the vehicle's speed and analyze the impact of a number of lower layer KPIs on network performance.

With 5G deployment gaining momentum, the control-plane traffic volume of cellular networks is escalating. Such rapid traffic growth motivates the need to study the mobile core network (MCN) control-plane design and performance optimization. Doing so requires realistic, large control-plane traffic traces in order to profile and debug the mobile network performance under real workload. However, large-scale control-plane traffic traces are not made available to the public by mobile operators due to business and privacy concerns. As such, it is critically important to develop accurate, scalable, versatile, and open-to-innovation control traffic generators, which in turn critically rely on an accurate traffic model for the control plane. Developing an accurate model of control-plane traffic faces several challenges: (1) how to capture the dependence among the control events generated by each User Equipment (UE), (2) how to model the inter-arrival time and sojourn time of control events of individual UEs, and (3) how to capture the diversity of control-plane traffic across UEs. We present a novel two-level hierarchical state-machine-based control-plane traffic model. We further show how our model can be easily adjusted from LTE to NextG networks (e.g., 5G) to support modeling future control-plane traffic. We experimentally validate that the proposed model can generate large realistic control-plane traffic traces. We have open-sourced our traffic generator to the public to foster MCN research.

For its stringent QoE requirement, augmented reality (AR) has been widely hailed as a representative of ultra-high bandwidth and ultra-low latency apps that will be enabled by 5G networks/edge clouds. Such a portrait of AR by the telco and cloud industry raises an important research question - can 5G enable latency-critical applications such as (edge-assisted) AR? In this paper, we conduct to our knowledge the first in-depth measurement study of whether 5G mmWave in combination with in-network edge cloud can support the baseline edge-assisted object detection. After we discover 5G mmWave is unlikely to achieve the level of uplink network performance needed to support a baseline edge-assisted object detection implementation in the near future, we quantify the performance benefits in retrofitting app-level optimizations developed in the pre-5G era on top of baseline edge-assisted object detection, as well as the performance benefits from hardware upgrade on the edge. We find that these optimizations can significantly boost object detection performance over both LTE and 5G mmWave; however, the improvement with 5G mmWave over LTE is marginal, and 5G mmWave still fails to provide satisfactory performance in all scenarios under consideration. Overall, we conclude that today's 5G mmWave deployment is not a deciding factor in enabling edge-assisted object detection.

Immersive applications such as Augmented Reality (AR) and Mixed Reality (MR) often need to perform multiple latency-critical tasks on every frame captured by the camera, which all require results to be available within the current frame interval. While such tasks are increasingly supported by Deep Neural Networks (DNNs) offloaded to edge servers due to their high accuracy but heavy computation, prior work has largely focused on offloading one task at a time. Compared to offloading a single task, where more frequent offloading directly translates into higher task accuracy, offloading of multiple tasks competes for shared edge server resources, and hence faces the additional challenge of balancing the offloading frequencies of different tasks to maximize the overall accuracy and hence app QoE.

Augmented Reality (AR) devices are set apart from other mobile devices by the immersive experience they offer. While the powerful suite of sensors on modern AR devices is necessary for enabling such an immersive experience, they can create unease in bystanders (i.e., those surrounding the device during its use) due to potential bystander data leaks, which is called the bystander privacy problem. In this paper, we propose BystandAR, the first practical system that can effectively protect bystander visual (camera and depth) data in real-time with only on-device processing. BystandAR builds on a key insight that the device user's eye gaze and voice are highly effective indicators for subject/bystander detection in interpersonal interaction, and leverages novel AR capabilities such as eye gaze tracking, wearer-focused microphone, and spatial awareness to achieve a usable frame rate without offloading sensitive information. Through a 16-participant user study,we show that BystandAR correctly identifies and protects 98.14% of bystanders while allowing access to 96.27% of subjects. We accomplish this with average frame rates of 52.6 frames per second without the need to offload unprotected bystander data to another device.

Augmented Reality (AR) devices are set apart from other mobile devices by the immersive experience they offer. While the powerful suite of sensors on modern AR devices is necessary for enabling such an immersive experience, they can create unease in bystanders (i.e., those surrounding the device during its use) due to potential bystander data leaks, which is called the bystander privacy problem. In this poster, we propose BystandAR, the first practical system that can effectively protect bystander visual (camera and depth) data in real-time with only on-device processing. BystandAR builds on a key insight that the device user's eye gaze and voice are highly effective indicators for subject/bystander detection in interpersonal interaction, and leverages novel AR capabilities such as eye gaze tracking, wearer-focused microphone, and spatial awareness to achieve a usable frame rate without offloading sensitive information. Through a 16-participant user study, we show that BystandAR correctly identifies and protects 98.14% of bystanders while allowing access to 96.27% of subjects. We accomplish this with average frame rates of 52.6 frames per second without the need to offload unprotected bystander data to another device.

IoT sensors, especially video cameras, are ubiquitously deployed around the world to perform a variety of computer vision tasks in several verticals including retail, health-care, safety and security, transportation, manufacturing, etc. To amortize their high deployment effort and cost, it is desirable to perform multiple video analytics tasks, which we refer to as Analytical Units (AUs), off the video feed coming out of every camera. As AUs typically use deep-learning based AI/ML models, their performances depend on the quality of the input video. The most recent work has shown that dynamically adjusting the camera setting exposed by popular network cameras can help improve the quality of the video feed and hence the AU accuracy, in a single AU setting. In this paper, we first show that in a multi-AU setting, changing the camera setting has disproportionate impact on different AUs performance. In particular, the optimal setting for one AU may severely degrade the performance for another AU, and further, the impact on different AUs varies as the environmental condition changes. We then present Elixir, a system to enhance the video stream quality for multiple analytics on a video stream. Elixir leverages Multi-Objective Reinforcement Learning (MORL), where the RL agent caters to the objectives from different AUs and adjusts the camera setting to simultaneously enhance the performance of all AUs. To define the multiple objectives in MORL, we develop new AU-specific quality estimator values for each individual AU. We evaluate Elixir through real-world experiments on a testbed with three cameras deployed next to each other (overlooking a large enterprise parking lot) running Elixir and two baseline approaches, respectively. Elixir correctly detects 7.1% (22,068) and 5.0% (15,731) more cars, 94% (551) and 72% (478) more faces, and 670.4% (4975) and 158.6% (3507) more persons than the default-setting and time-sharing approaches, respectively. It also detects 115 license plates, far more than the time-sharing approach (7) and the default setting (0).

The ability to accurately estimate job runtime properties allows a scheduler to effectively schedule jobs. State-of-the-art online cluster job schedulers use history-based learning, which uses past job execution information to estimate the runtime properties of newly arrived jobs. However, with fast-paced development in cluster technology (in both hardware and software) and changing user inputs, job runtime properties can change over time, which lead to inaccurate predictions. In this paper, we explore the potential and limitation of real-time learning of job runtime properties, by proactively sampling and scheduling a small fraction of the tasks of each job. Such a task-sampling-based approach exploits the similarity among runtime properties of the tasks of the same job and is inherently immune to changing job behavior. Our analytical and experimental analysis of 3 production traces with different skew and job distribution shows that learning in space can be substantially more accurate. Our simulation and testbed evaluation on Azure of the two learning approaches anchored in a generic job scheduler using 3 production cluster job traces shows that despite its online overhead, learning in space reduces the average Job Completion Time (JCT) by 1.28×, 1.56×, and 1.32× compared to the prior-art history-based predictor.

Millions of cameras at the edge are being deployed to power a variety of different deep learning applications. However, the frames captured by these cameras are not always pristine—they can be distorted due to lighting issues, sensor noise, compression etc. Such distortions not only deteriorate visual quality, they impact the accuracy of deep learning applications that process such video streams. In this work, we introduce AQuA, to protect application accuracy against such distorted frames by scoring the level of distortion in the frames. It takes into account the analytical quality of frames, not the visual quality, by learning a novel metric, classifier opinion score , and uses a lightweight, CNN-based, object-independent feature extractor. AQuA accurately scores distortion levels of frames and generalizes to multiple different deep learning applications. When used for filtering poor-quality frames at edge, it reduces high-confidence errors for analytics applications by 17%. Through filtering, and due to its low overhead (14 ms), AQuA can also reduce computation time and average bandwidth usage by 25%. Finally, we discuss numerous new avenues of optimizations of video analytics pipelines enabled by AQuA.

5G networks are being deployed rapidly across the world and have opened door to many uplink-oriented, bandwidth-intensive applications such as Augmented Reality and Connected Autonomous Vehicles. However, the roll-out is still in the early phase and the nature of deployment also varies across different geographic regions of the world. In this demo, we present NextG-UP, an Android-based tool designed to help understand the performance and evolution of 5G networks around the world. The crowd-sourcing mobile app collects various cellular network metrics and runs a short uplink throughput/latency test.

5G networks are being deployed rapidly across the world and have opened door to many uplink-oriented, bandwidth-intensive applications such as Augmented Reality and Connected Autonomous Vehicles (CAV). However, the roll-out is still in the early phase and the nature of deployment also varies across different geographic regions of the world. In this demo, we present NextG-UP, an open-source Android-based tool designed to help understand the performance and evolution of 5G networks around the world. The crowd-sourcing mobile app collects various cellular network metrics and runs a short uplink throughput/latency test.

In Video Analytics Pipelines (VAP), Analytics Units (AUs) such as object detection and face recognition running on remote servers critically rely on surveillance cameras to capture high-quality video streams in order to achieve high accuracy. Modern IP cameras come with a large number of camera parameters that directly affect the quality of the video stream capture. While a few of such parameters, e.g., exposure, focus, white balance are automatically adjusted by the camera internally, the remaining ones are not. We denote such camera parameters as non-automated (NAUTO) parameters. In this paper, we first show that environmental condition changes can have significant adverse effect on the accuracy of insights from the AUs, but such adverse impact can potentially be mitigated by dynamically adjusting NAUTO camera parameters in response to changes in environmental conditions. We then present CamTuner, to our knowledge, the first framework that dynamically adapts NAUTO camera parameters to optimize the accuracy of AUs in a VAP in response to adverse changes in environmental conditions. CamTuner is based on SARSA reinforcement learning and it incorporates two novel components: a light-weight analytics quality estimator and a virtual camera that drastically speed up offline RL training. Our controlled experiments and real-world VAP deployment show that compared to a VAP using the default camera setting, CamTuner enhances VAP accuracy by detecting 15.9% additional persons and 2.6%--4.2% additional cars (without any false positives) in a large enterprise parking lot and 9.7% additional cars in a 5G smart traffic intersection scenario, which enables a new usecase of accurate and reliable automatic vehicle collision prediction (AVCP). CamTuner opens doors for new ways to significantly enhance video analytics accuracy beyond incremental improvements from refining deep-learning models.

Improving software performance through configuration parameter tuning is a common activity during software maintenance. Beyond traditional performance metrics like latency, mobile app developers are interested in reducing app energy usage. Some mobile apps have centralized locations for parameter tuning, similar to databases and operating systems, but it is common for mobile apps to have hundreds of parameters scattered around the source code. The correlation between these “deep” parameters and app energy usage is unclear. Researchers have studied the energy effects of deep parameters in specific modules, but we lack a systematic understanding of the energy impact of mobile deep parameters. In this paper we empirically investigate this topic, combining a developer survey with systematic energy measurements. Our motivational survey of 25 Android developers suggests that developers do not understand, and largely ignore, the energy impact of deep parameters. To assess the potential implications of this practice, we propose a deep parameter energy profiling framework that can analyze the energy impact of deep parameters in an app. Our framework identifies deep parameters, mutates them based on our parameter value selection scheme, and performs reliable energy impact analysis. Applying the framework to 16 popular Android apps, we discovered that deep parameter-induced energy inefficiency is rare. We found only 2 out of 1644 deep parameters for which a different value would significantly improve its app's energy efficiency. A detailed analysis found that most deep parameters have either no energy impact, limited energy impact, or an energy impact only under extreme values. Our study suggests that it is generally safe for developers to ignore the energy impact when choosing deep parameter values in mobile apps.

Coflow scheduling improves data-intensive application performance by improving their networking performance. State-of-the-art online coflow schedulers in essence approximate the classic Shortest-Job-First (SJF) scheduling by learning the coflowsizeonline. In particular, they use multiple priority queues to simultaneously accomplish two goals: to sieve long coflows from short coflows, and to schedule short coflows with high priorities. Such a mechanism pays high overhead in learning the coflow size: moving a large coflow across the queues delays small and other large coflows, and moving similar-sized coflows across the queues results in inadvertent round-robin scheduling. We propose Philae, a new online coflow scheduler that exploits the spatial dimension of coflows,i.e.,a coflow has many flows, to drastically reduce the overhead of coflow sizelearning. Philae pre-schedules sampled flows of each coflow and uses their sizes to estimate the average flow size of the coflow. It then resorts to Shortest Coflow First, where the notion of shortest is determined using the learned coflow sizes and coflow contention. We show that the sampling-based learning is robust to flow size skew and has the added benefit of much improved scalability from reduced coordinator-local agent interactions. Our evaluation using an Azure testbed, a publicly available production cluster trace from Facebook shows that compared to the prior art Aalo, Philae reduces the coflow completion time (CCT) in average (P90) cases by$1.50\times $($8.00\times $) on a 150-node testbed and$2.72\times $($9.78\times $) on a 900-node testbed. Evaluation using additional traces further demonstrates Philae’s robustness to flow size skew.

In this paper, we report on our 6-year experience developing Eagle Tester (eTester for short) - a mobile battery drain testing and diagnostic tool. We show how eTester evolved from an "academic" prototype to a fully automated tool usable by the mobile industry.

By omitting external lighting, OLED display significantly reduces the power draw compared to its predecessor LCD and has gained wide adoption in modern smartphones. The real potential of OLED in saving phone battery drain lies in exploiting app UI color design, i.e., how to design app UI to use pixel colors that result in low OLED display power draw. In this paper, we design and implement an accurate per-frame OLED display power profiler, PFOP, that helps developers to gain insight into the impact of different app UI design on its OLED power draw, and an enhanced Android Battery that helps phone users to understand and manage phone display energy drain, for example, from different app and display configurations such as dark mode and screen brightness. A major challenge in designing both tools is to develop an accurate and robust OLED display power model. We experimentally show that linear-regression-based OLED power models developed in the past decade cannot capture the unique behavior of OLED display hardware in modern smartphones which have a large color space and propose a new piecewise power model that achieves much better modeling accuracy than the prior-art by applying linear regression in each small regions of the vast color space. Using the two tools, we performed to our knowledge the first power saving measurement of the emerging dark mode for a set of popular Google Android apps.

In this paper, we study how to support high-quality immersive multiplayer VR on commodity mobile devices. First, we perform a scaling experiment that shows simply replicating the prior-art 2-layer distributed VR rendering architecture to multiple players cannot support more than one player due to the linear increase in network bandwidth requirement. Second, we propose to exploit the similarity of background environment (BE) frames to reduce the bandwidth needed for prefetching BE frames from the server, by caching and reusing similar frames. We find that there is often little similarly between the BE frames of even adjacent locations in the virtual world due to a "near-object" effect. We propose a novel technique that splits the rendering of BE frames between the mobile device and the server that drastically enhances the similarity of the BE frames and reduces the network load from frame caching. Evaluation of our implementation on top of Unity and Google Daydream shows our new VR framework, Coterie, reduces per-player network requirement by 10.6X-25.7X and easily supports 4 players for high-resolution VR apps on Pixel 2 over 802.11ac, with 60 FPS and under 16ms responsiveness.

A significant challenge for future virtual reality (VR) applications is to deliver high quality-of-experience, both in terms of video quality and responsiveness, over wireless networks with limited bandwidth. This paper proposes to address this challenge by leveraging the predictability of user movements in the virtual world. We consider a wireless system where an access point (AP) serves multiple VR users. We show that the VR application process consists of two distinctive phases, whereby during the first (proactive scheduling) phase the controller has uncertain predictions of the demand that will arrive at the second (deadline scheduling) phase. We then develop a predictive scheduling policy for the AP that jointly optimizes the scheduling decisions in both phases. In addition to our theoretical study, we demonstrate the usefulness of our policy by building a prototype system. We show that our policy can be implemented under Furion, a Unity-based VR gaming software, with minor modifications. Experimental results clearly show visible difference between our policy and the default one. We also conduct extensive simulation studies, which show that our policy not only outperforms others, but also maintains excellent performance even when the prediction of future user movements is not accurate.

This paper explores network-side cellular user localization using fingerprints created from the angle measurements enabled by 5G. Our key idea is a binning-based fingerprinting technique that leverages multipath propagation to create fingerprint vectors based on angles of arrival of signals along multiple paths at each user. In network simulations that recreate urban environments with 3D building geometry and base station locations for a major city, our binning-based fingerprinting for 5G achieves significantly lower localization errors with a single base station than signal strength-based fingerprinting for LTE.

While live 360° video streaming provides an enriched viewing experience, it is challenging to guarantee the user experience against the negative effects introduced by start-up delay, event-to-eye delay, and low frame rate. It is therefore imperative to understand how different computing tasks of a live 360° streaming system contribute to these three delay metrics. Although prior works have studied commercial live 360° video streaming systems, none of them has dug into the end-to-end pipeline and explored how the task-level time consumption affects the user experience. In this paper, we conduct the first in-depth measurement study of task-level time consumption for five system components in live 360° video streaming. We first identify the subtle relationship between the time consumption breakdown across the system pipeline and the three delay metrics. We then build a prototype Zeus to measure this relationship. Our findings indicate the importance of CPU-GPU transfer at the camera and the server initialization as well as the negligible effect of 360° video stitching on the delay metrics. We finally validate that our results are representative of real world systems by comparing them with those obtained with a commercial system.

Despite the growing market penetration, today's high-end virtual reality (VR) systems remain tethered, which not only limits users' VR experience but also creates a safety hazard. In this paper, we perform a systematic design study of the “elephant in the room” facing the VR industry - is it feasible to enable high-quality VR apps on untethered mobile devices such as smartphones? Our quantitative, performance-driven design study makes two contributions. First, we show that the QoE achievable for high-quality VR applications on today's mobile hardware and wireless networks via local rendering or offloading is about 10X away from the acceptable QoE, yet waiting for future mobile hardware or next-generation wireless networks (e.g., 5G) is unlikely to help, because of power limitation and the higher CPU utilization needed for processing packets under higher data rate. Second, we present Furion, a VR framework that enables high-quality, immersive mobile VR on today's mobile devices and wireless networks. Furion exploits a key insight about the VR workload that foreground interactions and background environment have contrasting predictability and rendering workload, and employs a split renderer architecture running on both the phone and the server. Supplemented with video compression, use of panoramic frames, parallel decoding on multiple cores on the phone, and view-based bitrate adaptation we demonstrate Furion can support high-quality VR apps on today's smartphones over WiFi, with under 14 ms latency and 60 FPS (the phone display refresh rate).

With the advent of bandwidth-hungry applications and the new advancements in wireless LAN standards (802.11ad, 802.11ay) and cellular technologies (5G), modern smartphones need to be able support multi-Gbps data rates. In this work, we explore if today's smartphones are capable of handling such high-speed network traffic. Using two high-end smartphones, we show that, contrary to previous beliefs, they can indeed support Gbps data rates without significant strain on their hardware resources. Using projections, we further show that up to 12.8 Gbps could be supported with just 50% CPU utilization. Finally, we explore the factors that make this possible and the contribution of each of them.

While the bandwidth and latency improvement of both WiFi and cellular data networks in the past decades are plenty evident, the extent of signal strength fluctuation and network disruptions (unexpected switching or disconnections) experienced by mobile users in today's network deployment remains less clear. This paper makes three contributions. First, we conduct the first extensive measurement of network disruptions and significant signal strength fluctuations (together denoted as network instabilities) experienced by 2000 smartphones in the wild. Our results show that network disruptions and signal strength fluctuations remains prevalent as we moved into the 4G era. Second, we study how well popular mobile apps today handle such network instabilities. Our results show that even some of the most popular mobile apps do not implement any disruption-tolerant mechanisms. Third, we present Janus, an intelligent interface management framework that exploits the multiple interfaces on a handset to transparently handle network disruptions and satisfy apps' performance requirement. We have implemented a prototype of Janus and our evaluation using a set of popular apps shows that Janus can: 1) transparently and efficiently handle network disruptions; 2) reduce video stalls by 2.9 times and increase 31% of the time of good voice quality; 3) reduce traffic size by 26.4% and energy consumption by 16.3% compared to naive solutions.

CoFlow scheduling improves data-intensive application performance by improving their networking performance. State-of-the-art CoFlow schedulers in essence approximate the classic online Shortest-Job-First (SJF) scheduling, designed for a single CPU, in a distributed setting, with no coordination among how the flows of a CoFlow at individual ports are scheduled, and as a result suffer two performance drawbacks: (1) The flows of a CoFlow may suffer the out-of-sync problem -- they may be scheduled at different times and become drifting apart, negatively affecting the CoFlow completion time (CCT); (2) FIFO scheduling of flows at each port bears no notion of SJF, leading to suboptimal CCT.

Graphics is one of the major energy drain sources in smartphone apps. To optimize the app graphics energy, however, developers face the challenge of highly complex graphics rendering process, which involves multiple system layers including the app, the framework, the GPU, and the asynchronous interactions among them. Current diagnostic tools can profile the resource usage from certain layers, but fall short in stitching together profiling information across all the layers which is needed to provide developers with the visual effect-energy tradeoff at the app source-code level.

While the bandwidth and latency improvement of both WiFi and cellular data networks in the past decade are plenty evident, the extent of signal strength fluctuation and network disruptions (unexpected switching or disconnections) experienced by mobile users in today's network deployment remains less clear. This paper makes three contributions. First, we conduct the first extensive measurement of network disruptions and signal strength fluctuations (together denoted as instabilities) experienced by 2000 smartphones in the wild. Our results show that network disruptions and signal strength fluctuations remain prevalent as we moved into the 4G era. Second, we study how well popular mobile apps today handle such network instabilities. Our results show that even some of the most popular mobile apps do not implement any disruption-tolerant mechanisms. Third, we present JANUS, an intelligent interface management framework that exploits the multiple interfaces on a handset to transparently handle network disruptions and improve apps' QoE. We have implemented JANUS on Android and our evaluation using a set of popular apps shows that Janus can (1) transparently and efficiently handle network disruptions, (2) reduce video stalls by 2.9 times and increase 31% of the time of good voice quality compared to naive solutions.

In this paper, we perform a systematic design study of the "elephant in the room" facing the VR industry -- is it feasible to enable high-quality VR apps on untethered mobile devices such as smartphones? Our quantitative, performance-driven design study makes two contributions. First, we show that the QoE achievable for high-quality VR applications on today's mobile hardware and wireless networks via local rendering or offloading is about 10X away from the acceptable QoE, yet waiting for future mobile hardware or next-generation wireless networks (e.g. 5G) is unlikely to help, because of power limitation and the higher CPU utilization needed for processing packets under higher data rate. Second, we present Furion, a VR framework that enables high-quality, immersive mobile VR on today's mobile devices and wireless networks. Furion exploits a key insight about the VR workload that foreground interactions and background environment have contrasting predictability and rendering workload, and employs a split renderer architecture running on both the phone and the server. Supplemented with video compression, use of panoramic frames, and parallel decoding on multiple cores on the phone, we demonstrate Furion can support high-quality VR apps on today's smartphones over WiFi, with under 14ms latency and 60 FPS (the phone display refresh rate).

Layer-7 load balancing is a foundational building block of online services. The lack of offerings from major public cloud providers have left online services to build their own load balancers (LB), or use third-party LB design such as HAProxy. The key problem with such proxy-based design is each proxy instance is a single point of failure, as upon its failure, the TCP flow state for the connections with the client and server is lost which breaks the user flows. This significantly affects user experience and online services revenue.

As new iterations of more powerful and better connected smartphones emerge, their limited battery life remains a leading factor adversely affecting the mobile experience of millions of smartphone users. While it is well-known that many apps can drain battery even while running in background, there has not been any study that quantifies the extent and severity of such background energy drain for users in the wild. To extend battery life, various new features are being incorporated within the phone, one of them being preventing applications from running in background, i.e., when the screen is off, but their impact is largely unknown. This paper makes several contributions. First, we present a large-scale measurement study that performs an in-depth analysis of the activities of various apps running in background on thousands of phones in the wild. Second, we quantify the amount of battery drain by all such background activities and possible energy saving. Third, we develop a metric to measure the usefulness of background activities that is personalized to each user. Finally, we present a system called HUSH (screen-off optimizer) that monitors the metric online and automatically identifies and suppresses background activities during screen-off periods that are not useful to the user experience. In doing so, our proposed HUSH saves screen-off energy of smartphones by 15.7% on average while incurring minimal impact on the user experience with the apps.

The limited battery life of modern smartphones remains a leading factor adversely affecting the mobile experience of millions of smartphone users. In order to extend battery life, it is critical to understand where and how is energy drain happening on users' phones under normal usage, for example, in a one-day cycle.

Most of today's mobile devices come equipped with both cellular LTE and WiFi wireless radios, making radio bundling (simultaneous data transfers over multiple interfaces) both appealing and practical. Despite recent studies documenting the benefits of radio bundling with MPTCP, many fundamental questions remain about potential gains from radio bundling, or the relationship between performance and energy consumption in these scenarios. In this study, we seek to answer these questions using extensive measurements to empirically characterize both energy and performance for radio bundling approaches. In doing so, we quantify potential gains of bundling using MPTCP versus an ideal protocol. We study the links between traffic partitioning and bundling performance, and use a novel componentized energy model to quantify the energy consumed by CPUs (and radios) during traffic management. Our results show that MPTCP achieves only a fraction of the total performance gain possible, and that its energy-agnostic design leads to considerable power consumption by the CPU. We conclude that not only there is room for improved bundling performance, but an energy-aware bundling protocol is likely to achieve a much better tradeoff between performance and power consumption.

Load balancing is a foundational function of datacenter infrastructures and is critical to the performance of online services hosted in datacenters. As the demand for cloud services grows, expensive and hard-to-scale dedicated hardware load balancers are being replaced with software load balancers that scale using a distributed data plane that runs on commodity servers. Software load balancers offer low cost, high availability and high flexibility, but suffer high latency and low capacity per load balancer, making them less than ideal for applications that demand either high throughput, or low latency or both. In this paper, we present Duet, which offers all the benefits of software load balancer, along with low latency and high availability -- at next to no cost. We do this by exploiting a hitherto overlooked resource in the data center networks -- the switches themselves. We show how to embed the load balancing functionality into existing hardware switches, thereby achieving organic scalability at no extra cost. For flexibility and high availability, Duet seamlessly integrates the switch-based load balancer with a small deployment of software load balancer. We enumerate and solve several architectural and algorithmic challenges involved in building such a hybrid load balancer. We evaluate Duet using a prototype implementation, as well as extensive simulations driven by traces from our production data centers. Our evaluation shows that Duet provides 10x more capacity than a software load balancer, at a fraction of a cost, while reducing latency by a factor of 10 or more, and is able to quickly adapt to network dynamics including failures.

Search engines have greatly influenced the way people access information on the Internet, as such engines provide the preferred entry point to billions of pages on the Web. Therefore, highly ranked Web pages generally have higher visibility to people and pushing the ranking higher has become the top priority for Web masters. As a matter of fact, Search Engine Optimization (SEO) has became a sizeable business that attempts to improve their clients’ ranking. Still, the lack of ways to validate SEO’s methods has created numerous myths and fallacies associated with ranking algorithms. In this article, we focus on two ranking algorithms, Google’s and Bing’s, and design, implement, and evaluate a ranking system to systematically validate assumptions others have made about these popular ranking algorithms. We demonstrate that linear learning models, coupled with a recursive partitioning ranking scheme, are capable of predicting ranking results with high accuracy. As an example, we manage to correctly predict 7 out of the top 10 pages for 78% of evaluated keywords. Moreover, for content-only ranking, our system can correctly predict 9 or more pages out of the top 10 ones for 77% of search terms. We show how our ranking system can be used to reveal the relative importance of ranking features in a search engine’s ranking function, provide guidelines for SEOs and Web masters to optimize their Web pages, validate or disprove new ranking features, and evaluate search engine ranking results for possible ranking bias.

To maximally conserve the critical resource of battery energy, smartphone OSes implement an aggressive system suspend policy that suspends the whole system after a brief period of user inactivity. This burdens developers with the responsibility of keeping the system on, or waking it up, to execute time-sensitive code. Developer mistakes in using the explicit power management unavoidably give rise to energy bugs, which cause significant, unexpected battery drain.

Modern data center networks are commonly organized in multi-rooted tree topologies. They typically rely on equal-cost multipath to split flows across multiple paths, which can lead to significant load imbalance. Splitting individual flows can provide better load balance, but is not preferred because of potential packet reordering that conventional wisdom suggests may negatively interact with TCP congestion control. In this paper, we revisit this “myth” in the context of data center networks which have regular topologies such as multi-rooted trees. We argue that due to symmetry, the multiple equal-cost paths between two hosts are composed of links that exhibit similar queuing properties. As a result, TCP is able to tolerate the induced packet reordering and maintain a single estimate of RTT. We validate the efficacy of random packet spraying (RPS) using a data center testbed comprising real hardware switches. We also reveal the adverse impact on the performance of RPS when the symmetry is disturbed (e.g., during link failures) and suggest solutions to mitigate this effect.

Rapid flooding is necessary for code updates and routing tree formation in wireless sensor networks. Link correlation-aware collective flooding (CF) is a recently proposed technique that provides a substrate for efficiently disseminating a single packet. Applying CF to multiple packet dissemination poses several challenges, such as reliability degradation, redundant transmissions, and increased contention among node transmissions. The varying link correlation observed in real networks makes the problem harder. In this paper, we propose a multi-packet flooding protocol, SYREN, that exploits the synergy among link correlation and network coding. In particular, SYREN exploits link correlation to eliminate the overhead of explicit control packets in networks with high correlation, and uses network coding to pipeline transmission of multiple packets via a novel, single yet scalable timer per node. SYREN reduces the number of redundant transmissions while achieving near-perfect reliability, especially in networks with low link correlation. Test bed experiments and simulations show that SYREN reduces the average number of transmissions by 30% and dissemination delay by more than 60% while achieving the same reliability as state-of-the-art protocols.

Despite the tremendous market penetration of smartphones, their utility has been and will remain severely limited by their battery life. A major source of smartphone battery drain is accessing the Internet over cellular or WiFi connection when running various apps and services. Despite much anecdotal evidence of smartphone users experiencing quicker battery drain in poor signal strength, there has been limited understanding of how often smartphone users experience poor signal strength and the quantitative impact of poor signal strength on the phone battery drain. The answers to such questions are essential for diagnosing and improving cellular network services and smartphone battery life and help to build more accurate online power models for smartphones, which are building blocks for energy profiling and optimization of smartphone apps. In this paper, we conduct the first measurement and modeling study of the impact of wireless signal strength on smartphone energy consumption. Our study makes four contributions. First, through analyzing traces collected on 3785 smartphones for at least one month, we show that poor signal strength of both 3G and WiFi is routinely experienced by smartphone users, both spatially and temporally. Second, we quantify the extra energy consumption on data transfer induced by poor wireless signal strength. Third, we develop a new power model for WiFi and 3G that incorporates the signal strength factor and significantly improves the modeling accuracy over the previous state of the art. Finally, we perform what-if analysis to quantify the potential energy savings from opportunistically delaying network traffic by exploring the dynamics of signal strength experienced by users.

Energy conservation is essential in Wireless Sensor Networks (WSNs) because of limited energy in nodes' batteries. Collaborative beamforming uses multiple transmitters to form antenna arrays; the electromagnetic waves from these antenna arrays can create constructive interferences at the receiver and increase the transmission distance. Each transmitter can use lower power and save energy, since the energy consumption is spread over multiple transmitters. Each beamforming transmission requires multiple collaborative transmitters. Repetitively using the same transmitters will deplete their energy and create coverage holes in the sensing area. To prevent holes, energy should be balanced by using different transmitters. This article investigates the factors that can affect the energy consumption and network lifetime when using beamforming. We present an algorithm for selecting the transmitters in order to prolong the network lifetime. Compared with an existing beamforming transmitters scheduling algorithm, our algorithm doubles the network lifetime. When compared with direct transmission or multihop transmissions towards a receiver far away from the sensing area, our approach can increase the network's lifetime substantially.

A key challenge faced by users of public clouds today is how to request for the right amount of resources in the production datacenter that satisfies a target performance for a given cloud application. An obvious approach is to develop a performance model for a class of applications such as MapReduce. However, several recent studies have shown that even for the class of well-studied MapReduce jobs, their running times can be seriously affected by numerous external factors ranging from dozen or so configuration parameters, to the physical machine characteristics (CPU, memory, disk, and network bandwidth), to implementation deficiencies such as Java, garbage collection. These factors make direct performance modeling extremely difficult. In this paper, we propose a more practical systematic methodology to solve this problem. Our approach develops a projection model, based on insights into performance bottlenecks of MapReduce jobs and their scaling properties, and parameterized with component running times based on profiling on small clusters with sampled inputs. Evaluation results show our projection model can predict job running times with 2.7% of accuracy when scaling to 32 nodes.

Where is the energy spent inside my app? Despite the immense popularity of smartphones and the fact that energy is the most crucial aspect in smartphone programming, the answer to the above question remains elusive. This paper first presents eprof, the first fine-grained energy profiler for smartphone apps. Compared to profiling the runtime of applications running on conventional computers, profiling energy consumption of applications running on smartphones faces a unique challenge, asynchronous power behavior, where the effect on a component's power state due to a program entity lasts beyond the end of that program entity. We present the design, implementation and evaluation of eprof on two mobile OSes, Android and Windows Mobile.

The WiFi radio in smartphones consumes a significant portion of energy when active. To reduce the energy consumption, the Power Saving Mode was standardized in IEEE 802.11 and two major implementations, Static PSM and Dynamic PSM, have been widely used in mobile devices. Unfortunately, both PSMs have inherent drawbacks: Static PSM is energy efficient but imposes considerable extra delays on data transfers; Dynamic PSM incurs little extra delay but misses energy saving opportunities. In this paper, we first analyze a one-week trace from 10 users and show that more than 80% of all traffic are Web 2.0 flows, which are of very small sizes and short durations. Targeting these short but dominant flows, we propose a system called Percy, to achieve the best of both worlds (Static and Dynamic PSM), i.e., to maximize the energy saving while minimizing the delay of flow completion time. Percy works by deploying a web proxy at the AP and suitably configuring the PSM parameters, and is designed to work with unchanged clients running Dynamic PSM, and unchanged APs and Internet servers. We evaluate our system via trace-driven testbed experiments. Our results show that Percy saves 40-70% energy compared to Dynamic PSM configurations of Nokia, iPhone and Android, while imposing low extra delay that can hardly be perceived by users.

Despite their immense popularity in recent years, smartphones are and will remain severely limited by their battery life. Preserving this critical resource has driven smartphone OSes to undergo a paradigm shift in power management: by default every component, including the CPU, stays off or in an idle state, unless the app explicitly instructs the OS to keep it on! Such a policy encumbers app developers to explicitly juggle power control APIs exported by the OS to keep the components on, during their active use by the app and off otherwise. The resulting power-encumbered programming unavoidably gives rise to a new class of software energy bugs on smartphones called no-sleep bugs, which arise from mis-handling power control APIs by apps or the framework and result in significant and unexpected battery drainage.

Correlated packet reception can be advantageous for sensor network broadcast protocols. By exploiting link correlation information, researchers have devised efficient single packet flooding protocols. In this work, we use testbed experiments to gain insight into the behavior of link correlation-aware broadcast protocols. We observe that, in the presence of varying link correlation, traditional link correlation-aware flooding mechanisms do not perform well in disseminating multiple packets due to reliability requirements and redundant transmissions. We conduct simulations to compare existing link correlation-aware flooding protocols with two versions of a multi-packet dissemination protocol, where one uses network coding and the other exploits both link correlation and network coding. Simulation results indicate the potential of the latter approach to be used as a reliable multi-packet dissemination protocol in practical scenarios. We also compare this protocol with existing multi-packet dissemination protocols, and reveal cases when certain protocols perform better than others.

A primary challenge in exploiting Cognitive Radio Networks (CRNs), known as the rendezvous problem, is for the users to find each other in the dynamic open spectrum. We study blind rendezvous, where users search for each other without any infrastructural aid. Previous work in this area have focused on efficient blind rendezvous algorithms for two users but the solution for multiple users is still far from optimal. In particular, when two users encounter, one user inherits the other's hopping sequence but the sequence is never shortened or split among the encountering users. We denote this class of algorithms as uncoordinated channel hopping algorithms. In this paper, we introduce a new class of distributed algorithms for multi-user blind rendezvous, called Coordinated Channel Hopping (CCH), where users adjust, or coordinate, the sequence of channels being hopped as they rendezvous pairwise. Compared to existing rendezvous algorithms, our algorithms achieve 80% lower Time To Rendezvous (TTR) in case of multiple users.

In multi-tenant datacenters, jobs of different tenants compete for the shared datacenter network and can suffer poor performance and high cost from varying, unpredictable network performance. Recently, several virtual network abstractions have been proposed to provide explicit APIs for tenant jobs to specify and reserve virtual clusters (VC) with both explicit VMs and required network bandwidth between the VMs. However, all of the existing proposals reserve a fixed bandwidth throughout the entire execution of a job.

Current multipath routing techniques split traffic at a per-flow level because, according to conventional wisdom, forwarding packets of a TCP flow along different paths leads to packet reordering which is detrimental to TCP. In this paper, we revisit this "myth" in the context of cloud data center networks which have regular topologies such as multi-rooted trees. We argue that due to the symmetry in the multiple equal-cost paths in such networks, simply spraying packets of a given flow among all equal-cost paths, leads to balanced queues across multiple paths, and consequently little packet reordering. Using a testbed comprising of NetFPGA switches, we show how cloud applications benefit from better network utilization in data centers.

In contrast to unicast routing, high-throughput reliable multicast routing in wireless mesh networks (WMNs) has received little attention. There are two primary challenges to supporting high-throughput, reliable multicast in WMNs. The first is no different from unicast: Wireless links are inherently lossy due to varying channel conditions and interference. The second, known as the “crying baby” problem, is unique to multicast: The multicast source may have varying throughput to different multicast receivers, and hence trying to satisfy the reliability requirement for poorly connected receivers can potentially result in performance degradation for the rest of the receivers. In this paper, we propose Pacifier, a new high-throughput, reliable multicast protocol for WMNs. Pacifier seamlessly integrates four building blocks-namely, tree-based opportunistic routing, intraflow network coding, source rate limiting, and round-robin batching-to support high-throughput, reliable multicast routing in WMNs, while at the same time it effectively addresses the “crying baby” problem. Our experiments on a 22-node IEEE 802.11 WMN testbed show that Pacifier increases the average throughput over a state-of-the-art reliable network coding-based protocol MORE by up to 144%, while at the same time it solves the “crying baby” problem by improving the throughput of well-connected receivers by up to a factor of 14.

Accurate, fine-grained online energy estimation and accounting of mobile devices such as smartphones is of critical importance to understanding and debugging the energy consumption of mobile applications. We observe that state-of-the-art, utilization-based power modeling correlates the (actual) utilization of a hardware component with its power state, and hence is insufficient in capturing several power behavior not directly related to the component utilization in modern smartphones. Such behavior arise due to various low level power optimizations programmed in the device drivers. We propose a new, system-call-based power modeling approach which gracefully encompasses both utilization-based and non-utilization-based power behavior. We present the detailed design of such a power modeling scheme and its implementation on Android and Windows Mobile. Our experimental results using a diverse set of applications confirm that the new model significantly improves the fine-grained as well as whole-application energy consumption accuracy. We further demonstrate fine-grained energy accounting enabled by such a fined-grained power model, via amanually implemented eprof, the energy counterpart of the classic gprof tool, for profiling application energy drain.

This paper argues that a new class of bugs faced by millions of smartphones, energy bugs or ebugs, have become increasingly prominent that already they have led to significant user frustrations. We take a first look at this emerging important technical challenge faced by the smartphones, ebugs, broadly defined as an error in the system (application, OS, hardware, firmware, external conditions or combination) that causes an unexpected amount of high energy consumption by the system as a whole. We first present a taxonomy of the kinds of ebugs based on mining over 39K posts (1.2M before filtering) from 4 online mobile user forum and mobile OS bug repositories. The taxonomy shows the highly diverse nature of smartphone ebugs. We then propose a roadmap towards developing a systematic diagnosing framework for debugging ebugs on smartphones.

The early success of wireless sensor networks has led to a new generation of increasingly sophisticated sensor network applications, such as HP's CeNSE. These applications demand high network throughput that easily exceeds the capability of low-power 802.15.4 radios that are most commonly used in today's sensor nodes. To address this issue, this paper investigates an energy-efficient approach to supplementing an 802.15.4 based sensor network with high bandwidth, high power, longer range radios such as 802.11. Exploiting a key observation that the high bandwidth radio achieves low energy consumption per transmitted bit of data due to its inherent transmission efficiency, we propose a hybrid network architecture that utilizes an optimal density of dual-radio (802.15.4 and 802.11) nodes to augment a sensor network having only 802.15.4 radios. We present a cross-layer mathematical model to calculate this optimal density, which strikes a balance between the low energy per bit of the high-bandwidth radio and the low sleep power of 802.15.4 radio. Experimental results obtained using a wireless testbed reveal that our architecture improves the average energy per bit, the time elapsed before half of the nodes drain their battery, and the end-to-end delay by 62%, 106%, and 73% respectively, compared to a network that uses only 802.15.4 radios.

A primary challenge in multi casting video in a wireless LAN to multiple clients is to deal with the client diversity -- clients may have different channel characteristics and hence receive different numbers of transmissions from the AP. A promising approach to overcome this problem is to combine multi-resolution (layered) video coding with interlayer network coding. The fundamental challenge in such an approach is to determine the strategy of coding the packets across different layers that maximizes the number of decoded layers at all clients. This paper makes three contributions. (1) We first show that even for one client, the previously proposed canonical triangular scheme for inter-layer network coding can perform poorly. We show how to enhance the triangular scheme by incorporating the estimated target number of layers which significantly improves its effectiveness. (2) We show that such an enhanced triangular scheme still performs poorly for multiple clients with diverse channel characteristics, which motivates the need for searching for the optimal coding strategy. The naive way of searching for the optimal strategy is computationally prohibitive. We present several optimizations that drastically reduce the complexity of exhaustively searching for the optimal strategy, making it feasible in real time. (3) Finally, we design and evaluate an on line video delivery scheme, Percy, to be deployed at a proxy behind the AP of a wireless LAN. Our simulation results show that Percy outperforms the previous inter-layer coding heuristic by up to 22-80% with varying numbers of clients.

While MPLS has been extensively deployed in recent years, little is known about its behavior in practice. We examine the performance of MPLS in Microsoft's online service network (MSN), a well-provisioned multi-continent production network connecting tens of data centers. Using detailed traces collected over a 2-month period, we find that many paths experience significantly inflated latencies. We correlate occurrences of latency inflation with routers, links, and DC-pairs. This analysis sheds light on the causes of latency inflation and suggests several avenues for alleviating the problem.

The Border Gateway Protocol (BGP), the de-facto Internet interdomain routing protocol, disseminates information about Internet prefixes to Autonomous Systems (ASes). Prefixes are announced and withdrawn as routes and policies change, making them unreachable from portions of the Internet for certain time periods. This paper aims to predict routing failures of prefixes in the Internet.We investigate the similarity of prefixes in the Internet with respect to their propensity to fail, i.e., become unreachable. Given a prefix of interest, we define a “BGP molecule” - the prefixes in the Internet that are likely to fail together with this prefix. We show that the AS paths to prefixes, coupled with knowledge of the prefix geographical location, contribute to its failure tendency. The BGP molecules constructed are used in four failure prediction schemes among which a hybrid scheme achieves 91% predictability of failures with 99.3% coverage of prefixes in the Internet.

A primary challenge in multicasting video in a wireless LAN is to deal with the client diversity -- clients may have different channel characteristics and hence receive different numbers of transmissions from the AP. A promising approach to overcome this problem is to combine scalable video coding techniques such as MRC or MDC, which divide a video stream into multiple substreams, with inter-layer network coding. The fundamental challenge in such an approach is to determine the strategy of coding the packets across different layers that maximizes the number of decoded layers at all clients. In [7], the authors showed that inter-layer NC indeed helps the delivery of MRC coded media over the WiFi, and proposed how to efficiently search for the optimal coding strategies online.

We introduce a technique that utilizes distributing computing resources for the efficient optimization of a traditional physical design problem. Specifically, we present a detailed placement strategy designed to exploit distributed computing environments, where the additional computing resources are employed in parallel to improve the optimization time. A Mixed Integer Programming (MIP) model and branch-and-cut optimization strategy are employed to solve the standard cell placement problem. By exploiting the problem structure, our algorithm improves upon the solutions afforded by existing optimization algorithms. First, an efficient batch-branching technique can eliminate several integer decision variables during each step of the optimization procedure. This batch-branching scheme can be performed serially or in parallel. In addition, custom cutting-planes are shown to significantly reduce the run time for optimizations as they efficiently refine the feasible region in order to quickly produce integer solutions. Our serial branch-and-cut strategies allow for significant reductions in wirelength, relative to the state-of-the-art commercial software package CPLEX, assuming a fixed allotment of time. Furthermore, we show that distributed computing resources can be used to significantly reduce the time required to achieve reductions in wirelength.

The use of random linear network coding (NC) has significantly simplified the design of opportunistic routing (OR) protocols by removing the need of coordination among forwarding nodes for avoiding duplicate transmissions. However, NC-based OR protocols face a new challenge: How many coded packets should each forwarder transmit? To avoid the overhead of feedback exchange, most practical existing NC-based OR protocols compute offline the expected number of transmissions for each forwarder using heuristics based on periodic measurements of the average link loss rates and the ETX metric. Although attractive due to their minimal coordination overhead, these approaches may suffer significant performance degradation in dynamic wireless environments with continuously changing levels of channel gains, interference, and background traffic. In this paper, we propose CCACK, a new efficient NC-based OR protocol. CCACK exploits a novel Cumulative Coded ACKnowledgment scheme that allows nodes to acknowledge network-coded traffic to their upstream nodes in a simple way, oblivious to loss rates, and with negligible overhead. Through extensive simulations and testbed experiments, we show that CCACK greatly improves both throughput and fairness compared to MORE, a state-of-the-art NC-based OR protocol.

Collaborative beamforming is a transmission technique by using multiple transmitters to form antenna arrays and creating highly directional beams to a distant receiver. Collaborative beamforming can enhance energy efficiency in wireless sensor networks. However, the same information needs to be shared among the transmitters in advance. As a result, communication among the transmitters is required; this consumes energy and shortens the lifetime of the sensor network. In this paper, we propose a procedure for data sharing when multiple sensing nodes and multiple transmitters are used and examine the energy consumption for beamforming. We show that beamforming is energy-efficient when the sensor nodes are deployed far away from the base station and the energy consumed for data sharing has negligible effects on the network's lifetime.

The Border Gateway Protocol (BGP) maintains inter-domain routing information by announcing and withdrawing IP prefixes, possibly resulting in temporary prefix unreachability. Prefix availability observed from different vantage points in the Internet can be lower than standards promised by Service Level Agreements (SLAs). In this paper, we develop a framework for predicting long-term prefix availability, given short-duration prefix information from publicly available BGP routing databases. We compare three prediction models, and find that bagged decision trees perform the best when predicting for long future durations, whereas a simple model works well for short prediction durations. We show that mean time to failure and to recovery outperform past availability in terms of their importance for predicting availability for long durations. We also find that predictability is higher in the year 2009, compared to four years earlier. Our models allow ISPs to adjust BGP routing policies if predicted availability is low, and the models are useful for cloud computing systems, P2P, and VoIP applications.

The use of random linear network coding (NC) has significantly simplified the design of opportunistic routing (OR) protocols by removing the need of coordination among forwarding nodes for avoiding duplicate transmissions. However, NC-based OR protocols face a new challenge: How many coded packets should each forwarder transmit? To avoid the overhead of feedback exchange, most practical existing NC-based OR protocols compute offline the expected number of transmissions for each forwarder using heuristics based on periodic measurements of the average link loss rates and the ETX metric. Although attractive due to their minimal coordination overhead, these approaches may suffer significant performance degradation in dynamic wireless environments with continuously changing levels of channel gains, interference, and background traffic. In this paper, we propose CCACK, a new efficient NC-based OR protocol. CCACK exploits a novel Cumulative Coded ACKnowledgment scheme that allows nodes to acknowledge network coded traffic to their upstream nodes in a simple way, oblivious to loss rates, and with practically zero overhead. In addition, the cumulative coded acknowledgment scheme in CCACK enables an efficient credit-based, rate control algorithm. Our evaluation shows that, compared to MORE, a state-of-the-art NC-based OR protocol, CCACK improves both throughput and fairness, by up to 20× and 124%, respectively, with average improvements of 45% and 8.8%, respectively.

A fast and power efficient phase difference and frequency offset estimation technique for collaborative beamforming in a wireless sensor network is presented. Common radio blocks are used to implement the phase difference estimation technique and we present an analytical expression for the phase difference estimation accuracy in an AWGN channel. The analysis including the effect of noise and multipath on the estimation accuracy shows the effectiveness of the proposed estimation technique for collaborative beamforming applications.

Energy conservation is essential in wireless sensor networks (WSNs) because of limited energy in batteries. Collaborative beamforming uses multiple transmitters to form antenna arrays; the electromagnetic waves from these antenna arrays can create constructive interferences at the receiver and increase the transmission distance. Each transmitter can use lower power and save energy, since the energy consumption is spread over multiple transmitters. However, if the same nodes are always used for collaborative beamforming, these nodes would deplete their energy much sooner and this sensing area will no longer be monitored. To avoid this situation, energy consumption for collaborative beamforming needs to be balanced over the whole network by assigning the transmitters in turns. The transmitters in each round are selected by a scheduler and the energy carried in each node is balanced to increase the number of transmissions. We define the lifetime of a network as the number of transmissions until a certain percentage of the nodes depletes their energy. This paper proposes an algorithm to calculate energy-efficient schedules based on the remaining energy and the phase differences of their signals arriving at the receiver. Compared with an existing algorithm, our algorithm can extend the network lifetime by more than 60%.

No abstract available.

Search engines have greatly influenced the way people access information on the Internet as such engines provide the preferred entry point to billions of pages on the Web. Therefore, highly ranked web pages generally have higher visibility to people and pushing the ranking higher has become the top priority for webmasters. As a matter of fact, search engine optimization (SEO) has became a sizeable business that attempts to improve their clients' ranking. Still, the natural reluctance of search engine companies to reveal their internal mechanisms and the lack of ways to validate SEO's methods have created numerous myths and fallacies associated with ranking algorithms; Google'sin particular. In this paper, we focus on the Google ranking algorithm and design, implement, and evaluate a ranking system to systematically validate assumptions others have made about this popular ranking algorithm. We demonstrate that linear learning models, coupled with a recursive partitioning ranking scheme, are capable of reverse engineering Google's ranking algorithm with high accuracy. As an example, we manage to correctly predict 7 out of the top 10 pages for 78% of evaluated keywords. Moreover, for content-only ranking, our system can correctly predict 9 or more pages out of the top 10 ones for 77% of search terms. We show how our ranking system can be used to reveal the relative importance of ranking features in Google's ranking function, provide guidelines for SEOs and webmasters to optimize their web pages, validate or disapprove new ranking features, and evaluate search engine ranking results for possible ranking bias.

IP prefix hijacking remains a major threat to the security of the Internet routing system due to a lack of authoritative prefix ownership information. Despite many efforts in designing IP prefix hijack detection schemes, no existing design can satisfy all the critical requirements of a truly effective system: real-time, accurate, lightweight, easily and incrementally deployable, as well as robust in victim notification. In this paper, we present a novel approach that fulfills all these goals by monitoring network reachability from key external transit networks to one's own network through lightweight prefix-owner-based active probing. Using the prefix-owner's view of reachability, our detection system, iSPY, can differentiate between IP prefix hijacking and network failures based on the observation that hijacking is likely to result in topologically more diverse polluted networks and unreachability. Through detailed simulations of Internet routing, 25-day deployment in 88 autonomous systems (ASs) (108 prefixes), and experiments with hijacking events of our own prefix from multiple locations, we demonstrate that iSPY is accurate with false negative ratio below 0.45% and false positive ratio below 0.17%. Furthermore, iSPY is truly real-time; it can detect hijacking events within a few minutes.

The border gateway protocol (BGP) is a fundamental building block of the Internet infrastructure. However, due to the implicit trust assumption among networks, Internet routing remains quite vulnerable to various types of misconfiguration and attacks. Prefix hijacking is one such misbehavior where an attacker AS injects false routes to the Internet routing system that misleads victim's traffic to the attacker AS. Previous secure routing proposals, e.g., S-BGP, have relied on the global public key infrastructure (PKI), which creates deployment burdens. In this paper, we propose an efficient cryptographic mechanism, HC-BGP, using hash chains and regular public/private key pairs to ensure prefix ownership certificates. HC-BGP is computationally more efficient than previously proposed secure routing schemes, and it is also more flexible for supporting various traffic engineering goals. Our scheme can efficiently prevent common prefix hijacking attacks which announce routes with false origins, including both prefix and sub-prefix hijacking attacks.

The reachability of IP address prefixes exhibits significant fluctuations due to changes in both physical connectivity and ISP routing policies. In the late 1990s, Labovitz et al. performed an extensive study of inter-domain path stability by analyzing BGP routing data. To reduce the noise in the BGP data, e.g., transient updates during route convergence, they applied several filters to preprocess the raw BGP data. In this work, we investigate prefix reachability as advertised by BGP, while revisiting the preprocessing filter design problem. We show that the reachability analysis results are highly sensitive to the specific filters applied and the parameters that control the strength of the filters. In particular, we compute the mean time to failure and recovery (MTTF and MTTR) as well as the up- to-downtime ratios of prefixes, and find that these can fluctuate by a factor of 10 by varying the filter parameters. We analyze the impact of recent fiber cuts in the Mediterranean sea and the Middle East, and study prefix reachability during a nine-month period in 2007 to evaluate the general health of the Internet.

The email volume per mailbox has largely remained low and unchanged in the past several decades, and hence mail server performance has largely remained a secondary issue. The steep rise in the amount of unsolicited emails, i.e. spam, in the past decade, however, has permanently disrupted this tranquility of largely steady email volume and turned mail server performance into an increasingly important issue. In this paper, we point out that modern mail servers were not originally designed with email spam in mind, and as such, as the "common case'' workload for mail servers has shifted from legitimate emails to spam emails, we argue it is time to revisit mail server architecture design in following the system design principle of optimizing the common case. In particular, we show how to optimize the performance of three major components of modern mail servers, the concurrency architecture, the disk I/O, and DNSBL lookups, by exploiting the new "common case" workload. An evaluation of our prototype implementation of the enhanced postfix architecture shows that the optimizations significantly reduce the CPU, disk, and network resource consumptions, and improves the throughput of the mail server by 18% under a university departmental mail server workload and by 40% under a spam sinkhole workload.

In contrast to unicast routing, high-throughput reliable multicast routing in wireless mesh networks (WMNs) has received little attention. There are two primary challenges to supporting high-throughput, reliable multicast in WMNs. The first is no different from unicast: wireless links are inherently lossy due to varying channel conditions and interference. The second, known as the "crying baby" problem, is unique to multicast: the multicast source may have varying throughput to different multicast receivers, and hence trying to satisfy the reliability requirement for poorly connected receivers can potentially result in performance degradation for the rest of the receivers. In this paper, we propose Pacifier, a new high-throughput reliable multicast protocol for WMNs. Pacifier seamlessly integrates four building blocks, namely, tree-based opportunistic routing, intra-flow network coding, source rate limiting, and round-robin batching, to support high-throughput, reliable multicast routing in WMNs, while at the same time effectively addresses the "crying baby" problem. Our evaluations show that Pacifier increases the average throughput over a practical, state-of-the-art reliable network coding-based protocol MORE by 171%, while improving the throughput of well-connected receivers by up to a factor of 20.

Recently, network coding has gained much popularity and several practical routing schemes have been proposed for wireless mesh networks that exploit interflow network coding for improved throughput. However, the evaluation of these protocols either assumed simple topologies and traffic patterns such as opposite flows along a single chain, or small, dense networks which have ample overhearing of each other's transmissions in addition to many overlapping flows. In this paper, we seek to answer the fundamental question: how much performance benefit from network coding can be expected for general traffic patterns in a moderate-sized wireless mesh network? We approach this question via an empirical study of both coordinated and opportunistic coding based protocols subject to general traffic patterns. Our study shows the performance benefits under both types of coding for general traffic patterns are extremely limited. We then analyze and uncover fundamental reasons for the limited performance benefits.

Motivated by P2P file transfer applications (e.g., BitTorrent) on the Internet, this paper considers the problem of delivering a file from a server to multiple receivers in a P2P network. Each receiver has an associated delay in receiving the file. We aim at understanding the optimal delay region, i.e., the set of all possible delay vectors that can be achieved. Previous work has addressed the problem of delivering the file to all receivers in minimum amount of time (equivalently, minimizing the maximum delay to the receivers), assuming peer uplinks are the only bottleneck in the network. This paper shows that it is in fact possible to significantly reduce the average delay at a slight increase in the maximum delay. Moreover, given an order at which the receivers finish downloading, the optimal delay region is characterized by a system of linear inequalities. Any point in the optimal delay region can be achieved by linear network coding. We also propose a simple routing scheme that has near-optimal empirical performance.

There are two primary challenges to supporting high-throughput, reliable multicast in wireless mesh networks (WMNs). The first is no different from unicast: wireless links are inherently lossy due to varying channel conditions and interference. The second, known as the "crying baby" problem, is unique to multicast: the multicast source may have varying throughput to different multicast receivers, and hence trying to satisfy the reliability requirement for poorly connected receivers can potentially result in performance degradation for the rest of the receivers.

We present the design, implementation, and evaluation of a Time Division Multiplex (TDM) MAC protocol for multi-hop wireless mesh networks using a programmable wireless platform. Extensive research has been devoted to optimal scheduling algorithms for multi-hop wireless networks assuming a perfect TDM MAC protocol. However, the problem of designing and implementing such a protocol has not received due attention. We introduce a design framework that addresses the three main challenges that comprise this problem: (i) How to calibrate and optimize the TDM MAC protocol parameters given a wireless platform, (ii) how to achieve network-wide synchronization with high accuracy, minimal overhead, and most importantly, bounded delay, and (iii) how to integrate the synchronization algorithm with the TDM MAC protocol state machine using minimal hardware resources. We apply our design framework to our platform and evaluate the resulting TDM MAC protocol through controlled experiments in a wireless mesh testbed. The results demonstrate the protocol's ability to provide fairness and graceful performance degradation under packet losses and multi-hop traffic patterns that arise in mesh network deployments.

IP prefix hijacking remains a major threat to the security of the Internet routing system due to a lack of authoritative prefix ownership information. Despite many efforts in designing IP prefix hijack detection schemes, no existing design can satisfy all the critical requirements of a truly effective system: real-time, accurate, light-weight, easily and incrementally deployable, as well as robust in victim notification. In this paper, we present a novel approach that fulfills all these goals by monitoring network reachability from key external transit networks to one's own network through lightweight prefix-owner-based active probing. Using the prefix-owner's view of reachability, our detection system, iSPY, can differentiate between IP prefix hijacking and network failures based on the observation that hijacking is likely to result in topologically more diverse polluted networks and unreachability. Through detailed simulations of Internet routing, 25-day deployment in 88 ASes (108 prefixes), and experiments with hijacking events of our own prefix from multiple locations, we demonstrate that iSPY is accurate with false negative ratio below 0.45% and false positive ratio below 0.17%. Furthermore, iSPY is truly real-time; it can detect hijacking events within a few minutes.

Several multicast protocols for mobile ad hoc networks have been proposed, which build multicast trees by using location information that is available from the Global Positioning System (GPS) or localization algorithms and use geographic forwarding to forward packets down the multicast trees. These stateless multicast protocols carry encoded membership, location, and tree information in each packet and are more efficient and robust than stateful protocols (for example, ADMR and ODMRP), as they avoid the difficulty of maintaining distributed state in the presence of frequent topology changes. However, current stateless multicast protocols are not scalable to large groups because of the per-packet encoding overhead, and the centralized group membership and location management. We present the hierarchical rendezvous point multicast (HRPM) protocol, which significantly improves the scalability of stateless multicast with respect to the group size. HRPM consists of two key design ideas: 1) hierarchical decomposition of a large group into a hierarchy of recursively organized manageable-sized subgroups and 2) the use of distributed geographic hashing to construct and maintain such a hierarchy at virtually no cost. Our detailed simulations demonstrates that HRPM achieves significantly enhanced scalability and performance due to hierarchical organization and distributed hashing.

Community wireless mesh networks (WMNs) are increasingly being deployed for providing cheap, low maintenance Internet access. For the successful adoption of WMNs as a last-mile technology, we argue that a guarantee of per-client fairness is critical. Specifically, WMNs should support a bitrate-for-bucks service model similar to other popular access technologies such as Cable/DSL.We analyze the effectiveness of both off-the-shelf and theoretically optimal approaches towards providing such a service. We propose the APOLLO system that outperforms both these approaches.APOLLO seamlessly integrates three synergistic components: theory-guided service planning and subscription, rate-based admission control to enforce the planned service, and a novel distributed light-weight fair scheduling scheme to deliver the admitted traffic. We evaluate APOLLO using simulations and testbed experiments.

A major task of a wireless sensor network is energy-efficient, timely, and robust dissemination of sensor readings back to the sink node. The AIDA project [1] aims to create a new sensor network architecture, that uses antenna arrays of the distributed sensor nodes to create directional radio waves that can reach order-of-magnitude farther than individual antennas of the sensor nodes. This new network architecture, based on collaborative beamforming, drastically changes many aspects of the conventional networking stack. As part of the AIDA project, we are designing new energyefficient MAC and routing protocols for the new, distributed beamforming physical layer, which effectively involves “manysensors-to-many-sensors” for a single data packet transmission. 1. BACKGROUND

Prefix hijacking, a misbehavior in which a misconfigured or malicious BGP router originates an IP prefix that the router does not own, is becoming an increasingly serious security problem on the Internet. In this paper, we conduct a first comprehensive study on incrementally deployable mitigation solutions against prefix hijacking. We first propose a novel reactive detection-assisted solution based on the idea of bogus route purging and valid route promotion. Our simulations based on realistic settings show that purging bogus routes at 20 highest-degree ASes reduces the polluted portion of the Internet by a random prefix hijack from 50% down to 24%, and adding promotion further reduces the remaining pollution by 33% ~ 57%, We prove that our proposed route purging and promotion scheme preserve the convergence properties of BGP regardless of the number of promoters. We are the first to demonstrate that detection systems based on a limited number of BGP feeds are subject to detection evasion by hijackers. Motivated the need for proactive defenses to complement reactive mitigation response, we evaluate customer route filtering, a best common practice among large ISPs today, and show its limited effectiveness. We also show the added benefits of combining route purging-promotion with customer route filtering.

Many important applications in wireless mesh networks require reliable multicast communication. Previously, forward error correction (FEC) techniques have been proved successful for providing reliability in the Internet, as they avoid the control packet implosion and scalability problems of ARQ-based protocols. In this paper, we examine if FEC can be equally efficient wireless mesh networks. We implement four reliable schemes initially proposed for wired networks on top of ODMRP, a popular unreliable multicast routing protocol for wireless networks. We compare the performance of the four schemes using extensive simulations. Our results show that the use of pure FEC can offer significant improvements in terms of reliability, increasing PDR up to 100% in many cases, but it can be very inefficient regarding the number of redundant packets it transmits. Moreover, a carefully designed hybrid protocol, such as RMDP, can maintain the same high level of reliability while improving the efficiency by up to 38% compared to a pure FEC scheme.

Overlay routing has emerged as a promising approach to improving performance and reliability of Internet paths. To fully realize the potential of overlay routing under the constraints of deployment costs in terms of hardware, network connectivity and human effort, it is critical to carefully place infrastructure overlay nodes to balance the trade-off between performance and resource constraints. In this paper, we investigate approaches to perform intelligent placement of overlay nodes to facilitate (i) resilient routing and (ii) TCP performance improvement. We formulate objective functions to accurately capture application behavior: reliability and TCP performance, and develop several placement algorithms, which offer a wide range of trade-offs in complexity and required knowledge of the client- server location and traffic load. Using simulations on synthetic and real Internet topologies, and PlanetLab experiments, we demonstrate the effectiveness of the placement algorithms and objective functions developed, respectively. We conclude that an approach, hybrid of random and greedy approaches, provides the best tradeoff between computational efficiency and accuracy. We also uncover the fundamental challenge in simultaneously optimizing for reliability and TCP performance, and propose a simple unified algorithm to achieve the same.

Multi-hop wireless mesh networks are increasingly being deployed for last-mile Internet access. Typically, network algorithms such as routing, channel assignment and topology control for such networks rely heavily on metrics that intend to capture link "quality" across the network. However, the underlying dynamics of the proposed link metrics themselves have not yet been studied in detail. In this paper, we study the dynamics of the most popular link metrics in real network deployments. Using two wireless mesh testbeds, we measure a number of link metrics across different hardware platforms and network environments. The collected measurements allow us to study the stability and sensitivity of the different metrics to various conditions. Our study provides several insights and future research directions on how network algorithms need to adapt to link dynamics as well as how popular and widely used link metrics can be improved.

Several route monitoring systems have been set up to help understand the Internet routing system. They operate by gathering real-time BGP updates from different networks. Many studies have relied on such data sources by assuming reasonably good coverage and thus representative visibility into the Internet routing system. However, different deployment strategies of route monitors directly impact the accuracy and generality of conclusions.

In recent years, the success of single-robot SLAM has led to more multi-robot SLAM (MR-SLAM) research. A team of robots with MR-SLAM can explore an environment more efficiently and reliably; however, MR-SLAM also raises many challenging problems, including map fusion, unknown robot poses and scalability issues. The first two problems can be considered as an optimization problem of finding a consistent joint map based on robots’ relative poses and sensory data. This optimization problem exhibits a similar property of a singlerobot topological/metric mapping. To exploit this property, we propose a multi-robot SLAM (MR-SLAM) algorithm, which builds a graph-like topological map with vertices representing local metric maps and edges describing relative positions of adjacent local maps. In this MR-SLAM algorithm, the map fusion between two robots can be naturally done by adding an edge that connects two topological maps, and the estimation of relative robot pose is simply performed by optimizing this edge. For the third scalable problem, the proposed algorithm is also scalable to the number of robots and the size of an environment. Computer simulations with a public data set and experimental work on Pioneer 3-DX robots have been conducted to validate the performance of the proposed MR-SLAM algorithm.

Network delays and delay variations are two of the most important network performance metrics directly impacting real-time applications such as voice over IP and time-critical financial transactions. This importance is illustrated by past work on understanding the delay constancy of Internet paths and recent work on predicting network delays using virtual coordinate systems. Merely understanding currently observed delays is insufficient, as network performance can degrade not only due to traffic variability but also as a result of routing changes. Unfortunately this latter effect so far has been ignored in understanding and predicting delay related performance metrics of Internet paths. Our work is the first to address this short coming by systematically analyzing changes in network delays and jitter of a diverse and comprehensive set of Internet paths. Using empirical measurements, we illustrate that routing changes can result in roundtrip delay increase of converged paths by more than 1 second. Surprisingly, intradomain routing changes can also cause such large delay increase.

A fundamental challenge in improving file system performance is to design effective block replacement algorithms to minimize buffer cache misses. Despite the well-known interactions between prefetching and caching, almost all buffer cache replacement algorithms have been proposed and studied comparatively, without taking into account file system prefetching, which exists in all modern operating systems. This paper shows that such kernel prefetching can have a significant impact on the relative performance in terms of the number of actual disk l/Os of many well-known replacement algorithms; it can not only narrow the performance gap but also change the relative performance benefits of different algorithms. Moreover, since prefetching can increase the number of blocks clustered for each disk I/O and, hence, the time to complete the I/O, the reduction in the number of disk l/Os may not translate into proportional reduction in the total I/O time. These results demonstrate the importance of buffer caching research taking file system prefetching into consideration and comparing the actual disk l/Os and the execution time under different replacement algorithms.

In the past few years, peer-to-peer (P2P) networks have become a promising paradigm for building a wide variety of distributed systems and applications. The most popular P2P application till today is file sharing, e.g., Gnutella, Kazza, etc. These systems are usually referred to as unstructured, and search in unstructured P2P networks usually involves flooding or random walking. On the other hand, in structured P2P networks (DHTs), search is usually performed by looking up a distributed inverted index. The efficiency of the search mechanism is the key to the scalability of a P2P content sharing system. So far, neither unstructured nor structured P2P networks alone can solve the search problem in a satisfactory way. In this paper, we propose to combine the strengths of both unstructured and structured P2P networks to achieve more efficient search. Specifically, we propose to enhance search in unstructured P2P overlay networks by building a partial index of shared data using a structured P2P network. The index maintains two types of information: the top interests of peers and globally unpopular data, both characterized by data properties. The proposed search protocol, assisted search with partial indexing, makes use of the index to improve search in three ways: first, the index assists peers to find other peers with similar interests and the unstructured search overlay is formed to reflect peer interests. Second, the index also provides search hints for those data difficult to locate by exploring peer interest locality, and these hints can be used for second-chance search. Third, the index helps to locate unpopular data items. Experiments based on a P2P file sharing trace show that the assisted search with a lightweight partial indexing service can significantly improve the success rate in locating data than Gnutella and a hit-rate-based protocol in unstructured P2P systems, while incurring low search latency and overheads.

Traditionally, simultaneous localization and mapping (SLAM) algorithms solve the localization and mapping problem in explored regions. This paper presents a prediction-based SLAM algorithm (called P-SLAM), which has an environmental-structure predictor to predict the structure inside an unexplored region (i.e., look-ahead mapping). The prediction process is based on the observation of the surroundings of an unexplored region and comparing it with the built map of explored regions. If a similar environment/structure is matched in the map of explored regions, a hypothesis is generated to indicate that a similar structure has been explored before. If the environment has repeated structures, the mobile robot can use the predicted structure as a virtual mapping, and decide whether or not to explore the unexplored region to save the exploration time. If the mobile robot decides to explore the unexplored region, a correct prediction can be used to speed up the SLAM process and build a more accurate map. We have also derived the Bayesian formulation of P-SLAM to show its compact recursive form for real-time operation. We have experimentally implemented the proposed P-SLAM on a Pioneer 3-DX mobile robot using a Rao-Blackwellized particle filter in real time. Computer simulations and experimental results validated the performance of the proposed P-SLAM and its effectiveness in indoor environments

The stationary nature of nodes in a mesh network has shifted the main design goal of routing protocols from maintaining connectivity between source and destination nodes to finding high-throughput paths between them. In recent years, numerous link-quality-based routing metrics have been proposed for choosing high-throughput paths for unicast protocols. In this paper we study routing metrics for high-throughput tree or mesh construction in multicast protocols. We show that there is a fundamental difference between unicast and multicast routing in how data packets are transmitted at the link layer, and accordingly there is a difference in how the routing metrics for each of these primitives are designed. We adapt certain routing metrics for unicast for high-throughput multicast routing and propose news ones not previously used for high-throughput. We then study the performance improvement achieved by using different link-quality-based routing metrics via extensive simulation and experiments on a mesh network testbed, using ODMRP as a representative multicast protocol. Our testbed experiment results show that ODMRP enhanced with linkquality routing metrics can achieve up to 17.5% throughput improvement as compared to the original ODMRP.

Internet distance prediction gives pair-wise latency information with limited measurements. Recent studies have revealed that the quality of existing prediction mechanisms from the application perspective is short of satisfactory. In this paper, we explore the root causes and remedies for this problem. Our experience with different landmark selection schemes shows that although selecting nearby landmarks can increase the prediction accuracy for short distances, it can cause the prediction accuracy for longer distances to degrade. Such uneven prediction quality significantly impacts application performance. Instead of trying to select the landmark nodes in some "intelligent" fashion, we propose a hierarchical prediction approach with straightforward landmark selection. Hierarchical prediction utilizes multiple coordinate sets at multiple distance scales, with the "right" scale being chosen for prediction each time. Experiments with Internet measurement datasets show that this hierarchical approach is extremely promising for increasing the accuracy of network distance prediction.

Traditionally, the SLAM problem solves the localization and mapping problem in explored and sensed regions. This paper presents a prediction-based SLAM algorithm (called P-SLAM), which has an environmental structure predictor to predict the structure inside an unexplored region (i.e., look-ahead mapping). The prediction process is based on the observation of the surroundings of an unexplored region and comparing it with the built map of explored regions. If a similar structure is matched in the map of explored regions, a hypothesis is generated to indicate that a similar structure has been explored before. If the environment has repeated structures, the mobile robot can utilize the predicted structure as a virtual mapping, and decide whether or not to explore the unexplored region to save exploration time. If the mobile robot decides to explore the unexplored region, a correct prediction can be utilized to localize the robot and speed up the SLAM process. We also derive the Bayesian formulation of P-SLAM to show its compact recursive form for real-time operation. We have experimentally implemented the proposed P-SLAM in a Pioneer 3-DX mobile robot using a Rao-Blackwellized particle filter in real-time. Computer simulations and experimental results validated the performance of the proposed P-SLAM and its effectiveness in an indoor environment

Mobile robots can be used in many applications, including exploration in an unknown area. Robots usually carry limited energy so energy conservation is vital. This paper presents an approach for energy-efficient robot exploration. Our approach determines the next target for the robot to visit based upon orientation information. The robot plans the path between the current position to the next target in an energy-efficient way. Our method reduces repeated coverage, a common problem for most existing utility-based target selecting methods. We conduct simulations for both random and structured environments, and compare our method with a utility-based method that chooses the middle cell from the widest opening. Results show that our method can reduce energy consumption by 42% and traveling distance by 41%

An important stage of wide-area systems and networking research is to prototype a system to understand its performance when deployed in the real Internet. A key requirement of prototyping is that results obtained from the prototype experiments be representative of the behavior if the system were deployed over nodes connected to commercial ISPs. Recently, distributed testbeds such as PlanetLab and RON have become increasingly popular for performing wide-area experimentation. However, such testbeds typically consist of a significant fraction of nodes with connectivity to research and education networks which potentially hinder their usability in prototyping systems.In this paper, we investigate the impact of testbeds with connectivity to research and education networks on the applications and network services so that such testbeds can be leveraged for evaluation and prototyping. Specifically, we investigate when the representativeness of wide-area experiments deployed on such testbeds is affected by studying the routing paths that applications use over such testbeds. We then investigate how the representativeness of wide-area experiments is affected by studying the performance properties of such paths. We further measure the impact of using such testbeds on application performance via application case studies. Finally, we propose a technique that uses the currently available testbeds but reduces their bias by exposing applications evaluated to network conditions more reflective of the conditions in the commercial Internet.

The nature of digital content is undergoing a radical transformation due to the growing infusion of user-generated content. Users that generate content have a strong motivation to actively promote their content in order to achieve publicity, recognition or to simply spread their viewpoints, knowledge and creations. Existing content sharing mechanisms available to such users, such as in P2P file sharing, are pull-based, relegating the user to a passive role. To enable active participation from users, we propose Promoter, a framework that enhances P2P file sharing systems to support content promotion in addition to the available pull-based content search. Promotion is enabled by publicizing a user's content to peers and disseminating the content by incentivizing peers to download and further propagate it.

Energy-efficient broadcast communication is an important problem in wireless ad hoc networks. Previously, minimum-energy broadcast that exploits the broadcast nature of radio transmission has been studied and shown to be NP-complete for omnidirectional antennas. In this paper, we investigate the minimum-energy broadcast problem under a wide spectrum of directional antenna models, including sectored antennas with fixed sectors and beamwidth and antenna array-based smart antennas with varying degrees of beam orientation and beamwidth. We first propose the RF design and implementation of each model, which suggests the practical parameters of antennas under that model. We then show that the minimum-energy broadcast problem under each of the antenna models is NP-complete. Lastly, we present a heuristic algorithm based on BIP for the above problem under each directional antenna model and experimentally compare the energy efficiency of using different directional antennas using these heuristics. Our results show that using antennas with adjustable orientation and variable beamwidth gives the best results. For such antennas, the scanning angle is the dominant factor in improving the quality of the broadcast trees. The number of antennas per node is not that critical to obtaining a better broadcast tree as long as it is large enough to cover the entire 360◦ around a node so as to prevent network partitioning.

Distance prediction algorithms use O(N) round trip time (RTT) measurements to predict the N2RTTs among N nodes. Distance prediction can be applied to improve the performance of a wide variety of Internet applications: for instance, to guide the selection of a download server from multiple replicas, or to guide the construction of overlay networks or multicast trees. Although the accuracy of existing prediction algorithms has been extensively compared using the relative prediction error metric, their impact on applications has not been systematically studied. In this paper, we consider distance prediction algorithms from an application's perspective to answer the following questions: (1) Are existing prediction algorithms adequate for the applications? (2) Is there a significant performance difference between the different prediction algorithms, and which is the best from the application perspective? (3) How does the prediction error propagate to affect the user perceived application performance? (4) How can we address the fundamental limitation (i.e., inaccuracy) of distance prediction algorithms? We systematically experiment with three types of representative applications (overlay multicast, server selection, and overlay construction), three distance prediction algorithms (GNP, IDES, and the triangulated heuristic), and three real-world distance datasets (King, PlanetLab, and AMP). We find that, although using prediction can improve the performance of these applications, the achieved performance can be dramatically worse than the optimal case where the real distances are known. We formulate statistical models to explain this performance gap. In addition, we explore various techniques to improve the prediction accuracy and the performance of prediction-based applications. We find that selectively conducting a small number of measurements based on prediction-based screening is most effective.

Peer-to-peer (P2P) cycle sharing over the Internet has become increasingly popular as a way to share idle cycles. A fundamental problem faced by P2P cycle sharing systems is how to incrementally monitor and verify, with low overhead, the execution of jobs submitted to a remote untrusted hosting machine, or cluster of machines. In this paper, we present the design and implementation of GripCop DSM, a novel incremental execution monitoring and verification scheme for software distributed shared memory (SDSM) programs running on remote clusters. Our scheme maximally leverages the shared memory abstraction provided by the SDSM system by extending the shared memory abstraction to the monitoring process by replicating one of the processes running on the host cluster to verify intermediate results at runtime. Our GripCop DSM employs two monitoring schemes: (i) a full-scale monitoring scheme that completely replicates the computation of a process running on the cluster; and (ii) a decoy monitoring scheme that deceives the host cluster into believing that full-scale monitoring is being performed without it ever actually being done, thereby incurring negligible overhead. Experiments show that the combined use of full-scale and decoy monitoring ensures faithful execution with low performance impact, even over a wide area network

Internet cycle sharing systems that utilize idle computing resources dramatically increase the available resources for high performance computing. Fraudulent resource providers, however, can subvert these systems. While previous research has investigated protection against resource providers that return bad results, we consider a different fraudulent behavior -- cycle short-changing -- in which the resource provider faithfully executes the submitted job, but using a smaller percentage of the CPU resources than he/she promises. To detect this short-changing, we propose CycleMeter, a tool that allows a remotely executing application to accurately monitor the percentage of CPU resources it is utilizing throughout its execution period. CycleMeter employs a microbenchmark to measure the instantaneous CPU utilization of the application, and employs a simple and practical mechanism for embedding the microbenchmark into the application. Our experimental results on three operating systems and uniprocessor and multiprocessor machines show that CycleMeter is portable, incurs a low overhead, and is highly effective in detecting a spectrum of cycle shortchanging behavior.

Wireless mesh networks (WMNs) have been proposed as an effective solution for ubiquitous last-mile broadband access. Three key factors that affect the usability of WMNs are high throughput, cost-effectiveness, and ease of deployability. In this paper, we propose DMesh, a WMN architecture that combines spatial separation from directional antennas with frequency separation from orthogonal channels to improve the throughput of WMNs. DMesh achieves this improvement without inhibiting cost-effectiveness and ease of deployability by utilizing practical directional antennas that are widely and cheaply available (e.g., patch and yagi) in contrast to costly and bulky smart beamforming directional antennas. Thus, the key challenge in DMesh is to exploit spatial separation from such practical directional antennas despite their lack of electronic steerability and interference nulling, as well as the presence of significant sidelobes and backlobes. In this paper, we study how such practical directional antennas can improve the throughput of a WMN. Central to our architecture is a distributed, directional channel assignment algorithm for mesh routers that effectively exploits the spatial and frequency separation opportunities in a DMesh network. Simulation results show that DMesh improves the throughput of WMNs by up to 231% and reduces packet delay drastically compared to a multiradio multichannel omni antenna network. A DMesh implementation in our 16-node 802.11b WMN testbed using commercially available practical directional antennas provides transmission control protocol throughput gains ranging from 31% to 57%

Reducing energy consumption has become one of the major challenges in designing future computing systems. This paper proposes a novel idea of using program counters to predict I/O activities in the operating system. It presents a complete design of program-counter access predictor (PCAP) that dynamically learns the access patterns of applications and predicts when an I/O device can be shut down to save energy. PCAP uses path-based correlation to observe a particular sequence of program counters leading to each idle period and predicts future occurrences of that idle period. PCAP differs from previously proposed shutdown predictors in its ability to: 1) correlate I/O operations to particular behavior of the applications and users, 2) carry prediction information across multiple executions of the applications, and 3) attain higher energy savings while incurring lower mispredictions. We perform an extensive evaluation study of PCAP using a detailed trace-driven simulation and an actual Linux implementation. Our results show that PCAP achieves lower average mispredictions and higher energy savings than the simple timeout scheme and the state-of-the-art learning tree scheme.

The use of wireless in local loop (WiLL) has generated considerable interest due to the advantages it offers such as ease and low cost of deployment and maintenance. With an increase in the number of subscribers in the network, it becomes expedient to employ spectrum reusability techniques such as the use of multihop relaying in order to improve the capacity of the wireless systems. Throughput enhanced wireless in local loop (TWiLL) is one such architecture that employs multihop relaying and shortcut relaying to reuse bandwidth in WiLL systems. Compared to other multihop wireless network architectures, TWiLL architecture assumes significance due to its potential use in fixed wireless broadband services such as LMDS (local multipoint distribution service) and MMDS (multichannel multipoint distribution system). Analysis of the call acceptance ratio (CAR) in multihop wireless architectures including TWiLL is nontrivial as the Erlang B formula no longer holds. In this paper, we build multidimensional Markov chains to analyze the performance of multihop wireless systems such as TWiLL that has multiple types of channels. We also compare the results of our analysis with results from simulations. We observe that multihop relaying and shortcut relaying lead to a significant increase in the CAR of WiLL systems. Also, the free space propagation model that is normally used to model the radio channel is a very unrealistic model and does not consider reflection, diffraction, scattering, and multipath propagation that hinder transmissions in WiLL systems. In this paper, we studied the effect of several realistic radio channel propagation models on the performance of the TWiLL system through analysis and simulations

Mobile robots can be used in many applications, such as carpet cleaning, search and rescue, and exploration. Many studies have been devoted to the control, sensing, and communication of robots. However, the deployment of robots has not been fully addressed. The deployment problem is to determine the number of groups unloaded by a carrier, the number of robots in each group, and the initial locations of those robots. This paper investigates robot deployment for coverage tasks. Both timing and energy constraints are considered; the robots carry limited energy and need to finish the tasks before deadlines. We build power models for mobile robots and calculate the robots' power consumption at different speeds. A speed-management method is proposed to decide the traveling speeds to maximize the traveling distance under both energy and timing constraints. Our method uses rectangle scanlines as the coverage routes, and solves the deployment problem using fewer robots. Finally, we provide an approach to consider areas with random obstacles. Compared with two simple heuristics, our solution uses 36% fewer robots for open areas and 32% fewer robots for areas with obstacles.

Since sensor data gathering is the primary functionality of sensor networks, it is important to provide a fault tolerant method for reasoning about sensed events in the face of arbitrary failures of nodes sending in the event reports. In this paper, we propose a protocol called TIBFIT to diagnose and mask arbitrary node failures in an event-driven wireless sensor network. In our system model, sensor nodes are organized into clusters with rotating cluster heads. The nodes, including the cluster head, can fail in an arbitrary manner generating missed event reports, false reports, or wrong location reports. Correct nodes are also allowed to make occasional natural errors. Each node is assigned a trust index to indicate its track record in reporting past events correctly. The cluster head analyzes the event reports using the trust index and makes event decisions. TIBFIT is analyzed and simulated using the network simulator ns-2 and its coverage evaluated with a varying number and varying intelligence of the malicious nodes. We show that once TIBFIT gathers enough system state, accurate event detection is possible even if more than 50% of the network nodes are compromised.

In this paper, we study the problem of providing fairness in multi-hop wireless infrastructure access. In such networks, it is well known that the use of current media access and transport protocols can result in severe unfairness and even starvation for flows originated from different numbers of hops away from a wired infrastructure point or gateway. In this paper, we study a different type of fairness that exists in such networks - flows initiated by nodes that are similar numbers of hops away from the gateway can experience significant unfairness, and such unfairness exists even for perfectly symmetrical node distribution and channel conditions. We denote such fairness as symmetrical fairness. We first provide a framework to characterize and measure symmetrical fairness. We then perform an extensive set of simulation experiments to quantify the causes of symmetrical unfairness. Finally, we develop and study a distributed routing algorithm that significantly improves the symmetrical fairness

Publish/Subscribe (pub/sub) is an important paradigm for distributed content delivery. Traditionally, there have been two approaches to supporting pub/sub service: subject-based and content-based. Content-based pub/sub allows fine-grained expressiveness, and thus is a more attractive solution for content dissemination. However, the performance of a content-based pub/sub network is bounded by the expensive matching cost of content messages. In this paper, we propose a hybrid approach capable of minimizing both the matching and forwarding overhead within the pub/sub network and the delay experienced by clients receiving the content. The hybrid approach aims to eliminate redundant matching and forwarding inside the pub/sub network. In particular, it identifies a number of virtual groups by exploring common subscription interests among clients, and messages for each virtual group are only matched once at the group entry point. In addition, for each virtual group, the content delivery tree embedded in the underlying pub/sub network can benefit from shortcutting forwarding-only paths. Simulations have shown that the hybrid approach is highly effective in improving the service efficiency and quality of a content-based pub/sub system.

Mobile robot teams have many useful applications such as search and rescue, exploration and hazard detection and analysis. Communication between the robots of a team as well as between the robots and a human operator or controller are useful for many applications. Many applications of mobile robots involve scenarios in which no communication infrastructure such as base stations exist (e.g. demining in battlefields) or the existing infrastructure is damaged (e.g. search and rescue after an earthquake). In such scenarios, it is necessary for mobile robots to form an ad hoc network to enable communication by forwarding each other’s packets. In many applications, group communication can be used for flexible control, organization, and management of the mobile robots. Multicast provides a bandwidth efficient communication method between a source and a group of robots. In this paper, we propose an efficient multicast protocol MRMM (Mobile Robot Mesh Multicast) for deployment in mobile robot networks. MRMM exploits the fact that mobile robots know what velocity they are instructed to move at and for what distance in building a long lifetime sparse mesh for group communication that is more efficient. Our results show that MRMM provides an efficient group communication mechanism that can potentially be used in many mobile robot application scenarios.

Mobile multi-robot teams are useful in many critical applications such as search and rescue. Explicit communication among robots in such mobile multi-robot teams is useful for the coordination of such teams as well as exchanging data. Since many applications for mobile robots involve scenarios in which communication infrastructure may be damaged or unavailable, mobile robot teams frequently need to communicate with each other by using ad hoc networking. In such scenarios, energy efficient routing protocols to deliver messages among robots are a key requirement. In this paper, we propose and evaluate two routing protocols tailored for use in ad hoc networks formed by mobile multi-robot teams: Mobile Robot Distance Vector (MRDV) and Mobile Robot Source Routing (MRSR). Both protocols exploit the unique mobility characteristics of mobile robot networks to perform efficient routing. Our simulation study show that both MRDV and MRSR incur lower overhead while operating in mobile robot networks when compared to traditional mobile ad hoc network routing protocols such as DSR and AODV.

Mobile robots usually carry limited energy and have to accomplish their tasks before deadlines. Examples of these tasks include search and rescue, landmine detection, and carpet cleaning. Many researchers have been studying control, sensing, and coordination for these tasks. However, one major problem has not been fully addressed: the initial deployment of mobile robots. The deployment problem considers the number of robots needed and their initial locations. In this paper, we present a solution for the deployment problem when robots have limited energy and time to collectively accomplish coverage tasks. Simulation results show that our method uses 26% fewer robots comparing with two heuristics for covering the same size of area.

Geographic routing protocols allow stateless routing in mobile ad hoc networks (MANETs) by taking advantage of the location information of mobile nodes and thus are highly scalable. A central challenge in geographic routing protocols is the design of scalable distributed location services that track mobile node locations. A number of location services have been proposed, but little is known about the relative performance of these location services. In this paper, we perform a detailed performance comparison of three rendezvous-based location services that cover a range of design choices: a quorum-based protocol (XYLS) which disseminates each node's location to O(/spl radic/N) nodes, a hierarchical protocol (GLS) which disseminates each node's location to O(logN) nodes, and a geographic hashing based protocol (GHLS) which disseminates each node's location to O(1) nodes. We present a quantitative model of protocol overheads for predicting the performance tradeoffs of the protocols for static networks. We then analyze the performance impact of mobility on these location services. Finally, we compare the performance of routing protocols equipped with the three location services with two topology-based routing protocols, AODV and DSR, for a wide range of network sizes. Our study demonstrates that when practical MANET sizes are considered, robustness to mobility and the constant factors matter more than the asymptotic costs of location service protocols. In particular, while GLS scales better asymptotically, GHLS is far simpler, transmits fewer control packets, and delivers more data packets than GLS when used with geographic routing in MANETs of sizes considered practical today and in the near future. Similarly, although XYLS scales worse asymptotically than GLS, it transmits fewer control packets and delivers more data packets than GLS in large mobile networks.

This paper proposes to improve search in unstructured peer-to-peer (P2P) overlay networks by building a partial index of shared data. The index maintains two types of information: the top interests of peers and globally unpopular data, both characterized by data properties. The proposed search protocol, assisted search with partial indexing, makes use of the index to improve search in three ways. First, the index assists peers to find other peers with similar interests and the unstructured search overlay is formed to reflect peer interests. Second, the index also provides search hints for those data difficult to locate by exploring peer interest locality, and these hints can be used for second-chance search. Third, the index helps to locate unpopular data items. Experiments based on both the Web and P2P file sharing traces show that the assisted search with a lightweight partial indexing service can significantly improve the success rate and search speed in locating data, while inducing less traffic overhead than Gnutella and a hit-rate based protocol in unstructured P2P systems.

Mobile robots provide new opportunities for research in environment sensing. By combining sensors and robots, we can develop applications to enhance security, search and rescue, and detect hazardous materials. One important problem is to use fewer mobile sensors to cover an area. This paper focuses on two problems in robot sensor deployment: speed management and detouring distance under energy and timing constraints. We determine the robots' traveling speed based on the remaining energy and remaining time before deadline. We use probabilistic models for environments with obstacles and propose an empirical analysis to estimate the extra traveling distance due to detouring. We compute the number of robots (fleet size) needed for cover an area and our approach reduces the fleet size. Compared with two simple heuristics, our method uses 21% fewer robots.

The increased popularity of grid systems and cycle sharing across organizations requires scalable systems that provide facilities to locate resources, to be fair in the use of those resources, and to monitor jobs executing on remote systems. This paper describes the GridCop system which allows a computation on a remote, and potentially fraudulent, host system to be monitored for progress and execution correctness. A novel feature of our system is that it constructs cooperating submitter and host programs from the original program, and these programs allow both progress and execution correctness to be monitored with negligible overhead while providing protection against common fraudulent behaviors. Experimental results show that the overhead of this monitoring is low on both the submitting and host machines. We describe compiler algorithms that allow the required monitoring code to be automatically generated.

A fundamental challenge in improving the file system performance is to design effective block replacement algorithms to minimize buffer cache misses. Despite the well-known interactions between prefetching and caching, almost all buffer cache replacement algorithms have been proposed and studied comparatively without taking into account file system prefetching which exists in all modern operating systems. This paper shows that such kernel prefetching can have a significant impact on the relative performance in terms of the number of actual disk I/Os of many well-known replacement algorithms; it can not only narrow the performance gap but also change the relative performance benefits of different algorithms. These results demonstrate the importance for buffer caching research to take file system prefetching into consideration.

Reducing energy consumption has become one of the major challenges in designing future computing systems. We propose a novel idea of using program counters to predict I/O activities in the operating system. We present a complete design of program-counter access predictor (PCAP) that dynamically learns the access patterns of applications and predicts when an I/O device can be shut down to save energy. PCAP uses path-based correlation to observe a particular sequence of program counters leading to each idle period, and predicts future occurrences of that idle period. PCAP differs from previously proposed shutdown predictors in its ability to: (1) correlate I/O operations to particular behavior of the applications and users, (2) carry prediction information across multiple executions of the applications, and (3) attain better energy savings while incurring low mispredictions.

In this paper, we investigate energy-time-efficient dispatching methods for ant-like robots to cover an unmapped region effectively. These ant-like robots have very limited energy and sensor ability, making them practical and inexpensive to build. Our dispatching model was based on bio-inspired algorithms from an ant colony system. We assumed that all the ant-like robots start from their home starting point, the nest, and the region is composed of floor tiles that can be modelled as vertices in a graph. In this dispatching system, the ant-like robots leave pheromone on the tiles and use this information to cover the region. We developed and analyzed two different adaptive dispatching algorithms with different communication methods to the nest. We further compared these two adaptive dispatching algorithms with two non-adaptive methods. Extensive computer simulations validated the proposed adaptive algorithms, showing that they can dispatch ant-like mobile robots to cover an unmapped region with energy-time efficiency.

We study the problem of supporting communication in mobile sensor networks formed by teams of mobile robots equipped with sensors. We assume that in addition to communicating with each other by implicit or environmental means, the robots are equipped with wireless communication capability and effectively form a mobile ad hoc network (MANET). However, unlike typical MANETs where the primary communication pattern is any-to-any, such mobile multi-robot sensing networks need to support sensing applications which exhibit a many-to-one communication pattern. We evaluate the ability of current ad hoc network routing protocols to support communication in such sensing networks using detailed simulations of 50 robots. We consider typical communication patterns that arise in sensing applications and their impact on success rates, routing overhead, and energy costs of the mobile sensor network.

This paper presents a new approach to find energy-efficient motion plans for mobile robots. Motion planning has two goals: finding the routes and determining the velocities. We model the relationship of motors' speed and their power consumption with polynomials. The velocity of the robot is related to its wheels' velocities by performing a linear transformation. We compare the energy consumption of different routes at different velocities and consider the energy consumed for acceleration and turns. We use experiment-validated simulation to demonstrate up to 51% energy savings for searching an open area.

Simultaneous localization and map building (SLAM) is a fundamental and complex problem in mobile robot research. In SLAM, Kalman-filter-like implementations are widely adopted to localize a mobile robot and build a map simultaneously and incrementally. However, this approach requires extensive computations of order O(N/sup 2/), where N is the total number of landmarks. To make the computations more manageable, we propose a logarithmic map partitioning algorithm that partitions the global map into one local region and several sub-maps. The size of each sub-map is based on its distance from the mobile robot, and in each sub-map, a centroid landmark is selected to represent all the landmarks in the sub-map for SLAM computations. With this logarithmic-map partitioning, it maintains correlation updates with each sub-map and provides an efficient suboptimal solution to the SLAM problem. The number of landmarks reduces from N to a logarithm-based function of N, and the computational requirement reduces from O(N/sup 3/) to O(N/sup 2/), where N/sub L/ is the number of local landmarks. Furthermore, utilizing the compressed extended Kalman filter, the real-time computational complexity reduces to O(N/sub L//sup 2/). Computer simulation results showed that the proposed algorithm is consistent and efficient for a large number of landmarks.

As robotics technologies improve, mobile robots can be used in many applications. A fundamental question is to decide the number of robots needed (i.e., the "fleet-size problem") to accomplish tasks. Previous studies did not consider the energy constraints of the fleet size problem. In this paper, we present a probabilistic method to decide the fleet size for serving random requests. A simplification method is provided for fast computation. Our method is computationally efficient, with an average of 4% errors validated by an event-driven simulator.

In this paper, we examine the communication model widely used in simulation studies of mobile ad hoc networks (MANETs). We find that the communication model uses an overly simplistic traffic pattern which restricts the number of connections that originate from each source node to be one or two, and thus the communication model may not represent traffic patterns in many potential applications in MANETs. We then propose a new communication model which extends the previous communication model to include a more general traffic pattern that varies the number of connections per source node. We study the performance impact of traffic patterns on various routing protocols via detailed simulations of a MANET of 112 mobile nodes. Our simulation results show that many of the conclusions drawn in previous protocol comparison studies no longer hold under the new communication model. These results motivate the need for performance evaluation of MANETs to not only include rich and diverse mobility models as has been done in the past but also include diverse traffic patterns that stress a wide set of protocol design issues.

This paper presents Kosha, a peer-to-peer (p2p) enhancement for the widely-used Network File System (NFS). Kosha harvests redundant storage space on cluster nodes and user desktops to provide a reliable, shared file system that acts as a large storage with normal NFS semantics. P2p storage systems provide location transparency, mobility transparency, load balancing, and file replication - features that are not available in NFS. On the other hand, NFS provides hierarchical file organization, directory listings, and file permissions, which are missing from p2p storage systems. By blending the strengths of NFS and p2p storage systems, Kosha provides a low overhead storage solution. Our experiments show that compared to unmodified NFS, Kosha introduces a 4.1% fixed overhead and 1.5% additional overhead as nodes are increased from one to eight. For larger number of nodes, the additional overhead increases slowly. Kosha achieves load balancing in distributed directories, and guarantees 99.99% or better file availability.

Multicast avoids sending repeated packets over the same network links and thus offers the promise of supporting multimedia streaming over wide-area networks. Previously, two opposite multicast schemes -- forward-path forwarding and reverse-path forwarding -- have been proposed on top of structured peer-to-peer (p2p) overlay networks. This paper presents Borg, a new scalable application-level multicast system built on top of p2p overlay networks. Borg is a hybrid protocol that exploits the asymmetry in p2p routing and leverages the reverse-path multicast scheme for its low link stress on the physical networks. Borg has been implemented on top of Pastry, a generic, structured p2p routing substrate. Simulation results based on a realistic network topology model shows that Borg induces significantly lower routing delay penalty than both forward-path and reverse-path multicast schemes while retaining the low link stress of the reverse-path multicast scheme.

Condor provides high throughput computing by leveraging idle-cycles on off-the-shelf desktop machines. It also supports flocking, a mechanism for sharing resources among Condor pools. Since Condor pools distributed over a wide area can have dynamically changing availability and sharing preferences, the current flocking mechanism based on static configurations can limit the potential of sharing resources across Condor pools. This paper presents a technique for resource discovery in distributed Condor pools using peer-to-peer mechanisms that are self-organizing, fault-tolerant, scalable, and locality-aware. Locality-awareness guarantees that applications are not shipped across long distances when nearby resources are available. Measurements using a synthetic job trace show that self-organized flocking reduces the maximum job wait time in queue for a heavily loaded pool by a factor of 10 compared to without flocking. Simulations of 1000 Condor pools are also presented and the results confirm that our technique discovers and utilizes nearby resources in the physical network.

We present a new run-time system that supports object sharing in a distributed system. The key insight in this system is that a handle-based implementation of such a system enables efficient and transparent sharing of data with both fine- and coarse-grained access patterns. In addition, it supports efficient execution of garbage-collected programs. In contrast, conventional distributed shared memory (DSM) systems are limited to providing only one granularity with good performance, and have experienced difficulty in efficiently supporting garbage collection. A safe language, in which no pointer arithmetic is allowed, can transparently be compiled into a handle-based system and constitutes its preferred mode of use. A programmer can also directly use a handle-based programming model that avoids pointer arithmetic on the handles, and achieve the same performance but without the programming benefits of a safe programming language. This new run-time system, DOSA (Distributed Object Sharing Architecture), provides a shared object space abstraction rather than a shared address space abstraction. The key to its efficiency is the observation that a handle-based distributed implementation permits VM-based access and modification detection without suffering false sharing for fine-grained access patterns. We compare DOSA to TreadMarks, a conventional DSM system that is efficient at handling coarse-grained sharing. The performance of fine-grained applications and garbage-collected applications is considerably better than in TreadMarks, and the performance of coarse-grained applications is nearly as good as in TreadMarks. Inasmuch as the performance of such applications is already good in TreadMarks, we consider this an acceptable performance penalty.

This paper sketches the design of NLS, a scalable naming and location service, and presents an analysis and evaluation of its scalability. NLS resolves textual names to a nearby instance of a set of replicated objects associated with that name, and is designed to scale to the dimensions of a world-wide service. Applications include resolving Web URIs (uniform resource identifiers) to the nearest cached or replicated objects that provide the associated content. The key design goals of NLS are scalability, performance, availability and ease of administration. NLS is based on a dynamically configured, distributed search tree, with a fat-tree based topology at the global layer and spanning trees at the local layer. Analysis and preliminary empirical results obtained with a prototype implementation indicate that the system scales as expected.

We demonstrate that data reordering can substantially improve the performance of fine-grained irregular shared-memory benchmarks, on both hardware and software shared-memory systems. In particular, we evaluate two distinct data reordering techniques that seek to co-locate in memory objects that are in close proximity in the physical system modeled by the computation. The effects of these techniques are increased spatial locality and reduced false sharing. We evaluate the effectiveness of the data reordering techniques on a set of five irregular applications from SPLASH-2 and Chaos. We implement both techniques in a small library, allowing us to enable them in an application by adding less than 10 lines of code. Our results on one hardware and two software shared-memory systems show that, with data reordering during initialization, the performance of these applications is improved by 12%-99% on the Origin 2000, 30%-366% on TreadMarks, and 14%-269% on HLRC.

The high performance Fortran (HPF) benchmark suite HPFBench is designed for evaluating the HPF language and compilers on scalable architectures. The functionality of the benchmarks covers scientific software library functions and application kernels that reflect the computational structure and communication patterns in fluid dynamic simulations, fundamental physics, and molecular studies in chemistry and biology. The benchmarks are characterized in terms of FLOP count, memory usage, communication pattern, local memory accesses, array allocation mechanism, as well as operation and communication counts per iteration. The benchmarks output performance evaluation metrics in the form of elapsed times, FLOP rates, and communication time breakdowns. We also provide a benchmark guide to aid the choice of subsets of the benchmarks for evaluating particular aspects of an HPF compiler. Furthermore, we report an evaluation of an industry-leading HPF compiler from the Portland Group Inc. using the HPFBench benchmarks on the distributed-memory IBM SP2

In this paper, we compare the performance of two multiple-writer protocols based on lazy release consistency. In particular, we compare the performance of Princeton's home-based protocol and TreadMarks' protocol on a 32-processor platform. We found that the performance difference between the two protocols was less than 4% for four out of seven applications. For the three applications on which performance differed by more than 4%, the TreadMarks protocol performed better for two because most of their data were migratory, while the home-based protocol performed better for one. For this one application, the explicit control over the location of data provided by the home-based protocol resulted in a better distribution of communication load across the processors. These results differ from those of a previous comparison of the two protocols. We attribute this difference to (1) a different ratio of memory to network bandwidth on our platform and (2) lazy diffing and request overlapping, two optimizations used by TreadMarks that were not used in the previous study.

We describe an implementation of a sizable subset of OpenMP on networks of workstations (NOWs). By extending the availability of OpenMP to NOWs, we overcome one of its primary drawbacks compared to MPI, namely lack of portability to environments other than hardware shared memory machines. In order to support OpenMP execution on NOWs, our compiler targets a software distributed shared memory system (DSM) which provides multi-threaded execution and memory consistency. This paper presents two contributions. First, we identify two aspects of the current OpenMP standard that make an implementation on NOWs hard, and suggest simple modifications to the standard that remedy the situation. These problems reflect differences in memory architecture between software and hardware shared memory and the high cost of synchronization on NOWs. Second, we present performance results of a prototype implementation of an OpenMP subset on a NOW, and compare them with hand-coded software DSM and MPI results for the same applications on the same platform. We use five applications (ASCI Sweep3d, NAS 3D- FFT, SPLASH-2 Water, QSORT, and TSP) exhibiting various styles of parallelization, including pipelined execution, data parallelism, coarse-grained parallelism, and task queues. The measurements show little difference between OpenMP and hand-coded software DSM, but both are still lagging behind MPI. Further work will concentrate on compiler optimization to reduce these differences.

We present a general data parallel formulation for highly irregular problems in High Performance Fortran (HPF). Our formulation consists of(1) a method for linearizing irregular data structures (2) a data parallel implementation (in HPF) of graph partitioning algorithms applied to the linearized data structure, (3) techniques for expressing irregular communication and nonuniform computations associated with the elements of linearized data structures.We demonstrate and evaluate our formulation on a parallel, hierarchical N--body method for the evaluation of potentials and forces of nonuniform particle distributions. Our experimental results demonstrate that efficient data parallel (HPF) implementations of highly nonuniform problems are feasible with the proper language/compiler/runtime support. Our data parallel N--body code provides a much needed "benchmark" code for evaluating and improving HPF compilers.