A prototype of a dynamically reconfigurable processor based off-loading engine for accelerating the shortest path calculation with GNU zebra

A hardware off-loading engine to speed up the shortest path calculation in OSPF (Open Shortest Path First) has been developed. The developed system is co-designed with both hardware and software to optimize an architecture of a router for highly functional Traffic Engineering (TE). To speed up the shortest path calculation, we employ a dynamically reconflgurable processor, IPFlex DAPDNA-2, as a hardware off- loader, and newly structured a novel high-speed parallel shortest path algorithm, called MPSA (Multi-route Parallel Search Algorithm). The proposed algorithm consists of simple processing, in which multiple paths are simultaneously searched by multiple Processor Element (PE) of DAPDNA-2. Therefore, it reduces the execution time of shortest path calculation to 2.8% compared with the popular shortest path algorithm, Dijkstra's algorithm. Our prototype works together with a famous software-based router, GNU Zebra, on commodity Linux PC. The proposed architecture and prototype system can be applied to future network sophisticated TE.