一種基于域沖突空間的分布式報(bào)文分類(lèi)算法

摘 要:隨著網(wǎng)絡(luò)傳輸速率的不斷提高，分布式報(bào)文分類(lèi)算法以其快速高效的特點(diǎn)越來(lái)越受到業(yè)界的關(guān)注，但卻普遍存在內(nèi)存消耗過(guò)高的問(wèn)題。針對(duì)這一問(wèn)題提出了基于域沖突空間的多標(biāo)簽樹(shù)算法(MLT-FCS)，將各域規(guī)則劃分為不同的沖突區(qū)，并為沖突區(qū)和區(qū)內(nèi)元素分配各自的標(biāo)簽，然后在此基礎(chǔ)上設(shè)計(jì)出兩級(jí)查詢(xún)機(jī)制以減少待查規(guī)則的數(shù)目，充分利用硬件的并行處理和流水線操作特性，提出了第二級(jí)查詢(xún)的多標(biāo)簽樹(shù)算法。分析及仿真表明，MLT-FCS在實(shí)現(xiàn)高速分類(lèi)(OC-192)的同時(shí)減少了存儲(chǔ)開(kāi)銷(xiāo)，并為規(guī)則庫(kù)規(guī)模的擴(kuò)展和規(guī)則維數(shù)的擴(kuò)展提供了較好的支持。

關(guān)鍵詞:報(bào)文分類(lèi); 分布式; 域沖突空間; 標(biāo)簽樹(shù)

中圖分類(lèi)號(hào):TP393文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2009)09-3266-04

doi:10.3969/j.issn.1001-3695.2009.09.018

Distributed packet classification algorithm based on field conflict space

ZHOU Jing-di， CHENG Dong-nian， LIU Qin-rang

(National Digital Switching System Engineering Technology RD Center， Zhengzhou 450002， China)

Abstract:As the increasing speed of network transmission， fast and efficient distributed packet classification algorithms get more attention than ever before， however they generally consumes a large amount of memory. In order to overcome this problem， this paper proposed a novel algorithm called multiple label trees based on field conflict space (MLT-FCS). MLT-FCS divided every field’s rules into different conflict region， and then allocated labels to conflict regions and in-region elements respectively. At last， designed a two-level search mechanism for classification to reduce the number of pending rules， sufficiently utilized and the pipeline and parallel operation of hardware to propose a multiple label trees algorithm in level-2. Analysis and simulations indicate that MLT-FCS not only achieves high-speed classification (OC-192) and improves the storage efficiency， but also supports the expanding of filter sets scale and the increase of filter dimensions well.

Key words:packet classification; distributed; field conflict space; label trees

0 引言

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，特別是G比特和T比特網(wǎng)絡(luò)技術(shù)的出現(xiàn)，導(dǎo)致鏈路帶寬的快速增長(zhǎng)和網(wǎng)絡(luò)流量的急劇膨脹，給網(wǎng)絡(luò)的研究和使用帶來(lái)了巨大的挑戰(zhàn)和許多有待解決的問(wèn)題;另一方面，未來(lái)網(wǎng)絡(luò)的發(fā)展趨勢(shì)需要為用戶(hù)提供更好的服務(wù)質(zhì)量，如區(qū)分服務(wù)、虛擬專(zhuān)網(wǎng)VPN、基于策略的路由、防火墻等提高服務(wù)質(zhì)量的機(jī)制都是基于報(bào)文分類(lèi)技術(shù)之上的。

為實(shí)現(xiàn)高效的報(bào)文分類(lèi)，許多研究人員將目光放在了硬件的并行處理能力上，研究報(bào)文的分布式處理算法。所謂分布式處理，即分別對(duì)報(bào)文的各個(gè)域進(jìn)行處理，然后逐步聚合直至得到最終結(jié)果。華盛頓大學(xué)的Srinivasan等人[1]提出一種基于緩存策略的分布式算法Crossproducting。該算法對(duì)報(bào)文頭部的各個(gè)域分別作最優(yōu)匹配，并把各域匹配的結(jié)果級(jí)聯(lián)起來(lái)形成Crossproduct，通過(guò)一次哈希查表得到最佳匹配規(guī)則。Crossproducting速度很快，但存在內(nèi)存爆炸問(wèn)題。隨后來(lái)自斯坦福大學(xué)計(jì)算機(jī)系統(tǒng)實(shí)驗(yàn)室的Gupta等人[2]提出一種基于硬件實(shí)現(xiàn)的分布式算法RFC。該算法的主要思想是將報(bào)文頭的S bit映射到T bit的classID (T=log N且T<

綜上所述，分布式報(bào)文分類(lèi)算法普遍存在內(nèi)存消耗過(guò)大的問(wèn)題，使得該類(lèi)算法的應(yīng)用場(chǎng)景大大受限。隨著互聯(lián)網(wǎng)業(yè)務(wù)量的激增，分類(lèi)規(guī)則庫(kù)的規(guī)模在不斷擴(kuò)大，好的分類(lèi)算法應(yīng)該在規(guī)則數(shù)目增多時(shí)分類(lèi)處理的性能不會(huì)驟然下降[4]。所以，如何充分利用分布式報(bào)文分類(lèi)算法處理速度快、規(guī)則維數(shù)可擴(kuò)展性好等優(yōu)勢(shì)并盡可能降低內(nèi)存消耗，已經(jīng)成為目前分布式分類(lèi)算法研究的一個(gè)熱點(diǎn)。

本文從降低分布式報(bào)文分類(lèi)算法內(nèi)存消耗的目的出發(fā)，在給出域沖突空間概念的基礎(chǔ)上提出了基于域沖突空間的多標(biāo)簽樹(shù)算法(MLT-FCS)，將各個(gè)域的規(guī)則劃歸為不同的沖突區(qū)，并以此為基礎(chǔ)建立沖突空間查詢(xún)表;最后，為每個(gè)沖突區(qū)標(biāo)簽向量建立一個(gè)多標(biāo)簽樹(shù)查詢(xún)結(jié)構(gòu)以完成規(guī)則匹配。分析及仿真結(jié)果表明，MLT-FCS算法不僅保持了分布式算法良好的時(shí)間性能以及規(guī)則維數(shù)的可擴(kuò)展性，而且減少了內(nèi)存開(kāi)銷(xiāo)、提高了規(guī)模可擴(kuò)展性，能夠應(yīng)用于大型規(guī)則庫(kù)。

1 域沖突空間

分布式報(bào)文分類(lèi)算法通常利用硬件并行處理能力對(duì)報(bào)文各個(gè)字段作并行獨(dú)立查找，然后進(jìn)行分域查找結(jié)果的聚合。因?yàn)榉钟虿檎視?huì)在每一個(gè)字段得到若干匹配結(jié)果，所以該類(lèi)算法的關(guān)鍵在于采用什么樣的聚合方式得到最佳匹配規(guī)則。現(xiàn)有算法大都采用兩種聚合方式，即直接聚合和多級(jí)聚合。如果采用直接聚合，中間結(jié)果只有一個(gè)，但是中間結(jié)果與規(guī)則的對(duì)應(yīng)表需要占據(jù)龐大的內(nèi)存空間;如果采用多級(jí)聚合，雖然表項(xiàng)查詢(xún)的內(nèi)存需求比前者小很多，但卻需要大量緩存來(lái)存儲(chǔ)中間結(jié)果。

為降低聚合的內(nèi)存消耗，本文首先提出了域沖突空間的概念，并結(jié)合標(biāo)簽換規(guī)則的思想將分類(lèi)過(guò)程中對(duì)規(guī)則的處理變?yōu)閷?duì)標(biāo)簽的處理，然后以此為基礎(chǔ)將查詢(xún)過(guò)程劃分為兩個(gè)層次，使得中間處理結(jié)果只有兩個(gè)，進(jìn)一步降低了內(nèi)存消耗。下面首先給出域沖突空間的相關(guān)定義:

定義1 將包含N條前綴表示規(guī)則的d維規(guī)則庫(kù)按域劃分為d個(gè)部分，然后按域歸并相同的分域規(guī)則，得到d個(gè)規(guī)則集合Fi={fi1， fi2，…， fiNi} (i=1，2，…，d)。Fi包含了原規(guī)則庫(kù)第i域中所有不重復(fù)的規(guī)則，稱(chēng)為域規(guī)則集。

定義2 假設(shè)fip、 fiq屬于同一域規(guī)則集Fi。其中p， q∈{1，2，…，Ni}，如果fip是fiq的前綴或者fiq是fip的前綴，那么稱(chēng)兩者沖突。

定義3 對(duì)于fij∈Fi (j=1，2，…， Ni)，如果域規(guī)則集Fi中沒(méi)有一個(gè)規(guī)則是fij的前綴，稱(chēng)fij是元規(guī)則;元規(guī)則用yij′表示。其中i表示第i域，j′表示第i域中第j′條元規(guī)則。

定義4 對(duì)于某元規(guī)則yij′，如果它是域規(guī)則集Fi中某規(guī)則fij的前綴，那么稱(chēng)fij隸屬于yij′，表示為fijyij′。

定義5 定義一個(gè)集合Yij′，令它包含元規(guī)則yij′以及域規(guī)則集Fi中所有隸屬于yij′的規(guī)則，稱(chēng)其為一個(gè)沖突區(qū)。將Yij′中所有元素按優(yōu)先級(jí)從高到低排列后表示為Yij′ ={fij′1， fij′2，…}。

定義6 提取出域規(guī)則集Fi中所有的元規(guī)則，并按優(yōu)先級(jí)從高到低排列得到{yi1， yi2，…}，并用Yi表示，稱(chēng)其為第i域的沖突空間，且每一個(gè)元規(guī)則yij′指向一個(gè)沖突區(qū)Yij′。

根據(jù)元規(guī)則的定義可以知道，不同的元規(guī)則間是不存在包含關(guān)系的，否則它們存在沖突，應(yīng)歸并到同一個(gè)沖突區(qū)。另外，域沖突空間是基于前綴規(guī)則生成的，所以在處理范圍表示的規(guī)則庫(kù)時(shí)必須對(duì)原始規(guī)則作預(yù)處理，將其轉(zhuǎn)換為前綴表示。已有的范圍前綴轉(zhuǎn)換方法很多且不是本文研究的重點(diǎn)，筆者選擇一種開(kāi)銷(xiāo)較小的首尾端增補(bǔ)法[5]，不作贅述。

2 基于標(biāo)簽的數(shù)據(jù)結(jié)構(gòu)

為降低分布式算法的內(nèi)存消耗，本文利用標(biāo)簽換規(guī)則的思想用不同屬性的標(biāo)簽表示規(guī)則。根據(jù)定義，域沖突空間Yi (i=1，2，…，d)中所有的元規(guī)則{yi1， yi2，…}是按優(yōu)先級(jí)從高到低排列(前綴越長(zhǎng)優(yōu)先級(jí)越高)。首先為其分配標(biāo)簽(從1開(kāi)始)，優(yōu)先級(jí)越高的元規(guī)則標(biāo)簽值越小，令Cij表示第i域第j個(gè)沖突區(qū)的標(biāo)簽;最后用沖突區(qū)標(biāo)簽集合Ci表示第i域的沖突空間。同理，為各沖突區(qū)中的規(guī)則分配標(biāo)簽，標(biāo)簽值仍從1開(kāi)始;令Cijk表示第i域第j沖突區(qū)第k個(gè)標(biāo)簽，稱(chēng)其為內(nèi)標(biāo)簽。

在得到規(guī)則的標(biāo)簽表示形式后，本文設(shè)計(jì)出基于域沖突空間表和內(nèi)標(biāo)簽向量表的兩級(jí)查詢(xún)機(jī)制，將第一級(jí)查詢(xún)不中的報(bào)文直接按照默認(rèn)規(guī)則處理。而且由于各表的表項(xiàng)數(shù)有限，該機(jī)制進(jìn)一步減少了訪存次數(shù)，提高了算法速度。具體做法如下:

a)算法按照域沖突空間的定義并根據(jù)上述標(biāo)簽表示法得到兩種查詢(xún)表，一種是元規(guī)則與沖突區(qū)標(biāo)簽的對(duì)應(yīng)表Ti，另一種是各沖突區(qū)標(biāo)簽對(duì)應(yīng)的內(nèi)標(biāo)簽表Tij。其中i表示第i域，j表示第i域第j條元規(guī)則。表1所示的規(guī)則庫(kù)是經(jīng)過(guò)前綴化的三域規(guī)則庫(kù)，由它得到的各表項(xiàng)如圖1所示。

b)建立第一級(jí)查詢(xún)表，即沖突空間表Tconf。對(duì)于d維規(guī)則f={f1， f2，…， fd}，如果有f1y1j1， f2y2j2，…， fdydjd，則用向量(C1j1，C2j2，…，Cdjd)表示f在Tconf中的表項(xiàng)，稱(chēng)為沖突區(qū)標(biāo)簽向量。從查詢(xún)表的建立過(guò)程可以看出，一條規(guī)則必定對(duì)應(yīng)且只對(duì)應(yīng)Tconf中的一條表項(xiàng)，但是存在多條規(guī)則對(duì)應(yīng)同一表項(xiàng)的情況，所以必須有第二級(jí)查詢(xún)，這樣處理的好處是減少了待查規(guī)則的數(shù)目。

c)為T(mén)conf中每條表項(xiàng)建立一個(gè)第二級(jí)查詢(xún)表，即內(nèi)標(biāo)簽向量表T iconf，其中i表示Tconf中的第i條表項(xiàng)。對(duì)于d維規(guī)則f={f1， f2，…， fd}，如果有f1=f1j1k1， f2=f2j2k2，…， fd=fdjdkd，則用向量(C1j1k1，C2j2k2，…，Cdjdkd)表示f在Ticonf中的表項(xiàng)，稱(chēng)為內(nèi)標(biāo)簽向量。注意f1j1k1表示第1域第j1沖突區(qū)中第k1條規(guī)則。

d)利用Ticonf中的元素作為關(guān)鍵字可以直接索引到該元素對(duì)應(yīng)的規(guī)則。根據(jù)表1的規(guī)則庫(kù)得到的沖突空間表與內(nèi)標(biāo)簽向量表如圖2所示。

特別地，將各域的通配符看做一個(gè)特殊的沖突區(qū)，其成員只有通配符本身，并且令其優(yōu)先級(jí)最低。另外，由于協(xié)議域沒(méi)有范圍和前綴的概念，都是精確的協(xié)議號(hào)或通配符，在處理時(shí)將其視為特殊的范圍，對(duì)它的處理方式與范圍表示的域相同。

3 多標(biāo)簽樹(shù)查詢(xún)結(jié)構(gòu)

算法需要在第二級(jí)查詢(xún)時(shí)快速準(zhǔn)確地得到最優(yōu)匹配規(guī)則，因此提出了多標(biāo)簽樹(shù)查詢(xún)結(jié)構(gòu)，為每個(gè)內(nèi)標(biāo)簽向量表Ticonf建立一個(gè)這樣的結(jié)構(gòu)。

在各數(shù)據(jù)結(jié)構(gòu)確定之后，首先提取出Ticonf表第一域中所有不同的標(biāo)簽C1j11k11，C1j12k12，…，然后以每個(gè)標(biāo)簽作為一個(gè)根節(jié)點(diǎn)建立一棵標(biāo)簽樹(shù)。注意下標(biāo)1j11k11中，1表示第一域，j11表示第一域第j11個(gè)沖突區(qū)，k11表示該沖突區(qū)第k11個(gè)元素。

以標(biāo)簽C1j11k11為例，建立標(biāo)簽樹(shù)的具體方法是:以C1j11k11作為根節(jié)點(diǎn)，提取出Ticonf中所有包含C1j11k11的內(nèi)標(biāo)簽向量，然后提取出這些向量第二域所包含的所有不同標(biāo)簽作為C1j11k11的子節(jié)點(diǎn)，形成標(biāo)簽樹(shù)的第二層;接下來(lái)提取出Ticonf中所有同時(shí)包含C1j11k11和第二層某節(jié)點(diǎn)的內(nèi)標(biāo)簽向量，然后提取出這些向量第三域所包含的所有不同標(biāo)簽作為該節(jié)點(diǎn)的子節(jié)點(diǎn)，依此法為第二層的所有節(jié)點(diǎn)找到子節(jié)點(diǎn);最后根據(jù)上述方法建立標(biāo)簽樹(shù)的剩余各層，最終得到的標(biāo)簽樹(shù)共包含d層，第i層對(duì)應(yīng)第i域。根據(jù)圖2構(gòu)建出的多標(biāo)簽樹(shù)查詢(xún)結(jié)構(gòu)如圖3所示。

4 查詢(xún)過(guò)程

報(bào)文到達(dá)以后，按域并行查找得到報(bào)文各域?qū)?yīng)的元規(guī)則以及元規(guī)則對(duì)應(yīng)的沖突區(qū)標(biāo)簽;繼續(xù)查找沖突區(qū)得到報(bào)文各域?qū)?yīng)的最優(yōu)規(guī)則及其對(duì)應(yīng)的內(nèi)標(biāo)簽。需要指出的是，除了查詢(xún)結(jié)果不一樣外，這一過(guò)程與其他的分布式算法別無(wú)他樣。如果利用基于樹(shù)的LPM技術(shù)可將并行分域查找過(guò)程總的訪存次數(shù)控制在四次以?xún)?nèi)，內(nèi)存消耗可以控制在6 Byte/filter內(nèi)[3]。

將得到的沖突區(qū)標(biāo)簽組合成沖突區(qū)標(biāo)簽向量，并利用哈希函數(shù)將其映射到表Tconf進(jìn)行查詢(xún)。如果存在匹配項(xiàng)則進(jìn)行二級(jí)查詢(xún);否則按默認(rèn)規(guī)則對(duì)報(bào)文進(jìn)行處理。整體查詢(xún)過(guò)程如圖4所示。

在分析第二級(jí)查詢(xún)過(guò)程之前，先給出兩個(gè)定理及其證明。

定理1 沖突空間表Tconf中存在某待查報(bào)文的匹配項(xiàng)是規(guī)則庫(kù)中存在該報(bào)文匹配規(guī)則的必要條件。

證明 使用反證法證明。假設(shè)某報(bào)文P在Tconf中沒(méi)有匹配項(xiàng)而在規(guī)則庫(kù)中匹配上了一條規(guī)則f，令P通過(guò)分域獨(dú)立查找后得到的沖突區(qū)標(biāo)簽向量是(C1j11，C2j21，…，Cdjd1)，得到的內(nèi)標(biāo)簽向量是(C1j11k11，C2j21k21，…，Cdjd1kd1)，令f對(duì)應(yīng)的內(nèi)標(biāo)簽向量是(C1j12k12，C2j22k22，…，Cdjd2kd2);由于P與f匹配，C1j11k11與C1j12k12屬于同一沖突區(qū)，對(duì)應(yīng)同樣的沖突區(qū)標(biāo)簽C1j11。同理兩個(gè)內(nèi)標(biāo)簽向量的各個(gè)域都對(duì)應(yīng)同樣的沖突區(qū)標(biāo)簽，f對(duì)應(yīng)的沖突區(qū)標(biāo)簽向量就是(C1j11，C2j21，…，Cdjd1);按照數(shù)據(jù)結(jié)構(gòu)的構(gòu)建方式，所有規(guī)則都僅能在表Tconf中對(duì)應(yīng)惟一的表項(xiàng)，所以(C1j11，C2j21，…，Cdjd1)必定屬于表Tconf，這與P在表Tconf中找不到匹配項(xiàng)矛盾，即證。

定理2 如果規(guī)則庫(kù)中存在某待查報(bào)文的匹配規(guī)則，那么該報(bào)文在表Tconf中一定存在且只存在一個(gè)匹配表項(xiàng)。

證明 定理1已經(jīng)給出了滿足定理2條件的報(bào)文在表Tconf中的存在性，所以只需證明惟一性。同樣使用反證法進(jìn)行證明，首先假設(shè)某報(bào)文P在規(guī)則庫(kù)中匹配上了一條規(guī)則f且在表Tconf中有兩個(gè)匹配項(xiàng)。由于兩個(gè)沖突區(qū)標(biāo)簽向量至少在一個(gè)域上的標(biāo)簽值不一樣，即P在該域匹配上了兩個(gè)不同的元規(guī)則，說(shuō)明這兩個(gè)元規(guī)則存在包含關(guān)系，但這與元規(guī)則的定義相矛盾，即證。

由兩個(gè)定理可以知道，如果某待查報(bào)文在表Tconf中沒(méi)有匹配項(xiàng)，那么規(guī)則庫(kù)中一定不存在報(bào)文的匹配規(guī)則;反之，如果規(guī)則庫(kù)中存在某報(bào)文的匹配規(guī)則，那么該報(bào)文在表Tconf中一定存在惟一的匹配表項(xiàng)，這就需要進(jìn)行第二級(jí)查詢(xún)。

在使用硬件實(shí)現(xiàn)的前提下，報(bào)文的第二級(jí)查詢(xún)是在各標(biāo)簽樹(shù)中并行進(jìn)行:a)如果某標(biāo)簽樹(shù)根節(jié)點(diǎn)標(biāo)簽值小于待查報(bào)文第一域的內(nèi)標(biāo)簽值，那么直接停止在該標(biāo)簽樹(shù)的查詢(xún)，否則記錄下該根節(jié)點(diǎn)的標(biāo)簽值并繼續(xù)查詢(xún);b)在標(biāo)簽樹(shù)第二層中選擇標(biāo)簽值大于等于待查報(bào)文第二域的內(nèi)標(biāo)簽值的所有節(jié)點(diǎn)，記錄節(jié)點(diǎn)值后進(jìn)入下一層查詢(xún)，否則直接停止該標(biāo)簽樹(shù)的查詢(xún);經(jīng)過(guò)d層標(biāo)簽樹(shù)查詢(xún)后，將各標(biāo)簽樹(shù)搜索得到的所有標(biāo)簽向量送到優(yōu)先級(jí)判決模塊，最終輸出最優(yōu)匹配向量。如果沒(méi)有匹配向量輸出，則按照默認(rèn)規(guī)則對(duì)報(bào)文進(jìn)行處理。

另外，可以采用流水線方式將查詢(xún)過(guò)程的時(shí)間復(fù)雜度降到最低。由于所有標(biāo)簽樹(shù)都是d層，將標(biāo)簽樹(shù)同一層次的節(jié)點(diǎn)存放在獨(dú)立的內(nèi)存中，然后將標(biāo)簽樹(shù)的每一個(gè)層次作為流水結(jié)構(gòu)的一個(gè)階段。于是在標(biāo)簽樹(shù)上查找一次只相當(dāng)于一次訪存，整個(gè)多標(biāo)簽樹(shù)的查找過(guò)程只有并行流水查找加上一次優(yōu)先級(jí)判決，所以時(shí)間復(fù)雜度為O(1)。

最后用一個(gè)例子說(shuō)明報(bào)文的查找過(guò)程。以表1所示規(guī)則庫(kù)為例，設(shè)待查報(bào)文為P1={11011010，10111100，01011100}與P2={11010011，10100011，0101101}，查詢(xún)過(guò)程如圖5所示。經(jīng)第一級(jí)查詢(xún)后，得到P1和P2對(duì)應(yīng)的沖突區(qū)標(biāo)簽向量均為(1，1，2)，它們對(duì)應(yīng)的內(nèi)標(biāo)簽向量分別為(1，2，2)、(1，3，2);在第二級(jí)查詢(xún)中，P1命中的內(nèi)標(biāo)簽向量有(1，2，3)、(1，3，2)，最后選擇優(yōu)先級(jí)高的(1，2，3)作為最佳匹配向量，對(duì)應(yīng)的規(guī)則是(1101，1011，01);P2只命中一個(gè)內(nèi)標(biāo)簽向量是(1，3，2)，對(duì)應(yīng)的規(guī)則是(1101，101，010)。

5 仿真驗(yàn)證

5.1 對(duì)比實(shí)驗(yàn)

本文利用ClassBench[6]生成了不同規(guī)模和成分的規(guī)則庫(kù)對(duì)算法進(jìn)行仿真，并與Crossproducting、RFC、DCFL等分布式分類(lèi)算法作橫向比較。由于軟件仿真的限制，在算法編程時(shí)使用了串行流水模式[3]，而且要測(cè)試出硬件實(shí)現(xiàn)算法的極限分類(lèi)速度是比較困難的，于是本文利用完成一次查找的最大連續(xù)訪存次數(shù)(SMA)來(lái)評(píng)價(jià)算法速度。本實(shí)驗(yàn)測(cè)試了各算法在平均情況下的SMA，精確度為1;算法的內(nèi)存需求則以各算法總的內(nèi)存消耗量作為恒量標(biāo)準(zhǔn)，單位是KB，精確度為1 KB;特別的，對(duì)于低于10 KB的數(shù)值，精確度取到小數(shù)點(diǎn)后1位。

首先，利用ClassBench生成規(guī)模從50~10k條不等的規(guī)則庫(kù)，充分測(cè)試算法對(duì)于不同規(guī)模規(guī)則庫(kù)的支持能力;其次，對(duì)于規(guī)則維數(shù)的可擴(kuò)展性，將仿真分為A、B兩種情況。其中情況A的規(guī)則包含四元組(源地址、目的地址、源端口、目的端口)，情況B的規(guī)則包含六元組(源地址、目的地址、源端口、目的端口、協(xié)議類(lèi)型和標(biāo)志段)。具體評(píng)測(cè)結(jié)果如表2所示。

5.2 結(jié)果分析

下面，對(duì)仿真數(shù)據(jù)進(jìn)行對(duì)比分析。

Crossproducting算法在規(guī)則庫(kù)達(dá)到125條以后，出現(xiàn)了內(nèi)存爆炸現(xiàn)象。RFC在規(guī)則庫(kù)規(guī)模小于1k時(shí)的SMA最大僅為12，有著良好的時(shí)間性能;但是當(dāng)規(guī)則庫(kù)的規(guī)則數(shù)超過(guò)1k條以后，存儲(chǔ)空間以及預(yù)處理時(shí)間增長(zhǎng)過(guò)快。

從數(shù)據(jù)上顯示MLT-FCS與DCFL都具有較好的時(shí)空性能，不僅能夠支持大規(guī)模規(guī)則庫(kù)，而且能夠適應(yīng)規(guī)則維數(shù)的擴(kuò)展。實(shí)際上這是由于ClassBench工具集的限制，本仿真實(shí)驗(yàn)并沒(méi)有將各算法中間結(jié)果的緩存需求計(jì)算在內(nèi)。四種算法中Crossproducting只需緩存一個(gè)Crossproduct，MLT-FCS的中間結(jié)果只有一個(gè)沖突區(qū)標(biāo)簽向量和一個(gè)內(nèi)標(biāo)簽向量，而RFC與DCFL算法在多級(jí)聚合過(guò)程的每一級(jí)都需要緩存一定數(shù)量的中間結(jié)果。所以，如果將算法執(zhí)行過(guò)程中對(duì)中間結(jié)果的緩存需求計(jì)算在內(nèi)，DCFL算法的空間性能會(huì)比數(shù)據(jù)顯示差許多，而MLT-FCS的空間性能則不會(huì)有變化。

另一方面，DCFL平均情況下的SMA隨著規(guī)則庫(kù)規(guī)模的擴(kuò)大而增長(zhǎng)，而MLT-FCS平均情況下的SMA則恒定為7，較DCFL更能適應(yīng)規(guī)則庫(kù)規(guī)模的擴(kuò)展。根據(jù)MLT-FCS的仿真結(jié)果，如果使用工作頻率為150 MHz的帶有雙端口存儲(chǔ)模塊的邏輯設(shè)備，那么查詢(xún)周期會(huì)被控制在50 ns，MLT-FCS的執(zhí)行速度可以超過(guò)20 Mpps。即使在極限最差情況下，按照最小幀長(zhǎng)64 Byte計(jì)算，MLT-FCS算法的分類(lèi)速度也可達(dá)到OC-192的標(biāo)準(zhǔn)(10 Gbps)。而且MLT-FCS的查找速度還可以通過(guò)提高時(shí)鐘頻率、使用更多端口的內(nèi)存塊得到進(jìn)一步提高，利用目前的FPGA[7]與ASIC[8]是完全可以實(shí)現(xiàn)的。

6 結(jié)束語(yǔ)

基于域沖突空間的多標(biāo)簽樹(shù)算法(MLT-FCS)為降低分布式報(bào)文分類(lèi)算法的高內(nèi)存消耗、擴(kuò)展其應(yīng)用場(chǎng)景，首先根據(jù)分類(lèi)規(guī)則各個(gè)域內(nèi)部的冗余關(guān)系提出了域沖突空間的概念，然后利用標(biāo)簽換規(guī)則的思想進(jìn)一步構(gòu)建出基于域沖突空間表和內(nèi)標(biāo)簽向量表的兩級(jí)查詢(xún)機(jī)制，并在第二級(jí)查詢(xún)時(shí)充分利用硬件的并行處理和流水線操作特性提出了多標(biāo)簽樹(shù)查詢(xún)結(jié)構(gòu)。通過(guò)分析及仿真對(duì)比實(shí)驗(yàn)表明:a)MLT-FCS算法存儲(chǔ)需求低并且對(duì)中間結(jié)果的緩存要求不高，對(duì)于10k條規(guī)模6字段規(guī)則庫(kù)而言，總的內(nèi)存消耗量被控制在260 KB;b)只需要使用工作頻率為150 MHz的單端口內(nèi)存塊，算法的處理速度就可以達(dá)到OC-192的標(biāo)準(zhǔn)(10 Gbps);更重要的是，MLT-FCS算法對(duì)于規(guī)則庫(kù)規(guī)模的擴(kuò)展和規(guī)則維數(shù)的擴(kuò)展都能提供較好的支持。

參考文獻(xiàn):

[1]SRINIVASAN V， VARGHESE G， SURIS， et al. Fast and scalable layer four switching[C]// NEUFELD G， DELP G， SMITH J. Proc of ACM SIGCOMM. New York: Publications Dept， ACM Inc， 1998:191-202.

[2]GUPTA P， MCKEOWN N. Packet classification on multiple fields[J]. SIGCOMM Computer Communication Review， 1999， 29(14):147-160.

[3]TAYLOR D E， TURNER J S. Scalable packet classification using distributed Crossproducting of field labels[C]//ZNATI T， KNIGHTLY E. Proc of IEEE INFOCOM. Washington DC:IEEE Computer Society， 2005: 269-280.

[4]BABOESCU F， VARGHESE G. Scalable packet classification[J]. IEEE/ACM Trans on Networking， 2005， 13(1):2-14.

[5]董小明，林闖，陳震.基于空間優(yōu)化的決策樹(shù)算法[J]. 計(jì)算機(jī)應(yīng)用研究，2007， 24(11): 222-224.

[6]TAYLOR D E， TURNER J S. ClassBench: a packet classification benchmark[C] //ZNATI T， KNIGHTLY E. Proc of IEEE INFOCOM. Washington DC:IEEE Computer Society， 2005:499-511.

[7]IBM Blue Logic. Embedded SRAM selection guide[R]. 2002.

[8]Xilinx. Virtex-Ⅱ pro platform FPGAs: introduction and overview， DS083-1(v3.0)[R]. 2003.