Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
666 Index
Queuing analysis (cont.)
objective of, 223
systems of communicating Markov chains,
260–263
general solution for, 263–264
Queuing systems, 78
R
Random early detection (RED), 466–467
Random early drop detection, 466
Random numbers, generating, 39
importance sampling method, 41
inversion method, 39–40
rejection method, 40–41
uniform distribution, 39
using Gaussian distribution, 18
using Pareto distribution, 21
Von Neumann’s remark, 39
Random processes, 49–51
autocorrelation function, 54–55
correlation matrix, 59–60
covariance function, 58–59
covariance matrix, 60–62
cross-correlation function, 57
deterministic and nondeterministic
processes, 52–53
ensemble average, 53–54
exponential process, 52
notation, 51
Poisson process, 52
stationary processes, 56–57
time average, 54
types, 49–50
Random variables
Bernoulli (binary), 23–24
binomial, 25–26
approximating binomial distribution,
26–27
common continuous, 16
common discrete, 21
continuous, 10
cdf for, 12
pdf for, 13
continuous uniform (flat), 16–17
correlation between two, 23–24
discrete, 10, 21
cdf for, 12
pdf for, see Probability, mass function
uniform, 21–22
discrete uniform, 21–22
examples and numerical values, 10–11
exponential, 19
Gaussian, 18
geometric, 24–25
mean (m) of, 15
Pareto, 19–21
Poisson, 28–30
distribution from binomial distribution,
29–30
probability, 10–11
systems with many, 30
systems with many, 30
transforming, 35
continuous case, 35–38
discrete case, 38
variance, 34
Realistic bursty source, 391, 411
Reducible Markov chains, 151–152, 152
closed and transient states, 152–153
composite, 155–157
composite, at steady-state, 164–167
example, 151
identifying, 167–170
determining closed and transient states,
170–172
reducible composite matrices, 172–175
at steady-state, 161–164
transient analysis, 157–161
transition matrix of, 153–155
two sets of closed state, 153
Relative-frequency approach, 8
RESIDUE (MATLAB command), 133, 135
Round robin scheduler (RR), 439–440
queuing analysis for RR, 441–444
serving four sessions, 440
Router, 486
Rref (MATLAB function), 625
S
Sample space, 1
Scalars, 613
arithmetic operations on, 639
basic operations for, 639
Scheduler design issues, 434
degree of aggregation, 435
packet drop policy, 436
priority, 435
work-conserving versus nonwork-
conserving, 435–436
Scheduling algorithms versus media access
control (MAC) techniques, 434
Selective-repeat (SR ARQ) protocol, 316
modeling, 316–319
performance, 320–321
Set theory, and probability, 2–4
Shared buffer switch, 496–497, 569–572
assumptions for analysis of, 569
Index 667
performance, 571–572
performance bounds on, 572–574
Shuffle function, 517
Simple traffic models (point processes), 383
S(n)usingz-transform, finding, 607–611
Software, 478
networking components, examples, 478
Space division switching, 510
SR ARQ protocol, see Selective-repeat (SR
ARQ) protocol
Standard deviation ,15
State of occupancy
packet buffer, 283–284, 290
token buffer, 283, 290
State transition diagram
for ALOHA channel, 331
for 802.11 channel, 355
for CSMA/CA, 347
for discrete-time M/M/1 queue, 228
of sending station using GBN ARQ error
control protocol, 310
sending station using SR ARQ error control
protocol, 318
State transition matrix
constructing, P, Markov chains, 81–82
State vector, see Distribution vector
Static priority (SP) scheduler, 439
Stationary random processes, 56–57
ergodic, 57
properties, 56
Steady state
finding distribution vector s, 124–125
significance of s, 123–124
Stochastic processes, 49
Stop-and-wait ARQ (SW ARQ) protocol,
303–304
modeling stop-and-wait ARQ, 305–306
SW ARQ performance, 306–308
Switches, 478, 579–580
basic performance measures, 491–492
classifications, 492
comparision, 574–576
components, 486–487, 487
control section, 488–489
datapath, 489
lookup table design, 489–490
Network Processing Unit (NPU),
487–488
switch fabric, 489
designing approaches, 579–580
functions, 490
input queuing, 493, 552–555
arrival and departure probabilities for
one queue of, 553
assumptions for analysis of, 552
congestion in, 555
efficiency of, 554
performance bounds on, 555–558
potential causes for packet loss, 494
modeling VRQ switch, 585–587
analysis of input buffer, 587–589
analysis of output queue, 589–591
performance bounds on VRQ switch,
591–593
multiple input/output queuing, 499–500
multiple input queuing, 497–498
multiple output queuing, 498–499
output queuing, 494–495, 558–559
assumptions for analysis of, 558
modeling input buffer, 559–561
modeling output queue, 561–562
output queue performance, 563–565,
566–569
potential causes for packet loss, 496
transition matrix, 562–563
Promina 4000 switch, 580–581
backplane bus operation, 581
features, 582
Input Port Operation, 581
output port operation, 581
versus VRQ switch, 584–585
scheduler location in, 432–434
shared buffer, 496–497, 569–572
assumptions for analysis of, 569
performance, 571–572
performance bounds on, 572–574
switch functions, 490
congestion control, 491
routing, 490
scheduling, 491
traffic management, 490–491
switch performance measures, 491–492
virtual routing/virtual queuing (VRQ),
500–502
VRQ switch, 582–583
backplane bus operation, 583
features, 584
input port operation, 583
output port operation, 583
Switches and routers, 477–479
circuit and packet switching, 481
circuit switching, 482–483
packet switching, 483–484
components, 486–487
control section, 488–489
668 Index
Switches and routers (cont.)
datapath section, 489
lookup table design, 489–490
Network Processing Unit (NPU),
487–488
switch fabric, 489
input queuing switch, 492–494
media access techniques, 479–480
code division multiple access
(CDMA), 481
frequency division multiple access
(FDMA), 481
time division multiple access
(TDMA), 480
multiple input/output queuing switch,
499–500
multiple input queuing switch, 497–498
multiple output queuing switch, 498–499
networking, 479
output queuing switch, 494–496
packet switching hardware, 484
bridge, 485
end-node, 484
gateway, 486
hub, 485
router, 486
switch, 485–486
shared buffer switch, 496–497
switch classifications, 492
switch functions, 490
congestion control, 491
routing, 490
scheduling, 491
traffic management, 490–491
switch performance measures,
491–492
VRQ switch, 500–502
Switching hub, 485
Switch modeling, 551
comparing three switches, 574–576
input queuing switch, 552–555
congestion in input queuing switch, 555
performance bounds on input queuing
switch, 555–558
modeling other switch types, 576
output queuing switch, 558–559
modeling input buffer, 559–561
modeling output queue, 561–566
performance bounds on, 566–569
shared buffer switch, 569–572
performance bounds, 572–574
Synchronization and clock speed, network
hardware, 508
T
Tail drop strategy, 466
Telecommunication traffic, models, 383
Three-state MMPP source model, 387
Time division multiple access
(TDMA), 509
interconnection networks, 509
random assignment, 510
static-assignment, 509–510
media access techniques, 480
random assignment, 510
static-assignment, 509–510
Time division switching, 480
random assignment, 510
static assignment, 510
Toeplitz matrix, 60
Token bucket algorithm, 280–281
control of data rate by, 281
modeling, 282
multiple arrivals/single departures model
(M
m
/M/1/B), 288–291
single arrival/single departures model
(M/M/1/B), 282–285
throughput of, 286
token bucket performance (M/M/1/B
case), 285–288
token bucket performance (multiple
arrival/departure case), 291–295
Token buffer
Markov chain transition diagram, 284
state of occupancy, 283, 290
Traffic conservation, 227
Traffic intensity, 230
Traffic management protocols, 491
examples, 491
Traffic policing, see Traffic shaping
Traffic shaping, 269
Transition matrix
diagonalization
strongly periodic Markov chain, 188
Markov chains, 69–75
observations on asymptotic value, 216
periodic Markov chains, 185–187
determinant, 187–188
diagonalization, 188–191
eigenvalues, 191–195
elements, 195–196
unitary (orthogonal), 189
Trees, database design, 653
binary trees, 653–654
B-trees, 655–656
multiway trees, 654–655
Index 669
U
Union (set), 2
V
Vectors, 613–614
arithmetic operations with, 614
column, 613–614
linear independence of, 615
Vectors and matrices, 613
arithmetic operations with vectors, 614
diagonalizing matrix, 619
eigenvalues and eigenvectors, 618
inverse of matrix, 616–617
iterative techniques, 629
Gauss–Seidel iterations, 630–631
Jacobi iterations, 630
successive overrelaxation
iterations, 631
linear equations, 620–621
Gauss elimination, 621–623
Gauss–Jordan elimination, 623–625
Givens rotations, 627–629
row echelon form and reduced row
echelon form, 625–627
techniques for solving, 627
linear independence of vectors, 615
matrices, 615
matrix addition, 616
matrix multiplication, 616
null space of matrix, 617
rank of matrix, 618
scalars, 613
similarity transformation, 631–632
special matrices
circulant matrix, 632–633
diagonal matrix, 633
echelon matrix, 633–634
identity matrix, 634
nonnegative matrix, 634
orthogonal matrix, 634–635
plane rotation (givens) matrix, 635
stochastic (Markov) matrix, 635
substochastic matrix, 635–636
tridiagonal matrix, 636
upper Hessenberg matrix, 636
triangularizing matrix, 619–620
vectors, 613–614
Virtual circuit switching, 483
advantages over circuit and datagram,
483–484
Virtual clock (VC) algorithm, 451
Virtual output queuing (VOQ) switch, 433, 497
Virtual queuing, 583
Virtual routing/virtual queuing (VRQ) switch,
see VRQ switch
Virtual scheduling (VS) algorithm, 295–296
modeling, 296–297
protocol performance, 298–299
Von Neumann and Random numbers, 39
VRQ switch, 582–583
backplane bus operation, 583
features, 584
high-performance switch, 582
simple implementation of, 586
input port operation, 583
modeling, 585–587
analysis of input buffer, 587–589
analysis of output queue, 589–591
assumptions for analysis, 586–587
performance bounds on, 591–593
output port operation, 583
versus Promina 4000, 584–585
VS algorithm, see Virtual scheduling (VS)
algorithm
W
Wavelength division multiplexing
(WDM), 434
Weighted round robin scheduler (WRR),
444–445
queuing analysis for WRR, 445–446