Stabilization of General Loop-Free Routing
Stabilization of General Loop-Free Routing
复制标题
通用无环路由的稳定性
DOI：
10.1006/jpdc.2001.1830
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Gouda
中科院分区：
文献类型：
--
作者：
J. Cobb;M. Gouda
我们提出了一个协议，用于维护一个生成树，是最大的任何给定的（有界和单调的）路由度量。该协议有两个有趣的自适应特性。首先，协议是稳定的：从任何状态开始，协议稳定到存在最大树的状态。第二，该协议是无环的：从任何状态开始，生成树存在，协议稳定，而不形成任何循环，到一个最大树存在的状态。该协议的稳定时间是O（n度），其中n是节点数，度是网络中节点的度。
We present a protocol for maintaining a spanning tree that is maximal with respect to any given (bounded and monotonic) routing metric. This protocol has two interesting adaptive properties. First, the protocol is stabilizing: starting from any state, the protocol stabilizes to a state where a maximal tree is present. Second, the protocol is loop-free: starting from any state where a spanning tree is present, the protocol stabilizes, without forming any loops, to a state where a maximal tree is present. The stabilization time of this protocol is O(n deg), where n is the number of nodes, and deg is the node degree in the network.