bluuebunny/crossref_metadata_2025_split huggingface dataset:
ALOHA packet system with and without slots and capture
Authors: Roberts Lawrence G. 
Published: October 2004

This paper was originally distributed informally as ARPA Satellite System Note 8 on June 26, 1972. The paper is an important one and since its initial limited distribution, the paper has been frequently referenced in the open literature, but the paper itself has been unavailable in the open literature. Publication here is meant to correct the previous gap in the literature.
As the paper was originally distributed only to other researchers intimately familiar with the area covered by the paper, the paper makes few concessions to the reader along the lines of introductory or tutorial material. Therefore, a bit of background material follows.
ALOHA packet systems were originally described by Abramson ("The ALOHA System--Another Alternative for Computer Communication," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 37, 1970, pp. 281--285). In an ALOHA a single broadcast channel is shared by a number of communicating devices. In the version originally described by Abramson, every device transmits its packets independent of any other device or any specific time. That is, the device transmits the whole packet at a random point in time; the device then times out for receiving an acknowledgment. If an acknowledgment is not received, it is assumed that a collision occured with a packet transmitted by some other device and the packet is retransmitted after a random additional waiting time (to avoid repeated collisions). Under a certain set of assumptions, Abramson showed that the effective capacity of such a channel is 1/(2e).
Roberts in the present paper investigates methods of increasing the effective channel capacity of such a channel. One method he proposes to gain in capacity is to consider the channel to be slotted into segments of time whose duration is equal to the packet transmission time, and to require the devices to begin a packet transmission at the beginning of a time slot. Another method Roberts proposes to gain in capacity is to take advantage of the fact that even though packets from two devices collide in the channel (i.e., they are transmitted so they pass through the channel at overlapping times), it may be possible for the receiver(s) to "capture" the signal of one of the transmitters, and thus correctly receive one of the conflicting packets, if one of the transmitters has a sufficiently greater signal than the other. Roberts considers the cases of both satellite and ground radio channels.
Dynamic multi-path routing and how it compares with other dynamic routing algorithms for high speed wide area network
Authors: Bahk Saewoong , El Zarki Magda 
Published: October 2004

In this paper we describe briefly a dynamic multi-path routing scheme that has been considered for connection oriented homogeneous high speed networks. The fundamental objective of the scheme is to bridge the gap between routing and congestion control as the network becomes congested. Because propagation delay far out shadows queueing and transmission delay in high speed networks, the proposed routing scheme works as a shortest path (minimum hop) first algorithm under light traffic conditions. However as the shortest path becomes congested, the source node uses multiple paths when and if available in order to distribute the load and reduce packet loss. The scheme is a cross between Alternate Path routing and Trunk Reservation.
We compare the performance of the proposed scheme with the Shortest Path Only algorithm, the Alternate Path routing algorithm, the Random Routing algorithm, and the Trunk Reservation scheme. The throughput and packet loss performance are compared via simulations. These have been carried out concentrating on a 5 node network with varying traffic patterns, the intention being to gain insight into the strengths and weaknesses of the various schemes.
Continuous media communication with dynamic QOS control using ARTS with an FDDI network
Authors: Tokuda Hideyuki , Tobe Yoshito , Chou Stephen T.-C. , Moura José M. F. 
Published: October 2004

Continuous media communication requires timely delivery of data such as digital video and audio packets. Quality of Service (QOS) parameters specify the temporal and spatial characteristic of such continuous media data. To insure timely delivery of continuous media data, the system needs to minimize the communication delay by securing required processor and network resources. We have extended the Capacity-Based Session Reservation Protocol(CBSRP), which was proposed to realizing predictable real-time communications, to support dynamic control of QOS. We have implemented a QOS control scheme by which the network dynamically adjusts the allocations of network bandwidth on a Fiber Distributed Data Interface(FDDI) network.
In this paper, we describe the definition of our QOS model, the extension of CBSRP to support dynamic control of QOS, and the implementation and evaluation of extended CBSRP in our distributed systems testbed, Advanced Real-Time System(ARTS).
Multicast and multiprotocol support for ATM based Internets
Authors: Armitage G. J. 
Published: October 2004

Both the Internet Engineering Task Force (IETF) and ATM Forum are addressing the issue of building higher layer networks using ATM. The IETF's focus is on IP, while the ATM Forum has expanded its vision to include all common Network layer protocols. The task faced by both organizations is to develop solutions that will cause minimal interoperability problems, both for users and network architects.
This paper focuses on the solutions coming out of the IETF's IP over ATM working group, including the author's proposal for flexible, high performance IP multicast over ATM. The emerging Next Hop Resolution Protocol from the IETF's Routing Over Large Cloud group is briefly examined, and its possible conflict with the ATM Forum's Multiprotocol Over ATM'work is also discussed. The author finishes by noting how current IETF work could support 'multiprotocol' networks.
Development of a TCP/IP for the IBM/370
Authors: Brandriff Robert K. , Lynch Clifford A. , Needleman Mark H. 
Published: October 2004

This paper describes the design and implementation decisions that have been made in developing software to support the DARPA TCP/IP protocols for the IBM OS/370 environment at the University of California Division of Library Automation. The implementation is designed to support over 100 concurrent TCP connections, all of which are managed by a single program, which acts as a specialized sub-operating system. The system is optimized for line-by-line or screen-by-screen terminal traffic rather than character-by-character traffic. In addition, this TCP is designed to exploit the availability of the large main storage and processor speed available on the IBM/370.
TCP/IP is generally considered to be a mature protocol specification; however, in the course of our implementation we found several parts to be either ambiguous or problematic — in particular, error handling and notification, ICMP and its relationship to other protocols, and synchronization of data flow with TCP callers.
We also discuss problems encountered in trying to replace hardwired terminals in a public access environment with TCP and TELNET, and some protocol changes that would make these protocols more hospitable to our environment.
An algorithm for distributed computation of a spanningtree in an extended LAN
Authors: Perlman Radia 
Published: October 2004

A protocol and algorithm are given in which bridges in an extended Local Area Network of arbitrary topology compute, in a distributed fashion, an acyclic spanning subset of the network.
The algorithm converges in time proportional to the diameter of the extended LAN, and requires a very small amount of memory per bridge, and communications bandwidth per LAN, independent of the total number of bridges or the total number of links in the network.
Algorhyme

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

A tree whose crucial property Is loop-free connectivity.

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

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

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

A mesh is made by folks like me Then bridges find a spanning tree.
Domain names (panel session, abstract only)
Authors: Comer Douglas E. 
Published: October 2004

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

The domain scheme raises other questions. In principle, the hierarchical structure of domain names permits easy delegation of naming authority because it allows names within independent subtrees to be assigned by independent organizations. In practice, however, the hierarchical scheme collects together organizations under fixed top-level domains. Because extremely small organizations cannot afford to maintain a domain name server, they must be supported by (and obey the authority of) a domain server for the subhierarchy under which they lie.
A hierarchical organization of names also imposes restrictions on the use of the system. For example, even though domain name servers contain (name, address) pairs, it is impossible to locate the desired binding given only the address.
Chairman's remarks (panel session, abstract only)
Authors: Buttle T. C. 
Published: October 2004

From its experimental 1968 inception in ARPANET, followed by CCITT standardization of the X.25 protocol in 1976, packet switching now provides inexpensive worldwide data communications capabilities for its subscribers. Customer connections to public packet switched network services are increasing at a phenomenal rate, typically 30-40% year over year with no foreseen slowdown. This 2-3 year doubling effect presents numerous challenges to network operators in trying to effectively support and evolve their packet switched networks while simultaneously increasing customer service levels.
This Panel presents an overview of current customer packet switching applications and then focuses on how network operators are innovatively meeting the challenges presented by high growth on the operation, control, support, configuration and evolution of their packet switched networks.
A protocol-independent technique for eliminating redundant network traffic
Authors: Spring Neil T. , Wetherall David 
Published: October 2004

We present a technique for identifying repetitive information transfers and use it to analyze the redundancy of network traffic. Our insight is that dynamic content, streaming media and other traffic that is not caught by today's Web caches is nonetheless likely to derive from similar information. We have therefore adapted similarity detection techniques to the problem of designing a system to eliminate redundant transfers. We identify repeated byte ranges between packets to avoid retransmitting the redundant data.
We find a high level of redundancy and are able to detect repetition that Web proxy caches are not. In our traces, after Web proxy caching has been applied, an additional 39% of the original volume of Web traffic is found to be redundant. Moreover, because our technique makes no assumptions about HTTP protocol syntax or caching semantics, it provides immediate benefits for other types of content, such as streaming media, FTP traffic, news and mail.
Time warp operating system
Authors: Jefferson D. , Beckman B. , Wieland F. , Blume L. , Diloreto M. 
Published: October 2004

This paper describes the Time Warp Operating System, under development for three years at the Jet Propulsion Laboratory for the Caltech Mark III Hypercube multi-processor. Its primary goal is concurrent execution of large, irregular discrete event simulations at maximum speed. It also supports any other distributed applications that are synchronized by virtual time.
The Time Warp Operating System includes a complete implementation of the Time Warp mechanism, and is a substantial departure from conventional operating systems in that it performs synchronization by a general distributed process rollback mechanism. The use of general rollback forces a rethinking of many aspects of operating system design, including programming interface, scheduling, message routing and queueing, storage management, flow control, and commitment.
In this paper we review the mechanics of Time Warp, describe the TWOS operating system, show how to construct simulations in object-oriented form to run under TWOS, and offer a qualitative comparison of Time Warp to the Chandy-Misra method of distributed simulation. We also include details of two benchmark simulations and preliminary measurements of time-to-completion, speedup, rollback rate, and antimessage rate, all as functions of the number of processors used.
Log files: an extended file service exploiting write-once storage
Authors: Finlayson R. , Cheriton D. 
Published: October 2004

A log service provides efficient storage and retrieval of data that is written sequentially (append-only) and not subsequently modified. Application programs and subsystems use log services for recovery, to record security audit trails, and for performance monitoring. Ideally, a log service should accommodate very large, long-lived logs, and provide efficient retrieval and low space overhead.

In this paper, we describe the design and implementation of the Clio log service. Clio provides the abstraction of
log files
: readable, append-only files that are accessed in the same way as conventional files. The underlying storage medium is required only to be append-only; more general types of write access are not necessary. We show how log files can be implemented efficiently and robustly on top of such storage media—in particular, write-once optical disk.

In addition, we describe a general application software storage architecture that makes use of log files.
This work was supported in part by the Defense Advanced Research Projects Agency under contracts N00039-84-C-0211 and N00039-86-K-0431, by National Science Foundation grant DCR-83-52048, and by Digital Equipment Corporation, Bell-Northern Research and AT&T Information Systems.
Separating data and control transfer in distributed operating systems
Authors: Thekkath Chandramohan A. , Levy Henry M. , Lazowska Edward D. 
Published: October 2004

Advances in processor architecture and technology have resulted in workstations in the 100+ MIPS range. As well, newer local-area networks such as ATM promise a ten- to hundred-fold increase in throughput, much reduced latency, greater scalability, and greatly increased reliability, when compared to current LANs such as Ethernet.
We believe that these new network and processor technologies will permit tighter coupling of distributed systems at the hardware level, and that distributed systems software should be designed to benefit from that tighter coupling. In this paper, we propose an alternative way of structuring distributed systems that takes advantage of a communication model based on remote network access (reads and writes) to protected memory segments.

A key feature of the new structure, directly supported by the communication model, is the separation of
data transfer
and
control transfer
. This is in contrast to the structure of traditional distributed systems, which are typically organized using message passing or remote procedure call (RPC). In RPC-style systems, data and control are inextricably linked—all RPCs must transfer both data and control, even if the control transfer is unnecessary.

We have implemented our model on DECstation hardware connected by an ATM network. We demonstrate how separating data transfer and control transfer can eliminate unnecessary control transfers and facilitate tighter coupling of the client and server. This has the potential to increase performance and reduce server load, which supports scaling in the face of an increasing number of clients. For example, for a small set of file server operations, our analysis shows a 50% decrease in server load when we switched from a communications mechanism requiring both control transfer and data transfer, to an alternative structure based on pure data transfer.
eNVy
Authors: Wu Michael , Zwaenepoel Willy 
Published: October 2004

This paper describes the architecture of eNVy, a large non-volatile main memory storage system built primarily with Flash memory. eNVy presents its storage space as a linear, memory mapped array rather than as an emulated disk in order to provide an efficient and easy to use software interface.
Flash memories provide persistent storage with solid-state memory access times at a lower cost than other solid-state technologies. However, they have a number of drawbacks. Flash chips are write-once, bulk-erase devices whose contents cannot be updated in-place. They also suffer from slow program times and a limit on the number of program/erase cycles. eNVy uses a copy-on-write scheme, page remapping, a small amount of battery backed SRAM, and high bandwidth parallel data transfers to provide low latency, in-place update semantics. A cleaning algorithm optimized for large Flash arrays is used to reclaim space. The algorithm is designed to evenly wear the array, thereby extending its lifetime.
Software simulations of a 2 gigabyte eNVy system show that it can support I/O rates corresponding to approximately 30,000 transactions per second on the TPC-A database benchmark. Despite the added work done to overcome the deficiencies associated with Flash memories, average latencies to the storage system are as low as 180ns for reads and 200ns for writes. The estimated lifetime of this type of storage system is in the 10 year range when exposed to a workload of 10,000 transactions per second.
Fine-grain access control for distributed shared memory
Authors: Schoinas Ioannis , Falsafi Babak , Lebeck Alvin R. , Reinhardt Steven K. , Larus James R. , Wood David A. 
Published: October 2004

This paper discusses implementations of fine-grain memory access control, which selectively restricts reads and writes to cache-block-sized memory regions. Fine-grain access control forms the basis of efficient cache-coherent shared memory. This paper focuses on low-cost implementations that require little or no additional hardware. These techniques permit efficient implementation of shared memory on a wide range of parallel systems, thereby providing shared-memory codes with a portability previously limited to message passing.
This paper categorizes techniques based on where access control is enforced and where access conflicts are handled. We incorporated three techniques that require no additional hardware into Blizzard, a system that supports distributed shared memory on the CM-5. The first adds a software lookup before each shared-memory reference by modifying the program's executable. The second uses the memory's error correcting code (ECC) as cache-block valid bits. The third is a hybrid. The software technique ranged from slightly faster to two times slower than the ECC approach. Blizzard's performance is roughly comparable to a hardware shared-memory machine. These results argue that clusters of workstations or personal computers with networks comparable to the CM-5's will be able to support the same shared-memory interfaces as supercomputers.
Rethinking the TCP Nagle algorithm
Authors: Mogul J. C. , Minshall G. 
Published: October 2004

Modern TCP implementations include a mechanism, known as the Nagle
algorithm, which prevents the unnecessary transmission of a large number of small packets. This algorithm has proved useful in protecting the Internet against excessive packet loads. However, many applications suffer performance problems as a result of the traditional implementation of the Nagle algorithm. An interaction between the Nagle algorithm and TCP's delayed acknowledgement policy can create an especially severe problems, through a temporary “deadlock.” These flaws in the Nagle algorithm have prompted many application implementors to disable it, even in cases where this is neither necessary nor wise.
We categorize the applications that should and should not disable the Nagle algorithm, and we show that for some applications that often disable the Nagle algorithm, equivalent performance can be obtained through an improved implementation of the algorithm. We describe five possible modifications, including one novel proposal, and analyze their performance on benchmark tests. We also describe a receiver-side modification that can help in some circumstances.
Restricted data types, specification and enforcement of invariant properties of variables
Authors: Buckle Normand 
Published: October 2004

When defining a data type, it is often useful to specify restrictions on the permitted values of that type.
Pascal's subrange type declaration, a special case of this kind of constraint definition, has already proved itself to be quite useful. Restricted data types allow more complex constraints to be defined and checked; for example, a variable could be declared of type “odd integer” or the day field of a “date” type variable could be checked for consistency with the year and month fields.
A simple mechanism is proposed, allowing the formulation of such constraints and their association with data types; the behaviour of a restricted type variable is described. The effects of the use of such a mechanism on program reliability, readability and efficiency are discussed.
An experimental investigation of the effect of program structure on program understanding
Authors: Love Tom 
Published: October 2004

A within-subjects experimental design was used to test the effect of two variables on program understanding. The independent variables were complexity of control flow and paragraphing of the source code. Understanding was measured by having the subjects memorize the code for a fixed time and reconstruct the code verbatim. Also some subjects were asked to describe the function of the program after completing their reconstruction. The two groups of subjects for the experiment were students from an introductory programming class and from a graduate class in programming languages.
The major findings were that paragraphing of the source had no effect for either group of subjects but that programs with simplified control flow were easier for the computer science students to understand as measured by their ability to reconstruct the programs. The dependent variable, rated accuracy of their description of the programs functions, did not differ as a function of either independent variable.
The paper is concluded with a description of the utility of this experimental approach relative to improving the reliability of software and a discussion of the importance of these findings.