Mesh-based Data Dissemination

Mesh-based Data Dissemination

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.

Dejan Kostić obtained his Ph.D. in Computer Science at the Duke University, under Amin Vahdat. He spent the last two years of his studies and a brief stay as a postdoctoral scholar at the University of California, San Diego. He received his Master of Science degree in Computer Science from the University of Texas at Dallas, and his Bachelor of Science degree in Computer Engineering and Information Technology from the University of Belgrade, ETF (Serbia and Montenegro). In January 2006, he will be starting as a tenure-track assistant professor at the School of Computer and Communications Sciences at EPFL (Ecole Polytechnique Fédérale de Lausanne), Switzerland. His interests include Distributed Systems (Peer to Peer Computing, Overlay Networks), Computer Networks, Operating Systems, and Mobile Computing. He is a James B. Duke Fellow and a member of the ACM.

---

 

Overlay Mesh-bazirana Diseminacija Podataka

Tema ovog predavanja je diseminacija podataka velikog obima sa jednog na veći broj računara spojenih putem Interneta. Pokusaji da se ovaj problem resi na mreznom nivou koristeći IP multicast su bili neuspesni. U toku ovog predavanju opisaću Bullet, mesh-baziran distribuirani računarski sistem za diseminaciju podataka koji kreira strukturu u kojoj svaki računar prima podatke paralelno od nekoliko drugih korisnika. Da bi ova strukutura proizvela unapređenja u propusnoj moći i pouzdanosti, nekoliko problema je moralo biti reseno: 1) slanje podataka sa početnog računara, 2) lociranje podataka i pronalazenje drugih računara na mrezi, 3) pribavljanje podataka velikom brzinom od svih drugih računara, i 4) oporavljanje od kvarova i adaptiranje na promenljive mrezne karakteristike. Opisaću kako Bullet resava ove probleme tako da je brzi od konkurentskih sistema, uključujući BitTorrent, za 25-70%.

Biografija predavača:

Dejan Kostić je doktorirao na Duke University - Durham (NC), magistrirao na University of Texas at Dallas (TX), a diplomirao na Elektrotehničkom fakultetu u Beogradu. Počev od January 2006 biće professor na EPFL (Ecole Polytechnique Fédérale de Lausanne), u Svajcarskoj. Njegovi istrazivacki interesi su distribuirani računarski sistemi, računarske mreze, operativni sistemi i mobilne komunikacije.

Vreme i mesto:

Inovacioni centar ETF-a (Paviljon I), 16. decembra 2006 sa početkom u 14 časova. Posle predavanja je planiran razgovor sa studentima koji su zainteresovani za postdiplomske studije na EPFL - Svajcarska.