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

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

基于故障节点再利用的细粒度NoC容错路由算法

针对传统NoC容错算法中容错粒度过粗造成资源浪费的问题,提出了一种细粒度的自适应容错路由算法,对带有部分故障的节点重新利用。算法将各种故障映射为一种功能故障模型,结合新提出的路由端口优先级策略和嵌入的奇偶转向模型,实现数据包的无死锁容错路由。实验表明,随着负载和故障数目的增加,该算法具有更优越的容错性能,证明了算法的有效性。     

蜂窝网络单点容错路由协议研究

容错路由是目前分布式系统热门的研究课题之一，然而目前大多数容错路由的相关研究，如Mesh、Hypercubes等，大都以mesh架构为主要环境。本论文提出了一个可在蜂窝网络架构上容忍一个错误节点的容错路由算法。若最短路径发生一个节点错误时。仍可以利用该算法找到一条近似最佳路径，它是利用在蜂窝网络的：起始点S与终点D两点坐标找出最短路径R，并将此路径以正规表示式表示，然后当发现路径中有节点故障时，则利用算法的caba=ba替换规则，绕过此错误节点。这就是本文在Honeycomb架构下提出的容错路由算法。     

基于k-Petersen图的超节点网络容错机制*

针对已有容错机制动态维护复杂、带宽消耗大的问题,提出一种新的容错机制。首先,利用改进后的k-Petersen图,构建了超节点层拓扑结构,使网络具有高容错的特性;同时, 给出超节点选择和超节点负载均衡方法,减少了超节点因负载过重而失效的情况;另外,给出超节点失效恢复算法和容错路由算法,解决了网络中失效超节点的恢复问题和网络路由问题。理论分析和实验结果显示,该网络具有易维护、高容错的特点。     

PRDT（2，1）架构的NoC系统容错路由算法

链路和节点的故障会导致网络中许多节点无法相互通讯,因此容错性是NoC系统设计中的一个重要问题。基于一种新的NoC网络拓扑结构PRDT（2,1）,提出一种PRDT（2,1）容错路由算法以及相应的节点失效算法。节点失效算法通过使较少数量的无故障节点失效来构造矩形故障区域,PRDT（2,1）容错路由算法仅使用了最小数量的虚拟通道并提供足够的自适应性以实现无死锁容错路由。只要故障区域没有断开网络,这一算法能够保证路由的连通性。算法在不同故障率的PRDT（2,1）网络中仿真,结果显示这一算法具有良好的平滑降级使用特性。     

基于局部扭曲立方体的单播容错路由算法

对n维局部扭曲立方体存在节点故障时,提出了一种基于节点安全级概念的单播容错路由算法。该算法除了考虑邻接节点的安全状况外,还充分利用了局部扭曲立方体自身特有的结构,使得信息尽可能沿最优路径传递。通过模拟仿真实验可知,算法具有较高的容错能力。当故障节点的数目达到或超过一半时,算法仍能保持一个相当高的容错路由成功率,且算法所选路径在多数情况下是最优路径。     

局部扭曲立方体单播容错路由算法

在n维局部扭曲立方体存在节点故障的情况下,基于路由能力的概念提出了一种单播容错路由算法,该算法首先寻找最短路径上满足路由能力值要求的邻接节点,其次寻找非最短路径上满足路由能力值要求的邻接节点。这样求得的容错路径首先是最优路径,其次为次优路径。     

煤矿智能感知网络中基于后备节点集合的节能容错路由

节点能量效率和路由容错性是煤矿智能感知网络重要的两方面,目前的煤矿感知路由并没有兼顾两者,提出一种分布式的基于后备节点集合的节能容错路由(ECFTR),为每个簇头节点构造后备节点集合,计算转发代价来确定下一跳簇头节点,在当前簇头节点失效时利用后备集合节点恢复到基站的路由。对ECFTR算法的性能分析和仿真比较说明,相比同类算法,ECFTR算法在节省能量、延长网络生存期以及路由的稳定性、容错性方面有明显优势,网络生存期分别比其他三种同类算法提高了100%、46%和20%,基站平均接收的数据包数分别增加了37%、35%、33%。模拟井下实验进一步验证了ECFTR的有效性和抗干扰性。     

一种高效的超节点网络容错机制

超节点网络采用超节点作为普通节点服务器,负责管理和查询处理的机制,提高了搜索效率。但是,如果超节点失效,将会严重影响网络的稳定性和查询效率。提出一种高效的容错机制。首先,改进了无向双环结构,提出k-无向双环拓扑结构,并利用此技术,构建了超节点层拓扑结构,使网络具有高容错特性;同时在此基础上,给出了超节点选择和超节点负载均衡的方法,降低了超节点因负载过重而失效的可能性,另外,给出了超节点失效恢复算法和容错路由算法,解决了超节点失效后的恢复和路由问题。实验结果显示,该网络具有易维护、高容错的特点。     

故障超立方体网络中的路由算法

针对超立方体结构的多处理机系统中存在故障的情况,提出了一个应用于超立方体网络的容错路由算法。该容错路由算法是基于局部信息的,只需要知道邻节点的状态,而无需知道整个网络的运行情况。对于给定的源节点和目的节点,路由算法均能够找到一条最优通路,并且可以预防死锁。模拟实验结果表明,路由算法所构造的路径长度接近于两个节点之间的最优路径长度。     

一种无虚通道NoC负载均衡容错路由算法

随着芯片复杂度的不断增大,设计一个高效的片上网络容错路由算法面临着巨大的挑战。由于芯片面积开销的限制,拥有低面积开销的无虚通道片上网络路由器受到学术界的广泛关注。但目前对无虚通道片上网络容错路由算法的研究却停留在容错性能上,而忽略了容错路由算法的路由路径过于单一所造成的负载不均、数据包平均延迟较大等问题。文章在借鉴已有的奇偶转向容错路由算法的基础上,对算法的故障模型和故障绕行策略进行优化,并在算法中融入负载均衡策略,以形成新的容错算法缓解上述问题。在9x9的2D mesh网络中对新提出的算法和参考算法的仿真结果表明：与参考算法相比,新算法在降低数据延迟和吞吐量方面有着明显的优势,在最优情况下能减少8.92%数据延迟和增加10.46%的吞吐量。     

Bio-inspired self-aware fault-tolerant routing protocol for network-on-chip architectures using Particle Swarm Optimization

This research paper proposes a bio-inspired self-aware fault-tolerant routing protocol for network-on-chip architecture using particle swarm optimization (PSO), which considers synchronous, asynchronous, and self-organizing communication mechanisms to intelligently load-balance the traffic on the entire network in the presence of faulty components. By way of experimentation and simulation, this study demonstrates that the proposed scheme can converge to a global optimum, minimal routing path in real time, in the presence of network congestion and faulty routers and links. The basic PSO algorithm was improved to implement the proposed routing scheme, named bio-inspired self-aware fault-tolerant routing protocol (BISFTRP). This scheme uses the synchronous, asynchronous, and self-organizing features of PSO to create a global routing table and intelligent adaptation, which gives rise to scalable, real-time, and dynamic routing decisions with high throughput, low latency, and minimum power consumption. A cycle-accurate simulation system to demonstrate the flexibility and efficiency of the proposed scheme is used. Comparison results with state-of-the-art fault-tolerant routing algorithms show that the BISFTRP routing protocol achieves high routing performance without routing oscillations and throughput degradation. Furthermore, the hardware implementation results show that the BISFTRP router achieves an efficient area and power utilization, compared with state-of-the-art routers.     

Performance analysis of fault-tolerant routing algorithm in wormhole-switched interconnections

With nowadays popularity of large-scale parallel computers, Multiprocessors System-on-Chip (MP-SoCs), multicomputers, cluster computers and peer-to-peer communication networks, fault-tolerant routing becomes an important issue in developing these systems. Fault-tolerant routing algorithms in such systems aim at providing continuous operations in the presence of one or more failures by allowing the graceful degradation of system. The Software-Based fault-tolerant routing scheme has been suggested as an efficient routing algorithm to preserve both communication performance and fault-tolerant demands in parallel computer systems. To study network performance, a number of different analytical models for fault-free routing algorithms have been proposed in the past literature. However, there has not been reported any similar analytical model of fault-tolerant routing in the presence of faulty components. This paper presents a new analytical modeling approach for determining the effects of failures in wormhole-switched 2-D tori using the fault-tolerant Software-Based scheme. More specifically, we describe a general model to derive mathematical expressions to investigate the performance behavior of routing algorithms confronting convex (|-shaped, □-shaped) or concave (U-shaped, +-shaped, T-shaped, H-shaped) faulty regions. The model is validated through comprehensive simulation experiments for different types of failures.

Fault-Tolerant Wormhole Routing with 2 Virtual Channels in Meshes

In wormhole meshes, a reliable routing is supposed to be deadlock-free and fault-tolerant. Many routing algorithms are able to tolerate a large number of faults enclosed by rectangular blocks or special convex, none of them, however, is capable of handling two convex fault regions with distance two by using only two virtual networks. In this paper, a fault-tolerant wormhole routing algorithm is presented to tolerate the disjointed convex faulty regions with distance two or no less, which do not contain any nonfaulty nodes and do not prohibit any routing as long as nodes outside faulty regions are connected in the mesh network. The processors＇ overlapping along the boundaries of different fault regions is allowed. The proposed algorithm, which routes the messages by X-Y routing algorithm in fault-free region, can tolerate convex fault-connected regions with only two virtual channels per physical channel, and is deadlock- and livelock-free. The proposed algorithm can be easily extended to adaptive routing.     

A testbed for evaluation of fault-tolerant routing inmultiprocessor interconnection networks

This paper presents a comprehensive evaluation testbed for interconnection networks and routing algorithms using real applications. The testbed is flexible enough to implement any network topology and fault-tolerant routing algorithm, and allows the system architect to study the cost versus performance trade-offs for a range of network parameters. We illustrate its use with one fault-tolerant algorithm and analyze the performance of four shared memory applications with different fault conditions. We also show how the testbed can be used to drive future research in fault-tolerant routing algorithms and architectures by proposing and evaluating novel architectural enhancements to the network router, called path selection heuristics (PSH). We propose three such schemes and the Least Recently Used (LRU) PSH is shown to give the best performance in the presence of faults     

耐故障Clos网及其路由算法

提出了一种新的耐故障Clos网,通过在基础Clos网各段中增加冗余的交换单元,使其能够在发生少量故障的情况下正常工作,从而提供更可靠的服务。针对耐故障Clos网,给出一种耐故障Clos路由算法,该算法采用最小分布优先的策略逐列计算Clos网连接说明矩阵,通过重排完全实现无阻塞路由,该算法的时间复杂度在最坏情况下仅为O(N3/2)。该耐故障Clos网及其算法设计可以用于实现更为可靠的Clos网络。     

基于报文检测的快速自适应NoC容错路由算法

传统的自适应片上网络(NoC)容错路由算法采用一步一比较的方式来确定最优端口, 未能有效降低传输延迟。根据数据包在2D Mesh NoC前若干连续的跳数内最优端口固定的特点, 提出了一种基于报文检测的快速(FPIB)自适应容错路由算法。算法采用跳步比较的方式来减少数据包的路由时间, 并使用模糊优先级策略来进行容错路由计算。实验结果表明, 与uLBDR容错路由算法相比, 该算法能有效地降低平均延迟, 且实现算法的硬件开销更低。     

一种适用于2D Mesh片上网络的可重构容错路由算法

适用于2D Mesh片上网络的可重构容错路由算法,在芯片某些区域由于制造缺陷、使用老化等原因拓扑结构变得不再规整的时候,可以对网络节点重新进行配置,从而保证健康节点间的正常通信.基于SystemC的平台仿真表明该算法相对于传统算法可以获得更佳的网络性能.该算法是免于死锁的,同时对其可重构机制也给出了详细的论述.它还具有良好的扩展性,当系统规模增大的时候每个路由器的硬件开销保持恒定,而其容错能力也得到了增强.     

Routing in wormhole-switched clustered networks with applicationsto fault tolerance

This paper presents a novel technique for routing in wormhole-switched multiprocessor interconnection networks with clustered configuration. The network model used here consists of a set of clusters interfaced through a common central network. We assume that the central network and the clusters use independent algorithms to route messages between their internal nodes. A technique for deriving a global routing algorithm based on the local algorithms is presented, which allows the transfer of messages between any pair of nodes in the network. This proposed method is shown to be deadlock-free with two virtual channels. The clustered network model and the proposed routing technique can be used to enhance the fault tolerance capability of existing routing algorithms. In particular, we describe fault-tolerant routing methods for meshes, which can tolerate any arbitrary fault distribution without disabling connected healthy nodes     

一类双环网的特征分析及寻径控制

本文首先提出双环网中任意节点之间的最短路径求取方法，而后针对一类跨度为ｈ（≤Ｌ√」＋１）的双环网进行拓扑分析（Ｎ为网络规模），并构造了一个十分简便的最优寻径算法，最后给出一个容错寻径算法。