一種適用于比例區(qū)分服務(wù)的數(shù)據(jù)挖掘標(biāo)記算法

0色標(biāo)記算法在原始tcp協(xié)議中，只執(zhí)行流控制，且沒有沖突控制。接收口向tcp報(bào)告接收能力，并將接收能力通知接收方。這樣的控制機(jī)制只考慮了接收端的接收能力,而沒有考慮網(wǎng)絡(luò)的傳輸能力,導(dǎo)致了網(wǎng)絡(luò)擁塞崩潰的發(fā)生。網(wǎng)絡(luò)中的擁塞來源于網(wǎng)絡(luò)資源和網(wǎng)絡(luò)流量分布的不均衡性,不會隨著網(wǎng)絡(luò)處理能力的提高而消除。擁塞控制算法的分布性、網(wǎng)絡(luò)的復(fù)雜性和對擁塞控制算法的性能要求使擁塞控制算法的設(shè)計(jì)具有很高的難度。在DiffServ服務(wù)模型中單流通過DS域邊界后將被分類器劃分為匯聚流,匯聚流通過標(biāo)記器后將被標(biāo)記為不同的丟棄概率。對于核心來說,它僅僅需要對到達(dá)的網(wǎng)絡(luò)流實(shí)施隊(duì)列管理和轉(zhuǎn)發(fā)功能。當(dāng)前的速率標(biāo)記算法可以分為兩類,一類為基于令牌桶的標(biāo)記器,如單速率標(biāo)記器srTCM,雙速率標(biāo)記器trTCM等。另一類為基于時(shí)間的滑動窗口(TimeSlidingWindow,TSW)的標(biāo)記器,如tswTCM,ItswTCM等。本文提出了基于速率預(yù)測的三色標(biāo)記算法(RatePredictionMarker,RPM)。與現(xiàn)有的標(biāo)記算法相比,它有兩個(gè)明顯的改進(jìn):1)基于在線流量預(yù)測算法,能夠動態(tài)估計(jì)源端發(fā)送速率的變化,標(biāo)記依據(jù)為發(fā)送端當(dāng)前的計(jì)量結(jié)果以及未來的變化趨勢,使得算法能夠針對網(wǎng)絡(luò)的變化做出快速反應(yīng),從而提高了標(biāo)記算法的公平性;2)當(dāng)源端發(fā)送的數(shù)據(jù)包數(shù)急劇下降時(shí),發(fā)送端可能進(jìn)入了TCP的擁塞恢復(fù)階段,RPM算法會重新分配網(wǎng)絡(luò)中的可用帶寬,以減小源端的擁塞恢復(fù)所用的時(shí)間,達(dá)到提高網(wǎng)絡(luò)帶寬利用率的目的。1rm算法的設(shè)計(jì)1.1數(shù)據(jù)解碼和標(biāo)記RPM標(biāo)記器的基本設(shè)計(jì)思想為:1)使用在線流量預(yù)測算法MMSEP或者NMSEP對DiffServ網(wǎng)絡(luò)中經(jīng)過分類器劃分的網(wǎng)絡(luò)流或者進(jìn)入標(biāo)記器的網(wǎng)絡(luò)流進(jìn)行提前1期流量預(yù)報(bào),根據(jù)預(yù)報(bào)結(jié)果以及歷史流量的均值進(jìn)行加權(quán),根據(jù)相應(yīng)的結(jié)果對數(shù)據(jù)包進(jìn)行標(biāo)記;2)對源端的發(fā)送數(shù)據(jù)包的變化率進(jìn)行統(tǒng)計(jì),當(dāng)變化率由正值變?yōu)樨?fù)值時(shí),按比例將網(wǎng)絡(luò)中的可用帶寬分配給服務(wù)聚集流,以加快擁塞恢復(fù)時(shí)間,從而提高網(wǎng)絡(luò)帶寬的利用率。RPM標(biāo)記器的主要結(jié)構(gòu)如圖1所示,包括:計(jì)量器,帶寬分配器,速率變化統(tǒng)計(jì),可用帶寬統(tǒng)計(jì)和CIR統(tǒng)計(jì)器。計(jì)量器對到達(dá)的數(shù)據(jù)包進(jìn)行統(tǒng)計(jì),并根據(jù)歷史記錄,對數(shù)據(jù)包的到達(dá)率做出提前預(yù)測,將預(yù)測的結(jié)果和歷史記錄均值的加權(quán)值返回給標(biāo)記器。速率變化器對數(shù)據(jù)包發(fā)送速率的變化進(jìn)行統(tǒng)計(jì),為標(biāo)記器的帶寬分配提供必要的信息。RPM標(biāo)記器中最主要的是計(jì)量器和標(biāo)記器。1.2趨勢外推的計(jì)算方式在RPM算法中,使用計(jì)量器對于經(jīng)過分類器的網(wǎng)絡(luò)流進(jìn)行提前1期的流量預(yù)報(bào),同時(shí)將預(yù)測的結(jié)果與歷史均值進(jìn)行加權(quán),將結(jié)果反饋給標(biāo)記器。計(jì)量器使用MMSEP或者NMSEP算法對于到達(dá)數(shù)據(jù)包數(shù)進(jìn)行預(yù)報(bào),并將預(yù)報(bào)結(jié)果轉(zhuǎn)換為網(wǎng)絡(luò)流的到達(dá)率。具體來說,對于時(shí)間粒度為τ的提前1期預(yù)報(bào)值m來說,預(yù)報(bào)的到達(dá)率為v,且v=m/τ。令{X0,X1,…,Xk}為歷史到達(dá)率,則其均值為Xˉˉˉ=1m∑i=0kXiXˉ=1m∑i=0kXi。對于XˉˉˉXˉ來說,上述計(jì)算方式需要保留無限的歷史溯源信息,這對于現(xiàn)實(shí)網(wǎng)絡(luò)設(shè)備來說是無法實(shí)現(xiàn)的。為此,我們考慮采用遞推的計(jì)算方式來獲得XˉˉˉXˉ的近似值。令XˉˉˉtXˉt為t時(shí)刻的到達(dá)率均值,則t+l時(shí)刻的到達(dá)率均值為:Xˉˉˉt+l=12(Xˉˉˉt+1l∑i=0lXt+i)Xˉt+l=12(Xˉt+1l∑i=0lXt+i)計(jì)量器的數(shù)據(jù)包到達(dá)率估計(jì)算法如下:步驟1:對到達(dá)的網(wǎng)絡(luò)流的數(shù)據(jù)包數(shù)進(jìn)行累積,將具有相同DSCP的網(wǎng)絡(luò)流的數(shù)據(jù)包數(shù)進(jìn)行累加。步驟2:使用時(shí)間粒度為τ的MMSEP或者NMSEP算法對不同的DSCP的網(wǎng)絡(luò)流的數(shù)據(jù)包數(shù)進(jìn)行提前1期的預(yù)報(bào),得出預(yù)報(bào)值mitti。其中,i表示第i個(gè)DSCP分類,t為第t個(gè)時(shí)刻的預(yù)測值。步驟3:計(jì)算出第i個(gè)DSCP網(wǎng)絡(luò)流的提前1期的到達(dá)率預(yù)報(bào)值vitti,且vitti=mitti/τ。步驟4:計(jì)算新的到達(dá)率均值:Xˉˉˉit=12(Xˉˉˉit?τ+1τ∑j=0τXit+j)Xˉti=12(Xˉt-τi+1τ∑j=0τXt+ji)步驟5:得出到達(dá)率的加權(quán)值X^it=ηvit+(1?η)XˉˉˉitX^ti=ηvti+(1-η)Xˉti。1.3rpm算法的標(biāo)記概率標(biāo)記器的基本思想是允許匯聚流發(fā)送與其CIR成比例的Green或者Yellow數(shù)據(jù)包,以充分且公平的利用網(wǎng)絡(luò)中的可用帶寬。給出相應(yīng)的RPM標(biāo)記算法如下:在RMP標(biāo)記算法中,avgRate為計(jì)量器給出的匯聚流i的數(shù)據(jù)包的到達(dá)率。如果avgRate<CIR,則所有的數(shù)據(jù)包被標(biāo)記為Green,這有助于保證匯聚流的CIR;當(dāng)CIR<avgRage≤availableBW時(shí),數(shù)據(jù)包以概率avgRateAvgRate?CIRavgRateavgRateAvgRate-CΙRavgRate被標(biāo)記為Yellow,其余標(biāo)記為Green。當(dāng)avgRate>available時(shí),數(shù)據(jù)包以概率p1=(elseavailableBW[i]avgRate)2p1=(elseavailableBW[i]avgRate)2被標(biāo)記為Yellow,其余的被標(biāo)記為Red。RPM算法的標(biāo)記概率如圖2所示,由圖中可以看出,當(dāng)匯聚流的到達(dá)率小于CIR時(shí),匯聚流的數(shù)據(jù)包全部標(biāo)記為Green。當(dāng)匯聚流的到達(dá)率大于CIR時(shí),仍然有部分?jǐn)?shù)據(jù)包被標(biāo)記為Green。主要道既然匯聚流的發(fā)送速度大于CIR,表明網(wǎng)絡(luò)中必定存在剩余帶寬,因此建數(shù)據(jù)包標(biāo)記為Green有利于提高網(wǎng)絡(luò)吞吐連,進(jìn)而提高帶寬利用率。當(dāng)匯聚流的到達(dá)率大于avaliableB時(shí),隨著到達(dá)率的增大,數(shù)據(jù)包被標(biāo)記為Red的概率將隨著增大。由上述討論可知,RPM算法使用MMSEP或NMSEP兩個(gè)在線流量預(yù)報(bào)模型,對匯聚流的數(shù)據(jù)包的到達(dá)率進(jìn)行預(yù)報(bào),將預(yù)報(bào)的結(jié)果用于帶寬分配和速率變化統(tǒng)計(jì)。當(dāng)網(wǎng)絡(luò)中存在剩余帶寬時(shí),RPM算法根據(jù)比例區(qū)分服務(wù)的原則,將剩余的網(wǎng)絡(luò)帶寬分配給匯聚流。當(dāng)網(wǎng)絡(luò)中沒有剩余帶寬時(shí),優(yōu)先將低級別的匯聚流的CIR按比例減小,以保證高優(yōu)先級匯聚流的服務(wù)質(zhì)量。當(dāng)匯聚流進(jìn)入擁塞恢復(fù)階段是,RPM算法將剩余的網(wǎng)絡(luò)帶寬按比例分配給該匯聚流,以縮短擁塞恢復(fù)的時(shí)間,獲得更高的公平性。2實(shí)驗(yàn)的模擬和結(jié)果使用NS-2仿真軟件進(jìn)行仿真實(shí)驗(yàn),并且與trTCM,ItswTCM,srTCM,TSWTCM這四種標(biāo)記算法進(jìn)行比較。2.1實(shí)現(xiàn)流量模型及模型參數(shù)網(wǎng)絡(luò)仿真拓?fù)鋱D如圖3所示。仿真實(shí)驗(yàn)中,DiffServ域通過edg1,edg2,edg3這三個(gè)入口節(jié)點(diǎn)與DiffServ域外網(wǎng)絡(luò)節(jié)點(diǎn)相連。網(wǎng)絡(luò)source1中的各單元組成第一個(gè)匯聚流A1,通過邊界節(jié)點(diǎn)edg1進(jìn)入DiffServ域,然后經(jīng)過邊界節(jié)點(diǎn)edg3離開DiffServ域,到達(dá)接收端。網(wǎng)絡(luò)source2,source3中的網(wǎng)絡(luò)流形成匯聚流A2,A3并經(jīng)過edg2進(jìn)入DiffServ域,然后通過edg3到達(dá)不同的接收端。為了簡單起見,我們假定各單流在進(jìn)入DiffServ前,已經(jīng)經(jīng)過了分類器,且已被劃分為相應(yīng)的匯聚流A1,A2,A3。圖3中各部分的網(wǎng)絡(luò)鏈路的參數(shù)如表1所示。計(jì)量器的流量預(yù)報(bào)算法采用MMSEP模型,預(yù)報(bào)時(shí)間粒度為100ms,其模型參數(shù)如表2所示。在仿真實(shí)驗(yàn)中,采用FTP流作為TCP數(shù)據(jù)流,源端采用TCP-Reno協(xié)議,數(shù)據(jù)包平均大小為1000Bytes,源端和接收端最大窗口大小為40,edg1,edg2,edg3最多能容納1000個(gè)報(bào)文。在仿真實(shí)驗(yàn)中,srTCM和trTCM的令牌發(fā)送速率為其CIR,CBS為10k字節(jié),且srTCM的EBS設(shè)置為16K字節(jié)。trTCM的PBS為16K字節(jié),PIR=1.5*CIR。ItswTCM的因子c為2。2.2比例區(qū)分服務(wù)下的公平性本節(jié)通過實(shí)驗(yàn)討論RPM算法在非區(qū)分比例服務(wù)、區(qū)分比例服務(wù)條件下當(dāng)匯聚流的目標(biāo)速率發(fā)生變化時(shí),對算法公平性的影響。對于非比例區(qū)分服務(wù)的網(wǎng)絡(luò)流(即ci/cj=1,0<i,j<k)的公平性比較,采用文獻(xiàn)給出的公平性定義,即對于一個(gè)n流的系統(tǒng),其吞吐率分別表示為(x1,x2,…,xn),則系統(tǒng)的公平指數(shù)公式為:f(x1,x2,?,xn)=(∑i=1nxi)2n∑i=1nx2if(x1,x2,?,xn)=(∑i=1nxi)2n∑i=1nxi2在這里,令xi=匯聚流i的帶寬匯聚流i的CIRxi=匯聚流i的帶寬匯聚流i的CΙR。根據(jù)以上定義,公平指數(shù)越接近1,則可利用帶寬在匯聚流中的分配越公平。在本實(shí)驗(yàn)中,匯聚流A1的目標(biāo)速率由1Mbps變化到10Mbps,匯聚流A2的目標(biāo)速率由1kbps變化到1.2Mbps,然后進(jìn)入擁塞階段。匯聚流A3中單流的目標(biāo)速率由10Mbps變化為16Mbps,然后穩(wěn)定在這個(gè)目標(biāo)速率。各算法在不同網(wǎng)絡(luò)負(fù)載下的公平性如圖4所示。由圖4可知,當(dāng)匯聚流A2的目標(biāo)速率增大時(shí),srTCM,IswTCM,TSWTCM,trTCM的公平性指數(shù)都發(fā)生較大抖動,而RPM算法的公平性能在較大范圍內(nèi)保持平穩(wěn),且優(yōu)于其他算法?？芍?RPM在非比例區(qū)分服務(wù)條件下的公平性基本上不受匯聚流目標(biāo)速率變化的影響。接下來考慮RPM算法在比例區(qū)分服務(wù)條件下的公平性。對于匯聚流i,其相應(yīng)的流公平指數(shù)為:fi(xi,1,xi,2,?,xi,n)=(∑m=1nxi,m)2n∑m=1nx2i,mfi(xi,1,xi,2,?,xi,n)=(∑m=1nxi,m)2n∑m=1nxi,m2對于匯聚流i和匯聚流j,其對應(yīng)的比例因子分別為ci,cj,給出比例區(qū)分服務(wù)的公平指數(shù)fi/j定義如下:fi/j=fi(xi,1,xi,2,?,xi,n)cjfj(xj,1,xj,2,?,xj,n)cifi/j=fi(xi,1,xi,2,?,xi,n)cjfj(xj,1,xj,2,?,xj,n)ci由上式可知,fi/j越接近于1,說明相應(yīng)的公平性越好?？紤]采用比例區(qū)分服務(wù)后匯聚流A2和A3的公平性,定義A3為比A2具有更高服務(wù)級別的網(wǎng)絡(luò)匯聚流,其服務(wù)比例因子c3/c2=10。相應(yīng)的仿真結(jié)果如圖5所示。由圖中可以看出,即使匯聚流A3目標(biāo)速率發(fā)生了過量訂購,RPM算法仍能較好的保證高服務(wù)級別的匯聚流的服務(wù)質(zhì)量。2.3高隱蔽性的sdk2仿真RPM算法的另一個(gè)重要特點(diǎn)是,通過觀測到達(dá)率的變化率,來縮短相關(guān)匯聚流的擁塞恢復(fù)時(shí)間,從而提高匯聚流的平均吞吐量。流的擁塞恢復(fù)時(shí)間可以通過其吞吐量來反映,好的標(biāo)記算法,應(yīng)當(dāng)能夠使匯聚流的吞吐量在發(fā)生擁塞后,迅速恢復(fù)到平均水平。在本節(jié)的仿真試驗(yàn)中,只有匯聚流A2,A3發(fā)送數(shù)據(jù),A1不發(fā)送數(shù)據(jù)。鏈路的瓶頸帶寬為1.2Mbps,edg2的最大隊(duì)列長度定義為40個(gè)Packet,RTT為40ms,設(shè)置隨機(jī)的丟包率為0.05。匯聚流A3以300kbp/s的穩(wěn)定速率發(fā)送FTP數(shù)據(jù)。匯聚流A2的CIR為1M,其以500kb/s的速率開始發(fā)送FTP數(shù)據(jù),然后增加到1.2Mb/s,此時(shí)進(jìn)入擁塞控制階段。我們分別在edg2配置了srTCM算法和RPM算法。圖6和圖7為數(shù)據(jù)包丟失率和吞吐量的仿真結(jié)果。由圖6中可以看出,srTCM算法的數(shù)據(jù)包丟失率隨著匯聚流A2的發(fā)送速率的增加,急劇上升。而RPM算法的變化幅度則小得多。由圖7可以看出,隨著RTT的變化srTCM算法的吞吐量變化劇烈,而RPM算法獲得的吞吐量則比較平穩(wěn),而且能夠維持在較高水平。由上述仿真試驗(yàn)可知,RPM算法通過變化率統(tǒng)計(jì)器,來反映匯聚流到達(dá)率的變化率,能夠有效地縮短相應(yīng)流的擁塞恢復(fù)時(shí)間,從而能夠獲得較高的吞吐量,提高了相應(yīng)流競爭帶寬的能力,使得算法的公平性和帶寬利用率都有很大提高。3可檢測流量到達(dá)率提出了一種適用于比例區(qū)分服務(wù)的數(shù)據(jù)包標(biāo)記算法RPM算法,該算法通過預(yù)測匯聚流的到達(dá)率和帶寬估計(jì),能夠?yàn)镈iffServ域提供更好的服務(wù)質(zhì)量。RPM算法將MMSEP和NMSEP兩種在線流量預(yù)測算法引入計(jì)量器,用于估計(jì)匯聚流的到達(dá)率,將匯聚流的到達(dá)率和歷史均值進(jìn)行加權(quán),得出加權(quán)后的匯聚流到達(dá)率,將此到達(dá)率作為帶寬分配的依據(jù)。通過觀測匯聚流的到達(dá)率的變化情況,當(dāng)發(fā)現(xiàn)匯聚流進(jìn)入擁塞恢復(fù)階段時(shí),通過給相關(guān)匯聚流分配額外帶寬,來縮短匯聚流的擁塞恢復(fù)時(shí)間,從而提到了吞吐量。通過仿真試驗(yàn),驗(yàn)