The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Methods for Performance Evaluation of Networks: Fast Simulation of Loss Systems and Analysis of Internet Congestion Control

Pasi Lassila

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission for public examination and debate in Auditorium S4 at Helsinki University of Technology (Espoo, Finland) on the 12th of October, 2001, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-5637-1)   [637 KB]
Dissertation is also available in print (ISBN 951-22-5632-0)

Abstract

Performance evaluation of modern telecommunication networks by means of mathematical modeling frequently results in a situation, whereby an exact analytical solution poses a difficult problem in terms of computational evaluation. In this thesis, two such problems are studied and a different approach for easing the computational burden is developed in each case.

The first part of the thesis considers the problem of evaluating blocking probabilities in loss systems, which are often used as models for the call scale behavior of modern networks. In this case, the solution to the problem can be given a well known analytical expression, but in practice it can not be used for computing the blocking probabilities due to the prohibitive size of the state space of the system. Then one can use simulation to obtain estimates of the blocking probabilities. For increasing the efficiency of the simulation, i.e., for reducing the variance of the estimates, several novel and increasingly more efficient methods are presented. Noticeable variance reductions are obtained by applying the method of conditional expectations. However, even greater variance reductions are gained by using importance sampling. In the thesis several importance sampling based methods are presented, of which the inverse convolution approach provides variance reductions surpassing all previously reported results in the literature.

In the second part of the thesis, the problem of congestion control in the Internet is studied. Specifically, the focus is on modeling the interaction between the TCP rate control algorithm and the RED buffer management mechanism. By using various analytical approximations, a novel dynamic model is derived for describing the interaction between an idealized TCP source population and a RED controlled buffer. Ultimately, the model consists of a set of coupled retarded functional differential equations (RFDEs) governing the time dependent expectations of the stochastic system state variables. This model is used to explore the dependency of the equilibrium of the system on the parameters of the physical system. Additionally, methods are derived allowing the stability of the system to be analyzed. In particular, sufficient and necessary conditions are obtained for the RFDE system, such that the system is asymptotically stable.

This thesis consists of an overview and of the following 8 publications:

  1. P. Lassila, J. Virtamo, Using Gibbs Sampler in Simulating Multiservice Loss Systems, in Proceedings of IFIP TC6/WG6.3 7th International Conference on Performance of Information and Communications Systems, PICS '98, Lund, Sweden, May 1998, pp. 261-272.
  2. P. Lassila, J. Virtamo, Variance Reduction in Monte Carlo Simulation of Product Form Systems, IEE Electronics Letters, vol. 34, no. 12, 1998, pp. 1204-1205.
  3. P. Lassila, J. Virtamo, Efficient Importance Sampling for Monte Carlo Simulation of Loss Systems, in Proceedings of the 16th International Teletraffic Congress, ITC 16, Edinburgh, United Kingdom, June 1999, pp. 787-796.
  4. P. Lassila, J. Virtamo, Nearly Optimal Importance Sampling for Monte Carlo Simulation of Loss Systems, ACM Transactions on Modeling and Computer Simulation, vol. 10, no. 4, October 2000, pp. 326-347.
  5. P. Lassila, J. Karvo, J. Virtamo, Efficient Importance Sampling for Monte Carlo Simulation of Multicast Networks, in Proceedings of IEEE INFOCOM 2001, Anchorage, USA, April 2001, pp. 432-439.
  6. P. Lassila, J. Virtamo, Modeling the Dynamics of the RED Algorithm, in Proceedings of the 1st COST 263 International Workshop: Quality of Future Internet Services, QofIS 2000, Berlin, Germany, September 2000, pp. 28-42.
  7. P. Kuusela, P. Lassila, J. Virtamo, P. Key, Modeling RED with Idealized TCP Sources, in Proceedings of the 9th IFIP Working Conference on Performance Modeling and Evaluation of ATM & IP Networks, IFIP ATM & IP 2001, Budapest, Hungary, June 2001, pp. 155-166. © 2001 by authors.
  8. P. Kuusela, P. Lassila, J. Virtamo, Stability of TCP-RED Congestion Control, in Proceedings of the 17th International Teletraffic Congress, ITC 17, Bahia de Salvador, Brazil, September 2001, pp. 655-666.

Keywords: MC methods, importance sampling, loss systems, TCP modeling, RED, congestion control, stability

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2001 Helsinki University of Technology

Last update 2011-05-26