路由选择算法

路由选择协议的核心是路由算法。

理想的路由算法应具有以下特点：

（1）正确性，完整性

（2）简单性

（3）自适应通信量和网络拓扑的变化

（4）稳定性

（5）公平性

（6）最佳的

静态路由选择策略（非自适应路由选择）：

简单，开销小，但不能及时适应网络状态的变化，适用于小型网络。

动态路由选择策略（自适应路由选择）：

能较好地适应网络状态的变化，实现较为复杂，适用于大型网络。

分层次的路由选择协议：

因特网采用的路由选择协议主要是自适应的、动态的、分布式的、分层次的路由选择协议。

自治系统（autonomous system,AS）

在单一的技术管理下的一组路由器。

目前的因特网中，ISP就是一个自治系统。

网关协议分类：

（1）内部网关协议IGP（Interior Gateway Protocol），即一个自治系统内部使用的路由选择协议，如RIP和OSPF协议。

（2）外部网关协议EGP（External Gateway Protocol），若源主机和目的主机处在不同的自治系统中，当数据报传到一个自治系统的边界时，需要外部网关协议将路由选择信息传递到另一个自治系统中，常见的有BGP协议。

总之，使用分层次的路由选择算法，可将因特网的路由选择协议划分为：

（1）内部网关协议IGP（或域内选择路由）：如RIP和OSPF等

（2）外部网关协议EGP（或域间选择路由）：如BGP等

路由选择协议RIF（Routing Information Protocol）

RIP是一种分布式的基于距离向量的路由选择协议，最大的优点是简单。

RIP要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录，这一组距离，即为距离向量

RIP的距离也称为跳数，每经过一个路由器，跳数就+1,RIP的一条路径的最大跳数为15。

RIP协议特点：

（1）仅和相邻路由器交换信息，不相邻的路由器不交换信息

（2）路由器交换的信息是当前本路由所知道的全部信息（路由表）

（3）定时更新路由表

路由表中最主要的信息是到某个网络的距离（即最短距离），以及应经过的下一跳的地址。

路由表更新的原则是找出到每个目的网络的最短距离，此更新算法又称为距离向量算法。

RIP的距离向量算法（Bellman-Ford算法）：

假设需要更新的路由为R1，路由表为T1

相邻路由为R2，路由表为T2，

路由表T1

路由表T2

现在，需要把路由RA的路由表添加路由RB的路由表更新，需要以下步骤：

（1）将相邻路由器R2的路由表T2的所有距离都+1，并把下一跳路由器都改为R2，得到临时路由表temp

临时路由表T2

（2）将临时路由表的记录和路由RA的路由表记录T1做比较：

• temp的第一行的目的网络Net1在T1中没有存在，则直接插入到路由表T1中。
• temp的第二行的目的网络Net2在T1中存在，并且两个记录中下一跳路由器相同，都是R2，则更新此记录（表示以最新的为准）。
• temp的第三行的目的网络Net3在T1中存在，但下一跳路由器不同，则比较距离远近，选择最短距离的记录更新路由表T1。

（3）如果3分钟还没收到相邻路由表的更新路由表，则把此相邻路由器记为不可达的路由器，即把距离设置为16。

最终路由表T1

RIP协议让一个自治系统中的所有路由器都与自己相邻的路由器定期交换路由信息，不断更新路由表，使得从每一个路由器到每一个目的网络的路由都是最短的。

RIP报文由首部和路由部分组成。

RIP协议使用运输层的用户数据报UDP进行传送。

RIP报文的最大长度是504字节。

RIP协议的特点是：好消息传播得快，坏消息传播得慢。

RIP的优点是：实现简单，开销小。

缺点是：限制了网络规模，如果出现网络故障，传播的时间会大大增加。

对于网络规模较大的，应使用OSPF协议。

OSPF(Open Shortest Path First，开放最短路径优先)：

使用分布式的链路状态协议。

（1）向本自治系统中所有路由器发送信息，整个区域中所有的路由器都得到整个信息的一个副本。而RIP仅仅是向自己相邻的几个路由器发送信息。

（2）发送的信息就是与本路由器相邻的所有路由器的链路状态。

（3）只有当链路状态发生变化时，路由器才向所有路由器发送信息。

最终所有的路由器都能建立一个链路状态数据库（link-state database），即为全网的拓扑结构图。

OSPF的链路状态数据库能较快地进行更新，使各个路由器能及时更新路由表。OSPF的更新过程收敛得快。

OSPF使用IP数据报传送。

OSPF特点：

（1）OSPF对不同类型的业务可计算出不同的路由，这种灵活性是RIP没有的。

（2）OSPF可找出多条代价相同的路径。

（3）所有在OSPF路由器之间交换的分组都具有鉴别功能。

（4）OSPF支持可变长度的子网划分和无分类的编址CIDR。

（5）OSPF让每一条链路状态都带一个32位的序号，序号越大状态越新。

OSPF共有5种类型：

（1）问候分组，用来发现和维持邻站的可达性。

（2）数据库描述分组，向邻站给出自己的链路状态数据库中所有链路状态项目的摘要信息。

（3）链路状态请求分组，向对方请求发送某些链路状态项目的详细信息。

（4）链路状态更新分组，用洪泛法对全网更新链路状态，是OSPF最核心的部分。

（5）链路状态确认分组，对链路更新分组进行确认。

• OSPF规定，每两个相邻路由器，每隔10秒钟交换一次问候分组，确认哪些邻站是可达的。
• 若40秒没有收到某个相邻路由器发来的问候分组，则认为该相邻路由器是不可达的，应立刻修改链路状态数据库，重新计算路由表。
• 其他四种分组都是用来进行链路状态数据库的同步。
• OSPF让每一个路由器用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。（摘要信息是指有哪些路由器的链路状态信息已经写入了数据库）
• 链路状态请求、更新、确认分组，是用来更新路由数据库的。

边界网关协议BGP

BGP是不同AS（自治系统）的路由器之间交换路由信息的协议。

BGP力求寻找一条能够到达目的网络且比较好的路由，而不是寻找一条最佳路由。

BGP采用了路径向量路由选择协议。