Video players must adapt bitrate quickly to avoid stalls while using available capacity, yet ABR decisions rely on delayed user-space signals. We present eBandit, an eBPF prototype that moves online ABR-policy selection into the kernel using a small multi-armed bandit, while leaving bitrate computation in the player. In live eBPF trace-replay evaluation, eBandit improves adversarial-trace QoE by 12.0% over the best static baseline, attains the highest mean QoE on 42 Norway HSDPA sessions while matching or beating the best static ABR in every session and improving 28.6% of them, with control-path overhead of only tens of microseconds.

Most deployed WAN Traffic Engineering (TE) systems use a logically centralized controller that periodically gathers traffic demands, runs a TE optimization or heuristic, and then programs the network. At scale, these solutions are often suboptimal and can take minutes to react to demand changes or failures. In this paper, we introduce OnlineTE, a system that reacts immediately to demand changes and failures and delivers near-optimal solutions within seconds of a change. OnlineTE builds on the theory of optimization decomposition to devise scalable, near-optimal, distributed TE solvers for path-based MLU and Max-Flow problems. In OnlineTE, switches each solve a local subproblem, and a central coordinator coordinates their convergence. As such, a switch can trigger a re-optimization as soon as it detects a demand change or failure, enabling high reactivity. OnlineTE scales to large WANs, and its computational requirements are well within the capabilities of modern WAN switches. It also enables a novel paradigm, edge-based TE, which can utilize resources more efficiently than today's path-based approaches. On a testbed emulation of a 750-node WAN topology, OnlineTE outperforms the state-of-the-art by up to an order of magnitude.

Granular resource heterogeneity refers to the phenomenon in which small computational units within or across applications exhibit distinct resource usage patterns. Traditional resource management in shared clusters lumps monolithic applications into coarse categories, overlooking smaller execution phases that differ in resource demands.

Increasingly, web content is automatically generated by large language models (LLMs) with little human input. We call this ''LLM-dominant'' content. Since LLMs plagiarize and hallucinate, LLM-dominant content can be unreliable and unethical. Yet, websites rarely disclose such content, and human readers struggle to distinguish it. Thus, we must develop reliable detectors for LLM-dominant content. However, state-of-the-art LLM detectors are inaccurate on web content, because web content has low positive rates, complex markup, and diverse genres, instead of clean, prose-like benchmark data SoTA detectors are optimized for.

Outdoor AR applications on mobile devices need accurate estimates for the pose of the device. In this paper, we develop SplatPose, a novel pose estimation technique that uses a data-driven 3D modeling technique called Gaussian Splatting. SplatPose uses a trained Gaussian Splatting model to render an image at an estimated device location, then matches features with the camera image to estimate pose. % Because this matching can be fast, SplatPose can, in theory, estimate pose entirely on a mobile device, while existing approaches cannot. To this end, SplatPose trains Gaussian Splatting models to be robust to appearance changes, thereby improving accuracy. It also incorporates a novel fast renderer to improve rendering speed. Using an AR pose estimation benchmark dataset, we show that SplatPose outperforms the state-of-the-art in terms of accuracy, and is up to an order of magnitude faster on a mobile device.

Today, large-scale software-defined networks use microservice-based controllers. Bugs in these controllers can reduce network availability by making the data plane state inconsistent with the high-level intent. To recover from such inconsistencies, modern controllers periodically reconcile the state of all the switches with the desired intent. However, periodic reconciliation limits the availability and performance of the network at scale. We introduce Zenith, a microservice-based controller that avoids inconsistencies by design rather than always relying on recovery mechanisms. We have formally verified Zenith's specifications and have proved that it ensures the network state will eventually be consistent with intent. We automatically generate Zenith's code from its specification to minimize the likelihood of errors in the final implementation. Zenith's guarantees and abstractions also enable developers to independently verify SDN applications and ensure end-to-end safety and correctness. Zenith resolves inconsistencies 5× faster than today's designs and significantly improves availability.

Cloud-based financial exchanges require sub-10ns device-to-device clock synchronization accuracy while adhering to Coordinated Universal Time (UTC). Existing clock sync techniques struggle to meet this demand at scale and are vulnerable to clock drift, jitter, and path asymmetries. Firefly, a software-driven datacenter clock sync system, scalably, cost-effectively, and reliably achieves very high clock sync accuracy. It employs a distributed consensus algorithm on a random overlay graph to rapidly converge to a common time while applying gradual adjustments to device hardware clocks. To realize consistent sync-to-UTC (external sync) across devices while maintaining a stable device-to-device internal sync, Firefly uses a novel technique, layered synchronization, that decouples internal and external syncs. In a 248-machine Clos network, Firefly achieves sub-10ns device-to-device and ≤1μs device-to-UTC sync, and is resilient to time server failure and unstable clocks.

We propose a performance analysis tool for learning-enabled systems that allows operators to uncover potential performance issues before deploying DNNs in their systems. The tools that exist for this purpose require operators to faithfully model all components (a white-box approach) or do inefficient black-box local search. We propose a gray-box alternative, which eliminates the need to precisely model all the system's components. Our approach is faster and finds substantially worse scenarios compared to prior work. We show that a state-of-the-art learning-enabled traffic engineering pipeline can underperform the optimal by 6× --- a much higher number compared to what the authors found.

On-vehicle 3D sensing technologies, such as LiDARs and stereo cameras, enable a novel capability, 3D traffic reconstruction. This produces a volumetric video consisting of a sequence of 3D frames capturing the time evolution of road traffic. 3D traffic reconstruction can help trained investigators reconstruct the scene of an accident. In this paper, we describe the design and implementation of RECAP, a system that continuously and opportunistically produces 3D traffic reconstructions from multiple vehicles. RECAP builds upon prior work on point cloud registration, but adapts it to settings with minimal point cloud overlap (both in the spatial and temporal sense) and develops techniques to minimize error and computation time in multi-way registration. On-road experiments and trace-driven simulations show that RECAP can, within minutes, generate highly accurate reconstructions that have 2× or more lower errors than competing approaches.

Time-sensitive networking (TSN) Task Group of the IEEE proposed the frame replication and elimination for reliability (FRER) technique to guarantee reliable transmissions in TSN for the emerging Industrial Internet of Things (IIoT). FRER is a technique that manages the replication and elimination of frames of a stream sent through multiple paths as member streams. However, the standard does not specify how to find and select the multiple paths to send the replicated member streams on, nor how the time-aware shaper (TAS) should be scheduled considering frame elimination. Most prior work on routing or TAS scheduling in TSN do not consider FRER. Conversely, studies on FRER do not address the routing and scheduling issues effectively. In this article, we propose multipath routing and TAS scheduling strategies to support FRER in TSN with reduced complexity. We also identify a scheduling deadlock problem due to the unique characteristics of FRER, and propose a solution using topological sorting. Then, we propose two metaheuristic optimizers to increase the TAS scheduling success rate. Through extensive evaluation against state-of-the-art prior work, we show that our strategies can support more flows with reduced utilization and enhanced schedulability while effectively handling the complexity of routing and scheduling problems for FRER.

Tracking the position and orientation, or pose, of a viewing device enables AR applications to accurately embed virtual content in physical spaces. Mobile OSs track pose by matching device camera images against street-level imagery. Thus, pose tracking is often unavailable at off-street pedestrian locations. UbiPose enables pose tracking at such locations using aerial meshes, generated from satellite imagery, that are likely to be more widely available at these locations. However, matching a camera image against an aerial mesh can be error-prone, even with modern neural matchers. These neural components are also compute-intensive. UbiPose contains a novel pose tracking pipeline that runs entirely on a mobile device using fast-path optimizations designed to accept or reject pose estimates in many cases, without sacrificing accuracy. Experiments on real-world traces show that it achieves tracking accuracy comparable to AR pose tracking in iOS in places where that is available, and is able to track pose accurately in places where it is not.

When streaming 360° video, it is possible to reduce bandwidth by 5× with approaches that spatially segment video into tiles and only stream the user's viewport. Unfortunately, it is difficult to accurately predict a user's viewport even 2--3 seconds before playback. This results in rebuffering events owing to misprediction of a user's viewport or network bandwidth dips, which hurts interactive experience. However, avoiding rebuffering by naively skipping tiles that do not arrive by the playback deadline may lead to incomplete viewports and degraded experience.

To guarantee real-time performance and quality-of-service (QoS) of time-critical industrial systems, time-aware shaper (TAS) in time-sensitive networking (TSN) controls frame transmission times in a bridged network using a scheduled gate control mechanism. However, most TAS scheduling methods generate schedules based on pre-configured routes without exploring alternatives for better schedulability, and methods that jointly consider routing and scheduling require enormous runtime and computing resources. To address this problem, we propose a TSN Scheduler with Reinforcement Learning-based Routing (TSLR) that identifies improved load balanced routes for higher schedulability with acceptable complexity using distributional reinforcement learning. We evaluate TSLR through TSN simulations and compare it against state-of-the-art algorithms to demonstrate that TSLR effectively improves TAS schedulability and link utilization in TSN with lower complexity. Specifically, TSLR shows a more than 66% increase in schedulability compared to the other algorithms, and TSLR’s scheduling time is reduced by more than 1 h. It also shows flows’ transmission latency is less than 25% of their latency deadline requirement and reduces maximum link utilization by approximately 50%.

While most networks have long lifetimes, temporary network infrastructure is often useful for special events, pop-up retail, or disaster response. Aninstant IoTnetwork is one that is rapidly constructed, used for a few days, then dismantled. We consider the synthesis of instant IoT networks in urban settings. This synthesis problem must satisfy complex and competing constraints: sensor coverage, line-of-sight visibility, and network connectivity. The central challenge in our synthesis problem is quicklyscalingto large regions while producing cost-effective solutions. We explore two qualitatively different representations of the synthesis problems using satisfiability modulo convex optimization (SMC), and mixed-integer linear programming (MILP). The former is more expressive, for our problem, than the latter, but is less well-suited for solving optimization problems like ours. We show how to express our network synthesis in these frameworks. To scale to problem sizes beyond what these frameworks are capable of, we develop ahierarchical synthesistechnique that independently synthesizes networks in sub-regions of the deployment area, then combines these. We find that, while MILP outperforms SMC in some settings for smaller problem sizes, the fact that SMC's expressivity matches our problem ensures that it uniformly generates better quality solutions at larger problem sizes.

Oblivious routing distributes traffic from sources to destinations following predefined routes with rules independent of traffic demands. While finding optimal oblivious routing with a concave objective is intractable for general topologies, we show that it is tractable for structured topologies often used in datacenter networks. To achieve this, we apply graph automorphism and prove the existence of the optimal automorphism-invariant solution. This result reduces the search space to targeting the optimal automorphism-invariant solution. We design an iterative algorithm to obtain such a solution by alternating between convex optimization and a linear program. The convex optimization finds an automorphism-invariant solution based on representative variables and constraints, making the problem tractable. The linear program generates adversarial demands to ensure the final result satisfies all possible demands. Since the construction of the representative variables and constraints are combinatorial problems, we design polynomial-time algorithms for the construction. We evaluate the iterative algorithm in terms of throughput performance, scalability, and generality over three potential applications. The algorithm i) improves the throughput up to 87.5% for partially deployed FatTree and achieves up to$2.55\times $throughput gain for DRing over heuristic algorithms, ii) scales for three considered topologies with a thousand switches, iii) applies to a general structured topology with non-uniform link capacity and server distribution.

Network Functions (NFs) now process a significant fraction of Internet traffic. Software-based NF Virtualization (NFV) promised to enable rapid development of new NFs by vendors and leverage the power and economics of commodity computing infrastructure for NF deployment. To date, no cloud NFV systems achieve NF chaining, isolation, SLO-adherence, and scaling together with existing cloud computing infrastructure and abstractions, all while achieving generality, speed, and ease of deployment. These properties are taken for granted in other cloud contexts but unavailable for NF processing.

Oblivious routing distributes traffic from sources to destinations following predefined routes with rules independent of traffic demands. While finding optimal oblivious routing is intractable for general topologies, we show that it is tractable for structured topologies often used in datacenter networks. To achieve this, we apply graph automorphism and prove the existence of the optimal automorphism-invariant solution. This result reduces the search space to targeting the optimal automorphism-invariant solution. We design an iterative algorithm to obtain such a solution by alternating between two linear programs. The first program finds an automorphism-invariant solution based on representative variables and constraints, making the problem tractable. The second program generates adversarial demands to ensure the final result satisfies all possible demands. Since, the construction of the representative variables and constraints are combinatorial problems, we design polynomial-time algorithms for the construction. We evaluate proposed iterative algorithm in terms of throughput performance, scalability, and generality over three potential applications. The algorithm i) improves the throughput up to 87.5% over a heuristic algorithm for partially deployed FatTree, ii) scales for FatClique with a thousand switches, iii) is applicable to a general structured topology with non-uniform link capacity and server distribution.

Autonomous vehicles use 3D sensors for perception. Cooperative perception enables vehicles to share sensor readings with each other to improve safety. Prior work in cooperative perception scales poorly even with infrastructure support. AUTOCAST1 enables scalable infrastructure-less cooperative perception using direct vehicle-to-vehicle communication. It carefully determines which objects to share based on positional relationships between traffic participants, and the time evolution of their trajectories. It coordinates vehicles and optimally schedules transmissions in a distributed fashion. Extensive evaluation results under different scenarios show that, unlike competing approaches, AUTOCAST can avoid crashes and near-misses which occur frequently without cooperative perception, its performance scales gracefully in dense traffic scenarios providing 2-4x visibility into safety critical objects compared to existing cooperative perception schemes, its transmission schedules can be completed on the real radio testbed, and its scheduling algorithm is near-optimal with negligible computation overhead.

Public outdoor surveillance cameras often have limited metadata describing their properties. Frequently, a public camera’s precise position, orientation, focal length, and image center are unknown; these attributes are necessary to precisely pinpoint the location of events seen in the camera. In this article, we ask: what is the minimal information needed to accurately estimate these properties for public cameras? We show, using a judicious combination of projective geometry, neural networks, and crowd-sourced annotations from human workers, that it is possible to, for example, localize 95% of the cameras in our test data set to within 12 m using a single image taken from the camera. This performance is an order of magnitude better than PoseNet, a state-of-the-art neural network that needs significantly more information than our approach, and can only estimate position and orientation (and not other properties). Finally, we show that the camera’s inferred pose and properties can help design a number of virtual sensors , all of which have good accuracy.

Advances in deep learning (DL) have prompted the development of cloud-hosted DL-based media applications that process video and audio streams in real-time. Such applications must satisfy throughput and latency objectives and adapt to novel types of dynamics, while incurring minimal cost. Scrooge, a system that provides media applications as a service, achieves these objectives by packing computations efficiently into GPU-equipped cloud VMs, using an optimization formulation to find the lowest cost VM allocations that meet the performance objectives, and rapidly reacting to variations in input complexity (e.g., changes in participants in a video). Experiments show that Scrooge can save serving cost by 16-32% (which translate to tens of thousands of dollars per year) relative to the state-of-the-art while achieving latency objectives for over 98% under dynamic workloads.

While prior work has explored many proposed datacenter designs, only two designs, Clos-based and expander-based, are generally considered practical because they can scale using commodity switching chips. Prior work has used two different metrics, bisection bandwidth and throughput, for evaluating these topologies at scale. Little is known, theoretically or practically, how these metrics relate to each other. Exploiting characteristics of these topologies, we prove an upper bound on their throughput, then show that this upper bound better estimates worst-case throughput than all previously proposed throughput estimators and scales better than most of them. Using this upper bound, we show that for expander-based topologies, unlike Clos, beyond a certain size of the network, no topology can have full throughput, even if it has full bisection bandwidth; in fact, even relatively small expander-based topologies fail to achieve full throughput. We conclude by showing that using throughput to evaluate datacenter performance instead of bisection bandwidth can alter conclusions in prior work about datacenter cost, manageability, and reliability.

For decades, Internet protocols have been specified using natural language. Given the ambiguity inherent in such text, it is not surprising that protocol implementations have long exhibited bugs. In this paper, we apply natural language processing (NLP) to effect semi-automated generation of protocol implementations from specification text. Our system, Sage, can uncover ambiguous or under-specified sentences in specifications; once these are clarified by the author of the protocol specification, Sage can generate protocol code automatically.

Network Functions (NFs) perform on-path processing of network traffic. ISPs are deploying NF Virtualization (NFV) with software NFs run on commodity servers. ISPs aim to ensure that NF chains, directed acyclic graphs of NFs, do not violate Service Level Objectives (SLOs) promised by the ISP to its customers. To meet SLOs, NFV systems sometimes leverage on-path hardware (such as programmable switches and smart NICs) to accelerate NF execution.

Advances in optimization and constraint satisfaction techniques, together with the availability of elastic computing resources, have spurred interest in large-scale network verification and synthesis. Motivated by this, we consider the top-down synthesis of ad-hoc IoT networks for disaster response and search and rescue operations. This synthesis problem must satisfy complex and competing constraints: sensor coverage, line-of-sight visibility, and network connectivity. The central challenge in our synthesis problem is quickly scaling to large regions while producing cost-effective solutions. We explore a representation of the synthesis problems using a novel constraint satisfaction paradigm, satisfiability modulo convex optimization (SMC). We choose SMC because it matches the expressivity needs for our network synthesis. To scale to large problem sizes, we develop a hierarchical synthesis technique that independently synthesizes networks in sub-regions of the deployment area, then combines these. Our experiments show that SMC consistently generates better quality solutions than a baseline synthesis approach based on Mixed Integer Linear Programming (MILP).

Persistent surveillance with aerial vehicles (drones) subject to connectivity and power constraints is a relatively uncharted domain of research. To reduce the complexity of multi-drone motion planning, most state-of-the-art solutions ignore network connectivity and assume unlimited battery power. Motivated by this and advances in optimization and constraint satisfaction techniques, we introduce a new persistent surveillance motion planning problem for multiple drones that incorporates connectivity and power consumption constraints. We use a recently developed constrained optimization tool (Satisfiability Modulo Convex Optimization (SMC)) that has the expressivity needed for this problem. We show how to express the new persistent surveillance problem in the SMC framework. Our analysis of the formulation based on a set of simulation experiments illustrates that we can generate the desired motion planning solution within a couple of minutes for small teams of drones (up to 5) confined to a 7 × 7 × 1 grid-space.

The field of IoT has blossomed and is positively influencing many application domains. In this article, we bring out the unique challenges this field poses to research in computer systems and networking. The unique challenges arise from the unique characteristics of IoT systems such as the diversity of application domains where they are used and the increasingly demanding protocols they are being called upon to run (such as video and LIDAR processing) on constrained resources (on-node and network). We show how these open challenges can benefit from foundations laid in other areas, such as fifth-generation network cellular protocols, machine learning model reduction, and device-edge-cloud offloading. We then discuss the unique challenges for reliability, security, and privacy posed by IoT systems due to their salient characteristics which include heterogeneity of devices and protocols, dependence on the physical environment, and the close coupling with humans. We again show how open research challenges benefit from the reliability, security, and privacy advancements in other areas. We conclude by providing a vision for a desirable end state for IoT systems.

Video dominates Internet traffic today. Users retrieve on-demand video from Content Delivery Networks (CDNs) which cache video chunks at front-ends. In this paper, we describe AViC, a caching algorithm that leverages properties of video delivery, such as request predictability and the presence of highly unpopular chunks. AViC's eviction policy exploits request predictability to estimate a chunk's future request time and evict the chunk with the furthest future request time. Its admission control policy uses a classifier to predict singletons --- chunks evicted before a second reference. Using real world CDN traces from a commercial video service, we show that AViC outperforms a range of algorithm including LRU, GDSF, AdaptSize and LHD. In particular LRU requires up to 3.5× the cache size to match AViC's performance. Further, AViC has low time complexity and has memory complexity comparable to GDSF.

Detecting activities from video taken with a single camera is an active research area for ML-based machine vision. In this paper, we examine the next research frontier: near real-time detection of complex activities spanning multiple (possibly wireless) cameras, a capability applicable to surveillance tasks. We argue that a system for such complex activity detection must employ a hybrid design: one in which rule-based activity detection must complement neural network based detection. Moreover, to be practical, such a system must scale well to multiple cameras and have low end-to-end latency. Caesar, our edge computing based system for complex activity detection, provides an extensible vocabulary of activities to allow users to specify complex actions in terms of spatial and temporal relationships between actors, objects, and activities. Caesar converts these specifications to graphs, efficiently monitors camera feeds, partitions processing between cameras and the edge cluster, retrieves minimal information from cameras, carefully schedules neural network invocation, and efficiently matches specification graphs to the underlying data in order to detect complex activities. Our evaluations show that Caesar can reduce wireless bandwidth, on-board camera memory, and detection latency by an order of magnitude while achieving good precision and recall for all complex activities on a public multi-camera dataset.

The performance and availability of cloud and content providers often depends on the wide area networks (WANs) they use to interconnect their datacenters. WAN routers, which connect to each other using trunks (bundles of links), are sometimes built using an internal Clos topology connecting merchant-silicon switches. As such, these routers are susceptible to internal link and switch failures, resulting in reduced capacity and low availability. Based on the observation that today's WAN routers use relatively simple trunk wiring and routing techniques, we explore the design of novel wiring and more sophisticated routing techniques to increase failure resilience. Specifically, we describe techniques to 1) optimize trunk wiring to increase effective internal router capacity so as to be resilient to internal failures, 2) compute the effective capacity under different failure patterns, and 3) use these to compute compact routing tables under different failure patterns, since switches have limited routing table sizes. Our evaluations show that our approach can mask failures of up to 75% of switches in some cases without exceeding routing table limits, whereas competing techniques can sometimes lose half of a WAN router's capacity with a single failure.

Disaster and emergency response operations require rapid situational assessment of the affected area for timely and efficient rescue operations. A 3D map, collected after a disaster, can provide such awareness, but constructing this map quickly is a significant challenge. In this paper, we explore the design of a capability called QuickSketch that rapidly builds 3D representations of an unknown environment using crowdsourcing. QuickSketch employs multiple vehicles equipped with 3D sensors (stereo cameras) to explore different areas of an unknown territory and then combines 3D data from all the vehicles to build a single 3D map. QuickSketch annotates the 3D map with important landmarks and enables rapid contextualization of visual intelligence (photos) received from first responders and disaster victims to guarantee timely backup and rescue operations. Our evaluation results show that QuickSketch can stitch a 3D map for a large campus with sub-meter mapping accuracy under certain conditions, position landmarks an order of magnitude more accurately than other image matching techniques, and contextualize visual intelligence accurately.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

Deep neural networks (DNNs) are emerging as important drivers for GPU (Graphical Processing Unit) usage. Routinely, now, cloud offerings include GPU-capable VMs, and GPUs are used for training and testing DNNs. A popular way to run inference (or testing) tasks with DNNs is to use middleware called a serving system. Tensorflow-Serving (TF-Serving) is an example of a DNN serving system. In this paper, we consider the problem of carefully scheduling multiple concurrent DNNs in a serving system on a single GPU to achieve fairness or service differentiation objectives, a capability crucial to cloud-based TF-Serving offerings. In scheduling DNNs, we face two challenges: how to schedule, and switch between, different DNN jobs at low overhead; and, how to account for their usage. Our system, Olympian, extends TF-Serving to enable fair sharing of a GPU across multiple concurrent large DNNs at low overhead, a capability TF-Serving by itself is not able to achieve. Specifically, Olympian can run concurrent instances of several large DNN models such as Inception, ResNet, GoogLeNet, AlexNet and VGG, provide each with an equal share of the GPU, while interleaving them at timescales of 1-2 ms, and incurring an overhead of less than 2%. It achieves this by leveraging the predictability of GPU computations to profile GPU resource usage models offline, then using these to achieve low overhead switching between DNNs.

Accurate positioning in urban areas is important for personal navigation, geolocation apps, and ride-sharing. Smartphones localize themselves using GPS position estimates, and augment these with a variety of techniques including dead reckoning, map matching, and WiFi localization. However, GPS signals suffer significant impairment in urban canyons because of limited line-of-sight to satellites and signal reflections. In this paper, we focus on scalable and deployable techniques to reduce the impact of one specific impairment: reflected GPS signals from non-line-of-sight (NLOS) satellites. Specifically, we show how, using publicly available street-level imagery and off-the-shelf computer vision techniques, we can estimate the path inflation incurred by (the extra distance traveled by) a reflected signal from a satellite. Using these path inflation estimates we develop techniques to estimate the most likely actual position given a set of satellite readings at some position. Finally, we develop optimizations for fast position estimation on modern smartphones. Using extensive experiments in the downtown area of several large cities, we find that our techniques can reduce positioning error by up to 55% on average.

Autonomous vehicle prototypes today come with line-of-sight depth perception sensors like 3D cameras. These 3D sensors are used for improving vehicular safety in autonomous driving, but have fundamentally limited visibility due to occlusions, sensing range, and extreme weather and lighting conditions. To improve visibility and performance, not just for autonomous vehicles but for other Advanced Driving Assistance Systems (ADAS), we explore a capability called Augmented Vehicular Reality (AVR). AVR broadens the vehicle's visual horizon by enabling it to wirelessly share visual information with other nearby vehicles, but requires the design of novel relative positioning techniques, new perspective transformation methods, approaches to isolate and predict the motion of dynamic objects in order to hide latency, and adaptive transmission strategies to cope with wireless bandwidth variability. We show that AVR is feasible using off-the-shelf wireless technologies, and it can qualitatively change the decisions made by autonomous vehicle path planning algorithms. Our AVR prototype achieves positioning accuracies that are within a few percent of car lengths and lane widths, and is optimized to process frames at 30fps.

Most content providers are interested in providing good video delivery QoE for all users, not just on average. State-of-the-art ABR algorithms like BOLA and MPC rely on parameters that are sensitive to network conditions, so may perform poorly for some users and/or videos. In this paper, we propose a technique called Oboe to auto-tune these parameters to different network conditions. Oboe pre-computes, for a given ABR algorithm, the best possible parameters for different network conditions, then dynamically adapts the parameters at run-time for the current network conditions. Using testbed experiments, we show that Oboe significantly improves BOLA, MPC, and a commercially deployed ABR. Oboe also betters a recently proposed reinforcement learning based ABR, Pensieve, by 24% on average on a composite QoE metric, in part because it is able to better specialize ABR behavior across different network states.

Quality of information (QoI) provides a context-dependent measure of the utility that a network delivers to its users by incorporating non-traditional information attributes. Quickly and easily predicting performance and limitations of a network using QoI metrics is a valuable tool for network design. Even more useful is an understanding of how network components like topology, bandwidth, and protocols, impact these limitations. In this paper, we develop a QoI-based framework that can provide accurate estimates for limitations on network size and achievable QoI requirements, focusing on completeness and timeliness. We extend this framework to model competing flows and data loads as random variables to capture the stochastic nature of real networks. We show that our framework can provide a characterization of delays for satisfied queries to further analyze performance when some late arrivals are acceptable. Analysis shows that the large tradeoffs exist between network parameters, such as QoI requirements, topology, and network size. Simulation results also provide evidence that the developed framework can estimate network limits and delays with high accuracy. Finally, this paper also introduces scalably feasible QoI regions, which provide upper bounds on QoI requirements that can be supported for certain network applications.

This paper introduces a novel paradigm for resource management in distributed systems, called decision-driven execution. The paradigm is appropriate for mission-driven systems, where the goal is to enable faster, leaner, and more effective decision making. All resource consumption, in this paradigm, is tied to the needs of making decisions on alternative courses of action. A point of departure from traditional architectures lies in interfaces that allow applications to specify their underlying decision logic. This specification, in turn, allows the system to reason about most effective means to meet information needs of decisions, resulting in simultaneous optimization of decision accuracy, cost, and speed. The paper discusses the overall vision of decision-driven execution, outlining preliminary work and novel challenges.

Context awareness is crucial for ubiquitous computing, and position is an important aspect of context. In an ideal world, every stationary object or entity in the built environment would be associated with position, so that applications can have precise spatial context about the environment surrounding a human. In this paper, we take a step towards this ideal: by analyzing images from Google Street View that cover different perspectives of a given object and triangulating the location of the object, our system, ALPS, can discover and localize common landmarks at the scale of a city accurately and with high coverage. ALPS contains several novel techniques that help improve the accuracy, coverage, and scalability of localization. Evaluations of ALPS on many cities in the United States show that it can localize storefronts with a coverage higher than 90% and a median error of 5 meters.

The ever increasing quantity of user generated photos, nearly all compressed using JPEG, has created a growing storage burden on photo storage and sharing services. This creates the need for compression techniques that take JPEG compressed images as inputs. In this paper we propose two novel very low complexity codecs, ROMP and L-ROMP to recompress JPEG photos, achieving increased coding efficiency by making use of very large entropy coding tables. ROMP is a lossless JPEG recompression codec that achieves 15% average gains over JPEG, while L-ROMP is a lossy codec that can achieve 29% average compression gains over JPEG, by applying coefficient thresholding based on a perceptual criterion to a JPEG image before using the entropy coding of ROMP.

Large flows like videos consume significant bandwidth. Some ISPs actively manage these high volume flows with techniques like policing, which enforces a flow rate by dropping excess traffic. While the existence of policing is well known, our contribution is an Internet-wide study quantifying its prevalence and impact on video quality metrics. We developed a heuristic to identify policing from server-side traces and built a pipeline to deploy it at scale on traces from a large online content provider, collected from hundreds of servers worldwide. Using a dataset of 270 billion packets served to 28,400 client ASes, we find that, depending on region, up to 7% of lossy transfers are policed. Loss rates are on average six times higher when a trace is policed, and it impacts video playback quality. We show that alternatives to policing, like pacing and shaping, can achieve traffic management goals while avoiding the deleterious effects of policing.

Maintaining the highest levels of availability for content providers is challenging in the face of scale, network evolution and complexity. Little, however, is known about failures large content providers are susceptible to, and what mechanisms they employ to ensure high availability. From a detailed analysis of over 100 high-impact failure events in a global-scale content provider encompassing several data centers and two WANs, we quantify several dimensions of availability failures. We find that failures are evenly distributed across different network types and planes, but that a large number of failures happen when a management operation is in progress within the network. We discuss some of these failures in detail, and also describe our design principles for high availability motivated by these failures, including using defense in depth, maintaining consistency across planes, failing open on large failures, carefully preventing and avoiding failures, and assessing root cause quickly. Our findings suggest that, as networks become more complicated, failures lurk everywhere, and, counter-intuitively, continuous incremental evolution of the network can, when applied together with our design principles, result in a more robust network.

Developers deploying web applications in the cloud often need to determine how changes such as service tiers or runtime loads may affect user-perceived page load time. We devise and evaluate a systematic methodology for exploring such "what-if" questions at the time a web application is deployed. Given a website, a web request, and “whatif” scenario, with a hypothetical configuration and runtime condition, our methodology, embedded in a system called WebPerf, can estimate a distribution of end-to-end response times for the request under the “what-if” scenario. WebPerf makes three contributions: (1) automated instrumentation of web sites written with increasingly popular task parallel libraries, to capture causal call dependencies of various computation and asynchronous I/O calls; (2) an algorithm to use the call dependencies, together with online- and offlineprofiled models of various I/O calls to estimate a distribution of end-to-end latency of the request; and (3) an algorithm to optimize modeling errors by deciding how many measurements to take within a limited time. We have implemented WebPerf for Microsoft Azure. Our experiments with five real websites and seven scenarios show that the median error of WebPerf’s estimation is within 7% for all applications and scenarios.

As data centers grow larger and strive to provide tight performance and availability SLAs, their monitoring infrastructure must move from passive systems that provide aggregated inputs to human operators, to active systems that enable programmed control. In this paper, we propose Trumpet, an event monitoring system that leverages CPU resources and end-host programmability, to monitor every packet and report events at millisecond timescales. Trumpet users can express many *network-wide events*, and the system efficiently detects these events using *triggers* at end-hosts. Using careful design, Trumpet can evaluate triggers by inspecting every packet at full line rate even on future generations of NICs, scale to thousands of triggers per end-host while bounding packet processing delay to a few microseconds, and report events to a controller within 10 milliseconds, even in the presence of attacks. We demonstrate these properties using an implementation of Trumpet, and also show that it allows operators to describe new network events such as detecting correlated bursts and loss, identifying the root cause of transient congestion, and detecting short-term anomalies at the scale of a data center tenant.

Quality of Information (QoI) provides a context-dependent measure of the utility that a network delivers to its users by incorporating non-traditional information attributes. Quickly and easily predicting performance and limitations of a network using QoI metrics is a valuable tool for network design. Even more useful is an understanding of how network components like topology, bandwidth, protocols, etc. impact these limitations. In this paper, we develop a QoI-based framework that can provide this understanding of limitations and impact by modeling the various contributors to delay in the network, including channel rate and contention, competing traffic flows, and multi-hop propagation effects, and relating them to QoI requirements, especially completeness and timeliness. Analysis shows that large tradeoffs exist between network parameters, such as QoI requirements, topology, and network size. Simulation results also provide evidence that the developed framework can estimate network limits with high accuracy. Finally, this work also introduces scalably feasible QoI regions, which provide upper bounds on QoI requirements that can be supported for certain network applications.

Due to the lossy nature of wireless links, it is difficult to determine if packet losses are due to wireless-induced effects or from malicious discarding. Many prior efforts on detecting malicious packet drops rely on evidence collected via passive monitoring by neighbor nodes. However, they do not analyze the cause of packet losses. In this paper, we ask: 1) Given certain macroscopic parameters of the network (like traffic intensity and node density) what is the likelihood that evidence exists with respect to a transmission? 2) How can these parameters be used to perform a forensic analysis of the reason for the losses? Toward answering the above questions, we first build an analytical framework that computes the likelihood that evidence (we call this transmission evidence, or TE for short) exists with respect to transmissions, in terms of a set of network parameters. We validate our analytical framework via both simulations as well as real-world experiments on two different wireless testbeds. The analytical framework is then used as a basis for a protocol within a forensic analyzer to assess the cause of packet losses and determine the likelihood of forwarding misbehaviors. Through simulations, we find that our assessments are close to the ground truth in all examined cases, with an average deviation of 2.3% from the ground truth and a worst case deviation of 15.0%.

Software-defined networks can enable a variety of concurrent, dynamically instantiated, measurement tasks, that provide fine-grain visibility into network traffic. Recently, there have been many proposals for using sketches for network measurement. However, sketches in hardware switches use constrained resources such as SRAM memory, and the accuracy of measurement tasks is a function of the resources devoted to them on each switch. This paper presents SCREAM, a system for allocating resources to sketch-based measurement tasks that ensures a user-specified minimum accuracy. SCREAM estimates the instantaneous accuracy of tasks so as to dynamically adapt the allocated resources for each task. Thus, by finding the right amount of resources for each task on each switch and correctly merging sketches at the controller, SCREAM can multiplex resources among network-wide measurement tasks. Simulations with three measurement tasks (heavy hitter, hierarchical heavy hitter, and super source/destination detection) show that SCREAM can support more measurement tasks with higher accuracy than existing approaches.

Planned upgrades in cellular networks occur every day, may often need to be performed on weekdays, and can potentially degrade service for customers. In this paper, we explore the problem of tuning network configurations in order to mitigate any potential impact due to a planned upgrade which takes the base station off-air. The objective is to recover the loss in service performance or coverage which would have occurred without any modifications. To our knowledge, impact mitigation for planned base station downtimes has not been explored before in the literature. The primary contribution of this work is a proactive approach based on a predictive model that uses operational data of user density distributions and path loss (rather than idealized analytical models of these) to quickly estimate the best power and tilt configuration of neighboring base stations that enables high recovery. A secondary contribution is an approach to minimize synchronized handovers. These ideas, embodied in a capability called Magus, enables us to recover up to 76% of the potential performance loss due to planned upgrades in some cases for a large US mobile network, and this recovery varies as a function of base station density. Moreover, Magus is able to reduce synchronized handovers by a factor of 8.

We develop data retrieval algorithms for crowd-sensing applications that reduce the underlying network bandwidth consumption or any additive cost metric by exploiting logical dependencies among data items, while maintaining the level of service to the client applications. Crowd sensing applications refer to those where local measurements are performed by humans or devices in their possession for subsequent aggregation and sharing purposes. In this paper, we focus on resource-limited crowd sensing, such as disaster response and recovery scenarios. The key challenge in those scenarios is to cope with resource constraints. Unlike the traditional application design, where measurements are sent to a central aggregator, in resource limited scenarios, data will typically reside at the source until requested to prevent needless transmission. Many applications exhibit dependencies among data items. For example, parts of a city might tend to get flooded together because of a correlated low elevation, and some roads might become useless for evacuation if a bridge they lead to fails. Such dependencies can be encoded as logic expressions that obviate retrieval of some data items based on values of others. Our algorithm takes logical data dependencies into consideration such that application queries are answered at the central aggregation node, while network bandwidth usage is minimized. The algorithms consider multiple concurrent queries and accommodate retrieval latency constraints. Simulation results show that our algorithm outperforms several baselines by significant margins, maintaining the level of service perceived by applications in the presence of resource-constraints.

The Internet suffers from well-known performance, reliability, and security problems. However, proposed improvements have seen little adoption due to the difficulties of Internet-wide deployment. We observe that, instead of trying to solve these problems in the general case, it may be possible to make substantial progress by focusing on solutions tailored to the paths between popular content providers and their clients, which carry a large share of Internet traffic.

To reduce page load times and bandwidth usage for mobile web browsing, middleboxes that compress page content are commonly used today. Unfortunately, this can hurt performance in many cases; via an extensive measurement study, we show that using middleboxes to facilitate compression results in up to 28% degradation in page load times when the client enjoys excellent wireless link conditions. We find that benefits from compression are primarily realized under bad network conditions. Guided by our study, we design and implement FlexiWeb, a framework that determines both when to use a middlebox and how to use it, based on the client's network conditions. First, FlexiWeb selectively fetches objects on a web page either directly from the source or via a middlebox, rather than fetching all objects via the middlebox. Second, instead of simply performing lossless compression of all content, FlexiWeb performs network-aware compression of images by selecting from among a range of content transformations. We implement and evaluate a prototype of FlexiWeb using Google's open source Chromium mobile browser and our implementation of a modified version of Google's open source compression proxy. Our extensive experiments show that, across a range of scenarios, FlexiWeb reduces page load times for mobile clients by 35-42% compared to the status quo.

The proliferation of mobile apps is due in part to the advertising ecosystem which enables developers to earn revenue while providing free apps. Ad-supported apps can be developed rapidly with the availability of ad libraries. However, today?s ad libraries essentially have access to the same resources as the parent app, and this has caused signi?cant privacy concerns. In this paper, we explore ef?cient methods to de-escalate privileges for ad libraries where the resource access privileges for ad libraries can be different from that of the app logic. Our system, PEDAL, contains a novel machine classi?er for detecting ad libraries even in the presence of obfuscated code, and techniques for automatically instrumenting bytecode to effect privilege de-escalation even in the presence of privilege inheritance. We evaluate PEDAL on a large set of apps from the Google Play store and demonstrate that it has a 98% accuracy in detecting ad libraries and imposes less than 1% runtime overhead on apps.

The paper describes a novel algorithm for timely sensor data retrieval in resource-poor environments under freshness constraints. Consider a civil unrest, national security, or disaster management scenario, where a dynamic situation evolves and a decision-maker must decide on a course of action in view of latest data. Since the situation changes, so is the best course of action. The scenario offers two interesting constraints. First, one should be able to successfully compute the course of action within some appropriate time window, which we call the decision deadline. Second, at the time the course of action is computed, the data it is based on must be fresh (i.e., within some corresponding validity interval). We call it the freshness constraint. These constraints create an interesting novel problem of timely data retrieval. We address this problem in resource-scarce environments, where network resource limitations require that data objects (e.g., pictures and other sensor measurements pertinent to the decision) generally remain at the sources. Hence, one must decide on (i) which objects to retrieve and (ii) in what order, such that the cost of deciding on a valid course of action is minimized while meeting data freshness and decision deadline constraints. Such an algorithm is reported in this paper. The algorithm is shown in simulation to reduce the cost of data retrieval compared to a host of baselines that consider time or resource constraints. It is applied in the context of minimizing cost of finding unobstructed routes between specified locations in a disaster zone by retrieving data on the health of individual route segments.

Precise positioning of an automobile to within lane-level precision can enable better navigation and context-awareness. However, GPS by itself cannot provide such precision in obstructed urban environments. In this paper, we present a system called CARLOC for lane-level positioning of automobiles. CARLOC uses three key ideas in concert to improve positioning accuracy: it uses digital maps to match the vehicle to known road segments; it uses vehicular sensors to obtain odometry and bearing information; and it uses crowd-sourced location of estimates of roadway landmarks that can be detected by sensors available in modern vehicles. CARLOC unifies these ideas in a probabilistic position estimation framework, widely used in robotics, called the sequential Monte Carlo method. Through extensive experiments on a real vehicle, we show that CARLOC achieves sub-meter positioning accuracy in an obstructed urban setting, an order-of-magnitude improvement over a high-end GPS device.

Precise positioning of an automobile to within lane-level precision can enable better navigation and context-awareness. However, GPS by itself cannot provide such precision in obstructed urban environments. In this paper, we present a system called CARLOC for lane-level positioning of automobiles. CARLOC uses three key ideas in concert to improve positioning accuracy: it uses digital maps to match the vehicle to known road segments; it uses vehicular sensors to obtain odometry and bearing information; and it uses crowd-sourced location of estimates of roadway landmarks that can be detected by sensors available in modern vehicles. CARLOC unifies these ideas in a probabilistic position estimation framework, widely used in robotics, called the sequential Monte Carlo method. Through extensive experiments on a real vehicle, we show that CARLOC achieves sub-meter positioning accuracy in an obstructed urban setting, an order-of-magnitude improvement over a high-end GPS device.

Traditional routing metrics designed for wireless networks are application-agnostic. In this paper, we consider a wireless network where the application flows consist of video traffic. From a user perspective, reducing the level of video distortion is critical. We ask the question “Should the routing policies change if the end-to-end video distortion is to be minimized?” Popular link-quality-based routing metrics (such as ETX) do not account for dependence (in terms of congestion) across the links of a path; as a result, they can cause video flows to converge onto a few paths and, thus, cause high video distortion. To account for the evolution of the video frame loss process, we construct an analytical framework to, first, understand and, second, assess the impact of the wireless network on video distortion. The framework allows us to formulate a routing policy for minimizing distortion, based on which we design a protocol for routing video traffic. We find via simulations and testbed experiments that our protocol is efficient in reducing video distortion and minimizing the user experience degradation.

This paper complements the large body of social sensing literature by developing means for augmenting sensing data with inference results that "fill-in" missing pieces. Unlike trend-extrapolation methods, we focus on prediction in disaster scenarios where disruptive trend changes occur. A set of prediction heuristics (and a standard trend extrapolation algorithm) are compared that use either predominantly-spatial or predominantly-temporal correlations for data extrapolation purposes. The evaluation shows that none of them do well consistently. This is because monitored system state, in the aftermath of disasters, alternates between periods of relative calm and periods of disruptive change (e.g., aftershocks). A good prediction algorithm, therefore, needs to intelligently combine time-based data extrapolation during periods of calm, and spatial data extrapolation during periods of change. The paper develops such an algorithm. The algorithm is tested using data collected during the New York City crisis in the aftermath of Hurricane Sandy in November 2012. Results show that consistently good predictions are achieved. The work is unique in addressing the bi-modal nature of damage propagation in complex systems subjected to stress, and offers a simple solution to the problem.

This paper describes the exploitation of hierarchical data names to achieve information-utility maximizing data collection in social sensing applications. We describe a novel transport abstraction, called the information funnel. It encapsulates a data collection protocol for social sensing that maximizes a measure of delivered information utility, that is the minimized data redundancy, by diversifying the data objects to be collected. The abstraction leverages named-data networking, a communication paradigm where data objects are named instead of hosts. We argue that this paradigm is especially suited for utility-maximizing transport in resource constrained environments, because hierarchical data names give rise to a notion of distance between named objects that is a function of only the topology of the name tree. This distance, in turn, can expose similarities between named objects that can be leveraged for minimizing redundancy among objects transmitted over bottlenecks, thereby maximizing their aggregate utility. With a proper hierarchical name space design, our protocol prioritizes transmission of data objects over bottlenecks to maximize information utility, with very weak assumptions on the utility function. This prioritization is achieved merely by comparing data name prefixes, without knowing application-level name semantics, which makes it generalizable across a wide range of applications. Evaluation results show that the information funnel improves the utility of the collected data objects compared to other lossy protocols.

Mobile app ecosystems have experienced tremendous growth in the last six years. This has triggered research on dynamic analysis of performance, security, and correctness properties of the mobile apps in the ecosystem. Exploration of app execution using automated UI actions has emerged as an important tool for this research. However, existing research has largely developed analysis-specific UI automation techniques, wherein the logic for exploring app execution is intertwined with the logic for analyzing app properties. PUMA is a programmable framework that separates these two concerns. It contains a generic UI automation capability (often called a Monkey) that exposes high-level events for which users can define handlers. These handlers can flexibly direct the Monkey's exploration, and also specify app instrumentation for collecting dynamic state information or for triggering changes in the environment during app execution. Targeted towards operators of app marketplaces, PUMA incorporates mechanisms for scaling dynamic analysis to thousands of apps. We demonstrate the capabilities of PUMA by analyzing seven distinct performance, security, and correctness properties for 3,600 apps downloaded from the Google Play store.

Automotive apps can improve efficiency, safety, comfort, and longevity of vehicular use. These apps achieve their goals by continuously monitoring sensors in a vehicle, and combining them with information from cloud databases in order to detect events that are used to trigger actions (e.g., alerting a driver, turning on fog lights, screening calls). However, modern vehicles have several hundred sensors that describe the low level dynamics of vehicular subsystems, these sensors can be combined in complex ways together with cloud information. Moreover, these sensor processing algorithms may incur significant costs in acquiring sensor and cloud information. In this paper, we propose a programming framework called CARLOG to simplify the task of programming these event detection algorithms. CARLOG uses Datalog to express sensor processing algorithms, but incorporates novel query optimization methods that can be used to minimize bandwidth usage, energy or latency, without sacrificing correctness of query execution. Experimental results on a prototype show that CARLOG can reduce latency by nearly two orders of magnitude relative to an unoptimized Datalog engine.

No abstract available.

Software-defined networks can enable a variety of concurrent, dynamically instantiated, measurement tasks, that provide fine-grain visibility into network traffic. Recently, there have been many proposals to configure TCAM counters in hardware switches to monitor traffic. However, the TCAM memory at switches is fundamentally limited and the accuracy of the measurement tasks is a function of the resources devoted to them on each switch. This paper describes an adaptive measurement framework, called DREAM, that dynamically adjusts the resources devoted to each measurement task, while ensuring a user-specified level of accuracy. Since the trade-off between resource usage and accuracy can depend upon the type of tasks, their parameters, and traffic characteristics, DREAM does not assume an a priori characterization of this trade-off, but instead dynamically searches for a resource allocation that is sufficient to achieve a desired level of accuracy. A prototype implementation and simulations with three network-wide measurement tasks (heavy hitter, hierarchical heavy hitter and change detection) and diverse traffic show that DREAM can support more concurrent tasks with higher accuracy than several other alternatives.

Location-Based Mobile Service (LBMS) is one of the most popular smartphone services. LBMS enables people to more easily connect with each other and analyze the aspects of their lives. However, sharing location data can leak people's privacy. We present PDVLoc, a controlled location data-sharing framework based on selectively sharing data through a Personal Data Vault (PDV). A PDV is a privacy architecture in which individuals retain ownership of their data. Data are routinely filtered before being shared with content-service providers, and users or data custodian services can participate in making controlled data-sharing decisions. Introducing PDVLoc gives users flexible and granular access control over their location data. We have implemented a prototype of PDVLoc and evaluated it using real location-sharing social networking applications, Google Latitude and Foursquare. Our user study of 19 participants over 20 days shows that most users find that PDVLoc is useful to manage and control their location data, and are willing to continue using PDVLoc.

In social swarming applications, participants equipped with 3G and WiFi-capable smartphones are tasked to provide reports (possibly voluminous ones that include full-motion video) about their immediate environment to a central coordinator. In this paper, we consider the problem of timely delivery of these reports: Each report has an associated deadline, and the goal of the system is to retrieve as many reports as possible (or retrieve the most valuable reports), while satisfying each report's deadline. Reporters can use their cellular interface to upload their reports but can also ask neighbors (using their faster WiFi interface) to help upload parts of their reports. Under an assumption that WiFi transmission delays are negligible, we first show that there exists a polynomial time optimal solution using an earliest-deadline-first (EDF) strategy for achieving the goals described above. In practice, WiFi delays are not negligible; in this case, it turns out that the scheduling problem is strongly NP-hard. We formulate two heuristic algorithms, and show, through simulations and experiments on an Android-based implementation, that these heuristics perform 2-4× better than without peer-assistance, and within 60% of an upper-bound on the optimal.

Process variations are growing with technology scaling towards nano-scale. This brings new challenges to the design of memory modules, which are often the first circuits to be fabricated using a new technology and usually designed with critical timing. We observed that several delay faults, which are dependent on address transitions, may escape traditional march tests. This paper presents a new march test WT that targets such delay faults. Through Monte Carlo simulations and analytical studies on SRAM designs using an industrial 65nm process, we have demonstrated that WT provides a faulty-chip-coverage that is close to 100%. Most importantly, this is the first march test with test length that targets address-dependent delay faults and hence the first delay test which can be used in practice.

As process variations grow with technology scaling, failure rates increase and are predicted to be so high as to render devices unusable for computing domain. In order to continue to benefit from scaling, three dimensions can be explored: increasing operational margins, testing, and the resilience of applications. The solutions in each dimension bring out different trade-offs in yield, failure rate, test cost, and performance. We use a ternary content-addressable memory (TCAM) as a case study to better understand these trade-offs. We develop two new delay tests for TCAMs, and a new method to estimate yield, failure rate, test cost, and performance of TCAM under process variations when various tests are used. Our results show that with little test overhead and negligible yield loss, our new tests can significantly decrease the failure rates of TCAMs shipped to customers.

Computing-as-a-service has been evolving steadily. Today, private clouds (e.g., Google's internal shared computing cluster) as well as public clouds (e.g., Amazon's web services (AWS), Microsoft's Azure) provide computing abstractions at various levels: bare virtual machines, specialized languages and runtimes (e.g., for massively-parallel data processing---MapReduce, Dryad), web services. For example, Amazon offers bare virtual machines as well as MapReduce clusters.

Video transfers using smartphones are becoming increasingly popular. To prevent the interception of content from eavesdroppers, video flows must be encrypted. However, encryption results in a cost in terms of processing delays and energy consumed on the user's device. We argue that encrypting only certain parts of the flow can create sufficiently high distortion at an eavesdropper preserving content confidentiality as a result. By selective encryption, one can reduce delay and the battery consumption on the mobile device. We develop a mathematical framework that captures the impact of the encryption process on the delay experienced by a flow, and the distortion seen by an eavesdropper. This provides a quick and efficient way of determining the right parts of a video flow that must be encrypted to preserve confidentiality, while limiting performance penalties. In practice, it can aid a user in choosing the right level of encryption. We validate our model via extensive experiments with different encryption policies using Android smartphones. We observe that by selectively encrypting parts of a video flow one can preserve the confidentiality while reducing delay by as much as 75% and the energy consumption by as much as 92%.

To address the pressing need to provide transparency into the online targeted advertising ecosystem, we present AdReveal, a practical measurement and analysis framework, that provides a first look at the prevalence of different ad targeting mechanisms. We design and implement a browser based tool that provides detailed measurements of online display ads, and develop analysis techniques to characterize the contextual, behavioral and re-marketing based targeting mechanisms used by advertisers. Our analysis is based on a large dataset consisting of measurements from 103K webpages and 139K display ads. Our results show that advertisers frequently target users based on their online interests; almost half of the ad categories employ behavioral targeting. Ads related to Insurance, Real Estate and Travel and Tourism make extensive use of behavioral targeting. Furthermore, up to 65% of ad categories received by users are behaviorally targeted. Finally, our analysis of re-marketing shows that it is adopted by a wide range of websites and the most commonly targeted re-marketing based ads are from the Travel and Tourism and Shopping categories.

Transmission Evidence (TE for short) refers to a historic trail of the packet transmissions in the network. TE is collected and maintained in a distributed manner by the nodes in the network and can be queried on demand by a network forensics system to trace past events. The latter can facilitate crucial applications such as identifying malicious or malfunctioning nodes. Recently, we developed an analytical framework towards computing the likelihood of TE availability in wireless networks. Our prior efforts [1] brought to light the impact of the network's operational parameters (such as transmission rate and packet length) on the availability of TE. However, provisioning for TE could impact the network performance in terms of throughput and/or delay. Our objective in this work is to capture and quantify the trade-offs between provisioning transmission evidence and achieving high performance in wireless networks. In particular, we investigate the network performance hit, under the constraint of TE availability guarantees. Our results indicate that the performance remains unaffected up to a certain TE requirement. Beyond this, the throughput could degrade and the delay could increase by as much as 30%. To the best of our knowledge, this is the first study of its kind.

Optimizing the energy efficiency of mobile applications can greatly increase user satisfaction. However, developers lack viable techniques for estimating the energy consumption of their applications. This paper proposes a new approach that is both lightweight in terms of its developer requirements and provides fine-grained estimates of energy consumption at the code level. It achieves this using a novel combination of program analysis and per-instruction energy modeling. In evaluation, our approach is able to estimate energy consumption to within 10% of the ground truth for a set of mobile applications from the Google Play store. Additionally, it provides useful and meaningful feedback to developers that helps them to understand application energy consumption behavior.

Modern content-distribution networks both provide bulk content and act as "serving infrastructure" for web services in order to reduce user-perceived latency. Serving infrastructures such as Google's are now critical to the online economy, making it imperative to understand their size, geographic distribution, and growth strategies. To this end, we develop techniques that enumerate IP addresses of servers in these infrastructures, find their geographic location, and identify the association between clients and clusters of servers. While general techniques for server enumeration and geolocation can exhibit large error, our techniques exploit the design and mechanisms of serving infrastructure to improve accuracy. We use the EDNS-client-subnet DNS extension to measure which clients a service maps to which of its serving sites. We devise a novel technique that uses this mapping to geolocate servers by combining noisy information about client locations with speed-of-light constraints. We demonstrate that this technique substantially improves geolocation accuracy relative to existing approaches. We also cluster server IP addresses into physical sites by measuring RTTs and adapting the cluster thresholds dynamically. Google's serving infrastructure has grown dramatically in the ten months, and we use our methods to chart its growth and understand its content serving strategy. We find that the number of Google serving sites has increased more than sevenfold, and most of the growth has occurred by placing servers in large and small ISPs across the world, not by expanding Google's backbone.

IP anycast is a central part of production DNS. While prior work has explored proximity, affinity and load balancing for some anycast services, there has been little attention to third-party discovery and enumeration of components of an anycast service. Enumeration can reveal abnormal service configurations, benign masquerading or hostile hijacking of anycast services, and help characterize anycast deployment. In this paper, we discuss two methods to identify and characterize anycast nodes. The first uses an existing anycast diagnosis method based on CHAOS-class DNS records but augments it with traceroute to resolve ambiguities. The second proposes Internet-class DNS records which permit accurate discovery through the use of existing recursive DNS infrastructure. We validate these two methods against three widely-used anycast DNS services, using a very large number (60k and 300k) of vantage points, and show that they can provide excellent precision and recall. Finally, we use these methods to evaluate anycast deployments in top-level domains (TLDs), and find one case where a third-party operates a server masquerading as a root DNS anycast node as well as a noticeable proportion of unusual DNS proxies. We also show that, across all TLDs, up to 72% use anycast.

The end-user experience in viewing a video depends on the distortion; however, also of importance is the delay experienced by the packets of the video flow since it impacts the timeliness of the information contained and the playback rate at the receiver. Unfortunately, these performance metrics are in conflict with each other in a wireless network. Packet losses can be minimized by perfectly avoiding interference by separating transmissions in time or frequency; however, this decreases the rate at which transmissions occur, and this increases delay. Relaxing the requirement for interference avoidance can lead to packet losses and thus increase distortion, but can decrease the delay for those packets that are delivered. In this paper, we investigate this trade-off between distortion and delay for video. To understand the trade-off between video quality and packet delay, we develop an analytical framework that accounts for characteristics of the network (e.g. interference, channel variations) and the video content (motion level), assuming as a basis, a simple channel access policy that provides flexibility in managing the interference in the network. We validate our model via extensive simulations. Surprisingly, we find that the trade-off depends on the specific features of the video flow: it is better to trade-off high delay for low distortion with fast motion video, but not with slow motion video. Specifically, for an increase in PSNR (a metric that quantifies distortion) from 20 to 25 dB, the penalty in terms of the increase in mean delay with fast motion video is 91 times that with slow motion video. Our simulation results further quantify the trade-offs in various scenarios.

Motivated by an availability gap for visual media, where images and videos are uploaded from mobile devices well after they are generated, we explore the selective, timely retrieval of media content from a collection of mobile devices. We envision this capability being driven by similarity-based queries posed to a cloud search front-end, which in turn dynamically retrieves media objects from mobile devices that best match the respective queries within a given time limit. Building upon a crowd-sensing framework, we have designed and implemented a system called MediaScope that provides this capability. MediaScope is an extensible framework that supports nearest-neighbor and other geometric queries on the feature space (e.g. clusters, spanners), and contains novel retrieval algorithms that attempt to maximize the retrieval of relevant information. From experiments on a prototype, MediaScope is shown to achieve near-optimal query completeness and low to moderate overhead on mobile devices.

Motivated by an availability gap for visual media, where images and videos are uploaded from mobile devices well after they are generated, we explore the selective, timely retrieval of media content from a collection of mobile devices.

The popularity of mobile apps continues to grow as developers take advantage of the sensors and data available on mobile devices. However, the increased functionality comes with a higher energy cost, which can cause a problem for users on battery constrained mobile devices. To improve the energy consumption of mobile apps, developers need detailed information about the energy consumption of their applications. Existing techniques have drawbacks that limit their usefulness or provide information at too high of a level of granularity, such as components or methods. Our approach is able to calculate source line level energy consumption information. It does this by combining hardware-based power measurements with program analysis and statistical modeling. Our empirical evaluation of the approach shows that it is fast and accurate.

Mobile app ecosystems have experienced tremendous growth in the last five years. As researchers and developers turn their attention to understanding the ecosystem and its different apps, instrumentation of mobile apps is a much needed emerging capability. In this paper, we explore a selective instrumentation capability that allows users to express instrumentation specifications at a high level of abstraction; these specifications are then used to automatically insert instrumentation into binaries. The challenge in our work is to develop expressive abstractions for instrumentation that can also be implemented efficiently. Designed using requirements derived from recent research that has used instrumented apps, our selective instrumentation framework, SIF, contains abstractions that allow users to compactly express precisely which parts of the app need to be instrumented. It also contains a novel path inspection capability, and provides users feedback on the approximate overhead of the instrumentation specification. Using experiments on our SIF implementation for Android, we show that SIF can be used to compactly (in 20-30 lines of code in most cases) specify instrumentation tasks previously reported in the literature. SIF's overhead is under 2% in most cases, and its instrumentation overhead feedback is within 15% in many cases. As such, we expect that SIF can accelerate studies of the mobile app ecosystem.

In this demo, a learning system, called Metis, is presented that extrapolates missing pieces in participatory sensing data. The work addresses the challenge of incomplete coverage in participatory sensing applications, where lack of complete control over participant mobility and sensing patterns may create coverage gaps in space and in time. Metis learns the underlying spatiotemporal patterns of the measured phenomenon from available incomplete observations, and uses these patterns to infer missing data. We describe the overall system design and demonstrate the system using data collected during the New York City gas crisis in the aftermath of Hurricane Sandy.

To serve users quickly, Web service providers build infrastructure closer to clients and use multi-stage transport connections. Although these changes reduce client-perceived round-trip times, TCP's current mechanisms fundamentally limit latency improvements. We performed a measurement study of a large Web service provider and found that, while connections with no loss complete close to the ideal latency of one round-trip time, TCP's timeout-driven recovery causes transfers with loss to take five times longer on average.

Our editorial board continues to perform outstanding service to the mobile computing community, and for this we are very grateful. The board has evolved this year, and we take this opportunity to welcome several new Associate Editors: Prithwish Basu, Carla Fabiana-Chiasserini, Ahmed Helmy, Vana Kalogeraki, Richard J. La, Xiang-Yang Li, Cecilia Mascolo, Tommaso Melodia, Guevara Noubir, Andrea Richa, Lakshminarayanan Subramanian, Karthikeyan Sundaresan, Xinbing Wang, Edmund Yeh, Yanyong Zhang, and Lin Zhong. Biographies are provided. They collectively strengthen our expertise in disruption-tolerant networking, vehicular networks, mobile computing systems, wireless security, mobile social networks, wireless network optimization, game theory, cognitive radios, and information theory. We are excited to have them on board and thank them for agreeing to serve. Finally, we'd also like to acknowledge several Associate Editors whose terms recently expired: Tajana Simunic-Rosing, Sajal Das, Paolo Santi, Terry Todd, Wade Trappe, Nalini Venkatasubramanian, Mary Ann Ingram, Ekram Hossain, Chiara Petrioli, Alex Snoeren, Prasant Mohapatra, and Yunhao Liu. This very distinguished group of researchers has contributed greatly to increasing the journal's quality and reputation, and they will be missed! We wish them the best in their future endeavors.

Two constituencies form the backbone of a journal and act as stewards of its quality. One is the Editorial Board, whose judgments on the quality of manuscripts shape a journal signifi cantly and set the tone for its direction. Equally important, but perhaps not as externally visible, is the body of external reviewers who are called upon to review manuscripts. The IEEE Transactions on Mobile Computing (TMC) is very fortunate to have more than 1,200 dedicated reviewers whose service to the journal is one of the major factors that contributes to TMC's standing as an academic publication. These reviewers collectively completed nearly 1,800 reviews in 2012 alone, and their thoroughness in reviewing manuscripts has been exemplary. The IEEE has recently initiated a Reviewer Appreciation Program for its publications to highlight reviewers who have gone beyond the call of duty, both in contributing signifi cant amounts of their time to reviewing manuscripts for TMC and also in the quality of their reviews. It is our great pleasure to recognize the individuals listed as distinguished reviewers for TMC for the year 2012.

O N behalf of our Associate Editors, the TMC Steering Committee, and the TMC

In social swarming applications, participants equipped with 3G and WiFi-capable smart phones are tasked to provide reports (possibly voluminous ones that include full-motion video) about their immediate environment to a central coordinator. In this paper, we consider the problem of timely delivery of these reports: each report has an associated deadline and the goal of the system is to retrieve as many reports as possible (or retrieve the most valuable reports), while satisfying each report's deadline. Reporters can use their cellular interface to upload their reports, but can also ask neighbors (using their faster WiFi interface) to help upload parts of their reports. Under an assumption that WiFi transmission delays are negligible, we first show that there exists a polynomial time optimal solution using an earliest-deadline-first (EDF) strategy for achieving the goals described above. In practice, WiFi delays are not negligible: in this case, it turns out that the scheduling problem is strongly NP-hard. We formulate two heuristic algorithms, and show, through simulations with real-world measurements, that these heuristics perform 2-4× better than without peer-assistance, and within 60% of an upper-bound on the optimal.

Networked systems have benefited from unprecedented growth in hardware capabilities, but, as we move closer to the end of the Moore's law era, future networked systems are likely to be more constrained by hardware capabilities than they have been in the past. We take the position that the networking community should, in response to this development, proactively and systematically develop networking roadmaps, which attempt to predict how trends in hardware capabilities will impact networked systems. In this paper, we discuss a possible methodology for developing networking roadmaps, and present two case studies that illustrate the methodology and reveal how increasing hardware unreliability can affect the performance of routing and transport protocols.

Due to the lossy nature of wireless links, it is difficult to determine if packet losses are due to wireless-induced effects or from malicious discarding. Many prior efforts on detecting malicious packet drops rely on evidence collected via passive monitoring by neighbor nodes; however, they do not analyze the cause of packet losses. In this paper, we ask: (a) Given certain macroscopic parameters of the network (like traffic intensity and node density) what is the likelihood that evidence exists with respect to a transmission? and, (b) How can these parameters be used to perform a forensic analysis of the reason for the losses? Towards answering the above questions, we first build an analytical framework that computes the likelihood that evidence (we call this transmission evidence or TE for short) exists with respect to transmissions, in terms of a set of network parameters. We validate our analytical framework via both simulations as well as real-world experiments on two different wireless testbeds. The analytical framework is then used as a basis for a protocol within a forensic analyzer to assess the cause of packet losses and determine the likelihood of forwarding misbehaviors. Through simulations, we find that our assessments are close to the ground truth in all examined cases, with an average deviation of 2.3% from the ground truth and a worst case deviation of 15.0%.

Traditional routing metrics designed for wireless networks are application agnostic. In this paper, we consider a wireless network where the application flows consist of video traffic. From a user-perspective, reducing the level of video distortion is critical. We ask the question “Should the routing policies change if the end-to-end video distortion is to be minimized?” Popular link-quality based routing metrics (such as ETX) do not account for dependence (in terms of congestion) across the links of a path; as a result, they can cause video flows to converge onto a few paths and thus, cause high video distortion. To account for the evolution of the video frame loss process we construct an analytical framework to first, understand and second, assess the impact of the wireless network on video distortion. The framework allows us to formulate a routing policy for minimizing distortion, based on which we design a protocol for routing video traffic. We find via simulations and testbed experiments that our protocol is efficient in reducing video distortion and minimizing the user experience degradation. Specifically, our protocol reduces the distortion by 20% over traditional methods, which significantly improves the video quality perceived by a user.

Initially, packet forwarding in the Internet was destination-based -- that is, a router would forward all packets with the same destination address to the same next hop. In this paper, we use active probing methods to quantify and characterize deviations from destination-based forwarding in today's Internet. From over a quarter million probes, we analyze the forwarding behavior of almost 40,000 intermediate routers. We find that, for 29% of the targeted routers, the router forwards traffic going to a single destination via different next hops, and 1.3% of the routers even select next hops in different ASes. Load balancers are unlikely to explain these AS-level variations, and in fact we uncover causes including routers inside MPLS tunnels that otherwise employ default routes. We also find that these violations can significantly affect the results of measurement tools that rely on destination-based forwarding, and we discuss some ideas for making these tools more robust against these violations.

This demonstration illustrates a service for collection and delivery of images, in participatory camera networks, to maximize coverage while removing outliers (i.e., irrelevant images). Images, such as those taken by smart-phone users, represent an important and growing modality in social sensing applications. They can be used, for instance, to document occurrences of interest in participatory sensing campaigns, such as instances of graffiti on campus or invasive species in a park. In applications with a significant number of participants, the number of images collected may be very large. A key problem becomes one of data triage to reduce the number of images delivered to a manageable count, without missing important ones. In prior work, the authors presented a service, called PhotoNet [2], that reduces redundancy among delivered images by maximizing diversity. The current work significantly extends our previous effort by recognizing that diversity maximization often leads to selection of outliers; images that are visually different but not necessarily relevant, which in fact reduces the quality of the delivered image pool. We demonstrate a new prioritization technique that maximizes diversity among delivered pictures, while also reducing outliers.

The ubiquity of smartphones and their on-board sensing capabilities motivates crowd-sensing, a capability that harnesses the power of crowds to collect sensor data from a large number of mobile phone users. Unlike previous work on wireless sensing, crowd-sensing poses several novel requirements: support for humans-in-the-loop to trigger sensing actions or review results, the need for incentives, as well as privacy and security. Beyond existing crowd-sourcing systems, crowd-sensing exploits sensing and processing capabilities of mobile devices. In this paper, we design and implement Medusa, a novel programming framework for crowd-sensing that satisfies these requirements. Medusa provides high-level abstractions for specifying the steps required to complete a crowd-sensing task, and employs a distributed runtime system that coordinates the execution of these tasks between smartphones and a cluster on the cloud. We have implemented ten crowd-sensing tasks on a prototype of Medusa. We find that Medusa task descriptions are two orders of magnitude smaller than standalone systems required to implement those crowd-sensing tasks, and the runtime has low overhead and is robust to dynamics and resource attacks.

The ubiquity of smartphones and their on-board sensing capabilities motivates crowd-sensing, a capability that harnesses the power of crowds to collect sensor data from a large number of mobile phone users. Unlike previous work on wireless sensing, crowd-sensing poses several novel requirements: support for humans-in-the-loop to trigger sensing actions or review results, the need for incentives, as well as privacy and security. Beyond existing crowd-sourcing systems, crowd-sensing exploits sensing and processing capabilities of mobile devices. In this paper, we design and implement Medusa, a novel programming framework for crowd-sensing that satisfies these requirements. Medusa provides high-level abstractions for specifying the steps required to complete a crowd-sensing task, and employs a distributed runtime system that coordinates the execution of these tasks between smartphones and a cluster on the cloud. We have implemented ten crowd-sensing tasks on a prototype of Medusa. We find that Medusa task descriptions are two orders of magnitude smaller than standalone systems required to implement those crowd-sensing tasks, and the runtime has low overhead and is robust to dynamics and resource attacks.

In this paper, we consider the design of a system in which Internet-connected mobile users contribute sensor data as training samples, and collaborate on building a model for classification tasks such as activity or context recognition. Constructing the model can naturally be performed by a service running in the cloud, but users may be more inclined to contribute training samples if the privacy of these data could be ensured. Thus, in this paper, we focus on privacy-preserving collaborative learning for the mobile setting, which addresses several competing challenges not previously considered in the literature: supporting complex classification methods like support vector machines, respecting mobile computing and communication constraints, and enabling user-determined privacy levels. Our approach, Pickle, ensures classification accuracy even in the presence of significantly perturbed training samples, is robust to methods that attempt to infer the original data or poison the model, and imposes minimal costs. We validate these claims using a user study, many real-world datasets and two different implementations of Pickle.

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications: search and rescue, coordinated fire-fighting, and the DARPA balloon hunt challenge. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event. We first propose a model, based on common notions of believability, about the credibility of information. We then cast the problem posed above as a discrete optimization problem, prove hardness results, introduce optimal centralized solutions, and design an approximate solution amenable to decentralized implementation whose performance is about 20 percent off, on average, from the optimal (on real-world data sets derived from Google News) while being three orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions. To our knowledge, we are the first to propose and explore the problem of extracting credible information from a network of smartphones.

Increasingly, mobile devices equipped with 802.11n interfaces are being used for a wide variety of applications including bandwidth-intensive HD video streaming. Recent work has shown that 802.11n interfaces are power-hungry, so energy management is an important challenge. 802.11n implementations have additional power states relative to earlier generations of 802.11 technology, so energy management challenges for 802.11n are qualitatively different compared to that faced by prior work. In this paper, we describe the design and implementation of Snooze, an energy management technique for 802.11n which uses two novel and inter-dependent mechanisms: client micro-sleeps and antenna configuration management. In Snooze, the APmonitors traffic on the WLAN and directs client sleep times and durations as well as antenna configurations, without significantly affecting throughput or delay. Snooze achieves 30~85% energy-savings over CAM across workloads ranging from VoIP and video streaming to file downloads and chats.

In a setting that lacks infrastructure e.g., urban search and rescue, a team of networked mobile robots can provide a communication substrate by acting as routers in a wireless mesh network. We study the problem of determining the minimum number of robots, and how to position them, so that all clients using the resulting robotic network are connected and all network links satisfy minimum rate requirements. The key challenge we address is that in an environment with obstacles the strength of a wireless link is a non-monotonic function of the distance between the link end-points. Our approach to the problem is based on virtual potential fields. Clients and environmental obstacles are modeled as virtual charged particles exerting virtual forces on the robots. We validate our algorithm with physical robots in an indoor environment and demonstrate that we are able to get feasible solutions.

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event? We first propose a model, based on common intuitions of believability, about the credibility of information. We then cast the problem as a discrete optimization problem, and introduce optimal centralized solutions and an approximate solution amenable to decentralized implementation whose performance is about 20% off on average from the optimal while being 3 orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions.

Many emerging location-aware applications require position information. However, these applications rarely use celltower-based localization because of its inaccuracy, preferring instead to use the more energy-hungry GPS.In this paper, we present CAPS, a Cell-ID Aided Positioning System. CAPS leverages near-continuous mobility and the position history of a user to achieve significantly better accuracy than the celltower-based approach, while keeping energy overhead low. CAPS is designed based on the insight that users exhibit consistency in routes traveled, and that cell-ID transition points that the user experiences can, on a frequently traveled route, uniquely identify position. To this end, CAPS uses a cell-ID sequence matching technique to estimate current position based on the history of cell-ID and GPS position sequences that match the current cell-ID sequence. We have implemented CAPS on Android-based smartphones and have extensively evaluated it at different locations, and for different platforms and carriers. Our evaluation results show that CAPS can save more than 90% of the energy spent by the positioning system compared to the case where GPS is always used, while providing reasonably accurate position information with errors less than 20% of the celltower-based scheme.

Resource constrained mobile devices need to leverage computation on nearby servers to run responsive applications that recognize objects, people, or gestures from real-time video. The two key questions that impact performance are what computation to offload, and how to structure the parallelism across the mobile device and server. To answer these questions, we develop and evaluate three interactive perceptual applications. We find that offloading and parallelism choices should be dynamic, even for a given application, as performance depends on scene complexity as well as environmental factors such as the network and device capabilities. To this end we develop Odessa, a novel, lightweight, runtime that automatically and adaptively makes offloading and parallelism decisions for mobile interactive perception applications. Our evaluation shows that the incremental greedy strategy of Odessa converges to an operating point that is close to an ideal offline partitioning. It provides more than a 3x improvement in application performance over partitioning suggested by domain experts. Odessa works well across a variety of execution environments, and is agile to changes in the network, device and application inputs.

Wireless sensing and actuation have been explored in many contexts, but the automotive setting has received relatively little attention. Automobiles have tens of onboard sensors and expose several hundred engine parameters which can be tuned (a form of actuation). The optimal tuning for a vehicle can depend upon terrain, traffic, and road conditions, but the ability to tune a vehicle has only been available to mechanics and enthusiasts. In this paper, we describe the design and implementation of CarMA (Car Mobile Assistant), a system that provides high-level abstractions for sensing automobile parameters and tuning them. Using these abstractions, developers can easily write smart-phone "apps" to achieve fuel efficiency, responsiveness, or safety goals. Users of CarMA can tune their vehicles at the granularity of individual trips, a capability we call personalized tuning. We demonstrate through a variety of applications written on top of CarMA that personalized tuning can result in over 10% gains in fuel efficiency. We achieve this through route-specific or driver-specific customizations. Furthermore, CarMA is capable of improving user satisfaction by increasing responsiveness when necessary, and promoting vehicular safety by appropriately limiting the range of performance available to novice or unsafe drivers.

We develop a method to help discover manipulation attacks in protocol implementations. In these attacks, adversaries induce honest nodes to exhibit undesirable behaviors by misrepresenting their intent or network conditions. Our method is based on a novel combination of static analysis with symbolic execution and dynamic analysis with concrete execution. The former finds code paths that are likely vulnerable, and the latter emulates adversarial actions that lead to effective attacks. Our method is precise (i.e., no false positives) and we show that it scales to complex protocol implementations. We apply it to four diverse protocols, including TCP, the 802.11 MAC, ECN, and SCTP, and show that it is able to find all manipulation attacks that have been previously reported for these protocols. We also find a previously unreported attack for SCTP. This attack is a variant of a TCP attack but must be mounted differently in SCTP because of subtle semantic differences between the two protocols.

Credit networks represent a way of modeling trust between entities in a network. Nodes in the network print their own currency and trust each other for a certain amount of each other's currency. This allows the network to serve as a decentralized payment infrastructure---arbitrary payments can be routed through the network by passing IOUs between trusting nodes in their respective currencies---and obviates the need for a common currency. Nodes can repeatedly transact with each other and pay for the transaction using trusted currency. A natural question to ask in this setting is: how long can the network sustain liquidity, i.e. how long can the network support the routing of payments before credit dries up? We answer this question in terms of the long term failure probability of transactions for various network topologies and credit values.

STARTING in 2012, TMC will be going paperless! The journal will be published in a form called OnlinePlus (http:// www.computer.org/onlineplus), in which the format and pagination of a paper issue is maintained, since citation indices and academic promotion processes heavily depend upon these. Subscribers will, at a lower subscription rate, be given access to the full online archive. They will also receive, once every quarter, a small booklet containing abstracts of published articles from three issues and a CD-ROM containing electronic copies of these articles. I would like to take the opportunity to thank Dr. Mani Srivastava for his phenomenal service to the community as Editor-in-Chief. During his tenure, he has raised the quality and the visibility of the journal and has managed its growth and evolution in impressive fashion. He has left big shoes to fi ll! I would also like to welcome our new Associate Editor-in-Chief, Dr. Ram Ramanathan, who is Principal Research Scientist at Raytheon BBN. The journal has grown in size and stature over the years and has reached a point where it can benefi t greatly from a second person at the helm, and Ram has graciously agreed to take on that responsibility. Ram has played a leadership role in the fi eld of mobile computing for nearly two decades, and was also a former associate editor of TMC. Our Editorial Board continues to evolve, and I would like to take this opportunity to introduce the new members, whose biographies appear below, and thank the outgoing ones. I would like to welcome aboard several new Associate Editors to fi ll gaps left by Associate Editors whose terms expired, and to strengthen the Editorial Board’s expertise in emerging areas. It is my pleasure to introduce Fan Bai, Ranveer Chandra, Olivier Dousse, Michael Fang, Christina Fragouli, Allen MacKenzie, and Mihail Sichitiu. Together, they bring expertise in vehicular networks, cognitive radios, cellular networks, network information theory, game theory, location management, and localization. They also increase our international and industry representation. I would like to thank them for taking time from their busy schedules to volunteer for this important service to the community. Finally, I would like to acknowledge the contributions of four Associate Editors whose terms ended recently or who stepped down for personal reasons: Samir Das, Aura Ganz, Srikanth Krishnamurthy, and Marwan Krunz. They brought unique perspectives and expertise to the journal, and we are the richer for it. I greatly appreciate the dedication, diligence, and promptness they have shown during their terms. TMC continues to be a very desirable publication venue for mobile and wireless computing and networking, and this would not be possible without the support of our readers and authors, the members of the Editorial Board, the Steering Committee, and the Computer Society staff. I look forward to hearing feedback from our readership and receiving suggestions for ways to improve the journal in the coming years.

Complex interference in static multihop wireless mesh networks can adversely affect transport protocol performance. Since TCP does not explicitly account for this, starvation and unfairness can result from the use of TCP over such networks. In this paper, we explore mechanisms for achieving fair and efficient congestion control for multihop wireless mesh networks. First, we design an AIMD-based rate-control protocol called Wireless Control Protocol (WCP), which recognizes that wireless congestion is a neighborhood phenomenon, not a node-local one, and appropriately reacts to such congestion. Second, we design a distributed rate controller that estimates the available capacity within each neighborhood and divides this capacity to contending flows, a scheme we call Wireless Control Protocol with Capacity estimation (WCPCap). Using analysis, simulations, and real deployments, we find that our designs yield rates that are both fair and efficient. WCP assigns rates inversely proportional to the number of bottlenecks a flow passes through while remaining extremely easy to implement. An idealized version of WCPCap is max-min fair, whereas a practical implementation of the scheme achieves rates within 15% of the max-min optimal rates while still being distributed and amenable to real implementation.

In this paper, we explore a simple yet effective technique for explicitly allocating airtime to each active pair of communicating neighbors in a wireless neighborhood so that TCP starvation in a wireless mesh network is avoided. Our explicit allocation is efficient, redistributing unused airtime and also accounting for airtime rendered unusable by external interference. Our technique requires no modifications to TCP/IP and the 802.11 MAC, and is responsive to short flows, MAClayer auto rate adaptation, and other dynamics, as we demonstate in extensive experiments on two indoor testbeds. Despite its simplicity, the technique is on average within 12% of the max-min optimal allocation on several canonical topologies. 1.

The increasing ubiquity of the mobile phone is creating many opportunities for personal context sensing, and will result in massive databases of individuals' sensitive information incorporating locations, movements, images, text annotations, and even health data. In existing system architectures, users upload their raw (unprocessed or filtered) data streams directly to content-service providers and have little control over their data once they "opt-in".

Using detailed traces from 255 users, we conduct a comprehensive study of smartphone use. We characterize intentional user activities -- interactions with the device and the applications used -- and the impact of those activities on network and energy usage. We find immense diversity among users. Along all aspects that we study, users differ by one or more orders of magnitude. For instance, the average number of interactions per day varies from 10 to 200, and the average amount of data received per day varies from 1 to 1000 MB. This level of diversity suggests that mechanisms to improve user experience or energy consumption will be more effective if they learn and adapt to user behavior. We find that qualitative similarities exist among users that facilitate the task of learning user behavior. For instance, the relative application popularity for can be modeled using an exponential distribution, with different distribution parameters for different users. We demonstrate the value of adapting to user behavior in the context of a mechanism to predict future energy drain. The 90th percentile error with adaptation is less than half compared to predictions based on average behavior across users.

Many emerging smartphone applications require position information to provide location-based or context-aware services. In these applications, GPS is often preferred over its alternatives such as GSM/WiFi based positioning systems because it is known to be more accurate. However, GPS is extremely power hungry. Hence a common approach is to periodically duty-cycle GPS. However, GPS duty-cycling trades-off positioning accuracy for lower energy. A key requirement for such applications, then, is a positioning system that provides accurate position information while spending minimal energy.

Many applications are enabled by the ability to capture videos on a smartphone and to have these videos uploaded to an Internet-connected server. This capability requires the transfer of large volumes of data from the phone to the infrastructure. Smartphones have multiple wireless interfaces -- 3G/EDGE and WiFi -- for data transfer, but there is considerable variability in the availability and achievable data transfer rate for these networks. Moreover, the energy costs for transmitting a given amount of data on these wireless interfaces can differ by an order of magnitude. On the other hand, many of these applications are often naturally delay-tolerant, so that it is possible to delay data transfers until a lower-energy WiFi connection becomes available. In this paper, we present a principled approach for designing an optimal online algorithm for this energy-delay tradeoff using the Lyapunov optimization framework. Our algorithm, called SALSA, can automatically adapt to channel conditions and requires only local information to decide whether and when to defer a transmission. We evaluate SALSA using real-world traces as well as experiments using a prototype implementation on a modern smartphone. Our results show that SALSA can be tuned to achieve a broad spectrum of energy-delay tradeoffs, is closer to an empirically-determined optimal than any of the alternatives we compare it to, and, can save 10-40% of battery capacity for some workloads.

When many flows are multiplexed on a non-saturated link, their volume changes over short timescales tend to cancel each other out, making the average change across flows close to zero. This equilibrium property holds if the flows are nearly independent, and it is violated by traffic changes caused by several, potentially small, correlated flows. Many traffic anomalies (both malicious and benign) fit this description. Based on this observation, we exploit equilibrium to design a computationally simple detection method for correlated anomalous flows. We compare our new method to two well known techniques on three network links. We manually classify the anomalies detected by the three methods, and discover that our method uncovers a different class of anomalies than previous techniques do.

When many flows are multiplexed on a non-saturated link, their volume changes over short timescales tend to cancel each other out, making the average change across flows close to zero. This equilibrium property holds if the flows are nearly independent, and it is violated by traffic changes caused by several correlated flows. We exploit this empirical property to design a computationally simple anomaly detection method.

Emerging high-rate applications (imaging, structural monitoring, acoustic localization) will need to transport large volumes of data concurrently from several sensors. These applications are also loss-intolerant. A key requirement for such applications, then, is a protocol that reliably transports sensor data from many sources to one or more sinks without incurring congestion collapse. In this article, we discuss RCRT, a rate-controlled reliable transport protocol suitable for constrained sensor nodes. RCRT uses end-to-end explicit loss recovery, but places all the congestion detection and rate adaptation functionality in the sinks. This has two important advantages: efficiency and flexibility. Because sinks make rate allocation decisions, they are able to achieve greater efficiency since they have a more comprehensive view of network behavior. For the same reason, it is possible to alter the rate allocation decisions (for example, from one that ensures that all nodes get the same rate, to one that ensures that nodes get rates in proportion to their demands), without modifying sensor code at all. We evaluate RCRT extensively on a 40-node wireless sensor network testbed and show that RCRT achieves 1.7 times the rate achieved by IFRC and 1.4 times that of WRCP, two recently proposed interference-aware distributed rate-control protocols. We also present results from a 3-month-long 19-node real world deployment of RCRT in an imaging application and show that RCRT works well in real long-term deployments.

Most sensor network research and software design has been guided by an architectural principle that permits multinode data fusion on small-form-factor, resource-poor nodes, or motes . While we were among the earliest promoters of this approach, through experience we found that this principle leads to fragile and unmanageable systems and explore an alternative. The Tenet architecture is motivated by the observation that future large-scale sensor network deployments will be tiered , consisting of motes in the lower tier and masters , relatively unconstrained 32-bit platform nodes, in the upper tier. Tenet constrains multinode fusion to the master tier while allowing motes to process locally-generated sensor data. This simplifies application development and allows mote-tier software to be reused. Applications running on masters task motes by composing task descriptions from a novel tasklet library. Our Tenet implementation also contains a robust and scalable networking subsystem for disseminating tasks and reliably delivering responses. We show that a Tenet pursuit-evasion application exhibits performance comparable to a mote-native implementation while being considerably more compact. We also present two real-world deployments of Tenet system: a structural vibration monitoring application at Vincent Thomas Bridge and an imaging-based habitat monitoring application at James Reserve, and show that tiered architecture scales network capacity and allows reliable delivery of high rate data. 1

Various sensor network measurement studies have reported instances of transient faults in sensor readings. In this work, we seek to answer a simple question: How often are such faults observed in real deployments? We focus on three types of transient faults, caused by faulty sensor readings that appear abnormal. To understand the prevalence of such faults, we first explore and characterize four qualitatively different classes of fault detection methods. Rule-based methods leverage domain knowledge to develop heuristic rules for detecting and identifying faults. Estimation methods predict “normal” sensor behavior by leveraging sensor correlations, flagging anomalous sensor readings as faults. Time-series-analysis-based methods start with an a priori model for sensor readings. A sensor measurement is compared against its predicted value computed using time series forecasting to determine if it is faulty. Learning-based methods infer a model for the “normal” sensor readings using training data, and then statistically detect and identify classes of faults. We find that these four classes of methods sit at different points on the accuracy/robustness spectrum. Rule-based methods can be highly accurate, but their accuracy depends critically on the choice of parameters. Learning methods can be cumbersome to train, but can accurately detect and classify faults. Estimation methods are accurate, but cannot classify faults. Time-series-analysis-based methods are more effective for detecting short duration faults than long duration ones, and incur more false positives than the other methods. We apply these techniques to four real-world sensor datasets and find that the prevalence of faults as well as their type varies with datasets. All four methods are qualitatively consistent in identifying sensor faults, lending credence to our observations. Our work is a first step towards automated online fault detection and classification.

802.11 wireless mesh networks are ubiquitous, but suffer from severe performance degradations due to poor synergy between the 802.11 CSMA MAC protocol and higher layers. Several solutions have been proposed that either involve significant modifications to the 802.11 MAC or legacy higher layer protocols, or rely on 802. MAC models seeded with off-line measurements performed during network downtime.

Detecting visits to semantically meaningful places is important for many emerging mobile applications. We present PlaceSense, a place discovery algorithm suitable for mobile devices that exploits pervasive RF-beacons. By relying on separate mechanisms to detect entrance to and departure from a place and buffering overlapping data for subsequent visits, it is more robust than the state-of-the-art, especially in detecting short visits, places where people are mobile, or where inconsistent beacons are prevalent due to interference. We experimentally evaluate PlaceSense's effectiveness in discovering semantically meaningful places, and compare with other approaches that use coordinates or RF-beacon fingerprints. Our results demonstrate that PlaceSense correctly discovers 92% (compared to between 28% and 65% for previous work) of the visited places and accurately detects their entrance and departure times from both real-life and scripted data sets.

Many threads packages have been proposed for programming wireless sensor platforms. However, many sensor network operating systems still choose to provide an event-driven model, due to efficiency concerns. We present TOS-Threads, a threads package for TinyOS that combines the ease of a threaded programming model with the efficiency of an event-based kernel. TOSThreads is backwards compatible with existing TinyOS code, supports an evolvable, thread-safe kernel API, and enables flexible application development through dynamic linking and loading. In TOS-Threads, TinyOS code runs at a higher priority than application threads and all kernel operations are invoked only via message passing, never directly, ensuring thread-safety while enabling maximal concurrency. The TOSThreads package is non-invasive; it does not require any large-scale changes to existing TinyOS code.

Prior measurement studies of the Internet have explored traffic and topology, but have largely ignored edge hosts. While the number of Internet hosts is very large, and many are hidden behind firewalls or in private address space, there is much to be learned from examining the population of visible hosts, those with public unicast addresses that respond to messages. In this paper we introduce two new approaches to explore the visible Internet. Applying statistical population sampling, we use censuses to walk the entire Internet address space, and surveys to probe frequently a fraction of that space. We then use these tools to evaluate address usage, where we find that only 3.6% of allocated addresses are actually occupied by visible hosts, and that occupancy is unevenly distributed, with a quarter of responsive /24 address blocks (subnets) less than 5% full, and only 9% of blocks more than half full. We show about 34 million addresses are very stable and visible to our probes (about 16% of responsive addresses), and we project from this up to 60 million stable Internet-accessible computers. The remainder of allocated addresses are used intermittently, with a median occupancy of 81 minutes. Finally, we show that many firewalls are visible, measuring significant diversity in the distribution of firewalled block size. To our knowledge, we are the first to take a census of edge hosts in the visible Internet since 1982, to evaluate the accuracy of active probing for address census and survey, and to quantify these aspects of the Internet.

The most common programming languages and platforms for sensor networks foster a low-level programming style. This design provides fine-grained control over the underlying sensor devices, which is critical given their severe resource constraints. However, this design also makes programs difficult to understand, maintain, and debug. In this paper, we describe an approach to automatically recover the high-level system logic from such low-level programs, along with an instantiation of the approach for nesC programs running on top of the TinyOS operating system. We adapt the technique of symbolic execution from the program analysis community to handle the event-driven nature of TinyOS, providing a generic component for approximating the behavior of a sensor network application or system component. We then employ a form of predicate abstraction on the resulting information to automatically produce a finite state machine representation of the component. We have used our tool, called FSMGen, to automatically produce compact and fairly accurate state machines for several TinyOS applications and protocols. We illustrate how this high-level program representation can be used to aid programmer understanding, error detection, and program validation.

Complex interference in static multi-hop wireless mesh networks can adversely affect transport protocol performance. Since TCP does not explicitly account for this, starvation and unfairness can result from the use of TCP over such networks. In this paper, we explore mechanisms for achieving fair and efficient congestion control for multi-hop wireless mesh networks. First, we design an AIMD-based rate-control protocol called Wireless Control Protocol (WCP) which recognizes that wireless congestion is a neighborhood phenomenon, not a node-local one, and appropriately reacts to such congestion. Second, we design a distributed rate controller that estimates the available capacity within each neighborhood, and divides this capacity to contending flows, a scheme we call Wireless Control Protocol with Capacity estimation (WCPCap). Using analysis, simulations, and real deployments, we find that our designs yield rates that are both fair and efficient, and achieve near optimal goodputs for all the topologies that we study. WCP achieves this level of performance while being extremely easy to implement. Moreover, WCPCap achieves the max-min rates for our topologies, while still being distributed and amenable to real implementation.

The efficacy of data aggregation in sensor networks is a function of the degree of spatial correlation in the sensed phenomenon. The recent literature has examined a variety of schemes that achieve greater data aggregation by routing data with regard to the underlying spatial correlation. A well known conclusion from these papers is that the nature of optimal routing with compression depends on the correlation level. In this article we show the existence of a simple, practical, and static correlation-unaware clustering scheme that satisfies a min-max near-optimality condition. The implication for system design is that a static correlation-unaware scheme can perform as well as sophisticated adaptive schemes for joint routing and compression.

It is currently difficult to build practical and reliable programming systems out of distributed and resource-constrained sensor devices. The state of the art in today's sensornet programming is centered around a component-based language called nesC. nesC is a node-level language-a program is written for an individual node in the network-and nesC programs use the services of an operating system called TinyOS. We are pursuing an approach to programming sensor networks that significantly raises the level of abstraction over this practice. The critical change is one of perspective: rather than writing programs from the point of view of an individual node, programmers implement a central program that conceptually has access to the entire network. This approach pushes to the compiler the task of producing node-level programs that implement the desired behavio.

Emerging high-rate applications (imaging, structural monitoring, acoustic localization) will need to transport large volumes of data concurrently from several sensors. These applications are also loss-intolerant. A key requirement for such applications, then, is a protocol that reliably transport sensor data from many sources to one or more sinks without incurring congestion collapse. In this paper, we discuss RCRT, a rate-controlled reliable transport protocol suitable for constrained sensor nodes. RCRT uses end-to-end explicit loss recovery, but places all the congestion detection and rate adaptation functionality in the sinks. This has two important advantages: efficiency and flexibility. Because sinks make rate allocation decisions, they are able to achieve greater efficiency since they have a more comprehensive view of network behavior. For the same reason, it is possible to alter the rate allocation decisions (for example, from one that ensures that all nodes get the same rate, to one that ensures that nodes get rates in proportion to their demands), without modifying sensor code at all. We evaluate RCRT extensively on a 40-node wireless sensor network testbed and show that RCRT achieves more than twice the rate achieved by a recently proposed interference-aware distributed rate-control protocol, IFRC [23].

Network anomaly detection using dimensionality reduction techniques has received much recent attention in the literature. For example, previous work has aggregated netflow records into origin-destination (OD) flows, yielding a much smaller set of dimensions which can then be mined to uncover anomalies. However, this approach can only identify which OD flow is anomalous, not the particular IP flow(s) responsible for the anomaly. In this paper we show how one can use random aggregations of IP flows (i.e., sketches) to enable more precise identification of the underlying causes of anomalies. We show how to combine traffic sketches with a subspace method to (1) detect anomalies with high accuracy and (2) identify the IP flows(s) that are responsible for the anomaly. Our method has detection rates comparable to previous methods and detects many more anomalies than prior work, taking us a step closer towards a robust on-line system for anomaly detection and identification.

Detecting coordinated attacks on Internet resources requires a distributed network monitoring infrastructure. Such an infrastructure will have two logically distinct elements: distributed monitors that continuously collect traffic information, and a distributed query system that allows network operators to efficiently correlate information from different monitors in order to detect anomalous traffic patterns. In this paper, we discuss the design and implementation of MIND, a distributed index management system that supports the creation and querying of multiple distributed indices. We validate MIND using traffic traces from two large backbone networks, then examine the performance of a MIND prototype on more than 100 PlanetLab machines. Our experiments show that MIND can detect and report network anomalies in about one second on an inter-continental backbone. We also analyze the efficiency of our load balancing mechanism and evaluate the robustness of MIND to node failure. I.

... an environment and communicate using wireless links. The lifetime of these networks is severely curtailed by the limited battery power of the sensors. One line of research in sensor network lifetime management has examined sensor selection techniques, in which applications judiciously choose which sensors' data should be retrieved and are worth the expended energy. In the past, many ad-hoc approaches for sensor selection have been proposed. In this paper, we argue that sensor selection should be based upon a tradeoff between application-perceived benefit and energy consumption of the selected sensor set. We propose

Most sensor network research and software design has been guided by an architectural principle that permits multi-node data fusion on small-form-factor, resource-poor nodes, or motes. We argue that this principle leads to fragile and unmanageable systems and explore an alternative. The Tenet architecture is motivated by the observation that future large-scale sensor network deployments will be tiered, consisting of motes in the lower tier and masters, relatively unconstrained 32-bit platform nodes, in the upper tier. Masters provide increased network capacity. Tenet constrains multi-node fusion to the master tier while allowing motes to process locally-generated sensor data. This simplifies application development and allows mote-tier software to be reused. Applications running on masters task motes by composing task descriptions from a novel tasklet library. Our Tenet implementation also contains a robust and scalable networking subsystem for disseminating tasks and reliably delivering responses. We show that a Tenet pursuit-evasion application exhibits performance comparable to a mote-native implementation while being considerably more compact.

Geographic techniques promise highly scalable any-to-any routing in wireless sensor networks. In one thread of research on geographic routing, researchers have explored robust, distributed graph planarization. Arguing that such planarization techniques have high overhead, researchers have more recently pursued a thread in which they propose precomputation of routing structures (e.g., hull trees and grids) to achieve low-overhead geographic routing.In this paper we introduce a third approach, LCR, that does not involve any precomputation of distributed routing structures, nor full a priori planarization. Instead, LCR removes non-planarities lazily only when they interfere with correct geographic routing. Lazy removal of link crossings results in an order of magnitude or more lower overhead than any previously proposed approach. Copyright 2006 ACM.

In a wireless sensor network of N nodes transmitting data to a single base station, possibly over multiple hops, what distributed mechanisms should be implemented in order to dynamically allocate fair and efficient transmission rates to each node? Our interferenceaware fair rate control (IFRC) detects incipient congestion at a node by monitoring the average queue length, communicates congestion state to exactly the set of potential interferers using a novel low-overhead congestion sharing mechanism, and converges to a fair and efficient rate using an AIMD control law. We evaluate IFRC extensively on a 40-node wireless sensor network testbed. IFRC achieves a fair and efficient rate allocation that is within 20-40% of the optimal fair rate allocation on some network topologies. Its rate adaptation mechanism is highly effective: we did not observe a single instance of queue overflow in our many experiments. Finally, IFRC can be extended easily to support situations where only a subset of the nodes transmit, where the network has multiple base stations, or where nodes are assigned different transmission weights.

The Internet is a large, heterogeneous system operating at very high speeds and consisting of a large number of users. Researchers use a suite of tools and techniques in order to understand the performance of complex networks like the Internet: measurements, simulations, and deployments on small to medium-scale testbeds. This work considers a novel addition to this suite: a class of methods to scale down the topology of the Internet that enables researchers to create and observe a smaller replica, and extrapolate its performance to the expected performance of the larger Internet. This is complementary to the work of Psounis, 2003, where the authors presented a way to scale down the Internet in time, by creating a slower replica of the original system. The key insight that we leverage in this work is that only the congested links along the path of each flow introduce sizable queueing delays and dependencies among flows. Hence, one might hope that the network properties can be captured by a topology that consists of the congested links only. Using extensive simulations with transmission control protocol (TCP) traffic and theoretical analysis, we show that it is possible to achieve this kind of performance scaling even on topologies the size of the CENIC backbone (that provides Internet access to higher education institutions in California). We also show that simulating a scaled topology can be up to two orders of magnitude faster than simulating the original topology

Recent sensor networks research has produced a class of data storage and query processing techniques called data-centric storage that leverages locality-preserving distributed indexes to efficiently answer multi-dimensional range and range-aggregate queries. These distributed indexes offer a rich design space of a) logical decompositions of sensor relation schema into indexes, as well as b) physical mappings of these indexes onto sensors. In this paper, we explore this space for energy-efficient data organizations (logical and physical mappings of tuples and attributes to sensor nodes) and devise purely local query optimization techniques for processing queries that span such decomposed relations.

The recent trend of rapid increase in routing table sizes at routers comprising the Internet's core is posing a serious challenge to the current Internet's scalability, availability, and stability. Multihoming is a prime contributor to this table size explosion. This paper argues that it is possible to a) scale the Internet's routing table sub-linearly with degree of multihoming, and b) improve routing convergence times even under pervasive multihoming using simple and incrementally deployable extensions to today's routing protocols. We present an addressing and routing protocol called SIMPLER (scalable IP multihoming protocol leveraging routing), which is designed to minimize and contain the propagation in space and time of non-aggregatable routes. SIMPLER's prefix containment property results in lower lookup and route processing costs (promotes scalability), and faster convergence time (helps network availability and stability). SIMPLER vastly diminishes the number of non-aggregatable prefixes appearing in the Internet core due to multihoming (to zero in the absence of network faults, and O(number of faults) otherwise), and always leaks fewer non-aggregatable prefixes than today's dominant multihoming strategy of "hole punching". Additionally, SIMPLER provides transport-layer survivability (TLS) and better routing policy management, while offering the same routing robustness as today's multihoming. The main cost of SIMPLER is the increased use of address space (O(log(network size)) in the average case). SIMPLER is carefully designed to be useful to both multihomed transit providers and multihomed leaf sites.

With the advent of miniaturized sensing technology, it has become possible to envision smart structures containing millions of sensors embedded in concrete for autonomously detecting and locating incipient damage. Where are we today in our march towards this vision of autonomous structural health monitoring (SHM) using networked embedded sensing? In this paper, we summarize some of the systems we have developed towards this vision. Wisden is a wireless sensor network that allows continuous monitoring of structures and NetSHM is a programmable system that allows civil engineers to implement and deploy SHM techniques without having to understand the intricacies of wireless sensor networking. We highlight our experiences in developing these systems, and discuss the implications of our experiences on the achievability of the overall vision.

Wireless sensor networks research has, till date, made impressive advances in platforms and software services. Research in the area has moved on to consider an essential piece of sensor network technology---support for programming wireless sensor network applications and systems components at a suitably high level of abstraction. Two broad classes of programming models are currently being investigated by the community. One class focuses on providing higher-level abstractions for specifying a node's local behavior in a distributed computation. Examples of this approach include the recent work on node-local or region-based abstractions. By contrast, a second and less-explored class of research considers programming a sensor network in the large called macroprogramming.

Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly different from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems. In this paper, we discuss a random sampling technique that incrementally improves lookup latency in DHT systems. Our sampling can be implemented using information gleaned from lookups traversing the overlay network. For this reason, we call our approach lookup-parasitic random sampling (LPRS). LPRS converges quickly, and requires relatively few modifications to existing DHT systems. For idealized versions of DHT systems like Chord, Tapestry, and Pastry, we analytically prove that LPRS can result in lookup latencies proportional to the average unicast latency of the network, provided the underlying physical topology has a power-law latency expansion. We then validate this analysis by implementing LPRS in the Chord simulator. Our simulations reveal that LPRS-Chord exhibits a qualitatively better latency scaling behavior relative to unmodified Chord. The overhead of LPRS is one sample per lookup hop in the worst case. Finally, we provide evidence which suggests that the Internet router-level topology resembles power-law latency expansion. This finding implies that LPRS has significant practical applicability as a general latency reduction technique for many DHT systems. This finding is also of independent interest since it might inform the design of latency-sensitive topology models for the Internet.

Wireless sensor networks enable dense sensing of the environment, offering unprecedented opportunities for observing the physical world. This article addresses two key challenges in wireless sensor networks: in-network storage and distributed search. The need for these techniques arises from the inability to provide persistent, centralized storage and querying in many sensor networks. Centralized storage requires multihop transmission of sensor data to Internet gateways which can quickly drain battery-operated nodes.Constructing a storage and search system that satisfies the requirements of data-rich scientific applications is a daunting task for many reasons: (a) the data requirements may be large compared to available storage and communication capacity of resource-constrained nodes, (b) user requirements are diverse and range from identification and collection of interesting event signatures to obtaining a deeper understanding of long-term trends and anomalies in the sensor events, and (c) many applications are in new domains where a priori information may not be available to reduce these requirements.This article describes a lossy, gracefully degrading storage model . We believe that such a model is necessary and sufficient for many scientific applications since it supports both progressive data collection for interesting events as well as long-term in-network storage for in-network querying and processing. Our system demonstrates the use of in-network wavelet-based summarization and progressive aging of summaries in support of long-term querying in storage and communication-constrained networks. We evaluate the performance of our linux implementation and show that it achieves: (a) low communication overhead for multiresolution summarization, (b) highly efficient drill-down search over such summaries, and (c) efficient use of network storage capacity through load-balancing and progressive aging of summaries.

Ad-hoc localization systems enable nodes in a sensor network to fix their positions in a global coordinate system using a relatively small number of anchor nodes that know their position through external means (e.g., GPS). Because location information provides context to sensed data, such systems are a critical component of many sensor networks and have therefore received a fair amount of recent attention in the sensor networks literature. The efficacy of these systems is a function of the density of deployment and of anchor nodes, as well as the error in distance estimation (ranging) between nodes. In this paper, we examine how these factors impact the performance of the system. This examination lays the groundwork for the main question we consider in this paper: Can the ability to estimate bearing to neighboring nodes greatly increase the performance of ad-hoc localization systems? We discuss the design of ad-hoc localization systems that use range together with either bearing or imprecise bearing (such as sectoring) information, and evaluate these systems using analysis and simulation.

In the absence of location errors, geographic routing - using a combination of greedy forwarding and face routing - has been shown to work correctly and efficiently. The effects of location errors on geographic routing have not been studied before. In this work we provide a detailed analysis of the effects of location errors on the correctness and performance of geographic routing in static sensor networks. First, we perform a micro-level behavioral analysis to identify the possible protocol error scenarios and their conditions and bounds. Then, we present results from an extensive simulation study of GPSR and GHT to quantify the performance degradation due to location errors. Our results show that even small location errors (of 10% of the radio range or less) can in fact lead to incorrect (non-recoverable) geographic routing with noticeable performance degradation. We then introduce a simple modification for face routing that eliminates probable errors and leads to near perfect performance.

Due to lack of experimental data and sophisticated models derived from such data, most data processing algorithms from the sensor network literature are evaluated with data generated from simple parametric models. Unfortunately, the type of data input used in the evaluation often significantly affects the algorithm performance. Our case studies of a few widely-studied sensor network data processing algorithms demonstrated the need to evaluate algorithms with data across a range of parameters. In conclusion, we propose our synthetic data generation framework.

Unpredictable and heterogeneous links in a wireless sensor network require techniques to avoid low delivery rate and high delivery cost. Three commonly used techniques to help discover high quality paths include (1) link-layer retransmission, (2) blacklisting bad links, and (3) end-to-end routing metrics. Using simulation and testbed experiments, we present the first systematic exploration of the tradeoffs of combinations of these approaches, quantifying the effects of each of these three techniques. We identify several key results: one is that per-hop retransmissions (ARQ) is a necessary addition to any other mechanism if reliable data delivery is a goal. Additional interactions between the services are more subtle. First, in a multihop network, either blacklisting or reliability metrics like ETX can provide consistent high-reliability paths when added to ARQ. Second, at higher deployment densities, blacklisting has a lower routing overhead than CTX. But at lower densities, blacklisting becomes less stable as the network partitions. These results are consistent across both simulation and testbed experiments. We conclude that ETX with retransmissions is the best choice in general, but that blacklisting may be worth considering at higher densities, either with or without ETX.

No abstract available.

Structural health monitoring (SHM) is a well-established multi-disciplinary research field. The goal of SHM is to develop technologies and techniques to automatically detect, localize, and classify damages in large structures (ships, bridges, aircraft and buildings). The state of the art in SHM relies on collecting response of these structures to ambient phenomena such as wind, passing vehicles or earthquakes at various points in the structure (either via manual inspections or expensive wired data acquisition systems) to be analyzed centrally. In our demonstration we will show a proof of concept working model of an automated distributed damage detection system using a sensor-actuator network.

Recent sensor networks research has produced a class of data storage and query processing techniques called Data-Centric Storage that leverages locality-preserving distributed indexes like DIM, DIFS, and GHT to efficiently answer multi-dimensional range and range-aggregate queries. These distributed indexes offer a rich design space of a) logical decompositions of sensor relation schema into indexes, as well as b) physical mappings of these indexes onto sensors. In this poster, we explore this space for energy-efficient data organizations (logical and physical mappings of tuples and attributes to sensor nodes) and devise purely local query optimization techniques for processing queries that span such decomposed relations. We propose four design techniques: (a) fully decomposing the base sensor relation into distinct sub-relations, (b) spatially partitioning these sub-relations across the sensornet, (c) localized query planning and optimization to find fully decentralized optimal join orders, and (d) locally caching join results. Together, these optimizations reduce the overall network energy consumption by 4 times or more when compared against the standard single multi-dimensional distributed index on a variety of synthetic query workloads simulated over both synthetic and real-world datasets. We validate the feasibility of our approach by implementing a functional prototype of our data organizer and query processor on Mica2 motes and observing comparable message cost savings.

No abstract available.

Structural monitoring---the collection and analysis of structural response to ambient or forced excitation--is an important application of networked embedded sensing with significant commercial potential. The first generation of sensor networks for structural monitoring are likely to be data acquisition systems that collect data at a single node for centralized processing. In this paper, we discuss the design and evaluation of a wireless sensor network system (called Wisden for structural data acquisition. Wisden incorporates two novel mechanisms, reliable data transport using a hybrid of end-to-end and hop-by-hop recovery, and low-overhead data time-stamping that does not require global clock synchronization. We also study the applicability of wavelet-based compression techniques to overcome the bandwidth limitations imposed by low-power wireless radios. We describe our implementation of these mechanisms on the Mica-2 motes and evaluate the performance of our implementation. We also report experiences from deploying Wisden on a large structure.

BGP has been deployed in Internet for more than a decade. However, the events that cause BGP topological changes are not well understood. Although large traces of routing updates seen in BGP operation are collected by RIPE RlS and University of Oregon RouteViews, previous work examines this data set as individual routing updates. This paper describes methods that group routing updates into events. Since one event (a policy change or peering failure) results in many update messages, we cluster updates both temporally and topologically (based on the path vector information). We propose a new approach to analyzing the update traces, classifying the topological impact of muting events, and approximating the distance to the autonomous system originating the event. Our analysis provides some insight into routing behavior: First, at least 45% path changes are caused by events on transit peerings. Second, a significant number (23-37%) of path changes are transient, in that routing updates indicate temporary path changes, but they ultimately converge on a path that is identical from the previously stable path. These observations suggest that a content provider cannot guarantee end-to-end routing stability based solely on its relationship with its immediate ISP, and that better detection of transient changes may improve routing stability.

In many sensor networks, data or events are named by attributes. Many of these attributes have scalar values, so one natural way to query events of interest is to use a multi-dimensional range query. An example is: "List all events whose temperature lies between 50° and 60°, and whose light levels lie between 10 and 15." Such queries are useful for correlating events occurring within the network.In this paper, we describe the design of a distributed index that scalably supports multi-dimensional range queries. Our distributed index for multi-dimensional data (or DIM) uses a novel geographic embedding of a classical index data structure, and is built upon the GPSR geographic routing algorithm. Our analysis reveals that, under reasonable assumptions about query distributions, DIMs scale quite well with network size (both insertion and query costs scale as O(√N)). In detailed simulations, we show that in practice, the insertion and query costs of other alternatives are sometimes an order of magnitude more than the costs of DIMs, even for moderately sized network. Finally, experiments on a small scale testbed validate the feasibility of DIMs.

No abstract available.

Wireless sensor networks promise fine-grain monitoring in a wide variety of environments. Many of these environments (e.g., indoor environments or habitats) can be harsh for wireless communication. From a networking perspective, the most basic aspect of wireless communication is the packet delivery performance: the spatio-temporal characteristics of packet loss, and its environmental dependence. These factors will deeply impact the performance of data acquisition from these networks.In this paper, we report on a systematic medium-scale (up to sixty nodes) measurement of packet delivery in three different environments: an indoor office building, a habitat with moderate foliage, and an open parking lot. Our findings have interesting implications for the design and evaluation of routing and medium-access protocols for sensor networks.

The recent growth in the size of the routing table has led to an interest in quantitatively understanding both the causes (eg multihoming) as well as the effects (eg impact on router lookup implementations) of such routing table growth. In this paper, we describe a new model called ARAM that defines the structure of routing tables of any given size. Unlike simpler empirical models that work backwards from effects (eg current prefix length distributions), ARAM approximately models the causes of table growth (allocation by registries, assignment by ISPs, multihoming and load balancing). We show that ARAM models with high fidelity three abstract measures (prefix distribution, prefix depth, and number of nodes in the tree) of the shape of the prefix tree --- as validated against 20 snapshots of backbone routing tables from 1997 to the present. We then use ARAM for evaluating the scalability of IP lookup schemes, and studying the effects of multihoming and load balancing on their scaling behavior. Our results indicate that algorithmic solutions based on multibit tries will provide more prefixes per chip than TCAMs (as table sizes scale toward a million) unless TCAMs can be engineered to use 8 transistors per cell. By contrast, many of today's SRAM-based TCAMs use 14-16 transistors per cell.

Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly di#erent from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems.

Advances in processor, memory, and radio technology enable small and cheap nodes capable of sensing, communication, and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. We explore the directed diffusion paradigm for such coordination. Directed diffusion is data-centric in that all communication is for named data. All nodes in a directed-diffusion-based network are application aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network (e.g., data aggregation). We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network analytically and experimentally. Our evaluation indicates that directed diffusion can achieve significant energy savings and can outperform idealized traditional schemes (e.g., omniscient multicast) under the investigated scenarios.

In-network data aggregation is essential for wireless sensor networks where energy resources are limited. In a previously proposed data dissemination scheme (directed diffusion with opportunistic aggregation), data is opportunistically aggregated at intermediate nodes on a low-latency tree. In this paper, we explore and evaluate greedy aggregation, a novel approach that adjusts aggregation points to increase the amount of path sharing, reducing energy consumption. Our preliminary results suggest that, under investigated scenarios, greedy aggregation can achieve up to 45% energy savings over opportunistic aggregation in high-density networks without adversely impacting latency or robustness.

Anecdotal evidence suggests that misconfiguration of backbone routers occasionally leads to an injection of large routing tables into the BGP routing system. In this paper, we investigate the detailed mechanics of router response to large BGP routing tables. We examine three commercial routers, and find that their responses vary significantly. Some routers exhibit table-size oscillations that have the potential to cause cascading failure. Others need operator intervention to recover from large routing tables. We also find that deployed resource control mechanisms, such as prefix limits and route flap damping, are only partially suceessful in mitigating the impact of large routing tables.

C. Faloutsos et al. (see Proc. ACM SIGCOMM, 1999) found that the inter autonomous system (AS) topology exhibits a power-law vertex degree distribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phenomenon. The work of A.-L. Barabasi and R. Albert (see Science, p.509-512, 1999) and its application to network topology generation in the work of A. Medina et al. (see Proc. MASCOTS, 2001) have explored a promising class of models that yield strict power-law vertex degree distributions. We re-examine the BGP (border gateway protocol) measurements that form the basis for the results reported by Faloutsos et al. We find that by their very nature (i.e., being strictly BGP-based), the data provides a very incomplete picture of Internet connectivity at the AS level. The AS connectivity maps constructed from this data (original maps) typically miss 20-50% or even more of the physical links in AS maps constructed using additional sources (extended maps). Subsequently, we find that while the vertex degree distributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available historical data does not support the connectivity-based dynamics assumed by Barabasi and Albert. Together, our results suggest that the Internet topology at the AS level may well have developed over time following a very different set of growth processes than those proposed by Barabasi and Albert.

Efficient data retrieval in a peer-to-peer system like Freenet is a challenging problem. We study the impact of cache replacement policy on the performance of Freenet. We find that, with Freenet's LRU (least recently used) cache replacement, there is a steep reduction in the hit ratio with increasing load. Based on intuition from the small-world models and the recent theoretical results by Kleinberg, we propose an enhanced-clustering cache replacement scheme for use in place of LRU. Such a replacement scheme forces the routing tables to resemble neighbor relationships in a small-world acquaintance graph - clustering with light randomness. In our simulation, this new scheme improved the request hit ratio dramatically while keeping the small average hops per successful request comparable to LRU. A simple, highly idealized model of Freenet under clustering with light randomness proves that the expected message delivery time in Freenet is O(log/sup 2/n) if the routing tables satisfy the small-world model and have the size /spl theta/(log/sup 2/n).

Route flap damping is considered to be a widely deployed mechanism in core routers that limits the widespread propagation of unstable BGP routing information. Originally designed to suppress route changes caused by link flaps, flap damping attempts to distinguish persistently unstable routes from routes that occasionally fail. It is considered to be a major contributor to the stability of the Internet routing system.We show in this paper that, surprisingly, route flap damping can significantly exacerbate the convergence times of relatively stable routes. For example, a route to a prefix that is withdrawn exactly once and re-announced can be suppressed for up to an hour (using the current RIPE recommended damping parameters). We show that such abnormal behavior fundamentally arises from the interaction of flap damping with BGP path exploration during route withdrawal. We study this interaction using a simple analytical model and understand the impact of various BGP parameters on its occurrence using simulations. Finally, we outline a preliminary proposal to modify route flap damping scheme that removes the undesired interaction in all the topologies we studied. .

Following the long-held belief that the Internet is hierarchical, the network topology generators most widely used by the Internet research community, Transit-Stub and Tiers, create networks with a deliberately hierarchical structure. However, in 1999 a seminal paper by Faloutsos et al. revealed that the Internet's degree distribution is a power-law. Because the degree distributions produced by the Transit-Stub and Tiers generators are not power-laws, the research community has largely dismissed them as inadequate and proposed new network generators that attempt to generate graphs with power-law degree distributions.Contrary to much of the current literature on network topology generators, this paper starts with the assumption that it is more important for network generators to accurately model the large-scale structure of the Internet (such as its hierarchical structure) than to faithfully imitate its local properties (such as the degree distribution). The purpose of this paper is to determine, using various topology metrics, which network generators better represent this large-scale structure. We find, much to our surprise, that network generators based on the degree distribution more accurately capture the large-scale structure of measured topologies. We then seek an explanation for this result by examining the nature of hierarchy in the Internet more closely; we find that degree-based generators produce a form of hierarchy that closely resembles the loosely hierarchical nature of the Internet.

For the past two years,there has been a significant increase in research activities related to studying and modeling the Internet's topology, especially at the level of autonomous systems (ASs). A closer look at the measurements that form the basis for all these studies reveals that the data sets used consist of the BGP routing tables collected by the Oregon route server (henceforth, the Oregon route-views) [1]. So far, there has been anecdotal evidence and an intuitive understanding among researchers in the field that BGP-derived AS connectivity is not complete. However, as far as we know, there has been no systematic study on quantifying the completeness of currently known AS-level Internet topologies. Our main objective in this paper is to quantify the completeness of Internet AS maps constructed from the Oregon route-views and to attempt to capture more representative AS-level Internet topology. One of the main contributions of this paper is in developing a methodology that enables quantitative investigations into issues related to the (in)completeness of BGP-derived AS maps.

It is important to have continuously updated information about network resources and application activities in a wireless sensor network after it is deployed in an unpredictable environment. Such information can help notify users of resource depletion or abnormal activities. However, constrained by the low user-to-node ratio, limited energy and bandwidth resources, it is infeasible to extract the state of each individual node. In this paper, we propose an approach to constructing abstracted scans of sensor network health by applying in-network aggregation of network state. Specifically, we design a residual energy scan which approximately depicts the remaining energy distribution within a sensor network. Simulations show that our approach has good scalability and energy-efficiency characteristics, compared to continuously extracting the residual energy level individually from each node.

One approach to achieving scalability in reliable multicast is to use a hierarchy. A hierarchy can be established at the application level, or by using router-assist. With router-assist we have more fine-grain control over the placement of error-recovery functionality, therefore, a hierarchy produced by assistance from the routers is expected to have better performance. In this paper, we test this hypothesis by comparing two schemes, one that uses an application-level hierarchy (ALH) and another that uses router-assisted hierarchy (RAH). Contrary to our expectations, we find that the qualitative performance of ALH is comparable to RAH. We do not model the overhead of creating the hierarchy nor the cost of adding router-assist to the network. Therefore, our conclusions inform rather than close the debate of which approach is better.

The impact of routing policy on Internet paths is poorly understood. In theory, the policy can inflate shortest-router-hop paths. To our knowledge, the extent of this inflation has not been previously examined. Using a simplified model of the routing policy in the Internet, we obtain approximate indications of the impact of policy routing on Internet paths. Our findings suggest that the routing policy does impact the length of Internet paths significantly. For instance, in our model of the routing policy, some 20% of Internet paths are inflated by more than five router-level hops.

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the liteature. w propose a model braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures

In most distributed systems, naming of nodes for low-level communication leverages topological location (such as node addresses) and is independent of any application. In this paper, we investigate an emerging class of distributed systems where low-level communication does not rely on network topological location. Rather, low-level communication is based on attributes that are external to the network topology and relevant to the application. When combined with dense deployment of nodes, this kind of named data enables in-network processing for data aggregation, collaborative signal processing, and similar problems. These approaches are essential for emerging applications such as sensor networks where resources such as bandwidth and energy are limited. This paper is the first description of the software architecture that supports named data and in-network processing in an operational, multi-application sensor-network. We show that approaches such as in-network aggregation and nested queries can significantly affect network traffic. In one experiment aggregation reduces traffic by up to 42% and nested queries reduce loss rates by 30%. Although aggregation has been previously studied in simulation, this paper demonstrates nested queries as another form of in-network processing, and it presents the first evaluation of these approaches over an operational testbed.

Mercator is a program that uses hop-limited probes-the same primitive used in traceroute-to infer an Internet map. It uses informed random address probing to carefully exploring the IP address space when determining router adjacencies, uses source-route capable routers wherever possible to enhance the fidelity of the resulting map, and employs novel mechanisms for resolving aliases (interfaces belonging to the same router). This paper describes the design of these heuristics and our experiences with Mercator, and presents some preliminary analysis of the resulting Internet map.

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.

Fault isolation has received little attention in the Internet research literature. We take a step towards addressing this deficiency, exploring robust and scalable techniques by which multicast receivers can (in some cases, approximately) locate the on-tree router responsible for a route change, or the link responsible for significant packet loss. A common property of our techniques is that receivers with overlapped paths coordinate to share the responsibility of monitoring paths to the source. Our techniques assume no additional path monitoring capability other than that provided by multicast traceroute (mtrace).

Of the many distributed applications designed for the Internet, the successful ones are those that have paid careful attention to scale and robustness. These applications share several design principles. In this paper, we illustrate the application of these principles to common network monitoring tasks. Specifically, we describe and evaluate 1) a robust distributed topology discovery mechanism and 2) a mechanism for scalable fault isolation in multicast distribution trees. Our mechanisms reveal a different design methodology for network monitoring-one that carefully trades off monitoring fidelity (where necessary) for more graceful degradation in the presence of different kinds of network dynamics.

Article Free Access Share on Next century challenges: scalable coordination in sensor networks Authors: Deborah Estrin USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile , Ramesh Govindan USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile , John Heidemann USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile , Satish Kumar USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile Authors Info & Claims MobiCom '99: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networkingAugust 1999 Pages 263–270https://doi.org/10.1145/313451.313556Published:01 August 1999Publication History 1,787citation7,746DownloadsMetricsTotal Citations1,787Total Downloads7,746Last 12 Months255Last 6 weeks29 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The Internet routing fabric is partitioned into several domains. Each domain represents a region of the fabric administered by a single commercial entity. Over the past two years, the routing fabric has experienced significant growth. From more than a year's worth of inter-domain routing traces, we analyze the Internet inter-domain topology, its route stability behavior, and the effect of growth on these characteristics. Our analysis reveals several interesting results. Despite growth, the degree distribution and the diameter of the inter-domain topology have remained relatively unchanged. Furthermore, there exists a four-level hierarchy of Internet domains classified by degree. However, connectivity between domains is significantly non-hierarchical. Despite increased connectivity at higher levels in the topology, the distribution of paths to prefixes from the backbone remained relatively unchanged. There is evidence that both route availability and the mean reachability duration have degraded with Internet growth.

Due to a limited address space and poor scaling of backbone routing information, the Internet Protocol (IP) is rapidly reaching the end of its useful lifetime. The Simple Internet Protocol Plus (SIPP), a proposed next generation Internet Protocol, solves these problems with larger internet layer addresses. In addition, SIPP provides a number of advanced routing and addressing capabilities including mobility, extended (variable-length) addressing, provider selection, and certain forms of multicast. These capabilities are all achieved through a single mechanism, a generalization of the IP loose source route. We argue that, for reasons of simplicity and evolvability, a single powerful mechanism to achieve a wide range of routing and addressing functions is preferable to having multiple specific mechanisms, one for each function.

The Continuous Media File System, CMFS, supports real-time storage and retrieval of continuous media data (digital audio and video) on disk. CMFS clients read or write files in “sessions,” each with a guaranteed minimum data rate. Multiple sessions, perhaps with different rates, and non-real-time access can proceed concurrently. CMFS addresses several interrelated design issues; real-time semantics fo sessions, disk layout, an acceptance test for new sessions, and disk scheduling policy. We use simulation to compare different design choices.

Next-generation workstations will have hardware support for digital "continuous media" (CM) such as audio and video. CM applications handle data at high rates, with strict timing requirements, and often in small "chunks". If such applications are to run efficiently and predictably as user-level programs, an operating system must provide scheduling and IPC mechanisms that reflect these needs. We propose two such mechanisms: split-level CPU scheduling of lightweight processes in multiple address spaces, and memory-mapped streams for data movement between address spaces. These techniques reduce the the number of user/kernel interactions (system calls, signals, and preemptions). Compared with existing mechanisms, they can reduce scheduling and I/O overhead by a factor of 4 to 6.

The DASH resource model is defined as a basis for reserving and scheduling resources (disk, CPU, network, etc.) involved in end-to-end handling of continuous-media (information flowing continuously over real time i.e. digital audio or digital video) data. The model uses primitives that express work-load characteristics and performance requirements, and defines an algorithm for negotiated reservation of distributed resources. This algorithm is embodied in the session reservation protocol, a backward-compatible extension of the Internet Protocol. Hardware trends and future applications that motivate the DASH resource model are described. The performance requirements for using continuous media and the limitations of existing systems are discussed. The DASH resource model for reserving and scheduling resources is presented. The DASH kernel is briefly described.>