An Introduction to Communication Network Analysis

ISBN-13: 9780471371410 / Angielski / Twarda / 2007 / 248 str.

George Kesidis

Opis

This book is a quantitative text, which focuses on the real issues behind serious modeling and analysis of communications networks. The author covers all the necessary mathematics and theory in order for students to understand the tools that optimize computer networks today.

• Covers both classical (e.g. queueing theory) and modern (e.g. pricing) aspects of networking
• Integrates material on communication networks with material on modeling/analyzing and designing such networks
• Includes a Solution Manual

Recenzje

"This book provides valuable information on the application of analytical techniques to model communication networks." ( Computing Reviews, February 29, 2008)

Spis treści

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.

O autorze

George Kesidis, PhD, is a Professor at the Pennsylvania State University. He is a senior member of the IEEE and TCP co–chair of INFOCOM 2007.

Blurb

A self–contained text on modeling and performance evaluation of communication networks

This quantitative book focuses on the real issues behind modeling and analysis of communication networks. The author covers a wide variety of topical networking subject matter based on the provided background material in probability, Markov chains, and queues. Leveraging this material, the author explores topics in local multiplexing and routing over three successive chapters, stressing both continuous–time and discrete–time contexts. The remaining chapters focus more directly on networking, such as traffic shaping and multiplexing, static routing, dynamic routing, and peer–to–peer file sharing systems.

Providing more rigorous and technically deep coverage than most commonly used networking textbooks, An Introduction to Communication Network Analysis covers classical (e.g., queuing theory) and modern (e.g., pricing) aspects of networking in a clear, accessible manner. Chapters include:

• Review of Elementary Probability Theory

• Markov Chains

• Introduction to Queuing Theory

• Local Multiplexing

• Queuing Networks with Static Routing

• Dynamic Routing with Incentives

• Peer–to–Peer File Sharing with Incentives

Appendices include additional background information, solutions, and references for selected problems, making this an invaluable text for graduate–level students and networking researchers alike.