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.