一种改进的M/D/1模型及其应用的研究

M/D/1模型(M表示到达时间间隔为指数分布,D表示服务时间间隔为定长分布,1表示单服务台)是一种常见的排队模型,在生活的很多领域都会遇到。但是实际生活中的排队过程常常不是平稳过程,顾客到达率往往跟时间有显著相关的关系。针对这一个问题,以上海世博会的排队系统为例,将全天排队过程划分为若干时间区间,将每个时间区间内的排队过程视为平稳过程。并对其全天到达率做线性假设,给出排队系统各参数指标的递推公式。进而对全天排队情况进行预测,预测结果表明该方法行之有效。     

一种基于M/D/1排队模型的可用带宽测量算法

由于液体流模型不能反映实际背景流的突发性及包长分布,基于液体流模型的可用带宽测量技术在突发背景流及多跳链路下测量精度较低.因此,提出了一种基于M/D/1排队模型的高精度可用带宽测量算法FPU(five-packet-unit for available bandwidth measurement).该算法采用五包结构构...     

An M/D/1 Queueing System with Partial Synchronization of Its Incoming Flow and Demands Repeating at Constant Intervals

A one-channel queueing system with Poisson input flow, a constant service time, and a constant time of being in orbit is considered. The system admits of synchronization of its input flow. Some indicators of efficiency of operation of the system are deduced and numerical calculations are presented.     

Optimal management for infinite capacity N-policy M/G/1 queue with a removable service station

In this article, we consider an infinite capacity N-policy M/G/1 queueing system with a single removable server. Poisson arrivals and general distribution service times are assumed. The server is controllable that may be turned on at arrival epochs or off at service completion epochs. We apply a differential technique to study system sensitivity, which examines the effect of different system input parameters on the system. A cost model for infinite capacity queueing system under steady-state condition is developed, to determine the optimal management policy at minimum cost. Analytical results for sensitivity analysis are derived. We also provide extensive numerical computations to illustrate the analytical sensitivity properties obtained. Finally, an application example is presented to demonstrate how the model could be used in real applications to obtain the optimal management policy.     

M/G/1排队网络系统性能研究

本论文以单一路由器(服务器)为例,从最原始的队列理论出发,探讨具有容量C的M/G/1队列模型的系统平均时延、系统稳态下的报文(用户)平均值、以及时延等问题。并对报文(用户)的服务质量需求作了详尽的数学推导。     

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

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

基于M/G/1/K排队理论的IEEE 802.15.4网络吞吐量分析

针对IEEE 802.15.4时隙载波侦听多址接入与碰撞避免（CSMA/CA）算法,利用二维Markov链分析方法提出了一个网络分析模型。该模型特别考虑了IEEE 802.15.4协议的休眠模式以及退避窗口先于退避阶数(NB)达到最大值的情况。在此基础上,结合M/G/1/K排队理论推导得到了吞吐量的表达式,进而分析了网络在非饱和状态下数据包到达率对吞吐量的影响,利用模拟平台NS2进行了仿真。实验结果显示理论分析结果与仿真结果可以较好地拟合,并能准确描述网络吞吐量的变化,验证了分析模型的有效性。     

Analysis of the M/G/1 queue with discriminatory random order service policy

We consider an M/G/1 queue with different classes of customers and discriminatory random order service (DROS) discipline. The DROS discipline generalizes the random order service (ROS) discipline: when the server selects a customer to serve, all customers waiting in the system have the same selection probability under ROS discipline, whereas customers belonging to different classes may have different selection probabilities under DROS discipline. For the M/G/1 queue with DROS discipline, we derive equations for the joint queue length distributions and for the waiting time distributions of each class. We also obtain the moments of the queue lengths and the waiting time of each class. Numerical results are given to illustrate our results.     

M/M/1-PS queue and size-aware task assignment

We consider a distributed server system in which heterogeneous servers operate under the processor sharing (PS) discipline. Exponentially distributed jobs arrive to a dispatcher, which assigns each task to one of the servers. In the so-called size-aware system, the dispatcher is assumed to know the remaining service requirements of some or all of the existing jobs in each server. The aim is to minimize the mean sojourn time, i.e., the mean response time. To this end, we first analyze an M/M/1-PS queue in the framework of Markov decision processes, and derive the so-called size-aware relative value of state, which sums up the deviation from the average rate at which sojourn times are accumulated in the infinite time horizon. This task turns out to be non-trivial. The exact analysis yields an infinite system of first order differential equations, for which an explicit solution is derived. The relative values are then utilized to develop efficient dispatching policies by means of the first policy iteration (FPI). Numerically, we show that for the exponentially distributed job sizes the myopic approach, ignoring the future arrivals, yields an efficient and robust policy when compared to other heuristics. However, in the case of highly asymmetric service rates, an FPI based policy outperforms it. Additionally, the size-aware relative value of an M/G/1-PS queue is shown to be sensitive with respect to the form of job size distribution, and indeed, the numerical experiments with constant job sizes confirm that the optimal decision depends on the job size distribution.     

数据队列在AS／400的C／S编程模式中的应用

本文讨论了数据队列技术的原理,并通过一个实例分析了如何利用数据队列技术实现ＡＳ／４００和ＰＣ程序间的高速数据交换。     

基于大偏差统计模型的Http-Flood DDoS 检测机制及性能分析

针对Http洪泛Web DDoS(distributed denial of service)攻击,提出了一种检测机制.该机制首先采用型方法量化处理用户访问的网页序列,以得到用户访问不同网页的实际点击概率分布;然后,利用大偏差统计模型分析了用户访问行为的实际点击概率分布与网站先验概率分布的偏差;最后,依据大偏差概率检测恶意DDoS攻击.对该机制的性能进行仿真,结果表明,正常用户的大偏差概率大于恶意攻击者,并且大部分正常用户的大偏差概率大于10-36,而大部分恶意攻击者的大偏差概率则小于10-40由此,该机制能够有效地检测Http洪泛Web DDoS攻击,当检测门限设置为10-60时,其有效检测率可达97.5％,而误检率仅为0.6％.另外,将该机制与基于网页转移概率的检测方法进行性能比较,结果表明,该检测机制的检测率优于基于网页专业概率的检测机制,并且在误检率小于5％的情况下,该机制的检测率比现有检测机制提高0.6％.     

Randomized control of T-policy for an M/G/1 system

We study an M/G/1 queueing system with a server that can be switched on and off. The server can take a vacation time T after the system becomes empty. In this paper, we investigate a randomized policy to control a server with which, when the system is empty, the server can be switched off with probability p and take a vacation or left on with probability (1 − p) and continue to serve the arriving customers. For this system, we consider the operating cost and the holding cost where the operating cost consists of the system running and switching costs (start up and shut down costs). We describe the structure and characteristics of this policy and solve a constrained problem to minimize the average operating cost per unit time under the constraint for the holding cost per unit time.     

基于大偏差统计模型的Http-Flood DDoS检测机制及性能分析?

针对Http洪泛Web DDoS(distributed denial of service)攻击,提出了一种检测机制.该机制首先采用型方法量化处理用户访问的网页序列,以得到用户访问不同网页的实际点击概率分布;然后,利用大偏差统计模型分析了用户访问行为的实际点击概率分布与网站先验概率分布的偏差;最后,依据大偏差概率检测恶意DDoS攻击.对该机制的性能进行仿真,结果表明,正常用户的大偏差概率大于恶意攻击者,并且大部分正常用户的大偏差概率大于10?36,而大部分恶意攻击者的大偏差概率则小于10?40.由此,该机制能够有效地检测Http洪泛Web DDoS攻击,当检测门限设置为10?60时,其有效检测率可达97.5%,而误检率仅为0.6%.另外,将该机制与基于网页转移概率的检测方法进行性能比较,结果表明,该检测机制的检测率优于基于网页专业概率的检测机制,并且在误检率小于5%的情况下,该机制的检测率比现有检测机制提高0.6%.     

On the M/Ck/1 queue

We obtain the exact analytic expression of the probability distribution of the number of units in a single server queue with Poisson arrivals and Coxian service time distribution (notated as M/C_k/1). A recursive procedure for calculating this probability distribution is given. The well-known queues M/E_k/1 and M/D/1 are re-derived as special cases of the M/C_k/1 queue. Finally, the cases of M/C₂/1 and M/C₃/1 are fully worked out.     

An Elementary Derivation of the Large Deviation Rate Function for Finite State Markov Chains

Large deviation theory is a branch of probability theory that is devoted to a study of the “rate” at which empirical estimates of various quantities converge to their true values. The object of study in this paper is the rate at which estimates of the doublet frequencies of a Markov chain over a finite alphabet converge to their true values. In the case where the Markov process is actually an independent and identically distributed (i.i.d.) process, the rate function turns out to be the relative entropy (or Kullback‐Leibler divergence) between the true and the estimated probability vectors. This result is a special case of a very general result known as Sanov's theorem and dates back to 1957. Moreover, since the introduction of the “method of types” by Csiszar and his co‐workers during the 1980s, the Proof of this version of Sanov's theorem has been “elementary,” using some combinatorial arguments. However, when the i.i.d. process is replaced by a Markov process, the available Proofs are far more complex. The main objective of this paper is therefore to present a first‐principles derivation of the LDP for finite state Markov chains, using only simple combinatorial arguments (e.g. the method of types), thus gathering in one place various arguments and estimates that are scattered over the literature. The approach presented here extends naturally to multi‐step Markov chains.     

M/M/s等待制排队模型在教务员岗位数量确定中的应用

论述了排队论中M／M／s等待制模型确定教务员数量的分析步骤和方法原理，结合沈阳农业大学高等职业技术学院实际情况，确定了合理的教务员数量。     

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.     

Comparison of stability and queueing times for reader-writer queues

A reader-writer queue manages two classes of customers: readers and writers. An unlimited number of readers can be processed in parallel; writers are processed serially. Both classes arrive according to a Poisson process. Reader and writer service times are general iid random variables. There is infinite room in the queue for waiting customers.

In this paper, a reader-writer queue is considered under the following priority disciplines: strong reader preference (SRP), reader preference (RP), alternating exhaustive priority (AEP), writer preference (WP), and strong writer preference (SWP). Preemptive priority is given to readers under the SRP discipline, or to writers under the SWP discipline. Non-preemptive priority is accorded to readers with the RP discipline, or to writers with the WP discipline. For the AEP discipline, customers of a given class are served exhaustively in an alternating fashion.

For the five priority disciplines, a stability condition and first moments for the steady-state reader and writer queueing times are given. Using these analytical results, each of the five priority disciplines is seen to be optimal (among the five) in some region of the parameter space. Simulation results are also presented.     

Analysis of waiting time of M/G/1/K system with vacations under random scheduling and LCFS

This paper considers an M/G/1/K queueing system with multiple vacations under random scheduling and LCFS disciplines. As for M/G/1/K vacation models, Lee obtained the results of the joint distribution of the number of messages in the system and the remaining service or vacation time for a message. Using these expressions, we derive LSTs of the waiting time distribution under the two service disciplines. We show the calculation method for the first and the second moments of the waiting time under two service disciplines. Furthermore, we illustrate some numerical results of the mean waiting times and the coefficient of variations of the waiting time under FCFS, random scheduling and LCFS.