liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Optimization Models and Methods for Telecommunication Networks using OSPF
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
2006 (Engelska)Doktorsavhandling, monografi (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Matematiska institutionen , 2006. , s. 16
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1032
Nyckelord [en]
Telecommunication, OSPF, LP-duality, Polynomial methods
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-7450ISBN: 91-85523-33-X (tryckt)OAI: oai:DiVA.org:liu-7450DiVA, id: diva2:22448
Disputation
2006-09-14, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (Engelska)
Opponent
Tillgänglig från: 2006-09-27 Skapad: 2006-09-27 Senast uppdaterad: 2009-05-07

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Broström, Peter

Sök vidare i DiVA

Av författaren/redaktören
Broström, Peter
Av organisationen
OptimeringsläraTekniska högskolan
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 821 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf