Faster algorithms for construction of recovery trees enhancing QoP and QoS

Weiyi Zhang, Guoling Xue, Jian Tang, Krishnaiyan Thulasiraman

Research output: Contribution to journalArticle

26 Scopus citations

Abstract

Médard et al. proposed an elegant recovery scheme (known as the MFBG scheme) using red/blue recovery trees for multicast path protection against single link or node failures. Xue et al extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric for multifailure recovery capabilities of single failure recovery schemes. They also presented polynomial time algorithms to construct recovery trees with good QoP and quality of service (QoS). In this paper, we present faster algorithms for constructing recovery trees with good QoP and QoS performance. For QoP enhancement, our O(n+m) time algorithm has comparable performance with the previously best O(n2(n+m)) time algorithm, where n and m denote the number of nodes and the number of links in the network, respectively. For cost reduction, our O(n+m) time algorithms have comparable performance with the previously best O(n2(n+m)) time algorithms. For bottleneck bandwidth maximization, our O(m\log n) time algorithms improve the previously best O(nm) time algorithms. Simulation results show that our algorithms significantly outperform previously known algorithms in terms of running time, with comparable QoP or QoS performance.

Original languageEnglish (US)
Pages (from-to)642-655
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume16
Issue number3
DOIs
StatePublished - Jun 1 2008
Externally publishedYes

Keywords

  • Bottleneck bandwidth
  • Protection and restoration
  • Quality of protection (QoP)
  • Quality of service (QoS)
  • Redundant trees

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Faster algorithms for construction of recovery trees enhancing QoP and QoS'. Together they form a unique fingerprint.

  • Cite this