黃梅根，龐瑞琴，劉 亮，何大聰，汪 濤

(1.重慶郵電大學 計算機科學與技術學院，重慶 400065；2.重慶郵電大學 通信與信息工程學院，重慶 400065；3.重慶郵電大學 創(chuàng)新創(chuàng)業(yè)教育學院，重慶 400065)

0 引 言

近年來，隨著大型數(shù)據(jù)中心的快速增長以及移動終端的大面積普及，數(shù)據(jù)中心的規(guī)模越來越大，這些數(shù)據(jù)中心包含數(shù)十萬臺服務器，并承載各種不同的分布式應用程序。許多關鍵數(shù)據(jù)中心應用程序涉及許多小型事務通信，如社交網(wǎng)絡、web搜索、零售推薦等實時性業(yè)務對延遲敏感，即使是很小的延遲也會直接影響應用程序的性能，導致用戶的體驗效果降低[1-3]。因此，最小化平均完成時間(flow completion time，F(xiàn)CT)非常重要。在已有的研究中，有許多關于降低平均流完成時間的方案，這些方案大致可以分為4種，分別是流的優(yōu)先級調(diào)度、多路徑流調(diào)度機制、資源預留方案和減少交換機內(nèi)隊列長度的方案。

文獻[4]和文獻[5]基于優(yōu)先級調(diào)度。文獻[5]中pFabric通過在包上標記優(yōu)先級來最小化流完成時間，使得交換機根據(jù)流最小剩余大小對流進行調(diào)度。pFabric要求交換機根據(jù)流的大小給其分配一個獨立的優(yōu)先級隊列，但是當今的交換機無法滿足其需求，這使得pFabric的性能大大降低，進而影響FCT。文獻[5]研究的是在未知流信息的情況下采用離散的流感知服務，其根據(jù)已發(fā)送流的數(shù)量將流分成少量的優(yōu)先級隊列，跨隊列執(zhí)行優(yōu)先級，并在每個優(yōu)先級隊列中按照先進先出(first inpat first output,FIFO)的順序?qū)α鬟M行調(diào)度，但頻繁切換隊列的執(zhí)行時間就會相應增加，并且隊列內(nèi)部按照FIFO的順序執(zhí)行會阻塞后進入優(yōu)先級更高的流。

文獻[6]和文獻[7]使用多路徑流調(diào)度機制來減少FCT。文獻[6]提出了一種基于策略借助(software defined networking，SDN)的多路徑流調(diào)度(SDN based multipath flow scheduling, SMFS)機制。主要思想是通過使用周期性輪詢和動態(tài)流調(diào)度的方法來實現(xiàn)負載均衡，從而提高全網(wǎng)吞吐量。SMFS使用分段路由技術減少控制器與交換機之間的交互，但是容易導致次優(yōu)解，造成局部最優(yōu)路由。文獻[7]提出一種基于多路廣播樹的SDN多路徑路由算法。主要思想是為網(wǎng)絡拓撲中的每個節(jié)點創(chuàng)建一個以該節(jié)點為根節(jié)點的無環(huán)廣播樹，然后根據(jù)源節(jié)點和目的節(jié)點間各個路徑的可用帶寬和時延進行概率分配轉(zhuǎn)發(fā)路徑。

文獻[8]和文獻[9]分別是基于資源預留和減少交換機內(nèi)隊列長度的方案。文獻[8]認為對延遲敏感流而言，應該分配更多的網(wǎng)絡資源給他們，允許其提前完成，但是忽略了流之間的公平性。當負載較高時，一些對于延遲不敏感的流會一直處于等待分配網(wǎng)絡資源的狀態(tài)。DCTCP(data center transmission control protocol)充分利用網(wǎng)絡中的顯式擁塞通知(explicit congestion notification，ECN)，如果交換機內(nèi)的隊列長度達到閾值，那么交換機將向發(fā)送方發(fā)送ECN信號。發(fā)送方根據(jù)交換機的擁塞程度減少其擁塞窗口，從而保證交換機緩存空間的數(shù)據(jù)占據(jù)率始終低于某個閾值，這樣短數(shù)據(jù)流就無須排隊通過交換機，并同時保證長數(shù)據(jù)流的吞吐量比較高。但DCTCP要求交換機要帶有ECN功能。所有這些研究的目的都是為了減少平均FCT。

目前最理想的是pFabric與最短剩余處理時間優(yōu)先(shortest remaining time first，SRTF)調(diào)度策略。文獻[4，10]已經(jīng)表明，為了最小化FCT，對網(wǎng)絡流進行優(yōu)先級排序，然后以近似SRTF的調(diào)度策略是非常有效的。但pFabric要求給數(shù)據(jù)中心網(wǎng)絡中的每一條流都分配一個相對應的優(yōu)先級進行調(diào)度。但事實上，現(xiàn)有數(shù)據(jù)中心中可用于流調(diào)度的優(yōu)先級隊列是有限的，這一情況使得pFabric策略并不適用于實際的數(shù)據(jù)中心網(wǎng)絡環(huán)境中。

根據(jù)以上的分析，本文提出一種考慮等待時間的動態(tài)流調(diào)度策略，該策略為控制器中的一個模塊。該策略首先定義了流的優(yōu)先級劃分方法，設計了等待時間的流調(diào)度策略(flow priority scheduling algorithm considering waiting time,FPWT)算法；然后借助SDN數(shù)控分離和動態(tài)全局網(wǎng)絡視圖的優(yōu)勢，選取最優(yōu)的轉(zhuǎn)發(fā)路徑對流進行調(diào)度，使得流在盡可能短的時間內(nèi)完成，進而縮短流的平均完成時間，提高網(wǎng)絡的吞吐量。本文主要貢獻如下。

1)定義了一種考慮等待時間的優(yōu)先級劃分方法——時間比值(time ratio，TR)，即流在實際調(diào)度策略下的完成時間與在理想狀態(tài)下的完成時間的比值，依據(jù)TR來對網(wǎng)絡中的流進行優(yōu)先級的劃分；

2)設計了FPWT算法，該算法依據(jù)網(wǎng)絡中流的TR大小來確定發(fā)送流的先后順序，TR最大者優(yōu)先進行發(fā)送，之后以此類推；

3)使用Dijkstra算法，依據(jù)全局網(wǎng)絡視圖選擇K條最短路徑，然后選擇使得FP(flow priority)值最小的一條，即為該流的最終選擇路徑；

4)在Mininet實驗環(huán)境下實現(xiàn)FPWT調(diào)度策略，并與其他算法對比進行驗證。

1 FPWT策略模型

1.1 FCT最小化分析

根據(jù)參考文獻[4,10]，首先對流進行優(yōu)先級排序，然后以SRTF對流進行調(diào)度，是目前實施FCT最小化的比較有效的解決方案。

現(xiàn)有的SRTF能夠提供接近最優(yōu)的平均FCT，但SRTF往往容易忽視長流，這極有可能造成長流的饑餓。處理器共享(processor sharing，PS)策略中，長流可以和短流共享帶寬，不會出現(xiàn)餓死長流的現(xiàn)象，但會阻塞長流之后進入的短流，短流的完成時間會大大增加，進而影響平均流完成時間，這與我們追求的最小化流完成時間的目標相違背。因而我們提出FPWT算法，在不影響短流的情況下，長流在等待足夠時間后，會獲得資源進行發(fā)送，而不是一直等到短流發(fā)送完畢之后。

該示例如表1，采用SRTF調(diào)度策略如圖1，由于F2的剩余流大小比F1大，同時到達的F2處于等待狀態(tài)，F(xiàn)1先獨占鏈路資源，而F1需要2個時間才能完成；在1時刻，F(xiàn)3到達，然后與F2一樣進入等待狀態(tài)；當2時刻F1完成，盡管F2早于F3到，但F3的剩余流大小小于F2，因而不是先來的F2占用鏈路資源，而是之后到達的F3占用鏈路資源；在3時刻，F(xiàn)3仍在發(fā)送狀態(tài)，此時F4到達進入等待狀態(tài)；直到時刻4，F(xiàn)3完成，此時F2的剩余流大小小于F4，則F2進入發(fā)送狀態(tài)，直到F2完成，才會將鏈路資源分配給F4。SRTF的平均流完成時間為(2+3+7+8)/4=5。

表1 流示例

圖1 SRTF調(diào)度策略示例Fig.1 SRTF scheduling policy

雖然SRTF在平均流完成時間方面可以達到接近最優(yōu)，但是SRTF容易忽略長流，比如示例中的F2。這會對長流的完成時間造成影響，進而影響平均FCT，從而損害用戶的體驗效果。

PS策略中所有的流公平的共享帶寬。如圖2，F(xiàn)1與F2同時到達，鏈路帶寬一分為二，分配給F1與F2，在1時刻F3到達，此時，F(xiàn)1與F2并未完成，鏈路將會再次平均分配給第三者，即F3。PS的平均流完成時間為((19/3)+(53/6)+(41/6)+8)/4=15/2。

圖2 PS調(diào)度策略示例 Fig.2 PS scheduling policy

PS的優(yōu)點就在于所有的流之間實現(xiàn)公平競爭，并且不需提前知道流的任何信息。然而處理器共享的平均流完成時間遠遠不是最小值。從實例中的SRTF與PS的平均流完成時間對比就可以看出，PS的平均流完成時間大于SRTF。

總之，現(xiàn)有的流調(diào)度策略很難在取得接近最優(yōu)的流完成時間的同時又兼顧長流的饑餓問題，因此，本文提出了FPWT，以兼顧同一時刻進入的短流優(yōu)于長流進行發(fā)送，又能使得等待了一段時間的長流，在保證流完成時間的同時不至于造成長流的饑餓。

1.2 FPWT模型描述

FPWT的目的是最小化平均FCT，并且不能造成長流的饑餓。為了實現(xiàn)這一點，F(xiàn)PWT借鑒SRTF的短流優(yōu)先策略，引入長流等待時間動態(tài)調(diào)整的思路，實現(xiàn)不造成長流饑餓的效果，從而達到最小化平均FCT的目的。因此，F(xiàn)PWT設計堅持以下原則。

1)由于SRTF優(yōu)先處理剩余大小最短的流并且能夠獲得接近最優(yōu)的FCT，因此，F(xiàn)PWT針對同一時刻進入的流而言，應保證短流要在長流之前發(fā)送；

2)FPWT應保證長流在等待足夠長的時間后有機會獲得資源進行發(fā)送。FPWT使用該時刻流的實際完成時間(包括等待時間與發(fā)送時間)與理想狀態(tài)下的流完成時間(只包含發(fā)送時間)的比值對流進行優(yōu)先級設定，該比值應具有以下2個特征：①如果2個流在同一鏈路上等待的時間相同，那么越短的流的比值越大；②流的實際完成時間與理想狀態(tài)下流完成時間的比值隨著等待時間的增加而增大。

根據(jù)以上分析，給出TR的定義如下。

定義當流到達時，令Afct(f)表示在該調(diào)度策略下的實際流完成時間，用Ifct(f)表示理想狀態(tài)下的流完成時間(也即當流到達就會立即將所有的帶寬資源分配給該流，不需要等待)。則流f的TR的定義為

(1)

假設流f在獨占鏈路之前等待的時間為w(也即延遲)，則有

(2)

(2)式中：f.size表示流的大??；C表示鏈路的容量。由(2)式可以看出，假如給定2個流，當鏈路容量C和等待時間w固定時，較小的流具有較大的TR；當鏈路容量C和流尺寸大小f.size固定時，任意流的TR隨等待時間w的增加而增大。因此，確實滿足FPWT應具有的2個特性。

對于網(wǎng)絡中大量的流而言，對流的優(yōu)先級排序始終都是先根據(jù)TR的大小進行降序排列，也即是在當前所有流當中依次選出TR最大者進行優(yōu)先級的降級排序，假設當前有n條流，則某一時刻選擇流的規(guī)則如公式(3)。

(3)

FPWT根據(jù)TR來安排流的發(fā)送順序，在一組流當中TR最大者最先進行發(fā)送。表1中的實例使用FPWT調(diào)度策略如圖3，從圖3中發(fā)現(xiàn)，雖然F2的大小大于F3，但它比F3先進行發(fā)送，這是因為在2時刻，F(xiàn)1完成，此時等待的流有0時刻到達的F2和1時刻到達的F3，雖然F3的大小小于F2，但在2時刻TR(F2)=5/3，TR(F3)=3/2，TR(F2)>TR(F3)，因此F2先于F3發(fā)送。這在基于SRTF的策略中是不可能發(fā)生的。從如圖3中注意到，F(xiàn)PWT的平均流完成時間FCT為21/4，僅僅略高于SRTF。

圖3 FPWT調(diào)度策略示例Fig.3 FPWT scheduling policy

通過前面的例子說明，為了最小化最大的TR，F(xiàn)PWT會給予等待了足夠長時間的長流機會，而不是一味優(yōu)先調(diào)度等待少量時間的短流。這樣，F(xiàn)PWT可以有效地防止長流饑餓。因此，F(xiàn)PWT可以在不造成饑餓的情況下實現(xiàn)高效的流調(diào)度。

2 FPWT策略算法

每個SDN交換機維護一個流表T，流表中存放流ID(id)，源地址(S)，目的地址(D)，流大小(f.size)，流到達時間(at)，流剩余大小(RS)，流的TR(初始化1)。當有TR相同的情況出現(xiàn)時，此時還要考慮RS，RS小者優(yōu)先進行發(fā)送。算法的偽代碼如算法1。

算法1FPWT算法

輸入：流f，鏈路容量C，當前時間cT，流表TableT[fi]。

輸出：流調(diào)度順序。

1.f.aT=cT

2.TR(f)=∞

3.T.insert(f)

4.while T[fi]≠NULL do

5. maxTR=TR(f1)

6. for fi∈T[fi] do

8. if TR(fi)> maxTR then

9. maxTR=TR(fi)

10. if TR(fi)= maxTR then

11. if RS(fi)

12. maxTR=TR(fi) ?Dijkstra

13. return maxTR

在算法1中，第1—3行對新到達的流記錄其到達時間，并對TR進行初始化，然后插入流表中。第4—18行找到優(yōu)先級最高的流，每一步的解釋如下。第4—5行當流表T不為空時，假設f1的TR最大，也即f1的優(yōu)先級最高。第7行計算流表T中的每一條流的TR，然后將每條流的TR(fi)與maxTR相比較，若TR(fi)大于maxTR，則將TR(fi)賦給maxTR(8—9)。如果出現(xiàn)值TR(fi)= maxTR情況，此時就要比較RS(fi)與RS( maxTR)兩者的關系，RS更小的賦值給 maxTR(11—12)，最終找到maxTR，也即找到優(yōu)先級最高的流。之后用Dijkstra算法去找路徑，對流進行路由。

3 路徑選擇

對于網(wǎng)絡中大量的流而言，n條流的TR取決于其中一個流最大TR。當選出一條流之后，總是想讓它在盡可能短的時間內(nèi)完成，那么除了等待時間以外，其他運行時間就要盡可能的短。不同的路徑，同一條流的TR也不盡相同，依據(jù)全局網(wǎng)絡視圖，用Dijkstra算法搜索K條候選路徑，計算K條路經(jīng)的該流相應的TR，選擇使得該流TR最小的路徑即為最終路徑，也就是

FP=arg minTR(∪{fn})

(4)

最終路徑與其他候選路徑相比能讓流在更短的時間內(nèi)完成。為了更好地利用鏈路帶寬，當所選路徑仍有剩余帶寬時，則將在低優(yōu)先級隊列中選取TR最大的fi進入到高優(yōu)先級隊列中，進行發(fā)送，之后依次進行。

對于選取的任意鏈路uv發(fā)送流時要滿足以下需求得

(5)

4 仿真和結果分析

為了驗證FPWT的性能，針對所提出的考慮等待時間的動態(tài)流調(diào)度策略進行仿真，主要對其流完成時間和吞吐量進行性能測試。

4.1 仿真及拓撲結構

基于前面的研究，引入Mininet平臺(http://mininet.org/)對所提出的考慮等待時間的動態(tài)流調(diào)度策略進行仿真實驗，使用一個葉-脊拓撲結構(leaf-spine topology)，其中有8個葉(leaf)交換機到4個脊(spine)交換機。每個leaf交換機有16個10 Gbit/s的下行鏈路(即可連接128臺主機)和4個40 Gbit/s的上行鏈路連接到脊交換機，葉脊交換機之間的帶寬比例為1∶1，符合葉脊交換機之間的合理帶寬比例，不會超負荷。以上仿真環(huán)境的搭建全部在一臺物理服務器上實現(xiàn)，物理服務器使用Intel(R) Core(TM) i7-7700HQCPU@2.80 GHz處理器，內(nèi)存為8.00 GB。

4.2 仿真過程及結果分析

本文主要將FPWT與SRTF，DCTCP[4]進行比較。每次用Iperf工具根據(jù)需求隨機產(chǎn)生20 000條流進行實驗，共進行30次實驗，記錄每次實驗的相關數(shù)據(jù)。以圖4—圖9中所用數(shù)據(jù)為30次實驗所記錄數(shù)據(jù)的平均值并分析了不同流量大小(0,100) KB，(100 KB,10 MB)和(10,∞)MB的平均FCT，吞吐量(這里的吞吐量以字節(jié)為單位進行計算，計算在整個實驗期間內(nèi)輸出的總的數(shù)據(jù)量)。參考文獻[4,11]，且3種流所占比例分別為50%，30%和20%[11]。

圖4 (0,∞)平均流完成時間Fig.4 (0,∞) average FCT

圖5 平均吞吐量Fig.5 Average throughput

圖6 (0,100 KB) 平均流完成時間Fig.6 (0,100 KB) average FCT

圖7 (100 KB,10 MB)平均流完成時間Fig.7 (100 KB,10 MB) average FCT

圖8 每組實驗的平均吞吐量對比Fig.8 Each group average throughput

圖4和圖5分別顯示了不同鏈路負載情況下的SRTF，F(xiàn)PWT和DCTCP的總體平均FCT，從圖4—5中可以看出，F(xiàn)PWT的總體平均流完成時間表現(xiàn)良好，明顯優(yōu)于DCTCP，平均流完成時間縮短了約27%。雖然與SRPT相比有所增加，但FPWT的穩(wěn)定性要優(yōu)于SRTF，與SRTF相不容易出現(xiàn)饑餓的情況，并且吞吐量方面高出SRTF 17%。

針對(0,100)KB的短流，發(fā)現(xiàn)在平均流完成時間方面FPWT顯著優(yōu)于DCTCP，平均FCT減少了將近32%，如圖6。這是因為DCTCP在終端主機上使用反應速率控制，在網(wǎng)絡流量調(diào)度方面不如FPWT有效，從圖6中我們還可以直觀地觀察到在短流的情況下，F(xiàn)PWT的平均流完成時間與SRTF相差無幾，這是因為在短流和長流同時到達的情況下，F(xiàn)PWT與SRFT一樣也是優(yōu)先發(fā)送短流。

圖9 (10 MB,∞)平均流完成時間Fig.9 (10 MB,∞) average FCT

對于(100 KB,10 MB)的流，發(fā)現(xiàn)FPWT的平均流完成時間高于SRTF，但在平均流完成時間方面優(yōu)于DCTCP，F(xiàn)PWT在平均FCT相比SRTF多出了近14%，如圖7。但在吞吐量方面FPWT的表現(xiàn)優(yōu)于SRTF(尤其在(100 KB,10 MB)表現(xiàn)的更加明顯，吞吐量提高了約36%)，如圖8。這是因為SRTF總是優(yōu)先發(fā)送短流，當有新的更短的流進入鏈路時，SRTF總是停止正在發(fā)送的流來發(fā)送新進入的更短的流，在這種情況下，長流則需要一直等待比它小的短流發(fā)送完畢才有機會進行發(fā)送，則會導致嚴重的饑餓問題。而FPWT不僅僅只考慮流的大小，還要考慮流的等待時間來選擇流進行發(fā)送，當有更短的流進入隊列時，并不一定會得到立即發(fā)送的機會，因為在隊列中已經(jīng)等待一段時間的長流的TR可能會更大，因此長流仍能早于新進入的短流進行發(fā)送。

從圖9中可以觀察到，對于(10 MB,∞)的長流，F(xiàn)PWT在平均流完成時間方面顯著優(yōu)于DCTCP(尤其是在負載為0.8時，平均流完成時間縮短了近35%)。但是與SRTF相比較而言，平均流完成時間有所增加,增加了大約18%(也是在負載為0.8時，平均流完成時間增加了近約23%)，但在平均吞吐量方面的表現(xiàn)仍然優(yōu)于SRTF。隨著鏈路負載的增大，平均流完成時間也隨之增加。

5 結束語

本文提出一種考慮等待時間的動態(tài)的流調(diào)度策略，定義了流的優(yōu)先級劃分方法，設計了FPWT算法，選取最優(yōu)的轉(zhuǎn)發(fā)路徑對流進行調(diào)度，使得流在盡可能短的時間內(nèi)完成，從而縮短流的平均完成時間，提高網(wǎng)絡的吞吐量且不容易出長流饑餓的情況。最后實驗結果證明，本文提出的FPWT有效縮短了平均流完成時間，提高了網(wǎng)絡吞吐量并且不容易出現(xiàn)長流饑餓。

仿真實驗發(fā)現(xiàn)FPWT的最佳性能體現(xiàn)在(0,10)MB,但隨著鏈路負載的網(wǎng)絡流大小的增加，平均流完成時間明顯增大。未來，將進一步完善FPWT，并在其他大規(guī)模的網(wǎng)絡拓撲環(huán)境下驗證其性能。