Peter Broström
Linköping Institute of Technology, Sweden
Kaj Holmberg
Linköping Institute of Technology, 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:8, p.
Published: 2004-12-28
ISBN:
ISSN: 1650-3686 (print), 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”.
