距离矢量与链路状态路由协议分析

1、第第1212章章 距离矢量与链路状态路由协议分析距离矢量与链路状态路由协议分析 周小云周小云客支新员岗前培训系列教材客支新员岗前培训系列教材前前 言言 通过对本章内容的学习，你可以掌握距离矢量路通过对本章内容的学习，你可以掌握距离矢量路由协议和链路状态路由协议的基础知识，并了解这些由协议和链路状态路由协议的基础知识，并了解这些协议的算法和原理。协议的算法和原理。 提提 纲纲q距离矢量路由协议简介距离矢量路由协议简介q距离矢量路由协议分析距离矢量路由协议分析q链路状态路由协议简介链路状态路由协议简介q链路状态路由协议分析链路状态路由协议分析距离矢量路由协议简介距离矢量路由协议简介距离矢量 (Di

2、stance-Vector)距离矢量路由选择协议也称为B e l l m a n - F o r d协议。距离矢量路由协议主要有： RIPV1 , RIPV2 , IGRP距离矢量路由器定期向相邻的路由器发送它们的整个路由选择表(routing table)。距离相邻路由器在从相邻路由器接收到的信息的基础之上建立自己的路由选择信息表。距离矢量路由协议简介距离矢量路由协议简介距离矢量路由选择是一种路由选择协议算法。距离矢量路由协议有一个严重的缺点，缓慢的收敛时间过程会造成路由回路（Routing Loop）。解决路由回环方法：水平分割，定义最大跳数，毒性逆转，触发更新 ，抑制时间。水平分割（sp

3、lithorizon）:水平分割保证路由器记住每一条路由信息的来源，并且不在收到这条信息的端口上再次发送它。这是保证不产生路由循环的最基本措施。距离矢量路由协议简介距离矢量路由协议简介水平分割（splithorizon）:水平分割保证路由器记住每一条路由信息的来源，并且不在收到这条信息的端口上再次发送它。这是保证不产生路由循环的最基本措施。定义最大跳数:距离矢量路由协议定义了一个最大值，允许最大为15跳,16跳既为不可用。毒性逆转（poisonreverse）:当一条路径信息变为无效之后，路由器并不立即将它从路由表中删除，而是用16，即不可达的度量值将它广播出去。这样虽然增加了路由表的大小，但

4、对消除路由循环很有帮助，它可以立即清除相邻路由器之间的任何环路。距离矢量路由协议简介距离矢量路由协议简介触发更新（triggerupdate）: 当路由表发生变化时，更新报文立即广播给相邻的所有路由器，而不是等待30秒的更新周期。同样，当一个路由器刚启动RIP时，它广播请求报文。收到此广播的相邻路由器立即应答一个更新报文，而不必等到下一个更新周期。这样，网络拓扑的变化会最快地在网络上传播开，减少了路由循环产生的可能性。抑制计时（holddowntimer）: 一条路由信息无效之后，一段时间内这条路由都处于抑制状态，即在一定时间内不再接收关于同一目的地址的路由更新。如果，路由器从一个网段上得知一

5、条路径失效，然后，立即在另一个网段上得知这个路由有效。这个有效的信息往往是不正确的，抑制计时避免了这个问题，而且，当一条链路频繁起停时，抑制计时减少了路由的浮动，增加了网络的稳定性。距离矢量路由协议简介距离矢量路由协议简介真正的距离矢量路由协议只有RIPV1和RIPV2，因为它们只用到了HOP跳数做为唯一的计算路由的方法。IGRP是CISCO公司专有的动态距离矢量路由协议，它使用到了跳数，但是主要决定路由因数是链路带宽，延迟，负载，最大传输单元，设备可靠性，能力等。 提提 纲纲q距离矢量路由协议简介距离矢量路由协议简介q距离矢量路由协议分析距离矢量路由协议分析q链路状态路由协议简介链路状态路由

6、协议简介q链路状态路由协议分析链路状态路由协议分析距离矢量路由协议分析距离矢量路由协议分析距离矢量路由使用的是贝尔曼-福特路由算法：所有参加的路由器周期性地向外广播路由刷新报文，主要是由很多路由项（entry）组成的路由刷新报文。对路由来说，最主要的内容是目的地址和下一跳地址（next hop）。 距离矢量路由协议分析距离矢量路由协议分析距离矢量路由在设计时，每个路由器管理了一个路由数据库，该路由数据库为系统中所有可能的信宿包含一个路由项，并为每个信宿保留如下信息：目的地址：在算法的IP实现中，这指的是主机或网络的IP 地址。下一跳地址：到信宿的路由中的第一个路由器。距离矢量路由协议分析距离矢

7、量路由协议分析接口：用于到下一跳物理网络。metric值：一个数，指明本路由器到信宿的开销。定时器：路由项最后一次被修改的时间。路由标记：区分路由为内部路由协议的路由还是外部路由协议的路由的标记。 距离矢量路由协议分析距离矢量路由协议分析距离矢量路由协议中，数据库由与系统直接相连的实体的描述初始化，通过从相邻路由器受到的报文修改维护。路由器间交换的最重要的信息是修改报文，参加路由维护计划的路由器发送当前存在于实体的描述路由数据库的路由修改报文。仅通过相邻路由器间交换路由信息是可以维护整个系统的最佳路由的。 距离矢量路由协议分析距离矢量路由协议分析距离矢量算法总是基于一个这样的事实：路由数据库中

8、的路由已是目前通过报文交换而得到的最佳路由。同时，报文交换仅限于相邻的实体间，也就是说，实体共享同一个网络。当然，要定义路由是最佳的，就必须有衡量的办法，这就用到前面所说的“metric”。 距离矢量路由协议分析距离矢量路由协议分析在距离矢量路由协议中，通常用可行路由所经的路由器数简单地计算metric值。在复杂的网络中，metric一般代表该路由传输数据报的延迟或其它发送开销。具体地说，距离矢量算法如下所述： 距离矢量路由协议分析距离矢量路由协议分析令D(i,j)代表从实体i到实体j的最佳路由的metric值，d（i，j）代表从i直接到j的开销，因为开销是可加的，算法中最佳路由如此获取表示：

9、D（i，i）=0，对所有的iD（i，j）=MINd（i，j）+D（k，j），当i不等于k时实体i从相邻路由器k收到k到j的开销的估计D(i，j)，i将D（i，j）加上i到k的开销估计d（i，j），i比较从所有相邻路由器得到的数值，取得最小数，就得到了它到j的最佳路由。距离矢量路由协议分析距离矢量路由协议分析首先，路由器刚启动时，对距离矢量路由表（V-D路由表）进行初始化，该初始化路由表包含所有去往与本路由器直接相连的网络的路径。由于去往直接相连的网络不经过中间路由器，所以初始化的V-D路由表中的各路由的距离均为0。图2.1初始V-D路由表的一个示例。 距离矢量路由协议分析距离矢量路由协议分析距

10、离矢量路由协议分析距离矢量路由协议分析各路由器周期性地向外广播其V-D路由表内容。与某路由器直接相连的（位于同一物理网络）的路由器收到该路由表报文后，根据此报文对本地路由表进行刷新。刷新时，路由器逐项检查来自相邻路由器的V-D报文，遇到下述情况之一，须修改本地路由表（假设路由器Gi收到路由器Gj的V-D报文）： 距离矢量路由协议分析距离矢量路由协议分析1)Gj列出的某表目Gi路由表中没有。则Gi路由表中须增加相应表目，其“信宿”是Gj表目中的信宿，其“路径”为“Gj”（即下一路由器为Gj）。2)Gj去往某信宿的距离值比Gi去往该信宿的距离减1还小。这种情况说明，Gi去往某信宿若经过Gj，距离会

11、更短。则Gi修改本表目，其中“信宿”域不变，“距离”为Gj表目中距离加1，“路径”为“Gj”。距离矢量路由协议分析距离矢量路由协议分析3)Gi去往某信宿的路由经过Gj，而Gj去往该信宿的路由发生变化。这里分两种情况：Gj的V-D表不再包含去往某信宿的路由，则GI中相应路由须删除。Gj的V-D表中去往某信宿的路由距离发生变化，则Gi中相应表目“距离”须修改，以Gj中的“距离”加1取代原来的距离。距离矢量路由协议分析距离矢量路由协议分析这里要特别强调的是，V-D算法的路由刷新发生在相邻路由器之间，所以V-D报文不一定以广播方式发送出去，我们可以对V-D报文进行优化，让路由器直接向相邻路由器发送V-

12、D报文，不必采用广播方式。距离矢量路由选择协议在IANA网络中(主网络)边界进行汇总,这是根据首字节规则实现的 。 提提 纲纲q距离矢量路由协议简介距离矢量路由协议简介q距离矢量路由协议分析距离矢量路由协议分析q链路状态路由协议简介链路状态路由协议简介q链路状态路由协议分析链路状态路由协议分析链路状态路由协议简介链路状态路由协议简介链路状态协议也叫最短路径优先协议或分布式数据库协议。链路状态协议有一下一些：1、 IP开放式最短路径优先OSPF2、 CLNS或IP ISO的中介系统IS-IS3、 DEC的DNA阶段54、 Novell的netware链路服务协议NLSP链路状态路由协议简介链路状

13、态路由协议简介链路状态协议的步骤：步骤1：每台路由与他的邻居间建立联系，这种联系叫做邻接关系。步骤2：每台路由向每个邻居发送链路状态通告(LSA)，有时也叫链路状态报文(LSP)。每台链路都会生成一个LSA，LSA用于标识这条链路、链路状态、路由器接口到链路的代价度量值以及链路所连接的所有邻居。每个邻居收到公告后要依次向他的邻居转发这些通告（泛洪）步骤3：每台路由要在数据库中保存一份所收到的LSA，如所有工作正常所有路由的数据库应该是相同的。步骤4：完整的拓扑数据库也叫做链路状态库。链路状态路由协议简介链路状态路由协议简介链路状态路由选择协议的目的是映射互连网络的拓扑结构，它是一种比距离矢量更

14、复杂的路由选择协议，目前最流行的动态路由协议就是一种链路状态协议：OSPF 。OSPF的普及因为多协议标签交换（MPLS）的出现而更流行。链路状态路由协议主要有： OSPF , IS-IS链路状态路由协议简介链路状态路由协议简介链路状态路由协议是目前使用最广的一类域内路由协议。它采用一种“拼图”的设计策略，即每个路由器将它到其周围邻居的链路状态向全网的其他路由器进行广播。这样，一个路由器收到从网络中其他路由器发送过来的路由信息后，它对这些链路状态进行拼装，最终生成一个全网的拓扑视图，近而可以通过最短路径算法来计算它到别的路由器的最短路径。 提提 纲纲q距离矢量路由协议简介距离矢量路由协议简介q

15、距离矢量路由协议分析距离矢量路由协议分析q链路状态路由协议简介链路状态路由协议简介q链路状态路由协议分析链路状态路由协议分析链路状态路由协议分析链路状态路由协议分析链路状态路由协议(link-state routing protocol)的特征:1.对网络发生的变化能够快速响应2.当网络发生变化的时候发送触发式更新(triggered update)3.发送周期性更新(链路状态刷新),间隔时间为30分钟链路状态路由协议只在网络拓扑发生变化以后产生路由更新.当链路状态发生变化以后,检测到变化的设备创建。链路状态路由协议分析链路状态路由协议分析链路状态含义链路（Link）指的是路由之间的连接，即路

16、由器之间的物理连接（介质），逻辑链路是通过这种连接建立的。链路状态路由选择协议在链路状态发生变化时，在路由器之间发送有关链路的信息。因此，当路由器A和路由器B之间的连接发生故障后，路由器A和路由器B将发送一条更新，以告诉整个网络：路由器A和路由器B之间出现了故障。链路状态路由协议分析链路状态路由协议分析LSA(link state advertisement),通过使用组播地址传送给所有的邻居设备,然后每个设备拷贝一份LSA,更新它自己的链路状态数据库(link state database,LSDB),接着再转发LSA给其他的邻居设备.这种LSA的洪泛(flooding)保证了所有的路由设备

17、在更新自己的路由表之前更新它自己的LSDB。链路状态路由协议分析链路状态路由协议分析LSDB通过使用Dijkstra算法(该算法累积路径长度,以建立最短路径优先数,常在链路状态路由选择协议中用来决定使用哪条路由 )来计算到达目标网络的最佳路径,建立一条SPF树(tree),然后最佳路径从SPF树里选出来,被放进路由表里.过程如下图: 链路状态路由协议分析链路状态路由协议分析链路状态路由协议分析链路状态路由协议分析OSPF和IS-IS协议被归类到链路状态路由协议中.链路状态路由协议在一个特定的区域(area)里从邻居处收集网络信息,一旦路由信息都被收集齐以后,每个路由器开始通过使用Dijkstr

18、a算法(SPF)独立计算到达目标网络的最佳路径。链路状态路由协议分析链路状态路由协议分析链路状态协议的工作方式链路状态协议的工作方式 工作方式： 1.发送HELLO包，建立邻接关系 2.同步链路状态数据库 3.使用SPF算法生成最短路径优先树 4.将计算结果写入路由表 在链路状态路由协议中，所有路由器所记录的链路数据库都是一致的 链路状态路由协议分析链路状态路由协议分析链路状态协议使用hello协议，来与同一链路上的其他路由器建立邻接关系，并维护这种关系。这是一种面向连接的交换。路由器之间通过交换路由选择更新使其路由选择表同步后，他们便成了邻接邻居（adjacent neighbor)。只要路

19、由器彼此之间能够收到对方的Hello分组，这种邻接关系便保持不变。要建立邻接关系，两台路由器的子网掩码和Hello定时器值必须相同。链路状态路由协议分析链路状态路由协议分析链路状态协议中，由于邻居的关系是持续的，因此路由选择进程之间能够快速、高效地交换信息。所以，网络中的链路发生变化后，将很快被知道。路由器能迅速知道邻居（同时可能也是下一跳）是否失效，因为如果邻居失效，路由器将收不到Hello消息。链路状态路由协议分析链路状态路由协议分析路由选择协议发现问题后，立刻发送一条消息，而无需等待定时器到期。这也被称为触发更新，这是一条增量更新，因为它只包含网络变化的信息。通过使用增量更新，提高了网络

20、的会聚速度，同时减少了需要通过网络发送的信息量。这减轻了物理介质上的网络开销，将更多的带宽留给了用户数据。链路状态路由协议分析链路状态路由协议分析hello报文结构如下： 路由器ID *区域ID *接口的子网掩码 *认证类型 *HELLO间隔 链路状态路由协议分析链路状态路由协议分析*无效时间 优先级 DR和BDR 邻居列表 只有在同一物理网络上的路由器对以上所有标记为“*”的项目匹配，两个路由器才可能建立邻接关系 链路状态路由协议分析链路状态路由协议分析链路状态路由协议用于大型网络中，因为它们更新路由选择表的方法占用的网络资源较少。链路状态路由协议通过以下方法来降低网络开销：1.使用多播地址；2.发送触发更新；3.偶尔发送有关网络的摘要；4.每台路由器都使用小型分组来描述其本地连接性，而不是发送整个路由表。链路状态路由协议分析链路状态路由协议分析距离矢量路由选择协议和链路状态路由选择协议