面向互聯(lián)網(wǎng)流量工程的網(wǎng)絡(luò)測(cè)量及路由調(diào)整算法研究.pdf

1、近年來，隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)性能面臨嚴(yán)峻挑戰(zhàn)，流量工程成為互聯(lián)網(wǎng)進(jìn)一步發(fā)展的關(guān)鍵性問題。由于網(wǎng)絡(luò)傳輸速度日益加快，新業(yè)務(wù)不斷出現(xiàn)，目前的流量工程技術(shù)已經(jīng)不能滿足高速網(wǎng)絡(luò)性能優(yōu)化的要求，更無法滿足未來網(wǎng)絡(luò)發(fā)展的需要。本文重點(diǎn)研究了TCP往返時(shí)延測(cè)量、高速網(wǎng)絡(luò)中的大流檢測(cè)、高速網(wǎng)絡(luò)中的路由調(diào)整，為解決流量工程中的一系列問題提供基礎(chǔ)，從而改善網(wǎng)絡(luò)的性能和服務(wù)質(zhì)量。本文主要研究工作及內(nèi)容如下： (1)被動(dòng)測(cè)量TCP連接往返時(shí)延(R

2、TT)對(duì)網(wǎng)絡(luò)設(shè)計(jì)、流量工程、p2p網(wǎng)絡(luò)性能優(yōu)化等方面都有重要作用。本文針對(duì)現(xiàn)有被動(dòng)測(cè)量方法的不足之處，提出一種在TCP連接的非發(fā)送端被動(dòng)測(cè)量PTT的CROSS算法。CROSS算法通過互相關(guān)函數(shù)判斷數(shù)據(jù)分組與ACK分組之間的對(duì)應(yīng)關(guān)系，繼而獲得TCP連接的RTT值。通過PlanetLab網(wǎng)絡(luò)上的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證，CROSS算法不但能夠在TCP連接建立后的任意階段計(jì)算該連接的RTT，并且可以在網(wǎng)絡(luò)性能較差導(dǎo)致RTT變化較大時(shí)準(zhǔn)確測(cè)量。 (

3、2)互聯(lián)網(wǎng)中大流數(shù)目少但流量大，因此在網(wǎng)絡(luò)擁塞發(fā)生時(shí)快速準(zhǔn)確地找出網(wǎng)絡(luò)中的大流并對(duì)其路由做出調(diào)整，就能夠有效地提高網(wǎng)絡(luò)性能，同時(shí)避免了處理大量小流導(dǎo)致的系統(tǒng)開銷。傳統(tǒng)上基于采樣或Filter結(jié)構(gòu)的大流檢測(cè)算法存在準(zhǔn)確率不夠高的問題。不能滿足互聯(lián)網(wǎng)應(yīng)用的需要。本文提出一種基于兩級(jí)LRU結(jié)構(gòu)的大流檢測(cè)算法LRU2，其中第一級(jí)LRU用于小流過濾，第二級(jí)LRU用于對(duì)大流的準(zhǔn)確計(jì)數(shù)。文章推導(dǎo)了最壞情況下LRU2算法對(duì)大流統(tǒng)計(jì)的誤差上限。并且通過分

4、析證明算法具有10Gbps的線速處理能力?；趯?shí)際互聯(lián)網(wǎng)數(shù)據(jù)的實(shí)驗(yàn)表明：與現(xiàn)有算法相比，LRU2算法具有更高的準(zhǔn)確性和實(shí)用性。 (3)互聯(lián)網(wǎng)流量分布的不均衡會(huì)導(dǎo)致?lián)砣陌l(fā)生，此時(shí)對(duì)某些造成擁塞的關(guān)鍵大流進(jìn)行路由調(diào)整能夠有效地改善網(wǎng)絡(luò)的性能。本文提出一種針對(duì)單條流的路由調(diào)整算法，一方面降低了網(wǎng)絡(luò)最大帶寬利用率，另一方面把被調(diào)整流的路徑長度限制在可接受的范圍之內(nèi)，從而保證了該流的服務(wù)質(zhì)量?；谡鎸?shí)網(wǎng)絡(luò)拓?fù)浜土髁康膶?shí)驗(yàn)表明：新算法能夠

5、有效緩解骨干網(wǎng)擁塞，最多可降低最大帶寬利用率近50％。仿真實(shí)驗(yàn)顯示：與現(xiàn)有算法相比，新算法能夠同時(shí)滿足關(guān)鍵流路徑長度和降低最大鏈路帶寬利用率兩方面的要求。此外，算法復(fù)雜度為O(N2logN)，好于現(xiàn)有的大部分路由調(diào)整算法。 (4)互聯(lián)網(wǎng)中發(fā)生多鏈路擁塞的概率雖然較小，但也會(huì)時(shí)常出現(xiàn)，并且難于處理，給網(wǎng)絡(luò)性能優(yōu)化帶來了困難。針對(duì)這一問題，本文提出了一種基于概率選擇下一跳的關(guān)鍵流路由調(diào)整算法。當(dāng)網(wǎng)絡(luò)中出現(xiàn)多鏈路擁塞時(shí)，算法通過同時(shí)調(diào)