Determining the Non-Existence of a Compatible OSPF Metric

Peter Broström
Linköping Institute of Technology, Sweden

Kaj Holmberg
Linköping Institute of Technology, Sweden

Ladda ner artikelhttp://www.ep.liu.se/ecp_article/index.en.aspx?issue=014;article=008

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

Linköping Electronic Conference Proceedings 14:8, s.

Visa mer +

Publicerad: 2004-12-28


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


Many communication networks use the intra-domain protocol OSPF (Open Shortest Path First) for deciding the routing of traffic. Routers in such networks send traffic to destinations on shortest paths. The network operator control the traffic by assigning weights to each link. This set of weights is called the “metric” and is used in the shortest path computations.

It is easy to decide how traffic is routed when a network and a metric is given (this is in fact exactly what routers do). A more difficult question is whether or not there exists a metric giving a set of desired traffic patterns i.e. a metric making the desired paths shortest. Such a metric is in this work called compatible. The existence of a compatible metric is a matter of similarities between different traffic patterns; and this is further investigated in this work.

To this point; there is one known necessary condition for the existence of a compatible metric; called the “suboptimality”condition. We present more general necessary conditions for the existence of a compatible metric for set of desired shortest path graphs. In addition; we also present a polynomial method that use pairs of traffic patterns for explaining why some desired sets are not compatible with any metric. This method is successful in indicating where the conflict lie in most instances; but can sometimes fail when the type of conflict is more complicated. More complicating conflicts are treated in the presentation “Stronger necessary conditions for the existence of an compatible OSPF metric”.


Inga nyckelord är tillgängliga


Inga referenser tillgängliga

Citeringar i Crossref