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

Flow-Level Performance Analysis of Data Networks Using Processor Sharing Models

Juha Leino

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Electronics, Communications and Automation for public examination and debate in Auditorium S1 at Helsinki University of Technology (Espoo, Finland) on the 9th of May, 2008, at 12 noon.

Overview in PDF format (ISBN 978-951-22-9301-8)   [576 KB]
Dissertation is also available in print (ISBN 978-951-22-9300-1)

Abstract

Most telecommunication systems are dynamic in nature. The state of the network changes constantly as new transmissions appear and depart. In order to capture the behavior of such systems and to realistically evaluate their performance, it is essential to use dynamic models in the analysis. In this thesis, we model and analyze networks carrying elastic data traffic at flow level using stochastic queueing systems. We develop performance analysis methodology, as well as model and analyze example systems.

The exact analysis of stochastic models is difficult and usually becomes computationally intractable when the size of the network increases, and hence efficient approximative methods are needed. In this thesis, we use two performance approximation methods. Value extrapolation is a novel approximative method developed during this work and based on the theory of Markov decision processes. It can be used to approximate the performance measures of Markov processes. When applied to queueing systems, value extrapolation makes possible heavy state space truncation while providing accurate results without significant computational penalties. Balanced fairness is a capacity allocation scheme recently introduced by Bonald and Proutière that simplifies performance analysis and requires less restrictive assumptions about the traffic than other capacity allocation schemes. We introduce an approximation method based on balanced fairness and the Monte Carlo method for evaluating large sums that can be used to estimate the performance of systems of moderate size with low or medium loads.

The performance analysis methods are applied in two settings: load balancing in fixed networks and the analysis of wireless networks. The aim of load balancing is to divide the traffic load efficiently between the network resources in order to improve the performance. On the basis of the insensitivity results of Bonald and Proutière, we study both packet- and flow-level balancing in fixed data networks. We also study load balancing between multiple parallel discriminatory processor sharing queues and compare different balancing policies.

In the final part of the thesis, we analyze the performance of wireless networks carrying elastic data traffic. Wireless networks are gaining more and more popularity, as their advantages, such as easier deployment and mobility, outweigh their downsides. First, we discuss a simple cellular network with link adaptation consisting of two base stations and customers located on a line between them. We model the system and analyze the performance using different capacity allocation policies. Wireless multihop networks are analyzed using two different MAC schemes. On the basis of earlier work by Penttinen et al., we analyze the performance of networks using the STDMA MAC protocol. We also study multihop networks with random access, assuming that the transmission probabilities can be adapted upon flow arrivals and departures. We compare the throughput behavior of flow-optimized random access against the throughput obtained by optimal scheduling assuming balanced fairness capacity allocation.

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

  1. Juha Leino and Jorma Virtamo. 2006. An approximative method for calculating performance measures of Markov processes. In: Proceedings of the First International Conference on Performance Evaluation Methodologies and Tools (Valuetools 2006). Pisa, Italy, 11-13 October 2006.
  2. Juha Leino, Aleksi Penttinen, and Jorma Virtamo. 2007. Approximating flow throughput in complex data networks. In: Proceedings of the 20th International Teletraffic Congress (ITC20). Ottawa, Canada, 17-21 June 2007. Lecture Notes in Computer Science, volume 4516, pages 422-433.
  3. Juha Leino. 2007. Approximating optimal load balancing policy in discriminatory processor sharing systems. In: Proceedings of the Second International Workshop on Tools for solving Structured Markov Chains (SMCtools 2007). Nantes, France, 26 October 2007.
  4. Juha Leino and Jorma Virtamo. 2007. Determining the moments of queue-length distribution of discriminatory processor-sharing systems with phase-type service requirements. In: Proceedings of the 3rd EuroNGI Conference on Next Generation Internet Networks (NGI 2007). Trondheim, Norway, 21-23 May 2007, pages 205-208.
  5. Juha Leino and Jorma Virtamo. 2006. Insensitive load balancing in data networks. Computer Networks, volume 50, number 8, pages 1059-1068.
  6. Juha Leino and Jorma Virtamo. 2005. Insensitive traffic splitting in data networks. In: Proceedings of the 19th International Teletraffic Congress (ITC19). Beijing, China, 29 August - 2 September 2005, pages 1355-1364. © 2005 by authors.
  7. Juha Leino, Aleksi Penttinen, and Jorma Virtamo. 2006. Flow level performance analysis of wireless data networks: A case study. In: Proceedings of the 2006 IEEE International Conference on Communications (ICC 2006). Istanbul, Turkey, 11-15 June 2006, pages 961-966.
  8. Juha Leino, Aleksi Penttinen, and Jorma Virtamo. 2007. Flow-optimized random access for wireless multihop networks. In: Proceedings of the 10th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM 2007). Chania, Crete Island, Greece, 22-26 October 2007, pages 387-394.

Errata of publication 4

Keywords: data networks, elastic traffic, flow-level performance analysis, Markov decision processes, balanced fairness, processor sharing, load balancing

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

© 2008 Helsinki University of Technology

Last update 2011-05-26