Constraint Programming Methods for Optimization of Single Shortest Path Routing
(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 shortestpath property, known as admissibility, on the paths used in the routing. These constraints use new problemspecific propagation methods for ruling out inadmissible sets of paths. Our models also include resourcebased 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 CPLP 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:
http://lup.lub.lu.se/record/1397207
 author
 Wallander, Mats Petter ^{LU}
 supervisor
 opponent

 Beldiceanu, Nicolas, Ècole des Mines de Nantes, Frankrike
 organization
 publishing date
 2009
 type
 Thesis
 publication status
 published
 subject
 pages
 152 pages
 defense location
 E:1406
 defense date
 20090612 13:00
 ISSN
 16501268
 ISBN
 9789162878160
 language
 English
 LU publication?
 yes
 id
 9660b4e98fbf4496ab416bc1e8bb6f00 (old id 1397207)
 date added to LUP
 20090520 09:16:50
 date last changed
 20160919 08:45:00
@misc{9660b4e98fbf4496ab416bc1e8bb6f00, 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 shortestpath property, known as admissibility, on the paths used in the routing. These constraints use new problemspecific propagation methods for ruling out inadmissible sets of paths. Our models also include resourcebased 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 CPLP 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 = {9789162878160}, issn = {16501268}, language = {eng}, pages = {152}, title = {Constraint Programming Methods for Optimization of Single Shortest Path Routing}, year = {2009}, }