標題: 雙固定路徑迴狀網路之最佳路由方法
Optimal Routing Methods for Double Fixed-step Loop Networks
作者: 林再順
Tzai-Shunne Lin
簡榮宏
Rong-Hong Jan
資訊科學與工程研究所
關鍵字: 迴狀網路;網路直徑;平均節點距離;排列擇徑;Loop network; Diameter of network; Mean distance; Permutation routing
公開日期: 1993
摘要: 分散式迴狀網路廣泛地使用在區域網路及平行處理系統;雙固定路徑迴狀
網路是分散式迴狀網路的一種,它的N個節點形成一個迴路且每個節點有
另一條路徑連接到固定距離的節點上。在所有雙固定路徑迴狀網路中有一
種網路架構,它的直徑(Diameter)最短,我們稱它為最佳的雙固定路徑
迴狀網路。在本論文中,我們將證明這種網路架構的平均節點距離也是所
有雙固定路徑迴狀網路中最短的(當N< 1014 時)。隨後我們在這種網
路架構下提出兩種最佳的路由方法,第一種為起始節點到目的節點最短路
徑的路由方法( Optimal Source-to-Sink Routing),第二種為最佳排
列擇徑的路由方法(Optimal Permutation Routing);此兩種方法均保
證能在最短時間內完成路由的工作。
Distributed Loop Networks are widely used in the design and
implementation of local area network and parallel processing
architectures. Double Fixed-step Loop Network (DFLN) is one
kind of Distributed Loop Networks; A DFLN consists of a loop of
N vertices where each vertex is also connected by another
vertex with fixed distacne. There is one network structure
which has minimum diameter among all DFLNs. We call them
optimal DFLNs. In this thesis, we will show that the network
structure has minimum mean distance among DFLNs (when N <
1014). In addition, we consider two routing problems for this
kind of network. One is an optimal source-to-sink routing
problem. The other is permutation routing problem. We show that
the minimum hop can be obtained by our source-to-sink routing
method, and the largest steps for any permutation routing is
the diameter of the network by the method we proposed.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT820394057
http://hdl.handle.net/11536/57958
顯示於類別:畢業論文