Stochastic network utility maximization: Modeling, analysis and applications

An optimization-based approach to network resource allocation algorithms has gained extensive attention over the past decade, known as network utility maximization (NUM). However, these models' applicability is also limited for dynamic networks. This thesis aims at combining NUM with stochastic network theory and addressing a wide range of new questions in both formulations and solutions within the stochastic NUM framework.;For stochastic NUM on the flow-level, stability analysis has drawn extensive attention in the literature, as a fundamental performance metric of system dynamics. Two types of stability under different models are studied: queue stability under a Markovian traffic model and rate stability under a trace-based traffic model, respectively. For queue stability, when the rate region is non-convex or time-varying, the stability region depends on the fairness parameter alpha in alpha-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes. The tradeoff between fairness and stability when the rate region is non-convex or time-varying is further investigated. Similar results are also derived for rate stability via different proof techniques under a utility maximizing cone scheduling (UMCS) policy. In particular, a general concavity versus stability tradeoff is proved. Discussion on rate stability is also extended to some "exotic" utilities such as coupled utility or non-concave utility, which has rarely been studied.;The framework of stochastic NUM is also applied to random access designs for medium access control (MAC) in wireless networks. For slotted Aloha random access networks with multi-hop flow routes, a class of queue back-pressure random access algorithms (QBRA) is studied, in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities. The QBRA, combined with simple congestion control local to each source, leads to optimal end-to-end throughput allocation, within the network saturation throughput region achievable by random access without end-to-end message passing. Moreover, for the model with stochastic exogenous arrivals, QBRA ensures stability of the queues as long as nominal loads of the nodes are within the saturation throughput region.;On the other hand, following the state of the art on random access control without message passing, an algorithm of Jiang and Walrand is extended and a rigorous proof of utility-optimality for random access without message passing in a similar setting is provided. Then a more difficult discrete contention and backoff model with collisions is investigated in terms of its optimality properties, and the tradeoff between long-term efficiency and short-term fairness that emerges in this model is discussed.