Routing with multiple quality-of-services constraints: An approximation perspective |
| |
Authors: | Jun Huang Xiaohong HuangYan Ma |
| |
Affiliation: | a Institute of Networking Technology, Beijing University of Posts and Telecommunications (BUPT), Beijing 100876, PR China b Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, BUPT, Beijing 100876, PR China |
| |
Abstract: | Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a path. Moreover, few works focus on three or more QoS constraints. In this paper, we present an enhanced version of fully polynomial time approximation scheme (EFPTAS) for multiconstrainted path optimal (MCOP) problem. Specifically, we make four major contributions. We first allow the proposed algorithm to construct an auxiliary graph, through which the QoS parameters on each of the finding path can be guaranteed not to exceed the given constraints. Then we adopt a concept, called nonlinear definition of path constraints in EFPTAS for reducing both time and space complexity. Also, we enable EFPTAS to run iteratively to facilitate a progressive refinement of the finding result. In addition to these, we identify some “deployment” issues for proposed algorithm, the essential steps that how and when the EFPTAS takes place are presented. By analyzing the proposed algorithm theoretically, we find that the presented EFPTAS can find a (1+ε)-approximation path in the network with time complexity O(|E||V|/ε) (where |E| is the number of edges and |V| is the number of nodes), which outperforms the previous best-known algorithm for MCOP. We conduct an extensive comparison between the algorithm presented in this paper and previous best-known study experimentally, our results indicate that EFPTAS can find a path with low complexity and preferable quality. |
| |
Keywords: | QoS routing Multiple constraints Auxiliary graph Nonlinear definition of path constraints Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|