Files:DescriptionFile size FormatBrowse
Fulltext0.01 MBPDF (requires Acrobat Reader)Previous | Next
  
Authors:Peter Broström: Linköping Institute of Technology, Sweden
Kaj Holmberg: Linköping Institute of Technology, Sweden
Publication title:Determining the Non-Existence of a Compatible OSPF Metric
Conference:Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Publication type: Abstract
Issue:014
Article No.:008
Abstract: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”.

Language:English
Year:2004
No. of pages:1
Series:Linköping Electronic Conference Proceedings
ISSN (print):1650-3686
ISSN (online):1650-3740
File:http://www.ep.liu.se/ecp/014/008/ecp014008.pdf
Available:2004-12-28
Publisher:Linköping University Electronic Press, Linköpings universitet

REFERENCE TO THIS PAGE
Peter Broström, Kaj Holmberg (2004). Determining the Non-Existence of a Compatible OSPF Metric, Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society http://www.ep.liu.se/ecp_article/index.en.aspx?issue=014;article=008 (accessed 7/28/2014)