English

运筹学学报

• 运筹学 • 上一篇    下一篇

互连网络的向量图模型

  师海忠, 牛攀峰, 马继勇, 侯斐斐   

  1. 1. 西北师范大学数学与信息科学学院
    2. 甘肃省兰州市西北师范大学数学与信息科学学院
  • 收稿日期:2011-04-28 修回日期:2011-07-12 出版日期:2011-09-20 发布日期:2011-09-29
  • 通讯作者: 师海忠 E-mail:shihaizhong@nwnu.edu.cn

A vector graph model for interconnection networks

 SHI  Hai-Zhong, NIU  Pan-Feng, MA  Ji-Yong, HOU  Fei-Fei   

  • Received:2011-04-28 Revised:2011-07-12 Online:2011-09-20 Published:2011-09-29

PDF

1342

被引次数

13

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

关键词: 互连网络, 有向向量图, 向量图, 双星网络, 三角形网络

Abstract: the n-cube, the ring network, the k-ary-n-cube, the star network, the pancake network, the bubble sort network, the Cayley graph of transposition tree, the De Bruijn network, the Kautz network, the consecutive-d digraph, the ILLIAC network, the circulant digraph, the circulant undirected graph, the ring digraph, etc have been widely used as processor/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, at first, 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 shew that the networkd mentioned above can be concisely represented in the two models. More importantly, we shew that the two models enabled us to design new networks --- double star network and triangle network based on vector graphs.

Key words:  interconnection network, vector digraph, vector graph, double star network, triangle
network