MRE hierarchical decomposition of general queueing network models

Summary The principle of Minimum Relative Entropy (MRE), given fully decomposable subset and aggregate mean queue length, utilisation and flow-balance constraints, is used in conjunction with asymptotic connections to infinite capacity queues, to derive new analytic approximations for the conditional and marginal state probabilities of single class general closed queueing network models (QNMs) in the context of a multilevel variable aggregation scheme. The concept of subparallelism is applied to preserve the flow conservation and a universal MRE hierarchical decomposition algorithm is proposed for the approximate analysis of arbitrary closed queueing networks with single server queues and general service-times. Heuristic criteria towards an optimal coupling of network's units at each level of aggregation are suggested. As an illustration, the MRE algorithm is implemented iteratively by using the Generalised Exponential (GE) distributional model to approximate the service and asymptotic flow processes in the network. This algorithm captures the exact solution of separable queueing networks, while for general queueing networks it compares favourably against exact solutions and known approximations.This work is sponsored by the Science and Engineering Research Council (SERC), UK, under grant GR/F29271     

A hybrid method for performance analysis of G/G/m queueing networks

Open queueing networks are useful for the performance analysis of numerous real systems. Since exact results exist only for a limited class of networks, decomposition methods have been extensively used for approximate analysis of general networks. This procedure is based on several approximation steps. Successive approximations made in this approach can lead to a considerable error in the output. In particular, there are no general accurate formulas for computing the mean waiting time and the inter-departure variance in general multiple-server queues. This causes the results from decomposition methods when applied to G/G/m queueing networks to be very approximative and to significantly deviate from actual performance values. We suggest substituting some approximate formulae by low-cost simulation estimates in order to obtain more accurate results when benefiting from the speed of an analytical method. Numerical experiments are presented to show that the proposed approach provides improved performance.     

Machine allocation algorithms for job shop manufacturing

In this paper we present algorithms for the solution of two server (machine) allocation problems that occur in manufacturing networks. The manufacturing network is modelled as an open network of queues with general interarrival time and service time distributions. The queueing network is analyzed by using the parametric decomposition method: a two-moment approximation scheme. The server allocation problems are solved by means of a marginal analysis scheme. Numerical results on two manufacturing networks are presented.     

A review on queueing network models with finite capacity queues for software architectures performance prediction

A review is carried out on how queueing network models with blocking have been applied so far into the performance evaluation and prediction of Software Architectures (SA). Queueing network models with finite capacity queues and blocking have recently been introduced and applied as more realistic models of systems with finite capacity resources and population constraints. Queueing network models have been often adopted as models for the evaluation of software performance. Starting from our own experience, we observe the need of a more accurate definition of the performance models of SA to capture some features of the communication systems. We consider queueing networks with finite capacity and blocking after service (BAS) to represent some synchronization constraints that cannot be easily modeled with queueing network models with infinite capacity queues. We investigate the use of queueing networks with blocking as performance models of SA with concurrent components and synchronous communication. Queueing theoretic analysis is used to solve the queueing network model and study the synchronous communication and performance of concurrent software components. Our experience is supported by other approaches that also propose the use of queueing networks with blocking. Directions for future research work in the field are included.     

Netfilter/Iptables框架下基于TCP滑动窗口的串行流量控制算法

传统的基于流量整形的流量控制算法通常需要建立对应的队列模型,实施起来极为复杂,而且所有数据包都要进入整形队列,加大了网络延时。本文从TCP协议拥塞控制和数据包组包机制出发,提出了基于TCP滑动窗口的串行流量控制算法,通过改变TCP发送端窗口的大小来达到流量控制的目的。本文在Linux内核Netfilter/iptables框架中实现了该流量控制方法,在部署的网络环境中,比较了不同参数设置下的算法效果。与CBQ算法相比,该方法降低了数据包在队列中排队整形的延时。     

基于自相似通信量的p-坚持CSMA/CD协议仿真

近年来,大量的通信量测量研究表明实际的网络通信量具有自相似或长范围相关特性。为了准确评估军用网络的性能,论文利用叠加多个ON/OFF信源的方法,建立了自相似通信量模型,并对该模型所产生的序列进行检测,验证了其自相似特性;在此基础上,基于自相似通信量,采用离散事件仿真技术对军用网络中的p-坚持CSMA/CD协议建立了排队模型,通过仿真测试了各种负载下p值对冲突次数、平均等待时间、平均队长以及吞吐率等性能指标的影响,仿真结果表明,根据信道负载的轻重,动态调整p的取值可以提高网络的性能。     

On the nonconcavity of throughput in certain closed queueing networks

Analytic queueing network models are being used to analyze various optimization problems such as server allocation, design and capacity issues, optimal routing, and workload allocation. The mathematical properties of the relevant performance measures, such as throughput, are important for optimization purposes and for insight into system performance.We show that for closed queueing networks of m arbitrarily connected single server queues with n customers, throughput, as a function of a scaled, constrained workload, is not concave. In fact, the function appears to be strictly quasiconcave. There is a constraint on the total workload that must be allocated among the servers in the network. However, for closed networks of two single server queues, we prove that our scaled throughput is concave when there are two customers in the network and strictly quasi-concave when there are more than two customers. The mathematical properties of both the scaled throughput and reciprocal throughput are demonstrated graphically for closed networks of two and three single server queues.     

A delay model of queueing network system based on fuzzy sets theory

The goal of our research is the delay analysis of queueing model for data networks using fuzzy sets theory. We propose an fuzzification of M/M/1 queueing system. We also apply fuzzy sets theory to the open central server network model with the fuzzy queues. Thus, we represent the delay analysis and performance of open central server network model based on fuzzy sets theory.     

Adaptive back-pressure congestion control based on localinformation

The problem of distributed congestion control as it arises in communication networks as well as in manufacturing systems is studied in this paper. In particular, a multistage queueing system that models virtual circuit and datagram communication networks and a class of manufacturing systems are considered. The topology may be arbitrary, there are multiple traffic classes, and the routing can be class dependent, with routes that may form direct or indirect loops. The model incorporates the functions of transmission scheduling, flow control, and routing, through which congestion control is performed in the network. A policy is given that performs these functions jointly. According to the policy, heavily loaded queues are given higher priority in service. A congested node may reduce the how from upstream nodes through a flow control mechanism. Whenever routing is required, it is performed in such a manner that the lightly loaded queues receive most of the traffic. For arrival processes with bounded burstiness, the policy guarantees bounded backlogs in the network, as long as the load of each server is less than one. The actions of each server are based on the state of its own queues and of the queues one hop away. Therefore, they are implementable in a distributed fashion. An adaptive version of the policy is also provided which makes it independent of the arrival rates     

LRD and SRD traffic: review of results and open issues for the batch renewal process

The batch renewal process is the least-biased choice of process given only the measures of count correlation and interval correlation at all lags.

This paper reviews the batch renewal process, both for LRD (long-range-dependent) traffic and for SRD (short-range-dependent) traffic in the discrete space–discrete time domain, and in the wider context of general traffic in that domain. It shows some applications of the batch renewal process in simple queues and in queueing network models. The paper concludes with open research problems and issues arising from the discussion.     

Non-asymptotic end-to-end performance bounds for networks with long range dependent fBm cross traffic

Fractional Brownian motion (fBm) emerged as a useful model for self-similar and long-range dependent aggregate Internet traffic. Asymptotic, respectively, approximate performance measures are known for single queueing systems with fBm through traffic. In this paper end-to-end performance bounds for a through flow in a network of tandem queues under open-loop fBm cross traffic are derived. To this end, a rigorous sample path envelope for fBm is proven that complements previous approximate results. The sample path envelope and the concept of leftover service curves are employed to model the remaining service after scheduling fBm cross traffic at a queuing system. Using composition results for tandem systems from the stochastic network calculus end-to-end statistical performance bounds for individual flows in networks under fBm cross traffic are derived. The discovery is that these bounds grow in O(n(logn)^1/(2-2H)) for n systems in series where H is the Hurst parameter of the cross traffic. Explicit results on the impact of the variability and the burstiness of through and cross traffic on network performance are shown. Our analysis has direct implications on fundamental questions in network planning and service management.     

An analytical model for torus networks in the presence of batch message arrivals with hot-spot destinations

Interconnection networks are hardware fabrics supporting communications between individual processors in multi- computers. The low-dimensional k-ary n-cubes （or torus） with adaptive wormhole switching have attracted significant research efforts to construct high-performance interconnection networks in contemporary multi-computers. The arrival process and destination distribution of messages have great effects on network performance. With the aim of capturing the characteristics of the realistic traffic pattern and obtaining a deep understanding of the performance behaviour of interconneetion networks, this paper presents an analytical model to investigate the message latency in adaptive-routed wormhole-switched torus networks where there exists hot-spot nodes and the message arrivals follow a batch arrival process. Each generated message has a given probability to be directed to the hot-spot node. The average degree of virtual channel multiplexing is computed by the GE/G/1/V queueing system with finite buffer capacity. We compare analytical results of message latency with those obtained through the simulation experiments in order to validate the accuracy of the derived model.     

基于IP网络规划与设计的抖动模型的研究

提出了一个典型的模型,该模型考虑到包延时的相关性和串联队列的相关性,这对端到端的抖动有重要影响。针对一个单队列的Poisson流量分布的抖动,给出了一个非常易于计算的公式,然后推广到基于串联队列的标记流的端到端抖动。通过模拟实验可以发现,模型的分析值和模拟值基本吻合,在大流量背景下更为精确,更重要的是对于抖动而言该值是可信的,这样就可以用于网络设计过程中。     

Performance analysis of networks of queues under active queue management scheme

Analysis of networks of queues under repetitive service blocking mechanism has been presented in this paper. Nodes are connected according to an arbitrary configuration and each node in the networks employs an active queue management (AQM) based queueing policy to guarantee certain quality of service for multiple class external traffic. This buffer management scheme has been implemented using queue thresholds. The use of queue thresholds is a well known technique for network traffic congestion control. The analysis is based on a queue-by-queue decomposition technique where each queue is modelled as a GE/GE/1/N queue with single server, R (R ⩾ 2) distinct traffic classes and {N = N₁, N₂, … , N_R} buffer threshold values per class under first-come-first-serve (FCFS) service rule. The external traffic is modelled using the generalised exponential (GE) distribution which can capture the bursty property of network traffic. The analytical solution is obtained using the maximum entropy (ME) principle. The forms of the state and blocking probabilities are analytically established at equilibrium via appropriate mean value constraints. The initial numerical results demonstrate the credibility of the proposed analytical solution.     

Decomposition of general tandem queueing networks with MMPP input

For tandem queueing networks with generally distributed service times, decomposition often is the only feasible solution method besides simulation. The network is partitioned into individual nodes which are analyzed in isolation. In most existing decomposition algorithms for continuous-time networks, the output of a queue is usually approximated as a renewal process, which becomes the arrival process to the next queue. In this paper, the internal traffic processes are described as semi-Markov processes (SMPs) and Markov modulated Poisson processes (MMPPs). Thus, correlations in the traffic streams, which are known to have a considerable impact on performance, are taken into account to some extent. A two-state MMPP, which arises frequently in communications modeling, serves as input to the first queue of the tandem network. Furthermore, the single nodes may have infinite or finite buffers. Customers who arrive at a full buffer will get lost.

In principle, the analysis of an individual queue as an MMPP/G/1(/K) system delivers a wide range of performance measures. For different examples of tandem networks, stationary mean queue lengths at arbitrary time are compared to simulation data. The relative errors of the results, which are computed promptly by the decomposition component of the tool TimeNET, remain within a reasonable range.     

Analysis of GI/M/s/c queues using uniformisation

We combine uniformisation, a powerful numerical technique for the analysis of continuous time Markov chains, with the Markov chain embedding technique to analyze GI/M/s/c queues. The main steps of the proposed approach are the computation of

• (1)the mixed-Poisson probabilities associated to the number of arrival epochs in the uniformising Poisson process between consecutive customer arrivals to the system; and
• (2)the conditional embedded uniformised transition probabilities of the number of customers in the queueing system immediately before customer arrivals to the system.

To show the performance of the approach, we analyze queues with Pareto interarrival times using a stable recursion for the associated mixed-Poisson probabilities whose computation time is linear in the number of computed coefficients. The results for queues with Pareto interarrival times are compared with those obtained for queues with other interarrival time distributions, including exponential, Erlang, uniform and deterministic interarrival times. The obtained results show that much higher loss probabilities and mean waiting times in queue may be obtained for queues with Pareto interarrival times than for queues with the other mentioned interarrival time distributions, specially for small traffic intensities.     

Approximate analysis of product-form type queueing networks with blocking and deadlock

A numerical procedure for analyzing exactly closed exponential queueing networks with finite queues is presented first. Due to the finiteness of these queues, blocking and deadlock may occur. Deadlocks are assumed to be detected and resolved instantaneously. The numerical procedure is then incorporated in an approximation algorithm for analyzing closed exponential queueing networks of the product-form type, in which some of the queues are finite. These finite queues are assumed to be linked together to form a single subnetwork. The approximation algorithm is based on a variant of Norton's theorem. Comparisons between the approximate results and exact numerical results were carried out and the relative error was observed to be small.