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