9-路由协议概述

1、第第9章章 路由协议概述路由协议概述主要内容主要内容1、引言、引言2、路由表的建立与维护、路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现基本要求基本要求掌握路由表建立和维护的两种方式：静态配置和动态交换掌握路由表建立和维护的两种方式：静态配置和动态交换路由信息；路由信息；掌握两种路由更新算法掌握两种路由更新算法:矢量距离算法和矢量距离算法和SPF算法算法;掌握掌握Internet的路由体系结构，特别是自治系统的路由体系结构，特别是自治系统AS的概念的概念和作用和作用.学习内容学习内容1、引言、

2、引言2、路由表的建立与维护、路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现问题的提出问题的提出 问题：问题：（1）为什么选择这条路径？）为什么选择这条路径？（2）路由器的路由表如何获取）路由器的路由表如何获取?（3）假设）假设R2与与R4的连接断掉，如何通知的连接断掉，如何通知R1？（4）在）在Internet中，是否每个路由器都必须了解其它路由器中，是否每个路由器都必须了解其它路由器的情况？的情况？H1H2R1R5R2R3R4路径：路径：H1-R1-R2-R4-H2学习内容学习内容1、引言、

3、引言2、路由表的建立与维护、路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现路由表的建立和维护路由表的建立和维护 v静态配置：管理员静态配置：管理员手工手工配置和更新路由表配置和更新路由表优点：节省路由器的处理时间、存储空间以及网络带宽优点：节省路由器的处理时间、存储空间以及网络带宽缺陷：对于链路故障及拓扑结构变化的响应速度慢缺陷：对于链路故障及拓扑结构变化的响应速度慢两种方式：静态配置两种方式：静态配置 和和 动态路由交换动态路由交换H1H2R1R5R2R3R4适用环境：拓扑相对稳定，路由器个

4、数较少适用环境：拓扑相对稳定，路由器个数较少v 利用利用路由协议路由协议交换路由信息，并根据拓扑结构的变化动态更交换路由信息，并根据拓扑结构的变化动态更新路由表新路由表优点：自动适应链路故障及拓扑结构的变化优点：自动适应链路故障及拓扑结构的变化缺陷：耗费网络带宽、路由器的处理时间和存储空间缺陷：耗费网络带宽、路由器的处理时间和存储空间适用环境：路由器较多的大规模网络适用环境：路由器较多的大规模网络H1H2R1R5R2R3R4动态路由信息交换动态路由信息交换学习内容学习内容1、引言、引言2、路由表的建立与维护、路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由

5、体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现什么是选路？什么是选路？1230111到达分组首部的值到达分组首部的值选路算法选路算法本地转发表本地转发表首部值首部值输出链路输出链路01000101011110013221 集中式集中式 分布式分布式转发表的配置方法：转发表的配置方法： 静态：人工配置静态：人工配置 动态：选路协议动态：选路协议选路涉及到的选路涉及到的2个关键问题个关键问题（1）路径存在性）路径存在性 （2）路径最优性）路径最优性路径存在性路径存在性路由器采用路由器采用“下一跳下一跳”选路；选路；路由表的两个普遍特点：路由表的两个普遍特点：（1）路由表中不包含到达

6、所有目的地的路由）路由表中不包含到达所有目的地的路由（2）路由表中存在默认路由）路由表中存在默认路由这表明：这表明：（1）单个路由器为连接关系所做的贡献是局部的）单个路由器为连接关系所做的贡献是局部的（2）所有路由器组成的系统是完备的）所有路由器组成的系统是完备的问题：如何确定一条路径是最优的？问题：如何确定一条路径是最优的？ 选择不同的度量指标：选择不同的度量指标：（1）带宽）带宽 （2）延迟）延迟 （静态指标）（静态指标） （3）负载）负载 （4）可靠性）可靠性 （动态指标）（动态指标） （5）跳数）跳数（6）其它指标，比如代价）其它指标，比如代价理想情况：综合利用以上各指标理想情况：综合

7、利用以上各指标缺陷：选择动态度量要素可能会造成路由震荡缺陷：选择动态度量要素可能会造成路由震荡实现：简单的算法仅考虑一个要素，复杂的则综合考虑（如实现：简单的算法仅考虑一个要素，复杂的则综合考虑（如DUAL）最常用的：基于跳数最常用的：基于跳数路由度量路由度量学习内容学习内容1、引言、引言2、路由表的建立与维护、路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现选路算法选路算法 1. 非自适应算法非自适应算法 不考虑当前的拓扑结构和网络流量不考虑当前的拓扑结构和网络流量 设置设置中心路由器中心路由

8、器，由管理员预先为每个路由器设置路由表，由管理员预先为每个路由器设置路由表 拓扑发生变化时，由管理员操作中心路由器，更新路由表拓扑发生变化时，由管理员操作中心路由器，更新路由表 适用于规模小，拓扑结构变化少的网络适用于规模小，拓扑结构变化少的网络1.非自适应非自适应 2.自适应自适应(1) 矢量矢量-距离算法距离算法 (2) 链路状态算法链路状态算法(1) 矢量距离路由算法矢量距离路由算法(Bellman、Bellman-Ford和和Ford-Fulkerson算法算法 ) 思想：以思想：以跳数跳数作为度量值，通过交换路由表，计算出所有已知的作为度量值，通过交换路由表，计算出所有已知的最短路由

9、最短路由，并更新路由表。，并更新路由表。自适应算法自适应算法-矢量距离路由算法矢量距离路由算法表项格式：表项格式： 跳数：从源站到目的站间所经过的路由器数目。跳数：从源站到目的站间所经过的路由器数目。 如何建立路由表如何建立路由表? 初始化：初始化：路由器启动时，对每个直接相连的网络生成一个路由器启动时，对每个直接相连的网络生成一个表项，表项，hop数都为数都为0。 路由交换：路由器周期性向相邻路由器广播自己的整个路路由交换：路由器周期性向相邻路由器广播自己的整个路由表。由表。路由表更新路由表更新迭代更新，直至获得整个迭代更新，直至获得整个AS的路由信息。的路由信息。1 1 2 1 3 1 F

10、EDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 一开始，各路由表只有到相邻路由器的信息一开始，各路由表只有到相邻路由器的信息网网 3网网 2网网 4网网 6网网 5网网 1“4”表示表示“从本路由从本路由器到网器到网 4”“1”表示表示“距离是距离是 1”“ ”表示表示“直接交付直接交付”1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网网 3网网 2网网 4网网 6网网 5网网 11 1 2 1 3 1 4

11、 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后A 说：说：“我到网我到网 1 的距离是的距离是 1。”因此因此 B 现在也可以到网现在也可以到网 1，距离是距离是 2，经过，经过 A。”1 1 2 1 3 1 4 1 6 1 1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网网 3网网 2网网 4网网 6网网 5网网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后A 说：

12、说：“我到网我到网 2 的距离是的距离是 1。”因此因此 B 现在也可以到网现在也可以到网 2，距离是距离是 2，经过，经过 A。”1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网网 3网网 2网网 4网网 6网网 5网网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后A 说：说：“我到网我到网 3 的距离是的距离是 1。”但但 B 没有必要绕道经过路由器没有必要绕道经过路由器 A再到达网再到达

13、网 3，因此这一项目不变。，因此这一项目不变。1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网网 3网网 2网网 4网网 6网网 5网网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后C 说：说：“我到网我到网 4 的距离是的距离是 1。”但但 B 没有必要绕道经过路由器没有必要绕道经过路由器 C再到达网再到达网 4，因此这一项目不变。，因此这一项目不变。1 1 2 1 3 1 FEDCBA5

14、1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网网 3网网 2网网 4网网 6网网 5网网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后更新后C 说：说：“我到网我到网 6 的距离是的距离是 1。”因此因此 B 现在也可以到网现在也可以到网 6，距离是距离是 2，经过，经过 C。”最终所有的路由器的路由表都更新了最终所有的路由器的路由表都更新了FEDCBA1 1 2 1 3 1 4 2 B5 2 E6 3 B1 1 2 2 A3 2 A4

15、 3 A5 1 6 2 F1 2 E2 2 D3 3 C4 2 C5 1 6 1 1 3 B2 3 B3 2 B4 1 5 2 F6 1 网网 2网网 6网网 5网网 1网网 3网网 41 2 A2 1 3 2 A4 3 A5 1 6 2 F1 2 A2 2 A3 1 4 1 5 3 C6 2 C例子例子 目的网络目的网络 下一个路由器下一个路由器 到目的地的跳数到目的地的跳数 wA2yB2 zB7x-1.wxyzACDB在路由器在路由器D中的选路表中的选路表例子例子( (续续) ) 目的网络目的网络 下一个路由器下一个路由器 到目的地的跳数到目的地的跳数 wA2yB2 zB A7 5x-1.

16、D的选路表的选路表wxyzACDB目的地目的地 下一个下一个 跳跳 w - - x - - z C 4 . .D从从A收到通告收到通告路由表的更新路由表的更新 路由器每收到一个邻站的路由表，即更新自己的路由路由器每收到一个邻站的路由表，即更新自己的路由表。表。(假设假设K收到收到J的路由表的路由表) (1) K不知道目的站，则加入不知道目的站，则加入 ； (2) 有通过有通过J的更短路，则替换的更短路，则替换 ； (3) 原下站为原下站为J的距离有变化，则修改的距离有变化，则修改 。例：例：目的站目的站距离距离下一跳下一跳网络网络10直接直接网络网络20直接直接网络网络48路由器路由器L网络网

17、络175路由器路由器M网络网络246路由器路由器J网络网络302路由器路由器Q网络网络422路由器路由器J目的站目的站距离距离网络网络12网络网络43网络网络176网络网络214网络网络245网络网络3010网络网络423目的站目的站距离距离下一跳下一跳网络网络10直接直接网络网络20直接直接网络网络44J（替换）（替换）网络网络175路由器路由器M网络网络246路由器路由器J网络网络302路由器路由器Q网络网络424J（修改）（修改）网络网络215J（增加）（增加）路由器每收到一路由器每收到一个邻站的路由表，个邻站的路由表，即更新自己的路即更新自己的路由表。由表。(假设假设K收收到到J的路由

18、表的路由表) (1) K不知道目不知道目的站，则加入的站，则加入 ； (2) 有通过有通过J的的更短路，则替换更短路，则替换 ； (3) 原下站为原下站为J的距离有变化，的距离有变化，则修改则修改 。关于距离向量算法的说明关于距离向量算法的说明优点：优点：CPU和内存开销小和内存开销小缺点：缺点：容易引发路由更新不一致问题：路由信息传播速度容易引发路由更新不一致问题：路由信息传播速度缓慢，计算结果容易出错。缓慢，计算结果容易出错。消耗带宽较多。消耗带宽较多。适用于规模不太大的、拓扑结构变化不频繁的环境。适用于规模不太大的、拓扑结构变化不频繁的环境。（2 2）链路状态路由算法）链路状态路由算法

19、- - 最短路径优先最短路径优先SPF 思想：思想：通过交换链路状态，让通过交换链路状态，让AS中的每个路由器都有一张该中的每个路由器都有一张该AS的网络拓扑结构图。的网络拓扑结构图。节点：路由器；节点：路由器；边：链路边：链路;使用使用Dijkstra算法求最短路径，计算该路由器到其它目算法求最短路径，计算该路由器到其它目的站的最短路径，然后更新路由表。的站的最短路径，然后更新路由表。优点：优点： 每个路由器使用相同的原始数据，具有每个路由器使用相同的原始数据，具有良好的收敛性良好的收敛性。 每个路由器的链路状态报文大小取决于直接链路的数量，每个路由器的链路状态报文大小取决于直接链路的数量，

20、具有具有较好的规模可扩展性较好的规模可扩展性。步骤步骤 链路状态检测：向链路状态检测：向直接相邻的直接相邻的路由器周期性发测试报文，路由器周期性发测试报文，检查路由器状态，并按检查路由器状态，并按“n中取中取k”原则进行状态检查原则进行状态检查 。 路由信息广播：路由器周期性地（或某链路状态变化时）路由信息广播：路由器周期性地（或某链路状态变化时）广播广播它所连接的各个链路状态它所连接的各个链路状态(洪泛洪泛)。 路由表更新：收到链路状态的路由器更新自己的网络拓扑路由表更新：收到链路状态的路由器更新自己的网络拓扑图，并用图，并用Dijkstra算法计算最短路径算法计算最短路径 。关于链路状态算

21、法的说明关于链路状态算法的说明缺点：缺点：需要较高的需要较高的CPU性能性能优点：优点：收敛性好收敛性好规模可扩展性好规模可扩展性好学习内容学习内容1、引言、引言2、路由表的建立与维护、路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现Internet路由体系的发展路由体系的发展 路由体系的内容：如何对路由体系的内容：如何对Internet中的路由器进行划分、中的路由器进行划分、管理和控制，以便有效地交换路由信息。管理和控制，以便有效地交换路由信息。路由体系的重要性：决定了互联网的运行效率。路由体

22、系的重要性：决定了互联网的运行效率。Internet路由体系的发展：路由体系的发展：（1）最早的核心路由体系）最早的核心路由体系（2）随后的对等主干路由体系）随后的对等主干路由体系（3）当前的自治系统路由体系）当前的自治系统路由体系 核心体系结构（分层树型）核心体系结构（分层树型）ARPANET主干网主干网本地网络本地网络2本地网络本地网络2本地网络本地网络mk1k2kn核心路由器核心路由器G1G2Gk外围路由器外围路由器 核心路由器核心路由器: 构成核心系构成核心系统，集中管理，提供到所统，集中管理，提供到所有目的地的路由。有目的地的路由。 外围路由器外围路由器: 为外出数据为外出数据报提供

23、默认路由报提供默认路由, 发往某核发往某核心网关心网关; 将核心路由器传入将核心路由器传入的数据报投递到直连的物的数据报投递到直连的物理网络。理网络。Internet的对等主干结构的对等主干结构 契机：契机：NSFNET的引入，网络规模扩大的引入，网络规模扩大R2RnR1ARPANET主干网主干网主机主机2主机主机1NSFNET主干网主干网主机主机4主机主机3选路模式：选路模式： 各主干网内部按核心结构方式进行选路各主干网内部按核心结构方式进行选路 各核心各核心路由器路由器拥有对另一部分的默认路由。拥有对另一部分的默认路由。 对等主干网存在的问题对等主干网存在的问题 两主干间多重接入，造成选路

24、困难。两主干间多重接入，造成选路困难。 具有非法目的地址的数据报形成选路回路具有非法目的地址的数据报形成选路回路核心核心C1核心核心C2核心核心C1内网点的内网点的非法目的分组非法目的分组x到核心到核心C2的的默认路由默认路由P1到核心到核心C1的的默认路由默认路由P2目前的目前的Internet结构（网状）结构（网状） Internet主干网主干网NAP1NAP2NAPnNSP1NSP2NSPNISP1ISP1ISP1核心层核心层分布层分布层接入层接入层如何限制选路信息的无限传播？如何限制选路信息的无限传播？如何限制选路信息的传播如何限制选路信息的传播? 参与交换路由信息的路由器群组规模不能

25、太大。参与交换路由信息的路由器群组规模不能太大。指导原则：指导原则： （1）广域网范围）广域网范围12个路由器个路由器 （2）若干局域网范围）若干局域网范围60个路由器。个路由器。说明说明:(1)AS自治的主要内容是选路自治自治的主要内容是选路自治, AS可自由地选择路由算法；可自由地选择路由算法； (2)AS必须严格界定，并被赋予全局唯一的自治系统号必须严格界定，并被赋予全局唯一的自治系统号(NIC分配分配)； (3)主干网络本身也构成一个主干网络本身也构成一个AS (教育网教育网AS4538)。AS1R1主干网主干网(AS)ASnInternet中的自治系统结构中的自治系统结构AS(自治系统自治系统)：出于选路目的，处于一个管理机构控制之下：出于选路目的，处于一个管理机构控制之下的的一组网络和路由器一