路由算法介绍
网络层的作用：1、路由选择
2、网络互连
3、拥塞控制
4、为上层提供服务
网络层的主要功能是将分组从源机器路由到目标机器。

完成路由选择的路由算法是网络层设计的最主要内容。

路由算法：它负责确定一个进来的分组应该被传送到哪一条输出线路上。

如果是数据报子网，将在每一个分组到达时作此决定
如果是虚电路子网，是在虚电路建立时决定，该连接上所有分组都将沿此线路传输
路由算法设计必须考虑的问题：正确性简单性健壮性稳定性公平性最优性路由算法的原则：按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径。

静态算法：不会根据当前测量或者估计的流量和拓扑结构，来调整它们的路由决策，所有的路由选择是预先在离线情况下计算好的，在网络启动的时候被下载到路由器中。

1、最短路径路由：
如图所示，图中的每个节点代表一台路由器，每条弧代表一条通信线路，线路上的数字是它的开销。

现在我们想找到从A到D的最短路径。

过程：
（1）节点A标记为永久节点，依次检查每一个与A相邻的节点，并检查它们与A之间的距离。

（2）如果新的标记距离小于该节点原来的标记，说明找到了一条更短路径，该节点需要重新标记，作为暂时性标记
（3）检查整个图中所有有暂时性标记的节点，使其中具有最小标记的那个节点成为永久节点，并且作为下一个工作节点。

（4）重复上述过程，直到没有新的永久节点为止。

如下图所示
2、扩散法：每一个进来的分组将被发送到除了它进来的那条线路之外的每一条输出线路上。

产生的问题：会产生大量的重复分组。

解决办法：
在数据包头设一个计数器初值，每经过一个节点自动减1，计数值
为0 时，丢弃该数据包
在每个节点上建立登记表，则数据包再次经过时丢弃
缺点：重复数据包多，浪费带宽
优点：可靠性高，可用于并发数据库更新。

极好的健壮性，可用于军事应用。

常作为衡量标准，评价其它路由算法
现代计算机网络通常使用动态的路由算法（自适应算法），而不是上面介绍的静态路由算法，因为静态路由算法不会考虑到网络的当前负载情况。

自适应算法：随拓扑结构和流量的变化改变它们的路由决策，又称为动态路由算法。

1、 距离矢量路由：每个路由器维护一张表（即一个矢量），表中列出了当前抑制的到每个目标的最佳距离，以及所使用的线路。

通过邻居之间互相交换信息，路由器不断更新它们内部的表。

举例：
B A E
F
D
C
2
3
7
6
1
8
5
4 延迟信息B
缺点：交换的路径信息量大；路径信息不一致；坏消息收敛速度慢；不适合大型网络。

坏消息传播慢的原因：无穷计算问题。

假定A最初处于停机状态，所有其它路由器都知道这一点，那么，它们都将A的延迟记录为无穷大。

当A启动时，其它的路由器通过矢量交换知道了这一点。

通过定期的矢量交换，在四次后，得到了A到其它路由器的距离。

当A突然停机的时候，所有路由器并不清楚这一情况，要经过很多次交换后，所有路由器到A的距离才会趋向于无穷大。

这样就产生了好消息传播非常快，对坏消息却是反应迟钝的情况。

2、链路状态路由：
代替距离矢量路由算法的原因：（1）线路带宽不一致；（2）距离矢量路由算法需要很长时间才能收敛到稳定状态。

工作过程：（1）发现它的邻居节点，并知道其网络地址。

（2）测量到各邻居节点的延迟或者开销。

（3）构造一个分组，分组中包含所有它刚刚知道的信息。

（4）将这个分组发送给所有其它的路由器。

（5）计算出到每一个其它路由器的最短路径。