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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

1 FPWT策略模型

1.1 FCT最小化分析

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

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

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

表1 流示例

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

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

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

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

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

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

1.2 FPWT模型描述

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

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

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

2 FPWT策略算法

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

算法1FPWT算法

輸入：流f，鏈路容量C，當(dāng)前時(shí)間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行對(duì)新到達(dá)的流記錄其到達(dá)時(shí)間，并對(duì)TR進(jìn)行初始化，然后插入流表中。第4—18行找到優(yōu)先級(jí)最高的流，每一步的解釋如下。第4—5行當(dāng)流表T不為空時(shí)，假設(shè)f1的TR最大，也即f1的優(yōu)先級(jí)最高。第7行計(jì)算流表T中的每一條流的TR，然后將每條流的TR(fi)與maxTR相比較，若TR(fi)大于maxTR，則將TR(fi)賦給maxTR(8—9)。如果出現(xiàn)值TR(fi)= maxTR情況，此時(shí)就要比較RS(fi)與RS( maxTR)兩者的關(guān)系，RS更小的賦值給 maxTR(11—12)，最終找到maxTR，也即找到優(yōu)先級(jí)最高的流。之后用Dijkstra算法去找路徑，對(duì)流進(jìn)行路由。

3 路徑選擇

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

FP=arg minTR(∪{fn})

(4)

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

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

(5)

4 仿真和結(jié)果分析

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

4.1 仿真及拓?fù)浣Y(jié)構(gòu)

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

4.2 仿真過(guò)程及結(jié)果分析

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

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

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

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

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

圖8 每組實(shí)驗(yàn)的平均吞吐量對(duì)比Fig.8 Each group average throughput

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

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

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

對(duì)于(100 KB,10 MB)的流，發(fā)現(xiàn)FPWT的平均流完成時(shí)間高于SRTF，但在平均流完成時(shí)間方面優(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。這是因?yàn)镾RTF總是優(yōu)先發(fā)送短流，當(dāng)有新的更短的流進(jìn)入鏈路時(shí)，SRTF總是停止正在發(fā)送的流來(lái)發(fā)送新進(jìn)入的更短的流，在這種情況下，長(zhǎng)流則需要一直等待比它小的短流發(fā)送完畢才有機(jī)會(huì)進(jìn)行發(fā)送，則會(huì)導(dǎo)致嚴(yán)重的饑餓問(wèn)題。而FPWT不僅僅只考慮流的大小，還要考慮流的等待時(shí)間來(lái)選擇流進(jìn)行發(fā)送，當(dāng)有更短的流進(jìn)入隊(duì)列時(shí)，并不一定會(huì)得到立即發(fā)送的機(jī)會(huì)，因?yàn)樵陉?duì)列中已經(jīng)等待一段時(shí)間的長(zhǎng)流的TR可能會(huì)更大，因此長(zhǎng)流仍能早于新進(jìn)入的短流進(jìn)行發(fā)送。

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

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

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

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