許志聰
(廣東工程職業(yè)技術(shù)學(xué)院 實(shí)訓(xùn)中心,廣東 廣州510520)
根據(jù)微軟公司的測(cè)量結(jié)果,架頂式交換機(jī)的數(shù)據(jù)流量非常大,可能嚴(yán)重影響網(wǎng)絡(luò)性能[1]。為了緩解傳統(tǒng)有線數(shù)據(jù)中心網(wǎng)絡(luò)的問題,人們引入了低成本、高數(shù)據(jù)率的60GHz無線技術(shù) (比如802.11ad),以補(bǔ)充網(wǎng)絡(luò)容量,實(shí)現(xiàn)快速連通。在無線數(shù)據(jù)中心的每個(gè)機(jī)架頂部,均有無線訪問點(diǎn)和有線交換機(jī)共存?;诩茼?shù)亩嗖?shù)據(jù)可以通過無線接入點(diǎn)或有線交換機(jī)進(jìn)行傳輸。雖然樹結(jié)構(gòu)是傳輸多播數(shù)據(jù)的有效拓?fù)浣Y(jié)構(gòu),但是如何為無線數(shù)據(jù)中心構(gòu)建高效的樹是一個(gè)非常復(fù)雜的技術(shù)問題。具體原因如下:①因?yàn)闊o線接入點(diǎn)在數(shù)據(jù)中心的部署密度很大,必須要仔細(xì)考慮無線接入點(diǎn)間的干擾問題;②與有線傳輸相比,無線媒介是廣播型媒介,更適合于多播。與有線交換機(jī)不同的是,無線接入點(diǎn)可以把數(shù)據(jù)傳輸給在其通信范圍內(nèi)的多個(gè)訪問點(diǎn),傳輸路徑也有多種選擇,尤其是采用有向天線時(shí)更是如此;③如果在無線數(shù)據(jù)中心采用有線鏈路,同時(shí)傳輸多個(gè)無線訪問點(diǎn),則無線和有線鏈路共存,此時(shí)又會(huì)無線干擾。
為了實(shí)現(xiàn)群組通信,人們通過多播來把數(shù)據(jù)傳輸給多個(gè)目的地。文獻(xiàn) [2]為了在無線多播網(wǎng)絡(luò)中提高系統(tǒng)吞吐量,提出了一種新型的多播組間公平的無線資源分配方案。方案在保證公平分配無線資源的前提下,運(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)來最小化傳輸延遲,并結(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à)格的流量分配方案來解決多速率多播傳輸問題,從而能夠自適應(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ù)流。然而,上述無線多播路由算法不能用于無線數(shù)據(jù)中心網(wǎng)絡(luò)。這是因?yàn)椋跓o線數(shù)據(jù)中心網(wǎng)絡(luò)中,無線訪問點(diǎn)的部署密度非常高,導(dǎo)致干擾比較嚴(yán)重。同時(shí),在無線數(shù)據(jù)中心,相比于無線Ad-Hoc網(wǎng)絡(luò),有線和無線鏈路共存條件下的連通性問題更為復(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ù)娜哂喽?。然而,提出的路由方法無法兼容現(xiàn)代數(shù)據(jù)中心網(wǎng)絡(luò)的無線鏈路。此外,該方法只將降低所用的有線鏈路總數(shù)量作為其主要性能指標(biāo),沒有考慮異質(zhì)云服務(wù)會(huì)請(qǐng)求不同的數(shù)據(jù)率。鑒于此,本文在已有研究工作的基礎(chǔ)上,提出了一種基于流量最小化的多播數(shù)據(jù)傳輸方案,并通過仿真實(shí)驗(yàn)驗(yàn)證了本文方案的有效性。
對(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無線訪問技術(shù)在每個(gè)架頂交換機(jī)上部署一個(gè)無線訪問點(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)的部署密度非常高,所以采用窄波束天線陣列有向天線來緩解干擾[10]。圖1給出了一個(gè)簡(jiǎn)單的無線數(shù)據(jù)中心架構(gòu)示例。圖中共有12個(gè)機(jī)架,每個(gè)機(jī)架配置一個(gè)架頂交換機(jī)和一個(gè)無線訪問點(diǎn)。每個(gè)架頂交換機(jī)通過有線與匯聚/核心交換機(jī)相連,而每個(gè)架頂訪問點(diǎn)可以將數(shù)據(jù)發(fā)往其通信范圍內(nèi)的任意訪問點(diǎn)。
圖1 無線數(shù)據(jù)中心架構(gòu)示例
因?yàn)樘峁┰品?wù)的協(xié)調(diào)式應(yīng)用必須要進(jìn)行群組通信,所以無線數(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)建方法。
本節(jié)討論基于資源且由無線數(shù)據(jù)中心網(wǎng)絡(luò)有線和無線鏈路組成的多播樹構(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 的流量是否使用無線鏈路。如果使用了無線鏈路且lW(k,)設(shè)為1,則在傳輸覆蓋范圍內(nèi)的一組機(jī)架訪問點(diǎn)會(huì)竊聽和接收數(shù)據(jù)。我們的目的就是為每個(gè)多播群組構(gòu)建一個(gè)由有線和無線鏈路組成的多播樹。如果以下約束滿足,則可以構(gòu)建多播樹:
有線鏈路容量約束:為了避免架頂交換機(jī)過度使用,式(1)可保證多播群組通過各條有向鏈路的數(shù)據(jù)率不會(huì)超過每條有向鏈路的可用容量
訪問點(diǎn)容量約束:因?yàn)闊o線訪問點(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)。每條有線和無線鏈路的容量為和。有一組包括N 個(gè)多播群組的集合 。
目標(biāo):我們的目標(biāo)是為每個(gè)多播群組構(gòu)建由有線鏈路lF(k,)和無線鏈路lW(k,)組成的多播樹,以實(shí)現(xiàn)所有多播群組多播數(shù)據(jù)流量 (數(shù)據(jù)冗余)最小化
且約束條件為式 (1)~式 (3)。表1總結(jié)了問題描述時(shí)用到的標(biāo)記法。
表1 標(biāo)記法總結(jié)
本節(jié)通過NP 難題屬性已經(jīng)得到證明的劃分約簡(jiǎn)問題[13]來證明本文問題的NP 難題屬性,并提出一種高效的啟發(fā)式求解算法。
定理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è)無線數(shù)據(jù)中心有兩個(gè)機(jī)架,上面有兩個(gè)架頂交換機(jī)=2和兩個(gè)架頂無線訪問點(diǎn)=2。只通過1條有線鏈路和1條無線鏈路將一個(gè)機(jī)架連接到另一個(gè)機(jī)架 (即F=,}且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)于無線鏈路傳輸?shù)牧硪欢嗖ト航M的數(shù)據(jù)率。因此,M 個(gè)多播樹的總體數(shù)據(jù)流量為另一方面,如果M 個(gè)多播樹的總體數(shù)據(jù)流量為則有線鏈路和無線鏈路必須分別傳輸數(shù)據(jù)率。這表明,通過將對(duì)應(yīng)的整數(shù)分配給對(duì)應(yīng)的子集,便可對(duì)集合均勻劃分。劃分問題存在多項(xiàng)式時(shí)間算法,表明本文問題也存在多項(xiàng)式算法,問題得證。
本節(jié)給出一種算法,可以為所有多播群組高效構(gòu)建由有線鏈路和無線鏈路組成的多播樹。該算法的思路是搜索可以覆蓋盡量多目的地的無線訪問點(diǎn),以降低多播流量的數(shù)據(jù)冗余。然后,我們尋找由有線鏈路和無線鏈路組成的最短路徑,以便將每個(gè)數(shù)據(jù)源與其目的地相連。此外,為了盡量降低鏈路使用數(shù)量,我們對(duì)每條最短路徑盡可能優(yōu)先使用無線鏈路。如果無線鏈路無法支持?jǐn)?shù)據(jù)傳輸,則使用有線鏈路。此外,為了高效利用每條鏈路的容量,我們?cè)跇?gòu)建多播樹時(shí)為數(shù)據(jù)率較大的多播樹賦予較高優(yōu)先級(jí)。
本文算法的偽代碼見算法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)先級(jí)。如果多播群組k 的優(yōu)先級(jí)Pk較高,則我們應(yīng)該優(yōu)先為該多播群組構(gòu)建多播樹。在第4行,使用集合記錄哪些無線鏈路可用于傳輸多播群組k 的流量。在第5行,使用集合來記錄多播群組k 有多少個(gè)目的地可以竊聽到目的地 (機(jī)架)訪問點(diǎn)傳輸?shù)亩嗖?shù)據(jù)。在第6 行,使用集合來表示多播群組k 有多少個(gè)目的地可以接收到數(shù)據(jù)且初始化為。
然后,算法開始為每個(gè)多播群組構(gòu)建由有線鏈路和無線鏈路組成的多播樹 (第7~29行)。對(duì)每個(gè)多播群組k,因?yàn)闊o線數(shù)據(jù)中心往往采用窄波束有向天線,所以我們假設(shè)每個(gè)無線訪問點(diǎn)ax(x ∈νk)試圖把多播群組k的數(shù)據(jù)傳輸給每個(gè)無線訪問點(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的無線鏈路被加入集合。當(dāng)嘗試遍歷玩所有目的地訪問點(diǎn)對(duì)后,將多播群組k的優(yōu)先級(jí)Pk設(shè)為Tk×(第13 行)。也就是說,如果可以竊聽到無線訪問點(diǎn)傳輸?shù)臄?shù)據(jù)的目的地增多且多播群組k 的流量數(shù)據(jù)率更高,則可進(jìn)一步降低數(shù)據(jù)冗余。因此,我們優(yōu)先為這種多播群組構(gòu)建多播樹且使用無線訪問點(diǎn)。
所有多播群組的優(yōu)先級(jí)設(shè)置完畢后,我們通過降低Pk(1≤k≤N)的屬性來重新組織多播群組的索引,實(shí)現(xiàn)P1≥P2…≥PN(第14行)。然后,我們開始為每個(gè)多播群組構(gòu)建多播樹,并且采用每個(gè)多播群組的新索引,即多播群組k=1的優(yōu)先級(jí)P1最高 (第15~29行)。對(duì)多播群組k,我們通過降低(∩k)來重新組織無線鏈路索引∈,以便選擇可以覆蓋盡量多目的地的無線鏈路(第16行)。然后,對(duì)每個(gè)無線鏈路∈,如果滿足如下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行)。雖然無線鏈路被采用且可把數(shù)據(jù)傳輸給部分目的地,但是訪問點(diǎn)ax沒有路徑可接收來自發(fā)射機(jī)vk的多播數(shù)據(jù)流。于是,我們?yōu)榻o定的一對(duì)數(shù)據(jù)源vk和機(jī)架x 的訪問點(diǎn),搜索由有線鏈路和無線鏈路構(gòu)成的最短路徑。每當(dāng)調(diào)用SHORTEST-PATH()函數(shù)時(shí),它均試圖尋找從多播群組k 的源vk通往目的地x 且使用鏈路最少的最短路徑(第21行)。對(duì)該條路徑,我們首先盡量使用無線鏈路。如果無線鏈路不滿足訪問點(diǎn)容量約束,則我們采用有線鏈路。然后,對(duì)應(yīng)的指示函數(shù)lW(k,)和lF(k,e)設(shè)為1。
在第22~27行,雖然目的地機(jī)架v的訪問點(diǎn)av可以竊聽到無線傳輸 (即v∈∩),但是它可能沒有足夠的容量來接收數(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行)。正式來講,如果部分剩余目的地沒有路徑可以接收多播數(shù)據(jù) (即 k\≠),則我們使用SHORTEST-PATH ()函數(shù)為多播群組k的每個(gè)剩余目的地確定一條最短路徑 (第28~29行)。最后,我們?yōu)槊總€(gè)多播群組返回一個(gè)由有線鏈路和無線鏈路構(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((+))。
本節(jié)給出一種基于實(shí)際無線數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)的仿真模型來評(píng)估本文無線數(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ù)無線數(shù)據(jù)中心的有線和無線鏈路來構(gòu)建最短路徑樹。對(duì)每個(gè)最短路徑樹,算法試圖首先使用無線鏈路。直到訪問點(diǎn)的可用容量耗盡,算法將會(huì)改用有線鏈路。性能指標(biāo)為所有多播群組的總體數(shù)據(jù)傳輸流量。
我們根據(jù)文獻(xiàn) [10]微軟部署情況來研究具有分層拓?fù)浣Y(jié)構(gòu)的無線數(shù)據(jù)中心。無線數(shù)據(jù)中心共有160 個(gè)架頂,每個(gè)架頂有一個(gè)有線交換機(jī)和一個(gè)基于有向窄波束天線的60GHz無線訪問點(diǎn)。根據(jù)微軟的實(shí)際測(cè)量數(shù)據(jù),當(dāng)兩條平行鏈路間距低于22英尺時(shí)會(huì)出現(xiàn)互擾。請(qǐng)注意,機(jī)架寬度約為24英尺[12]。然后,我們可以計(jì)算無線訪問點(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ù)中心生成更多小型群組的冪律分布。具體來說,對(duì)冪律分布,根據(jù)如下概率生成每個(gè)多播群組k的目的地?cái)?shù)量
表2 參數(shù)設(shè)置
圖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ī)部署于無線數(shù)據(jù)中心,最短路徑樹可能會(huì)快速耗盡每條無線鏈路的容量。于是,改為使用有線鏈路,且最短路徑樹的性能與Steiner樹類似。相反,相比于其它兩種算法,EWDCMT 算法在群組規(guī)模均勻分布時(shí)對(duì)數(shù)據(jù)冗余的降低程度要高于群組規(guī)模冪律分布時(shí)。這是因?yàn)楸疚乃惴梢愿咝褂妹織l無線鏈路,并且試圖尋找可以把數(shù)據(jù)傳輸給盡量多目的地的訪問點(diǎn)。因此,當(dāng)每個(gè)多播群組有更多目的地時(shí),本文算法可以將無線媒介的優(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è)多播群組的高效無線鏈路可能無法使用。為了避免過度使用,這兩個(gè)算法必須選擇其它效率較
圖2 多播群組數(shù)量對(duì)總體多播數(shù)據(jù)流量的影響。
低的無線/有線鏈路來構(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)密集分布的無線數(shù)據(jù)中心構(gòu)建多播樹是個(gè)非常復(fù)雜的問題。
本文研究了無線數(shù)據(jù)中心網(wǎng)絡(luò)的群組通信問題。具體來說,我們研究了有線和無線鏈路共存條件下的多播樹構(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)解決方案和無線數(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 的無線多播比例公平調(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ò)編碼的無線多播速率選擇機(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.