科大计网之：网络层——控制平面
Weiquan Huangchp5-1 导论
路由的概念：按照某种指标找到一条从源节点到目标节点的较好路径
chp5-2 路由选择算法
路由算法可以分为
- 全局算法：所有路由器拥有完整的拓扑和边的代价的信息（link state）
- 分布式算法：路由器只知道与它有物理连接关系的邻居路由器以及到相应路由器的代价值（distance vector）
链路状态路由选择
- 发现相邻节点，获知对方网络地址
- 测量到相邻节点的代价
- 组装一个分组，描述相邻节点的情况
- 将分组通过扩散的方法发到所有其他路由器
- 无穷环状扩散：可用顺序号、TTL等解决
- Dijkstra’s Algorithm计算某个节点到其他节点的最短路径
距离矢量路由选择
- 每个节点记录其到达其他节点的代价，而与邻居的实时代价可以直接测出
- 从一个基础节点开始，该节点和其他节点互相交换矢量路由（也就是从本节点到某节点的代价）表，根据自身与邻居的实时距离来更新自身到其他节点的代价
- 广泛传播之后可以迭代式地更新路由表
- 通常是在自身检测到与邻居的代价有变化，或者别的路由传过来其矢量路由的变化，这样会导致路由器的路由表的变化
Bellman-Ford方程：$$d_x(y)=min_v{c(x,v),d_v(y)}$$表示如何更新节点路由的方程，不断更新以维持实时性
“好消息传得快、坏消息传的慢”问题：
- 如果某个路由器接入或者有更短的路径，那么由于更短路径一定会被更新，而其也会在必要的时候更新到受该路径影响的其他路由信息，传播速度快而且传播具有必要性
- 如果某个路径断开，那么坏消息可能会循环，比如a-b断开，而b向c寻找a的路径的时候，c又会将方向导向b（假设之前是c-b-a），那么如此无限循环，直到到达了无限循环的界限后返回不可达的信息
- 解决方法是水平分裂算法：在上面的例子中，c向b报告到a的距离为INF，向其他路由先报告为之前值；从而b-a路径在b上的信息可以及时更新，更新后提供给c以让c更新，同时d做如c的操作（也有可能是d有其他通向a的路径，则更换至另一条路径）
chp5-3 因特网中自治系统内部的路由选择
在一个自治系统(AS)内部进行路由选择，RIP是DV算法的协议，OSPF是LS算法的协议，本质上就是在自治系统内使用DV和LS算法来路由内部的主机，这样子可以避免由于算法作用范围过大导致的计算负担；AS与AS之间自有其他路由器作为沟通的桥梁
chp5-4 ISP之间的路由选择（未完待续）
