Search Results

  1. I. Juva, Analysis of Quality of Service Routing Approaches and Algorithms, Master's Thesis, Networking Laboratory, Helsinki University of Technology, 2003 (pdf)(bib)
    Abstract: So far the Internet has offered only best effort service. All traffic is processed as quickly as possible and no preferences are given to any type of traffic. Today there are more and more applications that need service guarantees in order to function properly. These kinds of applications include for instance IP telephony, video-conference applications or video on-demand services.\ One important part of the QoS framework is the ability to find the paths that have sufficient resources to support the QoS requirements of a traffic flow. Current Internet routing protocols always forward packets to the shortest path based on hop count. This can cause problems for flows with a need for performance requirements, if the shortest path does not have the resources needed to meet these requirements. Quality of Service routing is a routing scheme that considers the quality of service requirements of a flow when making routing decisions. As opposed to traditional shortest path routing, which only considers the hop count, QoS routing is designed to find feasible paths that satisfy multiple constraints.\ This thesis is a survey on QoS routing. It presents the most important problems in QoS routing concerning path selection algorithms, cost of QoS routing, and different approaches. Routing problems for cases with one or two metric are formalized as optimization problems, and solutions algorithms are presented. For the most complex problems heuristic approximation algorithms and their evaluations found in literature are discussed. Algorithms for the important special case where available bandwidth and hop count are used as metrics are considered in detail. The cost of QoS routing, and the factors contributing to the cost, are evaluated based on simulation and implementation study results found in literature. Different approaches concerning algorithm classes, link state information and timing of path computation are discussed.\ While providing paths that satisfy the QoS guarantees of traffic flows, QoS routing can cause inter-class effects that may lead to congestion or even starvation of low priority traffic. The authors own contribution consists of a simple Markov-model to study the effects of a bandwidth reservation scheme that sets aside some portion of a link's bandwidth for low priority traffic only, in order to prevent the starvation.