You are previewing Communication Networks.
O'Reilly logo
Communication Networks

Book Description

Provides a modern mathematical approach to the design of communication networks for graduate students, blending control, optimization, and stochastic network theories. A broad range of performance analysis tools are discussed, including important advanced topics that have been made accessible to students for the first time. Taking a top-down approach to network protocol design, the authors begin with the deterministic model and progress to more sophisticated models. Network algorithms and protocols are tied closely to the theory, illustrating the practical engineering applications of each topic. The background behind the mathematical analyses is given before the formal proofs and is supported by worked examples, enabling students to understand the big picture before going into the detailed theory. End-of-chapter problems cover a range of difficulties, with complex problems broken into several parts, and hints to many problems are provided to guide students. Full solutions are available online for instructors.

Table of Contents

  1. Cover
  2. Half Title
  3. Title
  4. Copyright
  5. Dedication
  6. Authors
  7. Contents
  8. Preface
  9. 1 Introduction
  10. I Network architecture and algorithms
    1. 2 Mathematics of Internet architecture
      1. 2.1 Mathematical background: convex optimization
        1. 2.1.1 Convex sets and convex functions
        2. 2.1.2 Convex optimization
      2. 2.2 Resource allocation as utility maximization
        1. 2.2.1 Utility functions and fairness
      3. 2.3 Mathematical background: stability of dynamical systems
      4. 2.4 Distributed algorithms: primal solution
        1. 2.4.1 Congestion feedback and distributed implementation
      5. 2.5 Distributed algorithms: dual solution
      6. 2.6 Feedback delay and stability
        1. 2.6.1 Linearization
      7. 2.7 Game-theoretic view of utility maximization
        1. 2.7.1 The Vickrey–Clarke–Groves mechanism
        2. 2.7.2 The price-taking assumption
        3. 2.7.3 Strategic or price-anticipating users
      8. 2.8 Summary
      9. 2.9 Exercises
      10. 2.10 Notes
    2. 3 Links: statistical multiplexing and queues
      1. 3.1 Mathematical background: the Chernoff bound
      2. 3.2 Statistical multiplexing and packet buffering
        1. 3.2.1 Queue overflow
      3. 3.3 Mathematical background: discrete-time Markov chains
      4. 3.4 Delay and packet loss analysis in queues
        1. 3.4.1 Little’s law
        2. 3.4.2 The Geo/Geo/1 queue
        3. 3.4.3 The Geo/Geo/1/B queue
        4. 3.4.4 The discrete-time G/G/1 queue
      5. 3.5 Providing priorities: fair queueing
        1. 3.5.1 Key properties
      6. 3.6 Summary
      7. 3.7 Exercises
      8. 3.8 Notes
    3. 4 Scheduling in packet switches
      1. 4.1 Switch architectures and crossbar switches
        1. 4.1.1 Head-of-line blocking and virtual output queues
      2. 4.2 Capacity region and MaxWeight scheduling
        1. 4.2.1 Intuition behind the MaxWeight algorithm
      3. 4.3 Low-complexity switch scheduling algorithms
        1. 4.3.1 Maximal matching scheduling
        2. 4.3.2 Pick-and-compare scheduling
        3. 4.3.3 Load-balanced switches
      4. 4.4 Summary
      5. 4.5 Exercises
      6. 4.6 Notes
    4. 5 Scheduling in wireless networks
      1. 5.1 Wireless communications
      2. 5.2 Channel-aware scheduling in cellular networks
      3. 5.3 The MaxWeight algorithm for the cellular downlink
      4. 5.4 MaxWeight scheduling for ad hoc P2P wireless networks
      5. 5.5 General MaxWeight algorithms
      6. 5.6 Q-CSMA: a distributed algorithm for ad hoc P2P networks
        1. 5.6.1 The idea behind Q-CSMA
        2. 5.6.2 Q-CSMA
      7. 5.7 Summary
      8. 5.8 Exercises
      9. 5.9 Notes
    5. 6 Back to network utility maximization
      1. 6.1 Joint formulation of the transport, network, and MAC problems
      2. 6.2 Stability and convergence: a cellular network example
      3. 6.3 Ad hoc P2P wireless networks
      4. 6.4 Internet versus wireless formulations: an example
      5. 6.5 Summary
      6. 6.6 Exercises
      7. 6.7 Notes
    6. 7 Network protocols
      1. 7.1 Adaptive window flow control and TCP protocols
        1. 7.1.1 TCP-Reno: a loss-based algorithm
        2. 7.1.2 TCP-Reno with feedback delay
        3. 7.1.3 TCP-Vegas: a delay-based algorithm
      2. 7.2 Routing algorithms: Dijkstra and Bellman–Ford algorithms
        1. 7.2.1 Dijkstra’s algorithm: link-state routing
        2. 7.2.2 Bellman–Ford algorithm: distance-vector routing
      3. 7.3 IP addressing and routing in the Internet
        1. 7.3.1 IP addressing
        2. 7.3.2 Hierarchical routing
      4. 7.4 MAC layer protocols in wireless networks
        1. 7.4.1 Proportionally fair scheduler in cellular downlink
        2. 7.4.2 MAC for WiFi and ad hoc networks
      5. 7.5 Summary
      6. 7.6 Exercises
      7. 7.7 Notes
    7. 8 Peer-to-peer networks
      1. 8.1 Distributed hash tables
        1. 8.1.1 Chord
        2. 8.1.2 Kademlia
      2. 8.2 P2P file sharing
        1. 8.2.1 The BitTorrent protocol
      3. 8.3 Structured P2P streaming
      4. 8.4 Unstructured P2P streaming
      5. 8.5 The gossip process
      6. 8.6 Summary
      7. 8.7 Exercises
      8. 8.8 Notes
  11. II Performance analysis
    1. 9 Queueing theory in continuous time
      1. 9.1 Mathematical background: continuous-time Markov chains
      2. 9.2 Queueing systems: introduction and definitions
      3. 9.3 The M/M/1 queue
      4. 9.4 The M/M/s/s queue
        1. 9.4.1 The PASTA property and blocking probability
      5. 9.5 The M/M/s queue
      6. 9.6 The M/GI/1 Queue
        1. 9.6.1 Mean queue length and waiting time
        2. 9.6.2 Different approaches taken to derive the P-K formula
      7. 9.7 The GI/GI/1 queue
      8. 9.8 Reversibility
        1. 9.8.1 The M/M/1 queue
        2. 9.8.2 The tandem M/M/1 queue
      9. 9.9 Queueing systems with product-form steady-state distributions
        1. 9.9.1 The Jackson network
        2. 9.9.2 The multi-class M/M/1 queue
      10. 9.10 Insensitivity to service-time distributions
        1. 9.10.1 The M/M/1-PS queue
        2. 9.10.2 The M/GI/1-PS queue
      11. 9.11 Connection-level arrivals and departures in the internet
      12. 9.12 Distributed admission control
      13. 9.13 Loss networks
        1. 9.13.1 Large-system limit
        2. 9.13.2 Computing the blocking probabilities
        3. 9.13.3 Alternative routing
      14. 9.14 Download time in BitTorrent
      15. 9.15 Summary
      16. 9.16 Exercises
      17. 9.17 Notes
    2. 10 Asymptotic analysis of queues
      1. 10.1 Heavy-traffic analysis of the discrete-time G/G/1 queue
      2. 10.2 Heavy-traffic optimality of JSQ
      3. 10.3 Large deviations of i.i.d. random variables: the Cramer–Chernoff theorem
      4. 10.4 Large-buffer large deviations
      5. 10.5 Many-sources large deviations
      6. 10.6 Summary
      7. 10.7 Exercises
      8. 10.8 Notes
    3. 11 Geometric random graph models of wireless networks
      1. 11.1 Mathematical background: the Hoeffding bound
      2. 11.2 Nodes arbitrarily distributed in a unit square
      3. 11.3 Random node placement
      4. 11.4 Summary
      5. 11.5 Exercises
      6. 11.6 Notes
  12. References
  13. Index