基于AWGR的動態光網絡及拓撲映射

范修宏，臧大偉，程 東

(1.中國科學院 西安光學精密機械研究所，陜西 西安 710119；2.中國科學院 計算技術研究所，北京 100190)

0 引 言

現在的數據中心廣泛使用虛擬化技術，為了高效利用數據中心的物理資源，需要將盡可能多的虛擬拓撲映射到數據中心物理服務器和網絡鏈路上運行。然而，由于資源量及映射算法的不足，經常會發生虛擬拓撲映射失敗的問題，據統計有99%的不成功映射是由于虛擬鏈路無法映射引起[1]。當前數據中心網絡缺乏彈性，是導致虛擬鏈路無法有效映射的主要原因，造成了數據中心硬件資源的極大浪費。光交換技術具有很強的靈活性和極低的能耗[2]，非常適合用來增強數據中心網絡的彈性。

基于網絡結構與映射算法協同設計的思路，本文提出了一種基于AWGR器件的光電混合網絡結構和面向此彈性網絡的虛擬拓撲映射算法。主要創新點在于，利用靈活可變的光域網絡，通過改變波長調整網絡之間的連接關系，重新分配鏈路的資源，從而提高數據中心的資源利用率和能效。模擬評測結果顯示，該方法可以極大提高數據中心的資源利用率和收益。

1 相關研究

在光電混合數據中心網絡結構研究方面，當前大量的研究試圖結合高帶寬的光域交換技術和高靈活性的電域交換技術，如c-Through,Helios,DOS,Proteus[3-5],Petabit Optical Switch[6]等經典的光電混合網絡結構。c-Through是一種基于慢速MEMS交換機的光電混合網絡結構，它在電域樹形網絡的基礎上增加一個光域交換機，每一個機柜中的柜頂交換機同時連接到電域網絡和光域網絡，大流量的網絡流在兩個機柜之間的光鏈路上傳輸。在運行過程中，流量監控系統根據任意兩個機柜之間的帶寬需求，形成一個帶寬需求矩陣；為了提高光鏈路的帶寬利用率，光線路的配置轉變成一個最大權值的完美匹配問題，使用Edmonds算法來求解匹配結果，并配置MEMS光交換機，重構光網絡的連接關系，然后使用基于VLAN的路由方法將ToR中的流量分配給電域網絡和光域網絡。但是，該結構使用的MEMS交換機，配置延遲達到秒級，只適合處理持續時間達到數秒鐘的網絡流，而不能加速持續時間較短的網絡流。

如何利用光電混合網絡的靈活性，高效、動態地將用戶需求映射到物理拓撲是另外一個核心問題，可以分為在線映射算法和離線映射算法兩種。在線映射算法[7]為隨機到達的虛擬網絡請求給予資源分配，當虛擬網絡拓撲運行結束后，其自動將資源回收。離線映射算法已知虛擬拓撲映射請求的一些詳細時間，對一段時間內收集到的虛擬拓撲請求進行集中的處理，由于虛擬拓撲一般需要長時間運行，本文所提出的方法為離線映射算法。按照虛擬拓撲映射計算方式的不同，映射算法分成集中式映射[8]與分布式映射[9]。集中式算法會在一個或幾個中心點上計算映射方式，由中心點負責資源的分配；而分布式算法將計算任務分配到若干的節點，由若干的節點共同來完成資源分配和拓撲映射。按照虛擬節點與鏈路處理的處理順序不同，將映射算法分為一階段映射[10]和二階段映射[11]。一階段算法同時映射虛擬節點和虛擬鏈路;而二階段映射算法通常先進行節點的映射、后進行鏈路的映射，本文提出的算法是一種二階段的映射算法。當前的研究主要在電域網絡上來進行拓撲的映射，例如文獻[12]提出了一種二階段的虛擬拓撲映射方法，在虛擬節點映射階段，采用貪婪算法將資源約束高的虛擬節點優先映射到資源量大的物理節點，同時使用路徑分割的算法VNE-Splitting，將同一條網絡流分散到多條路徑上運行。這種方法提高了映射的成功率但需要特殊的硬件支持，并會產生網絡包亂序的問題。文獻[10]提出了一種一階段的虛擬拓撲映射算法，它將問題歸約為一個SID(subgraph isomorphism detection)問題[13]，并提出了一個啟發式的算法來尋找Isomorphism圖，該方法可以取得很好的收益，但是仍然是針對純電域網絡。

同時也有研究試圖在光域中映射虛擬拓撲，例如文獻[14]。但是它們通過波長的分配來動態變化鏈路的帶寬，而不會通過橋接光鏈路來降低網絡直徑，并不能有效增加數據中心的收益。

綜上所述，當前的研究中并未將光域橋接網絡用于虛擬拓撲映射的研究中，本文具有前瞻性和創新性。

2 數據中心資源形式化

在數據中心運行過程中，每個虛擬拓撲請求不僅包含如計算能力、放置位置等節點資源約束，還包含帶寬、延遲等鏈路資源約束。所映射到數據中心中的虛擬拓撲，可以共享相同的底層節點的計算資源和鏈路資源，而不能采用獨占模式。本節中給出虛擬網絡映射問題的形式化描述，并給出該問題一些評價指標。

假設每一個虛擬拓撲映射請求中只包含一個虛擬拓撲，因此可以用三元組V(i)(Gv,ta,td) 表示第i個虛擬網絡請求，其中Gv表示此請求包含的虛擬拓撲。當ta時刻，虛擬拓撲請求到達時，數據中心需要為此虛擬網絡分配滿足節點和鏈路資源約束的物理資源，在虛擬網絡運行持續td時間后，虛擬網絡運行完成，其占用的相應資源被釋放。如果請求到來時，沒有足夠的資源分配，則將該請求放在等待隊列中，或直接拒絕映射。

3 基于AWGR的光電混合網絡結構

光電混合網絡充分利用靈活可變的光域網絡，從物理鏈路層改變數據中心網絡的拓撲架構，從而可以實現網絡資源的靈活調度和分配。本文所基于的數據中心物理網絡包括兩部分，分別為固定拓撲的電域網絡和動態可變的光域網絡。固定拓撲的電域網絡可以采用任意的拓撲結構如Fat-tree,Torus，Mesh等，同時電域網絡根據自己的拓撲結構均勻的分成若干的區塊，例如在樹形拓撲結構中，每一個機柜就是一個區塊，區塊的數量與所采用的光交換機的端口數相等。在每一個區塊中選擇一個具有最大通信能力的物理位置作為光域網絡的連接點，例如在樹形拓撲中的連接點就是ToR(top of rack)交換機的上行端口，而在Torus拓撲中，可以是區塊中任意得到一個點，如圖1所示。

圖1 動態光電混合網絡實例

在該結構中使用了多種光器件：首先是TWC(tunable wavelength converters)可調波長光調制器，它將輸入的光信號變換成給定波長輸出；目前的160 Gbps的波長轉換帶寬[15]的TWC已經商用，其重構時間只有十幾個納秒。其次是AWGR(arrayed-waveguide grating router)光波長路由器，它根據光的波長進行路由，允許不同輸入端口的光線路由至同一輸出端口；由端口i輸入的波長為w的信號將被路由 [(i+w-2)modN]+1 端口，其中N是端口數；基于這種特性，同一輸出端口可以接收不同波長的多個光信號，并復用在一條光纖上輸出，而不發生網絡競爭，當前高維度的512端口的AWGR器件技術已經成熟。最后是用于接收端光電轉換的OCA(optical channel adapter)器件，在接收端它會將光信號變成電信號；OCA器件有一個1：N的多路解復用器，可以將光纖中混合光信號分離成多束單波長的光信號，并由后端的接收陣列將這N個光信號轉換為電信號。

在光電混合網絡結構中，采用一個單層的光網絡作為電域網絡的輔助網絡。如圖1所示，每一個ToR交換機分別通過電域接口和光域接口連接到上層的電域交換機和光域交換機，光域端口的發送鏈路通過TWC光器件連接到OCA器件的輸入端(Tx)，接收鏈路連接到OCA器件的接收端(Rx)。

在控制層面，系統有一個集中的控制器，負責帶寬需求測量、鏈路仲裁控制和鏈路重構控制。在運行時，控制器收集系統中的拓撲映射請求信息，同時控制每個TWC波長變換器件和電域交換機的路由器件，根據鏈路匹配算法在兩個機柜間建立一條持續的光鏈路。

該光電混合網絡結構與c-Through、DOS等有相似之處，但是有著本質的區別：與經典光電混合網絡c-Through相比，同樣在機柜之間建立起一條較持續的光線路，屬于光線路交換(OCS)的范疇；但由于系統中使用了TWC變換器件納秒級的波長變換特性，可以快速切換光線路，使用網絡能夠按照網絡流量特征實時、快速重構。

4 虛擬拓撲映射算法

在虛擬拓撲映射過程中，分為節點映射、網絡分割、鏈路映射3個步驟，本文依次對3個步驟所采用的算法進行介紹。

4.1 虛擬節點映射算法

本文使用兩階段映射算法來完成虛擬拓撲的映射，即：首先根據虛擬節點的資源需求將虛擬節點映射到物理節點，然后再完成虛擬鏈路的映射。我們采用貪心策略完成虛擬節點的映射。在算法運行之前，會收集較長時間窗口內的虛擬拓撲映射請求，并將其放在等待隊列中，如果請求隊列中的某個請求較長的時間沒有得到響應，則刪除這個請求。

在算法運行時，首先會按照虛擬拓撲的收益將虛擬拓撲請求按照從高到低排序，優先映射具有高收益的虛擬拓撲。然后，對于每一個虛擬拓撲中的虛擬節點按照對計算能力的需求程度排序，優先對計算能力需求高的虛擬節點進行映射。定義3個公式

(1)

(2)

Tpb=αRp+(1-α)Rb

(3)

其中，Rp表示物理節點所擁有的計算能力與虛擬節點需要的計算能力的差值，Rb表示物理節點所擁有的網絡帶寬總和與虛擬節點需要的網絡帶寬的總和的差值，在選擇物理節點的時候，必須要滿足這兩個值大于0。而Tpb是計算能力差值和帶寬差值的一個和，根據計算資源和帶寬資源的昂貴程度來調整此值，并選取值最小的節點作為映射節點以保證盡可能的將虛擬節點映射到與其需求資源量相當的物理節點上。

算法1：虛擬節點映射算法

輸入：虛擬映射請求

輸出：虛擬節點位置

(1)按照收益高低排列虛擬拓撲請求；

(2)從隊列中選擇一個具有最高收益的虛擬拓撲映射請求VR；

(3)將此虛擬拓撲請求中虛擬節點按照計算資源需求排序；

(5)在物理拓撲中尋找物理節點ns滿足如下條件

如果有節點無法滿足此限制，則從隊列中刪除虛擬拓撲請求，并放在等待隊列中，GOTO步驟(2)；

(6)GOTO步驟(4)，直到所有的節點映射完成；

(7)GOTO步驟(2)，直到所有的請求被映射完成；

(8)算法結束。

如果有任何一個虛擬節點不滿足上述條件，則映射失敗并將已經映射的節點恢復至原狀態，同時將此虛擬拓撲映射請求放到等待隊列中。

4.2 光域拓撲重構

將虛擬節點映射到物理節點上之后，需要根據一定的規則對數據中心的光域網絡拓撲進行重構，在不同的區塊間建立快速的光鏈路，以便之后將虛擬鏈路高效的映射到物理拓撲上。

算法2：光域網絡重構算法

輸入：帶寬需求

輸出：光交換機的連接關系

(1)虛擬節點映射完成后，統計物理節點兩兩之間的帶寬需求量，形成矩陣M；

(2)對于數據中心中任意兩個區域，根據M計算兩個區域之間的加權帶寬消耗并形成加權帶寬消耗矩陣M′；

(3)在加權帶寬消耗矩陣M′上使用Edmonds’算法，根據不同區塊之間的帶寬消耗值計算出一個完美匹配；

(4)根據計算所得的完美匹配結果，控制光交換機在不同的區域間構建光域網絡拓撲。

定義物理拓撲中兩個區塊之間的加權帶寬消耗如式(4)所示

(4)

在算法中，統計任意兩個區域之間的物理節點的通信總量，形成加權帶寬消耗矩陣M′。為了構建光域拓撲，使盡可能多的流量在光域網絡上傳輸，光線路的配置可以歸約為一個匹配問題，在本文中使用Edmonds’算法在若干的區域中計算出一個完美匹配。計算出完美匹配后，控制TWC改變波長，實現光域網絡的構建；在重構過程中，對應鏈路中所承載的網絡流需要調度到其它鏈路中，防止重構過程中的丟包。

4.3 虛擬鏈路映射算法

在虛擬節點映射到物理節點及光域拓撲建立完成之后，將虛擬鏈路映射到實際的物理鏈路上。在虛擬節點固定的情況下，求解將虛擬鏈路映射到物理鏈路上的最優解可以歸約為不可分割流問題(UFP)，這個是NP-hard[16,17]問題。

本文中使用貪心策略，首先映射產生最大收益的拓撲的虛擬鏈路；映射每一條虛擬鏈路時，在虛擬節點映射到的兩個物理節點之間尋找一條滿足資源限制的最短路徑。對于同一個虛擬拓撲映射，優先映射帶寬需求最大的鏈路；如果沒有找到滿足資源限制的k-shortest path，則將該虛擬拓撲映射請求放入等待隊列中，并刪除已經映射的虛擬鏈路和頂點。

算法3：虛擬鏈路映射算法

輸入：物理節點帶寬需求

輸出：鏈路映射關系

(1)構建物理節點鄰接矩陣Mj, 標示節點間的鄰接帶寬；

(2)將完成節點映射的虛擬拓撲映射請求按照收益由高到低排列；

(3)選擇具有最大收益的虛擬拓撲映射請求，如果沒有，則算法停止；

(4)將選擇到的虛擬拓撲中的虛擬鏈路按照帶寬需求由高到低排序；

(5)選擇帶寬需求最大虛擬鏈路開始映射；

(6)對于每一個虛擬鏈路映射請求，通過遞增k，尋找兩個物理節點之間的k-shortest path，并且該路徑滿足B(ps)≥B(pv) 如果找到這樣的路徑，將虛擬鏈路映射到此物理鏈路，并更新臨接矩陣Mj。 GOTO步驟(5)；

(7)如果沒有找到這樣的路徑，則刪除此虛擬拓撲請求，并放入等待隊列中，GOTO步驟(3)；

5 系統評測

本部分將對提出的結構和算法進行評測，首先介紹評測所采用的拓撲生成、算法模擬等工具，然后通過實驗結果對其進行評價。在評測中，關注點在于使用動態光鏈路對虛擬鏈路映射性能和收益的提升。

5.1 評測指標

虛擬拓撲映射的主要目標在于提高數據中心物理資源的利用率，為更多的虛擬映射請求提供服務，從而提高數據中心的收益。對虛擬網絡映射的評價主要有：①物理拓撲的長期平均運營收益；②物理資源的有效利用率；③虛擬拓撲映射請求的接受率[1]。接受并映射一個虛擬拓撲的收益可以定義為式(5)，其中P(nv) 表示虛擬節點nv的計算能力需求值，B(lv) 表示虛擬鏈路lv的帶寬能力需求值，nv用來調節計算資源和帶寬資源收益的相對權重。根據式(5)，我們可以定義物理拓撲的長期平均運營收益為長時間的運營收益總和與運營收益的比值，如式(6)所示

(5)

(6)

(7)

(8)

虛擬拓撲請求的接受率不僅可以衡量物理拓撲資源的有效利用率，而且也是衡量映射算法是否高效的一個重要指標。虛擬拓撲請求的接收率定義為長時間內被成功映射的虛擬拓撲數量Vs與虛擬拓撲請求總數V的比值，如式(9)所示

(9)

5.2 評測參數設置

為了對本文提出的結構和算法進行評測，設計了一個光電混合網絡模擬器對網絡結構和映射算法進行仿真。模擬器根據提供的節點和鏈路關系，自動構建物理拓撲結構；在模擬映射過程中，它根據設置的隨機函數，生成若干的虛擬拓撲映射請求，并使用如上所示的算法執行虛擬拓撲的映射；在映射完成后，模擬器會統計接受率、鏈路資源利用率、節點資源利用率等信息。

由于本系統不針對于任何的特定拓撲結構，因此使用隨機拓撲來進行評測，其中使用GT-ITM工具[18]來生成隨機物理拓撲結構，所有物理拓撲的規模是變化的，而光域網絡的鏈路節點也隨機在物理拓撲中分布。模擬器會隨機產生若干的虛擬拓撲映射請求，其中虛擬拓撲中虛擬節點的數目滿足2至50間的均勻分布，每一對虛擬節點之間以0.5的概率具有一條虛擬鏈路相連，因此每一個虛擬拓撲中邊數的期望值為n(n-1)/4。 每一個虛擬拓撲中的虛擬節點對計算能力的需求滿足10至100間的均勻隨機分布，每一條虛擬鏈路的帶寬需求滿足0至60的均勻隨機分布，同時定義收益公式中的調節參數α=0.8。

5.3 評測結果

本文與之前的工作的最大不同之處是將靈活的光域網絡與拓撲映射算法協同設計，克服以前固定拓撲不能有效映射網絡拓撲的問題。在評測中以系統的收益為評價的標準，首先評測高速橋接鏈路對收益的影響。

在評測中以文獻[19]中提出的完全貪心算法作為基準算法，在評測中固定光域網絡的連接點的個數為N/25， 其中N為物理節點的個數，因此光域網絡的節點會隨著物理節點數的增加而增加。

從圖2所示的評測結果可見，與基準算法相比節點映射算法在沒有光網絡的情況下所獲得的總收益是基準算法的1.3倍；而如果增加光域拓撲結構之后，系統所獲得的總收益是基準算法的2到3.1倍，并且隨著物理節點數目和規模的增加，擁有光域網絡的系統可以獲得更大的收益，這主要是由于光域網絡縮短了網絡直徑，可以接受更多的虛擬拓撲映射請求。

圖2 不同結構下節點數量與收益關系

同時，在此評測了光域網絡的規模對收益的影響，在評測中電域網絡選擇了3種不同的規格，分別為1000、2000、3000節點；在評測中，以節點數為1000的物理拓撲作為基準，在不同的光域拓撲規模下分別評測收益率的變化。評測結果如圖3所示，對于同樣數量的光域網絡接入點，增加電域網絡的規模不會使收益有倍數的增長，并且隨著物理拓撲規模的增長這種損耗就更加明顯，物理拓撲節點數為2000時，總收益能達到節點數為1000時的1.9倍，而物理拓撲節點數為3000時，總收益只能達到節點數為1000時的2.75倍。這主要是由于在光域接入點數量相同的情況下，隨著物理節點數的增加使每個分區的規模變大，光域網絡對映射的效果的加速作用減弱。

圖3 不同規模拓撲收益與光節點關系

我們評測了在不同情況下物理節點的資源利用情況，在與測試1中我們使用了相同的參數，從圖4的測試結果可見，在有光域網絡的情況下，節點的利用率會有倍數的提升，這一趨勢與總收益的增長有類似的趨勢。這主要是由于評測中采用的收益因子為0.8，在數據中心中最主要、最昂貴的資源是計算資源，因此隨著物理節點資源利用率的提升，其收益也會相應提升。

圖4 不同結構下節點數量與利用率關系

在當前數據中心中隨著節點數增加和網絡半徑的增大，節點之間的通信需要經過若干次的電域交換機，期間伴隨多次光電轉換。在本文所提出的光電混合網絡結構中，由于光線路在不同網絡區間中采用光構建了一條橋接鏈路，因此可以減少光電轉換的能耗。如圖5所示，對網絡的能耗情況進行了統計，在此假設數據包每經過一級光電轉換消耗一個單位的電能。圖5數據顯示，隨著網絡規模的增加，光電混合網絡的節能效果快速顯現，當節點規模達到3000時，最高能節省22%的光電轉換次數。

圖5 不同規模拓撲能效統計

最后，評測了虛擬拓撲映射的拒絕率，相對于純電域網絡，光電混合網絡中將虛擬拓撲請求拒絕率由23%降低為8%，大概有兩倍的性能提高。

綜合上述，采用靈活光域輔助網絡的光電混合網絡結構在數據中心利用率、收益和拒絕率方面都有很大的提升。

6 結束語

隨著數據中心規模的增長，同一個虛擬拓撲中虛擬節點所分別映射到的物理節點間的距離越來越遠，其鏈路在映射過程中需要經過若干的跳步，占用了大量的物理網絡資源，因此降低了數據中心的收益。以前工作通過優化網絡映射算法來提高收益，但受到數據中心固定拓撲的限制，很難取得較好的提升；本文將光電混合動態網絡與映射算法協同設計，提出了一種基于AWGR的動態光網絡和對應的虛擬拓撲映射方法，該方法在當前數據中心的電域拓撲的基礎上，增加一層線路交換的光域網絡拓撲，在數據中心全域通過光域網絡來減少網絡直徑；結合與之匹配的虛擬拓撲映射方法，極大提升數據中心的利用率和能效，從而提高數據中心的收益。當前光網絡已經在Google、Facebook等互聯網巨頭的數據中心中嘗試使用，其巨大的資源利用率和能效優勢具有很大的應用前景。