Congestion pricing as scalable, efficient and stable congestion control for future IP networks [Elektronische Ressource] / Sebastian Zimmermann
171 Pages
English

Congestion pricing as scalable, efficient and stable congestion control for future IP networks [Elektronische Ressource] / Sebastian Zimmermann

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Congestion Pricing as Scalable, Ef cient and Stable Control for Future IP NetworksDissertationSebastian Zimmermann2005This dissertation has been published as a book by VDE-Verlag (http://www.vde-verlag.de).AcknowledgmentsThe results presented in this dissertation were obtained during my work at the Department ofCommunication Networks of the University of Technology at Hamburg-Harburg from 1999 to2003. I would like to express sincere thanks and gratitude to my supervisor ("Doktorvater") andhead of the department, Prof. Dr. Ulrich Killat, for his support and productive discussions aswell as disputes. I also wish to thank Prof. Dr.-Ing. Ralf Lehnert, who was co-evaluator of thisdissertation, and Prof. Dr. Hermann Rohling, who chaired the examination committee.I am indebted to my former colleagues at the Department of Communication Networks, whowere always extremely helpful and made the stay at the department a very pleasant experience.Special thanks go to Dr.-Ing. Kai Below for his support.Various simulations and experiments presented in this dissertation were conducted by stu-dents as part of their project work. They also took part in the enhancement of the networksimulators. I owe them many thanks for their assistance. In particular, I want to mention TiloHamann, who signi cantly contributed to the research presented in Chapter 5 as part of hisMaster’s thesis.Parts of this work were nancially supported by the Deutsche Forschungsgemeinschaft(DFG).

Subjects

Informations

Published by
Published 01 January 2005
Reads 21
Language English
Document size 7 MB

Congestion Pricing as Scalable, Ef cient and Stable Control for Future IP Networks
Dissertation
Sebastian Zimmermann
2005This dissertation has been published as a book by VDE-Verlag (http://www.vde-verlag.de).Acknowledgments
The results presented in this dissertation were obtained during my work at the Department of
Communication Networks of the University of Technology at Hamburg-Harburg from 1999 to
2003. I would like to express sincere thanks and gratitude to my supervisor ("Doktorvater") and
head of the department, Prof. Dr. Ulrich Killat, for his support and productive discussions as
well as disputes. I also wish to thank Prof. Dr.-Ing. Ralf Lehnert, who was co-evaluator of this
dissertation, and Prof. Dr. Hermann Rohling, who chaired the examination committee.
I am indebted to my former colleagues at the Department of Communication Networks, who
were always extremely helpful and made the stay at the department a very pleasant experience.
Special thanks go to Dr.-Ing. Kai Below for his support.
Various simulations and experiments presented in this dissertation were conducted by stu-
dents as part of their project work. They also took part in the enhancement of the network
simulators. I owe them many thanks for their assistance. In particular, I want to mention Tilo
Hamann, who signi cantly contributed to the research presented in Chapter 5 as part of his
Master’s thesis.
Parts of this work were nancially supported by the Deutsche Forschungsgemeinschaft
(DFG).
Last but not least, I would like to thank my family and my ancØ for their encouragement
and support.
iiiAbstract
This dissertation focuses on the design of distributed congestion control algorithms for TCP/IP
networks that are more powerful by utilizing the theory of Congestion Pricing as a mathemat-
ical framework. Currently implemented congestion control algorithms have several drawbacks
that lead to sub-optimal usage and unfair distribution of network resources. Further, new appli-
cations have signi cantly changed the demand for network performance and quality of service.
As will be shown, the use of wireless links and large link capacities can cause instability of the
algorithms in use today.
Congestion Pricing is a strategy based on economics and optimization theory: A congestion
measure (shadow price) is computed at each network node and fed back to the source. The
sources adapt their rates according to utility functions and aggregate pricing information. It can
be shown that this will lead to a social optimum for the entire network while maintaining both
low queue sizes and high utilization. By choosing the user’s utility function, different classes of
service can be implemented without additional network support. Thus, the increasing demands
on the network can be met changing the Internet’s fundamental principle of keeping
the network nodes simple, and thus retaining its exibility and scalability. At the same time,
ef ciency will also be signi cantly improved.
In this dissertation, Congestion Pricing will be applied to the Transmission Control Proto-
col (TCP). First, an implementation is developed that makes use of the full pricing information.
Then, in an effort to make the new TCP source compatible with the existing network and TCP
receivers, the pricing information is reduced to a single bit. This reduction of information intro-
duces new challenges that are addressed by a Single Bit Resource Marking (SBRM) proposal
developed by the author of this dissertation. Its performance is evaluated by comparison with
other proposals and current congestion control algorithms.
While the ef ciency and scalability problems are solved by the application of Congestion
Pricing, a control theoretic model is further developed to examine the linear stability of the
proposed algorithms. Current congestion control algorithms can become unstable in realistic
scenarios, which signi cantly harms network performance. SBRM, in contrast, is stable over a
wider range of network scenarios, and the impact on performance parameters is lower in cases
of instability.
Lastly, multimedia applications are also addressed in this dissertation. They usually cannot
change their transmission rate. Therefore, a distributed Call Admission Control using Conges-
tion Pricing is developed. Even without special network support, it will be effective and highly
ef cient. Since the Call Admission Control works in a distributed manner to make it scalable,
it can be implemented in network border gateways or in the sources themselves.
vContents
1 Introduction 1
2 Congestion Control Background 5
2.1 Congestion Control in Packet Switched Networks . . . . . . . . . . . . . . . . . 5
2.2 Elastic Traf c vs. Inelastic Traf c . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Congestion Control Mechanisms in Conventional TCP Variants . . . . . . . . . 8
2.3.1 Properties of TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.2 TCP’s Fundamental Algorithms . . . . . . . . . . . . . . . . . . . . . . 9
2.3.3 Important Variants of TCP . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Drawbacks of TCP and Proposed Extensions . . . . . . . . . . . . . . . . . . . . 14
2.4.1 Major Drawbacks of Conventional TCP Implementations . . . . . . . . 14
2.4.2 Explicit Congestion Noti cation . . . . . . . . . . . . . . . . . . . . . . 17
2.4.3 Active Queue Management . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.4 Time-stamp Option . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Congestion Pricing Framework 23
3.1 Introduction and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Mathematical Model and Important Properties . . . . . . . . . . . . . . . . . . . 25
3.2.1 Basic Without Delays . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Relaxed Model (Penalty Approach) . . . . . . . . . . . . . . . . . . . . 27
3.2.3 User’s Rate Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.4 Stability and Convergence with Delays . . . . . . . . . . . . . . . . . . . 28
3.2.5 Duality Model and Gradient Projection Method . . . . . . . . . . . . . . 28
3.2.6 Logarithmic Utility Functions and Proportional Fairness . . . . . . . . . 29
3.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 Implementation of Congestion Pricing Based TCP 33
4.1 Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Congestion Pricing-TCP with Explicit Price Feedback (CP-TCP/EPF) . . . . . 34
4.2.1 Source Algorithm (Direct Window Update Algorithm) . . . . . . . . . . 34
4.2.2 Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.3 Path Price Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3.1 Simulation Setup (Double Bottleneck Link Network) . . . . . . . . . . . 36
4.3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
viiContents
4.3.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Scalability and Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4.1 Simulation Setup (Parking Lot Network) . . . . . . . . . . . . . . . . . 44
4.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.3 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 Single Bit Marking Strategies 51
5.1 Virtual Queue Mechanism (VQM) . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.1.1 VQM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.1.2 Performance of VQM (Double Bottleneck Link Network) . . . . . . . . 54
5.2 Random Exponential Marking (REM) . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.1 REM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.2 Performance of REM (Double Bottleneck Link Network) . . . . . . . . 59
5.2.3 Evaluation of REM’s Path Price Estimation, Scalability and Fairness
(Parking Lot Network) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Summary of VQM and REM Simulation Results . . . . . . . . . . . . . . . . . . 68
5.4 Single Bit Resource Marking (SBRM) . . . . . . . . . . . . . . . . . . . . . . . 68
5.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.4.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4.3 Performance Evaluation (Simulations) . . . . . . . . . . . . . . . . . . . 70
5.4.4 Comparison of SBRM With Other Approaches in a Parking Lot Topology 73
5.4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.5 Steady-state Analysis of SBRM . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.6 Compatibility with Conventional TCP . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6.1 TCP-Friendliness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6.2 Compatibility with Existing TCP Sinks . . . . . . . . . . . . . . . . . . 79
5.6.3 TCP/RM (Modi ed SBRM) . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.6.4 Simulations and HTTP Model . . . . . . . . . . . . . . . . . . 80
5.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6 Control Theoretic Analysis 89
6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.2 Limitations of Control Theoretic Models . . . . . . . . . . . . . . . . . . . . . . 90
6.3 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.4 Non-linear Model of SBRM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.4.1 Window Evolvement under SBRM . . . . . . . . . . . . . . . . . . . . . 93
6.4.2 SBRM Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.5 Linear Model of SBRM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.5.1 Linearization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.5.2 Linear Model in the Laplace Domain . . . . . . . . . . . . . . . . . . . . 98
6.5.3 Single Bottleneck Link Model with Heterogeneous Sources . . . . . . . 98
6.5.4 Single Link with Homogeneous . . . . . . . 100
6.6 Evaluation of the Control Theoretic Model . . . . . . . . . . . . . . . . . . . . . 101
6.6.1 Evaluation of the Stability . . . . . . . . . . . . . . . . . . . . . . . . . . 101
viiiContents
6.6.2 Recommendations for SBRM . . . . . . . . . . . . . . . . . . . . . . . . 106
6.6.3 Validation of the Linearized Model . . . . . . . . . . . . . . . . . . . . . 110
6.7 Impact of Instability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.7.1 Impact of Instability on Validity of Fluid- ow Model Predictions . . . . 116
6.7.2 of on Performance . . . . . . . . . . . . . . . . . . . . 120
6.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7 Congestion Control for Inelastic Traf c 131
7.1 Relevance of Congestion Control for Inelastic Traf c . . . . . . . . . . . . . . . 131
7.2 Call Admission Control for Inelastic Traf c . . . . . . . . . . . . . . . . . . . . 132
7.2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.2.3 Simulations and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.3 Rate-adaptive MPEG Streaming . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.3.3 Simulations and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8 Conclusions 147
Bibliography 151
ix