技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)探測(cè)技術(shù)領(lǐng)域，尤其涉及一種用于計(jì)算網(wǎng)絡(luò)丟包率的探測(cè)方法。

背景技術(shù)

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

精確的丟包率監(jiān)測(cè)系統(tǒng)能夠在數(shù)秒內(nèi)探出路徑中斷和性能降低等現(xiàn)象。這些系統(tǒng)促進(jìn)了分布式系統(tǒng)(例如，VPN(Virtual?Private?Network，虛擬專用網(wǎng)絡(luò))和內(nèi)容分發(fā)網(wǎng)絡(luò))的管理。同時(shí)它們還有利于構(gòu)建適用于覆蓋網(wǎng)絡(luò)的應(yīng)用，例如流媒體框架。

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

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

對(duì)于上述技術(shù)問題的解決方案，有如下相關(guān)技術(shù)：

技術(shù)方案1：申請(qǐng)?zhí)枮?00810115485.3的中國(guó)專利申請(qǐng)公開了一種基于內(nèi)部監(jiān)測(cè)器的鏈路丟包率的推測(cè)方法，該方法在初始邏輯拓?fù)錁鋬?nèi)部放置監(jiān)測(cè)器，并收集初始邏輯樹的所有觀察數(shù)據(jù)，然后建立每顆子樹對(duì)應(yīng)的葉子節(jié)點(diǎn)的丟包序列，從而推測(cè)出它內(nèi)部每條鏈路的丟包率。該發(fā)明具有低復(fù)雜度、計(jì)算出的丟包率更接近于真實(shí)丟包率的優(yōu)點(diǎn)。

技術(shù)方案2：申請(qǐng)?zhí)枮?00810210890.3的中國(guó)專利申請(qǐng)公開了一種基于鏈路層發(fā)現(xiàn)協(xié)議進(jìn)行鏈路質(zhì)量檢測(cè)的方法及系統(tǒng)，網(wǎng)絡(luò)設(shè)備以單位時(shí)間T1為周期，采集各LLDP信宿端口在單位時(shí)間T1內(nèi)收到的鏈路層發(fā)現(xiàn)協(xié)議LLDP數(shù)據(jù)包數(shù)M1，并在管理信息庫MIB保存當(dāng)前采集的各LLDP信宿端口的LLDP數(shù)據(jù)包數(shù)M1；網(wǎng)管管理系統(tǒng)對(duì)每一待檢測(cè)鏈路進(jìn)行質(zhì)量檢測(cè)時(shí)，從該鏈路的目的端口所在網(wǎng)絡(luò)設(shè)備的MIB獲取當(dāng)前采集的該目的端口在單位時(shí)間T1內(nèi)收到的LLDP數(shù)據(jù)包數(shù)M1的信息，并得到該鏈路的源端口在單位時(shí)間T1內(nèi)發(fā)送的LLDP數(shù)據(jù)包數(shù)M2，計(jì)算出該鏈路當(dāng)前的丟包率H＝(1-M1/M2)×100％、該發(fā)明無需消耗額外資源且易于實(shí)現(xiàn)。

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

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

由此可見，目前存在大量的端到端丟包率的測(cè)量方案。通過端到端的測(cè)量來推測(cè)因特網(wǎng)鏈路的性能參數(shù)稱為網(wǎng)絡(luò)的層析成像。端到端的測(cè)量結(jié)果和鏈路性能參數(shù)無論是線性關(guān)系或者布爾運(yùn)算都可形成一個(gè)方程組。可以解這個(gè)方程組，然后得到需要的鏈路性能參數(shù)。然而現(xiàn)有的方法要么不能得到唯一解，要么就是由于在求解過程中，鏈路顆粒度劃分不夠精細(xì)，導(dǎo)致結(jié)果不夠精確。

下面具體評(píng)述上述現(xiàn)有技術(shù)的缺陷：