A Queuing Model for Evaluating the Transfer Latency of Peer-to-Peer Systems

This paper presents a queuing model to evaluate the latency associated with file transfers or replications in peer-to-peer (P2P) computer systems. The main contribution of this paper is a modeling framework for the peers that accounts for the file size distribution, the search time, load distribution at peers, and number of concurrent downloads allowed by a peer. We propose a queuing model that models the nodes or peers in such systems as M/G/1/K processor sharing queues. The model is extended to account for peers which alternate between online and offline states. The proposed queuing model for the peers is combined with a single class open queuing network for the routers interconnecting the peers to obtain the overall file transfer latency. We also show that in scenarios with multipart downloads from different peers, a rate proportional allocation strategy minimizes the download times.     

Application of Relational Interval Arithmetic to Computer Performance Analysis: a Survey

This paper presents a survey of the existing work in the area of interval-based performance analysis of computing systems. Intervals in performance analysis is required when uncertainties or variabilities exist in the workload parameters for the performance model of the system. Intervals are also useful for computing upper and lower bounds on system performance. Most conventional analytic models accept a set of single valued parameters and produce a single valued model output. Adaptation of these existing models to handle interval parameters require new techniques that use interval arithmetic. Experiences with relational interval arithmetic provided by a constraint logic programming language in solving a number of performance analysis problems in conventional multiprogrammed computers as well as distributed processing systems are described.     

Performance analysis of priority scheduling mechanisms under heterogeneous network traffic

Priority scheduling principle plays a crucial role in the Differentiated Services (DiffServ) architecture for the provisioning of Quality-of-Service (QoS) of network-based applications. Analytical modelling and performance evaluation of priority queuing systems have received significant attention and research efforts. However, most existing work has primarily focused on the analysis of priority queuing under either Short Range Dependent (SRD) or Long Range Dependent (LRD) traffic only. Recent studies have shown that realistic traffic reveals heterogeneous nature within modern multi-service networks. With the aim of investigating the impact of heterogeneous traffic on the design and performance of network-based systems, this paper proposes a novel analytical model for priority queuing systems subject to heterogeneous LRD self-similar and SRD Poisson traffic. The key contribution of the paper is to extend the application of the generalized Schilder's theorem (originally a large deviation principle for handling Gaussian processes only) to deal with heterogeneous traffic and further develop the analytical upper and lower bounds of the queue length distributions for individual traffic flows. The validity and accuracy of the model demonstrated through extensive comparisons between analytical bounds and simulation results make it a practical and cost-effective evaluation tool for investigating the performance behaviour of priority queuing systems under heterogeneous traffic with various parameter settings.     

State diagrams and steady-state balance equations for open queuing network models

In this paper, the state diagrams and steady-state balance equations for two kinds of open queuing network models are presented. The first model comprises a network of single queues with single servers, while the second model comprises multiple servers for single queues. State diagrams are drawn for (2, 3) queuing networks with (i) single servers and (ii) multiple servers. Steady-state balance equations are derived from the state diagrams. The paper provides a method to solve open queuing networks by analyzing the stochastic process involved in the transition of states in a continuous time Markov chain which represents the state diagram of a queuing system.     

Probability distribution functions for servicing two types of requests

A method for calculating the parameters of queuing systems with heterogeneous requests was obtained in our paper [1]. In [2], the accuracy of this method for a network of queuing systems was studied. This method is applicable for the case of the estimation of queuing systems with respect to an average value (averaged over the parameters of the distribution averages). This paper develops the method for calculating the parameters of queuing systems by using the integral characteristics (distribution functions of random quantities). This approach allows one to use more accurate methods for calculating the characteristics of queuing systems with different types of requests. In addition, this method provides more detailed specification of the characteristics of a queuing service system, in particular, the examination of the characteristics of output streams.     

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.     

Properties and performance bounds for closed free choicesynchronized monoclass queueing networks

It is shown that many monoclass queuing networks (QN) with synchronizations can naturally be modeled with a subclass of Petri nets (PN) called free-choice nets (FC), for which a wide gamut of qualitative behavioral and structural results have been derived. Some of these net theoretic results are used to characterize the ergodicity, boundedness, and liveness of closed free-choice synchronized QNs. Upper and lower throughput bounds are defined based on the mean value of the service times, without any assumption on the probability distributions (thus including both the deterministic and the stochastic cases). It is shown that monotonicity properties exist between the throughput bounds and the parameters of the model in terms of population and service times. Proposed are (theoretically polynomial and practically linear complexity) algorithms for the computation of these bounds, based on linear programming problems defined on the incidence matrix of the underlying FC net. Using classical laws from queuing theory, bounds are provided for mean queue lengths and response time     

Constrained pose refinement of parametric objects

Pose refinement is an essential task for computer vision systems that require the calibration and verification of model and camera parameters. Typical domains include the real-time tracking of objects and verification in model-based recognition systems. A technique is presented for recovering model and camera parameters of 3D objects from a single two-dimensional image. This basic problem is further complicated by the incorporation of simple bounds on the model and camera parameters and linear constraints restricting some subset of object parameters to a specific relationship. It is demonstrated in this paper that this constrained pose refinement formulation is no more difficult than the original problem based on numerical analysis techniques, including active set methods and lagrange multiplier analysis. A number of bounded and linearly constrained parametric models are tested and convergence to proper values occurs from a wide range of initial error, utilizing minimal matching information (relative to the number of parameters and components). The ability to recover model parameters in a constrained search space will thus simplify associated object recognition problems.     

基于OCSP方式的证书撤销策略

阐述了在线证书状态协议(OCSP)方式的证书撤销机制的原理,针对单服务员模式建立了一个策略评估模型。该模型基于排队理论对系统机制进行了简化和抽象,通过该模型对OCSP方式的证书撤销策略进行评价,结合模型对影响系统的排队时间、网络带宽、验证速度等相关参数进行了讨论,分析了机制中的多服务员模型。     

SNAPL/1: A language to describe and evaluate queuing network models

Recent theoretical developments in queuing theory have made multiclass queuing network models a viable alternative to established simulation methods for the analysis of dynamic systems. Computer software is required to describe and solve such network models. This paper describes a language which provides the human interface to a particular multiclass queuing network modelling package. The discussion is illustrated with an example from the language and concludes with suggestions for improvements.     

Calculating Steady-State Characteristics of Single-Channel Queuing Systems Using Phase-Type Distributions

This paper analyzes the results of application of the hyperexponential and Erlang approximations with parameters of paradoxical and complex types for calculating steady-state characteristics of G /G /1/ m queuing systems by the fictitious phase method. The results are verified using simulation models.     

On the analysis of exponential queuing systems with randomly changing arrival rates: Stability conditions and finite buffer scheme with a resume level

This paper considers a single server exponential queue with random fluctuations in the intensity of the arrival process. The motivation being the modelling of random changes in traffic patterns. This random intensity model does not obey the independence assumption made in queuing theory. Necessary and sufficient conditions for the stability or ergodicity of the queuing process are obtained via analytic techniques using Jury's stability criteria, often used to study discrete time control systems. The effect of such fluctuations is then studied for a finite resume level queue which is often used in flow control. Exact performance measures are computed and are compared with existing results.     

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

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

基于排队网络的VoIP信令解析系统性能分析

基于软件性能模型的软件性能评估可以应用在软件研发周期的早期阶段,以便对软件系统的行为进行定量分析。该文给出一种应用排队网络模型对VoIP信令解析软件体系结构性能的评估方法。该方法的基本思想是：从基于UML描述的活动图导出多类排队网络性能模型,通过统计分析将得出的性能参数反馈给UML软件体系结构模型,不断完善体系结构设计。模型提供的统计性能评估方法克服了受限估计离散事件分析的局限性。     

Analysis of the oral interface in the interactive servicing systems. I

The oral technologies created a new type of the human-computer interaction. The oral servers and oral portals which implement a new model of human-computer communications may be studied using the methods of the queuing theory. Development of the analytical models to estimate some numerical characteristics of the human-computer one-channel dialogue such as the probability of successful dialogue, number of overinterrogations, and mean time of dialogue are the immediate subject matters of such studies. These characteristics may be used further to analyze operation of the entire queuing system that models the multichannel oral portal. The main parameters of the human-computer dialogue such as the probability of correct recognition of an element and the entire dialogue at overinterrogations and the time used for a dialogue element were considered. The parameters for estimation of the dialogue length were determined. A classification of the dialogue control algorithms at oral interaction of the client with the computer-aided information and servicing systems was developed. The algorithms were compared in terms of duration with regard for the desired reliability of recognition.     

Optimal assignment of dynamic priorities in queuing systems with two types of customers

We consider queuing systems with two types of customers. For such systems, we develop numerical procedures for computation of optimal dynamic priorities in the case of multiplicative priority functions. The optimality criterion is based on the total queue length for customers of both types. Our technique allows one to take into account waiting-time bounds. The optimization problem is formulated in the language of linear-fractional programming. To illustrate our technique, we present some numerical results at the end of the paper.     

Controlling mean queuing delay under multi-class bursty and correlated traffic

This paper presents an adaptive queue management scheme to maintain queuing delay in a router at a required level based on a comprehensive analytical model under aggregated Internet traffic flows from various traffic classes. The proposed scheme uses a closed-loop feedback control mechanism to constrain the average queuing delay by regulating traffic arrival rate implicitly through a movable queuing threshold. A discrete-time queuing model is developed to derive the relationship between average queuing delays and queuing thresholds based on a traffic model that models aggregated Internet traffic through superposition of N MMBP-2 arrival processes. The queuing threshold is adjusted dynamically with reference to the relationship derived in the analytical model and also feedback of average queuing delay measurement. Packets are dropped dynamically with respect to the changes of queuing threshold and the packet loss events serve as implicit congestion indicators. Matlab is used to perform queuing analysis and simulation. Statistical evaluation is performed to show the efficiency and accuracy of the analytical and simulation results.     

Information-theoretic bounds on target recognition performancebased on degraded image data

This paper derives bounds on the performance of statistical object recognition systems, wherein an image of a target is observed by a remote sensor. Detection and recognition problems are modeled as composite hypothesis testing problems involving nuisance parameters. We develop information-theoretic performance bounds on target recognition based on statistical models for sensors and data, and examine conditions under which these bounds are tight. In particular, we examine the validity of asymptotic approximations to probability of error in such imaging problems. Problems involving Gaussian, Poisson, and multiplicative noise, and random pixel deletions are considered, as well as least-favorable Gaussian clutter. A sixth application involving compressed sensor image data is considered in some detail. This study provides a systematic and computationally attractive framework for analytically characterizing target recognition performance under complicated, non-Gaussian models and optimizing system parameters     

自相似环境中端到端延迟上界

论文对网络队列系统性能定量分析新型数学工具——网络微积分学进行了归纳和总结,利用网络微积分学证明了利用分形漏桶整形器对自相似业务进行整形不会增加网络端到端延迟上界,计算了通用处理器共享下以分形漏桶包络轨迹为到达曲线和以速度等待时间函数为服务曲线的端到端延迟确定性上界。     

Bound performance models of heterogeneous parallel processingsystems

Systems of heterogeneous parallel processing are studied such as arising in parallel programs executed on distributed systems. A lower and an upper bound model are suggested to obtain secure lower and upper bounds on the performance of these systems. The bounding models are solved by using a matrix-geometric algorithmic approach. Formal proofs of the bounds are provided along with error bounds on the accuracy of the bounds. These error bounds in turn are reduced to simple computational expressions. Numerical results are included. The results are of interest for application to arbitrary fork-join models with parallel heterogeneous processors and synchronization