Tuesday, September 25, 2012

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,提出一个FTCFT的惩罚函数)函数,是个凸优化,将存在不同TOR上的不同服务之间的虚拟机进行贪婪的swapswap可以保证不同服务对应的虚拟机个数不变,并同时可以不提高对核心网的压力),尽量将它们分散在不同的TOR上,即可提高FT
而对于FT + BW + #M,则没有那么简单,并不能保证取得比较优的解。可以通过一个系数\alphatradeoff两者。对这个问题也提出了两种算法。第一种算法是CUT+FT+BW的思路是首先,我们采用最小割算法来实现最小的BW,之后,通过迁移虚拟机试图最小化FTC(提高FT),并尽量降低BW的提高。第二种算法是FT+BW算法,仅执行第二步,在迁移虚拟机的时候同时考虑FTC和带宽的惩罚,最小化\delta{} FTC + \alpha{} \delta{}BW
最后,实验在四个产品级的cluster上进行。结果表明CUT+FT+BW算法效果最好,降低了30-60%的核心网带宽,提高了40%-120%的容错性能。
总结下,本文最大的亮点,是第一次将带宽利用率和容错性结合到了一起进行讨论,同时,建模分析和解决思路也都有可取之处(设计符合凸优化的FTC)。当然,文章中使用的实际数据中心的采集数据也是不小的加分点。