Metrics transform based Multi-constrained Optimal Path selection

Author

Yu Wang ; Lemin Li ; Du Xu

Author_Institution

Univ. of Electron. Sci. & Technol. of China, Chengdu

fYear

2007

fDate

11-13 July 2007

Firstpage

510

Lastpage

514

Abstract

The problem of MCOP (Multi-Constrained Optimal Path) is known to be NP-complete. A few of heuristic algorithms have been presented to solve it. In (Wang et al., 2007), a new method integrating QoS metrics with BFS (Bread-First-Search) is used to solve the MCP (multi-constrained path) problem. The MCOP problem differs from the MCP problem in that the former has to find a least cost path except for the multi-QoS constraints. Therefore, the algorithm in (Wang et al., 2007) cannot be applied to the MCOP problem straightly. In this paper, we introduce ATC_MCOP (Additive-to-Concave for MCOP) to solve the MCOP problem. The ATC_MCOP first searches three paths, and then chooses an optimal path among the three paths. From the simulation results, ATC_MCOP shows efficient performances.

Keywords

constraint theory; graph theory; optimisation; quality of service; telecommunication network routing; telecommunication network topology; tree searching; ATC_MCOP method; MCOP NP-complete problem; QoS metrics; QoS routing; bread-first-search; heuristic algorithms; metrics transform based MCOP selection; multiconstrained optimal path selection problem; truncated graph; Quality of service; Routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Circuits and Systems, 2007. ICCCAS 2007. International Conference on

Conference_Location

Kokura

Print_ISBN

978-1-4244-1473-4

Type

conf

DOI

10.1109/ICCCAS.2007.6251627

Filename

6251627