基于MESH的多路径高效容错路由算法研究

发布时间：2020-06-14 05:33

【摘要】：2D-Mesh网络由于结构简单且易于构造以及较低的维度,并且在处理各种算法时具有较高的性能,在集成电路的制造业中得到了广泛应用。路由算法的负载平衡会影响网络的吞吐量和延迟,吞吐率低和高延迟会导致网络传输性能下降。因此,改善负载平衡对路由算法、包括容错路由算法设计至关重要。一些特定的应用要求网络即使出现少量故障,也要正常工作,因此研究2D-Mesh网络中高效网络吞吐率的容错路由算法具有重要的意义。容错路由算法传统上采用自适应路由策略。自适应路由算法在网络中进行消息传输时,根据网络当前的是否繁忙可以自主选择路径进行传输,虽然有很好的灵活性但是需要判断网络状态并进行路由决策,这增加了网络传输延时,同时也使得路由器结构变得复杂。而随机的Oblivious路由算法中不用考虑当前网络的状态,通过随机的选择在源节点和目的节点之间存在的多条路径进行消息传输。因此,随机的Oblivious路由算法具有很高的灵活性,能达到很好的性能。本文提出了一种新的基于Oblivious容错路由的思想。该思想避免在传统容错路由中,网络流量集中在故障边界的问题,能够使网络流量更加均匀地分布;同时,为了避免基于Oblivious路由不连通的情况,在选择路由中间节点的过程中提出了基于矩阵相乘判断连通性的方法。通过在两阶段的路由中进行矩阵相乘计算准确排除了哪些导致不连通的中间节点。实验显示,通过使用该算法,有较少故障节点的网络的连通率达到100%。本文基于新的Oblivious容错路由的思想提出了三种2D-Mesh网络容错路由算法,即DXYFT算法、DYXFT算法和U3TFT算法,实现了从源节点到目的节点之间随机选择多条路径的功能。并对这三种路由算法的无死锁进行了证明。这些算法提高了吞吐率,避免了故障边界网络流量过于集中,使网络分布更加均衡,同时保证了系统的连通性。实验表明,与传统路由算法相比,新的算法在最坏情况的通讯情况下的网络吞吐率有较好的结果。例如在网络规模为6×6且多个故障节点的情况下与自适应绕道路由相比,DXYFT算法、DYXFT算法与U3TFT算法的最坏情况吞吐率分别提高了18%、18%和19%。 【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP393.0

【图文】：

路由器,报文

冲器的大小是流控单元的整数倍。路由器中开关的作用是需要将输入和输出的缓逡逑冲器进行内部的连接，其中连接分为全连接和非全连接等结构。逡逑一般的路由器模型如图２－１所示。传递报文消息的网络过程：１．输入通道的逡逑链接控制器收到报文消息之后，将报文消息存储到输入的缓冲器；２．路由和重载逡逑单元的模块，会读取报文头的路由信息；３．根据交换开关的使用情况进行判断，逡逑

路由算法

＿路由逡逑＼和仲戴逡逑图２－１路由器的结构逡逑２．３路由算法逡逑在二维Ｍｅｓｈ网络中，虽然拓扑结构比较简单，但是它属于比较严格的正交逡逑拓扑。在二维网络的之间进行消息传输时，必须有良好的路由算法作为传输的保逡逑障。路由算法应满足网络的一些基本要求。丨．性能要求是有限延迟、高吞吐量和逡逑低功耗。２．架构要求是通用性、可扩展性和简单性。３．路由算法的可靠性和寿命逡逑扩展能力己成为选择路由算法的关键因素。为了满足这些要求，存在确定性和自逡逑适应路由两种取向。逡逑２．３．１路由算法设计逦．逡逑路由算法是指从源节点传送消息到目的节点时有一条或者多条可以连通的逡逑路径。路由算法可以决定网络中的节点进行路由时对转发端口的选择，在一定程逡逑度上决定着整个Ｍｅｓｈ网络的吞吐量Ｍ。所以在路由算法设计时要考虑的因素有：逡逑１．

【相似文献】