Preface -- 1. Review of Elementary Probability Theory -- 1.1 Sample space, events and probabilities -- 1.2 Random variables -- 1.3 Cumulative distribution functions, expectation and moment generating functions -- 1.4 Discretely distributed random variables -- 1.4.1 The Bernoulli distribution -- 1.4.2 The geometric distribution -- 1.4.3 The binomial distribution -- 1.4.4 The Poisson distribution -- 1.4.5 The discrete uniform distribution -- 1.5 Continuously distributed random variables -- 1.5.1 The continuous uniform distribution -- 1.5.2 The exponential distribution -- 1.5.3 The gamma distribution -- 1.5.4 The Gaussian (or normal) distribution -- 1.6 Some useful inequalities -- 1.7 Joint distribution functions -- 1.7.1 Joint PDF -- 1.7.2 Marginalizing a joint distribution -- 1.8 Conditional expectation -- 1.9 Independent random variables -- 1.9.1 Sums of independent random variables -- 1.10 Conditional independence -- 1.11 A law of large numbers -- 1.12 First order autoregressive estimators -- 1.13 Measures of separation between distributions -- 1.14 Statistical confidence -- 1.14.1 A central limit theorem -- 1.14.2Confidence intervals -- 1.14.3Recursive formulas and a stopping criterion -- 1.15 Deciding between two alternative claims -- Problems -- 2. Markov Chains -- 2.1 Memoryless property of the exponential distribution -- 2.2 Finite dimensional distributions and stationarity -- 2.3 The Poisson (counting) process on R+ -- 2.4 Continuous-time, time-homogeneous, Markov processes with countable state-space -- 2.4.1 The Markov property -- 2.4.2 Sample-path construction of a time-homogeneous, continuous-time Markov chain -- 2.4.3 The transition rate matrix and transition rate diagram -- 2.4.4 The Kolmogorov equations -- 2.4.5 The balance equations for the stationary distribution -- 2.4.6 Transience and recurrence -- 2.4.7 Convergence in distribution to steady-state -- 2.4.8 Time-reversibility and the detailed balance equation

2.5 Birth-death Markov chains -- 2.5.1 Birth-death processes with finite state-space -- 2.5.2 Birth-death processes with infinite state-space -- 2.5.3 Applications of forward equations -- 2.6 Modeling time-series data using a Markov chain -- 2.7 Simulating a Markov chain -- 2.8 Overview of discrete-time Markov chains -- 2.9 Martingales adapted to discrete-time Markov chains -- Problems -- 3. Introduction to Queueing Theory -- 3.1 Arrivals, departures and queue occupancy -- 3.2 Lossless queues -- 3.2.1 No waiting room -- 3.2.2 Single-server queue -- 3.2.3 Single-server and constant service times -- 3.2.4 Single-server and general service times -- 3.3 A queue described by an underlying Markov chain -- 3.4 Stationary queues -- 3.4.1 Point processes and queues on R -- 3.4.2 Stationary and synchronous versions of a marked point process -- 3.4.3 Poisson arrivals see time-averages -- 3.4.4 Little's result -- 3.5 Erlang's blocking formula for the M/M/K/K queue -- 3.6 Overview of discrete-time queues -- Problems -- 4. Local Multiplexing -- 4.1 Internet router architecture -- 4.1.1 Big picture of an IP (layer 3) router -- 4.1.2 Ingress linecard -- 4.1.3 Switch fabric -- 4.1.4 Egress linecard -- 4.2 Token (leaky) buckets for packet-traffic regulation -- 4.3 Multiplexing flows of variable-length packets -- 4.3.1 Multiplexing with a single FIFO queue -- 4.3.2 Strict priority -- 4.3.3 Deficit Round-Robin (DRR) -- 4.3.4 Shaped Virtual Clock (SVC) -- 4.4 Service curves -- 4.5 Connection multiplexing on a single trunk -- 4.6 A game-theoretic framework for multiplexing packet flows -- 4.7 Discussion: local medium access control of a single wireless channel -- Problems -- 5. Queueing networks with static routing -- 5.1 Loss Networks -- 5.1.1 Fixed route arrival rates -- 5.1.2 Exact expression for connection blocking -- 5.1.3 Fixed point iteration for approximate connection blocking -- 5.2 Stable open networks of queues -- 5.2.1 Flow balance equation

5.2.2 Open Jackson networks -- Problems -- 6. Dynamic Routing and Routing with Incentives -- 6.1 General routing issues -- 6.1.1 Discussion: IP forwarding -- 6.1.2 Discussion: MPLS -- 6.2 Unconstrained optimization -- 6.3 Revenue maximization for loss networks -- 6.4 Constrained optimization and duality -- 6.5 A distributed pricing and resource management framework -- 6.6 Discussion: joint scheduling and routing in multihop wireless networks -- 6.7 Multipath load balancing -- Problems -- 7. Peer-to-Peer File Sharing with Incentives -- 7.1 Summary of query resolution -- 7.2 Unstructured query resolution -- 7.2.1 A centralized approach -- 7.2.2 A decentralized approach: limited-scope flooding and reverse-path forwarding -- 7.2.3 A hybrid approach -- 7.2.4 An example of search by random walk -- 7.3 Structured query resolution -- 7.3.1 A "Voronoi" structured P2P framework -- 7.3.2 Specific Voronoi approaches -- 7.3.3 Variations in the design of search, including Chord -- 7.3.4 The Kademlia example -- 7.3.5 Spatial neighbor-to-neighbor graphs -- 7.4 Discussion: security issues -- 7.5 Incentives for cooperation when downloading -- 7.5.1 Rule-based incentives of BitTorrent-like swarms -- 7.5.2 Cumulative reputations -- 7.5.3 Trust groups for scalability and reliability -- 7.5.4 Discussion: P2P games -- Problems -- References -- Appendix A: Additional Background on Routing -- A.1 Network graph terminology -- A.2 Link-state algorithms -- A.3 The Bellman-Ford approach -- Appendix B: Solutions or References for Selected Problems -- Reference