9-路由协议概述课件

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

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

静态配置：管理员手工配置和更新路由表优点：节省路由器的处理时间、存储空间以及网络带宽缺陷：对于链路故障及拓扑结构变化的响应速度慢两种方式：静态配置和动态路由交换H1H2R1R5R2R3R4适用环境：拓扑相对稳定，路由器个数较少路由表的建立和维护静态配置：管理员手工配置和更新路由表两种7利用路由协议交换路由信息，并根据拓扑结构的变化动态更新路由表优点：自动适应链路故障及拓扑结构的变化缺陷：耗费网络带宽、路由器的处理时间和存储空间适用环境：路由器较多的大规模网络H1H2R1R5R2R3R4动态路由信息交换利用路由协议交换路由信息，并根据拓扑结构的变化动态更新路由8学习内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现学习内容1、引言9什么是选路？1230111到达分组首部的值选路算法本地转发表首部值输出链路01000101011110013221

集中式分布式转发表的配置方法：静态：人工配置动态：选路协议什么是选路？1230111到达分组首部的值选路算法本地转发表10选路涉及到的2个关键问题（1）路径存在性（2）路径最优性选路涉及到的2个关键问题（1）路径存在性11路径存在性路由器采用“下一跳”选路；路由表的两个普遍特点：（1）路由表中不包含到达所有目的地的路由（2）路由表中存在默认路由这表明：（1）单个路由器为连接关系所做的贡献是局部的（2）所有路由器组成的系统是完备的路径存在性路由器采用“下一跳”选路；12问题：如何确定一条路径是最优的？选择不同的度量指标：（1）带宽（2）延迟（静态指标）（3）负载（4）可靠性（动态指标）（5）跳数（6）其它指标，比如代价理想情况：综合利用以上各指标缺陷：选择动态度量要素可能会造成路由震荡实现：简单的算法仅考虑一个要素，复杂的则综合考虑（如DUAL）最常用的：基于跳数路由度量问题：如何确定一条路径是最优的？（1）带宽13学习内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现学习内容1、引言14选路算法

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

--矢量距离路由算法表项格式：<目的网络，距离（跳数hop），下一站>跳数：从源站到目的站间所经过的路由器数目。

(1)矢量-距离算法(2)链路状态算法(1)16如何建立路由表?

初始化：路由器启动时，对每个直接相连的网络生成一个表项，hop数都为0。

路由交换：路由器周期性向相邻路由器广播自己的整个路由表。路由表更新迭代更新，直至获得整个AS的路由信息。如何建立路由表?初始化：路由器启动时，对每个直接相连的网络17112131FEDCBA51612151314141611151一开始，各路由表只有到相邻路由器的信息网

3网

2网

4网

6网

5网

1“4”表示“从本路由器到网

4”“1”表示“距离是

1”“”表示“直接交付”11FEDCBA5121318112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后A说：“我到网1的距离是1。”因此B现在也可以到网1，距离是2，经过A。”112131416111FEDCBA5121319112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后A说：“我到网2的距离是1。”因此B现在也可以到网2，距离是2，经过A。”11FEDCBA5121320112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后A说：“我到网3的距离是1。”但

B

没有必要绕道经过路由器

A再到达网

3，因此这一项目不变。11FEDCBA5121321112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后C说：“我到网4的距离是1。”但

B

没有必要绕道经过路由器

C再到达网

4，因此这一项目不变。11FEDCBA5121322112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后C说：“我到网6的距离是1。”因此B现在也可以到网6，距离是2，经过C。”11FEDCBA5121323最终所有的路由器的路由表都更新了FEDCBA11213142B52E63B1122A32A43A5162F12E22D33C42C516113B23B32B4152F61网2网6网5网1网3网412A2132A43A5162F12A22A314153C62C最终所有的路由器的路由表都更新了FEDCBA11124例子

目的网络 下一个路由器 到目的地的跳数

w

A 2

y B 2

z B 7

x -- 1 …. …. ....wxyzACDB在路由器D中的选路表…例子目的网络 下一个路由器25例子(续)

目的网络 下一个路由器到目的地的跳数

w

A 2

y

B 2

z

BA 75

x

-- 1

…. …. ....D的选路表wxyzACDB目的地下一个跳

w

--

x

--z

C

4

…. …...D从A收到通告…例子(续)目的网络 下一个26路由表的更新路由器每收到一个邻站的路由表，即更新自己的路由表。(假设K收到J的路由表)(1)K不知道目的站，则加入；(2)有通过J的更短路，则替换；(3)原下站为J的距离有变化，则修改。路由表的更新路由器每收到一个邻站的路由表，即更新自己27例：目的站距离下一跳网络10直接网络20直接网络48路由器L网络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的路由表)(1)K不知道目的站，则加入；(2)有通过J的更短路，则替换；(3)原下站为J的距离有变化，则修改。例：目的站距离下一跳网络10直接网络20直接网络48路由器L28关于距离向量算法的说明优点：CPU和内存开销小缺点：容易引发路由更新不一致问题：路由信息传播速度缓慢，计算结果容易出错。消耗带宽较多。适用于规模不太大的、拓扑结构变化不频繁的环境。关于距离向量算法的说明优点：29（2）链路状态路由算法

-最短路径优先SPF

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

-最短路径优先SPF思想：30步骤①链路状态检测：向直接相邻的路由器周期性发测试报文，检查路由器状态，并按“n中取k”原则进行状态检查。②路由信息广播：路由器周期性地（或某链路状态变化时）广播它所连接的各个链路状态(洪泛)。③路由表更新：收到链路状态的路由器更新自己的网络拓扑图，并用Dijkstra算法计算最短路径。步骤①链路状态检测：向直接相邻的路由器周期性发测试报文，检31关于链路状态算法的说明缺点：需要较高的CPU性能优点：收敛性好规模可扩展性好关于链路状态算法的说明缺点：32学习内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现学习内容1、引言33Internet路由体系的发展

路由体系的内容：如何对Internet中的路由器进行划分、管理和控制，以便有效地交换路由信息。路由体系的重要性：决定了互联网的运行效率。Internet路由体系的发展：（1）最早的核心路由体系（2）随后的对等主干路由体系（3）当前的自治系统路由体系Internet路由体系的发展路由体系的内容：如何对Int34核心体系结构（分层树型）ARPANET主干网本地网络2本地网络2本地网络mk1k2kn核心路由器G1G2Gk外围路由器核心路由器:构成核心系统，集中管理，提供到所有目的地的路由。外围路由器:为外出数据报提供默认路由,发往某核心网关;将核心路由器传入的数据报投递到直连的物理网络。核心体系结构（分层树型）ARPANET主干网本地网络2本地网35Internet的对等主干结构

契机：NSFNET的引入，网络规模扩大R2RnR1ARPANET主干网主机2主机1NSFNET主干网主机4主机3选路模式：①各主干网内部按核心结构方式进行选路②各核心路由器拥有对另一部分的默认路由。

Internet的对等主干结构契机：NSFNET的引入，网36对等主干网存在的问题①两主干间多重接入，造成选路困难。②具有非法目的地址的数据报形成选路回路核心C1核心C2核心C1内网点的非法目的分组x到核心C2的默认路由P1到核心C1的默认路由P2对等主干网存在的问题①两主干间多重接入，造成选路困难。核心37目前的Internet结构（网状）

Internet主干网NAP1NAP2NAPnNSP1NSP2NSPNISP1ISP1ISP1………………核心层分布层接入层目前的Internet结构（网状）Internet主干网N38如何限制选路信息的无限传播？如何限制选路信息的传播?参与交换路由信息的路由器群组规模不能太大。指导原则：（1）广域网范围≤12个路由器（2）若干局域网范围≤60个路由器。如何限制选路信息的无限传播？如何限制选路信息的传播?39说明:(1)AS自治的主要内容是选路自治,AS可自由地选择路由算法；(2)AS必须严格界定，并被赋予全局唯一的自治系统号(NIC分配)；(3)主干网络本身也构成一个AS(教育网AS4538)。AS1R1主干网(AS)ASn……Internet中的自治系统结构AS(自治系统)：出于选路目的，处于一个管理机构控制之下的一组网络和路由器。限制了路由信息传播的规模增强了扩展性说明:AS1R1主干网(AS)ASn……Internet中的40（1）AS内部：IGP，比如RIP、OSPF、IS-IS等；（2）AS之间：EGP，最常用的是BGP;（3）EGP通常是一种可达性协议。R1R2R3AS1AS2AS3IGP1IGP2IGP3EGP12EGP13EGP23Internet的路由管理模式（1）AS内部：IGP，比如RIP、OSPF、IS-IS等；41举例3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP会话iBGP会话138.16.64/24138.16.65/24138.16.66/24138.16.67/24138.16.64/22聚合当AS2向AS1通告一个CIDR前缀,并承诺它将转发任何指向该前缀的数据报，AS2能够在它的通告中聚合前缀举例3b1d3a1c2aAS3AS1AS21a2c2b1b342小结路由表配置方式有:静态和动态两种.选路问题涉及路径存在性和路径最优性两个问题.路由度量要素主要有:带宽,延迟,负载,可靠性,跳数.路由算法包括:非自适应路由算法和自适应路由算法.自适应路由算法包括：向量距离算法和链路状态算法.Internet路由体系经历了核心路由体系,对等主干网路由体系和自治系统路由体系三个发展阶段.自治系统路由体系便于管理和控制.小结路由表配置方式有:静态和动态两种.43课堂作业P121，8题课堂作业P121，8题44课后作业课后认真看教材,查阅参考书相应部分的内容。书面作业：P121，3,10,12题课后作业课后认真看教材,查阅参考书相应部分的内容。45第9章路由协议概述——《网络协议分析》第9章路由协议概述——《网络协议分析》46主要内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现主要内容1、引言47基本要求掌握路由表建立和维护的两种方式：静态配置和动态交换路由信息；掌握两种路由更新算法:矢量距离算法和SPF算法;掌握Internet的路由体系结构，特别是自治系统AS的概念和作用.基本要求掌握路由表建立和维护的两种方式：静态配置和动态交换路48学习内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现学习内容1、引言49问题的提出

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

静态配置：管理员手工配置和更新路由表优点：节省路由器的处理时间、存储空间以及网络带宽缺陷：对于链路故障及拓扑结构变化的响应速度慢两种方式：静态配置和动态路由交换H1H2R1R5R2R3R4适用环境：拓扑相对稳定，路由器个数较少路由表的建立和维护静态配置：管理员手工配置和更新路由表两种52利用路由协议交换路由信息，并根据拓扑结构的变化动态更新路由表优点：自动适应链路故障及拓扑结构的变化缺陷：耗费网络带宽、路由器的处理时间和存储空间适用环境：路由器较多的大规模网络H1H2R1R5R2R3R4动态路由信息交换利用路由协议交换路由信息，并根据拓扑结构的变化动态更新路由53学习内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现学习内容1、引言54什么是选路？1230111到达分组首部的值选路算法本地转发表首部值输出链路01000101011110013221

集中式分布式转发表的配置方法：静态：人工配置动态：选路协议什么是选路？1230111到达分组首部的值选路算法本地转发表55选路涉及到的2个关键问题（1）路径存在性（2）路径最优性选路涉及到的2个关键问题（1）路径存在性56路径存在性路由器采用“下一跳”选路；路由表的两个普遍特点：（1）路由表中不包含到达所有目的地的路由（2）路由表中存在默认路由这表明：（1）单个路由器为连接关系所做的贡献是局部的（2）所有路由器组成的系统是完备的路径存在性路由器采用“下一跳”选路；57问题：如何确定一条路径是最优的？选择不同的度量指标：（1）带宽（2）延迟（静态指标）（3）负载（4）可靠性（动态指标）（5）跳数（6）其它指标，比如代价理想情况：综合利用以上各指标缺陷：选择动态度量要素可能会造成路由震荡实现：简单的算法仅考虑一个要素，复杂的则综合考虑（如DUAL）最常用的：基于跳数路由度量问题：如何确定一条路径是最优的？（1）带宽58学习内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现学习内容1、引言59选路算法

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

--矢量距离路由算法表项格式：<目的网络，距离（跳数hop），下一站>跳数：从源站到目的站间所经过的路由器数目。

(1)矢量-距离算法(2)链路状态算法(1)61如何建立路由表?

初始化：路由器启动时，对每个直接相连的网络生成一个表项，hop数都为0。

路由交换：路由器周期性向相邻路由器广播自己的整个路由表。路由表更新迭代更新，直至获得整个AS的路由信息。如何建立路由表?初始化：路由器启动时，对每个直接相连的网络62112131FEDCBA51612151314141611151一开始，各路由表只有到相邻路由器的信息网

3网

2网

4网

6网

5网

1“4”表示“从本路由器到网

4”“1”表示“距离是

1”“”表示“直接交付”11FEDCBA5121363112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后A说：“我到网1的距离是1。”因此B现在也可以到网1，距离是2，经过A。”112131416111FEDCBA5121364112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后A说：“我到网2的距离是1。”因此B现在也可以到网2，距离是2，经过A。”11FEDCBA5121365112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后A说：“我到网3的距离是1。”但

B

没有必要绕道经过路由器

A再到达网

3，因此这一项目不变。11FEDCBA5121366112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后C说：“我到网4的距离是1。”但

B

没有必要绕道经过路由器

C再到达网

4，因此这一项目不变。11FEDCBA5121367112131FEDCBA51612151314141611151路由器B收到相邻路由器A和C的路由表网

3网

2网

4网

6网

5网

1112131416112A22A314162C更新后C说：“我到网6的距离是1。”因此B现在也可以到网6，距离是2，经过C。”11FEDCBA5121368最终所有的路由器的路由表都更新了FEDCBA11213142B52E63B1122A32A43A5162F12E22D33C42C516113B23B32B4152F61网2网6网5网1网3网412A2132A43A5162F12A22A314153C62C最终所有的路由器的路由表都更新了FEDCBA11169例子

目的网络 下一个路由器 到目的地的跳数

w

A 2

y B 2

z B 7

x -- 1 …. …. ....wxyzACDB在路由器D中的选路表…例子目的网络 下一个路由器70例子(续)

目的网络 下一个路由器到目的地的跳数

w

A 2

y

B 2

z

BA 75

x

-- 1

…. …. ....D的选路表wxyzACDB目的地下一个跳

w

--

x

--z

C

4

…. …...D从A收到通告…例子(续)目的网络 下一个71路由表的更新路由器每收到一个邻站的路由表，即更新自己的路由表。(假设K收到J的路由表)(1)K不知道目的站，则加入；(2)有通过J的更短路，则替换；(3)原下站为J的距离有变化，则修改。路由表的更新路由器每收到一个邻站的路由表，即更新自己72例：目的站距离下一跳网络10直接网络20直接网络48路由器L网络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的路由表)(1)K不知道目的站，则加入；(2)有通过J的更短路，则替换；(3)原下站为J的距离有变化，则修改。例：目的站距离下一跳网络10直接网络20直接网络48路由器L73关于距离向量算法的说明优点：CPU和内存开销小缺点：容易引发路由更新不一致问题：路由信息传播速度缓慢，计算结果容易出错。消耗带宽较多。适用于规模不太大的、拓扑结构变化不频繁的环境。关于距离向量算法的说明优点：74（2）链路状态路由算法

-最短路径优先SPF

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

-最短路径优先SPF思想：75步骤①链路状态检测：向直接相邻的路由器周期性发测试报文，检查路由器状态，并按“n中取k”原则进行状态检查。②路由信息广播：路由器周期性地（或某链路状态变化时）广播它所连接的各个链路状态(洪泛)。③路由表更新：收到链路状态的路由器更新自己的网络拓扑图，并用Dijkstra算法计算最短路径。步骤①链路状态检测：向直接相邻的路由器周期性发测试报文，检76关于链路状态算法的说明缺点：需要较高的CPU性能优点：收敛性好规模可扩展性好关于链路状态算法的说明缺点：77学习内容1、引言2、路由表的建立与维护3、路径确定4、路由算法5、Internet路由体系发展6、大规模网络拓扑发现学习内容1、引言78Internet路由体系的发展

路由体系的内容：如何对Internet中的路由器进行划分、管理和控制，以便有效地交换路由信息。路由体系的重要性：决定了互联网的运行效率。Internet路由体系的发展：（1）最早的核心路由体系（2）随后的对等主干路由体系（3）当前的自治系统路由体系Internet路由体系的发展路由体系的内容：如何对Int79核心体系结构（分层树型）ARPANET主干网本地网络2本地网络2本地网络mk1