Controlling mean queuing delay under multi-class bursty and correlated traffic

This paper presents an adaptive queue management scheme to maintain queuing delay in a router at a required level based on a comprehensive analytical model under aggregated Internet traffic flows from various traffic classes. The proposed scheme uses a closed-loop feedback control mechanism to constrain the average queuing delay by regulating traffic arrival rate implicitly through a movable queuing threshold. A discrete-time queuing model is developed to derive the relationship between average queuing delays and queuing thresholds based on a traffic model that models aggregated Internet traffic through superposition of N MMBP-2 arrival processes. The queuing threshold is adjusted dynamically with reference to the relationship derived in the analytical model and also feedback of average queuing delay measurement. Packets are dropped dynamically with respect to the changes of queuing threshold and the packet loss events serve as implicit congestion indicators. Matlab is used to perform queuing analysis and simulation. Statistical evaluation is performed to show the efficiency and accuracy of the analytical and simulation results.     

Control of queueing delay in a buffer with time-varying arrival rate

Quality of Service (QoS) is of extreme importance in accommodating the increasingly diverse range of services and types of traffic in present day communication networks and delay is one of the most important QoS metrics. This paper presents a new approach for constraining queueing delay in a buffer to a specified level as the arrival rate changes with time. A discrete-time control algorithm is presented that operates on a buffer (queue) which incorporates a moveable threshold. An algorithm is developed that controls the delay by dynamically adjusting the threshold which, in turn, controls the arrival rate. The feasibility of the system is examined using both theoretical analysis and simulation.     

Numerical analysis of the power saving with a bursty traffic model in LTE-Advanced networks

We analyze the power saving operation called Discontinuous Reception (DRX) with a novel bursty packet arrival model in 3GPP Long Term Evolution (LTE)-Advanced networks. Typical analytical studies on the power saving operations in wireless networks have been carried out under the assumption that an expectation of exponentially distributed packet arrival intervals stays unchanged. However, practical packet arrival rate may change depending on time or typical Internet services may incur bursty packet arrivals. In either case, we need to evaluate the performance of the DRX operation. For this purpose, we develop a more realistic traffic arrival model considering packets may arrive in a bursty manner under the DRX operation. We, then, analyze the performance of the DRX operation in terms of power saving efficiency and average queuing delay, respectively. The analytical results are validated via comparisons with simulation results.     

Simulation model of buffer behavior for data multiplexing with Erlang arrivals in analog speech

Due to great simplicity in mathematical analysis, data-arrival process is generally assumed to be a Poisson process but it does not fit in many practical situations. However, the arrival process can be better approximated by Erlang distribution having appropriate degree. This paper analyses buffer behavior in queueing system with finite waiting-room, Erlang arrivals, synchronous transmission and single server having interruptions through a first order Markov process. Erlang distribution for arrival process puts multiple dependence on buffer states. Also this interruption process gives two simultaneous linear matrix equations. Thus the solution of state equations is difficult. Therefore, computer simulation has been used to study the relationships among overflow probability, buffer size and expected queueing delay due to buffering as a function of traffic intensity and the degree of Erlang distribution (Erlang parameter). A voice-data system (shown in Fig. 1) has been considered as an application for this model. The results of this study are portrayed on graphs and may be used as guidelines in buffer design problems in similar situations. Although this problem arose in the study of multiplexing of data in speech, the queueing model developed is quite general and may be useful for other industrial applications.     

一种自相似网络可靠性分析模型

利用ON/OFF模型产生自相似流量,提出了一种基于排队延迟的自相似网络可靠性分析模型。将节点和到达信息流视为G/M/1/B排队模型,利用大偏差理论得到节点平均排队延迟时间,进而得到网络各种工作状态下全网平均排队延迟时间。再利用延迟阀值得到各种工作状态下的网络可靠性,进一步得到全网可靠性。通过模拟计算,得到了给定拓扑结构网络的可靠性与自相似程度、ON/OFF源数量以及节点缓存大小之间的关系。     

An analytical model for Network-on-Chip with finite input buffer

An analytical model is proposed for input buffer router architecture Network-on-Chip (NoC) with finite size buffers. The model is developed based on M/G/1/K queuing theory and takes into consideration the restriction of buffer sizes in NoC. It analyzes the packet’s sojourn time in each buffer and calculates the packets average latency in NoC The validity of the model is verified through simulation. By comparing our analytical outcomes to the simulation results, we show that the proposed model successfully captures the performance characteristics of NoC, which provides an efficient performance analysis tool for NoC design.     

基于车辆载带中继的路边单元突发业务分组调度最优策略

高速公路车联网场景中, 路边单元(Roadside units, RSUs)可作为多种周边监测数据的汇入网关, 其业务具有突发特性, 且可通过移动车辆以“存储?载带?转发”方式传输到与骨干网络互联的RSU. 针对RSU间业务传输问题, 源RSU可根据实时业务到达率按需匹配资源, 以应对业务突发性对分组端到端时延的影响. 本文首先针对RSU突发业务传输过程建立突发业务到达模型、车辆到达模型和离散车速状态模型; 进而利用受限马尔科夫决策过程对系统状态转移过程进行分析, 并建立非线性平均端到端时延最小化问题; 最后通过分析最优解的形式得出最优分组调度策略具有门限结构. 仿真结果验证了RSU间业务传输过程中排队时延和传播时延之间存在折中, 且该分组调度策略能降低业务传输过程的平均端到端时延.     

Optimally efficient estimation of the statistics of rare events inqueueing networks

Because of their rarity, the estimation of the statistics of buffer overflows in networks of queues by direct simulation is very costly. An asymptotically optimal (as the overflow recurrence time becomes large) scheme has been proposed by others, using importance sampling. Two aspects of this scheme are addressed. First, in the existing approach, a numerical minimization is required to generate the simulation network. An equivalent analytic minimization is described. A simple procedure for constructing the optimal simulation network is included. Second, it is shown that the average behaviour of the simulation system is the same as the average behavior of the original network in the period leading up to a buffer overflow. For a sufficiently large buffer size, the optimal simulation system depends only on the statistics of the service rate of one queue (that of the least serviced buffer) and the arrival process, assuming that no two service rates are actually equal, and does not depend in any way on the statistics of the service rates of buffers other than the one dominating the overflow statics     

基于CAC的ATM网络性能仿真

该文在ATM网络排队性能的基础上 ,根据信元的平均丢失率及平均延迟时间与传输带宽及缓存单元数量的近似关系 ,提出了连接允许控制的 (CAC)算法 ,从而为ATM网络性能仿真提供了理论依据。     

A model of periodic acknowledgement

We study a problem abstracted from modeling a multicast protocol. In our model, messages generated by a single source are simultaneously forwarded to a set of receivers where they are independently processed. We assume a state-dependent message arrival rate and memoryless service time distributions. The receivers may process messages at different average rates. Messages processed by all receivers are periodically acknowledged and cleared from the system. Due to finite buffer space, the total number of non-acknowledged messages in the system is limited. Our focus in this paper is on the number of messages cleared at acknowledgement time.

The problem under consideration bears resemblance to a fork/join process with heterogeneous servers, used in the study of multiprocessing computer systems. Our model includes the additional features of finite buffer space and delayed periodic departure of completed jobs. Even without these features, the resulting type of queuing model has no known closed-form solution in the general case of more than two servers. Because the arrival processes to the servers are correlated, the model is difficult to decompose. We propose a relatively simple decomposition technique and a fixed-point iteration scheme. In our approach, we consider each receiver (server) in isolation, and we account for the influence of other receivers through the probability that a given number of messages can be cleared at acknowledgement time. We derive elementary differential equations for the number of messages processed by a receiver. These equations involve the conditional probability of the number of messages not yet processed given the number of messages waiting to be cleared. We compute an approximate solution using the conditional probability obtained from a model with exponentially distributed acknowledgement periods. Our numerical results for the average number of messages cleared at acknowledgment time are typically within a few percent of simulation midpoints.     

Optimal hop-by-hop flow control in computer networks

The problem of hop-by-hop flow control in a computer network is formulated as a Markov decision process with a cost function composed of the delay of the messages and the buffer constraints. The optimal control is shown to be a linear truncated function of the state and the explicit form is found when the arrival process of the messages is a Bernoulli process. For a renewal arrival process, the long-rnn average cost of any policy with a linear truncated structure is expressed by a set of linear equations.     

Hybrid fluid modeling approach for performance analysis of P2P live video streaming systems

In this paper a hybrid modeling approach with different modeling formalisms and solution methods is employed in order to analyze the performance of peer to peer live video streaming systems. We conjointly use queuing networks and Fluid Stochastic Petri Nets, developing several performance models to analyze the behavior of rather complex systems. The models account for: network topology, peer churn, scalability, peer average group size, peer upload bandwidth heterogeneity and video buffering, while introducing several features unconsidered in previous performance models, such as: admission control for lower contributing peers, control traffic overhead and internet traffic packet loss. Our analytical and simulation results disclose the optimum number of peers in a neighborhood, the minimum required server upload bandwidth, the optimal buffer size and the influence of control traffic overhead. The analysis reveals the existence of a performance switch-point (i.e. threshold) up to which system scaling is beneficial, whereas performance steeply decreases thereafter. Several degrees of degraded service are introduced to explore performance with arbitrary percentage of lost video frames and provide support for protocols that use scalable video coding techniques. We also find that implementation of admission control does not improve performance and may discourage new peers if waiting times for joining the system increase.     

A simulation study of bursty data traffic with hybrid source smoothing in an ATM node

In this paper, we study the mean delay and maximum buffer requirements at different levels of burstiness for highly bursty data traffic in an ATM node. This performance study is done via an event-driven simulation program which considers both real-time and data traffic. We assume that data traffic is loss-sensitive. A large buffer (fat bucket) is allocated to data traffic to accommodate sudden long burst of cells. Real-time traffic is delay-sensitive. We impose input traffic shaping on real-time traffic using a leaky-bucket based input rate control method. Channel capacity is allocated based on the average arrival rate of each input source to maximize the utilization of channel capacity. Simulation results show that both the maximum buffer requirements and mean node delay for data traffic are directly proportional to the burstiness of its input traffic. Results for mean node delay and cell loss probability of real-time traffic are also analyzed. The simulation program is written in C++ and has been verified using the zero mean statistics concept by comparing simulation results to known theoretical or observed results.     

Dimensioning shared-per-node recirculating fiber delay line buffers in an optical packet switch

Optical buffering based on fiber delay lines (FDLs) has been proposed as a means for contention resolution in an optical packet switch. In this article, we propose a queuing model for feedback-type shared-per-node recirculating FDL optical buffers in asynchronous optical switching nodes. In this model, optical packets are allowed to recirculate over FDLs as long as the total number of recirculations is less than a pre-determined limit to meet signal loss requirements. Markov Modulated Poisson Process (MMPP)-based overflow traffic models and fixed-point iterations are employed to provide an approximate analysis procedure to obtain blocking probabilities as a function of various buffer parameters in the system when the packet arrival process at the optical switch is Poisson. The proposed algorithm is numerically efficient and accurate especially in a certain regime identified with relatively long and variably-sized FDLs, making it possible to dimension optical buffers in next-generation optical packet switching systems.     

多信道有限缓存下混合业务接入控制的排队性能研究

基于无线通信网的运行机制和实时性、非实时性混合业务对无线通信网络的不同服务质量（QoS）要求,设计了有限缓存下实时性业务优先接入控制策略,并建立了无线通信网络在有限缓存下混合业务带有优先接入控制的多服务台离散时间排队模型Geom₁±Geom₂/Geom₁, Geom₂/s, s（PP）/n+s, s.精确划分了系统的状态组成,分析了系统性能和状态转移概率,获得了系统的稳态分布、平均队长、损失率、以及信道的平均利用率.最后,对所建模型进行数值模拟,得到各业务到达率、服务率、信道个数、缓冲器容量与各业务损失率的关系.针对网络拥塞控制,本文提出通过增加信道个数、提高优先级业务的服务率能有效地降低两类业务的损失率.     

拥挤路线交通量控制的模糊推理算法

当道路发生突发性事件引起交通拥挤时，一方面需要引导驾驶员转向到可替换路线， 另一方面也要对进入拥挤路线的交通量进行控制．本文通过对反映路线拥挤程度的延误时间 信息和排队长度信息进行预测，设计了在事件持续时间内，以车辆到达率不超过事件发生地 点通行能力为拥挤路线控制目标的模糊推理算法，并进行了实际案例分析．分析结果表明， 这种模糊推理算法能在一定程度上取代交通工程师们对拥挤的管理，从而提高了拥挤管理的 效率．     

Simulation of queueing network with time varying arrival rates

Queueing models are important in the analysis of many aspects of system or human behaviour. In such widely divergent fields as administrative processes, health services, traffic control, production control, computer communication networks, time sharing, and architecture, queueing analysis is indisposable for better understanding and ultimately synthesis of the system.However straight mathematical analysis is difficult, as the difference equations describing a queueing network are non-linear and of infinite dimensional. Due to this difficulty, time varying cases are seldomly included in the study of analytic solutions of queueing systems. In existing literature, the mean arrival rates are assumed independent of time. This assumption is of dubious validity as the arrival rate in actual operations varies with a twenty four hours period. While one can assume further that at every instant in time, the equilibrium condition for constant arrival rate is reached for the current arrival rate, it has never been verified that such is the case.An alternative approach is to reduce the queueing problem to finite dimensional and to simulate it on computer as is proposed in the present paper. The basic assumptions are (1) time-varying random arrival rate with Poisson statistics and (2) exponentially distributed service time. An algorithm and flow diagram for doing this is given. With the simulation techniques developed in this paper, we can study the dynamics of varying arrival rate. Simulation of a simple network shows that as the arrival rate approaches capacity, the divergence between simulated results and previous analytical results for the equilibrium condition become increasingly large. A conclusion is therefore that except for systems with very light loading, analytical results based on constant arrival rate are not accurate. Simulation is necessary if one is to obtain a true picture of the system.     

Performance analysis of a non-preemptive priority queuing system subjected to a correlated Markovian interruption process

In this paper, we consider a discrete-time queuing system with head-of-line non-preemptive priority scheduling and a single server subjected to server interruptions. We model the server interruptions by a correlated Markovian on/off process with geometrically distributed on and off periods. Two classes of traffic are considered, namely high-priority and low-priority traffic. In the first part of the paper, we derive an expression for the functional equation describing the transient evolution of this priority queuing system. This functional equation is then manipulated and transformed into a mathematical tractable form. This allows us to derive the joint probability generating function (pgf) of the system contents. From this pgf, closed-form expressions for various performance measures, such as mean and variance of system contents and customer delay can be derived. Finally, we illustrate our solution technique with some numerical examples, whereby we demonstrate the negative effect of correlation in the interruption process on the performance of both classes. Some numerical results illustrating the impact of second-order characteristics of the arrival process on mean delays are also presented. The proposed approach which is purely based on pgfs is entirely analytical and enables the derivation of not only steady-state but transient performance measures, as well. The paper presents new insights into the performance analysis of discrete-time queues with service interruption and it also covers some previously published results as a special case.

Scope and purpose

In this contribution, we consider a practical queuing model, with HOL priority scheduling, two classes of traffic, and a server which is subjected to a correlated Markovian interruption process. We first derive a non-linear functional equation relating the joint pgf of the system state vector between two consecutive slots. Then we outline a solution technique to solve for this functional equation. This allows us to derive the joint pgf of the system contents of both classes, from which various performance measures related to mean system contents and customer delays are derived. We also demonstrate how the proposed approach allows for derivation of transient performance measures, as well. It should be noted that detailed coverage of the transient analysis of the system is beyond the scope of this paper.To our best knowledge, this is the first initiative that aims to explore the performance of queuing systems with priority scheduling when the shared server is subjected to service interruption. The paper also generalizes the results of Walraevens et al. (Analysis of a single-server ATM queue with priority scheduling, Computers & Operations Research 2003;30(12):1807–30) by incorporating service interruption into their original queuing model. By means of numerical results, the paper also demonstrates the effect of correlation in the service interruption process on the performance of both classes of customers. The impact of second-order characteristics of the arrival process on mean delays is also investigated.     

Performance analysis of a threshold-based discrete-time queue using maximum entropy

The provision of guaranteed QoS for various Internet traffic types has become a challenging problem for researchers. New Internet applications, mostly multimedia-based, require differentiated treatments under certain QoS constraints. Due to a rapid increase in these new services, Internet routers are facing serious traffic congestion problems. This paper presents an approximate analytical performance model in a discrete-time queue, based on closed form expressions using queue threshold, to control the congestion caused by the bursty Internet traffic. The methodology of maximum entropy (ME) has been used to characterize closed form expressions for the state and blocking probabilities. A discrete-time GGeo/GGeo/1/{N₁, N₂} censored queue with finite capacity, N₂, external compound Bernoulli traffic process and generalised geometric transmission times under a first come first serve (FCFS) rule and arrival first (AF) buffer management policy has been used for the solution process. To satisfy the low delay along with high throughput, a threshold, N₁, has been incorporated to slow the arrival process from mean arrival rate λ₁ to λ₂ once the instantaneous queue length has been reached, otherwise the source operates normally. This creates an implicit feedback from the queue to the arrival process. The system can be potentially used as a model for congestion control based on the Random Early Detection (RED) mechanism. Typical numerical experiments have been included to show the credibility of ME solution against simulation for various performance measures and to demonstrate the performance evaluation of the proposed analytical model.     

排队系统输出序列的广义相关与广义谱研究

由于排队论不可能求解排队系统中的时间序列问题,因此,将时间列自相关函数的定义作了推广,以便应用于这一问题。方法是将m视为另一种采样规则下所得序列的序号,即以排队到达时刻为采样时刻。由此可以试探寻排队系统等待时间序列{WT(n)}等的ARMA模型。文中还建立了排队系统时间序列的广义谱的概念,可以期望,广义谱概念的建立,将十分有助于对排队系统输出序列、排队仿真序列以及所有离散系统随机仿真序列特征与规律的揭示。