| In this thesis, we extend the recently developed Lyapunov optimization technique (also known as Max-Weight or Backpressure) for stochastic queueing networks in two important directions: (1) guaranteeing small network delay; and (2) resolving underflows.;To achieve our objective, we first establish an explicit connection between the Lyapunov technique and a randomized dual subgradient method. Based on this connection, we develop a novel exponential attraction result, which states that the network queue backlog under a Lyapunov algorithm deviates from a certain fixed point with a probability that decreases exponentially in the deviation distance. Inspired by the exponential attraction result, we develop three delay-efficient algorithms and show that they achieve near-optimal utility-delay tradeoffs for a general class of multi-hop communication networks. One of the algorithms has also been implemented on a sensor network testbed and was shown to be able to guarantee very small network delay in practical systems.;We later consider the problem of resolving underflows in general complex network scheduling problems. In this case, we propose the weight perturbation technique and develop the Perturbed Max-Weight algorithm (PMW). We show that PMW effectively resolves underflow constraints without sacrificing utility performance. We then apply the perturbation technique to construct utility optimal scheduling algorithms for two important classes of networks---stochastic processing networks and energy harvesting networks.;The results developed in this thesis highlight the importance of Lagrange multiplier engineering in queueing networks. Specifically, our results show that the queues under the Lyapunov technique indeed correspond to the Lagrange multiplier values under the randomized dual subgradient method. This not only helps us better understand the Lyapunov technique, but also gives us general guidelines on how should one design its algorithm to achieve the desire properties of the queues. |
PDF Full Text Request