決策樹報文分類算法

呂高鋒，譚 靖，喬冠杰，嚴錦立

(國防科技大學 計算機學院， 湖南 長沙 410073)

報文分類是各種網絡服務所需的基本技術之一，如安全防護、策略路由和服務質量(quality of service，QOS)等。因此，報文分類在云服務提供商、互聯網服務提供商(internet service provider，ISP)和互聯網交換中心(internet exchange point，IXP)的核心網絡設備中廣泛部署[1]。報文分類的目的是根據網絡報文頭部的多個字段值來區分報文類型，從而對報文執行相應的差異化操作。

報文分類解決方案可分為兩大類：硬件方案和軟件方案[2]。其中基于三態內容可尋址存儲器(ternary content addressable memory，TCAM)的硬件方案[3-6]在行業中占據主導地位，其利用TCAM將所有規則存儲在相聯存儲器中，然后將報文與這些規則并行匹配，優點是提供了常量的分類時間、實現了線速查找，但存在高成本、高功耗、可擴展性較差等缺點[7]。軟件方案主要有決策樹算法、元組空間搜索算法[8-10]等，其中決策樹算法由于具有吞吐量高、適用于多字段和可流水線化[11]等特點，被認為是最有希望替代TCAM方案的方案之一。

由于報文分類具有重要的研究和實用價值，近十年一直是人們的研究熱點。并且網絡帶寬的持續增長和網絡應用復雜性的不斷增加[12]，給報文分類帶來了高維度和動態性等新挑戰，研究人員仍在尋求新的、更高效的報文分類解決方案。近年來決策樹報文分類算法研究取得了重要進展，新的算法層出不窮，并且出現了跨領域的趨勢，例如與機器學習結合取得了初步成果，但是相關研究的綜述性文章[13-15]并未涉及決策樹算法新的研究進展，對近年來優秀的研究成果也缺乏系統的分析與總結。

為進一步推動基于決策樹的報文分類算法的研究與發展，本文從節點切割技術、規則集分組技術兩個維度對決策樹算法進行了系統的分析和總結，并對比了各類算法的設計思路和特點。

1 決策樹算法分析

1.1 報文分類問題

報文分類器含有一個規則列表，其中每條規則由優先級、匹配域(match field)和匹配報文時采取的動作(action)組成。報文分類問題是從規則列表中找到報文所匹配的規則，并返回其中優先級最高的匹配規則。

對報文分類問題的正式定義[16]如下：

規則列表中含有n條規則，每條規則由d個匹配域(維度)和動作域組成，其中每個匹配域f[i](1 ≤i≤d)都是關于報文頭部的第ith字段的表達式。表達式的形式可以為精確匹配、前綴匹配或范圍匹配形式。如標準IPv4五元組中的源和目的IP地址屬于前綴匹配，源和目的端口號屬于范圍匹配，協議類型則屬于精確匹配。

如果?i(1 ≤i≤d)，報文P的第ith報頭字段值都能滿足規則Rt(1 ≤t≤n)的第i個匹配域f[i]，則認為報文P與特定規則Rt匹配。如果報文P同時匹配了多條規則，則返回優先級最高的匹配規則。

表1給出了含有6條規則的二維分類器示例。其中每個維度的位寬為4，“*”表示通配符，優先級數值越小的規則對應的優先級越高。

表1 二維分類器示例

1.2 算法基本思想

報文分類問題可等價為計算幾何中的多維空間點定位問題，即報文頭部中的字段(如源和目的IP地址、源和目的端口號以及協議類型)表示幾何空間中的維度，報文被表示為該空間中的點，而規則被表示為空間中的超立方體。然后，報文分類問題等價于找到包含點(報文)的優先級最高的超立方體(規則)：如果報文P與特定規則R匹配，則表示報文P的點將落入規則R指定的超立方體中。

經過數學推導[17]，在具有n個互不重疊的超立方體的d維幾何空間中，當d>3時，多維空間點定位問題理論上具有O(log2n)時間復雜度和O(nd)空間復雜度，或者具有O(log2n)d-1時間和O(n)空間復雜度。而對于五元組或更高維度的報文分類，這兩個選擇都不具吸引力。因此，需要采取有效的數據結構來組織規則集，決策樹算法便是理想的選擇之一。

在基于決策樹算法的方案中，對報文分類問題采取幾何視圖，并構建決策樹。樹的根節點覆蓋了包含所有規則的整個搜索空間，然后遞歸地將搜索空間切割為更小的子空間，直到每個子空間包含的規則數不大于預定義的閾值時停止切割，并將當前子空間對應的節點設為葉節點。如果規則了跨越多個子空間，則在切割時會發生不必要的規則復制。當有報文到達時，基于報文頭部字段中的關鍵字值遍歷決策樹，以在葉節點處找到匹配規則。表1中的二維規則集對應的幾何視圖如圖1所示。

圖1 表1中規則集的幾何視圖Fig.1 Geometric view of rules in Tab.1

1.3 算法類型

現有報文分類問題解決方案主要分為硬件方案和軟件方案，基本框架如圖2所示。

其中硬件方案主要有TCAM和位向量[18-19]，決策樹算法屬于軟件解決方案。構建決策樹有兩類常用技術：節點切割和規則集分組。

1.3.1 節點切割

節點切割基本思想是將整個多維規則集視為樹的根節點，然后沿一個或多個特定的維度切割節點構建決策樹。算法從包含所有規則的根節點開始，迭代地切割節點，直到每個葉節點包含的規則數不大于預定義的閾值時停止切割，從而構建單棵決策樹。各類決策樹算法在節點切割方面的主要區別為：

圖2 報文分類解決方案的基本框架Fig.2 Basic framework for the solution of packet classification problems

1)切割維度的選擇。選擇哪個維度切割最優；一次選擇單個維度還是多個維度進行切割。

2)切割端點的選擇。包括對節點進行等分切割或者等密切割。等分切割能快速將節點等分為2n個子節點，但會帶來嚴重的規則復制問題，即同一條規則分布在多個子節點中；而等密切割能夠緩解規則復制問題，但也存在樹深度增加、節點索引復雜等問題。

此外，新提出的比特切割技術使用比特級視圖(bit-level view)，利用規則每一位都可表示為0、1或者*(通配符)的特點，選擇其中有效比特將規則映射到各個子節點中，從而避免了盲目地切割整個搜索空間。從另一個角度看，等分切割也是一種特殊的比特切割，但只允許使用連續的最高有效位。

1.3.2 規則集分組

事實上，規則集中部分規則之間存在明顯的差異。對訪問控制列表(access control list, ACL)、防火墻(firewall, FW)和IP鏈(IP chain, IPC)類型規則集進行統計分析，結果如圖3所示。從圖中可得，IP地址字段前綴長度為邊緣分布，即大部分位于0附近或32附近。

(a) 源IP地址前綴分布(a) Distribution of source IP address

(b) 目的IP地址前綴分布(b) Distribution of destination IP address圖3 地址前綴分布Fig.3 Distribution of address

因此不加任何區分直接切割整個搜索空間將導致嚴重的規則復制，其中一個解決方案便是分治思想，即將具有相似特征的規則放到一個規則子集中，然后應用節點切割技術為每個子集單獨構建決策樹，最后形成多棵決策樹。規則集分組的主要方法有：

1)按字段大小分組。根據規則在每個字段覆蓋的范圍來劃分規則子集，該類方法應用最廣泛。

2)按前綴長度分組。根據規則在特定字段的前綴長度來劃分規則集。

3)基于聚類算法分組。使用聚類算法來劃分規則子集。

4)基于深度神經網絡模型分組。將機器學習技術應用到報文分類問題中，如使用深度神經網絡模型來學習優化節點切割和規則集分組，以獲得最大的獎勵函數(分類速度、內存消耗等)，從而構建性能優異的決策樹。

按字段大小、前綴長度分組等啟發式策略建立在對規則集分布特征觀察的基礎之上，原理相對簡單、容易實現，但對于不同的規則集，往往需要手動調整部分參數以獲得理想結果；聚類算法、神經網絡模型則可以使用機器學習來替代人工調整，實現對規則子集的自適應劃分，但需要經過大量的訓練和迭代才能收斂。

1.4 面臨的挑戰

設計高效的決策樹算法面臨的最大挑戰是規則復制問題和數據結構更新問題。

決策樹算法犧牲了線性空間來獲得較高的分類速度，是典型的以空間換時間。規則復制問題是困擾決策樹類型解決方案的主要問題之一，早期的決策樹算法在規則集規模較大的時候產生大量規則復制，甚至耗盡系統內存。規則集分組技術的主要目的就是解決規則復制問題。

決策樹算法存在的另一大挑戰是規則更新速度較慢。在軟件定義網絡中，虛擬交換機得到大規模部署，目前主流的虛擬交換機如Open vSwitch，要求算法的數據結構規則更新時間復雜度為常量級別，即時間復雜度為O(1),因此采用了優先級元組空間搜索(priority sorted tuple space search, PSTSS)算法。而決策樹算法由于存在規則復制問題，導致數據結構更新困難，甚至在更新時需要重新構造決策樹。更新速度較慢已經成為限制決策樹算法應用的關鍵因素之一。

決策樹算法目前的研究熱點是在保證算法性能的基礎上，解決規則復制問題和更新速度問題，在算法吞吐量、內存消耗和更新速度等重要指標之間取得更好的折中。

1.5 測試基準

報文分類算法的測試基準為ClassBench[20]和ClassBench-ng[21]。

ClassBench是2007年由Taylor等提出，用于對報文分類算法進行基準測試的開源工具。ClassBench能夠接收規則集參數配置文件，生成精確模擬實際規則集分布特征的規則集。ClassBench中共提供了12個參數文件，支持生成ACL、FW和 IPC三種類型、不同規模的IPv4 五元組規則集。此外，ClassBench還能夠針對規則集生成特定長度的報文頭部序列，以對算法性能進行測試。

IPv6協議和軟件定義網絡(software defined network, SDN)技術的發展給報文分類問題帶來了新的挑戰，而ClassBench僅支持生成IPv4環境下的規則集。針對這一問題，Matou?ek等于2017年提出了新的開源基準測試工具ClassBench-ng，能夠生成IPv4、IPv6規則集和OpenFlow[22]1.0流表。此外，ClassBench-ng還提供了一種從實際規則集提取參數文件的機制，并可上傳至ClassBench-ng工具庫，以生成不同應用環境下的規則集，適應不同研究人員的需求。

2 基于節點切割的單棵決策樹

節點切割技術采用幾何視圖，將包含所有規則的整個搜索空間視作根節點，利用啟發式等策略選擇合適的切割維度和端點切割當前節點，獲得子空間，然后遞歸地將搜索子空間分解為更小的空間，直到滿足特定條件停止遞歸，最終構建基本的單棵決策樹。節點切割方案主要有等分切割、等密切割和比特切割。

2.1 等分切割

HiCuts算法[23]是由Gupta等提出的最早用于報文分類的決策樹算法，一次選擇單個切割維度來等分規則空間，目的是將規則盡可能均勻地分離到樹的葉節點中。HiCuts從覆蓋整個規則空間的根節點開始，在單個維度上切割搜索空間，以創建一組大小相等的子空間。HiCuts算法中應用了多種啟發式策略來選擇最優的切割維度和切割次數。

HiCuts算法存在兩個主要缺陷：首先， HiCuts算法僅考慮在一個節點處切割一個維度，這將增加樹的深度，從而增加了樹遍歷所需的時間。其次，算法在構建決策樹后存在大量的規則冗余，消耗了大量內存。針對上述缺陷， Singh等提出了HyperCuts算法[24]，改進了樹的深度和內存消耗問題。HyperCuts算法提出同時切割多個維度，而不是在一個節點處只切割單個維度，從而減少了樹的深度。其次，HyperCuts提出了公共規則向上推送的優化方法，允許將所有同級子節點通用的規則向上移動到父節點處，以緩解規則復制問題。

HyperCuts算法雖然在一定程度上緩解了樹的深度較大和規則復制問題，但仍存在相當大的規則冗余，尤其是對于大規模的規則集。其問題在于等分切割本身的局限性，即等分切割適用于規則分布均勻的場合，而實際上規則集的分布并不是均勻的。

2.2 等密切割

針對HiCuts和HyperCuts算法等分切割搜索空間導致大量規則冗余的問題，Qi等提出了HyperSplit算法[25]。HyperSplit的思想是構建一個平衡的二叉樹，以便規則均勻地分布在其子節點中，并沿著規則邊界進行切割，從而防止過多的規則復制。HyperSplit算法在每個內部節點處采用啟發式策略選擇一個最佳的切割維度和切割端點，將搜索空間拆分成兩個大小不等的子空間，其中包含的規則數近似相等。選擇切割端點的策略包括規則平衡、范圍平衡和加權分段平衡。

HyperSplit算法提出了等密切割的思路，進一步緩解了規則復制問題，但由于算法構建的決策樹為二叉樹，且每次只能判斷一次維度，因此隨著規則集規模的擴大和維度的增加，樹的深度也會增加，相應的遍歷決策樹所需的訪存次數也將增加。

2.3 比特切割

Liu等提出的BitCuts算法[26]是對節點切割技術一次新的嘗試。不同于等分切割和等密切割算法，BitCuts算法充分利用了規則的二進制特點，即對于精確值和前綴表達式的字段，其每一位取值均為0、1或*，而范圍表達式可轉換為前綴表達式，然后通過貪心策略迭代地選擇其中的有效比特，將規則分離到葉節點中。

BitCuts算法利用了規則的二進制特點，迭代地選擇有效比特來構建決策樹，在內存訪問次數上相比HiCuts、HyperCuts和HyperSplit算法有了大幅度減少，因此吞吐量更高。但比特選擇策略的效率很大程度上決定著算法性能。典型的比特選擇策略有暴力策略、啟發式策略等。

對表1中的規則集分別使用HiCuts算法、HyperCuts算法、HyperSplit算法和BitCuts算法構建決策樹，結果如圖4～7所示，其中葉節點中最多可包含的規則數量為4。采用不同節點切割方案的決策算法設計思路及特點如表2所示。

圖4 HiCuts算法構建的決策樹Fig.4 Decision tree built by HiCuts

圖5 HyperCuts算法構建的決策樹Fig.5 Decision tree built by HyperCuts

圖6 HyperSplit算法構建的決策樹Fig.6 Decision tree built by HyperSplit

圖7 BitCuts算法構建的決策樹Fig.7 Decision tree built by BitCuts

表2 節點切割的決策樹算法

總的來說，三類節點切割算法中，等分切割優點在于簡單快速，分類速度較快，但是內存消耗較大，適用于對分類速度要求高而對內存消耗不敏感的場景。而等密切割則在內存消耗方面占有優勢，但算法吞吐量有所下降，適用于對內存要求嚴格的場景。比特切割是一種更新穎和靈活的切割算法，在時間性能和空間性能之間實現了更好的折中，能夠以合理的內存消耗提供較高的分類速度。

3 基于規則集分組的多棵決策樹

研究人員在節點切割技術方面開展了深入的研究，充分挖掘了單棵決策樹的性能，但仍無法有效解決規則復制問題。針對單棵樹的固有缺陷，提出了規則集分組的想法。根據規則集的某些特征來劃分子集，將具有相似特征的規則放在一個子集里單獨構建決策樹，最終形成多棵決策樹。將規則集分成子集的規則集分組技術可減少每個子集中的規則重疊，從而改善單棵樹中嚴重的規則復制問題。

規則集分組的主要方法有：按字段大小分組、按前綴長度分組、基于聚類算法分組和基于深度神經網絡分組。

3.1 按字段大小分組

EffiCuts算法[27]是使用規則集分組最具代表性的算法。EffiCuts算法基于兩個關鍵結論：①規則大小的變化：規則集中有許多規則重疊，重疊的規則在大小上差異很大。因此，具有重疊的小規則和大規則的單棵樹需要精細切割來分隔小規則，但會復制大規則。②規則空間密度的變化。針對重疊規則大小變化的情況，EffiCuts算法提出了“可分離樹”的思想，通過將小規則和大規則放在不同的樹中減少復制，再應用HyperCuts算法為每個子集構建決策樹。例如對于圖2中的6條規則，可根據規則在X、Y兩個域上的大小，分為4個子集{R1，R2}、{R3，R4}、{R5}和{R6}。

對于字段大小的區分，算法通過規則投影到每個字段上的覆蓋區間的大小來界定，定義了一個稱為大分數(largeness fraction)的分界點，一般情況下取值為0.5。對于d維規則集，EffiCuts算法最多能產生2d個子集，呈指數級別增長。EffiCuts算法雖然考慮子樹過多的情況，采用子樹合并方法來消除部分子樹，但仍然會生成大量的子樹，這將導致較多的內存訪問次數，不利于算法的擴展。使用EffiCuts算法為表1中的二維規則集構建的決策樹如圖8所示。

圖8 EffiCuts算法構建的決策樹Fig.8 Decision tree built by EffiCuts

HybridCuts算法[28]和SmartSplit算法[29]針對EffiCuts算法中子類別過多的問題進行改進。在這兩個算法中僅使用了源IP地址和目的IP地址兩個字段而不是全部的字段來劃分規則集，限制了規則子集的數量最多為4。

Li等將按字段大小分組擴展到OpenFlow等多維規則集，提出了CutSplit算法[30]。CutSplit的基本思想是基于很少的幾個字段對規則集進行分組，然后預切割和后拆分結合構建決策樹。CutSplit算法的框架如圖9所示。

圖9 CutSplit算法框架Fig.9 Framework of CutSplit

算法具體實現為：根據小的維度將整個規則集劃分為若干子集，劃分依據是從F維中挑選前m個包含最多的小規則數量的維度，保證這m個小維度覆蓋絕大部分的規則(≥95%)，并且在算法中定義了閾值向量，使得規則“大”“小”定義更多靈活；在劃分子集后，對每個子規則集運用簡單、快速的固定小字段等分切割，以得到更小的子空間；對每個子空間運用HyperSplit算法，以盡量減小冗余并且達到最壞情況下的有界性能。

CutSplit算法相比EffiCuts算法，通過精心挑選少數維度劃分規則子集，性能有了改善，但存在切割和拆分的邊界難以確定、算法性能不穩定等缺點。

TabTree算法[31]是繼CutSplit算法之后的一項新的研究成果，其規則集分組方法類似CutSplit，但對于每個子集使用了平衡位選擇的方法來構建決策樹，而不是預切割和后拆分的組合，從而實現了高速分類和規則快速更新。

3.2 按前綴長度分組

Daly 等提出的ByteCuts算法[32]，根據規則在IP地址字段的前綴長度來劃分規則子集。算法將具有相同的核心位集合的所有規則放在同一樹中，然后對單棵樹使用字節切割(以半字節為單位的比特切割)構建決策樹。ByteCuts算法對子樹數量與子樹大小之間的平衡進行了深入研究：子樹數量過多會導致訪存次數增加；過少會使得單棵樹的體積大，從而在單棵樹內部產生更多的規則復制。ByteCuts算法定義了兩個閾值：切割效率(決定子樹內部沖突率)和樹大小，目標是最大化樹中規則的數量(最小化樹的數量)，同時滿足一定的平衡要求。

算法具體實現為：通過兩個閾值(切割效率和決策樹大小)來選擇字段長度對(f，Wf)；然后將為字段f上前綴長度至少為Wf的所有規則放入同一個子集中，并創建單個決策樹；對剩下規則重復該過程，直到剩余規則的數量低于某個特定閾值τ(如5%)停止。

ByteCuts算法因以半個字節為單位切割搜索空間，構建決策樹數據結構所需時間較短。此外，算法還具有較強的靈活性，可通過調整閾值參數在時間性能和空間性能之間取得較好的折中。

3.3 基于聚類算法分組

Fong 等提出的ParaSplit算法[33]的基本思想是使用聚類算法劃分子集，然后對每個子集使用HyperSplit 算法構建決策樹。ParaSplit算法首先使用范圍-點轉換算法，通過將每個字段的起點和終點視為單獨的維度，從而將F維空間中的超矩形轉化為2F維空間中的點(F維規則被表示為2F維空間中的點)。然后利用K-means聚類算法有效劃分規則子集，應用模擬退火算法來尋找最優劃分，并對每個子集使用HyperSplit算法構建決策樹。在使用K-means聚類算法劃分子集時，提出了最小距離、最大距離和距離原點距離三種啟發式策略，其中最小距離策略的性能更優。

ParaSplit算法通過聚類算法實現了規則集的自適應劃分，但K-means算法的性能受初始k個中心點的選擇影響較大，且算法需要上萬次的迭代才能獲得理想結果，預處理時間較長。

3.4 基于深度神經網絡分組

NeuroCuts算法[34]使用了深度神經網絡模型來學習構建高效的決策樹，算法框架如圖10所示。神經網絡模型的環境由規則集和當前決策樹組成；代理使用一個神經網絡模型，選擇最佳的切割或規則集分組操作來增量地構建樹；當前節點的可用操作(節點切割或規則集分組)在每個步驟由環境通告，代理選擇其中一個操作生成決策樹。隨著時間推移，代理學會優化其決策，以最大化從環境中獲得的獎勵函數，最終構建性能優異的決策樹。獎勵函數可以是分類速度、消耗內存或兩者的結合。NeuroCuts算法在訓練過程中使用了馬爾可夫決策過程，并且結合了已有的研究成果，如按字段分組等策略。

圖10 NeuroCuts算法框架Fig.10 Framework of NeuroCuts

NeuroCuts算法在報文分類和機器學習結合方面開創先河，是一次有益的大膽嘗試，有助于啟發新一代基于機器學習的分類算法。

表3給出了采用不同規則集分組方案的決策樹算法的設計思路和特點。總的來說，按字段大小分組和按前綴長度分組原理簡單，容易實現，較好地利用了規則集的幾何分布特征，達到了較好的性能，且更新速度也有優勢。但缺點在于需要自定義閾值參數，且在面對不同的規則集時可能需要重新調整參數。按字段大小分組適用于規則集更新頻繁，或者面向特定應用領域和特定規則集的場景。

表3 規則集分組的決策樹算法

而基于聚類算法分組和基于深度神經網絡分組則將報文分類問題與機器學習較好結合在一起，利用機器學習技術來解決經典的網絡問題，實現了規則集的自適應分組，通用性較強。但預處理速度較慢，往往需要大量的計算和迭代才能收斂，從而獲得理想的性能。適用于規則更新頻率較低，但對算法性能要求較高的場景。

4 決策樹算法研究方向

網絡技術的進步以及網絡應用的復雜性和多樣性，給報文分類帶來了新挑戰，研究人員仍致力于提出更高效的決策樹報文分類算法。決策樹下一步的研究方向主要有以下四個方面：

一是節點切割技術創新。利用規則集分布特征，提出新穎的、更高效的節點切割技術或者規則集分組技術，例如新的比特切割技術等。目前常用的有效比特選擇標準有規則可分離性[26]、子節點內規則數量最少化[35]、信息熵[36]和子節點內規則數量平衡[37]等，但以上方法存在預處理時間較長、容易陷入局部最優等缺點，因此研究更好的比特切割技術，有助于提升決策樹算法的時間性能和空間性能。

二是規則集分組與節點切割技術結合使用。根據各類規則集分組技術與節點切割技術的特點，積極嘗試將它們結合使用以得到性能更優的決策樹，這是當前研究的熱點，新的研究成果也多集中在該方向上。如按字段大小分組與等分切割結合使用能夠取得較好效果[30]，而按前綴長度分組后則更適合使用比特切割來構建決策樹。

三是異構的算法架構。即各類軟件方案、軟件方案和硬件方案的結合使用。如Partition Sort算法[38]就充分利用了元組空間搜索(tuple space search, TSS)算法和決策樹算法的優點，從而兼顧了決策樹算法的高吞吐量和TSS算法的快速更新。CutTSS算法[39]則創造性地將等分切割與元組空間搜索算法結合使用，因此能夠同時支持高速分類和快速更新。此外，軟硬件協同處理也是一個研究熱點，首先設計高性能的決策樹算法，再將決策樹映射到FPGA等硬件平臺上[40-41]，利用硬件大規模并行、流水線架構的特點來提升算法性能，以兼顧軟件算法靈活性和硬件高性能的優點。

四是跨領域研究。將決策樹算法與機器學習等技術結合，借助于其他領域的專業知識來解決報文分類問題。如使用深度神經網絡模型學習構建高效的決策樹是一個新的研究方向，對神經網絡模型的研究和改進也有助于提升決策樹算法的性能。

5 結論

本文主要介紹了最新的決策樹研究成果，從節點切割和規則集分組技術兩個方面對決策樹算法進行了系統分析和總結。總的來說，構建單棵決策樹的技術主要包括等分切割、等密切割和比特切割等，已經得到了較為深入的研究。規則集分組技術主要包括按字段大小分組、按前綴長度分組、基于聚類算法分組和基于深度神經網絡分組等，目前仍是研究熱點。一個好的規則集分組方案能夠有效解決困擾決策樹算法已久的規則復制問題，同時提高算法的數據結構更新速度，從而提升算法的應用價值。

隨著網絡帶寬的持續增長和網絡應用復雜性的不斷增加，決策樹報文分類算法的發展趨勢是更高的吞吐量、更小的內存消耗和更快的更新速度，并支持高維度擴展，尤其是在數據中心等規則集頻繁更新的應用環境中，算法的更新性能顯得越來越重要。