Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
Contents xxvii
11.8 ParetoTrafficDistribution...................................409
11.8.1 FlowDescription ...................................411
11.8.2 InterarrivalTimeDescription .........................411
11.8.3 ExtractingParetoInterarrivalTimeStatistics............412
11.8.4 Pareto Distribution and Queuing Analysis . . . . ..........414
11.9 Traffic Data Rate Modeling with Arbitrary Source Distribution . . . . 417
11.10 Interarrival Time Traffic Modeling with Arbitrary Source
Distribution .............................................. 418
11.11 DestinationStatistics .......................................420
11.11.1 UniformTraffic ....................................420
11.11.2 Broadcast Traffic ...................................420
11.11.3 Hot-Spot Traffic ....................................421
11.12 Packet Length Statistics . . ...................................422
11.13 PacketTransmissionErrorDescription ........................423
References . . . . ..................................................428
12 Scheduling Algorithms ...........................................431
12.1 Introduction . ..............................................431
12.1.1 PacketSelectionPolicy..............................431
12.1.2 Packet Dropping Policy . . ............................431
12.1.3 Fair Sharing Policy . . . . . ............................432
12.2 Scheduling as an Optimization Problem . . .....................432
12.3 Scheduler Location in Switches . . ............................432
12.4 Scheduling and Medium Access Control . . .....................434
12.5 Scheduler Design Issues . ...................................434
12.5.1 Priority ...........................................435
12.5.2 DegreeofAggregation ..............................435
12.5.3 Work-Conserving Versus Nonwork-conserving ..........435
12.5.4 PacketDropPolicy .................................436
12.6 Rate-Based Versus Credit-Based Scheduling . . .................436
12.7 Scheduler Performance Measures .............................437
12.8 Analysis of Common Scheduling Algorithms . . .................437
12.9 First-In/First-Out(FIFO)....................................437
12.9.1 Queuing Analysis of FIFO/FCFS . .....................438
12.10 Static Priority (SP) Scheduler . . . . ............................439
12.11 Round Robin Scheduler (RR) . . . . ............................439
12.11.1 Queuing Analysis for RR ............................441
12.12 Weighted Round Robin Scheduler (WRR) .....................444
12.12.1 Queuing Analysis for WRR . . . . . .....................445
12.13 Max–Min Fairness Scheduling . . . ............................446
12.14 Processor Sharing (PS). . . ...................................448
12.15 Generalized Processor Sharing (GPS) . . . . .....................449
12.16 Fair Queuing (FQ) . . .......................................451
12.17 Packet-by-PacketGPS(PGPS) ...............................454
12.17.1 VirtualTimeCalculationforPGPS/WFQ...............454
xxviii Contents
12.17.2 FinishNumberCalculationforPGPS/WFQ.............456
12.17.3 CompletionTimeCalculationforPGPS/WFQ...........457
12.18 Frame-Based Fair Queuing (FFQ) ............................459
12.18.1 SystemPotentialCalculationforFFQ..................460
12.18.2 TimestampCalculationforFFQ.......................460
12.18.3 CompletionTimesCalculationforFFQ ................461
12.19 Core-Stateless Fair Queuing (CSFQ) . . . . . .....................463
12.19.1 Determination of Packet Arrival Rate λ
i
................464
12.19.2 Determination of Fair Rate f .........................465
12.19.3 Bit Dropping Probability p
b
..........................465
12.20 Random Early Detection (RED) . . ............................466
12.21 PacketDropOptions .......................................467
References . . . . ..................................................473
13 Switches and Routers ............................................477
13.1 Introduction . ..............................................477
13.2 Networking ...............................................479
13.3 Media Access Techniques ...................................479
13.3.1 Time Division Multiple Access (TDMA) . . . . . ..........480
13.3.2 Space Division Multiple Access (SDMA). . . . . ..........480
13.3.3 Frequency Division Multiple Access (FDMA) . ..........481
13.3.4 Code Division Multiple Access (CDMA) . . . . . ..........481
13.4 CircuitandPacketSwitching ................................481
13.4.1 CircuitSwitching...................................482
13.4.2 PacketSwitching ...................................483
13.5 PacketSwitchingHardware..................................484
13.5.1 End-Node .........................................484
13.5.2 Hub ..............................................485
13.5.3 Bridge............................................485
13.5.4 Switch............................................485
13.5.5 Router............................................486
13.5.6 Gateway ..........................................486
13.6 Basic Switch Components . . . . . . . ............................486
13.6.1 NetworkProcessingUnit(NPU) ......................487
13.6.2 ControlSection ....................................488
13.6.3 Datapath Section ...................................489
13.6.4 SwitchFabric......................................489
13.6.5 Lookup Table Design . . . ............................489
13.7 Switch Functions . . . .......................................490
13.7.1 Routing...........................................490
13.7.2 Traffic Management . . . . ............................490
13.7.3 Scheduling . .......................................491
13.7.4 Congestion Control . . . . . ............................491
13.8 Switch Performance Measures . . . ............................491
13.9 SwitchClassifications ......................................492
Contents xxix
13.10 Input Queuing Switch . . . ...................................492
13.11 Output Queuing Switch . . ...................................494
13.12 Shared Buffer Switch .......................................496
13.13 Multiple Input Queuing Switch . . . ............................497
13.14 Multiple Output Queuing Switch . ............................498
13.15 Multiple Input/Output Queuing Switch . . . .....................499
13.16 Virtual Routing/Virtual Queuing (VRQ) Switch .................500
References . . . . ..................................................506
14 Interconnection Networks ........................................507
14.1 Introduction . ..............................................507
14.2 NetworkDesignParameters .................................507
14.2.1 Network Performance . . . ............................507
14.2.2 NetworkHardware..................................508
14.2.3 Scalability Issues . . . . . . ............................508
14.3 ClassificationofNetworks ..................................509
14.4 Time Division Multiple Access (TDMA) . .....................509
14.4.1 Static-AssignmentTDMA ...........................509
14.4.2 Random Assignment TDMA . . . . .....................510
14.5 Space Division Switching ...................................510
14.6 CrossbarNetwork..........................................511
14.6.1 CrossbarNetworkContentionandArbitration...........512
14.6.2 AnalysisofCrossbarNetwork ........................512
14.7 Multistage Interconnection Networks. . . . . .....................515
14.7.1 Definitions ........................................517
14.8 Generalized-Cube Network (GCN) . . . . . . .....................518
14.8.1 RoutingAlgorithmforGCNNetwork..................519
14.8.2 AnalysisofGCNNetwork ...........................521
14.9 TheBanyanNetwork .......................................523
14.9.1 RoutingAlgorithmforBanyanNetwork................524
14.9.2 AnalysisofBanyanNetwork .........................524
14.10 AugmentedDataManipulatorNetwork(ADMN) ...............527
14.10.1 RoutingAlgorithmsforADMNNetwork...............529
14.10.2 FirstADMNRoutingAlgorithm ......................529
14.10.3 Second ADMN Routing Algorithm . . . .................531
14.10.4 ThirdADMNRoutingAlgorithm .....................533
14.10.5 AnalysisofADMNNetwork .........................536
14.11 Improved Logical Neighborhood (ILN) . . . .....................539
14.11.1 RoutingAlgorithmforILNNetwork...................540
14.11.2 PathSelectionIssues................................542
14.11.3 AnalysisofILNNetwork ............................543
References . . . . ..................................................548
15 Switch Modeling ................................................551
15.1 Introduction . ..............................................551
xxx Contents
15.2 Input Queuing Switch . . . ...................................552
15.2.1 Congestion in Input Queuing Switch . . .................555
15.2.2 Performance Bounds on Input Queuing Switch ..........555
15.3 Output Queuing Switch . . ...................................558
15.3.1 Modeling the Input Buffer . . . . . . .....................559
15.3.2 Modeling the Output Queue . . . . . .....................561
15.3.3 Putting It All Together . . . ............................565
15.3.4 Performance Bounds on Output Queuing Switch . . . ......566
15.4 Shared Buffer Switch .......................................569
15.4.1 Performance Bounds on Shared Buffer Switch ..........572
15.5 Comparing the Three Switches . . . ............................574
15.6 Modeling Other Switch Types . . . . ............................576
References . . . . ..................................................578
16 Examples of Switches ............................................579
16.1 Introduction . ..............................................579
16.2 Promina 4000 Switch .......................................580
16.2.1 Input Port Operation . . . . ............................581
16.2.2 Backplane Bus Operation ............................581
16.2.3 OutputPortOperation...............................581
16.2.4 Promina 4000 Features . . ............................582
16.3 TheVRQSwitch ..........................................582
16.3.1 Input Port Operation . . . . ............................583
16.3.2 Backplane Bus Operation ............................583
16.3.3 OutputPortOperation...............................583
16.3.4 VRQ Features . . . ...................................584
16.4 Comparing Promina 4000 with VRQ Switch . . .................584
16.5 ModelingtheVRQSwitch ..................................585
16.5.1 Analysis of the Input Buffer . . . . . .....................587
16.5.2 Analysis of the Output Queue . . . .....................589
16.5.3 Putting It All Together . . . ............................590
16.5.4 Performance Bounds on VRQ Switch . .................591
References . . . . ..................................................595
A Summation of Series .............................................597
A.1 ArithmeticSeries ..........................................597
A.2 GeometricSeries...........................................597
A.3 Arithmetic–GeometricSeries ................................597
A.4 SumsofPowersofPositiveIntegers...........................598
A.5 BinomialSeries............................................598
A.5.1 Properties of Binomial Coefficients . . . .................599
A.6 OtherUsefulSeriesandFormulas ............................599
B Solving Difference Equations .....................................601
B.1 Introduction . ..............................................601
Contents xxxi
B.2 First-OrderForm...........................................601
B.3 Second-Order Form . .......................................602
B.3.1 Real and Different Roots α = β .......................603
B.3.2 Real and Equal Roots α = β .........................603
B.3.3 ComplexConjugateRoots ...........................603
B.4 General Approach . . . .......................................603
References . . . . ..................................................605
C Finding s(n)Usingthez-Transform ................................607
Reference . . . . . ..................................................611
D Vectors and Matrices ............................................613
D.1 Introduction . ..............................................613
D.2 Scalars . ..................................................613
D.3 Vectors...................................................613
D.4 ArithmeticOperationswithVectors ...........................614
D.5 Linear Independence of Vectors . . ............................615
D.6 Matrices..................................................615
D.7 Matrix Addition . . . . .......................................616
D.8 Matrix Multiplication .......................................616
D.9 InverseofaMatrix.........................................616
D.10 Null Space of a Matrix . . . ...................................617
D.11 TheRankofaMatrix.......................................618
D.12 EigenvaluesandEigenvectors................................618
D.13 Diagonalizing a Matrix . . ...................................619
D.14 Triangularizing a Matrix . ...................................619
D.15 Linear Equations . . . . .......................................620
D.15.1 GaussElimination ..................................621
D.15.2 Gauss–JordanElimination ...........................623
D.15.3 Row Echelon Form and Reduced Row Echelon Form . . . . . 625
D.16 Direct Techniques for Solving Systems of Linear Equations . ......627
D.16.1 GivensRotations ...................................627
D.17 Iterative Techniques . .......................................629
D.17.1 Jacobi Iterations . ...................................630
D.17.2 Gauss–Seidel Iterations . . ............................630
D.17.3 Successive Overrelaxation Iterations . . .................631
D.18 SimilarityTransformation ...................................631
D.19 Special Matrices . . . . .......................................632
D.19.1 CirculantMatrix....................................632
D.19.2 Diagonal Matrix . ...................................633
D.19.3 Echelon Matrix. . ...................................633
D.19.4 Identity Matrix . . ...................................634
D.19.5 Nonnegative Matrix . . . . . ............................634
D.19.6 Orthogonal Matrix . . . . . . ............................634
D.19.7 PlaneRotation(Givens)Matrix .......................635
xxxii Contents
D.19.8 Stochastic (Markov) Matrix . . . . . .....................635
D.19.9 Substochastic Matrix ................................635
D.19.10 Tridiagonal Matrix . . . . . . ............................636
D.19.11 Upper Hessenberg Matrix ............................636
Reference . . . . . ..................................................636
E Using MATLAB .................................................637
E.1 Introduction . ..............................................637
E.2 TheHelpCommand........................................637
E.3 NumbersinMATLAB......................................637
E.4 Basic Arithmetic Operations on Scalars . . . .....................639
E.5 Variables .................................................639
E.6 Arrays ...................................................640
E.7 NeatTricksforArrays ......................................640
E.8 Array–Scalar Arithmetic . ...................................641
E.9 Array–Array Arithmetic . . ...................................642
E.10 TheColonNotation ........................................642
E.11 AddressingArrays .........................................643
E.12 Matrix Functions. . . . .......................................644
E.13 M-Files(ScriptFiles).......................................645
E.14 Function M-Files . . . .......................................645
E.15 Statistical Functions . .......................................646
E.16 System of Linear Equations. . . . . . ............................648
E.16.1 A IsOverdetermined................................648
E.16.2 A Is Underdetermined . . . ............................649
E.16.3 b = 0 (Homogeneous Equations) . .....................649
E.17 Solution of Nonlinear Equations . . ............................649
E.18 Formatting Output . . .......................................650
Reference . . . . . ..................................................650
F Database Design ................................................651
F.1 Introduction . ..............................................651
F.2 Hashing ..................................................651
F.3 Trees.....................................................653
F.3.1 BinaryTrees.......................................653
F.3.2 Multiway Trees . ...................................654
F.3.3 B-Trees ...........................................655
Reference . . . . . ..................................................656
Index .............................................................657
Chapter 1
Probability
1.1 Introduction
The goal of this chapter is to provide a review of the principles of probability,
random variables, and distributions. Probability is associated with conducting a ran-
dom experiment or trial and checking the resulting outcome.
Definition 1.1 Outcome: An outcome is any possible observation of a random
experiment.
For example, the random experiment might be flipping a coin and the outcome
would be heads or tails depending on whether the coin lands face up or down. The
possible outcomes of a random experiment could be discrete or continuous. An
example of a random experiment with discrete outcomes is rolling a die since the
possible outcomes would be the numbers 1, 2, ... , 6. An example of a random
experiment with continuous outcomes is spinning a pointer and measuring its an-
gle relative to some reference direction. The angle we measure could be anything
between 0
◦
and 360
◦
.
Definition 1.2 Sample space: The collection of all possible, mutually exclusive
outcomes is called the sample space S.
For the random experiment of rolling a die, the sample space will be the set
S =
{
1, 2, 3, 4, 5, 6
}
.
This sample space is discrete since the possible outcomes were discrete. For the
example of spinning a pointer, the sample space is specified by the equation
S =
{
θ | 0
◦
≤ θ<360
◦
}
.
Definition 1.3 Event: An event is a set of outcomes sharing a common
characteristic.
In that sense, an event could correspond to one or several outcomes of an exper-
iment. An event could be thought of as a subset of the sample space S. On the other
hand, an outcome is an element of the subset space.
F. Gebali, Analysis of Computer and Communication Networks,
DOI: 10.1007/978-0-387-74437-7
1,
C
Springer Science+Business Media, LLC 2008
1
2 1 Probability
Definition 1.4 Event space: The event space is the collection of all possible,
mutually exclusive events of a random experiment.
In that sense, the event space is the partitioning of S into subsets that do not share
their elements.
For the case of die rolling experiment, we might be interested in the event E that
the outcome is an even number. Thus we can specify E: the number is even or
E:
the number is odd. In that case, there are six outcomes and two events. The event
space will be composed of two events
S =
E,
E
Another event could be that the outcome is less than or equal to 2, say. In that
case, there are two events again for the experiment—E: the number = 1 or 2 and
E: the number > 2. The event space will also consist of two events.
1.2 Applying Set Theory to Probability
We saw above that sets are used to describe aspects of random experiments such as
sample space, outcomes, and events. Table 1.1 shows the correspondence between
set theory terminology and probability definitions.
Assume A and B are two events in a random experiment. These two events might
be graphically shown using the Venn diagram of Fig. 1.1. The event defined as
any outcome that belongs to either A or B is called the union of A and B and is
represented by the expression
A ∪ B
Figure 1.1(a) shows the union operation as the shaded area.
The event defined as any outcome that belongs to both A and B is called the
intersection of A and B and is represented by the expression
A ∩ B
Figure 1.1(b) shows the intersection operation as the shaded area.
Table 1.1 Correspondence
between set theory and
probability definitions
Probability Set theory
Outcome Element of a set
Sample space S Universal set U
Event Set
Impossible event Null set ∅
1.2 Applying Set Theory to Probability 3
Fig. 1.1 Venn diagram for
two events A and B in a
sample space S.(a)The
union operation A ∪ B.(b)
The intersection operation
A ∩ B
(b)(a)
B
A
A
B
Definition 1.5 Complementary event: Given an event A,thecomplementary event
A is a set of all outcomes that do not belong to the set A.
Figure 1.2 shows that the universal set U is partitioned into two sets A and
A.
These two sets are not overlapping in the sense that there is not a single outcome
that belongs to both A and
A simultaneously.
We can write the following equations describing the operations on events.
A = U − A
A ∪
A = U
A ∩
A = Ø
De Morgan’s law for sets applies also for events and we can write
A ∩ B = A ∪ B
Example 1.1 Let U ={a, b, c, d, e, f, g, h, i, j, k}, A ={a, c, e, h, j},
and B ={c, d, e, f, k}. Find the events
1. A ∪ B
2. A ∩ B
Prove also that
A ∩ B = A ∪ B.
A ∪ B ={a, c, d, e, f, h, j, k}
A ∩ B ={c, e}
Fig. 1.2 Event A and its
complementary event
A
(b)(a)
A A
A
4 1 Probability
We also have
A ∩ B ={a, b, d, f, g, h, i, j, k}
A ={b, d, f, g, i, k}
B ={a, b, g, h, i, j}
A ∪ B ={a, b, d, f, g, h, i, j, k}
Hence De Morgan’s law is proved by direct counting.
Definition 1.6 Mutually exclusive events: Events A and B are said to be mutually
exclusive or disjoint events if they have no elements in common.
From that definition, we can write
A ∩ B = φ (1.1)
1.3 Counting Sample Space Points
In many discussions of probability, we need to determine the number of possible
outcomes of a given experiment or trial. The multiplication principle, permutations,
and combinations, to be discussed in the following sections, will prove useful.
1.4 The Multiplication Principle
The fundamental principle of counting is useful in finding the number of points in
the sample space. Suppose that the number of outcomes for doing experiment E
1
is
x and the number of outcomes for doing experiment E
2
is y. Then the number of
outcomes for doing experiment E
1
followed by experiment E
2
is the product xy.
Example 1.2 Assume there are 3 different ways for a data packet to travel through
network A and 15 different ways to travel through network B. Use the multiplication
principle to find the number of ways the packet could travel through network A
followed by network B.
The multiplication principle states that there are 3×15 or 45 ways for the packet
to travel through network A followed by network B.
We can generalize the multiplication principle as follows. Suppose that N
1
is the
number of outcomes for doing experiment E
1
, and N
2
is the number of outcomes for
doing experiment E
2
, ..., and N
n
is the number of outcomes for doing experiment
E
n
. The number of outcomes of performing experiments E
1
, E
2
, ..., E
n
is given by
the product
N = N
1
N
2
··· N
n