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:Stronger Necessary Conditions for the 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.:016
Abstract:This presentation is a continuation of the presentation “Determining the Non-Existence of a Compatible OSPF Metric”. It addresses the question of whether or not for a set of desired traffic patterns in an Internet Protocol telecommunication network using OSPF (Open Shortest Path First); there exists a compatible metric; i.e. weights making the routers give the specified traffic patterns. In the previous presentation it was shown that the existence of what we here call 1-valid cycles prove the non-existence of a compatible metric. In a 1-valid cycle the flow of two commodities is changed in a cycle. We here prove that a 2-valid cycle; which is a cycle in which more than two commodities are changed; exists if and only if there exists a 1-valid cycle. Furthermore; a 3-valid set of cycles is defined as a set of cycles where the flow of one commodity is changed in each cycle. Unfortunately we have not been able to show that the non-existence of 3-valid sets of cycles is sufficient for the existence of a compatible metric. However; for some special cases; such as when the desired traffic patterns only consist of a number of trees; stronger results are obtainable. Since it is fairly easy to find 1-valid cycles; we also consider the case when we know that there does not exist any 1-valid cycle.

An alternate title of this talk is “In Search of Sufficient Conditions for the Existence of a Compatible OSPF Metric”. We can formulate sufficient conditions for the existence of a compatible metric; but at the moment this formulation is not practically usable. However; this talk aims to show that the gap between the necessary and sufficient conditions is decreasing.

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/016/ecp014016.pdf
Available:2004-12-28
Publisher:Linköping University Electronic Press; Linköpings universitet

REFERENCE TO THIS PAGE
Peter Broström, Kaj Holmberg (2004). Stronger Necessary Conditions for the 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=016 (accessed 11/22/2014)