• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于Hash和AQT的類(lèi)決策樹(shù)包分類(lèi)算法研究

      2010-08-13 03:07:04趙國(guó)鋒陳群麗
      通信技術(shù) 2010年2期
      關(guān)鍵詞:決策樹(shù)數(shù)據(jù)包端口

      趙國(guó)鋒, 陳群麗

      (重慶郵電大學(xué),重慶 400065)

      0 引言

      隨著網(wǎng)絡(luò)上各種業(yè)務(wù)的快速發(fā)展,原有的路由器必須不斷提供豐富的多業(yè)務(wù)能力。近來(lái),新型的網(wǎng)絡(luò)應(yīng)用包括區(qū)分服務(wù)(Differentiated Qualities of Service),虛擬專(zhuān)用網(wǎng)(Virtual Private Network), Qos等等。所有這些業(yè)務(wù)的實(shí)現(xiàn)都依賴(lài)于IP分類(lèi)算法,也就是說(shuō)IP分類(lèi)算法的好壞在一定程度上決定了這些業(yè)務(wù)的性能。因此研究有效的包分類(lèi)算法及其實(shí)現(xiàn)技術(shù)是目前網(wǎng)絡(luò)技術(shù)領(lǐng)域的熱門(mén)課題。

      國(guó)內(nèi)外學(xué)者針對(duì)不同的應(yīng)用已提出了一些有代表性的軟件包分類(lèi)算法.一類(lèi)是基于樹(shù)型結(jié)構(gòu)的算法(Trie-based Algorithms)[1]。該類(lèi)算法構(gòu)建一個(gè)等級(jí)索引樹(shù),用關(guān)鍵字按等級(jí)依次搜索這個(gè)索引樹(shù)。對(duì)于單個(gè)域的搜索是有效的,但這種機(jī)制的存儲(chǔ)要求會(huì)隨著搜索維數(shù)的增加而迅速增加。代表算法有Grid of-tree、AQT等。第二類(lèi)是基于哈希函數(shù)的算法[2-3]。該類(lèi)算法是根據(jù)各域前綴的長(zhǎng)度將規(guī)則聚合在一起形成元組,但哈希表的技術(shù)對(duì)于規(guī)則個(gè)數(shù)的可擴(kuò)展性較差;第三類(lèi)是并行查找算法。它將多維的匹配問(wèn)題轉(zhuǎn)換為單維的匹配,為每一維設(shè)置一個(gè)位向量來(lái)標(biāo)記與這一維相匹配的規(guī)則,各維并行執(zhí)行,最后將各維的位向量相與找到最佳匹配規(guī)則。該算法在讀取各維的位向量或聚合向量時(shí)需要較多的讀取次數(shù),尤其是規(guī)則庫(kù)中規(guī)則的個(gè)數(shù)比較大時(shí),所以該算法只適合硬件執(zhí)行。代表算法有Parallel Bitvectors(BV)、Aggregated Bit-vector(ABV) 等。第四類(lèi)是啟發(fā)式算法[4]。該類(lèi)型算法充分利用規(guī)則的結(jié)構(gòu)特點(diǎn)和冗余特點(diǎn),其時(shí)間復(fù)雜度一般為O(k),空間復(fù)雜度一般為O(nk)(k為規(guī)則的維數(shù))。因此該算法只適用于單維或二維搜索的情況。對(duì)于多維的搜索,需要的存儲(chǔ)空間太大。代表算法有RFC、Hierarchical Cuttings 等。

      現(xiàn)有的經(jīng)典算法都是從某一個(gè)特殊的角度提出解決方案,只能解決某一個(gè)方面的問(wèn)題,且其自身也存在一定的缺陷。本文提出了一種全新的基于Hash和AQT的類(lèi)決策樹(shù)包分類(lèi)算法,并闡述了該算法的具體實(shí)現(xiàn)過(guò)程。

      1 算法設(shè)計(jì)

      IP數(shù)據(jù)包通常包含源IP地址、目的IP地址、源端口、目的端口和協(xié)議類(lèi)型(一般稱(chēng)為5元組),還可能包括TCP標(biāo)志位、服務(wù)類(lèi)型等,在IPv6中還會(huì)使用流標(biāo)簽。包分類(lèi)是基于這些域的多維分類(lèi)算法,不失一般性,本文討論基于5元組的包分類(lèi)算法。不同的域有不同的表示方法。IP地址一般以前綴表示,端口一般用范圍表示,而協(xié)議類(lèi)型一般是某個(gè)精確取值。通過(guò)分析大規(guī)模規(guī)則集的特征,發(fā)現(xiàn)協(xié)議類(lèi)型域只有通配符和有限幾種精確取值,據(jù)此提出一種基于Hash和AQT的類(lèi)決策樹(shù)IP數(shù)據(jù)包分類(lèi)算法。

      該算法思想如下:首先根據(jù)協(xié)議類(lèi)型域的值將規(guī)則集劃分為若干個(gè)子集,這樣在每個(gè)子集里需要對(duì)4維IP數(shù)據(jù)包進(jìn)行分類(lèi),鑒于Hash函數(shù)和AQT算法適合二維分類(lèi)的特點(diǎn),將這兩個(gè)子集又作了細(xì)分。利用源端口和目的端口不同的取值都很有限的這一特征,構(gòu)造無(wú)沖突哈希函數(shù)。也就是把規(guī)則按照不同的源端口、目的端口劃分成不同的等價(jià)類(lèi)。然后每個(gè)等價(jià)類(lèi)指向一個(gè)兩維的AQT樹(shù)。整個(gè)規(guī)則集按照決策樹(shù)方式排列?;贖ash和AQT算法的類(lèi)決策樹(shù)IP數(shù)據(jù)包分類(lèi)算法的分類(lèi)過(guò)程(見(jiàn)圖1)如下:

      ① 查找數(shù)據(jù)包的時(shí)候,先要提取出協(xié)議域,根據(jù)協(xié)議類(lèi)型域的值查找到規(guī)則集中的某個(gè)子集;

      ② 然后根據(jù)源端口和目的端口兩個(gè)域,查找哈希表確定對(duì)應(yīng)的兩維的AQT樹(shù);

      ③ 最后按照源IP、目的IP的值沿著AQT樹(shù)的分枝不斷的向底端的葉子結(jié)點(diǎn)靠近,直到葉子結(jié)點(diǎn)為空或者使LC代碼用完,最后得到的最佳規(guī)則就是要找的規(guī)則;

      ④ 特殊情況下,對(duì)于未知協(xié)議類(lèi)型的數(shù)據(jù)包采用線(xiàn)性查找方式進(jìn)行。

      2 算法實(shí)現(xiàn)

      2.1 基于協(xié)議類(lèi)型的初始決策

      初始決策的構(gòu)造在根據(jù)協(xié)議類(lèi)型劃分得到的子集中進(jìn)行。因?yàn)閰⑴c初始決策構(gòu)造的規(guī)則已經(jīng)由5維降到了4維,并且規(guī)則的數(shù)量也大大減少,即使是比例最大的TCP規(guī)則也不足原有規(guī)則數(shù)量的一半,所以決策s樹(shù)的構(gòu)造過(guò)程大大加快,決策樹(shù)的高度也隨之降低。初始決策構(gòu)造完成后,就可以將IP數(shù)據(jù)流分配到各自協(xié)議的規(guī)則子集中進(jìn)行細(xì)化查找。下面是構(gòu)建基于協(xié)議類(lèi)型的初始決策樹(shù)的代碼:

      2.2 基于源端口和目的端口的Hash函數(shù)尋找等價(jià)類(lèi)

      (1)Hash函數(shù)的建立

      將源端口和目的端口做一個(gè)交叉積,由于這兩個(gè)域不同的取值有限,所以完 全可以避免空間的爆炸問(wèn)題,比較好的解決了多維分類(lèi)Hash函數(shù)空間爆炸使空間 復(fù)雜度過(guò)大的問(wèn)題。假設(shè)源端口和目的端口的不同取值個(gè)數(shù)分別為:S_p和D _p。

      (2)基于源端口和目的端口的Hash函數(shù)尋找等價(jià)類(lèi)查找過(guò)程

      由上一個(gè)階段已經(jīng)將5維IP數(shù)據(jù)包降為4維數(shù)據(jù),并且將數(shù)據(jù)包轉(zhuǎn)移到各個(gè)協(xié)議的子判決層上。進(jìn)入子判決層后,利用在源端口、目的端口各種不同的取值都很有限的基礎(chǔ)上。構(gòu)造無(wú)沖突的哈希函數(shù)。也就是把規(guī)則按照不同的源端口、目的端口劃分成不同的等價(jià)類(lèi)。然后每個(gè)等價(jià)類(lèi)指向一個(gè)兩維的AQT樹(shù)。

      2.3 基于源IP、目的IP的AQT樹(shù)搜索規(guī)則

      由上一步中,已經(jīng)利用源端口、目的端口兩個(gè)域輸入已經(jīng)構(gòu)建好的無(wú)沖突 Hash函數(shù),然后查找哈希表確定對(duì)應(yīng)的兩維的AQT樹(shù)。再按照源IP、目的IP的值沿著AQT樹(shù)的分枝不斷的向底端的葉子結(jié)點(diǎn)靠近,直到葉子結(jié)點(diǎn)為空或者使LC代碼用完,最后得到的最佳規(guī)則就是要找的規(guī)則。

      AQT算法是將二維數(shù)據(jù)解釋為平面空間的矩陣,使用四叉樹(shù)作為其實(shí)現(xiàn)的基本數(shù)據(jù)結(jié)構(gòu),用遞歸空間分解技術(shù)將分類(lèi)規(guī)則存儲(chǔ)于四叉樹(shù)的結(jié)點(diǎn)中。四樹(shù)中的結(jié)點(diǎn)最多可以有四個(gè)孩子,四個(gè)指針?lè)謩e標(biāo)示為00,01, 10, 11。

      3 仿真實(shí)驗(yàn)與算法性能分析

      3.1 實(shí)驗(yàn)條件及結(jié)果

      為檢測(cè)本文算法性能,本文在普通 PC上進(jìn)行了性能測(cè)試,測(cè)試環(huán)境為P4 1.7 內(nèi)存384 MB。測(cè)試了由ClassBench產(chǎn)生的5維共1000個(gè)規(guī)則集。AQT中的可調(diào)因子α取2。表1為實(shí)驗(yàn)中所選取的1000個(gè)規(guī)則集中的部分實(shí)例。

      表1 規(guī)則集實(shí)例

      3.2 算法性能分析

      本文所提出的基于Hash和AQT的類(lèi)決策樹(shù)IP數(shù)據(jù)包分類(lèi)算法首先要經(jīng)過(guò)1次查表處理基于協(xié)議類(lèi)型的初始決策,而后經(jīng)過(guò)K次訪問(wèn)內(nèi)存進(jìn)行查找無(wú)沖突的Hash函數(shù),最后沿AQT的分枝不斷下降到達(dá)葉子結(jié)點(diǎn),最后找到相應(yīng)的規(guī)則。由此可見(jiàn),AQT決策樹(shù)的樹(shù)深是一個(gè)是個(gè)決定因素,其查找性能主要由決策樹(shù)的樹(shù)深決定,平均性能由決策樹(shù)的平均樹(shù)深決定,最差性能由決策樹(shù)的最大樹(shù)深決定。時(shí)間性能上來(lái)看, Hash函數(shù)時(shí)間性能為O(K),AQT時(shí)間性能為O(N2)。因此本文算法的復(fù)雜度為O(1 +K1+N2)。其中K為訪問(wèn)Hash函數(shù)訪問(wèn)內(nèi)存數(shù),N2為規(guī)則數(shù),搜索時(shí)間測(cè)試見(jiàn)圖2。

      從空間性能測(cè)試(見(jiàn)圖3)來(lái)看,1位的協(xié)議類(lèi)型所占空間基本可以忽略不計(jì),而2維的目的端口和源端口是利用Hash函數(shù)來(lái)查找的,因此這部分空間O(N1)相對(duì)來(lái)說(shuō)也較小,其中N1是規(guī)則數(shù)。剩下的2維源IP和目的IP是由AQT算法來(lái)實(shí)現(xiàn)的,這部分的空間性能為O(αW1),W1為IP地址的長(zhǎng)度,α為可調(diào)因子。因此本文算法的總空間性能就是O(N1+αW1)。

      圖2 搜索時(shí)間測(cè)試

      圖3 空間性能測(cè)試

      更新時(shí)間性能來(lái)看,初始的協(xié)議類(lèi)型的初始決策容易,更形主要是在后續(xù)的2維Hash函數(shù)更新和2維AQT決策樹(shù)更新上面。2維Hash函數(shù)更新性能為O(1),2維AQT決策樹(shù)更新性能為其中N2為規(guī)則數(shù),α為可調(diào)因子。因此,算法的更新性能為其中N2為AQT算法的IP規(guī)則數(shù),α為可調(diào)因子。各部分算法比較見(jiàn)表2所示。

      表2 Hash、AQT和本文算法性能比較

      表2中N,K為總的規(guī)則數(shù)和查找內(nèi)存次數(shù);W為總長(zhǎng)度;而N1,N2,W1,K1都是各部分的規(guī)則數(shù)、長(zhǎng)度和次數(shù);其中N>N1,N>N2,W>W(wǎng)1和W>W(wǎng)2。

      4 結(jié)語(yǔ)

      本文算法是在協(xié)議類(lèi)型域有限的基礎(chǔ)上實(shí)現(xiàn)初始分類(lèi)決策,不僅繼承了Hash算法優(yōu)秀時(shí)間性能、AQT算法優(yōu)秀的空間性能和更新性能,而且克服了原有的Hash算法和AQT算法不易應(yīng)用于多維分類(lèi)等不足,將Hash函數(shù)、AQT算法與決策樹(shù)有機(jī)結(jié)合起來(lái)[5-10]。通過(guò)實(shí)驗(yàn)和性能分析得出,本文算法最大化的提高了時(shí)間性能、空間性能。

      [1] Simone M,Giancarlo C,Riccardo B,et al. A Low-complexity Packet Classification Algorithm for Multiple Description Video Streaming over IEEE802.11E Networks Image Processing[C]//ICIP 15th IEEE International Conference. USA:ICIP, 2008:3072-3075.

      [2] 江朝勇.IP數(shù)據(jù)包分類(lèi)算法的研究[D]. 重慶:重慶郵電大學(xué), 2006.

      [3] 錢(qián)萌,董小明.基于統(tǒng)計(jì)決策樹(shù)的包分類(lèi)算法[J].華東理工大學(xué)學(xué)報(bào):自然科學(xué)版,2008,34(03):432-435.

      [4] Phang S Y, Lee H J, Lim H. Design and Implementation of V6GEN and V6PCF: A Compact IPv6 Packet Generator and a New Packet Classification Framework for IPv6[C]//Convergence and Hybrid Information Technology, 2008. ICCIT'08. Third International Conference on 2008.Busan:Pongseo Univ.,2008:38-43.

      [5] 余磊. IP包分類(lèi)算法研究[D].重慶:重慶郵電大學(xué), 2007.

      [6] 戴雪龍,王永綱,張萬(wàn)生.并行層壓縮樹(shù)包分類(lèi)算法[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2006,36(03):297-300.

      [7] 周曉飛,楊靜宇 姜文瀚.核最近鄰?fù)拱诸?lèi)算法[J].中國(guó)圖象圖形學(xué)報(bào),2007,12(07):1209-1222.

      [8] 甘利杰.路由器中的包分類(lèi)算法研究[J].計(jì)算機(jī)科學(xué),2006, 33(11):54-57.

      [9] 關(guān)愛(ài)芳.網(wǎng)絡(luò)處理器中包分類(lèi)引擎設(shè)計(jì)[D].西安:西北工業(yè)大學(xué),2007.

      [10] 劉鐸.快速包分類(lèi)算法的研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué).2006.

      猜你喜歡
      決策樹(shù)數(shù)據(jù)包端口
      一種端口故障的解決方案
      一種針對(duì)不均衡數(shù)據(jù)集的SVM決策樹(shù)算法
      SmartSniff
      決策樹(shù)和隨機(jī)森林方法在管理決策中的應(yīng)用
      電子制作(2018年16期)2018-09-26 03:27:06
      端口阻塞與優(yōu)先級(jí)
      基于決策樹(shù)的出租車(chē)乘客出行目的識(shí)別
      初識(shí)電腦端口
      電腦迷(2015年6期)2015-05-30 08:52:42
      生成樹(shù)協(xié)議實(shí)例探討
      基于肺癌CT的決策樹(shù)模型在肺癌診斷中的應(yīng)用
      基于Libpcap的網(wǎng)絡(luò)數(shù)據(jù)包捕獲器的設(shè)計(jì)與實(shí)現(xiàn)
      灵川县| 称多县| 安吉县| 江陵县| 娱乐| 珲春市| 孙吴县| 巴南区| 凯里市| 桓台县| 巴马| 郧西县| 金平| 文安县| 鄯善县| 宜宾县| 大姚县| 滦平县| 福海县| 梧州市| 阜南县| 徐闻县| 宜川县| 邯郸县| 武定县| 临漳县| 南昌县| 德州市| 新余市| 盐津县| 酉阳| 磐石市| 寻甸| 永清县| 阜城县| 白河县| 申扎县| 郓城县| 麻江县| 丹寨县| 鲁山县|