Determining the Non-Existence of a Compatible OSPF Metric
2004 (English)Report (Other academic)
Many telecommunication networks use Internet Protocol for deciding the routing of traffic. The specifications OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath) are very common, and state that each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. In order to have some control over the traffic distribution, the operator can assign weights to the links in the network, and these weights are used by the routers when calculating the shortest paths. It has been shown that by optimizing over the values of the weights, the performance of a network can be much improved. A difficult question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. There is one known necessary condition for the existence of such a metric, but up to now no sufficient conditions. We investigate this problem, and find more general necessary conditions for the existence of compatible weights for a set of given desired "shortest path"-graphs. A polynomial algorithm that for most cases verifies the non-existence of a compatible metric is presented. The algorithm also indicates which parts of the traffic patterns that are in conflict. A few numer;cal examples are used to illustrate the procedure, and some computational tests are reported.
Place, publisher, year, edition, pages
Linköping: University of Linköping, Department of Mathematics , 2004. , 42 p.
LiTH-MAT-R, ISSN 0348-2960 ; 6
Internet protocol, OSPF, compatible metric, optimization
IdentifiersURN: urn:nbn:se:liu:diva-22362Local ID: 1569OAI: oai:DiVA.org:liu-22362DiVA: diva2:242675