Algorithms for multiconstrained quality-of-service paths and restoration

Quality-of-service (QoS) routing requires finding end-to-end paths subject to given requirements. QoS routing is important for real-time multimedia applications such as video-conferencing and video-streaming. Determining a QoS path that satisfies 2 or more path constraints (such as delay, cost, and delay-jitter) is known to be NP-hard. Hence research has focused on developing pseudo-polynomial time algorithms, heuristics, and approximation algorithms for constraint-based routing problems.;We studied 3 fundamental QoS routing problems: multiconstrained path, constrained shortest path, and restoration paths for QoS routing. The objective of the multiconstrained path problem is to find a path from a source to a destination that satisfies given constraints. We proposed 6 heuristic algorithms for the multiconstrained path problem. Five of these algorithms become approximation algorithms when parameters are selected properly. The constrained shortest path problem is to find the cheapest end-to-end path subject to given requirements. We proposed 2 approximation algorithms for the constrained shortest path problem. The proposed algorithms use the notion of randomized rounding and interval partitioning which makes it possible to develop efficient and fast algorithms. Extensive experimental studies show effective performance of our proposed algorithms.;Finally, we considered failure-resilient QoS routing. Providing efficient recovery from network failures is crucial to guarantee stable QoS services. We studied restoration paths for QoS routing problem and proved that the problem is NP-hard.