[發(fā)明專利]一種網(wǎng)絡(luò)流量監(jiān)測方法和裝置

無效

• 申請?zhí)枺?/td>: 201010113469.8
• 申請日: 2010-02-25
• 公開（公告）號: CN102170373A
• 公開（公告）日: 2011-08-31
• 發(fā)明（設(shè)計）人: 周曄;俞鋼;王華;范靜;詹海;鄭文蘊
• 申請（專利權(quán)）人: 國信朗訊科技網(wǎng)絡(luò)技術(shù)有限公司
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/56
• 代理公司: 上海專利商標事務(wù)所有限公司 31100
• 代理人: 陳亮

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

本發(fā)明涉及IP網(wǎng)絡(luò)流量監(jiān)測和分析技術(shù)，尤其涉及對網(wǎng)絡(luò)中各網(wǎng)址的流量進行排序的技術(shù)。

背景技術(shù)

包頭采樣是IP骨干網(wǎng)主要的流量監(jiān)控技術(shù)之一，該技術(shù)是一種可操作性強、性價比好的技術(shù)。IETF針對這一應(yīng)用專門推出了IPFIX標準，但由于流量采集數(shù)據(jù)量一般都很大，加上網(wǎng)絡(luò)流量監(jiān)控的時效性要求比較高，所以采用軟件實現(xiàn)的性能問題比較突出，主要體現(xiàn)在采集數(shù)據(jù)的緩存和快速訪問、原始數(shù)據(jù)統(tǒng)計分析時的TOP?N(即：N個最大值或最小值)排序這兩個方面。

從各種全排序算法的原理可知，冒泡排序、堆排序、直接選擇排序可以在不完成全部排序的情況下得到TOP?N個最大(或最小)值；但由于冒泡法對于一個隨機數(shù)列的排序效率較低，所以針對堆排序、直接選擇排序來改進TOP?N排序技術(shù)。另外，直接插入排序雖然也需要在完成全部排序的情況下才能得到TOP?N個最大(最小)值，但如果對其算法作一下改進，同樣可以滿足要求。

在IP網(wǎng)絡(luò)流量監(jiān)測中，通常需要了解互聯(lián)網(wǎng)應(yīng)用、目的網(wǎng)站、源IP地址、網(wǎng)絡(luò)協(xié)議等等各個維度的流量統(tǒng)計狀況。舉例來說，通常需要了解在網(wǎng)絡(luò)中的流量分布來自哪些IP地址(源IP地址)，去向哪些IP地址(目的IP地址)，各個源IP地址或目的IP地址的流量分布情況和排名情況。但是IP地址的數(shù)量最大可達到2³²個，所以對所有IP地址進行流量進行排名是不現(xiàn)實的，而且在大多數(shù)情況下，只需要了解對網(wǎng)絡(luò)影響最大的一批IP地址，即網(wǎng)絡(luò)流量排名比較靠前的IP地址，這就是通常所說的TOP?N排名，N值通常在10～100之間，再大或再小都失去了實際應(yīng)用意義。

在計算機算法中，傳統(tǒng)的各類排序算法理論上也可以滿足這一網(wǎng)絡(luò)流量統(tǒng)計的這一需求，但是在實際使用中存在著很大的性能缺陷，主要原因是傳統(tǒng)排序算法是全排序算法。在IP地址的流量監(jiān)控中，傳統(tǒng)的全排序算法意味著要對網(wǎng)絡(luò)中數(shù)量極其龐大的IP地址產(chǎn)生的流量一一排序，而其實需要關(guān)注的僅僅是其中很小的流量排名前N的IP地址，但是對于N位之后的大量數(shù)據(jù)進行排序其實根本沒必要，帶來的結(jié)果是白白耗費大量的寶貴時間。

發(fā)明內(nèi)容

本發(fā)明的目的在于解決上述問題，提供了一種網(wǎng)絡(luò)流量監(jiān)測方法，提高了網(wǎng)絡(luò)流量原始數(shù)據(jù)統(tǒng)計分析在時效性上的效率。

本發(fā)明的另一目的在于提供了一種網(wǎng)絡(luò)流量監(jiān)測裝置。

本發(fā)明的技術(shù)方案為：本發(fā)明揭示了一種網(wǎng)絡(luò)流量監(jiān)測方法，對網(wǎng)絡(luò)中前N個流量最大的網(wǎng)址進行排序，其中N是自然數(shù)，該監(jiān)測方法包括：

將網(wǎng)絡(luò)中任意N個網(wǎng)址根據(jù)流量的大小進行排序，構(gòu)成當(dāng)前處理序列的初始序列；

將下一個未處理的網(wǎng)址和當(dāng)前處理序列中流量最小的網(wǎng)址進行流量大小的比較；

若該未處理的網(wǎng)址的流量小于該當(dāng)前處理序列中流量最小的網(wǎng)址的流量，則丟棄該未處理的網(wǎng)址，否則，將該未處理的網(wǎng)址根據(jù)其流量大小插入到該當(dāng)前處理序列中的合適位置，同時丟棄該流量最小的網(wǎng)址以更新該當(dāng)前處理序列，返回上一步驟直至所有網(wǎng)址都已處理。

根據(jù)本發(fā)明的網(wǎng)絡(luò)流量監(jiān)測方法的一實施例，N的取值范圍是10～100之間。

根據(jù)本發(fā)明的網(wǎng)絡(luò)流量監(jiān)測方法的一實施例，該任意N個網(wǎng)址是在網(wǎng)絡(luò)流量監(jiān)控過程中最初接收到的N個網(wǎng)址。

根據(jù)本發(fā)明的網(wǎng)絡(luò)流量監(jiān)測方法的一實施例，將未處理的網(wǎng)址根據(jù)其流量大小插入到該當(dāng)前處理序列中的合適位置是采用二分查找法。

本發(fā)明還揭示了一種網(wǎng)絡(luò)流量監(jiān)測裝置，對網(wǎng)絡(luò)中前N個流量最大的網(wǎng)址進行排序，其中N是自然數(shù)，該監(jiān)測裝置包括：

流量監(jiān)測模塊，監(jiān)測網(wǎng)絡(luò)中各網(wǎng)址的流量；

排序模塊，連接該流量監(jiān)測模塊，將網(wǎng)絡(luò)中任意N個網(wǎng)址根據(jù)流量的大小進行排序，構(gòu)成當(dāng)前處理序列的初始序列；

比較模塊，連接該排序模塊和該流量監(jiān)測模塊，將從該流量監(jiān)測模塊輸出的下一個未處理的網(wǎng)址和來自該排序模塊的當(dāng)前處理序列中流量最小的網(wǎng)址進行流量大小的比較；

序列更新模塊，其輸入端連接該比較模塊，輸出端連接該排序模塊，若該未處理的網(wǎng)址的流量小于該當(dāng)前處理序列中流量最小的網(wǎng)址的流量，則丟棄該未處理的網(wǎng)址，否則，將該未處理的網(wǎng)址根據(jù)其流量大小插入到該當(dāng)前處理序列中的合適位置，同時丟棄該流量最小的網(wǎng)址以更新該當(dāng)前處理序列；

其中該比較模塊和該序列更新模塊是反復(fù)運行的直至網(wǎng)絡(luò)中所有網(wǎng)址均已處理。

根據(jù)本發(fā)明的網(wǎng)絡(luò)流量監(jiān)測裝置的一實施例，N的取值范圍是10～100之間。

根據(jù)本發(fā)明的網(wǎng)絡(luò)流量監(jiān)測裝置的一實施例，該任意N個網(wǎng)址是在網(wǎng)絡(luò)流量監(jiān)控過程中最初接收到的N個網(wǎng)址。