[發(fā)明專利]一種多域網(wǎng)包分類方法

有效

• 申請?zhí)枺?/td>: 201110425385.2
• 申請日: 2011-12-16
• 公開（公告）號: CN102420831A
• 公開（公告）日: 2012-04-18
• 發(fā)明（設(shè)計(jì)）人: 王翔;亓亞烜;李軍
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L12/56
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩

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

本發(fā)明涉及網(wǎng)絡(luò)監(jiān)控技術(shù)領(lǐng)域，特別涉及一種多域網(wǎng)包分類方法。

背景技術(shù)

多域網(wǎng)包分類是網(wǎng)絡(luò)設(shè)備中的基本功能。其應(yīng)用方式是用戶根據(jù)具體分類需求，選擇網(wǎng)包包頭中的相關(guān)域(或維度)建立分類規(guī)則的集合；網(wǎng)絡(luò)設(shè)備通過檢查流經(jīng)自身網(wǎng)包中分類規(guī)則定義的相關(guān)域，判定網(wǎng)包匹配分類規(guī)則集合中的哪條規(guī)則，完成分類過程。多域網(wǎng)包分類問題本質(zhì)上是多維空間中的點(diǎn)定位問題：分類規(guī)則中的每個(gè)域的取值范圍張成了整個(gè)多維空間，每條分類規(guī)則對應(yīng)到整個(gè)多維空間中的一個(gè)子空間，每個(gè)待分類的網(wǎng)包包頭中的相關(guān)域的取值相當(dāng)于一個(gè)待定位的點(diǎn)，分類的過程等價(jià)于判定上述待定位的點(diǎn)屬于哪個(gè)子空間。

多域網(wǎng)包分類的實(shí)現(xiàn)方法直接影響了網(wǎng)絡(luò)設(shè)備的性能，因此，該問題在學(xué)術(shù)界和工業(yè)界一直備受關(guān)注。目前，高端策略路由器及防火墻等安全設(shè)備大多采用專用硬件方案來實(shí)現(xiàn)。基于硬件的實(shí)現(xiàn)方式能夠達(dá)到高分類速率，但是開發(fā)周期長、更新難度高。基于軟件的實(shí)現(xiàn)方式具有高靈活性，但是很難達(dá)到較高的處理性能。這些軟件的實(shí)現(xiàn)方式一般通過對算法的處理復(fù)雜度和占用空間進(jìn)行折中，來平衡算法的處理性能和靈活性。因此，很難保證算法具有確定性的分類速率和較小的空間占用。同時(shí)，大部分基于軟件的多域網(wǎng)包分類的實(shí)現(xiàn)方式，由于其數(shù)據(jù)結(jié)構(gòu)和處理過程的復(fù)雜性和不一致性，很難移植到硬件上進(jìn)行實(shí)現(xiàn)。

現(xiàn)有多域網(wǎng)包分類方法的軟件實(shí)現(xiàn)方式大多如下：根據(jù)分類規(guī)則的集合，預(yù)先建立決策樹類型的查找數(shù)據(jù)結(jié)構(gòu)；對網(wǎng)包的分類過程通過在決策樹中進(jìn)行查找來完成。決策樹中的根節(jié)點(diǎn)相當(dāng)于整個(gè)多維空間，決策樹中的每一級相當(dāng)于對多維空間在某一維度上進(jìn)行了一次切分，決策樹中的每一級上的多個(gè)節(jié)點(diǎn)相當(dāng)于對多維空間在某一維度上進(jìn)行了一次切分后產(chǎn)生的多個(gè)子空間。通過對多維空間進(jìn)行不斷地切分，每個(gè)子空間不斷縮小，直到?jīng)Q策樹上的所有葉子節(jié)點(diǎn)都只涵蓋分類規(guī)則中某一條特定規(guī)則時(shí)，決策樹構(gòu)建完成。網(wǎng)絡(luò)設(shè)備對網(wǎng)包進(jìn)行分類時(shí)，根據(jù)網(wǎng)包中分類規(guī)則定義的相關(guān)域上的取值，在決策樹中逐級進(jìn)行查找，直到葉子節(jié)點(diǎn)為止。

下表1描述了一個(gè)用戶定義的分類規(guī)則集合，該集合中的所有規(guī)則都基于兩個(gè)域(X和Y)進(jìn)行描述。圖1是對應(yīng)表1所述分類規(guī)則集合的幾何圖形表示。

表1分類規(guī)則集合表

圖2是對應(yīng)表1所述分類規(guī)則集合的決策樹類型的數(shù)據(jù)結(jié)構(gòu)表示。最下一行的節(jié)點(diǎn)為葉子節(jié)點(diǎn)；除葉子節(jié)點(diǎn)以外的節(jié)點(diǎn)為內(nèi)部節(jié)點(diǎn)(包括根節(jié)點(diǎn)和中間一行節(jié)點(diǎn))。每個(gè)節(jié)點(diǎn)內(nèi)部存儲如下信息：(1)該節(jié)點(diǎn)所代表的空間需要在哪一維度上進(jìn)行進(jìn)一步的切分；該切分把當(dāng)前空間分成多少個(gè)子空間(例如，node-0節(jié)點(diǎn)代表整個(gè)二維空間，cuts：Y-4表示對整個(gè)二維空間在Y維度上進(jìn)行進(jìn)一步切分，分成4份)。(2)切分后所產(chǎn)生的子空間所對應(yīng)節(jié)點(diǎn)的索引信息(例如，node-0節(jié)點(diǎn)中以數(shù)組的形式存儲其子節(jié)點(diǎn)的索引信息，數(shù)組中的每個(gè)元素是子節(jié)點(diǎn)的指針/地址)。從該數(shù)據(jù)結(jié)構(gòu)中我們可以看出兩個(gè)問題：(1)每個(gè)節(jié)點(diǎn)存儲的信息不具有統(tǒng)一的格式，這樣會(huì)導(dǎo)致在后續(xù)的查找過程中需要針對每個(gè)節(jié)點(diǎn)進(jìn)行特殊的處理(例如，node-2和node-3，它們進(jìn)行進(jìn)一步切分的份數(shù)不相同，所需要存儲的子節(jié)點(diǎn)的索引信息也不相同：node-2需要存儲4個(gè)子節(jié)點(diǎn)的索引信息，node-3需要存儲2個(gè)子節(jié)點(diǎn)的索引信息)。(2)每個(gè)節(jié)點(diǎn)存儲的信息量太大，具有較多的冗余，這樣會(huì)導(dǎo)致查找數(shù)據(jù)結(jié)構(gòu)占用的空間較大，很難適應(yīng)分類規(guī)則集合中規(guī)則的數(shù)量過多的情況(例如，每個(gè)節(jié)點(diǎn)中為了存儲子節(jié)點(diǎn)的索引信息，使用了指針數(shù)組；每個(gè)指針在32位系統(tǒng)下占用4個(gè)字節(jié)，整個(gè)決策樹中所有節(jié)點(diǎn)占用的空間加起來相當(dāng)可觀)。