【路由算法】
概述
路由器转发分组是通过路由表转发的，而路由表是通过各类算法得到的，根据能否随网络通信量或拓扑自适应进行调整，路由算法可分为静态路由算法、动态路由算法两类
静态路由算法，又称非自适应路由算法，是指由网络管理员手工配置路由信息，一旦当网络拓扑结构或链路状态发生变化，网络管理员需要手工去修改路由表中相关的静态路由信息，适用于小型网络
动态路由算法，又称自适应路由算法，是指路由表上的路由表项通过相互连接的路由器不断交换信息，然后通过一定算法优化出来的，常见的动态路由算法分为距离向量路由算法、链路状态路由算法两类
距离-向量路由算法
在距离-向量路由算法中，所有的结点都在每次更新中都将他们的全部路由表传送给所有与其直接相邻的结点，这种路由表每行只有两个项目：
- 另一结点 IP 地址：每条路径的目的地
- 到另一结点的距离：路径的代价
在这种算法中，所有结点都必须参与距离向量交换，以保证路由的有效性和一致性，也就是说，所有的结点都监听从其他结点传送过来的路由选择更新信息，并在下列情况下更新他们的路由选择表：
- 被通告一条新的路由，该路由在本结点的路由表中不存在，此时本地系统加入该条新路由信息
- 发送来的路由信息中有一条到达某结点的路由，且该路由比当前使用的路由有较小的代价，此时用较小代价的路由代替当前使用的路由
该算法的实质是迭代计算一条路由中的站点数或延迟时间，从而得到到达一个目标的最小代价通路
在 RIP 协议中，进行路由更新的 RIP 算法就是距离-向量算法，其采用跳数作为距离的度量
链路状态路由算法
链路状态路由算法，要求每个参与该算法的结点都掌握完整网络拓扑信息，同时，每个结点会执行以下两个任务：
- 主动测试所有邻接结点的状态，即测试两个共享一条链接的结点
- 定期将链路状态传播给所有其他结点
也就是说，在链路状态路由算法中，每个结点都会检查所有直连链路的状态，并将所得的状态信息发送给网络上其他的结点，同时，每个结点都会从其他结点接收包含直接链路状态的路由选择信息
每当链路状态报文到达时，路由结点便利用这些状态信息去更新自己的网络拓扑和状态，一旦链路状态发生变化，结点对更新了的网络图利用 Dijkstra 算法来重新计算路径，从单一的源点出发，计算到达所有目的结点的最短路径
简单来说，链路状态路由算法，就是只有当链路状态发生变化时，路由器才会向本自治系统内的其他所有路由器采用泛洪法发送信息，发送的信息就是与路由器相邻的所有路由器的链路状态，即说明路由器都与哪些路由器相邻，以及该链路的度量
在 OSPF 协议中，进行路由更新的 OSPF 算法就是链路状态路由算法
所谓泛洪法，就是路由器通过所有端口向所有相邻的路由器发送信息，每一个相邻路由器又将该信息发往除了刚刚发来信息的那个路由器外的，其他的所有相邻的路由器
【路由选择协议】
自治系统
而当网络规模扩大时，路由器的路由表成比例增大，这不仅消耗大量的路由器缓冲区，还耗费大量的 CPU 时间进行扫描，为解决这种问题，提出了自治系统（Autonomous System，AS）
Internet 将整个互联网划分为许多较小的自治系统，每个自治系统内可能包含许多局域网，同时，每个自治系统有权自主决定本系统内采用何种路由选择协议
这样一来，路由选择会按照层次方式进行，在自治系统内部的路由选择称为域内路由选择，在两个自治系统之间的路由选择称为域间路由选择
内部网关协议与外部网关协议
对于域内路由选择来说，其采用的路由选择协议被称为内部网关协议（Interior Gateway Protocol，IGP）
IGP 与互联网中其他自治系统中选用什么路由选择协议无关，目前这类路由选择协议应用的最多，常见的有 RIP 协议、OSPF 协议
对于域间路由选择来说，其采用的路由选择协议被称为外部网关协议（External Gateway Protocol，EGP）
其将路由选择信息从一个自治系统的边界传递到另一个自治系统中，目前使用最多的外部网关协议是 BGP-4 协议
自治系统的互联
如下图，是两个自治系统互联在一起的示意图，每个自治系统自己决定在系统内部运行何种路由协议，但每个自治系统都有一个或多个路由器，除了运行本系统内部的路由选择协议外，还要运行自治系统间的路由选择协议
