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.
Type de document :
Communication dans un congrès
Mosharaka International Conference on Communications Computers and Applications, Oct 2009, Amman, Jordan. 2009
Liste complète des métadonnées

https://hal.inria.fr/inria-00538293
Contributeur : Alia Bellabas <>
Soumis le : lundi 22 novembre 2010 - 11:57:01
Dernière modification le : mardi 16 janvier 2018 - 15:54:19

Identifiants

  • 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. 2009. 〈inria-00538293〉

Partager

Métriques

Consultations de la notice

276