Application of extreme value theory to the analysis of a network simulation

ABSTRACT

In this paper we present an application of the extreme value theory to the results of a GPSS simulation of a network of queues which is not suitable to be modeled by a product form and, so, to be treated by operational analysis. The objective of this work is to estimate the finite buffer size of the queues such that packets (elements) arriving to the system at a lower rate than one fixed have a very low probability — usually, less than 10-8 — to be rejected (because the buffer is full). To carry out this task only by means of simulation would require a large amount of computational effort. Extreme value theory is employed to estimate, from the results of a reduced simulation, which buffer size corresponds to this loss probability. The extreme value theory is presented and the way it can be applied to the simulation analysis is explained. Further refinements, in order to extend its extrapolative capability, are introduced, and also the way to calculate confidence intervals. Numerical results are presented.

REFERENCES

• 1: Berberana, I. 1988a. "Application of the Extreme Value Theory to the estimation of Probability Tails. I. Classic Method." Systems Department Technical Report, Telefbnica I+D, Madrld. (Oct)
• 2: Berberana, I. 1988b. "Application of the Extreme Value Theory to the estimation of Probability Tails. II. Generalized Method." Systems Department Technical Report, Telefdnica I+D, Madrid.(Dec)
• 3: Castillo, E. 1988. Extreme Value Theory in Engineering. Academic Press, S. Diego.
• 4: Guida, M.; D Iovino; and M. Longo. 1988. "Comparative Performance Analysis of Some Extrapolative Estimators of Probability Tails." IEEE Journal on Selected Areas in Communications 6, n 1(Jan). 76-84.
• 5: Galambos, j. 1987. The Asymptotic Theory of Extreme Order Statistics, Znd edition. Robert E. Krleger Publishing Co. Malabar, Florida.
• 6: Gumbeil, E. 3. 1958. Statistics of Extremes. Columbia University Press, N. York.
• 7: Haan, L. de. 1970. On Regular Variation and its Application to ~eak Convergence of Sample Extremes. Mathematical Centre Tract 32, Mathematic Centre, Amsterdam, Holland.
• 8: Heyde, C.C. 1971. "On the Growth of the Maximum Queue Length in a Stable Queue." Operations Research 19: 447-452.
• 9: Jeruchim, M.C. 1976."0n the Estimation of Error Probability Using Generalized Extreme Value Theory." IEEE Transactions on Information Theory 22, n~ 1(3an)'I08-110.
• 10: 3eruchim, M.C. 1984. "Techniques for Estimating the Bit Error Rate in the Simulation of Digital Communication Systems." IEEE Journal on Selected Areas in Communications 2, n~ 1 (Jan): 153-170.
• 11: Leadbetter, H.D.: G. Lindgren: and H. Rootzen. 1983. Extremes and Related Properties of Random Sequences and Processes. Springer-Verlag, Berlin
• 12: Ratz, H.C. 1988. "Extreme Value EnEineering for Local Network Traffic." IEEE Transactions on Co~nlcations 36, n IZ(Dec)- 1302-1308.
• 13: Resnick, S.I. 1987. Extreme Values, Regular Variations and Point Processes. Springer-Verlag, N. York.
• 14: Tiago de Oliveira, J. (ed) 1984. Statistical Extremes and Applications. D. Reidel, Dordrecht, Holland.
• 15: Weinstein, S.B. 1973. "Theory and Application of Some Classical and Generalized Asymptotic Distributions of Extreme Values." IEEE Transactions on Information Theory 19, n~ 2(March)- 148-154.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Performance, Theory