Peter Broström
Department of Mathematics, Linköping University, Sweden
Kaj Holmberg
Department of Mathematics, Linköping University, Sweden
Download article
Published in: Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Linköping Electronic Conference Proceedings 14:1, p. 7-21
Published: 2004-12-28
ISBN:
ISSN: 1650-3686 (print), 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.
