弦環式網路之全體對全體私有訊息傳送問題之研究

Abstract

弦環式網路中的邊可分為「弦邊」和「環邊」。在文獻[5]和文獻[7]中，Masuyama等學者提出了兩個弦環式網路的全體對全體通訊演算法，其中的第一個演算法（為方便，稱之演算法A）是一個全體對全體私有訊息傳送演算法，它使用於網路中沒有任何壞點時，第二個演算法（為方便，稱之演算法B）是一個全體對全體廣播演算法，當網路中有一至二個壞點時，它仍可使用。文獻[5]和文獻[7]證明了：對弦環式網路 而言，演算法A需要 單位時間，其中 表示節點數， 表示弦長。然而，我們發現演算法A只使用弦環式網路中的環邊來傳送訊息，演算法B只在網路中有壞點時才會使用弦邊來傳送訊息。文獻[5]和文獻[7]的演算法浪費了大量的網路硬體，因為只要沒有壞點就不會使用弦邊。在這篇論文中，我們利用弦邊來使弦環式網路的全體對全體私有訊息傳送更快速。我們首先提出一個利用弦邊的演算法來執行弦環式網路的全體對全體私有訊息傳送；我們以實際數據來證明我們的演算法比演算法A花費較少的單位時間，因此改進了演算法A。此外，我們也提出了一個針對 的弦環式網路的全體對全體私有訊息傳送演算法，我們證明了此演算法比演算法A花費少50%以上的單位時間。最後，我們闡明了演算法B中的一些不清楚或不正確的地方。

In [5, 7], Masuyama et al. proposed two all-to-all communication algorithms for chordal ring networks of degree 3. The ‾rst algorithm (call it Algorithm A) is an all-to-all personalized exchange algorithm and it is used when there is no fault. The second algorithm (call it Algorithm B) is an all-to-all broadcast algorithm and it can tolerate one or two faults. In [5, 7], it has been proven that Algorithm A takes sigma_i=1 to N/2 i time units to fulfill an all-to-all personalized exchange in a chordal ring network CR(N;w), where N is the number of nodes and w is the chord length of the chordal ring network. However, we observe that Algorithm A only utilizes ring-links to fulfill an all-to-all communication and Algorithm B tilizes chordal-links only when there are faults. Since all of the chordal-links are not used in any all-to-all communication when there is no fault, a huge amount of hardware is wasted. In this thesis, we will use chordal-links to facilitate an all-to-all personalized exchange. In particular, we propose an all-to-all personalized exchange algorithm that works for all chordal ring networks. We will show that our algorithm uses less time units to fulfill an all-to-all personalized exchange and hence improves Algorithm A. We also provide an all-to-all personalized exchange algorithm that works only for chordal ring networks with w = 3 and clarify some unclear parts and correct some incorrect parts in Algorithm B.