HCASP: A hop-constrained adaptive shortest-path algorithm for routing bandwidth-guaranteed tunnels in MPLS networks

We present an efficient low-cost algorithm for routing of MPLS bandwidth-guaranteed tunnels in general topology networks. The HCASP algorithm tries to achieve two objectives: the first is to limit the length of the chosen path for a certain tunnel so as not to largely exceed the length of the shortest-hop path between the ingress-egress pair; the second objective is to avoid over-loaded links at the time of tunnel establishment. Two popular schemes for routing of bandwidth-guaranteed tunnels in MPLS networks are the minimum interference routing algorithm (MIRA) and widest-shortest path routing (WSP). MIRA is known to provide excellent performance at the expense of solving a large number of maxflow problems each time a tunnel is routed. Using extensive simulation for general network topologies, we show that HCASP outperforms both MlRA and WSP for networks with a low degree of connectivity and large network diameter, whereas MIRA is better (but not significantly better than HCASP) for networks with high degree of connectivity and small network diameter. Moreover, HCASP can be applied in a distributed fashion using source routing, whereas MIRA is suitable for centralized implementation. Another advantage for HCASP is that it has a much lower computational complexity than MlRA.