Bi-LCQ: A low-weight clustering-based Q-learning approach for NoCs

Network congestion has a negative impact on the performance of on-chip networks due to the increased packet latency. Many congestion-aware routing algorithms have been developed to alleviate traffic congestion over the network. In this paper, we propose a congestion-aware routing algorithm based on the Q-learning approach for avoiding congested areas in the network. By using the learning method, local and global congestion information of the network is provided for each switch. This information can be dynamically updated, when a switch receives a packet. However, Q-learning approach suffers from high area overhead in NoCs due to the need for a large routing table in each switch. In order to reduce the area overhead, we also present a clustering approach that decreases the number of routing tables by the factor of 4. Results show that the proposed approach achieves a significant performance improvement over the traditional Q-learning, C-routing, DBAR and Dynamic XY algorithms.     

Design and evaluation of a high throughput QoS-aware and congestion-aware router architecture for Network-on-Chip

This paper proposes a novel QoS-aware and congestion-aware Network-on-Chip architecture that not only enables quality-oriented network transmission and maintains a feasible implementation cost but also well balance traffic load inside the network to enhance overall throughput. By differentiating application traffic into different service classes, bandwidth allocation is managed accordingly to fulfill QoS requirements. Incorporating with congestion control scheme which consists of dynamic arbitration and adaptive routing path selection, high priority traffic is directed to less congested areas and is given preference to available resources. Simulation results show that average latency of high priority and overall traffic is improved dramatically for various traffic patterns. Cost evaluation results also show that the proposed router architecture requires negligible cost overhead but provides better performance for both advanced mesh NoC platforms.     

EDXY – A low cost congestion-aware routing algorithm for network-on-chips

In this paper, an adaptive routing algorithm for two-dimensional mesh network-on-chips (NoCs) is presented. The algorithm, which is based on Dynamic XY (DyXY), is called Enhanced Dynamic XY (EDXY). It is congestion-aware and more link failure tolerant compared to the DyXY algorithm. On contrary to the DyXY algorithm, it can avoid the congestion when routing from the current switch to the destination whose X position (Y position) is exactly one unit apart from the switch X position (Y position). This is achieved by adding two congestion wires (one in each direction) between each two cores which indicate the existence of congestion in a row (column). The same wires may be used to alarm a link failure in a row (column). These signals enable the routing algorithm to avoid these paths when there are other paths between the source and destination pair. To assess the latency of the proposed algorithm, uniform, transpose, hotspot, and realistic traffic profiles for packet injection are used. The simulation results reveal that EDXY can achieve lower latency compared to those of other adaptive routing algorithms across all workloads examined, with a 20% average and 30% maximum latency reduction on SPLASH-2 benchmarks running on a 49-core CMP. The area of the technique is about the same as those of the other routing algorithms.     

CAP-W: Congestion-aware platform for wireless-based network-on-chip in many-core era

In order to fulfill the ever-increasing demand for high-speed and high-bandwidth, wireless-based MCSoC is presented based on a NoC communication infrastructure. Inspiring the separation between the communication and the computation demands as well as providing the flexible topology configurations, makes wireless-based NoC a promising future MCSoC architecture. However, congestion occurrence in wireless routers reduces the benefit of high-speed wireless links and significantly increases the network latency. Therefore, in this paper, a congestion-aware platform, named CAP-W, is introduced for wireless-based NoC in order to reduce congestion in the network and especially over wireless routers. The triple-layer platform of CAP-W is composed of mapping, migration, and routing layers. In order to minimize the congestion probability, the mapping layer is responsible for selecting the suitable free core as the first candidate, finding the suitable first task to be mapped onto the selected core, and allocating other tasks with respect to contiguity. Considering dynamic variation of application behaviors, the migration layer modifies the primary task mapping to improve congestion situation. Furthermore, the routing layer balances utilization of wired and wireless networks by separating short-distance and long-distance communications. Experimental results show meaningful gain in congestion control of wireless-based NoC compared to state-of-the-art works.     

一种考虑节点拥塞情况的DTN概率路由算法*

容迟网络是一种新型网络,其概率路由算法根据历史相遇频率对相遇概率进行计算与更新,通过相遇概率判断是否转发报文。当节点缓存受限时,在网络中采用概率路由算法使得节点很容易发生拥塞,对报文的传送产生影响。为了减小拥塞对概率路由算法的影响,提出了一种考虑节点拥塞情况的概率路由算法,将节点相遇的概率和节点拥塞的情况综合起来,得到一个报文的递交概率,降低了由于拥塞对网络性能的影响,提高了报文的递交率,减小了报文在缓存中排队等候的时间。仿真结果表明,与传统的概率路由算法相比,在改进后的概率路由算法中报文递交率显著提高,平均延迟也在降低。     

A location routing protocol based on smart antennas for ad hoc networks

Ad hoc networks are a type of mobile networks that function without any fixed infrastructure. One of the weaknesses of ad hoc networks is that route between a source and a destination is likely to break during communication. Location-based routing algorithms are promising in reducing routing overhead in ad hoc networks. Existing location-based routing algorithms employ the Global Positioning System (GPS) as their location information provider, and synchronize information network-wide. Nonetheless, these protocols have some limitations because the use of GPS is not realistic in certain circumstances. Since smart antenna is able to infer direction and ranging information between pairs of ad hoc node, the obtained local position information can be used to improve routing mechanism. This work proposes a novel Location-Enhanced On-Demand (LEOD) routing protocol which is based on smart antenna technique. The LEOD protocol utilizes local position instead of global position to discover routes and make routing decision for the ad hoc network. Theoretical computation and simulation results show that data packet loss rate decreased significantly compared to other methods well-documented in the literature. In addition, this protocol reduces the network control overheads and the power consumption. It also improves network average throughput.     

基于小世界理论和QoS支持的DSR协议

动态源路由(DSR)协议是一种按需路由协议,存在着搜索路由时延较大,没有考虑节点能量等问题。针对DSR协议的这些不足,提出一种改进的DSR(IDSR)协议。IDSR协议首先预测即将发送数据的节点,然后应用小世界理论提前探测出该节点所在网络的拓扑结构。当预测准确时,可以省去路由发现过程,减少传输时延。在进行路由选择时,以时延和剩余能量作为最佳路由的选择标准,提供QoS支持。仿真实验表明:与DSR协议相比,IDSR协议降低了路由开销、平均时延和平均跳数,分组抵达率和网络生存周期也有一定程度提高。     

A routing-table-based adaptive and minimal routing scheme on network-on-chip architectures

In this paper, we present a routing algorithm that combines the shortest path routing and adaptive routing schemes for NoCs. In specific, routing follows the shortest path to ensure low latency and low energy consumption. This routing scheme requires routing information be stored in a series of routing tables created at the routers along the routing path from the source to the destination. To reduce the exploration space and timing cost for selecting the routing path, a routing list and routing table for each node are created off-line. Routing table is updated on-line to reflect the dynamic change of the network status to avoid network congestion. To alleviate the high hardware implementation cost associated with the routing tables, a method to help reduce the size of the routing tables is also introduced. Compared to the existing routing algorithms, the experimental results have confirmed that the proposed algorithm has better performance in terms of routing latency and power consumption.     

一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法

类脑处理器能够支持多种脉冲神经网络SNN的部署来完成多种任务。片上网络NoC能够用较少的资源和功耗解决片上复杂的互连通信问题。现有的类脑处理器多采用片上网络来连接多个神经元核,以支持神经元之间的通信。SNN在时间步内瞬时突发的通信会在短时间内产生大量的脉冲报文。在这种通信行为下,片上网络会在短时间内达到饱和,造成网络拥塞。片上网络中非拥塞感知路由算法会进一步加剧网络拥塞状态,如何在每一个时间步内有效处理这些数据包,从而降低网络延迟,提高吞吐率,成为了目前需要解决的问题。首先对SNN的瞬时猝发通信特性进行了分析;然后提出一种拥塞感知的哈密尔顿路径路由算法,以降低NoC平均延迟和提高吞吐率;最后,使用Verilog HDL实现该路由算法,并通过模拟仿真进行性能评估。在网络规模为16×16的2D Mesh结构的片上网络中,相对于没有拥塞感知的路由算法,在数量猝发模式和概率猝发模式下,所提出的拥塞感知路由算法的NoC平均延迟分别降低了13.9%和15.9%;吞吐率分别提高了21.6%和16.8%。     

基于拥塞控制的片上网络多播路由算法

为了满足片上网络日益丰富的应用要求,多播路由机制被应用到片上网络,以弥补传统单播通信方式的不足。以Mesh和Torus类的片上网络为例,分析了基于路径的3种多播路由算法(即XY路由、UpDown路由和SubPartition路由算法),并研究了相应的拥塞控制策略。通过模拟实验表明,多播较单播通信具有更小的平均传输延时和更高的网络吞吐量,且负载分配均匀;特别是SubPartition路由算法随着规模增大效果更加明显;提出的多播拥塞控制机制,能更有效地利用多播通信,提高片上网络的性能。     

无线传感器网络中一种拥塞感知的多路径流量分配算法

拥塞控制是无线传感器网络中的一个关键问题,拥塞不但增加丢包率,影响传输可靠性,而且会浪费宝贵的能量资源。本文从保证数据传输可靠性的多路径路由出发,提出了 一个拥塞感知的多路径流量分配算法COTA。COTA从全网出发,基于路径的启发式信息分配流量,避免给潜在的热点区域分配过多负载。此外,繁忙节点使用可靠性相关的报文文调度策略有效保证高可靠报文优先使用带宽。详细的模拟实验表明了COTA在可靠性、吞吐率等方面的优势。     

具有路由性能和蚁群优化的移动P2P路由策略*

目前的移动P2P网络路由策略不能较好适应网络拓扑结构的动态多变、网络和移动设备的资源有限等特点,以及不能较好解决路由建立和维护所带来的网络拥塞和资源消耗。针对上述问题,采用有限洪泛路由查询和移动agent路由查询相结合的策略,为每个移动节点提供丰富可靠、及时高效的路由信息。同时,使用改进的蚁群算法,综合考虑网络带宽、时延等多个路由性能指标,作为路由策略中路由选择机制。仿真研究证明,将所提出的理论与方法应用于移动P2P的路由选择和维护等问题,本算法在控制消息的开销、平均响应效率等方面具有良好的性能,对于网络     

一种线性时间复杂度的高效路由保护方法

如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。由于动态路由协议在应对网络中的故障时,在协议动态收敛的过程中将会有大量的报文被丢弃。因此,目前路由器厂商普遍采用路由保护方法来克服网络故障,在众多的路由保护方法中,DC（downstream criterion）规则是一种被普遍认可的方法。然而,已有的实现 DC规则算法的时间复杂度普遍较高,并且复杂度随着网络节点平均度的增加而迅速增加。为了应对上述问题,提出一种线性时间复杂度的高效路由保护方案ERPLR（an efficient routing protection method with linear time complexity）,该方法首先提出了备份下一跳计算规则,然后在已有最短路径树的基础上,根据备份下一跳计算规则为所有的源目的节点对计算备份下一跳。在计算备份下一跳的过程中,每个节点和其邻居最多被访问一次,因此ERPLR的时间复杂度为O（V+E）。实验结果表明,与已有的实现DC规则相比较,ERPLR在故障保护率和路径拉伸度两个度量指标结果相似的情况下,在真实网络拓扑和模拟拓扑中,ERPLR分别降低了大约74.93%和78.91%的计算开销,该方法可以极大地降低DC规则的计算开销。     

结合距离与队列积压的无线Mesh网络拥塞感知路由协议

针对无线Mesh网络中路由的拥塞问题,提出了一种结合距离与队列积压信息的拥塞感知路由协议(DR-CAR)。首先,结合链路质量源路由(LQSR)协议中的距离度量和E-Backpressure协议中的队列积压度量构建一种新的链路质量度量。然后,每个节点通过探测数据包来计算链路质量,并通过控制数据包和其邻居节点进行交互,以此来更新链路质量。最后,节点根据链路质量来选择下一跳节点,从而构建从源节点到目的节点之间的最佳路径。另外,在MAC层中为控制数据包分配最高的优先级,同时保证控制数据包的安全性。仿真实验表明,在不同的链路负载下,该协议在网络传输时延和网络吞吐量方面都具有优越的性能,具有可行性和有效性。     

一种负载均衡的移动Ad-hoc网络路由协议及改进

随着移动ad hoc网络负载的增加，现有路由协议的性能将急剧下降。为适应重负载网络，本文提出了一种带宽估算模型和负载平衡技术，并结合AODV（Ad hoc On-demand Distance Vector Routing）设计了新的路由协议。同时考虑到时廷因素，对新协议进一步改进。仿真表明，本文提出的协议可以提高分组传送率，降低平均端到端时延，并减少路由开销。     

神经网络预测Ad hoc节点流量的路由协议

提出了一种基于神经网络预测模型对网络流量负载进行预测的负载均衡协议NNP-LBRP（Load-Balanced Routing Protocol based on Neural Network Prediction model）,该协议利用RBF神经网络预测模型对Ad hoc网络中的节点流量负载进行预测,根据预测到的下一时刻的流量负载状况,在节点出现拥塞之前提前更换路径,避免中间节点出现拥塞,以此来提高网络的性能。协议中的流量值是以MAC层接口队列长度来衡量,负载均衡中的负载是流量负载。另外,协议在目的节点处采用了延迟应答策略,即在多路径中选择负载最轻的路径应答,对改善网络的性能也有一定作用。仿真结果与AODV路由协议进行比较,数据包投递率提高了约10%;平均端到端延时平均降低了27%;网络开销平均降低了26%。     

机会网络典型路由算法性能分析

通过对真实城市场景中行人移动行为的仿真,定量分析First Contact、Direct Delivery、Epidemic、Spray and Wait、Prophet和MaxProp6种机会网络典型路由算法在不同场景下的性能。在仿真过程中,以不同节点密度、不同节点移动模型和不同节点缓存大小设置多种场景,从传输能力、传输效率、网络资源开销和节点能耗4个方面对路由算法进行分析和比较。实验结果表明,节点移动模型、节点密度等因素会对路由算法产生显著影响,各路由算法在不同的场景下性能差距较大,每种算法都有其适用的特定场景。     

MRABM:一种新的基于mesh结构的多径路由算法

针对移动AdHoc网络提出了一种新的基于mesh结构的多径路由算法MRABM(MultipathRoutingAlgorithmBasedonMeshStructure),该算法采用目的节点建立和更新mesh结构的机制。该算法不仅为每个源节点、中间节点提供了到目的节点最优路径,而且为每个节点建立了到目的节点的多条路径。当节点移动造成链路断开时,该算法能避开断开的链路,迅速沿其它路径转发数据,不需要路由修复和路由重建过程,从而降低了丢包率和端到端的延时。对大流量数据的传输,该算法能有效利用网络资源,减少网络拥塞。因此该算法能很好地适应网络拓扑结构的动态变化。     

Making-a-stop: A new bufferless routing algorithm for on-chip network

In the deep submicron regime, the power and area consumed by router buffers in network-on-chip (NoC) have become a primary concern. With buffers elimination, bufferless routing is emerging as a promising solution to provide power-and-area efficiency for NoC. In this paper, we present a new bufferless routing algorithm that can be coupled with any topology. The proposed routing algorithm is based on the concept of making-a-stop (MaS), aiming to deadlock and livelock freedom in wormhole-switched NoC. Performance evaluation is carried out by using a flit-level, cycle-accurate network simulator under synthetic traffic scenarios. Simulation results indicate that the proposed routing algorithm yields an improvement over the recent bufferless routing algorithm in average latency, power consumption, and area overhead by up to 10%, 9%, and 80%, respectively.     

一种基于旁听的机会网络路由算法

针对基于议价博弈的概率路由算法存在消息传送成功率提升偏慢、开销大、节点无序情况下竞争信道引起碰撞以及节点在多邻居状态下存在冗余交互的问题,提出一种基于旁听的机会网络路由算法—ORON。ORON算法通过旁听邻居节点信息,设计博弈策略使激励相容,节点对邻居与自身的交易状态进行分析,选择最佳策略,使得网络性能得到提升。仿真验证了ORON算法设计的有效性,结果表明：与基于议价博弈的现有路由算法GSCP相比,ORON算法的吞吐量和消息传送成功率至少提高了6.72%,而控制开销和平均端到端消息时延则分别降低了20%和3.55%以上。