容错路由

摘要： BCube是具有良好性能的数据中心网络.相比传统的树形数据中心网络,BCube在扩展和容错性能方面都表现出很大的优势.目前,对于BCube的研究可以归结为对其逻辑图BCn,k(广义超立方体的一种特例)的研究,其中交换机被视为透明设备.在实际应用中,随着网络规模的不断增加,顶点发生故障已经成为一种常态.因此,研究网络的容错路由很有意义.目前,有不少关于BCn,k容错路由的研究,但其2-限制连通度下的容错路由目前还没有被研究.在提出容错路由算法之前,首先证明了BCn,k的2-限制连通度为3(k+1)(n-1)-2n,其中k≥3且n≥3.然后在此基础上提出了一个时间复杂度为O(κ(BCn,k)3)的容错路由算法,其中κ(BCn,k)=(k+1)(n-1)是BCn,k的连通度.该算法可以在故障顶点个数小于3(k+1)(n-1)-2n且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径.

摘要： 提出一种2D-Mesh上不使用虚拟通道的容错路由算法.目前,同类算法要牺牲掉网络边缘的所有节点,还要把所有错误都包含到一个错误块中.所提算法虽然也将错误包含到错误块中,但是不会牺牲掉网络边缘的所有节点,而是在错误处形成一个矩形区域,使包在路由时可以发现并绕开它.该算法不使用虚拟通道,能容一个甚至更多错误,允许错误发生在任何位置,不仅不会降低网络性能,而且还能获得与其他算法相似的传输延迟.

摘要： 由于TSV通道具有高硬件代价和低可靠性的缺点,限制TSV通道数量的非全互连3D NoC得到广泛研究.在非全互连3D NoC中,路由器需要维护TSV表以助数据包在层间传输时找到可用的TSV通道.现有研究的TSV表存储了整个层面内的TSV通道,具有高硬件开销、高重构代价的缺点.因此,提出新的TSV表存储策略,仅需存储距离路由4个端口最近的TSV位置和距离.同时考虑到由于TSV分布的非均匀性,数据包在传输过程中可能在TSV附近的路由造成拥塞,文中提出了基于新TSV表的具有拥塞感知的容错路由算法.实验结果表明,在高注入率条件下该算法比Elevator-First算法具有更好的网络传输性能,且在故障率达到50％时仍能保证75％的数据包接收率.%Because of the cost and reliability issues of TSV,the vertically partially connected 3D NoC with the limit number of TSVs has been researched widely.Router should maintain TSV table which helps packet to find TSV in vertically partially connected 3D NoC.The current TSV table saves TSVs of the whole layer but the cost of hardware and reconfiguration is relatively high.So this paper proposes a new TSV table that only records 4 TSVs which have the smallest distance to each port of router.Due to the fact that the distribution of TSV is heterogeneous,the congestion may occur in the router around TSVs.So this paper also proposes a fault-tolerant routing algorithm with congestion-awareness based on the new TSV table.The experimental results show that the performance of this algorithm is better than Elevator-First algorithm under the high packet injection rate.Additionally,this algorithm can provide 75％ packet reception when the fault rate is 50％.

摘要： Network is vulnerable when failures happen due to its heterogeneity, mobility and instability, at the same time reliability and user QoS(quality of service)cannot be guaranteed. Therefore fault tolerance needs to be improved to guarantee the reliability of QoS routing. For this purpose, an intelligent fault-tolerant QoS routing mechanism was proposed based on PSO( particle swarm optimization)and SA(simulated annealing). Considering the network dynamics, network model was quantitatively described by introducing knowledge of fuzzy mathematics and probability theory. The SRLG( shared risk link group) disjoint and preventive shared-path protective strategy were adopted to find backup path, which optimized end-to-end reliability, cost and QoS parameters. Simulation results indicate that the proposed mechanism has good performance on the percentage of route validity, fault-restoring ratio and resource utilization and thus is feasible and effective.%由于网络的异构性、移动性和不稳定性等特点导致网络在发生故障时连接的可靠性变差,不能满足用户服务质量(quality of service,QoS)需求,因此网络需要具有保证QoS的容错路由能力.为此提出基于粒子群优化(particle swarm optimization,PSO)和模拟退火(simulated annealing,SA)混合优化的容错QoS路由机制.考虑到网络环境的动态性,引入模糊数学和概率论定量刻画网络模型,采用共享风险链路组(shared risk link group,SRLG)分离和共享通路的预防式保护策略建立备份路径,使其端到端可靠性、代价和路径QoS评价值达到最优.仿真结果表明,所提出的容错路由机制具有良好的路由有效性、故障恢复率和资源利用率,是可行和有效的.

摘要： In order to solve the problem of high packet delay and congestion around the faulty region of the traditional fault-tolerant routing algorithms in networks-on-chip,this paper presented a fault-tolerant routing method using two virtual channels. The method determined the prohibited and permitted turns on each virtual channel in such a way that prohibited turns in one virtual channel were permitted in the other one.When a link failure occured,the proposed method based on a new fault infor-mation dissemination mechanism made the packet transmission on the shortest path.In addition,the method was extended to support multiple faulty links by fully utilizing all allowable turns in the network.Finally,the simulation also verifies the effec-tively of the proposed method.%针对片上网络中传统的容错路由算法的高报文延时和故障区域拥塞等不足，利用两个虚拟信道提出一种新的容错路由方法。该方法通过确定每个虚拟信道哪些转向被允许和禁止，使得一个虚拟信道中被禁止的转向在另一信道被允许。当发生链路故障时，该方法基于一种新的故障信息传播机制使报文在最短路径上传输；通过充分利用网络中的所有被允许转向对该方法进行扩展，以支持多链路故障。最后的仿真实验也验证了该方法的有效性。

摘要： 为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法.该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up*/down*算法确定路由路径.此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁.在6×6Mesh网络中,RFTR算法能减少25％的路由表资源用量.仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up*/down*算法和segment算法相当甚至更优的性能.

摘要： An optimized fault routing algorithm is supposed for Network on Chip Based on Built In Self Test by judg-ing information about the fault node. A judgment node and a turning node are set up for decreasing the payload in the reconfigurable loop routing according to the position of the fault node,we made payload balanced while completed fault optimization. We got the delay and throughput data for 2 kinds of 2D-mesh NoC by means of OPNET simulation plat-form, the Experiment’ s results show the advantage of the supposed algorithm, and more optimized network perfor-mance can be achieved in the 7×7 than 5×5 network.%基于内建自测技术，通过判断故障节点信息，提出了一种片上网络可重构容错路由优化算法。算法根据故障节点的位置在网络中设立判断点和有效转向点，以减少在重构环路上的负载，在完成路由容错优化的同时实现了负载均衡。在OPNET仿真平台上，采用均匀流量模式，对比了该算法与RRA算法在两种2D-mesh网络中的性能，实验结果表明，提出算法在平均时延和吞吐率方面具有显著优势，并且与5×5网络相比，7×7规模的NoC中随着网络注入率的增加延时优化愈加明显。

摘要： 随着集成电路制造工艺的不断发展,集成在芯片上晶体管的数量也随之增多,已超过几十亿晶体管的规模,因此芯片上可以集成越来越多的IP核.随着芯片中IP核数量的增多,基于总线结构的片上系统(System-on-Chip,SoC)已不能满足数据的通信要求,为了解决这个问题,片上网络(Network-on-Chip,NoC)作为一种全新的互联结构被提出来.其核心是把网络设计的思想移植到芯片设计中,将片上资源互连起来,并将计算与通信分离.片上网络具有很好的空间可扩展性,采用的全局异步一局部同步的通信机制使并行通信效率更高.NOC带来了一种全新的片上通信方式,它的引入有利于提升可重用设计、解决通信瓶颈和全局同步等难题.本文在研究片上网络结构的基础上,针对片上网络多播通信的特点提出了一种多播容错路由算法.

摘要： MANET routing is critical and routing decision should be made sooner before the node leaves the network.Fast decisions always compensate network performance.In addition,most MANET routing protocols assume a friendly and cooperative environment,and hence are vulnerable to various attacks.Trust and Reputation would serve as a major solution to these problems.Learning the network characteristics and choosing right routing decisions at right times would be a significant solution.In this work,we have done an extensive survey of fault tolerant protocols and ant colony algorithms applied to routing in MANETs.We propose a QoS constrained fault tolerant ant lookahead routing algorithm which attempts to identify valid route and look-ahead route pairs which might help in choosing the alternate path in case of valid route failure.The results prove that the proposed algorithm takes better routing decisions with 20-30 percent improvement compared with existing ant colony algorithms.

摘要： 为了提高片上网络(Network-on-Chip,NoC)系统的可靠性及故障情况下的网络性能,基于转弯模型(Turn Model)的思想对现有的XY路由算法进行了改进,提出了一种容错路径短,且在故障情况下具有信息均衡能力的无虚通道容错路由算法(T-XY路由算法).OPNET仿真结果表明,该算法与同类算法相比具有较好的吞吐及时延性能.

摘要： 随着VLSI技术的发展，对集成电路可靠性的保证越来越受重视，容错技术已经成为SOC集成和多核结构的重要部分．rn 另一方面，NOC近年来以其高带宽和吞吐量等特点逐渐成为片上通信的标准结构．由于网络规模的增大，NOC发生故障的概率也相应增加，NoC的容错也逐渐成为NoC设计的重要组成部分．本文基于NoC通信网络的功能故障模型提出了一种自适应容错路由算法FFBR，着重讨论了功能故障模型和该容错路由算法流程，最后给出了该算法的吞吐量和时延等参数的仿真结果．

摘要： Peer-to-Peer(2P)技术是近年来兴起的一种新型网络计算技术，具有广阔的应用前景。FissionE是首个基于Kautz图的结构化P2P覆盖网，在给定节点度数(d=2)下具有最优的网络直径。针对恶劣环境下结点失效导致的FissionE路由性能较差的问题，本文对FissionE的容错路由算法进行研究，其基本思想是：如果下一跳结点失效或网络连接失效，那么将采用某种方法“绕过”失效的结点或连接，从而在恶劣环境下获得较好的路由性能。

摘要： 本文讨论了广义超立方体网络的容错路由问题.证明了当无效点很多时,只要存在某个(n-1)-维广立方体中无效节点不超过两个,则该n-维广义超立方体中的任意两个有效节点x到y之间可以找到长度不超过O(x,y)+4的有效路由,这里O(x,y)表示x到y的最优距离.

摘要： 当系统包含足够多的故障点时,mesh/torus网整个系统很有可能是不安全的.本文采用扩展的局部安全性信息来指导3维mesh/torus网的容错路由.扩展的局部安全性信息在每个平面内部对无故障节点分类,所以系统中的故障块也是在不同的平面上构成的,而不是基于整个系统.很多基于整个系统不安全的节点在2维的平面中都会变成安全的节点.不管是在安全的系统内,甚或不安全的系统内,扩展的局部安全性信息都能有效地指导容错路由.应该注意到,我们的方法不会将任何无故障节点设置为无效节点,而在以往的方法中并不是这样.所有的故障块都是在平面内构成的,而不是基于整个系统;在一个平面内,任何包含在故障块里的无故障节点仍然可作为出发点或者目标点,这样将大大提高系统的计算能力和性能.模拟结果表明本文方法优于已有的方法.

摘要： 该文研究了蛀洞网络的容错路由问题，提出了一种新的重新路由算法，与已知算法不同的是，该算法不需要虚拟信道，适用于任何网络拓扑结构和任意确定的路由策略，只要保证网络连通，也可适用于任意数目的故障信道，模拟结果表明，与现有方法相比，该文提出的方法在网络结构下具有更好或类似的性能。

摘要： 该文针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵（ＯＰＭｓ－ＯｐｔｉｍａｌＰａｔｈＭａｔｒｉｃｅｓ）的概念。存储于超立方体各节点中的最优通路矩阵记录系统中的故障信息，用于判定该节点与消息的目的节点之间是否存在最优通路（长度等于两节点间海明距离的通路）。然后给出了一个简单的基于最优通路矩阵的路由算法。利用该算法所选的通路的长度不超过两点间的海明距离加２。对于ｍ维超立方体，每个节点所需的存储开销为ｎ〈’２〉个字。

摘要： 为了满足系统对通信带宽的要求，片上网络逐渐取代总线成为当前多核及众核系统的主流互连方案．然而，由于芯片特征尺寸的不断减小，芯片内发生故障的概率显著增加．为了提供可靠的片上通信，本文提出了一种低成本的可重构路由算法．rn 通过时路由器状态的更新，本文提出的片上网络系统可以容忍任意数目，任意分布的路由器以及链路故障．与目前存在的容错设计方案不同之处在于，本文提出的可重构路由器不需要增加虚拟通道来保证网络的无死锁特性。因此，其具有低成本、高可靠的特性．通过大量的分析和实验证实，本文提出的方案特别适用于处理器与缓存，或缓存与缓存之间等低负载的片上通信．

摘要： 为了满足系统对通信带宽的要求，片上网络逐渐取代总线成为当前多核及众核系统的主流互连方案．然而，由于芯片特征尺寸的不断减小，芯片内发生故障的概率显著增加．为了提供可靠的片上通信，本文提出了一种低成本的可重构路由算法．rn 通过时路由器状态的更新，本文提出的片上网络系统可以容忍任意数目，任意分布的路由器以及链路故障．与目前存在的容错设计方案不同之处在于，本文提出的可重构路由器不需要增加虚拟通道来保证网络的无死锁特性。因此，其具有低成本、高可靠的特性．通过大量的分析和实验证实，本文提出的方案特别适用于处理器与缓存，或缓存与缓存之间等低负载的片上通信．

摘要： 为了满足系统对通信带宽的要求，片上网络逐渐取代总线成为当前多核及众核系统的主流互连方案．然而，由于芯片特征尺寸的不断减小，芯片内发生故障的概率显著增加．为了提供可靠的片上通信，本文提出了一种低成本的可重构路由算法．rn 通过时路由器状态的更新，本文提出的片上网络系统可以容忍任意数目，任意分布的路由器以及链路故障．与目前存在的容错设计方案不同之处在于，本文提出的可重构路由器不需要增加虚拟通道来保证网络的无死锁特性。因此，其具有低成本、高可靠的特性．通过大量的分析和实验证实，本文提出的方案特别适用于处理器与缓存，或缓存与缓存之间等低负载的片上通信．

摘要： 为了满足系统对通信带宽的要求，片上网络逐渐取代总线成为当前多核及众核系统的主流互连方案．然而，由于芯片特征尺寸的不断减小，芯片内发生故障的概率显著增加．为了提供可靠的片上通信，本文提出了一种低成本的可重构路由算法．rn 通过时路由器状态的更新，本文提出的片上网络系统可以容忍任意数目，任意分布的路由器以及链路故障．与目前存在的容错设计方案不同之处在于，本文提出的可重构路由器不需要增加虚拟通道来保证网络的无死锁特性。因此，其具有低成本、高可靠的特性．通过大量的分析和实验证实，本文提出的方案特别适用于处理器与缓存，或缓存与缓存之间等低负载的片上通信．

摘要： 本发明公开了一种应用于多级功能节点冗余容错的路由装置和冗余容错系统，路由装置包括分别与搜索模块相连接的接收模块、第一存储模块、发送模块；所述接收模块用于接收外部的数据包，并将所述数据包传送给所述搜索模块；所述第一存储模块，用于存储预设置目标地址；所述搜索模块，用于根据所述数据包，搜索所述第一存储模块中各预设置目标地址，当所述数据目标地址与所述预设置目标地址一致时，发送执行代码数据给所述发送模块；所述发送模块按照所述执行代码数据，发送所述数据包给外部的各级功能节点；冗余容错系统包括若干级的功能节点及其控制装置，以及所述的路由装置。本发明结构简单、成本较低，应用较广。

摘要： 本发明公开一种针对路由方向单调变化网络的容错曼哈顿路由方法，包括步骤：判断源节点和目标节点是否为错误节点，若至少有一个为错误节点则结束流程；判断每一个中间节点的被最小路由策略允许的下一跳节点，并记录每一个中间节点的被最小路由策略允许的上一跳节点；将源节点的路径计数值设为非0，并计算中间节点和目标节点的路径计数值；判断目标节点的路径计数值是否为0，若为0则结束流程；将目标节点作为起点，开始逐跳查找路径计数值不为0且被最小路由策略允许的上一跳节点直至查找到源节点，得到容错曼哈顿路径。本发明复杂度低、普适性高且不牺牲可用容错曼哈顿路径。

摘要： 本发明公开了一种数据中心网络容错单播路由系统，数据中心网络基于n口交换机，有k个维度,网络中每台服务器与n‑1台服务器通过交换机相连接，与q台服务器直接相连接,当数据中心网络中存在不超过n+q‑2个服务器出现故障时，本发明实现了任意两个无故障服务器能够进行可靠单播通信。

摘要： 本发明公开了一种应用于多级功能节点冗余容错的路由装置和冗余容错系统，路由装置包括分别与搜索模块相连接的接收模块、第一存储模块、发送模块；所述接收模块用于接收外部的数据包，并将所述数据包传送给所述搜索模块；所述第一存储模块，用于存储预设置目标地址；所述搜索模块，用于根据所述数据包，搜索所述第一存储模块中各预设置目标地址，当所述数据目标地址与所述预设置目标地址一致时，发送执行代码数据给所述发送模块；所述发送模块按照所述执行代码数据，发送所述数据包给外部的各级功能节点；冗余容错系统包括若干级的功能节点及其控制装置，以及所述的路由装置。本发明结构简单、成本较低，应用较广。

摘要： 本申请实施例提供的高容错性路由物联的消防传感节点网络，包括：至少一个传感节点、至少一个物联网基站和后台服务器；所述传感节点分布在智能建筑内，用于采集对应类型的火情数据，并生成数据包，通过所述物联网基站将生成的数据包发送至所述后台服务器，或者，与临近节点建立点对点的直接通信连接，将生成的数据包发送至临近节点，由临近节点直接发送至所述物联网基站或者通过一跳或者多跳的节点中继转发至所述物联网基站；所述物联网基站用于建立与所述传感节点的通信连接，接收所述传感节点发送的数据包，并将接收到的数据包发送至所述后台服务器。本申请实施例的消防传感节点网络，能够在传输路径中断时，迅速建立新路径以恢复数据包传输。

摘要： 本发明公开一种针对路由方向单调变化网络的容错曼哈顿路由方法，包括步骤：判断源节点和目标节点是否为错误节点，若至少有一个为错误节点则结束流程；判断每一个中间节点的被最小路由策略允许的下一跳节点，并记录每一个中间节点的被最小路由策略允许的上一跳节点；将源节点的路径计数值设为非0，并计算中间节点和目标节点的路径计数值；判断目标节点的路径计数值是否为0，若为0则结束流程；将目标节点作为起点，开始逐跳查找路径计数值不为0且被最小路由策略允许的上一跳节点直至查找到源节点，得到容错曼哈顿路径。本发明复杂度低、普适性高且不牺牲可用容错曼哈顿路径。

摘要： 本发明公开了一种基于虚拟链路的边缘容错路由方法和装置，该方法利用贪心转发策略，构建一个全部边缘节点构成的结构化虚拟链路网络，由物理链路和虚拟链路链接，每个边缘节点存储着构建该网络的路由表；当源节点需要向目标节点转发数据包时，源节点在数据包上添加目标节点的标识符，根据路由表中的路由表项，贪心地选择在标识符空间内距离目标节点最近的节点作为下一跳目标，并通过构建的网络转发数据包，直至到达目标节点；面临节点宕机或链路断路时，通过回溯策略和贪心转发策略旁路绕过。本发明具有路由延伸性好，容错性高的特点，能够适应大规模的边缘节点，保证了边缘节点在可靠性差、且常发生节点扰动的情况下，仍能完成路由任务。

摘要： 本申请涉及一种用于延迟容忍网络的容错路由方法、装置和系统。所述方法包括：接收延迟容忍网络中第二节点发送的第二节点的缓存状态、空间地理位置以及数据生成特征中的至少一个，根据缓存状态、空间地理位置以及数据生成特征中的至少一个，根据预先设置的优化目标，生成无节点中断状态和任意节点中断状态对应的拓扑和路由信息，将拓扑和路由信息发送至第二节点，以使第二节点根据无节点中断状态时拓扑和路由信息进行传输路径选择及数据传输，以及第二节点检测网络异常时，根据节点中断状态对应的拓扑和路由信息进行传输路径选择及数据传输。采用本方法能够提高延迟容忍网络的鲁棒性。

摘要： 本发明属于电力边缘计算和片上网络领域，公开了一种基于区域生长树的片上网络容错路由方法，包括如下步骤：步骤一、给出节点的定义；步骤二、定义当前数据包存在两种模式，分别为普通模式和树模式；步骤三、判断当前数据包的路由模式；步骤四、根据当前数据包的模式，即所在节点，进行不同的操作和使用路由算法。本发明通过广度优先搜索（Breadth‑First‑Search，BFS）重新激活故障块中经失效的一些节点，提高了故障覆盖率。

摘要： 本发明公开了一种基于虚拟链路的边缘容错路由方法和装置，该方法利用贪心转发策略，构建一个全部边缘节点构成的结构化虚拟链路网络，由物理链路和虚拟链路链接，每个边缘节点存储着构建该网络的路由表；当源节点需要向目标节点转发数据包时，源节点在数据包上添加目标节点的标识符，根据路由表中的路由表项，贪心地选择在标识符空间内距离目标节点最近的节点作为下一跳目标，并通过构建的网络转发数据包，直至到达目标节点；面临节点宕机或链路断路时，通过回溯策略和贪心转发策略旁路绕过。本发明具有路由延伸性好，容错性高的特点，能够适应大规模的边缘节点，保证了边缘节点在可靠性差、且常发生节点扰动的情况下，仍能完成路由任务。