Optimization-based multi-tree multicast algorithms for content distribution
Ye Xia, Chunglae Cho · 2011
Massive content distribution has become one of the most important applications on the Internet. In this work, we present three algorithms for utility maximization problems using multiple multicast trees for content distribution. All of the algorithms are much decentralized and local. The operations are well distributed throughout the network components and there is no global exchange of control messages. We first consider the problem over a single-layer infrastructure network where infrastructure nodes are strategically placed by the providers and are well managed and relatively static. On this setting, we first present a virtual-queue-based multicast backpressure algorithm and provide a rigorous analysis of the performance including the primal optimality and the bound on real queue sizes using the Lyapunov optimization technique and the convex optimization techniques together. Next, we present a multicast backpressure algorithm using the real queue backlogs and provide a rigorous analysis to prove the optimality of the algorithm, using a fluid limit model. As an important byproduct, we show that the backpressure algorithm with real queues is exactly a subgradient algorithm in the fluid limit model. As our second problem, we consider the problem of content distribution among data servers over a two-layer network consisting of the overlay and underlay networks, where the control variables can be adjusted at both networks. We propose an optimal backpressure algorithm for content distribution over the layered network. The algorithm is well separated into the overlay and underlay operations such that the communication between the two layers only occurs locally at their interface. We show that our algorithm achieves optimality even when the two network layers operate under different timescales and without time synchronization. (Full text of this dissertation may be available via the University of Florida Libraries web site. Please check http://www.uflib.ufl.edu/etd.html)