An Introduction to Communication Network Analysis

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 equations. 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 equations. 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. References.