《data networks second edition P556》求取 ⇩

1INTRODUCTION AND LAYERED NETWORK ARCHITECTURE1

1.1Historical Overview1

1.1.1 Technological and Economic Background5

1.1.2 Communication Technology6

1.1.3 Applications of Data Networks7

1.2Messages and Switching9

1.2.1 Messages and Packets9

1.2.2 Sessions11

1.2.3 Circuit Switching and Store-and-Forward Switching14

1.3Layering17

1.3.1 The Physical Layer20

1.3.2The Data Link Control Layer23

The MAC sublayer24

1.3.3 The Network Layer25

The Internet sublayer28

1.3.4 The Transport Layer29

1.3.5 The Session Layer30

1.3.6 The Presentation Layer31

1.3.7 The Application Layer31

1.4A Simple Distributed Algorithm Problem32

Notes and Suggested Reading35

Problems35

2POINT-TO-POINT PROTOCOLS AND LINKS37

2.1 Introduction37

2.2The Physical Layer：Channels and Modems40

2.2.1 Filtering41

2.2.2 Frequency Response43

2.2.3 The Sampling Theorem46

2.2.4 Bandpass Channels47

2.2.5 Modulation48

2.2.6 Frequency-and Time-Division Multiplexing52

2.2.7 Other Channel Impairments53

2.2.8 Digital Channels53

ISDN54

2.2.9 Propagation Media for Physical Channels56

2.3Error Detection57

2.3.1 Single Parity Checks58

2.3.2 Horizontal and Vertical Parity Checks，58

2.3.3 Parity Check Codes59

2.3.4 Cyclic Redundancy Checks61

2.4ARQ：Retransmission Strategies64

2.4.1Stop-and-Wait ARQ66

Correctness of stop and wait69

2.4.2 Go Back n ARQ72

Rules followed by transmitter and receiver in go back n74

Correctness of go back n76

Go back n with modulus m＞n78

Efficiency of go back n implementations80

2.4.3Selective Repeat ARQ81

2.4.4 ARPANET ARQ84

2.5Framing86

2.5.1 Character-Based Framing86

2.5.2 Bit-Oriented Framing：Flags88

2.5.3 Length Fields90

2.5.4 Framing with Errors92

2.5.5 Maximum Frame Size93

Variable frame length93

Fixed frame length97

2.6Standard DLCs97

2.7Initialization and Disconnect for ARQ Protocols103

2.7.1 Initialization in the Presence of Link Failures103

2.7.2 Master-Slave Protocol for Link Initialization104

2.7.3 A Balanced Protocol for Link Initialization107

2.7.4 Link Initialization in the Presence of Node Failures109

2.8Point-to-Point Protocols at the Network Layer110

2.8.1Session Identification and Addressing111

Session identification in TYMNET112

Session identification in the Codex networks113

2.8.2Packet Numbering Window Flow Control and Error Recove114

Error recovery115

Flow control116

Error recovery at the transport layer versus the network layer117

2.8.3 The X.25 Network Layer Standard118

2.8.4 The Internet Protocol120

2.9The Transport Layer123

2.9.1 Transport Layer Standards123

2.9.2 Addressing and Multiplexing in TCP124

2.9.3 Error Recovery in TCP125

2.9.4 Flow Control in TCP/IP127

2.9.5 TP Class 4128

2.10 Broadband ISDN and the Asynchronous Transfer Mode128

2.10.1 Asynchronous Transfer Mode（ATM）132

2.10.2 The Adaptation Layer135

Class 3（connection-oriented）traffic136

Class 4（connectionless）traffic137

Class 1 and 2 traffic137

2.10.3 Congestion138

Summary139

Notes，Sources，and Suggested Reading140

Problems141

3DELAY MODELS IN DATA NETWORKS149

3.1Introduction149

3.1.1 Multiplexing of Traffic on a Communication Link150

3.2Queueing Models：Little’s Theorem152

3.2.1 Little’s Theorem152

3.2.2 Probabilistic Form of Little’s Theorem154

3.2.3 Applications of Little’s Theorem157

3.3The M/M/1 Queueing System162

3.3.1 Main Results164

Arrival statistics—the Poisson process164

Service statistics165

Markov chain formulation166

Derivation of the stationary distribution167

3.3.2 Occupancy Distribution upon Arrival171

3.3.3 Occupancy Distribution upon Departure173

3.4The M/M/m，M/M/∞，M/M/m/m，and Other Markov Systems173

3.4.1 M/M/m：The m-Server Case174

3.4.2 M/M/∞：The Infinite-Server Case177

3.4.3 M/M/m/m：The m-Server Loss System178

3.4.4 Multidimensional Markov Chains：Applications in Circuit Switching180

Truncation of independent single-class systems182

Blocking probabilities for circuit switching systems185

3.5The M/G/1 System186

3.5.1 M/G/1 Queues with Vacations192

3.5.2 Reservations and Polling195

Single-user system196

Multi-user system198

Limited service systems201

3.5.3 Priority Queueing203

Nonpreemptive priority203

Preemptive resume priority205

3.5.4 An Upper Bound for the G/G/1 System206

3.6Networks of Transmission Lines209

3.6.1 The Kleinrock Independence Approximation211

3.7 Time Reversibility—Burke’s Theorem214

3.8Networks of Queues—Jackson’s Theorem221

Heuristic explanation of Jackson’s Theorem227

3.8.1Extensions of Jackson’s Theorem229

State-dependent service rates229

Multiple classes of customers230

3.8.2 Closed Queueing Networks233

3.8.3 Computational Aspects—Mean Value Analysis238

Summary240

Notes，Sources，and Suggested Reading241

Problems242

Appendix A：Review of Markov Chain Theory259

3A.1Discrete-Time Markov Chains259

3A.2 Detailed Balance Equations261

3A.3 Partial Balance Equations262

3A.4 Continuous-Time Markov Chains262

3A.5 Drift and Stability264

Appendix B：Summary of Results265

4MULTIACCESS COMMUNICATION271

4.1Introduction271

4.1.1 Satellite Channels273

4.1.2 Multidrop Telephone Lines274

4.1.3 Multitapped Bus274

4.1.4 Packet Radio Networks275

4.2Slotted Multiaccess and the Aloha System275

4.2.1Idealized Slotted Multiaccess Model275

Discussion of assumptions276

4.2.2 Slotted Aloha277

4.2.3 Stabilized Slotted Aloha282

Stability and maximum throughput282

Pseudo-Bayesian algorithm283

Approximate delay analysis284

Binary exponential backoff286

4.2.4 Unslotted Aloha287

4.3Splitting Algorithms289

4.3.1 Tree Algorithms290

Improvements to the tree algorithm292

Variants of the tree algorithm293

4.3.2 First-Come First-Serve Splitting Algorithms293

Analysis of FCFS splitting algorithm297

Improvements in the FCFS splitting algorithm301

Practical details302

Last-come first-serve（LCFS）splitting algorithm302

Delayed feedback303

Round-robin splitting304

4.4Carrier Sensing304

4.4.1 CSMA Slotted Aloha305

4.4.2 Pseudo-Bayesian Stabilization for CSMA Aloha307

4.4.3 CSMA Unslotted Aloha309

4.4.4 FCFS Splitting Algorithm for CSMA310

4.5Multiaccess Reservations312

4.5.1 Satellite Reservation Systems313

4.5.2 Local Area Networks：CSMA/CD and Ethernet317

Slotted CSMA/CD317

Unslotted CSMA/CD318

The IEEE 802 standards320

4.5.3 Local Area Networks：Token Rings320

IEEE 802.5 token ring standard323

Expected delay for- token rings324

FDDI326

Slotted rings and register insertion rings330

4.5.4Local Area Networks：Token Buses and Polling331

IEEE 802.4 token bus standard332

Implicit tokens：CSMA/CA333

4.5.5 High-Speed Local Area Networks333

Distributed queue dual bus（IEEE 802.6）335

Expressnet339

Homenets341

4.5.6 Generalized Polling and Splitting Algorithms342

4.6Packet Radio Networks344

4.6.1 TDM for Packet Radio Nets346

4.6.2 Collision Resolution for Packet Radio Nets347

4.6.3 Transmission Radii for Packet Radio349

4.6.4 Carrier Sensing and Busy Tones350

Summary351

Notes，Sources，and Suggested Reading352

Problems353

5ROUTING IN DATA NETWORKS363

5.1Introduction363

5.1.1 Main Issues in Routing365

5.1.2 Wide-Area Network Routing：An Overview367

Flooding and broadcasting368

Shortest path routing370

Optimal routing372

Hot potato（deflection）routing schemes372

Cut-through routing373

ARPANET：An example of datagram routing374

TYMNET：An example of virtual circuit routing376

Routing in SNA378

Routing in circuit switching networks379

5.1.3 Interconnected Network Routing：An Overview379

Bridged local area networks382

Spanning tree routing in bridged local area networks383

Source routing in bridged local area networks385

5.2Network Algorithms and Shortest Path Routing387

5.2.1 Undirected Graphs387

5.2.2 Minimum Weight Spanning Trees390

5.2.3 Shortest Path Algorithms393

The Bellman-Ford algorithm396

Bellman’s equation and shortest path construction399

Dijkstra’s algorithm401

The Floyd-Warshall algorithm403

5.2.4 Distributed Asynchronous Bellman-Ford Algorithm404

5.2.5Stability of Adaptive Shortest Path Routing Algorithms410

Stability issues in datagram networks410

Stability issues in virtual circuit networks414

5.3Broadcasting Routing Information：Coping with Link Failures418

5.3.1 Flooding：The ARPANET Algorithm420

5.3.2 Flooding without Periodic Updates422

5.3.3 Broadcast without Sequence Numbers425

5.4Flow Models，Optimal Routing，and Topological Design433

5.4.1 Overview of Topological Design Problems437

5.4.2 Subnet Design Problem439

Capacity assignment problem439

Heuristic methods for capacity assignment442

Network reliability issues445

Spanning tree topology design447

5.4.3 Local Access Network Design Problem448

5.5Characterization of Optimal Routing451

5.6Feasible Direction Methods for Optimal Routing455

5.6.1 The Frank-Wolfe（Flow Deviation）Method458

5.7Projection Methods for Optimal Routing464

5.7.1 Unconstrained Nonlinear Optimization465

5.7.2 Nonlinear Optimization over the Positive Orthant467

5.7.3 Application to Optimal Routing468

5.8 Routing in the Codex Network476

Summary477

Notes，Sources，and Suggested Reading478

Problems479

6FLOW CONTROL493

6.1Introduction493

6.1.1 Means of Flow Control494

6.1.2 Main Objectives of Flow Control496

Limiting delay and buffer overflow496

Fairness498

6.2Window Flow Control500

6.2.1End-to-End Windows501

Limitations of end-to-end windows502

6.2.2 Node-by-Node Windows for Virtual Circuits506

6.2.3 The Isarithmic Method508

6.2.4 Window Flow Control at Higher Layers508

6.2.5 Dynamic Window Size Adjustment510

6.3Rate Control Schemes510

Queueing analysis of the leaky bucket scheme513

6.4Overview of Flow Control in Practice515

Flow control in the ARPANET515

Flow control in the TYMNET517

Flow control in SNA517

Flow control in a Codex network518

Flow control in the PARIS network518

Flow control in X.25519

6.5Rate Adjustment Algorithms519

6.5.1 Combined Optimal Routing and Flow Control519

6.5.2 Max-Min Flow Control524

Summary530

Notes，Sources，and Suggested Reading530

Problems531

REFERENCES537

INDEX552