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


  • Peter Broström
  • Kaj Holmberg Linkoping University


Telecommunication, Internet Protocol, OSPF, routing, compatible weights, valid cycle


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.

Author Biography

Kaj Holmberg, Linkoping University

Professor in optimization Department of Mathematics Linkoping University Sweden




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