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 ro uting model applies routing tables that store the set of patent pointers as sociated with each out-neighborhood defined by the acorn. Unlike the standa rd 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 dy namically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destinati on node, as well as an independent tree generator for global point-to-point communication A fundamental fault-tolerant measure of the model is the cap acity of an acorn, i.e., the largest integer k such that each vertex outsid e the neighborhood N(nu) of the destination nu has at least k parent pointe rs. 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 partition ed into k nonempty classes labeled 1,2,...,K such that any set of sink tree s 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 in to nu. We present an linear time optimization algorithm for finding an acor n A of maximum capacity in graphs, based upon a minimax theorem. We also pr esent efficient algorithms that label the parent pointers of capacity-k aco rn A, yielding a k-independent sink tree generating schemer (C) 2000 Elsevi er Science B.V. All rights reserved.