Towards a deeper understanding of link restoration algorithms for mesh networks

S. S. Lumetta, M. Médard

Research output: Contribution to journalConference articlepeer-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
Event20th Annual Joint Conference on the IEEE Computer and Communications Societies (IEEE INFOCOM 2001) - Anchorage, AK, United States
Duration: Apr 22 2001Apr 26 2001

ASJC Scopus subject areas

  • General Computer Science
  • 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