Bibliothèque de L'IMIST/CNRST

Includes bibliographical references (pages 221-232).

1 Review of Elementary Probability Theory 1 -- 1.1 Sample space, events, and probabilities 1 -- 1.2 Random variables 3 -- 1.3 Cumulative distribution functions, expectation, and moment generating functions 3 -- 1.4 Discretely distributed random variables 5 -- 1.4.1 The Bernoulli distribution 5 -- 1.4.2 The geometric distribution 6 -- 1.4.3 The binomial distribution 6 -- 1.4.4 The Poisson distribution 7 -- 1.4.5 The discrete uniform distribution 8 -- 1.5 Continuously distributed random variables 9 -- 1.5.1 The continuous uniform distribution 10 -- 1.5.2 The exponential distribution 11 -- 1.5.3 The gamma distribution 11 -- 1.5.4 The Gaussian (or normal) distribution 11 -- 1.6 Some useful inequalities 12 -- 1.7 Joint distribution functions 14 -- 1.7.1 Joint PDF 14 -- 1.7.2 Marginalizing a Joint distribution 15 -- 1.8 Conditional expectation 15 -- 1.9 Independent random variables 18 -- 1.9.1 Sums of independent random variables 18 -- 1.10 Conditional independence 20 -- 1.11 A law of large numbers 20 -- 1.12 First-order autoregressive estimators 22 -- 1.13 Measures of separation between distributions 23 -- 1.14 Statistical confidence 24 -- 1.14.1 A central limit theorem 24 -- 1.14.2 Confidence intervals 25 -- 1.14.3 Recursive formulas and a stopping criterion 28 -- 1.15 Deciding between two alternative claims 29 -- 2 Markov Chains 35 -- 2.1 Memoryless property of the exponential distribution 36 -- 2.2 Finite-dimensional distributions and stationarity 37 -- 2.3 The Poisson (counting) process on R+ 38 -- 2.4 Continuous-time, time-homogeneous Markov processes with countable state space 41 -- 2.4.1 The Markov property 41 -- 2.4.2 Sample path construction of a time-homogeneous, continuous-time Markov chain 42 -- 2.4.3 The transition rate matrix and transition rate diagram 45 -- 2.4.4 The Kolmogorov equations 47 -- 2.4.5 The balance equations for the stationary distribution 52 -- 2.4.6 Transience and recurrence 54 -- 2.4.7 Convergence in distribution to steady state 56 -- 2.4.8 Time reversibility and the detailed balance equations 56 -- 2.5 Birth-death Markov chains 59 -- 2.5.1 Birth-death processes with finite state space 60 -- 2.5.2 Birth-death processes with infinite state space 61 -- 2.5.3 Applications of the forward equations 63 -- 2.6 Modeling time-series data using a Markov chain 65 -- 2.7 Simulating a Markov chain 70 -- 2.8 Overview of discrete-time Markov chains 72 -- 2.9 Martingales adapted to discrete time Markov chains 78 -- 3.1 Arrivals, departures, and queue occupancy 83 -- 3.2 Lossless queues 85 -- 3.2.1 No waiting room 86 -- 3.2.2 Single-server queue 87 -- 3.2.3 Single server and constant service times 88 -- 3.2.4 Single server and general service times 91 -- 3.3 A queue described by an underlying Markov chain 91 -- 3.4 Stationary queues 92 -- 3.4.1 Point processes and queues on R 93 -- 3.4.2 Stationary and synchronous versions of a marked point process 94 -- 3.4.3 Poisson arrivals see time averages 96 -- 3.4.4 Little's result 100 -- 3.5 Erlang's blocking formula for the M/M/K/K queue 104 -- 3.6 Overview of discrete-time queues 105 -- 4 Local Multiplexing 111 -- 4.1 Internet router architecture 111 -- 4.1.1 Big picture of an IP (layer 3) router 112 -- 4.1.2 Ingress linecard 112 -- 4.1.3 Switch fabric 115 -- 4.1.4 Egress linecard 118 -- 4.2 Token (leaky) buckets for packet traffic regulation 119 -- 4.3 Multiplexing flows of variable-length packets 122 -- 4.3.1 Multiplexing with a single FIFO queue 124 -- 4.3.2 Strict priority 124 -- 4.3.3 Deficit round-robin 124 -- 4.3.4 Shaped VirtualClock 126 -- 4.4 Service curves 128 -- 4.5 Connection multiplexing on a single trunk 129 -- 4.6 A game-theoretic framework for multiplexing packet flows 132 -- 4.7 Discussion: Local medium access control of a single wireless channel 137 -- 5 Queueing networks with static routing 141 -- 5.1 Loss Networks 141 -- 5.1.1 Fixed-route arrival rates 143 -- 5.1.2 Exact expression for connection blocking 145 -- 5.1.3 Fixed-point iteration for approximate connection blocking 146 -- 5.2 Stable open networks of queues 147 -- 5.2.1 Flow balance equations 148 -- 5.2.2 Open Jackson networks 150 -- 6 Dynamic Routing and Routing with Incentives 157 -- 6.1 General routing issues 157 -- 6.1.1 Discussion: IP forwarding 159 -- 6.1.2 Discussion: MPLS 160 -- 6.2 Unconstrained optimization 161 -- 6.3 Revenue maximization for loss networks 163 -- 6.4 Constrained optimization and duality 164 -- 6.5 A distributed pricing and resource management framework 166 -- 6.6 Discussion: Joint scheduling and routing in multihop wireless networks 169 -- 6.7 Multipath load balancing 170 -- 7 Peer-to-Peer File Sharing with Incentives 177 -- 7.2 Unstructured query resolution 179 -- 7.2.1 A centralized approach to search 179 -- 7.2.2 A decentralized approach to search: Limited-scope flooding and reverse-path forwarding 179 -- 7.2.3 A partially centralized approach to search 180 -- 7.2.4 An example of search by random walk 181 -- 7.3 Structured query resolution 182 -- 7.3.1 A structured P2P framework using Voronoi cells 183 -- 7.3.2 Specific approaches using Voronoi cells 184 -- 7.3.3 Variations in the design of search, including Chord 187 -- 7.3.4 The Kademlia example 190 -- 7.3.5 Discussion: Spatial neighbor-to-neighbor graphs 191 -- 7.4 Discussion: Security issues 192 -- 7.4.1 The querying process 192 -- 7.4.2 The downloading process 193 -- 7.5 Incentives for cooperation when uploading 193 -- 7.5.1 Rule-based incentives of BitTorrent-like swarms 194 -- 7.5.2 A cumulative reputation system to observe the level of peer cooperation 195 -- 7.5.3 Modeling trust groups 198 -- 7.5.4 Discussion: Game-theoretic models of P2P systems 199 -- Appendix A Additional Background on Routing 203 -- A.1 Network graph terminology 203 -- A.2 Link state algorithms 207 -- A.3 Distance vector algorithms 209 -- Appendix B Solutions or References for Selected Problems 213.