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并没有给出证明。

SIGCOMM 2012 论文选读 - Surviving Failures in Bandwidth-Constrained Datacenters

Session:
Session 10: Data Centers: Network Resilience

Abstract:
Datacenter networks have been designed to tolerate failures of network equipment and provide sufficient bandwidth.  In practice, however, failures and maintenance of networking and power equipment often make tens to thousands of servers unavailable, and network congestion can increase service latency. Unfortunately, there exists an inherent tradeoff between achieving high fault tolerance and reducing bandwidth usage in network core; spreading servers across fault domains improves fault tolerance.

阅读笔记：

这篇文章延续了MS一贯的风格，从实践中发掘有趣的问题，提升到理论高度，并提出初步解法。

文章关注的问题是不太容易想到的。去年的SIGCOMM中有篇文章讨论了数据中心中如何进行资源分配，以降低核心网的带宽压力。本文敏锐的指出，降低带宽压力和提高容错性之间往往存在矛盾。要理解这个矛盾，就要从实际出发，分析网络流量。这也是写文章的一般思路。

首先，文章通过分析bing数据中心中的流量数据，发现了一些有趣的pattern。数据中心中的网络流量多发生在同一类服务之内，而非之间，并且存在着不均匀的情况。例如只有2%的服务对（service pairs）之间存在流量，98%的服务对之间不需要流量交换。同时，在发生的流量中，0.1%的服务对产生了60%的流量，4.8%的服务对产生了99%的流量。

有了这个观察，就可以给出一个直观的例子。例如一种应用的多个服务器，如果放在同一个TOR中，大量流量仅发生在内部，这降低了核心网的带宽压力。但是，一旦TOR的交换机发生故障，则所有服务器都无法提供服务；反之，如果分布在多个TOR，会提高容错性能，但需要利用核心网交换大量数据。

问题提出后，便可以进行建模。这是个典型的多目标优化问题。

进行优化的目标主要包括两点，容错（FT）、带宽（BW）。

其中容错又包括了网络、电力、制冷等多个方面，并提出了容错域和最坏存活性能（即发生最坏情况的单点故障后的服务率）。

带宽则主要是降低核心网的带宽压力。同时要考虑到实际的限制。

最后，虚拟机的迁移（#M）也是个很费资源的行为，所以要尽量的少迁移现有的虚拟机，将其作为限制条件。

分析单一目标的FT优化和BW优化自身都是NP-hard（一个是最大独立集问题，一个是最小割问题），因此，本文考虑的多目标自然也是很难的。这里的思路主要两点，一个是解决FT问题可以采用凸优化，局部解就是全局最优解了。同时由于流量分布十分稀疏，可能存在一些能利用的地方。比如迁移可能并不太改变BW。

文章提出了两套优化框架，FT + #M，以及FT + BW + #M。

考虑FT + #M，提出一个FTC（FT的惩罚函数）函数，是个凸优化，将存在不同TOR上的不同服务之间的虚拟机进行贪婪的swap（swap可以保证不同服务对应的虚拟机个数不变，并同时可以不提高对核心网的压力），尽量将它们分散在不同的TOR上，即可提高FT。

而对于FT + BW + #M，则没有那么简单，并不能保证取得比较优的解。可以通过一个系数\alpha来tradeoff两者。对这个问题也提出了两种算法。第一种算法是CUT+FT+BW的思路是首先，我们采用最小割算法来实现最小的BW，之后，通过迁移虚拟机试图最小化FTC（提高FT），并尽量降低BW的提高。第二种算法是FT+BW算法，仅执行第二步，在迁移虚拟机的时候同时考虑FTC和带宽的惩罚，最小化\delta{} FTC + \alpha{} \delta{}BW。

最后，实验在四个产品级的cluster上进行。结果表明CUT+FT+BW算法效果最好，降低了30-60%的核心网带宽，提高了40%-120%的容错性能。

总结下，本文最大的亮点，是第一次将带宽利用率和容错性结合到了一起进行讨论，同时，建模分析和解决思路也都有可取之处（设计符合凸优化的FTC）。当然，文章中使用的实际数据中心的采集数据也是不小的加分点。

OpenvSwitch 代码分析（零）

虚拟交换机是云计算和网络虚拟化的基础。
作为目前唯一一个事实上的标准，OpenvSwitch几乎占据了所有的优势。唯一一个开源的虚拟交换机软件实现（注意，竟然是产品级实现），集成到了大部分的云计算和虚拟化产品中，被主流厂商所追捧，支持SDN的相关协议……好了，更多的介绍还是自己看官方网站吧。
为什么要做软件交换机？并不是说软件交换机灵活、廉价，更重要的原因，云计算的发展太快了，SDN的发展太快了，大家对网络要求的发展太快了，硬件设计和制造的缓慢让像样的虚拟交换机迟迟无法release。能简单支持OpenFlow协议的交换机本身就屈指可数，更不要说在实际应用中的各种复杂需求了。
而OpenvSwitch偏偏做到了，在关键的时刻挺身而出。nicira能让vmware掏出10亿+的美金，除了高层的政治和寥寥数个核心的开发人员，很重要的就是它的两大产品——OpenvSwitch和Onix！Onix姑且不提，OpenvSwitch已经被开源届广泛关注并应用，其意义不下于操作系统届当年的minix甚至linux，大大小小的厂家都借鉴它来进行虚拟交换设备的开发。
因此，OpenvSwitch的源码设计，很值得大家仔细研究，无论是对交换的抽象和各个子功能的分离，以及考虑到扩展性的设计思想，甚至数据结构，每一个真正搞网络技术的人都很值得进行深入的分析。
考虑到国内对OpenvSwitch代码进行分析的人还不多，希望能抽空写个系列，谈谈OpenvSwitch设计上的一些独到之处。当然，很推荐大家直接阅读源码，只要具备一定的内核编程基础，并对网络协议栈的实现，特别Linux上的，有所熟悉，并能理解网络虚拟化和SDN的核心理念，应该问题还是不大的。从接触代码到打通流程，大概花了两三周的时间。当然，肯定还有不少细节之处没有完全理解透彻，需要进一步的探索。

智能算法与人生决策

最近研究智能算法，发现大部分算法都采用了所谓的启发式策略。

从下山法，到模拟退火，到蚁群，等等。

所有的智能算法，从模型上说，其核心都在于所采用的选择策略。

而选择策略，无非两类。

一类是根据已知信息（包括历史，当前信息，规律等）进行有目的的选择，或者说（智能的）启发式。

另外一类，不根据已知信息，进行选择，或者说（愚笨的）猜测。

有的算法，启发式信息用的多一些，应用的范围较广，取得的效果也不错。

一个比较有意思的现象是，对于很多问题来说，单纯的启发式的算法往往不能得到最优化的结果。适当的引入一些随机的抖动，反而效果可能更佳。

其实，所谓的道，是从生活中提炼出来的。

智能算法，也正是每个人做种种决策的方法雏形。

很多时候，我们做决策，都是根据已知条件选择最优的，所谓“人性贪婪”。这样的策略也被称为贪婪原则。这样决策的结果从算法分析的角度，被证明只能保证局部最优。

事实上也如此。经商的投机倒把，为官的滥用职权，虽取得一时的荣光或暴利，结果往往令人叹息。

而引入启发式信息，对已知条件进行充分的发掘，甚至总结规律，前瞻后顾，则可能在名利场中面面兼顾，取得的成就也自然更大。

但常规的问题往往都没有太好的方法，对于人生这个复杂的系统问题，启发式算法能起到的作用也是十分有限。即便看透世界大势，即便往前看个数十年，眼下做的决策，谁又能保证是全局最优的呢？

于是，我看到太多人，因为追求优化，反而限制了自身的发展。试图追求最优，却最终丧失了追求优化的资格。

所以有些时候，将智能的启发与随机的选择结合一下，未必要事事做到极致。凡事留有一线余地，有机的结合趋利性和对问题周边的探知。

人生决策，非大量的计算而不能。而即便有了大量的计算，也难以确保解答。

能走好人生路者，大智慧也。

OpenStack - 开源云计算项目

时下云计算如火如荼，众多企业纷纷推出云计算相关的应用，不少还搭建企业私有云和少数公有云（代表为Amazon）。然而，业界仍然缺乏一套实用的云计算管理平台，很大程度上提高了云计算应用的门槛，制约了云服务的发展。

作为开源的IaaS（Infrastructure as a Service）平台，OpenStack遵循Apache许可，其长期设计目标为同时服务公有云和私有云，提供统一的开源资源管理平台。

OpenStack是美国国家航空航天局（NASA）和Rackspace合作研制的云计算管理软件，最初目的是存储大量的空间视频、图片等信息，随着云计算需求的增长逐渐成长起来。

自2010年7月项目成立开始，OpenStack就收到广泛关注和支持。项目成员不乏业界巨头，包括Cisco、Citrix、HP、Intel、Dell、IBM、Microsoft等。其中Dell和HP公司还利用OpenStack创建了自己的云计算解决方案，当然，所使用的企业版本与开源版本有所区别。经过两年左右的发展，该项目已经吸引了超过160家公司和2600多名开发者，足可见认可程度。

目前，OpenStack项目由若干子项目组成，包括计算组件Nova、存储组件Swift、镜像管理组件Glance、认证组件Keystone、前台组件Horizon和网络管理组件Quantum。其中前三个组件是OpenStack的核心，经过长期开发和完善，已经较为成熟。大部分的组件都是松耦合联系，支持分布式，较好的保证了扩展性。

OpenStack在虚拟化技术上支持Xen、KVM、VMware、ESX、LXC、QEMU、UML等，并通过统一的虚拟层（Libvirt）来调用，实现底层对用户透明。对现有虚拟化技术较为全面的支持使得OpenStack可以被广泛部署在多种场景，而不用担心底层需要选取哪家技术实现。同时，OpenStack还支持亚马逊的EC2和S3的API，使得面向AWS（Amazon Web Services）开发的应用可以轻松的实现迁移。

OpenStack的版本命名与Ubuntu类似，按照字母顺序，分别为Austin、Bexar、Cactus、Diablo、Essex。最新版本为第五版的Essex，这一版经过了较长的开发周期。从第五版开始，OpenStack开始注意代码的质量和用户的体验，真正可以作为较为实用的云计算管理平台。

另外，根据最新的消息，OpenStack将在今年的4月16-18日在美国旧金山举办OpenStack Conference & Design Summit峰会，讨论该项目的未来发展，大家不妨略作关注。

客观地看，OpenStack对推动云计算的发展有着积极的作用（类似的项目包括OpenNebula、Eucalyptus等），但目前的版本，功能还比较简单，面向的群体也有限。同时，不支持网络虚拟化等新兴技术，在某种程度上制约了OpenStack的功能和性能。希望OpenStack在未来能更加完善，成为功能完善而又易用的云计算平台；也希望有更多的优质开源云计算项目能够成长起来，促进产业的发展。对OpenStack有兴趣的朋友可以尝试访问官方网站，或者trystack.org，简单注册后即可进行体验。