计算机工程
計算機工程
계산궤공정
Computer Engineering
2015年
9期
63-67
,共5页
范富明%李念军%雷升平%吉萌
範富明%李唸軍%雷升平%吉萌
범부명%리념군%뢰승평%길맹
路由器%路由查找%哈希表%多比特树%最长前缀匹配
路由器%路由查找%哈希錶%多比特樹%最長前綴匹配
로유기%로유사조%합희표%다비특수%최장전철필배
router%route lookup%Hash table%multi-bit tree%longest prefix matching
网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求.为此,将哈希表和多比特树相结合,提出一种新的路由查找算法.根据路由前缀的长度将路由表项分层存储在固定的三层Tree中,采用哈希表存储路由下一跳的信息,根据目的IP地址在三层Tree结构中按最长前缀匹配的原则进行快速路由表项定位,并通过表项的信息在对应的哈希表中读取下一跳信息,进行数据转发.在多核平台上的测试结果表明,该算法在百万条路由环境下可达到双向10 GB/s的速度,平均查找次数介于1～2次之间,平均延时小于30 μs.
網絡帶寬的急劇增加對處于網絡節點的路由器設備數據轉髮速度提齣瞭更高的要求.為此,將哈希錶和多比特樹相結閤,提齣一種新的路由查找算法.根據路由前綴的長度將路由錶項分層存儲在固定的三層Tree中,採用哈希錶存儲路由下一跳的信息,根據目的IP地阯在三層Tree結構中按最長前綴匹配的原則進行快速路由錶項定位,併通過錶項的信息在對應的哈希錶中讀取下一跳信息,進行數據轉髮.在多覈平檯上的測試結果錶明,該算法在百萬條路由環境下可達到雙嚮10 GB/s的速度,平均查找次數介于1～2次之間,平均延時小于30 μs.
망락대관적급극증가대처우망락절점적로유기설비수거전발속도제출료경고적요구.위차,장합희표화다비특수상결합,제출일충신적로유사조산법.근거로유전철적장도장로유표항분층존저재고정적삼층Tree중,채용합희표존저로유하일도적신식,근거목적IP지지재삼층Tree결구중안최장전철필배적원칙진행쾌속로유표항정위,병통과표항적신식재대응적합희표중독취하일도신식,진행수거전발.재다핵평태상적측시결과표명,해산법재백만조로유배경하가체도쌍향10 GB/s적속도,평균사조차수개우1～2차지간,평균연시소우30 μs.
