Multi-constrained routing based on simulated annealing
Lists
Only you see this
Abstract
Multi-constrained quality-of-service routing (QoSR) is to find a feasible path that satisfies multiple constraints simultaneously, as an NPC problem, which is also a big challenge for the upcoming next-generation networks. In this paper, we propose SA/spl I.bar/MCP, a novel heuristic algorithm, by applying simulated annealing to Dijkstra's algorithm. This algorithm first uses a nonlinear energy function to translate multiple QoS weights into a single metric and then seeks to find a feasible path by simulated annealing. The paper outlines simulated annealing algorithm and analyzes the problems met when we apply it to QoSR. Extensive simulations demonstrate that SA/spl I.bar/MCP has good scalability regarding both network size and the number of QoS constraints with high performance. Furthermore, when most QoS requests are feasible, the running time of SA/spl I.bar/MCP is about O(k(m+nlogn)), which is only k times that of the traditional Dijkstra's algorithm, where k is the number of QoS constraints.
BibTeX
@inproceedings{cui2003multi,
author = {Yong Cui and Ke Xu and Jianping Wu and Zhongchao Yu and Youjian Zhao},
title = {{Multi-constrained routing based on simulated annealing}},
booktitle = {ICC},
year = {2003},
url = {https://openreview.net/forum?id=8kFQ6cm8Qc},
}Loading related content...