快速IP包分類算法及實(shí)現(xiàn).pdf

1、對(duì)于IP包分類的問題,本文先介紹了目前常用的分類算法,分析了各個(gè)算法的優(yōu)缺點(diǎn).針對(duì)交叉相乘法速度快,但對(duì)存儲(chǔ)空間的需求大的問題,本文在第三章提出了對(duì)交叉相乘法進(jìn)行改進(jìn)的方法.這個(gè)改進(jìn)方法在提高速度的同時(shí),還成倍地降低了對(duì)存儲(chǔ)空間的要求.對(duì)于交叉相乘法,原來對(duì)于每一維的分類是基于地址的形式上的區(qū)別,將每一維地址分為若干類,然后交叉相乘.由這種分類方法分出的各個(gè)類,無論是在一維還是二維上,它們都是有重疊的,所以沒法用快速查找算法.本文提出基

2、于各維對(duì)空間的無重疊的劃分的基礎(chǔ)上的分類,從而在查找上可以使用更快的算法.為了對(duì)交叉相乘法所產(chǎn)生的巨大的表進(jìn)行壓縮,本文先是利用了等價(jià)類的方法對(duì)表中重復(fù)的行或列進(jìn)行壓縮,然后使用行程編碼或位向量的方法對(duì)表進(jìn)一步壓縮.同時(shí)利用類似貨郎擔(dān)問題的解決辦法來提高壓縮率.本文中在提出方法的同時(shí)也提供了算法.為了驗(yàn)證這個(gè)方法的正確性,我們使用現(xiàn)實(shí)網(wǎng)絡(luò)中自治系統(tǒng)網(wǎng)絡(luò)前綴產(chǎn)生模擬的分類數(shù)據(jù)庫,用非隨機(jī)方式及隨機(jī)方式產(chǎn)生不同大小及具有不同動(dòng)作數(shù)量的數(shù)據(jù)庫