Papers and Presentations
Journal Articles
Shortle, J.F., M.J. Fischer, and P. H. Brill. 2006. "Waiting Time Distributions of the M/DN/1 Queues Through Numerical Laplace Inversion." INFORMS Journal on Computing, Winter 2007.
ABSTRACT [+]
ABSTRACT [-]
This paper considers an M/G/1 queue where the service time for each customer is a discrete random variable taking one of N values. We call this an M/DN/1 queue. There are potential numerical problems inverting Laplace transforms associated with this queue because the service distribution is discontinuous. The purpose of this paper is to investigate the performance of numerical transform inversion methods in analyzing this queue. We first derive continuity properties of the steady-state distribution of wait in the M/DN/1 queue. Then, we show analytically how continuity properties affect the performance of the Fourier method for inverting transforms. In particular, continuity is not required in all derivatives for best performance of the method. We also present a new inversion method specifically for the M/DN/1 queue. Finally, we give numerical experiments comparing these and four other inversion methods. Although no method clearly dominates, the recursion method performs well in most examples.
Shortle, J.F., M.J. Fischer, D. Gross, and D.M. Masi. 2005. "Using the Pareto Distribution in Queueing Modeling." Journal of Probability and Statistical Science, vol. 4, no. 1, pp. 85-98, Feb 2006.
ABSTRACT [+]
ABSTRACT [-]
The Pareto distribution was first formulated in the late 1800s by the Italian economist Vilfredo Pareto. He argued that the distribution of income could be described by the formula log(N) = log(A) + m log(x), where N is the proportion of income earners who receive incomes higher than x, and A and m are constants. Over the years Pareto's Law has held up in empirical studies. The Pareto distribution has recently been used as a model for file sizes in the Internet and insurance losses. It has various forms; here, we consider a 1-parameter form and a 2-parameter form. The purpose of this paper is to show that using different forms of the Pareto distribution can result in drastically different congestion measures in a queueing system. This is true even if the means and variances between two Pareto distributions are the same. In other words, even within the same family of distributions, a matching of the first two moments is not sufficient to guarantee similar performance measures. In addition, we show that different forms of the Pareto can yield qualitatively different behavior in a queueing system, with respect to analogous Markovian models. We specifically consider P/M/1 and M/P/1 queueing systems.
Shortle, J.F. 2005. "Piecewise-Polynomial Approximations for Heavy-Tailed Distributions in Queueing Analysis." Stochastic Models. Vol. 21, No. 1. p. 215-234. 2005.
ABSTRACT [+]
ABSTRACT [-]
A basic difficulty in dealing w/ heavy-tailed distributions is that they may not have closed-form Laplace transforms. This makes numerical methods which use the Laplace transform more challenging. This paper generalizes an existing method for approximating heavy-tailed distributions, for use in queueing analysis. The generalization involves fitting Chebyshev polynomials to a probability density function g(t) at specified points t1, t2, …, tN. By choosing points ti which rapidly get far out in the tail, it is possible to capture the tail behavior with relatively few points, and to control the relative error in the approximation. We give numerical examples to evaluate the performance of the method in simple queueing problems.
Shortle, J.F., and Brill, P.H. 2005. "Analytical Distribution of Waiting Time in the M/{iD}/1 Queue." Queueing Systems. Vol. 50, p. 185-197.
ABSTRACT [+]
ABSTRACT [-]
We give an analytical formula for the steady-state distribution of wait in the M/G/1 queue, where the service time for each customer is a positive integer multiple of a constant D > 0. We call this an M/{iD}/1 queue. We give numerical algorithms to calculate the distribution. In addition, in the case that the service distribution is sparse, we give revised algorithms that can compute the distribution more quickly.
Hsiung, H., M.J. Fischer, and J.G. Leigh. 2005. "Internet Protocol Multi-Class Service Performance Analysis." Telecommunications Review. 2005. Noblis, Falls Church, Va.
ABSTRACT [+]
ABSTRACT [-]
In a circuit-switched network which carries multiple services, bandwidth is allocated for data service to ensure the minimum data delivery. When data demand exceeds the reserved bandwidth, data traffic tends to overflow and use resources allocated for voice, if voice resources are not used. In a packet-switched network, bandwidth is reserved for voice service to ensure the Service Level Agreement is met. This paper studies voice and data performance (i.e., delay and jitter) using four resource management and queueing rules.
Shortle, J. F., M.J. Fischer, and D.M. Masi. 2005. "Estimating Delay in a Data Network Through Numerical Laplace Inversion." Telecommunications Review. 2005. Noblis, Falls Church, Va.
ABSTRACT [+]
ABSTRACT [-]
In place, at present, is a simplified analytical queueing model to estimate the end-to-end delay of packets in a data network. [1] The key modeling assumption is that the end-to-end path can be divided into a series of independent queues. In other words, the total travel time is approximated by the sum of the waiting times in a series of individual queues that are independent of each other. The simplified model gives approximately the same mean performance metrics as the detailed OPNET Modeler simulation (less than 10 percent error for the problem considered), but takes only a fraction of the time.
This paper gives an even faster numerical method to solve the simplified analytical model. [1] The new method performs all computations initially using Laplace transforms. This avoids using numerical integration to convolve distribution functions. The new method is about 180 times faster than the previously implemented solution.
The main challenge with the new method is that the distribution functions of interest have discontinuities or atoms. These are known to cause problems for numerical transform inversion. In this paper, we present methods to remove these atoms prior to numerical inversion and then to re-insert the atoms into the resulting distribution function, thus preserving the accuracy and speed of the inversion methods.
Shortle, J. F., M.J. Fischer, D. Gross, and D.M. Masi. 2005. "One-Parameter Pareto, Two-Parameter Pareto, Three-Parameter Pareto: Is There A Modeling Difference?" Telecommunications Review. 2005. Noblis, Falls Church, Va.
ABSTRACT [+]
ABSTRACT [-]
The Pareto distribution was first formulated in the late 1800s by the Italian economist Vilfredo Pareto. He presented the argument that in all countries and times, the distribution of income and wealth could be described by the formula log(N) = log(A) + mlog(x), where N is the proportion of income earners who receive incomes higher than x, and A and m are constants. Over the years, Pareto's Law has held up in empirical studies. The Pareto distribution has recently been used as a model for file sizes on the Internet, insurance losses, financial behavior of the stock market, and in telecommunications systems. It has various forms; here, we consider a one-parameter form and a two-parameter form. Thus, we question if using one form of the Pareto gives different results than using another form. In this paper, we numerically address this question by studying queueing systems with either Pareto arrivals or service times. The two Pareto forms are studied in detail: Case 1, both Pareto forms have equal means and variances; and Case 2, both Pareto forms have equal mean and shape parameters. For both cases, our numerical results, substantiated by simulation studies, show that using the two-parameter Pareto results in lower congestion than the comparable one-parameter Pareto.
Fischer, M.J., Masi, D.M.B., Gross, D., and Shortle, J.F. 2004. "Loss Systems with Heavy-Tailed Arrivals." Telecommunications Review. 2004. Noblis, Falls Church, Va.
ABSTRACT [+]
ABSTRACT [-]
R. I. Wilkinson [1] was one of the first researchers to study traffic peakedness in circuit-switched systems. His pioneering work, called the Equivalent Random Method (ERM), gave engineers an approximation for a trunk group's blocking probability when presented with a peaked offered load. ERM was based on the mean and variance of the offered load to the trunk group and did not assume the form of the underlying arrival distribution. With the advent of the Internet, traffic studies have indicated the existence of heavy- or power-tailed probability distributions that characterized these traffics. The Pareto, Weibull, and LogNormal distributions most frequently appear in these studies. A fact that seems to be overlooked is that different congestion results may be obtained depending upon which probability distribution is used in the congestion model, even when the mean and variance of the probability distributions are equal. In this paper, we study the effect of different heavy- or power-tailed arrival distributions on the blocking probability in loss systems.
Shortle, J.F., Brill, P.H., Fischer, M.J., Gross, D., and Masi, D.M.B. 2004. "An Algorithm to Compute the Waiting Time Distribution for the M/G/1 Queue." INFORMS Journal on Computing. Vol. 16, no. 2, p. 152-161. PDF file provided by INFORMS. Copyright 2004 INFORMS.
ABSTRACT [+]
ABSTRACT [-]
In many modern applications of queueing theory, the classical assumption of exponentially decaying service distributions does not apply. In particular, Internet and insurance risk problems may involve heavy-tailed distributions. A difficulty with heavy-tailed distributions is that they may not have closed-form, analytic Laplace transforms. This makes numerical methods, which use the Laplace transform, challenging. In this paper, we develop a method for approximating Laplace transforms. Using the approximation, we give algorithms to compute the steady state probability distribution of the waiting time of an M/G/1 queue to a desired accuracy. We give several numerical examples, and we validate the approximation with known results where possible or with simulations otherwise. We also give convergence proofs for the methods.
Masi, D.M.B., Fischer, M.J., and Garbin, D. A., "Modeling Internet Protocol Networks: OPNET and Analytics." Sigma: Mitretek Technology Summaries. Winter 2004. p. 52-63.
ABSTRACT [+]
ABSTRACT [-]
With the advent of the events surrounding September 11, it is apparent that the protection of critical federal telecommunications networks needs to be ensured. This paper focuses on analytic queueing and simulation capabilities that have been developed to analyze the performance of federal private Internet Protocol (IP) networks.
We have developed an initial version of an analytic model called the IP Network Performance and Analysis Tool (IP-NPAT) and an initial OPNET simulation model. Calibration of the analytic model and the simulation for all link queues based on a realistic packet distribution indicate close agreement in the two analyses. Link loads, mean link delays, link jitter, and delay distribution were compared for each link, as well as end-to-end delay distributions.
Shortle, J.F., M.J. Fischer, and D. Gross. 2003. "Using the Transform Approximation Method to Analyze Queues with Heavy-Tailed Service." Journal of Probability and Statistical Science, Vol. 1, No. 1, pp. 15-27, February.
ABSTRACT [+]
ABSTRACT [-]
Many modern queueing problems involve distributions which are heavy-tailed. This means their distribution functions decay more slowly than any exponential function. Analyzing queues with these distributions is difficult since they do not have closed-form, analytic Laplace transforms. This paper investigates a recently proposed method for numerically approximating Laplace transforms, called the Transform Approximation Method (TAM). While TAM can be used to approximate the Laplace transform of a heavy-tailed distribution, one must still invert a Laplace transform to recover the desired probability distribution. This paper investigates using TAM with two numerical methods for inverting Laplace transforms. In particular, we compare the well-known Fourier-series method with a recursion method specifically adapted for TAM. We give several benchmark problems and algorithms to compare the methods. In general, the Fourier method is better, though the recursion method is better for a specific class of problems.
Fischer, M.J., Masi, D.M.B., Brill, P., Gross, D., and Shortle, J. 2002. "Structural Properties of the Transform Approximation Method and Recursion Method." The Telecommunications Review. 2002. Noblis, Falls Church, Va.
ABSTRACT [+]
ABSTRACT [-]
We have developed the Transform Approximation Method (TAM) to analyze Internet type queueing systems. Those systems are characterized by arrival or service distributions that are known as power or heavy tailed. This class of distributions do not possess a closed form Laplace transform and so TAM was developed to overcome this difficulty. When applying TAM to the M/G/1 queueing system, one is studying the M/DN/1 queue. That is, a single server system with Poisson arrivals and service that takes on any one of N values each with a certain probability. In this paper we present the structural properties of that queueing system and show how those properties impact on TAM and its associated numerical method, the Recursion Method.
Fischer, M. J., Masi, D. M., Gross, D., and Shortle, J. 2001. "Analyzing the Waiting Time Process in Internet Queueing Systems with the Transform Approximation Method." The Telecommunications Review. 2001. Noblis, McLean, Va. p. 21-32.
ABSTRACT [+]
ABSTRACT [-]
The underlying arrival and service distributions of Internet traffic are drawn from a family of distributions, which are known as heavy-tailed distributions. These distributions have tails that decay much slower than exponential and do not possess a closed form Laplace transform. This feature significantly limits the use of standard queueing theory analysis techniques on Internet-type queueing systems. We have developed an analysis method, known as the Transform Approximation Method (TAM), to overcome this problem. TAM has been successfully applied to the analysis of the queue length process of systems with heavy-tailed service distributions and to systems with heavy-tailed arrivals. In this paper, we examine the use of TAM in analyzing the waiting time process in systems with heavy-tailed service times. The original version of TAM was modified and successfully applied to this problem. The modification and illustrated examples are presented in the paper.
Fischer, M. J., and T. B. Fowler. 2001. "Fractals, Heavy-Tails and the Internet." Sigma. Fall 2001. Noblis, McLean, Va.
ABSTRACT [+]
ABSTRACT [-]
In a recent Business Week article (2001), a mathematical concept known as fractals was listed as one of the top ten technologies of the future. The article referenced many potential applications for fractals, including data compression and the Internet. In this paper, we discuss the impact fractals have on the Internet and how fractals relate to heavy tailed probability distributions. Fractals are applicable when the underlying process being mathematically modeled has a similar appearance regardless of the time or observation scale. It turns out that much of the traffic riding the Internet can be modeled using fractals. Fowler (1999) presents a tutorial - on fractals and the Internet. Here we review his tutorial and develop the relationship to heavy tailed probability distribution and problems they cause in analyzing Internet congestion.
Harris, C. M., P. H. Brill, and M. J. Fischer. 2000. "Internet-Type Queues with Power-Tailed Interarrival Times and Computational Methods for Their Analysis." INFORMS Journal on Computing. Vol. 12, p. 261-271.
ABSTRACT [+]
ABSTRACT [-]
Internet traffic flows have often been characterized as having power-tailed (long-tailed, fat-tailed, heavy-tailed) packet interarrival times or service requirements. In this work, we focus on the development of a complete and computationally efficient steady-state solution of queues with power-tailed interarrival times when the service times are assumed exponential. The classical method for obtaining the steady-state probabilities and delay-time distributions for the G/M/l (G/M/c) queue requires solving a rootfinding problem involving the Laplace--Stieltjes transform of the interarrival-time distribution function. Then the exponential service assumption is combined with the derived geometric arrival-point probabilities to get both the limiting general-time state and delay distributions. However, in situations where there is a power tail, the interarrival transform is typically quite complicated and always not analytic. In addition, it is possible that there is only a degenerate steady-state system-size probability distribution. Thus an alternative approach to solution is typically needed when power-tailed arrivals are present. For the centerpiece of our numerical work, we exploit the exponentiality of the steady-state delay distributions for the G/M/I and G/M/c queues using level crossings to develop an alternative rootfinding problem when there are power-tailed interarrival times. In addition, we offer a third method for the rootfinding based on a tight approximation of the interarrival distribution function. Extensive computational results are given.
Fischer, M. J., and Harris, C. M. 1999. "A Method for Analyzing Congestion In Pareto and Related Queues." The Telecommunications Review 1999. Noblis, McLean, Va. p. 15-27.
ABSTRACT [+]
ABSTRACT [-]
There are many articles in professional literature documenting the fact that classical queueing models assuming Poisson arrivals or exponential service cannot be used accurately to study congestion on the Internet. In contrast, Internet traffic data indicate that long-tailed distributions typically serve as better models for packet interarrival times and service lengths. But these distributions may not possess all of their moments, and, therefore, certainly not their Laplace transforms. In the absence of the Laplace transform, much of the standard queueing theory analysis cannot be used. In this paper, we apply a new method for approximating Laplace transforms of arbitrary probability distributions to generate complete probabilistic analyses of queues with Pareto arrivals or service times. The use of the approximation is validated using comparisons with known results when possible or simulations otherwise. Further experiments confirm that the inappropriate use of models with Poisson arrivals and exponential service times models can seriously underestimate Internet congestion, and we provide some thoughts on how to make appropriate adjustments.
Proceedings
Fischer, M.J., D.M. Masi, D. Gross, J.F. Shortle, and P.H. Brill. 2006. "Development of Procedures to Analyze Queueing Models with Heavy-Tailed Interarrival and Service Times", presented at the NSF Design, Service, and Manufacturing Grantees and Research Conference, St. Louis, Missouri.
Masi, D.M. and Fischer, M.J. 2005. "Voice over Internet Protocol (VoIP) Performance Models - A Comprehensive Approach", 2005 International Conference on Telecommunication Systems - Modeling and Analysis (ICTSMA), 17-20 November 2005, Dallas, TX.
ABSTRACT [+]
ABSTRACT [-]
Voice over Internet Protocol (VoIP) is one of the most widely discussed and analyzed technologies in the telecommunication industry. Under VoIP the voice conversations are packetized and intermingle with data packets in the networks. This integration has the potential to maximize the use of network bandwidth, but comes at a price. The voice packets must be delivered from the source to the destination in less than 150 milliseconds. In order to achieve this differentiated service, many queue management disciplines have been proposed to handle the voice packets. In this paper we present three queue disciplines and give comprehensive discussion of the analytic performance congestion modeling of the voice and data packets under these disciplines. These models are usually based on Poisson packet arrivals for voice and data; we discuss where and under what conditions the Poisson process is a good model. In addition, we present data to show that the service time of data packets can be modeled by a D3 probability distribution. That is, a distribution that takes on three values each with a certain probability. The voice service time will be fixed length and depend on the codec that is being used. We present analytic expressions of the voice and data latency, jitter and packet loss. In addition, we present a numerical procedure that can easily be used to generate the complete Cumulative Distribution Function (CDF) of queue and system delay for each type of packet.
M.L. Huang, P.H. Brill, D. Gross. 2005. "A Weighted Estimation Method for the Pareto Variance," 2005 Proceedings of the American Statistical Association, Section on Nonparametric Statistics. Alexandria, VA: American Statistical Association. Also presented at the Joint Statistical Meetings 2005 (JSM2005), Minneapolis, MN, August 7-11, 2005.
ABSTRACT [+]
ABSTRACT [-]
The Pareto distribution is a heavy-tailed distribution with many applications. There are problems for estimating the Pareto variance. This paper uses a weighted empirical distribution function (i.e., level-crossing empirical distribution function [LCEDF]) to estimate the population Pareto variance. An efficiency function of this estimator relative to the classical sample variance estimator is given and studied. Monte Carlo simulation results show the new estimator is more efficient than the classical-moment, maximum-likelihood and other estimators.
Fischer, M.J., and D.M. Masi. 2005. "Voice Packet Arrival Models and Their Effect on Packet Performance." Applied Telecommunications Symposium. April 3-7, 2005. San Diego, Calif.
ABSTRACT [+]
ABSTRACT [-]
Voice over Internet Protocol (VoIP) is the most highly discussed and studied technology within the IP arena. Central in this discussion is the need to be sure the voice packets are delivered with the desired quality of service agreements. For the quality of voice to be acceptable, packets must be delivered within 150 ms to 200 ms, jitter free, and without loss. To ensure these performance measures are met, performing modeling of VoIP systems is critical.
In this paper, we discuss the overall problem of packet traffic characterization in an IP network carrying packetized voice traffic. Our discussions will focus on how to model the voice packet arrival process. Recent research has shown that if the number of active voice sessions is fairly large, then using a Poisson process for characterizing the packet arrival process is acceptable. This result is an application of the well-known Central Limit Theorem for Point Processes (CLTPP). This theorem says that the superposition of N independent and identically distributed renewal processes tends to a Poisson process as N gets large. VoIP packets are a fixed size for a given codec. These results would indicate that one could use an M/D/1/K queueing model to characterize the voice packet performance. In this paper, we study and characterize under what conditions that would be a good model and when it would not; we also study how various suggested voice packet arrival models can result in different levels of congestion.
Fischer, M.J., D.M. Masi, D. Gross, J.F. Shortle, and P.H. Brill. 2005. "Development of Procedures to Analyze Queueing Models with Heavy-Tailed Interarrival and Service Times - Phase III," 2005 NSF Design, Service, and Manufacturing Grantees and Research Conference. January 3-6, 2005. Scottsdale, Ariz.
ABSTRACT [+]
ABSTRACT [-]
In many modern applications of queueing theory, the classical assumption of exponentially decaying interarrival-time or service-time distributions does not apply. In particular, Internet and insurance risk problems may involve heavy-tailed distributions. A difficulty with heavy-tailed distributions is that they may not have closed-form, analytic Laplace Transforms. This makes numerical methods, which use the Laplace Transform, challenging. Previous researchers, to get around this, have approximated these heavy-tailed distributions by families of exponentials. In this research, we use different approaches. One method approximates the Laplace Transform needed to produce the output measures (waiting-time and system-size distribution) by using a discretized version of the heavy-tailed distribution itself (Transform Approximation Method [TAM]). Another method avoids using the Laplace Transform directly by solving an integral equation involving the complementary cdf of the heavy-tailed distribution (Level Crossing [LC] method). While discrete-event simulation is an alternative to analytical queueing analyses, this also has its limitations in that it usually can only produce mean measures of output performance. It also has difficulty simulating certain of the heavy-tailed distributions, especially with large coefficients of variation (standard deviation divided by mean). Our recent research has focused on the numerical comparisons of the TAM Recursion Method (TRM) and the Fourier Method. To better understand these methods, we have investigated the continuity properties of the M/DN/1 queue. When applying TAM to the M/G/1 queue, one is really studying an M/DN/1 queue; and the continuity properties of the waiting time process for that queue can provide insights into the application of numerical inversions methods. We are also investigating different forms of the very heavy-tailed Pareto distribution for P/M/1 and M/P/1 queues, and are finding that significantly different results can be obtained, depending on the particular form of the Pareto used. In addition, we have developed an analytic network performance algorithm from an Internet Protocol (IP) network. The last areas of research have been in the application of TAM and TRM in the study of congestion systems that have applied interest.
Masi, D., Fischer, M., and Garbin, D. "Analytically Modeling Cyber Attacks in Internet Protocol Networks." 2004 Advanced Simulation Technologies Conference. April 18-22, 2004. Arlington, Va. p. 69-74.
ABSTRACT [+]
ABSTRACT [-]
Network attacks are a growing national concern in both the government and private sector. Increasing amounts of federal funding are devoted to the detection of and response to cyber attacks. However, the protection of critical federal telecommunications networks should also include proactive modeling of these threats, in addition to the detection and response efforts that are prevalent. This paper focuses on analytic queueing and simulation capabilities that have been developed to analyze the performance of federal private Internet Protocol networks.
We have developed an initial version of an analytical model called the Internet Protocol Network Performance and Analysis Tool and a simulation model using the Operations Network Modeler. Calibration of the analytic tool and the simulation for all link queues based on a realistic packet distribution indicates close agreement in the two analyses. Link loads, mean link delays, link jitter, and delay distribution were compared for each link, under baseline and attack network conditions.
Fischer, M.J., Masi, D.M.B., Brill, P.H., Gross, D., and Shortle, J. 2004. "Development of Procedures to Analyze Queueing Models with Heavy-Tailed Interarrival and Service Times - Phase II," 2004 NSF Design, Service, and Manufacturing Grantees and Research Conference, ed. R. Kovacevic. Dallas, Texas. January 5-8, 2004.
ABSTRACT [+]
ABSTRACT [-]
In many modern applications of queueing theory, the classical assumption of exponentially decaying service distributions does not apply. In particular, Internet and insurance risk problems may involve heavy-tailed distributions. A difficulty with heavy-tailed distributions is that they may not have closed-form, analytic Laplace transforms. This makes numerical methods, which use the Laplace transform, challenging. Previous researchers, to get around this, have approximated these heavy-tailed distributions by families of exponentials. The approaches developed under this research avoid the problems and pitfalls of finding approximating distributions by using the actual heavy-tailed distributions themselves. One method approximates the Laplace Transform needed to produce the output measures (waiting-time and system-size distributions) of interest by directly approximating it using a discretized version of the heavy-tailed distribution itself (transform approximation method [TAM]). Another method avoids using the Laplace Transform directly by solving an integral equation involving the complementary CDF of the heavy-tailed distribution (level crossing method [LC]). While discrete-event simulation is an alternative to analytical queueing analyses, this also has its limitations in that it usually can only produce mean measures of output performance. It also has difficulty simulating certain of the heavy-tailed distributions, especially with large coefficients of variation (standard deviation divided by mean). Our resent research has focused on the numerical comparisons of the TAM Recursion Method (TRM) and the Fourier method. To better understand these methods, we have investigated the continuity properties of the M/DN/1 queue. When applying TAM to the M/G/1 queue one is really studying an M/DN/1 queue; and the continuity properties of the waiting time process for that queue can provide insights into the application of numerical inversions methods. The last area of research has been in the application of TAM and TRM in the study of congestion systems that have applied interest.
Fischer, M.J., Masi, D.M.B., Gross, D., and Shortle, J. 2003. "Using the Correct Heavy-Tailed Arrival Distribution in Modeling Congestion Systems." Proceedings from the Eleventh International Conference on Telecommunication Systems, Modeling and Analysis. Monterey, Calif. October 2-5, 2003,
ABSTRACT [+]
ABSTRACT [-]
Internet traffic studies have shown that heavy-tailed probability distributions characterize these traffics. The Pareto, Weibull, and LogNormal distributions are the ones most frequently used in these studies. Associated with these distributions is the characterization of traffic peakedness with respect to the packet arrival process. We define an arrival process to be peaked (or bursty) if the variance of the offered load is greater than the mean. A fact that seems to be overlooked is that different levels of congestion may be obtained depending on which probability distribution is used in the congestion model-even when the mean and variance of the probability distributions are equal. In this paper, we study the effect of different heavy- or power-tailed arrival distributions on the blocking probability in loss systems and latency in delay systems. Our numerical investigations show there is an ordering with respect to these congestion measures based on the distributions that are used.
Fischer, M.J., Masi, D.M.B., Gross, D., Shortle, J., and Brill, P.H. 2003. "Applying the TAM Recursion Method (TRM) to Analyze an Internet Type Congestion Problem," Applied Telecommunications Symposium. Orlando, Fla. March 31, 2003.
ABSTRACT [+]
ABSTRACT [-]
We have developed a method called the Transform Approximation Method (TAM) to analyze congestion systems where heavy-tailed distributions are used to characterize the customer arrival or service processes. The well known problem in studying these systems is that these distributions do not possess a closed form Laplace transform. This fact negates the direct application of well-established results from Queueing Theory. TAM and its associated numerical procedure, called the TAM Recursion Method (TRM), were developed to overcome these problems. Newman et al. (2001) have developed a probability distribution of packet sizes based on samples taken between 28 August 2000 and 13 September 2000 between core Internet routers from Merit Network, Inc. Their tests show that packets come primarily in four sizes. It turns out that this is a special case of the type of queueing system assumed for TAM, and the TRM is ideally suited to analyze such systems. We use their packet size distribution and TRM to numerically study link congestion. In addition, we show how to extend this analysis by considering the same example when voice Internet Protocol (IP) packets may be present.
Fischer, M.J., Masi, D.M.B., Brill, P.H., Gross, D., and Shortle, J. 2003. "Development of Procedures to Analyze Queueing Models with Heavy-Tailed Interarrival and Service Times - A Status Report." 2003 NSF Design, Service and Manufacturing Grantees and Research Conference Proceedings. ed. R.G. Reddy. Birmingham, Ala. January 6-9, 2003.
ABSTRACT [+]
ABSTRACT [-]
In many modern applications of queueing theory, the classical assumption of exponentially decaying service distributions does not apply. In particular, Internet and insurance risk problems may involve heavy-tailed distributions. A difficulty with heavy-tailed distributions is that they may not have closed-form, analytic Laplace transforms. This makes numerical methods, which use the Laplace transform, challenging. Previous researchers, to get around this, have approximated these heavy-tailed distributions by families of exponentials. The approaches developed under this research avoid the problems and pitfalls of finding approximating distributions by using the actual heavy-tailed distributions themselves. One method approximates the Laplace Transform needed to produce the output measures (waiting-time and system-size distributions) of interest by directly approximating it using a discretized version of the heavy-tailed distribution itself (transform approximation method [TAM]). Another method avoids using the Laplace Transform directly by solving an integral equation involving the complementary CDF of the heavy-tailed distribution (level crossing method [LC]). While discrete-event simulation is an alternative to analytical queueing analyses, this also has its limitations in that it usually can only produce mean measures of output performance. It also has difficulty simulating certain of the heavy-tailed distributions, especially with large coefficients of variation (standard deviation divided by mean). New procedures for discrete-event simulation involving quantile estimators are also be investigated. In this paper we summarize the use of these techniques on the G/M/c and M/G/1 queues.
Gross, D., Shortle, J., Fischer, M.J., and Masi, D.M.B. 2002. "Difficulties in Simulating Queues with Pareto Service." Proceedings of the 2002 Winter Simulation Conference. ed. E. Yücesan, C.H. Chen, J.L. Snowdon, and J.M. Charnes. San Diego, Calif. December 2002. p. 407-415.
ABSTRACT [+]
ABSTRACT [-]
M/G/1 queues, where G is a heavy-tailed distribution, have applications in Internet modeling and modeling for insurance claim risk. The Pareto distribution is a special heavy-tailed distribution called a power-tailed distribution, and has been found to serve as adequate models for many of these situations. However, to get the waiting time distribution, one must resort to numerical methods, e.g., simulation. Many difficulties arise in simulating queues with Pareto service and we investigate why this may be so. Even if we are willing to consider truncated Pareto service, there still can be problems in simulating if the truncation point (maximum service time possible) is too large.
Shortle, J. F., M. J. Fischer, D. Gross, and D. Masi. 2003. "Numerical Methods for Analyzing Queues with Heavy-Tailed Distributions." Telecommunications Network Design. G. Anandalingam, S. Raghavan (eds.), Kluwer Academic Publishers, pp. 193-206, Boston, Mass.
ABSTRACT [+]
ABSTRACT [-]
In many Internet-type queues, arrival and service distributions are heavy-tailed. A difficulty with analyzing these queues is that heavy-tailed distributions do not generally have closed-form Laplace transforms. A recently proposed method, the Transform Approximation Method (TAM), overcomes this by numerically approximating the transform. This paper investigates numerical issues of implementing the method for simple queueing systems. In particular, we argue that TAM can be used in conjunction with the Fourier-series method for inverting Laplace transforms, even though TAM is a discrete approximation and the Fourier method requires a continuous distribution. We apply concepts to compute the waiting time distribution of an M/G/1 priority queue.
Fischer, M. J., Masi, D. M. B., Gross, D., Shortle, J., and Brill, P. H. 2001. "Using Quantile Estimates in Simulating Internet Queues with Pareto Service Times." Proceedings of the 2001 Winter Simulation Conference. ed. B.A. Peters, J.S. Smith, D.J. Medeiros, and M. W. Rohrer. Washington, D.C., December 2001, p. 477-485.
ABSTRACT [+]
ABSTRACT [-]
It is readily apparent how important the Internet is to modern life. The exponential growth in its use requires good tools for analyzing congestion. Much has been written recently asserting that classical queueing models assuming Poisson arrivals or exponential service cannot be used for the accurate study of congestion in major portions of the Internet. Internet traffic data indicate that heavy-tailed distributions (e.g., Pareto) serve as better models in many situations for packet service lengths. But these distributions may not possess closed-form analytic Laplace transforms; hence, much of standard queueing theory cannot be used. Simulating such queues becomes essential; however, previous research pointed out difficulties in obtaining the usual moment performance measures such as mean wait in queue. In this paper, we investigate using quantile estimates of waiting times (e.g., median instead of mean), which appear to be considerably more efficient when service times are Pareto.
Gross, D., Shortle, J., Fischer, M. J., and Masi, D. M. 2001. "Using Quantile Estimates in Simulating Internet Queues with Heavy-Tailed Service Times." 5th World Multi-Conference on Systemics, Cybernetics and Informatics. July 22-25, 2001. Orlando, Fla. p. 414-419.
ABSTRACT [+]
ABSTRACT [-]
Internet traffic data indicate that heavy-tailed distributions, i.e., distributions for which the tails of the probability distributions decay much slower than exponential, serve as appropriate models in many Internet situations. Classical queueing theory (which generally requires Poisson flows) used so successfully in other telecommunications situations cannot be used here, since heavy-tailed distributions violate the necessary assumptions. Heavy-tailed distributions include the Pareto, Lognormal and Weibull distributions, and these distributions have been seen to be appropriate for describing many Internet traffic flows, e.g., packet service lengths. For queueing models that cannot be treated analytically, discrete-event simulation is often employed. But standard methods for obtaining output performance measures, such as the mean delay time (queue wait) also do not work well for these types of distributions. We find that instead of using moment measures for output performance (mean and variance of delay), estimates of quantiles of the delay distribution often perform much better, and actually provide more meaningful information concerning system congestion. Results of several simulation experiments illustrate this.
Fischer, M. J., Girard, A. M., Masi, D. M., and Gross, D. 2001. "Simulating Internet-Type Queues with Heavy-Tailed Service or Interarrival Times." Proceedings of the Applied Telecommunication Symposium. ed. Bohdan Bodnar. 2001 Advanced Simulation Technologies Conference. Seattle, Wash. April 22-26. Society for Modeling and Simulation International (SCS). p. 161-167.
ABSTRACT [+]
ABSTRACT [-]
There has been much written recently asserting that classical queueing models assuming Poisson arrivals or exponential service cannot be used for the accurate study of congestion in major portions of the Internet. Internet traffic data indicate that heavy-tailed distributions serve as better models in many situations for packet interarrival times and service lengths. But these distributions may not possess a closed-form analytic Laplace transform; hence, much of standard queueing theory cannot be used. In this paper, we apply and discuss the use of simulation methods on queues with heavy-tailed interarrival or service times. An extensive number of numerical examples are given, and the results are validated using comparisons with known results when possible or other numerical methods otherwise. We have found difficulties in simulating some queues with heavy-tailed service times. We present cases where simulation does not compare well with theoretical results, and discuss some alternative performance measures for these cases.
Conference Presentations
Fischer, M.J., D.M.B. Masi, J. F. Shortle, and D. Gross, "Simulation Techniques and Numerical Methods for Analyzing Queueing Systems with Heavy-Tailed Distributions," American Mathematical Society/Joint Mathematics Meetings, Washington, DC, Jan. 5-8, 2009
ABSTRACT [+]
ABSTRACT [-]
Many systems that involve heavy-tailed distributions are difficult to analyze analytically. The presence of heavy tails often presents challenges that do not exist for similar systems without heavy tails. This talk presents an overview of some of these issues as well as numerical methods and simulation techniques for addressing the problems. For example, G/G/1 queues, which have applications in telecommunications and insurance-risk modeling, pose challenges for simulation when the underlying distributions are heavy-tailed. We investigate why this may be so. Even if we are willing to consider truncated distributions (as a way to model some large but finite maximum for the distributions in question), there still can be problems in simulating if the truncation point is too large. Simulation techniques, such as importance sampling, and other numerical techniques to address these issues, are discussed.
Fischer, M.J. and D.M.B. Masi, 2005. "Modeling Overloaded VoIP Systems," Winter Simulation Conference, Case Studies Track, Orlando, FL, December 2005.
ABSTRACT [+]
ABSTRACT [-]
Since 9/11 many telecommunications systems have seen the need to deal with overloading during high traffic conditions. As the use of VoIP increases an important question that needs to be answered is: "Can the voice packets be delivered in a timely fashion when the there has been a significant increase in traffic?" In this paper we considered the problem of modeling VoIP systems in an overloaded condition. We look at the problem from a simulation and analytic point of view. We present analytic models for the packet latency and jitter and loss probability for the three prevalent disciplines being used for VoIP today: First Come First Served, Priority Queue and Weighted Fair Queueing Systems. In addition, we investigate how simulation languages like GPSS/H compare with respect to runtime with simulation models developed using Visual Basic for Applications and if their runtimes are acceptable for practical use.
Fischer, M.J. and Masi, D.M. 2005. "Voice over Internet Protocol (VoIP) Performance Modeling - A Discussion", 17th Triennial Conference of the International Federation of Operational Research Societies (IFORS) 2005, Honolulu, Hawaii, 11-15 July 2005.
ABSTRACT [+]
ABSTRACT [-]
In this presentation we will discuss the overall problem of performance modeling of Voice over IP systems. Our discussions will focus on potential queue disciplines to support meeting the required quality of service (QoS) for voice and the availability of models to evaluate the voice QoS metrics. In addition, we present a discussion of models for the voice packet arrival process.
Shortle, J. and Brill, P. 2005. "Analytical and Numerical Solutions to M/Discrete/1/K Queues", 13th INFORMS Applied Probability Society Conference, Ottawa, Ontario, Canada, July 6-8, 2005.
ABSTRACT [+]
ABSTRACT [-]
This talk presents analytical formulas for the steady-state distribution of queue-wait in the M/G/1 and M/G/1/K queues, where the service time for each customer is a positive integer multiple of a constant D > 0. Although the solutions are analytic, there are numerical difficulties in evaluating the expressions. Thus, we also present several numerical algorithms to compute the distribution. In particular, when the service distribution is sparse, the queue-wait distribution can be computed much more quickly than a straight-forward evaluation.
Masi, D.M., and M.J. Fischer. 2005. "Analytically Modeling Worm Attacks in Internet Protocol Networks," Ninth INFORMS Computing Society (ICS) Conference. Annapolis, Md. January 5-7, 2005.
ABSTRACT [+]
ABSTRACT [-]
Network attacks are a growing national concern in both the government and private sector. This presentation focuses on analytic queueing and simulation capabilities that have been developed to analyze the performance of Federal Private IP Networks, especially in the presence of worm attacks.
We have developed an analytical queueing model called the IP Network Performance and Analysis Tool. The assumptions made and methodology used to analyze network performance using analytical queueing and numerical approaches will be presented. Worms typically propagate by first infecting a single node; infected node(s) then scan other network nodes and infect those that are vulnerable. Thus propagation of the worm occurs in stages as more and more nodes are infected. The impact of the scanning traffic during worm propagation on network performance will be examined. The relationship between our approach and to epidemic models discussed in the literature will be discussed. The problems with incorporating the different approaches into analytic performance models, the use of stages in modeling, and the relationship of stages to continual time will be discussed. The mitigating effect of worm deactivation is also modeled. Numerical results and validation will be presented.
Shortle, J.F., M.J. Fischer, D.M. Masi., S. Gordon, and S. Rutherford. 2004. "Analytical Models for Internet Protocol Networks." INFORMS Annual Meeting. Denver, Colo. October 25, 2004.
ABSTRACT [+]
ABSTRACT [-]
This talk presents an analytical network model of queues for Internet Protocol networks. We discuss computational complexity issues with evaluating performance metrics using this model. Finally, we compare speed and accuracy with existing network simulators such as OPNET.
Brill, P. Fischer, M.J., and Shortle, J.F. 2004. "Analytical Results for M/Discrete/1 Queues." CORS/INFORMS Joint International Meeting. Banff, Alberta, Canada. May 16-19.
ABSTRACT [+]
ABSTRACT [-]
We discuss: (a) analytical properties - continuity, jump discontinuities, convexity, (b) analytical formulas; for the steady state PDF and CDF of the wait before service in M/Discrete/1 queues. The derived properties are useful for analyzing M/Discrete/1 queues and model variants. The results also provide analytical benchmarks to test the precision of new methods for computing the steady state distribution of wait in M/G/1 queues with general service time distributions.
Fischer, M.J., Masi, D.M.B., Gross, D., and Shortle, J.F. 2004. "One-Parameter, Two-Parameter, Three-Parameter Pareto: Is There a Modeling Difference?" CORS/INFORMS Joint International Meeting. Banff, Alberta, Canada. May 16-19.
ABSTRACT [+]
ABSTRACT [-]
Data analysis has shown that the Pareto distribution characterizes many Internet traffic statistics. But the Pareto has three forms based on the number (1, 2, or 3) of parameters used. Does it make a difference which form is used in these congestion models? We examine this question using the Pareto for arrivals to delay and loss systems. We discuss reasons why even when the mean and variance of the distributions are the same, one can get significant different levels of performance measures.
Masi, D., Fischer, M., and Garbin, D. "Modeling IP Networks: OPNET and Analytics." 7th INFORMS Telecommunications Conference. Boca Raton, Fla. March 7-10, 2004.
Shortle, J., Fischer, M., Gross, D., and Masi, D. "Piecewise-Polynomial Approximations for Heavy-Tailed Distributions." INFORMS Fall 2003. Atlanta, Ga. October 19-22, 2003.
ABSTRACT [+]
ABSTRACT [-]
A difficulty in analyzing queues with heavy-tailed distributions is that, in general, they do not have closed-form Laplace transforms. A recently proposed method, the Transform Approximation Method (TAM), overcomes this by numerically approximating the transform. In this talk, we discuss recent improvements which significantly speed up the method. We also compare TAM with existing methods for approximating heavy-tailed distributions.
Gross, D., Shortle, J., and Masi, D.M.B. 2002. "Why Simulating Queues With Pareto Service Is So Difficult." INFORMS Fall 2002. San Jose, Calif. November 17-20, 2002.
ABSTRACT [+]
ABSTRACT [-]
It has been noted in the literature that M/G/1 queues with Pareto service times are difficult to simulate. We investigate causes of this difficulty, and will discuss some implications in practice. It turns out that if the actual Pareto distribution is a truncated one, problems in simulating may still arise.
Shortle, J.F., P.H. Brill, M.J. Fischer, D. Gross, and D.M.B. Masi. 2002. "Numerical Methods to Analyze Queues with Heavy-Tails." AOL/CIT Finding Common Ground Research Day. Virginia's Center for Innovative Technology (CIT). Herndon, Va. Nov. 6.
ABSTRACT [+]
ABSTRACT [-]
This research gives fast, numerical solutions to queueing problems with heavy-tailed distributions. By approximating the Laplace transform of a probability distribution, we can efficiently use standard queueing models to approximate delay metrics for single-node queueing systems.
Shortle, J. F., and Fischer, M. J. 2002. "Using the Transform Approximation Method to Analyze Queues with Heavy-Tailed Distributions." First Madrid Queueing Conference on Queueing. Madrid, Spain. July 2-5.
ABSTRACT [+]
ABSTRACT [-]
Many modern queueing problems involve distributions which are heavy-tailed. This means their distribution functions decay more slowly than any exponential function. Analyzing queues with these distributions is difficult since they do not have closed-form, analytic Laplace transforms. This paper investigates a recently proposed method for numerically approximating Laplace transforms, called the Transform Approximation Method (TAM). While TAM can be used to approximate the Laplace transform of a heavy-tailed distribution, one must still invert a Laplace transform to recover the desired probability distribution. This paper investigates using TAM with two numerical methods for inverting Laplace transforms. In particular, we compare the well-known Fourier-series method with a recursion method specifically adapted for TAM. We give several benchmark problems and compare results for several simple queueing systems.
Fischer, M. J., P. Brill, and J. F. Shortle. 2002. "The Transformation Approximation Method and Level Crossing." CORS 2002. Toronto, Canada. June 3-5.
ABSTRACT [+]
ABSTRACT [-]
The Transform Approximation Method (TAM) has been used to study queueing systems where no Laplace transform exist for either the arrival or service distributions. A theoretical understanding of TAM can be gained by using Level Crossing arguments. In this talk we discuss this relationship and relate the Level Crossing results to convergence issues associated with TAM.
Shortle, J. F., and M. J. Fischer. 2002. "Numerical Methods to Analyze Queues with Heavy-Tailed Service." CORS 2002. Toronto, Canada. June 3-5.
ABSTRACT [+]
ABSTRACT [-]
We have developed the Transform Approximation Method (TAM) to analyze queues with heavy- or power-tailed distributions. We discuss the accuracy of TAM compared with other numerical methods, and discuss practical aspects of using TAM in conjunction with other queueing analysis methods.
Shortle, J. F., M. J. Fischer, D. Gross, and D. M. B. Masi. 2002. "Numerical Methods for Analyzing Queues with Heavy-Tailed Distributions." 6th INFORMS Telecommunications Conference. Boca Raton, Fla. March 10-13.
ABSTRACT [+]
ABSTRACT [-]
In many modern applications of queueing theory, the classical assumption of exponentially decaying service times does not apply. This is particularly true in Internet-type queues, where service and arrival distributions are often heavy-tailed. Intuitively, this means there is a non-trivial probability of an extremely large event. A difficulty with analyzing queues with these distributions is that heavy-tailed distributions, in general, do not have closed-form Laplace transforms. A recently proposed method, the Transform Approximation Method (TAM), overcomes this by numerically approximating the transform. An advantage of the method is that it is quite general and can be used for any distribution. This paper investigates numerical issues of implementing the method for simple queueing systems. In particular, we show that using TAM in conjunction with the Fourier-series method provides accurate solutions in little time.
Shortle, J. F., M. J. Fischer, D. Gross, and D. M. B. Masi. 2001. "Numerical Methods for Analyzing Queues with Heavy-Tailed Service Distributions." INFORMS Fall 2001. Miami Beach, Fla. Nov. 4-7.
ABSTRACT [+]
ABSTRACT [-]
We have developed the transform approximation method (TAM) to analyze queueing systems with heavy- or power-tailed service distributions. We discuss and compare practical aspects of using TAM in conjunction with other queueing analysis methods.
Brill, P. H., and Harris, C. M. "G/M/c Queues with Power-tailed Interarrivals and a Level Crossing Computational Method for their Analysis." INFORMS Fall 2000 Conference. San Antonio, Texas. Nov. 5-8.
ABSTRACT [+]
ABSTRACT [-]
We analyze the waiting time in G/M/c queues having power-tailed interarrival times, analytically using a level crossing method. This method provides numerical results when interarrival times have Pareto, folded Cauchy or log-normal distributions. Simulations confirm the results. Applications to Internet traffic are discussed.
Fischer, M. J., Gross, D., Shortle, J., and Masi, D. M. 2001. "Experiences in Using the Transform Approximation Method to Analyze Queues with Heavy Tailed Service Distributions." Applied Probability Conference. July 26, 2001. New York City.
ABSTRACT [+]
ABSTRACT [-]
We have developed the Transform Approximation Method (TAM) to analyze queueing systems with heavy or power tailed service distributions. In this talk, we will discuss our experiences in using TAM on these type queueing systems. Our focus will be on the numerical and practical aspects of our experiences, as well as the comparisons that we have made with other analysis methods.
Fischer, M. J., Gross, D., Brill, P. H., and Masi, D. M. 2001. "Development of Procedures for Utilizing Power-Tail Distributions in Queueing Models of Internet Traffic." NSF Grantees Conference. Jan. 2001.
ABSTRACT [+]
ABSTRACT [-]
This presentation was given at the National Science Foundation Grantees conference in January 2001 (Tampa, Florida). The talk summarized work to date on using the Transform Approximation Method (TAM) and Level Crossing methods to analyze queues with heavy tails. The TAM results focused on the uniform sampling method for generating the samples.
Fischer, M. J., and Harris, C. M. 2000. "A Transform Approximation Method & its Use in Analyzing Queues with Heavy-Tail Arrival or Service Distributions." INFORMS Fall 2000 Conference. San Antonio, Texas. Nov. 5-8.
ABSTRACT [+]
ABSTRACT [-]
We present and discuss the use of a TAM in the analysis of queues that have heavy- or long-tailed arrivals or service distributions. Computational experiences with TAM and performance improvement techniques are discussed. Comparisons with simulation, level crossing and other methods are presented.
Fischer, M. J., Gross, D., and Harris, C. M. 2000. "Utilizing Power-Tail Distributions in Queueing Models of Internet Traffic." INFORMS Spring 2000 Conference. Salt Lake City, Utah. May 7-10, 2000.
ABSTRACT [+]
ABSTRACT [-]
Internet traffic data indicate that long-tailed (power-tailed, fat-tailed) distributions typically serve as better models for packet interarrival times and/or service lengths. These distributions have properties that make it impossible to derive manageable queueing theory formulas for measuring congestion. We offer a plan to apply a new method for approximating Laplace transforms of arbitrary probability distributions.
Gross, D., Harris, C. M., and Masi, D. M. 2000. "Simulation of Power-Tail Distributions in Queueing Problems." INFORMS Fall 2000 Conference. San Antonio, Texas. Nov. 5-8.
ABSTRACT [+]
ABSTRACT [-]
Using power-tail distributions in discrete-event simulation modeling of Internet congestion (often necessary in the absence of analytical results) can be fraught with difficulty, especially when dealing with high coefficients of variation. We illustrate these difficulties and compare simulation to the numerical procedures of the previous 2 papers [in the San Antonio session].
Gross, D., and Fischer, M. J. 2000. "Simulation of Heavy-Tail Distributions in Queueing Models." INFORMS Spring 2000 Conference. Salt Lake City, Utah. May 7-10. Please note title in meeting bulletin is somewhat different: "Simulation of Queueing Problems Power-Tail distributions in Queueing Models."
ABSTRACT [+]
ABSTRACT [-]
Much recent research has been directed at the use of power-tail distributions in modeling congestion in the Internet. But using discrete-event simulation for such problems, for example, is fraught with difficulty because of the unusual tail behavior inherent in these types of distributions. We propose an approach combining a new method for approximating Laplace transforms.
Fischer, M.J. et al. 2000. "Web Site Performance and the M/P/1 Queue," INFORMS Spring 2000 Conference. Salt Lake City, Utah. May 7-10.
Fischer, M.J. et al. 2000. "Pareto Queues," INFORMS Fall 1999 Conference, November.
Harris, C. 1998. "Internet Traffic Engineering: The Pareto/D/1 Queue," WINFORMS.
