界又提出了简化 ＳＰＦ 算法。 １．３ 简化 ＳＰＦ 算法
简化 ＳＰＦ 算法是先判断链路的变化是否 需 要 重 构 ＳＰＴ 树，如 果 不 影 响 ＳＰＴ 结 构，采 用 ＰＲＣ 进 行 路 由 信 息更新；如果影响到 ＳＰＴ，则 所 有 节 点 直 接 进 行 全 部 的 ＳＰＦ 计算重构 ＳＰＴ。简化 ＳＰＦ 算法需要记录整个网络 的拓扑关系，保存每次 ＳＰＦ 计 算 生 成 的 ＳＰＴ 树。 此 时 ＰＲＣ 用来处理网络拓扑不变而 路 由 信 息 发 生 改 变 的 情 况 ，这 样 就 是 根 据 网 络 变 化 的 不 同 情 况 做 出 最 精 简 的 处 理，使得路由计算处理 工 作 量 降 到 最 低，从 而 大 大 节 约 路由计算所用时间 。 ［８］
１ 常 见 的 路 由 计 算 方 案 分 析
１．１ ＳＰＦ 算法 ＳＰＦ 最短路径 优 先 算 法，采 用 Ｄｉｊｋｓｔｒａ算 法，在 链
路状态路由协 议 中 用 来 计 算 到 网 络 的 最 短 路 径 。 ［２］ 每 台路由器都 是 以 自 己 为 根 节 点，其 他 路 由 器 为 叶 子 节 点，根据网络拓扑信息 生 成 一 棵 最 短 路 径 树 ＳＰＴ，然 后 计算出根节点到 各 个 目 的 地 的 最 短 路 径，但 ＳＰＦ 并 不 保存这棵最短路径树，当 链 路 状 态 发 生 变 化 时，不 论 是 否影响网络 的 拓 扑 结 构，ＳＰＦ 只 能 再 次 全 部 重 新 计 算 一遍这棵最短路径树 。 ［３］ 网络规模扩大的时候，链 路 状 态变化频率增加，ＳＰＦ 计 算 频 度 增 加，同 时 链 路 状 态 数 据库随之增大，每次 ＳＰＦ 的计算时间也会很长，基 于 以
关键词：ＩＳＩＳ；ＳＰＦ；ＩＳＰＦ；ＰＲＣ；简化 ＳＰＦ；半拓扑 ＳＰＦ 中 图 分 类 号 ：ＴＮ９１５－３４ 文 献 标 识 码 ：Ａ 文 章 编 号 ：１００４－３７３Ｘ（２０１１）１９－００９４－０３
Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍ Ａｎａｌｙｓｉｓ ｏｆ ＩＳＩＳ Ｐｒｏｔｏｃｏｌ
上面已经 介 绍 了 各 种 链 路 变 化 以 及 是 否 需 要 重 构 ＳＰＴ，有些链路的变化是不需要重构 ＳＰＴ 的。简化 ＳＰＦ 算 法 与ＩＳＰＦ 计 算 时 间 相 比 ，判 定 链 路 变 化 是 否 需 要 重 新 计算拓扑的时间复杂度比确定受影响的节点范围的时间 复杂度小得多 ，虽 然 计 算 全 部 拓 扑 的 时 间 大 于 增 量 拓 扑 计算的时间，但对于节点变化影响大部分网络拓扑时，简 化 ＳＰＦ 算 法 能 够 减 少 很 多 无 效 计 算 。 但 有 时 变 化 的 节 点 靠 近 叶 子 节 点，受 影 响 的 节 点 范 围 很 小，全 部 节 点 进 行 ＳＰＦ 计算又增加 了 路 由 计 算 时 间 ，没 有 充 分 利 用 原 来 的 ＳＰＴ［９］，因此本文提出了半拓扑 ＳＰＦ算法。
Ｋｅｙｗｏｒｄｓ：ＩＳＩＳ；ＳＰＦ；ＩＳＰＦ；ＰＲＣ；ｓｉｍｐｌｉｆｉｅｄ ＳＰＦ；ｓｅｍｉ－ｔｏｐｏｌｏｇｉｃａｌ ＳＰＦ
ＯＳＰＦ 协议 过 于 复 杂 大 大 限 制 了 支 持 的 路 由 器 的 数量和 路 由 的 条 数，ＩＳＩＳ 路 由 协 议 相 对 于 ＯＳＰＦ 来 说 实现简单，所以越 来 越 多 的 企 业来自百度文库采 用ＩＳＩＳ 协 议 作 为 网 络中的ＩＧＰ 协议［１］，如 何 更 高 效 的 实 现ＩＳＩＳ 协 议 是 当 前 研 究 的 热 点 。 路 由 计 算 是 协 议 的 核 心 部 分 ，因 此 加 快 路 由 计 算 来 加 快 路 由 收 敛 越 来 越 受 到 重 视 ，很 多 学 者 研 究改进路由算法来加快路由计算。本文分析了几种工 业中应用的 路 由 算 法 和 它 们 的 不 足，在 此 基 础 上 提 出 一种半拓扑 ＳＰＦ 算法。
２０１１ 年 １０ 月 １ 日 第 ３４ 卷 第 １９ 期
现代电子技术
Ｍｏｄｅｒｎ Ｅｌｅｃｔｒｏｎｉｃｓ Ｔｅｃｈｎｉｑｕｅ
Ｏｃｔ．２０１１ Ｖｏｌ．３４ Ｎｏ．１９
ＩＳＩＳ路由协议中路由计算研究
李俊杰
（北 京 交 通 大 学 ，北 京 １０００４４）
摘 要：路由算法在路由器中至关重 要，好 的 路 由 算 法 能 够 提 高 路 由 器 性 能。 分 析 了 目 前 常 用 的 几 种ＩＳＩＳ 路 由 算 法， ＳＰＦ、ＩＳＰＦ 和 ＰＲＣ 以及工业界采用的简化 ＳＰＦ 算法。在此基础上提出一种改进方案是半拓扑 ＳＰＦ 算法，在较稳定的网络中 使得路由计算速度大大提高。
链路状态变化对路由计算的影响： （１）ｃｏｓｔ增 加 ，处 于 删 除 状 态 的ｌｉｎｋ 看 作 是ｃｏｓｔ从 有效值增加 到 无 穷 大。 若ｌｉｎｋ 不 是 ＳＰＴ 上 的 有 效 路 径，ｃｏｓｔ增加后不 影 响 ＳＰＴ 树 结 构，不 需 重 新 计 算；若 ｌｉｎｋ在 ＳＰＴ 上，ｃｏｓｔ增加需要重新计算。 （２）ｃｏｓｔ减 少 ，新 增ｌｉｎｋ 可 看 作 是ｃｏｓｔ从 无 穷 减 少 到有效值。ｃｏｓｔ减少时无论ｌｉｎｋ在不在 ＳＰＴ 上都需要 重 新 计 算 ，因 为 此 时 可 能 影 响 其 他 路 由 器 的 路 径 。 （３）若仅仅是ｌｉｎｋ 的 下 一 跳 （邻 居 路 由 器）变 化 或 者协议类型变化（由ＩＳＩＳ 变 为 ＯＳＰＦ），ｃｏｓｔ不 变，则 不 需 重 新 计 算 ，只 需 更 新 相 关 节 点 的 下 一 跳 。
ＰＲＣ 计算是为了处理变化的ＩＳＩＳ路由，而ＩＳＩＳ 路 由的变化由叶子节点变化引起。系统节点的变化必然 引起系统节点上 叶 子 节 点 的 变 化，因 此 在 ＰＲＣ 计 算 时 要先处理变化的系统 节 点，然 后 处 理 变 化 的 叶 子 节 点。 ＰＲＣ 算法实现 时 先 提 交 变 化 节 点，将 节 点 下 的 路 由 放 入路由变化表中，然后 遍 历 路 由 变 化 列 表，将 变 化 的 路 由下刷到路由管理的ＩＰ 路由表。 １．２．３ ＩＳＰＦ 算法的不足
ＩＳＰＦ 第一次计算 时 要 计 算 全 部 节 点，之 后 只 计 算 变化的部分，每次计算 完 成 后 要 记 录 整 个 拓 扑 关 系，保 存生成的最短路径 树 ＳＰＴ，ＩＳＰＦ 能 够 形 成 一 个 直 接 反 映网络拓扑 的 “图”状 数 据 库，而 计 算 出 的 ＳＰＴ 则 保 存 在这个“图”中 。 ［５］ 当链路状态发生变化时，根据上 述 原 则判断是否需重 构 ＳＰＴ 树，若 需 要 则 按 一 定 原 则 得 到 拓 扑 变 化 影 响 到 的 节 点 ，然 后 在 受 影 响 的 节 点 范 围 内 做 ＳＰＦ 计算即ＩＳＰＦ，其 他 未 受 到 影 响 的 节 点 拓 扑 关 系 保 持不变。根据增量 计 算 结 果 更 新 ＳＰＴ 树，并 将 受 到 影 响节点的路由进行更新，即 ＰＲＣ 部分路由计算。 １．２．２ ＰＲＣ 部分路由计算
ＬＩ Ｊｕｎ－ｊｉｅ
（Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １０００４４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｖｅｒｙ ｉｍｐｏｒｔａｎｔ ｉｎ ｔｈｅ ｒｏｕｔｅｒ，ｗｈｉｃｈ ｃａｎ ｉｍｐｒｏｖｅ ｒｏｕｔｅｒ′ｓ ｐｅｒｆｏｒｍａｎｃｅ．Ｓｅｖｅｒａｌ ｃｏｍｍｏｎ ＩＳＩＳ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｓｕｃｈ ａｓ ＳＰＦ，ＩＳＰＦ，ＰＲＣ ａｎｄ ａ ｓｉｍｐｌｉｆｉｅｄ ＳＰＦ ａｌｇｏｒｉｔｈｍ ｕｓｅｄ ｉｎ ｔｈｅ ｉｎｄｕｓｔｒｙ ａｒｅ ａｎａｌｙｚｅｄ．Ａ ｓｅｍｉ－ｔｏ－ ｐｏｌｏｇｉｃａｌ ＳＰＦ ｉｓ ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ ｉｍｐｒｏｖｅｓ ｒｏｕｔｅ ｃａｌｃｕｌａｔｉｏｎ ｓｐｅｅｄ ｇｒｅａｔｌｙ ｉｎ ｔｈｅ ｓｔａｂｌｅ ｎｅｔｗｏｒｋ．
网络拓扑 变 化 的 位 置 不 同，受 到 影 响 的 范 围 就 不 同，ＩＳＰＦ 计算所消 耗 的 时 间 就 不 同。 最 坏 情 况 是 整 个 拓扑受 到 影 响，ＩＳＰＦ 相 当 于 进 行 了 全 部 重 新 计 算。 ＩＳＰＦ算法进行路由计算 的 时 间 包 括 搜 寻 受 影 响 节 点 的 计算时间，增 量 路 由 计 算 的 时 间 和 ＰＲＣ 计 算 的 时 间。 一般情况下搜寻受影响节点的计算和增量路由计算的 时间总和会比计算全 部 拓 扑 的 时 间 少，因 此ＩＳＰＦ 在 大 多数情况下能够减 少 计 算 开 销、增 加 收 敛 速 度。 但ＩＳ－ ＰＦ 算法实现流程过 于 复 杂，在 某 种 网 络 中 的 计 算 效 率 比 ＳＰＦ 还要差［７］，例 如 某 一 链 路 的 变 化 引 起 整 个 拓 扑 结 构 的 变 化 ，则 增 量 路 由 计 算 的 时 间 其 实 是 整 个 拓 扑 计 算的时间，使用ＩＳＰＦ 算法还 增 加 了 搜 寻 时 间，此 时ＩＳ－ ＰＦ 算法反而会比传统的 ＳＰＦ 算法 开 销 更 大，因 此 工 业
收 稿 日 期 ：２０１１－０４－１８
上不足，工业界提出了ＩＳＰＦ 算法和 ＰＲＣ 结合的改进方 案。 １．２ ＩＳＰＦ 算法和 ＰＲＣ 算法结合 １．２．１ ＩＳＰＦ 算法介绍
ＩＳＰＦ（Ｉｎｃｒｅｍｅｎｔａｌ ＳＰＦ）是 指 增 量 路 由 计 算，它 每 次 只 对 变 化 的 一 部 分 路 由 进 行 计 算 ，而 不 是 对 全 部 路 由 重新计算［４］。ＩＳＰＦ 改进 了 ＳＰＦ 算 法，第 一 次 计 算 时 需 要计算全部节点，之后 只 是 计 算 受 影 响 的 节 点，大 大 降 低了 ＣＰＵ 的占用率，提高了网络收敛速度。ＩＳＰＦ 算法 实现的关键点是如何选取要计算的最小范围和如何在 选定的范围内重新计 算，同 时 要 求：每 次 计 算 完 成 后 保 存 ＳＰＴ，记录 ＳＰＴ 上每个节点的路径；建立节点同路由 之 间 的 对 应 关 系 ，每 次 只 更 新 变 化 节 点 的 路 由 信 息 。
２ 半拓扑 ＳＰＦ算法
半拓扑 ＳＰＦ 算法是先判断链路的变化是 否 影 响 网 络的拓扑结构，是否需要重构 ＳＰＴ 树，如果不影响 ＳＰＴ 结构，直接采用 ＰＲＣ 更 新 路 由 信 息；如 果 影 响 到 ＳＰＴ， 则 判 断 变 化 的 链 路 指 向 的 节 点 在 网 络 中 的 拓 扑 层 次 ，若 在上层则 全 部 节 点 进 行 ＳＰＦ 计 算，若 在 下 层 则 采 用 ＩＳＰＦ找出 受 影 响 的 节 点 进 行 变 化 部 分 的 增 量 路 由 计 算，重构 ＳＰＴ 后采用 ＰＲＣ 算法更新路由。 半拓扑 ＳＰＦ 算法需要记 录 整 个 网 络 的 拓 扑 关 系，同 时 要 保 存 每 次 ＳＰＦ 计算生成的 ＳＰＴ 树，还 要 保 存 每 个 路 由 器 所 在 的 网络层次。
第 １９ 期
李 俊 杰 ：ＩＳＩＳ 路 由 协 议 中 路 由 计 算 研 究
９５
（４）ＳＰＴ 上节点状态变化对ｌｉｎｋ的影响。节点处于 删除 状 态 ，则 与 该 节 点 相 连 的 所 有ｌｉｎｋ 都 标 记 为 删 除 状 态 ，需要重新计 算 ；节 点 处 于 过 载 状 态 ，则 所 有 到 达 该 节 点的ｌｉｎｋ都标记为受影响状态，需要重新计算；节点从过 载状态恢复正常或者是新增节点，则 ＳＰＴ 上节点到该节 点的ｌｉｎｋ都标记为受影响状态，需要重新计算。
ＰＲＣ 是部分路由计算，它与ＩＳＰＦ 配 合 使 用。ＰＲＣ 的原理也是只计 算 变 化 的 那 一 部 分，但 ＰＲＣ 不 需 要 计 算节点路径，而 是 根 据 ＩＳＰＦ 算 出 来 的 ＳＰＴ 来 更 新 路 由 。 ［６］ 如果ＩＳＰＦ 计 算 后 的 ＳＰＴ 改 变，ＰＲＣ 处 理 所 有 变化的节 点 上 的 所 有 路 由；如 果 经 过 ＩＳＰＦ 计 算 后 的 ＳＰＴ 并没 有 变 化，只 有 叶 子 节 点 变 化，则 ＰＲＣ 只 处 理 变化的叶子节点的路由信息。