設計與分析超立方體與星狀圖架構之連結網路

Abstract

『超立方體』(Hypercubes) 與『星狀圖』(Star graphs) 是 目前最受矚目的兩個連結網路 (Interconnection networks) 架構。為了 提昇效能或針對特定的需求，它們的一些變形相繼被提出與探討。在這篇 論文當中，我們將更深入分析兩個已被提出的網路架構：分別是『層次超 立方體狀網路』(Hierarchical Cubic Networks) 與『編排圖』( Arrangement graphs) 。此外，我們將提出兩個『超立方體』狀的連結網 路： 分別是 『多層次超立方體』(Multilevel hypercubes) 與 『金字 塔化超立方體』(Pyramided hypercubes) 。前者是『層次超立方體狀網 路』的一般化架構；而後者是一個具有最佳容錯能力的網路架構，在結點 間互連程度固定下，其系統可作彈性延伸，此架構可視為用來取代『延伸 性超立方體』(Extended hypercubes) 的一種選擇。另外，我們也將提出 一個『星狀圖』架構的變形，稱之為『(n,k)-星狀圖』((n,k)-Star graphs) ，是『星狀圖』網路的一般化架構，也可視為用來取代『編排圖 』網路架構的另一種選擇。論文最後，我們將『超立方體』與『星狀圖』 的優點加以結合，設計出一個新的網路連結策略，稱之為『區段互調式網 路』 (Block-swapped networks) 架構。 The hypercube and the star graph have been two of the most popular interconnection networks. Several variations of them have been proposed and investigated to overcome their shortcomings. In this dissertation, we will further analyze the topological properties of two already proposed network topologies: the hierarchical cubic network and thearrangement graph. In addition, we will propose two cube-based interconnection networks: the multilevel hypercube and the pyramided hypercube; the former can be considered as a generalization of the hierarchical cubic network, the latter is an optimal fault tolerant network for extendability with fixed degree as an alternative to the extended hypercube. We will also propose a star-based interconnection network called the (n, k)-star graph; it is a generalization of the star graph as an alternative to the arrangement graph. Finally, we will propose a new interconnection scheme, called the block-swapped network, combining positive features of both the hypercube and the star graph.