In large measure the traditional concern of communications engineers has been the conveyance of voice signals. The most prominent example is the telephone network, in which the techniques used for transmission multiplex­ ing and switching have been designed for voice signals. However, one of the many effects of computers has been the growing volume of the sort of traffic that flows in networks composed of user terminals, processors, and peripherals. The characteristics of this data traffic and the associated perfor­ mance requirements are quite different from those of voice traffic. These differences, coupled with burgeoning digital technology, have engendered a whole new set of approaches to multiplexing and switching this traffic. The new techniques are the province of what has been loosely called computer communications networks. The subject of this book is the mathematical modeling and analysis of computer communications networks, that is to say, the multiplexing and switching techniques that have been developed for data traffic. The basis for many of the models that we shall consider is queueing theory, although a number of other disciplines are drawn on as well. The level at which this material is covered is that of a first-year graduate course. It is assumed that at the outset the student has had a good undergraduate course in probability and random processes of the sort that are more and more common among electrical engineering and computer science departments.

Table of Contents:
1. Basic Orientation.- 1.1. Modeling and Analysis of Computer Communication Networks.- 1.2. Computer Communications Networks.- 1.3. Summary of Text.- 2. Protocols and Facilities.- 2.1. Introduction.- 2.2. Properties of Data Traffic.- 2.3. Protocols.- 2.4. The Telephone Network.- 2.5. Data Transmission.- 2.6. Data Networks.- 2.7. Local Area Networks.- 2.8. Alternative Facilities: Satellites and Cable Television.- 3. Pure Birth and Birth-Death Processes: Applications to Queueing.- 3.1. Introduction.- 3.2. Bernoulli Trials—Markov Chains.- 3.3. The Poisson Process.- 3.4. Pure Birth Processes.- 3.5. Birth-Death Processes.- 3.6. Queueing Models.- 3.7. Delay—Little’s Formula.- 3.8. Burke’s Theorem.- 3.9. Communications Example.- 3.10. Method of Stages.- Exercises.- 4. Imbedded Markov Chain: The M/G/1 Queue.- 4.1. Introduction.- 4.2. The M/G/1 Queue.- 4.3. Variation for the Initiator of a Busy Period.- 4.4. Numerical Results.- Exercises.- 5. Imbedded Markov Chain Analysis of Time-Division Multiplexing.- 5.1. Introduction.- 5.2. Simple and Compound Poisson Arrival.- 5.3. Asynchronous Time-Division Multiplexing.- 5.4. Synchronous Time-Division Multiplexing.- 5.5. Message Delay.- 5.6. Alternate Derivation Average Delay in STDM.- 5.7. “Come Right In” Strategy.- 5.8. Automatic Repeat Request.- Exercises.- 6. Intermittently Available Server, Priority Queues: Application to Ring Systems.- 6.1. Interrupted Service, Priority Queues.- 6.2. Preemptive Resume Discipline.- 6.3. Nonpreemptive Priorities.- 6.4. Application to Local Area Networks with the Ring Topology.- Exercises.- 7. Polling.- 7.1. Basic Model: Applications.- 7.2. Average Cycle Time: Infinite Buffer.- 7.3. Single-Message Buffers.- 7.4. Analysis: Infinite Buffer.- 7.5. Review of Literature.- Exercises.- 8. RandomAccess Systems.- 8.1. ALOHA and Slotted ALOHA.- 8.2. Carrier Sense Multiple Access.- 8.3. Delay Calculations CSMA/CD.- 8.4. Performance Comparisons.- 8.5. Reservation Techniques.- Exercises.- 9. Probing and Tree Search Techniques.- 9.1. Overhead and Information Theory.- 9.2. Probing.- 9.3. Cycle Time in Probing.- 9.4. Message Delay.- 9.5. More Complete State Information.- Exercises.- 10. Networks of Queues.- 10.1. Introduction—Jackson Networks.- 10.2. Multidimensional Birth-Death Processes; Queues in Tandem.- 10.3. Networks of Queues—Product Form Distribution.- 10.4. The Departure Process—Time Reversal.- 10.5. Store-and-Forward Communication Networks.- 10.6. Capacity Allocation.- Exercises.- 11. Congestion and Flow Control.- 11.1. Introduction.- 11.2. Link Level Flow Control—HDLC.- 11.3. Flow Control and Jackson Networks.- 11.4. Computational Techniques—Closed Networks.- 11.5. Networks with Blocking.- Exercises.- 12. Routing-Flow Allocation.- 12.1. Introduction.- 12.2. Routing Model.- 12.3. Shortest-Path Algorithms.- 12.4. Capacity Constraints.- 12.5. Flow Control and Routing.- 12.6. Routing in Practice.- Exercises.- 13. Network Layout and Reliability.- 13.1. Introduction.- 13.2. Trees.- 13.3. Distributed Networks.- 13.4. Network Reliability.- Exercises.- Appendix A: Review of Probability Theory.- ?.1. Axioms of Probability.- A.2. Conditional Probability.- A.3. Random Variables—Probability Distributions and Densities.- A.4. Joint Distributions of Random Variables.- A.5. Expectation of a Random Variable—Moments.- A.6. Probability-Generating Functions and Characteristic Functions.- A.7. Bounds and Limit Theorems.- Appendix B: Review of Markov Chains.- B.1. Example: Bernoulli Trials.- B.2. State Transition Matrix.- B.3. Steady-state Distribution.