《9-路由协议概述》由会员分享，可在线阅读，更多相关《9-路由协议概述（45页珍藏版）》请在金锄头文库上搜索。
1、第第9章章 路由协议概述路由协议概述网络协议分析网络协议分析主要内容主要内容1、引言、引言2、路由表的建立与维护路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现基本要求基本要求掌掌握握路路由由表表建建立立和和维维护护的的两两种种方方式式：静静态态配配置置和和动动态态交交换换路由信息；路由信息；掌握两种路由更新算法掌握两种路由更新算法:矢量距离算法和矢量距离算法和SPF算法算法;掌掌握握Internet的的路路由由体体系系结结构构，特特别别是是自自治治系系统统AS的的概概念念和作用和作用.学习内容
2、学习内容1、引言、引言2、路由表的建立与维护路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现问题的提出问题的提出 问题：问题：（1）为什么选择这条路径？）为什么选择这条路径？（2）路由器的路由表如何获取）路由器的路由表如何获取?（3）假设）假设R2与与R4的连接断掉，如何通知的连接断掉，如何通知R1？（4）在在Internet中中，是是否否每每个个路路由由器器都都必必须须了了解解其其它它路路由由器器的情况？的情况？H1H2R1R5R2R3R4路径：路径：H1-R1-R2-R4-H2学习内容学习内
3、容1、引言、引言2、路由表的建立与维护路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Internet路由体系发展路由体系发展6、大规模网络拓扑发现、大规模网络拓扑发现路由表的建立和维护路由表的建立和维护 v静态配置：管理员静态配置：管理员手工手工配置和更新路由表配置和更新路由表优点：节省路由器的处理时间、存储空间以及网络带宽优点：节省路由器的处理时间、存储空间以及网络带宽缺陷：对于链路故障及拓扑结构变化的响应速度慢缺陷：对于链路故障及拓扑结构变化的响应速度慢两种方式：静态配置两种方式：静态配置 和和 动态路由交换动态路由交换H1H2R1R5R2R3R4适用环境：拓扑相对稳定
4、，路由器个数较少适用环境：拓扑相对稳定，路由器个数较少v 利利用用路路由由协协议议交交换换路路由由信信息息，并并根根据据拓拓扑扑结结构构的的变变化化动动态态更更新路由表新路由表优点：自动适应链路故障及拓扑结构的变化优点：自动适应链路故障及拓扑结构的变化缺陷：耗费网络带宽、路由器的处理时间和存储空间缺陷：耗费网络带宽、路由器的处理时间和存储空间适用环境：路由器较多的大规模网络适用环境：路由器较多的大规模网络H1H2R1R5R2R3R4动态路由信息交换动态路由信息交换学习内容学习内容1、引言、引言2、路由表的建立与维护路由表的建立与维护3、路径确定、路径确定4、路由算法、路由算法5、Interne
5、t路由体系发展路由体系发展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
10、1 FEDCBA5 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
11、1 4 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 FEDCB
14、A5 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
15、 A4 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
16、-1.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(自治系统自治系统)：出于选
26、路目的，处于一个管理机构控制之下：出于选路目的，处于一个管理机构控制之下的的一组网络和路由器一组网络和路由器。 限制了路由信息传播限制了路由信息传播的规模的规模 增强了扩展性增强了扩展性（1）AS内部：内部：IGP，比如比如RIP、OSPF、IS-IS等；等； （2）AS之间：之间：EGP，最常用的是最常用的是BGP;（3）EGP通常是一种通常是一种可达性可达性协议。协议。R1R2R3AS1AS2AS3IGP1IGP2IGP3EGP12EGP13EGP23Internet的路由管理模式的路由管理模式举例举例3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP会话会话iBGP会话会
27、话138.16.64/24138.16.65/24138.16.66/24138.16.67/24138.16.64/22聚合聚合l当当AS2向向AS1通告一个通告一个CIDR前缀前缀, 并承诺它将转发任何指并承诺它将转发任何指向该前缀的数据报，向该前缀的数据报，AS2能够在它的通告中能够在它的通告中聚合前缀聚合前缀小结小结路由表配置方式有路由表配置方式有:静态和动态两种静态和动态两种.选路问题涉及路径存在性和路径最优性两个问题选路问题涉及路径存在性和路径最优性两个问题.路由度量要素主要有路由度量要素主要有:带宽带宽,延迟延迟,负载负载,可靠性可靠性,跳数跳数.路由算法包括路由算法包括: 非自适应路由算法和自适应路由算法非自适应路由算法和自适应路由算法.自适应路由算法包括：向量距离算法和链路状态算法自适应路由算法包括：向量距离算法和链路状态算法.Internet路由体系经历了核心路由体系路由体系经历了核心路由体系,对等主干网路由体对等主干网路由体系和自治系统路由体系三个发展阶段系和自治系统路由体系三个发展阶段.自治系统路由体系便于管理和控制自治系统路由体系便于管理和控制.课堂作业课堂作业P121，8题题课后作业课后作业课后认真看教材课后认真看教材, 查阅参考书相应部分的内容查阅参考书相应部分的内容。书面作业：书面作业：P121，3, 10, 12题题
