导读:本文包含了无死锁路由算法论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:死锁,路由,算法,网络,立方,子网,自适应。
无死锁路由算法论文文献综述
陈凌剑[1]（2017）在《数据中心网络中节能路由算法及无死锁路由算法的研究》一文中研究指出为了满足日益增长的在线活动需求,数据中心的规模变得越来越大,很多数据中心都具有数十万台服务器。正因为数据中心的规模变得越来越大,导致如今具备大量网络设备的数据中心成为了地球上最大的能源消费者之一。本课题将从路由的角度对数据中心网络的节能问题进行研究。同样,因为数据中心的规模越来越大,提供的服务种类越来越多,经常会出现突发性数据包请求的情况,在这种情况下,很容易由于网络拥塞而导致数据包丢失。数据中心通过应用数据中心桥接技术解决了网络丢包问题,却又引入了路由死锁故障。为此,很多研究人员开展了对无死锁路由算法的研究,本课题也将针对路由死锁问题,对无死锁路由算法进行研究。本文的第一部分,从路由的角度出发,对数据中心网络的节能问题进行研究,提出了一种节能路由算法。本课题在系统初期搭建好网络拓扑结构时,以节点失效概率为主要参数计算出所有节点的重要性,从大到小排序得到重要节点排序矩阵,确保最后参与网络通信的重要节点的失效概率都很小,提高系统的可靠性。然后以重要节点排序矩阵为标准,从最不重要的节点开始,逐渐关闭对应的网络设备,只留下不可删除的重要节点进行网络通信。本文提出的算法以尽可能多的关闭网络设备为目标,为数据中心网络节省最多的能量。仿真实验结果表明,本文所提出的节能路由算法节能量更高。本文的第二部分,从限制路由路径无环路与寻找更短的路由路径角度出发,对数据中心网络的路由死锁问题进行研究,提出了一个有效的无死锁路由算法。本课题首先详细分析了数据中心网络拓扑结构的特征,在网络中构建广度优先搜索生成树来限制路由路径无环路,以此来避免死锁。同时使路由路径的长度更短,得到更低的网络平均时延和更高的网络吞吐量。另外,本文设计的无死锁路由算法还利用数据中心桥接技术,将物理层划分为多个虚拟层,既增加了路由路径的多样性,也增加了备份路由的数量,提高了路由算法的容错性。仿真实验结果显示,本文所设计的算法在保证无路由死锁的同时,网络性能也更优。(本文来源于《哈尔滨工业大学》期刊2017-12-01）
谢瑞莲[2]（2017）在《片上无死锁路由算法研究》一文中研究指出半导体技术的发展和应用需求推动着处理器设计进入“多核”甚至“众核”时代。在“多核”以及“众核”环境下,传统总线或点对点通信结构面临着性能、功耗和可扩展性等方面的不足。针对这些局限,研究者们借鉴计算机通信网络的思想提出了一种新的片上通信结构—片上网络(Network-on-Chip,NoC)。随着处理器核数的不断增加,由生产缺陷、工艺偏差和芯片老化等引发的硬故障导致NoC出现故障的概率也在相应提高。另外,网络拥塞导致数据的传输延时显着增加,NoC整体性能急剧下降。因此,本文以容错路由和拥塞路由为对象,研究2D mesh结构片上网络中无死锁容错路由算法和拥塞感知自适应路由算法。路由算法主要采用虚通道技术和无虚通道转向模型来避免死锁。本文主要内容包括:1.提出了一种面向单故障无虚通道容错路由算法在分析单故障NoC结构特点的基础上,本文提出了一种适用于容错的奇偶(Fault-Tolerant Odd-Even,FTOE)转向模型,以弥补现有转向模型应用于无虚通道容错路由算法中存在故障周围负载不均衡和丢包的问题。同时基于该转向模型本文设计了一种可重构的无虚通道容错路由(Reconfigurable and Fault-Tolerant Routing,RFTR)算法。RFTR算法可以容忍任意位置的单链路故障或者单节点故障,并且均衡了故障周围的负载,缩短了部分数据包的绕行路径。2.提出了一种面向多节点故障无虚通道容错路由算法面向多节点故障的无虚通道容错路由算法通常采用故障模型将多节点故障容错问题转换为故障区域绕行问题,从而简化了算法的复杂度。然而,现有多节点故障无虚通道容错路由算法都存在故障区域周围负载不均衡和长绕行路径的问题;并且由于数据包垂直进入故障区域边界而引入被禁止的转向,造成网络死锁。为了解决上述问题,本文将FTOE转向模型与提前预测相结合,设计了一种面向多节点故障的负载均衡无虚通道容错路由(Load-Balancing and Fault-Tolerant routing,LBFT)算法。LBFT算法只需要存储少量的故障信息就能预测故障区域的位置并且提前绕过它,这样数据包就不会垂直进入故障区域边界,避免了网络死锁。更重要的是,LBFT算法可以容忍任意位置、任意数量的节点故障,并且均衡了故障区域周围的负载,缩短了部分数据包的绕行路径。3.提出了一种面向多故障的自适应容错路由算法无虚通道容错路由算法通常采用转向模型来避免死锁,而转向模型禁止了一些转向,降低了算法的自适应性。为了采用最少数量虚通道,同时又使得容错路由算法具有更大的自适应性,本文将double-Y结构应用于片上网络中,该网络Y方向采用两条虚通道,X方向采用一条虚通道。然而,应用于double-Y网络的现有转向模型由于其自身的限制,容错路由算法只能容忍单链路故障或者单节点故障。随着故障的不断增加,越来越多的数据包被丢弃。因此,本文提出了一种新的转向模型NMad-y,该转向模型将现有转向模型中被禁止的转向变为可转,大大提高了转向模型的自适应性。本文还提出了一种新的故障信息分发机制,该机制可以分发2-hop之内邻接链路的故障信息。最后基于NMad-y转向模型和2-hop之内链路的故障信息,本文设计了一种自适应容错路由(Adaptive and Fault-Tolerant Routing,AFTR)算法。该算法可在不丢失网络性能的前提下提高网络的可靠性,实现了数据包97.43%的到达率,并且可以容忍任意位置、任意数量的链路故障和节点故障。4.提出一种面向高效拥塞传播机制的非本地自适应路由算法非本地自适应路由算法通常采用本地和远端链路的拥塞信息选择输出路径,从而大大促进网络性能。现有的非本地自适应路由算法都采用专用的拥塞信息传播网络或者将拥塞信息嵌入到数据包包头中传播。经过拥塞信息的传播,网络中的每个节点都知道远端链路的状态。然而,这些拥塞传播机制要么引入额外的硬件开销,要么使得拥塞信息传播不及时,进而造成更大的拥塞。为了解决上述问题,本文提出了一种基于消息的拥塞信息传播机制,该机制采用两种专用的消息传播拥塞信息,这样既没有引入额外的硬件开销,也使得拥塞信息传播更及时。最后本文设计了一种高效的非本地自适应路由(Efficient and Non-local Adaptive Routing,ENAR)算法。ENAR算法根据被传播的拥塞信息选择输出路径,能有效避免网络拥塞。由于该算法只考虑位于源节点和目标节点之间最小象限内的链路状态,且每个方向只比较相同数量的链路状态,因此消除了冗余信息。(本文来源于《西安电子科技大学》期刊2017-04-01）
陈洁坤,管祥生,续鹏[3]（2017）在《基于3Dmesh的新型热量均衡无死锁路由算法》一文中研究指出该文根据叁维片上网络结构温度特性,提出了一种基于3D Mesh结构的新型热量均衡路由算法TLHB(Transport Layer Heat Balance Routing),并且给出无死锁证明。通过网络仿真软件OPNET14.5,将该算法在一个4*4*4的3D Mesh网络中进行仿真,并与XYZ路由算法,TADR路由算法以及TLAR路由算法进行比较,结果显示TLHB算法在网络性能几乎没有下降的前提下,热量性能指标方面较现有的叁维路由算法有所提升。(本文来源于《电子质量》期刊2017年01期）
曹继军,王克非,庞征斌,刘路[4]（2015）在《“天河一号”正交交换机无死锁负载均衡路由算法》一文中研究指出基于正交背板的交换结构(简称为正交交换机)是实现高阶互连网络高密度封装的重要技术途径。描述了"天河一号"正交交换机的结构,分析了该正交交换机容易出现的路由环路及其死锁问题,进一步提出了无死锁的负载均衡路由算法,讨论了该路由算法优缺点。提出的路由算法已实际应用于"天河一号"高性能计算系统互连网络中,既避免了路由死锁,又达到了静态负载相对均衡,分析了路由算法的可行性与有效性。研究成果对于采用类似结构正交交换机的无死锁负载均衡路由算法设计具有借鉴意义。(本文来源于《第十九届计算机工程与工艺年会暨第五届微处理器技术论坛论文集》期刊2015-10-18）
梁锦叶,梁家荣,苏树海[5]（2014）在《交换超立方网的无死锁虫洞路由算法》一文中研究指出针对交换超立方网络通信中所出现的死锁及延迟问题,提出了一种基于虫洞路由的无死锁算法。引入交换超立方网的s-导出子网和t-导出子网的的概念,证明了s-导出子网和t-导出子网分别同构于s维超立方体网络和t维超立方体网络。通过把交换超立方网分解成若干个s-导出子网和t-导出子网,利用虚通道技术和虫洞路由策略设计了交换超立方网络的最短路径路由算法。理论分析证明,所提出的最短路径路由算法是无死锁的,且有效地减少了交换超立方网络通信的延迟。(本文来源于《计算机应用研究》期刊2014年06期）
王新玉[6]（2014）在《二维DMesh网络中基于转弯模型的无死锁路由算法研究》一文中研究指出路由算法对整个互连网络的性能有着至关重要的影响。二维DMesh网络有效地结合了Mesh网络以及高阶路由器的优势,降低了网络的拓扑直径和平均跳步数,为消息传输提供了更多的可选择路径。针对DMesh网络,设计了一种基于转弯模型的适应性无死锁路由算法,该算法为消息传输提供了更多的灵活性。当网络中负载率较高时,能够指导消息避开拥塞区域和热点路由器,降低等待时间,最终指导消息以更快的速度到达目的节点。对新提出的路由算法进行了路径多样性方面的分析,并对算法的无死锁性进行了严格的证明。仿真实验结果表明,与DMesh网络中传统的DXY路由算法相比,这种新的适应性路由算法有效地降低了平均延迟,增加了消息传输的灵活性,最终提高了整个网络的通信性能。(本文来源于《沈阳师范大学学报(自然科学版)》期刊2014年02期）
陈宜漂[7]（2013）在《基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法》一文中研究指出并行计算是一个重要的研究领域,而提高其处理器间的通信效率是一个重要的研究课题。网络中的路由是指将消息从源节点经过一些中间中继转发节点传送到目的节点的过程。路由规则的好坏直接决定着并行计算机的性能,其中容错路由是衡量路由规则的标准之一。本论文基于二维平面网格的容错自适应路由算法,研究缩短路由长度,提高路由效率的方法。无线传感器网络是近年来成为一个研究的热点,基于上面的定位算法,数据收集方法,拓扑结构研究等多方面,多角度的研究取得相当的成果。本文在二维拓扑结构用于并行计算的基础上拓展到无线传感器网络上,并取得良好的效果。对于容错自适应路由在并行计算及无线传感器网路的应用和负载平衡问题的改进是本文的主要内容。本论文提出并实现的新算法“容错自适应故障块路由表算法”是基于《图论在通信网络和无线网络传感器网络中的应用》中提到的全新容错模型——有缝隙的裂痕矩形块(cracky rectangular block)。它是指在含有故障的网络中形成一些极小的不交块,使得处于块的边界和块的外部的链路都无故障,而所有的故障链路或结点都位于块的内部,称这样的块为故障块,将故障块内部的连通结点经无故障链路悬挂在以故障块边界点为根的树上,由这样的树和故障块的边界构成的图叫做裂痕故障块,也称作有缝隙的裂痕矩形块。该算法通过相邻结点间不断地发送消息,不断更新自己的状态直到每个点的状态都稳定为止实现了二维网格中故障块的构造。本论文提出的负载平衡模型应用在无线传感器网络中取得良好的效果。由于路由大都要经过内部节点,使得内部节点的负责大于边界节点,这导致负载不均衡从而造成网络拥堵,使得网络的生命周期下降。为了克服负载平衡,本论文提出了一种可行的网络结构模型,这种网络结构模型从根本上解决了大部分路由需要通过内部节点的问题,因为在这种网络结构模型下,边界节点能直接传送,这与Torus模型类似,但不一样,因为如果无线传感器的所有节点像Torus结构那样都能相互间通信,那么将产生巨大的电磁干扰以及昂贵的造价,在现实应用中很不可行。本论文设计了一系列的实验。在比较容错自适应路由算法按照网格规模和故障块占比这两个条件进行设计,其中网格规模分别为25×25,50×50,100×100,200×200,故障块占比分别为10%,20%,30%,40%,50%。实验采用随机产生出错结点的方法,随机产生1000对不同的发送点和接收点,计算两种算法的平均路由路径长度。在设计无线传感器网络负载平衡试验时,也采取了随机路由1000对不同的发送点和接收点,在没有故障块的良好网络里进行比较。网格规模也采取25×25,50×50,100×100,200×200,尽可能多地比较负载平衡的结果。之所以选取完好的网络是为了让负载平衡不受故障块的影响。本论文的重要贡献是提出了改进型容错自适应路由算法的,使得不论在哪种网格规模,何种故障块占比下,改进型容错自适应路由算法都能减少路由长度,增加路由的目标性。并且将此算法用于无线传感器网络中,通过进一步研究路由负载平衡问题,提出新的无线传感器网络拓扑模型,这种模型使得边界节点也能够参与路由,从而降低网络内部节点的负载,达到负载平衡的目的。此外进一步提出了基于裂痕故障块解决死锁的路由算法,采用最少虚拟通道数量,解决死锁的问题。(本文来源于《兰州大学》期刊2013-03-01）
曹入辉,梁家荣,王新阳,豆秋丽[8]（2013）在《交换超立方网的自适应性无死锁路由算法》一文中研究指出交换超立方网是一种新提出来的互连网络。首先,利用图论的方法研究了交换超立方网的拓扑性质,引入了相似子网的概念,得出相似子网和超立方体同构的结论;然后,利用将物理通道分成两条虚拟通道的方法,给出了一种交换超立方网的自适应性路由算法,并从理论上证明了该算法的无死锁性。(本文来源于《计算机工程与科学》期刊2013年02期）
虞潇,李丽,张宇昂,潘红兵,王佳文[9]（2013）在《一种面向功耗免死锁叁维全动态3D NoC路由算法》一文中研究指出随着近年来叁维片上网络(3D NoC)技术的提出及不断发展,功耗问题已成为3D NoC设计中面临的严峻挑战之一.本文为3DNoC提出一种面向功耗免死锁叁维全动态路由算法TFRA(Three-dimensional Ful-l adaptive Rout-ing Algorithm).其以传统二维NoC奇偶拐弯模型为基础,将叁维路由空间划分为8个象限,针对每个象限制定相应的路由策略,从而实现免死锁.采用SystemC系统级建模语言搭建的3D NoC仿真平台进行验证,结果显示TFRA算法在功耗性能指标方面较现有的叁维路由算法有大幅提升.(本文来源于《电子学报》期刊2013年02期）
周磊,吴宁,李云[10]（2013）在《一种基于2D-mesh的片上网络无死锁容错路由算法》一文中研究指出为解决片上网络中的永久性故障问题,提出一种基于2D-mesh拓扑结构的无死锁容错路由算法.定义了新的故障块生成规则,减小了故障节点的区域和受影响的健康节点数目,设计了一种故障节点探测和绕道路径生成算法,通过递归式消息传递实现了故障块区域的建立和绕道路径列表的生成.在绕道容错路由算法中,采用部分路由表与路由规则相结合的方法,通过在报头中加入绕道路径列表的方式引导报文绕过故障区域.结果表明,与现有算法相比,所提出的容错路由算法在随机均衡负载和热点负载2种情况下的延时都有所降低.(本文来源于《上海交通大学学报》期刊2013年01期）
无死锁路由算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
半导体技术的发展和应用需求推动着处理器设计进入“多核”甚至“众核”时代。在“多核”以及“众核”环境下,传统总线或点对点通信结构面临着性能、功耗和可扩展性等方面的不足。针对这些局限,研究者们借鉴计算机通信网络的思想提出了一种新的片上通信结构—片上网络(Network-on-Chip,NoC)。随着处理器核数的不断增加,由生产缺陷、工艺偏差和芯片老化等引发的硬故障导致NoC出现故障的概率也在相应提高。另外,网络拥塞导致数据的传输延时显着增加,NoC整体性能急剧下降。因此,本文以容错路由和拥塞路由为对象,研究2D mesh结构片上网络中无死锁容错路由算法和拥塞感知自适应路由算法。路由算法主要采用虚通道技术和无虚通道转向模型来避免死锁。本文主要内容包括:1.提出了一种面向单故障无虚通道容错路由算法在分析单故障NoC结构特点的基础上,本文提出了一种适用于容错的奇偶(Fault-Tolerant Odd-Even,FTOE)转向模型,以弥补现有转向模型应用于无虚通道容错路由算法中存在故障周围负载不均衡和丢包的问题。同时基于该转向模型本文设计了一种可重构的无虚通道容错路由(Reconfigurable and Fault-Tolerant Routing,RFTR)算法。RFTR算法可以容忍任意位置的单链路故障或者单节点故障,并且均衡了故障周围的负载,缩短了部分数据包的绕行路径。2.提出了一种面向多节点故障无虚通道容错路由算法面向多节点故障的无虚通道容错路由算法通常采用故障模型将多节点故障容错问题转换为故障区域绕行问题,从而简化了算法的复杂度。然而,现有多节点故障无虚通道容错路由算法都存在故障区域周围负载不均衡和长绕行路径的问题;并且由于数据包垂直进入故障区域边界而引入被禁止的转向,造成网络死锁。为了解决上述问题,本文将FTOE转向模型与提前预测相结合,设计了一种面向多节点故障的负载均衡无虚通道容错路由(Load-Balancing and Fault-Tolerant routing,LBFT)算法。LBFT算法只需要存储少量的故障信息就能预测故障区域的位置并且提前绕过它,这样数据包就不会垂直进入故障区域边界,避免了网络死锁。更重要的是,LBFT算法可以容忍任意位置、任意数量的节点故障,并且均衡了故障区域周围的负载,缩短了部分数据包的绕行路径。3.提出了一种面向多故障的自适应容错路由算法无虚通道容错路由算法通常采用转向模型来避免死锁,而转向模型禁止了一些转向,降低了算法的自适应性。为了采用最少数量虚通道,同时又使得容错路由算法具有更大的自适应性,本文将double-Y结构应用于片上网络中,该网络Y方向采用两条虚通道,X方向采用一条虚通道。然而,应用于double-Y网络的现有转向模型由于其自身的限制,容错路由算法只能容忍单链路故障或者单节点故障。随着故障的不断增加,越来越多的数据包被丢弃。因此,本文提出了一种新的转向模型NMad-y,该转向模型将现有转向模型中被禁止的转向变为可转,大大提高了转向模型的自适应性。本文还提出了一种新的故障信息分发机制,该机制可以分发2-hop之内邻接链路的故障信息。最后基于NMad-y转向模型和2-hop之内链路的故障信息,本文设计了一种自适应容错路由(Adaptive and Fault-Tolerant Routing,AFTR)算法。该算法可在不丢失网络性能的前提下提高网络的可靠性,实现了数据包97.43%的到达率,并且可以容忍任意位置、任意数量的链路故障和节点故障。4.提出一种面向高效拥塞传播机制的非本地自适应路由算法非本地自适应路由算法通常采用本地和远端链路的拥塞信息选择输出路径,从而大大促进网络性能。现有的非本地自适应路由算法都采用专用的拥塞信息传播网络或者将拥塞信息嵌入到数据包包头中传播。经过拥塞信息的传播,网络中的每个节点都知道远端链路的状态。然而,这些拥塞传播机制要么引入额外的硬件开销,要么使得拥塞信息传播不及时,进而造成更大的拥塞。为了解决上述问题,本文提出了一种基于消息的拥塞信息传播机制,该机制采用两种专用的消息传播拥塞信息,这样既没有引入额外的硬件开销,也使得拥塞信息传播更及时。最后本文设计了一种高效的非本地自适应路由(Efficient and Non-local Adaptive Routing,ENAR)算法。ENAR算法根据被传播的拥塞信息选择输出路径,能有效避免网络拥塞。由于该算法只考虑位于源节点和目标节点之间最小象限内的链路状态,且每个方向只比较相同数量的链路状态,因此消除了冗余信息。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
无死锁路由算法论文参考文献
[1].陈凌剑.数据中心网络中节能路由算法及无死锁路由算法的研究[D].哈尔滨工业大学.2017
[2].谢瑞莲.片上无死锁路由算法研究[D].西安电子科技大学.2017
[3].陈洁坤,管祥生,续鹏.基于3Dmesh的新型热量均衡无死锁路由算法[J].电子质量.2017
[4].曹继军,王克非,庞征斌,刘路.“天河一号”正交交换机无死锁负载均衡路由算法[C].第十九届计算机工程与工艺年会暨第五届微处理器技术论坛论文集.2015
[5].梁锦叶,梁家荣,苏树海.交换超立方网的无死锁虫洞路由算法[J].计算机应用研究.2014
[6].王新玉.二维DMesh网络中基于转弯模型的无死锁路由算法研究[J].沈阳师范大学学报(自然科学版).2014
[7].陈宜漂.基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法[D].兰州大学.2013
[8].曹入辉,梁家荣,王新阳,豆秋丽.交换超立方网的自适应性无死锁路由算法[J].计算机工程与科学.2013
[9].虞潇,李丽,张宇昂,潘红兵,王佳文.一种面向功耗免死锁叁维全动态3DNoC路由算法[J].电子学报.2013
[10].周磊,吴宁,李云.一种基于2D-mesh的片上网络无死锁容错路由算法[J].上海交通大学学报.2013
论文知识图
![基于优先级的流量控制[7]](http://image.cnki.net/GetImage.ashx?id=1018895074.nh0001&suffix=.jpg)
