EMBEDDINGS INTO HYPER PETERSEN NETWORKS - YET ANOTHER HYPERCUBE-LIKE INTERCONNECTION TOPOLOGY

被引:30
作者
DAS, SK
OHRING, S
BANERJEE, AK
机构
[1] Department of Computer Science, University of North Texas, Denton
关键词
COMMUNICATION; EMBEDDING; FAULT TOLERANCE; HYPERCUBE; INTERCONNECTION NETWORK; PETERSEN GRAPH;
D O I
10.1155/1995/95759
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
A new hypercube-like topology, called the hyper Petersen (HP) network, is proposed and analyzed, which is constructed from the well-known cartesian product of the binary hypercube and the Petersen graph of ten nodes. This topology is an attractive candidate for multiprocessor interconnection having such desirable properties as regularity, high symmetry and connectivity, and logarithmic diameter. For example, an n-dimensional hyper Petersen network, HPn, with N = 1.25 * 2(n) nodes is a regular graph of degree and node-connectivity n and diameter n-1, whereas an (n - 1)-dimensional binary hypercube, Q(n-1), with the same diameter covers only 2(n-1) nodes, each of degree (n - 1). Thus the HP topology accommodates 2.5 times extra nodes than Q(n-1) at the cost of increasing the node-degree by one. With the same degree and connectivity of n, the diameter of the HP, network is one less than that of Q(n), yet having 1.25 times larger number of nodes. Efficient routing and broadcasting schemes are presented, and node-disjoint paths in HPn are computed even under faulty conditions. The versatility of the hyper Petersen networks is emphasized by embedding rings, meshes, hypercubes and several tree-related topologies into it. Contrary to the hypercubes, rings of odd lengths, and a complete binary tree of height n - 1 permit subgraph embeddings in HPn.
引用
收藏
页码:335 / 351
页数:17
相关论文
共 40 条
[1]  
ABRAHAM S, 1989, P INT C PARALLEL PRO, V1, P116
[2]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[3]  
BENTLEY JL, 1979, 1979 P INT C PAR PRO, P257
[4]  
BERMOND JC, 1989, HYPERCUBE AND DISTRIBUTED COMPUTERS, P279
[5]  
BHATT SN, 1990, COINS90108 U MASS CO
[6]  
BHATT SN, 1985, RR443 YAL U DEP COMP
[7]  
Chartrand G., 1985, GRAPHS APPL, P69
[8]  
Chartrand Gary, 2016, GRAPHS DIGRAPHS, VSixth, DOI DOI 10.1201/B19731
[9]  
DAS RK, 1992, 1992 INT C PAR PROC, V1, P72
[10]  
DAS SK, 1991, 22ND P INT C GRAPH T