考慮全局延遲的中間件調度問題

2021-08-23 04:10:44李長江周湘貞肖文顯王俊閣

計算機工程與設計 2021年8期

關鍵詞：資源

李長江，周湘貞，肖文顯，王俊閣

(1. 河南科技學院網絡與信息化管理中心，河南新鄉 453003；2.北京航空航天大學計算機學院，北京 100191；3.鄭州升達經貿管理學院信息工程學院，河南鄭州 451191)

0 引言

在傳統網絡中，各種網絡設備如交換機、middlebox都是獨立工作、獨立配置的，路由器可以通過相互協作運行分布式路由協議。在配置middlebox滿足相應的服務鏈的時候，需要考慮middlebox之間的狀態依賴，這讓middlebox的配置變得異常復雜。而軟件定義網絡的出現，讓統一管理網絡狀態成為了可能。用SDN管理middlebox的代表性工作有Simple-fying和FlowTags[1-3]。

Simple-fying預留了IP包頭的某些域，用它來標記網絡包的狀態，當網絡包被middlebox處理之后，這個狀態會修改。在査詢流表的過程中，這個域作為一個匹配域，來確定網絡包的轉發路徑。Simple-fying充分體現了軟件定義網絡的優勢，統一管理整個網絡的狀態。FlowTags也采取了相似的思路。但是FlowTags進一步擴展了openflow協議，讓控制器可以直接控制middlebox，配置參數，讀取狀態，讓middlebox的管理和switch的管理統一了起來。另一方面，它將復雜的middlebox的配置命令封裝在具體的南向協議里，這樣可以避免人工手動配置出錯的情況。

在上述工作中，研究者更多的是關心middlebox的配置工作，沒有考慮到middlebox的動態部署和調度。現有文獻中忽略了網絡性能的一個重要的指標——傳輸延遲。在部署了middlebox的網絡中，數據包的延遲主要由兩部分組成，一是在鏈路上的傳輸時延，二是包在middlebox的處理時延[4,5]。如果能合理控制流在鏈路上的負載均衡，包在鏈路上的傳輸時延可以認為是固定的，而包在middlebox里的處理時延和當前middlebox的負載有關，如果一個middlebox需要處理的包多，那么就會引來較大的處理等待延遲。所以middlebox在進行部署和調度的時候，有必要考慮網絡包的延遲性能。另外，由于企業網絡中部署著大量middlebox，通常要求流的延遲小于某個閾值。本文充分考慮middlebox位置和負載對流延遲的影響，對全局延遲限制下middlebox的動態部署和流量調度問題展開研究，對應的方案命名為Quokka，該方案可以有效降低資源占用并降低傳輸延遲。

1 問題描述與建模

在企業網絡中，動態地將middlebox放在合適的位置，然后把流量分配到middlebox實例上，可以減少網絡包的延遲[6]。具體方法為給定拓撲、流量分布和延遲限制，部署最少數目的middlebox實例到合適位置并調度相應的流量[7]。

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

在網絡中，有PoolNum個資源池用來運行middlebox實例，每個資源池最多運行N個實例。在拓撲中，middlebox的部署方案可以用一個向量pl表示。比如，pl[i]表示第i個資源池的部署情況，定義MBSet(pl[i])為pl[i]的middlebox實例集合，定義MBNum(pl[i])為pl[i]中middlebox的數目，也就是|MBSet(pl[i])|。

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

(1)

式(1)中的概率函數P表征一個特定流的總延遲。對于一個固定的MDP，鏈路的總延遲Slk為常數。Smb表示一個服務鏈中所有middlebox的總延遲。Delay(FNum(m))表示m的處理延遲，是一個和流量數目相關的隨機數。為了計算P，需要必須計算所有middlebox延遲的聯合分布，這會帶來不必要的巨大計算開銷。

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

因此，優化問題可以表達成

(2)

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

2 算法設計

2.1 算法框架

本節提出相應的次優算法來解決前面的優化問題。算法框架MBSchedule(G,Tlist,γ)如算法1所示。其中，G和Tlist對分別表示網絡拓撲和流量矩陣。γ是網絡傳輸延遲的上界。考慮到問題的復雜性，把問題分成兩個子問題：一是為middlebox找到合適的部署位置；二是調度流量到middlebox實例(即為每條流計算MDP)。

給定拓撲G，流量矩陣Tlist，傳輸延遲上界γ，算法MBSchedule先初始化每種類型的middlebox數目。接著，第一階段算法MBPosition根據middlebox數目生成合適的middlebox部署位置。如果計算不出合適的部署方案，發出錯誤信息，這表明γ太小，在當前的拓撲和流量下沒有合適的方案。如果得到某個部署方案，可以進行算法第二階段MDPSoution。這個算法用來計算每個流的MDP。如果計算結果不合適，算法會調整middlebox數目，因為當前數目下部署方案不合適。

對應于算法的兩個階段，分別進行具體的實現。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輪投票來選取合適的middlebox部署候選資源池。在投票的過程中，為每一個<資源池，middlebox類型>維護著一個分數表。在每一輪當中，所有的流根據自身服務鏈和middlebox位置，為每一個<資源池，middlebox類型>投票。在每一輪最后，會根據得分選取臨時的middlebox部署候選位置。投票過程是遞增的，得分是上一輪最終得分和本輪得分之和。

在算法2中，G.plist表示資源池列表。首先初始化分數表和scores候選資源池candidate，然后，進行k輪投票(socres.vote())和選取(candidate.select())。通過投票，不斷優化candidate。

假設所有流中，最長的服務鏈長度是k，也就是最多包含k個middlebox實例。?f∈Tlist，定義f.chain是流f的服務鏈。在第一輪投票時，所有流為服務鏈中第一個middlebox的類型MBx(MBx=f,chain[1])投票。這個時候流的投票位置是流的起點f.>src(加入到loclist,和也就是投票起點的列表)。對于?p∈G.>plist，流f為打一個分數1/ln(dist(f.src, >p))。經過這輪打分投票，每個對應的分數是所有流對他們打分之和。然后根據這個分數表，為MBx選取mx個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

假設MBx類型的middlebox暫時放置在這些位置。在第一輪投票中，對于某個流f來說，loclist變成了第一輪投票當中的候選位置(也就是f.>chain中第一個middlebox類型的候選位置)。這是因為，被第一種類型middlebox處理之后，流在middlebox的位置(也就是loclist)，準備發往下一種類型的middlebox去處理。然后f在此位置對服務鏈中下一種類型的middlebox類型投票(MBx>對)。得分是原來分數和新得分的和。投票結束，middlebox的候選位置需要根據新的分數重新選取。接下來k-2輪投票過程都和第二輪類似。最后，經過k輪投票，得到全部的最終得分。對于某種類型的middleboxMBx，選取得分最高的相應數目的資源池位置，在選取的過程中，也需要額外考慮資源池的限制(處理能力，每個資源池只能運行有限數目的middlebox實例)。

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

2.3 掩碼維特比算法

算法MaskedViterbi被用來計算MDP，它分為兩個階段：第一階段，不考慮處理延遲，計算流的最小可能延遲，存在MinPosslist中，然后根據MinPosslist將流進行降序排序；在第二階段，按照第一輪的排序順序，用一個改進的Viterbi算法，逐個計算每個流的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

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

這個重新排序過程十分重要。如果一個流有較小的最小可能延遲，那么它有很大概率有許多條延遲不大的候選路徑。這里把高延遲的流放在前面，讓它們在選擇的過程中有更多的選擇。隨著流的逐條計算，有些middlebox可能會過載(overloaded)，導致后面的流無法選擇相應的middlebox實例。

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

正如式(2)所示，通過限制每個middlebox的流數目來控制處理延遲。對于middleboxm，這個閾值是Maxm。當m的流的數目超過0.9Maxm(把剩余的10%流量留給彈出的情況)時，認為m過載了，把它加入到mask。

這個算法可以很容易改成在線算法，因為投票過程和MDP計算過程都是逐條流計算的[9]。為了防止頻繁變化的流表影響網絡的性能，設置一個更新周期(通常是數十分鐘)。在此期間已部署的middlebox的位置不變，新來的流同樣可以參與到middlebox位置的投票當中。

3 實驗驗證

本節通過充分的實驗驗證對算法進行驗證。基于企業網絡拓撲和運營商網絡拓撲，在實驗中著重觀察和分析網絡包的延遲以及資源的利用效率。

3.1 實驗設置

調度算法應該在SDN控制器里作為一個應用實現。為了在大規模和復雜網絡中驗證算法，實驗中做了一個自用的仿真器。控制器運行在一個Intel服務器上，CPU為Xeon 2.6 GHz dual-core，內存4 G，操作系統為Linux 3.10.0。

為了驗證算法在各種拓撲上的有效性，采用了FatTree、中國教育和科研網(CERNET)、克羅地亞教育和科研網(CARNET)以及Rocketfuel項目中的AS2914作為實驗拓撲。拓撲的詳細信息見表1。

表1 實驗用拓撲屬性

根據企業網絡的真實流量行為生成具體流。實驗中，56%的流量是內外交互的流量，其余都是內部流量。共有4種類型的流量，見表2。其中Long和Short是表征流的持續性(duration)，而Small和Large表征流的數據量大小，同時存在2000個流。

表2 企業網流量特征

根據文獻中的統計結果，生成了各種應用的trace數據，例如ssh、NFS和Dantz，然后根據校園網絡的策略為各種類型的middlebox設置服務鏈。為了體現Quokka算法的優勢，將兩種傳統的配置方式作對比：

(1)固定放置并且靜態配置(Fixed-Fixed)：提前放置一定數目的middlebox在固定的資源池，當一個流產生時，Fixed-Fixed方案將它送到最近的middlebox實例。這種方案類似于傳統的物理middlebox管理方案。

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

3.2 結果和分析

Quokka是個可擴展的調度算法，它可以結合網絡處理需求(流量)的變化，根據流量的服務鏈和資源的限制，動態地增加和刪除middlebox實例的數目。圖1顯示了隨著尺KLeveLVoting-MaskedViterbi迭代，Quokka的延遲分布。剛開始，系統給網絡分配了比較少的middlebox實例，導致網絡的延遲比較大。然后在每一輪的迭代過程中，Quokka自動增加各種middlebox實例數目，運行投票算法部署新的middlebox實例，然后通過掩碼維特比算法調度流量。可以發現，每一輪迭代，網絡包的延遲都相應減少，如圖1所示。

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

這個實驗表明，Quokka可以動態地根據處理負載的變化，動態調整middlebox 的數目，進而部署middlebox實例在合適的位置，然后根據部署方案調度流量。middlebox數目的變化可以根據流量需求進行粗略的估計，然后根據算法運行結果進行調整。在實驗當中，迭代過程收斂速度非常快，在大部分拓撲當中，3次迭代就達到了很好的結果，這讓Quokka非常計算友好(computing-friendly)。

給定固定的middlebox數目，分別在控制器里運行Fixed-Fixed、Fixed-LB和Quokka算法。如圖2所示，Quokka比其它兩種算法具有更小的延遲特性。在AS2914中，Fixed-LB比Fixed-Fixed的性能還要差。這是因為AS2914包含很多高延遲鏈路。在這樣的拓撲中，鏈路延遲比處理延遲影響更大。傳統的負載均衡方案，可能會把網絡調度到比較遠的middlebox實例去處理，導致總體延遲增大。這是傳統的負載均衡方案的典型問題，在模型分析中已經分析過了。Quokka可以避免這種問題，在4個拓撲中，都取得了很好的性能。

圖2 3種算法延遲分布

從這個實驗可以看出，Quokka比最近處理方案(Fixed-Fixed)和負載均衡方案(Fixed-LB)都要有優勢。Fixed-Fixed選擇最近的middlebox處理，會導致一部分middlebox過載。過載的middlebox處理延遲會增大，導致經過它的流增大。盡管Fixed-LB通過負載均衡方案解決了這個問題，但是它會把一些流發到比較遠的middlebox實例去處理，引入了而外的延遲。在前3種拓撲中，Fixed-LB都比Fixed-Fixed有優勢，但是在復雜的跨國拓撲如AS2914中，Fixed-LB的性能反而比Fixed-Fixed差。

接下來，計算Quokka相對其它兩種方案延遲減少的比例。這里計算了實驗中所有網絡流的平均延遲，接著計算了Quokka相對于Fixed-Fixed和Fixed-LB減少的具體比例。結果見表3。從實驗中可以看出，Quokka相較于其它兩種方案，平均減少了20%的延遲。

表3 Quokka與相應算法相比延遲減少比例/%

在前3個拓撲中，Fixed-Fixed性能非常差，比負載均衡方案和Quokka都至少有20%的倒退。這是因為，最近選擇原則，會讓很多middlebox過載，導致網絡性能降低。然而，雖然Fixed-LB方案在前3個拓撲中表現不錯，Quokka相較于它，仍然有4%-8%的優勢。在AS2914這張拓撲中，Fixed-Fixed和Fixed-LB的性能似乎反轉了過來。正如前面介紹的那樣，AS2914有很多長延遲鏈路，導致負載均衡方案可能會帶來新的延遲。在這個拓撲中，Quokka的優勢更加明顯，比負載均衡方案有高達43%的優勢。

給定一個固定的延遲要求，通過實驗，測試每種算法需要多少個middlebox實例，才能滿足這個延遲要求。對于每個算法和每個拓撲進行5次實驗，如果至少有4次滿足延遲要求，認為延遲被滿足。否則，認為在當前拓撲和資源下，延遲不能被滿足。實際上，Fixed-Fixed不能在FatTree拓撲上滿足120 ms的限制，表4中用*號來表示。其它的實驗方案下，都是5次全部滿足。大多數情況下，Quokka相比其它兩種方案，減少了30%-50%的資源使用率。

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

給定固定數目的middlebox，測試每種算法能夠提供的最小的延遲保證。在各種拓撲上運行3種算法，發現Quokka總是提供較小的延遲保證。如圖3所示，在前3個拓撲當中，Quokka相比Fixed-Fixed有低于40%的延遲保證，而比Fixed-LB有輕微的優勢。但是在AS2914中，Quokka相對于其它兩種方案延遲保證小得多。

圖3 最小延遲保證比較

如表2所示，Long-Large類型的流，占了97.8%的數據量。所以可以為在線算法設置一個較大的更新間隔，這不會對算法的最優性產生過大的影響。實際上，實驗結果表明，在線算法和靜態版的算法取得的性能十分接近。

3.3 算法復雜度分析

在KLeveLVoting的每一輪循環中，為了計算dist，需要計算所有交換機對之間的最短路徑。在實現中采用了Floyd-Warshall算法。這個算法的復雜度是O(|V|)3，其中|V|是網絡中節點的數目。實驗過程中，這部分所用的時間是最長的。由于在算法計算過程中拓撲是不變的，可以提前離線計算交換機對之間的最短路徑。即使資源池發生故障，也不影響交換機之間的路徑。這樣，一個KLeve-LVoting循環可以在常數時間內完成。

在MaskedViterbi算法當中，全局大循環的數目同樣是和流數目成正比的。分析方法和KLeveLVoting類似，|f.chain|是常數大小，|mask|是資源池的一個子集，也可以認為是個小常數。在每個大循環中，維特比算法執行常數次。采用維特比算法解決一個多階段最短路徑問題。然而，實驗中每個階段的點的數目是小常數，總階段數也是小常數。所以維特比算法的復雜度也是常數時間。這樣每個MaskedViterbi算法循環是常數時間復雜度。

這樣，整個算法的時間復雜度就是和流的數目成正比。實驗結果表明，Quokka對計算資源的消耗非常小，代碼沒有明顯增加控制器的計算消耗。在動態版本的算法中，由于更新間隔比較大(通常是數十分鐘)，資源消耗的比例更加低了。

4 結束語

本文對全局延遲限制下middlebox部署和調度問題進行建模分析。首先將問題形式化成一個優化問題，然后分析和證明了問題的復雜度。由于該問題是個NP-Hard問題，提出了相應的次優化算法。將問題拆分為部署問題和流量調度問題，通過逐輪迭代的方式逐步求出整個優化問題的解。對于兩個子問題，分別提出了KLeveLVoting和MaskedViterbi算法，分別用貪心的方式解決了部署和調度問題。為了在大規模的網絡中，驗證我們算法的有效性，在4種拓撲中進行了算法仿真，拓撲既包含經典的企業網絡，又包含復雜的運營商網絡。為了比對算法效果，實現了傳統方案的兩種配置方式：靜態配置 (Fixed-Fixed)和簡單的負載均衡(Fixed-LB)。在各種拓撲上實現了Quokka、Fixed-Fixed、Fixed-LB，通過比較在指定延遲下對資源的消耗，發現Quokka少使用了30%-50%左右的資源。給定固定的資源，測試網絡包的延遲分布，發現Quokka可以減少平均20%的延遲。