The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

A CP-LP approach to network management in OSPF routing

På svenska

Author

  • Mats Petter Wallander
  • Radoslaw Szymanek
  • Krzysztof Kuchcinski

Summary, in English

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.

Publishing year

2007

Language

English

Publication/Series

Proceedings of the ACM Symposium on Applied Computing

Document type

Conference paper

Publisher

Association for Computing Machinery (ACM)

Topic

  • Computer Science

Conference name

ACM Symposium on Applied Computing

Conference date

2007-03-11 - 2007-03-15

Status

Published

Research group

  • ESDLAB