A fault-tolerant routing scheme for outerplanar networks is presented, that stores routing information succinctly and routes messages along near-shortest paths. For an n-node network containing t node and edge faults, the total space and communication is O(tαn) and the routings generated are within a factor of ((α + 1)/(α - 1))t of optimal, where α > 1 is an odd-value integer parameter. Thus, the routings can be tuned as desired. Efficient algorithms are given for setting up the routing scheme.
|Original language||English (US)|
|Number of pages||8|
|Journal||Proceedings of the International Conference on Parallel Processing|
|State||Published - Dec 1 1988|