标题: 双环式网路两点间之可容错路线演算法
A Fault-Tolerant Two Terminals Routing Algorithm of Double-Loop Networks
作者: 陈沅百
Yuanpai Chen
陈秋媛
Chiuyuan Chen
应用数学系所
关键字: 双环式网路;讯息传送最佳路线;讯息传送可容错路线;double-loop network;optimal message routing;fault-tolerant message routing
公开日期: 2001
摘要: 讯息传送是网路的一个基本功能,而可容错的特性可以确保网路传送的品质。通常假设双环式网路中最多只有一个点或边发生错误,而且错误发生在哪里是无法事先知道的。在不要求事先知道错误发生在哪里的前提下,我们发展了一个经由两条点不重复的路径传送两个相同的讯息到目的地的演算法,并且保证其中一个讯息会避过错误、而且走最短路径将讯息传送到目的地,此演算法在每个端点只需要花常数时间即可判断下一步要将讯息传送到哪一点。
Delivering messages between two terminals is a very important function of a network. Fault-tolerant is an important criteria to ensure the quality of a network. Under this circumstance that there is at most one edge (or node) fault in the double-loop network and the fault can not be detected before a message is sent, we propose a routing algorithm which simultaneously sends two messages to the destination along two node-disjoint routes among which at least one route is optimal. At each vertex, our algorithm spends only constant time and space to determine which
vertex is the next vertex that the message should be sent.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT900507021
http://hdl.handle.net/11536/69317
显示于类别:Thesis