標題: | 最佳多容錯之號誌環網路 Optimal k-Fault-Tolerant Networks for Token Rings |
作者: | 洪春男 Chun-Nan Hung 徐力行 Lih-Hsing Hsu 資訊科學與工程研究所 |
關鍵字: | 容錯;漢米爾頓迴圈;漢米爾頓圖形;漢米爾頓連通;號誌環;fault tolerance;hamiltonian cycle;hamiltonian graphs;hamiltonian-connected;token rings |
公開日期: | 1998 |
摘要: | 一個連結網路連接了平行計算機之上的處理器始能交換資訊。
其結構可以用一個圖形來表示,其中節點即相當於處理器,而
邊線則相當於連結網路上處理器與處理器之間的通訊連結。在
設計計算機網路的拓樸結構(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)這個圖是最佳漢米爾頓連通圖。我們更進一步地提出了設計
最佳1漢米爾頓圖形的一般性定理,我們發現前人與我們自己前
面的結果都是此定理的特例而已。
接下來我們討論了最佳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. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT870394004 http://hdl.handle.net/11536/64141 |
Appears in Collections: | Thesis |