控制平面核心：路由算法与 OSPF 协议

5.1 概述核心定位本章聚焦网络层的控制平面是网络层两大核心平面数据平面 控制平面的关键组成部分。数据平面负责路由器中转发IP 数据报是 “执行层”由路由器硬件 / 固件实现处理每一个到达的分组。控制平面负责路由选择是 “决策层”由路由器软件实现决定数据报的转发路径生成并维护路由表供数据平面使用。控制平面的两大核心架构传统分布式路由架构每台路由器独立运行路由选择算法通过和相邻路由器交换路由信息自主计算到所有目的网络的最优路径生成本地路由表。代表协议内部网关协议 OSPF本章 5.3、外部网关协议 BGP后续章节。特点分布式、去中心化每台路由器自主决策是互联网传统路由的核心架构。软件定义网络SDN架构路由计算由集中式 SDN 控制器完成控制器统一计算全网最优路径将流表下发给所有路由器路由器仅执行转发不参与路由计算。特点集中式、可编程适合数据中心、云网络等新型网络场景是网络架构的演进方向。本章前 3 节的核心脉络5.1 搭建控制平面的整体框架 →5.2 讲解路由选择的通用算法链路状态、距离向量不依赖具体协议 → 5.3落地到互联网实际使用的OSPF 协议链路状态算法在自治系统内的工程实现。5.2 路由选择算法路由选择算法的核心目标在网络拓扑中计算从源节点到目的节点的最优路径最优通常指 “最小代价”代价可以是跳数、链路带宽、时延、费用等。路由算法的分类分类维度类型核心特点网络范围域内路由IGP自治系统AS内部使用如 OSPF、RIP域间路由EGP自治系统之间使用如 BGP决策方式链路状态LS全网拓扑透明每台路由器拥有完整拓扑图独立计算最短路径距离向量DV邻居间迭代交换距离向量逐步收敛到最优路径服务类型单播路由点到点通信本章核心组播路由点到多点通信后续章节5.2.1 链路状态路由选择算法Link-State, LS核心原理每台路由器获取全网完整的拓扑图所有链路的状态、代价然后用 Dijkstra 最短路径算法独立计算到所有目的节点的最短路径。算法执行步骤以路由器 u 为例发现邻居初始化链路状态路由器 u 向所有直连邻居发送 Hello 报文发现邻居节点记录直连链路的代价如带宽、时延。泛洪Flooding链路状态分组LSP路由器 u 生成包含自身 ID、直连邻居、链路代价的 LSP通过泛洪发送给全网所有路由器每台路由器收到 LSP 后转发给除入接口外的所有邻居确保全网同步。构建全网拓扑图所有路由器收到所有 LSP 后在本地构建完全一致的全网拓扑图无向带权图节点是路由器边是链路权值是链路代价。运行 Dijkstra 算法计算最短路径以自身为根节点运行 Dijkstra 算法计算到所有目的节点的最短路径生成路由表。Dijkstra 算法核心逻辑以 u 为源节点初始化N已确定最短路径的节点集合初始仅包含uD(v)到节点 v 的当前最短路径代价初始D(u)0直连邻居D(v)c(u,v)其余节点D(v)∞p(v)v 的前驱节点用于回溯路径迭代从N外的节点中选择D(w)最小的节点w加入N对w的所有邻居v更新D(v) min(D(v), D(w)c(w,v))若更新则记录p(v)w重复直到所有节点加入N最终D(v)就是 u 到 v 的最短路径代价p(v)回溯得到完整路径。链路状态算法的优缺点✅优点路由收敛快拓扑变化时泛洪 LSP 后全网同步更新无计数到无穷问题路由无环路基于全网拓扑计算最短路径天然无环支持大规模网络适合自治系统内部的大规模路由如 OSPF❌缺点泛洪开销大LSP 泛洪会占用网络带宽尤其在大型网络中存储与计算开销高每台路由器需要存储全网拓扑运行 Dijkstra 算法对路由器性能要求高5.2.2 距离向量路由选择算法Distance-Vector, DV核心原理每台路由器仅和直连邻居交换 “距离向量”到所有目的网络的最小代价 下一跳通过迭代更新逐步收敛到最优路径是 Bellman-Ford 算法的分布式实现。算法核心公式Bellman-Ford 方程对于路由器x到目的网络y的最小代价D_x(y)满足Dx​(y)minv∈N(x)​{c(x,v)Dv​(y)}其中N(x)x 的直连邻居集合c(x,v)x 到邻居 v 的链路代价D_v(y)邻居 v 到 y 的最小代价邻居向 x 通告的距离向量算法执行步骤以路由器 x 为例初始化路由表初始时x 仅知道直连链路的代价到直连邻居 v 的代价为c(x,v)到非直连节点的代价为∞。周期性向邻居通告距离向量x 周期性如 RIP 的 30 秒向所有直连邻居发送自己的距离向量[D_x(y_1), D_x(y_2), ...]即到所有目的网络的最小代价。根据邻居通告更新路由表x 收到邻居 v 的距离向量后用 Bellman-Ford 方程更新自己的D_x(y)若c(x,v) D_v(y) 当前D_x(y)更新D_x(y)并将下一跳设为 v若邻居 v 不再可达将所有以 v 为下一跳的路由代价设为∞触发更新迭代收敛重复步骤 2-3直到所有路由器的距离向量不再变化算法收敛路由表稳定。距离向量算法的关键问题与解决方案计数到无穷Count to Infinity问题当链路故障时坏消息传播慢路由器之间会互相 “误导”导致路由代价无限增大无法收敛。场景A-B-CA 到 C 的代价为 2A→B→C若 B-C 链路断开B 会向 A 通告 “到 C 的代价为∞”但 A 会向 B 通告 “到 C 的代价为 3A→B→C”B 误以为 A 有路径更新为 4A 再更新为 5无限循环。解决方案定义最大有效代价如 RIP 定义最大跳数为 1516 代表不可达超过 15 跳直接标记为不可达终止计数。毒性逆转Poison Reverse路由器向邻居通告路由时若下一跳是该邻居则通告代价为无穷大避免邻居从该路由器学习路由解决两个节点的计数到无穷问题。水平分割Split Horizon路由器不从收到路由的接口再发回该路由从根源避免邻居间的路由循环。触发更新Triggered Update拓扑变化时立即发送更新报文而不是等待周期加快坏消息传播。距离向量算法的优缺点✅优点实现简单仅和邻居交换信息无需泛洪全网存储与计算开销低适合小型网络如早期局域网、小型自治系统如 RIP 协议❌缺点收敛慢拓扑变化时坏消息传播慢存在计数到无穷问题路由环路风险迭代过程中可能出现临时环路不适合大规模网络周期更新会占用大量带宽收敛时间随网络规模增大而变长5.3 因特网中自治系统内部的路由选择OSPFOSPFOpen Shortest Path First开放最短路径优先是互联网标准的内部网关协议IGP用于自治系统AS内部的路由选择是链路状态路由算法的工程实现替代了早期的 RIP 协议。核心特点基于链路状态算法每台 OSPF 路由器泛洪 LSA链路状态通告构建全网拓扑运行 Dijkstra 算法计算最短路径天然无环、收敛快。开放标准IETF 定义的开放协议所有厂商设备均可实现无专利限制。支持层次化路由区域划分将自治系统划分为多个区域Area解决大规模网络的泛洪开销问题。支持多种链路代价可基于带宽、时延、费用等自定义链路代价默认以带宽为参考代价 10^8 / 带宽单位 bps。安全机制支持报文认证明文 / MD5/SHA防止非法路由器注入虚假路由。支持等价路由可同时计算多条代价相同的最短路径实现负载均衡。支持 IP 多播OSPF 报文使用 IP 多播地址224.0.0.5/224.0.0.6发送减少网络带宽占用。OSPF 的核心组件与工作流程1. 自治系统与区域划分Hierarchical OSPF为解决大型 AS 的泛洪开销问题OSPF 将 AS 划分为区域Area核心结构骨干区域Area 0必须存在ID 为 0.0.0.0所有非骨干区域必须直接连接到骨干区域负责区域间路由的分发。非骨干区域如 Area 1、Area 2 等仅在区域内泛洪 LSA区域间路由通过骨干区域传递。路由器角色区域内路由器Internal Router所有接口都在同一个区域内仅维护本区域的拓扑。区域边界路由器ABR同时连接骨干区域和非骨干区域负责将非骨干区域的路由汇总后发布到骨干区域再由骨干区域分发到其他区域。骨干路由器Backbone Router至少有一个接口在骨干区域包括 ABR 和骨干区域内的内部路由器。自治系统边界路由器ASBR连接 OSPF AS 和其他 AS如 BGP 网络负责将外部路由引入 OSPF 网络。2. OSPF 报文类型OSPF 直接封装在 IP 报文中协议号 89共 5 种报文报文类型名称核心作用1Hello 报文发现 / 维护邻居关系周期性发送默认 10 秒确认邻居可达2数据库描述报文DBD交换链路状态数据库LSDB的摘要用于邻居间同步 LSDB3链路状态请求报文LSR请求缺失的 LSA用于同步 LSDB4链路状态更新报文LSU发送完整的 LSA泛洪拓扑信息5链路状态确认报文LSAck确认 LSU 报文确保泛洪可靠3. OSPF 工作流程邻居发现与邻接建立路由器发送 Hello 报文发现直连邻居协商参数区域 ID、认证信息、Hello/Dead 间隔等参数一致则建立邻居关系。对于广播网络如以太网选举指定路由器DR和备份指定路由器BDR所有非 DR/BDR 路由器仅和 DR/BDR 建立邻接关系减少邻接数量降低泛洪开销。链路状态数据库LSDB同步邻居间交换 DBD 报文对比 LSDB 摘要若有缺失 LSA发送 LSR 请求对方回复 LSU发送 LSAck 确认最终所有同区域路由器的 LSDB 完全一致。泛洪 LSA维护拓扑拓扑变化时路由器生成 LSA通过 LSU 报文泛洪到全网所有路由器更新 LSDB重新运行 Dijkstra 算法计算最短路径。周期性泛洪默认 30 分钟确保 LSDB 一致性。计算最短路径生成路由表每台路由器以自身为根运行 Dijkstra 算法计算到所有目的网络的最短路径生成 OSPF 路由表供数据平面转发使用。4. OSPF 的链路代价与路由类型链路代价默认cost 10^8 / 带宽(bps)如 100M 链路代价为 11G 链路代价为 110G 链路代价为 1可手动配置。路由类型优先级从高到低区域内路由Intra-area本区域内的路由优先级最高区域间路由Inter-area通过 ABR 学习的其他区域的路由类型 1 外部路由E1外部路由代价 外部代价 内部到 ASBR 的代价类型 2 外部路由E2仅使用外部代价默认类型优先级最低OSPF vs RIP距离向量协议特性OSPF链路状态RIP距离向量算法基础链路状态 Dijkstra距离向量 Bellman-Ford收敛速度快拓扑变化立即泛洪慢周期更新存在计数到无穷网络规模适合大型 AS无跳数限制适合小型网络最大跳数 15泛洪开销区域划分后开销可控周期更新大型网络带宽占用高路由环路天然无环存在临时环路风险认证机制支持不支持RIPv2 支持等价路由支持支持报文封装IP 协议号 89UDP 520 端口核心知识点总结控制平面 vs 数据平面控制平面负责路由决策数据平面负责分组转发是网络层的两大核心。两大路由算法链路状态LS全网拓扑透明Dijkstra 计算收敛快、无环适合大型网络OSPF。距离向量DV邻居迭代更新Bellman-Ford 实现实现简单适合小型网络RIP需解决计数到无穷问题。OSPF 核心链路状态算法的工程实现支持层次化区域划分是互联网主流的内部网关协议解决了 RIP 的规模限制和收敛问题。