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 则 表 示 此 结 点 代 表 的 路 由 前 缀 是 不 可 删 减

19、 的，应 更 新 至TCAM中。路 由 压 缩 在 增 加 路 由 和 删 除 路 由 时，都 需 要 进 行。图1，图2 为 增 加 路 由 和 删 除 路 由 时，路 由 压 缩 过 程 的 流 程 图。图 中，t c a m _ a d d 为 图3 所 示 的T C A M 增 加 前 缀 过 程；t c a m _ d e l e t e为图4所示的TCAM删除前缀过程；parent为结点的父结点指针。为 了 保 证T C A M 芯 片 可 进 行 最 长 匹 配 查 找，T C A M 内 的 路 由 前 缀 采 用 前 缀 链 约 束 顺 序 进行 组 织。前 缀 链 约 束

20、基 于Tries 树 结 构，我 们 维 护 一 个Tries 树 结 构 辅 助TCAM 的 路 由 前 缀 更新。我们把TCAM 内的空间划分为N 个子空间，分别为S1，S2，S3，.，SN-1，SN；每个子空间关联一个前缀区间，分别为L10，l1，L2l1+1，l2，.，LN-1lN-2+1，lN-1，LNlN-1+1，W，其中l1，l2，.，lN-1为0，W的整数，并且满足l1l2.lN-1；这些区间把路由前缀长度区间0，W03109123.7说 明 书 第4/7页6分 成 了 连 续 的N 段。(W 为I P 地 址 长 度，也 是 最 大 路 由 前 缀 长 度)。如 果 某 个

21、前 缀 它 的 前 缀长 度 属 于 前 缀 区 间 Lk，则 该 前 缀 在 T C A M 内 应 存 储 在 Sk子 空 间 中。图 5 为 T C A M 内 子 空 间划 分 的 示 意 图。图 中 灰 色 条 框 表 示T C A M 内 的 一 个 地 址 单 元。虚 线 表 示 前 缀 在T r i e s 树 中 的链关系。子 空 间 内 空 闲 的 空 间 位 于 低 地 址 端，这 与 把 空 闲 空 间 放 在 高 地 址 端 相 比，可 以 有 效 减 少更新时移动的次数。链中越靠近叶子的结点，结点的密度越大，如果空闲空间放在高地址端，添 加 靠 近 叶 子 结 点

22、时，它 们 的 父 结 点 需 要 频 繁 的 进 行 移 动 操 作，这 大 大 增 加 了 更 新 的 开 销。进 行 前 缀 更 新 时，首 先 根 据 前 缀 的 长 度 判 断 前 缀 所 属 的 子 空 间，然 后 在 对 应 的 子 空 间 内 进 行对 该 前 缀 进 行 添 加 和 删 除 操 作。下 面 对 子 空 间 内 前 缀 的 添 加 和 删 除 做 进 一 步 说 明。子空间内前缀增加 图6 为 子 空 间 内 前 缀 增 加 示 意 图。为 了 基 于 链 完 成 前 缀 更 新，我 们 需 要 为 每 个 前 缀 结 点p 在Tries 树结点增加两个变量：t

23、cam_index、hcld。tcam_indx 为p 结点前缀在TCAM 芯片中的 位 置。hcld 为 指 针，它 指 向p 结 点 多 个 前 缀 子 结 点 中，在TCAM 中 存 储 位 置 最 低 的 子 结 点。图6 中p 为新加入的前缀结点。按照图中箭头所示，首先把hcld(hcld(p)的前缀移至空闲空间，然 后hcld(p)的 前 缀 移 至hcld(hcld(p)所 在 位 置，最 后 把p 结 点 写 入hcld(p)所 在 位 置。图 3 为 在 T C A M 内 进 行 前 缀 增 加 整 个 过 程 的 流 程 图。对 流 程 图 的 步 骤 解 释 如 下：1

24、.设f n 为 增 加 的 前 缀 结 点，置 当 前 结 点p n f n，找 到 结 点f n 对 应 的 前 缀 子 空 间Lk；2.如果pn-hcld的前缀属于Lk子空间，跳至3；否则跳至4；3.把pn-hcld加入到hcld_array数组中，置pnpn-hcld，至2；4.按照图6所示的方法，顺序移动hcld_array数组中的结点前缀；图3中的变量i，为临时计数变量。子空间内前缀删除 图7 子 空 间 内 前 缀 删 除 的 示 意 图。为 了 基 于 链 进 行 前 缀 的 删 除，我 们 需 要 为Tries 树 中 每个 结 点p 增 加 一 个 变 量：parent。它

25、为 指 针，指 向p 结 点 的Tries 树 中 的 前 缀 父 结 点，同 时 我们 还 需 要 记 录 子 空 间 中 最 靠 近 空 闲 空 间 的 前 缀 结 点。如 图4 所 示，结 点p 为 要 删 除 的 结 点，q0 为最靠近空闲空间的结点，parent(q0)的位置低于结点p，parent(parent(q0)的位置高于p。我 们 按 照 下 面 的 步 骤 删 除 结 点p：首 先 把parent(q0)的 前 缀 移 至p 结 点 位 置，然 后 把q0的 前 缀移至parent(q0)的位置，最后释放q0所占的TCAM空间。图 4 为 在 T C A M 内 进 行

26、前 缀 删 除 整 个 过 程 的 流 程 图。对 流 程 图 的 步 骤 解 释 如 下：1.设f n 为 删 除 的 前 缀 结 点，所 属 子 空 间 为Lk，p0为Lk中 最 靠 近 空 闲 空 间 的 结 点，置 当 前结点pnp0；2.如果pn-parent的前缀位置低于fn结点，跳至3；否则跳至4；3.把p n-p a r e n t 加 入 到p a r e n t _ a r r a y 数 组 中，置p n p n-p a r e n t，跳 至2；03109123.7说 明 书 第5/7页7 4.按照图7所示方法，顺序移动parent_array数组中的结点；假 设Tri

27、es 树 中 最 大 链 长 为D，最 好 情 况 下，更 新 算 法 的 复 杂 度 为(D/N)；最 差 情 况 下，更 新 复 杂 度 为D。如 果 我 们 把 子 空 间 的 空 闲 区 间 放 在 中 间，更 新 算 法 的 性 能 会 近 一 步 提 高，最好情况下为D/2N，最差情况下为D/2。N 个 子 空 间 前 缀 区 间 的 划 分 直 接 影 响 着T C A M 的 更 新 性 能，不 合 适 的 划 分 将 导 致T C A M更 新 性 能 的 下 降。为 了 量 化 影 响，我 们 用 子 空 间 划 分 评 价 函 数T(W，N)对 划 分 进 行 评 价。T

28、(W，N)表 示 给 定 一 个 路 由 表，在 划 分N 情 况 下，更 新 前 缀 长 度 在0，W 之 间 的 路 由，TCAM芯 片 内 移 动 操 作 和 写 入 操 作 的 总 数 目。当T(W，N)达 到 最 小 时，我 们 认 为 此 时 划 分N 是 最 优的。为 了 计 算T(W，N)，我 们 采 用 递 规 的 思 想。假 设N 个 子 空 间 中 第N 个 子 空 间 的 前 缀 区 间为LN(i，W)，把0，W区间的前缀更新，分为两个部分：0，i-1区间和i，W区间。i，W区间前缀在子空间LN内更新，0，i-1 区间的前缀在L1到LN-1N-1 个子空间内更新。由此我

29、们可以得到T(W，N)的递规表达式。T(W，N)T(i-1，N-1)+F(i，W)(1)当T(W，N)最小时，我们会进一步得到(2)式：式(1)和(2)中，F(i，W)表 示 在 区 间i，W 内 的 前 缀，在LN子 空 间 内 更 新 所 需 操 作 的 数目。T(i-1，N-1)表 示 在 区 间0，i-1 内 的 前 缀，在L1到LN-1(N-1)个 子 空 间 内 更 新 时 所 需的 操 作。Tm i n(W，N)为T(W，N)的 最 小 值，Tm i n(i-1，N-1)为T(i-1，N-1)的 最 小 值。对于(2)式，我们可以推广得到更一般的表达式(3)：式(3)中，y 属于

30、区间1，W，x 属于区间1，N。Tm i n(y，x)表示对给定的路由表，在划分x 情 况 下，更 新 前 缀 长 度 在0，y 之 间 的 路 由，TCAM 芯 片 内 所 需 的 最 小 移 动 和 写 入 操 作 数。Tmin(i-1，x-1)表示在区间0，i-1内的前缀，在L1到Lx-1(x-1)个子空间内更新时所需的操作。F(i，y)表示在区间i，y内的前缀，在Lx子空间内更新所需操作的数目。实际计算过程中，为了避免递规，我们可以先计算初始值Tm i n(k1，1)(k11 to W)，然后 再 利 用(2)式 计 算Tm i n(k2，2)(k22 to W)，依 次 类 推，最

31、后 计 算Tm i n(W，N)，计 算 过程共需要计算(2*W-N+2)(N-1)/2+1)个T值。对F(i，W)值的计算除了考虑路由前缀在Trie 树中位置之外，还要考虑路由前缀插入的顺序。比如：Tries 树中某条链上有两个路由前缀，如果先加入靠近根节点的前缀，再加入远离根 节 点 的 前 缀 则 不 需 要 移 动 操 作，只 需 要 写 入 操 作，所 用 操 作 数 为2；如 果 先 加 入 远 离 根 结点 的 前 缀，再 加 入 靠 近 根 结 点 的 前 缀 则 需 要1 次 移 动 操 作，所 用 总 操 作 数 为3。为 了 方 便 计03109123.7说 明 书 第6

32、/7页8算，F(i，W)为左子结点链中可能的最大操作数。所谓左子结点链是指由下面结点组成的链：某个结点fn，fn的左子结点fn-l_child，fn-l_child的左子结点fn-l_child-l_child，.，依次类推，链中最后-个结点为fn的最左叶子结点。计 算 得 到Tm i n(W，N)同 时，我 们 也 可 以 得 到N 个 子 空 间 的 前 缀 区 间。计 算Tm i n(W，N)以及确定最佳K子空间划分的算法伪码，表示如下：N_Partition()初始化TW+1N+1数组；划分评价函数Tmin(y，x)初始化boundW+1N+1数组；前缀区间的边界 for(i1；iW；

33、i+)计算Ti1；for(x2；xN；x+)x循环 for(yx；yW；y+)y循环 利用递推公式(3)计算Tyx for(ix；iy；i+)t e m p T T i-1 x-1 +F(i，y)；t e m p T 和t e m p B o u n d 为 临 时 变 量 tempBoundi；if(tempTTyx)判断Tyx是否达到最小 boundyxtempBound；TyxtempT；得到N个子空间的前缀区间划分 N_BoundN-1boundWN；N_Bound数组为子空间前缀区间的边界 for(iN-2；i1；i-)N_BoundiboundN_Boundi+1i+1；RT为已知

34、路由表的Tries结构的根结点F(i，j)fnRT；count0；所有操作计数 while(fn！NULL)if(fn的前缀长度i&&fn的前缀长度j)判断fn的前缀是否在i，j区间 按照左子结点链计算操作数目 childfn-l_child；l_child为fn的左子结点 while(child！NULL)i f(c h i l d 的 前 缀 长 度 j)判 断c h i l d 是 否 在 区 间 i，j 内 count+；一次移动操作 childchild-l_child；03109123.7说 明 书 第7/7页9 count+；一次写入操作 fnfn的下一个结点；利

35、用fn的下一个结点遍历整个Tries树结构 函数F(i，j)表示长度在区间i，j 内的路由前缀，在TCAM 中更新时所用操作的数目。T 数组 中 的TW+1K+1 元 素 为 最 后 的Tm i n(W，K)值，N_boundi(i 1 到N-1)为N 个 子 空 间 的N-1个边界。得 到N 个 子 空 间 的 划 分 后，为 了 保 证 空 间 的 充 分 利 用，N 的 子 空 间 大 小 的 分 配 可 以 依 据各自空间内部路由前缀数目的多少来进行分配。路 由 压 缩 部 分 也 是 基 于T r i e s 结 构，它 可 以 兼 容 后 面 的T C A M 前 缀 更 新，并

36、且 压 缩 的 操作很简单，不会影响路由更新速度。用我们的压缩方法对Internet 中实际的路由表进行压缩，可以达到平均20的压缩比。由 于 路 由 压 缩 部 分 与TCAM 路 由 前 缀 更 新 部 分 都 是 基 于Tries 树 结 构，Tries 结 构 对IPv6路 由 表 具 有 很 好 的 扩 展 性，所 以 我 们 的 更 新 算 法 对IPv6 路 由 表 的 更 新 也 具 有 很 好 的 扩 展 性。03109123.7说 明 书 附 图第1/7页10图103109123.7说 明 书 附 图 第2/7页1103109123.7说 明 书 附 图 第3/7页12图2图303109123.7说 明 书 附 图 第4/7页13图403109123.7说 明 书 附 图 第5/7页14图503109123.7说 明 书 附 图 第6/7页15图603109123.7说 明 书 附 图 第7/7页16图7