An Evaluation of Routing Algorithms in Traffic Engineering and Quality of Service Provision of Network on Chips ()
1. Introduction
As the number of cores that are integrated into NoC (Network on Chip) systems is steadily increasing, the role they play in communication systems is becoming increasingly important. NoC has been characterized as the most sustainable solution in the communications field [1]. Nowadays application traffic, running in such multi core environments requires more and more bandwidth, and hence, NoC architectures should be properly designed so as to provide efficient traffic engineering, as well as QoS support. Routing algorithm choice in conjunction with other parameters such as network size and topology, traffic features (time and spatial distribution), as well as packet injection rate (PIR), packet size, and buffering capability, are all equivalently critical for designing a robust NoC architecture, on the grounds of traffic engineering and QoS provision.
This paper is an attempt to thoroughly evaluate routing algorithm selection impact on NoC performance and its major QoS parameters, such as End-to-End Delay (EED) and throughput, in conjunction with all aforementioned parameters, varying either individually, or as a set, thus exhausting all possible combinations and optimizing a proper routing algorithm selection for NoC architectures. As known, the network delay is the time in clock cycle that passes between the incidences of a header fit injected into the network at the source node and the incidences of a tail fit arrival at the destination node, while the total number of fits received at the destination node in a clock cycle describes the throughput.
Our paper is structured as follows: In Section 2, there is some background information and a brief overall description of related parameters on traffic engineering in NoCs. In Section 3, there is an updated literature review on research related works and critical traffic engineering issues and parameters that they haven’t taken into consideration, which is the objective aim of this work that is implemented via numerical simulation and described in Section 4: a thorough evaluation of routing algorithm selection impact which takes into consideration all critical parameters for designing a robust NoC architecture, on the grounds of traffic engineering and QoS provision, varying either individually, or as a set, thus exhausting all possible combinations, and making compact decisions on proper routing algorithm selection in NoC architectures. This is done via implementation of 4 routing evaluation traffic scenarios. Specifically, at first, a routing algorithm evaluation is examined on a basis of varying traffic spatial distribution profiles, while at a second stage, the routing evaluation is tested for more realistic Hotspot traffic scenarios. Next, the evaluation is tested for scaling up network dimensions. Last, we evaluate routing algorithm impact, varying a four parameter set (buffer size, packet injection rate, packet size and network size). In this last measurement, at a second stage, we evaluate routing algorithm impact for two traffic scenarios, a worst case and a normal case scenario, based on the four-parameter set, on the grounds of average delay and throughput. All comparison evaluations and the results have been obtained via numerical simulation with Noxim simulator, and included in Section 4 of this paper, while in the last two sections, there is a discussion on the critical points along with a final conclusion of the outcome of this of routing evaluation in NoCs.
2. Background
Normally, a router element within a NoC system is modeled by a routing algorithm, for computing a path between input and output ports of the switching matrix, an arbiter, for granting access to a given port when multiple input requests arrive in parallel, buffers, for temporal data storage, and a selection function for selecting the appropriate output port, considering the status of the output channels. In general, routing algorithms in NoC systems are divided into two major classes, adaptive and deterministic [2]. As concerns deterministic routing or else named oblivious routing, the path is completely determined by the source and the destination address. In adaptive routing, the selected path depends on dynamic network conditions such as network load, traffic condition and information about available output channel. Hence, deterministic routing main advantage is simplicity while for the cognition of adaptive routing, extra computation logic and overheads and more complicated designs are required, in order to decide for an optimized path. There are many routing algorithms representative on either of the two routing classes, such as the XY deterministic algorithm [3], the odd even (OE) adaptive algorithm, the West First, Norst Last και Negative First, as partially adaptive algorithms [4], and hybrid ones, such as DyAD (Dynamic Adaptive Deterministic) algorithm [5], which is switched on either deterministic or adaptive mode, depending on the network congestion status.
When considering a 2D mesh NoC layout, a packet can follow four directions (East, West, North, and South) and eight distinct turns, as shown in Figure 1, where deadlock or livelock may appear [4]. A deadlock is a cyclic dependency among nodes requiring access to a set of resources, so that no forward progress can be made, no matter what sequence of events happens, while a livelock refers to packets circulating the network without ever making any progress towards their destination. A deadlock may cause the packets to wait for a cycle. In order for a routing algorithm to be deadlock free, it needs to prohibit at least one turn in each of the possible routing cycles, while at the same time, it should not prohibit more turns than necessary. In XY routing, packets are first routed in x or horizontal direction to the correct column and then in y or vertical direction to the destination, according to the source and destination xy-coordinates. If some
network hop within the selected path, is in use by another packet, the flit remains blocked in the switch until the path is released. In the West First algorithm, if x (destination) ≤ x (source), packets are routed deterministically, as in the XY algorithm, else if x (destination) > x (source), packets can be routed adaptively in East, North or South directions. In the North Last algorithm, if y (destination) ≤ y (source), packets are routed deterministically, else if y (destination) > y (source), packets can be routed adaptively in West, East, or South directions. In the Negative First algorithm, packets are routed first in negative directions. If (x (destination) ≤ x (source) and y (destination) ≥ y (source), or (x (destination) ≥ x (source) and y (destination) ≤ y (source), packets are deterministically routed, else they are routed adaptively. Odd Even is an adaptive routing algorithm which is based on odd even turn model, and imposes some restrictions, for avoiding and preventing from deadlock appearance. Odd even turn model facilitates deadlock-free routing in 2D mesh NoC layouts. Last, a DyAD routing algorithm works in a deterministic mode, when the network is not congested, thus leading to low latency routing, and be switched to the adaptive mode, when the network becomes congested, thus avoiding the congested links, and leading to higher network throughputs.
The choice of the right topology in conjunction with the proper routing algorithm selection is also critical for the performance of a NoC architecture. There are popular topologies for on-chip technologies such as shared-bus, crossbar, butterfly fat-tree, ring, torus and 2D-mesh, with the latter to be most commonly used for such NoC performance investigations. Traffic features, such as spatial and time distribution for a given NoC topology (e.g. 2D mesh), have also a great impact in NoC performance. Most popular traffic time distributions for a given PIR, are considered the memory-less Poisson distribution, and the bursty distribution which is more realistic to IP bursty data traffic, or even Pareto distribution [6].
As far as concerns spatial traffic distribution within NoCs, there are several popular traffic types such as uniform traffic, first and second transpose traffic, complement traffic, bit reversal traffic, butterfly traffic, and shuffle traffic distribution. In uniform traffic, which is a commonly used benchmark for NoC routing studies, each node sends messages to other nodes with an equal probability, while in transpose traffic each node sends messages only to a destination with the upper and lower halves of its own address transposed, according to a transpose matrix. In complement traffic, each node sends messages only to a node with one’s complement of its own address, while in bit reversal traffic, each node sends only to a node, whose address is bit reversal of the sender’s address. There is also a more realistic traffic type called Hotspot. According to this type of traffic, each node sends messages to other nodes with an equal probability except for a specific node the Hotspot node, which receives messages with a greater probability. Therefore, the Hotspot node would perfectly represent a very busy node. There can be more than one nodes that are designated as the Hotspot nodes, which receive Hotspot traffic in addition to the regular traffic.
Wormhole (WH) switching has been widely adopted for on-chip routers and typical NoC applications. According to the WH switching, the packet is divided into fixed size flits (Flow Control Unit). Header flit includes all control data, and be transmitted in prior of all the flit of the message, in wormhole switching. Moreover, as has been mentioned, a NoC router functionality also includes a selection function for selecting the appropriate output port from a given set, considering the status of the output channels. Selection strategies could be either random, when there is an equal probability for selecting each output port, or buffer-level based when selecting the output whose connected input port has the minimum occupied buffer [7]. Neighbor-on-Path (NoP) [8], is also a popular smart selection strategy for adaptive routing in NoCs, which aims to choose the channel for the packet to be routed to its destination, along a path with minimum congestion. In doing so, for each candidate output channel, the current node investigates the availability of the input buffers of NoP nodes. Then by using a score selection classification, the score of each candidate destination is increased for each NoP with available free input buffer space, and the channel with the higher score is finally selected.
Another critical factor for router element design, is considered its buffer size in conjunction with packet size, which are directly related to NoC performance parameters, as latency and throughput. Normally, each packet will enter the buffer through the input port when arriving at the router and latency will be increasing, as long as the incoming packets will exceed the buffer capacity. Virtual Channel (VC) [9], with inherent flow control mechanisms have been employed to improve NoC latency and throughput, by choosing an alternative path, without passing through the congested path and thus avoiding deadlock. However, it is characterized as a power hungry and computation inefficient solution, when applied for a large number of VCs.
3. Related Works
Many research works in the recent past, have attempted similar evaluation comparisons, none of them however has considered such a combined impact of all these aforementioned critical parameters together, in qualifying QoS in 2D NoC systems. Specifically in [10], a similar evaluation has been attempted but without considering a wide variety of traffic profiles, or buffering capability, in [11] the evaluation is restricted and focused mainly in selection strategy, while in [12] is focused in varying only network size. In [13], the evaluation is strictly based on uniform versus Hotspot traffic for two specific NoC topologies, while in [14], the evaluation is restricted in varying PIR. Similar works have been focused exclusively on specific NoC topologies as well [15] [16]. In [17], NoC behavior is examined under three communications processes namely TCP, VBR and CBR for various packet sizes. In [18] [19] [20] and [21], new customized routing schemes are compared against classic deterministic and adaptive ones, as concerns NoC delay and throughput and fault management accordingly.
4. Numerical Results
4.1. Numerical Method Description
This paper proposes an evaluation of routing algorithm impact on traffic engineering and performance specified via QoS metrics, such as average delays and throughputs in 2D NoCs, under different values of critical importance parameters, as spatial and time distribution traffic profiles, or more realistic Hotspot traffic profiles, while varying buffer size, PIR, packet size and network size, either individually or as a set. Noxim simulator [22], which is a flit-level cycle-accurate NoC simulator, is used to observe the performance of each routing algorithm. We evaluate a NoC model of mesh 8 × 8 structures, which is the most commonly used model nowadays, except for cases that network mesh size is required to vary, while examining routing algorithm evaluation. In this simulation, each source generates 8-flit packets and injects them into the network, in intervals determined by Poisson distribution. Other traffic time interval distribution types used and supported by Noxim, are the bursty distribution, which is more realistic to IP bursty data traffic, and the Pareto distribution. Packet size may be varied as well, when required in some measurement sets for evaluating routing algorithms. For each simulation measurement, WH switching has been adopted, which is a commonly used technique. Each input port of the router has a 4-flit sized FIFO buffer. Buffer size may be also varied in some measurement sets. Normally, each simulation runs 20,000 cycles, after 1000 cycles of warm-up period, in order to allow the system to stabilize. The simulation for each configuration is 10 times iterated so as to improve accuracy, and the mean value is taken into consideration.
We have evaluated six different routing algorithms, namely XY deterministic algorithm, the Odd Even adaptive algorithm, the West First, North Last and Negative First, as partially adaptive algorithms, and hybrid DyAD algorithm, that are implemented and supported by the Noxim simulator. To evaluate the routing algorithms we have considered 4 simulation scenarios, in which, the following parameters vary: 1) traffic spatial distribution; 2) Hotspot generated traffic; 3) network mesh size; and 4) a four parameter set (buffer size, packet, injection rate, packet size and network size), while at a later evaluation stage, a worst-case and a normal case traffic scenario are compared, based on this parameter set. The average delay and the throughput under a long range of PIRs, is considered, as the performance index for the simulations.
4.2. Routing Evaluation Scenarios
Scenario 1: Routing algorithm evaluation for different traffic patterns. In this scenario a routing algorithm evaluation is achieved, for various spatial distribution traffic patterns. Specifically, the impact of routing algorithm selection on NoC performance and QoS is examined, on the grounds of average delay and throughput, for a wide range of PIRs (0.05 up to 0.5). A different spatial traffic pattern is selected each time for the routing algorithms evaluation, among 3 different characteristic types, as random, shuffle, and butterfly traffic distributions. The time distribution for all traffic patterns is Poisson, and the router selection strategy is random.
XY routing seems to perform better than the all the other routing algorithms in terms of throughput, under random traffic load, with relatively lower delays as well, as seen in Figure 2(b) and Figure 2(a) respectively. XY algorithm also seems to perform better than the other routing algorithms under shuffle traffic distribution, with the DyAD having the second best performance, and the West First to follow up, among all the rest algorithms, which have the same performance, as concerns throughput metric (Figure 3(b)). All routing algorithms seem to behave the same more or less, in terms of delay, for shuffle traffic pattern (Figure 3(a)). As far as concerns butterfly traffic pattern, all routing algorithms seem to have the same throughput for all PIR range, with the XY to have lower delays at low PIRs, as seen in Figure 4(b) and Figure 4(a) respectively.
Scenario 2: Routing algorithm evaluation for Hotspot traffic pattern. As the traffic distributions of the previous scenarios is quite deterministic and hence unrealistic, we achieve in this scenario, to employ a more realistic traffic pattern, such as Hotspot traffic. Normally, more realistic traffic exhibits a non-uniform communication pattern with higher probability of increase traffic locality, where traffic load of the sources is the same, but the probability that a module will send a packet to one of its adjacent neighbors is greater of the
![]()
(a) ![]()
(b)
Figure 2. (a) Routing evaluation of network average delay for random traffic; (b) Routing evaluation of network throughput for random traffic.
![]()
(a)![]()
(b)
Figure 3. (a) Routing evaluation of network average delay for shuffle traffic; (b) Routing evaluation of network throughput for shuffle traffic.
![]()
(a)![]()
(b)
Figure 4. (a) Routing evaluation of network average delay for butterfly traffic; (b) Routing evaluation of network throughput for butterfly traffic.
probability to send the packet to any other node. According to Hotspot traffic, each node sends messages to other nodes with an equal probability except for the Hotspot node, which receives messages with a greater probability. The additional message percentage that a Hotspot node receives, against the other non Hotspot nodes, is the x-axis parameter varying in this measurement set. Again, the time distribution for this traffic patterns is Poisson, and the router selection strategy is random, applied on an 8 × 8 mesh network.
All routing algorithms seem to behave the same more or less, in terms of throughput (Figure 5(b)). XY routing seems to perform better than the other routing algorithms in terms of delay, with relatively lower delays especially as PIR increases. DyAD is having the second best performance in delays, with the North Last to follow up, among the rest of the others, which have the same delay performance (Figure 5(a)).
Scenario 3: Routing algorithm evaluation for scaling up network size As NoC cores are continuously increasing and becoming denser, scalability is considered as a critical figure of merit for studying NoC system performance. Hence, in this scenario, a routing algorithm evaluation is achieved when scaling up network mesh size, from a small 4 × 4 to a regular 8 × 8 mesh size. In this scenario, random traffic type is considered, with Poisson time intervals for packet injection, and the router selection strategy is random, for 3 discrete PIRs.
As far as concerns 4 × 4 mesh size case, XY routing algorithm has a slightly lower delay than all the other algorithms, especially for low PIRs, while for
![]()
(a)![]()
(b)
Figure 5. (a) Routing evaluation of network average delay for Hotspot traffic; (b) Routing evaluation of network throughput for Hotspot traffic.
greater PIRs, the delay performance is more or less the same for all routing schemes, as seen in Figure 6(a). XY routing algorithm has also a better throughput for all PIRs against the other algorithms, as also seen in Figure 6(b).
As far as concerns 8 × 8 mesh size case, delay performance superiority of XY tends to decrease, while at the same time, all algorithms have the same increased delay performance for all PIRs (Figure 7(a)). On the other hand, the throughput superiority of XY routing scheme is becoming even better and more crystal clear, against all the other routing schemes, which all have almost the same throughput for all PIRs (Figure 7(b)).
Scenario 4a: QoS evaluation for combined parameter set variation. It is of great importance for network performance and QoS potential, to consider the variation of more than one parameter at a time, rather than examining individually, parameter impacts. Hence in this scenario, the two basic metrics of QoS for NoC system, the delay and throughput, are evaluated for a given deterministic routing algorithm, under a combined parameter variation, which are all critical for network traffic engineering, such as the buffer size, the PIR, the packet size, and the network mesh size. In such a case, a worst scenario is considered as a reference starting point for varying this parameter set. Specifically, we initially consider a rather small 4 × 4 mesh network, with the minimum buffer depth (only 2 flits), and huge size packets (64 flits) injected with a high PIR (0.5), as a worst case to begin with. Then, we gradually attempt to improve this NoC layout, by improving the values of all these four critical parameters together, via
![]()
(a)![]()
(b)
Figure 6. (a) Routing evaluation of network average delay for 4 × 4 mesh size; (b) Routing evaluation of network throughput for 4 × 4 mesh size.
![]()
(a)![]()
(b)
Figure 7. (a) Routing evaluation of network average delay for 8 × 8 mesh size; (b) Routing evaluation of network throughput for 8 × 8 mesh size.
checking QoS and network performance in terms of delay and throughput. In doing so, the improvement of these parameters would mean that some of them would have to be increased, such as the buffer and the network size, while others would have to be decreased, such as the PIR and the packet size, as can be seen in the x-axis of Figure 8(a) and Figure 8(b).
It can be seen that the improvement of two of the four parameters, namely the decrease of the PIR and the packet size, lead to lower delays for the network, while the other two parameters do not seem to affect NoC delay (Figure 8(a)). As far as concerns network throughput, as expected, network size increase, would lead to better NoC performances, as seen in Figure 8(b). Slight NoC performance improvement can be also seen, via increasing buffer size and decreasing packet size, which is a reasonable system behavior as well.
Scenario 4b: Routing evaluation for combined parameter set variation scenarios. As concerns NoC performance, in this numerical measurement, a routing algorithm evaluation is examined, for two discrete traffic scenarios, the worst case scenario of the previous measurement set, and a normal case traffic scenario of a regular 8 × 8 mesh NoC, with a buffer depth of 4 flits, and 8-flit size packets to be injected with a PIR of 0.1.
For the worst case scenario, it seems that routing algorithm selection has no impact at all in terms of NoC delay, while for the normal scenario, XY deterministic algorithm seem to have a much lower delay than the other algorithms, as seen in Figure 9(a). As far as concerns network throughput, it seems that XY deterministic algorithm has a better performance for the worst, as well as for the normal scenario, while the other algorithms have more or less all, the same behavior with lower throughputs (Figure 9(b)).
![]()
(a)![]()
(b)
Figure 8. (a) Network average delay for a combined parameter set variation; (b) Network throughput for a combined parameter set variation.
![]()
(a)![]()
(b)
Figure 9. (a) Routing evaluation of network average delay for worst and regular traffic scenario; (b) Routing evaluation of network throughput for worst and regular traffic scenario.
5. Discussion
In the first scenario, where routing algorithm evaluation is tested for various spatial distribution traffic patterns, as seen, XY routing algorithm performs better in terms of throughput, than the other routing algorithms under random traffic load, and with relatively lower delays as well. XY algorithm also performs better than all the other routing algorithms, under shuffle traffic distribution, with the DyAD having the second best performance, compared to the others, which have all quite the same throughput performance and delay. As concerns random traffic patterns, XY algorithm superiority in both terms of delay and throughput, is quite reasonable, as due to its deterministic nature, it exploits global long term information traffic, which takes advantage of the evenness of such traffic types [23]. The adaptive algorithms, on the other hand, select channels based on local short term information, which in case of a local congestion event, it would result in increased, locally at first, contention, which in turn would spread through neighbor nodes, and consequently would decrease performance as well, especially at higher PIRs [23]. Hybrid DyAD algorithm performs better than the other adaptive algorithms, as long as it operates mostly as a deterministic algorithm.
As concerns routing algorithm evaluation for Hotspot traffic scenario, all routing algorithms seem to behave the same more or less, in terms of throughput, with XY algorithm to perform better than the others in terms of delay, especially as PIR increases. DyAD is having the second best performance in delays, among the others which all have the same delay performance. Theoretically one would expect that adaptive routing algorithms would outperform XY routing for non-uniform traffic patterns. As far as concerns Hotspot traffic, unfortunately this is not what happens. It is quite reasonable however, as for Hotspot nodes, especially for those with high message percentages, a local congestion event, among a Hotspot node, and its rapid expansion through all of its neighbors, is very possible to occur. As adaptive algorithms are made for selecting paths based on short term information, it is not very likely to avoid such a local congestion event, that would result in long delays. Hence, a Hotspot node prediction mechanism would be beneficial for such cases of adopting adaptive routing schemes, in order to avoid local congestions and boost network performance. Again, DyAD has the second best performance, as it operates partially as deterministic algorithm.
As concerns routing algorithm impact on network scalability, for low network mesh sizes, XY routing algorithm has more or less, the same delay with all the other algorithms, especially as PIR is increasing, which it is fairly reasonable, as for such small size mesh layouts, the increased PIR does not leave much chance for any routing algorithm to overcome congestion matters, no matter of its buffering capability. As network mesh size increases and so does the delay, again, more or less, all algorithms have the same increased delay performance for all PIRs. It is also reasonable, as scaling up network size, it is less possible for a congestion event to occur, and thus the delays, although being increased according to network size increase, would be the same for either applying deterministic or adaptive algorithms. On the other hand, the XY routing throughput superiority, against all the other routing schemes is also reasonable, as by increasing number of nodes and thus expanding network size, there are much more alternative routing paths, even for a simple deterministic routing schemes to follow, with no restrictions. Hence in such cases, there is no need for applying complicated and computation intensive adaptive routing schemes.
In the scenario of testing the mutual impact of more than one critical parameters on NoC system throughput and delay, such as the buffer size, the PIR, the packet size and the mesh size, it can be seen that the decrease of the PIR and the packet size, has an impact on lower delays, while the other two parameters do not seem to affect NoC delay. It is quite reasonable, as in such cases of low PIR and packet sizes, the network would have adequate resources for efficiently managing such less load, thus eliminating any event of awaiting packets that would lead to increased delays. As concerns network throughput, as expected and deduced from the previous scalability measurement set, a network size increase would lead to better NoC performances. A slight NoC performance improvement can be also seen via increasing buffer size and decreasing packet size, which is a reasonable system behavior as well.
The last numerical measurement, concerns routing algorithm evaluation for two discrete traffic scenarios, the worst case and normal case traffic scenarios. Apparently for the former, it seems that routing algorithm selection has no impact at all in terms of NoC delay, which is expected, as for such small size mesh layouts, with high PIR long packets and minimum depth buffer, that tight combination would not leave much chance for any routing algorithm to overcome congestion matters. As far as concerns network throughput, it seems that XY deterministic algorithm appears to have a better performance for both scenarios, due to its simplicity and long term global traffic information retrieval, while the other more complicated and intensive routing adaptive algorithms have more or less the same behavior with lower throughputs.
6. Conclusion
In this paper, a thorough investigation of evaluating routing algorithm selection impact on NoC traffic performance and QoS potentials, has been attempted, via numerical simulation, while varying critical traffic parameters, either individually, or as a set, thus exhausting all possible combinations, and optimizing a proper global routing algorithm selection for applying in NoC architectures. It has been shown that the simplicity of a deterministic nature routing algorithm such as XY, seems to be a primary and reasonable choice, not only for random traffic patterns but also for more realistic, non-uniform distributed traffic patterns, in both terms of delay and throughput for 2D mesh NoC systems. In tight traffic scenarios, of small size mesh layouts, with minimum buffering capability and relatively high PIR long packets, there is not much chance for any routing algorithm applied to overcome congestion matters, and hence to have a superiority, in terms of delay and throughput. For normal traffic scenarios of regular sized mesh layouts, XY deterministic algorithm seems to have a better performance, due to its simplicity, with DyAD ranked second, as the latter behaves partially in a deterministic mode as well. As NoC system scalability increases, delay performance, although increasing according to the proportional network size increase, would be the same for either deterministic or adaptive algorithms, as the probability of a congestion event would be eliminated for any applied routing scheme. In such a case, XY routing throughput is superior than all the other routing schemes, as by increasing number of nodes, there are much more alternative routing paths to choose, and hence simplistic XY routing scheme would behave better than other complicated and computation intensive adaptive routing schemes which are mostly based on short term traffic information retrieval. On an application traffic engineering perspective, apart from routing selection criterion, as concerns delay sensitive applications, mostly PIR and the packet size seem to have a great impact on delays, rather than buffering capability, while as concerns network throughput, a network size increase would lead to better NoC performances.