bluuebunny/crossref_metadata_2025 huggingface dataset:
Open Signaling for ATM, INTERNET and Mobile Networks (OPENSIG'98)
Authors: Campbell Andrew T. , Katzela Irene , Miki Kazuho , Vicente John
Published: October 2004

The ability to rapidly create and deploy new transport, control and management architectures in response to new service demands is a key factor driving the programmable networking community. Competition between service providers may hinge on the speed at which one provider can respond to new market demands over another. The notion of open programmable networks is having broad impact on service providers and vendors across a range of telecommunication sectors calling for major advances in open network control architecture, network programmability and distributed systems technology. In this paper we discuss the origins of the Open Signalling Working Group (OPENSIG) and present a summary of the fifth Workshop on Open Signaling for ATM, Internet and Mobile Networks (OPENSIG'98), which was held at the University of Toronto, Ontario, October, 1998. We also discuss a number of new initiatives in the area of open programmable networks that have recently emerged.
Embedding security policies into a distributed computing environment
Authors: Halfmann Udo , Kühnhauser Winfried E.
Published: October 2004

This paper discusses the implementation of security policies in multipolicy systems. Multipolicy systems are systems supporting a multitude of security policies, each policy governing the applications within its own and precisely defined security domain.The paper argues that within multipolicy systems, traditional approaches for implementing security policies such as security kernels are both too weak and too strong. In order to support this thesis, we will discuss architectural issues of the implementation of policy separation, policy persistency, total mediation and putting off-the-shelf applications under the control of security policies. Whenever our statements are illustrated by examples, these examples are taken from a case study we implemented for the OSF Distributed Computing Environment.
A fully reusable class of objects for synchronization and communication in Ada 95
Authors: de Bondeli Patrick
Published: October 2004

This paper presents a very general class which can be reused to specify and implement any type exporting synchronization or communication properties. The new Ada 95 features modelling inheritance, polymorphism and hierarchies of library units are used extensively in describing the architecture of the class and other new features (access to subprograms, protected types, …) are used for the specification and implementation of the components of the class.Section 2 presents the general architecture of our class. Sections 3, 4, 5 respectively give examples of specification, use and implementation of its components. Section 6 concludes on recalling the full role of formal techniques in our approach (they appear in the present paper only to show that the semantics of our class is defined at a more abstract level than its implementation) and discussing a few interesting points about the way Ada 95 is used here.
Incremental view maintenance in object-oriented databases
Authors: Alhajj Reda , Polat Faruk
Published: October 2004

A database management system should support views to facilitate filtering of information in order to have only necessary and required information available to users with minimal delay. Although a lot of research efforts concentrated on views within the conventional relational model, much more effort is required when object-oriented models are considered. However, supporting views is only a step forward in achieving the purpose that requires improving the performance of the system by considering incremental maintenance of views instead of recomputing a view from scratch each time it is accessedIn this paper, we introduce a model that facilitates incremental maintenance of single-class-based object-oriented views by employing the deferred update mode that has proved to be more suitable for object-oriented databases in general. For that purpose, we categorize classes into base and brother classes corresponding to classes originally present in the database and those introduced as views, respectively. To each class, we add a modification list that keeps related modifications during different intervals. An interval starts with the creation or update of a view and ends with the creation or update of another view. A modification list is empty as long as no views depend on its class. Further, we introduce some algorithms that locate modifications done on related classes while trying to compute a given view incrementally. Finally, we give a theoretical justification showing that, in general, the introduced algorithms perform much better than doing computation from scratch each time a view is accessed.
A readable TCP in the Prolac protocol language
Authors: Kohler Eddie , Kaashoek M. Frans , Montgomery David R.
Published: October 2004

Prolac is a new statically-typed, object-oriented language for network protocol implementation. It is designed for readability, extensibility, and real-world implementation; most previous protocol languages, in contrast, have been based on hard-to-implement theoretical models and have focused on verification. We present a working Prolac TCP implementation directly derived from 4.4BSD. Our implementation is modular---protocol processing is logically divided into minimally-interacting pieces; readable---Prolac encourages top-down structure and naming intermediate computations; and extensible---subclassing cleanly separates protocol extensions like delayed acknowledgements and slow start. The Prolac compiler uses simple global analysis to remove expensive language features like dynamic dispatch, resulting in end-to-end performance comparable to an unmodified Linux 2.0 TCP.
KHIP—a scalable protocol for secure multicast routing
Authors: Shields Clay , Garcia-Luna-Aceves J. J.
Published: October 2004

We present Keyed HIP (KHIP), a secure, hierarchical multicast routing protocol. We show that other shared-tree multicast routing protocols are subject to attacks against the multicast routing infrastructure that can isolate receivers or domains or introduce loops into the structure of the multicast routing tree. KHIP changes the multicast routing model so that only trusted members are able to join the multicast tree. This protects the multicast routing against attacks that could form branches to unauthorized receivers, prevents replay attacks and limits the effects of flooding attacks. Untrusted routers that are present on the path between trusted routers cannot change the routing and can mount no denial-of-service attack stronger than simply dropping control messages. KHIP also provides a simple mechanism for distributing data encryption keys while adding little overhead to the protocol.
A flexible model for resource management in virtual private networks
Authors: Duffield N. G. , Goyal Pawan , Greenberg Albert , Mishra Partho , Ramakrishnan K. K. , van der Merive Jacobus E.
Published: October 2004

As IP technologies providing both tremendous capacity and the ability to establish dynamic secure associations between endpoints emerge, Virtual Private Networks (VPNs) are going through dramatic growth. The number of endpoints per VPN is growing and the communication pattern between endpoints is becoming increasingly hard to forecast. Consequently, users are demanding dependable, dynamic connectivity between endpoints, with the network expected to accommodate any traffic matrix, as long as the traffic to the endpoints does not overwhelm the rates of the respective ingress and egress links. We propose a new service interface, termed a
hose
, to provide the appropriate performance abstraction. A hose is characterized by the aggregate traffic to and from one endpoint in the VPN to the set of other endpoints in the VPN, and by an associated performance guarantee.Hoses provide important advantages to a VPN customer: (i) flexibility to send traffic to a set of endpoints without having to specify the detailed traffic matrix, and (ii) reduction in the size of access links through multiplexing gains obtained from the natural aggregation of the flows between endpoints. As compared with the conventional point to point (or customer-pipe) model for managing QoS, hoses provide reduction in the state information a customer must maintain. On the other hand, hoses would appear to increase the complexity of the already difficult problem of resource management to support QoS. To manage network resources in the face of this increased uncertainty, we consider both conventional statistical multiplexing techniques, and a new
resizing
technique based on online measurements.To study these performance issues, we run trace driven simulations, using traffic derived from AT&T's voice network, and from a large corporate data network. From the customer's perspective, we find that aggregation of traffic at the hose level provides significant multiplexing gains. From the provider's perspective, we find that the statistical multiplexing and resizing techniques deal effectively with uncertainties about the traffic, providing significant gains over the conventional alternative of a mesh of statically sized customer-pipes between endpoints.
An analysis of BGP convergence properties
Authors: Griffin Timothy G. , Wilfong Gordon
Published: October 2004

The Border Gateway Protocol (BGP) is the
de facto
inter-domain routing protocol used to exchange reachability information between Autonomous Systems in the global Internet. BGP is a path-vector protocol that allows each Autonomous System to override distance-based metrics with policy-based metrics when choosing best routes. Varadhan
et al.
[18] have shown that it is possible for a group of Autonomous Systems to independently define BGP policies that together lead to BGP protocol oscillations that never converge on a stable routing. One approach to addressing this problem is based on
static analysis
of routing policies to determine if they are safe. We explore the worst-case complexity for convergence-oriented static analysis of BGP routing policies. We present an abstract model of BGP and use it to define several global sanity conditions on routing policies that are related to BGP convergence/divergence. For each condition we show that the complexity of statically checking it is either NP-complete or NP-hard.
The end-to-end effects of Internet path selection
Authors: Savage Stefan , Collins Andy , Hoffman Eric , Snell John , Anderson Thomas
Published: October 2004

The path taken by a packet traveling across the Internet depends on a large number of factors, including routing protocols and per-network routing policies. The impact of these factors on the end-to-end performance experienced by users is poorly understood. In this paper, we conduct a measurement-based study comparing the performance seen using the "default" path taken in the Internet with the potential performance available using some alternate path. Our study uses five distinct datasets containing measurements of "path quality", such as round-trip time, loss rate, and bandwidth, taken between pairs of geographically diverse Internet hosts. We construct the set of potential alternate paths by composing these measurements to form new synthetic paths. We find that in 30-80% of the cases, there is an alternate path with significantly superior quality. We argue that the overall result is robust and we explore two hypotheses for explaining it.
Development of a TCP/IP for the IBM/370
Authors: Brandriff Robert K. , Lynch Clifford A. , Needleman Mark H.
Published: October 2004

This paper describes the design and implementation decisions that have been made in developing software to support the DARPA TCP/IP protocols for the IBM OS/370 environment at the University of California Division of Library Automation. The implementation is designed to support over 100 concurrent TCP connections, all of which are managed by a single program, which acts as a specialized sub-operating system. The system is optimized for line-by-line or screen-by-screen terminal traffic rather than character-by-character traffic. In addition, this TCP is designed to exploit the availability of the large main storage and processor speed available on the IBM/370.

TCP/IP is generally considered to be a mature protocol specification; however, in the course of our implementation we found several parts to be either ambiguous or problematic — in particular, error handling and notification, ICMP and its relationship to other protocols, and synchronization of data flow with TCP callers.

We also discuss problems encountered in trying to replace hardwired terminals in a public access environment with TCP and TELNET, and some protocol changes that would make these protocols more hospitable to our environment.
An algorithm for distributed computation of a spanningtree in an extended LAN
Authors: Perlman Radia
Published: October 2004

A protocol and algorithm are given in which bridges in an extended Local Area Network of arbitrary topology compute, in a distributed fashion, an acyclic spanning subset of the network.

The algorithm converges in time proportional to the diameter of the extended LAN, and requires a very small amount of memory per bridge, and communications bandwidth per LAN, independent of the total number of bridges or the total number of links in the network.

Algorhyme

I think that I shall never see A graph more lovely than a tree.

A tree whose crucial property Is loop-free connectivity.

A tree which must be sure to span So packets can reach every LAN.

First the Root must be selected By ID it is elected.

Least cost paths from Root are traced. In the tree these paths are placed.

A mesh is made by folks like me Then bridges find a spanning tree.
Modeling physical layer protocols using communicating finite state machines
Authors: Gouda Mohamed G. , The Khe-Sing
Published: October 2004

We illustrate the usefulness of communicating finite state machines in modeling a number of physical layer protocols that include (i) an asynchronous start-stop protocol and (ii) a protocol for synchronous transmission with modems. Each protocol is modeled as a network of four finite state machines that communicate by exchanging messages over unbounded, FIFO channels. (Two machines are used to model the protocol itself, while the other two are used to model its interface to the upper data link protocol in the protocol hierarchy.) We outline a methodology to verify communication boundedness and progress for each protocol model. The methodology is based on three techniques that were proposed earlier to verify networks of communicating finite state machines; they are network decomposition, machine equivalence, and closed covers.
Domain names (panel session, abstract only)
Authors: Comer Douglas E.
Published: October 2004

The DARPA Domain Name project is an attempt to move from a centralized naming authority to a distributed one. In essence, the domain system computes a single binding from a character string known as a host
name
to another string known as the host
address
(a 32-bit integer). Besides the syntactic changes in names, the chief difference between the old-style names and domain names is that in the old system, a database containing the name-to-address bindings was distributed to each host where bindings were performed locally, while in the domain system computation of the name-to-address binding uses the internet to contact search the hierarchy of domains until a server is found that can perform the binding. Unfortunately, to make the system efficient, servers cache bindings they look up, and clients begin a search by contacting the nearest “leaf” server to avoid searching the hierarchy. If sufficient memory is available, the cache at a server corresponds exactly to old-style host tables.

The domain scheme raises other questions. In principle, the hierarchical structure of domain names permits easy delegation of naming authority because it allows names within independent subtrees to be assigned by independent organizations. In practice, however, the hierarchical scheme collects together organizations under fixed top-level domains. Because extremely small organizations cannot afford to maintain a domain name server, they must be supported by (and obey the authority of) a domain server for the subhierarchy under which they lie.

A hierarchical organization of names also imposes restrictions on the use of the system. For example, even though domain name servers contain (name, address) pairs, it is impossible to locate the desired binding given only the address.
Chairman's remarks (panel session, abstract only)
Authors: Buttle T. C.
Published: October 2004

From its experimental 1968 inception in ARPANET, followed by CCITT standardization of the X.25 protocol in 1976, packet switching now provides inexpensive worldwide data communications capabilities for its subscribers. Customer connections to public packet switched network services are increasing at a phenomenal rate, typically 30-40% year over year with no foreseen slowdown. This 2-3 year doubling effect presents numerous challenges to network operators in trying to effectively support and evolve their packet switched networks while simultaneously increasing customer service levels.

This Panel presents an overview of current customer packet switching applications and then focuses on how network operators are innovatively meeting the challenges presented by high growth on the operation, control, support, configuration and evolution of their packet switched networks.
A path-oriented routing strategy for packet switching networks with end-to-end protocols
Authors: Aubin R. , Ng P.
Published: October 2004

A path-oriented routing strategy is proposed for packet switching networks with end-to-end internal protocols. It allows switch pairs to communicate over multiple paths (for better network throughput), while maintaining knowledge of user connections at the network's endpoints only. The most significant aspect of this strategy lies in its flow assignment method. A distributed loop-free shortest path algorithm assigns a number to a path at the time it is created and this number remains valid through shortest path changes. Consequently, existing traffic can be maintained on existing paths, while new traffic is assigned to the current shortest paths. Stable multiple path routing is thus achieved without packet disordering. Abnormal conditions such as trunk failure and recovery and trunk congestion are dealt with by tagging routing updates with update causes. Simulation of this routing strategy shows that maximum network throughput (under a certain congestion constraint) can be increased substantially compared to a single path routing strategy.
Host groups
Authors: Cheriton David R. , Deering Stephen E.
Published: October 2004

The extensive use of local networks is beginning to drive requirements for internetwork facilities that connect these local networks. In particular, the availability of multicast addressing in many local networks and its use by sophisticated distributed applications motivates providing multicast across internetworks.

In this paper, we propose a model of service for multicast in an internetwork, describe how this service can be used, and describe aspects of its implementation, including how it would fit into one existing internetwork architecture, namely the US DoD Internet Architecture.
1 2
ISDN architecture
Authors: Eigen Daryl J.
Published: October 2004

ISDN is an acronym for Integrated Services Digital Network. ISDN embodies world-wide standards that will engender the technology necessary to weave the fabric of a global communications network and provide the foundation for information age services. Siemens has a cost effective ISDN introduction strategy that will allow ISDN to interwork with existing switching systems, current transmission networks, and nonproprietary Customer Premises Equipment (CPE), as well as to interface with operational and administration systems. This strategy also entails the development of ISDN terminals, terminal adapters and service capabilities so that the end user can quickly realize the benefits of ISDN. Siemens is forming partnerships with Bell Operating Telephone Companies, like Wisconsin Bell Telephone Co., to perform market research of the end users to better determine their ISDN needs and applications. ISDN architecture is briefly discussed to provide a basis for some examples on how ISDN and network components can be combined to meet customer needs.
Redistribution in distributed Ada
Authors: James Scott
Published: October 2004

In this paper we will demonstrate how Ada and its Distributed Annex may be used to relocate concurrent objects in a distributed dataflow application. This relocation mechanism will provide the capability of providing both passive and active fault tolerance. Special care will be taken to demonstrate how errors are trapped and propagated across partitions containing multiple threads of execution.
A formal model of the Ada Ravenscar tasking profile; delay until
Authors: Lundqvist Kristina , Asplund Lars
Published: October 2004

The definition of the Ravenscar Tasking Profile for Ada 95 provides a definition of a tasking runtime system with deterministic behaviour and low enough complexity to permit a formal description and verification of the model. A complete run-time system is being modeled using the real-time model checker U
PPAAL
, and this work describes the handling of
delay until.
Since scheduling is not yet modelled a simple non-preemptive scheduler has been used when verifying the delay queue.
Verification of requirements for saftey-critical software
Authors: Carpenter Paul B.
Published: October 2004

The purpose of this paper is to describe a methodology for the verification of safety-critical software. The methodology is implemented with use-cease modeling notation of the Unified Modeling Language (UML). The methodology also contains techniques for creating requirements-based test cases from scenarios. The test cases are formatted for test scripts that exercised the software.
A truly implementation independent GUI development tool
Authors: Carlisle Martin C.
Published: October 2004

Over the last few years, graphical user interface programming has become increasingly prevalent. Many libraries and languages have been developed to simplify this task. Additionally, design tools have been created that allow the programmer to "draw" their desired interface and then have code automatically generated. Unfortunately, use of these tools locks the programmer into a particular implementation. Even if the tool targets a multi-platform library (e.g. Tcl/Tk or JVM), the flexibility of the result is constrained. We present a truly implementation and platform independent solution. RAPID generates Ada code targeted to an object-oriented set of graphical user interface specifications with absolutely no implementation dependent information. The pattern used to derive these specifications is an improvement over the "Abstract Factory" Pattern, as it allows both the specification and implementation to take advantage of inheritance. The user can then select an implementation (for example, Tcl/Tk or JVM) at compile time. RAPID itself is also written using the same specifications; therefore it requires no modification to target a new implementation or to use a new implementation itself. RAPID is currently being used to design the user interface for a satellite ground station.
“Transitioning an ASIS application
Authors: Wisniewski Joseph R.
Published: October 2004

ASIS (Ada Semantic Interface Specification) applications written to the "Version 1" standard or subsequent 1.X permutations of this standard (such as Version 1.1.1) were developed with and for Ada83. Porting such applications to the Ada95 ASIS standard, Version 2.0, is a non-trivial task. Such an effort needs to address the major changes to the semantic abstractions of the language as represented by the Version 2.0 Ada95 ASIS specification.This paper is an experience report that documents an approach used to port several Version 1.0 ASIS applications to Version 2.0 compliance. A methodology for "finding" the mappings between the two specifications is documented along with the results (a mapping table of the ASIS queries) of that approach.
Code analysis of saftey-critical and real-time software using ASIS
Authors: Colket William Currie
Published: October 2004

The Ravenscar Profile is a restricted tasking profile that supports applications requiring separate threads of control yet would satisfy the certification requirements of high-integrity (safety-critical) real-time systems. If the Ravenscar Profile were to be used for systems having safety-critical and real-time requirements, it would be valuable to demonstrate that the application satisfies the restrictions. Code analysis is an important technique to support this demonstration. Ada Semantic Interface Specification (ASIS) based tools provide an excellent capability for the automatic identification of violations to that set of the Ravenscar Profile restrictions, which can be determined through static code analysis. All but one of these restrictions can be identified using static code analysis using ASIS. This paper provides an approach to building such an ASIS-based tool. This tool might promote the use of automatic tools for the analysis of the Ravenscar Profile and other tasking profiles to support safety-critical and real-time requirements. This paper should be viewed as work in progress.
Building Tcl-Tk GUIs for HRT-HOOD systems
Authors: Díaz Martín Juan Carlos , Veloso Isidro Irala , Rodríguez García José Manuel
Published: October 2004

This work explores Tcl-Tk 8.0 as a building tool for script-based GUIs in Ada95 real-time systems. Tcl-Tk 8.0 is a library that makes graphic programming easier, but it suffers from being non-thread-safe. An application architecture is proposed, the deferred server, which provides transparent use of Tcl-Tk to multithreaded Ada95 applications via TASH, a thick binding that allows Ada95 single-threaded code to use Tcl-Tk. We find that only a minimal extension to Tcl-Tk 8.0 and TASH is required to support it, while a successful prototype has been implemented based on these ideas. Likewise, the early integration of Tcl-Tk graphic user interfaces in HRT-HOOD designs is examined; unfortunately, in this respect, we conclude that this is not feasible. However, a HRT-HOOD conform distributed configuration is outlined in wich the user interface becomes a multithreaded remote service based on the deferred server architecture.
Extending Ada to assist multiprocessor embedded development
Authors: Lowe Tony
Published: October 2004

The Ada language supports high level techniques for inter-processor communication and also supports low level implementation of data address manipulation. The language however requires the software developers to manage the low-level manipulations. This paper proposes a technique to incorporate the high level concepts with low level implementation for multiprocessor communications.
Manageability, availability and performance in Porcupine
Authors: Saito Yasushi , Bershad Brian N. , Levy Henry M.
Published: October 2004

This paper describes the motivation, design, and performance of Porcupine, a scalable mail server. The goal of Porcupine is to provide a highly available and scalable electronic mail service using a large cluster of commodity PCs. We designed Porcupine to be easy to manage by emphasizing dynamic load balancing, automatic configuration, and graceful degradation in the presence of failures. Key to the system's manageability, availability, and performance is that sessions, data, and underlying services are distributed homogeneously and dynamically across nodes in a cluster.
On the scale and performance of cooperative Web proxy caching
Authors: Wolman Alec , Voelker M. , Sharma Nitin , Cardwell Neal , Karlin Anna , Levy Henry M.
Published: October 2004

While algorithms for cooperative proxy caching have been widely studied, little is understood about cooperative-caching performance in the large-scale World Wide Web environment. This paper uses both trace-based analysis and analytic modelling to show the potential advantages and drawbacks of inter-proxy cooperation. With our traces, we evaluate quantitatively the performance-improvement potential of cooperation between 200 small-organization proxies within a university environment, and between two large-organization proxies handling 23,000 and 60,000 clients, respectively. With our model, we extend beyond these populations to project cooperative caching behavior in regions with millions of clients. Overall, we demonstrate that cooperative caching has performance benefits only within limited population bounds. We also use our model to examine the implications of future trends in Web-access behavior and traffic.
The interactive performance of SLIM
Authors: Schmidt Brian K. , Lam Monica S. , Northcutt J. Duane
Published: October 2004

Taking the concept of thin clients to the limit, this paper proposes that desktop machines should just be simple, stateless I/O devices (display, keyboard, mouse, etc.) that access a shared pool of computational resources over a dedicated interconnection fabric --- much in the same way as a building's telephone services are accessed by a collection of handset devices. The stateless desktop design provides a useful mobility model in which users can transparently resume their work on any desktop console.This paper examines the fundamental premise in this system design that modern, off-the-shelf interconnection technology can support the quality-of-service required by today's graphical and multimedia applications. We devised a methodology for analyzing the interactive performance of modern systems, and we characterized the I/O properties of common, real-life applications (e.g. Netscape, streaming video, and Quake) executing in thin-client environments. We have conducted a series of experiments on the Sun Ray™ 1 implementation of this new system architecture, and our results indicate that it provides an effective means of delivering computational services to a workgroup.We have found that response times over a dedicated network are so low that interactive performance is indistinguishable from a dedicated workstation. A simple pixel encoding protocol requires only modest network resources (as little as a 1Mbps home connection) and is quite competitive with the X protocol. Tens of users running interactive applications can share a processor without any noticeable degradation, and many more can share the network. The simple protocol over a 100Mbps interconnection fabric can support streaming video and Quake at display rates and resolutions which provide a high-fidelity user experience.
Energy-aware adaptation for mobile applications
Authors: Flinn Jason , Satyanarayanan M.
Published: October 2004

In this paper, we demonstrate that a collaborative relationship between the operating system and applications can be used to meet user-specified goals for battery duration. We first show how applications can dynamically modify their behavior to conserve energy. We then show how the Linux operating system can guide such adaptation to yield a battery-life of desired duration. By monitoring energy supply and demand, it is able to select the correct tradeoff between energy conservation and application quality. Our evaluation shows that this approach can meet goals that extend battery life by as much as 30%.
File system usage in Windows NT 4.0
Authors: Vogels Werner
Published: October 2004

We have performed a study of the usage of the Windows NT File System through long-term kernel tracing. Our goal was to provide a new data point with respect to the 1985 and 1991 trace-based File System studies, to investigate the usage details of the Windows NT file system architecture, and to study the overall statistical behavior of the usage data.In this paper we report on these issues through a detailed comparison with the older traces, through details on the operational characteristics and through a usage analysis of the file system and cache manager. Next to architectural insights we provide evidence for the pervasive presence of heavy-tail distribution characteristics in all aspect of file system usage. Extreme variances are found in session inter-arrival time, session holding times, read/write frequencies, read/write buffer sizes, etc., which is of importance to system engineering, tuning and benchmarking.
Deciding when to forget in the Elephant file system
Authors: Santry Douglas S. , Feeley Michael J. , Hutchinson Norman C. , Veitch Alistair C. , Carton Ross W. , Ofir Jacob
Published: October 2004

Modern file systems associate the deletion of a file with the immediate release of storage, and file writes with the irrevocable change of file contents. We argue that this behavior is a relic of the past, when disk storage was a scarce resource. Today, large cheap disks make it possible for the file system to protect valuable data from accidental delete or overwrite.This paper describes the design, implementation, and performance of the Elephant file system, which automatically retains all important versions of user files. Users name previous file versions by combining a traditional pathname with a time when the desired version of a file or directory existed. Storage in Elephant is managed by the system using file-grain user-specified retention policies. This approach contrasts with checkpointing file systems such as Plan-9, AFS, and WAFL that periodically generate efficient checkpoints of entire file systems and thus restrict retention to be guided by a single policy for all files within that file system.Elephant is implemented as a new Virtual File System in the FreeBSD kernel.
Cellular Disco
Authors: Govil Kinshuk , Teodosiu Dan , Huang Yongqiang , Rosenblum Mendel
Published: October 2004

Despite the fact that large-scale shared-memory multiprocessors have been commercially available for several years, system software that fully utilizes all their features is still not available, mostly due to the complexity and cost of making the required changes to the operating system. A recently proposed approach, called Disco, substantially reduces this development cost by using a virtual machine monitor that leverages the existing operating system technology.In this paper we present a system called Cellular Disco that extends the Disco work to provide all the advantages of the hardware partitioning and scalable operating system approaches. We argue that Cellular Disco can achieve these benefits at only a small fraction of the development cost of modifying the operating system. Cellular Disco effectively turns a large-scale shared-memory multiprocessor into a virtual cluster that supports fault containment and heterogeneity, while avoiding operating system scalability bottle-necks. Yet at the same time, Cellular Disco preserves the benefits of a shared-memory multiprocessor by implementing dynamic, fine-grained resource sharing, and by allowing users to overcommit resources such as processors and memory. This hybrid approach requires a scalable resource manager that makes local decisions with limited information while still providing good global performance and fault containment.In this paper we describe our experience with a Cellular Disco prototype on a 32-processor SGI Origin 2000 system. We show that the execution time penalty for this approach is low, typically within 10% of the best available commercial operating system for most workloads, and that it can manage the CPU and memory resources of the machine significantly better than the hardware partitioning approach.
The design and implementation of an intentional naming system
Authors: Adjie-Winoto William , Schwartz Elliot , Balakrishnan Hari , Lilley Jeremy
Published: October 2004

This paper presents the design and implementation of the Intentional Naming System (INS), a resource discovery and service location system for dynamic and mobile networks of devices and computers. Such environments require a naming system that is (i) expressive, to describe and make requests based on specific properties of services, (ii) responsive, to track changes due to mobility and performance, (iii) robust, to handle failures, and (iv) easily configurable. INS uses a simple language based on attributes and values for its names. Applications use the language to describe what they are looking for (i.e., their
intent
), not where to find things (i.e., not hostnames). INS implements a
late binding
mechanism that integrates name resolution and message routing, enabling clients to continue communicating with end-nodes even if the name-to-address mappings change while a session is in progress. INS resolvers self-configure to form an application-level overlay network, which they use to discover new services, perform late binding, and maintain weak consistency of names using soft-state name exchanges and updates. We analyze the performance of the INS algorithms and protocols, present measurements of a Java-based implementation, and describe three applications we have implemented that demonstrate the feasibility and utility of INS.
Design and implementation of a distributed virtual machine for networked computers
Authors: Sirer Emin Gün , Grimm Robert , Gregory Arthur J. , Bershad Brian N.
Published: October 2004

This paper describes the motivation, architecture and performance of a distributed virtual machine (DVM) for networked computers. DVMs rely on a distributed service architecture to meet the manageability, security and uniformity requirements of large, heterogeneous clusters of networked computers. In a DVM, system services, such as verification, security enforcement, compilation and optimization, are factored out of clients and located on powerful network servers. This partitioning of system functionality reduces resource requirements on network clients, improves site security through physical isolation and increases the manageability of a large and heterogeneous network without sacrificing performance. Our DVM implements the Java virtual machine, runs on x86 and DEC Alpha processors and supports existing Java-enabled clients.
Progress-based regulation of low-importance processes
Authors: Douceur John R. , Bolosky William J.
Published: October 2004

MS Manners is a mechanism that employs progress-based regulation to prevent resource contention with low-importance processes from degrading the performance of high-importance processes. The mechanism assumes that resource contention that degrades the performance of a high-importance process will also retard the progress of the low-importance process. MS Manners detects this contention by monitoring the progress of the low-importance process and inferring resource contention from a drop in the progress rate. This technique recognizes contention over any system resource, as long as the performance impact on contending processes is roughly symmetric. MS Manners employs statistical mechanisms to deal with stochastic progress measurements; it automatically calibrates a target progress rate, so no manual tuning is required; it supports multiple progress metrics from applications that perform several distinct tasks; and it orchestrates multiple low-importance processes to prevent measurement interference. Experiments with two low-importance applications show that MS Manners can reduce the degradation of high-importance processes by up to an order of magnitude.
Borrowed-virtual-time (BVT) scheduling
Authors: Duda Kenneth J. , Cheriton David R.
Published: October 2004

Systems need to run a larger and more diverse set of applications, from real-time to interactive to batch, on uniprocessor and multiprocessor platforms. However, most schedulers either do not address latency requirements or are specialized to complex real-time paradigms, limiting their applicability to general-purpose systems.In this paper, we present
Borrowed-Virtual-Time (BVT) Scheduling,
showing that it provides low-latency for real-time and interactive applications yet weighted sharing of the CPU across applications according to system policy, even with thread failure at the real-time level, all with a low-overhead implementation on multiprocessors as well as uniprocessors. It makes minimal demands on application developers, and can be used with a reservation or admission control module for hard real-time applications.
Performance measurement of parallel Ada
Authors: Goforth Andre , Collard Philippe , Marquardt Matthew
Published: October 2004

This paper reports on the development of benchmarks and performance measures for parallel Ada tasking. The focus is on the macroscopic behavior of the benchmarks across a set of load parameters because parallel processing of Ada tasks involves complex run-time behavior and side effects. An Ada program of an application with parallel processes was implemented and its tasks' execution on a multiprocessor system was studied.The chosen application was the NASREM model developed by National Bureau of Standards (NBS). The purpose of the model is to serve as a standard reference control architecture for intelligent, autonomous telerobotic systems. The control architectures of these systems have significant communication requirements as well as computational requirements. A preliminary load model of communication and computation characteristics has been made.Experiments were run on a Sequent Balance 8000 which has a tightly coupled, shared memory multiprocessor architecture and hosts a proprietary version of UNIX. The number of processors varied from 1 to 16. The software environment was a Verdix Ada compiler. A proprietary Ada run-time environment automatically scheduled Ada tasks for parallel execution on available processors.Most results show lowered communication response time as more processors were made available. However, in some cases communication response time increased as more processors were added. This appears because of system overhead.
Extending the scope of the program library
Authors: Narfelt Kjell-Hakan , Schefstrom Dick
Published: October 2004

The idea of a database as a central facility of a programming environment is explored, taking the Ada program Library as a starting point. The database used is based on a node model similar to the one proposed in the CAIS standard (KIT/KITIA 1984). The paper suggests an expansion of the scope of the program library into the area of configuration and version management in an environment with several ungoing projects sharing software objects. The authors furthermore present a technique for the manipulation of the relationships in a relational algebra inspired way - providing some of the powerful capabilities of the relational approach within the context of node models.
A tool kit for database programming in Ada
Authors: Fox Stephen , Nori Anil , Smith John M. , Chan Arvola , Danberg Sy
Published: October 2004

This paper describes an Ada-compatible database application development environment being designed and prototyped at Computer Corporation of America. This environment is intended to provide uniform access to centralized, homogeneously distributed, and heterogeneously distributed databases. There are two key interfaces: an interactive interface called Daplex which is based on a semantically rich data model and a powerful access language, and an application program interface called Adaplex which consists of an expression level integration of Daplex with Ada. The objective of this paper is to explain our rationale for designing Adaplex and to describe its support environment.
Saving traces for Ada debugging
Authors: LeDoux Carol H. , Parker D. Stott
Published: October 2004

A trace database model for debugging concurrent Ada programs is presented. In this approach, trace information is captured in an historical database and queried using Prolog. This model was used to build a prototype debugger, called Your Own Debugger for Ada (YODA). The design of YODA is described and a trace analysis of a sample program exhibiting misuse of shared data is presented. Because the trace database model is flexible and general, it can aid diagnosis of a variety of runtime errors.
Ada and the graphical kernel system
Authors: Leonard Thomas M.
Published: October 2004

The Graphical Kernel System (GKS) is a general purpose, Device-Independent, two-dimensional graphics system currently in the final stages of standardization by both the International Organization for Standerdization (ISO) [ISO 1982] and the American National Standards Institute (ANSI) [ANSI 1984c]. Associated with each GKS standardization effort are programming language bindings which standardize language-specific interfaces fro implementations of GKS. Currently in the draft proposed phase of standardization is the Ada language binding to ANSI GKS [ANSI 1985]. This paper describes the effort to produce the ada language binding to ANSI GKS and an implemention of GKS in Ada (GKS/Ade) which conforms to this draft proposed Ada language binding. This work will be the first standerdized Ade graphics capability.
Viewing Ada from a process model perspective
Authors: Strom Rob , Yemini Shaula , Wegner Peter
Published: October 2004

This paper compares two programming language paradigms for large software systems. The first is based upon nested block structure and static binding, augmented with abstract data types and concurrency, as exemplified by Ada. The second is based upon processes with disjoint data spaces which communicate by passing messages over dynamically bound ports as exemplified by the process model of NIL. We argue that the process model paradigm is simpler, has better support for modularity and programming-in-the-large, and results in more reliable and maintainable programs.We suggest usage restrictions and language extensions which allow Ada to support a process model with minimal change to the language. We show that our suggested modification of Ada yields a considerably simpler language.
The development of an Ada front end for small computers
Authors: Bundgaard J.
Published: October 2004

This paper concerns the design of an Ada front end that was required to be hosted on small computers. The paper discusses the special problems to be solved when implementing a compiler for a large language, like Ada, on machines with limited resources and capabilities, such as 16 bits for storage addressing. We also outline various possible solutions to these problems and describe in some detail the actual solutions applied in the Ada front end developed by Dansk Datamatik Center (DDC) as part of the Portable Ada Programming System.
A runtime supervisor to support Ada tasking
Authors: Riccardi G. A. , Baker T. P.
Published: October 2004

This paper describes a simple and efficient approach to implementing the Ada operations of entry calls, conditional and timed entry calls, accept statements, selective wait statements and delay statements. This is accomplished by describing the tasking supervisor -- a collection of programs which control the tasking operations. Ada definitions of the data structures and the supervisor procedures are given. The semantics of the Ada tasking operations are related to the supervisor by following the description of tasking in chapter 9 of the Reference Manual for the Ada Programming Language (1983). The structure of the object code for various Ada source language constructs is given. The interaction between the Ada object code and the run-time supervisor is described in detail. The remaining tasking opertions are described in Part 1 of this report (Riccardi and Baker 1984).
Computational geometry column 37
Authors: Demaine Erik D. , O'Rourke Joseph
Published: October 2004

Open problems from the 15th Annual ACM Symposium on Computational Geometry.
Who is interested in algorithms and why?
Authors: Skiena Steven S.
Published: October 2004

We present "market research" for the field of combinatorial algorithms and algorithm engineering, attempting to determine which algorithmic problems are most in demand in applications. We analyze 1,503,135 WWW hits recorded on the Stony Brook Algorithms Repository (http://www.cs.sunysb.edu/~algorith), to determine the relative level of interest among 75 algorithmic problems and the extent to which publicly available algorithm implementations satisfy this demand.