基於穩定採樣序列的網絡路徑帶寬測量方法
2023-09-17 11:12:35 5
專利名稱：基於穩定採樣序列的網絡路徑帶寬測量方法
技術領域：
本發明涉及一種網絡路徑帶寬測量方法，確切地說涉及一種基於穩定採樣序列，測量結果準確、消耗CPU和內存等資源低的網絡路徑帶寬測量方法。
技術背景網絡運營商需要了解網際網路的帶寬情況來指導網絡運行維護和擴充容量等規劃工作；同時，網際網路的許多應用也需要了解網絡帶寬特性來優 化其應用的性能。因此，網絡路徑帶寬測量技術對於網絡運營商和網絡應 用有著非常重要的意義，它在網絡運營、設備研製和下一代網絡新生業務 中有著廣泛的應用。人們發明了各種方法對路徑帶寬進行測量，如VPS, SLOPS ， Packet Pair 等等。在基於TCP協議的帶寬測量中，目前採用的主要是包對(PacketPair) 方法及其變種。包對的測量方式不需要網絡中路由器協作， 一般通過受測網絡路徑兩 端的兩臺主機來完成測量任務，其中一臺主機A發送測量數據包，另一臺 主機B接受測量數據包。其基本原理如下為了測量兩點之間如果主機A 到主機B之間的路徑帶寬，先從主機A連續發送兩個長度相等(都為L) 的報文到主機B，在主機B上記錄這兩個報文到達的時間差AT，則路徑帶 寬PB可以表示為L/AT。 PB表示了實際路徑帶寬的一個測量結果(稱為 採樣)，將多個PB採樣結果取其均值，就可以獲得對主機A到主機B實 際路徑帶寬的最終估計結果。儘管原理非常簡單，但是包對測量有著相當大的技術難度，上述原理 是在假定網絡中沒有背景流量下獲得的。但是，網絡中總是存在著背景流 量，即其他正常業務的數據包。由於背景流量的影響，上述包對測量方法 所測得的路徑帶寬存在著很大的誤差，有研究發現多個探測包對得出的測 量結果呈現多峰態分布，並指出是背景流量的多模態引起了多峰現象。特 別是在網絡擁塞程度較高的情況下，不同測量採樣之間的差異將會非常明 顯，導致測量結果無法真實代表網絡的真實路徑帶寬。為了濾除背景流量對測量結果帶來的影響，目前，國內外主要採用兩 種技術密度估計技術和基於接收/發送帶寬比率的過濾技術。但這兩種方 '法都要求測量主機保存所有的測量採樣，然後按照比較複雜的統計算法在 有測量採樣中反覆進行統計和比較操作，因此必然會大量消耗測量主機 的CPU和內存資源，不適合於大規模流量下對多個網絡路徑的並發實時測 量。
公開號為CN154527，申請日為2003年11月19日的中國專利文獻公 開了一種端到端的網絡瓶頸帶寬測量方法，該專利文獻具體公開了以下技術方案包括下述步驟A.初步估算三個測量參數受測網絡路徑的環回時延RTT，帶寬測量精度範圍BIN和一個比真實值偏小的瓶頸帶寬左界值； B.發送端發送多組不同包長的測量數據包對，接收端收到測量數據包對後， 記錄存儲測量數據，並發送確認應答；C.接收端分別按不同包長和不同序號把測量數據分組，兩兩交織進行矩形呈現處理，獲得多幅測量樣值矩形 分布圖，然後根據所有分布圖中峰的位置分布情況，利用挑峰和濾峰操作 找出相對固定的成峰位置，得出瓶頸帶寬測量結果值。該專利與現有技術 相比，該方法能比較準確地測出路徑帶寬，但由於找出相對固定的成峰位 置採樣需要仍然必須保留所有的採樣，才能夠得到最終的路徑帶寬值，從
而仍然需要佔用大量的CPU和內存資源。
發明內容
為解決上述技術問題，本發明提出了一種基於穩定採樣序列的網絡路 徑帶寬測量方法，與現有的各種測量方法、工具相比，本發明採用穩定序 列過濾方法，濾除了大量不穩定的測量採樣序列，使剩餘的採樣具有較高 的穩定程度，測量結果能夠更加準確地反應網絡的真實帶寬；同時，本發 明濾除了大量不穩定的測量採樣序列，只需保留最近的幾個採樣序列就可 以判斷下一採樣是否是穩定採樣，與傳統的必須保留所有採樣才能夠得到 最終結果的估計方法相比，大大節省了 CPU和內存資源。
本發明釆用的技術方案是這樣實現的 一種基於穩定採樣序列的網絡 路徑帶寬測量方法，其步驟如下A、 選擇兩臺主機， 一臺為主機A， 一臺為主機B;B、 選擇測量點，在主機A和主機B之間的網絡路徑上選擇一測量點C;C、 傳送測量數據包對，主機A向主機B發送請求數據包，主機B發 送回應並向A發送數據；D、 數據分析，在測量點C處抓取從主機A到達測量點C的數據流分 組，把兩個連續的數據包稱為一個包對，包括DATA1和DATA2兩個數據 包，其中DATA1到達測量點C的時間為T0， DATA2到達測量點C的時 間為Tl， T0和Tl之間的間隔AT-T1-T0，定義DATA1的長度為L，則主 機B與C之間的路徑帶寬為HPBb=L/AT;在測量點C處抓取從主機A到 達測量點C的數據包，同樣把兩個連續的數據包稱為一個包對，也包括 DATA1和DATA2兩個數據包，其中DATA1到達測量點C的時間為T0， DATA2到達測量點C的時間為TI， T0和Tl之間的間隔AT-T1-T0，定義 DATA1的長度為L，則主機A與C之間的路徑帶寬為HPBa=L/AT;E、濾除不穩定採樣，將步驟D中獲得的n個採樣HPBa作為一個採 樣序列，比較任意兩個相鄰採樣之間的偏差比例d叫HPBai- HPBai-l|/ (HPBai + HPBai-l),定義d的絕對值小於0.2，表示所述兩個相鄰採樣差異 不大，那麼這兩個相鄰採樣被認為是穩定的採樣，被保留，如果所得結果 d的絕對值大於或等於0.2，則表示這兩個相鄰採樣為不穩定的採樣，被濾 除，n個採樣被濾除後剩下m個穩定採樣，將這m個穩定採樣取平均值， 獲得HPBa的相對精確測量值；同理，將步驟D中獲得的n個採樣HPBb 作為 一 個採樣序列，比較任意兩個相鄰採樣之間的偏差比例 d叫HPBbi-HPBbi-11/ (HPBbi+HPBbi-1),定義d的絕對值小於0.2，表示所 述兩個相鄰採樣差異不大，那麼這兩個相鄰採樣被認為是穩定的採樣，被 保留，如果所得結果d的絕對值大於或等於0.2，則表示這兩個相鄰採樣 為不穩定的採樣，被濾除，n個採樣被濾除後剩下m個穩定採樣，將這m 個穩定採樣取平均值，獲得HPBb的相對精確測量值；F、獲得最終相對精確測量值，取步驟E所得的相對精確測量值HPBa 和HPBb之間的最小值，則獲得主機A和主機B之間的實際路徑帶寬。所述的數據流為根據TCP協議類型傳輸的TCP數據流，或包括TCP 數據流和以其他協議類型傳輸的其他數據流。本發明的優點在於1、 與現有的各種測量方法、工具相比，本發明採用穩定序列過濾方 法，濾除了大量不穩定的測量採樣序列，使剩餘的採樣具有較高的穩定程 度，測量結果能夠更加準確地反應網絡的真實帶寬。2、 由於本發明穩定採樣序列的分析方法不需要保留所有的測量採樣， 只需要保留最近的幾個釆樣就可以判斷下一採樣是否是穩定採樣，而傳統 的統計方法、核心密度估計方法必須保留所有採樣，才能夠從中計算出密 度最高的採樣值，因此，與傳統方法相比，本方法在大規模網絡環境下， 可以節省大量的CPU和內存資源。
圖1為在主機A和主機B之間設置測量點C並數據分析的位置結構 示意2為網絡中多種類型流量存在時測得的不同的AT示意3為未經過過濾的採樣序列4為未過濾序列對應的帶寬分布5為濾除不穩定採樣序列後的採樣序列6為過濾後序列對應的帶寬分布圖具體實施方式
. ^ 實施例1
在實驗中我們發現在網絡擁塞的情況下，密度最大的採樣往往不能 代表真實的路徑帶寬，而相對穩定的採樣序列才是真實有效的。因此，應 當將一段時間內的採樣結果作為序列進行研究，取出穩定性較高的序列作 為有效序列，並且在最終測量結果中佔有較高的權重。本方案的目標是測量網際網路中兩臺主機之間的路徑帶寬，採用如下方法A、 選擇兩臺主機， 一臺稱為主機A， 一臺稱為主機B;B、 選擇測量點，測量點C位於主機A和主機B之間，則只要估算出A到C之間的路徑帶寬就可知道A與B之間的帶寬。C、 在測量點C抓取從主機A通往主機B的網絡流量。A和B之間的 通信包括很多內容，由於目前網絡上應用最多的是TCP協議，因此只選擇 TCP數據流作為觀測對象，將TCP數據流看作從主機A到主機B路徑上 的所有流量，在C點抓取從主機A到達測量點的每個TCP分組，通過對 TCP分組進行分析操作來得到路徑的帶寬。如圖l，主機A向主機B發送 請求數據包，主機B發送回應並向A發送數據，在測量點C將路徑上的 所有數據包抓獲，通過對這些數據包的分析，來計算主機A到主機B路徑 上的帶寬。D、 網絡上的TCP報文都是連續發送的，並且往往單向發送儘量多的 報文，然後等待對方的確認，因此網絡上經常出現順序連續的TCP分組， 把兩個連續的TCP分組稱為一個包對(Packet Pair),如圖1所示的DATA1 與DATA2， DATA1分組到達測量點C的時間為TO, DATA2分組到達測量 點C的時間為T1， 二者間隔AT-T1-T0，如果DATA1分組的長度為L，則 B與C點之間的路徑帶寬可以表示為HPBb=L/AT ，當A與B之間的路 徑不存在其他類型流量的情況下，HPBb就是B與C之間的路徑帶寬。同 理可以獲得A與C之間的路徑帶寬HPBa,即在測量點C處抓取從主機A 到達測量點C的數據流分組，把兩個連續的數據流稱為一個包對，包對 DATA1到達測量點C的時間為TO,包對DATA2到達測量點C的時間為 Tl， TO和Tl之間的間隔AT-T1-T0，定義DATA1的長度為L，則主機A 與C之間的路徑帶寬為HPBa=L/AT;取HPBa和HPBb中間的最小值，就 可以獲得A點和B點之間的路徑帶寬PB。 ，E、 當然，前面講的是較理想的情況，在現實網絡中，往往不可能沒 有其他類型流量的存在，因此針對不同包對測得的AT值都會不一樣。如圖 2所示。由此帶來的結果是HPBa的多個採樣值(HPBal…n)存在不同程度 的差異，同樣HPBb的多個採樣值(HPBal…n)之間也存在差異。為了從不同採樣中找出最能夠反應網絡真實帶寬的釆樣值，本方案採 用"穩定採樣序列"方法來篩除不穩定的釆樣。具體方法為將n個採樣(HPBal…n)作為一個採樣序列，比較任意
兩個相鄰採樣之間的偏差比例d=(HPBai-HPBai-l)/(HPBai + HPBai-l)，如 果d的絕對值小於某個閾值(0.2)，表示這兩個相鄰的採樣差異不大，那 麼這兩個採樣被認為是穩定的採樣，被保留，否則會被篩除。經過一輪篩 選之後，n個採樣只剩下m個穩定採樣(nK^)，將這m個採樣(HPBal…m) 取平均值，可獲得HPBa的相對精確估計。例如，某採樣序列(HPBal…4 )的值依次為(67Mbps,32Mbps,88Mbps,81Mbps)，採用"穩定採樣序列方法"進行過濾 時，計算HPBal禾a HPBa2之間的偏差比為d=|67-32|/(67+32)=0.35>0.2， 說明前兩個採樣測得的結果是不穩定的，應當被篩除；而計算HPBa3和 HPBa4之間的偏差比為<1叫81-88|/(81+88)=0.04<0.2，說明這兩個相鄰採樣 的結果較為穩定，應當被保留。由此，經過本方法過濾之後的採樣序列為(88Mbps,81Mbps)。同理可獲得HPBb的精確估計，即將步驟D中獲得的n個採樣HPBb 作為一個採樣序列，比較任意兩個相鄰採樣之間的偏差比例d=(HPBbi-HPBbi-l) / (HPBbi+HPBbi陽l),定義d的絕對值小於0.2，表示 所述兩個相鄰採樣差異不大，那麼這兩個相鄰採樣被認為是穩定的採樣， 被保留，如果所得結果d的絕對值大於或等於0.2，則表示這兩個相鄰採 樣為不穩定的採樣，被濾除，n個採樣被濾除後剩下m個穩定採樣，將這 m個穩定採樣取平均值，獲得HPBb的相對精確測量值。F、取HPBa禾P HPBb的最小值，可獲得A和B之間的實際路徑帶寬。 實施例2實驗驗證已知A、 B兩點之間的路徑帶寬為100Mbps (該網絡路徑已經承載了 大量網絡流量，已經高度擁塞)，在AB之間部署測量點C，顯然，主機A 到測量點C之間的路徑帶寬HPBa也是1 OOMbps 。在測量點C監視A發送給B的TCP數據流(可以通過FTP文件傳輸 等方式產生該數據流)，其中，可以觀測到多個連續的TCP包對(Packet Pair),根據每個包對，可以計算出一個HPBa路徑帶寬HPBa=L/AT，其 中L為TCP包對中第一個數據包的長度，AT為包對中兩個包到達C點的 時間間隔。經過以上計算，產生了一個測量採樣。在測量過程中， 一共獲得520個採樣(HPBal…HPBa520)。如下表 採樣序號 採樣值(單位Mbps)1 0.152902882 79.027027033 0.0942093774 36.66457685 92.094488196 0.274773293
724.5714285780.299023368954.65420561100.162370025110.091637743120.0912047041387.939849621492.8253968315248.8510638160.075333157170.163961084180.1565184811939.513513512068.800000002163.912568312287.28358209230.171563522採樣序列分布如圖3。可見，大量的採樣位於0—10Mbps之間，如果採用傳統統計方法或核 心密度方法，統計得到的HPBa帶寬僅為10Mbps，與實際值相差很遠。採用本方案的穩定序列過濾方法，過濾掉大量不穩定的採樣，最終保 留的穩定採樣數量IIO個，如圖5。對以上採樣取平均值，得到HPBa=97Mbps，能夠比較精確地反應A 到C的真實路徑帶寬。可見，本方案測量精確度明顯優於傳統方法。
權利要求
1、一種基於穩定採樣序列的網絡路徑帶寬測量方法，其特徵在於步驟如下A、選擇兩臺主機，一臺為主機A，一臺為主機B；B、選擇測量點，在主機A和主機B之間的網絡路徑上選擇一測量點C；C、傳送測量數據包對，主機A向主機B發送請求數據包，主機B發送回應並向A發送數據；D、數據分析，在測量點C處抓取從主機A到達測量點C的數據流分組，把兩個連續的數據包稱為一個包對，包括DATA1和DATA2兩個數據包，其中DATA1到達測量點C的時間為T0，DATA2到達測量點C的時間為T1，T0和T1之間的間隔ΔT＝T1-T0，定義DATA1的長度為L，則主機B與C之間的路徑帶寬為HPBb＝L/ΔT；在測量點C處抓取從主機A到達測量點C的數據包，同樣把兩個連續的數據包稱為一個包對，也包括DATA1和DATA2兩個數據包，其中DATA1到達測量點C的時間為T0，DATA2到達測量點C的時間為T1，T0和T1之間的間隔ΔT＝T1-T0，定義DATA1的長度為L，則主機A與C之間的路徑帶寬為HPBa＝L/ΔT；E、濾除不穩定採樣，將步驟D中獲得的n個採樣HPBa作為一個採樣序列，比較任意兩個相鄰採樣之間的偏差比例d＝|HPBai-HPBai-1|/(HPBai+HPBai-1)，定義d的絕對值小於0.2，表示所述兩個相鄰採樣差異不大，那麼這兩個相鄰採樣被認為是穩定的採樣，被保留，如果所得結果d的絕對值大於或等於0.2，則表示這兩個相鄰採樣為不穩定的採樣，被濾除，n個採樣被濾除後剩下m個穩定採樣，將這m個穩定採樣取平均值，獲得HPBa的相對精確測量值；同理，將步驟D中獲得的n個採樣HPBb作為一個採樣序列，比較任意兩個相鄰採樣之間的偏差比例d＝|HPBbi-HPBbi-1|/(HPBbi+HPBbi-1)，定義d的絕對值小於0.2，表示所述兩個相鄰採樣差異不大，那麼這兩個相鄰採樣被認為是穩定的採樣，被保留，如果所得結果d的絕對值大於或等於0.2，則表示這兩個相鄰採樣為不穩定的採樣，被濾除，n個採樣被濾除後剩下m個穩定採樣，將這m個穩定採樣取平均值，獲得HPBb的相對精確測量值；F、獲得最終相對精確測量值，取步驟E所得的相對精確測量值HPBa和HPBb之間的最小值，則獲得主機A和主機B之間的實際路徑帶寬。
2、 根據權利要求1所述的基於穩定採樣序列的網絡路徑帶寬測量方 法，其特徵在於所述的數據流為根據TCP協議類型傳輸的TCP數據流， 或包括TCP數據流和以其他協議類型傳輸的其他數據流。
全文摘要
本發明公開了一種基於穩定採樣序列的網絡路徑帶寬測量方法，包括選擇主機、選擇測量點、主機之間傳送測量數據包對，對數據包對進行分析，濾除不穩定採樣以及獲得最終相對精確測量值等步驟，與現有的各種測量方法、工具相比，本發明採用穩定序列過濾方法，濾除了大量不穩定的測量採樣序列，使剩餘的採樣具有較高的穩定程度，測量結果能夠更加準確地反應網絡的真實帶寬。
文檔編號H04L12/56GK101110714SQ20071004979
公開日2008年1月23日 申請日期2007年8月20日 優先權日2007年8月20日
發明者翔 張, 定 李, 汪文勇, 黃鸝聲 申請人:電子科技大學