One of the pioneering efforts to obtain guaranteed performance from the Internet was born out of sheer curiosity. The question "Can it be done, and, if so, how?" came unexpectedly to the mind of a researcher who had never been active in the field of networking, and kept tormenting him until it became a personal challenge. Also due to many other researchers (with a lot more networking credentials), the topic was for several years quite a popular one in the community, and various protocols were designed, some even implemented, to incarnate some of the results of research. Will any of those protocols ever be deployed on the Internet? Only the future will tell.

In this paper we present a prototype implementation of a management scheme that can be used to dynamically manage Guaranteed Performance Connection (GPC) services in Integrated Services Networks. These services are required to support the wide range of quality-of-service parameters desired by many useful applications. The GPC services provide performance guarantees in terms of throughput, delay, delay jitter and loss rates, and adopt a connection-oriented, fixed-route, reservation-oriented approach to achieve these guarantees. In such an approach, resource allocation and route selection decisions are usually static (i.e. they are made before the start of the communication on the basis of resource availability and real-time network load at that time, and are usually kept for the duration of the communication). This static approach limits the flexibility of these GPC services. In our previous work we presented our solution to this lack of flexibility. This solution, the Dynamic Connection Management (DCM) Scheme, provides the network with the capability to dynamically modify the traffic characteristics, the performance requirements, and the route of any existing guaranteed-performance connection (C. Parris, H. Zhang and D. Ferrari, ACM Multimedia Systems Journal, 1 (6) (1993) 267–283). We also presented several simulation experiments that proved the feasibility of the scheme and analyzed its performance. In this work we complete this proof of concept by implementing the DCM scheme and conducting several initial measurement experiments on this prototype. The implementation utilized the data delivery protocols of the Tenet Real-Time Protocol suite and the Simple Network Management Protocol version 1 (SNMPv1) as the control or management protocol. The measurement experiments indicated that, although the scheme is indeed useful, there are several limitations caused by the use of SNMPv1.

Many future applications will require guarantees on network performance, such as bounds on throughput, delay, delay jitter, and reliability. To address this need, the authors have designed, simulated, and implemented a suite of network protocols to support real-time channels (network connections with mathematically provable performance guarantees). The protocols, which constitute the prototype Tenet real-time protocol suite (Suite 1), run on a packet-switching internetwork and can coexist with the popular Internet protocol suite. The authors rely on the use of connection-oriented communication, per-channel admission control, channel rate control, and priority scheduling. This protocol suite is the first set of transport and network-layer communication protocols that can transfer real-time streams with guaranteed quality in packet-switching internetworks. The authors have performed a number of experiments and demonstrations on multiple platforms using continuous-media loads (particularly video). The results show that the approach is both feasible and practical to build, and that it can successfully provide performance guarantees to real-time applications. The paper describes the design and implementation of, the suite, the experiments performed, and some of the lessons learned.

To support the requirements for the transmission of continuous media, such as audio and video, multiservice packet-switching networks must provide service guarantees to connections, including guarantees on throughput, network delays, and network delay variations. For the most demanding applications, the network must offer a service which provides deterministically bounded delay guarantees, referred to as "bounded delay service." The admission control functions in a network with a bounded delay service require 'schedulability conditions' that detect violations of delay guarantees in a network switch. Exact schedulability conditions are presented for three packet scheduling methods: earliest-deadline-first (EDF), static-priority (SP), and a novel scheduling method, referred to as rotating-priority-queues (RPQ). By characterizing the worst-case traffic with general subadditive functions, the presented schedulability conditions can be applied to a large class of traffic models. Examples, which include actual MPEG video traces, are presented to demonstrate the trade-offs involved in selecting a packet scheduling method for a bounded delay service.

For real-time communication services to achieve widespread usage, it is important that network managers be allowed to control the services effectively. An important management capability concerns resource partitioning. Resource partitioning is useful for a number of applications, including the creation of virtual private subnetworks and of mechanisms for advance reservation of real-time network services, fast establishment of real-time connections, and mobile computing with real-time communication. In previous work, the authors presented a scheme for resource partitioning in a guaranteed performance networking environment with EDD-based packet scheduling disciplines. The present paper gives the results of research in resource partitioning, with admission control tests for resource partitioned servers for four representative scheduling disciplines, FIFO, WFQ, RCSP and EDD. The simulations confirm the intuition that resource fragmentation losses due to resource partitioning are small and that resource partitioning reduces the admission control computation overhead. An interesting result from the simulation experiments is that, under circumstances that arise naturally in multi-party communication scenarios, resource partitioning results in higher overall connection acceptance rate. The authors also present experiences with implementing resource partitioning in the second generation of Tenet real-time protocols; this implementation, with resource partitioned servers, runs on multiple platforms, including Sun workstations under SunOS, DEC workstations under Ultrix, and PCs under BSDI Unix.>

Most of the solutions proposed to support real-time (i.e. guaranteed performance) communication services in packet-switching networks adopt a connection-oriented and reservation-oriented approach. In such an approach, resource allocation and route selection decisions are made before the start of the communication on the basis of resource availability and real-time network load at that time, and are usually kept for the duration of the communication. This rather static resource management approach has certain limitations: it does not take into account (a) the dynamicity of the communicating clients; (b) the dynamicity of the network state; and (c) the tradeoff between quality of service and network availability, thus affecting the availability and flexibility of the real-time network services. Availability is the ability of the network to accommodate as many real-time clients as possible, while flexibility is the ability to adapt the real-time services to changing network state and client demands. The authors present the dynamic connection management (DCM) scheme, which addresses these issues by providing the network with the capability to dynamically modify the performance parameters and the routes of any existing real-time connection. With these capabilities, DCM can be used to increase the availability and flexibility of the guaranteed performance service offered to the clients.>

In this paper we explore the packet starvation effect (PSE) that occurs in Ethernet controllers due to the unfairness of the CSMA/CD algorithm. The PSE causes some packets to experience latencies up to 100 times the average or to completely starve out due to 16 collisions. The PSE causes some packets to experience high delays at realistic offered loads as low as 40% and causes complete starvation of some packets at offered loads as low as 60%. The PSE makes CSMA/CD LANs unsuitable for real-time traffic except at offered loads much less than 100%. It is the limiting factor in the usable bandwidth of the bus. As an alternative to CSMA/CD, we present the fair dual distributed queue (FDDQ) algorithm. Under high load, FDDQ uses a single reservation mini-dot per packet and a tree-based collision resolution algorithm (CRA) to maintain two distributed queues of waiting senders. This provides two priority FCFS access to the network. FDDQ provides utilizations and average latencies very similar to those of CSMA/CD but is fair even at extremely high offered loads. The protocol is stable for a constant number of senders, is simple enough to be practical, should be implementable in firmware, and completely eliminates the PSE.>

Communication in real-time systems has to be predictable, because unpredictable delays in the delivery of messages can adversely affect the execution of tasks dependent on these messages. We develop a scheme for providing predictable interprocess communication in real-time systems with (partially connected) point-to-point interconnection networks, which provide guarantees on the maximum delivery time for messages. This scheme is based on the concept of a real-time channel, a unidirectional connection between source and destination. A real-time channel has parameters that describe the performance requirements of the source-destination communication, e.g., from a sensor station to a control site. Once such a channel is established, the communications subsystem guarantees that these performance requirements will be met. We concentrate on methods to compute guarantees for the delivery time of messages belonging to real-time channels. We also address problems associated with allocating buffers for these messages and develop a scheme that preserves delivery time guarantees.>

The authors propose a service discipline, called the rate-controlled static-priority (RCSP) queuing discipline, that provides throughput, delay, delay jitter, and loss free guarantees in a connection-oriented packet-switching network. The RCSP queuing discipline avoids both time-framing and sorted priority queues; it achieves flexibility in the allocation of delay and bandwidth, as well as simplicity of implementation. The key idea is to separate rate-control and delay-control functions in the design of the server. Applying this separation of functions results in a class of service disciplines of which RCSP is an instance.>

A scheme is developed for providing predictable interprocess communication in real-time systems with (partially connected) point-to-point interconnection networks, which provides guarantees on the maximum delivery time for messages. This scheme is based on the concept of a real-time channel, a unidirectional connection between source and destination. A real-time channel has parameters which describe the performance requirements of the source-destination communication, e.g., from a sensor station to a control site. Methods to compute guarantees for the delivery time of messages belonging to real-time channels are examined. Problems associated with allocating buffers for these messages are addressed, and a scheme which preserves delivery time guarantees is developed.>

Multimedia communication involving digital audio and/or digital video has rather strict delay requirements. A real-time channel is defined as a simplex connection between a source and a destination characterized by parameters representing the performance requirements of the client. A study is made of the feasibility of providing real-time services on a packet-switched store-and-forward wide-area network with general topology. A description is given of a scheme for the establishment of channels with deterministic or statistical delay bounds, and the results of the simulation experiments run to evaluate it are presented. The results are judged encouraging: the approach satisfies the guarantees even in worst case situations, uses the network's resources to a fair extent, and efficiently handles channels with a variety of offered load and burstiness characteristics. Also, the packet transmission overhead is quite low, and the channel establishment overhead is small enough to be acceptable in most practical cases.>

Workload characterization is that branch of performance evaluation which concerns itself with the measurement and modeling of the workloads to be processed by the system being evaluated. Since all performance indices of interest are workload-dependent, there is no evaluation study that does not require the characterization of one or more workloads. In spite of the importance of the problem, our knowledge in this area leaves much to be desired.

The growing acceptance of database systems makes their performance increasingly more important. One way to gain performance is to off-load some of the functions of the database system to aback-end computer. The problem is what functions should be off-loaded to maximize the benefits of distributed processing. Our approach to this problem consisted of constructing several variants of an existing relational database system. INGRES, that partition the database system software into two parts, and assigning these two parts to two computers connected by a local area network. For the purposes of this experiment, six different variants of the database software were constructed to test the sir most interesting functional subdivisions. Each variant was then benchmarked using two different databases and query streams. The communication medium and the communication software were also benchmarked to measure their contribution to the performance of each configuration. Combining the database and network measurement results, various conclusions were reached about the viability of the configurations, the desirable properties of the communications mechanisms to he used, the operating system interface and overhead, and the performance of the database system. The variants to be preferred depend on the hardware technology, operating system features, database system internal structure, and network software overhead.

It is argued that systems performance evaluation, in the first 20 years of its existence, has developed in substantial isolation from such disciplines as computer architecture, system organization, operating systems, and software engineering. The possible causes for this phenomenon, which seems to be unique in the history of engineering, are explored. Its positive and negative effects on computer science and technology, as well as on performance evaluation itself, are discussed. The drawbacks of isolated development outweigh its advantages. Thus, instructional and research initiatives to foster the rapid integration of the performance evaluation viewpoint into the mainstream of computer science and engineering are proposed.

In a paper published in 1984 [Ferr84], the validity of applying clustering techniques to the design of an executable model for an interactive workload was discussed. The following assumptions, intended not to be necessarily realistic but to provide sufficient conditions for the applicability of clustering techniques, were made:

This paper presents a modeling methodology for the design of file system organizations in a local area network environment. We first propose a characterization for the workload of typical business transaction systems, and then use this measurable characterization to derive input parameters for the file distribution graph models and the queuing network models that represent two completely different file system organizations, i.e., a file server-based file system and a distributed file system. Total system throughput and mean system response time are the indices used in comparing these two design approaches. An example of this comparison is given. It is shown that this methodology and these models are useful tools for the evaluation of certain design tradeoffs.

The principles on which artificial workload model design is currently based are reviewed. Design methods are found wanting for three main reasons: their resource orientation, with the selection of resources often unrelated to the performance impact of resource demands; their avoiding to define an accuracy criterion for the resulting workload model; and their ignoring the dynamics of the workload to be modeled. An attempt at establishing conceptual foundations for the design of interactive artificial workloads is described. The problems found in current design methods are taken into account, and sufficient conditions for the applicability of these methods are determined. The study also provides guidance for some of the decisions to be made in workload model design using one of the current methods.

One of the primary motivations for implementing virtual memory is its ability to automatically manage a hierarchy of storage systems with different characteristics. The composite system behaves as if it were a single-level system having the more desirable characteristics of each of its constituent levels. In this paper we extend the virtual memory concept to within the top level of a two-level hierarchy. Here, the top level is thought of as containing two additional levels within it. This hierarchy is not a physical one, but rather an artificial one arising from the employment of two different replacement algorithms. Given two replacement algorithms, one of which has good performance but high implementation cost and the other poor performance but low implementation cost, we propose and analyze schemes that result in an overall algorithm having the performance characteristics of the former and the cost characteristics of the latter. We discuss the suitability of such schemes in the management of storage hierarchies that lack page reference bits.

A local variable-size memory policy called the variable-interval sampled working set (VSWS) policy is described. The results of trace-driven simulation experiments reported here show that VSWS has a static performance comparable to those of the working set (WS) and sampled working set (SWS) policies, a dynamic performance better than those of WS, SWS, and the page fault frequency (PFF) policy, and similar to that of the damped working set (DWS) policy. Furthermore, VSWS generaly causes substantially less process suspensions than SWS, and is less expensive to implement than WS or DWS, since it requires the same hardware support as SWS and PFF. The sampling overhead of VSWS is comparable to that of SWS and lower than that of PFF.

Program restructuring techniques have proven successful in two-level automatically managed memory hierarchies. The possibility of extending them to multilevel environments is investigated. The performance of strategy-oriented restructuring algorithms in a three-level linear hierarchy managed by sampled working set policies or by a combination of sampled working set and local LRU policies is studied both analytically (assuming an independent reference model of program behavior) and by trace-driven simulation. The results of the study show that strategy-oriented restructuring may be as beneficial in a virtual memory with three levels as it is in one with two levels.

An algorithm for generating a page reference string which exhibits a given working set size behavior in the time domain is presented, and the possible applications of such a string are discussed. The correctness of the algorithm is proved, and its computational complexity found to be linear in the length of the string. A program implementing the algorithm, which is performed in one pass and requires very little space, is briefly described, and some experimental results are given.

Abstract A software measurement tool designed for the users of PRIME, an interactive system being developed, is presented. The tool, called SMT, allows its user to instrument a program, modify a pre‐existing instrumentation and specify how the collected data are to be reduced by typing in a few simple commands. The user can also write his own measurement routines, which specify the actions to be taken at event detection time, and submit them to the SMT; after checking their correctness, the SMT deals with them as with its built‐in, standard measurement routines. The design goals of a general‐purpose tool like the SMT are discussed, and the prototype version of the tool, which has been implemented, is described from the two distinct viewpoints of a user and of a measurement‐tool designer. An example of the application of the prototype to a measurement problem is illustrated, the reasons why not all of the design goals have been achieved in the implementation of the prototype are reviewed, and some of the foreseeable extensions of the SMT are described.

A software measurement tool designed for the users of PRIME, an interactive system being developed, is presented. The tool, called SMT, allows its user to instrument a program, modify a pre-existing instrumentation and specify how the collected data are to be reduced by typing in a few simple commands. The user can also write his own measurement routines, which specify the actions to be taken at event detection time, and submit them to the SMT; after checking their correctness, the SMT deals with them as with its built-in, standard measurement routines. The design goals of a general-purpose tool like the SMT are discussed, and the prototype version of the tool, which has been implemented, is described from the two distinct viewpoints of a user and of a measurement-tool designer. An example of the application of the prototype to a measurement problem is illustrated, the reasons why not all of the design goals have been achieved in the implementation of the prototype are reviewed, and some of the foreseeable extensions of the SMT are described.

Equation (14) on p. 226 of the above1 should have read:

A cellular structure ("transfer logic"), suitable for implementing sequential networks, is described in this paper. A method is outlined for obtaining, for a given flow table, a transfer logic assignment employing the minimal number of state variables. The method is based on the properties of partitions of the set of internal states.

Abstract—The operation speed of a one-dimensional, unilateral, iterative switching network with strictly combinational cells is often drastically limited by the propagation delays of carry variables. In this paper an attempt is made to extend to other iterative networks the scheme of a fast carry-propagation circuit proposed by several authors for parallel adder. The class of the networks which are realizable according to this scheme is small but contains many networks of practical interest.

The use of a parallel multiplier for performing high-speed binary division requires that an algorithm be devised that obtains the quotient by means of multiplications and additions. Furthermore, its hardware implementation must be as simple and as fast as possible. A suitable algorithm, which applies to a first approximation to the reciprocal of the divisor, has already been proposed[1]. A similar algorithm is presented in this paper. The comparison between the two methods for equal numbers of multiplications shows that the latter is more accurate. Conversely, a given accuracy can often be obtained with a higher speed. The generation of a piecewise-linear initial approximation is also discussed.