基于线性函数的QoS路由预计算算法

多度量的服务质量路由(QoSR)作为下一代互联网的一个重要难题，具有NPC的复杂度．作者设计了启发式算法(LFP)使用线性函数将两个度量转化成单一函数值，进而通过多个不同线性函数实现了与服务质量请求无关的QoSR预计算方式．文章分析了线性函数对算法性能的影响，给出了服务质量约束的可行区域和不可行区域的线性函数判定方法．实验结果表明，算法使用少量均匀分布的线性函数，即可产生具有较高路由性能的QoSR路由表，在可扩展性和路由性能等方面均明显优于现有算法。

Precomputation for QoS Routing Based on Linear Functions

As one of the most challenging problems of the upcoming next-generation high-speed networks, quality-of-service routing (QoSR) has the complexity of NPC. This paper propose a heuristic algorithm, which converts two QoS weights to a single value by a linear function. Then multiple linear functions are selected to achieve the QoSR routing table precomputation independent of QoS request. The performance of linear functions is analyzed. This paper also give the method determining the feasible and unfeasible areas for a QoS request. Extensive simulations show that with a few linear functions in uniform distribution, the proposed algorithm can construct a well-performed QoS routing table and excels the current algorithms on both scalability and routing performance.