Peer-to-peer flash dissemination
Nalini Venkatasubramanian, Mayur Deshpande · 2007
Network broadcast is the fundamental problem of distributing data from a source computer/node to multiple other nodes connected by a network. While there exists an optimal solution for fast network broadcast in a homogenous network, it is a NP-hard problem in heterogenous networks. Further, current content dissemination systems are optimized for large data (hundreds of MBs to GBs). In this thesis we explore the problem of Flash Dissemination, a type of network broadcast where small to medium sized data (hundreds of KiloBytes to tens of MegaBytes) needs to be disseminated on a heterogenous network to a large number of recipients while dealing with dynamic catastrophic failures. The use cases of Flash Dissemination range from disseminating crisis related information, data update in large cluster server farms, operating systems update to millions of PCs and low-cost, scalable dissemination of web-pages. Flash Dissemination, therefore must be (a) fast, (b) scalable (must be able to handle millions of recipients) and (c) be handle to handle faults (and catastrophes). This thesis makes four main contributions: (a) Two centralized heuristics for broadcast in heterogenous networks, (b) A decentralized, fault tolerant, gossip-based protocol (CREW) for disseminating medium sized data, (c) Identification of need for Catastrophe Tolerance and (d) A protocol for fast dissemination under repeated catastrophes (Roulette). In emulation studies on an Internet testbed, CREW could disseminate medium sized data much faster than current state of the art dissemination systems. We have also developed a full distributed web-server, Flashback, that uses Roulette to handle unexpected large loads on web sites. Testing on the emulator has shown that a Flashback enabled web site could potentially handle ten times its normal web load without any investment in extra server bandwidth. Though our primary contributions are systems and protocols for fast, scalable and robust dissemination, they are still based upon heuristics. Our hope is that via a study of these systems, future researchers and practitioners can design even faster and better systems.