An Effective Approximation Scheme for Multiconstrained Quality-of-Service Routing
Jun Huang, Xiaohong Huang, Yan Ma · 2010
Finding a path that satisfies multiple Quality-of-Service (QoS) requirements is vital to the deployment of current emerged services. However, existing QoS routing algorithms are not very efficient and effective at finding such path. Moreover, few works focus on two or more QoS constraints. In this paper, we propose an effective fully polynomial approximation scheme (FPAS) for multiconstrainted path optimal problem based on the technique of auxiliary graph construction. By employing the nonlinear definition of the path constraint and limited iteration of the FPAS itself, our FPAS can not only achieve the complexity reduction but generate a preferable path as well. We further analyze the Markov properties of the entire network and obtain some key parameters to reflect the routing characteristic. We experiment with different scale of random networks and compare our FPAS against previous well known studies. Our results show that FPAS can find path with lower complexity and better quality.