An FPGA implementation for Dijkstra's shortest path algorithm

Router is a critical networking device in a network as it has to determine for the best path between the source and the destination nodes for the packets travelling along the network. This process is important to prevent network congestion in the network. In this work, a novel hardware architecture is proposed and implemented for link state routers which make use of Dijkstra’s Shortest Path algorithm. Conventional CPU’s suffer from long load/store operations and consequently long execution times due to their sequential structure. In this work, specific datapath and controller are designed considering Dijkstra algorithm. It is shown that the proposed hardware architecture provides less running time complexity comparing to software implementations. Moreover, the similar works in the literature are examined, and the improvements are shown. The proposed hardware architecture produces result with less execution time and less logical elements.

Router è un dispositivo di rete critico in una rete in quanto deve determinare il percorso migliore tra i nodi di origine e di destinazione per i pacchetti che viaggiano lungo la rete. Questo processo è importante per impedire la congestione della rete nella rete. In questo lavoro viene proposta e implementata una nuova architettura hardware per i link state router che utilizzano l'algoritmo di Dijkstra. Le CPU convenzionali soffrono di lunghe operazioni di load / store e conseguentemente lunghi tempi di esecuzione dovuti alla loro struttura sequenziale. In questo lavoro, specifico datapath e controller sono progettati considerando l'algoritmo di Dijkstra. Si è dimostrato che l'architettura hardware proposta offre meno tempo di esecuzione rispetto alla realizzazione del software. Inoltre, vengono analizzate le opere simili in letteratura e vengono mostrati i miglioramenti. L'architettura hardware proposta produce risultati con meno tempo di esecuzione e meno elementi logici.