連接網路上的一些通訊問題

Some Communication Issues on Interconnection Networks

張書豪(Shu-Hao Chang)

指導教授 ： 王振仲

義守大學/電機資訊學院/資訊工程學系/博士(2015年)

https://doi.org/10.6343/ISU.2015.00260

摘要

一平行分散式系統通常可以使用一個圖來表示，在設計一平行分散式
系統有兩個考慮的重點: 通信延遲與容錯傳輸延遲。在平行分散式系
統兩個處理器之間的最大通信延遲可以由其表示的圖的直徑來決定，而圖的直徑會隨著圖上邊的增減而改變。我們證明n 維超立方體可以增加22k–1個邊來降低他的直徑k, 2≤ k ≤ n/2 。 對於容錯傳輸延遲我們探討圖的衍生連通性，我們證明廣義皮特森圖P(n, 3)是全域3*連通若且為若n 為奇數。

關鍵字

none

並列摘要

A parallel and distributed system is usually represented by a graph. In a parallel and distributed system, we consider two important issues, namely, communication delay and fault tolerant transmission delay. The maximum communication delay between any pair of processors in a parallel and distributed system can be determined by the diameter of its underlying graph. The diameter of a graph can be affected by the addition or deletion of edges. We had shown that an n-dimensional hypercube can be decreased by k with the addition of 22k−1 edges for 2 ≤ k ≤ ⌊n/2⌋. We would like to compute the diameter variability caused by the removal of
edges in a hypercube. For fault tolerant transmission delay, we consider the spanning connectivity of a graph. We would like to prove that general Peterson graph P(n, 3) with odd n is globally 3∗-connected which is one factor of spanning connectivity.

並列關鍵字

none

參考文獻

[2] B. Alspach, “The classification of hamiltonian generalized Petersen graphs,” Journal of Combinatorial Theory B 34 (1983) 293–312.

[3] B. Alspach and J. Liu, “On the Hamilton connectivity of generalized Petersen graphs,” Discrete Mathematics 309 (2009) 5461–5473.

[4] B. Alspach, P. J. Robinson, and M. Rosenfeld, “A result on Hamiltonian cycles in generalized Peterson graphs,” J. Combinatorial Theory, Ser. B 31 (1981) 225–231.

[5] B. Alspach, “The classification of Hamiltonian generalized Peterson graphs,” J. Combinatorial Theory, Ser. B 34 (1983) 293–312.

[6] K. Bannai, “Hamiltonian cycles in generalized Peterson graph,” J. Combinatorial Theory, Ser. B 24 (1978) 181–188.