Vol 4 No 1 (2009)
Articles

Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns

Kaj Holmberg
Linkoping University
Bio
Published February 3, 2009
Keywords
  • Telecommunication,
  • Internet Protocol,
  • OSPF,
  • routing,
  • compatible weights,
  • valid cycle
  • ...More
    Less
How to Cite
Broström, P., & Holmberg, K. (2009). Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns. Algorithmic Operations Research, 4(1), Pages 19 - 35. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/4175

Abstract

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.