一种前缀长度二分查找的改进算法

第33 卷 Vo1． 33 第15期 N o ． 15 计C om puter E 算机工程 2007 年 8 月 A u gu st 20 07 ·软件技术与数据库 · ~ l mq " l00o． _3428(2 007 )l -0070_ _ _o2 文 献 标 识 码： A 中 圈 分 类 号： TP301 ． 6 一种前缀长度二分查找的改进算法 崔尚森 ，冯博琴 2 张自一 ( 1． 长安大学信息工程学院，西安 ；2． 西安交通大学电子与信息工程学院， 西安 ) 摘干种前缀合并成一种， 降低了查找树的高度， 减少了存储器访问次数， 提高了查找速度， 分析了一种实用的 存储算法， 探讨了IPv6 的路由查找问题。 关健诃：IP路 由；前缀长度；最长前缀匹配；二分查找 要：在研究路由表地址前缀分布特点的基础上，提出了前缀长度二分查找方案。该方案采用前缀扩展技术，将前缀数量相对稀少的若 Im p rov ed A lgor ithm fo r P r ef i x L ength B inar y Sea rc h C U I S ha ng ． sen ， 一 ， F E N G B o． qin ， Z H A N G B ai． y i (1． C of on and E ng， C hang’an U ， X i ’an 7 10064 ； 2． of E and E ， Xi’ an ， X i’an 7 10049) [ ] on t he of IP in core ， t h is paper an for t h e usi ng sea r c h on hash ed by ． It uses p ref i x exp ansio n tO reduc e the num bers of t h e lengt h ． T ， it t h e of hash and low ered t h e of t h e tree． T he paper provi des a con cise a n d util ity M a r ker store al so，and gi v es some v iew poi nts for IP v 6 routi ng ． [ K ey words ] IP ； ； match ； bina r y sea r ch 随着 的快速发展网络前缀长度， 用于主干网络互联的核心路由 器的接I =1速率已达到 2． 5Gb／ s~10Gb／ s。

这一速率要求核心路 由器每秒能够转发几百万乃至上千万个分组。分组转发的重 要步骤就是查找路由表。在各种查找算法中， Hash 查找具有 最快的搜索速度， 具体性能与 Hash 函数的设计以及冲突处理 技术有关；二分搜索算法的时间复杂度为对数阶，在大量数 据中查找特定值的问题时， 性能良好。 等人提出的 前缀长度二分查找方案 是一种兼有二分查找和 Hash 查找 特征的理想方案，时间复杂度为 O(1 og2 说，查找过程中最多需要 =5 次存储器访问；对于 IPv6 地址最多也需要 =7 次存储器访问。 前缀长度二分查找需要解决的 3 个关键问题是 ： (1)Hash 函数的设计；(2)插入 进行查找路径的正确引导；(3) 通过 (预计算)来解决 的误导和回溯问 题。 在这 3 个关键问题中， 预计算问题相对简单， 在 等人提出二分查找方案时，已给出了明确的解决方案。Hash 函数设计依据表项的数量和值的分布特点， 等人提出 的 d 维 Hash 函数的设计方案 是一种可借鉴的方案。

笔者在研究http： ／ P ogp． ． net 网核心路由器前缀长度 统计数据的基础上，结合地址前缀的分布特点 ，提 出了改进 的前缀长度二分查找算法和 的存储算法，并对 IPv6 路由查找提出了建议。 1 前缀长度二分查找的改进方案 根据对 http： ／ ／ bgp． ． net 网核心路由器前缀长度统计 数据的长期跟踪研究，可以得出如下结论：(1)到目前为止， 还不存在长度小于 8 的前缀；(2)长度在 8～15 的前缀相对较 少；(3)长度大于 24 的前缀非常稀疏；(4)大量前缀的长度介 于 1 6～24。此外 ，自 1998 年以来，路由表中前缀数量增长 。对于 IPv4 地址来 量最大的也是长度介于 16～24 的前缀， 其余长度的前缀增长 量相对很小。针对前缀分布的这些特点，如果采用前缀扩展 技术，将若干种比较稀疏的前缀合并为一种长度网络前缀长度，就可以降 低查找树的高度、减少查找次数。 1． 1数据结构的改进 基于上述考虑，本文提出的方案将前缀长度介于 8～13 的前缀一律扩展为长度为 13 的前缀；将长度介于 27～32 的 前缀一律扩展为长度为 32 的前缀， 这样， 前缀长度的种类数 只有 15 种，可以形成如图 1所示的深度为 4 的查找树。

图 1 优化的 IPv4 前缀长度二分查找树 为方便数据组织、节省存储空间，出于 插入位置 计算等方面的考虑，可以为每种长度的前缀设计一个独立的 Hash表，并为这些 Hash表建立一个索引表。 Hash表的每个表项包含 3个域：(1) 域，存储对应 基金项目：国家 “863” 计划基金资助项 目 “应用服务器中间件及其 支撑环境研发” ( 1 Z 2610) 作者倚介：崔尚森(1957 一)，男，副教授、博士研究生，主研方向： 计算机 网络应用 ，可靠性算法 ；冯博琴 ，教授、博士生导师 ； 张自一，副教授 收稿日期：2006— 10— 22 E-mail：cui～ ss@chd． edu． cn 维普资讯