聯合元組空間和位圖設計的二維分組分類算法

謝鯤，趙姣姣，張大方

（湖南大學 信息科學與工程學院，湖南 長沙 410082）

1 引言

隨著新型網絡設備及新型網絡服務的提出和發展，傳統單維分組分類算法已不能滿足網絡應用和服務的需求，多維分組分類算法成為分組分類技術研究的重點。多維分組分類算法將IP分組頭多個域的信息在相應的規則庫中進行多維匹配，以獲得匹配規則。網絡設備根據匹配規則中對應的策略對數據分組采取相應的措施，以完成相應的新型服務。

維度分解是解決多維分組分類問題的基本方法。利用維度分解，多維分組分類問題首先被分解成多個簡單一維匹配問題，然后通過某種數據結構，將多個一維的匹配結果相關聯得到最終的匹配規則。現有的基于維度分解的多維分組分類算法主要有：ABV[1]算法，P2C[2]算法和RSFR算法[3]。

ABV算法為每一維SIP、DIP分別建立Tire樹結構，在掛規則的Tire節點中存放一個Nbit的向量，以標示規則庫中與該節點相匹配的所有規則（N為規則條數）。對每維處理后，取出各維匹配節點的Nbit向量，求交集得到最后匹配結果。ABV主要依據Nbit向量關聯出最后結果，然而每個規則節點均需要存儲Nbit向量，空間占用大，不易擴展到大規模規則庫。P2C算法在維度分解后利用硬件TCAM（ternary content addressable memory）[4]來解決單維到多維的關聯，匹配速度快，但是需要耗費硬件資源來支撐，并且TCAM存在高功耗、價格高、集成度低等缺點，只能用于小規模規則庫。RSFR算法采用元組空間 （TS, tuple space）[5]進行算法設計，其核心是用規則重編碼對 RS算法[5]進行改進。RSFR首先對各維進行一維處理，而后利用RS算法查找結構關聯出最終結果。RSFR時間性能較其他多維分解算法優越，易于向大規模規則庫擴展。然而RSFR算法為了減少訪問元組空間的個數，提高匹配速度，除了對規則重編碼外，還需要兩項復雜的預處理操作：插入偽規則和計算每條規則的BMP（最優匹配規則）。這使得RSFR空間耗費過大，需要存儲真實規則和偽規則（最壞情況需要插入40%×N條偽規則（N為規則數目）），還有每條規則的 BMP（BMP作為規則的屬性存放）。另外，規則庫更新復雜度也增加，增加刪除規則都需要處理所需的偽規則，并重新計算所有受影響的BMP。

一方面，維度分解可降低多維分組分類算法的難度，算法的整體性能取決于關聯數據結構的設計，因此，如何設計高效的關聯數據結構，以聯合各維匹配結果得出最終匹配規則成為高效多維數據分組分類算法設計的關鍵。另一方面，現有研究表明，大規模規則庫中與前兩維匹配的子規則庫規模非常小，處理多維分組分類可以首先進行二維分組分類[6]（二維分組分類通常根據 IP分組中的源IP（SIP）、目的IP（DIP）2個域進行規則匹配），而后在規模有限的子規則庫中對其他維進行簡單的線性匹配即可。

本文從維度分解出發，設計并實現了一種新的二維分組分類算法（TB, joint tuple space and bitmap）。TB將元組空間和位圖相結合作為一維匹配后的關聯結構，并利用交叉組合思想形成需要訪問的TS路線，利用位圖過濾減少需要訪問的TS數目，可以高效快速的匹配出最終結果，并且可以克服RSFR算法的缺點。TB算法結構簡潔，易于實現，具有良好的時空性能。另外，TB預處理操作簡單，規則庫更新較易且具有良好的擴展性能。

本文的行文安排為：第2節介紹TB算法設計的基本思想，第3節對TB算法各部分進行具體實現，第4節分析TB算法的性能，第5節從不同場景實驗測試TB算法的性能，第6節是結束語。

2 TB設計的基本思想

TB算法結構框架如圖 1所示。算法可分為 3部分，第1部分：分別對SIP、DIP進行AMP匹配，并利用前綴長度交叉組合成TS。第2部分：在位圖上驗證交叉元組空間是否存在，過濾掉不存在的TS。第3部分：在通過位圖驗證的相應TS中進行查找以獲得最終匹配的多維規則。

圖1 TB算法結構

TB算法包括以下3點基本設計思想。

1) 維度分解設計思想。

TB算法的第一部分分別對SIP、DIP進行所有匹配規則的查找即求AMP。不同于RSFR算法中只求最長前綴匹配（LMP, longest prefix match），TB算法不僅求LMP，還要求出所有和SIP、DIP匹配的嵌套子規則（如果規則Px是規則Py前綴的子串，則稱Px為Py的一條嵌套子規則）。如圖2所示，若 SIP匹配的 LMP為規則 P4，TB算法第一步AMP(SIP)的結果為 P4、P3、P1。

圖2 規則編碼實例

2) 利用規則庫嵌套特征進行優化設計。

基于規則庫嵌套原理，TB算法有2處設計：第一，對于一維的AMP結果，進行交叉組合。第二，引入規則重編碼，減少TS的個數。

在真實規則庫中，單維規則最大嵌套層次數目（稱為S）遠遠小于規則中不同前綴長度的個數，S一般小于3，最壞情況下為5。例如規則0*和規則0100*都是規則010000*的嵌套子規則，且嵌套層次為3。換句話描述，對一個IP分組的SIP或者DIP進行單維的AMP匹配，AMP中包含的規則數目即為S，因此可知AMP規則數目與嵌套層次相同一般小于3。這就是規則嵌套的基本特征。文獻[1,3,7,8]均調研得出如此結論，且此結論也用在許多經典的算法設計中[1,6,9]，本文通過實驗也證明了此特征。

基于規則的嵌套特征，TB算法運用交叉組合思想進行算法設計。第一部分對SIP、DIP求得AMP后，分別取 SIP、DIP各個匹配規則的前綴長度，將其交叉組合成元組空間，由于S數目很小，因此交叉組合形成的TS個數也很小，一般小于9最壞情況下為25，下一步只需要在這些數目規模有限的TS中進行訪問，時間性能得到第一步保證。因為和二維均匹配的規則必在這些交叉元組空間中，這是TB算法關聯各維結果后形成的TS訪問路線。例如SIP的AMP長度為2、3，DIP的AMP長度為1、4，那么交叉組合形成的TS分別為TS（2，1）、TS（2，4）、TS（3，1）、TS（3，4），在這些 TS 中訪問一定可以找到與二維均匹配的最優規則。

為減少所需形成TS的數目，TB算法還引入規則重編碼設計。規則重編碼思想廣泛應用于分組分類算法設計中，因為重編碼可以大大降低形成的元組空間個數，減少交叉元組空間在位圖上的命中率，提高匹配速度。在TB中，根據規則P所有嵌套子規則的前綴長度，將規則P分成多個子串，并歸入不同的層次。為了理解編碼過程，圖2是取自文獻[3]的編碼實例，規則P4（010000）有2個嵌套子規則分別為P1（0）、P3（0100），因此，將P4 分為3 個位串＜0＞＜100＞＜00＞，將這3個位串分別歸入第一層，第二層和第三層。對所有規則如此處理后，為每一層的位串賦予新的 ID如圖2所示，規則新的編碼為連接該規則在各層相關位串的新ID。例如規則P4編碼后為（0000100）。可見，編碼后規則不同長度的數目將大大減少，即從W（W為IP地址的長度）降低為規則庫的最大嵌套層次數S。RSFR算法正是基于此將RS的時間性能從O(2W?1)提升為O(2S?1)。圖2中，實例規則庫的嵌套層次為3，編碼后規則不同長度個數由7降至3，長度分別為2、5、7。

3) 元組空間和位圖相結合的關聯結構。

在進行多維關聯數據結構設計時，交叉組合形成的TS并不一定真正存在，為了進一步減少訪問TS的個數，利用位圖技術來對所需訪問的TS進行空間的過濾。若沒有通過位圖，則不需要訪問對應TS；若通過位圖，則在相應的TS中查找所匹配的規則。位圖技術是TB算法時間性能的第二步保證，結合規則庫嵌套原理使得TB算法在平均時間性能上仍優于RSFR算法。

3 TB算法具體實現

圖1給出了TB算法的匹配數據結構框架，本節具體說明算法3個部分的實現。

算法第1部分，分別求出與IP分組的SIP、DIP匹配的所有規則，此部分需要一個查找AMP的一維包匹配算法。TB算法與RSFR算法一樣均采用文獻[10]提出的BSH（binary search on hash table）算法實現。BSH算法是一維分組分類算法，根據IP分組的SIP或者DIP在散列表上進行折半查找，最終查找出與一維地址匹配的最長匹配規則即LMP。文獻[10]指出 BSH算法一次查找最多需要lbW次散列訪問，W為IP地址的位寬。因此對于IPv4最多需要lb 32，即 5次散列訪問，對于 IPv6需要lb128即7次。本文采用BSH一是便于與RSFR比較，因為2個算法該部分均可根據需要換取效率更高的一維匹配算法，二是BSH算法查找性能較好，訪問內存次數只與IP地址位寬有關，與規則庫大小無關，因此易于向大規模規則庫和IPv6擴展。

然而BSH是針對LMP的一維算法，TB需要的一維匹配算法需要匹配出AMP。因此，在TB算法設計中，將規則重編碼思想和 BSH相結合，以得到AMP結果。算法在規則重編碼階段已經記錄了編碼后所有規則的長度，如圖2實例中，編碼后不同規則長度數目為 3，分別為 2、5、7，因此當求得SIP、DIP的LMP后，可根據此LMP的前綴長度以及編碼后所有規則的長度，直接求得AMP，例如在圖2中若某SIP的LMP規則為P4，其長度為7，則與此SIP匹配的所有AMP的長度一定分別為2、5、7，具體值即為取P4的前2、5位組成的規則，即 P1、P3。然而在 TB算法中只需要記錄AMP規則的長度即可。因此采用BSH算法實現TB算法第1部分，則TB算法和RSFR算法此部分內存訪問次數相同。

算法第2部分，采用位圖標識各個TS的存在狀態，對于IPv4，所有可能的規則前綴長度為從0到32，因此所有可能形成的TS個數為33×33。因此位圖的大小設為 33×33bit，稱之為bitMap[33][33]。位圖初值為0，標識各TS不存在，即沒有規則屬于此TS。當將編碼后形成的規則放入對應的TS時初始化位圖相應位置的值為1，標識此TS存在。例如二維規則（0000100*，01011*）屬于TS（7,5），設位圖bitMap[7][5]值為true即為1。將第一部分形成的交叉元組在位圖上進行過濾查找時，相應位置為0則過濾掉，不必進行算法第3部分查找。位圖結構簡單，可以用軟件或者硬件實現，若用片上硬件實現，則可加快驗證速度。

算法第3部分，需要在通過位圖的相應TS中進行查找，在具體一個TS中用散列進行匹配，算法時間性能取決于訪問TS的個數，因此本文記錄算法訪問TS的個數。

圖3是TB算法具體匹配過程的實例，算法匹配過程非常簡潔：對于某IP分組，若匹配出SIP的AMP分別為規則P4、P3、P1，由圖2可知這些規則編碼后對應的長度分別為7、5、2，同樣對于DIP，P14、P12對應的長度為 5、2，利用這些規則長度交叉組合成 6個 TS 分別為 TS（7，5）、TS（7，2）、TS（5，5）、TS（5，2）、TS（2，5）、TS（2，2）。而后，將上述6個TS在位圖上過濾，位圖相應位置為1表明此TS存在，則在該TS中匹配，若匹配到即將此規則作為當前IP分組匹配的最優規則，若后續在其他TS中匹配到優先級更高的規則，則替換，最終找到最優的匹配規則。

圖3 TB算法分組匹配實例

4 TB算法性能分析

本節分析TB算法和RSFR算法時空需求并比較各方面的性能。TB算法空間需求為：BSH算法空間+位圖+TS中規則，RSFR空間為：BSH算法空間+RS算法空間（包括偽規則和規則）；TB算法內存訪問次數為：AMP（SIP）.access + AMP（DIP）.access+交叉組合形成的元組空間中通過位圖即存在的元組空間個數，其中access表示相應算法的訪問內存次數。RSFR算法內存訪問次數為：LMP（SIP）.access+LMP（DIP）.acces+RS.access。2 種算法在一維處理上均采用BSH算法，雖然TB求解一維的AMP，RSFR求解一維的LMP，但由上節算法具體實現可知，這部分的內存訪問次數和空間需求與RSFR算法相同，因此時空性能主要取決于第2部分。下面可以暫不考慮一維的開銷，對2種算法性能進行比較分析。

1) 預處理復雜度：TB和RSFR均需要對規則進行重編碼，此外，TB預處理中只需要將每條規則存放入相應的元組空間，并根據形成的元組空間初始化位圖。而RSFR除了存放規則外，還需要插入需要的偽規則，并計算各條規則的 BMP規則。顯然TB預處理操作簡單，所需時間少。

2) 更新復雜度：TB算法不需要RSFR中2項復雜的預處理，因此規則庫更新較易，因為不需要為增加刪除規則處理偽規則，并重新計算所有受到影響的BMP。

3) 空間占用：TB算法只需要在TS中存儲規則，不需插入任何偽規則，也不需要在預處理中為規則存放 BMP，大大降低了空間耗費。TB算法中增加的位圖空間相比RSFR中插入的很多偽規則，空間占用非常小，TB空間性能大大優于RSFR。

4) 時間性能分析：2種算法均不考慮2個一維匹配過程，對于RSFR算法最多訪問元組空間個數為O(2S?1)（S為規則庫嵌套的最大層次），TB算法第一部分求出AMP的個數分別為S，交叉組合形成的元組空間個數為S×S，算法需要訪問的元組空間個數最多為O(S×S)。但是由規則嵌套特征可知S數目很小，因此O(S×S)不會非常大于O(2S?1)。雖然從分析看TB時間性能不如RSFR，但是TB算法通過兩點降低了訪問元組空間的個數，第一，算法采用位圖過濾，S×S個TS中只有標示存在才需要訪問，大大降低了訪問TS的個數。第二，TB算法形成的TS個數少于RSFR算法，因為雖然兩算法均通過規則重編碼使得元組空間個數很少，但是在RSFR算法中仍有一些TS是純粹的偽規則組成，這些TS在TB算法中不存在。分析可知，TB算法的時間性能主要取決于規則庫嵌套層次和位圖的過濾效果，嵌套層次決定了交叉形成的TS個數，位圖過濾決定了真正需要訪問的TS個數。然而實際中，每個數據分組交叉形成的TS中有大部分并不真正存在，可以通過位圖過濾掉。本文實驗仿真的數據是通過多個大規模流量文件測試并取得其平均值，可見TB算法除了空間性能優越外，時間性能通過位圖過濾仍然優于RSFR。

5) 重編碼的依賴程度：重編碼降低了TS的個數，有利于提高匹配速度，然而對算法的更新帶來了困難。RSFR算法的性能完全依賴于重編碼，否則退化為RS算法。而TB算法中就算不引入重編碼，訪問的TS個數由規則庫嵌套原理可知，也是極其有限的，時間性能上不會有很大波動。因此TB算法在設計的選擇上有更大的自由空間。

5 仿真實驗

仿真平臺由C++語言編寫完成，運行環境為：Pentium 4 3.00GHz CPU，512MB內存，Windows XP操作系統。仿真實驗采用PALAC（packet lookup and classification simulator）平臺[11]的流量生成器生成網絡流量。為了有效驗證算法性能，本文采用華盛頓大學開發的ClassBench平臺[8]生成仿真所用的規則庫。ClassBench是一組工具，它將真實的規則庫作為種子，通過高層參數的調控生成符合真實規則庫特征的規則庫，與其他研究中運用路由表生成規則庫相比，能更準確真實的模擬了分組分類算法的運行環境。本文運用ClassBench生成大小不同且類型不同的規則庫，規則庫3種類型分別是 Access Control List（ACL）、Firewall（FW）、IP Chain（IPC）。

實驗中，將論文所提出的TB算法與RSFR算法進行性能比較。5.1節中為了驗證算法在小規模規則庫中運行的性能，規則庫大小為300～6 000條不等。為了驗證算法的擴展性能，在5.2節規則庫大小為5 000～100 000條不等。對這些規則庫進行實驗分析可知它們均符合規則庫的嵌套特征。分組分類算法主要性能衡量指標為時間性能即數據分組匹配速度及算法存儲空間占用2個方面。時間性能方面通過統計各算法的平均內存訪問次數來衡量?？臻g占用方面，統計各算法需要存儲的規則和偽規則，規則的每一維度占用40bit（32bit存儲IP地址，8bit用來表示前綴長度）。需要注意的是，2個算法均統計兩個一維算法 BSH占用的空間，并且對于 TB算法需要統計位圖的空間，RSFR算法需要統計其偽規則所需空間。

5.1 小規模規則庫性能分析

已有研究表明，真實規則庫的大小一般為5 000條左右。首先測試算法在小規模規則庫（300～6 000條）上運行的性能。圖4(a)為TB算法和RSFR算法的平均訪問內存次數，圖4(b)是2種算法空間大小需求。表1統計了2種算法數據結構形成的TS的個數以及最壞的內存訪問次數。

需要指出的是，雖然兩算法第1部分的單維匹配算法可通過并行提高速度，但測試中仍按照串行進行測試，即按照第4節分析的性能公式計算。由圖 4(a)可知，算法 TB平均內存訪問次數優于RSFR算法，平均低于RSFR算法26.6%。注意此平均訪問次數中均包含2個一維算法BSH的訪問次數，而由具體實現可知2種算法一維匹配算法性能相同，因此實驗結果表明若不計算一維算法，TB算法的平均內存訪問次數仍優于RSFR算法。這證明了在第 4節分析的結果，雖然不考慮一維，RSFR算法的訪問次數為O(2S?1)，TB算法訪問次數為O(S×S)，但是TB算法通過位圖過濾和減少 TS個數保證了算法平均訪問次數仍然優于RSFR算法。因為由一維匹配結果交叉形成的S×S個 TS中大部分并不存在，可通過位圖排除，且由表 1統計的 TS個數可知，TB算法不需要插入偽規則，所以不存在由純粹偽規則組成的TS，形成的TS個數少于RSFR算法，有利于降低位圖命中率，提高速度。然而TB算法在最壞內存訪問次數性能方面不如RSFR算法穩定，如表1所示，雖然2種算法最壞訪問次數彼此相差不大，但是RSFR算法較為穩定。這是由于 TB算法最壞內存訪問次數取決于交叉形成的S×S個TS在位圖中的命中率。

圖4 小規模規則庫（300～6 000條）性能測試

表1 TS個數及最壞內存訪問次數

圖4(b)為2個算法空間需求性能比較，由圖可見雖然兩算法都隨規則庫規模增大而線性增長，但是TB算法較RSFR算法節省大量空間，平均降低35.1%的空間需求。因為TB算法不需要插入任何偽規則，且隨著規則庫規模增大空間優勢越明顯。

綜上分析，TB算法在空間和時間性能上均優于RSFR，實驗證明了TS和位圖相結合的優勢。

5.2 大規模規則庫性能分析

圖5 大規模規則庫（5 000～100 000條）性能測試

為了證明算法的擴展性能，測試算法在大規模規則庫下的性能，規則數目分別為5 000～100 000條不等。實驗結果如圖5所示，從圖5(a)可知，TB算法平均內存訪問次數優于RSFR算法，且平均訪問次數隨規則庫規模的增大波動很小，相差不大，最大和最小訪問次數相差為 2，具有良好的擴展性，比RSFR算法擴展性能穩定。仔細分析可知，對于RSFR算法開始的規則5 000～30 000條的訪問次數較高，是因為這些規則庫類型為 Firewall（FW），FW類型的規則庫嵌套層次S比較大，而這對于TB算法影響不大，因為 TB算法中運用位圖結構進行過濾，只有真正存在的 TS才進一步訪問。圖5(b)表明，對于大規模規則庫，空間上TB算法仍低于RSFR算法，且增長速度低于RSFR算法，因為RSFR算法隨著規則庫規模擴大，插入的偽規則條數亦增大。

6 結束語

本文從維度分解設計思想出發，將元組空間和位圖結構相結合作為一維處理后的關聯結構，設計并實現了一種新的高性能二維分組分類算法。TB算法首先進行維度分解，查找各維的AMP，然后運用交叉組合形成元組空間并在位圖上進行過濾，在各元組空間中查找后返回優先級最高的匹配規則。相比于傳統的元組空間算法，TB算法不需要插入任何偽規則，大大降低了算法空間需求，并通過采用位圖過濾技術以及減少元組空間個數，提高了算法的時間性能。論文最后通過在規模不同的規則庫上進行實驗測試，證明了算法TB在空間和時間性能上均優于 RSFR算法，且具有良好的擴展性能。

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

[2]LUNTEREN J V, ENGBERSEN T.Fast and scalable packet classification[J].IEEE Journal of Selected Areas in Communications, 2003,21(4): 560-571.

[3]PI-CHUNG W, CHUN-LIANG L, CHIA-TAI C,et al.Performance improvement of two-dimensional packet classif i cation by filter rephrasing[J].IEEE /ACM Transactions on Networking, 2007, 15(4):906-917.

[4]ZANE F, NARLIKAR G, BASU A.Coolcams: power-efficient TCAMs for forwarding engines[A].Proc of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications[C].San Francisco, 2003, 42-52.

[5]SRINIVASAN V, SURI S, VARGHESE G.Packet classification using tuple space search[A].Proc of ACMSIGCOMM 1999[C].Cambridge,Massachusetts, United States, 1999.135-146.

[6]BABOESCU F, SUMEET S, GEORGE V.Packet classification for core routers: is there an alternative to CAMs?[A]Proc of IEEE INFOCOM 2003[C].Toronho, Ontarion, Canada, 2003, 53-63.

[7]FELDMAN A, MUTHUKRISHNAN S.Tradeoffs for packet classification[J].IEEE INFOCOM, 2000.1193-1202.

[8]DAVID E T, JONATHAN S T.ClassBench: a packet classification benchmarks[A].Proceedings of IEEE/ACM Trans on Networking[C].San Francisco, CA, USA, 2007,499-511.

[9]LAKSHMAN T V, STIDIALIS D.High speed policy-based packet forwarding using efficient multi-dimensional range matching[A].Proc of.ACM SIGCOMM 1998[C].Vancouver, British Columbia, Canada,1998, 203-214.

[10]MALDVOGEL M, VARGHESE G, TURNER J,et al.Scalable high speed IP routing lookups[A].Proc of ACM SIGCOMM, Cannes,France, 1997.25-36.

[11]PANKAJ G, BALKMAN J.PALAC: Packet Lookup and Classification Simulator[Z].User's Manual, ver.4, Rev.2000.