http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Constrained_Shortest_Path_First 2026-05-04T20:50:39Z Revision history for this page on the wiki MediaWiki 1.43.1 http://debianws.lexgopc.com/wiki143/index.php?title=Constrained_Shortest_Path_First&diff=2800361&oldid=prev 2022-12-30T21:26:37Z

<p>Tag for sources</p> <p><b>New page</b></p><div>{{multiple issues|<br /> {{No footnotes|date=December 2022}}<br /> {{More references|date=December 2022}}<br /> }}<br /> <br /> &#039;&#039;&#039;Constrained Shortest Path First&#039;&#039;&#039; (CSPF) is an extension of shortest path algorithms. The path computed using CSPF is a shortest path fulfilling a set of constraints. It simply means that it runs shortest path algorithm after &#039;&#039;pruning&#039;&#039; those links that violate a given set of constraints. A &#039;&#039;constraint&#039;&#039; could be minimum bandwidth required per link (also known as bandwidth guaranteed constraint), end-to-end delay, maximum number of links traversed, include/exclude nodes. CSPF is widely used in [[Multiprotocol Label Switching|MPLS]] [[Teletraffic engineering|Traffic Engineering]]{{Citation needed|date=June 2008}}. The routing using CSPF is known as &#039;&#039;Constraint Based Routing&#039;&#039; (CBR).<br /> <br /> The path computed using CSPF could be exactly same as that of computed from [[OSPF]] and [[IS-IS]], or it could be completely different depending on the set of constraints to be met.<br /> <br /> ==Example with bandwidth constraint==<br /> [[Image:CSPF-Network.svg|thumb|right|300px|An Example network]]<br /> Consider the network to the right, where a route has to be computed from router-A to the router-C satisfying bandwidth constrained of x- units, and link cost for each link is based on hop-count (i.e., 1).<br /> <br /> If x = 50 units then CSPF will give path A → B → C.<br /> <br /> If x = 55 units then CSPF will give path A → D → E → C.<br /> <br /> If x = 90 units then CSPF will give path A → D → E → F → C.<br /> <br /> In all of these cases [[OSPF]] and [[IS-IS]] will result in path A → B → C.<br /> <br /> However, if the link costs in this topology are different, CSPF may accordingly determine a different path. For example, suppose that as before, hop count is used as link cost for all links but A → B and B → C, for which the cost is 4. In this case:<br /> <br /> If x = 50 units then CSPF will give path A → D → E → C.<br /> <br /> If x = 55 units then CSPF will give path A → D → E → C.<br /> <br /> If x = 90 units then CSPF will give path A → D → E → F → C.<br /> <br /> ==References==<br /> {{Reflist}}<br /> *{{cite book<br /> |first=Mark<br /> |last=Ziegelmann<br /> |title=Constrained Shortest Path and Related Problems. Constrained Network Optimization<br /> |publisher=[[VDM Verlag Dr. Müller]]<br /> |url=http://d-nb.info/987067745<br /> |year=2007<br /> |isbn=978-3-8364-4633-4<br /> }}<br /> <br /> [[Category:MPLS networking]]<br /> [[Category:Network protocols]]<br /> [[Category:Internet protocols]]<br /> [[Category:Routing protocols]]</div>

imported>NapoliRoma