一種改進(jìn)的交叉組合包分類研究

本文提出一種改進(jìn)的基于交叉組合的包分類方法，基于對(duì)各維空間的無(wú)重疊的劃分基礎(chǔ)上進(jìn)行分類，采用等價(jià)區(qū)間的辦法來(lái)降低空間需求，該方法在提高處理速度的同時(shí)，所需存儲(chǔ)空間也降低了三分之二。使用自治系統(tǒng)網(wǎng)絡(luò)前綴產(chǎn)生模擬的分類數(shù)據(jù)庫(kù)，用非隨機(jī)方式及隨機(jī)方式產(chǎn)生不同大小的數(shù)據(jù)庫(kù)來(lái)對(duì)這個(gè)算法進(jìn)行了驗(yàn)證，證明了這個(gè)算法的有效性。

【關(guān)鍵詞】包分類 交叉組合 等價(jià)區(qū)間

數(shù)據(jù)包分類指根據(jù)數(shù)據(jù)包所攜帶的IP包頭、傳輸層頭部信息等查找預(yù)先設(shè)置的分類器，根據(jù)匹配規(guī)則來(lái)區(qū)分不同的數(shù)據(jù)包。包分類的結(jié)果決定了數(shù)據(jù)包應(yīng)得到什么樣的服務(wù)等級(jí)或者數(shù)據(jù)包屬于哪一個(gè)數(shù)據(jù)流，包轉(zhuǎn)發(fā)引擎根據(jù)分類的結(jié)果采用相應(yīng)的處理。在千兆網(wǎng)絡(luò)取證系統(tǒng)中，網(wǎng)絡(luò)取證機(jī)數(shù)據(jù)包的采集、分析及轉(zhuǎn)發(fā)是整個(gè)系統(tǒng)的核心，由于被取證機(jī)的網(wǎng)絡(luò)數(shù)據(jù)量異常龐大，這就要求網(wǎng)絡(luò)取證機(jī)對(duì)IP包進(jìn)行分類，根據(jù)分類結(jié)果完成對(duì)數(shù)據(jù)包的不同過(guò)濾處理，對(duì)感興趣的IP數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)存儲(chǔ)至取證存儲(chǔ)機(jī)，其它數(shù)據(jù)流進(jìn)行丟棄，再轉(zhuǎn)發(fā)至后端的取證分析機(jī)。

包分類的數(shù)據(jù)模型如下：一個(gè)數(shù)據(jù)包分類器包含M條規(guī)則RLj（1≤j≤M），如果對(duì)報(bào)文頭的S個(gè)字段進(jìn)行分類，規(guī)則RLj包含以下幾個(gè)部分：

（1） RLj[i]（1≤i≤K）：用于表示數(shù)據(jù)包頭的K個(gè)字段關(guān)系的正則表達(dá)式，它可以是特定的值、前綴表達(dá)式或是作用范圍等；

（2）優(yōu)先級(jí)Pri（RLj）：它定義了在分類器中規(guī)則的優(yōu)先級(jí)，用來(lái)決定當(dāng)數(shù)據(jù)包匹配多條規(guī)則，哪條規(guī)則有更高的優(yōu)先級(jí)。

（3）Act（Rj）：它表示當(dāng)規(guī)則匹配時(shí)，應(yīng)該執(zhí)行的動(dòng)作。

假定數(shù)據(jù)包P的包頭有K個(gè)字段（F1，F(xiàn)2，…，F(xiàn)k），K維的包分類器可以在所有匹配規(guī)則中尋找到優(yōu)先級(jí)最高的規(guī)則RLh，即：Pri（RLm）>Pri（RLi），1≤i≤M且i≠h。RLh被認(rèn)為是數(shù)據(jù)包P的最佳匹配規(guī)則。

在包分類問(wèn)題，主要在以下方向進(jìn)行研究：基于并行分解-綜合的算法。先將多維查找分解成并行的幾個(gè)查找，然后綜合它們的結(jié)果，最后得到匹配結(jié)果。例如BV，ABV等算法就是通過(guò)并行來(lái)查找各維的匹配情況，然后將各維的匹配結(jié)果通過(guò)規(guī)則映射的位圖“位與”得到匹配規(guī)則，這類算法的缺點(diǎn)是當(dāng)規(guī)則庫(kù)比較大時(shí)，得到的位圖會(huì)比較龐大。RFC算法借助于硬件流水線的方法，通過(guò)多階段的并行分解過(guò)程，可以達(dá)到很好的查找性能，但缺點(diǎn)是性能通常受到階段數(shù)和如何選取前一階段結(jié)果的策略等因素的制約。而交叉組合（Cross-Product）算法通過(guò)并行查找各維匹配的前綴，從它們的各種組合中選出合適的匹配規(guī)則，交叉組合法在查找的時(shí)間上有很大的優(yōu)勢(shì)。在K維的情況下，它只需要K次線性查找和一次查表的時(shí)間，時(shí)間復(fù)雜度為O（KN）。但它的空間復(fù)雜度卻是O（NK），在實(shí)際應(yīng)用中可能因交叉組合表太大，造成路由器的存儲(chǔ)體無(wú)法存儲(chǔ)的情況，能不能在提高查找的速度的同時(shí)，對(duì)空間進(jìn)行壓縮呢？以下提出了一種改進(jìn)的交叉組合算法。

1 改進(jìn)的交叉組合算法

對(duì)于D維的情況，交叉組合需要進(jìn)行D次的線性查找。由于地址范圍相互之間可能重疊的原因，只能順序查找方法，而不能采用快速的一維查找方法；每一維同一個(gè)IP包地址可能與幾個(gè)部分同時(shí)匹配，所以可能匹配多條規(guī)則，需要從多條規(guī)則中尋找出最高優(yōu)先級(jí)的規(guī)則。因此這一查找的效率并不是很高。表1是一個(gè)分類規(guī)則集的示例，對(duì)規(guī)則集C中地址S，T進(jìn)行排序，產(chǎn)生交叉組合表如表2所示。

當(dāng)使用交叉組合法來(lái)查找點(diǎn)P（0110，1000）時(shí)，則需要先對(duì)S進(jìn)行順序查找，得到匹配的S為{01*，011*，*}，再對(duì)T進(jìn)行順序查找，得到匹配的T為{10*，*}，再查表2，可得到6條匹配規(guī)則{R3，R4，R5，R6}，找出其中優(yōu)先級(jí)最高的規(guī)則R3（假設(shè)以序號(hào)前后做為優(yōu)先級(jí)的高低），以R3為最佳匹配規(guī)則。

以上過(guò)程可以看出，由于在每一維（S，T）中，規(guī)則所定義的范圍相互之間有沖突，會(huì)有重疊區(qū)域，這樣在各維的查找結(jié)果會(huì)存在多個(gè)匹配的前綴。

圖1給出規(guī)則庫(kù)的交叉組合區(qū)域圖，R3、R4、R5和R6有共同的相交區(qū)域。當(dāng)尋找H點(diǎn)的匹配規(guī)則時(shí)，有4條規(guī)則都匹配，由于R6與其它區(qū)域都相交，故任一次匹配查找都會(huì)找到R6，當(dāng)某個(gè)點(diǎn)與其它規(guī)則（R1-R5）相匹配，必然與R6相匹配。

為了去掉這種區(qū)域的重疊，可以嘗試換一種分段方法，將圖1按圖2進(jìn)行分段，在X軸方向劃分4個(gè)區(qū)間：X1、X2、X3、X4；在Y軸劃分5個(gè)區(qū)間：Y1、Y2、Y3、Y4、Y5。這樣就得到了20個(gè)劃分區(qū)域，并且這些區(qū)域互不相交。每個(gè)區(qū)域內(nèi)的點(diǎn)要么全部與規(guī)則R相匹配，要么全部與規(guī)則R不匹配。如果出現(xiàn)匹配多條規(guī)則的情況，由于區(qū)域內(nèi)的各個(gè)點(diǎn)具有相同的性質(zhì)，它們具有相同的最佳匹配規(guī)則。因此可以在建立查找表時(shí)先計(jì)算每個(gè)區(qū)域的最佳匹配規(guī)則，存儲(chǔ)時(shí)就只存儲(chǔ)最佳匹配規(guī)則即可。

2 實(shí)驗(yàn)分析

我們模擬一些規(guī)則數(shù)據(jù)庫(kù)對(duì)本文的算法進(jìn)行測(cè)試。交叉組合算法在最壞情況下，它的查找時(shí)間為O（KlogN），一般認(rèn)為這種查找時(shí)間是很快的了。但它的空間復(fù)雜度達(dá)到了O（N2），因此，我們主要在存儲(chǔ)空間的占用方面加以模擬。我們假設(shè)有兩個(gè)自治系統(tǒng)AS-A和AS-B，它們之間的邊界路由器直接相連的，每個(gè)自治系統(tǒng)都有一定數(shù)量的前綴地址。我們模擬在自治系統(tǒng)的邊界路由器中對(duì)數(shù)據(jù)包的分類，我們將一個(gè)自治系統(tǒng)的前綴地址與另一個(gè)自治系統(tǒng)的前綴地址交叉組合，并在路由器中定義從一個(gè)自治系統(tǒng)到另一個(gè)自治系統(tǒng)的包的規(guī)則。例如，假設(shè)自治系統(tǒng)1有30個(gè)前綴，自治系統(tǒng)2有20個(gè)前綴，交叉組合就可得到了一個(gè)600條規(guī)則的數(shù)據(jù)庫(kù)。

我們所有的規(guī)則數(shù)量雖然很多，但是各規(guī)則的動(dòng)作種類并不多，在實(shí)驗(yàn)中我們假設(shè)每個(gè)規(guī)則庫(kù)的動(dòng)作種類只有其中規(guī)則數(shù)量的3%。例如對(duì)于一個(gè)有1000條規(guī)則的數(shù)據(jù)庫(kù)來(lái)說(shuō)，只有30個(gè)不同的動(dòng)作，等價(jià)類合并實(shí)驗(yàn)結(jié)果如表3所示。

由表3可以看出：

（1）基于本文所提出的交叉組合法，在每一維的分段比以前的方法的分段增加了許多。這是因?yàn)檫@個(gè)算法在最壞情況下的分段數(shù)為（2N+1）*（2N+1），而原方法在最壞情況下分段數(shù)為N*N。

（2）利用合并等價(jià)類的方法，有效地壓縮了交叉組合表的大小，壓縮率達(dá)到了1/3。

（3）對(duì)于前綴形式的目的地址和源地址，按等價(jià)類的方法合并后，每一維的分段合并后不超過(guò)N+1個(gè)等價(jià)類。

總之，對(duì)于規(guī)則數(shù)據(jù)庫(kù)，經(jīng)過(guò)合并等價(jià)類后，交叉組合表已經(jīng)很小了，其中的冗余度已經(jīng)不大了，例如對(duì)于有5000條規(guī)則的數(shù)據(jù)庫(kù)，用原方法其交叉組合表只有5000項(xiàng)，用本文的方法也只有5151項(xiàng)，所以在這種情況下，是基本不用壓縮的。本文提出的方法的意義在于提高了搜索的速度。

3 結(jié)語(yǔ)

針對(duì)交叉組合法速度快，但對(duì)存儲(chǔ)空間的需求大的問(wèn)題，本文提出了對(duì)交叉組合法進(jìn)行改進(jìn)的方法。第一是采用無(wú)重疊區(qū)域的交叉組合法。將每一維地址分為若干類，然后交叉組合，由這種分類方法分出的各個(gè)類，無(wú)論是在一維還是二維上，它都是有重疊的，無(wú)法采用快速的查找方法。本文采用的基于各維對(duì)空間的無(wú)重疊的劃分的基礎(chǔ)上的分類，從而在每一維的查找上可以使用較快的算法，提高了搜索的速度，降低了時(shí)間復(fù)雜度，由O（KN）下降到了O（KlogN），但也加大了空間需求。第二個(gè)方面采用等價(jià)區(qū)間的辦法來(lái)降低空間需求。對(duì)于具有N條規(guī)則的規(guī)則數(shù)據(jù)庫(kù)來(lái)說(shuō)，本文證明了：通過(guò)等價(jià)區(qū)間合并方法，每一維的分類數(shù)不大于N+1個(gè)，其空間復(fù)雜度在O（N2）。該方法在提高處理速度的同時(shí)，還成倍地降低了對(duì)存儲(chǔ)空間的要求。

參考文獻(xiàn)

[1]劉震宇，李衛(wèi)軍，賴粵.基于網(wǎng)絡(luò)處理器的并行包分類方法[J].計(jì)算機(jī)應(yīng)用.2010，30（02）：306-315.

[2]曹婕，陳兵.一種內(nèi)存優(yōu)化的RFC包分類算法Merge_RFC[J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（04）：865-868.

[3]亓亞烜，李軍.高性能網(wǎng)包分類理論與算法綜述[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（02）：408-421.

作者簡(jiǎn)介

李戈（1979-），女，河南省內(nèi)鄉(xiāng)縣人。碩士研究生。講師。主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)信息安全，智能信息處理。

作者單位

河南水利與環(huán)境職業(yè)學(xué)院機(jī)電與信息工程系 河南省鄭州市 450000