Performance Evaluation of Efficient Solutions for the QoS Unicast Routing

Alia Bellabas (1) , Samer Lahoud (1) , Miklós Molnár (2)

1 ATNET - Advanced Technolgy in Networking
2 MAORE - Methods, Algorithms for Operations REsearch

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.

Mots clés: multi-constrained; optimization; Routing; Quality of Service; multicast; heuristic

Domaines: Réseaux et télécommunications [cs.NI]

Alia Bellabas, Samer Lahoud, Miklós Molnár. Performance Evaluation of Efficient Solutions for the QoS Unicast Routing. Journal of Networks, 2012, 7 (1), pp.73-80. ⟨10.4304/jnw.7.1.73-80⟩. ⟨lirmm-00738055⟩