SIGCOMM 2012 论文选读 - Optimizing Cost and Performance for Content Multihoming

session:
Session 8: Streaming and Content Networking

abstract:
Many large content publishers usemultiple content distribution networks to deliver their content, and many commercial systems have become available to help a broader set of content publishers to benefit from using multiple distribution networks, which we refer to as content multihoming. In this paper, we conduct the first systematic study on optimizing content multihoming, by introducing novel algorithms to optimize both performance and cost for content multihoming. In particular, we design a novel, efficient algorithm to compute assignments of content objects to content distribution networks for content publishers, considering both cost and performance. We also design a novel, lightweight client adaptation algorithm executing at individual content viewers to achieve scalable, fine-grained, fast online adaptation to optimize the quality of experience (QoE) for individual viewers. We prove the optimality of our optimization algorithms and conduct systematic, extensive evaluations, using real charging data, content viewer demands, and performance data, to demonstrate the effectiveness of our algorithms. We show that our content multihoming algorithms reduce publishing cost by up to 40%. Our client algorithm executing in browsers reduces viewer QoE degradation by 51%.

阅读笔记

本文研究的是“content multihoming”问题，即如何利用多个CDN来高效、省钱地提供内容给用户。文章主要从两个方面（publisher、viewer）研究了在对于不同内容选择CDN时候的算法，来优化cost和performance。
publisher主要面临的问题是：多家CDN对不同的内容收费不同（流量方案、带宽方案、功能、性能），该如何选择一个CDN来发布内容？提出的解决算法称为CMO。
本地的viewer则面临着：内容在多家CDN的不同服务器上都有提供，该选择哪个来提高用户体验（Quality of Experience，QoE）？
文章将这些问题抽象为优化问题（常见思路）。
所建立的模型中，利用一个集中式的优化器（central Optimizer），来响应对CDN的内容请求。根据请求客户端功能的不同，将客户端分为被动客户端和主动客户端。前者对某个内容只能连接到一台CDN服务器，因此，只能在server端进行优化。后者对一个内容可能利用多个CDN服务器。这样，当某台服务器服务能力不够时，主动客户端还可以利用其它的服务器。
因此，研究包括两个方面的优化，一个是服务器端的优化，一个是主动客户端的优化。
服务端优化问题最终抽象的模型是一个带有约束条件的最小优化问题。优化目标是整体的cost，约束条件是满足用户需求（Sec 5.1）。解决这一类问题的一般思路是线性规划或者凸优化。然而，当问题的规模比较大的时候，线性规划计算代价不可接受；目标函数是凹函数，无法直接进行凸优化。因此，作者提出可以转化为其他问题（分配问题），并进一步提出了优化的分配方案（考虑分配后的输出空间，使用凹优化），降低解决问题的复杂度。
在转化过程中，也应用了凸优化和凹优化的理论。近些年，类似优化理论以及图论理论在网络领域应用的越来越多，但国内相关领域还比较少见这方面的研究文章。
在主动客户端上，还借用了TCP的AIMD机制来进行流量调整。
在实验方面，采用了来自真实CDN的大量traffic做模拟。验证了提出的方案确实能降低cost。
整体来看，本文将一个实际问题成功抽象为理论问题。虽然模型比较简单，但解决的过程中降低复杂度的手法值得借鉴，体现出比较深的数学功底，同时对于阅读者数学背景要求也比较高。但部分细节说的不是太清楚，例如引理1并没有给出证明。