学步园

1.概述

     路由算法是用于获取路由表中的路由项目。它是路由选择协议的核心。

2.路由算法的分类

     从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来分，可以分为两类。

• 静态路由选择策略
• • 静态路由选择也叫非自适应路由选择，其特点是简单和开销较小，但不能适应网络变化
• 动态路由选择策略
• • 动态路由选择也叫自适应路由选择，特点是能适应网络变化，实现起来复杂，开销也比较大。

3.自治系统

     因特网将整个互联网划分成许多较小的自治系统，一般简称为AS。自治系统有以下特点：

• 自治系统有权决定自己的路由选择协议
• 所有的网络都属于一个行政单位管辖
• 所有的路由器在本自治系统内都必须是连通的

4.路由选择协议的分类

• 内部网关协议IGP
• • 即在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用的最多，如RIP和OSPF协议。
• 外部网关协议EGP
• • 若源站和目的站处在不相同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用外部网关协议将路由选择信息传递到另一个自治系统中。目前外部网关协议使用最多的是BGP-4.

5.RIP路由信息协议（Routing Information Protocol)

• 路由信息协议RIP是一种分布式的基于距离向量的路由选择协议，是因特网标准协议。
•  RIP协议将“距离”定义如下：
• • 从一路由器到直接连接的网络的距离定义为1，从一路由器到非直接链接的网络的距离定义为所经过的路由器加1。因此，直接链接的网络的距离定义为1。
  •  RIP允许一条路径最多只能包含15个路由器。因此距离的最大值为16，相当于不可达。可见RIP只适用于小型互联网。
• RIP的距离向量算法为（Bellman-Ford算法）（详情请谷歌or查阅算法导论）
• RIP协议报文格式：
• • RIP协议使用运输层的用户数据报UDP进行传送。

• • 命令字段：1表示请求路由信息，2表示请求路由信息的响应或未被请求而发出的路由更新协议
  • 必为0字段：用来四字节对齐
  • 地址族标识符：该字段用来标识所使用的地址协议
  • 路由标记：填入自治系统的编号，这是因为考虑到有可能收到本自治系统以外的路由选择信息。

6.内部网关协议OSPF

• OSPF开放最短路径优先协议（OpenShortestPathFirst)用于在单一自治系统（autonomous system,AS）内决策路由。是对链路状态路由协议的一种实现。OSPF使用了Dijkstra提出的最短路径算法。
• OSPF分组的格式

• • 版本：当前的版本号为2
  • 类型：可以是5种类型分组中的一种
  • • 类型1：问候分组（hello),用来发现和维持邻站的可达性
    • 类型2：数据库描述分组，向邻站给出自己的链路状态数据库中的所有链路状态项目摘要信息。
    • 类型3：链路状态请求分组，向对方请求发送某些链路状态项目的详细信息
    • 类型4：链路状态更新分组，用洪泛法对全网更新链路状态
    • 类型5：链路状态确认分组，对链路状态更新分组确认。
  • 分组长度：包括OSPF首部在内的分组长度，以字节为单位
  • 路由器标识符：标志发送该分组的路由器的接口IP地址
  • 区域标识符：分组属于的区域
  • 检验和：用来检测分组中的差错。
  • 鉴别类型：0（不用），1（口令8个字符）