中文摘要：

随着互联网的飞速发展,集群结构的下一代核心路由器已经成为研究的重点.在可扩展路由器中（clus- ter router）,并行路由算法是关键问题之一.对于广泛部署的OSPF协议,最短路径树（SPT）的并行计算是其并行化的核心难点.本文提出了一种计算最短路径树的算法-分区Dijkstra算法（D-D）,分析了算法性能,并通过模拟实验验证了算法的性能.

英文摘要：

To keep up with the pace of fast development of Internet,cluster architecture has been proposed for next generation core routers.In a cluster router,parallel computation is expected.Computing shortest path tree（SPT）is a fundamental problem implementing OSPF,which is one of the most popular routing protocols.This paper presents a parallel algorithm D-D（Divisional-Dijkstra Algorithm）for computing SPT,analyzes the performance of D-D,and finally validates the D-D performance by experiments.