IP地址查找和數(shù)據(jù)包分類算法研究.pdf

1、隨著Internet的飛速發(fā)展，網(wǎng)絡(luò)流量不斷增長(zhǎng)，現(xiàn)有的鏈路速度已經(jīng)能夠滿足網(wǎng)絡(luò)流量的要求，但是路由器的包轉(zhuǎn)發(fā)速度卻遠(yuǎn)遠(yuǎn)沒有跟上它們的步伐。同時(shí)，路由器的空間效率也成為了影響路由器性能的一個(gè)重要瓶頸。IP地址查找和數(shù)據(jù)包分類是兩個(gè)非常重要的路由功能。如何設(shè)計(jì)查找速度快、內(nèi)存開銷小的IP地址查找和數(shù)據(jù)包分類算法是目前研究中的熱點(diǎn)問題。
　　 本文提出了三種高性能IP地址查找和數(shù)據(jù)包分類算法。1）提出了優(yōu)化的特里樹合并算法。采用動(dòng)態(tài)

2、規(guī)劃方法計(jì)算初始合并節(jié)點(diǎn)和最優(yōu)子節(jié)點(diǎn)排列，根據(jù)兩項(xiàng)計(jì)算結(jié)果構(gòu)造最優(yōu)特里樹。與已有的特里樹合并算法相比，優(yōu)化的特里樹合并算法有效地節(jié)省了內(nèi)存開銷。2）提出了優(yōu)化的流水線索引哈希樹算法(OPIHT)。用路由表的所有前綴構(gòu)造一顆特里樹并對(duì)其作預(yù)處理，再用動(dòng)態(tài)規(guī)劃方法確定最優(yōu)前綴劃分方案。與現(xiàn)有的PIHT算法相比，OPIHT算法有效地節(jié)省了內(nèi)存開銷。3）提出了快速多路特征樹(FMMSPT)。將特征前綴作為關(guān)鍵字構(gòu)造B+樹，用一個(gè)無符號(hào)整數(shù)在葉節(jié)