Fairness is an important property of computer networks and systems. In a wide range of these systems such as distributed multi-hop wireless networks, multihomed networks, and cloud computing, each user may be allocated a number of system resources; this resembles a many-to-many relationship between the sets of users and resources, which raises the problem of system-wide fair resource allocation. In this paper, we assume that each user/node can be allocated a number of resources, which could be either in its neighborhood or far from it. As a key difference with previous works and through incorporating the concept of “flow”, we model near/far resources allocated to nodes. To attain fair flow control in such systems, first we model this situation by introducing a new multi-server system called multi-ring, in which a server that represents a resource, can serve only a subset of either neighboring or far nodes in the system. Then, we define a centralized optimization problem to attain weighted proportional fairness among all nodes meaning that the sum of allocated capacities from all servers to each node (while considering its flow) is fair. We evaluate fairness properties of multi-ring networks and provide conditions on system parameters under which a system can have a fair resource allocation. Moreover, we present a distributed method to attain fairness in distributed environments, and its stability/convergence is evaluated by non-linear discrete dynamical systems. We present conditions under which the system is stable, and through numerical analysis, we show how to obtain stable system parameters for large systems. The effectiveness of the presented method is studied through extensive numerical evaluation. Results show the success of our method in attaining fairness for various topologies and system parameters, and confirm our stability analysis. A number of systems with fairness issues are also studied as potential applications of our model.

Maintaining efficiency and fairness is a challenging problem in distributed systems and networks. In this paper, we focus on distributed multi-server systems and networks in which each user may be allocated resources by different servers. Reemphasizing polling systems as abstractions of resource sharing systems, in this paper, first we introduce a multi-server polling system in which each server (resource) can poll (be allocated to) only a subset of queues (users) in the system to model a wide range of multi-server systems such as multihomed networks and cloud computing. Then, to obtain a fair resource allocation vector to queues, a network utility maximization problem with a general utility function is defined. Depending on the type of the utility function, the presented scheme can attain different kinds of fairness such as weighted proportional and max-min fairness. Although maintaining fairness is important in many applications, providing efficiency is also crucial. Hence, we present an efficient algorithm to convert the obtained fair resource allocation vector into a Markovian routing matrix to determine the polling order of queues. This algorithm is capable of improving performance measures such as delay variance and mitigating short-term unfairness by minimizing the probability of consecutive polling of the same queue. Two distributed schemes are presented to obtain fairness and efficiency in even highly dynamic and distributed environments. The effectiveness of the presented schemes is also studied through simulation and numerical evaluation. Our results show their success in attaining fairness and efficiency in dynamic multi-server distributed systems and networks.

Optical buffers based on Fiber Delay Lines (FDL) have been proposed for contention resolution in optical packet/burst switching systems. In this article, we propose a retrial queuing model for FDL optical buffers in asynchronous optical switching nodes. In the considered system, the reservation model employed is of post-reservation type and optical packets are allowed to re-circulate over the FDLs in a probabilistic manner. We combine the MMPP-based overflow traffic models of the classical circuit switching literature and fixed-point iterations to devise an algorithmic procedure to accurately estimate blocking probabilities as a function of various buffer parameters in the system when packet arrivals are Poisson and packet lengths are exponentially distributed. The proposed algorithm is both accurate and fast, allowing one to use the procedure to dimension optical buffers in next-generation optical packet switching systems.

In packet communication systems, a header is attached to the transmitted packet at each layer. The overhead due to the transmission of the individual header can have a significant impact on the performance of the communication system especially when the system operates in heavy load. In order to increase data throughput, a number of packets sharing a single header can be aggregated into a frame. In this paper, we present a mathematical model for a packet aggregation system assuming a general distribution for the packet length. For a given header size, we obtain the minimum system utilization where packet aggregation improves the system performance. We also analyze the asymptotic behavior of such systems leading to a simple heuristic policy on the optimum aggregation level. It is shown that the impact of the variability of the packet length distribution on different system performance measures is rather insignificant when the system load is low or moderate.

In packet communication systems, a header is attached to the transmitted packet at each layer. The overhead due to the transmission of the individual header can have significant impact on the performance of the communication system especially when the system operates in the heavy load. In order to increase data throughput, a number of packets can be aggregated into a frame in a particular OSI layer. In this paper, we present a queuing model with batch service which describes a packet aggregation process for Poisson arrivals and Phase-type service time distributions of the transmitted packets. We focus on the asymptotic behavior of such systems providing a significant reduction in the numerical complexity of their solution and provide analysis of the end-to-end delay of a packet transmitted by the system. Simple expressions for bounds on the average total delay of a packet are obtained. Based on results of experiments with the analytical model, we provide the minimum header size for which packet aggregation improves the system performance. It is numerically shown that the impact of the variability of the packet service time is rather insignificant when the system load is moderate or low. We also examine numerically the accuracy of the bound on the average total packet delay.

In an attempt to increase data throughput, many modern data transmission protocols provide capabilities for aggregating transmitted data fragments into larger packets at the time of encapsulation in a particular OSI layer. The decision and ability to aggregate packets into a single frame can have significant impact on the performance of the communication system. The impact can be even more substantial when the system operates under a heavy load. In this paper, we present a queuing model which describes a packet encapsulation and aggregation process. We assume Poisson arrivals and phase-type service time distributions for the transmitted packets. Using the proposed queuing model, we provide analysis of the end-to-end delay of a packet transmitted by the system. We verify analytical results with a simulation model of the system. Based on results of experiments with the analytical model, we provide the maximum number of packets in a single frame for which packet aggregation minimizes the average total delay of a packet for various system loads and sizes of the packet header. It is numerically shown that when the load is high, the higher the variability of the packet service time, the higher the maximum allowed number of packets in the frame should be to achieve the minimum average total packet delay. On the other hand, the impact of the variability of the packet service time is insignificant when the system load is moderate or low.

It is generally believed that the queueing behavior of an arrival process is most sensitive to its first and second order statistics. In this paper, we show that this is not generally true. We consider the queueing behavior of two classes of sources. The first class is the superposition of multiple discrete autoregressive sources of order 1 (referred to as DAR(1) sources), and the second class is a single DAR(1) source having the same first and second order statistics as the superposed source. In particular, we show that in the homogeneous case, the mean queue lengths of the two models are identical, but the queue length variances of the two models are significantly different depending on the correlation of individual sources.

The paper considers a general class of discrete time systems with batch arrivals and departures. Such models appear frequently in the teletraffic analysis of computer and communications networks. Our arrival models are assumed to be quite general. They could be independent and identically distributed (i.i.d.) in successive slots, periodic, Markovian, or described by the moving average time-series model, etc. Our solution framework is novel and unifying and it uses a combination of multidimensional generating functions and combinatorial analysis utilizing extensions of classical ballot theorems. In general, we provide an explicit analytical expression as an infinite sum to obtain the system stationary probability distribution avoiding classical root-finding methods, matrix analytical methodologies, and spectral decomposition approaches. We provide a number of analytical and numerical examples including: i.i.d. models with Poisson and Binomial arrivals; multiserver queueing systems fed by Markovian sources; queues fed with a discrete moving average source of the first and second order; an i.i.d. discrete Pareto batch arrival model. Closed-form analytical expressions are obtained for the stationary distribution of the system queue lengths and numerical examples are also provided when appropriate.

We consider the buffer requirement for a shared memory buffer arising in an ingress MPLS (multiprotocol label switching) LER (label edge router) system. The buffer is divided into virtual queues, each of which is assigned to provide a guaranteed IP service. In such a system, strong correlation between the packet interarrival times and the service times exists in each virtual queue since each packet arriving through a link with finite bandwidth is transmitted only after the system receives the entire packet. We provide a framework, including an accurate analytical model and its solution, to compute the queue length distribution for each virtual queue and the total buffer requirement for the shared memory buffer in the MPLS LER system supporting multiple guaranteed IP services simultaneously. Some numerical results on the buffer requirement and the impact of correlation on the performance are considered.

We focus on correlated queues where service and inter-arrival times are strongly correlated, and the input and output link speeds are the same. We present an analytical method to derive the LST (Laplace Stieltjes transform) of the (actual) waiting time distribution. To investigate the effect of correlation between service and inter-arrival times on the system performance, we consider a counterpart GI/G/1 queue where inter-arrival time and service time distributions are the same as in our correlated system, but they are independent. Some numerical examples are provided to show that such correlations have significant impact on the system performance.

We discuss scheduling policies in wireless networks with fading channels. A utility function that takes both the communication throughput and the transmission delay into account is defined. A dynamic programming optimization method is used to obtain the optimal scheduling policy which explores the channel dynamics and gets a reasonable trade-off between the communication throughput and the packet transmission delay. A near-optimal solution is also presented to deal with problems with large state space. Through simulation results, we show that our policy can improve the performance in both aspects of throughput and transmission delay, compared to the well-known weighted round-robin scheme which does not consider channel dynamics.

We develop a numerically stable algorithm for the solution of a general fluid-flow model in steady-state. The fluid dynamics is modulated by a semi-Markov process, with phase-type distributions for the sojourn times. We use an algorithmic solution to examine the impact of variance in the case of homogeneous on-off sources, and differences between the infinite and finite buffer case. The need for the complete distribution of the buffer is demonstrated through analysis of two existing approximations, which perform unsatisfactorily. Our numerical results demonstrate the robustness of the numerical algorithm; we compute both the cumulative distribution functions (CDF) and the moments of the process, over a wide range of time-scales and system parameters.

This paper considers a general class of discrete time systems with batch arrivals and departures. Such models appear frequently in the teletraffic analysis of computer and communications networks. Our arrival models are assumed to be quite general. They could be independent and identically distributed (i.i.d) in successive slots, be periodic, be Markovian or described by the moving average time-series model, etc. Our solution framework is novel and unifying. It uses a combination of multi-dimensional generating functions and combinatorial analysis using extensions of classical ballot theorems. In general, we provide an explicit analytical expression as an infinite sum to obtain the system stationary probability distribution avoiding classical root finding methods, matrix analytical methodologies and finally spectral decomposition approaches. We provide a number of analytical and numerical examples including a simple multi-server model with i.i.d arrivals, an ATM multiplexer fed by a (random) number of periodic sources, and a new example considering the discrete moving average model for the arrival process where a simple closed-form expression for the stationary distribution of the system queue lengths is provided.

We consider combined M/G/1-G/M/1 type Markov chains with block-structured transition. It is assumed that all the blocks are generated with rational generating matrices. We provide an algorithmic approach to find the stationary probability distribution based on well-known/concepts in linear system theory. These chains arise in the (correlated) G/G/1 queueing systems and known structured Markov chains such as canonical and non-canonical M/G/1 and G/M/1 types which frequently arising in teletraffic analysis of computer and communications networks are special cases. We provide a truncation-free algorithmic solution in a simple geometric form of the the stationary probability vector of the chain taking full advantage of the rational generating matrices.

In this paper we present a multi-cell analytic model for multi-class cellular networks. We investigate the effects subscriber mobility has on bandwidth control strategies when the network supports multiple classes of subscribers having different bandwidth requirements. We introduce control strategies from non-mobile networks and examine them in a mobile environment. The expressions for call blocking using these control strategies have product form solutions. This allows us to develop a multi-cell, multi-class, model by generalizing on the Erlang fixed point approximation using generalized multi-rate, multi-class, Erlang loss formulas for each class of traffic. We produce expressions for originating calls lost, hand-off calls lost, forced-termination, and mean channel occupancy for each class of traffic in each cell for different control strategies. The multicell analytic model allows us to investigate the effects of asymmetric loads and mobility patterns in the network. The analytic results are supported by simulation.

In this paper we present an analytical model for micro- and pico-cell wireless networks for any arbitrary topology in a high mobility feedforward environment. We introduce an approximation technique which uses a single-cell decomposition analysis which incorporates moment matching of handoff processes into the cell. The approximation technique can provide close approximations for non-Poisson arrival traffic and it is easily parallelized. Performance measures such as new calls blocked, handoff calls lost, and forced termination are derived for any general independent call arrival distribution in a heterogeneous traffic environment. We produce some numerical examples for some simple topologies with varying mobility for several call arrival distributions and compare our results to those from simulation studies.

In this paper, we introduce and analyze a new cut-off priority scheme which provides a better grade-of-service to hand-off traffic while maintaining high throughput for the originating calls. A hysteresis control is used for additional robustness. The system model is found to have a general level-dependent quasi-birth-and-death (QBD) structure. An efficient solution methodology is used taking full advantage of the problem structure. Our model extends, generalizes and unifies the existing models for cut-off priority schemes in wireless cellular networks.

In this paper we introduce a general class of level-dependent quasi-birth-and-death (QBD) processes and their stationary solution. We obtain the complete characterization of their fundamental matrices in terms of minimal non-negative solution of the number of matrix quadratic equations. Our results provides a mixed-geometric solution for the stationary solution of level-dependent chains. Applications in overload control in communication networks are also discussed.

Constant bit rate (CBR) traffic is expected to be an important source of traffic in high-speed networks. Such sources may have stringent delay and loss requirements and in many cases, they should be delivered exactly as they were generated. A simple delay priority scheme will bound the cell delay and jitter for CBR flows, so that in the network switches, CBR traffic will only compete with other CBR traffic in the networks. In this paper, we will consider a slotted queue at a typical (intermediate) node in such an environment. The cell arrival process of each source is characterized by a dispersed periodic arrival process (DPAP), the cells of which are assumed to arrive periodically and distribute randomly within the period. We provide an exact analysis of buffer fill and delay distribution using Ballot Theorems. Another generalized source model, the dispersed batch periodic arrival process (DBPAP) is also investigated. A DBPAP source is assumed to have a number of batches of cell arrivals and the batches position randomly in the period. This work shows that the traditional Markovian approximation models may grossly overestimate the buffer fill and delay, unless the number of sources is very large.

Discrete time queueing systems have gained attention recently due to their applications in the performance analysis of ATM and other systems. In this paper, we analyze generic discrete-time queueing models with general distribution for batch arrivals and departures. Our models allow correlation and distributions with arbitrary rational probability generating functions. Our solution methodology is significantly different, compared with the traditional methods. We provide a state-space representation of the model resulting in an exact simple matrix geometric solution of the system probability vector. Our approach is algorithmic, numerically robust and efficient. Applications in ATM systems and classical (discrete) G/G/1 queues with semi-Markovian arrival and departure processes are immediate and are discussed.

In this paper we present an analytical model for microcellular and picocellular wireless networks for any arbitrary topology in a high-mobility environment. We introduce an approximation technique which uses a single-cell decomposition analysis which incorporates moment matching of hand-off processes into the cell. The approximation technique is novel in that it can provide close approximations for non-Poisson arrival traffic and it is easily parallelized. Performance measures such as new calls blocked and hand-off calls lost are presented for any general call arrival distribution in a non-homogeneous traffic environment. We produce some numerical examples for some simple topologies with varying mobility for several call arrival distributions and compare our results to those from simulation studies.

We present a model for soft, hand-off in wireless cellular networks. In such networks, due to overlapping cells, hand-offs are not instantaneous and multiple channels may be occupied by a single mobile for a non-zero freeze time period.

We consider the performance analysis of an ATM multiplexer supporting both delay sensitive (e.g. silence detected voice) and loss sensitive (e,g. data) traffic flows. The delay sensitive cells are stored in a finite (relatively small) buffer and are given service priority over loss sensitive cells in each slot. In our formulation, we allow both classes to have a general (Markovian) correlation structure. A simple matrix geometric solution for the state probability of the system is provided allowing simple computation of any desired performance metric such as loss probability and buffer requirements of high and low priority classes, respectively. We provide number of numerical results. In particular, we consider the superposition of Bernoulli on-off sources often used to model silence detected packetized voice-like traffic as a high priority class. The example for low priority traffic is taken to be i.i.d batches of geometric distribution and two-state correlated batches. The numerical results show that both the loss behavior and the buffer requirements are quite sensitive to the (average) burst size of high priority traffic. In particular, it is demonstrated that for any level of utilization, the buffer requirements for both classes appear to be almost proportional to the burst size of the high priority class. The performance of low priority traffic is shown to be quite sensitive to its correlation structure. This class suffers most if both low and high priority traffic are very bursty.

Constant bit rate (CBR) traffic is expected to be an important traffic source in high-speed networks. Such sources usually have stringent delay and loss requirements and in many cases they should be delivered exactly as they were generated. A simple delay priority scheme in the network nodes will bound the delay and delay jitter for CBR traffic so that the CBR flows with stringent QoS will only compete with similar traffic flows within the network. We extend the work of Privalov and Sohraby (see IEEE/ACM Trans. on Networking, 1998) to a networking environment and provide the end-to-end jitter analysis of feed-forward connection-oriented networks supporting multiplexed CBR connections. The impact of the traffic mix in each node and the number of nodes in the network on the end-to-end jitter of individual flows are examined.

Constant bit rate (CBR) traffic is expected to be a major source of traffic in high-speed networks. Such sources may have stringent delay and loss requirements and in many cases, they should be delivered exactly as they were generated. A simple delay priority scheme will bound the cell delay and jitter for CBR streams, so that in the network switches, CBR traffic will only compete with other CBR traffic in the networks. We consider a multiplexor in such an environment. We provide an exact analysis of the jitter process in the homogeneous case. In this case, we obtain the complete characterization of the jitter process showing the inaccuracies of the existing results. Our results indicate that the jitter variance is bounded and never exceeds the constant /sup 2///sub 3/ slot. It is also shown that the per-stream successive cell inter-departures times are negatively correlated with the lag 1 correlation of - 1/2 . Higher order correlation coefficients are shown to be zero. Simple asymptotic results on per-stream behavior are also provided when the number of CBR streams is considered large. In the heterogeneous case, we bound the jitter distribution and moments. Simple results are provided for the computation of the bound on the jitter variance for any mix of CBR streams in this case. It is shown that streams with a low rate (large period) do experience little jitter variance. However, the jitter variance for the high-rate streams could be quite substantial.

We present an algorithmic approach to find the stationary probability distribution of M/G/1-type Markov chains which arise frequently in performance analysis of computer and communication networks. The approach unifies finite- and infinite-level Markov chains of this type through a generalized state-space representation for the probability generating function of the stationary solution. When the underlying probability generating matrices are rational, the solution vector for level k, x/sub k/, is shown to be in the matrix-geometric form x/sub k+1/=gF/sup k/H, k/spl ges/0, for the infinite-level case, whereas it takes the modified form x/sub k+1/=g/sub 1/F/sup k//sub 1/H/sub 1/+g/sub 2/F/sup K-k-1//sub 2/H/sub 2/, 0/spl les/k/spl les/K, for the finite-level case. The matrix parameters in the above two expressions can be obtained by decomposing the generalized system into forward and backward subsystems, or, equivalently, by finding bases for certain generalized invariant subspaces of a regular pencil /spl lambda/E-A. We note that the computation of such bases can efficiently be carried out using advanced numerical linear algebra techniques including matrix-sign function iterations with quadratic convergence rates or ordered generalized Schur decomposition. The simplicity of the matrix-geometric form of the solution allows one to obtain various performance measures of interest easily, e.g., overflow probabilities and the moments of the level distribution, which is a significant advantage over conventional recursive methods.

Constant bit-rate (CBR) traffic is expected to be a major source of traffic in high-speed networks. Such sources may have stringent delay and loss requirements and, in many cases, they should be delivered exactly as they were generated. A simple delay priority scheme will bound the cell delay and jitter for CBR streams so that in the network switches CBR traffic will only compete with other CBR traffic in the networks, In this paper we consider a multiplexor in such an environment. We provide an exact analysis of the jitter process in the homogeneous case. In this case we obtain the complete characterization of the jitter process showing the inaccuracies of the existing results. Our results indicate that jitter variance is bounded and never exceeds the constant 2/3 slot. It is also shown that the per-stream successive cell interdeparture times are negatively correlated with the lag 1 correlation of -1/2. Higher order correlation coefficients are shown to be zero. Simple asymptotic results on per-stream behavior are also provided when the number of CBR streams is considered large. In the heterogeneous case we bound the jitter distribution and moments. Simple results are provided for the computation of the bound on the jitter variance for any mix of CBR streams in this case. It is shown that streams with a low rate (large period) do experience little jitter variance. However, the jitter variance for the high-rate streams could be quite substantial.

In this paper, we present a novel algorithmic approach, the hybrid matrix geometric/invariant subspace method, for finding the stationary probability distribution of the finite quasi-birth-death (QBD) process which arises in performance analysis of computer and communication systems. Assuming that the QBD state space is defined in two dimensions with m phases and K+1 levels, the solution vector for level k, /spl pi//sub k/, 0/spl les/k/spl les/K is shown to be in a modified matrix geometric form /spl pi//sub k/=/spl upsi//sub 1/R/sub 1//sup k/+/spl upsi//sub 2/R/sub 2//sup K-k/ where R/sub 1/ and R/sub 2/ are certain solutions to two nonlinear matrix equations and /spl upsi//sub 1/ and /spl upsi//sub 2/ are vectors to be determined using the boundary conditions. We show that the matrix geometric factors R/sub 1/ and R/sub 2/ can simultaneously be obtained independently of K via finding the sign function of a real matrix by an iterative algorithm with quadratic convergence rates. The time complexity of obtaining the coefficient vectors /spl upsi//sub 1/ and /spl upsi//sub 2/ is shown to be O(m/sup 3/ log/sub 2/ K) which indicates that the contribution of the number of levels on the overall algorithm is minimal. Besides the numerical efficiency, the proposed method is numerically stable and in the limiting case of K/spl rarr//spl infin/, it is shown to yield the well-known matrix geometric solution /spl pi//sub k/=/spl pi//sub 0/R/sub 1//sup k/ for infinite QBD chain.

We provide simple techniques for estimating the end-to-end jitter incurred by a periodic traffic in an asynchronous transfer mode (ATM) network. Our analysis is based on the careful examination of light and heavy traffic behavior of jitter incurred to a tagged renewal stream in a single node. Our results indicate that, in the heavy traffic as the number of nodes increases, the jitter distribution approaches to a limiting distribution which only depends on the behavior of the background traffic. We provide the functional equation satisfying this limit which bounds the moments of the jitter for arbitrary level of traffic. A simple approximation method based on the heavy and light traffic analysis of the jitter process is also provided and the results is supported by extensive simulation.

The main motivation for developing the MetaRing architecture was to increase the throughput of a ring-based local area network beyond its single link capacity by means of spatial bandwidth reuse. We describe and evaluate a protocol for integrating two types of traffic on the MetaRing architecture. Synchronous (reserved or real-time) traffic which is periodic and requires a connection set-up and will have guaranteed bandwidth and bounded delay, and asynchronous or bursty traffic with no real-time constraints that can use the remainder of the bandwidth in a fair manner. The integration mechanism is functionally equivalent to the timed-token function in FDDI, which is a shared media ring protocol. Simulation results are also presented to show the effects of the fairness and flow control signals on the performance of the network.

A large class of teletraffic analysis problems encountered in communication networks are based on Markov chains of M/G/1 and G/M/1 type, the study of which require numerically efficient and reliable algorithms to solve the nonlinear matrix equations arising in such chains. The traditional transform approach to solve these chains which requires root finding is known to cause problems when some roots are close or identical. The alternative iterative schemes based on matrix analytic methods have in general low linear convergence rates yielding a computation time bottleneck in solving large-scale probability models. We develop a novel algebraic theory for the solution of these chains based on which we propose numerically efficient algorithms. The key to our approach is an invariant subspace computation implemented using the matrix sign function iterations. These algorithms have high convergence rates unlike the linear convergence rates of existing algorithms, they are amenable to parallelization and can easily be implemented using standard linear algebra software packages.

This paper shows how to design an ATM network, for real-time traffic, such that under full network load (i) the maximum delay of a low-rate voice connection is minimized, (ii) the delay uncertainty or jitter is a fixed network parameter, and (iii) the required buffer sizes (inside the network) to ensure loss-free routing is minimized. In addition, this design does not exclude the integration of other classes of traffic, such as connectionless, which have lower priority. The isochronous timing information is used only for regulating and pacing the traffic forwarded inside the network rather than for routing as in traditional circuit switching networks. This means that an ATM cell is sent from one switch to another not at a very specific time but within a time frame of a relatively long duration as compared to the cell transmission time. The routing of cells of each connection is based on VCI and VPI, and as a result, timing errors do not affect the ATM routing. Analytical and simulation results are presented, which demonstrate the effectiveness of this switching approach.>

The authors formulate and analyse the jitter process in an ATM environment. The jitter analysis is presented for a tagged renewal stream. The queueing model consists of the superposition of the tagged renewal stream and background traffic. In the case of periodic tagged stream, the correlated background traffic is also considered. A solution methodology is developed which can be utilized in solving a large class of problems. They investigate the impact of various traffic parameters (e.g. the background traffic load and burstiness, the interarrival time of the renewal stream, etc.) on the jitter of the tagged stream. Numerical examples provide insight into the behavior of the system. They observe that the variance of the jitter behaves (almost) linearly with the variance of the background traffic. Some interesting heavy traffic results are also provided when the background traffic consists of number of identical two state ON-OFF sources.>

The authors provide sample techniques for estimating the end-to-end jitter incurred to a periodic traffic in an ATM network. The analysis is based on carefully examining the light and heavy traffic behavior of jitter incurred to a general tagged renewal stream in a single node. The results indicate that for any number of nodes, the jitter variance is almost proportional to the variance of the background traffic competing for resources with the tagged stream. They also find that in general, as the number of nodes increases, the jitter distribution approaches a limit. In the heavy traffic, they provide the functional equation satisfying this limit which readily gives all the moments of the jitter in closed form for large number of nodes in the network.>

Provides an analysis of a rate-based access control scheme in high speed environments based on a buffered leaky bucket algorithm. The analysis is carried out in discrete time which is representative of an ATM environment. For the cell arrivals to the leaky bucket the authors consider a general discrete Markovian arrival process which models bursty and modulated sources. The key of the analysis is the introduction of the deficit junction that allows the reduction of the original problem to a more standard discrete time queueing system with the same arrival process. As an important special case, the detailed analysis of the binary Markov source throttled by such rate-based access control schemes is presented. Along with explicit recursions for computation of state probabilities and simple characterisation of the asymptotic behavior of the queue build up, some guidelines for the parameter selection of these schemes are provided. The results indicate that for sources with relatively large active periods, for an acceptable grade-of-service at the input queue, the token generation rate should be chosen to be close to the peak rate of the source, and increasing the bucket size of the leaky bucket does not improve substantially the performance at the input queue.>

A general theory of on-off sources is provided. The basic source model is characterized by alternating independent on (burst) and off (silence) periods, which may have general distributions. Other more complex sources are constructed, and their behavior is characterized in terms of the basic source model. Heterogeneous and homogeneous statistical multiplexers fed by such sources are considered. In the heterogeneous environment, a simple result on the tail behavior of the multiplexer queue length distribution in the heavy traffic is provided. In the homogeneous environment, asymptotic results on the tail behavior of the queue length distribution are provided for all levels of utilization. The results for the heterogeneous environment suggest a new call admission control policy for general on-off sources in high-speed networks, which depends only on the first two moments of the on and off periods of individual sources and their respective peak rates.>

In many applications certain parameters of a system should be set on the basis of some large percentiles of a delay random variable, for which the characteristics may not be known or may change slowly with time. Assuming that sample values of delays are available sequentially, the authors obtain a simple algorithm to track two key statistical characteristics of the delay. Any high percentile then may be approximated as a simple linear function of these parameters. The approach is based on a quasi-exponential assumption concerning the delays.>

The authors present an analysis of a rate-based access control mechanism for high-speed networks that is based on the buffered leaky bucket scheme. The analysis assumes a discrete time environment representative of asynchronous transfer mode (ATM) networks and a batch arrival process that captures cell arrivals generated by segmentation of large user packets or superposition of a number of arrival streams. The solution method is based on matrix analytic techniques, but the particular structure of the system allowed for a number of important improvements. It is shown that the problem can be partitioned and that the matrix G, central to the matrix analytic technique, can be computed using exact recursive procedures instead of the traditional iterative approach. These improvements not only extend the range of systems that can be handled, but also eliminate computational issues such as convergence rate and stopping criterion.>

The author combines a heterogeneous statistical multiplexer in heavy traffic with different characteristics in discrete time which is representative of the asynchronous transfer mode (ATM) environment at the cell level. An exact formulation of the queuing model for the multiplexer is presented. Using spectral decomposition method and asymptotic analysis, it is shown that for fixed source average utilization and peak rate, as the burst size of the individual sources increase the tail behavior of the distribution of the number of cells queued in the multiplexer has a simple characterization. This characterization provides a simple approximation of the queuing behavior of the multiplexer, where the impact of each source is quite evident. The accuracy of this approximation is examined. Some applications are considered where both buffer sizing and admission control are discussed.>

Previous work by the authors (See Proceedings Conf. on Information Sciences and Systems, Baltimore, USA, 1990) where the spectral decomposition method was used for the transient analysis of a single-server queue is generalized. For the arrival process a general discrete-time Markovian batch arrival process is assumed, where the batch size distribution of the arrivals in successive slots is governed by a N-state discrete-time Markov chain. It is shown that once the N eigenvalues of the probability generating matrix of the arrival process are obtained, the complete solution in the transform domain may be given. Using the complex analysis technique and Cauchy's integral formula, an efficient numerical method is presented for the calculation of a few performance measures. The numerical method is generalized to the situations where the superpositions of a number of independent arrival sources are fed to the queue. It is shown that the numerical complexity are fed to the queue. It is shown that the numerical complexity of obtaining the transient solution in this case can be substantially reduced by using an approach based on the Kronecker product.>

The analysis of a rate-based access control scheme in high speed environments that is based on a buffered leaky bucket algorithm is presented. The analysis is carried out in discrete time, which is representative of asynchronous transfer mode environments. For the cell arrivals to the leaky bucket, a general discrete Markovian arrival process is considered which models bursty and correlated sources. The introduction of the deficit function allows the reduction of the original problem to a more standard discrete time queuing system with the same arrival process. As an important special case, the detailed analysis of the binary Markov source throttled by such rate-based access control schemes is presented. Along with explicit recursions for computation of state probabilities and simple characterization of the asymptotic behavior of the queue buildup, some guidelines for the parameter selection of these schemes is provided.>

The authors suggest and investigate a general input congestion control scheme that takes into account a broad spectrum of network issues. As a preventive congestion control strategy, a leaky-bucket-type scheme operating on a session basis that limits the session's average rate and the burstiness is proposed. This restrictive control is combined with an optimistic bandwidth usage scheme which works by marking packets into two different colors, green and red. The packets are marked so that the average green packet rate entering the network is at the reserved average rate. The average red packet rate represents traffic in excess of this guaranteed average rate and is sent to further utilize unused bandwidth in the network. Both types of packets are further filtered by a spacer which limits the peak rate at which the packets enter the network. The marked packets are then sent into the network, where they are treated according to their color, using at each intermediate node a simple threshold policy.>

Carrier sense multiple-access (CSMA) protocols are widely used in local area networks (LAN's) to control access to a shared communications channel such as a coaxial cable or radio frequency band. CSMA protocols are designed to exploit the property that the signal propagation time across the LAN is much smaller than the packet transmission time. Consequently, their performance depends on the exact timing of a sequence of asynchronous events originating at different points in the network. Previous models of CSMA protocols have not captured this essential space-time characteristic. Instead, the system has been reduced to a 1-dimensional model (i.e., a sequence of events on a single time line) by assuming either that events are synchronous (i.e., "slotted" operation of the protocol) or that all stations are mutually equidistant (so it can be assumed that each station's time line is identical). The novelty in our work is to describe the system state in terms of an (N + 1)-dimensional "ribbon" of space-time, allowing us to faithfully model the exact timings of events for LAN's where the stations are distributed over a fully connected region inN-space. For example, an Ethernet-like "bus" network can be viewed as a 1-dimensional LAN, a terrestrial packet radio network can be viewed as a 2dimensional LAN, and so on. First we highlight some of the key properties exhibited by such a model in the general case, including the notion of an embedded Markovian sequence of "idle points," and the decomposition of the space-time ribbon into cycles (each of which can be further decomposed into a number of "regions"). Then we present extensive results for the interesting special case of a 1-dimensional LAN, i.e., an Ethernet-like "bus" network. Our results show that previous models of bus LAN's can significantly underestimate their performance.

We present a brief and simple analysis of asynchronous (unslotted) 1-Persistent CSMA protocols in the worst-case star topology. The purpose is two-fold. First, we give a simple approach based on an embedded Markov chain at the beginning of subbusy periods that greatly simplifies the analysis. And second, using the above approach we give the correct analysis for 1-Persistent CSMA with collision detection, since the only available analysis of the present model [1] is in error.