Routing based on User Requirements
T.A.A. Bestebreur (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Fernando Kuipers – Mentor (TU Delft - Networked Systems)
Johan Pouwelse – Graduation committee member (TU Delft - Data-Intensive Systems)
A. Zapletal – Graduation committee member (TU Delft - Networked Systems)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.