# Congestion-Aware Routing Algorithm for NoC Using Data Packets

Authors: Khurshid Ahmad; Muhammad Athar Javed Sethi; Rehmat Ullah; Imran Ahmed; Amjad Ullah; Naveed Jan; Ghulam Mohammad Karami
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Network on Chip (NoC) is a communication framework for the Multiprocessor System on Chip (MPSoC). It is a router-based communication system. In NoC architecture, nodes of MPSoC are communicating through the network. Different routing algorithms have been developed by researchers, e.g., XY, intermittent XY, DyAD, and DyXY. The main problems in these algorithms are congestion and faults. Congestion and faults cause delay, which degrades the performance of NoC. A congestion-aware algorithm is used for the distribution of traffic over NoC and for the avoidance of congestion. In this paper, a congestion-aware routing algorithm is proposed. The algorithm works by sending congestion information in the data packet. The algorithm is implemented on a4×4 mesh NoC using FPGA. The proposed algorithm decreases latency, increases throughput, and uses less bandwidth in sharing congestion information between routers in comparison to the existing congestion-aware routing algorithms.


---

## Body

## 1. Introduction

Semiconductors revolutionized the microelectronics world in all aspects that include the military, computers, medical field, telecommunication, and aerospace. The increasingly lower cost per transistor increases the transistor’s integration up to 20 million transistors per chip because of the industrial revolution that leads to System on Chip (SoC) in the application area of military, computer peripheral, DSP, communication, and multiprocessor. SoC’s functional unit connectivity is a complex task because it is more important for the system’s overall performance [1, 2].SoC is a bus-based system, and because of nonscalability, it cannot fulfill the requirement of performance. In SoC, the bandwidth of the bus is shared between devices, and it is insufficient. Based on this reason, in 2000, a new generic interconnection template was proposed, which addresses the performance and scalability requirement for SoC, using a switching network [3, 4]. In this network, data is moved from one terminal to another in a small format called a packet. A packet contains a header, payload, and tail flits. The header comprises destination information. The switching element is called a router. When the router receives the packet, it forwards it to a neighbor router based on its destination information.Like a computer network, the routing algorithm in NoC can forward data flit (packet in NoC) from source to destination. For the avoidance of congestion and distribution of traffic over the network, the routing algorithms are used in NoC [5]. Different techniques are used by researchers in the development of routing algorithms to control congestion in NoC [6].A congestion-aware routing algorithm is developed by sending congestion information in data packets across NoC, which controls congestion. The proposed algorithm decreases latency, increases throughput, and uses less bandwidth in sharing congestion information between routers in comparison to existing congestion-aware algorithms.


## 2. Literature Review

The employed routing algorithm and topology of NoC affect the overall performance. The NoC routing algorithm is the same as the routing algorithm of a computer network with area and cost constraints [5]. The routing algorithm is the set of rules used by the NoC router to traverse a packet from a source to a destination [7–9]. XY, West first, and random routing algorithms are oblivious congestion algorithms [10, 11]. In these algorithms, routing decisions do not depend on the network’s status which affects the performance of NoC. Unlike oblivious congestion algorithms, congestion-aware algorithms consider network congestion information when sending data flit from source to destination [12–14].The DyAD routing algorithm integrates the benefit of adaptive and deterministic routing algorithms [15]. If no congestion is in a neighbor router, then routing is done through deterministic routing. Otherwise, adaptive routing is used for sending flits across NoC. In DyAD, they are flipping between routing schemes based on local congestion information. If the source sends data flit to a destination, the source router selects deterministic routing based on local congestion information. However, if congestion occurs in the neighbor router, then the latency of the flit is increased significantly. In the DyXY routing algorithm, data flit travels through the shortest path [16]. When there are several shortest routes from source to destination, then path selection is based on local congestion information. The DyXY algorithm’s weakness is when there are two paths between source and destination (e.g., path1 and path2); then based on congestion information, if there is no congestion in the neighbor router of path1, the DyXY algorithm selects path1 to traverse data flit. However, if in path1 the router next to the neighbor router is congested, then the algorithm chooses the wrong path [17].The EDXY routing algorithm overcomes the problem of the DyXY algorithm [18]. To share congestion information between routers over row (or column), a congestion wire is used. Through congestion wire, the congestion flags are spread on the path of row (or column), which tells the adjacent row (or column) that this row is congested or not. For implementation, extra hardware is used, which increases area and power consumption. The function of the FADyAD algorithm is the same as DyAD. FADyAD has the same problem as DyAD [19].In 2014, a congestion controlling routing algorithm based on a dynamic routing table in NoC was developed [20]. After every 10 seconds, routers broadcast their routing table to neighbor routers. At the time of sharing the routing table, no data flits are sent which affects the latency. Another issue is that a more congested node is declared faulty. In regional congestion-aware routing, congestion information is shared between routers when links are idle [21]. When links are not idle, no congestion information is shared between routers. When a network is loaded, and congestion occurs at any router; then, delivery of data flit to a destination is compromised [22].In MCAR, without a data packet, two types of messages propagate between routers for congestion avoidance [23]. One is normal (0), and the other is congested (1). Each router has four neighbors (north, south, east, and west). For example, when the input port on the north side of the router is crowded from normal, the output port on the north side of the router sends a congested (1) message to the north side router without taking any turns as this causes delay [24].The congestion-aware, fault-tolerant, and process variation adaptive routing algorithm (CFPA) was developed in 2019 [25]. CFPA avoids congestion based on two routing tables (queuing delay table and propagation delay table) which are maintained in each router of NoC. Overhead in CFPA is periodic broadcasting queuing delay information through queuing delay message (QD_MSGs), and extra memory is required for storage. One other issue is the calculation for finding a path which requires more processing.In MCAR, when sending a normal or congested message to a neighbor, data flit moving in that direction waits until a normal or congested message is sent. Here is the possibility to attach a normal or congested message to data flits and send it to a neighbor router. In CFPA, without sending QD_MSGs, the delay information is periodically attached to the data flit and sent to a neighbor.


## 3. Methodology

### 3.1. Congestion Information Calculation

In [26], a delay model is proposed in which input and output buffer delay and calculation of the router delay are not considered. In the CFPA routing algorithm, a new model of delays is proposed [20]. In this model, they consider propagation delay of the packet and queuing delay in its input port and output port to calculate congestion information. Equation (1) shows the total delay:
(1)TD=PD+QD,where QD is the queuing delay and PD is the propagation delay. The propagation delay is calculated based on links from the sender router output port to receiving router input port. The queuing delay is the delay that how many packets stay in the sender router output port and an input port of the receiving router.In the proposed routing algorithm, both propagation delay and queuing delay for congestion information calculation are used. Each router calculates its propagation delay and queuing delay. The total delay is the time in which the flit is staying on the router.


### 3.2. Propagation Delay

The propagation delay is the time interval taken by the packet when passing through the router. Propagation delay calculation starts when a packet enters into an input port up to when the packet is sent through the output port without waiting in a queue.PD is the propagation delay of the router, and the components of propagation delay are as below:
(i)
Input portdelay=Pi(ii)
Delay at RC (routing competition) unit ofrouter=Prc(iii)
Delay at the outputport=Pout(iv)
When packet moves from the input port to the RC unit and from RC unit to output port, thedelays=2PdlTotal propagation delay calculated from Equation (2) is the sum of all the delays at the input, output, routing competition unit, and a link between these components:
(2)PD=∑i=03Pi+Prc+Pout+2Pdli.


### 3.3. Queuing Delay

Queuing delay refers to the time that a packet can take in the queue of the input port and output port of the router. A router has four input ports and four output ports for communication with neighbor routers. The total queuing delay is the sum of all the time that flit can take on the input and output ports. So, the total queuing delays are(3)QD=∑i=03QIDi+QODi.In Equation (3), QD is the total queuing delay of the router. QIDi and QODi are the delays at their input port and output port, respectively. The components of the queuing delay of a router are illustrated in Figure 1. The total delay is calculated from Equation (1), and the average of TD is used as congestion information in the proposed routing algorithm. On this base, the router was declared to be congested or not congested. This TTD is calculated on the router and embedded in a flit to share congestion information between the routers.Figure 1
Q delay components.


### 3.4. Flit Pattern

An NoC flit (flow control unit or flow control digit) is the smallest unit of a packet that carries data from source to destination. The packet is divided into flit. Flit size influences the capability of NoC. When flit size is small, it requires a smaller memory/buffer for storage over a network or on the router. When buffer sizes are small, it shrinks the size of the router, so the size of a network on chip is decreased, but it increases the power consumption. On the other hand, when the flit size is large, the size of the router is increased, which increases the overall area of a network on chip. Flit size for different NoC structures varies, starting from 8 bits to 256 bits. The flit size is 64 bits in the proposed algorithm.The communicating data between two nodes is first divided into a packet, and then, the packet contains multiple flits. Flit contains head flit, body flit, and tail flit. Figure2 shows the structure of the flit. In Figure 2, the first three bytes are head flit, the next 4 bytes are body flit, and the last one is tail flit.Figure 2
Flit structure.


### 3.5. Head Flit

Head flit contains the source address, destination address, and congestion information. Figure3 shows a structural organization of the head flit. The first byte is the source address. In the source address, the first four bits show the location of a router on the x-axis, and the last four bits show the location on the y-axis in NoC. The second byte specifies the destination address. The source and the destination address are the same or not changing when the flit is on a route over the network. The last byte of the head flit contains congestion information that is shared between two neighbor routers.Figure 3
Head flit.The congestion information is detached and attached when the flit moves from one router to another. The first four bits of congestion information contain the total delay of a current router which is calculated from Equation (1). The last four bits have the conservation status of the router. Each router has four neighbors. The last four bits of congestion information have the congestion status of neighbor routers, and each bit shows the status of one router. Each bit has to state either 0 or 1, 1 for congested and 0 for an uncongested router.


### 3.6. Body Flit

The body flit has the data, which is sent from source to destination via the network. The size of the body flit is 4 bytes. The data in flit is placed in sequence order.


### 3.7. Tail Flit

Tail flit contains ending information of data and the sequence number of flit. The size of the tail flit is one byte. The seven bits starting from 0 to 6 in tail flit are the sequence number of flit. For example, the data size is 256 bits, which will be sent from source to destination. This data will be sent through eight different flits (flit-0 to flit-7). The flit sequence number shows the flit number on which the data is rearranged at its destination. The maximum number of flit in a single packet is up to 27. The size of data in a packet is up to 27×4 bytes.The last bit of the tail flit shows the ending of a packet. When the bit is on, it means this is the last flit. Otherwise, it is not the last flit of sent data to the destination.


### 3.8. Proposed Routing Algorithm

The proposed routing algorithm is a congestion-aware routing in which the congestion information is shared between the routers through data packets/flits. The routing decision on sending data from source to destination is taken based on the congestion information of neighbor routers. This algorithm calculates router congestion information according to Equation (1), then shares it with the neighbor router when the packet/flit moves from the current router to the neighbor router. The congestion information is embedded in the head flit and moves to the neighbor router on the route. The router detaches the packet’s congestion information and attaches its congestion information and sends the packet through the route.The proposed routing algorithm for routing decisions relies on the destination address and congestion information table (CITb). CITb stores the congestion information of the neighbor router and next-door neighbor router congestion status. The node connectivity between routers in mesh4×4 topology is the following.
(i)
Cornerrouter=2(ii)
Boundaryrouter=3(iii)
Centrerouter=4Each router stores four neighbors’ congestion information and their neighbor congestion status based on the CITb. Let routerR connect to four routers on his north, south, east, and west. Router R CITb contains congestion information of the northside route and the northside router neighbor’s congestion status. Router R also stores congestion information of all other side routers and the congestion status of their neighbors. Table 1 shows the CITb. The CITb is updated when the packet passes through the router. This routing algorithm has two parts: congestion information sharing and routing decisions.Table 1
Congestion information table (CITb).
S.No.Neighbor router locationCongestion information of the neighbor routerCongestion status of the next-door neighbor routerNorthEastWestSouth1North4 bits1 bit1 bit1 bit1 bit2East4 bits1 bit1 bit1 bit1 bit3West4 bits1 bit1 bit1 bit1 bit4South4 bits1 bit1 bit1 bit1 bit


### 3.9. Congestion Information Sharing

In this section, congestion information sharing is elaborated. The congestion information sharing algorithm calculates, stores, and shares the congestion information with the neighbor router. The congestion information sharing process cannot require a congestion propagation network. The routers’ congestion information is shared when the head flit passes from the router to its neighbor. Figure4 shows the steps of congestion information sharing for each packet.Figure 4
Congestion information sharing steps.The congestion information sharing process relies on the CITb. When the head flit is received on the router, it reads and writes the congestion information byte of the head flit. In reading, it collects congestion information and stores congestion information in CITb with respect to the location of the sender router. In writing, the router calculates congestion information of its own and congestion status of its neighbor from stored congestion information in the CITb.The congestion information of the router and the total delay of the router is calculated through Equation (1). The congestion status of the router means the router is congested or not. The router declares if its neighbor is congested or not and is dependent on the congestion information of that neighbor router which is stored in the CITb. The router will be declared congested when delay/100>0.70.When the router is declared congested, its status is set to 1; otherwise, it is zero. The congestion status of the neighbor router is attached in the congestion information byte of the head flit whenever routing decisions are finalized, and congestion information of the router is attached, when the head flit is on the output port of the router. After the attachment of congestion information byte data in the head flit, the flit is sent to the neighbor router on the route.


### 3.10. Routing Decision

The routing decision of the proposed routing algorithm depends on the destination address and congestion information stored in the CITb. The routing decision of the proposed routing algorithm has two levels. In the first level, it finds the two alternative paths for flit, which can send the packet to a destination. There are two possible paths to a destination, one on thex-axis and the other on the y-axis. In this level, it compares the destination address of the flit with its address. In comparison, first, it compares the x-axis then the y-axis for finding the two alternative paths. In the second level, it selects the route for flit between these two alternative paths. The selection of paths between these two alternative routes depends on the CITb data. In order to finalize routing decisions, it checks the neighbor router’s congestion status of alternative paths from the CITb. Comparison of the congestion status of the neighbor router of both alternative paths has three possibilities.
(i)
When both neighbor routers are uncongested, select the route with low delay information of the neighbor router(ii)
When between these two neighbor routers one is congested and another is uncongested, then an uncongested router route is selected for flit routing(iii)
When both neighbor routers are congested, then compare the congestion status of the next-door neighbor of both routesComparing the congestion status of next-door neighbor routers has three possibilities.(i)
When both next-door neighbor routers of both routes are congested, select the route with low delay information of the neighbor router(ii)
When both next-door neighbor routers of both routes are uncongested, select the route with low delay information of the neighbor router(iii)
When one next-door neighbor router is uncongested and another is congested, the route is selected on which next-door neighbor router is uncongestedFigure5 shows that the flit is routed from route P1,1 to destination router Q4,4. The route from P to Q is shown through blue arrow lines, and R‐D is the delay of the router.Figure 5
Routing fromP to Q.


## 3.1. Congestion Information Calculation

In [26], a delay model is proposed in which input and output buffer delay and calculation of the router delay are not considered. In the CFPA routing algorithm, a new model of delays is proposed [20]. In this model, they consider propagation delay of the packet and queuing delay in its input port and output port to calculate congestion information. Equation (1) shows the total delay:
(1)TD=PD+QD,where QD is the queuing delay and PD is the propagation delay. The propagation delay is calculated based on links from the sender router output port to receiving router input port. The queuing delay is the delay that how many packets stay in the sender router output port and an input port of the receiving router.In the proposed routing algorithm, both propagation delay and queuing delay for congestion information calculation are used. Each router calculates its propagation delay and queuing delay. The total delay is the time in which the flit is staying on the router.


## 3.2. Propagation Delay

The propagation delay is the time interval taken by the packet when passing through the router. Propagation delay calculation starts when a packet enters into an input port up to when the packet is sent through the output port without waiting in a queue.PD is the propagation delay of the router, and the components of propagation delay are as below:
(i)
Input portdelay=Pi(ii)
Delay at RC (routing competition) unit ofrouter=Prc(iii)
Delay at the outputport=Pout(iv)
When packet moves from the input port to the RC unit and from RC unit to output port, thedelays=2PdlTotal propagation delay calculated from Equation (2) is the sum of all the delays at the input, output, routing competition unit, and a link between these components:
(2)PD=∑i=03Pi+Prc+Pout+2Pdli.


## 3.3. Queuing Delay

Queuing delay refers to the time that a packet can take in the queue of the input port and output port of the router. A router has four input ports and four output ports for communication with neighbor routers. The total queuing delay is the sum of all the time that flit can take on the input and output ports. So, the total queuing delays are(3)QD=∑i=03QIDi+QODi.In Equation (3), QD is the total queuing delay of the router. QIDi and QODi are the delays at their input port and output port, respectively. The components of the queuing delay of a router are illustrated in Figure 1. The total delay is calculated from Equation (1), and the average of TD is used as congestion information in the proposed routing algorithm. On this base, the router was declared to be congested or not congested. This TTD is calculated on the router and embedded in a flit to share congestion information between the routers.Figure 1
Q delay components.


## 3.4. Flit Pattern

An NoC flit (flow control unit or flow control digit) is the smallest unit of a packet that carries data from source to destination. The packet is divided into flit. Flit size influences the capability of NoC. When flit size is small, it requires a smaller memory/buffer for storage over a network or on the router. When buffer sizes are small, it shrinks the size of the router, so the size of a network on chip is decreased, but it increases the power consumption. On the other hand, when the flit size is large, the size of the router is increased, which increases the overall area of a network on chip. Flit size for different NoC structures varies, starting from 8 bits to 256 bits. The flit size is 64 bits in the proposed algorithm.The communicating data between two nodes is first divided into a packet, and then, the packet contains multiple flits. Flit contains head flit, body flit, and tail flit. Figure2 shows the structure of the flit. In Figure 2, the first three bytes are head flit, the next 4 bytes are body flit, and the last one is tail flit.Figure 2
Flit structure.


## 3.5. Head Flit

Head flit contains the source address, destination address, and congestion information. Figure3 shows a structural organization of the head flit. The first byte is the source address. In the source address, the first four bits show the location of a router on the x-axis, and the last four bits show the location on the y-axis in NoC. The second byte specifies the destination address. The source and the destination address are the same or not changing when the flit is on a route over the network. The last byte of the head flit contains congestion information that is shared between two neighbor routers.Figure 3
Head flit.The congestion information is detached and attached when the flit moves from one router to another. The first four bits of congestion information contain the total delay of a current router which is calculated from Equation (1). The last four bits have the conservation status of the router. Each router has four neighbors. The last four bits of congestion information have the congestion status of neighbor routers, and each bit shows the status of one router. Each bit has to state either 0 or 1, 1 for congested and 0 for an uncongested router.


## 3.6. Body Flit

The body flit has the data, which is sent from source to destination via the network. The size of the body flit is 4 bytes. The data in flit is placed in sequence order.


## 3.7. Tail Flit

Tail flit contains ending information of data and the sequence number of flit. The size of the tail flit is one byte. The seven bits starting from 0 to 6 in tail flit are the sequence number of flit. For example, the data size is 256 bits, which will be sent from source to destination. This data will be sent through eight different flits (flit-0 to flit-7). The flit sequence number shows the flit number on which the data is rearranged at its destination. The maximum number of flit in a single packet is up to 27. The size of data in a packet is up to 27×4 bytes.The last bit of the tail flit shows the ending of a packet. When the bit is on, it means this is the last flit. Otherwise, it is not the last flit of sent data to the destination.


## 3.8. Proposed Routing Algorithm

The proposed routing algorithm is a congestion-aware routing in which the congestion information is shared between the routers through data packets/flits. The routing decision on sending data from source to destination is taken based on the congestion information of neighbor routers. This algorithm calculates router congestion information according to Equation (1), then shares it with the neighbor router when the packet/flit moves from the current router to the neighbor router. The congestion information is embedded in the head flit and moves to the neighbor router on the route. The router detaches the packet’s congestion information and attaches its congestion information and sends the packet through the route.The proposed routing algorithm for routing decisions relies on the destination address and congestion information table (CITb). CITb stores the congestion information of the neighbor router and next-door neighbor router congestion status. The node connectivity between routers in mesh4×4 topology is the following.
(i)
Cornerrouter=2(ii)
Boundaryrouter=3(iii)
Centrerouter=4Each router stores four neighbors’ congestion information and their neighbor congestion status based on the CITb. Let routerR connect to four routers on his north, south, east, and west. Router R CITb contains congestion information of the northside route and the northside router neighbor’s congestion status. Router R also stores congestion information of all other side routers and the congestion status of their neighbors. Table 1 shows the CITb. The CITb is updated when the packet passes through the router. This routing algorithm has two parts: congestion information sharing and routing decisions.Table 1
Congestion information table (CITb).
S.No.Neighbor router locationCongestion information of the neighbor routerCongestion status of the next-door neighbor routerNorthEastWestSouth1North4 bits1 bit1 bit1 bit1 bit2East4 bits1 bit1 bit1 bit1 bit3West4 bits1 bit1 bit1 bit1 bit4South4 bits1 bit1 bit1 bit1 bit


## 3.9. Congestion Information Sharing

In this section, congestion information sharing is elaborated. The congestion information sharing algorithm calculates, stores, and shares the congestion information with the neighbor router. The congestion information sharing process cannot require a congestion propagation network. The routers’ congestion information is shared when the head flit passes from the router to its neighbor. Figure4 shows the steps of congestion information sharing for each packet.Figure 4
Congestion information sharing steps.The congestion information sharing process relies on the CITb. When the head flit is received on the router, it reads and writes the congestion information byte of the head flit. In reading, it collects congestion information and stores congestion information in CITb with respect to the location of the sender router. In writing, the router calculates congestion information of its own and congestion status of its neighbor from stored congestion information in the CITb.The congestion information of the router and the total delay of the router is calculated through Equation (1). The congestion status of the router means the router is congested or not. The router declares if its neighbor is congested or not and is dependent on the congestion information of that neighbor router which is stored in the CITb. The router will be declared congested when delay/100>0.70.When the router is declared congested, its status is set to 1; otherwise, it is zero. The congestion status of the neighbor router is attached in the congestion information byte of the head flit whenever routing decisions are finalized, and congestion information of the router is attached, when the head flit is on the output port of the router. After the attachment of congestion information byte data in the head flit, the flit is sent to the neighbor router on the route.


## 3.10. Routing Decision

The routing decision of the proposed routing algorithm depends on the destination address and congestion information stored in the CITb. The routing decision of the proposed routing algorithm has two levels. In the first level, it finds the two alternative paths for flit, which can send the packet to a destination. There are two possible paths to a destination, one on thex-axis and the other on the y-axis. In this level, it compares the destination address of the flit with its address. In comparison, first, it compares the x-axis then the y-axis for finding the two alternative paths. In the second level, it selects the route for flit between these two alternative paths. The selection of paths between these two alternative routes depends on the CITb data. In order to finalize routing decisions, it checks the neighbor router’s congestion status of alternative paths from the CITb. Comparison of the congestion status of the neighbor router of both alternative paths has three possibilities.
(i)
When both neighbor routers are uncongested, select the route with low delay information of the neighbor router(ii)
When between these two neighbor routers one is congested and another is uncongested, then an uncongested router route is selected for flit routing(iii)
When both neighbor routers are congested, then compare the congestion status of the next-door neighbor of both routesComparing the congestion status of next-door neighbor routers has three possibilities.(i)
When both next-door neighbor routers of both routes are congested, select the route with low delay information of the neighbor router(ii)
When both next-door neighbor routers of both routes are uncongested, select the route with low delay information of the neighbor router(iii)
When one next-door neighbor router is uncongested and another is congested, the route is selected on which next-door neighbor router is uncongestedFigure5 shows that the flit is routed from route P1,1 to destination router Q4,4. The route from P to Q is shown through blue arrow lines, and R‐D is the delay of the router.Figure 5
Routing fromP to Q.


## 4. Results and Discussion

For the experimental setup, a4×4 mesh topology NoC having flexible routers is modeled. For routing purposes, the proposed routing algorithm is used in simulator tool ISE 14.7 webpack through Verilog language. Model NoC is implemented on the Spartan 6 XC6SLX9 FPGA development kit. UART is an intermediate node between NoC and PC for receiving and sending data from PC to FPGA kit. UART is also embedded/implemented in the FPGA kit and connected to NoC routers. Figure 6 shows the experimental setup and connectivity of PC, UART, PE, and 4×4 NoC.Figure 6
Experimental setup.For the result evaluation, an experiment was conducted by sending several packets having a size from 1 flit to 4 flits from sourceR1‐1 to all other destinations of NoC shown in Figure 5, and the latency was monitored in both situations, without congestion and with congestion. The flit size is 64 bits, and the size of the buffer is also 64 bits. One buffer in a router can store one flit at a time. The channel width is 8 bits, and in one clock cycle, 12.55 packets can be processed. The latency was analyzed in the worst case. The latency was explored through the Chip Scope Pro Analyzer. Average latency from R1‐1 to all other routers are shown in line graphs in Figures 7–21 and in bar graphs in Figures 22–36. In Figures 21–36, the blue line in the line graph and blue bar in the bar graph show the average latency from R1‐1 to all other routers when the route from R1‐1 to destination is uncongested. The red line and red bar show average latency when the route from R1‐1 to destination is congested. The latency depends on the route length or the number of nodes between source and destination, congestion status of the route, and packet size.Figure 7
Latency fromR1‐1 to R1‐2.Figure 8
Latency fromR1‐1 to R3‐1.Figure 9
Latency fromR1‐1 to R4‐1.Figure 10
Latency fromR1‐1 to R1‐2.Figure 11
Latency fromR1‐1 to R2‐2.Figure 12
Latency fromR1‐1 to R3‐2.Figure 13
Latency fromR1‐1 to R4‐2.Figure 14
Latency fromR1‐1 to R1‐3.Figure 15
Latency fromR1‐1 to R2‐3.Figure 16
Latency fromR1‐1 to R3‐3.Figure 17
Latency fromR1‐1 to R4‐3.Figure 18
Latency fromR1‐1 to R1‐4.Figure 19
Latency fromR1‐1 to R2‐4.Figure 20
Latency fromR1‐1 to R3‐4.Figure 21
Latency fromR1‐1 to R4‐4.Figure 22
Latency fromR1‐1 to R2‐1.Figure 23
Latency fromR1‐1 to R3‐1.Figure 24
Latency fromR1‐1 to R4‐1.Figure 25
Latency fromR1‐1 to R1‐2.Figure 26
Latency fromR1‐1 to R2‐2.Figure 27
Latency fromR1‐1 to R3‐2.Figure 28
Latency fromR1‐1 to R4‐2.Figure 29
Latency fromR1‐1 to R1‐3.Figure 30
Latency fromR1‐1 to R2‐3.Figure 31
Latency fromR1‐1 to R3‐3.Figure 32
Latency fromR1‐1 to R4‐3.Figure 33
Latency fromR1‐1 to R1‐4.Figure 34
Latency fromR1‐1 to R2‐4.Figure 35
Latency fromR1‐1 to R3‐4.Figure 36
Latency fromR1‐1 to R4‐4.The node betweenR1‐1 to R1‐2 and R2‐1 is 0. The highest number of nodes in this mesh topology from R1‐1 to R4‐4 is 5 when a route is uncongested. The latency is increased when the number of nodes between source and destination increases. The latency of congested routes is higher than uncongested route latency because of computation in a router for finding an uncongested route from source to destination. In Figures 21–36, a congested route means finding an alternate uncongested route by the router based on shared congestion information when the first shortest route to a destination is congested.In the experiment for the calculation of results, packet size is from 1 flit to 4 flits, and the size of flit is 64 bits. The latency in Figures21–36 increases with the packet size.


## 5. Conclusion

In this paper, a congestion-aware routing algorithm is proposed in which the congestion information between routers is shared through a data flit. The routing decision in the router from source to destination is based on the congestion information of neighbor routers. The proposed routing algorithm is a congestion-aware adaptive routing algorithm. The routing algorithms in the literature use a separate network to share congestion information which increases the area of NoC. In few routing algorithms, congestion information is transmitted through the data line, and during congestion information sharing time, the data flits are not sent. In the proposed routing algorithm, the congestion information between routers is shared when the date flit traverses over the network. The proposed routing algorithm distributes the traffic over the network to avoid congestion in the router of NoC. The route from source to destination is dependent on basis of the congestion status of the NoC router. The packet/flit in the proposed routing algorithm is sent on an uncongested route or the route which has low congestion compared to other routes to a destination. From the experiment results, the average latency is calculated in both conditions, congested route and uncongested route in the worst case. The latency decreases up to approximately 50-70% when we increase the buffer size in router and channel width.



---

*Source: 8588646-2021-08-19.xml*