Faculty Candidate

Dejan Kostic, University of California, San Diego
Mesh-based Data Dissemination
Date: Tuesday, April 5, 2005
Time: 11:00AM
Place: Gould-Simpson, Room 701
Refreshments will be served in the 7th floor lobby of Gould-Simpson at 10:45 AM


Recently, overlay networks have emerged as a fundamental building block for evolving the network architecture. Sample uses include application-level multicast, scalable object location and routing, improving end-to-end path characteristics, service discovery, and increasing resistance to DoS attacks. This talk focuses on the multi-receiver data dissemination problem. Traditionally, researchers thought that this problem would be solved by multicasting data at the IP (network) level. Although IP multicast was unsuccessful for a variety of reasons, its tree-based distribution approach was carried over to overlays. We argue however, that trees have two fundamental limitations for data dissemination. First, since all data comes from a single parent, participants are forced to continuously expend bandwidth for probing in search of a parent with an acceptable level of bandwidth. Second, due to packet losses and failures, the bandwidth in an overlay tree is monotonically decreasing down the tree.

In this talk, I will describe Bullet, a data dissemination mesh that takes advantage of the computational and storage capabilities of end hosts to create a distribution structure where a node receives data in parallel from multiple peers. For the mesh to deliver improved bandwidth and reliability, we need to solve several key problems: i) disseminating disjoint data over the mesh, ii) locating missing content, iii) finding who to peer with (peering strategy), iv) retrieving data at the right rate from all peers (flow control), and v) recovering from failures and adapting to dynamically changing network conditions. Additionally, the system should be self-adjusting and should have few user-adjustable parameter settings. I will describe my approach to addressing all of these problems in a working, deployed system across the Internet. Bullet outperforms state-of-the-art systems, including BitTorrent, by 25-70% and performs near optimally in a range of deployment settings.

Finally, I will discuss RanSub, an abstraction for distributing state about changing, uniformly random subsets of configurable size once per application-specific epoch. I describe techniques for delivering this functionality in a scalable and decentralized manner. RanSub is generally applicable to a broad range of applications, including Bullet, because it helps to overcome inherent scaling limitations to services that require snapshots of global system characteristics.