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

Authors

  • Peter Broström
  • Kaj Holmberg Linkoping University

Keywords:

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

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.

Author Biography

Kaj Holmberg, Linkoping University

Professor in optimization Department of Mathematics Linkoping University Sweden

Downloads

Published

2009-02-03

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

Issue

Vol. 4 No. 1 (2009)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.