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.5 Continuously distributed random variables.

1.6 Some useful inequalities.

1.7 Joint distribution functions.

1.8 Conditional expectation.

1.9 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.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.

Markov chain.

2.5 Birth-death Markov chains.

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.3 A queue described by an underlying Markov chain.

3.4 Stationary queues.

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.2 Token (leaky) buckets for packet-traffic regulation.

4.3 Multiplexing flows of variable-length packets.

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.2 Stable open networks of queues.

Problems.

6. Dynamic Routing and Routing with Incentives.

6.1 General routing issues.

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.

forwarding.

7.3 Structured query resolution.

7.4 Discussion: security issues.

7.5 Incentives for cooperation when downloading.

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.