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

Qi Li, Mingwei Xu, Qing Li, Lingtao Pan, Dan Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)2082-2092
Number of pages11
JournalComputer Communications
Issue number17
Publication statusPublished - 1 Oct 2012


  • IP Fast Reroute
  • MPCT
  • Routing Resilience
  • Tunnel

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Minimum protection cost tree: A tunnel-based IP fast reroute scheme'. Together they form a unique fingerprint.

Cite this