臺灣博碩士論文加值系統

星狀圖(Star Graph)擁有對稱性、高連結性、高可靠度以及簡單的路由策略等優異的拓樸特性，對於建構大型平行及分散式系統的連結網路極佔優勢；另外單方向星狀圖(Unidirectional Star Graph)更支援高速網路及高效能分散式運算等應用。有鑑於單方向星狀網路的發展，這篇論文研究單方向星狀圖上的路由策略，透過等價轉換cycle structure的概念，設計適用於單方向星狀圖路由的Routing cycle structure；這篇論文並且設計一套簡易的路由策略，此策略將根據Routing cycle structure來產生可行的路由路徑(feasible routing paths)。最後我們推導出在USn上，根據此篇論文提出的路由策略所產生之所有路由路徑，其最大長度將不超過[5(n-1)/2]+4，這個結果遠優於先前Day和Tripathi所提出的分散式路由策略(Distributed Routing Algorithm)，其最大的路由距離是5n-9。

The star graph has been recognized as an attractive alternative to the hypercube. It possesses many attractive topological properties, such as recursive structure, symmetry, maximal fault tolerance and a simple routing algorithm. In addition, the unidirectional star graph also supports high speed networking and high performance distributed computing. Motivated by the investigations on the unidirectional interconnection networks, this paper improves the previous result on routing in USn. In this paper, we equivalently transform the cycle structure into a specific cycle representation, the Routing cycle structure, and develop a scheme to specify the feasible routing paths upon the Routing cycle structure. The feasible routing paths accomplish the routing effectively in USn, and we conclud that the length of any feasible routing path is no more than [5(n-1)/2]+4. Obviously our scheme specifies a much shorter routing path than the routing algorithm proposed by Day and Tripathi (the maximal routing distance is 5n-9 in USn), and these feasible routing paths are nearly optimal.

LIST OF TABLES . . . . . . . . . . . . . . . . .iv
LIST OF FIGURES . . . . . . . . . . . . . . . . .v
I INTRODUCTION . . . . . . . . . . . . . . . . 1
II PRELIMINARIES . . . . . . . . . . . . . . . .3
2.1 The Star Graph . . . . . . . . . . . . . . .3
2.2 The Unidirectional Star Graph . . . . . . . .4
2.3 The Relative Cycle Structure . . . . . . . .5
III THE ROUTING SCHEME . . . . . . . . . . . . . 9
3.1 Our Approach . . . . . . . . . . . . . . . .11
3.2 Get the Routing cycle structure . . . . . . 13
3.2.1 Phase 1-Eliminate the pure-cycles . . . . 13
3.2.2 Phase 2 -Factorize cycle Ci . . . . . . . 16
3.2.3 Phase 3 -Get the good-cycles . . . . . . .22
IV THE ROUTING DISTANCE . . . . . . . . . . . . 24
V CONCLUSION . . . . . . . . . . . . . . . . . .29

[1] Abdel-Elah, Al-Ayyoub and Khaled Day, "Node-ranking schemes for the star networks," Journal of Parallel Distributed Computing, vol. 63, pp. 239-250, 2003.
[2] S.B. Akers and B. Krisnamurthy, "A group-theoretic model for symmetric interconnection networks," Proceeding of International Conference on Parallel Processing, pp. 216-223, 1986.
[3] S.B. Akers, D. Horel and B. Krisnamurthy, "The Star graph: An attractive alternative to the n-cube," Proceeding of the 1987 International Conference on Parallel Processing, Penn State University, pp. 393-400, 1987.
[4] N. Bagherzadeh, N. Nassif and S. Latifi, "A routing and broadcasting scheme on faulty star graphs," IEEE Transactions on Computers, vol. 42, no. 11, pp.1398-1403, 1993.
[5] N. Bagherzadeh, M. Dowd and N. Nassif, "Embedding an Arbitrary Tree into the Star Graph," IEEE Transactions on Computers, vol. 45, no. 4, pp. 475-481, Apr. 1996.
[6] W.K. Chiang and R.J. Chen, "The (n, k)-star graph: A generalized star graph," Information Processing Letters, vol. 56, pp. 259-264, 1995.
[7] E. Cheng and M.J. Lipman, "Orienting split-stars and alternating group graphs," Networks, vol. 35, pp.139-144, 2000.
[8] E. Cheng and M.J. Lipman, "On the Day-Tripathi orientation of the star graphs: connectivity," Information Processing Letters, vol. 73, pp. 5-10, 2000.
[9] E. Cheng, W.A. Lindsey and D.E. Steffy, "Maximal Vertex-Connectivity of USn,k," Networks, vol. 46, no. 3, pp. 154-162, 2005.
[10] K. Day and A. Tripathi, "Unidirectional star graphs," Information Processing Letters, vol. 45, pp. 123-129, 1993.
[11] K. Day and A. Tripathi, "A comparative study of topological properties of hypercubes and star graphs," IEEE Transactions on Parallel Distributed Systems, vol. 5, no. 1, pp. 31-38, 1994.
[12] K. Day and A. Tripathi, "Arrangement graphs: a class of generalized star graph," Information Precessing Letters, vol. 42, pp. 234-241, 1992.
[13] P. Fragopoulou and S.G. Akl, "A parallel algorithm for computing Fourier transforms on the star graph," IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 5, pp. 525-531, 1994.
[14] John B. Fraleigh, "A First Course In Abstract Algebra," ISBN. 0-201-53467-3, Addison Wesley, 1997.
[15] J.S. Jwo, S. Lakshmivarahan and S.K. Dhall, "Characterization of Node Disjoint (Parallel) Path in Star Graphs," 5th International Parallel Processing symposium, pp. 404-409, 1991.
[16] J.S. Jwo and T.C. Tuan, "On container length and connectivity in unidirectional hypercubes," Networks, vol. 32, pp. 307-317, 1998.
[17] S. Latifi, "On the Fault-Diameter of the Star Graph," Information Processing Letters, vol. 46, pp. 143-150, 1993.
[18] V. Mendia and D. Sarkar, "Optimal broadcastingon the star graph," IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 4, pp. 389-396, 1992.
[19] K. Qiu, S.G. Akl, and H. Meijer, "On some properties and algorithms for the star and pancake interconnection networks," Journal of Parallel and Distributed Computing, vol. 12, pp. 16-25, 1994.
[20] S. Ranka, J.C. Wang and N. Yeh, "Embedding meshes on the star graph," Journal of Parallel and Distributed Computing, vol. 19, pp. 131-135, 1993.
[21] S. Rajasekaran and D.S.L. Wei, "Selection routing and sorting on the star graph," Journal of Parallel and Distributed Computing, vol. 41, pp. 225--233, 1997.
[22] Y. Rouskov and P.K. Srimani, "Fault Diameter of Star Graphs," Information Processing Letters, vol. 48, pp. 243-251, 1993.
[23] J.P. Sheu, W.H. Liaw and T.S. Chen, "A broadcasting algorithm in star graph interconnection networks," Information Processing Letters, vol. 48, no. 15, pp. 237-241, 1993.