Accelerating Shortest-Path Computation in Ring Networks Via Graph Simplification

Abstract

This paper presents a method for graph simplification that aims to improve routing efficiency in large-scale communication networks. The approach identifies rings—linear chains of degree-2 vertices decorated with pendant trees and attached to the rest of the network via two connection points. In the simplified representation, the rings are removed and only precomputed intra-ring shortest distances from the connection points are stored. The routing problem on the simplified network then is solved via a standard single-source shortest-path (SSSP) algorithm on a reduced graph, combined with constant-time lookups in the precomputed intra-ring distance tables. Although the topology of the original network can not be recovered from the simplified representation, the proposed approach preserves the ability to compute exact next hops along the shortest paths, and is therefore lossless in an algorithmic sense w.r.t. the shortest path routing. Experimental evaluation on real-world IP Radio Access Network (IPRAN) demonstrates that, at the cost of a small preprocessing overhead (4 ms), the method reduces the number of nodes in the corresponding graph by a factor of 4 and accelerates routing information base (RIB) construction by a factor of 3. Experiments on synthetic topologies suggest that, as the fraction of nodes in rings increases, the speedup can reach up to 16×.