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

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

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