路由算法与路由协议¶
路由算法¶
静态路由与动态路由¶
-
静态路由：人工配置，路由固定不随拓扑自动变化
-
优点：简单、可控、无协议开销
-
缺点：不适应故障/扩容；维护成本高
-
-
动态路由：路由器运行路由协议，自动学习与更新路由
-
优点：适应性强，可自动收敛
-
代价：协议开销、实现复杂、可能出现环路/震荡（需机制保证）
-
距离-向量路由算法¶
核心思想（DV）¶
每个路由器维护“到各目的网络的距离 + 下一跳”，并把自己的向量周期性发给邻居；通过迭代达到稳定（Bellman-Ford 思想）。
用一句话记：只和邻居交换“我到哪儿多远”，不知道全网拓扑。
更新规则（做题口述版）¶
若路由器 \(x\) 从邻居 \(v\) 收到 \(v\) 到目的 \(y\) 的距离 \(d_v(y)\)，且链路代价为 \(c(x,v)\)，则：
典型问题：坏消息传播慢（计数到无穷）¶
-
某条路径失效后，邻居间会相互“误以为对方还有路”，距离逐步增大
-
表现为：路由环路、收敛慢
常见改进思想（知道名字即可）：
-
水平分割
-
毒性逆转
-
触发更新
链路状态路由算法¶
核心思想（LS）¶
每个路由器通过泛洪获得全网链路状态（形成 LSDB），在本地对拓扑跑最短路（Dijkstra），得到到各目的的下一跳。
Tip
拿到“全网地图”自己算最短路。
典型特性（对比 DV）¶
-
收敛快、不易“坏消息传播慢”
-
代价是：维护 LSDB 与泛洪开销更大、实现更复杂
层次路由¶
内部网关协议¶
IGP（域内路由）核心点¶
-
作用范围：一个自治系统（AS）内部
-
典型协议：RIP、OSPF
-
目标倾向：更关注“度量最优”（跳数/代价）与快速收敛
外部网关协议¶
EGP（域间路由）核心点¶
-
作用范围：自治系统之间
-
典型协议：BGP
-
目标倾向：策略优先（商业关系/策略约束），不保证选最短物理路径
路由信息协议¶
RIP的规定¶
-
采用 距离-向量思想
-
度量：跳数（hop count）
- 最大 15 跳（16 表示不可达）
RIP的特点¶
-
周期性更新（也可触发更新）
-
适用于规模较小、拓扑相对简单的网络
-
缺点：收敛慢、易形成环路（与 DV 的典型问题一致）
RIP的距离向量算法¶
RIP 的“做题抓手”：
-
每次更新把“距离”加 1（相当于每经过一个路由器 +1 跳）
-
选择跳数最少的路径
-
由于上限 15 跳，因此不适合大规模网络
RIP的优缺点¶
-
优点：简单、开销小、易部署
-
缺点：
-
最大跳数限制导致可扩展性差
-
坏消息传播慢，可能计数到无穷
-
开放最短路径优先¶
OSPF的基本特点¶
-
基于 链路状态（LS）
-
使用“代价 cost”（常与带宽相关），不受 15 跳限制
-
收敛快：链路状态变化触发泛洪与重计算
-
支持分层区域（Area）思想提升扩展性（理解即可）
OSPF的基本工作原理¶
最常考的“过程主线”（能口述就够）：
-
相邻路由器发现并建立邻接关系
-
交换链路状态信息，形成一致的 LSDB
-
各自本地运行 Dijkstra，生成最短路径树（SPT）
-
由 SPT 得到路由表/转发表
OSPF的分组类型¶
知道“有多种类型用于建立邻接与同步 LSDB”即可；408 更常考“OSPF 是 LS + 收敛快 + 代价度量”这一组特征。
边界网关协议¶
BGP的基本特点¶
-
域间路由协议（AS 之间）
-
策略路由：不追求纯最短路，而追求“满足策略约束的可达”
-
携带 AS-PATH 等路径属性，能用于域间环路检测（理解点）
BGP的路由¶
eBGP vs iBGP¶
-
eBGP：不同 AS 之间交换路由
-
iBGP：同一 AS 内传播从外部学到的路由（使 AS 内部一致）
BGP的路由选择¶
408 常见考法：给出多条路由属性，问选哪条。
这里给一个“够应付做题的记忆顺序”（不同教材/实现细节略有差异，考试更重理解）：
-
先看是否符合策略（本地优先级等）
-
再看 AS-PATH 更短（常见倾向）
-
再看其他属性（如 MED、下一跳可达等，了解即可）
BGP的四种报文¶
-
OPEN：建立邻居关系
-
UPDATE：发布/撤销路由
-
KEEPALIVE：保持会话
-
NOTIFICATION：差错与关闭
408 高频易错点清单¶
-
RIP 的度量是 跳数（不是带宽）
-
OSPF 属于 链路状态，特点是“泛洪 + 全网拓扑 + Dijkstra”
-
BGP 的核心是 策略，不是“域间最短路”