路由协议和架构/路由算法

转发和路由	路由协议和架构	距离向量算法
	路由算法

路由算法是协作类型的一种流程，负责在每个中间节点上决定到达目的地的方向。

它确定每个节点可达目的地。
- 它生成关于本地网络可达性的信息：路由器通知其邻居路由器本地网络存在，并且可以通过它到达。
- 它接收关于远程网络可达性的信息：邻居路由器通知路由器远程网络存在，并且可以通过它到达。
- 它传播关于远程网络可达性的信息：路由器通知其他邻居路由器远程网络存在，并且可以通过它到达。
它根据某些标准以协作方式与其他节点一起计算最佳路径（下一跳）。
- 必须建立一个度量：一条路径可能是基于一个度量最好的路径，但不是基于另一个度量。
- 标准必须在网络中的所有节点之间一致，以避免循环、黑洞等。
- 算法必须自动运行，以避免人工配置错误并有利于可扩展性。
它将本地信息存储在每个节点的路由表中：路由算法不需要了解网络的整个拓扑结构，它只关心构建正确的路由表。

理想路由算法的特点

简单实现：错误更少，易于理解等。
轻量级执行：路由器在运行算法时应尽可能少地消耗资源，因为它们的 CPU 和内存有限。
最优：计算出的路径应根据选择的度量是最优的。
稳定：只有在拓扑结构或成本发生变化时才应该切换到另一条路径，以避免路由震荡，即首选路由频繁变化，随之而来的瞬态周期过长。
公平：它不应偏袒任何特定的节点或路径。
健壮：它应该能够自动适应拓扑结构或成本变化
- 故障检测：它不应依赖外部组件来检测故障（例如，如果故障发生在集线器之外，则无法在物理层检测到它）。
- 自动稳定：在网络发生变化的情况下，它应该收敛到一个解决方案，而无需任何外部干预（例如，明确的手工配置）。
- 拜占庭容错：它应该识别并隔离由于故障或恶意攻击而发送虚假信息的邻居节点。
  互联网没有实现拜占庭容错，但它基于信任→故障和恶意行为需要人工干预。

路由算法分类

非自适应算法（静态）：它们独立于网络状况做出决策
- 静态路由（或固定目录路由）
- 随机游走
- 泛洪，选择性泛洪
自适应算法（动态）：它们了解有关网络的信息以更好地做出决策
- 集中式路由
- 隔离路由：热土豆，反向学习
- 分布式路由：距离向量，链路状态
分层算法：它们允许路由算法在广泛的基础设施上扩展。

度量

度量是衡量一条路径好坏的指标，它通过将物理量（例如距离、传输速度）或它们的组合转换为数值形式（成本）来获得，以便选择成本最低的路径作为最佳路径。

对于所有类型的流量，不存在最佳度量：例如，带宽适合文件传输流量，而传输延迟适合实时流量。度量的选择可以从 IP 数据包中的“服务类型”（TOS）字段确定。

问题

（非）优化：路由器的主要任务是转发用户流量，而不是花时间计算路径→最好优先选择即使没有完全优化，也不会影响网络主要功能并且不会表现出用户可以感知到的问题的解决方案
- 复杂度：组合的标准越多，算法就越复杂，运行时所需的计算资源就越多。
- 稳定性：基于链路可用带宽的度量太不稳定，因为它取决于瞬时流量负载，而瞬时流量负载在时间上变化很大，并且可能导致路由震荡。
不一致：网络中节点采用的度量必须一致（对于每个数据包），以避免循环的风险，即数据包在使用不同冲突度量的两个路由器之间“弹跳”。

瞬态

现代路由算法总是“活跃的”：它们不断交换服务消息以自动检测故障。但是，它们不会更改路由表，除非检测到状态更改

拓扑结构更改：链路故障，添加新目的地。
成本更改：例如，一条 100 Mbps 链路升级到 1 Gbps。

状态更改会导致瞬态阶段：分布式系统中的所有节点不能同时更新，因为变化以有限的速度在整个网络中传播→在瞬态期间，网络中的状态信息可能不一致：某些节点已经有了新的信息（例如，检测到故障的路由器），而其他节点仍然拥有旧的信息。

并非所有状态更改对数据流量的影响都相同

正状态更改：瞬态的影响是有限的，因为网络可能只是暂时处于次优状态
- 一条路径的成本变得更低：一些数据包可能仍然按照现在变得不太方便的旧路径前进。
- 添加了新的目的地：由于通往它的路径上的黑洞，该目的地可能看起来不可到达。
负状态更改：瞬态的影响对用户来说更为严重，因为它也会干扰不应该受故障影响的流量
- 链接故障发生：并非所有路由器都已了解旧路径不再可用→数据包可能开始在备用链接上“来回弹跳”，导致备用链接饱和（路由循环）；
- 路径成本变差：并非所有路由器都已了解旧路径不再方便→类似于故障情况（路由循环）。

一般而言，在瞬态期间，有两个常见问题会影响路由算法：黑洞和路由循环。

黑洞

黑洞定义为：即使存在至少一条可以到达特定目的地的路径，路由器也无法得知任何路径（暂未得知）。

影响

对数据流量的影响仅限于指向相关目的地的数据包，这些数据包会被丢弃，直到节点更新其路由表并获取有关如何到达目的地的信息。指向其他目的地的流量完全不受黑洞影响。

路由循环

路由循环定义为从路由角度来看的循环路径：路由器将数据包发送到一条链路上，但由于路由表不一致，链接另一端路由器将数据包发送回原路由器。

影响

指向相关目的地的数据包开始在链路上“来回弹跳”（弹跳效应）→链接变得饱和→穿越该链接的指向其他目的地的流量也会受到影响。

备用路由

备用路由是一个主要用于基于层次结构组织的电话网络的概念：每个交换机通过主路由连接到上级交换机，并通过备用路由连接到另一个上级交换机→如果主路由出现故障，备用路由可以立即投入使用，无需任何瞬态过程。

数据网络则基于网状拓扑结构，路由器以多种方式相互连接→无法预见网络中所有可能的故障以预先安排备用路径，但当出现故障时，路由算法优选自动计算出备用路径（即使计算步骤需要瞬态过程）。

现代网络中的备用路由仍然可以应用

通过ADSL连接到互联网的公司，当ADSL线路断开时，可以通过切换到HiperLAN技术（无线）的备用路由来保持连接；
互联网骨干网现在掌握在电话公司手中，这些公司根据电话网络的标准对其进行了建模→其组织结构具有足够的层次性，可以预先安排备用路由。

多路径路由

使用网络地址进行路由时，所有指向目的地的数据包都遵循相同的路径，即使存在备用路径→最好将部分流量沿备用路径发送，即使备用路径的成本更高，也不要使算法选择的路径饱和。

多路径路由也称为“负载共享”，是一种流量工程功能，旨在将指向同一目的地的流量分布到多条路径（如果可用），在路由表中为每个目的地创建多个条目，以便更有效地使用网络资源。

非等成本多路径路由

仅当备用路径的成本 $c_{\text{sec}}$ 不明显大于最小成本主路径的成本 $c_{\text{prim}}$ 时，才会使用备用路径

{\text{given }}K\geq 1,\,c_{\text{sec}}\geq c_{\text{prim}}:\;{\text{sec used}}\Leftrightarrow c_{\text{sec}}\leq K\cdot c_{\text{prim}}

流量与路径成本成反比分布。例如在这种情况下

{\begin{cases}c_{\text{prim}}=10\\c_{\text{sec}}=20\end{cases}}\Rightarrow {\begin{cases}{\text{prim}}=66\%{\text{ traffic}}\\{\text{sec}}=33\%{\text{ traffic}}\end{cases}}

路由器可以决定以66%的概率将数据包沿主路径发送，以33%的概率沿备用路径发送。

问题

对于给定的数据包，每个路由器会自主决定沿哪条路径转发→路由器之间可能做出不一致的决定，导致数据包进入路由循环，并且由于转发通常基于会话，因此该数据包将永远无法退出循环

等成本多路径路由

只有当备用路径的成本 $c_{\text{sec}}$ 恰好等于主路径的成本 $c_{\text{prim}}$ 时，才会使用备用路径 ( $K=1$ )。

{\text{given }}c_{\text{sec}}\geq c_{\text{prim}}:\;{\text{sec used}}\Leftrightarrow c_{\text{sec}}=c_{\text{prim}}

流量在两条路径上均等分配（50%）。

问题

如果第一个数据包走的是慢速路径，而第二个数据包走的是快速路径，TCP 机制可能会导致整体性能下降。

等成本多路径路由引起的问题。
TCP 排序问题。
传输速率下降。

TCP 排序问题：数据包可能乱序到达：第二个数据包在第一个数据包之前到达目的地 → 用于排序序号的处理过程会占用接收端的计算资源；
传输速率下降：如果第一个数据包的确认包（ACK）到达太晚，源端会认为第一个数据包丢失了 → 当 3 个重复（累积）ACK 到达且超时时间到期时，TCP 滑动窗口机制会启动
- 快速重传：源端会不必要地再次传输数据包 → 数据包会重复；
- 快速恢复：源端会认为网络拥塞 → 它会通过限制传输窗口来降低数据包发送速度：将阈值设置为当前拥塞窗口值的一半，并使拥塞窗口从值 1 重新开始（即一次只发送一个数据包，并在发送下一个数据包之前等待其 ACK）。

标准

真正的多路径路由实现会将流量拆分，使得到达同一目的地的流量走相同的路径。

基于流的：每个传输层会话由五元组标识
1. <源 IP 地址>
2. <目标 IP 地址>
3. <传输层协议类型>（例如 TCP）
4. <源端口>
5. <目标端口>
路由器会存储一个表，将会话标识符映射到输出端口
1. 由于支持的各种数据包格式（VLAN、MPLS 等），从数据包中提取构成会话 ID 的字段很繁琐；
2. 对于分片 IP 数据包，传输层端口信息不可用；
3. 在会话 ID 表中查找五元组很繁琐；
4. 通常 TCP 连接关闭不是“优雅退出”，也就是说 FIN 和 ACK 数据包不会被发送 → 会话 ID 表中的条目不会被清除 → 需要一个线程来定期清理旧条目，方法是查看它们的 timestamp；
基于数据包的：路由器会将具有偶数（目标或源或两者）IP 地址的数据包发送到一条路径，而将具有奇数 IP 地址的数据包发送到另一条路径 → 哈希操作非常快。

问题

到达同一目的地的流量不能同时使用两条路径 → 如果有大量流量到达某个特定目的地（例如，两个服务器之间的夜间备份），就会出现问题。

非自适应算法

静态路由

网络管理员会在每台路由器上手动配置其路由表。

缺点

如果网络发生变化，则需要手动更新路由表。

应用

静态路由主要用于网络边缘的路由器

边缘路由器不允许传播路由信息到骨干网：核心路由器会阻止来自边缘的所有广告，否则用户可能会宣传一个地址与现有网络（例如 google.com）相同的网络，并将他重定向到指向该网络的部分流量。
由于用户不能宣传自己的网络，如何才能从外部访问它们？ ISP 了解其出售给用户的网络所使用的地址，必须配置核心路由器，使其即使没有本地连接也能将这些网络广告给其他路由器；
边缘路由器不允许接收来自骨干网的路由信息：边缘路由器通常通过单个链路连接到核心路由器 → 一个全局默认路由足以访问整个互联网。

随机漫步

当数据包到达时，路由器会随机选择一个端口（但不是接收数据包的端口），并将数据包发送到该端口。

应用

当数据包到达目的地的概率很高时，它很有用

对等网络（P2P）：用于内容查找；
传感器网络：发送消息应该是低功耗操作。

泛洪

当数据包到达时，路由器会将数据包发送到所有端口（但不是接收数据包的端口）。

数据包可能有一个“跳数”字段，用于将泛洪限制到网络的一部分。

应用

军事应用：在攻击情况下，网络可能会损坏 → 数据包能够到达目的地至关重要，即使这会导致大量重复流量；
链路状态算法：每个路由器在接收到来自邻居的网络地图后，必须将其传播给其他邻居： A4. 链路状态算法#泛洪算法.

选择性泛洪

当数据包到达时，路由器首先检查它是否已在过去收到并泛洪。

旧数据包：它会丢弃它；
新数据包：它会存储并将其发送到所有端口（但接收到的端口除外）。

每个数据包通过发送者标识符（例如源 IP 地址）和序列号来识别

如果发送者从网络断开连接或关闭，当它再次连接时，序列号将从头开始 → 路由器将所有接收到的数据包视为旧数据包；
序列号编码在有限数量的位上 → 应选择序列号空间，以最大程度地减少错误地识别为旧数据包的新数据包。

序列号空间

线性空间

如果选择性泛洪用于少量控制消息，则可以容忍它

当序列号达到最大可能值时，会发生溢出错误；
旧数据包：序列号低于当前序列号；
新数据包：序列号大于当前序列号。

循环空间

它解决了序列号空间耗尽问题，但如果数据包到达的序列号与当前序列号相差太远，它就会失败

当序列号达到最大可能值时，序列号将从最小值重新开始；
旧数据包：序列号位于当前序列号之前的半部分；
旧数据包：序列号位于当前序列号之后的半部分。

棒棒糖空间

空间的前半部分是线性的，后半部分是循环的。

自适应算法

集中式路由

所有路由器都连接到一个称为 **路由控制中心** (RCC) 的集中式控制核心：每个路由器都告诉 RCC 它的邻居是谁，RCC 使用这些信息来创建网络地图，计算路由表并将其传达给所有路由器。

优点

性能：路由器不需要具有很高的计算能力，所有计算都集中在一个设备上；
调试：网络管理员可以从单个设备获取整个网络的地图，以检查其正确性；
维护：智能集中在控制中心 → 更新算法只需更新控制中心即可。

缺点

容错性：控制中心是单点故障 → 控制中心的故障会影响整个网络；
可扩展性：网络包含的路由器越多，控制中心的负担就越重 → 它不适合互联网等广域网络。

应用

电话网络中使用类似的原理。

隔离路由

没有控制中心，但所有节点都是对等的：每个节点自主地决定其路径，无需与其他路由器交换信息。

优点和缺点

它们实际上是集中式路由的相反。

反向学习

每个节点根据数据包源地址学习网络信息：本地网络设计/A3. 中继器和网桥#透明网桥。

它仅在“健谈”的节点上运行良好；
当最佳路径不再可用时，很难实现切换到备用路径的需要；
很难检测到目标变得无法访问 → 需要一个特殊的计时器来删除旧条目。

分布式路由

分布式路由使用“对等”模型：它利用了集中式路由和隔离路由的优势

集中式路由：路由器参与有关连接性的信息交换；
隔离路由：路由器是等效的，不存在“更好”的路由器。

应用

现代路由协议使用两种主要的分布式路由算法

距离矢量：每个节点都告诉它所有邻居关于网络的知识；
链路状态：每个节点都告诉整个网络关于其邻居的知识。

比较

邻居

LS：需要“hello”协议；
DV：通过 DV 本身了解它的邻居。

路由表

DV 和 LS 创建相同的路由表，只是以不同的方式计算，并且具有不同的瞬态持续时间（和行为）

LS：路由器协作以保持网络地图最新，然后每个路由器计算自己的生成树：每个路由器都知道网络的拓扑结构，并且知道到达目标的精确路径；
DV：路由器协作以计算路由表：每个路由器只知道它的邻居，并且信任它们来确定到达目标的路径。

简单性

DV：易于实现的单个算法；
LS：包含许多不同的组件。

调试

LS 中更好：每个节点都有网络地图。

内存消耗 (在每个节点中)

它们可以被认为是等效的

LS：每个 $N$ LS 有 $A$ 个邻接关系 (Dijkstra： $\sim N\cdot A$ )；
DV：每个 $A$ 个 DV 有 $N$ 个目标 (Bellman-Ford： $\sim A\cdot N$ )。

流量

LS 中更好：邻居问候包比 DV 小得多。

收敛

LS 中更好：故障检测更快，因为它基于以高频率发送的邻居问候包。

转发和路由	路由协议和架构	距离向量算法
	路由算法