- 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.

Created by Tsan-sheng Hsu, last updated April 18, 2001.