bluuebunny/crossref_metadata_2025 huggingface dataset:
A designer's perspective of the Hawk multiprocessor operating system kernel
Authors: Holmes V. P. , Harris D. L.
Published: October 2004

The Hawk operating system kernel was specifically designed and implemented to support real-time applications on the SANDAC V embedded multiprocessor. The kernel provides a tasking model for program decomposition and supports message passing, synchronization, as well as other ancillary services. The kernel primitives have a Unix™-like system call interface to the C language and were designed to provide users a choice of level of abstraction, yet perform efficiently and behave predictably. Many design choices were limited by the type of environment the system was intended to support, namely, hard-real-time for missions of short duration. The system has been implemented and has supported applications for nearly two years. Measurements of kernel performance are herein reported. This paper is an overview of the Hawk kernel and a look backward at the decisions that were made in its design.
An expert system for Cobol program debugging
Authors: Litecky Chuck
Published: October 2004

The purpose of this research is to assess the feasibility of applying expert systems techniques for improved error control and productivity of commercial programming. Error control in programming: error detection, error removal and error prevention is a major problem for productivity (Jones,1986). Improved error control appears to offer substantial potential for improving programmer productivity. The purpose of this paper is to analyze and describe the structure of an expert systems model for COBOL debugging. COBOL was selected as part of this research due to its importance in commercial programming. The Data Processing Management Association's Educational Foundation has sponsored the development of a pilot model suitable for testing the feasibility of this research. This is a preliminary paper which is limited to the development of the expert systems model and it's rationale. As this is an early paper, feedback and suggestions are solicited.This paper is organized into two major sections. The first part reports on utilizing previous empirical research on COBOL error frequency to build a knowledge base of errors in programming. The second part of the paper is an analysis of an expert systems model in which the COBOL error frequency and debugging strategies are implemented on an experimental basis.
Computer-aided software engineering: present status and future directions
Authors: Chen M. , Nunamaker J. F. , Weber E. S.
Published: October 2004

The authors examine the current status of Computer-Aided Software Engineering (CASE) and discuss the benefits it promises to deliver in the future. First, an extended life-cycle model is presented. Next, basic functions of a CASE environment and the authors' classification scheme for analyzing CASE products are discussed. Following this, the authors draw implications from the results of empirical CASE studies and propose strategies for adapting CASE technologies. The paper concludes with a discussion of future research and development directions. These include the use of CASE in integrating organization and information systems modeling, in adding value to Executive Information Systems (EIS), and in fostering user-developer collaboration.
Programming atomic actions in Ada
Authors: Burns A. , Wellings A. J.
Published: October 2004

Atomic actions are often seen as an important structuring aid in the design and construction of fault tolerant programs. In this paper we consider whether recoverable atomic action can be implemented in Ada using the language's communication and synchronisation mechanisms. Whilst simple atomic actions can be programmed in Ada, recoverable actions cannot because the language does not have an asynchronous exception facility.
Ada: adding reliability and efficiency to task communication in programming distributed control systems
Authors: Sacha K. M.
Published: October 2004

One of the main application areas of the Ada language is programming of embedded systems. The most important issues in such applications are reliability and efficiency. On the hardware level these issues are addressed by distribute d architectures. On the software level appropriate language constructs are needed to benefit the reliability of the distributed hardware. Two extensions to the Ada language are suggested: one to improve the reliability of the remote procedure call and the other to improve the efficiency of the message broadcasting facility.
A simplified graphic notation for Ada programs
Authors: Sterne D. , Glendening A. , Jachowski A. , Pretti G.
Published: October 2004

A number of graphic notations for describing Ada programs have been proposed. In general, these are not supported by off-the-shelf tools; they are perceived by nonexperts as incomprehensible; they obscure simple design deficiencies; and they cannot adequately represent design overviews. To address these problems, a simplified graphic notation has been developed and used in a large Ada application at GTE Government Systems Corporation, in Rockville, Maryland. The notation consists of three interrelated diagrams based on extensions of structure chart concepts.
An overview of DARK
Authors: van Scoy R. , Bamberger J. , Firth R.
Published: October 2004

Ada is now being mandated for a large number of DoD development projects as the sole programming language to be used for developing software. Many of these projects are trying to build distributed real-time systems. Many project managers and contractors are anxious to support this effort, to reap the advantages of Ada, and to use the newer techniques of software engineering that Ada can support. This transition, however, has not always been smooth; some serious problems have been encountered. This paper discusses several of thes e problems and describes a prototype software artifact, called the Distributed Ada Real-Time Kernel (DARK), built to address these concerns and to support execution of real-time Ada applications in a distributed, embedded environment. This prototype is not intended to solve all the problems of real-time, embedded systems, but it does provide one viable, near-term option demonstrating that Ada can be used in real-time systems today.
Reducing risks from poorly chosen keys
Authors: Lomas T. , Gong L. , Saltzer J. , Needhamn R.
Published: October 2004

It is well-known that, left to themselves, people will choose passwords that can be rather readily guessed. If this is done, they are usually vulnerable to an attack based on copying the content of messages forming part of an authentication protocol and experimenting, e.g. with a dictionary, offline. The most usual counter to this threat is to require people to use passwords which are obscure, or even to insist on the system choosing their passwords for them. In this paper we show alternatively how to construct an authentication protocol in which offline experimentation is impracticable; any attack based on experiment must involve the real authentication server and is thus open to detection by the server noticing multiple attempts.
A lazy buddy system bounded by two coalescing delays
Authors: Barkley R. , Lee T.
Published: October 2004

The watermark-based lazy buddy system for dynamic memory management uses lazy coalescing rules controlled by watermark parameters to achieve low operational costs. The correctness of the watermark-based lazy buddy system is shown by defining a space of legal states called the lazy space and proving that the watermark-based lazy coalescing rules always keep the memory state within that space. In this paper we describe a different lazy coalescing policy, called the DELAY-2 algorithm, that focuses directly on keeping the memory state within the lazy space. The resulting implementation is simpler, and experimental data shows it to be up to 12% faster than the watermark-based buddy system and about 33% faster than the standard buddy system. Inexpensive operations make the DELAY-2 algorithm attractive as a memory manager for an operating system.

The watermark-based lazy buddy policy offers fine control over the coalescing policy of the buddy system. However, applications such as the UNIX System kernel memory manager do not need such fine control. For these applications, the DELAY-2 buddy system provides an efficient memory manager with low operational costs and low request blocking probability. In the DELAY-2 buddy system, the worst-case time for a free operation is bounded by two coalescing delays per class, and when all blocks are returned to the system, the system memory is coalesced back to its original state. This ensures that the memory space can be completely shared.
Analysis of transaction management performance
Authors: Duchamp D.
Published: October 2004

There is currently much interest in incorporating transactions into both operating systems and general-purpose programming languages. This paper provides a detailed examination of the design and performance of the transaction manager of the Camelot system. Camelot is a transaction facility that provides a rich model of transactions intended to support a wide variety of general-purpose applications. The transaction manager's principal function is to execute the protocols that ensure atomicity.

The conclusions of this study are: a simple optimization to two-phase commit reduces logging activity of distributed transactions; non-blocking commit is practical for some applications; multithreaded design improves throughput provided that log batching is used; multi-casting reduces the variance of distributed commit protocols in a LAN environment; and the performance of transaction mechanisms such as Camelot depend heavily upon kernel performance.
Threads and input/output in the synthesis kernal
Authors: Massalin H. , Pu C.
Published: October 2004

The Synthesis operating system kernel combines several techniques to provide high performance, including kernel code synthesis, fine-grain scheduling, and optimistic synchronization. Kernel code synthesis reduces the execution path for frequently used kernel calls. Optimistic synchronization increases concurrency within the kernel. Their combination results in significant performance improvement over traditional operating system implementations. Using hardware and software emulating a SUN 3/160 running SUNOS, Synthesis achieves several times to several dozen times speedup for UNIX kernel calls and context switch times of 21 microseconds or faster.
Mirage: a coherent distributed shared memory design
Authors: Fleisch B. , Popek G.
Published: October 2004

Shared memory is an effective and efficient paradigm for interprocess communication. We are concerned with software that makes use of shared memory in a single site system and its extension to a multimachine environment. Here we describe the design of a
distributed shared memory
(DSM) system called Mirage developed at UCLA. Mirage provides a form of network transparency to make network boundaries invisible for shared memory and is upward compatible with an existing interface to shared memory. We present the rationale behind our design decisions and important details of the implementation. Mirage's basic performance is examined by component timings, a worst case application, and a “representative” application. In some instances of page contention, the tuning parameter in our design improves application throughput. In other cases, thrashing is reduced and overall system performance improved using our tuning parameter.
Analysis and simulation of a fair queueing algorithm
Authors: Demers A. , Keshav S. , Shenker S.
Published: October 2004

We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. A fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources.
A hierarchical solution for application level store-and-forward deadlock prevention
Authors: Brachman B. J. , Chanson S. T.
Published: October 2004

Application level message transfer systems, primarily used to transport electronic mail, have several unique characteristics that make using existing methods of dealing with deadlock impractical. The special requirements for the efficient transport of application level messages are discussed and a description of a hierarchical scheme that meets these requirements is given. For networks consisting of interconnected clusters of computers, the structured buffer pool technique can be combined with other deadlock-free message transport schemes to form a network-wide, deadlock-free message transport facility. A properly chosen hierarchical system has the advantages of the individual schemes while lessening the impact of their disadvantages. The hierarchical scheme is also applicable to packet-switched and datagram-based networks.
Specification and verification of network managers for large internets
Authors: Cohrs D. L. , Miller B. P.
Published: October 2004

Large internet environments are increasing the difficulty of network management. Integrating increasing numbers of autonomous subnetworks (each with an increasing number of hosts) makes it more difficult to determine if the network managers of the subnetworks will interoperate correctly. We propose a high level, formal specification language, NMSL, as an aid in solving this problem. NMSL has two aspects of operation, a descriptive aspect and a prescriptive aspect. In its descriptive aspect, NMSL specifies abstractions of the network components and their instantiations, and verifies the consistency of such a specification. The abstractions include the data objects and processes in a network management system. These abstractions are instantiated on network elements. Network elements are grouped together in the specification of domains of administration. An extension mechanism is provided to allow for the specification of new management characteristics that the basic language cannot express. In its prescriptive aspect, NMSL generates configuration information directly from a consistent specification. This information is used to configure network management processes to make their operation consistent with their specifications. Standard management protocols (such as the emerging ISO or IETF standards) can be used to incorporate the configuration information into running management processes.
A routing architecture for very large networks undergoing rapid reconfiguration
Authors: Snyder J. M.
Published: October 2004

A routing architecture is described for very large communications networks with greater than 10,000 routing nodes and 100,000 end nodes. This architecture, called the Traveler Architecture, is designed to be independent of network configuration and to be robust even under conditions of rapid reconfiguration. Traveler is an extension of the ISO routing protocols. The Traveler architecture is designed to work with traffic characteristic of existing large networks, such as the Internet. While Traveler does not require a particular routing algorithm, it is designed to work in conjunction with families of distributed routing algorithms. Because Traveler is based on the paradigm of a human traveler, it attempts to use non-deterministic and heuristic methods rather than purely algorithmic methods to determine high quality routes between two points. Traveler builds on the Landmark and Area routing architectures.
X-NET: a dual bus fiber-optic LAN using active switches
Authors: Kamal A. E. , Abeysundara B. W.
Published: October 2004

X-Net is a new local area network based on the dual, unidirectional bus topology. Stations are connected to two fiber-optic busses using active switches. At light load, X-Net behaves as a random access scheme. With increasing load, transmissions are done in an orderly manner, arranged into cycles.

The main advantage of X-Net is its superior channel utilization and delay performance, compared to other bus schemes. The packet delay is bounded at all loads. Performance is shown to be satisfactory over a wide range of a values, where a is the ratio of end-to-end medium propagation delay to the packet transmission time. Therefore, X-Net is a suitable candidate for operation at high speeds.
AMp: a highly parallel atomic multicast protocol
Authors: Veríssimo P. , Rodrigues L. , Baptista M.
Published: October 2004

This paper deals with the problem of reliable group communication for distributed applications, in the context of the Reliable Broadcast class of protocols. An atomic multicast protocol for token passing Lans is presented. The actual implementation is on an 8802/4 Token-bus, although it is applicable to 8802/5 Token-rings and the FDDI Fibre-Optic network.

The simplicity and efficiency of reliable broadcast protocols may be considerably improved, if the system fault model is restricted or convenient architectures are used. Fail-controlled communication components are used here to build an efficient reliable multicast protocol on top of the exposed MAC interface of a VLSI Lan controller. The architecture is built on standard Lans, in view of taking advantage of the availability of communications hardware and the possibility of coexistence with standard stations, in the same network.

The service offered allows transparent multicasting inside logical groups, which are dynamically created and updated. The primitive is highly parallel and provides atomic agreement and consistent delivery order, respecting logical precedence. These features are an important contribution for the implementation of high performance distributed computing systems.
Traffic placement policies for multi-band network
Authors: Maly K. J. , Foudriat E. C. , Game D. , Mukkamala R. , Overstreet C. M.
Published: October 2004

Recently protocols have been introduced that enable the integration of synchronous traffic (voice or video) and asynchronous traffic (data) and extend the size of local area networks without loss in speed or capacity. One of these is DRAMA, a multiband protocol based on broadband technology. It provides dynamic allocation of bandwidth among clusters of nodes in the total network. In this paper, we propose and evaluate a number of traffic placement policies for such networks. Metrics used for performance evaluation include average network access delay, degree of fairness of access among the nodes, and network throughput. The feasibility of the DRAMA protocol is established through simulation studies. DRAMA provides effective integration of synchronous and asynchronous traffic due to its ability to separate traffic types. Under the suggested traffic placement policies, the DRAMA protocol is shown to handle diverse loads, mixes of traffic types, and numbers of nodes, as well as modifications to the network structure and momentary traffic overloads.
Block acknowledgement: redesigning the window protocol
Authors: Brown G. M. , Gouda M. G. , Miller R. E.
Published: October 2004

We describe a new version of the window protocol where message sequence numbers are taken from a finite domain and where both message disorder and loss can be tolerated. Most existing window protocols achieve only one of these two goals. Our protocol is based on a new method of acknowledgement, called
block acknowledgement
, where each acknowledgement message has two numbers
m
and
n
to acknowledge the reception of all data messages with sequence numbers ranging from
m
to
n
. Using this method of acknowledgement, the proposed protocol achieves the two goals while maintaining the same data transmission capability of the traditional window protocol.
A high speed transport protocol for datagram/virtual circuit networks
Authors: Sabnani K. K. , Netravali A. N.
Published: October 2004

We present a design and preliminary analysis of an end-to-end transport protocol that is capable of high throughput consistent with the evolving wideband physical networks based on fiber optic transmission lines and high capacity switches. Unlike the current transport protocols in which changes in control state information are exchanged between the two communicating entities only when some significant event occurs, our protocol exchanges relevant and full state information periodically, routinely and frequently. We show that this results in reducing the complexity of protocol processing by removing many of the procedures required to recover from the inadequacies of the network such as bit-errors, packet loss, out of sequence packets and makes it more amenable to parallel processing. Also, to increase channel utilization in the presence of high speed, long latency networks, and to support datagrams, we propose an efficient implementation of selective repeat method of error control used in our protocol. Thus, we utilize small extra bandwidth to simplify protocol processing; a trade-off that appears proper since electronic speeds for protocol processing are far slower than fiber transmission rates. Our preliminary estimates indicate that 20,000 packets/second can be handled in a completely software implementation on a 10 MIP microprocessor using 8% of its cycles.
A unified approach to loop-free routing using distance vectors or link states
Authors: Garcia-Luna-Aceves J. J.
Published: October 2004

We present a unified approach for the dynamic computation of shortest paths in a computer network using either distance vectors or link states. We describe a distributed algorithm that provides loop-free paths at every instant and extends or improves algorithms introduced previously by Chandy and Misra, Jaffe and Moss, Merlin and Segall, and the author. Our approach treats the problem of distributed shortest-path routing as one of diffusing computations, which was first proposed by Dijkstra and Scholten. We verify the loop-freedom of the new algorithm, and also demonstrate that it converges to the correct routing entries a finite time after an arbitrary sequence of topological changes. We analyze the complexity of the new algorithm when distance vectors and link states are used, and show that using distance vectors is better insofar as routing overhead is concerned.
A new responsive distributed shortest-path rounting algorithm
Authors: Rajagopalan B. , Fairman M.
Published: October 2004

Distributed shortest-path routing algorithms based on the Ford-Fulkerson method are simple to implement but they suffer from the
cost-dependent looping
problem: when link costs increase, routing table loops may form and convergence to correct paths may be too slow, depending on link costs. This problem can be eliminated if constraints are imposed on the order in which routing tables are updated at different nodes but the resulting internode protocols tend to be relatively complex. Furthermore, update constraints may restrict a node's ability to obtain alternate paths quickly in an environment where topology changes are frequent. In this paper, a new distributed shortest-path routing scheme based on the Ford-Fulkerson method is presented. Under the new scheme, each node uses partial topology information to eliminate the cost-dependent looping problem. No update constraints are imposed and no assumptions are made regarding link costs. In the worst case, the new scheme responds to link cost changes in
O(D)
update steps, where
D
is the diameter of the network after the occurrence of the changes.
Deriving a protocol converter: a top-down method
Authors: Calvert K. L. , Lam S. S.
Published: October 2004

A
protocol converter
mediates the communication between implementations of different protocols, enabling them to achieve some form of useful interaction. The problem of deriving a protocol converter from specifications of the protocols and a desired service can be viewed as the problem of finding the “quotient” of two specifications. We define a class of finite-state specifications and present an algorithm for solving “quotient” problems for the class. The algorithm is applied to an example conversion problem. We also discuss its application in the context of layered network architectures.
A protocol conversion software toolkit
Authors: Auerbach J.
Published: October 2004

This paper describes a “toolkit” (a software function library) for synthesizing conversions between different transport interfaces. The method employed involves classifying these interfaces according to their “transport abstraction type.” Each actual interface is converted to or from a canonical form depending on its type, and the library also contains sufficient “abstraction converters” to convert between all of the canonical forms. The overall conversion is accomplished by combining some number of elementary conversions which execute in series. The paper describes the toolkit, contrasts it with other approaches, and shows how it can be used to solve various problems in protocol conversion and the “migration” of distributed services to new network contexts.
Protocol validation in complex systems
Authors: West C. H.
Published: October 2004

Protocol validation and verification techniques have been applied successfully for a number of years to a wide range of protocols. The increasing complexity of our communications systems requires us to examine existing techniques and make a realistic assessment of which techniques will be applicable to the complex systems of the future. We believe that validation techniques based on an exhaustive reachability analysis will not be effective. Sampling techniques, such as executing a random walk through the reachable state space, are effective in complex systems, since most protocol errors occur in many different states of the system.

More than 10 years have elapsed since the first automated validation techniques were first applied to communications protocols [1,2]. In the meantime, considerable advances have been made in validation technology, but more significantly, the scale and nature of the validation problem have changed. The communications systems that we need to validate today are significantly more complex than those of ten years ago. Our methods must evolve in order to address the current challenge.

This paper is concerned primarily with the nature of the validation process, and the results that we might reasonably expect to achieve when validating protocols in complex communications systems.
JVM
Authors: Pinilla Ruben , Gil Marisa
Published: October 2004

Nowadays Java technology has become an important reference to application developers. The great acceptance from software developer's community is mainly based on its platform independence execution environment. In this paper, we analyze the degree of dependence between the Java Virtual Machine (JVM) and the underlying platform. We have observed that the Sun JVM (Java 2 SDK 1.2.2-006) API is independent from programmer's point of view, but offers different behaviour depending on the target HPI (Host Porting Interface) implementation, being a possible cause of incorrect program execution. This fact can be solved implementing a HPI that could manage scheduling entities provided by an operating system (or a threads library) performing a uniform behaviour independently of the target operating system.
Implementing Remote procedure calls
Authors: Birrell Andrew D. , Nelson Bruce Jay
Published: October 2004

Remote procedure calls (
RPC
) are a useful paradigm for providing communication across a network between programs written in a high level language. This paper describes a package, written as part of the
Cedar
project, providing a remote procedure call facility. The paper describes the options that face a designer of such a package, and the decisions we made. We describe the overall structure of our RPC mechanism, our facilities for binding RPC clients, the transport level communication protocol, and some performance measurements. We include descriptions of some optimisations we used to achieve high performance and to minimize the load on server machines that have many clients.

Our primary aim in building an RPC package was to make the building of distributed systems easier. Previous protocols were sufficiently hard to use that only members of a select group of communication experts were willing to undertake the construction of distributed systems. We hoped to overcome this by providing a communication paradigm as close as possible to the familiar facilities of our high level languages. To achieve this aim, we concentrated on making remote calls efficient, and on making the semantics of remote calls as close as possible to those of local calls.
A file system supporting cooperation between programs
Authors: Reid Loretta Guarino , Karlton Philip L.
Published: October 2004

File systems coordinate simultaneous access of files by concurrent client processes. Although several processes may read a file simultaneously, the file system must grant exclusive access to one process wanting to write the file. Most file systems consider processes to be antagonistic: they prevent one process from taking actions on a file that have any chance to harm to another process already using the file. If several processes need to cooperate in a more sophisticated manner in their use of a file, they must communicate explicitly among themselves.

The next three sections describe the file system procedures used by clients for using and sharing files. Section Two discusses how a client gains access to a file and how a client can respond if the file system asks it to give up a file it is using. Section Three discusses the mechanism by which a client might ask to be notified that a file is available for some access. Section Four discusses a controlled type of file access that lets clients read and write the same file at the same time.

Section Five comprises three examples of the cooperative features of the file system taken from the Xerox Development Environment. Section Six discusses the subtleties of writing the call-back procedures that clients provide to the file system to implement interprocess cooperation. Section Seven discusses the implementation of this file system.
New methods for dynamic storage allocation (Fast Fits)
Authors: Stephenson C. J.
Published: October 2004

The classical methods for implementing dynamic storage allocation can be summarized thus

First Fit and Best Fit

The available blocks of storage are linked together in address order. Storage is allocated from the first available block of sufficient length, or from a block with the minimum excess length. Storage can be allocated or released in multiples of two words. In the long run, if numerous pieces of storage of more-or-less random lengths are allocated and released at more-or-less random intervals, the storage becomes fragmented, and a number of uselessly small blocks develop, particularly near the beginning of the list. Although these fragments usually comprise a small proportion of the storage (typically around 10 per cent), a lot of time can be wasted chaining through them.

Buddy Methods

Here the task of managing the storage is reduced in size by constraining the way in which the storage can be divided up, e.g. into blocks with lengths which are powers of 2. This eliminates chaining through long lists of uselessly small blocks; on the other hand, space is wasted in rounding up the length requested to an allowable size, and typically about 40 per cent more storage is required to satisfy the same allocations than when using First Fit or Best Fit.

The methods presented in this paper are externally compatible with First Fit and Best Fit, and require roughly the same amount of storage for a given sequence of allocations. They use, however, a completely different internal data structure, one effect of which is to reduce the number of blocks that have to be visited to perform a typical allocation or release operation. These new methods exhibit roughly the same
space performance
as First Fit, and a
time performance
which falls between those of First Fit and Buddy.
A nested transaction mechanism for LOCUS
Authors: Mueller Erik T. , Moore Johanna D. , Popek Gerald J.
Published: October 2004

Atomic transactions are useful in distributed systems as a means of providing reliable operation in the face of hardware failures. Nested transactions are a generalization of traditional transactions in which transactions may be composed of other transactions. The programmer may initiate several transactions from within a transaction, and serializability of the transactions is guaranteed even if they are executed concurrently. In addition, transactions invoked from within a given transaction fail independently of their invoking transaction and of one another, allowing use of alternate transactions to accomplish the desired task in the event that the original should fail. Thus nested transactions are the basis for a general-purpose reliable programming environment in which transactions are modules which may be composed freely.

A working implementation of nested transactions has been produced for LOCUS, an integrated distributed operating system which provides a high degree of network transparency. Several aspects of our mechanism are novel. First, the mechanism allows a transaction to access objects directly without regard to the location of the object. Second, processes running on behalf of a single transaction may be located at many sites. Thus there is no need to invoke a new transaction to perform processing or access objects at a remote site. Third, unlike other environments, LOCUS allows replication of data objects at more than one site in the network, and this capability is incorporated into the transaction mechanism. If the copy of an object that is currently being accessed becomes unavailable, it is possible to continue work by using another one of the replicated copies. Finally, an efficient orphan removal algorithm is presented, and the problem of providing continued operation during network partitions is addressed in detail.
Publishing
Authors: Powell Michael L. , Presotto David L.
Published: October 2004

Publishingis a model and mechanism for crash recovery in a distributed computing environment. Published communication works for systems connected via a broadcast medium by recording messages transmitted over the network. The recovery mechanism can be completely transparent to the failed process and all processes interacting with it. Although published communication is intended for a broadcast network such as a bus, a ring, or an Ethernet, it can be used in other environments.

Arecorderreliably stores all messages that are transmitted, as well as checkpoint and recovery information. When it detects a failure, the recorder may restart affected processes from checkpoints. The recorder subsequently resends to each process all messages which were sent to it since the time its checkpoint was taken, while ignoring duplicate messages sent by it.

Message-based systems without shared memory can use published communications to recover groups of processes. Simulations show that at least 5 multi-user minicomputers can be supported on a standard Ethernet using a single recorder. The prototype version implemented in DEMOS/MP demonstrates that an error recovery can be transparent to user processes and can be centralized in the network.
Process migration in DEMOS/MP
Authors: Powell Michael L. , Miller Barton P.
Published: October 2004

Process migration has been added to the DEMOS/MP operating system. A process can be moved during its execution, and continue on another processor, with continuous access to all its resources. Messages are correctly delivered to the process's new location, and message paths are quickly updated to take advantage of the process's new location. No centralized algorithms are necessary to move a process.

A number of characteristics of DEMOS/MP allowed process migration to be implemented efficiently and with no changes to system services. Among these characteristics are the uniform and location independent communication interface, and the fact that the kernel can participate in message send and receive operations in the same manner as a normal process.
The TRIPOS filing machine, a front end to a file server
Authors: Richardson M. F. , Needham R. M.
Published: October 2004

This paper discusses an experiment which sets out to improve the performance of a number of single user computers which rely on a general purpose file server for their filing systems. The background is described in detail in reference [1], but for completeness it is necessary to say something about it here.

The Cambridge Distributed Computing System consists, at the time of writing, of between 50 and 60 machines of various types, connected by a digital communications ring. On the ring, there are two file servers [2], [3], which are general purpose (or "universal" [4]) in the sense that they have no commitment to a particular directory or access control structure. This is done in order that they may support several client systems, and so that new systems may be added without difficulty. We speak of a particular directory and access control structure implemented over the file server as "a filing system".
The distributed V kernel and its performance for diskless workstations
Authors: Cheriton David R. , Zwaenepoel Willy
Published: October 2004

The distributed V kernel is a message-oriented kernel that provides uniform local and network interprocess communication. It is primarily being used in an environment of diskless workstations connected by a high-speed local network to a set of file servers. We describe a performance evaluation of the kernel, with particular emphasis on the cost of network file access. Our results show that over a local network:

1. Diskless workstations can access remote files with minimal performance penalty.

2. The V message facility can be used to access remote files at comparable cost to any well-tuned specialized file access protocol.

We conclude that it is feasible to build a distributed system with all network communication using the V message facility even when most of the network nodes have no secondary storage.
Reflections on the verification of the security of an operating system kernel
Authors: Silverman Jonathan M.
Published: October 2004

This paper discusses the formal verification of the design of an operating system kernel's conformance to the multilevel security property. The kernel implements multiple protection structures to support both discretionary and nondiscretionary security policies. The design of the kernel was formally specified. Mechanical techniques were used to check that the design conformed to the multilevel security property. All discovered security flaws were then either closed or minimized. This paper considers the multilevel security model, the verification methodology, and the verification tools used. This work is significant for two reasons. First, it is for a complete implementation of a commercially available secure computer system. Second, the verification used off-the-shelf tools and was not done by the verification environment researchers.
A retrospective view of ATM
Authors: Kalmanek Charles
Published: October 2004

ATM was the focus of active research and significant investment in the early to mid 1990's. This paper discusses several visions for ATM prevalent at the time, and analyzes how ATM evolved during this period. The paper also considers the implications of this history for current connection-oriented technologies, such as optical transport networks and MPLS.
Implementation experience with MANET routing protocols
Authors: Chin Kwan-Wu , Judge John , Williams Aidan , Kermode Roger
Published: October 2004

This paper outlines our experience with the implementation and deployment of two MANET routing protocols on a five node, four hop, network. The work was prompted by the lack of published results concerning the issues associated with the implementation of MANET routing protocols on actual wireless networks, as opposed to results of simulation experiments. We examined implementations of two distance vector MANET routing protocols and found a number of problems with both protocols during the course of our experiments. The most significant was that neither protocol could provide a stable route over any multi-hop network connection. The route discovery process of both protocols is fooled by the transient availability of network links to nodes that were more than one hop away. Packets transmitted over a fading channel cause the routing protocol to conclude incorrectly that there is a new one hop neighbor that could provide a lower metric (hop count) route to even more distant nodes. This can occur even when nodes are stationary, mobility resulted in even less route stability. We implemented a simple signal strength based neighbor selection procedure to test our assertion that fading channels and unreliable network links were the cause of the failure of the routing protocols. The result was that neighbor discovery and the filtering for neighbors with which nodes could communicate reliably enables the creation of reliable multihop routes. Based on our experiences, we outline several recommendations for future work in MANET research.
Hop-by-hop routing algorithms for premium traffic
Authors: Wang Jun , Nahrstedt Klara
Published: October 2004

In Differentiated Service (DiffServ) networks, the routing algorithms used by the premium class traffic, due to the high priority afforded to that traffic, may have a significant impact not only on the premium class traffic itself, but on all other classes of traffic as well. The shortest hop-count routing scheme, used in current Internet, turns out to be no longer sufficient in DiffServ networks. This paper studies the problem of finding optimal routes for the premium-class traffic in a DiffServ domain, such that (1) no forwarding loop exists in the entire network in the context of hop-by-hop routing; and (2) the residual bandwidth on bottleneck links is maximized. This problem is called the Optimal Premium-class Routing (OPR) problem. We prove in this paper that the OPR problem is NP-hard.To handle the OPR problem, first, we analyze the strength and weaknesses of two existing algorithms (Widest-Shortest-Path algorithm and Bandwidth-inversion Shortest-Path algorithm). Second, we propose a novel heuristic algorithm, called the
Enhanced Bandwidth-inversion Shortest-Path (EBSP) algorithm
. We prove theoretically the correctness of the EBSP algorithm, i.e., we show that it is
consistent
and loop-free. Our extensive simulations in different network environments show clearly that the EBSP algorithm performs better when routing the premium traffic in complex, heterogeneous networks.
Network pointers
Authors: Tschudin Christian , Gold Richard
Published: October 2004

The Internet architecture can be characterized as having a rather coarse grained and imperative style of network packet handling: confronted with an IP packet and its source and destination addresses, the infrastructure almost blindly and unalterably executes hundreds of resolution, routing and forwarding decisions. There are numerous attempts that try to "extend" the Internet in order to either reduce the immediate impact an arbitrary packet can have (e.g., NAT), or to insert diversions from the normal processing paths in order to better use the existing resources (e.g., content delivery). In this paper we argue that we need a more fine grained control, in the hands of end nodes, over how packets are handled. The basic abstraction presented here is that of networking pointers, which we show to relate to low level concepts like ARP caches, but also high level routing decisions for terminal mobility, content delivery networks, or peer-to-peer overlay forming. We report on first implementation experiences of an "underlay" networking approach which uses pointer tricks underneath IP in order to provide new network layer services.
The scaling hypothesis
Authors: Psounis Konstantinos , Pan Rong , Prabhakar Balaji , Wischik Damon
Published: October 2004

As the Internet grows, so do the complexity and computational requirements of network simulations. This leads either to unrealistic, or to prohibitely expensive simulation experiments.We explore a way to side-step this problem, by combining simulation with sampling and analysis. Our hypothesis is this: if we take a sample of the traffic, and feed it into a suitably scaled version of the system, we can extrapolate from the performance of the scaled system to that of the original.We find that when we scale a network which is shared by TCP-like flows, and which is controlled by a variety of active queue management schemes, then performance measures such as queueing delay and the distribution of flow transfer times are left virtually unchanged. Hence, the computational requirements of network simulations and the cost of experiments can decrease dramatically.
Toward an optimization-driven framework for designing and generating realistic Internet topologies
Authors: Alderson David , Doyle John , Govindan Ramesh , Willinger Walter
Published: October 2004

We propose a novel approach to the study of Internet topology in which we use an optimization framework to model the mechanisms driving incremental growth. While previous methods of topology generation have focused on explicit replication of statistical properties, such as node hierarchies and node degree distributions, our approach addresses the economic tradeoffs, such as cost and performance, and the technical constraints faced by a single ISP in its network design. By investigating plausible objectives and constraints in the design of actual networks, observed network properties such as certain hierarchical structures and node degree distributions can be expected to be the natural by-product of an approximately optimal solution chosen by network designers and operators. In short, we advocate here essentially an approach to network topology design, modeling, and generation that is based on the concept of
Highly Optimized Tolerance (HOT)
. In contrast with purely descriptive topology modeling, this opens up new areas of research that focus on the
causal
forces at work in network design and aim at identifying the economic and technical drivers responsible for the observed large-scale network behavior. As a result, the proposed approach should have significantly more predictive power than currently pursued efforts and should provide a scientific foundation for the investigation of other important problems, such as pricing, peering, or the dynamics of routing protocols.
Lowering the barrier to wireless and mobile experimentation
Authors: White Brian , Lepreau Jay , Guruprasad Shashi
Published: October 2004

The success of
ns
highlights the importance of an infrastructure that enables efficient experimentation. Similarly, Netbed's automatic configuration and control of emulated and live network environments minimizes the effort spent configuring and running experiments. Learning from the evolution of these systems, in this paper we argue that a live wireless and mobile experimental facility focusing on ease of use and accessibility will not only greatly lower the barrier to research in these areas, but that the primary technical challenges can be overcome.The flexibility of Netbed's common abstractions for diverse node and link types has enabled its development from strictly an emulation platform to one that integrates simulation and live network experimentation. It can be further extended to incorporate wireless and mobile devices. To reduce the tedium of wireless and mobile experimentation, we propose automatically allocating and mapping a subset of a dense mesh of devices to match a specified network topology. To achieve low-overhead, coarse repeatability for mobile experiments, we outline how to leverage the predictability of passive couriers, such as PDA-equipped students and PC-equipped busses.