14118439
Inferring link weights using end-to-end measurements
We describe a novel constraint-based approach to approximate ISP link weights using only end-to-end measurements. Common routing protocols such as OSPF and IS-IS choose least-cost paths using link weights, so inferred weights provide a simple, concise, and useful model of intradomain routing. Our approach extends router-level ISP maps, which include only connectivity, with link weights that are consistent with routing. Our inferred weights agree well with observed routing: while our inferred weights fully characterize the set of shortest paths between 84--99% of the router-pairs, alternative models based on hop count and latency do so for only 47--81% of the pairs.
1591428
User-level interprocess communication for shared memory multiprocessors
Interprocess communication (IPC), in particular IPC oriented towards local cornmzmzcation (between address spaces on the same machine), has become central to the design of contemporary operating systems. IPC has traditionally been the responsibility of the kernel, but kernel-based IPC has two inherent problems First, its performance is architecturally limited by the cost of invoking the kernel and reallocating a processor from one address space to another. Second, applications that need inexpensive threads and must provide their own thread management encounter functional and performance problems stemming from the interaction between kernellevel communication and user-level thread management. On a shared memory multiprocessor, these problems can be solved by moving the communication facilities out of the kernel and supporting them at the user level within each address space. Communication performance is improved since kernel invocation and processor reallocation can be avoided when communicating between address spaces on the same machine. These observations motivated User-Level Remote Procedure Call (URPC) URPC combines a fast cross-address space communication protocol using shared memory with lightweight threads managed at the user level, This structure allows the kernel to be bypassed during cross-address space communication. The programmer sees threads and RPC through a conventional interface, though with unconventional performance,
10812673
A Quantitative Analysis of Disk Drive Power Management in Portable Computers
With the advent and subsequent popularity of portable computers, power management of system components has become an important issue. Current portable computers implement a number of power reduction techniques to achieve a longer battery life. Included among these is spinning down a disk during long periods of inactivity. In this paper, we perform a quantitative analysis of the potential costs and benefits of spinning down the disk drive as a power reduction technique. Our conclusion is that almost all the energy consumed by a disk drive can be eliminated with little loss in performance. Although on current hardware, reliability can be impacted by our policies, the next generation of disk drives will use technology (such as dynamic head loading) which is virtually unaffected by repeated spinups. We found that the optimal spindown delay time, the amount of time the disk idles before it is spun down, is 2 seconds. This differs significantly from the 3-5 minutes in current practice by industry. We will show in this paper the effect of varying the spindown delay on power consumption; one conclusion is that a 3-5 minute delay results in only half of the potential benefit of spinning down a disk.
52829694
Reverse engineering the Internet
To provide insight into Internet operation and performance, recent efforts have measured various aspects of the Internet, developing and improving measurement tools in the process. In this paper, we argue that these independent advances present the community with a startling opportunity: the collaborative reverse-engineering of the Internet. By this, we mean annotating a map of the Internet with properties such as: client populations, features and workloads; network ownership, capacity, connectivity, geography and routing policies; patterns of loss, congestion, failure and growth; and so forth. This combination of properties it greater than the sum of its parts, and exposes the attributes of network design easily overlooked by simpler, uncorrelated models. We argue that reverse engineering the Internet is feasible based on continuing improvements in measurement techniques, the potential to infer new properties from external measurements, and an accounting of the resources required to complete the process.
2515359
The case for informed transport protocols
Wide-area distributed applications are frequently limited by the performance of Internet data transfers. We argue that the principle cause of this effect is the poor interaction between host-centric congestion control algorithms and the realities of today's Internet traffic and infrastructure. In particular when the duration of a network flow is short, then using end-to-end feedback to determine network conditions will be extremely inefficient. We propose an incremental approach to the problem, in which congestion information is shared among many co-located hosts and transport protocols make informed congestion control decisions. We argue that the resulting system can potentially improve the performance experienced by each network user as well as the overall efficiency of the network.
38998802
Measuring ISP topologies with rocketfuel
To date, realistic ISP topologies have not been accessible to the research community, leaving work that depends on topology on an uncertain footing. In this paper, we present new Internet mapping techniques that have enabled us to measure router-level ISP topologies. Our techniques reduce the number of required traces compared to a brute-force, all-to-all approach by three orders of magnitude without a significant loss in accuracy. They include the use of BGP routing tables to focus the measurements, the elimination of redundant measurements by exploiting properties of IP routing, better alias resolution, and the use of DNS to divide each map into POPs and backbone. We collect maps from ten diverse ISPs using our techniques, and find that our maps are substantially more complete than those of earlier Internet mapping efforts. We also report on properties of these maps, including the size of POPs, distribution of router outdegree, and the interdomain peering structure. As part of this work, we release our maps to the community.
1295439
Analysis of Timeliness Requirements in Safety-Critical Systems
Requirements analysis plays a vital role in the development of safetycritical systems since any faults in the requirements specification will corrupt the subsequent stages of system development. Experience in safetycritical systems has shown that faults in the requirements can and do cause accidents. This paper presents a general framework for the analysis of timeliness requirements in safetycritical systems. The analysis is performed in two distinct phases; for each phase we propose different formalisms and time structures. The specification of the timing constraints is based on an event/action model. To illustrate the proposed approach an example based on a train set crossing is presented.
2844388
Protective Wrapper Development: A Case Study
We have recently proposed a general approach to engineering protective wrappers as a means of detecting errors or unwanted behaviour in systems employing an OTS (Off-The-Shelf) item, and launching appropriate recovery actions. This paper presents results of a case study in protective wrapper development, using a Simulink model of a steam boiler system together with an OTS PID (Proportional, Integral and Derivative) controller. The protective wrappers are developed for the model of the system in such a way that they allow detection and tolerance of typical errors caused by unavailability of signals, violations of constraints, and oscillations.
9257653
Can design faults be tolerated?
The short answer to the question posed by the title is “Yes”. A more cautious, and less simplistic, response would be that in certain circumstances, with appropriate provision of redundancy and allied supporting mechanisms, it is certainly possible to provide a measure of tolerance to faults of design. However, although this question may serve as an appropriate title, and starting point for discussion, it does not adequately address the significant issues concerning the application of fault tolerance techniques to deficiencies of design. As is usually the case, the first, and perhaps most important, step is to ask the right questions. In this paper, I propose to substitute five further questions in place of my title and, in answering those questions, will argue the case for the use of design fault tolerance in the development of reliable computing systems. In so doing I hope to justify the short and cautious answers already given above.
21451715
Reliable Software: A Selective Annotated Bibliography
A total of 64 references to papers, books and conference proceedings on the subject of software reliability have been selected. Each of these references is provided with an annotation consisting of a paragraph of commentary. Sections of the bibliography are devoted to requirements definition, programming methodology, certification, fault-tolerance and reliability modelling.
16865512
Wrapping the future
Enclosing a component within a software “wrapper” is a well-established way of adapting components for use in new environments. This paper presents an overview of an experimental evaluation of the use of a wrapper to protect against faults arising during the (simulated) operation of a practical and critical system; the specific context is a protective wrapper for an off-the-shelf software component at the heart of the control system of a steam raising boiler. Encouraged by the positive outcomes of this experimentation we seek to position protective wrappers as a basis for structuring the provision of fault tolerance in component-based open systems and networks. The paper addresses some key issues and developments relating wrappers to the provision of dependability in future computing systems.