四星狀圖形上之最佳排列擇徑方法

Abstract

可遞迴分解的結構化網路拓樸被廣範的運用在設計和製作一個平行處理的 環境. 幾年前, 布林n-cube因為可以用很少的鏈結來連結許多的節點而較 受歡迎. 近幾年來, n-star 的架構被提出來並且被證明擁有兩個很吸引 人的特性: 小的直徑(diameter)和分支數(degree).在本論文中, 我們針 對四星狀圖形考慮排列擇徑的問題. 我們以複製封包的新觀念為基礎, 提 出了一個可調式路由演算法(The adaptive on-line routing algorithm), 可以在最短的時間(diameter time steps)內完成這個工作. Decomposited structured network topologies are widely used in the design and implementation for parallel processing environment. A few years ago, Boolean n-cube was more popular because a large number of nodes can be interconnected using a small number of links. Recently, n-Star Graph has been presented and shown that it has two attractive properties: low diameter and degree. In this thesis, we consider a permutation routing problem for 4-star graphs, and present an adaptive on- line routing algorithm based on duplicating packets to solve this problem under its diameter time steps.