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 mixedinteger program (MIP) and approached by means of branchand-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.