liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Optimization Models and Methods for Telecommunication Networks using OSPF
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2006 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The routing in OSPF Telecommunication networks is determined by computing shortest paths with respect to link weights set by the network operator. All shortest paths to a destination are used by the routers when traffic is routed, and the routers split the traffic evenly when alternative shortest paths exist.

This thesis includes models and methods for various problems related to OSPF networks and OSPF routing. Two different models for the design of OSPF networks are presented. One model ensures that the network is capable of accommodating large parts of the traffic even if a single link fails. The OSPF protocol is modeled using constraints based on weights, and a heuristical method uses the link weights for generating good feasible solutions. The second model is based on routing patterns and does not include the link weights. The OSPF protocol is modeled by ensuring that no pair of routing patterns contains different paths between the same pair of nodes, which is a necessary condition for the existence of weights. A Lagrangean heuristic is proposed as solution method.

The thesis also includes models that can be used for determining if a set of desired routing patterns is obtainable in an OSPF network. The models are infeasible if no link weights yield shortest path graphs which are identical to the patterns, and this means that the patterns can not be used simultaneously in an OSPF network. Infeasible instances are characterized using LP-duality, and a certain structure called “valid cycle” is found in most infeasible instances. A valid cycle involves two routing patterns and indicates which parts of the patterns that are in conflict. This information can be used for finding weights that yields slightly modified patterns. Polynomial methods which can be used for finding valid cycles are presented. There are however also some infeasible instances where no valid cycle exists, so the absence of valid cycles is a necessary condition for the existence of weights. In this case, the conflict involves more than two routing patterns, and such conflicts are characterized by a structure called “3-valid set of cycles”. The absence of 3-valid sets of cycles is a stronger necessary condition for the existence of weights.

Place, publisher, year, edition, pages
Matematiska institutionen , 2006. , 16 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1032
Keyword [en]
Telecommunication, OSPF, LP-duality, Polynomial methods
National Category
URN: urn:nbn:se:liu:diva-7450ISBN: 91-85523-33-XOAI: diva2:22448
Public defence
2006-09-14, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Available from: 2006-09-27 Created: 2006-09-27 Last updated: 2009-05-07

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Broström, Peter
By organisation
Optimization The Institute of Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 690 hits
ReferencesLink to record
Permanent link

Direct link