一、路由选择协议概述

路由选择分为：静态路由选择和动态路由选择

• 静态路由选择：由人工配置的网络路由，默认路由，特定主机路由，黑洞路由等，配置方式简单，开销小，但不能及时适应网络状态的变化

• 动态路由选择：路由器通过路由选择协议自动获取路由信息，比较复杂，开销较大，能较好的适应网络状态的变化，适用于大规模网络

因特网所采用的路由选择协议的特点

• 自适应：动态路由选择，能较好地适应网络状态的变化
• 分布式：路由器之间交换路由信息
• 分层次：将整个因特网划分为较小的自治系统AS（autonomous system）

二、自治系统

自治系统(Autonomous System，AS)：单一技术管理下的一组路由器，这些路由器使用一种AS内部的路由选择协议和共同的度量来确定分组在该AS内的路由，同时还使用一种AS之间的路由选择协议来确定分组在AS之间的路由。

一个自治系统内的所有网络都由一个行政单位（如一家公司、一所大学、一个政府部门等)管辖，一个自治系统的所有路由器在本自治系统内都必须是连通的。

自治系统内部的路由选择称为域内路由选择，自治系统之间的路由选择称为域间路由选择。因特网有两大类路由选择协议。

1. 内部网关协议(Interior Gateway Protocol，IGP)

内部网关协议即在一个自治系统内部使用的路由选择协议，它与互联网中其他自治系统选用什么路由选择协议无关。目前这类路由选择协议使用得最多，如RIP和OSPF。

2. 外部网关协议(External Gateway Protocol，EGP)

若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时（两个自治系统可能使用不同的IGP)，就需要使用一种协议将路由选择信息传递到另一-个自治系统中。这样的协议就是外部网关协议（EGP)。目前使用最多的外部网关协议是 BGP-4。

三、常见的路由选择协议

内部网关协议IGP
    路由信息协议RIP
    内部网关路由协议IGRP
            RIP和IGRP是基于距离向量的，RIP是因特网上最早使用的，IGRP是思科早期私有的协议，现在已经被EIGRP取代
    增强型内部网关路由协议EIGRP
            思科特有的，用来取代IGRP的混合型路由协议（基于距离向量和链路状态）
    开放式最短路径优先OSPF
    中间系统到中间系统IS-IS
            OSPF和IS-IS是基于链路状态的，OSPF在各种网络中广泛使用，集成化IS-IS是ISP骨干网上最长常用的IGP协议
外部网关协议EGP
    边界网关协议BGP

路由器是一种具有多个输入端口和输出端口的专用计算机，其任务是转发分组。

四、路由信息协议（RIP）

路由信息协议（Routing Information Protocol，RP）是内部网关协议（IGP）中最先得到广泛应用的协议。RIP是一种分布式的基于距离向量的路由选择协议，其最大优点就是简单。

RIP规定

1. 网络中的每个路由器都要维护从它自身到其他每个目的网络的距离记录（因此这是一组距离，称为距离向量)。
2. 距离也称跳数（Hop Count)，规定从一个路由器到直接连接网络的距离（跳数）为1。而每经过一个路由器，距离（跳数）加1。
3. RIP认为好的路由就是它通过的路由器的数目少，即优先选择跳数少的路径。
4. RITP允许一条路径最多只能包含15个路由器（即最多允许15跳)。因此距离等于16时,它表示网络不可达。可见RIP只适用于小型互联网。距离向量路由可能会出现环路的情况，规定路径上的最高跳数的目的是为了防止数据报不断循环在环路上，减少网络拥塞的可能性。
5. RIP 默认在任意两个使用RIP的路由器之间每30秒广播一次RIP路由更新信息，以便自动建立并维护路由表（动态维护)。
6. 在RTP中不支持子网掩码的RIP广播，所以RIP中每个网络的子网掩码必须相同。但在新的 RIP2 中，支持变长子网掩码和 CIDR。

距离向量算法

每个路由表项目都有三个关键数据：<目的网络N，距离d，下一跳路由器地址X>。对于每个相邻路由器发送过来的RIP报文，执行如下步骤:

1. 对地址为X的相邻路由器发来的RIP报文，先修改此报文中的所有项目：把“下一跳”字段中的地址都改为X，并把所有“距离”字段的值加1。

2. 对修改后的RIP报文中的每个项目，执行如下步骤：

①当原来的路由表中没有目的网络 N 时，把该项目添加到路由表中。

②当原来的路由表中有目的网络N，且下一跳路由器的地址是 X 时，用收到的项目替换原路由表中的项目。

③当原来的路由表中有目的网络N，且下一跳路由器的地址不是X时，如果收到的项目中的距离d小于路由表中的距离，那么就用收到的项目替换原路由表中的项目；否则什么也不做。

3. 如果180秒(RIP默认超时时间为180秒)还没有收到相邻路由器的更新路由表，那么把此相邻路由器记为不可达路由器，即把距离设置为16（距离为16表示不可达)。
4. 返回。

距离向量算法练习1

已知 路由器R6 的路由表，现收到相邻路由器R4 发来的路由更新信息，试更新路由器R6 的路由表:

距离向量算法练习2

注：来自B的向量为 (5, 0, 8, 12, 6, 2) 表明B到A的距离为5，到C的距离为8，到D的距离为12，诸如此类。

答案为 D

RIP 报文格式

从 RIP的报文格式可知，RIP是应用层协议，使用UDP传送数据。一个 RIP 报文最多可包括 25 个路由，如超过，必须再用一个 RIP 报文传送。

RIP 最大的优点是实现简单、开销小、收敛过程较快。RIP的缺点如下:

1. RP限制了网络的规模，它能使用的最大距离为15（16表示不可达)。
2. 路由器之间交换的是路由器中的完整路由表，因此网络规模越大，开销也越大。
3. 网络出现故障时，会出现慢收敛现象（即需要较长时间才能将此信息传送到所有路由器)，俗称“坏消息传得慢”，使更新过程的收敛时间长。

RIP是应用层协议，它使用UDP传送数据(端口520)。RIP选择的路径不一定是时间最短但一定是具有最少路由器的路径。因为它是根据最少跳数进行路径选择的。

五、开放最短路径优先（OSPF)协议

OSPF协议的基本特点

开放最短路径优先（OSPF）协议是使用分布式链路状态路由算法的典型代表，也是内部网关协议（IGP）的一种。OSPF与RIP相比有以下4点主要区别:

1. OSPF向本自治系统中的所有路由器发送信息，这里使用的方法是洪泛法。而 RIP 仅向自己相邻的几个路由器发送信息。
2. 发送的信息是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。“链路状态”说明本路由器和哪些路由器相邻及该链路的“度量”(或代价)。而在RIP中，发送的信息是本路由器所知道的全部信息，即整个路由表。
3. 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息，并且更新过程收敛得快，不会出现RTP“坏消息传得慢”的问题。而在 RIP中，不管网络拓扑是否发生变化，路由器之间都会定期交换路由表的信息。
4. OSPF是网络层协议，它不使用UDP或TCP，而直接用P数据报传送（其P数据报首部的协议字段为89)。而RIP是应用层协议，它在传输层使用UDP。
5. 支持可变长度的子网划分和无分类编址CIDR。

OSPF的基本工作原理

由于各路由器之间频繁地交换链路状态信息，因此所有路由器最终都能建立一个链路状态数据库。这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（称为链路状态数据库的同步)。然后，每个路由器根据这个全网拓扑结构图，使用Dijkstra 最短路径算法计算从自己到各目的网络的最优路径，以此构造自己的路由表。此后，当链路状态发生变化时，每个路由器重新计算到各目的网络的最优路径，构造新的路由表。

注意:虽然使用Dijkstra算法能计算出完整的最优路径，但路由表中不会存储完整路径，而只存储“下一跳”（只有到了下一跳路由器，才能知道再下一跳应当怎样走)。

OSPF 的区域

OSPF 分组

六、边界网关协议(BGP)

层次路由

当网络规模扩大时，路由器的路由表成比例地增大。这不仅会消耗越来越多的路由器缓冲区空间，而且需要用更多CPU时间来扫描路由表，用更多的带宽来交换路由状态信息。因此路由选择必须按照层次的方式进行。
因特网将整个互联网划分为许多较小的自治系统（注意一个自治系统中包含很多局域网),每个自治系统有权自主地决定本系统内应采用何种路由选择协议。如果两个自治系统需要通信,那么就需要一种在两个自治系统之间的协议来屏蔽这些差异。据此，因特网把路由选择协议划分为两大类:

1. 一个自治系统内部所使用的路由选择协议称为内部网关协议（IGP)，也称域内路由选择，具体的协议有RIP和OSPF等。

2）自治系统之间所使用的路由选择协议称为外部网关协议（EGP)，也称域间路由选择，用在不同自治系统的路由器之间交换路由信息，并负责为分组在不同自治系统之间选择最优的路径。具体的协议有BGP。

使用层次路由时，OSPF将一个自治系统再划分为若干区域(Area)，每个路由器都知道在本区域内如何把分组路由到目的地的细节，但不用知道其他区域的内部结构。

采用分层次划分区域的方法虽然会使交换信息的种类增多，但也会使OSPF协议更加复杂。但这样做却能使每个区域内部交换路由信息的通信量大大减小，因而使 OSPF协议 能够用于规模很大的自治系统中。

边界网关协议规定

边界网关协议《Border Gateway Protocol，BGP)是不同自治系统的路由器之间交换路由信息。

BGP 协议的特点

• 和谁交换?

与其他AS的邻站BGP发言人交换信息。

• 交换什么?

交换的网络可达性的信息，即要到达某个网络所要经过的一系列AS。

• 多久交换?

发生变化时更新有变化的部分。

BGP所交换的网络可达性的信息就是要到达某个网络所要经过的一系列A。当BGP发言人互相交换了网络可达性的信息后，各BGP发言人就根据所采用的策略从收到的路由信息中找出到达各AS的较好路由。

BGP协议交换信息的过程

BGP发言人交换路径向量：
主干网还可发出通知：“要到达网络N5、N6和N7可沿路径（AS, AS）。”

BGP协议报文格式

一个BGP发言人与其他自治系统中的BGP发言人要交换路由信息，就要先建立TCP连接，即通过TCP传送，然后在此连接上交换BGP报文以建立BGP会话(session)，利用BGP会话交换路由信息。

BGP协议特点

BGP支持 CIDR，因此BGP的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列。

在BGP刚刚运行时，BGP的邻站是交换整个的BGP路由表。但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销都有好处。

BGP-4共使用4种报文:

1. 打开(Open）报文。用来与相邻的另一个 BGP发言人建立关系。
2. 更新(Update）报文。用来发送某一路由的信息，以及列出要撤销的多条路由。
3. 保活(Keepalive〉报文。用来确认打开报文并周期性地证实邻站关系。
4. 通知(Notification）报文。用来发送检测到的差错。也被用于关闭连接。

RIP、OSPF与BGP的比较

• RIP 是一种分布式的基于距离向量的内部网关路由选择协议，通过广播UDP报文来交换路由信息。
• OSPF是一个内部网关协议，要交换的信息量较大，应使报文的长度尽量短，所以不使用传输层协议（如UDP或TCP)，而是直接采用IP。
• BGP是一个外部网关协议，在不同的自治系统之间交换路由信息，由于网络环境复杂，需要保证可靠传输，所以采用TCP。