网络分组交换中的排队论模型分析

排队论模型在计算机网络通信系统中具有广泛应用,如评价网络性能,设计计算机网络等.作者通过对M/M/1和M/D/1模型的深入分析,得出了M/G/1模型中的最佳排队系统模型.     

基于输入匹配排队系统M/Dr/1'/Q的多目标规划模型研究

研究了M/D^r/1’/Q输入匹配排队系统。提出了一种新的排队规则,即顾客到达是两个独立的泊松过程,在排队系统中引入快速通道,服务机制为修正的先到先服务,一个群体服务台,成批接受定长服务。快速通道是一种减少排队系统等待时间的有效方式。详细分析了单通道和双通道M/D^r/1’/Q两种排队系统的性态,建立了具有快速通道的双通道M/D^r/1’/Q排队系统的多目标规划模型,模型仅有一个决策变量。最后利用理想点法给出了多目标规划模型的有效解,表明模型有良好的性质。     

码头装卸服务G／M／1排队模型及仿真研究

研究码头装卸仿真服务系统,M/M/1排队模型有严格的理论条件,在工程应用中对不满足理论条件的情况,模型分析结果的准确性会受到影响。为提高控制序列的准确性,提出了等间隔到达和随机到达的混合序列到达时间间隔概率分布,假定该混合到达顾客到达时间间隔相互独立同分布,采用G/M/1排队模型得出了排队服务系统的系统参数。编写MAT-LAB仿真程序,结合实例比较了G/M/1与M/M/1模型分析结果和仿真结果,表明比M/M/1模型能更准确地描述系统的各项参数,结果证明可为排队系统设计提供参考依据。     

一种新的排队方式

下图表示两种不同的排队方式。图中λ表示“顾客”到来的平均速度(人/秒);μ表示服务台平均服务的速度(人/秒)。图1中设各队顾客到来的速度是λ/m,其排队系统可用m个M/M/1系统来表示;而图2中的排队系统可用M/M/m系统来表示。其中图1是常见的排队方式,而图2情况在我国难以找到。图2排队方式的好处有以下几点:     

非强占有限优先权M/M/1排队系统

以计算机网络中实时视频流传输的实际应用为基础,建立非强占有限优先权M/M/1排队系统模型;对该系统模型进行分析研究,推导出顾客在系统内的的平均等待时间、平均逗留时间和平均队长。     

基于仿真模型的集装箱码头排队系统分析

基于Witness仿真软件建立了集装箱码头桥吊服务系统的排队系统仿真模型,通过对M/M/m排队系统参数分析,发现随着服务台数量的增大,排队系统的性能逐渐变好。各指标的变化曲线存在拐点,拐点之后变化幅度不再明显,此拐点对应的x坐标值就是桥吊配置数量的最佳值。通过对比不同排队模型进行仿真分析,认为集装箱码头桥吊服务系统的M/M/m排队系统的工作能力和效率都更高,且性能更容易改善。研究结果对码头其它节点的排队系统的分析也有参考价值。     

输入匹配排队系统M/D^r/1’/Q的灵敏度分析

对M/Dr/1’/Q输入匹配排队系统进行了分析和研究,提出了顾客到达是两个独立的泊松过程的一种新的排队规则,即在服务机制为修正的先到先服务且为群体服务台,成批接受定长服务的排队系统中引入快速通道。快速通道是一种减少排队系统等待时间的有效方式。详细分析了单通道和双通道M/Dr/1’/Q两种排队系统的性态。大量的仿真试验表明具有快速通道的双通道M/Dr/1’/Q排队系统在很大程度上提高了系统性能,包括减少平均队长和缩短收敛时间。     

云制造系统中区块链排队时延分析与仿真

针对云制造系统中区块链的排队时延问题,探索降低云制造系统中区块链排队时延的因素,提出一种新型的云制造系统区块链模型,在传统云制造系统架构的服务层中引入区块链服务。将制造服务请求在区块链服务的排队时延过程分解为缓冲阶段和共识阶段,使用M/M/1排队模型分析系统指标。提出一种自适应难度值机制,优化不同算力的节点参与共识的机会。并且研究节点收益与节点服务率的关系。仿真结果表明,基于M/M/1排队模型能够反映云制造系统的请求排队时延过程;引入自适应难度值后,算力小的区块链节点有更大的机会获取记账权,且节点的收益与其服务率呈正相关。     

基于排队网络的流水线模拟器任务缓存新分析模型

流水线软件模拟器是嵌入式微处理器软件仿真系统的关键技术,提出对嵌入式微处理器流水线仿真系统的排队网络建模与缓存大小分析方法.对SPARC-V8流水线模拟器建立M/M/1/N型排队网络模型,分析指令到达及服务阻塞机制.为了解决模型计算中的阻塞问题,在排队网络模型中增加"保持节点",得到扩展的等价排队网络模型.采用近似计算迭代算法,得到系统性能评价指标,并建立排队网络节点性能关系曲线,确定各功能模块的任务缓存大小.根据得出的任务缓存计算值设置流水线软件模拟器实际缓存大小,实验表明模型计算数据与实际运行数据基本一致.该评价方法对嵌入式微处理器流水线仿真系统的建模与性能分析具有重要的指导意义.     

基于CPN的空竭服务单重休假M/G/1型排队系统建模与分析

空竭服务单重休假M/G/1型排队系统是经典排队系统的推广,在许多领域有着广泛的应用.到目前为止对其的处理方法还都是建立在概率论和数理统计的基础上,运用马尔可夫随机过程求解,推导十分复杂,没有直观的模型描述.因此,利用着色Petri网对空竭服务单重休假M/G/1型排队系统进行建模,并对主要性能指标进行仿真分析是迫切以及可行地.仿真软件选用CPNTools[1],仿真结果证明该方法具有较高的精确度以及实用价值.     

Analysis of the discrete-time Geo/G/1 working vacation queue and its application to network scheduling

In this paper we present an exact steady-state analysis of a discrete-time Geo/G/1 queueing system with working vacations, where the server can keep on working, but at a slower speed during the vacation period. The transition probability matrix describing this queuing model can be seen as an M/G/1-type matrix form. This allows us to derive the probability generating function (PGF) of the stationary queue length at the departure epochs by the M/G/1-type matrix analytic approach. To understand the stationary queue length better, by applying the stochastic decomposition theory of the standard M/G/1 queue with general vacations, another equivalent expression for the PGF is derived. We also show the different cases of the customer waiting to obtain the PGF of the waiting time, and the normal busy period and busy cycle analysis is provided. Finally, we discuss various performance measures and numerical results, and an application to network scheduling in the wavelength division-multiplexed (WDM) system illustrates the benefit of this model in real problems.     

基于两次丢包策略的主动队列管理算法研究

针对网络拥塞现象,基于两次丢包方法建立了一种新的主动队列管理算法TDPQW。该算法利用M/G/1排队模型推导了实际队列长度和等待时间的数学表达式,以此提出在队列头部和队中随机位置进行丢包的策略。同时,通过仿真实验对比分析了该算法与RED、DROP-TAIL算法的性能,结果表明TDPQW具有较好的适应性。     

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.     

一种基于损失率估算的可变缓冲管理模型

缓冲区作为一种缓存关键信息、协调速度差异的重要手段,在计算机工程领域一直扮演着一个不可忽视的角色。缓冲区的大小对其作用的发挥至关重要。为此,在分析现有缓冲技术的基础上,提出了一种基于损失率估算的可变缓冲管理模型。该模型将缓冲区拥塞视为顾客损失,建立M/M/I/K损失排队系统,根据实时变化的数据流速率和有效处理能力,周期性计算、调整缓冲区大小,以提高资源利用率并保障缓冲区通畅。     

Approximation von Leistungsgrößen symmetrischer Mehrprozessorsysteme

In the modelling of computer systems, especially multiprocessor systems, for performance evaluation are mostly formulae needed for the computation of the performance measures such as queue lengths or response times for M/M/m-, M/G/m- or G/G/m-queueing systems. For M/M/m-systems there exist exact formulae which are very complex compared to M/M/1-formulae. There exist only approximate formulae for M/G/m- and G/G/m-systems. In the first part of the work approximate formulae are derived for the mean queue lengths, waiting time distributions and steady state probabilities for M/M/m-systems. These obtained formulae are as well easy as the M/M/1-formulae and though amazingly very accurate. These solutions are partly extended to M/G/m- and G/G/m-queueing systems in the second part of the work. It is also shown that the known approximate formulae compared to these results are unessentially more accurate but essentially more complex.     

基于分组到达率的802.11 DCF性能分析

针对WLAN(wireless local area network)基础结构模式中的IEEE 802.11 DCF(distributed coordination function)机制,提出了一种基于分组到达率的性能分析模型.模型不仅考虑了终端数量、传输负载、二进制指数回退机制等因素,而且分析了MAC(mediunl access control)层有限队列对系统性能的影响.在每个终端被模型化为M/M/1/K队列的基础上,进一步利用虚拟时隙在时间上离散化终端MAC层队列状态,并采用离散时间的三维马尔可夫链对系统性能建模.基于该模型得到了归一化吞吐量、分组时延和丢包率.仿真分析结果表明,该模型能够有效地预测变化的分组到达率情形下DCF机制的性能.     

Performance of a beacon enabled IEEE 802.15.4 cluster with downlink and uplink traffic

The performance of an IEEE 802.15.4 compliant network operating in the beacon enabled mode with both downlink and uplink traffic is analyzed through discrete time Markov chains and the theory of M/G/1 queues. The model considers acknowledged transmissions and includes the impact of different network and traffic parameters such as the packet arrival rate, packet size, inactive period between the beacons, and the number of stations. We investigate the nonsaturation region and outline the conditions under which the network abruptly goes to saturation. The analysis of stability of the network queues shows that the stability of the downlink queue at the coordinator is the most critical for network operation. Due to the abruptness with which the switch from nonsaturation to saturation occurs, the network operating point has to be carefully chosen according to the volume of downlink traffic. Furthermore, our model shows that certain features prescribed by the standard actually limit the performance of 802.15.4 networks.     

基于混合制排队模型的SDN控制器性能评估研究

软件定义网络SDN将逻辑控制与数据转发相分离,提高了网络的灵活性和可编程能力,成为近年来未来网络领域的研究热点。SDN在实际应用部署时将面临控制器性能瓶颈的挑战,因而有必要理解SDN控制器的性能特性。为此,首先对SDN控制器中Packet-In消息的到达过程和处理时间进行分析,进而基于排队论提出了一种容量有限的SDN控制器性能评估模型M/M/1/m,推导得出了该模型的性能参数,包括:平均等待队长、平均等待时间、平均队列长度和平均逗留时间。最后,采用控制器性能测试工具Cbench对该模型进行了实验评估。实验结果表明:相对于现有其它模型,该模型的估计时延更接近于实际测量时延,可更精确地描述SDN控制器的性能。     

Information theoretic approximations for M/G/1 and G/G/1 queuing systems

Summary This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.     

On the overflow processes from the PH1 + PH2/M/S/K queue with two independent PH-renewal inputs

This paper presents an analysis of overflow processes from a PH₁ + PH₂/M/S/K queue having two independent phase type renewal input streams. Both the superposed overflow process and individual overflow processes for the PH₁- and PH₂-streams are analyzed using first passage time distributions for the number of customers in the system. Each overflow process is characterized as a Markov renewal process. The nth moment of the number of customers in an infinite server group to which these overflows have been offered is derived using a theory for the MR/M/∞ queue with a Markov renewal input. The numerical examples for means and variance-to-mean ratios (peakednesses) of the individual overflow streams are given for an H₂ + H₂/M/S/S queue with interrupted Poisson inputs, which is a vital model for telephone network planning. In addition, overflow traffic characteristics are discussed by using these examples.