Modeling and analysis of power-tail distributions via classical teletraffic methods

We propose a new methodology for modeling and analyzing power-tail distributions, such as the Pareto distribution, in communication networks. The basis of our approach is a fitting algorithm which approximates a power-tail distribution by a hyperexponential distribution. This algorithm possesses several key properties. First, the approximation can be achieved within any desired degree of accuracy. Second, the fitted hyperexponential distribution depends only on a few parameters. Third, only a small number of exponentials are required in order to obtain an accurate approximation over many time scales. Once equipped with a fitted hyperexponential distribution, we have an integrated framework for analyzing queueing systems with power-tail distributions. We consider the GI/G/1 queue with Pareto distributed service time and show how our approach allows to derive both quantitative numerical results and asymptotic closed-form results. This derivation shows that classical teletraffic methods can be employed for the analysis of power-tail distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

过离散次数分布模型的尾部特征

在保险精算和生物统计等领域,离散型次数分布模型的应用十分广泛.当实际数据的尾部较长(即过离散),且零点的概率较大时,许多模型的拟合效果往往欠佳.本文通过计算概率之比的极限和偏度系数,对混合泊松分布和复合泊松分布的右尾特征和零点概率进行了比较,给出了它们的尾部排列顺序,以及尾部长短与零点概率的关系,从而为模型的构造或选择提供了一种指导.本文最后应用一组实际数据说明了在构造或选择次数分布模型时如何考虑尾部特征,从而改善对实际数据的拟合效果.     

Tail probabilities for M/G/∞ input processes (I): Preliminary asymptotics

The infinite server model of Cox with arbitrary service time distribution appears to provide a large class of traffic models - Pareto and log-normal distributions have already been reported in the literature for several applications. Here we begin the analysis of the large buffer asymptotics for a multiplexer driven by this class of inputs. To do so we rely on recent results by Duffield and O’Connell on overflow probabilities for the general single server queue. In this paper we focus on the key step in this approach: The appropriate large deviations scaling is shown to be related to the forward recurrence time of the service time distribution, and a closed form expression is derived for the corresponding generalized limiting log-moment generating function associated with the input process. Three different regimes are identified. In a companion paper we apply these results to obtain the large buffer asymptotics under a variety of service time distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Perturbation Theory for the Asymptotic Decay Rates in the Queues with Markovian Arrival Process and/or Markovian Service Process

Three kinds of queues with Markovian arrival process and/or Markovian service process, are considered in this paper. In great generality, their basic steady-state distributions have asymptotically exponential tails. We investigate the sensitivity of these asymptotic decay rates to the small entrywise perturbations in the parameter matrices of the Markovian arrival process.     

Numerical Computation and Tail Asymptotic for Stationary Indices of a Discrete-Time Vacation Queue

In this paper we study a Geo/Geo/1 queue with T-IPH vacations, where T-IPH denotes the discrete-time phase type distribution defined on a birth and death process with countably many states. Both the multiple and single vacation strategies are considered. For each case, based on the system of stationary equations and using complex analysis method, we firstly give the probability generating functions (PGFs) of stationary distributions for queue length and sojourn time. Moreover, by analysis the PGFs, recursive and asymptotic formulas for additional queue length and additional delay are also given. Finally, we further give some numerical examples to show the effectiveness of the method.     

基于Zipf律的尾部特征分析及VaR计算

分布的尾部特征分析在许多领域都非常重要，估计和分辨尾部服从幂律特征还是指数特征非常重要。在本文中，我们提出了在分析数据的Zipf幂律的基础上来分辨尾部特征的方法。通过实证分析，我们得出了上证指数收益率的确存在具有尺度不变性的Zipf幂律现象，然后分布的尾部特征就被确定，并得到了尾部指数的一种简单的估计方法，最后对该市场的在险价值（VaR）进行了计算和分析。     

On the Distribution of the Extremes of Unequally Correlated Normal Variables with Applications to Antedependent Cluster Data

Based on a small correlations approach, this paper deals with the probability distributions of the order statistics under a general Gaussian model with unequal (positive or negative) correlations. Illustrations are given for the cluster data those follow suitable antedependence models.     

Extreme Values in ON/OFF Models of Teletraffic under Permanent and Periodic Measurements

The asymptotic behavior of stream intensity extreme values in ON/OFF models of teletraffic under permanent and periodic measurements is studied. It is assumed that the intensity of each source has a distribution with a heavy (regularly varying) tail. A joint limiting distribution for maxima with a common linear normalization, marginal distributions, and the distribution of the maxima ratio are obtained. The extremal index for a sequence of periodic measurements is calculated.     

A direct approach to sojourn times in a busy period of an M/M/1 queue

In this paper we present a direct approach to obtaining joint distributions of various quantities of interest in a busy period in an M/M/1 queue. These quantities are: the sojourn times and waiting times of all the customers in the busy period, the busy period length and the number of customers served in a busy period. Since the evolution of the total workload process between two successive customer arrivals is deterministic, this work gives statistic of the complete evolution of the workload process within a busy period. This work was done when the author was post doctoral fellow with the MAESTRO group at INRIA, Sophia Antipolis, France, and was supported by project no. 2900-IT-1 from the Centre Franco-Indien pour la Promotion de la Recherche Avancee (CEFIPRA).     

Joint Distributions for Interacting Fluid Queues

Motivated by recent traffic control models in ATM systems, we analyse three closely related systems of fluid queues, each consisting of two consecutive reservoirs, in which the first reservoir is fed by a two-state (on and off) Markov source. The first system is an ordinary two-node fluid tandem queue. Hence the output of the first reservoir forms the input to the second one. The second system is dual to the first one, in the sense that the second reservoir accumulates fluid when the first reservoir is empty, and releases fluid otherwise. In these models both reservoirs have infinite capacities. The third model is similar to the second one, however the second reservoir is now finite. Furthermore, a feedback mechanism is active, such that the rates at which the first reservoir fills or depletes depend on the state (empty or nonempty) of the second reservoir.The models are analysed by means of Markov processes and regenerative processes in combination with truncation, level crossing and other techniques. The extensive calculations were facilitated by the use of computer algebra. This approach leads to closed-form solutions to the steady-state joint distribution of the content of the two reservoirs in each of the models.     

具有位相型修理的离散时间可修排队系统

本文研究了具有一般独立输入，位相型修理的离散时间可修排队系统，假定服务台对顾客的服务时间和服务台寿命服从几何分布，运用矩阵解析方法我们给出系统嵌入在到达时刻的稳态队长分布和等待时间分布，并证明这些分布均为离散位相型分布．我们也得到在广义服务时间内服务台发生故障次数的分布，证明它服从一个修正的几何分布．我们对离散时间可修排队与连续时间可修排队进行了比较，说明这两种排队系统在一些性能指标方面的区别之处．最后我们通过一些数值例子说明在这类系统中顾客的到达过程、服务时间和服务台的故障率之间的关系．     

Degree Sequences Beyond Power Laws in Complex Networks

Many complex networks possess vertex-degree distributions in a power-law form of $ck^{-\gamma}$, where $k$ is the degree variable and $c$ and $\gamma$ are constants. To better understand the mechanism of power-law formation in real-world networks, it is effective to analyze their degree variable sequences. We had shown before that, for a scale-free network of size $N$ ,if its vertex-degree sequence is $k_11$ , then the length $l$ of the vertex-degree sequence is of order $logN$ . In the present paper, we further study complex networks with more general distributions and prove that the same conclusion holds even for non-network type of complex systems. In addition, we support the conclusion by verifying many real-world network and system examples. We finally discuss some potential applications of the new finding in various fields of science, technology and society.     

THE M/M/c QUEUE WITH PH SYNCHRONOUS VACATIONS

In this paper, we give a detailed analysis of the M/M/c queue with Phase Type synchronous vacations. Two models are considered. Firstly, the vacation strategy is a multiple synchronous vacation. Secondly, only a single vacation is taken each time. For model 1, we give the distributions of the stable queue length and the waiting time. Finally,it is shown that model 2 may be analyzed similarly to model 1.     

An Arrival Time Approach to M/G/1-type Queues with Generalized Vacations

We propose a simple way, called the arrival time approach, of finding the queue length distributions for M/G/1-type queues with generalized server vacations. The proposed approach serves as a useful alternative to understanding complicated queueing processes such as priority queues with server vacations and MAP/G/1 queues with server vacations.     

Tail dependence for elliptically contoured distributions

The relationship between the theory of elliptically contoured distributions and the concept of tail dependence is investigated. We show that bivariate elliptical distributions possess the so-called tail dependence property if the tail of their generating random variable is regularly varying, and we give a necessary condition for tail dependence which is somewhat weaker than regular variation of the latter tail. In addition, we discuss the tail dependence property for some well-known examples of elliptical distributions, such as the multivariate normal, t, logistic, and Bessel distributions.     

一类具有到达损失、可选服务、反馈的M/G/1重试排队系统

考虑一个具有到达损失、可选服务、反馈的M/G/1重试排队系统.在假定重试区域中顾客具有相互独立的指数重试时间的情况下,得到了系统的转移概率矩阵和系统稳态的充分必要条件.列出微分方程,求得稳态时系统队长和重试区域中队长分布及相关指标.     

具有可选服务、反馈、一般重试时间的M/G/1排队系统

本文考虑了一个具有可选服务、反馈的M／G／1重试排队系统。在假定重试区域中只有队首的顾客允许重试的情况下，重试时间具有一般分布时，得到了系统稳态的充分必要条件。求得稳态时系统队长和重试区域中队长分布及相关指标。     

Computation of the quasi-stationary distributions inM(n)/GI/1/K andGI/M(n)/1/K queues

In this paper, we provide numerical means to compute the quasi-stationary (QS) distributions inM/GI/1/K queues with state-dependent arrivals andGI/M/1/K queues with state-dependent services. These queues are described as finite quasi-birth-death processes by approximating the general distributions in terms of phase-type distributions. Then, we reduce the problem of obtaining the QS distribution to determining the Perron-Frobenius eigenvalue of some Hessenberg matrix. Based on these arguments, we develop a numerical algorithm to compute the QS distributions. The doubly-limiting conditional distribution is also obtained by following this approach. Since the results obtained are free of phase-type representations, they are applicable for general distributions. Finally, numerical examples are given to demonstrate the power of our method.     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

相型同步启动时间的M／M／c排队系统

本文研究带有同步启动时间的Ｍ／Ｍ／ｃ系统，其中启动时间是相型变量，给出了稳态和等待时间分布等结果。