基于哈希表与多比特树的路由查找算法 (2015年)

网络带宽的急剧增加对处于例络节点的路由器设备数据转发速度提出了更高的要求。为此，将哈希表和多比特树相结合，提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层Tree中，采用哈希表存储路由下一跳的信息，根据目的IP地址在二层Tree结构中按最长前缀匹配的原则进行快速路由表项定位，并通过表项的信息在对应的哈希表中读取下一跳信息，进行数据转发。在多核平台上的测试结果表明．该算法在百万条路由环境下可达到双向10 GB/s的速度，平均查找次数介于1～2次之间，平均延时小于30 μs。