计算机与数字工程
計算機與數字工程
계산궤여수자공정
COMPUTER & DIGITAL ENGINEERING
2009年
10期
8-11
,共4页
路由查找%长前缀匹配%Hash表%Trie树%掩码
路由查找%長前綴匹配%Hash錶%Trie樹%掩碼
로유사조%장전철필배%Hash표%Trie수%엄마
根据IPV6地址结构和骨干路由表特点,分析了原有路由查找算法,基于IPV6的掩码长度和分段地址,采用Hash表和多分支Trie树结构,提出了一种快速的IPV6路由查找算法.根据分段地址和掩码将最常用到的路由前缀按前缀长度设置Hash表,并将前缀值有序存放在表结点中.不仅可以进行前缀长度的二分查找,同时又是其它前缀匹配的索引.对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配.实践证明该算法具有较好的时空效率,可以较好地提高路由查找速度.
根據IPV6地阯結構和骨榦路由錶特點,分析瞭原有路由查找算法,基于IPV6的掩碼長度和分段地阯,採用Hash錶和多分支Trie樹結構,提齣瞭一種快速的IPV6路由查找算法.根據分段地阯和掩碼將最常用到的路由前綴按前綴長度設置Hash錶,併將前綴值有序存放在錶結點中.不僅可以進行前綴長度的二分查找,同時又是其它前綴匹配的索引.對于其他的前綴匹配問題,根據Hash錶中的索引到相應的多分支Trie樹完成最長前綴匹配.實踐證明該算法具有較好的時空效率,可以較好地提高路由查找速度.
근거IPV6지지결구화골간로유표특점,분석료원유로유사조산법,기우IPV6적엄마장도화분단지지,채용Hash표화다분지Trie수결구,제출료일충쾌속적IPV6로유사조산법.근거분단지지화엄마장최상용도적로유전철안전철장도설치Hash표,병장전철치유서존방재표결점중.불부가이진행전철장도적이분사조,동시우시기타전철필배적색인.대우기타적전철필배문제,근거Hash표중적색인도상응적다분지Trie수완성최장전철필배.실천증명해산법구유교호적시공효솔,가이교호지제고로유사조속도.