- Cheng-Shang Chang
- ISBN 1-85233-226-3
- 392 pages
Providing performance guarantees is one of the most important issues for future telecommunication networks. It is our attempt to introduce theoretical developments in the last decade for performance guarantees in telecommunication networks. The book consists of two parts. In the first part, we deal with deterministic (hard) guarantees, where we show how deterministic bounds for delay and queue length can be achieved. The second part addresses stochastic (soft) guarantees, focusing mainly on tail distributions of queue lengths and packet loss probabilities.
Like the classical queueing theory, both the deterministic theory and the stochastic theory addressed in this book introduce new traffic characterizations and then develop the associated calculus from such traffic characterizations. One of the most famous achievements in the classical queueing theory is the theory for the product form networks. In a product form network, arrivals are characterized by Poisson processes. The calculus associated with Poisson processes includes (i) multiplexing independent Poisson processes yields a Poisson process, (ii) random splitting of a Poisson process yields independent Poisson processes, and (iii) the departure process from an M/M/1 queue is also a Poisson process. From the calculus, all the queues in a product form network have Poisson inputs and behave like independent M/M/1 queues. The development of this book follows the same spirit. For the deterministic theory, we introduce the new traffic characterization by Rene Cruz and the associated calculus for multiplexing, work conserving links, output characterization, and routing. The beauty of the deterministic theory is that it can be generalized and explained systematically by a filtering theory under the min-plus algebra. For the stochastic theory, we introduce the effective bandwidth function for traffic characterization. Such a traffic characterization is based on the moment generating function of an arrival process and is related to the large deviation principle. Its associated calculus is then built upon the mathematical theory of the large deviation principle. As the moment generating function of a random variable contains more information than its mean, traffic characterizations based on effective bandwidth functions are more accurate than those based on simple Poisson processes when dealing with traffic in modern communication networks.
This book is the result of courses developed in high speed digital networks at National Tsing Hua University. The material in this book can serve as a basis for a semester-long graduate level course that covers all the sections in Chapters 1,2,3,7,8, Sections 5.1-5.4 and Sections 9.1-9.3. Readers that have taken undergraduate courses in linear algebra and signals and systems may find the concepts in the first part easy to adapt. For the second part of this book, readers are required to have knowledge of elementary probability and stochastic processes.
As ``industrial standards'' come and go, we do not cover any industrial standards in this book purposely. Our intent is to teach students the basic ideas and principles of how performance guarantees can be achieved in telecommunication networks. We hope the students through self-discovery can associate the material in this book with the current developments of industrial standards. Readers who are interested in industrial standards may consult the book by Tanenbaum and references there. Some proposals for future industrial standards can also be found at the web site by the Internet Engineering Task Force (IETF).
Many colleagues and students have contributed to this work on various portions of this book. I gratefully thank Jin-Fu Chang, Chi-Chao Chao, Xiuli Chao, Kwang-Cheng Chen, Rene Cruz, Philip Heidelberger, George Kesidis, Jean-Yves Le Boudec, Yih-Haur Lin, Randolph Nelson, Michael Pinedo, Perwez Shahabuddin, Patrick Thiran, Joy Thomas, Jean Walrand, David Yao, and Tim Zajic for the privilege of working with them. Many ideas in this book were originated from discussions with them and several chapters of the book were rewritten from papers jointly coauthored with them. I give special thanks to Wen-Jyh Chen, Ling-I Ho, Hsiang-Yi Huang, and Jyh-Jye Yen for generating many of the plots, and to Francois Baccelli, Stephan Lapic and many graduate students for carefully reviewing an earlier draft. It was a pleasure working with Oliver Jackson, Springer-Verlag's editor. I am also grateful to the National Science Council, Taiwan, R.O.C., for support of much of this work under contracts NSC 87-2213-E-007-084, NSC 88-2213-E-007-046 and NSC 89-2213-E-007-002. Most importantly, I would like to express my sincere appreciation to my wife, Katherine, and to my daughter, Marisa, for their constant support during the process of writing this book.
1.1 (\sigma , \rho)-traffic characterization
1.2 Multiplexing
1.3 Work conserving links
1.4 Output burstiness
1.5 Routing
1.6 Multi-class networks with feedforward routing
1.7 Single-class networks with nonfeedforward routing
1.8 General traffic characterization
1.9 Notes
- 2.1 Filtering theory under the min-plus algebra
- 2.1.1 Min-plus algebra
- 2.1.2 Subadditive closure
- 2.2 Traffic regulation
- 2.2.1 Maximal f-regulator
- 2.2.2 Realizations of leaky buckets under the (min,+)-algebra
- 2.2.3 Traffic regulation for periodic constraint functions
- 2.3 Service guarantees
- 2.3.1 f-servers
- 2.3.2 Work conserving links with priorities
- 2.3.3 Work conserving links with vacations
- 2.3.4 GPS links
- 2.3.5 SCED links
- 2.3.6 Jitter control
- 2.3.7 Window flow control
- 2.3.8 Service curve allocation
- 2.4 Extensions to networks with variable length packets
- 2.4.1 L-packetizer
- 2.4.2 Work conserving links with nonpre-emptive priorities
- 2.4.3 PGPS links
- 2.4.4 SCED with nonpre-emptive priority
- 2.4.5 Window flow control with variable length packets
- 2.5 Notes
3.1 Projections under the min-plus algebra
3.2 Ordered orthogonal bases under the min-plus algebra
3.3 C-transform under the min-plus algebra
3.4 Notes
4.1 Min-plus matrix algebra
4.2 Traffic regulation for multiple inputs
4.3 Service guarantees for multiple inputs
4.4 Notes
5.1 Time varying filtering theory under the min-plus algebra
5.2 Maximal dynamic F-regulator
5.3 Maximal dynamic F-clipper
5.4 Constrained traffic regulation
5.5 Dynamic F-servers
5.6 The dynamic SCED scheduling algorithm
5.7 General system theory
5.8 Notes
- 6.1 Preliminaries on the max-plus algebra
- 6.2 Traffic regulation for marked point processes
- 6.2.1 Minimal g-regulator
- 6.2.2 Minimal g-regulators in parallel
- 6.2.3 Inversion formula and superposition of g-regular traffic
- 6.2.4 Segmentation and reassembly
- 6.3 Service guarantees for marked point processes
- 6.3.1 g-server
- 6.3.2 g-servers in tandem
- 6.3.3 g-servers in parallel
- 6.3.4 g-server with feedback
- 6.4 Scheduling
- 6.4.1 Nonpre-emptive servers with multiple priorities
- 6.4.2 The SCED scheduling algorithm
- 6.5 Notes
7.1 Convexity and related inequalities
7.2 (\sigma (\theta ), \rho (\theta ))-traffic characterization
7.3 Multiplexing
7.4 Work conserving links
7.5 Routing
7.6 Acyclic networks and intree networks
7.7 Notes
8.1 Legendre transform
8.2 Cram\'er's theorem
8.3 The G\"artner-Ellis theorem
8.4 Sanov's theorem
8.5 Mogulskii's theorem
8.6 The contraction principle
- 9.1 Effective bandwidth at a work conserving link
- 9.2 Multiplexing independent arrivals
- 9.3 Routing
- 9.4 Intree networks
- 9.4.1 Sample path large deviations
- 9.4.2 Closure properties of sample path large deviations
- 9.4.3 The proof for the lower bound
- 9.5 Work conserving links with priorities
- 9.6 Conjugate processes
- 9.6.1 Finite-state Markov arrival processes
- 9.6.2 Autoregressive processes
- 9.6.3 Properties of conjugate processes
- 9.7 Fast simulations
- 9.7.1 Change of measures and importance sampling
- 9.7.2 Simulation methodology for steady state probabilities
- 9.8 Martingale bounds
- 9.9 Traffic descriptors
- 9.9.1 A four-parameter traffic descriptor
- 9.9.2 A two-state Markov fluid model
- 9.9.3 Closed-form approximations
- 9.10 Fuzzy reasoning for the theory of effective bandwidth
- 9.10.1 Work conserving links
- 9.10.2 Multiplexing independent arrivals
- 9.10.3 Routing
- 9.10.4 Output characterization from a work conserving link
- 9.11 Fractional Gaussian noise
- 9.12 M/G/\infty inputs
- 9.13 Notes