Determining the Non-Existence of Compatibel OSPF Weights

Peter Broström
Department of Mathematics, Linköping University, Sweden

Kaj Holmberg
Department of Mathematics, Linköping University, Sweden

Ladda ner artikel

Ingår i: Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Linköping Electronic Conference Proceedings 14:1, s. 7-21

Visa mer +

Publicerad: 2004-12-28


ISSN: 1650-3686 (tryckt), 1650-3740 (online)


Many telecommunication networks use the OSPF protocol (Open Shortest Path First) for deciding the routing of traffic. In such networks; each router sends traffic on all shortest paths to the destination. The links in the network are assigned weights to be used by the routers when calculating the shortest paths.

An interesting question is whether or not a set of desired routing patterns can be used in an OSPF network. We investigate this problem; and find new necessary conditions for the existence of weights making the desired patterns shortest. A polynomial algorithm that for most cases verifies the non-existence of compatible weights is presented. The algorithm also indicates which parts of the traffic patterns that are in conflict. Some computational tests of the algorithm are reported.


Telecommunication networks; Internet protocol; OSPF; routing; compatible weights


Inga referenser tillgängliga

Citeringar i Crossref