1 路由选择算法

路由：按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径
以网络为单位进行路由（路由信息通告+路由计算）
- 一个网络使用的节点地址前缀相同，且物理上聚集
- 路由：计算一个网络到另一个网络的路径
路由选择算法（routing algorithm）：网络层软件的一部分，完成路由功能
- 从图中找到一棵汇集树（Sink Tree）
  - 此节点到其他节点的最优路径形成的树
  - 路由选择算法就是为所有路由器找到并使用汇集树

1.1 Link State

配置LS路由选择算法
- 通过各种渠道获得整个网络的拓扑，整个网络链路代价等信息
- 使用LS路由算法计算本站点到其他站点的最优路径（汇集树），得到路由表
- 按照路由表转发分组（datagram方式）
LS路由选择算法工作流程
1. 发现相邻节点，获取对方网络地址
2. 测量到相邻节点的代价（延迟、开销）
3. 组装一个LS分组，描述它到相邻节点的代价情况
4. 将分组通过扩散的方式发送到所有其他路由器
5. 通过Dijkstra算法找出最短路径
  - 每个节点独立计算到其他节点的最短路径
  - 迭代算法：第K步知道本届点到K个其他节点的最短路径
符号标记
- c(i,j)：从节点i到节点j的链路代价（初始状态下非相邻节点之间代价为∞）
- D(v)：从源节点到目标节点的当前路径代价（节点的代价）
- P(v)：从源到节点V的路径前序节点（P(P(v))则表示的是前序的前序节点）
- N'：当前已知最优路径的节点集合（永久节点集合）临时节点：没找到最优路径；永久节点：找到最优路径

Dijkstra算法讨论（n个节点）
- 每次迭代需要检查所有不在永久集合N中的节点
- n(n+1)/2 O(n²) 复杂度（有更好的logn的实现）
- 可能会存在震荡，每次计算出来的不一样，大家都去挤新的路径

　　XYZ分别记录了自己到B的代价，然后告诉给A；A测量自己到XYZ的代价，最后判断到B应该走哪个节点。每个路由器仅维护了自己的终点和下一跳分别是哪个路由器，这个算法原理很简单

　　路由信息协议（Routing Information Protocol，RIP），该协议是基于距离矢量算法的路由协议。最大支持15跳的长度，DV每隔30秒与相邻路由器交换信息，每个通告最多包括25个目标子网。如果180秒（6个周期）没有收到下一个路由器的路由通告，认为该邻居已失效。

　　RIP通过进程的方式实现，并且使用UDP报文传送数据，网络层的协议实际上使用传输层的服务来实现了网络层。

　　开放式最短路径优先（Open Shortest Path First，OSPF），该协议是基于链路状态算法的路由协议。OSPF通告信息中携带每个邻居路由器的一个表象，通过泛洪在IP数据报上直接传送OSPF报文（不通过UDP或TCP）。

　　所有OSPF报文都经过认证（安全性高级特性），允许多个代价相同的路径存在，允许多种代价指标来计算路径，并且允许使用层次化的OSPF路由（本地和骨干2个层级，区域边界路由去、骨干路由器、边界路由器）

一个平面的路由
- 一个网络中所有路由器的地位相同
- 通过LS、DV计算所有路由器（子网）之间路径如何走
- 所有路由器在同一个平面
平面路由的问题
- 规模巨大的网络中，路由信息的存储、传输和计算代价巨大
- 管理问题，不同的网络希望按照自己的方式管理网络，隐藏自己网络的细节，同时与其他网络互联
使用层次路由解决该问题
- 将互联网分成一个个区域路由器，每个区域内部自治
- 互联网AS间路由：BGP（Border Gateway Protocol）自治区间路由协议