Internet路由协议

基本概念

为了便于管理，Internet将整个互联网络划分为相对较小的自治系统（AS，autonomous system）。一个自治系统内的所有网络通常属于一个行政单位（例如以所公司、大学或政府部门）。一个自治系统的所有路由器在本自治系统内都必须是连通的

自治系统

自治系统.png

Internet路由协议分类

• 内部网关协议IGP（interior gateway protocol）
自治系统AS内使用的路由算法，RIP、OSPF
• 外部网关协议EGP（exterior gateway protocol）
自治系统AS之间使用的路由算法，BGP

内部网关协议

路由信息协议RIP协议（Routing information Protocol）

RIP是一种分布式的基于距离向量的路由选择协议

距离的定义

RIP使用跳数度量来衡量到达目的站的距离，不能同时使用多种度量，比如时延等。也就是说如果有一条路径是跳数最少但是时延比较大的，和另外一条跳数比较大但时延较小的路径，按照RIP协议会按照跳数最少的来选择路径，不管时延是多少
从一路由器到直接连接的网络的距离定义为1，从一路由器到非直连的网络的距离定义为所经过的路由器数加1。RIP允许一条路径最多只能包含15个路由器。“距离”的最大值为16时即相当于不可达，数据会被丢弃，可见RIP只适用于小型互联网

RIP协议的三个要点

• 仅和相邻路由器交换信息
• 交换的信息时当前本路由器所知道的全部信息，即自己的路由表
• 按固定的时间间隔交换路由信息，例如每隔30秒

RIP协议报文格式

RIP协议报文格式.png

距离向量的算法

对每一个相邻路由器发送过来的RIP报文，进行以下步骤：

步骤.png

上面给出的距离向量算法的基础就是Bellman-Ford 算法(或Ford-Fulkerson 算法)。这种算法的要点是这样的: 设X是结点A到B的最短路径上的一个结点。若把路径A→B拆成两段路径A-X和X-B.则每一段路径A-X和X→B也都分别是结点A到X和结点X到B的最短路径

下面是对上述距离向量算法的五点解释：

解释.png

例：己知路由器R6有表R6所示的路由表。现在收到相邻路由器R4发来的路|由更新信息，如表R4所示。 试更新路由器R6的路由表

更新R6路由表.png

把这个表的每一行和表R6进行比较
第一行在表R6中没有，因此要把这行添加到表R6中
第二行的Net2在表R6中有，且下跳路由器也是R4.因此要更新(距离增大了)
第三行的Net3在表R6中有， 但下一跳路由器不同。于是就要比较距离。新的路由器的距离是2，小于原来表中的4，因此要更新
这样，得出更新后的R6的路由表如表R6新所示

RIP协议的优缺点

• 优点：就是实现简单，开销较小
• 缺点：当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。
RIP限制了网络的规模，它能使用的最大距离为15。路由器之间交换完整路由表，随着网络规模的扩大，开销也就增加

内部网关路由协议OSPF协议（Open Shortest Path First）

OSPF是一种公开发表的分布式的链路状态协议

OSPF要点

• 向本自治系统中所有路由器发送信息（洪泛）
• 发送的信息就是与本路由器相邻的所有路由器的链路状态（即本路由器都和哪些路由器相邻，以及该链路的“度量”）
• 支持多种距离衡量尺度，例如：物理距离、延迟等（综合考虑最优路径）

OSPF特点

• 不用UDP而是直接用IP数据报传送
• 允许管理员给每条路由指派不同的代价。比如对于非实时的业务科设置较低的代价，对于时延敏感的业务可设置为很高的代价
• 如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径，即多路径间的负载平衡
• 有鉴别功能，保证仅在可信赖的路由器之间交换链路状态信息
• 支持可变长度的子网划分和无分类的编制CIDR
• 由于网络中的链路状态可能经常发生变化，因此OSPF让每个链路状态都带上一个32位的序号，序号越大状态越新
• 路由更新过程收敛的快
• 支持隧道技术

OSPF的分层路由

为了使OSPF能够用于规模很大的网络，OSPF将一个自治系统划分为若干个更小的范围，叫做区域。每一个区域都有一个32bit的区域标识符（用点分十进制表示）。设定一个主干区域（backbone area），标识符规定为0.0.0.0，用于连通其他各区域。利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。在一个区域内部的路由器只知道本区域的完整网络拓扑，不需要知道其他区域的网络拓扑的情况。OSPF更加适合大规模的网络路由

OSPF的协议操作

建立路由器的邻接关系→发现路由器→选择适当的路由器→维护路由信息

OSPF路由协议的路由层次

这是一个自治系统划分出的若干区域↓

OSPF路由协议的路由层次.png

OSPF分组

OSPF分组.png

OSPF分组类型

• 类型1：问候（Hello）分组
• 类型2：数据库描述（Database Description）分组
• 类型3：链路状态请求（Link State Request）分组
• 类型4：链路状态更新（Link State Update）分组，用洪泛法对全网更新链路状态
• 类型5：链路状态确认（Link State Acknowledgment）分组

OSPF的基本操作

OSPF的基本操作.png

RIP和OSPF形象总结

RIP：
是一个距离矢量协议,也叫基于传闻的协议.路由器之间运行RIP,虽然彼此会传递更新报文,路由器也能学习到非直连网络的路由信息,但是！网络是如何连接而成的？有几台路由器？各有几个接口？接口类型是什么样的？从自身出发去往一个非直连网络有哪些路径？这些信息路由器一概不知。只是听从邻居的话,使用邻居做为去往一个又一个非直连网络的下一跳.
例如R1---R2---X 该例子中R1连接R2, R2身后连接X网络, 当在R1和R2之间运行RIP之后 ,R2给R1发送的更新报文中会包含X网络路由。这相当于R2在告诉R1, 想去往X网络请使用我R2做下一跳, R1会照办。将路由加入本地路由表,下一跳地址设置为R2.但R1其实并不知道X在哪里,自己去往X有哪些可行路径,路径包含哪些路由都不知道,因为不能证明R2传递的路径信息的真伪。因此只能选择相信,但如果X网络不在R2身后,R2认可的X网络路径信息如果是错的,R1收到更新也无法辨别,只能选择信任。在这种情况下,路由器之间彼此传递错误的路径信息就会导致路由选择环路,导致去往X网络的数据在环中不停传递,浪费大量资源
OSPF：
是一个链路状态协议,也叫基于拓扑的协议。路由器之间运行OSPF之后，彼此交互的更新报文中包含的不是路由条目，而是LSA。虽然LSA有很多类型，不同场合路由器会使用特定LSA传输特定信息，但是大体上LSA包含的内容既包含拓扑信息，又包含路由信息。比如说路由器产生的1类LSA里包含该路由器自身的信息，比如他的路由器ID，他是什么类型的路由器？以及该路由器宣告进OSPF的接口信息，有几个接口？连接的是什么类型的链路？有没有通过接口建立其他OSPF邻居？如果有邻居的RID是多少？每个接口IP地址，子网掩码，度量值是多少，都会在1类LSA中包含。路由器收到邻居的LSA后，会在一个区域内泛洪扩散，使得区域内所有路由器都能收到这条LSA。当OSPF运行一段时间后，每台路由器都能收到区域内所有路由器所产生的LSA，基于这些LSA路由器能知道整个区域是怎么连接而成的。有多少台路由器？每台路由器有多少接口？都是什么类型的？每个网络分布在什么位置？都一清二楚。届时每台路由器都使用一个树形结构算法，将自身设置为树根，利用SPF算法判断去往每个一个非直连网络的最优路径。最终将最优路径的路由加入路由表转发数据，可以理解为运行OSPF的路由器是先知道网络的拓扑，再基于拓扑计算路由。而不是听从邻居的建议使用相应邻居做下一跳转发数据去往相应目的网络

外部网关路由协议EGP

因特网的规模太大，使得自治系统之间路由选择非常困难。若源主机和目的主机处在不同的自制系统中(这两个自制系统可能使用不同的内部网关协议)，当数据报传到一个自制系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自制系统中

自治系统.png

自治系统AS2的BGP发言人通知主干网的BGP发言人：要达到网络N1，N2，N3和N4可经过AS2.主干网在受到这个通知后，就发出通知：要达到网络N1，N2，N3和N4可沿路径(AS1，AS2)。同理，主干网还可发出通知：要想到达网络N5，N6和N7可沿路径(AS1，AS3)

BGP发言人与会话

每一个自治系统的管理员要选择至少一个路由器作为该自治系统的“BGP发言人”。BGP发言人往往就是BGP边界路由器。BGP发言人之间要交换路由信息，就要建立BGP会话（session）

BGP发言人与会话.png

边界网关协议BGP

BGP是不同自治系统的路由器之间交换路由信息的协议。BGP是一种距离向量路由算法
建立了BGP会话连接的路由器又被称作对等体（peers or neighbors）。在BGP刚刚运行时，BGP的邻站是交换整个的BGP路由表。但以后只需要在发生变化时更新有变化的部分

对等体的连接有两种模式：
• IBGP（Internal BGP）：用来在AS内部完成BGP更新信息的交换，维护AS内部连通性
• EBGP（External BGP）：用来建立AS之间的路由器会话

边界网关协议BGP.png

BGP的特点

采用路径向量算法，路由信息中记录路径的轨迹。与距离矢量法非常类似，每个边界网关向邻居路由器广播到目的节点完整路径。力求寻找一条能够到达目的网络且比较好的路由，而并非寻找一条最佳路由

例如：
网关X可能发送到目的节点Z的路径如→：Path（X，Z） = X，Y1，Y2，Y3，......，Z
假设：网关X将它的路径送到网关W，W可能接受或者不接受X所提供的路径。如果W接收X发来的路径，则：Path（W，Z）= w，Path（X，Z）。注意：X可以通过控制是否广播某条路径来控制该路径的流量

BGP的4种消息类型

• 打开（Open）报文：用来与相邻的另一个BGP发言人建立关系
• 更新（Update）报文：用来发送某一路由的信息，以及列出要撤销的多条路由
• 保活（Keepalive）报文：用来确认打开报文和周期性地证实邻站关系（周期性地询问相邻站 点是否存在，如果相邻的站点撤销了，下面的路由就不再给这个站点发送数据了）
• 通知（Notification）报文：用来发送检测到的差错

RIP，OSPF和BGP的简单比较

RIP，OSPF和BGP的简单比较.png

三个协议的传递协议不同的原因
OSPF自身提供主从协商机制，可以保证可靠的传输，另外全网路由器保持着同样的一个链路状态数据库，当拓扑发生变化时，需要携带的变更信息较少，通过IP协议即可完成
RIP协议每周期需全网组播路由信息，路由信息数目较大，故使用UDP协议可提高效率
BGP为边界网关协议，因携带的路由信息较多，且可能跨不同网络传送路由信息，为保证可靠性，需使用TCP协议，可兼顾容量和可靠性