NETWORK PROCESSOR AND SOFTWARE ROUTER

Get Complete Project Material File(s) Now! »

Routing Algorithm

Distributed vs. Source routing

Routing in NoC can be classified in many ways. But here we will discuss two way classifications. Routing can be classified into source routing and distributed routing. These will be discussed one by one.

Source routing

In source routing, path followed by the flit from source to destination is predetermined. All the path information from source to destination is stored in the Head flit. Router takes decision by looking at the Head flit. There is no extra logic used to calculate the path inside the router. Path information is calculated inside the source before sending flits into the network. For this purpose Path Tables are stored inside the source core or resource network interface (RNI). These Path Tables contain the complete path information for a specific destination in the network. Path information is calculated by applying routing algorithms [10]. When a core wants to send the packet into the network, it stores path information into packet header.

Distributed routing

Distributed routing can be static/deterministic or adaptive. In static routing the path between a pair is fixed. In adaptive routing there are multiple paths and actual path taken depends on network condition. In distributed routing, routing logic is implemented inside the router because there is no information about the path inside the header packet. Only destination address and some control bits are added in header packet. Each router in the network has information about the neighbouring router which is stored in the form of tables. Design for router is complex in this routing technique because extra hardware is needed for routing logic and bigger memories are required to store the routing tables.

 Junction Based Routing (JBR)

Source routing is very suitable for NoC due to its deterministic nature. But there is need of change in this algorithm due to its packet overhead. Drawback in this algorithm is that header of the packet contains all information of the path from source to destination which means it needs more buffer size to store the packet. A large buffer size means it increases the cost of the router.
A new algorithm called Junction Based Source Routing has been developed to overcome this flaw. The basic idea is to limit the required path information to be stored in every packet to a small number of bits (corresponding to only a few hops). The large distance is covered by going through intermediate temporary destinations (called Junctions) such that sub-paths (from source to a junction, junction to another junction, and junction to the destination) are always smaller than or equal to a maximum hop count. If a packet needs to go through a junction (or many junctions) the source just appends path information from source to the junction. On reaching the junction, the packet picks up path information to reach the destination (or another junction) from this junction [18].

Real Life Example

Idea of junction based source routing resembles with real life train system. In train system it is very difficult to build big platform at every station from where you can find any train for any city. Development cost is increased for each big platform in every city and for some small cities resource utilization is not efficient like big cities. To overcome this problem junctions are build in big cities. Purpose of the Junction is to give facility to passengers for the small cities or the places which are far away from the small cities. Suppose a passenger wants to go to a city or village which is not far away from its home city then he can go by direct train. But if he wants to go to a village or city which is not near then first he has to go to the Junction from there he will change the train for destination. If destination is is still far away then there might be possibility to change the train twice through another Junction. Using this idea make the source routing more efficient in term of cost.

1 Introduction
1.1 SYSTEM ON CHIP
1.2 NETWORK ON CHIP …
1.3 IMPORTANT ISSUES IN NOC BASED DESIGN
1.4 GOALS, SCOPE AND TASKS OF THE THESIS
1.5 THESIS LAYOUT
2 Theoretical Background 
2.1 NOC CONCEPT
2.2 NOC TERMINOLOGIES AND SWITCHING TECHNIQUES
2.3 COMPONENTS OF NOC ARCHITECTURE
2.4 ROUTING ALGORITHM .
2.5 ROUTER ARCHITECTURE
2.6 HANDSHAKING PROTOCOL
2.7 GAISLER’S TWO PROCESS METHOD
2.8 PROTOTYPE OF DESIGN
3 Router Design Options 
3.1 HARDWARE ROUTER
3.2 NETWORK PROCESSOR AND SOFTWARE ROUTER
3.3 TABLE BASED ROUTER .
3.4 COMPARISON .
4 Router Design for Junction Based Routing (JBR) 
4.1 PATH TABLE STORAGE OPTIONS in RNI
4.2 PACKET FORMAT
4.3 DESIGN OVERVIEW .
4.4 ROUTER DESIGN DETAILS
5 VHDL Modeling, Simulation and Results.
5.1 TEST RESULTS
5.2 IMPROVED DESIGN
5.3 RESULTS
6 FPGA Prototyping 
6.1 PROTOTYPE RESULT
7 Conclusions .
7.1 SUMMARY OF CONTRIBUTION
7.2 LIMITATION AND FUTURE WORK .
8 References
9 Appendix I

GET THE COMPLETE PROJECT
Router Architecture for Junction Based Source Routing: Design and FPGA Prototyping