1 基本概念
路由选择协议的核心就是路由算法：即需要何种算法来获得路由表中的各项目。
1）理想的路由算法
- 算法必须是正确和完整的
- 算法在计算上应该简单
- 要有自适应性
- 应具有稳定性
- 算法应是公平的
- 算法应是最佳的
2）分层次的路由选择协议
采用分层次的路由选择协议的原因：
- 互联网规模比较大，不可能让路由器知道如何到达所有的网络。
- 很多单位不想让外界知道自己单位网络的内部路由选择协议。
因此互联网被划分成多个较小的自治系统（autonomous system，AS）。AS是在单一技术管理下的一组路由器，这些路由器使用自治系统内部的路由选择协议和共同的度量。一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。
一个大的ISP就是一个自治系统。互联网把路由选择协议分为两大类：
- 内部网关协议IGP：在一个自治系统内部使用的路由选择协议。具体有很多种如RIP和OSPF
- 外部网关协议EGP：源主机和目标主机不在一个自治系统内时，需要将路由选择信息传递到另一个自治系统。目前使用的就是BGP-4
2 内部网关协议 RIP
RIP（Routing Information Protocol，路由信息协议） 是一种基于距离向量的路由选择协议。
RIP协议要求网络中每个路由器都要维护一个从它自己到其它目的网络的距离记录。距离是指跳数，直接相连的路由器跳数为 1。
RIP允许一条路径最多只能包含15个路由器。因此RIP只适用于小型互联网。
RIP协议使用运输层的用户数据报UDP进行传送。特点是：故障消息传播慢，而好消息传播快
1）RIP 协议下的路由器工作原理
- 仅和临近的路由器交换信息
- 交换的信息是本路有其当前所知道的全部信息，也就是自己现在的路由表
- 按固定的时间间隔交换路由信息
2）距离向量算法
- 对地址为 X 的相邻路由器发来的 RIP 报文，先修改报文中的所有项目，把下一跳字段中的地址改为 X，并把所有的距离字段加 1；
- 对修改后的 RIP 报文中的每一个项目，进行以下步骤：
- 若原来的路由表中没有目的网络 N，则把该项目添加到路由表中；
- 否则：若下一跳路由器地址是 X，则把收到的项目替换原来路由表中的项目；否则：若收到的项目中的距离 d 小于路由表中的距离，则进行更新（例如原始路由表项为 Net2, 5, P，新表项为 Net2, 4, X，则更新）；否则什么也不做。
- 若 3 分钟还没有收到相邻路由器的更新路由表，则把该相邻路由器标为不可达，即把距离置为 16。
3 内部网关协议 OSPF
OSPF（Open Shortest Path First，开放最短路径优先），原理简单，实现复杂。是为了克服 RIP 的缺点而开发出来的。OSPF使用的是分布式的链路状态协议，而不像RIP那样使用距离向量协议。
OSPF不用UDP而是直接用IP数据报发送。
1）OSPF 的要点及与 RIP 的区别
- 向本自治系统中的所有路由器发送信息，这种方法是洪泛法。
- 发送的信息就是与相邻路由器的链路状态，链路状态包括与哪些路由器相连以及链路的度量，度量用费用、距离、时延、带宽等来表示。
- 只有当链路状态发生变化时，路由器才会发送信息。
洪泛法：路由器将信息通过所有输出端口向其邻近路由器发送，每一个邻近路由器再将信息发往其邻近路由器（但不发给发来信息的那个路由器）
经过路由器之间的链路状态信息的交换，所有路由器最终都能建立一个链路状态数据库，这个数据库就是全网的拓扑结构图。每个路由器使用这个数据库来构建自己的路由表。
2）OSPF 分组有五种类型
- 问候分组，用来发现维持邻站的可达性
- 数据库描述分组，向邻站发出自己的链路状态数据库中的所有链路状态项目的摘要信息
- 链路状态请求分组，请求对方发送链路状态信息
- 链路状态更新分组，用洪泛法对全网更新链路状态
- 链路状态确认，对链路更新分组的确认
3）工作机理
- 每组相邻的路由器每隔10秒交换一次问候分组，以确保可达，若40秒后没收到某个邻近路由器的问候，则表明该邻近路由器不可达。应立即修改数据看，并重新计算路由表。
- 在路由器刚开始工作时不是将自己的本地链路状态对全网广播，因为这样会占用太大网路带宽，而是发送本地已有链路状态的信息摘要。经过和其他路由器交换链路状态描述分组和后，各个路由器使用链路状态请求分组向目的路由器请求自己缺失的链路状态的详细信息。
- 就是各自发送自己已有信息的摘要，然后每个路由器根据摘要查看自己是否缺失某信息，若缺失就向发送该信息摘要的路由器请求详细信息。
- 在网络运行过程中，也就是链路状态数据库已经建立好了，这时某个路由器的链路状态发送变化，那么该路由器就向全网使用链路更新分组，用洪泛法向全网更新状态。
- 在收到更新分组后要回复链路状态确认分组，即使用可靠的洪泛法。
4 外部网关协议 BGP
BGP（Border Gateway Protocol，边界网关协议）
AS 之间的路由选择很困难，主要是由于：
- 互联网规模很大；
- 各个 AS 内部使用不同的路由选择协议，无法准确定义路径的度量；
- AS 之间的路由选择必须考虑有关的策略，比如有些 AS 不愿意让其它 AS 经过。
BGP 只能寻找一条比较好的路由，而不是最佳路由。
每个 AS 都必须配置 BGP 发言人，通过在两个相邻 BGP 发言人之间建立 TCP 连接来交换路由信息。
5 路由器的构成
- 具有多个输入端口和多个输出端口的专用计算机，任务是转发分组
- 路由器某个端口接收到分组，按照分组要去的目的地，将该分组从路由器的某个合适的端口转发给下一跳路由器，直到该分组到达终点
- 由路由选择和分组转发部分组成
- 路由选择部分：即控制部分。核心构件是路由选择处理机，其任务是根据所选择的路由协议构造出路由表，同时经常或者定期的和相邻的路由器交换信息以不断更新维护路由表
- 分组转发部分：交换结构、一组输入端口、一组输出端口
- 交换结构根据转发表对分组进行处理，将某个输入端口进入的分组从另一个合适的输出端口转发出去
