Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
[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
conference location
Budapest, Hungary
conference dates
2013-03-04 - 2013-03-07
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
2016-04-04 11:47:03
date last changed
2022-01-29 22:25:45
@inproceedings{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}},
  booktitle    = {{[Host publication title missing]}},
  isbn         = {{978-1-4799-0049-7}},
  language     = {{eng}},
  pages        = {{210--217}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{A distributed scheme for resolution of the single-path routing problem}},
  url          = {{http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6529863}},
  year         = {{2013}},
}