A multi-tree routing scheme using acyclic orientations |
| |
Authors: | Fred S Annexstein Kenneth A Berman Tsan-Sheng Hsu Ram Swaminathan |
| |
Affiliation: | a Department of ECE and Computer Science, University of Cincinnati, P.O. Box. 210030, Cincinnati, OH 45221, USA b Institute of Information Science, Academia Sinica, Nankang 11529, Taipei, Taiwan, People's Republic of China c Bell Laboratories, Lucent Technologies, Murray Hill, NJ 07974, USA |
| |
Abstract: | 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 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. 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(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 V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T1,T2,…,Tk are pairwise independent, where tree Ti 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|