algorithm - 任意多节点的Bellman-Ford距离向量算法

Question

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

例如，假设我连接了 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 确定最短路径。一方面，您没有网络的全局 View 。每个路由器都在它看到的范围内运行，并且它看到的内容受到限制——可能会产生误导。查看DVMRP的循环问题。 DVMRP 永远无法处理完整的网络信息。

它也不可扩展。它的性能越来越低随着数量或路由器的增加。这是因为距离矢量更新消息泛滥和这些消息的当前准确性。

它是最早的多播协议(protocol)之一。它的性能匹配单播规模的 RIP。