《DV选路算法的毒性逆转技术》由会员分享，可在线阅读，更多相关《DV选路算法的毒性逆转技术（7页珍藏版）》请在金锄头文库上搜索。
1、HUNAN UNIVERSITY计算机网络论文题 目： DV 选路算法的毒性逆转技术 学生姓名 田田 玉玉 祥祥 学生学号 20110801129 专业班级 2011 级计科一班 指导老师 王王 东东 老师 2 20 01 14 4年年0 06 6月月2 23 3日日 DV 选路算法的毒性逆转技术田田 玉玉 祥祥摘要：随着网络科技的进步，人们越来越多地提出了包括选路算法特点的综合服务要求，DV 选路算法的毒性逆转现在是 Internet 研究的热点，当一个分组 要从源主机带目的主机时，网络层必须确定从发送方到接受方的分组所采用的 路径。选路算法的目的就是给定一组路由器以及连接路由器的链路，选路
2、算法 要找到一条从源路由器到目的路由器的“好”的路径，即具有最低费用的路径。 DV 算法是分散式的选路算法距离向量算法（distance-vector, DV） 。本文将通 过对这该算法的毒性逆转技术进行浅谈。关键字：关键字：选路算法，路由器，网络层Abstract:With the advancement of internet technology, more and more people put forward a comprehensive service requirements including routing algorithm characteristics, DV poi
3、son reverse routing algorithm is now a hot research Internet, when a packet from the source host to the destination host with , the network layer must determine the path a packet from the sender to the recipient used. “Good,“ the path to the destination routing algorithm is given a set of routers an
4、d links connecting the router, the routing algorithm to find a path from the source router to the destination router that has the lowest path costs. DV algorithm is a distributed routing algorithm based on distance vector algorithms (distance-vector, DV). In this paper, the algorithm through these t
5、echnologies Talking poison reverse.Keywords：routing algorithm，router，Network layer引言 不同的网络层提供的不管是数据服务还是虚电路服务，网络层都必须确定 为从发送方到接受方的分组所采用的路径。我们看到选路的工作是从发送方到 接受方通过路由器的网络决定的好路径。选路算法的目的是简单的，即给定一 组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由 器的“好”的路径。通常一条好的路径指具有最低费用的路径。对选路算法分 类的一种方法是根据该算是全局性的还是分散式的可分为全局选路算法和分散 式选路算法，而
6、根据分散式路由选路算法，拓展出来的毒性逆转技术将是本文 特点讨论的话题。1、选路算法路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的寻径结果，因此选择路由算法一定要仔细。通常需要综合考虑以下几个设计目标：（1）最优化：指路由算法选择最佳路径的能力。（2）简洁性：算法设计简洁，利用最少的软件和开销，提供最有效的功能。（3）坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的。（4）快速收敛：收敛是在最佳
7、路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息 遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 （5）灵活性：路由算法可以快速、准确地适应各种网络环境。例如，某个网段发生故障，路由算法要能很快发现故障，并为使用该网段的所有路由选择另一条最佳路径。 2、距离向量路由选择算法2.1 距离向量算法 DV（Distance-vector）是一种迭代的、异步的和分布的算法：分布式的：每个节点都要从一个活多个直接相连的邻居收集某些信息，执行计算，然后将结果发回个邻居。迭代的
8、：该过程要一直持续到邻居之间没有更多的信息要交换为止。异步的：各个节点的操作不需要保持一致。DV 算法，利用了 Bellman-Ford 方程：dx(y)=minvc(x,v)+dv(y)其中 dx(y)表示从节点 x 到节点 y 的最低费用路径的费用。c(x,v)的含义是节点 x 到其邻居 v 的路径费用。方程式的含义是从节点 x 到节点 y 的最低费用路径的费用等于所有邻居 v 中 c(x,v)+dv(y)最小的那个。在 DV 算法中，Bellman-Ford 的一个重要的贡献就是，得到最小值的那个 v节点就是当前节点向 y 转发时的下一跳节点，当需要向 y 转发时，只需要将分组送给节点
9、v 即可。算法思想：对于网络 N 中的素有节点，令 Dx=Dx(y):y 属于 N是节点 x 的距离向量，该向量是从 x 到 N 中所有其它节点 y 的费用估计向量。每个节点 x 维护下列选路数据：对于每个邻居 v，从 x 到直接相连的邻居 v 的费用为 c(x,v)。节点 x 的距离向量，它包含了 x 到 N 中所有目的地的费用的估计值它的每个邻居的距离向量，即对 x 的每个邻居 v 有 Dv=Dv(y):y 属于 NDV 算法中，每个节点不时的向它的每个邻居发送它的距离向量的拷贝。当节点 x 收到他的邻居 v 的一个新的距离向量时，它保存 v 的距离向量，然后根据 Bellman-Ford
10、 方程更新自己的距离向量。如果节点 x 的距离向量因这个更新而改变，则节点 x 将向它的每个邻居发送它的更新后的距离向量。从邻居接收更新距离向量，重新计算选路表项和通知邻居到目的地的最低费用路径的费用已经变化的过程会一直持续知道无更新报文发送为止。DV 算法被用于因特网的 RIP 和 BGP。2.2 距离向量算法：链路费用变化和链路故障运行 DV 算法的节点在检测到其到邻居的链路费用发生变化时就会更新器距离向量，并且如果最低费用路径发生了变化，它就向邻居通知其新的距离向量。当链路费用降低时，DV 算法可以就得到变化后的最低费用。但是如果是链路费用增加，则会出现一点问题，如下图所示拓扑：链路费用
11、变化前，网络拓扑如上图所示，则 Dy(x)=4,Dy(z)=1, Dz(y)=1, Dz(x)=5,在t0时刻，y 检测到链路费用变化（从4增加到40） 。y 会更新器最低费用路径，根据Bellman-Ford 方程，其计算出来的值为6。但是观察这个时候的网络拓扑，显然这是不正确的。出现这个现象的原因是：y 更新器距离向量时，利用了 z 通告给它的 z 的距离向量，Dz(x)=5，但是显然，Dz(x)是依赖于 Dy(x)的，在 Dy(x)变化后它显然是一个错误的值。更重要的是在这个时刻，会出现选路环路：为了到达 x，y 通过 z 选路，而 z 又选择通过 y 选路，这样的选路结果是分组无法到达
12、目的地。y 计算出来了一个新的到 x 的最低费用，因而它在 t1时刻将新的距离向量通告给 zz 收到 y 的新的距离向量后更新其距离向量，它计算出来的新的 Dz(x)=7该过程一直循环，直到计算出来一个正确的值 Dy(x)=40，Dz(x)=41从上述过程可以看到使用 DV 算法时，坏消息传递的比较慢。而且上述过程只是一个链路的费用变高了，如果有多个链路的费用变高，则会遇到所谓的计数到无穷的问题。2.3.距离向量算法：增加毒性逆转毒性逆转可以解决上述特定的网络拓扑中的环路状况。其思想是：如果 z 通过 y 选路，则 z 在通告 y 时会告诉 y 它（z）到 x 的距离是无穷大。毒性逆转只能解决
13、这种特殊环路的问题，如果环路涉及到3个或更多的节点，则它也无能为力3.毒性逆转方法上文提到，毒性逆转可以解决上述特定的网络拓扑中的环路状况。这里将详细介绍这个特殊方法。选路环路和计数到无穷 当某条链接的费用减少时，我们称之为有一个“好消息” 。在网络中，好消息的传递往往很迅速。例如，存在这样一个网络（图2）：图 2 X-Y-Z 链路网络 1某一时刻，Y 检测到它到 X 的链路费用由4减少为1，好消息当然要告诉大家了，于是它更新了自己的距离向量，并通知了 Z。Z 在收到 Y 的更新报文后，也更新了自己的距离向量（由5减为2） ，并向邻居们发送更新报文。而后，Y 又收到了 Z 的更新报文，但它发现
14、并没有改变自己的最低费用，于是保持不变。这样，仅仅经过了两次迭代网络就达到了静止。好消息通过网络得到了迅速传播。然而，当链路费用增加（甚至断开）时，就不会这么简单了。继续观察下面这个例子（图3）：图 3 X-Y-Z 链路网络 2还是 X、Y、Z 三个节点。此时 Y 检测到它到 X 的路径费用由4增加到了60。此时节点 Z的距离向量为：d(X) = 5, d(Y) = 1, d(Z) = 0。于是 Y 在更新向量时发现，咦，Z 到 X的距离只有5诶，那可以先到 Z 再到 X，于是 Y 的距离向量更新为：d(x) = 5 + 1 = 6, d(Y) = 0, d(z) = 1。我们可以发现，这个逻
15、辑显然是错误的，因为 Z 到 X 的距离为5的前提是要经过 Y，但 Y 更新后的路径又要经过 Z，这就形成了一个选路环路（routing-loop）问题。因为 Y 的距离向量更新了，但它还是向 Z 发送了更新报文。Z 收到更新报文后，比较了下邻居们到 X 的距离，发现经过 Y 的路径距离为1 + 6 = 7，小于直接到 X 的距离，于是 Z 也更新的自己的距离向量，然后又将更新后的距离向量发给 Y。Y 收到后又更新向量为8，然后再发给 Z.这样循环往复，更新报文在 Y 和 Z 之间传来传去，直到第44次迭代后，Z 算出它经由 Y 的路径费用大于50为止。此时，Z 最终确定到 X 的最短路径费用是直接到达 X 的费用50，而 Y 也得到了最短路径是经 Z 到 X 的费用51。可以看出，虽然最后还是得到了正确的信息（最后的50和51是正确的！） ，但坏消息的传播与好消息相比实在是慢太多了！而且，如果 X 和 Y 之间的费用为10000，Z 和 X 的费用是9999时，就会出现计数到无穷的问题！4 应用总结和比较带毒性逆转的水平分割技术,是
