一种基于偏移编码特里树的高效IP寻址算法

提出一种新的偏移编码特里树(OET)的IP寻址算法,即采用OET表示一组IP前缀规则,以减少其存储空间需求。OET的每个节点仅维护1个下一跳步位图和1个偏移值,不需要孩子指针和下一跳步指针,从而提高了IP寻址性能。采用实际IP前缀规则集进行实验评估,与树位图特里树相比,对于实际IPv4和IPv6前缀规则集,OET在存储空间开销上分别减少60%~76%和55%~63%,是一种存储高效的数据结构,整个OET可存储在片上存储器中,能实现高速的IP地址查找,满足虚拟路由器和软件路由器的可扩展性要求。