《IP路由技术与协议.ppt》由会员分享，可在线阅读，更多相关《IP路由技术与协议.ppt（141页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、内容提纲内容提纲n1、引言、引言 n2、域内和域间路由选择、域内和域间路由选择n3、距离向量路由选择与、距离向量路由选择与RIPn4、链路状态路由选择与、链路状态路由选择与OSPFn5、路径向量路由选择与、路径向量路由选择与BGPn6、多播和多播路由选择协议、多播和多播路由选择协议1、引言、引言n互联网由许多互联网由许多路由器路由器连接起来的网络组成连接起来的网络组成n数据从源站到目的站，可能经过多个路由器数据从源站到目的站，可能经过多个路由器n一个一个路由器路由器连接多个网络，当路由器收到分组连接多个网络，当路由器收到分组，应该将分组转发到哪个网络？，应该将分组转发到哪个网络？n按照路由表（
2、选路表）转发！按照路由表（选路表）转发！n路由表路由表是怎样形成的？是怎样形成的？n何时如何发现路由？何时如何发现路由？n如何建立和管理路由表？如何建立和管理路由表？1、引言、引言n根据何时和如何发现路由，路由可分为：根据何时和如何发现路由，路由可分为：n先应式路由先应式路由n表驱动路由（事先建立路由表，查表转发）表驱动路由（事先建立路由表，查表转发）n适合静态网络的路由适合静态网络的路由n反应式路由反应式路由n按需路由（需要时发现并建立路由，按实时路由转发）按需路由（需要时发现并建立路由，按实时路由转发）n适合动态移动网络路由（如移动多跳适合动态移动网络路由（如移动多跳Ad-hoc网络）网络
3、）n根据路由表的建立方式，路由可分为：根据路由表的建立方式，路由可分为：n静态路由静态路由路由表管理者人工配置和维护路由表管理者人工配置和维护n建表不需要额外网络开销建表不需要额外网络开销n不能及时自动反映网络变化不能及时自动反映网络变化n可能出现路由与网络不一致的情况可能出现路由与网络不一致的情况n动态路由动态路由路由表由路由协议动态创建和维护路由表由路由协议动态创建和维护n路由发现过程需要占用网络资源，额外开销路由发现过程需要占用网络资源，额外开销n表的形成需要一定时间表的形成需要一定时间n能自动适应网络变化，更灵活能自动适应网络变化，更灵活1、引言、引言n路由协议的目的路由协议的目的使路
4、由器能够找到到达目使路由器能够找到到达目的地的最佳路径的地的最佳路径n路由协议的共同特点路由协议的共同特点n路由器协同工作路由器协同工作n彼此共享对互连网络的信息彼此共享对互连网络的信息n计算路径，建立路由表计算路径，建立路由表n根据拓扑或某些策略根据拓扑或某些策略n规定信息交互的周期，定期更新路由表规定信息交互的周期，定期更新路由表n网络拓扑变化时，触发更新路由网络拓扑变化时，触发更新路由交互信息（报文）不同，体交互信息（报文）不同，体现了不同路由协议特点现了不同路由协议特点不同的路由协议，计算方法不同的路由协议，计算方法不同不同:可能局部路由，可能全可能局部路由，可能全局路由，可能依赖邻居
5、局路由，可能依赖邻居关键词关键词Metric（度量）（度量）nMetric：用来衡量：用来衡量通过某一网络通过某一网络所需的代价所需的代价n代价代价是什么？是什么？n代价的度量取决于代价的度量取决于Routing ProtocolnHop count（跳数）（跳数）, bandwidth（带宽）（带宽）, delay（延迟（延迟）, MTU, load（负载）（负载）, reliability（可靠性）（可靠性）, nRouting protocol 使用使用Metric来选择一条来选择一条 best path （最优路）（最优路）for routingnMetric之和最小的路径之和最小的路
6、径关键词关键词Convergence（收敛）（收敛）nConvergencen网络中的所有路由器都认为一致的网络中的所有路由器都认为一致的 topologynConvergence time（收敛时间）（收敛时间）n网络发现到网络形成或网络变化到恢复的时间网络发现到网络形成或网络变化到恢复的时间n反应了网络形成或恢复的快慢反应了网络形成或恢复的快慢n从不一致到一致所经历的时间从不一致到一致所经历的时间n体现路由算法的效率体现路由算法的效率n影响收敛的因素影响收敛的因素n使用的路由协议使用的路由协议n变化点到路由器的距离变化点到路由器的距离n网络中路由器的数量网络中路由器的数量n通信链路的带宽和
7、负载通信链路的带宽和负载n路由器的负载路由器的负载n。2、域内路由与域间路由、域内路由与域间路由nInternet十分庞大，需要划分多个自治系统十分庞大，需要划分多个自治系统ASnAutonomous system（自治系统，（自治系统，AS）n一个管理机构管辖的一组网路和路由器一个管理机构管辖的一组网路和路由器n每个每个AS可选择一个或多个路由协议处理本可选择一个或多个路由协议处理本AS内的路由选择内的路由选择nAS内部的路由选择称为内部的路由选择称为域内路由选择域内路由选择nAS 的编号的编号n每个每个AS都赋予一个编号都赋予一个编号nRange: 165535nPrivate AS nu
8、mber: 64512655352、域内路由与域间路由、域内路由与域间路由nInternet十分庞大，需要划分多个自治系统十分庞大，需要划分多个自治系统ASnAutonomous system（自治系统，（自治系统，AS）n一个管理机构管辖的一组网路和路由器一个管理机构管辖的一组网路和路由器n每个每个AS可选择一个或多个路由协议处理本可选择一个或多个路由协议处理本AS内的路由选择内的路由选择nAS内部的路由选择称为内部的路由选择称为域内路由选择域内路由选择nAS 的编号的编号n每个每个AS都赋予一个编号都赋予一个编号nRange: 165535nPrivate AS number: 64512
9、655352、域内路由与域间路由、域内路由与域间路由nInternet由若干由若干AS互相连接构成互相连接构成n每个每个AS内可能有多个网络存在内可能有多个网络存在n核心主干网也可以构成一个核心主干网也可以构成一个ASn核心主干网提供到所有可能的目的地的核心主干网提供到所有可能的目的地的可靠的、统一的、权威的路由可靠的、统一的、权威的路由ASxASyAS1AS3AS2nIGP: Interior Gateway Protocol（内部网关协议）（内部网关协议）n适用于适用于AS内部路由，寻找内部路由，寻找AS内的最佳路径内的最佳路径nExample：RIP、OSPF、IS-ISnEGP: Ex
10、terior Gateway Protocol（外部网关协议）（外部网关协议）n适用于适用于AS 之间路由，寻找到之间路由，寻找到AS的最佳路径的最佳路径nExample：BGP-4nNotenThe static routing or an IGP could also be used between autonomous systems in some caseIGPIGPIGPIGPIGP：动态路由协议：动态路由协议nRIP：适用于密集型网络：适用于密集型网络n采用广播方式与邻居网关交互路由信息采用广播方式与邻居网关交互路由信息nV-D路由算法路由算法nRIPv1：RFC1058(STD
11、 34, 1988)， 基本协议基本协议nRIPv2：RFC1723(1994)， 增加增加CIDR支持支持nOSPF：适用于稀疏型网络：适用于稀疏型网络n采用扩散方式与所有网关交互路由信息采用扩散方式与所有网关交互路由信息nOpen SPF，具有开放性的链路状态路由算法，具有开放性的链路状态路由算法nOSPF V2： RFC2178 ，. J. Moy. April 1998.3、距离向量路由选择与、距离向量路由选择与RIP协议协议n3.1 距离向量路由选择距离向量路由选择n3.1.1 距离向量路由选择算法距离向量路由选择算法n3.1.2 环路问题分析环路问题分析n3.1.3 解决环路的措施
12、解决环路的措施n3.2 RIP协议协议距离距离向量向量法（法（V-D：Vector Distance）n根据协议的设计者命名，也称为根据协议的设计者命名，也称为nBellman-Ford路由算法路由算法nV-D算法通常以跳数作为算法通常以跳数作为Metric（cost）n当然也可以是其他度量参数：如时延、带宽等当然也可以是其他度量参数：如时延、带宽等n基本思想基本思想n每个节点都保持一张到其他节点的路由表每个节点都保持一张到其他节点的路由表 （目的网络，距离，下一节点（目的网络，距离，下一节点）（如以跳数为）（如以跳数为cost，则距离就是跳数），则距离就是跳数）n邻居之间交换路由信息（目的网
13、络，距离）邻居之间交换路由信息（目的网络，距离）n根据收到相邻节点的信息，判断并决定是否更新路由根据收到相邻节点的信息，判断并决定是否更新路由n算法涉及的内容算法涉及的内容n初始的路由表如何建立？初始的路由表如何建立？n邻居交换哪些信息邻居交换哪些信息?n如何根据邻居信息计算并更新自己的路由表？如何根据邻居信息计算并更新自己的路由表？V-D路由算法路由算法n算法的几个步骤算法的几个步骤n 初始化初始化n建立初始路由表建立初始路由表直连路由表直连路由表n扩散扩散n向邻居扩散自己的路由表信息向邻居扩散自己的路由表信息n计算计算n根据收到相邻节点的信息，计算最短路径，更新路由表根据收到相邻节点的信息
14、，计算最短路径，更新路由表n再扩散、再计算再扩散、再计算n这样就逐渐形成了到全网路由这样就逐渐形成了到全网路由n使每个节点都计算出了到其他节点的路径信息使每个节点都计算出了到其他节点的路径信息n值得注意的是：何时向邻居扩散路由信息？值得注意的是：何时向邻居扩散路由信息？n定期定期n拓扑发生变化时拓扑发生变化时V-D算法案例算法案例1）初始路由表建立）初始路由表建立（目的网络，距离，下一跳）（初始都是直连网路（目的网络，距离，下一跳）（初始都是直连网路2）路由表向邻居扩散）路由表向邻居扩散特别说明：特别说明：l为方便讲解，本教案为方便讲解，本教案采用跳数作为采用跳数作为metricl到直连网络的
15、最短距到直连网络的最短距离为离为1跳，因此跳，因此“距离距离”记为记为1注意：注意：度量值也可以是其他参度量值也可以是其他参数数距离距离11-21-距离距离11-31-距离距离21-41-51-距离距离31-41-61-距离距离51-61-V-D算法案例算法案例3）节点计算并更新本节点的路由表）节点计算并更新本节点的路由表n相邻节点定期交换信息相邻节点定期交换信息（目的网络，距离）（目的网络，距离）（目的网络，跳数）（目的网络，跳数）n更新路由表的原则更新路由表的原则（以跳数为例）（以跳数为例）n将收到的路由表信息与本节点原路由表比较将收到的路由表信息与本节点原路由表比较n（1）若原表项无该项
16、，则代价）若原表项无该项，则代价+1，添加该项，添加该项n（2）若原表项中有该项）若原表项中有该项n若具有不同的下一跳，但代价若具有不同的下一跳，但代价+1小于原表项，更新；小于原表项，更新；n 否则，保留原表项否则，保留原表项n若具有相同的下一跳，无论代价是否若具有相同的下一跳，无论代价是否=原代价，都必须更原代价，都必须更新！新！Why？距离矢量算法距离矢量算法距离距离11-21-距离距离1131距离距离11-21-322距离距离214151距离距离11-21-322423523距离距离11-21-322423523632也可能是也可能是3，取决，取决于节点于节点1先收到先收到2还是还是3
17、的再次路由的再次路由信息发布信息发布Count to Infinity，计数到无穷大，计数到无穷大Net1Net1A定义定义1616代表无代表无穷大穷大几种解决措施几种解决措施触发更新触发更新n目的：促进快速收敛目的：促进快速收敛n如网络无变化如网络无变化n每隔每隔30秒定期发送路由更新消息秒定期发送路由更新消息n如网络有变化如网络有变化n立即触发发送路由更新消息立即触发发送路由更新消息Split Horizons（水平分割）（水平分割）节点没有必要将从某节点节点没有必要将从某节点收到的信息再传回给该节点收到的信息再传回给该节点Poison Reverse（毒性反转）（毒性反转）节点将从某节点
18、收到的节点将从某节点收到的信息再传回给该节点时，信息再传回给该节点时，告诉对方不能从我这里告诉对方不能从我这里过（设置成过（设置成16）Hold-down Timer, 抑制定时器抑制定时器n当路由器收到一个路由不可达更新消息时，当路由器收到一个路由不可达更新消息时，启动抑制定时器启动抑制定时器( 60s 、120s)n路由器收到某条路由不可达的消息后，在一段路由器收到某条路由不可达的消息后，在一段时间内（典型时间内（典型6060秒），忽略关于该网络的任何秒），忽略关于该网络的任何路由信息路由信息n确保有较大范围内的站点都收到该坏消息，避确保有较大范围内的站点都收到该坏消息，避免过时的路由通告
19、，但抑制期间环路依然存在免过时的路由通告，但抑制期间环路依然存在V-D算法小节算法小节n特点：特点：n只与邻节点交换路由信息只与邻节点交换路由信息n各节点独立计算最优路径（但依赖邻居的计算结果）各节点独立计算最优路径（但依赖邻居的计算结果）n能适应网络拓扑的变化能适应网络拓扑的变化n稳定后，形成最短路径稳定后，形成最短路径n算法简单算法简单n缺点：缺点：n网络变化扩散到全网速度慢网络变化扩散到全网速度慢n扩散时间：所有节点都发现变化的速度扩散时间：所有节点都发现变化的速度n路由收敛慢路由收敛慢n经过多轮邻居信息交换才能趋于一致经过多轮邻居信息交换才能趋于一致n存在路由环在网络变化未扩散完全时。
20、存在路由环在网络变化未扩散完全时。3.2 RIP协议协议n3.2.1 RIP概述概述n3.2.2 RIP操作操作n3.2.3 RIP定时器定时器n3.2.4 RIP消息格式消息格式n3.2.5 相关讨论相关讨论3.2.1 RIP概述概述n标准标准nRIPv1：RFC1058(STD 34, 1988)， 基本协议基本协议nRIPv2：RFC2453， 增加增加CIDR支持支持n采用采用V-D算法算法n采用跳数作为度量采用跳数作为度量n采用采用UDP封装封装n平面路由协议，仅适合小网平面路由协议，仅适合小网 3.2.1 RIP协议协议nRouting Information Protocol，R
21、IPnv1：RFC 1058，v2：RFC 2453，路由信息协议，路由信息协议 IPLANsMANsWANsICMPIGMPARPRARPTCPUDPRIP软件实现层次软件实现层次Example of a domain using RIP3.2.2 RIP 操作操作nDiscoverynTopology changenCalculatingnRIP updating algorithm网络发现网络发现N3N3- -1 1 0 0N4N4- -2 2 0 0N1N1- -1 1 0 0N2N2- -2 2 0 0N2N2- -1 1 0 0N3N3- -2 2 0 0目的网络目的网络下一跳下一
22、跳发送接口发送接口MetricMetric拓扑变化拓扑变化N3N3- -1 1 0 0N4N4- -2 2 0 0N1N1- -1 1 0 0N2N2- -2 2N2N2- -1 1N3N3- -2 2 0 03.2.3 RIP的定时器的定时器控制更新报文定控制更新报文定期通告，期通告，通常为通常为25-35s的的随机数随机数避免同时更新引避免同时更新引起过载起过载触发更新例外触发更新例外管理路由的有效性管理路由的有效性正常情况下，每正常情况下，每30s复位一次，如复位一次，如故障，在故障，在180s未收未收到更新报文，则过到更新报文，则过期，跳数设置为期，跳数设置为16当某条路由信息成当某条
23、路由信息成为无效时（为无效时（16），），路由器并不立即清路由器并不立即清除该表项，而是继除该表项，而是继续通告，待续通告，待120s后后才清除该表项才清除该表项3.2.4 RIP消息格式（消息格式（V1)nRIP只定义了有一种报文格式只定义了有一种报文格式n交换（交换（IP address，Metric）对）对nIP address 可为可为A、B、C类网络地址或主机地址类网络地址或主机地址3.2.4 RIP消息格式（消息格式（V1)nCommandn1=Request 请求部分或全部选路信息请求部分或全部选路信息n2=Response 发送方给出自己选路表的发送方给出自己选路表的(V，D)
24、n9=更新请求更新请求 10=更新响应更新响应 11=更新确认更新确认nAddress Family Identifiern2 IPaddressnV1版未定义掩码，只能用于有类地址方式版未定义掩码，只能用于有类地址方式 RIPv2的扩展的扩展nRIPv2格式格式n路由标记：路由起点、自治域号等额外信息路由标记：路由起点、自治域号等额外信息nRIP2实现对实现对CIDR的扩展的扩展081624 31CommandVersion=2Must be 0Address Family Identifier目的网的路由标记目的网的路由标记目的网地址（目的网地址（IP Addr）目的网掩码（目的网掩码（M
25、ask）到目的网的下一网关（到目的网的下一网关（Next Hop）到目的网的距离（到目的网的距离（Metric） 重复重复25次次3.2.5 RIP的讨论的讨论n距离距离16指网络的跨度，而不是路由器的数目指网络的跨度，而不是路由器的数目nRIP适合于不大的网络适合于不大的网络n简单的路由，无法处理时延、容量要求简单的路由，无法处理时延、容量要求n相对固定的路由，较长时间不变相对固定的路由，较长时间不变n无法对网络性能变化（负载、时延等）做出反应（无法对网络性能变化（负载、时延等）做出反应（调整路由）调整路由）n仍有大量的应用仍有大量的应用4、链路状态路由选择与、链路状态路由选择与OSPFn4
26、.1 链路状态路由选择链路状态路由选择n4.1.1 算法基本思想算法基本思想n4.1.2 链路状态算法的操作链路状态算法的操作n4.2 OSPF协议协议4.1.1 L-S路由选择算法基本思想路由选择算法基本思想n参与该算法的所有路由器都需要掌握全部拓扑结构参与该算法的所有路由器都需要掌握全部拓扑结构n拓扑结构：拓扑结构：n点：路由器点：路由器n边：路由器相连的网络边：路由器相连的网络n算法基本思想算法基本思想n周期地检查邻接路由器的状态（可达性）周期地检查邻接路由器的状态（可达性）n向所有路由器通告自己的链路状态（全网扩散）向所有路由器通告自己的链路状态（全网扩散）n每个路由器根据自己掌握的拓
27、扑结构，独立计算到所有目每个路由器根据自己掌握的拓扑结构，独立计算到所有目网络的路由网络的路由n典型算法：典型算法：Dijkstra最短路径算法最短路径算法4.1.1 L-S路由选择算法基本思想路由选择算法基本思想n涉及到的主要问题涉及到的主要问题n（1）各路由器如何知道全部拓扑？）各路由器如何知道全部拓扑？n（2）路由器如何扩散自己的链路状态）路由器如何扩散自己的链路状态n（3）路由器如何计算到各网的最短路径）路由器如何计算到各网的最短路径4.1.2 链路状态算法的操作链路状态算法的操作n发现邻居发现邻居n探寻邻居，得到邻居的唯一地址探寻邻居，得到邻居的唯一地址n测量链路开销测量链路开销n测
28、量到各邻居节点的延迟（链路质量）测量到各邻居节点的延迟（链路质量）n交换路链路状态信息交换路链路状态信息n形成链路状态分组，向所有节点扩散形成链路状态分组，向所有节点扩散n充实路由信息库充实路由信息库n根据收到各节点的链路状态信息，进而得出全网拓扑根据收到各节点的链路状态信息，进而得出全网拓扑n计算到各网络的最佳路径计算到各网络的最佳路径n根据自己掌握的路由信息，独立计算本节点到其他节点的最佳根据自己掌握的路由信息，独立计算本节点到其他节点的最佳路由路由n特别注意：特别注意：n交流的路由信息：链路状态信息交流的路由信息：链路状态信息n交流的对象：向所有的节点交流的对象：向所有的节点n交流的方法
29、：扩散法交流的方法：扩散法n路由的计算：只根据自己掌握的路由信息，独立计算最佳路由路由的计算：只根据自己掌握的路由信息，独立计算最佳路由（不依赖别人的计算）（不依赖别人的计算）链路状态算法链路状态算法发现邻居发现邻居n初始时，每个节点都向每个出口（直接链路）发送初始时，每个节点都向每个出口（直接链路）发送“Hello”分组，告知自己的分组，告知自己的IP地址地址n收到分组的节点则回应一个分组告知自己的收到分组的节点则回应一个分组告知自己的IP地址地址n特别强调：每个节点的地址必须唯一特别强调：每个节点的地址必须唯一ABHello，I am AHello，I am B链路状态算法链路状态算法测量
30、链路开销测量链路开销n测量链路开销（以链路时延为例）测量链路开销（以链路时延为例）n向邻居发送向邻居发送“Echo”分组（对方必须应答）分组（对方必须应答）n对方发送应答对方发送应答n计算来回延时除以计算来回延时除以2，得到时延（可计算几次得平均值），得到时延（可计算几次得平均值）n计算链路开销时值得讨论的问题计算链路开销时值得讨论的问题n是否考虑负荷？是否考虑负荷？n两种观念两种观念n考虑负荷，从进入发送队列排队开始算考虑负荷，从进入发送队列排队开始算n忽略负荷，从发送开始算忽略负荷，从发送开始算n正反方向延时是否一样？正反方向延时是否一样？n可能不一样可能不一样n为分析简便，通常忽略差异，
31、用平均值为分析简便，通常忽略差异，用平均值“Echo”“Echo”Response链路状态算法链路状态算法测量并计算链路开销测量并计算链路开销n通过测试计算出到邻居的开销通过测试计算出到邻居的开销n假设各节点测得的开销如下所示假设各节点测得的开销如下所示A节点节点B节点节点4C3B开开销销邻邻居居6C5D3A开开销销邻邻居居2D6B1E4A开开销销邻邻居居3E2C2F5B开开销销邻邻居居3D2F1C开开销销邻邻居居2E2D开开销销邻邻居居C节点节点D节点节点F节点节点E节点节点链路状态算法链路状态算法交换链路状态信息交换链路状态信息n创建链路状态分组并向全网发布创建链路状态分组并向全网发布n根
32、据测得的到所有邻居的的延时，形成链路状态分组根据测得的到所有邻居的的延时，形成链路状态分组n链路状态分组的内容链路状态分组的内容n发布者：发布信息的节点名称发布者：发布信息的节点名称n序号：序号的大小表示信息的新旧序号：序号的大小表示信息的新旧n年龄：一个分组在网络中的存活时间年龄：一个分组在网络中的存活时间4C3B时间时间序号序号A发布发布者者6C3A时间时间序号序号B发布发布者者5D6B4A时间时间序号序号C发布发布者者2D1E2C5B时间时间序号序号D发布发布者者3E2F3D1C时间时间序号序号E发布发布者者2F2E2D时间时间序号序号F发布发布者者链路状态算法链路状态算法n发布链路状态
33、分组发布链路状态分组n发布对象：所有节点发布对象：所有节点n发布时间：定期，连路状态发生改变时发布时间：定期，连路状态发生改变时n发布方法：扩散法（洪泛）发布方法：扩散法（洪泛）n采用扩散法一定可以到达全网各节点采用扩散法一定可以到达全网各节点n节点可能收到多个相同的分组节点可能收到多个相同的分组n可根据序号判别，相同的序号则丢弃重复的可根据序号判别，相同的序号则丢弃重复的n节点也可能收到同一个发布者不同序号的分组节点也可能收到同一个发布者不同序号的分组n根据发布时间判别，丢弃老的，处理新的根据发布时间判别，丢弃老的，处理新的n为避免分组可能在网中循环为避免分组可能在网中循环n通过年龄字段避免
34、（年龄按时间递减，到通过年龄字段避免（年龄按时间递减，到0时将被丢弃）时将被丢弃）链路状态算法链路状态算法绘制全局拓扑绘制全局拓扑n根据逐步收到的链路分组，充实根据逐步收到的链路分组，充实路由信息库，逐步路由信息库，逐步“绘出绘出”拓扑拓扑图图n以节点以节点A为例，各节点发布链路为例，各节点发布链路分组后，分组后，A逐步得到了分组逐步得到了分组4C3B时间时间序号序号A发布发布者者6C3A时间时间序号序号B发布发布者者5D6B4A时间时间序号序号C发布发布者者2D1E2C5B时间时间序号序号D发布发布者者3E2F3D1C时间时间序号序号E发布发布者者2F2E2D时间时间序号序号F发布发布者者链
35、路状态算法链路状态算法计算最佳路径计算最佳路径n计算到各节点的最佳路由计算到各节点的最佳路由n计算方法：计算方法：n把本节点作为源节点，计算到其他节点的路由把本节点作为源节点，计算到其他节点的路由n采用著名的采用著名的Dijkstra算法（最短路径算法）算法（最短路径算法）n计算的依据计算的依据n只根据自己掌握的路由信息库（拓扑）只根据自己掌握的路由信息库（拓扑）n独立计算最佳路由（不依赖别人的计算）独立计算最佳路由（不依赖别人的计算）链路状态算法链路状态算法nDijkstra算法的基本思想算法的基本思想 以计算路由的节点以计算路由的节点V0为源节点（出发点）为源节点（出发点）1）设置源节点到
36、其他所有节点的初始开销）设置源节点到其他所有节点的初始开销n相邻的节点设置为测得的开销值（相邻的节点设置为测得的开销值（Ci，Vi）nCi：源节点到相邻节点：源节点到相邻节点Vi的代价（的代价（cost）n不相邻的节点设置为（不相邻的节点设置为（，- -）2 2）将具有最小）将具有最小CiCi的节点的节点ViVi及链路加入到及链路加入到V0V0的路由中的路由中3 3）根据加入的）根据加入的ViVi节点计算与之相邻节点到节点计算与之相邻节点到V0V0的最小代价的最小代价 并将到并将到V0V0代价最小的节点及链路加入到路由中（已加入代价最小的节点及链路加入到路由中（已加入的节点和链路除外）的节点和
37、链路除外）4 4）依此，不断重复）依此，不断重复3 3），直到包含所有节点和最佳链路为止），直到包含所有节点和最佳链路为止链路状态算法链路状态算法nDijkstra算法案例算法案例n假设假设A收到收到B的链路分组，的链路分组，n以以A为源节点，为源节点， 计算计算A到其他节点的路由到其他节点的路由ABCD34A B48A B C8A B C D8节点的逐步节点的逐步加入加入链路的逐步链路的逐步加入加入A到其他节点代价的到其他节点代价的逐步优化逐步优化A-BA-CB-D6C3A时间时间序号序号B发布发布者者5DA的路由的路由 转发表转发表目目的的节节点点下下一一节节点点 开开销销BB3CC4DB
38、8A节点节点4C3B开开销销邻邻居居链路状态算法链路状态算法nDijkstra算法案例算法案例n假设假设A收到收到B、C的链路分组，的链路分组，n以以A为源节点，为源节点， 计算计算A到其他节点的路由到其他节点的路由6C3A时间时间序号序号B发布发布者者5D6B4A时间时间序号序号C发布发布者者2D1EABCDE34A B48A B C65A B C E6A B C ED节点的逐步节点的逐步加入加入链路的逐步链路的逐步加入加入A到其他节点代价的到其他节点代价的逐步优化逐步优化A-BA-CC-EC-DA的路由转发表的路由转发表目目的的节节点点下下一一节节点点 开开销销BB3CC4DC6EC5A的
39、路由转发表的路由转发表链路状态算法链路状态算法nDijkstra算法案例算法案例nA点收到所有节点分组后点收到所有节点分组后n以以A为源节点，为源节点，n计算计算A到其他节点的路由到其他节点的路由ABCDEF34A B48A B C65A B C E67A B C ED7A B C ED F节点的逐步节点的逐步加入加入链路的逐步链路的逐步加入加入A到其他节点代价的到其他节点代价的逐步优化逐步优化A-BA-CC-EC-DE-F链路状态算法链路状态算法nDijkstra算法案例算法案例n计算的结果，计算的结果，A点到其他节点形成了一棵以点到其他节点形成了一棵以A为根的树为根的树n根据最优判决原理，
40、这是一棵最佳路由树根据最优判决原理，这是一棵最佳路由树n也称为信源树或汇集树也称为信源树或汇集树链路状态算法链路状态算法nDijkstra算法案例算法案例n根据计算结果，根据计算结果，A节点的路由转发表如下：节点的路由转发表如下：目的节点目的节点下一节点下一节点 开销开销BB3CC4DC6EC5FC7A节点的路由转发表节点的路由转发表链路状态算法小结链路状态算法小结n特点特点n与全网节点交换路由信息路由信息的扩散与全网节点交换路由信息路由信息的扩散n各节点独立计算最优路径一致性、准确性有各节点独立计算最优路径一致性、准确性有较好的保证较好的保证n不是建立在别人的计算结果上（如距离矢量算法以来不
41、是建立在别人的计算结果上（如距离矢量算法以来邻居的计算结构）邻居的计算结构）n能适应网络拓扑的变化，稳定后能形成最短路径能适应网络拓扑的变化，稳定后能形成最短路径n收敛速度快可在大网中使用收敛速度快可在大网中使用n拓扑改变立即独立计算拓扑改变立即独立计算n算法复杂，存储空间需求大算法复杂，存储空间需求大n需要记录全网所有的链路状态需要记录全网所有的链路状态4.2 OSPFn4.2.1 OSPF概述概述n4.2.2 OSPF的分区的分区n4.2.3 OSPF路由器类型路由器类型n4.2.4 OSPF链路类型链路类型n4.2.5 OSPF分组格式分组格式n4.2.6 OSPF的的LSU分组分组n4
42、.2.7 OSPF的的LSA类型类型n4.2.8 OSPF的操作的操作4.2.1 OSPF概述概述nOSPF: Open Shortest Path Firstn 一种适合与一种适合与AS内的路由协议内的路由协议n采用采用L-S算法计算最短路径算法计算最短路径nOSPF直接使用直接使用IP实体提供的服务实体提供的服务nIP协议协议ID 89n是一种分层的路由协议，适合于大网是一种分层的路由协议，适合于大网4.2.1 OSPF概述概述IPLANsMANsWANsICMPIGMPARPRARPTCPUDPOSPF软件实软件实现层次现层次RIPOSPF算法核心思想算法核心思想n掌握网络拓扑结构掌握网
43、络拓扑结构n掌握网络拓扑掌握网络拓扑 = 掌握所有路由器与邻居的连接关系掌握所有路由器与邻居的连接关系n通过路由器之间彼此共享链路状态通过路由器之间彼此共享链路状态n拓扑有变化时更新并共享拓扑有变化时更新并共享n路由计算路由计算n根据网络拓扑结构，计算到任意站点的最短路径根据网络拓扑结构，计算到任意站点的最短路径(SPF)nDijkstra经典算法经典算法n从最短路径确定下一跳地址从最短路径确定下一跳地址(FIB内容内容)n关键点关键点n只要掌握了网络拓结构，路由器就能计算所有路由只要掌握了网络拓结构，路由器就能计算所有路由R1,1R2,2R3,3R0,2R1,2R5,25R2,25R3,35
44、R4,45R6,56R8,58邻居关系：邻居关系：R0R2R5R0,1R2,12R4,14R8,18R14.2.2 OSPF的分区的分区n分区域理由：大规模的网络会给分区域理由：大规模的网络会给OSPF路由路由器带来沉重的负担器带来沉重的负担n链路状态的改变，可能会使路由器经常执行链路状态的改变，可能会使路由器经常执行SPF（最短路径优先）算法（最短路径优先）算法n路由表膨胀路由表膨胀n每个路由器需要保持的完整网络拓扑（链路数每个路由器需要保持的完整网络拓扑（链路数据库）据库）nOSPF将网络划分成若干较小的区域将网络划分成若干较小的区域n区域内的路由器执行区域内的路由器执行SPF算法算法n区
45、域间：交换汇总后的路由信息，而不是详细区域间：交换汇总后的路由信息，而不是详细的路由信息的路由信息4.2.2 OSPF的分区的分区63n多区域多区域n每个区域是独立的每个区域是独立的OSPF路由协议范围路由协议范围n网络拓扑数据库只包含区域内部分网络拓扑数据库只包含区域内部分nOSPF协议在区域边界处终止协议在区域边界处终止n某些路由器会属于多个区域某些路由器会属于多个区域n称为：区域边界路由器称为：区域边界路由器n区域边界路由器构成另一个路由域（主干域）区域边界路由器构成另一个路由域（主干域）n形成分层路由结构形成分层路由结构n一级路由：区域间路由一级路由：区域间路由主干路由主干路由n二级路
46、由：区域内路由二级路由：区域内路由OSPF域OSPF域OSPF域OSPF域OSPF域OSPF域ASRRRRRRRRRRRRRRRRRRRRRRRRR2级路由级路由区域内路由区域内路由1级路由级路由区域间路由）区域间路由）3级路由级路由RRR区域内路由器区域内路由器R区域间路由器区域间路由器RAS边界路由器边界路由器分级路由结构分级路由结构OSPF多区域模型多区域模型2级路由级路由区域内路由区域内路由2级路由级路由区域内路由区域内路由3级路由级路由4.2.2 OSPF的分区的分区nArea：包含在：包含在AS中的一些网络、主机和路由器的中的一些网络、主机和路由器的集合集合n类型：标准区域、主干区
47、域（类型：标准区域、主干区域（ Backbone area ）、残桩区域（、残桩区域（Stub area）Autonomous SystemAutonomous SystemArea 1Area 1Area 2Area 2Area 0 (backbone)Area 0 (backbone)ToTootherotherASsASsOSPF区域类型区域类型n区域的类型：决定区域的类型：决定了该区域内路由器所能接了该区域内路由器所能接收的路由信息的类型收的路由信息的类型n标准区域：区域内路由器能够接收标准区域：区域内路由器能够接收链路状态链路状态更新更新和和路由归纳（区间路由）路由归纳（区间路由）n
48、主干区域：具有标准区域的一切属性，特殊主干区域：具有标准区域的一切属性，特殊之处在于：它需要负责之处在于：它需要负责互连互连其它所有其它所有区域区域n残桩区域：这种区域残桩区域：这种区域不接收不接收那些那些自治系统以自治系统以外外的路由信息的路由信息n如果需要发送分组到自治系统之外的网络，区如果需要发送分组到自治系统之外的网络，区域内路由器将使用域内路由器将使用默认路由默认路由n主干区域主干区域n负责分发非主干区域间的路由信息负责分发非主干区域间的路由信息nAS中的其他所有区域必须与主干区邻接中的其他所有区域必须与主干区邻接n并不要求一定是物理连接并不要求一定是物理连接n可以是可以是Virtu
49、al link（可以人工配置）（可以人工配置）4.2.3 OSPF路由器类型路由器类型Autonomous SystemAutonomous SystemArea 2Area 2Area 0 (backbone)Area 0 (backbone)To otherTo otherASASABRABR，BRBRIRIRASBRASBR，BRBRIRIR，BRBRnInternal router（内部路由器）（内部路由器）, IRnBackbone router（主干路由器）（主干路由器）, BRnArea Border Router（区域边界路由器）（区域边界路由器）, ABRnAS Border
50、 Router（ AS边界路由器）边界路由器）, ASBR4.2.3 OSPF路由器类型路由器类型Autonomous SystemAutonomous SystemArea 2Area 2Area 0 (backbone)Area 0 (backbone)To otherTo otherASASABR:ABR接口连接不同区域接口连接不同区域ABR为其连接的每个区域维护单为其连接的每个区域维护单独的链路状态数据库独的链路状态数据库并从中归纳路由，将汇总路由发并从中归纳路由，将汇总路由发布到主干区域，而主干区域中的布到主干区域，而主干区域中的ABR再将其扩散到其它区域再将其扩散到其它区域IRIR