一种基于偏移寻址的存储高效IP地址查找算法

网络带宽的迅猛增长、虚拟路由器和软件路由器等新兴技术的涌现，迫切需要存储高效IP 地址查找算法。已有的实际IP 地址查找算法是基于多叉特里树的空间高效编码，例如树位图特里树(Tree Bitmap Trie)。但在这些编码方法中，每个节点维护多个指针以及多个关联的位图，导致特里树的存储空间开销大，难以将信息存储在高速片上存储器中，从而限制了IP 查找性能。本文提出了一种新颖的偏移编码特里树(Offset Encoded Trie, OET)，实现存储高效IP 地址查找。偏移编码特里树的每个节点仅维护1 个下一跳步位图和1个偏移值，而不需要孩子指针和下一跳步指针。每个节点利用下一跳步位图和偏移值计算出下一搜索节点的存储地址。在IP 地址查找过程中，片上偏移编码特里树查找出最长匹配前缀，而片外前缀哈希表查找出与该前缀想关联的下一跳步信息。本文采用实际IP 前缀规则集进行了实验评估，实验结果表明：与已有多叉特里树编码方法相比，偏移编码特里树显著减少了存储空间开销。