网络拓扑结构中的最优性原则

引言：

这里提出了关于最优路径的一般性描述，而并未考虑网络拓扑结构或交通状况等因素。这种描述被称为“最优性原理”（Bellman, 1975）。

声明/说明那个最优性原理 :

该定理指出，如果路由器J位于从路由器I到路由器K的最优路径上，那么从J到K的最优路径也必然沿着相同的路线。我们将从路由器I到路由器J的路径称为r1，而其余的路线则称为r2。通过将r1与r2结合起来，可以优化从路由器I到路由器K的路径。但这与我们之前的结论相矛盾——因为我们认为，只有当从J到K存在比r2更优的路径时，r1r2才是最优路径。

为路由器设置“下沉式树形结构”：

我们可以看到，从所有起点到某个指定目的地的理想路线集合，实际上是从以该目的地为根节点的树中得出的。这种树被称为“最优路径树”。倒树如图1所示。

图示描述：

在给定的图中，距离度量指的是所需的跳数。因此，所有路由算法的目标都是找到并利用适用于所有路由器的汇聚树结构。

“Sink tree”并不是唯一的例子。实际上，可能存在其他具有相同路径长度的树。如果我们允许选择所有可能的路径，那么这种树就变成了一个更为通用的结构了。有向无环图。DAGs中不存在循环结构。在这里，我们可以使用“汇点树”来简洁地表示这两种情况。对于这两种情况，我们都假设路径之间不会相互干扰。也就是说，例如，一条路径上出现交通堵塞时，不会影响到另一条路径的正常运行。

结论：

该路由树中不存在任何循环路径，因此每个数据包都只会经过有限数量的跳数才能被传输到目的地。 实际上，生活并不容易。 在运行过程中，连接设备和路由器可以不断重新连接或断开连接。因此，不同的路由器可能会对当前的网络拓扑结构有不同的理解。 此外，我们还探讨了这样一个问题：每个路由器是否需要单独获取用于计算其接收树所需的信息？或者，这些信息是否可以通过其他方式来获取呢？ “Sink Tree”和“最优性原理”为其他路由算法提供了一个衡量标准。