許志聰

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

0 引 言

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

1 相關(guān)工作

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

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

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

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

2.1 系統(tǒng)模型

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

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

因?yàn)樘峁┰品?wù)的協(xié)調(diào)式應(yīng)用必須要進(jìn)行群組通信，所以無(wú)線數(shù)據(jù)中心網(wǎng)絡(luò)也必須要進(jìn)行多播數(shù)據(jù)傳輸。多播數(shù)據(jù)傳輸通過樹結(jié)構(gòu)完成。多播樹構(gòu)建分為兩類［11］：基于數(shù)據(jù)源型和基于共享型。因?yàn)閿?shù)據(jù)中心的大多數(shù)群組通信在每個(gè)多播群組內(nèi)只有一個(gè)多播發(fā)送方，所以為不失一般性，我們?cè)诒疚闹锌紤]基于數(shù)據(jù)源的樹構(gòu)建方法。

2.2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 問題的NP難題屬性

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

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

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

3.2 算法描述

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

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

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

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

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

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

4 性能評(píng)估

4.1 仿真配置

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

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

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

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

4.2 仿真結(jié)果

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

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

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

低的無(wú)線/有線鏈路來(lái)構(gòu)建多播樹，導(dǎo)致數(shù)據(jù)冗余下降程度降低。這也解釋了為何當(dāng)背景流量較高時(shí)本文算法與其它兩種算法的性能比較接近的原因。另一方面，不同的背景流量水平對(duì)Steiner樹沒有影響，因?yàn)镾teiner樹不考慮有線鏈路的鏈路容量約束。比較圖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é)果也證明，為訪問點(diǎn)密集分布的無(wú)線數(shù)據(jù)中心構(gòu)建多播樹是個(gè)非常復(fù)雜的問題。

5 結(jié)束語(yǔ)

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

圖3 多播群組數(shù)量對(duì)總體多播數(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 的無(wú)線多播比例公平調(diào)度方案 ［J］.電子與信息學(xué)報(bào)，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ò)編碼的無(wú)線多播速率選擇機(jī)制 ［J］.電子與信息學(xué)報(bào)，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é)報(bào)，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］.計(jì)算機(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）.［陳怡，胡瑞敏，高戈.面向動(dòng)態(tài)Ad Hoc網(wǎng)絡(luò)異構(gòu)多播業(yè)務(wù)流最優(yōu)資源控制策略 ［J］.電子學(xué)報(bào)，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.