最佳多容錯之號誌環網路

Abstract

一個連結網路連接了平行計算機之上的處理器始能交換資訊。 其結構可以用一個圖形來表示，其中節點即相當於處理器，而 邊線則相當於連結網路上處理器與處理器之間的通訊連結。在 設計計算機網路的拓樸結構（topology）時，許多需求將互相衝 突，包括： 小的直徑(diameter)，有限制的分支度(degree)，對稱 性(symmetry)，擴充性(expansibility)，有效率的處理器佈置(layout) ，簡單的路由(route)演算法，容錯(fault tolerant)，漢米爾頓特性 (hamiltonian properties)…等等。另外，「號誌環傳送」（token passing）技巧廣為分散式作業系統（distributed operating systems） 所採用，設計一個最佳k容錯號誌環網路的問題就等於建構一個 最佳k漢米爾頓(k-hamiltonian)的圖形，其中的k為容錯的個數。 若一個圖形的邊數與點數總共壞掉k個之後還有一個漢米爾頓迴 圈，則此圖形稱為k漢米爾頓圖。在相同點數的k漢米爾頓圖形中 ，邊數最少的稱為最佳k漢米爾頓圖形(optimal k-hamiltonian graph) 。在本篇論文中，我們介紹最佳k漢米爾頓問題的研究成果，其中 我們提出了兩個新的最佳1漢米爾頓圖形：G(k)與C(s)，G(k)的直徑 (diameter)為O（√n）而C(s)的直徑是2log_2 n，其中的n為整個圖形 的點數，這兩個值都比以前的結果小很多。另外我們也證明了 CT(s)這個圖是最佳漢米爾頓連通圖。我們更進一步地提出了設計 最佳１漢米爾頓圖形的一般性定理，我們發現前人與我們自己前 面的結果都是此定理的特例而已。 接下來我們討論了最佳k漢米爾頓的圖形(optimal k-hamiltonian graphs)，其中的k>1，我們提出了一系列的最佳k漢米爾頓圖形， 其直徑為 2log_{k+1} n。只是這些圖形並不是點對稱的圖形，於 是我們設計了另外一系列的k漢米爾頓圖形，這些圖形是點對稱 ，其點數為(k+3)* (k+3)!，每個點的分支度是k+2，而直徑約為 3(k+2) 。我們另外證明：若圖形G每個點的分支度為(k+2)的最佳 k漢米爾頓圖形，則 是每個點分支度為(k+3)的最佳(k+1)漢米爾頓 圖形。

Designing an optimal k-fault-tolerant network for token rings is equivalent to constructing an optimal k-hamiltonian graph, where k is a positive integer and corresponds to the number of faults. A graph G = (V, E) is k-hamiltonian if G - (V' - E')$ is hamiltonian for arbitrary V' is a subset of V, E' is a subset of E with |V'| + |E'| <= k. A k-hamiltonian graph G* is optimal if it contains the fewest edges among all k-hamiltonian graphs with the same number of nodes as G*. In this thesis, we propose two families of optimal 1-hamiltonian graphs {G(k) | k is a positive integer.} and {CT(s) | s is a positive integer.}. The graph G(k) has diameter O(\sqrt{n}) and the graph CT(s) has diameter 2 log_2 n -O(1) where n is the number of nodes. We also prove that CT(s) is optimal hamiltonian-connected. Furthermore, we propose a general construction scheme for optimal 1-hamiltonian graphs. Applying this scheme, we can construct some previous optimal 1-hamiltonian graphs and the graphs G(k) and CT(s). We then focus our attention on optimal k-hamiltonian graphs with k >= 1. We construct a family of k-hamiltonian graphs with diameter 2 log_{k+1} n - O(1), that is 2 times Moore bound. However, the graphs of this family are not symmetric. We propose another family of k-hamiltonian graphs which is node symmetric with (k+3) * (k+3)! nodes, degree k+2, and diameter 2 * [3(k+2)/2]. We also prove that G is a (k+2)-regular k-hamiltonian graph then G \times K_2 is (k+3)-regular (k+1)-hamiltonian.