电子学报
電子學報
전자학보
ACTA ELECTRONICA SINICA
2005年
11期
1992-1999
,共8页
动态IP路由查找%有限前缀扩展%哈希%最大熵判定法
動態IP路由查找%有限前綴擴展%哈希%最大熵判定法
동태IP로유사조%유한전철확전%합희%최대적판정법
该算法根据IP路由表的分布特征将前缀有限扩展为三种长度,并用算法所提出的最大熵判定法选取多个Hash函数,将扩展后的前缀映射到三个Hash表的不同级别.在查找过程中算法根据三个Hash表的命中率动态计算查找代价,并据此调整对三个Hash表的搜索顺序.算法支持增量更新,适于软件实现和硬件流水实现.实验表明,对128K前缀的真实转发表算法仅约需3.7M字节,平均每次查找仅需约1.1次访存,而且路由更新时间较小.
該算法根據IP路由錶的分佈特徵將前綴有限擴展為三種長度,併用算法所提齣的最大熵判定法選取多箇Hash函數,將擴展後的前綴映射到三箇Hash錶的不同級彆.在查找過程中算法根據三箇Hash錶的命中率動態計算查找代價,併據此調整對三箇Hash錶的搜索順序.算法支持增量更新,適于軟件實現和硬件流水實現.實驗錶明,對128K前綴的真實轉髮錶算法僅約需3.7M字節,平均每次查找僅需約1.1次訪存,而且路由更新時間較小.
해산법근거IP로유표적분포특정장전철유한확전위삼충장도,병용산법소제출적최대적판정법선취다개Hash함수,장확전후적전철영사도삼개Hash표적불동급별.재사조과정중산법근거삼개Hash표적명중솔동태계산사조대개,병거차조정대삼개Hash표적수색순서.산법지지증량경신,괄우연건실현화경건류수실현.실험표명,대128K전철적진실전발표산법부약수3.7M자절,평균매차사조부수약1.1차방존,이차로유경신시간교소.
