路由选择算法及路由协议

路由器要实现数据转发的功能，至少需要完成两个工作：
① 选路策略。根据数据包的目的地和网络的拓扑结构选择一条最佳路径.把对应不同目的地的最佳路径存放在路由表中，及如何建立并维护路由表。包括静态路由选择以及各种动态路由协议。
② 选路机制。查路由表从而决定向哪个接口转发数据，并执行相应的操作。即如何根据路由表内容转发数据包。
选路策略只影响路由表的内容，比如对同一个目的IP地址来说.由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。
            选路机制的基本工作过程见上一小节，本小节重点介绍路由器中完成选路策略功能的路由选择算法及路由协议。
1. 路由选择算法
            路由选择的基本概念可参见6.1.2节的相关内容，而互联网中的路由选择算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确传输路径的方法或者策略。一个理想的路由算法至少应该具备以下几点特征：
① 完整性和正确性：即每个路由器中的路由表都必须给出到所有可能目的节点的下一跳应怎样走，且给出的走法是正确的。
② 简单性：即路由选择的计算不应使网络通信量增加太多的额外开销。
③ 健壮性：主要指当某些节点、链路出现故障不能工作，或故障恢复后投入运行，算法能及时改变路由。
④ 公平性：即算法对所有用户都平等的。
⑤ 最佳性：即以最低的成本来实现路由算法。
            互联网的复杂性使得当前使用的路由算法主要是动态的、分布式的。目前互联网上的动态路由协议主要基于两种动态分布式路由选择算法：距离矢量路由算法和链路状态路由算法。
2. 路由协议
            由于互联网规模太大，分布范围太广，所以路由表中对应每一个目的网络都有一个条目是不可能的，同样.也不可能采用一个全局的路由算法或协议。因此.Internet将整个网络划分为若干个相对自治的局部系统，即自治系统(AS：AutonomousSystem)₀自治系统可以定义为同一机构下管理的路由器和网络的集合。路由协议是IP路由器最重要的一个组成部分，可以分为内部网关协议(IGP：InteriorGatewayProtoco)和外部网关协议(EGP：ExteriorGatewayProtocol)两大类。内部网关协议是用于自治系统内部的动态路由协议，包括路由信息协议RIP、开放最短路径优先OS-PF、()SI的IS-IS和Cisco路由器系统中的EIGRP(EnhancedInteriorGatewayRoutingProtocol,增强型内部网关路由选择协议)等；而外部网关协议则是用于自治系统之间拓扑信息交换的路由协议，包含边界网关协议BGP等。
            为了降低数据包在网络中的传输开销和时延，要求为数据选择的路径是最短的。这里的“最短”在不同的场合具有不同的含义，它可以是跳数的多少、物理距离的长短或者时延的大小等。互联网中使用的各种路由协议或者路由算法，其根本目的就是寻找源节点和目的节点之间最短的一条路径，即最短路由。其中RIP和BGP使用距离矢量路由算法，OSPF使用链路状态路由算法来寻找最短路由。
下面对主要的RIP和OSPF路由协议进行简要介绍。
            在各种内部网关协议中，RIP是出现最早，也是使用时间最长的协议之一，它使用距离矢量算法来计算路由。具体来说，各个路由器都维持一个距离矢量表，对每个目的节点都有一个对应的表项，包括到该目的节点最短路径上的下一个路由器和到该目的节点的最短路径长度两项内容。路由器周期地和相邻路由器交换路由表中的信息，即向邻居路由器发送路由表的全部或部分。各个路由器根据收到的信息，重新计算到各目的节点的距离，并对自己的路由表进行修正。这样使得每一个路由器都可以知道其他路由器的情况,并形成关于网络“距离”的累积透视图.并据此更新路由表。RIP的优点是易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。
            OPSF的提出主要是为了克服RIP的缺陷。在网络中，每个OSPF路由器都维护一个用于跟踪网络状态的链路状态数据库，内容是反映路由器状态的各种链路状态通告，包括路由器可用接口、已知可达路由和链路状态信息。各OSPF路由器都会主动测试所有与之相邻的路由器的状态，并根据测试结果设置相关链路的状态。这样，路由器就得到了一张整个网络拓扑结构的图，再利用最短路由选择算法（详见6.1.2节）计算所有路由，并写到路由表中。OPSF能够及时反映网络拓扑结构的变化，收敛速度很快，适用于规模较大及拓扑变化比较快的网络，但对处理器性能要求比较高，占用的网络带宽比较多。