When a root certificate authority (CA) in the Web PKI misbehaves, primary root-store operators such as Mozilla and Google respond by distrusting that CA. However, full distrust is often too broad, so root stores often implement partial distrust of roots, such as only accepting a root for a subset of domains. Unfortunately, derivative root stores (e.g., Debian and Android) that mirror decisions made by primary root stores are often out-of-date and cannot implement partial distrust, leaving TLS applications vulnerable.

Edna is a system that helps web applications allow users to remove their data without permanently losing their accounts, anonymize their old data, and selectively dissociate personal data from public profiles. Edna helps developers support these features while maintaining application functionality and referential integrity via disguising and revealing transformations. Disguising selectively renders user data inaccessible via encryption, and revealing enables the user to restore their data to the application. Edna's techniques allow transformations to compose in any order, e.g., deleting a previously anonymized user's account, or restoring an account back to an anonymized state.

Providing privacy in complex, data-rich applications is hard. Deleting accounts, anonymizing an account's contributions, and other privacy-related actions may require the traversal and transformation of interwoven state in a relational database. Finding the affected data is already nontrivial, but privacy actions must additionally balance competing requirements, such as preserving data trails for legal reasons or allowing users to change their mind. We believe a systematic shared framework for specifying and implementing privacy transformations could simplify and empower applications. Our prototype, data disguising, supports fine-grained, nuanced, and useful policies that would be cumbersome to implement manually, including reversible transformations that can compose.

Optimistic concurrency control, or OCC, can achieve excellent performance on uncontended workloads for main-memory transactional databases. Contention causes OCC's performance to degrade, however, and recent concurrency control designs, such as hybrid OCC/locking systems and variations on multiversion concurrency control (MVCC), have claimed to outperform the best OCC systems. We evaluate several concurrency control designs under varying contention and varying workloads, including TPCC, and find that implementation choices unrelated to concurrency control may explain much of OCC's previously-reported degradation. When these implementation choices are made sensibly, OCC performance does not collapse on high-contention TPC-C. We also present two optimization techniques, commit-time updates and timestamp splitting , that can dramatically improve the high-contention performance of both OCC and MVCC. Though these techniques are known, we apply them in a new context and highlight their potency: when combined, they lead to performance gains of 3.4X for MVCC and 3.6X for OCC in a TPC-C workload.

A multiverse database transparently presents each application user with a flexible, dynamic, and independent view of shared data. This transformed view of the entire database contains only information allowed by a centralized and easily-auditable privacy policy. By enforcing the privacy policy once, in the database, multiverse databases reduce programmer burden and eliminate many frontend bugs that expose sensitive data.

It is often possible to improve a concurrent system's performance by leveraging the semantics of its datatypes. We build a new software transactional memory (STM) around this observation. A conventional STM tracks read- and write-sets of memory words; even simple operations can generate large sets. Our STM, which we call STO, tracks abstract operations on transactional datatypes instead. Parts of the transactional commit protocol are delegated to these datatypes' implementations, which can use datatype semantics, and new commit protocol features, to reduce bookkeeping, limit false conflicts, and implement efficient concurrency control. We test these ideas on the STAMP benchmark suite for STM applications and on our own prior work, the Silo high-performance in-memory database, observing large performance improvements in both systems.

What opportunities for multicore scalability are latent in software interfaces, such as system call APIs? Can scalability challenges and opportunities be identified even before any implementation exists, simply by considering interface specifications? To answer these questions, we introduce the scalable commutativity rule: whenever interface operations commute, they can be implemented in a way that scales. This rule is useful throughout the development process for scalable multicore software, from the interface design through implementation, testing, and evaluation. This article formalizes the scalable commutativity rule. This requires defining a novel form of commutativity, SIM commutativity , that lets the rule apply even to complex and highly stateful software interfaces. We also introduce a suite of software development tools based on the rule. Our Commuter tool accepts high-level interface models, generates tests of interface operations that commute and hence could scale, and uses these tests to systematically evaluate the scalability of implementations. We apply Commuter to a model of 18 POSIX file and virtual memory system operations. Using the resulting 26,238 scalability tests, Commuter highlights Linux kernel problems previously observed to limit application scalability and identifies previously unknown bottlenecks that may be triggered by future workloads or hardware. Finally, we apply the scalable commutativity rule and Commuter to the design and implementation sv6, a new POSIX-like operating system. sv6’s novel file and virtual memory system designs enable it to scale for 99% of the tests generated by Commuter . These results translate to linear scalability on an 80-core x86 machine for applications built on sv6’s commutative operations.

What fundamental opportunities for scalability are latent in interfaces, such as system call APIs? Can scalability opportunities be identified even before any implementation exists, simply by considering interface specifications? To answer these questions this paper introduces the following rule: Whenever interface operations commute, they can be implemented in a way that scales. This rule aids developers in building more scalable software starting from interface design and carrying on through implementation, testing, and evaluation.

Silo is a new in-memory database that achieves excellent performance and scalability on modern multicore machines. Silo was designed from the ground up to use system memory and caches efficiently. For instance, it avoids all centralized contention points, including that of centralized transaction ID assignment. Silo's key contribution is a commit protocol based on optimistic concurrency control that provides serializability while avoiding all shared-memory writes for records that were only read. Though this might seem to complicate the enforcement of a serial order, correct logging and recovery is provided by linking periodically-updated epochs with the commit protocol. Silo provides the same guarantees as any serializable database without unnecessary scalability bottlenecks or much additional latency. Silo achieves almost 700,000 transactions per second on a standard TPC-C workload mix on a 32-core machine, as well as near-linear scalability. Considered per core, this is several times higher than previously reported results.

We present Masstree, a fast key-value database designed for SMP machines. Masstree keeps all data in memory. Its main data structure is a trie-like concatenation of B+-trees, each of which handles a fixed-length slice of a variable-length key. This structure effectively handles arbitrary-length possiblybinary keys, including keys with long shared prefixes. +-tree fanout was chosen to minimize total DRAM delay when descending the tree and prefetching each tree node. Lookups use optimistic concurrency control, a read-copy-update-like technique, and do not write shared data structures; updates lock only affected nodes. Logging and checkpointing provide consistency and durability. Though some of these ideas appear elsewhere, Masstree is the first to combine them. We discuss design variants and their consequences.

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

Soil contains vast ecosystems that play a key role in the Earth's water and nutrient cycles, but scientists cannot currently collect the high-resolution data required to fully understand them. In this paper, we present Suelo, an embedded networked sensing system designed for soil monitoring. An important challenge for Suelo is that many soil sensors are inherently fragile and often produce invalid or uncalibrated data. Therefore Suelo is an assisted sensing system: it actively requests the help of a human when necessary to validate, calibrate, repair, or replace sensors. This approach allows us to use available sensors without sacrificing data integrity, while minimizing the human resources required. We tested our system in multiple real soil monitoring deployments and demonstrate that, using human assistance, Suelo produced 91% fewer false negatives and false positives than common fault detection solutions on these datasets.

Databases have achieved orders-of-magnitude performance improvements by changing the layout of stored data -- for instance, by arranging data in columns or compressing it before storage. These improvements have been implemented in monolithic new engines, however, making it difficult to experiment with feature combinations or extensions. We present Anvil, a modular and extensible toolkit for building database back ends. Anvil's storage modules, called dTables, have much finer granularity than prior work. For example, some dTables specialize in writing data, while others provide optimized read-only formats. This specialization makes both kinds of dTable simple to write and understand. Unifying dTables implement more comprehensive functionality by layering over other dTables -- for instance, building a read/write store from read-only tables and a writable journal, or building a general-purpose store from optimized special-purpose stores. The dTable design leads to a flexible system powerful enough to implement many database storage layouts. Our prototype implementation of Anvil performs up to 5.5 times faster than an existing B-tree-based database back end on conventional workloads, and can easily be customized for further gains on specific data and workloads.

This tutorial presents a detailed study of sensor faults that occur in deployed sensor networks and a systematic approach to model these faults. We begin by reviewing the fault detection literature for sensor networks. We draw from current literature, our own experience, and data collected from scientific deployments to develop a set of commonly used features useful in detecting and diagnosing sensor faults. We use this feature set to systematically define commonly observed faults, and provide examples of each of these faults from sensor data collected at recent deployments.

Today's system programmers go to great lengths to extend the languages in which they program. For instance, system-specific compilers find errors in Linux and other systems, and add support for specialized control flow to Qt and event-based programs. These compilers are difficult to build and cannot always understand each other's language changes. However, they can greatly improve code understandability and correctness, advantages that should be accessible to all programmers.

The continuing frequency and seriousness of security incidents underline the critical importance of application security. Decentralized information flow control (DIFC), a promising tool for improving application security, gives application developers fine-grained control over security policy and privilege management. DIFC developers can partition much application functionality into untrusted components bound by a kernel- or language-enforced security policy. Unless a (usually smaller and less exposed) trusted component is exploited, the effects of an application compromise are contained by the policy.

Abstract This paper assesses BitTorrent's robustness against selfish peers who try to download content faster than their fair share by abusing existing protocol mechanisms. We present three exploits that can deliver potential benefits to a selfish peer and evaluate their impact on both public and private download sessions. Our results show that BitTorrent is quite robust against these exploits. Although selfish peers can sometimes attain high download throughput and compliant peers' download rates suffer slightly in consequence, we observe no significant degradation of the overall system's quality of service. We identify scenarios where a selfish peer could attain significant benefits at the expense of compliant peers, and discuss the protocol characteristics that render these scenarios unlikely and hence lead to the system's robustness. Copyright © 2007 John Wiley & Sons, Ltd.

Many embedded systems contain resource constrained microcontrollers where applications, operating system components and device drivers reside within a single address space with no form of memory protection. Programming errors in one application can easily corrupt the state of the operating system and other applications on the microcontroller. In this paper we propose a system that provides memory protection in tiny embedded processors. Our system consists of a software run-time working with minimal low-cost architectural extensions to the processor core that prevents corruption of state by buggy applications. We restrict memory accesses and control flow of applications to protection domains within the address space. The software run-time consists of a Memory map: a flexible and efficient data structure that records ownership and layout information of the entire address space. Memory map checks are done for store instructions by hardware accelerators that significantly improve the performance of our system. We preserve control flow integrity by maintaining a Safe stack that stores return addresses in a protected memory region. Cross domain function calls are redirected through a software based jump table. Enhancements to the microcontroller call and return instructions use the jump table to track the current active domain. We have implemented our scheme on a VHDL model of ATMEGA103 microcontroller. Our evaluations show that embedded applications can enjoy the benefits of memory protection with minimal impact on performance and a modest increase in the area of the microcontroller.

Many sensor nodes contain resource constrained microcontrollers where user level applications, operating system components, and device drivers share a single address space with no form of hardware memory protection. Programming errors in one application can easily corrupt the state of the operating system or other applications. In this paper, we propose Harbor, a memory protection system that prevents many forms of memory corruption. We use software based fault isolation ("sandboxing") to restrict application memory accesses and control flow to protection domains within the address space. A flexible and efficient memory map data structure records ownership and layout information for memory regions; writes are validated using the memory map. Control flow integrity is preserved by maintaining a safe stack that stores return addresses in a protected memory region. Run-time checks validate computed control flow instructions. Cross domain calls perform low-overhead control transfers between domains. Checks are introduced by rewriting an application's compiled binary. The sand-boxed result is verified on the sensor node before it is admitted for execution. Harbor's fault isolation properties depend only on the correctness of this verifier and the Harbor runtime. We have implemented and tested Harbor on the SOS operating system. Harbor detected and prevented memory corruption caused by programming errors in application modules that had been in use for several months. Harbor's overhead, though high, is less than that of application-specific virtual machines, and reasonable for typical sensor workloads.

Peer-to-peer protocols play an increasingly instrumental role in Internet content distribution. It is therefore important to gain a complete understanding of how these protocols behave in practice and how their operating parameters affect overall system performance. This paper presents the first detailed experimental investigation of the peer selection strategy in the popular BitTorrent protocol. By observing more than 40 nodes in instrumented private torrents, we validate three protocol properties that, though believed to hold, have not been previously demonstrated experimentally: the clustering of similar-bandwidth peers, the effectiveness of BitTorrent's sharing incentives, and the peers' high uplink utilization. In addition, we observe that BitTorrent's modified choking algorithmin seed state provides uniform service to all peers, and that an underprovisioned initial seed leads to absence of peer clustering and less effective sharing incentives. Based on our results, we provide guidelines for seed provisioning by content providers, and discuss a tracker protocol extension that addresses an identified limitation of the protocol.

Reliable storage systems depend in part on “write-before” relationships where some changes to stable storage are delayed until other changes commit. A journaled file system, for example, must commit a journal transaction before applying that transaction’s changes, and soft updates [9] and other consistency enforcement mechanisms have similar constraints, implemented in each case in systemdependent ways. We present a general abstraction, the patch, that makes write-before relationships explicit and file system agnostic. A patch-based file system implementation expresses dependencies among writes, leaving lower system layers to determine write orders that satisfy those dependencies. Storage system modules can examine and modify the dependency structure, and generalized file system dependencies are naturally exportable to user level. Our patch-based storage system, Featherstitch, includes several important optimizations that reduce patch overheads by orders of magnitude. Our ext2 prototype runs in the Linux kernel and supports asynchronous writes, soft updates-like dependencies, and journaling. It outperforms similarly reliable ext2 and ext3 configurations on some, but not all, benchmarks. It also supports unusual configurations, such as correct dependency enforcement within a loopback file system, and lets applications define consistency requirements without micromanaging how those requirements are satisfied.

Decentralized Information Flow Control (DIFC) [24] is an ap-proach to security that allows application writers to control how data flows between the pieces of an application and the outside world. As applied to privacy, DIFC allows untrusted software to compute with private data while trusted security code controls the release of that data. As applied to integrity, DIFC allows trusted code to protect untrusted software from unexpected malicious in-puts. In either case, only bugs in the trusted code, which tends to be small and isolated, can lead to security violations. We present Flume, a new DIFC model and system that applies at the granularity of operating system processes and standard OS ab-stractions (e.g., pipes and file descriptors). Flume eases DIFC’s use in existing applications and allows safe interaction between con-ventional and DIFC-aware processes. Flume runs as a user-level reference monitor on Linux. A process confined by Flume cannot perform most system calls directly; instead, an interposition layer replaces system calls with IPC to the reference monitor, which en-forces data flow policies and performs safe operations on the pro-cess’s behalf. We ported a complex Web application (MoinMoin wiki) to Flume, changing only 2 % of the original code. The Flume version is roughly 30–40 % slower due to overheads in our current implementation but supports additional security policies impossible without DIFC.

Asbestos, a new operating system, provides novel labeling and isolation mechanisms that help contain the effects of exploitable software flaws. Applications can express a wide range of policies with Asbestos's kernel-enforced labels, including controls on interprocess communication and system-wide information flow. A new event process abstraction defines lightweight, isolated contexts within a single process, allowing one process to act on behalf of multiple users while preventing it from leaking any single user's data to others. A Web server demonstration application uses these primitives to isolate private user data. Since the untrusted workers that respond to client requests are constrained by labels, exploited workers cannot directly expose user data except as allowed by application policy. The server application requires 1.4 memory pages per user for up to 145,000 users and achieves connection rates similar to Apache, demonstrating that additional security can come at an acceptable cost.

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.

Small-form-factor, low-power wireless sensors—motes—are convenient to deploy, but lack the bandwidth to capture and transmit raw high-frequency data, such as human voices or neural signals, in real time. Local filtering can help, but we show that the right filter settings depend on changing ambient conditions and network effects such as congestion, which makes them dynamic and unpredictable. Mote collection systems for high-frequency data must support iteratively-tuned, deployment-specific filter settings as well as fast sampling.VANGO, our software system for high-frequency data collection, achieves these goals via integrated processing across network tiers. Bandwidth-limited sensor nodes reduce data in network but rely on microservers, which have greater computational capabilities and a wider scope of observation, to plan how. VANGO provides a cross-platform library for data transformation, measurement, and classification; a fast and low-jitter data acquisition system for motes; and a mechanism to control mote and microserver signal processing. With VANGO we have developed new applications: the first acoustic collection system for motes responsive to changing environmental conditions and user interests, and the first neural spike acquisition application capable of supporting a network of nodes.

Fast-growing Internet applications like streaming media and telephony prefer timeliness to reliability, making TCP a poor fit. Unfortunately, UDP, the natural alternative, lacks congestion control. High-bandwidth UDP applications must implement congestion control themselves-a difficult task-or risk rendering congested networks unusable. We set out to ease the safe deployment of these applications by designing a congestion-controlled unreliable transport protocol. The outcome, the Datagram Congestion Control Protocol or DCCP, adds to a UDP-like foundation the minimum mechanisms necessary to support congestion control. We thought those mechanisms would resemble TCP's, but without reliability and, especially, cumulative acknowledgements, we had to reconsider almost every aspect of TCP's design. The resulting protocol sheds light on how congestion control interacts with unreliable transport, how modern network constraints impact protocol design, and how TCP's reliable bytestream semantics intertwine with its other mechanisms, including congestion control.

Sensor network nodes exhibit characteristics of both embedded systems and general-purpose systems. They must use little energy and be robust to environmental conditions, while also providing common services that make it easy to write applications. In TinyOS, the current state of the art in sensor node operating systems, reusable components implement common services, but each node runs a single statically-linked system image, making it hard to run multiple applications or incrementally update applications. We present SOS, a new operating system for mote-class sensor nodes that takes a more dynamic point on the design spectrum. SOS consists of dynamically-loaded modules and a common kernel, which implements messaging, dynamic memory, and module loading and unloading, among other services. Modules are not processes: they are scheduled cooperatively and there is no memory protection. Nevertheless, the system protects against common module bugs using techniques such as typed entry points, watchdog timers, and primitive resource garbage collection. Individual modules can be added and removed with minimal system interruption. We describe SOS's design and implementation, discuss tradeoffs, and compare it with TinyOS and with the Maté virtual machine. Our evaluation shows that despite the dynamic nature of SOS and its higher-level kernel interface, its long term total usage nearly identical to that of systems such as Matè and TinyOS.

Being embedded in the physical world, sensor networks present a wide range of bugs and misbehavior qualitatively different from those in most distributed systems. Unfortunately, due to resource constraints, programmers must investigate these bugs with only limited visibility into the application. This paper presents the design and evaluation of Sympathy, a tool for detecting and debugging failures in sensor networks. Sympathy has selected metrics that enable efficient failure detection, and includes an algorithm that root-causes failures and localizes their sources in order to reduce overall failure notifications and point the user to a small number of probable causes. We describe Sympathy and evaluate its performance through fault injection and by debugging an active application, ESS, in simulation and deployment. We show that for a broad class of data gathering applications, it is possible to detect and diagnose failures by collecting and analyzing a minimal set of metrics at a centralized sink. We have found that there is a tradeoff between notification latency and detection accuracy; that additional metrics traffic does not always improve notification latency; and that Sympathy's process of failure localization reduces.

No abstract available.

Asbestos, a new prototype operating system, provides novel labeling and isolation mechanisms that help contain the effects of exploitable software flaws. Applications can express a wide range of policies with Asbestos's kernel-enforced label mechanism, including controls on inter-process communication and system-wide information flow. A new event process abstraction provides lightweight, isolated contexts within a single process, allowing the same process to act on behalf of multiple users while preventing it from leaking any single user's data to any other user. A Web server that uses Asbestos labels to isolate user data requires about 1.5 memory pages per user, demonstrating that additional security can come at an acceptable cost.

For robustness, stability, and reboot speed, file system implementations must ensure that the file system's stored image is kept consistent or easy to return to consistency. Advanced consistency mechanisms such as soft updates [2] and journalling make this possible; unfortunately, they are generally tied to a particular file system, and can't be ported or adapted without significant engineering effort. Furthermore, interfaces like fsync () give user code only coarse control over consistency. Applications with custom consistency and performance requirements get little help from conventional file systems, which either impose high overhead (data journalling) or don't guarantee data consistency (soft updates, for example, ensures metadata consistency only).

multiQ is a passive capacity measurement tool suitable for large-scale studies of Internet path characteristics. It is the first passive tool that discovers the capacity of multiple congested links along a path from a single flow trace, and the first tool that effectively extracts capacity information from ack-only traces. It uses equally-spaced mode gaps in TCP flows' packet interarrival time distributions to detect multiple bottleneck capacities in their relative order.We validate multiQ in depth using the RON overlay network, which provides more than 400 heterogeneous, well-understood Internet paths. We compare multiQ with two other capacity measurement tools (Nettimer and Pathrate) in the first large-scale wide-area evaluation of capacity measurement techniques, and find that multiQ is highly accurate; for instance, though multiQ is passive, it achieves the same accuracy as Pathrate, which is active.

We study four distributed techniques for computing the area of a region in a sensor network. Area calculation is a fundamental sensor network primitive, and distributed, in-network approaches prove more scalable than centralized collection in terms of energy consumption. The four techniques - Delaunay triangulations, Voronoi diagrams, and two new, simpler algorithms, inverse neighborhood and inverse neighborhood with location - vary in computational complexity, communication cost, and information required from the sensor network. We conclude that when sensors know their physical locations, our simple and efficient inverse-neighborhood approach performs comparably to more systematic, but more expensive, computational geometry algorithms. We also analyze the effects of radio range and deployment density on accuracy, and show that topologies derived from real testbeds behave quite differently from commonly seen random topologies with unit disk connectivity.

This work presents a preliminary design and evaluation of Sympathy, a debugging tool for pre-deployment sensor networks. Sympathy consists of mechanisms for collecting system performance metrics with minimal memory overhead; mechanisms for recognizing events based on these metrics; and a system for collecting events and their spatio-temporal context. Sympathy introduces the idea of correlating seemingly unrelated events, and providing context for these events, in order to track down bugs and find their root causes. Eventually, Sympathy will be part of a system that can aid in debugging sensor networks both pre- and post-deployment.

We propose a new configuration language, component and service library, and compiler that make it easier to develop efficient sensor network applications. Our goal is the construction of smart application service libraries: high-level libraries that implement concepts like routing trees and periodic sensing, and that combine automatically into efficient programs. Important language features include flexible control over component sharing and transitive arrow connections, which let independently-implemented services knit themselves into integrated control flow paths. Our language, library, and compiler are collectively called SNACK (Sensor Network Application Construction Kit). We describe them, and present and evaluate a simple SNACK-based multihop data collection application. This application uses SNACK language features to provide both simplicity (excluding reusable service definitions, its description is three lines long) and efficiency (it performs comparably to the well-known Surge application).

Networking systems such as Ensemble, the x-kernel, Scout, and Click achieve flexibility by building routers and other packet processors from modular components. Unfortunately, component designs are often slower than purpose-built code, and routers in particular have stringent efficiency requirements. This paper addresses the efficiency problems of one component-based router, Click, through optimization tools inspired in part by compiler optimization passes. This pragmatic approach can result in significant performance improvements; for example, the combination of three optimizations reduces the amount of CPU time Click requires to process a packet in a simple IP router by 34%. We present several optimization tools, describe how those tools affected the design of Click itself, and present detailed evaluations of Click's performance with and without optimization.

This paper investigates the structure of addresses contained in IP traffic. Specifically, we analyze the structural characteristics of destination IP addresses seen on Interuet links, considered as a subset of the address space. These characteristics may have implications for algorithms that deal with IP address aggregates, such as routing lookups and aggregatebased congestion control. We find that address structures are well modeled by a multifractal Cantor dust with two parameters. The model may be useful for simulations where realistic IP addresses are preferred. We also develop concise characterizations of address structures, including active aggregate counts and discriminating prefixes. Our structural characterizations are stable over short time scales at a given site, and different sites have visibly different characterizations, so that the characterizations make useful fingerprints of the traffic seen at a site. Also, changing traffic conditions, such as worm propagation, significantly alter these fingerprints.

Clicks is a new software architecture for building flexible and configurable routers. A Click router is assembled from packet processing modules called elements . Individual elements implement simple router functions like packet classification, queuing, scheduling, and interfacing with network devices. A router configurable is a directed graph with elements at the vertices; packets flow along the edges of the graph. Several features make individual elements more powerful and complex configurations easier to write, including pull connections, which model packet flow drivn by transmitting hardware devices, and flow-based router context, which helps an element locate other interesting elements. Click configurations are modular and easy to extend. A standards-compliant Click IP router has 16 elements on its forwarding path; some of its elements are also useful in Ethernet switches and IP tunnelling configurations. Extending the IP router to support dropping policies, fairness among flows, or Differentiated Services simply requires adding a couple of element at the right place. On conventional PC hardware, the Click IP router achieves a maximum loss-free forwarding rate of 333,000 64-byte packets per second, demonstrating that Click's modular and flexible architecture is compatible with good performance.

Prolac is a new statically-typed, object-oriented language for network protocol implementation. It is designed for readability, extensibility, and real-world implementation; most previous protocol languages, in contrast, have been based on hard-to-implement theoretical models and have focused on verification. We present a working Prolac TCP implementation directly derived from 4.4BSD. Our implementation is modular---protocol processing is logically divided into minimally-interacting pieces; readable---Prolac encourages top-down structure and naming intermediate computations; and extensible---subclassing cleanly separates protocol extensions like delayed acknowledgements and slow start. The Prolac compiler uses simple global analysis to remove expensive language features like dynamic dispatch, resulting in end-to-end performance comparable to an unmodified Linux 2.0 TCP. 1 INTRODUCTION Most familiar programming idioms handle network protocols badly---even modern languages are stressed...

Click is a new software architecture for building flexible and configurable routers. A Click router is assembled from packet processing modules called elements. Individual elements implement simple router functions like packet classification, queueing, scheduling, and interfacing with network devices. Complete configurations are built by connecting elements into a graph; packets flow along the graph's edges. Several features make individual elements more powerful and complex configurations easier to write, including pull processing, which models packet flow driven by transmitting interfaces, and flow-based router context, which helps an element locate other interesting elements.We demonstrate several working configurations, including an IP router and an Ethernet bridge. These configurations are modular---the IP router has 16 elements on the forwarding path---and easy to extend by adding additional elements, which we demonstrate with augmented configurations. On commodity PC hardware running Linux, the Click IP router can forward 64-byte packets at 73,000 packets per second, just 10% slower than Linux alone.