跳到主要內容

臺灣博碩士論文加值系統

(35.168.110.128) 您好!臺灣時間:2022/08/16 06:16
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:高英耀
研究生(外文):Ying-Yao Gao
論文名稱:最小直徑的雙迴圈網路
論文名稱(外文):Minimum Diameter Double-Loop Networks
指導教授:官大智官大智引用關係
指導教授(外文):D. J. Guan
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:28
中文關鍵詞:最佳拓樸直徑下界值雙迴圈網路
外文關鍵詞:lower bound lb(N)double-loop networksoptimal topologydiameter
相關次數:
  • 被引用被引用:0
  • 點閱點閱:161
  • 評分評分:
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:0
摘  要
雙迴圈網路在區域網路架構或是在分散式記憶體多處理器系統中是一種廣為使用的網路架構,因為它具有較小的直徑、容易路遊,而且在各個節點容易切換至另一個連結,因此它是一個非常穩定的網路架構。N表示網路中節點的個數,d(N)表示在一N個節點的雙迴圈網路中有可能的最短直徑,對於任一給定的N值, Bermond et al. [5], Boesch and Wang [7], 和 Yebra et al. [23]已經證明了 ,這是一個廣為人知的下界值,標記為lb(N)。此篇論文所討論的主題為給定一個N值,如何決定一個最佳的拓樸使得d(N)= lb(N),我們提供了一個非常簡單的計算公式,可以快速地找出搭配N值的最佳拓樸,可使得雙迴圈網路達到最佳化。
Abstract
  Double-loop networks have become one of the most popular architectures in the design of Local Area Networks and distributed memory multiprocessor systems. This is due to its characters of minimal diameter, easy routing, expandability and regularity. The switching mechanism at each node can easily be implemented using building blocks of the same specification. Therefore, double-loop networks have a high degree of reliability and hence very low vulnerability. Let N denote the number of nodes in a double-loop network and d(N) be the best possible diameter with N vertices. Given an N, Bermond et al. [5], Boesch and Wang [7], and Yebra et al. [23] have shown that . This is a well-known lower bound for d(N) and is usually denoted as lb(N). In this paper, what we discuss is finding an optimal topology such that d(N)= lb(N) for any given value of N. We provide a simple formula to find optimal topologies of double-loop networks with N nodes.
Contents Page
Abstract (in Chinese) ……………………………………………………………I
Abstract (in English) …………………………………………………………….II
Contents ………………………………………………………………………….III
List of Figures …………………………………………………………………..IV
List of Tables …………………………………………………………………..V
1. Introduction ……………………………………………………………………1
1.1 About this work …………………………………………………………. 2
2. Problem Definition and Notation …………………………………………. 4
3. Relevant Results ……………………………………………………………..8
4. Main Results ………………………………………………………………….13
4.1 Simple Formula to Compute Optimal N and h ………………………13
4.2 Comparison with Other Results ……………………………………….18
5. Future Work ………………………………………………………………….20
6. References …………………………………………………………………..21
6. References[1] B. W. Arden, and H. Lee, Analysis of chordal ring, IEEE Trans. Comput. C-30 (1981), 291-292.[2] R. Beivide, V. Vinals, and C. Rodriguez, Optimal topologies with four bidirectional links and its applications, Proc. IAESTED Int. Symp. AI’87, Grindelwald, Switzerland (1987), 66-69.[3] J. —C. Bermond, F. Comellas, and D. F. Hsu, Distributed loop computer networks: a survey, J. Parallel Distribut. Comput. 24 (1995), 2-10.[4] J. -C. Bermond, O. Favaron, and M. Maheo, Hamiltonian decomposition of Cayley graphs of degree four, J. Combinatorial Theory, Ser. B 46 (1989), 142-153.[5] J. —C. Bermond, G. Illiades, and C. Peyrat, An optimization problem in distributed loop computer networks, Third International Conference on Combinatorial Math. New York, U. S. A., June 1985, Ann. New York Acad. Sci. 555 (1989), 45-55.[6] J. —C. Bermond, and D. Tzvieli, Minimal diameter double-loop networks: Dense optimal families, Networks 21 (1991), 1-9.[7] F. T. Boesch, and J. K. Wang, Reliable circulant-networks with minimum transmission delay, IEEE Trans. Circuits System CAS-32 (1985), 1286-1291.[8] M. Y. Chen, and D. J. Guan, An optimal message routing algorithm for undirected double-loop networks, To Appear.[9] Y. Cheng, and F. K. Hwang, Diameters of weighted double loop networks, J. Algorithms 9 (1988), 401-410.[10] D. Z. Du, D. F. Hsu, Q. Li, and J. Xu, A combinatorial problem related to distributed loop networks, Networks 20 (1990), 173-180.[11] A. Grnarov, L. Kleinrock, and M. Gerla, A highly reliable distributed loop network architecture, Proc. Int. Symp. Fault-Tolerant Comput., Kyoto, Japan (1980), 319-324.[12] D. J. Guan, An optimal message routing algorithm for double-loop networks, Inform. Process Lett. 65 (1998), 255-260.[13] F. K. Hwang, A survey on double loop networks, in: F. Roberts, F. K. Hwang, C. Monma (Eds.), Reliability of Computer and Communication Networks, AMS Series (1991), 143-151.[14] F. K. Hwang, A complementary survey on double-loop networks, Theoretical Computer Science 263 (2001), 211-229.[15] F. K. Hwang, T. S. Lin, and R. H. Jan, A permutation routing algorithm for double loop networks, Para. Trans. Comput. 44 (1995), 1468-1471.[16] M. T. Liu, Distributed loop computer networks, Adv. Comput. 17 Academic, New York (1981), 163-221.[17] D. Nassimi, and S. Sahni, An optimal routing algorithm for mesh connected parallel computers, J. ACM 27 (1980), 6-29.[18] C. S. Raghavendra, M. Gerla, and A. Avizienis, Reliable loop topologies for large local computer networks, IEEE Trans. Comput. 34 (1985), 46-55.[19] C. S. Raghavendra, and P. Kumar, Permutations on Illiac-4 type networks, IEEE Trans. Comput. C-35 (1986), 662-669.[20] C. S. Raghavendra, and J. A. Sylvester, A survey of multi-connected loop topologies for local computer networks, Comput. Netw. ISDN Syst. 11 (1986), 29-42.[21] D. Tzvieli, Minimal diameter double-loop networks: Part I: Large infinite optimal families, Networks 21 (1991), 387-415.[22] C. K. Wong, and D. Coppersmith, A combinatorial problem related to multimodule memory organizations, J. ACM 21 (1974), 392-402.[23] J. A. L. Yebra, M. A. Fiol, P. Morillo, and I. Alegre, The diameter of undirected graphs associated to plane tessellations, Ars Combinatoria 20B (1985), 151-171.[24] J. Žerovnik, and T. Pisanski, Computing the diameter in multiple loop networks, J. Algorithms 14 (1993), 226-243.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top