因特网的路由选择协议

路由选择协议

1. 理想路由算法
   • 算法是正确的，完整的
   • 在计算上简单
   • 自适应性
   • 稳定性
   • 公平的
   • 最佳的
2. 分层次的路由选择协议
   • 因特网采用自适应，分布式路由选择协议
   • 两大类：内部网关协议IGP和外部网关协议EGP
   • IGP(Interior Gateway Protocol)：包括RIP和OSPF等
   • EGP(External Gateway Protocol)：目前使用BGP

内部网关协议RIP（Routing Information Protocal）

工作原理

• 路由信息协议，基于距离向量的路由选择协议，优点是简单
• 从一路由器到直接连接的网络的距离定义为1，距离也称为跳数
• 一条路径最多包含15个路由器，16代表不可达，因此用于小型互联网
• 只选择最短路由，哪怕有一条高速但多路由器的路由
• 分布式路由选择协议，不断地和其他路由器交换信息
• 协议特点
  1. 仅和相邻路由器交换信息
  2. 交换的信息是当前本路由知道的全部信息（路由表）
  3. 按固定的时间间隔交换信息（30秒）

距离向量算法

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

1. 对地址为X的路由器发来的RIP报文，先修改报文的所有项目：“下一跳”改为X，所有距离加一。每个项目有三个数据：到达目的网络N，距离d，下一跳路由器是X
2. 对修改后的每一个项目

• 如果原来的路由表没有目的网络N，加入路由表
• 否则如果有目的网络，下一跳地址也是X，更新路由表
• 否则如果有目的网络，下一跳不是X，查看距离，更新路由表

1. RIP协议使得从每一个路由器到每一个目的网络的路由都是最短的

   RIP协议的报文格式

• RIP2是新版本，改进性能，支持CIDR和变长子网掩码，多播
• 使用运输层的用户数据报UDP进行传送（UDP的端口520）
• 报文由首部和路由组成
• 首部4字节，包括命令，版本，和一个0保证四字节对齐
• 路由部分由若干个路由信息组成，20字节。包含地址族标识符，路由标记，后面是网络地址，子网掩码，下一跳路由地址，距离。重复出现最多25个
• 问题：网络出现故障时，需要较长时间才能传送到所有路由器（栗子很有趣）
• 特点：好消息传的快，坏消息传得慢
• 优点：实现简单，开销较小
• 缺点：限制网络规模；随着规模扩大，开销增加
• 规模小的网络适合

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

协议基本特点

• 开放最短路径优先
• 使用分布式的链路状态协议
• 与RIP的不同之处：
  1. 用洪泛法（flooding）向本自治系统中的所有路由器发送信息
  2. 发送的信息是与本路由器相邻的所有路由器的链路状态。链路状态还包括“度量”（metric）
  3. 只有当链路状态发生变化时，才使用洪泛法发送信息
• 所有路由器都能建立链路状态数据库，也就是全网的拓扑结构图
• 每一个路由器使用链路状态数据库中的数据构造自己的路由表（迪杰斯特拉算法）
• OSPF会将一个自治系统划分为若干个更小的范围，叫做区域，每个区域有32位的标识符
• 划分区域的好处是洪泛法交换信息的范围局限于一个区域，减少通信量
• OSPF使用层次结构的划分
  1. 区域边界路由器
  2. 主干路由器
  3. 自治系统边界路由器
• 使用IP数据报传送，很短
• 特点
  1. 允许管理员给每条路由指定代价
  2. 如果有多条代价相同的路径，可以将通信量分配给这几条路径。即负载均衡
  3. 所有在OSPF路由器之间交换的分组都有鉴别的功能
  4. 支持可变长的子网划分和CIDR
  5. 每一个链路状态都有一个32位的序号，增长速率不超过5秒1次。
  6. 只要一个路由器的链路状态发生变化，就用洪泛法向全网更新链路状态
  7. 每30分钟刷新一次数据库的链路状态

五种分组类型

1. 问候分组，发现和维持邻站的可达性
2. 数据库描述分组，给邻站自己的链路状态数据库中的链路状态项目
3. 链路状态请求分组，向对方请求链路状态项目
4. 链路状态更新分组，洪泛法，最复杂，最核心的部分
5. 链路状态确认分组

外部网关协议BGP

• 使用原因
  1. 因特网规模太大，使得AS之间路由选择太难
  2. AS之间的路由选择必须考虑有关策略
• 每一个自治系统的管理员要选择至少一个路由器作为“BGP发言人”。两个BGP发言人通过一个共享网络连接在一起，发言人一般是BGP边界路由器
• 要交换路由信息，先建立TCP连接，在此连接上交换BGP报文以建立BGP会话
• 使用TCP连接能提供可靠的服务，简化了路由选择协议
• 使用TCP连接交换路由信息的两个BGP发言人，彼此成为对方的邻站或对等站
• 每一个BGP发言人处理必须运行BGP协议外，还必须运行内部网关协议
• 交换的信息是到达某个网络所要经过的一系列自治系统
• BGP支持无分类域间路由选择CIDR，因此路由表包括网络前缀，下一跳路由器，以及到达该面对网络所要经过的自治系统序列
• 四种报文
  1. OPEN报文：建立关系，通信初始化
  2. UPDATE报文，报告路由信息，列出要撤销的路由
  3. KEEPALIVE报文，周期性证实邻站连通性
  4. NOTIFICATION报文，发送检测到的差错
• 报文过程
  1. 先发送OPEN报文
  2. 如果接受，用KEEPALIVE相应
  3. 然后周期性地交换KEEPALIVE报文
  4. UPDATE报文可以撤销通知过的路由，也可以增加新的路由；撤销可以多条，增加只能一条
• 能解决“坏消息传播得慢”

路由器的构成

路由器的结构

• 多个输入端口和多个输出端口的专用计算机
• 任务是转发分组
• 两部分结构：路由选择和分组转发
• 路由选择
  1. 核心构件是路由选择处理机
  2. 任务是根据所选定的路由选择协议构造路由表，定期和相邻路由器交换路由信息而不断更新和维护路由表
• 分组转发
  1. 由交换结构，输入端口和输出端口组成
  2. 交换结构：根据转发表对分组进行处理，将某个输入端口进入的分组从一个合适的输出端口转发出去
  3. 输入输出各有三个模块：物理层，数据链路层，网络层
  4. 网络层中有缓冲区