基于NP的Dijkstra算法硬件多线程实现与性能分析

摘要

Dijkstra算法是链路状态路由协议使用的主要算法.随着Intenet中加入的路由器数目的不断增加,该算法运行的时间花费越来越大,影响了路由协议的性能,成为链路状态路由协议的一个瓶颈问题.本文将从这一瓶颈问题出发,采用Intel公司的网络处理器IXP2400为硬件平台,设计Dijkstra算法的硬件多线程实现,从而提高处理器利用率,缓解瓶颈.最后给出一种性能分析和优化的计算方法.通过计算可以看到,在节点比较密集的星形网络拓扑结构中,多线程实现可提高两倍的性能.