CN1447223A.PDF
《CN1447223A.PDF》由会员分享,可在线阅读,更多相关《CN1447223A.PDF(16页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、19中华人民共和国国家知识产权局12发明专利申请公开说明书11公开号CN 1447223A43公开日2003年10月8日21申请号03109123.721申请号03109123.722申请日2003.04.0471申请人清华大学地址 100084北京市北京10008482信箱72发明人梁志勇 徐恪 51Int.CI7G06F 9/00 权利要求书 1 页 说明书 7 页 附图 7 页54发明名称支持路由压缩的TCAM高速更新方法57摘要 支持路由压缩的TCAM高速更新方法属于互联网IP地址高速查找技术领域,其特征在于它是一种把都基于树结构的路由压缩以及建立在三态内容可寻址存储器(TCAM)芯片
2、内的空间划分为N个子空间的前缀链约束基础上的前缀更新这两个步骤前后合在一起的TCAM高速更新方法,其中,判断前缀是否需更新的原则是该结点是否冗余,冗余则不更新,反之,则更新;在判断N个子空间的划分是否影响TCAM更新性能时,使用了子空间划分评价函数。它具有支持高速的路由更新,支持有效的路由表压缩,对IPv6协议具有很好的扩展性的优点。03109123.7权 利 要 求 书第1/1页2 1.支持路由压缩的TCAM高速更新方法含有路由压缩的步骤,其特征在于:它是一种把都基于树结构的路由压缩和建立在把TCAM(三态内容可寻址存储器)芯片内的空间划分为N个子空间的前缀链约束基础之上的前缀更新这两个步骤
3、前后合在一起的TCAM高速更新方法,它依次含有以下步骤:(1)在树结构中,找到代表更新路由的结点fn,更新路由是指增加路由或删除路由;(2)判断fn的前缀是否需要更新至TCAM中:若需要更新,则执行步骤(3);若无需更新,则执行步骤(4);(3)把fn的前缀更新至TCAM;(4)判断fn的子结点是否需要更新至TCAM中:若需要更新,则执行步骤(5);若无需更新,则执行步骤(6);(5)把fn子结点的前缀更新至TCAM;(6)更新结点fn的数据成员;其 中,所 述 的 步 骤(3)把f n 的 前 缀 更 新 至T C A M,它 依 次 含 有 以 下 步 骤:3.1利用评价函数Tmin(W,
4、N)把TCAM空间划分为N子空间,其中:W表示IP地址长度,也是最大路由前缀长度;N表示划分子空间的个数;Tm i n(W,N)表示0,W长度区间的前缀,在N子空间划分下,移动操作和写入操作总和的最小值;Tmin(i-i,N-1)表示0,i-1长度区间的前缀,在N-1子空间划分下,移动操作和写入操作总和的最小值;F(i,W)表示在区间i,W 内的前缀,在一个子空间内更新所需操作的数目。3.2 根 据 前 缀 的 长 度 找 到T C A M 中 对 应 的 前 缀 子 空 间Lk lk-1+1,lk;3.3 在子空间Lk内,按照前缀链约束,对树中链上的路由前缀进行移动操作;3.4把fn的前缀更
5、新至TCAM中;2.根据权利要求1所述的支持路由压缩的TCAM高速更新方法,其特征在于:所述的步骤(2),判断fn的前缀是否需要更新至TCAM中的原则是,此路由前缀是否冗余,即此路由前缀若和其父结点具有相同的下一跳地址和出端口,也就是说,它们的转发结果是一样的,则此路由前缀在路由表中是冗余的,则不更新至TCAM;否则,就需要更新至TCAM中。03109123.7说 明 书第1/7页3支持路由压缩的TCAM高速更新方法 技术领域 支 持 路 由 压 缩 的T C A M(三 态 内 容 可 寻 址 存 储 器)高 速 更 新 方 法 属 于 互 联 网 中 高 速I P 地址查找领域。背景技术
6、TCAM(Ternary Content Addressable Memory 三态内容可寻址存储器)技术是近年出现的 一 种 硬 件 查 找 技 术,它 可 以 实 现 高 速 的 路 由 查 找。T C A M 芯 片 内 部 使 用 并 行 技 术,可 获 得O(1)的 查 找 复 杂 度。目 前 市 场 上 可 获 得 的T C A M 芯 片 的 查 找 速 度 最 快 可 达1 0 0 M 次/秒。和 其他 路 由 查 找 技 术 相 比,T C A M 技 术 优 势 在 于 查 找 速 度 快,实 现 比 较 简 单。但 它 也 存 在 下 面 三个 缺 点:1、成 本 高。T
7、 C A M 芯 片 要 比 相 同 存 储 空 间 的S R A M,D R A M 贵 很 多。2、功 耗 大。T C A M 芯 片 内 部 采 用 并 行 技 术 进 行 关 键 字 的 比 较,内 部 的 功 耗 很 大。3、路 由 更 新 复 杂。用T C A M 技 术 实 现 最 长 前 缀 查 找 时,路 由 前 缀 在T C A M 芯 片 内 需 要 按 照 一 定 的 顺 序 进 行 排 序,这使得路由更新操作相对复杂。Internet 网络中,拓扑是动态变化的,路由也是动态改变的。路由器为了保证分组的转发正 确,必 须 快 速 的 对 路 由 改 变 做 出 反 映,
8、及 时 的 把 新 路 由 加 入 到 路 由 表,并 把 过 期 路 由 从 路由 表 中 删 除。路 由 更 新 的 处 理 速 度 成 为 路 由 查 找 方 案 的 一 个 重 要 评 价 指 标。低 效 率 的 路 由 更新会大大影响TCAM的路由查找性能,增加路由查找的延迟。对 于T C A M 技 术 的 三 个 缺 点,研 究 者 提 出 了 相 应 的 解 决 方 案。对 于 缺 点1、2,可 以 通 过压 缩 路 由 表 的 方 法 来 解 决。压 缩 后 的 路 由 表 对T C A M 存 储 空 间 的 需 求 减 少,使 用 较 小 容 量 的T C A M 芯 片
9、 就 可 满 足 存 储 要 求,这 就 减 少 了 T C A M 技 术 的 成 本,同 时 使 用 小 容 量 的 T C A M芯 片 也 减 少 了芯 片 内 部 的 功 耗 以 及 散 热。Liu 基 于Prunning(删 减)和Mask Extension(掩码扩 展)技 术,提 出 一 种T C A M 的 路 由 表 压 缩 算 法。该 算 法 对I n t e r n e t 网 络 中 实 际 路 由 表,可达 到40 左 右 的 压 缩 比。但 算 法 的 更 新 过 程 复 杂,更 新 速 度 很 慢,难 以 满 足Internet 网 络 中路由更新的速度。对 于
10、 缺 点3,S h a h 基 于T C A M 中 前 缀 链 约 束 的 路 由 排 序 方 式(T r i e s 树 结 构 中,从 根 结点 到 叶 子 结 点 的 路 径 称 为 链,前 缀 链 约 束 是 指 链 上 出 现 的 路 由 前 缀 应 按 照 越 靠 近 叶 子 的 前 缀存 储 在 越 低 的 地 址 的 规 则 在T C A M 中 存 储),提 出C A O _ O P T 路 由 更 新 算 法。最 差 情 况 下,CAO_OPT 算 法 的 更 新 复 杂 度 为O(D/2)(D 为Tries 树 中 最 大 链 长 度),平 均 情 况 下,CAO_OP
11、T的 更 新 复 杂 度 可 达O(AD/2)(AD 为Tries 树 中 所 有 链 的 平 均 长 度)。当 路 由 表 中 路 由 前 缀 比 较少 时,A D 值 也 比 较 小,C A O _ O P T 算 法 性 能 很 好。但 随 着 路 由 前 缀 的 增 加,T r i e s 树 结 点 分布 越 来 越 密 集,A D 值 也 随 之 增 加,C A O _ O P T 算 法 性 能 相 应 下 降。尤 其 对I P v 6 协 议,地 址03109123.7说 明 书 第2/7页4长 度 从32Bits 扩 展 为128Bits,路 由 表 中 的 路 由 前 缀
12、数 目 大 大 增 加,CAO_OPT 算 法 的 性 能 会下降很多。发明内容 本发明的目的在于提供一种支持路由压缩的TCAM高速更新方法。本 发 明 提 出 的 查 找 方 法 的 特 征 在 于,它 是 一 种 把 都 基 于 树 结 构 的 路 由 压 缩 和 建 立 在 把T C A M(三 态 内 容 可 寻 址 存 储 器)芯 片 内 的 空 间 划 分 为N 个 子 空 间 的 前 缀 链 约 束 基 础 之 上 的前 缀 更 新 这 两 个 步 骤 前 后 合 在 一 起 的 T C A M 高 速 更 新 方 法,它 依 次 含 有 以 下 步 骤:(1)在 树 结 构 中
13、,找 到 代 表 更 新 路 由 的 结 点f n,更 新 路 由 是 指 增 加 路 由 或 删 除 路 由;(2)判断fn的前缀是否需要更新至TCAM中:若需要更新,则执行步骤(3);若无需更新,则执行步骤(4);(3)把fn的前缀更新至TCAM;(4)判断fn的子结点是否需要更新至TCAM中:若需要更新,则执行步骤(5);若无需更新,则执行步骤(6);(5)把fn子结点的前缀更新至TCAM;(6)更新结点fn的数据成员;其中,所述的步骤(3)把fn的前缀更新至TCAM,它依次含有以下步骤:3.1利用评价函数Tmin(W,N)把TCAM空间划分为N子空间,其中:W表示IP地址长度,也是最大
14、路由前缀长度;N表示划分子空间的个数;Tm i n(W,N)表 示0,W 长 度 区 间 的 前 缀,在N 子 空 间 划 分 下,移 动 操 作 和 写 入 操 作 总 和的最小值;Tm i n(i-1,N-1)表示0,i-1 长度区间的前缀,在N-1 子空间划分下,移动操作和写入操作总和的最小值;F(i,W)表 示 在 区 间 i,W 内 的 前 缀,在 一 个 子 空 间 内 更 新 所 需 操 作 的 数 目。3.2根据前缀的长度找到TCAM中对应的前缀子空间Lklk-1+1,lk;3.3在子空间Lk内,按照前缀链约束,对树链上的路由前缀进行移动操作;3.4把fn的前缀更新至TCAM中
15、;所 述 的 步 骤(2),判 断f n 的 前 缀 是 否 需 要 更 新 至T C A M 中 的 原 则 是,此 路 由 前 缀 是 否冗 余,即 此 路 由 前 缀 若 和 其 父 结 点 具 有 相 同 的 下 一 跳 地 址 和 出 端 口,也 就 是 说,它 们 的 转 发03109123.7说 明 书 第3/7页5结 果 是 一 样 的,则 此 路 由 前 缀 在 路 由 表 中 是 冗 余 的,则 不 更 新 至T C A M;否 则,就 需 要 更 新至TCAM中。使 用 证 明:它 有 以 下 特 点:支 持 高 速 的 路 由 更 新,支 持 有 效 的 路 由 表 压
16、 缩,对IPv6 协 议具有很好的扩展性。附图说明 图1.增加前缀时路由更新的程序流程框图。图2.删除前缀时路由更新的程序流程框图。图3.TCAM 前 缀 增 加 的 程 序 流 程 框 图(hcld-prefixlen:hcld 结 点 前 缀 的 前 缀 长 度)。图 4.T C A M 前 缀 删 除 的 程 序 流 程 框 图(P0:子 空 间 最 靠 近 空 闲 区 域 的 前 缀 结 点)。图5.TCAM内N子空间划分。图6.子空间内增加前缀示意图。图7.子空间内删除前缀示意图。具体实施方式 为 了 减 少 T C A M 芯 片 成 本 和 功 耗,我 们 对 T C A M 路
17、 由 表 进 行 压 缩。压 缩 的 基 本 思 想 是向 T C A M 内 更 新 路 由 前 缀 时,首 先 判 断 一 下 此 路 由 前 缀 是 否 冗 余,如 果 冗 余 则 不 更 新 至T C A M,这 减 少 了T C A M 空 间 的 使 用。判 断 路 由 前 缀 是 否 冗 余 成 为 路 由 压 缩 部 分 设 计 的 主 要问题。基 于T r i e s 树 的 路 由 表 结 构 中,如 果 路 由 前 缀P 1 为 路 由 前 缀P 2 的 父 结 点,同 时P 1 具 有和P2 相 同 的 下 一 跳 地 址 和 出 端 口,那 么 路 由 查 找 结 果
18、 为P1 和P2,它 们 的 转 发 结 果 是 一 样 的。这 时,P 2 在 路 由 表 中 是 冗 余,我 们 可 以 对P 2 可 以 实 行 删 减,不 把P 2 的 路 由 前 缀 写 入 到T C A M芯片中。基于这样的思想我们进行路由压缩。为了支持压缩,我们需要对Tries 结点增加一个标 记prun_flag,如 果prun_flag 为1 则 表 示 该 结 点 代 表 的 路 由 前 缀 是 可 删 减 的,不 用 更 新 至T C A M 芯 片 中,如 果p r u n _ f l a g 为0 则 表 示 此 结 点 代 表 的 路 由 前 缀 是 不 可 删 减
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CN1447223A
限制150内