2. 链路状态数据库 (The Link State Database)
-
链路状态数据库：组织与计算 (The Link-state Database: organization and calculations)
以下各小节描述 OSPF 链路状态数据库 (link-state database) 的组织方式，以及为了生成路由器的路由表而在该数据库上执行的路由计算。
2.1. 路由器与网络的表示 (Representation of routers and networks)
自治系统 (Autonomous System) 的链路状态数据库描述了一个有向图 (directed graph)。图的顶点 (vertices) 由路由器和网络组成。当两个路由器通过物理点到点 (point-to-point) 网络相连时，一条图边 (edge) 连接这两个路由器。一条连接路由器与网络的边表示该路由器在该网络上有一个接口。网络可以是中转网络 (transit) 或末梢网络 (stub networks)。中转网络是那些能够承载既非本地发起、也非本地终结的数据流量的网络。中转网络由一个具有入边和出边的图顶点表示。末梢网络顶点只有入边。 图中每个网络节点的邻域 (neighborhood) 取决于网络的类型（点到点、广播、NBMA 或 Point-to-MultiPoint）以及拥有该网络接口的路由器数量。图 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: Network map components 网络和路由器由顶点表示。 当且仅当顶点 A 的列与顶点 B 的行的 交叉处标有 X 时，存在一条边连接 顶点 A 与顶点 B。 图 1a 顶部显示两个由点到点链路连接的路由器。在生成的链路状态数据库图中，两个路由器顶点由一对边直接连接，每个方向各一条。点到点网络的接口不必分配 IP 地址。当分配了接口地址时，它们被建模为末梢链路 (stub links)，每台路由器通告一个到另一台路由器接口地址的末梢连接。可选地，可以给点到点网络分配一个 IP 子网 (subnet)。在这种情况下，两台路由器都通告一个到该 IP 子网的末梢链路，而不是通告彼此的 IP 接口地址。 图 1a 中间显示了一个仅连接一台路由器（即末梢网络）的网络。在这种情况下，该网络在链路状态数据库的图中出现在一条末梢连接的末端。 当多个路由器连接到同一个广播网络时，链路状态数据库图显示所有路由器与该网络顶点双向连接。这描绘在图 1a 的底部。 图中的每个网络（末梢或中转）都有一个 IP 地址和关联的网络掩码 (network mask)。掩码指示网络上的节点数。直接连接到路由器的主机（称为主机路由，host routes）作为末梢网络出现在图上。主机路由的网络掩码总是 0xffffffff，表示存在单个节点。 2.1.1. 非广播网络的表示 (Representation of non-broadcast networks) 如前所述，OSPF 可以在非广播 (non-broadcast) 网络上以两种模式之一运行：NBMA 或 Point-to-MultiPoint。模式的选择决定了 Hello 协议 (Hello protocol) 和泛洪 (flooding) 在非广播网络上的工作方式，以及该网络在链路状态数据库中的表示方式。 在 NBMA 模式下，OSPF 模拟在广播网络上的运行：为 NBMA 网络选举一个 Designated Router (指定路由器)，并且 Designated Router 为该网络始发一个 LSA (Link State Advertisement)。广播网络和 NBMA 网络的图表示是相同的。这种表示描绘在图 1a 的中间部分。 NBMA 模式是在非广播网络上运行 OSPF 最高效的方式，无论就链路状态数据库的大小而言，还是就路由协议流量的数量而言。然而，它有一个显著的限制：它要求连接到 NBMA 网络的所有路由器都能直接通信。这一限制在某些非广播网络上可以满足，例如利用 SVC 的 ATM 子网。但在其他非广播网络上常常无法满足，例如仅支持 PVC 的帧中继 (Frame Relay) 网络。在并非所有路由器都能直接通信的非广播网络上，你可以将非广播网络拆分为逻辑子网 (logical subnets)，每个子网上的路由器能够直接通信，然后将每个独立的子网作为 NBMA 网络运行（参见 [Ref15]）。然而这需要相当大的管理开销，并且容易出现配置错误。对于这样的非广播网络，可能更适宜以 Point-to-Multipoint 模式运行。 在 Point-to-MultiPoint 模式下，OSPF 将非广播网络上的所有路由器到路由器的连接视为点到点链路。不为该网络选举 Designated Router，也不为该网络生成 LSA。事实上，Point-to-MultiPoint 网络的顶点不会出现在链路状态数据库的图中。 图 1b 说明了 Point-to-MultiPoint 网络的链路状态数据库表示。在图的左侧描绘了一个 Point-to-MultiPoint 网络。假定所有路由器都能直接通信，路由器 RT4 和 RT5 除外。I3 到 I6 表示路由器在 Point-to-MultiPoint 网络上的 IP 接口地址。在链路状态数据库的图形表示中，能够通过 Point-to-MultiPoint 网络直接通信的路由器由双向边连接，并且每台路由器还有一个到其自身 IP 接口地址的末梢连接（这与真实点到点链路的表示不同；参见图 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: Network map components Point-to-MultiPoint networks 除路由器 RT4 和 RT5 外，所有路由器都能 通过 N2 直接通信。I3 至 I6 表示 IP 接口地址 2.1.2. 一个链路状态数据库示例 (An example link-state database) 图 2 显示了一个 Autonomous System 的示例拓扑图。标记为 H1 的矩形表示一个主机 (host)，它通过一条 SLIP 连接连到路由器 RT12。因此路由器 RT12 正在通告一条主机路由。路由器之间的连线表示物理点到点网络。唯一分配了接口地址的点到点网络是连接路由器 RT6 和 RT10 的那一个。路由器 RT5 和 RT7 拥有到其他 Autonomous System 的 BGP 连接。为这两台路由器都显示了一组 BGP 学习到的路由。 一个代价 (cost) 与每个路由器接口的输出侧相关联。该代价可由系统管理员配置。代价越低，该接口越有可能被用来转发数据流量。代价也与外部派生的路由数据（例如 BGP 学习到的路由）相关联。 由图 2 中的拓扑图生成的有向图 (directed graph) 描绘在图 3 中。弧 (arcs) 标有相应路由器输出接口的代价。没有标代价值的弧代价为 0。注意，从网络指向路由器的弧的代价总是 0；尽管如此它们仍然有意义。还应注意，外部派生的路由数据作为末梢出现在图上。 链路状态数据库由路由器生成的 LSA 拼装而成。在关联的图形表示中，每个路由器或中转网络的邻域在单一、独立的 LSA 中表示。图 4 以图形方式显示这些 LSA。路由器 RT12 有一个到两个广播网络的接口，以及一条到主机的 SLIP 线路。网络 N6 是一个拥有三个附加路由器的广播网络。从网络 N6 到其附加路由器的所有链路的代价为 0。注意，网络 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 _|_ _|__ | 3+----+1 / \ / \ 1+----+2 | +----+ \____/ * N9 *------|RT11|----|---|RT10|---* N6 * \____/ +----+ | +----+ \____/ | | | |1 + |1 +--+ 10+----+ N8 +---+ |H1|-----|RT12| |RT8| +--+SLIP +----+ +---+ |2 |4 | | +---------+ +--------+ N10 N7 Figure 2: A sample 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: The resulting directed graph Networks and routers are represented by vertices. An edge of cost X connects Vertex A to Vertex B iff the intersection of Column A and Row B is marked with an X. **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: Individual link state components Networks and routers are represented by vertices. An edge of cost X connects Vertex A to Vertex B iff the intersection of Column A and Row B is marked with an X.2.2. 最短路径树 (The shortest-path tree)
当未配置 OSPF 区域 (areas) 时，Autonomous System 中的每个路由器拥有完全相同的链路状态数据库，从而产生完全相同的图形表示。路由器通过以自身为根计算一棵最短路径树 (shortest-path tree)，从该图生成其路由表。显然，最短路径树取决于执行计算的路由器。我们示例中路由器 RT6 的最短路径树描绘在图 5 中。 该树给出了到任何目的网络或主机的完整路径。然而，在转发过程中只使用到目的地的下一跳 (next hop)。还应注意，到任何路由器的最佳路由也已计算出来。为了处理外部数据，我们记录通告外部路由的任何路由器的下一跳和距离。路由器 RT6 生成的路由表描绘在表 2 中。注意，对于一个编址 (numbered) 点到点网络的每一端都有一条独立的路由（本例中是路由器 RT6 和 RT10 之间的串行线路）。 属于其他 AS（例如 N12）的网络路由在图 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: The SPF tree for Router RT6 Edges that are not marked with a cost have a cost of of zero (these are network-to-router links). Routes to networks N12-N15 are external information that is considered in 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: The portion of Router RT6's routing table listing local destinations.
这些外部派生的路由信息将在下一节中考虑。2.3. 外部路由信息的使用 (Use of external routing information)
树构建完成后，检查外部路由信息。这些外部路由信息可能源自另一个路由协议（如 BGP），或是静态配置的（静态路由，static routes）。默认路由 (default routes) 也可以作为 Autonomous System 外部路由信息的一部分包含进来。 外部路由信息以未改变的方式 (unaltered) 泛洪到整个 AS。在我们的示例中，Autonomous System 中的所有路由器都知道路由器 RT7 有两条外部路由，度量 (metrics) 分别为 2 和 9。 OSPF 支持两类外部度量 (external metrics)。Type 1 外部度量以与 OSPF 接口代价相同的单位表示（即，以链路状态度量的形式）。Type 2 外部度量大一个数量级；任何 Type 2 度量都被视为大于 AS 内部任何路径的代价。使用 Type 2 外部度量假设 AS 之间的路由是路由一个报文的代价的主要构成部分，并且消除了将外部代价转换为内部链路状态度量的需要。 作为 Type 1 外部度量处理的例子，假设图 2 中的路由器 RT7 和 RT5 正在通告 Type 1 外部度量。对于每条通告的外部路由，从路由器 RT6 出发的总代价计算为外部路由的通告代价与从路由器 RT6 到通告路由器的距离之和。当两台路由器通告相同的外部目的地时，RT6 选择提供最小总代价的通告路由器。RT6 于是将到该外部目的地的下一跳设置为等于路由报文到所选通告路由器时所使用的下一跳。 在图 2 中，路由器 RT5 和 RT7 都在通告到目的网络 N12 的外部路由。路由器 RT7 被优先选择，因为它以到路由器 RT6 距离 10 (8+2) 通告 N12，这优于路由器 RT5 的 14 (6+8)。表 3 显示了在检查外部路由时添加到路由表中的条目： Destination Next Hop Distance __________________________________ N12 RT10 10 N13 RT5 14 N14 RT5 14 N15 RT10 17 Table 3: The portion of Router RT6's routing table listing external destinations. Type 2 外部度量的处理更简单。无论到 AS 边界路由器 (AS boundary router) 的内部距离如何，都选择通告最小外部度量的 AS 边界路由器。假设在我们的示例中路由器 RT5 和路由器 RT7 都在通告 Type 2 外部路由。那么所有发往网络 N12 的流量都将被转发到路由器 RT7，因为 2 < 8。当存在多条等价 (equal-cost) Type 2 路由时，使用到通告路由器的内部距离来打破平局 (tie)。 Type 1 和 Type 2 外部度量可以同时存在于 AS 中。在这种情况下，Type 1 外部度量总是优先。 本节假定发往外部目的地的报文总是通过通告的 AS 边界路由器路由。这并不总是可取的。例如，假设在图 2 中网络 N6 上附加了另一台名为路由器 RTX 的路由器。进一步假设 RTX 不参与 OSPF 路由，但与 AS 边界路由器 RT7 交换 BGP 信息。那么，路由器 RT7 将最终为所有应当路由到 RTX 的目的地通告 OSPF 外部路由。如果发往这些目的地的报文总是需要先路由到路由器 RT7（通告路由器），有时就会引入额外的一跳。 为了处理这种情况，OSPF 协议允许 AS 边界路由器在其 AS-external-LSA 中指定一个 "forwarding address"（转发地址）。在上例中，路由器 RT7 将为所有其报文应当直接路由到 RTX 的目的地，指定 RTX 的 IP 地址作为 "forwarding address"。 "forwarding address" 还有另一个用途。它使 Autonomous System 内部的路由器能够充当 "route servers"（路由服务器）。例如，在图 2 中路由器 RT6 可以成为一个路由服务器，通过静态配置和外部路由协议的组合获得外部路由信息。RT6 于是将开始通告自身为 AS 边界路由器，并始发出一组 OSPF AS-external-LSA。在每个 AS-external-LSA 中，路由器 RT6 通过适当设置 LSA 的 "forwarding address" 字段，为目的地指定要使用的正确 Autonomous System 出口点。2.4. 等价多路径 (Equal-cost multipath)
上述讨论通过仅考虑单一到任何目的地的路由而得以简化。实际上，如果到目的地存在多条等价路由，它们都会被发现并被使用。这不需要对算法做任何概念上的改变，其讨论推迟到我们更详细地考虑树的构建过程时。
有了等价多路径 (equal cost multipath)，路由器可能拥有多个到任何给定目的地的可用下一跳。