雙固定路徑迴狀網路之最佳路由方法

Abstract

分散式迴狀網路廣泛地使用在區域網路及平行處理系統；雙固定路徑迴狀 網路是分散式迴狀網路的一種，它的Ｎ個節點形成一個迴路且每個節點有 另一條路徑連接到固定距離的節點上。在所有雙固定路徑迴狀網路中有一 種網路架構，它的直徑（Diameter）最短，我們稱它為最佳的雙固定路徑 迴狀網路。在本論文中，我們將證明這種網路架構的平均節點距離也是所 有雙固定路徑迴狀網路中最短的（當Ｎ＜ 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.