一。 向量距离( V-D) 算法
1) 向量距离算法的两个基本要素在向量距离算法中有 两个基本的要素,一个向量,另一个为距离 。 这两个要素构成了动态路由表的基本元素结构 。
向量是指源路由器去目的网络的路径 。 这里的路径是指源路由器去目的网络途径中,首先应把包传递给它的那个相邻路由器,至于相邻路由器为达到目的网络接着把包再传给下面哪一个路由器,源路由器是不关心的 。 一个路由器经与所有相邻路由器的层层连接,构成了去所有目的网络的路径拓扑构图 。 距离是向量距离算法选择最佳路径的一种度量规划
,即度规 ( metrics) 。 可把源站到目的站中间经过的路由器数 ( 下跳数 hop) 为最小作为度量最佳路径的唯一权值 。
事实上,距离也可以用延迟来作权度量,也可以由网络延迟,带宽,可靠性,负载等多种权值综合来决定 。
2)向量距离算法的路由表的形成向量距离算法路由表的形成和刷新的 基本思想是,路由器启动时,首先从其各端口 获取所连网络的网络号信息而形成初始路由表,然后 定期 向相邻路由器广播路由消息。某路由器收到的相邻路由器发来的路由表信息中,如果 有一部分是记录了经相邻路由器能到达的网络而该路由器路由表中没有,
则增加之; 如果 有去某个目的网络更佳的路径,则修改之; 如果 原有经相邻路由器可以到达目的网络而现在因故相邻路由器不能到达,则该路由器的路由表也要作相应修改。
RIP协议就是采用的向量距离算法,它 每 30秒 向相邻路由器广播一次。
( 3)向量距离算法的基本特点向量距离算法 要求 网络中每台路由器都定期的将其路由表信息向其相邻的路由器广播。随着信息经层层相邻路由器涌动式的传播,每台路由器最终能获得到达网络中其他所有目标网络的信息,并计算出所有的相应距离。
由于每次刷新发生在相邻路由器之间,而再通过相邻路由器层层涌动式传播,所以过程非常缓慢,在大型的互连网环境中容易发生远近路由器路由表中的路径不一致的问题,并且互连网规模越大,每台路由器再广播的路由表信息就越多,而其中许多信息与真正要刷新的内容无关,因此在环境剧烈变化的互连网中开销会更大。
向量距离算法的优点是易于实现,但它不适应环境剧烈变化或大型的网际环境。
收到相邻路由器(其地址为 X) 的一个 RIP 报文:
(1) 先修改此 RIP 报文中的所有项目:将,下一跳,
字段中的地址都改为 X,并将所有的,距离,字段的值加 1。
(2) 对修改后的 RIP 报文中的每一个项目,重复以下步骤:
若项目中的目的网络不在路由表中,则将该项目加到路由表中。
否则 若下一跳字段给出的路由器地址是同样的,
则将收到的项目替换原路由表中的项目。
否则 若收到项目中的距离小于路由表中的距离,
则进行更新,
否则,什么也不做。
(3) 若 3 分钟还没有收到相邻路由器的更新路由表,
则将此相邻路由器记为不可达的路由器,即将距离置为
16(距离为 16表 示不可达)。
(4) 返回二。链路状态( L-S) 算法链 路 状 态 算 法 又 称 最 短 路 径 优 先 ( SPF,
Shortest Path First) 算法 。 著名的 OSPF( 开放式最短路径优先 ) 协议就是采用这类算法 。
链路状态算法的基本思想是,每台路由器在 启动时 首先获得链路状态元素;每台路由器定期向互连网上所有的路由器广播链路状态广告 ( LSA) ; 每台路由器累积 LSA后 形成拓扑结构数据库,并以此算出本路由器去目的网络的最佳路径 。
(1)链路状态这里链路是指连接路由器的网络;状态是指相邻路由器是开通还是关断 。 所以 链路状态是指 一台路由器所连的网络和相邻路由器是开还是关的状态,链路状态反映了一台路由器最基本的网络拓扑结构 。
( 2)链路状态广告( LSA)
链路状态广告( LSA,Link State
Advertisements) 包含了一台路由器最基本的网络拓扑结构信息。当一台路由器的相邻路由器状态发生变化时,即该路由器的物理链路状态发生变化时会很快检查出来,该路由器就会向互连网中所有的路由器广播 LSA报文。 LSA报文广播的是路由更新消息。 每台路由器 周期性地发送 LSA报文
,以保证拓扑数据库的同步。
一台路由器所发的 LSA是向全网所有路由器广播的,而不是仅局限于相邻路由器。
( 3)拓扑结构数据库每台路由器接收互连网中所有其他路由器发来的 LSA报文,不断积累并归入到该路由器的拓扑结构数据库中。 每台路由器根据拓扑结构数据库即能用一定算法计算出去所有目的网络的最佳途径。
拓扑结构数据库 反映了整个互连网的拓扑结构图,在互连网中所有路由器中的拓扑结构数据库都是相同的。 但是互连网中各路由器都是分别以本路由器作为源站点计算路径的,即是以本路由器作为树根,计算出一棵最短路径树,所以各路由器最终产生的路由表是各不相同的。
三。 向量距离算法与链路状态算法的比较向量距离算法 定期 ( 如每 30秒 ) 将 路由表的全部或部分送给与其相邻的每个路由器,其中许多并不是刷新所需要的信息,
而且随着网际规模的扩大,路由表信息量也随之增大 。
而链路状态算法 只是在事件发生时 才发送的 LSA报文只是一个路由器小的局部链路状态变化信息,而且 LSA报文大小与网际规模的大小无关 。
向量距离算法的路由表信息只传给相邻的路由器,在相邻路由器更新路由表后再传给下一个相邻的路由器,这种 层层涌动式 的传播刷新过程是相当缓慢的,容易造成远近路由器路径不一致的问题,并且会导致慢收敛( P125上)。
(说明:收敛时间是指从网络的拓扑结构发生变化到网络上所有的相关路由器都得知这一变化,并且相应地做出改变所需要的时间。这一时间越短,网络变化对全网的扰动就越小。收敛时间过长会导致路由循环的出现。)
而链路状态算法的 LSA报文 一次性无修改地 向全网广播
,保证了全网所有路由器的拓扑结构数据库的一致性。链路状态算法是 以每台路由器本身作为路径树根 计算出本路由器的最佳路径,并单向传送,所以不会导致像向量距离算法那样的慢收敛。简而言之,向量距离算法是将全网路由器的情况告诉相邻路由器,而链路状态算法是将相邻路由器的情况告诉全网的路由器。 所以,链路状态算法比向量距离算法更适宜大规模网际和激烈变化的网际环境。
RIP是使用广泛的 IP路由选择算法之一,它实现了向量距离算法,并使用跨度计算标准,0个跨度是直接连接的局域网,1个跨度是通过一个路由器可达,2个跨度是通过两个路由器可达,依此类推。 但
15个跨度被认为是最大极限,表示无穷距离,意即不可达。
OSPF是一个现代的链路状态协议,每个路由器将它所连接的链路状态信息向其他路由器传播。 链路状态机制解决了向量距离产生的许多收敛问题,
适用可伸缩的环境。
OSPF还有若干其他先进特征:身份验证;路由选择服务类型;负载平衡;子网划分;内部和外部网关表。
—— RIP路由协议路由收敛较慢。 RIP路由协议周期性地将整个路由表作为路由信息广播至网络中,该广播周期为 30秒。在一个较为大型的网络中,RIP协议会产生很大的广播信息,占用较多的网络带宽资源;并且由于 RIP协议 30秒的广播周期,影响了 RIP路由协议的收敛,甚至出现不收敛的现象。而 OSPF是一种链路状态的路由协议,当网络比较稳定时,网络中的路由信息是比较少的,并且其广播也不是周期性的,因此
OSPF路由协议即使是在大型网络中也能够较快地收敛
。
—— OSPF路由协议支持路由验证,只有互相通过路由验证的路由器之间才能交换路由信息。并且 OSPF可以对不同的区域定义不同的验证方式,提高网络的安全性。
RIP路由协议中用于表示目的网络远近的唯一参数为跳( HOP),也即到达目的网络所要经过的路由器个数。在 RIP路由协议中,该参数被限制为最大 15,
也就是说 RIP路由信息最多能传递至第 16个路由器;
对于 OSPF路由协议,路由表中表示目的网络的参数为
Cost,该参数为一虚拟值,与网络中链路的带宽等相关,也就是说 OSPF路由信息不受物理跳数的限制。并且,OSPF路由协议还支持 TOS( Type of Service) 路由,因此,OSPF比较适合应用于大型网络中。
1) 向量距离算法的两个基本要素在向量距离算法中有 两个基本的要素,一个向量,另一个为距离 。 这两个要素构成了动态路由表的基本元素结构 。
向量是指源路由器去目的网络的路径 。 这里的路径是指源路由器去目的网络途径中,首先应把包传递给它的那个相邻路由器,至于相邻路由器为达到目的网络接着把包再传给下面哪一个路由器,源路由器是不关心的 。 一个路由器经与所有相邻路由器的层层连接,构成了去所有目的网络的路径拓扑构图 。 距离是向量距离算法选择最佳路径的一种度量规划
,即度规 ( metrics) 。 可把源站到目的站中间经过的路由器数 ( 下跳数 hop) 为最小作为度量最佳路径的唯一权值 。
事实上,距离也可以用延迟来作权度量,也可以由网络延迟,带宽,可靠性,负载等多种权值综合来决定 。
2)向量距离算法的路由表的形成向量距离算法路由表的形成和刷新的 基本思想是,路由器启动时,首先从其各端口 获取所连网络的网络号信息而形成初始路由表,然后 定期 向相邻路由器广播路由消息。某路由器收到的相邻路由器发来的路由表信息中,如果 有一部分是记录了经相邻路由器能到达的网络而该路由器路由表中没有,
则增加之; 如果 有去某个目的网络更佳的路径,则修改之; 如果 原有经相邻路由器可以到达目的网络而现在因故相邻路由器不能到达,则该路由器的路由表也要作相应修改。
RIP协议就是采用的向量距离算法,它 每 30秒 向相邻路由器广播一次。
( 3)向量距离算法的基本特点向量距离算法 要求 网络中每台路由器都定期的将其路由表信息向其相邻的路由器广播。随着信息经层层相邻路由器涌动式的传播,每台路由器最终能获得到达网络中其他所有目标网络的信息,并计算出所有的相应距离。
由于每次刷新发生在相邻路由器之间,而再通过相邻路由器层层涌动式传播,所以过程非常缓慢,在大型的互连网环境中容易发生远近路由器路由表中的路径不一致的问题,并且互连网规模越大,每台路由器再广播的路由表信息就越多,而其中许多信息与真正要刷新的内容无关,因此在环境剧烈变化的互连网中开销会更大。
向量距离算法的优点是易于实现,但它不适应环境剧烈变化或大型的网际环境。
收到相邻路由器(其地址为 X) 的一个 RIP 报文:
(1) 先修改此 RIP 报文中的所有项目:将,下一跳,
字段中的地址都改为 X,并将所有的,距离,字段的值加 1。
(2) 对修改后的 RIP 报文中的每一个项目,重复以下步骤:
若项目中的目的网络不在路由表中,则将该项目加到路由表中。
否则 若下一跳字段给出的路由器地址是同样的,
则将收到的项目替换原路由表中的项目。
否则 若收到项目中的距离小于路由表中的距离,
则进行更新,
否则,什么也不做。
(3) 若 3 分钟还没有收到相邻路由器的更新路由表,
则将此相邻路由器记为不可达的路由器,即将距离置为
16(距离为 16表 示不可达)。
(4) 返回二。链路状态( L-S) 算法链 路 状 态 算 法 又 称 最 短 路 径 优 先 ( SPF,
Shortest Path First) 算法 。 著名的 OSPF( 开放式最短路径优先 ) 协议就是采用这类算法 。
链路状态算法的基本思想是,每台路由器在 启动时 首先获得链路状态元素;每台路由器定期向互连网上所有的路由器广播链路状态广告 ( LSA) ; 每台路由器累积 LSA后 形成拓扑结构数据库,并以此算出本路由器去目的网络的最佳路径 。
(1)链路状态这里链路是指连接路由器的网络;状态是指相邻路由器是开通还是关断 。 所以 链路状态是指 一台路由器所连的网络和相邻路由器是开还是关的状态,链路状态反映了一台路由器最基本的网络拓扑结构 。
( 2)链路状态广告( LSA)
链路状态广告( LSA,Link State
Advertisements) 包含了一台路由器最基本的网络拓扑结构信息。当一台路由器的相邻路由器状态发生变化时,即该路由器的物理链路状态发生变化时会很快检查出来,该路由器就会向互连网中所有的路由器广播 LSA报文。 LSA报文广播的是路由更新消息。 每台路由器 周期性地发送 LSA报文
,以保证拓扑数据库的同步。
一台路由器所发的 LSA是向全网所有路由器广播的,而不是仅局限于相邻路由器。
( 3)拓扑结构数据库每台路由器接收互连网中所有其他路由器发来的 LSA报文,不断积累并归入到该路由器的拓扑结构数据库中。 每台路由器根据拓扑结构数据库即能用一定算法计算出去所有目的网络的最佳途径。
拓扑结构数据库 反映了整个互连网的拓扑结构图,在互连网中所有路由器中的拓扑结构数据库都是相同的。 但是互连网中各路由器都是分别以本路由器作为源站点计算路径的,即是以本路由器作为树根,计算出一棵最短路径树,所以各路由器最终产生的路由表是各不相同的。
三。 向量距离算法与链路状态算法的比较向量距离算法 定期 ( 如每 30秒 ) 将 路由表的全部或部分送给与其相邻的每个路由器,其中许多并不是刷新所需要的信息,
而且随着网际规模的扩大,路由表信息量也随之增大 。
而链路状态算法 只是在事件发生时 才发送的 LSA报文只是一个路由器小的局部链路状态变化信息,而且 LSA报文大小与网际规模的大小无关 。
向量距离算法的路由表信息只传给相邻的路由器,在相邻路由器更新路由表后再传给下一个相邻的路由器,这种 层层涌动式 的传播刷新过程是相当缓慢的,容易造成远近路由器路径不一致的问题,并且会导致慢收敛( P125上)。
(说明:收敛时间是指从网络的拓扑结构发生变化到网络上所有的相关路由器都得知这一变化,并且相应地做出改变所需要的时间。这一时间越短,网络变化对全网的扰动就越小。收敛时间过长会导致路由循环的出现。)
而链路状态算法的 LSA报文 一次性无修改地 向全网广播
,保证了全网所有路由器的拓扑结构数据库的一致性。链路状态算法是 以每台路由器本身作为路径树根 计算出本路由器的最佳路径,并单向传送,所以不会导致像向量距离算法那样的慢收敛。简而言之,向量距离算法是将全网路由器的情况告诉相邻路由器,而链路状态算法是将相邻路由器的情况告诉全网的路由器。 所以,链路状态算法比向量距离算法更适宜大规模网际和激烈变化的网际环境。
RIP是使用广泛的 IP路由选择算法之一,它实现了向量距离算法,并使用跨度计算标准,0个跨度是直接连接的局域网,1个跨度是通过一个路由器可达,2个跨度是通过两个路由器可达,依此类推。 但
15个跨度被认为是最大极限,表示无穷距离,意即不可达。
OSPF是一个现代的链路状态协议,每个路由器将它所连接的链路状态信息向其他路由器传播。 链路状态机制解决了向量距离产生的许多收敛问题,
适用可伸缩的环境。
OSPF还有若干其他先进特征:身份验证;路由选择服务类型;负载平衡;子网划分;内部和外部网关表。
—— RIP路由协议路由收敛较慢。 RIP路由协议周期性地将整个路由表作为路由信息广播至网络中,该广播周期为 30秒。在一个较为大型的网络中,RIP协议会产生很大的广播信息,占用较多的网络带宽资源;并且由于 RIP协议 30秒的广播周期,影响了 RIP路由协议的收敛,甚至出现不收敛的现象。而 OSPF是一种链路状态的路由协议,当网络比较稳定时,网络中的路由信息是比较少的,并且其广播也不是周期性的,因此
OSPF路由协议即使是在大型网络中也能够较快地收敛
。
—— OSPF路由协议支持路由验证,只有互相通过路由验证的路由器之间才能交换路由信息。并且 OSPF可以对不同的区域定义不同的验证方式,提高网络的安全性。
RIP路由协议中用于表示目的网络远近的唯一参数为跳( HOP),也即到达目的网络所要经过的路由器个数。在 RIP路由协议中,该参数被限制为最大 15,
也就是说 RIP路由信息最多能传递至第 16个路由器;
对于 OSPF路由协议,路由表中表示目的网络的参数为
Cost,该参数为一虚拟值,与网络中链路的带宽等相关,也就是说 OSPF路由信息不受物理跳数的限制。并且,OSPF路由协议还支持 TOS( Type of Service) 路由,因此,OSPF比较适合应用于大型网络中。