A novel APSP algorithm and its application in multi domain SDN

Abstract

Finding the shortest path in networks has always been a major challenge in terms of it's computation time and space complexities. Rather than computing the shortest paths whenever it is needed, they can be pre computed and can be retrieved using hashing techniques effectively. But as the network grows or updates, storing and recomputing requires a lot of memory and processing resources. To overcome this, many approaches which work by effectively decomposing the graph have been proposed. In this paper, one such approach which effectively decomposes the given network into dense components with minimal crossovers between them is being proposed. It was analysed with the existing approaches and shown how the proposed approach works effectively in finding the shortest path in a Multi Domain SDN. It has been tested against different network topologies and in all the cases it is producing promising results. � 2014 IEEE.