Minimum protection cost tree: A tunnel-based IP fast reroute scheme

Diverse delay-sensitive realtime applications, e.g., Voice over IP, are emerging in the Internet and bringing a rigorous requirement on the transmission delay. Therefore, several IP Fast Reroute (IPFRR) schemes have been proposed. However, these schemes are all either too computationally expensive or unsatisfactory in protection coverage. In this paper, we propose Minimum Protection Cost Tree (MPCT), a tunnel-based IP Fast Reroute Scheme. First, MPCT provides 100% single-node protection coverage with direct forwarding (DF). Second, the computational complexity of MPCT is less than one full shortest path first (SPF) calculation. Third, by simulation with the data from China Education and Research Network (CERNET), Rocketfuel and BRITE, we show that even without DF, MPCT can provide more than 99% protection coverage. Besides, the protection path stretch ratios in real topologies are between 10% and 20%, which is acceptable compared with the corresponding achievement of reducing the algorithm complexity. We believe that our scheme MPCT moves a big step towards practical deployment.