Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A CP-LP approach to network management in OSPF routing

Wallander, Mats Petter LU ; Szymanek, Radoslaw LU and Kuchcinski, Krzysztof LU orcid (2007) 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
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the ACM Symposium on Applied Computing
publisher
Association for Computing Machinery (ACM)
conference name
ACM Symposium on Applied Computing
conference dates
2007-03-11 - 2007-03-15
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
2016-04-04 11:41:08
date last changed
2022-01-29 22:14:56
@inproceedings{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}},
  booktitle    = {{Proceedings of the ACM Symposium on Applied Computing}},
  language     = {{eng}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  title        = {{A CP-LP approach to network management in OSPF routing}},
  url          = {{http://dx.doi.org/10.1145/1244002.1244076}},
  doi          = {{10.1145/1244002.1244076}},
  year         = {{2007}},
}