基于trie的路由查找算法研究.pdf

1、由于Internet的飛速發(fā)展，網(wǎng)絡用戶數(shù)目的增長，多媒體網(wǎng)絡應用日益廣泛，網(wǎng)絡流量呈爆炸式的增長趨勢。Internet若要想繼續(xù)提供較好的服務，要求核心路由器每秒能轉發(fā)幾百萬個以上的分組，快速路由查找技術成為路由器報文轉發(fā)的瓶頸。因此如何實現(xiàn)高速路由表的查找和更新是研究的難點。同時隨著IPv6技術的逐步成熟和推廣，也進一步要求提升路由查找的性能。 文章在通過對近年來提出的各種路由查找方法進行詳細闡述基礎上，對各種算法的性能以及

2、對IPv6的適應性進行了分析，結果發(fā)現(xiàn)trie數(shù)據(jù)結構是實現(xiàn)高速路由查找和報文轉發(fā)的關鍵，且trie算法具有易于與硬件結合的特點，因此提出基于trie的最長前綴的查找算法。 該算法中某些節(jié)點包含多條路由信息，減少了trie樹的節(jié)點數(shù)目。這樣大大減少了存儲空間?？紤]到當前路由表中前綴分布的特點，改進后的算法降低了樹的高度。同時，該算法能夠應用于IPv6網(wǎng)絡。尤其適于當前快速變化的Internet更新要求?？傊?，該算法不僅保障了路由