next up previous
Next: Bibliography

Research Proposal

Queueing systems have important applications in various fields like production management, inventory control, management of fluid reservoirs, population dynamics, genetics and chemical reactions. Computer communication systems constitute one of the principle areas of applications of queueing models. A basic problem in the dimensioning and performance evaluation of telecommunication network elements is the computation of the buffer occupancy and waiting time distribution of a single/multi-server queue, whose input consists of a superposition of processes modelling traffic streams. Several main classes of traffic models commonly used in traffic modelling exist, e.g., renewal, Markov based, fluid, autoregressive, self-similar etc. A nice survey of these classes can be found in [18]. This research proposal concentrates in modelling computer and communication networks using queueing models and finding approximate solutions for the performance measures using rational approximation theory and in fine tuning the results.

Variable bit rate communications with real time constraints in general, and video communication services (video phone, video conferencing, television distribution) in particular, are expected to be a major class of services provided by the future Quality of Service (QoS) enabled Internet. This network must offer a high degree of flexibility, together with efficiency in resource consumption, by sharing the same network resources (bandwidth and buffers) among several connections with different characteristics (bandwidth, peak bit rate, correlation) requiring different QoS level guarantees. The introduction of statistical multiplexing techniques, such as provided in ATM networks, offers the capability to efficiently support variable bit rate connections by taking advantage of the variability of the bandwidth requirements of individual connections. In this way, connections share a link, of capacity less than the sum of the individual peak bit rates, achieving a more or less significant multiplexing gain, while guaranteeing the often stringent QoS requirements with respect to packet loss, end-to-end packet delay and delay jitter.

In a multiplexer network, all information such as voice, data, and video is segmented into fixed-size packets, called cells. The share of common network resources among individual connections is made on a statistical multiplexing basis. The performance analysis of a statistical multiplexer whose input consists of a superposition of several packetized sources is in general difficult. This difficulty is mostly due to the number of arrivals in adjacent time intervals possessing a positive correlation. A common approach is to approximate this complex nonrenewal input process by an analytically tractable one.

Neuts [27] introduced a versatile Markovian point process, called N-process, which is analytically tractable and which is convenient for approximation of these complicated nonrenewal processes. This class of processes includes the MMPP, PH-renewal processes and a wide range of other processes as special cases, e.g., see [16], [21], [25]. Lucantoni [24] introduced the Batch Markovian Arrival Process (BMAP), which is equivalent to the $N$-process but which has a simpler unifying notation. For a BMAP, arrivals are allowed to occur in batches where different types of arrivals may have different batch size distributions. If batch arrivals are not allowed, BMAP reduced to the Markovian Arrival Process (MAP) which is still a rich class of processes that contains MMPP and PH-renewal processes as subcases. Quasi-Birth-and-Death (QBD) Markov chains are special cases of M/G/1 type Markov chains and include the MAP/PH/1 queue as a subcase. Latouche and Ramaswami [22] have presented QBD chains with a quadratic convergence rate.

Many forms of data, voice and image based communications in multiplexer networks are expected to have an on-off type behaviour. On-off sources generate traffic during activity periods alternating with silence period during which there is no traffic generation. The cell arrival process form an individual on-off source may be highly complicated and exact analysis of systems offered with a superposition of such sources is generally difficult. One basic approach is to approximate the superposition by fitting certain parameters of the original process to those of a 2-state MMPP, a subcase of the MAP, proposed by Heffes and Lucantoni [16]. In [17], the individual on-off source is characterized by an Interrupted Poisson Process (IPP) which is indeed a special case of the MMPP. The MMPP is also used to model packetized video traffic by Saito et al. [30] and Skelly, Schwartz and Dixit [31]. In [35], the individual on-off sources is characterized by an Interrupted Bernoulli Process (IBP).

In multiplexer models, packets are of fixed length and the buffering memory in switching nodes is limited to a finite number of cells. In such models with finite buffer, a variety of techniques have been developed in recent years to assess the multiplexing gain. These techniques are based on the exact analysis, approximate analysis and simulation. Considerable work has been done on the development of analytical techniques for evaluating packet loss probabilities, also called cell loss probabilities (CLP) [4,19,26,34].

An algorithmic procedure to calculate the delay distribution of a type $K$ customer in a FCFS MMAP[K]/PH[K]/1 queue is proposed in [32]. This work has been extended to compute the delay distribution of impatient customers in a discrete time D-MAP/PH/1 queue with age-dependent service times in [33]. Queueing systems of this type have obvious applications in telecommunication systems. For instance, packets belonging to real time services become worthless to a receiver if they do not arrive before a certain deadline, therefore, these packets can be modelled as impatient customers. Moreover, packet video receivers may also vary the playout time of a video frame based on its age.

In the analysis and design of multiplexer models using queueing models, difficulties often arise due to the so-called ``curse of dimensionality'' - prohibitive computational requirements for large size systems. When the system is small, we can often get accurate results. As the system size grows, the computational burdens become overwhelming. Examples among many of such systems are: computer communication networks consisting of hundreds of nodes; multiplexers/switches in B-ISDN having large buffer space; multiprocessor computing systems having thousands of processors; multimedia (voice, video data) communication networks consisting of many traffic sources with diverse characteristics; and models using phase type distributions involving large or infinite dimensional Markov chains. The situation looks so hopeless that research efforts in analytical modeling of such systems are fading away. Simulation has become the standard approach in the research literature to justify new designs. The curse of dimensionality becomes a major difficulty in the analysis and design of many computer/communication systems. Hence, considerable attention has been paid to the development of techniques that provide approximate estimates for performance metrics. These techniques include methods which approximate the arrival process by fluid models [1].

In the last decade, the literature on queueing theory has paid lot of attention to Markov-modulated fluid models. In these models, a fluid buffer is either filled or depleted, or both, at rates which are determined by the current state of a background Markov process, also called Markovian random environment. Such models are widely used in modelling many communication and computer systems (see, for example, [1], [13], [3], [20], [28], [29]).

Monte Carlo simulation is also used to compute the CLP. If the desired performance measure, e.g., CLP, is in the range of $10^{-12}$ to $10^{-6}$, depending on the kind of service, it is, however, computationally impossible to use the conventional Monte Carlo simulation. A simulation technique called Importance Sampling (IS) can speed up simulations involving rare events such as CLP [5]. However, because of the complicated nature of multiplexer queueing models, applying the IS technique is not straightforward.

In this project work, we propose to apply univariate/multivariate rational interpolation techniques to tackle the problem from the standpoint of systems analysis. A large number of analysis and design problems involve performance measures that are only defined on positive integers (let us denote it by $n$), which usually represent the sizes of the systems. In this project, we focus on such integer parameterized performance functions, $f(n)$ which could be the CLP or the waiting time distribution of the packets in the switch. These techniques are based on information regarding the performance values of down-sized systems, i.e., values of $f(n)$ when $n$ is small, and the asymptotic properties of $f(n)$ as $n$ goes to infinity. The performance values of down-sized systems can be obtained either by analytic methods or from simulations.

In the past decade, an impressive amount of knowledge has been accumulated regarding the qualitative behaviour of $f(n)$, such as monotonicity, convexity, boundedness and the asymptotic behaviour of performance functions for computer/communication systems, or, general stochastic discrete event systems (DES) [14]. It is clear that performance functions for many computer/communication systems have provable nice qualitative properties. Pathological cases are rare in practical systems.

It has been proved that for infinite M/G/1-type queues, the buffer overflow probability decays exponentially [12]. In [23], the authors have shown that for Markov modulated queueing models with multi-server and infinite buffer, the queue length distribution has exponential bounds. In [2], the author has studied the exponential decay of the loss probability of the finite MAP/G/1/K queue. In all these papers, the exponential decay rate is studied by providing some conditions on the stationary queue length distribution.

The essence of our work is that we propose to take advantage of such properties to help evaluate the quantitative behaviour of the performance functions. This approach is motivated by the earlier work on the Padé approximants applied to queueing networks [15] and on rational interpolants applied to ATM multiplexers [35].

In summary, our approach is based on the following observations:

  1. Model the given computer/communication system using queueing theory.
  2. Computing the values of the performance functions of the system is computationally feasible (either using queueing models or via Monte Carlo simulation for more complicated models) when the system size is small. This computation becomes impractical only when the system size becomes large. The values corresponding to small system size will be used as support points to construct an appropriate rational approximant.
  3. The performance function, as a function of system size, exhibits nice qualitative properties. It is often provably monotonic, convex, etc.
  4. The asymptotic properties of the performance function when the system size goes to infinity are often obtainable via analyzing the system itself.

For functions having features described above, it is possible to obtain simple rational approximants that are virtually exact for all engineering purposes. In other words, in these situations if we only ask for accurate approximants for large size systems, we can obtain easy solutions to a problem for which exact analysis is impossible.

Oftentimes the exact calculation is not feasible even for small size systems, for example in the case of a multiplexer with more heterogeneous sources. In these cases, the values of the performance measure for small size systems are obtained using simulation, and therefore contain error. This error will cause additional error in rational interpolation. This additional error can be made arbitrarily small by making the error of the values at the support points sufficiently small. This will be done by using the quasi-Monte Carlo method in order to guarantee deterministic convergence.

In [11], the authors have successfully applied the rational interpolation technique to compute packet loss probabilities in multiplexer models. The accuracy of the approach is validated by comparison with both analytical results and simulation results. In rare cases it happens that the poles of the computed rational function disturb the fit of the packet loss probability. In [9], the authors indicate that this can be prevented through an a priori optimal placement of the poles. The location of the poles is determined, indirectly, from the system parameters. Extensive testing illustrates that the new technique is even more efficient than the one proposed in [11], especially in the case of correlation between the packets (such as with more video sources), or high (but realistic) network load.

The extension of univariate interpolation to multivariate interpolation is not trivial since a large degree of freedom in the choice for the numerator and denominator polynomials exists. Only a few multivariate sampling algorithms have been published. One approach to multivariate rational interpolation is based on the accuracy through order principle. With this approach it is possible to write down explicit formulas for the multivariate rational interpolants, to construct a recursive scheme or to find the interpolant as the convergent of a multivariate continued fraction [6]. A second and equivalent approach does not rewrite the interpolation data in a Newton series. Immediately starting from the interpolation conditions determinant formulas, a recursive computation scheme and an interpolating continued fraction are provided in [7]. The later approach is extremely useful if the support points are scattered rather than grid points.

In [8], the authors have successfully applied multivariate rational approximants for multiclass closed queueing networks to compute the normalizing function. This function is the key element of the stationary solution of the network in product form. This function depends on the number of customers in each class of the network. The authors have used multivariate Newton-Padé approximants computed from data for small numbers of customers in each class, to estimate the normalizing function for a larger population in the network.

Expert judgments, generic data, heterogeneous and partial information on the occurrences of events may be sources of the probability assessments. All this source information cannot produce precise probabilities of interest without having to introduce drastic assumptions often of quite an arbitrary nature. This motivates us to work with measured data of the network parameters. This leads to the perturbation analysis of the networks under consideration. It will be done using interval arithmetic. It is proposed to analyze the above discussed networks using interval-arithmetic. Preliminary work in this direction by the author yielded some interesting results already [10].

next up previous
Next: Bibliography
Lenin Bhavanandan 2006-03-28