（通信与信息系统专业论文）高性能路由器中高速转发查表算法研究与实现.pdf

中文摘要 随着i n t e m e t 规模的急剧膨胀 路由器的体系结构 转发速度和交换网络的容量己成为 网络发展的瓶颈 本文结合国家8 6 3 项目 可扩展到t 比特的高性能i p v 4 v 6 路由器基础平 台及实验系统 较深入的研究了高速路由器路由查找算法及其实现技术 在对现有路由查 找算法分析比较的基础上 本文重点研究了基于t c a m 的路由查找技术 提出了基于 t c a m 的二级路由查找方案 对基于流分类的哈希查找进行了分析 提出了多哈希随机检 测快速选择更新算法 本文所做的工作如下 l 提出了评价路由查找算法的标准 指出了现有路由查找算法的问题 对现有路由查 找算法及新兴发展方向进行了较为全面的分类分析比较 为t 比特路由器转发引擎的研究 设计提出了新的课题和思路 2 设计了一种由t c a m 和s r a m 分别完成搜索和读结果的查表流水线 该方案引入 一种全新的t c a m 表项配置与管理方法来支持i p v 4 v 6 双协议栈下的路由查找 与传统的 由t c a m 串行完成搜索和读结果两个过程的路由查表方案相比 该方法可将路由查表时间 从十多个周期减少到仅为2 或4 个周期 大大提高了转发引擎性能 实测结果表明 在数 据速率高达1 0 g b p s 时 该方案下的转发引擎能线速转发包长4 0 字节以上的i p 数据包 3 根据t c a m 的特性 提出了一种基于t c a m 的二级路由查找方案 该方案由一种 基于比特选择的h a s h 分类机制实现 大大节省了查表的功耗 消除了基于t c a m 的路由 查找功率消耗大的特点 提高了系统的稳定性 具有重要的实用价值 4 对现有路由表项更新算法进行了分析和比较 在分析了基于流分类的哈希查找算法 的随机性的基础上 提出了一种支持i p v 4 i p v 6 双协议栈的路由表项更新算法 多哈希 随机检测快速选择更新算法 分析了该算法的性能并给出了实验结果 该算法在t 比特路 由器上已得到实现 取得了较好的效果 关键词 路由器 转发引擎 路由查找 最长匹配 t o n i 哈希 第1 页 a b s t r a c t t h er o u t e ra r c h i t e c t u r e f o r w a r d i n gr a t ea n ds w i t c h i n gc a p a c i t yh a sb e c a m et h r e eb o t t l e n e c k s i nt h ed e v e l o p m e mo fn e t w o r ka st h et r e m e n d o u se x p l o s i o no ft h et r a f f i ci ni n t e m e t t h i s d i s s e r t a t i o ni sd e v o t e dt ot h er e s e a r c h e so ft h et h e o r ya n di m p l e m e n t a t i o no fh i c as p e e dr o u t i n g l o o k u pt e c h n o l o g ya c c o r d i n g t ot h er e q u i r e m e n t so f8 6 3t e r a b i tr o u t e rp r o j e c t t h em a i nw o r ko f t l l i sd i s s e r t a t i o ni sa sf o l l o w s 1 t h es t a n d a r do fj u d g i n gr o u t i n gl o o k u pa l g o r i t h m si sp r o p o s e da n dt h ep r o b l e m so f c u r r e n tr o u t i n gl o o k u ps c h e m ea r ep o i n t e do u t t h i sp a p e re m p h a s i z e so nt h ec l a s s i f i c a t i o na n d c o m p a r i s o no f c u r r e n tr o u t i n gl o o k u pa l g o r i t h m sf r o mt h ep o i n to f i m p l e m e n t a t i o nm e t h o d 2 as e g m e n t a lr o u t i n gl o o k u pp i p e l i n eb a s e do nt c a ma n ds r a mi sd e s i g n e d t h el o o k u p p i p e l i n eg r e a t l yi m p r o v e st h ee f f i c i e n c yo ft h ef o r w a r d i n ge n g i n eb yd e c r e a s i n gl o o k u pt i m e f r o m1 0c y c l e st o2o r4c y c l e s t h et e s tp e r f o r m a n c er e p o r to ft h es t r u c t u r ed e m o n s t r a t e st h a t t h i ss c h e m ec a ns u p p o r ta1 0 g b p sp o r tf o r w a r d i n g4 0b y t e sl o n gp a c k e t sa tl i n e s p e e d 3 at w o s t a g er o u t i n gl o o k u ps c h e m eb a s e do nt c a mi sp r o p o s e db ys t u d y i n gt h e c h a r a c t e r i s t i co ft e a m t h i ss c h a m ew h i c hm a k e st c a m b a s e dr o u t i n gt a b l e sm o r ep o w e r e f f i c i e n ti si m p l e m e n t e db yt h eb i ts e l e c t i o ns t r u c t u r e a n a l y s e si n d i c a t e dt h a tt h es c h e m ec a n o v e r c o m et h ed r a w b a c ko f h i 曲p o w e rc o n s u m p t i o no f t c a ma sw e l la si m p r o v et h es t a b i l i t yo f t h es y s t e m a n di sv a l u a b l ef o rp r a c t i c a lu s e 4 b ya n a l y z i n gt h ec u r r e n tu p d a t i n ga l g o r i t h m sa n dt h eh a s h i n g b a s e dl o o k u pa l g o r i t h m s t h i sp a p e rp r e s e n t saq u i c kr o u t i n gu p d a t i n ga l g o r i t h m q u i c ka n ds e l e c t i v em u l t i h a s h u p d a t i n ga g o r i t h mb a s e do nr a n d o ms a m p l e t h ea l g o r i t h mw h i c hs u p p o r t sb o n li p v 4a n d i p v 6p r o t o c o li si m p l e m e n t e di nt h et e r a b i tr o u t e rp r o d u c e db yn d s c e x p e r i m e n tr e s u l t s i n d i c a t et h a tt h ea l g o r i t h mp e r f o r m a n c ew e l l k e yw o r d s r o u t e r f o r w a r d i n ge n g i n e r o u t i n gl o o k u p l o n g e s tp r e f i xm a t c h t c a m h a s h i n g 第1 i 页 信息t 稃大学硕十学付论文 表目录 表1 选路表例 表2 路由查表算法性能综合表 表3 几种主要硬件查表算法的性能比较 表4 不同接口类型条件下转发引擎包转发率需求 表5 转发查表所需器件表 表6i p v 4 地址表项结构 表7i p v 6 地址表项结构 表8s r a m 查表结果表项结构 表9 测试仪吞吐量 表1 0 二级路由查找下路由器吞吐量 表11 二元比特运算真值表 表1 2 三种哈希函数的执行时间 表1 3 三种哈希函数的随机测度值 第v 页 加殂 拍 勰勰凹弱钔 虬 信息丁稃大学硕十学付论文 图目录 图l 骨干网路由表包含路由数量的增长曲线 3 图2 二叉树结构存储的路由表 8 图3l e a v ep u s h e d 树存储示例路由表 9 图4p a t r i c i a 树存储的示例路由表 l o 图5 路径压缩树示例 1 1 图6 多分支树示例 1 2 图7 层压缩树示例 1 4 图8 前缀对应地址区间的示例 1 6 图9 分段式i p 线速率查找逻辑原理图 1 8 图l o 混合查表算法原理框图 1 9 图1 l 转发处理模块结构框图 2 2 图1 2 转发引擎系统级流水线连接图 2 4 图1 3t c a m 查找结构 2 4 图1 4 查表的流水线结构 2 5 图1 5 单播查表外部结构图 2 6 图1 6 查表模块f p g a 内部结构 2 7 图1 7i p v 4 i p v 6 查表流程图 2 8 图1 8 转发性能测试环境 2 9 图1 9 七种情况下转发系统时延曲线图 3 0 图2 0 二次查表原理图 3 l 图2 1 二次查表流程图 3 3 图2 2 三比特选择分类机制 3 4 图2 3 a s l 2 2 1 上前缀分布图 3 4 图2 4 功耗降低倍数与比特数关系图 3 4 图2 5 两种查表机制时延对比 3 6 图2 6 顺序移动法 3 8 图2 7 选择移动法和p l o o p t 算法 3 9 图2 8 哈希查找模型 4 0 图2 9 多哈希随机检测快速选择更新算法 4 5 图3 0t c a m 映射表的初始化 4 6 圈3 1 算法实现的外部软件环境 4 7 图3 2 算法实现流程图 4 9 图3 3 表项更新速度曲线 5 1 第 页 独创性声明 所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果 尽我所 知 除了文中标注和致谢的相关内容外 论文中不包含其他个人或集体已经公开的研究成 果 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意 学位论文题目 直性能路自墨生直速缱筮查塞篡洼班壅皇塞现 学位论文作者签名 趔酗叁日期 山衫年 月 多日 学位论文版权使用授权书 本人完全了解信息工程大学有关保留 使用学位论文的规定 本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档 允许论文被查阅和借 阅 可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或 扫描等复制手段保存 汇编学位论文 涉密学位论文在解密后适用本授权书 学位论文作者签名 i 丑幽垒日期 纱 年厂月 巧日 作者指导教师签名 缢篓墨主日期 功 f 年f 月 日 笪星工登奎兰堡 兰生丝茎 第一章绪论 本章首先介绍了课题的研究背景 接着提出了路由算法的评价标准并指出了当前路由 查找算法存在的问题 最后介绍了本文的主要贡献以及结构安排 1 1 研究背景 核心高速路由器作为i n t e m e t 网络互联的主要设备 它的体系结构 转发速度和交换 网络的容量是i n t e m e t 网络发展的三大主要瓶颈 为了提高路由器的性能 满足未来网络 发展的需要 处于i n t e m e t 骨干位置的核心路由器进行了一个又一个的技术变革 包括以 专用网络处理器替代通用处理器 大容量交换矩阵的应用 以硬件查找路由表代替软件查 表等等 近几年来 随着i n t e m e t 规模的急剧膨胀以及i n t e m e t 上新应用的不断出现 i p 网 络正逐步向高速化 宽带化发展 核心路由器这个中心节点的交换容量也必然会以几十 几百倍的速度增长 为了满足i n t e m e t 日益发展的需要 研制t 比特级的高速核心路由器 势在必行 为此科技部发布 可扩展到t 比特的高性能i p v 4 v 6 路由器基础平台及实验系统 课题 研制t 比特路由器作为中国高性能宽带信息网运营的关键设备 本文主要研究t 比特路由 器转发引擎的路由查找算法及其更新算法 1 2 路由查找算法的研究 1 2 1 路由查找算法的性能评价标准 1 路由查找速度 查找速度是决定路由查找算法性能及路由器转发处理能力的最主要的因素 物理链路 速率的提高要求路由查找速度也相应提高 在给定链路速率下 要求查找速度一般有两种 计算方式 一种是按照i n t e m e t 最短分组长度和最坏情况下的查找速度来计算 在i p v 4 为 基础的i n t e m e t 流量中 仅t c p 回应报文 2 0 字节的i p 头 2 0 字节t c p 头 计4 0 字节 就占4 0 左右 因此对第一种情况的速度要求按分组长度4 0 字节计算 对o c l 9 2 1 0 0 b p s g i g a b i tp e rs e c o n d 链路来说最坏情况下的查找速度需要达到3 1 2 5 m p p s m i l l i o np a c k e t s p e rs e c o n d 对i p v 6 路由查找则常以4 8 字节长度分组计算 即o c l 9 2 1 0 g b p s 链路的 分组速率为2 5 m p p s o c 7 6 8 4 0 g b p s 链路的分组速率为1 0 0 m p p s 另一种是按平均分组长度和平均查找速度来计算 根据现在的统计结果 i n t e m e t 上传 输的i p 分组的平均长度为2 0 0 0 比特左右 假如平均分组长度为2 4 0 字节 对o c 1 9 2 平 均查找速度只要达到5 2 1 m p p s 就可以满足要求 制约路由查找速度的问题之一是存储器的访问速度太慢 远不能满足数据链路速度的 第1 页 信息t 稃大学硕士学何论文 要求 由于路由表越来越大 若采用d r a m d y n a m i cr a n d o m a c c e s sm e m o r y 来存储路 由表 如果链路速率为1 0 g b p s 即使按照平均分组长度计算 查找速率也要达到5 2 1 m p p s 即1 9 0 n s 要完成一次路由查找 也就是说 按照一次d r a m 的访问时间约为5 0 n s 计算 要支持1 0 g b p s 的链路速率最多只能读三次存储器 减少访问存储器的次数是提高查找速 度的一条途径 所以 一次路由查找需要访问存储器的次数是衡量查找算法速度的指标之 一 为了适应高速率链路 并行处理技术成为高速路由查找的一个基础 因此 并行处理 路由查找结构的查找速率和查找流程的连续性 成为衡量查找算法性能的重要指标 2 表项更新速度 路由表一般以转发表的形式供转发处理模块进行路由查找 通常路由表由包含协议处 理功能的主控模块产生和维护 而将与转发密切相关的信息简化为转发表 被分发到各转 发处理模块保存和使用 转发处理模块根据主控模块发来的指令对转发表进行更新 根据 对转发表更新方式的不同 路由查找算法可以分为两种类型 一种称为静态算法 即当发 生路由更新 包括添加和删除 时 转发表数据结构需要完全重新构建 另一种称为动态 更新算法 当发生路由更新时 只需要在原有的基础上相应更新 而不需要完全重构 与 静态更新相比 动态更新的速度更快 研究表明 骨干网路由器的路由表更新频率很高 可以达到1 0 0 次 秒 路由表的频繁更新 要求查找算法应该能够动态插入删除转发表项 同时 为了不影响查找操作 插入与删除的时间应尽可能短 因此 快速表项更新算法成 为研究的一个热点 为了适应高速链路采用并行处理查找结构时 一个表项更新需要的更新次数 或对路 由查找流程的中断次数 一次更新耗费的时间 成为衡量查找算法性能的重要指标 3 对i p v 6 的适用性 i p 地址的长度越长 路由查找的难度就越大 要求路由查找算法随地址长度的扩展性 要好 以适应地址长度为1 2 8 比特的i p v 6 路由查找 4 支持的路由表容量 随着i n t e r a c t 的发展 骨干网路由器的路由表容量也在不断增大 至2 0 0 6 年 骨干网 路由器的路由表所含表项已超过2 4 万 并仍然呈显著上升趋势 见图1 因此 查 找算法对路由表容量的扩展性要好 以容纳足够大的路由表来适应路由增长的需要 5 所需的存储空间 转发表数据结构所占存储空间应尽可能少 这样不仅可以降低成本 还可用快速存储 器如s r a m 实现 从而达到更高的速度 但是随着微电子技术的快速发展 存储器的容量 不断增加且价格不断下降 使得对算法所需的存储容量有所放宽 对核心路由器来说主要 的性能指标是 查找速度 更新速度 i p v 6 适应性以及对大路由表的支持 第2 页 信息t 稃大学硕十学付论文 u 图1 骨干网路由表包含路由数量的增长曲线 1 2 2 传统的路由查找算法存在的问题 路由器的转发引擎主要功能是 接收输入输出线卡单元传来的i p 报文并提取出报头消 息 然后进行路由查找 报头处理以及q o s q u a l i t yo fs e r v i c e 和报文分类处理等 最 后将报文送入交换单元进行交换 其中高性能路由查找技术和流转发 交换技术是转发引擎 的关键技术 由于互联网的迅速发展 传统的路由查找方案主要面l 临以下问题 1 商用存储器的随机访问速率限制了部分传统路由查找算法的应用 随着传输技术的飞速发展 路由器尤其是核心路由器的线路接口速率越来越高 当高 速路由器的端口速率大于o c l 9 2 i o g b s 达到o c 7 6 8 4 0 g b s 甚至o c 3 0 7 2 1 6 0 g b s 时 路由器几乎不可能对分组包进行缓存 要达到1 0 g 的线速转发 对存储器的要求越来 越高 目前s r a m 技术只能达到5m p p s 的性能 t c a m 技术可以达到1 0 0m p p s 的性能 因此高速路由器限制了此类传统路由查找方案的直接使用 2 传统路由查找算法的性能使其在高速路由器中的应用受到限制 路由器端口速率的提高 不仅使商用存储器的访问速度成为高速路由器的瓶颈 同时 还要求路由查找算法易于高速实现 对于t r i e 树 包括二进制t r i e 树和多分支t r i e 树 来 说 由于它使用的树结点灵活度非常高 所以直接将t r i e 树算法用硬件实现并不可取 业界 线速路由器也未见直接采用l r i e 树算法实现路由查表的 前缀长度二分查找和地址区问二 分查找算法使用二分法作为查找的基本思想 必然会导致路由查表时间的不均匀 不适于 硬件实现 第3 页 口c g一 g q 兰 oc 信息t 稃大学硕士学俯论文 3 传统路由查找算法可扩展性差 缺乏对多协议的支持限制了它们的应用 互联网的迅速发展要求其成为一种能够提供多种不同服务 以支持不同应用需求的网 络 随着i n t e m e t 规模的急剧膨胀 信息量的加大以及i n t e m e t 上新应用的不断出现 2 0 多年前提出的i p v 4 网际互连版本在许多方面己不适应 首先是地址限制 其次是日益复杂 的应用业务如流媒体业务和音频业务等对网络性能提出的新的需求 人们对i p 协议的地址 空间 性能以及安全性等方面提出了更高的需求 使i p v 4 的局限性越发显现出来 迫切需 要发展新一代i n t e m e t 而i p v 6 正是为满足这些新的需求而提出来的 目前在许多发达国 家如日本 瑞典 美国等都有基于i p v 6 的商用网 中国教育科研网c e m e t 网络中心于1 9 9 8 年6 月加入6 b o n e 同年1 1 月成为其骨干网成员这一试验网正式使用部分的骨干网由1 0 个节点组成 随着i p v 6 的广泛应用 作为网络核心的路由器必须对其进行很好的支持 然 而大部分传统的路由查找算法对i p v 6 的支持不够好 而且现代正处于i p v 4 向i p v 6 过渡的 时机 路由器必须要能同时支持i p v 4 和i p v 6 双协议栈 因此新的路由查找算法的研究十 分必要 1 3 本文的主要贡献 本文主要贡献如下 对现有路由查找算法及新兴发展方向进行了较为全面的分类分析比较 这样分类不仅 有利于较全面总结各种算法 更有利于揭示路由查找算法的研究方向 为t 比特路由 器转发引擎的研究设计提出了新的课题和思路 设计了一种由t c a m 和s r a m 分别完成搜索和读结果的查表流水线 该方案引入一种 全新的t c a m 表项配置与管理方法来支持i p v 4 v 6 双协议栈下的路由查找 与传统的 由t c a m 串行完成搜索和读结果两个过程的路由查表方案相比 该方法可将路由查表 时间从十多个周期减少到仅为2 或4 个周期 大大提高了转发引擎性能 实测结果表 明 在数据速率高达1 0 g b p s 时 该转发引擎能线速转发包长4 0 字节以上的i p 数据包 根据t c a m 的特性 提出了一种基于t c a m 的二级路由查找方案 该方案由一种基 于比特选择的h a s h 分类机制实现 在路由查表性能略微下降的情况下 大大节省了查 表的功耗 消除了基于t c a m 的路由查找功率消耗大的特点 具有重要的实用价值 对现有路由表项更新算法进行了分析和比较 提出了一种支持i p v 4 i p v 6 双协议栈的路 由表项更新算法 多哈希随机检测快速选择更新算法 分析了该算法的性能并对其 做了仿真测试 最后给出了实验结果 该算法在t 比特路由器上已得到实现 取得了 较好的效果 1 4 本文的结构和安丰 本文剩余部分安排如下 第4 页 信息t 稃大学硕十学何论文 第二章对现有的路由查找算法进行了性能分析 对已有相关路由查找算法研究成果做 了简要介绍 并对各种算法的性能进行分析 是本文研究工作的基础 第三章首先对t 比特路由器的转发引擎作了简要介绍 然后引入流水线设计思想 并 在其基础上提出了路由查找的流水线结构 重点描述由t c a m 和s r a m 分别完成搜索和 读结果的查表流水线的实现 本章最后提出了一种基于t c a m 的二级路由查找机制 给出 了其基本原理并对该方案下最差功率消耗进行了分析 给出了测试结果 第四章首先分析和比较了现有路由表项更新算法 接着分析了基于流分类的哈希算法 的随机性 提出了一种支持i p v 4 i p v 6 双协议栈的路由表项更新算法 多哈希随机检测 快速选择更新算法 q u i c ka n ds e l e c t i v em u l t i h a s hu p d a t i n ga g o r i t h mb a s e do nr a n d o m s a m p l e 给出了该算法的基本原理并对其性能进行了分析 最后给出了该算法在t 比特 路由器中的实现方案和测试结果 最后是结束语 对全文进行了总结 指出了目前在研究中还存在的一些问题和不足 并给出了下一步可能的研究课题和相应的一些设想 第5 页 信息t 稃大学硕士学位论文 第二章路由查找算法研究与分析 本章主要讨论现有的路由查找算法 从路由查找速率 表项更新速度等方面对现有的 路由查找算法进行了分类和比较 对该领域的成果进行了较全面的总结 对当前研究的新 热点进行了重点分析 为t 比特路由器转发引擎的研究设计提出了新的课题和思路 2 1 引言 i n t e r a c t 的地址结构在1 9 9 3 年之前采用的是分类地址结构m 1 因而路由器的路由查 表非常简单 但是却极大地浪费了m 地址空间 早在1 9 9 1 年人们就预测 在1 4 个月内 b 类地址将被分配完毕 而整个坤地址空间将在1 9 9 6 年耗尽 尽管已分配的地址不到1 在真正使用 另外 骨干网上路由器中的路由表项呈指数增长 的趋势使得路由器的处 理器负荷不断加重 为了减缓路由表项的增长速度和有效利用i p 地址空间 1 9 9 3 年 i n t e r a c t 网络采用了 c i d r c l a s s l e s si n t e r d o m a i nr o u t i n g 呻1 地址分配机制 c i d r 废除了分类地址空间中网 络号长度固定为7 1 4 或2 1 的作法 网络地址可取任意长度 可变长度前缀的采用使得 我们可根据i n t e m e t 的物理拓扑结构将i p 地址进行分层 连到骨干网上的某一业务提供者 i s p 可分配一较短的前缀 而i s p 从他的地址空间中分出一部分 构成较长的网络地址 提供给连接到它的较小的i s p 或站点 网络结构可如此分配下去 采用c i d r 技术后 一台路由器中的转发表中表项形式为 其中r o u t e p r e f i x 为i p 地址前缀 即网络号 而n e x t h o p a d d r 就是对应前缀为r o u t e p r e f i x 的i p 包的下一跳地址 如果一个i p 包目的地址的前几比特正好与某一r o u t e p r e f i x 的有效 比特相同 则此目的地址与该表项匹配 对一个i p 包的查表操作就是在所有匹配表项中找 到具有最长r o u t e p r e f i x 的表项 称为最长匹配 该表项对应的n e x t h o p a d d r 即为该i p 包 的下一跳地址 而该表项的r o u t e p r e f i x 称为最长匹配前缀 由于i p 目的地址不携带其网 络号的长度 最长匹配查表必须找到所有匹配表项中p r e f i x 最长的表项 这样给查表带来 了较大的困难 近年来 研究人员提出了多种路由查表算法以提高查找性能 本章全面综 述了各种路由查表算法及其数据结构 并对它们进行了详细的分析和比较 最后给出了区 别应用不同查表算法的总结 2 2 路由查表算法分类 最长地址前缀匹配查找的难点在于在查找过程中 不仅需要与地址前缀的比特值进行 匹配查找 而且还需要考虑地址前缀的长度 因此各种路由查找算法都可以归结为这两个 方面的匹配查找过程 第6 页 信息t 稃大学硕十学何论文 2 2 1 基于地址前缀值的路由查找算法 基于地址前缀值路由查找算法的特点是通过对整个地址前缀空间进行地址关键字穷举 来消除地址前缀长度对查找的影响 2 3 1 中介绍的线性匹配查找算法是基于地址前缀值查 找中最简单直观的地址前缀查找方法 2 4 5 节介绍的地址区域二分法也是基于地址前缀值 的查找算法 但是由于它采用了二分查找 所以在算法性能上有了很大的提高 2 5 节介 绍的t c a m 硬件实现方法从本质上来说也属于地址前缀值的查找算法 2 2 2 基于地址前缀长度的路由查找算法 另一类查找方法是基于地址前缀长度的路由查找算法 这类算法的出发点就是在静缀 长度空间内进行查找 与基于地址前缀值查找算法类似 查找过程可以使用线性遍历法 也可以使用二分法遍历法 2 3 3 节介绍的二迸制t r i e 树查找算法就是基于地址前缀长度的 线性遍历法 因为对于查找的第i 步来说匹配的是长度为i 的地址前缀 同理2 4 1 节介绍 的多分支t r i e 查找算法也是基于在地址前缀长度空间内的线性遍历法 但是由于它采用大 于1 的步宽 所遍历的地址长度数目变少了 查找性能得到了提高 2 4 4 节介绍的算法能 够在前缀长度空间内进行二分查找 所以从算法的复杂度来看它的性能更好 2 3 传统的路由查找算法 下面首先给出一示例路由表 如表1 以后的数据结构和算法均以此表作为例子 表1 选路表例 前缀标号前缀值下一跳地址 p 11 1 1 h l p 2l o h 2 p 31 0 1 0 h 3 p 41 0 l o l h 4 2 3 1 线性查找 线性表结构是最简单的查找数据结构 把所有的路由地址前缀用线性链表的方式组织 起来存储 每一次查找需要遍历线性表中的所有表项 遍历过程中记录最长的路由前缀项 直到遍历完整个线性链表 对于n 个路由前缀表项 查找过程的算法复杂度为0 0 叼 存 储空间复杂度为o n 插入删除路由表项的算法复杂度为o 1 假设表项插入删除的位 置是已知的 如果路由前缀按长度降序排列存储 则第一次匹配的查找结果就是符合最 长匹配原则的 这样平均查找时间可以得到减少 在表l 选路表例中 则前缀按p 4 p 3 第7 页 信息t 稃大学硕十学付论文 p 1 p 2 的顺序排列 显而易见 线性搜索算法直观简单 很容易实现 但是速度太慢 不能用于实际查表 2 3 2 缓存策略 在路由查表中 可以使用缓存策略 把最近查找过的目的地址路由存放在高速的路由 缓存表 r o u t ec a c h e 中 只有当路由缓存表中查找失败的时候 才需要进行真正完整的 前缀查找匹配过程 为了能够在查找性能上获得较大提高 缓存的命中率就需要有一定的保证 假设缓存 查找速度是路由前缀查找速度的2 0 倍 经过计算可以得出 为了能够使平均查找性能达 到原来的1 0 倍 缓存的命中率需要达到9 5 左右 随着i n t e m e t 的高速发展 网络用户的 不断增加以及业务数据流量的多样化 数掘流的时间局部性变得越来越不明显 从而大大 的降低了缓存的命中率 因此有文献建议缓存的大小应该能够随着网络用户或者网络数据 业务量的增加而相应线性的增加 但是在实际应用中 不够高的命中率 缓存搜索 缓存刷新等额外的负荷甚至可能降 低使用缓存策略后路由查表的性能 而且使用缓存必然导致不同i p 包路由查表时间的不均 匀性大大增加 而这正是路由查表硬件实现所要极力避免的情况 所以业界路由器生产厂 商如c i s c o j u n i p e r 和l u c e n t 的产品中都没有使用缓存策略 2 3 3r a d i xt i l e 树 无类型选路表通常存储在一个层状数据结构中 搜索是沿层次向下进行的 最流行的 数据结构是二叉树 b i n a r yt r i e 或者是根树 r a d i xt r i e 及其变形 其中地址静缀连续比 特的值决定了从根向下的路径 下图2 就是用二叉树存储表示的示例路由表 图2 二叉树结构存储的路由表 f 第8 页 信息工稃大学硕十学付论文 每个树结点包含的域 l 下一跳地址 如果该前缀存在 l 指向左分支指针指向右分支指针 在图2 中 一0 代表向左分支 1 1 代表向右分支 阴影结点f c g h 分别对应着前 缀p 1 p 2 p 3 p 4 而且可以发现实际上该二叉树的结点并没有存储前缀p 1 p 4 的值 p 1 p 4 的值是包含在抵达对应结点的路径中的 比如 c 是1 0 f 是1 1 1 因此二叉树是个 路径由所存储的数据 这里是前缀比特串 而确定的树 或者说是二叉树的路径就表示了 它所要存储的数据 在二叉树中 处于第l 层的结点代表了一类地址前l 比特均相同的地 址空间 并且这前l 个比特串就是由从根结点到这个结点路径上的l 比特组成 比如c 结 点就处在第二层 它代表了所有前两个比特为 1 0 的地址族 基于二叉树结构的路由查表就是根据目的地址的比特串逐比特搜索该二叉树 遇到匹 配的中间结点就记录下来 搜索中后发生的匹配必须覆盖任何更早发生的匹配 一直到叶 结点结束 若路由表最大前缀长度为w 则树的深度为w 最坏情况下需要w 次内存访问 最 长匹配查找复杂度为0 w 若有n 个前缀则存储复杂度为o o q w 注意到基本的二叉树 结构中每个结点包含三个域 而其实有相当的存储空间被浪费了 通过更巧妙的设计结点 域能够减少结点数节省存储空间 被称为l e a v ep u s h e d 树 如下图3 所示 d 图3l e a v e p u s h e d 树存储示例路由表 树结点域为 l e a v e p u s h e d 树结点数由8 个减少为6 个 查找效率也有提高 如p 4 只需4 次比特搜 索而图2 中需要5 次 另外一个前缀可能不只对应到一个结点上 如图3 中p 2 就对应了c 第9 页 信息t 程大学硕十学俯论文 e 两结点 这里已经隐含了前缀扩展的思想 2 3 4p a t r i c i a 树 可以看到基本的二叉树结构查找效率和存储效率都还是很低的 比如对于一组传统的 b 类地址上划分的子网地址 它们的前1 6 比特都是相同的 但是前述遍历二叉树结构一次 只提取一比特速度很慢 这种情况下一次检查目的地址的前1 6 比特会快的多 对二叉树的变形或修改以提高搜索效率 实质都是压缩二叉树中不必要的结构 其中 p a t r i c i a 树允许每个结点指定一个值 测试连续跳过的比特数以加快搜索速度 p a t r i c i a 树是基本二叉树 b i n a r yt r i e 的变型 它没有度为1 的结点也就是说p a t r i c i a 树是完全二叉树 前缀都存放在它的叶结点上 假设有n 个前缀则有n 个叶结点 另有 n 1 个内部结点 冗余的支路链被压缩到了一个结点 因此查找算法不需要做连续的比特 匹配而是可以一次匹配多个比特来快速到达叶结点 而每个内部结点都包含了一个 比特位 置 域来指示该结点以下的分支对应的比特位置 以便搜索算法知道匹配进行到的位置 但 是因为路径并不完整 故在到达叶结点时必须要进行前缀比特串的再匹配 下图4 是p a t r i c i a 树存储表示的示例路由表 p a t r i c i a 树内部结点域 1 0 1 0 8 1 0 1 0 i 图4p a t r i c i a 树存储的示例路由表 l 下一分支的 比特位置 l 指向左分支指针指向右分支指针 对p a t r i c i a 树的搜索能够较快的到达叶结点 即如果是较长的前缀则搜索效率较之基 本二叉树要高 如对于前缀p 4 仅需3 次匹配就可以完成查找 而b i n a r yt r i e 需要5 次 l e a v e p u s h e dt r i e 需要4 次 但是对短前缀一旦无法匹配则必须回退至别的分支或者是更上 层的结点 总的效率反而降低了 所以p a t r i c i a 树的查找复杂度是很高的 最长匹配查找 复杂度为o w 2 不过存储复杂度降低为o n 第1 0 页 信息丁稃大学硕七学位论文 伯克利大学的u n i x 中的路由查表使用的就是p a t r i c i a 树方案 通过在每个结点保持 清晰的父指针以避免递归实现 在p a t r i c i a 树中搜索深度为1 4 4 1 0 9 n n 为非前缀的结点 数 但是由前面知道前缀数 叶结点 比内部结点数大1 故n 其实就是前缀数 当n 9 8 0 0 0 时 需要的存储器访问次数是2 4 2 4 1 4 4 1 0 9 9 8 0 0 0 w d o e r i n g e r 提出一种p a t r i c i a 树的变型 称为动态前缀树的数据结构 1 支持非递归 的搜索实现和更新操作 但是其每个结点包含了多达6 个域 而且一次路由查表需要两次 遍历该树 更新操作也很复杂 不能很好的适应高速路由查表 2 3 5 路径压缩树 p a t hc o m p r e s s e dt r i e p a t r i c i a 树在压缩路径分支链时信息是有损失的 因为它只记录了该分支链最后的树支 来表示该链 比如图4 中结点b 和e 之间就略去了一个树支 与p a t r i c i a 树不同 路径压 缩树的结点存储了未压缩的基本二叉树中结点所代表的全部比特串信息 查找算法必须完 全匹配该结点的比特串值后才会遍历以该结点为根的子树 这样就避免了在p a t r i c i a 树中 的回退现象 将查找时间减少到w 次存储器访问即查找复杂度为0 w 同时存储复杂度 仍为o n 下图5 是以路径压缩树存储表示的示例路由表 阴影结点代表的是路由前缀 其中p 2 p 3 中的3 个值是压缩树结点域的前三项 路径压缩树结点域 l o i o l 图5 路径压缩树示例 l 可变长比特串下一跳 若前缀存在 比特位置 l 指向左分支的指针指向右分支的指针 数据结构的优化代表的是一种折衷 尽管优化提高了搜索速度 但在创建和修改选路 表时需要进行更多的计算 不过 大多数情况下这样的优化是值得的 因为选路表的修改 频率会比搜索它的频率小的多 第1 1 页 信息t 稃大学硕士学侥论文 然而如果只是局限于以上的方法 在i p v 4 下最大查找次数为3 2 仍然需要很大的内存 访问频率 实验表明 使用b s d 路径压缩t r i e 树来表示典型路由器中4 7 1 1 3 表项数目的 前缀表 1 最大搜索深度为2 6 平均搜索深度也达到了2 0 使用简单二进制t r i e 树来表示 同样的地址前缀表 它的最大搜索深度为3 0 平均搜索深度为2 2 它们的效率是比较低 的 2 4 路由查表新算法 2 4 1 多分支树 m u l t i e a r y t r i 1 基本算法 基本的二叉树搜索一步检查1 个比特 相应的若地址前缀最长为w 则树的深度为w 如果一次检查k 个比特则树的深度可减少到w k 这样树的内部结点度增加为2 的k 次幂 这样的树被称为2 的k 次幂分支树 树的最大层数为w 瓜 查找算法在每个结点处检查的 比特数为k 也就被称为树的步宽 最早将多分支树与前缀和路由表联系起来详细讨论的 资料见 照此定义则基本二叉树可看作是二分支树 成为多分支树的一个特例 路由前缀在多分支树中是按如下方式存储的 如果前缀的长度是k 的整数倍 如m k 则 该前缀存储在树的第r n 层 否则前缀长度不是k 的整数倍 则该前缀需要被扩展到多个长 度为k 的整数倍的前缀上 比如对于长度为k 1 的前缀就被扩展为两个长度为k 的前缀 以便存储在多分支树的结构中 下图6 是用四分支树存储表示的路由表例 四分支树结点域 图6 多分支树示例 l 下一跳地址 若前缀存在 f 指向 0 0 指向 0 1 指向 1 0 指向 1 1 图6 中可以看到 p 2 和p 3 是直接存储的并没有扩展 而p l p 4 因为长度不是2 的整 数倍被分别扩展为p l p l 和p 4 p 4 所有的前缀长度都是2 或4 被扩展为2 的整数倍了 第1 2 页 信息t 稃大学硕十学何论文 前缀扩展后每个结点包含有一组指针 指针的数量是2 的k 次幂 第j 个指针所指向的就 是该结点的第j 条分支 扩展前缀会导致多分支树结构消耗更多的存储容量 原因有以下两点 a 一条前缀 对应的下一跳地址在该i i 缀扩展后会存储在多分支树的多个结点中 b 在一个结点中无 用的空指针数量增加了 举例来说在图2 的基本二叉树结构中 有8 个结点7 条分支 因 而共有8 2 7 9 个空指针 但在图6 的四分支树中同样有8 个结点7 条分支 却有8 4 7 2 5 个空指针 因此 多分支树的查找速度提高是以消耗更大存储空间为代价的 多分支t r i e 树的查找过程与二分支t i l e 树的查找过程类似 在每次结点访问过程时 记录下到目前为止已经匹配上的最长地址i j 缀 直到到达叶子节点搜索过程结束 尽管多 分支t r i e 树的查找也是基于地址前缀长度的线性遍历法 但是因为多分支t r i e 树采用的步 宽大于1 所以它的搜索效率大大提高了 2 改进和优化算法 多分支t r i e 树设计的关键是步宽的选择 也就是如何在算法查找速度和算法消耗的存 储空间两个尺度上进行折衷 在极端情况下 可以使用一层步宽为3 2 的多分支t r i e 树 显 然在这种t i l e 树结构下每次查找只需要访问一次存储器操作就可以了 但是需要耗费多达 4 g 的表项存储空间 在现有条件下这是无法接受的 一种更为一般化的设想是在多分支树的每层设置不同的步宽 例如对于i p v 4 深度为 3 2 的基本二叉树可以变型为层数为4 的多分支树 而各层的步宽可设置为 l o 1 0 8 4 或是 8 8 8 8 等等 s f i n i v a s a n 等人 提出了一种多分支t r i e 树的优化算法 他们算 法的出发点是在多分支t r i e 树搜索深度固定的情况下 如何来选择合适的步宽来使得整个 t r i e 树的存储空间达到最小 在算法设计中他们根据实际地址前缀的特点使用了动态编程 d y n a m i cp r o g r a m m i n g 的思想来达到优化算法存储空间的目的 但是其步宽的选择依赖 于转发表的特性 使得这样的算法在硬件中难以实现 有的研究人员 2 1 将这种思路延伸得更为普遍 即允许每个树结点拥有不同的步宽 而 称这种树为可变步宽树 v a r i a b l e s t r i d et r i e 他们提出了另一种动态编程算法 在给定转 发表和树搜索深度的条件下计算每个树结点的最佳步宽 以此最小化该结构所需的存储 量 2 4 2 层压缩树 l c t r i e 我们已经看到 多分支树中以扩展自口缀的方法来压缩树的层次 所付出的代价是消耗 了更大存储空间 特别是在树结点稀少的部分 存储空间浪费的非常严重 此时 存储空 间利用率还不如使用路径压缩 本文2 3 5 技术来的高 n i l s s o n 等人 提出了融合路径压缩和前