TY - JOUR
T1 - Charting the algorithmic complexity of waypoint routing
AU - Amiri, Saeed Akhoondian
AU - Foerster, Klaus Tycho
AU - Jacob, Riko
AU - Schmid, Stefan
PY - 2018/1/1
Y1 - 2018/1/1
N2 - Modern computer networks support interesting new routing models in which traffic flows from a source s to a destination t can be flexibly steered through a sequence of waypoints, such as (hardware) middleboxes or (virtualized) network functions (VNFs), to create innovative network services like service chains or segment routing. While the benefits and technological challenges of providing such routing models have been articulated and studied intensively over the last years, less is known about the underlying algorithmic traffic routing problems. The goal of this paper is to provide the network community with an overview of algorithmic techniques for waypoint routing and also inform about limitations due to computational hardness. In particular, we put the waypoint routing problem into perspective with respect to classic graph theoretical problems. For example, we find that while computing a shortest path from a source s to a destination t is simple (e.g., using Dijkstra’s algorithm), the problem of finding a shortest route from s to t via a single waypoint already features a deep combinatorial structure.
AB - Modern computer networks support interesting new routing models in which traffic flows from a source s to a destination t can be flexibly steered through a sequence of waypoints, such as (hardware) middleboxes or (virtualized) network functions (VNFs), to create innovative network services like service chains or segment routing. While the benefits and technological challenges of providing such routing models have been articulated and studied intensively over the last years, less is known about the underlying algorithmic traffic routing problems. The goal of this paper is to provide the network community with an overview of algorithmic techniques for waypoint routing and also inform about limitations due to computational hardness. In particular, we put the waypoint routing problem into perspective with respect to classic graph theoretical problems. For example, we find that while computing a shortest path from a source s to a destination t is simple (e.g., using Dijkstra’s algorithm), the problem of finding a shortest route from s to t via a single waypoint already features a deep combinatorial structure.
KW - Algorithms
KW - Complexity
KW - VNFs
KW - Waypoints
UR - http://www.scopus.com/inward/record.url?scp=85047339336&partnerID=8YFLogxK
U2 - 10.1145/3211852.3211859
DO - 10.1145/3211852.3211859
M3 - Journal article
AN - SCOPUS:85047339336
SN - 0146-4833
VL - 48
SP - 42
EP - 48
JO - Computer Communication Review
JF - Computer Communication Review
IS - 1
ER -