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

Direct link
Multiobjective design of survivable IP networks
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0001-5907-0087
2006 (English)In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 147, no 1, 235-253 p.Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
2006. Vol. 147, no 1, 235-253 p.
Keyword [en]
Internet protocol, Network design, OSPF, Survivability, Weight optimization
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-50114DOI: 10.1007/s10479-006-0067-yOAI: diva2:271010
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2013-11-06
In thesis
1. Optimization in the Design of OSPF Telecommunication Networks
Open this publication in new window or tab >>Optimization in the Design of OSPF Telecommunication Networks
2004 (English)Licentiate thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2004. 10 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1102
National Category
urn:nbn:se:liu:diva-22354 (URN)1560 (Local ID)91-7373-988-X (ISBN)1560 (Archive number)1560 (OAI)
2004-06-03, Sal BL 32, Hus B, Linköpings Universitet, Linköping, 10:15 (Swedish)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2013-11-06

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Broström, PeterHolmberg, Kaj
By organisation
Optimization The Institute of Technology
In the same journal
Annals of Operations Research
Engineering and 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

Altmetric score

Total: 315 hits
ReferencesLink to record
Permanent link

Direct link