Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

656 F Database Design

Operations on a B-tree such as search, insertion, and deletion can be found in [4].

In the worst case, the root node will have only one key and all other nodes will have

m − 1 keys and m children. In that case, the number of entries in the table N will

depend on the tree height according to the following table [5]:

Tree height Number of keys

21+m

31+m +mc

41+m +mc + mc

h 1 +m



h−2

i=0

= c

h−1

−1

Reference

1. A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data Structures and Algorithms, Addison-Wesley,

Reading, Massachusetts, 1983.

2. R. Sedgewick, Algorithms, Addison-Wesley, Reading, Massachusetts, 1984.

3. S. Baase, Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1983.

4. http://www.semaphorecorp.com/btp/algo.html.

5. N. Alechina, “B-Trees”, http://www.cs.nott.ac.uk/ nza/G5BADS/l14.html

Index

Access probability (p

), queuing analysis, see

Efficiency (␩), queuing analysis

Algorithms, scheduling, 431, 463–464

analysis of, 437

bit dropping probability p

, 465–466

core-stateless fair queuing (CSFQ),

463–464

bit dropping probability p

, 465–466

fair rate f, 465

packet arrival rate (λ

), 464–465

fair queuing (FQ), 451–454

fair rate f, 465

fair sharing policy, 432

first-in/first-out (FIFO), 437–438

queuing analysis of FIFO/FCFS,

438–439

frame-based fair queuing (FFQ), 459

completion times calculation for,

461–463

system potential calculation, 460

timestamp calculation, 460–461

generalized processor sharing (GPS),

449–451

Max–Min fairness scheduling, 446–448

packet arrival rate (λ

), 464–465

packet-by-packet GPS (PGPS), 454

completion time calculation for

PGPS/WFQ, 457–459

finish number calculation for

PGPS/WFQ, 456

virtual time calculation for PGPS/WFQ,

454–456

packet drop options, 467

packet dropping policy, 431

packet selection policy, 431

processor sharing (PS), 448–449

random early detection (RED), 466–467

rate-based versus credit-based

scheduling, 436

round robin scheduler (RR), 439–440

queuing analysis for RR, 441–444

scheduler design issues, 434

degree of aggregation, 435

packet drop policy, 436

priority, 435

work-conserving versus nonwork-

conserving, 435–436

scheduler location in switches, 432–434

scheduler performance measures, 437

scheduling and medium access control, 434

scheduling as optimization problem, 432

static priority (SP) scheduler, 439

weighted round robin scheduler (WRR),

444–445

queuing analysis for WRR, 445–446

ALOHA, 329–330

channel, 331

contention problem, 329, 330

modeling network, 330–331

performance, 332–335

slotted, 335

modeling network, 335–337

performance, 337–340

state transition diagram for, 331

wireless channel, states

collided, 336

idle, 335

transmitting, 336

Arithmetic–geometric series, 597–598

Arithmetic series, 597

Augmented data manipulator network

(ADMN), 527–528

analysis of, 536–539

first routing algorithm, 529–530, 529–531

alternative route, 530–531

routing algorithms, 529

657

658 Index

Augmented data manipulator network (cont.)

second routing algorithm, 531–533

alternative route, 533

third routing algorithm, 533–535, 533–536

alternative route, 535–536

Autocorrelation function, 54–55, 383

Autocovariance function, 58, 409

Automatic-repeat-request (ARQ)

techniques, 303

Autoregressive models, 387

Balance equations, 142

Banyan network, 523–524

analysis, 524–527

routing algorithm for, 524

Bernoulli traffic

discrete-time modeling: interarrival time

for, 398–401

extracting parameters, 404–405

memoryless property of, 402

queuing analysis, 405–407

realistic models for, 401, 403–404

Binary trees, 653–654

Binomial coefficient, 8

Binomial series, 598

properties of, 599

B-trees (Balanced tree), 655–656

Butterfly function, 517

Canonic form, 153

Carrier sense multiple access-collision

avoidance (CSMA/CA), 345–346

model assumptions, 346–347

protocol performance, 348–350

state transition diagram, 347

cdf, see Cumulative distribution

function (cdf)

Circuit switching, 481, 482–483

characteristics, 482

establishing path in, 482–483

Circulant matrix, 197

Code division multiple access (CDMA)

media access techniques, 481

Column stochastic matrix, see Markov

matrices

Combinations, 8

Complementary event, 3

Complexity, network hardware, 508

Continuous-time modeling: Poisson traffic

description, 387–389

extracting Poisson traffic parameters,

394–395

flow description, 392

interarrival time description, 392–394

memoryless property of Poisson traffic,

389–391

Poisson traffic and queuing analysis,

395–398

realistic models for Poisson traffic, 391

Core router, 464

Core-stateless fair queuing (CSFQ), 463–464

bit dropping probability (p

), 465–466

core router, 464

edge router, 464

fair rate f, 465

packet arrival rate (λ

), 464–465

scheduling algorithms, 463–464

bit dropping probability p

, 465–466

fair rate f, 465

packet arrival rate (λ

), 464–465

Core switches, 478

Correlation

coefficient, 34

matrix, 59–60

between 2 random variables, 34

Covariance

function, 58–59

matrix, 60–62

Crossbar switches, 511

Cross-correlation function, 57

orthogonal, 57

statistically independent processes, 57

Cross-covariance function, 58

uncorrelated, 58

CSMA access strategies, 341

Cube function, 517

Cumulative distribution function (cdf), 11–12

for continuous random variable, 12

for discrete random variable, 12

Database design, 651

hashing, 651–653

trees, 653

binary trees, 653–654

B-trees, 655–656

multiway trees, 654–655

Datagram switching, 483

DeMoivre-Laplace Theorem, 26

Deterministic process, 52

Difference equations, solving, 601

first-order form, 601–602

general approach, 6–3–605

second-order form, 602–603

complex conjugate roots, 603

Index 659

real and different roots, 603

real and equal roots, 603

Distribution index, 129

Distribution vector, 70

D/M/1/B queue, 253–256

efficiency, 256

performance, 256–257

relation of queue states, 254

state transition diagram for

discrete-time, 254

Early drop schedulers, 466

Edge router, 464

Edge switches, 478

Efficiency (␩), queuing analysis, 226

Eigenvalues, 618

Eigenvectors, 618

EIG (MATLAB function), 637

help eig, 638

EIGPOWERS (MATLAB function), 87, 159

End-nodes, 477, 484

Ensemble average, 53

Error control protocols, modeling, 303

go-back-N (GBN ARQ) protocol, 308

algorithm for finding s by

iterations, 313

modeling, 309–312

performance, 314–315

using iterations to find s, 312–313

selective-repeat (SR ARQ) protocol, 316

modeling, 316–319

performance, 320–321

stop-and-wait ARQ (SW ARQ) protocol,

303–304

modeling, 305–306

performance, 306–308

Event, 1

space, 2

Exchange function, 517

Exponential process, 52

Factorial(n) (MATLAB function), 5–6

Fair queuing (FQ), 451–454

Fair sharing policy, 432

First-come/first-served (FCFS), see

First-in/first-out (FIFO)

First-in/first-out (FIFO), 437–438

queuing analysis of FIFO/FCFS, 438–439

Flow traffic models, 384

autoregressive models, 387

Markov modulated Poisson process,

386–387

modulated Poisson processes, 384–385

on–off model, 385–386

Frame-based fair queuing (FFQ), 459

completion times calculation for, 461–463

computation of three quantities, 459

scheduling algorithms, 459

system potential calculation, 460

timestamp calculation, 460–461

Frequency division multiple access

(FDMA), 481

media access techniques, 481

Fundamental law of probabilities, 36

Gateway, 486

Gauss elimination, 621–623

Gauss–Jordan elimination, 623–625

Gauss–Seidel iterations, 630–631

GBN ARQ protocol, see Go-back-N (GBN

ARQ) protocol

GCN, see Generalized-cube network (GCN)

Generalized-cube network (GCN), 518–519

analysis of, 521–523

routing algorithm for, 519–520

Generalized processor sharing (GPS), 449–451

Geometric series, 597

Givens rotations, 627–629

Go-back-N (GBN ARQ) protocol, 308

algorithm for finding s by iterations, 313

modeling, 309–312

performance, 314–315

using iterations to find s, 312–313

Hash function, 651

Hashing, 651–653

storage of data, 652

Head of line (HOL) packets, 552, 565

Heavy-tailed distributions, 409

Homogeneous system of linear equations, 140

Hub, 485

See also individual types of Hub

Hurst parameter, 410

IEEE 802.11

DCF function for ad hoc wireless

LANs, 351

final remarks, 360–361

medium access control, 351–352

model assumptions, 352–356

protocol performance, 356–360

frame structure for, protocol using PCF

function, 361

660 Index

IEEE 802.11 (cont.)

MAC scheme, 353

modeling backoff counters, 353

PCF function for infrastructure wireless

LANs, 361–362

IEEE 802.11: 1-persistent PCF,

366–369

IEEE 802.11e: quality of service

support, 374–378

medium access control, 362

nonpersistent PCF model assumptions,

362–364

nonpersistent PCF protocol

performance, 364–366

1-persistent IEEE 802.11/PCF

performance, 369–371,

371–374

IEEE 802.3 model

assumptions, 341–342

state transition diagram, CSMA/CD

channel, 343

IEEE 802.1p: Static Priority Protocol,

modeling, 326–329

assumptions, 326

flows into and out of each queue, 327

IEEE Standard 802.3 (CSMA/CD),

340–341

model assumptions, 341–342

protocol performance, 343–345

state transition diagram, 342–343

IEEE standard 802.1p: static priority

protocol, 326

Improved logical neighborhood (ILN),

539–540

analysis of, 543–545

paths chosen in, 541

path selection issues, 542

routing algorithm, 540–542

Input queuing switch, 552–555

arrival and departure probabilities, 553

assumptions for analysis of, 552

congestion in, 555

efficiency of, 554

performance bounds on, 555–558

Intelligent hub, 485

Interconnection networks, 507

augmented data manipulator network

(ADMN), 527–528

analysis of, 536–539

first routing algorithm, 529–531

routing algorithms for, 529

second routing algorithm, 531–533

third routing algorithm, 533–536

Banyan network, 523–524

analysis of, 524–527

routing algorithm for, 524

classification of networks, 509

crossbar network, 511–512

analysis of, 512–515

contention and arbitration, 512

generalized-cube network (GCN), 518–519

analysis of, 521–523

routing algorithm for, 519–520

improved logical neighborhood (ILN),

539–540

analysis of, 543–545

path selection issues, 542

routing algorithm for, 540–542

multistage interconnection networks,

515–516, 517–518

network design parameters, 507

network hardware, 508

network performance, 507–508

scalability issues, 508–509

space division switching, 510

time division multiple access (TDMA), 509

random assignment, 510

static-assignment, 509–510

Interconnection networks, multistage, 515–516

Internet traffic archive (http://ita.ee.lbl.gov/

index.html), 384

Intersection (set), 2

Inverse shuffle function, 517

Irreducible Markov chain, 151, 152

Iterative techniques, 629

Gauss–Seidel iterations, 630–631

Jacobi iterations, 630

successive overrelaxation iterations, 631

Jacobi iterations, 630

Jordan canonic form (JCF), 103–106

finding s(n), 103–106

properties, 106–107

properties of, 106–107

Kendall’s notation, 224–225

Leaky bucket algorithm, 269–271

control of data rate by, 271

events of packet arrival and departure, 276

leaky bucket buffer, 270–271

modeling, 271–272

multiple arrival/single departure model

/M/1/B), 276–278

Index 661

performance

M/M/1/B case, 274–276

/M/1/B case, 278–280

single arrival/single departure model

(M/M/1/B), 272–273

Linear equations, 620–621

direct techniques for solving systems

of, 627

givens rotations, 627–629

Gauss elimination, 621–623

Gauss–Jordan elimination, 623–625

homogeneous system of, 140

MATLAB system of, 648–649

row echelon form and reduced row echelon

form, 625–627

Links, 477

Local-area networks (LANs), 223, 479

wired, 340

Lookup table design, 489–490

MAC scheme

IEEE 802.11, 353

modeling backoff counters, 353

Markov chains, 65–66

assumptions for, 128

eigenvalues and eigenvectors of P, 79–81

expanding P

in terms of its eigenvalues,

94–102

test for matrix diagonalizability,

102–103

expressing P

in terms of eigenvalues,

109–111

finding P

using Z-transform, 111

finding s(n), 85–86

finding s(n) by diagonalizing P, 91–92

comparing diagonalization with

expansion of s(0), 92–94

finding s(n) by expanding s(0), 86–91

finding s(n) using Jordan canonic form,

103

Jordan canonic form (JCF), 103–106

properties of JCF, 106–107

homogeneous, 123

equation, 69

identification of, 216

nonperiodic Markov chain, 216

strongly periodic, 217

weakly periodic, 217

involving three states, 72

irreducible, 151

Markov matrices, 75–78

diagonals of P, 78

matrix U, properties of, 107

memoryless property of, 68–69

model of network of interdependent, 261

periodic classes of, 184

Expressed in Jordan canonic form,

108–109

reducible, 151

renaming states, 111–112

selection of time step, 66

continuous-time, 66

discrete-time, 66–68

solution for communicating, 263–264

state of sender as, 305, 317

state transition diagram, 73, 127

for CSMA/CD channel, 74

state transition matrix P, constructing,

81–82

systems of communicating, 260–263

general solution for, 263–264

transient behavior, 82–85

properties of P

,85

transition matrix, 69–75

Markov chains at equilibrium, 123

balance equations, 142

finding s

difference equations, 127–130

direct techniques, 140–141

eigenvector approach, 126–127

forward- or back-substitution, 137–139

iterative techniques, 141

Z-transform, 130–137

finding steady-state distribution vector s,

124–125

significance of s at “steady state,” 123–124

techniques for finding s, 125–126

algebraic and numerical techniques, 125

Markov matrices, 75–78

diagonals of P, 78

Markov process, 65

examples, 65

Markov property, 68

MATLAB, 637

arrays, 640

addressing, 643

array–array arithmetic, 642

array–scalar arithmetic, 641

colon notation, 642

commands, 645

features of, 639–640

format compact (formatting output), 650

formatting numbers, 638

formatting output, 650

function M-files, 645–646

662 Index

MATLAB (cont.)

help command, 637

hist function, 647

matrix functions, 644

M-files (script files), 645

neat tricks for arrays, 640–641

numbers in, 637–639

number types, 638

RAND and RANDN, 646

rand function, 647

scalars

arithmetic operations on, 639

basic operations for, 639

statistical functions, 646–648

system of linear equations, 648–649, 649

variables, 639–640

Matrices, 615

addition, 616

circulant, 632–633

coefficient, 615

correlation, 59–60

covariance, 60–62

diagonal, 633

diagonalizing, 619

echelon, 633–634

elementary, 621

identity, 634

inverse of, 616–617

left inverse, 616

right inverse, 616

multiplication, 616

nonnegative, 634

null space of, 617

orthogonal, 634–635

plane rotation (givens), 635

rank of, 618

row echelon form, 625

stochastic (Markov), 635

substochastic, 635–636

triangularizing, 619–620

tridiagonal, 636

upper Hessenberg, 636

Max–Min fairness scheduling, 446–448

M/D/1/B queue, 257–259

performance, 259–260

relation of queue states, 258

state transition diagram for

discrete-time, 257

Medium access control (MAC) protocols, 325

ALOHA, 329–330

modeling network, 330–331

performance, 332–335

carrier sense multiple access-collision

avoidance (CSMA/CA), 345–346

model assumptions, 346–347

protocol performance, 348–350

IEEE 802.11: DCF Function for Ad Hoc

Wireless LANs, 351

final remarks, 360–361

medium access control,

351–352

model assumptions, 352–356

protocol performance, 356–360

IEEE 802.11: PCF function for

infrastructure wireless LANs,

361–362

IEEE 802.11: 1-persistent PCF,

366–369

IEEE 802.11e: quality of service

support, 374–378

medium access control, 362

nonpersistent PCF model assumptions,

362–364

nonpersistent PCF protocol perfor-

mance, 364–366

1-persistent IEEE 802.11/PCF

performance, 369–371

1-persistent IEEE 802.11/PCF user

performance, 371–374

IEEE Standard 802.3 (CSMA/CD),

340–341

model assumptions, 341–342

protocol performance, 343–345

state transition diagram, 342–343

IEEE standard 802.1p: static priority

protocol, 326

modeling, 326–329

slotted ALOHA, 335

modeling network, 335–337

performance, 337–340

M/M/1/B queue, 225, 233–235

average queue size versus distribution

index ρ, 237

efficiency, 236

performance, 235–240

bounds on, 240–241

queue performance, 235–240

input traffic, 235–236

throughput or output traffic, 235

state transition diagram for discrete-time,

233–234

throughput, 235

M/M/J/B queue, 225

M/M

/1/B queue, 225, 248–249

alternative solution method, 253

Index 663

efficiency of, 249

performance, 249–252

performance bounds, 252–253

/M/1/B queue, 225, 241–242

alternative solution method, 247

efficiency, 243

performance, 242–246

performance bounds on, 246–247

stability of queue, 241

M/M/1 queue, 225, 227–230

average queue size versus distribution

index ρ, 225, 227–230

continuous-time, 230

for discrete-time

state transition diagram, 228

efficiency of, 230, 231

example, 227

performance, 230–233

queue performance, 230–233

throughput, 231

throughput for, 230–231

Modeling network traffic, 383–384

continuous-time modeling: Poisson traffic

description, 387–389

extracting Poisson traffic parameters,

394–395

flow description, 392

interarrival time description, 392–394

memoryless property of Poisson traffic,

389–391

Poisson traffic and queuing analysis,

395–398

realistic models for Poisson traffic, 391

destination statistics, 420

broadcast traffic, 420–421

hot-spot traffic, 421–422

uniform traffic, 420

discrete-time modeling: interarrival time

for Bernoulli traffic, 398–401

extracting parameters, 404–405

memoryless property of, 402

queuing analysis, 405–407

realistic models for, 401, 403–404

flow traffic models, 384

autoregressive models, 387

Markov modulated Poisson process,

386–387

modulated Poisson processes, 384–385

on–off model, 385–386

heavy-tailed distributions, 409

interarrival time traffic modeling with

arbitrary source distribution,

418–420

packet length statistics, 422–423

packet transmission error description,

423–425

Pareto traffic distribution, 409–411

extracting Pareto interarrival time

statistics, 412–414

flow description, 411

interarrival time description, 411–412

queuing analysis, 414–417

self-similarity and random processes,

408–409

self-similar traffic, 407–408

traffic data rate modeling with arbitrary

source distribution, 417–418

Modeling traffic flow control protocols, 269

leaky bucket algorithm, 269–271

modeling leaky bucket algorithm,

271–272

multiple arrival/single departure model

/M/1/B), 276–278

performance (M/M/1/B case),

274–276

performance (M

/M/1/B case),

278–280

single arrival/single departure model

(M/M/1/B), 272–273

token bucket algorithm, 280–281

modeling, 282

multiple arrivals/single departures

model (M

/M/1/B), 288–291

single arrival/single departures model

(M/M/1/B), 282–285

token bucket performance (M/M/1/B

case), 285–288

token bucket performance (multiple

arrival/departure case), 291–295

virtual scheduling (VS) algorithm, 295–296

modeling, 296–297

protocol performance, 298–299

Multiplication principle, probability, 4–5

Multistage interconnection networks, 515–516,

517–518

classification, 516

factors determining MIN complexity, 516

N × N multistage interconnection

network, 516

Mutually exclusive events, 4

Network, delay of, 514

Network design parameters, 507

network hardware, 508

network performance, 507–508

scalability issues, 508–509

664 Index

Network design parameters, interconnection

networks, 507

network hardware, 508

network performance, 507–508

scalability issues, 508–509

Network hardware, 508

Network Processing Unit (NPU),

487–488

examples of tasks, 487–488

switch incorporating, components, 488

Nondeterministic process, 53

Nonlinear equations, solution of, 649

FMINBND, 649

FMINSEARCH, 649

FZERO, 649

Nonperiodic Markov chain, 185, 216

Null (MATLAB function), 617

On–off model, 385–386

packet pattern for, 385

Outcome, 1

Output queuing switch, 558–559

assumptions for analysis of, 558

modeling input buffer, 559–561

modeling output queue, 561–562

output queue performance, 563–565,

566–569

transition matrix, 562–563

Packet buffer

Markov chain transition diagram, 284

state of occupancy, 283–284, 290

Packet-by-packet GPS (PGPS), 454

completion time calculation for

PGPS/WFQ, 457–459

finish number calculation for

PGPS/WFQ, 456

virtual time calculation for PGPS/WFQ,

454–456

Packet-by-packet GPS (PGPS), computation of

three quantities, 464

Packet drop options, 467

Packet dropping policy, 431

Packet length statistics, 422–423

Packet selection policy, 431

Packet switching, 481, 483–484

bridge, 485

end-node, 484

gateway, 486

hardware, 484

hub, 485

penalties, 483

router, 486

switch, 485–486

Packet transmission error description, 423–425

Pareto traffic distribution, 409–411

extracting Pareto interarrival time statistics,

412–414

flow description, 411

interarrival time description, 411–412

queuing analysis, 414–417

Passive hub, 485

Periodic Markov chains, 183–184, 184–185

asymptotic behavior, 213–216

canonic form for P, 196–197

composite strongly, 198–202

eigenvalues of reducible, 209

identification of Markov chains, 216

nonperiodic Markov chain, 216

strongly periodic, 217

weakly periodic, 217

intuitive examples

population of wild salmon, 183, 184

predator–prey relation, 183, 184

reducible, 208–211

states divided into groups and transitions

between adjacent groups, 184

strongly, 185, 217

transient analysis, 211–213

transition diagram, 197–198

for composite strongly, 198

transition matrix, 185–187

determinant, 187–188

diagonalization, 188–191

eigenvalues, 191–195

elements, 195–196

types, 185

weakly, 185, 202–208, 217

Permutations, 5

n distinct objects taken k at a time, 6

n distinct objects taken n at a time, 5–6

of objects in groups, 6–7

Plus–Minus 2

(PM2I) function, 517

Poisson distribution, expression for, 391

Poisson processes, 52

flow traffic models

Markov modulated, 386–387

modulated, 384–385

random processes, 52

Poisson source, exponential distribution

instantaneous rate of, 392

Poisson Theorem, 26–27

Poisson traffic description, 387–389

extracting Poisson traffic parameters,

394–395

Index 665

flow description, 392

interarrival time description, 392–394

memoryless property of Poisson traffic,

389–391

Poisson traffic and queuing analysis,

395–398

realistic models for Poisson traffic, 391

Position parameter, 403

Positive integers, sums of powers of, 598

Power consumption , network hardware, 508

Probability, 1–2, 8

applying set theory to, 2–4

axioms of, 9

Bernoulli (binary) RV, 23–24

binomial RV, 25–26

approximating binomial distribution,

26–27

combinations, 8

common continuous RVs, 16

common discrete RVs, 21

continuous uniform (flat) RV, 16–17

correlation, 34

counting sample space points, 4

covariance, 34–35

cumulative distribution function (cdf),

11–12

cdf in discrete case, 12

discrete uniform RV, 21–22

expected value, 33

and variance, 14–15

exponential RV, 19

Gaussian RV, 18

generating random numbers, 39

importance sampling method, 41

inversion method, 39–40

rejection method, 40–41

uniform distribution, 39

geometric RV, 24–25

individual Pmf from given joint Pmf,

32–33

joint cdf and pdf, 31–32

mass function, 13–14

for discrete random variables, 14

multiplication principle, 4–5

Pareto RV, 19–21

permutations, 5

n distinct objects taken k at a time, 6

n distinct objects taken n at a time,

5–6

of objects in groups, 6–7

Poisson RV, 28–30

Poisson Distribution from binomial

distribution, 29–30

probability density function (pdf), 13

random variables, 10–11

systems with many, 30

random variables, transforming, 35

continuous case, 35–38

discrete case, 38

relationships, 9–10

variance, 34