Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
xiv Preface
tables used in switches and routers. The performance of the hashing function and
average lookup delay are analyzed. The B-tree data structure is discussed and the
advantages of B-trees over regular binary trees and multiway trees are explained.
Advanced Topics
I invested special effort in making this book useful to practicing engineers and
students. There are many interesting examples and models throughout the book.
However, I list here some interesting topics:
• Chapter 1 discusses heavy-tailed distribution in Section 1.20 and generation of
random numbers in Section 1.35.
• Chapter 3 discusses techniques for finding higher powers for Markov chain state
transition matrix in Sections 3.13 and 3.14.
• Chapter 5 discusses reducible Markov chains at steady state in Section 5.7 and
transient analysis of reducible Markov chains in Section 5.6. Also, there is a dis-
cussion on how to identify a reducible Markov chain by examining its eigenvalues
and eigenvectors.
• Chapter 6 discusses transient analysis of periodic Markov chains in Section 6.15
and asymptotic behavior of periodic Markov chains in Section 6.15. Also, there
is a discussion on how to identify a periodic Markov chain and how to determine
its period by examining its eigenvalues.
• Chapter 7 discusses developing performance metrics for the major queue types.
• Chapter 8 discusses how to model three flow control protocols dealing with traffic
management.
• Chapter 9 discusses how to model three flow control protocols dealing with error
control.
• Chapter 10 discusses how to model three flow control protocols dealing with
medium access control.
• Chapter 11 discusses developing realistic models for source traffic using Poisson
description (Section 11.3.2), Bernoulli (Section 11.4.3), and Pareto traffic (Sec-
tion 11.8). There is also discussion on packet destination and length modeling.
• Chapter 12 discusses 12 scheduling algorithms and provides Markov chain anal-
ysis for many of them.
• Chapter 13 discusses seven types of switches based on their buffering strategies
and the advantages and disadvantages of each choice.
• Chapter 14 discusses many types of interconnection networks and also provides,
for the first time, analysis of the performance of each network.
Web Resource
The website http://www.ece.uvic.ca/∼fayez/Book, www.springer.com/978-0-387-
74437-7 contains information about the textbook and any related web resources.
Preface xv
Errors
This book covers a wide range of topics related to communication networks and
provides an extensive set of analyses and worked examples. It is “highly probable”
that it contains errors and omissions. Other researchers and/or practicing engineers
might have other ideas about the content and organization of this book. We welcome
receiving any constructive comments and suggestions for inclusion in the next edi-
tion. If you find any errors, we would appreciate hearing from you. We also welcome
ideas for examples and problems (along with their solutions if possible) to include
in the next edition with proper citation.
You can send your comments and bug reports electronically to fayez@uvic.ca,
or you can fax or mail the information to
Dr. Fayez Gebali
Elec. and Comp. Eng. Dept.
University of Victoria Victoria, B.C., Canada V8W 3P6
Tel: (250) 721-6509
Fax: (250)721-6052.
Acknowledgment
I was motivated to write this book as a result of reading two very good works.
One book is of course the famous Queueing Systems – Volume 1: Theory by Leonard
Kleinrock. The other book is Communication and Computer Networks: Modeling
with Discrete-Time Queues by Michael E. Woodward. The title of the last book
sums it all. Discrete-time queuing systems proved to be very useful in dealing with
communications systems.
I felt that there were more practical topics and important definitions that either
were not discussed or were a bit vague. This book provides a minor contribution
to this area by summarizing in book form the techniques I advise my students to
use while doing their graduate degrees under my supervision. I would like to thank
Dr. Mohamed Watheq El-Kharashi for suggesting that I put everything in a book
format. I also value his excellent suggestions and help. His vision, suggestions, and
his time were absolutely helpful and appreciated.
I would like to thank Dr. W.-S. Lu of the Electrical and Computer Engineering
Department at the University of Victoria for his extremely valuable help and insight
in all the matrix topics covered in this book. I would also like to thank Dr. G.A. Shoja
and Dr. D. Olesky of the Computer Science Department at the University of Victoria
for their suggestions, the references they provided, and their encouragement during
preparing the material for this book. The constant help and feedback of some of my
past and current graduate students was particularly helpful. In particular, I note Mr.
Maher Fahmi, Dr. A. Sabba, and Dr. Esam Abdel-Raheem.
Gratitude must go to PMC-Sierra, Inc. of Vancouver for the meetings and con-
sultations I regularly had with their directors, managers, and engineering staff. The
financial support of PMC-Sierra throughout the years have contributed enormously
to my research program. Without that support I would not have been able to build
my research group or acquire the necessary equipment.
The MathWorks, Inc. has provided me with their MATLAB, Simulink, and State-
flow software packages. This is a great help in developing the material and presen-
tations for the examples and problems of this book. For that I am obliged.
Thanks must go to my children Michael Monir, Tarek Joseph, Aleya Lee, and
Manel Alia for being such responsible and outstanding young men and women.
Victoria, B.C. Dr. Fayez Gebali, Ph.D., P.Eng.
Canada
xvii
About the Author
Dr. Fayez Gebali has been the Associate Dean (undergraduate programs) from July
2002 – June 2007 at the Faculty of Engineering, University of Victoria. He is also
a professor at the Electrical and Computer Engineering Department. He joined the
department after its inception in 1983 where he was an assistant professor from
1984 to 1986, associate professor from 1986 to 1991, and professor from 1991 to
the present. Before that he was a research associate with Dr. M.I. Elmasry in the De-
partment of Electrical Engineering at the University of Waterloo from 1983 to 1984.
He was also a research associate with Dr. K. Colbow in the Physics Department of
Simon Fraser University from 1979 to 1983.
Dr. Gebali’s research interests include computer networks, communication pro-
tocol modeling, and computer arithmetic. He has published over 170 articles in
refereed journals and conferences in his areas of expertise.
Dr. Gebali received his B.Sc. in Electrical Engineering (first-class honors) from
Cairo University, his B.Sc. (first-class honors) in Applied Mathematics from Ain
Shams University, and his Ph.D. degree in Electrical Engineering from the Univer-
sity of British Columbia. Dr. Gebali is a senior member of the IEEE since 1983
and a member of the Society of Professional Engineers and Geoscientists of British
Columbia since 1985.
xix
Contents
1 Probability ..................................................... 1
1.1 Introduction . .............................................. 1
1.2 Applying Set Theory to Probability . . . . . . ..................... 2
1.3 Counting Sample Space Points . . . ............................ 4
1.4 The Multiplication Principle . . . . . ............................ 4
1.5 Permutations.............................................. 5
1.5.1 n Distinct Objects Taken n ataTime................... 5
1.5.2 n Distinct Objects Taken k ataTime................... 6
1.6 Permutations of Objects in Groups . . . . . . . ..................... 6
1.7 Combinations ............................................. 8
1.8 Probability . . .............................................. 8
1.9 Axioms of Probability . . . ................................... 9
1.10 Other Probability Relationships . . ............................ 9
1.11 Random Variables . . . ....................................... 10
1.12 Cumulative Distribution Function (cdf) . . . ..................... 11
1.12.1 cdfintheDiscreteCase.............................. 12
1.13 Probability Density Function (pdf) ............................ 13
1.14 Probability Mass Function . . . . . . . ............................ 13
1.15 Expected Value and Variance . . . . ............................ 14
1.16 Common Continuous RVs ................................... 16
1.17 Continuous Uniform (Flat) RV . . . ............................ 16
1.18 GaussianRV .............................................. 18
1.19 Exponential RV . . . . . ....................................... 19
1.20 ParetoRV................................................. 19
1.21 CommonDiscreteRVs...................................... 21
1.22 DiscreteUniformRV....................................... 21
1.23 Bernoulli(Binary)RV ...................................... 23
1.24 GeometricRV............................................. 24
1.25 BinomialRV.............................................. 25
1.25.1 ApproximatingtheBinomialDistribution............... 26
1.26 PoissonRV ............................................... 28
1.27 Systems with Many Random Variables . . . ..................... 30
1.28 Jointcdfandpdf........................................... 31
xxi
xxii Contents
1.29 Individual pmf From a Given Joint pmf . . . ..................... 32
1.30 Expected Value . . . . . ....................................... 33
1.31 Correlation................................................ 34
1.32 Variance . . . . .............................................. 34
1.33 Covariance . . .............................................. 34
1.34 Transforming Random Variables . ............................ 35
1.34.1 Continuous Case ................................... 35
1.34.2 DiscreteCase ...................................... 38
1.35 Generating Random Numbers ................................ 39
1.35.1 UniformDistribution................................ 39
1.35.2 InversionMethod................................... 39
1.35.3 RejectionMethod................................... 40
1.35.4 Importance Sampling Method . . . ..................... 41
References . . . . .................................................. 48
2 Random Processes............................................... 49
2.1 Introduction . .............................................. 49
2.2 Notation.................................................. 51
2.3 Poisson Process . . . . . ....................................... 52
2.4 Exponential Process . ....................................... 52
2.5 Deterministic and Nondeterministic Processes . ................. 52
2.6 EnsembleAverage ......................................... 53
2.7 TimeAverage ............................................. 54
2.8 Autocorrelation Function . ................................... 54
2.9 Stationary Processes ........................................ 56
2.10 Cross-Correlation Function . . . . . . ............................ 57
2.11 Covariance Function . ....................................... 58
2.12 CorrelationMatrix ......................................... 59
2.13 Covariance Matrix . . ....................................... 60
References . . . . .................................................. 64
3 Markov Chains ................................................. 65
3.1 Introduction . .............................................. 65
3.2 MarkovChains ............................................ 65
3.3 SelectionoftheTimeStep................................... 66
3.3.1 Discrete-TimeMarkovChains ........................ 66
3.4 Memoryless Property of Markov Chains . . ..................... 68
3.5 Markov Chain Transition Matrix . ............................ 69
3.6 MarkovMatrices........................................... 75
3.6.1 The Diagonals of P . . . . . ............................ 78
3.7 EigenvaluesandEigenvectorsofP............................ 79
3.8 Constructing the State Transition Matrix P ..................... 81
3.9 TransientBehavior ......................................... 82
3.9.1 Properties of P
n
.................................... 85
3.10 Finding s (n) .............................................. 85
3.11 Finding s (n) by Expanding s (0) . . ............................ 86
Contents xxiii
3.12 Finding s (n) by Diagonalizing P . . ............................ 91
3.12.1 Comparing Diagonalization with Expansion of s (0) ...... 92
3.13 Expanding P
n
inTermsofItsEigenvalues...................... 94
3.13.1 Test for Matrix Diagonalizability . .....................102
3.14 Finding s (n) Using the Jordan Canonic Form . . .................103
3.14.1 Jordan Canonic Form (JCF) . . . . . .....................103
3.14.2 Properties of Jordan Canonic Form . . . .................106
3.15 Properties of Matrix U . . . ...................................107
3.16 P
n
Expressed in Jordan Canonic Form . . . .....................108
3.17 Expressing P
n
inTermsofItsEigenvalues .....................109
3.18 Finding P
n
UsingtheZ-Transform............................111
3.19 Renaming the States . .......................................111
References . . . . ..................................................121
4 Markov Chains at Equilibrium ...................................123
4.1 Introduction . ..............................................123
4.2 Markov Chains at Equilibrium . . . ............................123
4.3 Significance of s at “Steady State” ............................123
4.4 Finding Steady-State Distribution Vector s .....................124
4.5 Techniques for Finding s . ...................................125
4.6 Finding s Using Eigenvector Approach . . . .....................126
4.7 Finding s Using Difference Equations . . . . .....................127
4.8 FindingsUsingZ-Transform ................................130
4.9 Finding s Using Forward- or Back-Substitution .................137
4.10 Finding s Using Direct Techniques . . . . . . . .....................140
4.11 Finding s Using Iterative Techniques . . . . . .....................141
4.12 Balance Equations . . .......................................142
References . . . . ..................................................149
5 Reducible Markov Chains ........................................151
5.1 Introduction . ..............................................151
5.2 Definition of Reducible Markov Chain . . . .....................152
5.3 ClosedandTransientStates..................................152
5.4 Transition Matrix of Reducible Markov Chains .................153
5.5 Composite Reducible Markov Chains . . . . .....................155
5.6 TransientAnalysis .........................................157
5.7 Reducible Markov Chains at Steady-State . .....................161
5.8 Reducible Composite Markov Chains at Steady-State . . ..........164
5.9 Identifying Reducible Markov Chains . . . . .....................167
5.9.1 DeterminingClosedandTransientStates ...............170
5.10 Identifying Reducible Composite Matrices .....................172
References . . . . ..................................................182
6 Periodic Markov Chains .........................................183
6.1 Introduction . ..............................................183
6.2 Definition. . . ..............................................184
xxiv Contents
6.3 Types of Periodic Markov Chains .............................185
6.4 The Transition Matrix . . . ...................................185
6.5 The Transition Matrix Determinant . . . . . . .....................187
6.6 Transition Matrix Diagonalization ............................188
6.7 Transition Matrix Eigenvalues. . . . ............................191
6.8 Transition Matrix Elements . . . . . . ............................195
6.9 Canonic Form for P ........................................196
6.10 Transition Diagram . . .......................................197
6.11 Composite Strongly Periodic Markov Chains . . .................198
6.12 Weakly Periodic Markov Chains . . ............................202
6.13 Reducible Periodic Markov Chains . . . . . . .....................208
6.14 TransientAnalysis .........................................211
6.15 AsymptoticBehavior .......................................213
6.16 IdentificationofMarkovChains..............................216
6.16.1 Nonperiodic Markov chain . . . . . . .....................217
6.16.2 Strongly periodic Markov chain . . .....................217
6.16.3 Weakly periodic Markov chain. . . .....................217
6.17 Problems .................................................218
References . . . . ..................................................221
7 Queuing Analysis ...............................................223
7.1 Introduction . ..............................................223
7.1.1 Kendall’s Notation . . . . . . ............................224
7.2 Queue Throughput (Th) . . ...................................225
7.3 Efficiency (η) or Access Probability (p
a
).......................226
7.4 TrafficConservation........................................227
7.5 M/M/1 Queue . . . . . . .......................................227
7.5.1 M/M/1 Queue Performance . . . . .....................230
7.6 M/M/1/B Queue . . . . .......................................233
7.6.1 M/M/1/B Queue Performance . . .....................235
7.6.2 Performance Bounds on M/M/1/B Queue . . . ..........240
7.7 M
m
/M/1/B Queue . .......................................241
7.7.1 M
m
/M/1/B Queue Performance .....................242
7.7.2 Performance Bounds on M
m
/M/1/B Queue . . ..........246
7.7.3 AlternativeSolutionMethod..........................247
7.8 M/M
m
/1/B Queue . .......................................248
7.8.1 M/M
m
/1/B Queue Performance .....................249
7.8.2 Performance Bounds on M/M
m
/1/B Queue . . ..........252
7.8.3 AlternativeSolutionMethod..........................253
7.9 The D/M/1/B Queue . . . ...................................253
7.9.1 Performance of the D/M/1/B Queue. .................256
7.10 The M/D/1/B Queue . . . ...................................257
7.10.1 Performance of the M/D/1/B Queue. .................259
7.11 SystemsofCommunicatingMarkovChains ....................260
7.11.1 A General Solution for Communicating Markov Chains. . . 263
References . . . . ..................................................268
Contents xxv
8 Modeling Traffic Flow Control Protocols ...........................269
8.1 Introduction . ..............................................269
8.2 TheLeakyBucketAlgorithm ................................269
8.2.1 ModelingtheLeakyBucketAlgorithm.................271
8.2.2 Single Arrival/Single Departure Model (M /M /1 /B) . . . . 272
8.2.3 Leaky Bucket Performance (M /M /1 /B Case)..........274
8.2.4 Multiple Arrival/Single Departure Model (M
m
/M /1 /B) . 276
8.2.5 Leaky Bucket Performance (M
m
/M /1 /B Case)........278
8.3 TheTokenBucketAlgorithm ................................280
8.3.1 ModelingtheTokenBucketAlgorithm.................282
8.3.2 Single Arrival/Single Departures Model (M /M /1 /B) . . . 282
8.3.3 Token Bucket Performance (M /M /1 /B Case)..........285
8.3.4 Multiple Arrivals/Single Departures Model (M
m
/M /1 /B)288
8.3.5 Token Bucket Performance (Multiple Arrival/Departure
Case) ............................................ 291
8.4 Virtual Scheduling (VS) Algorithm . . . . . . .....................295
8.4.1 ModelingtheVSAlgorithm..........................296
8.4.2 VS Protocol Performance ............................298
References . . . . ..................................................301
9 Modeling Error Control Protocols.................................303
9.1 Introduction . ..............................................303
9.2 Stop-and-Wait ARQ (SW ARQ) Protocol . .....................303
9.2.1 Modeling Stop-and-Wait ARQ . . . .....................305
9.2.2 SW ARQ Performance . . ............................306
9.3 Go-Back-N (GBN ARQ) Protocol ............................308
9.3.1 Modeling the GBN ARQ Protocol . . . . .................309
9.3.2 Using Iterations to Find s ............................312
9.3.3 AlgorithmforFindingsbyIterations ..................313
9.3.4 GBN ARQ Performance . ............................314
9.4 Selective-Repeat (SR ARQ) Protocol . . . . . .....................316
9.4.1 Modeling the SR ARQ Protocol . . .....................316
9.4.2 SR ARQ Performance . . . ............................320
References . . . . ..................................................324
10 Modeling Medium Access Control Protocols ........................325
10.1 Introduction . ..............................................325
10.2 IEEE Standard 802.1p: Static Priority Protocol..................326
10.2.1 Modeling the IEEE 802.1p: Static Priority Protocol ......326
10.3 ALOHA..................................................329
10.3.1 ModelingtheALOHANetwork.......................330
10.3.2 ALOHA Performance . . . ............................332
10.4 SlottedALOHA ...........................................335
10.4.1 ModelingtheSlottedALOHANetwork ................335
10.4.2 Slotted ALOHA Performance . . . .....................337
xxvi Contents
10.5 IEEE Standard 802.3 (CSMA/CD) ............................340
10.5.1 IEEE 802.3 (CSMA/CD) Model Assumptions ...........341
10.5.2 IEEE 802.3 (CSMA/CD) State Transition Diagram.......342
10.5.3 IEEE 802.3 (CSMA/CD) Protocol Performance . . . ......343
10.6 Carrier Sense Multiple Access-Collision Avoidance (CSMA/CA) . . 345
10.6.1 CSMA/CA Model Assumptions . . .....................346
10.6.2 CSMA/CA Protocol Performance .....................348
10.7 IEEE 802.11: DCF Function for Ad Hoc Wireless LANs . . . ......351
10.7.1 IEEE 802.11: DCF Medium Access Control . . ..........351
10.7.2 IEEE 802.11: DCF Model Assumptions . . . . . . ..........352
10.7.3 IEEE 802.11: DCF Protocol Performance . . . . . ..........356
10.7.4 IEEE 802.11/DCF Final Remarks .....................360
10.8 IEEE 802.11: PCF Function for Infrastructure Wireless LANs . . . . . 361
10.8.1 IEEE 802.11: PCF Medium Access Control . . . ..........362
10.8.2 IEEE 802.11: Nonpersistent PCF Model Assumptions . . . . 362
10.8.3 IEEE 802.11: Nonpersistent PCF Protocol Performance . . . 364
10.8.4 IEEE 802.11: 1-Persistent PCF . . .....................366
10.8.5 1-Persistent IEEE 802.11/PCF Performance . . . ..........369
10.8.6 1-Persistent IEEE 802.11/PCF User Performance . . ......371
10.9 IEEE 802.11e: Quality of Service Support .....................374
References . . . . ..................................................381
11 Modeling Network Traffic ........................................383
11.1 Introduction . ..............................................383
11.2 Flow Traffic Models ........................................384
11.2.1 Modulated Poisson Processes .........................384
11.2.2 On–Off Model . . ...................................385
11.2.3 Markov Modulated Poisson Process . . .................386
11.2.4 Autoregressive Models . . ............................387
11.3 Continuous-Time Modeling: Poisson Traffic Description . . . ......387
11.3.1 Memoryless Property of Poisson Traffic . . . . . . ..........389
11.3.2 Realistic Models for Poisson Traffic . . .................391
11.3.3 FlowDescription ...................................392
11.3.4 InterarrivalTimeDescription .........................392
11.3.5 ExtractingPoissonTrafficParameters..................394
11.3.6 Poisson Traffic and Queuing Analysis ..................395
11.4 Discrete-Time Modeling: Interarrival Time for Bernoulli Traffic . . . 398
11.4.1 Realistic Models for Bernoulli Traffic ..................401
11.4.2 Memoryless Property of Bernoulli Traffic . . . . ..........402
11.4.3 Realistic Model for Bernoulli Traffic. . .................403
11.4.4 ExtractingBernoulliTrafficParameters ................404
11.4.5 Bernoulli Traffic and Queuing Analysis . . . . . . ..........405
11.5 Self-SimilarTraffic.........................................407
11.6 Self-Similarity and Random Processes.........................408
11.7 Heavy-TailedDistributions ..................................409