Resilient Overlays and Multicast
Building streaming overlays that survive the churn of the peers they are made of.
Project Overview
IP multicast was never deployed widely enough to carry streaming media across the Internet, so the job fell to overlays built out of the participants themselves. That trade is attractive — no infrastructure required — and it creates a hard problem: the network you are building on is made of ordinary machines that leave without warning. A structure that delivers efficiently when everyone stays put can collapse when a fraction of its interior nodes disappear at once.
This project ran for several years on the question of what overlay structure actually survives churn, and produced both protocols and a body of comparative measurement about how the alternatives behave when conditions stop being convenient.
Nemo
Nemo’s argument was that resilience need not be bought with overhead. Prevailing approaches improved reliability by adding redundancy — more paths, more copies, more maintenance traffic — and paid for it in bandwidth and complexity. Nemo used co-leaders to keep delivery going when interior nodes fail, achieving resilience comparable to far more expensive schemes at a fraction of the cost. Nemo: Resilient Peer-to-Peer Multicast without the Cost is the paper that carries the argument.
FatNemo
FatNemo borrowed a structure from parallel computing. Leiserson’s fat-trees widen as they approach the root, giving interior links the capacity that traffic concentration demands — exactly the property a multi-source multicast overlay needs, where conventional trees choke near the top. FatNemo builds that shape out of peers, sizing the overlay’s interior to the bandwidth it must carry rather than assuming uniform links.
DHT-Based Variants and Comparison
Alongside the purpose-built protocols we examined whether general-purpose structured overlays could do the job, releasing reference implementations of NUPastry and NUScribe and studying the feasibility of DHT-based streaming multicast. The comparative strand ran throughout the project — Resilience in Overlay Multicast Protocols, A Comparison of Resilient Overlay Multicast Approaches, and Structured and Unstructured Overlays Under the Microscope — and fed a related question about how much structure an overlay should have at all when churn is the normal condition rather than the exception.
Software
- Nemo — reference implementation of a structurally resilient, performance-centric overlay multicast protocol for streaming applications. Its own page is long gone; an Internet Archive snapshot survives.
- FatNemo and FatScribe — fat-tree overlays addressing the bandwidth constraints of conventional tree multicast.
- NUPastry and NUScribe — a resilient distributed hash table and DHT-based multicast, with a work-in-progress NUSplitStream.
- The Nixes Tool Set — the PlanetLab scripts these wide-area experiments were deployed with.
Papers
- Nemo: Resilient Peer-to-Peer Multicast — Northwestern CS technical report, 2003
- Resilient Peer-to-Peer Multicast from the Ground Up — NCA 2004
- FatNemo: Building a Resilient Multi-Source Multicast Fat-Tree — WCW 2004
- Nemo: Resilient Peer-to-Peer Multicast without the Cost — MMCN 2005
- FatNemo: Multisource Multicast Overlay Fat-Trees — NSDI 2005 (poster)
- The Feasibility of DHT-based Streaming Multicast — MASCOTS 2005
- Magellan: Performance-based, Cooperative Multicast — WCW 2005
- Elders Know Best: Handling Churn in Less Structured P2P Systems — IEEE P2P 2005
- Resilience in Overlay Multicast Protocols — MASCOTS 2006
- Structured and Unstructured Overlays Under the Microscope — USENIX ATC 2006
- Designing Less-structured P2P Systems for the Expected High Churn — IEEE/ACM Transactions on Networking, 2007
- A Comparison of Resilient Overlay Multicast Approaches — IEEE JSAC, 2007
People
Lead & PI
- Fabián E. Bustamante (Northwestern University)
Students
Collaborators
- Dong Lu (Northwestern University)
- Peter Dinda (Northwestern University)