AbstractIn linear broadcasting, packets originally stored in one node, called the source, have to visit all other nodes of the network. Every packet has a predetermined route indicating in which order it visits the nodes. A faulty link or node of the network destroys all packets passing through it. A linear broadcasting scheme consisting of packets' routes is f-fault-tolerant if every fault-free node is visited by at least one packet for any configuration of at most f link or node failures. We estimate the minimum number of packets for which there exists an f-fault-tolerant linear broadcasting scheme in complete networks, and we construct schemes using few packets. Variations of this problem when faults can occur only in links or only in nodes are also considered.
Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]; C.4 [Performance of Systems]; G.2.1 [Discrete Mathematics]: Combinatorics; G.4 [Mathematical Software]
Additional Key Words and Phrases: broadcasting, fault-tolerance, packet, route
Selected references
- Sara Bitan and Shmuel Zaks. Optimal linear broadcast. Journal of Algorithms, 14(2):288-315, March 1993.
- Ching-Tsun Chou and Inder S. Gopal. Linear broadcast routing. Journal of Algorithms, 10(4):490-517, December 1989.