Achieving high-performance when developing specialized hardware/software systems requires understanding and improving not only core compute kernels, but also intricate and elusive system-level bottlenecks. Profiling these bottlenecks requires both high-fidelity introspection and the ability to run sufficiently many cycles to execute complex software stacks, a challenging combination. In this work, we enable agile full-system performance optimization for hardware/software systems with FirePerf, a set of novel out-of-band system-level performance profiling capabilities integrated into the open-source FireSim FPGA-accelerated hardware simulation platform. Using out-of-band call stack reconstruction and automatic performance counter insertion, FirePerf enables introspecting into hardware and software at appropriate abstraction levels to rapidly identify opportunities for software optimization and hardware specialization, without disrupting end-to-end system behavior like traditional profiling tools. We demonstrate the capabilities of FirePerf with a case study that optimizes the hardware/software stack of an open-source RISC-V SoC with an Ethernet NIC to achieve 8x end-to-end improvement in achievable bandwidth for networking applications running on Linux. We also deploy a RISC-V Linux kernel optimization discovered with FirePerf on commercial RISC-V silicon, resulting in up to 1.72x improvement in network performance.

Machine learning (ML) workflows are extremely complex. The typical workflow consists of distinct stages of user interaction, such as preprocessing, training, and tuning, that are repeatedly executed by users but have heterogeneous computational requirements. This complexity makes it challenging for ML users to correctly provision and manage resources and, in practice, constitutes a significant burden that frequently causes over-provisioning and impairs user productivity. Serverless computing is a compelling model to address the resource management problem, in general, but there are numerous challenges to adopt it for existing ML frameworks due to significant restrictions on local resources.

We present FireSim, an open-source simulation platform that enables cycle-exact microarchitectural simulation of large scale-out clusters by combining FPGA-accelerated simulation of silicon-proven RTL designs with a scalable, distributed network simulation. Unlike prior FPGA-accelerated simulation tools, FireSim runs on Amazon EC2 F1, a public cloud FPGA platform, which greatly improves usability, provides elasticity, and lowers the cost of large-scale FPGA-based experiments. We describe the design and implementation of FireSim and show how it can provide sufficient performance to run modern applications at scale, to enable true hardware-software co-design. As an example, we demonstrate automatically generating and deploying a target cluster of 1,024 3.2 GHz quad-core server nodes, each with 16 GB of DRAM, interconnected by a 200 Gbit/s network with 2 microsecond latency, which simulates at a 3.4 MHz processor clock rate (less than 1,000x slowdown over real-time). In aggregate, this FireSim instantiation simulates 4,096 cores and 16 TB of memory, runs ~14 billion instructions per second, and harnesses 12.8 million dollars worth of FPGAs—at a total cost of only ~$100 per simulation hour to the user. We present several examples to show how FireSim can be used to explore various research directions in warehouse-scale machine design, including modeling networks with high-bandwidth and low-latency, integrating arbitrary RTL designs for a variety of commodity and specialized datacenter nodes, and modeling a variety of datacenter organizations, as well as reusing the scale-out FireSim infrastructure to enable fast, massively parallel cycle-exact single-node microarchitectural experimentation.

This paper presents MARVEL, a mobile augmented reality (MAR) system which provides a notation display service with imperceptible latency (<100 ms) and low energy consumption on regular mobile devices. In contrast to conventional MAR systems, which recognize objects using image-based computations performed in the cloud, MARVEL mainly utilizes a mobile device's local inertial sensors for recognizing and tracking multiple objects, while computing local optical flow and offloading images only when necessary. We propose a system architecture which uses local inertial tracking, local optical flow, and visual tracking in the cloud synergistically. On top of that, we investigate how to minimize the overhead for image computation and offloading. We have implemented and deployed a holistic prototype system in a commercial building and evaluate MARVEL's performance. The efficient use of a mobile device's capabilities lowers latency and energy consumption without sacrificing accuracy.

Operating systems and applications in the built environment have relied upon central authorization and management mechanisms that restrict their scalability, especially with respect to administrative overhead. We propose a new set of primitives encompassing syndication, security, and service execution that unifies the management of applications and services across the built environment, while enabling participants to individually delegate privilege across multiple administrative domains with no loss of security or manageability. We show how to leverage a decentralized authorization syndication platform to extend the design of building operating systems beyond the single administrative domain of a building. The authorization system leveraged is based on blockchain smart contracts to permit decentralized and democratized delegation of authorization without central trust. Upon this, a publish/subscribe syndication tier and a containerized service execution environment are constructed. Combined, these mechanisms solve problems of delegation, federation, device protection and service execution that arise throughout the built environment. We leverage a high-fidelity city-scale emulation to verify the scalability of the authorization tier, and briefly describe a prototypical democratized operating system for the built environment using this foundation. This is an extension of work presented in Ref. [3].

Users of cloud services are presented with a bewildering choice of VM types and the choice of VM can have significant implications on performance and cost. In this paper we address the fundamental problem of accurately and economically choosing the best VM for a given workload and user goals. To address the problem of optimal VM selection, we present PARIS, a data-driven system that uses a novel hybrid offline and online data collection and modeling framework to provide accurate performance estimates with minimal data collection. PARIS is able to predict workload performance for different user-specified metrics, and resulting costs for a wide range of VM types and workloads across multiple cloud providers. When compared to sophisticated baselines, including collaborative filtering and a linear interpolation model using measured workload performance on two VM types, PARIS produces significantly better estimates of performance. For instance, it reduces runtime prediction error by a factor of 4 for some workloads on both AWS and Azure. The increased accuracy translates into a 45% reduction in user cost while maintaining performance.

Parallel processing frameworks (Dean and Ghemawat, 2004) accelerate jobs by breaking them into tasks that execute in parallel. However, slow running or straggler tasks can run up to 8 times slower than the median task on a production cluster (Ananthanarayanan et al., 2013), leading to delayed job completion and inefficient use of resources. Existing straggler mitigation techniques wait to detect stragglers and then relaunch them, delaying straggler detection and wasting resources. We built Wrangler (Yadwadkar et al., 2014), a system that predicts when stragglers are going to occur and makes scheduling decisions to avoid such situations. To capture node and workload variability, Wrangler built separate models for every node and workload, requiring the time-consuming collection of substantial training data. In this paper, we propose multi- task learning formulations that share information between the various models, allowing us to use less training data and bring training time down from 4 hours to 40 minutes. Unlike naive multi-task learning formulations, our formulations capture the shared structure in our data, improving generalization performance on limited data. Finally, we extend these formulations using group sparsity inducing norms to automatically discover the similarities between tasks and improve interpretability.

The drive towards richer and more interactive web content places increasingly stringent requirements on datacenter network performance. Applications running atop these networks typically partition an incoming query into multiple subqueries, and generate the final result by aggregating the responses for these subqueries. As a result, a large fraction --- as high as 80% --- of the network flows in such workloads are short and latency-sensitive. The speed with which existing networks respond to packet drops limits their ability to meet high-percentile flow completion time SLOs. Indirect notifications indicating packet drops (e.g., duplicates in an end-to-end acknowledgement sequence) are an important limitation to the agility of response to packet drops.

Slow running or straggler tasks in distributed processing frameworks [1, 2] can be 6 to 8 times slower than the median task in a job on a production cluster [3], despite existing mitigation techniques. This leads to extended job completion times, inefficient use of resources, and increased costs. Recently, proactive straggler avoidance techniques [4] have explored the use of predictive models to improve task scheduling. However, to capture node and workload variability, separate models are built for every node and workload, requiring the time consuming collection of training data and limiting the applicability to new nodes and workloads. In this work, we observe that predictors for similar nodes or workloads are likely to be similar and can share information, suggesting a multi-task learning (MTL) based approach. We generalize the MTL formulation of [5] to capture commonalities in arbitrary groups. Using our formulation to predict stragglers allows us to reduce job completion times by up to 59% over Wrangler [4]. This large reduction arises from a 7 point increase in prediction accuracy. Further, we can get equal or better accuracy than [4] using a sixth of the training data, thus bringing the training time down from 4 hours to about 40 minutes. In addition, our formulation reduces the number of parameters by grouping our parameters into node- and workload-dependent factors. This helps us generalize to tasks with insufficient data and achieve significant gains over a naive MTL formulation [5].

Straggler tasks continue to be a major hurdle in achieving faster completion of data intensive applications running on modern data-processing frameworks. Existing straggler mitigation techniques are inefficient due to their reactive and replicative nature -- they rely on a wait-speculate-re-execute mechanism, thus leading to delayed straggler detection and inefficient resource utilization. Existing proactive techniques also over-utilize resources due to replication. Existing modeling-based approaches are hard to rely on for production-level adoption due to modeling errors. We present Wrangler, a system that proactively avoids situations that cause stragglers. Wrangler automatically learns to predict such situations using a statistical learning technique based on cluster resource utilization counters. Furthermore, Wrangler introduces a notion of a confidence measure with these predictions to overcome the modeling error problems; this confidence measure is then exploited to achieve a reliable task scheduling. In particular, by using these predictions to balance delay in task scheduling against the potential for idling of resources, Wrangler achieves a speed up in the overall job completion time. For production-level workloads from Facebook and Cloudera's customers, Wrangler improves the 99th percentile job completion time by up to 61% as compared to speculative execution, a widely used straggler mitigation technique. Moreover, Wrangler achieves this speed-up while significantly improving the resource consumption (by up to 55%).

The great French writer, historian and philosopher Voltaire once asked, "Is there anyone so wise as to learn by the experience of others?" In celebration of the 20th MobiCom conference, join us for a thought provoking discussion between pioneers of our field on the lessons they have learned over their illustrious career paths that accelerated the pace of technology adoption and enabled world-wide societal impact. Learn from our heroes as they share with us gems of wisdom on how to choose a great problem, what to avoid and how to be successful as you build your own remarkable careers.

Mobile computing has deeply influenced the lives of almost every human in the world on a daily basis. In celebration of the 20th anniversary of Mobicom, Mobicom 2014 features an exciting panel on the topic of tackling societal grand challenges using mobile computing. The panel features five excellent researchers who have had a tremendous impact on the field of mobile computing over the years and whose research work has directly addressed pressing societal problems. The panel discussion will feature an in-depth discussion of the grand challenges that we face in society today and the role of mobile computing as a frontier platform for addressing these challenges. The panel will cover both a retrospective and futuristic perspective where the retrospective aspects highlight the diverse contributions of the panelists and the futuristic aspects will feature of a discussion of their individual views of what are the next big societal problems that Mobicom as a community should tackle.

MapReduce was designed by Google for large-scale data analysis on slow but cheap disk-based storage. Nevertheless, memory has declined in price to where cost-effective machines offer ever larger memory capacity. Furthermore, a more diverse data analyst community, with smaller datasets, has emerged. These trends motivate new parallel processing frameworks, like Spark [2], with better support for in-memory data analysis.

We describe our experiences teaching MapReduce in a large undergraduate lecture course using public cloud services and the standard Hadoop API. Using the standard API, students directly experienced the quality of industrial big-data tools. Using the cloud, every student could carry out scalability benchmarking assignments on realistic hardware, which would have been impossible otherwise. Over two semesters, over 500 students took our course. We believe this is the first large-scale demonstration that it is feasible to use pay-as-you-go billing in the cloud for a large undergraduate course. Modest instructor effort was sufficient to prevent students from overspending. Average per-pupil expenses in the Cloud were under $45. Students were excited by the assignment: 90% said they thought it should be retained in future course offerings.

To better understand the challenges in developing effective cloud-based resource schedulers, we analyze the first publicly available trace data from a sizable multi-purpose cluster. The most notable workload characteristic is heterogeneity: in resource types (e.g., cores:RAM per machine) and their usage (e.g., duration and resources needed). Such heterogeneity reduces the effectiveness of traditional slot- and core-based scheduling. Furthermore, some tasks are constrained as to the kind of machine types they can use, increasing the complexity of resource assignment and complicating task migration. The workload is also highly dynamic, varying over time and most workload features, and is driven by many short jobs that demand quick scheduling decisions. While few simplifying assumptions apply, we find that many longer-running jobs have relatively stable resource utilizations, which can help adaptive resource schedulers.

Cake is a coordinated, multi-resource scheduler for shared distributed storage environments with the goal of achieving both high throughput and bounded latency. Cake uses a two-level scheduling scheme to enforce high-level service-level objectives (SLOs). First-level schedulers control consumption of resources such as disk and CPU. These schedulers (1) provide mechanisms for differentiated scheduling, (2) split large requests into smaller chunks, and (3) limit the number of outstanding device requests, which together allow for effective control over multi-resource consumption within the storage system. Cake's second-level scheduler coordinates the first-level schedulers to map high-level SLO requirements into actual scheduling parameters. These parameters are dynamically adjusted over time to enforce high-level performance specifications for changing workloads. We evaluate Cake using multiple workloads derived from real-world traces. Our results show that Cake allows application programmers to explore the latency vs. throughput trade-off by setting different high-level performance requirements on their workloads. Furthermore, we show that using Cake has concrete economic and business advantages, reducing provisioning costs by up to 50% for a consolidated workload and reducing the completion time of an analytics cycle by up to 40%.

MapReduce workloads have evolved to include increasing amounts of time-sensitive, interactive data analysis; we refer to such workloads as MapReduce with Interactive Analysis (MIA). Such workloads run on large clusters, whose size and cost make energy efficiency a critical concern. Prior works on MapReduce energy efficiency have not yet considered this workload class. Increasing hardware utilization helps improve efficiency, but is challenging to achieve for MIA workloads. These concerns lead us to develop BEEMR (Berkeley Energy Efficient MapReduce), an energy efficient MapReduce workload manager motivated by empirical analysis of real-life MIA traces at Facebook. The key insight is that although MIA clusters host huge data volumes, the interactive jobs operate on a small fraction of the data, and thus can be served by a small pool of dedicated machines; the less time-sensitive jobs can run on the rest of the cluster in a batch fashion. BEEMR achieves 40-50% energy savings under tight design constraints, and represents a first step towards improving energy efficiency for an increasingly important class of datacenter workloads.

Web applications have now become so sophisticated that rendering a typical page may require hundreds of intra-datacenter flows. At the same time, web sites must meet strict page creation deadlines of 200-300ms to satisfy user demands for interactivity. Long-tailed flow completion times make it challenging for web sites to meet these constraints. They are forced to choose between rendering a subset of the complex page, or delay its rendering, thus missing deadlines and sacrificing either quality or responsiveness. Either option leads to potential financial loss.

We describe our experiences teaching MapReduce in a large undergraduate lecture course using public cloud services. Using the cloud, every student could carry out scalability benchmarking assignments on realistic hardware, which would have been impossible otherwise. Over two semesters, over 500 students took our course. We believe this is the first large-scale demonstration that it is feasible to use pay-as-you-go billing in the Cloud for a large undergraduate course. Modest instructor effort was sufficient to prevent students from overspending. Average per-pupil expenses in the Cloud were under $45, less than half our available grant funding. Students were excited by the assignment: 90% said they thought it should be retained in future course offerings.

Within the past few years, organizations in diverse industries have adopted MapReduce-based systems for large-scale data processing. Along with these new users, important new workloads have emerged which feature many small, short, and increasingly interactive jobs in addition to the large, long-running batch jobs for which MapReduce was originally designed. As interactive, large-scale query processing is a strength of the RDBMS community, it is important that lessons from that field be carried over and applied where possible in this new domain. However, these new workloads have not yet been described in the literature. We fill this gap with an empirical analysis of MapReduce traces from six separate business-critical deployments inside Facebook and at Cloudera customers in e-commerce, telecommunications, media, and retail. Our key contribution is a characterization of new MapReduce workloads which are driven in part by interactive analysis, and which make heavy use of query-like programming frameworks on top of MapReduce. These workloads display diverse behaviors which invalidate prior assumptions about MapReduce such as uniform data access, regular diurnal patterns, and prevalence of large jobs. A secondary contribution is a first step towards creating a TPC-like data processing benchmark for MapReduce.

Many programs use a key-value model for configuration options. We examined how this model is used in seven open source Java projects totaling over a million lines of code. We present a static analysis that extracts a list of configuration options for a program. Our analysis finds 95% of the options read by the programs in our sample, making it more complete than existing documentation.

Complex software packages, particularly systems software, often require substantial customization before being used. Small mistakes in configuration can lead to hard-todiagnose error messages. We demonstrate how to build a map from each program point to the options that might cause an error at that point. This can aid users in troubleshooting these errors without any need to install or use additional tools. Our approach relies on static dataflow analysis, meaning all the analysis is done in advance. We evaluate our work in detail on two substantial systems, Hadoop and the JChord program analysis toolkit, using failure injection and also by using log messages as a source of labeled program points. When logs and stack traces are available, they can be incorporated into the analysis. This reduces the number of false positives by nearly a factor of four for Hadoop, at the cost of approximately one minute's work per unique query.

MapReduce systems face enormous challenges due to increasing growth, diversity, and consolidation of the data and computation involved. Provisioning, configuring, and managing large-scale MapReduce clusters require realistic, workload-specific performance insights that existing MapReduce benchmarks are ill-equipped to supply. In this paper, we build the case for going beyond benchmarks for MapReduce performance evaluations. We analyze and compare two production MapReduce traces to develop a vocabulary for describing MapReduce workloads. We show that existing benchmarks fail to capture rich workload characteristics observed in traces, and propose a framework to synthesize and execute representative workloads. We demonstrate that performance evaluations using realistic workloads gives cluster operator new ways to identify workload-specific resource bottlenecks, and workload-specific choice of MapReduce task schedulers. We expect that once available, workload suites would allow cluster operators to accomplish previously challenging tasks beyond what we can now imagine, thus serving as a useful tool to help design and manage MapReduce systems.

Enterprise storage systems are facing enormous challenges due to increasing growth and heterogeneity of the data stored. Designing future storage systems requires comprehensive insights that existing trace analysis methods are ill-equipped to supply. In this paper, we seek to provide such insights by using a new methodology that leverages an objective, multi-dimensional statistical technique to extract data access patterns from network storage system traces. We apply our method on two large-scale real-world production network storage system traces to obtain comprehensive access patterns and design insights at user, application, file, and directory levels. We derive simple, easily implementable, threshold-based design optimizations that enable efficient data placement and capacity optimization strategies for servers, consolidation policies for clients, and improved caching performance for both.

The nine papers in this special issue focus on recent advances in autonomic communications. This issue addresses four areas in which autonomics play a central role: network architectures, traffic management, monitoring, and resource management.

In this paper we describe the Internet-in-a-Box datacenter network emulator, an FPGA-based tool for researchers to rapidly experiment with O(10,000) node datacenter network architectures. Our basic approach to emulation involves constructing a model of the target architecture by composing simplified hardware models of key datacenter building blocks, including switches, routers, links, and servers. Since models in our system are implemented in programmable hardware, designers have full control over emulated buffer sizes, line rates, topologies, and many other network properties. Full system control also gives researchers a significant degree of system visibility. Additionally, because our node model emulates servers using a full SPARC v8 ISA compatible processor, each node in the network is capable of running real applications. This allows researchers to study a network under complex real-world workloads at a scale that matches that of a large datacenter today. Moreover, because the system is a private testbed, experiments can be deterministic and therefore reproduced by other researchers. Lastly, the system is cost effective for designers, and we show that using FPGA technology on the market today we can actually emulate a network of 256-nodes for about $2,000.

The energy efficiency of network elements is becoming more prominent, with growing concern for Internet power consumption and heat dissipation in datacenters and communications closets. Previous work has looked at energy efficient wireless topologies, network nodes, routers, and protocols. In considering a fresh redesign of the Internet datacenter for energy efficiency, we believe that energy efficient encodings are worthy of study. In this work, we re-examine the choice of Ethernet encoding, develop an associated energy model, evaluate current encodings, and propose new encodings. We found that simpler encodings are more energy efficient, with power savings of around 20% for the best encoding. Our work represents a first step in re-examining the established assumptions and practices of the PHY level of the network stack with respect to energy.

Packet content scanning at high speed has become extremely important due to its applications in network security, network monitoring, HTTP load balancing, etc. In content scanning, the packet payload is compared against a set of patterns specified as regular expressions. In this paper, we first show that memory requirements using traditional methods are prohibitively high for many patterns used in packet scanning applications. We then propose regular expression rewrite techniques that can effectively reduce memory usage. Further, we develop a grouping scheme that can strategically compile a set of regular expressions into several engines, resulting in remarkable improvement of regular expression matching speed without much increase in memory usage. We implement a new DFA-based packet scanner using the above techniques. Our experimental results using real-world traffic and patterns show that our implementation achieves a factor of 12 to 42 performance improvement over a commonly used DFA-based scanner. Compared to the state-of-art NFA-based implementation, our DFA-based packet scanner achieves 50 to 700 times speedup.

The effectiveness of automatic storage management depends on the accuracy of the storage performance models that are used for making resource allocation decisions. Several approaches have been proposed for modeling. Black-box approaches are the most promising in real-world storage systems because they require minimal device specific information, and are self-evolving with respect to changes in the system. However, blackbox techniques have been traditionally considered inaccurate and non-converging in real-world systems. This paper evaluates a popular off-the-shelf black-box technique for modeling a real-world storage environment. We measured the accuracy of performance predictions in single workload and multiple workload environments. We also analyzed accuracy of different performance metrics namely throughput, latency, and detection of saturation state. By empirically exploring improvements for the model accuracy, we discovered that by limiting the component model training for the nonsaturated zone only and by taking into account the number of outstanding IO requests, the error rate of the throughput model is 4.5% and the latency model is 19.3%. We also discovered that for systems with multiple workloads, it is necessary to consider access characteristics of each workload as input parameters for the model. Lastly, we report results on the sensitivity of model accuracy as a function of the amount of bootstrapping data.

New network applications like intrusion detection systems and packet-level accounting require multimatch packet classification, where all matching filters need to be reported. Ternary content addressable memories (TCAMs) have been adopted to solve the multimatch classification problem due to their ability to perform fast parallel matching. However, TCAMs are expensive and consume large amounts of power. None of the previously published multimatch classification schemes are both memory and power efficient. In this paper, we develop a novel scheme that meets both requirements by using a new set splitting algorithm (SSA). The main idea behind SSA is that it splits filters into multiple groups and performs separate TCAM lookups into these groups. It guarantees the removal of at least 1/2 the intersections when a filter set is split into two sets, thus resulting in low TCAM memory usage. SSA also accesses filters in the TCAM only once per packet, leading to low-power consumption. We compare SSA with two best known schemes: multimatch using discriminators (MUD) (Lakshminarayanan and Rangarajan, 2005) and geometric intersection-based solutions (Yu and Katz, 2004). Simulation results based on the SNORT filter sets show that SSA uses approximately the same amount of TCAM memory as MUD, but yields a 75%-95% reduction in power consumption. Compared with geometric intersection-based solutions, SSA uses 90% less TCAM memory and power at the cost of one additional TCAM lookup per packet. We also show that SSA can be combined with SRAM/TCAM hybrid approaches to further reduce energy consumption

An increasing variety of malware, such as worms, spyware and adware, threatens both personal and business computing. Remotely controlled bot networks of compromised systems are growing quickly. In this paper, we tackle the problem of automated detection of break-ins caused by unknown malware targeting personal computers. We develop a host based system, BINDER (Break-IN DEtectoR), to detect break-ins by capturing user unintended malicious outbound connections (referred to as extrusions). To infer user intent, BINDER correlates outbound connections with user-driven input at the process level under the assumption that user intent is implied by user-driven input. Thus BINDER can detect a large class of unknown malware such as worms, spyware and adware without requiring signatures. We have successfully used BINDER to detect real world spyware on daily used computers and email worms on a controlled testbed with very small false positives.

New network applications like intrusion detection systems and packet-level accounting require multi-match packet classification, where all matching filters need to be reported. Ternary Content Addressable Memories (TCAMs) have been adopted to solve the multi-match classification problem due to their ability to perform fast parallel matching. However, TCAM is expensive and consumes large amounts of power. None of the previously published multi-match classification schemes is both memory and power efficient. In this paper, we develop a novel scheme that meets both requirements by using a new Set Splitting Algorithm (SSA). The main idea of SSA is that it splits filters into multiple groups and performs separate TCAM lookups into these groups. It guarantees the removal of at least half the intersections when a filter set is split into two sets, thus resulting in low TCAM memory usage. SSA also accesses filters in the TCAM only once per packet, leading to low power consumption. We compare SSA with two best known schemes: MUD [1] and Geometric Intersection-based solutions [2]. Simulation results based on the SNORT filter sets show that SSA uses approximately the same amount of TCAM memory as MUD, but yields a 75% to 95% reduction in power consumption. Compared with Geometric Intersection-based solutions, SSA uses 90% less TCAM memory and power at the cost of one additional TCAM lookup per packet.

One of the key reasons overlay networks are seen as an excellent platform for large scale distributed systems is their resilience in the presence of node failures. This resilience rely on accurate and timely detection of node failures. Despite the prevalent use of keep-alive algorithms in overlay networks to detect node failures, their tradeoffs and the circumstances in which they might best he suited is not well understood. In this paper, we study how the design of various keep-alive approaches affect their performance in node failure detection time, probability of false positive, control overhead, and packet loss rate via analysis, simulation, and implementation. We find that among the class of keep-alive algorithms that share information, the maintenance of backpointer state substantially improves detection time and packet loss rate. The improvement in detection time between baseline and sharing algorithms becomes more pronounced as the size of neighbor set increases. Finally, sharing of information allows a network to tolerate a higher churn rate than baseline.

In this paper, we formulate a new theoretical problem, namely the reliable broadcast problem in unknown fixed-identity networks. This problem arises in the context of developing decentralized security mechanisms in a specific-class of distributed systems: Consider an undirected graph G connecting n nodes where each node is aware of only its neighbors but not of the entire graph. Additionally, each node has a unique identity and cannot fake its identity to its neighbors. Assume that k among the n nodes act in an adversarial manner and the remaining n-k are good nodes. Under what constraints does there exist a distributed algorithm Γ that enables every good node v to reliably broadcast a message m(v) to all other good nodes in G? While good nodes follow the algorithm Γ, an adversary can additionally discard messages, generate spurious messages or collude with other adversaries.In this paper, we prove two results on this problem. First, we provide a distributed algorithm Γ that can achieve reliable broadcast in an unknown fixed-identity network in the presence of k adversaries if G is 2k+1 vertex connected. Additionally, a minimum vertex connectivity of 2k+1 is a necessary condition for achieving reliable broadcast. Next, we study the problem of reliable broadcast in sparse networks (1-connected and 2-connected) in the presence of a single adversary i.e. k=1. In sparse networks, we show that a single adversary can partition the good nodes into groups such that nodes within a group can reliably broadcast to each other but nodes across groups cannot. For 1-connected and 2-connected graphs, we prove lower bounds on the number of such groups and provide a distributed algorithm to achieve these lower bounds. We also show that in a power-law random graph G(n,α), a single adversary can partition at most O(n1/α x (log n)(5- α)/(3-α)) good nodes from the remaining set of good nodes.Addressing this problem has practical implications to two real-world problems of paramount importance: (a) developing decentralized security measures to protect Internet routing against adversaries; (b) achieving decentralized public key distribution in static networks. Prior works on Byzantine agreement [17, 11, 23, 13, 3, 4, 24] are not applicable for this problem since they assume that either G is known, or that every pair of nodes can directly communicate, or that nodes use a key distribution infrastructure to sign messages. A solution to our problem can be extended to solve the byzantine agreement problem in unknown fixed-identity networks.

In today's Internet, worms and viruses cause service disruptions with enormous economic impact. Current attack prevention mechanisms rely on end-user cooperation to install new system patches or upgrade security software, yielding slow reaction time. However, malicious attacks spread much faster than users can respond, making effective attack prevention difficult network-based mechanisms, by avoiding end-user coordination, can respond rapidly to new attacks. Such mechanisms require the network to inspect the packet payload at line rates to detect and filter those packets containing worm signatures. These signature sets are large (e.g., thousands) and complex. Software-only implementations are unlikely to meet the performance goals. Therefore, making a network-based scheme practical requires efficient algorithms suitable for hardware implementations. This work develops a ternary content addressable memory (TCAM) based multiple-pattern matching scheme. The scheme can handle complex patterns; such as arbitrarily long patterns, correlated patterns, and patterns with negation. For the ClamAv virus database with 1768 patterns whose sizes vary from 6 bytes to 2189 bytes, the proposed scheme can operate at a 2 Gbps rate with a 240 KB TCAM.

Traceroute is used heavily by network operators and researchers to identify the IP forwarding path from a source to a destination. In practice, knowing the autonomous system (AS) associated with each hop in the path is also quite valuable. In previous work we showed that the IP-to-AS mapping extracted from BGP routing tables is not sufficient for determining the AS-level forwarding paths. By comparing BGP and traceroute AS paths from multiple vantage points, Z. Morley Mao et al. (2003) proposed heuristics that identify the root causes of the mismatches and fix the inaccurate IP-to-AS mappings. These heuristics, though effective, are labor-intensive and mostly ad hoc. This paper proposes a systematic way to construct accurate IP-to-AS mappings using dynamic programming and iterative improvement. Our algorithm reduces the initial mismatch ratio of 15% between BGP and traceroute AS paths to 5% while changing only 2.9% of the assignments in the initial IP-to-AS mappings. This is in contrast to the results of Z. Morley Mao et al. (2003), where 10% of the assignments were modified and the mismatch ratio was only reduced to 9%. We show that our algorithm is robust and can yield near-optimal results even when the initial mapping is corrupted or when the number of probing sources or destinations is reduced. Our work is a key step towards building a scalable and accurate AS-level traceroute tool

Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with n end hosts, existing systems either require O(n2) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Our earlier extended abstract [1] briefly proposes an algebraic approach that selectively monitors k linearly independent paths that can fully describe all the O(n2) paths. The loss rates and latency of these k paths can be used to estimate the loss rates and latency of all other paths. Our scheme only assumes knowledge of the underlying IP topology, with links dynamically varying between lossy and normal.In this paper, we improve, implement and extensively evaluate such a monitoring system. We further make the following contributions: i) scalability analysis indicating that for reasonably large n (e.g., 100), the growth of k is bounded as O(n log n), ii) efficient adaptation algorithms for topology changes, such as the addition or removal of end hosts and routing changes, iii) measurement load balancing schemes, and iv) topology measurement error handling. Both simulation and Internet experiments demonstrate we obtain highly accurate path loss rate estimation while adapting to topology changes within seconds and handling topology errors.

The rapid increase of wireless LAN (WLAN) deployments in enterprises and public places will likely cause frequent geographical coverage overlap among different domains. This work presents a radio resource broker (RRB) architecture that ensures fair allocation of radio resources across domains. The RRB keeps track of each provider's resource usage, and enforces fair resource allocation across providers by limiting the number of available channels or introducing network-initiated load balancing. We derive an empirical workload model based on measurements from a university-campus environment, and then use it to evaluate our approach with simulated dynamic radio resource usage. The simulation results demonstrate that channel compensation and load balancing are effective for redistributing radio resources fairly over a long time span, and that load balancing also performs well over a short span.

Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with n end hosts, existing systems either require O(n2) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Unlike other network tomography systems, we characterize end-to-end losses (this extends to any additive metrics, including latency) rather than individual link losses. We find a minimal basis set of k linearly independent paths that can fully describe all the O(n,2) paths. We selectively monitor and measure the loss rates of these paths, then apply them to estimate the loss rates of all other paths. By extensively studying synthetic and real topologies, we find that for reasonably large n (e.g., 100), k is only in the range of O(n log n). This is explained by the moderately hierarchical nature of Internet routine.Our scheme only assumes the knowledge of underlying IP topology, and any link can become lossy or return to normal. In addition, our technique is tolerant to topology measurement inaccuracies, and is adaptive to topology changes.

Service composition enables flexible creation of new services by assembling independent service components. We are focused on the scenario where such composition takes place across the wide-area Internet. We envision independent providers deploying and managing service instances and portal providers composing them to quickly enable new applications in next-generation networks. One of the important goals in such service composition is load balancing across service instances. While load balancing has been studied extensively for web-server selection, the presence of composition presents new challenges. First, each client session involving composition requires a set of service instances and not just one server. Second, unlike web-mirror selection, we also concern ourselves with load balancing in the presence of failure recovery during a client session. We introduce (a) a metric to choose the set of service instances for composed client sessions: the least-inverse-available-capacity (LIAC) metric, as well as (b) a piggybacking mechanism to give quick feedback about server load. We then introduce an additional factor in the load balancing metric to avoid choosing far away service instances. Our experiments, based on an emulation testbed, show that our load balancing mechanism works well under a variety of scenarios including network path failures.

Article Share on Host Mobility Using an Internet Indirection Infrastructure Authors: Shelley Zhuang View Profile , Kevin Lai View Profile , Ion Stoica View Profile , Randy Katz View Profile , Scott Shenker View Profile Authors Info & Claims MobiSys '03: Proceedings of the 1st international conference on Mobile systems, applications and servicesMay 2003Pages 129–144https://doi.org/10.1145/1066116.1189042Published:05 May 2003Publication History 46citation228DownloadsMetricsTotal Citations46Total Downloads228Last 12 Months5Last 6 weeks1 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 SiteGet Access

Traceroute is widely used to detect routing problems, characterize end-to-end paths, and discover the Internet topology. Providing an accurate list of the Autonomous Systems (ASes) along the forwarding path would make traceroute even more valuable to researchers and network operators. However, conventional approaches to mapping traceroute hops to AS numbers are not accurate enough. Address registries are often incomplete and out-of-date. BGP routing tables provide a better IP-to-AS mapping, though this approach has significant limitations as well. Based on our extensive measurements, about 10% of the traceroute paths have one or more hops that do not map to a unique AS number, and around 15% of the traceroute AS paths have an AS loop. In addition, some traceroute AS paths have extra or missing AS hops due to Internet eXchange Points, sibling ASes managed by the same institution, and ASes that do not advertise routes to their infrastructure. Using the BGP tables as a starting point, we propose techniques for improving the IP-to-AS mapping as an important step toward an AS-level traceroute tool. Our algorithms draw on analysis of traceroute probes, reverse DNS lookups, BGP routing tables, and BGP update messages collected from multiple locations. We also discuss how the improved IP-to-AS mapping allows us to home in on cases where the BGP and traceroute AS paths differ for legitimate reasons.

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

We analyzed 70 voice traces collected from IP-telephony applications, multicast lectures, and multimedia conferencing sessions which involve multiple speakers and different dynamics of interaction beyond two-way conversations. Results show that application differences have significant impact on the traffic characteristics. The conventional exponential model, established for telephone conversations, fails to capture accurately the packet level activity observed in these traces, e.g., the heavy-tail distributions of the talk-spurt and silence periods. We classify the traces into four types based on their audio contents: audience, lecture, multi-party conferencing and conversation. Further analysis shows that Weibull is a better matching statistical model and achieves lower mean-square-error than the exponential model (by 1 to 2 orders of magnitude) in approximating the audio streams for all four cases.

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

Communication reliability is a desired property in computer networks. One key technology to increase the reliability of a communication path is to provision a disjoint backup path. One of the main challenges in implementing this technique is that two paths that are disjoint at the IP or overlay layer may share the same physical links. As a result, although we may select a disjoint backup path at the overlay layer one physical link failure may cause the failure of both the primary and the backup paths. In this paper we propose a solution to address this problem. The main idea is to take into account the correlated link failure at the overlay layer More precisely, our goal is to find a route for the backup path to minimize the joint path failure probability between the primary and the backup paths. To demonstrate the feasibility of our approach, we perform extensive evaluations under both single and double link failure models. Our results show that, in terms of robustness, our approach is near optimal and is up to 60% better than no backup path reservation and is up to 30% better than using the traditional shortest disjoint path algorithm to select the backup path.

The delivery of IP traffic through the Internet depends on the complex interactions between thousands of autonomous systems (AS) that exchange routing information using the border gateway protocol (BGP). This paper investigates the topological structure of the Internet in terms of customer-provider and peer-peer relationships between autonomous systems, as manifested in BGP routing policies. We describe a technique for inferring AS relationships by exploiting partial views of the AS graph available from different vantage points. Next we apply the technique to a collection of ten BGP routing tables to infer the relationships between neighboring autonomous systems. Based on these results, we analyze the hierarchical structure of the Internet and propose a five-level classification of AS. Our characterization differs from previous studies by focusing on the commercial relationships between autonomous systems rather than simply the connectivity between the nodes.

Mobile ad-hoc networking involves peer-to-peer communication in a network with a dynamically changing topology. Achieving energy efficient communication in such a network is more challenging than in cellular networks since there is no centralized arbiter such as a base station that can administer power management. We propose and evaluate a power control loop, similar to those commonly found in cellular CDMA networks, for ad-hoc wireless networks. We use a comprehensive simulation infrastructure consisting of group mobility, group communication and terrain blockage models. A major focus of research in ad-hoc wireless networking is to reduce energy consumption because the wireless devices are envisioned to have small batteries and be incapable of energy scavenging. We show that this power control loop reduces energy consumption per transmitted byte by 10-20%. Furthermore, we show that it increases overall throughput by 15%.

The dynamic nature of a mobile ad hoc network (MANET) may result in a cluster of nodes being isolated from the rest of the network, especially when deployed in a terrain with blockages. To provide connectivity between the partitions of an ad hoc network that might occur due to mobility, a 'range extension' network can be employed. Such a network might consist of airborne communication platforms, or geostationary/low-Earth-orbit satellites maintaining communication links with specific 'gateway' nodes that are dispersed among the mobile ground nodes. Thus, to communicate with a node that is geographically distant or belongs to a different network partition, an ad hoc node can relay its data packets through an appropriate mobile gateway and via the range extension network. In such an architecture, MANET is divided into different domains with a mobile gateway deployed for each domain. The objective, then, is to determine the position and trajectory of the gateways to optimize network performance metrics such as throughput and latency. In this paper, computation of the optimal position for a gateway is shown to be equivalent to a linear optimization problem by means of some simplifying but realistic assumptions. An algorithm is proposed for the control of the gateway trajectory. The practical constraints imposed by the velocity and maneuverability of the gateways are taken into account. Simulation results show a 10-15% improvement in the throughput and latency, per gateway domain, if a gateway has a dynamic trajectory whose locus follows the computed optimal position, as compared to a gateway that is statically placed at a fixed position, or to a gateway that has a random trajectory.

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. .

We conducted user experiments and simulations to understand the tradeoffs of congestion pricing between system performance and user satisfaction for a large community of users. We found that congestion pricing can be effective for voice calls because it only needs to be applied occasionally and that users are responsive to occasional price increases.

Charging a higher price during periods of congestion should more efficiently allocate scarce resources by encouraging users to conserve. We study its benefits by conducting several pricing experiments over two semesters with students in the dormitories using a computer-telephony-service. Users can use the service to make and receive phone calls from their computers or telephones. While we do not charge users real money, we limit each user to a certain number of tokens a week. With this experimental setup, we conducted a different pricing experiment each week to better understand how prices can be used to entice users to talk less, talk at another time, or use a lower quality connection. With our token scheme as a budget constraint, we can use static pricing policies to influence users' behaviors, but cannot use a simple congestion pricing scheme to encourage users to talk less. For example, we can use time-of-day pricing to encourage users to shift 30% of their usages from the peak to the off-peak hours. We can also use call-duration pricing, a higher rate as a call lasts longer, to encourage 3 times as many calls (18% instead of 6%) to terminate after a price increase. However, when using a simple congestion pricing scheme that charges a rate depending on the number of people calling, we find that we cannot get users to terminate their calls earlier. We believe that users do not change their behaviors because they do not know how long the price increases or decreases will last. Thus to make a congestion pricing scheme more effective, we believe that the price changes need to be more permanent to entice users to change their behaviors'.

Advances in the Internet and telecommunications technologies have spurred many research efforts in Internet-based unified communication systems, which integrate heterogeneous devices and networks (PSTN, cellular networks, or the pager networks). Nonetheless, these systems lack support for a systematic, easy, flexible way of customizing and creating services at the system level as well as at the user level. In this paper, we present such a service creation model by exposing a limited set of primitives from a call model that is network and device independent. Our model and framework not only supports the traditional telephony call services easily but also enables novel ways of creating third party services such as application-specific billing services.

The demand for streaming multimedia applications is growing at an incr edible rate. In this paper, we propose Bayeux, an efficient application-level multicast system that scales to arbitrarily large receiver groups while tolerating failures in routers and network links. Bayeux also includes specific mechanisms for load-balancing across replicate root nodes and more efficient bandwidth consumption. Our simulation results indicate that Bayeux maintains these properties while keeping transmission overhead low. To achieve these properties, Bayeux leverages the architecture of Tapestry, a fault-tolerant, wide-area overlay routing and location network.

Advances in satellite technology are enabling the deployment of large constellations of low Earth Orbiting (LEO) satellites. Next-generation systems will be tailored for broadband, packet-switched services, and therefore require either distributed or centralized packet routing mechanisms. Some researchers have hypothesized that the semi-regular mesh topology of a polar-orbiting constellation admits a simple distributed routing protocol based on using geographic information embedded in the node address. We take a closer look at this hypothesis in the context of commercially-proposed constellation designs. Using simulation, we study a distributed routing protocol that selects the next hop based on a minimization of the remaining distance to the destination. Our numerical results indicate that this routing strategy usually yields good routes, with an average latency degradation of less than 10 ms when compared with the optimal route. However, there are locations in the topology, most notably around the counter-rotating seams, the polar regions, and close to the destination of a packet, where the assumption of a regular mesh topology breaks down and it is difficult to guarantee robustness without adding significant additional complexity to the protocol.

Scalability of multicast forwarding state is likely to be a major issue facing inter-domain multicast deployment. We present a comprehensive analysis of the multicast forwarding state problem. Our goal is to understand the scaling trends of multicast forwarding state in the Internet, and to explore the intuitions that have motivated state reduction research. We conducted simulation experiments on both real and generated network topologies, with a range of parameters driven by multicast application characteristics. We found that the increase in peering among Internet backbone networks has led to more multicast forwarding state at a handful of core domains, but less state in the rest of the domains. We observed that scalability of multicast forwarding state with respect to session size follows a power law. Our findings show that distribution and concentration of multicast forwarding state in the Internet is significantly, impacted by the application characteristics. We investigated the proposals on non-branching multicast forwarding state elimination, and found substantial reduction is attainable even with very dense multicast sessions.

The quality of network connectivity between a pair of Internet hosts can vary greatly. Adaptive applications can cope with these differences in connectivity by choosing alternate representations of objects or streams or by downloading the objects from alternate locations. In order to effectively adapt, applications must discover the condition of the network before communicating with distant hosts. Unfortunately, the ability to predict or report the quality of connectivity is missing in today's suite of Internet services. To address this limitation, we have developed SPAND (shared passive network performance discovery), a system that facilitates the development of adaptive network applications. In each domain, applications make passive application specific measurements of the network and store them in a local centralized repository of network performance information. Other applications may retrieve this information from the repository and use the shared experiences of all hosts in a domain to predict future performance. In this way, applications can make informed decisions about adaptation choices as they communicate with distant hosts. In this paper, we describe and evaluate the SPAND architecture and implementation. We show how the architecture makes it easy to integrate new applications into our system and how the architecture has been used with specifics types of data transport. Finally, we describe LookingGlass, a WWW mirror site selection tool that uses SPAND. LookingGlass meets the conflicting goals of collecting passive network performance measurements and maintaining good client response times. In addition, LookingGlass's server selection algorithms based on application level measurements perform much better than techniques that rely on geographic location or route metrics.

Because of the emergence of heterogeneous access devices and diverse wired and wireless networks, and a substantial lack of support for integrating these networks, we are building a communication network and a service infrastructure that provides integrated telephony and data services across these networks. We generalize the basic call service to support communication between two or more call parties using any number of devices through any media. Call setup has already been addressed by protocols such as the session initiation protocol (SIP), so we focus on a missing component: scalable and fault-tolerant call session maintenance and control after call setup. In this paper, we present a new signaling protocol that offers scalability, high availability, robustness, and flexibility in creating new call processing services. The protocol is compatible with existing call setup protocols, but provides lightweight call session management using a completely decentralized, soft-state group control protocol. We show that this approach simplifies the implementation of the basic call service, including multi-device calling and service handoff between diverse access networks. The design of our protocol follows the principle of separation of control (signaling information) from data. The signaling protocol has been implemented in ICEBERG, an IP-based core network testbed with access to heterogeneous networks.

The efficiency of using multicast in multi-party applications is constrained by preference heterogeneity, where receivers range in their preferences for application data. We examine an approach in which approximately similar sources and receivers are clustered into multicast groups. The goal is to maximize preference overlap within each group while satisfying the constraint of limited network resources. This allows an application to control the number of multicast groups it uses and thus the number of connections it maintains. We present a clustering framework with a two-phase algorithm: a bootstrapping phase that groups new sources and receivers together, and an adaptation phase that re-groups them in reaction to changes. The framework is generic in that an application can customize the algorithm according to its requirements and data characteristics. We conducted detail simulation experiments to study various issues and tradeoffs in applying clustering to different preference patterns and application classes. We found that clustering successfully exploits preference similarity and utilizes network resources more efficiently than when it is not used. Also, application-level hints can be incorporated in our algorithm, which are instrumental in the creation of an effective grouping of sources and receivers. Our algorithm handles changes dynamically, and also limits multicast "join" and "leave" disruption to the application.

Developing wireless sensor networks can enable information gathering, information processing and reliable monitoring of a variety of environments for both civil and military applications. It is however necessary to agree upon a basic architecture for building sensor network applications. This paper presents a general classification of sensor network applications based on their network configurations and discusses some of their architectural requirements. We propose a generic architecture for a specific subclass of sensor applications which we define as self-configurable systems where a large number of sensors coordinate amongst themselves to achieve a large sensing task. Throughout this paper we assume a certain subset of the sensors to be immobile. This paper lists the general architectural and infra-structural components necessary for building this class of sensor applications. Given the various architectural components, we present an algorithm that self-organizes the sensors into a network in a transparent manner. Some of the basic goals of our algorithm include minimizing power utilization, localizing operations and tolerating node and link failures.

The widespread deployment of inexpensive communications technology, computational resources in the networking infrastructure, and network-enabled end devices poses an interesting problem for end users: how to locate a particular network service or device out of hundreds of thousands of accessible services and devices.This paper presents the architecture and implementation of a secure Service Discovery Service (SDS).Service providers use the SDS to advertise complex descriptions of available or already running services, while clients use the SDS to compose complex queries for locating these services.Service descriptions and queries use the extensible Markup Language (XML) to encode such factors as cost, performance, location, and device-or service-specific capabilities.The SDS provides a highlyavailable, fault-tolerant, incrementally scalable service for locating services in the wide-area.Security is a core component of the SDS and, where necessary, communications are both encrypted and authenticated.Furthermore, the SDS uses an hybrid access control list and capability system to control access to service information.

Article Next century challenges: mobile networking for "Smart Dust" Share on Authors: J. M. Kahn Department of Electrical Engineering and Computer Sciences, University of California, Berkeley Department of Electrical Engineering and Computer Sciences, University of California, BerkeleyView Profile , R. H. Katz Department of Electrical Engineering and Computer Sciences, University of California, Berkeley Department of Electrical Engineering and Computer Sciences, University of California, BerkeleyView Profile , K. S. J. Pister Department of Electrical Engineering and Computer Sciences, University of California, Berkeley Department of Electrical Engineering and Computer Sciences, University of California, BerkeleyView Profile Authors Info & Claims MobiCom '99: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networkingAugust 1999 Pages 271–278https://doi.org/10.1145/313451.313558Online:01 August 1999Publication History 972citation5,666DownloadsMetricsTotal Citations972Total Downloads5,666Last 12 Months122Last 6 weeks18 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 SiteGet Access

We address the question of how well end-to-end transport connections perform in a satellite environment composed of one or more satellites in geostationary orbit (GEO) or low-altitude Earth orbit (LEO), in which the connection may traverse a portion of the wired Internet. We first summarize the various ways in which latency and asymmetry can impair the performance of the Internet's transmission control protocol (TCP), and discuss extensions to standard TCP that alleviate some of these performance problems. Through analysis, simulation, and experiments, we quantify the performance of state-of-the-art TCP implementations in a satellite environment. A key part of the experimental method is the use of traffic models empirically derived from Internet traffic traces. We identify those TCP implementations that can be expected to perform reasonably well, and those that can suffer serious performance degradation. An important result is that, even with the best satellite-optimized TCP implementations, moderate levels of congestion in the wide-area Internet can seriously degrade performance for satellite connections. For scenarios in which TCP performance is poor, we investigate the potential improvement of using a satellite gateway, proxy, or Web cache to "split" transport connections in a manner transparent to end users. Finally, we describe a new transport protocol for use internally within a satellite network or as part of a split connection. This protocol, which we call the satellite transport protocol (STP), is optimized for challenging network impairments such as high latency, asymmetry, and high error rates. Among its chief benefits are up to an order of magnitude reduction in the bandwidth used in the reverse path, as compared to standard TCP, when conducting large file transfers. This is a particularly important attribute for the kind of asymmetric connectivity likely to dominate satellite-based Internet access.

We analyze the way in which Web browsers use TCP connections based on extensive traffic traces obtained from a busy Web server (the official Web server of the 1996 Atlanta Olympic games). At the time of operation, this Web server was one of the busiest on the Internet. We first describe the techniques used to gather these traces and reconstruct the behavior of the TCP on the server. We then present a detailed analysis of the TCP's loss recovery and congestion control behavior from the recorded transfers. Our two most important results are: (1) short Web transfers lead to poor loss recovery performance for TCPs, and (2) concurrent connections are overly aggressive users of the network. We then discuss techniques designed to solve these problems. To improve the data-driven loss recovery performance of short transfers, we present a new enhancement to the TCP's loss recovery. To improve the congestion control and loss recovery performance of parallel TCP connections, we present a new integrated approach to congestion control and loss recovery that works across the set of concurrent connections. Simulations and trace analysis show that our enhanced loss recovery scheme could have eliminated 25% of all timeout events, and that our integrated approach provides greater fairness and improved startup performance for concurrent connections.

Wireless networking is becoming an increasingly important communication means, yet high wide--area wireless data connectivity is difficult to achieve due to technological and physical limitations. To alleviate these problems we experiment with an alternative by placing many high bandwidth local "islands" of info--stations dispersed throughout the low bandwidth wide--area wireless network. The location and distribution of the individual stations is crucial for the network's overall effectiveness, as demonstrated by our investigations. The info--stations are deployed in a transparent manner, often not geographically visible to the user. Applications must be designed to be mobile--aware and able to account for changing network characteristics by optimally utilizing the available network resources. We simulate alternative network layouts and determine their effectiveness by experimenting with an incremental map downloading application for road travelers that uses intelligent prefetching to...

Several recent proposals for an "active networks" architecture advocate the placement of user-defined computation within the network as a key mechanism to enable a wide range of new applications and protocols, including reliable multicast transports, mechanisms to foil denial of service attacks, intra-network real-time signal transcoding, and so forth. This laudable goal, however, creates a number of very difficult research problems, and although a number of pioneering research efforts in active networks have solved some of the preliminary small-scale problems, a large number of wide open problems remain. In this paper, we propose an alternative to active networks that addresses a restricted and more tractable subset of the active-networks design space. Our approach, which we (and others) call "active services", advocates the placement of user-defined computation within the network as with active networks, but unlike active networks preserves all of the routing and forwarding semantics of current Internet architecture by restricting the computation environment to the application layer. Because active services do not require changes to the Internet architecture, they can be deployed incrementally in today's Internet.We believe that many of the applications and protocols targeted by the active networks initiative can be solved with active services and, toward this end, we propose herein a specific architecture for an active service and develop one such service in detail --- the Media Gateway (MeGa) service --- that exploits this architecture. In defining our active service, we encountered six key problems --- service location, service control, service management, service attachment, service composition, and the definition of the service environment --- and have crafted solutions for these problems in the context of the MeGa service. To verify our design, we implemented and fielded MeGa on the UC Berkeley campus, where it has been used regularly for several months by real users who connect via ISDN to an "on-line classroom". Our initial experience indicates that our active services prototype provides a very flexible and programmable platform for intra-network computation that strikes a good balance between the flexibility of the active networks architecture and the practical constraints of incremental deployment in the current Internet.

Summary form only given. In this presentation, we explore in greater detail the challenges faced by wireless data services, and some of the technology developments and possible solutions that lead us to be optimistic that wireless data is not yet dead, and in fact, has a very promising future. In particular, new spectrum allocations, coupled with integrated circuit technology breakthroughs, will enable much higher data rates. For example, the FCC has recently allocated spectrum for the Unlicensed NII Band at 5.15 GHz (350 MHz) and in the 60 GHz band (an incredible 5 GHz of available spectrum). Furthermore, ubiquitous digital cellular telephones will provide a widely available, flexible, and moderate rate digital channel for voice and data over the wide-area. And new networking technologies, in particular, wireless overlay networks and spectrum sharing techniques, will make it possible to maintain connectivity as a user moves from room-sized wireless networks, to building-sized networks, to the metropolitan, wide-area, and regional networks.

The SPEC benchmark system has traditionally been used for evaluating computer architectures. However, this system is too general and does not accurately reflect the performance of architectures on domain-specific applications. Moreover the CPU95 benchmark suite used in the SPEC system is compute-intensive, while many important domains of applications have memory intensive algorithms. In this work, we present a benchmarking methodology for such an application domain-CAD for VLSI design. We have created a benchmark suite consisting of CAD applications from each stage in a typical VLSI design flow. To exercise the memory organization, each application is run on a sequence of input designs of increasing size. We observed that increasing the input size causes non-monotonic variations in the performance of different machines. We simulate the caches of the benchmarked architectures to assess the effect of memory organization on performance.

Current Internet multicast conferencing tools treat all sources with equal importance in that they either statically allocate a fixed bandwidth to each source in a session, or they automatically adapt each source's transmission rate independently of all other sources.But not all sources are of equal interest to all receivers.We believe that to effectively support human to human communication, this disparity in receiver interest should be reflected in the rate-adaptation process.To this end, we propose a protocol called "SCUBA" that enables media sources to intelligently account for receiver interest in their rate-adjustment algorithms.SCUBA is orthogonal to and complements existing rate-adaptation schemes and can interoperate with either sender-or receiverdirected control systems.To scale the SCUBA protocol with multicast session size, we decouple the receiver-feedback process from the session size through sampling.This approach introduces a "tunable" tradeoff between convergence time and sampling accuracy that for large sessions is solely dependent on the control traffic bandwidth.In addition to its applicability in video conferencing, our control scheme can be combined with media transcoders to intelligently manage a bottleneck link at a well-known and fixed location in the network.We implemented SCUBA within our video conferencing tool vie and our media gateway rtpgw and feedback from their preliminary deployment indicates that the efficacy of the overall multimedia communication system has been greatly enhanced.

In this paper, we study the effects of network asymmetry on endto -end TCP performance and suggest techniques to improve it. The networks investigated in this study include a wireless cable modem network and a packet radio network. In recent literature (e.g., [16]), asymmetry has been considered in terms of a mismatch in bandwidths in the two directions of a data transfer. We generalize this notion of bandwidth asymmetry to other aspects of asymmetry, such as latency and media-access, and packet error rate, which are common in wide-area wireless networks. Using a combination of experiments on real networks and simulation, we analyze TCP performance in such networks where the throughput achieved is not solely a function of the link and traffic characteristics in the direction of data transfer (the forward direction) , but depends significantly on the reverse direction as well. We focus on bandwidth and latency asymmetries, and propose and evaluate several schemes to improve end-to-end ...

This paper introduces the notion of “universal interaction,” allowing a device to adapt its functionality to exploit services it discovers as it moves into a new environment. Users wish to invoke services — such as controlling the lights, printing locally, or reconfiguring the location of DNS servers — from their mobile devices. But aprioristandardization of interfaces and methods for service invocation is infeasible. Thus,the challenge is to develop a new service architecture that supports heterogeneity in client devices and controlled objects, and which makes minimal assumptions about standard interfaces and control protocols. There are five components to a comprehensive solution to this problem: 1) allowing device mobility, 2) augmenting controllable objects to make them network-accessible, 3) building an underlying discovery architecture, 4) mapping between exported object interfaces and client device controls, and 5) building complex behaviors from underlying composable objects. We motivate the need for these components by using an example scenario to derive the design requirements for our mobile services architecture. We then present a prototype implementation of elements of the architecture and some example services using it, including controls to audio/visual equipment, extensible mapping, server autoconfiguration, location tracking, and local printer access.

Subjecting a mobile computing system to wireless network conditions that are realistic yet reproducible is a challenging problem. In this paper, we describe a technique called trace modulation that re-creates the observed end-to-end characteristics of a real wireless network in a controlled and repeatable manner. Trace modulation is transparent to applications and accounts for all network traffic sent or received by the system under test. We present results that show that it is indeed capable of reproducing wireless network performance faithfully.

The Internet is a very large scale, complex, dynamical system that is hard to model and analyze. In this paper, we develop and analyze statistical models for the observed end-to-end network performance based on extensive packet-level traces (consisting of approximately 1.5 billion packets) collected from the primary Web site for the Atlanta Summer Olympic Games in 1996. We find that observed mean throughputs for these transfers measured over 60 million complete connections vary widely as a function of end-host location and time of day, confirming that the Internet is characterized by a large degree of heterogeneity. Despite this heterogeneity, we find (using best-fit linear regression techniques) that we can express the throughput for Web transfers to most hosts as a random variable with a log-normal distribution. Then, using observed throughput as the control parameter, we attempt to quantify the spatial (statistical similarity across neighboring hosts) and temporal (persistence over time) stability of network performance. We find that Internet hosts that are close to each other often have almost identically distributed probability distributions of throughput. We also find that throughputs to individual hosts often do not change appreciably for several minutes. Overall, these results indicate that there is promise in protocol mechanisms that cache and share network characteristics both within a single host and amongst nearby hosts.

Reliable transport protocols such as TCP are tuned to perform well in traditional networks where packet losses occur mostly because of congestion. However, networks with wireless and other lossy links also suffer from significant losses due to bit errors and handoffs. TCP responds to all losses by invoking congestion control and avoidance algorithms, resulting in degraded end-to end performance in wireless and lossy systems. We compare several schemes designed to improve the performance of TCP in such networks. We classify these schemes into three broad categories: end-to-end protocols, where loss recovery is performed by the sender; link-layer protocols that provide local reliability; and split-connection protocols that break the end-to-end connection into two parts at the base station. We present the results of several experiments performed in both LAN and WAN environments, using throughput and goodput as the metrics for comparison. Our results show that a reliable link-layer protocol that is TCP-aware provides very good performance. Furthermore, it is possible to achieve good performance without splitting the end-to-end connection at the base station. We also demonstrate that selective acknowledgments and explicit loss notifications result in significant performance improvements.

Reliable transport protocols such as TCP are tuned to perform well in traditional networks where packet losses occur mostly because of congestion. However, networks with wireless and other lossy links also suffer from significant non-congestion-related losses due to reasons such as bit errors and handoffs. TCP responds to all losses by invoking congestion control and avoidance algorithms, resulting in degraded end-to-end performance in wireless and lossy systems. In this paper, we compare several schemes designed to improve the performance of TCP in such networks. These schemes are classified into three broad categories: end-to-end protocols, where the sender is aware of the wireless link; link-layer protocols, that provide local reliability; and split-connection protocols, that break the end-to-end connection into two parts at the base station. We present the results of several experiments performed in both LAN and WAN environments, using throughput and goodput as the metrics for comparison.Our results show that a reliable link-layer protocol with some knowledge of TCP provides very good performance. Furthermore, it is possible to achieve good performance without splitting the end-to-end connection at the base station. We also demonstrate that selective acknowledgments and explicit loss notifications result in significant performance improvements.

Abstract — Most information and services required today by designers will soon become available as documents distributed in a wide area hypermedia network. New integration services are required from the design environment, supporting business transactions with design information providers, automatic exchange of design data between independent groups, and inte-grated support for new forms of collaboration. We discuss design using electronic commerce and other services based on the Inter-net, and propose a hypermedia system organization for a new generation of CAD systems, conceived to make efficient use of that infrastructure. We also describe our experience as designers of an integrated design and documentation system that interfaces existing design and documentation tools with electronic com-merce services based on the World Wide Web. I.

TCP is a reliable transport protocol tuned to perform well in traditional networks made up of wired links with stationary hosts. Networks with wireless links and mobile hosts violate many of the assumptions made by TCP, causing degraded performance. We describe a simple protocol that improves TCP performance by modifying network-layer software only at a basestation without violating end-to-end TCP semantics. The main idea is to cache packets at the basestation and perform focal retransmissions. Simulations of this protocol show that is it significantly more robust in the presence of multiple packet losses in a single transmission window as compared to TCP. This enables our protocol to tolerate at least 10 times as high an error rate without any performance degradation.

No abstract available.

TCP is a reliable transport protocol tuned to perform well in traditional networks made up of links with low bit-error rates. Networks with higher bit-error rates, such as those with wireless links and mobile hosts, violate many of the assumptions made by TCP, causing degraded end-to-end performance. In tbis paper, we describe the design and implementation of a simple protocol, called the snoop protocol, that improves TCP performance in wireless networks. The protocol modifies network-layer software mainly at a base station and preserves end-to-end TCP semantics. The main idea of the protocol is to cache packets at the base station and perform local retransmissions across the wireless link. We have implemented the snoop protocol on a wireless testbed consisting of IBM ThinkPad laptops and i486 base stations communicating over an AT&T Wavelan. Our experiments show that it is significantly more robust at dealing with unreliable wireless links as compared to normal TCP; we have achieved throughput speedups of up to 20 times over regular TCP in our experiments with the protocol.

This paper describes the design and implementation of a VLSI design process management system called Papyrus, which is built upon a history-based design process model that supports both routine and exploratory VLSI design processes. Emphasis of this paper is put on the descriptions of Papyrus's basic data models, design decisions, and implementation details. The operational prototype features a transparent dynamic load balancing scheme to exploit the computation power of networked workstations, an atomicity-guarantee mechanism to preserve the high-level abstraction of the design task construct, an interactive design-history manipulation facility, and a set of storage management techniques to reduce the storage overhead entailed by the single assignment update semantics, which is crucial to the support of the so-called rework mechanism. This system also embodies an innovative history-based meta-data inference scheme that automates many previously user-responsible design data management functions.>

In 1989, the RAID (Redundant Arrays of Inexpensive Disks) group at U.C. Berkeley built a prototype disk array called RAID-I. The bandwidth delivered to clients by RAID-I was severely limited by the memory system bandwidth of the disk array's host workstation. They designed their second prototype, RAID-II, to deliver more of the disk array bandwidth to file server clients. A custom-built crossbar memory system called the XBUS board connects the disks directly to the high-speed network, allowing data for large requests to bypass the server workstation. RAID-II runs Log-Structured File System (LFS) software to optimize performance for bandwidth-intensive applications. The RAID-II hardware with a single XBUS controller board delivers 20 megabytes/second for large, random read operations and up to 31 megabytes/second for sequential read operations. A preliminary implementation of LFS on RAID-II delivers 21 megabytes/second on large read requests and 15 megabytes/second on large write operations.>

No abstract available.

Abstruc&Wepresent a new system for documentation in VLSI design environments.The system integrates hypermedia and some services of a CAD applications framework to offer a radically new user interface to designers.This combination of technologies enables the use of the documentation system as a frontend to the design tools, resulting in a single interface metaphor for manipulating design data, processes and the design environment.Through the use of design data and history management services, the design pmeess becomes like writing a notebook, containing all the information associated with a design as it is being conceived.Hypermedia ptwvides new capabilities for integrating media into design documentation and for non-linear views of documents.Invoking the design tools from within the documentation system adds the capability of direct manipulation of the design objects and their re-use as part of the documentation.This paper describes the conceptual model for a design system front-end embodying these ideas and a prototype implemetttation.

The design and implementation of the network architecture (hardware, software, and protocols) of the RAID-II system are described. RAID-II is a high-speed file server connected to an UltraNetwork. To support high bandwidth network transfers with the RAID-II server, the networking software is divided among the various processors in the system. With the distributed software, the CPU still limits the RAID-II file server to 21 Mbyte/s of data bandwidth on the authors' network.

In a multimedia storage system video is probably the most demanding data type because of its large data volume and strict timing requirements.Image compression and parallel I/O architecture have been proposed in the literature to address the storage problem associated with digital video.This paper takes a systems approach by integrating video compression with data layout algorithms on parallel disk arrays to support high-quality video rendition.Specifically, we propose to use a multiresolution video representation scheme based on Gaussian and Laplacian Pyramids, which allows the storage system to satisfy video access requests by transferring only the minimum amount of data that is absolutely necessary.We also develope a new array storage layout algorithm for the Laplacian pyramid coding scheme to support jitter-free video rendering at the level of disk subsystems.We report on the results of a simulation study on the effectiveness of the proposed integrated design.The result shows that under the assumed workload the multi-resolution scheme is significantly better than the conventional representation in terms of the I/O rate, average waiting time, and average physical data bandwidth requirement.Specifically, the Laplacian Pyramid representation costs three to four times less data traffic, , reduces the average waiting time to one-eighth of that of the conventional approach, and achieves a five to ten times better average I/O rate.

Data striping is a technique for increasing the throughput and reducing the response time of large accesses to a storage system. In this paper, we evaluate the effectiveness of applying striping concepts to large tape libraries. Striping in tape libraries is being used with success for applications such as backup and scientific data collection, where data access patterns are strictly sequential. In this paper, we evaluate striped performance for randomly distributed accesses to the tape library. We believe such operations will be characteristic of future tertiary storage databases using large objects, such as on-line libraries and multimedia databases. Using an event-driven simulator, we show that striped large tape libraries perform poorly for this random workload because striping causes contention for the small number of readers and robot arms in these libraries. Increasing the number of readers results in better striped performance. We also examine how the effectiveness of striping ...

As disk arrays become widely used, tools for understanding and analyzing their performance become increasingly important. In particular, performance models can be invaluable in both configuring and designing disk arrays. Accurate analytic performance models are preferable to other types of models because they can be quickly evaluated, are applicable under a wide range of system and workload parameters, and can be manipulated by a range of mathematical techniques. Unfortunately, analytic performance models of disk arrays are difficult to formulate due to the presence of queueing and fork-join synchronization; a disk array request is broken up into independent disk requests which must all complete to satisfy the original request. In this paper, we develop and validate an analytic performance model for disk arrays. We derive simple equations for approximating their utilization, response time and throughput. We validate the analytic model via simulation, investigate the error introduced by each approximation used in deriving the analytic model, and examine the validity of some of the conclusions that can be drawn from the model.

Due to recent advances in central processing unit (CPU) and memory system performance, input/output (I/O) systems are increasingly limiting the performance of modern computer systems. Redundant arrays of inexpensive disks (RAID) have been proposed to meet the impending I/O crisis. RAIDs substitute many small inexpensive disks for a few large expensive disks to provide higher performance, smaller footprints, and lower power consumption at a lower cost than the large expensive disks they replace. RAIDs provide high availability by using parity encoding of data to survive disk failures. It is shown that the way parity is distributed in a RAID has significant consequences for performance. The performances of eight different parity placements are investigated using simulation.>

A data management paradigm that incrementally and transparently constructs the relationship among VLSI design objects is proposed. This paradigm is based on a design history model and the specifications of CAD-tool execution semantics. Based on this paradigm, algorithms are developed to automatically establish interobject relationships as a side effect of CAD-tool execution. This paradigm represents a vastly different approach in that it exploits history information, as well as domain knowledge, to deduce useful metadata for data management.>

Article Eliminating the address translation bottleneck for physical address cache Share on Authors: Tzi-cker Chiueh View Profile , Randy H. Katz View Profile Authors Info & Claims ASPLOS V: Proceedings of the fifth international conference on Architectural support for programming languages and operating systemsSeptember 1992 Pages 137–148https://doi.org/10.1145/143365.143501Online:01 September 1992Publication History 28citation507DownloadsMetricsTotal Citations28Total Downloads507Last 12 Months10Last 6 weeks2 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 SiteGet Access

The technology trends underlying high-performance network-based storage, namely, advances in networks, storage devices, and I/O controller and server architectures, are discussed. The emphasis is on the integration of storage and network services and the challenges of managing the complex storage hierarchy of the future: file caches, online disk storage, nearline data libraries, and offline archives. Several commercial systems and research prototypes that are leading to a new approach to high-performance computing based on network-attached storage are reviewed.>

article Performance consequences of parity placement in disk arrays Share on Authors: Edward K. Lee View Profile , Randy H. Katz View Profile Authors Info & Claims ACM SIGOPS Operating Systems ReviewVolume 25Issue Special IssueApr. 1991 pp 190–199https://doi.org/10.1145/106974.106992Published:01 April 1991 47citation615DownloadsMetricsTotal Citations47Total Downloads615Last 12 Months6Last 6 weeks0 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 SiteGet Access

The collection and analysis of supercomputer I/O traces and their use in a collection of buffering and caching simulations are described. This serves two purposes. First, it gives a model of how individual applications running on supercomputers request file system I/O, allowing system designer to optimize I/O hardware and file system algorithms to that model. Second, the buffering simulations show what resources are needed to maximize the CPU utilization of a supercomputer given a very bursty I/O request rate. By using read-ahead and write-behind in a large solid stated disk, one or two applications were sufficient to fully utilize a Cray Y-MP CPU.

The RAID group at U.C. Berkeley recently built a prototype disk array. This paper examines the performance limits of each component of the array usiug SCSI bus traces, Sprite operating system traces and user programs.The array performs successfully for a workload of small, random I/O operations, achieving 275 I/Os per second on 14 disks before the Sun4/280 host becomes CPU-limited. The prototype is less successful in delivering high throughput for large, sequential operations. Memory system contention on the Sun4/280 host limits throughput to 2.3 MBytes/sec under the Sprite Operating System. Throughput is also limited by the bandwidth supported by the VME backplane, disk controller and disks, and overheads associated with the SCSI protocol.We conclude that merely using a powerful host CPU and many disks will not provide the full bandwidth possible from disk arrays. Host memory bandwidth and throughput of disk controllers are equally important. In addition, operating systems should avoid unnecessary copy and cache flush operations that can saturate the host memory system.

There are two aspects of engineering design datz internal data representation and abstract attri-

A history model is proposed to support the dynamic aspects of VLSI design, i.e., the controlled and disciplined sequencing of CAD tool invocations. This model is based on a task specification language, for encapsulating CAD tool invocations, and a novel activity thread, which maintains the history of task invocations and serves as a focus for sharing work results in a cooperative manner. A prototype was built on top of the OCT CAD framework.>

Recently we presented several disk array architectures designed to increase the data rate and I/O rate of supercomputing applications, transaction processing, and file systems [Patterson 88]. In this paper we present a hardware performance measurement of two of these architectures, mirroring and rotated parity. We see how throughput for these two architectures is affected by response time requirements, request sizes, and read to write ratios. We find that for applications with large accesses, such as many supercomputing applications, a rotated parity disk array far outperforms traditional mirroring architecture. For applications dominated by small accesses, such as transaction processing, mirroring architectures have higher performance per disk than rotated parity architectures.

Bus bandwidth ultimately limits the performance, and therefore the scale, of bus-based, shared memory multiprocessors. Previous studies have extrapolated from uniprocessor measurements and simulations to estimate the performance of these machines. In this study, we use traces of parallel programs to evaluate the cache and bus performance of shared memory multiprocessors, in which coherency is maintained by a write-invalidate protocol. In particular, we analyze the effect of sharing overhead on cache miss ratio and bus utilization.

This paper describes the extensions made for adding support for group development within the Oct/VEM CAD framework. In our implementation, a set of mechanisms has been incorporated into the Oct library. These contain support for versioning and concurrent access to Oct design objects. The mechanisms can be configured for establishment of specific design management styles. As an example, there is now support for organization of designs in terms of workspaces; but, the number of workspaces or the relationship between them must be established externally by a design management tool. Design management tools configure these mechanisms to establish policies to be followed by the other tools. With this architecture, integration of existing tools with distinct design management styles then becomes feasible.

Write-invalidate and write-broadcast coherency protocols have been criticized for being unable to achieve good bus performance across all cache configurations. In particular, write-invalidate performance can suffer as block size increases; and large cache sizes will hurt write-broadcast. Read-broadcast and competitive snooping extensions to the protocols have been proposed to solve each problem.

Virtual address caches can provide faster access times than physical address caches, because translation is only required on cache misses. However, because we don't check the translation information on each cache access, maintaining reference and dirty bits is more difficult. In this paper we examine the trade-offs in supporting reference and dirty bits in a virtual address cache. We use measurements from a uniprocessor SPUR prototype to evaluate different alternatives. The prototype's built-in performance counters make it easy to determine the frequency of important events and to calculate performance metrics.

Object-oriented databases provide new kinds of data semantics in terms of inheritance and structural relationships. This paper examines how to use these additional semantics to obtain more effective object buffering and clustering. We use the information collected from real-world object-oriented applications, the Berkeley CAD Group's OCT design tools, as the basis for a simulation model with which to investigate alternative buffering and clustering strategies. Observing from our measurements that real CAD applications exhibit high data read to write ratios, we propose a run-time clustering algorithm whose initial evaluation indicates that system response time can be improved by a factor of 200% when the read/write ratio is high. We have also found it useful to limit the amount of I/O allowed to the clustering algorithm as it examines candidate pages for clustering at run-time. Basically, there is little performance distinction between limiting reclustering to a few I/Os or many, so a low limit on I/O appears to be acceptable. We also examine, under a variety of workload assumptions, context-sensitive buffer replacement policies with alternative prefetching policies.

Following a brief review of the fundamentals of disk system architecture, the characteristics of the applications that demand high I/O system performance are described. Conventional ways to improve disk performance are discussed. New developments in disk array systems are introduced, and controller architectures are described.>

Abstract The Version Server is a system for managing the versions and configurations of design descriptions as they change over time. In this paper we focus on the design and implementation of such a system, which we have built at U.C. Berkeley. The data model supported and the browser application are introduced to illustrate the system's user and application interface. The design decisions and details of the internal architecture are described and the system's performance is evaluated. For structure‐oriented queries, such as ‘traverse an entire chip's design hierarchy’, the Version Server is about five times as fast as comparable design management systems that store their design objects as files in a hierarchical file system.

A program, called EPOXY, which sizes a circuit's transistors to satisfy performance and area constraints is discussed. If these cannot be met, the program considers small circuit changes in an effort to meet the constraints. Several CMOS examples demonstrate how EPOXY applies these heuristics to meet difficult timing constraints, power requirements, and cell width and height limitations. Compact layout and aspect-ratio requirements are handled by a virtual grid area model. From an implementation viewpoint, EPOXY's underlying equation representation of circuit performance automatically provides critical path information and allows rapid modification of the circuit structure. When EPOXY was applied to a CMOS 16-bit adder, a speed improvement of 23% was achieved over transistor sizing alone while satisfying a height constraint. Similarly, the speed of a dynamic CMOS PLA was improved by 10% and that of an array of CMOS JK flip-flops by 23%.>

An automatic tool that heuristically determines a good partitioning of a single large programmable logic array (PLA) into a PLA with a smaller number of encoded outputs (and usually fewer product terms), followed by a set of decoders to regenerate the original outputs, has been developed. Initial results using logic descriptions of processor chips and a benchmark set of industrial PLAs show area savings of up to 35% and delay reductions of up to 45%. The approach can be considered an alternative to Boolean decomposition and factoring in multilevel logic synthesis.>

Trace-driven simulation is used to analyze the memory reference patterns of write-shared data in several parallel applications. A characterization of write sharing is developed (based on the notion of a write run), and the traces are examined using metrics derived from the characterization. The results indicate that the amount of write sharing in all programs is small, and that it is characterized by short-to-medium sequences of per-processor references, with little contention for either data or locks. A simple model of write sharing is developed from the write run characterization. By applying the results of the sharing analysis to the model, weighted by machine-specific cycle costs for carrying out coherency-related bus-operations, relative protocol performance can be estimated. These results are compared to those from detailed architectural simulations.>

Increasing performance of CPUs and memories will be squandered if not matched by a similar performance increase in I/O. While the capacity of Single Large Expensive Disks (SLED) has grown rapidly, the performance improvement of SLED has been modest. Redundant Arrays of Inexpensive Disks (RAID), based on the magnetic disk technology developed for personal computers, offers an attractive alternative to SLED, promising improvements of an order of magnitude in performance, reliability, power consumption, and scalability. This paper introduces five levels of RAIDs, giving their relative cost/performance, and compares RAID to an IBM 3380 and a Fujitsu Super Eagle.

Design methodologies specify the sequence in which verification programs must be successfully executed to determine a design's correctness. We present a mechanism for assisting designers in adhering to their methodology, specified as Prolog rules that must match a verification event log. A new version cannot be released if a methodology violation is detected. Designers can query for the source of their violation. The system has been implemented within a prototype Version Server.

In the design of SPUR, a high-performance multiprocessor workstation, the use of large caches and hardware-supported cache consistency suggests a new approach to virtual address translation. By performing translation in each processor's virtually-tagged cache, the need for separate translation lookaside buffers (TLBs) is eliminated. Eliminating the TLB substantially reduces the hardware cost and complexity of the translation mechanism and eliminates the translation consistency problem. Trace-driven simulations show that normal cache behavior is only minimally affected by caching page table entries, and that in many cases, using a separate device would actually reduce system performance.

We present an ownership-based multiprocessor cache consistency protocol, designed for implementation by a single chip VLSI cache controller. The protocol and its VLSI realization are described in some detail, to emphasize the important implementation issues, in particular, the controller critical sections and the inter- and intra-cache interlocks needed to maintain cache consistency. The design has been carried through to layout in a P-Well CMOS technology

Abstract We describe the implementation of a flexible data storage system for the UNIX environment that has been designed as an experimental vehicle for building database management systems. The storage component forms a foundation upon which a variety of database systems can be constructed including support for unconventional types of data. We describe the system architecture, the design decisions incorporated within its implementation, our experiences in developing this large piece of software, and the applications that have been built on top of it.

With the availability of very large, relatively inexpensive main memories, it is becoming possible keep large databases resident in main memory In this paper we consider the changes necessary to permit a relational database system to take advantage of large amounts of main memory We evaluate AVL vs B+-tree access methods for main memory databases, hash-based query processing strategies vs sort-merge, and study recovery issues when most or all of the database fits in main memory As expected, B+-trees are the preferred storage mechanism unless more than 80--90% of the database fits in main memory A somewhat surprising result is that hash based query processing strategies are advantageous for large memory situations

We identify the roles played by design versions and alternatives in an engineering database. The obvious way to implement versions is to maintain each in a separate collection of files. Because several versions must be kept on line in a design environment, the approach leads to large disk requirements. We develop B-tree-based storage structures to encode versions as ``negative'' differential files. Our objective is to keep the disk requirements small. We discuss the effect of enormous amounts of cheap archival storage (write-once optical digital disks) on the proposed structures. We have implemented versions in the Wisconsin storage system (WiSS), an experimental database component developed at the University of Wisconsin-Madison.

In this paper we treat the problem of subdividing a database and allocating the fragments to the sites in a distributed database system in order to maximize non-duplicative parallelism. Our goal is to establish a conceptual framework for distributing data without being committed to specific cost models.We introduce the concept of "local sufficiency" as a measure of parallelism, and show how certain classes of queries lead naturally to irredundant partitions of a database that are locally sufficient. For classes of queries for which no irredundant distribution is locally sufficient, we offer ways to introduce redundancy in achieving local sufficiency

We present a conceptual framework in which a database's intra- and interrecord set access requirements are specified as a constrained assignment of abstract characteristics (“evaluated,” “indexed,” “clustered,” “well-placed”) to logical access paths. We derive a physical schema by choosing an available storage structure that most closely provides the desired access characteristics. We use explicit replication of schema objects to reduce the access cost along certain paths, and analyze the trade-offs between increased update overhead and improved retrieval access. Finally, we given an algorithm to select storage structures for a CODASYL 78 DBTG schema, given its access requirements specification.

We describe an approach to managing information about VLSI designs, founded upon database system methods. A database component provides a low-level flat-file interface to stored data. Built on top is a design data management system, supporting the hierarchical construction of a design from primitive cells, and organizing data about alternative design representations and versions. Programs to provide a tailored interface to design data are also provided. The system simplifies the rapid construction of new design tools by taking responsibility for design data management.

In the pure relational model, duplicate tuples are automatically eliminated. Some real world languages such as DAPLEX, however, give users control over duplicate elimination. This paper extends the relational model to include multiset relations, i.e., relations with duplicate tuples. It considers three formalisms for expressing queries in this model: extended relational algebra, tableaux, and DAPLEX. It shows that, as in the original algebra, the equivalence problem for conjunctive expressions in the extended algebra can be solved using tableaux, and is NP-complete. Finally, it demonstrates that the extended algebra and DAPLEX have essentially the same expressiveness relative to conjunctive expressions.

A “decompilation” algorithm is developed to transform a program written with the procedural operations of CODASYL DML into one which interacts with a relational system via a nonprocedural query specification. An Access Path Model is introduced to interpret the semantic accesses performed by the program. Data flow analysis is used to determine how FIND operations implement semantic accesses. A sequence of these is mapped into a relational query and embedded into the original program. The class of programs for which the algorithm succeeds is characterized.

Design and Access Path Data Models are presented to form an integrated framework for logical and physical database design in a heterogeneous database environment. This paper focuses on the physical design process. First, a physical design is specified in terms of general properties of access paths, independent of implementation details. Then, a design is realized by mapping the specification into the storage structures of a particular database system. Algorithms for assigning the properties to logical access paths and for realizing a CODASYL 78 DBTG schema are given.