双环Petersen网络直径公式及最优路由算法

双环Petersen图互联网络DLCPG(k)是双环网络与Petersen图的笛卡尔积,它具有良好的可扩展性、较短的网络直径和简单的拓扑结构等特性。通过研究其拓扑结构,得到了DLCPG(k)直径的显式公式,并给出了该网络的最优单播路由算法。     

二维环/双环互连Petersen图网络及其路由算法

基于双环结构提出了一种Petersen图的新扩展方法 ,并在此基础上构造了一个 2维双环互连Petersen图网络DCP(k) .分析了 2维环互连Petersen图网络TCP(k)的特性 ,给出了TCP(k)优于 2 DTorus互联网络的直径及可分组性的条件 .证明了DCP(k)和TCP(k)具有良好的可扩性和连接度 ;而且对 10×k个节点组成的互联网络 ,DCP(k)和TCP(k)均具有比RP(k)及 2 DTorus互联网络更小的直径和更优越的可分组性 .最后 ,分别设计了DCP(k)和TCP(k)上的单播和广播路由算法 ,证明了其通信效率较RP(k)上的对应算法均分别有明显提高 ,且DCP(k)更优于TCP(k) .     

基于超立方体环连接的Petersen图互联网络研究

基于环的简单扩展性,Petersen图的短直径与超立方体互联网络中节点的高可连接性相结合,提出了一种新型互联网络RHP(n)(Ringed Hypercube Connected Petersen),并对其特性进行了研究．证明了RHP(n)网络不但具有正则性以及良好的可扩展性,同时还具有比Q、HP(n)网络更短的直径和更小的构造开销．另外,还基于RHP(n)网络分别给出了其上的单播和广播路由算法,证明了其通信效率分别为n-1和n-1．     

一种实用的互联网络拓扑结构RPC(k)及路由算法

Pertersen图由于具有短直径和正则性等特性,在并行计算与分布式计算中具有良好的性能.基于环结构,提出了一种Pertersen图的新扩展方法,构造了互联网络RPC(k).分析了该互联网络的性质,它具有连接度小、网络直径短、拓扑结构简单以及易于扩展等特点.同时给出了RPC(k)优于二维Torus以及RP(k)互联网络的直径和节点可分组性的条件.最后,分别设计了RPC(k)上的单播路由、置换路由、广播路由和多对多路由,它们的通信效率分别为「k/2」+5,k+9,「k/2」+5和k+9.特别是随着k的增大,RPC(k)网络路由算法的通信效率近似于RP(k)网络上的时应算法通信效率的1/3倍.     

Torus连接Petersen图互连网络及路由算法

可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素.基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络.该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性.网络节点采用混合编码方法,使得路由算法设计简单.分别设计了基于混合编码的单播、广播路由算法.分析表明提出的互连网络具有较好的拓扑性质.     

一种实用的互联网络RPn(k)及其路由算法

基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销。最后,讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步。在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高。     

互联网络RCP(n)的路由算法

在对互联网络RCP（Ringed Crossed cube Petersen）拓扑结构研究的基础上,利用RCP（n）网络具有正则性,良好的可扩展性,以及具有比Q_n、HP（n）、RHP（n）网络更短的直径和更小的构造开销这些特性,给出了RCP（n）的单播路由算法和广播路由算法,并证明了RCP（n）比Q_n、HP（n）、RHP（n）网络具有更好的路由性能。     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

多连通多边形的内部Voronoi图的顶点和边数的上界

多边形的Voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held证明了一个简单多边形的内部Voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中n和k分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其Voronoi图转化为有根树,并利用有根树的性质,给出了其内部Voronoi图的顶点和边数上界的估计,并对Voronoi区域的边界所包含顶点和边数的平均值进行了讨论."SDU数字博物馆"系统所采用的基于Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.     

一种支持多维资源描述的高效P2P路由算法

在分析现有P2P(peer to peer)路由算法的基础上,提出了一种基于二阶矩定位、支持多维资源数据描述的高效资源路由算法--FAN(flabellate addressable network)路由算法.FAN算法将节点映射到统一的多维笛卡尔空间,并以节点相对空间原点的二阶矩作为子空间管理和资源搜索的依据.FAN路由算法具有O(log(N/k))的高路由效率,在节点加入和退出FAN网络时,更新路由信息的代价为O(klog(N/k)).实验结果表明,FAN路由算法具有路由效率高、维护代价小的优点,是一种P2P环境中支持多维资源数据描述的高效结构化资源路由算法.而且,目前部分基于CAN(content-addressable network)网络的改进算法也可以在FAN网络中适用,并获得更好的路由效率和更低的维护代价.     

The Flexible Hypercube: A New Fault-Tolerant Architecture for Parallel Computing

This paper presents the new Flexible Hypercube architecture. The Flexible Hypercube is a fault-tolerant network topology that can be constructed for an arbitrary number of nodes and is incrementally expandable. This topology maintains the strong features of the Hypercube while overcoming deficiencies in expandability. It is shown to have strong node connectivity, a small diameter, and to be tolerant of faults. The Flexible Hypercube is a suitable architecture for the design of both tightly coupled parallel systems and distributed systems. Efficient fault-free and fault-tolerant algorithms for message routing and broadcasting are presented for the architecture. The fault-free algorithm guarantees successful routing inO(logN) time, whereNis the number of nodes in the system, and the fault-tolerant algorithm guarantees routing to functioning nodes if a route exists. The fault-free and fault-tolerant broadcasting algorithms have time complexityO(logN), and the fault-tolerant algorithm guarantees success if no two faulty nodes are adjacent and no functioning node is adjacent to two faults.     

A delay optimal coterie on the k-dimensional folded Petersen graph

Coteries are an effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important metric to measure the performance of a coterie. The topology of the interconnection network in a distributed system also has an impact on its performance. The k-dimensional folded Petersen graph, a graph with 10^k nodes and diameter 2k, qualifies as a good network topology for large distributed systems. In this paper, we present a delay optimal coterie on the k-dimensional folded Petersen graph, FP_k. For any positive integer k, the coterie has message complexity 4^k and delay k. Moreover, this coterie is not vote-assignable.     

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-al     

The hierarchical Petersen network: a new interconnection network with fixed degree

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph.     

Optical transpose k-ary n-cube networks

This paper derives a number of results related to the topological properties of OTIS k-ary n-cube interconnection networks. The basic topological metrics of size, degree, shortest distance, and diameter are obtained. Then results related to embedding in OTIS k-ary n-cubes of OTIS k-ary (n−1)-cubes, cycles, meshes, cubes, and spanning trees are derived. The OTIS k-ary n-cube is shown to be Hamiltonian. Minimal one-to-one routing and optimal broadcasting algorithms are proposed. The OTIS k-ary n-cube is shown to be maximally fault-tolerant. These results are derived based on known properties of k-ary n-cube networks and general properties of OTIS networks.     

Metacube—a versatile family of interconnection networks for extremely large-scale supercomputers

In the next decade, the high-performance supercomputers will consist of several millions of CPUs. The interconnection networks in such supercomputers play an important role for achieving high performance. In this paper, we introduce the Metacube (MC), a versatile family of interconnection network that can connect an extremely large number of nodes with a small number of links per node and keep the diameter rather low. An MC network has a 2-level hypercube structure. An MC(k,m) network can connect 2^2km+k2^{2^{k}m+k} nodes with m+k links per node, where k is the dimension of the high-level hypercubes (classes) and m is the dimension of the low-level hypercubes (clusters). An MC is a symmetric network with short diameter, easy and efficient routing and broadcasting similar to that of the hypercube. However, the MC network can connect millions of nodes with up to 6 links per node. An MC(2,3) with 5 links per node has 16,384 nodes and an MC(3,3) with 6 links per node has 134,217,728 nodes. We describe the MC network’s structure, topological properties, routing and broadcasting algorithms, and the Hamiltonian cycle embedding in the Metacube networks.     

超立方体双环互连网络及路由算法*

给出了一种可扩展的互连网络拓扑结构,称为超立方体双环。该互连网络拓扑结构结合了超立方体拓扑的短直径、高连通性、对称性、路由简单和一种新的双环拓扑结构的可扩展性和常数节点度的优点,使得网络规模增大时,网络节点度可以保持常数;网络节点采用格雷编码和约翰逊编码的混合编码方法,网络的任意相邻节点编码有且仅有一位不同,使得路由算法设计简单。最后分别设计了基于混合编码的单播、广播路由算法。分析表明提出的互连网络具有较好的拓扑性质和通信性能。