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 language | English (US) |
|---|---|
| Pages (from-to) | 1529-1540 |
| Number of pages | 12 |
| Journal | IEEE Transactions on Computers |
| Volume | 37 |
| Issue number | 12 |
| DOIs | |
| State | Published - 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