路由生产算法

路由分为域内路由和域间路由

内部网关协议IGP，指的是在一个自治系统内部的路由器所采用的路由算法，通常有RIP和OSPF协议，即域内路由。

外部网关协议EGP，指的时在一个或多个自治系统之间所采用的算法，有EGP协议(旧)，和BGP协议。

RIP路由协议采用的算法是距离向量算法：

每一个相邻路由器发送过来的路由表都要经过以下步骤：

1、对地址为X的 路由器发过来的路由表，先修改此路由表中的所有项目：把”下一跳”字段中的地址改为X，并把所有”距离”字段都加1。

2、对修改后的路由表 中的每一个项目，进行以下步骤：

2.1、将X的路由表(修改过的)，与S的路由表的目的网络进行对比。

若在X中出现，在S中没出现，则将X路由表中的这一条项目添加到S的路由表中。

2.2、对于目的网络在S和X路由表中都有的项目进行下面步骤

2.2.1、在S的路由表中，若下一跳地址是x

则直接用X路由表中这条项目替换S路由表中的项目。

2.2.2、在S的路由表中，若下一跳地址不是x

若X路由表项目中的距离d小于S路由表中的距离，则进行更新。

3、若3分钟还没有收到相邻路由器的更新表，则把此相邻路由器记为不可到达路由器，即把距离设置为16

OSPF采用洪泛法，即路由器向所有相邻的路由器发送信息，每一个相邻路由器将此信息再发给所有相邻的路由器。这样所有的路由器都能建立一个链路状态数据库，即每个路由器都知道全网有多少个路由器，以及哪些路由器之间是相连的，其距离等等信息。然后根据最短路径算法，构建自己的路由表。

而RIP只知道相邻路由器之间的信息，不知道全网的拓补结构。而且OSPF不是不断地用洪泛法，只有链路状态发生变化才采用洪泛法。RIP每隔30分进行一次数据交换，信息交换代价大。

路由收敛指网络的拓扑结构发生变化后，路由表重新建立到发送再到学习直至稳定，并通告网络中所有相关路由器都得知该变化的过程。也就是网络拓扑变化引起的通过重新计算路由而发现替代路由的行为。RIP因向相邻路由发送信息，不断改变自己的路由表，收敛的非常慢。而OSPF采取洪泛法，每个路由器的都知道全网的拓补结构，构建路由表很快。

BGP外部网关协议，采取路径向量算法，为什么不采取OSPF呢?因为因特网规模太大，每个路由器都必须有一个很大的链路状态数据库，每次更新都要花费很长时间。2.为了考虑有关政策，比如AS1自制系统要给AS2发送数据，经过AS3，但AS3不愿意让数据通过。

由于上述情况，因此BGP寻求一条能够到达目的网络的最佳路由。

采用了路径向量路由选择协议，从自制系统中选择一个路由器作为BGP发言人，并避免绕圈圈，然后和其他BGP发言人进行通信，交换网络是否可达，然后各BGP发言人你就根据信息找出到达各自制系统较好的路由。