Charting the algorithmic complexity of waypoint routing

Saeed Akhoondian Amiri, Klaus Tycho Foerster, Riko Jacob, Stefan Schmid

Research output: Contribution to journalJournal articleResearchpeer-review

14 Citations (Scopus)

Abstract

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.

Original languageEnglish
JournalComputer Communication Review
Volume48
Issue number1
Pages (from-to)42-48
Number of pages7
ISSN0146-4833
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Algorithms
  • Complexity
  • VNFs
  • Waypoints

Fingerprint

Dive into the research topics of 'Charting the algorithmic complexity of waypoint routing'. Together they form a unique fingerprint.

Cite this