Paper Info
Title
A distributed scheme for resolution of the single-path routing problem
Abstract
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.
Year
Venue
Keywords
2013
DRCN
global problem,multidomain network,trees (mathematics),mixed integer program,integer programming,distributed scheme,dantzig-wolfe method,b&p tree nodes,branch-and-price,telecommunication network routing,b&p algorithm,path routing problem resolution,domain subproblem,network theory (graphs),mip,branch and price,bandwidth,topology,resource management,vectors,routing,linear programming
Field
DocType
ISSN
Routing control plane,Numerical tests,Mathematical optimization,Multipath routing,Computer science,Correctness,Destination-Sequenced Distance Vector routing,Algorithm,Integer programming,Distributed computing
Conference
2639-2313
ISBN
Citations 
PageRank 
978-1-4799-0049-7
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Mariusz Mycek1113.65
Michal Pióro229350.26