Stochastic Analysis of Deterministic Routing Algorithms in the Presence of Self-Similar Traffic

Many performance models for deterministic routing in multicomputer interconnection networks have been derived and analyzed under the assumption of the traditional Poisson stochastic arrival process, which is inherently unable to capture traffic self-similarity revealed by many real-world parallel applications. In an effort towards understanding the network performance under various traffic loads and different design alternatives, this paper presents an analytical model for dimension-ordered routing in k-ary n-cubes when subjected to self-similar traffic. As the service time, blocking probability and waiting time experienced by a message vary from a dimension to another, the design of such a model for dimension-ordered routing poses greater challenges. The developed analytical model is then used to investigate the efficiency of two different ways to organize virtual channels for deterministic routing and to evaluate the impact of self-similar traffic with various Hurst parameters on network performance.     

Analytical modelling of networks in multicomputer systems under bursty and batch arrival traffic

The hypercube and torus are two important message-passing network architectures of high-performance multicomputers. Analytical models of multicomputer networks under the non-bursty Poisson traffic have been widely reported. Motivated by the convincing evidence of bursty and batch arrival nature of traffic generated by many real-world parallel applications in high-performance computing environments, we develop a new and concise analytical model in this paper for hypercube and torus networks in the presence of batch message arrivals modelled by the compound Poisson process with geometrically distributed batch sizes. The average degree of virtual channel multiplexing is derived by employing a Markov chain which can capture the batch arrival nature. An attractive advantage of the model is its constant computation complexity independent of the network size. The accuracy of the analytical performance results is validated against those obtained from simulation experiments of an actual system.     

Performance modelling of pipelined circuit switching in hypercubes with hot spot traffic

Pipelined Circuit Switching (PCS) has been suggested as an efficient switching method for supporting interprocessor communication in multicomputer networks due to its ability to preserve both communication performance and fault-tolerant demands in these networks. A number of studies have demonstrated that PCS can exhibit superior performance characteristics over Wormhole Switching (WS) under uniform traffic. However, the performance properties of PCS have not yet been thoroughly investigated in the presence of non-uniform traffic. Analytical model of PCS for common networks (e.g., hypercube) under the uniform traffic pattern has been reported in the literature. A non-uniform traffic model that has attracted much attention is the hot spot model which leads to extreme network congestion resulting in serious performance degradation due to the tree saturation phenomenon in the network. An analytical model for WS with hot spot traffic has been reported in the literature. However, to the best of our knowledge, there has not been reported any analytical model for PCS augmented with virtual channels in the presence of hot spot traffic. This paper proposes a model for this switching mechanism using new methods to calculate the probability of message header blocking and hot spot rates on channels. The model makes latency predictions that are in good agreement with those obtained through simulation experiments. An extensive performance comparison using the new analytical model reveals that PCS performs the same or in some occasions worse than WS in the presence of hot spot traffic.     

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.     

An approximate model for performance evaluation of real-time multimedia communication systems

A Markov Modulated Poisson Process (MMPP) is a doubly stochastic Poisson process which has recently received a lot of attention due to its ability to model a highly correlated arrival stream while retaining analytical tractability. In this paper, the cell arrival process from integrated voice and data sources is approximated by a two-state MMPP with batch arrivals (BMMPP). We propose a new matching technique which leads to more accurate performance prediction than other recent work for both delay estimation and evaluation of tail probabilities. While using BMMPP in the model does not noticeably increase the computational complexity over MMPP, it allows better representation of traffic sources with significantly higher burstiness. Another major contribution of the proposed model is its simplicity which makes the model suitable for real-time traffic control. An extended version of the model for integrated video, voice and data sources is also given with numerical examples again showing that the accuracy is quite satisfactory.     

基于独立MMPP业务输入模型的输入／输出排队ATM交换机性能分析方法研究

本文针对现有ATM交换机性能分析中以Poisson或Bernoulli过程作为输入业务流模型的不足,提出了一种基于独立MMPP输入业务流模型的ATM交换机性能分析方法,由于采用了MMPP过程作为输入业务流模型,因此所给出的ATM交换机性能分析方法考虑了输入业务流本身的相关特性和突发特性,从而能够给出与实际情况更接近的ATM交换机性能分析结果。     

Closed-form analysis of end-to-end network delay with Markov-modulated Poisson and fluid traffic

This paper develops a method for using traffic sources modelled as a Markov-modulated Poisson process (MMPP) and Markov-modulated fluid process (MMFP) in the framework of the bounded-variance network calculus, a novel stochastic network calculus framework for the approximated analysis of end-to-end network delay. The bounded-variance network calculus is an extension to multi-hop end-to-end paths of the Choe’s and Shroff’s Central-Limit-Theorem-based analysis of isolated network nodes. The input of the analysis is the statistical traffic envelope of sources, which is not available for generic MMPP and MMFP sources. The paper provides two statistical traffic envelopes, named two-moment and linear envelope, for general MMPP and MMFP sources, which can be used as an input of Central-Limit-Theorem-based frameworks for the analysis of network delay and, in turn, make it possible to use the rich collection of MMPP and MMFP models of voice, audio, data and video sources available in the literature. In this way, it is possible to avoid the computational complexity of traditional Markov analysis of end-to-end delay with MMPP and MMFP sources. With the linear envelope we can use simple analytical closed-form solutions for many important schedulers.     

Network Performance Under Bimodal Traffic Loads

In actual multicomputer networks, communications consist of hybrid traffic in which messages exhibit a variety of sizes. However, to date, most studies on network performance are based on traffic loads of uniformly-sized messages. We investigate the performance of wormhole-routed networks under bimodal traffic distributions, a mix of short and long messages. Our studies show that the presence of long messages degrades network performance for short messages dramatically, qualitatively changing network behavior. We present an analytical model for wormhole-routed networks which not only models network performance under uniformly sized message loads more accurately than existing models, but also can be extended to support bimodal traffic distributions. The model is validated against detailed simulation of routing networks, over a variety of message size distributions and message lengths. In virtually all cases, the model accurately predicts both network throughput and average message latency to within 8%. Because the impact of long messages can be severe, we consider three techniques-packetization, virtual lanes, and adaptive routing-to alleviate their impact. Packetization reduces the blocking time of long messages, improving network performance in most cases. Virtual lanes and adaptive routing together provide sufficient routing freedom to eliminate much of the blocking, producing performance comparable or even superior to that produced by packetization. Together, all three techniques are complementary, providing robust performance over a variety of traffic mixes and message sizes.     

Prediction of communication delay in torus networks under multiple time-scale correlated traffic

The efficiency of a large-scale multicomputer is critically dependent on the performance of its interconnection network. Current multicomputers have widely employed the torus as their underlying network topology for efficient interprocessor communication. In order to ensure a successful exploitation of the computational power offered by multicomputers it is essential to obtain a clear understanding of the performance capabilities of their interconnection networks under various system configurations. Analytical modelling plays an important role in achieving this goal. This study proposes a concise performance model for computing communication delay in the torus network with circuit switching in the presence of multiple time-scale correlated traffic which is found in many real-world parallel computation environments and has strong impact on network performance. The tractability and reasonable accuracy of the analytical model demonstrated by extensive simulation experiments make it a practical and cost-effective evaluation tool to investigate network performance with various alternative design solutions and under different operating conditions.     

非泊松工件流CSPS系统的Q学习算法适用性仿真研究

研究工件非泊松到达情况下,传送带给料加工站(CSPS)系统无法建立成半马尔可夫决策过程(SMDP)模型时, Q学习算法的适用性问题.首先,以马尔可夫调制泊松过程(MMPP)和半马尔可夫调制泊松过程(SMMPP)来模拟非泊松工件流,并在相同的平均到达率下,仿真评估其Q学习算法性能,并分别与泊松工件流情况下的Q学习算法性能进行比较:其次,在非泊松工件流情况下,观测以实时统计平均到达率作为工件标准泊松到达率的理论优化情况:最后讨论在MMPP和SMMPP叠加混合非泊松工件流情况下CSPS系统的Q学习算法性能.实验表明,在工件非泊松到达情况下Q学习算法依然能学到较好的控制策略,从而说明了CSPS系统中Q学习算法的适用性.     

Analytical queue length distributions of GPS systems with long range dependent service capacity

Generalized Processor Sharing (GPS) is an idealized scheduling mechanism with given weights assigned to individual traffic flows for service differentiation. Based on the principle of GPS, a number of variants have been proposed and deployed in real-world communication systems where the service capacity of network channels is usually variable. This paper proposes an analytical performance model for GPS systems with the variable service capacity characterized by Long Range Dependent (LRD) processes. The model is able to accommodate heterogeneous fractional Brownian motion (fBm) and Poisson traffic in multi-service networks. We derive the expressions of the queue length distributions of the GPS system and individual traffic flows. The accuracy of the analytical model is validated through comparison between analytical and simulation results.     

Discrete time analysis of leaky-bucket congestion control

Traffic control at an ATM multiplexer is of fundamental importance in B-ISDN. Due to the presence of large propagation delay, effective traffic control tends to use only local information. Leaky bucket has been introduced as a rate control method. The present paper studies the system performance of a leaky bucket controller with the arrivals being Poisson processes or Markov modulated Poisson processes (MMPP). Numerical results indicate that a small to medium sized controller is sufficient to attain the capability of a leaky bucket controller; increasing the size of the controller will not offer much improvement in performance. Controlling MMPP type of arrivals with a leaky bucket device may incur low performance especially when the burst duration is long. The performance can be improved by controlling a group of bursty users instead of a single bursty user.     

A new approach to model virtual channels in interconnection networks

Dealing with virtual channels has always been a critical issue in developing analytical performance models for interconnection networks. Almost all previous studies relied on a method proposed by Dally to capture the effect of virtual channels multiplexing in the performance of interconnection networks. This paper presents a new method to model the effect of virtual channel multiplexing in high-speed wormhole-switched interconnection networks. Dally's method loses its accuracy as the traffic load increases due to blocking nature of wormhole-switched networks. Our new method is based on a finite capacity queue, M/G/1/V and comparing to Dally's method achieves a higher degree of accuracy under low, moderate and high traffic loads. Furthermore, its simplicity eases its employment under different network conditions and setup. The presented model is validated by means of an event driven simulator and a detailed comparison with Dally's method is presented.     

Performance analysis of an integrated scheduling scheme in the presence of bursty MMPP traffic

Contemporary communication networks are expected to support multimedia applications which require diversified Quality-of-Services (QoS). An integrated scheduling discipline of Priority Queueing (PQ) and Generalized Processor Sharing (GPS), referred to as P-G, has recently emerged as a promising scheme for cost-effective QoS differentiation. In this paper, we develop a new analytical model for the integrated P-G system subject to bursty traffic. The Markov-Modulated Poisson Process (MMPP) is adopted to capture traffic burstiness because it can qualitatively model time-varying arrival rate and important correlation between inter-arrival times. To derive the desired performance metrics for individual sessions, the integrated P-G system is decomposed into a set of Single-Server Single-Queue (SSSQ) systems. Specifically, the integrated system is first divided into an SSSQ system and a GPS system. Next, a bounding approach is adopted to decompose the GPS system into individual SSSQ systems. Extensive comparisons between analytical and simulation results validate the accuracy of the analytical model. To demonstrate its merits, the model is used to investigate the configuration of the GPS weights under the QoS constraints of different traffic flows.     

Computational analysis of a Markovian queueing system with geometric mean-reverting arrival process

In the queueing literature, an arrival process with random arrival rate is usually modeled by a Markov-modulated Poisson process (MMPP). Such a process has discrete states in its intensity and is able to capture the abrupt changes among different regimes of the traffic source. However, it may not be suitable for modeling traffic sources with smoothly (or continuously) changing intensity. Moreover, it is less parsimonious in that many parameters are involved but some are lack of interpretation. To cope with these issues, this paper proposes to model traffic intensity by a geometric mean-reverting (GMR) diffusion process and provides an analysis for the Markovian queueing system fed by this source. In our treatment, the discrete counterpart of the GMR arrival process is used as an approximation such that the matrix geometric method is applicable. A conjecture on the error of this approximation is developed out of a recent theoretical result, and is subsequently validated in our numerical analysis. This enables us to calculate the performance measures with high efficiency and precision. With these numerical techniques, the effects from the GMR parameters on the queueing performance are studied and shown to have significant influences.     

pp-mess-sim: a flexible and extensible simulator for evaluatingmulticomputer networks

The paper presents pp-mess-sim, an object-oriented discrete-event simulation environment for evaluating interconnection networks in message-passing systems. The simulator provides a toolbox of various network topologies, communication workloads, routing-switching algorithms, and router models. By carefully defining the boundaries between these modules, pp-mess-sim creates a flexible and extensible environment for evaluating different aspects of network design. The simulator models emerging multicomputer networks that can support multiple routing and switching schemes simultaneously; pp-mess-sim achieves this flexibility by associating routing-switching policies, traffic patterns, and performance metrics with collections of packets, instead of the underlying router model. Besides providing a general framework for evaluating router architectures, pp-mess-sim includes a cycle-level model of the PRC, a programmable router for point-to-point distributed systems. The PRC model captures low-level implementation details, while another high-level model facilitates experimentation with general router design issues. Sample simulation experiments capitalize on this flexibility to compare network architectures under various application workloads     

An accurate performance model for network-on-chip and multicomputer interconnection networks

In this paper, we present a mathematical background for a new approach for performances modeling of interconnection networks, based on analyzing the packet blocking and waiting time spent in each channel passing through all possible paths in the channel dependency graph. We have proposed a new, simple and very accurate analytical model for deterministic routing in wormhole networks, which is general in terms of the network topology and traffic distribution. An accurate calculation of the variance of the service time has been developed, which overcomes the rough approximation used, as a rule, in the existing models. The model supports two-dimensional mesh topologies, widely used in network-on-chip architectures, and multidimensional topologies, popular in multicomputer architectures. It is applicable even for irregular topologies and arbitrary application-specific traffic. Results obtained through simulation show that the model achieves a high degree of accuracy.     

无线数据网络中的自相似性

在研究通信网络的流量控制及网络性能的时候．业务源模型是一个十分重要的组成部分。传统的业务流模型大多是基于泊松或贝努力过程的．而这些模型表现出的行为与实际网络的测量结果不符。大量业务的测量表明：在这些业务中普遍存在着自相似性(即长相关性)。采用自相似建模表征业务到达过程的长时相关特性具有较高的精度．其中Hurst系数是表征业务突发特性的重要参数。经研究发现，无线网络中仍然存在自相似性。考察CDPD(蜂窝数字分组数据网)的特性，发现自相似性对网络的排队性能有着显著的影响．可以通过增加队列长度，加大缓冲存储空间，实现降低延时。     

Optimisation of control parameters for genetic algorithms to test computer networks under realistic traffic loads

Although many studies have focused on testing computer networks under realistic traffic loads by means of genetic algorithms (GAs), little attention has been paid to optimising the parameters of the GAs in this problem. The objective of this work is to design and validate a system that, given some constraints on traffic bandwidth, generates the worst-case traffic for a given computer network and finds the traffic configuration (critical background traffic) that minimises throughput in that computer network. The proposed system is based on a meta-GA, which is combined with an adaptation strategy that finds the optimum values for the GA control parameters and adjusts them to improve the GA's performance. To validate the approach, different comparisons are performed with the goal of assessing the acceptable optimisation power of the proposed system. Moreover, a statistical analysis was conducted to ascertain whether differences between the proposed system and other algorithms are significant. The results demonstrate the effectiveness of the system and prove that, when the background traffic is driven by a GA that uses the parameters obtained from the system, the computer network's performance is much lower than when the traffic is generated by Poisson statistical processes or by other algorithms. This system has identified the worst traffic pattern for the protocol under analysis.