Approximation for the departure process of a queue in a network

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component-renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.     

Approximations for departure processes and queues in series

Methods are developed for approximately characterizing the departure process from a single-server queue and calculating approximate congestion measures for several single-server queues in series. These methods are modifications of the previously described asymptotic method and stationary-interval method for approximating a stochastic point process. The approximations are evaluated by comparing approximate congestion measures for queues in series with previous simulation results.     

Algorithmic and approximation analyses of the shorter queue model

A system of two parallel queues where the arrivals from a single stream of customers join the shorter queue is considered. Arrivals form a homogeneous Poisson stream and the service times in each of the two queues are independent exponential variates. By treating one of the queues as bounded, the steady-state probability vector for the system can be expressed in a modified matrix-geometric form and can be computed efficiently. Computational procedures for the sojourn time distribution and characteristics of the departure stream are developed. Some numerical results are presented, and based on these results an efficient approximation scheme for the model is developed which can be readily extended to systems with more than two parallel queues.     

The single server queue in discrete time-numerical analysis I

This is the first of a sequence of papers dealing with the computational aspects of the transient behavior of queues in discrete time It is shown that for a substantial class of queues of practical interest, a wealth of numerical information may be obtained by relatively unsophisticated methods This approach should prove useful in the analysis of unstable queues which operate over a limited time interval, but is by no means limited to such queues Mathematically the service unit is modeled in terms of a multivariate Markov chain, whose particular structure is used in iterative computation. Many important queue features may then be derived from the n-step transition probabilities of this chain.     

Some order relations in closed networks of queues with multiserver stations

Consider a closed network of queues of the “product-form” type, where each station has s servers (s ≥ 1 is identical for all stations). We show that the throughput function of the network is Schur concave with respect to the loading of the stations and arrangement increasing with respect to the assignment of server groups. Consequently, different loading/assignment policies can be compared under majorization/arrangement orderings and their relative merits decided according to the yields of throughput. The results can be used to support planning decisions in computer and production systems which are modeled as closed networks of queues.     

Allocating capacity in parallel queues to improve their resilience to deliberate attack

We develop models that lend insight into how to design systems that enjoy economies of scale in their operating costs, when those systems will subsequently face disruptions from accidents, acts of nature, or an intentional attack from a well‐informed attacker. The systems are modeled as parallel M/M/1 queues, and the key question is how to allocate service capacity among the queues to make the system resilient to worst‐case disruptions. We formulate this problem as a three‐level sequential game of perfect information between a defender and a hypothetical attacker. The optimal allocation of service capacity to queues depends on the type of attack one is facing. We distinguish between deterministic incremental attacks, where some, but not all, of the capacity of each attacked queue is knocked out, and zero‐one random‐outcome (ZORO) attacks, where the outcome is random and either all capacity at an attacked queue is knocked out or none is. There are differences in the way one should design systems in the face of incremental or ZORO attacks. For incremental attacks it is best to concentrate capacity. For ZORO attacks the optimal allocation is more complex, typically, but not always, involving spreading the service capacity out somewhat among the servers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

On a large sample test for the traffic intensity in GI|G|s queue

A large sample test based on normal approximation for the traffic intensity parameter ρ in the cases of single and multiple-server queues has been proposed. The test procedure is developed without imposing steady-state assumptions and is applicable to queueing systems with general interarrival and service-time distributions.     

Optimal control of multi-channel service systems

D. P. Heyman, M. Sobel, and M. J. Magazine among others have shown existence of an optimal policy for control of single server queuing systems. For queues under periodic review existence of an analogous rule is established for multi-server systems. Formulation as a dynamic programming problem is given and proofs for existence are presented for finite horizon, infinite horizon and average cost criteria.     

Bilateral phase-type distributions

In this article we define a class of distributions called bilateral phase type (BPH), and study its closure and computational properties. The class of BPH distributions is closed under convolution, negative convolution, and mixtures. The one-sided version of BPH, called generalized phase type (GPH), is also defined. The class of GPH distributions is strictly larger than the class of phase-type distributions introduced by Neuts, and is closed under convolution, negative convolution with nonnegativity condition, mixtures, and formation of coherent systems. We give computational schemes to compute the resulting distributions from the above operations and extend them to analyze queueing processes. In particular, we present efficient algorithms to compute the steady-state and transient waiting times in GPH/GPH/1 queues and a simple algorithm to compute the steady-state waiting time in M/GPH/1 queues.     

平面杆系结构内力包络图仿真优化与编程

讨论受任意集中力、集中力偶和线性分布力等复杂移动荷载作用下的平面杆系结构内力包络图仿真优化技术。借助平面杆系结构分析软件Vsap2011,分析了单元截面离散方式和荷载移动步长对内力包络图求解精度的影响。研究表明:为了获得较高的内力包络图求解精度,对于移动荷载经过的单元,截面必须按步细分;对于活载任意布置的单元,截面必须在荷载作用点之间再插入足够多的分点;对于不受荷载的单元,两端刚结的必须按距离细分,而含有一个以上铰结点的不必细分。此外,在步长接近或相差不大的情况下,如果步长既能整除荷载队列的间距,又能整除载荷载通过单元的长度,那么就可以提高内力包络图的求解精度。如果将单元长度和荷载队列间距的最大公约数作为步长,既可获得较高的内力包络图求解精度,又可大大节省计算机时。     

On queues with state-dependent Erlang service

Some general results are derived for single-channel queues with Poisson input and state-dependent Erlang service times in view of the possible use of this model to approximate arbitrary M/G/1-like state-dependent queues in a manner similar to that suggested by Rosenshine, and by Kendall, and Kotiah, Thompson, and Waugh for the M/G/1. Numerical procedures are indicated for the evaluation of stationary state probabilities, expected system sizes and waiting times, and parameter estimation.     

Level crossing analysis of priority queues and a conservation identity for vacation models

The two purposes of this article are to illustrate the power and simplicity of level crossing analysis and to present a conservation identity for M/G/1 priority queues with server vacations. To illustrate the use of level crossing analysis we apply it to preemptive (resume) priority M/G/1 queues with single- and multiple-server vacations considered by Kella and Yechiali (1986) and to non-preemptive priority M/M/c queues considered by Kella and Yechiali (1985). The conservation identity presented here states that the ratios of mean waiting times in an M/G/1 queue with and without server vacation policies are independent of the service discipline for first come first served, shortest processing time, shortest processing time within generations and non-preemptive priority service disciplines.     

Waiting-time distributions for bulk arrival,bulk service queues with vehicle-holding and cancellation strategies

Procedures are developed for numerically calculating the waiting-time distribution for bulk arrival, bulk service queues operated under a vehicle-cancellation or a vehicle-holding strategy, as well as for queues where vehicles depart regardless of the length of the queue. Experiments indicate that the mean and variance of the calculated distribution agree very closely with analytical expressions obtained from transforms. The results can be used to study the service reliability of different dispatching strategies. Alternatively, the results may be used to evaluate simpler approximations for the higher moments.     

An approximation for the waiting time distribution in single server queues

Single server queues with general interarrival and service times are approximated by queues with two-point (Bernoulli) interarrival times and exponential service times. The parameters are chosen such that the first four moments of the difference of the service times and interarrival times in the approximating system equal those of the original system. The aptness of the approximation is discussed and some examples are presented comparing the exact and approximate waiting time distributions. A more complicated approximation is presented using the dual system (exponential arrivals, Bernoulli service) for those cases where the original approximation cannot be used.     

Single server queues with hyperexponential service times

Single server queues with hyperexponential service times are studied. Explicit expressions are derived for the waiting time and state distributions.     

Analysis of a finite‐buffer bulk‐service queue with discrete‐Markovian arrival process: D‐MAP/Ga,b/1/N

Discrete‐time queues with D‐MAP arrival process are more useful in modeling and performance analysis of telecommunication networks based on the ATM environment. This paper analyzes a finite‐buffer discrete‐time queue with general bulk‐service rule, wherein the arrival process is D‐MAP and service times are arbitrarily and independently distributed. The distributions of buffer contents at various epochs (departure, random, and prearrival) have been obtained using imbedded Markov chain and supplementary variable methods. Finally, some performance measures such as loss probability and average delay are discussed. Numerical results are also presented in some cases. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 345–363, 2003.     

光互连网络中资源预留的多级光互连仲裁机制

基于资源预留策略提出一种多级光互连仲裁机制,通过将网络分级实现快速、高效的仲裁。多优先级数据缓存队列的传输节点设计,提供了不同类型流量的差异化传输;通过预约式两级仲裁机制,实现网络的完全公平与100%的高吞吐率。设计并对快速仲裁通道进行了合理布局,极大地缩短了仲裁延迟。仿真结果表明:采用基于资源预留的分级仲裁策略,在多种流量模式下所有节点均获得公平的服务。与Feather Weight相比,分级仲裁策略吞吐率提高17%;与2-pass相比,仲裁延迟减少15%,同时,功耗减少5%。     

带脉冲负荷的电站柴油机动态性能分析

通过对某一个在脉冲负荷作用下配置了液压调速器的电站柴油机系统的动态仿真计算 ,确定了改善这类系统动态性能的方法 ,并通过调整使系统动态性能达到了要求     

The effect of correlated exponential service times on single server tandem queues

An investigation via simulation of system performance of two stage queues in series (single server, first-come, first-served) under the assumption of correlated exponential service times indicates that the system's behavior is quite sensitive to departures from the traditional assumption of mutually independent service times, especially at higher utilizations. That service times at the various stages of a tandem queueing system for a given customer should be correlated is intuitively appealing and apparently not at all atypical. Since tandem queues occur frequently, e.g. production lines and the logistics therewith associated, it is incumbent on both the practitioner and the theoretician that they be aware of the marked effects that may be induced by correlated service times. For the case of infinite interstage storage, system performance is improved by positive correlation and impaired by negative correlation. This change in system performance is reversed however for zero interstage storage and depends on the value of the utilization rate for the case where interstage storage equals unity. The effect due to correlation is shown to be statistically significant using spectral analytic techniques. For correlation equal unity and infinite interstage storage, results are provided for two through twenty-five stages in series to suggest how adding stages affects system performance for ρ>0. In this extreme case of correlation, adding stages has an effect on system performance which depends markedly on the utilization rate. Recursive formulae for the waiting time per customer for the cases of zero, one, and infinite interstage storage are derived.     

通信设备及其网络仿真训练模型的分析

根据通信设备及其网络的特点和通信业务训练的要求 ,提出了层次化结构的仿真训练模型 ,并提供和分析了各层建模方法和编程技术。然后介绍了通信设备及其网络仿真训练系统的典型实例 ,结果表明 :该模型对于建立通信设备及其网络仿真训练系统具有易于代码开发、易于理解、易于维护管理、易于系统功能扩展的特点。