DCN 中基于流量最小化的多播數(shù)據(jù)傳輸方案

許志聰

（廣東工程職業(yè)技術(shù)學(xué)院 實訓(xùn)中心，廣東 廣州510520）

0 引 言

根據(jù)微軟公司的測量結(jié)果，架頂式交換機的數(shù)據(jù)流量非常大，可能嚴重影響網(wǎng)絡(luò)性能［1］。為了緩解傳統(tǒng)有線數(shù)據(jù)中心網(wǎng)絡(luò)的問題，人們引入了低成本、高數(shù)據(jù)率的60GHz無線技術(shù) （比如802.11ad），以補充網(wǎng)絡(luò)容量，實現(xiàn)快速連通。在無線數(shù)據(jù)中心的每個機架頂部，均有無線訪問點和有線交換機共存?；诩茼?shù)亩嗖?shù)據(jù)可以通過無線接入點或有線交換機進行傳輸。雖然樹結(jié)構(gòu)是傳輸多播數(shù)據(jù)的有效拓撲結(jié)構(gòu)，但是如何為無線數(shù)據(jù)中心構(gòu)建高效的樹是一個非常復(fù)雜的技術(shù)問題。具體原因如下：①因為無線接入點在數(shù)據(jù)中心的部署密度很大，必須要仔細考慮無線接入點間的干擾問題；②與有線傳輸相比，無線媒介是廣播型媒介，更適合于多播。與有線交換機不同的是，無線接入點可以把數(shù)據(jù)傳輸給在其通信范圍內(nèi)的多個訪問點，傳輸路徑也有多種選擇，尤其是采用有向天線時更是如此；③如果在無線數(shù)據(jù)中心采用有線鏈路，同時傳輸多個無線訪問點，則無線和有線鏈路共存，此時又會無線干擾。

1 相關(guān)工作

為了實現(xiàn)群組通信，人們通過多播來把數(shù)據(jù)傳輸給多個目的地。文獻 ［2］為了在無線多播網(wǎng)絡(luò)中提高系統(tǒng)吞吐量，提出了一種新型的多播組間公平的無線資源分配方案。方案在保證公平分配無線資源的前提下，運用設(shè)置平均誤塊率門限的方法，在系統(tǒng)的多用戶分集增益和多播增益之間找到了最佳平衡，從而提高了系統(tǒng)的吞吐量。文獻 ［3］根據(jù)節(jié)點的當(dāng)前信道狀態(tài)信息 （CSI）和接收節(jié)點已接收數(shù)據(jù)狀態(tài)信息 （DSI），提出了一種基于信道預(yù)測多播速率選擇算法 （MDCP）來最小化傳輸延遲，并結(jié)合網(wǎng)絡(luò)編碼提高數(shù)據(jù)傳輸效率。仿真結(jié)果表明，與基于最差信道狀態(tài)節(jié)點的多播速率選擇算法和沒有信道預(yù)測的基于最大延遲節(jié)點的多播速率選擇算法相比，MDCP能夠獲得10%～20%延遲增益。文獻 ［4］提出了一種組內(nèi)資源分配算法。在考慮用戶之間不同速率需求的前提下，通過子載波分配和功率分配實現(xiàn)了組內(nèi)用戶多播傳輸?shù)臍w一化速率最大化。仿真結(jié)果表明，與傳統(tǒng)多播組內(nèi)資源分配方案相比，顯著提升多播系統(tǒng)的歸一化速率。

另外，文獻 ［5］提出了一種支持多速率多播傳輸?shù)腁d－Hoc網(wǎng)絡(luò)資源分配算法，它通過引入基于價格的流量分配方案來解決多速率多播傳輸問題，從而能夠自適應(yīng)地分配網(wǎng)絡(luò)流量，并且最大化網(wǎng)絡(luò)流的總效用。文獻 ［6］提出了一種基于分段效用函數(shù)和判決機制的自適應(yīng)多播控制算法 （AMC），仿真結(jié)果表明，AMC 對移動Ad－Hoc網(wǎng)絡(luò)狀態(tài)改變具有優(yōu)良的自適應(yīng)性能，尤其適用動態(tài)網(wǎng)絡(luò)的異構(gòu)分層多播業(yè)務(wù)流。然而，上述無線多播路由算法不能用于無線數(shù)據(jù)中心網(wǎng)絡(luò)。這是因為，在無線數(shù)據(jù)中心網(wǎng)絡(luò)中，無線訪問點的部署密度非常高，導(dǎo)致干擾比較嚴重。同時，在無線數(shù)據(jù)中心，相比于無線Ad－Hoc網(wǎng)絡(luò)，有線和無線鏈路共存條件下的連通性問題更為復(fù)雜。

最近，部分研究人員開始關(guān)注傳統(tǒng)有線數(shù)據(jù)中心的多播問題。在文獻 ［7］中，鑒于在支持交換機多播操作時的硬件約束，Vigfusson等提出了一種多播傳輸群組通信請求選擇機制，該機制在多播傳輸時選擇部分群組通信請求，其余請求通過單播傳輸完成。然后，文獻 ［8］指出，如果為互聯(lián)網(wǎng)設(shè)計的數(shù)據(jù)中心網(wǎng)絡(luò)的連接密度較大，且基于接收方驅(qū)動的多播路由協(xié)議生成多條等成本路徑，則這種數(shù)據(jù)中心網(wǎng)絡(luò)在傳輸鏈路數(shù)量方面的性能較差。因此，作者提出了有線數(shù)據(jù)中心網(wǎng)絡(luò)的高效多播路由方法，以降低數(shù)據(jù)傳輸?shù)娜哂喽?。然而，提出的路由方法無法兼容現(xiàn)代數(shù)據(jù)中心網(wǎng)絡(luò)的無線鏈路。此外，該方法只將降低所用的有線鏈路總數(shù)量作為其主要性能指標(biāo)，沒有考慮異質(zhì)云服務(wù)會請求不同的數(shù)據(jù)率。鑒于此，本文在已有研究工作的基礎(chǔ)上，提出了一種基于流量最小化的多播數(shù)據(jù)傳輸方案，并通過仿真實驗驗證了本文方案的有效性。

2 系統(tǒng)模型和問題闡述

2.1 系統(tǒng)模型

對傳統(tǒng)的數(shù)據(jù)中心，多個服務(wù)器放于一個機架上，每個機架配置一個交換機，交換機稱為架頂交換機 （top－ofrack switch），且機架上的所有服務(wù)器與其相連。架頂交換機往往基于分層拓撲、Fat－tree樹或BCube［9］等架構(gòu)通過匯聚交換機或核心交換機相連。然而，傳統(tǒng)數(shù)據(jù)中心的部署成本和復(fù)雜度過高。最近，微軟采用了60GHz無線訪問技術(shù)在每個架頂交換機上部署一個無線訪問點，以補充網(wǎng)絡(luò)容量，實現(xiàn)快速連通［2］。60GHz訪問點可以支持10m 傳輸范圍內(nèi)的高數(shù)據(jù)率。因為數(shù)據(jù)中心內(nèi)訪問點的部署密度非常高，所以采用窄波束天線陣列有向天線來緩解干擾［10］。圖1給出了一個簡單的無線數(shù)據(jù)中心架構(gòu)示例。圖中共有12個機架，每個機架配置一個架頂交換機和一個無線訪問點。每個架頂交換機通過有線與匯聚/核心交換機相連，而每個架頂訪問點可以將數(shù)據(jù)發(fā)往其通信范圍內(nèi)的任意訪問點。

圖1 無線數(shù)據(jù)中心架構(gòu)示例

因為提供云服務(wù)的協(xié)調(diào)式應(yīng)用必須要進行群組通信，所以無線數(shù)據(jù)中心網(wǎng)絡(luò)也必須要進行多播數(shù)據(jù)傳輸。多播數(shù)據(jù)傳輸通過樹結(jié)構(gòu)完成。多播樹構(gòu)建分為兩類［11］：基于數(shù)據(jù)源型和基于共享型。因為數(shù)據(jù)中心的大多數(shù)群組通信在每個多播群組內(nèi)只有一個多播發(fā)送方，所以為不失一般性，我們在本文中考慮基于數(shù)據(jù)源的樹構(gòu)建方法。

2.2 問題描述

本節(jié)討論基于資源且由無線數(shù)據(jù)中心網(wǎng)絡(luò)有線和無線鏈路組成的多播樹構(gòu)建問題。目的是使總多播數(shù)據(jù)流量最小化 （即總體數(shù)據(jù)冗余度）。問題闡述如下。出于簡便考慮，如果表達意思結(jié)合上下文非常明確時省略""符號。

我們考慮一組N 個多播群組 ＝（r1，r2，…，rN），其中rk＝（vk，Tk）表示機架vk是多播群組k 的發(fā)射機且必須以Tk（bps）數(shù)據(jù)率把多播流量發(fā)送給多個 （機架）。然后，我們定義lF（k）∈｛0，1｝為指示函數(shù)，如果多播群組k的流量通過有線鏈路則函數(shù)為1。如果使用有線鏈路且lF（k，eFsisj）設(shè)為1，則機架j∈ 的架頂交換機sj可以接收到多播數(shù)據(jù)。我們同時定義lW（k）∈｛0，1｝以表明多播群組k 的流量是否使用無線鏈路。如果使用了無線鏈路且lW（k，）設(shè)為1，則在傳輸覆蓋范圍內(nèi)的一組機架訪問點會竊聽和接收數(shù)據(jù)。我們的目的就是為每個多播群組構(gòu)建一個由有線和無線鏈路組成的多播樹。如果以下約束滿足，則可以構(gòu)建多播樹：

有線鏈路容量約束：為了避免架頂交換機過度使用，式（1）可保證多播群組通過各條有向鏈路的數(shù)據(jù)率不會超過每條有向鏈路的可用容量

訪問點容量約束：因為無線訪問點會對周圍其它訪問點造成干擾，所以式 （2）保證各個訪問點在數(shù)據(jù)接收和傳輸時不會超過其容量。通過使用I（ay，）以表明訪問點ay是否被訪問點ax干擾，且I（ay）的定義以基于幾何學(xué)的協(xié)議干擾模型［12］為基礎(chǔ)。根據(jù)該模型，當(dāng)訪問點ay位于訪問點ax向訪問點az傳輸數(shù)據(jù)時的傳輸范圍內(nèi)時，I（ay，）＝1

傳輸約束：每個多播群組的目的地必須要接收它們的多播數(shù)據(jù)

我們現(xiàn)在定義目標(biāo)問題如下：

高效的多播樹構(gòu)建問題

輸入實例：考慮一個有向圖G＝（V，E）。每條有線和無線鏈路的容量為和。有一組包括N 個多播群組的集合 。

目標(biāo)：我們的目標(biāo)是為每個多播群組構(gòu)建由有線鏈路lF（k，）和無線鏈路lW（k，）組成的多播樹，以實現(xiàn)所有多播群組多播數(shù)據(jù)流量 （數(shù)據(jù)冗余）最小化

且約束條件為式 （1）～式 （3）。表1總結(jié)了問題描述時用到的標(biāo)記法。

表1 標(biāo)記法總結(jié)

3 多播數(shù)據(jù)高效傳輸

本節(jié)通過NP 難題屬性已經(jīng)得到證明的劃分約簡問題［13］來證明本文問題的NP 難題屬性，并提出一種高效的啟發(fā)式求解算法。

3.1 問題的NP難題屬性

定理1 多播樹高效構(gòu)建問題是NP難題。

已知劃分問題的一個實例 〈B〉，我們闡述當(dāng)且僅當(dāng)存在M 個總體數(shù)據(jù)流量為的多播樹時，如何在多項式時間內(nèi)構(gòu)建本文問題的〈，，， ，N〉實例才能對均分。構(gòu)建方法如下：在一個無線數(shù)據(jù)中心有兩個機架，上面有兩個架頂交換機＝2和兩個架頂無線訪問點＝2。只通過1條有線鏈路和1條無線鏈路將一個機架連接到另一個機架 （即F＝，｝且W＝，｝）。每 條 有 線 和 無 線 鏈 路 的 容 量 設(shè) 為（即有一個包括M 個多播群組的集合 （即N＝M ）。M 個多播群組的多播數(shù)據(jù)全部從同一機架 （源）發(fā)往其它機架 （目的地）。多播群組m 的數(shù)據(jù)率設(shè)為Tm＝bm，1≤m ≤M 。

為了完成證明過程，我們將證明通過兩個分割子集可以獲得總數(shù)據(jù)流量為Tm＝bm，1≤m ≤M 的M 個多播樹，反之亦然。如果有兩個分割子集，每個整數(shù)bm對應(yīng)于多播群組m 要求的數(shù)據(jù)率Tm。一個子集對應(yīng)于分配給有線鏈路的多播群組的數(shù)據(jù)率，另一個子集對應(yīng)于無線鏈路傳輸?shù)牧硪欢嗖ト航M的數(shù)據(jù)率。因此，M 個多播樹的總體數(shù)據(jù)流量為另一方面，如果M 個多播樹的總體數(shù)據(jù)流量為則有線鏈路和無線鏈路必須分別傳輸數(shù)據(jù)率。這表明，通過將對應(yīng)的整數(shù)分配給對應(yīng)的子集，便可對集合均勻劃分。劃分問題存在多項式時間算法，表明本文問題也存在多項式算法，問題得證。

3.2 算法描述

本節(jié)給出一種算法，可以為所有多播群組高效構(gòu)建由有線鏈路和無線鏈路組成的多播樹。該算法的思路是搜索可以覆蓋盡量多目的地的無線訪問點，以降低多播流量的數(shù)據(jù)冗余。然后，我們尋找由有線鏈路和無線鏈路組成的最短路徑，以便將每個數(shù)據(jù)源與其目的地相連。此外，為了盡量降低鏈路使用數(shù)量，我們對每條最短路徑盡可能優(yōu)先使用無線鏈路。如果無線鏈路無法支持數(shù)據(jù)傳輸，則使用有線鏈路。此外，為了高效利用每條鏈路的容量，我們在構(gòu)建多播樹時為數(shù)據(jù)率較大的多播樹賦予較高優(yōu)先級。

本文算法的偽代碼見算法1。在第1行，使用指示函數(shù)lF（k，）來記錄是否分配有線鏈路傳輸多播群組k 的數(shù)據(jù)，且初始化為0，1≤k≤N，∈F。在第2行，使用指示函數(shù)lW（k）記錄是否分配無線鏈路傳輸多播群組k的數(shù)據(jù)，且初始化為0，1 ≤k ≤N。在第3行，利用初始化為0的變量Pk來記錄多播群組k 的優(yōu)先級。如果多播群組k 的優(yōu)先級Pk較高，則我們應(yīng)該優(yōu)先為該多播群組構(gòu)建多播樹。在第4行，使用集合記錄哪些無線鏈路可用于傳輸多播群組k 的流量。在第5行，使用集合來記錄多播群組k 有多少個目的地可以竊聽到目的地 （機架）訪問點傳輸?shù)亩嗖?shù)據(jù)。在第6 行，使用集合來表示多播群組k 有多少個目的地可以接收到數(shù)據(jù)且初始化為。

然后，算法開始為每個多播群組構(gòu)建由有線鏈路和無線鏈路組成的多播樹 （第7～29行）。對每個多播群組k，因為無線數(shù)據(jù)中心往往采用窄波束有向天線，所以我們假設(shè)每個無線訪問點ax（x ∈νk）試圖把多播群組k的數(shù)據(jù)傳輸給每個無線訪問點ayyvk，且計算有多少個目的地可以接收到數(shù)據(jù) （第7～13行）。在第10～11行，如果機架x 的訪問點ax可以把數(shù)據(jù)傳輸給機架y 的訪問點 （即），則有一組目的地可以接收到數(shù)據(jù)（即）。且集合更新為）。在第12行，可用于傳輸多播群組k的無線鏈路被加入集合。當(dāng)嘗試遍歷玩所有目的地訪問點對后，將多播群組k的優(yōu)先級Pk設(shè)為Tk×（第13 行）。也就是說，如果可以竊聽到無線訪問點傳輸?shù)臄?shù)據(jù)的目的地增多且多播群組k 的流量數(shù)據(jù)率更高，則可進一步降低數(shù)據(jù)冗余。因此，我們優(yōu)先為這種多播群組構(gòu)建多播樹且使用無線訪問點。

所有多播群組的優(yōu)先級設(shè)置完畢后，我們通過降低Pk（1≤k≤N）的屬性來重新組織多播群組的索引，實現(xiàn)P1≥P2…≥PN（第14行）。然后，我們開始為每個多播群組構(gòu)建多播樹，并且采用每個多播群組的新索引，即多播群組k＝1的優(yōu)先級P1最高 （第15～29行）。對多播群組k，我們通過降低（∩k）來重新組織無線鏈路索引∈，以便選擇可以覆蓋盡量多目的地的無線鏈路（第16行）。然后，對每個無線鏈路∈，如果滿足如下3個條件 （第17～18行），則我們選擇訪問點ax把數(shù)據(jù)傳輸給訪問點ay：①訪問點滿足其容量約束；②至少有兩個目的地可以同時接收到多播數(shù)據(jù) （即2）；③多播群組k 的每個目的地?zé)o法從2條或更多鏈路接收到相同的多播數(shù)據(jù)，以滿足樹屬性 （即）。如果鏈路被采用，則我們把可以接收數(shù)據(jù)的目的地（機架）x加入到注冊目的地集合（即＝∪x）中 （第19行），且相應(yīng)地把指示函數(shù)lW（k，）設(shè)為1 （第20行）。雖然無線鏈路被采用且可把數(shù)據(jù)傳輸給部分目的地，但是訪問點ax沒有路徑可接收來自發(fā)射機vk的多播數(shù)據(jù)流。于是，我們?yōu)榻o定的一對數(shù)據(jù)源vk和機架x 的訪問點，搜索由有線鏈路和無線鏈路構(gòu)成的最短路徑。每當(dāng)調(diào)用SHORTEST－PATH（）函數(shù)時，它均試圖尋找從多播群組k 的源vk通往目的地x 且使用鏈路最少的最短路徑（第21行）。對該條路徑，我們首先盡量使用無線鏈路。如果無線鏈路不滿足訪問點容量約束，則我們采用有線鏈路。然后，對應(yīng)的指示函數(shù)lW（k，）和lF（k，e）設(shè)為1。

在第22～27行，雖然目的地機架v的訪問點av可以竊聽到無線傳輸 （即v∈∩），但是它可能沒有足夠的容量來接收數(shù)據(jù)。因此，如果訪問點有容量接收數(shù)據(jù)，則我們直接把機架目的地v 加入到注冊目的地集合（第24行）。否則，我們用有線鏈路構(gòu)建由發(fā)射機vk到目的地v的最短路徑，且把相應(yīng)的lF（k）設(shè)為1 （第26行）。機架目的地v也加入注冊目的地集合v（第27行）。正式來講，如果部分剩余目的地沒有路徑可以接收多播數(shù)據(jù) （即 k＼≠），則我們使用SHORTEST－PATH （）函數(shù)為多播群組k的每個剩余目的地確定一條最短路徑 （第28～29行）。最后，我們?yōu)槊總€多播群組返回一個由有線鏈路和無線鏈路構(gòu)成的多播樹 （第30行）。

證明：初始化過程需要時間O（N珟E）。對每個多播群組k，優(yōu)先級Pk只計算一次，且可在時間O（）內(nèi)完成。因此，對N 個多播群組，算法需要時間O（）。對于構(gòu)建群組k的多播樹，最多有個目的地和珟E 條鏈路，且對每個目的地，函數(shù)SHORTEST－PATH（）只使用一次。為N個多播群組構(gòu)建多播樹需要時間O（）。于是，算法1的時間復(fù)雜度為O（（＋））。

4 性能評估

4.1 仿真配置

本節(jié)給出一種基于實際無線數(shù)據(jù)中心拓撲結(jié)構(gòu)的仿真模型來評估本文無線數(shù)據(jù)中心多播樹高效構(gòu)建算法 （EWDCMT）及其它兩種算法的性能。第1 種算法稱為Steiner樹，針對有線數(shù)據(jù)中心網(wǎng)絡(luò)而設(shè)計，該算法可以在不考慮每條有線鏈路容量約束的條件下獲得每個多播群組的最優(yōu)多播樹。因此，在性能比較時我們放松了Steiner樹的約束。請注意，放松約束有助于提高Steiner樹的性能。第2種算法稱為最短路徑樹算法，在本文中作為基準算法。該算法根據(jù)無線數(shù)據(jù)中心的有線和無線鏈路來構(gòu)建最短路徑樹。對每個最短路徑樹，算法試圖首先使用無線鏈路。直到訪問點的可用容量耗盡，算法將會改用有線鏈路。性能指標(biāo)為所有多播群組的總體數(shù)據(jù)傳輸流量。

我們根據(jù)文獻 ［10］微軟部署情況來研究具有分層拓撲結(jié)構(gòu)的無線數(shù)據(jù)中心。無線數(shù)據(jù)中心共有160 個架頂，每個架頂有一個有線交換機和一個基于有向窄波束天線的60GHz無線訪問點。根據(jù)微軟的實際測量數(shù)據(jù)，當(dāng)兩條平行鏈路間距低于22英尺時會出現(xiàn)互擾。請注意，機架寬度約為24英尺［12］。然后，我們可以計算無線訪問點的傳輸/干擾范圍。如果不考慮背景流量 （BT），則每條鏈路的最大容量為1Gbps。在實驗中我們研究了大背景流量和小背景流量對總體多播數(shù)據(jù)流量的影響。根據(jù)數(shù)據(jù)中心流量分布的真實測量結(jié)果，當(dāng)考慮大背景流量時，每條鏈路的可用容量服從300Mbps－1000Mbps均勻分布［14］。對小背景流量，我們從700Mbps－to 1000Mbps范圍中隨機確定每條鏈路的可用容量。

此外，我們觀察了數(shù)量在50－200間的多播群組的影響。對每個多播群組，從160個架頂隨機選擇數(shù)據(jù)源和目的地。為了生成每個多播群組的多個目的地，我們考慮兩種不同的分布情況。第1種是3－160間的均勻分布，另一種是可在數(shù)據(jù)中心生成更多小型群組的冪律分布。具體來說，對冪律分布，根據(jù)如下概率生成每個多播群組k的目的地數(shù)量

表2 參數(shù)設(shè)置

4.2 仿真結(jié)果

圖2給出了不同群組規(guī)模部署條件下多播群組數(shù)量對總體多播數(shù)據(jù)流的影響。如圖2所示，當(dāng)多播群組數(shù)量上升時3種算法的總體多播數(shù)據(jù)流量均有上升。這一結(jié)果與預(yù)期一致，因為多播群組數(shù)量越多，多播數(shù)據(jù)流量越多，占用的網(wǎng)絡(luò)資源也就越多。相比于其它兩種算法，本文算法可以更為有效地降低總體多播數(shù)據(jù)流量。比較圖2 （a）和圖2 （b）可以發(fā)現(xiàn)，在群組規(guī)模均勻分布條件下，最短路徑樹算法的性能與Steiner樹算法更為接近。原因是均勻群組規(guī)模條件下的每個多播群組的成員 （目的地）更多且每個成員隨機部署于無線數(shù)據(jù)中心，最短路徑樹可能會快速耗盡每條無線鏈路的容量。于是，改為使用有線鏈路，且最短路徑樹的性能與Steiner樹類似。相反，相比于其它兩種算法，EWDCMT 算法在群組規(guī)模均勻分布時對數(shù)據(jù)冗余的降低程度要高于群組規(guī)模冪律分布時。這是因為本文算法可以高效使用每條無線鏈路，并且試圖尋找可以把數(shù)據(jù)傳輸給盡量多目的地的訪問點。因此，當(dāng)每個多播群組有更多目的地時，本文算法可以將無線媒介的優(yōu)勢更為高效地利用到多播傳輸中，顯著降低多播數(shù)據(jù)流的冗余性。仿真結(jié)果表明，相比于其它兩種算法，EWDCMT 算法在群組規(guī)模均勻分布和群組規(guī)模冪律分布兩種情況下可以把總體數(shù)據(jù)流從45%和49%分別降低到72%和55%。

圖3給出了不同背景流量水平對總體多播數(shù)據(jù)流量的影響。從圖中可以看出，對最短路徑和EWDCMT 算法，當(dāng)背景流量較高時總體多播數(shù)據(jù)流量也較高。原因是當(dāng)背景流量較高時，每個多播群組的高效無線鏈路可能無法使用。為了避免過度使用，這兩個算法必須選擇其它效率較

圖2 多播群組數(shù)量對總體多播數(shù)據(jù)流量的影響。

低的無線/有線鏈路來構(gòu)建多播樹，導(dǎo)致數(shù)據(jù)冗余下降程度降低。這也解釋了為何當(dāng)背景流量較高時本文算法與其它兩種算法的性能比較接近的原因。另一方面，不同的背景流量水平對Steiner樹沒有影響，因為Steiner樹不考慮有線鏈路的鏈路容量約束。比較圖3 （a）和圖3 （b）可以發(fā)現(xiàn)結(jié)果與圖2類似。如圖3 （a）和圖3 （b）所示，相比其它兩種算法，本文算法在在群組規(guī)模均勻分布條件下降低總體多播數(shù)量流量方面的性能仍然優(yōu)于群組規(guī)模冪律分布條件下。仿真結(jié)果表明，EWDCMT 算法優(yōu)于其它兩種算法。群組規(guī)模均勻分布和群組規(guī)模冪律分布兩種情況下的下降幅度分別是44%和36%。結(jié)果也證明，為訪問點密集分布的無線數(shù)據(jù)中心構(gòu)建多播樹是個非常復(fù)雜的問題。

5 結(jié)束語

本文研究了無線數(shù)據(jù)中心網(wǎng)絡(luò)的群組通信問題。具體來說，我們研究了有線和無線鏈路共存條件下的多播樹構(gòu)建問題。目的是實現(xiàn)總體多播數(shù)據(jù)流 （即總體多播數(shù)據(jù)冗余）最小化。我們證明了目標(biāo)問題的NP 難題屬性，并提出了一種高效的啟發(fā)式問題求解方法。利用真實數(shù)據(jù)中心的實際參數(shù)設(shè)置值展開了仿真和性能評估。仿真結(jié)果表明，相比于傳統(tǒng)有線數(shù)據(jù)中心的最優(yōu)解決方案和無線數(shù)據(jù)中心的基準解決方案，本文方法可以更有效地降低總體多播數(shù)據(jù)流量。

圖3 多播群組數(shù)量對總體多播數(shù)據(jù)流量的影響。

［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 的無線多播比例公平調(diào)度方案 ［J］.電子與信息學(xué)報，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）.［蔣友輝，盧漢成，洪佩琳，等.基于網(wǎng)絡(luò)編碼的無線多播速率選擇機制 ［J］.電子與信息學(xué)報，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）.［李松， 王曉湘，張鴻濤，等.多播系統(tǒng)中基于多用戶分集的資源分配［J］.北京郵電大學(xué)學(xué)報，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網(wǎng)絡(luò)資源分配算法 ［J］.計算機科學(xué)，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）.［陳怡，胡瑞敏，高戈.面向動態(tài)Ad Hoc網(wǎng)絡(luò)異構(gòu)多播業(yè)務(wù)流最優(yōu)資源控制策略 ［J］.電子學(xué)報，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.