對於弦環式網路上直徑的研究

On the Study of the Diameter of Chordal Ring Network

劉士慶(Ching-Shih Liu)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系暨研究所/碩士(2010年)

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

摘要

環狀網路是最簡單的網路架構。由於環狀網路的可靠度低、傳輸延遲高，因此，以環狀網路為基礎的混合式環狀網路結構相繼被提出，以提高其可靠度與降低其傳輸延遲（亦即直徑）。弦環式網路是在環狀網路的結構中增加弦，使得其可靠度提高、直徑降低。Arden 和Lee 在[1]中對於弦環式網路發表了一個公式來計算其直徑；此直徑公式包含了三個狀況，且第三個狀況中還包含了五個子狀況：子狀況3.1、3.2、3.3、3.4 和3.5。Huang 和Chen 在[8]中指出Arden 和Lee 的直徑公式中的第三個狀況是錯的。在本論文中，我們執行電腦程式以得到直徑公式中的每個狀況所佔有的百分比、和第三個狀況中五個子狀況錯誤的比例。我們特別觀察到直徑公式在子狀況3.4 是完全正確的，而且符合子狀況3.4 的N 有特殊形式。

關鍵字

連接網路 ； 環狀網路 ； 弦環式網路 ； 直徑

並列摘要

One of the simplest topologies for interconnection networks is the ring network. Since the ring network has poor reliability and high transmission delay, hybrid topologies utilizing the ring network as a basis for synthesizing richer interconnection schemes have been proposed to improve the reliability and reduce the transmission delay (the diameter). The chordal ring network is a commonly used extension for the ring network and it is considered to be obtained by adding chords to a ring network so that the diameter can be reduced and the reliability can be increased. In [1], Arden and Lee proposed a formula for computing the diameter of a given chordal ring network; this diameter formula consists of three cases and case 3 of
it consists of five subcases: subcases 3.1, 3.2, 3.3, 3.4 and 3.5. In [4], Huang and Chen pointed out that case 3 of the diameter formula is incorrect. In this thesis, we run a computer program to obtain the percentage of each of the three cases of the diameter formula, the percentage of each of the five subcases of case 3, and the faulty percentages for the five subcases of case 3. In particular, we observe that subcase 3.4 is never incorrect and the N that
satisfying subcase 3.4 is of a specific form.

並列關鍵字

interconnection network ； ring network ； chordal ring network ； diameter

參考文獻

[1] B. W. Arden and H. Lee, Analysis of chordal ring network networks, IEEE Trans.Comput. C-30 (1981) 291-295.

[2] J. C. Bermond, F. Comellas, and D. F. Hsu, Distributed loop computer-networks - a survey, J. Parallel and Distrib. Comput. 24(1) (1995) 2-10.

[3] S. K. Chen, F. K. Hwang, and Y. C. Liu, Some

Combinatorial Properties of Mixed chordal ring networks, Journal of Interconnection Networks 4 (2003) 3-16.

[4] H. C. Huang, The diameter-edge-invariant property of chordal ring networks, Master Thesis, National Chiao Tung University, Taiwanm 2009.