路由算法

选路算法，目的是找到一条从原路由器到目的路由器最佳的路径。提高路由协议功能，尽量减少路由所带来开销的算法

理想的路由算法

1.算法正确和完整。根据路由表的指引，最终到达目的网络及主机

2.算法计算简单

3.算法适应通信量和网络拓扑的变化

4.算法最佳、公平、稳定

<1>静态路由选择策略

非自适应性路由选择。简单和开销小，但不能及时适应网络状态的变化

<2>动态路由选择策略

较好地适应网络状态的变化，实现起来复杂且开销大。在现实生活中普遍使用动态，分布式的路由选择协议，具体可以分为两种：内部网关协议和外部网关协议。

内部网关协议IGP（IRP）分布式路由选择协议
RIP（Routing Information Protocol）路由信息协议	OSPF（Open Shortest Path First）开放最短路径优先
分布式的基于距离向量的路由选择协议，从一路由器到目的网络的网络距离为距离向量	分布式的链路状态协议
特点： 1.仅和相邻路由器交换信息 2.发送信息为本路由器的全部信息（到某个网络的距离，应经过的下一跳地址） 3.固定时间间隔交换路由信息（定期交换路由表信息）	特点： 1.在本自治系统中向所有路由发送信息，洪泛法 2.发送信息为与本路由器相邻的所有路由器的链路状态 3.当链路状态发生变化时，路由器使用洪泛法交换信息
问题： 1.当网络出现故障时，要经过比较长的时间才能将此信息传送给所有的路由器 2.使用的最大距离为15 3.更新时间收敛时间过长	特点： 1.更新过程收敛得快 2.使用的IP数据报短 3.使用层次结构进行区域划分 4.使用多路径间的负载均衡（代价相同的多条路径上分配通信量） 5.支持可变长度的子网划分和CIDR

举例：假定网络中的路由器B的路由表有以下部分信息：

现在B收到C的路由信息，如下：

计算得出B更新后的路由表：

1.修改C所发来的路由信息，添加下一跳路由器项为C，所有的距离值加1，目的地址不变，修改后如下：

2.修改B表，将B路由表中没有的目的网络直接进行添加

若B表中有目的地址，且下一跳地址为C进行更新。

若B表中有目的地址，但下一跳地址不是C则判断距离，选择距离小的进行更新（距离相同，则不进行更新）。修改后B路由表如下：

路由器互相发送直接相连的链路信息和它拥有的到其它路由器的链路信息。每个OSPF路由器维护相同自治系统拓扑结构的数据库。从这个数据库里，构造出最短路径树来计算出路由表。当拓扑结构发生变化时，OSPF能迅速重新计算出路径，而只产生少量的路由协议流量。