AbstractsComputer Science

Resource allocation in stochastic processing networks : performance and scaling

by Yuan Zhong




Institution: MIT
Department: Operations Research Center
Degree: PhD
Year: 2012
Keywords: Operations Research Center.
Record ID: 1942491
Full text PDF: http://hdl.handle.net/1721.1/77828


Abstract

This thesis addresses the design and analysis of resource allocation policies in largescale stochastic systems, motivated by examples such as the Internet, cloud facilities, wireless networks, etc. A canonical framework for modeling many such systems is provided by "stochastic processing networks" (SPN) (Harrison [28, 29]). In this context, the key operational challenge is efficient and timely resource allocation. We consider two important classes of SPNs: switched networks and bandwidth-sharing networks. Switched networks are constrained queueing models that have been used successfully to describe the detailed packet-level dynamics in systems such as input-queued switches and wireless networks. Bandwidth-sharing networks have primarily been used to capture the long-term behavior of the flow-level dynamics in the Internet. In this thesis, we develop novel methods to analyze the performance of existing resource allocation policies, and we design new policies that achieve provably good performance. First, we study performance properties of so-called Maximum-Weight-[alpha] (MW-[alpha]) policies in switched networks, and of a-fair policies in bandwidth-sharing networks, both of which are well-known families of resource allocation policies, parametrized by a positive parameter [alpha] > 0. We study both their transient properties as well as their steady-state behavior. In switched networks, under a MW-a policy with a 2 1, we obtain bounds on the maximum queue size over a given time horizon, by means of a maximal inequality derived from the standard Lyapunov drift condition. As a corollary, we establish the full state space collapse property when [alpha] > 1. In the steady-state regime, for any [alpha] >/= 0, we obtain explicit exponential tail bounds on the queue sizes, by relying on a norm-like Lyapunov function, different from the standard Lyapunov function used in the literature. Methods and results are largely parallel for bandwidth-sharing networks. Under an a-fair policy with [alpha] >/= 1, we obtain bounds on the maximum number of flows in the network over a given time horizon, and hence establish the full state space collapse property when [alpha] >/= 1. In the steady-state regime, using again a norm-like Lyapunov function, we obtain explicit exponential tail bounds on the number of flows, for any a > 0. As a corollary, we establish the validity of the diffusion approximation developed by Kang et al. [32], in steady state, for the case [alpha] = 1. Second, we consider the design of resource allocation policies in switched networks. At a high level, the central performance questions of interest are: what is the optimal scaling behavior of policies in large-scale systems, and how can we achieve it? More specifically, in the context of general switched networks, we provide a new class of online policies, inspired by the classical insensitivity theory for product-form queueing networks, which admits explicit performance bounds. These policies achieve optimal queue-size scaling, in the conventional heavy-traffic…