跳到主要內容

臺灣博碩士論文加值系統

(54.225.48.56) 您好!臺灣時間:2022/01/19 22:03
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳沅百
研究生(外文):Yuanpai Chen
論文名稱:雙環式網路兩點間之可容錯路線演算法
論文名稱(外文):A Fault-Tolerant Two Terminals Routing Algorithm of Double-Loop Networks
指導教授:陳秋媛陳秋媛引用關係
指導教授(外文):Chiuyuan Chen
學位類別:碩士
校院名稱:國立交通大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:27
中文關鍵詞:雙環式網路訊息傳送最佳路線訊息傳送可容錯路線
外文關鍵詞:double-loop networkoptimal message routingfault-tolerant message routing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:122
  • 評分評分:
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
訊息傳送是網路的一個基本功能,而可容錯的特性可以確保網路傳送的品質。通常假設雙環式網路中最多只有一個點或邊發生錯誤,而且錯誤發生在哪裡是無法事先知道的。在不要求事先知道錯誤發生在哪裡的前提下,我們發展了一個經由兩條點不重複的路徑傳送兩個相同的訊息到目的地的演算法,並且保證其中一個訊息會避過錯誤、而且走最短路徑將訊息傳送到目的地,此演算法在每個端點只需要花常數時間即可判斷下一步要將訊息傳送到哪一點。

Delivering messages between two terminals is a very important function of a network. Fault-tolerant is an important criteria to ensure the quality of a network. Under this circumstance that there is at most one edge (or node) fault in the double-loop network and the fault can not be detected before a message is sent, we propose a routing algorithm which simultaneously sends two messages to the destination along two node-disjoint routes among which at least one route is optimal. At each vertex, our algorithm spends only constant time and space to determine which
vertex is the next vertex that the message should be sent.

Contents
Abstract (in Chinese) i
Abstract (in English) ii
Acknowledgement iii
Contents iv
List of Figures v
List of Tables vi
1. Introduction 1
2. The five cases 5
3. Our algorithm 13
4. The comparison of CGW’s algorithm, LWG’s algorithm and
our algorithm 17
5. Conclusions 24
References 25
Appendix 26

Y. Cheng and F.K. Hwang, ``Diameters of weighted double loop
networks,'' J. Algorithms 9 (1988), 401-410.
C.Y. Chou, D.J. Guan, and K.L. Wang ``A dynamic fault-tolerant
message routing algorithm for double-loop networks,''
Information Processing Letters 70 (1999), 259-264.
M.A. Fiol, J.L.A. Yebra, I. Alegre, M.Valero, ``A discrete
optimization problem in local networks and data alognment,'' IEEE Trans. Computers 36 (1987), 702-713.
D.J. Guan, ``An optimal message routing algorithm for double-loop networks,'' Information Processing Letters 65 (1998),
255-260.
F.K. Hwang, ``A complementary survey on double-loop networks''
Theortical Computer Science 263 (2001), 211-229.
Y.L. Liu, Y.L. Wang, and D.J. Guan, ``An optimal fault-tolerant
routing algorithm for double-loop networks,'' IEEE Trans.
Computers 50 (2001), 500-505.
C.K. Wong and D. Coppersmith, ``A combinatorial problem related to multimodule organizations,'' J. Assoc. Comput. Mach. 21 (1974), 392-402.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top