Investigations on additive multi-constrained quality of service routing

Abstract

Providing Quality-of-Service (QoS) in packet switched networks has many challenging problems. One of them is how to determine a feasible path that satisfies additive multiple constraints. Most of the constraints in proposed protocols use centralized approaches which suffer from languid response to network dynamics and excessive overhead required for the dissemination network state information that limit their scalability and success ratio. To address the above mentioned issues, two categories of approaches are proposed. In the first category a distributed protocol OMCR (Optimized Multi Constrained Routing) is proposed. In the second category two different multi constraint algorithms namely MCPv3 (Multi Constrained Path version 3) and DCMCR (Delay Coerced Multi Constrained Routing) are proposed. The proposed protocol outperforms shortest path routing protocols both link-state and distance vector in terms of convergence time, success ratio and message overhead. MCPv3 is an approximation algorithm that finds a path between the given source-destination pair such that the path weight is not more than (1+and#945;)W where and#945; is approximation factor and W is constraint bound. By properly selecting and#945; and constraint bounds, MCPv3 performs well in terms of quality of paths, running time and scalability irrespective of nature of constraints. Another algorithm DCMCR is a variant of MCPv3 which approximates (K-1) constraints while coercing one of constraints is proposed. DCMCR is (1+and#945;) (K-1) approximation algorithm and it finds a feasible solution whose first path weight is bounded by the first constraint and approximating remaining (K-1) constraints. DCMCR is applied where one of the constraints is strictly satisfied. DCMCR performs well by choosing appropriate values of and#945; and constraint bounds. A variety of experimental validations are carried out on different scenario to analyze the performance of the proposed schemes.