An introduction to communication network analysis

AN INTRODUCTION TO COMMUNICATION NETWORK ANALYSIS......Page 3
CONTENTS......Page 9
Preface......Page 15
1.1 Sample space, events, and probabilities......Page 17
1.3 Cumulative distribution functions, expectation, and moment generating functions......Page 19
1.4.1 The Bernoulli distribution......Page 21
1.4.3 The binomial distribution......Page 22
1.4.4 The Poisson distribution......Page 23
1.4.5 The discrete uniform distribution......Page 24
1.5 Continuously distributed random variables......Page 25
1.5.1 The continuous uniform distribution......Page 26
1.5.4 The Gaussian (or normal) distribution......Page 27
1.6 Some useful inequalities......Page 28
1.7.1 Joint PDF......Page 30
1.8 Conditional expectation......Page 31
1.9.1 Sums of independent random variables......Page 34
1.11 A law of large numbers......Page 36
1.12 First-order autoregressive estimators......Page 38
1.13 Measures of separation between distributions......Page 39
1.14.1 A central limit theorem......Page 40
1.14.2 Confidence intervals......Page 41
1.14.3 Recursive formulas and a stopping criterion......Page 44
1.15 Deciding between two alternative claims......Page 45
Problems......Page 46
2 Markov Chains......Page 51
2.1 Memoryless property of the exponential distribution......Page 52
2.2 Finite-dimensional distributions and stationarity......Page 53
2.3 The Poisson (counting) process on R+......Page 54
2.4.1 The Markov property......Page 57
2.4.2 Sample path construction of a time-homogeneous, continuous-time Markov chain......Page 58
2.4.3 The transition rate matrix and transition rate diagram......Page 61
2.4.4 The Kolmogorov equations......Page 63
2.4.5 The balance equations for the stationary distribution......Page 68
2.4.6 Transience and recurrence......Page 70
2.4.8 Time reversibility and the detailed balance equations......Page 72
2.5 Birth-death Markov chains......Page 75
2.5.1 Birth-death processes with finite state space......Page 76
2.5.2 Birth-death processes with infinite state space......Page 77
2.5.3 Applications of the forward equations......Page 79
2.6 Modeling time-series data using a Markov chain......Page 81
2.7 Simulating a Markov chain......Page 86
2.8 Overview of discrete-time Markov chains......Page 88
Problems......Page 94
3.1 Arrivals, departures, and queue occupancy......Page 99
3.2 Lossless queues......Page 101
3.2.1 No waiting room......Page 102
3.2.2 Single-server queue......Page 103
3.2.3 Single server and constant service times......Page 104
3.3 A queue described by an underlying Markov chain......Page 107
3.4 Stationary queues......Page 108
3.4.1 Point processes and queues on R......Page 109
3.4.2 Stationary and synchronous versions of a marked point process......Page 110
3.4.3 Poisson arrivals see time averages......Page 112
3.4.4 Little's result......Page 116
3.5 Erlang's blocking formula for the M/M/K/K queue......Page 120
3.6 Overview of discrete-time queues......Page 121
Problems......Page 123
4.1 Internet router architecture......Page 127
4.1.2 Ingress linecard......Page 128
4.1.3 Switch fabric......Page 131
4.1.4 Egress linecard......Page 134
4.2 Token (leaky) buckets for packet traffic regulation......Page 135
4.3 Multiplexing flows of variable-length packets......Page 138
4.3.3 Deficit round-robin......Page 140
4.3.4 Shaped VirtualClock......Page 142
4.4 Service curves......Page 144
4.5 Connection multiplexing on a single trunk......Page 145
4.6 A game-theoretic framework for multiplexing packet flows......Page 148
Problems......Page 153
5.1 Loss Networks......Page 157
5.1.1 Fixed-route arrival rates......Page 159
5.1.2 Exact expression for connection blocking......Page 161
5.1.3 Fixed-point iteration for approximate connection blocking......Page 162
5.2 Stable open networks of queues......Page 163
5.2.1 Flow balance equations......Page 164
5.2.2 Open Jackson networks......Page 166
Problems......Page 169
6.1 General routing issues......Page 173
6.1.1 Discussion: IP forwarding......Page 175
6.1.2 Discussion: MPLS......Page 176
6.2 Unconstrained optimization......Page 177
6.3 Revenue maximization for loss networks......Page 179
6.4 Constrained optimization and duality......Page 180
6.5 A distributed pricing and resource management framework......Page 182
6.6 Discussion: Joint scheduling and routing in multihop wireless networks......Page 185
6.7 Multipath load balancing......Page 186
Problems......Page 190
7 Peer-to-Peer File Sharing with Incentives......Page 193
7.1 Summary of query resolution......Page 194
7.2.2 A decentralized approach to search: Limited-scope flooding and reverse-path forwarding......Page 195
7.2.3 A partially centralized approach to search......Page 196
7.2.4 An example of search by random walk......Page 197
7.3 Structured query resolution......Page 198
7.3.1 A structured P2P framework using Voronoi cells......Page 199
7.3.2 Specific approaches using Voronoi cells......Page 200
7.3.3 Variations in the design of search, including Chord......Page 203
7.3.4 The Kademlia example......Page 206
7.3.5 Discussion: Spatial neighbor-to-neighbor graphs......Page 207
7.4.1 The querying process......Page 208
7.5 Incentives for cooperation when uploading......Page 209
7.5.1 Rule-based incentives of BitTorrent-like swarms......Page 210
7.5.2 A cumulative reputation system to observe the level of peer cooperation......Page 211
7.5.3 Modeling trust groups......Page 214
7.5.4 Discussion: Game-theoretic models of P2P systems......Page 215
Problems......Page 216
A.1 Network graph terminology......Page 219
A.2 Link state algorithms......Page 223
A.3 Distance vector algorithms......Page 225
Appendix B: Solutions or References for Selected Problems......Page 229
References......Page 237