计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
3期
615-618,627
,共5页
黄胜%张卫%吴川川%陈胜蓝
黃勝%張衛%吳川川%陳勝藍
황성%장위%오천천%진성람
IP路由查找%多分支tire树%最长前缀匹配%多分支优先级树
IP路由查找%多分支tire樹%最長前綴匹配%多分支優先級樹
IP로유사조%다분지tire수%최장전철필배%다분지우선급수
IP address lookup%multi-bit trie tree%longest matching prefix%Multi-Bit Priority Tries (MBPT) tree
针对现有路由表查找方法效率低的问题,提出了一种基于多分支优先级树的数据查找算法.该算法将优先级较高的前缀依次存储在原多分支树的虚节点上,将需要进行扩展的前缀存储在辅助存储结构中,从而在路由查找时,该方法可在内部节点找到最长前缀匹配而无需查找到叶子节点,同时避免了在路由表更新时对路由表的重建.仿真结果表明,提出的查找算法能够有效减少在对路由表查找、插入和删除操作所需的内存访问次数,并大幅度地提高路由查找及其更新速率.
針對現有路由錶查找方法效率低的問題,提齣瞭一種基于多分支優先級樹的數據查找算法.該算法將優先級較高的前綴依次存儲在原多分支樹的虛節點上,將需要進行擴展的前綴存儲在輔助存儲結構中,從而在路由查找時,該方法可在內部節點找到最長前綴匹配而無需查找到葉子節點,同時避免瞭在路由錶更新時對路由錶的重建.倣真結果錶明,提齣的查找算法能夠有效減少在對路由錶查找、插入和刪除操作所需的內存訪問次數,併大幅度地提高路由查找及其更新速率.
침대현유로유표사조방법효솔저적문제,제출료일충기우다분지우선급수적수거사조산법.해산법장우선급교고적전철의차존저재원다분지수적허절점상,장수요진행확전적전철존저재보조존저결구중,종이재로유사조시,해방법가재내부절점조도최장전철필배이무수사조도협자절점,동시피면료재로유표경신시대로유표적중건.방진결과표명,제출적사조산법능구유효감소재대로유표사조、삽입화산제조작소수적내존방문차수,병대폭도지제고로유사조급기경신속솔.
