Analysis of GI/M/s/c queues using uniformisation

We combine uniformisation, a powerful numerical technique for the analysis of continuous time Markov chains, with the Markov chain embedding technique to analyze GI/M/s/c queues. The main steps of the proposed approach are the computation of

• (1)the mixed-Poisson probabilities associated to the number of arrival epochs in the uniformising Poisson process between consecutive customer arrivals to the system; and
• (2)the conditional embedded uniformised transition probabilities of the number of customers in the queueing system immediately before customer arrivals to the system.

To show the performance of the approach, we analyze queues with Pareto interarrival times using a stable recursion for the associated mixed-Poisson probabilities whose computation time is linear in the number of computed coefficients. The results for queues with Pareto interarrival times are compared with those obtained for queues with other interarrival time distributions, including exponential, Erlang, uniform and deterministic interarrival times. The obtained results show that much higher loss probabilities and mean waiting times in queue may be obtained for queues with Pareto interarrival times than for queues with the other mentioned interarrival time distributions, specially for small traffic intensities.     

无线数据网络中的自相似性

在研究通信网络的流量控制及网络性能的时候．业务源模型是一个十分重要的组成部分。传统的业务流模型大多是基于泊松或贝努力过程的．而这些模型表现出的行为与实际网络的测量结果不符。大量业务的测量表明：在这些业务中普遍存在着自相似性(即长相关性)。采用自相似建模表征业务到达过程的长时相关特性具有较高的精度．其中Hurst系数是表征业务突发特性的重要参数。经研究发现，无线网络中仍然存在自相似性。考察CDPD(蜂窝数字分组数据网)的特性，发现自相似性对网络的排队性能有着显著的影响．可以通过增加队列长度，加大缓冲存储空间，实现降低延时。     

基于自相似流量的一种新的队列管理算法

鉴于网络流量的自相似特性,结合应对该特性可采用的两种主要措施,提出了一种应对该特性的一种新的队列管理算法。算法包括两部分,一是缓冲区管理算法,另一是队列调度算法。新算法在缓冲区管理上采用了一种“伪扩充”缓冲区的方法。“伪扩充”维持缓冲区总空间的不变的情况下,按照策略增加一个用于处理自相似突发流量的队列。针对“扩充”后的缓冲区,采用基于静态优先级和轮询的队列调度算法。从理论上分析了,两部分的结合产生的新的队列管理算法在应对自相似突发流量中的有用性。     

自相似业务下拥塞避免机制的实现

传统拥塞避免机制所采用的随机早期检测（Random Early Detection,RED）算法是建立在网络流量按Poisson分布的基础上,因此不适应具有自相似业务流量特征的Internet网。针对自相似业务流量特点,对RED算法进行了改进,提出了一种基于时间间隔的随机早期检测（Based Interval Random Early Detection,BIRED）算法。BIRED算法能够在自相似业务流量特征下,通过控制平均队列长度,避免网络进入拥塞状态。通过仿真比较了BIRED和RED的动态性能,显示了BIRED具有更好的鲁棒性,证明了BIRED比RED、DropTail更能适应自相似业务流量,减小系统负担,有效稳定平均队列长度,改善系统的暂态特性。     

The departure process of an N/G/1 queue

The departure process of an N/G/1 queue is investigated. The arrival process called an N process is a versatile point process and includes, for example, a Markov-modulated Poisson process, which is comprised of models of packetized voice and video traffic arrival processes. The first passage analysis yields LSTs of distributions of the interdeparture times. Emphasis is on the interdeparture times of an N/D/1 queue. Numerical examples show that correlation of interarrival times is likely to be preserved in interdeparture times, and that the departure of a voice packet multiplexer can be expected to be smoothed for a normal load. The result in this paper enables evaluation of the smoothing effect of burst traffic through nodes in Asynchronous Transfer Mode networks.     

A Monte Carlo Approach for ɛ Placement in Fractal-Dimension Calculations for Waveform Graphs

Many diverse and complicated objects of nature and math possess the quality of self-similarity, and algorithms which produce self-similar shapes provide a way for computer graphics to represent natural structures. For a variety of studies in signal processing and shape-characterization, it is useful to compare the structures of many different "objects". Unfortunately, large amounts of computer time are needed as prerequisite for rigorous self-similarity characterization and comparison. The present paper describes a fast computer technique for the characterization of self-similar shapes and signals based upon Monte Carlo methods. The algorithm is specifically designed for digitized input (e.g. pictures, acoustic waveforms, analytic functions) where the self-similarity is not obvious from visual inspection of just a few sample magnifications. A speech waveform graph is used as an example, and additional graphics are included as a visual aid for conceptualizing the Monte Carlo process when applied to speech waveforms.     

Performance Analysis of Discrete-Time Finite-Buffer Batch-Arrival GIX/Geom/1/N Queues

This paper presents the performance analysis of a discrete-time finite-buffer queue with batch input, general interarrival and geometric service times. It is assumed that a batch arriving with size larger than the available buffer is partially accepted and the rest is rejected. The queue is analyzed for early arrival system as well as for late-arrival system with delayed access using both the supplementary variable and imbedded Markov chain techniques. Besides obtaining state probabilities at various epochs and loss probability of a batch as well as of a customer, other performance measures have also been discussed. The waiting time analysis of an arbitrary customer of a batch is also carried out.     

Design of a computerized scheduling system for best rule analysis and control

A Computerized Scheduling System (CSS) for a gear box manufacturing plant has been developed to simulate a specific manufacturing facility and to analyse conditions that identify bottlenecks during the production process. The model, based partly on practical experience and partly on theoretical work, allows the analyst to concentrate on a single entity (such as a job) and the sequence of events and activities that undergoes as it “passes through” the system. The CSS makes use of actual company data regarding individual machines and operators, and incorporates interarrival times, job types, tasks for each job, routings for the different job types and process time for each job type and specific task. Also, the model provides information on output — average total delay in queue, average number in queue, average utilization and average delay in queue. Although the resultant model was constructed for the application on hand, the principles employed can be extended to include procedures encountered in similar manufacturing environments.     

Modelling manufacturing systems: A birth-death approach

An approximation method for modelling a manufacturing system is introduced. The system is considered as a queueing network, where each queue is limited in size, and interarrival and processing times are exponentially distributed. The birth-death approach is considered and an approximation method to reduce the dimension of the model is developed. The results are the marginal probability distribution of the number of units in each queue; other performance indices, such as mean queue lengths, utilizations of the working stations, and throughput can be easily obtained. The general procedure is applied to model, for example, queues in tandem, a split node, and a more complex network of queues. Simulation and, when possible, comparison with the exact solution show an acceptable error level of the proposed method.     

A maximum entropy optimization approach to tandem queues with generalized blocking

We study a general blocking scheme for an open tandem queueing network with finite intermediate buffers. The service time at each node as well as interarrival time at the first node is assumed to be exponentially distributed. The interarrival and service time at each intermediate node of the tandem queue, under the general blocking scheme, depend upon three parameters at each node, namely, the maximum number of raw jobs, the upper limit on the number of finished but blocked jobs and the buffer capacity. This three-parameter analysis was introduced by Cheng and Yao (1993), and was shown, using Monte Carlo simulations, to provide good results. Our analysis is also based on this three-parameter approach, but with a different view. We first decompose the tandem queue into a group of two-node subsystems in order to derive a set of equations for the effective interarrival and service time distributions at each node. Each of these two-node subsystems is treated as a finite capacity queueing system with population size constraints. Then we apply the principle of maximum entropy to evaluate different parameters such as the blocking probabilities, starvation probabilities, etc., of each subsystem. We propose a step-by-step algorithm along with its convergence properties. A comparison of numerical results with the simulation results is also discussed.     

A conservation law based approximate analysis for a class of simultaneous resource possession problems

In this paper we analyze a single server queueing model in which there are two types of jobs, one of which must wait in an external queue until a token is available, and only then may join the service queue. The interarrival times and service requirements for both types of jobs are assumed to be independent and exponentially distributed.

We derive the stability condition for such a model where the service queue discipline is either FCFS (First-Come-First-Serve) or PS (Processor-Sharing). We then propose analytic approximations for the mean waiting times for both types of jobs, relying heavily on the M/G/1 conservation law. Numerical results show that our approximations are very accurate (within a few percent of the simulated results) even when the system is heavily loaded. The approximations are also shown to be asymptotically exact as the number of tokens N → ∞.     

CIPP — a versatile analytical model for VBR traffic

Correlated interarrival time Poisson process (CIPP) has been proposed in Proceedings of the Fifth Biennial Conference on Signal Processing and Communications (SPCOM’99), IISc, Bangalore, July 1999, pp. 43–50; J. Indian Inst. Sci. 79 (3) (1999) 233–249] for modeling both the composite arrival process of packets in broadband networks and the individual video source modeling. The CIPP — a generalization of the Poisson process — is a stationary counting process and is parameterized by correlation parameter ‘ρ’, the degree of correlation in adjacent interarrivals and ‘λ’, the intensity of the process. In this paper, we develop the theory for CIPP/M/1 queue and undertake the performance modeling of statistical multiplexer with VBR video traffic in broadband networks using the CIPP/M/1 queue. We first derive the expressions for stationary distributions for queue length and waiting time in a CIPP/M/1 queue. Then, we derive the queuing performance measures of interest. For reasons of feasibility of theoretical performance modeling and realistic compulsions, we propose a deterministic smoothing with random (geometrically distributed) packet sizes. We simulate a queue with (thus smoothed) VBR video trace data as input to compare with the theoretical performance measures derived above. Experimental results show that the CIPP/M/1 queue models well the statistical multiplexer performance with the real-world MPEG-1 VBR video traffic input.     

Fuzzy random renewal reward process and its applications

This paper studies a renewal reward process with fuzzy random interarrival times and rewards under the ?-independence associated with any continuous Archimedean t-norm ?. The interarrival times and rewards of the renewal reward process are assumed to be positive fuzzy random variables whose fuzzy realizations are ?-independent fuzzy variables. Under these conditions, some limit theorems in mean chance measure are derived for fuzzy random renewal rewards. In the sequel, a fuzzy random renewal reward theorem is proved for the long-run expected reward per unit time of the renewal reward process. The renewal reward theorem obtained in this paper can degenerate to that of stochastic renewal theory. Finally, some application examples are provided to illustrate the utility of the result.     

Random fuzzy delayed renewal processes

In renewal processes, fuzziness and randomness often coexist intrinsically. Based on the random fuzzy theory, a delayed renewal process with random fuzzy interarrival times is proposed in this paper. Relations between the renewal number and interarrival times in such a process are investigated. Useful theorems such as the elementary renewal theorem, the Blackwell renewal theorem and the Smith key renewal theorem in a conventional delayed renewal process are extended to their counterparts for random fuzzy delayed renewal processes.     

无尺度网络的数据包传输元胞自动机模型研究*

为了更真实地模拟网络行为,提出了一种基于无尺度网络的数据包传输元胞自动机模型,模型中通过增加缓存队列大小和提高中心节点的处理速度来减少丢包数,提高网络性能。仿真结果表明,在元胞交互规则的作用下,数据包发送速率,缓存队列大小和丢包数在时间序列上都具有自相似特性,自相似程度呈现负相关;它们在时间序列上是长程相关的,在功率谱图中都具有幂律分布特性,在高频段呈现出白噪声特性。     

基于小波变换与EMD的快速Hurst指数估值

网络业务具有自相似性。为了有效地对自相似数据业务流进行控制、管理与疏导,必须快速获得业务流的Hurst参数。该文通过分析自相似业务流的特性,在研究小波分解、经验模态分解和R/S估值过程的基础上,提出一种快速(数据量每减少50%,估值时间减少85.7%)、高精度的Hurst指数估值方法,可直接用于网络业务的实时监测、调度和路由仲裁。     

A numerical procedure for the selection of the constant interarrival time to a single server queue

We study a single server queue with deterministric arrivals to find the optimal interarrival time. No analytically tractable solution is available, except in the particular D/M/1 case, but under the assumption of a phase type service time distribution, the model has a tractable algorithmic solution.

The purpose of this paper is to present the algorithm for the D/PH/1 queue and to demonstrate its implementation through interactive computation. The algorithm provides enough information about the system to be useful to a variety of problems in engineering design.

Potential applications are in assembly line industrial processes, particularly those in computer-controlled, fully automated factories, and also in the selection of a good appointment system.     

Analysis and modeling of a campus wireless network TCP/IP traffic

In this paper we analyzed and modeled wireless TCP/IP traffic. Specifically, we focused on the interarrival times of TCP flows and the number of packets within a flow. We show that the marginal distribution of the flow interarrival times is piecewise Weibull distributed. Second and higher order statistics show that the flow interarrival times are long-range dependent and exhibit multifractal scaling. Taking these higher order properties into consideration, we proposed a multinomial canonical cascade with 3 stages to model the flow interarrival times. Looking at the IP layer, we find that the number of packets in a flow is heavy-tailed distributed. Especially interesting is that in 2 of our data sets, the number of packets in a flow possesses infinite mean. The interarrival time of packets within a flow is highly correlated, bursty, and its statistical characteristics vary from flow to flow.     

Stochastic Analysis of Deterministic Routing Algorithms in the Presence of Self-Similar Traffic

Many performance models for deterministic routing in multicomputer interconnection networks have been derived and analyzed under the assumption of the traditional Poisson stochastic arrival process, which is inherently unable to capture traffic self-similarity revealed by many real-world parallel applications. In an effort towards understanding the network performance under various traffic loads and different design alternatives, this paper presents an analytical model for dimension-ordered routing in k-ary n-cubes when subjected to self-similar traffic. As the service time, blocking probability and waiting time experienced by a message vary from a dimension to another, the design of such a model for dimension-ordered routing poses greater challenges. The developed analytical model is then used to investigate the efficiency of two different ways to organize virtual channels for deterministic routing and to evaluate the impact of self-similar traffic with various Hurst parameters on network performance.     

Burstiness in broadband integrated networks

Since broadband integrated networks have to cope with a wide range of bit rates, the notion of burstiness which expresses the irregularity of a flow, has been recognized as a vital question for such networks. In burstiness characterization encountered in the literature, special attention is given to the squared coefficient of variation of interarrival time (Cv²) in a cell arrival process. In order to observe the impact of a bursty flow on a queue, we introduce in this paper a new class of arrival process, the n-stage Markov Modulated Bernoulli Process, MMBP_n, for short, and its peculiar case, the n-stage Hyper-Bernoulli process, denoted by HBP_n. We numerically solve the MMBP_n/D/1/K and we compute in particular the rejection probability and the mean waiting time. For that purpose, a relation between the stationary queue length distribution and arrival time distribution is established. This relation adapts the GASTA equality to the arrival process under consideration. We then discuss the relevance of Cv² for burstiness characterization through an example: the HBP₂/D/1/K queue. We show that Cv² becomes significant only when local overload occurs, i.e., when the arrival rate is momentarily greater than the server rate. The results are then applied to two basic ATM problems: traffic characterization and buffer dimensioning using bursty inputs.