We start with the premise, and provide evidence that it is valid, that a Markov-modulated Poisson process (MMPP) is a good model for Internet traffic at the packet/byte level. We present an algorithm to estimate the parameters and size of a discrete MMPP (D-MMPP) from a data trace. This algorithm requires only two passes through the data. In tandem-network queueing models, the input to a downstream queue is the output from an upstream queue, so the arrival rate is limited by the rate of the upstream queue. We show how to modify the MMPP describing the arrivals to the upstream queue to approximate this effect. To extend this idea to networks that are not tandem, we show how to approximate the superposition of MMPPs without encountering the state-space explosion that occurs in exact computations. Numerical examples that demonstrate the accuracy of these methods are given. We also present a method to convert our estimated D-MMPP to a continuous-time MMPP, which is used as the arrival process in a matrix-analytic queueing model.

Most of the studies of feedback-based flow and congestion control consider only persistent sources which always have data to send. However, with the rapid growth of Internet applications built on TCP/IP such as the World Wide Web and the standardization of traffic management schemes such as Available Bit Rate (ABR) in Asynchronous Transfer Mode (ATM) networks, it is essential to evaluate the performance of feedback-based protocols using traffic models which are specific to dominant applications. This paper presents a method for analysing feedback-based protocols with a Web-user-like input traffic where the source alternates between "transfer" periods followed by "think" periods. Our key results, which are presented for the TCP protocol, are:(1) The goodputs and the fraction of time that the system has some given number of transferring sources are insensitive to the distributions of transfer (file or page) sizes and think times except through the ratio of their means. Thus, apart from network round-trip times, only the ratio of average transfer sizes and think times of users need be known to size the network for achieving a specific quality of service.(2) The Engset model can be adapted to accurately compute goodputs for TCP and TCP over ATM, with different buffer management schemes. Though only these adaptations are given in the paper, the method based on the Engset model can be applied to analyze other feedback systems, such as ATM ABR, by finding a protocol specific adaptation. Hence, the method we develop is useful not only for analysing TCP using a source model significantly different from the commonly used persistent sources, but also can be useful for analysing other feedback schemes.(3) Comparisons of simulated TCP traffic to measured Ethernet traffic shows qualitatively similar autocorrelation when think times follow a Pareto distribution with infinite variance. Also, the simulated and measured traffic have long range dependence. In this sense our traffic model, which purports to be Web-user-like, also agrees with measured traffic.

The Grassmann–Taksar–Heyman algorithm is a direct algorithm for computing the steady-state distribution of an finite irreducible Markov chain. We describe our experience in implementing this algorithm on a single-instruction multiple-data parallel processor computer. Our main conclusions are that a lower-level language has a performance advantage compared to Fortran, and that data storage is the limiting factor that determines the largest problem that can be solved. As a consequence, we devote considerable attention to storing a block tridiagonal transition matrix.

Heyman (1992) examined three sequences giving the number of cells per frame of a VBR encoding of videoconferences (talking heads); these sequences were produced by hardware encoders using different coding algorithms. Each sequence had a gamma marginal distribution, and the autocorrelation function was geometric up to lags of at least 3 s, which includes all autocorrelation values larger than 0.1. We present an easy to simulate autoregressive process that has these properties. The model is tested by comparing the cell-loss rate produced when the data trace was used as the sole source in a simulation of an ATM switch to the cell-loss rates produced when traces generated by the model were used as the source.

Traffic from video services is expected to be a substantial portion of the traffic carried by emerging broadband integrated networks. For variable bit rate (VBR) coded video, statistical source models are needed to design networks that achieve acceptable picture quality at minimum cost and to design traffic shaping and control mechanisms. For video teleconference traffic Heyman et al. (1992) showed that traffic is sufficiently accurately characterized by a multistate Markov chain model that can be derived from three traffic parameters (mean, correlation, and variance). The present authors describe modeling results for sequences with frequent scene changes (the previously studied video teleconferences have very little scene variation) such as entertainment television, news, and sports broadcasts. The authors analyze 11 long sequences of broadcast video traffic data. Unlike video teleconferences, the different sequences studied have different details regarding distributions of cells per frame. The authors present source models applicable to the different sequences and evaluate their accuracy as predictors of cell losses in asynchronous transfer mode (ATM) networks. The modeling approach is the same for all of the sequences but use of a single model based on a few physically meaningful parameters and applicable to all sequences does not seem to be possible.

The authors explore the influence of long-range dependence in broadband traffic engineering. The classification of stochastic processes {X/sub t/} into those with short or long-range dependence is based on the asymptotic properties of the variance of the sum S/sub m/=X/sub 1/+X/sub 2/+/spl middot//spl middot//spl middot/+X/sub m/. Suppose this process describes the number of packets (or ATM cells) that arrive at a buffer; X/sub t/ is the number that arrive in the tth time slice (e.g., 10 ms). We use a generic buffer model to show how the distribution of S/sub m/ (for all values of m) determines the buffer occupancy. From this model we show that long-range dependence does not affect the buffer occupancy when the busy periods are not large. Numerical experiments show this property is present when data from four video conferences and two entertainment video sequences (which have long-range dependence) are used as the arrival process, even when the transmitting times are long enough to make the probability of buffer overflow 0.07. We generated sample paths from Markov chain models of the video traffic (these have short-range dependence). Various operating characteristics, computed over a wide range of loadings, closely agree when the data trace and the Markov chain paths are used to drive the model. From this, we conclude that long-range dependence is not a crucial property in determining the buffer behavior of variable bit rate (VBR)-video sources.

The main contributions of this paper are two-fold. First, we prove fundamental, similarly behaving lower and upper bounds, and give an approximation based on the bounds, which is effective for analyzing ATM multiplexers, even when the traffic has many, possibly heterogeneous, sources and their models are of high dimension. Second, we apply our analytic approximation to statistical models of video teleconference traffic, obtain the multiplexing system's capacity as determined by the number of admissible sources for given cell loss probability, buffer size and trunk bandwidth, and, finally, compare with results from simulations, which are driven by actual data from coders. The results are surprisingly close. Our bounds are based on Large Deviations theory. Our approximation has two easily calculated parameters, one is from Chernoff's theorem and the other is the system's dominant eigenvalue. A broad range of systems are analyzed and the time for analysis in each case is a fraction of a second.

Recent measurement studies in Bellcore and elsewhere have convincingly established the presence of statistical self similarity in high-speed network traffic. What is less clear --- and as such the subject of intense current research --- is the impact of the self-similarity on network performance. Given that traditional queueing models of network performance do not model self-similarity, the validity of traditional models to predict network performance would be supported if it is shown that self-similarity does not have measurable impacts on performance. On the other hand, if the converse of this assertion were true, it would have significant impacts on the way networks are designed and analyzed, as well as open up new areas of research in mathematical modeling, queueing analysis, network design and control. The issues addressed in this session are therefore of fundamental importance in high-speed network research.Given that queueing behavior is dominated by traffic characteristics over the time scales of busy periods, it has been argued that phenomena that span many time scales, such as self-similarity, should not be relevant for queueing performance. However, the paper by Narayan, Erramilli and Willinger presents evidence that for data traffic, the long range dependence (which is related to the self-similarity in traffic) can dominate queueing behavior under a variety of conditions. Specifically, it is shown based on a series of carefully designed simulation experiments with actual traffic traces, that the queueing behavior with actual traces is considerably heavier than that predicted by traditional theory, and that these differences are attributable to long range dependence. The paper by Heyman and Lakshman investigates modeling of video traffic to predict cell loss performance with finite buffer systems, and they conclude that long-range dependence is not a crucial property in determining the finite buffer behavior of video conferences. In particular, a Markov chain model that does not model long-range dependence is nevertheless able to reproduce various operating characteristics over a wide range of loadings obtained with the actual video trace. Mukherjee, Adas, Klivansky and Song investigate the performance impacts of short-range and long-range correlation components using simulations with a fractional ARIMA model. They also discuss a strategy to provide quality of service guarantees with long range dependent traffic, as well as recent results on NSFNET traffic. Finally, the paper by Li describes a frequency-domain based analytical tool that matches a special class of Markov chains with traces exhibiting a variety of characteristics, including long-range dependence. Good agreement is reported between analytical queueing solutions of the matched Markov chains, and simulation results obtained video and data traffic traces.This session therefore brings together a wide range of viewpoints on this issue. Resolution of such seemingly conflicting conclusions lies in the fact that in performance analysis, answers sensitively depend on the specific details of a problem. Thus the proper question to ask is not whether or not self-similarity matters in queueing; but under what conditions it matters. Likewise, the question to ask is not whether a class of models is invalid; but to identify the conditions under which traditional Markov or self-similar traffic models are expected to be valid. Finally, given an understanding of statistical features that are relevant to a given problem, the challenge is to model these accurately and parsimoniously so that the model is useful in practical performance analysis. The work outlined in the abstracts below adds significantly to our understanding of these issues.

Aggregation/disaggregation is an iterative scheme that leads to an algorithm for computing the steady-state distribution of a finite Markov chain. The idea is to partition the states into aggregates, estimate the probability that the Markov chain is in a particular aggregate, and then estimate the conditional probability of being in each state of an aggregate given that the Markov chain is in some state in that aggregate. Previous computational performance studies of this algorithm concentrated on applying it to chains that were nearly decomposable. We focus on chains that are not nearly decomposable. We compare this iterative algorithm to a direct method that is a variant of Gaussian elimination. We use a variety of test problems that range in size from 500 to 5,000 states, and which include unstructured and banded matrices. We conclude that, for this array of problems, the direct method requires less computation. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The main contributions of this paper are two-fold. First, we prove fundamental, similarly behaving lower and upper bounds, and give an approximation based on the bounds, which is effective for analyzing ATM multiplexers, even when the traffic has many, possibly heterogeneous, sources and their models are of high dimension. Second, we apply our analytic approximation to statistical models of video teleconference traffic, obtain the multiplexing system's capacity as determined by the number of admissible sources for given cell-loss probability, buffer size and trunk bandwidth, and, finally, compare with results from simulations, which are driven by actual data from coders. The results are surprisingly close. Our bounds are based on large deviations theory. The main assumption is that the sources are Markovian and time-reversible. Our approximation to the steady-state buffer distribution is called Chenoff-dominant eigenvalue since one parameter is obtained from Chernoffs theorem and the other is the system's dominant eigenvalue. Fast, effective techniques are given for their computation. In our application we process the output of variable bit rate coders to obtain DAR(1) source models which, while of high dimension, require only knowledge of the mean, variance, and correlation. We require cell-loss probability not to exceed 10/sup -6/, trunk bandwidth ranges from 45 to 150 Mb/s, buffer sizes are such that maximum delays range from 1 to 60 ms, and the number of coder-sources ranges from 15 to 150. Even for the largest systems, the time for analysis is a fraction of a second, while each simulation takes many hours. Thus, the real-time administration of admission control based on our analytic techniques is feasible.>

Traffic from video services is expected to be a substantial portion of the traffic carried by emerging broadband integrated networks. For variable bit rate (VBR) coded video, statistical source models are needed to design networks that achieve acceptable picture quality at minimum cost, and to design traffic shaping and control mechanisms. For video teleconference traffic, the authors have previously shown that traffic is sufficiently accurately characterized by a multi-state Markov chain model that can be derived from three traffic parameters (mean, correlation, and variance). In the present paper, they describe modeling results for sequences with frequent scene changes (the previously studied video teleconferences have very little scene variation) such as entertainment television, news, and sports broadcasts. They analyze eleven long sequences of broadcast video traffic data. Unlike video teleconferences, the different sequences studied have different details regarding distributions of cells per frame. The authors present source models applicable to the different sequences and evaluate their accuracy as predictors of cell losses in asynchronous transfer mode (ATM) networks.>

Existing congestion control and network management techniques have been designed to cope with problems such as unexpectedly high offered load and hardware failures. On rare occasions, networks have failed despite the deployment of such techniques. The authors survey the current research in congestion control and network management techniques and their role in ensuring network stability in the presence of software errors. What situations are these techniques intended to address? What are the characteristics of the problems that have led to network collapse? What areas of research offer the best prospect for further improving network reliability?.>

Results of a simulation study of the potential multiplexing gains from using variable-bit-rate encoding to multiplex video teleconferencing traffic over an asynchronous transfer mode (ATM) network are presented. Simulated traffic from several video teleconferences was fed into a buffer and multiplexed onto a higher speed output line. The study observed the cell loss resulting from buffer overflow. The spacings between the start times for the individual video conferences are found to have a large role in determining the aggregate cell-loss-rate seen by the collection of calls. After the cell-loss-rate becomes non-negligible, it grows rapidly as a function of the number of input lines. The cell losses are not distributed uniformly over time but are clustered, with the consequence that the probability that a call is loss free is much better than indicated by the cell-loss-rate.>

In this paper we consider Markov chains with these properties. The transition matrix is banded, and except for some boundary conditions, when the transition matrix is written in block form, the rows are identical except for a shift to the right. Some authors have used variants of the state reduction method to solve special cases. We present a general algorithm and some of the theoretical underpinnings of these methods. In particular, we give a rigorous proof of convergence. We also provide a simple method to norm the probabilities such that their sum is unity. We describe the connection between this new technique and the matrix-iterative methods of M. F. Neuts. The paper concludes with some numerical examples. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Results are presented of a simulation study of the potential multiplexing gains from using variable-bit-rate (VBR) encoding to multiplex video teleconferencing traffic over an asynchronous transfer mode (ATM) network. Simulated traffic from several video teleconferences is fed into a buffer and multiplexed onto a higher-speed output line. The cell loss resulting from buffer overflow is observed. The major results are as follows: (1) the spacing between cells has a large role in determining the aggregate cell loss rate seen by a collection of calls. The cell loss rate is reduced when either the frame start times are evenly spaced or cells are evenly distributed in the video frame. (2) After the cell loss rate becomes nonnegligible, it grows rapidly as a function of the number of access lines. (3) The cell losses are not distributed uniformly over time but are clustered. A consequence is that the average time between clusters of cell loss and the time to first loss is greater than if the losses were spaced uniformly. (4) A simple model is found to describe when a cluster of cell losses occurs, the duration of the cluster, and how many cells are lost in the cluster.>

Source modeling and performance issues are studied using a long (30 min) sequence of real video teleconference data. It is found that traffic periodicity can cause different sources with identical statistical characteristics to experience differing cell-loss rates. For a single-stage multiplexer model, some of this source-periodicity effect can be mitigated by appropriate buffer scheduling and one effective scheduling policy is presented. For the sequence analyzed, the number of cells per frame follows a gamma (or negative binomial) distribution. The number of cells per frame is a stationary stochastic process. For traffic studies, neither an autoregressive model of order two nor a two-state Markov chain model is good because they do not model correctly the occurrence of frames with a large number of cells, which are a primary factor in determining cell-loss rates. The order two autoregressive model, however, fits the data well in a statistical sense. A multistate Markov chain model that can be derived from three traffic parameters is sufficiently accurate for use in traffic studies.>

We examine several methods for numerically solving linear equations that arise in the study of Markov chains. These methods are Gaussian elimination, state-reduction, closed-form matrix solutions, and some hybrid methods. The emphasis is on moments of first-passage times and times to absorption. We compare the methods on the basis of accuracy and computation. We conclude that state-reduction is the most accurate and that the matrix solutions have the least computation time. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

We present a performance model of the carrier-sense multiple-access protocol with collision detection when each message consists of a geometrically distributed number of packets. We solve the model analytically and present numerical evidence that throughput degrades slightly when the mean number of packets per message is increased and the load is kept constant. The numerical examples indicate that the average response time of a message is approximately proportional to the average number of packets per message. We also derive a general relation between throughput and average response time that provides a theoretical explanation of these results.

In this paper we address the performance issues that arise as a result of the two level scheduling in a database/operating system. At the upper (database) level transactions are logically scheduled so as to maintain the database integrity. At the lower (operating system) level physical disk requests are scheduled.We consider the performance problems that result from the interplay between these two levels of scheduling. Our model assumes the existence of a dictionary that must be consulted prior to the execution of a transaction. We derive the optimal disk placement of this dictionary and our results show that the waiting time for dictionary look-up is the critical component in the transaction response-time for a wide range of transaction sizes. To alleviate this problem we suggest alternative approaches to dictionary placement in such systems.

As data are updated, the initial physical structure of a database is changed and retrieval of specific pieces of data becomes more time consuming. This phenomenon is called database degradation. In this paper two models of database degradation are described. Each model refers to a different aspect of the problem. It is assumed that transactions are statistically independent and either add, delete, or update data. The first model examines the time during which a block of data is filling up. The second model examines the overflows from a block of data, which essentially describes the buildup of disorganization. Analytical results are obtained for both models. In addition, several numerical examples are presented which show that the mean number of overflows grows approximately linearly with time. This approximation is used to devise a simple formula for the optimal time to reorganize a stochastically growing database.