1. 理想的路由算法 有关路由选择协议的几个基本概念 算法必须是正确的和完整的。 算法在计算上应简单。

Presentation on theme: "1. 理想的路由算法 有关路由选择协议的几个基本概念 算法必须是正确的和完整的。 算法在计算上应简单。"— Presentation transcript:

1 1. 理想的路由算法 4.7.1 有关路由选择协议的几个基本概念 算法必须是正确的和完整的。 算法在计算上应简单。
有关路由选择协议的几个基本概念 1. 理想的路由算法 算法必须是正确的和完整的。 算法在计算上应简单。 算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。 算法应具有稳定性。 算法应是公平的。 算法应是最佳的。

2 4.7.3 内部网关协议 OSPF (Open Shortest Path First)
4.7 因特网的路由选择协议（2） 内部网关协议 OSPF (Open Shortest Path First) 1. OSPF 协议的基本特点 “开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。 “最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法SPF OSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。 是分布式的链路状态协议。

3 OSPF协议的三个要点 向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法。
发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。 “链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。

4 Building Link State Packets
simple: just put in a sequence number and aging information. The hard part is when to build them. Practice shows that once an hour is often enough.

5 链路状态数据库(link-state database)
由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。 这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。 OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点。

6 OSPF 的区域(area) 为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫作区域。
每一个区域都有一个 32 位的区域标识符（用点分十进制表示）。 区域也不能太大，在一个区域内的路由器最好不超过 200 个。

7 OSPF 划分为两种不同的区域 至其他自治系统 自治系统 AS 主干区域 0.0.0.0 区域 0.0.0.1 区域 0.0.0.3
R1 R6 网 6 R3 R7 网 1 R5 R9 网 7 网 2 R4 R2 网 3 网 8 R8 网 4 网 5 区域 区域 区域

8 划分区域 划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。
在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。 OSPF 使用层次结构的区域划分。在上层的区域叫作主干区域(backbone area)。主干区域的标识符规定为 。主干区域的作用是用来连通其他在下层的区域。

9 主干路由器 至其他自治系统 自治系统 AS 主干区域 0.0.0.0 区域 0.0.0.1 区域 0.0.0.3 区域 0.0.0.2 R1
网 6 R3 R7 网 1 R5 R9 网 7 网 2 R4 R2 网 3 网 8 R8 网 4 网 5 区域 区域 区域

10 区域边界路由器 至其他自治系统 自治系统 AS 主干区域 0.0.0.0 区域 0.0.0.1 区域 0.0.0.3 区域 0.0.0.2
R1 R6 网 6 R3 R7 网 1 R5 R9 网 7 网 2 R4 R2 网 3 网 8 R8 网 4 网 5 区域 区域 区域

11 Hierarchical Routing（层次路由）
Problem: No routing algorithm discussed so far can scale: all of them require each router to know about all others, that is, too demanding with respect to memory capacity and processing power. Solution: Go for sub-optimal routes by introducing regions, and separate algorithms for intra-region and inter-region routing. Two or three levels will generally do.

12

13 OSPF 直接用 IP 数据报传送 OSPF 不用 UDP 而是直接用 IP 数据报传送。
数据报很短的另一好处是可以不必将长的数据报分片传送。分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。

14 OSPF 的其他特点 OSPF 对不同的链路可根据 IP 分组的不同服务类型 TOS 而设置成不同的代价。因此，OSPF 对于不同类型的业务可计算出不同的路由。 如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。这叫作多路径间的负载平衡。 所有在 OSPF 路由器之间交换的分组都具有鉴别的功能。 支持可变长度的子网划分和无分类编址 CIDR。 每一个链路状态都带上一个 32 位的序号，序号越大状态就越新。

15 OSPF 分组 位 8 16 31 版 本 类 型 分 组 长 度 路 由 器 标 识 符 区 域 标 识 符 检 验 和 鉴 别 类 型
8 16 31 版 本 类 型 分 组 长 度 路 由 器 标 识 符 区 域 标 识 符 检 验 和 鉴 别 类 型 鉴 别 鉴 别 24 字节 OSPF 分组首部 类型 1 至类型 5 的 OSPF 分组 IP数据报首部 OSPF 分组 IP 数据报

16 2. OSPF 的五种分组类型 类型1，问候(Hello)分组。用来发现和维持邻站的可达性。在两个路由器之间形成一个邻居关系。
类型2，数据库描述(Database Description)分组。向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息。 类型3，链路状态请求(Link State Request)分组。 类型4，链路状态更新(Link State Update)分组， 用洪泛法对全网更新链路状态。 类型5，链路状态确认(Link State Acknowledgment) 分组。

17 数据库描述（DBD）分组，大多用于数据库交换期间。第一个DBD分组用于选举主从关系和配置由主设备选举的最初的序列号。有着最大路由器ID的路由器变成主设备并且对数据库同步进行初始化。主路由器发送序列号，从路由器进行确认。在主从路由器选举出来之后，数据库同步过程开始了，在这个过程中，所有LSA的分组头都在邻居之间进行交换。 DBD分组中的字段： 　　接口MTU--这个字段包含有以字节为单位、可以通过相关联接口传送的最大数据的大小。这个选项从RFC2178起开始被添加。当通过虚链路发送分组时这个字段必须设置为0。 　　选项--这个字段的选项在上一节有关Hello分组的格式中已经被讨论过了。 　　I比特--当设置为1时，表示这是DBD交换中的第一个分组。 　　M比特--当设置为1时，表示后面将有更多的分组过来。 　　MS比特--用于主从设备。当这个比特设置为1时，表示路由器在DBD交换过程中是主设备，如果这个比特被设置为0，表示路由器是从设备。 　　DBD序列号--这个字段包含一个由主设备设置的唯一的值。这个序列号在数据库交换过程中使用。只有主设备才能增加序列号。 　　LSA头--这个字段由一个链路状态数据库头列表组成。

18 2. OSPF 的五种分组类型 类型1，问候(Hello)分组。 类型2，数据库描述(Database Description)分组。
类型3，链路状态请求(Link State Request)分组。向对方请求发送某些链路状态项目的详细信息。 类型4，链路状态更新(Link State Update)分组，用洪泛法对全网更新链路状态。是OSPF中最复杂、最核心的部分。链路状态更新分组有5种不同的链路状态。 类型5，链路状态确认(Link State Acknowledgment) 分组。 对链路更新分组的确认。

19 OSPF的基本操作 问候 确定可达性 问候 数据库描述 数据库描述 达到数据库的同步 数据库描述 数据库描述 链路状态请求 新情况下的同步
链路状态更新 链路状态确认

20 OSPF 的特点 每两个相邻的路由器每隔10秒要交换一次问候分组。若有40秒没有收到某个相邻路由器发来的问候分组，则可认为该路由器不可到达，应立即修改链路状态数据库，并重新计算路由表。 OSPF 还规定每隔一段时间，如 30 分钟，要刷新一次数据库中的链路状态。 由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF 协议要比距离向量协议 RIP 好得多。 OSPF 没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于 100 ms。

21 OSPF 使用的是可靠的洪泛法 t1 更新报文 R t2 t3 R t4 R ACK报文 R t
1 收到信息的下游路由器在转发信息时，要将其上游路由器除外。 2 在收到更新分组后要进行确认。 t1 t2 t3 t4 更新报文 R R R ACK报文 t R

22 指定的路由器 (designated router)
多点接入的局域网采用了指定的路由器的方法，使广播的信息量大大减少。 指定的路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。

23 Thanks！