面向互聯(lián)網流量工程的網絡測量及路由調整算法研究.pdf

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

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

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

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

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