TCPIP路由技术课件：第4章 动态路由选择协议

1第4章动态路由选择协议2本章包括的主题路由选择协议基础距离矢量路由选择协议链路状态路由选择协议内部和外部网关协议34.1路由选择协议基础路由算法至少应指明以下内容向其他路由器发送网络可达性的过程从其它路由器接收可达性信息的过程基于现有可达性信息决策最优路由和记录路由的过程响应、修正和通告网络中拓扑变化的过程44.1.2路径决策问题1：路由器A是否应该将路由器C的数据包信息传递给路由器B,还是将路由器B的路由选择信息包传递给路由器C呢?54.1.2路径决策问题2：如果路由器A从路由器B和路由器C那里知道网络192.168.4.0,那么为了到达该网络应该使用哪一台路由器呢?它们都合法吗?谁是最优路径呢?64.1.2路径决策问题3：什么机制可以确保所有路由器能接收到所有的路由选择信息,而且这种机制还可以阻止更新数据包在网络中无休止地循环下去呢?2022/11/1074.1.2路径决策问题4：如果路由器共享某个直连网络（192.168.1.0、192.168.3.0和192.168.6.0）,那么路由器是否仍旧应该通告这些网络呢?84.1.1度量为什么需要度量当有多条路径到达相同目标网络时,路由器需要一种机制来计算最优路径度量是指派给路由的一种变量，可以路由进行等级划分不同路由选择协议使用不同的度量94.1.2度量可用于计算的度量的参数跳数：记录路由器跳数带宽：通常选择高带宽链路负载：反应流量占用沿途链路带宽的数量时延：数据包经过一条路径所花费的时间可靠性：用来测量链路在某种情况下发生故障的可能性代价：由管理员设置，反应更优或更差路由，是一个描述无量纲度量的术语104.1.3收敛所有路由表都达到一致的过程叫收敛全网内路由器间信息共享及计算最优路径所花费的时间总和就是收敛时间收敛过程1、链路发生故障,直连路由器都从数据链路协议获知链路故障2、直连路由器通知它们的邻居该链路不再可用3、邻接路由器立即更新路由表并通知它们的邻居4、这个过程一直持续到所有路由器都知道此变化为止114.1.3收敛124.2距离矢量路由选择协议大多数距离矢量算法以Bellman-Ford和Fulkerson工作为基础依照传闻进行路由选择常见的距离矢量路由协议IP路由选择信息协议(R1P)Xerox网络系统的XNSRIPNovell的IPXRIPCocosystems的Internet网关路由选择协议(IGRP)和增强型Internet网关路由协议(ElGRP)

DEC的DNA阶段4AppleTalk的路由选择表维护协议(RTNIP)134.2.1通用属性定期更新每经过特定时间就发送更新信息，从10~90s邻居共享相同链路的路由器广播更新路由器通过向广播地址发送更新信息来宣布自己的存在不关心路由更新信息的主机和其他设备丢弃该包全路由选择表更新告诉邻居它所知道的一切14以跳数为度量154.2.3路由失效计时器情景描述网络10.1.5.0没有故障，路由器D故障路由器A、B、C将把数据发向一个不可达的网络解决办法为每个路由表项设置失效计时器每隔一定时间间隔都会收到表项的更新信息，复位该计时器3~6个更新周期未收到更新，将使该路由无效164.2.4水平分隔情景描述--距离矢量算法的漏洞D监测到10.1.5.0故障D将该网络标记为不可达并在下一更新周期通知C意外发生，D更新触发前，收到C的更新，C声称自己到达10.1.5.0的距离为1D采纳C的建议，标记到达10.1.5.0的距离为2

（注意，此时D-C间路由环路产生）174.2.4水平分隔逆向路由路由的指向与数据包流动方向相反的路由水平分隔在两台路由器直接阻止逆向路由的技术两类水平分隔方法简单水平分隔法规则：从某接口发送的更新信息不能包含从该接口收到的更新所包含的网络(即：我告诉你的，你不能再告诉我)184.2.4水平分隔两类水平分隔方法毒性逆转水平分隔法规则：当更新信息被发送出某接口时，信息中将指定从该接口收到的更新信息中获取的网络是不可达的194.2.4水平分隔两类水平分隔方法毒性逆转对比简单水平分隔法优点：更健壮---“坏消息总比没有消息好”缺点：路由更新包更大了204.2.5计数到无穷大水平分隔法的局限切断了邻居间的环路，却无法隔断网络中的环路214.2.6触发更新触发更新又叫快速更新，如果一个度量变好或变坏，路由器则不等定期更新计时超时，立即发送更新消息优点大大减少无穷计算引发的问题缺点定期更新和触发更新一起发生，路由器可能会在收到触发更新的正确信息之后又收到来自未收敛路由器的错误信息改进更新信息中仅包括实际触发该事件的网络，而不是包括整个路由表224.2.7抑制计时器目的为了降低接受错误路由选择信息的可能性抑制路由如果到一个目标的距离增加（例如，跳数由2增加到4），那么路由器将为该路由设置抑制计时器。直到计时器超时，路由器才可以接受有关此路由的更新信息23下面两种方法维持异步更新每台路由器的更新计时器独立于路由选择进程,因而不会受到路由器处理负载的影响在每个更新周期中加入一个小的随机时间或定时抖动作为偏移。4.2.8异步更新244.3链路状态路由选择协议链路状态协议有时叫最短路径优先协议或分布式数据库协议，是围绕着图论中的一个著名算法—Dijkstra的最短路径算法设计的基本思路链路状态路由器从对等路由器那里获取第一手信息。每台路由器会产生一些关于自已的本地直连链路、这些链路的状态和所有直接相连邻居的信息。这些信息汇总成链路状态数据库,每台路由器都做一份拷贝，每台路由器独立地计算各自的最优路径,但是决不改动信息254.3链路状态路由选择协议工作流程步骤1：建立邻接关系步骤2：通过洪泛向邻居发送LSA（见备注！），每台路由器的链路都会产生一个LSA，用于标识这条链路、链路状态、路由器接口到链路的代价度量值以及链路所连接的所有邻居步骤3：每台路由器备份收到的LSA步骤4：依据LSA数据库，Dijkstra算法计算最短路径264.3.1邻接关系建立发现邻居通过hello协议，邻居路由器之间交换数据包Hello数据包至少应包含一个路由器ID和发送数据包的网络地址路由器ID：可以是路由器的一个接口的IP地址数据包的其他字段可以携带子网掩码、Hello间隔、线路类型描述符和帮助建立邻居关系的标记274.3.2链路状态泛洪扩散洪泛的工作过程LSA被发送给每个邻居，并依次向每个邻居的邻居再转发,除了发送该LSA的邻居284.3.2链路状态泛洪扩散洪泛扩散中的尴尬294.3.2链路状态泛洪扩散解决方案序列号线性序列号空间循环序列号空问序列号的隐患路由器根据自己已收到数据包的序列号，来判断新到数据包的新旧，丢弃旧的，接收新的如果数据包传输过程序列号出错了304.3.2链路状态泛洪扩散老化为洪泛扩散过程增加另一层可靠性LSA格式中包含年龄字段，LSA创建时，该字段为0扩散过程中，每台路由器修改并增加LSA中的年龄定义一个最大年龄差（MaxAgeDiff）如果收到的LSA序列号相同，年龄差小于MaxAgeDiff，说明正常的网络延迟造成了年龄的差异，因此路由器中原有的LSA保存，且不扩散新到LSA年龄差大于MaxAgeDiff，说明网络异常，因此新的LSA被记录，且被扩散（注：ospf的MaxAgeDiff为15min）LSA驻留在数据库中，则年龄会不断增加，如果增加到某个最大值MaxAge,则带有MaxAge的LSA扩散至所有邻居，邻居随即删除相关记录为防止LSA年龄到达MaxAge，链路状态刷新计时器可以复位MaxAge314.3.3链路状态数据库LSA中序列号、年龄和其他信息,主要用于管理泛洪扩散进程LSA还包括两类通用信息路由器链路信息——使用三元组(路由器ID、邻居ID、代价)通告路由器的邻居路由器,这里的代价是指链路到邻居的代价。末梢网络信息——使用三元组(路由器ID、网络ID、代价)通告路由器直接连接的末梢网络(没有邻居的网络)。SPF算法如何利用这两类通用信息对路由器链路信息进行一次计算以建立到每台路由器的最短路径使用末梢网络信息向路由器添加网络32334.3.3链路状态数据库链路两端的代价并不一定要相同，代价和接口的出站方向有关344.3.3链路状态数据库链路两端的代价并不一定要相同，代价和接口的出站方向有关354.3.4SFP算法Dijkstra算法常常被认为是最短路径优先算法，具体参见《计算机网络》364.3.5区域链路状态协议的3个不利影响必要的数据库要求内存的数量比距离矢量协议更多复杂的算法要求CPU时间比距离矢量协议更多链路状态泛洪扩散数据包对可用带宽带来了不利的影响,特别是不稳定的网络解决方案将网络划分区域一个区域内的路由器仅需要在本区域扩散LSA，只需要维护本区域的链路状态数据库利用区域的链路状态协议可以节省系统资源37384.3.5区域区域边界路由器连接两个区域的路由器，同属于两个区域必须为每个区域维护各自的拓扑数据库区域之间的路由区域内的路由器仅需要知道怎样找到本区域的边界路由器即可区域边界路由器/区域内路由器之间的关系如同主机/路由器之间的关系394.4