具有任意多个节点的Bellman-Ford距离向量算法

Question

我正在尝试为一个模拟路由器的类编写一个程序，到目前为止，我已经完成了基本设置(“路由器”可以通过模拟服务器向连接到该服务器的其他“路由器”发送和接收数据包)。每个数据包仅包含该路由器的距离矢量。当路由器接收到数据包时，它应该使用贝尔曼-福特算法相应地更新自己的距离矢量。我遇到的问题是，我发现自己无法在不作弊和使用邻接矩阵的情况下实现实际的算法。

例如，假设我连接了3台路由器，如下所示：

A ---1--- B ---2--- C

也就是说，A和B的链路开销为1，B和C的链路开销为2。因此，当路由器全部启动时，它们将向每个直接连接的邻居发送一个数据包，其中包含距离矢量信息。因此A将发送路由器B (0，1，INF)，B将发送A和C (1，0，2)，C将发送B ( INF，2，0)，其中INF表示这两个路由器没有直接连接。

因此，让我们看一下路由器A从路由器B接收到一个数据包。使用Bellman-Ford算法计算到每个路由器的最小开销如下所示。

Mincost(a,b) = min((cost(a,b) + distance(b,b)),(cost(a,c) + distance(c,b))

Mincost(a,c) = min((cost(a,b) + distance(b,c)),(cost(a,c) + distance(c,c))

所以我遇到的问题是，我无论如何也想不出如何实现一个算法，来计算一台路由器到每台其他路由器的最小路径。如果您确切地知道将有多少个路由器，那么制作一个路由器就足够容易了，但是当路由器的数量可以任意多时，您该如何做呢？

Answer 1

使用DVMRP，您永远无法确定最短路径。首先，你没有网络的全局视图。每个路由器都在它看到的东西上运行，而且它看到的东西是受限的--可能会产生误导。查找DVMRP的循环问题。DVMRP永远不能处理完整的网络信息。

它也是不可伸缩的。随着路由器数量的增加，其性能也越来越低。这是因为大量的距离矢量更新消息和这些消息的当前准确性。

它是最早的组播协议之一。其性能与单播规模的RIP相当。