Route Preserving Stabilization
Route Preserving Stabilization
复制标题
路由保持稳定
DOI：
10.1007/3-540-45032-7_14
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
C. Johnen;S. Tixeuil
一个分布式系统是自稳定的，如果它返回到一个合法的状态，在有限的步骤，无论初始状态，系统保持在一个合法的状态，直到另一个故障发生。如果在两个处理器p和q之间构建路径，任何边成本变化都会引起路由表的修改，使得在任何时候都存在从p到q的路径，则路由算法是无环的。
我们提出了一个自稳定的无环路由算法，也是路由保持。最后一个属性意味着，在构建树时，发送到根节点的任何消息都将在有限的时间内收到，即使存在连续的边成本变化。此外，与以前的方法不同，我们不要求执行路由算法的处理器知道网络直径的界限。我们保证许多指标的自稳定性（如最小距离，最短路径，最佳发射机，深度优先搜索指标等），通过重复使用先前关于r算子的结果。
A distributed system is self-stabilizing if it returns to a legitimate state in a finite number of steps regardless of the initial state, and the system remains in a legitimate state until another fault occurs. A routing algorithm is loop-free if, a path being constructed between two processors p and q, any edges cost change induces a modification of the routing tables in such a way that at any time, there always exists a path from p to q.
We present a self-stabilizing loop-free routing algorithm that is also route preserving. This last property means that, a tree being constructed, any message sent to the root is received in a bounded amount of time, even in the presence of continuous edge cost changes. Also, and unlike previous approaches, we do not require that a bound on the network diameter is known to the processors that perform the routing algorithm. We guarantee self-stabilization for many metrics (such as minimum distance, shortest path, best transmitter, depth first search metrics, etc.), by reusing previous results on r-operators.