Premium
k ‐Splittable delay constrained routing problem: A branch‐and‐price approach
Author(s) -
Truffot Jérôme,
Duhamel Christophe,
Mahey Philippe
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20311
Subject(s) - computer science , routing (electronic design automation) , mathematical optimization , path (computing) , elmore delay , key (lock) , quality of service , equal cost multi path routing , static routing , computer network , mathematics , routing protocol , propagation delay , delay calculation , computer security
Routing problems, which include a QoS‐based path control, play a key role in broadband communication networks. We analyze here an algorithmic procedure based on branch‐and‐price algorithm and on the flow deviation method to solve a nonlinear k ‐splittable flow problem. The model can support end‐to‐end delay bounds on each path and we compare the behavior of the algorithm with and without these constraints. The trade‐off between QoS guarantees and CPU time is clearly established and we show that minimizing the average delay on all arcs will yield solutions close to the optimal one at a significant computational saving. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010