# 链路状态（LS）和距离向量（DV）算法介绍
# 1. 链路状态算法（Link State, LS）
工作原理：
全局视图：每个路由器都会维护整个网络的拓扑结构，收集关于整个网络的链路状态信息。
链路状态广播：路由器向网络中的所有其他路由器发送链路状态包（LSA），每个路由器都会广播自己与邻居的连接情况，并包括这些连接的代价。
拓扑图更新：所有路由器根据接收到的链路状态信息构建整个网络的拓扑图。
Dijkstra 算法：一旦所有路由器获得了网络的拓扑图，它们会使用 Dijkstra 算法来计算从自己到每个目的地的最短路径。
优点：
快速收敛：LS 算法基于整个网络的拓扑信息进行计算，能够迅速做出决策。
路径选择精准：由于路由器了解整个网络的状态，它能够选择最佳路径，包括负载均衡等高级策略。
缺点：
计算复杂度高：LS 算法的时间复杂度为 O (n^2) 或 O (n log n)，对于大型网络来说，计算和存储的开销较大。
消息传递量大：路由器需要定期向整个网络广播链路状态更新，因此在大规模网络中会产生较多的控制流量。
# 2. 距离向量算法（Distance Vector, DV）
工作原理：
局部视图：每个路由器只与邻居路由器交换路由信息，并且每个路由器只知道自己到邻居的距离。
迭代更新：每个路由器通过与邻居交换 “距离向量”（表示到每个目的地的距离）来逐步构建自己的路由表。路由器根据邻居的信息逐步更新自己的最优路径。
贝尔曼 - 福特算法：DV 算法依赖贝尔曼 - 福特算法进行路径选择，它通过多次迭代更新到各个目的地的最短距离。
优点：
简单：DV 算法实现相对简单，路由器只需要与邻居交换信息，不需要维护整个网络的拓扑图。
计算开销小：由于只与邻居交换信息，计算和消息传递的开销较低。
缺点：
收敛较慢：由于信息传播速度较慢，尤其在大网络中，收敛时间可能较长。出现网络故障时，DV 算法需要较长时间才能收敛到新的状态。
计数到无穷大问题：当网络中出现环路时，DV 算法可能陷入 “计数到无穷大” 的问题，即路由器不断增大其距离估计值，直到达到上限（通常为 16 跳）。
# 3. LS 和 DV 的比较
消息复杂度：LS 的消息复杂度为 O (nE)（n 为节点数，E 为边数），DV 的消息复杂度较低，因为它只在邻居之间交换消息。
收敛速度：LS 算法收敛快，DV 算法由于逐步迭代，收敛时间可能较长。
应用场景：LS 算法适用于需要高精度、高可靠性的网络（如 OSPF 协议），DV 算法则适用于较小、简单的网络（如 RIP 协议）。
总结来说，LS 算法适合对全网有更高掌控需求的大型网络，DV 算法则更适合小型或中型网络中简单的路径选择需求。
# 分层路由 (Hierarchical routing)
# 介绍
网络规模与分层的必要性：
- 互联网包含数亿个目的地，无法在每个路由器中存储所有目的地的路由信息。同时，路由信息的交换会消耗大量带宽。为了解决这些问题，互联网采用了分层路由的结构，将网络划分为若干自治系统（AS），以便集中管理。
自治系统（AS）的作用：
- 每个自治系统由单一的管理机构控制，可以自主选择使用的路由协议和策略。每个 AS 内部使用一种 “域内路由协议”（如 OSPF、RIP），而跨越不同 AS 的通信则依赖 “域间路由协议”（如 BGP）。
- 在 AS 的边界上使用 “网关路由器”（Gateway Router）负责连接不同的 AS，使数据在不同 AS 之间转发。
域内与域间路由的协作：
- ** 域内路由协议（Intra-AS Routing Protocol）** 负责计算 AS 内部的路径。通过这些协议，每个 AS 可以独立确定到本 AS 内所有目的地的最佳路由。
- ** 域间路由协议（Inter-AS Routing Protocol）** 负责跨 AS 的路由选择。每个 AS 与其邻居 AS 共享可达性信息，选择最合适的跨域路径。比如，AS1 的一个路由器在收到目标在其他 AS 的消息时，首先会选择最合适的网关将数据包转发至下一个 AS。
分层路由的优势：
- 减少复杂度：路由信息被划分到不同层级，每个 AS 仅需管理内部的路由，大大减少了每个路由器的负担。
- 管理自主性：每个 AS 可自主设置策略，比如可以决定是否承载特定类型的流量。
- 可扩展性强：分层结构支持互联网的扩展，不会因网络规模的增加导致路由器超负荷。
通过这种分层路由方式，互联网能够更有效地管理和转发数据，确保在全球范围内实现快速且高效的通信。
# Hot Potato Routing
Hot Potato Routing（烫手山芋路由）是一种在网络中进行数据包转发的路由策略，旨在将数据包快速传递给下一个网络节点，以尽快将数据包 “推” 出当前网络。这种策略通常在没有明确最优路径选择，或路径延迟相近的情况下使用，常见于自治系统（AS）之间的数据包转发中。
Hot Potato Routing 的核心思想是尽快将数据包交给下一个路由器或自治系统，而不是试图找到某条具体的最短路径。换句话说，路由器会选择离自己最近的出口转发数据包，而不一定是整体路径上最优的出口。这种方式可以减少数据包在本地网络中的延迟和资源占用。
# 1. 实现流程
- 邻居成本计算：当数据包需要从源 AS 传递到目的 AS 时，源 AS 中的路由器首先会计算到达其所有出口网关的路径成本（例如延迟或跳数）。
- 选择最接近的网关：路由器选择成本最低的出口网关，将数据包转发给离它最近的网关，而不再考虑数据包后续的详细路径。
- 数据包交接：一旦数据包被转发到出口网关，它便会离开源 AS，进入下一个 AS 或网络。
# 2. 优缺点
优点：
- 降低网络资源占用：数据包尽快离开当前网络，减少了在本地网络中占用的带宽和计算资源。
- 减少转发延迟：选择最近的出口可以减少在本地 AS 内的传输延迟，从而加快数据包的传输速度。
- 简单易实现：不需要维护复杂的全局路由信息，适合大型分布式网络。
缺点：
- 路径非最优：数据包并未按照全局最短路径转发，可能会绕路，增加传输时间。
- 跨 AS 的成本可能更高：数据包可能会被交给距离最近但非最优的 AS 网关，导致数据包在其他 AS 中的传输成本增加。
- 依赖邻居策略：邻近 AS 的转发策略可能与源 AS 不同，增加了路由的不确定性。
# 3. 应用场景
Hot Potato Routing 适用于大型分布式网络和多 AS 互连的网络，如 ISP（Internet Service Provider）间的路由选择。因为不同 ISP 之间可能没有直接的链路质量信息或最优路径协议，它们倾向于使用 Hot Potato Routing 将数据包尽快转发给下一个网络。这种策略也用于减少自己的网络资源消耗，把负担转移给邻居 ISP。
# Routing in the Internet
RIP（Routing Information Protocol）：
- 特点：RIP 是一种基于距离向量（Distance Vector）的路由协议，使用跳数（hop count）作为距离度量，每个链路的跳数成本为 1，最大跳数为 15。超过 15 跳表示目的地不可达。
- 信息更新：RIP 每 30 秒向邻居发送一次距离向量表（称为广告消息），广告消息包含最多 25 个目标子网的跳数信息，更新邻居的路由信息。
- 应用场景：适用于小型网络，由于其最大跳数限制，不适合大规模的互联网环境。
OSPF（Open Shortest Path First）：
- 特点：OSPF 是一种链路状态（Link State）路由协议，每个路由器都通过链路状态广告（LSA）了解网络拓扑，使用 Dijkstra 算法计算最短路径。OSPF 是开源协议，允许在整个自治系统（AS）中进行拓扑广播。
- 高级功能：OSPF 支持路径认证（保证安全性）、相同成本路径（允许多路径负载均衡）、多种服务类型的链路成本以及单播和多播的集成。它还支持分层 OSPF（Hierarchical OSPF）用于大型域中的分区管理。
- 应用场景：适合大型企业网络和数据中心，因其精确的路径计算和灵活的策略选择受到青睐。
BGP（Border Gateway Protocol）：
- 特点：BGP 是事实上的互联网域间（Inter-domain）路由协议，通过边界网关（Border Gateway）连接不同的 AS。BGP 分为外部 BGP（eBGP）和内部 BGP（iBGP），分别用于 AS 之间和 AS 内部的路由信息传播。
- 路由策略：BGP 路由基于策略而非纯粹的最短路径。例如，一个 AS 可以选择不传递商业流量或避免特定路径。BGP 的主要属性包括 AS 路径（AS-PATH）和下一跳（NEXT-HOP），允许路由器基于策略接受或拒绝路径。
- 应用场景：适用于全球互联网，BGP 被称为 “互联网的粘合剂”，通过政策控制和子网可达性信息的传播，使得各 AS 能够互通数据并实现复杂的跨域通信。
# 总结
- RIP 适用于小型网络，简单但跳数有限。
- OSPF 适合自治系统内部，精确高效，支持高级功能。
- BGP 是跨 AS 的核心协议，基于策略路由，适合全球互联网。
# BGP
BGP（Border Gateway Protocol） 被介绍为互联网的主要域间路由协议，常用于自治系统（AS）之间的通信，确保不同网络能够互通。BGP 被称为 “互联网的粘合剂”，其主要特点和运作机制如下：
BGP 的基本功能：
- BGP 为每个 AS 提供了一种交换可达性信息的机制。通过外部 BGP（eBGP），一个 AS 能够从邻居 AS 接收子网的可达性信息；通过内部 BGP（iBGP），该 AS 内部的所有路由器可以共享这些信息。
- 通过这种方式，BGP 可以将互联网中各个网络连接起来，使得一个 AS 能够将其存在公告给其他 AS（例如：“我在这里”），并为其路由器提供通往其他网络的路径。
路径属性与路由选择：
- 每个 BGP 路径包含多个属性，包括 AS 路径（AS-PATH）和下一跳（NEXT-HOP）。AS-PATH 记录了通过的 AS 列表，路由器根据 AS-PATH 来选择更短的路径。
- NEXT-HOP 指明数据包的下一个目的 AS 的具体路由器，接收路由通告的网关路由器可以使用 “导入策略” 选择是否接受该路径，比如拒绝经过某个特定 AS 的路径。
策略驱动的路由：
- 与域内协议（如 OSPF）追求最短路径不同，BGP 关注的是策略。例如，一个教育机构的网络可以选择不传递商业流量，而一个企业可以选择从成本更低的 ISP 接收流量。
- BGP 的策略可以非常细化，支持复杂的商业和政治考量，例如限制某些流量经过竞争对手的网络。
路由选择的顺序：
- BGP 在选择路由时按照以下优先级：本地优先级 / 策略 > 最短 AS-PATH > 最近的 NEXT-HOP（即 “烫手山芋路由”）。
- 当出现多个同等优质的路径时，BGP 将选择最近的网关将数据包快速推出本 AS，从而减少自身网络的负担。
应用场景：
- BGP 广泛应用于 ISP 之间的网络连接和大型企业的跨地域网络。由于 BGP 允许基于策略的路由选择，它成为全球互联网通信的关键协议之一。
BGP 的策略导向特性使其能够有效地连接全球的自治系统，适应多变的互联网需求。
