《data networks P486》求取 ⇩

Chapter 1INTRODUCTION AND LAYERED NETWORKARCHITECTURE1

1.1Historical Overview,1

1.1.1 Technological and Economic Background,4

1.1.2 Communication Technology,5

1.1.3 Applications of Data Networks,6

1.2Messages and Switching,8

1.2.1 Messages and Packets,8

1.2.2 Sessions,9

1.2.3 Circuit Switching and Store and Forward Switching,11

1.3Layering,14

1.3.1 The Physical Layer,17

1.3.2 The Data Link Control （DLC） Layer,20

1.3.3 The Network Layer,22

1.3.4 The Transport Layer,24

1.3.5 The Session Layer,25

1.3.6 The Presentation Layer,25

1.3.7 The Application Layer,26

1.4 A Simple Distributed Algorithm Problem,26

1.5 Notes and Suggested Reading,29

Chapter 2DATA LINK CONTROL AND COMMUNICATIONCHANNELS31

2.1 Overview,31

2.2The Physical Layer: Channels and Modems,34

2.2.1 Filtering,35

2.2.2 Frequency Response,37

2.2.3 The Sampling Theorem,40

2.2.4 Bandpass Channels,42

2.2.5 Modulation,43

2.2.6 Frequency- and Time-Division Multiplexing,47

2.2.7 Other Channel Impairments,48

2.2.8 Digital Channels,48

2.2.9 Propagation Media for Physical Channels,49

2.3Error Detection,50

2.3.1 Single Parity Checks,50

2.3.2 Horizontal and Vertical Parity Checks,51

2.3.3 Parity Check Codes,52

2.3.4 Cyclic Redundancy Checks,54

2.4ARQ—Retransmission Strategies58

2.4.1 Stop-and-Wait ARQ,59

2.4.2 ARPANET ARQ,62

2.4.3Go Back n ARQ,63

Rules Followed by Sending DLC,66

Rules Followed by Receiving DLC,67

Go Back n with Modulus m ＞ n,68

Efficiency of Go Back n Implementations,70

2.4.4 Selective Repeat ARQ,71

2.5Framing,73

2.5.1 Character-Based Framing,75

2.5.2 Bit-Oriented Framing—Flags,76

2.5.3 Length Fields,79

2.5.4 Framing with Errors,80

2.5.5 Maximum Frame Size,82

2.6 Standard DLCs,85

2.7Session Identification and Addressing,91

2.7.1 Session Identification in TYMNET,92

2.7.2 Session Identification in the Codex Networks,94

2.8Error Recovery at the Network and Transport Layer,95

2.8.1 End-to-End acks, Flow Control, and Permits,96

2.8.2 Using End-to-End acks for Error Recovery,98

2.8.3 The X.25 Network Laver Standard99

2.9 Summary,101

2.10 Notes, Sources, and Suggested Reading,102

PROBLEMS,103

Chapter 3DELAY MODELS IN DATA NETWORKS111

3.1Introduction,111

3.1.1 Multiplexing of Traffic on a Communication Link,112

3.2 Queueing Models—Little’s Theorem,114

3.3TheM/M/I Queueing System,122

3.3.1 Main Results、124

3.3.2 Occupancy Distribution Upon Arrival,132

3.3.3 Occupancy Distribution Upon Departure,134

3.4TheM/M/m, M/M/x and M/M/m/m Systems,134

3.4.1 M/M/m: The m-Server Case,135

3.4.2 M/M/∞: Infinite-Server Case,138

3.4.3 M/M/m/m: The m-Server Loss System,140

3.5The M/G/1 System,140

3.5.1 M/G/1 Queues with Vacations,147

3.5.2Reservations and Polling,150

Single-User System,152

Multiuser System,154

Limited Service Systems,157

3.5.3Priority Queueing,159

Nonpreemptive Priority,159

Preemptive Resume Priority,161

3.6 Networks of Transmission Lines,163

3.7 Time Reversibility—Burke’s Theorem,167

3.8 Networks of Queues—Jackson’s Theorem,174

3.9 Summary,180

3.10 Notes, Sources, and Suggested Reading,180

PROBLEMS,182

APPENDIX A:Review of Markov Chain Theory,194

3.A.1 Discrete-Time Markov Chains,194

3.A.2 Detailed Balance Equations,196

3.A.3 Partial Balance Equations,197

3.A.4 Continuous-Time Markov Chains,197

APPENDIX B: Summary of Results,199

Chapter 4MULTIACCESS COMMUNICATION205

4.1Introduction,205

4.1.1 Satellite Channels,207

4.1.2 Multidrop Telephone Lines,208

4.1.3 Multitapped Bus,208

4.1.4 Packet Radio Networks,209

4.2Slotted Multiaccess andi the Aloha System,209

4.2.1Idealized Slotted Multiaccess Model,209

Discussion of Assumptions,210

4.2.2 Slotted Aloha,211

4.2.3Stabilized Slotted Aloha,216

Stability andi Maximum Throughput216

Pseudo- Bavesian Algorithm,217

Approximate Delay Analysis,219

Binary Exponential Backoff,221

4.2.4 Unslotted Aloha222

4.3Splitting Algorithms,224

4.3.1Tree Algorithms,225

Improvements to the Tree Algorithm227

Variants of the Tree Algorithm,229

4.3.2First-Come First-Serve Splitting Algorithms,229

Analysis of FCFS Splitting Algorithm,233

Improvements in the FCFS Splitting Algorithm,237

Practical Details,238

The Last-Come First-Serve （LCFS） Splitting Algorithm238

Delayed Feedback,240

Round Robin Splitting,240

4.4Carrier Sensing,240

4.4.1 CSMA Slotted Aloha,241

4.4.2 Pseudo-Bayesian Stabilization for CSMA Aloha,244

4.4.3 CSMA Unslotted Aloha,246

4.4.4 FCFS Splitting Algorithm for CSMA,247

4.5Multiaccess Reservations,249

4.5.1 Satellite Reservation Svstems,250

4.5.2Local Area Networks: CSMA/CD and Ethernet,254

Slotted CSMA/CD,255

Unslotted CSMA/CD,256

The IEEE 802 Standards,257

4.5.3Local Area Networks: Token Rings,258

IEEE 802.5 Token Ring Standard,261

Expected Delay for Token Rings,262

Slotted Rings and Register Insertion Rings,263

4.5.4Local Area Networks: Token Buses and Polling,265

IEEE 802.4 Token Bus Standard,266

Implicit Tokens: CSMA/CA,267

4.5.5Higher-Speed Local Area Networks,267

Expressnet,269

Homenets,270

4.5.6 Generalized Polling and Splitting Algorithms,272

4.6Packet Radio Networks,274

4.6.1 TDM for Packet Radio Nets,276

4.6.2 Collision Resolution for Packet Radio Nets,277

4.6.3 Transmission Radii for Packet Radio,280

4.6.4 Carrier Sensing and Busy Tones,281

4.7 Summary,282

4.8 Notes, Sources, and Suggested Reading,283

PROBLEMS,283

Chapter 5ROUTING IN DATA NETWORKS297

5.1Introduction,297

5.1.1 Main Issues in Routing,299

5.1.2An Overview of Routing in Practice,302

Routing in the ARPANET,303

Routing in the TYMNET,305

Routing in SNA,307

5.2Network Algorithms and Shortest Path Routing,308

5.2.1 Undirected Graphs,308

5.2.2 Minimum Weight Spanning Trees,312

5.2.3Shortest Path Algorithms,315

The Bell man-Ford Algorithm,318

Dijkstra’s Algorithm,322

The Flovd-Warshall Algorithm,323

5.2.4 Distributed Asynchronous Bellman-Ford Algorithm,325

5.2.5Adaptive Routing Based on Shortest Paths,333

Stability Issues in Datagram Networks,333

Stability Issues in Virtual Circuit Networks,336

5.3Broadcasting Routing Information—Coping with Link Failures,340

5.3.1 Flooding—The ARPANET Algorithm,343

5.3.2 Flooding without Periodic Updates,345

5.3.3 Topology Broadcast without Sequence Numbers,347

5.4Flow Models, Optimal Routing, and Topological Design,355

5.4.1 An Overview of Topological Design Problems,360

5.4.2The Subnet Design Problem,362

Capacity Assignmnent Problem,362

Heurisric Methods for Capacity Assignment,364

Network Reliability Issues,367

Spanning Tree Topology Design,370

5.4.3 The Local Access Network Design Problem,371

5.5 Characterization of Optimal Routing,374

5.6Feasible Direction Methods for Optimal Routing,382

5.6.1 The Frank-Wolfe （Flow Deviation） Method,385

5.7Projection Methods for Optimal Routing,392

Unconstrained Nonlinear Optimization,392

Nonlinear Optimization Over the Positive Orthant,394

Application to Optimal Routing,396

5.8 Routing in the Codex Network,403

5.9 Summary,405

5.10Notes, Sources, and Suggested Reading,406

PROBLEMS,407

Chapter 6FLOW CONTROL423

6.1Introduction,423

6.1.1 Main Objectives of Flow Control,424

Keeping Delay Small within the Subnet,424

Fairness,425

Buffer Overflow,427

6.2Window Flow Control,429

6.2.1End-to-End Windows,430

Limitations of End-to-End Windows,432

6.2.2 Node-by-Node Windows for Virtual Circuits,435

6.2.3 The Isarithmic Method437

6.2.4 Window Flow Control at the User Level,438

6.3Overview of Flow Control in Practice,439

Flow Control in the ARPANE T,439

Flow Conuol in the T YM NET,440

Flow Control in SNA,440

Flow Control in the Codex Network441

Flow Control in X.25,442

6.4Flow Control Schemes Based on Input Rate Adjustment,442

6.4.1 Combined Optimal Routing aud Flow Control,443

6.4.2 Max-Min Flow Control,448

6.4.3 Implementation of Input Rates in a Dvnamic Environment,453

6.5 Smmnary,455

6.6 Notes, Sources, and Suggested Reading,455

PROBLEMS,456

REFERENCES463

INDEX477