Quality of service routing in the internet; theory, complexity and algorithms

Abstract

The Internet consists of many network elements that direct packets on the correct path leading towards the destination. This process of finding and following a path to the destination is called routing. Routing is not infallible and packets may get lost: the current Internet cannot give any quality guarantees regarding the packets it transports. However, many new multi-media applications (e.g., VoIP) cannot properly operate without such guarantees. Finding paths that can meet such demands is called Quality of Service (QoS) routing. This thesis identifies several algorithmic concepts of QoS routing, which are all incorporated into our exact SAMCRA algorithm. The first large-scale performance evaluation of QoS algorithms indicates that the SAMCRA algorithm performs best. Besides SAMCRA, also algorithms for multicast QoS routing and link-disjoint QoS routing are proposed in this thesis. QoS routing is NP-complete, which means that to find the exact solution, algorithms require, in the worst case, a running time that cannot be bounded by a polynomial function. This thesis also analyzes the complexity of QoS routing and argues that it is feasible in practice. Hence, exact algorithms like SAMCRA should be used instead of heuristics. Finally, the dynamics of QoS routing are discussed and some preliminary work in this area is provided. Here, too, SAMCRA outperformed the other implemented algorithms.