余 虎，黃 宇

（合肥工業(yè)大學計算機與信息學院，合肥230009）

1 概述

流分類技術［1］根據(jù)事先設定好的一組策略和規(guī)則，將數(shù)據(jù)包區(qū)分為特定種類的數(shù)據(jù)流，事先設定的策略和規(guī)則集合組成規(guī)則表。隨著網(wǎng)絡流量迅速增長，流分類技術成為路由器、防火墻等網(wǎng)絡設備的關鍵技術之一。還應用于IP網(wǎng)絡QoS模型［2］中，對不同等級的業(yè)務流進行分類和調(diào)度，以提供不同級別的服務質(zhì)量［3］。

遞歸流分類（Recursive Flow Classification，RFC）算法［4］是一種多維流分類算法，具有分類速度快、支持前綴匹配等優(yōu)點。然而，隨著規(guī)則表規(guī)模的增加，對內(nèi)存空間的需求也迅速增加［5］。針對這一缺點，許多學者提出了不同的改進算法，文獻［3］提出利用比特位圖（BitMap）位來表示獨立元素分布的改進算法，改善空間使用效率，但并沒有解決獨立元素的重復存儲問題；文獻［6］提出改變縮減樹的存儲結(jié)構(gòu)的改進算法，消除交叉乘積表中重復存儲元素，一定程度壓縮內(nèi)存空間，但存在算法設計復雜、預處理時間過長等問題；文獻［7］提出利用或運算壓縮塊比特位圖（Chunk BitMap）向量表的Merge＿RFC算法，進一步避免了交叉乘積表中由于規(guī)則分布稀疏所造成的空間浪費問題。

本文對RFC算法進行改進，通過異或運算壓縮規(guī)則表中塊存儲位數(shù)，降低等價類表和交叉乘積表的內(nèi)存消耗。

2 RFC算法

RFC算法包含預處理階段和查找階段。預處理階段由一系列遞歸歸并組成，查找階段是對到達的數(shù)據(jù)包進行提取關鍵字和查找索引表操作。

2．1 預處理階段

預處理階段主要分為以下4個部分：

（1）將規(guī)則表劃分成7個塊 （Chunk0－Chunk6），其中IP地址域劃分成高16位和低16位。Src Addr表示源IP地址，Chunk#0表示高16位源IP地址塊號，Chunk#1表示低16位源IP地址塊號；Dst Addr表示目的IP地址，Chunk#2表示高16位目的IP地址塊號，Chunk#3表示低16位目的IP地址塊號；Pro表示協(xié)議號，塊號為Chunk#4；SPort表示源端口號，塊號為Chunk#5，DPort表示目的端口號，塊號為Chunk#6。

（2）根據(jù)規(guī)則表分別生成7個塊對應的等價類表，等價類表以塊比特位圖（CBM）值為內(nèi)容，等價類標識eqID（Equivlance Class ID）值為索引。再計算每個塊在不同情況下對應的eqID值，建立以eqID值為內(nèi)容的預處理表。

（3）根據(jù)第（2）步中的等價類表，對表項按位交叉相與，計算該步的等價類表；再根據(jù)等價類表得到交叉乘積表。交叉乘積表的內(nèi)容是等價類表中eqID值。

（4）采用類似第（3）步的操作，得到交叉乘積表和等價類表，預處理完成。

2．2 查找階段

對到達的數(shù)據(jù)包，提取關鍵字段值并根據(jù)預處理階段分塊格式進行分塊；再對每塊在相應的向量表中找對應索引值（Index），按照預處理階段的歸并路徑，查找索引表，直到找到數(shù)據(jù)包的最佳匹配規(guī)則，獲得分類標識（ClassID），完成查找過程。

3 Optimize＿RFC算法

3．1 Optimize＿RFC算法的提出

RFC算法預處理時，等價類表和交叉成績表占用大量的內(nèi)存空間，等價類表的長度由規(guī)則數(shù)目所決定［8］。當規(guī)則表過大時，會導致等價類表長度急劇增加。此外，等價類表交叉相與生成交叉乘積表，因此，當?shù)葍r類表長度增加時又會造成交叉乘積表聚合增大。

文獻［9］對RFC算法的IP地址域進行4位異或操作，先將源IP地址和目的IP地址分割為高低16位，再分別將分割后高低16位壓縮到4位，在一定程度上減少了預處理階段的內(nèi)存消耗；但文獻［9］對IP地址域進行分割操作后，又對塊的位長進行壓縮，造成塊冗余。

本文基于RFC算法提出改進算法Optimize＿RFC，利用異或運算對塊的位數(shù)進行壓縮，且不對IP地址域劃分高低16位。將源／目的IP地址分別由32位壓縮到8位，端口號由16位壓縮到8位，協(xié)議字段不進行壓縮操作，生成5個塊，相對于RFC算法，減少了2個塊，并且壓縮了等價類表，從而降低預處理階段的內(nèi)存消耗。

3．2 Optimize＿RFC算法描述

分類規(guī)則表如表1所示。規(guī)則分5個域，分別是源IP地址 （Op＿SIP）、目的IP地址 （Op＿DIP）、協(xié)議號 （Op＿Pro）和源端口號 （Op＿SPort），目的端口號（Op＿DPort），ClassID表示規(guī)則號，Opt表示操作。

表1 分類規(guī)則

Optimize＿RFC算法分為預處理階段和查找階段。

3．2．1 預處理階段

預處理階段主要分為以下2個部分：

（1）規(guī)則表壓縮。

對表1中32位源／目的IP地址字段分別按4位進行異或，壓縮成2個8位的塊（chunk#00，chunk#01）；對16位源／目的端口號字段分別按2位進行異或操作，壓縮成2個8位的（chunk#03，chunk#04）；協(xié)議字段單獨構(gòu)成一個塊chunk#02。

IP地址字段異或壓縮過程如圖1所示。

圖1 IP地址字段異或壓縮過程

（2）生成預處理表、等價類表和交叉乘積表。

針對查找階段的4步：phase0～phase3，為查找階段提供預處理表，等價類表以及交叉乘積表。

1）根據(jù)表1壓縮后的5個塊分別生成對應等價類表，在 phase0中用 Op＿eqID00－Op＿eqID04表示，Op＿eqID表描述每個eqID對應CBM位串。等價類表以CBM值為內(nèi)容，eqID為索引；再根據(jù)等價類表生成對應預處理表，以eqID值為內(nèi)容。Optimize＿RFC算法的eqID和CBM值計算同RFC算法。

2）對phase0生成的等價類表進行逐項相與操作，將 Op＿eqID00和 Op＿eqID02表項內(nèi)容相與，Op＿eqID01，Op＿eqID03和 Op＿eqID04相與，分別得到phase1的交叉乘積表chunk#10，chunk#11，并計算相應的等價類表。

3）根據(jù)phase1的等價類表，利用同樣的方法，計算得到phase2的交叉乘積表及對應的等價類表。

3．2．2 查找階段

查找階段分為以下2步：

（1）數(shù)據(jù)包關鍵字壓縮。

當數(shù)據(jù)包到達時，提取頭部關鍵字段值，并進行壓縮，壓縮方法同3．2．1中的第（1）步。

兒童貧血是臨床常見疾病,據(jù)報道中國5歲以下兒童貧血率為12.6%,引起貧血的主要因素是:膳食結(jié)構(gòu)、生活習慣、遺傳因素,主要類型為:地中海貧血與缺鐵性貧血。臨床癥狀主要為食欲不振、肝脾腫大、皮膚黏膜蒼白等。[1]并且貧血可影響到患兒的生長發(fā)育、免疫發(fā)育、智力與心理的發(fā)展。文山地區(qū)屬于地中海高發(fā)地區(qū),但是地中海貧血與缺鐵性貧血的治療方法也不盡相同,兩者常規(guī)檢查結(jié)果相似性較高,診斷鑒別具有一定難度,在實際過程中,目前以血液檢驗為主要手段。因此,本文旨在探討血液檢驗應用于小兒貧血中的鑒別意義。

（2）查找階段共分為4步，如圖2所示。

假設到達數(shù)據(jù)包關鍵字值是158．166．1．42（Op＿SIP），192．168．1．0（Op＿DIP），udp（Op＿Pro），23（Op＿SPort），80（Op＿DPort）。

1）通過異或運算分別計算每個塊的索引（Index）。得到源IP地址索引值為3，目的IP地址索引值為20，協(xié)議號索引值為17，源端口號索引值為23，目的端口號索引值為80。

2）根據(jù)phase0的等價類表和Index公式［10］計算phase1的索引 值。Index＝Ci，j＊N＋Ci，j＋1＋…＋C00（Ci，j為chunk#ij的索引值，N為chunk#（i，j＋1）等價類表大?。?。通過計算得到chunk#10、chunk#11索引值分別為9和7。

3）再根據(jù)phase1的索引值以及Index公式計算得到phase2中交叉乘積表索引值為5。

4）根據(jù)phase2的等價類表以及索引值得到最終查找結(jié)果，對應CBM值為010001。再對最終查找結(jié)果進行順序查找，獲得最終匹配的規(guī)則2。

圖2 Optimize＿RFC算法查找過程

3．3 算法分析

算法分析過程如下：

（1）空間復雜度。

Optimize＿RFC算法與RFC算法相比，在存儲開銷上會大大降低。在預處理階段，RFC算法中每塊數(shù)據(jù)有S位，Optimize＿RFC算法將數(shù)據(jù)塊由S位壓縮到8位（2S≥28），N條規(guī)則中每塊的等價類表也相應的壓縮，并且phase0的預處理表和等價類表由原先的7個降低到5個。由于是利用順序查找的方法解決最后匹配規(guī)則可能存在的沖突，因此需要額外的存儲空間保存最后階段的CBM表。

Optimize＿RFC算法與文獻［9］算法相比，在預處理階段預處理表和等價類表個數(shù)各減少2個。

（2）時間復雜度。

與RFC算法相比，由于Optimize＿RFC算法在預處理階段進行大量異或處理操作，因此Optimize＿RFC算法的預處理時長會相對增加。Optimize＿RFC算法在各個階段的查找速度與RFC算法基本相當，只多出最后階段的沖突處理時間。沖突處理時間由沖突量決定，沖突量取決于規(guī)則表規(guī)模，因此查找階段時間復雜度增加O（N）。

與文獻［9］算法相比，Optimize＿RFC算法在預處理階段與文獻［9］執(zhí)行相同次數(shù)的異或操作，查找階段也有相同的沖突處理，因此，兩者時間復雜度相近。

4 實驗結(jié)果與分析

本文對Optimize＿RFC算法以及RFC算法、文獻［9］算法進行仿真實驗，運行環(huán)境為Thinkpad E420（Intel coreI5 2．4GHz CPU，2GB 內(nèi) 存 ）PC 機、Windows XP3系統(tǒng)。規(guī)則表和對應的分類數(shù)據(jù)包由ClassBench［11］產(chǎn)生，規(guī)則表規(guī)模為100條～5 000條。統(tǒng)計出各算法的內(nèi)存消耗和分類速度。

由圖3和圖4的實驗結(jié)果表明，RFC算法在預處理階段需要大量的存儲空間，當規(guī)則表規(guī)模超過一定大小時，RFC算法可能存在內(nèi)存溢出。Optimize＿RFC算法在分類速度上略慢于RFC算法，但是內(nèi)存消耗方面，隨著規(guī)則表規(guī)模的增加，Optimize＿RFC算法的空間性能要優(yōu)于RFC算法。并且相對于文獻［9］算法，Optimize＿RFC算法的空間性能也要更好。

5 結(jié)束語

針對RFC算法運行時存在存儲空間的不足，本文提出一種基于內(nèi)存優(yōu)化的改進算法Optimize＿RFC算法，該算法可以有效減少RFC算法的內(nèi)存開銷，同時保持相對較快的流分類速度。實驗結(jié)果表明，當規(guī)則表超過一定規(guī)模時，RFC算法的內(nèi)存消耗會急劇增加，而Optimize＿RFC算法通過對等價類表進行異或處理，可以有效改善因規(guī)則表規(guī)模過大造成內(nèi)存消耗過大的問題。Optimize＿RFC算法可以提高遞歸流分類算法效率，但是并沒有解決規(guī)則集的動態(tài)更新［12］問題，可作為流分類算法的進一步研究方向。

［1］Gupta P，Mckeown N．Packet Classification on Multiple Field［C］／／Proceedings of ACM SIGCOMM’99．New York，USA：ACM Press，1999：147－160．

［2］Babulak E．User’s Perception of Quality of Service Provision［C］／／Proceedings of IEEE International Con－ference on Industrial Technology．Washington D．C．，USA：IEEE Press，2003：1022－1025．

［3］Spitznagel E． Compressed Data Structures for Recursive Flow Classification［C］／／Proceedings ofIEEE WUCSE’03．Washington D．C．，USA：IEEE Press，2003：984－992．

［4］Gupta P， Mckeown N． Algorithms for Packet Classifica－tion［J］．IEEE Network，2001，15（2）：24－32．

［5］Berndt D，F(xiàn)isher J，Joshson L，et al．Breeding Software Test Cases with Genetic Algorithms［C］／／Proceedings of the 36th Hawaii International Conference on System Sciences．Big Island，USA：［s．n．］，2003：338－349．

［6］劉 鐸，華 蓓，唐錫南，等．Compact RFC：一種內(nèi)存優(yōu)化的RFC包分類算法［J］．小型微型計算機系統(tǒng)，2007，28（3）：482－487．

［7］曹 婕，陳 兵．一種內(nèi)存優(yōu)化的RFC包分類算法Merge＿RFC［J］．小型微型計算機系統(tǒng)，2012，33（4）：865－868．

［8］亓亞烜，李 軍．高性能網(wǎng)包分類理論與算法綜述［J］．計算機學報，2013，36（2）：378－382．

［9］劉 胤，楊世平．基于RFC算法的快速多維數(shù)據(jù)包分類算法［J］．計算機工程，2008，34（6）：95－97．

［10］陳 勝，張大方，畢夏安．一種基于流的局部特性和多級查找的高效包分類算法［J］．小型微型計算機系，2013，34（11）：2499－2503．

［11］Taylor D E．Class Bench：A Packet Classification Benchmark［J］．IEEE／ACM Transactions on Networking，2007，15（3）：499－511．

［12］Trivedi U．An Optimized RFC Algorithm with Incremental Update［C］／／Proceedings of International Conference on Advances in Computing Communications and Informatics．Washington D．C．，USA：IEEE Press，2014：120－127．