Existing architectures designed to host large-scale virtual environments (VEs) use a variety of approaches, but they often limit the interaction range with other users or with the VE. How densely users can populate a given region is also limited by the hosting machine's CPU or bandwidth resources. We are motivated to remove such restrictions and present SPEX, an infrastructure that supports scalable spatial publish/subscribe for VE applications. SPEX is scalable and fault-tolerant, with adaptive load balancing and low latency as its key features. It is designed for the state and overlay management in VEs with many concurrent users. We evaluate a practical SPEX implementation within Amazon's EC2 Cloud and present a feasible approach to supporting 750 users across a continent with low latency, opening the possibility for hosting fast-paced games (e.g., first-person shooters) or applications on a large-scale.

Key/value data storage systems serve as the fundamental component of scalable cloud-based services. However, the scalability of existing key/value data stores comes at the cost of a narrow data access API. We present Innesto, a distributed key/value data store that provides search as part of its API. Search allows data items to be retrieved based on constraints on multiple different attributes. Innesto's strong consistency data model and its transactional interface bring much of the power of traditional relational databases to cloud-scale performance. Our evaluation of Innesto shows it offers these extra features with competitive performance compared to an industrial key/value data store such as Cassandra which offers an inferior feature set.

Operating systems represent large pieces of complex software that are carefully tested and broadly deployed. Despite this, developers frequently have little more than their source code to understand how they behave. This static representation of a system results in limited insight into execution dynamics, such as what code is important, how data flows through a system, or how threads interact with one another. We describe Tralfamadore, a system that preserves complete traces of machine execution as an artifact that can be queried and analyzed with a library of simple, reusable operators, making it easy to develop and run new dynamic analyses. We demonstrate the benefits of this approach with several example applications, including a novel unified source and execution browser.

Browsers have become mature execution platforms enabling web applications to rival their desktop counterparts. An important class of such applications is interactive multimedia: games, animations, and interactive visualizations. Unlike many early web applications, these applications are latency sensitive and processing (CPU and graphics) intensive. When demands exceed available resources, application quality (e.g., frame rate) diminishes because it is hard to balance timeliness and utilization. The quality of ambitious web applications is also limited by single-threaded execution prevalent in the Web. Applications need to scale their quality, and thereby scale processing load, based on the resources that are available. We refer to this as scalable quality.

Program source is an intermediate representation of software; it lies between a developer's intention and the hardware's execution. Despite advances in languages and development tools, source itself and the applications we use to view it remain an essentially static representation of software, from which developers can spend considerable energy postulating actual behavior.

Parallax is a distributed storage system that uses virtualization to provide storage facilities specifically for virtual environments. The system employs a novel architecture in which storage features that have traditionally been implemented directly on high-end storage arrays and switches are relocated into a federation of storage VMs, sharing the same physical hosts as the VMs that they serve. This architecture retains the single administrative domain and OS agnosticism achieved by array- and switch-based approaches, while lowering the bar on hardware requirements and facilitating the development of new features. Parallax offers a comprehensive set of storage features including frequent, low-overhead snapshot of virtual disks, the 'gold-mastering' of template images, and the ability to use local disks as a persistent cache to dampen burst demand on networked storage.

As the disks typically found in personal computers grow larger, protecting data by replicating it on a collection of "peer" systems rather than on dedicated high performance storage systems can provide comparable reliability and availability guarantees but at reduced cost and complexity. In order to be adopted, peer-to-peer storage systems must be able to replicate data on hosts that are trusted, secure, and available. However, recent research has shown that the traditional model, where nodes are assumed to have identical levels of trust, to behave independently, and to have similar failure modes, is over simplified. Thus, there is a need for a mechanism that automatically and efficiently selects replica nodes from a large number of available hosts with varying capabilities and trust levels. In this paper we present an algorithm to handle replica node selection either for new replica groups or to replace failed replicas in a peer-to-peer storage system. We show through simulation that our algorithm maintains the node inter-connection topology minimizing the cost of recovery from a failed replica, measured by the number of nodes affected by the failure and the number of inter-node messages

Media server software is significantly complicated to develop and maintain, due to the nature of the many interface aspects which must be considered. This paper provides a case study of the design, implementation, and evolution of a continuous media file server. We place emphasis on the evolution of the software and our approach to maintainability. The user interface is a major consideration, even though the server software would appear isolated from that factor. Since continuous media servers must send the raw data to a client application over a network, the protocol considerations, hardware interface, and data storage/retrieval methods are of the paramount importance. In addition, the application programmer's interface to the server facilities has an impact on both the internal design and the performance of such a server. We discuss our experiences and insight into the development of such software products within a small research-based university environment. We experienced two main types of evolutionary change: requirements changes from the limited user community and performance enhancements/corrections. While the former were anticipated via a generic interface and modular design structure, the latter were surprising and substantially more difficult to solve. Copyright © 2005 John Wiley & Sons, Ltd.

Many routing protocols have been developed to establish and maintain routes in mobile ad-hoc networks (MANETs). They try to address the unique challenges that MANETs present over traditional wired networks. Some of these challenges are: use of unreliable wireless medium for communication; frequent change in topology; lack of a central authority to arbitrate communication in the network. These protocols find a route to a destination, if such a route exists. However in the wireless medium, links are susceptible to frequent failures which can cause partitions in the network. Current routing protocols use a passive delivery approach for packets destined to a host in another partition. Packets destined to a disconnected host are dropped after some route repair attempts. The paper presents a novel protocol, Voila/spl grave/, that delivers messages across disconnected hosts. Voila/spl grave/ uses nodes moving between the source and destination partitions to act as carriers of messages. It uses a novel carrier select algorithm to select carrier nodes in the source partition.

The emergence of wireless ad hoc networking has opened the way for a new style of distributed computing. Ad hoc networks operate without infrastructure such as routers or access points. Software designed for this environment faces new challenges. In traditional networks, partitioning is typically treated as an exceptional and transient condition. The situation in ad hoc wireless networks is completely reversed. Each ad hoc group is an isolated network, partitioned from all other ad hoc networks. As computers move from one ad hoc group to another, the set of partitions changes. This paper presents the design and implementation of a data synchronization service intended specifically for ad hoc wireless networks. It describes the underlying factors affecting the design, the protocol used to achieve synchronization, and some performance measurements from the actual implementation.

Abstract A file server for continuous media must provide resource guarantees and only admit requests that do not violate the resource availability. This paper addresses the admission performance of a server that explicitly considers the variable bit rate nature of the continuous media streams. A prototype version of the server has been implemented and evaluated in several heterogeneous environments. The two system resources for which admission control is evaluated are the disk bandwidth and the network bandwidth. Performance results from both measurement and simulation are shown with respect to different admission methods and varying scenarios of stream delivery patterns. We show that the vbrSim algorithm developed specifically for the server outperforms the other options for disk admission especially with request patterns that have staggered arrivals, while the network admission control algorithm is able to utilize a large percentage of the network bandwidth available. We also show the interactions between the limits of these two resources and how a system can be configured without wasted capacity on either one of the resources. Copyright © 2004 John Wiley & Sons, Ltd.

Recent work has demonstrated a peer-to-peer storage system that locates data objects using O(logN) messages by placing objects on nodes according to pseudo-randomly chosen IDs. While elegant, this approach constrains system functionality and flexibility: files are immutable, directories and symbolic names are not supported, data location is fixed, and access locality is not exploited. This paper presents Mammoth, a peer-to-peer hierarchical file system that, unlike alternative approaches, supports a traditional file-system API, allows files and directories to be stored on any node, and adapts storage location to exploit locality, balance load, and ensure availability. Our approach handles all coordination at the granularity of files instead of nodes. In effect, the nodes that store a particular file act as its server independently of other nodes in the system. The resulting system is highly available and robust to failure. Our experiments with our prototype have yielded good results, but an important question remains: how the system will perform on a massive scale. We discuss the key issues, some of which we have addressed and others that remain open.

Operating system structure is important; it leads to understandable, maintainable, 'pluggable' code. But despite our best efforts, some system elements have been difficult to structure. We propose a new analysis of this problem, and a new technology that can structure these elements. Aspect-oriented programming (AOP) (G. Kiczales et al., 1997) uses linguistic mechanisms to support the separation of crosscutting elements, or aspects of the system, from primary functionality. We have developed a proof-of-concept AOP implementation of prefetching in FreeBSD (www.cs.ubc.ca/labs/spl/aspects/aspectc.html). In our implementation, we have been able to modularize prefetching.

Summary form only given. Our work to date has been in the design and development of a stream-centric model for communications which we have called the flow. A flow is a uniquely named, message-based, multicast communications stream. Flows are named by FlowIDs which represent a collection of resources used to provide a communications stream in the same manner that process IDs represent resources associated with a computational task. By providing distinct names for these multicast streams, services become decoupled from network endpoints. This single property provides sweeping benefits for mobility, fault tolerance, and resource location. In addition to naming, we have implemented three properties of flows which we feel are beneficial to distributed applications. We have finished an initial implementation of flows as a network middleware and have become convinced that they are an interesting and useful communications abstraction.

We describe the design and implementation of a file server for variable bit rate continuous media. We address the problem of building a server where each stream may have a different bit rate and, more importantly, where the bit rate within a single stream may vary considerably. Such a server has been implemented within a high-speed network environment. The server is designed to be used in a heterogeneous environment and is linearly scalable. A significant aspect of the design of the system is the detailed consideration of the variable bit-rate profile of each data stream in performing admission control for the disk and for the network. This paper describes the system model, the user interface design, implementation details, and performance results based on initial experience with the server.

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.

Heterogeneous process migration is a technique whereby an active process is moved from one machine to another. It must then continue normal execution and communication. The source and destination processors can have a different architecture, that is, different instruction sets and data formats. Because of this heterogeneity, the entire process memory image must be translated during the migration. Tui is a migration system that is able to translate the memory image of a program (written in ANSI-C) between four common architectures (m68000, SPARC, i486 and PowerPC). This requires detailed knowledge of all data types and variables used with the program. This is not always possible in non-type-safe (but popular) languages such as ANSI-C, Pascal and Fortran. The important features of the Tui algorithm are discussed in great detail. This includes the method by which a program's entire set of data values can be located, and eventually reconstructed on the target processor. Performance figures demonstrating the viability of using Tui to migrate real applications are given. © 1998 John Wiley & Sons, Ltd.

In this paper, we address the problem of choosing a disk admission algorithm for continuous media streams where each stream may have a different bit rate, and more importantly, where the bit rate within a single stream may vary considerably.We evaluate several different Variable Bit Rate (VBR) disk admission control algorithms for continuous media.An algorithm which accepts too few streams under-utilizes the server resources, while an algorithm which accepts too many streams over-utilizes the resources resulting in inadequate service (i.e.missing or delayed data) to the clients.The evaluation process is based on a representative set of video streams encoded in MJPEG.We conclude that one particular algorithm, the VBR simulation algorithm, performs the best among realizable algorithms in terms of system utilization and delivery guarantees and performs close to an optimal algorithm, Keywords: multimedia, file servers, variable bit rate, admission control Pemhsion to mnke digitnhrd topics orall or part ofthis mnterinl for personal or clnssroom use is granted without Ike provided IIXII the copi& are not mnde or distribtltrd for prolit or coonuncrcinl advantage.11x copy-

An evolution is happening in the way that operating systems support the real-time requirements of their applications. The need to run real-time applications such as multimedia in the same environment as complex non-real-time servers and applications has motivated much interest in restructuring existing operating systems. Many issues related to thread scheduling and synchronization have been investigated. However, little consideration has been given to the flexibility and modularity required in the support of application-level scheduling needs, although it is well known that application requirements are diverse. In this paper, we describe a real-time scheduling abstraction which provides modularity and flexibility to the scheduling support of operating systems. Our design has been implemented using the Mach 3.0 kernel and a locally developed multiprocessor kernel (the r-kernel) as development platforms. © 1997 John Wiley & Sons, Ltd.

With the advent of high speed networks, the future communication environment is expected to comprise a variety of networks with widely varying characteristics. The next generation multimedia applications require transfer of a wide variety of data such as voice, video, graphics, and text which have widely varying access patterns such as interactive, bulk transfer, and real-time guarantees. Traditional protocol architectures have difficulty in supporting multimedia applications and high-speed networks because they are neither designed nor implemented for such a diverse communication environment. In this paper, we analyze the drawbacks of traditional protocol architectures and propose two alternative architectures for the next generation high-speed network environment: Direct Application Association and Integrated Layered Logical Multiplexing. We implement sample protocol stacks for each of the above models using the most widely used protocol stack (TCP/UDP-IP-Ethernet) in the context of the x-kernel. The performance of these protocol architectures is shown to be comparable to that of a traditional protocol architecture. They win by enabling the key requirements (Application specific Quality of Service) and optimizations (Integrated Layer Processing) necessary for future communication environments.

Raven is an object-oriented programming language and system that supports distributed and multiprocessor computing. This paper describes the motivation and design of Raven's object property scheme. Raven properties are used to provide system services on a per-object basis. Raven is distinguishable from similar systems in several fundamental ways: the behavioral semantics of each system supported property is truly orthogonal to those of the others, allowing properties to be combined without side effects; and all properties can be assigned dynamically, in any combination, even after object creation. Property support is provided automatically by the system. This scheme provides a simple yet powerful and flexible system where every object can have the properties it requires.>

A vital role of real-time kernels is to help applications meet real-time requirements. The common approach in existing kernel design methodology has been to replace the scheduler in the kernel according to the needs of the application. As new real-time applications with unconventional scheduling requirements continue to emerge, constantly changing the kernel results in it becoming less stable and less maintainable. We discuss the modularity problems associated with this adhoc approach. We propose a kernel design which solves many of the problems by providing a common real-time task model for all real-time applications. This model allows for much more flexibility in the implementation of application-level schedulers and at the same time encourages modularity in kernel and application design. The model has been implemented using the Mach 3.0 kernel as a development platform. The flexibility of our solution is illustrated by considering the demands placed on the kernel by a modern multimedia application.>

It is argued that a modular operating system architecture should provide support for modularity independent of protection domains. Given such support, modules and interfaces can be designed according to sound software engineering principles, without concern for cross-domain invocation costs. The partitioning of modules into domains and across machines becomes a matter of configuration, rather than design. Current micro-kernel-based architectures do not sufficiently address this issue since their communication mechanisms are designed for the nonlocal, i.e., cross-domain, case. An architecture that provides location-transparent binding and access of modules optimized for the local case, thereby decoupling the orthogonal concepts of modularity and protection, is proposed.>

Abstract Emerald is a general‐purpose language with aspects of traditional object‐oriented languages, such as Smalltalk, and abstract data type languages, such as Modula‐2 and Ada. It is strongly typed with a non‐traditional object model and type system that emphasize abstract types, allow separation of typing and implementation, and provide the flexibility of polymorphism and subtyping with compile‐time checking. This paper describes the Emerald language and its programming methodology. We give examples that demonstrate Emerald's features, and compare and contrast the Emerald approach to programming with the approaches used in other similar languages.

A description is given of an operating system kernel, called the x-Kernel, that provides an explicit architecture for constructing and composing network protocols. The authors' experience implementing and evaluation several protocols in the x-Kernel shows that this architecture is general enough to accommodate a wide range of protocols, yet efficient enough to perform competitively with less-structured operating systems. Experimental results demonstrating the architecture's generality and efficiency are provided. The explicit structure provided by the x-Kernel has the following advantages. First, the architecture simplifies the process of implementing protocols in the kernel, making it easier to build and test novel protocols. Second, the uniformity of the interface between protocols avoids the significant cost of changing abstractions and makes protocol performance predictable. Third, it is possible to write efficient protocols by tuning the underlying architecture rather than heavily optimizing protocols themselves.>

This paper reports our experiences implementing remote procedure call (RPC) protocols in the x-kernel. This exercise is interesting because the RPC protocols exploit two novel design techniques: virtual protocols and layered protocols. These techniques are made possible because the x-kernel provides an object-oriented infrastructure that supports three significant features: a uniform interface to all protocols, a late binding between protocol layers, and a small overhead for invoking any given protocol layer. For each design technique, the paper motivates the technique with a concrete example, describes how it is applied to the implementation of RPC protocols, and presents the results of experiments designed to evaluate the technique.

The x-kernel is a configurable operating system kernel designed to support experimentation in interprocess communication and distributed programming. The x-kernel's underlying architecture provides a rich set of abstractions that are used to construct and compose communication protocols. The architecture is interesting because the abstractions are both general enough to accommodate a wide range of protocols and efficient enough to provide a useful testbed in which protocol performance can be accurately measured.

Emerald is an object-based language and system designed for the construction of distributed programs. An explicit goal of Emerald is support for object mobility; objects in Emerald can freely move within the system to take advantage of distribution and dynamically changing environments. We say that Emerald has fine-grained mobility because Emerald objects can be small data objects as well as process objects. Fine-grained mobility allows us to apply mobility in new ways but presents implementation problems as well. This paper discusses the benefits of tine-grained mobility, the Emerald language and run-time mechanisms that support mobility, and techniques for implementing mobility that do not degrade the performance of local operations. Performance measurements of the current implementation are included.

The Emerald compiler analyzes object definitions and attempts to produce efficient implementations commensurate with the way in which objects are used. For example, an object that moves around the network will require a very general remote procedure call implementation; however, an object that is completely internal to that mobile object can be implemented using direct memory addressing and inline code or procedure calls.We wanted to achieve performance competitive with standard procedural languages in the local case and standard remote procedure call systems in the remote case. These goals are not trivial in a location-independent object-based environment. To meet them, we relied heavily on an appropriate choice of language semantics, a tight coupling between the compiler and run-time kernel, and careful attention to implementation.As an example of Emerald's local performance, Table 1 shows execution times for several local Emerald operations executed on a Micro VAX II1. The “resident global invocation” time is for a global object (i.e., one that can move around the network) when invoked by another object resident on the same node. By comparison, other object-based distributed systems are typically over 100 times slower for local invocations of their most general objects [6, 1].The Emerald language uses call-by-object-reference parameter passing semantics for all invocations, local or remote. While call-by-object-reference is the natural semantics for object-based systems, it presents a potential performance problem in a distributed environment. When a remotely invoked object attempts to access its arguments, those accesses will typically require remote invocations. Because Emerald objects are mobile, it may be possible to avoid some of these remote references by moving argument objects to the site of a remote invocation.From this table we can compute the benefit of call-by-move for a simple argument object. For this simple argument object, the additional cost of call-by-move was 2 milliseconds while call-by-visit cost 6.4 milliseconds. These are computed by subtracting the time for a remote invocation with an argument reference that is local to the destination. The call-by-visit time includes sending the invocation message and the argument object, performing the remote invocation (which then invokes its argument), and returning the argument object with the reply. Had the argument been a reference to a remote object (i.e., had the object not been moved), the incremental cost would have been 30.8 milliseconds. These measurements are somewhat of a lower bound because the cost of moving an object depends on the complexity of the object and the types of objects it names.Emerald currently executes on a small network of MicroVAX IIs and has recently been ported to the SUN 32. We have concentrated on implementing fine-grained mobility in Emerald while minimizing its impact on local performance. This has presented significant problems; however, through the use of language support and a tightly-coupled compiler and kernel, we believe that our design has been successful in meeting both its conceptual and performance goals.

Emerald is an object-based language for programming distributed subsystems and applications. Its novel features include 1) a single object model that is used both for programming in the small and in the large, 2) support for abstract types, and 3) an explicit notion of object location and mobility. This paper outlines the goals of Em-erald, relates Emerald to previous work, and describes its type system and distribution support. We are currently constructing a prototype implementation of Emerald.

Emerald is an object-based language for the construction of distributed applications. The principal features of Emerald include a uniform object model appropriate for programming both private local objects and shared remote objects, and a type system that permits multiple user-defined and compiler-defined implementations. Emerald objects are fully mobile and can move from node to node within the network, even during an invocation. This paper discusses the structure, programming, and implementation of Emerald objects, and Emerald's use of abstract types.