增強型金字塔網路之ω-寬直徑

陳怡靜等人於2004年時，藉由取代金字塔網路上每一個網格 (mesh) 為圓盤網格(torus) 的作法提出一種新的階層結構，稱之為增強型金字塔網路。近年來，已經有一些關於增強型金字塔網路上拓樸特性與通訊方法的研究。這些研究結果指出，增強型金字塔網路相對於金字塔網路而言，是具有吸引力的替代方案。為了能夠評估一個快速平行通訊互聯網路的可靠度與容錯能力、最大平行度與最小傳輸延遲，在此網路上建置點不相交路徑，並且決定其寬直徑是非常重要的議題。在一個互聯網路上兩個不同節點之間，可能會有許多不同的不相交路徑集。在一個連結度為κ的網路上，任意兩個節點之間建立ω小於等於κ之ω-寬度的最佳不相交路徑集，並且計算出其w-寬直徑是非常困難的。因為增強型金字塔網路的連結度為4，依據Menger定理與其變化形式可知，增強型金字塔網路上任意兩節點之間，至少存在4條節點不相交路徑。本研究首先提出數個新穎的演算法，在n-層增強型金字塔網路上，每組相異兩節點間都建立長度盡可能短寬度為2-，3- 及 4-的不相交路徑集，並且計算出其2-，3- 及 4-寬直徑之上限值。其次，在特定兩節點間分別建立2，3 及 4條路徑。分別而言，這些路徑的長度最多是寬度2-，3- 及 4-的最佳不相交路徑集的長度，並且分別等於此n-層增強型金字塔網路2-，3- 及 4-寬直徑之上限值。最後，便可因此決定出增強型金字塔網路之ω-寬直徑。

關鍵字

增強型金字塔網路；金字塔網路；容錯； ω-寬直徑；節點不相交路徑；不相交路徑集；互聯網路

並列摘要

Chen et al. proposed in 2004 a new hierarchy structure, called the enhanced pyramid network (EPM), by replacing each mesh in a pyramid network (PM) with a torus. Recently, some topological properties and communication on an EPM have been investigated or derived. Their measurement results indicate that an EPM is an attractive alternative to a PM. In order to evaluate reliability and fault tolerant ability, maximize parallelism and minimize transmission delay for fast parallel communication of an interconnection network, constructing node-disjoint paths and determining ?-wide diameters of the network are very important issues. Given two distinct nodes in an interconnection network, there may be many different containers between these two nodes. Establishing a ω-wide best-container between two given nodes and then computing ω-wide diameters of a κ-connected network are very difficult, where ω ≤ κ. Since connectivity of every enhanced pyramid network is 4, by Menger’s theorem and its variances, there are at least 4 node-disjoint paths between arbitrary two distinct nodes in an enhanced pyramid network. This work first computes upper bounds of 2-, 3- and 4-wide diameters of an n-layer enhanced pyramid network by providing novel algorithms for constructing 2-, 3- and 4-wide containers as short as possible between every two distinct nodes of the network. Second, build 2, 3 and 4 paths between two specific nodes whose lengths are at most the lengths of 2-, 3- and 4-best-containers and equal to upper bounds of 2-, 3- and 4-wide diameters of the n-layer enhanced pyramid network, respectively. Finally, ω-wide diameters of an EPM can then be determined.

並列關鍵字

Enhanced pyramid networks ； pyramid networks ； fault tolerance ； wide diameter ； node-disjoint paths ； container ； interconnection networks

參考文獻

[1] N. Bagherzadeh, N. Nassif, S. Latifi, A routing and broadcasting scheme on faulty star graphs, IEEE Trans. Comput. (42) (11) (1993) 1398–1403.

Google Scholar

[2] F. Buckley and F. Harary, Distance in graphs, Addison-Wesley, CA, 1990.

Google Scholar

[3] F. Cao, D.Z. Du, D.F. Hsu, S.H. Teng, Fault tolerance properties of pyramid networks, IEEE Trans. Comput. 48 (1999) 88–93.

Google Scholar

[4] J.M. Chang, J.S. Yang,Y.L. Wang,Y. Cheng, Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs, Networks 14 (4) (2004) 302–310.