Several researchers have suggested employing two-stage entry monitors for high-speed networks; the first stage enforcing a long term rate, the second stage enforcing a peak rate over a shorter time scale. In spite of this interest, little work on analyzing such systems has appeared. Not only is the analysis hard because of the the correlation between the stages, but for the most popular policing scheme, the leaky bucket, prior work is not easily generalized to two stages. This paper presents a performance analysis of a two-stage entry monitor, by analyzing the combined queue length of a two-stage system. Our analysis is for a two-stage buffered moving window. Analyzing such a conservative scheme enables us to bound the penalty of more optimistic schemes, in particular a two stage leaky bucket based system. We obtain a closed form analytical result, and show how to evaluate it for a wide range of parameters of interest. Our results show that the performance penalty of having the second stage is minimal under reasonable rate assumptions.

Polling systems have been used to model a large variety of applications and much research has been devoted to the derivation of efficient algorithms for computing the delay measures in these systems. Recent research efforts in this area, which have focused on the optimization of these systems, have raised the need for very efficient such algorithms. This work develops the descendant set approach as a general efficient algorithm for deriving all moments of customer delay (in particular, mean delay) in these systems. The method is applied to a very large variety of model variations, including: 1) The exhaustive and gated service policies, 2) Fractional service policies, 3) The cyclic visit order, 4) Arbitrary periodic visit orders (polling tables), and 5) Customer routing. For most of these variations the method significantly outperforms the algorithms commonly used today.>

A large variety of computer communications systems, in particular the token ring network, are modeled and analyzed as polling systems. The authors present the descendant set approach as a general efficient algorithm for deriving all moments of packet delay (in particular, mean delay) in these systems. The method can apply to a very large variety of model variations including: the exhaustive, gated, and fractional service policies; the cyclic visit order; arbitrary periodic visit orders, (polling tables); random polling orders; and customer routing. For most variations the method significantly outperforms the algorithms commonly used.>

We study a data structure ${\bf L}$ referred to variously as a padded list, controlled density array or sparse table containing records $\{ R_i \} $ each uniquely identified by a key $\{ k(R_i )\} $. ${\bf L}$ is required to support the operations Search $({\bf L},k)$, Insert $({\bf L},k)$ and Delete $({\bf L},k)$ to search, insert and delete a record with key k. To optimize Search $({\bf L},k)$, records are stored with their keys in sorted order. If the order of the keys is to be maintained under insertion, records currently in ${\bf L}$ must be moved to free space. To improve the efficiency of Insert $({\bf L},k)$, records are stored in a circular buffer with “gaps” so that insertion necessitates moving only records up to the next gap. The array is expanded and contracted during a sequence of insertions and deletions depending upon the current number of gaps. In this paper we assess the amount of work required to insert a sequence of records.

Consider a closed cyclic queuing system consisting of M exponential queues.The Laplace-Stieltjes transform of the joint d~stribution of the consecutive sojourn times of a customer at the M queues is determined and shown to have a product form.The proof is based on a reverslbdity argument.

Let $(p_1 ,p_2 , \cdots ,p_n )$ be a probability distribution, $\pi = (\pi _1 ,\pi _2 , \cdots ,\pi _n )$ be a permutation of $1,2, \cdots ,n$ and $X_1 ,X_2 , \cdots ,X_k $ be k independent and identically distributed random variables with distribution $P(X = i) = p\pi _i $. It is known that the organ pipe permutation $\pi ^ * $ makes the range \[ D(k,\pi ) = \max\limits_{1 \leqq j \leqq k} X_i - \min\limits_{1 \leqq j \leqq k} X_i \]a stochastic minimum for $k = 2$ (P. P. Bergmans, Information and Control, 20 (1972), pp. 331–350), and minimal on the average for general k (J. R. Bitner and C. K. Wong, 8 (1979), pp. 479–498). We prove the stochastic minimality for general k and study a natural extension of the organ pipe permutation that is optimal when certain constraints are placed on the possible choices of $\pi $.

-A model of a moving-boundary, fixed frame length, integrated multiplexor is proposed and analyzed. The assignment of slots within a frame to the voice and data sources is made by an allocation function. The joint distributions of queue length and expected waiting time are derived.

In every data communication system, a procedure must be provided to allow for the retransmission of data when errors are detected. The receiving node is required to make a (positive/negative) acknowledgment (ACK/NACK) to the sending node. Until an acknowledgment is received, a "copy" of the message must be retained at the sending node. If an ACK is received, the space assigned to the "copy" is released. If either a NACK or no acknowledgment is received in a suitable interval of time, retransmission is required. Different protocols specifying how the nodes recover from a transmission error can be defined. In this paper, we present a queueing analysis of the two ARQ (automatic repeat request) protocols-block and select ARQ-for a (slotted) concentrator network node.

A queuing system with a buffer of unlimited capacity in front of a cyclic arrangement of two exponential server queues is analyzed. The main feature of the system is blocking, i.e., when the population in the two queues attains a maximum value M, say, new arrivals are held back in the buffer. The solution is given in form of polynomial equations which require the roots of a characteristic equation. A solution algorithm is provided. The stability condition is given in terms of these roots and also in explicit form. Limiting cases which are of practical interest are discussed. These limiting cases lead to a better understanding of some popular approximation techniques.

The relationship between certain techniques for the storage of information in a computer and a cell occupancy problem is shown Specifically, consider n cells or buckets each capable of holding k balls.Balls are distributed into the cells randomly A ball sent to the/th cell is placed either into the ]th cell or into the first cell to the right of the/th cell which has k -1 or fewer balls The placement of balls into cells requires comparisons to determine the status of the cells The distribution and expected value of the number of such comparisons and in particular the behavior as n --~ ~ are determined

The last few years have witnessed the intensive growth of computer communication networks. The need for nationwide and multination computer communication systems brought about the development of packet-switching networks such as the ARPANET. In this paper we examine a model for computer-to-computer communication via a satellite link. In each network, a single node, the satellite communication concentrator (SCC), manages the flow of information between the terminals in the network and the satellite link. The SCC buffers messages from the terminals and retransmits them over the satellite channel. Buffer space claimed by a message is made free only after the SCC receives an acknowledgment from the receiving network; transmission errors cause the buffer to retransmit the message. The statistical behavior of such a system is considered.

Modeling and performance prediction are becoming increasingly important issues in the design and operation of computer communications systems. Complexities in their configuration and sophistications in resource sharing found in today's computer communications demand our intensive effort to enhance the modeling capability. The present paper is intended to review the state of affairs of analytic methods, queueing analysis techniques in particular, which are essential to modeling of computer communication systems. First we review basic properties of exponential queueing systems, and then give an overview of recent progress made in the areas of queueing network models and discrete-time queueing systems. A unified treatment of buffer storage overflow problems will be discussed as an application example, in which we call attention to the analogy between buffer behavior and waiting time in theGI/G/1queue. Another application deals with the analysis of various multiplexing techniques and network configuration. An extensive reference list of the subject fields is also provided.

A two-stage queueing network with feedback and a finite intermediate waiting room is studied. The first-stage server is blocked whenever M requests are enqueued in the second stage. The analysis of this system under exponential assumptions is carried out. An algorithm to calculate the stationary state probabilities is given and some special cases are considered.

This paper offers an approximate analysis of the chaining operation in a loop system. The system consists of a central processor andNterminals linked by a common communication channel. Chaining refers to the service protocol whereby the channel is assigned in sequence to each of the terminals. Messages from terminals to the central processor are sent as chains of segments. The object of the analysis is to display the relationships between the arrival processes, the channel allocation, and the response of the system.

In this note we give an elementary method for calculating the stationary distribution of waiting time in a G/G/1 queue.

The finite capacity of storage has a significant effect on the performance of a contemporary computer system. Yet it is difficult to formulate this problem and analyze it by existing queueing network models.

A loop system with N buffered terminals sharing a common time-multiplexed channel is studied. The service discipline is prescribed by a permutation φ = (φ(1), ···, φ( N )) which gives the relative ranking of the terminals. Data from the i th terminal may be buffered at an intermediate terminal—its transmission to the CPU interrupted—if there is a conflict with data from a terminal with higher ranking. It is shown how such systems may be analyzed and how the system performance, as measured by average response time, may be improved by imposing a suitable priority discipline.

A communication system consisting of a number of buffered input terminals connected to a computer by a single channel is analyzed. The terminals are polled in sequence and the data is removed from the terminal's buffer. When the buffer has been emptied, the channel, for an interval of randomly determined length, is used for system overhead and/or to transmit data to the terminals. The system then continues with a poll of the next terminal. The stationary distributions of the length of the waiting line and the queueing delay are calculated for the case of identically distributed input processes.

The statistical behavior of a loop service system is studied.The system consists of a main station, a server and N stations arranged on a loop.Customers arrive at each station according to a random process.The server makes successive tours along the loop bringing customers from the N stations to the main station.Two related measures of the grade of service are considered: the average queue length and the average virtual waiting time at each station.

This paper studies the merging operation when data is stored on the surfaces of a disk. The data consists of q lists (each of n numbers) stored on a disk. Each list is stored on one surface of a disk. The time needed to merge into a single (sorted) list, T, is a function of the required motion of the reading head. In this paper we calculate the expected value of T.

Recent advances in computer communications are discussed including computer-traffic and channel error characteristics, optimal fixed message block size, statistical multiplexing, and loop systems. A unified model is developed and then used to analyze the queueing behavior of the star and loop systems. Numerical results for selected traffic intensities and message lengths, given in graphical form, provide insight into the performance of these systems.

A model of a storage system involving a disk and a buffer is analyzed under two access disciplines.The average stationary access rate is calculated for each discipline.

Abstract A model for a communication system which consists of a computer and a number of buffered terminals connected by means of a loop channel is analyzed. Data flows in two directions: from the computer to the terminals and from the terminals to the computer. The channel is alternately available to the computer and the terminals to effect these data transfers. The transient behavior of the system is determined and the stationary or limiting expected queue lengths at all terminals are calculated.