Dejan Kostic - Department of Computer Science Duke University
Adolfo Rodriguez - Department of Computer Science Duke University
Feannie Albrecht - Department of Computer Science Duke University
Amin Vahdat - Department of Computer Science Duke University

In recent years, overlay networks have become an e ective alter-native to IP multicast for e cient point to multipoint communi-cation across the Internet. Typically, nodes self-organize with thegoal of forming an e cient overlay tree, one that meets perfor-mance targets without placing undue burden on the underlyingnetwork. In this paper, we target high-bandwidth data distribu-tion from a single source to a large number of receivers. Applica-tions include large- le transfers and real-time multimedia stream-ing. For these applications, we argue that an overlay mesh, ratherthan a tree, can deliver fundamentally higher bandwidth and re-liability relative to typical tree structures. This paper presentsBullet, a scalable and distributed algorithm that enables nodesspread across the Internet to self-organize into a high bandwidthoverlay mesh. We construct Bullet around the insight that datashould be distributed in a disjoint manner to strategic points inthe network. Individual Bullet receivers are then responsible forlocating and retrieving the data from multiple points in parallel.Key contributions of this work include: i) an algorithm thatsends data to di erent points in the overlay such that any dataobject is equally likely to appear at any node, ii) a scalable anddecentralized algorithm that allows nodes to locate and recovermissing data items, and iii) a complete implementation and eval-uation of Bullet running across the Internet and in a large-scaleemulation environment reveals up to a factor two bandwidth im-provements under a variety of circumstances. In addition, we ndthat, relative to tree-based solutions, Bullet reduces the need toperform expensive bandwidth probing. In a tree, it is critical thata node s parent delivers a high rate of application data to eachchild. In Bullet however, nodes simultaneously receive data frommultiple sources in parallel, making it less important to locateany single source capable of sustaining a high transmission rate.

Bandwidth, Overlays, Peer-to-peer