Most NOC implementations are based on lossless networks, consisting of many small, buffered switch modules (SMs, or routers). Having buffers inside each SM avoids packet loss in the case of contention but introduces extra queuing delays. Small buffer limitation degrades the system performance in terms of latency and throughput when traffic load is heavy, and complicates the design of congestion control mechanisms.

Congestion can occur at the SMs, so called internal/link congestion, or at overloaded destinations, so called hotspot. Poor routing in the 2D Mesh and torus networks can result in link congestion. Fig. 1(a) illustrates the problem of link congestion in 2D Mesh. Because of the low bisection bandwidth and poor routing, link congestion occurs and degrades the network performance. Several efforts have shown that adaptive routing alleviates link congestion by steering traffic away from the congested links. However, adaptive routing would exhaust even more links in the network when a hotspot occurs as shown in Fig. 1(b). On the other hand, the high bisection bandwidth and symmetric nature of Clos NOC (CNOC, see Fig. 1(c)) allows traffic to be evenly distributed among the SMs in the central stage. With a good load-balanced routing algorithm, CNOC should experience less link congestion than the above mentioned networks. However, the end-point congestion or hotspot problem still exists.

As soon as a hotspot occurs, it starts pushing back the traffic from upstream SMs, resulting in head-of-line (HOL) blocking in the SMs. This phenomenon is called saturation-tree congestion, as shown in Fig. 1(c), where starting from the congestion point (e.g., the hotspot PE in Fig. 1(c)), all traffic flows destined for the choke point form a tree and cannot move forward. Packets destined for low loaded destinations could also be blocked by the jammed traffic in the internal SMs and suffer from high queuing delay. Our performance study shows that CNOC's throughput degrades significantly under hotspot traffic as shown in Fig. 2. 

Fig. 1. Congestion problems in 2D Mesh and CNOC. (a) Link Congestion in 2D Mesh. PEs connected to nodes 1, 2 and 3 send traffic to the PE connected to node B using the X-Y routing. Node X is congested due to link congestion before the traffic arrives at the destination. (b) Hotspot congestion in 2D Mesh. When using adaptive routing by steering traffic based on the possible dashed lines, multiple nodes (named X) will be congested and the problem gets worse. (c) Hotspot congestion in CNOC. The high bisection bandwidth and load-balanced routing alleviate link congestion in CNOC; however hotspot traffic introduces the saturation-tree problem.

Fig. 2. CNOC average latency in clock cycles under different traffic patterns. 
 

Hotspot congestion control is one of the most challenging issues when designing a high-throughput low-latency NOC. How to detect the occurrence(s) of hotspots and notify all sources to regulate their traffic to the hotspot(s) can be quite complex because of the potentially high volume of information to be collected and the non-negligible latency between the detection point of congestion and the sources. In this project, we propose an effective end-to-end flow control scheme, called HOPE (HOtspot PrEvention), to resolve the hotspot congestion problem for both CNOC and 2D Mesh. Specifically, HOPE regulates the injected traffic rate proactively by estimating the number of packets inside the network destined for each destination and applying a simple stop-and-go protocol to prevent hotspot traffic from jamming the internal links of the network. We evaluate HOPE's overall performance and its fairness and scalability. Extensive simulation results based on different traffic patterns confirm that HOPE can effectively improve system performance by fairly regulating hotspot flows. Our hardware analysis shows that HOPE has a very small logic overhead.
More details about the work can be found in [1][3].

Reference

[1] Najla Alfaraj, Junjie Zhang, Yang Xu, H. Jonathan Chao, "HOPE: Hotspot congestion control for Clos network on chip", in the Proceedings of 2011 Fifth ACM/IEEE International Symposium on Networks on Chip (NOCS), Pittsburg, May 2011.
[2] Y. H. Kao and H. J. Chao, "BLOCON: A Bufferless Photonic Clos Network-on-Chip Architectures", in the Proceedings of 2011 Fifth ACM/IEEE International Symposium on Networks-on-Chip, Pittsburg, May 2011
[3] Y. H. Kao, N. Alfaraj, M. Yang, and H. J. Chao, "Design of High-Radix Clos Network on Chip", in the Proceedings of 2010 ACM/IEEE International Symposium on Networks-on-Chip, Grenoble, France, May 2010