臺灣博碩士論文加值系統

我們在這篇論文中提出在單方向星狀圖中給定任意兩點間的路由演算法，藉由一個特別的cycle structure，稱之為feasible routing cycle structure，來實現我們的路由演算法。我們在論文中證明得到的路由路徑可以有效率的完成單方向星狀圖中任意兩點間的路由，並且證明單方向星狀圖的直徑當n 5時不會超過2n。這個結果比起Day和Tripathi所提出的分散式路由演算法(DRA)有顯著的進步，而且對於先前已知的單方向星狀圖直徑明顯的更接近最佳解。此外，在單方向星狀圖中最長路由路徑當5 n 12時也和計算出的直徑相同。

In this paper, we propose a routing algorithm between any two nodes in the unidirectional star graph upon the specific cycle representation, called the feasible routing cycle structure (RCS), which is equivalently transformed from the cycle structure. We prove that the feasible routing path can accomplish the routing effectively in the unidirectional n-star graph USn, and also derive that the diameter is no more than 2n for n 5 in USn. We also show that our routing algorithm could be performed in time O(n2). The result shows a great improvement to the corresponding result of distributed routing algorithm (DRA) proposed by Day and Tripathi (the maximal routing distance is 5n-9 in USn. That is, the previous known bound for the diameter of USn is substantially improved and nearly optimal. Moreover, the upper bound of the maximal routing distance is the same as the calculated diameters for 5 n 12 in USn.

1 Introduction ………………………………………………...1
2 Preliminary …………………………………………………2
3 Our Approach ………………………………………………4
3.1 The Relative cycle structure ………………………………….. 4
3.2 The Routing cycle structure and the feasible routing path ….....6
3.3 Our routing algorithm ………………………………………….7
3.3.1 Phase 1 - Generate the Relative cycle structure ………… 8
3.3.2 Phase 2 - Analyze the Relative cycle structure …………. 8
3.3.3 Phase 3 - Merge the pure cycles with other cycles or
invariant positions ….………………………....10
3.3.4 Phase 4 - Get the good cycles ………………………….. 12
3.3.5 Phase 5 - Derive the feasible routing path ………………14
4 Routing Distance and Diameter..…………………………..15
5 Conclusion ………………………………………………...29

[1] Abdel􀀀Elah, Al􀀀Ayyoub, and K. 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 intercon-nection 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. Lati…, “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. Stey, “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, 1993.
[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. Lati…, “On the Fault􀀀Diameter of the Star Graph,”Information Processing Letters, vol. 46, pp. 143-150, 1993.
[18] V. Mendia and D. Sarkar, “Optimal broadcasting on 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.