Network Performance Analysis E-Book

T. Bonald

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 238

Veröffentlichungsjahr: 2013

Beschreibung

The book presents some key mathematical tools for the performance analysis of communication networks and computer systems. Communication networks and computer systems have become extremely complex. The statistical resource sharing induced by the random behavior of users and the underlying protocols and algorithms may affect Quality of Service. This book introduces the main results of queuing theory that are useful for analyzing the performance of these systems. These mathematical tools are key to the development of robust dimensioning rules and engineering methods. A number of examples illustrate their practical interest.

Leseprobe

Table of Contents

Preface

Chapter 1. Introduction

1.1. Motivation

1.2. Networks

1.3. Traffic

1.4. Queues

1.5. Structure of the book

1.6. Bibliography

Chapter 2. Exponential Distribution

2.1. Definition

2.2. Discrete analog

2.3. An amnesic distribution

2.4. Minimum of exponential variables

2.5. Sum of exponential variables

2.6. Random sum of exponential variables

2.7. A limiting distribution

2.8. A “very” random variable

2.9. Exercises

2.10. Solution to the exercises

Chapter 3. Poisson Processes

3.1. Definition

3.2. Discrete analog

3.3. An amnesic process

3.4. Distribution of the points of a Poisson process

3.5. Superposition of Poisson processes

3.6. Subdivision of a Poisson process

3.7. A limiting process

3.8. A “very” random process

3.9. Exercises

3.10. Solution to the exercises

Chapter 4. Markov Chains

4.1. Definition

4.2. Transition probabilities

4.3. Periodicity

4.4. Balance equations

4.5. Stationary measure

4.6. Stability and ergodicity

4.7. Finite state space

4.8. Recurrence and transience

4.9. Frequency of transition

4.10. Formula of conditional transitions

4.11. Chain in reverse time

4.12. Reversibility

4.13. Kolmogorov’s criterion

4.14. Truncation of a Markov chain

4.15. Random walk

4.16. Exercises

4.17. Solution to the exercises

Chapter 5. Markov Processes

5.1. Definition

5.2. Transition rates

5.3. Discrete analog

5.4. Balance equations

5.5. Stationary measure

5.6. Stability and ergodicity

5.7. Recurrence and transience

5.8. Frequency of transition

5.9. Virtual transitions

5.10. Embedded chain

5.11. Formula of conditional transitions

5.12. Process in reverse time

5.13. Reversibility

5.14. Kolmogorov’s criterion

5.15. Truncation of a reversible process

5.16. Product of independent Markov processes

5.17. Birth–death processes

5.18. Exercises

5.19. Solution to the exercises

Chapter 6. Queues

6.1. Kendall’s notation

6.2. Traffic and load

6.3. Service discipline

6.4. Basic queues

6.5. A general queue

6.6. Little’s formula

6.7. PASTA property

6.8. Insensitivity

6.9. Pollaczek–Khinchin’s formula

6.10. The observer paradox

6.11. Exercises

6.12. Solution to the exercises

Chapter 7. Queuing Networks

7.1. Jackson networks

7.2. Traffic equations

7.3. Stationary distribution

7.4. MUSTA property

7.5. Closed networks

7.6. Whittle networks

7.7. Kelly networks

7.8. Exercises

7.9. Solution to the exercises

Chapter 8. Circuit Traffic

8.1. Erlang’s model

8.2. Erlang’s formula

8.3. Engset’s formula

8.4. Erlang’s waiting formula

8.5. The multiclass Erlang model

8.6. Kaufman–Roberts formula

8.7. Network models

8.8. Decoupling approximation

8.9. Exercises

8.10. Solutions to the exercises

Chapter 9. Real-time Traffic

9.1. Flows and packets

9.2. Packet-level model

9.3. Flow-level model

9.4. Congestion rate

9.5. Mean throughput

9.6. Loss rate

9.7. Multirate model

9.8. Recursive formula

9.9. Network models

9.10. Gaussian approximation

9.11. Exercises

9.12. Solution to the exercises

Chapter 10. Elastic Traffic

10.1. Bandwidth sharing

10.2. Congestion rate

10.3. Mean throughput

10.4. Loss rate

10.5. Multirate model

10.6. Recursive formula

10.7. Network model

10.8. Exercises

10.9. Solution to the exercises

Chapter 11. Network Performance

11.1. IP access networks

11.2. 2G mobile networks

11.3. 3G mobile networks

11.4. 3G+ mobile networks

11.5. WiFi access networks

11.6. Data centers

11.7. Cloud computing

11.8. Exercises

11.9. Solution to the exercises

Index

First published 2011 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd 27-37 St George’s Road London SW19 4EU UK

www.iste.co.uk

John Wiley & Sons, Inc. 111 River Street Hoboken, NJ 07030 USA

www.wiley.com

© ISTE Ltd 2011

The rights of Thomas Bonald and Mathieu Feuillet to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Bonald, Thomas.

Network performance analysis / Thomas Bonald, Mathieu Feuillet. p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-312-8

1. Computer networks--Evaluation. 2. Network performance (Telecommunication) 3. Queuing theory.

I. Feuillet, Mathieu. II. Title.

TK5105.5.B656 2011

621.382--dc23

2011026541

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-312-8

Preface

When speaking of queues, the first idea that comes to mind is that of everyday life: queues in supermarkets, airports, banks, etc. It is more difficult to imagine the queues used in computer systems and communication networks. However, these queues are crucial for smooth system operation and good performance. They are also more various and elaborate than those of everyday life just like bits and datagrams are more flexible than human beings.

Traffic being random, the analysis of queues relies on the theory of probability and more specifically on the Markov theory. This theory has a very simple principle, but a wide range of applications, and has become, during the last century, a fundamental tool for computer science and networking, but also for other scientific domains such as statistics, physics, biology, and economics. In the first four chapters of this book, we present the main results of the Markov theory, using only basic notions of probability.

The chapters dedicated to traffic and communication networks have benefited from our work experience in the laboratories of France Telecom, where we have experienced the importance of traffic modeling and performance evaluation in all the domains of network engineering: design, planning, architecture, measurement, control, etc. Analyzing each part of those huge systems that are communication networks allows us to better understand their global behavior and, in fine, to improve their performance.

Thomas BONALD

Mathieu FEUILLET

July 2011

Paris,

Rocquencourt

Chapter 1

Introduction

1.1. Motivation

Network performance analysis, and the underlying queueing theory, was born at the beginning of the 20th Century when two Scandinavian engineers, Erlang1 and Engset2, independently found very close formulas for calculating the reject probability of a telephone call. Their results have since proved instrumental in dimensioning telephone networks, to find the optimal capacity given some expected demand and target call reject rates.

Nowadays, the engineering of communication networks and computer systems, which consists of both dimensioning and designing resource-sharing algorithms and traffic control schemes, relies on mathematical tools derived from the queueing theory. The objective of this book is to describe some of these tools and to show how they are used in solving the practical engineering and performance issues.

1.2. Networks