網絡丟包率探測方法
2023-09-19 15:21:45 1
專利名稱：網絡丟包率探測方法
技術領域：
本發明涉及計算機網絡技術領域，特別是涉及一種網絡丟包率探測方法。
背景技術：
近年來，隨著計算機網絡規模日益擴大，受設備多樣性與網絡複雜性影響，網絡中的不穩定因素也在增加；與此同時，網絡流量急劇增長，各類新型業務，如視頻會議、視頻點播、P2P等，也以極快的速度吞噬著網絡資源，人們對網絡的可靠性、穩定性和高效性的要求越來越高，對網絡的管理提出了嚴峻的考驗。網絡測量——精確地捕捉定量的網際網路及其活動的測量數據——作為系統中獲取信息的關鍵環節，其根本目的是全面了解網絡行為，總結網絡行為的規律，研究制約網絡性能提高的因素，為人們正確、高效地管理網絡提供了有力的理論依據。按照測量系統所處 的位置，網絡測量可分為基於路由器的測量、端到端的測量以及路由器協助的測量。當前廣泛應用的是路由器測量方法，即在網絡節點或者網絡節點之間直接主動或被動測量網絡性能，但該方法存在著很多潛在的局限，如成本、安全、性能、可行性等。以上這些原因使得需要引進新的測量方法，能夠在沒有路由節點的配合下，通過端到端的測量來診斷網絡性能問題。網絡層析成像，是將醫學上的計算機斷層成像思想引入到網絡測量中，在網絡邊界上進行端到端的測量，根據網絡邊界的測量信息來分析和探測網絡的內部性能，是一種在沒有網絡節點協作條件下，通過主動發送探測或被動收集網絡內部有用信息的新技術，結合統計學方法能夠較準確地探測出網絡所有鏈路的參數。丟包率探測技術作為其中一個分支，是了解網絡行為、進行網絡控制、消除網絡瓶頸、提高網絡性能的基礎和重要環節，因此具有十分重要的意義。現有的丟包率探測技術可以採用多播探測或單播探測，基於多播探測的探測技術是指各網絡節點使用多播數據包進行探測，通過路徑間的相關性信息探測丟包率；而基於單播探測的探測技術是指各節點使用單播數據包進行探測，視算法不同可能需要進行多次探測或特殊形式的探測。較早的層析成像技術多採用多播探測，R. Caceres等人早在1999年就對其進行了較為系統的研究。基於多播探測的丟包率探測技術通常採用極大似然法進行探測，在探測中需要採用多播探測包探測，精度較高。但是支持多播的網絡環境較少，因而這類方法的應用受到較大限制。為了解決多播探測應用環境受限的問題，可以採用單播探測。公開號為CN102299829A的中國專利申請提供了一種網絡故障探測與定位的方法，通過將網絡模擬成貝葉斯模型進行概率探測來定位丟包率大的故障鏈路；公開號為CN101296133A的中國專利申請提供了一種丟包率的推測方法，在網絡內部設置監測點，通過極大似然法和期望最大化法探測鏈路丟包率；公開號為CN1921422A的中國專利申請提供了一種估計丟包率的方法，通過包組模擬多播環境，並通過最小二乘法探測鏈路丟包率。H. X. Nguyen等人提出的LIA算法是目前較為先進的丟包率探測算法，通過多次探測計算鏈路丟包率的方差，根據方差探測鏈路丟包率。但這些算法對探測要求較高，並且計算複雜，不能滿足大規模網絡探測的需求。具體來說，上述現有技術存在以下缺陷(I)早期基於多播探測的探測算法以及公開號為CN101296133A的中國專利申請提供的丟包率探測算法，其應用環境受限。現有的基於多播探測的丟包率探測算法需要被探測網絡內部所有設備支持多播，而大多數網絡無法滿足這一要求，因而基於多播探測的丟包率探測算法缺乏實用價值。在網絡內部設置監測點同樣存在這個缺陷。(2) LIA算法以及公開號為CN1921422A的中國專利申請提供的包組探測法對網絡造成負載較重，探測時間長。現有的基於單播探測的丟包率探測技術為了獲取網絡中的信息而採取了較為複雜的探測模式。例如LIA算法需要對每條路徑進行多次探測，包組法需要對每一組路徑發送探測包組，也會使每條路經被多次探測，這都將產生較大的網絡流量，從而可能人為造成擁塞，對測量結果造成影響。多次探測所需的探測時間也比較長，更容易 受到網絡內不穩定因素的幹擾。(3)公開號為CN102299829A的中國專利申請提供的方法複雜度較高。實際網絡節點規模比較大的情況下，運算時間比較長，已經失去探測的意義。
發明內容
(一)要解決的技術問題本發明要解決的技術問題是如何快速、準確、簡便地探測丟包率。(二)技術方案為了解決上述技術問題，本發明提供一種網絡丟包率探測方法，其特徵在於，包括以下步驟101、使用單播數據包探測網絡的拓撲以及每條探測路徑的丟包率，並根據所述網絡的拓撲和路徑的丟包率進行建豐吳;102、根據所建的模型計算鏈路丟包率；103、判斷步驟102是否能計算出所有鏈路丟包率，若是，則結束；否則執行步驟104 ；104、根據步驟102所計算的鏈路丟包率建立目標函數；105、根據所述目標函數求出剩餘鏈路的丟包率；106、將步驟102和步驟105所計算出的鏈路丟包率合併，得到所有鏈路丟包率結果。優選地，步驟101中，使用線性代數模型進行建模。優選地，所述建模的步驟具體為建立代數方程y = Dx，式中y是已知列向量，表示每條路徑通過率的對數，通過率=I-丟包率，X是未知列向量,表示每條鏈路通過率的對數；D是路由矩陣，所述路由矩陣的一行表示一條路徑，一列表示一條鏈路，Di,,為矩陣D的第i行第k列的元素。優選地，步驟102中，將方程y = Dx的解X表示為非齊次線性方程組的導出組0=Dx的基礎解系Zr，與非齊次線性方程的一組特解Xtl之和，X = Zr+x0, Z為矩陣D的零空間中的一組基，r為任意實數向量，X0為非齊次線性方程y = Dx的一組特解。優選地，步驟103具體為判斷步驟102是否已經計算出所有鏈路丟包率，若Z為空矩陣，表示所有鏈路丟包率都能夠唯一確定，則結束；若Z非空，表示不能唯一確定所有鏈路丟包率，則方程y = Dx的解包含任意實數向量r，執行步驟104。優選地，步驟104中，根據矩陣Z中每一行是否包含非0元素，將方程組y = Dx的解X拆分成兩組xA = x0A和XB = ZBr+x0B,上標A、B用於標識這兩組解，根據步驟102所計算出的鏈路丟包率求出對應的鏈路通過率的均值歹，然後以歹為先驗概率建立非線性規劃的目標函數min f(r),其中，
權利要求
1.一種網絡丟包率探測方法，其特徵在於，包括以下步驟 101、使用單播數據包探測網絡的拓撲以及每條探測路徑的丟包率，並根據所述網絡的拓撲和路徑的丟包率進行建模； 102、根據所建的模型計算鏈路丟包率； 103、判斷步驟102是否能計算出所有鏈路丟包率，若是，則結束；否則執行步驟104； 104、根據步驟102所計算的鏈路丟包率建立目標函數； 105、根據所述目標函數求出剩餘鏈路的丟包率； 106、將步驟102和步驟105所計算出的鏈路丟包率合併，得到所有鏈路丟包率結果。
2.如權利要求I所述的方法，其特徵在於，步驟101中，使用線性代數模型進行建模。
3.如權利要求2所述的方法，其特徵在於，所述建模的步驟具體為建立代數方程y=Dx，式中y是已知列向量，表示每條路徑通過率的對數，通過率=I-丟包率，X是未知列向量，表示每條鏈路通過率的對數；D是路由矩陣，所述路由矩陣的一行表示一條路徑，一列表示一條鏈路，Dijk為矩陣D的第i行第k列的元素。
4.如權利要求3所述的方法，其特徵在於，步驟102中，將方程y= Dx的解x表示為非齊次線性方程組的導出組O = Dx的基礎解系Zr與非齊次線性方程的一組特解Xtl之和，X = Zr+x0, Z為矩陣D的零空間中的一組基，r為任意實數向量，X0為非齊次線性方程y =Dx的一組特解。
5.如權利要求4所述的方法，其特徵在於，步驟103具體為判斷步驟102是否已經計算出所有鏈路丟包率，若Z為空矩陣，表示所有鏈路丟包率都能夠唯一確定，則結束；若Z非空，表示不能唯一確定出所有鏈路丟包率，方程y = Dx的解包含任意實數向量r，執行步驟104。
6.如權利要求3所述的方法，其特徵在於，步驟104中，根據矩陣Z中每一行是否包含非O元素,將方程組y = Dx的解X拆分成兩組xA = x0A和xB = ZBr+x0B,上標A、B用於標識這兩組解，根據步驟102所計算出的鏈路丟包率求出對應的鏈路通過率的均值歹，然後以歹為先驗概率建立非線性規劃的目標函數min f (r)，其中，
7.如權利要求6所述的方法，其特徵在於，步驟105具體為使用非線性規劃方法求出滿足約束條件且使目標函數最小的一組r，再代入Xb的表達式解出xB，從而求出剩餘鏈路的丟包率。
8.如權利要求3所述的方法，其特徵在於,Di,k取值為O或1，當Di,k= O時表示路徑i不包含鏈路k,當Di,k = I時表示路徑i包含鏈路k。
9.如權利要求4所述的方法，其特徵在於，步驟102中使用最小範數解作為特解X(1。
全文摘要
本發明涉及計算機網絡技術領域，公開了一種網絡丟包率探測方法，包括以下步驟101、使用單播數據包探測網絡的拓撲以及每條探測路徑的丟包率，並根據所述網絡的拓撲和路徑的丟包率進行建模；102、根據所建的模型計算鏈路丟包率；103、判斷步驟102是否能計算出所有鏈路丟包率，若是，則結束；否則執行步驟104；104、根據步驟102所計算的鏈路丟包率建立目標函數；105、根據所述目標函數求出剩餘鏈路的丟包率；106、將步驟102和步驟105所計算出的鏈路丟包率合併，得到所有鏈路丟包率結果。本發明針對應用環境受限的問題，採用單播探測，無需內部節點協助，快速、準確地探測丟包率。
文檔編號H04L12/26GK102739527SQ201210195830
公開日2012年10月17日 申請日期2012年6月14日 優先權日2012年6月14日
發明者亓峰, 孟洛明, 王穎, 邱雪松, 陳興渝, 顧然, 高志鵬 申請人:北京郵電大學