高性能多維包分類算法的研究.pdf

1、隨著網絡技術的飛速發(fā)展以及網絡應用的層出不窮，互聯(lián)網用戶對網絡服務的可靠性、安全性、多樣性都提出了更深層次的要求。路由器需要提供有差別的網絡服務才能滿足不同用戶的需求，如包過濾防火墻、流量計費、流量控制、區(qū)分服務、QoS等。為了支撐這些新型的網絡服務，傳統(tǒng)的單獨依據目標地址進行匹配的單維包分類算法已經不能滿足多樣化的網絡新需求，路由器需要根據數據包頭的多個域對數據進行分類處理，例如數據報文的5元組(源IP地址、目的IP地址、源端口、目的

2、端口、協(xié)議)。研究表明，Internet持續(xù)迅猛的發(fā)展對多維包分類算法提出越來越高的性能要求，不僅要求匹配速度快、空間占用少，且對算法動態(tài)更新及擴展性能也有高的要求。研究高性能的多維包分類算法是大規(guī)模高速網絡發(fā)展的必然要求。本文提出兩種高性能的多維包分類算法，一種屬于軟件范疇，一種屬于硬件范疇，如下所述：
　　 軟件算法方面，提出一種基于元組空間的高性能二維包分類算法TB(JointTuple Space and Bitmap)

3、，該算法從維度分解思想出發(fā)，聯(lián)合元組空間和位圖設計并實現(xiàn)。TB算法首先分別對源IP和目的IP進行單維匹配后，運用交叉組合思想形成訪問元組空間的路線，并通過位圖過濾技術進一步減少訪問元組空間的個數。相比傳統(tǒng)的元組空間算法，TB算法結構清晰簡潔易于實現(xiàn)，時間和空間性能較為優(yōu)越，規(guī)則庫更新較易，且算法擴展性能較好。實驗證明，TB算法平均訪問內存次數低于元組空間代表算法RSFR約26.6％，空間性能平均低于RSFR算法35.1％。
　　

4、 硬件算法方面，提出一種基于計數布魯姆過濾器的快速多維包分類算法CBHT(Counting Bloom filter and Hash Table)，該算法從數據包匹配規(guī)則的聚集特性出發(fā)，結合計數布魯姆過濾器和哈希表設計并實現(xiàn)?；诰奂匦?，對于五維包分類問題，CBHT算法首先利用計數布魯姆過濾器的過濾功能結合單域匹配獲得與前兩維匹配的小規(guī)模規(guī)則集，而后在此有限規(guī)則集中對后三維進行匹配。CBHT運用數據包匹配的聚集特性對傳統(tǒng)的硬件算法結