Space-efficient and fault-tolerant message routing in outerplanar networks

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.