On the Forwarding Paths Produced by Internet Routing Algorithms

Seweryn Dynerowicz, Timothy Griffin

Research output: Contribution to conferencePaper

Abstract

Most Internet routing protocols have one of two algorithms lurking at their core — either Dijkstra’s algorithm in the case of link-state protocols or a distributed Bellman-Ford algorithm in the case of distance-vector or path-vector protocols. When computing simple shortest paths these protocols can be modified to utilize all best paths with a combination of next-
hop sets and Equal Cost Multi-Path (ECMP) forwarding. We show that this picture breaks down even for simple modifications to the shortest path metric. This is illustrated with widest-shortest paths where among all shortest paths only those with greatest bandwidth are considered best. In this case Bellman-Ford and Dijkstra may compute different sets of paths and neither
can compute all best paths. In addition, some paths computed by Dijkstra’s algorithm cannot be implemented with next-hop forwarding. We provide a general algebraic model that helps to clarify such anomalies. This is accomplished by computing paths within the route metric rather than with specialized algorithmic extensions. Our model exploits the theoretical distinction between global and local optima that has hitherto been applied almost exclusively to more exotic routing protocols such as BGP.
Original languageEnglish
Publication statusPublished - 10 Oct 2013
EventInternational Conference on Network Protocols - Mathematical Institute, Georg-August University, Göttingen, Germany
Duration: 7 Oct 201310 Oct 2013

Conference

ConferenceInternational Conference on Network Protocols
CountryGermany
CityGöttingen
Period7/10/1310/10/13

Fingerprint

Routing algorithms
Internet
Routing protocols
Network protocols
Internet protocols
Bandwidth
Costs

Cite this

Dynerowicz, S., & Griffin, T. (2013). On the Forwarding Paths Produced by Internet Routing Algorithms. Paper presented at International Conference on Network Protocols, Göttingen, Germany.
Dynerowicz, Seweryn ; Griffin, Timothy. / On the Forwarding Paths Produced by Internet Routing Algorithms. Paper presented at International Conference on Network Protocols, Göttingen, Germany.
@conference{52c24a1021004a479b08edae5b45f1c4,
title = "On the Forwarding Paths Produced by Internet Routing Algorithms",
abstract = "Most Internet routing protocols have one of two algorithms lurking at their core — either Dijkstra’s algorithm in the case of link-state protocols or a distributed Bellman-Ford algorithm in the case of distance-vector or path-vector protocols. When computing simple shortest paths these protocols can be modified to utilize all best paths with a combination of next-hop sets and Equal Cost Multi-Path (ECMP) forwarding. We show that this picture breaks down even for simple modifications to the shortest path metric. This is illustrated with widest-shortest paths where among all shortest paths only those with greatest bandwidth are considered best. In this case Bellman-Ford and Dijkstra may compute different sets of paths and neithercan compute all best paths. In addition, some paths computed by Dijkstra’s algorithm cannot be implemented with next-hop forwarding. We provide a general algebraic model that helps to clarify such anomalies. This is accomplished by computing paths within the route metric rather than with specialized algorithmic extensions. Our model exploits the theoretical distinction between global and local optima that has hitherto been applied almost exclusively to more exotic routing protocols such as BGP.",
author = "Seweryn Dynerowicz and Timothy Griffin",
note = "http://icnp13.informatik.uni-goettingen.de/; International Conference on Network Protocols ; Conference date: 07-10-2013 Through 10-10-2013",
year = "2013",
month = "10",
day = "10",
language = "English",

}

Dynerowicz, S & Griffin, T 2013, 'On the Forwarding Paths Produced by Internet Routing Algorithms' Paper presented at International Conference on Network Protocols, Göttingen, Germany, 7/10/13 - 10/10/13, .

On the Forwarding Paths Produced by Internet Routing Algorithms. / Dynerowicz, Seweryn; Griffin, Timothy.

2013. Paper presented at International Conference on Network Protocols, Göttingen, Germany.

Research output: Contribution to conferencePaper

TY - CONF

T1 - On the Forwarding Paths Produced by Internet Routing Algorithms

AU - Dynerowicz, Seweryn

AU - Griffin, Timothy

N1 - http://icnp13.informatik.uni-goettingen.de/

PY - 2013/10/10

Y1 - 2013/10/10

N2 - Most Internet routing protocols have one of two algorithms lurking at their core — either Dijkstra’s algorithm in the case of link-state protocols or a distributed Bellman-Ford algorithm in the case of distance-vector or path-vector protocols. When computing simple shortest paths these protocols can be modified to utilize all best paths with a combination of next-hop sets and Equal Cost Multi-Path (ECMP) forwarding. We show that this picture breaks down even for simple modifications to the shortest path metric. This is illustrated with widest-shortest paths where among all shortest paths only those with greatest bandwidth are considered best. In this case Bellman-Ford and Dijkstra may compute different sets of paths and neithercan compute all best paths. In addition, some paths computed by Dijkstra’s algorithm cannot be implemented with next-hop forwarding. We provide a general algebraic model that helps to clarify such anomalies. This is accomplished by computing paths within the route metric rather than with specialized algorithmic extensions. Our model exploits the theoretical distinction between global and local optima that has hitherto been applied almost exclusively to more exotic routing protocols such as BGP.

AB - Most Internet routing protocols have one of two algorithms lurking at their core — either Dijkstra’s algorithm in the case of link-state protocols or a distributed Bellman-Ford algorithm in the case of distance-vector or path-vector protocols. When computing simple shortest paths these protocols can be modified to utilize all best paths with a combination of next-hop sets and Equal Cost Multi-Path (ECMP) forwarding. We show that this picture breaks down even for simple modifications to the shortest path metric. This is illustrated with widest-shortest paths where among all shortest paths only those with greatest bandwidth are considered best. In this case Bellman-Ford and Dijkstra may compute different sets of paths and neithercan compute all best paths. In addition, some paths computed by Dijkstra’s algorithm cannot be implemented with next-hop forwarding. We provide a general algebraic model that helps to clarify such anomalies. This is accomplished by computing paths within the route metric rather than with specialized algorithmic extensions. Our model exploits the theoretical distinction between global and local optima that has hitherto been applied almost exclusively to more exotic routing protocols such as BGP.

M3 - Paper

ER -

Dynerowicz S, Griffin T. On the Forwarding Paths Produced by Internet Routing Algorithms. 2013. Paper presented at International Conference on Network Protocols, Göttingen, Germany.