Advanced

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

Mycek, Mariusz and Pioro, Michal LU (2013) 9th International Conference on the Design of Reliable Communication Networks (DRCN), 2013 In [Host publication title missing] p.210-217
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
[Host publication title missing]
pages
210 - 217
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
9th International Conference on the Design of Reliable Communication Networks (DRCN), 2013
external identifiers
  • Scopus:84881102065
ISBN
978-1-4799-0049-7
language
English
LU publication?
yes
id
e5aab104-db6b-45e0-85e6-a0798fa2b5c4 (old id 3912859)
alternative location
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6529863
date added to LUP
2013-07-03 13:53:50
date last changed
2016-10-13 04:47:51
@misc{e5aab104-db6b-45e0-85e6-a0798fa2b5c4,
  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.},
  author       = {Mycek, Mariusz and Pioro, Michal},
  isbn         = {978-1-4799-0049-7},
  language     = {eng},
  pages        = {210--217},
  publisher    = {ARRAY(0x952f390)},
  series       = {[Host publication title missing]},
  title        = {A distributed scheme for resolution of the single-path routing problem},
  year         = {2013},
}