新複合傳送策略的廣義不阻塞

Wide-sense Nonblocking Under New Compound Routing Strategies

徐仲煒(Jhong-Wei Syu)

指導教授 ： 郭君逸

國立臺灣師範大學/理學院/數學系/碩士(2010年)

摘要

張等人證明了對稱三級式克勞斯網路和多重對數網路在「沒用到的中繼交換器留到最後(STU)」、「最忙碌的中繼交換器優先(P)」、「最小編號的中繼交換器優先(MI)」、「從上次編號的中繼交換器開始(CS)」以及「從下一個編號的中繼交換器開始(CD)」這六個傳送策略下，達成廣義不阻塞所需的條件和嚴格不阻塞是一樣的。在這篇論文裡，我們從 P 和 STU 這兩個策略延伸出六個新的傳送策略，並且證明出和嚴格不阻塞一樣的結果。我們也針對了垂直多重網路考慮了一些條件，並證明在這些條件下，達成廣義不阻塞在這六個策略下所需的條件和嚴格不阻塞是一樣的。

關鍵字

嚴格不阻塞 ； 廣義不阻塞 ； 克勞斯三級式網路 ； 多重對數網路

並列摘要

Chang et al. showed that the symmetric 3-stage Clos network or the multi-log_d N network is SNB if and only if it is WSNB under any of the five strategies: save the unused, packing, cyclic dynamic, and cyclic static. In this paper, we extend the strategies P and STU to six new strategies and get the same results for these strategies. We also consider the conditions of the vertical-copy network such that it is SNB if and only if it is WSNB under these six strategies.

並列關鍵字

SNB ； WSNB ； 3-stage Clos network ； multi-log_d N network

參考文獻

J. C. Bermond, J. M. Fourneau, and A. Jean-marie, Equivalence of multistage interconnection networks, Information Processing Letter 26 (1987) 45-50.

D.G. Cantor, On nonblocking switching networks, Networks. 1(1971) 367-377.

F.H. Chang, J.Y. Guo, F.K. Hwang, J.K. Lin, Wide-sense nonblocking for symmetric or asymmetric 3-Stage Clos networks under various routing stragegies, Theoret. Comput. Sci. 314 (2004) 375-386.

F.H. Chang, J.Y. Guo, F.K. Hwang, Wide-sense nonblocking for multi-lod_d N networks under various routing strategies, Theoret. Comput. Sci. 352 (2006) 232-239.

Clos, C., A study of non-blocking switching networks, Bell Syst. Tech. J., 32, 406-424.