A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G = (V,E). The acorn routing model applies routing tables that store the set of patent 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 A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(nu) of the destination nu has at least k parent pointers. A capacity-k acorn A to destination ti is k-vertex fault-tolerant to nu. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w epsilon V - N(nu) can be partitioned into k nonempty classes labeled 1,2,...,K such that any set of sink trees T-1,T-2,..,, 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 nu. 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 schemer (C) 2000 Elsevier Science B.V. All rights reserved.