A Distributed Scheme for Resolution of the Single-Path Routing Problem

Mariusz Mycek , Michał Pióro

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 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.
Author Mariusz Mycek (FEIT / IT)
Mariusz Mycek,,
- The Institute of Telecommunications
, Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
Pages210-217
Publication size in sheets0.5
Book Cinkler Tibor, Tapolcai János, Ho Pin-Han, Rupe Jason W., Rak Jacek (eds.): Proceedings of the 9th International Workshop on Design and Reliable Communication Networks - DRCN 2013, 2013, Budapest, IEEE, ISBN 978-963-8111-79-1, [978-1-4799-0049-7], 860 p.
URL http://ieeexplore.ieee.org/xpl/abstractKeywords.jsp?arnumber=6529863
ProjectMixed-integer programming models for joint optimization of link capacity assignment, flow scheduling, and routing in fair multicommodity flow networks. Project leader: Pióro Michał, , Phone: +48 22 234-7383, application date 07-06-2011, start date 07-12-2011, end date 06-12-2014, IT/2012/badawczy/30, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
The Develpment of Digital Communicatios. Project leader: Lubacz Józef, , Phone: 22 234 65 31, start date 04-05-2012, planned end date 31-03-2013, end date 31-12-2013, IT/2012/statut, Completed
WEiTI Działalność statutowa
Languageen angielski
File
06529863.pdf 480.36 KB
Score (nominal)15
Score sourceconferenceIndex
ScoreMinisterial score = 10.0, 27-02-2020, BookChapterMatConfByIndicator
Ministerial score (2013-2016) = 15.0, 27-02-2020, BookChapterMatConfByIndicator
Publication indicators WoS Citations = 0; GS Citations = 1.0
Citation count*1 (2020-09-15)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?