Article | Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society | Determining the Non-Existence of a Compatible OSPF Metric

Title:
Determining the Non-Existence of a Compatible OSPF Metric
Author:
Peter Broström: Link√∂ping Institute of Technology, Sweden Kaj Holmberg: Link√∂ping Institute of Technology, Sweden
Download:
Full text (pdf)
Year:
2004
Conference:
Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Issue:
014
Article no.:
008
No. of pages:
1
Publication type:
Abstract
Published:
2004-12-28
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


Export in BibTex, RIS or text

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‚ÄĚ.

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Peter Broström, Kaj Holmberg
Title:
Determining the Non-Existence of a Compatible OSPF Metric
References:
No references available

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Peter Broström, Kaj Holmberg
Title:
Determining the Non-Existence of a Compatible OSPF Metric
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment