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

Direct link
BETA
Broström, Peter
Publications (10 of 18) Show all publications
Broström, P. & Holmberg, K. (2009). Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns. Algorithmic Operations Research, 4(1), 19-35
Open this publication in new window or tab >>Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns
2009 (English)In: Algorithmic Operations Research, ISSN 1718-3235, Vol. 4, no 1, p. 19-35Article in journal (Refereed) Published
Abstract [en]

Many IP (Internet Protocol) networks use OSPF (Open Shortest Path First) for determining the routing of traffic. OSPF routers compute routing paths using link weights set by the network administrator, and the routers send traffic on all shortest paths to the destination. An interesting question is whether or not a set of prespecified routing patterns can be realized in an OSPF network. If not, we seek structural properties that explain why no such weights exist. Mathematical models for finding weights and for combining routing patterns are presented. We show that two possibly non-spanning routing patterns forming a ``valid cycle'' cannot simultaneously be obtained in an OSPF network. Two new methods for finding valid cycles are presented, illustrated by numerical examples, and shown to be faster that those previously known.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-21084 (URN)
Available from: 2009-09-28 Created: 2009-09-28 Last updated: 2013-08-29
Broström, P. & Holmberg, K. (2008). Valid Cycles: A Source of Infeasibility in Open Shortest Path First Routing. Networks, 52(4), 206-215
Open this publication in new window or tab >>Valid Cycles: A Source of Infeasibility in Open Shortest Path First Routing
2008 (English)In: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 52, no 4, p. 206-215Article in journal (Refereed) Published
Abstract [en]

Many telecommunication networks use the open shortest path first (OSPF) protocol for the routing of traffic. In such networks, each router sends the traffic on the shortest paths to the destination, with respect to the link weights assigned. An interesting question is whether or not a set of desired routing patterns can be obtained in an OSPF network by assigning appropriate weights. If not, we wish to find the source of the infeasibility. We study these issues by formulating a mathematical model and investigating its feasibility. A certain structure, called valid cycle, is found to be present in most infeasible instances. This yields new necessary conditions, stronger than those previously known, for the existence of weights yielding a set of given desired shortest path graphs. A valid cycle indicates which parts of the routing patterns are in conflict and can be used for changing the routing patterns to make the problem feasible. A polynomial algorithm for finding valid cycles is presented, the method is illustrated by a numerical example, and computational tests are reported.

Keywords
telecommunication networks, Internet Protocol, OSPF, routing, compatible weights
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-53609 (URN)10.1002/net.20232 (DOI)
Available from: 2010-01-26 Created: 2010-01-26 Last updated: 2017-12-12
Broström, P. & Holmberg, K. (2007). Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns. Linköping: Linköpings universitet
Open this publication in new window or tab >>Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns
2007 (English)Report (Other academic)
Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2007
Series
LiTH-MAT-R ; 4
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-38016 (URN)LiTH-MAT-R-2007-04-SE (ISRN)41205 (Local ID)41205 (Archive number)41205 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2013-08-29
Broström, P. & Holmberg, K. (2007). Design of OSPF Networks using Subpath Consistent Routing Patterns. Linköping: Linköpings universitet
Open this publication in new window or tab >>Design of OSPF Networks using Subpath Consistent Routing Patterns
2007 (English)Report (Other academic)
Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2007
Series
LiTH-MAT-R ; 5
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-37878 (URN)LiTH-MAT-R-2007-05-SE (ISRN)40165 (Local ID)40165 (Archive number)40165 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2013-08-29
Broström, P. & Holmberg, K. (2007). On the Extremal Structure of an OSPF Related Cone. Vietnam journal of mathematics, 35, 507-522
Open this publication in new window or tab >>On the Extremal Structure of an OSPF Related Cone
2007 (English)In: Vietnam journal of mathematics, ISSN 0866-7179, Vol. 35, p. 507-522Article in journal (Refereed) Published
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-43951 (URN)75224 (Local ID)75224 (Archive number)75224 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2013-08-29
Broström, P. & Holmberg, K. (2006). Multiobjective design of survivable IP networks. Annals of Operations Research, 147(1), 235-253
Open this publication in new window or tab >>Multiobjective design of survivable IP networks
2006 (English)In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 147, no 1, p. 235-253Article 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.

Keywords
Internet protocol, Network design, OSPF, Survivability, Weight optimization
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-50114 (URN)10.1007/s10479-006-0067-y (DOI)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-12
Broström, P. & Holmberg, K. (2006). On the Extremal Structure of an OSPF Related Cone. Linköping: Linköpings universitet
Open this publication in new window or tab >>On the Extremal Structure of an OSPF Related Cone
2006 (English)Report (Other academic)
Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2006. p. 12
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2006:2
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-32841 (URN)2006-02 (ISRN)18779 (Local ID)18779 (Archive number)18779 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-08-29Bibliographically approved
Broström, P. (2006). Optimization Models and Methods for Telecommunication Networks using OSPF. (Doctoral dissertation). : Matematiska institutionen
Open this publication in new window or tab >>Optimization Models and Methods for Telecommunication Networks using OSPF
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. p. 16
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1032
Keywords
Telecommunication, OSPF, LP-duality, Polynomial methods
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-7450 (URN)91-85523-33-X (ISBN)
Public defence
2006-09-14, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Available from: 2006-09-27 Created: 2006-09-27 Last updated: 2009-05-07
Broström, P. & Holmberg, K. (2005). A new derivation of valid cycles. Linköping: Linköpings universitet
Open this publication in new window or tab >>A new derivation of valid cycles
2005 (English)Report (Other academic)
Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2005
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-24570 (URN)LiTH-MAT-R (ISRN)6739 (Local ID)6739 (Archive number)6739 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2013-08-29
Holmberg, K. & Broström, P. (2005). Design of IP/OSPF Networks Using a Lagrangean Heuristic on an In-graph Based Model. In: L. Gouveia and C. Mourao (Ed.), Proceedings of the International Network Optimization Conference, INOC 2005: . Paper presented at INOC 2005: Lisbon, Portugal, March 20-23, 2005 (pp. 702). Lisbon, Portugal: University of Lisbon
Open this publication in new window or tab >>Design of IP/OSPF Networks Using a Lagrangean Heuristic on an In-graph Based Model
2005 (English)In: Proceedings of the International Network Optimization Conference, INOC 2005 / [ed] L. Gouveia and C. Mourao, Lisbon, Portugal: University of Lisbon , 2005, p. 702-Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
Lisbon, Portugal: University of Lisbon, 2005
Keywords
Internet Protocol, OSPF, network design, in-graph
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-30654 (URN)16250 (Local ID)16250 (Archive number)16250 (OAI)
Conference
INOC 2005: Lisbon, Portugal, March 20-23, 2005
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-11-06
Organisations

Search in DiVA

Show all publications