連結網路上之路徑與迴圏嵌入

Path and Cycle Embedding on Interconnection Networks

龔自良(Tzu-Liang Kung)

指導教授 ： 梁婷 ； 徐力行

國立交通大學/資訊學院/資訊科學與工程研究所/博士(2009年)

https://doi.org/10.6842/NCTU.2009.00014

摘要

陣列與環是平行計算與分散式計算中兩種最基本的網路類型。一般而言，路徑與迴圏是普遍被使用來表示這兩種網路的拓樸結構。在本論文中，我們著眼於連結網路上的路徑與迴圏嵌入問題。由於網路上的任何元件隨時隨地都可能因損壞、損毀而使得整個網路無法正常運作，因此，網路的容錯能力是設計任何一個網路系統時所不能忽視的重要考量。所以，我們也深入討論與網路容錯相關的研究議題。藉由將網路抽象地以數學上的「圖」來表示，我們可以嚴謹地探討各種連結網路的特性。

　　首先，我們研究具有「超級容錯漢彌爾頓」性質的網路。若一個k－正則漢彌爾頓連通網路在任意移除了k－2個節點或連線之後仍然保有漢彌爾頓的特性，且在任意移除了k－3個節點或連線之後仍然具有漢彌爾頓連通的特性，則我們稱此網路為「超級容錯漢彌爾頓」網路。給定n個具有相同節點數的k－正則超級容錯漢彌爾頓網路，其中n≥3且k≥4，我們可以使用「迴圏複合」的架構來建構（k＋2）－正則的超級容錯漢彌爾頓網路。

　　其次，我們研究漢彌爾頓迴圏問題的變形，文獻上稱之為「相互獨立漢彌爾頓迴圏」。給定一固定的節點作為起始點，若一個網路的任意n條漢彌爾頓迴圏從此固定的起始節點開始，在後續的每一個時間點上都剛好繞經不同的中間節點，最後這n條漢彌爾頓迴圏又同時回到起始節點，則我們稱此n條漢彌爾頓迴圏具有相互獨立的特性。在本論文中，我們研究了如何在立方體、星狀圖及蝴蝶圖上嵌入相互獨立漢彌爾頓迴圏的方法。

最後，我們討論網路的條件式容錯能力。在本論文中，我們假定網路中的任一節點必須保有至少二個功能正常的相鄰節點或保有至少二個通訊功能正常的連線。在這個前提假設之下，我們針對立方體網路上的容錯式路徑嵌入問題進行深入的探討。相較於文獻中的既有的研究成果，我們證明了超立方體網路的容錯能力，在條件式損壞模型的假設之下其實是可以大幅增加的。

關鍵字

連結網路 ； 立方體 ； 星狀圖 ； 蝴蝶圖 ； 漢彌爾頓 ； 漢彌爾頓連通 ； 容錯 ； 條件式損壞 ； 迴圏嵌入 ； 路徑嵌入

並列摘要

In many parallel computer systems, processors are connected on the basis of interconnection networks, referred to as networks henceforth. Among various kinds of networks, linear arrays and rings are widely applied in parallel and distributed computation. In particular, paths and cycles are two topological structures commonly used to model linear arrays and rings, respectively. Therefore we investigate how to embed paths and cycles into some interconnection networks in this thesis. Because the components of a network may fail not only accidentally but frequently, it is of great importance for a network to be capable of tolerating as many faults as possible. In this thesis the fault-tolerance related issues are also concerned. With the graph representation of an interconnection network, we can discuss these issues in a formal way.

Firstly, we study a family of super fault-tolerant hamiltonian networks, namely cycle composition networks. A k-regular hamiltonian and hamiltonian connected network is super fault-tolerant hamiltonian if it remains hamiltonian after removing up to k-2 vertices and/or edges and remains hamiltonian connected after removing up to k-3 vertices and/or edges. Super fault-tolerant hamiltonian networks have an optimal flavor with regard to fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. For this motivation, we observe that the cycle composition is an effective framework to construct a (k+2)-regular super fault-tolerant hamiltonian network on the basis of n k-regular super fault-tolerant hamiltonian networks, containing the same number of vertices, provided that n≥3 and k≥4.
Secondly, we investigate a variant of hamiltonian cycles, namely mutually independent hamiltonian cycles, on some interconnection networks. A set of hamiltonian cycles, having the same start vertex, is said to be mutually independent if any two of these hamiltonian cycles traverse different vertices at every time step except the start-up and termination. In this thesis, we show that the maximum number of mutually independent hamiltonian cycles can be embedded onto the binary wrapped butterfly network. Moreover, embedding mutually independent hamiltonian cycles onto faulty hypercubes and onto faulty star networks are also addressed.

Next, we investigate the conditional-fault tolerance of hypercubes. There is one thing worth noting. That is, if components of a network fail independently, then it is unlikely that all failures would be close to each other. When faulty vertices are concerned, it is reasonable to require that every vertex should have at least g fault-free neighbors. Analogously, when faulty edges are concerned, it can be assumed that every vertex is still incident to at least g fault-free edges. In this thesis we first study the fault diameter of the n-cube only for g=1, and then we explore the feasibility of fault-tolerant path embedding on hypercubes when g=2.

並列關鍵字

Interconnection network ； Hypercube ； Star graph ； Butterfly graph ； Hamiltonian ； Hamiltonian connected ； Fault tolerance ； Conditional fault ； Cycle embedding ； Path embedding

參考文獻

[1] S. B. Akers, B. Krishnameurthy, A group-theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38 (1989) 555-566.

[2] M. M. Bae, B. Bose, Edge disjoint hamiltonian cycles in $k$-ary $n$-cubes, IEEE Transactions on Computers 52(10) (2003) 1271-1284.

[3] M. Baldi, Y. Ofek, A comparison of ring and tree embedding for real-time group multicast, IEEE/ACM Transactions on Networking 11(3) (2003) 451-464.

[4] B. Barden, R. L. Hadas, J. Davis, W. Williams, On edge-disjoint spanning trees in hypercubes, Information Processing Letters 70 (1999) 13-16.

[5] S. Bettayeb, On the $k$-ary hypercube, Theoretical Computer Science 140 (1995) 333-339.