bluuebunny/crossref_metadata_2025 huggingface dataset:
Modeling and simulation of self-similar variable bit rate compressed video
Authors: Huang Changcheng , Devetsikiotis Michael , Lambadaris Ioannis , Kaye A. Roger
Published: October 2004

Variable bit rate (VBR) compressed video is expected to become one of the major loading factors in high-speed packet networks such as ATM-based B-ISDN. However, recent measurements based on long empirical traces (complete movies) revealed that VBR video traffic possesses
self-similar
(or
fractal
) characteristics, meaning that the dependence in the traffic stream lasts much longer than traditional models can capture.In this paper, we present a unified approach which, in addition to accurately modeling the marginal distribution of empirical video records, also models directly
both
the short and the long-term empirical autocorrelation structures. We also present simulation results using synthetic data and compare with results based on empirical video traces.Furthermore, we extend the application of efficient estimation techniques based on
importance sampling
that we had used before only for simple fractal processes. We use importance sampling techniques to efficiently estimate low probabilities of packet losses that occur when a multiplexer is fed with synthetic traffic from our self-similar VBR video model.
Efficient fair queueing using deficit round robin
Authors: Shreedhar M. , Varghese George
Published: October 2004

Fair queuing is a technique that allows each flow passing through a network device to have a fair share of network resources. Previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement: specifically, the work required to process a packet in these schemes was
O
(
log
(
n
)), where
n
is the number of active flows. This is expensive at high speeds. On the other hand, cheaper approximations of fair queuing that have been reported in the literature exhibit unfair behavior. In this paper, we describe a new approximation of fair queuing, that we call
Deficit Round Robin
. Our scheme achieves nearly perfect fairness in terms of throughput, requires only
O
(1) work to process a packet, and is simple enough to implement in hardware. Deficit Round Robin is also applicable to other scheduling problems where servicing cannot be broken up into smaller units, and to distributed queues.
A mobile user location update and paging mechanism under delay constraints
Authors: Akyildiz Ian F. , Ho Joseph S. M.
Published: October 2004

A mobile user location management mechanism is introduced that incorporates a distance based location update scheme and a paging mechanism that satisfies predefined delay requirements. An analytical model is developed which captures the mobility and call arrival pattern of a terminal. Given the respective costs for location update and terminal paging, the average total location update and terminal paging cost is determined. An iterative algorithm is then used to determine the optimal location update threshold distance that results in the minimum cost. Analytical results are also obtained to demonstrate the relative cost incurred by the proposed mechanism under various delay requirements.
Locating nearby copies of replicated Internet servers
Authors: Guyton James D. , Schwartz Michael F.
Published: October 2004

In this paper we consider the problem of choosing among a collection of replicated servers, focusing on the question of how to make choices that segregate client/server traffic according to network topology. We explore the cost and effectiveness of a variety of approaches, ranging from those requiring routing layer support (e.g., anycast) to those that build location databases using application-level probe tools like traceroute. We uncover a number of tradeoffs between effectiveness, network cost, ease of deployment, and portability across different types of networks. We performed our experiments using a simulation parameterized by a topology collected from 7 survey sites across the United States, exploring a global collection of Network Time Protocol servers.
Sharing the “cost” of multicast trees
Authors: Herzog Shai , Shenker Scott , Estrin Deborah
Published: October 2004

Given the need to provide users with reasonable feedback about the "costs" their network usage incurs, and the increasingly commercial nature of the Internet, we believe that the allocation of cost among users will play an important role in future networks. This paper discusses cost allocation in the context of multicast flows. The question we discuss is this: when a single data flow is shared among many receivers, how does one split the cost of that flow among the receivers? Multicast routing increases network efficiency by using a single shared delivery tree. We address the issue of how these savings are allocated among the various members of the multicast group. We first consider an axiomatic approach to the problem, analyzing the implications of different distributive notions on the resulting allocations. We then consider a one-pass mechanism to implement such allocation schemes and investigate the family of allocation schemes such mechanisms can support.
A reliable multicast framework for light-weight sessions and application level framing
Authors: Floyd Sally , Jacobson Van , McCanne Steve , Liu Ching-Gung , Zhang Lixia
Published: October 2004

This paper describes SRM (Scalable Reliable Multicast), a reliable multicast framework for application level framing and light-weight sessions. The algorithms of this framework are efficient, robust, and scale well to both very large networks and very large sessions. The framework has been prototyped in wb, a distributed whiteboard application, and has been extensively tested on a global scale with sessions ranging from a few to more than 1000 participants. The paper describes the principles that have guided our design, including the IP multicast group delivery model, an end-to-end, receiver-based model of reliability, and the application level framing protocol model. As with unicast communications, the performance of a reliable multicast delivery algorithm depends on the underlying topology and operational environment. We investigate that dependence via analysis and simulation, and demonstrate an adaptive algorithm that uses the results of previous loss recovery events to adapt the control parameters used for future loss recovery. With the adaptive algorithm, our reliable multicast delivery algorithm provides good performance over a wide range of underlying topologies.
Guarded page tables on Mips R4600 or an exercise in architecture-dependent micro optimization
Authors: Liedtke Jochen , Elphinstone Kevin
Published: October 2004

Guarded Page Tables implement huge sparsely occupied address spaces efficiently and have the advantages of multi-level tables (tree structure, hierarchy, sharing). We present an implementation guarded page tables on the R4600 processor. The paper describes both the architecture-dependent design process of the algorithms and the resulting tool box.
A display and analysis tool for process-resource graphs
Authors: Samadzadeh M. H. , Koshy B. S.
Published: October 2004

This paper describes the design and implementation of a graphical tool called Prograph which enables users to model and analyze operating systems process-resource graphs. The Prograph program enables users to model operating system Process-Resource graphs rapidly, analyze the graphs, and then view the different stages of the deadlock analysis. The deadlock representation and analysis tool Prograph was prototypically evaluated by the students in the graduate level Operating Systems class as well as a number of graduate students at the Computer Science Department of Oklahoma State University. The feedback obtained from the users of the Prograph program indicated that it was functional and useful for modeling and analyzing Process-Resource graphs.
Exploring issues of operating systems structuring
Authors: Cheung W. H. , Loong Anthony H. S.
Published: October 2004

The microkernel concept has once been the most advocated approach for operating system development. Unfortunately, before its publicized advantages have been fully realized in an operating system implementation, current operating system researchers claim its weaknesses and make their ways to develop "extensible" operating systems. New operating systems like SPIN, Ageis, Cache Kernel, Apertos and Scout, employ new concepts to support application specific customization and optimal allocation of system resource, in order to boost up the performance of certain applications. The microkernel concept in itself never contradicts with this purpose, as it is to provide basic efficient primitives for construction of system services. Probably, the crucial problem is that the OS architecture of most current microkernel implementations cannot suitably meet with the new requirements of extensibility. In this paper, we try to explore issues in developing a better OS architecture that can fully enhance OS extensibility. Moreover, we investigate how microkernel abstraction can be remodeled to support better reconfiguration in operating systems. To cope with the conflicting issues of efficiency, flexibility and ease of reconfiguration, we suggest and discuss an approach of structuring operating systems. The approach is characteristed by lightweight meta-abstraction mechanism and progressive reflective reconfiguration.
A pragmatic Ada software design/development methodology
Authors: Pullan Wayne
Published: October 2004

A pragmatic design method is described which has been successfully applied to two medium size Ada projects. This design method parallels (albeit at a much less sophisticated level) the domain oriented methodologies currently becoming popular with the advent of products such as Microsoft Visual Basic (TM).
Integrating rate monotonic analysis into the preliminary Ada design process
Authors: Cronin Kevin J.
Published: October 2004

High quality software is easier to understand, maintain and reuse. The quality of real-time systems is often measured in how well they meet their critical timing requirements as well as their computational requirements. Management and practitioners need to know early on in the development process if what they are designing will meet its critical timing requirements. The Rate Monotonic Analysis (RMA) theory and guidelines for its usage in Ada designs are reviewed. This paper proposes extending this work to include the integration of RMA as a design metric when evaluating the timing correctness of preliminary Ada programs.
A short note on Shor's factoring algorithm
Authors: Buhrman Harry
Published: October 2004

This note shows that Shor's algorithm for factoring in polynomial time on a quantum computer can be made to work with zero error probability.
Scheduling PVM tasks
Authors: Ju Jiubin , Wang Yong
Published: October 2004

This paper describes a PVM task scheduler designed and implemented by the authors. The scheduler supports selecting idle workstations, scheduling pool tasks and dynamically produced subtasks. It can improve resource utilization, reduce job response time and simplize programming.
Distributed mutual exclusion on hypercubes
Authors: Naimi Mohamed
Published: October 2004

Hypercube have been commercially available in the past few years to their high degree of connectivity, symmetry, and low degree of diameter. In this paper, we analyse the performance in number of messages on d-dimensional hypercube, for two groups of distributed algorithms for mutual exclusion, a permission-based mutual exclusion group, and a token-based mutual exclusion group.In the permission-based mutual exclusion algorithm, a node enters in the critical section only after receiving permission from all others nodes, this algorithm requires d2
d
messages.In the token-based mutual exclusion algorithm, a node is allowed to access its critical section if and only if it holds the token. In this algorithm, there is a node, called root, which knows the last node to get the token among the current requesting nodes. When a node wants to enter critical section, it sends request message to the root, which in turn informs the last node that new node will get the token next, and updates its last node. As result, the requesting nodes form a distributed queue, each of which records only the element next to it, this algorithm requires 2d messages in the worst case.
What's new for scanning with Ada-95?
Authors: Gauthier Michel
Published: October 2004

This paper illustrates how some new Ada-95 features improve the versatility of scanning techniques. It will recall the definition of a scan, how scanning can be implemented in Ada-83, and what problems are associated with scans, notably in passing them as (generic) parameters. After that, we will discuss accesses to subprograms and show that they cannot become a worthwhile solution, and finally show an unexpected solution with tagged types used as a factorisation of properties rather than as an implementation of inheritance mechanisms.From some low-level point of view, both generic and file-like scannings can look like theoretical fashions that have no interest. The real question beyond such scannings is whether we accept the application of these programming principles that have emerged from decades of programming professional practice, such as weak coupling, abstraction and encapsulation. We argue that it is essential to study in depth all the consequences of these programming principles before assessing their interest in real life. We conjecture that encapsulated scans could be of enough interest to be much more widely used in industrial projects.Aside from industrial usages, scanning is a valid illustration of both tagged types and genericity, and we provided some suggested exercises for lecturers who would emphasize factorization of type properties and nested genericity or package parameters.
Pricing in computer networks
Authors: Shenker S. , Clark D. , Estrin D. , Herzog S.
Published: October 2004

As the Internet makes the transition from research testbed to commercial enterprise, the topic of pricing in computer networks has suddenly attracted great attention. Much of the discussion in the network design community and the popular press centers on the usage-based
vs.
flat pricing debate. The more academic literature has largely focused on devising optimal pricing policies; achieving optimal welfare requires charging marginal congestion costs for usage. In this paper we critique this
optimality
paradigm on three grounds: (1) marginal cost prices may not produce sufficient revenue to fully recover costs and so are perhaps of limited relevance, (2) congestion costs are inherently inaccessible to the network and so cannot reliably form the basis for pricing, and (3) there are other, more structural, goals besides optimality, and some of these goals are incompatible with the global uniformity required for optimal pricing schemes. For these reasons, we contend that the research agenda on pricing in computer network should shift away from the optimality paradigm and focus more on structural and architectural issues. Such issues include allowing local control of pricing policies, fostering interconnection, handling multicast appropriately, and allowing receivers to pay for transmission. To illustrate our point, we describe how these goals might be accomplished in the context of a different pricing paradigm:
edge
pricing. In addition, we argue that in the context of this edge pricing paradigm, usage-based pricing and flat pricing are not radically different but instead both reside along the single continuum of
usage-constraining
pricing policies.
Factors influencing electronic data interchange success
Authors: Farhoomand Ali F. , Drury Don H.
Published: October 2004

With the rapid proliferation of electronic data interchange (EDI) in recent years, there has been a growing need for understanding various issues surrounding the adoption, implementation, and evaluation of such systems. In particular, as an increasing number of firms are piloting, implementing, or using EDI, it is becoming crucial to identify the factors that influence the success of EDI. Through a survey of 242 companies that were at different stages of adopting EDI, we show that EDI success is affected by four distinct factors relating to information quality, systems outcomes, user participation, and system quality. Evidence of reliability and validity of the scale, along with some practical standards and evaluation baseline, are provided.
An empirical comparison of a hypertext-based systems analysis case with conventional cases and role playing
Authors: Kendall Julie E. , Kendall Kenneth E. , Baskerville Richard L. , Barnes Raymond J.
Published: October 2004

Systems analysis and design is a practical discipline, difficult to teach realistically with conventional methods. HyperCase is an interactive program that presents an organization called Maple Ridge Engineering in a highly graphical environment for use on a microcomputer. Use of hypertext allows students to navigate through the organization, doing interviews, and examining diagrams in the order they prefer, rather than in the prescribed, linear fashion found in conventional cases.The effectiveness of HyperCase versus conventional cases and role playing in helping students reach six different levels of educational objectives was assessed in an experiment with 22 students. Those using HyperCase performed as well or better on the examination questions than those using standard approaches. In the second part of the study, results from an affective student questionnaire completed by the original 22 students, plus 97 others, revealed that they were overwhelmingly positive in their reaction to this new approach. Little difference in the reactions among experienced and inexperienced computer users was found. Based on our empirical findings, we conclude that students felt their experience with HyperCase was an important departure from the traditional systems analysis and design class.
Limited nondeterminism
Authors: Goldsmith Judy , Levy Matthew A. , Mundhenk Martin
Published: October 2004

Yes, the lucky 13th column is here, and it is a guest column written by J. Goldsmith, M. Levy, and M. Mundhenk on the topic of limited nondeterminism---classes and hierarchies derived when nondeterminism itself is viewed as a quantifiable resource (as it indeed is!).Coming up in the Complexity Theory Column in the very special 100th issue of
SIGACT News
: A forum on the future of complexity theory. Many of the field's leading lights share their exciting insights on what lies ahead, so please be there in three!
Analysis of steady-state segment storage utilizations in a log-structured file system with least-utilized segment cleaning
Authors: Robinson John T.
Published: October 2004

The steady-state distribution of storage utilizations of segments in a log-structured file system with least-utilized (greedy) segment cleaning is found using analytic methods. Furthermore, it is shown that as the number of segments increases, this distribution approaches a limiting continuous distribution, which is also derived. These results could be useful for preliminary performance analysis of LFS-type system designs prior to the development of detailed simulation models or actual implementation.
M-UDP
Authors: Brown Kevin , Singh Suresh
Published: October 2004

In this paper we present our implementation of a modified UDP protocol appropriate for the mobile networking environment. Our protocol, like UDP, does not guarantee reliable delivery of datagrams. However, unlike UDP, it does ensure that the number of lost datagrams is kept small. In this paper we discuss our implementation of M-UDP (in NetBSD) and compare its performance against that of UDP in an experimental mobile network that is currently under development at the University of South Carolina.
Teaching teamwork
Authors: Fellers Jack W.
Published: October 2004

The business world continues to change at a tremendous rate. We in the information systems field contribute to this rate of change and at the same time try to keep up with it. While the content in our field changes constantly, the way in which we attempt to educate our students (pedagogy) has not changed for some time. One way to change how we teach our students is through the use of alternative pedagogical models, such as the cooperative learning model. Cooperative learning is defined as "… the instructional use of small groups so that students work together to maximize their own and each other's learning" (Johnson, Johnson, and Smith 1991a; p. 3). This paper presents an overview of the cooperative learning model, two examples of the model in use, and an exploratory assessment of the model. Additionally, limitations of this study, and recommendations for future research and for practice are provided.
An assessment of structure and causation of IS usage
Authors: Hendrickson Anthony R. , Collins Michael R.
Published: October 2004

Factors contributing to information system (IS) usage are of interest to both academicians and practitioners alike. Previous research has shown that perceived usefulness and perceived ease of use are two dominant factors affecting an individual's intention to use a system. Different models of the causal relationships between perceived usefulness, perceived ease of use, and system usage have been investigated in the literature (Adams, Nelson, and Todd, 1992). Contributing to this body of knowledge, this paper reports on the analysis of three competing models of Davis's constructs: perceived ease of use, perceived usefulness, and intention to use. The results indicate Davis is correct in proposing that the indirect relationship between perceived ease of use and intention to use, mediated by perceived usefulness, is an important one. In addition, the direct relationship between perceived ease of use and intention to use, is also significant. The study's findings indicate the full Davis model with all causal paths is superior to alternative nested models tested.
Efficient and timely mutual authentication
Authors: Otway Dave , Rees Owen
Published: October 2004

This paper describes a protocol for efficient mutual authentication (via a mutually trusted third party) that assures both principal parties of the timeliness of the interaction without the use of clocks or double encipherment. The protocol requires a total of only four messages to be exchanged between the three parties concerned.
Launching a successful CPME program in a multi-vendor environment
Authors: Ruckert Rogert G , Dean John D
Published: October 2004

Establishing a modest CPME (Computer Performance, Management, and Evaluation) program is often regarded as being a difficult and expensive project. This image is compounded when a multi-vendor environment exists. This article describes how to establish a CPME program in such an environment without committing substantial resources to it. It details how such a program was constructed and implemented at Medtronic, Inc.
Support for heterogeneity in the global distributed operating system
Authors: Turnbull Martin
Published: October 2004

Heterogeneity in distributed systems is potentially the major restricting factor to effective resource utilisation. In the global distributed operating system, where resource sharing crosses many organisational boundaries on a world-wide scale, this problem is increased. The approach to solving the heterogeneity problem is to provide a simple, coherent and consistent base on which to build services. The global distributed operating system provides support for remote heterogeneous service access. Supporting existing services is an important aspect that is aimed at minimising the changeover effort and cost from the old operating system to the new global distributed operating system.
Some observations on the performance of a 56 Kbit internet link
Authors: Farber D , Cassel L
Published: October 2004

A 56 Kb gateway between two Ethernets was installed and subjected to heavy traffic loads. While large file transfers were being done between the networks, less demanding internetwork commands were issued and the response time measured. The effect of the heavy network load on the smaller tasks is presented in this report. It appears that the smaller tasks are unfairly penalized for the network load caused by the larger tasks. If so, this could be a problem for the design and use of the backbone network of the NSFnet. No conclusions are drawn concerning the applicability of these results in a general case. The data is presented for consideration by those who are planning to rely on such links and have some knowledge of the level of traffic that can be expected in their own environment.
Using large families for handling priority requests
Authors: Burns A
Published: October 2004

With ordinary task entries, requests are handled strictly in the order in which they arrive at the called task. To circumvent this rule, for prioritised requests, the Ada language provides entry families. Unfortunately the programming of a reliable algorithm for a large number of priority levels is non-trivial. This paper reviews the "solutions" usually given and derives an acceptable, if somewhat complex, algorithm. Suggestions for improvements in the facilities Ada provides are also presented.
Implementation of a prototype CAIS environment
Authors: Carr P , Stevenson R , Alea J , Berthold J , Croucher G
Published: October 2004

This paper describes a project to investigate the feasibility, performance and utility o f a CAIS compliant Ada Programming Support Environment. A working model of an environment was built, with a command language interpreter and a small toolset. Tools from the host environment have been imported and made to behave as native CAIS tools. A number of tools have been ported from a parallel effort by a MITRE corporation team with little difficulty. The prototype was built initially for correctness and enhanced later for performance improvements. The performance was found to be acceptable as a test bed for development of prototype tools and offered hope for the performance of a product-quality implementation. A test suite for compliance with the standard was partially implemented.
Interfacing Ada and relational databases
Authors: McCoy L S
Published: October 2004

With the advent of the Ada* language, relational database manufacturers are faced with the task of interfacing their databases to a language based on the object-oriented model. This paper discusses the benefits gained from interfacing Ada to a relational DBMS, with ORACLE* Pro*Ada used as a concrete example. Two approaches to interfacing Ada and a DBMS are discussed: one which was based on the alpha testing the author performed on Pro*Ada, and one based on retrieving rows in a record format. The paper concludes with a discussion of the Government request for an SQL to Ada interface, as well as general issues for DBMS interfaces.
Ada-embedded SQL: the options
Authors: Donaho J E D , Davis G K
Published: October 2004

This paper investigates the possibilities for incorporating relational database queries into an Ada application program. The research was done from a language features viewpoint, and only concerned itself with the broadest of implementation issues.Three alternative approaches are investigated. The first tries to express database definitions and queries in pure Ada source code. The second attempts to write Ada code that looks and functions just like SQL. The third approach embeds a distinct query language within an Ada application program.The most feasible approach is found to be that of an embedded query language, in conjunction with pre-processing of the integrated Ada-language/query-language program. The paper then goes on to describe a number of modifications and enhancements to the SQL model which would provide an acceptable Ada-compatible query language.
Evaluation of the VAX
TM
Ada:2E compiler and APSE by means of a real program
Authors: Frigo G V
Published: October 2004

This paper describes the design, implementation and check up of a non-trivial Ada® program involving tasking and generic packages in the context of an evaluation of the VAX Ada compiler and Ada Programming System Environment. The exercise took place at the end of 1985 at the European Laboratory for Particle Physics (CERN).
An environment for Ada software development based on formal specification
Authors: Luckham D C , Neff R , Rosenblum D S
Published: October 2004

This report gives an overview of the current status and plans to construct a prototype environment of advanced tools for software and hardware development based on the use of wide-spectrum languages. The wide-spectrum languages include Anna (ANNotated Ada), and TSL (Task Sequencing Language). The tools described here provide interactive aid at all stages in the system development process. Special emphasis is placed on distributed computing, both in providing tools for handling parallelism in the subject system, and in designing tools that utilize parallelism in the programming environment. Applications of these tools include requirements analysis, formal specification, rapid prototyping, testing, formal verfication and construction of self-testing Ada software for multi-processor systems.The report describes an existing environment of prototype tools supporting applications of Anna and TSL to formal specification and testing of Ada software. The new environment tools will be based on component tools already developed at Stanford and proven to be portable to various Ada environments. All tools are implemented in Ada and are intended to interface with standard components of Ada programming environments.
Quantum cryptography
Authors: Wiedemann D
Published: October 2004

An idea of Stephen Wiesner [1] is expanded to give a method of public key distribution which is provably secure under the principles of quantum mechanics. It appears that this scheme could actually be implemented in favorable environments.
End-to-end routing behavior in the Internet
Authors: Paxson Vern
Published: October 2004

The large-scale behavior of routing in the Internet has gone virtually without any formal study, the exception being Chinoy's analysis of the dynamics of Internet routing information [Ch93]. We report on an analysis of 40,000 end-to-end route measurements conducted using repeated "traceroutes" between 37 Internet sites. We analyze the routing behavior for pathological conditions, routing stability, and routing symmetry. For pathologies, we characterize the prevalence of routing loops, erroneous routing, infrastructure failures, and temporary outages. We find that the likelihood of encountering a major routing pathology more than doubled between the end of 1994 and the end of 1995, rising from 1.5% to 3.4%. For routing stability, we define two separate types of stability, "prevalence" meaning the overall likelihood that a particular route is encountered, and "persistence," the likelihood that a route remains unchanged over a long period of time. We find that Internet paths are heavily dominated by a single prevalent route, but that the time periods over which routes persist show wide variation, ranging from seconds up to days. About 2/3's of the Internet paths had routes persisting for either days or weeks. For routing symmetry, we look at the likelihood that a path through the Internet visits at least one different city in the two directions. At the end of 1995, this was the case half the time, and at least one different autonomous system was visited 30% of the time.
DPF
Authors: Engler Dawson R. , Kaashoek M. Frans
Published: October 2004

Fast and flexible message demultiplexing are well-established goals in the networking community [1, 18, 22]. Currently, however, network architects have had to sacrifice one for the other. We present a new packet-filter system, DPF (Dynamic Packet Filters), that provides both the traditional flexibility of packet filters [18] and the speed of hand-crafted demultiplexing routines [3]. DPF filters run 10-50 times faster than the fastest packet filters reported in the literature [1, 17, 18, 27]. DPF's performance is either equivalent to or, when it can exploit runtime information, superior to hand-coded demultiplexors. DPF achieves high performance by using a carefully-designed declarative packet-filter language that is aggressively optimized using dynamic code generation. The contributions of this work are: (1) a detailed description of the DPF design, (2) discussion of the use of dynamic code generation and quantitative results on its performance impact, (3) quantitative results on how DPF is used in the Aegis kernel to export network devices safely and securely to user space so that UDP and TCP can be implemented efficiently as user-level libraries, and (4) the unrestricted release of DPF into the public domain.
Analysis of techniques to improve protocol processing latency
Authors: Mosberger David , Peterson Larry L. , Bridges Patrick G. , O'Malley Sean
Published: October 2004

This paper describes several techniques designed to improve protocol latency, and reports on their effectiveness when measured on a modern RISC machine employing the DEC Alpha processor. We found that the memory system---which has long been known to dominate network throughput---is also a key factor in protocol latency. As a result, improving instruction cache effectiveness can greatly reduce protocol processing overheads. An important metric in this context is the
memory cycles per instructions
(mCPI), which is the average number of cycles that an instruction stalls waiting for a memory access to complete. The techniques presented in this paper reduce the mCPI by a factor of 1.35 to 5.8. In analyzing the effectiveness of the techniques, we also present a detailed study of the protocol processing behavior of two protocol stacks---TCP/IP and RPC---on a modern RISC processor.
Speeding up protocols for small messages
Authors: Blackwell Trevor
Published: October 2004

Many techniques have been discovered to improve performance of bulk data transfer protocols which use large messages. This paper describes a technique that improves protocol performance for protocols that use small messages, such as signalling protocols, by reducing memory system penalties. Detailed measurements show that for TCP, most memory system costs are due to poor locality in the protocol code itself, rather than movement of data. We present a new technique, analogous to blocked matrix multiplication, for scheduling layer processing to reduce memory system costs, and analyze its performance in a synthetic environment.
Masking the overhead of protocol layering
Authors: van Renesse Robbert
Published: October 2004

Protocol layering has been advocated as a way of dealing with the complexity of computer communication. It has also been criticized for its performance overhead. In this paper, we present some insights in the design of protocols, and how these insights can be used to mask the overhead of layering, in a way similar to client caching in a file system. With our techniques, we achieve an order of magnitude improvement in end-to-end message latency in the Horus communication framework. Over an ATM network, we are able to do a round-trip message exchange, of varying levels of semantics, in about 170 µseconds, using a protocol stack of four layers that were written in ML, a high-level functional language.
Efficient support of delay and rate guarantees in an internet
Authors: Georgiadis L. , Guérin R. , Peris V. , Rajan R.
Published: October 2004

In this paper, we investigate some issues related to the efficient provision of end-to-end delay guarantees in the context of the Guaranteed (G) Services framework [16]. First, we consider the impact of reshaping traffic within the network on the end-to-end delay, the end-to-end jitter, as well as per-hop buffer requirements. This leads us to examine a class of traffic disciplines that use reshaping at each hop, namely rate-controlled disciplines. In this case, it is known that it is advantageous to use the Earliest Deadline First (EDF) scheduling policy at the link scheduler [8]. For this service discipline, we determine the appropriate values of the parameters that have to be exported, as specified in [16]. Subsequently, with the help of an example, we illustrate how the G service traffic will typically underutilize the network, regardless of the scheduling policy used. We then define a Guaranteed Rate (GR) service, that is synergetic with the G service framework and makes use of this unutilized bandwidth to provide rate guarantees to flows. We outline some of the details of the GR service and explain how it can be supported in conjunction with the G service in an efficient manner.
Receiver-driven layered multicast
Authors: McCanne Steven , Jacobson Van , Vetterli Martin
Published: October 2004

State of the art, real-time, rate-adaptive, multimedia applications adjust their transmission rate to match the available network capacity. Unfortunately, this source-based rate-adaptation performs poorly in a heterogeneous multicast environment because there is no single target rate --- the conflicting bandwidth requirements of all receivers cannot be simultaneously satisfied with one transmission rate. If the burden of rate-adaption is moved from the source to the receivers, heterogeneity is accommodated. One approach to receiver-driven adaptation is to combine a layered source coding algorithm with a layered transmission system. By selectively forwarding subsets of layers at constrained network links, each user receives the best quality signal that the network can deliver. We and others have proposed that selective-forwarding be carried out using multiple IP-Multicast groups where each receiver specifies its level of subscription by joining a subset of the groups. In this paper, we extend the multiple group framework with a rate-adaptation protocol called Receiver-driven Layered Multicast, or RLM. Under RLM, multicast receivers adapt to both the static heterogeneity of link bandwidths as well as dynamic variations in network capacity (i.e., congestion). We describe the RLM protocol and evaluate its performance with a preliminary simulation study that characterizes user-perceived quality by assessing loss rates over multiple time scales. For the configurations we simulated, RLM results in good throughput with transient short-term loss rates on the order of a few percent and long-term loss rates on the order of one percent. Finally, we discuss our implementation of a software-based Internet video codec and its integration with RLM.
Measurement and analysis of the error characteristics of an in-building wireless network
Authors: Eckhardt David , Steenkiste Peter
Published: October 2004

There is general belief that networks based on wireless technologies have much higher error rates than those based on more traditional technologies such as optical fiber, coaxial cable, or twisted pair wiring. This difference has motivated research on new protocol suites specifically for wireless networks. While the error characteristics of wired networks have been well documented, less experimental data is available for wireless LANs.In this paper we report the results of a study characterizing the error environment provided by AT&T WaveLAN, a commercial product designed for constructing 2 Mb/s in-building wireless networks. We evaluated the effects of interfering radiation sources, and of attenuation due to distance and obstacles, on the packet loss rate and bit error rate. We found that under many conditions the error rate of this physical layer is comparable to that of wired links. We analyze the implications of our results on today's CSMA/CA based wireless LANs and on future pico-cellular shared-medium reservation-based wireless networks.
Forward acknowledgement
Authors: Mathis Matthew , Mahdavi Jamshid
Published: October 2004

We have developed a Forward Acknowledgment (FACK) congestion control algorithm which addresses many of the performance problems recently observed in the Internet. The FACK algorithm is based on first principles of congestion control and is designed to be used with the proposed TCP SACK option. By decoupling congestion control from other algorithms such as data recovery, it attains more precise control over the data flow in the network. We introduce two additional algorithms to improve the behavior in specific situations. Through simulations we compare FACK to both Reno and Reno with SACK. Finally, we consider the potential performance and impact of FACK in the Internet.
Removal policies in network caches for World-Wide Web documents
Authors: Abrams Marc , Standridge Charles R. , Abdulla Ghaleb , Fox Edward A. , Williams Stephen
Published: October 2004

World-Wide Web proxy servers that cache documents can potentially reduce three quantities: the number of requests that reach popular servers, the volume of network traffic resulting from document requests, and the latency that an end-user experiences in retrieving a document. This paper examines the first two using the measures of cache hit rate and weighted hit rate (or fraction of client-requested bytes returned by the proxy). A client request for an uncached document may cause the removal of one or more cached documents. Variable document sizes and types allow a rich variety of policies to select a document for removal, in contrast to policies for CPU caches or demand paging, that manage homogeneous objects. We present a taxonomy of removal policies. Through trace-driven simulation, we determine the maximum possible hit rate and weighted hit rate that a cache could ever achieve, and the removal policy that maximizes hit rate and weighted hit rate. The experiments use five traces of 37 to 185 days of client URL requests. Surprisingly, the criteria used by several proxy-server removal policies (LRU, Hyper-G, and a proposal by Pitkow and Recker) are among the worst performing criteria in our simulation; instead, replacing documents based on size maximizes hit rate in each of the studied workloads.
The case for a single-chip multiprocessor
Authors: Olukotun Kunle , Nayfeh Basem A. , Hammond Lance , Wilson Ken , Chang Kunyung
Published: October 2004

Advances in IC processing allow for more microprocessor design options. The increasing gate density and cost of wires in advanced integrated circuit technologies require that we look for new ways to use their capabilities effectively. This paper shows that in advanced technologies it is possible to implement a single-chip multiprocessor in the same area as a wide issue superscalar processor. We find that for applications with little parallelism the performance of the two microarchitectures is comparable. For applications with large amounts of parallelism at both the fine and coarse grained levels, the multiprocessor microarchitecture outperforms the superscalar architecture by a significant margin. Single-chip multiprocessor architectures have the advantage in that they offer localized implementation of a high-clock rate processor for inherently sequential applications and low latency interprocessor communication for parallel applications.
An evaluation of memory consistency models for shared-memory systems with ILP processors
Authors: Pai Vijay S. , Ranganathan Parthasarathy , Adve Sarita V. , Harton Tracy
Published: October 2004

Relaxed consistency models have been shown to significantly outperform sequential consistency for single-issue, statically scheduled processors with blocking reads. However, current microprocessors aggressively exploit instruction-level parallelism (ILP) using methods such as multiple issue, dynamic scheduling, and non-blocking reads. Researchers have conjectured that two techniques, hardware-controlled non-binding prefetching and speculative loads, have the potential to equalize the hardware performance of memory consistency models on such processors.This paper performs the first detailed quantitative comparison of several implementations of sequential consistency and release consistency optimized for aggressive ILP processors. Our results indicate that hardware prefetching and speculative loads dramatically improve the performance of sequential consistency. However, the gap between sequential consistency and release consistency depends on the cache write policy and the complexity of the cache-coherence protocol implementation. In most cases, release consistency significantly outperforms sequential consistency, but for two applications, the use of a write-back primary cache and a more complex cache-coherence protocol nearly equalizes the performance of the two models.We also observe that the existing techniques, which require on-chip hardware modifications, enhance the performance of release consistency only to a small extent. We propose two new software techniques ---
fuzzy acquires
and
selective acquires
--- to achieve more overlap than allowed by the previous implementations of release consistency. To enhance methods for overlapping acquires, we also propose a technique to eliminate control dependences caused by an acquire loop, using a small amount of off-chip hardware called the
synchronization buffer.
The Rio file cache
Authors: Chen Peter M. , Ng Wee Teck , Chandra Subhachandra , Aycock Christopher , Rajamani Gurushankar , Lowell David
Published: October 2004

One of the fundamental limits to high-performance, high-reliability file systems is memory's vulnerability to system crashes. Because memory is viewed as unsafe, systems periodically write data back to disk. The extra disk traffic lowers performance, and the delay period before data is safe lowers reliability. The goal of the Rio (RAM I/O) file cache is to make ordinary main memory safe for persistent storage by enabling memory to survive operating system crashes. Reliable memory enables a system to achieve the best of both worlds: reliability equivalent to a write-through file cache, where every write is instantly safe, and performance equivalent to a pure write-back cache, with no reliability-induced writes to disk. To achieve reliability, we protect memory during a crash and restore it during a reboot (a "warm" reboot). Extensive crash tests show that even without protection, warm reboot enables memory to achieve reliability close to that of a write-through file system. Adding protection makes memory even
safer
than a write-through file system while adding essentially no overhead. By eliminating reliability-induced disk writes, Rio performs 4-22 times as fast as a write-through file system, 2-14 times as fast as a standard Unix file system, and 1-3 times as fast as an optimized system that risks losing 30 seconds of data and metadata.
Multiple-block ahead branch predictors
Authors: Seznec André , Jourdan Stéphan , Sainrat Pascal , Michaud Pierre
Published: October 2004

A basic rule in computer architecture is that a processor cannot execute an application faster than it fetches its instructions. This paper presents a novel cost-effective mechanism called the two-block ahead branch predictor. Information from the current instruction block is not used for predicting the address of the next instruction block, but rather for predicting the block following the next instruction block.This approach overcomes the instruction fetch bottle-neck exhibited by wide-dispatch "brainiac" processors by enabling them to efficiently predict addresses of two instruction blocks in a single cycle. Furthermore, pipelining the branch prediction process can also be done by means of our predictor for "speed demon" processors to achieve higher clock rate or to improve the prediction accuracy by means of bigger prediction structures.Moreover, and unlike the previously-proposed multiple predictor schemes, multiple-block ahead branch predictors can use any of the branch prediction schemes to perform the very accurate predictions required to achieve high-performance on superscalar processors.