Precomputation for finding paths with two additive weights
Lists
Only you see this
Abstract
As the most challenging problems of the upcoming next-generation networks, 2-constrained quality of service routing (QoSR) is NP-complete problem, for which we propose a novel precomputation algorithm, LEFPA. This algorithm converts two additive weights to a single metric with linear energy functions (LEFs) and pre-computes QoS routing table with multiple (B) LEFs to further enhance its scalability. We first analyze the performance of LEFs and give a method to determine the feasible and unfeasible areas in the metric space for a QoS request. We then introduce the proposed LEFPA, whose computation complexity is O(B(m+nlogn+n)). Furthermore, we use three methods to evaluate the routing performance. Extensive simulations show that our LEFPA has both absolutely and competitively high performance.
BibTeX
@inproceedings{cui2003precomputation,
author = {Yong Cui and Ke Xu and Jianping Wu and Mingwei Xu},
title = {{Precomputation for finding paths with two additive weights}},
booktitle = {ICC},
year = {2003},
doi = {10.1109/icc.2003.1204253},
}Loading related content...