Communication Networks : An Optimization, Control and Stochastic Networks Perspective

[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]

Preface                                            xi
  1 Introduction                                   1  (4)
I Network architecture and algorithms              5  (222)
  2 Mathematics of Internet architecture           7  (42)
    2.1 Mathematical background: convex            7  (8)
    optimization
      2.1.1 Convex sets and convex functions       7  (4)
      2.1.2 Convex optimization                    11 (4)
    2.2 Resource allocation as utility             15 (4)
    maximization
      2.2.1 Utility functions and fairness         17 (2)
    2.3 Mathematical background: stability of      19 (2)
    dynamical systems
    2.4 Distributed algorithms: primal solution    21 (5)
      2.4.1 Congestion feedback and distributed    24 (2)
      implementation
    2.5 Distributed algorithms: dual solution      26 (1)
    2.6 Feedback delay and stability               27 (3)
      2.6.1 Linearization                          29 (1)
    2.7 Game-theoretic view of utility             30 (11)
    maximization
      2.7.1 The Vickrey-Clarke-Groves mechanism    31 (3)
      2.7.2 The price-taking assumption            34 (1)
      2.7.3 Strategic or price-anticipating        35 (6)
      users
    2.8 Summary                                    41 (1)
    2.9 Exercises                                  42 (5)
    2.10 Notes                                     47 (2)
  3 Links: statistical multiplexing and queues     49 (37)
    3.1 Mathematical background: the Chernoff      49 (2)
    bound
    3.2 Statistical multiplexing and packet        51 (4)
    buffering
      3.2.1 Queue overflow                         52 (3)
    3.3 Mathematical background: discrete-time     55 (9)
    Markov chains
    3.4 Delay and packet loss analysis in queues   64 (8)
      3.4.1 Little's law                           64 (3)
      3.4.2 The Geo/Geo/1 queue                    67 (2)
      3.4.3 The Geo/Geo/1B queue                   69 (1)
      3.4.4 The discrete-time G/G/1 queue          70 (2)
    3.5 Providing priorities: fair queueing        72 (6)
      3.5.1 Key properties                         76 (2)
    3.6 Summary                                    78 (1)
    3.7 Exercises                                  79 (6)
    3.8 Notes                                      85 (1)
  4 Scheduling in packet switches                  86 (24)
    4.1 Switch architectures and crossbar          87 (3)
    switches
      4.1.1 Head-of-line blocking and virtual      88 (2)
      output queues
    4.2 Capacity region and MaxWeight scheduling   90 (6)
      4.2.1 Intuition behind the MaxWeight         96 (1)
      algorithm
    4.3 Low-complexity switch scheduling           96 (9)
    algorithms
      4.3.1 Maximal matching scheduling            96 (6)
      4.3.2 Pick-and-compare scheduling            102(1)
      4.3.3 Load-balanced switches                 102(3)
    4.4 Summary                                    105(1)
    4.5 Exercises                                  106(3)
    4.6 Notes                                      109(1)
  5 Scheduling in wireless networks                110(32)
    5.1 Wireless communications                    110(4)
    5.2 Channel-aware scheduling in cellular       114(2)
    networks
    5.3 The MaxWeight algorithm for the            116(6)
    cellular downlink
    5.4 MaxWeight scheduling for ad hoc P2P        122(3)
    wireless networks
    5.5 General MaxWeight algorithms               125(4)
    5.6 Q-CSMA: a distributed algorithm for ad     129(5)
    hoc P2P networks
      5.6.1 The idea behind Q-CSMA                 129(1)
      5.6.2 Q-CSMA                                 130(4)
    5.7 Summary                                    134(1)
    5.8 Exercises                                  135(5)
    5.9 Notes                                      140(2)
  6 Back to network utility maximization           142(23)
    6.1 Joint formulation of the transport,        142(9)
    network, and MAC problems
    6.2 Stability and convergence: a cellular      151(4)
    network example
    6.3 Ad hoc P2P wireless networks               155(2)
    6.4 Internet versus wireless formulations:     157(2)
    an example
    6.5 Summary                                    159(1)
    6.6 Exercises                                  160(3)
    6.7 Notes                                      163(2)
  7 Network protocols                              165(30)
    7.1 Adaptive window flow control and TCP       166(9)
    protocols
      7.1.1 TCP-Reno: a loss-based algorithm       167(3)
      7.1.2 TCP-Reno with feedback delay           170(1)
      7.1.3 TCP-Vegas: a delay-based algorithm     171(4)
    7.2 Routing algorithms: Dijkstra and           175(7)
    Bellman-Ford algorithms
      7.2.1 Dijkstra's algorithm: link-state       176(3)
      routing
      7.2.2 Bellman-Ford algorithm:                179(3)
      distance-vector routing
    7.3 IP addressing and routing in the           182(4)
    Internet
      7.3.1 IP addressing                          183(1)
      7.3.2 Hierarchical routing                   184(2)
    7.4 MAC layer protocols in wireless networks   186(5)
      7.4.1 Proportionally fair scheduler in       187(1)
      cellular downlink
      7.4.2 MAC for WiFi and ad hoc networks       188(3)
    7.5 Summary                                    191(1)
    7.6 Exercises                                  192(2)
    7.7 Notes                                      194(1)
  8 Peer-to-peer networks                          195(32)
    8.1 Distributed hash tables                    195(12)
      8.1.1 Chord                                  196(6)
      8.1.2 Kademlia                               202(5)
    8.2 P2P file sharing                           207(3)
      8.2.1 The BitTorrent protocol                208(2)
    8.3 Structured P2P streaming                   210(5)
    8.4 Unstructured P2P streaming                 215(4)
    8.5 The gossip process                         219(2)
    8.6 Summary                                    221(1)
    8.7 Exercises                                  222(3)
    8.8 Notes                                      225(2)
II Performance analysis                            227(113)
  9 Queueing theory in continuous time             229(61)
    9.1 Mathematical background:                   229(8)
    continuous-time Markov chains
    9.2 Queueing systems: introduction and         237(2)
    definitions
    9.3 The M/M/1 queue                            239(2)
    9.4 The M/M/s/s queue                          241(1)
      9.4.1 The PASTA property and blocking        242(1)
      probability
    9.5 The M/M/s queue                            242(1)
    9.6 The M/GI/1 Queue                           243(6)
      9.6.1 Mean queue length and waiting time     246(1)
      9.6.2 Different approaches taken to          247(2)
      derive the P-K formula
    9.7 The GI/GI/1 queue                          249(2)
    9.8 Reversibility                              251(3)
      9.8.1 The M/M/1 queue                        253(1)
      9.8.2 The tandem M/M/1 queue                 254(1)
    9.9 Queueing systems with product-form         254(4)
    steady-state distributions
      9.9.1 The Jackson network                    255(1)
      9.9.2 The multi-class M/M/1 queue            256(2)
    9.10 Insensitivity to service-time             258(5)
    distributions
      9.10.1 The M/M/1-PS queue                    259(1)
      9.10.2 The M/GI/1-PS queue                   259(4)
    9.11 Connection-level arrivals and             263(4)
    departures in the internet
    9.12 Distributed admission control             267(2)
    9.13 Loss networks                             269(7)
      9.13.1 Large-system limit                    271(3)
      9.13.2 Computing the blocking                274(1)
      probabilities
      9.13.3 Alternative routing                   275(1)
    9.14 Download time in BitTorrent               276(4)
    9.15 Summary                                   280(2)
    9.16 Exercises                                 282(7)
    9.17 Notes                                     289(1)
  10 Asymptotic analysis of queues                 290(33)
    10.1 Heavy-traffic analysis of the             291(3)
    discrete-time G/G/1 queue
    10.2 Heavy-traffic optimality of JSQ           294(8)
    10.3 Large deviations of i.i.d. random         302(5)
    variables: the Cramer-Chernoff theorem
    10.4 Large-buffer large deviations             307(5)
    10.5 Many-sources large deviations             312(5)
    10.6 Summary                                   317(1)
    10.7 Exercises                                 318(3)
    10.8 Notes                                     321(2)
  11 Geometric random graph models of wireless     323(17)
  networks
    11.1 Mathematical background: the Hoeffding    323(2)
    bound
    11.2 Nodes arbitrarily distributed in a        325(3)
    unit square
    11.3 Random node placement                     328(7)
    11.4 Summary                                   335(1)
    11.5 Exercises                                 336(3)
    11.6 Notes                                     339(1)
References                                         340(9)
Index                                              349