Fault Tolerant Routing

• IIS members:
  • Tsan-sheng Hsu, IIS, Academia Sinica.
• Outside members:
  • Fred S. Annexstein, Department of ECE and Computer Science, University of Cincinnati.
  • Kenneth A. Berman, Department of ECE and Computer Science, University of Cincinnati.
  • Ram Swaminathan, Bell Laboratories, Lucent Technologies.

Together with several other researchers in the USA, we have devised a model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network. The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication.

• Fred S. Annexstein, Kenneth A. Berman, Tsan-sheng Hsu and Ram Swaminathan, "A Multi-Tree Generating Routing Scheme Using Acyclic Orientations," Theoretical Computer Science, volume 240, number 2, pages 487--494, 2000.
  • A fundamental fault-tolerant measure of the model is the {\em capacity\/} of an acorn, i.e., the largest integer $k$ such that each vertex outside the neighborhood $N(v)$ of the destination $v$ has at least $k$ parent pointers. A capacity-$k$ acorn $A$ to destination $v$ is $k$-vertex fault-tolerant to $v$. More strongly, we show $A$ supports a $k$ independent sink tree generator, i.e., the parent pointers of each vertex $w \in V \setminus N(v)$ can be partitioned into $k$ nonempty classes labeled $1, 2, \ldots, k$ such that any set of sink trees $T_1, T_2, \ldots, T_k$ are pairwise independent, where tree $T_i$ is a sink tree generated by parent pointers labeled $i$ together with the parent pointers into $v$. We present an linear time optimization algorithm for finding an acorn $A$ of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-$k$ acorn $A$, yielding a $k$-independent sink tree generating scheme.