Scheduling and Congestion Control for Wireless and Processing Networks

Book description

In this book, we consider the problem of achieving the maximum throughput and utility in a class of networks with resource-sharing constraints. This is a classical problem of great importance. In the context of wireless networks, we first propose a fully distributed scheduling algorithm that achieves the maximum throughput. Inspired by CSMA (Carrier Sense Multiple Access), which is widely deployed in today's wireless networks, our algorithm is simple, asynchronous, and easy to implement. Second, using a novel maximal-entropy technique, we combine the CSMA scheduling algorithm with congestion control to approach the maximum utility. Also, we further show that CSMA scheduling is a modular MAC-layer algorithm that can work with other protocols in the transport layer and network layer. Third, for wireless networks where packet collisions are unavoidable, we establish a general analytical model and extend the above algorithms to that case.

Stochastic Processing Networks (SPNs) model manufacturing, communication, and service systems. In manufacturing networks, for example, tasks require parts and resources to produce other parts. SPNs are more general than queueing networks and pose novel challenges to throughput-optimum scheduling. We proposes a "deficit maximum weight" (DMW) algorithm to achieve throughput optimality and maximize the net utility of the production in SPNs.

Table of Contents: Introduction / Overview / Scheduling in Wireless Networks / Utility Maximization in Wireless Networks / Distributed CSMA Scheduling with Collisions / Stochastic Processing networks

Table of contents

  1. Preface
  2. Introduction
  3. Overview
    1. A Small Wireless Network
      1. Feasible Rates
      2. Maximum Weighted Matching
      3. CSMA
      4. Entropy Maximization
      5. Discussion
    2. Admission Control
    3. Randomized Backpressure
    4. Appendix
    5. Summary
  4. Scheduling in Wireless Networks
    1. Model and Scheduling Problem
    2. CSMA Algorithm
    3. Idealized Algorithm
      1. CSMA Can Achieve Maximal Throughput
      2. An idealized distributed algorithm
    4. Distributed Algorithms
      1. Throughput-Optimal Algorithm 1
      2. Variation: Constant Update Intervals
      3. Time-invariant A-CSMA
    5. Maximal-Entropy Interpretation
    6. Reducing Delays: Algorithm 1(b)
    7. Simulations
      1. Time-invariant A-CSMA
      2. Time-varying A-CSMA
    8. Proof Sketch of Theorem 3.10-(i)
    9. Further Proof Details of Theorem 3.10-(i)
      1. Property 3.21
      2. Property 3.22: Noise
      3. Property 3.22: Bias
    10. Proof of Theorem 3.10-(ii)
    11. Proof of Theorem 3.13
    12. General Transmission Times
    13. Appendices
      1. Proof of the fact that C is the interior of
      2. Proof the Proposition 3.7
    14. Summary
    15. Related Works
      1. Maximal-weight scheduling
      2. Low-complexity but sub-optimal algorithms
      3. Throughput-optimum algorithms for restrictive interference models
      4. Random Access algorithms
  5. Utility Maximization in Wireless Networks
    1. Joint Scheduling and Congestion Control
      1. Formulation of Optimization Problem
      2. Derivation of Algorithm
      3. Approaching the Maximal Utility
    2. Extensions
      1. Anycast
      2. Multicast with Network Coding
    3. Simulations
    4. Properties of Algorithm 3
      1. Bound on Backpressure
      2. Total Utility
      3. Queue Lengths
    5. Summary
    6. Related Works
  6. Distributed CSMA Scheduling with Collisions
    1. Introduction
    2. CSMA/CA-Based Scheduling with Collisions
      1. Model
      2. Notation
      3. Computation of the Service Rates
    3. A Distributed Algorithm to Approach Throughput-Optimality
      1. CSMA Scheduling with Collisions
    4. Reducing Delays
    5. Numerical Examples
    6. Proofs of Theorems
      1. Proof of Theorem 5.1
      2. Proof of Theorem 5.2
      3. Proof of Theorem 5.4
    7. Summary
    8. Related Works
  7. Stochastic Processing networks
    1. Introduction
    2. Examples
    3. Basic model
    4. DMW scheduling
      1. Arrivals that are smooth enough
      2. More random arrivals
    5. Utility maximization
    6. Extensions
    7. Simulations
      1. DMW scheduling
      2. Utility maximization
    8. Summary
    9. Skipped proofs
      1. Proof of Theorem 6.5
      2. Proof of Theorem refthm:rate-stable
      3. Proof of Theorem 6.8
      4. Proof of Theorem 6.9
  8. Stochastic Approximation
    1. Gradient algorithm
    2. Stochastic approximation
    3. Summary
    4. References
  9. Bibliography (1/2)
  10. Bibliography (2/2)
  11. Authors' Biographies
  12. Index

Product information

  • Title: Scheduling and Congestion Control for Wireless and Processing Networks
  • Author(s): Libin Jiang, Jean Walrand
  • Release date: October 2010
  • Publisher(s): Morgan & Claypool Publishers
  • ISBN: 9781608454624