Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On open shortest path first related network optimisation problems

Pioro, Michal LU ; Szentesi, A ; Harmatos, J ; Juttner, A ; Gajowniczek, P and Kozdrowski, S (2002) In Performance Evaluation 48(1-4). p.201-223
Abstract
The paper deals with flow allocation problems in IP networks using open shortest path first (OSPF) routing. Its main purpose is to discuss and propose methods for finding settlements of OSPF link weight system realising the assumed demand pattern for the given network resources (links capacities). Such settlements can result in a significantly better network performance, as compared with the simplified weight setting heuristics typically used nowadays. Although the configuration of the link weight system is primarily done in the network planning phase, still additional re-optimisations are feasible, and in fact essential, in order to cope with major changes in traffic conditions and with major resources' failures and rearrangements. The... (More)
The paper deals with flow allocation problems in IP networks using open shortest path first (OSPF) routing. Its main purpose is to discuss and propose methods for finding settlements of OSPF link weight system realising the assumed demand pattern for the given network resources (links capacities). Such settlements can result in a significantly better network performance, as compared with the simplified weight setting heuristics typically used nowadays. Although the configuration of the link weight system is primarily done in the network planning phase, still additional re-optimisations are feasible, and in fact essential, in order to cope with major changes in traffic conditions and with major resources' failures and rearrangements. The paper formulates a relevant OSPF routing optimisation problem, proves its NP-completeness, and discusses possible heuristic approaches and related optimisation methods for solving it. Two basic approaches are considered (the direct approach and the two-phase approach) and the resulting optimisation algorithms are presented. The considerations are illustrated with numerical results. (C) 2002 Elsevier Science B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
author
; ; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
multicommodity flows, network optimisation, OSPF, traffic engineering
in
Performance Evaluation
volume
48
issue
1-4
pages
201 - 223
publisher
Elsevier
external identifiers
  • wos:000175584200011
  • scopus:0036604974
ISSN
0166-5316
DOI
10.1016/S0166-5316(02)00036-6
language
English
LU publication?
yes
id
5adcd8aa-587f-40a2-a62d-de14a047daf7 (old id 337415)
date added to LUP
2016-04-01 11:42:55
date last changed
2022-03-05 05:24:50
@article{5adcd8aa-587f-40a2-a62d-de14a047daf7,
  abstract     = {{The paper deals with flow allocation problems in IP networks using open shortest path first (OSPF) routing. Its main purpose is to discuss and propose methods for finding settlements of OSPF link weight system realising the assumed demand pattern for the given network resources (links capacities). Such settlements can result in a significantly better network performance, as compared with the simplified weight setting heuristics typically used nowadays. Although the configuration of the link weight system is primarily done in the network planning phase, still additional re-optimisations are feasible, and in fact essential, in order to cope with major changes in traffic conditions and with major resources' failures and rearrangements. The paper formulates a relevant OSPF routing optimisation problem, proves its NP-completeness, and discusses possible heuristic approaches and related optimisation methods for solving it. Two basic approaches are considered (the direct approach and the two-phase approach) and the resulting optimisation algorithms are presented. The considerations are illustrated with numerical results. (C) 2002 Elsevier Science B.V. All rights reserved.}},
  author       = {{Pioro, Michal and Szentesi, A and Harmatos, J and Juttner, A and Gajowniczek, P and Kozdrowski, S}},
  issn         = {{0166-5316}},
  keywords     = {{multicommodity flows; network optimisation; OSPF; traffic engineering}},
  language     = {{eng}},
  number       = {{1-4}},
  pages        = {{201--223}},
  publisher    = {{Elsevier}},
  series       = {{Performance Evaluation}},
  title        = {{On open shortest path first related network optimisation problems}},
  url          = {{http://dx.doi.org/10.1016/S0166-5316(02)00036-6}},
  doi          = {{10.1016/S0166-5316(02)00036-6}},
  volume       = {{48}},
  year         = {{2002}},
}