Stochastic Network Calculus

by Jiang, Yuming; Liu, Yong

• ISBN13: 9781848001268
• ISBN10: 1848001266
• Format: Hardcover
• Copyright: 2008-09-23
• Publisher: Springer-Verlag New York Inc

Summary

Network calculus, a theory dealing with queuing systems found in computer networks, focuses on performance guarantees. The development of an information theory for stochastic service-guarantee analysis has been identified as a grand challenge for future networking research. Towards that end, stochastic network calculus, the probabilistic version or generalization of the (deterministic) Network Calculus, has been recognized by researchers as a crucial step.Stochastic Network Calculus presents a comprehensive treatment for the state-of-the-art in stochastic service-guarantee analysis research and provides basic introductory material on the subject, as well as discusses the most recent research in the area. This helpful volume summarizes results for stochastic network calculus, which can be employed when designing computer networks to provide stochastic service guarantees.Features and Topics:'¢ Provides a solid introductory chapter, providing useful background knowledge'¢ Reviews fundamental concepts and results of deterministic network calculus'¢ Includes end-of-chapter problems, as well as summaries and bibliographic comments'¢ Defines traffic models and server models for stochastic network calculus'¢ Summarizes the basic properties of stochastic network calculus under different combinations of traffic and server models'¢ Highlights independent case analysis'¢ Discusses stochastic service guarantees under different scheduling disciplines'¢ Presents applications to admission control and traffic conformance study using the analysis results'¢ Offers an overall summary and some open research challenges for further study of the topicKey Topics: '¢ Queuing systems'¢ Performance analysis and guarantees '¢ Independent case analysis '¢ Traffic and server models '¢ Analysis of scheduling disciplines '¢ Generalized processor sharing '¢ Open research challengesResearchers and graduates in the area of performance evaluation of computer communication networks will benefit substantially from this comprehensive and easy-to-follow volume. Professionals will also find it a worthwhile reference text.Professor Yuming Jiang at the Norwegian University of Science and Technology (NTNU) has lectured using the material presented in this text since 2006.Dr Yong Liu works at the Optical Network Laboratory, National University of Singapore, where he researches QoS for optical communication networks and Metro Ethernet networks.

Author Biography

Yong Liu works at the Optical Network Laboratory, National University of Singapore. Yuming Jiang is Professor at the Norwegian University of Science and Technology (NTNU).

Table of Contents

Preface	p. vii
List of Figures	p. xvii
List of Tables	p. xix
Introduction	p. 1
Quality of Service Guarantees	p. 2
Basic Properties for Network Analysis	p. 3
Notation and Mathematical Background	p. 6
Notation	p. 6
Min-Plus Algebra Basics	p. 8
Maximum Horizontal Distance and Maximum Vertical Distance	p. 10
Random Variable and Stochastic Process Basics	p. 10
Random Variables	p. 10
Stochastic Processes	p. 13
Stochastic Ordering	p. 13
Min-Plus Linearity of Queuing Systems	p. 15
Summary and Bibliographic Comments	p. 16
Problems	p. 17
Deterministic Network Calculus	p. 19
Traffic Models	p. 19
([sigma],[rho]) Traffic Characterization	p. 19
Arrival Curve	p. 20
Envelope Process	p. 22
Server Models	p. 23
Service Curve	p. 23
Network Elements Offering Service Curves	p. 24
Strict Service Curve	p. 26
Service Envelope Process	p. 26
Basic Results	p. 27
Service Guarantees	p. 28
Output Characterization	p. 30
Concatenation Property	p. 31
Leftover Service	p. 33
Superposition	p. 34
Example: Analysis of a Network of Arbitrary Topology	p. 34
Summary and Bibliographic Comments	p. 36
Problems	p. 37
Traffic Models for Stochastic Network Calculus	p. 41
([sigma]([theta], [rho]([theta])) Traffic Characterization	p. 41
t.a.c. Stochastic Arrival Curve	p. 42
Difficulties and Additional Constraints	p. 45
v.b.c. Stochastic Arrival Curve	p. 48
m.b.c. Stochastic Arrival Curve	p. 53
[theta]-m.b.c. Stochastic Arrival Curve	p. 56
Stochastic Envelope Process	p. 57
Summary and Bibliographic Comments	p. 60
Problems	p. 63
Server Models for Stochastic Network Calculus	p. 65
Weak Stochastic Service Curve	p. 65
Stochastic Service Curve	p. 66
[theta]-Stochastic Service Curve	p. 68
Stochastic Strict Service Curve	p. 69
Stochastic Strict Server due to Impairment	p. 71
Service Envelope Process	p. 74
Latency Rate Characterization	p. 76
Relationship with ([sigma]([theta]), [rho]([theta])) Traffic Characterization	p. 77
Summary and Bibliographic Comments	p. 78
Problems	p. 79
Basic Properties of Stochastic Network Calculus	p. 83
Service Guarantees	p. 83
Backlog Bound	p. 83
Delay Bound	p. 85
Output Characterization	p. 88
Output t.a.c Stochastic Arrival Curve	p. 88
Output v.b.c. Stochastic Arrival Curve	p. 90
Output m.b.c Stochastic Arrival Curve	p. 93
Output [theta]-m.b.c. Stochastic Arrival Curve	p. 96
Concatenation Property	p. 97
Leftover Service Characterization	p. 101
Leftover Weak Stochastic Service Curve	p. 101
Leftover Stochastic Service Curve	p. 102
Leftover [theta]-Stochastic Service Curve	p. 105
Superposition Property	p. 107
Scaling of End-to-End Delay Bound	p. 109
Delay Bound From the Concatenation Property	p. 110
Delay Bound from Node-by-Node Analysis	p. 111
Calculus on Traffic and Service Envelope Processes	p. 112
Summary and Bibliographic Comments	p. 114
Problems	p. 116
Independent Case Analysis	p. 119
Introduction	p. 119
Analysis Based on Stochastic Strict Server	p. 121
Backlog and Delay Bounds	p. 122
Output Characterization	p. 124
Concatenation Property	p. 128
Leftover Service Characterization	p. 130
Superposition Property	p. 133
Scaling of End-to-End Delay Bound	p. 134
Calculus with Moment Generating Functions	p. 136
Moment Generating Function Basics	p. 136
Basic Properties and Performance Bounds	p. 138
Summary and Bibliographic Comments	p. 141
Problems	p. 142
Analysis on Scheduling Disciplines	p. 145
Introduction to gSBB	p. 145
Properties of gSBB	p. 148
Analysis on Different Scheduling Disciplines	p. 150
General Results	p. 151
First In First Out (FIFO)	p. 152
Strict Priority (SP)	p. 153
Generalized Processor Sharing (GPS)	p. 154
Application to Measurement-Based Admission Control	p. 155
Introduction to MBAC	p. 156
Introduction to Flow-Aware Networking	p. 157
Dynamic Priority Scheduling-Based MBAC	p. 158
Analysis	p. 160
Summary and Bibliographic Comments	p. 163
Problems	p. 164
Traffic Conformance Study	p. 165
Network Model	p. 166
Conformance Deterioration and Stochastic Burstiness Increase	p. 167
Property of Token Bucket Shaper	p. 168
Conformance Study of Per-Flow Scheduling Network	p. 169
Single-Node Case	p. 169
Multi-node Case	p. 170
Conformance Study of Aggregate Scheduling Network	p. 171
Per-Flow in Single-Node Case	p. 171
Per-Flow in Multi-node Case	p. 176
Per-Aggregate Case	p. 178
Simulation Results	p. 179
Per-Flow Scheduling Network in Single-Node Case	p. 179
Aggregate Scheduling Network in Single-Node Case	p. 182
Aggregate Scheduling Network in Multi-node Case	p. 183
Summary and Bibliographic Comments	p. 185
Problems	p. 187
LRD Isolation in Generalized Processor Sharing	p. 189
Introduction	p. 190
GPS Fundamentals	p. 190
LRD Traffic Characterization	p. 191
LRD Isolation of Flows	p. 192
Analysis of LRD Traffic	p. 193
Single Arrival Process	p. 193
Aggregate Process	p. 196
Sample Path Behavior of LRD Traffic in a GPS System	p. 199
GPS Decomposition	p. 199
A General Bound	p. 200
An Alternate Bound	p. 201
Technique to Check and Ensure LRD Isolation	p. 202
Limitations of Existing Methods	p. 203
Necessary and Sufficient Condition	p. 205
Weight Adjustment and Assignment	p. 206
Sample Path Behavior of LRD Traffic in a PGPS System	p. 208
Summary and Bibliographic Comments	p. 211
Problems	p. 212
Open Research Challenges	p. 213
Applicability Condition Study of Stochastic Network Calculus	p. 214
Advanced Properties	p. 215
Network Information Theory for the Internet	p. 217
References	p. 219
Index	p. 227
Table of Contents provided by Ingram. All Rights Reserved.