文档介绍：片上网络自适应路由选择策略
冯漪平 摘要:本文研究了现有自适应路由算法选择策略,提出一种适合于片上网络自适应路由算法选择策略的设计方法――动态的、非探测式的路由选择,并设计了SDNS(Simple Dynamic Non-Cred集网络状态信息并更新路由表。自适应路由选择拥塞较小方向作为发送方向来减少网络中热点(Hot Spot)的形成。提出片上网络邻居节点拥塞发现选择策略(Neighbors-on-Path Congestion-Aware Selection)。NoP策略在进行路由选择时,假设下一跳各可选相邻节点向当前数据包的目的节点发送数据包,NoP策略将沿某一条从相邻节点到目的节点的路径上所有缓存占用的数量相加,最后选择缓存占用最少的方向作为数据包发送的方向。
由于片上网络的硬件条件限制,片上网络设计的各方面,包括拓扑结构、IP核之间的交换方式、路由算法等,和多处理器系统都存在差异。片上网络的路由算法需要与片上网络中特殊的拓扑结构、交换方式相适应,才能够在有效地利用有限的资源条件下,保证良好的数据传输能力。
在传统网络中,广泛采用专门探测包收集网络负载信息的方法,它提高了自适应路由算法的性能。但是由于适用于片上网络的虫孔交换方式可能会使数据包跨越多个节点,这种方法应用在片上网络中时,会降低探测包所收集网络负载信息的有效性,不能获得其在传统网络中相当的性能。在片上网络探测包工作所产生的开销不能忽视,它需要设计的专门硬件模块,产生额外的功耗,这些限制是片上网络设计中区别于传统网络设计非常重要的方面。与传统的相邻节点最小拥塞选择策略不同,NoP策略和基于蚁群方式的策略是基于全局网络负载信息自适应路由选择策略,实现基于全局网络负载信息的自适应路由选择策略需要产生NoC设计更多的开销。基于蚁群算法建模的选择策略中,每个节点在一定的时钟间隔向网络中所有节点广播探测包,并且需要建立与数据包传输并行的探测包控制模块和路由表,其路由表随着网络规模的增大而不断增大;NoP选择策略在路由决策时需要迭代计算某一条路径上所有可能路由节点的缓存占用数量,当数据包离目的节点距离较远时,会产生较大的时间开销。此外,由于基于全局网络负载信息的自适应路由选择策略实现过程复杂,决策过程中网络状态的变化可能会降低所收集网络负载信息的有效性。
片上网络路由算法选择策略设计的困难之处在于,如何在非常有限的硬件条件下,减小或者避免额外的硬件和能耗开销,同时又能充分利用可用网络资源,提高数据传输的效率。本文研究片上网络在互连传输中各方面的特点,抽象出片上网络路由选择策略中对开销和性能影响很大的两个属性,提出一种适合于片上网络应用的自适应路由选择策略设计方法。
一、探测式路由选择与非探测式路由选择
探测式路由选择策略在传统路由中有着广泛的应用,它通过专用的探测包收集局部或者全局的网络状态信息,作为路由选择的依据。探测式路由选择策略需要一组专门的硬件来完成探测包生成、发送、回收以及处理的过程。在传统网络设计中,硬件以及能耗限制较小,探测式路由选择测策略产生的额外开销是值得的。由于对面积需求小,和其他交换方式相比,虫蚀寻径是适合于片上网络要求的数据交换方式。在这种数据交换方式下,数据包会跨越多个节点,采用探测式路由选择策略容易出现探测包收集到的信