bluuebunny/crossref_metadata_2025 huggingface dataset:
An application of fault tolerance patterns and coordinated atomic actions to a problem in railway scheduling
Authors: Beder D. M. , Romanovsky A. , Randell B. , Snow C. R. , Stroud R. J.
Published: October 2004

Developing and applying advanced approaches for system structuring is vital for fighting ever-increasing complexity of modern and future software systems. The concept of Coordinated Atomic (CA) actions has been developed at Newcastle University for designing and structuring complex concurrent and distributed applications. Certain successful experience has been gained in applying them in several application areas. The purpose of the research, some initial results of which we report here, is twofold: to show how CA actions can be used in a new application area (a railway control system) and to analyse how the design patterns which have been developed using our previous experience can help in designing such system using CA actions.
Characterizing Internet performance to support wide-area application development
Authors: Ballintijn Gerco , van Steen Maarten
Published: October 2004

To help in our wide-area application development, we have done an informal study of the relation between wide-area latency, the number of routers, and geographical distance between Internet sites. We did this by performing ping and traceroute measurements between 19 sites distributed across the globe. Contrary to our expectation there is almost no correlation between distance, latency, and number of routers in the current Internet. To help further studies of these characteristics the problems of this pilot project are also described.
On a session key compromise problem in [KC95] protocol
Authors: Pei Pengjun , Cui Guohua , Peng Kun
Published: October 2004

Depending on the implementation assumptions we have made, we give an attack to the protocol proposed by Kao and Chow in [KC95] to show that it is not always secure when the session key is compromised. We also proposed a modification to counter this attack.
Strategies optimization and integration in DSM
Authors: Ji Li , Tianning Li , Guihai Chen , Li Xie , Wang C. L.
Published: October 2004

In large-scale parallel computing that may contain many nodes, a computing task is often divided into several sub-tasks running on a large platform. We present a group-based DSM model named GDSM. In our solution, sub-tasks are to be mapped to groups, which applies different techniques based on the distinct characteristics of inter-group and intra-group data sharing. A series of alternatives are employed with respect to the intra-group and inter-group property of this mechanism: (1) Consistency model: Release Consistency vs. Scope Consistency; (2) Coherence protocol: multiple-writer and write-update protocol vs. single-writer and write-invalidate protocol; (3) Granularity: fine-grain vs. coarse-grain. Our strategy to combine grouping with consistency and granularity switch enhances flexibility, cuts down the overhead of consistency maintenance, increases the parallelism between groups and thus promotes system performance. We also put forward the architecture of Protocol Engine based on group implementing the GDSM scheme, the engine that achieves message-forwarding transparency, clear hierarchical structure and encapsulation of group.
Factors influencing the formation of a user's perceptions and use of a DSS software innovation
Authors: Chiasson Mike W. , Lovato Chris Y.
Published: October 2004

Understanding how users form perceptions of a software innovation would help software designers, implementers and users in their evaluation, selection, implementation and on-going use of software. However, with the exception of some recent work, there is little research examining how a user forms his or her perceptions of an innovation over time. To address this research need, we report on the experiences of a health planner using a DSS software tool for health planning over a 12-month period. Using diffusion theory as outlined by Rogers, we interpret the user's perceptions of the software following Rogers' perceived characteristics of the innovation. Furthermore, we show how our user justifies her attitudes toward the technology using 5 important factors during 3-, 6- and 12-month interviews: stage of adoption, implementation processes, organizational factors, subjective norms, and user competence. Results are compared with key IS research in these areas, and the implications of these findings on the diffusion of decision support systems are discussed.
Preliminary evidence for the effect of automatic responses to authority on information technology diffusion
Authors: Cooper Randolph B. , Bhattacherjee Anol
Published: October 2004

Successful diffusion of IT within an organization can depend on IT use decisions by many individuals. Current rational models focusing on cognitive determinants of such IT use decisions explain 30 to 40 percent of organizational members' use behaviors. This article demonstrates, via a laboratory study, that automatic unthinking responses may be significant in explaining user behavior. We find that automatic responses to authority, that are cued by incentives and controls, may explain more than 20 percent of IT use variance, over and above that accounted for by rational decision making. This suggests interesting opportunities for IT diffusion research, exploring automatic IT use responses resulting from authority, as well as other automatic response generators such as reciprocation and consistency.
Organizational adoption and assimilation of complex technological innovations
Authors: Gallivan Michael J.
Published: October 2004

This paper explores the applicability of traditional innovation adoption and diffusion models to contingent, authority innovation processes occurring within an organizational context (Zaltman, Duncan & Holbeck, 1973); that is, when employees in organizations adopt an innovation that has been chosen by an authority figure. This paper identifies existing gaps in traditional innovation adoption models and concludes that a new framework is required --- one that incorporates the unique processes and factors related to organizational adoption and assimilation of innovations. A new hybrid theoretical framework is developed which combines insights from organizational-level research on technology implementation (Cooper & Zmud, 1990; Orlikowski, 1993) with constructs from traditional innovation adoption models (Rogers, 1983; Prescott & Conger, 1995). The resulting theory is a hybrid process/variance theory, which captures both implementation events and the factors that influence them (Shaw & Jarvenpaa, 1997). Data from a longitudinal case study of a firm that implemented client/server development are used to illustrate the framework and to develop propositions for future research.
The impact of culture and gender on web sites
Authors: Simon Steven John
Published: October 2004

The growth of electronic commerce, in particular business-to-consumer, has been explosive during the last few years. Until recently, the Web community has been a male dominated western-oriented society, with the design of Web sites reflecting that homogenous audience. Using an adapted version of Hofstede's dimensions as a means of differentiation, this study explores the perception and satisfaction levels of one hundred and sixty subjects on four web sites. Analysis indicates that perception and satisfaction differences exist between the cultural clusters and gender groups within those cultures --- Asia, Europe, Latin & South America, and North America. In particular, the perceptions of the Asian and Latin/South American were found to be similar, as were the perceptions of the Europeans and North Americans. Qualitative analysis indicates that females within certain cultures have widely different preferences from their male counterparts regarding web site attributes.
Formal participation and performance of the system development group
Authors: Aladwani Adel M. , Rai Arun , Ramaprasad Arkalgud
Published: October 2004

This study examines the influence of two selected group structural characteristics on successful participation in system development. It draws upon work-group design research to develop and test nine hypotheses that link group heterogeneity and group-based rewards to participation and performance outcomes. Some interesting findings emerge from the study.The nature of the relationship between group heterogeneity and participation is not the same as that between group-based rewards and participation. Both heterogeneity and group-based rewards directly impact participation; and as participation positively impacts outcomes, both variables indirectly impact outcomes. In addition, group-based rewards have a direct effect on performance outcomes, while no direct effect is detected between heterogeneity and performance outcomes. Contrary to conventional wisdom, this study found the effect of group-based rewards on participation is not always positive. The study suggests that group-based rewards could suppress participation in heterogeneous system development groups. The study concludes with a discussion of the implications of these findings for managerial practice and future research.
The effect of data model, system and task characteristics on user query performance
Authors: Chan Hock , Siau Keng , Wei Kwok-Kee
Published: October 2004

With the proliferation of end-user computing and empowerment of end users in the organizations, the user-database interface is increasingly being recognized as an important research area. A user-database interface consists of two key components: the data model and the query language. Database management system designers can manipulate these two components to produce an effective database interface to maximize user task performance. However, in order to do this, the designers first need to know the effect of the two components on end users and the interaction effect of the two components. Despite the acknowledgment of user-database interface as a cornerstone in database utilization, there is still a paucity of research in this area.In this paper, we report on an empirical study that investigates the effect of entity-relationship versus relational models, and textual versus visual query languages for user-database interfaces. A good understanding of how the data models and query languages affect the user performance will enable the database developer to choose and design interfaces that can provide effective and efficient support for end users.
Computer-assisted evaluation of interface designs
Authors: Khalifa Mohamed
Published: October 2004

Research in human-computer interaction has resulted in the development of task-theoretic analytical models that allow interface designers to evaluate the interface design on paper before building a prototype. Despite the potential of such models to reduce interface development costs and improve design quality, they are not widely used. We believe that the complexity of these models is the main impediment and propose a computer system to remove this obstacle. The proposed system enables interface designers to describe an interface design formally and then assess it in terms of usability dimensions such as ease of learning and ease of use. It facilitates and structures task analysis and spares designers the burden of learning the complex syntax of analytical models. This paper describes the proposed system and discusses an empirical study designed to evaluate it. The empirical results show that the proposed system improves the accuracy and speed of evaluation of interface designs and contributes to more favorable attitudes towards analytical models.
Ada 95 bindings for the NCSA hierarchical data format
Authors: Barkstrom Bruce R.
Published: October 2004

This paper describes Ada95 bindings for HDF4 and HDF5, the current versions of the NCSA Hierarchical Data Format (HDF). These self-describing file formats are intended for storage of large, diverse collections of scientific data and for retrieving subsets of these data. The libraries also support data compression, chunking of large arrays, and automatic conversion of vendor-specific binary formats for a variety of data types.
Implementing a product line-based architecture in Ada
Authors: Sherrill Joel , Averett Jennifer , Humphrey Glenn
Published: October 2004

This paper describes a software component model that encourages reuse in application families by recognizing and leveraging similarities between products within a product family, as well as among product families themselves. By applying a product-oriented view, developers gain insight into the capabilities of the organization's products and can leverage that insight to incorporate common software components across the entire enterprise. This component model is being applied to an existing family of similar embedded systems whose application software is written in Ada. Features of this language will be examined in the context of how they facilitate construction of reusable product line-based components.
Ship system 2000, a stable architecture under continuous evolution
Authors: Källberg Björn , Stråhle Rei
Published: October 2004

Ship System 2000 was conceived in the middle of the 1980s. It was started as a development project for a general Command and Control and Weapon Control Systems for naval ships (C2 and WCS), intended for reuse. Its first use was for three different ship types. Following these orders, later deliveries with similar functionality were made. From the beginning the company chose to use the Ada language for future systems in this area and selected Rational as the first programming environment. A strategic decision was made to include all the Ada components developed in a family of reusable components. The number of components has grown and variants for different platforms and compilers have been included. In the early days the word was
Reuse,
and later the terms
Dual Life Cycle
and
Product Line Management
have been introduced for the same concept. Since then, the 1
st
generation has been successfully reused for ships from many other navies and air forces. However, the architecture has evolved in two major steps, and several minor steps. Thus, it is still a modern architecture, but with a heritage.
Beyond ASIS
Authors: Laski Janusz , Stanley William , Podgorski Pawel
Published: October 2004

The availability of higher level ASIS libraries is of prime importance for the real success of ASIS technology to facilitate the development of Software Analysis and Testing (SAT) tools. This is due to the fact that ASIS queries are expressed in terms of the syntax of an immensely complex language and do not directly support the objectives of a tool builder. In this paper we discuss two plausible sets of higher levels, tool-oriented queries about the Program Under Analysis (PUA), which ideally do not require the knowledge of ASIS. We first present our experience with using ASIS to develop the front end of SWAT (SoftWare Analysis and Testing), a comprehensive system for static and dynamic (execution-based) software analysis. In it, ASIS is used to retrieve the information about the PUA and store it in Program Data Bases (PDBs). Then, an SAT tool uses the PDBs rather than ASIS to get the necessary information about the PUA. We hypothesize that the access functions to the PDBs can be viewed as second-level queries about the PUA; if well thought-out, a claim not made here, those queries can be used to build a wide class of program browsers. If, however, a more complicated tool is needed, a third level of queries can be specified. We illustrate that possibility by briefly showing how SEER, SWAT's dependency analyzer, uses several PDBs to carry out the dependency analysis whose results are stored in the
derived
PDBs; they are produced by processing the data in the original,
primary
PDBs. Again, the relations stored in the secondary PDBs gives rise to the third level queries about the PUA. It is obvious that higher level queries neither have to be implemented by an underlying ASIS layer nor the PDBs have to be used for that purpose. The main motivation here was to do that analysis
without
a
direct
use of ASIS. Indeed, we stress the importance of research into various SAT tools that would provide guidance in the definition of an "optimal" query language. In particular, we emphasize the need for ASIS queries that support dynamic, execution-based program analysis.
Targeting Ada95/DSA for distributed simulation of multiprotocol communication networks
Authors: Gantsou Dhavy
Published: October 2004

This paper describes the use of Ada95/DSA as middleware for modeling network's entities into distributed objects which can be used for both distributed execution and simulation without transformation of the model. First, general issues of simulation of network's entities are briefly presented. Then, the paper shows how DSA features are used to abstract these entities in a manner as they can be executed or simulated on a cluster of workstations. The DSA based model of distributed simulation is built on a combination of two kinds of classes: the first one support general purpose of distributed objects computing and the second deal with the development of distributed network elements. To illustrate the feasibility of this approach, a partial implementation of classes that have been used to model routers running a subset of border gateway protocol (BGP) is presented.
Dynamic analysis for locating product features in Ada code
Authors: White Laura J. , Wilde Norman
Published: October 2004

In this paper, we describe a Software Reconnaissance method for locating product features in code. The University of West Florida has provided a public domain Reconnaissance tool for C and C++. Characteristics of the Ada programming language present new interesting issues related to the development of a similar tool for Ada Reconnaissance, particularly its use in embedded systems, multi-tasking systems, and systems with real-time constraints. We describe our on-going efforts to develop a public domain Ada Reconnaissance tool.
Event-based implicit invocation decentralized in Ada
Authors: Xianzhong Liang , Zhenyu Wang
Published: October 2004

Nowadays more and more attraction is drawn by the event-based implicit invocation --- one of useful architectural patterns, because of its loose coupling between components in the architecture and reactive integration in software systems. Analyzing object-oriented interaction with objects, this paper, based upon the principle of software architecture, presents an approach on event-based object model with Ada exception handler. Consequently it is possible for us to improve, with adding specific architectural patterns, traditional programming languages into architectural description languages.
On the need for system-level support for ad hoc and sensor networks
Authors: Barr Rimon , Bicket John C. , Dantas Daniel S. , Du Bowei , Kim T. W. Danny , Zhou Bing , Sirer Emin Gün
Published: October 2004

Ad hoc and sensor networks are an important, emerging niche that is poorly supported by existing operating systems. In this paper, we argue that network-wide energy management is a primary concern in ad hoc networks, and that this functionality is best provided by a systems layer. We are currently designing and implementing a distributed, power-aware, adaptive operating system, called MagnetOS, specifically targeting ad hoc and sensor networks. MagnetOS provides a single system image of a unified Java virtual machine across the nodes that comprise an ad hoc network. By automatically and transparently partitioning applications into components and dynamically placing these components on nodes within the ad hoc network, our system reduces energy consumption, avoids hotspots and increases system longevity. We show that a systems approach to automatic object placement in an ad hoc network can increase system longevity by a factor of four to five.
A pragmatic alternative to undetachable signatures
Authors: Borselius Niklas , Mitchell Chris J. , Wilson Aaron
Published: October 2004

A 'pragmatic' alternative to undetachable signatures is proposed. Undetachable signatures were introduced by Sander and Tschudin, [4], as a means of giving a mobile agent the means to sign a message on behalf of a user, without endangering the user's private key. The alternative discussed in this paper involves the use of conventional signatures and public key certificates.
Interaction points
Authors: Waddington Daniel G. , Viswanathan Ramesh
Published: October 2004

This paper introduces the concept of "interaction points" which are currently used in an experimental programming environment, the In-process Modular Programming (IMP) platform. IMP is a Microsoft COM-style platform designed specifically for building component-based applications in real-time and embedded environments, and used for research prototyping at Lucent Technologies, Bell-labs. Interaction points serve as a unified abstraction for a wide range of inter-component communication mechanisms. They allow the programmer to easily take advantage of available operating system level mechanisms such as semaphores, shared memory, spinlocks and I/O buffers, in order to realise advanced inter-component communication paradigms. They excel in supporting broadcast and multicast communication, which are often difficult to realise with point-to-point communications such as those provided by conventional program function calls. In addition to supporting operating system mechanisms, interaction points also provide a mechanism for building re-useable custom communication facilities that are not themselves, considered worthy of componentisation. Finally, the use of interaction points helps to maintain an explicit definition of communications on component-interfaces and thus avoid problems of ill specified 'hidden' component interactions that often lead to problems during third party re-use.
On making TCP more robust to packet reordering
Authors: Blanton Ethan , Allman Mark
Published: October 2004

Previous research indicates that packet reordering is not a rare event on some Internet paths. Reordering can cause performance problems for TCP's fast retransmission algorithm, which uses the arrival of duplicate acknowledgments to detect segment loss. Duplicate acknowledgments can be caused by the loss of a segment or by the reordering of segments by the network. In this paper we illustrate the impact of reordering on TCP performance. In addition, we show the performance of a conservative approach to "undo" the congestion control state changes made in conjunction with spurious retransmissions. Finally, we propose several alternatives to dynamically make the fast retransmission algorithm more tolerant of the reordering observed in the network and assess these algorithms.
The impact of false sharing on shared congestion management
Authors: Akella Aditya , Seshan Srinivasan
Published: October 2004

Recently, several proposals have been made for sharing congestion information across concurrent flows between end-systems. In these proposals, the granularity for sharing has ranged from all flows to a common host to all hosts on a shared LAN. While these proposals have been successful at ensuring sound AIMD behavior of the aggregate of flows, they suffer from what we term "false sharing". False sharing occurs when two or more flows sharing congestion state may, in fact, not share the same bottleneck.In this work, we investigate the effects of false sharing on shared congestion management schemes. We characterize the origins of false sharing into two distinct cases: (i) networks with QoS enhancements such as differentiated services, where a flow classifier segregates flows into different queues, and (ii) networks with path diversity where different flows to the same destination address are routed differently --- a situation that occurs in dispersity routing, load-balancing, and with network address translators (NATs). We evaluate the impact of false sharing on flow performance and consider whether it might cause a bottleneck link to become persistently overloaded. We propose schemes for detecting false sharing and show how different metrics (loss rate, delay distribution, and reordering) compare for this purpose. We also consider the issue of how a sender should respond when it detects false sharing.
A measurement study of Napster and Gnutella as examples of peer-to-peer file sharing systems
Authors: Gummadi P. Krishna , Saroiu Stefan , Gribble Steven D.
Published: October 2004

In this paper, we present and analyze an extensive measurement study of Napster and Gnutella.
Measuring organizational IS effectiveness
Authors: Seddon Peter B. , Graeser Valerie , Willcocks Leslie P.
Published: October 2004

This paper reports the views of 80 senior IT managers about IT evaluation approaches, and the benefits that IT provides for their organizations. Their views were obtained through a survey mailed to medium to large organizations in both Europe and the US. The survey sought answers to three questions: How does the senior IT manager's organization assess the value of its (1) overall IT investment portfolio? (2) individual IT projects and applications? (3) IT function? Questions for the survey were based on a thorough review of prior research into IT evaluation. The paper provides a summary of that prior work and compares current findings to prior research. Consistent with prior research, the paper concludes that many firms do not conduct rigorous evaluations of all their IT investments, and offers a tentative explanation of why it might be rational to skip formal evaluations in some circumstances. It also posits five push factors to explain occasions when more lasting improvements in IT evaluation practice have occurred.
A resource-based analysis of IT sourcing
Authors: Roy Vital , Aubert Benoit A.
Published: October 2004

This paper studies the relationships between the choice of a sourcing mode for information systems, the value of the resources used in systems development activities and the presence of those resources at a sufficient level within the firm. The objective is to better understand the factors underlying the decision to keep the development of an information system inside the firm or to entrust it to an outside partner. A sourcing model is proposed using the resource-based theory. A case study is used to illustrate the concepts included in the research model. Data from this case illustrate how the model could be used to predict the appropriate sourcing mode, given the availability of the necessary resources and their strategic value.
Tasking communication deadlocks in concurrent Ada programs
Authors: Cheng J. , Araki K. , Ushijima K.
Published: October 2004

Tasking communication deadlock is one of most typical synchronization errors in concurrent Ada programs. In this article, we specify four kinds of tasking communication deadlocks, i.e., Circular-entry-calling, Dependence-blocking, Termination-blocking, and Acceptance-blocking. We also discuss briefly how to detect such deadlocks.
Ada translation tools development: automatic translation of FORTRAN to Ada
Authors: Parsian M. , Basdell B. , Bhayat Y. , Caldwell I. , Garland N. , Jubanowsky B. , Robinette J.
Published: October 2004

The problem addressed is how existent syntactically and semantically correct FORTRAN programs can be translated into Ada programs (library units). We present a system to find one possible form of translation. Our algorithm for translator system can be applied to generate translators from any source high level language into target language (Ada source code).
Topological analysis of local-area internetworks
Authors: Trewitt G.
Published: October 2004

It has become common to connect local-area networks together to form high-bandwidth internetworks. The topology of such an internetwork — how the component networks and gateways are interconnected — is an important factor in determining the reliability of the internet. We present several techniques for analyzing an internetwork's topology. These techniques are based on a novel mapping of network components onto a bipartite graph.

We use these techniques to analyze the topology of the Stanford University Network and the impact of topological changes as it has grown to its current size of 60 networks.
Optical interconnection using ShuffleNet multihop networks in multi-connected ring topologies
Authors: Karol M. J.
Published: October 2004

In many applications, such as metropolitan area, campus, and local area networks, multicomputer interconnection networks, and the interconnection of cabinets, shelves, and boards, optical interconnection is increasingly favored over electrical. Recently, ShuffleNet multihop lightwave networks were proposed as a way to tap the vast bandwidth potential of optical fiber for multiuser packet communications. We consider the use of ShuffleNet multihop networks for optical interconnection, and study their implementation in ring topologies with each node connected to several other nodes of the ring (i.e., multi-connected ring topologies). To minimize fiber cabling congestion, the design procedure uses a new representation of the ShuffleNet connectivity graph and a generalization of Gray code patterns. As an example, only six fibers (without wavelength-division multiplexing) are required to interconnect 24 Network Interface Units (NIUs), providing a total network throughput of 1.47 Gb/s for an optical transmission rate of 100 Mb/s. The design also provides for easy, modular growth of multi-connected rings.
The landmark hierarchy: a new hierarchy for routing in very large networks
Authors: Tsuchiya P. F.
Published: October 2004

Landmark Routing is a set of algorithms for routing in communications networks of arbitrary size. Landmark Routing is based on a new type of hierarchy, the Landmark Hierarchy. The Landmark Hierarchy exhibits path lengths and routing table sizes similar to those found in the traditional area or cluster hierarchy. The Landmark Hierarchy, however, is easier to dynamically configure using a distributed algorithm. It can therefore be used as the basis for algorithms that dynamically configure the hierarchy on the fly, thus allowing for very large, dynamic networks. This paper describes the Landmark Hierarchy, analyzes it, and compares it with the area hierarchy.
Pitfalls in the design of distributed routing algorithms
Authors: Perlman R. , Varghese G.
Published: October 2004

The bridge algorithm adopted by the IEEE 802.1 committee for interconnecting 802 LANs requires the topology of the Extended LAN to be a Spanning Tree. A distributed algorithm to compute a spanning tree dynamically has already been published [1], and adopted by the IEEE 802.1 committee [2]. In this paper, however, we describe an alternative distributed algorithm to compute a spanning tree. This algorithm, variants of which have been implemented, initially appears simpler than the IEEE 802.1 algorithm; we show, however, that it has subtle failure modes that makes it unattractive in practice.

We also show that some failure modes of the Spanning Tree Algorithm introduced in this paper are characteristic of a broader class of distributed graph algorithms. Such algorithms potentially examine all possible path combinations between a source and destination in a graph. Thus, they suffer from exponential message overhead in topologies that have an exponential number of paths between source and destination. Attempts to fix this problem lead to extra complexity (in terms of CPU, bandwidth, memory) when compared to other algorithms. We briefly describe a second example belonging to this class, and propose that designers avoid such algorithms if restricting the topology or scale of the network is unacceptable.
Multicast routing in internetworks and extended LANs
Authors: Deering S. E.
Published: October 2004

Multicasting is used within local-area networks to make distributed applications more robust and more efficient. The growing need to distribute applications across multiple, interconnected networks, and the increasing availability of high-performance, high-capacity switching nodes and networks, lead us to consider providing LAN-style multicasting across an internetwork. In this paper, we propose extensions to two common internetwork routing algorithms—distance-vector routing and link-state routing—to support low-delay datagram multicasting. We also suggest modifications to the single-spanning-tree routing algorithm, commonly used by link-layer bridges, to reduce the costs of multicasting in large extended LANs. Finally, we show how different link-layer and network-layer multicast routing algorithms can be combined hierarchically to support multicasting across large, heterogeneous internetworks.
Design of the
x
-kernel
Authors: Hutchinson N. , Peterson L.
Published: October 2004

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.
The fuzzball
Authors: Mills D. L.
Published: October 2004

The Fuzzball is an operating system and applications library designed for the PDP11 family of computers. It was intended as a development platform and research pipewrench for the DARPA/NSF Internet, but has occasionally escaped to earn revenue in commercial service. It was designed, implemented and evolved over a seventeen-year era spanning the development of the ARPANET and TCP/IP protocol suites and can today be found at Internet outposts from Hawaii to Italy standing watch for adventurous applications and enduring experiments. This paper describes the Fuzzball and its applications, including a description of its novel congestion avoidance/control and timekeeping mechanisms.
An analysis of Memnet—an experiment in high-speed shared-memory local networking
Authors: Delp G. , Sethi A. , Farber D.
Published: October 2004

Memnet is a shared-memory local area network under development at the University of Delaware that provides close coupling to the processors of a physically distributed multiprocessor system. The Memnet local network appears as memory in the physical address space of each processor (host) on the network.

This paper describes an analysis of the Memnet system performed to predict the possible performance levels attainable by a Memnet system. One objective of this analysis is to provide analytic results demonstrating the intrinsic soundness of the Memnet architecture. This is in support of the intuitive arguments of the shared-memory network model over the I/O modeled local network schemes. Another function of this analysis has been to provide design feedback for the choice of values for parameters such as page size.

The analysis results indicate that the Memnet approach to networking should significantly speed communication compared to alternative networking schemes.

Due to space limitations, the details of the analysis have not been included. The full text is available as TR-88-6-1 from: Department of Electrical Engineering, University of Delaware, Newark DE, 19716.
A pseudo-machine for packet monitoring and statistics
Authors: Braden R. T.
Published: October 2004

This paper concerns the design of a flexible and efficient packet monitoring program for analyzing traffic patterns and gathering statistics on a packet network. This monitor operates in real time, using an analyzer which is an interpretive pseudo-machine driving object-oriented data collection programs. The pseudo-program for the interpreter is “compiled” from configuration commands written in a monitoring control language.
Knowledge-based monitoring and control: an approach to understanding behavior of TCP/IP network protocols
Authors: Hitson B. L.
Published: October 2004

Complex, dynamic, and evolving network environments present difficult challenges for monitoring and control. We have encoded some of the expertise of human networking experts into a knowledge-based system that uses production rules and opportunistic scheduling, and have been using this system to better understand the behavior of the TCP/IP protocols and the applications that use them. Novel aspects of this research include understanding how to encode knowledge from this domain, and how to reason efficiently on real networking problems. The prototype system—KNOBS/TCP—can correctly identify many common problems that network experts would normally be required to find (
e.g.
, improper or inefficient retransmission and ACK strategies, silly-window-syndrome, a subset of reset and connection closing anomalies, and basic problems with auxiliary protocols such as address resolution, and routing). Preliminary measurements indicate that the resulting system is reasonably fast and will scale well. In some important test cases, speedup of two orders of magnitude over analogous manual and partially automated techniques has been observed.
Distributed testing and measurement across the Atlantic packet satellite network(SATNET)
Authors: Seo K. , Crowcroft J. , Spilling P. , Laws J. , Leddy J.
Published: October 2004

The analysis of the test and measurement of TCP/IP performance over the Atlantic Packet Satellite Network (SATNET) is described. Both the methodology and tools as well as the results and their analysis are discussed. Because of the Internetwork nature of the environment, the tests were designed to allow the SATNET Measurement Taskforce to look at the effects of each component of the end-to-end path, e.g., local networks, gateways, SATNET, and protocol layers. Results are given for the IP service provided by SATNET as a function of offered load and for TCP behavior as a function of offered load and the underlying IP service.
A multicast transport protocol
Authors: Crowcroft J. , Paliwoda K.
Published: October 2004

This paper presents the design of a reliable multicast transport protocol. The aim of the protocol is to provide a service equivalent to a sequence of reliable sequential unicasts between a client and a number of servers, whilst using the broadcast nature of some networks to reduce both the number of packets transmitted and the overall time needed to collect replies.

The service interface of the protocol offers several types of service, ranging from the collection of a single reply from any one of a set of servers to the collection of all replies from all known servers. The messages may be of effectively arbitrary size, and the number of servers may be quite large. To support this service over real networks, special flow control mechanisms are used to avoid multiple replies overrunning the client. Reliable delivery is ensured using timeouts and a distributed acknowledgement scheme. The protocol is implemented over a network layer which support multicast destination addressing and packet delivery. The behaviour of the protocol over both LANs and LANs interconnected by WAN lines is discussed. We also include some notions for possible future support from network interface hardware.
Experience with test generation for real protocols
Authors: Sidhu D. , Leung T.
Published: October 2004

This paper presents results on the application of four protocol test sequence generation techniques (T-, U-, D-, and W-methods) to the NBS Class 4 transport protocol (TP4). The ability of a test sequence to decide whether a protocol implementation conforms to its specification depend on the range of faults that it can capture. The study shows that a test sequence produced by the T-method has a poor fault detection capability whereas test sequences produced by the U-, D- and W-methods have comparable (superior to that for T-method) fault coverage on several classes of randomly generated machines. The lengths of test sequences produced by the four methods tend to be different. The length of a test sequence produced by the T-method (W-method) is the smallest (largest). The length of a test sequence from the U-method is smaller than that for the D-method and lengths for both are greater than that for the T-method and less than that for the W-method.
A high performance broadcast file transfer protocol
Authors: Daka J. S. J. , Waters A. J.
Published: October 2004

This paper describes a broadcast bulk file transfer protocol and presents its performance characteristics. The protocol is for bulk file distribution over a single satellite channel. The transmitting site and multiple receiver sites share channel access time to send data and acknowledgements.

The protocol performance characteristics are investigated using a simulation model that includes modelling of the uplink and downlink error processes at both the transmitter and receivers. The results obtained show that this protocol offers efficient reliable bulk file transfer to multiple receivers using a single satellite channel.
Delivery and discrimination: the Seine protocol
Authors: Gouda A. , Maxemchuk N. , Mukherji U. , Sabnani K.
Published: October 2004

We present two protocols for information exchange between multiple identical senders and a single receiver. At each instant, every sender sends one bit, and the bits from all of senders are or-ed together into one bit before being received by the receiver. If a sender has a data message to send, it sends the message bits one by one; otherwise it sends zero bits. Clearly, if the sending of two messages by two senders overlap, then the resulting “collision” can result in a corrupted message, i.e., one that was not sent by either sender. The function of the protocol is to deliver those and only those messages that are not corrupted by collision. (In other words, the receiver acts as a discriminating seine that catches and delivers only uncorrupted messages; hence the title.) The two protocols presented here are based on Manchester codes and general balanced codes, respectively.
A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer
Authors: Ramakrishnan K. K. , Jain Raj
Published: October 2004

We propose a scheme for
congestion avoidance
in networks using a connectionless protocol at the network layer. The scheme uses feedback from the network to the users of the network. The interesting challenge for the scheme is to use a minimal amount of feedback (one bit in each packet) from the network to adjust the amount of traffic allowed into the network. The servers in the network detect congestion and set a
congestion indication
bit on packets flowing in the forward direction. The congestion indication is communicated back to the users through the transport level acknowledgement.

The scheme is distributed, adapts to the dynamic state of the networks, converges to the optimal operating point, is quite simple to implement, and has low overhead while operational. The scheme also addresses a very important aspect of
fairness
in the service provided to the various sources utilizing the network. The scheme attempts to maintain fairness in service provided to multiple sources.

This paper presents the scheme and the analysis that went into the choice of the various decision mechanisms. We also address the performance of the scheme under transient changes in the network and for pathological conditions.
Congestion avoidance and control
Authors: Jacobson V.
Published: October 2004

In October of '86, the Internet had the first of what became a series of 'congestion collapses'. During this period, the data throughput from LBL to UC Berkeley (sites separated by 400 yards and three IMP hops) dropped from 32 Kbps to 40 bps. Mike Karels
1
and I were fascinated by this sudden factor-of-thousand drop in bandwidth and embarked on an investigation of why things had gotten so bad. We wondered, in particular, if the 4.3BSD (Berkeley UNIX) TCP was mis-behaving or if it could be tuned to work better under abysmal network conditions. The answer to both of these questions was “yes”.

Since that time, we have put seven new algorithms into the 4BSD TCP:

round-trip-time variance estimation

exponential retransmit timer backoff

slow-start

more aggressive receiver ack policy

dynamic window sizing on congestion

Karn's clamped retransmit backoff

fast retransmit Our measurements and the reports of beta testers suggest that the final product is fairly good at dealing with congested conditions on the Internet.

This paper is a brief description of (
i
) - (
v
) and the rationale behind them. (
vi
) is an algorithm recently developed by Phil Karn of Bell Communications Research, described in [KP87]. (
viii
) is described in a soon-to-be-published RFC.

Algorithms (
i
) - (
v
) spring from one observation: The flow on a TCP connection (or ISO TP-4 or Xerox NS SPP connection) should obey a 'conservation of packets' principle. And, if this principle were obeyed, congestion collapse would become the exception rather than the rule. Thus congestion control involves finding places that violate conservation and fixing them.

By 'conservation of packets' I mean that for a connection 'in equilibrium', i.e., running stably with a full window of data in transit, the packet flow is what a physicist would call 'conservative': A new packet isn't put into the network until an old packet leaves. The physics of flow predicts that systems with this property should be robust in the face of congestion. Observation of the Internet suggests that it was not particularly robust. Why the discrepancy?

There are only three ways for packet conservation to fail:

The connection doesn't get to equilibrium, or

A sender injects a new packet before an old packet has exited, or

The equilibrium can't be reached because of resource limits along the path. In the following sections, we treat each of these in turn.
A protocol to maintain a minimum spanning tree in a dynamic topology
Authors: Cheng C. , Cimet I. , Kumar S.
Published: October 2004

We present a distributed protocol for updating and maintaining a minimum-weight spanning tree (MST) in a network with changing topology. The protocol can respond to multiple link/node failures and recoveries that can occur at arbitrary times. Given that an arbitrary finite number of topological changes occur during a period, the protocol finds the MST corresponding to the latest network, within finite time after the last change. The message complexity of the protocol is O(m|E|+k|V|) when k link recoveries and m link failures occur, where |V| and |E| are the total number of nodes and links, respectively.
Fletcher's error detection algorithm: how to implement it efficiently and how toavoid the most common pitfalls
Authors: Nakassis Anastase
Published: October 2004

In what follows we pursue the following objectives:(a) to present efficient versions of Fletcher's Arithmetic Checksum Algorithm,(b) to discuss the issues that arise when these versions are implemented,(c) to present possible implementation independent shortcomings of the algorithm, and(d) to contrast its properties to those of a CRC encoding scheme.
Performance of the world's fastest distributed operating system
Authors: van Renesse Robbert , van Staveren Hans , Tanenbaum Andrew S.
Published: October 2004

Distributed operating systems have been in the experimental stage for a number of years now, but few have progressed to the point of actually being used in a production environment. It is our belief that the reason lies primarily with the performance of these systems---they tend to be fairly slow compared to traditional single computer systems. The Amoeba system has been designed with high performance in mind. In this paper some performance measurements of Amoeba are presented and comparisons are made with UNIX on the SUN, as well as with some other interesting systems. In particular, short remote procedure calls take 1.4 msec and long data transfers achieve a user-to-user bandwidth of 677 kbytes/sec. Furthermore, the file server is so fast that it is limited by the communication bandwidth to 677 kbytes/sec. The real speed of the file server is too high to measure. To the best of our knowledge, these are the best figures yet reported in the literature for the class of hardware used.