交叉立方体网络的无死锁虫洞路由算法

Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.首先证明n(n≥3)维交叉立方体网络不存在无死锁的最短路径路由算法,然后利用虚通道技术将一条物理通道分成三条逻辑通道,并在此基础上提出一种基于虫洞路由的最短路径路由算法,其时间复杂度为O(n).理论证明了算法是无死锁的.     

具有不连通子立方体的超立方体中广播路由

基于扩展的局部k—维子立方体连通的超立方体网络Hn,提出了超立方体网络Hn中新的广播容错路由算法。算法分析表明,基于扩展局部k—维子立方体连通的广播路由算法比基于局部k-子立方连通的广播路由算法提高了超立方体网络的容错性和通用性。     

Mesh网中高效无死锁自适应路由算法

提出了一种新的应用于三维Mesh网中的无死锁路由算法.在当今的商用多计算机系统中,二维和三维的Mesh网是多处理器网络最为常用的拓扑结构之一.在应用于Mesh网的平面自适应路由(Planar Adaptive Routing)算法中,每条物理通道只需三条虚拟通道就可以有效地在三维以及更高维的Mesh网中避免死锁的产生.然而,采用该算法,网络拓扑一维和三维分别有两条和一条虚拟通道始终处于空闲状态.该文所提出的算法针对三维Mesh网,每条物理通道只需两条虚拟通道就可以有效地避免死锁.文中通过充分的模拟数据验证了此算法的有效性.     

具有大量错误结点的超立方体网络中的高效路由算法的设计与讨论

该文提出了容错超立方体网络的一个很自然的机关报概念;局部连通性;讨论了两种类型的局部连通性;大局中部k-维子立方体连通性和局部子立方体连通性;一个局部连通的超立方体网络可容许大量错误结点且能确保超立方体网络是全局连通的;给出了满足局部连通性条件的超立方体网络中的几个高效的容错路由算法,文中的容错路由算法是分布式的和基于局部信息的,因而具有很强的实际意义。     

蜂窝网络上的路由算法*

主要研究蜂窝网络上的无死锁单播路由算法和一对全的广播路由算法。基于蜂窝网络的砖形画法,利用二维网络维序路由的基本思想和两个虚拟网络实现了无死锁的最短单播路由算法,并证明了算法的无死锁性。然后基于这个单播路由算法和线列上的广播算法,用软件实现了蜂窝网络上一对全的广播路由算法,经过简单比较得出该广播算法比以往的算法在通信效率上有了极大的提高。     

具有混合故障广义超立方体中的容错路由

针对广义超立方体网络中的同时具有大量结点和链路故障模式,提出了两类新的局部连通性概念。在这两类局部连通性概念的基础上给出了两个广义超立方体网络的分布式容错路由算法。基于两类新的局部连通性概念的广义超立方体网络容错路由算法与基于局部连通性的广义超立方体网络容错路由容错路由算法相比较,新算法提高了容错能力。     

不规则网络拓扑结构下的多棵树路由算法研究

为了提高不规则网络拓扑结构的路由效率,提出了一种新型路由算法-多棵树路由算法.考虑了原始路由算法的不足,平均了网络中各个通道的利用率,降低路由表的平均路径长度,同时在死锁发生时能够及时有效的进行死锁恢复,解决了先前路由算法中通道负载集中、通道利用率低、路由表平均路径长度过长的问题.通过模拟真实硬件环境的模拟器软件,表明了在不同规模、不同负载下的不规则网络下多棵树路由算法具有更高的效率.     

具有大量错误结点的超立方体网络中的单播路由算法的设计与分析

本文讨论具有大量错误结点的超立方体网络中的单播路由算法，假定Hn是一个局部3－维子立方体连通的n-维超立方体网络并且每一个基本的3－维子立方体中分别最多有1个和2个错误结点，本文提出的单播路由算法能够在线性时间找到路径长度分别为源结点和目的结点之间大约1．5倍和2倍海明距离的次优路径，我们提出的单播路由算法只需要结点知道其邻结点的状态，而无需知道整个网络信息，也就是说，该算法是基于局部信息的，因而该算法具有很强的实际意义。     

故障超立方体网络中的高效容错路由算法研究

对超立方体网络中具有大量节点和链路故障模式进行了研究,提出了两类"子连通性"即k-维子连通性和任意子连通性的概念;基于两类子连通性概念,分别给出了两个满足该两类子连通性条件的超立方体网络的分布式容错路由算法.证明了已有的两类局部连通性概念中的条件"错误节点数小于正确节点数"是不必要的.提出的两个子连通性概念是两类局部连通性概念的最大扩展,可以在更大程度上保证整个超立方体网络的全局连通性,是已有的两类局部连通性概念的一种完全扩展.     

基于超立方体容错路由算法分析*

基于超立方体的优良的拓扑性质,提出了一个应用于超立方体网络的容错路由算法.该容错路由算法是基于局部信息的,因为路由算法在路由过程中,只需要知道其邻节点的信息,而无须知道其他节点的出错情况.对于给定的源节点和目的节点,路由算法均能够找到一条最优容错路径,并且可以预防死锁.模拟实验结果表明,路由算法所构造的路由路径长度接近于两个节点之间的最优路径长度.     

Nearly optimal one-to-many parallel routing in star networks

Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n-1 node-disjoint paths between one node and a set of other n-1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and the running time of our algorithm is bounded by O(n²). More specifically, given a node s and n-1 other nodes {t₁, t₂ , …, t_n-1} in the n-star network, our algorithm constructs n-1 node-disjoint paths P₁, P₂, …, P_n-1, where P_i is a path from s to t_j of length at most dist(s, t_j)+6 and dist(s, t _j) is the distance, i.e., the length of a shortest path, from s to t_j, for i=1, 2, …, n-1.The best bound on the path length by previously known algorithms for the same problem is 5(n-2)≈10Δ_n/3, where Δ_n=max{dist(s, t)} is the diameter of the n-star network     

一个针对洗牌交换网的最优路由算法

洗牌交换网是最流行的互连网之一,然而,它的缺点之一便是最短路由算法,最短路由算法,通常也称为最优路由算法,能保证报文在任意一对结点之间沿着最短路径传送。针对包含2^n个结点的洗牌交换网,文中给出了一个O（n^2)时间复杂度的最短路由算法。该算法还可以很容易地适用于立方体连接圈（CCC）,且所得到的算法比已有的CCC路由算法要简单得多。     

N-立方体消息通信时延的分析

本文利用生灭过程理论,对Ｎ－立方体的消息通信延时建立了一个计算模型,在存在消息堵塞的情况下对Ｎ－立方体采用虫孔寻径机制和ｅ－ｃｕｂｅ算法时的沙息通信延迟进行了分析求解,最后,通过模拟实验,证明了结果的正确性。     

虚网叠加构造自适应路由算法的有效框架

大规模并行处理机系统中路由算法对互联网络通信性能和系统性起着重要作用。     

网络容错路由算法概率分析的一种新的方法

该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。     

On the design of hypermesh interconnection networks for multicomputers

Topology, routing algorithm, and router structure are among the most important factors that greatly influence network performance. This paper assesses the interaction of these elements on two related but distinct types of multicomputer networks, the binary n-cube (or cube) and the hypermesh. The analysis will show that the topological properties of the hypermesh confer an important advantage over the cube that makes the former a promising option for use in high-performance multicomputers. The hypermesh can use simple routing algorithms and cheap routers with little performance penalty. The cube, on the other hand, is constrained to the use of a specific routing algorithm and complex routers to take advantage of its rich connectivity.     

基于Hamming距离的超立方体网络的寻径算法

本文利用Ｈａｍｍｉｎｇ距离概念,提出两种基于Ｈａｍｍｉｎｇ距离的确定性寻径算法－Ｅ１－ｃｕｂｅｒｏｕｔｉｎｇ和Ｅ２－ｃｕｂｅ－ｒｏｕｔｉｎｇ,分析这两种算法的特点,为了克服确定性寻径算法易出现通道拥挤现象,本文综合上述两种算法,提出一种自适应寻径算法－Ｅ３－ｃｕｂｅ ｒｏｕｔｈｉｎｇ。     

The twisted crossed cube

The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQ_n) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQ_n that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQ_n are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQ_n with crossed cube (CQ_n), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQ_n/CQ_n and better properties in other respects, for example, its connection complexity is half of that of TCQ_n/CQ_n when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQ_n/CQ_n. Copyright © 2015 John Wiley & Sons, Ltd.     

交叉立方体网络上的一种双向搜索路由算法

交叉立方体是近年提出的一种互联网络。虽然直径大约是超立方体直径的一半,但由于节点连接方式比超立方体复杂,所以在交叉立方体中利用节点编码研究路由算法比在超立方体中复杂的多。针对交叉立方体互联网络节点编码的特点,在理论分析的基础上采用双向搜索的方法,给出了一个基于交叉立方体节点编码的多项式路由算法,证明了在交叉立方体上采用该算法求得的任意两节点间的路长不超过该交叉立方体的直径。     

A class of multistage conference switching networks for group communication

There is a growing demand for network support for group applications, in which messages from one or more sender(s) are delivered to a large number of receivers. Here, we propose a network architecture for supporting a fundamental type of group communication, conferencing. A conference refers to a group of members in a network who communicate with each other within the group. We consider adopting a class of multistage networks, such as a baseline, an omega, or an indirect binary cube network, composed of switch modules with fan-in and fan-out capability for a conference network which supports multiple disjoint conferences. The key issue in designing a conference network is to determine the multiplicity of routing conflicts, which is the maximum number of conflict parties competing a single interstage link when multiple disjoint conferences simultaneously present in the network. Our results show that, for a network of size n /spl times/ n, the multiplicities of routing conflicts are small constants (between 2 and 4) for an omega network or an indirect binary cube network; while it can be as large as /spl radic/n/q + 1 for a baseline network, where q is the minimum allowable conference size. Thus, our design for conference networks is based on an omega network or an indirect binary cube network. We also develop fast self-routing algorithms for setting up routing paths in the newly designed conference networks. As can be seen, such an n /spl times/ n conference network has O(logn) routing time and communication delay and O(nlogn) hardware cost. The conference networks are superior to existing designs in terms of routing complexity, communication delay and hardware cost. The conference network proposed is rearrangeably nonblocking in general, and is strictly nonblocking under some conference service policy. It can be used in applications that require efficient or real-time group communication.