FatNemo and FatScribe
Importing fat-trees from parallel architectures into overlay multicast.
Motivation and Approach
For streaming-oriented applications, where timely delivery is the key requirement, trees are generally the preferred overlay structure. But when the application is bandwidth-demanding — video conferencing, multi-party games — basic trees run into a structural problem. Bandwidth availability decreases monotonically as one ascends from the leaves, so under high load the paths near the root become the bottleneck and dominate delivery latency. Once those links are loaded, packets are buffered, then dropped.
We imported the concept of fat-trees from parallel architectures into overlay networks to address exactly that constraint. Fat-trees widen as they approach the root, giving the interior the capacity that traffic concentration demands.
We implemented two protocols on this idea: FatNemo, for performance-centric overlay multicast, and FatScribe, for DHT-based systems.
Results
Through simulation and wide-area experimentation — against each other and against alternative protocols — the fat-tree approach was shown to:
- lower the forwarding responsibility of individual nodes, increasing scalability to match the demands of high-bandwidth multicast
- reduce the height of the forwarding tree, significantly shortening delivery latency
- improve robustness to node transiency, by increasing path diversity in the overlay
That last point matters most in practice. An overlay is built from machines that leave without warning, and a structure with more distinct paths degrades more gracefully when they do.
Availability
Reference implementations were distributed to users who registered on the lab site, with the requirement that any paper using the software cite the corresponding publication. They are no longer available. Wide-area deployment used the Nixes tool set.
Papers
- FatNemo: Building a Resilient Multi-Source Multicast Fat-Tree — WCW 2004
- FatNemo: Multisource Multicast Overlay Fat-Trees — NSDI 2005 (poster)
- The Feasibility of DHT-based Streaming Multicast — MASCOTS 2005
People
Lead & PI
- Fabián E. Bustamante (Northwestern University)
Students
Collaborators
- Peter Dinda (Northwestern University)
- Dong Lu (Northwestern University)
Related Links
- Resilient Overlays and Multicast — the project FatNemo was built for