Precomputation for finding paths with two additive weights

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.