Improving Routing Performance Through Distributed and Parallel Computing Approaches

Hassan A. Karimi
ICC-North Carolina Supercomputing Center, P.O. Box 12889, 3021 Cornwallis Road, Research Triangle Park, NC 27709-2889

Network analysis is one of the main functions in most Geographic Information Systems (GlS) software packages. Numerous applications utilise GIS for network analysis and network mapping functionality. Routing is one of the most required activities in network analysis on which many crucial decisions are based. Dijkstra's algorithm is a well known routing algorithm which is used widely for computing best routes in networks. Although with this algorithm best solutions can be guaranteed, the cost is a time complexity of O(n2) in the worst case. This time complexity results in very long processing times for computing best routes in large networks, which can be a serious problem for real-time applications. Alternative approaches that give a better time complexity have been suggested, most of which are based on heuristics. The major drawback of using heuristic approaches is that they do not guarantee best solutions. To achieve best solutions at low computational costs, distributed and parallel computing approaches are suggested. Discussed in this paper are a parallel algorithm for routing, different strategies for implementing parallelism, and an analysis of the performance of the parallel algorithm on a distributed heterogeneous environment and on a massively parallel machine.