Path selection in data communication networks

Abstract

Systems and methods are disclosed for determining a more-efficient set of routes on a communications network, given an initial set of routes that satisfies a set of demands. Consistent with disclosed embodiments, the routes can be represented as network paths on a network graph that represents the communications network. In some embodiments, a set of irreducible paths can be generated from the original network paths. The communications network can then be updated to implement routes corresponding to the set of irreducible paths. In some embodiments, a bipartite graph can be generated from the original network paths and the irreducible paths. An updated set of paths can be generated by selecting ones of the original network paths or the irreducible paths. In some embodiments, auxiliary graph can be generated from the original network paths and the irreducible paths. An updated set of paths can be generated using the auxiliary graph.