这个计网有丶东西(一)

是关于路有选择算法的,也是Dijkstra算法和Bellman-Ford算法的应用把,终于知道这个有什么用了….

总的来说这个路由算法分为两个:链路状态路由选择算法 和 距离向量路由选择算法,前者简称 LS,后者简称 DV。

LS:看上去很高端霸气,实际上也就那个样子,LS算法是由链路状态广播算法加上这个Dijkstra算法而来的,事实上由于Dijkstra算法需要知道全局的链路信息,因此必须在进行疯狂计算前进行数据之间的传递,然后开始松弛计算最短路径(某个点到其余点的最短路径)。当然这个算法也存在着路由震荡的问题,简单的说就是假如四个路由器都在同一时间点进行计算,分发,则会出现其余三个路由器一起选择同一条在它们当时看来不拥挤的道路,然后….就炸了,因此每台路由器会发送链路通告让时间随机化

DV:不同于上,LS算法并不需要知道每一条链路的信息,相反它只知道自己和邻居链路的信息以及它邻居发给他的信息。在收到第一批邻居发的信息后,该路由器开始计算,更新(把所有已知的边带进去算,看是否能进行松弛)。更新后把结果分发给自己的邻居,显然这个过程是异步的。然后这个算法的问题是会出现故障(废话),就是因为它是异步的,信息改变时感觉会给各个路由器之间造成误会,而每个路由器知道的也只是 “诶,我的邻居告诉我他有一条可以去x点的路而且代价不高,可以啊小老弟”。这里就看出来和LS算法的不同,LS算法中的路由器是确切的知道每一条链路的信息的,因此不会有“误会”,而误会造成的后果就是一旦某一条链路的拥挤程度,假设是 x(u,v)发生猛增,这时对于第三方路由器 a 来说 a 本来认为 u 有一条路代价不高就可以去到 v 因此就对 u 说 “我有一条路去v代价不高哦”(实际上这时这一条路已经高的一比,u不知道a这个沙雕说的路就是自己通向v的路),这时 u 为了把东西发往 v 会把文件发给 a ,同时告诉a说我知道一条路可以以很低的代价通向 x(其实就是z传递错误信息造成的误会,u说的就包含z说的那一条)然后 a 说不错然后转手把文件甩给 u 。。。

然后,这样的误会会一直加深直到超过某个阈值(通常是 y(a,v)的代价),即文件在 a 和 u 之间反复横跳 🙂

这个时候就有一种方法叫毒性逆转,其实就是欺骗啦,a骗u说自己去x的路是无穷大的。。也不是很有用,只适合于三角形的路由。

发布者

我乃堂堂SCUT的一条咸鱼!

发表评论

电子邮件地址不会被公开。 必填项已用*标注