An Efficient Multipath Routing Algorithm

Abstract

This paper studies how to employ the incremental shortest path first algorithm to reduce the computational overhead of the DC (Downstream Criterion) implementation, and proposes an efficient Intra-domain routing protection algorithm based on i-SPF (ERPISPF). Theoretical analysis indicates that the time complexity of ERPISPF is less than that of constructing a shortest path tree. The experiment results show that ERPISPF reduce more than 93% computation overhead compared to the DC, and can provide the same protection ratio with DC.