Chapter 1 INTRODUCTION AND LAYERED NETWORKARCHITECTURE 1
1.1 Historical 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.2 Messages 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.3 Layering, 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 2 DATA LINK CONTROL AND COMMUNICATIONCHANNELS 31
2.1 Overview, 31
2.2 The 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.3 Error 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.4 ARQ—Retransmission Strategies 58
2.4.1 Stop-and-Wait ARQ, 59
2.4.2 ARPANET ARQ, 62
2.4.3 Go 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.5 Framing, 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.7 Session Identification and Addressing, 91
2.7.1 Session Identification in TYMNET, 92
2.7.2 Session Identification in the Codex Networks, 94
2.8 Error 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 Standard 99
2.9 Summary, 101
2.10 Notes, Sources, and Suggested Reading, 102
PROBLEMS, 103
Chapter 3 DELAY MODELS IN DATA NETWORKS 111
3.1 Introduction, 111
3.1.1 Multiplexing of Traffic on a Communication Link, 112
3.2 Queueing Models—Little’s Theorem, 114
3.3 TheM/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.4 TheM/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.5 The M/G/1 System, 140
3.5.1 M/G/1 Queues with Vacations, 147
3.5.2 Reservations and Polling, 150
Single-User System, 152
Multiuser System, 154
Limited Service Systems, 157
3.5.3 Priority 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 4 MULTIACCESS COMMUNICATION 205
4.1 Introduction, 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.2 Slotted Multiaccess andi the Aloha System, 209
4.2.1 Idealized Slotted Multiaccess Model, 209
Discussion of Assumptions, 210
4.2.2 Slotted Aloha, 211
4.2.3 Stabilized Slotted Aloha, 216
Stability andi Maximum Throughput 216
Pseudo- Bavesian Algorithm, 217
Approximate Delay Analysis, 219
Binary Exponential Backoff, 221
4.2.4 Unslotted Aloha 222
4.3 Splitting Algorithms, 224
4.3.1 Tree Algorithms, 225
Improvements to the Tree Algorithm 227
Variants of the Tree Algorithm, 229
4.3.2 First-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 Algorithm 238
Delayed Feedback, 240
Round Robin Splitting, 240
4.4 Carrier 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.5 Multiaccess Reservations, 249
4.5.1 Satellite Reservation Svstems, 250
4.5.2 Local Area Networks: CSMA/CD and Ethernet, 254
Slotted CSMA/CD, 255
Unslotted CSMA/CD, 256
The IEEE 802 Standards, 257
4.5.3 Local 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.4 Local Area Networks: Token Buses and Polling, 265
IEEE 802.4 Token Bus Standard, 266
Implicit Tokens: CSMA/CA, 267
4.5.5 Higher-Speed Local Area Networks, 267
Expressnet, 269
Homenets, 270
4.5.6 Generalized Polling and Splitting Algorithms, 272
4.6 Packet 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 5 ROUTING IN DATA NETWORKS 297
5.1 Introduction, 297
5.1.1 Main Issues in Routing, 299
5.1.2 An Overview of Routing in Practice, 302
Routing in the ARPANET, 303
Routing in the TYMNET, 305
Routing in SNA, 307
5.2 Network Algorithms and Shortest Path Routing, 308
5.2.1 Undirected Graphs, 308
5.2.2 Minimum Weight Spanning Trees, 312
5.2.3 Shortest 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.5 Adaptive Routing Based on Shortest Paths, 333
Stability Issues in Datagram Networks, 333
Stability Issues in Virtual Circuit Networks, 336
5.3 Broadcasting 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.4 Flow Models, Optimal Routing, and Topological Design, 355
5.4.1 An Overview of Topological Design Problems, 360
5.4.2 The 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.6 Feasible Direction Methods for Optimal Routing, 382
5.6.1 The Frank-Wolfe （Flow Deviation） Method, 385
5.7 Projection 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.10 Notes, Sources, and Suggested Reading, 406
PROBLEMS, 407
Chapter 6 FLOW CONTROL 423
6.1 Introduction, 423
6.1.1 Main Objectives of Flow Control, 424
Keeping Delay Small within the Subnet, 424
Fairness, 425
Buffer Overflow, 427
6.2 Window Flow Control, 429
6.2.1 End-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 Method 437
6.2.4 Window Flow Control at the User Level, 438
6.3 Overview 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 Network 441
Flow Control in X.25, 442
6.4 Flow 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
REFERENCES 463
INDEX 477