Contents PREFACE xiii Chapter 1 INTRODUCTION AND LAYERED NETWORK ARCHITECTURE 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
xiii sss Xlll Chapter 1 INTRODUCTION AND LAYERED NETWORK ARCHITECTURE 1 1.1 Historical Overview, 1 Technological and Economic Background, 4 Communication Technology, 5 Applications of Data Networks, 6 1.2 Messages and Switching, 8 Messages and Packets, 8 Sessions, 9 Circuit Switching and Store and Forward Switching, 11 1.3 Layering, 14 The Physical Layer, 17 The Data Link Control (DLC) Layer, 20 The Network Layer, 22 The Transport Layer, 24 The Session Layer, 25 Contents PREFACE 1.1.1 1.1.2 1.1.3 1.2.1 1.2.2 1.2.3 1.3.1 1.3.2 1.3.3 1.3.4 1.3.5
vi Contents 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 COMMUNICATION CHANNELS 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
Contents 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 COMMUNICATION CHANNELS 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
Contents vii 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 Layer 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 The M/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 The M/M/m,M/M/,and M/M/m/m Systems,134
Contents vii 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 Layer 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, Ill 3.1.1 Multiplexing of Traffic on a Communication Link, 112 3.2 Queueing Models-Little's Theorem, 114 3.3 The M/M/1 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 The M/M/m, MIM/oo, and MIM/mIm Systems, 134
vi曲 Contents 3.4.1 M/M/m:The m-Server Case,135 3.4.2 M/M/o: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
viii Contents 3.4.1 MIMIm: The m-Server Case, 135 3.4.2 M/M/oo: 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 ___
Contents ix 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 and 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 and Maximum Throughput,216 Pseudo-Bayesian 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.I Satellite Reservation Systems,250 4.5.2 Local Area Networks:CSMA/CD and Ethernet,254 Slotted CSMA/CD,255
Contents ix 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 and 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 and Maximum Throughput, 216 Pseudo-Bayesian 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 Systems, 250 4.5.2 Local Area Networks: CSMA/CD and Ethernet, 254 Slotted CSMA/CD, 255