Performance analysis of queuing and computer networks

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010205731	TK5105.5956 D37 2008	Open Access Book	Book	Searching... Unknown
Searching... SPACE KL Main Library	30000003506494	TK5105.5956 D37 2008	Open Access Book	Book	Searching... Unknown

Performance Analysis of Queuing and Computer Networks develops simple models and analytical methods from first principles to evaluate performance metrics of various configurations of computer systems and networks. It presents many concepts and results of probability theory and stochastic processes.

After an introduction to queues in computer networks, this self-contained book covers important random variables, such as Pareto and Poisson, that constitute models for arrival and service disciplines. It then deals with the equilibrium M/M/1/∞queue, which is the simplest queue that is amenable for analysis. Subsequent chapters explore applications of continuous time, state-dependent single Markovian queues, the M/G/1 system, and discrete time queues in computer networks. The author then proceeds to study networks of queues with exponential servers and Poisson external arrivals as well as the G/M/1 queue and Pareto interarrival times in a G/M/1 queue. The last two chapters analyze bursty, self-similar traffic, and fluid flow models and their effects on queues.

Author Notes

Dattatreya, G.R.

1 Introduction	p. 1
1.1 Background	p. 1
1.2 Queues in Computers and Computer Networks	p. 2
1.2.1 Single processor systems	p. 2
1.2.2 Synchronous multi-processor systems	p. 3
1.2.3 Distributed operating system	p. 3
1.2.4 Data communication networks	p. 3
1.2.4.1 Data transfer in communication networks	p. 3
1.2.4.2 Organization of a computer network	p. 4
1.2.5 Queues in data communication networks	p. 5
1.3 Queuing Models	p. 6
1.4 Conclusion	p. 9
2 Characterization of Data Traffic	p. 13
2.1 Introduction	p. 13
2.2 The Pareto Random Variable	p. 15
2.3 The Poisson Random Variable	p. 22
2.3.1 Derivation of the Poisson pmf	p. 23
2.3.2 Interarrival times in a Poisson sequence of arrivals	p. 25
2.3.3 Properties of Poisson streams of arrivals	p. 26
2.3.3.1 Mean of exponential random variable	p. 26
2.3.3.2 Mean of the Poisson random variable	p. 27
2.3.3.3 Variance of the exponential random variable	p. 28
2.3.3.4 Variance of Poisson random variable	p. 29
2.3.3.5 The Z transform of a Poisson random variable	p. 29
2.3.3.6 Memoryless property of the exponential random variable	p. 30
2.3.3.7 Time for the next arrival	p. 31
2.3.3.8 Nonnegative, continuous, memoryless random variables	p. 31
2.3.3.9 Succession of iid exponential interarrival times	p. 31
2.3.3.10 Merging two independent Poisson streams	p. 32
2.3.3.11 iid probabilistic routing into a fork	p. 35
2.4 Simulation	p. 37
2.4.1 Technique for simulation	p. 37
2.4.2 Generalized Bernoulli random number	p. 37
2.4.3 Geometric and modified geometric random numbers	p. 39
2.4.4 Exponential random number	p. 39
2.4.5 Pareto random number	p. 40
2.5 Elements of Parameter Estimation	p. 42
2.5.1 Parameters of Pareto random variable	p. 43
2.5.2 Properties of estimators	p. 46
2.6 Sequences of Random Variables	p. 47
2.6.1 Certain and almost certain events	p. 49
2.7 Elements of Digital Communication and Data Link Performance	p. 52
2.7.1 The Gaussian noise model	p. 52
2.7.2 Bit error rate evaluation	p. 54
2.7.3 Frame error rate evaluation	p. 56
2.7.4 Data rate optimization	p. 57
2.8 Exercises	p. 59
3 The M/M/1/[infinity] Queue	p. 63
3.1 Introduction	p. 63
3.2 Derivation of Equilibrium State Probabilities	p. 64
3.2.1 Operation in equilibrium	p. 70
3.2.2 Setting the system to start in equilibrium	p. 71
3.3 Simple Performance Figures	p. 72
3.4 Response Time and its Distribution	p. 76
3.5 More Performance Figures for M/M/1/[infinity] System	p. 77
3.6 Waiting Time Distribution	p. 80
3.7 Departures from Equilibrium M/M/1/[infinity] System	p. 81
3.8 Analysis of ON-OFF Model of Packet Departures	p. 86
3.9 Round Robin Operating System	p. 88
3.10 Examples	p. 94
3.11 Analysis of Busy Times	p. 96
3.11.1 Combinations of arrivals and departures during a busy time period	p. 98
3.11.2 Density function of busy times	p. 99
3.11.3 Laplace transform of the busy time	p. 101
3.12 Forward Data Link Performance and Optimization	p. 104
3.12.1 Reliable communication over unreliable data links	p. 104
3.12.2 Problem formulation and solution	p. 105
3.13 Exercises	p. 109
4 State Dependent Markovian Queues	p. 115
4.1 Introduction	p. 115
4.2 Stochastic Processes	p. 115
4.2.1 Markov process	p. 117
4.3 Continuous Parameter Markov Chains	p. 118
4.3.1 Time intervals between state transitions	p. 118
4.3.2 State transition diagrams	p. 118
4.3.3 Development of balance equations	p. 119
4.3.4 Graphical method to write balance equations	p. 123
4.4 Markov Chains for State Dependent Queues	p. 124
4.4.1 State dependent rates and equilibrium probabilities	p. 124
4.4.2 General performance figures	p. 127
4.4.2.1 Throughput	p. 127
4.4.2.2 Blocking probability	p. 127
4.4.2.3 Expected fraction of lost jobs	p. 127
4.4.2.4 Expected number of customers in the system	p. 128
4.4.2.5 Expected response time	p. 128
4.5 Intuitive Approach for Time Averages	p. 129
4.6 Statistical Analysis of Markov Chains' Sample Functions	p. 132
4.7 Little's Result	p. 141
4.7.1 FIFO case	p. 141
4.7.2 Non-FIFO case	p. 142
4.8 Application Systems	p. 143
4.8.1 Constant rate finite buffer M/M/1/k system	p. 143
4.8.2 Forward data link with a finite buffer	p. 146
4.8.3 M/M/[infinity] or immediate service	p. 147
4.8.4 Parallel servers	p. 148
4.8.5 Client-server model	p. 152
4.9 Medium Access in Local Area Networks	p. 160
4.9.1 Heavily loaded channel with a contention based transmission protocol	p. 160
4.9.1.1 Consequences of modeling approximations	p. 161
4.9.1.2 Analysis steps	p. 162
4.9.2 A simple contention-free LAN protocol	p. 163
4.10 Exercises	p. 170
5 The M/G/1 Queue	p. 179
5.1 Introduction	p. 179
5.2 Imbedded Processes	p. 180
5.3 Equilibrium and Long Term Operation of M/G/1/[infinity] Queue	p. 181
5.3.1 Recurrence equations for state sequence	p. 181
5.3.2 Analysis of equilibrium operation	p. 183
5.3.3 Statistical behavior of the discrete parameter sample function	p. 185
5.3.4 Statistical behavior of the continuous time stochastic process	p. 189
5.3.5 Poisson arrivals see time averages	p. 190
5.4 Derivation of the Pollaczek-Khinchin Mean Value Formula	p. 193
5.4.1 Performance figures	p. 198
5.5 Application Examples	p. 198
5.5.1 M/D/1/[infinity]: Constant service time	p. 198
5.5.2 M/U/1/[infinity]: Uniformly distributed service time	p. 198
5.5.3 Hypoexponential service time	p. 199
5.5.4 Hyperexponential service time	p. 199
5.6 Special Cases	p. 200
5.6.1 Pareto service times with infinite variance	p. 200
5.6.2 Finite buffer M/G/1 system	p. 200
5.7 Exercises	p. 202
6 Discrete Time Queues	p. 209
6.1 Introduction	p. 209
6.2 Timing and Synchronization	p. 209
6.3 State Transitions and Their Probabilities	p. 211
6.4 Discrete Parameter Markov Chains	p. 216
6.4.1 Homogeneous Markov chains	p. 218
6.4.2 Chapman-Kolmogorov equations	p. 220
6.4.3 Irreducible Markov chains	p. 220
6.5 Classification of States	p. 223
6.5.1 Aperiodic states	p. 223
6.5.2 Transient and recurrent states	p. 226
6.6 Analysis of Equilibrium Markov Chains	p. 231
6.6.1 Balance equations	p. 232
6.6.2 Time averages	p. 239
6.6.3 Long term behavior of aperiodic chains	p. 240
6.6.4 Continuous parameter Markov chains	p. 244
6.7 Performance Evaluation of Discrete Time Queues	p. 245
6.7.1 Throughput	p. 245
6.7.2 Buffer occupancy	p. 246
6.7.3 Response time	p. 247
6.7.4 Relationship between [pi subscript c] and [pi subscript e]	p. 248
6.8 Applications	p. 249
6.8.1 The general Geom/Geom/m/k queue	p. 253
6.8.1.1 Transition probabilities	p. 253
6.8.1.2 Equilibrium state probabilities	p. 254
6.8.2 Slotted crossbar	p. 256
6.8.3 Late arrival systems	p. 258
6.9 Conclusion	p. 259
6.10 Exercises	p. 259
7 Continuous Time Queuing Networks	p. 267
7.1 Introduction	p. 267
7.2 Model and Notation for Open Networks	p. 268
7.3 Global Balance Equations	p. 270
7.4 Traffic Equations	p. 273
7.5 The Product Form Solution	p. 276
7.6 Validity of Product Form Solution	p. 278
7.7 Development of Product Form Solution for Closed Networks	p. 282
7.8 Convolution Algorithm	p. 286
7.9 Performance Figures from the g(n, m) Matrix	p. 288
7.9.1 Marginal state probabilities	p. 288
7.9.2 Average number in a station	p. 289
7.9.3 Throughput in a station	p. 289
7.9.4 Utilization in a station	p. 289
7.9.5 Expected response time in a station	p. 290
7.10 Mean Value Analysis	p. 293
7.10.1 Arrival theorem	p. 294
7.10.2 Cyclic network	p. 295
7.10.2.1 MVA for cyclic queues	p. 295
7.10.3 Noncyclic closed networks	p. 296
7.10.3.1 MVA for noncyclic networks	p. 298
7.11 Conclusion	p. 301
7.12 Exercises	p. 301
8 The G/M/1 Queue	p. 307
8.1 Introduction	p. 307
8.2 The Imbedded Markov Chain for G/M/1/[infinity] Queue	p. 307
8.3 Analysis of the Parameter [alpha]	p. 313
8.3.1 Stability criterion in terms of the parameters of the queue	p. 317
8.3.2 Determination of [alpha]	p. 319
8.4 Performance Figures in G/M/1/[infinity] Queue	p. 321
8.4.1 Expected response time	p. 321
8.4.2 Expected number in the system	p. 321
8.5 Finite Buffer G/M/1/k Queue	p. 322
8.6 Pareto Arrivals in a G/M/1/[infinity] Queue	p. 323
8.7 Exercises	p. 326
9 Queues with Bursty, MMPP, and Self-Similar Traffic	p. 329
9.1 Introduction	p. 329
9.2 Distinction between Smooth and Bursty Traffic	p. 331
9.3 Self-Similar Processes	p. 334
9.3.1 Fractional Brownian motion	p. 335
9.3.2 Discrete time fractional Gaussian noise and its properties	p. 336
9.3.3 Problems in generation of pure FBM	p. 337
9.4 Hyperexponential Approximation to Shifted Pareto Interarrival Times	p. 337
9.5 Characterization of Merged Packet Sources	p. 339
9.6 Product Form Solution for the Traffic Source Markov Chain	p. 340
9.6.1 Evaluation of h, the Constant in the Product Form Solution	p. 343
9.7 Joint Markov Chain for the Traffic Source and Queue Length	p. 344
9.8 Evaluation of Equilibrium State Probabilities	p. 348
9.8.1 Analysis of the sequence R[subscript (n)]	p. 351
9.9 Queues with MMPP Traffic and Their Performance	p. 355
9.10 Performance Figures	p. 357
9.11 Conclusion	p. 357
9.12 Exercises	p. 358
10 Analysis of Fluid Flow Models	p. 363
10.1 Introduction	p. 363
10.2 Leaky Bucket with Two State ON-OFF Input	p. 364
10.2.1 Development of differential equations for buffer content	p. 365
10.2.2 Stability condition	p. 376
10.3 Little's Result for Fluid Flow Systems	p. 377
10.4 Output Process of Buffer Fed by Two State ON-OFF chain	p. 382
10.5 General Fluid Flow Model and its Analysis	p. 384
10.6 Leaky Bucket Fed by M/M/1/[infinity] Queue Output	p. 387
10.7 Exercises	p. 394
A Review of Probability Theory	p. 397
A.1 Random Experiment	p. 397
A.2 Axioms of Probability	p. 397
A.2.1 Some useful results	p. 398
A.2.2 Conditional probability and statistical independence	p. 399
A.3 Random Variable	p. 400
A.3.1 Cumulative distribution function	p. 401
A.3.2 Discrete random variables and the probability mass function	p. 402
A.3.3 Continuous random variables and the probability density function	p. 403
A.3.4 Mixed random variables	p. 404
A.4 Conditional pmf and Conditional pdf	p. 405
A.5 Expectation, Variance, and Moments	p. 407
A.5.1 Conditional expectation	p. 411
A.6 Theorems Connecting Conditional and Marginal Functions	p. 412
A.7 Sums of Random Variables	p. 415
A.7.1 Sum of two discrete random variables	p. 415
A.7.2 Sum of two continuous random variables	p. 416
A.8 Bayes' Theorem	p. 417
A.9 Function of a Random Variable	p. 421
A.9.1 Discrete function of a random variable	p. 421
A.9.1.1 Discrete function of a discrete random variable	p. 421
A.9.1.2 Discrete function of a continuous random variable	p. 422
A.9.2 Strictly monotonically increasing function	p. 422
A.9.3 Strictly monotonically decreasing function	p. 423
A.9.4 The general case of a function of a random variable	p. 423
A.10 The Laplace Transform L	p. 428
A.11 The Z Transform	p. 430
A.12 Exercises	p. 434
Index	p. 436

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents