Performance Evaluation of Efficient Solutions for the QoS Unicast Routing
Performance Evaluation of Efficient Solutions for the QoS Unicast Routing
复制标题
DOI：
10.4304/jnw.7.1.73-80
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Alia Bellabas;S. Lahoud;M. Molnár
中科院分区：
文献类型：
--
作者：
Alia Bellabas;S. Lahoud;M. Molnár
服务质量（QoS）路由（也称为多约束路由）对于新兴的网络应用至关重要，并且吸引了许多研究工作。这个 NP 难问题旨在基于延迟、带宽或抖动等多种约束来计算满足 QoS 要求的路径。在本文中，我们提出了两种快速启发式方法，可以快速计算可行路径（如果存在）。这些启发式方法与精确的 QoS 路由算法进行比较：自适应多重约束路由算法 (SAMCRA)。为此，探索了两个主轴。在第一个轴中，我们限制了启发式的执行时间。仿真结果表明，计算出的路径长度非常接近SAMCRA计算出的最优路径长度。此外，这些启发式方法满足了 80% 以上的可行请求。在第二个轴中，为了强化我们关于所提出的启发式的相关性的假设，我们强制我们的算法计算路径，直到找到可行路径（如果存在这样的路径）。那么成功率就变成100%了。此外，所找到的解决方案的质量以及我们启发式的组合复杂性仍然很有吸引力。
Quality of Service (QoS) routing known as multi-constrained routing is of crucial importance for the emerging network applications and has been attracting many research works. This NP-hard problem aims to compute paths that satisfy the QoS requirements based on multiple constraints such as the delay, the bandwidth or the jitter. In this paper, we propose two fast heuristics that quickly compute feasible paths if they exist. These heuristics are compared to the exact QoS routing algorithm: Self Adaptive Multiple Constraints Routing Algorithm (SAMCRA). For that, two main axes are explored. In the first axis, we limited the execution time of our heuristics. The simulation results show that the length of the computed paths is very close to the optimal ones that are computed by SAMCRA. Moreover, these heuristics satisfy more than 80% of the feasible requests. In the second axis, to enforce our hypothesis about the relevancy of the proposed heuristics, we force our algorithms to compute paths until a feasible path is found if such a path exists. The success rate becomes then 100%. Moreover, the qualities of found solutions as well as the combinatorial complexity of our heuristics are still attractive.