CLIP is a seminal multimodal model that maps images and text into a shared representation space by contrastive learning on billions of image–caption pairs. Inspired by the rapid progress of large language models (LLMs), we investigate how the superior linguistic understanding and broad world knowledge of LLMs can further strengthen CLIP—particularly in handling long, complex captions. We introduce an efficient fine-tuning framework that embeds an LLM into a pretrained CLIP while incurring almost the same training cost as regular CLIP fine-tuning. Our method first “embedding-izes” the LLM for the CLIP setting, then couples it to the pretrained CLIP vision encoder through a lightweight adaptor trained on only a few million image–caption pairs. With this strategy we achieve large performance gains—without large-scale retraining—over state-of-the-art CLIP variants such as EVA02 and SigLIP-2. The LLM-enhanced CLIP delivers consistent improvements across a wide spectrum of downstream tasks, including linear-probe classification, zero-shot image–text retrieval with both short and long captions (in English and other languages), zero-shot/supervised image segmentation, object detection, and used as tokenizer for multimodal large-model benchmarks.

Text-to-video generation poses significant challenges due to the inherent complexity of video data, which spans both temporal and spatial dimensions. It introduces additional redundancy, abrupt variations, and a domain gap between language and vision tokens while generation. Addressing these challenges requires an effective video tokenizer that can efficiently encode video data while preserving essential semantic and spatiotemporal information, serving as a critical bridge between text and vision. Inspired by the observation in VQ-VAE-2, we propose HiTVideo, a novel approach for text-to-video generation with hierarchical tokenizers. It utilizes a 3D causal VAE with a multi-layer discrete token framework, encoding video content into hierarchically structured codebooks. Higher layers capture semantic information with higher compression, while lower layers focus on fine-grained spatiotemporal details, striking a balance between compression efficiency and reconstruction quality. Our approach efficiently encodes longer video sequences (e.g., 8 seconds, 64 frames), reducing bits per pixel (bpp) by approximately 70% compared to previous tokenizers, while maintaining competitive reconstruction quality. We explore the trade-offs between compression and reconstruction, while emphasizing the advantages of high-compressed semantic tokens in text-to-video tasks. HiTVideo aims to address the potential limitations of existing video tokenizers in text-to-video generation tasks, striving for higher compression ratios, improved token quality, and simplify LLMs modeling under language guidance, offering a scalable and promising framework for advancing text to video generation.

Low Earth Orbit (LEO) satellite communication is a promising approach to providing Internet connectivity to users in many remote areas. As videos are likely to account for most traffic in the LEO satellite network, as in the rest of the Internet, this work introduces a novel video-aware mobility management framework tailored for LEO satellite networks. Utilizing simulation models alongside real-world datasets, we show the importance of handoff strategy and throughput prediction algorithms in single-user and multi-user video streaming scenarios. Motivated by these observations, we propose a set of novel algorithms that can jointly choose the satellite and video bitrate to optimize the Quality of Experience (QoE). We first develop Model Predictive Control (MPC) and Reinforcement Learning (RL) based algorithms for a single user, and then extend them to accommodate multiple competing users that may share the same satellite. We introduce centralized training and distributed inference for our RL design, enabling a distributed policy informed by a global perspective. We demonstrate the effectiveness of our proposed models using trace-driven simulation and testbed experiments. We share our code and data with the research community.

With the rapid growth of IoT and AIoT applications, the demand for customized hardware is surging, yet PCB design for IoT devices remains a heavily manual, GUI-centric process that requires significant expertise in circuit and tools. This creates a widening gap between the accelerated software development and the difficulty of realizing corresponding hardware, making PCB-based hardware a critical bottleneck for system innovation. We present IoTGen, an LLM-driven agentic system that generates IoT PCB designs directly from natural-language demands. IoTGen introduces semantic-rich programming abstractions that capture schematic construction, enabling a domain-specialized language model to synthesize schematics with code. It further integrates a semantic component retrieval algorithm that combines LLM understanding with vector-based search, and an LLM-guided hybrid layout procedure that coordinates auto-routing tools to produce PCB layouts suitable for fabrication. We evaluate IoTGen on a dataset of diverse IoT designs, achieving a high component matching accuracy of 90%, a schematic generation success rate of 82%, and significant layout improvement. Case studies further demonstrate its capability to generate IoT PCB designs while substantially reducing the human effort and domain expertise required for hardware development. We release IoTGen to facilitate further research.

RF hardware design is a complicated, time-consuming, and expertise-bound process, which constrains the development and adoption of hardware innovation. Manual workflows do not scale to emerging wireless applications, while existing design generation strategies, e.g., learning-based approaches, lack training efficiency and generalizability across hardware types, frequency bands, operation modes, and substrate materials. In this paper, we present AutoRF, the first agentic framework for automated RF hardware design, supporting metasurfaces and antennas. It allows users to specify their demands and generate corresponding designs. We introduce extensible design abstractions to enable a modular framework. The core of the framework is an efficient and generalizable algorithm for design search and optimization, which utilizes LLMs to drive both circuit model simulator and EM simulator. To boost reliability and performance, we propose custom programming interfaces and a rule reviewer agent as feedback sources to train a specialized LLM. Evaluation demonstrates high success rate and significant optimization speedup; case studies with fabricated metasurface and antennas, ranging from 2.4 GHz to sub-THz, illustrate an ability to derive novel designs for next-generation wireless infrastructure.

Wireless sensing is an emerging technology with a wide range of applications, but most existing systems capture only the motion of a single point, such as in respiration monitoring. This limitation is critical for tasks requiring multi-point data, such as respiratory volume measurement, where different body points provide distinct information, and a single point cannot represent them all. In this paper, we propose LiSen, a smartphone-integrated LiDAR system for multi-point wireless sensing, and demonstrate its contact-free capability for measuring respiratory volume. LiSen uses smartphone LiDAR to track multiple chest and abdominal points, enabling the first ranging-based spirometer system that captures the full volume curve without new-user calibration. We leverage the unique feature of multi-point sensing to address challenges such as body interference, diverse breathing patterns, and pressure differences. Tests with 35 examinees show that LiSen accurately estimates both instantaneous forced expiratory and inspiratory volume, achieving mean absolute errors below 0.24 L and 0.30 L, respectively, and an 8.93% error for four common pulmonary function indices.

Many sensing tasks, such as plant stress sensing and blood pressure estimation, require co-located multi-modal measurements from two to five sensors at one site. RF backscatter enables low-power sensing, but existing tags usually support only one sensor; using multiple tags increases footprint and antenna coupling. We present Matrix, a fully-analog single-chain backscatter tag that supports multiple onboard sensors by multiplexing them into a composite voltage for transmission through one analog modulation chain. Unlike time-division polling, which introduces inter-sensor sampling offsets, or frequency-division, which requires separate chains, Matrix uses voltage-division multiplexing. Each sensor is encoded as a PWM waveform whose duty cycle represents the measurement, while amplitude enables multiplexing. Binary-weighted voltage-division weights make each active-sensor set uniquely invertible for reliable demultiplexing. The composite voltage is then converted into backscatter frequency shifts through the same chain. At the receiver, Matrix uses a Hidden Markov Model to recover per-sensor readings. Its ASIC consumes 25.56μW. A five-sensor prototype achieves 20 dB average reconstruction SNR at 30 kHz sampling, and we validate Matrix in plant sensing, health monitoring, and microphone-based direction finding.

Large language models (LLMs) enable longcontext tasks but face efficiency challenges due to the growing key-value (KV) cache.We propose LeanK, a learning-based method that prunes unimportant key (K) cache channels by leveraging static channel sparsity.With a novel two-stage training process, LeanK learns channel-wise static mask that could satisfy specific sparsity ratio and hardware alignment requirement.LeanK reduces GPU memory and accelerates decoding without sacrificing accuracy.Experiments demonstrate up to 70% K cache and 16%-18% V cache memory reduction.Custom decoding kernel enables 1.3x speedup for attention computation.We also provide insights into model channels and attention heads during long-context inference by analyzing the learned importance distribution.Our code is available at https://aka.ms/LeanK.

Long-context Large Language Models (LLMs) have enabled numerous downstream applications but also introduced significant challenges related to computational and memory efficiency. To address these challenges, optimizations for long-context inference have been developed, centered around the KV cache. However, existing benchmarks often evaluate in single-request, neglecting the full lifecycle of the KV cache in real-world use. This oversight is particularly critical, as KV cache reuse has become widely adopted in LLMs inference frameworks, such as vLLM and SGLang, as well as by LLM providers, including OpenAI, Microsoft, Google, and Anthropic. To address this gap, we introduce SCBENCH (SharedContextBENCH), a comprehensive benchmark for evaluating long-context methods from a KV cache centric perspective: 1) KV cache generation, 2) KV cache compression, 3) KV cache retrieval, and 4) KV cache loading. Specifically, SCBench uses test examples with shared context, ranging 12 tasks with two shared context modes, covering four categories of long-context capabilities: string retrieval, semantic retrieval, global information, and multi-task. With SCBench, we provide an extensive KV cache-centric analysis of eight categories long-context solutions, including Gated Linear RNNs (Codestal-Mamba), Mamba-Attention hybrids (Jamba-1.5-Mini), and efficient methods such as sparse attention, KV cache dropping, quantization, retrieval, loading, and prompt compression. The evaluation is conducted on six Transformer-based long-context LLMs: Llama-3.1-8B/70B, Qwen2.5-72B/32B, Llama-3-8B-262K, and GLM-4-9B. Our findings show that sub-O(n) memory methods suffer in multi-turn scenarios, while sparse encoding with O(n) memory and sub-O(n^2) pre-filling computation perform robustly. Dynamic sparsity yields more expressive KV caches than static patterns, and layer-level sparsity in hybrid architectures reduces memory usage with strong performance. Additionally, we identify attention distribution shift issues in long-generation scenarios.

To deliver coherent and personalized experiences in long-term conversations, existing approaches typically perform retrieval augmented response generation by constructing memory banks from conversation history at either the turn-level, session-level, or through summarization techniques. In this paper, we explore the impact of different memory granularities and present two key findings: (1) Both turn-level and session-level memory units are suboptimal, affecting not only the quality of final responses, but also the accuracy of the retrieval process. (2) The redundancy in natural language introduces noise, hindering precise retrieval. We demonstrate that *LLMLingua-2*, originally designed for prompt compression to accelerate LLM inference, can serve as an effective denoising method to enhance memory retrieval accuracy. Building on these insights, we propose **SeCom**, a method that constructs a memory bank with topical segments by introducing a conversation **Se**gmentation model, while performing memory retrieval based on **Com**pressed memory units. Experimental results show that **SeCom** outperforms turn-level, session-level, and several summarization-based methods on long-term conversation benchmarks such as *LOCOMO* and *Long-MT-Bench+*. Additionally, the proposed conversation segmentation method demonstrates superior performance on dialogue segmentation datasets such as *DialSeg711*, *TIAGE*, and *SuperDialSeg*.

The integration of long-context capabilities with visual understanding unlocks unprecedented potential for Vision Language Models (VLMs). However, the quadratic attention complexity during the pre-filling phase remains a significant obstacle to real-world deployment. To overcome this limitation, we introduce MMInference (Multimodality Million tokens Inference), a dynamic sparse attention method that accelerates the prefilling stage for long-context multi-modal inputs. First, our analysis reveals that the temporal and spatial locality of video input leads to a unique sparse pattern, the Grid pattern. Simultaneously, VLMs exhibit markedly different sparse distributions across different modalities. We introduce a permutation-based method to leverage the unique Grid pattern and handle modality boundary issues. By offline search the optimal sparse patterns for each head, MMInference constructs the sparse distribution dynamically based on the input. We also provide optimized GPU kernels for efficient sparse computations. Notably, MMInference integrates seamlessly into existing VLM pipelines without any model modifications or fine-tuning. Experiments on multi-modal benchmarks-including Video QA, Captioning, VisionNIAH, and Mixed-Modality NIAH-with state-of-the-art long-context VLMs (LongVila, LlavaVideo, VideoChat-Flash, Qwen2.5-VL) show that MMInference accelerates the pre-filling stage by up to 8.3x at 1M tokens while maintaining accuracy. Our code is available at https://ama.ms/MMInference.

Non-invasive continuous glucose monitoring for diabetes patients remains challenging despite ongoing interest. This paper presents CGMM, a novel non-invasive wireless glucose monitoring system integrated into wearable devices. It features a specially designed metasurface that couples with the wearable's antenna and tissue fluid beneath the skin, amplifying frequency response changes caused by subtle glucose concentration variations. To address individual tissue variability and optimize the passive metasurface design, we develop a tunable metasurface and a one-shot calibration method to obtain the impedance for optimal resonance in glucose sensing environments with unknown parameters. The calibrated impedance is then used for the inverse design and fabrication of an economical passive metasurface. We implement prototypes of CGMM and conduct extensive experimental evaluations. In human experiments involving ten participants using the prototype with LibreVNA, the overall performance is quantified with relative errors ranging from -5.02% to 6.93% and an RMSE of 9.65 mg/dL.

With global population growth, sustainable agriculture requires efficient soil moisture sensing for precise irrigation. While commercial soil moisture sensors are often limited by cost and durability, state-of-the-art RF-based sensing solutions require additional signal transmitter infrastructure, hindering widespread adoption. To fill this gap, we introduce GPSoil—a novel soil moisture sensing system that leverages pervasive Global Navigation Satellite System (GNSS) signals. On the hardware side, we employ two antennas along with a low-cost RF switch, enabling error mitigation for long propagation distances by comparing the signals captured from both antennas. On the software side, we leverage the inherent clock drift errors in commercial GNSS sensors and turn them into tools for fine-grained value extraction, enabling high-resolution sensing from otherwise coarse data. By integrating hardware and software innovations, we successfully achieve practical soil moisture sensing using GNSS signals. Built with off-the-shelf components, GPSoil achieves a soil moisture accuracy of 5.2% at a material cost of only $10.56, making it far more affordable than existing systems. GPSoil can sense moisture up to one meter underground, far surpassing other RF-based sensing systems and meeting the needs of most crops and irrigation systems. This work pioneers the use of GNSS signals in agriculture, offering a scalable, low-cost solution for advancing precision irrigation and promoting sustainable agriculture.

Beyond communication, wireless signals have been extensively utilized for localization, tracking, and sensing in recent years. The key information extracted for these purposes includes distance and angle. While distance measurement accuracy is mainly limited by signal bandwidth, angle accuracy depends on the number of antennas and phase noise. Conventional approaches typically improve angle estimation by boosting signal strength and increasing the number of antennas. In this paper, we propose employing a quantum receiver to substantially improve angle estimation performance. Rather than amplifying signal strength, the quantum receiver reduces the inherent hardware noise. Furthermore, we exploit the unique properties of a quantum RF receiver to construct a multi-antenna quantum system. Using only two physical quantum antennas, we generate virtual antennas by leveraging the receiver's broad frequency range, effectively increasing the number of antennas and significantly improving angle measurement performance. Our experimental results demonstrate that, with only two quantum antennas, we achieve angle estimation performance surpassing that of a conventional RF receiver equipped with 40 antennas. Furthermore, quantum antennas are not constrained by the coupling effects that typically limit the spacing between conventional RF antennas, allowing for much closer placement. This represents a significant step toward reducing the size of antenna arrays while preserving localization and tracking performance.

Diffractive neural networks (NNs) have garnered attention for directly implementing wireless signal processing at the physical layer. However, they are limited by a constrained weight learning space and activation functions, which restricts their data processing capabilities. To address this, we propose an RF circuit-based weighted diffraction NN (WDNN) that rivals digital NNs in processing ability. We design a weighted asymmetric RF coupler unit that, when stacked into a network, enables diffractive propagation with arbitrary connection weights. Additionally, an activation module is introduced that utilizes RF amplifiers operating in their nonlinear regions. We validate the effectiveness of the proposed WDNN through three tasks: 32-level amplitude modulated (AM) signal decoding, 31-class angle of arrival (AoA) estimation, and 2-class Wi-Fi based fall detection. After training, WDNN achieves the accuracy of 98.5%, 93.7%, and 90.8% in the AM decoding, AoA estimation, and fall detection tasks, respectively; while the diffractive NN SOTA achieves only 21.6%, 16.9%, and 63.3%. We also implement the prototypes of WDNN and SOTA, and real-world experimental results demonstrate that our method achieves an average accuracy improvement of up to 76.85% across various tasks compared to SOTA.

Various wireless technologies have been utilized for sensing. Although promising, these wireless sensing technologies have inherent limitations. Prior research mainly focuses on overcoming the limitations of an individual wireless sensing technology, and little attention has been paid to the potential benefits of sensing with more than one wireless technology. In this paper, we introduce the concept of cross-technology sensing for the first time, and propose LoFiSen to enable LoRa-to-WiFi sensing. LoFiSen leverages the strengths of both LoRa and WiFi—combining LoRa's long-range capability with WiFi's pervasiveness. The chirp characteristic of LoRa signal significantly improves the sensing range of WiFi, and the widespread availability of WiFi devices makes LoRa sensing more pervasive. LoFiSen is fully compatible with LoRa and WiFi protocols, and can work on commodity LoRa and WiFi hardware. The key component of our design is enabling the WiFi receiver to capture fine-grained LoRa signal variations for sensing. Real-world experiments demonstrate that LoFiSen improves the WiFi sensing range for respiration monitoring from 8 m to 41 m, and pushes the walking sensing range from 16 m to 73.5 m. Through-wall passive respiration monitoring, previously infeasible with state-of-the-art WiFi sensing, is now possible with LoFiSen.

Transformer-based Large Language Models (LLMs) have become increasingly important. However, scaling LLMs to longer contexts incurs slow inference speed and high GPU memory consumption for caching key-value (KV) vectors. This paper presents RetrievalAttention, a training-free approach to both accelerate the decoding phase and reduce GPU memory consumption by pre-building KV vector indexes for fixed contexts and maintaining them in CPU memory for efficient retrieval. Unlike conventional KV cache methods, RetrievalAttention integrate approximate nearest neighbor search (ANNS) indexes into attention computation. We observe that off-the-shelf ANNS techniques often fail due to the out-of-distribution (OOD) nature of query and key vectors in attention mechanisms. RetrievalAttention overcomes this with an attention-aware vector index. Our evaluation shows RetrievalAttention achieves near full attention accuracy while accessing only 1-3\% of the data, significantly reducing inference costs. Remarkably, RetrievalAttention enables LLMs with 8B parameters to handle 128K tokens on a single NVIDIA RTX4090 (24GB), achieving a decoding speed of 0.107 seconds per token.

In this paper, we propose a novel learning paradigm, termed *Chain-of-Model* (CoM), which incorporates the causal relationship into the hidden states of each layer as a chain style. thereby introducing great scaling efficiency in model training and inference flexibility in deployment.We introduce the concept of *Chain-of-Representation* (CoR), which formulates the hidden states at each layer as a combination of multiple sub-representations (i.e., chains). In each layer, each chain from the output representations can only view all of its preceding chains in the input representations. Consequently, the model built upon CoM framework can progressively scale up the model size by increasing the chains based on the previous models (i.e., chains), and offer multiple sub-models at varying sizes for elastic inference by using different chain numbers. Based on this principle, we devise *Chain-of-Language-Model* (CoLM), which incorporates the idea of CoM into each layer of Transformer architecture. Based on CoLM, we further introduce CoLM-Air by introducing a *KV sharing* mechanism, that computes all keys and values within the first chain and then shares across all chains. This design demonstrates additional extensibility, such as enabling seamless LM switching, prefilling acceleration and so on. Experimental results demonstrate our CoLM family can achieve comparable performance to the standard Transformer, while simultaneously enabling greater flexiblity, such as progressive scaling to improve training efficiency and offer multiple varying model sizes for elastic inference, paving a a new way toward building language models.

This paper presents Babel, the expandable modality alignment model, specially designed for multi-modal sensing. While there has been considerable work on multi-modality alignment, they all struggle to effectively incorporate multiple sensing modalities due to the data scarcity constraints. How to utilize multi-modal data with partial pairings in sensing remains an unresolved challenge.

Acoustic tracking technology, leveraging the ubiquitous presence of speakers and microphones in commercial off-the-shelf (COTS) mobile devices, has become a versatile tool across various applications. However, current phase-based acoustic tracking methods encounter significant limitations in tracking fast movements, thereby restricting their practical utility. This paper identifies three practical challenges to enable fast hand motion tracking using acoustic signals: 1) high mobility, 2) low signal-to-noise ratio (SNR), and 3) variations in hardware frequency response. The high mobility introduces Doppler shift and phase ambiguity which is the primary cause of failure in fast movement tracking, while the latter two factors can further impair the tracking performance in practical scenarios involving high mobility. To address the high mobility issue, we effectively compensate the Doppler shift in the Channel Impulse Response (CIR) for better selection of channel taps and then propose a novel phase derivative approach to mitigate the phase ambiguity. To enhance the real-world robustness, we integrate multiple algorithms including an SNR enhancement algorithm inspired by time-domain beamforming and a hardware frequency response compensation approach that addresses both amplitude and phase distortions. Additionally, an LSTM-based distance reconstruction algorithm is further implemented to correct residual phase noise. Implemented on Android platforms under the name SwiftTrack+, our system demonstrates superior performance in tracking fast movements. Through extensive evaluations, SwiftTrack+ proves its efficacy across diverse scenarios, significantly broadening the scope and reliability of acoustic tracking applications.

Huiqiang Jiang, Qianhui Wu, Xufang Luo, Dongsheng Li, Chin-Yew Lin, Yuqing Yang, Lili Qiu. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

The performance of large language models (LLMs) is significantly influenced by the quality of the prompts provided.In response, researchers have developed enormous prompt engineering strategies aimed at modifying the prompt text to enhance task performance.In this paper, we introduce a novel technique termed position engineering, which offers a more efficient way to guide large language models.Unlike prompt engineering, which requires substantial effort to modify the text provided to LLMs, position engineering merely involves altering the positional information in the prompt without modifying the text itself.We have evaluated position engineering in two widely-used LLM scenarios: retrieval-augmented generation (RAG) and in-context learning (ICL).Our findings show that position engineering substantially improves upon the baseline in both cases.Position engineering thus represents a promising new strategy for exploiting the capabilities of large language models.

We introduce Nada, the first framework to autonomously design network algorithms by leveraging the generative capabilities of large language models (LLMs). Starting with an existing algorithm implementation, Nada enables LLMs to create a wide variety of alternative designs in the form of code blocks. It then efficiently identifies the top-performing designs through a series of filtering techniques, minimizing the need for full-scale evaluations and significantly reducing computational costs. Using adaptive bitrate (ABR) streaming as a case study, we demonstrate that Nada produces novel ABR algorithms---previously unknown to human developers---that consistently outperform the original algorithm in diverse network environments, including broadband, satellite, 4G, and 5G.

Programmable radio environments with metasurfaces introduce signal-level programmability to wireless networks, providing various services such as connectivity enhancement, coverage extension, sensing, security protection, and wireless powering. Next-generation wireless networks are set to widely deploy metasurfaces. However, the current one-system-per-use-case approach cannot scale with wide-ranging hardware designs and surface-aided applications. This paper presents a vision, SurfOS, a metasurface operating system for programmable radio environments. SurfOS aims to orchestrate heterogeneous surface hardware and provide diverse services for user-level applications. We discuss the challenges of building such a system, potential abstraction layers, and open research problems. Our early-stage implementation demonstrates the feasibility and benefits of this approach.

The popularity of 4K videos is on the rise. However, streaming such high-quality videos over mm Wave to several users presents significant challenges due to directional communication, fluctuating channels, and high bandwidth demands. To address these challenges, this paper introduces an innovative 4K layered video multicast streaming system. We (i) develop a video quality model tailored for layered video coding, (ii) optimize resource allocation, scheduling, and beamforming based on the channel conditions of different users, and (iii) design a streaming strategy that integrates fountain code to eliminate redundancy in multicast groups, coupled with a Leaky-Bucket approach for congestion control. We implement our system on Commodity-Off- The-Shelf (COTS) WiGig devices and demonstrate its effectiveness through comprehensive testbed and emulation experiments.

Depth estimation enables a wide variety of 3D applications, such as robotics and autonomous driving. Despite significant work on various depth sensors, it is challenging to develop an all-in-one method to meet multiple basic criteria. In this paper, we propose a novel audio-visual learning scheme by integrating semantic features with physical spatial cues to boost monocular depth with only one microphone. Inspired by the flash-to-bang theory, we develop FBDepth, the first passive audio-visual depth estimation framework. It is based on the difference between the time-of-flight (ToF) of the light and the sound. We formulate sound source depth estimation as an audio-visual event localization task for collision events. To approach decimeter-level depth accuracy, we design a coarse-to-fine pipeline to push the temporary localization accuracy from event-level to millisecond-level by aligning audio-visual correspondence and manipulating optical flow. FBDepth feeds the estimated visual timestamp together with the audio clip and objects visual features to regress the source depth. We use a mobile phone to collect 3.6K+ video clips with 24 different objects at up to 65m. FBDepth shows superior performance especially at a long range compared to monocular and stereo methods.

Wireless sensing is gaining increasing attention from both academia and industry. Various wireless signals, such as Wi-Fi, UWB, and acoustic signals, have been leveraged for sensing. While promising in many aspects, two critical limitations still exist: a) limited sensing coverage; and b) the requirement for dedicated sensing signals, which may interfere with the original function of the wireless technology. To address these issues, we propose to utilize GPS signals for sensing, as GPS signals are already pervasive and emitted from satellites 24/7 at pre-allocated frequency bands, causing no interference. To make GPS sensing possible, we reconstruct signals with amplitude and phase information which is critical for sensing using the raw measurements reported by commercial GPS receiver module. We also develop sensing models to tailor the unique properties of GPS signals such as extremely long transmission distance. Finally, we introduce the concept of distributed sensing and design signal processing methods to fuse signals from multiple satellites to improve sensing performance. With all these designs, we prototype the first GPS wireless sensing system on commercial GPS receiver modules. Comprehensive experiments demonstrate that the proposed system can realize meaningful sensing applications such as human activity sensing, passive trajectory tracking, and respiration monitoring.

This paper introduces a novel multi-directional speaker, named MuDiS, which utilizes a parametric array to generate highly focused sound beams in multiple directions. The system capitalizes on air nonlinearity to reproduce sound from ultrasounds, successfully overcoming challenges inherent in traditional parametric arrays, such as transducer size and wavefront shape. It supports three important features simultaneously: independent beams, wide-angle digital steering, and unintended leakage suppression. To address these challenges, we designed a specialized cell structure that connects ultrasonic transducers, redirecting an approximately omnidirectional wavefront with optimal interspacing. An optimization-based algorithm is developed to minimize unintended leakages, and a nonlinear distortion reduction scheme is proposed to enhance sound quality. The paper showcases a prototype demonstrating the system's capabilities as a multidirectional speaker with a wide sound projection angle. Experimental results validate the effectiveness of our approach. The proposed multi-beam projection system rivals the performance of commercially available single-beam projection directional speakers, and improved steering angle and sound fidelity compared to multi-beamforming performance using traditional parametric arrays.

mmWave networks offer wide bandwidth for high-speed wireless communication but suffer from limited range and susceptibility to blockage. Existing coverage provisioning solutions not only incur high costs but also require significant expert knowledge and manual efforts. In this paper, we present AutoMS, an automated service framework to optimize mmWave coverage by strategically designing and placing low-cost passive metasurfaces. Our approach consists of three key components: (1) joint optimization of metasurface phase configurations and placement as well as access point beamforming codebooks. (2) a fast 3D ray-tracing simulator for accelerated large-scale metasurface channel modeling. (3) a metasurface design amenable to ultra-low-cost hot stamping fabrication, featuring high reflectivity, near 2π phase control, and wideband support. Simulation and testbed experiments show that AutoMS can increase the median received signal strength by 11 dB in target rooms and over 20 dB at previous blind spots, and improve the median throughput by over 3× in real-world scenarios.

Microwave ovens have become an essential cooking appliance owing to their convenience and efficiency. However, microwave ovens suffer from uneven distribution of energy, which causes prolonged delays, unpleasant cooking experiences, and even safety concerns. Despite significant research efforts, current solutions remain inadequate. In this paper, we first conduct measurement studies to understand the energy distribution for 10 microwave ovens and show their energy distribution in both 2D and 3D is very skewed, with notably lower energy levels at the center of the microwave cavity, where food is commonly placed. To tackle this challenge, we propose a novel methodology to enhance the performance of microwave ovens. Our approach begins with the development of a measurement driven model of a microwave oven. We construct a detailed 3D model in the High Frequency Structure Simulator (HFSS) and use real temperature measurements from a microwave to derive critical parameters relevant to the appliance's functionality (e.g., operating frequency, waveguide specifications). We then develop a novel approach that optimizes the design and placement of a low-cost passive metasurface for a given heating objective. Using extensive experiments, we demonstrate the efficacy of our approach across diverse food, optimization objectives, and microwave ovens.

Global Navigation Satellite System (GNSS) is extensively utilized for outdoor positioning and navigation. However, achieving high-precision indoor positioning is challenging due to the significant attenuation of GNSS signals indoors. To address this issue, we propose an innovative indoor GNSS positioning system called GPMS, which uses passive metasurface technology to redirect GNSS signals from outdoors into indoor spaces. These passive metasurfaces are strategically optimized for indoor coverage by steering and scattering the GNSS signals across a wide range of incident angles. We further develop a novel localization algorithm that can determine which metasurface the signal goes through and localize the user using the set of metasurfaces as anchor points. A distinct advantage of our localization algorithm is that it can be implemented on existing mobile devices without any hardware modifications. We implement the prototype of GPMS, and deploy six metasurfaces in two indoor environments, a 10×50 m2 office floor and a 15×20 m2 lecture room, to evaluate system performance. In terms of coverage, our GPMS increases the C/N0 from 9.1 dB-Hz to 23.2 dB-Hz and increases the number of visible satellites from 3.6 to 21.5 in the office floor. In terms of indoor positioning accuracy, our proposed system decreases the absolute positioning error from 30.6 m to 3.2 m in the office floor, and from 11.2 m to 2.7 m in the lecture room, demonstrating the feasibility and benefits of metasurface-assisted GNSS for indoor positioning.

The past decade has witnessed a surge of interest in human respiration sensing with various wireless signals to achieve at-home smart health. While promising in many aspects, two critical limitations still exist: a) dedicated sensing signal transmitters are needed; b) existing sensing schemes affect the original function of the wireless technology such as communication. In this demo, we present the GPSense Respiration system, a new kind of contact-free respiration sensing system that breaks the above limitations. GPSense Respiration operates by receiving and analyzing the GNSS signals reflected by the human body without additional pre-deployed signal transmitters. Also, GPSense Respiration system will not affect wireless communications because GNSS signals operate at different frequencies than communication signals. This demo enables respiration monitoring for different users in real-time without any calibration.

While localization has gained a tremendous amount of attention from both academia and industry, much less attention has been paid to equally important orientation estimation. Traditional orientation estimation systems relying on gyroscopes suffer from cumulative errors. In this paper, we propose UWBOrient, the first fine-grained orientation estimation system utilizing ultra-wideband (UWB) modules embedded in smartphones. The proposed system presents an alternative solution that is more accurate than gyroscope estimates and free of error accumulation. We propose to fuse UWB estimates with gyroscope estimates to address the challenge associated with UWB estimation alone and further improve the estimation accuracy. UWBOrient decreases the estimation error from the state-of-the-art 7.6° to 2.7° while maintaining a low latency (20 ms) and low energy consumption (40 mWh). Comprehensive experiments with both iPhone and Android smartphones demonstrate the effectiveness of the proposed system under various conditions including natural motion, dynamic multipath and NLoS. Two real-world applications, i.e., head orientation tracking and 3D reconstruction are employed to showcase the practicality of UWBOrient.

Acoustic imaging is attractive due to its ability to work under occlusion, different lighting conditions, and privacy-sensitive environments. Existing acoustic imaging methods require large transceiver arrays or device movement, which makes it challenging to use in many scenarios. In this paper, we develop a novel acoustic imaging system for low-cost devices with few speakers and microphones without any device movement. To achieve this goal, we leverage a 3D-printed passive acoustic metasurface to significantly enhance the diversity of the measurement data, thereby improving the imaging quality. Specifically, we jointly design the transmission signal, transceivers' beamforming weights, metasurface, and imaging algorithm to minimize the imaging reconstruction error in an end-to-end manner. We further develop a scheme to dynamically adapt the imaging resolution based on the distance to the target. We implement a system prototype. Using extensive experiments, we show that our system yields high-quality images across a wide range of scenarios.

Web is increasingly becoming the primary platform to deliver AI services onto edge devices, making in-browser deep learning (DL) inference more prominent. Nevertheless, the heterogeneity of edge devices, combined with the underdeveloped state of Web hardware acceleration practices, hinders current in-browser inference from achieving its full performance potential on target devices.

The computational challenges of Large Language Model (LLM) inference remain a significant barrier to their widespread deployment, especially as prompt lengths continue to increase. Due to the quadratic complexity of the attention computation, it takes 30 minutes for an 8B LLM to process a prompt of 1M tokens (i.e., the pre-filling stage) on a single A100 GPU. Existing methods for speeding up prefilling often fail to maintain acceptable accuracy or efficiency when applied to long-context LLMs. To address this gap, we introduce MInference (Milliontokens Inference), a sparse calculation method designed to accelerate pre-filling of long-sequence processing. Specifically, we identify three unique patterns in long-context attention matrices-the A-shape, Vertical-Slash, and Block-Sparse-that can be leveraged for efficient sparse computation on GPUs. We determine the optimal pattern for each attention head offline and dynamically build sparse indices based on the assigned pattern during inference. With the pattern and sparse indices, we perform efficient sparse attention calculations via our optimized GPU kernels to significantly reduce the latency in the pre-filling stage of longcontext LLMs. Our proposed technique can be directly applied to existing LLMs without any modifications to the pre-training setup or additional fine-tuning. By evaluating on a wide range of downstream tasks, including InfiniteBench, RULER, PG-19, and Needle In A Haystack, and models including LLaMA-3-1M, GLM-4-1M, Yi-200K, Phi-3-128K, and Qwen2-128K, we demonstrate that MInference effectively reduces inference latency by up to 10x for pre-filling on an A100, while maintaining accuracy. Our code is available at https://aka.ms/MInference.

Online video streaming has fundamental limitations on the transmission bandwidth and computational capacity and super-resolution is a promising potential solution. However, applying existing video super-resolution methods to online streaming is non-trivial. Existing video codecs and streaming protocols (e.g., WebRTC) dynamically change the video quality both spatially and temporally, which leads to diverse and dynamic degradations. Furthermore, online streaming has a strict requirement for latency that most existing methods are less applicable. As a result, this paper focuses on the rarely exploited problem setting of online streaming video super resolution. To facilitate the research on this problem, a new benchmark dataset named LDV-WebRTC is constructed based on a real-world online streaming system. Leveraging the new benchmark dataset, we propose a novel method specifically for online video streaming, which contains a convolution and Look-Up Table (LUT) hybrid model to achieve better performance-latency trade-off. To tackle the changing degradations, we propose a mixture-of-expert-LUT module, where a set of LUT specialized in different degradations are built and adaptively combined to handle different degradations. Experiments show our method achieves 720P video SR around 100 FPS, while significantly outperforms existing LUT-based methods and offers competitive performance compared to efficient CNN-based methods. Code is available at https://github.com/quzefan/ConvLUT.

Large language models (LLMs) have been applied in various applications due to their astonishing capabilities.With advancements in technologies such as chain-of-thought (CoT) prompting and in-context learning (ICL), the prompts fed to LLMs are becoming increasingly lengthy, even exceeding tens of thousands of tokens.To accelerate model inference and reduce cost, this paper presents LLMLingua, a coarse-to-fine prompt compression method that involves a budget controller to maintain semantic integrity under high compression ratios, a token-level iterative compression algorithm to better model the interdependence between compressed contents, and an instruction tuning based method for distribution alignment between language models.We conduct experiments and analysis over four datasets from different scenarios, i.e., GSM8K, BBH, ShareGPT, and Arxiv-March23; showing that the proposed approach yields state-of-the-art performance and allows for up to 20x compression with little performance loss. 1

Deep learning training on cloud platforms usually follows the tradition of the separation of storage and computing. The training executes on a compute cluster equipped with GPUs/TPUs while reading data from a separate cluster hosting the storage service. To alleviate the potential bottleneck, a training cluster usually leverages its local storage as a cache to reduce the remote IO from the storage cluster. However, existing deep learning schedulers do not manage storage resources thus fail to consider the diverse caching effects across different training jobs. This could degrade scheduling quality significantly.

Monitoring and analyzing stereotypical behaviours is important for early intervention and care taking in Autism Spectrum Disorder (ASD). This paper focuses on automatically detecting stereotypical behaviours with computer vision techniques. Off-the-shelf methods tackle this task by supervised classification and activity recognition techniques. However, the un-bounded types of stereotypical behaviours and the difficulty in collecting video recordings of ASD patients largely limit the feasibility of the existing supervised detection methods. As a result, we tackle these challenges from a new perspective, i.e. unsupervised video anomaly detection for stereotypical behaviours detection. The models can be trained among unlabeled videos containing only normal behaviours and unknown types of abnormal behaviours can be detected during inference. Correspondingly, we propose a Dual Stream deep model for Stereotypical Behaviours Detection, DS-SBD, based on the temporal trajectory of human poses and the repetition patterns of human actions. Extensive experiments are conducted to verify the effectiveness of our proposed method and suggest that it serves as a potential benchmark for future research.

In vision-language modeling, image token removal is an efficient augmentation technique to reduce the cost of encoding image features. The CLIP-style models, however, have been found to be negatively impacted by this technique. We hypothesize that removing a large portion of image tokens may inadvertently destroy the semantic information associated to a given text description, resulting in misaligned paired data in CLIP training. To address this issue, we propose an attentive token removal approach, which retains a small number of tokens that have a strong semantic correlation to the corresponding text description. The correlation scores are dynamically evaluated through an EMA-updated vision encoder. Our method, termed attentive mask CLIP, outperforms original CLIP and CLIP variant with random token removal while saving the training time. In addition, our approach also enables efficient multi-view contrastive learning. Experimentally, by training ViT-B on YFCC-15M dataset, our approach achieves 43.9% top-1 accuracy on ImageNet-1K zero-shot classification, 62.7/42.1 and 38.0/23.2 I2T/T2I retrieval accuracy on Flickr30K and MS COCO, outperforming SLIP by +1.1%, +5.5/+0.9, and +4.4/+1.3, respectively, while being 2.30× faster. An efficient version of our approach runs 1.16× faster than the plain CLIP model, while achieving significant gains of +5.3%, +11.3/+8.0, and +9.5/+4.9 on these benchmarks, respectively. Code will be release in https://github.com/microsoft/A-CLIP.

Motivated by many potential applications that could be enabled by acoustic motion tracking, in this paper we systematically examine the factors that limit the accuracy of acoustic tracking in practical scenarios. We identify three main challenges: (i) high mobility, (ii) low SNR, and (iii) hardware frequency response. We further show that the last two issues may exacerbate the performance issue under high mobility. We develop effective approaches to address the issues. In particular, to address high mobility, we tackle phase wrap-around using the derivative of the phase; we further estimate the Doppler shift under diverse scenarios and compensate the Doppler in channel impulse response (CIR). To address low SNR, we use a novel approach to estimate the phase shift between consecutive time intervals to effectively support time-domain beamforming and increase SNR. To tackle the uneven frequency response, we show that it is important to estimate and compensate the phase as well as the amplitude of the frequency response. Our extensive evaluation shows that each of our techniques is effective and putting them together significantly enhances the accuracy of acoustic motion tracking in general scenarios.

Low Earth Orbit (LEO) satellite communication is essential for wireless communication. While manufacturing and launching LEO satellites have become efficient and cost-effective, ground stations remain expensive due to complex designs for handling severe path losses and precise beam tracking. Hence, it is important to develop low cost and high-performance ground stations for widespread adoption of LEO satellite communication. Towards realizing this goal, we design a passive metasurface-enhanced LEO ground station system, named PMSat, combining metasurface's fine-grained beamforming capability with a small-size phased array's adaptive steering and focusing. For uplink, we jointly optimize the phase array codebook and uplink metasurface phase profile, and realize electronic steering by switching the codeword. We further jointly optimize the downlink metasurface phase profile to improve the focusing performance and enhance the received signal strength (RSS) over a wide range of incident angles. Our PMSat prototype consists of a single passive metasurface with 21 × 21 elements for uplink and 22 × 22 for downlink, along with 1 × 4 receiving and 1 × 4 transmitting phased array antennas. The effectiveness of our proposed PMSat is validated through extensive experiments, and results demonstrate that the optimized metasurface improves the SNR by 8.32 dB and 16.57 dB for uplink and downlink, respectively.

Channel estimation is critical to millimeter-wave capability. Unlike sub-6 GHz WiFi, commercial-off-the-shelf 60 GHz WiFi devices adopt a single RF-chain and can only report the combined received signal strength (RSS) instead of the antenna-wise channel state information (CSI). Therefore, recovering the CSI using a limited number of RSS measurements is important but faces the following challenges: (i) solving a non-convex objective is hard and computationally heavy, (ii) the estimation error is high with insufficient RSS measurements, and (iii) channel fluctuates dynamically. To jointly tackle them, we propose 2ACE, an Accelerated and Accurate Channel Estimation approach using spectral profile-driven multiresolutional compressive sensing. Our thorough experiments show that 2ACE yields 2--8 dB reduction in CSI estimation error, 1--5 dB improvement in beamforming performance, and 5° - 10° reduction in angle-of-departure estimation error over the existing schemes.

While language-guided image manipulation has made remarkable progress, the challenge of how to instruct the manipulation process faithfully reflecting human intentions persists. An accurate and comprehensive description of a manipulation task using natural language is laborious and sometimes even impossible, primarily due to the inherent uncertainty and ambiguity present in linguistic expressions. Is it feasible to accomplish image manipulation without resorting to external cross-modal language information? If this possibility exists, the inherent modality gap would be effortlessly eliminated. In this paper, we propose a novel manipulation methodology, dubbed ImageBrush, that learns visual instructions for more accurate image editing. Our key idea is to employ a pair of transformation images as visual instructions, which not only precisely captures human intention but also facilitates accessibility in real-world scenarios. Capturing visual instructions is particularly challenging because it involves extracting the underlying intentions solely from visual demonstrations and then applying this operation to a new image. To address this challenge, we formulate visual instruction learning as a diffusion-based inpainting problem, where the contextual information is fully exploited through an iterative process of generation. A visual prompting encoder is carefully devised to enhance the model's capacity in uncovering human intent behind the visual instructions. Extensive experiments show that our method generates engaging manipulation results conforming to the transformations entailed in demonstrations. Moreover, our model exhibits robust generalization capabilities on various downstream tasks such as pose transfer, image translation and video inpainting.

A timely detection of seizures for newborn infants with electroencephalogram (EEG) has been a common yet lifesaving practice in the Neonatal Intensive Care Unit (NICU). However, it requires great human efforts for real-time monitoring, which calls for automated solutions to neonatal seizure detection. Moreover, the current automated methods focusing on adult epilepsy monitoring often fail due to (i) dynamic seizure onset location in human brains; (ii) different montages on neonates and (iii) huge distribution shift among different subjects. In this paper, we propose a deep learning framework, namely STATENet, to address the exclusive challenges with exquisite designs at the temporal, spatial and model levels. The experiments over the real-world large-scale neonatal EEG dataset illustrate that our framework achieves significantly better seizure detection performance.

Dynamic sparsity, where the sparsity patterns are unknown until runtime, poses a significant challenge to deep learning. The state-of-the-art sparsity-aware deep learning solutions are restricted to pre-defined, static sparsity patterns due to significant overheads associated with preprocessing. Efficient execution of dynamic sparse computation often faces the misalignment between the GPU-friendly tile configuration for efficient execution and the sparsity-aware tile shape that minimizes coverage wastes (non-zero values in tensor).

Mobile devices have emerged as the most popular platforms to access information. However, they have also become a major concern of privacy violation and previous researches have demonstrated various approaches to infer user privacy based on mobile devices. In this paper, we study the electromagnetic (EM) emission of a laptop that could be harvested by a commercial-off-the-shelf (COTS) mobile device, e.g., a smartphone. We proposeMagAttack, which exploits the electromagnetic side channel of a laptop to guess user activities, i.e., application launching and application operation. The key insight ofMagAttackis that applications are discrepant in essence due to the different compositions of instructions, which can be reflected on the CPU power consumption, and thus the corresponding EM emissions.MagAttackis challenging since that EM signals are noisy due to the dynamics of applications and the limited sampling rate of the built-in magnetometers in COTS mobile devices. We overcome these challenges and convert noisy coarse-grained EM signals to robust fine-grained features. We implementMagAttackon both an iOS and an Android smartphone without any hardware modification, and evaluate its performance with 30 popular applications, 30 YouTube videos, and 50 top websites in China. The results demonstrate thatMagAttackcan recognize aforementioned 30 applications with an average accuracy of 98.6 percent, and identify which video out of the 30 candidates being played with an average accuracy of 97.5 percent and visiting which website among the 50 candidates with an average accuracy of 90.4 percent.

Extreme mobility becomes a norm rather than an exception with emergent high-speed rails, drones, industrial IoT, and many more. However, 4G/5G mobility management is not always reliable in extreme mobility, with non-negligible failures and policy conflicts. The root cause is that, existing mobility management is primarily based on wireless signal strength. While reasonable in static and low mobility, it is vulnerable to dramatic wireless dynamics from extreme mobility in triggering, decision, and execution. We deviseREM, Reliable Extreme Mobility management for beyond 5G cellular networks while maintaining backward compatibility to 4G/5G.REMshifts to movement-based mobility management in the delay-Doppler domain. Its signaling overlay relaxes feedback via cross-band estimation, simplifies policies with provable conflict freedom, and stabilizes signaling via scheduling-based OTFS modulation. Our evaluation with operational high-speed rail datasets shows that,REMreduces failures comparable to static and low mobility, with low signaling and latency cost.REMreduces the network failures by up to an order of magnitude, eliminates policy conflicts, and improves application performance by 31.8% - 88.3% compared to legacy 4G/5G.

Hypernasality is an abnormal resonance in human speech production, especially in patients with craniofacial anomalies such as cleft palate.In clinical application, hypernasality estimation is crucial in cleft palate diagnosis, as its results determine the subsequent surgery and additional speech therapy.Therefore, designing an automatic hypernasality assessment method will facilitate speech-language pathologists to make precise diagnoses.Existing methods for hypernasality estimation only conduct acoustic analysis based on low-resource cleft palate dataset, by using statistical or neural network-based features.In this paper, we propose a novel approach that uses automatic speech recognition model to improve hypernasality estimation.Specifically, we first pre-train an encoder-decoder framework in an automatic speech recognition (ASR) objective by using speech-to-text dataset, and then fine-tune ASR encoder on the cleft palate dataset for hypernasality estimation.Benefiting from such design, our model for hypernasality estimation can enjoy the advantages of ASR model: 1) compared with low-resource cleft palate dataset, the ASR task usually includes large-scale speech data in the general domain, which enables better model generalization; 2) the text annotations in ASR dataset guide model to extract better acoustic features.Experimental results on two cleft palate datasets demonstrate that our method achieves superior performance compared with previous approaches.

In large-scale online services, crucial metrics, a.k.a., key performance indicators (KPIs), are monitored periodically to check the running statuses. Generally, KPIs are aggregated along multiple dimensions and derived by complex calculations among fundamental metrics from the raw data. Once abnormal KPI values are observed, root cause analysis (RCA) can be applied to identify the reasons for anomalies, so that we can troubleshoot quickly. Recently, several automatic RCA techniques were proposed to localize the related dimensions (or a combination of dimensions) to explain the anomalies. However, their analyses are limited to the data on the abnormal metric and ignore the data of other metrics which are also related to the anomalies, leading to imprecise or even incorrect root causes. To this end, we propose a cross-metric multi-dimensional root cause analysis method, named CMMD, which consists of two key components: 1) relationship modeling, which utilizes graph neural network (GNN) to model the unknown complex calculation among metrics and aggregation function among dimensions from historical data; 2) root cause localization, which adopts the genetic algorithm to efficiently and effectively dive into the raw data and localize the abnormal dimension(s) once the KPI anomalies are detected. Experiments on synthetic datasets, real-world datasets and online production environments demonstrate the superiority of our proposed CMMD method compared with baselines. Currently, CMMD is running as an online service in Microsoft Azure.

Optical image stabilizers (OIS) are widely used in digital cameras to counteract motion blur caused by camera shakes in capturing videos and photos. In this paper, we sought to expand the applicability of the lens-shift OIS technology for metric depth estimation, i.e., let a RGB camera to achieve the similar function of a time-of-flight (ToF) camera. Instead of having to move the entire camera for depth estimation, we propose DoCam, which controls the lens motion in the OIS module to achieve 3D reconstruction. After controlling the lens motion by altering the MEMS gyroscopes readings through acoustic injection, we improve the traditional bundle adjustment algorithm by establishing additional constraints from the linearity of the lens control model for high-precision camera pose estimation. Then, we elaborate a dense depth reconstruction algorithm to compute depth maps at real-world scale from multiple captures with micro lens motion (i.e., ≤ 3 mm). Extensive experiments demonstrate that our proposed DoCam can enable a 2D color camera to estimate high-accuracy depth information of the captured scene by means of controlling lens motion in the OIS. DoCam is suitable for a variety of applications that require depth information of the scenes, especially when only a single color camera is available and located at a fixed position.

The wireless signal propagates via multipath arising from different reflections and penetration between a transmitter and receiver. Extracting multipath profiles (e.g., delay and Doppler along each path) from received signals enables many important applications, such as channel prediction and crossband channel estimation (i.e., estimating the channel on a different frequency). The benefit of multipath estimation further increases with mobility since the channel in that case is less stable and more important to track. Yet high-speed mobility poses significant challenges to multipath estimation. In this paper, instead of using time-frequency domain channel representation, we leverage the delay-Doppler domain representation to accurately extract and predict multipath properties. Specifically, we use impulses in the delay-Doppler domain as pilots to estimate the multipath parameters and apply the multipath information to predicting wireless channels as an example application. Our design rationale is that mobility is more predictable than the wireless channel since mobility has inertial while the wireless channel is the outcome of a complicated interaction between mobility, multipath, and noise. We evaluate our approach via both acoustic and RF experiments, including vehicular experiments using USRP. Our results show that the estimated multipath matches the ground truth, and the resulting channel prediction is more accurate than the traditional channel prediction schemes.

Real-time mobile video analytics plays an increasingly important role in our daily life, such as smart driving, unmanned delivery, cashier free stores, and video surveillance. The existing video analytics runs complex deep models to detect and recognize objects in video frames. However, running deep models on mobile devices can not meet the real-time requirement. This paper develops a novel mobile video analytics system. Its unique features include (i) high accuracy, (ii) real-time, and (iii) running exclusively on a mobile device without the need of edge/cloud server or network connectivity. At its heart lies an effective technique to reliably extract motion from video frames and use the motion to speed up video analytics. Unlike the existing motion extraction, our technique is robust to background noise and changes in object sizes. Extensive evaluation results show that we can support real-time object tracking at 30 frames/second (fps) on Nvidia Jetson TX2. For single-object tracking, Sight improves the average Intersection-over-Union (IoU) by 88%, improves the mean Average Precision (mAP) by 207% and reduces the average hardware resource usage by 45% over state-of-the-art approach. For multi-object tracking, Sight improves IoU by 69%, improves mAP by 173% and reduces resource usage by around 32% over state-of-the-art approach.

Rotational movement is important in many applications, yet has been under-explored. In this paper, we explore the feasibility of using a single RFID reader antenna to simultaneously sense rotation and translation movement (i.e., rotation axis, rotation speed, and translation speed). We exploit the polarization in RFID to enable motion sensing. We develop an analytical model to capture the impact of polarization on the received signal and an optimization framework to incorporate the model to estimate the movement. We implement our system, Tag-based Inertial Measurement Unit (TIMU), and demonstrate its effectiveness through an extensive evaluation. To our knowledge, this is the first system that tracks general motion using a single RFID reader antenna.

Performance impacts are commonly observed in cellular networks and are induced by several factors, such as software upgrade and configuration changes. The variability in traffic patterns across different granularities can lead to impact cancellation or dilution. As a result, performance impacts are hard to capture if not aggregated over problematic features. Analyzing performance impact across all possible feature combinations is too expensive. On the other hand, the set of features that causes issues is unpredictable due to the highly dynamic and heterogeneous cellular networks. In this paper, we propose a novel algorithm that dynamically explores those network feature combinations that are likely to have problems by using a summary structure Sketch. We further design a neural network based algorithm to localize root cause. We achieve high scalability in neural network by leveraging the Lattice and Sketch structure. We demonstrate the effectiveness of our impact detection and diagnosis through extensive evaluation using data collected from a major tier-1 cellular carrier in US and synthetic traces.

Passive radio-frequency identification (RFID) tags are attractive because they are low cost, battery-free, and easy to deploy. This technology is traditionally being used to identify tags attached to the objects. In this paper, we explore the feasibility of turning passive RFID tags into battery-free temperature sensors. The impedance of the RFID tag changes with the temperature and this change will be manifested in the reflected signal from the tag. This opens up an opportunity to realize battery-free temperature sensing using a passive RFID tag with already deployed Commercial Off-the-Shelf (COTS) RFID reader-antenna infrastructure in supply chain management or inventory tracking. However, it is challenging to achieve high accuracy and robustness against the changes in the environment. To address these challenges, we first develop a detailed analytical model to capture the impact of temperature change on the tag impedance and the resulting phase of the reflected signal. We then build a system that uses a pair of tags, which respond differently to the temperature change to cancel out other environmental impacts. Using extensive evaluation, we show our model is accurate and our system can estimate the temperature within a 2.9 degree centigrade median error and support a normal read range of 3.5 m in an environment-independent manner.

Extreme mobility has become a norm rather than an exception. However, 4G/5G mobility management is not always reliable in extreme mobility, with non-negligible failures and policy conflicts. The root cause is that, existing mobility management is primarily based on wireless signal strength. While reasonable in static and low mobility, it is vulnerable to dramatic wireless dynamics from extreme mobility in triggering, decision, and execution. We devise REM, Reliable Extreme Mobility management for 4G, 5G, and beyond. REM shifts to movement-based mobility management in the delay-Doppler domain. Its signaling overlay relaxes feedback via cross-band estimation, simplifies policies with provable conflict freedom, and stabilizes signaling via scheduling-based OTFS modulation. Our evaluation with operational high-speed rail datasets shows that, REM reduces failures comparable to static and low mobility, with low signaling and latency cost.

Mobile devices have emerged as the most popular platforms to access information. However, they have also become a major concern of privacy violation and previous researches have demonstrated various approaches to infer user privacy based on mobile devices. In this paper, we study a new side channel of a laptop that could be harvested by a commercial-off-the-shelf (COTS) mobile device, eg, a smartphone. We propose MagAttack, which exploits the electromagnetic (EM) side channel of a laptop to infer user activities, i.e., application launching and application operation. The key insight of MagAttack is that applications are discrepant in essence due to the different compositions of instructions, which can be reflected on the CPU power consumption, and thus the corresponding EM emissions. MagAttack is challenging since that EM signals are noisy due to the dynamics of applications and the limited sampling rate of the built-in magnetometers in COTS mobile devices. We overcome these challenges and convert noisy coarse-grained EM signals to robust fine-grained features. We implement MagAttack on both an iOS and an Android smartphone without any hardware modification, and evaluate its performance with 13 popular applications and 50 top websites in China. The results demonstrate that MagAttack can recognize aforementioned 13 applications with an average accuracy of 98.6%, and figure out the visiting operation among 50 websites with an average accuracy of 84.7%.

The popularity of 4K videos has grown significantly in the past few years. Yet coding and streaming live 4K videos incurs prohibitive cost to the network and end system. Motivated by this observation, we explore the feasibility of supporting live 4K video streaming over wireless networks using commodity devices. Given the high data rate requirement of 4K videos, 60 GHz is appealing, but its large and unpredictable throughput fluctuation makes it hard to provide desirable user experience. In particular, to support live 4K video streaming, we should (i) adapt to highly variable and unpredictable wireless throughput, (ii) support efficient 4K video coding on commodity devices. To this end, we propose a novel system, Jigsaw. It consists of (i) easy-to-compute layered video coding to seamlessly adapt to unpredictable wireless link fluctuations, (ii) efficient GPU implementation of video coding on commodity devices, and (iii) effectively leveraging both WiFi and WiGig through delayed video adaptation and smart scheduling. Using real experiments and emulation, we demonstrate the feasibility and effectiveness of our system. Our results show that it improves PSNR by 6-15dB and improves SSIM by 0.011-0.217 over state-of-the-art approaches. Moreover, even when throughput fluctuates widely between 0.2Gbps-2Gbps, it can achieve an average PSNR of 33dB.

Smart speakers allow users to interact with home appliances using voice commands and are becoming increasingly popular. While voice-based interface is intuitive, it is insufficient in many scenarios, such as in noisy or quiet environments, for users with language barriers, or in applications that require continuous motion tracking. Motion-based control is attractive and complementary to existing voice-based control. However, accurate and reliable room-scale motion tracking poses a significant challenge due to low SNR, interference, and varying mobility. To this end, we develop a novel recurrent neural network (RNN) based system that uses speakers and microphones to realize accurate room-scale tracking. Our system jointly estimates the propagation distance and angle-of-arrival (AoA) of signals reflected by the hand, based on AoA-distance profiles generated by 2D MUSIC. We design a series of techniques to significantly enhance the profile quality under low SNR. We feed the profiles in a recent history to our RNN to estimate the distance and AoA. In this way, we can exploit the temporal structure among consecutive profiles to remove the impact of noise, interference and mobility. Using extensive evaluation, we show our system achieves 1.2--3.7~cm error within 4.5~m range, supports tracking multiple users, and is robust against ambient sound. To our knowledge, this is the first acoustic device-free room-scale tracking system.

Smartphones with dual cameras are increasingly popular due to the need of supporting 3D vision. The depth information is critical for 3D vision. However, the two cameras on a smartphone are too close to accurately estimate the depth information especially for objects beyond two meters. In this paper, we propose an innovative system, called HyperSight, to estimate the depth information of objects using a dual camera smartphone. HyperSight realizes a virtual longbaseline stereo vision rig by having a user to move the phone in the air. The phone movement is continuously tracked and estimated using the short-baseline dual camera seeing nearby objects. We implement HyperSight as software on a Commercial-Off-The-Shelf (COTS) smartphone and conduct real-world experiments. The results show that when measuring feature-rich objects at a distance of five meters, HyperSight achieves a mean depth error of 6cm, which is up to 10× and 18× improvement in the accuracy compared with the stereo vision system using the native dual cameras and the Measure app based on ARKit 1 on mobile devices, respectively.

The citizen broadband radio service (CBRS) is a newly re-purposed spectrum band in 3550-3700 MHz, reclaiming spectrum occasionally used by radars and other incumbents for mobile data communication. It is also a poster child for future LTE-based dynamic spectrum access systems. At present, CBRS does not manage interference from unlicensed LTE users, which we show can be detrimental for its performance. In this paper we develop F-CBRS, a decentralized spectrum interference management system for unlicensed LTE users in the CBRS band. We first look at how much information can each operator be allowed to conceal and how much it has to be mandated (by a regulator) to disclose, and formally prove that the network can achieve fairness only if all operators share fully verifiable information about Access point (AP) locations and user activity. Using this insight we design a channel allocation scheme to efficiently utilize spectrum and incentivise collaboration. This also includes a simple, non-disruptive channel change scheme to frequently and efficiently change channels to accommodate dynamic traffic and environments. Through simulation and testbed evaluation, we show that we increase throughput of more than 90% of the flow by 80%-100% compared to the current CBRS protocol.

Video rate adaptation has large impact on quality of experience (QoE). However, existing video rate adaptation is rather limited due to a small number of rate choices, which results in (i) under-selection, (ii) rate fluctuation, and (iii) frequent rebuffering. Moreover, selecting a single video rate for a 360° video can be even more limiting, since not all portions of a video frame are equally important. To address these limitations, we identify new dimensions to adapt user QoE - dropping video frames, slowing down video play rate, and adapting different portions in 360° videos. These new dimensions along with rate adaptation give us a more fine-grained adaptation and significantly improve user QoE. We further develop a simple yet effective learning strategy to automatically adapt the buffer reservation to avoid performance degradation beyond optimization horizon. We implement our approach Favor in VLC, a well known open source media player, and demonstrate that Favor on average out-performs Model Predictive Control (MPC), rate-based, and buffer-based adaptation for regular videos by 24%, 36%, and 41%, respectively, and 2X for 360° videos.

The popularity of 360° videos has grown rapidly due to the immersive user experience. 360° videos are displayed as a panorama and the view automatically adapts with the head movement. Existing systems stream 360° videos in a similar way as regular videos, where all data of the panoramic view is transmitted. This is wasteful since a user only views a small portion of the 360° view. To save bandwidth, recent works propose the tile-based streaming, which divides the panoramic view to multiple smaller sized tiles and streams only the tiles within a user's field of view (FoV) predicted based on the recent head position. Interestingly, the tile-based streaming has only been simulated or implemented on desktops. We find that it cannot run in real-time even on the latest smartphone (e.g., Samsung S7, Samsung S8 and Huawei Mate 9) due to hardware and software limitations. Moreover, it results in significant video quality degradation due to head movement prediction error, which is hard to avoid. Motivated by these observations, we develop a novel tile-based layered approach to stream 360° content on smartphones to avoid bandwidth wastage while maintaining high video quality. Through real system experiments, we show our approach can achieve up to 69% improvement in user QoE and 49% in bandwidth savings over existing approaches. To the best of our knowledge, this is the first 360° streaming framework that takes into account the practical limitations of Android based smartphones.

The popularity of smartphones has grown at an unprecedented rate, which makes smartphone based imaging especially appealing. In this paper, we develop a novel acoustic imaging system using only an off-the-shelf smartphone. It is an attractive alternative to camera based imaging under darkness and obstruction. Our system is based on Synthetic Aperture Radar (SAR). To image an object, a user moves a phone along a predefined trajectory to mimic a virtual sensor array. SAR based imaging poses several new challenges in our context, including strong self and background interference, deviation from the desired trajectory due to hand jitters, and severe speaker/microphone distortion. We address these challenges by developing a 2-stage interference cancellation scheme, a new algorithm to compensate trajectory errors, and an effective method to minimize the impact of signal distortion. We implement a proof-of-concept system on Samsung S7. Our results demonstrate the feasibility and effectiveness of acoustic imaging on a mobile.

In this paper we study network architecture for unlicensed cellular networking for outdoor coverage in TV white spaces. The main technology proposed for TV white spaces is 802.11af, a Wi-Fi variant adapted for TV frequencies. However, 802.11af is originally designed for improved indoor propagation. We show that long links, typical for outdoor use, exacerbate known Wi-Fi issues, such as hidden and exposed terminal, and significantly reduce its efficiency.

Cellular networks are constantly evolving due to frequent changes in radio access and end user equipment technologies, dynamic applications and associated trafflc mixes. Network upgrades should be performed with extreme caution since millions of users heavily depend on the cellular networks for a wide range of day to day tasks, including emergency and alert notifications. Before upgrading the entire network, it is important to conduct field evaluation of upgrades. Field evaluations are typically cumbersome and can be time consuming; however if done correctly they can help alleviate a lot of the deployment issues in terms of service quality degradation. The choice and number of field test locations have significant impacts on the time-to-market as well as confidence in how well various network upgrades will work out in the rest of the network. In this paper, we propose a novel approach — Reflection to automatically determine where to conduct the upgrade field tests in order to accurately identify important features that affect the upgrade. We demonstrate the effectiveness of Reflection using extensive evaluation based on real traces collected from a major US cellular network as well as synthetic traces.

Cellular service providers continuously upgrade their network software on base stations to introduce new service features, fix software bugs, enhance quality of experience to users, or patch security vulnerabilities. A software upgrade typically requires the network element to be taken out of service, which can potentially degrade the service to users. Thus, the new software is deployed across the network using a rolling upgrade model such that the service impact during the roll-out is minimized. A sequential roll-out guarantees minimal impact but increases the deployment time thereby incurring a significant human cost and time in monitoring the upgrade. A network-wide concurrent roll-out guarantees minimal deployment time but can result in a significant service impact. The goal is to strike a balance between deployment time and service impact during the upgrade. In this paper, we first present our findings from analyzing upgrades in operational networks and discussions with network operators and exposing the challenges in rolling software upgrades. We propose a new framework Concord to effectively coordinate software upgrades across the network that balances the deployment time and service impact. We evaluate Concord using real-world data collected from a large operational cellular network and demonstrate the benefits and tradeoffs. We also present a prototype deployment of Concord using a small-scale LTE testbed deployed indoors in a corporate building.

In today's always-connected world, we receive a large number of notifications on our mobile devices. These notifications cause interruptions, stress, and even impact users' lifestyle. To understand how users respond to notifications, we develop an application that monitors various features (e.g., importance) of the notifications, users' actions, and the level of users' engagement with the notifications. We recruit 30 users to use the application and monitor over 30 days, and subsequently find that 20% to 50% of the notifications generally get ignored by the users. In addition, we also solicit explicit feedback about the importance of notifications from 12 users over 14 days and identify the relation between perceived importance and users' engagement level. Based on this study, we identify the key characteristics of notifications and users' engagement, which is further substantiated by an onfine survey of 400+ users. In addition, we develop a notification manager that includes a machine learning based prediction model and that shows only the important notifications and delays the unimportant notifications. Our experimental results show that our notification manager automatically assesses the importance of notifications with more than 87% accuracy. We believe this work is a promising step toward intelligent personal assistant that manages notifications.

The ever increasing of display resolution on mobile devices raises high demand for GPU rendering details. However, the challenge of poor hardware support but fine-grained rendering details often makes user unsatisfied especially in calling for high frame rate scenarios, e.g., game. To resolve such issue, we propose BUTTERFLY, a novel system which collaboratively utilizes mobile GPUs to process high-quality rendering details for on-the-go mobile users. In particular, ButterFly achieves two technical contributions for the collaborative design: (1) a mobile device can migrate GPU workloads in buffer queue to peers, and (2) the collaborative rendering mechanism benefits user high quality details while significant power saving performance. Both techniques are compatible with the OpenGL ES standards. Furthermore, a 40-person survey perceives that ButterFly can provide excellent user experience of both rendering details and frame rate over Wi-Fi network. In addition, our comprehensive trace-driven experiments on Android prototype reveal the benefits of Butterfly have more superior performance over state-of-the-art systems, which achieves more than 28.3% power saving.

In this paper, we design and develop RIO, a novel battery-free touch sensing user interface (UI) primitive for future IoT and smart spaces. RIO enables UIs to be constructed using off-the-shelf RFID readers and tags, and provides a unique approach to designing smart IoT spaces. With RIO, any surface can be turned into a touch-aware surface by simply attaching RFID tags to them. RIO also supports custom-designed RFID tags, and thus allows specially customized UIs to be easily deployed into a real-world environment. RIO is built using the technique of impedance tracking: when a human finger touches the surface of an RFID tag, the impedance of the antenna changes. This change manifests as a change in the phase of the RFID backscattered signal, and is used by RIO to track fine-grained touch movement over both off-the shelf and custom built tags. We study this impedance behavior in-depth and show how RIO is a reliable UI primitive that is robust even within a multi-tag environment. We leverage this primitive to build a prototype of RIO that can continuously locate a finger during a swipe movement to within 3 mm of its actual position. We also show how custom-design RFID tags can be built and used with RIO, and provide two example applications that demonstrate its real-world use.

With the availability of inexpensive and powerful drones, it is possible to let drones automatically follow a user for video taping. This can not only reduce cost, but also support video taping in situations where otherwise not possible (e.g., during private moments or at inconvenient locations like indoor rock climbing). While there have been many follow-me drones on the market for outdoors, which rely on GPS, enabling indoor follow-me function is more challenging due to the lack of an effective approach to track users in indoor environments. To this end, we develop a holistic system that lets a mobile phone carried by a user accurately track the drone's relative location and control it to maintain a specified distance and orientation for automatic video taping. We develop a series of techniques to (i) track a drone's location using acoustic signals with sub-centimeter errors even under strong propeller noise from the drone and complicated multipath in indoor environments, and (ii) solve practical challenges in applying model predictive control (MPC) framework to control the drone. The latter consists of developing measurement-based flight models, designing measurement techniques to provide feedback to the controller, and predicting the user's movement. We implement our system on AR Drone 2.0 and Samsung S7. The extensive evaluation shows that our drone can follow a user effectively and maintain a specified following distance and orientation within 2-3 cm and 1-3 degree errors, respectively. The videos taped by the drone during flight are smooth according to the jerk metric.

Next generation devices, such as virtual reality (VR), augmented reality (AR), and smart appliances, demand a simple and intuitive way for users to interact with them. To address such needs, we develop a novel acoustic based device-free tracking system, called Strata, to enable a user to interact with a nearby device by simply moving his finger. In Strata, a mobile (e.g., smartphone) transmits known audio signals at inaudible frequency, and analyzes the received signal reflected by the moving finger to track the finger location. To explicitly take into account multipath propagation, the mobile estimates the channel impulse response (CIR), which characterizes signal traversal paths with different delays. Each channel tap corresponds to the multipath effects within a certain delay range. The mobile selects the channel tap corresponding to the finger movement and extracts the phase change of the selected tap to accurately estimate the distance change of a finger. Moreover, it estimates the absolute distance of the finger based on the change in CIR using a novel optimization framework. We then combine the absolute and relative distance estimates to accurately track the moving target. We implement our tracking system on Samsung Galaxy S4 mobile phone. Through micro-benchmarks and user studies, we show that our system achieves high tracking accuracy and low latency without extra hardware.

The signal-to-noise ratio (SNR) is the gold standard metric for capturing wireless link quality, but offers limited predictability. Recent work shows that frequency diversity causes limited predictability in SNR, and proposes effective SNR. Owing to its significant improvement over SNR, effective SNR has become a widely adopted metric for measuring wireless channel quality and served as the basis for many recent rate adaptation schemes. In this paper, we first conduct trace driven evaluation, and find that the accuracy of effective SNR is still inadequate due to frequency diversity and bursty errors. While common wisdom says that interleaving should remove the bursty errors, bursty errors still persist under the WiFi interleaver. Therefore, we develop two complementary methods for computing frame delivery rate to capture the bursty errors under the WiFi interleaver. We then design a new interleaver to reduce the burstiness of errors, and improve the frame delivery rate. We further design a rate adaptation scheme based on our delivery rate estimation. It can support both WiFi and our interleaver. Using extensive evaluation, we show our delivery rate estimation is accurate and significantly out-performs effective SNR; our interleaver improves the delivery rate over the WiFi interleaver; and our rate adaptation improves both throughput and energy.

Always-on localization is an important problem for a lot of context sensitive mobile computing applications. This paper proposes WaveLoc, which effectively uses measurements from a trajectory as its fingerprint for localization. Different from traditional approaches, which use signatures from single-points for localization, we leverage signatures from a trajectory, since it offers a lot more information. However, it is much more challenging to match measurements across trajectories than from single points. To tackle this challenge, WaveLoc divides the problem into the following two steps: (i) identify a user's current trajectory by matching its measurements with those in the training traces (trajectory matching) and (ii) localize the user on the trajectory (localization). The core requirement of both steps is an accurate and robust algorithm to match two time-series that may contain significant noise and perturbation due to differences in speed, mobility, devices, and environment. WaveLoc addresses these by performing multi-level wavelet analysis of the measurements and applying an enhanced Dynamic Time Warping (DTW) alignment to the wavelet coefficients. Using both indoor and outdoor experiments, we demonstrate that WaveLoc is accurate and power efficient.

Video games, Virtual Reality (VR), Augmented Reality (AR), and Smart appliances (e.g., smart TVs) all call for a new way for users to interact and control them. This paper develops high-preCision Acoustic Tracker (CAT), which aims to replace a traditional mouse and let a user play games, interact with VR/AR headsets, and control smart appliances by moving a smartphone in the air. Achieving high tracking accuracy is essential to provide enjoyable user experience. To this end, we develop a novel system that uses audio signals to achieve mm-level tracking accuracy. It lets multiple speakers transmit inaudible sounds at different frequencies. Based on the received sound, our system continuously estimates the distance and velocity of the mobile with respect to the speakers to continuously track it. At its heart lies a distributed Frequency Modulated Continuous Waveform (FMCW) that can accurately estimate the absolute distance between a transmitter and a receiver that are separate and unsynchronized. We further develop an optimization framework to combine FMCW estimation with Doppler shifts and Inertial Measurement Unit (IMU) measurements to enhance the accuracy, and efficiently solve the optimization problem. We implement two systems: one on a desktop and another on a mobile phone. Our evaluation and user study show that our system achieves high tracking accuracy and ease of use using existing hardware.

Video games, virtual reality, augmented reality, and smart appliances all call for a new way for users to interact and control them. This paper develops high-preCision Acoustic Tracker (CAT), which aims to replace a traditional mouse and let a user control various devices by moving a smartphone in the air. At its heart lies a distributed Frequency Modulated Continuous Waveform (FMCW) that can accurately estimate the distance between a transmitter and a receiver that are separate and unsynchronized. We further develop an optimization framework to combine FMCW estimation with Doppler shifts to enhance the accuracy. We implement CAT on a mobile phone. The performance evaluation and user study show that our system achieves high tracking accuracy and ease of use using existing hardware.

Interference in WiFi deployments is a growing problem due to the increasing popularity of WiFi. Therefore it is important that APs find the right channel to operate upon. Through a large scale measurement study involving over 10,000 WiFi APs we show that channel measurements and selection are most effective when performed frequently (every few minutes). This is because of the highly dynamic nature of WiFi traffic congestion. Our key contribution in this paper is a novel approach to distributed channel selection -- Ineffective time Quantum (IQ) Hopping, that is simple enough to be described in three lines and has provable optimality guarantees. IQ-Hopping does not require any explicit channel measurements and can react within a matter of several seconds to bad channel conditions, including microwave ovens, hidden interferers, or dynamically varying congestion. Through implementation and experiments on off-the-shelf WiFi routers (OpenWRT, MadWiFi), we demonstrate the effectiveness of IQ-Hopping.

Cellular networks are constantly evolving due to frequent changes in radio access and end user equipment technologies, applications, and traffic. Network upgrades should be performed with extreme caution since millions of users heavily depend on the cellular networks. Before upgrading the entire network, it is important to conduct field evaluation of upgrades.The choice and number of field test locations have significant impact on the time-to-market and confidence in how well various network upgrades will work out in the rest of the network. We propose a novel approach -- Reflection to automatically determine where to conduct the upgrade field tests to accurately identify important features that affect the upgrade and predict for the performance of untested locations. We demonstrate its effectiveness using real traces collected from a major US cellular network as well as synthetic traces.

While recent works on multiuser MIMO (MU-MIMO) mainly focus on boosting the throughput by enabling concurrent transmissions, less attention is paid to recovering concurrent erroneous streams. We however notice that uplink MU-MIMO is especially vulnerable to errors because error in any stream corrupts most of the other concurrent streams. Even worse, carrier sense and rate adaptation become more challenging in MU-MIMO, which further decreases reliability. Existing systems however recover errors by retransmitting all the streams in a corrupted packet, thereby taking away the significant performance benefit of MU-MIMO. To effectively harness the ideal gain of MU-MIMO, we develop Concurrent Packet Recovery (CPR), a recovery protocol customized for MU-MIMO. It has two distinctive features: (i) It judiciously selects the minimum number of streams to be retransmitted to support successful decoding; (ii) during retransmission, it utilizes the full degrees of freedom by allowing new streams to be sent in parallel. Our evaluation via testbed experiments and trace-driven simulations shows that CPR can efficiently recover both normal losses and collisions. For three-antenna AP scenarios, the throughput gain is up to 31.1 percent when no hidden terminal exists, and is 3.16× when 20 percent pairs of contending clients are hidden terminals.

Wireless spectrum is a precious resource and must be allocated and used efficiently. Conventional spectrum allocations let a government agency (e.g., FCC) sell a portion of spectrum to one provider. This is not only restrictive, but also limits spectrum reuse and may lead to significant under-utilization of spectrum. In this paper, we develop a novel truthful double-auction scheme to let any resource owner (e.g., a cellular provider), who has spare spectrum at a given time period, sell to one or more providers that need additional spectrum at that time. Spectrum auctions are fundamentally different from conventional auction problems since spectrum can be reused and competition among buyers is complex due to wireless interference. Our proposal is the first double-auction design for spectrum allocation that explicitly decouples the buyer-side and seller-side auction design while achieving: 1) truthfulness; 2) individual rationality; and 3) budget-balance. To accurately capture wireless interference and support spectrum reuse, we partition the conflict graph so that buyers with strong direct and indirect interference are put into the same subgraph, and buyers with no interference or weak interference are put into separate subgraphs. Then, we compute pricing independently within each subgraph. We then develop a scheme to combine spectrum allocation results from different subgraphs and resolve potential conflicts. We further extend our approach to support local sellers whose spectrum can only be sold to buyers within certain regions, instead of all buyers. Using conflict graphs generated from real cell tower locations, we extensively evaluate our approach and demonstrate that it achieves high efficiency, revenue, and utilization.

This paper proposes a novel routing protocol, DM+, to achieve distributed spatial multiplexing gain in wireless mesh networks. It lets multiple nodes simultaneously send and receive different streams over each hop. To realize this goal, we propose an optimization framework that jointly optimizes spatial multiplexing, routing, and rate limits while taking into account wireless interference. We further design and implement a practical routing protocol that (i) enforces the optimized multiplexed routes, (ii) synchronizes transmissions from different senders, (iii) encodes and decodes analog signals to support simultaneous transmissions, and (iv) compensates for the frequency offset incurred over a multihop path. Using QualNet simulation and USRP implementation, we show it significantly out-performs state-of-the-art shortest path routing and opportunistic routing protocols. To our knowledge, this is the first routing protocol and prototype that achieves distributed spatial multiplexing in a real multihop network.

Transmission failures are common in wireless networks due to dynamic channel conditions and unpredictable interference. To efficiently recover from failures, we proposea smart retransmission scheme where the receiver combines information received from multiple failed transmissions associated with the same frame. The smart retransmission has two distinguishing features: (i) it can simultaneously supportpartial retransmission and combines bits with low confidence, and (ii) it has the first combining-aware rate adaptation scheme, which selects the data rates for all transmissions associated withthe same frame to maximize overall throughput. We find thatcombining-aware rate adaptation is essential to harnessing thecombining gain. Using trace-driven simulation and USRP testbedexperiments, we demonstrate the feasibility and effectiveness ofour approach, and show it significantly out-performs the existingschemes, such as WiFi, partial packet recovery (PPR), andSOFT in terms of both throughput and energy.

Wireless video traffic has grown at an unprecedented rate and put significant burden on wireless networks. Multicast can significantly reduce traffic by sending a single video to multiple receivers simultaneously. On the other hand, wireless receivers are heterogeneous due to both channel and antenna heterogeneity, the latter of which is rapidly increasing with the emergence of 802.11n and 802.11ac. In this paper, we develop optimized layered integrated video encoding (LIVE) to guarantee reasonable performance to weaker receivers (with worse channel and/or fewer antennas) and allow stronger receivers to enjoy better quality. Our approach has three distinct features: (i) It uses a novel layered coding to naturally accommodate the heterogeneity of different video receivers; (ii) It uses an optimization framework to optimize the amount of time used for transmission and the amount of information to transmit at each layer under the current channel condition; and (iii) It uses an integrated modulation, where most video data are transmitted using soft modulation to enjoy efficiency and resilience while the most important video data are transmitted using a combination of soft modulation and conventional hard modulation to further enhance their reliability. To our knowledge, this is the first approach that handles MIMO antenna heterogeneity in wireless video multicast. We demonstrate its effectiveness through extensive Matlab simulation and USRP testbed experiments.

Motivated by the recent push to deploy LTE in unlicensed spectrum, this paper develops a novel system to enable co-existence between LTE and WiFi. Our approach leverages LTE and WiFi antennas already available on smartphones to let LTE and WiFi transmit together and successfully decode the interfered signals. Our system offers several distinct advantages over existing MIMO work: (i) it can decode all the interfering signals under cross technology interference even when the interfering signals have similar power and occupy similar frequency, (ii) it does not need clean reference signals from either WiFi or LTE transmission, (iii) it can decode interfering WiFi MIMO and LTE transmissions, and (iv) it has a simple yet effective carrier sense mechanism for WiFi to access the medium under interfering LTE signals while avoiding other WiFi transmissions. We use USRP implementation and experiments to show its effectiveness.

No abstract available.

A mouse has been one of the most successful user interfaces due to its intuitive use. As more devices are equipped with displays and offer rich options for users to choose from, a traditional mouse that requires a surface to operate is no longer sufficient. While different types of air mice are available in the market, they rely on accelerometers and gyroscopes, which significantly limit the accuracy and ease of use.

Fingerprinting the Operating System (OS) running on a device based on its traffic has several applications, such as NAT detection, policy enforcement in enterprise networks, and billing for shared access in mobile networks. In this paper, we propose to utilize several features in TCP/IP headers for OS identification, and use real traffic traces to evaluate the accuracy of fingerprinting. Our trace-driven study shows that several techniques that successfully fingerprint desktop OSes are not effective for fingerprinting mobile devices. Therefore, we propose new features for fingerprinting OSes on mobile devices. We also consider NAT/tethering detection, an important application of OS fingerprinting. We use the presence of multiple OSes from the same IP address along with TCP timestamp, clock frequency, and boot time to detect tethering. Evaluation shows that our approach effectively detects tethering and outperforms existing schemes.

Wireless spectrum is a precious resource and must be allocated and used efficiently. The conventional spectrum allocation lets a government (e.g., FCC) sell a given portion of spectrum to one provider. This is not only restrictive, but also limits spectrum reuse and may lead to significant under-utilization of spectrum. In this paper, we develop a novel truthful double auction scheme to let any resource owner (e.g., a cellular provider), who has spare spectrum at a given time, sell to one or more providers that need additional spectrum at that time. Spectrum auction is fundamentally different from conventional auction problems since spectrum can be re-used and competition pattern is complex due to wireless interference. We propose the first double auction design for spectrum allocation that explicitly decouples the buyer side and seller side auction design while achieving (i) truthfulness, (ii) individual rationality, and (iii) budget balance. To accurately capture wireless interference and support spectrum reuse, we partition the conflict graph so that buyers with strong direct and indirect interference are put into the same subgraph and buyers with no or weak interference are put into separate subgraphs and then compute pricing independently within each subgraph. We develop a merge scheme to combine spectrum allocation results from different subgraphs and resolve potential conflicts. Using conflict graphs generated from real cell tower locations, we extensively evaluate our approach and demonstrate that it achieves high efficiency, revenue, and utilization.

Despite significant advances, supporting high-quality large video conferences at a low cost remains a significant challenge due to stringent performance requirements, limited and heterogeneous client resources, and dynamic traffic demands. In this paper, we develop a simple yet effective valiant multicast routing to select application-layer routes and adapt streaming rates according to the current network condition. It consists of four novel components: (i) a valiant multicast routing using two random choices to effectively balance the load in the presence of uncertainty about the clients' load, (ii) a scheme to cluster clients based on their delay and adapt valiant multicast routing based on both upload capacity and locality, (iii) an approach to further leverage resources from other peers or nodes in content distribution network (CDN) to enhance performance, and (iv) a simple distributed scheme to adapt streaming rates according to the current network resources. Our real implementation and experiments show that our approach significantly out-performs existing multicast routing schemes and quickly adapts to changing traffic demands and network conditions.

Networks are constantly generating an enormous amount of rich diverse information. Such information creates exciting opportunities for network analytics. However, a major challenge to enable effective network analytics is the presence of missing data, measurement errors, and anomalies. Despite significant work in network analytics, fundamental issues remain: (i) the existing works do not explicitly account for anomalies or measurement noise, and incur serious performance degradation under significant noise or anomalies, and (ii) they assume network matrices have low-rank structure, which may not hold in reality.

No abstract available.

We consider the problem of tracking physical browsing by users in indoor spaces such as retail stores. Analogous to online browsing, where users choose to go to certain webpages, dwell on a subset of pages of interest to them, and click on links of interest while ignoring others, we can draw parallels in the physical setting, where a user might walk purposefully to a section of interest, dwell there for a while, gaze at specific items, and reach out for the ones that they wish to examine more closely.

We develop a novel trajectory-based localization scheme which (i) identifies a user's current trajectory based on the measurements collected while the user is moving, by finding the best match among the training traces (trajectory matching) and then (ii) localizes the user on the trajectory (localization). The core requirement of both the steps is an accurate and robust algorithm to match two time-series that may contain significant noise and perturbation due to differences in mobility, devices, and environments. To achieve this, we develop an enhanced Dynamic Time Warping (DTW) alignment, and apply it to RSS, channel state information, or magnetic field measurements collected from a trajectory. We use indoor and outdoor experiments to demonstrate its effectiveness.

The Guest Editor summarizes the three papers in this special section. These papers were presented at the Annual International Conference on Mobile Computing and Networking (MobiCom) held in August 2012 in Istanbul, Turkey.

The explosive growth of cellular traffic and its highly dynamic nature often make it increasingly expensive for a cellular service provider to provision enough cellular resources to support the peak traffic demands. In this paper, we propose iDEAL, a novel auction-based incentive framework that allows a cellular service provider to leverage resources from third-party resource owners on demand by buying capacity whenever needed through reverse auctions. iDEAL has several distinctive features: 1) iDEAL explicitly accounts for the diverse spatial coverage of different resources and can effectively foster competition among third-party resource owners in different regions, resulting in significant savings to the cellular service provider. 2) iDEAL provides revenue incentives for third-party resource owners to participate in the reverse auction and be truthful in the bidding process. 3) iDEAL is provably efficient. 4) iDEAL effectively guards against collusion. 5) iDEAL effectively copes with the dynamic nature of traffic demands. In addition, iDEAL has useful extensions that address important practical issues. Extensive evaluation based on real traces from a large US cellular service provider clearly demonstrates the effectiveness of our approach. We further demonstrate the feasibility of iDEAL using a prototype implementation.

Customer care calls serve as a direct channel for a service provider to learn feedbacks from their customers. They reveal details about the nature and impact of major events and problems observed by customers. By analyzing the customer care calls, a service provider can detect important events to speed up problem resolution. However, automating event detection based on customer care calls poses several significant challenges. First, the relationship between customers' calls and network events is blurred because customers respond to an event in different ways. Second, customer care calls can be labeled inconsistently across agents and across call centers, and a given event naturally give rise to calls spanning a number of categories. Third, many important events cannot be detected by looking at calls in one category. How to aggregate calls from different categories for event detection is important but challenging. Lastly, customer care call records have high dimensions (e.g., thousands of categories in our dataset). In this paper, we propose a systematic method for detecting events in a major cellular network using customer care call data. It consists of three main components: (i) using a regression approach that exploits temporal stability and low-rank properties to automatically learn the relationship between customer calls and major events, (ii) reducing the number of unknowns by clustering call categories and using L1norm minimization to identify important categories, and (iii) employing multiple classifiers to enhance the robustness against noise and different response time. For the detected events, we leverage Twitter social media to summarize them and to locate the impacted regions. We show the effectiveness of our approach using data from a large cellular service provider in the US.

The explosive growth of cellular traffic and its highly dynamic nature often make it increasingly expensive for a cellular service provider to provision enough cellular resources to support the peak traffic demands. In this paper, we propose iDEAL, a novel auction-based incentive framework that allows a cellular service provider to leverage resources from third-party resource owners on demand by buying capacity whenever needed through reverse auctions. iDEAL has several distinctive features: (i) iDEAL explicitly accounts for the diverse spatial coverage of different resources and can effectively foster competition among third-party resource owners in different regions, resulting in significant savings to the cellular service provider. (ii) iDEAL provides revenue incentives for third-party resource owners to participate in the reverse auction and be truthful in the bidding process. (iii) iDEAL is provably efficient. (iv) iDEAL effectively guards against collusion. (v) iDEAL effectively copes with the dynamic nature of traffic demands. In addition, iDEAL has useful extensions that address important practical issues. Extensive evaluation based on real traces from a large US cellular service provider clearly demonstrates the effectiveness of our approach. We further demonstrate the feasibility of iDEAL using a prototype implementation.

Users around the world have embraced new generation of mobile devices such as the smartphones at a remarkable rate. These devices are equipped with powerful communication and computation capabilities and they enable a wide range of exciting location-based services, e.g., location based ads, content prefetching etc. Many of these services can benefit from a better understanding of the smartphone user mobility, which may differ significantly from the general user mobility. Hence, previous works on understanding user mobility models and predicting user mobility may not directly apply to smartphone users. To overcome this, in this paper we analyze data from two popular location based social networks, where the users are real smartphone users and the places they check-in represent the typical locations where they use their smartphone applications. Specifically, we analyze how individual users move across different locations. We identify several factors that affect user mobility and their relative significance. We then leverage these factors to perform individual mobility prediction. We further show that our mobility prediction yields significant benefit to two important location based applications: content prefetching and shared ride recommendation.

Distributed multiple-input multiple-output (MIMO) promises a dramatic capacity increase. While significant theoretical work has been done on distributed MIMO at the physical layer, how to translate the physical layer innovation into tangible benefits to real networks remains open. In particular, realizing multi-point to multi-point MIMO involves the following challenges: (i) how to accurately synchronize multiple APs in phase and time in order to successfully deliver precoded signals to the clients, and (ii) how to develop a MAC protocol to effectively support multi-point to multi-point MIMO. In this paper, we develop a practical approach to address the above challenges. We implement multi-point to multi-point MIMO for both uplink and downlink to enable multiple APs to simultaneously communicate with multiple clients. We examine a number of important MAC design issues, such as how to access the medium, perform rate adaptation, support acknowledgments in unicast traffic, deal with losses/collisions, and schedule transmissions. We demonstrate its feasibility and effectiveness through a prototype implementation on USRP and SORA, two of the most well-known software defined radio platforms.

Explosive growth of WiFi traffic calls for new technologies to dramatically improve spectrum efficiency. In this paper, we propose an approach to adapt the spectrum on a per-frame basis. It consists of three major components: (i) a fine-grained spectrum access design that allows a sender and receiver to change their transmission and reception spectrum on demand, (ii) fast and accurate spectrum detection that allows a receiver to determine which spectrum is used by its sender on a per-frame basis by exploiting the IEEE 802.11 preamble structure, and (iii) an efficient spectrum allocation algorithm that determines which spectrum to use for each transmission by taking into account frequency diversity and interference. It can further be adapted to perform a joint assignment of spectrum, schedule, and access point (AP) for each frame. Using a SORA implementation and trace-driven simulation, we demonstrate the feasibility of per-frame spectrum adaptation and its significant benefit over existing channel assignment approaches. To our knowledge, this is the first per-frame spectrum adaptation prototype for WiFi networks.

Rate adaptation in WiFi networks has received significant attention recently. However, most existing work focuses on selecting the rate to maximize throughput. How to select a data rate to minimize energy consumption is an important yet under-explored topic. This problem is becoming increasingly important with the rapidly increasing popularity of MIMO deployment, because MIMO offers diverse rate choices (e.g., the number of antennas, the number of streams, modulation, and FEC coding) and selecting the appropriate rate has significant impact on power consumption.

This paper proposes VideoFountain, a novel service that deploys kiosks at popular venues to store and transmit digital media to users' personal devices using Wi-Fi access points, which may not have Internet connectivity. We leverage mobile users to deliver content to these kiosks. A key component in this design is an in-depth understanding of user mobility. We gather real mobility traces from two largest location-based social networks (Foursquare and Gowalla) and analyze both macroscopic and microscopic human mobility in different cities. Based on the insights we gain, we study several algorithms to determine the initial placement of content and design routing algorithms to optimize the content delivery. We further consider several practical issues, such as how to incentivize users to forward content, how to manage copyrights, how to ensure security, and how to achieve service discovery. We demonstrate the feasibility of VideoFountain using trace-driven simulations.

Opportunistic routing aims to improve wireless performance by exploiting communication opportunities arising by chance. A key challenge in opportunistic routing is how to achieve good, predictable performance despite the incidental nature of such communication opportunities and the complicated effects of wireless interference in IEEE 802.11 networks. To address the challenge, we develop a model-driven optimization framework to jointly optimize opportunistic routes and rate limits for both unicast and multicast traffic. A distinctive feature of our framework is that the performance derived from optimization can be achieved in a real IEEE 802.11 network. Our framework consists of three key components: 1) a model for capturing the interference among IEEE 802.11 broadcast transmissions; 2) a novel algorithm for accurately optimizing different performance objectives; and 3) effective techniques for mapping the resulting solutions to practical routing configurations. Extensive simulations and testbed experiments show that our approach significantly outperforms state-of-the-art shortest-path routing and opportunistic routing protocols. Moreover, the difference between the achieved performance and our model estimation is typically within 20%. Evaluation in dynamic and uncontrolled environments further shows that our approach is robust against inaccuracy introduced by a dynamic network and it also consistently outperforms the existing schemes. These results clearly demonstrate the effectiveness and accuracy of our approach.

The explosive growth of social networks has created numerous exciting research opportunities. A central concept in the analysis of social networks is a proximity measure, which captures the closeness or similarity between nodes in the network. Despite much research on proximity measures, there is a lack of techniques to efficiently and accurately compute proximity measures for large-scale social networks. In this paper, we embed the original massive social graph into a much smaller graph, using a novel dimensionality reduction technique termed Clustered Spectral Graph Embedding. We show that the embedded graph captures the essential clustering and spectral structure of the original graph and allow a wide range of analysis to be performed on massive social graphs. Applying the clustered embedding to proximity measurement of social networks, we develop accurate, scalable, and flexible solutions to three important social network analysis tasks: proximity estimation, missing link inference, and link prediction. We demonstrate the effectiveness of our solutions to the tasks in the context of large real-world social network datasets: Flickr, LiveJournal, and MySpace with up to 2 million nodes and 90 million links.

Despite advances in measurement technology, it is still challenging to reliably compile large-scale network datasets. For example, because of flaws in the measurement systems or difficulties posed by the measurement problem itself, missing, ambiguous, or indirect data are common. In the case where such data have spatio-temporal structure, it is natural to try to leverage this structure to deal with the challenges posed by the problematic nature of the data. Our work involving network datasets draws on ideas from the area of compressive sensing and matrix completion, where sparsity is exploited in estimating quantities of interest. However, the standard results on compressive sensing are: 1) reliant on conditions that generally do not hold for network datasets; and 2) do not allow us to exploit all we know about their spatio-temporal structure. In this paper, we overcome these limitations with an algorithm that has at its heart the same ideas espoused in compressive sensing, but adapted to the problem of network datasets. We show how this algorithm can be used in a variety of ways, in particular on traffic data, to solve problems such as simple interpolation of missing values, traffic matrix inference from link data, prediction, and anomaly detection. The elegance of the approach lies in the fact that it unifies all of these tasks and allows them to be performed even when as much as 98% of the data is missing.

Mobile social networks extend social networks in the cyberspace into the real world by allowing mobile users to discover and interact with existing and potential friends who happen to be in their physical vicinity. Despite their promise to enable many exciting applications, serious security and privacy concerns have hindered wide adoption of these networks. To address these concerns, in this paper we develop novel techniques and protocols to compute social proximity between two users to discover potential friends, which is an essential task for mobile social networks.We make three major contributions. First, we identify a range of potential attacks against friend discovery by analyzing real traces. Second, we develop a novel solution for secure proximity estimation, which allows users to identify potential friends by computing social proximity in a privacy-preserving manner. A distinctive feature of our solution is that it provides both privacy and verifiability, which are frequently at odds in secure multiparty computation. Third, we demonstrate the feasibility and effectiveness of our approaches using real implementation on smartphones and show it is efficient in terms of both computation time and power consumption.

Wireless multicarrier communication systems transmit data by spreading it over multiple subcarriers and are widely used today owing to their robustness to multipath fading, high spectrum efficiency, and ease of implementation. In this paper, we use real measurements to show there is significant frequency diversity in Wi-Fi channels, and propose a series of techniques to explicitly harness such frequency diversity. In particular, we leverage the Channel State Information (CSI), which captures the SNR on each subcarrier to (i) map symbols to subcarriers according to their importance, (ii) effectively recover partially corrupted FEC groups and facilitate FEC decoding, and (iii) develop MAC-layer FEC to offer different degrees of protection to the symbols according to their error rates at the PHY layer. We further develop a rate adaptation approach that works together with these optimization schemes. Our trace-driven simulation and testbed experiments based on USRP clearly demonstrate the effectiveness of our approaches.

Efficiently sharing spectrum among multiple users is critical to wireless network performance. In this paper, we propose a novel spectrum sharing protocol called Collision-Resistant Multiple Access (CRMA) to achieve high efficiency. In CRMA, each transmitter views the OFDM physical layer as multiple orthogonal but sharable channels, and independently selects a few channels for transmission. The transmissions that share the same channel naturally add up in the air. The receiver extracts the received signals from all the channels and efficiently decodes the transmissions by solving a simple linear system. We implement our approach in the Qualnet simulator and show that it yields significant improvement over existing spectrum sharing schemes. We also demonstrate the feasibility of our approach using implementation and experiments on GNU Radios.

Opportunistic routing achieves significant performance gain under lossy wireless links. In this paper, we develop a novel approach that exploits inter-flow network coding in opportunistic routing. A unique feature of our design is that it systematically optimizes end-to-end performance (e.g., total throughput). A key challenge to achieve this goal is a strong tension between opportunistic routing and inter-flow network coding: to achieve high reliability, opportunistic routing uses intra-flow coding to spread information across multiple nodes; this reduces the information reaching an individual node, which in turn reduces inter-flow coding opportunity. To address this challenge, we decouple opportunistic routing and inter-flow network coding by proposing a novel framework where an overlay network performs overlay routing and inter-flow coding without worrying about packet losses, while an underlay network uses optimized opportunistic routing and rate limiting to provide efficient and reliable overlay links for the overlay network to take advantage of. Based on this framework, we develop the first optimization algorithm to jointly optimize opportunistic routes, rate limits, inter-flow and intra-flow coding. We then develop a practical opportunistic routing protocol (O3) based on the optimization results. Using Qualnet simulation, we study the individual and aggregate benefits of opportunistic routing, inter-flow coding, and rate limits. Our results show that (i) rate limiting significantly improves the performance of all routing protocols, (ii) opportunistic routing is beneficial under high loss rates, whereas inter-flow coding is more effective under low loss rates, and (iii) O3 significantly out-performs state-of-the-art routing protocols by simultaneously leveraging optimized opportunistic routing, inter-flow coding, and rate limits.

Opportunistic routing aims to improve wireless performance by exploiting communication opportunities arising by chance. A key challenge in opportunistic routing is how to achieve good, predictable performance despite the incidental nature of such communication opportunities and the complicated effects of wireless interference in IEEE 802.11 networks. To address the challenge, we develop a model-driven optimization framework to jointly optimize opportunistic routes and rate limits for both unicast and multicast traffic. A distinctive feature of our framework is that the performance derived from optimization can be achieved in a real IEEE 802.11 network. Our framework consists of three key components: (i) a model for capturing the interference among IEEE 802.11 broadcast transmissions, (ii) a novel algorithm for accurately optimizing different performance objectives, and (iii) effective techniques for mapping the resulting solutions to practical routing configurations. Extensive simulations and testbed experiments show that our approach significantly outperforms state-of-the-art shortest path routing and opportunistic routing protocols. Moreover, the difference between the achieved performance and our model estimation is typically within 20%. Evaluation in dynamic and uncontrolled environments further shows that our approach is robust against inaccuracy introduced by a dynamic network and it also consistently out-performs the existing schemes. These results clearly demonstrate the effectiveness and accuracy of our approach.

We present VCD, a novel system for enabling high-bandwidth content distribution in vehicular networks. In VCD, a vehicle opportunistically communicates with nearby access points (APs) to download the content of interest. To fully take advantage of such transient contact with APs, we proactively push content to the APs that the vehicles will likely visit in the near future. In this way, vehicles can enjoy the full wireless capacity instead of being bottle-necked by the Internet connectivity, which is either slow or even unavailable. We develop a new algorithm for predicting the APs that will soon be visited by the vehicles. We then develop a replication scheme that leverages the synergy among (i) Internet connectivity (which is persistent but has limited coverage and low bandwidth), (ii) local wireless connectivity (which has high bandwidth but transient duration), (iii) vehicular relay connectivity (which has high bandwidth but high delay), and (iv) mesh connectivity among APs (which has high bandwidth but low coverage). We demonstrate the effectiveness of VCD system using trace-driven simulation and Emulab emulation based on real taxi traces. We further deploy VCD in two vehicular networks: one using 802.11b and the other using 802.11n, to demonstrate its effectiveness.

To take advantage of the broadcast nature of wireless communication, a number of opportunistic routing protocols have recently been proposed. In order to manage the extra signaling overhead associated with operation of the opportunistic routing, these schemes work in terms of `batches' that consist of multiple packets. While these opportunistic protocols can dramatically improve the total throughput, the use of batches means that they are best suited to bulk UDP transfer. However, in the Internet and wireless networks, the vast majority of the traffic is interactive (e.g., TCP/VoIP which requires close interactions and feedback between the two communicating end points). To effectively support interactive traffic, we develop a new opportunistic routing protocol, called RIPPLE. RIPPLE uses an expedited multi-hop transmission opportunity mechanism to achieve low signaling overhead and eliminate re-ordering, and uses a two-way packet aggregation technique to further reduce overhead. We implement the RIPPLE in NS-2 along with several existing routing protocols, including predetermined routing, shortest path routing, the early version of ExOR, MCExOR, and an IEEE 802.11n-like single-hop packet aggregation scheme called AFR. We compare their performance for long-and short-lived TCP transfers and VoIP traffic over a wide range of network conditions, including varying wireless channel states, collision levels, and types of network topologies. Our results show that the RIPPLE scheme consistently achieves 100% - 300% performance gains over other approaches.

Localization is a fundamental operation for many wireless networks. While GPS is widely used for location determination, it is unavailable in many environments either due to its high cost or the lack of line of sight to the satellites (e.g., indoors, under the ground, or in a downtown canyon). The limitations of GPS have motivated researchers to develop many localization schemes to infer locations based on measured wireless signals. However, most of these existing schemes focus on localization in static wireless networks. As many wireless networks are mobile (e.g., mobile sensor networks, disaster recovery networks, and vehicular networks), we focus on localization in mobile networks in this paper. We analyze real mobility traces and find that they exhibit temporal stability and low-rank structure. Motivated by this observation, we develop three novel localization schemes to accurately determine locations in mobile networks: (i) Low Rank based Localization (LRL), which exploits the low-rank structure in mobility, (ii) Temporal Stability based Localization (TSL), which leverages the temporal stability, and (iii) Temporal Stability and Low Rank based Localization (TSLRL), which incorporates both the temporal stability and the low-rank structure. These localization schemes are general and can leverage either mere connectivity (i.e., range-free localization) or distance estimation between neighbors (i.e., range-based localization). Using extensive simulations and testbed experiments, we show that our new schemes significantly outperform state-of-the-art localization schemes under a wide range of scenarios and are robust to measurement errors.

Network resiliency is crucial to IP network operations. Existing techniques to recover from one or a series of failures do not offer performance predictability and may cause serious congestion. In this paper, we propose Resilient Routing Reconfiguration (R3), a novel routing protection scheme that is (i) provably congestion-free under a large number of failure scenarios; (ii) efficient by having low router processing overhead and memory requirements; (iii) flexible in accommodating different performance requirements (e.g., handling realistic failure scenarios, prioritized traffic, and the trade-off between performance and resilience); and (iv) robust to both topology failures and traffic variations. We implement R3 on Linux using a simple extension of MPLS, called MPLS-ff. We then conduct extensive Emulab experiments and simulations using realistic network topologies and traffic demands. Our results show that R3 achieves near-optimal performance and is at least 50% better than the existing schemes under a wide range of failure scenarios.

As wireless hotspot business becomes a tremendous financial success, users of these networks have increasing motives to misbehave in order to obtain more bandwidth at the expense of other users. Such misbehaviors threaten the performance and availability of hotspot networks and have recently attracted increasing research attention. However, the existing work so far focuses on sender-side misbehavior. Motivated by the observation that many hotspot users receive more traffic than they send, we study greedy receivers in this paper. We identify a range of greedy receiver misbehaviors, and quantify their damage using both simulation and testbed experiments. Our results show that even though greedy receivers do not directly control data transmission, they can still result in very serious damage, including completely shutting off the competing traffic. To address the issues, we further develop techniques to detect and mitigate greedy receiver misbehavior, and demonstrate their effectiveness.

Routing protocols for large wireless networks must address the challenges of reliable packet delivery at increasingly large scales and with highly limited resources. Attempts to reduce routing state can result in undesirable worst-case routing performance, as measured by stretch, which is the ratio of the hop count of the selected path to that of the optimal path. We present a new routing protocol, Small State and Small Stretch (S4), which jointly minimizes the state and stretch. S4 uses a combination of beacon distance-vector-based global routing state and scoped distance-vector-based local routing state to achieve a worst-case stretch of 3 usingO(√(N)) routing state per node in anN-node network. Its average routing stretch is close to 1. S4 further incorporates local failure recovery to achieve resilience to dynamic topology changes. We use multiple simulation environments to assess performance claims at scale and use experiments in a 42-node wireless sensor network testbed to evaluate performance under realistic RF and failure dynamics. The results show that S4 achieves scalability, efficiency, and resilience in a wide range of scenarios.

Proximity measures quantify the closeness or similarity between nodes in a social network and form the basis of a range of applications in social sciences, business, information technology, computer networks, and cyber security. It is challenging to estimate proximity measures in online social networks due to their massive scale (with millions of users) and dynamic nature (with hundreds of thousands of new nodes and millions of edges added daily). To address this challenge, we develop two novel methods to efficiently and accurately approximate a large family of proximity measures. We also propose a novel incremental update algorithm to enable near real-time proximity estimation in highly dynamic social networks. Evaluation based on a large amount of real data collected in five popular online social networks shows that our methods are accurate and can easily scale to networks with millions of nodes.

With the phenomenal growth of wireless networks and applications, it is increasingly important to deliver content efficiently and reliably over wireless links. However, wireless performance is still far from satisfactory due to limited wireless spectrum, inherent lossy wireless medium, and imperfect packet scheduling. While significant research has been done to improve wireless performance, much of the existing work focuses on individual design space. We take a holistic approach to optimizing wireless performance and resilience. We propose Fast Resilient Jumbo frames (FRJ), which exploit the synergy between three important design spaces: (i) frame size selection, (ii) partial packet recovery, and (iii) rate adaptation. While these design spaces are seemingly unrelated, we show that there are strong interactions between them and effectively leveraging these techniques can provide increased robustness and performance benefits in wireless LANs. FRJ uses jumbo frames to boost network throughput under good channel conditions and uses partial packet recovery to efficiently recover packet losses under bad channel conditions. FRJ also utilizes partial recovery aware rate adaptation to maximize throughput under partial recovery. Using real implementation and testbed experiments, we show that FRJ out-performs existing approaches in a wide range of scenarios.

Many basic network engineering tasks (e.g., traffic engineering, capacity planning, anomaly detection) rely heavily on the availability and accuracy of traffic matrices. However, in practice it is challenging to reliably measure traffic matrices. Missing values are common. This observation brings us into the realm of compressive sensing, a generic technique for dealing with missing values that exploits the presence of structure and redundancy in many real-world systems. Despite much recent progress made in compressive sensing, existing compressive-sensing solutions often perform poorly for traffic matrix interpolation, because real traffic matrices rarely satisfy the technical conditions required for these solutions.

Multihop wireless mesh networks are becoming a new attractive communication paradigm owing to their low cost and ease of deployment. Routing protocols are critical to the performance and reliability of wireless mesh networks. Traditional routing protocols send traffic along predetermined paths and face difficulties in coping with unreliable and unpredictable wireless medium. In this paper, we propose a simple opportunistic adaptive routing protocol (SOAR) to explicitly support multiple simultaneous flows in wireless mesh networks. SOAR incorporates the following four major components to achieve high throughput and fairness: 1) adaptive forwarding path selection to leverage path diversity while minimizing duplicate transmissions, 2) priority timer-based forwarding to let only the best forwarding node forward the packet, 3) local loss recovery to efficiently detect and retransmit lost packets, and 4) adaptive rate control to determine an appropriate sending rate according to the current network conditions. We implement SOAR in both NS-2 simulation and an 18-node wireless mesh testbed. Our extensive evaluation shows that SOAR significantly outperforms traditional routing and a seminal opportunistic routing protocol, ExOR, under a wide range of scenarios.

Disruption tolerant networks (DTNs) are a class of networks in which no contemporaneous path may exist between the source and destination at a given time. In such a network, routing takes place with the help of relay nodes and in a store-and-forward fashion. If the nodes in a DTN are controlled by rational entities, such as people or organizations, the nodes can be expected to behave selfishly and attempt to maximize their utilities and conserve their resources. Since routing is an inherently cooperative activity, system operation will be critically impaired unless cooperation is somehow incentivized. The lack of end-to-end paths, high variation in network conditions, and long feedback delay in DTNs imply that existing solutions for mobile ad-hoc networks do not apply to DTNs. In this paper, we propose the use of pair-wise tit-for-tat (TFT) as a simple, robust and practical incentive mechanism for DTNs. Existing TFT mechanisms often face bootstrapping problems or suffer from exploitation. We propose a TFT mechanism that incorporates generosity and contrition to address these issues. We then develop an incentive-aware routing protocol that allows selfish nodes to maximize their own performance while conforming to TFT constraints. For comparison, we also develop techniques to optimize the system-wide performance when all nodes are cooperative. Using both synthetic and real DTN traces, we show that without an incentive mechanism, the delivery ratio among selfish nodes can be as low as 20% as what is achieved under full cooperation; in contrast, with TFT as a basis of cooperation among selfish nodes, the delivery ratio increases to 60% or higher as under full cooperation. We also address the practical challenges involved in implementing the TFT mechanism. To our knowledge, this is the first practical incentive-aware routing scheme for DTNs.

Wireless LANs (WLANs) have been deployed at a remarkable rate at university campuses, office buildings, airports, hotels, and malls. Providing efficient and reliable wireless communications is challenging due to inherent lossy wireless medium and imperfect packet scheduling that results in packet collisions. In this paper, we develop an efficient retransmission scheme (ER) for wirless LANs. Instead of retransmitting the lost packets in their original forms, ER codes packets lost at different destinations and uses a single retransmission to potentially recover multiple packet losses. We develop a simple and practical protocol to realize the idea and implement it in both simulation and testbed, and our results demonstrate the effectiveness of this approach.

As wireless hotspot business becomes a tremendous financial success, users of these networks have increasing motives to misbehave in order to obtain more bandwidth at the expense of other users. Such misbehaviors threaten the performance and availability of hotspot networks, and have recently attracted increasing research attention. However the existing work so far focuses on sender-side misbehavior. Motivated by the observation that many hotspot users receive more traffic than they send, we study greedy receivers in this paper. We identify a range of greedy receiver misbehaviors, and quantify their damage using both simulation and testbed experiments. Our results show that even though greedy receivers do not directly control data transmission, they can still result in very serious damage, including completely shutting off the competing traffic. To address the issues, we further develop techniques to detect and mitigate greedy receiver misbehavior, and demonstrate their effectiveness.

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.

Campus and enterprise wireless networks are increasingly characterized by ubiquitous coverage and rising traffic demands. Efficiently assigning channels to access points (APs) in these networks can significantly affect the performance and capacity of the WLANs. The state-of-the-art approaches assign channels statically, without considering prevailing traffic demands. In this paper, we show that the quality of a channel assignment can be improved significantly by incorporating observed traffic demands at APs and clients into the assignment process. We refer to this astraffic-aware channel assignment. We conduct extensive trace-driven and synthetic simulations and identify deployment scenarios where traffic-awareness is likely to be of great help, and scenarios where the benefit is minimal. We address key practical issues in using traffic-awareness, including measuring an interference graph, handling non-binary interference, collecting traffic demands, and predicting future demands based on historical information. We present an implementation of our assignment scheme for a 25-node WLAN testbed. Our testbed experiments show that traffic-aware assignment offers superior network performance under a wide range of real network configurations. On the whole, our approach is simple yet effective. It can be incorporated into existing WLANs with little modification to existing wireless nodes and infrastructure.

Reliability is critical to a variety of network applications. Unfortunately, due to lack of QoS support across ISP boundaries, it is difficult to achieve even two 9s (99%) reliability in toadyism Internet. In this paper, we propose SmartTunnel, an end-to-end approach to achieving reliability. A SmartTunnel is a logical point-to-point tunnel between two end points that spans multiple physical network paths. It achieves reliability by strategically allocating traffic onto multiple paths and performing FEC coding. Such an end-to-end approach requires no explicit QoS support from intermediate ISPs, and is therefore easy to deploy in today's Internet. To fully realize the potential of SmartTunnel, we analytically derive near-optimal traffic allocation schemes that minimize loss rates. We extensively evaluate our approach using trace-driven simulations, ns-2 simulations, and experiments on PlanetLab. Our results clearly demonstrate that SmartTunnel is effective in achieving high reliability.

We develop a general model to estimate the throughput and goodput between arbitrary pairs of nodes in the presence of interference from other nodes in a wireless network. Our model is based on measurements from the underlying network itself and is thus more accurate than abstract models of RF propagation such as those based on distance. The seed measurements are easy to gather, requiring only O(N) measurements in an N-node networks. Compared to existing measurement-based models, our model advances the state of the art in three important ways. First, it goes beyond pairwise interference and models interference among an arbitrary number of senders. Second, it goes beyond broadcast transmissions and models the more common case of unicast transmissions. Third, it goes beyond homogeneous nodes and models the general case of heterogeneous nodes with different traffic demands and different radio characteristics. Using simulations and measurements from two different wireless testbeds, we show that the predictions of our model are accurate in a wide range of scenarios.

Wireless LAN administrators often have to deal with the problem of sporadic client congestion in popular locations within the network. Existing approaches that relieve congestion by balancing the traffic load are encumbered by the modifications that are required to both access points and clients. We propose cell breathing, a well-known concept in cellular telephony, as a load balancing mechanism to handle client congestion in a wireless LAN. We develop power management algorithms for controlling the coverage of access points to handle dynamic changes in client workloads. We further incorporate hand-off costs and manufacturer specified power level constraints into our algorithms. Our approach does not require modification to clients or to the standard. It only changes the transmission power of beacon packets and does not change the transmission power of data packets to avoid the interactions with auto-rating. We analyze the worst-case bounds of the algorithms and show that they are either optimal or close to optimal. In addition, we evaluate our algorithms empirically using synthetic and real wireless LAN traces. Our results show that cell breathing significantly outperforms the commonly used fixed power scheme and performs at par with sophisticated load balancing schemes that require changes to both the client and access points

Traffic engineering plays a critical role in determining the performance and reliability of a network. A major challenge in traffic engineering is how to cope with dynamic and unpredictable changes in traffic demand. In this paper, we propose COPE, a class of traffic engineering algorithms that optimize for the expected scenarios while providing a worst-case guarantee for unexpected scenarios. Using extensive evaluations based on real topologies and traffic traces, we show that COPE can achieve efficient resource utilization and avoid network congestion in a wide variety of scenarios.

Multihoming is a popular method used by large enterprises and stub ISPs to connect to the Internet to reduce cost and improve performance. Recently researchers have studied the potential benefits of multihoming and proposed protocols and algorithms to realize these benefits. They focus on how to dynamically select which ISPs to use for forwarding and receiving packets, and assume that the set of subscribed ISPs is given a priori. In practice, a user often has the freedom to choose which subset of ISPs among all available ISPs to subscribe to. We call the problem of how to choose the optimal set of ISPs the ISP subscription problem. In this paper, We design a dynamic programming algorithm to solve the ISP subscription problem optimally. We also design a more efficient algorithm for a large class of common pricing functions. Using real traffic traces and realistic pricing data, we show that our algorithm reduces users' cost. Next we study how ISPs respond to users' optimal ISP subscription by adjusting their pricing strategies. We call this problem the ISP pricing problem. Using a realistic charging model, we formulate the problem as a non-cooperative game. We first prove that if cost is the only criterion used by a user to determine which subset of ISPs to subscribe to, at any equilibrium all ISPs receive zero revenue. We then study a more practical formulation in which different ISPs provide different levels of reliability and users choose ISPs to both improve reliability and reduce cost. We analyze this problem and show that at any equilibrium an ISP's revenue is positive and determined by its reliability.

The ability to discover the AS-level path between two end-points is valuable for network diagnosis, performance optimization, and reliability enhancement. Virtually all existing techniques and tools for path discovery require direct access to the source. However, the uncooperative nature of the Internet makes it difficult to get direct access to any remote end-point. Path inference becomes challenging when we have no access to the source or the destination. Moveover even when we have access to the source and know the forward path, it is nontrivial to infer the reverse path, since the Internet routing is often asymmetric.In this paper, we explore the feasibility of AS-level path inference without direct access to either end-points. We describe RouteScope-a tool for inferring AS-level paths by finding the shortest policy paths in an AS graph obtained from BGP tables collected from multiple vantage points. We identify two main factors that affect the path inference accuracy: the accuracy of AS relationship inference and the ability to determine the first AS hop. To address the issues, we propose two novel techniques: a new AS relation-ship inference algorithm, and a novel scheme to infer the first AS hop by exploiting the TTL information in IP packets. We evaluate the effectiveness of RouteScope using both BGP tables and the AS paths collected from public BGP gateways. Our results show that it achieves 70% - 88% accuracy in path inference.

Effective network troubleshooting is critical for maintaining efficient and reliable network operation. Troubleshooting is especially challenging in multihop wireless networks because the behavior of such networks depends on complicated interactions between many unpredictable factors such as RF noise, signal propagation, node interference, and traffic flows. In this paper we propose a new direction for research on fault diagnosis in wireless networks. Specifically, we present a diagnostic system that employs trace-driven simulations to detect faults and perform root cause analysis. We apply this approach to diagnose performance problems caused by packet dropping, link congestion, external noise, and MAC misbehavior. In a 25 node multihop wireless network, we are able to diagnose over 10 simultaneous faults of multiple types with more than 80% coverage. Our framework is general enough for a wide variety of wireless and wired networks.

Efficient integration of a multi-hop wireless network with the Internet is an important research problem. In a wireless neighborhood network, a few Internet transit access points (ITAPs), serving as gateways to the Internet, are deployed across the neighborhood; houses are equipped with low-cost antennas, and form a multi-hop wireless network among themselves to cooperatively route traffic to the Internet through the ITAPs. Furthermore, the placement of Internet TAPs is a critical determinant of system performance and resource usage. We explore the placement problem under three wireless link models. For each link model, we develop algorithms to make informed placement decisions based on neighborhood layouts, user demands, and wireless link characteristics. We also extend our algorithms to provide fault tolerance and handle significant workload variation. We evaluate our placement algorithms and show that our algorithms yield close to optimal solutions over a wide range of scenarios we have considered.

Recently we have seen an emergent trend of self adaptive routing in both Internet and wireless ad hoc networks. Although there are previous methods for computing the traffic equilibria of self adaptive routing (e.g., selfish routing), these methods use computationally demanding algorithms and require that a precise analytical model of the network be given. Also, it remains an open question how to design an adaptive routing scheme which ensures convergence to traffic equilibria in practice. In this paper we propose a simple, efficient, distributed probabilistic routing scheme for self adaptive routing in dynamic, realistic environments. Using both analysis and extensive simulations, we show that our scheme can converge to the desired traffic equilibrium (either user-optimal or network-optimal) very quickly. We find that user-optimal routing can achieve very close to optimal average latency in dynamic environments, but such performance often comes at the cost of seriously overloading certain links. To avoid link overloads, we improve adaptive routing by optimizing average user latency and link utilization simultaneously. Our evaluation shows that there is a trade-off between optimizing dual objectives, but the degradation in average latency is only marginal for typical link utilization requirements.

The wide-scale deployment of IEEE 802.11 wireless networks has generated significant challenges for Information Technology (IT) departments in corporations. Users frequently complain about connectivity and performance problems, and network administrators are expected to diagnose these problems while managing corporate security and coverage. Their task is particularly difficult due to the unreliable nature of the wireless medium and a lack of intelligent diagnostic tools for determining the cause of these problems.This paper presents an architecture for detecting and diagnosing faults in IEEE 802.11 infrastructure wireless networks. To the best of our knowledge, ours is the first paper to address fault diagnostic issues for these networks. As part of our architecture, we propose and evaluate a novel technique called Client Conduit, which enables boot-strapping and fault diagnosis of disconnected clients. We describe techniques for analyzing performance problems faced in a wireless LAN deployment. We also present an approach for detecting unauthorized access points. We have built a prototype of our fault diagnostic architecture on the Windows operating system using off-the-shelf IEEE 802.11 cards. The initial results show that our mechanisms are effective; furthermore, they impose low overheads when clients are not experiencing problems.

Multihoming is often used by large enterprises and stub ISPs to connect to the Internet. In this paper, we design a series of novel smart routing algorithms to optimize cost and performance for multihomed users. We evaluate our algorithms through both analysis and extensive simulations based on realistic charging models, traffic demands, performance data, and network topologies. Our results suggest that these algorithms are very effective in minimizing cost and at the same time improving performance. We further examine the equilibrium performance of smart routing in a global setting and show that a smart routing user can improve its performance without adversely affecting other users.

The problem of inferring the packet loss characteristics of Internet links using server-based measurements is investigated. Unlike much of existing work on network tomography that is based on active probing, we make inferences based on passive observation of end-to-end client-server traffic. Our work on passive network tomography focuses on identifying lossy links (i.e., the trouble spots in the network). We have developed three techniques for this purpose based on random sampling, linear optimization, and Bayesian inference using Gibbs sampling, respectively. We evaluate the accuracy of these techniques using both simulations and Internet packet traces. We find that these techniques can identify most of the lossy links in the network with a manageable false positive rate. For instance, simulation results indicate that the Gibbs sampling technique has over 80% coverage with a false positive rate under 5%. Furthermore, this technique provides a confidence indicator on its inference. We also perform inference based on Internet traces gathered at the busy microsoft.com Web site. However, validating these inferences is a challenging problem. We present a method for indirect validation that suggests that the false positive rate is manageable.

In this paper, we address the following question: given a specific placement of wireless nodes in physical space and a specific traffic workload, what is the maximum throughput that can be supported by the resulting network? Unlike previous work that has focused on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, we work with any given network and workload specified as inputs.A key issue impacting performance is wireless interference between neighboring nodes. We model such interference using a conflict graph, and present methods for computing upper and lower bounds on the optimal throughput for the given network and workload. To compute these bounds, we assume that packet transmissions at the individual nodes can be finely controlled and carefully scheduled by an omniscient and omnipotent central entity, which is unrealistic. Nevertheless, using ns-2 simulations, we show that the routes derived from our analysis often yield noticeably better throughput than the default shortest path routes even in the presence of uncoordinated packet transmissions and MAC contention. This suggests that there is opportunity for achieving throughput gains by employing an interference-aware routing protocol.

A recent trend in routing research is to avoid inefficiencies in network-level routing by allowing hosts to either choose routes themselves (e.g., source routing) or use overlay routing networks (e.g., Detour or RON). Such approaches result in selfish routing, because routing decisions are no longer based on system-wide criteria but are instead designed to optimize host-based or overlay-based metrics. A series of theoretical results showing that selfish routing can result in suboptimal system behavior have cast doubts on this approach. In this paper, we use a game-theoretic approach to investigate the performance of selfish routing in Internet-like environments. We focus on intra-domain network environments and use realistic topologies and traffic demands in our simulations. We show that in contrast to theoretical worst cases, selfish routing achieves close to optimal average latency in such environments. However, such performance benefit comes at the expense of significantly increased congestion on certain links. Moreover, the adaptive nature of selfish overlays can significantly reduce the effectiveness of traffic engineering by making network traffic less predictable.

Recently, there has been an increasing deployment of content distribution networks (CDNs) that offer hosting services to Web content providers. In this paper, we first compare the uncooperative pulling of Web contents used by commercial CDNs with the cooperative pushing. Our results show that the latter can achieve comparable users' perceived performance with only 4%-5% of replication and update traffic compared with the former scheme. Therefore, we explore how to efficiently push content to CDN nodes. Using trace-driven simulation, we show that replicating content in units of URLs can yield 60%-70% reduction in clients' latency, compared with replicating in units of Websites. However, it is very expensive to perform such a fine-grained replication. To address this issue, we propose to replicate content in units of clusters, each containing objects which are likely to be requested by clients that are topologically close. To this end, we describe three clustering techniques and use various topologies and several large Web server traces to evaluate their performance. Our results show that the cluster-based replication achieves performance close to that of the URL-based scheme, but only at 1%-2% of computation and management cost. In addition, by adjusting the number of clusters, we can smoothly trade off management and computation cost for better client performance. To adapt to changes in users' access patterns, we also explore incremental clustering that adaptively adds new documents to the existing content clusters. We examine both offline and online incremental clustering, where the former assumes access history is available while the latter predicts access pattern based on the hyperlink structure. Our results show that the offline clustering yields performance close to that of the complete re-clustering at much lower overhead. The online incremental clustering and replication cut down the retrieval cost by 4.6 times compared with random and by 8 times compared with no replication. Therefore it is especially useful to improve document availability during flash crowds.

Recently, there has been an increasing deployment of content distribution networks (CDNs) that offer hosting services to Web content providers. We first compare uncooperative pulling of Web contents, used by commercial CDNs, with cooperative pushing. The latter can achieve user perceived performance comparable to the former scheme with only 4-5% of replication and update traffic. Therefore, we explore how to push content to CDN nodes efficiently. Using trace-driven simulation, we show that replicating content in units of URLs can yield 60-70% reduction in clients' latency, compared to replicating in units of Web sites. However, such a fine-grained replication is very expensive. We propose to replicate content in units of clusters, each containing objects which are likely to be requested by clients that are topologically close. We describe three clustering techniques, and use various topologies and several large Web server traces to evaluate their performance. Cluster-based replication achieves 40-60% improvement over per Web site based replication. By adjusting the number of clusters, we can smoothly trade off the management and computation cost for better client performance. We also explore incremental clusterings that adaptively add new documents to the existing content clusters. We examine both offline and online incremental clusterings. The offline clusterings yield close to the performance of the complete re-clustering at much lower overhead. The online incremental clustering and replication cut down the retrieval cost by 4.6-8 times compared to no replication and random replication, so it is especially useful for improving document availability during flash crowds.

No abstract available.

With the increasing popularity of handheld devices and wireless local area networks (LANs), real-time applications such as Internet telephony are poised to become ubiquitous. While there has been a substantial amount of research on quality of service problems in the Internet, most end-to-end bandwidth allocation approaches, such as RSVP, have had limited success due to scalability and deployment issues. Starting with the observation that reserving bandwidth in the Internet backbone requires substantial infrastructure support, but reserving bandwidth in the first hop does not, we only focus on the first-hop reservation. We evaluate several first hop allocation schemes and determine their effectiveness in improving end-to-end performance. Since utilization of the reserved first-hop bandwidth depends on the remaining Internet path throughput, we characterize this throughput using traces collected from a popular Web site. Our analysis shows that different clients experience widely different throughputs, and that a significant portion of the clients receive very low throughput (e.g. less than 20 Kbps). We then evaluate several bandwidth allocation schemes for various congestion scenarios. Our results show that the scheme which takes into account of both the application data rate and available Internet path bandwidth yields the best performance. Moreover, the scheme performs even better if it adapts to the changing path properties. We discuss how path bandwidth can be measured without active probing, how frequently it needs to be measured, and how this measurement is incorporated into the first-hop bandwidth allocation algorithm.

Encryption is often proposed as a tool for protecting the privacy of World Wide Web browsing. However, encryption-particularly as typically implemented in, or in concert with popular Web browsers-does not hide all information about the encrypted plaintext. Specifically, HTTP object count and sizes are often revealed (or at least incompletely concealed). We investigate the identifiability of World Wide Web traffic based on this unconcealed information in a large sample of Web pages, and show that it suffices to identify a significant fraction of them quite reliably. We also suggest some possible countermeasures against the exposure of this kind of information and experimentally evaluate their effectiveness.

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and diffserv. Classification can be based on an arbitrary number of fields in the packet header. Performing classification quickly on an arbitrary number of fields is known to be difficult, and has poor worst-case complexity. In this paper, we re-examine two basic mechanisms that have been dismissed in the literature as being too inefficient: backtracking search and set pruning tries. We find using real databases that the time for backtracking search is much better than the worst-case bound; instead of /spl Omega/((logN)/sup k-1/), the search time is only roughly twice the optimal search time. Similarly, we find that set pruning tries (using a DAG optimization) have much better storage costs than the worst-case bound. We also propose several new techniques to further improve the two basic mechanisms. Our major ideas are: (i) backtracking search on a small memory budget, (ii) a novel compression algorithm, (iii) pipelining the search, (iv) the ability to trade-off smoothly between backtracking and set pruning. We quantify the performance gain of each technique using real databases. We show that on real firewall databases our schemes, with the accompanying optimizations, are close to optimal in time and storage.

There has been an increasing deployment of content distribution networks (CDNs) that offer hosting services to Web content providers. CDNs deploy a set of servers distributed throughout the Internet and replicate provider content across these servers for better performance and availability than centralized provider servers. Existing work on CDNs has primarily focused on techniques for efficiently redirecting user requests to appropriate CDN servers to reduce request latency and balance load. However, little attention has been given to the development of placement strategies for Web server replicas to further improve CDN performance. We explore the problem of Web server replica placement in detail. We develop several placement algorithms that use workload information, such as client latency and request rates, to make informed placement decisions. We then evaluate the placement algorithms using both synthetic and real network topologies, as well as Web server traces, and show that the placement of Web replicas is crucial to CDN performance. We also address a number of practical issues when using these algorithms, such as their sensitivity to imperfect knowledge about client workload and network topology, the stability of the input data, and methods for obtaining the input.

Transport of real-time voice traffic on the Internet is difficult due to packet loss and jitter. Packet loss is handled primarily through a variety of different forward error correction (FEC) algorithms and local repair at the receiver. Jitter is compensated for by means of adaptive playout buffer algorithms at the receiver. Traditionally, these two mechanisms have been investigated in isolation. In this paper, we show the interactions between adaptive playout buffer algorithms and FEC, and demonstrate the need for coupling. We propose a number of novel playout buffer algorithms which provide this coupling, and demonstrate their effectiveness through simulations based on both network models and real network traces.

In this paper, we study the dynamics of the MSNBC news site, one of the busiest Web sites in the Internet today. Unlike many other efforts that have analyzed client accesses as seen by proxies, we focus on the server end. We analyze the dynamics of both the server content and client accesses made to the server. The former considers the content creation and modification process while the latter considers page popularity and locality in client accesses. Some of our key results are: (a) files tend to change little when they are modified, (b) a small set of files tends to get modified repeatedly, (c) file popularity follows a Zipf-like distribution with a parameter &agr that is much larger than reported in previous, proxy-based studies, and (d) there is significant temporal stability in file popularity but not much stability in the domains from which clients access the popular content. We discuss the implications of these findings for techniques such as Web caching (including cache consistency algorithms), and prefetching or server-based ``push'' of Web content.

We study the MSNBC Web site, one of the busiest in the Internet today. We analyze the dynamics of content creation and modification as well as client accesses. Our key findings are (a) files tend to change little upon modification, (b) a small set of files get modified repeatedly, (c) file popularity follows a Zipf-like distribution with an α much larger than reported in previous, proxy-based studies, and (d) there is significant temporal stability in file popularity but not much stability in the domains from which popular content is accessed. We discuss implications of these findings.

/sup A/s the most widely used reliable transport in today's Internet, TCP has been extensively studied in the past. However previous research usually only considers a small or medium number of concurrent TCP flows. The TCP behavior under many competing TCP flows has not been sufficiently explored. In this paper we use extensive simulations to investigate the individual and aggregate TCP performance for a large number of concurrent TCP flows. First, we develop a simple yet realistic network model to abstract an Internet connection. Based on the model, we study the performance of a single TCP flow with many competing TCP flows by evaluating the best-known analytical model proposed in the literature. Finally, we examine the aggregate TCP behavior and derive general conclusions about overall throughput, goodput, and loss probability.

This paper proposes a novel approach to the contour extraction of moving objects in an image sequence. Our approach is to fuse information from color segmentation, motion segmentation, and active contour (snake) to achieve accurate extraction of the boundary of moving objects. It works well not only for a single moving object, but also for images having multiple moving objects. Several experiments have been conducted to show the promise of our algorithm.