路由协议与架构/链路状态算法

距离向量算法	路由协议与架构	分层路由
	链路状态算法

链路状态 (LS) 算法基于在整个网络中分发有关路由器邻域的信息。每个节点都可以创建网络地图（所有节点都一样），从中获得路由表。

组件

邻居问候
链路状态
泛洪算法
Dijkstra 算法
邻接建立

邻居问候

邻居问候是相邻节点之间定期交换的消息，用于收集有关邻接的信息。每个节点

发送邻居问候以向其邻居报告其存在；
接收邻居问候以了解其邻居以及到达邻居的成本。

邻居问候基于连续未收到邻居问候的最大数量来实现故障检测

快速：邻居问候可以以高频率发送（例如每 2 秒一次），以在很短的时间内识别邻接的变化
- 一旦收到，它们就不会被传播，而是停止在第一跳→它们不会使网络饱和；
- 它们是小型数据包，因为它们不包含除生成节点之外的节点信息；
- 它们对路由器来说开销很低，路由器不必在收到这些数据包时重新计算其路由表；
可靠：它不依赖于“链路建立”信号，在存在集线器的情况下不可用。

链路状态

每个路由器都会生成一个 LS，它是一组邻接-成本对

邻接：生成节点的所有邻居；
成本：生成路由器与其邻居之间链路的成本。

每个节点将来自网络中所有节点的所有 LS 存储在链路状态数据库中，然后扫描所有邻接的列表，并通过合并节点（路由器）和边（链路）来构建图，以便构建网络地图。

LS 生成主要基于事件：当本地拓扑（= 路由器邻域）发生变化时，就会生成一个 LS

路由器获得了新的邻居；
到达邻居的成本发生了变化；
路由器已失去与先前可达的邻居的连接。

基于事件的生成

允许更好地利用网络：它不消耗带宽；
它需要基于邻居问候的“hello”组件，因为路由器不能再使用周期性生成来检测其邻居的故障。

此外，路由器还实现周期性生成，频率非常低（以几十分钟为单位）

这提高了可靠性：如果一个 LS 由于某种原因丢失，它可以重新发送，而不必等待下一个事件；
这允许包含“年龄”字段：与已消失的目的地相关的条目保留在路由表中，数据包会继续发送到该目的地，直到信息在没有刷新之前变老，足以将其删除。

泛洪算法

每个 LS 必须以“广播”方式发送到网络中的所有路由器，所有路由器都必须以不变的形式接收它→真正的协议实现了一种选择性泛洪，它代表了使用相同数据到达所有路由器的唯一方法，并且开销最小。广播仅限于 LS，以避免网络饱和。

LS 传播速度很快：与 DV 不同，每个路由器都可以立即传播接收到的 LS，并在稍后本地处理它。

真实协议为 LS 传播实现了可靠机制：每个 LS 必须通过确认“逐跳”确认，因为路由器必须确保发送到其邻居的 LS 已被接收，还要考虑 LS 是以低频率生成的。

Dijkstra 算法

在从其邻接列表构建网络地图后，每个路由器都可以使用Dijkstra 算法来计算图的生成树，即以该节点为根的成本最小的路径树：在每次迭代中，都会考虑所有连接已选择节点与未选择节点的链路，并选择最近的相邻节点。

所有节点都具有相同的链路状态数据库，但每个节点都有一个不同的到达目的地的路由树，因为获得的生成树会随着选择的根节点的不同而变化

更好的流量分配：合理地，没有未使用的链路（与生成树协议不同）；
显然，路由树必须在各个节点之间保持一致。

邻接建立

在检测到新邻接时，需要建立邻接以同步路由器的链路状态数据库

新节点连接到网络：相邻节点向其传达所有与网络相关的 LS，以填充其链路状态数据库，它将能够从中计算其路由表；
两个分区子网（例如由于故障）重新连接在一起：链路端点处的两个节点中的每一个都向另一个节点传达与其子网相关的全部 LS。

过程

“hello”协议检测到新的邻接，该协议控制邻接；
同步是点对点过程，即它仅影响新链路端点处的两个路由器；
以前未知的 LS 以泛洪方式发送到网络中的其他节点。

在广播数据链路层网络上的行为

LS 算法将网络建模为一组点到点链路 → 它在存在广播 ^[1] 数据链路层网络（例如以太网）的情况下会遇到问题，在这些网络中，任何实体都可以直接访问同一数据链路上的任何其他实体（共享总线），从而创建一组完全连接的邻接关系（ $N$ 个节点 → ${\tfrac {N\left(N-1\right)}{2}}$ 个点到点链路）。

大量的邻接关系对 LS 算法有严重的影响

计算问题: Dijkstra 算法的收敛速度取决于链路的数量（ $L\cdot \log {N}$ ），但在广播网络中，链路的数量会激增；
传播 LS 时不必要的开销: 当路由器需要在广播网络上发送其 LS 时，它必须生成 $N-1$ 个 LS，每个邻居一个，即使只在共享通道上发送一次就能让所有邻居收到，然后每个邻居又会多次传播接收到的 LS（ $\sim N^{2}$ ）；
建立邻接关系时不必要的开销: 每当一个新的路由器添加到广播网络中时，它必须启动 $N-1$ 个建立阶段，每个邻居一个，即使只需要与其中一个重新对齐数据库就足够了。