2. 链路状态数据库 (The Link State Database)
-
链路状态数据库: 组织与计算
以下小节描述 OSPF 链路状态数据库 (link-state database) 的组织方式, 以及为了生成路由器路由表而在该数据库上执行的路由计算.
2.1. 路由器和网络的表示 (Representation of routers and networks)
Autonomous System 的链路状态数据库描述一张有向图. 图的顶点由路由器和网络组成. 当两台路由器通过物理点到点网络连接时, 图中用一条边连接这两台路由器. 连接路由器与网络的边表示该路由器在该网络上有接口. 网络可以是 transit network 或 stub network. Transit networks 能够承载既非本地产生、也非发往本地的数据流量. transit network 表示为一个同时具有入边和出边的图顶点. stub network 的顶点只有入边.
图中每个网络节点的邻域取决于网络类型 (point-to-point, broadcast, NBMA 或 Point-to-MultiPoint), 以及有接口连接到该网络的路由器数量. Figure 1a 描绘了三种情况. 矩形表示路由器. 圆形和椭圆表示网络. 路由器名称以字母 RT 为前缀, 网络名称以字母 N 为前缀. 路由器接口名称以字母 I 为前缀. 路由器之间的线表示点到点网络. 图左侧显示网络及其连接的路由器, 右侧显示得到的图.
**FROM**
* |RT1|RT2|
+---+Ia +---+ * ------------
|RT1|------|RT2| T RT1| | X |
+---+ Ib+---+ O RT2| X | |
* Ia| | X |
* Ib| X | |
Physical point-to-point networks
**FROM**
+---+ *
|RT7| * |RT7| N3|
+---+ T ------------
| O RT7| | |
+----------------------+ * N3| X | |
N3 *
Stub networks
**FROM**
+---+ +---+
|RT3| |RT4| |RT3|RT4|RT5|RT6|N2 |
+---+ +---+ * ------------------------
| N2 | * RT3| | | | | X |
+----------------------+ T RT4| | | | | X |
| | O RT5| | | | | X |
+---+ +---+ * RT6| | | | | X |
|RT5| |RT6| * N2| X | X | X | X | |
+---+ +---+
Broadcast or NBMA networks
Figure 1a: 网络拓扑组件
网络和路由器表示为顶点.
当 Column A 与 Row B 的交叉处标记为 X 时,
一条边连接 Vertex A 到 Vertex B.
Figure 1a 顶部显示两台通过点到点链路连接的路由器. 在得到的链路状态数据库图中, 两个路由器顶点由一对边直接连接, 每个方向一条. 点到点网络的接口不需要分配 IP 地址. 当分配接口地址时, 它们被建模为 stub links, 每台路由器都通告到另一台路由器接口地址的一条 stub 连接. 可选地, 可以给点到点网络分配一个 IP 子网. 在这种情况下, 两台路由器都通告到该 IP 子网的 stub link, 而不是通告彼此的 IP 接口地址.
Figure 1a 中部显示一个只有一台连接路由器的网络, 即 stub network. 在这种情况下, 该网络出现在链路状态数据库图中一条 stub 连接的末端.
当多台路由器连接到广播网络时, 链路状态数据库图显示所有路由器都与网络顶点双向连接. 这在 Figure 1a 底部示出.
图中的每个网络 (stub 或 transit) 都有一个 IP 地址和关联的网络掩码. 掩码指示网络上的节点数量. 直接连接到路由器的主机 (称为 host routes) 在图中表现为 stub networks. host route 的网络掩码始终为 0xffffffff, 表示存在单个节点.
2.1.1. 非广播网络的表示 (Representation of non-broadcast networks)
如前所述, OSPF 可以在非广播网络上以两种模式之一运行: NBMA 或 Point-to-MultiPoint. 模式选择决定 Hello protocol 和泛洪在非广播网络上的工作方式, 以及该网络在链路状态数据库中的表示方式.
在 NBMA 模式下, OSPF 模拟在广播网络上的运行: 为 NBMA 网络选举 Designated Router, 并由 Designated Router 为该网络产生 LSA. 广播网络和 NBMA 网络的图表示完全相同. 这种表示见 Figure 1a 中部.
从链路状态数据库大小和路由协议流量数量两方面看, NBMA 模式是在非广播网络上运行 OSPF 的最高效方式. 但是, 它有一个重要限制: 它要求连接到 NBMA 网络的所有路由器都能直接通信. 某些非广播网络可能满足此限制, 例如使用 SVC 的 ATM 子网. 但其他非广播网络通常不满足, 例如仅 PVC 的 Frame Relay 网络. 在并非所有路由器都能直接通信的非广播网络上, 可以将非广播网络拆分为逻辑子网, 使每个子网上的路由器能够直接通信, 然后把每个独立子网作为 NBMA 网络运行 (见 [Ref15]). 但是这需要相当多的管理开销, 且容易配置错误. 对这样的非广播网络, 以 Point-to-Multipoint 模式运行通常更好.
在 Point-to-MultiPoint 模式下, OSPF 将非广播网络上的所有 router-to-router 连接都视为点到点链路. 不为该网络选举 Designated Router, 也不会为该网络生成 LSA. 实际上, Point-to-MultiPoint 网络的顶点不会出现在链路状态数据库图中.
Figure 1b 展示 Point-to-MultiPoint 网络的链路状态数据库表示. 图左侧绘制了一个 Point-to-MultiPoint 网络. 假定除 RT4 和 RT5 之外, 所有路由器都可以直接通信. I3 到 I6 表示路由器在 Point-to-MultiPoint 网络上的 IP 接口地址. 在链路状态数据库的图形表示中, 可通过 Point-to-MultiPoint 网络直接通信的路由器由双向边连接, 并且每台路由器还有一条到其自身 IP 接口地址的 stub 连接 (这与真实点到点链路的表示不同; 见 Figure 1a).
在某些非广播网络上, 使用 Point-to-MultiPoint 模式和 Inverse ARP 等数据链路协议 (见 [Ref14]) 将允许 OSPF 邻居自动发现, 即使没有广播支持.
**FROM**
+---+ +---+
|RT3| |RT4| |RT3|RT4|RT5|RT6|
+---+ +---+ * --------------------
I3| N2 |I4 * RT3| | X | X | X |
+----------------------+ T RT4| X | | | X |
I5| |I6 O RT5| X | | | X |
+---+ +---+ * RT6| X | X | X | |
|RT5| |RT6| * I3| X | | | |
+---+ +---+ I4| | X | | |
I5| | | X | |
I6| | | | X |
Figure 1b: 网络拓扑组件
Point-to-MultiPoint networks
除 routers RT4 和 RT5 外, 所有路由器都能在 N2 上
直接通信. I3 到 I6 表示 IP 接口地址
2.1.2. 链路状态数据库示例 (An example link-state database)
Figure 2 显示一个 Autonomous System 的示例拓扑图. 标记为 H1 的矩形表示一个主机, 该主机通过 SLIP 连接到 Router RT12. 因此 Router RT12 正在通告一条 host route. 路由器之间的线表示物理点到点网络. 唯一分配了接口地址的点到点网络是连接 Routers RT6 和 RT10 的网络. Routers RT5 和 RT7 与其他 Autonomous Systems 有 BGP 连接. 两台路由器都显示了一组通过 BGP 学到的路由.
每个路由器接口的输出侧都有关联代价. 该代价可由系统管理员配置. 代价越低, 该接口越可能用于转发数据流量. 外部派生的路由数据, 例如 BGP 学到的路由, 也有关联代价.
Figure 2 中拓扑产生的有向图见 Figure 3. 弧上的标签是对应路由器输出接口的代价. 没有标记代价的弧代价为 0. 注意, 从网络指向路由器的弧代价始终为 0; 但它们仍然有意义. 还要注意, 外部派生的路由数据在图中表现为 stub.
链路状态数据库由路由器生成的 LSA 拼接而成. 在关联的图形表示中, 每台路由器或 transit network 的邻域都由单个独立 LSA 表示. Figure 4 以图形方式显示这些 LSA. Router RT12 有到两个广播网络的接口, 以及一条到主机的 SLIP 线路. Network N6 是一个连接三台路由器的广播网络. 从 Network N6 到其连接路由器的所有链路代价均为 0. 注意, Network N6 的 LSA 实际上由该网络连接路由器之一生成: 被选为该网络 Designated Router 的路由器.
+
| 3+---+ N12 N14
N1|--|RT1|\ 1 \ N13 /
| +---+ \ 8\ |8/8
+ \ ____ \|/
/ \ 1+---+8 8+---+6
* N3 *---|RT4|------|RT5|--------+
\____/ +---+ +---+ |
+ / | |7 |
| 3+---+ / | | |
N2|--|RT2|/1 |1 |6 |
| +---+ +---+8 6+---+ |
+ |RT3|--------------|RT6| |
+---+ +---+ |
|2 Ia|7 |
| | |
+---------+ | |
N4 | |
| |
| |
N11 | |
+---------+ | | N12
| | |6 2/
|3 | | +---+/
+---+ | |RT7|---N15
|RT9| | +---+ 9
+---+ | |1
|1 + | __|_
_|__ | Ib|5 / \
/ \ 1+----+2 | 3+----+1 * N6 *
* N9 *------|RT11|----|---|RT10|---\____/
\____/ +----+ | +----+ |
| | |
|1 + |1
+--+ 10+----+ N8 +---+
|H1|-----|RT12| |RT8|
+--+SLIP +----+ +---+
|2 |4
| |
+---------+ +--------+
N10 N7
Figure 2: Autonomous System 示例
**FROM**
|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
|1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
----- ---------------------------------------------
RT1| | | | | | | | | | | | |0 | | | |
RT2| | | | | | | | | | | | |0 | | | |
RT3| | | | | |6 | | | | | | |0 | | | |
RT4| | | | |8 | | | | | | | |0 | | | |
RT5| | | |8 | |6 |6 | | | | | | | | | |
RT6| | |8 | |7 | | | | |5 | | | | | | |
RT7| | | | |6 | | | | | | | | |0 | | |
* RT8| | | | | | | | | | | | | |0 | | |
* RT9| | | | | | | | | | | | | | | |0 |
T RT10| | | | | |7 | | | | | | | |0 |0 | |
O RT11| | | | | | | | | | | | | | |0 |0 |
* RT12| | | | | | | | | | | | | | | |0 |
* N1|3 | | | | | | | | | | | | | | | |
N2| |3 | | | | | | | | | | | | | | |
N3|1 |1 |1 |1 | | | | | | | | | | | | |
N4| | |2 | | | | | | | | | | | | | |
N6| | | | | | |1 |1 | |1 | | | | | | |
N7| | | | | | | |4 | | | | | | | | |
N8| | | | | | | | | |3 |2 | | | | | |
N9| | | | | | | | |1 | |1 |1 | | | | |
N10| | | | | | | | | | | |2 | | | | |
N11| | | | | | | | |3 | | | | | | | |
N12| | | | |8 | |2 | | | | | | | | | |
N13| | | | |8 | | | | | | | | | | | |
N14| | | | |8 | | | | | | | | | | | |
N15| | | | | | |9 | | | | | | | | | |
H1| | | | | | | | | | | |10| | | | |
Figure 3: 得到的有向图
网络和路由器表示为顶点.
当 Column A 与 Row B 的交叉处标记为 X 时,
一条代价为 X 的边连接 Vertex A 到 Vertex B.
**FROM** **FROM**
|RT12|N9|N10|H1| |RT9|RT11|RT12|N9|
* -------------------- * ----------------------
* RT12| | | | | * RT9| | | |0 |
T N9|1 | | | | T RT11| | | |0 |
O N10|2 | | | | O RT12| | | |0 |
* H1|10 | | | | * N9| | | | |
* *
RT12's router-LSA N9's network-LSA
Figure 4: 单独链路状态组件
网络和路由器表示为顶点.
当 Column A 与 Row B 的交叉处标记为 X 时,
一条代价为 X 的边连接 Vertex A 到 Vertex B.2.2. 最短路径树 (The shortest-path tree)
未配置 OSPF 区域时, Autonomous System 中每台路由器都有相同的链路状态数据库, 从而得到相同的图形表示. 路由器通过计算以自身为根的最短路径树, 从这张图生成自己的路由表. 显然, 最短路径树取决于执行计算的路由器. 我们示例中 Router RT6 的最短路径树见 Figure 5.
该树给出到任意目的网络或主机的完整路径. 但是, 转发过程中只使用到目的地的下一跳. 还要注意, 到任意路由器的最佳路由也已经计算出来. 对于外部数据处理, 我们记录到任何通告外部路由的路由器的下一跳和距离. Router RT6 得到的路由表见 Table 2. 注意, 对编号点到点网络的每一端都有单独路由 (在此例中, 即 Routers RT6 和 RT10 之间的串行线路).
属于其他 AS 的网络路由 (例如 N12) 在 Figure 5 的最短路径树中以虚线显示. 这种外部派生路由信息的使用将在下一节讨论.
RT6(origin)
RT5 o------------o-----------o Ib
/|\ 6 |\ 7
8/8|8\ | \
/ | \ 6| \
o | o | \7
N12 o N14 | \
N13 2 | \
N4 o-----o RT3 \
/ \ 5
1/ RT10 o-------o Ia
/ |\
RT4 o-----o N3 3| \1
/| | \ N6 RT7
/ | N8 o o---------o
/ | | | /|
RT2 o o RT1 | | 2/ |9
/ | | |RT8 / |
/3 |3 RT11 o o o o
/ | | | N12 N15
N2 o o N1 1| |4
| |
N9 o o N7
/|
/ |
N11 RT9 / |RT12
o--------o-------o o--------o H1
3 | 10
|2
|
o N10
Figure 5: Router RT6 的 SPF tree
未标记代价的边代价为零 (这些是 network-to-router links).
到 networks N12-N15 的路由是外部信息,
将在 Section 2.3 中考虑
Destination Next Hop Distance
__________________________________
N1 RT3 10
N2 RT3 10
N3 RT3 7
N4 RT3 8
Ib * 7
Ia RT10 12
N6 RT10 8
N7 RT10 12
N8 RT10 10
N9 RT10 11
N10 RT10 13
N11 RT10 14
H1 RT10 21
__________________________________
RT5 RT5 6
RT7 RT10 8Table 2: Router RT6 路由表中列出本地目的地的部分.
2.3. 外部路由信息的使用 (Use of external routing information)
创建树之后, 会检查外部路由信息. 该外部路由信息可能来自 BGP 等另一个路由协议, 也可能是静态配置 (static routes). 默认路由也可以作为 Autonomous System 外部路由信息的一部分包含在内.
外部路由信息会在整个 AS 中原样泛洪. 在我们的示例中, Autonomous System 中的所有路由器都知道 Router RT7 有两条外部路由, 度量分别为 2 和 9.
OSPF 支持两种外部 metric. Type 1 external metrics 使用与 OSPF 接口代价相同的单位表示, 即以链路状态度量表示. Type 2 external metrics 大一个数量级; 任意 Type 2 metric 都被视为大于 AS 内部任何路径的代价. 使用 Type 2 external metrics 假定 AS 之间路由是路由报文的主要代价, 并消除了把外部代价转换为内部链路状态 metric 的需要.
作为 Type 1 external metric 处理的示例, 假设 Figure 2 中 Routers RT7 和 RT5 正在通告 Type 1 external metrics. 对每条通告的外部路由, 从 Router RT6 出发的总代价计算为外部路由通告代价与 Router RT6 到通告路由器距离之和. 当两台路由器通告同一外部目的地时, RT6 选择提供最小总代价的通告路由器. 然后 RT6 将到外部目的地的下一跳设置为向所选通告路由器路由报文时使用的下一跳.
在 Figure 2 中, Router RT5 和 RT7 都在通告到目的 Network N12 的外部路由. Router RT7 更优, 因为它向 Router RT6 通告 N12 的距离为 10 (8+2), 优于 Router RT5 的 14 (6+8). Table 3 显示检查外部路由时添加到路由表中的条目:
Destination Next Hop Distance
__________________________________
N12 RT10 10
N13 RT5 14
N14 RT5 14
N15 RT10 17
Table 3: Router RT6 路由表中列出外部目的地的部分.
Type 2 external metrics 的处理更简单. 选择通告最小外部 metric 的 AS boundary router, 而不管到 AS boundary router 的内部距离如何. 假设在我们的示例中 Router RT5 和 Router RT7 都在通告 Type 2 external routes. 那么所有发往 Network N12 的流量都会转发给 Router RT7, 因为 2 < 8. 当存在多条等价代价 Type 2 routes 时, 使用到通告路由器的内部距离来打破平局.
Type 1 和 Type 2 external metrics 可以同时存在于 AS 中. 在这种情况下, Type 1 external metrics 始终优先.
本节假定发往外部目的地的报文总是通过通告的 AS boundary router 路由. 这并不总是理想的. 例如, 假设 Figure 2 中还有一台连接到 Network N6 的额外路由器, 称为 Router RTX. 再假设 RTX 不参与 OSPF 路由, 但与 AS boundary router RT7 交换 BGP 信息. 那么 Router RT7 最终会为所有应路由到 RTX 的目的地通告 OSPF external routes. 如果这些目的地的报文总是必须先路由到 Router RT7 (通告路由器), 有时会引入额外一跳.
为处理这种情况, OSPF 协议允许 AS boundary router 在其 AS-external-LSAs 中指定 "forwarding address". 在上述示例中, 对所有其报文应直接路由到 RTX 的目的地, Router RT7 会把 RTX 的 IP 地址指定为 "forwarding address".
"forwarding address" 还有另一个用途. 它使 Autonomous System 内部的路由器能够充当 "route servers". 例如, 在 Figure 2 中, router RT6 可以成为 route server, 通过静态配置和外部路由协议的组合获得外部路由信息. 随后 RT6 会开始把自己通告为 AS boundary router, 并产生一组 OSPF AS-external-LSAs. 在每个 AS-external-LSA 中, Router RT6 会通过适当设置该 LSA 的 "forwarding address" 字段, 指定该目的地应使用的正确 Autonomous System 出口点.2.4. 等价代价多路径 (Equal-cost multipath)
上述讨论通过只考虑到任意目的地的一条路由而被简化了. 实际上, 如果存在到目的地的多条等价代价路由, 它们都会被发现并使用. 这不需要对算法进行概念性改变, 其讨论推迟到我们更详细考虑树构建过程时进行.
通过 equal cost multipath, 路由器可能对任意给定目的地拥有多个可用下一跳.