Routing based on User Requirements

Abstract

The versatility of the internet enables many applications that play an increasingly bigger role in our society. However, users have little control over the route that their internet traffic takes, which prevents them from controlling who sees their packets and how their traffic is handled. Researchers have proposed an extension to the internet, called the responsible internet, that aims to provide users with control over the route that their internet traffic takes.
Providing this control is the aim of this thesis. Users can control their route by specifying requirements that their route has to fulfill. This thesis defines the Maximum Path Requirement Intersection (MPRI) problem as the problem of finding the route that satisfies as many of the user’s requirements as possible, and this thesis proves that MPRI is NP-hard. Subsequently, both a heuristic to solve the problem in a reasonable amount of time as well as an exact algorithm that guarantees to find the globally best path are introduced. The performance of the heuristic is measured relative to the globally optimal solution given by the exact algorithm. Results show that less features allow the heuristic to have a larger search space, which improves the results; that the runtime of the heuristic scales polynomially in the number of hops between the start and end node; that the heuristic is most effective in graphs that have a power-law degree distribution and least effective in grid-like graphs; and that in a realistic setting the heuristic runs quickly while performing close to optimal.