04动态路由选择协议.ppt

LOGO路由技术路由技术第四讲第四讲 动态路由选择协议动态路由选择协议 电子科技大学中山学院电子科技大学中山学院李瑞芳李瑞芳 2010年年 动态路由选择协议（动态路由选择协议（routing protocol）作为路由器之间进行相互交）作为路由器之间进行相互交流的语言，用于实现可达性信息和网流的语言，用于实现可达性信息和网络状态的共享。络状态的共享。动态路由选择协议不仅执行路径决策动态路由选择协议不仅执行路径决策和路由表更新功能，而且还要在最优和路由表更新功能，而且还要在最优秀的路径不可用时决策下一条最优路秀的路径不可用时决策下一条最优路径。径。4.1 4.1 路由选择协议基础路由选择协议基础所有路由选择协议都是围绕着一种算法所有路由选择协议都是围绕着一种算法而构建的，一种路由算法至少应指明以而构建的，一种路由算法至少应指明以下内容下内容:(1)向其他路由器传送网络信息的过程；向其他路由器传送网络信息的过程；(2)从其他路由器接收网络信息的过程；从其他路由器接收网络信息的过程；(3)基于现有信息决策最优路由的过程，以基于现有信息决策最优路由的过程，以及在路由表中记录这些信息的过程；及在路由表中记录这些信息的过程；(4)响应、修正和通告网络中拓扑变化的过响应、修正和通告网络中拓扑变化的过程程。在网络内的所有子网都必须连接到一在网络内的所有子网都必须连接到一台路由器上，无论什么情况下，只要台路由器上，无论什么情况下，只要路由器有接口连接到一个网络上，那路由器有接口连接到一个网络上，那么该接口必须具有一个属于该网络的么该接口必须具有一个属于该网络的地址，这个地址就是可达性信息的起地址，这个地址就是可达性信息的起始点。始点。基本术语基本术语度量度量（metric）是衡量目的网络远近）是衡量目的网络远近的值。的值。不同的路由选择协议使用不同的度量，不同的路由选择协议使用不同的度量，主要有：跳数、带宽、负载、可靠性、主要有：跳数、带宽、负载、可靠性、时延等时延等路由选择环路路由选择环路：在两个或多个目标网：在两个或多个目标网络之间流量的持续循环。络之间流量的持续循环。4.2 4.2 距离矢量路由协议距离矢量路由协议距离矢量的意义距离矢量的意义:使用距离矢量路由协议的路由器并不了解使用距离矢量路由协议的路由器并不了解到达目的网络的整条路径。该路由器只知到达目的网络的整条路径。该路由器只知道：道：自身与目的网络之间的距离自身与目的网络之间的距离(根据度量定义根据度量定义)应该往哪个方向或使用哪个接口转发数据包应该往哪个方向或使用哪个接口转发数据包（根据下一跳路由器定义）（根据下一跳路由器定义）距离矢量路由协议有时又被称为距离矢量路由协议有时又被称为“依照传闻进行的路由选择依照传闻进行的路由选择”距离矢量路由协议举例距离矢量路由协议举例:路由信息协议路由信息协议(RIPRIP)内部网关协议内部网关协议 (IGRPIGRP)增强型增强型 IGRP(IGRP(EIGRPEIGRP)距离矢量路由协议有一些距离矢量路由协议有一些共同特征共同特征:周期更新周期更新邻居邻居 广播更新广播更新整个路由表更新整个路由表更新距离矢量路由技术距离矢量路由技术路由失效计时器路由失效计时器：路由器不断的向某：路由器不断的向某个不可达的网络转发数据包的情况叫个不可达的网络转发数据包的情况叫做路由黑洞，解决这个问题的办法是做路由黑洞，解决这个问题的办法是为路由器中每个表项设置路由失效计为路由器中每个表项设置路由失效计时器。时器。路由超时的典型周期范围是路由超时的典型周期范围是 36 个个更新周期更新周期 水平分隔水平分隔：路由的指向与数据包流动方：路由的指向与数据包流动方式相反的路由被称为逆向路由（式相反的路由被称为逆向路由（reverse route），水平分隔技术可以解决这个问），水平分隔技术可以解决这个问题题 执行水平分隔可以阻止路由环路的发生，执行水平分隔可以阻止路由环路的发生，有两类水平分隔方法：简单水平分隔和有两类水平分隔方法：简单水平分隔和毒性逆转水平分隔法毒性逆转水平分隔法 简单水平分隔简单水平分隔：从某个接口发送的更新消息：从某个接口发送的更新消息不能包含从该接口收到的更新所包含的网络，不能包含从该接口收到的更新所包含的网络，简单水平分隔采用抑制更新的方式简单水平分隔采用抑制更新的方式 毒性逆转水平分隔：毒性逆转水平分隔：是一种改进的方法，它是一种改进的方法，它的原理是当更新信息被发送出某接口时，信的原理是当更新信息被发送出某接口时，信息中将指定从该接口收到的更新信息中获取息中将指定从该接口收到的更新信息中获取的网络是不可达的的网络是不可达的 距离矢量路由技术距离矢量路由技术距离矢量路由技术距离矢量路由技术水平分隔水平分隔切断了邻居路由器之间的环路，切断了邻居路由器之间的环路，但是它不能切断网络中的环路，解决这个但是它不能切断网络中的环路，解决这个问题的办法是定义无穷大的数值。问题的办法是定义无穷大的数值。定义无穷大数值的方法收敛速度慢，定义无穷大数值的方法收敛速度慢，触发触发更新更新可以用于减少收敛时间可以用于减少收敛时间。触发更新触发更新又叫快速更新，如果一个度量变又叫快速更新，如果一个度量变好或变坏，那么路由器将立即发送更新信好或变坏，那么路由器将立即发送更新信息，而不等更新计时器超时息，而不等更新计时器超时。触发更新时仅包括实际触发该事件的网络，触发更新时仅包括实际触发该事件的网络，而不是包括整个路由表。而不是包括整个路由表。距离矢量路由技术距离矢量路由技术抑制计时器：抑制计时器：如果到一个目标的距离增如果到一个目标的距离增加，那么路由器将为该路由设置抑制计加，那么路由器将为该路由设置抑制计时器，直到计时器超时，路由器才可以时器，直到计时器超时，路由器才可以接受有关此路由的更新信息。接受有关此路由的更新信息。异步更新：异步更新：如果更新计时器同步，就可如果更新计时器同步，就可能发生碰撞，维持异步更新的两种方法：能发生碰撞，维持异步更新的两种方法：（1）每台路由器的更新计时器独立于路由选）每台路由器的更新计时器独立于路由选择进程；择进程；（2）在每个更新周期中加入一个小的随机时）在每个更新周期中加入一个小的随机时间或定时抖动作为偏移。间或定时抖动作为偏移。4.3 链路状态路由协议链路状态路由协议又称为又称为 最短路径优先协议最短路径优先协议，它建基于，它建基于 Edsger Dijkstra 的的 SPF（最短路径（最短路径优先）算法优先）算法OSPF（开放最短路径优先）（开放最短路径优先）IS-IS（中间系统到中间系统）：主（中间系统到中间系统）：主要供要供ISP和电信公司使用和电信公司使用业内还有用于非业内还有用于非 IP 网络的一些链路状网络的一些链路状态路由协议。态路由协议。SPF 算法简介算法简介Dijkstras算法通常称为算法通常称为 SPF（最（最短路径优先）算法，但事实上，优短路径优先）算法，但事实上，优先最短路径是所有路由算法的目的。先最短路径是所有路由算法的目的。SPF 算法简介算法简介每台路由器会自行确定通向拓扑每台路由器会自行确定通向拓扑中每个目的地的开销。中每个目的地的开销。最短路径最短路径 最少跳数的最少跳数的路径路径链路状态路由协议工作原理链路状态路由协议工作原理1.1.每台路由器了解其自身的链路（即与其直连每台路由器了解其自身的链路（即与其直连的网络）的网络）2.2.每台路由器负责每台路由器负责“问候问候”直连网络中的相邻直连网络中的相邻路由器路由器3.3.每台路由器创建一个链路状态数据包（每台路由器创建一个链路状态数据包（LSPLSP），），其中包含与该路由器直连的每条链路的状态其中包含与该路由器直连的每条链路的状态4.4.每台路由器将每台路由器将LSPLSP泛洪到所有邻居，然后邻居泛洪到所有邻居，然后邻居将收到的所有将收到的所有LSPLSP存储到数据库中存储到数据库中5.5.每台路由器使用数据库构建一个完整的拓扑每台路由器使用数据库构建一个完整的拓扑图并计算通向每个目的网络的最佳路径图并计算通向每个目的网络的最佳路径了解直连的网络了解直连的网络从从R1来了解来了解链路链路是路由器上的一个接口是路由器上的一个接口链路状态链路状态是有关各条链路的状态的信息是有关各条链路的状态的信息向邻居发送向邻居发送Hello数据包数据包路由器使用路由器使用 Hello 协协议议来发现其链路上的来发现其链路上的所有邻居所有邻居两台链路状态路由器两台链路状态路由器获悉它们是邻居时，获悉它们是邻居时，将形成一种将形成一种相邻关系相邻关系这些小型这些小型 Hello 数据数据包持续在两个相邻的包持续在两个相邻的邻居之间互换，以此邻居之间互换，以此实现实现“保持生存保持生存”功功能来监控邻居的状态能来监控邻居的状态创建链路状态数据包创建链路状态数据包路由器一旦建立了相邻关系，即可创建链路路由器一旦建立了相邻关系，即可创建链路状态数据包状态数据包(LSPs)包含与该链路相关的链路状态信息包含与该链路相关的链路状态信息将链路状态数据库泛洪到邻居将链路状态数据库泛洪到邻居路由器一旦接收到路由器一旦接收到来自相邻路由器的来自相邻路由器的 LSP，立即立即将该将该 LSP 从除接收该从除接收该 LSP 的接口以外的的接口以外的所有接口发出所有接口发出链路状态路由协议链路状态路由协议则在泛洪完成后则在泛洪完成后 再再计算计算 SPF 算法算法LSP 中还包含其它中还包含其它信息（例如序列号信息（例如序列号和过期信息），以和过期信息），以帮助管理泛洪过程帮助管理泛洪过程(1)(2)将链路状态数据库泛洪到邻居将链路状态数据库泛洪到邻居LSP 并不需要定期发送，而仅在下列情并不需要定期发送，而仅在下列情况下才需要发送：况下才需要发送：在路由器初始启动期间，或在该路由器上的在路由器初始启动期间，或在该路由器上的路由协议进程启动期间。路由协议进程启动期间。每次拓扑发生更改时，包括链路接通或断开，每次拓扑发生更改时，包括链路接通或断开，或是相邻关系建立或破裂。或是相邻关系建立或破裂。链路状态路由协议达到收敛状态的速度比距离矢量路由协议快得多构建链路状态数据库构建链路状态数据库路由区域内的每台路由器都可以使用路由区域内的每台路由器都可以使用 SPF 算法来构建算法来构建SPF 树树构建链路状态数据库构建链路状态数据库有了完整的链路状态数据库，有了完整的链路状态数据库，R1 现在即可使现在即可使用该数据库和用该数据库和 SPF（最短路径优先）算法来（最短路径优先）算法来计算通向每个网络的首选路径（即最短路径）计算通向每个网络的首选路径（即最短路径）SPF（最短路径优先）树构建过程（最短路径优先）树构建过程下面详细分析下面详细分析 R1 构建构建 SPF 树的过程树的过程例例:R1:R1 构建构建 SPF SPF 树的过程树的过程SPF 算法首先算法首先处理来自理来自 R2 的下列的下列 LSP 信息：信息：1.连接到网接到网络 10.2.0.0/16 上的上的邻居居 R1，开，开销为 202.连接到网接到网络 10.9.0.0/16 上的上的邻居居 R5，开，开销为 103.带有一个网有一个网络 10.5.0.0/16，开，开销为 2R1 可以忽略第一个可以忽略第一个 LSP，因，因为 R1 已已经知道它知道它连接到网接到网络 10.2.0.0/16 上的上的 R2（开（开销为 20）。）。R1 可以使用第二个可以使用第二个 LSP 并并创建一个从建一个从 R2 到另一路到另一路由器由器(R5)的的链路，路，该链路所在的网路所在的网络为 10.9.0.0/16，开，开销为 10。此信息被添加到。此信息被添加到 SPF 树中。通中。通过第三个第三个 LSP，R1 可可获悉悉 R2 带有一个网有一个网络 10.5.0.0/16，该网网络的开的开销为 2，且，且 R2 在在该网网络上无上无邻居。此居。此链路被添加到路被添加到 R1 的的 SPF 树中。中。例例:R1:R1 构建构建 SPF SPF 树的过程树的过程SPF 算法算法现在在处理来自理来自 R3 的的 LSP：1.连接到网接到网络 10.3.0.0/16 上的上的邻居居 R1，开，开销为 52.连接到网接到网络 10.7.0.0/16 上的上的邻居居 R4，开，开销为 103.带有一个网有一个网络 10.6.0.0/16，开，开销为 2R1 可以忽略第一个可以忽略第一个 LSP，因，因为 R1 已已经知道它知道它连接到网接到网络 10.3.0.0/16 上的上的 R3（开（开销为 5）。）。R1 可以使用第二个可以使用第二个 LSP 并并创建一个从建一个从 R3 到到路由器路由器 R4 的的链路，路，该链路所在的网路所在的网络为 10.7.0.0/16，开，开销为 10。此信息被添加到。此信息被添加到 SPF 树中。通中。通过第三个第三个 LSP，R1 可可获悉悉 R3 带有一有一个网个网络 10.6.0.0/16，该网网络的开的开销为 2，且，且 R3 在在该网网络上无上无邻居。此居。此链路被添加到路被添加到 R1 的的 SPF 树中。中。例例:R1:R1 构建构建 SPF SPF 树的过程树的过程SPF 算法算法现在在处理来自理来自 R4 的的 LSP：1.连接到网接到网络 10.4.0.0/16 上的上的邻居居 R1，开，开销为 202.连接到网接到网络 10.7.0.0/16 上的上的邻居居 R3，开，开销为 103.连接到网接到网络 10.10.0.0/16 上的上的邻居居 R5，开，开销为 104.带有一个网有一个网络 10.8.0.0/16，开，开销为 2R1 可以忽略第一个可以忽略第一个 LSP，因，因为 R1 已已经知道它知道它连接到接到网网络 10.4.0.0/16 上的上的 R4（开（开销为 20）。）。R1 还可以忽可以忽略第二个略第二个 LSP，因，因为 SPF 已已经知道网知道网络 10.7.0.0/16 来自来自 R3 且开且开销为 10。不不过，R1 可以使用第三个可以使用第三个 LSP 来来创建从建从 R4 到路由器到路由器 R5 的的链路，路，该链路所在的网路所在的网络为 10.10.0.0/16，开，开销为 10。此信息被添加到。此信息被添加到 SPF 树中。通中。通过第四个第四个 LSP，R1 可可获悉悉 R4 带有一个网有一个网络 10.8.0.0/16，该网网络的开的开销为 2，且，且 R4 在在该网网络上无上无邻居。此居。此链路被添加到路被添加到 R1 的的 SPF 树中。中。例例:R1:R1 构建构建 SPF SPF 树的过程树的过程SPF 算法算法现在在处理最后一个理最后一个 LSP（来自（来自 R5）：）：1.连接到网接到网络 10.9.0.0/16 上的上的邻居居 R2，开，开销为 102.连接到网接到网络 10.10.0.0/16 上的上的邻居居 R4，开，开销为 103.带有一个网有一个网络 10.11.0.0/16，开，开销为 2R1 可以忽略前两个可以忽略前两个 LSP（分（分别来自网来自网络 10.9.0.0/16 和网和网络 10.10.0.0/16），因），因为 SPF 已已经获悉悉这些些链路并已将它路并已将它们添加到了添加到了 SPF 树中。中。通通过第三个第三个 LSP，R1 可可获悉悉 R5 带有一个网有一个网络 10.11.0.0/16，该网网络的开的开销为 2，且，且 R5 在在该网网络上无上无邻居。此居。此链路被添加到路被添加到 R1 的的 SPF 树中。中。例例:R1:R1 构建构建 SPF SPF 树的过程树的过程网络 10.5.0.0/16：通过 R2，serial 0/0/0，开销为 22网络 10.6.0.0/16：通过 R3，serial 0/0/1，开销为 7网络 10.7.0.0/16：通过 R3，serial 0/0/1，开销为 15网络 10.8.0.0/16：通过 R3，serial 0/0/1，开销为 17网络 10.9.0.0/16：通过 R2，serial 0/0/0，开销为 30网络 10.10.0.0/16：通过 R3，serial 0/0/1，开销为 25网络 10.11.0.0/16：通过 R3，serial 0/0/1，开销为 27SPF 算法在构建算法在构建 SPF 树的同时便会确定最短树的同时便会确定最短路径。路径。链路链路 10.4.0.0/16 和链路和链路 10.9.0.0/16 未用于访问未用于访问其它网络，因为存在开销更低（即更短）的路径其它网络，因为存在开销更低（即更短）的路径SPFSPF（最短路径优先）树构建过程（最短路径优先）树构建过程由由 SPF 树生成路由表树生成路由表SPFSPF（最短路径优先）树构建过程（最短路径优先）树构建过程链路状态路由协议的优点链路状态路由协议的优点是是基本事件驱基本事件驱动更新动更新快快是是是是链路状态链路状态否否基本周期更基本周期更新新慢慢否否否否距离矢量距离矢量 使用使用LSP更新方式更新方式收敛时间收敛时间路由器自行路由器自行判断到每一判断到每一个网络的最个网络的最短路径短路径创建拓扑创建拓扑图图路由协议路由协议链路状态路由协议的要求链路状态路由协议的要求现代链路状态路由协议设计旨在尽量降现代链路状态路由协议设计旨在尽量降低对内存、低对内存、CPU 和带宽的影响和带宽的影响使用并配置使用并配置多个区域多个区域可减小链路状态数可减小链路状态数据库据库链路状态路由协议的要求链路状态路由协议的要求与距离矢量路由协议相比，链路状态路由与距离矢量路由协议相比，链路状态路由协议通常需要占用更多的内存、协议通常需要占用更多的内存、CPU 运算运算量和带宽量和带宽链路状态数据包泛洪会对网络的可用带宽链路状态数据包泛洪会对网络的可用带宽产生负面影响。这只应该出现在路由器初产生负面影响。这只应该出现在路由器初始启动过程中，但在不稳定的网络中也可始启动过程中，但在不稳定的网络中也可能导致问题。能导致问题。完