報文分類的規(guī)則沖突檢測與匹配算法研究.pdf

1、報文分類是許多網(wǎng)絡(luò)關(guān)鍵技術(shù)的基礎(chǔ)，它涉及到網(wǎng)絡(luò)的控制、性能、安全和管理等多個方面，報文分類的正確與否、速度的快慢、功能的強弱對這些都有直接影響。 本文重點探討了報文分類中兩個重要問題，一個問題是分類規(guī)則庫的沖突檢測問題，另外一個問題為報文匹配問題。本文第一部分給出了規(guī)則沖突檢測的形式化定義，總結(jié)了近些年來報文分類問題中規(guī)則沖突檢測算法，然后給出Ehab Al-Shaer等人提出的規(guī)則關(guān)系模型，在分析集中式和分布式環(huán)境下包過濾規(guī)則

2、沖突異常模型和檢測算法基礎(chǔ)上提出報文分類規(guī)則在這兩種環(huán)境下的對應(yīng)的模型和算法，在理論上和實驗上做了一定的探索。本文第二部分通過對現(xiàn)有報文分類算法的分析和性能比較，結(jié)合分類規(guī)則所具有的特性，提出了設(shè)計報文分類算法所應(yīng)遵循的原則和思路，并在原有HSM算法基礎(chǔ)上改進了多維報文分類算法。這個改進的算法可以根據(jù)實際需要構(gòu)建各維搜索樹(二分查找樹或裁剪Tile樹)結(jié)構(gòu)；在構(gòu)建中間查詢表和最終查詢表時，可以選擇壓縮參數(shù)，利用表本身的一些啟發(fā)式信息對這

3、些表進行壓縮，減少算法占用的空間。實驗表明該算法分類速度快、存儲空間需求量小，并且具有原先算法固有的可擴展性，參數(shù)的選擇可以使得算法能適應(yīng)多種環(huán)境，能用于IPv6。另外，該算法數(shù)據(jù)結(jié)構(gòu)固定，適合于軟硬件實現(xiàn)，同時支持并行和流水線處理。這些特點非常符合現(xiàn)代網(wǎng)絡(luò)處理器的發(fā)展方向，使得算法具有比較強的生命力。 論文還探討了在IPv6環(huán)境下的報文分類問題，提出相關(guān)的報文分類匹配算法在IPv6下的擴展，討論了本領(lǐng)域中還有待解決的一些問題。