Space-Efficient and Fault-Tolerant Message Routing in Outerplanar Networks

Greg N. Frederickson, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

An important problem in designing message routing schemes for distributed networks is to route over shortest or near-shortest paths, despite faults in the network. The straightforward approach of storing a complete routing table at each of the n nodes and recomputing the tables whenever faults occur is expensive, using θ(n2) space and communication even for sparse networks containing just one fault. This paper addresses the problem of designing space- and communication-efficient routing schemes for networks that experience faults. For any outerplanar network containing t faults, a succinct routing scheme is presented which uses O(αtn) space and communication to generate routings that are less than ((α + 1)/(α -1))t times longer than optimal, where a > 1 is an odd-valued integer parameter. Thus, the routings can be tuned as desired using a suitable amount of information. Efficient sequential and distributed algorithms are presented for setting up the routing schemes.

Original languageEnglish (US)
Pages (from-to)1529-1540
Number of pages12
JournalIEEE Transactions on Computers
Volume37
Issue number12
DOIs
StatePublished - Dec 1988

Bibliographical note

Funding Information:
Manuscript received March 3, 1988; revised July 25, 1988. G. N. Frederickson was supported in part by NSF Grant CCR-86202271 and by ONR Contract "14-86-K-0689. R. Janardan was supported in part by NSF Grants DCR-8320124 and CCR-8808574 and by a grant-in-aid of research from the Graduate School of the University of Minnesota. G. N. Frederickson is with the Department of Computer Sciences, Purdue University, West Lafayette, IN 47907. R. Janardan is with the Department of Computer Science, University of Minnesota, Minneapolis, MN 55455. IEEE Log Number 8824080.

Keywords

  • Distributed network
  • algorithms
  • fault-tolerance
  • graph
  • message routing
  • node naming
  • outerplanar graph
  • shortest paths

Fingerprint Dive into the research topics of 'Space-Efficient and Fault-Tolerant Message Routing in Outerplanar Networks'. Together they form a unique fingerprint.

Cite this