可扩展组播及其在数据中心网络中的应用

蒋长林 徐明伟 李丹

中图分类号：TN915.1文献标志码：A 文章编号：1009-6868 (2012) 04-0011-004

摘要：文章认为组播协议的可扩展性一直是阻碍组播技术广泛部署的重要因素之一，为此文章探讨了互联网环境下几种可扩展组播的解决方案：基于组成员稀疏分布的可扩展组播方案、基于布鲁姆过滤器的可扩展组播方案、基于聚合组播树的可扩展组播方案；数据中心网络中可扩展组播面临的新挑战主要来自于硬件限制导致无法同时容纳大量的组播组，同时基于组成员稀疏分布的可扩展组播方案和聚合组播树的方案在数据中心网中应用受限，为此文章探讨了数据中心网络环境下混合使用组播和单播的可扩展组播方案、基于布鲁姆过滤器的可扩展组播方案。

关键词： 可扩展组播；布鲁姆过滤器；数据中心网络

Abstract: Scalability of the multicast protocol is important when deploying multicast technology. This paper describes some scalable multicast solutions, including group-member-based sparse distribution, Bloom Filter, and tree-based aggregated multicasting. There are two particular issues in scalable multicasting in data center networks: the limited capacity of multicast group, and the limited applications for group-member-based sparse distribution and Bloom Filter. In this paper, we discuss unicast-multicast-mixed scalable multicasting and Bloom Filter-based scalable multicasting in the data center in more depth.

Key words: scalable multicast; Bloom Filter; data center network

网络层组播(IP Multicast)[1]最初是由Steve Deering于1988年提出，其主要思想是通过减少发送重复报文，提高网络带宽利用率，减少终端和路由器的处理负担，为多点通信提供一种高效的通信机制。虽然组播技术提出已经有20多年的时间，但组播技术始终未得到广泛的商用，其中可扩展性是一个很重要的原因[2]。

随着互联网的快速发展，云计算服务模式应运而生。作为云计算服务的核心组成部分，数据中心网络为执行运算的大量服务器之间提供路由和传输服务。虽然组播技术在互联网中的部署面临重重困难，但数据中心网络的特殊环境却为组播技术的应用提供了新的契机：

(1)数据中心网络中的大量应用具有组通信模式：如在线搜索引擎将搜索请求同时发向多台索引服务器，分布式文件存储系统将同一份文件数据同时备份到多台服务器上等等。应用组播技术能够大大节约网络带宽，降低运营成本。

(2)数据中心网络通常由单一的实体运营，通信多为内部节点之间的通信，而且收费机制也有别于因特网服务提供商(ISP)的收费机制。因此组播技术在数据中心网络中的应用不存在收费机制、安全性等部署障碍。然而数据中心网对组播的可扩展性也提出了新的挑战。

1 互联网可扩展组播研究

成果

本文从实现原理角度对互联网环境下可扩展组播的研究成果进行分类介绍。

1.1 基于组成员稀疏分布的可扩展

组播方案

组成员稀疏分布是指组播组的成员较分散地分布在网络中，导致组播树中仅有少数的节点从多个端口转发组播报文，这类节点被称作分枝节点。这类方案的核心思想是只在分枝节点中存储组播状态，其他节点不存储组播状态、按单播操作实现数据的转发，通过只在部分节点中保存组播状态保证可扩展性。动态隧道组播(DTM)、递归单播树(REUNITE)和逐跳组播路由协议(HBH)是这类方案的代表[3-6]。

DTM是第一个针对组成员稀疏分布提出的可扩展组播方案。DTM在使用IP层组播协议生成的组播树上创建隧道，隧道经过的路由器不保存组播状态。

REUNITE方案抛弃了组播地址，使用IP地址(第一个加入该组播组的成员地址)作为目标地址。REUNITE方案将组播路由信息分为两部分，一是存放于控制平面的组播控制表(MCT)和存储于数据平面的组播转发表(MFT)。

HBH方案的大致思想与REUNITE相同，但不同之处在于：HBH方案的MCT和MFT存储的目标地址可以是下一个分枝节点的地址，也可以是组成员的地址。而REUNITE方案的MCT和MFT存储的目标地址是组成员的地址。这样设计的目的是提高组播树的稳定性。

这类方案通过仅在分枝节点上保存组播状态实现可扩展组播。但在实际应用时存在以下问题：

(1)只适用于组成员分布稀疏的组播组。当组成员数目较大时，本类方案的可扩展性将大打折扣。

(2)组播状态都是软状态，通常需要组成员定期向组播源发送消息进行状态更新，组成员信息的维护开销较大。

1.2 基于Bloom Filter的可扩展组播

方案

这类方案应用布鲁姆过滤器(Bloom Filter)[7]压缩组播状态，提高可扩展性。根据Bloom Filter的存放位置，我们可以将这类方案分为两类：一类是将Bloom Filter存放在网络设备中的in-switch Bloom Filter可扩展组播方案，如捎带组播(FRM)[8]。另一类是将Bloom Filter存放在报文中的in-packet Bloom Filter方案，如面向应用的组播协议(AOM)[9]和支持线速转发的订阅/分发网络通信(LIPSIN)[10]方案。但Bloom Filter固有的假真现象会造成报文风暴、路由环路和重复流等后果[11]。降低假真现象的出现概率是这类方案亟需解决的问题。

1.2.1 In-switch Bloom Filter可扩展组播

方案

FRM是第一个使用Bloom Filter的组播方案，主要解决域间组播的可扩展性问题。FRM将组播组的管理与路由管理分开：每个自治域内的边缘路由器获得本域内的组播组信息后，通过扩展边界网关协议(BGP)报文将组播组信息放入其中、并公告给其他自治域。通过BGP报文的传播，源主机所在自治域的边缘路由器即可获知每个自治域内的组播组信息。通过合并到各个组播组所在自治域的单播路由完成路由计算。FRM将组播树信息放入每个报文中，使用源路由的方式进行路由。中间节点通过查看报文中的组播树信息确定路由。为了减少带宽占用，自治域内的组播组信息和组播树信息都使用Bloom Filter进行压缩。FRM通过两个技术减小假真现象：

(1)根据组播组的数量动态改变Bloom Filter的长度。

(2)在组播树枝很多的情况下，将组播树划分为多棵子树，并为一棵子树制作一个数据包拷贝。

FRM对拓扑信息和到达目标自治域的路径向量信息的准确性要求较高，但由于路径变化的传播比较缓慢、且BGP路由聚合也会丢失一部分路径向量信息，因此在实际应用中有一定的限制。另外，FRM对组播树的分割会造成相同的数据通过同一条网络，导致带宽利用率下降。

1.2.2 In-packet Bloom Filter可扩展组播

方案

AOM方案的实现机制是为每一个自治域指派一个路由器(DR)负责管理该自治域内的组播组信息。当DR发现本自治域中组播组有变化后，通过组成员更新(MUM)消息将最新的组播组信息发送给源主机。MUM传输过程中经过的中间自治域的DR会在本地维护转发信息。当MUM传送到源主机后，源主机会根据MUM消息内容在本地维护到每个组播组所有目标自治域DR的组播组列表(MGL)。源主机发送的每个报文都包含MGL信息。转发路由器根据MGL信息确定目标DR的信息，并根据单播路由确定转发路径。为了防止产生多余的流量，中间的路由器会更新MGL信息。为了节省传输过程中占用的带宽，MUM和MGL中的数据均通过Bloom Filter压缩。由于AOM仅保存DR信息，而不是为每个组都保存状态，因此能够极大地减少存储的信息。但是AOM对每个报文的处理开销较大，会增加报文的传输时延。

LIPSIN方案采用了类似FRM方案的源路由方式。LIPSIN为网络中每一条边分配一个全局唯一的标识(ID)号(同一条边，不同方向具有不同的ID号)。源主机根据网络拓扑和组成员的位置，计算出组播树。然后源主机会将组播树中所有边的ID信息压缩到Bloom Filter中，并放置在每一个报文中。中间节点通过比较报文中的Bloom Filter和每条备选转发链路的ID号即可确定转发路径。但是当组通信规模增大时，为了减少假真现象的发生，Bloom Filter的长度会增大，这样会大大降低带宽利用率。

1.3 基于聚合组播树的可扩展组播

方案

聚合树(AT)方案[12]的应用场景是域间组播。基于多棵跨域的组播树在某个自治域内有重叠这个发现，AT把某个自治域内重叠的组播树分枝进行聚合。在该自治域内仅保存聚合后的组播树信息，而不再为每个组播组都保存状态。通过这种操作，能够使自治域内需要保存的组播信息大大减少，提高组播可扩展性。但AT并未给出了一个计算域内聚合树的算法。而且在自治域边缘路由器存储的状态非但没有减少，反而增加了(因为既要保存每棵组播树信息，还需保存聚合树信息)。

2 数据中心网可扩展组播

方案

数据中心网不仅为用户提供在线搜索等前台应用，同时也运行多种后台计算，例如以MapReduce为代表的分布式计算引擎和以谷歌文件系统(GFS)为代表的分布式文件系统等等。数据中心网运行的分布式计算具有参与服务器数量多、服务器之间数据交互量大等特点。这些特点导致树型拓扑已经不能很好地满足当前的需求，主要原因是：

(1)随着网络规模的增加，树型拓扑的超额订购率会增大，顶层交换机会成为网络“瓶颈”。

(2)树型拓扑对顶层网络设备的吞吐量要求很高，随着网络规模的增大，构建成本也会不断增加。

(3)无法为任意两台服务器提供非阻塞通信。针对这些问题，学术界和工业界提出了若干解决方案。这些方案大概可以分为3类：第一类是以交换机为核心的拓扑方案，代表是Fat-Tree、VL2和PortLand；第二类是以服务器为核心的拓扑方案，代表是DCell、BCube、FiConn和CamCube；第三类是融合了分组交换网络和电路交换网络的混合型拓扑方案，Helios和c-Through属于这类方案。

虽然这些拓扑方案很好地解决了数据中心网络的可扩展性问题，为任意两台服务器之间提供了较充足的带宽，能够更好地支持数据中心网络中典型的one-to-several、one-to-all和all-to-all等流量模式。但由于分布式计算需要在服务器之间传输大量的数据，以及服务器性能的不断提高(如多核CPU的广泛应用)，导致网络仍然是分布式计算的“瓶颈”。由于数据中心网中存在大量组通信模式，因此应用组播技术能够有效地减少网络中传输的数据量，对实现动态大规模计算和存储、提高企业经济效益和建设绿色家庭都有着非常积极的意义。同时，数据中心网络的以下特点为设计更有效的组播协议提供了有利的条件：

(1)新型拓扑都比较规整，有利于简化路由设计。

(2)网络规模较互联网小。

(3)可控性强。设计和部署新协议时几乎不用考虑增量部署、协议兼容性等问题。

但数据中心网络对组播的可扩展性提出了新的挑战：目前的设计趋势是使用低端网络设备构建数据中心网络。

然而绝大部分互联网环境中可扩展组播的解决方案在数据中心网络环境中并不适用：一方面，在任务分配时，通常将组成员分配在物理位置靠近的区域，组成员的分布通常不再呈现稀疏分布，因此互联网中基于组成员稀疏分布的可扩展组播方案不能直接用于数据中心网中；另一方面，数据中心网络是一个富连接的网络，任意一对主机之间可能存在多条等价路径，因此聚合组播树的方案在数据中心网中也行不通。

目前学术界在数据中心网络环境下提出的可扩展组播的解决方案大致可以分为两类：一类是将组播应用映射为网络层组播和单播，代表方案是MCMD[13]；一类是沿用互联网的解决思路，采用Bloom Filter解决组播可扩展性问题，例如文献[14]所述和多级布鲁姆过滤器(MBF)[15]。

2.1 混合使用组播和单播的可扩展

组播方案

MCMD方案的核心思想是利用数据中心网络特殊的网络环境，采用文献[16]提出的控制平面公告组成员信息，实现全网范围内组播信息的松散一致。针对大量使用组播地址、造成网络设备组播转发表超出硬件限制的问题，MCMD优化了组播地址的使用：根据硬件资源的限制、组播组的规模和设置的策略，把应用层组播地址翻译为网络层组播地址或一组单播地址，从而大大减少网络设备中组播转发表的条目，提高组播协议的可扩展性。

MCMD方案具有以下特点：

(1)可扩展性强，可以进行策略设置(例如决定每个组播组的成员数量或是否禁止使用IP组播)。

(2)对应用层透明，无需升级硬件，易于部署。

(3)容错性好。但由于MCMD是将部分组播通信映射为一组单播通信，不可避免地会造成带宽浪费。

2.2 基于Bloom Filter的可扩展组播

方案

李丹等提出了一种基于Bloom Filter的可扩展组播方案。该方案采用了与MCMD类似的思想，对组播组区别对待：对成员较多的组播组使用传统的往交换机中注入路由转发表的方式实现组播，对成员较少的组播组采用在in-packet Bloom Filter实现组播。因为数据中心网络中的大多数组播的成员都较少，因此采用这种机制能够在满足传输效率的前提下提高组播的可扩展性。

虽然Bloom Filter能够有效提高组播方案的可扩展性，但其假真特性总会造成流量泄露。众所周知，Bloom Filter的标准实现是为每一个插入元素使用相同数目的哈希(Hash)函数。然而李丹等通过理论分析和实验发现对于相同的一批插入元素，如果为每个元素分配不同数量的哈希函数，结果产生的假真现象比率会比标准Bloom Filter低。基于这个发现，李丹等提出了MBF降低假真现象的发生概率。MBF的核心思想是按照每个组播组的出现概率相应地指定哈希函数的个数：为出现概率大的组分配较少数量的哈希函数，而为出现概率小的组分配较多数量的哈希函数。通过为不同组播组分配不同个数的哈希函数达到降低假真现象的目的。

3 总结与展望

组播技术虽然提出已有20多年的历史了，但由于可扩展性等原因一直未得到广泛的应用，这也促使学术界对可扩展组播技术进行了广泛深入的研究。在互联网环境中，按照实现原理大致可以将可扩展组播方案分为3类，分别是基于组成员稀疏分布、基于Bloom Filter和基于聚合组播树的方案。

近年来，随着云计算的推广，在数据中心网络中普遍存在组通信模式，这为组播技术的应用提供了一个非常好的平台。然而数据中心通常使用存储容量和计算能力都较小的低端网络设备构建数据中心网络。随着网络规模的增长，组播的可扩展性问题面临更严峻的挑战。目前主要的研究成果大都采用基于Bloom Filter实现可扩展组播。

我们认为数据中心网中的可扩展组播研究的未来方向包括：

(1)借鉴互联网中成功的设计经验，分离组播组的管理与路由管理，简化方案设计。

(2)应利用数据中心网络规整的拓扑结构优化组播设计。文献[14]根据近几年提出的多级图拓扑(如BCube、Portland和VL2)提出了一种由源主机驱动的高效的组播树创建方法，有效减少组播树中的节点数量。

(3)设计时应充分考虑应用特点。数据中心网络的应用不如因特网多样化(比如某些数据中心网络内部运行的应用大都采用MapReduce编程模型)，可以根据应用的特点定制组播方案。

4 参考文献

[1] ALMEROTH K C. The evolution of multicast: From the MBone to interdomain multicast to Internet2 deployment [J]. IEEE Network, 2000,14(1): 10-20.

[2] HOLBROOK H W, CHERITON D R. IP multicast channels: EXPRESS support for large-scale single-source applications [C]//Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication(SIGCOMM99): Vol 1, Aug 30-Sep 3, 1999, Cambridge, MA,USA. New York, NY,USA:ACM, 1999: 65-78.

[3] TIAN J, NEUFEL G. Forwarding state reduction for sparse mode multicast communication [C]//Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM98):Vol 2, Mar 29-Apr 2,1998, San Francisco, CA,USA. Piscataway, NJ, USA:IEEE, 1998:711-719.

[4] STOICA I, NG T S E, ZHANG H. REUNITE: A recursive unicast approach to multicast [C]//Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (InFOCOM00):Vol 3, Mar 26-30,2000, Tel Aviv, Israel. Piscataway, NJ, USA:IEEE, 2000:1644-1653.

[5] CHO T W, RABINOVICH M, RAMAKRISHNAN K K, et al. Enabling content dissemination using efficient and scalable multicast [C]//Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM09), Apr 19-25,2009, Rio de Janeiro, Brazil. Piscataway, NJ, USA: IEEE, 2009:1980-1988.

[6] COSTA L H M K, FDIDA S, DUARTE O C M B. Hop by hop multicast routing protocol [C]//Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication(SIGCOMM01), Aug 27-31,2001, San Diego, CA, USA. New York, NY, USA:ACM, 2001:249-259.

[7] Bloom Filter [EB/OL]. [2012-05-19]. http://en.wikipedia.org/wiki/Bloom_filter.

[8] RATNASAMY S, ERMOLINSKIY A, SHENKER S. Revisiting IP multicast [C]//Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06), Sep11-15, 2006, Pisa, Italy. New York, NY, USA:ACM, 2006: 15-26.

[9] TIAN X, CHENG Y, LIU B. Design of a scalable multicast scheme with an application--Network cross-layer approach [J]. IEEE Transactions on Multimedia, 2009,11(6): 1160-1169.

[10] JOKELA P, ZAHEMSZKY A, ROTHENBERG C E, et al. LIPSIN: Line speed publish/subscribe inter-networking [C]//Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM09), Aug 17-21, 2009, Barcelona, Spain. New York, NY, USA: ACM, 2009: 195-206.

[11] SARELA M, ROTHENBERG C E, AURA T, et al. Forwarding anomalies in Bloom filter-based multicast [C]//Proceedings of the 30th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM11), Apr 10-15, 2011, Shanghai, China. Piscataway, NJ, USA: IEEE, 2011: 2399-2407.

[12] FEI A, CUI J, GERLA M, et al. Aggregated multicast: An approach to reduce multicast state [C]//Proceedings of the Global Telecommunications Conference (GLOBECOM '01):Vol 3, Nov 25-29,2001, San Antonio, TX, USA. Piscataway, NJ, USA: IEEE, 2001: 1595-1599.

[13] VIGFUSSON Y, ABU-LIBDEH H, BALAKRISHNAN M, et al. Dr. multicast: Rx for data center communication scalability [C]//Proceedings of the 2nd Workshop on Large-scale Distributed Systems and Middleware (LADIS '08),Sep 15-17,2008, Yorktown, NY, USA. New York, NY, USA:ACM, 2008.

[14]LI D, YU J W,YU J B, et al. Exploring efficient and scalable multicast routing in future data center networks [C]//Proceedings of the 30th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM11), Apr 10-15, 2011, Shanghai, China. Piscataway, NJ, USA: IEEE, 2011: 1368-1376.

[15] LI D,CUI H G, HU Y, et al. Scalable data center multicast using multi-class Bloom filter [C]//Proceedings of the 19th IEEE International Conference on Network Protocols (ICNP11),Oct 17-20,2011, Vancouver, Canada. Los Alamitos, CA, USA: IEEE Computer Society, 2011:266-275.

[16] VAN RENESSE R, MINSKY Y, HAYDEN M. A gossip-based failure detection service [C]//Proceedings of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing(Middleware98),Sep 15-18,1998, Lake Dist, UK. 1998:55-70.

收稿日期：2012-05-07

作者简介

蒋长林，清华大学计算机系在读博士研究生；研究领域为计算机网络和数据中心网络；已发表论文1篇。

徐明伟，清华大学计算机科学与技术系博士毕业；清华大学计算机系教授、博士生导师；研究领域为计算机网络体系结构、互联网路由和高性能路由器；已发表论文100余篇。

李丹，清华大学博士毕业；清华大学计算机系副教授；研究领域为计算机网络和数据中心网络；已发表论文30余篇。