互连网络的向量图模型

A Vector Graph Model for Interconnection Networks

n-超立方体、环网、k元n超立方体、Star网络、煎饼(pancake)网络、冒泡排序(bubble sort)网络、对换树的Cayley图、De Brujin图、Kautz图、Consecutive-d有向图、循环图以及有向环图等已被广泛地应用做处理机或通信互连网络.这些网络的性能通常通过它们的度、直径、连通度、Hamiltonian性、容错度以及路由选择算法等来度量.首先提出了有向向量图和向量图的概念;其次,开发了有向向量图模型和向量图模型来更好地设计、分析、改良互连网络.进一步证明了上述各类著名互连网络都可表示为有向向量图模型或向量图模型.更重要的是该模型能够设计出新的互连网络-双星网络和三角形网络.

n-cube, ring network, k-ary-n-cube, star network, pancake network, bub- ble sort network, Cayley graph of transposition tree, De Bruijn network, Kautz network, consecutive-d digraph, ILLIAC network, circulant digraph, circulant undirected graph, ring digraph,etc have been widely used as processor or communication networks. The performance of such networks is often measured through an analysis of their degree, diameter, connectivity, fault tolerance, routing algorithm, etc. In this paper, we proposed the concepts -- vector digraph and vector graph. Second, we developed vector digraph model and vector graph model for interconnection networks for designing, analyzing, and improving above networks. Furthermore, we show that the networks mentioned above can be concisely represented in the two models. More importantly, we show that the two models enabled us to design new networks -- double star network and triangle network based on vector graphs.