Mean-Variability-Fairness tradeoffs in resource allocation with applications to video delivery

Network Utility Maximization (NUM) provides a key conceptual framework to study reward allocation amongst a collection of users/entities in disciplines as diverse as economics, law and engineering. However when the available resources and/or users' utilities vary over time, reward allocations will tend to vary, which in turn may have a detrimental impact on the users' overall satisfaction or quality of experience. In this thesis, we introduce a generalization of the NUM framework which incorporates the detrimental impact of temporal variability in a user's allocated rewards and explicitly incorporates Mean-Variability-Fairness tradeoffs, i.e., tradeoffs amongst the mean and variability in users' reward allocations, as well as fairness across users. We propose a simple online algorithm to realize these tradeoffs, which, under stationary ergodic assumptions, is shown to be asymptotically optimal, i.e., achieves a long term performance equal to that of an offline algorithm with knowledge of the future variability in the system. This substantially extends work on NUM to an interesting class of relevant problems where users/entities are sensitive to temporal variability in their service or allocated rewards. We extend the theoretical framework and tools developed for realizing Mean-Variability-Fairness tradeoffs to develop a simple online algorithm to solve the problem of optimizing video delivery in networks. The tremendous increase in mobile video traffic projected for the future along with insufficiency of available wireless network capacity makes this one of the most important networking problems today. Specifically, we consider a network supporting video clients streaming stored video, and focus on the problem of jointly optimizing network resource allocation and video clients' video quality adaptation. Our objective is to fairly maximize video clients' video Quality of Experience (QoE) realizing Mean-Variability-Fairness tradeoffs, incorporating client preferences on rebuffering time and the cost of video delivery. We present a simple asymptotically optimal online algorithm NOVA (Network Optimization for Video Adaptation) to solve the problem. Our algorithm uses minimal communication, 'distributes' the tasks of network resource allocation to a centralized network controller, and video clients' video quality adaptation to the respective video clients. Further, the quality adaptation is also optimal for standalone video clients, and is an asynchronous algorithm well suited for use in the Dynamic Adaptive Streaming over HTTP (DASH) framework. We also extend NOVA for use with more general video QoE models, and study NOVA accounting for practical considerations like time varying number of video clients, sharing with other types of traffic, performance under legacy resource allocation policies, videos with variable sized segments etc.