周忠華，彭智朝，趙志鵬

ZHOU Zhonghua1,PENG Zhichao2,ZHAO Zhipeng3

1.廣東財經(jīng)大學(xué) 網(wǎng)絡(luò)信息中心，廣州 510320

2.湖南人文科技學(xué)院 信息學(xué)院，湖南 婁底 417000

3.天津大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，天津 300350

1.Network Information Center,Guangdong University of Finance&Economics,Guangzhou 510320,China

2.School of Information,Hunan University of Humanities,Science and Technology,Loudi,Hunan 417000,China

3.School of Computer Science and Technology,Tianjin University,Tianjin 300350,China

1 引言

隨著云計算和大數(shù)據(jù)的快速發(fā)展，數(shù)據(jù)中心東西向流量遠(yuǎn)遠(yuǎn)超過南北向流量，這給網(wǎng)絡(luò)基礎(chǔ)架構(gòu)帶來了前所未有的挑戰(zhàn)[1-2]。為應(yīng)對大帶寬和低延遲的需求，光交換比電交換在容量和功耗方面有更好的性能[3]。目前，光儲存技術(shù)仍不成熟，因此電緩存光交換技術(shù)被廣泛應(yīng)用于工業(yè)領(lǐng)域中[4-5]。盡管光交換能提高傳輸速率，但網(wǎng)絡(luò)擴展性仍然受限。多級Clos架構(gòu)被應(yīng)用于DCN中支持大規(guī)模的服務(wù)，此架構(gòu)于1953年被Charles Clos提出，最初被用于電話交換網(wǎng)絡(luò)，通過設(shè)計較少的交叉點減小硬件開銷來實現(xiàn)非阻塞交換[6]。由于其較好的擴展性，基于電緩存和光交換的多級Clos網(wǎng)絡(luò)已被作為DCN中典型的網(wǎng)絡(luò)拓?fù)洌渲休斎牒洼敵黾壊捎脦в芯彺娴碾娊粨Q架構(gòu)，而中間級交換機采用光交換架構(gòu)。

在DCN中，為了提高吞吐量和減少數(shù)據(jù)包傳輸延遲，采用有效的調(diào)度算法可實現(xiàn)負(fù)載均衡，并使網(wǎng)絡(luò)資源被更高效地利用。單個光交換機中調(diào)度算法已經(jīng)被大量地研究[7-8]，但目前的研究只是單純將這些算法應(yīng)用到多級中[9-10]，而并沒考慮多級架構(gòu)的自身特征，故沒有利用Clos網(wǎng)絡(luò)的多路徑特性。例如現(xiàn)存的ADAPT[10]算法在單級中能通過給定的任意流量矩陣來調(diào)節(jié)配置數(shù)量以實現(xiàn)加速比最小化，但此算法在生成配置過程中仍有一些空閑時間槽未被利用。在多級網(wǎng)路中，這些空閑時間槽能通過多跳路由被額外的數(shù)據(jù)傳輸所利用，進(jìn)而實現(xiàn)負(fù)載均衡和減小網(wǎng)絡(luò)中數(shù)據(jù)包的傳輸延遲。

為了實現(xiàn)上述目標(biāo)，本文提出了一個新穎的多跳路由和調(diào)度（Multi-Hop Routing and Scheduling，MHRS）算法，其核心思想是通過探索Clos網(wǎng)絡(luò)中多跳路由容量來利用單級調(diào)度算法中所浪費的空閑時間槽，以實現(xiàn)負(fù)載均衡。為了簡化配置復(fù)雜度，所有的光交換架構(gòu)保持同步的配置切換。負(fù)載均衡意味著一些在單個交換機調(diào)度情況下被浪費的空閑時間槽可以通過多跳路由被利用，進(jìn)而通過利用有效的網(wǎng)絡(luò)資源而使數(shù)據(jù)包傳輸延遲降低。

2 相關(guān)工作

目前最常用的調(diào)度方法為矩陣分解法，如前面提到的ADAPT[10]算法，其分解過程為：用矩陣T表示流量矩陣，矩陣中的元素tij表示的是輸入級端口i到輸出級端口j的流量，其中i,j=1,2,…,N-1，N為交換機的端口數(shù)，而矩陣可分解為多個矩陣的和，如式（1）所示。矩陣Pn為一個置換矩陣，即在同一行同一列中只有一個元素為1，其余元素均為0。若矩陣元素，表示輸入級端口i至輸出級端口j間無連接，若,表示輸入級端口i至輸出級端口j間有連接。φn為每個置換矩陣占用的時隙數(shù)。且流量矩陣與置換矩陣要滿足式（2）。這樣就能保障數(shù)據(jù)包被100%調(diào)度，也就完成了一次數(shù)據(jù)調(diào)度過程。

但是ADAPT算法并沒有考慮到，由于存在一些不滿稚的配置矩陣，也就是說這些矩陣依然有傳輸更多數(shù)據(jù)的能力，并且與當(dāng)前傳輸?shù)臄?shù)據(jù)不發(fā)生沖突。由于配置矩陣會有空時間槽，即在同一配置狀態(tài)下，有些鏈路會一直傳輸數(shù)據(jù)，但是有些鏈路傳輸完數(shù)據(jù)之后會留下空時間槽，如果能充分利用這些空時間槽，可以減少數(shù)據(jù)調(diào)度的時間。本文在ADAPT算法基礎(chǔ)上，第一次提出了多跳路由和調(diào)度結(jié)合的思想，利用單跳調(diào)度和多跳調(diào)度的方法，根據(jù)Clos多級架構(gòu)的特性，盡可能利用ADAPT產(chǎn)生的配置矩陣中存在的空時間槽進(jìn)行包交換，最大化地利用網(wǎng)絡(luò)中的帶寬，以減少包交換的時間。

3 系統(tǒng)模型

圖1展示了一個三級Clos網(wǎng)絡(luò)，由許多小規(guī)模的交換模塊組成[11]。這些模塊被組成為3個層級（即輸入級、中間級和輸出級）。輸入級有k個n×m的輸入模塊（Input Modules，IMs），中間級有m個k×k的中間級模塊（Center Modules，CMs），輸出級有k個m×n的輸出級模塊（Output Modules，OMs）。每個層級上的每個交換模塊通過唯一的一條鏈路被連接到相鄰層級上的所有交換模塊。通常情況下，在IMs和OMs上的ToR交換機采用電交換架構(gòu)，在CMs上的核心交換機采用光交換架構(gòu)，此交換網(wǎng)絡(luò)的輸入/輸出端口數(shù)為N=n×k。

圖1 Clos(m,n,k)網(wǎng)絡(luò)

如圖2所示，本文采用了基于MSM-Clos的數(shù)據(jù)中心網(wǎng)絡(luò)[12]。IMs和OMs采用帶有緩存的電交換架構(gòu)，CMs采用光交換架構(gòu)。因為虛擬輸出隊列（Virtual Output Queuing，VOQ）可以消除頭（Head-of-Line，HoL）阻塞問題，故在IMs上基于MSM-Clos的網(wǎng)絡(luò)采用VOQ，數(shù)據(jù)包從VOQ出來后執(zhí)行電光轉(zhuǎn)換，經(jīng)過CMs后執(zhí)行光電轉(zhuǎn)換進(jìn)入OMs中的輸出隊列（Output Queue，OQ）。定義在IM(i)上第n個輸入端口為IP(i,n-1),在OM(j)上第n個輸出端口為OP(j,n-1)。在IM(i)交換模塊中要到達(dá)OP(j,n-1)的包被儲存在VOQ(i,j,n-1)中，而CMs組成的光交換模塊在更新配置狀態(tài)時會遭遇一個重配置開銷δ[13]。在此期間由于數(shù)據(jù)包不能被傳輸，為了實現(xiàn)無丟包，一個加速比必須去彌補重配置開銷來阻止輸入級交換模塊的緩存溢出[14-15]。流量矩陣CN×N被定義為在T時間槽內(nèi)輸入級累積的數(shù)據(jù)包，流量矩陣的每行匹配輸入級的交換模塊，每列匹配輸出級的交換模塊，將輸入交換模塊和輸出交換模塊之間的連接看作一個配置，用1表示兩個交換模塊的狀態(tài)是連接的，0代表是斷開的。

圖2MSM-Clos網(wǎng)絡(luò)

在MHRS算法的數(shù)據(jù)包的傳統(tǒng)調(diào)度過程中，數(shù)據(jù)包首先在輸入級交換模塊中積累一段時間，然后輸入級中積累的數(shù)據(jù)包通過中間級交換模塊被傳輸?shù)捷敵黾墸詈髷?shù)據(jù)包被緩存到輸出隊列后而被分發(fā)到相應(yīng)的目的端口。圖2展示了數(shù)據(jù)包從IP（0，0）到OP(k-1,n-1)的轉(zhuǎn)發(fā)過程。第一步是流量累積，數(shù)據(jù)包被儲存在VOQ(0,k-1,n-1)，并經(jīng)過T時間槽，然后數(shù)據(jù)包通過用紅虛線標(biāo)注的路徑被路由到目的交換級。最后數(shù)據(jù)包被儲存到OQ(k-1,n-1)，等待被分發(fā)到OP(k-1,n-1)。若沒有匹配的配置但存在空閑時間槽，這些數(shù)據(jù)包就不能被轉(zhuǎn)發(fā)，從而造成帶寬的浪費。

4MHRS算法

4.1MHRS算法核心思想

為了提高網(wǎng)絡(luò)吞吐量，本文提出了一個MHRS算法，其核心思想是采用單跳或多跳方法來利用空閑時間槽，以盡可能多地傳輸包，而不是使數(shù)據(jù)包在被匹配到合適的配置時才被傳輸。其通過兩步最小化數(shù)據(jù)包傳輸延遲實現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡：

（1）單跳路由優(yōu)先去核查是否存在一些空閑時間槽被直接利用。

（2）如果單跳不能直接實現(xiàn)，則通過嘗試找到一個可行的多跳傳輸路徑來進(jìn)一步利用空閑時間槽。其中單機環(huán)境不能采用多跳策略。

4.2 調(diào)度過程

關(guān)于MHRS算法的調(diào)度過程，首先定義沒有匹配狀態(tài)但能找到一條合適傳輸路徑的數(shù)據(jù)包為主動包。相反，通過傳統(tǒng)方式傳輸?shù)臄?shù)據(jù)包為被動包。當(dāng)一些被動包儲存在輸入級的VOQ中，但沒有被調(diào)度時，若有一些主動包選擇此VOQ，主動包將會被阻塞。為了避免此現(xiàn)象，在輸入級為主動包設(shè)置一個專用的虛擬輸出隊列（Dedicated Virtual Output Queuing，DVOQ）。

一些被動包也可能存在于OQ中，以致主動包不得不在其隊列后等待。為避免此現(xiàn)象，每個輸出端口將被配置兩個具有不同優(yōu)先級的輸出隊列。高優(yōu)先級隊列用于主動包傳輸，而低優(yōu)先級隊列用于被動包傳輸。當(dāng)它們需要同時離開輸出端口時，高優(yōu)先級隊列中的主動包可以提前離開，且在輸出級添加一個優(yōu)先輸出隊列（Priority Output Queue，POQ）。

多跳調(diào)度過程有四步：

（1）主動包尋找一個可行的DVOQ，盡管當(dāng)前的DVOQ不能確保通過單跳調(diào)度后數(shù)據(jù)包被傳輸?shù)侥康亩丝冢?/p>

（2）主動包通過中間級被傳輸?shù)捷敵黾墸?/p>

（3）主動包在輸出級被儲存在POQ中等待被分發(fā)到對應(yīng)的輸出端口，且假如這些數(shù)據(jù)包到達(dá)目的端口，則此調(diào)度結(jié)束，此過程即為單調(diào)調(diào)度；

（4）假如此輸出端口不是主動包的目的端口，主動包應(yīng)盡快離開輸出端口并繼續(xù)進(jìn)入輸入端口以尋找一個合適的DVOQ。

主動包重復(fù)前三步直到被分發(fā)到目的端口，此過程即為多跳調(diào)度。顯然與多跳調(diào)度相比，單跳調(diào)度更加有效。

圖3 多跳調(diào)度過程

圖3展示了數(shù)據(jù)包從IP（0，0）到 OP(k-1,n-1)的一個多跳轉(zhuǎn)發(fā)過程。第一步主動包從VOQ(0,k-1,n-1)到可行的DVOQ(0,j,n-1)。第二步主動包通過紅虛線路徑被路由到輸出級。第三步主動包在被分發(fā)到OP(j,n-1)前被儲存在POQ(j,n-1)中。第四步主動包再次進(jìn)入(i,n-1)中，其中OP(j,n-1)和IP(i,n-1)是同一個端口。它會重復(fù)第一步去尋找可行的DVOQ(i,k-1,n-1)，然后主動包通過紅實線路徑被路由到輸出級。最終主動包被儲存在POQ(k-1,n-1)中等待被分發(fā)到OP(k-1,n-1)。其中主動包通過兩個中間級進(jìn)行交換，此過程為兩跳調(diào)度。

4.3MHRS算法描述

MHRS算法的詳細(xì)過程：首先輸入級交換模塊對收到的數(shù)據(jù)包進(jìn)行累積，形成一個r×r的流量矩陣C，然后利用ADAPT算法對當(dāng)前的流量矩陣C進(jìn)行分解以生成商矩陣Q和余矩陣R，以及對應(yīng)的配置矩陣PQ、PR和配置權(quán)重φ。配置矩陣PQ以及PR都是置換矩陣，其個數(shù)分別為N1和N2，其中N1+N2=Ns。由于ADAPT產(chǎn)生的配置矩陣PQ中存在空時隙，可通過單跳和多跳的方法來利用這些空時隙進(jìn)行數(shù)據(jù)包交換，以減少數(shù)據(jù)包交換的時間。

4.3.1 單跳調(diào)度

由ADAPT產(chǎn)生的配置矩陣PQ中，存在一些配置矩陣PQE，其秩不為r，即這些矩陣依然有傳輸更多數(shù)據(jù)的能力，并且與當(dāng)前所傳輸?shù)臄?shù)據(jù)不發(fā)生沖突。如找到一個矩陣PQP使得PQP+PQE=PQF，其中PQF是一個滿秩的轉(zhuǎn)換矩陣，且若將PQF替代PQE之后，在能傳輸PQE以前數(shù)據(jù)的同時，還能傳輸余矩陣R中的數(shù)據(jù)，則將PQF替代PQE。理論上PQP的個數(shù)會有r-rQ個，其中rQ是PQE的秩，但在算法中選擇集合S={1,2,r-rQ}中最小的那一個，其中集合S是PQP的序號索引。

單跳調(diào)度偽代碼：

1.forQ=1:Ns-Ndo

2.K=0

3. fori=1:Ndo

4. forj=1:Ndo

5. if配置矩陣PQ中，存在一些配置矩陣PQE，其秩不為rthen

6.K++

7. end for

8. end for

9. 找到一個矩陣PQP使得PQP+PQE=PQF，其中PQF是一個滿秩的轉(zhuǎn)換矩陣。

10.end for

11.fori=1:Ndo

12. forj=1:Ndo

13. if將PQF替代PQE之后，在能傳輸PQE以前數(shù)據(jù)的同時，還能傳輸余矩陣R中的數(shù)據(jù) then

14. 將PQF替代PQE

15. end for

16.end for

4.3.2 多跳調(diào)度

由于采用ADAPT所產(chǎn)生的配置矩陣PQ會有空時隙，即在同一個配置狀態(tài)下，有些鏈路會一直傳輸數(shù)據(jù)，但是有些鏈路傳輸完數(shù)據(jù)之后會留下空時隙。如果不充分利用這些空時隙，會造成浪費。算法利用這些空時隙的方法是，遍歷余矩陣R中所有元素Rij，如果存在矩陣Ph∈PQ，且矩陣Ph中存在一些1，其位置滿足前一個1的列序號是后一個1的行序號，并且在這些1中有兩個位置不相同的1，即一個1的行序號為i，而另一個1的列序號為j。這樣就能找到一條鏈路L:i→l1→l2→…→ln→j，其 中 (i,l1),(l1,l2),…,(ln,j)是矩陣Ph中滿足上述條件1元素所存在的位置。進(jìn)而算法在不影響原本傳輸數(shù)據(jù)的同時，能夠傳輸更多數(shù)據(jù)，其最多傳輸包的個數(shù)為N，計算公式如下：

多跳調(diào)度偽代碼：

4.4MHRS算法例子

以下展示了一個MHRS算法實例，根據(jù)ADAPT算法得出Ns=6，φ=14，流量矩陣C被分解為商矩陣Q和余矩陣R。單跳調(diào)度中，直接傳輸R中的主動包使配置矩陣P1和P2的空閑時間槽被利用。而后在多跳調(diào)度中，余矩陣R中第3行第4列的兩個主動包在P2中找到一條可行的多跳路徑L:3→4→2，由于第11～14 s期間（3，4）、（4，2）位置是空閑時間槽，因此這兩個主動包通過多跳調(diào)度被傳輸。

（1）ADAPT算法

（2）單跳調(diào)度

（3）多跳調(diào)度

5 性能仿真

5.1 仿真平臺及算法流量模型介紹

在8 GB內(nèi)存且4 GHz的計算機上用MATLAB 7.11進(jìn)行仿真，Clos架構(gòu)的參數(shù)分別設(shè)置為n=4,m=4,k=4。采用均勻流量模型和非均勻流量模型來實現(xiàn)兩種類型的伯努力包到達(dá)過程。每個輸出端口在每個槽中生成一個概率p，其中p(0≤p≤1)是端口的輸出負(fù)荷。且均勻流量模型指數(shù)據(jù)包到達(dá)每個輸入端口的概率相等，非均勻流量模型意味著數(shù)據(jù)包到達(dá)每個輸入端口的概率是不同的。為了有效地驗證算法的性能，研究采用隨機生成的350000個樣本數(shù)據(jù)得出實驗結(jié)果，這些數(shù)據(jù)由流量矩陣CN×N表示，而后將平均延遲變化與所提供的不斷增加的負(fù)荷進(jìn)行比較。

5.2 在均勻流量模型下的性能

圖4表示在均勻流量模型和δ={1,3,5}下，對ADAPT和MHRS的平均延遲性能進(jìn)行比較。在ADAPT和MHRS中，隨著負(fù)荷的增加延遲會迅速增加；在負(fù)荷值和δ相同時，MHRS上的延遲小于ADAPT的延遲；在ADAPT和MHRS中，延遲隨著δ減小而降低。例如，在橫坐標(biāo)表示的第4個輸入負(fù)荷中，當(dāng)δ為5時，ADAPT算法的平均延時為0.64%，而MHRS算法的平均延時是0.55%，平均延遲性能提升了14%。兩種算法的平均延時都增加了，且針對不同的輸入負(fù)荷，兩者平均延時保持同步增加。

圖4 均勻流量模型中不同輸入負(fù)荷下平均延遲的比較

5.3 在非均勻流量模型下的性能

MHRS的核心思想是利用空閑時間槽，更適合非均勻流量模型。非均勻流量分布的度ω對算法的執(zhí)行和結(jié)果有重大影響，非均勻的輸入負(fù)荷p′遵循式（6）。圖5表明了其計算結(jié)果，即當(dāng)非均勻流量分布ω=1時，MHRS的延遲變化和ADAPT差別不大。但是當(dāng)ω={3,4,5}時，二者有很大的差別。因此MHRS的性能在非均勻流量模型中比在均勻流量模型中的效果更好，這說明MHRS更適合非均勻的流量模型。

圖5 非均勻流量模型中不同ω下平均延遲的比較

6 結(jié)束語

本文給出了一種多跳路由和調(diào)度算法（MHRS）來實現(xiàn)DCN中的負(fù)載均衡。通過對Clos網(wǎng)絡(luò)多跳能力進(jìn)行探索，MHRS可以通過多跳路由策略進(jìn)一步利用調(diào)度中的空閑時間槽，使DCN實現(xiàn)高帶寬利用率和低傳輸延遲。MHRS包括兩個步驟，首先檢查一些空閑時間槽是否可以在單跳方式中直接使用。若不行則調(diào)用第二個步驟，通過尋找一個可行的多跳路由來利用空閑時間槽中的帶寬，空閑時間槽可以在調(diào)度中跨多個交換配置架構(gòu)。仿真結(jié)果表明，通過對Clos網(wǎng)絡(luò)的多跳路由功能進(jìn)行探索，有效地減少了數(shù)據(jù)包傳輸延遲，并實現(xiàn)了負(fù)載均衡。