Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Constraint Programming Methods for Optimization of Single Shortest Path Routing

Wallander, Mats Petter LU (2009)
Abstract
In this thesis, we propose methods based on constraint programming (CP) for solving an optimization problem in telecommunications, the single shortest path routing problem. The problem is to find optimal values for a set of routing configuration parameters in a shortest path routing protocol, for a given network. With optimal parameters, traffic is routed through the network in a way which is optimal w.r.t. the available bandwidths of the network links. The routing parameters define a link weight for each network link, and the routing protocol makes sure that traffic between pairs of nodes in the network is sent along shortest paths w.r.t. the chosen link weight parameters. An example of such a routing protocol is the widely used Open... (More)
In this thesis, we propose methods based on constraint programming (CP) for solving an optimization problem in telecommunications, the single shortest path routing problem. The problem is to find optimal values for a set of routing configuration parameters in a shortest path routing protocol, for a given network. With optimal parameters, traffic is routed through the network in a way which is optimal w.r.t. the available bandwidths of the network links. The routing parameters define a link weight for each network link, and the routing protocol makes sure that traffic between pairs of nodes in the network is sent along shortest paths w.r.t. the chosen link weight parameters. An example of such a routing protocol is the widely used Open Shortest Path First (OSPF) protocol. We consider the version of shortest path routing that requires the shortest path to be unique for every node pair.



Our CP models for this problem use two kinds of constraints. First, we propose several different constraints for enforcing the shortest-path property, known as admissibility, on the paths used in the routing. These constraints use new problem-specific propagation methods for ruling out inadmissible sets of paths. Our models also include resource-based constraints, for modeling the bandwidth consumption on links. Here, our central resource constraint is based on a linear programming (LP) relaxation of the problem, so our method can be understood as a hybrid CP-LP method.



In the last part of the thesis, we consider different methods for organizing the search process, and present experimental results from comparing different versions of our CP models. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Beldiceanu, Nicolas, Ècole des Mines de Nantes, Frankrike
organization
publishing date
type
Thesis
publication status
published
subject
pages
152 pages
defense location
E:1406
defense date
2009-06-12 13:00:00
ISBN
978-91-628-7816-0
language
English
LU publication?
yes
id
9660b4e9-8fbf-4496-ab41-6bc1e8bb6f00 (old id 1397207)
date added to LUP
2016-04-04 09:16:46
date last changed
2018-11-21 20:52:00
@phdthesis{9660b4e9-8fbf-4496-ab41-6bc1e8bb6f00,
  abstract     = {{In this thesis, we propose methods based on constraint programming (CP) for solving an optimization problem in telecommunications, the single shortest path routing problem. The problem is to find optimal values for a set of routing configuration parameters in a shortest path routing protocol, for a given network. With optimal parameters, traffic is routed through the network in a way which is optimal w.r.t. the available bandwidths of the network links. The routing parameters define a link weight for each network link, and the routing protocol makes sure that traffic between pairs of nodes in the network is sent along shortest paths w.r.t. the chosen link weight parameters. An example of such a routing protocol is the widely used Open Shortest Path First (OSPF) protocol. We consider the version of shortest path routing that requires the shortest path to be unique for every node pair.<br/><br>
<br/><br>
Our CP models for this problem use two kinds of constraints. First, we propose several different constraints for enforcing the shortest-path property, known as admissibility, on the paths used in the routing. These constraints use new problem-specific propagation methods for ruling out inadmissible sets of paths. Our models also include resource-based constraints, for modeling the bandwidth consumption on links. Here, our central resource constraint is based on a linear programming (LP) relaxation of the problem, so our method can be understood as a hybrid CP-LP method.<br/><br>
<br/><br>
In the last part of the thesis, we consider different methods for organizing the search process, and present experimental results from comparing different versions of our CP models.}},
  author       = {{Wallander, Mats Petter}},
  isbn         = {{978-91-628-7816-0}},
  language     = {{eng}},
  school       = {{Lund University}},
  title        = {{Constraint Programming Methods for Optimization of Single Shortest Path Routing}},
  year         = {{2009}},
}