Analysis of a class of distributed queues with applications

Recently we have developed a class of media access control algorithms for different types of Local Area Networks. A common feature of these LAN algorithms is that they represent various methods by which the processors in the LAN can simulate the availability of centralized packet transport facility, but whose service incorporates a particular type of changeover time known as ‘moving server’ overhead. First we describe the operation of moving server systems in general, for both First-Come-First-Served and Head-of-the-Line orders of service, together with an approach for their delay analysis where we transform the moving server system into a conventional queueing system having proportional waiting times. Then we describe how the various LAN algorithms may be obtained from the ideal moving server system, and how a major component of their performance characteristics is determined by the performance characteristics of that ideal system. Finally, we evaluate the compatibility of such LAN algorithms with separable queueing network models of distributed systems by computing the interdeparture time distribution for M/M/1 in the presence of moving server overhead. Although it is not exponential except in the limits of low server utilization or low overhead, the interdeparture time distribution is a weighted sum of exponential terms with a coefficient of variation not much smaller than unity. Thus, we conjecture that a service centre with moving server overhead could be used to represent one of these LAN algorithms in a product form queueing network model of a distributed system without introducing significant approximation errors.     

Single server stochastic recirculation systems

A recursive methodology is suggested for approximating the asymptotic performance of a single server recirculation system. A single server recirculation system is modeled by a G/G/1/0 queueing loss system with generally distributed interarrivai times, generally distributed service times, a single server, no waiting room, first come first served queueing discipline, and retrials. In this queueing system, the units which initially are not processed by the server are not lost. These units retry to receive service by retrying. Furthermore, numerical results are provided and the approximation outcomes are compared against those from a simulation study.     

Performance Analysis of a Client–Server System Using Queueing Networks: A Case Study

Queueing networks have been widely used to evaluation performance of mainframe computer systems. In contrast, few results have been reported for modern open systems, so it was not clear whether queueing networks are useful for modern systems or not. We think this situation has partly been due to lack of handy evaluation tools. This paper presents tow tools that we developed to evaluate open system performance. On is a measuring tool that is capable of accurately obtaining the service times of system resources requested by an application transaction. The other is an estimating tool which calculates various performance measures based on queueing network models. This paper also describes a case study in which the performance of a medium-sized UNIX client–server system (up to 24 clients) is estimated using the tools and these estimates are then compared with experimental results. The estimates closely agree with the measured results and are accurate enough for practical applications. Based on this, we conclude that queueing network models are also useful for modern systems.     

WWW系统性能分析

本文提出了一个简单高水平的开放网络模型,得出了一些ＷＷＷ服务器性能的结论,并分析了多服务器系统,定义了ＷＷＷ服务器处理能力的上限,分析了文件的大小、服务 器的速度、网络带宽等因素对ＷＷＷ服务器性能的影响,最后,评价了几种改善ＷＷＷ服务器性能的方法。     

基于随机Petri网的IP-SWAN系统性能评价

在分析基于iSCSI协议的IP存储广域网(IP-SWAN)的数据传输流程的基础上,提出了IP-SWAN系统的随机Petri网模型和一种新的基于变迁的串并联等价变换计算系统I/O响应时间的SPNA方法。基于SPNA方法的性能分析和预测结果表明,在低速网环境下,网络传输速率是系统性能的主要瓶颈,提高网络带宽可以有效地改进整个系统性能。在高速网环境下,提高中心节点的读缓存命中率和CPU处理效率,可以降低系统的I/O响应时间。     

Standby memory performance of a mini/micro computer in a computer communication system

the utilization of computer communication systems for distributed information processing is growing very fast due to the reduction of transmission time and cost. Keeping in view the user's demand for simultaneous transmission of documents and burst messages in a large user resource-sharing mode, a system model mainly consisting of a mini/micro computer and a switching mechanism is presented. The standby memory performance of the mini/micro computer is analyzed with facsimile and burst data input, synchronous transmission and random server interruption through Bernoulli sequences, and its performance is studied in terms of overflow probability and average queueing delay. Some of the computed results are portrayed in graphs for the use of computer communication system designer's as guidelines.     

A comparative workload-based methodology for performance evaluation of parallel computers

A practical methodology for evaluating and comparing the performance of distributed memory Multiple Instruction Multiple Data (MIMD) systems is presented. The methodology determines machine parameters and program parameters separately, and predicts the performance of a given workload on the machines under consideration. Machine parameters are measured using benchmarks that consist of parallel algorithm structures. The methodology takes a workload-based approach in which a mix of application programs constitutes the workload. Performance of different systems are compared, under the given workload, using the ratio of their speeds. In order to validate the methodology, an example workload has been constructed and the time estimates have been compared with the actual runs, yielding good predicted values. Variations in the workload are analysed in terms of increase in problem sizes and changes in the frequency of particular algorithm groups. Utilization and scalability are used to compare the systems when the number of processors is increased. It has been shown that performance of parallel computers is sensitive to the changes in the workload and therefore any evaluation and comparison must consider a given user workload. Performance improvement that can be obtained by increasing the size of a distributed memory MIMD system depends on the characteristics of the workload as well as the parameters that characterize the communication speed of the parallel system.     

Design and performance evaluation considerations of a multimediamedical database

Multimedia information management and communications systems for medical applications have been undergoing design and development. The aim of these activities has been the development of distributed computer systems providing storage, processing, and communication services required by the medical community. One of the main critical issues of such systems is the handling of multimedia information (i.e., text, images, graphics, and voice) in a uniform way and the fast access to images through the network. We present the design architecture and concepts used in our multimedia database system, along with its performance evaluation. The evaluation focuses on the response times of a multimedia medical database server, as seen by remote workstations for various retrieval and image transfer requests. For this purpose, a queueing network model was developed and simulated. Communications between the workstations and the database server are governed by the client-server model using TCP/IP and appropriate application protocols on a 10 Mb/s Ethernet LAN     

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.     

Performance evaluation of fork and join synchronization primitives

Summary The paper presents a performance model of fork and join synchronization primitives. The primitives are used in parallel programs executed on distributed systems. Three variants of the execution of parallel programs with fork and join primitives are considered and queueing models are proposed to evaluate their performance on a finite number of processors. Synchronization delays incurred by the programs are represented by a state-dependent server with service rate depending on a particular synchronization scheme. Closed form results are presented for the two processor case and a numerical method is proposed for many processors. Fork-join queueing networks having more complex structure i.e., processors arranged in series and in parallel, are also analyzed in the same manner. The networks can model the execution of jobs with a general task precedence graph corresponding to a nested structure of the fork-join primitives. Some performance indices of the parallel execution of programs are studied. The results show that the speedup which can be obtained theoretically in a parallel system may be decreased significantly by synchronization constraints.This research we carried out while the author was visiting ISEM, Université de Paris-Sud, France     

Modeling parallel and distributed systems with finite workloads

In studying or designing parallel and distributed systems one should have available a robust analytical model that includes the major parameters that determine the system performance. Jackson networks have been very successful in modeling computer systems. However, the ability of Jackson networks to predict performance with system changes remains an open question, since they do not apply to systems where there are population size constraints. Also, the product-form solution of Jackson networks assumes steady-state and exponential service centers or certain specialized queueing discipline. In this paper, we present a transient model for Jackson networks that is applicable to any population size and any finite workload (no new arrivals). Using several non-exponential distributions we show to what extent the exponential distribution can be used to approximate other distributions and transient systems with finite workloads. When the number of tasks to be executed is large enough, the model approaches the product-form solution (steady-state solution). We also, study the case where the non-exponential servers have queueing (Jackson networks cannot be applied). Finally, we show how to use the model to analyze the performance of parallel and distributed systems.     

Performance Analytic Models and Analyses for Workflow Architectures

The design and implementation of a workflow management system is typically a large and complex task. Decisions need to be made about the hardware and software platforms, the data structures, the algorithms, and network interconnection of various modules utilized by various users and administrators. These decisions are further complicated by requirements such as flexibility, robustness, modifiability, availability, performance, and usability. As the size of workflow systems increases, organizations are finding that the standard server/client architectures, and off-the-shelf solutions are not adequate. We can further see that in the future, very large-scale workflow systems (VLSW) will become more complex, and more prevalent. Thus, one further requirement is an emphasis of this document: scalability. For the purposes of our scalable workflow investigations, we describe a framework, a taxonomy, a model, and a methodology to investigate the performance of various workflow architectures as the size of the system (number of workcases) grows very large.First, this paper presents a novel workflow architectural framework and taxonomy. We survey some example current workflow products and research prototype systems, illustrating some of the taxonomical categories. In fact, most current workflow architectures fall into only one of the many categories of this taxonomy: the centralized server/client category. The paper next explains a performance analysis methodology useful for exploring this taxonomy. The methodology deploys a layered queuing model, and performs mathematical analysis on this model using a modified MOL (method of layers) combined with a linearization algorithm. Finally, the paper utilizes this methodology to compare and contrast the various architectural categories, providing interesting results about performance as the number of workcases increases. Our analytic results suggest that (a) for VLSW performance determination, software architecture is as important as hardware architecture, and (b) alternatives to the client server architecture provide significantly better scalability.     

An Analytical Method for Predicting the Performance of Parallel Image Processing Operations

This paper presents an analytical performance prediction model and methodology that can be used to predict the execution time, speedup, scalability and similar performance metrics of a large set of image processing operations running on a p-processor parallel system. The model which requires only a few parameters obtainable on a minimal system can help in the systematic design, evaluation and performance tuning of parallel image processing systems. Using the model one can reason about the performance of a parallel image processing system prior to implementation. The method can also support programmers in detecting critical parts of an implementation and system designers in predicting hardware performance and the effect of hardware parameter changes on performance. The execution of parallel image processing operations was studied and operations were arranged in three main problem classes based on data locality and the communication patterns of the algorithms. The core of the method is the derivation of the overhead function, as it is the overhead that determines the achievable speedup. The overheads were examined and modelled for each class. The use of the method is illustrated by four class-representative image processing algorithms: image-scalar addition, convolution, histogram calculation and the Fast Fourier Transform. The developed performance model has been validated on a 16-node parallel machine and it has been shown that the model is able to predict the parallel run-time and other performance metrics of parallel image processing operations accurately.     

Response times in a two-node queueing network with feedback

The study presented in this paper is motivated by the performance analysis of response times in distributed information systems, where transactions are handled by iterative server and database actions. We model system response times as sojourn times in a two-node open queueing network with a processor sharing (PS) node and a first-come-first-served (FCFS) node. External customers arrive at the PS node according to a Poisson process. After departing from the PS node a customer proceeds to the FCFS node with probability p, and with probability 1−p the customer departs from the system. After a visit to the FCFS node, customers are fed back to the PS node. The service requirements at both nodes are exponentially distributed. The model is a Jackson network, admitting a product-from solution for the joint number of customers at the nodes, immediately leading to a closed-form expression for the mean sojourn times in steady-state. The variance of the sojourn times, however, does not admit an exact expression—the complexity is caused by the possibility of overtaking. In this paper we propose a methodology for deriving simple, explicit and fast-to-evaluate approximations for the variance of the sojourn times. Numerical results demonstrate that the approximations are very accurate in most model instances.     

集群环境中影响NFS文件系统带宽的测试与分析

NFS是集群系统中提供全局文件共享的主要手段,研究影响NFS带宽的因素对于优化集群系统的性能十分重要。该文针对集群系统中I/O特征建立了NFS的带宽模型,设计和实现了基于MPI开发的并行文件系统测试工具Mpbonnie,在集群系统中测试和分析了多种因素对NFS性能的影响。结果表明,除已知的存储和网络因素外,与NFS带宽关系密切的因素还包括客户端数量、服务器文件系统类型、读写方式和服务器处理能力等。     

Performance analysis of a scheme for concurrency/synchronization using queueing network models

Queueing network models have been used extensively to analyze performance of computer systems. However, queueing network models with product form solutions are not directly applicable to systems that process programs with internal concurrency/synchronization. An exact solution of such systems is often not feasible because of its large state space.Approximation techniques, based on queueing network theory, are presented which analyze the performance of closed systems with a specific scheme of concurrency/synchronization. The techniques are applicable to multitasking systems, distributed database systems, packet routing environments, and fork/join situations.This research was partially supported by CNPq/Brazil, Hospital Corporation of America (HCA) and Northern Telecom.     

Task Scheduling on the PASM Parallel Processing System

PASM is a proposed large-scale distributed/parallel processing system which can be partitioned into independent SIMD/MIMD machines of various sizes. One design problem for systems such as PASM is task scheduling. The use of multiple FIFO queues for nonpreemptive task scheduling is described. Four multiple-queue scheduling algorithms with different placement policies are presented and applied to the PASM parallel processing system. Simulation of a queueing network model is used to compare the performance of the algorithms. Their performance is also considered in the case where there are faulty control units and processors. The multiple-queue scheduling algorithms can be adapted for inclusion in other multiple-SIMD and partitionable SIMD/MIMD systems that use similar types of interconnection networks to those being considered for PASM.     

Cost-minimization analysis of a working vacation queue with N-policy and server breakdowns

This paper investigates the N-policy M/M/1 queueing system with working vacation and server breakdowns. As soon as the system becomes empty, the server begins a working vacation. The server works at a lower service rate rather than completely stopping service during a vacation period. The server may break down with different breakdown rates during the idle, working vacation, and normal busy periods. It is assumed that service times, vacation times, and repair times are all exponentially distributed. We analyze this queueing model as a quasi-birth–death process. Furthermore, the equilibrium condition of the system is derived for the steady state. Using the matrix-geometric method, we find the matrix-form expressions for the stationary probability distribution of the number of customers in the system and system performance measures. The expected cost function per unit time is constructed to determine the optimal values of the system decision variables, including the threshold N and mean service rates. We employ the particle swarm optimization algorithm to solve the optimization problem. Finally, numerical results are provided, and an application example is given to demonstrate the applicability of the queueing model.     

Markovian queueing systems with retrials and heterogeneous servers

The asymptotic performances of a random access and an ordered entry G/M/K/Oqueueing system with a stationary counting arrival process, K heterogeneous parallel servers, no waiting room and retrials are approximated based on a two-parameter method. In a random access system, units upon arrival are randomly assigned to one of the servers. In an ordered entry system, servers are indexed from 1 to K, and units first arrive at server i and if the server is found to be busy, those units arrive at server (i + 1), for i = 1 to K − 1. In both queueing systems, if units are not processed by one of the servers, those units are not lost, instead they retry to receive service by merging with the incoming arrival units.

To approximate the asymptotic performance of the above queueing systems, a recursive algorithm is suggested, and appropriate performance measures are presented to be used as comparison criteria at the design stage. Furthermore, numerical results are provided and approximation outcomes are compared against those from a simulation study.     

基于分层排队网络模型的MCU性能预测及优化研究

针对视频会议系统中的多点控制单元(MCU)提出了一个基于分层排队网络模型的性能预测方法．通过对分层排队网络模型进行扩展，建立了多点控制单元的分层排队模型．设计了一个仿真程序对模型进行评价，仿真程序的输入即模型配置文件．该方法可以较快地从多种设计方案或硬件平台中选择满足系统性能设计目标的软件或硬件配置．仿真结果显示，选择双处理器配置和采用多线程技术，多点控制单元的接入容量提高了50％．最后，多点控制单元终端接入实验证明了该方法的有效性。