k-splittable delay constrained routing problem: A branch and price approach

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Truffot, J., Duhamel, C., Mahey, P.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
branch and price
Broadband communication
column generation
Communication system control
Communication system traffic control
convex constraint
Costs
Delay effects
end-to-end delay
flow deviation
Fluid flow measurement
Multiprotocol label switching
Quality of service
Routing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
DOI:10.1109/DRCN.2007.4762284