Multi-constrained routing based on simulated annealing

Yong Cui, Ke Xu, Jianping Wu, Zhongchao Yu, Youjian ZhaoICC 2003 · OpenReview

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...

Figure