Modeling multiple IP traffic streams with rate limits

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.     

Towards the formation of comprehensive SLAs between heterogeneous wireless DiffServ domains

Traffic patterns generated by multimedia services are different from traditional Poisson traffic. It has been shown in numerous studies that multimedia network traffic exhibits self-similarity and burstiness over a large range of time-scales. The area of wireless IP traffic modeling for the purpose of providing assured QoS to the end-user is still immature and the majority of existing work is based on characterization of wireless IP traffic without any coupling of the behaviour of queueing systems under such traffic conditions. Work in this area has either been limited to simplified models of FIFO queueing systems which do not accurately reflect likely queueing system implementations or the results have been limited to simplified numerical analysis studies. In this paper, we advance the knowledge of queueing systems by example of traffic engineering of different UMTS service classes. Specifically, we examine QoS mapping using three common queueing disciplines; Priority Queuing (PQ), Low Latency Queuing (LLQ) and Custom Queueing (CQ), which are likely to be used in future all-IP based packet transport networks. The present study is based on a long-range dependent traffic model, which is second order self-similar. We consider three different classes of self-similar traffic fed into a G/M/1 queueing system and construct analytical models on the basis of non-preemptive priority, low-latency queueing and custom queueing respectively. In each case, expressions are derived for the expected waiting times and packet loss rates of different traffic classes. We have developed a comprehensive discrete-event simulator for a G/M/1 queueing system in order to understand and evaluate the QoS behaviour of self-similar traffic and carried out performance evaluations of multiple classes of input traffic in terms of expected queue length, packet delay and packet loss rate. Furthermore, we have developed a traffic generator based on the self-similar traffic model and fed the generated traffic through a CISCO router-based test bed. The results obtained from the three different queueing schemes (PQ, CQ and LLQ) are then compared with the simulation results in order to validate our analytical models.     

Parameter estimation for Markov modulated Poisson processes via the EM algorithm with time discretization

The Markov modulated Poisson process (MMPP) has been proposed as a suitable model for characterizing the input traffic to a statistical multiplexer [6]. This paper describes a novel method of parameter estimation for MMPPs. The idea is to employ time discretization to convert an MMPP from the continuous-time domain into the discrete-time domain and then to use a powerful statistical inference technique, known as the EM algorithm, to obtain maximum-likelihood estimates of the model parameters. Tests conducted through a series of simulation experiments indicate that the new method yields results that are significantly more accurate compared to the method described in [8]. In addition, the new method is more flexible and general in that it is applicable to MMPPs with any number of states while retaining nearly constant simplicity in its implementation. Detailed experimental results on the sensitivity of the estimation accuracy to (1) the initialization of the model, (2) the size of the observation interarrival interval data available for the estimation, and (3) the inherent separability of the MMPP states are presented.     

Performance analysis of MAC layer protocols in the IEEE 802.11 wireless LAN

In recent years, WLANs (Wireless Local Area Networks) based on the IEEE 802.11 standard have been taken a growing interest and developed widely all over the world. CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) protocols are the most popular MAC (Medium Access Control) protocols for WLANs. The performance of CSMA/CA protocols over wireless channels has been investigated over the past years. In this paper, we obtain the probability distribution function of the MAC layer packet service time, and we present the comprehensive performance analysis of IEEE 802.11 MAC protocol by investigating the queue dynamics of a wireless station based on the MAC layer packet service time. We adopt an MMPP(Markov Modulated Poisson Process) as the input traffic model that describes well the bursty nature of Internet traffic. The analysis on the throughput and the delay performance has been carried out by using the MMPP/G/1/K queueing model. We have some numerical results that represent the system throughput and the queue dynamics including the mean packet waiting time and packet blocking probability.     

MMPP models for multimedia traffic

The paper presents a study on the use of Markov‐Modulated Poisson Processes (MMPP's) for characterizing multimedia traffic with short‐term and long‐term correlation. The applicability of the 2‐state MMPP and a refined moment‐based parameter‐matching technique to model an arbitrary ATM traffic stream in evaluating its queueing performance are examined by simulation. Following a discussion on the limitation of the 2‐state MMPP model, a model using a superposition of N homogeneous 2‐state MMPP to characterize bursty multimedia traffic is presented. The proposed model requires only five parameters which can be estimated from the samples of the traffic counting process by using a pdf‐based matching technique. The introduced pdf‐based parameter‐matching procedure uses the probability density function of the arrival rate and the IDC curve of the traffic samples. An approximation for the probability of loss in MMPP/D/1 queues is also obtained. The versatility and accuracy of the proposed model to characterize bursty multimedia traffic are shown by several case studies and test results. This revised version was published online in June 2006 with corrections to the Cover Date.     

An application of Markovian arrival process (MAP) to modelingsuperposed ATM cell streams

First, we propose a new modeling method for superposed ATM traffic by the MMPP(2), which is a special case of the MAP(2). In this new method, we measure the mean and autocorrelation of cell interarrival times, and the histogram of the number of arrivals during measurement windows of fixed size. The MMPP(2) has interarrival times with a second-order hyper-exponential distribution with coefficient of variation c_ν > 1. However, superposed traffic is often observed to have c_ν < 1. To cover this situation, we extend the MMPP(2) to a MAP(3) by adding a new state with inter-state transition accompanied by an arrival. For the MAP(3) model, we take into account the second moment of the interarrival times. From numerical examples, we observe that both the proposed MMPP(2) and MAP(3) yields very good estimation of the cell loss ratio (CLR) for usual superpositions of voice and/or VBR video sources. However, when we have superpositions from CBR video sources together with other VBR sources, c _ν. is much less than 1, and the MAP(3) outperform the MMPP(2), as expected. The proposed MAP(3) well characterizes the cell scale component as well as the burst scale component of superposed traffic streams     

自相似业务模型下的队列分析--大偏差技术

近年来对许多实际运行中的网络（局域网和广域网）的测量与分析证实：真实的网络业务具有统计上的自相似性而且是长相关的。传统的排队理论均假定业务是Poisson或Markovian,因此是短相关的,那里的队列分析方法对自相似业务模型是不适用的。大偏差技术是对自相似业务模型进行队列分析的有效方法。本文应用大偏差技术对以FARIMA为业务模型的队列系统进行了分析,结果证明：队列长度尾分布渐进为Weibullian分布,而且与模型的短相关结构无关。     

Per-stream jitter analysis in CBR ATM multiplexors

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     

Delay jitter first-order and second-order statistical functions ofgeneral traffic on high-speed multimedia networks

We develop analytical approximations for the first order and second-order statistics of the delay jitter experienced by a stationary traffic stream multiplexed at a major communication node; these approximations are then used to gain insight into the behavior of jitter at a single node under diverse system and traffic conditions. Our construction applies when the node can be modeled as a finite quasi-birth-death (QBD) process and the interarrival time probability density functions (pdfs) for the tagged stream are obtainable. We compare the jitter performance of three different tagged streams: periodic, Poisson, and on/off binary Markov process. Because jitter behavior is most deleterious for the former, we study the individual effects of various system and traffic parameters on the jitter statistics of a periodic stream multiplexed in a Markov-modulated Poisson process (MMPP)/M/1/K system. To demonstrate the flexibility of this analytical technique, we also consider a JPEG video stream multiplexed with JPEG, MPEG, and data sources on an OC-12 line     

基于分形点过程自相似流的队列性能分析

通过对交换机排队系统进行仿真,分析了以分形点过程( FPP )自相似业务流为输入的排队系统的性能.仿真结果显示,自相似业务流量模型下队列的性能与传统指数流量模型下的队列性能大不相同.文中所获得的仿真结果可用于网络流量模型、网络设计、网络拥塞控制和流量工程等.     

Performance of a priority-based dynamic capacity allocation schemefor wireless ATM systems

The performance of a priority-based dynamic capacity allocation suitable for wireless ATM systems is presented. The scheduling of ATM cell transmission in each uplink TDMA frame is based on a priority scheme with priority given to real-time traffic over nonreal-time traffic. Real-time traffic exceeding the uplink capacity is lost while nonreal-time traffic that cannot be served is stored in a first-in first-out (FIFO) queue. An analytical model is developed to evaluate the cell loss ratio (CLR) of both real-time and nonreal-time traffic. Aggregate voice, video, and data traffic is modeled by three two-state Markov-modulated Poisson processes (MMPPs). Analytical results for different system capacities and various traffic loads and scenarios are discussed. Simulation results with on-off sources and approximating MMPP sources are also presented     

Multiscale Fitting Procedure Using Markov Modulated Poisson Processes

This paper proposes a parameter fitting procedure using Markov Modulated Poisson Processes (MMPPs) that leads to accurate estimates of queuing behavior for network traffic exhibiting long-range dependence behavior. The procedure matches both the autocovariance and marginal distribution of the counting process. A major feature is that the number of states is not fixed a priori, and can be adapted to the particular trace being modeled. The MMPP is constructed as a superposition of L 2-MMPPs and one M-MMPP. The 2-MMPPs are designed to match the autocovariance and the M-MMPP to match the marginal distribution. Each 2-MMPP models a specific time-scale of the data. The procedure starts by approximating the autocovariance by a weighted sum of exponential functions that model the autocovariance of the 2-MMPPs. The autocovariance tail can be adjusted to capture the long-range dependence characteristics of the traffic, up to the time-scales of interest to the system under study. The procedure then fits the M-MMPP parameters in order to match the marginal distribution, within the constraints imposed by the autocovariance matching. The number of states is also determined as part of this step. The final MMPP with M2 ^L states is obtained by superposing the L 2-MMPPs and the M-MMPP. We apply the inference procedure to traffic traces exhibiting long-range dependence and evaluate its queuing behavior through simulation. Very good results are obtained, both in terms of queuing behavior and number of states, for the traces used, which include the well-known Bellcore traces.     

Performance of broadcast and unknown server (BUS) in ATM LANemulation

We develop performance models of the broadcast and unknown server (BUS) in the LANE. The traffic on the BUS is divided into two classes: the broadcast and multicast traffic, and the unicast relay flow. The broadcast and multicast traffic is assumed to form a Markov modulated Poisson process (MMPP). The traffic for a particular unicast relay flow is an MMPP as well. However, the number of active unicast relay flows sojourning on the BUS is determined by a tandem queueing system, where the flow arrival process is Poisson, the address resolution delay is exponentially distributed, and the connection setup delay is three-stage Erlang distributed. The size of data frames in traffic flows is a random variable with three possible values: short, medium, and large. In order to deal with the intractability (i.e., largeness and stiffness) of the underlying Markov chain, a hierarchical model is used to decompose the system. With the help of the Stochastic Petri Net Package (SPNP), a software package for the automated generation and solution of Markovian stochastic systems, and the decomposition method, we study the performance of the BUS module under different loads. We also investigate the effect of address resolution delay and connection setup delay on the performance of the BUS     

Network heavy traffic modeling using α-stable self-similarprocesses

We propose a new model for network heavy traffic approximation, based on α-stable self-similar processes, namely the skewed linear fractional stable noise. The model demonstrates more flexibility than existing models in fitting different levels of burstiness and correlation in the data. Nonetheless, it is parsimonious in the number of parameters, which have a direct physical meaning. An algorithmic procedure for the estimation of the model parameters is presented, and an asymptotic lower bound of the residual queueing distribution is derived. Extensive simulations are presented, where the new model is fitted to bursty Ethernet data collected at Bellcore (now Telcordia) Laboratories. Furthermore, new measurements of aggregate Web and Webcasting traffic are introduced along with traffic generated by the fitted new model. Queueing simulations of a G/D/1 system confirm our analytical results regarding the tail of the queue distribution     

Markovian Arrival Process Parameter Estimation With Group Data

This paper addresses a parameter estimation problem of Markovian arrival process (MAP). In network traffic measurement experiments, one often encounters the group data where arrival times for a group are collected as one bin. Although the group data are observed in many situations, nearly all existing estimation methods for MAP are based on nongroup data. This paper proposes a numerical procedure for fitting a MAP and a Markov-modulated Poisson process (MMPP) to group data. The proposed algorithm is based on the expectation-maximization (EM) approach and is a natural but significant extension of the existing EM algorithms to estimate parameters of the MAP and MMPP. Specifically for the MMPP estimation, we provide an efficient approximation based on the proposed EM algorithm. We examine the performance of proposed algorithms via numerical experiments and present an example of traffic analysis with real traffic data.      

On the evolution of traffic characteristics inside multistage switching systems

In this paper, a method is developed to analyze the evolution of the traffic characteristics of information streams crossing the consecutive stages of an ATM multistage switching structure. Specifically, we develop a generic model for characterizing the traffic streams at the input of the consecutive stages, based on the assumption that the queueing processes in subsequent stages are independent. In our model, the parameters that determine the arrival process on the inlets of a switching element in a given stage solely depend on the output process on the outlets of the switching elements belonging to the previous stage. As a result, we are able to calculate the mean value and variance, as well as the whole distribution of the buffer contents and the packet delay in a tagged switching element, anywhere in the structure, based on earlier work. Furthermore, we can prove that, under the assumptions of the model, the traffic characteristics converge to a spatial steady state after a few stages in the system, i.e., the traffic parameters reach limiting values which are independent of the characteristics of the traffic sources at the entrance of the first stage. Although the present study focuses on the specific case of ATM switching systems, the authors believe similar results to hold also for more general multistage structures in which routing and multiplexing occurs in each stage.     

On the effects of the packet size distribution on the packet loss process

Real-time multimedia applications have to use forward error correction (FEC) anderror concealment techniques to cope with losses in today’s best-effort Internet. The efficiency of these solutions is known however to depend on the correlation between losses in the media stream. In this paper we investigate how the packet size distribution affects the packet loss process, that is, the distribution of the number of lost packets in a block, the related FEC performance and the average loss run length. We present mathematical models for the loss process of the MMPP+M/D/1/K and the MMPP+M/M/1/K queues; we validate the models via simulations, and compare the results to simulation results with an MPEG-4 coded video trace. We conclude that the deterministic packet size distribution (PSD) not only results in lower stationary loss probability than the exponential one, but also gives a less correlated loss process, both at a particular average link load and at a particular stationary loss probability as seen by the media stream.Our results show that for applications that can only measure the packet loss probability, the effects of the PSD on FEC performance are higher in access networks, where a single multimedia stream might affect the multiplexing behavior. Our results show that the effects of the PSD on FEC performance are higher in access networks, where a single multimedia stream might affect the multiplexing behavior and thus can improve the queuing performance by decreasing the variance of its PSD.     

自相似业务量的流量控制研究

由于自相似性是宽带网络中业务量的一个普遍特性,因此在进行宽带网络管理和流量控制时必须考虑它所带来的影响。目前,有关基于自相似业务量的流控机制的研究已经引起了人们广泛地注意。一些研究表明自相似业务量表现出了与传统模型不同的排队特征。本文围绕业务质量保证和流量控制机制,具体研究和分析了业务量的自相似性质对业务量成形、用法参数控制和呼叫接纳控制等流量控制机制的影响,并得到了一些重要结论。