计算机网络 路由算法

路由选择协议的核心是路由算法，即需要何种算法来获得路由表中的各个项目。

路由算法的目的很明显，给定一组路由器以及连接路由器的链路，路由算法需要找到一条从源路由器到目的路由器的最佳路径，通常，最佳路径是由最低费用组成的路径。

1.静态路由与动态路由

路由器转发分组是通过路由表转发的，而路由表是通过各种算法得到的。

从能否随着网络的通信量或者拓扑自适应的进行调整变化来划分，路由算法可以分为如下两大类。

1）静态路由算法，指的是由网络管理员手工的配置每一条路由。

2）动态路由算法，根据网络流量负载和拓扑结构的变化来动态调整自身的路由表。

静态路由算法的特点是简单而且开销较小，但是不能及时的适应网络状态的变化，适用于简单的小型的网络。动态路由算法能够较好的适应网络状态的变化，但是实现起来复杂，开销也大，适用于比较复杂的较大网络。

常用的动态路由算法可以分为两类：距离向量路由算法和链路状态路由算法。

RIP：规定，

1）网络中的每个路由器都要维护从它自身到其他每个目的网络的距离记录，即距离向量。

2）RIP使用跳数（Hop Count）来衡量到达目的网络的距离。规定从一路由器到直接相连接的网络的距离定义为1；而没经过一个路由器，距离就加1。

3）RIP认为好的路由就是它通过的路由器的数量少，即，距离短或者跳数少。

4）RIP允许一条路径最多只能包含15个路由器，因此距离16时表示网络不可达。可见RIP只能适用于小型互联网，距离向量路由可能会出现环路的情况，规定路径上的最高跳数的目的是为了防止分组不断在环路上循环，减少网络拥塞的可能性。

5）每个路由表都有三个关键字段：《目的网络N，距离d，下一跳的路由地址X》

RIP是应用层的协议，他使用UDP传输数据，RIP选择的路径不一定是时间最短的，但是一定是具有最少的路由跳数的，因为他是根据最少跳数进行路由选择的。