三種包分類算法的實(shí)現(xiàn) SX1116090

1、簡(jiǎn)單實(shí)現(xiàn)包分類算法概要包分類是VPNs、下一代路由器、防火墻等設(shè)備的關(guān)鍵技術(shù)。包 分類算法研究具有十分重要的意義，是目前的熱點(diǎn)之一。本文介紹了 常用的包分類算法，分析了它們的優(yōu)缺點(diǎn)，并簡(jiǎn)單實(shí)現(xiàn)線性、Hicuts 和Hypercut三種基本算法，對(duì)這三種算法進(jìn)行性能對(duì)比。、包分類算法背景路由器的主要功能是將一個(gè)網(wǎng)絡(luò)的IP數(shù)據(jù)報(bào)(包)Packet轉(zhuǎn)發(fā)到另一個(gè)網(wǎng) 絡(luò)。傳統(tǒng)路由器僅根據(jù)數(shù)據(jù)包的目的地址對(duì)數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，提供未加區(qū)分的盡 力服務(wù)(Best Effort Service)，這是一維報(bào)文分類的典型形式：對(duì)所有的用戶報(bào)文 一視同仁的處理。但是，隨著因特網(wǎng)規(guī)模的不斷擴(kuò)大和應(yīng)用技術(shù)的進(jìn)步，越來(lái)越

2、多的業(yè)務(wù)需要對(duì)數(shù)據(jù)包進(jìn)行快速有效的分類以便區(qū)別處理提供不同級(jí)別的服務(wù)， 因此路由器還需要對(duì)數(shù)據(jù)包進(jìn)行進(jìn)一步的處理。最常見(jiàn)的是根據(jù)安全性需要，對(duì) 包進(jìn)行過(guò)濾，阻止有安全隱患的數(shù)據(jù)包通過(guò)。因此，研究高速包分類算法具有十 分重要的意義。因特網(wǎng)是由許許多多的主機(jī)及連接這些主機(jī)的網(wǎng)絡(luò)組成，主機(jī)間通過(guò)TCP /IP協(xié)議交換數(shù)據(jù)包。數(shù)據(jù)包從一個(gè)主機(jī)穿過(guò)網(wǎng)絡(luò)到達(dá)另一個(gè)主機(jī)，其中就需 要路由器提供數(shù)據(jù)包轉(zhuǎn)發(fā)服務(wù)。近年來(lái)，因特網(wǎng)己經(jīng)從主要連接教育機(jī)構(gòu)的低速 網(wǎng)絡(luò)迅速成為重要的商業(yè)基礎(chǔ)設(shè)施?，F(xiàn)在，因特網(wǎng)正呈現(xiàn)兩方面的新變化：一方 面，因特網(wǎng)上的用戶正在呈現(xiàn)爆炸性增長(zhǎng)，Web站點(diǎn)正在迅速增加，需要寬帶 網(wǎng)絡(luò)的多媒體應(yīng)

3、用正在日益普及，因特網(wǎng)的通信量也正在呈現(xiàn)爆炸性增長(zhǎng)，因特 網(wǎng)正日益變得擁擠：另一方面，因特網(wǎng)上的用戶正呈現(xiàn)許多不同的種類，從以瀏 覽和下載資料為主的普通家庭用戶到經(jīng)營(yíng)電子商務(wù)的大型企業(yè)等等，這些用戶從 安全、性能、可靠性方面對(duì)因特網(wǎng)的期望是不同的。人們希望路由器能夠具有諸 如數(shù)據(jù)包過(guò)濾、區(qū)分服務(wù)、QoS、多播、流量計(jì)費(fèi)等額外功能。所有這些處理都 需要路由器按某些規(guī)則將數(shù)據(jù)包進(jìn)行分類，分類后的數(shù)據(jù)構(gòu)成許多“流，再對(duì) 每一個(gè)流分別進(jìn)行處理。對(duì)于網(wǎng)絡(luò)流量的不斷增長(zhǎng)問(wèn)題，由于光纖技術(shù)和DWDM 技術(shù)的發(fā)展使得鏈路的速率不再成為瓶頸，已經(jīng)滿足了大流量傳輸?shù)男枨螅@就 使得路由器的處理速度成為網(wǎng)絡(luò)整體速度

4、的一個(gè)瓶頸。這主要由于路由器需要對(duì) 每個(gè)輸入包執(zhí)行許多操作，包括十分復(fù)雜的分類操作。例如，它們需要對(duì)每個(gè)輸 入包執(zhí)行最長(zhǎng)前綴匹配以發(fā)現(xiàn)其下一跳地址：需要對(duì)每個(gè)輸入包執(zhí)行多維包分類 以便在執(zhí)行緩沖器管理、QoS調(diào)度、防火墻、網(wǎng)絡(luò)地址翻譯、多播服務(wù)、虛擬專 用網(wǎng)、速率限制、流量計(jì)費(fèi)等任務(wù)時(shí)區(qū)別對(duì)待不同的包。因此，為了滿足服務(wù)快 速性和服務(wù)多樣性這兩方面的需要，就必須研究相應(yīng)的快速包分類算法應(yīng)用到實(shí) 際路由中。二、包分類原理包分類是QoS的基礎(chǔ)，只有區(qū)分了不同的報(bào)文業(yè)務(wù)，才能進(jìn)行分別處理及保 障相關(guān)業(yè)務(wù)的服務(wù)質(zhì)量。分類是定義傳輸類別并判斷報(bào)文所屬傳輸類別的過(guò)程。 TCP/IP報(bào)文有兩種基本的分類模式

5、，行為聚合（BA）或多字段（MF）。BA類 是區(qū)分服務(wù)編碼點(diǎn)（DSCP）處理的基礎(chǔ)，具有較好的擴(kuò)展性，適用于核心網(wǎng)絡(luò)。 MF類基于TCP/IP報(bào)頭一個(gè)或多個(gè)域（字段），原則上講所有的字段都可以用于 分類。比如經(jīng)典的五元組形式（源端口，目的端口，源地址，目的地址，協(xié)議類 型）。MF類一般在網(wǎng)絡(luò)邊界實(shí)現(xiàn)，是一種廣泛使用的靈活的報(bào)文分類方法。高 性能的路由器應(yīng)該支持靈活的分類策略，實(shí)現(xiàn)高效的分類算法。動(dòng)作通常數(shù)據(jù)包分類就是根據(jù)網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)包的包頭信息，將數(shù)據(jù)包按照一定規(guī)則進(jìn)行分類。在網(wǎng)絡(luò)分層模型中，要傳輸?shù)臄?shù)據(jù)被各層協(xié)議的包頭依次封裝， 每層的包頭都包含若干個(gè)域（字段），它們分別表示該層協(xié)議的特

6、征數(shù)據(jù)。一個(gè)分 類器又稱規(guī)則庫(kù)f，含有條過(guò)濾規(guī)則，記為 R1,R2,.,Rn。R為其中任意一條規(guī) 則，由匹配條件filter、優(yōu)先級(jí)priority和匹配處理action三部分構(gòu)成，記為Rfilter， Rpriority和 R action:Rfilter:d元組（RF1,RF2,.,RFd），指示數(shù)據(jù)包匹配該規(guī)則的條件。Fi表 示規(guī)則R的第6匹配域，是該條規(guī)則對(duì)數(shù)據(jù)包頭的第i個(gè)字段的約束條件。Rpriority:規(guī)則的優(yōu)先級(jí)，優(yōu)先級(jí)越高，代價(jià)越小。取值范圍是1,+“），即 RpriorityE1,+s）。默認(rèn)情況下規(guī)則編號(hào)表示優(yōu)先級(jí)，編號(hào)較小的規(guī)則具有較高 的優(yōu)先級(jí)。Raction:對(duì)滿足

7、相應(yīng)過(guò)濾規(guī)則的數(shù)據(jù)包的處理動(dòng)作，其取值范圍是 a1,a2,a3,.,ak，艮口RactionE a1, a2, a3,.,ak。一般來(lái)說(shuō)k域報(bào)文分類匹配分類器設(shè)計(jì)到的技術(shù)也稱k維報(bào)文分類問(wèn)題。k維 報(bào)文分類問(wèn)題是通用報(bào)文分類問(wèn)題。一個(gè)數(shù)據(jù)包的包頭經(jīng)過(guò)解析以后得到一個(gè)關(guān) 鍵字P,P為d元（p1,p2，,p）,d維包分類問(wèn)題就是在規(guī)則集中尋找和P匹配的具有 最高優(yōu)先級(jí)的的規(guī)則Rbest （最佳匹配）。三、三種包分類算法包分類問(wèn)題巨大的需求，眾多的算法和體系結(jié)構(gòu)已被提出，基本上可以劃分 為5種類型的算法：窮舉分類算法、基于Trie分割的分類算法、幾何區(qū)域分割的 分類算法、元組空間分割分類算法、維度分

8、解分類算法，本文要實(shí)現(xiàn)的三種包 分類算法：線性包分類算法、Hucuts和Hypercut算法分別屬于窮舉分類算法和幾 何區(qū)域劃分算法。下文將就著兩種類型的算法展開(kāi)。窮舉分類算法是查找問(wèn)題最基本而簡(jiǎn)單的解決方法將待分類的數(shù)據(jù)包依次 和分類規(guī)則庫(kù)內(nèi)的所有規(guī)則進(jìn)行比較。討論這種方法的意義在于，假設(shè)規(guī)則集已 被分成許多子集，每個(gè)子集的獨(dú)立查找往往可以選擇該方法。窮盡查找法中具體 兩個(gè)最常見(jiàn)的算法是線性查找和大規(guī)模并行查找。二者恰好代表窮盡查找法的兩 種極端，線性查找對(duì)規(guī)則集不進(jìn)行分割，其性能最低，WTCAM將規(guī)則集劃分成 每個(gè)子集只有一條規(guī)則，其性能最高。線性查找算法按照按優(yōu)先級(jí)降序排列分類規(guī)則鏈表，

9、一個(gè)數(shù)據(jù)包順序地與每 個(gè)規(guī)則進(jìn)行比較直到找到第一個(gè)匹配的規(guī)則。由于規(guī)則已經(jīng)事先按照優(yōu)先級(jí)降序 排列，所以第一個(gè)匹配的規(guī)則即為最佳匹配規(guī)則。包分類階段的空間復(fù)雜度為 O(N)，時(shí)間復(fù)雜度為O(N)。包分類的時(shí)間隨著規(guī)則數(shù)目的增加呈線性增加，適 用于規(guī)則數(shù)目比較少的情況。幾何區(qū)域劃分算法，主要思想根據(jù)規(guī)則代表的區(qū)域，對(duì)規(guī)則集進(jìn)行分割儲(chǔ)存 查找時(shí)，判斷數(shù)據(jù)包代表的點(diǎn)落入的子空間范圍，逐步收攏得到最佳匹配規(guī)則。 典型算法有：智能層次切割(Hierarchical IntelligentCuttings，Hicuts)算法和多決 策樹(shù)HyperCuts算法。HiCuts(Hierarchical Int

10、elligent Cuttings)算法由學(xué)者 Gupta和 Mckeown提 出，切 割(Cutting)的概念來(lái)源于從幾何學(xué)角度觀察包分類問(wèn)題。該算法適于范圍類型的 規(guī)則，將其它字段統(tǒng)一轉(zhuǎn)化成范圍。卬。皿，采用了一棵決策樹(shù)作為快速查找的 數(shù)據(jù)結(jié)構(gòu)，其內(nèi)部結(jié)點(diǎn)包含適當(dāng)?shù)姆诸悓?dǎo)向信息，但不存儲(chǔ)任何規(guī)則，其葉結(jié)點(diǎn) (或外部結(jié)點(diǎn))存儲(chǔ)一個(gè)小型的規(guī)則子集。算法結(jié)合了決策樹(shù)搜索和線性查找兩種 分類方式，采用多級(jí)空間分解，每級(jí)分解在一個(gè)維度上進(jìn)行，把規(guī)則庫(kù)分為各個(gè) 葉子結(jié)點(diǎn)內(nèi)的小規(guī)則集。當(dāng)一個(gè)IP包進(jìn)來(lái)時(shí)，沿著樹(shù)的某一分支遍歷到樹(shù)的葉子， 將該IP包和葉子結(jié)點(diǎn)中少量的規(guī)則線性匹配。Hicuts算法的優(yōu)點(diǎn)

11、是占用內(nèi)存空間 小，規(guī)則集更新容易，直接支持范圍匹配，缺點(diǎn)是預(yù)處理時(shí)間較長(zhǎng)，分類速度比 一些快速包分類算法低。HyperCuts算法由Singh、Baboescu、Varghese和Wang等學(xué)者提出。HyperCut 以HiCuts算法為基礎(chǔ)上，做了一些改進(jìn)，通過(guò)多重切割多維空間，最小化決策樹(shù) 的高度，同樣也限制葉結(jié)點(diǎn)上規(guī)則最大數(shù)目。由于等分切割，HypcrCuts對(duì)子空 間的編碼簡(jiǎn)單而有效，譯碼簡(jiǎn)單，這使得多重切割沒(méi)有大幅增加數(shù)據(jù)結(jié)構(gòu)所占用 內(nèi)存。HyperCuts算法對(duì)Hicuts算法的改進(jìn)，包括：HyperCuts通過(guò)增加一個(gè)參數(shù)， 使決策樹(shù)中間結(jié)點(diǎn)可以同時(shí)基于多維進(jìn)行分割。Hicut

12、s形成的決策樹(shù)葉子結(jié)點(diǎn) 上重復(fù)的規(guī)則較多，HyperCuts過(guò)把一些通用規(guī)則（比如通配規(guī)則，前綴較短的 規(guī)則）從分類規(guī)則庫(kù)中獨(dú)立出來(lái)，存放在根結(jié)點(diǎn)中。HyperCuts在葉結(jié)點(diǎn)所存儲(chǔ)規(guī) 則列表中仍進(jìn)行線性查找。理論上，該算法時(shí)間和空間復(fù)雜度與HiCuts算法屬于 同一個(gè)數(shù)量級(jí)。HyperCutsa策樹(shù)比HiCuts策樹(shù)更低，然而內(nèi)部結(jié)點(diǎn)信息更多， 需要位數(shù)也更多，這可能增加一個(gè)內(nèi)部結(jié)點(diǎn)訪問(wèn)內(nèi)存的次數(shù)，故一次多重切割的 維數(shù)和份數(shù)受存儲(chǔ)器位寬限制。HyperCuts算法也支持增量更新，支持以中等速 度進(jìn)行隨機(jī)更新，最壞情況下，需要重構(gòu)決策樹(shù).四、算法描述這里只做算法的描述，具體代碼見(jiàn)附件包分類根

13、據(jù)IP數(shù)據(jù)的包頭字段分類，小數(shù)據(jù)包為網(wǎng)絡(luò)層信息傳輸?shù)妮d體，擁 有固定長(zhǎng)度20字節(jié)的首部。同時(shí)IP數(shù)據(jù)報(bào)還封裝了上一層的TCP/UDP報(bào)文段得的 首部，包括源端口、目的端口等信息。規(guī)則庫(kù)f中的每條規(guī)則規(guī)則Rule由分類器 (filter)、優(yōu)先級(jí)(priority)、動(dòng)作(action)組成。分類器可以用經(jīng)典的五元組表示 (目的地址，源地址，協(xié)議，目的端口，源端口)即DA，SA，PR，DP，SP)。 當(dāng)一條IP數(shù)據(jù)報(bào)進(jìn)入路由器要經(jīng)過(guò)路由器轉(zhuǎn)發(fā)時(shí)，數(shù)據(jù)報(bào)會(huì)解析出一個(gè)關(guān)鍵字P， 若P也是由5個(gè)字段組成P(d1,d2,d3,d4,d5),那么數(shù)據(jù)包與規(guī)則的匹配問(wèn)題就是P 的五元組每個(gè)分量d跟filte

14、r的分量匹配尋找路由器處理動(dòng)作action的過(guò)程。typedef structunsigned long DA ;unsigned long SA ;int PR ;unsigned DP ;unsigned SP ;filter , *Filter;線性包分類算法：規(guī)則庫(kù)中的規(guī)則用一條單鏈表的形式組織，按照優(yōu)先Rule.priority將單鏈表 非升序排列。包頭解析關(guān)鍵字P在鏈表中從頭結(jié)點(diǎn)開(kāi)始順序匹配，第一個(gè)與之匹 配的規(guī)則就是最佳匹配。typedef struct rulefliter fliters;int priority ;int action ;struct rule *next

15、; Rule ;Hicuts算法Hicuts算法結(jié)合了決策樹(shù)搜索和線性查找兩種分類方式，采用多級(jí)空間分解， 每級(jí)分解在一個(gè)維度上進(jìn)行，把規(guī)則庫(kù)分為各個(gè)葉子結(jié)點(diǎn)內(nèi)的小規(guī)則集。Hicuts 算法構(gòu)建了一顆決策樹(shù)，其內(nèi)部結(jié)點(diǎn)包含適當(dāng)?shù)姆诸悓?dǎo)向信息，但是不包含任何 規(guī)則，規(guī)則都是存儲(chǔ)在葉子結(jié)點(diǎn)中。概括地描述d維HiCuts算法如下。每個(gè)內(nèi)部 結(jié)點(diǎn)v，代表幾何查找空間的一個(gè)分區(qū)。例如根結(jié)點(diǎn)代表完整的d維空間，根據(jù)其 中一維可將個(gè)結(jié)點(diǎn)空間分割成更小子空間，每個(gè)子空間為v結(jié)點(diǎn)的每個(gè)子結(jié)點(diǎn)所 表示。子空間被遞歸地分割直至每個(gè)空間包含的規(guī)則數(shù)目不大于參數(shù)binth，此時(shí) 給葉結(jié)點(diǎn)分派規(guī)則。公式化描述內(nèi)部結(jié)點(diǎn)v如

16、下：一個(gè)超矩形(Hyper-rectangle)B(v)，是一個(gè)范圍類型的d元組(m1,h1,m2,h2,，mdOd該矩形定義了一個(gè)子空間，存儲(chǔ)于v結(jié)點(diǎn)中。一次切割c(v)，包含兩個(gè)實(shí)體。k=dim(c(v)，切割空間B(V)所依據(jù)的維 的編號(hào)。np(C(v)，空間B(v)被分成的份數(shù)，等于內(nèi)部結(jié)點(diǎn)v的孩子結(jié)點(diǎn)個(gè)數(shù)。所包含的規(guī)則子集CRS(v)，如果是內(nèi)部結(jié)點(diǎn)w的子結(jié)點(diǎn)， UCRS(v )是 CRS(w)的一個(gè)子集。每個(gè)CRS(w)中的規(guī)則，如果跨入(或被切入)空間B(v)，也即 成為CRS(v)中的一員。CRS(root)是包含所有規(guī)則的集合。CRS(v)的規(guī)則數(shù)目記 作 NumRules(

17、v)。為一個(gè)規(guī)則集構(gòu)造一棵決策樹(shù)有許多方法。在預(yù)處理階段，HiCuts算法在幾 個(gè)啟發(fā)公式引導(dǎo)下，在限定可用內(nèi)存的情況下最小化決策樹(shù)的高度，從而能夠構(gòu) 造出一棵比較合理的決策樹(shù)。Typedef enumLEAF,BRANCH NodeKind ; 結(jié)點(diǎn)種類typedef struct TREENODENodeKind kind ;unionstruct Filter ;Rule* infoptr lf ;葉子struct TREENODE*ptr31 ;int num bh; /分支TREENODE;*rootTREE ;規(guī)則劃分 int PreCut (unsigned char dimTo

18、Cut, unsigned int currRange42,unsigned int numRules,unsigned int *currRuleList,struct CUTTING *tempCut,struct RULESET *ruleSet) unsigned int i, num, cut;unsigned int cuts = 1;/unsigned int numCuts = 1; / number of cuts is 2AnumCuts/ TODO:refer to HiCuts for alternative initialization of numCutsunsig

19、ned int spaceAvailable = numRules*SPFAC; / space availableunsigned int smC=0; / space measurementunsigned int rangeToSearch2; / search this range for the number of colliding rulesunsigned int interval = currRangedimToCut1-currRangedimToCut0; / interval is always 2Acutfloat costs4, worstCosts4;for(i=

20、0; i4; i+) worstCostsi = 0;/ decide if current search range really need to cutfor(num=0; numruleListcurrRuleListnum.ruleRangedimToCut0ruleListcurrRuleListnum.ruleRangedimToCut1=currRangedimToCut1)smC+;if(smC = numRules)return FALSE; / all rules cover the full search space, so is of no use to cut any

21、more/ cutting with the limit of spaceAvailablewhile(TRUE)smC = 0; / space measurementinterval = (interval1)+1;/ interval/2numCuts = (0 x1cuts);costs1 = 0;for(cut=0; cutnumCuts; cut+)劃分出來(lái)的區(qū)間rangeToSearch0 = currRangedimToCut0+cut*interval;rangeToSearch1 = rangeToSearch0+interval-1;/ -1 為防止越界 costs0 =

22、 0;for(num=0; numruleListcurrRuleListnum.ruleRangedimToCut0=rangeToSearch0 &ruleSet-ruleListcurrRuleListnum.ruleRangedimToCut0ruleListcurrRuleListnum.ruleRangedimToCut1=rangeToSearch0&ruleSet-ruleListcurrRuleListnum.ruleRangedimToCut1ruleListcurrRuleListnum.ruleRangedimToCut0ruleListcurrRuleListnum.

23、ruleRangedimToCut1rangeToSearch1)smC+;costs0+;costs1+=costs0;if(worstCosts0costs0)worstCosts0 = costs0;costs1 = costs1/numCuts; / average number of rules falling in each child node if(worstCosts1costs1) worstCosts1 = costs1;smC+=numCuts;if(smCspaceAvailable)cuts+; / twice larger than current number

24、of cuttings interval-;for(i=0; idimToCut = dimToCut;tempCut-numCuts = cuts;for(i=0; icostsi = worstCostsi;return SUCCESS;HyperCuts 算法HyperCuts以HiCuts算法為基礎(chǔ)上，做了一些改進(jìn)，通過(guò)多重切割多維空間， 最小化決策樹(shù)的高度，同樣也限制葉結(jié)點(diǎn)上規(guī)則最大數(shù)目，降低決策樹(shù)高度。由 于等分切割，HypcrCuts對(duì)子空間的編碼簡(jiǎn)單而有效，譯碼簡(jiǎn)單，這使得多重切 割沒(méi)有大幅增加數(shù)據(jù)結(jié)構(gòu)所占用內(nèi)存。五、算法性能分析對(duì)于包分類算法的軟件仿真要滿足四個(gè)原則：一、數(shù)據(jù)

25、流的產(chǎn)生：只有實(shí)際 的網(wǎng)絡(luò)流才能對(duì)算法給出準(zhǔn)確的評(píng)估。二、分類規(guī)則集的產(chǎn)生：網(wǎng)絡(luò)設(shè)備對(duì)規(guī)則 數(shù)的容忍度要多達(dá)10K1M個(gè)，仿真軟件可以根據(jù)參數(shù)設(shè)定自動(dòng)產(chǎn)生規(guī)則集。三、 算法的實(shí)現(xiàn)和嵌入：實(shí)現(xiàn)上述多種算法，分別將它們嵌入到平臺(tái)中測(cè)試。四、仿 真統(tǒng)計(jì)參數(shù)分析：主要包括時(shí)間性能測(cè)試和空間需求量測(cè)試。時(shí)間量的統(tǒng)計(jì)是將 同一個(gè)包經(jīng)過(guò)多次重復(fù)處理后的平均值?？臻g需求量主要是算法的代碼空間和數(shù) 據(jù)占用空間?；谏鲜鲞@些原則可以使用PALAC模擬器為測(cè)試包分類算法提供了一個(gè)模 擬環(huán)境，也可以使使用Quartus II 6.0平臺(tái)。它可以分析普通的ACL條（存取訪問(wèn)規(guī) 則），產(chǎn)生背景數(shù)據(jù)流，在其提供的離散事件模

26、擬框架中靜態(tài)的存儲(chǔ)算法的相關(guān) 數(shù)據(jù)，最后輸出統(tǒng)計(jì)結(jié)果。算法性能對(duì)比（S：速度M：存儲(chǔ)空間）線性算法幾何空間分解S隨規(guī)則數(shù)變化線性增長(zhǎng)幾乎無(wú)影響S隨域數(shù)變化不敏感慢速線性增長(zhǎng)M隨規(guī)則數(shù)變化線性增長(zhǎng)線性增長(zhǎng)M隨樹(shù)數(shù)變化較敏感慢線性增長(zhǎng)適用性適用于規(guī)則數(shù)很少的情況速度較快占用空間小，適合高速應(yīng)用線性查找的空間復(fù)雜度是O (n)，時(shí)間復(fù)雜度也是O(n)。若把查找過(guò)程分為若 十小步，并采用流水線技術(shù)，可以將平均查找時(shí)間降低一個(gè)常數(shù)因子，令k代表 流水線的階段個(gè)數(shù)，平均查找時(shí)間變?yōu)镺(N /k)，但是計(jì)算所需資源也將增加k 倍。線性查找相對(duì)較慢，但是，當(dāng)根據(jù)其它算法將所有可能與輸入包相匹配的規(guī) 則數(shù)目已經(jīng)縮小到一個(gè)常數(shù)后，往往將線性查找作為查找的最后階段。HiCuts是一個(gè)表現(xiàn)杰出的動(dòng)態(tài)軟件算法。用depth表示決策樹(shù)的高度，binth 為決策樹(shù)葉子