Ahmed Frikha and Samer Lahoud (2011)
Performance Evaluation of Pre-computation Algorithms for Inter-Domain QoS Routing
In: 2011 18th International Conference on Telecommunications (ICT 2011), Ayia Napa, Cyprus.
Inter-domain QoS routing is a very challenging problem
area. This problem combines the complexity of QoS routing,
with the limitations of inter-domain routing, such as
domain heterogeneity and information confidentiality. The
pre-computation offers a very promising solution for
addressing this problem. Although the pre-computation
scheme has been investigated in several previous studies
for a single routing domain, applying pre-computation on an
inter-domain level is not straightforward and necessitates
deeper investigation. In this work, we study different
algorithms for QoS routing based on pre-computation. First,
we investigate an exact algorithm. This algorithm provides
an optimal solution for the QoS routing problem. However,
its application in large scale networks is not always
practical. Second, heuristic solutions are also
investigated in this work. Particularly, a detailed study
of the ID-MEFPA and the ID-PPPA heuristics is provided.
Analytical studies and extensive simulations confirm that
the exact algorithm achieves the best success rate, but has
a very high computational complexity. The ID-MEFPA
heuristic has a lower complexity and provides a success
rate always close to the exact algorithm. When inter-domain
connectivity is high, the ID-PPPA heuristic is the most
appropriate with the lowest computation complexity and a
success rate very close to the exact algorithm.