交換超立方體的拓撲性質之研究

A Study on Topological Properties of Exchanged Hypercubes

蔡宗翰(Tsung-Han Tsai)

指導教授 ： 譚建民 ； 陳玉專

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

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

摘要

拓撲性質對於分析網絡之間互連研究已成為是一種普及和重要的領域， n維超立方體是用於網絡間互連最廣泛討論的拓撲結構中的一種，並且通常包括在介紹的基本原理和網絡設計的方法，交換超立方體EH(s, t) 是具有略超過超立方體的一半的邊之一個新的變型，並保持該超立方體的若干有價值且所期望的性質，例如：小直徑，泛偶圈和超級連通性。
在本篇論文當中，我們研究了在交換超立方體EH(s, t) 中的寬直徑和損壞直徑，我們建構出在交換超立方體EH(s, t) (3 ≤ s ≤ t) 中任何兩點之平行路由會產生出s+1 (或 t+1) 條不相交的路徑，而且也證明其(s + 1)-寬直徑和s-損壞直徑都是s + t + 3。除此之外，我們提出了一個方法是針對交換超立方體EH(s, t) 從起始點至目標點的最短路徑路由演算法，其時間複雜度為O(n)，其中n = s +t+1且1 ≤ s ≤ t。然後，我們專注在邊壅塞度，它是在互連網絡中成本分析和性能測量的一個重要指標。基於我們的最短路徑路由演算法，我們證明了在交換超立方體EH(s, t) 的邊壅塞度是3 · 2^(s+t+1) − 2^(s+1) − 2^(t+1)。最後，我們驗證了我們的最短路徑路由演算法關於交換超立方體EH(s, t) 的邊壅塞度是一個最佳的路由策略。

關鍵字

超立方體 ； 交換超立方體 ； 連結網路 ； 不相交的路徑 ； 寬直徑 ； 損壞直徑 ； 最短路徑路由 ； 邊壅塞度

並列摘要

Topological properties have become a popular and important area of focus for studies that analyze interconnections between networks. The n-dimensional hypercube is one of the most widely discussed topological structures for interconnections between networks and is usually covered in introductions to the basic principles and methods for network design. The exchanged hypercube EH(s, t) is a new variant of the hypercube that has slightly more than half as many edges and retains several valuable and desirable properties of the hypercube such as a small diameter, bipancyclicity, and super connectivity.
In this dissertation, we study the wide diameter and fault diameter of exchanged hypercubes EH(s, t). We construct s+1 (or t+1) internally ver-tex-disjoint paths between any two vertices for parallel routes in the exchanged hypercube EH(s, t) for 3 ≤ s ≤ t. We also show that both the (s + 1)-wide diameter and s-fault diameter of the exchanged hypercube EH(s, t) are s + t + 3 for 3 ≤ s ≤ t. Moreover, we propose an approach for shortest path routing algorithms from the source vertex to the destination vertex in EH(s, t) with time complexity O(n), where n = s +t+1 and 1 ≤ s ≤ t. Then, we focus on edge congestion, which is an important indicator for cost analyses and performance measurements in interconnection networks. Based on our shortest path routing algorithm, we show that the edge congestion of EH(s, t) is 3 · 2^(s+t+1) − 2^(s+1) − 2^(t+1). Finally, we prove that our shortest path routing algorithm is an optimal routing strategy with respect to the edge congestion of EH(s, t).

並列關鍵字

hypercube ； exchanged hypercube ； interconnection network ； internally vertex disjoint paths ； wide diameter ； fault diameter ； shortest path routing ； edge congestion

參考文獻

[3] C. P. Chang, T. Y. Sung, and L. H. Hsu, “Edge Congestion and Topological Properties of Crossed Cubes,” IEEE Trans. on Parallel and Distributed Systems, vol. 11, no. 1, pp. 64-80, 2000.

[1] M. Andrews, J. Chuzhoy, V. Guruswami, S. Khanna, K. Talwar, and L. Zhang, “Inapproximability of Edge-disjoint Paths and Low Congestion Routing on Undirected Graphs,” Combinatorica, vol. 30, no. 5, pp. 485-520, 2010.

[2] J. A. Aroca and A. F. Anta, “Bisection (Band)Width of Product Networks with Application to Data Centers,” IEEE Trans. on Parallel and Distributed Systems, vol. 25, no. 3, pp. 570-580, 2014.

[4] C. P. Chang, J. N. Wang, and L. H. Hsu, “Topological properties of twisted cube,” Information Sciences, vol. 113, pp. 147-167, 1999.

[5] C. Chekuri, S. Khanna, and F. B. Shepherd, “Edge-disjoint Paths in Planar Graphs with Constant Congestion,” SIAM J. Comput., vol. 39, no. 1, pp. 281-301, 2009.