Advanced

A CP-LP approach to network management in OSPF routing

Wallander, Mats Petter LU ; Szymanek, Radoslaw LU and Kuchcinski, Krzysztof LU (2007) ACM Symposium on Applied Computing In Proceedings of the ACM Symposium on Applied Computing
Abstract
In this paper, we consider a routing problem related to the widely used Open Shortest Path First (OSPF) protocol, which is considered a challenge within the Constraint Programming (CP) community. We address the special version of OSPF which requires unique and symmetrical paths. To solve this problem, we propose a novel hybrid approach which combines CP and Linear Programming (LP). Our approach employs a new global constraint with problem-specific filtering algorithms to efficiently remove inconsistent values from partial solutions. Moreover, this constraint employs two LP relaxations which are used to indicate in-feasible partial solutions due either to network capacity constraints, or to protocol-specific routing constraints. We show the... (More)
In this paper, we consider a routing problem related to the widely used Open Shortest Path First (OSPF) protocol, which is considered a challenge within the Constraint Programming (CP) community. We address the special version of OSPF which requires unique and symmetrical paths. To solve this problem, we propose a novel hybrid approach which combines CP and Linear Programming (LP). Our approach employs a new global constraint with problem-specific filtering algorithms to efficiently remove inconsistent values from partial solutions. Moreover, this constraint employs two LP relaxations which are used to indicate in-feasible partial solutions due either to network capacity constraints, or to protocol-specific routing constraints. We show the efficiency of our complete approach on backbone networks with hundreds of different demands to route. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Proceedings of the ACM Symposium on Applied Computing
publisher
ACM
conference name
ACM Symposium on Applied Computing
external identifiers
  • Scopus:35248881460
DOI
10.1145/1244002.1244076
language
English
LU publication?
yes
id
c5e4e010-f5f9-4fa4-94fe-41f334fcdb58 (old id 622406)
date added to LUP
2007-12-10 14:34:51
date last changed
2016-10-13 04:47:09
@misc{c5e4e010-f5f9-4fa4-94fe-41f334fcdb58,
  abstract     = {In this paper, we consider a routing problem related to the widely used Open Shortest Path First (OSPF) protocol, which is considered a challenge within the Constraint Programming (CP) community. We address the special version of OSPF which requires unique and symmetrical paths. To solve this problem, we propose a novel hybrid approach which combines CP and Linear Programming (LP). Our approach employs a new global constraint with problem-specific filtering algorithms to efficiently remove inconsistent values from partial solutions. Moreover, this constraint employs two LP relaxations which are used to indicate in-feasible partial solutions due either to network capacity constraints, or to protocol-specific routing constraints. We show the efficiency of our complete approach on backbone networks with hundreds of different demands to route.},
  author       = {Wallander, Mats Petter and Szymanek, Radoslaw and Kuchcinski, Krzysztof},
  language     = {eng},
  publisher    = {ARRAY(0x98d9b48)},
  series       = {Proceedings of the ACM Symposium on Applied Computing},
  title        = {A CP-LP approach to network management in OSPF routing},
  url          = {http://dx.doi.org/10.1145/1244002.1244076},
  year         = {2007},
}