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,255Contents 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