Hardware transports such as RoCE deliver high performance with minimal host CPU, but are best suited to special-purpose deployments that limit their use, e.g., backend networks or Ethernet with Priority Flow Control (PFC). We introduce Falcon, the first hardware transport that supports multiple Upper Layer Protocols (ULPs) and heterogeneous application workloads in general-purpose Ethernet datacenter environments (with losses and without special switch support). Key design elements include: delay-based congestion control with multipath load balancing; a layered design with a simple request-response transaction interface for multi-ULP support; hardware-based retransmissions and error-handling for scalability; and a programmable engine for flexibility. The first Falcon hardware implementation delivers a peak performance of 200 Gbps, 120 Mops/sec, with near-optimal operation completion times that are up to 8× lower than CX-7 RoCE under network congestion, and up to 65% higher goodput under lossy conditions.

We describe our experience with Fathom, a system for identifying the network performance bottlenecks of any service running in the Google fleet. Fathom passively samples RPCs, the principal unit of work for services. It segments the overall latency into host and network components with kernel and RPC stack instrumentation. It records these detailed latency metrics, along with detailed transport connection state, for every sampled RPC. This lets us determine if the completion is constrained by the client, network or server. To scale while enabling analysis, we also aggregate samples into distributions that retain multi-dimensional breakdowns. This provides us with a macroscopic view of individual services. Fathom runs globally in our datacenters for all production traffic, where it monitors billions of TCP connections 24x7. For five years Fathom has been our primary tool for troubleshooting service network issues and assessing network infrastructure changes. We present case studies to show how it has helped us improve our production services.

We present PRR (Protective ReRoute), a transport technique for shortening user-visible outages that complements routing repair. It can be added to any transport to provide benefits in multipath networks. PRR responds to flow connectivity failure signals, e.g., retransmission timeouts, by changing the FlowLabel on packets of the flow, which causes switches and hosts to choose a different network path that may avoid the outage. To enable it, we shifted our IPv6 network architecture to use the FlowLabel, so that hosts can change the paths of their flows without application involvement. PRR is deployed fleetwide at Google for TCP and Pony Express, where it has been protecting all production traffic for several years. It is also available to our Cloud customers. We find it highly effective for real outages. In a measurement study on our network backbones, adding PRR reduced the cumulative region-pair outage time for RPC traffic by 63--84%. This is the equivalent of adding 0.4--0.8 "nines" of availability.

We present a new, host-based design for link load balancing and report the first experiences of link imbalance in datacenters. Our design, PLB (Protective Load Balancing), builds on transport protocols and ECMP/WCMP to reduce network hotspots. PLB randomly changes the paths of connections that experience congestion, preferring to repath after idle periods to minimize packet reordering. It repaths a connection by changing the IPv6 Flow Label on its packets, which switches include as part of ECMP/WCMP. Across hosts, this action drives down hotspots in the network, and lowers the latency of RPCs.

We report on experiences with Swift congestion control in Google datacenters. Swift targets an end-to-end delay by using AIMD control, with pacing under extreme congestion. With accurate RTT measurement and care in reasoning about delay targets, we find this design is a foundation for excellent performance when network distances are well-known. Importantly, its simplicity helps us to meet operational challenges. Delay is easy to decompose into fabric and host components to separate concerns, and effortless to deploy and maintain as a congestion signal while the datacenter evolves. In large-scale testbed experiments, Swift delivers a tail latency of <50μs for short RPCs, with near-zero packet drops, while sustaining ~100Gbps throughput per server. This is a tail of <3x the minimal latency at a load close to 100%. In production use in many different clusters, Swift achieves consistently low tail completion times for short RPCs, while providing high throughput for long RPCs. It has loss rates that are at least 10x lower than a DCTCP protocol, and handles O(10k) incasts that sharply degrade with DCTCP.

Always-on continuous sensing apps drain the battery quickly because they prevent the main processor from sleeping. Instead, sensor hub hardware, available in many smartphones today, can run continuous sensing at lower power while keeping the main processor idle. However, developers have to divide functionality between the main processor and the sensor hub. We implement MobileHub, a system that automatically rewrites applications to leverage the sensor hub without additional programming effort. MobileHub uses a combination of dynamic taint tracking and machine learning to learn when it is safe to leverage the sensor hub without affecting application semantics. We implement MobileHub in Android and prototype a sensor hub on a 8-bit AVR micro-controller. We experiment with 20 applications from Google Play. Our evaluation shows that MobileHub significantly reduces power consumption for continuous sensing apps.

Datacenter transports aim to deliver low latency messaging together with high throughput. We show that simple packet delay, measured as round-trip times at hosts, is an effective congestion signal without the need for switch feedback. First, we show that advances in NIC hardware have made RTT measurement possible with microsecond accuracy, and that these RTTs are sufficient to estimate switch queueing. Then we describe how TIMELY can adjust transmission rates using RTT gradients to keep packet latency low while delivering high bandwidth. We implement our design in host software running over NICs with OS-bypass capabilities. We show using experiments with up to hundreds of machines on a Clos network topology that it provides excellent performance: turning on TIMELY for OS-bypass messaging over a fabric with PFC lowers 99 percentile tail latency by 9X while maintaining near line-rate throughput. Our system also outperforms DCTCP running in an optimized kernel, reducing tail latency by $13$X. To the best of our knowledge, TIMELY is the first delay-based congestion control protocol for use in the datacenter, and it achieves its results despite having an order of magnitude fewer RTT signals (due to NIC offload) than earlier delay-based schemes such as Vegas.

Through their normal operation, cellular networks are a repository of continuous location information from their subscribed devices. Such information, however, comes at a coarse granularity both in terms of space, as well as time. For otherwise inactive devices, location information can be obtained at the granularity of the associated cellular sector, and at infrequent points in time, that are sensitive to the structure of the network itself, and the level of mobility of the device. In this paper, we are asking the question of whether such sparse information can help to identify the paths followed by mobile connected devices throughout the day. If such a task is possible, then we would not only enable continuous mobility path estimation for smartphones, but also for the millions of future connected "things".

Browser caches are widely used to improve the performance of Web page loads. Unfortunately, current object-based caching is too coarse-grained to minimize the costs associated with small, localized updates to a Web object. In this paper, we evaluate the benefits if caching were performed at a finer granularity and at different levels (i.e., computed layout and compiled JavaScript). By analyzing Web pages gathered over two years, we find that both layout and code are highly cacheable, suggesting that our proposal can radically reduce time to first paint. We also find that mobile pages are similar to their desktop counterparts in terms of the amount and composition of updates.

RF-powered computers are small devices that compute and communicate using only the power that they harvest from RF signals. While existing technologies have harvested power from ambient RF sources (e.g., TV broadcasts), they require a dedicated gateway (like an RFID reader) for Internet connectivity. We present Wi-Fi Backscatter, a novel communication system that bridges RF-powered devices with the Internet. Specifically, we show that it is possible to reuse existing Wi-Fi infrastructure to provide Internet connectivity to RF-powered devices. To show Wi-Fi Backscatter's feasibility, we build a hardware prototype and demonstrate the first communication link between an RF-powered device and commodity Wi-Fi devices. We use off-the-shelf Wi-Fi devices including Intel Wi-Fi cards, Linksys Routers, and our organization's Wi-Fi infrastructure, and achieve communication rates of up to 1 kbps and ranges of up to 2.1 meters. We believe that this new capability can pave the way for the rapid deployment and adoption of RF-powered devices and achieve ubiquitous connectivity via nearby mobile devices that are Wi-Fi enabled.

Mobile phones in the 3G/4G era enable us to stay connected not only to the voice network, but also to online services like social networks. In this paper, we study the energy and network costs of mobile applications that provide continuous online presence (e.g. WhatsApp, Facebook, Skype). By combining measurements taken on the mobile and the cellular access network, we reveal a detailed picture of the mechanisms selected to implement online presence, along with their effect on handset energy consumption and network signaling traffic.

As personal information increases in value, the incentives for remote services to collect as much of it as possible increase as well. In the current Internet, the default assumption is that all behavior can be correlated using a variety of identifying information, not the least of which is a user's IP address. Tools like Tor, Privoxy, and even NATs, are located at the opposite end of the spectrum and prevent any behavior from being linked. Instead, our goal is to provide users with more control over linkability---which activites of the user can be correlated at the remote services---not necessarily more anonymity.

We present the design of a communication system that enables two devices to communicate using ambient RF as the only source of power. Our approach leverages existing TV and cellular transmissions to eliminate the need for wires and batteries, thus enabling ubiquitous communication where devices can communicate among themselves at unprecedented scales and in locations that were previously inaccessible.

We present the design and evaluation of FindAll, a local search engine that lets users search and retrieve web pages, even in the absence of connectivity. Our user study with 23 users show that mobile users often search for web pages that they have previously visited, known as re-finding. This re-finding behavior makes the case for a local solution. FindAll goes beyond caching and using keyword search, and instead, implements a full blown search engine. The key challenge in FindAll is in designing a search engine, which is both memory- and energy-intensive, on the constrained phone environment. To this end, FindAll balances the cost of running the search engine with the expected benefits of serving a web page locally. FindAll estimates the benefits of local search, by learning the re-finding behavior of users. We implement FindAll on Android by adapting a publicly available search engine. Our evaluations, based on the traces collected from our user study, shows that FindAll reduces search latency by two-folds for users who re-find often, and reduces 3G data usage by up to 100 MB a month.

The articles in this special section contain selected papers from MobiSys 2011.

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.

The 60 GHz wireless technology that is now emerging has the potential to provide dense and extremely fast connectivity at low cost. In this paper, we explore its use to relieve hotspots in oversubscribed data center (DC) networks. By experimenting with prototype equipment, we show that the DC environment is well suited to a deployment of 60GHz links contrary to concerns about interference and link reliability. Using directional antennas, many wireless links can run concurrently at multi-Gbps rates on top-of-rack (ToR) switches. The wired DC network can be used to sidestep several common wireless problems. By analyzing production traces of DC traffic for four real applications, we show that adding a small amount of network capacity in the form of wireless flyways to the wired DC network can improve performance. However, to be of significant value, we find that one hop indirect routing is needed. Informed by our 60GHz experiments and DC traffic analysis, we present a design that uses DC traffic levels to select and adds flyways to the wired DC network. Trace-driven evaluations show that network-limited DC applications with predictable traffic workloads running on a 1:2 oversubscribed network can be sped up by 45% in 95% of the cases, with just one wireless device per ToR switch. With two devices, in 40% of the cases, the performance is identical to that of a non-oversubscribed network.

RSSI is known to be a fickle indicator of whether a wireless link will work, for many reasons. This greatly complicates operation because it requires testing and adaptation to find the best rate, transmit power or other parameter that is tuned to boost performance. We show that, for the first time, wireless packet delivery can be accurately predicted for commodity 802.11 NICs from only the channel measurements that they provide. Our model uses 802.11n Channel State Information measurements as input to an OFDM receiver model we develop by using the concept of effective SNR. It is simple, easy to deploy, broadly useful, and accurate. It makes packet delivery predictions for 802.11a/g SISO rates and 802.11n MIMO rates, plus choices of transmit power and antennas. We report testbed experiments that show narrow transition regions (<2 dB for most links) similar to the near-ideal case of narrowband, frequency-flat channels. Unlike RSSI, this lets us predict the highest rate that will work for a link, trim transmit power, and more. We use trace-driven simulation to show that our rate prediction is as good as the best rate adaptation algorithms for 802.11a/g, even over dynamic channels, and extends this good performance to 802.11n.

The next generation internet will be the internet of things (and not just of computing devices like PCs, PDAs); this is presumed to be enabled by integrating simple computing plus communications capabilities into common objects of everyday use. Radio-frequency identification (RFID) is a compelling technology for creation of such pervasive sensor networks due to its potential for ubiquitous, low-cost/low-maintenance use. However, the current drivers for RFID deployment emphasize supply chain management using passive tags, implying that RFID sensor nets require advances beyond the components and system designs aimed at supply chain applications. This work provides a glimpse of how this may be achieved.

Increasingly, users access online services such as email, e-commerce, and social networking sites via 802.11-based wireless networks. As they do so, they expose a range of personal information such as their names, email addresses, and ZIP codes to anyone within broadcast range of the network. This paper presents results from an exploratory study that examined how users from the general public understand Wi-Fi, what their concerns are related to Wi-Fi use, and which practices they follow to counter perceived threats. Our results reveal that while users understand the practical details of Wi-Fi use reasonably well, they lack understanding of important privacy risks. In addition, users employ incomplete protective practices which results in a false sense of security and lack of concern while on Wi-Fi. Based on our results, we outline opportunities for technology to help address these problems.

This paper presents the design and evaluation of SafeGuard, an intra-domain routing system that can safely forward packets to their destinations even when routes are changing. SafeGuard is based on the simple idea that packets carry a destination address plus a local estimate of the remaining path cost. We show that this simple design enables routers to detect path inconsistencies during route changes and resolve on a working path for anticipated failure and restoration scenarios. This in turn means that route changes do not disrupt connectivity although routing tables are inconsistent over the network. We evaluate the router performance of SafeGuard using a prototype based on NetFPGA and Quagga. We show that SafeGuard is amenable to high-speed hardware implementation with low overhead. We evaluate the network performance of SafeGuard via simulation. The results show that SafeGuard converges faster than a state-of-the-art IP fast restoration mechanism and reduces periods of disruption to a minimal duration, i.e., the failure detection time.

We explore a dense sensing approach that uses RFID sensor network technology to recognize human activities. In our setting, everyday objects are instrumented with UHF RFID tags called WISPs that are equipped with accelerometers. RFID readers detect when the objects are used by examining this sensor data, and daily activities are then inferred from the traces of object use via a Hidden Markov Model. In a study of 10 participants performing 14 activities in a model apartment, our approach yielded recognition rates with precision and recall both in the 90% range. This compares well to recognition with a more intrusive short-range RFID bracelet that detects objects in the proximity of the user; this approach saw roughly 95% precision and 60% recall in the same study. We conclude that RFID sensor networks are a promising approach for indoor activity monitoring.

We describe the design and implementation of Privacy Oracle, a system that reports on application leaks of user information via the network traffic that they send. Privacy Oracle treats each application as a black box, without access to either its internal structure or communication protocols. This means that it can be used over a broad range of applications and information leaks (i.e., not only Web traffic or credit card numbers). To accomplish this, we develop a differential testing technique in which perturbations in the application inputs are mapped to perturbations in the application outputs to discover likely leaks; we leverage alignment algorithms from computational biology to find high quality mappings between different byte-sequences efficiently. Privacy Oracle includes this technique and a virtual machine-based testing system. To evaluate it, we tested 26 popular applications, including system and file utilities, media players, and IM clients. We found that Privacy Oracle discovered many small and previously undisclosed information leaks. In several cases, these are leaks of directly identifying information that are regularly sent in the clear (without end-to-end encryption) and which could make users vulnerable to tracking by third parties or providers.

This paper examines the performance of EPC Class-1 Generation-2 UHF RFID reader systems in a realistic setting. Specifically, we identify factors that degrade overall performance and reliability with a focus on the physical layer, and we explore the degree to which reader configuration options can mitigate these factors. We use a custom software-radio based RFID monitoring system and configurable RFID readers to gather fine-grained data and assess the effects of the different factors. We find that physical layer considerations have a significant impact on reader performance, and that this is exacerbated by a lack of integration between the physical and MAC layers. We show that tuning physical layer operating parameters can increase the read rate for a set of tags by more than a third. Additionally, we show that tighter integration of the physical and MAC layers has the potential for even greater improvements.

A fundamental problem with unmanaged wireless networks is high packet loss rates and poor spatial reuse, especially with bursty traffic typical of normal use. To address these limitations, we explore the notion of interference cancellation for unmanaged networks - the ability for a single receiver to disambiguate and successfully receive simultaneous overlapping transmissions from multiple unsynchronized sources. We describe a practical algorithm for interference cancellation, and implement it for ZigBee using software radios. In this setting, we find that our techniques can reduce packet loss rate and substantially increase spatial reuse. With carrier sense set to prevent concurrent sends, our approach reduces the packet loss rate during collisions from 14% to 8% due to improved handling of hidden terminals. Conversely, disabling carrier sense reduces performance for only 7% of all pairs of links and increases the delivery rate for the median pair of links in our testbed by a factor of 1.8 due to improved spatial reuse.

We present the design and evaluation of an 802.11-like wireless link layer protocol that obfuscates all transmitted bits to increase privacy. This includes explicit identifiers such as MAC addresses, the contents of management messages, and other protocol fields that the existing 802.11 protocol relies on to be sent in the clear. By obscuring these fields, we greatly increase the difficulty of identifying or profiling users from their transmissions in ways that are otherwise straightforward. Our design, called SlyFi, is nearly as efficient as existing schemes such as WPA for discovery, link setup, and data delivery despite its heightened protections; transmission requires only symmetric key encryption and reception requires a table lookup followed by symmetric key decryption. Experiments using our implementation on Atheros 802.11 drivers show that SlyFi can discover and associate with networks faster than 802.11 using WPA-PSK. The overhead SlyFi introduces in packet delivery is only slightly higher than that added by WPA-CCMP encryption (10% vs. 3% decrease in throughput).

We demonstrate a simple RFID sensor network comprised of an Intel WISP and a commodity UHF RFID reader. WISPs are devices that gather their operating energy from RFID reader transmissions, in the manner of passive RFID tags, and further include sensors, e.g., accelerometers, and provide a very small-scale computing platform. We believe that the small form factor and lack of battery makes the WISP an attractive alternative to motes for many of the original smart dust applications that require very small or long-lived sensors. The Intel WISP that we demonstrate has an ultra-low-power microcontroller, 32K of program space, 8K of flash, and accelerometer and temperature sensors. It harvests power from and communicates sensor data to standard (EPC Class 1 Gen 2) UHF RFID readers with a range of roughly 10 feet. This combination of RFID technology and sensor networks raises many research challenges, such as how to function with intermittent power and how to modify RFID protocols to support sensor queries.

The ubiquity of 802.11 devices and networks enables anyone to track our every move with alarming ease. Each 802.11 device transmits a globally unique and persistent MAC address and thus is trivially identifiable. In response, recent research has proposed replacing such identifiers with pseudonyms (i.e., temporary, unlinkable names). In this paper, we demonstrate that pseudonyms are insufficient to prevent tracking of 802.11 devices because implicit identifiers, or identifying characteristics of 802.11 traffic, can identify many users with high accuracy. For example, even without unique names and addresses, we estimate that an adversary can identify 64 % of users with 90 % accuracy when they spend a day at a busy hot spot. We present an automated procedure based on four previously unrecognized implicit identifiers that can identify users in three real 802.11 traces even when pseudonyms and encryption are employed. We find that the majority of users can be identified using our techniques, but our ability to identify users is not uniform; some users are not easily identifiable. Nonetheless, we show that even a single implicit identifier is sufficient to distinguish many users. Therefore, we argue that design considerations beyond eliminating explicit identifiers (i.e., unique names and addresses), must be addressed in order to prevent user tracking in wireless networks. Categories and Subject Descriptors:

We study the impact on 802.11 networks of RF interference from devices such as Zigbee and cordless phones that increasingly crowd the 2.4GHz ISM band, and from devices such as wireless camera jammers and non-compliant 802.11 devices that seek to disrupt 802.11 operation. Our experiments show that commodity 802.11 equipment is surprisingly vulnerable to certain patterns of weak or narrow-band interference. This enables us to disrupt a link with an interfering signal whose power is 1000 times weaker than the victim's 802.11 signals, or to shut down a multiple AP, multiple channel managed network at a location with a single radio interferer. We identify several factors that lead to these vulnerabilities, ranging from MAC layer driver implementation strategies to PHY layer radio frequency implementation strategies. Our results further show that these factors are not overcome by simply changing 802.11 operational parameters (such as CCA threshold, rate and packet size) with the exception of frequency shifts. This leads us to explore rapid channel hopping as a strategy to withstand RF interference. We prototype a channel hopping design using PRISM NICs, and find that it can sustain throughput at levels of RF interference well above that needed to disrupt unmodified links, and at a reasonable cost in terms of switching overheads.

We present Topology-based Geolocation (TBG), a novel approach to estimating the geographic location of arbitrary Internet hosts. We motivate our work by showing that 1) existing approaches, based on end-to-end delay measurements from a set of landmarks, fail to outperform much simpler techniques, and 2) the error of these approaches is strongly determined by the distance to the nearest landmark, even when triangulation is used to combine estimates from different landmarks. Our approach improves on these earlier techniques by leveraging network topology, along with measurements of network delay, to constrain host position. We convert topology and delay data into a set of constraints, then solve for router and host locations simultaneously. This approach improves the consistency of location estimates, reducing the error substantially for structured networks in our experiments on Abilene and Sprint. For networks with insufficient structural constraints, our techniques integrate external hints that are validated using measurements before being trusted. Together, these techniques lower the median estimation error for our university-based dataset to 67 km vs. 228 km for the best previous approach.

This paper presents Virgil, an automatic access point discovery and selection system. Unlike existing systems that select access points based entirely on received signal strength, Virgil scans for all available APs at a location, quickly associates to each, and runs a battery of tests to estimate the quality of each AP's connection to the Internet. Virgil also probes for blocked or redirected ports, to guide AP selection in favor of preserving application services that are currently in use. Results of our evaluation across five neighborhoods in three cities show Virgil finds a usable connection from 22% to 100% more often than selecting based on signal strength alone. By caching AP test results, Virgil both improves performance and success rate. Our overhead is acceptable and is shown to be faster than manually selecting an AP with Windows XP.

We present Wit, a non-intrusive tool that builds on passive monitoring to analyze the detailed MAC-level behavior of operational wireless networks. Wit uses three processing steps to construct an enhanced trace of system activity. First, a robust merging procedure combines the necessarily incomplete views from multiple, independent monitors into a single, more complete trace of wireless activity. Next, a novel inference engine based on formal language methods reconstructs packets that were not captured by any monitor and determines whether each packet was received by its destination. Finally, Wit derives network performance measures from this enhanced trace; we show how to estimate the number of stations competing for the medium. We assess Wit with a mix of real traces and simulation tests. We find that merging and inference both significantly enhance the originally captured trace. We apply Wit to multi-monitor traces from a live network to show how it facilitates 802.11 MAC analyses that would otherwise be difficult or rely on less accurate heuristics.

We present practical models for the physical layer behaviors of packet reception and carrier sense with interference in static wireless networks. These models use measurements of a real network rather than abstract RF propagation models as the basis for accuracy in complex environments. Seeding our models requires N trials in an N node network, in which each sender transmits in turn and receivers measure RSSI values and packet counts, both of which are easily obtainable. The models then predict packet delivery and throughput in the same network for different sets of transmitters with the same node placements. We evaluate our models for the base case of two senders that broadcast packets simultaneously. We find that they are effective at predicting when there will be significant interference effects. Across many predictions, we obtain an RMS error for 802.11a and 802.11b of a half and a third, respectively, of a measurement-based model that ignores interference.

We present the design of a routing system in which end-systems set tags to select non-shortest path routes as an alternative to explicit source routes. Routers collectively generate these routes by using tags as hints to independently deflect packets to neighbors that lie off the shortest-path. We show how this can be done simply, by local extensions of the shortest path machinery, and safely, so that loops are provably not formed. The result is to provide end-systems with a high-level of path diversity that allows them to bypass unde-sirable locations within the network. Unlike explicit source routing, our scheme is inherently scalable and compatible with ISP policies because it derives from the deployed Internet routing. We also sug-gest an encoding that is compatible with common IP usage, making our scheme incrementally deployable at the granularity of individual routers.

We present the design and evaluation of TVA, a network architecture that limits the impact of Denial of Service (DoS) floods from the outset. Our work builds on earlier work on capabilities in which senders obtain short-term authorizations from receivers that they stamp on their packets. We address the full range of possible attacks against communication between pairs of hosts, including spoofed packet floods, network and host bottlenecks, and router state exhaustion. We use simulation to show that attack traffic can only degrade legitimate traffic to a limited extent, significantly outperforming previously proposed DoS solutions. We use a modified Linux kernel implementation to argue that our design can run on gigabit links using only inexpensive off-the-shelf hardware. Our design is also suitable for transition into practice, providing incremental benefit for incremental deployment.

Pervasive computing provides an attractive vision for the future of computing. Computational power will be available everywhere. Mobile and stationary devices will dynamically connect and coordinate to seamlessly help people in accomplishing their tasks. For this vision to become a reality, developers must build applications that constantly adapt to a highly dynamic computing environment. To make the developers' task feasible, we present a system architecture for pervasive computing, called one.world. Our architecture provides an integrated and comprehensive framework for building pervasive applications. It includes services, such as discovery and migration, that help to build applications and directly simplify the task of coping with constant change. We describe our architecture and its programming model and reflect on our own and others' experiences with using it.

To date, realistic ISP topologies have not been accessible to the research community, leaving work that depends on topology on an uncertain footing. In this paper, we present new Internet mapping techniques that have enabled us to measure router-level ISP topologies. Our techniques reduce the number of required traces compared to a brute-force, all-to-all approach by three orders of magnitude without a significant loss in accuracy. They include the use of BGP routing tables to focus the measurements, the elimination of redundant measurements by exploiting properties of IP routing, better alias resolution, and the use of DNS to divide each map into POPs and backbone. We collect maps from ten diverse ISPs using our techniques, and find that our maps are substantially more complete than those of earlier Internet mapping efforts. We also report on properties of these maps, including the size of POPs, distribution of router outdegree, and the interdomain peering structure. As part of this work, we release our maps to the community.

Diagnosing faults in the Internet is arduous and time-consuming, in part because the network is composed of diverse components spread across many administrative domains. We consider an extreme form of this problem: can end users, with no special privileges, identify and pinpoint faults inside the network that degrade the performance of their applications? To answer this question, we present both an architecture for user-level Internet path diagnosis and a practical tool to diagnose paths in the current Internet. Our architecture requires only a small amount of network support, yet it is nearly as complete as analyzing a packet trace collected at all routers along the path. Our tool, tulip, diagnoses reordering, loss and significant queuing events by leveraging well deployed but little exploited router features that approximate our architecture. Tulip can locate points of reordering and loss to within three hops and queuing to within four hops on most paths that we measured. This granularity is comparable to that of a hypothetical network tomography tool that uses 65 diverse hosts to localize faults on a given path. We conclude by proposing several simple changes to the Internet to further improve its diagnostic capabilities.

In this paper, we present STP, a system in which communicating end hosts use untrusted mobile code to remotely upgrade each other with the transport protocols that they use to communicate. New transport protocols are written in a type-safe version of C, distributed out-of-band, and run in-kernel. Communicating peers select a transport protocol to use as part of a TCP-like connection setup handshake that is backwards-compatible with TCP and incurs minimum connection setup latency. New transports can be invoked by unmodified applications. By providing a late binding of protocols to hosts, STP removes many of the delays and constraints that are otherwise commonplace when upgrading the transport protocols deployed on the Internet. STP is simultaneously able to provide a high level of security and performance. It allows each host to protect itself from untrusted transport code and to ensure that this code does not harm other network users by sending significantly faster than a compliant TCP. It runs untrusted code with low enough overhead that new transport protocols can sustain near gigabit rates on commodity hardware. We believe that these properties, plus compatibility with existing applications and transports, complete the features that are needed to make STP useful in practice.

We describe a novel constraint-based approach to approximate ISP link weights using only end-to-end measurements. Common routing protocols such as OSPF and IS-IS choose least-cost paths using link weights, so inferred weights provide a simple, concise, and useful model of intradomain routing. Our approach extends router-level ISP maps, which include only connectivity, with link weights that are consistent with routing. Our inferred weights agree well with observed routing: while our inferred weights fully characterize the set of shortest paths between 84--99% of the router-pairs, alternative models based on hop count and latency do so for only 47--81% of the pairs.

It is well-known that simple, accidental BGP configuration errors can disrupt Internet connectivity. Yet little is known about the frequency of misconfiguration or its causes, except for the few spectacular incidents of widespread outages. In this paper, we present the first quantitative study of BGP misconfiguration. Over a three week period, we analyzed routing table advertisements from 23 vantage points across the Internet backbone to detect incidents of misconfiguration. For each incident we polled the ISP operators involved to verify whether it was a misconfiguration, and to learn the cause of the incident. We also actively probed the Internet to determine the impact of misconfiguration on connectivity.Surprisingly, we find that configuration errors are pervasive, with 200-1200 prefixes (0.2-1.0% of the BGP table size) suffering from misconfiguration each day. Close to 3 in 4 of all new prefix advertisements were results of misconfiguration. Fortunately, the connectivity seen by end users is surprisingly robust to misconfigurations. While misconfigurations can substantially increase the update load on routers, only one in twenty five affects connectivity. While the causes of misconfiguration are diverse, we argue that most could be prevented through better router design.

To date, realistic ISP topologies have not been accessible to the research community, leaving work that depends on topology on an uncertain footing. In this paper, we present new Internet mapping techniques that have enabled us to directly measure router-level ISP topologies. Our techniques reduce the number of required traces compared to a brute-force, all-to-all approach by three orders of magnitude without a significant loss in accuracy. They include the use of BGP routing tables to focus the measurements, exploiting properties of IP routing to eliminate redundant measurements, better alias resolution, and the use of DNS to divide each map into POPs and backbone. We collect maps from ten diverse ISPs using our techniques, and find that our maps are substantially more complete than those of earlier Internet mapping efforts. We also report on properties of these maps, including the size of POPs, distribution of router outdegree, and the inter-domain peering structure. As part of this work, we release our maps to the community.

Pervasive computing, with its focus on users and their tasks rather than on computing devices and technology, provides an attractive vision for the future of computing. But, while hardware and networking infrastructure to realize this vision are becoming a reality, precious few applications run in this infrastructure. We believe that this lack of applications stems largely from the fact that it is currently too hard to design, build, and deploy applications in the pervasive computing space. In this paper, we argue that existing approaches to distributed computing are flawed along three axes when applied to pervasive computing; we sketch out alternatives that are better suited for this space. First, application data and functionality need to be kept separate, so that they can evolve gracefully, in a global computing infrastructure. Second, applications need to be able to acquire any resource they need at any time, so that they can continuously provide their services in a highly dynamic environment. Third, pervasive computing requires a common system platform, allowing applications to be run across the range of devices and to be automatically distributed and installed.

We present an improved explicit congestion notification (ECN) mechanism that enables a router to signal congestion to the sender without trusting the receiver or other network devices along the signaling path. Without our mechanism, ECN-based transports can be manipulated to undermine congestion control. Web clients seeking faster downloads, for example, can trivially conceal congestion signals from Web servers. A misbehaving connection would exceed its fair bandwidth share at the expense of competing traffic by as much as an order of magnitude in our simulations. Our improved mechanism is robust because it does not depend on correct implementation at locations other than the sender and marking router, and it is practical because it admits an efficient implementation that is backwards-compatible with prior ECN and TCP/IP mechanisms.

FIFO queueing is simple but does not protect traffic from high-bandwidth flows, which include not only flows that fail to use end-to-end congestion control, but also short round-trip time TCP flows. At the other extreme, per-flow scheduling mechanisms provide max-min fairness but are more complex, keeping state for all flows going through the router. This paper presents RED-PD (Random Early Detection-Preferential Dropping), a mechanism that combines simplicity and protection by keeping state for just the high-bandwidth flows. RED-PD uses the packet drop history at the router to detect high-bandwidth flows in times of congestion and preferentially drops packets from these flows. This paper discusses the design decisions underlying RED-PD. We show that it is effective at controlling high-bandwidth flows using a small amount of state and very simple fast-path operations.

This paper describes a technique for tracing anonymous packet flooding attacks in the Internet back toward their source. This work is motivated by the increased frequency and sophistication of denial-of-service attacks and by the difficulty in tracing packets with incorrect, or "spoofed," source addresses. We describe a general purpose traceback mechanism based on probabilistic packet marking in the network. Our approach allows a victim to identify the network path(s) traversed by attack traffic without requiring interactive operational support from Internet service providers (ISPs). Moreover, this traceback can be performed "post mortem"-after an attack has completed. We present an implementation of this technology that is incrementally deployable, (mostly) backward compatible, and can be efficiently implemented using conventional technology.

This paper describes a technique for tracing anonymous packet flooding attacks in the Internet back towards their source. This work is motivated by the increased frequency and sophistication of denial-of-service attacks and by the difficulty in tracing packets with incorrect, or ``spoofed'', source addresses. In this paper we describe a general purpose traceback mechanism based on probabilistic packet marking in the network. Our approach allows a victim to identify the network path(s) traversed by attack traffic without requiring interactive operational support from Internet Service Providers (ISPs). Moreover, this traceback can be performed ``post-mortem'' -- after an attack has completed. We present an implementation of this technology that is incrementally deployable, (mostly) backwards compatible and can be efficiently implemented using conventional technology.

We present a technique for identifying repetitive information transfers and use it to analyze the redundancy of network traffic. Our insight is that dynamic content, streaming media and other traffic that is not caught by today's Web caches is nonetheless likely to derive from similar information. We have therefore adapted similarity detection techniques to the problem of designing a system to eliminate redundant transfers. We identify repeated byte ranges between packets to avoid retransmitting the redundant data.

A key challenge facing wireless networking is to utilize the spectrum as efficiently as possible given current channel conditions and in the most effective way for each application.This is difficult to achieve with existing wireless devices because physical layer functionality is fixed, while channel condibions and applications can change rapidly.Here; we argue that RadioActive networks, an adaptable wireless network architecture that draws on the strengths of software radios and active networks, can meet this challenge.Active networks provide a framework for programming network services, and software radios extend this programmability into the phvsical layer.?Ve believe that this approach offers the opliortunity for significant improvements in functionality and performance over today's wireless networks by making it no longer necessary to design a priori with pessimistic assumptions that describe worst case conditions.In this paper, we outline our vision, the opportunities it affords, and the challenges that must be tackled before it can become a reality.

Although active networks have generated much debate in the research community, on the whole there has been little hard evidence to inform this debate. This paper aims to redress the situation by reporting what we have learned by designing, implementing and using the ANTS active network toolkit over the past two years. At this early stage, active networks remain an open research area. However, we believe that we have made substantial progress towards providing a more flexible network layer while at the same time addressing the performance and security concerns raised by the presence of mobile code in the network. In this paper, we argue our progress towards the original vision and the difficulties that we have not yet resolved in three areas that characterize a "pure" active network: the capsule model of programmability; the accessibility of that model to all users; and the applications that can be constructed in practice.

An active network allows applications to inject customized programs into network nodes. This enables faster protocol innovation by making it easier to deploy new network protocols, even over the wide area. We argue that the ability to introduce active protocols offers important opportunities for end-to-end performance improvements of distributed applications. We begin by describing several active protocols that provide novel network services and discussing the potential impact of these kinds of services on end-to-end application performance. We then present and analyze the performance of an active networking protocol that uses caching within the network backbone to reduce load on both servers and backbone routers.

This paper describes applications built on the ViewStation, a distributed multimedia system based on Unix workstations and a gigabit per second local area network. A key tenet of the ViewStation project is the delivery of media data not just to the desktop but all the way to the application program. As processing power continues to improve, our approach enables applications that perform intensive processing of audio and video data. We hypothesize that as media data are shaped by this software-based processing, the resultant network traffic patterns will be dominated more by software behavior than by so-called real-time issues. We have written applications that directly process live video to provide more responsive human-computer interaction. We have also developed applications to explore the potential of media processing to support content-based retrieval of prerecorded television broadcasts. These applications perform intelligent processing on video, as well as straightforward presentation. They demonstrate the utility of network-based multimedia systems that deliver audio and video data all the way to the application. The network requirements of the applications are modeled as a combination of bursty transfers and periodic packet-trains.>

In computer-participative multimedia applications, the computer not only manipulates media, but also digests it and performs independent actions based on media content. We present a design approach that applies the programming techniques of visualization systems to the development of computer-participative multimedia applications. We describe an implementation based on this approach, and report performance measurements that demonstrate it is practical. We conclude by describing three applications written with the system, and suggest future directions for research in the area.