三環網路的緊密族群及寬直徑之研究

THE STUDY ON THE DENSE FAMILIES AND WIDE-DIAMETERS OF THE TRIPLE-LOOP NETWORK

陳珊妤(San-Yu Chen)

指導教授 ： 張薰文

大同大學/電機資訊學院/應用數學學系所/碩士(2005年)

摘要

多環網路因其架構簡單及點對稱等特性，時常做為通訊網路的架構，並受到廣泛的討論。相對於單環網路的低可靠度與長傳輸延遲，以及高環網路的高硬體複雜度，本論文將著重於三環網路之研究。
在三環網路 $TL(N ;s_1, s_2, s_3) $中，每一節點可連結至其後差距 $s_1$、$s_2$ 、及$s_3$ 三點。針對網路的族群，有兩個重要的對偶問題：一為在直徑固定時，找尋包含最多節點數的網路，其可應用於在給定的傳輸延遲下，所能服務最多的使用者；一為在節點數固定時，找尋最佳三參數使得網路具有最小直徑，其可應用於找最小傳輸延遲。由於緊密族群並不具有單調性，因此更增問題的困難度。本論文的第一部份研究三環網路的對偶問題，並提出五個新緊密族群以改進現有的結果。
在另一方面，網路的寬直徑可做為容錯能力的指標。本論文第二部份針對Hyper-L型三環網路，提出任兩點間的互不相交路徑，並推導出Hyper-L型三環網路的寬直徑，除了兩特例為$D+2$以外，其餘皆為$D+1$ 。此外，我們也研究Hyper-L型三環網路的傳輸，依據互不相交路徑的長短，分配適當的工作量，使得總傳輸時間最短，而得到最佳點對點的傳輸方式。

關鍵字

三環網路 ； 超L三環網路 ； 最小距離圖 ； 互不相交路徑 ； 寬直徑

並列摘要

With simple construction and node-symmetric properties, multiple-loop networks have been widely studied and used in data communication. Relative to low reliability and long transmission delay of single-loop (ring) networks and to high hardware complexity of high-loop networks, in this thesis, we concentrate on the triple-loop network.
In the triple-loop network $TL(N ;s_1, s_2, s_3) $ , every node connects to the nodes with differences $s_1$ , $s_2$ , and $s_3$. There are two important dual problems of dense families. One is to find the maximum number of nodes for fixed diameters, which has an important application to maximizing the support of services under fixed transmission delay. The other one is to find the minimum diameter for a fixed number of nodes by determining three parameters, which has an application to finding minimum transmission delay. Note that the problem of dense families is difficult because it is not monotonic. In the first part of this thesis, we survey the literatures and present five new dense families of triple-loop networks to improve the previous results.
On the other hand, the wide-diameter of a network is an important measure of fault-tolerance. In the second part of this thesis, we present disjoint paths between any two nodes of the hyper-L triple-loop network and determine the wide-diameter of the hyper-L triple-loop network to be $D+1$, except two cases with $D+2$. Moreover, we apply the disjoint paths to optimal one-to-one data communication of the hyper-L triple-loop network. According to the lengths of disjoint paths, we partition suitable workloads to each path such that the total transmission delay is minimized.

並列關鍵字

Disjoint Paths ； Hyper-L Triple-Loop Network ； Minimum Distance Diagram ； Triple-Loop Network ； Wide-Diameter

參考文獻

[1] F. Aguiló and M. A. Fiol, “An Efficient Algorithm to Find Optimal Double-Loop Networks,” Discrete Math., Vol. 138, pp. 15-29, 1995.

[2] F. Aguiló, M. A. Fiol, and C. Garcia, “Triple-Loop Networks with Small Transmission Delay,” Discrete Math., Vol. 167/168, pp. 3-16, 1997.

[3] F. Aguiló-Gost, “New Dense Families of Triple Loop Networks,” Discrete Math., Vol. 197/198, pp. 15-27, 1999.

[4] B. W. Arden and H. Lee, “Analysis of Chordal Ring Network,” IEEE Trans. Comput., Vol. 30, pp. 291-295, 1981.

[5] R. C.-F. Chan, C. Chen, and Z.-X. Hong, “A Simple Algorithm to Find the Steps of Double-Loop Networks,” Discrete Appl. Math., Vol. 121, pp. 61-72, 2002.