雙環式網路兩點間之可容錯路線演算法

Abstract

訊息傳送是網路的一個基本功能，而可容錯的特性可以確保網路傳送的品質。通常假設雙環式網路中最多只有一個點或邊發生錯誤，而且錯誤發生在哪裡是無法事先知道的。在不要求事先知道錯誤發生在哪裡的前提下，我們發展了一個經由兩條點不重複的路徑傳送兩個相同的訊息到目的地的演算法，並且保證其中一個訊息會避過錯誤、而且走最短路徑將訊息傳送到目的地，此演算法在每個端點只需要花常數時間即可判斷下一步要將訊息傳送到哪一點。

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.