Heuristics for the Multicriteria Routing Problem

Alia Bellabas 1 Miklos Molnar 1 Samer Lahoud 1
1 ATNET - Advanced Technolgy in Networking
IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
Abstract : In current networks, the applications require more and more quality of services. Hence, a routing algorithm has to satisfy several constraints such as delay, bandwidth or jitter. This is called multicriteria routing problem. Since the multicriteria routing is an NP-Hard problem, we propose heuristics that quickly compute paths that satisfy Quality of service (QoS) constraints between a source node and a destination node. Several solutions exist in the literature; SAMCRA (Self Adaptive Multiple Constraints Routing Algorithm) is one of the most efficient algorithms, that was proposed by Van Mieghem et al. in 2001. SAMCRA is an exact unicast multi-constrained algorithm, which may have a high combinatorial complexity. In our paper, we investigate the possibility to replace SAMCRA by an improved k shortest paths algorithm. The simulation results show that applying such an algorithm significantly reduces the computation time while giving satisfying solutions.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00538293
Contributor : Alia Bellabas <>
Submitted on : Monday, November 22, 2010 - 11:57:01 AM
Last modification on : Friday, November 16, 2018 - 1:37:48 AM

Identifiers

  • HAL Id : inria-00538293, version 1

Citation

Alia Bellabas, Miklos Molnar, Samer Lahoud. Heuristics for the Multicriteria Routing Problem. Mosharaka International Conference on Communications Computers and Applications, Oct 2009, Amman, Jordan. ⟨inria-00538293⟩

Share

Metrics

Record views

363