Towards a deeper understanding of link restoration algorithms for mesh networks

Steven Sam Lumetta, M. Médard

Research output: Contribution to journalArticlepeer-review


We study the relationship between failure localization and the properties of link restoration algorithms, employing a quantitative measure of a network's ability to recover from two-link failures. This model allows us to consider issues of failure localization that cannot be addressed through models that assume only single failures. Based on the relationship between algorithmic properties and restoration failures, we construct a failure classification hierarchy that provides insight as to the relative value of advances in algorithm design. Finally, we apply this classification scheme to three networks from the literature and discuss the results in terms of their importance for link restoration algorithms. We find that the topological constraints on restoration paths required by algorithms that embed rings within mesh networks result in significant degradation of failure localization. The preselection of restoration paths (as opposed to selection at the time of failure) also has a negative impact, although it is not as significant as the topological effect. Algorithms that make use of the mesh topology and dynamically route around existing failures come close to an inherent limit imposed by the complexity of additional algorithmic advances.

Original languageEnglish (US)
Pages (from-to)367-375
Number of pages9
JournalProceedings - IEEE INFOCOM
StatePublished - 2001

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Towards a deeper understanding of link restoration algorithms for mesh networks'. Together they form a unique fingerprint.

Cite this