A distributed scheme for resolution of the single-path routing problem

The goal of the paper is to present a distributed scheme to resolving a single path routing problem in multidomain networks. The global problem is formulated as a mixed-integer program (MIP) and approached by means of branch-and-price (B&P). Problems associated with a B&P tree nodes are decomposed using the Dantzig-Wolfe method to a set of domain subproblems coordinated by a single master problem. The presented scheme applies a novel formulation of a domain subproblem that in general results in very tight bounds on the problem represented by a B&P node and hence leads to faster completion of the B&P algorithm. The issue of implementing such a scheme as a distributed network-wide process which could be run in the control plane of the multi-domain network is considered. Correctness of the scheme is verified experimentally and results of preliminary numerical tests are presented.