考慮全局延遲的中間件調(diào)度問(wèn)題

李長(zhǎng)江，周湘貞，肖文顯，王俊閣

(1. 河南科技學(xué)院 網(wǎng)絡(luò)與信息化管理中心，河南 新鄉(xiāng) 453003；2.北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院， 北京 100191；3.鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院 信息工程學(xué)院，河南 鄭州 451191)

0 引 言

在傳統(tǒng)網(wǎng)絡(luò)中，各種網(wǎng)絡(luò)設(shè)備如交換機(jī)、middlebox都是獨(dú)立工作、獨(dú)立配置的，路由器可以通過(guò)相互協(xié)作運(yùn)行分布式路由協(xié)議。在配置middlebox滿足相應(yīng)的服務(wù)鏈的時(shí)候，需要考慮middlebox之間的狀態(tài)依賴(lài)，這讓middlebox的配置變得異常復(fù)雜。而軟件定義網(wǎng)絡(luò)的出現(xiàn)，讓統(tǒng)一管理網(wǎng)絡(luò)狀態(tài)成為了可能。用SDN管理middlebox的代表性工作有Simple-fying和FlowTags[1-3]。

Simple-fying預(yù)留了IP包頭的某些域，用它來(lái)標(biāo)記網(wǎng)絡(luò)包的狀態(tài)，當(dāng)網(wǎng)絡(luò)包被middlebox處理之后，這個(gè)狀態(tài)會(huì)修改。在査詢流表的過(guò)程中，這個(gè)域作為一個(gè)匹配域，來(lái)確定網(wǎng)絡(luò)包的轉(zhuǎn)發(fā)路徑。Simple-fying充分體現(xiàn)了軟件定義網(wǎng)絡(luò)的優(yōu)勢(shì)，統(tǒng)一管理整個(gè)網(wǎng)絡(luò)的狀態(tài)。FlowTags也采取了相似的思路。但是FlowTags進(jìn)一步擴(kuò)展了openflow協(xié)議，讓控制器可以直接控制middlebox，配置參數(shù)，讀取狀態(tài)，讓middlebox的管理和switch的管理統(tǒng)一了起來(lái)。另一方面，它將復(fù)雜的middlebox的配置命令封裝在具體的南向協(xié)議里，這樣可以避免人工手動(dòng)配置出錯(cuò)的情況。

在上述工作中，研究者更多的是關(guān)心middlebox的配置工作，沒(méi)有考慮到middlebox的動(dòng)態(tài)部署和調(diào)度?，F(xiàn)有文獻(xiàn)中忽略了網(wǎng)絡(luò)性能的一個(gè)重要的指標(biāo)——傳輸延遲。在部署了middlebox的網(wǎng)絡(luò)中，數(shù)據(jù)包的延遲主要由兩部分組成，一是在鏈路上的傳輸時(shí)延，二是包在middlebox的處理時(shí)延[4,5]。如果能合理控制流在鏈路上的負(fù)載均衡，包在鏈路上的傳輸時(shí)延可以認(rèn)為是固定的，而包在middlebox里的處理時(shí)延和當(dāng)前middlebox的負(fù)載有關(guān)，如果一個(gè)middlebox需要處理的包多，那么就會(huì)引來(lái)較大的處理等待延遲。所以middlebox在進(jìn)行部署和調(diào)度的時(shí)候，有必要考慮網(wǎng)絡(luò)包的延遲性能。另外，由于企業(yè)網(wǎng)絡(luò)中部署著大量middlebox，通常要求流的延遲小于某個(gè)閾值。本文充分考慮middlebox位置和負(fù)載對(duì)流延遲的影響，對(duì)全局延遲限制下middlebox的動(dòng)態(tài)部署和流量調(diào)度問(wèn)題展開(kāi)研究，對(duì)應(yīng)的方案命名為Quokka，該方案可以有效降低資源占用并降低傳輸延遲。

1 問(wèn)題描述與建模

在企業(yè)網(wǎng)絡(luò)中，動(dòng)態(tài)地將middlebox放在合適的位置，然后把流量分配到middlebox實(shí)例上，可以減少網(wǎng)絡(luò)包的延遲[6]。具體方法為給定拓?fù)?、流量分布和延遲限制，部署最少數(shù)目的middlebox實(shí)例到合適位置并調(diào)度相應(yīng)的流量[7]。

這里用一個(gè)三元組(src,dst,>(MBa,MBb,MBc))來(lái)描述一個(gè)流，即從src到dst的流，而且它應(yīng)該被a、b、c類(lèi)型的middlebox按序處理，一系列的流組成了流量矩陣(Tlist)。

在網(wǎng)絡(luò)中，有PoolNum個(gè)資源池用來(lái)運(yùn)行middlebox實(shí)例，每個(gè)資源池最多運(yùn)行N個(gè)實(shí)例。在拓?fù)渲?，middlebox的部署方案可以用一個(gè)向量pl表示。比如，pl[i]表示第i個(gè)資源池的部署情況，定義MBSet(pl[i])為pl[i]的middlebox實(shí)例集合，定義MBNum(pl[i])為pl[i]中middlebox的數(shù)目，也就是|MBSet(pl[i])|。

根據(jù)具體的部署方案，為流量矩陣的每條流選取具體的middlebox實(shí)例，將這些實(shí)例組成的路徑命名最小延遲路徑(minimum delay path，MDP)。分別用links(f)和mbs(f)表示這條路徑中的鏈路集合和middlebox實(shí)例集合。用FNum(m)表示某個(gè)middleboxm所處理的流的數(shù)目，用Delay(FNum(m))表示middleboxm的處理延遲，鏈路l的延遲為Delay(l)。假定η是可接受的最大傳輸延遲，問(wèn)題可以描述為

(1)

式(1)中的概率函數(shù)P表征一個(gè)特定流的總延遲。對(duì)于一個(gè)固定的MDP，鏈路的總延遲Slk為常數(shù)。Smb表示一個(gè)服務(wù)鏈中所有middlebox的總延遲。Delay(FNum(m))表示m的處理延遲，是一個(gè)和流量數(shù)目相關(guān)的隨機(jī)數(shù)。為了計(jì)算P，需要必須計(jì)算所有middlebox延遲的聯(lián)合分布，這會(huì)帶來(lái)不必要的巨大計(jì)算開(kāi)銷(xiāo)。

由FNum(m)≤Maxm?Em(FNum(m))≤Em(Maxm)可得

因此，優(yōu)化問(wèn)題可以表達(dá)成

(2)

這是一個(gè)組合優(yōu)化問(wèn)題。為了分析這個(gè)問(wèn)題的復(fù)雜度，考慮MDP計(jì)算的一個(gè)子問(wèn)題：給定middlebox的部署方案，為一個(gè)O(n)的流尋找合適的MDP。如果最大延遲限制γ是多項(xiàng)式級(jí)別大(polynomially large)，這個(gè)子問(wèn)題是一個(gè)NP-Hard問(wèn)題。因此，計(jì)算MDP是一個(gè)NP-Hard問(wèn)題。進(jìn)而，整個(gè)優(yōu)化問(wèn)題是一個(gè)NP-Hard問(wèn)題。

2 算法設(shè)計(jì)

2.1 算法框架

本節(jié)提出相應(yīng)的次優(yōu)算法來(lái)解決前面的優(yōu)化問(wèn)題。算法框架MBSchedule(G,Tlist,γ)如算法1所示。其中，G和Tlist對(duì)分別表示網(wǎng)絡(luò)拓?fù)浜土髁烤仃?。γ是網(wǎng)絡(luò)傳輸延遲的上界?？紤]到問(wèn)題的復(fù)雜性，把問(wèn)題分成兩個(gè)子問(wèn)題：一是為middlebox找到合適的部署位置；二是調(diào)度流量到middlebox實(shí)例(即為每條流計(jì)算MDP)。

給定拓?fù)銰，流量矩陣Tlist，傳輸延遲上界γ，算法MBSchedule先初始化每種類(lèi)型的middlebox數(shù)目。接著，第一階段算法MBPosition根據(jù)middlebox數(shù)目生成合適的middlebox部署位置。如果計(jì)算不出合適的部署方案，發(fā)出錯(cuò)誤信息，這表明γ太小，在當(dāng)前的拓?fù)浜土髁肯聸](méi)有合適的方案。如果得到某個(gè)部署方案，可以進(jìn)行算法第二階段MDPSoution。這個(gè)算法用來(lái)計(jì)算每個(gè)流的MDP。如果計(jì)算結(jié)果不合適，算法會(huì)調(diào)整middlebox數(shù)目，因?yàn)楫?dāng)前數(shù)目下部署方案不合適。

對(duì)應(yīng)于算法的兩個(gè)階段，分別進(jìn)行具體的實(shí)現(xiàn)。MBPosition用k階段投票算法解決(K-Level Voting)，MDPSoution用掩碼維特比算法解決(Masked-Viterbi)。

算法1：MBSchedule(G,Tlist,γ)

(1)MBNumList.init()

(2)whileturedo

(3)pl=MBPosition(G，Tlist，MBNumlist)

(4)ifpl!>=Nonethen

(5)solution=MDPSolution(G,Tlist,pl,γ)

(6)ifsolutionacceptedthen

(7)returnsolution

(8)else

(9)MBNumlist.adjust(solution)

(10)endif

(11)else

(12)returnERROR:γis too small

(13)endif

(14)endwhile

2.2 k輪投票算法

在k輪投票算法中，模擬k輪投票來(lái)選取合適的middlebox部署候選資源池。在投票的過(guò)程中，為每一個(gè)<資源池，middlebox類(lèi)型>維護(hù)著一個(gè)分?jǐn)?shù)表。在每一輪當(dāng)中，所有的流根據(jù)自身服務(wù)鏈和middlebox位置，為每一個(gè)<資源池，middlebox類(lèi)型>投票。在每一輪最后，會(huì)根據(jù)得分選取臨時(shí)的middlebox部署候選位置。投票過(guò)程是遞增的，得分是上一輪最終得分和本輪得分之和。

在算法2中，G.plist表示資源池列表。首先初始化分?jǐn)?shù)表和scores候選資源池candidate，然后，進(jìn)行k輪投票(socres.vote())和選取(candidate.select())。通過(guò)投票，不斷優(yōu)化candidate。

假設(shè)所有流中，最長(zhǎng)的服務(wù)鏈長(zhǎng)度是k，也就是最多包含k個(gè)middlebox實(shí)例。?f∈Tlist，定義f.chain是流f的服務(wù)鏈。在第一輪投票時(shí)，所有流為服務(wù)鏈中第一個(gè)middlebox的類(lèi)型MBx(MBx=f,chain[1])投票。這個(gè)時(shí)候流的投票位置是流的起點(diǎn)f.>src(加入到loclist,和也就是投票起點(diǎn)的列表)。對(duì)于?p∈G.>plist，流f為打一個(gè)分?jǐn)?shù)1/ln(dist(f.src, >p))。經(jīng)過(guò)這輪打分投票，每個(gè)對(duì)應(yīng)的分?jǐn)?shù)是所有流對(duì)他們打分之和。然后根據(jù)這個(gè)分?jǐn)?shù)表，為MBx選取mx個(gè)middlebox候選資源池，mx是由MBNumlist決定的。

算法2：KLevelVoting(G，Tlist，MBNumlist)

(1) initscoresandcandidate

(2)foriin 1∶kdo

(3)forallfinTlistdo

(4)forallpinG.>plistdo

(5)mb=f.>chain[i]

(6)ifkis 1then

(7) setloclistto {f.src}

(8)else

(9) setloclisttocandidate[f.chain[k-1]]

(10)endif

(11)forallst∈loclistdo

(12)scores.vote(st,p,>1/ln(dis(st,p)))

(13)endfor

(14)endfor

(15)endfor

(16)candidate.select(scores)

(17)endfor

假設(shè)MBx類(lèi)型的middlebox暫時(shí)放置在這些位置。在第一輪投票中，對(duì)于某個(gè)流f來(lái)說(shuō)，loclist變成了第一輪投票當(dāng)中的候選位置(也就是f.>chain中第一個(gè)middlebox類(lèi)型的候選位置)。這是因?yàn)?，被第一種類(lèi)型middlebox處理之后，流在middlebox的位置(也就是loclist)，準(zhǔn)備發(fā)往下一種類(lèi)型的middlebox去處理。然后f在此位置對(duì)服務(wù)鏈中下一種類(lèi)型的middlebox類(lèi)型投票(MBx>對(duì))。得分是原來(lái)分?jǐn)?shù)和新得分的和。投票結(jié)束，middlebox的候選位置需要根據(jù)新的分?jǐn)?shù)重新選取。接下來(lái)k-2輪投票過(guò)程都和第二輪類(lèi)似。最后，經(jīng)過(guò)k輪投票，得到全部的最終得分。對(duì)于某種類(lèi)型的middleboxMBx，選取得分最高的相應(yīng)數(shù)目的資源池位置，在選取的過(guò)程中，也需要額外考慮資源池的限制(處理能力，每個(gè)資源池只能運(yùn)行有限數(shù)目的middlebox實(shí)例)。

KLevelVoting算法是一種貪心算法，在每一輪的投票過(guò)程中，根據(jù)之前的得分和上一輪候選資源池的位置，算法為服務(wù)鏈中下一種middlebox類(lèi)型投票。投票位置距離資源池距離dist(f.>src,>p)越近，資源池p得分越高。最后，KLevelVoting為各種類(lèi)型的middlebox貪心地找到合適的部署位置。

2.3 掩碼維特比算法

算法MaskedViterbi被用來(lái)計(jì)算MDP，它分為兩個(gè)階段：第一階段，不考慮處理延遲，計(jì)算流的最小可能延遲，存在MinPosslist中，然后根據(jù)MinPosslist將流進(jìn)行降序排序；在第二階段，按照第一輪的排序順序，用一個(gè)改進(jìn)的Viterbi算法，逐個(gè)計(jì)算每個(gè)流的MDP。

MaskedViterbi算法如算法3所示：

算法3：MaskedViterbi(G,Tlist,pl,γ)

(1)forfinTlistdo

(2)mindelay=Viterbi(G,>pl)

(3)addmindelaytoMinPosslist

(4)endfor

(5)rankTlistbyMinPosslist

(6)forfinTlistdo

Stage 2:>line (6)-(x)

(7)formbTypeinf.>chaindo

(8) intimaskbased on flow numbers

(9)mb=ImpViterbi(G,>pl,>mbType,mask)

(10)whilembisNonedo

(11)mask.pop()

(12)mb=ImpViterbi(G,>pl,>mbType,mask)

(13)endwhile

(14)mad.append(mb)

(15)endfor

(16)ifmdpis acceptedthen

(17) addmdpintosolution

(18)else

(19)returnsolutionwith a feetback

(20)endif

(21)endfor

(22)returnsolution

在第一階段，假設(shè)所有的middlebox可以處理無(wú)限大的流量，處理延遲是固定的，計(jì)算每條流的最小可能處理延遲。這其實(shí)是個(gè)多階段最短路徑問(wèn)題(multi-stage shortest path problem)，可以用維特比算法(ViterbiAlgorithm)解決。在這個(gè)問(wèn)題中，每種類(lèi)型的middlebox實(shí)例組成一個(gè)階段(stage)，服務(wù)鏈中所有類(lèi)型的middlebox之間組成多個(gè)階段。不考慮流量對(duì)middlebox處理的影響，計(jì)算MDP就是找一條最短路徑，這條路徑分別按序經(jīng)過(guò)每一個(gè)階段。維特比算法用動(dòng)態(tài)規(guī)劃的思路解決了這個(gè)問(wèn)題。計(jì)算完畢后，按照最小可能延遲，降序排列，將高延遲的排在前面。

這個(gè)重新排序過(guò)程十分重要。如果一個(gè)流有較小的最小可能延遲，那么它有很大概率有許多條延遲不大的候選路徑。這里把高延遲的流放在前面，讓它們?cè)谶x擇的過(guò)程中有更多的選擇。隨著流的逐條計(jì)算，有些middlebox可能會(huì)過(guò)載(overloaded)，導(dǎo)致后面的流無(wú)法選擇相應(yīng)的middlebox實(shí)例。

在第二個(gè)階段中，考慮流的延遲限制γ，按照新的順序，重新計(jì)算流的MDP。在計(jì)算過(guò)程中，應(yīng)用了一個(gè)過(guò)載middlebox的掩碼集(mask)在為流選擇路徑的時(shí)候，算法會(huì)跳過(guò)掩碼集中的middlebox實(shí)例。如果一條流在掩碼集的限制之下，無(wú)法找到合適的路徑，就會(huì)從掩碼集當(dāng)中彈出一個(gè)middlebox實(shí)例。這個(gè)實(shí)例是掩碼集中負(fù)載最小的實(shí)例。彈出之后，用新的掩碼集重新計(jì)算MDP。這個(gè)重新計(jì)算的過(guò)程可能會(huì)重復(fù)多次，直到算出相應(yīng)的MDP。如果不能為所有的流找到滿足延遲限制條件的MDP，算法將反饋，調(diào)整middlebox數(shù)目列表MBNumList。

正如式(2)所示，通過(guò)限制每個(gè)middlebox的流數(shù)目來(lái)控制處理延遲。對(duì)于middleboxm，這個(gè)閾值是Maxm。當(dāng)m的流的數(shù)目超過(guò)0.9Maxm(把剩余的10%流量留給彈出的情況)時(shí)，認(rèn)為m過(guò)載了，把它加入到mask。

這個(gè)算法可以很容易改成在線算法，因?yàn)橥镀边^(guò)程和MDP計(jì)算過(guò)程都是逐條流計(jì)算的[9]。為了防止頻繁變化的流表影響網(wǎng)絡(luò)的性能，設(shè)置一個(gè)更新周期(通常是數(shù)十分鐘)。在此期間已部署的middlebox的位置不變，新來(lái)的流同樣可以參與到middlebox位置的投票當(dāng)中。

3 實(shí)驗(yàn)驗(yàn)證

本節(jié)通過(guò)充分的實(shí)驗(yàn)驗(yàn)證對(duì)算法進(jìn)行驗(yàn)證?；谄髽I(yè)網(wǎng)絡(luò)拓?fù)浜瓦\(yùn)營(yíng)商網(wǎng)絡(luò)拓?fù)?，在?shí)驗(yàn)中著重觀察和分析網(wǎng)絡(luò)包的延遲以及資源的利用效率。

3.1 實(shí)驗(yàn)設(shè)置

調(diào)度算法應(yīng)該在SDN控制器里作為一個(gè)應(yīng)用實(shí)現(xiàn)。為了在大規(guī)模和復(fù)雜網(wǎng)絡(luò)中驗(yàn)證算法，實(shí)驗(yàn)中做了一個(gè)自用的仿真器。控制器運(yùn)行在一個(gè)Intel服務(wù)器上，CPU為Xeon 2.6 GHz dual-core，內(nèi)存4 G，操作系統(tǒng)為L(zhǎng)inux 3.10.0。

為了驗(yàn)證算法在各種拓?fù)渖系挠行?，采用了FatTree、中國(guó)教育和科研網(wǎng)(CERNET)、克羅地亞教育和科研網(wǎng)(CARNET)以及Rocketfuel項(xiàng)目中的AS2914作為實(shí)驗(yàn)拓?fù)?。拓?fù)涞脑敿?xì)信息見(jiàn)表1。

表1 實(shí)驗(yàn)用拓?fù)鋵傩?/p>

根據(jù)企業(yè)網(wǎng)絡(luò)的真實(shí)流量行為生成具體流。實(shí)驗(yàn)中，56%的流量是內(nèi)外交互的流量，其余都是內(nèi)部流量。共有4種類(lèi)型的流量，見(jiàn)表2。其中Long和Short是表征流的持續(xù)性(duration)，而Small和Large表征流的數(shù)據(jù)量大小，同時(shí)存在2000個(gè)流。

表2 企業(yè)網(wǎng)流量特征

根據(jù)文獻(xiàn)中的統(tǒng)計(jì)結(jié)果，生成了各種應(yīng)用的trace數(shù)據(jù)，例如ssh、NFS和Dantz，然后根據(jù)校園網(wǎng)絡(luò)的策略為各種類(lèi)型的middlebox設(shè)置服務(wù)鏈。為了體現(xiàn)Quokka算法的優(yōu)勢(shì)，將兩種傳統(tǒng)的配置方式作對(duì)比：

(1)固定放置并且靜態(tài)配置(Fixed-Fixed)：提前放置一定數(shù)目的middlebox在固定的資源池，當(dāng)一個(gè)流產(chǎn)生時(shí)，F(xiàn)ixed-Fixed方案將它送到最近的middlebox實(shí)例。這種方案類(lèi)似于傳統(tǒng)的物理middlebox管理方案。

(2)固定放置并且負(fù)載均衡(Fixed-LB)：這種方案放置固定數(shù)目的middlebox在資源池，然后將流量平均的均衡到各個(gè)middlebox實(shí)例，和Simple-fying中的均衡方案類(lèi)似。

3.2 結(jié)果和分析

Quokka是個(gè)可擴(kuò)展的調(diào)度算法，它可以結(jié)合網(wǎng)絡(luò)處理需求(流量)的變化，根據(jù)流量的服務(wù)鏈和資源的限制，動(dòng)態(tài)地增加和刪除middlebox實(shí)例的數(shù)目。圖1顯示了隨著尺KLeveLVoting-MaskedViterbi迭代，Quokka的延遲分布。剛開(kāi)始，系統(tǒng)給網(wǎng)絡(luò)分配了比較少的middlebox實(shí)例，導(dǎo)致網(wǎng)絡(luò)的延遲比較大。然后在每一輪的迭代過(guò)程中，Quokka自動(dòng)增加各種middlebox實(shí)例數(shù)目，運(yùn)行投票算法部署新的middlebox實(shí)例，然后通過(guò)掩碼維特比算法調(diào)度流量。可以發(fā)現(xiàn)，每一輪迭代，網(wǎng)絡(luò)包的延遲都相應(yīng)減少，如圖1所示。

圖1 3次迭代中Quokka延遲分布

這個(gè)實(shí)驗(yàn)表明，Quokka可以動(dòng)態(tài)地根據(jù)處理負(fù)載的變化，動(dòng)態(tài)調(diào)整middlebox 的數(shù)目，進(jìn)而部署middlebox實(shí)例在合適的位置，然后根據(jù)部署方案調(diào)度流量。middlebox數(shù)目的變化可以根據(jù)流量需求進(jìn)行粗略的估計(jì)，然后根據(jù)算法運(yùn)行結(jié)果進(jìn)行調(diào)整。在實(shí)驗(yàn)當(dāng)中，迭代過(guò)程收斂速度非?？欤诖蟛糠滞?fù)洚?dāng)中，3次迭代就達(dá)到了很好的結(jié)果，這讓Quokka非常計(jì)算友好(computing-friendly)。

給定固定的middlebox數(shù)目，分別在控制器里運(yùn)行Fixed-Fixed、Fixed-LB和Quokka算法。如圖2所示，Quokka比其它兩種算法具有更小的延遲特性。在AS2914中，F(xiàn)ixed-LB比Fixed-Fixed的性能還要差。這是因?yàn)锳S2914包含很多高延遲鏈路。在這樣的拓?fù)渲校溌费舆t比處理延遲影響更大。傳統(tǒng)的負(fù)載均衡方案，可能會(huì)把網(wǎng)絡(luò)調(diào)度到比較遠(yuǎn)的middlebox實(shí)例去處理，導(dǎo)致總體延遲增大。這是傳統(tǒng)的負(fù)載均衡方案的典型問(wèn)題，在模型分析中已經(jīng)分析過(guò)了。Quokka可以避免這種問(wèn)題，在4個(gè)拓?fù)渲?，都取得了很好的性能?/p>

圖2 3種算法延遲分布

從這個(gè)實(shí)驗(yàn)可以看出，Quokka比最近處理方案(Fixed-Fixed)和負(fù)載均衡方案(Fixed-LB)都要有優(yōu)勢(shì)。Fixed-Fixed選擇最近的middlebox處理，會(huì)導(dǎo)致一部分middlebox過(guò)載。過(guò)載的middlebox處理延遲會(huì)增大，導(dǎo)致經(jīng)過(guò)它的流增大。盡管Fixed-LB通過(guò)負(fù)載均衡方案解決了這個(gè)問(wèn)題，但是它會(huì)把一些流發(fā)到比較遠(yuǎn)的middlebox實(shí)例去處理，引入了而外的延遲。在前3種拓?fù)渲校現(xiàn)ixed-LB都比Fixed-Fixed有優(yōu)勢(shì)，但是在復(fù)雜的跨國(guó)拓?fù)淙鏏S2914中，F(xiàn)ixed-LB的性能反而比Fixed-Fixed差。

接下來(lái)，計(jì)算Quokka相對(duì)其它兩種方案延遲減少的比例。這里計(jì)算了實(shí)驗(yàn)中所有網(wǎng)絡(luò)流的平均延遲，接著計(jì)算了Quokka相對(duì)于Fixed-Fixed和Fixed-LB減少的具體比例。結(jié)果見(jiàn)表3。從實(shí)驗(yàn)中可以看出，Quokka相較于其它兩種方案，平均減少了20%的延遲。

表3 Quokka與相應(yīng)算法相比延遲減少比例/%

在前3個(gè)拓?fù)渲?，F(xiàn)ixed-Fixed性能非常差，比負(fù)載均衡方案和Quokka都至少有20%的倒退。這是因?yàn)椋罱x擇原則，會(huì)讓很多middlebox過(guò)載，導(dǎo)致網(wǎng)絡(luò)性能降低。然而，雖然Fixed-LB方案在前3個(gè)拓?fù)渲斜憩F(xiàn)不錯(cuò)，Quokka相較于它，仍然有4%-8%的優(yōu)勢(shì)。在AS2914這張拓?fù)渲?，F(xiàn)ixed-Fixed和Fixed-LB的性能似乎反轉(zhuǎn)了過(guò)來(lái)。正如前面介紹的那樣，AS2914有很多長(zhǎng)延遲鏈路，導(dǎo)致負(fù)載均衡方案可能會(huì)帶來(lái)新的延遲。在這個(gè)拓?fù)渲?，Quokka的優(yōu)勢(shì)更加明顯，比負(fù)載均衡方案有高達(dá)43%的優(yōu)勢(shì)。

給定一個(gè)固定的延遲要求，通過(guò)實(shí)驗(yàn)，測(cè)試每種算法需要多少個(gè)middlebox實(shí)例，才能滿足這個(gè)延遲要求。對(duì)于每個(gè)算法和每個(gè)拓?fù)溥M(jìn)行5次實(shí)驗(yàn)，如果至少有4次滿足延遲要求，認(rèn)為延遲被滿足。否則，認(rèn)為在當(dāng)前拓?fù)浜唾Y源下，延遲不能被滿足。實(shí)際上，F(xiàn)ixed-Fixed不能在FatTree拓?fù)渖蠞M足120 ms的限制，表4中用*號(hào)來(lái)表示。其它的實(shí)驗(yàn)方案下，都是5次全部滿足。大多數(shù)情況下，Quokka相比其它兩種方案，減少了30%-50%的資源使用率。

表4 延遲保證所需最少資源

給定固定數(shù)目的middlebox，測(cè)試每種算法能夠提供的最小的延遲保證。在各種拓?fù)渖线\(yùn)行3種算法，發(fā)現(xiàn)Quokka總是提供較小的延遲保證。如圖3所示，在前3個(gè)拓?fù)洚?dāng)中，Quokka相比Fixed-Fixed有低于40%的延遲保證，而比Fixed-LB有輕微的優(yōu)勢(shì)。但是在AS2914中，Quokka相對(duì)于其它兩種方案延遲保證小得多。

圖3 最小延遲保證比較

如表2所示，Long-Large類(lèi)型的流，占了97.8%的數(shù)據(jù)量。所以可以為在線算法設(shè)置一個(gè)較大的更新間隔，這不會(huì)對(duì)算法的最優(yōu)性產(chǎn)生過(guò)大的影響。實(shí)際上，實(shí)驗(yàn)結(jié)果表明，在線算法和靜態(tài)版的算法取得的性能十分接近。

3.3 算法復(fù)雜度分析

正如前面提到的那樣，在算法中KLeveLVoting-MaskedViterbi循環(huán)通常只迭代3輪就終止了。在KLeveLVoting算法中，全局大循環(huán)次數(shù)是|k|*|Tlist|*|G.plist|。k是最長(zhǎng)服務(wù)鏈長(zhǎng)度，|G.plist|是資源池總數(shù)。實(shí)驗(yàn)中k小于10，|G.plist|最多是200左右。所以算法的循環(huán)數(shù)目和流的數(shù)目對(duì)成正比。

在KLeveLVoting的每一輪循環(huán)中，為了計(jì)算dist，需要計(jì)算所有交換機(jī)對(duì)之間的最短路徑。在實(shí)現(xiàn)中采用了Floyd-Warshall算法。這個(gè)算法的復(fù)雜度是O(|V|)3，其中|V|是網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目。實(shí)驗(yàn)過(guò)程中，這部分所用的時(shí)間是最長(zhǎng)的。由于在算法計(jì)算過(guò)程中拓?fù)涫遣蛔兊?，可以提前離線計(jì)算交換機(jī)對(duì)之間的最短路徑。即使資源池發(fā)生故障，也不影響交換機(jī)之間的路徑。這樣，一個(gè)KLeve-LVoting循環(huán)可以在常數(shù)時(shí)間內(nèi)完成。

在MaskedViterbi算法當(dāng)中，全局大循環(huán)的數(shù)目同樣是和流數(shù)目成正比的。分析方法和KLeveLVoting類(lèi)似，|f.chain|是常數(shù)大小，|mask|是資源池的一個(gè)子集，也可以認(rèn)為是個(gè)小常數(shù)。在每個(gè)大循環(huán)中，維特比算法執(zhí)行常數(shù)次。采用維特比算法解決一個(gè)多階段最短路徑問(wèn)題。然而，實(shí)驗(yàn)中每個(gè)階段的點(diǎn)的數(shù)目是小常數(shù)，總階段數(shù)也是小常數(shù)。所以維特比算法的復(fù)雜度也是常數(shù)時(shí)間。這樣每個(gè)MaskedViterbi算法循環(huán)是常數(shù)時(shí)間復(fù)雜度。

這樣，整個(gè)算法的時(shí)間復(fù)雜度就是和流的數(shù)目成正比。實(shí)驗(yàn)結(jié)果表明，Quokka對(duì)計(jì)算資源的消耗非常小，代碼沒(méi)有明顯增加控制器的計(jì)算消耗。在動(dòng)態(tài)版本的算法中，由于更新間隔比較大(通常是數(shù)十分鐘)，資源消耗的比例更加低了。

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

本文對(duì)全局延遲限制下middlebox部署和調(diào)度問(wèn)題進(jìn)行建模分析。首先將問(wèn)題形式化成一個(gè)優(yōu)化問(wèn)題，然后分析和證明了問(wèn)題的復(fù)雜度。由于該問(wèn)題是個(gè)NP-Hard問(wèn)題，提出了相應(yīng)的次優(yōu)化算法。將問(wèn)題拆分為部署問(wèn)題和流量調(diào)度問(wèn)題，通過(guò)逐輪迭代的方式逐步求出整個(gè)優(yōu)化問(wèn)題的解。對(duì)于兩個(gè)子問(wèn)題，分別提出了KLeveLVoting和MaskedViterbi算法，分別用貪心的方式解決了部署和調(diào)度問(wèn)題。為了在大規(guī)模的網(wǎng)絡(luò)中，驗(yàn)證我們算法的有效性，在4種拓?fù)渲羞M(jìn)行了算法仿真，拓?fù)浼劝?jīng)典的企業(yè)網(wǎng)絡(luò)，又包含復(fù)雜的運(yùn)營(yíng)商網(wǎng)絡(luò)。為了比對(duì)算法效果，實(shí)現(xiàn)了傳統(tǒng)方案的兩種配置方式：靜態(tài)配置 (Fixed-Fixed)和簡(jiǎn)單的負(fù)載均衡(Fixed-LB)。在各種拓?fù)渖蠈?shí)現(xiàn)了Quokka、Fixed-Fixed、Fixed-LB，通過(guò)比較在指定延遲下對(duì)資源的消耗，發(fā)現(xiàn)Quokka少使用了30%-50%左右的資源。給定固定的資源，測(cè)試網(wǎng)絡(luò)包的延遲分布，發(fā)現(xiàn)Quokka可以減少平均20%的延遲。