[發明專利]用于計算網絡丟包率的探測方法

有效

• 申請號: 201110067047.6
• 申請日: 2011-03-18
• 公開（公告）號: CN102684825A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 林巍;張杰;劉彬;張龍;鄭珊;謝丹
• 申請（專利權）人: 北京市天元網絡技術股份有限公司
• 主分類號: H04L1/00
• 分類號: H04L1/00;H04L12/24
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩

技術領域

本發明涉及網絡探測技術領域，尤其涉及一種用于計算網絡丟包率的探測方法。

背景技術

快速膨脹的因特網體系結構使在核心網部署創新性的技術異常困難。這也促使眾多的學者投入了覆蓋網絡和P2P(peer-to-peer，點對點)系統的研究，比如覆蓋網絡的選路和定位、應用層多播和P2P文件共享等。這些系統可以靈活地選擇它們的通信路徑和目的終端，這主要有利于端到端的網絡評估(比如計算時延和丟包率)。

精確的丟包率監測系統能夠在數秒內探出路徑中斷和性能降低等現象。這些系統促進了分布式系統(例如，VPN(Virtual?Private?Network，虛擬專用網絡)和內容分發網絡)的管理。同時它們還有利于構建適用于覆蓋網絡的應用，例如流媒體框架。

如果擁有一個精確計算丟包率的監測系統，并且這個系統的部署是逐步加入的，這對網絡測量工作來說是非常有利的。然而現有的網絡距離測量系統不能滿足這樣的要求。現有的網絡測量系統分為兩類：一類是一般的測量系統，一類是只測量時延的系統。前者系統能夠測量網絡很多性能，但是當有n個終端時，需要O(n²)的測量復雜度。而后者系統一方面是測量結果不夠精確；另一方面，這個時延測量系統即使可以測量到結果，依然不能提供精確的通過率和失敗率比值的推測值。

在具有n個終端的覆蓋網絡中，若定義選路路徑為一對終端間的路徑，IP鏈路為路由之間的鏈路，路徑就是一連串的鏈路組合。那么在n個終端間就存在著O(n²)數量級數目的路徑，O(n²)表示n²數量級的數值。而現有要解決的技術問題是：希望監測一個最小的路徑子集，進而能夠推測出余下路徑的丟包率和時延。

對于上述技術問題的解決方案，有如下相關技術：

技術方案1：申請號為200810115485.3的中國專利申請公開了一種基于內部監測器的鏈路丟包率的推測方法，該方法在初始邏輯拓撲樹內部放置監測器，并收集初始邏輯樹的所有觀察數據，然后建立每顆子樹對應的葉子節點的丟包序列，從而推測出它內部每條鏈路的丟包率。該發明具有低復雜度、計算出的丟包率更接近于真實丟包率的優點。

技術方案2：申請號為200810210890.3的中國專利申請公開了一種基于鏈路層發現協議進行鏈路質量檢測的方法及系統，網絡設備以單位時間T1為周期，采集各LLDP信宿端口在單位時間T1內收到的鏈路層發現協議LLDP數據包數M1，并在管理信息庫MIB保存當前采集的各LLDP信宿端口的LLDP數據包數M1；網管管理系統對每一待檢測鏈路進行質量檢測時，從該鏈路的目的端口所在網絡設備的MIB獲取當前采集的該目的端口在單位時間T1內收到的LLDP數據包數M1的信息，并得到該鏈路的源端口在單位時間T1內發送的LLDP數據包數M2，計算出該鏈路當前的丟包率H＝(1-M1/M2)×100％、該發明無需消耗額外資源且易于實現。

文獻方案1：《An?algebraic?approach?to?practical?and?scalable?overlay?network?monitoring》，該文獻是一種監測覆蓋網絡的實用可測量代數主動探測算法。該算法只測量其中一小部分路徑，然后使用這些收集的路徑丟包測量結果來推測剩下的路徑丟包率。假設網絡中有m條鏈路，現在通過計算收集到的m條線性獨立的路徑的丟包率，解一組m個路徑和丟包率關系的等式。一旦線性獨立的鏈路丟包率已知，就可以用來推測所有的n條路徑精確的丟包率，從而檢測出哪些路徑出現異常。

文獻方案2：《Scalable?deterministic?overlay?network?diagnosis》，該文獻解釋很多技術方案中，不能獲得唯一解的原因。其原因有二：一是只有使用無窮多個探針才能達到100％的健壯性；二是假定在理想的多播環境下，這些系統通過一些探針才能獲得高概率的估算結果。由此提出根據網絡中鏈路的狀態、特性將路徑細顆粒化。比如，可以將一些特性，狀態完全一致的鏈路合并。這樣能處理在計算中出現的鏈路未標明的情況。

由此可見，目前存在大量的端到端丟包率的測量方案。通過端到端的測量來推測因特網鏈路的性能參數稱為網絡的層析成像。端到端的測量結果和鏈路性能參數無論是線性關系或者布爾運算都可形成一個方程組。可以解這個方程組，然后得到需要的鏈路性能參數。然而現有的方法要么不能得到唯一解，要么就是由于在求解過程中，鏈路顆粒度劃分不夠精細，導致結果不夠精確。

下面具體評述上述現有技術的缺陷：