DCN 中基于流量最小化的多播数据传输方案

许志聪

（广东工程职业技术学院 实训中心，广东 广州510520）

0 引 言

根据微软公司的测量结果，架顶式交换机的数据流量非常大，可能严重影响网络性能［1］。为了缓解传统有线数据中心网络的问题，人们引入了低成本、高数据率的60GHz无线技术 （比如802.11ad），以补充网络容量，实现快速连通。在无线数据中心的每个机架顶部，均有无线访问点和有线交换机共存。基于架顶的多播数据可以通过无线接入点或有线交换机进行传输。虽然树结构是传输多播数据的有效拓扑结构，但是如何为无线数据中心构建高效的树是一个非常复杂的技术问题。具体原因如下：①因为无线接入点在数据中心的部署密度很大，必须要仔细考虑无线接入点间的干扰问题；②与有线传输相比，无线媒介是广播型媒介，更适合于多播。与有线交换机不同的是，无线接入点可以把数据传输给在其通信范围内的多个访问点，传输路径也有多种选择，尤其是采用有向天线时更是如此；③如果在无线数据中心采用有线链路，同时传输多个无线访问点，则无线和有线链路共存，此时又会无线干扰。

1 相关工作

为了实现群组通信，人们通过多播来把数据传输给多个目的地。文献 ［2］为了在无线多播网络中提高系统吞吐量，提出了一种新型的多播组间公平的无线资源分配方案。方案在保证公平分配无线资源的前提下，运用设置平均误块率门限的方法，在系统的多用户分集增益和多播增益之间找到了最佳平衡，从而提高了系统的吞吐量。文献 ［3］根据节点的当前信道状态信息 （CSI）和接收节点已接收数据状态信息 （DSI），提出了一种基于信道预测多播速率选择算法 （MDCP）来最小化传输延迟，并结合网络编码提高数据传输效率。仿真结果表明，与基于最差信道状态节点的多播速率选择算法和没有信道预测的基于最大延迟节点的多播速率选择算法相比，MDCP能够获得10%～20%延迟增益。文献 ［4］提出了一种组内资源分配算法。在考虑用户之间不同速率需求的前提下，通过子载波分配和功率分配实现了组内用户多播传输的归一化速率最大化。仿真结果表明，与传统多播组内资源分配方案相比，显著提升多播系统的归一化速率。

另外，文献 ［5］提出了一种支持多速率多播传输的Ad－Hoc网络资源分配算法，它通过引入基于价格的流量分配方案来解决多速率多播传输问题，从而能够自适应地分配网络流量，并且最大化网络流的总效用。文献 ［6］提出了一种基于分段效用函数和判决机制的自适应多播控制算法 （AMC），仿真结果表明，AMC 对移动Ad－Hoc网络状态改变具有优良的自适应性能，尤其适用动态网络的异构分层多播业务流。然而，上述无线多播路由算法不能用于无线数据中心网络。这是因为，在无线数据中心网络中，无线访问点的部署密度非常高，导致干扰比较严重。同时，在无线数据中心，相比于无线Ad－Hoc网络，有线和无线链路共存条件下的连通性问题更为复杂。

最近，部分研究人员开始关注传统有线数据中心的多播问题。在文献 ［7］中，鉴于在支持交换机多播操作时的硬件约束，Vigfusson等提出了一种多播传输群组通信请求选择机制，该机制在多播传输时选择部分群组通信请求，其余请求通过单播传输完成。然后，文献 ［8］指出，如果为互联网设计的数据中心网络的连接密度较大，且基于接收方驱动的多播路由协议生成多条等成本路径，则这种数据中心网络在传输链路数量方面的性能较差。因此，作者提出了有线数据中心网络的高效多播路由方法，以降低数据传输的冗余度。然而，提出的路由方法无法兼容现代数据中心网络的无线链路。此外，该方法只将降低所用的有线链路总数量作为其主要性能指标，没有考虑异质云服务会请求不同的数据率。鉴于此，本文在已有研究工作的基础上，提出了一种基于流量最小化的多播数据传输方案，并通过仿真实验验证了本文方案的有效性。

2 系统模型和问题阐述

2.1 系统模型

对传统的数据中心，多个服务器放于一个机架上，每个机架配置一个交换机，交换机称为架顶交换机 （top－ofrack switch），且机架上的所有服务器与其相连。架顶交换机往往基于分层拓扑、Fat－tree树或BCube［9］等架构通过汇聚交换机或核心交换机相连。然而，传统数据中心的部署成本和复杂度过高。最近，微软采用了60GHz无线访问技术在每个架顶交换机上部署一个无线访问点，以补充网络容量，实现快速连通［2］。60GHz访问点可以支持10m 传输范围内的高数据率。因为数据中心内访问点的部署密度非常高，所以采用窄波束天线阵列有向天线来缓解干扰［10］。图1给出了一个简单的无线数据中心架构示例。图中共有12个机架，每个机架配置一个架顶交换机和一个无线访问点。每个架顶交换机通过有线与汇聚/核心交换机相连，而每个架顶访问点可以将数据发往其通信范围内的任意访问点。

图1 无线数据中心架构示例

因为提供云服务的协调式应用必须要进行群组通信，所以无线数据中心网络也必须要进行多播数据传输。多播数据传输通过树结构完成。多播树构建分为两类［11］：基于数据源型和基于共享型。因为数据中心的大多数群组通信在每个多播群组内只有一个多播发送方，所以为不失一般性，我们在本文中考虑基于数据源的树构建方法。

2.2 问题描述

本节讨论基于资源且由无线数据中心网络有线和无线链路组成的多播树构建问题。目的是使总多播数据流量最小化 （即总体数据冗余度）。问题阐述如下。出于简便考虑，如果表达意思结合上下文非常明确时省略""符号。

我们考虑一组N 个多播群组 ＝（r1，r2，…，rN），其中rk＝（vk，Tk）表示机架vk是多播群组k 的发射机且必须以Tk（bps）数据率把多播流量发送给多个 （机架）。然后，我们定义lF（k）∈｛0，1｝为指示函数，如果多播群组k的流量通过有线链路则函数为1。如果使用有线链路且lF（k，eFsisj）设为1，则机架j∈ 的架顶交换机sj可以接收到多播数据。我们同时定义lW（k）∈｛0，1｝以表明多播群组k 的流量是否使用无线链路。如果使用了无线链路且lW（k，）设为1，则在传输覆盖范围内的一组机架访问点会窃听和接收数据。我们的目的就是为每个多播群组构建一个由有线和无线链路组成的多播树。如果以下约束满足，则可以构建多播树：

有线链路容量约束：为了避免架顶交换机过度使用，式（1）可保证多播群组通过各条有向链路的数据率不会超过每条有向链路的可用容量

访问点容量约束：因为无线访问点会对周围其它访问点造成干扰，所以式 （2）保证各个访问点在数据接收和传输时不会超过其容量。通过使用I（ay，）以表明访问点ay是否被访问点ax干扰，且I（ay）的定义以基于几何学的协议干扰模型［12］为基础。根据该模型，当访问点ay位于访问点ax向访问点az传输数据时的传输范围内时，I（ay，）＝1

传输约束：每个多播群组的目的地必须要接收它们的多播数据

我们现在定义目标问题如下：

高效的多播树构建问题

输入实例：考虑一个有向图G＝（V，E）。每条有线和无线链路的容量为和。有一组包括N 个多播群组的集合 。

目标：我们的目标是为每个多播群组构建由有线链路lF（k，）和无线链路lW（k，）组成的多播树，以实现所有多播群组多播数据流量 （数据冗余）最小化

且约束条件为式 （1）～式 （3）。表1总结了问题描述时用到的标记法。

表1 标记法总结

3 多播数据高效传输

本节通过NP 难题属性已经得到证明的划分约简问题［13］来证明本文问题的NP 难题属性，并提出一种高效的启发式求解算法。

3.1 问题的NP难题属性

定理1 多播树高效构建问题是NP难题。

已知划分问题的一个实例 〈B〉，我们阐述当且仅当存在M 个总体数据流量为的多播树时，如何在多项式时间内构建本文问题的〈，，， ，N〉实例才能对均分。构建方法如下：在一个无线数据中心有两个机架，上面有两个架顶交换机＝2和两个架顶无线访问点＝2。只通过1条有线链路和1条无线链路将一个机架连接到另一个机架 （即F＝，｝且W＝，｝）。每 条 有 线 和 无 线 链 路 的 容 量 设 为（即有一个包括M 个多播群组的集合 （即N＝M ）。M 个多播群组的多播数据全部从同一机架 （源）发往其它机架 （目的地）。多播群组m 的数据率设为Tm＝bm，1≤m ≤M 。

为了完成证明过程，我们将证明通过两个分割子集可以获得总数据流量为Tm＝bm，1≤m ≤M 的M 个多播树，反之亦然。如果有两个分割子集，每个整数bm对应于多播群组m 要求的数据率Tm。一个子集对应于分配给有线链路的多播群组的数据率，另一个子集对应于无线链路传输的另一多播群组的数据率。因此，M 个多播树的总体数据流量为另一方面，如果M 个多播树的总体数据流量为则有线链路和无线链路必须分别传输数据率。这表明，通过将对应的整数分配给对应的子集，便可对集合均匀划分。划分问题存在多项式时间算法，表明本文问题也存在多项式算法，问题得证。

3.2 算法描述

本节给出一种算法，可以为所有多播群组高效构建由有线链路和无线链路组成的多播树。该算法的思路是搜索可以覆盖尽量多目的地的无线访问点，以降低多播流量的数据冗余。然后，我们寻找由有线链路和无线链路组成的最短路径，以便将每个数据源与其目的地相连。此外，为了尽量降低链路使用数量，我们对每条最短路径尽可能优先使用无线链路。如果无线链路无法支持数据传输，则使用有线链路。此外，为了高效利用每条链路的容量，我们在构建多播树时为数据率较大的多播树赋予较高优先级。

本文算法的伪代码见算法1。在第1行，使用指示函数lF（k，）来记录是否分配有线链路传输多播群组k 的数据，且初始化为0，1≤k≤N，∈F。在第2行，使用指示函数lW（k）记录是否分配无线链路传输多播群组k的数据，且初始化为0，1 ≤k ≤N。在第3行，利用初始化为0的变量Pk来记录多播群组k 的优先级。如果多播群组k 的优先级Pk较高，则我们应该优先为该多播群组构建多播树。在第4行，使用集合记录哪些无线链路可用于传输多播群组k 的流量。在第5行，使用集合来记录多播群组k 有多少个目的地可以窃听到目的地 （机架）访问点传输的多播数据。在第6 行，使用集合来表示多播群组k 有多少个目的地可以接收到数据且初始化为。

然后，算法开始为每个多播群组构建由有线链路和无线链路组成的多播树 （第7～29行）。对每个多播群组k，因为无线数据中心往往采用窄波束有向天线，所以我们假设每个无线访问点ax（x ∈νk）试图把多播群组k的数据传输给每个无线访问点ayyvk，且计算有多少个目的地可以接收到数据 （第7～13行）。在第10～11行，如果机架x 的访问点ax可以把数据传输给机架y 的访问点 （即），则有一组目的地可以接收到数据（即）。且集合更新为）。在第12行，可用于传输多播群组k的无线链路被加入集合。当尝试遍历玩所有目的地访问点对后，将多播群组k的优先级Pk设为Tk×（第13 行）。也就是说，如果可以窃听到无线访问点传输的数据的目的地增多且多播群组k 的流量数据率更高，则可进一步降低数据冗余。因此，我们优先为这种多播群组构建多播树且使用无线访问点。

所有多播群组的优先级设置完毕后，我们通过降低Pk（1≤k≤N）的属性来重新组织多播群组的索引，实现P1≥P2…≥PN（第14行）。然后，我们开始为每个多播群组构建多播树，并且采用每个多播群组的新索引，即多播群组k＝1的优先级P1最高 （第15～29行）。对多播群组k，我们通过降低（∩k）来重新组织无线链路索引∈，以便选择可以覆盖尽量多目的地的无线链路（第16行）。然后，对每个无线链路∈，如果满足如下3个条件 （第17～18行），则我们选择访问点ax把数据传输给访问点ay：①访问点满足其容量约束；②至少有两个目的地可以同时接收到多播数据 （即2）；③多播群组k 的每个目的地无法从2条或更多链路接收到相同的多播数据，以满足树属性 （即）。如果链路被采用，则我们把可以接收数据的目的地（机架）x加入到注册目的地集合（即＝∪x）中 （第19行），且相应地把指示函数lW（k，）设为1 （第20行）。虽然无线链路被采用且可把数据传输给部分目的地，但是访问点ax没有路径可接收来自发射机vk的多播数据流。于是，我们为给定的一对数据源vk和机架x 的访问点，搜索由有线链路和无线链路构成的最短路径。每当调用SHORTEST－PATH（）函数时，它均试图寻找从多播群组k 的源vk通往目的地x 且使用链路最少的最短路径（第21行）。对该条路径，我们首先尽量使用无线链路。如果无线链路不满足访问点容量约束，则我们采用有线链路。然后，对应的指示函数lW（k，）和lF（k，e）设为1。

在第22～27行，虽然目的地机架v的访问点av可以窃听到无线传输 （即v∈∩），但是它可能没有足够的容量来接收数据。因此，如果访问点有容量接收数据，则我们直接把机架目的地v 加入到注册目的地集合（第24行）。否则，我们用有线链路构建由发射机vk到目的地v的最短路径，且把相应的lF（k）设为1 （第26行）。机架目的地v也加入注册目的地集合v（第27行）。正式来讲，如果部分剩余目的地没有路径可以接收多播数据 （即 k＼≠），则我们使用SHORTEST－PATH （）函数为多播群组k的每个剩余目的地确定一条最短路径 （第28～29行）。最后，我们为每个多播群组返回一个由有线链路和无线链路构成的多播树 （第30行）。

证明：初始化过程需要时间O（N珟E）。对每个多播群组k，优先级Pk只计算一次，且可在时间O（）内完成。因此，对N 个多播群组，算法需要时间O（）。对于构建群组k的多播树，最多有个目的地和珟E 条链路，且对每个目的地，函数SHORTEST－PATH（）只使用一次。为N个多播群组构建多播树需要时间O（）。于是，算法1的时间复杂度为O（（＋））。

4 性能评估

4.1 仿真配置

本节给出一种基于实际无线数据中心拓扑结构的仿真模型来评估本文无线数据中心多播树高效构建算法 （EWDCMT）及其它两种算法的性能。第1 种算法称为Steiner树，针对有线数据中心网络而设计，该算法可以在不考虑每条有线链路容量约束的条件下获得每个多播群组的最优多播树。因此，在性能比较时我们放松了Steiner树的约束。请注意，放松约束有助于提高Steiner树的性能。第2种算法称为最短路径树算法，在本文中作为基准算法。该算法根据无线数据中心的有线和无线链路来构建最短路径树。对每个最短路径树，算法试图首先使用无线链路。直到访问点的可用容量耗尽，算法将会改用有线链路。性能指标为所有多播群组的总体数据传输流量。

我们根据文献 ［10］微软部署情况来研究具有分层拓扑结构的无线数据中心。无线数据中心共有160 个架顶，每个架顶有一个有线交换机和一个基于有向窄波束天线的60GHz无线访问点。根据微软的实际测量数据，当两条平行链路间距低于22英尺时会出现互扰。请注意，机架宽度约为24英尺［12］。然后，我们可以计算无线访问点的传输/干扰范围。如果不考虑背景流量 （BT），则每条链路的最大容量为1Gbps。在实验中我们研究了大背景流量和小背景流量对总体多播数据流量的影响。根据数据中心流量分布的真实测量结果，当考虑大背景流量时，每条链路的可用容量服从300Mbps－1000Mbps均匀分布［14］。对小背景流量，我们从700Mbps－to 1000Mbps范围中随机确定每条链路的可用容量。

此外，我们观察了数量在50－200间的多播群组的影响。对每个多播群组，从160个架顶随机选择数据源和目的地。为了生成每个多播群组的多个目的地，我们考虑两种不同的分布情况。第1种是3－160间的均匀分布，另一种是可在数据中心生成更多小型群组的幂律分布。具体来说，对幂律分布，根据如下概率生成每个多播群组k的目的地数量

表2 参数设置

4.2 仿真结果

图2给出了不同群组规模部署条件下多播群组数量对总体多播数据流的影响。如图2所示，当多播群组数量上升时3种算法的总体多播数据流量均有上升。这一结果与预期一致，因为多播群组数量越多，多播数据流量越多，占用的网络资源也就越多。相比于其它两种算法，本文算法可以更为有效地降低总体多播数据流量。比较图2 （a）和图2 （b）可以发现，在群组规模均匀分布条件下，最短路径树算法的性能与Steiner树算法更为接近。原因是均匀群组规模条件下的每个多播群组的成员 （目的地）更多且每个成员随机部署于无线数据中心，最短路径树可能会快速耗尽每条无线链路的容量。于是，改为使用有线链路，且最短路径树的性能与Steiner树类似。相反，相比于其它两种算法，EWDCMT 算法在群组规模均匀分布时对数据冗余的降低程度要高于群组规模幂律分布时。这是因为本文算法可以高效使用每条无线链路，并且试图寻找可以把数据传输给尽量多目的地的访问点。因此，当每个多播群组有更多目的地时，本文算法可以将无线媒介的优势更为高效地利用到多播传输中，显著降低多播数据流的冗余性。仿真结果表明，相比于其它两种算法，EWDCMT 算法在群组规模均匀分布和群组规模幂律分布两种情况下可以把总体数据流从45%和49%分别降低到72%和55%。

图3给出了不同背景流量水平对总体多播数据流量的影响。从图中可以看出，对最短路径和EWDCMT 算法，当背景流量较高时总体多播数据流量也较高。原因是当背景流量较高时，每个多播群组的高效无线链路可能无法使用。为了避免过度使用，这两个算法必须选择其它效率较

图2 多播群组数量对总体多播数据流量的影响。

低的无线/有线链路来构建多播树，导致数据冗余下降程度降低。这也解释了为何当背景流量较高时本文算法与其它两种算法的性能比较接近的原因。另一方面，不同的背景流量水平对Steiner树没有影响，因为Steiner树不考虑有线链路的链路容量约束。比较图3 （a）和图3 （b）可以发现结果与图2类似。如图3 （a）和图3 （b）所示，相比其它两种算法，本文算法在在群组规模均匀分布条件下降低总体多播数量流量方面的性能仍然优于群组规模幂律分布条件下。仿真结果表明，EWDCMT 算法优于其它两种算法。群组规模均匀分布和群组规模幂律分布两种情况下的下降幅度分别是44%和36%。结果也证明，为访问点密集分布的无线数据中心构建多播树是个非常复杂的问题。

5 结束语

本文研究了无线数据中心网络的群组通信问题。具体来说，我们研究了有线和无线链路共存条件下的多播树构建问题。目的是实现总体多播数据流 （即总体多播数据冗余）最小化。我们证明了目标问题的NP 难题属性，并提出了一种高效的启发式问题求解方法。利用真实数据中心的实际参数设置值展开了仿真和性能评估。仿真结果表明，相比于传统有线数据中心的最优解决方案和无线数据中心的基准解决方案，本文方法可以更有效地降低总体多播数据流量。

图3 多播群组数量对总体多播数据流量的影响。

［1］Kandula S，Padhye J，Bahl P.Flyways to de－congest data center networks ［J］.Flyways to Decongest Data Center Networks，2009，18 （12）：21－26.

［2］WANG Bin，ZHANG Yanfeng，WANG Wennai.A proportional fair scheduling based on OFDMA for wireless multicast service［J］.Journal of Electronics ＆Information Technology，2012，34 （7）：1672－1677 （in Chinese）. ［王斌，张艳凤，王文鼐.一种基于OFDMA 的无线多播比例公平调度方案 ［J］.电子与信息学报，2012，34 （7）：1672－1677.］

［3］JIANG Youhui，LU Hancheng，HONG Peilin，et al.Multicast transmission rate selection schemes based on network coding in wireless networks［J］.Journal of Electronics ＆Information Technology，2012，34 （5）：1202－1207（in Chinese）.［蒋友辉，卢汉成，洪佩琳，等.基于网络编码的无线多播速率选择机制 ［J］.电子与信息学报，2012，34 （5）：1202－1207.］

［4］LI Song，WANG Xiaoxiang，ZHANG Hongtao，et al.Resource allocation for exploiting multiuser diversity in multicast system ［J］.Journal of Beijing University of Posts and Telecommunications，2012，35 （4）：81－84 （in Chinese）.［李松， 王晓湘，张鸿涛，等.多播系统中基于多用户分集的资源分配［J］.北京邮电大学学报，2012，35 （4）：81－84.］

［5］HAN Bingqing，CHEN Wei，ZHANG Hong. Multi－rate multi－cast resource allocation algorithm for Ad hoc networks［J］.Computer Science，2013，39 （12）：55－59 （in Chinese）.［韩冰青，陈伟，张宏.支持多速率多播的Ad hoc网络资源分配算法 ［J］.计算机科学，2013，39 （12）：55－59.］

［6］CHEN Yi，HU Ruimin，GAO Ge.Optimal resource control strategy for heterogeneous multicast applications on dynamic Ad Hoc network ［J］.Acta Electronica Sinica，2011，39 （11）：2583－2588 （in Chinese）.［陈怡，胡瑞敏，高戈.面向动态Ad Hoc网络异构多播业务流最优资源控制策略 ［J］.电子学报，2011，39 （11）：2583－2588.］

［7］Vigfusson Y，Abu－Libdeh H，Balakrishnan M，et al.Dr.multicast：Rx for data center communication scalability ［C］//Proceedings of the 5th European Conference on Computer Systems.ACM，2010：349－362.

［8］Li D，Yu J，Yu J，et al.Exploring efficient and scalable multicast routing in future data center networks［C］//Proceedings IEEE INFOCOM，2011：1368－1376.

［9］Guo C，Lu G，Li D，et al.BCube：A high performance，server－centric network architecture for modular data centers［J］.ACM SIGCOMM Computer Communication Review，2009，39 （4）：63－74.

［10］Halperin D，Kandula S，Padhye J，et al.Augmenting data center networks with multi－gigabit wireless links ［J］.ACM SIGCOMM Computer Communication Review.ACM，2011，41 （4）：38－49.

［11］Yang Y，Wang J，Yang M.A service－centric multicast architecture and routing protocol［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19 （1）：35－51.

［12］Weber S，Andrews J G，Jindal N.An overview of the transmission capacity of wireless networks［J］.IEEE Transactions on Communications，2010，58 （12）：3593－3604.

［13］Lacroix M，Ridha Mahjoub A，Martin S，et al.On the NPcompleteness of the perfect matching free subgraph problem［J］.Theoretical Computer Science，2012，423：25－29.

［14］Benson T，Anand A，Akella A，et al.Understanding data center traffic characteristics［J］.ACM SIGCOMM Computer Communication Review，2010，40 （1）：92－99.

［15］Kandula S，Sengupta S，Greenberg A，et al.The nature of data center traffic：measurements ＆analysis ［C］//Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference.ACM，2009：202－208.