bluuebunny/crossref_metadata_2025 huggingface dataset:
An efficient communication protocol for high-speed packet-switched multichannel networks
Authors: Humblet Pierre A. , Ramaswami Rajiv , Sivarajan Kumar N.
Published: October 2004

This paper proposes a new media-access protocol for high-speed packet-switched multichannel networks based on a broadcast topology, for example, optical passive star networks using wavelength-division multiple access. The protocol supports connection-oriented traffic with or without bandwidth reservation as well as datagram traffic, in an attempt to integrate transport-layer functions with the media-access layer. It utilizes the bandwidth efficiently while keeping the processing requirements low by requiring stations to compute their transmission and reception schedules only at the start and end of each connection. A simple analysis shows that we can achieve low blocking probabilities for connections, as well as high network throughput.
A language-based approach to protocol implementation
Authors: Abbott Mark B. , Peterson Larry L.
Published: October 2004

Morpheus is special-purpose programming language that facilitates the efficient implementation of communication protocols. Protocols are divided into three categories, called
shapes
, so that they can inherit code and data structures based on their category; the programmer implements a particular protocol by refining the inherited structure. Morpheus optimization techniques reduce per-layer overhead on time-critical operations to a few assembler instructions even though the protocol stack is not determined until runtime. This supports divide-and-conquer simplification of the programming task by minimizing the penalty for decomposing complex protocols into combinations of simpler protocols.
Scalable inter-domain routing architecture
Authors: Estrin Deborah , Rekhter Yakov , Hotz Steven
Published: October 2004

As internets grow, both in size and in the diversity of routing requirements, providing inter-domain routing that can accommodate both of these factors becomes increasingly crucial. We propose a scalable inter-domain routing architecture consisting of two major components: source-demand routing (SDR) and node routing (NR).

The NR component pre-computes and installs routes that are shared by a significant number of sources. These
generic routes
are commonly used and warrant wide propagation. The SDR component provides on-demand computation and installation of
specialized routes
that are not shared by enough sources to justify computation by NR. The potentially large number of different specialized routes, combined with their sparse utilization, make them too costly to support with the NR mechanism. Together NR and SDR address the issue of scaling to global internet sizes without restricting the availability of a diverse set of routes. Routing will adapt naturally over time to changing traffic patterns and new services by shifting computation and installation of particular types of routes between the two components.

To complement earlier discussions of SDR design choices [3], this paper evaluates the algorithmic design choices for the NR component in terms of scalability and functionality. In addition, we discuss mechanisms for improving the scaling properties of link-state SDR, and for integrating the two components of the architecture.
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).
A continuous media transport and orchestration service
Authors: Campbell Andrew , Coulson Geoff , García Francisco , Hutchison David
Published: October 2004

The desire to transfer continuous media such as digital audio and video across packet switched networks imposes a number of new requirements on transport level communication services. This paper identifies a number of these requirements in the context of an experimental distributed multimedia infrastructure, and reports on research which addresses some of the associated issues. Particular attention is paid to two areas: (i) extended Quality of Service (QoS) provision; and (ii) support for the co-ordination of multiple related connections. We then describe an application level service, known as an orchestrator, which performs synchronisation functions over multiple related transport connections. We also outline the design and implementation of a continuous media transport service which meets the identified requirements. Finally, we outline the way in which the orchestrator and transport services are integrated into an object-based distributed multimedia application platform.
A hop by hop rate-based congestion control scheme
Authors: Mishra Partho P. , Kanakia Hemant
Published: October 2004

The flow/congestion control scheme of TCP is based on the sliding window mechanism. As we demonstrate in this paper, the performance of this and other similar end-to-end flow control schemes deteriorates as networks move to the gigabit range. This has been the motivation for our search for a new flow and congestion control scheme. In this paper, we propose as an alternative, a hop-by-hop rate-based mechanism for congestion control. Due to the increasing sophistication in switch architectures, to provide “quality of service” guarantees for real-time as well as bursty data traffic, the implementation of hop-by-hop controls has become relatively inexpensive. A cost-effective implementation of the proposed scheme for a multi-gigabit packet switch is described in [2]. In this paper, we present results of a simulation study comparing the performance of this hop-by-hop flow control scheme to two end-to-end flow control schemes. The results indicate that the proposed scheme displays stable behavior for a wide range of traffic conditions and diverse network topologies. More importantly, the performance of the scheme, measured in terms of the average number of occupied buffers, the end-to-end throughput, the network delay, and the link utilization at the bottleneck, is better than that of the end-to-end control schemes studied here. These results present a convincing case against popular myths about hop-by-hop control mechanisms.
A labeling algorithm for just-in-time scheduling in TDMA networks
Authors: Boncelet Charles G. , Mills David L.
Published: October 2004

This paper describes a scheduling algorithm for high speed, TDMA communication networks. The problem is to find a route and determine switch schedules so that a burst of information can traverse the network from source to destination. We show that this problem is difficult, i.e., that several simple variations are NP-complete. We present an algorithm that finds schedules, and within a simplifying assumption, is guaranteed to find a route if one exists. Simulations indicate that this algorithm runs quickly in practice and overall scheduling efficiencies of 80-90% can be achieved. We also describe a variation in which the problem is to find a repeating schedule and we show how to adapt the basic algorithm for this variation.
An evaluation framework for Multicast Ordering Protocols
Authors: Mayer Erwin
Published: October 2004

A new framework for evaluating Multicast Ordering protocols is presented. It allows to compare solutions to the problem of ordering multicast messages in an identical way at all receiving sites when multiple senders operate concurrently. A new type of delay measure called Synchronization Delay forms the basis for this framework. It filters out network-dependent factors and accounts precisely for the excess delay that user messages suffer in order to achieve the ordering property. The usefulness of the evaluation framework is demonstrated by applying it to three protocols covered in the literature. As an example their delay behavior is analyzed for low-traffic environments. The evaluation results allow a user to choose the most suitable protocol for his application.
Analyzing communication latency using the Nectar communication processor
Authors: Steenkiste Peter
Published: October 2004

For multicomputer applications, the most important performance parameters of a network is the latency for short messages. In this paper we present an analysis of communication latency using measurement of the Nectar system. Nectar is a high-performance multicomputer built around a high-bandwidth crosspoint network. Nodes are connected to the Nectar network using network coprocessors that are primarily responsible the protocol processing, but that can also execute application code. This architecture allows us to analyze message latency both between workstations with an outboard protocol engine and between lightweight nodes with a minimal runtime system and a fast, simple network interface (the coprocessors). We study how much context switching, buffer management and protocol processing contribute to the communication latency and we discuss how the latency is influenced by the protocol implementation.
Scheduling algorithms for multi-hop radio networks
Authors: Ramanathan S. , Lloyd Errol L.
Published: October 2004

New algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both
link scheduling
and
broadcast scheduling
are considered. In each instance scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. Theoretically, it is shown that tree networks can be scheduled optimally, and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network
thickness
times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree, the algorithms presented here represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods.
Joint scheduling and admission control for ATS-based switching nodes
Authors: Hyman Jay , Lazar Aurel A. , Pacifici Giovanni
Published: October 2004

A joint scheduling and admission control algorithm is presented for Asynchronous Time-Sharing (ATS)-based switching nodes carrying real-time traffic. Systems based on ATS guarantee quality of service, at both the levels of cells and calls, for three well-defined traffic classes. A mechanism is outlined by which an admission control strategy can be tailored to a particular mix of traffic classes. A mechanism is outlined by which an admission control strategy can be tailored to a particular mix of traffic by making use of high-level information from the scheduler. This mechanism is based on a
principle of separation
between scheduling and admission control. A linear programming formulation is used to find the admission control policy which will maximize the expected system utility while maintaining the guaranteed quality of service. The
admissible load region
is introduced as a means of quantifying the capacity of a switch under the QOS constraints at the cell and call levels. Numerical calculations for a single MAGNET II switching node carrying two classes of real-time traffic are used to illustrate the effects of different scheduling and admisssion control policies on both the expected utility and the admissible load region.
An analysis of wide-area name server traffic
Authors: Danzig Peter B. , Obraczka Katia , Kumar Anant
Published: October 2004

Over a million computers implement the Internet's Domain Name System of DNS, making it the world's most distributed database and the Internet's most significant source of wide-area RPC-like traffic. Last year, over eight percent of the packets and four percent of the bytes that traversed the NSFnet were due to DNS. We estimate that a third of this wide-area DNS traffic was destined to seven
root
name servers. This paper explores the performance of DNS based on two 24-hour traces of traffic destined to one of these root name servers. It considers the effectiveness of name caching and retransmission timeout calculation, shows how algorithms to increase DNS's resiliency lead to disastrous behavior when servers fail or when certain implementation faults are triggered, explains the paradoxically high fraction of wide-area DNS packets, and evaluates the impact of flaws in various implementations of DNS. It shows that
negative caching
would improve DNS performance only marginally in an internet of correctly implemented name servers. It concludes by calling for a fundamental change in the way we specify and implement future name servers and distributed applications.
Measuring, monitoring and enforcing CPU execution time
Authors: Burns A. , Wellings A. J.
Published: October 2004

Many real-time scheduling theories depend on the ability to measure or estimate the amount of CPU time processes require. Furthermore, they often required a limit to the amount of CPU time a process consumes at run-time. This paper considers the requirements these theories place on a language and its associated run-time support system. It also considers the extent to which Ada 9X meets these requirements.
The effect of expertise on software selection
Authors: Galletta Dennis , King Ruth C. , Rateb Dina
Published: October 2004

Selection of hardware and software is a complicated task involving the consideration of multiple criteria decision making (MCDM) as well as the expertise of the decision maker. Two MCDM studies examined whether or not expertise in database management systems (DBMS) would facilitate selection among DBMS alternatives. The results of the first study suggest that (I) experts seemed to exhibit more agreement on criterion weights than did novices, (2) experts were about twice as consistent in applying the weights they assigned to the choice task compared to novices, (3) novices tended to rate criteria with scores that were closer to the neutral midpoint than did experts, and (4) experts made different choices than did novices. Consistency was assessed using two different quantitative measures; one was based on ordinality and the other on position. In the second study, concurrent verbal protocols showed that experts tended to bring their own experience to the choice task, were distracted less frequently, and used superior strategies in elimination of weakest alternatives. This implies that staff members with significant domain expertise should be used in DBMS acquisition tasks. Future research should determine whether or not these findings generalize to other task domains.
On lazy natural numbers with applications to computability theory and functional programming
Authors: Escardó Martín Hötzel
Published: October 2004

Lazy natural numbers arise by lazy evaluation of the successor function. This work investigates fundamental mathematical properties of the domain
L
of lazy natural numbers, and presents applications to computability theory and functional programming. It is shown that certain functions on sets of natural numbers like cardinality-finding and emptyness-testing which are not continuous (or even monotonic) when sets are given by characteristic functions
N⊥ → T
are both continuous and computable when sets are given by characteristic functions
L → T
defined in an appropriate way. These functions are definable in λ calculus based functional programming languages provided some parallel features are available.
The implementation of expert systems
Authors: Tyran Craig K. , George Joey F.
Published: October 2004

A descriptive mail survey of managers of work groups using expert system (ES) technology was performed to gain insight into the management of the ES implementation process. This article presents survey results representing 45 different ES projects that have been successfully implemented in organizations. Each of the managers was asked to evaluate the importance of 13 factors to ES implementation success and to report on the organizational climate and practices related to ES implementation. The survey results are generally consistent with earlier implementation research and indicate that successful ES implementation requires management attention to a combination of organizational factors, implementation activities, and technical factors. Implementation practices that were associated with the successful ES implementations were commitment to the ES project, user participation, and management support.
Impact of mobility on distributed computations
Authors: Badrinath B. R. , Acharya Arup , Imieliński Tomasz
Published: October 2004

The integration of mobile/portable computers within existing static networks introduces a new set of issues to distributed computations. A mobile host can connect to the network from different locations at different times; distributed algorithms therefore, cannot rely on the assumption that a participant maintains a fixed and universally known location in the network at all times. Mobile hosts communicate with the rest of the network via a wireless broadcast medium and portable computers such as laptops and palmtops, often operate in a "disconnected" or "doze" mode to conserve battery power. These unique physical features of a mobile computing environment need to be considered as well, while designing distributed algorithms for such systems.
Causal controversy at Le Mont St.-Michel
Authors: van Renesse Robbert
Published: October 2004

As usual, the SIGOPS workshop provided a great platform for interesting discussion. Among other things, a controversy arose around the usefulness of causal ordering in a distributed system. In this paper, I explain causality in non-technical terms, and enumerate some of the most prevalent misconceptions that surrounded causality. Next I present some important examples where causal delivery is a necessary and sufficient ordering of events.
Parallel computing using idle workstations
Authors: Ju Jiubin , Xu Gaochao , Tao Jie
Published: October 2004

Enormous aggregate computing capacity in distributed computing systems composed of workstations connected by high speed local area networks may exceed that supercomputers often have. The Sidle (for Sharing Idle Workstatinos), a system for scheduling idle workstations and remote executing which is currently running on 19 SUN4 workstations connected by an Ethernet is presented in this paper. Sidle enables user's many programs or sections of a program to be executed parallelly on many idle workstations. Sidle has many features compared with existing systems: It allows more than one job to be run on an idle workstation and nested remote executing, makes use of CPU utilization much better, with more higher transparency to the users and better performance.
Lowness
Authors: Hemaspaandra Lane A.
Published: October 2004

This column gives a quick introduction to lowness theory [Sch83], which classifies the complexity of problems that are in NP but seem to be neither in P nor NP-complete.
Memory consistency models
Authors: Mosberger David
Published: October 2004

This paper discusses memory consistency models and their influence on software in the context of parallel machines. In the first part we review previous work on memory consistency models. The second part discusses the issues that arise due to weakening memory consistency. We are especially interested in the influence that weakened consistency models have on language, compiler, and runtime system design. We conclude that tighter interaction between those parts and the memory system might improve performance considerably.
Structured interrupts
Authors: Hills Ted
Published: October 2004

In this paper I refine the concept of
interrupt
to define a more structured mechanism with straightforward semantics. Some commonly implemented interrupt mechanisms are reviewed; their semantics are deduced and analyzed. I show how a different understanding of interrupts resolves the deficiencies of existing interrupt mechanisms and provides the programmer with powerful tools for addressing real-time and multiprocessing problems. On this basis a recommendation is made for architectural and operating system support of the improved interrupt mechanism.
A machine independent interface for lightweight threads
Authors: Mukherjee Bodhisattwa , Eisenhauer Greg , Ghosh Kaushik
Published: October 2004

Recently, lightweight thread libraries have become a common entity to support concurrent programming on shared memory multiprocessors. However, the disparity between primitives offered by operating systems creates a challenge for those who wish to create portable lightweight thread packages. What should be the interface between the machine-independent and machine-dependent parts of the thread library? We have implemented a portable lightweight thread library on top of Unix on a KSR-1 supercomputer, BBN Butterfly multiprocessor, SGI multiprocessor, Sequent multiprocessor and Sun 3/4 family of uniprocessors. This paper first compares the nature and performance of the OS primitives offered by these machines. We then present procedure-level abstraction that is efficiently implementable on all the architectures and is a sufficient base upon which a user-level thread package can be built.
Analysis of burstiness and jitter in real-time communications
Authors: Wang Zheng , Crowcroft Jon
Published: October 2004

This paper examines burstiness and jitter in real-time communications. In this paper, we make so assumptions about the arrival patterns of the incoming traffic but characterize the traffic with two parameters. We assume that the synchronization process is adaptive, so that the traffic stream can be divided into smaller synchronization units. The jitter is defined with the delay experienced by the first packet in a synchronization unit as the target delay. We present the results on the relationship between burstiness and jitter, and on the upper bounds of burstiness and jitter.
The synchronization of periodic routing messages
Authors: Floyd Sally , Jacobson Van
Published: October 2004

The paper considers a network with many apparently-independent periodic processes and discusses one method by which these processes can inadvertently become synchronized. In particular, we study the synchronization of periodic routing messages. We give examples of the harmful effect of these synchronized updates on other network traffic, and offer guidelines on how to avoid inadvertent synchronization. Using simulations and analysis, we study the process of synchronization and show that the transition from unsynchronized to synchronized traffic is not one of gradual degradation but is instead a very abrupt 'phase transition': in general, the addition of a single router will convert a completely unsynchronized traffic stream into a completely synchronized one. We show that synchronization can be avoided by the addition of randomization to the traffic sources and quantify how much randomization is necessary. In addition, we argue that the inadvertent synchronization of periodic processes is likely to become an increasing problem in computer networks.
Dynamics of internet routing information
Authors: Chinoy Bilal
Published: October 2004

The Internet is a complex mesh of networks that use a common suite (TCP/IP) of networking protocols. A key feature of the Internet is that all of these constituent networks are interconnected, thereby providing system wide communication. The magnitude and pattern of the flow of routing information directly represents the connectivity stability of the Internet. The NSFNET backbone network provides transit services to a large portion of the global Internet and maintains routing tables reflecting this current connectivity. These routing tables are constantly updated based on information received by the attached networks. This paper investigates the dynamics of routing information flow as presented to the NSFNET backbone network.
Implementing network protocols at user level
Authors: Thekkath Chandramohan A. , Nguyen Thu D. , Moy Evelyn , Lazowska Edward D.
Published: October 2004

Traditionally, network software has been structured in a monolithic fashion with all protocol stacks executing either within the kernel or in a single trusted user-level server. This organization is motivated by performance and security concerns. However, considerations of code maintenance, ease of debugging, customization, and the simultaneous existence of multiple protocols argue for separating the implementations into more manageable user-level libraries of protocols. This paper describes the design and implementation of transport protocols as user-level libraries.We begin by motivating the need for protocol implementations as user-level libraries and placing our approach in the context of previous work. We then describe our alternative to monolithic protocol organization, which has been implemented on Mach workstations connected not only to traditional Ethernet, but also to a more modern network, the DEC SRC ANI. Based on our experience, we discuss the implications for host-network interface design and for overall system structure to support efficient user-level implementations of network protocols.
Locking effects in multiprocessor implementations of protocols
Authors: Björkman Mats , Gunningberg Per
Published: October 2004

We investigate how to exploit shared memory multiprocessors for parallel protocol processing. We present a multiprocessor implementation of the x-kernel protocol environment from the University of Arizona. A "processor-per-message" paradigm is used to partition the work over processors. Locks are used to protect shared protocol state and data. Mutual exclusion by locking can be costly if the parallel protocol code frequently accesses shared state and data. This paper addresses the effect of locking on performance.The x-kernel is implemented in user address space on a Sequent Symmetry. Performance results of UDP/IP and TCP/IP are given, and we compare them to performance predictions from simulations. The measured speedups for the parallel implementations relative to the sequential ones are more than 12 times for UDP and 3 times for TCP. These limits are set by locking and machine contention.
Core based trees (CBT)
Authors: Ballardie Tony , Francis Paul , Crowcroft Jon
Published: October 2004

One of the central problems in one-to-many wide-area communications is forming the delivery tree - the collection of nodes and links that a multicast packet traverses. Significant problems remain to be solved in the area of multicast tree formation, the problem of scaling being paramount among these.In this paper we show how the current IP multicast architecture scales poorly (by scale poorly, we mean consume too much memory, bandwidth, or too many processing resources), and subsequently present a multicast protocol based on a new scalable architecture that is low-cost, relatively simple, and efficient. We also show how this architecture is decoupled from (though dependent on) unicast routing, and is therefore easy to install in an internet that comprises multiple heterogeneous unicast routing algorithms.
Routing reserved bandwith multi-point connections
Authors: Verma Dinesh C. , Gopal P. M.
Published: October 2004

Some important classes of multi-point bandwidth-intensive applications like video-conferencing with mixing and the distributed classroom can be characterized as consisting of a broadcast from a source node to several destinations nodes, and point-to-point flows from the destination nodes to the source node. Determining a tree in an arbitrary mesh network which satisfies the bandwidth constraints and minimizes the cost of reserved bandwidth is a NP-hard problem. In this paper, we look at some heuristics that can be used to solve the problem of routing these multi-point connections. The heuristics are based on finding the capacity-constrained minimum cost tree which minimizes the cost of bandwidth reserved for point-to-point communication from destinations to the source, and weights are assigned to minimize the number of extra nodes in the tree which increase the cost of bandwidth reserved from the source to the destination. A theoretical bound on the performance of some of the heuristics, as well as simulation results comparing their performance to that of the optimum solution are presented. The results are encouraging, the heuristics find a tree with a cost within 2% of the optimum on the average, and with a cost within 10% of the optimum in those cases when the heuristic fails to find the optimum tree.
Optimizing file transfer response time using the loss-load curve congestion control mechanism
Authors: Williamson Carey L.
Published: October 2004

Loss-load curves are a recently proposed feedback mechanism for rate-based congestion control in datagram computer networks. In the loss-load model, packet loss inside the network is a direct function of sender transmission rates, and senders have the responsibility of choosing their own transmission rate based on the loss-load tradeoff curve provided by the network. Earlier work has provided the mathematical basis for the loss-load model and provided preliminary simulation results demonstrating its responsiveness, fairness, and stability. The loss-load model works well for simple network environments where each source has many packets to transmit, and wishes to maximize raw throughput.In this paper, the applicability of loss-load curves is extended to senders with more general network traffic requirements, such as file transfer activities. In particular, the paper considers senders wishing to minimize the response time for a transfer of
N
packets. When
N
is small, a sender chooses a low transmission rate, to minimize the probability of packet loss. When
N
is large, a higher transmission rate is chosen to increase raw throughput. The loss-load curve mechanism provides necessary and sufficient information for senders at the edges of the network to choose a proper transmission rate based on their traffic requirements and the current network load.Simulation results show that the loss-load mechanism is effective in achieving high network utilization and minimizing response time for file transfers. The loss-load model also does a good job of providing equitable service to senders with different traffic workloads and different round trip times.
Control handling in real-time communication protocols
Authors: Shionozaki Atsushi , Tokoro Mario
Published: October 2004

In order to guarantee real-time services in a network architecture, resource reservation schemes seem most effective. In such protocols, dynamic protocol parameter control is necessary to support balanced quality of service for applications which are allocated the resources of the system, but timeliness of protocol control negotiation has never been emphasized.We have proposed RtP, a general purpose real-time protocol which supports virtual channels used exclusively for control information processing in an internet-work. However, our first proposal did not provide an effective mechanism for preallocating control channels thus presenting an overhead in gateways.This paper presents a simple new protocol for managing control reservations on each subnetwork of an internet; it is called the Virtual Control Setup Protocol (VCSP). It provides an interface between the network layer and the data link layer for ensuring the timeliness of control information. The effectiveness of VCSP is investigated and demonstrated by a prototype implementation.
A data labelling technique for high-performance protocol processing and its consequences
Authors: Feldmeier David C.
Published: October 2004

Reordering and reassembly of data before processing can reduce communication system performance as seen by the application. We examine a method of explicitly labelling blocks of data with sufficient information to allow processing of misordered data. Our labelling syntax for data blocks, which we call
chunks,
is cleaner and more general than that of other protocols. We show how chunks can be used for efficient fragmentation/reassembly and compare chunks with other fragmentation systems. End-to-end error detection is complex for chunks or other systems that allow both fragmentation and processing of misordered data. We show that it is possible to design an end-to-end error detection system that does not compromise chunk processing performance. Chunks can take advantage of processing techniques such as Integrated Layer Processing and can be used to implement concepts such as Application Layer Framing [CLAR 90].
Application of sampling methodologies to network traffic characterization
Authors: Claffy Kimberly C. , Polyzos George C. , Braun Hans-Werner
Published: October 2004

The relative performance of different data collection methods in the assessment of various traffic parameters is significant when the amount of data generated by a complete trace of a traffic interval is computationally overwhelming, and even capturing summary statistics for all traffic is impractical. This paper presents a study of the performance of various methods of sampling in answering questions related to wide area network traffic characterization. Using a packet trace from a network environment that aggregates traffic from a large number of sources, we simulate various sampling approaches, including time-driven and event-driven methods, with both random and deterministic selection patterns, at a variety of granularities. Using several metrics which indicate the similarity between two distributions, we then compare the sampled traces to the parent population. Our results revealed that the time-triggered techniques did not perform as well as the packet-triggered ones. Furthermore, the performance differences within each class (packet-based or time-based techniques) are small.
ATM scheduling with queuing delay predictions
Authors: Schwartz Daniel B.
Published: October 2004

Efficient utilization of cell switched networks supporting diverse applications will require service disciplines that are well designed for the particular quality of service constraints and traffic mix, a difficult task in view of the paucity of information about the expected traffic. We demonstrate the use of on-line dynamic programming in an adaptive cell scheduling mechanism that can easily be engineered to meet arbitrary quality of service constraints. When the objective is to minimize the total cell loss rate, our algorithm,
urgency scheduling,
compares favorably with the optimal earliest deadline first algorithm. For more complex quality of service constraints where optimal scheduling algorithms are unavailable, the simulations show urgency scheduling can provide significant increases in the usable bandwidth of a link. The learning techniques we develop are quite general and should be readily applicable to other network control problems.
The importance of non-data touching processing overheads in TCP/IP
Authors: Kay Jonathan , Pasquale Joseph
Published: October 2004

We present detailed measurements of various processing overheads of the TCP/IP and UDP/IP protocol stacks on a DECstation 5000/200 running the Ultrix 4.2a operating system. These overheads include data-touching operations, such as the checksum computation and data movement, which are well known to be major time consumers. In this study, we also considered overheads due to non-data touching operations, such as network buffer manipulation, protocol-specific processing, operating system functions, data structure manipulations (other than network buffers), and error checking. We show that when one considers realistic message size distributions, where the majority of messages are small, the cumulative time consumed by the non-data touching overheads represents the majority of processing time. We assert that it will be difficult to significantly reduce the cumulative processing time due to non-data touching overheads.
The Information Bus
Authors: Oki Brian , Pfluegl Manfred , Siegel Alex , Skeen Dale
Published: October 2004

Research can rarely be performed on large-scale, distributed systems at the level of thousands of workstations. In this paper, we describe the motivating constraints, design principles, and architecture for an extensible, distributed system operating in such an environment. The constraints include continuous operation, dynamic system evolution, and integration with extant systems. The
Information Bus
, our solution, is a novel synthesis of four design principles: core communication protocols have minimal semantics, objects are self-describing, types can be dynamically defined, and communication is anonymous. The current implementation provides both flexibility and high performance, and has been proven in several commercial environments, including integrated circuit fabrication plants and brokerage/trading floors.
Using threads in interactive systems
Authors: Hauser Carl , Jacobi Christian , Theimer Marvin , Welch Brent , Weiser Mark
Published: October 2004

We describe the results of examining two large research and commercial systems for the ways that they use threads. We used three methods: analysis of macroscopic thread statistics, analysis the microsecond spacing between thread events, and reading the implementation code. We identify ten different paradigms of thread usage:
defer work, general pumps, slack processes, sleepers, one-shots, deadlock avoidance, rejuvenation, serializers, encapsulated fork and exploiting parallelism
. While some, like
defer work
, are well known, others have not been previously described. Most of the paradigms cause few problems for programmers and help keep the resulting system implementation understandable. The
slack process
paradigm is both particularly effective in improving system performance and particularly difficult to make work well. We observe that thread priorities are difficult to use and may interfere in unanticipated ways with other thread primitives and paradigms. Finally, we glean from the practices in this code several possible future research topics in the area of thread abstractions.
Protection traps and alternatives for memory management of an object-oriented language
Authors: Hosking Antony L. , Moss J. Eliot B.
Published: October 2004

Many operating systems allow user programs to specify the protection level (inaccessible, read-only, read-write) of pages in their virtual memory address space, and to handle any protection violations that may occur. Such page-protection techniques have been exploited by several user-level algorithms for applications including generational garbage collection and persistent stores. Unfortunately, modern hardware has made efficient handling of page protection faults more difficult. Moreover, page-sized granularity may not match the natural granularity of a given application. In light of these problems, we reevaluate the usefulness of page-protection primitives in such applications, by comparing the performance of implementations that make use of the primitives with others that do not. Our results show that for certain applications software solutions outperform solutions that rely on page-protection or other related virtual memory primitives.
Performance assertion checking
Authors: Perl Sharon E. , Weihl William E.
Published: October 2004

Performance assertion checking
is an approach to automating the testing of performance properties of complex systems. System designers write assertions that capture expectations for performance; these assertions are checked automatically against monitoring data to detect potential performance bugs. Automatically checking expectations allows a designer to test a wide range of performance properties as a system evolves: data that meets expectations can be discarded automatically, focusing attention on data indicating potential problems.
PSpec
is a language for writing performance as sertions together with tools for testing assertions and estimating values for constants in assertions. The language is small and efficiently checkable, yet capable of expressing a wide variety of performance properties. Initial experience indicates that PSpec is a useful tool for performance testing and debugging; it helped uncover several performance bugs in the runtime system of a parallel programming language.
Protocol service decomposition for high-performance networking
Authors: Maeda Chris , Bershad Brian N.
Published: October 2004

In this paper we describe a new approach to implementing network protocols that enables them to have high performance and high flexibility, while retaining complete conformity to existing application programming interfaces. The key insight behind our work is that an application's interface to the network is distinct and separable from its interface to the operating system. We have separated these interfaces for two protocol implementations, TCP/IP and UDP/IP, running on the Mach 3.0 operating system and UNIX server. Specifically, library code in the application's address space implements the network protocols and transfers data to and from the network, while an operating system server manages the heavyweight abstractions that applications use when manipulating the network through operations other than send and receive. On DECstation 5000/200 systems connected by 10Mb/sec Ethernet, this approach to protocol decomposition achieves TCP/IP throughput of 1088 KB/second, which is comparable to that of a high-quality in-kernel TCP/IP implementation, and substantially better than a server-based one. Our approach achieves small-packet UDP/IP round trip latencies of 1.23 ms, again comparable to a kernel-based implementation and more than twice as fast as a server-based one.
Host migration transparency in IP networks
Authors: Teraoka Fumio , Tokoro Mario
Published: October 2004

Increasing portability of computers will require users in the future to access the network regardless of location. Host migration transparency will be an essential feature of wide area network environments. We proposed the concept of
virtual network
and the
propagating cache method
to achieve host migration transparency [12]. We also established the feasibility of Virtual Internet Protocol (VIP), derived from Internet Protocol (IP), as an example of a virtual network protocol. In this paper, we define VIP in detail and describe how VIP achieves host migration transparency in IP networks. We also show two VIP implementation approaches: 1) VIP as a sublayer; and 2) VIP as an IP option. By modifying an operating systems kernel in each case, we implement VIP using both approaches. We then compare both implementations in terms of overhead, backward compatibility, and other metrics. The measured performance indicates that VIP can provide host migration transparency in IP networks with negligible overhead.
Estimation of the optimal performance of ASN.1/BER transfer syntax
Authors: Lin Huai-An (Paul)
Published: October 2004

Many networked applications intend to use the OSI syntax language ASN.1 (Abstract Syntax Notation One) and the associated encoding standard BER (Basic Encoding Rules) to achieve interoperability. However, the processing efficiency of BER has been a serious concern. The BER data conversion function has been viewed as the dominant communication cost, with a processing overhead many times greater than that of the other protocol-related functions combined. This paper demonstrates that if engineered to operate under certain favorable but realistic conditions, the BER conversion function runs much faster than what has been previously reported. In fact, a throughput comparable to a TCP/IP/ATM package (20 Mb/s) has been achieved in experiments. This result implies that ASN.1/BER as a solution to interoperability is more viable than previously thought.
How hard are
n
2
-hard problems?
Authors: Bloch Stephen A. , Buss Jonathan F. , Goldsmith Judy
Published: October 2004

Many of the "
n
2
-hard" problems described by Gajentaan and Overmars can be solved using limited nondeterminism or other sharply-bounded quantifiers. Thus we suggest that problems are not among the hardest problems solvable in quadratic time
Extensible access control for a hierarchy of servers
Authors: Bacon Jean , Hayton Richard , Lo Sai Lai , Moody Ken
Published: October 2004

We discuss the protection requirements of a distributed storage service comprising a two-level hierarchy of storage servers with value-adding service layers above them. A flexible and extensible access control mechanism is required. Our scheme uses Access Control Lists (ACLs) to allow fine grained expression of policy together with capabilities for efficient runtime access after a once-off ACL check. Our capabilities are principal- specific and transient and their design ensures that access to objects is via the correct service hierarchy; for example, a directory object may only be manipulated via a directory service. The implementation of this protection is stateless at the servers above the storage service. The scheme also provides a convenient means to delegate rights for an object, temporarily, to an unprivileged server, for example a print-server. The fact that our capabilities are short-lived alleviates the requirement for selective revocation and crash recovery.