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

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

基于部分自适应路由的片上网络数据传输防护机制

现代多处理器片上系统(MPSoC)将应用程序分布在多个IP上,而片上网络(NoC)是广泛采用的IP间数据交换解决方案.由于不同的IP可能由多个第三方供应商提供,而第三方供应商的可信度往往难以保证,在这种情况下,如何确保重要IP之间的安全数据通信是一个重要的研究课题.本文按应用程序的需求构建NoC安全区,并对可能遭受攻击的安全区成员实施防护措施.通过对成员间传输的数据进行认证加密来保证数据的安全,同时,在数据包路由过程中对其进行逐跳认证的方式实现对恶意节点的检测与定位.对于定位到的恶意节点,本设计能通过部分自适应路由技术对其进行路由隔离,防止恶意节点再次危害数据安全.在gem5仿真器的ruby内存模型的garnet框架上实现了该设计,并进行了功能和性能的验证.实验结果表明,所提出的防护设计能够保证NoC数据传输的有效性和可靠性,同时对系统的性能影响较小.

最短路径自适应路由的路径条数及可缓冲的数据包数目

在采用最短路径自适应路由方案的片上网络中,从源节点到目的节点具有多条可能的路径,采用最短路径有助于提高片上网络的效率。片上网络每一级路由器都能缓冲一定量的数据包,从源节点到目的节点的距离越远、路径数目越多,可缓冲的数据包数目越多。处理单元(Processing Element,PE)间数据传输需要的流量控制数据包越少,数据传输的效率越高。本文提出从源节点到目的节点可缓冲数据包数目的两种计算方法,并通过计算机搜索和仿真进行了验证。研究结果有助于提升对采用最短路径自适应路由的片上网络的行为的认识,从而设计更好的PE间数据传输方案。

移动无线传感网能量时延约束的自适应路由及性能评估

针对间歇性连通的移动无线传感网提出一种能量时延约束的自适应路由协议(EDCA),EDCA由初始化阶段、转发决策阶段、转发阶段和等待阶段组成,传感器节点根据目标时延实时判断是否转发副本,并选择剩余能量多的节点进行副本转发.EDCA对平均时延和网络负载具有控制力,对网络环境变化具有自适应能力,能够有效延长网络生命周期.

应用于Ad Hoc网络的时延敏感自适应路由协议

针对Ad Hoc网络中实时业务对网络平均时延的要求,提出了一种应用于AdHoc网络的新型路由协议——时延敏感的自适应路由协议。该协议在保持“最少跳数”的最佳路由条件下,增加了“平均最短时延”的约束条件,从而不仅可以为实时业务(即时延敏感的业务)提供可靠的路由,同时还能根据网络节点当前的业务流量,动态地选择最佳路径,降低网络的平均时延。这是一种新型的有QoS保证的路由协议。仿真结果表明,该协议的确可以有效地改善网络的性能。

一个低代价的完全自适应路由器设计

互连网络路由器是MPP系统的关键部件，其性能优劣直接影响系统性能．本文在mesh结构上，针对完全自适应路由算法实现难度较大的问题，在性能、代价和实现复杂性上进行合理折衷，给出了一个代价低、自适应性强的完全自适应路由算法LCFAA，对传统的虫孔路由切换技术进行改进，提出了弹性虫孔路由切换技术（elasticwormhole），并采用基于虚通道的综合流控策略，设计了一个简洁高效的完全自适应路由器LFR。

众核处理器片上网络的层次化全局自适应路由机制

Mesh和环拓扑结构以其实现简单、易于扩展的特点成为众核处理器片上网络应用最为广泛的拓扑结构.应用于Mesh结构中的健忘型路由算法在网络流量较大时影响片上网络的负载均衡,表现在降低吞吐量和增大数据包延迟.自适应算法中的本地自适应算法和区域自适应算法均存在不同程度的短视现象,不适合大规模的Mesh结构,而目前全局自适应算法又由于路由计算量大而速度缓慢.提出一种新的层次化全局自适应路由机制,包括一个全局拥塞信息传播网络Roof-Mesh和一个层次化全局自适应路由算法(global hierarchical adaptive routing algorithm,GHARA).通过全局拥塞信息传播网络得到拥塞信息,GHARA采用全网分区逐级计算路由的方式,减少了全局路由的计算步骤,从而减少了平均数据包延迟、提升了饱和带宽.实验结果表明GHARA表现优于其他区域和全局自适应路由算法.在人工注入通信模式下,8×8 Mesh平均饱和带宽比全局自适应算法GCA提高10.7%,16×16Mesh平均饱和带宽比全局自适应算法GCA提高14.7%.在运行真实测试程序集SPLASH-2模式下,数据包延迟最高比GCA提高40%,平均提升14%.

基于WDM技术的虚拟多环互连网络的自适应路由算法

自适应路由算法能够根据网络状态选择能回避阻塞或故障结点的路径 ,使得链路得到有效利用 ,均匀分布通信流量 ,减少平均传输延时 ,最大限度地提高网络的性能 .该文针对一种结构简单、易于实现、性能较优的多跳虚拟环网结构 DS- WDM Ring设计了三种自适应路由算法 .在 PC机上设计并实现了路由算法模拟模型 ,对 DS-WDM Ring上的自适应路由算法和静态路由算法进行了模拟 ,统计出了几种路由算法在不同的网络负载下的平均阻塞率、平均跳数、平均延时和结点端口的利用率 ,比较分析了几种路由的性能 .

多层卫星通信网络自适应路由策略

单层卫星网络由于轨道高度和覆盖能力的不同,以至构成通信的单层系统往往不能满足不同业务服务质量的需求。分析了Walkerdelta型星座构建多层卫星通信网络的拓扑结构和ISL性能,提出了在统计分布模型下的多层卫星自适应路由策略,综合考虑了路径时延和ISL链路负载。仿真结果表明了多层网络自适应路由策略能够更加有效地分配网络通信量,网络具有较小的丢包率、网络平均归一化链路负载和特定路径综合路径权重,有利于降低网络平均阻塞概率和特定路径阻塞概率,获得更高的可靠性,较传统的单层非自适应路由更加有效、可靠。

片上网络中基于拥塞感知的自适应路由算法

针对片上网络中现有XY路由算法延时较高的问题,提出一种新的容错和拥塞感知型自适应路由算法。采用分布式策略将常规的片上网络架构分为多个由本地监测单元控制的区域,每个本地监控单元利用最短路径计算方法检测出最优路径,以避免采用拥塞严重的路由器和故障链路,进而降低延时。为了对不断变化的网络状态做出响应,给出基于ball-string模型的最短路径计算方法,并结合基于分布式区域路由方法实现硬件开销最小化。基于真实Verilog部署的实验结果表明,与传统的XY路由算法和Dy XY自适应路由算法相比,该算法能明显提升网络吞吐量。

Torus网络中基于中心距离的完全自适应路由算法

Torus网络凭借其优越的结构特性,引起了工业界和学术界的广泛关注.高效、无死锁的路由算法设计是互连网络研究的一个重要方面.针对Torus网络实现自适应路由所需虚通道数目多的缺点,提出了自适应路由算法Gear,该算法基于中心距离的方法来限制虚通道的使用,在虚切通交换下仅需两条虚通道即可为Torus网络提供无死锁自适应路由.通过仿真对所提算法的有效性进行了验证,结果表明,在同等情况下算法Gear的性能较经典的维序路由和Duato协议具有非常明显的优势.

环网中的维度气泡流控与自适应路由算法

介绍了一个称为环网维度气泡流控(TDBFC)的新型流控策略和称为环网维度气泡路由(TAD-BR)算法的新型自适应路由算法.在Bubble流控和DBFC流控的基础上设计了适合于环网的维度气泡流控.在环网中,如果采用TDBFC流控策略,设计的TADBR自适应路由算法可实现无死锁的最短距离的路由.对于以上结论,提供了详细的证明.最后,介绍了自行设计的模拟工具RingNetSim,该模拟器实现了TDBFC流控策略和TADBR算法.在RingNetSim上分析了TADBR算法的性能,结果显示环网维度气泡路由算法拥有较好的性能.

LCFAA:一个低代价的完全自适应路由算法

大规模并行处理机系统（ＭＰＰ）中路由算法对互联网络通信性能和系统性能起着重要作用．自适应路由算法具有灵活性好、网络的通道利用率高和网络容错能力强等优点，但其实现难度较大，因而目前仅在少数ＭＰＰ系统中得以实现．文中在ｍｅｓｈ结构上提出了一个低代价无死锁的完全自适应最短虫孔路由算法ＬＣＦＡＡ，该算法所需虚通道数少，具有代价低、自适应性强的特点．文中证明了算法的无死锁、无活锁性和完全自适应性，并模拟验证了其性能．

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

大规模并行处理机系统（ＭＰＰ）中路由算法对互联网络通信性能和系统性能起着重要作用．文中在虫孔路由的直接网络中提出了一种虚网叠加的自适应路由算法构造框架ＶＮＯＦ，框架中为每条物理通道上设置多条虚通道，将物理网络划分成一组独立的虚拟子网，在不同的虚拟子网中根据不同的应用目的可采用不同的路由算法，但保证有一子网中采用的路由算法是无死锁的，由此达到整个网络的无死锁性．基本框架还保证了算法的无活锁性和自适应性．文中最后给出了基于该框架设计的几个典型算法，为具体算法设计提供指导．

海上无线网状网中基于Q-Learning的自适应路由算法

针对海上无线网状网通信环境复杂多变、船舶节点具有特殊移动模型等特点,提出一种基于Q-Learning的自适应路由(Q-Learning Based Adaptive Routing,QLAR)算法。综合考虑海上无线电波传播特性、船舶航程信息以及相应海区气象信息等因素的影响,提出链路可靠性、链路稳定性和节点航程相似度等概念,并对链路状态进行评估;然后,根据链路状态评估结果,利用Q-Learning算法寻找源、目的节点间最稳定的路径以传输数据分组;最后,利用OPNET搭建仿真平台对算法进行测试。仿真结果表明,与4种对比算法中性能最优的算法相比,QLAR算法最高可提升分组投递率4.89%,降低平均分组时延17.42%,减少归一化路由开销21.99%。

MANETs面向稳定性的自适应路由开销控制算法

为了在节点频繁移动的MANETs网络环境中发现和建立具有较长维持时间的路由,以增强路由的可用性和数据传输的连续性,面向稳定性的路由算法需要中间节点转发更多的RREQ分组,但这会造成路由开销显著增加。为此,提出了一种面向稳定性的自适应路由开销控制算法。算法使用策略型博弈对RREQ转发过程进行建模,利用该博弈存在的混合策略纳什均衡计算RREQ的转发概率,实现RREQ的概率转发。仿真结果表明,提出的面向稳定性的自适应路由开销控制算法不仅保证了路由的稳定性和分组递交率,而且有效地减少了路由开销和传输延迟。

基于改进遗传算子的QoS自适应路由算法

基于改进遗传算子的自适应路由算法有效地解决了应用RIP、SPF等协议造成的网络拥塞问题,模拟试验表明该算法简明有效。

用于自适应路由片上网络的缓冲分配算法

针对片上网络缓冲资源紧张的问题,提出了一种缓冲分配算法。在有限的资源下,该算法能够根据每个路由器输入通道上负载的情况来自动分配缓冲资源,从而获得最大的网络性能。在该算法中,提出了适用于自适应路由算法下的路由器性能分析模型,利用该模型可以快速定位系统中的性能瓶颈。仿真实验的结果表明,使用本算法后的NoC能比均匀分配策略下的NoC获得更小的数据包平均传输时延,同时,该算法还能节省约33%的缓冲资源。

无线传感网自适应路由的能量空洞抑制研究

在无线传感器网络中,由于节点的能量消耗不均衡,容易造成能量空洞,当能量空洞范围扩大到一定程度时会阻断路由,从而导致整个网络失效,造成能量的极大浪费;针对现有发送速率可调方法中的功率级别太多,计算较复杂,并结合跳数因子,提出了发送速率和跳数协同的自适应路由算法,其中对于功率的计算简单,并且在路由选择时基于剩余能量,充分利用能耗低的节点的能量,达到均衡整个网络能耗的目的;实验结果表明,此算法可以有效延缓能量空洞的形成速度,延长了网络寿命20%左右。

自适应路由算法优于确定性路由算法

在研究并行计算机系统的容错时 ,自适应路由算法是一个极为重要的研究课题 .它是在网络结点出错时 ,算法通过可选择的路径进行路由 .在每个结点具有独立的出错概率的模型下 ,研究 Mesh网络上自适应路由算法和确定性路算法的性能 .本文提出的技术使得我们能严格地推导出路由算法的成功的概率 ,从而能分析和比较算法的性能 .研究结果表明自适应路由算法具有明显的优势 :一方面确定性路算法需要全局错误信息而变得高效性 ,另一方面自适应路由算法对于结点出错和网络规模具有更好的健壮性而具有更高的成功概率 .