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.     

Hardware implementation of dynamic fuzzy logic based routing in Network-on-Chip

This paper presents the hardware implementation of a generic fuzzy logic-based adaptive routing scheme for both buffered and bufferless Networks-on-Chip (NoC). The routing scheme considers the dynamic traffic load and power consumption on neighboring router links to select the output port of an incoming flit. Specifically, fuzzy logic control is used to build a simple, generic, and efficient nonlinear control law that dynamically calculates the input link cost. Basing the link cost on traffic load and power consumption and not on empty buffer slots, makes the proposed algorithm applicable to both buffered and bufferless NoCs. Hardware implementation in ASIC and FPGA technologies demonstrate that the hardware area overhead imposed by the fuzzy control logic is from minimal to negligible for practical flit sizes and scales excellently with network size. Furthermore, since the fuzzy control logic is not in the router critical path, it imposes no additional latency. Finally, we demonstrate the efficiency of the proposed routing scheme through simulative evaluation against representative conventional counterparts.     

面向非全互连3D NoC的自适应单播路由算法

针对在非全互连三维片上网络（3D NoC）架构中的硅通孔（TSV）表只存储TSV地址信息,导致网络拥塞的问题,提出了记录表结构。该表不仅可以存储距离路由器最近的4个TSV地址,也可存储相应路由器输入缓存的占用和故障信息。在此基础上,又提出最短传输路径的自适应单播路由算法。首先,计算当前节点与目的节点的坐标确定数据包的传输方式;其次,检测传输路径是否故障,同时获取端口缓存占用信息;最后,确定最佳的传输端口,传输数据包到邻近路由器。两种网络规模下的实验结果表明,与Elevator-First算法相比,所提算法在平均延时和吞吐率性能指标上有明显的优势,且在网络故障率为50%时,Random和Shuffle流量模型下的丢包率分别为25.5%和29.5%。     

基于模糊逻辑的高速网络自适应拥塞控制研究

基于模糊逻辑 ,利用自适应拥塞控制机制来预测高速网络 (如Internet中 )的拥塞问题 .把路由器的缓冲系统看作一个非线性离散动态系统 ,利用基于模糊逻辑的控制器来预测源端发送速率的确切值以防止拥塞的发生 .通过对参数向量的调节来估计无法预测的和具有统计波动性的网络通信量 ,并利用Lyapunov分析方法来验证闭环系统的稳定性 .最后 ,以一个仿真例子说明了所提出方法的有效性 .     

Dynamic load balancing in IP-over-WDM optical burst switching networks

In this paper, we consider the problem of dynamic load balancing in wavelength division multiplexing (WDM)-based optical burst switching (OBS) networks. We propose a load balancing scheme based on adaptive alternate routing aimed at reducing burst loss. The key idea of adaptive alternate routing is to reduce network congestion by adaptively distributing the load between two pre-determined link-disjoint alternative paths based on the measurement of the impact of traffic load on each of them. We develop two alternative-path selection schemes to select link-disjoint alternative paths to be used by adaptive alternate routing. The path selection schemes differ in the way the cost of a path is defined and in the assumption made about the knowledge of the traffic demands. Through extensive simulation experiments for different traffic scenarios, we show that the proposed dynamic load balancing algorithm outperforms the shortest path routing and static alternate routing algorithms.     

Balancing buffer utilization in meshes using a "restricted area" concept

Adaptive routing and virtual channels are used to increase routing adaptivity in wormhole-routed two-dimensional meshes. But increasing channel buffer utilization without considering even distribution of the traffic loads tends to cause congestion in the most adaptive routing area. To avoid such traffic congestion, a concept of the restricted area is proposed. The proposed restricted area, defined to be a part of the network where message transmission concentrates, can be located following the region of adaptivity. By properly guiding message routing inside and outside the area, we are able to achieve more balanced buffer utilization and to reduce traffic congestion accordingly. The performance of several routing algorithms with or without using the restricted area is simulated and evaluated under various traffic loads and distribution patterns. The results indicate that routing algorithms with the restricted areas yield constantly larger throughput and smaller latency than routing algorithms without using the concept.     

Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network

In transportation networks with stochastic and dynamic travel times, park-and-ride decisions are often made adaptively considering the realized state of traffic. That is, users continue driving towards their destination if the congestion level is low, but may consider taking transit when the congestion level is high. This adaptive behavior determines whether and where people park-and-ride. We propose to use a Markov decision process to model the problem of commuters’ adaptive park-and-ride choice behavior in a transportation network with time-dependent and stochastic link travel times. The model evaluates a routing policy by minimizing the expected cost of travel that leverages the online information about the travel time on outgoing links in making park-and-ride decisions. We provide a case study of park-and-ride facilities located on freeway I-394 in Twin Cities, Minnesota. The results show a significant improvement in the travel time by the use of park-and-ride during congested conditions. It also reveals the time of departure, the state of the traffic, and the location from where park-and-ride becomes an attractive option to the commuters. Finally, we show the benefit of using online routing in comparison to an offline routing algorithm.

     

基于源区域路径选择的层次化片上网络路由算法

针对较大规模片上网络(NoC)远端节点和邻近节点之间的通信问题,提出一种基于区域划分的层次化簇状分层网（CHM）结构。在此基础上,针对中间节点拥塞严重导致网络性能降低的问题,提出一种基于源区域路径选择的自适应算法。该算法利用CHM结构区域特性将路由决策由源节点移至源区域,同时在原有底层和上层节点对的基础上增加自适应节点对,并增加该部分节点对路由选择性,从而缓解网络拥塞状况。仿真实验表明,与最短路径算法相比,在合成流量和局部化流量模式下,该算法下的CHM结构饱和注入率最多可分别提升约51%和31%,因此该算法可有效提升网络整体吞吐性能。     

MCAR: Non-local adaptive Network-on-Chip routing with message propagation of congestion information

Congestion occurs frequently in Networks-on-Chip (NoC) when the packet demands exceed the capacity of network resources. Non-local adaptive routing algorithms utilize the congestion information of both local and distant links to decide the output link selection, which can greatly improve the network performance. The existing non-local adaptive routing algorithms have two mechanisms to propagate the congestion information of distant links. One of mechanism is to increase additional wires/clusters. The other mechanism is to embed the propagated information in packet headers. This paper proposes a new non-local adaptive routing algorithm called MCAR. In MCAR, two special kinds of messages are used to propagate the congestion information of distant links across the network without introducing additional wires/clusters and leading to a better timeliness of congestion information. Moreover, MCAR efficiently utilizes the propagated information to decide the output link selection. Experimental results on both synthetic traffic patterns and application traces show that MCAR achieves better saturation throughput (5.84% on average) and smaller power consumption (7.58% on average) than a state-of-the-art adaptive routing algorithm.     

一种基于连接的增强拥塞控制机制

文中针对越来越多的网络应用不采用端拥塞控制机制而导致非公平占用网络带宽问题,介绍了在路由器内部实现基于连接调度的增强拥塞控制方法。路由器使用公平排队调度算法代替传统的先来服务调度算法,可隔离和保护基于漏桶控制的连接。但采用基于窗口反馈拥塞控制机制ＴＣＰ连接会对数据包丢失敏感,路由器使用公平排队调度算法还需要结合相应的缓冲管理方法,才能保证ＴＣＰ连接获取公平的吞吐量。文中还讨论了基于连接的排队数据包     

Adaptive load balancing in learning-based approaches for many-core embedded systems

Adaptive routing algorithms improve network performance by distributing traffic over the whole network. However, they require congestion information to facilitate load balancing. To provide local and global congestion information, we propose a learning method based on dual reinforcement learning approach. This information can be dynamically updated according to the changing traffic condition in the network by propagating data and learning packets. We utilize a congestion detection method which updates the learning rate according to the congestion level. This method calculates the average number of free buffer slots in each switch at specific time intervals and compares it with maximum and minimum values. Based on the comparison result, the learning rate sets to a value between 0 and 1. If a switch gets congested, the learning rate is set to a high value, meaning that the global information is more important than local. In contrast, local is more emphasized than global information in non-congested switches. Results show that the proposed approach achieves a significant performance improvement over the traditional Q-routing, DRQ-routing, DBAR and Dynamic XY algorithms.     

Traffic modeling, prediction, and congestion control for high-speednetworks: a fuzzy AR approach

In this study, a fuzzy autoregressive (fuzzy-AR) model is proposed to describe the traffic characteristics of high-speed networks. The fuzzy-AR model approximates a nonlinear time-variant process with a combination of several linear local AR processes using a fuzzy clustering method. We propose that the use of this fuzzy-AR model has greater potential for congestion control of packet network traffic. The parameter estimation problem in fuzzy-AR modeling is treated by a clustering algorithm developed from actual traffic data in high-speed networks. Based on the adaptive AR-prediction model and queueing theory, a simple congestion control scheme is proposed to provide an efficient traffic management for high-speed networks. Finally, using the actual Ethernet-LAN packet traffic data, several examples are given to demonstrate the validity of this proposed method for high-speed network traffic control     

基于模糊参考模型机制的网络自适应拥塞控制

在高速通信网络的发展过程中,业务流呈现出的突发性和多样性为提高网络服务质量制造了更多的困难。该文提出的网络自适应拥塞控制方法以模糊参考模型机制的核心来提高主动队列管理算法在突发性网络状况中的适应能力,以2条信息通道分别实现主动队列管理的控制与学习功能,并结合参考模型机制实现模糊反向推理算法,针对网络突发性状况自适应调整主控制通道的控制行为。仿真研究表明,该控制方法提高了拥塞控制机制的自适应性能,并在自适应性能和实时性能上获得了较好的平衡。     

An intelligent usage parameter controller based on dynamic rate leaky bucket for ATM networks

In this paper we present a high performance intelligent traffic controller based on dynamic rate leaky bucket algorithm. In our proposed model, by using a fuzzy controller, the leaky rate is dynamically tuned according to the state of traffic source. Control actions are taken based on real time estimation of actual mean cell rate. Simulation results show that the proposed traffic controller has a high selectivity, good dynamic behavior and has also a null false alarm probability. To achieve the benefits of statistical multiplexing gain, the proposed traffic controller employs a network congestion feedback to take a decision to discard or tag the input violating cells. It is seen that the proposed fuzzy traffic controller protects the QoS of well-behavior connections far better than any traditional traffic controller does.     

DTBR: A dynamic thermal-balance routing algorithm for Network-on-Chip

Network-on-Chip (NoC) replaces the traditional bus-based architecture to become the mainstream design methodology for future complex System-on-Chip (SoC). It introduces the principles of packet switching and interconnection network into SoC design, and achieves much better performance for its high bandwidth, scalability, reliability, etc. However, thermal problem, such as regional temperature differential and hotspot, is still one of the main designing constraints. This paper proposes a dynamic thermal-balance routing (DTBR) algorithm for Network-on-Chip, which can solve both of the two thermal problems. DTBR is a minimal adaptive routing algorithm based on an architectural thermal model. An efficient thermal-aware router is designed to implement the DTBR algorithm. According to the simulation results, the proposed DTBR algorithm can make the network thermal distribution more uniform and hotspot temperature is cut down about 20% in different traffic patterns. Moreover, DTBR will bring a profit for the performance of packet delay and network throughput compared with other routing algorithms.     

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.     

一种基于模糊理论的拥塞控制算法

路由器在处理拥塞时,通常把网络载荷分为正常、拥塞避免和拥塞三个阶段,并在拥塞避免阶段开始采取行动。由于各个阶段的描述存在一定的不确定性,因此一些传统的方法很难取得更好的效果。论文则充分利用模糊理论在处理不确定性问题上的优越性,采取整体和局部相结合的方法,从而在保证各TCP连接吞吐量的公平性方面,取得了比传统的方法更好的效果。实验仿真结果表明,模糊算法较传统方法更为合理,从而更好地改进了路由器的拥塞控制性能。     

直线引导的Torus结构路由算法

为了提高片上网络在Torus拓扑结构下的路由通信效率,提出了一种基于直线引导思想的路由算法Tline。该路由算法将Torus拓扑结构的片上网络拓展为类似Mesh结构的坐标平面,以数据包的源节点和目的节点构成的直线为路由转发方向,并根据周围邻近节点的拥塞状况选择传输路径方向实现部分自适应路由。实验结果表明,与XY、OE路由算法相比,在热点流量模式下Tline路由算法具有较好的路由性能,且平均能耗降低约8%。     

An integrated congestion control mechanism for optimized performance using two-step rate controller in optical burst switching networks

Optical burst switching (OBS) is a promising solution to implement the optical internet backbone. However, the lack of adequate congestion-control mechanisms may result in high burst loss. Schemes such as fiber delay line (FDL), wavelength conversion, and deflection routing to reduce burst collision are unable to prevent the network congestion effectively. To address this problem, we propose and investigate a global solution, called Integrated Congestion-Control Mechanism (ICCM), for OBS networks. ICCM, which combines congestion avoidance with recovery mechanism, restricts the amount of burst flows entering the network according to the feedback information from core routers to edge routers to prevent network congestion. Also, a flow-policing scheme is proposed to intentionally drop the overloaded traffic with a certain probability at a core router to support fairness among flows. Moreover, the transmission rate of each flow is controlled to achieve optimized performance such as maximizing throughput or minimizing loss probability using two-step rate controller at the edge router. Simulation results show that ICCM effectively eliminates congestion within the network and that, when combined with a flow-policing mechanism, the fairness for competing flows can be supported while maintaining effective network performance.     

Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees

Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Lately there has been a tremendous increase in management traffic due to the growing complexity and size of the data networks and the services provisioned on them. Traffic engineering for management flows is essential for the smooth functioning of these networks to avoid congestion, which can result in loss of critical data such as billing records, network alarms, etc. As is the case with most intra-domain routing protocols, the management flows in many of these networks are routed on shortest paths connecting the NOC with the service provider’s POPs (points of presence). This collection of paths thus forms a “confluent” tree rooted at the gateway router connected to the NOC. The links close to the gateway router may form a bottleneck in this tree resulting in congestion. Typically this congestion is alleviated by adding layer two tunnels (virtual links) that offload the traffic from some links of this tree by routing it directly to the gateway router. The traffic engineering problem is then to minimize the number of virtual links needed for alleviating congestion. In this paper we formulate a traffic engineering problem motivated by the above mentioned applications. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which the underlying network is a tree, we design efficient algorithms. In particular, we design fully polynomial-time approximate schemes (FPTAS) for different variants of this problem on trees. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general (non-tree) service provider network topologies.