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

Direktlänk
Referera
Referensformat
  • apa
  • 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 in the Design of OSPF Telecommunication Networks
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
2004 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

This thesis address optimization problems related to the design of lP (Internet Protocol) networks. One of the most commonly used IGP's (Interior Gateway Protocols) in telecommunication networks is the OSPF (Open Shortest Path First) protocol with ECM (Equal Cost Multipath) distribution. This link state based protocol uses link weights, which usually are set by an network operator, for providing routers necessary information regarding how traffic should be routed. By shortest path computations, router decide by themselves how to distribute the traffic.

One problem considered in this thesis is the problem of designing networks which are capable of accommodating large parts of the traffic when network components fails. Link failures are the most common failures, and this is the kind of disturbance which is considered. A multiobjective optimization model is presented and we search for pareto-optimal solutions using a two-phased weight based search method. This method tries to minimize the design cost simultaneously as the level of network survivability is maximized. This method uses the fact that is is easy to compute how traffic is distributed when the OSPF metric is known.

In contrary, it is a much more difficult task to determine if there are any OSPF weights that yield a desired flow distribution. This is a topic which also is studied in the thesis. Necessary conditions, which flow patterns must fulfill for being identical to the shortest paths obtained from OSPF weights, are reported. Sufficient conditions for a special type of flow patterns are also presented. The thesis also contains a polynomial method which can be used for detecting impossibilities in a set of flow patterns when this set do not correspond to the shortest paths of any OSPF weights.

Flow patterns are the basis for a new model which is developed for designing lP networks where OSPF and ECM distribution is used . This model uses a set of in-graphs in order to represent weights implicitly. The model also uses a new set of constraints used for modeling ECM distribution. The usefulness of the model is verified by computational experiments.

Ort, förlag, år, upplaga, sidor
Linköping: Linköpings universitet , 2004. , s. 10
Serie
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1102
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-22354Lokalt ID: 1560ISBN: 91-7373-988-X (tryckt)OAI: oai:DiVA.org:liu-22354DiVA, id: diva2:242667
Presentation
2004-06-03, Sal BL 32, Hus B, Linköpings Universitet, Linköping, 10:15 (Svenska)
Opponent
Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-11-06
Delarbeten
1. Multiobjective design of survivable IP networks
Öppna denna publikation i ny flik eller fönster >>Multiobjective design of survivable IP networks
2006 (Engelska)Ingår i: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 147, nr 1, s. 235-253Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Modern communication networks often use Internet Protocol routing and the intra-domain protocol OSPF (Open Shortest Path First). The routers in such a network calculate the shortest path to each destination and send the traffic on these paths, using load balancing. The issue of survivability, i.e. the question of how much traffic the network will be able to accommodate if components fail, is increasingly important. We consider the problem of designing a survivable IP network, which also requires determining the routing of the traffic. This is done by choosing the weights used for the shortest path calculations.

Nyckelord
Internet protocol, Network design, OSPF, Survivability, Weight optimization
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
urn:nbn:se:liu:diva-50114 (URN)10.1007/s10479-006-0067-y (DOI)
Tillgänglig från: 2009-10-11 Skapad: 2009-10-11 Senast uppdaterad: 2017-12-12
2. Determining the Non-Existence of a Compatible OSPF Metric
Öppna denna publikation i ny flik eller fönster >>Determining the Non-Existence of a Compatible OSPF Metric
2004 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

Many telecommunication networks use Internet Protocol for deciding the routing of traffic. The specifications OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath) are very common, and state that each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. In order to have some control over the traffic distribution, the operator can assign weights to the links in the network, and these weights are used by the routers when calculating the shortest paths. It has been shown that by optimizing over the values of the weights, the performance of a network can be much improved. A difficult question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. There is one known necessary condition for the existence of such a metric, but up to now no sufficient conditions. We investigate this problem, and find more general necessary conditions for the existence of compatible weights for a set of given desired "shortest path"-graphs. A polynomial algorithm that for most cases verifies the non-existence of a compatible metric is presented. The algorithm also indicates which parts of the traffic patterns that are in conflict. A few numer;cal examples are used to illustrate the procedure, and some computational tests are reported.

Ort, förlag, år, upplaga, sidor
Linköping: University of Linköping, Department of Mathematics, 2004. s. 42
Serie
LiTH-MAT-R, ISSN 0348-2960 ; 6
Nyckelord
Internet protocol, OSPF, compatible metric, optimization
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:liu:diva-22362 (URN)1569 (Lokalt ID)1569 (Arkivnummer)1569 (OAI)
Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-11-06
3. Stronger Necessary Conditions for the Existence of a Compatible OSPF Metric
Öppna denna publikation i ny flik eller fönster >>Stronger Necessary Conditions for the Existence of a Compatible OSPF Metric
2004 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

A dominating standard for routing in telecommunication networks is Internet Protocol with OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath). Each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. The operator can assign weights to the links in the network, which are used by the routers when calculating the shortest paths. An important question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. We describe necessary conditions, stronger than those previously discovered, for the existence of compatible weights for a set of given desired shortest path-graphs.

Ort, förlag, år, upplaga, sidor
Linköping: Linköpings universitet, 2004. s. 24
Serie
LiTH-MAT-R, ISSN 0348-2960 ; 8
Nyckelord
Internet protocol, OSPF, compatible metric, optimization
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:liu:diva-22361 (URN)1568 (Lokalt ID)1568 (Arkivnummer)1568 (OAI)
Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-11-06
4. Design of IP/OSPF Networks Using a Lagrangean Heuristic on an In-graph Based Model
Öppna denna publikation i ny flik eller fönster >>Design of IP/OSPF Networks Using a Lagrangean Heuristic on an In-graph Based Model
2005 (Engelska)Ingår i: Proceedings of the International Network Optimization Conference, INOC 2005 / [ed] L. Gouveia and C. Mourao, Lisbon, Portugal: University of Lisbon , 2005, s. 702-Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

This paper address the problem of designing IP networks where traffic is distributed in accordance with the OSPF protocol. Routers use link weights for determining how traffic is distributed. All shortest paths between pairs of routers are used and the traffic is evenly divided when several paths are shortest. We formulate a new model for the design of IP networks with OSPF and ECM distribution where weights are implicitly included. Necessary constraints for representing the shortest paths obtained from link weights by in-graphs are described. A Lagrangean heuristic is developed for verifying the usefulness of the model. Numerical experiments on test problems shows that acceptable gaps are obtained in reasonable time.

Ort, förlag, år, upplaga, sidor
Lisbon, Portugal: University of Lisbon, 2005
Nyckelord
Internet Protocol, OSPF, network design, in-graph
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:liu:diva-30654 (URN)16250 (Lokalt ID)16250 (Arkivnummer)16250 (OAI)
Konferens
INOC 2005: Lisbon, Portugal, March 20-23, 2005
Tillgänglig från: 2009-10-09 Skapad: 2009-10-09 Senast uppdaterad: 2013-11-06

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: 597 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • 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