This paper discusses two approaches to statistical multiplexing: rate envelope multiplexing, allowing resource sharing with small delays for low peak rate connections, and rate sharing, based on the use of large multiplexer buffers to ensure high link utilization for high speed data traffic. We argue that the weighted fair queueing scheduling algorithm provides an efficient means for combining both kinds of multiplexing in the B-ISDN. A feasible implementation known as Virtual Spacing is outlined. We illustrate the flexibility of the proposed scheme by showing how different service categories could be provided.

A new rate-controlled queueing discipline, called virtual rate-based queueing (VRBQ), is proposed for packet-switching nodes in connection-oriented, high-speed, wide-area networks. The VRBQ discipline is based on the virtual rate which has a value between the average and peak transmission rates. By choosing appropriate virtual rates, various requirements can be met regarding the performance and quality of services in integrated-service networks. As the worst-case performance guarantee, we determine the upper bounds of queueing delay when VRBQ is combined with an admission control mechanism, i.e., Dynamic Time Windows or Leaky Bucket. Simulation results demonstrate the fairness policy of VRBQ in comparison with other queueing disciplines, and the performance of sources controlled under different virtual rates.

This paper presents an alternative traffic model for an ATM multiplexer providing video, voice, image, and data services. The traffic model classifies the input traffic into two types: real-time and non-real-time. The input process for realtime traffic is periodic and correlated, while that for non-realtime traffic is batch Poisson and independent. This multiplexer is assumed to be a priority queueing system with synchronous servers operating on time-frame basis and with separate finite buffers for each type of traffic. State probabilities and performance measures are successfully obtained using a Markov analysis technique and an application of the residue theorem in complex variable. The results can be applied in the design of an ATM multiplexer.

Kumar and Billinton have presented a new technique for obtaining the steady-state probabilities from a flow graph based on Markov model. By examining the graph and choosing suitable input and output nodes, the steady-state probabilities can be obtained directly by using the flow graph. In this paper this graphical technique is applied for a k-out-of-n: G repairable system. Consequently a new derivation way of the formulae for the steady-state availability and MTBF is obtained.

Go-Back-N automatic repeat request (GBN ARQ) and Stop-and wait (SW) ARQ schemes are one of fundamental and widely used error control procedures for data communication and computer communication systems. The throughput and delay performances of these ARQ schemes have been analyzed for a random error channel, which could not applicable for a radio channel, for example. In this paper, considering the correlated, noisy channel, we derive the exact formula for the delay of a frame in GBN and SW ARQ schemes. First, the delay formula for the discrete time M[x]/G/1 queueing system with starter. Next, the virtual service time of a frame is found in terms of the decay factor of a two-state Markov chain. As a result, it is shown that the performance of the delay is improved with the larger decay factor.

Recently, the throughput performances of ARQ's have been analyzed over a Markov error channel. It has been shown that given a round-trip-delay, the throughput of the Stop-and-Wait ARQ is dependent only on the overall average packet-error probability. In this paper, we exactly analyze the Stop-and-Wait ARQ scheme under the condition that the channel is slotted and packet errors occur according to a two-state Markov chain which is characterized by the decay factor. The distribution of packet delay time and the channel usage factor are obtained. From the analytical results and numerical examples, it is shown that for a given round-trip-delay, the average packet delay time and the channel utilization factor depend on both the overall average packet-error probability and the decay factor characterizing the two-state Markov chain. Furthermore, the decay factor gives different influence on the average delay time and the channel usage factor depending on whether the round-trip-delay is even slots or not.

Queueing problems are investigated for very wide classes of input traffic and service time models to obtain good loss probability and waiting time probability approximation. The proposed approximation is based on the fundamental recursion formula and the Chernoff bound technique, both of which requires no particular assumption for the stochastic nature of input traffic and service time, such as renewal or markovian properties. The only essential assumption is stationarity. We see that the accuracy of the obtained approximation is confirmed by comparison with computer simulation. There are a number of advantages of the proposed method of approximation when we apply it to network capacity design or path accommodation design problems. First, the proposed method has the advantage of applying to multi-media traffic. In the ATM network, a variety of bursty or non-bursty cell traffic exist and are superposed, so some unified analysis methodology is required without depending each traffic's characteristics. Since our method assumes only the stationarity of input and service process, it is applicable to arbitrary types of cell streams. Further, this approach can be used for the unexpected future traffic models. The second advantage in application is that the proposed probability approximation requires only small amount of computational complexity. Because of the use of the Chernoff bound technique, the convolution of every traffic's probability density fnuction is replaced by the product of probability generating functions. Hence, the proposed method provides a fast algorithm for, say, the call admission control problem. Third, it has the advantage of accuracy. In this paper, we applied the approxmation to the cases of homogeneous CBR traffic, non-homogeneous CBR traffic, M/D/1, AR(1)/D/1, M/M/1 and D/M/1. In all cases, the approximating values have enough accuracy for the exact values or computer simulation results from low traffic load to high load. Moreover, in all cases of the numerical comparison, our approximations are upper bounds of the real values. This is very important for the sake of conservative network design.

This paper is a study on the behavioral aspects of the input buffer limiting scheme whose basic feature is to award priority to the transit messages over the input messages so that congestion does not develop in the network. The numerical method employed in the analysis is that proposed in Ref.(7). The performance aspects are studied for different buffer capacities, different message handling capacities and different levels of reservation for transit traffic. The numerical method indicates that thrashing occurs at low levels of reservation for the transit messages, irrespective of the buffer size or the processor capacities of the node. This observation is supported by simulation results. With reference to the state-space of the model of our study, the congestion aspects are related to two Liapunov functions. Under the domain of one of the Liapunov functions, the evolution of the perturbed system is towards a congested state whereas, under the domain of the other Liapunov function, the evolution is towards a congestion-free state. Regardless of the configuration, it is found that the fundamental characteristic of the congestion under the input buffer limiting scheme is the characteristic of a fold catastrophe. In the systems with insufficient level of reservation for the transit traffic, the performance degradation appears to be inevitable, irrespective of the capacities of the nodal processor and output channel processor, and the size of the buffer pool. Given such an inevitability, the active life of a node under a typical node configuration is studied by simulation. A suitable performance index is suggested to assess the performance of deadlock-prone nodes.

Processors are important resources of stored program control (SPC) switching systems, and estimation of their workload level is crucial to maintaining service quality. Processor utilization is measured as processor usage per unit time, and workload level is usually estimated from measurement of this utilization during a given interval. This paper provides an approximate distribution of processor utilization of SPC switching systems, and it provides a method for designing an overload detection scheme. This method minimizes the observation interval required to keep overload detection errors below specified values. This observation interval is obtained as an optimal solution of a linear programming.

The embedded Markov processes associated with Markovian queueing systems are closely related, and their relationships are important for establishing an analytical basis for performance evaluation techniques. As a first step, we analyze the embedded processes associated with a general M/M/1 queueing system. Linear transformations between the infinitesimal generators and the transition probability matrices of embedded processes at arrival and departure times are explicitly derived. Based upon these linear transformations, the equilibrium distributions of the system states at arrival and departure times are obtained and expressed in terms of the equilibrium distribution at arbitrary times. The approach presented here uncovers an underlying algebraic structure of M/M/1 queueing systems, and establishes an algebraic methodology for analyzing the equilibrium probabilities of the system states at arrival and departure times for more general Markovian queueing systems.

This paper describes the integration of a qualitative method and a quantitative method by Bottleneck Diagnosis/Improvement Expert Systems for Synchronized queueing network (BDES-S and BIES-S). On the basis of qualitative reasoning, BDES-S can carry out parameter tuning in order to diagnose and improve bottlenecks of synchronized queueing networks. BDES-S can produce several alternative qualitative improvement plans for one bottleneck server. BIES-S can produce quantitative improvement equations for each qualitative improvement plan. Our method using BDES-S and BIES-S can integrate both quantitative and qualitative methods for parameter tuning on complicated queueing synchronized networks.

The effect of mesage-class dependent threshold-type scheduling on queueing delay and resequencing delay for the M/M/n queueing system is analyzed. We first derive the expressions for the state transition equations, mean queueing delay, resequencing delay and total delay for the M/M/n queueing system shared by C different message classes under a threshold-type scheduling in which the threshold values depend on the message class at the head of queue and the number of messages in the buffer. Next, the numerical calculation and the computer simulation are carried out for the queueing system with two servers. It is found that the message-class dependent threshold-type scheduling is effective to reduce the resequencing delay of some specific message class, which can not be attained under the conventional threshold-type scheduling, and thus, the proposed scheduling can satisfy the different requirements of the different message classes, such as minimizing only queueing delay or total delay including resequencing delay.

Optimal static load balancing problems in open BCMP queueing networks with state-independent arrival and service rates are studied. Their examples include optimal static load balancing in distributed computer systems and static routing in communication networks. We refer to the load balancing policy of minimizing the overall mean response (or sojourn) time of a job as the overall optimal policy. We show the conditions that the solutions of the overall optimal policy satisfy and show that the policy uniquely determines the utilization of each service center, the mean delay for each class and each path class, etc., although the solution, the utilization for each class, the mean delay for all classes at each service center, etc., may not be unique. Then we give tha linear relations that characterize the set whose elements are the optimal solutions, and discuss the condition wherein the overall optimal policy has a unique solution. In parametric analysis and numerical calculation of optimal values of performance variables we must ensure whether they can be uniquely determined.